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 */
013 package org.mmtk.plan.refcount;
014
015 import org.mmtk.plan.Phase;
016 import org.mmtk.plan.StopTheWorld;
017 import org.mmtk.plan.Trace;
018 import org.mmtk.plan.refcount.backuptrace.BTFreeLargeObjectSweeper;
019 import org.mmtk.plan.refcount.backuptrace.BTSweeper;
020 import org.mmtk.policy.ExplicitFreeListSpace;
021 import org.mmtk.policy.ExplicitLargeObjectSpace;
022 import org.mmtk.policy.Space;
023 import org.mmtk.utility.Log;
024 import org.mmtk.utility.alloc.LinearScan;
025 import org.mmtk.utility.deque.SharedDeque;
026 import org.mmtk.utility.heap.VMRequest;
027 import org.mmtk.utility.options.Options;
028 import org.mmtk.utility.sanitychecker.SanityChecker;
029 import org.mmtk.vm.VM;
030
031 import org.vmmagic.pragma.*;
032 import 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
042 public 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.create());
147 public static final ExplicitLargeObjectSpace rcloSpace = new ExplicitLargeObjectSpace("rclos", VMRequest.create());
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 *
201 */
202 public static final boolean isRCObject(ObjectReference object) {
203 return !object.isNull() && (Space.isInSpace(REF_COUNT, object) || Space.isInSpace(REF_COUNT_LOS, object));
204 }
205
206 @Override
207 public boolean lastCollectionFullHeap() {
208 return performCycleCollection;
209 }
210
211 @Override
212 public void collectionPhase(short phaseId) {
213 if (phaseId == SET_COLLECTION_KIND) {
214 super.collectionPhase(phaseId);
215 if (CC_ENABLED) {
216 ccForceFull = Options.fullHeapSystemGC.getValue();
217 if (BUILD_FOR_GENRC) performCycleCollection = (collectionAttempt > 1) || emergencyCollection || ccForceFull;
218 else performCycleCollection |= (collectionAttempt > 1) || emergencyCollection || ccForceFull;
219 if (performCycleCollection && Options.verbose.getValue() > 0) Log.write(" [CC] ");
220 }
221 return;
222 }
223
224 if (phaseId == PREPARE) {
225 VM.finalizableProcessor.clear();
226 VM.weakReferences.clear();
227 VM.softReferences.clear();
228 VM.phantomReferences.clear();
229 rootTrace.prepare();
230 rcSpace.prepare();
231 if (CC_BACKUP_TRACE && performCycleCollection) {
232 backupTrace.prepare();
233 }
234 return;
235 }
236
237 if (phaseId == CLOSURE) {
238 rootTrace.prepare();
239 modPool.prepare();
240 return;
241 }
242
243 if (phaseId == BT_CLOSURE) {
244 if (CC_BACKUP_TRACE && performCycleCollection) {
245 backupTrace.prepare();
246 }
247 return;
248 }
249
250 if (phaseId == PROCESS_OLDROOTBUFFER) {
251 oldRootPool.prepare();
252 return;
253 }
254
255 if (phaseId == PROCESS_NEWROOTBUFFER) {
256 newRootPool.prepare();
257 return;
258 }
259
260
261 if (phaseId == PROCESS_MODBUFFER) {
262 modPool.prepare();
263 return;
264 }
265
266 if (phaseId == PROCESS_DECBUFFER) {
267 decPool.prepare();
268 return;
269 }
270
271 if (phaseId == RELEASE) {
272 rootTrace.release();
273 if (CC_BACKUP_TRACE && performCycleCollection) {
274 backupTrace.release();
275 rcSpace.sweepCells(rcSweeper);
276 rcloSpace.sweep(loFreeSweeper);
277 } else {
278 rcSpace.release();
279 }
280 if (!BUILD_FOR_GENRC) performCycleCollection = getPagesAvail() < Options.cycleTriggerThreshold.getPages();
281 return;
282 }
283
284 super.collectionPhase(phaseId);
285 }
286
287 /*****************************************************************************
288 *
289 * Accounting
290 */
291
292 /**
293 * {@inheritDoc}
294 */
295 @Override
296 public int getPagesUsed() {
297 return (rcSpace.reservedPages() + rcloSpace.reservedPages() + super.getPagesUsed());
298 }
299
300 /**
301 * Perform a linear scan across all objects in the heap to check for leaks.
302 */
303 @Override
304 public void sanityLinearScan(LinearScan scan) {
305 //rcSpace.linearScan(scan);
306 }
307
308 @Override
309 public int sanityExpectedRC(ObjectReference object, int sanityRootRC) {
310 if (RCBase.isRCObject(object)) {
311 int fullRC = RCHeader.getRC(object);
312 if (fullRC == 0) {
313 return SanityChecker.DEAD;
314 }
315 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(fullRC >= sanityRootRC);
316 return fullRC - sanityRootRC;
317 }
318 return SanityChecker.ALIVE;
319 }
320
321 @Override
322 @Interruptible
323 protected void registerSpecializedMethods() {
324 super.registerSpecializedMethods();
325 }
326 }