[hfs-user] Map nodes linked list

Pierre Duhem Pierre Duhem <lsduhem@duhem.com>
Fri, 30 Apr 2004 09:29:15 +0200


Mark,


MD> 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 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. I
>> followed the specs and built a simply linked list from the tree
>> header. All nodes are empty, with only the downward pointer, 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.
>>
>> Who should build this list? Is it against the rule to build an empty
>> node list?

MD> The B-trees keep track of which nodes are used and which are free by
MD> using one or more map records.  These map records are just a bitmap,
MD> much like the one that is used to keep track of used/free allocation
MD> blocks.  The first map record is in the B-tree header node (node #0).
MD> If the B-tree contains more nodes than there are bits in the header
MD> node's map record, then there will be additional map nodes which each
MD> contain a single map record.  The header node and map nodes form a
MD> singly linked list, using the forward link field (the first four bytes
MD> of the node).  If your B-tree is large enough (has enough nodes), then
MD> you definitely do need to create the linked list of map nodes at format
MD> time.

OK. This is also what I thought. It is definitively simpler to do it a
formatting time.

MD> Similarly, you may have to add map nodes to the end of the
MD> linked list if you grow the B-tree (if it now has more nodes than the
MD> existing map nodes can track).

MD> It should be OK to create more map nodes than your B-tree strictly
MD> needs.  I don't think Mac OS X will complain, but third party repair
MD> utilities might.  Note that Mac OS X will only grow, never shrink, a
MD> B-tree.

MD> Some things to verify:
MD> * The linked list uses the forward link field in the node header.  This
MD> is the first four bytes of the node.  It should contain the node number
MD> of the next node in the linked list, stored in big endian (network)
MD> byte order.  The forward link of the last node in the linked list 
MD> should be zero.
MD> * The backward link (bytes 4-7 of the node) should be zero.
MD> * The node type (byte 8) is 1 for the header node, or 2 for the map
MD> nodes.
MD> * The node height (byte 9) should be zero for both the header node and
MD> map nodes.
MD> * The number of records (bytes 10-11) of the map nodes should be set to
MD> 1 (again, in big endian, so 00 01).
MD> * Bytes 12-13 of the nodes should be zeroes.
MD> * The offsets at the end of the node are in the opposite order of the
MD> keys in the node.  For example, the offsets for HFS (node size = 512)
MD> would be the bytes 01 FC 00 0E.  The offset (0x000E) for the first
MD> record is at the end of the node; the offset for the next record 
MD> (0x01FC, free space) comes just before that; and so on.
MD> * On HFS Plus, the size of a map record must be a multiple of 4 bytes.
MD> Since the node header is 14 bytes (not a multiple of 4), and there are
MD> two record offsets (4 bytes), there will be two free bytes between the
MD> map record and record offsets in a map node.  That is, the second 
MD> offset (the offset to free space) will be the node size minus 6 (bytes
MD> xx FA).

Thanks for pointing me at this. My code was wrong. I'll correct it.

MD> * Don't forget to mark the header node and any map nodes as in use in
MD> the map record(s).

I already did it.

MD> If that doesn't help you figure out the problem, let me know.

MD> By the way, if you want to experiment with how Mac OS X formats 
MD> volumes, try using disk images.  You can use sparse disk images to
MD> create volumes much larger than you have physical space for.  For 
MD> example, here's how I created a sparse image of an 80GB HFS Plus 
MD> volume, with an extents B-tree containing 10,000 nodes, with a node
MD> size of 1024:

Thanks. Bus, as I said in another message, I do all this on a PC under
Windows.

When the system tries to mount my disk (40GB, formatted as HFS), it
aborts with an error, and the Disk utility, when asked to check
the disk, displays (retranslated from the French):
Testing Extents Overflow File
Invalid Map Node link.
This disk must be repaired (but the Repare button remains greyed).

Norton Disk Doctor (v. 8) hangs somewhere, without any message.

On the other hand, since it was childish to try to format such big
disks in plain HFS (I now automatically switch to HFS+ from 4GB),
the problem will disappear, but I'm not quite satisfied.

-- 
Best Regards
Pierre Duhem
Logiciels & Services Duhem, Paris (France)
duhem@macdisk.com