super.c

NTFS 磁盘系统 加载源代码

/*
 *  super.c
 *
 *  Copyright (C) 1995 Martin von L鰓is
 *  Copyright (C) 1996 Regis Duchesne
 */

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

/*
 * All important structures in NTFS use 2 consistency checks :
 * . a magic structure identifier (FILE, INDX, RSTR, ...)
 * . a fixup technique : the last word of each sector (called a fixup) of a
 *   structure's record should end with the word at offset <n> of the first
 *   sector, and if it is the case, must be replaced with the words following
 *   <n>. The value of <n> and the number of fixups is taken from the fields
 *   at the offsets 4 and 6.
 *
 * This function perform these 2 checks, and _fails_ if :
 * . the magic identifier is wrong
 * . the size is given and does not match the number of sectors
 * . a fixup is invalid
 */
int ntfs_fixup_record(ntfs_volume* vol,char *record, char *magic, int size)
{
	int start, count, offset;
	short fixup;

	if(!IS_MAGIC(record,magic))
		return 0;
	start=NTFS_GETU16(record+4);
	count=NTFS_GETU16(record+6);
	count--;
	if(size && vol->blocksize*count != size)
		return 0;
	fixup = NTFS_GETU16(record+start);
	start+=2;
	offset=vol->blocksize-2;
	while(count--){
		if(NTFS_GETU16(record+offset)!=fixup)
			return 0;
		NTFS_PUTU16(record+offset, NTFS_GETU16(record+start));
		start+=2;
		offset+=vol->blocksize;
	}
	return 1;
}

/* Get vital informations about the ntfs partition from the boot sector */
void ntfs_init_volume(ntfs_volume *vol,char *boot)
{
	vol->blocksize=NTFS_GETU16(boot+0xB);
	vol->clusterfactor=NTFS_GETU8(boot+0xD);
	vol->mft_clusters_per_record=NTFS_GETS8(boot+0x40);
	vol->index_clusters_per_record=NTFS_GETS8(boot+0x44);
	
	/* Just some consistency checks */
	if(NTFS_GETU32(boot+0x40)>256)
		ntfs_error("Unexpected data #1 in boot block\n");
	if(NTFS_GETU32(boot+0x44)>256)
		ntfs_error("Unexpected data #2 in boot block\n");
	if(vol->index_clusters_per_record<0){
		ntfs_error("Unexpected data #3 in boot block\n");
		/* If this really means a fraction, setting it to 1
		   should be safe. */
		vol->index_clusters_per_record=1;
	}
	/* in some cases, 0xF6 meant 1024 bytes. Other strange values have not
	   been observed */
	if(vol->mft_clusters_per_record<0 && vol->mft_clusters_per_record!=-10)
		ntfs_error("Unexpected data #4 in boot block\n");

	vol->clustersize=vol->blocksize*vol->clusterfactor;
	if(vol->mft_clusters_per_record>0)
		vol->mft_recordsize=
			vol->clustersize*vol->mft_clusters_per_record;
	else
		vol->mft_recordsize=1<<(-vol->mft_clusters_per_record);
	vol->index_recordsize=vol->clustersize*vol->index_clusters_per_record;
	/* FIXME: long long value */
	vol->mft_cluster=NTFS_GETU64(boot+0x30);
	vol->upcase=0;
	vol->upcase_length=0;
	/* this will be initialized later */
	vol->mft_ino=0;

}

int ntfs_load_special_files(ntfs_volume *vol)
{
	ntfs_inode upcase;
	vol->mft_ino=(ntfs_inode*)ntfs_malloc(sizeof(ntfs_inode));
	if(!vol->mft_ino || ntfs_init_inode(vol->mft_ino,vol,FILE_MFT)==-1)
	{
		ntfs_error("Problem loading MFT\n");
		return -1;
	}
	ntfs_init_inode(&upcase,vol,FILE_UPCASE);
	ntfs_init_upcase(&upcase);
	ntfs_clear_inode(&upcase);
	return 0;
}

