Versions Compared

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.

...

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

...

Code Block
titleMS.java
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).

...

Code Block
titleMSCollector.java
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.