Patrick,
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.