fs/ntfs/super.c

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