[M3devel] gc/barriers?

[Jay K]

Thanks Tony this looks very useful.

Here is the untruncated more informative email.

(We'll see how the quoted period is handled! :) )

 

 - Jay

 

> CC: m3devel at elegosoft.com
> From: hosking at cs.purdue.edu
> To: jay.krell at cornell.edu
> Subject: Re: gc/barriers?
> Date: Thu, 5 Nov 2009 14:27:40 -0500
> 
> 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
> >
> >
> >
> >
> >
> 

 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20091105/73d5b392/attachment-0002.html>