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.generational;
014
015 import org.mmtk.plan.*;
016 import org.mmtk.policy.CopySpace;
017 import org.mmtk.policy.Space;
018
019 import org.mmtk.utility.deque.*;
020 import org.mmtk.utility.heap.Map;
021 import org.mmtk.utility.heap.VMRequest;
022 import org.mmtk.utility.Log;
023 import org.mmtk.utility.options.Options;
024 import org.mmtk.utility.sanitychecker.SanityChecker;
025 import org.mmtk.utility.statistics.*;
026
027 import org.mmtk.vm.Collection;
028 import org.mmtk.vm.VM;
029
030 import org.vmmagic.pragma.*;
031 import org.vmmagic.unboxed.*;
032
033 /**
034 * This abstract class implements the core functionality of generic
035 * two-generationa copying collectors. Nursery collections occur when
036 * either the heap is full or the nursery is full. The nursery size
037 * is determined by an optional command line argument. If undefined,
038 * the nursery size is "infinite", so nursery collections only occur
039 * when the heap is full (this is known as a flexible-sized nursery
040 * collector). Thus both fixed and flexible nursery sizes are
041 * supported. Full heap collections occur when the nursery size has
042 * dropped to a statically defined threshold,
043 * <code>NURSERY_THRESHOLD</code><p>
044 *
045 * See also Plan.java for general comments on local vs global plan
046 * classes.
047 */
048 @Uninterruptible
049 public abstract class Gen extends StopTheWorld {
050
051 /*****************************************************************************
052 *
053 * Constants
054 */
055 protected static final float SURVIVAL_ESTIMATE = 0.8f; // est yield
056 protected static final float MATURE_FRACTION = 0.5f; // est yield
057 private static final float WORST_CASE_COPY_EXPANSION = 1.5f; // worst case for addition of one word overhead due to address based hashing
058 public static final boolean IGNORE_REMSETS = false;
059 public static final boolean USE_NON_HEAP_OBJECT_REFERENCE_WRITE_BARRIER = false;
060 public static final boolean USE_OBJECT_BARRIER_FOR_AASTORE = false; // choose between slot and object barriers
061 public static final boolean USE_OBJECT_BARRIER_FOR_PUTFIELD = false; // choose between slot and object barriers
062 public static final boolean USE_OBJECT_BARRIER = USE_OBJECT_BARRIER_FOR_AASTORE || USE_OBJECT_BARRIER_FOR_PUTFIELD;
063
064 /** Fraction of available virtual memory to give to the nursery (if contiguous) */
065 protected static final float NURSERY_VM_FRACTION = 0.15f;
066
067 /** Switch between a contiguous and discontiguous nursery (experimental) */
068 static final boolean USE_DISCONTIGUOUS_NURSERY = false;
069
070 // Allocators
071 public static final int ALLOC_NURSERY = ALLOC_DEFAULT;
072 public static final int ALLOC_MATURE = StopTheWorld.ALLOCATORS + 1;
073 public static final int ALLOC_MATURE_MINORGC = StopTheWorld.ALLOCATORS + 2;
074 public static final int ALLOC_MATURE_MAJORGC = StopTheWorld.ALLOCATORS + 3;
075
076 public static final int SCAN_NURSERY = 0;
077 public static final int SCAN_MATURE = 1;
078
079 /*****************************************************************************
080 *
081 * Class fields
082 */
083
084 /* Statistics */
085 protected static final BooleanCounter fullHeap = new BooleanCounter("majorGC", true, true);
086 private static final Timer fullHeapTime = new Timer("majorGCTime", false, true);
087 protected static final EventCounter wbFast;
088 protected static final EventCounter wbSlow;
089 public static final SizeCounter nurseryMark;
090 public static final SizeCounter nurseryCons;
091
092 /** The nursery space is where all new objects are allocated by default */
093 private static final VMRequest vmRequest = USE_DISCONTIGUOUS_NURSERY ? VMRequest.create() : VMRequest.create(NURSERY_VM_FRACTION, true);
094 public static final CopySpace nurserySpace = new CopySpace("nursery", DEFAULT_POLL_FREQUENCY, false, vmRequest);
095
096 public static final int NURSERY = nurserySpace.getDescriptor();
097 private static final Address NURSERY_START = nurserySpace.getStart();
098
099 /*****************************************************************************
100 *
101 * Instance fields
102 */
103 /* status fields */
104 public boolean gcFullHeap = false;
105 public boolean nextGCFullHeap = false;
106
107 /* The trace object */
108 public final Trace nurseryTrace = new Trace(metaDataSpace);
109
110 /**
111 * Remset pools
112 */
113 public final SharedDeque modbufPool = new SharedDeque("modBufs",metaDataSpace, 1);
114 public final SharedDeque remsetPool = new SharedDeque("remSets",metaDataSpace, 1);
115 public final SharedDeque arrayRemsetPool = new SharedDeque("arrayRemSets",metaDataSpace, 2);
116
117 /*
118 * Class initializer
119 */
120 static {
121 if (GATHER_WRITE_BARRIER_STATS) {
122 wbFast = new EventCounter("wbFast");
123 wbSlow = new EventCounter("wbSlow");
124 } else {
125 wbFast = null;
126 wbSlow = null;
127 }
128 if (Stats.GATHER_MARK_CONS_STATS) {
129 nurseryMark = new SizeCounter("nurseryMark", true, true);
130 nurseryCons = new SizeCounter("nurseryCons", true, true);
131 } else {
132 nurseryMark = null;
133 nurseryCons = null;
134 }
135 }
136
137 /*****************************************************************************
138 *
139 * Collection
140 */
141
142 /**
143 * Force the next collection to be full heap.
144 */
145 public void forceFullHeapCollection() {
146 nextGCFullHeap = true;
147 }
148
149 /**
150 * Perform a (global) collection phase.
151 *
152 * @param phaseId Collection phase to execute.
153 */
154 @NoInline
155 public void collectionPhase(short phaseId) {
156 if (phaseId == SET_COLLECTION_KIND) {
157 super.collectionPhase(phaseId);
158 gcFullHeap = requiresFullHeapCollection();
159 return;
160 }
161
162 if (phaseId == PREPARE) {
163 nurserySpace.prepare(true);
164 if (traceFullHeap()){
165 if (gcFullHeap) {
166 if (Stats.gatheringStats()) fullHeap.set();
167 fullHeapTime.start();
168 }
169 super.collectionPhase(phaseId);
170
171 // we can throw away the remsets (but not modbuf) for a full heap GC
172 remsetPool.clearDeque(1);
173 arrayRemsetPool.clearDeque(2);
174 }
175 return;
176 }
177
178 if (phaseId == CLOSURE) {
179 if (!traceFullHeap()) {
180 nurseryTrace.prepare();
181 }
182 return;
183 }
184 if (phaseId == RELEASE) {
185 nurserySpace.release();
186 modbufPool.clearDeque(1);
187 remsetPool.clearDeque(1);
188 arrayRemsetPool.clearDeque(2);
189 if (!traceFullHeap()) {
190 nurseryTrace.release();
191 } else {
192 super.collectionPhase(phaseId);
193 if (gcFullHeap) fullHeapTime.stop();
194 }
195 nextGCFullHeap = (getPagesAvail() < Options.nurserySize.getMinNursery());
196 return;
197 }
198
199 super.collectionPhase(phaseId);
200 }
201
202 /**
203 * This method controls the triggering of a GC. It is called periodically
204 * during allocation. Returns true to trigger a collection.
205 *
206 * @param spaceFull Space request failed, must recover pages within 'space'.
207 * @return True if a collection is requested by the plan.
208 */
209 public final boolean collectionRequired(boolean spaceFull) {
210 int nurseryPages = nurserySpace.reservedPages();
211
212 if (nurseryPages > Options.nurserySize.getMaxNursery()) {
213 return true;
214 }
215
216 if (virtualMemoryExhausted())
217 return true;
218
219 return super.collectionRequired(spaceFull);
220 }
221
222 /**
223 * Determine if this GC should be a full heap collection.
224 *
225 * @return True is this GC should be a full heap collection.
226 */
227 protected boolean requiresFullHeapCollection() {
228 if (collectionTrigger == Collection.EXTERNAL_GC_TRIGGER && Options.fullHeapSystemGC.getValue()) {
229 return true;
230 }
231
232 if (nextGCFullHeap || collectionAttempt > 1) {
233 // Forces full heap collection
234 return true;
235 }
236
237 if (loSpace.allocationFailed() ||
238 nonMovingSpace.allocationFailed() ||
239 (USE_CODE_SPACE && (largeCodeSpace.allocationFailed() || smallCodeSpace.allocationFailed()))) {
240 // We need space from the nursery
241 return true;
242 }
243
244 if (virtualMemoryExhausted())
245 return true;
246
247 int smallNurseryPages = nurserySpace.committedPages();
248 int smallNurseryYield = (int)((smallNurseryPages << 1) * SURVIVAL_ESTIMATE);
249
250 if (smallNurseryYield < getPagesRequired()) {
251 // Our total yield is insufficent.
252 return true;
253 }
254
255 if (nurserySpace.allocationFailed()) {
256 if (smallNurseryYield < (nurserySpace.requiredPages() << 1)) {
257 // We have run out of VM pages in the nursery
258 return true;
259 }
260 }
261
262
263 return false;
264 }
265
266 /**
267 * Independent of how many pages remain in the page budget (a function of
268 * heap size), we must ensure we never exhaust virtual memory. Therefore
269 * we must never let the nursery grow to the extent that it can't be
270 * copied into the mature space.
271 *
272 * @return True if the nursery has grown to the extent that it may not be
273 * able to be copied into the mature space.
274 */
275 private boolean virtualMemoryExhausted() {
276 return ((int) (nurserySpace.reservedPages()*WORST_CASE_COPY_EXPANSION) >= getMaturePhysicalPagesAvail());
277 }
278
279 /*****************************************************************************
280 *
281 * Correctness
282 */
283
284 /*****************************************************************************
285 *
286 * Accounting
287 */
288
289 /**
290 * Return the number of pages in use given the pending
291 * allocation. Simply add the nursery's contribution to that of
292 * the superclass.
293 *
294 * @return The number of pages reserved given the pending
295 * allocation, excluding space reserved for copying.
296 */
297 @Override
298 public int getPagesUsed() {
299 return (nurserySpace.reservedPages() + super.getPagesUsed());
300 }
301
302 /**
303 * Return the number of pages available for allocation, <i>assuming
304 * all future allocation is to the nursery</i>.
305 *
306 * @return The number of pages available for allocation, <i>assuming
307 * all future allocation is to the nursery</i>.
308 */
309 @Override
310 public int getPagesAvail() {
311 return super.getPagesAvail() >> 1;
312 }
313
314 /**
315 * Return the number of pages reserved for copying.
316 *
317 * @return The number of pages reserved given the pending
318 * allocation, including space reserved for copying.
319 */
320 @Override
321 public int getCollectionReserve() {
322 return nurserySpace.reservedPages() + super.getCollectionReserve();
323 }
324
325 /**
326 * Return the number of pages available for allocation into the mature
327 * space.
328 *
329 * @return The number of pages available for allocation into the mature
330 * space.
331 */
332 public abstract int getMaturePhysicalPagesAvail();
333
334 /**
335 * Calculate the number of pages a collection is required to free to satisfy
336 * outstanding allocation requests.
337 *
338 * @return the number of pages a collection is required to free to satisfy
339 * outstanding allocation requests.
340 */
341 @Override
342 public int getPagesRequired() {
343 /* We don't currently pretenure, so mature space must be zero */
344 return super.getPagesRequired() + (nurserySpace.requiredPages() << 1);
345 }
346
347 /*****************************************************************************
348 *
349 * Miscellaneous
350 */
351
352 /**
353 * Return true if the address resides within the nursery
354 *
355 * @param addr The object to be tested
356 * @return true if the address resides within the nursery
357 */
358 @Inline
359 static boolean inNursery(Address addr) {
360 if (USE_DISCONTIGUOUS_NURSERY)
361 return Map.getDescriptorForAddress(addr) == NURSERY;
362 else
363 return addr.GE(NURSERY_START);
364 }
365
366 /**
367 * Return true if the object resides within the nursery
368 *
369 * @param obj The object to be tested
370 * @return true if the object resides within the nursery
371 */
372 @Inline
373 static boolean inNursery(ObjectReference obj) {
374 return inNursery(obj.toAddress());
375 }
376
377 /**
378 * @return Does the mature space do copying ?
379 */
380 protected boolean copyMature() {
381 return false;
382 }
383
384 /**
385 * Print pre-collection statistics. In this class we prefix the output
386 * indicating whether the collection was full heap or not.
387 */
388 public void printPreStats() {
389 if ((Options.verbose.getValue() >= 1) && (gcFullHeap))
390 Log.write("[Full heap]");
391 super.printPreStats();
392 }
393
394 /**
395 * @return The mature space, set by each subclass of <code>Gen</code>.
396 */
397 protected abstract Space activeMatureSpace();
398
399 /**
400 * @return True if we should trace the whole heap during collection. True if
401 * we're ignorning remsets or if we're doing a full heap GC.
402 */
403 public final boolean traceFullHeap() {
404 return IGNORE_REMSETS || gcFullHeap;
405 }
406
407 /**
408 * @return Is current GC only collecting objects allocated since last GC.
409 */
410 public final boolean isCurrentGCNursery() {
411 return !gcFullHeap;
412 }
413
414 /**
415 * @return Is last GC a full collection?
416 */
417 public final boolean lastCollectionFullHeap() {
418 return gcFullHeap;
419 }
420
421 /**
422 * @see org.mmtk.plan.Plan#willNeverMove
423 *
424 * @param object Object in question
425 * @return True if the object will never move
426 */
427 @Override
428 public boolean willNeverMove(ObjectReference object) {
429 if (Space.isInSpace(NURSERY, object))
430 return false;
431 return super.willNeverMove(object);
432 }
433
434 /**
435 * Return the expected reference count. For non-reference counting
436 * collectors this becomes a true/false relationship.
437 *
438 * @param object The object to check.
439 * @param sanityRootRC The number of root references to the object.
440 * @return The expected (root excluded) reference count.
441 */
442 public int sanityExpectedRC(ObjectReference object, int sanityRootRC) {
443 Space space = Space.getSpaceForObject(object);
444
445 // Nursery
446 if (space == Gen.nurserySpace) {
447 return SanityChecker.DEAD;
448 }
449
450 // Immortal spaces
451 if (space == Gen.immortalSpace || space == Gen.vmSpace) {
452 return space.isReachable(object) ? SanityChecker.ALIVE : SanityChecker.DEAD;
453 }
454
455 // Mature space (nursery collection)
456 if (VM.activePlan.global().isCurrentGCNursery()) {
457 return SanityChecker.UNSURE;
458 }
459
460 // Mature space (full heap collection)
461 return space.isReachable(object) ? SanityChecker.ALIVE : SanityChecker.DEAD;
462 }
463
464 /**
465 * Register specialized methods.
466 */
467 @Interruptible
468 protected void registerSpecializedMethods() {
469 TransitiveClosure.registerSpecializedScan(SCAN_NURSERY, GenNurseryTraceLocal.class);
470 super.registerSpecializedMethods();
471 }
472 }