<html>
<head>
<style><!--
.hmmessage P
{
margin:0px;
padding:0px
}
body.hmmessage
{
font-size: 10pt;
font-family:Verdana
}
--></style>
</head>
<body class='hmmessage'>
Thanks Tony this looks very useful.<BR>
Here is the untruncated more informative email.<BR>
(We'll see how the quoted period is handled! :) )<BR>
<BR>
- Jay<BR>
<BR>
> CC: m3devel@elegosoft.com<BR>> From: hosking@cs.purdue.edu<BR>> To: jay.krell@cornell.edu<BR>> Subject: Re: gc/barriers?<BR>> Date: Thu, 5 Nov 2009 14:27:40 -0500<BR>> <BR>> For a description of the current concurrent CM3 GC algorithm I suggest <BR>> you take a look at my ISMM'06 paper: http://www.cs.purdue.edu/~hosking/papers/ismm06.pdf <BR>> .<BR>> <BR>> You are correct in stating that the write barriers used in the CM3 <BR>> collector are used for generational GC, to keep track of updates to <BR>> objects in the older generation. That way, when collecting just the <BR>> younger generation we can focus our attention to those pages of the <BR>> older generation that refer into the younger generation. Note that <BR>> all surviving young objects are promoted into the older generation at <BR>> every GC cycle. Thus, there are never young objects referred to by <BR>> old objects at the end of GC.<BR>> <BR>> The read barrier is used to protect against mutator threads executing <BR>> concurrently with the garbage collector from acquiring pointers to <BR>> objects that have not yet been scanned by the garbage collector. We <BR>> divide objects into those that are black (scanned by the garbage <BR>> collector), grey (reached but not yet scanned), and white (not yet <BR>> reached). At the end of the GC cycle unreached objects are garbage. <BR>> The CM3 collector maintains an invariant that black objects can never <BR>> contain pointers to white objects. Moreover, the read barrier ensures <BR>> that mutator threads hold only pointers to black objects. This <BR>> prevents the mutator from copying a pointer to a white object into a <BR>> black object. Otherwise, the collector might never reach that white <BR>> object and it would be freed even though it is reachable from the <BR>> black object.<BR>> <BR>> Impure objects contain pointers. Pure objects are "leaves" in the <BR>> object graph -- they contain no pointers.<BR>> <BR>> On 5 Nov 2009, at 13:19, Jay K wrote:<BR>> <BR>> > > Feel free to ask if you have questions.<BR>> ><BR>> > On a different matter.... can you, um, explain garbage collection?<BR>> > Specifically barriers?<BR>> > And the five states? Are they just older/younger?<BR>> ><BR>> ><BR>> > I understand "the generational hypothesis".<BR>> > "Most objects die young".<BR>> > (Most objects could be stack allocated. :) )<BR>> ><BR>> > And then there is a need to divide objects, at runtime, into older <BR>> > and younger.<BR>> ><BR>> > And then, there is some need to notice pointers that cross <BR>> > generations?<BR>> > That is, "old" usually includes no garbage, unless it has been <BR>> > changed since<BR>> > the last check, and then needs a new check?<BR>> ><BR>> > That is, a write barrier is a sort of copy-on-write, or notice- <BR>> > writes mechanism?<BR>> > A write into a generation means the gc needs to check it?<BR>> ><BR>> > That is, if you look at the Win32 GetWriteWatch API, that's what we <BR>> > are simulating sort of?<BR>> > (or vice versa)?<BR>> ><BR>> > I'm really guessing.<BR>> > And this doesn't explain what, if anything, a read barrier is.<BR>> ><BR>> > But then is meant by gray/impure/etc.?<BR>> ><BR>> > Maybe checkin RTCollector.readme?<BR>> ><BR>> > (note that read/write barriers are other things too -- ways to enforce<BR>> > (relative) order of executation).<BR>> ><BR>> > - Jay<BR>> ><BR>> ><BR>> ><BR>> ><BR>> ><BR>> <BR><BR> </body>
</html>