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