[M3devel] gc/barriers?

[Tony Hosking]

For a description of the current concurrent CM3 GC algorithm I suggest  
you take a look at my ISMM'06 paper: http://www.cs.purdue.edu/~hosking/papers/ismm06.pdf 
.

You are correct in stating that the write barriers used in the CM3  
collector are used for generational GC, to keep track of updates to  
objects in the older generation.  That way, when collecting just the  
younger generation we can focus our attention to those pages of the  
older generation that refer into the younger generation.  Note that  
all surviving young objects are promoted into the older generation at  
every GC cycle.  Thus, there are never young objects referred to by  
old objects at the end of GC.

The read barrier is used to protect against mutator threads executing  
concurrently with the garbage collector from acquiring pointers to  
objects that have not yet been scanned by the garbage collector.  We  
divide objects into those that are black (scanned by the garbage  
collector), grey (reached but not yet scanned), and white (not yet  
reached).  At the end of the GC cycle unreached objects are garbage.   
The CM3 collector maintains an invariant that black objects can never  
contain pointers to white objects.  Moreover, the read barrier ensures  
that mutator threads hold only pointers to black objects.  This  
prevents the mutator from copying a pointer to a white object into a  
black object.  Otherwise, the collector might never reach that white  
object and it would be freed even though it is reachable from the  
black object.

Impure objects contain pointers.  Pure objects are "leaves" in the  
object graph -- they contain no pointers.

On 5 Nov 2009, at 13:19, Jay K wrote:

>  > Feel free to ask if you have questions.
>
> On a different matter.... can you, um, explain garbage collection?
> Specifically barriers?
> And the five states? Are they just older/younger?
>
>
> I understand "the generational hypothesis".
> "Most objects die young".
>  (Most objects could be stack allocated. :) )
>
> And then there is a need to divide objects, at runtime, into older  
> and younger.
>
> And then, there is some need to notice pointers that cross  
> generations?
> That is, "old" usually includes no garbage, unless it has been  
> changed since
> the last check, and then needs a new check?
>
> That is, a write barrier is a sort of copy-on-write, or notice- 
> writes mechanism?
> A write into a generation means the gc needs to check it?
>
> That is, if you look at the Win32 GetWriteWatch API, that's what we  
> are simulating sort of?
> (or vice versa)?
>
> I'm really guessing.
> And this doesn't explain what, if anything, a read barrier is.
>
> But then is meant by gray/impure/etc.?
>
> Maybe checkin RTCollector.readme?
>
> (note that read/write barriers are other things too -- ways to enforce
> (relative) order of executation).
>
>  - Jay
>
>
>
>
>