[hfs-user] Map nodes linked list

Pierre Duhem Pierre Duhem <lsduhem@duhem.com>
Fri, 30 Apr 2004 08:40:37 +0200


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 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 ;-)).

>> 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)