*** Work in progress ***

This page gives a brief outline of the major control flows in the execution of a garbage collector in MMTk.  For simplicity, we focus on the MarkSweep collector, although much of the discussion will be relevant to other collectors. 

This page assumes you have a basic knowledge of garbage collection, for those that don't, please see one of the standard texts such as The Garbage Collection Handbook. 

Structure of a Plan

An MMTk Plan is required to provide 5 classes.  They are required to have consistent names which start with the same name and have a suffix that indicates which class it inherits from. in the case of the MarkSweep plan, the name is "MS".

The basic architecture of MMTk is that virtual address space is divided into chunks (of 4MB in a 32-bit memory model) that are managed according to a specific policy.  A policy is implemented by an instance of the Space class, and it is in the policy class that the mechanics of a particular mechanism (like mark-sweep) is implemented.  The task of a Plan is to create the policy (Space) objects that manage the heap, and to integrate them into the MMTk framework.  
MMTk exposes some of this memory management policy to the host VM, by allowing the VM to specify an allocator (represented by a small integer) when allocating space.  The interface exposed to the VM allows it to choose whether an object will move during collection or not, whether the object is large enough to require special handling etc.  The MMTk plan is free (within the semantic guarantees exposed to the VM) to direct each of these allocators to a particular policy.


A policy describes how a range of virtual address space is managed.  The base class of all policies is org.mmtk.policy.Space, and a particular instance of a policy is known generically as a space.  The static initializer of a Plan and its subclasses define the spaces that make up an MMTk plan.  


public static final MarkSweepSpace msSpace = new MarkSweepSpace("ms", VMRequest.create());
public static final int MARK_SWEEP = msSpace.getDescriptor();

In this code fragment, we see the MS plan defined.  Note that we generally also define a static final space descriptor.  This is an optimization that allows some rapid operations on spaces.

Space is a global object, shared among multiple mutator threads.  Each policy will also have one or more thread-local classes which provide unsynchronized allocation.  These classes are subclasses of org.mmtk.utility.alloc.Allocator, and in the case of MarkSweep, it is called MarkSweepLocal.  Instances of MarkSweepLocal are created as part of a mutator context, like this

protected MarkSweepLocal ms = new MarkSweepLocal(MS.msSpace);

The design pattern is that the local Allocator will allocate space from a thread-local buffer, and when that is exhausted it will allocate a new buffer from the global Space, performing appropriate locking.  The constructor of the MarkSweepLocal specifies the space from which the allocator will allocate global memory.


MMTk provides two methods for allocating an object.  These are provided by the MSMutator class, to give each plan the opportunity to use fast, unsynchronized thread-local allocation before falling back to a slower synchronized slow-path.

The version implemented in MarkSweep looks like this:

