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.Plan;
017import org.mmtk.plan.StopTheWorldCollector;
018import org.mmtk.plan.TraceLocal;
019import org.mmtk.plan.TransitiveClosure;
020import org.mmtk.plan.refcount.backuptrace.BTTraceLocal;
021import org.mmtk.policy.Space;
022import org.mmtk.policy.ExplicitFreeListSpace;
023import org.mmtk.utility.deque.ObjectReferenceDeque;
024import org.mmtk.vm.VM;
025import org.vmmagic.pragma.Inline;
026import org.vmmagic.pragma.Uninterruptible;
027import org.vmmagic.unboxed.ObjectReference;
028
029/**
030 * This class implements the collector context for a reference counting collector.
031 * See Shahriyar et al for details of and rationale for the optimizations used
032 * here (http://dx.doi.org/10.1145/2258996.2259008).  See Chapter 4 of
033 * Daniel Frampton's PhD thesis for details of and rationale for the cycle
034 * collection strategy used by this collector.
035 */
036@Uninterruptible
037public abstract class RCBaseCollector extends StopTheWorldCollector {
038
039  /************************************************************************
040   * Initialization
041   */
042
043  /**
044   *
045   */
046  protected final ObjectReferenceDeque newRootBuffer;
047  private final BTTraceLocal backupTrace;
048  private final ObjectReferenceDeque modBuffer;
049  private final ObjectReferenceDeque oldRootBuffer;
050  private final RCDecBuffer decBuffer;
051  private final RCZero zero;
052
053  /**
054   * Constructor.
055   */
056  public RCBaseCollector() {
057    newRootBuffer = new ObjectReferenceDeque("new-root", global().newRootPool);
058    oldRootBuffer = new ObjectReferenceDeque("old-root", global().oldRootPool);
059    modBuffer = new ObjectReferenceDeque("mod buf", global().modPool);
060    decBuffer = new RCDecBuffer(global().decPool);
061    backupTrace = new BTTraceLocal(global().backupTrace);
062    zero = new RCZero();
063  }
064
065  /**
066   * @return the modified processor to use.
067   */
068  protected abstract TransitiveClosure getModifiedProcessor();
069
070  /**
071   * @return the root trace to use.
072   */
073  protected abstract TraceLocal getRootTrace();
074
075  /****************************************************************************
076   *
077   * Collection
078   */
079
080  /**
081   * {@inheritDoc}
082   */
083  @Override
084  public void collect() {
085    if (RCBase.BUILD_FOR_GENRC) Phase.beginNewPhaseStack(Phase.scheduleComplex(global().genRCCollection));
086    else Phase.beginNewPhaseStack(Phase.scheduleComplex(global().refCountCollection));
087  }
088
089  @Override
090  public void collectionPhase(short phaseId, boolean primary) {
091    if (phaseId == RCBase.PREPARE) {
092      getRootTrace().prepare();
093      if (RCBase.CC_BACKUP_TRACE && RCBase.performCycleCollection) backupTrace.prepare();
094      return;
095    }
096
097    if (phaseId == RCBase.ROOTS) {
098      VM.scanning.computeGlobalRoots(getCurrentTrace());
099      VM.scanning.computeStaticRoots(getCurrentTrace());
100      if (Plan.SCAN_BOOT_IMAGE && RCBase.CC_BACKUP_TRACE && RCBase.performCycleCollection) {
101        VM.scanning.computeBootImageRoots(getCurrentTrace());
102      }
103      return;
104    }
105
106    if (phaseId == RCBase.CLOSURE) {
107      getRootTrace().completeTrace();
108      newRootBuffer.flushLocal();
109      return;
110    }
111
112    if (phaseId == RCBase.BT_CLOSURE) {
113      if (RCBase.CC_BACKUP_TRACE && RCBase.performCycleCollection) {
114        backupTrace.completeTrace();
115      }
116      return;
117    }
118
119    if (phaseId == RCBase.PROCESS_OLDROOTBUFFER) {
120      if (RCBase.CC_BACKUP_TRACE && RCBase.performCycleCollection) return;
121      ObjectReference current;
122      while ((!(current = oldRootBuffer.pop()).isNull())) {
123        decBuffer.push(current);
124      }
125      return;
126    }
127
128    if (phaseId == RCBase.PROCESS_NEWROOTBUFFER) {
129      ObjectReference current;
130      if (RCBase.CC_BACKUP_TRACE && RCBase.performCycleCollection) {
131        while (!(current = newRootBuffer.pop()).isNull()) {
132          if (RCHeader.testAndMark(current)) {
133            if (RCBase.BUILD_FOR_GENRC) {
134              RCHeader.initRC(current);
135            } else {
136              if (RCHeader.initRC(current) == RCHeader.INC_NEW) {
137                modBuffer.push(current);
138              }
139            }
140            backupTrace.processNode(current);
141          } else {
142            if (RCBase.BUILD_FOR_GENRC) {
143              RCHeader.incRC(current);
144            } else {
145              if (RCHeader.incRC(current) == RCHeader.INC_NEW) {
146                modBuffer.push(current);
147              }
148            }
149          }
150        }
151        if (!RCBase.BUILD_FOR_GENRC) modBuffer.flushLocal();
152        return;
153      }
154      while (!(current = newRootBuffer.pop()).isNull()) {
155        if (RCBase.BUILD_FOR_GENRC) {
156          RCHeader.incRC(current);
157        } else {
158          if (RCHeader.incRC(current) == RCHeader.INC_NEW) {
159            modBuffer.push(current);
160          }
161        }
162        oldRootBuffer.push(current);
163      }
164      oldRootBuffer.flushLocal();
165      if (!RCBase.BUILD_FOR_GENRC) modBuffer.flushLocal();
166      return;
167    }
168
169    if (phaseId == RCBase.PROCESS_MODBUFFER) {
170      ObjectReference current;
171      while (!(current = modBuffer.pop()).isNull()) {
172        RCHeader.makeUnlogged(current);
173        if (!RCBase.BUILD_FOR_GENRC) {
174          if (Space.isInSpace(RCBase.REF_COUNT, current)) {
175            ExplicitFreeListSpace.testAndSetLiveBit(current);
176          }
177        }
178        VM.scanning.scanObject(getModifiedProcessor(), current);
179      }
180      return;
181    }
182
183    if (phaseId == RCBase.PROCESS_DECBUFFER) {
184      ObjectReference current;
185      if (RCBase.CC_BACKUP_TRACE && RCBase.performCycleCollection) {
186        if (!RCBase.BUILD_FOR_GENRC) {
187          while (!(current = decBuffer.pop()).isNull()) {
188            if (RCHeader.isNew(current)) {
189              if (Space.isInSpace(RCBase.REF_COUNT, current)) {
190                RCBase.rcSpace.free(current);
191              } else if (Space.isInSpace(RCBase.REF_COUNT_LOS, current)) {
192                RCBase.rcloSpace.free(current);
193              } else if (Space.isInSpace(RCBase.IMMORTAL, current)) {
194                VM.scanning.scanObject(zero, current);
195              }
196            }
197          }
198        }
199        return;
200      }
201      while (!(current = decBuffer.pop()).isNull()) {
202        if (RCBase.BUILD_FOR_GENRC) {
203          if (RCHeader.decRC(current) == RCHeader.DEC_KILL) {
204            decBuffer.processChildren(current);
205            if (Space.isInSpace(RCBase.REF_COUNT, current)) {
206              RCBase.rcSpace.free(current);
207            } else if (Space.isInSpace(RCBase.REF_COUNT_LOS, current)) {
208              RCBase.rcloSpace.free(current);
209            } else if (Space.isInSpace(RCBase.IMMORTAL, current)) {
210              VM.scanning.scanObject(zero, current);
211            }
212          }
213        } else {
214          if (RCHeader.isNew(current)) {
215            if (Space.isInSpace(RCBase.REF_COUNT, current)) {
216              RCBase.rcSpace.free(current);
217            } else if (Space.isInSpace(RCBase.REF_COUNT_LOS, current)) {
218              RCBase.rcloSpace.free(current);
219            } else if (Space.isInSpace(RCBase.IMMORTAL, current)) {
220              VM.scanning.scanObject(zero, current);
221            }
222          } else {
223            if (RCHeader.decRC(current) == RCHeader.DEC_KILL) {
224              decBuffer.processChildren(current);
225              if (Space.isInSpace(RCBase.REF_COUNT, current)) {
226                RCBase.rcSpace.free(current);
227              } else if (Space.isInSpace(RCBase.REF_COUNT_LOS, current)) {
228                RCBase.rcloSpace.free(current);
229              } else if (Space.isInSpace(RCBase.IMMORTAL, current)) {
230                VM.scanning.scanObject(zero, current);
231              }
232            }
233          }
234        }
235      }
236      return;
237    }
238
239    if (phaseId == RCBase.RELEASE) {
240      if (RCBase.CC_BACKUP_TRACE && RCBase.performCycleCollection) {
241        backupTrace.release();
242        global().oldRootPool.clearDeque(1);
243        if (RCBase.BUILD_FOR_GENRC) global().decPool.clearDeque(1);
244      }
245      getRootTrace().release();
246      if (VM.VERIFY_ASSERTIONS) {
247        VM.assertions._assert(newRootBuffer.isEmpty());
248        VM.assertions._assert(modBuffer.isEmpty());
249        VM.assertions._assert(decBuffer.isEmpty());
250      }
251      return;
252    }
253
254    super.collectionPhase(phaseId, primary);
255  }
256
257  /****************************************************************************
258   *
259   * Miscellaneous
260   */
261
262  /** @return The active global plan as an <code>RC</code> instance. */
263  @Inline
264  protected static RCBase global() {
265    return (RCBase) VM.activePlan.global();
266  }
267
268  @Override
269  public final TraceLocal getCurrentTrace() {
270    return getRootTrace();
271  }
272
273  /** @return The current modBuffer instance. */
274  @Inline
275  public final ObjectReferenceDeque getModBuffer() {
276    return modBuffer;
277  }
278}