dir.c

NTFS 磁盘系统 加载源代码

/*
 *  dir.c
 *
 *  Copyright (C) 1995 Martin von L鰓is
 */

#include <stdio.h>
#include <string.h>
#include <errno.h>
#include "ntfs.h"
#include "config.h"

static int ntfs_getdir_record(ntfs_iterate_s*,int);

/*	Tree walking is done using position numbers. The following numbers have
    a special meaning:
        0    start (.)
        -1   no more entries
        -2   ..
    All other numbers encode sequences of indices. The sequence a,b,c is 
    encoded as <stop><c><b><a>, where <foo> is the encoding of foo. The
    first few integers are encoded as follows:
        0:    0000    1:    0010    2:    0100    3:    0110
        4:    1000    5:    1010    6:    1100 stop:    1110
        7:  000001    8:  000101	9:  001001   10:  001101
	The least significant bits give the width of this encoding, the
	other bits encode the value, starting from the first value of the 
	interval.
		tag		width	first value		last value
		0		3		0				6
		01		4		7				22
		011		5		23				54
		0111	6		55				119
	More values are hopefully not needed, as the file position has currently
	64 bits in total.
*/

int	is_top(long long stack)
{
	return stack==14;
}

unsigned int top(void)
{
	return 14;
}

long long push(long long 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 -1;
}

long long pop(long long *stack)
{
	static 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=(*stack&15)>>1;
		*stack>>=4;
		break;
	case 2:res=((*stack&63)>>2)+7;
		*stack>>=6;
		break;
	case 3:res=((*stack & 255)>>3)+23;
		*stack>>=8;
		break;
	case 4:res=((*stack & 1023)>>4)+55;
		*stack>>=10;
		break;
	default:ntfs_error("Unknown encoding\n");
	}
	return res;
}

#if 0
void display_stack(long long stack)
{
	while(!is_top(stack))
	{
		printf("%d ",pop(&stack));
	}
	printf("\n");
}
#endif

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

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

/* use $UpCase some day */
static inline unsigned short 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 */
/* obsolete: expects ASCII string
static int 
my_strcmp(ntfs_iterate_s* walk,const unsigned char *entry)
{
	int lu=*(entry+0x50);
	int i;
	ntfs_volume *vol=walk->dir->vol;
	entry+=0x52;
	for(i=0;i<lu && i<walk->namelen;i++)
		if(my_toupper(vol,entry[2*i])!=my_toupper(vol,walk->name[i]) 
		   || entry[2*i+1]!='\0')
			break;
	if(i==lu && i==walk->namelen)return 0;
	if(i==lu)return -1;
	if(i==walk->namelen)return 1;
	if(entry[2*i+1])return 1;
	if(my_toupper(vol,entry[2*i])<my_toupper(vol,walk->name[i]))return -1;
	return 1;
}
*/
static int 
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(my_toupper(vol,name[i])!=my_toupper(vol,walk->name[i]))
			break;
	if(i==lu && i==walk->namelen)return 0;
	if(i==lu)return -1;
	if(i==walk->namelen)return 1;
	if(my_toupper(vol,name[i])<my_toupper(vol,walk->name[i]))return -1;
	return 1;
}


/* 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);
}

/* go down to the next block of entries. These collate before
   the current entry */
static int 
descend(ntfs_iterate_s* walk,char *entry)
{
	int length=NTFS_GETU16(entry+8);
	int nextblock=NTFS_GETU32(entry+length-8);
	if(!entry_has_subnodes(entry)) {
		ntfs_error("illegal descend call\n");
		return 0;
	}
	return ntfs_getdir_record(walk,nextblock);
}

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

/* type == BY_POSITION: pos points to index, which is decremented to zero
   type == BY_NAME:     look for name, pos points to strlen(name) */

/* 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;
	ntfs_io io;

	io.fn_put=ntfs_put;
	io.param=record;
	/* Read the block from the index allocation attribute */
	if(ntfs_read_attr(walk->dir,AT_INDEX_ALLOCATION,"$I30",
			  block*walk->dir->vol->clustersize,
			  &io,length)!=length){
		ntfs_error("read failed\n");
		ntfs_free(record);
		return 0;
	}
	if(!ntfs_check_index_record(walk->dir,record)){
		ntfs_error("%x is not an index record\n",block);
		ntfs_free(record);
		return 0;
	}
	offset=record+NTFS_GETU16(record+0x18)+0x18;
	retval=ntfs_getdir_iterate(walk,offset);
	ntfs_free(record);
	return retval;
}

