[hfs-user] Map nodes linked list

Patrick Dirks pwd@apple.com
Fri, 30 Apr 2004 08:00:39 -0700

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.

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

Nevertheless, examining your disks on a Mac would be a good debugging 
tool!  If you can't use an external drive like a FireWire drive to 
practice on, create a disk image of whatever size you like (I believe 
.dmg files are just block-for-block copies of the device - nothing 
special) and transfer that to a Mac somehow.
>>> Who should build this list? Is it against the rule to build an empty
>>> node list?
> PD> It's unusual but I believe this would be no different than how a 
> volume
> PD> would look if the B*-Tree had been grown a lot and then the nodes 
> freed
> PD> up, right?  It'd still have a map node linked to the header but the
> PD> bitmap field would be empty, so I'd think it SHOULD be OK.  I bet
> PD> there's some other field tripping you up.
> Surely. I'll check again.
> -- 
> Best Regards
> Pierre Duhem
> Logiciels & Services Duhem, Paris (France)
> duhem@macdisk.com