fs/ntfs/super.c

   1 /*
   2  *  super.c
   3  *
   4  *  Copyright (C) 1995-1997 Martin von Löwis
   5  *  Copyright (C) 1996-1997 Régis Duchesne
   6  */
   7
   8 #include "ntfstypes.h"
   9 #include "struct.h"
  10 #include "super.h"
  11
  12 #include <linux/errno.h>
  13 #include "macros.h"
  14 #include "inode.h"
  15 #include "support.h"
  16 #include "util.h"
  17
  18 /*
  19  * All important structures in NTFS use 2 consistency checks :
  20  * . a magic structure identifier (FILE, INDX, RSTR, RCRD...)
  21  * . a fixup technique : the last word of each sector (called a fixup) of a
  22  *   structure's record should end with the word at offset <n> of the first
  23  *   sector, and if it is the case, must be replaced with the words following
  24  *   <n>. The value of <n> and the number of fixups is taken from the fields
  25  *   at the offsets 4 and 6.
  26  *
  27  * This function perform these 2 checks, and _fails_ if :
  28  * . the magic identifier is wrong
  29  * . the size is given and does not match the number of sectors
  30  * . a fixup is invalid
  31  */
  32 int ntfs_fixup_record(ntfs_volume *vol, char *record, char *magic, int size)
  33 {
  34         int start, count, offset;
  35         ntfs_u16 fixup;
  36
  37         if(!IS_MAGIC(record,magic))
  38                 return 0;
  39         start=NTFS_GETU16(record+4);
  40         count=NTFS_GETU16(record+6);
  41         count--;
  42         if(size && vol->blocksize*count != size)
  43                 return 0;
  44         fixup = NTFS_GETU16(record+start);
  45         start+=2;
  46         offset=vol->blocksize-2;
  47         while(count--){
  48                 if(NTFS_GETU16(record+offset)!=fixup)
  49                         return 0;
  50                 NTFS_PUTU16(record+offset, NTFS_GETU16(record+start));
  51                 start+=2;
  52                 offset+=vol->blocksize;
  53         }
  54         return 1;
  55 }
  56
  57 /* Get vital informations about the ntfs partition from the boot sector */
  58 int ntfs_init_volume(ntfs_volume *vol,char *boot)
  59 {
  60         /* Historical default values, in case we don't load $AttrDef */
  61         vol->at_standard_information=0x10;
  62         vol->at_attribute_list=0x20;
  63         vol->at_file_name=0x30;
  64         vol->at_security_descriptor=0x50;
  65         vol->at_data=0x80;
  66         vol->at_index_root=0x90;
  67         vol->at_index_allocation=0xA0;
  68         vol->at_bitmap=0xB0;
  69         vol->at_symlink=0xC0;
  70
  71         /* Sector size */
  72         vol->blocksize=NTFS_GETU16(boot+0xB);
  73         vol->clusterfactor=NTFS_GETU8(boot+0xD);
  74         vol->mft_clusters_per_record=NTFS_GETS8(boot+0x40);
  75         vol->index_clusters_per_record=NTFS_GETS8(boot+0x44);
  76
  77         /* Just some consistency checks */
  78         if(NTFS_GETU32(boot+0x40)>256)
  79                 ntfs_error("Unexpected data #1 in boot block\n");
  80         if(NTFS_GETU32(boot+0x44)>256)
  81                 ntfs_error("Unexpected data #2 in boot block\n");
  82         if(vol->index_clusters_per_record<0){
  83                 ntfs_error("Unexpected data #3 in boot block\n");
  84                 /* If this really means a fraction, setting it to 1
  85                    should be safe. */
  86                 vol->index_clusters_per_record=1;
  87         }
  88         /* in some cases, 0xF6 meant 1024 bytes. Other strange values have not
  89            been observed */
  90         if(vol->mft_clusters_per_record<0 && vol->mft_clusters_per_record!=-10)
  91                 ntfs_error("Unexpected data #4 in boot block\n");
  92
  93         vol->clustersize=vol->blocksize*vol->clusterfactor;
  94         if(vol->mft_clusters_per_record>0)
  95                 vol->mft_recordsize=
  96                         vol->clustersize*vol->mft_clusters_per_record;
  97         else
  98                 vol->mft_recordsize=1<<(-vol->mft_clusters_per_record);
  99         vol->index_recordsize=vol->clustersize*vol->index_clusters_per_record;
 100         /* FIXME: long long value */
 101         vol->mft_cluster=NTFS_GETU64(boot+0x30);
 102
 103         /* This will be initialized later */
 104         vol->upcase=0;
 105         vol->upcase_length=0;
 106         vol->mft_ino=0;
 107         return 0;
 108 }
 109
 110 static void
 111 ntfs_init_upcase(ntfs_inode *upcase)
 112 {
 113         ntfs_io io;
 114 #define UPCASE_LENGTH  256
 115         upcase->vol->upcase = ntfs_malloc(2*UPCASE_LENGTH);
 116         upcase->vol->upcase_length = UPCASE_LENGTH;
 117         io.fn_put=ntfs_put;
 118         io.fn_get=0;
 119         io.param=(char*)upcase->vol->upcase;
 120         io.size=2*UPCASE_LENGTH;
 121         ntfs_read_attr(upcase,upcase->vol->at_data,0,0,&io);
 122 }
 123
 124 static int
 125 process_attrdef(ntfs_inode* attrdef,ntfs_u8* def)
 126 {
 127         int type = NTFS_GETU32(def+0x80);
 128         int check_type = 0;
 129         ntfs_volume *vol=attrdef->vol;
 130         ntfs_u16* name = (ntfs_u16*)def;
 131
 132         if(ntfs_ua_strncmp(name,"$STANDARD_INFORMATION",64)==0){
 133                 vol->at_standard_information=type;
 134                 check_type=0x10;
 135         }else if(ntfs_ua_strncmp(name,"$ATTRIBUTE_LIST",64)==0){
 136                 vol->at_attribute_list=type;
 137                 check_type=0x20;
 138         }else if(ntfs_ua_strncmp(name,"$FILE_NAME",64)==0){
 139                 vol->at_file_name=type;
 140                 check_type=0x30;
 141         }else if(ntfs_ua_strncmp(name,"$SECURITY_DESCRIPTOR",64)==0){
 142                 vol->at_file_name=type;
 143         }else if(ntfs_ua_strncmp(name,"$DATA",64)==0){
 144                 vol->at_data=type;
 145                 check_type=0x80;
 146         }else if(ntfs_ua_strncmp(name,"$INDEX_ROOT",64)==0){
 147                 vol->at_index_root=type;
 148                 check_type=0x90;
 149         }else if(ntfs_ua_strncmp(name,"$INDEX_ALLOCATION",64)==0){
 150                 vol->at_index_allocation=type;
 151                 check_type=0xA0;
 152         }else if(ntfs_ua_strncmp(name,"$BITMAP",64)==0){
 153                 vol->at_bitmap=type;
 154                 check_type=0xB0;
 155         }else if(ntfs_ua_strncmp(name,"$SYMBOLIC_LINK",64)==0 ||
 156                  ntfs_ua_strncmp(name,"$REPARSE_POINT",64)==0){
 157                 vol->at_symlink=type;
 158         }
 159         if(check_type && check_type!=type){
 160                 ntfs_error("Unexpected type %x for %x\n",type,check_type);
 161                 return EINVAL;
 162         }
 163         return 0;
 164 }
 165
 166 int
 167 ntfs_init_attrdef(ntfs_inode* attrdef)
 168 {
 169         ntfs_u8 *buf;
 170         ntfs_io io;
 171         int offset,error,i;
 172         ntfs_attribute *data;
 173         buf=ntfs_malloc(4050); /* 90*45 */
 174         if(!buf)return ENOMEM;
 175         io.fn_put=ntfs_put;
 176         io.fn_get=ntfs_get;
 177         io.do_read=1;
 178         offset=0;
 179         data=ntfs_find_attr(attrdef,attrdef->vol->at_data,0);
 180         if(!data){
 181                 ntfs_free(buf);
 182                 return EINVAL;
 183         }
 184         do{
 185                 io.param=buf;
 186                 io.size=4050;
 187                 error=ntfs_readwrite_attr(attrdef,data,offset,&io);
 188                 for(i=0;!error && i<io.size-0xA0;i+=0xA0)
 189                         error=process_attrdef(attrdef,buf+i);
 190                 offset+=4096;
 191         }while(!error && io.size);
 192         ntfs_free(buf);
 193         return error;
 194 }
 195
 196 int ntfs_load_special_files(ntfs_volume *vol)
 197 {
 198         int error;
 199         ntfs_inode upcase,attrdef;
 200
 201         vol->mft_ino=(ntfs_inode*)ntfs_calloc(3*sizeof(ntfs_inode));
 202         error=ENOMEM;
 203         ntfs_debug(DEBUG_BSD,"Going to load MFT\n");
 204         if(!vol->mft_ino || (error=ntfs_init_inode(vol->mft_ino,vol,FILE_MFT)))
 205         {
 206                 ntfs_error("Problem loading MFT\n");
 207                 return error;
 208         }
 209         ntfs_debug(DEBUG_BSD,"Going to load MIRR\n");
 210         vol->mftmirr=vol->mft_ino+1;
 211         if((error=ntfs_init_inode(vol->mftmirr,vol,FILE_MFTMIRR))){
 212                 ntfs_error("Problem %d loading MFTMirr\n",error);
 213                 return error;
 214         }
 215         ntfs_debug(DEBUG_BSD,"Going to load BITMAP\n");
 216         vol->bitmap=vol->mft_ino+2;
 217         if((error=ntfs_init_inode(vol->bitmap,vol,FILE_BITMAP))){
 218                 ntfs_error("Problem loading Bitmap\n");
 219                 return error;
 220         }
 221         ntfs_debug(DEBUG_BSD,"Going to load UPCASE\n");
 222         error=ntfs_init_inode(&upcase,vol,FILE_UPCASE);
 223         if(error)return error;
 224         ntfs_init_upcase(&upcase);
 225         ntfs_clear_inode(&upcase);
 226         ntfs_debug(DEBUG_BSD,"Going to load ATTRDEF\n");
 227         error=ntfs_init_inode(&attrdef,vol,FILE_ATTRDEF);
 228         if(error)return error;
 229         error=ntfs_init_attrdef(&attrdef);
 230         ntfs_clear_inode(&attrdef);
 231         if(error)return error;
 232         return 0;
 233 }
 234
 235 int ntfs_release_volume(ntfs_volume *vol)
 236 {
 237         if(vol->mft_ino){
 238                 ntfs_clear_inode(vol->mft_ino);
 239                 ntfs_clear_inode(vol->mftmirr);
 240                 ntfs_clear_inode(vol->bitmap);
 241                 ntfs_free(vol->mft_ino);
 242                 vol->mft_ino=0;
 243         }
 244         ntfs_free(vol->mft);
 245         ntfs_free(vol->upcase);
 246         return 0;
 247 }
 248
 249 int ntfs_get_volumesize(ntfs_volume *vol)
 250 {
 251         ntfs_io io;
 252         char *cluster0=ntfs_malloc(vol->clustersize);
 253         ntfs_u64 size;
 254
 255         io.fn_put=ntfs_put;
 256         io.fn_get=ntfs_get;
 257         io.param=cluster0;
 258         io.do_read=1;
 259         io.size=vol->clustersize;
 260         ntfs_getput_clusters(vol,0,0,&io);
 261         size=NTFS_GETU64(cluster0+0x28);
 262         ntfs_free(cluster0);
 263         /* FIXME: more than 2**32 cluster */
 264         /* FIXME: gcc will emit udivdi3 if we don't truncate it */
 265         return ((unsigned int)size)/vol->clusterfactor;
 266 }
 267
 268 static int nc[16]={4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};
 269
 270 int
 271 ntfs_get_free_cluster_count(ntfs_inode *bitmap)
 272 {
 273         unsigned char bits[2048];
 274         int offset,error;
 275         int clusters=0;
 276         ntfs_io io;
 277
 278         offset=0;
 279         io.fn_put=ntfs_put;
 280         io.fn_get=ntfs_get;
 281         while(1)
 282         {
 283                 register int i;
 284                 io.param=bits;
 285                 io.size=2048;
 286                 error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,
 287                                      offset,&io);
 288                 if(error || io.size==0)break;
 289                 /* I never thought I would do loop unrolling some day */
 290                 for(i=0;i<io.size-8;){
 291                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 292                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 293                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 294                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 295                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 296                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 297                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 298                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 299                 }
 300                 for(;i<io.size;){
 301                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 302                 }
 303                 offset+=io.size;
 304         }
 305         return clusters;
 306 }
 307
 308 /* Insert the fixups for the record. The number and location of the fixes
 309    is obtained from the record header */
 310 void ntfs_insert_fixups(unsigned char *rec, int secsize)
 311 {
 312         int first=NTFS_GETU16(rec+4);
 313         int count=NTFS_GETU16(rec+6);
 314         int offset=-2;
 315         ntfs_u16 fix=NTFS_GETU16(rec+first);
 316         fix=fix+1;
 317         NTFS_PUTU16(rec+first,fix);
 318         count--;
 319         while(count--){
 320                 first+=2;
 321                 offset+=secsize;
 322                 NTFS_PUTU16(rec+first,NTFS_GETU16(rec+offset));
 323                 NTFS_PUTU16(rec+offset,fix);
 324         };
 325 }
 326
 327 /* search the bitmap bits of l bytes for *cnt zero bits. Return the bit
 328    number in *loc, which is initially set to the number of the first bit.
 329    Return the largest block found in *cnt. Return 0 on success, ENOSPC if
 330    all bits are used */
 331 static int
 332 search_bits(unsigned char* bits,ntfs_cluster_t *loc,int *cnt,int l)
 333 {
 334         unsigned char c=0;
 335         int bc=0;
 336         int bstart=0,bstop=0,found=0;
 337         int start,stop=0,in=0;
 338         /* special case searching for a single block */
 339         if(*cnt==1){
 340                 while(l && *cnt==0xFF){
 341                         bits++;
 342                         *loc+=8;
 343                         l--;
 344                 }
 345                 if(!l)return ENOSPC;
 346                 for(c=*bits;c & 1;c>>=1)
 347                         (*loc)++;
 348                 return 0;
 349         }
 350         start=*loc;
 351         while(l || bc){
 352                 if(bc==0){
 353                         c=*bits;
 354                         if(l){
 355                                 l--;bits++;
 356                         }
 357                         bc=8;
 358                 }
 359                 if(in){
 360                         if((c&1)==0)
 361                                 stop++;
 362                         else{ /* end of sequence of zeroes */
 363                                 in=0;
 364                                 if(!found || bstop-bstart<stop-start){
 365                                         bstop=stop;bstart=start;found=1;
 366                                         if(bstop-bstart>*cnt)
 367                                                 break;
 368                                 }
 369                                 start=stop+1;
 370                         }
 371                 }else{
 372                         if(c&1)
 373                                 start++;
 374                         else{ /*start of sequence*/
 375                                 in=1;
 376                                 stop=start+1;
 377                         }
 378                 }
 379                 bc--;
 380                 c>>=1;
 381         }
 382         if(in && (!found || bstop-bstart<stop-start)){
 383                 bstop=stop;bstart=start;found=1;
 384         }
 385         if(!found)return ENOSPC;
 386         *loc=bstart;
 387         if(*cnt>bstop-bstart)
 388                 *cnt=bstop-bstart;
 389         return 0;
 390 }
 391
 392 int
 393 ntfs_set_bitrange(ntfs_inode* bitmap,ntfs_cluster_t loc,int cnt,int bit)
 394 {
 395         int bsize,locit,error;
 396         unsigned char *bits,*it;
 397         ntfs_io io;
 398
 399         io.fn_put=ntfs_put;
 400         io.fn_get=ntfs_get;
 401         bsize=(cnt+(loc & 7)+7) & ~7; /* round up to multiple of 8*/
 402         bits=ntfs_malloc(bsize);
 403         io.param=bits;
 404         io.size=bsize;
 405         if(!bits)
 406                 return ENOMEM;
 407         error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,loc>>3,&io);
 408         if(error || io.size!=bsize){
 409                 ntfs_free(bits);
 410                 return error?error:EIO;
 411         }
 412         /* now set the bits */
 413         it=bits;
 414         locit=loc;
 415         while(locit%8 && cnt){ /* process first byte */
 416                 if(bit)
 417                         *it |= 1<<(locit%8);
 418                 else
 419                         *it &= ~(1<<(locit%8));
 420                 cnt--;locit++;
 421                 if(locit%8==7)
 422                         it++;
 423         }
 424         while(cnt>8){ /*process full bytes */
 425                 *it= bit ? 0xFF : 0;
 426                 cnt-=8;
 427                 locit+=8;
 428                 it++;
 429         }
 430         while(cnt){ /*process last byte */
 431                 if(bit)
 432                         *it |= 1<<(locit%8);
 433                 else
 434                         *it &= ~(1<<(locit%8));
 435                 cnt--;locit++;
 436         }
 437         /* reset to start */
 438         io.param=bits;
 439         io.size=bsize;
 440         error=ntfs_write_attr(bitmap,bitmap->vol->at_data,0,loc>>3,&io);
 441         ntfs_free(bits);
 442         if(error)return error;
 443         if(io.size!=bsize)
 444                 return EIO;
 445         return 0;
 446 }
 447
 448
 449
 450 /* allocate count clusters around location. If location is -1,
 451    it does not matter where the clusters are. Result is 0 if
 452    success, in which case location and count says what they really got */
 453 int
 454 ntfs_search_bits(ntfs_inode* bitmap, ntfs_cluster_t *location, int *count, int flags)
 455 {
 456         unsigned char *bits;
 457         ntfs_io io;
 458         int error=0,found=0;
 459         int loc,cnt,bloc=-1,bcnt=0;
 460         int start;
 461
 462         bits=ntfs_malloc(2048);
 463         io.fn_put=ntfs_put;
 464         io.fn_get=ntfs_get;
 465         io.param=bits;
 466
 467         /* first search within +/- 8192 clusters */
 468         start=*location>>3;
 469         start= start>1024 ? start-1024 : 0;
 470         io.size=2048;
 471         error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,start,&io);
 472         if(error)goto fail;
 473         loc=start*8;
 474         cnt=*count;
 475         error=search_bits(bits,&loc,&cnt,io.size);
 476         if(error)
 477                 goto fail;
 478         if(*count==cnt){
 479                 bloc=loc;
 480                 bcnt=cnt;
 481                 goto success;
 482         }
 483
 484         /* now search from the beginning */
 485         for(start=0;1;start+=2048)
 486         {
 487                 io.param=bits;
 488                 io.size=2048;
 489                 error=ntfs_read_attr(bitmap,bitmap->vol->at_data,
 490                                      0,start,&io);
 491                 if(error)goto fail;
 492                 if(io.size==0){
 493                         if(found)
 494                                 goto success;
 495                         else{
 496                                 error=ENOSPC;
 497                                 goto fail;
 498                         }
 499                 }
 500                 loc=start*8;
 501                 cnt=*count;
 502                 error=search_bits(bits,&loc,&cnt,io.size);
 503                 if(error)
 504                         goto fail;
 505                 if(*count==cnt)
 506                         goto success;
 507                 if(bcnt<cnt){
 508                         bcnt=cnt;
 509                         bloc=loc;
 510                         found=1;
 511                 }
 512         }
 513  success:
 514         ntfs_free(bits);
 515         /* check flags */
 516         if((flags & ALLOC_REQUIRE_LOCATION) && *location!=bloc)
 517                 error=ENOSPC;
 518         else if((flags & ALLOC_REQUIRE_SIZE) && *count!=bcnt)
 519                 error=ENOSPC;
 520         else ntfs_set_bitrange(bitmap,bloc,bcnt,1);
 521         /* If allocation failed due to the flags, tell the caller what he
 522            could have gotten */
 523         *location=bloc;
 524         *count=bcnt;
 525         return 0;
 526  fail:
 527         *location=-1;
 528         *count=0;
 529         ntfs_free(bits);
 530         return error;
 531 }
 532
 533 int ntfs_allocate_clusters(ntfs_volume *vol, ntfs_cluster_t *location, int *count,
 534         int flags)
 535 {
 536         int error;
 537         error=ntfs_search_bits(vol->bitmap,location,count,flags);
 538         return error;
 539 }
 540
 541 int ntfs_deallocate_clusters(ntfs_volume *vol, ntfs_cluster_t location, int count)
 542 {
 543         int error;
 544         error=ntfs_set_bitrange(vol->bitmap,location,count,0);
 545         return error;
 546 }
 547
 548 /*
 549  * Local variables:
 550  * c-file-style: "linux"
 551  * End:
 552  */
 553
 554