Quick Links:

Releases | Mailing Lists | Source Control | Issue Tracker | Regression Tests

19 Building a Mark-sweep Collector

Chapter 19
Building a Mark-sweep Collector

We will now modify the Tutorial collector to perform allocation and collection according to a mark-sweep policy. First we will change the allocation from bump-allocation to free-list allocation (but still no collector whatsoever), and then we will add a mark-sweep collection policy, yielding a complete mark-sweep collector.

19.1 Free-list Allocation

This step will change your simple collector from using a bump pointer to a free list (but still without any garbage collection).

  1. Update the constraints for this collector to reflect the constraints of a mark-sweep system, by updating TutorialConstraints as follows:
    • gcHeaderBits() should return MarkSweepSpace.LOCAL_GC_BITS_REQUIRED.
    • gcHeaderWords() should return MarkSweepSpace.GC_HEADER_WORDS_REQUIRED.
    • The maxNonLOSDefaultAllocBytes()\spverb method should be added, overriding one provided by the base class, and should return SegregatedFreeListSpace.MAX_FREELIST_OBJECT_BYTES (because this reflects the largest object size that can be allocated with the free list allocator).
  2. In Tutorial, replace the ImmortalSpace with a MarkSweepSpace:
    1. rename the variable noGCSpace to msSpace (right-click, Refactor → Rename...)
    2. rename the variable NOGC to MARK_SWEEP (right-click, Refactor → Rename...)
    3. change the type and static initialization of msSpace to
      public static final MarkSweepSpace msSpace = new MarkSweepSpace("ms", VMRequest.discontiguous());
    4. add an import for MarkSweepSpace and remove the redundant import for ImmortalSpace.
  3. In TutorialMutator, replace the ImmortalLocal (a bump pointer) with a MarkSweepLocal (a free-list allocator)
    1. change the type of nogc and change the static initializer appropriately.
    2. change the appropriate import statement from ImmortalLocal to MarkSweepLocal.
    3. rename the variable nogc to ms (right-click, Refactor → Rename...)
  4. Also in TutorialMutator, fix postAlloc() to initialize the mark-sweep header:
    if (allocator == Tutorial.ALLOC_DEFAULT) { 
      Tutorial.msSpace.postAlloc(ref); 
    } else { 
      super.postAlloc(ref, typeRef, bytes, allocator); 
    }
  5. In PlanSpecificConfig, find the line for Tutorial, and change "default" to "ms"

With these changes, Tutorial should now work, just as it did before, only exercising a free list (mark-sweep) allocator rather than a bump pointer (immortal) allocator. Create a BaseBaseTutorial build, and test your system to ensure it performs just as it did before. You may notice that its memory is exhausted slightly earlier because the free list allocator is slightly less efficient in space utilization than the bump pointer allocator.

19.2 Mark-Sweep Collection

