dir.c

一个linux下NTFS文件格式源代码

/*
 *  dir.c
 *
 *  Copyright (C) 1995-1997, 1999 Martin von L鰓is
 *  Copyright (C) 1999 Steve Dodd
 *  Copyright (C) 1999 Joseph Malicki
 */

#include "ntfstypes.h"
#include "struct.h"
#include "dir.h"
#include "macros.h"

#include <errno.h>
#include "super.h"
#include "inode.h"
#include "attr.h"
#include "support.h"
#include "util.h"

static char I30[]="$I30";

/* An index record should start with INDX, and the last word in each
   block should contain the check value. If it passes, the original
   values need to be restored */
int ntfs_check_index_record(ntfs_inode *ino, char *record)
{
	return ntfs_fixup_record(ino->vol, record, "INDX", 
				 ino->u.index.recordsize);
}

static inline int ntfs_is_top(ntfs_u64 stack)
{
	return stack==14;
}

static int ntfs_pop(ntfs_u64 *stack)
{
	static int width[16]={1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,-1};
	int res=-1;
	switch(width[*stack & 15])
	{
	case 1:res=(int)((*stack&15)>>1);
		*stack>>=4;
		break;
	case 2:res=(int)(((*stack&63)>>2)+7);
		*stack>>=6;
		break;
	case 3:res=(int)(((*stack & 255)>>3)+23);
		*stack>>=8;
		break;
	case 4:res=(int)(((*stack & 1023)>>4)+55);
		*stack>>=10;
		break;
	default:ntfs_error("Unknown encoding\n");
	}
	return res;
}

static inline unsigned int ntfs_top(void)
{
	return 14;
}

static ntfs_u64 ntfs_push(ntfs_u64 stack,int i)
{
	if(i<7)return (stack<<4)|(i<<1);
	if(i<23)return (stack<<6)|((i-7)<<2)|1;
	if(i<55)return (stack<<8)|((i-23)<<3)|3;
	if(i<120)return (stack<<10)|((i-55)<<4)|7;
	ntfs_error("Too many entries\n");
	return ~((ntfs_u64)0);
}

#if 0
static void ntfs_display_stack(ntfs_u64 stack)
{
	while(!ntfs_is_top(stack))
	{
		printf("%d ",ntfs_pop(&stack));
	}
	printf("\n");
}
#endif

/* True if the entry points to another block of entries */
static inline int ntfs_entry_has_subnodes(char* entry)
{
	return (int)NTFS_GETU8(entry+12)&1;
}

/* True if it is not the 'end of dir' entry */
static inline int ntfs_entry_is_used(char* entry)
{
	return (int)(NTFS_GETU8(entry+12)&2)==0;
}

