[hfs-user] Map nodes linked list

Mark Day mday@apple.com
Thu, 29 Apr 2004 11:21:43 -0700


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