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 "types.h"
   9 #include "struct.h"
  10 #include "super.h"
  11
  12 #include <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         short 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=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) ||
 156                  ntfs_ua_strncmp(name,"$REPARSE_POINT",64)){
 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(4096);
 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=4096;
 187                 error=ntfs_readwrite_attr(attrdef,data,offset,&io);
 188                 for(i=0;!error && i<io.size;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         if(!vol->mft_ino || (error=ntfs_init_inode(vol->mft_ino,vol,FILE_MFT)))
 204         {
 205                 ntfs_error("Problem loading MFT\n");
 206                 return error;
 207         }
 208         vol->mftmirr=vol->mft_ino+1;
 209         if((error=ntfs_init_inode(vol->mftmirr,vol,FILE_MFTMIRR))){
 210                 ntfs_error("Problem %d loading MFTMirr\n",error);
 211                 return error;
 212         }
 213         vol->bitmap=vol->mft_ino+2;
 214         if((error=ntfs_init_inode(vol->bitmap,vol,FILE_BITMAP))){
 215                 ntfs_error("Problem loading Bitmap\n");
 216                 return error;
 217         }
 218         error=ntfs_init_inode(&upcase,vol,FILE_UPCASE);
 219         if(error)return error;
 220         ntfs_init_upcase(&upcase);
 221         ntfs_clear_inode(&upcase);
 222         error=ntfs_init_inode(&attrdef,vol,FILE_ATTRDEF);
 223         if(error)return error;
 224         error=ntfs_init_attrdef(&attrdef);
 225         ntfs_clear_inode(&attrdef);
 226         if(error)return error;
 227         return 0;
 228 }
 229
 230 int ntfs_release_volume(ntfs_volume *vol)
 231 {
 232         if(vol->mft_ino){
 233                 ntfs_clear_inode(vol->mft_ino);
 234                 ntfs_clear_inode(vol->mftmirr);
 235                 ntfs_clear_inode(vol->bitmap);
 236                 ntfs_free(vol->mft_ino);
 237                 vol->mft_ino=0;
 238         }
 239         ntfs_free(vol->mft);
 240         ntfs_free(vol->upcase);
 241         return 0;
 242 }
 243
 244 int ntfs_get_volumesize(ntfs_volume *vol)
 245 {
 246         ntfs_io io;
 247         char *cluster0=ntfs_malloc(vol->clustersize);
 248         int size;
 249
 250         io.fn_put=ntfs_put;
 251         io.fn_get=ntfs_get;
 252         io.param=cluster0;
 253         io.do_read=1;
 254         io.size=vol->clustersize;
 255         ntfs_getput_clusters(vol,0,0,&io);
 256         size=NTFS_GETU64(cluster0+0x28);
 257         ntfs_free(cluster0);
 258         size/=vol->clusterfactor;
 259         return size;
 260 }
 261
 262 static int nc[16]={4,3,3,2,3,2,2,1,3,2,2,1,2,1,1,0};
 263
 264 int
 265 ntfs_get_free_cluster_count(ntfs_inode *bitmap)
 266 {
 267         unsigned char bits[2048];
 268         int offset,error;
 269         int clusters=0;
 270         ntfs_io io;
 271
 272         offset=0;
 273         io.fn_put=ntfs_put;
 274         io.fn_get=ntfs_get;
 275         while(1)
 276         {
 277                 register int i;
 278                 io.param=bits;
 279                 io.size=2048;
 280                 error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,
 281                                      offset,&io);
 282                 if(error || io.size==0)break;
 283                 /* I never thought I would do loop unrolling some day */
 284                 for(i=0;i<io.size-8;){
 285                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 286                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 287                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 288                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 289                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 290                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 291                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 292                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 293                 }
 294                 for(;i<io.size;){
 295                         clusters+=nc[bits[i]>>4];clusters+=nc[bits[i++] & 0xF];
 296                 }
 297                 offset+=io.size;
 298         }
 299         return clusters;
 300 }
 301
 302 /* Insert the fixups for the record. The number and location of the fixes
 303    is obtained from the record header */
 304 void ntfs_insert_fixups(unsigned char *rec, int secsize)
 305 {
 306         int first=NTFS_GETU16(rec+4);
 307         int count=NTFS_GETU16(rec+6);
 308         int offset=-2;
 309         ntfs_u16 fix=NTFS_GETU16(rec+first);
 310         fix=fix+1;
 311         NTFS_PUTU16(rec+first,fix);
 312         count--;
 313         while(count--){
 314                 first+=2;
 315                 offset+=secsize;
 316                 NTFS_PUTU16(rec+first,NTFS_GETU16(rec+offset));
 317                 NTFS_PUTU16(rec+offset,fix);
 318         };
 319 }
 320
 321 /* search the bitmap bits of l bytes for *cnt zero bits. Return the bit
 322    number in *loc, which is initially set to the number of the first bit.
 323    Return the largest block found in *cnt. Return 0 on success, ENOSPC if
 324    all bits are used */
 325 static int
 326 search_bits(unsigned char* bits,int *loc,int *cnt,int l)
 327 {
 328         unsigned char c=0;
 329         int bc=0;
 330         int bstart=0,bstop=0,found=0;
 331         int start,stop=0,in=0;
 332         /* special case searching for a single block */
 333         if(*cnt==1){
 334                 while(l && *cnt==0xFF){
 335                         bits++;
 336                         *loc+=8;
 337                         l--;
 338                 }
 339                 if(!l)return ENOSPC;
 340                 for(c=*bits;c & 1;c>>=1)
 341                         (*loc)++;
 342                 return 0;
 343         }
 344         start=*loc;
 345         while(l || bc){
 346                 if(bc==0){
 347                         c=*bits;
 348                         if(l){
 349                                 l--;bits++;
 350                         }
 351                         bc=8;
 352                 }
 353                 if(in){
 354                         if((c&1)==0)
 355                                 stop++;
 356                         else{ /* end of sequence of zeroes */
 357                                 in=0;
 358                                 if(!found || bstop-bstart<stop-start){
 359                                         bstop=stop;bstart=start;found=1;
 360                                         if(bstop-bstart>*cnt)
 361                                                 break;
 362                                 }
 363                                 start=stop+1;
 364                         }
 365                 }else{
 366                         if(c&1)
 367                                 start++;
 368                         else{ /*start of sequence*/
 369                                 in=1;
 370                                 stop=start+1;
 371                         }
 372                 }
 373                 bc--;
 374                 c>>=1;
 375         }
 376         if(in && (!found || bstop-bstart<stop-start)){
 377                 bstop=stop;bstart=start;found=1;
 378         }
 379         if(!found)return ENOSPC;
 380         *loc=bstart;
 381         if(*cnt>bstop-bstart)
 382                 *cnt=bstop-bstart;
 383         return 0;
 384 }
 385
 386 int
 387 ntfs_set_bitrange(ntfs_inode* bitmap,int loc,int cnt,int bit)
 388 {
 389         int bsize,locit,error;
 390         unsigned char *bits,*it;
 391         ntfs_io io;
 392
 393         io.fn_put=ntfs_put;
 394         io.fn_get=ntfs_get;
 395         bsize=(cnt+loc%8+7)/8; /* round up */
 396         bits=ntfs_malloc(bsize);
 397         io.param=bits;
 398         io.size=bsize;
 399         if(!bits)
 400                 return ENOMEM;
 401         error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,loc/8,&io);
 402         if(error || io.size!=bsize){
 403                 ntfs_free(bits);
 404                 return error?error:EIO;
 405         }
 406         /* now set the bits */
 407         it=bits;
 408         locit=loc;
 409         while(locit%8 && cnt){ /* process first byte */
 410                 if(bit)
 411                         *it |= 1<<(locit%8);
 412                 else
 413                         *it &= ~(1<<(locit%8));
 414                 cnt--;locit++;
 415                 if(locit%8==7)
 416                         it++;
 417         }
 418         while(cnt>8){ /*process full bytes */
 419                 *it= bit ? 0xFF : 0;
 420                 cnt-=8;
 421                 locit+=8;
 422                 it++;
 423         }
 424         while(cnt){ /*process last byte */
 425                 if(bit)
 426                         *it |= 1<<(locit%8);
 427                 else
 428                         *it &= ~(1<<(locit%8));
 429                 cnt--;locit++;
 430         }
 431         /* reset to start */
 432         io.param=bits;
 433         io.size=bsize;
 434         error=ntfs_write_attr(bitmap,bitmap->vol->at_data,0,loc/8,&io);
 435         ntfs_free(bits);
 436         if(error)return error;
 437         if(io.size!=bsize)
 438                 return EIO;
 439         return 0;
 440 }
 441
 442
 443
 444 /* allocate count clusters around location. If location is -1,
 445    it does not matter where the clusters are. Result is 0 if
 446    success, in which case location and count says what they really got */
 447 int
 448 ntfs_search_bits(ntfs_inode* bitmap, int *location, int *count, int flags)
 449 {
 450         unsigned char *bits;
 451         ntfs_io io;
 452         int error=0,found=0;
 453         int loc,cnt,bloc=-1,bcnt=0;
 454         int start;
 455
 456         bits=ntfs_malloc(2048);
 457         io.fn_put=ntfs_put;
 458         io.fn_get=ntfs_get;
 459         io.param=bits;
 460
 461         /* first search within +/- 8192 clusters */
 462         start=*location/8;
 463         start= start>1024 ? start-1024 : 0;
 464         io.size=2048;
 465         error=ntfs_read_attr(bitmap,bitmap->vol->at_data,0,start,&io);
 466         if(error)goto fail;
 467         loc=start*8;
 468         cnt=*count;
 469         error=search_bits(bits,&loc,&cnt,io.size);
 470         if(error)
 471                 goto fail;
 472         if(*count==cnt){
 473                 bloc=loc;
 474                 bcnt=cnt;
 475                 goto success;
 476         }
 477
 478         /* now search from the beginning */
 479         for(start=0;1;start+=2048)
 480         {
 481                 io.param=bits;
 482                 io.size=2048;
 483                 error=ntfs_read_attr(bitmap,bitmap->vol->at_data,
 484                                      0,start,&io);
 485                 if(error)goto fail;
 486                 if(io.size==0) {
 487                         if(found)
 488                                 goto success;
 489                         else{
 490                                 error=ENOSPC;
 491                                 goto fail;
 492                         }
 493                 }
 494                 loc=start*8;
 495                 cnt=*count;
 496                 error=search_bits(bits,&loc,&cnt,io.size);
 497                 if(error)
 498                         goto fail;
 499                 if(*count==cnt)
 500                         goto success;
 501                 if(bcnt<cnt){
 502                         bcnt=cnt;
 503                         bloc=loc;
 504                         found=1;
 505                 }
 506         }
 507  success:
 508         ntfs_free(bits);
 509         /* check flags */
 510         if((flags & ALLOC_REQUIRE_LOCATION) && *location!=bloc)
 511                 error=ENOSPC;
 512         else if((flags & ALLOC_REQUIRE_SIZE) && *count!=bcnt)
 513                 error=ENOSPC;
 514         else ntfs_set_bitrange(bitmap,bloc,bcnt,1);
 515         /* If allocation failed due to the flags, tell the caller what he
 516            could have gotten */
 517         *location=bloc;
 518         *count=bcnt;
 519         return 0;
 520  fail:
 521         *location=-1;
 522         *count=0;
 523         ntfs_free(bits);
 524         return error;
 525 }
 526
 527 int ntfs_allocate_clusters(ntfs_volume *vol, int *location, int *count,
 528         int flags)
 529 {
 530         int error;
 531         error=ntfs_search_bits(vol->bitmap,location,count,flags);
 532         return error;
 533 }
 534
 535 int ntfs_deallocate_clusters(ntfs_volume *vol, int location, int count)
 536 {
 537         int error;
 538         error=ntfs_set_bitrange(vol->bitmap,location,count,0);
 539         return error;
 540 }
 541
 542 /*
 543  * Local variables:
 544  * c-file-style: "linux"
 545  * End:
 546  */
 547
 548