[hfs-user] Map nodes linked list
Fri, 30 Apr 2004 08:00:39 -0700
On Apr 29, 2004, at 11:40 PM, Pierre Duhem wrote:
> PD> On Apr 29, 2004, at 7:25 AM, Pierre Duhem wrote:
>>> I didn't like very much the code I had to check for an overflow of
>>> binary table used in the Extents and Catalog B-trees for the node
>>> 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
>>> 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
> 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
> 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
> PD> would look if the B*-Tree had been grown a lot and then the nodes
> 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)