static int 
ntfs_getdir_iterate_byposition(ntfs_iterate_s *walk,char *entry)
{
	int retval=0;
	int curpos=0,destpos=0;
	int length;
	if(walk->pos!=0){
		if(is_top(walk->pos))return 0;
		destpos=pop(&walk->pos);
	}
	while(1){
		if(walk->pos==0)
		{
			if(entry_has_subnodes(entry))
				descend(walk,entry);
			else
				walk->pos=top();
			if(is_top(walk->pos) && !entry_is_used(entry))
			{
				return 1;
			}
			walk->pos=push(walk->pos,curpos);
			return 1;
		}
		if(curpos==destpos)
		{
			if(!is_top(walk->pos) && entry_has_subnodes(entry))
			{
				retval=descend(walk,entry);
				if(retval){
					walk->pos=push(walk->pos,curpos);
					return retval;
				}else{
					if(!entry_is_used(entry))
						return 0;
					walk->pos=0;
				}
			}
			if(entry_is_used(entry))
			{
				retval=copyresult(walk->result,entry);
				walk->pos=0;
			}else{
				walk->pos=top();
				return 0;
			}
		}
		curpos++;
		if(!entry_is_used(entry))break;
		length=NTFS_GETU16(entry+8);
		if(!length){
			ntfs_error("infinite loop\n");
			break;
		}
		entry+=length;
	}
	return -1;
}

	
/* Iterate over a list of entries, either from an index block, or from
   the index root. 
   If searching BY_POSITION, pop the top index from the position. If the
   position stack is empty then, return the item at the index and set the
   position to the next entry. If the position stack is not empty, 
   recursively proceed for subnodes. If the entry at the position is the
   'end of dir' entry, return 'not found' and the empty stack.
   If searching BY_NAME, walk through the items until found or until
   one item is collated after the requested item. In the former case, return
   the result. In the latter case, recursively proceed to the subnodes.
   If 'end of dir' is reached, the name is not in the directory */
int ntfs_getdir_iterate(ntfs_iterate_s* walk,char* entry)
{
	int length;
	int retval=0;
	if(walk->type==BY_POSITION)
		return ntfs_getdir_iterate_byposition(walk,entry);
	do{
		switch(walk->type){
		case BY_NAME:
			if(entry_is_used(entry))
				switch(my_strcmp(walk,entry))
				{
				case -1:break;
				case  0:return copyresult(walk->result,entry);
				case  1:return entry_has_subnodes(entry)?
					       descend(walk,entry):0;
				}else
					return entry_has_subnodes(entry)?
						descend(walk,entry):0;
			break;
		default:
			ntfs_error("TODO\n");
		}
		if(!entry_is_used(entry))break;
		length=NTFS_GETU16(entry+8);
		if(!length){
			ntfs_error("infinite loop\n");
			break;
		}
		entry+=length;
	}while(1);
	return retval;
}

/* Find an entry in the directory. Return 0 if not found, otherwise copy
   the entry to the result buffer. */
int ntfs_getdir(ntfs_iterate_s* walk)
{
	int length=walk->dir->vol->mft_recordsize;
	int retval;
	/* start at the index root.*/
	char *root=ntfs_malloc(length);
	ntfs_io io;

	io.fn_put=ntfs_put;
	io.param=root;
	if(ntfs_read_attr(walk->dir,AT_INDEX_ROOT,"$I30",
			  0,&io,length)<=0)
	{
		ntfs_error("Not a directory\n");
		return 0;
	}
	/* FIXME: move these to walk */
	walk->dir->u.index.recordsize = NTFS_GETU32(root+0x8);
	walk->dir->u.index.clusters_per_record = NTFS_GETU32(root+0xC);
	/* FIXME: consistency check */
	/* skip header */
	retval = ntfs_getdir_iterate(walk,root+0x20);
	ntfs_free(root);
	return retval;
}

