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
9 /* INCLUDES *****************************************************************/
14 /* PROTOTYPES ***************************************************************/
15 typedef struct _FAT_SCAN_CONTEXT
17 PFILE_OBJECT FileObject
;
18 LARGE_INTEGER PageOffset
;
19 LONGLONG BeyondLastEntryOffset
;
24 #define FatEntryToDataOffset(xEntry, xVcb) \
25 ((xVcb)->DataArea + (((LONGLONG) ((xEntry) - 0x02)) << (xVcb)->BytesPerClusterLog))
27 #define FatDataOffsetToEntry(xOffset, xVcb) \
28 ((ULONG) ((xOffset - (xVcb)->DataArea) >> (xVcb)->BytesPerClusterLog) + 0x02)
31 FatScanFat12ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
36 FatSetFat12ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
42 FatScanFat12ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
48 FatSetFat12ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
55 FatScanFat16ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
60 FatSetFat16ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
66 FatScanFat16ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
72 FatSetFat16ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
79 FatScanFat32ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
84 FatSetFat32ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
90 FatScanFat32ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
96 FatSetFat32ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
104 FatValidBpb(IN PBIOS_PARAMETER_BLOCK Bpb
);
106 /* VARIABLES ****************************************************************/
107 FAT_METHODS Fat12Methods
= {
108 FatScanFat12ForContinousRun
,
109 FatSetFat12ContinousRun
,
110 FatScanFat16ForValueRun
,
114 FAT_METHODS Fat16Methods
= {
115 FatScanFat16ForContinousRun
,
116 FatSetFat16ContinousRun
,
117 FatScanFat16ForValueRun
,
121 FAT_METHODS Fat32Methods
= {
122 FatScanFat32ForContinousRun
,
123 FatSetFat32ContinousRun
,
124 FatScanFat32ForValueRun
,
128 /* FUNCTIONS ****************************************************************/
131 * Determines the index of the set bit.
134 * Number having a single bit set.
137 * Index of the set bit.
146 - ((Number
>> 1) & 033333333333)
147 - ((Number
>> 2) & 011111111111);
148 return (((Temp
+ (Temp
>> 3)) & 030707070707) % 63);
152 FatScanFat12ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
156 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
160 FatSetFat12ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
165 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
169 FatScanFat12ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
174 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
178 FatSetFat12ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
184 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
188 FatScanFat16ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
192 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
196 FatSetFat16ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
201 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
205 FatScanFat16ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
210 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
214 FatSetFat16ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
220 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
224 * Scans FAT32 for continous chain of clusters
227 * Pointer to FAT_SCAN_CONTEXT.
230 * Supplies the Index of the first cluster
231 * and receves the last index after the last
232 * cluster in the chain.
235 * Indicates if the context allows blocking.
238 * Value of the last claster terminated the scan.
241 * Raises STATUS_CANT_WAIT race condition.
244 FatScanFat32ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
249 SIZE_T OffsetWithinPage
, PageValidLength
;
250 PULONG Entry
, BeyoudLastEntry
;
251 /* Determine page offset and the offset within page
252 * for the first cluster.
254 PageValidLength
= PAGE_SIZE
;
255 PageOffset
= ((LONGLONG
) *Index
) << 0x2;
256 OffsetWithinPage
= (SIZE_T
) (PageOffset
& (PAGE_SIZE
- 1));
257 PageOffset
-= OffsetWithinPage
;
258 /* Check if the context already has the required page mapped.
259 * Map the first page is necessary.
261 if (PageOffset
!= Context
->PageOffset
.QuadPart
)
263 Context
->PageOffset
.QuadPart
= PageOffset
;
264 if (Context
->PageBcb
!= NULL
)
266 CcUnpinData(Context
->PageBcb
);
267 Context
->PageBcb
= NULL
;
269 if (!CcMapData(Context
->FileObject
,
270 &Context
->PageOffset
,
274 &Context
->PageBuffer
))
276 Context
->PageOffset
.QuadPart
= 0LL;
277 ExRaiseStatus(STATUS_CANT_WAIT
);
280 Entry
= Add2Ptr(Context
->PageBuffer
, OffsetWithinPage
, PULONG
);
281 /* Next Page Offset */
282 PageOffset
= Context
->PageOffset
.QuadPart
+ PAGE_SIZE
;
283 if (PageOffset
> Context
->BeyondLastEntryOffset
)
284 PageValidLength
= (SIZE_T
) (Context
->BeyondLastEntryOffset
285 - Context
->PageOffset
.QuadPart
);
286 BeyoudLastEntry
= Add2Ptr(Context
->PageBuffer
, PageValidLength
, PULONG
);
291 if ((*Entry
& FAT_CLUSTER_LAST
) != ++(*Index
))
292 return (*Entry
& FAT_CLUSTER_LAST
);
293 } while (++Entry
< BeyoudLastEntry
);
294 /* Check if this is the last available entry */
295 if (PageValidLength
< PAGE_SIZE
)
297 /* We are getting beyond current page and
298 * are still in the continous run, map the next page.
300 Context
->PageOffset
.QuadPart
= PageOffset
;
301 CcUnpinData(Context
->PageBcb
);
302 if (!CcMapData(Context
->FileObject
,
303 &Context
->PageOffset
, PAGE_SIZE
, CanWait
,
304 &Context
->PageBcb
, &Context
->PageBuffer
))
306 Context
->PageBcb
= NULL
;
307 Context
->PageOffset
.QuadPart
= 0LL;
308 ExRaiseStatus(STATUS_CANT_WAIT
);
310 Entry
= (PULONG
) Context
->PageBuffer
;
311 /* Next Page Offset */
312 PageOffset
= Context
->PageOffset
.QuadPart
+ PAGE_SIZE
;
313 if (PageOffset
> Context
->BeyondLastEntryOffset
)
314 PageValidLength
= (SIZE_T
) (Context
->BeyondLastEntryOffset
315 - Context
->PageOffset
.QuadPart
);
316 BeyoudLastEntry
= Add2Ptr(Context
->PageBuffer
, PageValidLength
, PULONG
);
322 FatSetFat32ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
327 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
331 FatScanFat32ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
336 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
340 FatSetFat32ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
346 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
350 * Queries file MCB for the specified region [Vbo, Vbo + Length],
351 * returns the number of runs in the region as well as the first
352 * run of the range itself.
353 * If the specified region is not fully cached in MCB the routine
354 * scans FAT for the file and fills the MCB until the file offset
355 * (defined as Vbo + Length) is reached.
358 * Pointer to FCB structure for the file.
361 * Virtual Byte Offset in the file.
364 * Receives the Value of Logical Byte offset corresponding
365 * to supplied Vbo Value.
368 * Supplies file range length to be examined and receives
369 * the length of first run.
372 * Receives the index (in MCB cache) of first run.
375 * Incremented index of the last run (+1).
378 * Should be called by I/O routines to split the I/O operation
379 * into sequential or parallel I/O operations.
382 FatScanFat(IN PFCB Fcb
,
385 IN OUT PLONGLONG Length
,
389 LONGLONG CurrentLbo
, CurrentVbo
, BeyondLastVbo
, CurrentLength
;
390 ULONG Entry
, NextEntry
, NumberOfEntries
, CurrentIndex
;
391 FAT_SCAN_CONTEXT Context
;
394 /* Some often used values */
397 BeyondLastVbo
= Vbo
+ *Length
;
398 CurrentLength
= ((LONGLONG
) Vcb
->Clusters
) << Vcb
->BytesPerClusterLog
;
399 if (BeyondLastVbo
> CurrentLength
)
400 BeyondLastVbo
= CurrentLength
;
401 /* Try to locate first run */
402 if (FsRtlLookupLargeMcbEntry(&Fcb
->Mcb
, Vbo
, Lbo
, Length
, NULL
, NULL
, Index
))
404 /* Check if we have a single mapped run */
405 if (Vbo
>= BeyondLastVbo
)
406 goto FatScanFcbFatExit
;
410 /* Get the first scan startup values */
411 if (FsRtlLookupLastLargeMcbEntryAndIndex(
412 &Fcb
->Mcb
, &CurrentVbo
, &CurrentLbo
, &CurrentIndex
))
414 Entry
= FatDataOffsetToEntry(CurrentLbo
, Vcb
);
418 /* Map is empty, set up initial values */
419 Entry
= Fcb
->FirstCluster
;
421 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
422 if (Entry
>= Vcb
->Clusters
)
424 if (Entry
< FAT_CLUSTER_LAST
)
425 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
431 RtlZeroMemory(&Context
, sizeof(Context
));
432 Context
.FileObject
= Vcb
->VolumeFileObject
;
433 while (CurrentVbo
< BeyondLastVbo
)
435 /* Locate Continous run starting with the current entry */
436 NumberOfEntries
= Entry
;
437 NextEntry
= Vcb
->Methods
.ScanContinousRun(
438 &Context
, &NumberOfEntries
, CanWait
);
439 NumberOfEntries
-= Entry
;
440 /* Check value that terminated the for being valid for FAT */
441 if (NextEntry
<= 0x2)
442 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
443 if (NextEntry
>= Vcb
->Clusters
)
445 if (NextEntry
< FAT_CLUSTER_LAST
)
446 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
450 CurrentLength
= ((LONGLONG
) NumberOfEntries
)
451 << Vcb
->BytesPerClusterLog
;
452 FsRtlAddLargeMcbEntry(&Fcb
->Mcb
,
454 FatEntryToDataOffset(Entry
, Vcb
),
456 /* Setup next iteration */
458 CurrentVbo
+= CurrentLength
;
461 if (*Length
== 0LL && CurrentIndex
> 0)
463 if (!FsRtlLookupLargeMcbEntry(&Fcb
->Mcb
,
464 Vbo
, Lbo
, Length
, NULL
, NULL
, Index
))
476 FatValidBpb(IN PBIOS_PARAMETER_BLOCK Bpb
)
478 return (FatValidBytesPerSector(Bpb
->BytesPerSector
)
479 && FatValidSectorsPerCluster(Bpb
->SectorsPerCluster
)
480 && Bpb
->ReservedSectors
> 0
482 && (Bpb
->Sectors
> 0 || Bpb
->LargeSectors
> 0)
483 && (Bpb
->SectorsPerFat
> 0
484 || (Bpb
->LargeSectorsPerFat
> 0 && Bpb
->FsVersion
== 0))
485 && (Bpb
->Media
== 0xf0
486 || Bpb
->Media
== 0xf8
487 || Bpb
->Media
== 0xf9
488 || Bpb
->Media
== 0xfb
489 || Bpb
->Media
== 0xfc
490 || Bpb
->Media
== 0xfd
491 || Bpb
->Media
== 0xfe
492 || Bpb
->Media
== 0xff)
493 && (Bpb
->SectorsPerFat
== 0 || Bpb
->RootEntries
> 0)
494 && (Bpb
->SectorsPerFat
> 0 || !Bpb
->MirrorDisabled
));
498 FatiInitializeVcb(PVCB Vcb
)
500 ULONG ClustersCapacity
;
502 /* Various characteristics needed for navigation in FAT */
503 if ((Vcb
->Sectors
= Vcb
->Bpb
.Sectors
) == 0)
504 Vcb
->Sectors
= Vcb
->Bpb
.LargeSectors
;
505 if ((Vcb
->SectorsPerFat
= Vcb
->Bpb
.SectorsPerFat
) == 0)
506 Vcb
->SectorsPerFat
= Vcb
->Bpb
.LargeSectorsPerFat
;
507 Vcb
->RootDirent
= Vcb
->Bpb
.ReservedSectors
+ Vcb
->Bpb
.Fats
* Vcb
->SectorsPerFat
;
508 Vcb
->RootDirentSectors
= BytesToSectors(Vcb
,
509 Vcb
->Bpb
.RootEntries
* sizeof(DIR_ENTRY
));
510 Vcb
->DataArea
= Vcb
->RootDirent
+ Vcb
->RootDirentSectors
;
511 Vcb
->Clusters
= (Vcb
->Sectors
- Vcb
->Bpb
.ReservedSectors
512 - Vcb
->Bpb
.Fats
* Vcb
->SectorsPerFat
513 - Vcb
->RootDirentSectors
) / Vcb
->Bpb
.SectorsPerCluster
;
514 if (Vcb
->BytesPerClusterLog
< 4087)
516 Vcb
->IndexDepth
= 0x0c;
517 Vcb
->Methods
= Fat12Methods
;
521 Vcb
->IndexDepth
= 0x10;
522 Vcb
->Methods
= Fat16Methods
;
524 /* Large Sectors are used for FAT32 */
525 if (Vcb
->Bpb
.Sectors
== 0) {
526 Vcb
->IndexDepth
= 0x20;
527 Vcb
->Methods
= Fat32Methods
;
529 ClustersCapacity
= (SectorsToBytes(Vcb
, Vcb
->Sectors
) * 0x8 / Vcb
->IndexDepth
) - 1;
530 if (Vcb
->Clusters
> ClustersCapacity
)
531 Vcb
->Clusters
= ClustersCapacity
;
532 Vcb
->BytesPerCluster
= SectorsToBytes(Vcb
, Vcb
->Bpb
.SectorsPerCluster
);
533 Vcb
->BytesPerClusterLog
= FatPowerOfTwo(Vcb
->BytesPerCluster
);
534 Vcb
->BeyondLastClusterInFat
= ((LONGLONG
) Vcb
->Clusters
) * Vcb
->IndexDepth
/ 0x8;
538 FatInitializeVcb(IN PVCB Vcb
,
539 IN PDEVICE_OBJECT TargetDeviceObject
,
545 LARGE_INTEGER Offset
;
547 RtlZeroMemory(Vcb
, sizeof(*Vcb
));
549 /* Initialize list head, so that it will
550 * not fail in cleanup.
552 InitializeListHead(&Vcb
->VcbLinks
);
554 /* Setup FCB Header */
555 Vcb
->Header
.NodeTypeCode
= FAT_NTC_VCB
;
556 Vcb
->Header
.NodeByteSize
= sizeof(*Vcb
);
558 /* Setup Vcb fields */
559 Vcb
->TargetDeviceObject
= TargetDeviceObject
;
560 ObReferenceObject(TargetDeviceObject
);
562 /* Setup FCB Header */
563 ExInitializeFastMutex(&Vcb
->HeaderMutex
);
564 FsRtlSetupAdvancedHeader(&Vcb
->Header
, &Vcb
->HeaderMutex
);
566 /* Create Volume File Object */
567 Vcb
->VolumeFileObject
= IoCreateStreamFileObject(NULL
,
568 Vcb
->TargetDeviceObject
);
570 /* We have to setup all FCB fields needed for CC */
571 Vcb
->VolumeFileObject
->FsContext
= Vcb
;
572 Vcb
->VolumeFileObject
->SectionObjectPointer
= &Vcb
->SectionObjectPointers
;
574 /* At least full boot sector should be available */
575 Vcb
->Header
.FileSize
.QuadPart
= sizeof(PACKED_BOOT_SECTOR
);
576 Vcb
->Header
.AllocationSize
.QuadPart
= sizeof(PACKED_BOOT_SECTOR
);
577 Vcb
->Header
.ValidDataLength
.HighPart
= MAXLONG
;
578 Vcb
->Header
.ValidDataLength
.LowPart
= MAXULONG
;
581 CcInitializeCacheMap(Vcb
->VolumeFileObject
,
582 (PCC_FILE_SIZES
)&Vcb
->Header
.AllocationSize
,
584 &FatGlobalData
.CacheMgrNoopCallbacks
,
587 /* Read boot sector */
591 /* Note: Volume Read path does not require
592 * any of the parameters set further
595 if (CcMapData(Vcb
->VolumeFileObject
,
597 sizeof(PACKED_BOOT_SECTOR
),
602 PPACKED_BOOT_SECTOR BootSector
= (PPACKED_BOOT_SECTOR
) Buffer
;
603 FatUnpackBios(&Vcb
->Bpb
, &BootSector
->PackedBpb
);
604 if (!(FatBootSectorJumpValid(BootSector
->Jump
) &&
605 FatValidBpb(&Vcb
->Bpb
)))
607 Status
= STATUS_UNRECOGNIZED_VOLUME
;
609 CopyUchar4(&Vpb
->SerialNumber
, BootSector
->Id
);
614 Status
= STATUS_UNRECOGNIZED_VOLUME
;
615 goto FatInitializeVcbCleanup
;
618 /* Set up notifications */
619 FsRtlNotifyInitializeSync(&Vcb
->NotifySync
);
620 InitializeListHead(&Vcb
->NotifyList
);
622 /* Call helper function */
623 FatiInitializeVcb(Vcb
);
625 /* Add this Vcb to grobal Vcb list. */
626 InsertTailList(&FatGlobalData
.VcbListHead
, &Vcb
->VcbLinks
);
627 return STATUS_SUCCESS
;
629 FatInitializeVcbCleanup
:
631 /* Unwind the routine actions */
632 FatUninitializeVcb(Vcb
);
637 FatUninitializeVcb(IN PVCB Vcb
)
639 LARGE_INTEGER ZeroSize
;
641 ZeroSize
.QuadPart
= 0LL;
643 /* Close volume file */
644 if (Vcb
->VolumeFileObject
!= NULL
)
646 /* Uninitialize CC. */
647 CcUninitializeCacheMap(Vcb
->VolumeFileObject
, &ZeroSize
, NULL
);
648 ObDereferenceObject(Vcb
->VolumeFileObject
);
649 Vcb
->VolumeFileObject
= NULL
;
652 /* Free notifications stuff */
653 FsRtlNotifyUninitializeSync(&Vcb
->NotifySync
);
655 /* Unlink from global Vcb list. */
656 RemoveEntryList(&Vcb
->VcbLinks
);
658 /* Release Target Device */
659 ObDereferenceObject(Vcb
->TargetDeviceObject
);
660 Vcb
->TargetDeviceObject
= NULL
;