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 IN PLONGLONG DiskOffset
,
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)
89 IN PIRP_CONTEXT IrpContext
,
91 IN LONGLONG FileOffset
,
92 OUT PLONGLONG DiskOffset
,
100 This routine looks through the mapping information for the file
101 to find the logical diskoffset and number of bytes at that offset.
102 We only deal with logical 2048 byte sectors here.
104 If the mapping isn't present we will look it up on disk now.
105 This routine assumes we are looking up a valid range in the file. This
106 routine raises if it can't find mapping for the file offset.
108 The Fcb may not be locked prior to calling this routine. We will always
113 Fcb - Fcb representing this stream.
115 FileOffset - Lookup the allocation beginning at this point.
117 DiskOffset - Address to store the logical disk offset.
119 ByteCount - Address to store the number of contiguous bytes beginning
129 BOOLEAN FirstPass
= TRUE
;
130 ULONG McbEntryOffset
;
131 PFCB ParentFcb
= NULL
; /* ReactOS Change: GCC uninitialized variable bug */
132 BOOLEAN CleanupParent
= FALSE
;
134 BOOLEAN UnlockFcb
= FALSE
;
136 LONGLONG CurrentFileOffset
;
137 ULONG CurrentMcbOffset
;
138 PCD_MCB_ENTRY CurrentMcbEntry
;
140 DIRENT_ENUM_CONTEXT DirContext
;
145 ASSERT_IRP_CONTEXT( IrpContext
);
149 // Use a try finally to facilitate cleanup.
155 // We use a loop to perform the lookup. If we don't find the mapping in the
156 // first pass then we look up all of the allocation and then look again.
162 // Lookup the entry containing this file offset.
165 CdLockFcb( IrpContext
, Fcb
);
168 McbEntryOffset
= CdFindMcbEntry( IrpContext
, Fcb
, FileOffset
);
171 // If within the Mcb then we use the data out of this entry and are
175 if (McbEntryOffset
< Fcb
->Mcb
.CurrentEntryCount
) {
177 CdDiskOffsetFromMcbEntry( IrpContext
,
178 Fcb
->Mcb
.McbArray
+ McbEntryOffset
,
186 // If this is not the first pass then the disk is corrupt.
189 } else if (!FirstPass
) {
191 CdRaiseStatus( IrpContext
, STATUS_DISK_CORRUPT_ERROR
);
194 CdUnlockFcb( IrpContext
, Fcb
);
198 // Initialize the search dirent structures.
201 CdInitializeDirContext( IrpContext
, &DirContext
);
202 CdInitializeDirent( IrpContext
, &Dirent
);
205 // Otherwise we need to walk the dirents for this file until we find
206 // the one containing this entry. The parent Fcb should always be
210 ParentFcb
= Fcb
->ParentFcb
;
211 CdAcquireFileShared( IrpContext
, ParentFcb
);
212 CleanupParent
= TRUE
;
215 // Do an unsafe test to see if we need to create a file object.
218 if (ParentFcb
->FileObject
== NULL
) {
220 CdCreateInternalStream( IrpContext
, ParentFcb
->Vcb
, ParentFcb
);
224 // Initialize the local variables to indicate the first dirent
225 // and lookup the first dirent.
228 CurrentFileOffset
= 0;
229 CurrentMcbOffset
= 0;
231 CdLookupDirent( IrpContext
,
233 CdQueryFidDirentOffset( Fcb
->FileId
),
237 // If we are adding allocation to the Mcb then add all of it.
243 // Update the dirent from the on-disk dirent.
246 CdUpdateDirentFromRawDirent( IrpContext
, ParentFcb
, &DirContext
, &Dirent
);
249 // Add this dirent to the Mcb if not already present.
252 CdLockFcb( IrpContext
, Fcb
);
255 if (CurrentMcbOffset
>= Fcb
->Mcb
.CurrentEntryCount
) {
257 CdAddAllocationFromDirent( IrpContext
, Fcb
, CurrentMcbOffset
, CurrentFileOffset
, &Dirent
);
260 CdUnlockFcb( IrpContext
, Fcb
);
264 // If this is the last dirent for the file then exit.
267 if (!FlagOn( Dirent
.DirentFlags
, CD_ATTRIBUTE_MULTI
)) {
273 // If we couldn't find another entry then the directory is corrupt because
274 // the last dirent for a file doesn't exist.
277 if (!CdLookupNextDirent( IrpContext
, ParentFcb
, &DirContext
, &DirContext
)) {
279 CdRaiseStatus( IrpContext
, STATUS_DISK_CORRUPT_ERROR
);
283 // Update our loop variables.
286 CurrentMcbEntry
= Fcb
->Mcb
.McbArray
+ CurrentMcbOffset
;
287 CurrentFileOffset
+= CurrentMcbEntry
->ByteCount
;
288 CurrentMcbOffset
+= 1;
292 // All of the allocation is loaded. Go back and look up the mapping again.
293 // It better be there this time.
304 // Release the parent and cleanup the dirent structures.
307 CdReleaseFile( IrpContext
, ParentFcb
);
309 CdCleanupDirContext( IrpContext
, &DirContext
);
310 CdCleanupDirent( IrpContext
, &Dirent
);
313 if (UnlockFcb
) { CdUnlockFcb( IrpContext
, Fcb
); }
321 CdAddAllocationFromDirent (
322 IN PIRP_CONTEXT IrpContext
,
324 IN ULONG McbEntryOffset
,
325 IN LONGLONG StartingFileOffset
,
333 This routine is called to add an entry into the Cd Mcb. We grow the Mcb
334 as necessary and update the new entry.
336 NOTE - The Fcb has already been locked prior to makeing this call.
340 Fcb - Fcb containing the Mcb to update.
342 McbEntryOffset - Offset into the Mcb array to add this data.
344 StartingFileOffset - Offset in bytes from the start of the file.
346 Dirent - Dirent containing the on-disk data for this entry.
357 PCD_MCB_ENTRY McbEntry
;
361 ASSERT_IRP_CONTEXT( IrpContext
);
363 ASSERT_LOCKED_FCB( Fcb
);
366 // If we need to grow the Mcb then do it now.
369 if (McbEntryOffset
>= Fcb
->Mcb
.MaximumEntryCount
) {
372 // Allocate a new buffer and copy the old data over.
375 NewArraySize
= Fcb
->Mcb
.MaximumEntryCount
* 2 * sizeof( CD_MCB_ENTRY
);
377 NewMcbArray
= FsRtlAllocatePoolWithTag( CdPagedPool
,
381 RtlZeroMemory( NewMcbArray
, NewArraySize
);
382 RtlCopyMemory( NewMcbArray
,
384 Fcb
->Mcb
.MaximumEntryCount
* sizeof( CD_MCB_ENTRY
));
387 // Deallocate the current array unless it is embedded in the Fcb.
390 if (Fcb
->Mcb
.MaximumEntryCount
!= 1) {
392 CdFreePool( &Fcb
->Mcb
.McbArray
);
396 // Now update the Mcb with the new array.
399 Fcb
->Mcb
.MaximumEntryCount
*= 2;
400 Fcb
->Mcb
.McbArray
= NewMcbArray
;
404 // Update the new entry with the input data.
407 McbEntry
= Fcb
->Mcb
.McbArray
+ McbEntryOffset
;
410 // Start with the location and length on disk.
413 McbEntry
->DiskOffset
= LlBytesFromBlocks( Fcb
->Vcb
, Dirent
->StartingOffset
);
414 McbEntry
->ByteCount
= Dirent
->DataLength
;
417 // Round the byte count up to a logical block boundary if this is
421 if (!FlagOn( Dirent
->DirentFlags
, CD_ATTRIBUTE_MULTI
)) {
423 McbEntry
->ByteCount
= BlockAlign( Fcb
->Vcb
, McbEntry
->ByteCount
);
427 // The file offset is the logical position within this file.
428 // We know this is correct regardless of whether we bias the
429 // file size or disk offset.
432 McbEntry
->FileOffset
= StartingFileOffset
;
435 // Convert the interleave information from logical blocks to
439 if (Dirent
->FileUnitSize
!= 0) {
441 McbEntry
->DataBlockByteCount
= LlBytesFromBlocks( Fcb
->Vcb
, Dirent
->FileUnitSize
);
442 McbEntry
->TotalBlockByteCount
= McbEntry
->DataBlockByteCount
+
443 LlBytesFromBlocks( Fcb
->Vcb
, Dirent
->InterleaveGapSize
);
446 // If the file is not interleaved then the size of the data block
447 // and total block are the same as the byte count.
452 McbEntry
->DataBlockByteCount
=
453 McbEntry
->TotalBlockByteCount
= McbEntry
->ByteCount
;
457 // Update the number of entries in the Mcb. The Mcb is never sparse
458 // so whenever we add an entry it becomes the last entry in the Mcb.
461 Fcb
->Mcb
.CurrentEntryCount
= McbEntryOffset
+ 1;
468 CdAddInitialAllocation (
469 IN PIRP_CONTEXT IrpContext
,
471 IN ULONG StartingBlock
,
472 IN LONGLONG DataLength
479 This routine is called to set up the initial entry in an Mcb.
481 This routine handles the single initial entry for a directory file. We will
482 round the start block down to a sector boundary. Our caller has already
483 biased the DataLength with any adjustments. This is used for the case
484 where there is a single entry and we want to align the data on a sector
489 Fcb - Fcb containing the Mcb to update.
491 StartingBlock - Starting logical block for this directory. This is
492 the start of the actual data. We will bias this by the sector
495 DataLength - Length of the data.
504 PCD_MCB_ENTRY McbEntry
;
508 ASSERT_IRP_CONTEXT( IrpContext
);
510 ASSERT_LOCKED_FCB( Fcb
);
511 ASSERT( 0 == Fcb
->Mcb
.CurrentEntryCount
);
512 ASSERT( CDFS_NTC_FCB_DATA
!= Fcb
->NodeTypeCode
);
515 // Update the new entry with the input data.
518 McbEntry
= Fcb
->Mcb
.McbArray
;
521 // Start with the location and length on disk.
524 McbEntry
->DiskOffset
= LlBytesFromBlocks( Fcb
->Vcb
, StartingBlock
);
525 McbEntry
->DiskOffset
-= Fcb
->StreamOffset
;
527 McbEntry
->ByteCount
= DataLength
;
530 // The file offset is the logical position within this file.
531 // We know this is correct regardless of whether we bias the
532 // file size or disk offset.
535 McbEntry
->FileOffset
= 0;
538 // If the file is not interleaved then the size of the data block
539 // and total block are the same as the byte count.
542 McbEntry
->DataBlockByteCount
=
543 McbEntry
->TotalBlockByteCount
= McbEntry
->ByteCount
;
546 // Update the number of entries in the Mcb. The Mcb is never sparse
547 // so whenever we add an entry it becomes the last entry in the Mcb.
550 Fcb
->Mcb
.CurrentEntryCount
= 1;
557 CdTruncateAllocation (
558 IN PIRP_CONTEXT IrpContext
,
560 IN LONGLONG StartingFileOffset
567 This routine truncates the Mcb for a file by eliminating all of the Mcb
568 entries from the entry which contains the given offset.
570 The Fcb should be locked when this routine is called.
574 Fcb - Fcb containing the Mcb to truncate.
576 StartingFileOffset - Offset in the file to truncate the Mcb from.
585 ULONG McbEntryOffset
;
589 ASSERT_IRP_CONTEXT( IrpContext
);
591 ASSERT_LOCKED_FCB( Fcb
);
594 // Find the entry containing this starting offset.
597 McbEntryOffset
= CdFindMcbEntry( IrpContext
, Fcb
, StartingFileOffset
);
600 // Now set the current size of the mcb to this point.
603 Fcb
->Mcb
.CurrentEntryCount
= McbEntryOffset
;
611 IN PIRP_CONTEXT IrpContext
,
619 This routine is called to initialize the Mcb in an Fcb. We initialize
620 this with an entry count of one and point to the entry in the Fcb
623 Fcb should be acquired exclusively when this is called.
627 Fcb - Fcb containing the Mcb to initialize.
638 ASSERT_IRP_CONTEXT( IrpContext
);
642 // Set the entry counts to show there is one entry in the array and
646 Fcb
->Mcb
.MaximumEntryCount
= 1;
647 Fcb
->Mcb
.CurrentEntryCount
= 0;
649 Fcb
->Mcb
.McbArray
= &Fcb
->McbEntry
;
657 IN PIRP_CONTEXT IrpContext
,
665 This routine is called to cleanup an Mcb in an Fcb. We look at the
666 maximum run count in the Fcb and if greater than one we will deallocate
669 Fcb should be acquired exclusively when this is called.
673 Fcb - Fcb containing the Mcb to uninitialize.
684 ASSERT_IRP_CONTEXT( IrpContext
);
688 // If the count is greater than one then this is an allocated buffer.
691 if (Fcb
->Mcb
.MaximumEntryCount
> 1) {
693 CdFreePool( &Fcb
->Mcb
.McbArray
);
701 // Local support routine
706 IN PIRP_CONTEXT IrpContext
,
708 IN LONGLONG FileOffset
715 This routine is called to find the Mcb entry which contains the file
716 offset at the given point. If the file offset is not currently in the
717 Mcb then we return the offset of the entry to add.
719 Fcb should be locked when this is called.
723 Fcb - Fcb containing the Mcb to uninitialize.
725 FileOffset - Return the Mcb entry which contains this file offset.
729 ULONG - Offset in the Mcb of the entry for this offset.
734 ULONG CurrentMcbOffset
;
735 PCD_MCB_ENTRY CurrentMcbEntry
;
739 ASSERT_IRP_CONTEXT( IrpContext
);
741 ASSERT_LOCKED_FCB( Fcb
);
744 // We expect a linear search will be sufficient here.
747 CurrentMcbOffset
= 0;
748 CurrentMcbEntry
= Fcb
->Mcb
.McbArray
;
750 while (CurrentMcbOffset
< Fcb
->Mcb
.CurrentEntryCount
) {
753 // Check if the offset lies within the current Mcb position.
756 if (FileOffset
< CurrentMcbEntry
->FileOffset
+ CurrentMcbEntry
->ByteCount
) {
762 // Move to the next entry.
765 CurrentMcbOffset
+= 1;
766 CurrentMcbEntry
+= 1;
770 // This is the offset containing this file offset (or the point
771 // where an entry should be added).
774 return CurrentMcbOffset
;
779 // Local support routine
783 CdDiskOffsetFromMcbEntry (
784 IN PIRP_CONTEXT IrpContext
,
785 IN PCD_MCB_ENTRY McbEntry
,
786 IN LONGLONG FileOffset
,
787 IN PLONGLONG DiskOffset
,
795 This routine is called to return the diskoffset and length of the file
796 data which begins at offset 'FileOffset'. We have the Mcb entry which
797 contains the mapping and interleave information.
799 NOTE - This routine deals with data in 2048 byte logical sectors. If
800 this is an XA file then our caller has already converted from
801 'raw' file bytes to 'cooked' file bytes.
805 McbEntry - Entry in the Mcb containing the allocation information.
807 FileOffset - Starting Offset in the file to find the matching disk
810 DiskOffset - Address to store the starting disk offset for this operation.
812 ByteCount - Address to store number of contiguous bytes starting at this
822 LONGLONG ExtentOffset
;
824 LONGLONG CurrentDiskOffset
;
825 LONGLONG CurrentExtentOffset
;
827 LONGLONG LocalByteCount
;
830 ASSERT_IRP_CONTEXT( IrpContext
);
833 // Extent offset is the difference between the file offset and the start
837 ExtentOffset
= FileOffset
- McbEntry
->FileOffset
;
840 // Optimize the non-interleave case.
843 if (McbEntry
->ByteCount
== McbEntry
->DataBlockByteCount
) {
845 *DiskOffset
= McbEntry
->DiskOffset
+ ExtentOffset
;
847 LocalByteCount
= McbEntry
->ByteCount
- ExtentOffset
;
852 // Walk though any interleave until we reach the current offset in
856 CurrentExtentOffset
= McbEntry
->DataBlockByteCount
;
857 CurrentDiskOffset
= McbEntry
->DiskOffset
;
859 while (CurrentExtentOffset
<= ExtentOffset
) {
861 CurrentDiskOffset
+= McbEntry
->TotalBlockByteCount
;
862 CurrentExtentOffset
+= McbEntry
->DataBlockByteCount
;
866 // We are now positioned at the data block containing the starting
867 // file offset we were given. The disk offset is the offset of
868 // the start of this block plus the extent offset into this block.
869 // The byte count is the data block byte count minus our offset into
873 *DiskOffset
= CurrentDiskOffset
+ (ExtentOffset
+ McbEntry
->DataBlockByteCount
- CurrentExtentOffset
);
876 // Make sure we aren't past the end of the data length. This is possible
877 // if we only use part of the last data block on an interleaved file.
880 if (CurrentExtentOffset
> McbEntry
->ByteCount
) {
882 CurrentExtentOffset
= McbEntry
->ByteCount
;
885 LocalByteCount
= CurrentExtentOffset
- ExtentOffset
;
889 // If the byte count exceeds our limit then cut it to fit in 32 bits.
892 if (LocalByteCount
> MAXULONG
) {
894 *ByteCount
= MAXULONG
;
898 *ByteCount
= (ULONG
) LocalByteCount
;