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.