[hfs-user] Map nodes linked list

Pierre Duhem Pierre Duhem <lsduhem@duhem.com>
Fri, 30 Apr 2004 18:41:14 +0200


PD> On Apr 29, 2004, at 11:40 PM, Pierre Duhem wrote:

>> Patrick,
>> PD> On Apr 29, 2004, at 7:25 AM, Pierre Duhem wrote:
>>>> Hello,
>>>> I didn't like very much the code I had to check for an overflow of
>>>> the
>>>> binary table used in the Extents and Catalog B-trees for the node
>>>> allocation.
>>>> Therefore, I had the idea to build this list when formatting
>> PD> Of course, even THAT could eventually still overflow...
>> Of course, But it is definitively easier to build this linked list
>> from scratch, when your tree is still empty.

PD> I don't really see why.  Why don't you have a look at the hfs code?
PD> When the bitmap's full and the B*-Tree is extended it just allocates a
PD> new node, updates the header to point to it, and initializes it with a
PD> map data structure.  No problem, and completely confined to the B*-Tree
PD> expansion code.  The "allocate-a-node" logic doesn't directly need to
PD> be involved.

If it happens that you have to create a map node at a moment where you
don't have any free room in the binary table of the tree header (for
instance), you are in a catch-22. You need the map node to allocate
the node and you need a node to register the newly allocated node.

>>>> I followed the specs and built a simply linked list from the tree
>>>> header. All nodes are empty, with only the downward pointer,
>> PD> What do you mean by this?  IIRC correctly, the map nodes are linked
>> PD> back and forth via the usual forward/backward link fields in the
>> node
>> PD> header?  Of course, for the definitive word look to Mark's recently
>> PD> updated tech note!
>> The map nodes list is not doubly linked, and has only forward
>> (downward) links. The last node has 00 00 00 00 in the first four
>> bytes, which could be interpreted as a link back to the node 0 (tree
>> header), btw.
>>>>  the 2 as
>>>> node kind, a 1 since there is a single entry and the two offsets at
>>>> the end, 00 0E for the binary table and 01 FC (in the case of a HFS
>>>> node) pointing to itself.
>>>> But Mac OS X doesn't seem to like my idea, refuses to mount even an
>>>> empty volume, as soon as there is a map node linked list.
>> PD> Have you tried running fsck_hfs from a command-line shell with the
>> "-d"
>> PD> option (along with -f if necessary - see 'man fsck_hfs') to see
>> what it
>> PD> generates?
>> My code runs on a PC, under Windows ;-)).

PD> Nevertheless, examining your disks on a Mac would be a good debugging
PD> tool!  If you can't use an external drive like a FireWire drive to
PD> practice on, create a disk image of whatever size you like (I believe
PD> .dmg files are just block-for-block copies of the device - nothing
PD> special) and transfer that to a Mac somehow.

Of course. I have a Mac running Mac OS X.2 to do my checks. And I use
Norton v. 8 to do the checks, as well as the Disk Utility. As a matter
of fact, I use a Zip 100 for little volumes and two FireWire Maxtor of
40 and 250GB for bigger tests.

The point is that you can't manage to have to up to date programming
computers with all necessary tools correctly set. If I had some Unix
culture, this would definitively be easier, but I don't ;-)).

Thanks for writing.

Best Regards
Pierre Duhem
Logiciels & Services Duhem, Paris (France)