Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
Comment: Migrated to Confluence 5.3

...

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.

...

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.  

 

Code Block
titleMS.java
themeConfluence
linenumberstrue
languagejava
  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

Code Block
titleMSMutator.java
linenumberstrue
languagejava
   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.

...

Code Block
titleMSMutator.java
linenumberstrue
languagejava
  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.

...

Code Block
titleSegregatedFreeListLocal.java (simplified)
linenumberstrue
languagejava
  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 */
      cell.store(Address.zero());
      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.

...

Code Block
titleSpace.java (simplified)
linenumberstrue
languagejava
  public final Address acquire(int pages) {
    pr.reservePages(pages);
    /*/ Poll, either fixing budget or requiring GC
*/     if (VM.activePlan.global().poll(false, this)) {
      VM.collection.blockForGC();
      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);
      VM.collection.blockForGC();
      return Address.zero();
    }
    return rtn;
  }

The logic of space.acquire is:

...

 

Code Block
titleAllocator.java (simplified)
linenumberstrue
languagejava
   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) {
        VM.collection.outOfMemory();
      }
      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.

...

Code Block
titleParallelCollector
linenumberstrue
languagejava
  public void run() {
    while(true) {
      park();
      collect();
    }
  }

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

Code Block
titleStopTheWorldCollector
linenumberstrue
languagejava
  public void collect() {
    Phase.beginNewPhaseStack(Phase.scheduleComplex(global().collection));
  }

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.

...

Code Block
titleSimple.java
linenumberstrue
languagejava
  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.

Code Block
titleSimple.java
linenumberstrue
languagejava
  /** 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));

...

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

Code Block
titleMS.java
linenumberstrue
languagejava
  @Inline
  @Override
  public void collectionPhase(short phaseId) {
    if (phaseId == PREPARE) {
      super.collectionPhase(phaseId);
      msTrace.prepare();
      msSpace.prepare(true);
      return;
    }
    if (phaseId == CLOSURE) {
      msTrace.prepare();
      return;
    }
    if (phaseId == RELEASE) {
      msTrace.release();
      msSpace.release();
      super.collectionPhase(phaseId);
      return;
    }
    super.collectionPhase(phaseId);
  }

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).

...

  • 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 ... is the process of identifying the reference fields of an object and processing the objects reachable from each of them.

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

Code Block
titleMSCollector.java
linenumberstrue
languagejava
  public void collectionPhase(short phaseId, boolean primary) {
    ...
    if (phaseId == MS.CLOSURE) {
      fullTrace.completeTrace();
      return;
    }
    ...
  }

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.