Linux and GC
P T Withington
Tue, 12 May 1998 15:21:53 -0400
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?
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
"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/>