static int ntfs_allocate_index_block(ntfs_iterate_s *walk)
{
	ntfs_attribute *allocation=0,*bitmap=0;
	int error,size,i,bit;
	ntfs_u8 *bmap;
	ntfs_io io;
	ntfs_volume *vol=walk->dir->vol;

	/* check for allocation attribute */
	allocation=ntfs_find_attr(walk->dir,vol->at_index_allocation,I30);
	if(!allocation){
		ntfs_u8 bmp[8];
		/* create index allocation attribute */
		error=ntfs_create_attr(walk->dir,vol->at_index_allocation,I30,
				       0,0,&allocation);
		if(error)return error;
		ntfs_bzero(bmp,sizeof(bmp));
		error=ntfs_create_attr(walk->dir,vol->at_bitmap,I30,
				       bmp,sizeof(bmp),&bitmap);
		if(error)return error;
	}else
		bitmap=ntfs_find_attr(walk->dir,vol->at_bitmap,I30);
	if(!bitmap){
		ntfs_error("Directory w/o bitmap\n");
		return EINVAL;
	}
	size=bitmap->size;
	bmap=ntfs_malloc(size);
	if(!bmap)return ENOMEM;
	io.fn_put=ntfs_put;
	io.fn_get=ntfs_get;
	io.param=bmap;
	io.size=size;
	error=ntfs_read_attr(walk->dir,vol->at_bitmap,I30,0,&io);
	if(error){
		ntfs_free(bmap);
		return error;
	}
	if(io.size!=size){
		ntfs_free(bmap);
		return EIO;
	}
	
	/* allocate a bit */
	for(i=bit=0;i<size;i++){
		if(bmap[i]==0xFF)continue;
		for(bit=0;bit<8;bit++)
			if(((bmap[i]>>bit) & 1) == 0)
				break;
		if(bit!=8)break;
	}
	if(i==size)
		/* FIXME: extend bitmap */
		return EOPNOTSUPP;
	walk->newblock=(i*8+bit)*walk->dir->u.index.clusters_per_record;
	bmap[i]|= 1<<bit;
	io.param=bmap;
	io.size=size;
	error=ntfs_write_attr(walk->dir,vol->at_bitmap,I30,0,&io);
	if(error || io.size!=size){
		ntfs_free(bmap);
		return error?error:EIO;
	}
	ntfs_free(bmap);

	/* check whether record is out of allocated range */
	size=allocation->size;
	if(walk->newblock * vol->clustersize >= size){
		/* build index record */
		int s1=walk->dir->u.index.recordsize;
		int nr_fix = s1/vol->blocksize+1;
		int hsize;
		char *record=ntfs_malloc(s1);
		if( !record )
			return ENOMEM;
		ntfs_bzero(record,s1);
		/* magic */
		ntfs_memcpy(record,"INDX",4);
		/* offset to fixups */
		NTFS_PUTU16(record+4,0x28);
		/* number of fixups */
		NTFS_PUTU16(record+6,nr_fix);
		/* FIXME: log file number */
		/* VCN of buffer */
		NTFS_PUTU64(record+0x10,walk->newblock);
		/* header size. */
		hsize = 0x10+2*nr_fix;
		hsize = (hsize+7) & ~7; /* Align. */
		NTFS_PUTU16(record+0x18, hsize);
		/* total size of record */
		NTFS_PUTU32(record+0x20,s1-0x18);
		/* Writing the data will extend the attribute. */
		io.param=record;
		io.size=s1;
		io.do_read=0;
		error=ntfs_readwrite_attr(walk->dir, allocation, size, &io);
		if(error || io.size!=s1){
			ntfs_free(record);
			return error?error:EIO;
		}
		ntfs_free(record);
	}

	return 0;
}

/* Write an index block (root or allocation) back to storage.
   used is the total number of bytes in buf, including all headers. */

static int ntfs_index_writeback(ntfs_iterate_s *walk, ntfs_u8 *buf, int block,
				int used)
{
	ntfs_io io;
	int error;
	ntfs_attribute *a;
	ntfs_volume *vol = walk->dir->vol;
	
	io.fn_put=0;
	io.fn_get=ntfs_get;
	io.param=buf;
	if(block==-1){
		NTFS_PUTU16(buf+0x14,used-0x10);
		/* 0x18 is a copy thereof */
		NTFS_PUTU16(buf+0x18,used-0x10);
		io.size=used;
		error=ntfs_write_attr(walk->dir,vol->at_index_root,
				      I30,0,&io);
		if(error)return error;
		if(io.size!=used)return EIO;
		/* shrink if necessary */
		a = ntfs_find_attr(walk->dir, vol->at_index_root, I30);
		ntfs_resize_attr(walk->dir, a, used);
	}else{
		NTFS_PUTU16(buf+0x1C,used-0x18);
		ntfs_insert_fixups(buf,vol->blocksize);
		io.size=walk->dir->u.index.recordsize;
		error=ntfs_write_attr(walk->dir,vol->at_index_allocation,I30,
				      block*vol->clustersize,
				      &io);
		if(error)return error;
		if(io.size!=walk->dir->u.index.recordsize)
			return EIO;
	}
	return 0;
}

