HAMMER Update

[Matthew Dillon <dillon@xxxxxxxxxxxxxxxxxxxx>]

    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
    batty.

    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
    extension coded).

    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.

    Whew.

					-Matt
					Matthew Dillon 
					<dillon@backplane.com>