Well, after many months of effort, my LLVM-based garbage collector is finally passing its unit tests. This represents a significant milestone for me in the development of my programming language, Tart.<div><br></div><div>The collector itself is fairly rudimentary - a single-generation, copying collector. It does not yet support multi-threaded programs, but in practice there's no serious obstacle to supporting threading due to the fact that the collector does not need any mutable global variables.</div>
<div><br></div><div>The stack tracer is based on the paper I posted a few months back, which I have now transferred over to the LLVM wiki. It's meant to be a practical introduction to the task of building a garbage collector in LLVM:</div>
<div><br></div><div><meta http-equiv="content-type" content="text/html; charset=utf-8"> <a href="http://wiki.llvm.org/Building_a_stack_crawler_in_LLVM">http://wiki.llvm.org/Building_a_stack_crawler_in_LLVM</a></div><div>
<br></div><div>Here's a sample of one of the unit tests. It's checking that the tracer can properly distinguish between two states of a union, one state having a traceable object (a String), and the other state containing a non-traceable value (a float):</div>
<div><br></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> def testCollectUnionLocalVar {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> var u:String or float = newString("Hello");</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> tart.gc.GC.collect();</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> assertTrue(u isa String);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> assertEq("Hello", typecast[String](u));</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> u = 1.0;</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> tart.gc.GC.collect();</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> assertFalse(u isa String);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div></div><div><br></div><div>The heart of the collector is the TraceAction class - which is invoked for each pointer reference. The tracer for the Tart language is written, of course, in Tart, although the style is not the normal Tart style due to the need to deal with low-level objects such as addresses and pointers:</div>
<div><br></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> private final class TraceActionImpl : TraceAction {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> protected def tracePointer(ptrAddr:Address[Object]) {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> let addr:Address[ubyte] = Memory.bitCast(ptrAddr[0]);</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> if fromSpace.contains(addr) {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> let header:Address[ObjectHeader] = Memory.bitCast(addr);</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> // A gcstate of 0 means that 'header' is the head of a statically</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> // allocated object </font><span class="Apple-style-span" style="font-family: 'courier new', monospace; ">instance, in which case we need not do</span></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> // anything since it will be traced as </span><span class="Apple-style-span" style="font-family: 'courier new', monospace; ">a static root.</span></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> if (header.gcstate != 0) {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> if (header.gcstate & uint(GCFlags.RELOCATED)) != 0 {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> ptrAddr[0] = header.newLocation;</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> } else {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> let size = header.gcstate & uint(~3);</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> let newAddr:Address[ubyte] = toSpace.alloc(size);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> Memory.arrayCopy(newAddr, addr, size);</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> header.newLocation = ptrAddr[0] = Memory.bitCast(newAddr);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> header.gcstate = uint(GCFlags.RELOCATED);</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div></div><div><font class="Apple-style-span" face="'courier new', monospace"><div><br></div><div> /** Static instance of the trace action. */</div>
<div> let TRACE_ACTION = TraceActionImpl();</div></font></div><div><br></div><div>The collect function simply invokes the trace action on the stack roots, the static roots, and the surviving members in the to-space:</div>
<div><br></div><div><div><font class="Apple-style-span" face="'courier new', monospace"> @LinkageName("GC_collect") def collect() {</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> // Swap the spaces.</font></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> toSpace, fromSpace = fromSpace, toSpace;</span></div><div><font class="Apple-style-span" face="'courier new', monospace"> toSpace.pos = toSpace.begin;</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace"> // Trace static roots and runtime stack</font></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> GCRuntimeSupport.traceStack(TRACE_ACTION);</span></div><div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> GCRuntimeSupport.traceStaticRoots(TRACE_ACTION);</span></div>
<div><font class="Apple-style-span" face="'courier new', monospace"><br></font></div><div><font class="Apple-style-span" face="'courier new', monospace"> // Trace all remaining live objects.</font></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> var tracePos = toSpace.begin;</span></div><div><font class="Apple-style-span" face="'courier new', monospace"> while (tracePos < toSpace.pos) {</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> let header:Address[ObjectHeader] = Memory.bitCast(tracePos);</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> let obj:Object = Memory.bitCast[Address[ubyte], Object](tracePos);</font></div>
<div><font class="Apple-style-span" face="'courier new', monospace"> let length = header.gcstate;</font></div><div><font class="Apple-style-span" face="'courier new', monospace"> TRACE_ACTION.traceObject(obj);</font></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> tracePos += length;</span></div><div><font class="Apple-style-span" face="'courier new', monospace"> }</font></div>
<div><span class="Apple-style-span" style="font-family: 'courier new', monospace; "> }</span></div></div><div><br></div><div>If you are curious about the Tart language ("Tart is to C++ as Python is to Perl") you can check it out at <a href="http://tart.googlecode.com">http://tart.googlecode.com</a> or join the tart-dev mailing list on Google groups.</div>
<div><br></div><div>-- Talin</div><div><br></div>