A working garbage collector - finally :)

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

Since you are using a copying collector, may I ask how do you handle registers holding pointers to intermediate values?

The example I am considering is something like

void foo(void);
void f(long long *v, long long n) {
   long long int i;
   for (i = 0; i < n; ++i) {
     v[i] = i;
     foo();
   }
}

If *v points to gc memory, we can start the function with

%v.addr = alloca i64*, align 8
%foobar = bitcast i64** %v.addr to i8**
call void @llvm.gcroot(i8** %foobar, i8* null)
store i64* %v, i64** %v.addr, align 8

but nothing prevents llvm from putting the call to foo in between the computation of &v[i] and the store by using a callee saved register. If GC moves moves v during the call to foo, the next store will be wrong.

-- Talin

Cheers,
Rafael

Where's the problem? A pointer to v's alloca escapes to llvm.gcroot,
so the optimizers should know that foo could modify the value it
holds. foo() might also read v[i] through the escaped pointer, so the
store will have to happen before the call.

Reid

Where's the problem? A pointer to v's alloca escapes to llvm.gcroot,
so the optimizers should know that foo could modify the value it
holds. foo() might also read v[i] through the escaped pointer, so the
store will have to happen before the call.

It is fine, sorry. I had a bug in the example IL I wrote, I had added the call after the load of 'v' but before the getelement pointer. If I put it in the right place I get a load of 'v' in the correct side of the call.

Reid

Thanks,
Rafael