void ntfs_init_upcase(ntfs_inode *upcase)
{
	ntfs_io io;
#define UPCASE_LENGTH  256
	upcase->vol->upcase = ntfs_malloc(2*UPCASE_LENGTH);
	upcase->vol->upcase_length = UPCASE_LENGTH;
	io.fn_put=ntfs_put;
	io.fn_get=0;
	io.param=upcase->vol->upcase;
	ntfs_read_attr(upcase,AT_DATA,NULL,0,&io,2*UPCASE_LENGTH);
}

int ntfs_get_volumesize(ntfs_volume *vol)
{
	ntfs_io io;
	char *cluster0=ntfs_malloc(vol->clustersize);
	int size;

	io.fn_put=ntfs_put;
	io.fn_get=ntfs_get;
	io.param=cluster0;
	io.do_read=1;
	ntfs_getput_clusters(vol,0,0,vol->clustersize,&io);
	size=NTFS_GETU64(cluster0+0x28);
	ntfs_free(cluster0);
	return size;
}

static int nc[16]={4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};

int ntfs_get_free_cluster_count(ntfs_inode *bitmap)
{
	unsigned char bits[2048];
	int l,offset;
	int clusters=0;
	ntfs_io io;

	offset=0;
	io.fn_put=ntfs_put;
	io.fn_get=ntfs_get;
	while(1)
	{
		register int i;
		io.param=bits;
		l=ntfs_read_attr(bitmap,AT_DATA,NULL,offset,&io,2048);
		if(l==0)break;
		if(l<0 || l>2048)return 0; /* something wrong here */
		/* I never thought I would do loop unrolling some day */
		for(i=0;i<l-8;){
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
		}
		for(;i<l;){
			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
		}
		offset+=l;
	}
	return clusters;
}

/* Insert the fixups for the record. The number and location of the fixes 
   is obtained from the record header */
void ntfs_insert_fixups(unsigned char *rec,int secsize)
{
	int first=NTFS_GETU16(rec+4);
	int count=NTFS_GETU16(rec+6);
	int offset=-2;
	ntfs_u16 fix=NTFS_GETU16(rec+first);
	fix=fix+1;
	NTFS_PUTU16(rec+first,fix);
	count--;
	while(count--){
		first+=2;
		offset+=secsize;
		NTFS_PUTU16(rec+first,NTFS_GETU16(rec+offset));
		NTFS_PUTU16(rec+offset,fix);
	};
}

/* search the bitmap bits of l bytes for *cnt zero bits. Return the bit
   number in *loc, which is initially set to the number of the first bit.
   Return the largest block found in *cnt. Return 0 on success, ENOSPC if
   all bits are used */
static int search_bits(unsigned char* bits,int *loc,int *cnt,int l)
{
	unsigned char c=0;
	int bc=0;
	int bstart=0,bstop=0,found=0;
	int start,stop=0,in=0;
	/* special case searching for a single block */
	if(*cnt==1){
		while(l && *cnt==0xFF){
			bits++;
			*loc+=8;
			l--;
		}
		if(!l)return ENOSPC;
		for(c=*bits;c & 1;c>>=1)
			(*loc)++;
		return 0;
	}
	start=*loc;
	while(l || bc){
		if(bc==0){
			c=*bits;
			if(l){
				l--;bits++;
			}
			bc=8;
		}
		if(in){
			if((c&1)==0)
				stop++;
			else{ /* end of sequence of zeroes */
				in=0;
				if(!found || bstop-bstart<stop-start){
					bstop=stop;bstart=start;found=1;
					if(bstop-bstart>*cnt)
						break;
				}
				start=stop+1;
			}
		}else{
			if(c&1)
				start++;
			else{ /*start of sequence*/
				in=1;
				stop=start+1;
			}
		}
		bc--;
		c>>=1;
	}
	if(!found)return ENOSPC;
	*loc=bstart;
	if(*cnt>bstop-bstart)
		*cnt=bstop-bstart;
	return 0;
}

