Linux and GC

[P T Withington]

On 4/28/98 18:17, Kragen wrote:

>One particularly interesting garbage-collection method involves copying
>the entire VM of a process, scanning it for garbage while the program
>continues to run, then communicating back to the process what objects
>were discovered to be garbage, so they can be freed.
>
>In Linux (or Unix in general), you can copy the entire VM of a process
>by calling fork().  In Linux, this is fast, because the memory doesn't
>actually get copied until it's written to.  In other Unices, it is
>often not so fast, especially for processes with a lot of data.
>
>This is a way of doing incremental GC that seems to avoid most of the
>hairy problems incremental GC usually has.  The parent and child need
>only share some small communication window though which they can talk
>about garbage; when the child finishes, it can exit.
>
>What are some disadvantages of this method?
>
>Kragen

The "hairy problem" that incremental GC has is that to decide if an 
object is live or dead, you have to trace out all paths from the root of 
the object graph, which is particularly hard to do if the mutator is 
changing the graph while you try to trace it.  The GC can lose a live 
object if the mutator stores a reference to an object the GC has not seen 
into an object the GC has already looked at, and then deletes any other 
references to the first object before the GC sees them.  This object is 
then "in use", but the GC has failed to notice it (because the mutator 
changed the graph behind its back).

What you describe falls into the class of collectors that Wilson 
<ftp://ftp.cs.utexas.edu/pub/garbage/bigsurv.ps> calls 
"Snapshot-at-beginning" collectors.  They prevent the GC from losing any 
objects because the mutator is effectively prevented from ever deleting a 
reference from the graph.

Wilson's paper covers the pros and cons of nearly every known GC 
technique.  In general, Snapshot-at-beginning collectors are efficient 
because they only have to notice mutator writes, which are infrequent 
(and, as you propose, to do a copy-on-write of any page the mutator would 
modify is supported directly in the O/S), but they are inefficient 
because objects that become inaccessible _during_ the collection will not 
be collected (e.g., even if the mutator nulls every pointer to an object, 
if there was one reference to it at the beginning of the collection, it 
will still be preserved).

Most snapshot-at-beginning implementations do not actually make a 
snapshot of the whole image, but rather arrange a write barrier, so that 
any changes to the image can be recorded and dealt with (e.g., by 
recording every value that gets overwritten).

What I find really interesting about your idea is that normally the GC is 
run as a co-routine with the mutator, but in these days of multiple-cpu 
machines, it really makes sense for the GC to be a separately schedulable 
thread.  Incremental collectors use _some_ form of read or write barrier 
to discover the changes that the mutator is making to the graph, but they 
also want the collector to have access to all of the graph.  A thread 
necessarily will have the same VM image as the mutator, but by forking 
the GC as a separate process, it can have a different set of protections 
for its own use.

What looks difficult in your idea is that the list of dead objects to be 
communicated back to the mutator might be large.  In a collector that is 
a co-routine, it is simple for the collector to pop those objects onto a 
free list.  Where your collector is in a separate address space, some 
form of IPC is needed to communicate them back to the mutator.

[GC is my day job]

P. T. Withington, Harlequin Inc., One Cambridge Center, Cambridge MA 02142
Phone: +1 617 374 2557     Fax: +1 617 252 6505    "Honk if you love GC's"
The Memory Management Reference:  <http://www.harlequin.com/mm/reference/>