Disk Forwarding Hairball

[Mark S. Miller <vlad!mark>]

Problem: We discovered and solved a nasty hairball that comes from
the combination of: 1) allowing flocks to migrate and leave forwarders
behind, and 2) insisting that stubs be canonical.  A stub for the
original location and a stub for the new location of a migrated object
can simultaneously exist in memory, and when they get faulted in, the
C++ become operation can't connect all the pointers.  

Solution: When creating a ShepherdStub (at the edge of a flock), first
check whether there are any already existing shepherd/stubs have the
same hash value.  If so, fault them in.  If the resulting object is
actually the object that the stub would point to, then just return a
pointer to it.  Note that this algorithm actually needs to be more
symetrical because both stubs might point at forwarders.

Since all shepherds use sequence numbers for their hashes, the actual
incidence of true hash collisions between different objects will be
very low.  We typically only drag things in from disk when they are
actually pointers to the same object.  Even then, we can stop dragging
in flocks as soon as we know that the two stubs would point to the
same object.

The hash table for finding other objects with the same hash already
exists to canonicalize the stubs.

This can cause an arbitrary number of reads (bounded by the length of
forwarder chains), but URDI doesn't get overwhelmed by too many reads.
The other problem is running out of core.  If every object had the
same hash (the extreme case :-), then each flock brought in would
require resolving the hash conflicts between its stubs, which requires
bringing in more objects, recursively....  The trivial solution is to
not actually image objects brought in for location resolution but to
stop as soon as we know whether two stubs are identical or not.

what fun ...
dean and markm