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