Source code

001/*
002 *  This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 *  This file is licensed to You under the Eclipse Public License (EPL);
005 *  You may not use this file except in compliance with the License. You
006 *  may obtain a copy of the License at
007 *
008 *      http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 *  See the COPYRIGHT.txt file distributed with this work for information
011 *  regarding copyright ownership.
012 */
013package org.mmtk.plan.refcount;
014
015import org.mmtk.plan.Phase;
016import org.mmtk.plan.StopTheWorld;
017import org.mmtk.plan.Trace;
018import org.mmtk.plan.refcount.backuptrace.BTFreeLargeObjectSweeper;
019import org.mmtk.plan.refcount.backuptrace.BTSweeper;
020import org.mmtk.policy.ExplicitFreeListSpace;
021import org.mmtk.policy.ExplicitLargeObjectSpace;
022import org.mmtk.policy.Space;
023import org.mmtk.utility.Log;
024import org.mmtk.utility.alloc.LinearScan;
025import org.mmtk.utility.deque.SharedDeque;
026import org.mmtk.utility.heap.VMRequest;
027import org.mmtk.utility.options.Options;
028import org.mmtk.utility.sanitychecker.SanityChecker;
029import org.mmtk.vm.VM;
030import org.vmmagic.pragma.*;
031import org.vmmagic.unboxed.Address;
032import org.vmmagic.unboxed.ObjectReference;
033
034/**
035 * This class implements the global state of a reference counting collector.
036 * See Shahriyar et al for details of and rationale for the optimizations used
037 * here (http://dx.doi.org/10.1145/2258996.2259008).  See Chapter 4 of
038 * Daniel Frampton's PhD thesis for details of and rationale for the cycle
039 * collection strategy used by this collector.
040 */
041@Uninterruptible
042public class RCBase extends StopTheWorld {
043  public static final short PROCESS_OLDROOTBUFFER  = Phase.createSimple("old-root");
044  public static final short PROCESS_NEWROOTBUFFER  = Phase.createSimple("new-root");
045  public static final short PROCESS_MODBUFFER      = Phase.createSimple("mods");
046  public static final short PROCESS_DECBUFFER      = Phase.createSimple("decs");
047
048  /** Is cycle collection enabled? */
049  public static final boolean CC_ENABLED           = true;
050  /** Force full cycle collection at each GC? */
051  public static boolean ccForceFull        = false;
052  /** Use backup tracing for cycle collection (currently the only option) */
053  public static final boolean CC_BACKUP_TRACE      = true;
054
055  public static boolean performCycleCollection;
056  public static final short BT_CLOSURE             = Phase.createSimple("closure-bt");
057
058  /** True if we are building for generational RC */
059  public static final boolean BUILD_FOR_GENRC = ((RCBaseConstraints) VM.activePlan.constraints()).buildForGenRC();
060
061  // CHECKSTYLE:OFF
062
063  /**
064   * Reference counting specific collection steps.
065   */
066  protected static final short refCountCollectionPhase = Phase.createComplex("release", null,
067      Phase.scheduleGlobal     (PROCESS_OLDROOTBUFFER),
068      Phase.scheduleCollector  (PROCESS_OLDROOTBUFFER),
069      Phase.scheduleGlobal     (PROCESS_NEWROOTBUFFER),
070      Phase.scheduleCollector  (PROCESS_NEWROOTBUFFER),
071      Phase.scheduleMutator    (PROCESS_MODBUFFER),
072      Phase.scheduleGlobal     (PROCESS_MODBUFFER),
073      Phase.scheduleCollector  (PROCESS_MODBUFFER),
074      Phase.scheduleMutator    (PROCESS_DECBUFFER),
075      Phase.scheduleGlobal     (PROCESS_DECBUFFER),
076      Phase.scheduleCollector  (PROCESS_DECBUFFER),
077      Phase.scheduleGlobal     (BT_CLOSURE),
078      Phase.scheduleCollector  (BT_CLOSURE));
079
080  protected static final short genRCCollectionPhase = Phase.createComplex("release", null,
081      Phase.scheduleGlobal     (PROCESS_OLDROOTBUFFER),
082      Phase.scheduleCollector  (PROCESS_OLDROOTBUFFER),
083      Phase.scheduleGlobal     (PROCESS_NEWROOTBUFFER),
084      Phase.scheduleCollector  (PROCESS_NEWROOTBUFFER),
085      Phase.scheduleMutator    (PROCESS_DECBUFFER),
086      Phase.scheduleGlobal     (PROCESS_DECBUFFER),
087      Phase.scheduleCollector  (PROCESS_DECBUFFER),
088      Phase.scheduleGlobal     (BT_CLOSURE),
089      Phase.scheduleCollector  (BT_CLOSURE));
090
091  /**
092   * Perform the initial determination of liveness from the roots.
093   */
094  protected static final short refCountRootClosurePhase = Phase.createComplex("initial-closure", null,
095      Phase.scheduleMutator    (PREPARE),
096      Phase.scheduleGlobal     (PREPARE),
097      Phase.scheduleCollector  (PREPARE),
098      Phase.scheduleComplex    (prepareStacks),
099      Phase.scheduleCollector  (STACK_ROOTS),
100      Phase.scheduleCollector  (ROOTS),
101      Phase.scheduleGlobal     (ROOTS),
102      Phase.scheduleGlobal     (CLOSURE),
103      Phase.scheduleCollector  (CLOSURE));
104
105  protected static final short genRCRootClosurePhase = Phase.createComplex("initial-closure", null,
106      Phase.scheduleMutator    (PREPARE),
107      Phase.scheduleGlobal     (PREPARE),
108      Phase.scheduleCollector  (PREPARE),
109      Phase.scheduleComplex    (prepareStacks),
110      Phase.scheduleCollector  (STACK_ROOTS),
111      Phase.scheduleCollector  (ROOTS),
112      Phase.scheduleGlobal     (ROOTS),
113      Phase.scheduleMutator    (PROCESS_MODBUFFER),
114      Phase.scheduleGlobal     (PROCESS_MODBUFFER),
115      Phase.scheduleCollector  (PROCESS_MODBUFFER),
116      Phase.scheduleGlobal     (CLOSURE),
117      Phase.scheduleCollector  (CLOSURE));
118
119  /**
120   * This is the phase that is executed to perform a collection.
121   */
122  public short refCountCollection = Phase.createComplex("collection", null,
123      Phase.scheduleComplex(initPhase),
124      Phase.scheduleComplex(refCountRootClosurePhase),
125      Phase.scheduleComplex(refCountCollectionPhase),
126      Phase.scheduleComplex(completeClosurePhase),
127      Phase.scheduleComplex(finishPhase));
128
129  public short genRCCollection = Phase.createComplex("collection", null,
130      Phase.scheduleComplex(initPhase),
131      Phase.scheduleComplex(genRCRootClosurePhase),
132      Phase.scheduleComplex(genRCCollectionPhase),
133      Phase.scheduleComplex(completeClosurePhase),
134      Phase.scheduleComplex(finishPhase));
135
136  // CHECKSTYLE:ON
137
138  /*****************************************************************************
139   *
140   * Class fields
141   */
142
143  /**
144   *
145   */
146  public static final ExplicitFreeListSpace rcSpace = new ExplicitFreeListSpace("rc", VMRequest.discontiguous());
147  public static final ExplicitLargeObjectSpace rcloSpace = new ExplicitLargeObjectSpace("rclos", VMRequest.discontiguous());
148
149  public static final int REF_COUNT = rcSpace.getDescriptor();
150  public static final int REF_COUNT_LOS = rcloSpace.getDescriptor();
151
152  public final SharedDeque modPool = new SharedDeque("mod", metaDataSpace, 1);
153  public final SharedDeque decPool = new SharedDeque("dec", metaDataSpace, 1);
154  public final SharedDeque newRootPool = new SharedDeque("newRoot", metaDataSpace, 1);
155  public final SharedDeque oldRootPool = new SharedDeque("oldRoot", metaDataSpace, 1);
156
157  /*****************************************************************************
158   *
159   * Instance fields
160   */
161
162  /**
163   *
164   */
165  public final Trace rootTrace;
166  public final Trace backupTrace;
167  private final BTSweeper rcSweeper;
168  private final BTFreeLargeObjectSweeper loFreeSweeper;
169
170  /**
171   * Constructor
172   */
173  public RCBase() {
174    Options.noReferenceTypes.setDefaultValue(true);
175    Options.noFinalizer.setDefaultValue(true);
176    rootTrace = new Trace(metaDataSpace);
177    backupTrace = new Trace(metaDataSpace);
178    rcSweeper = new BTSweeper();
179    loFreeSweeper = new BTFreeLargeObjectSweeper();
180  }
181
182  @Override
183  @Interruptible
184  public void processOptions() {
185    super.processOptions();
186    if (!Options.noReferenceTypes.getValue()) {
187      VM.assertions.fail("Reference Types are not supported by RC");
188    }
189    if (!Options.noFinalizer.getValue()) {
190      VM.assertions.fail("Finalizers are not supported by RC");
191    }
192  }
193
194  /*****************************************************************************
195   *
196   * Collection
197   */
198
199  /**
200   * @param object an object reference
201   * @return whether the object is subject to collection by reference counting
202   */
203  public static final boolean isRCObject(ObjectReference object) {
204    return !object.isNull() && (Space.isInSpace(REF_COUNT, object) || Space.isInSpace(REF_COUNT_LOS, object));
205  }
206
207  @Override
208  public boolean lastCollectionFullHeap() {
209    return performCycleCollection;
210  }
211
212  @Override
213  public void collectionPhase(short phaseId) {
214    if (phaseId == SET_COLLECTION_KIND) {
215      super.collectionPhase(phaseId);
216      if (CC_ENABLED) {
217        ccForceFull = Options.fullHeapSystemGC.getValue();
218        if (BUILD_FOR_GENRC) performCycleCollection = (collectionAttempt > 1) || emergencyCollection || ccForceFull;
219        else performCycleCollection |= (collectionAttempt > 1) || emergencyCollection || ccForceFull;
220        if (performCycleCollection && Options.verbose.getValue() > 0) Log.write(" [CC] ");
221      }
222      return;
223    }
224
225    if (phaseId == PREPARE) {
226      VM.finalizableProcessor.clear();
227      VM.weakReferences.clear();
228      VM.softReferences.clear();
229      VM.phantomReferences.clear();
230      rootTrace.prepare();
231      rcSpace.prepare();
232      if (CC_BACKUP_TRACE && performCycleCollection) {
233        backupTrace.prepare();
234      }
235      return;
236    }
237
238    if (phaseId == CLOSURE) {
239      rootTrace.prepare();
240      modPool.prepare();
241      return;
242    }
243
244    if (phaseId == BT_CLOSURE) {
245      if (CC_BACKUP_TRACE && performCycleCollection) {
246        backupTrace.prepare();
247      }
248      return;
249    }
250
251    if (phaseId == PROCESS_OLDROOTBUFFER) {
252      oldRootPool.prepare();
253      return;
254    }
255
256    if (phaseId == PROCESS_NEWROOTBUFFER) {
257      newRootPool.prepare();
258      return;
259    }
260
261
262    if (phaseId == PROCESS_MODBUFFER) {
263      modPool.prepare();
264      return;
265    }
266
267    if (phaseId == PROCESS_DECBUFFER) {
268      decPool.prepare();
269      return;
270    }
271
272    if (phaseId == RELEASE) {
273      rootTrace.release();
274      if (CC_BACKUP_TRACE && performCycleCollection) {
275        backupTrace.release();
276        rcSpace.sweepCells(rcSweeper);
277        rcloSpace.sweep(loFreeSweeper);
278      } else {
279        rcSpace.release();
280      }
281      if (!BUILD_FOR_GENRC) performCycleCollection = getPagesAvail() < Options.cycleTriggerThreshold.getPages();
282      return;
283    }
284
285    super.collectionPhase(phaseId);
286  }
287
288  /*****************************************************************************
289   *
290   * Accounting
291   */
292
293  /**
294   * {@inheritDoc}
295   */
296  @Override
297  public int getPagesUsed() {
298    return (rcSpace.reservedPages() + rcloSpace.reservedPages() + super.getPagesUsed());
299  }
300
301  /**
302   * Perform a linear scan across all objects in the heap to check for leaks.
303   */
304  @Override
305  public void sanityLinearScan(LinearScan scan) {
306    //rcSpace.linearScan(scan);
307  }
308
309  @Override
310  public int sanityExpectedRC(ObjectReference object, int sanityRootRC) {
311    if (RCBase.isRCObject(object)) {
312      int fullRC = RCHeader.getRC(object);
313      if (fullRC == 0) {
314        return SanityChecker.DEAD;
315      }
316      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(fullRC >= sanityRootRC);
317      return fullRC - sanityRootRC;
318    }
319    return SanityChecker.ALIVE;
320  }
321
322  @Override
323  @Interruptible
324  protected void registerSpecializedMethods() {
325    super.registerSpecializedMethods();
326  }
327
328  @Override
329  public byte setBuildTimeGCByte(Address object, ObjectReference typeRef, int size) {
330    return (byte) RCHeader.UNLOGGED.toInt();
331  }
332}