static int ntfs_split_record(ntfs_iterate_s *walk, char *start, int bsize,
	int usize)
{
	char *entry,*prev;
	ntfs_u8 *newbuf=0,*middle=0;
	int error,othersize,mlen;
	ntfs_io io;
	ntfs_volume *vol=walk->dir->vol;
	int oldblock;

	error=ntfs_allocate_index_block(walk);
	if(error)
		return error;
	/* This should not happen */
	if(walk->block == -1){
		ntfs_error("Trying to split root");
		return EOPNOTSUPP;
	}
	entry = start+NTFS_GETU16(start+0x18)+0x18; 
	for(prev=entry; entry-start<usize/2; entry += NTFS_GETU16(entry+8))
		prev=entry;

	newbuf=ntfs_malloc(vol->index_recordsize);
	if(!newbuf)
		return ENOMEM;
	io.fn_put=ntfs_put;
	io.fn_get=ntfs_get;
	io.param=newbuf;
	io.size=vol->index_recordsize;
	/* read in old header. FIXME: reading everything is overkill */
	error=ntfs_read_attr(walk->dir,vol->at_index_allocation,I30,
			     walk->newblock*vol->clustersize,&io);
	if(error)goto out;
	if(io.size!=vol->index_recordsize){
		error=EIO;
		goto out;
	}
	/* FIXME: adjust header */
	/* copy everything from entry to new block */
	othersize=usize-(entry-start);
	ntfs_memcpy(newbuf+NTFS_GETU16(newbuf+0x18)+0x18,entry,othersize);
	/* Copy flags. */
	NTFS_PUTU32(newbuf+0x24, NTFS_GETU32(start+0x24));
	error=ntfs_index_writeback(walk,newbuf,walk->newblock,
				   othersize+NTFS_GETU16(newbuf+0x18)+0x18);
	if(error)goto out;

	/* move prev to walk */
	mlen=NTFS_GETU16(prev+0x8);
	/* Remember old child node. */
	if(ntfs_entry_has_subnodes(prev))
		oldblock = NTFS_GETU32(prev+mlen-8);
	else
		oldblock = -1;
	/* allow for pointer to subnode */
	middle=ntfs_malloc(ntfs_entry_has_subnodes(prev)?mlen:mlen+8);
	if(!middle){
		error=ENOMEM;
		goto out;
	}
	ntfs_memcpy(middle,prev,mlen);
	/* set has_subnodes flag */
	NTFS_PUTU8(middle+0xC, NTFS_GETU8(middle+0xC) | 1);
	/* middle entry points to block, parent entry will point to newblock */
	NTFS_PUTU64(middle+mlen-8,walk->block);
	if(walk->new_entry)
		ntfs_error("entry not reset");
	walk->new_entry=middle;
	walk->u.flags|=ITERATE_SPLIT_DONE;
	/* Terminate old block. */
	othersize = usize-(prev-start);
	NTFS_PUTU64(prev, 0);
	if(oldblock==-1){
		NTFS_PUTU32(prev+8, 0x10);
		NTFS_PUTU32(prev+0xC, 2);
		othersize += 0x10;
	}else{
		NTFS_PUTU32(prev+8, 0x18);
		NTFS_PUTU32(prev+0xC, 3);
		NTFS_PUTU64(prev+0x10, oldblock);
		othersize += 0x18;
	}
	/* write back original block */
	error=ntfs_index_writeback(walk,start,walk->block,othersize);
 out:
	if(newbuf)ntfs_free(newbuf);
	if(middle)ntfs_free(middle);
	return error;
}

static int ntfs_dir_insert(ntfs_iterate_s *walk, char *start, char* entry)
{
	int blocksize,usedsize,error,offset;
	int do_split=0;
	offset=entry-start;
	if(walk->block==-1){ /*index root */
		blocksize=walk->dir->vol->mft_recordsize;
		usedsize=NTFS_GETU16(start+0x14)+0x10;
	}else{
		blocksize=walk->dir->u.index.recordsize;
		usedsize=NTFS_GETU16(start+0x1C)+0x18;
	}
	if(usedsize+walk->new_entry_size > blocksize){
		char* s1=ntfs_malloc(blocksize+walk->new_entry_size);
		if(!s1)return ENOMEM;
		ntfs_memcpy(s1,start,usedsize);
		do_split=1;
		/* adjust entry to s1 */
		entry=s1+(entry-start);
		start=s1;
	}
	ntfs_memmove(entry+walk->new_entry_size,entry,usedsize-offset);
	ntfs_memcpy(entry,walk->new_entry,walk->new_entry_size);
	usedsize+=walk->new_entry_size;
	ntfs_free(walk->new_entry);
	walk->new_entry=0;
	if(do_split){
		error=ntfs_split_record(walk,start,blocksize,usedsize);
		ntfs_free(start);
	}else{
		error=ntfs_index_writeback(walk,start,walk->block,usedsize);
		if(error)return error;
	}
	return 0;
}

/* Try to split INDEX_ROOT attributes. Return E2BIG if nothing changed. */

