*** 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".
- MS - this is a singleton class that is a subclass of
org.mmtk.plan.Plan. This class encapsulates data structures that are shared among multiple threads.
- MSMutator - subclass of org.mmtk.plan.MutatorContext. This class encapsulates data structures that are local to a single mutator thread. In the case of Jikes RVM, a Thread is actually a subclass of this class for efficiency reasons.
- MSCollector - subclass of org.mmtk.plan.CollectorContext. This provides thread-local data structures specific to a garbage collector thread.
- MSConstraints - subclass of org.mmtk.plan.PlanConstraints. This provides configuration information that the host virtual machine might need. It is separated out from the Plan class in order to prevent circular class loading dependencies.
- MSTraceLocal - subclass of org.mmtk.plan.TraceLocal. This provides thread-local data structures specific to a particular way of traversing the heap. In a simple collector like MarkSweep, there is only one of these classes, but in more complex collectors there may be several. For example, in a generational collector, there will be one TraceLocal class for a nursery collection, and another for a full-heap collection.
Spaceclass, 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.
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.
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
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:
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
alloc method of
MarkSweepLocal is inherited from
SegregatedFreeListLocal (mark-sweep is not the only way of managing free-list allocation), and looks like this
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 is the only correct way for a policy to allocate new virtual memory for its own use.
The logic of space.acquire is:
- First, poll the plan to find out whether the heap is full. This logic is performed by the plan, because it has knowledge of copy reserves etc.
- The 'poll' method will request a GC if required, and return
trueif it has done so.
- Then we wait for GC if required. 'poll' can't wait, because it is called in circumstances that aren't GC safe.
- If Plan.poll(...) returns false (we are within the allowed heap size), we call pr.getNewPages to allocate virtual memory. At this stage we can find that we have run out of virtual memory, and if so, we force a GC
- If a GC is performed, we return Address.zero(), rather than retrying locally. In many plans, the next allocation request will be satisfied by re-using space in a page that already belongs to a policy, so the post-GC allocation must be performed further up in the call stack. The retry logic is handled in
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
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.
collect() method is specific to the type of collector, and in
StopTheWorldCollector it looks like this
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.
org.mmtk.plan.Simple defines the basic structure of most of MMTk's garbage collectors. First it defines the phases themselves,
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.
A simple phase can be scheduled in one of 4 ways:
- Global. One collector thread is chosen to run the collectionPhase method of the global Plan object.
- Collector. All collector threads run collectionPhase of the plan's CollectorContext object(s).
- Mutator. The collector threads run in parallel and iterate over the available MutatorContext objects (ie the mutator threads), and run the mutator's collectionPhase method. Note that the collector threads are performing work on a per-mutator basis, because in general the mutator threads are stopped at this point.
- Concurrent. The controller is requested to start a concurrent collectcor thread.
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.
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:
- An edge is a reference in the heap from one reference field to the object (or node) it points to.
- Tracing an object is the policy-defined operation performed by the collector on an object. In a mark-sweep policy this means setting the mark state of the object. In a copying policy this means moving the object to its new location.
- Scanning ...
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
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