RE: GC "survey"

[Nick Trout <Nick.Trout@...>]

> -----Original Message-----
> From: Thatcher Ulrich [mailto:tu@tulrich.com]
> Sent: 27 August 2002 18:37
> To: Multiple recipients of list
> Subject: Re: GC "survey"
> 
> 
> On Aug 27, 2002 at 09:53 -0300, Roberto Ierusalimschy wrote:
> > > The idea is to keep separate lists for each type of object (thus
> > > eliminating the vtype variable) and not storing an 
> explicit "marked"
> > > value -- instead, the marked status is determined by 
> which list the
> > > object is linked into (white, gray, or black).
> > 
> > Are you sure you can do that? You need a fast way to check the color
> > of an object while running the mutator.
> 
> Actually, I don't think you do -- IIRC with this algorithm, whenever
> you need to mark an object and you don't know its color, it's always
> correct to put it on the gray list.
> 
> That's just my recollection from the last time I worked on this, which
> was several months ago, so I could be mistaken.

---8<----

(note) For a tracing collector (marking or copying), one conceptually
colours the data white (not yet seen by the collector), black (alive and
scanned by the collector) and grey (alive but not yet scanned by the
collector). The collector proceeds by scanning grey objects for pointers to
white objects. The white objects found are turned grey, and the grey objects
scanned are turned black. When there are no more grey objects, the
collection is complete and all the white objects can be recycled. 

---8<----

Source: http://www.iecc.com/gclist/GC-algorithms.html#Variations

Link is on the wiki: http://lua-users.org/wiki/GarbageCollection





write barrier
read barrier

A write barrier is a mechanism for executing some memory management code
when a write to some object takes place (that object is then "behind the
write barrier", or - informally - "write barrier-ed", or - sloppily -
"write-protected"). It can take the form of inlined code (if memory
management is integral to the compiler), or a memory-protection fault which
is handled by the memory management code. There are also "read barriers",
the nature of which is obvious. 
The roles a write barrier can play in GC are a little trickier to explain to
a novice, but I'll give it a stab. 

Consider a simple generational stop-and-collect collector, such as the one
which SML/NJ used to have. "Generational" means that data is partitioned
into old and new. This partition is useful to the GC for two reasons: (a)
because data tends to die young, collecting just new data will probably free
a lot of space, and (b) because pointers tend to point from new objects to
old objects, and not vice versa, it is cheap to find all the pointers to new
objects. 
Property (b) is only true if you can tell when a pointer to a new object has
been written into an old object. Otherwise you have to scan all the old
objects to find pointers to new objects, which loses one of the main
advantages of generational GC. So you put the old data behind a write
barrier, and record those writes. When you come to GC the new data, you know
the only pointers from old to new are those which you have recorded. 

Consider a tracing GC (see note below) which is incremental or concurrent,
i.e. the user's program (the 'mutator') can run before the GC is complete.
Now there is an invariant: black objects do not point to white objects. If
the mutator writes a white pointer into a black object, this invariant is
broken and the GC can fail. There are two basic solutions: prevent the
mutator from seeing white objects ("read barriers") or prevent the mutator
from writing white pointers into black objects ("write barriers"). The write
barrier solution puts the black objects behind a write barrier. When a
white-on-black write takes place there are various fixes: incrementally grey
the white object, regrey the black object, &c. 
(note) For a tracing collector (marking or copying), one conceptually
colours the data white (not yet seen by the collector), black (alive and
scanned by the collector) and grey (alive but not yet scanned by the
collector). The collector proceeds by scanning grey objects for pointers to
white objects. The white objects found are turned grey, and the grey objects
scanned are turned black. When there are no more grey objects, the
collection is complete and all the white objects can be recycled.