/* Find an entry in the directory by its position stack. Iteration starts
   if the stack is 0, in which case the position is set to the first item
   in the directory. If the position is nonzero, return the item at the
   position and change the position to the next item. The position is -1
   if there are no more items */
int 
ntfs_getdir_byposition(ntfs_iterate_s *walk)
{
	walk->type=BY_POSITION;
	return ntfs_getdir(walk);
}

/* Find an entry in the directory by its name. Return 0 if not found */
int 
ntfs_getdir_byname(ntfs_iterate_s *walk)
{
	walk->type=BY_NAME;
	return ntfs_getdir(walk);
}
int ntfs_getdir_unsorted(ntfs_inode *ino,ntfs_u32 *p_high,ntfs_u32* p_low,
			 int(*cb)(ntfs_u8*,void*),void *param)
{
	char *buf=0,*entry=0;
	ntfs_io io;
	int length;
	int block;
	int start;
	ntfs_attribute *attr;
	int byte,bit;
	int error=0;

	/* are we still in the index root */
	if(*p_high==0){
		buf=ntfs_malloc(length=ino->vol->mft_recordsize);
		io.fn_put=ntfs_put;
		io.param=buf;
		if(ntfs_read_attr(ino,AT_INDEX_ROOT,"$I30",0,&io,length)<=0){
			ntfs_free(buf);
			return ENOTDIR;
		}
		ino->u.index.recordsize = NTFS_GETU32(buf+0x8);
		ino->u.index.clusters_per_record = NTFS_GETU32(buf+0xC);
		entry=buf+0x20;
	}else{ /* we are in an index record */
		length=ino->u.index.recordsize;
		buf=ntfs_malloc(length);
		io.fn_put=ntfs_put;
		io.param=buf;
		/* 0 is index root, index allocation starts with 4 */
		block = *p_high - ino->u.index.clusters_per_record;
		if(ntfs_read_attr(ino,AT_INDEX_ALLOCATION,"$I30",
				  block*ino->vol->clustersize,&io,length)!=length){
			ntfs_error("read failed\n");
			ntfs_free(buf);
			return EIO;
		}
		if(!ntfs_check_index_record(ino,buf)){
			ntfs_error("%x is not an index record\n",block);
			ntfs_free(buf);
			return ENOTDIR;
		}
		entry=buf+NTFS_GETU16(buf+0x18)+0x18;
	}

	/* process the entries */
	start=*p_low;
	while(entry_is_used(entry)){
		if(start)
			start--; /* skip entries that were already processed */
		else{
			if((error=cb(entry,param)))
				/* the entry could not be processed */
				break;
			(*p_low)++;
		}
		entry+=NTFS_GETU16(entry+8);
	}

	/* caller did not process all entries */
	if(error){
		ntfs_free(buf);
		return error;
	}

	/* we have to locate the next record */
	ntfs_free(buf);
	buf=0;
	*p_low=0;
	attr=ntfs_find_attr(ino,AT_BITMAP,"$I30");
	if(!attr){
		/* directory does not have index allocation */
		*p_high=0xFFFFFFFF;
		*p_low=0;
		return 0;
	}
	buf=ntfs_malloc(length=DATASIZE(&attr->header));
	io.param=buf;
	if(ntfs_read_attr(ino,AT_BITMAP,"$I30",0,&io,length)!=length){
		ntfs_free(buf);
		return EIO;
	}
	attr=ntfs_find_attr(ino,AT_INDEX_ALLOCATION,"$I30");
	while(1){
		if(*p_high*ino->vol->clustersize > DATASIZE(attr->header)){
			/* no more index records */
			*p_high=0xFFFFFFFF;
			ntfs_free(buf);
			return 0;
		}
		*p_high+=ino->u.index.clusters_per_record;
		byte=*p_high/ino->u.index.clusters_per_record-1;
		bit  = 1 << (byte & 7);
		byte = byte >> 3;
		/* this record is allocated */
		if(buf[byte] & bit)
			break;
	}
	return 0;
}

/*int ntfs_dir_add(ntfs_inode *dir,const char* name,int namelen,ntfs_inode *ino)
{
	ntfs_attribute *attr;
*/
/*
 * Local variables:
 * c-file-style: "linux"
 * End:
 */