[hfs-user] map node linkage
Tue, 5 Oct 2004 22:52:15 -0700
On Oct 5, 2004, at 7:55 AM, Pierre Duhem wrote:
> 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