The next change required is to perform mark-and-sweep collection whenever the heap is exhausted. The poll() method of a plan is called at appropriate intervals by other MMTk components to ask the plan whether a collection is required.

  1. Change TutorialConstraints so that it inherits constraints from a collecting plan:
    public class TutorialConstraints extends StopTheWorldConstraints
  2. The plan needs to know how to perform a garbage collection. Collections are performed in phases, coordinated by data structures defined in StopTheWorld, and have global and thread-local components. First ensure the global components are behaving correctly. These are defined in Tutorial (which is implicitly global).
    1. Make Tutorial extend StopTheWorld (for stop-the-world garbage collection) rather than Plan (the superclass of StopTheWorld):
      public class Tutorial extends StopTheWorld
    2. Rename the trace variable to msTrace (right-click, Refactor → Rename...)
    3. Add code to ensure that Tutorial performs the correct global collection phases in collectionPhase():
      1. First remove the assertion that the code is never called (if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(false);).
      2. Add the prepare phase, preparing both the global tracer (msTrace) and the space (msSpace), after first performing the preparation phases associated with the superclasses. Using the commented template in Tutorial.collectionPhase(), set the following within the clause for phaseId == PREPARE:
        if (phaseId == PREPARE) { 
          super.collectionPhase(phaseId); 
          msTrace.prepare(); 
          msSpace.prepare(true); 
          return; 
        }
      3. Add the closure phase, again preparing the global tracer (msTrace):
        if (phaseId == CLOSURE) { 
          msTrace.prepare(); 
          return; 
        }
      4. Add the release phase, releasing the global tracer (msTrace) and the space (msSpace) before performing the release phases associated with the superclass:
        if (phaseId == RELEASE) { 
          msTrace.release(); 
          msSpace.release(); 
          super.collectionPhase(phaseId); 
          return; 
        }
      5. Finally ensure that for all other cases, the phases are delegated to the superclass, uncommenting the following after all of the above conditionals:
        super.collectionPhase(phaseId);
    4. Add a new accounting method that determines how much space a collection needs to yield to the mutator. The method, getPagesUsed, overrides the one provided in the StopTheWorld superclass:
      @Override 
      public int getPagesUsed() { 
        return super.getPagesUsed() + msSpace.reservedPages(); 
      }
    5. Add a new method that determines whether an object will move during collection:
      @Override 
      public boolean willNeverMove(ObjectReference object) { 
        if (Space.isInSpace(MARK_SWEEP, object)) 
         return true; 
        return super.willNeverMove(object); 
      }
  3. Next ensure that Tutorial correctly performs local collection phases. These are defined in TutorialCollector.
    1. Make TutorialCollector extend StopTheWorldCollector:
      1. Extend the class (public class TutorialCollector extends StopTheWorldCollector).
      2. Import StopTheWorldCollector.
      3. Remove some methods now implemented by StopTheWorldCollector: collect() and (if present) concurrentCollect() and
        concurrentCollectionPhase().
    2. Add code to ensure that Tutorial performs the correct global collection phases in collectionPhase():
      1. First remove the assertion that the code is never called (if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(false);).
      2. Add the prepare phase, preparing both the local tracer (trace) after first performing the preparation phases associated with the superclasses. Using the commented template in TutorialCollector.collectionPhase(), set the following within the clause for phaseId == PREPARE:
        if (phaseId == Tutorial.PREPARE) { 
          super.collectionPhase(phaseId, primary); 
          trace.prepare(); 
          return; 
        }
      3. Add the closure phase, completing the local tracer (trace):
        if (phaseId == Tutorial.CLOSURE) { 
          trace.completeTrace(); 
          return; 
        }
      4. Add the release phase, releasing the local tracer (trace) before performing the release phases associated with the superclass:
        if (phaseId == Tutorial.RELEASE) { 
          trace.release(); 
          super.collectionPhase(phaseId, primary); 
          return; 
        }
      5. Finally ensure that for all other cases, the phases are delegated to the superclass, uncommenting the following after all of the above conditionals:
        super.collectionPhase(phaseId, primary);
  4. Finally ensure that Tutorial correctly performs local mutator-related collection activities:
    1. Make TutorialMutator extend StopTheWorldMutator:
      1. Extend the class: public class TutorialMutator extends StopTheWorldMutator.
      2. Import StopTheWorldMutator.
    2. Update the mutator-side collection phases:
      1. First remove the assertion that the code is never called (if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(false);).
      2. Add the prepare phase to collectionPhase() which prepares mutator-side data structures (namely the per-thread free lists) for the startof a collection:
        if (phaseId == Tutorial.PREPARE) { 
          super.collectionPhase(phaseId, primary); 
          ms.prepare(); 
          return; 
        }
      3. Add the release phase to collectionPhase() which re-initializes mutator-side data structures (namely the per-thread free lists) after the end of a collection:
        if (phaseId == Tutorial.RELEASE) { 
          ms.release(); 
          super.collectionPhase(phaseId, primary); 
          return; 
        }
      4. Finally, delegate all other phases to the superclass:
        super.collectionPhase(phaseId, primary);

With these changes, Tutorial should now work with both mark-sweep allocation and collection. Create a BaseBaseTutorial build, and test your system to ensure it performs just as it did before. You can observe the effect of garbage collection as the program runs by adding -X:gc:verbose=1 to your command line as the first argument after rvm. If you run a very simple program (such as HelloWorld), you might not observe any garbage collection. In that case, try running a larger program such as a DaCapo benchmark. You may also observe that the output from -X:gc:verbose=1 indicates that the heap is growing. Dynamic heap resizing is normal default behavior for a JVM. You can override this by providing minimum (-Xms) and maximum (-Xmx) heap sizes (these are standard arguments respected by all JVMs. The heap size should be specified in bytes as an integer and a unit (K, M, G), for example: -Xms20M -Xmx20M.

19.3 Optimized Mark-sweep Collection

MMTk has a unique capacity to allow specialization of the performance-critical scanning loop. This is particularly valuable in collectors which have more than one mode of collection (such as in a generational collector), so each of the collection paths is explicitly specialized at build time, removing conditionals from the hot portion of the tracing loop at the core of the collector. Enabling this involves just two small steps:

  1. Indicate the number of specialized scanning loops and give each a symbolic name, which at this stage is just one since we have a very simple collector:
    1. Override the numSpecializedScans() getter method in TutorialConstraints:
      @Override 
      public int numSpecializedScans() { return 1; }
    2. Define a constant to represent our (only) specialized scan in Tutorial (we will call this scan ”mark”):
      public static final int SCAN_MARK = 0;
  2. Register the specialized method:
    1. Add the following line to registerSpecializedMethods() method in Tutorial:
      TransitiveClosure.registerSpecializedScan(SCAN_MARK, TutorialTraceLocal.class);
    2. Add Tutorial.SCAN_MARK as the first argument to the superclass constructor for TutorialTraceLocal:
      public TutorialTraceLocal(Trace trace) { 
        super(Tutorial.SCAN_MARK, trace); 
      }