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.
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.
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:
http://wiki.llvm.org/Building_a_stack_crawler_in_LLVM
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):
def testCollectUnionLocalVar {
var u:String or float = newString(“Hello”);
tart.gc.GC.collect();
assertTrue(u isa String);
assertEq(“Hello”, typecastString);
u = 1.0;
tart.gc.GC.collect();
assertFalse(u isa String);
}
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:
private final class TraceActionImpl : TraceAction {
protected def tracePointer(ptrAddr:Address[Object]) {
let addr:Address[ubyte] = Memory.bitCast(ptrAddr[0]);
if fromSpace.contains(addr) {
let header:Address[ObjectHeader] = Memory.bitCast(addr);
// A gcstate of 0 means that ‘header’ is the head of a statically
// allocated object instance, in which case we need not do
// anything since it will be traced as a static root.
if (header.gcstate != 0) {
if (header.gcstate & uint(GCFlags.RELOCATED)) != 0 {
ptrAddr[0] = header.newLocation;
} else {
let size = header.gcstate & uint(~3);
let newAddr:Address[ubyte] = toSpace.alloc(size);
Memory.arrayCopy(newAddr, addr, size);
header.newLocation = ptrAddr[0] = Memory.bitCast(newAddr);
header.gcstate = uint(GCFlags.RELOCATED);
}
}
}
}
}
/** Static instance of the trace action. */
let TRACE_ACTION = TraceActionImpl();
The collect function simply invokes the trace action on the stack roots, the static roots, and the surviving members in the to-space:
@LinkageName(“GC_collect”) def collect() {
// Swap the spaces.
toSpace, fromSpace = fromSpace, toSpace;
toSpace.pos = toSpace.begin;
// Trace static roots and runtime stack
GCRuntimeSupport.traceStack(TRACE_ACTION);
GCRuntimeSupport.traceStaticRoots(TRACE_ACTION);
// Trace all remaining live objects.
var tracePos = toSpace.begin;
while (tracePos < toSpace.pos) {
let header:Address[ObjectHeader] = Memory.bitCast(tracePos);
let obj:Object = Memory.bitCastAddress[ubyte], Object;
let length = header.gcstate;
TRACE_ACTION.traceObject(obj);
tracePos += length;
}
}
If you are curious about the Tart language (“Tart is to C++ as Python is to Perl”) you can check it out at http://tart.googlecode.com or join the tart-dev mailing list on Google groups.
– Talin