int ntfs_set_bitrange(ntfs_inode* bitmap,int loc,int cnt,int bit)
{
	int bsize,locit;
	unsigned char *bits,*it;
	ntfs_io io;
	int l;

	io.fn_put=ntfs_put;
	io.fn_get=ntfs_get;
	bsize=(cnt+loc%8+7)/8; /* round up */
	bits=ntfs_malloc(bsize);
	io.param=bits;
	if(!bits)
		return ENOMEM;
	l=ntfs_read_attr(bitmap,AT_DATA,NULL,loc/8,&io,bsize);
	if(l!=bsize){
		ntfs_free(bits);
		return EIO;
	}
	/* now set the bits */
	it=bits;
	locit=loc;
	while(locit%8 && cnt){ /* process first byte */
		if(bit)
			*it |= 1<<(locit%8);
		else
			*it &= ~(1<<(locit%8));
		cnt--;locit++;
		if(locit%8==7)
			it++;
	}
	while(cnt>8){ /*process full bytes */
		*it= bit ? 0xFF : 0;
		cnt-=8;
		locit+=8;
		it++;
	}
	while(cnt){ /*process last byte */
		if(bit)
			*it |= 1<<(locit%8);
		else
			*it &= ~(1<<(locit%8));
		cnt--;locit++;
	}
	/* reset to start */
	io.param=bits;
	l=ntfs_write_attr(bitmap,AT_DATA,NULL,loc/8,&io,bsize);
	ntfs_free(bits);
	if(l!=bsize)
		return EIO;
	return 0;
}
  
  
	
/* allocate count clusters around location. If location is -1,
   it does not matter where the clusters are. Result is 0 if
   success, in which case location and count says what they really got */
int ntfs_search_bits(ntfs_inode* bitmap, int *location, int *count)
{
	unsigned char *bits;
	ntfs_io io;
	int error,found=0;
	int loc,cnt,bloc=-1,bcnt=0;
	int start,l;

	bits=ntfs_malloc(2048);
	io.fn_put=ntfs_put;
	io.fn_get=ntfs_get;
	io.param=bits;

	/* first search within +/- 8192 clusters */
	start=*location/8;
	start= start>1024 ? start-1024 : 0;
	l=ntfs_read_attr(bitmap,AT_DATA,NULL,start,&io,2048);
	if(l<0 || l>2048){
		error=EIO;
		goto fail;
	}
	loc=start*8;
	cnt=*count;
	error=search_bits(bits,&loc,&cnt,l);
	if(error)
		goto fail;
	if(*count==cnt){
		bloc=loc;
		bcnt=cnt;
		goto success;
	}

	/* now search from the beginning */
	for(start=0;1;start+=2048)
	{
		l=ntfs_read_attr(bitmap,AT_DATA,NULL,start,&io,2048);
		if(l<0 || l>2048){
			error=EIO;
			goto fail;
		}
		
		if(l==0)
			if(found)
				goto success;
			else{
				error=ENOSPC;
				goto fail;
			}
		loc=start*8;
		cnt=*count;
		error=search_bits(bits,&loc,&cnt,l);
		if(error)
			goto fail;
		if(*count==cnt)
			goto success;
		if(bcnt<cnt){
			bcnt=cnt;
			bloc=loc;
			found=1;
		}
	}
 success:
	ntfs_free(bits);
	ntfs_set_bitrange(bitmap,bloc,bcnt,1);
	*location=bloc;
	*count=bcnt;
	return 0;
 fail:
	ntfs_free(bits);
	return error;
}

int ntfs_allocate_clusters(ntfs_volume *vol,int *location,int *count)
{
	ntfs_inode bitmap;
	int error;
	ntfs_init_inode(&bitmap,vol,FILE_BITMAP);
	error=ntfs_search_bits(&bitmap,location,count);
	ntfs_clear_inode(&bitmap);
	return error;
}

int ntfs_deallocate_clusters(ntfs_volume *vol,int location,int count)
{
	ntfs_inode bitmap;
	int error;
	ntfs_init_inode(&bitmap,vol,FILE_BITMAP);
	error=ntfs_set_bitrange(&bitmap,location,count,0);
	ntfs_clear_inode(&bitmap);
	return error;
}

/* Helper functions */
void ntfs_put(ntfs_io *dest,void *src,ntfs_size_t n)
{
	ntfs_memcpy(dest->param,src,n);
	dest->param+=n;
}

void ntfs_get(void* dest,ntfs_io *src,ntfs_size_t n)
{
	ntfs_memcpy(dest,src->param,n);
	src->param+=n;
}

/*
 * Local variables:
 * c-file-style: "linux"
 * End:
 */