patch-2.1.74 linux/fs/ntfs/super.c

Next file: linux/fs/ntfs/super.h
Previous file: linux/fs/ntfs/struct.h
Back to the patch index
Back to the overall index

diff -u --recursive --new-file v2.1.73/linux/fs/ntfs/super.c linux/fs/ntfs/super.c
@@ -0,0 +1,547 @@
+/*
+ *  super.c
+ *
+ *  Copyright (C) 1995-1997 Martin von Löwis
+ *  Copyright (C) 1996-1997 Régis Duchesne
+ */
+
+#include "types.h"
+#include "struct.h"
+#include "super.h"
+
+#include <errno.h>
+#include "macros.h"
+#include "inode.h"
+#include "support.h"
+#include "util.h"
+
+/*
+ * All important structures in NTFS use 2 consistency checks :
+ * . a magic structure identifier (FILE, INDX, RSTR, RCRD...)
+ * . 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 */
+int ntfs_init_volume(ntfs_volume *vol,char *boot)
+{
+	/* Historical default values, in case we don't load $AttrDef */
+	vol->at_standard_information=0x10;
+	vol->at_attribute_list=0x20;
+	vol->at_file_name=0x30;
+	vol->at_security_descriptor=0x50;
+	vol->at_data=0x80;
+	vol->at_index_root=0x90;
+	vol->at_index_allocation=0xA0;
+	vol->at_bitmap=0xB0;
+	vol->at_symlink=0xC0;
+
+	/* Sector size */
+	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);
+
+	/* This will be initialized later */
+	vol->upcase=0;
+	vol->upcase_length=0;
+	vol->mft_ino=0;
+	return 0;
+}
+
+static 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;
+	io.size=2*UPCASE_LENGTH;
+	ntfs_read_attr(upcase,upcase->vol->at_data,0,0,&io);
+}
+
+static int
+process_attrdef(ntfs_inode* attrdef,ntfs_u8* def)
+{
+	int type = NTFS_GETU32(def+0x80);
+	int check_type = 0;
+	ntfs_volume *vol=attrdef->vol;
+	ntfs_u16* name = (ntfs_u16*)def;
+
+	if(ntfs_ua_strncmp(name,"$STANDARD_INFORMATION",64)==0){
+		vol->at_standard_information=type;
+		check_type=0x10;
+	}else if(ntfs_ua_strncmp(name,"$ATTRIBUTE_LIST",64)==0){
+		vol->at_attribute_list=type;
+		check_type=0x20;
+	}else if(ntfs_ua_strncmp(name,"$FILE_NAME",64)==0){
+		vol->at_file_name=type;
+		check_type=0x30;
+	}else if(ntfs_ua_strncmp(name,"$SECURITY_DESCRIPTOR",64)==0){
+		vol->at_file_name=type;
+	}else if(ntfs_ua_strncmp(name,"$DATA",64)==0){
+		vol->at_data=type;
+		check_type=0x80;
+	}else if(ntfs_ua_strncmp(name,"$INDEX_ROOT",64)==0){
+		vol->at_index_root=type;
+		check_type=0x90;
+	}else if(ntfs_ua_strncmp(name,"$INDEX_ALLOCATION",64)==0){
+		vol->at_index_allocation=type;
+		check_type=0xA0;
+	}else if(ntfs_ua_strncmp(name,"$BITMAP",64)==0){
+		vol->at_bitmap=type;
+		check_type=0xB0;
+	}else if(ntfs_ua_strncmp(name,"$SYMBOLIC_LINK",64) ||
+		 ntfs_ua_strncmp(name,"$REPARSE_POINT",64)){
+		vol->at_symlink=type;
+	}
+	if(check_type && check_type!=type){
+		ntfs_error("Unexpected type %x for %x\n",type,check_type);
+		return EINVAL;
+	}
+	return 0;
+}
+
+int
+ntfs_init_attrdef(ntfs_inode* attrdef)
+{
+	ntfs_u8 *buf;
+	ntfs_io io;
+	int offset,error,i;
+	ntfs_attribute *data;
+	buf=ntfs_malloc(4096);
+	if(!buf)return ENOMEM;
+	io.fn_put=ntfs_put;
+	io.fn_get=ntfs_get;
+	io.do_read=1;
+	offset=0;
+	data=ntfs_find_attr(attrdef,attrdef->vol->at_data,0);
+	if(!data){
+		ntfs_free(buf);
+		return EINVAL;
+	}
+	do{
+		io.param=buf;
+		io.size=4096;
+		error=ntfs_readwrite_attr(attrdef,data,offset,&io);
+		for(i=0;!error && i<io.size;i+=0xA0)
+			error=process_attrdef(attrdef,buf+i);
+		offset+=4096;
+	}while(!error && io.size);
+	ntfs_free(buf);
+	return error;
+}
+
+int ntfs_load_special_files(ntfs_volume *vol)
+{
+	int error;
+	ntfs_inode upcase,attrdef;
+
+	vol->mft_ino=(ntfs_inode*)ntfs_calloc(3*sizeof(ntfs_inode));
+	error=ENOMEM;
+	if(!vol->mft_ino || (error=ntfs_init_inode(vol->mft_ino,vol,FILE_MFT)))
+	{
+		ntfs_error("Problem loading MFT\n");
+		return error;
+	}
+	vol->mftmirr=vol->mft_ino+1;
+	if((error=ntfs_init_inode(vol->mftmirr,vol,FILE_MFTMIRR))){
+		ntfs_error("Problem %d loading MFTMirr\n",error);
+		return error;
+	}
+	vol->bitmap=vol->mft_ino+2;
+	if((error=ntfs_init_inode(vol->bitmap,vol,FILE_BITMAP))){
+		ntfs_error("Problem loading Bitmap\n");
+		return error;
+	}
+	error=ntfs_init_inode(&upcase,vol,FILE_UPCASE);
+	if(error)return error;
+	ntfs_init_upcase(&upcase);
+	ntfs_clear_inode(&upcase);
+	error=ntfs_init_inode(&attrdef,vol,FILE_ATTRDEF);
+	if(error)return error;
+	error=ntfs_init_attrdef(&attrdef);
+	ntfs_clear_inode(&attrdef);
+	if(error)return error;
+	return 0;
+}
+
+int ntfs_release_volume(ntfs_volume *vol)
+{
+	if(vol->mft_ino){
+		ntfs_clear_inode(vol->mft_ino);
+		ntfs_clear_inode(vol->mftmirr);
+		ntfs_clear_inode(vol->bitmap);
+		ntfs_free(vol->mft_ino);
+		vol->mft_ino=0;
+	}
+	ntfs_free(vol->mft);
+	ntfs_free(vol->upcase);
+	return 0;
+}
+
+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;
+	io.size=vol->clustersize;
+	ntfs_getput_clusters(vol,0,0,&io);
+	size=NTFS_GETU64(cluster0+0x28);
+	ntfs_free(cluster0);
+	size/=vol->clusterfactor;
+	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 offset,error;
+	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;
+		io.size=2048;
+		error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,
+				     offset,&io);
+		if(error || io.size==0)break;
+		/* I never thought I would do loop unrolling some day */
+		for(i=0;i<io.size-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<io.size;){
+			clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
+		}
+		offset+=io.size;
+	}
+	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(in && (!found || bstop-bstart<stop-start)){
+		bstop=stop;bstart=start;found=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,error;
+	unsigned char *bits,*it;
+	ntfs_io io;
+
+	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;
+	io.size=bsize;
+	if(!bits)
+		return ENOMEM;
+	error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,loc/8,&io);
+	if(error || io.size!=bsize){
+		ntfs_free(bits);
+		return error?error: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;
+	io.size=bsize;
+	error=ntfs_write_attr(bitmap,bitmap->vol->at_data,0,loc/8,&io);
+	ntfs_free(bits);
+	if(error)return error;
+	if(io.size!=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, int flags)
+{
+	unsigned char *bits;
+	ntfs_io io;
+	int error=0,found=0;
+	int loc,cnt,bloc=-1,bcnt=0;
+	int start;
+
+	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;
+	io.size=2048;
+	error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,start,&io);
+	if(error)goto fail;
+	loc=start*8;
+	cnt=*count;
+	error=search_bits(bits,&loc,&cnt,io.size);
+	if(error)
+		goto fail;
+	if(*count==cnt){
+		bloc=loc;
+		bcnt=cnt;
+		goto success;
+	}
+
+	/* now search from the beginning */
+	for(start=0;1;start+=2048)
+	{
+		io.param=bits;
+		io.size=2048;
+		error=ntfs_read_attr(bitmap,bitmap->vol->at_data,
+				     0,start,&io);
+		if(error)goto fail;
+		if(io.size==0)
+			if(found)
+				goto success;
+			else{
+				error=ENOSPC;
+				goto fail;
+			}
+		loc=start*8;
+		cnt=*count;
+		error=search_bits(bits,&loc,&cnt,io.size);
+		if(error)
+			goto fail;
+		if(*count==cnt)
+			goto success;
+		if(bcnt<cnt){
+			bcnt=cnt;
+			bloc=loc;
+			found=1;
+		}
+	}
+ success:
+	ntfs_free(bits);
+	/* check flags */
+	if((flags & ALLOC_REQUIRE_LOCATION) && *location!=bloc)
+		error=ENOSPC;
+	else if((flags & ALLOC_REQUIRE_SIZE) && *count!=bcnt)
+		error=ENOSPC;
+	else ntfs_set_bitrange(bitmap,bloc,bcnt,1);
+	/* If allocation failed due to the flags, tell the caller what he
+	   could have gotten */
+	*location=bloc;
+	*count=bcnt;
+	return 0;
+ fail:
+	*location=-1;
+	*count=0;
+	ntfs_free(bits);
+	return error;
+}
+
+int ntfs_allocate_clusters(ntfs_volume *vol, int *location, int *count,
+	int flags)
+{
+	int error;
+	error=ntfs_search_bits(vol->bitmap,location,count,flags);
+	return error;
+}
+
+int ntfs_deallocate_clusters(ntfs_volume *vol, int location, int count)
+{
+	int error;
+	error=ntfs_set_bitrange(vol->bitmap,location,count,0);
+	return error;
+}
+
+/*
+ * Local variables:
+ * c-file-style: "linux"
+ * End:
+ */
+
+

FUNET's LINUX-ADM group, linux-adm@nic.funet.fi
TCL-scripts by Sam Shen, slshen@lbl.gov