reactos/drivers/filesystems/fastfat_new/fat.c

   1 /*
   2  * PROJECT:         ReactOS FAT file system driver
   3  * LICENSE:         GPL - See COPYING in the top level directory
   4  * FILE:            drivers/filesystems/fastfat/fat.c
   5  * PURPOSE:         FAT support routines
   6  * PROGRAMMERS:     Alexey Vlasov
   7  */
   8
   9 /* INCLUDES *****************************************************************/
  10
  11 #define NDEBUG
  12 #include "fastfat.h"
  13
  14 /* PROTOTYPES ***************************************************************/
  15 typedef struct _FAT_SCAN_CONTEXT
  16 {
  17     PFILE_OBJECT FileObject;
  18     LARGE_INTEGER PageOffset;
  19     LONGLONG BeyondLastEntryOffset;
  20     PVOID PageBuffer;
  21     PBCB PageBcb;
  22 } FAT_SCAN_CONTEXT;
  23
  24 #define FatEntryToDataOffset(xEntry, xVcb) \
  25     ((xVcb)->DataArea + (((LONGLONG) ((xEntry) - 0x02)) << (xVcb)->BytesPerClusterLog))
  26
  27 #define FatDataOffsetToEntry(xOffset, xVcb) \
  28     ((ULONG) ((xOffset - (xVcb)->DataArea) >> (xVcb)->BytesPerClusterLog) + 0x02)
  29
  30 ULONG
  31 FatScanFat32ForContinousRun(IN OUT PFAT_PAGE_CONTEXT Context,
  32                             IN OUT PULONG Index,
  33                             IN BOOLEAN CanWait);
  34
  35 BOOLEAN
  36 NTAPI
  37 FatValidBpb(IN PBIOS_PARAMETER_BLOCK Bpb);
  38
  39 /* VARIABLES ****************************************************************/
  40 FAT_METHODS Fat12Methods = {
  41     NULL,
  42     NULL,
  43     NULL,
  44     NULL
  45 };
  46
  47 FAT_METHODS Fat16Methods = {
  48     NULL,
  49     NULL,
  50     NULL,
  51     NULL
  52 };
  53
  54 FAT_METHODS Fat32Methods = {
  55     FatScanFat32ForContinousRun,
  56     NULL,
  57     NULL,
  58     NULL
  59 };
  60
  61 /* FUNCTIONS ****************************************************************/
  62
  63 /**
  64  * Pins the page containing ByteOffset byte.
  65  *
  66  * @param Context
  67  * Keeps current BCB, Buffer pointer
  68  * and maintains current and next page offset.
  69  *
  70  * @param ByteOffset
  71  * Offset from the beginning of the data stream to be pinned.
  72  *
  73  * @return
  74  * Pointer to the buffer starting with the specified ByteOffset.
  75  */
  76 PVOID
  77 FatPinPage(
  78     PFAT_PAGE_CONTEXT Context,
  79     LONGLONG ByteOffset)
  80 {
  81     SIZE_T OffsetWithinPage;
  82
  83     OffsetWithinPage = (SIZE_T) (ByteOffset & (PAGE_SIZE - 1));
  84     ByteOffset -= OffsetWithinPage;
  85     if (ByteOffset != Context->Offset.QuadPart)
  86     {
  87         Context->Offset.QuadPart = ByteOffset;
  88         if (Context->Bcb != NULL)
  89         {
  90             CcUnpinData(Context->Bcb);
  91             Context->Bcb = NULL;
  92         }
  93         if (!CcMapData(Context->FileObject,
  94                        &Context->Offset,
  95                        PAGE_SIZE,
  96                        Context->CanWait,
  97                        &Context->Bcb,
  98                        &Context->Buffer))
  99         {
 100             Context->Offset.QuadPart = 0LL;
 101             ExRaiseStatus(STATUS_CANT_WAIT);
 102         }
 103     }
 104     Context->EndOfPage.QuadPart =
 105         Context->Offset.QuadPart + PAGE_SIZE;
 106     if (Context->EndOfPage.QuadPart
 107         > Context->EndOfData.QuadPart)
 108     {
 109         Context->ValidLength = (SIZE_T)
 110             (Context->EndOfData.QuadPart
 111                 - Context->Offset.QuadPart);
 112     }
 113     else
 114     {
 115         Context->ValidLength = PAGE_SIZE;
 116     }
 117     return Add2Ptr(Context->Buffer, OffsetWithinPage, PVOID);
 118 }
 119
 120 /**
 121  * Pins the next page of data stream.
 122  *
 123  * @param Context
 124  * Keeps current BCB, Buffer pointer
 125  * and maintains current and next page offset.
 126  *
 127  * @return
 128  * Pointer to the buffer starting with the beginning of the next page.
 129  */
 130 PVOID
 131 FatPinNextPage(
 132     PFAT_PAGE_CONTEXT Context)
 133 {
 134     ASSERT ((Context->Offset.QuadPart % PAGE_SIZE)
 135         != (Context->EndOfPage.QuadPart % PAGE_SIZE)
 136         && Context->Bcb != NULL);
 137
 138     ASSERT  (Context->ValidLength == PAGE_SIZE);
 139
 140     Context->Offset = Context->EndOfPage;
 141     CcUnpinData(Context->Bcb);
 142     if (!CcMapData(Context->FileObject,
 143                    &Context->Offset,
 144                    PAGE_SIZE,
 145                    Context->CanWait,
 146                    &Context->Bcb,
 147                    &Context->Buffer))
 148     {
 149         Context->Bcb = NULL;
 150         Context->Offset.QuadPart = 0LL;
 151         ExRaiseStatus(STATUS_CANT_WAIT);
 152     }
 153     Context->EndOfPage.QuadPart =
 154         Context->Offset.QuadPart + PAGE_SIZE;
 155     return Context->Buffer;
 156 }
 157
 158 /**
 159  * Determines the index of the set bit.
 160  *
 161  * @param Number
 162  * Number having a single bit set.
 163  *
 164  * @return
 165  * Index of the set bit.
 166  */
 167 FORCEINLINE
 168 ULONG
 169 FatPowerOfTwo(
 170     ULONG Number)
 171 {
 172     ULONG Temp;
 173     Temp = Number
 174         - ((Number >> 1) & 033333333333)
 175         - ((Number >> 2) & 011111111111);
 176     return (((Temp + (Temp >> 3)) & 030707070707) % 63);
 177 }
 178
 179 /**
 180  * Scans FAT32 for continous chain of clusters
 181  *
 182  * @param Context
 183  * Pointer to FAT_PAGE_CONTEXT.
 184  *
 185  * @param Index
 186  * Supplies the Index of the first cluster
 187  * and receves the last index after the last
 188  * cluster in the chain.
 189  *
 190  * @param CanWait
 191  * Indicates if the context allows blocking.
 192  *
 193  * @return
 194  * Value of the last claster terminated the scan.
 195  *
 196  * @note
 197  * Raises STATUS_CANT_WAIT race condition.
 198  */
 199 ULONG
 200 FatScanFat32ForContinousRun(IN OUT PFAT_PAGE_CONTEXT Context,
 201                             IN OUT PULONG Index,
 202                             IN BOOLEAN CanWait)
 203 {
 204     PULONG Entry, EndOfPage;
 205
 206     Entry = FatPinPage(Context, ((LONGLONG) *Index) << 0x2);
 207     EndOfPage = FatPinEndOfPage(Context, PULONG);
 208     while (TRUE)
 209     {
 210         do
 211         {
 212             if ((*Entry & FAT_CLUSTER_LAST) != ++(*Index))
 213                 return (*Entry & FAT_CLUSTER_LAST);
 214         } while (++Entry < EndOfPage);
 215         /* Check if this is the last available entry */
 216         if (FatPinIsLastPage(Context))
 217             break;
 218         Entry = (PULONG) FatPinNextPage(Context);
 219         EndOfPage = FatPinEndOfPage(Context, PULONG);
 220     }
 221     return (*Index - 1);
 222 }
 223
 224 ULONG
 225 FatSetFat32ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context,
 226                         IN ULONG Index,
 227                         IN ULONG Length,
 228                         IN BOOLEAN CanWait)
 229 {
 230     ExRaiseStatus(STATUS_NOT_IMPLEMENTED);
 231 }
 232
 233 ULONG
 234 FatScanFat32ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context,
 235                         IN OUT PULONG Index,
 236                         IN ULONG IndexValue,
 237                         IN BOOLEAN CanWait)
 238 {
 239     ExRaiseStatus(STATUS_NOT_IMPLEMENTED);
 240 }
 241
 242 ULONG
 243 FatSetFat32ValueRun(IN OUT PFAT_SCAN_CONTEXT Context,
 244                     IN ULONG Index,
 245                     IN ULONG Length,
 246                     IN ULONG IndexValue,
 247                     IN BOOLEAN CanWait)
 248 {
 249     ExRaiseStatus(STATUS_NOT_IMPLEMENTED);
 250 }
 251
 252 /**
 253  * Queries file MCB for the specified region [Vbo, Vbo + Length],
 254  * returns the number of runs in the region as well as the first
 255  * run of the range itself.
 256  * If the specified region is not fully cached in MCB the routine
 257  * scans FAT for the file and fills the MCB until the file offset
 258  * (defined as Vbo + Length) is reached.
 259  *
 260  * @param Fcb
 261  * Pointer to FCB structure for the file.
 262  *
 263  * @param Vbo
 264  * Virtual Byte Offset in the file.
 265  *
 266  * @param Lbo
 267  * Receives the Value of Logical Byte offset corresponding
 268  * to supplied Vbo Value.
 269  *
 270  * @param Length
 271  * Supplies file range length to be examined and receives
 272  * the length of first run.
 273  *
 274  * @param OutIndex
 275  * Receives the index (in MCB cache) of first run.
 276  *
 277  * @return
 278  * Incremented index of the last run (+1).
 279  *
 280  * @note
 281  * Should be called by I/O routines to split the I/O operation
 282  * into sequential or parallel I/O operations.
 283  */
 284 ULONG
 285 FatScanFat(IN PFCB Fcb,
 286            IN LONGLONG Vbo,
 287            OUT PLONGLONG Lbo,
 288            IN OUT PLONGLONG Length,
 289            OUT PULONG Index,
 290            IN BOOLEAN CanWait)
 291 {
 292     LONGLONG CurrentLbo, CurrentVbo, BeyondLastVbo, CurrentLength;
 293     ULONG Entry, NextEntry, NumberOfEntries, CurrentIndex;
 294     FAT_PAGE_CONTEXT Context;
 295     PVCB Vcb;
 296
 297     /* Some often used values */
 298     Vcb = Fcb->Vcb;
 299     CurrentIndex = 0;
 300     BeyondLastVbo = Vbo + *Length;
 301     CurrentLength = ((LONGLONG) Vcb->Clusters) << Vcb->BytesPerClusterLog;
 302     if (BeyondLastVbo > CurrentLength)
 303         BeyondLastVbo = CurrentLength;
 304     /* Try to locate first run */
 305     if (FsRtlLookupLargeMcbEntry(&Fcb->Mcb, Vbo, Lbo, Length, NULL, NULL, Index))
 306     {
 307         /* Check if we have a single mapped run */
 308         if (Vbo >= BeyondLastVbo)
 309             goto FatScanFcbFatExit;
 310     } else {
 311         *Length = 0L;
 312     }
 313     /* Get the first scan startup values */
 314     if (FsRtlLookupLastLargeMcbEntryAndIndex(
 315         &Fcb->Mcb, &CurrentVbo, &CurrentLbo, &CurrentIndex))
 316     {
 317         Entry = FatDataOffsetToEntry(CurrentLbo, Vcb);
 318     }
 319     else
 320     {
 321         /* Map is empty, set up initial values */
 322         Entry = Fcb->FirstCluster;
 323         if (Entry <= 0x2)
 324             ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR);
 325         if (Entry >= Vcb->Clusters)
 326         {
 327             if (Entry < FAT_CLUSTER_LAST)
 328                 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR);
 329                 BeyondLastVbo = 0LL;
 330         }
 331         CurrentIndex = 0L;
 332         CurrentVbo = 0LL;
 333     }
 334     /* Initialize Context */
 335     RtlZeroMemory(&Context, sizeof(Context));
 336     Context.FileObject = Vcb->StreamFileObject;
 337     Context.EndOfData.QuadPart = Vcb->BeyondLastClusterInFat;
 338
 339     while (CurrentVbo < BeyondLastVbo)
 340     {
 341         /* Locate Continous run starting with the current entry */
 342         NumberOfEntries = Entry;
 343         NextEntry = Vcb->Methods.ScanContinousRun(
 344         &Context, &NumberOfEntries, CanWait);
 345         NumberOfEntries -= Entry;
 346         /* Check value that terminated the for being valid for FAT */
 347         if (NextEntry <= 0x2)
 348             ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR);
 349         if (NextEntry >= Vcb->Clusters)
 350         {
 351             if (NextEntry < FAT_CLUSTER_LAST)
 352             ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR);
 353             break;
 354         }
 355        /* Add new run */
 356         CurrentLength = ((LONGLONG) NumberOfEntries)
 357             << Vcb->BytesPerClusterLog;
 358         FsRtlAddLargeMcbEntry(&Fcb->Mcb,
 359             CurrentVbo,
 360             FatEntryToDataOffset(Entry, Vcb),
 361             CurrentLength);
 362         /* Setup next iteration */
 363         Entry = NextEntry;
 364         CurrentVbo += CurrentLength;
 365         CurrentIndex ++;
 366     }
 367     if (*Length == 0LL && CurrentIndex > 0)
 368     {
 369         if (!FsRtlLookupLargeMcbEntry(&Fcb->Mcb,
 370             Vbo, Lbo, Length, NULL, NULL, Index))
 371         {
 372             *Index = 0L;
 373             *Lbo = 0LL;
 374         }
 375     }
 376 FatScanFcbFatExit:
 377     return CurrentIndex;
 378 }
 379
 380 BOOLEAN
 381 NTAPI
 382 FatValidBpb(IN PBIOS_PARAMETER_BLOCK Bpb)
 383 {
 384     return (FatValidBytesPerSector(Bpb->BytesPerSector)
 385         && FatValidSectorsPerCluster(Bpb->SectorsPerCluster)
 386         && Bpb->ReservedSectors > 0
 387         && Bpb->Fats > 0
 388         && (Bpb->Sectors > 0 || Bpb->LargeSectors > 0)
 389         && (Bpb->SectorsPerFat > 0
 390             || (Bpb->LargeSectorsPerFat > 0 && Bpb->FsVersion == 0))
 391         && (Bpb->Media == 0xf0
 392             || Bpb->Media == 0xf8
 393             || Bpb->Media == 0xf9
 394             || Bpb->Media == 0xfb
 395             || Bpb->Media == 0xfc
 396             || Bpb->Media == 0xfd
 397             || Bpb->Media == 0xfe
 398             || Bpb->Media == 0xff)
 399         && (Bpb->SectorsPerFat == 0 || Bpb->RootEntries > 0)
 400         && (Bpb->SectorsPerFat > 0 || !Bpb->MirrorDisabled));
 401 }
 402
 403 VOID
 404 FatiInitializeVcb(PVCB Vcb)
 405 {
 406     ULONG ClustersCapacity;
 407
 408     /* Various characteristics needed for navigation in FAT */
 409     if ((Vcb->Sectors = Vcb->Bpb.Sectors) == 0)
 410         Vcb->Sectors = Vcb->Bpb.LargeSectors;
 411     if ((Vcb->SectorsPerFat = Vcb->Bpb.SectorsPerFat) == 0)
 412         Vcb->SectorsPerFat = Vcb->Bpb.LargeSectorsPerFat;
 413     Vcb->RootDirent = Vcb->Bpb.ReservedSectors + Vcb->Bpb.Fats * Vcb->SectorsPerFat;
 414     Vcb->RootDirentSectors = BytesToSectors(Vcb,
 415         Vcb->Bpb.RootEntries * sizeof(DIR_ENTRY));
 416     Vcb->DataArea = Vcb->RootDirent + Vcb->RootDirentSectors;
 417     Vcb->Clusters = (Vcb->Sectors - Vcb->Bpb.ReservedSectors
 418         - Vcb->Bpb.Fats * Vcb->SectorsPerFat
 419         - Vcb->RootDirentSectors) / Vcb->Bpb.SectorsPerCluster;
 420     if (Vcb->BytesPerClusterLog < 4087)
 421     {
 422         Vcb->IndexDepth = 0x0c;
 423         Vcb->Methods = Fat12Methods;
 424     }
 425     else
 426     {
 427         Vcb->IndexDepth = 0x10;
 428         Vcb->Methods = Fat16Methods;
 429     }
 430     /* Large Sectors are used for FAT32 */
 431     if (Vcb->Bpb.Sectors == 0) {
 432         Vcb->IndexDepth = 0x20;
 433         Vcb->Methods = Fat32Methods;
 434     }
 435     ClustersCapacity = (SectorsToBytes(Vcb, Vcb->Sectors) * 0x8 / Vcb->IndexDepth) - 1;
 436     if (Vcb->Clusters > ClustersCapacity)
 437         Vcb->Clusters = ClustersCapacity;
 438     Vcb->BytesPerCluster = SectorsToBytes(Vcb, Vcb->Bpb.SectorsPerCluster);
 439     Vcb->BytesPerClusterLog = FatPowerOfTwo(Vcb->BytesPerCluster);
 440     Vcb->BeyondLastClusterInFat = ((LONGLONG) Vcb->Clusters) * Vcb->IndexDepth / 0x8;
 441
 442     /* Update real volume size with the real value. */
 443     Vcb->Header.FileSize.QuadPart =
 444     Vcb->Header.AllocationSize.QuadPart = SectorsToBytes(Vcb, Vcb->Sectors);
 445 }
 446
 447 NTSTATUS
 448 FatInitializeVcb(IN PFAT_IRP_CONTEXT IrpContext,
 449                  IN PVCB Vcb,
 450                  IN PDEVICE_OBJECT TargetDeviceObject,
 451                  IN PVPB Vpb)
 452 {
 453     NTSTATUS Status;
 454     PBCB Bcb;
 455     PVOID Buffer;
 456     LARGE_INTEGER Offset;
 457
 458     RtlZeroMemory(Vcb, sizeof(*Vcb));
 459
 460     /* Initialize list head, so that it will
 461      * not fail in cleanup.
 462      */
 463     InitializeListHead(&Vcb->VcbLinks);
 464
 465     /* Setup FCB Header */
 466     Vcb->Header.NodeTypeCode = FAT_NTC_VCB;
 467     Vcb->Header.NodeByteSize = sizeof(*Vcb);
 468
 469     /* Setup Vcb fields */
 470     Vcb->TargetDeviceObject = TargetDeviceObject;
 471     ObReferenceObject(TargetDeviceObject);
 472     Vcb->Vpb = Vpb;
 473
 474     /* Setup FCB Header */
 475     ExInitializeFastMutex(&Vcb->HeaderMutex);
 476     FsRtlSetupAdvancedHeader(&Vcb->Header, &Vcb->HeaderMutex);
 477
 478     /* Create Volume File Object */
 479     Vcb->StreamFileObject = IoCreateStreamFileObject(NULL,
 480                                                      Vcb->TargetDeviceObject);
 481
 482     /* We have to setup all FCB fields needed for CC */
 483     Vcb->StreamFileObject->FsContext = Vcb;
 484     Vcb->StreamFileObject->SectionObjectPointer = &Vcb->SectionObjectPointers;
 485
 486     /* At least full boot sector should be available */
 487     Vcb->Header.FileSize.QuadPart = sizeof(PACKED_BOOT_SECTOR);
 488     Vcb->Header.AllocationSize.QuadPart = sizeof(PACKED_BOOT_SECTOR);
 489     Vcb->Header.ValidDataLength.HighPart = MAXLONG;
 490     Vcb->Header.ValidDataLength.LowPart = MAXULONG;
 491
 492     /* Initialize CC */
 493     CcInitializeCacheMap(Vcb->StreamFileObject,
 494                          (PCC_FILE_SIZES)&Vcb->Header.AllocationSize,
 495                          FALSE,
 496                          &FatGlobalData.CacheMgrNoopCallbacks,
 497                          Vcb);
 498
 499     /* Read boot sector */
 500     Offset.QuadPart = 0;
 501     Bcb = NULL;
 502
 503     /* Note: Volume Read path does not require
 504      * any of the parameters set further
 505      * in this routine.
 506      */
 507     if (CcMapData(Vcb->StreamFileObject,
 508                   &Offset,
 509                   sizeof(PACKED_BOOT_SECTOR),
 510                   TRUE,
 511                   &Bcb,
 512                   &Buffer))
 513     {
 514         PPACKED_BOOT_SECTOR BootSector = (PPACKED_BOOT_SECTOR) Buffer;
 515         FatUnpackBios(&Vcb->Bpb, &BootSector->PackedBpb);
 516         if (!(FatBootSectorJumpValid(BootSector->Jump) &&
 517             FatValidBpb(&Vcb->Bpb)))
 518         {
 519             Status = STATUS_UNRECOGNIZED_VOLUME;
 520         }
 521         CopyUchar4(&Vcb->Vpb->SerialNumber, BootSector->Id);
 522         CcUnpinData(Bcb);
 523     }
 524     else
 525     {
 526         Status = STATUS_UNRECOGNIZED_VOLUME;
 527         goto FatInitializeVcbCleanup;
 528     }
 529
 530     /* Set up notifications */
 531     FsRtlNotifyInitializeSync(&Vcb->NotifySync);
 532     InitializeListHead(&Vcb->NotifyList);
 533
 534     /* Call helper function */
 535     FatiInitializeVcb(Vcb);
 536
 537     /* Add this Vcb to global Vcb list */
 538     (VOID)FatAcquireExclusiveGlobal(IrpContext);
 539     InsertTailList(&FatGlobalData.VcbListHead, &Vcb->VcbLinks);
 540     FatReleaseGlobal(IrpContext);
 541
 542     return STATUS_SUCCESS;
 543
 544 FatInitializeVcbCleanup:
 545
 546     /* Unwind the routine actions */
 547     FatUninitializeVcb(Vcb);
 548     return Status;
 549 }
 550
 551 VOID
 552 FatUninitializeVcb(IN PVCB Vcb)
 553 {
 554     LARGE_INTEGER ZeroSize;
 555
 556     ZeroSize.QuadPart = 0LL;
 557
 558     /* Close volume file */
 559     if (Vcb->StreamFileObject != NULL)
 560     {
 561         /* Uninitialize CC. */
 562         CcUninitializeCacheMap(Vcb->StreamFileObject, &ZeroSize, NULL);
 563         ObDereferenceObject(Vcb->StreamFileObject);
 564         Vcb->StreamFileObject = NULL;
 565     }
 566
 567     /* Free notifications stuff */
 568     FsRtlNotifyUninitializeSync(&Vcb->NotifySync);
 569
 570     /* Unlink from global Vcb list. */
 571     RemoveEntryList(&Vcb->VcbLinks);
 572
 573     /* Release Target Device */
 574     ObDereferenceObject(Vcb->TargetDeviceObject);
 575     Vcb->TargetDeviceObject = NULL;
 576 }
 577
 578 /* EOF */
 579
 580