public Address alloc(int bytes, int align, int offset, int allocator, int site) {
  if (allocator == MS.ALLOC_DEFAULT) {
    return ms.alloc(bytes, align, offset);
  return super.alloc(bytes, align, offset, allocator, site);

The basic structure of this method is common to all MMTk plans.  First they decide whether the operation applies to this level of abstraction (if (allocator == MS.ALLOC_DEFAULT)), and if so, delegate to the appropriate place, otherwise pass it up the chain to the super-class.  In the case of MarkSweep, MSMutator delegates the allocation to its thread-local MarkSweepLocal object ms.

The alloc method of MarkSweepLocal is inherited from SegregatedFreeListLocal (mark-sweep is not the only way of managing free-list allocation), and looks like this

public final Address alloc(int bytes, int align, int offset) {
  int sizeClass = getSizeClass(bytes);
  Address cell = freeList.get(sizeClass);
  if (!cell.isZero()) {
    freeList.set(sizeClass, cell.loadAddress());
    /* Clear the free list link */
    return cell;
  return allocSlow(bytes, align, offset);

This is a standard pattern for thread-local allocation: first we look in the thread-local space (line 3), and if successful return the result (lines 4-8).  If unsuccessful, we request space from the global policy via the method Allocator.allocSlow.  This is the common interface that all Allocators use to request space from the global policy.  This will eventually call the allocator-specific allocSlowOnce method.  The workings of the allocSlowOnce method are very policy-specific, so not appropriate to look at at this stage, but eventually all policies will attempt to acquire fresh virtual memory via the Space.acquire method.

Space.acquire is the only correct way for a policy to allocate new virtual memory for its own use.  

public final Address acquire(int pages) {
  // Poll, either fixing budget or requiring GC
  if (VM.activePlan.global().poll(false, this)) {
    return Address.zero(); // GC required, return failure
  // Page budget is ok, try to acquire virtual memory
  Address rtn = pr.getNewPages(pagesReserved, pages, zeroed);
  if (rtn.isZero()) {  // Failed, so force a GC
    boolean gcPerformed = VM.activePlan.global().poll(true, this);
    return Address.zero();
  return rtn;

The logic of space.acquire is:


public final Address allocSlowInline(int bytes, int alignment, int offset) {
  boolean emergencyCollection = false;
  while (true) {
    Address result = allocSlowOnce(bytes, alignment, offset);
    if (!result.isZero()) {
      return result;
    if (emergencyCollection) {
    emergencyCollection = Plan.isEmergencyCollection();

This code fragment shows the retry logic in the allocator.  We try allocating using allocSlowOnce, which may recycle partially-used blocks and eventually call Space.acquire.  If a GC occurred, we try again.  Eventually the plan will request an emergency collection which will (for example) cause soft references to be dropped.  If this fails we throw an OutOfMemoryError.



In a stop-the-world garbage collector like MarkSweep, the mutator threads run until memory is exhausted, then all mutator threads are suspended, the collector threads are activated, and they perform a garbage collection.  After the GC is complete, the collector threads are suspended and the mutator threads resume.  MMTk also has some support for concurrent collectors, in which one or more collector threads can be scheduled to run alongside the mutator, either exclusively or in addition to (hopefully briefer) stop-the-world phases. 

Thread scheduling in MMTk is handled by a GC controller thread, implemented in the singleton class org.mmtk.plan.ControllerCollectorContext  held in the static field Plan.controlCollectorContext. Whenever a collection is initiated, it is done by calling methods on this object.


As mentioned above, every attempt to allocate fresh virtual memory calls the current plan's poll(...) method.  This initiates a GC by calling controlCollectorContext.request(), which in a stop-the-world collector like MarkSweep pauses the mutator threads and then wakes the collector threads.  The main loop of the garbage collector is simply the run() method of ParallelCollector, shown below.

public void run() {
  while(true) {

The collect() method is specific to the type of collector, and in StopTheWorldCollector it looks like this

public void collect() {

Collector Phases

Every garbage collection consists of a series of steps.  Each step is either executed once (e.g. updating the mark state before marking the heap), or in parallel on all available collector threads (e.g. the parallel mark phase).  The actual work of a step is done by the collectionPhase method of the global, collector or mutator class of a plan.

In early versions of MMTk, the main collection method was a template method, calling individual methods for each phase of the collection.  As the number of collectors in MMTk grew, this became unwieldy and has been replaced with a configurable mechanism of phases.  

The class org.mmtk.plan.Simple defines the basic structure of most of MMTk's garbage collectors.  First it defines the phases themselves,

public static final short SET_COLLECTION_KIND = Phase.createSimple("set-collection-kind", null);
public static final short INITIATE            = Phase.createSimple("initiate", null);
public static final short PREPARE             = Phase.createSimple("prepare");

Each phase of the collection is represented by a 16-bit integer, an index into a table of Phase objects.  Simple phases are scheduled, and combined into sequences, or complex phases.

/** Ensure stacks are ready to be scanned */
protected static final short prepareStacks = Phase.createComplex("prepare-stacks", null,
    Phase.scheduleMutator    (PREPARE_STACKS),
    Phase.scheduleGlobal     (PREPARE_STACKS));

A simple phase can be scheduled in one of 4 ways: 

Between every phase of a collection, the collector threads rendezvous at a synchronization barrier.  The actual execution of a collector's phases is done in the method Phase.processPhaseStack.  This method handles resuming a concurrent collection as well as running a full stop-the-world collection.

The actual work of a collection phase is done (as mentioned above) in the collectionPhase method of the major Plan classes.

public void collectionPhase(short phaseId) {
  if (phaseId == PREPARE) {
  if (phaseId == CLOSURE) {
  if (phaseId == RELEASE) {

This excerpt shows how the global MS plan implements collectionPhase, illustrating the key phases of a simple stop-the-world collector.  The prepare phase performs tasks such as changing the mark state, the closure phase performs a transifive closure over the heap (the mark phase of a mark-sweep algorithm) and the release phase performs any post-collection steps.  Where possible, a plan is structured so that each layer of inheritance deals only with the objects it creates, i.e. the MS class operates on the msSpace and delegates work on all other spaces to the super-class where they are defined.  By convention the PREPARE phase is performed outside-in (super-class preparation first) and RELEASE is done inside-out (local first, super-class second).

Tracing the heap

The main operation of a tracing collector is the transitive closure operation where all (or a subset) of the object graph is visited.  Some collectors such as generational collectors perform these operations in more than one way, e.g. a nursery collection in a generational collector does not trace through pointers into the mature space, while a full-heap collection does.  All MMTk collectors are designed to run using several parallel threads, using data structures that have unsynchronized thread-local and synchronized global components in the same way as MMTk's policy classes.

MMTk's trace operation uses the following terminology:

Each distinct transitive closure operation is defined as a subclass of TraceLocal.  The closure is performed in the collectionPhase method of the plan-specific CollectorContext class

public void collectionPhase(short phaseId, boolean primary) {
  if (phaseId == MS.CLOSURE) {

The initial starting point for the closure is computed by the STACK_ROOTS and ROOTS phases, which add root locations to a buffer by calling TraceLocal.reportDelayedRootEdge.  The closure operation proceeds by invoking traceObiect on each root location (in method processRootEdge), and then invoking scanObject on each heap object encountered.  Note that the CLOSURE operation is performed multiple times in each GC, due to processing of reference types.