[LLVMdev] A working garbage collector - finally :)

[Talin]

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", typecast[String](u));
    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.bitCast[Address[ubyte], Object](tracePos);
      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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110220/24e90bd8/attachment.html>