dillon at apollo.backplane.com
Thu Nov 1 14:08:54 PDT 2007
I will be continuing to commit bits and pieces of HAMMER, but note
that it will probably not even begin to work for quite some time.
I am still on track for it to make it into the end-of-year release.
Mostly I just needed to clear my plate (my source working set) to keep
track of the various major segments of the work without going completely
Only the A-list code is reasonably well tested so far, because
newfs_hammer uses the same code. The B-Tree code cannot be tested until
I get more of the VFS infrastructure in place. I expect that to be
fairly straight-forward since I will be able to do a lot of testing
with a one-cluster filesystem (i.e. without the B-Tree cluster
The most difficult piece in the entire design is the B-Tree deletion code
and that is now coded. I decided to go with a forward-iteration for both
insertions AND deletions, which is THE most difficult B-Tree algorithm to
implement. But the huge advantage is that I will be able to remove
the cluster lock in the future and lock B-Tree nodes as I go down without
getting into deadlock situations, which is very SMP friendly.
My B-Tree implementation also allows HAMMER to cache B-Tree nodes
and start lookups from any internal node rather then having to start at
the root. You can do this in a standard B-Tree too but it isn't
necessarily efficient for certain boundary cases. In my implementation
I store boundaries for the left AND right side which means a search
starting in the middle of the tree knows exactly where to go and will
never have to retrace its steps.
<dillon at backplane.com>
More information about the Kernel