int
ntfs_split_indexroot(ntfs_inode *ino)
{
	ntfs_attribute *ra;
	ntfs_u8 *root=0, *index=0;
	ntfs_io io;
	int error, off, i, bsize, isize;
	ntfs_iterate_s walk;

	ra = ntfs_find_attr(ino, ino->vol->at_index_root, I30);
	if(!ra)
		return E2BIG;
	bsize = ino->vol->mft_recordsize;
	root = ntfs_malloc(bsize);
	if(!root)
		return E2BIG;
	io.fn_put = ntfs_put;
	io.param = root;
	io.size = bsize;
	error = ntfs_read_attr(ino, ino->vol->at_index_root, I30, 0, &io);
	if(error)
		goto out;
	off = 0x20;
	/* Count number of entries. */
	for(i = 0; ntfs_entry_is_used(root+off); i++)
		off += NTFS_GETU16(root+off+8);
	if(i<=2){
		/* We don't split small index roots. */
		error = E2BIG;
		goto out;
	}
	index = ntfs_malloc(ino->vol->index_recordsize);
	if(!index) {
		error = ENOMEM; goto out;
	}
	walk.dir = ino;
	walk.block = -1;
	walk.result = walk.new_entry = 0;
	walk.name = 0;
	error = ntfs_allocate_index_block(&walk);
	if(error)
		goto out;

	/* Write old root to new index block. */
	io.param = index;
	io.size = ino->vol->index_recordsize;
	error = ntfs_read_attr(ino, ino->vol->at_index_allocation, I30,
			       walk.newblock*ino->vol->clustersize, &io);
	if(error)
		goto out;
	isize = NTFS_GETU16(root+0x18) - 0x10;
	ntfs_memcpy(index+NTFS_GETU16(index+0x18)+0x18, root+0x20, isize);
	/* Copy flags. */
	NTFS_PUTU32(index+0x24, NTFS_GETU32(root+0x1C));

	error = ntfs_index_writeback(&walk, index, walk.newblock, 
				     isize+NTFS_GETU16(index+0x18)+0x18);
	if(error)
		goto out;

	/* Mark root as split. */
	NTFS_PUTU32(root+0x1C, 1);
	/* Truncate index root. */
	NTFS_PUTU64(root+0x20, 0);
	NTFS_PUTU32(root+0x28, 0x18);
	NTFS_PUTU32(root+0x2C, 3);
	NTFS_PUTU64(root+0x30, walk.newblock);
	error = ntfs_index_writeback(&walk,root,-1,0x38);
 out:
	ntfs_free(root);
	ntfs_free(index);
	return error;
}

/* The entry has been found. Copy the result in the caller's buffer */
static int ntfs_copyresult(char *dest,char *source)
{
	int length=NTFS_GETU16(source+8);
	ntfs_memcpy(dest,source,length);
	return 1;
}

/* use $UpCase some day */
static inline unsigned short ntfs_my_toupper(ntfs_volume *vol, ntfs_u16 x)
{
	/* we should read any pending rest of $UpCase here */
	if(x >= vol->upcase_length)
		return x;
	return vol->upcase[x];
}

/* everything passed in walk and entry */
static int ntfs_my_strcmp(ntfs_iterate_s *walk, const unsigned char *entry)
{
	int lu=*(entry+0x50);
	int i;

	ntfs_u16* name=(ntfs_u16*)(entry+0x52);
	ntfs_volume *vol=walk->dir->vol;
	for(i=0;i<lu && i<walk->namelen;i++)
		if(ntfs_my_toupper(vol,NTFS_GETU16(name+i))!=ntfs_my_toupper(vol,NTFS_GETU16(walk->name+i)))
			break;
	if(i==lu && i==walk->namelen)return 0;
	if(i==lu)return 1;
	if(i==walk->namelen)return -1;
	if(ntfs_my_toupper(vol,NTFS_GETU16(name+i))<ntfs_my_toupper(vol,NTFS_GETU16(walk->name+i)))return 1;
	return -1;
}

/* Necessary forward declaration */
static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry);

/* Parse a block of entries. Load the block, fix it up, and iterate
   over the entries. The block is given as virtual cluster number */
static int ntfs_getdir_record(ntfs_iterate_s *walk, int block)
{
	int length=walk->dir->u.index.recordsize;
	char *record=(char*)ntfs_malloc(length);
	char *offset;
	int retval,error;
	int oldblock;
	ntfs_io io;

	if( !record )
		return ENOMEM;

	io.fn_put=ntfs_put;
	io.param=record;
	io.size=length;
	/* Read the block from the index allocation attribute */