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 BeyoundLastEntryOffset
;
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 ****************************************************************/
132 * Determines the index of the set bit.
134 * Number = Number having a single bit set.
135 * RETURNS: Index of the set bit.
144 - ((Number
>> 1) & 033333333333)
145 - ((Number
>> 2) & 011111111111);
146 return (((Temp
+ (Temp
>> 3)) & 030707070707) % 63);
150 FatScanFat12ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
154 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
158 FatSetFat12ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
163 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
167 FatScanFat12ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
172 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
176 FatSetFat12ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
182 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
186 FatScanFat16ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
190 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
194 FatSetFat16ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
199 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
203 FatScanFat16ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
208 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
212 FatSetFat16ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
218 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
223 * Scans FAT32 for continous chain of clusters
225 * Context = Pointer to FAT_SCAN_CONTEXT.
226 * Index = Supplies the Index of the first cluster
227 * and receves the last index after the last
228 * cluster in the chain.
229 * CanWait = Indicates if the context allows blocking.
230 * RETURNS: Value of the last claster terminated the scan.
231 * NOTES: Raises STATUS_CANT_WAIT race condition.
234 FatScanFat32ForContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
239 SIZE_T OffsetWithinPage
, PageValidLength
;
240 PULONG Entry
, BeyoudLastEntry
;
241 /* Determine page offset and the offset within page
242 * for the first cluster.
244 PageValidLength
= PAGE_SIZE
;
245 PageOffset
= ((LONGLONG
) *Index
) << 0x2;
246 OffsetWithinPage
= (SIZE_T
) (PageOffset
& (PAGE_SIZE
- 1));
247 PageOffset
-= OffsetWithinPage
;
248 /* Check if the context already has the required page mapped.
249 * Map the first page is necessary.
251 if (PageOffset
!= Context
->PageOffset
.QuadPart
)
253 Context
->PageOffset
.QuadPart
= PageOffset
;
254 if (Context
->PageBcb
!= NULL
)
256 CcUnpinData(Context
->PageBcb
);
257 Context
->PageBcb
= NULL
;
259 if (!CcMapData(Context
->FileObject
,
260 &Context
->PageOffset
,
264 &Context
->PageBuffer
))
266 Context
->PageOffset
.QuadPart
= 0LL;
267 ExRaiseStatus(STATUS_CANT_WAIT
);
270 Entry
= Add2Ptr(Context
->PageBuffer
, OffsetWithinPage
, PULONG
);
271 /* Next Page Offset */
272 PageOffset
= Context
->PageOffset
.QuadPart
+ PAGE_SIZE
;
273 if (PageOffset
> Context
->BeyoundLastEntryOffset
)
274 PageValidLength
= (SIZE_T
) (Context
->BeyoundLastEntryOffset
275 - Context
->PageOffset
.QuadPart
);
276 BeyoudLastEntry
= Add2Ptr(Context
->PageBuffer
, PageValidLength
, PULONG
);
281 if ((*Entry
& FAT_CLUSTER_LAST
) != ++(*Index
))
282 return (*Entry
& FAT_CLUSTER_LAST
);
283 } while (++Entry
< BeyoudLastEntry
);
284 /* Check if this is the last available entry */
285 if (PageValidLength
< PAGE_SIZE
)
287 /* We are getting beyound current page and
288 * are still in the continous run, map the next page.
290 Context
->PageOffset
.QuadPart
= PageOffset
;
291 CcUnpinData(Context
->PageBcb
);
292 if (!CcMapData(Context
->FileObject
,
293 &Context
->PageOffset
, PAGE_SIZE
, CanWait
,
294 &Context
->PageBcb
, &Context
->PageBuffer
))
296 Context
->PageBcb
= NULL
;
297 Context
->PageOffset
.QuadPart
= 0LL;
298 ExRaiseStatus(STATUS_CANT_WAIT
);
300 Entry
= (PULONG
) Context
->PageBuffer
;
301 /* Next Page Offset */
302 PageOffset
= Context
->PageOffset
.QuadPart
+ PAGE_SIZE
;
303 if (PageOffset
> Context
->BeyoundLastEntryOffset
)
304 PageValidLength
= (SIZE_T
) (Context
->BeyoundLastEntryOffset
305 - Context
->PageOffset
.QuadPart
);
306 BeyoudLastEntry
= Add2Ptr(Context
->PageBuffer
, PageValidLength
, PULONG
);
312 FatSetFat32ContinousRun(IN OUT PFAT_SCAN_CONTEXT Context
,
317 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
321 FatScanFat32ForValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
326 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
330 FatSetFat32ValueRun(IN OUT PFAT_SCAN_CONTEXT Context
,
336 ExRaiseStatus(STATUS_NOT_IMPLEMENTED
);
341 * Queries file MCB for the specified region [Vbo, Vbo + Length],
342 * returns the number of runs in the region as well as the first
343 * run of the range itself.
344 * If the specified region is not fully cached in MCB the routine
345 * scans FAT for the file and fills the MCB until the file offset
346 * (defined as Vbo + Length) is reached.
348 * Fcb = Pointer to FCB structure for the file.
349 * Vbo = Virtual Byte Offset in the file.
350 * Lbo = Receives the Value of Logical Byte offset corresponding
351 * to supplied Vbo Value.
352 * Length = Supplies file range length to be examined and recieves
353 * the length of first run.
354 * OutIndex = Recieves the index (in MCB cache) of first run.
355 * RETURNS: Incremented index of the last run (+1).
356 * NOTES: Should be called by I/O routines to split the I/O operation
357 * into sequential or parallel I/O operations.
360 FatScanFat(IN PFCB Fcb
,
363 IN OUT PLONGLONG Length
,
367 LONGLONG CurrentLbo
, CurrentVbo
, BeyoundLastVbo
, CurrentLength
;
368 ULONG Entry
, NextEntry
, NumberOfEntries
, CurrentIndex
;
369 FAT_SCAN_CONTEXT Context
;
372 /* Some often used values */
375 BeyoundLastVbo
= Vbo
+ *Length
;
376 CurrentLength
= ((LONGLONG
) Vcb
->Clusters
) << Vcb
->BytesPerClusterLog
;
377 if (BeyoundLastVbo
> CurrentLength
)
378 BeyoundLastVbo
= CurrentLength
;
379 /* Try to locate first run */
380 if (FsRtlLookupLargeMcbEntry(&Fcb
->Mcb
, Vbo
, Lbo
, Length
, NULL
, NULL
, Index
))
382 /* Check if we have a single mapped run */
383 if (Vbo
>= BeyoundLastVbo
)
384 goto FatScanFcbFatExit
;
388 /* Get the first scan startup values */
389 if (FsRtlLookupLastLargeMcbEntryAndIndex(
390 &Fcb
->Mcb
, &CurrentVbo
, &CurrentLbo
, &CurrentIndex
))
392 Entry
= FatDataOffsetToEntry(CurrentLbo
, Vcb
);
396 /* Map is empty, set up initial values */
397 Entry
= Fcb
->FirstCluster
;
399 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
400 if (Entry
>= Vcb
->Clusters
)
402 if (Entry
< FAT_CLUSTER_LAST
)
403 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
404 BeyoundLastVbo
= 0LL;
409 RtlZeroMemory(&Context
, sizeof(Context
));
410 Context
.FileObject
= Vcb
->VolumeFileObject
;
411 while (CurrentVbo
< BeyoundLastVbo
)
413 /* Locate Continous run starting with the current entry */
414 NumberOfEntries
= Entry
;
415 NextEntry
= Vcb
->Methods
.ScanContinousRun(
416 &Context
, &NumberOfEntries
, CanWait
);
417 NumberOfEntries
-= Entry
;
418 /* Check value that terminated the for being valid for FAT */
419 if (NextEntry
<= 0x2)
420 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
421 if (NextEntry
>= Vcb
->Clusters
)
423 if (NextEntry
< FAT_CLUSTER_LAST
)
424 ExRaiseStatus(STATUS_FILE_CORRUPT_ERROR
);
428 CurrentLength
= ((LONGLONG
) NumberOfEntries
)
429 << Vcb
->BytesPerClusterLog
;
430 FsRtlAddLargeMcbEntry(&Fcb
->Mcb
,
432 FatEntryToDataOffset(Entry
, Vcb
),
434 /* Setup next iteration */
436 CurrentVbo
+= CurrentLength
;
439 if (*Length
== 0LL && CurrentIndex
> 0)
441 if (!FsRtlLookupLargeMcbEntry(&Fcb
->Mcb
,
442 Vbo
, Lbo
, Length
, NULL
, NULL
, Index
))
454 FatValidBpb(IN PBIOS_PARAMETER_BLOCK Bpb
)
456 return (FatValidBytesPerSector(Bpb
->BytesPerSector
)
457 && FatValidSectorsPerCluster(Bpb
->SectorsPerCluster
)
458 && Bpb
->ReservedSectors
> 0
460 && (Bpb
->Sectors
> 0 || Bpb
->LargeSectors
> 0)
461 && (Bpb
->SectorsPerFat
> 0
462 || (Bpb
->LargeSectorsPerFat
> 0 && Bpb
->FsVersion
== 0))
463 && (Bpb
->Media
== 0xf0
464 || Bpb
->Media
== 0xf8
465 || Bpb
->Media
== 0xf9
466 || Bpb
->Media
== 0xfb
467 || Bpb
->Media
== 0xfc
468 || Bpb
->Media
== 0xfd
469 || Bpb
->Media
== 0xfe
470 || Bpb
->Media
== 0xff)
471 && (Bpb
->SectorsPerFat
== 0 || Bpb
->RootEntries
> 0)
472 && (Bpb
->SectorsPerFat
> 0 || !Bpb
->MirrorDisabled
));
476 FatiInitializeVcb(PVCB Vcb
)
478 ULONG ClustersCapacity
;
480 /* Various characteristics needed for navigation in FAT */
481 if ((Vcb
->Sectors
= Vcb
->Bpb
.Sectors
) == 0)
482 Vcb
->Sectors
= Vcb
->Bpb
.LargeSectors
;
483 if ((Vcb
->SectorsPerFat
= Vcb
->Bpb
.SectorsPerFat
) == 0)
484 Vcb
->SectorsPerFat
= Vcb
->Bpb
.LargeSectorsPerFat
;
485 Vcb
->RootDirent
= Vcb
->Bpb
.ReservedSectors
+ Vcb
->Bpb
.Fats
* Vcb
->SectorsPerFat
;
486 Vcb
->RootDirentSectors
= BytesToSectors(Vcb
,
487 Vcb
->Bpb
.RootEntries
* sizeof(DIR_ENTRY
));
488 Vcb
->DataArea
= Vcb
->RootDirent
+ Vcb
->RootDirentSectors
;
489 Vcb
->Clusters
= (Vcb
->Sectors
- Vcb
->Bpb
.ReservedSectors
490 - Vcb
->Bpb
.Fats
* Vcb
->SectorsPerFat
491 - Vcb
->RootDirentSectors
) / Vcb
->Bpb
.SectorsPerCluster
;
492 if (Vcb
->BytesPerClusterLog
< 4087)
494 Vcb
->IndexDepth
= 0x0c;
495 Vcb
->Methods
= Fat12Methods
;
499 Vcb
->IndexDepth
= 0x10;
500 Vcb
->Methods
= Fat16Methods
;
502 /* Large Sectors are used for FAT32 */
503 if (Vcb
->Bpb
.Sectors
== 0) {
504 Vcb
->IndexDepth
= 0x20;
505 Vcb
->Methods
= Fat32Methods
;
507 ClustersCapacity
= (SectorsToBytes(Vcb
, Vcb
->Sectors
) * 0x8 / Vcb
->IndexDepth
) - 1;
508 if (Vcb
->Clusters
> ClustersCapacity
)
509 Vcb
->Clusters
= ClustersCapacity
;
510 Vcb
->BytesPerCluster
= SectorsToBytes(Vcb
, Vcb
->Bpb
.SectorsPerCluster
);
511 Vcb
->BytesPerClusterLog
= FatPowerOfTwo(Vcb
->BytesPerCluster
);
512 Vcb
->BeyoundLastClusterInFat
= ((LONGLONG
) Vcb
->Clusters
) * Vcb
->IndexDepth
/ 0x8;
516 FatInitializeVcb(IN PVCB Vcb
,
517 IN PDEVICE_OBJECT TargetDeviceObject
,
523 LARGE_INTEGER Offset
;
525 RtlZeroMemory(Vcb
, sizeof(*Vcb
));
527 /* Initialize list head, so that it will
528 * not fail in cleanup.
530 InitializeListHead(&Vcb
->VcbLinks
);
532 /* Setup FCB Header */
533 Vcb
->Header
.NodeTypeCode
= FAT_NTC_VCB
;
534 Vcb
->Header
.NodeByteSize
= sizeof(*Vcb
);
536 /* Setup Vcb fields */
537 Vcb
->TargetDeviceObject
= TargetDeviceObject
;
538 ObReferenceObject(TargetDeviceObject
);
540 /* Setup FCB Header */
541 ExInitializeFastMutex(&Vcb
->HeaderMutex
);
542 FsRtlSetupAdvancedHeader(&Vcb
->Header
, &Vcb
->HeaderMutex
);
544 /* Create Volume File Object */
545 Vcb
->VolumeFileObject
= IoCreateStreamFileObject(NULL
,
546 Vcb
->TargetDeviceObject
);
548 /* We have to setup all FCB fields needed for CC */
549 Vcb
->VolumeFileObject
->FsContext
= Vcb
;
550 Vcb
->VolumeFileObject
->SectionObjectPointer
= &Vcb
->SectionObjectPointers
;
552 /* At least full boot sector should be available */
553 Vcb
->Header
.FileSize
.QuadPart
= sizeof(PACKED_BOOT_SECTOR
);
554 Vcb
->Header
.AllocationSize
.QuadPart
= sizeof(PACKED_BOOT_SECTOR
);
555 Vcb
->Header
.ValidDataLength
.HighPart
= MAXLONG
;
556 Vcb
->Header
.ValidDataLength
.LowPart
= MAXULONG
;
559 CcInitializeCacheMap(Vcb
->VolumeFileObject
,
560 (PCC_FILE_SIZES
)&Vcb
->Header
.AllocationSize
,
562 &FatGlobalData
.CacheMgrNoopCallbacks
,
565 /* Read boot sector */
569 /* Note: Volume Read path does not require
570 * any of the parameters set further
573 if (CcMapData(Vcb
->VolumeFileObject
,
575 sizeof(PACKED_BOOT_SECTOR
),
580 PPACKED_BOOT_SECTOR BootSector
= (PPACKED_BOOT_SECTOR
) Buffer
;
581 FatUnpackBios(&Vcb
->Bpb
, &BootSector
->PackedBpb
);
582 if (!(FatBootSectorJumpValid(BootSector
->Jump
) &&
583 FatValidBpb(&Vcb
->Bpb
)))
585 Status
= STATUS_UNRECOGNIZED_VOLUME
;
587 CopyUchar4(&Vpb
->SerialNumber
, BootSector
->Id
);
592 Status
= STATUS_UNRECOGNIZED_VOLUME
;
593 goto FatInitializeVcbCleanup
;
596 /* Set up notifications */
597 FsRtlNotifyInitializeSync(&Vcb
->NotifySync
);
598 InitializeListHead(&Vcb
->NotifyList
);
600 /* Call helper function */
601 FatiInitializeVcb(Vcb
);
603 /* Add this Vcb to grobal Vcb list. */
604 InsertTailList(&FatGlobalData
.VcbListHead
, &Vcb
->VcbLinks
);
605 return STATUS_SUCCESS
;
607 FatInitializeVcbCleanup
:
609 /* Unwind the routine actions */
610 FatUninitializeVcb(Vcb
);
615 FatUninitializeVcb(IN PVCB Vcb
)
617 LARGE_INTEGER ZeroSize
;
619 ZeroSize
.QuadPart
= 0LL;
621 /* Close volume file */
622 if (Vcb
->VolumeFileObject
!= NULL
)
624 /* Uninitialize CC. */
625 CcUninitializeCacheMap(Vcb
->VolumeFileObject
, &ZeroSize
, NULL
);
626 ObDereferenceObject(Vcb
->VolumeFileObject
);
627 Vcb
->VolumeFileObject
= NULL
;
630 /* Free notifications stuff */
631 FsRtlNotifyUninitializeSync(&Vcb
->NotifySync
);
633 /* Unlink from global Vcb list. */
634 RemoveEntryList(&Vcb
->VcbLinks
);
636 /* Release Target Device */
637 ObDereferenceObject(Vcb
->TargetDeviceObject
);
638 Vcb
->TargetDeviceObject
= NULL
;