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?
The B-trees keep track of which nodes are used and which are free by using one or more map records. These map records are just a bitmap, much like the one that is used to keep track of used/free allocation blocks. The first map record is in the B-tree header node (node #0). If the B-tree contains more nodes than there are bits in the header node's map record, then there will be additional map nodes which each contain a single map record. The header node and map nodes form a singly linked list, using the forward link field (the first four bytes of the node). If your B-tree is large enough (has enough nodes), then you definitely do need to create the linked list of map nodes at format time. Similarly, you may have to add map nodes to the end of the linked list if you grow the B-tree (if it now has more nodes than the existing map nodes can track).
It should be OK to create more map nodes than your B-tree strictly needs. I don't think Mac OS X will complain, but third party repair utilities might. Note that Mac OS X will only grow, never shrink, a B-tree.
Some things to verify: * The linked list uses the forward link field in the node header. This is the first four bytes of the node. It should contain the node number of the next node in the linked list, stored in big endian (network) byte order. The forward link of the last node in the linked list should be zero. * The backward link (bytes 4-7 of the node) should be zero. * The node type (byte 8) is 1 for the header node, or 2 for the map nodes. * The node height (byte 9) should be zero for both the header node and map nodes. * The number of records (bytes 10-11) of the map nodes should be set to 1 (again, in big endian, so 00 01). * Bytes 12-13 of the nodes should be zeroes. * The offsets at the end of the node are in the opposite order of the keys in the node. For example, the offsets for HFS (node size = 512) would be the bytes 01 FC 00 0E. The offset (0x000E) for the first record is at the end of the node; the offset for the next record (0x01FC, free space) comes just before that; and so on. * On HFS Plus, the size of a map record must be a multiple of 4 bytes. Since the node header is 14 bytes (not a multiple of 4), and there are two record offsets (4 bytes), there will be two free bytes between the map record and record offsets in a map node. That is, the second offset (the offset to free space) will be the node size minus 6 (bytes xx FA). * Don't forget to mark the header node and any map nodes as in use in the map record(s).
If that doesn't help you figure out the problem, let me know.
By the way, if you want to experiment with how Mac OS X formats volumes, try using disk images. You can use sparse disk images to create volumes much larger than you have physical space for. For example, here's how I created a sparse image of an 80GB HFS Plus volume, with an extents B-tree containing 10,000 nodes, with a node size of 1024:
% hdiutil create -size 80g -type SPARSE -layout NONE myhfs Initializing... Creating... Finishing... created: /Users/mark/myhfs.sparseimage % hdiutil attach -nomount myhfs.sparseimage Initializing... Attaching... Finishing... Finishing... /dev/disk2 % newfs_hfs -n e=1024 -c e=10000 /dev/disk2 Initialized /dev/rdisk2 as a 80 GB HFS Plus volume
Here's a hex dump showing that volume's extents B-tree:
Here's the header node: 00281000 00 00 00 01 00 00 00 00 01 00 00 03 00 00 00 00 |................| 00281010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| 00281020 04 00 00 0a 00 00 9c 40 00 00 9c 3a 00 00 02 71 |.......@...:...q| 00281030 00 00 00 00 00 00 00 02 00 00 00 00 00 00 00 00 |................| 00281040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 002810f0 00 00 00 00 00 00 00 00 fc 00 00 00 00 00 00 00 |................| 00281100 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 002813f0 00 00 00 00 00 00 00 00 03 f8 00 f8 00 78 00 0e |.............x..| The first map node: 00281400 00 00 00 02 00 00 00 00 02 00 00 01 00 00 00 00 |................| 00281410 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 002817f0 00 00 00 00 00 00 00 00 00 00 00 00 03 fa 00 0e |................| Next map node... 00281800 00 00 00 03 00 00 00 00 02 00 00 01 00 00 00 00 |................| 00281810 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00281bf0 00 00 00 00 00 00 00 00 00 00 00 00 03 fa 00 0e |................| 00281c00 00 00 00 04 00 00 00 00 02 00 00 01 00 00 00 00 |................| 00281c10 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 00281ff0 00 00 00 00 00 00 00 00 00 00 00 00 03 fa 00 0e |................| 00282000 00 00 00 05 00 00 00 00 02 00 00 01 00 00 00 00 |................| 00282010 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 002823f0 00 00 00 00 00 00 00 00 00 00 00 00 03 fa 00 0e |................| 00282400 00 00 00 00 00 00 00 00 02 00 00 01 00 00 00 00 |................| 00282410 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................| * 002827f0 00 00 00 00 00 00 00 00 00 00 00 00 03 fa 00 0e |................|
-Mark