hfs_fs-0.95: hfs_hfind: corrupted b-tree 4
Thu, 21 Jan 1999 17:08:45 -0800
The internal format of HFS disks is described in considerable detail in
Apple's "Inside Macintosh: Files", published by Addison-Wesley. A
must-read if you plan to modify a catalog B*-Tree by hand...
>Corresponding to the '..' directory entry, each group of files
>belonging to the same directory is preceded by a special type of entry
>called a thread entry. It's key is just the ID number of the
>directory, with an empty filename appended. It holds the ID of the
Actually, it holds the complete key by which the directory is known: the
parent's dirID and the name within the parent's directory. It allows the
filesystem to locate the catalog record describing the directory itself
(its mod. date, etc.)
>What appears likely is that one of more "pointers" in the tree have
>become corrupted and so the thread records for the "missing"
>directories are inaccessible. This surely means that the entries for
>at least some of the entries in those directories are also
>inaccessible, but not necessarily ALL of them. It may still be
>possible to access some files or directories in the "missing" ones by
>name, but not by 'ls', 'find', 'du' or anything else which tries to do
>the equivalent of an 'ls' in the "missing" directories. If you know
>the names of files under the "missing" directories, then give it a
The damage can be on two levels: in the B*-Tree itself (an index node
pointing to two subnodes that aren't linked along their forward and
backward links, for instance) or in the structure of the B*-Tree records
(missing thread records for directories, for instance).
Without knowing more I wouldn't speculate on the kind of damage your disk
may have sustained. Machine crashes do different damage than hard disk
bad blocks, for instance.
Locating an object by DirID and Name involves doing a traversal of
successive levels of index nodes in the B*-Tree in order to locate the
leaf node that holds the actual record for the object in question.
Opening a folder involves locating the thread record of that directory
(because it always immediately precedes the record for the first object
in the directory), followed by a traversal of successive forward links to
enumerate the contents of the directory. It is possible to end up in a
situation as described above although the reverse is more common: the
leaf links are intact allowing a directory to be enumerated but, even
though the contents are plainly visible in the Finder window, trying to
do anything to any of them results in a "File Not Found" because the
index node superstructure is corrupted and the file cannot be found by
its ID/Name key.
>In principle the "extents tree", which holds to info on what blocks
>are used by what files, should still know about the files with
>inaccessible catalog entries. If an fsck existed, it would do as
>Michael Knox suggests: find all catalog entries is COULD get to and
>then find al the extents that weren't accounted for by the accesible
>catalog entries and make them into files again, thought there names,
>types, and otehr vital statistics would be lost. This is what Norton
>tries to do too, but I imagine that the catalog tree is too badly
>damaged for it to be able to create any entries for the lost files. I
>think you should assume that is the case any not try to create of
>delete any files or directories on the disk for fear of further
>corrupting the catalog tree.
Unfortunately (from a recovery standpoint) not all extent information is
in the extents B*-Tree. In fact, it's somewhat rare; the first 3 extents
of any file are stored in the catalog record for the file itself. It's
only when a file allocates a fourth extent that extent records are
created in the extents B*-Tree (which is really an extents OVERFLOW
tree). If it helps any, the resource header (in the first block of a
resource fork) contains the file's name and some of the Finder info. You
can tell resource fork extents because there's a flag byte in the extents
B*-Tree key that's different for data fork blocks and resource fork
>My only USEFULL suggestion is to be sure you have the newest Norton
>Utilities for Mac which you can find. There is always the hope that a
>newer version can fix the problem.
That's certainly sound advice. Looking over the remains of a corrupted
hard disk can be educational and fun but the repairs are not for the
faint of heart. I wouldn't dive in without reading some source for
information on the volume format, and the "Inside Macintosh" volume does
a remarkably thorough job.
Hope that helps,