3 Copyright (c) 1990-2000 Microsoft Corporation
11 This module implements the Allocation support routines for Cdfs.
13 The data structure used here is the CD_MCB. There is an entry in
14 the Mcb for each dirent for a file. The entry will map the offset
15 within some file to a starting disk offset and number of bytes.
16 The Mcb also contains the interleave information for an extent.
17 An interleave consists of a number of blocks with data and a
18 (possibly different) number of blocks to skip. Any number of
19 data/skip pairs may exist in an extent but the data and skip sizes
20 are the same throughout the extent.
22 We store the following information into an Mcb entry for an extent.
24 FileOffset Offset in file for start of extent
25 DiskOffset Offset on disk for start of extent
26 ByteCount Number of file bytes in extent, no skip bytes
27 DataBlockByteCount Number of bytes in each data block
28 TotalBlockByteCount Number of bytes is data block and skip block
30 The disk offset in the Mcb has already been biased by the size of
31 the Xar block if present. All of the byte count fields are aligned
32 on logical block boundaries. If this is a directory or path table
33 then the file offset has been biased to round the initial disk
34 offset down to a sector boundary. The biasing is done when loading
35 the values into an Mcb entry.
37 An XA file has a header prepended to the file and each sector is 2352
38 bytes. The allocation information ignores the header and only deals
39 with 2048 byte sectors. Callers into the allocation package have
40 adjusted the starting offset value to reflect 2048 sectors. On return
41 from this package the caller will have to convert from 2048 sector values
42 into raw XA sector values.
50 // The Bug check file id for this module
53 #define BugCheckFileId (CDFS_BUG_CHECK_ALLOCSUP)
56 // Local support routines
61 _In_ PIRP_CONTEXT IrpContext
,
63 _In_ LONGLONG FileOffset
67 CdDiskOffsetFromMcbEntry (
68 _In_ PIRP_CONTEXT IrpContext
,
69 _In_ PCD_MCB_ENTRY McbEntry
,
70 _In_ LONGLONG FileOffset
,
71 _Out_ PLONGLONG DiskOffset
,
72 _Out_ PULONG ByteCount
76 #pragma alloc_text(PAGE, CdAddInitialAllocation)
77 #pragma alloc_text(PAGE, CdAddAllocationFromDirent)
78 #pragma alloc_text(PAGE, CdDiskOffsetFromMcbEntry)
79 #pragma alloc_text(PAGE, CdFindMcbEntry)
80 #pragma alloc_text(PAGE, CdInitializeMcb)
81 #pragma alloc_text(PAGE, CdLookupAllocation)
82 #pragma alloc_text(PAGE, CdTruncateAllocation)
83 #pragma alloc_text(PAGE, CdUninitializeMcb)
87 _Requires_lock_held_(_Global_critical_region_
)
90 // PREFast currently has no way to express the Fcb==Fcb->Vcb->VolumeDasdFcb early return
91 #pragma warning(suppress: 6001 6101)
94 _In_ PIRP_CONTEXT IrpContext
,
96 _In_ LONGLONG FileOffset
,
97 _Out_ PLONGLONG DiskOffset
,
98 _Out_ PULONG ByteCount
105 This routine looks through the mapping information for the file
106 to find the logical diskoffset and number of bytes at that offset.
107 We only deal with logical 2048 byte sectors here.
109 If the mapping isn't present we will look it up on disk now.
110 This routine assumes we are looking up a valid range in the file. This
111 routine raises if it can't find mapping for the file offset.
113 The Fcb may not be locked prior to calling this routine. We will always
118 Fcb - Fcb representing this stream.
120 FileOffset - Lookup the allocation beginning at this point.
122 DiskOffset - Address to store the logical disk offset.
124 ByteCount - Address to store the number of contiguous bytes beginning
134 BOOLEAN FirstPass
= TRUE
;
135 ULONG McbEntryOffset
;
136 PFCB ParentFcb
= NULL
;
137 BOOLEAN CleanupParent
= FALSE
;
139 BOOLEAN UnlockFcb
= FALSE
;
141 LONGLONG CurrentFileOffset
;
142 ULONG CurrentMcbOffset
;
143 PCD_MCB_ENTRY CurrentMcbEntry
;
145 DIRENT_ENUM_CONTEXT DirContext
= {0};
150 ASSERT_IRP_CONTEXT( IrpContext
);
154 // For DASD IO we already have clamped the read to the volume limits.
155 // We'll allow reading beyond those limits for extended DASD IO, so
156 // no MCB lookup here.
159 if (Fcb
== Fcb
->Vcb
->VolumeDasdFcb
) {
161 *DiskOffset
= FileOffset
;
166 // Use a try finally to facilitate cleanup.
172 // We use a loop to perform the lookup. If we don't find the mapping in the
173 // first pass then we look up all of the allocation and then look again.
179 // Lookup the entry containing this file offset.
182 CdLockFcb( IrpContext
, Fcb
);
185 McbEntryOffset
= CdFindMcbEntry( IrpContext
, Fcb
, FileOffset
);
188 // If within the Mcb then we use the data out of this entry and are
192 if (McbEntryOffset
< Fcb
->Mcb
.CurrentEntryCount
) {
194 CdDiskOffsetFromMcbEntry( IrpContext
,
195 Fcb
->Mcb
.McbArray
+ McbEntryOffset
,
203 // If this is not the first pass then the disk is corrupt.
206 } else if (!FirstPass
) {
208 CdRaiseStatus( IrpContext
, STATUS_DISK_CORRUPT_ERROR
);
211 CdUnlockFcb( IrpContext
, Fcb
);
215 // Initialize the search dirent structures.
218 CdInitializeDirContext( IrpContext
, &DirContext
);
219 CdInitializeDirent( IrpContext
, &Dirent
);
222 // Otherwise we need to walk the dirents for this file until we find
223 // the one containing this entry. The parent Fcb should always be
227 ParentFcb
= Fcb
->ParentFcb
;
228 CdAcquireFileShared( IrpContext
, ParentFcb
);
229 CleanupParent
= TRUE
;
232 // Do an unsafe test to see if we need to create a file object.
235 CdVerifyOrCreateDirStreamFile( IrpContext
, ParentFcb
);
238 // Initialize the local variables to indicate the first dirent
239 // and lookup the first dirent.
242 CurrentFileOffset
= 0;
243 CurrentMcbOffset
= 0;
245 CdLookupDirent( IrpContext
,
247 CdQueryFidDirentOffset( Fcb
->FileId
),
251 // If we are adding allocation to the Mcb then add all of it.
257 // Update the dirent from the on-disk dirent.
260 CdUpdateDirentFromRawDirent( IrpContext
, ParentFcb
, &DirContext
, &Dirent
);
263 // Add this dirent to the Mcb if not already present.
266 CdLockFcb( IrpContext
, Fcb
);
269 if (CurrentMcbOffset
>= Fcb
->Mcb
.CurrentEntryCount
) {
271 CdAddAllocationFromDirent( IrpContext
, Fcb
, CurrentMcbOffset
, CurrentFileOffset
, &Dirent
);
274 CdUnlockFcb( IrpContext
, Fcb
);
278 // If this is the last dirent for the file then exit.
281 if (!FlagOn( Dirent
.DirentFlags
, CD_ATTRIBUTE_MULTI
)) {
287 // If we couldn't find another entry then the directory is corrupt because
288 // the last dirent for a file doesn't exist.
291 if (!CdLookupNextDirent( IrpContext
, ParentFcb
, &DirContext
, &DirContext
)) {
293 CdRaiseStatus( IrpContext
, STATUS_DISK_CORRUPT_ERROR
);
297 // Update our loop variables.
300 CurrentMcbEntry
= Fcb
->Mcb
.McbArray
+ CurrentMcbOffset
;
301 CurrentFileOffset
+= CurrentMcbEntry
->ByteCount
;
302 CurrentMcbOffset
+= 1;
306 // All of the allocation is loaded. Go back and look up the mapping again.
307 // It better be there this time.
318 // Release the parent and cleanup the dirent structures.
321 CdReleaseFile( IrpContext
, ParentFcb
);
323 CdCleanupDirContext( IrpContext
, &DirContext
);
324 CdCleanupDirent( IrpContext
, &Dirent
);
327 if (UnlockFcb
) { CdUnlockFcb( IrpContext
, Fcb
); }
335 CdAddAllocationFromDirent (
336 _In_ PIRP_CONTEXT IrpContext
,
338 _In_ ULONG McbEntryOffset
,
339 _In_ LONGLONG StartingFileOffset
,
347 This routine is called to add an entry into the Cd Mcb. We grow the Mcb
348 as necessary and update the new entry.
350 NOTE - The Fcb has already been locked prior to makeing this call.
354 Fcb - Fcb containing the Mcb to update.
356 McbEntryOffset - Offset into the Mcb array to add this data.
358 StartingFileOffset - Offset in bytes from the start of the file.
360 Dirent - Dirent containing the on-disk data for this entry.
371 PCD_MCB_ENTRY McbEntry
;
375 UNREFERENCED_PARAMETER( IrpContext
);
377 ASSERT_IRP_CONTEXT( IrpContext
);
379 ASSERT_LOCKED_FCB( Fcb
);
382 // If we need to grow the Mcb then do it now.
385 if (McbEntryOffset
>= Fcb
->Mcb
.MaximumEntryCount
) {
388 // Allocate a new buffer and copy the old data over.
391 NewArraySize
= Fcb
->Mcb
.MaximumEntryCount
* 2 * sizeof( CD_MCB_ENTRY
);
393 NewMcbArray
= FsRtlAllocatePoolWithTag( CdPagedPool
,
397 RtlZeroMemory( NewMcbArray
, NewArraySize
);
398 RtlCopyMemory( NewMcbArray
,
400 Fcb
->Mcb
.MaximumEntryCount
* sizeof( CD_MCB_ENTRY
));
403 // Deallocate the current array unless it is embedded in the Fcb.
406 if (Fcb
->Mcb
.MaximumEntryCount
!= 1) {
408 CdFreePool( &Fcb
->Mcb
.McbArray
);
412 // Now update the Mcb with the new array.
415 Fcb
->Mcb
.MaximumEntryCount
*= 2;
416 Fcb
->Mcb
.McbArray
= NewMcbArray
;
420 // Update the new entry with the input data.
423 McbEntry
= Fcb
->Mcb
.McbArray
+ McbEntryOffset
;
426 // Start with the location and length on disk.
429 McbEntry
->DiskOffset
= LlBytesFromBlocks( Fcb
->Vcb
, Dirent
->StartingOffset
);
430 McbEntry
->ByteCount
= Dirent
->DataLength
;
433 // Round the byte count up to a logical block boundary if this is
437 if (!FlagOn( Dirent
->DirentFlags
, CD_ATTRIBUTE_MULTI
)) {
439 McbEntry
->ByteCount
= BlockAlign( Fcb
->Vcb
, McbEntry
->ByteCount
);
443 // The file offset is the logical position within this file.
444 // We know this is correct regardless of whether we bias the
445 // file size or disk offset.
448 McbEntry
->FileOffset
= StartingFileOffset
;
451 // Convert the interleave information from logical blocks to
455 if (Dirent
->FileUnitSize
!= 0) {
457 McbEntry
->DataBlockByteCount
= LlBytesFromBlocks( Fcb
->Vcb
, Dirent
->FileUnitSize
);
458 McbEntry
->TotalBlockByteCount
= McbEntry
->DataBlockByteCount
+
459 LlBytesFromBlocks( Fcb
->Vcb
, Dirent
->InterleaveGapSize
);
462 // If the file is not interleaved then the size of the data block
463 // and total block are the same as the byte count.
468 McbEntry
->DataBlockByteCount
=
469 McbEntry
->TotalBlockByteCount
= McbEntry
->ByteCount
;
473 // Update the number of entries in the Mcb. The Mcb is never sparse
474 // so whenever we add an entry it becomes the last entry in the Mcb.
477 Fcb
->Mcb
.CurrentEntryCount
= McbEntryOffset
+ 1;
484 CdAddInitialAllocation (
485 _In_ PIRP_CONTEXT IrpContext
,
487 _In_ ULONG StartingBlock
,
488 _In_ LONGLONG DataLength
495 This routine is called to set up the initial entry in an Mcb.
497 This routine handles the single initial entry for a directory file. We will
498 round the start block down to a sector boundary. Our caller has already
499 biased the DataLength with any adjustments. This is used for the case
500 where there is a single entry and we want to align the data on a sector
505 Fcb - Fcb containing the Mcb to update.
507 StartingBlock - Starting logical block for this directory. This is
508 the start of the actual data. We will bias this by the sector
511 DataLength - Length of the data.
520 PCD_MCB_ENTRY McbEntry
;
524 UNREFERENCED_PARAMETER( IrpContext
);
526 ASSERT_IRP_CONTEXT( IrpContext
);
528 ASSERT_LOCKED_FCB( Fcb
);
529 NT_ASSERT( 0 == Fcb
->Mcb
.CurrentEntryCount
);
530 NT_ASSERT( CDFS_NTC_FCB_DATA
!= Fcb
->NodeTypeCode
);
533 // Update the new entry with the input data.
536 McbEntry
= Fcb
->Mcb
.McbArray
;
539 // Start with the location and length on disk.
542 McbEntry
->DiskOffset
= LlBytesFromBlocks( Fcb
->Vcb
, StartingBlock
);
543 McbEntry
->DiskOffset
-= Fcb
->StreamOffset
;
545 McbEntry
->ByteCount
= DataLength
;
548 // The file offset is the logical position within this file.
549 // We know this is correct regardless of whether we bias the
550 // file size or disk offset.
553 McbEntry
->FileOffset
= 0;
556 // If the file is not interleaved then the size of the data block
557 // and total block are the same as the byte count.
560 McbEntry
->DataBlockByteCount
=
561 McbEntry
->TotalBlockByteCount
= McbEntry
->ByteCount
;
564 // Update the number of entries in the Mcb. The Mcb is never sparse
565 // so whenever we add an entry it becomes the last entry in the Mcb.
568 Fcb
->Mcb
.CurrentEntryCount
= 1;
575 CdTruncateAllocation (
576 _In_ PIRP_CONTEXT IrpContext
,
578 _In_ LONGLONG StartingFileOffset
585 This routine truncates the Mcb for a file by eliminating all of the Mcb
586 entries from the entry which contains the given offset.
588 The Fcb should be locked when this routine is called.
592 Fcb - Fcb containing the Mcb to truncate.
594 StartingFileOffset - Offset in the file to truncate the Mcb from.
603 ULONG McbEntryOffset
;
607 ASSERT_IRP_CONTEXT( IrpContext
);
609 ASSERT_LOCKED_FCB( Fcb
);
612 // Find the entry containg this starting offset.
615 McbEntryOffset
= CdFindMcbEntry( IrpContext
, Fcb
, StartingFileOffset
);
618 // Now set the current size of the mcb to this point.
621 Fcb
->Mcb
.CurrentEntryCount
= McbEntryOffset
;
627 _At_(Fcb
->NodeByteSize
, _In_range_(>=, FIELD_OFFSET( FCB
, FcbType
)))
630 _In_ PIRP_CONTEXT IrpContext
,
631 _Inout_updates_bytes_(Fcb
->NodeByteSize
) PFCB Fcb
638 This routine is called to initialize the Mcb in an Fcb. We initialize
639 this with an entry count of one and point to the entry in the Fcb
642 Fcb should be acquired exclusively when this is called.
646 Fcb - Fcb containing the Mcb to initialize.
657 UNREFERENCED_PARAMETER( IrpContext
);
659 ASSERT_IRP_CONTEXT( IrpContext
);
663 // Set the entry counts to show there is one entry in the array and
667 Fcb
->Mcb
.MaximumEntryCount
= 1;
668 Fcb
->Mcb
.CurrentEntryCount
= 0;
670 Fcb
->Mcb
.McbArray
= &Fcb
->McbEntry
;
676 _At_(Fcb
->NodeByteSize
, _In_range_(>=, FIELD_OFFSET( FCB
, FcbType
)))
677 _When_(Fcb
->NodeTypeCode
== CDFS_NTC_FCB_PATH_TABLE
, _At_(Fcb
->NodeByteSize
, _In_range_(==, SIZEOF_FCB_INDEX
)))
678 _When_(Fcb
->NodeTypeCode
== CDFS_NTC_FCB_INDEX
, _At_(Fcb
->NodeByteSize
, _In_range_(==, SIZEOF_FCB_INDEX
)))
679 _When_(Fcb
->NodeTypeCode
== CDFS_NTC_FCB_DATA
, _At_(Fcb
->NodeByteSize
, _In_range_(==, SIZEOF_FCB_DATA
)))
682 _In_ PIRP_CONTEXT IrpContext
,
683 _Inout_updates_bytes_(Fcb
->NodeByteSize
) PFCB Fcb
690 This routine is called to cleanup an Mcb in an Fcb. We look at the
691 maximum run count in the Fcb and if greater than one we will deallocate
694 Fcb should be acquired exclusively when this is called.
698 Fcb - Fcb containing the Mcb to uninitialize.
709 UNREFERENCED_PARAMETER( IrpContext
);
711 ASSERT_IRP_CONTEXT( IrpContext
);
715 // If the count is greater than one then this is an allocated buffer.
718 if (Fcb
->Mcb
.MaximumEntryCount
> 1) {
720 CdFreePool( &Fcb
->Mcb
.McbArray
);
728 // Local suupport routine
733 _In_ PIRP_CONTEXT IrpContext
,
735 _In_ LONGLONG FileOffset
742 This routine is called to find the Mcb entry which contains the file
743 offset at the given point. If the file offset is not currently in the
744 Mcb then we return the offset of the entry to add.
746 Fcb should be locked when this is called.
750 Fcb - Fcb containing the Mcb to uninitialize.
752 FileOffset - Return the Mcb entry which contains this file offset.
756 ULONG - Offset in the Mcb of the entry for this offset.
761 ULONG CurrentMcbOffset
;
762 PCD_MCB_ENTRY CurrentMcbEntry
;
766 UNREFERENCED_PARAMETER( IrpContext
);
768 ASSERT_IRP_CONTEXT( IrpContext
);
770 ASSERT_LOCKED_FCB( Fcb
);
773 // We expect a linear search will be sufficient here.
776 CurrentMcbOffset
= 0;
777 CurrentMcbEntry
= Fcb
->Mcb
.McbArray
;
779 while (CurrentMcbOffset
< Fcb
->Mcb
.CurrentEntryCount
) {
782 // Check if the offset lies within the current Mcb position.
785 if (FileOffset
< CurrentMcbEntry
->FileOffset
+ CurrentMcbEntry
->ByteCount
) {
791 // Move to the next entry.
794 CurrentMcbOffset
+= 1;
795 CurrentMcbEntry
+= 1;
799 // This is the offset containing this file offset (or the point
800 // where an entry should be added).
803 return CurrentMcbOffset
;
808 // Local support routine
812 CdDiskOffsetFromMcbEntry (
813 _In_ PIRP_CONTEXT IrpContext
,
814 _In_ PCD_MCB_ENTRY McbEntry
,
815 _In_ LONGLONG FileOffset
,
816 _Out_ PLONGLONG DiskOffset
,
817 _Out_ PULONG ByteCount
824 This routine is called to return the diskoffset and length of the file
825 data which begins at offset 'FileOffset'. We have the Mcb entry which
826 contains the mapping and interleave information.
828 NOTE - This routine deals with data in 2048 byte logical sectors. If
829 this is an XA file then our caller has already converted from
830 'raw' file bytes to 'cooked' file bytes.
834 McbEntry - Entry in the Mcb containing the allocation information.
836 FileOffset - Starting Offset in the file to find the matching disk
839 DiskOffset - Address to store the starting disk offset for this operation.
841 ByteCount - Address to store number of contiguous bytes starting at this
851 LONGLONG ExtentOffset
;
853 LONGLONG CurrentDiskOffset
;
854 LONGLONG CurrentExtentOffset
;
856 LONGLONG LocalByteCount
;
860 UNREFERENCED_PARAMETER( IrpContext
);
862 ASSERT_IRP_CONTEXT( IrpContext
);
865 // Extent offset is the difference between the file offset and the start
869 ExtentOffset
= FileOffset
- McbEntry
->FileOffset
;
872 // Optimize the non-interleave case.
875 if (McbEntry
->ByteCount
== McbEntry
->DataBlockByteCount
) {
877 *DiskOffset
= McbEntry
->DiskOffset
+ ExtentOffset
;
879 LocalByteCount
= McbEntry
->ByteCount
- ExtentOffset
;
884 // Walk though any interleave until we reach the current offset in
888 CurrentExtentOffset
= McbEntry
->DataBlockByteCount
;
889 CurrentDiskOffset
= McbEntry
->DiskOffset
;
891 while (CurrentExtentOffset
<= ExtentOffset
) {
893 CurrentDiskOffset
+= McbEntry
->TotalBlockByteCount
;
894 CurrentExtentOffset
+= McbEntry
->DataBlockByteCount
;
898 // We are now positioned at the data block containing the starting
899 // file offset we were given. The disk offset is the offset of
900 // the start of this block plus the extent offset into this block.
901 // The byte count is the data block byte count minus our offset into
905 *DiskOffset
= CurrentDiskOffset
+ (ExtentOffset
+ McbEntry
->DataBlockByteCount
- CurrentExtentOffset
);
908 // Make sure we aren't past the end of the data length. This is possible
909 // if we only use part of the last data block on an interleaved file.
912 if (CurrentExtentOffset
> McbEntry
->ByteCount
) {
914 CurrentExtentOffset
= McbEntry
->ByteCount
;
917 LocalByteCount
= CurrentExtentOffset
- ExtentOffset
;
921 // If the byte count exceeds our limit then cut it to fit in 32 bits.
924 if (LocalByteCount
> MAXULONG
) {
926 *ByteCount
= MAXULONG
;
930 *ByteCount
= (ULONG
) LocalByteCount
;