3 Copyright (c) 1989-2000 Microsoft Corporation
11 This module implements the Path Table support routines for Cdfs.
13 The path table on a CDROM is a condensed summary of the entire
14 directory structure. It is stored on a number of contiguous sectors
15 on the disk. Each directory on the disk has an entry in the path
16 table. The entries are aligned on USHORT boundaries and MAY span
17 sector boundaries. The entries are stored as a breadth-first search.
19 The first entry in the table contains the entry for the root. The
20 next entries will consist of the contents of the root directory. The
21 next entries will consist of the all the directories at the next level
22 of the tree. The children of a given directory will be grouped together.
24 The directories are assigned ordinal numbers based on their position in
25 the path table. The root directory is assigned ordinal value 1.
33 +----------------------------+ +------------------------+
35 DirName | \ | a | b |c| | c | d | e |
37 Parent #| 1 | 1 | 1 | | | 2 | 2 | 3 |
38 +----------------------------+ +------------------------+
54 - Position scan at known offset in the path table. Path Entry at
55 this offset must exist and is known to be valid. Used when
56 scanning for the children of a given directory.
58 - Position scan at known offset in the path table. Path Entry is
59 known to start at this location but the bounds must be checked
62 - Move to next path entry in the table.
64 - Update a common path entry structure with the details of the
65 on-disk structure. This is used to smooth out the differences
66 in the on-disk structures.
68 - Update the filename in the in-memory path entry with the bytes
69 off the disk. For Joliet disks we will have
70 to convert to little endian. We assume that directories
71 don't have version numbers.
79 // The Bug check file id for this module
82 #define BugCheckFileId (CDFS_BUG_CHECK_PATHSUP)
91 // IN PIRP_CONTEXT IrpContext,
92 // IN PPATH_ENUM_CONTEXT PathContext
96 #define CdRawPathEntry(IC, PC) \
97 Add2Ptr( (PC)->Data, (PC)->DataOffset, PRAW_PATH_ENTRY )
100 // Local support routines
104 CdMapPathTableBlock (
105 IN PIRP_CONTEXT IrpContext
,
107 IN LONGLONG BaseOffset
,
108 IN OUT PPATH_ENUM_CONTEXT PathContext
112 CdUpdatePathEntryFromRawPathEntry (
113 IN PIRP_CONTEXT IrpContext
,
115 IN BOOLEAN VerifyBounds
,
116 IN PPATH_ENUM_CONTEXT PathContext
,
117 OUT PPATH_ENTRY PathEntry
121 #pragma alloc_text(PAGE, CdFindPathEntry)
122 #pragma alloc_text(PAGE, CdLookupPathEntry)
123 #pragma alloc_text(PAGE, CdLookupNextPathEntry)
124 #pragma alloc_text(PAGE, CdMapPathTableBlock)
125 #pragma alloc_text(PAGE, CdUpdatePathEntryFromRawPathEntry)
126 #pragma alloc_text(PAGE, CdUpdatePathEntryName)
132 IN PIRP_CONTEXT IrpContext
,
133 IN ULONG PathEntryOffset
,
135 IN BOOLEAN VerifyBounds
,
136 IN OUT PCOMPOUND_PATH_ENTRY CompoundPathEntry
143 This routine is called to initiate a walk through a path table. We are
144 looking for a path table entry at location PathEntryOffset.
148 PathEntryOffset - This is our target point in the Path Table. We know that
149 a path entry must begin at this point although we may have to verify
152 Ordinal - Ordinal number for the directory at the PathEntryOffset above.
154 VerifyBounds - Indicates whether we need to check the validity of
157 CompoundPathEntry - PathEnumeration context and in-memory path entry. This
158 has been initialized outside of this call.
167 PPATH_ENUM_CONTEXT PathContext
= &CompoundPathEntry
->PathContext
;
168 LONGLONG CurrentBaseOffset
;
173 // Compute the starting base and starting path table offset.
176 CurrentBaseOffset
= SectorTruncate( PathEntryOffset
);
179 // Map the next block in the Path Table.
182 CdMapPathTableBlock( IrpContext
,
183 IrpContext
->Vcb
->PathTableFcb
,
188 // Set up our current offset into the Path Context.
191 PathContext
->DataOffset
= PathEntryOffset
- PathContext
->BaseOffset
;
194 // Update the in-memory structure for this path entry.
197 (VOID
) CdUpdatePathEntryFromRawPathEntry( IrpContext
,
200 &CompoundPathEntry
->PathContext
,
201 &CompoundPathEntry
->PathEntry
);
206 CdLookupNextPathEntry (
207 IN PIRP_CONTEXT IrpContext
,
208 IN OUT PPATH_ENUM_CONTEXT PathContext
,
209 IN OUT PPATH_ENTRY PathEntry
216 This routine is called to move to the next path table entry. We know
217 the offset and the length of the current entry. We start by computing
218 the offset of the next entry and determine if it is contained in the
219 table. Then we check to see if we need to move to the next sector in
220 the path table. We always map two sectors at a time so we don't
221 have to deal with any path entries which span sectors. We move to
222 the next sector if we are in the second sector of the current mapped
225 We look up the next entry and update the path entry structure with
226 the values out of the raw sector but don't update the CdName structure.
230 PathContext - Enumeration context for this scan of the path table.
232 PathEntry - In-memory representation of the on-disk path table entry.
236 BOOLEAN - TRUE if another entry is found, FALSE otherwise.
237 This routine may raise on error.
242 LONGLONG CurrentBaseOffset
;
247 // Get the offset of the next path entry within the current
251 PathContext
->DataOffset
+= PathEntry
->PathEntryLength
;
254 // If we are in the last data block then check if we are beyond the
258 if (PathContext
->LastDataBlock
) {
260 if (PathContext
->DataOffset
>= PathContext
->DataLength
) {
266 // If we are not in the last data block of the path table and
267 // this offset is in the second sector then move to the next
271 } else if (PathContext
->DataOffset
>= SECTOR_SIZE
) {
273 CurrentBaseOffset
= PathContext
->BaseOffset
+ SECTOR_SIZE
;
275 CdMapPathTableBlock( IrpContext
,
276 IrpContext
->Vcb
->PathTableFcb
,
281 // Set up our current offset into the Path Context.
284 PathContext
->DataOffset
-= SECTOR_SIZE
;
288 // Now update the path entry with the values from the on-disk
292 return CdUpdatePathEntryFromRawPathEntry( IrpContext
,
293 PathEntry
->Ordinal
+ 1,
302 IN PIRP_CONTEXT IrpContext
,
305 IN BOOLEAN IgnoreCase
,
306 IN OUT PCOMPOUND_PATH_ENTRY CompoundPathEntry
313 This routine will walk through the path table looking for a matching entry for DirName
314 among the child directories of the ParentFcb.
318 ParentFcb - This is the directory we are examining. We know the ordinal and path table
319 offset for this directory in the path table. If this is the first scan for this
320 Fcb we will update the first child offset for this directory in the path table.
322 DirName - This is the name we are searching for. This name will not contain wildcard
323 characters. The name will also not have a version string.
325 IgnoreCase - Indicates if this search is exact or ignore case.
327 CompoundPathEntry - Complete path table enumeration structure. We will have initialized
328 it for the search on entry. This will be positioned at the matching name if found.
332 BOOLEAN - TRUE if matching entry found, FALSE otherwise.
337 BOOLEAN Found
= FALSE
;
338 BOOLEAN UpdateChildOffset
= TRUE
;
340 ULONG StartingOffset
;
341 ULONG StartingOrdinal
;
346 // Position ourselves at either the first child or at the directory itself.
347 // Lock the Fcb to get this value and remember whether to update with the first
351 StartingOffset
= CdQueryFidPathTableOffset( ParentFcb
->FileId
);
352 StartingOrdinal
= ParentFcb
->Ordinal
;
355 // ISO 9660 9.4.4 restricts the backpointer from child to parent in a
356 // pathtable entry to 16bits. Although we internally store ordinals
357 // as 32bit values, it is impossible to search for the children of a
358 // directory whose ordinal value is greater than MAXUSHORT. Media that
359 // could induce such a search is illegal.
361 // Note that it is not illegal to have more than MAXUSHORT directories.
364 if (ParentFcb
->Ordinal
> MAXUSHORT
) {
366 CdRaiseStatus( IrpContext
, STATUS_DISK_CORRUPT_ERROR
);
369 CdLockFcb( IrpContext
, ParentFcb
);
371 if (ParentFcb
->ChildPathTableOffset
!= 0) {
373 StartingOffset
= ParentFcb
->ChildPathTableOffset
;
374 StartingOrdinal
= ParentFcb
->ChildOrdinal
;
375 UpdateChildOffset
= FALSE
;
377 } else if (ParentFcb
== ParentFcb
->Vcb
->RootIndexFcb
) {
379 UpdateChildOffset
= FALSE
;
382 CdUnlockFcb( IrpContext
, ParentFcb
);
384 CdLookupPathEntry( IrpContext
, StartingOffset
, StartingOrdinal
, FALSE
, CompoundPathEntry
);
387 // Loop until we find a match or are beyond the children for this directory.
393 // If we are beyond this directory then return FALSE.
396 if (CompoundPathEntry
->PathEntry
.ParentOrdinal
> ParentFcb
->Ordinal
) {
399 // Update the Fcb with the offsets for the children in the path table.
402 if (UpdateChildOffset
) {
404 CdLockFcb( IrpContext
, ParentFcb
);
406 ParentFcb
->ChildPathTableOffset
= StartingOffset
;
407 ParentFcb
->ChildOrdinal
= StartingOrdinal
;
409 CdUnlockFcb( IrpContext
, ParentFcb
);
416 // If we are within the children of this directory then check for a match.
419 if (CompoundPathEntry
->PathEntry
.ParentOrdinal
== ParentFcb
->Ordinal
) {
422 // Update the child offset if not yet done.
425 if (UpdateChildOffset
) {
427 CdLockFcb( IrpContext
, ParentFcb
);
429 ParentFcb
->ChildPathTableOffset
= CompoundPathEntry
->PathEntry
.PathTableOffset
;
430 ParentFcb
->ChildOrdinal
= CompoundPathEntry
->PathEntry
.Ordinal
;
432 CdUnlockFcb( IrpContext
, ParentFcb
);
434 UpdateChildOffset
= FALSE
;
438 // Update the name in the path entry.
441 CdUpdatePathEntryName( IrpContext
, &CompoundPathEntry
->PathEntry
, IgnoreCase
);
444 // Now compare the names for an exact match.
447 if (CdIsNameInExpression( IrpContext
,
448 &CompoundPathEntry
->PathEntry
.CdCaseDirName
,
454 // Let our caller know we have a match.
463 // Go to the next entry in the path table. Remember the current position
464 // in the event we update the Fcb.
467 StartingOffset
= CompoundPathEntry
->PathEntry
.PathTableOffset
;
468 StartingOrdinal
= CompoundPathEntry
->PathEntry
.Ordinal
;
470 } while (CdLookupNextPathEntry( IrpContext
,
471 &CompoundPathEntry
->PathContext
,
472 &CompoundPathEntry
->PathEntry
));
479 // Local support routine
483 CdMapPathTableBlock (
484 IN PIRP_CONTEXT IrpContext
,
486 IN LONGLONG BaseOffset
,
487 IN OUT PPATH_ENUM_CONTEXT PathContext
494 This routine is called to map (or allocate and copy) the next
495 data block in the path table. We check if the next block will
496 span a view boundary and allocate an auxiliary buffer in that case.
500 Fcb - This is the Fcb for the Path Table.
502 BaseOffset - Offset of the first sector to map. This will be on a
505 PathContext - Enumeration context to update in this routine.
523 // Map the new block and set the enumeration context to this
524 // point. Allocate an auxiliary buffer if necessary.
527 CurrentLength
= 2 * SECTOR_SIZE
;
529 if (CurrentLength
>= (ULONG
) (Fcb
->FileSize
.QuadPart
- BaseOffset
)) {
531 CurrentLength
= (ULONG
) (Fcb
->FileSize
.QuadPart
- BaseOffset
);
534 // We know this is the last data block for this
538 PathContext
->LastDataBlock
= TRUE
;
542 // Set context values.
545 PathContext
->BaseOffset
= (ULONG
) BaseOffset
;
546 PathContext
->DataLength
= CurrentLength
;
549 // Drop the previous sector's mapping
552 CdUnpinData( IrpContext
, &PathContext
->Bcb
);
555 // Check if spanning a view section. The following must
556 // be true before we take this step.
558 // Data length is more than one sector.
559 // Starting offset must be one sector before the
560 // cache manager VACB boundary.
563 if ((CurrentLength
> SECTOR_SIZE
) &&
564 (FlagOn( ((ULONG
) BaseOffset
), VACB_MAPPING_MASK
) == LAST_VACB_SECTOR_OFFSET
)) {
567 // Map each sector individually and store into an auxiliary
571 SectorSize
= SECTOR_SIZE
;
575 PathContext
->Data
= FsRtlAllocatePoolWithTag( CdPagedPool
,
577 TAG_SPANNING_PATH_TABLE
);
578 PathContext
->AllocatedData
= TRUE
;
580 while (PassCount
--) {
582 CcMapData( Fcb
->FileObject
,
583 (PLARGE_INTEGER
) &BaseOffset
,
589 RtlCopyMemory( Add2Ptr( PathContext
->Data
, DataOffset
, PVOID
),
593 CdUnpinData( IrpContext
, &PathContext
->Bcb
);
595 BaseOffset
+= SECTOR_SIZE
;
596 SectorSize
= CurrentLength
- SECTOR_SIZE
;
597 DataOffset
= SECTOR_SIZE
;
601 // Otherwise we can just map the data into the cache.
607 // There is a slight chance that we have allocated an
608 // auxiliary buffer on the previous sector.
611 if (PathContext
->AllocatedData
) {
613 CdFreePool( &PathContext
->Data
);
614 PathContext
->AllocatedData
= FALSE
;
617 CcMapData( Fcb
->FileObject
,
618 (PLARGE_INTEGER
) &BaseOffset
,
622 &PathContext
->Data
);
630 // Local support routine
634 CdUpdatePathEntryFromRawPathEntry (
635 IN PIRP_CONTEXT IrpContext
,
637 IN BOOLEAN VerifyBounds
,
638 IN PPATH_ENUM_CONTEXT PathContext
,
639 OUT PPATH_ENTRY PathEntry
646 This routine is called to update the in-memory Path Entry from the on-disk
647 path entry. We also do a careful check of the bounds if requested and we
648 are in the last data block of the path table.
652 Ordinal - Ordinal number for this directory.
654 VerifyBounds - Check that the current raw Path Entry actually fits
655 within the data block.
657 PathContext - Current path table enumeration context.
659 PathEntry - Pointer to the in-memory path entry structure.
664 FALSE if we've hit the end of the pathtable - zero name length && PT size is a multiple
665 of blocksize. This is a workaround for some Video CDs. Win 9x works around this.
667 This routine may raise.
672 PRAW_PATH_ENTRY RawPathEntry
= CdRawPathEntry( IrpContext
, PathContext
);
673 ULONG RemainingDataLength
;
678 // Check for a name length of zero. This is the first byte of the record,
679 // and there must be at least one byte remaining in the buffer else we
680 // wouldn't be here (caller would have spotted buffer end).
683 PathEntry
->DirNameLen
= CdRawPathIdLen( IrpContext
, RawPathEntry
);
685 if (0 == PathEntry
->DirNameLen
) {
688 // If we are in the last block, and the path table size (ie last block) is a
689 // multiple of block size, then we will consider this the end of the path table
690 // rather than raising an error. Workaround for NTI Cd Maker video CDs which
691 // round path table length to blocksize multiple. In all other cases we consider
692 // a zero length name to be corruption.
695 if ( PathContext
->LastDataBlock
&&
696 (0 == BlockOffset( IrpContext
->Vcb
, PathContext
->DataLength
))) {
701 CdRaiseStatus( IrpContext
, STATUS_DISK_CORRUPT_ERROR
);
705 // Check if we should verify the path entry. If we are not in the last
706 // data block then there is nothing to check.
709 if (PathContext
->LastDataBlock
&& VerifyBounds
) {
712 // Quick check to see if the maximum size is still available. This
713 // will handle most cases and we don't need to access any of the
717 RemainingDataLength
= PathContext
->DataLength
- PathContext
->DataOffset
;
719 if (RemainingDataLength
< sizeof( RAW_PATH_ENTRY
)) {
722 // Make sure the remaining bytes hold the path table entries.
723 // Do the following checks.
725 // - A minimal path table entry will fit (and then check)
726 // - This path table entry (with dir name) will fit.
729 if ((RemainingDataLength
< MIN_RAW_PATH_ENTRY_LEN
) ||
730 (RemainingDataLength
< (ULONG
) (CdRawPathIdLen( IrpContext
, RawPathEntry
) + MIN_RAW_PATH_ENTRY_LEN
- 1))) {
732 CdRaiseStatus( IrpContext
, STATUS_DISK_CORRUPT_ERROR
);
738 // The ordinal number of this directory is passed in.
739 // Compute the path table offset of this entry.
742 PathEntry
->Ordinal
= Ordinal
;
743 PathEntry
->PathTableOffset
= PathContext
->BaseOffset
+ PathContext
->DataOffset
;
746 // We know we can safely access all of the fields of the raw path table at
750 // Bias the disk offset by the number of logical blocks
753 CopyUchar4( &PathEntry
->DiskOffset
, CdRawPathLoc( IrpContext
, RawPathEntry
));
755 PathEntry
->DiskOffset
+= CdRawPathXar( IrpContext
, RawPathEntry
);
757 CopyUchar2( &PathEntry
->ParentOrdinal
, &RawPathEntry
->ParentNum
);
759 PathEntry
->PathEntryLength
= PathEntry
->DirNameLen
+ MIN_RAW_PATH_ENTRY_LEN
- 1;
762 // Align the path entry length on a ushort boundary.
765 PathEntry
->PathEntryLength
= WordAlign( PathEntry
->PathEntryLength
);
767 PathEntry
->DirName
= (PCHAR
)RawPathEntry
->DirId
; /* ReactOS Change: GCC "assignment makes pointer from integer without a cast" */
774 // Local support routine
778 CdUpdatePathEntryName (
779 IN PIRP_CONTEXT IrpContext
,
780 IN OUT PPATH_ENTRY PathEntry
,
781 IN BOOLEAN IgnoreCase
788 This routine will store the directory name into the CdName in the
789 path entry. If this is a Joliet name then we will make sure we have
790 an allocated buffer and need to convert from big endian to little
791 endian. We also correctly update the case name. If this operation is ignore
792 case then we need an auxiliary buffer for the name.
794 For an Ansi disk we can use the name from the disk for the exact case. We only
795 need to allocate a buffer for the ignore case name. The on-disk representation of
796 a Unicode name is useless for us. In this case we will need a name buffer for
797 both names. We store a buffer in the PathEntry which can hold two 8.3 unicode
798 names. This means we will almost never need to allocate a buffer in the Ansi case
799 (we only need one buffer and already have 48 characters).
803 PathEntry - Pointer to a path entry structure. We have already updated
804 this path entry with the values from the raw path entry.
819 // Check if this is a self entry. We use a fixed string for this.
821 // Self-Entry - Length is 1, value is 0.
824 if ((*PathEntry
->DirName
== 0) &&
825 (PathEntry
->DirNameLen
== 1)) {
828 // There should be no allocated buffers.
831 ASSERT( !FlagOn( PathEntry
->Flags
, PATH_ENTRY_FLAG_ALLOC_BUFFER
));
834 // Now use one of the hard coded directory names.
837 PathEntry
->CdDirName
.FileName
= CdUnicodeDirectoryNames
[0];
840 // Show that there is no version number.
843 PathEntry
->CdDirName
.VersionString
.Length
= 0;
846 // The case name is identical.
849 PathEntry
->CdCaseDirName
= PathEntry
->CdDirName
;
859 // Compute how large a buffer we will need. If this is an ignore
860 // case operation then we will want a double size buffer. If the disk is not
861 // a Joliet disk then we might need two bytes for each byte in the name.
864 Length
= PathEntry
->DirNameLen
;
871 if (!FlagOn( IrpContext
->Vcb
->VcbState
, VCB_STATE_JOLIET
)) {
873 Length
*= sizeof( WCHAR
);
877 // Now decide if we need to allocate a new buffer. We will if
878 // this name won't fit in the embedded name buffer and it is
879 // larger than the current allocated buffer. We always use the
880 // allocated buffer if present.
882 // If we haven't allocated a buffer then use the embedded buffer if the data
883 // will fit. This is the typical case.
886 if (!FlagOn( PathEntry
->Flags
, PATH_ENTRY_FLAG_ALLOC_BUFFER
) &&
887 (Length
<= sizeof( PathEntry
->NameBuffer
))) {
889 PathEntry
->CdDirName
.FileName
.MaximumLength
= sizeof( PathEntry
->NameBuffer
);
890 PathEntry
->CdDirName
.FileName
.Buffer
= PathEntry
->NameBuffer
;
895 // We need to use an allocated buffer. Check if the current buffer
899 if (Length
> PathEntry
->CdDirName
.FileName
.MaximumLength
) {
902 // Free any allocated buffer.
905 if (FlagOn( PathEntry
->Flags
, PATH_ENTRY_FLAG_ALLOC_BUFFER
)) {
907 CdFreePool( &PathEntry
->CdDirName
.FileName
.Buffer
);
908 ClearFlag( PathEntry
->Flags
, PATH_ENTRY_FLAG_ALLOC_BUFFER
);
911 PathEntry
->CdDirName
.FileName
.Buffer
= FsRtlAllocatePoolWithTag( CdPagedPool
,
913 TAG_PATH_ENTRY_NAME
);
915 SetFlag( PathEntry
->Flags
, PATH_ENTRY_FLAG_ALLOC_BUFFER
);
917 PathEntry
->CdDirName
.FileName
.MaximumLength
= (USHORT
) Length
;
922 // We now have a buffer for the name. We need to either convert the on-disk bigendian
923 // to little endian or covert the name to Unicode.
926 if (!FlagOn( IrpContext
->Vcb
->VcbState
, VCB_STATE_JOLIET
)) {
928 Status
= RtlOemToUnicodeN( PathEntry
->CdDirName
.FileName
.Buffer
,
929 PathEntry
->CdDirName
.FileName
.MaximumLength
,
932 PathEntry
->DirNameLen
);
934 ASSERT( Status
== STATUS_SUCCESS
);
935 PathEntry
->CdDirName
.FileName
.Length
= (USHORT
) Length
;
940 // Convert this string to little endian.
943 CdConvertBigToLittleEndian( IrpContext
,
945 PathEntry
->DirNameLen
,
946 (PCHAR
) PathEntry
->CdDirName
.FileName
.Buffer
);
948 PathEntry
->CdDirName
.FileName
.Length
= (USHORT
) PathEntry
->DirNameLen
;
952 // There is no version string.
955 PathEntry
->CdDirName
.VersionString
.Length
=
956 PathEntry
->CdCaseDirName
.VersionString
.Length
= 0;
959 // If the name string ends with a period then knock off the last
963 if (PathEntry
->CdDirName
.FileName
.Buffer
[(PathEntry
->CdDirName
.FileName
.Length
- sizeof( WCHAR
)) / 2] == L
'.') {
966 // Shrink the filename length.
969 PathEntry
->CdDirName
.FileName
.Length
-= sizeof( WCHAR
);
973 // Update the case name buffer if necessary. If this is an exact case
974 // operation then just copy the exact case string.
979 PathEntry
->CdCaseDirName
.FileName
.Buffer
= Add2Ptr( PathEntry
->CdDirName
.FileName
.Buffer
,
980 PathEntry
->CdDirName
.FileName
.MaximumLength
/ 2,
983 PathEntry
->CdCaseDirName
.FileName
.MaximumLength
= PathEntry
->CdDirName
.FileName
.MaximumLength
/ 2;
985 CdUpcaseName( IrpContext
,
986 &PathEntry
->CdDirName
,
987 &PathEntry
->CdCaseDirName
);
991 PathEntry
->CdCaseDirName
= PathEntry
->CdDirName
;