[hfs-user] map node linkage

Patrick Dirks pwd@apple.com
Tue, 5 Oct 2004 22:52:15 -0700

On Oct 5, 2004, at 7:55 AM, Pierre Duhem wrote:

> Hello,
> Still plagued with this "bad map node linkage" (E_MapLk in SVerify2.c)
> The BTMapChk pseudocode is:
> Calculate mapsize ((totalNodes + 7) / 8)
> Walk the map node forward links
>      Do some formal checks
>      Calculate the size of the map in the current node
>      Substract this size from mapsize
>      If no more forward links, break
> If mapsize is not null (the node number being not null is not a
> problem in my case), rise the E_MapLk error.

I believe the idea is that there should, at all times, exist exactly 
enough map nodes to cover the total size of the catalog (or whatever 
B*-Tree is involved, actually) and that they [ the map nodes ] must all 
be properly linked in both directions starting from the header node.  
> That means that it is an error to have several correctly linked map
> nodes to manage the beginning of the catalog, but not enough (yet) to
> manage the whole catalog.

Yes.  Just because nodes are not currently allocated doesn't mean there 
shouldn't be map nodes to describe that state.  For every node in the 
B*-Tree there must be a bit in a bitmap in a header or map node 
somewhere to track its allocated/free state.
> On the other hand, it is not an error to build an empty catalog with
> no map nodes.

I'm not sure what that means; if the catalog is large enough (LOGICAL 
end-of-file, not merely space reserved on disk) then there must be 
enough map nodes.  If the catalog is small, it's perfectly possible 
that the smaller bitmap in the B*-Tree header node will be sufficient 
to cover all blocks.
> That means also that, when you build the first map node outside of the
> B-Tree header, you have to allocate and link all the nodes.

All the MAP nodes, yes.  When you expand the bitmap with a separate 
header node it must be linked to and from the previous map node, which 
may be the B*-Tree header node.
> Am I on the spot, or totally wrong?

Sounds like you're at least on the right track.

Hope that helps,
> Thanks for your comments.
> -- 
> Pierre Duhem
> duhem@macdisk.com