[gclist] Re: gclist-digest V1 #68

[Marc Shapiro]

 || From: giuliano@ix.netcom.com (Giuliano Carlini)
 || Date: Wed, 5 Jun 1996 12:23:29 -0700
 || Subject: [gclist] Collecting distributed cyclic garbage.
 || 
 || I hope that posting it to the list is within the list's charter.

I'm glad you started this discussion.  Distributed GC is a hot topic but
hasn't really been discussed here yet.

 || Back-Searching to Collect Distributed Cyclic Garbage.

Sorry to disappoint you, but I've seen this before, lots of times.  Can't
give you a reference though.  You've added a number of nice features though.

 || 	- It should be relatively efficient. It should be O(n) where n is
 || 		the size of a cycle.

In order to find any garbage, it must examine every object that *might* be on
a cycle (your zombies).  Starting from these objects, it examines every object
that is reachable [in your case, reachable backwards] from this point.  If
there are n zombies, and the average number of objects reachable from a zombie
is m, the cost is O(n*m).

 || When a stub is no longer reclaimed by the local collector, it sends a
 || delete message to its scion.

This does not tolerate lost messages.  Instead, each space periodically sends
the list of scions reachable from its own stubs, to every other space; any
scion not appearing on this list is deleted.  This is safe and live even when
messages are lost.  (It's somewhat inefficient, but this basic protocol can be
optimized; I won't get into that.)

 || A zombie is: Locally unreachable.  The target of at least one scion.  Not
 || recently mentioned by an RPC.

You only need to consider scions for zombies.  (A locally unreachable object is
garbage anyway unless it is reachable from a scion.)

 || Distributed cycles are collected by finding zombies, and searching
 || transitively backwards through the objects which reference the zombie
 || looking for an object which is locally reachable. If there is no such
 || object, the zombie is unreachable. It and all its ancestors can be
 || reclaimed.

Why search *backwards*?  You get the same amount of information by going
forwards: if by going forward you get back to where you started, and have
encountered no locally-reachable objects, then the path you took MIGHT be a
cycle of garbage.

I say "might", because you must take into account: (i) all possible paths,
and (ii) concurrent mutator activity.

Following pointers backwards can be done, but it costs orders of magnitude
more costly than forwards.

 || Only two requirements are imposed on [the local collector] by the
 || distributed collector. First, it must clear the remotely visible mark bit
 || of the objects it retains.

More precisely: the local collector first marks or copies from local roots,
setting the RV bit OFF; then from the scions, setting the RV bit ON.  Since
it never marks the same object twice, the RV bits are correct.

 || If a back search cycles back to a zombie, then the zombie is not live
 || along that path.

Careful here!  If the mutator is running concurrently, then this sentence is
incorrect!  Fortunately you do not make the mistake of believing yourself,
since you implement a write barrier to detect changes in the midst of a
search.

 || Whenever a stub has been scanned, the space is notified that new scions
 || should be marked dirty. If the dirty scion is the first for the target,

This bit is confusing. "Whenever a stub has been scanned" is the same as "all
the time" since stubs are being scanned continuously.  "If the dirty scion is
the first for the target...": how can it not be, if there is a 1-to-1
correspondence between stubs and scions?

How about trying a figure?  It's very hard to read through all the details of
your text.  I know figures are difficult to draw with ASCII but it can be
done...

                                                Marc