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;
014
015 import org.mmtk.policy.Space;
016 import org.mmtk.utility.Constants;
017 import org.mmtk.utility.Log;
018 import org.mmtk.utility.deque.*;
019 import org.mmtk.utility.options.Options;
020
021 import org.mmtk.vm.VM;
022
023 import org.vmmagic.pragma.*;
024 import org.vmmagic.unboxed.*;
025
026 /**
027 * This abstract class and its global counterpart implement the core
028 * functionality for a transitive closure over the heap graph. This class
029 * specifically implements the unsynchronized thread-local component
030 * (ie the 'fast path') of the trace mechanism.<p>
031 *
032 * @see org.mmtk.plan.Plan
033 * @see org.mmtk.plan.Trace
034 */
035 @Uninterruptible
036 public abstract class TraceLocal extends TransitiveClosure implements Constants {
037 /****************************************************************************
038 *
039 * Instance variables
040 */
041
042 /** gray objects */
043 protected final ObjectReferenceDeque values;
044 /** delayed root slots */
045 protected final AddressDeque rootLocations;
046
047 /****************************************************************************
048 *
049 * Initialization
050 */
051
052 /**
053 * Constructor
054 *
055 * @param trace The global trace class to use.
056 */
057 public TraceLocal(Trace trace) {
058 this(-1, trace);
059 }
060
061 /**
062 * Constructor
063 *
064 * @param specializedScan The specialized scan id.
065 * @param trace The global trace class to use.
066 */
067 public TraceLocal(int specializedScan, Trace trace) {
068 super(specializedScan);
069 values = new ObjectReferenceDeque("value", trace.valuePool);
070 rootLocations = new AddressDeque("roots", trace.rootLocationPool);
071 }
072
073 /****************************************************************************
074 *
075 * Internally visible Object processing and tracing
076 */
077
078 /**
079 * Should reference values be overwritten as the heap is traced?
080 */
081 protected boolean overwriteReferenceDuringTrace() {
082 return true;
083 }
084
085 /**
086 * Trace a reference during GC. This involves determining which
087 * collection policy applies and calling the appropriate
088 * <code>trace</code> method.
089 *
090 * @param source The source of the reference.
091 * @param slot The location containing the object reference to be
092 * traced. The object reference is <i>NOT</i> an interior pointer.
093 */
094 @Override
095 @Inline
096 public final void processEdge(ObjectReference source, Address slot) {
097 ObjectReference object = VM.activePlan.global().loadObjectReference(slot);
098 ObjectReference newObject = traceObject(object, false);
099 if (overwriteReferenceDuringTrace()) {
100 VM.activePlan.global().storeObjectReference(slot, newObject);
101 }
102 }
103
104 /**
105 * Report a root edge to be processed during GC. As the given reference
106 * may theoretically point to an object required during root scanning,
107 * the caller has requested processing be delayed.
108 *
109 * NOTE: delayed roots are assumed to be raw.
110 *
111 * @param slot The location containing the object reference to be
112 * traced. The object reference is <i>NOT</i> an interior pointer.
113 */
114 @Inline
115 public final void reportDelayedRootEdge(Address slot) {
116 rootLocations.push(slot);
117 }
118
119 /**
120 * Trace a reference during GC. This involves determining which
121 * collection policy applies and calling the appropriate
122 * <code>trace</code> method.
123 *
124 * @param slot The location containing the object reference to be
125 * traced. The object reference is <i>NOT</i> an interior pointer.
126 * @param untraced <code>true</code> if <code>objLoc</code> is an untraced root.
127 */
128 @Inline
129 public final void processRootEdge(Address slot, boolean untraced) {
130 ObjectReference object;
131 if (untraced) object = slot.loadObjectReference();
132 else object = VM.activePlan.global().loadObjectReference(slot);
133 ObjectReference newObject = traceObject(object, true);
134 if (overwriteReferenceDuringTrace()) {
135 if (untraced) slot.store(newObject);
136 else VM.activePlan.global().storeObjectReference(slot, newObject);
137 }
138 }
139
140 /**
141 * Trace a reference during GC. This involves determining which
142 * collection policy applies and calling the appropriate
143 * <code>trace</code> method.
144 *
145 * @param target The object the interior edge points within.
146 * @param slot The location of the interior edge.
147 * @param root <code>true</code> if this is a root edge.
148 */
149 public final void processInteriorEdge(ObjectReference target, Address slot, boolean root) {
150 Address interiorRef = slot.loadAddress();
151 Offset offset = interiorRef.diff(target.toAddress());
152 ObjectReference newTarget = traceObject(target, root);
153 if (VM.VERIFY_ASSERTIONS) {
154 if (offset.sLT(Offset.zero()) || offset.sGT(Offset.fromIntSignExtend(1<<24))) {
155 // There is probably no object this large
156 Log.writeln("ERROR: Suspiciously large delta to interior pointer");
157 Log.write(" object base = "); Log.writeln(target);
158 Log.write(" interior reference = "); Log.writeln(interiorRef);
159 Log.write(" delta = "); Log.writeln(offset);
160 VM.assertions._assert(false);
161 }
162 }
163 if (overwriteReferenceDuringTrace()) {
164 slot.store(newTarget.toAddress().plus(offset));
165 }
166 }
167
168 /**
169 * Collectors that move objects <b>must</b> override this method.
170 * It performs the deferred scanning of objects which are forwarded
171 * during bootstrap of each copying collection. Because of the
172 * complexities of the collection bootstrap (such objects are
173 * generally themselves gc-critical), the forwarding and scanning of
174 * the objects must be dislocated. It is an error for a non-moving
175 * collector to call this method.
176 *
177 * @param object The forwarded object to be scanned
178 */
179 @Inline
180 protected void scanObject(ObjectReference object) {
181 if (specializedScan >= 0) {
182 VM.scanning.specializedScanObject(specializedScan, this, object);
183 } else {
184 VM.scanning.scanObject(this, object);
185 }
186 }
187
188
189 /****************************************************************************
190 *
191 * Externally visible Object processing and tracing
192 */
193
194 /**
195 * Add a gray object
196 *
197 * @param object The object to be enqueued
198 */
199 @Override
200 @Inline
201 public final void processNode(ObjectReference object) {
202 values.push(object);
203 }
204
205 /**
206 * Flush the local buffers of all deques.
207 */
208 public final void flush() {
209 values.flushLocal();
210 rootLocations.flushLocal();
211 }
212
213 /**
214 * Is the specified object live?
215 *
216 * @param object The object.
217 * @return {@code true} if the object is live.
218 */
219 @Inline
220 public boolean isLive(ObjectReference object) {
221 Space space = Space.getSpaceForObject(object);
222 if (space == Plan.loSpace)
223 return Plan.loSpace.isLive(object);
224 else if (space == Plan.nonMovingSpace)
225 return Plan.nonMovingSpace.isLive(object);
226 else if (Plan.USE_CODE_SPACE && space == Plan.smallCodeSpace)
227 return Plan.smallCodeSpace.isLive(object);
228 else if (Plan.USE_CODE_SPACE && space == Plan.largeCodeSpace)
229 return Plan.largeCodeSpace.isLive(object);
230 else if (space == null) {
231 if (VM.VERIFY_ASSERTIONS) {
232 Log.write("space failure: "); Log.writeln(object);
233 }
234 }
235 return true;
236 }
237
238 /**
239 * Is the specified object reachable? Used for GC Trace
240 *
241 * @param object The object.
242 * @return {@code true} if the object is live.
243 */
244 @Inline
245 public boolean isReachable(ObjectReference object) {
246 return Space.getSpaceForObject(object).isReachable(object);
247 }
248
249 /**
250 * Is the specified referent of a reference type object live?
251 *
252 * @param object The object.
253 * @return {@code true} if the reference object is live.
254 */
255 @Inline
256 public boolean isReferentLive(ObjectReference object) {
257 return isLive(object);
258 }
259
260 /**
261 * This method is the core method during the trace of the object graph.
262 * The role of this method is to:
263 *
264 * <ol>
265 * <li>Ensure the traced object is not collected.</li>
266 * <li>If this is the first visit to the object enqueue it to be scanned.</li>
267 * <li>Return the forwarded reference to the object.</li>
268 * </ol>
269 *
270 * @param object The object to be traced.
271 * @return The new reference to the same object instance.
272 */
273 @Inline
274 public ObjectReference traceObject(ObjectReference object) {
275 if (Space.isInSpace(Plan.VM_SPACE, object))
276 return (Plan.SCAN_BOOT_IMAGE) ? object : Plan.vmSpace.traceObject(this, object);
277 if (Space.isInSpace(Plan.IMMORTAL, object))
278 return Plan.immortalSpace.traceObject(this, object);
279 if (Space.isInSpace(Plan.LOS, object))
280 return Plan.loSpace.traceObject(this, object);
281 if (Space.isInSpace(Plan.NON_MOVING, object))
282 return Plan.nonMovingSpace.traceObject(this, object);
283 if (Plan.USE_CODE_SPACE && Space.isInSpace(Plan.SMALL_CODE, object))
284 return Plan.smallCodeSpace.traceObject(this, object);
285 if (Plan.USE_CODE_SPACE && Space.isInSpace(Plan.LARGE_CODE, object))
286 return Plan.largeCodeSpace.traceObject(this, object);
287 if (VM.VERIFY_ASSERTIONS) {
288 Log.write("Failing object => "); Log.writeln(object);
289 Space.printVMMap();
290 VM.assertions._assert(false, "No special case for space in traceObject");
291 }
292 return ObjectReference.nullReference();
293 }
294
295 /**
296 * This method traces an object with knowledge of the fact that object
297 * is a root or not. In simple collectors the fact it is a root is not
298 * important so this is the default implementation given here.
299 *
300 * @param object The object to be traced.
301 * @param root Is this object a root?
302 * @return The new reference to the same object instance.
303 */
304 @Inline
305 public ObjectReference traceObject(ObjectReference object, boolean root) {
306 return traceObject(object);
307 }
308
309 /**
310 * Ensure that the referenced object will not move from this point through
311 * to the end of the collection. This can involve forwarding the object
312 * if necessary.
313 *
314 * <i>Non-copying collectors do nothing, copying collectors must
315 * override this method in each of their trace classes.</i>
316 *
317 * @param object The object that must not move during the collection.
318 * @return {@code true} If the object will not move during collection
319 */
320 public boolean willNotMoveInCurrentCollection(ObjectReference object) {
321 if (!VM.activePlan.constraints().movesObjects())
322 return true;
323 if (Space.isInSpace(Plan.LOS, object))
324 return true;
325 if (Space.isInSpace(Plan.IMMORTAL, object))
326 return true;
327 if (Space.isInSpace(Plan.VM_SPACE, object))
328 return true;
329 if (Space.isInSpace(Plan.NON_MOVING, object))
330 return true;
331 if (Plan.USE_CODE_SPACE && Space.isInSpace(Plan.SMALL_CODE, object))
332 return true;
333 if (Plan.USE_CODE_SPACE && Space.isInSpace(Plan.LARGE_CODE, object))
334 return true;
335 if (VM.VERIFY_ASSERTIONS)
336 VM.assertions._assert(false, "willNotMove not defined properly in subclass");
337 return false;
338 }
339
340 /**
341 * If a Finalizable object has moved, return the new location.
342 *
343 * @param object The object which may have been forwarded.
344 * @return The new location of <code>object</code>.
345 */
346 public ObjectReference getForwardedFinalizable(ObjectReference object) {
347 return getForwardedReference(object);
348 }
349
350 /**
351 * If the reference object (from a Reference Type) has object has moved,
352 * return the new location.
353 *
354 * @param object The object which may have been forwarded.
355 * @return The new location of <code>object</code>.
356 */
357 @Inline
358 public ObjectReference getForwardedReferent(ObjectReference object) {
359 return getForwardedReference(object);
360 }
361
362 /**
363 * If the Reference Type object has moved, return the new location.
364 *
365 * @param object The object which may have been forwarded.
366 * @return The new location of <code>object</code>.
367 */
368 @Inline
369 public ObjectReference getForwardedReferenceType(ObjectReference object) {
370 return getForwardedReference(object);
371 }
372
373 /**
374 * If the referenced object has moved, return the new location.
375 *
376 * Some copying collectors will need to override this method.
377 *
378 * @param object The object which may have been forwarded.
379 * @return The new location of <code>object</code>.
380 */
381 @Inline
382 public ObjectReference getForwardedReference(ObjectReference object) {
383 return traceObject(object);
384 }
385
386 /**
387 * Make alive a referent object that is known not to be live
388 * (isLive is false). This is used by the ReferenceProcessor.
389 *
390 * <i>For many collectors these semantics reflect those of
391 * <code>traceObject</code>, which is implemented here. Other
392 * collectors must override this method.</i>
393 *
394 * @param object The object which is to be made alive.
395 * @return The possibly forwarded address of the object.
396 */
397 @Inline
398 public ObjectReference retainReferent(ObjectReference object) {
399 return traceObject(object);
400 }
401
402 /**
403 * An object is unreachable and is about to be added to the
404 * finalizable queue. The collector must ensure the object is not
405 * collected (despite being otherwise unreachable), and should
406 * return its forwarded address if keeping the object alive involves
407 * forwarding. This is only ever called once for an object.<p>
408 *
409 * <i>For many collectors these semantics reflect those of
410 * <code>traceObject</code>, which is implemented here. Other
411 * collectors must override this method.</i>
412 *
413 * @param object The object which may have been forwarded.
414 * @return The forwarded value for <code>object</code>. <i>In this
415 * case return <code>object</code>, copying collectors must override
416 * this method.
417 */
418 public ObjectReference retainForFinalize(ObjectReference object) {
419 return traceObject(object);
420 }
421
422 /**
423 * Return true if an object is ready to move to the finalizable
424 * queue, i.e. it has no regular references to it. This method may
425 * (and in some cases is) be overridden by subclasses. If this method
426 * returns true then it can be assumed that retainForFinalize will be
427 * called during the current collection.
428 *
429 * <i>For many collectors these semantics reflect those of
430 * <code>isLive</code>, which is implemented here. Other
431 * collectors must override this method.</i>
432 *
433 * @param object The object being queried.
434 * @return <code>true</code> if the object has no regular references
435 * to it.
436 */
437 public boolean readyToFinalize(ObjectReference object) {
438 return !isLive(object);
439 }
440
441 /****************************************************************************
442 *
443 * Collection
444 *
445 * Important notes:
446 * . Global actions are executed by only one thread
447 * . Thread-local actions are executed by all threads
448 * . The following order is guaranteed by BasePlan, with each
449 * separated by a synchronization barrier.
450 * 1. globalPrepare()
451 * 2. threadLocalPrepare()
452 * 3. threadLocalRelease()
453 * 4. globalRelease()
454 */
455
456 /**
457 * TODO write JavaDoc comment
458 */
459 public void prepare() {
460 // Nothing to do
461 }
462
463 public void release() {
464 values.reset();
465 rootLocations.reset();
466 }
467
468 /**
469 * Process any roots for which processing was delayed.
470 */
471 @Inline
472 public void processRoots() {
473 logMessage(5, "processing delayed root objects");
474 while (!rootLocations.isEmpty()) {
475 processRootEdge(rootLocations.pop(), true);
476 }
477 }
478
479 /**
480 * Finishing processing all GC work. This method iterates until all work queues
481 * are empty.
482 */
483 @Inline
484 public void completeTrace() {
485 logMessage(4, "Processing GC in parallel");
486 if (!rootLocations.isEmpty()) {
487 processRoots();
488 }
489 logMessage(5, "processing gray objects");
490 assertMutatorRemsetsFlushed();
491 do {
492 while (!values.isEmpty()) {
493 ObjectReference v = values.pop();
494 scanObject(v);
495 }
496 processRememberedSets();
497 } while (!values.isEmpty());
498 assertMutatorRemsetsFlushed();
499 }
500
501 /**
502 * Process GC work until either complete or workLimit
503 * units of work are completed.
504 *
505 * @param workLimit The maximum units of work to perform.
506 * @return <code>true</code> if all work was completed within workLimit.
507 */
508 @Inline
509 public boolean incrementalTrace(int workLimit) {
510 logMessage(4, "Continuing GC in parallel (incremental)");
511 logMessage(5, "processing gray objects");
512 int units = 0;
513 do {
514 while (!values.isEmpty() && units < workLimit) {
515 ObjectReference v = values.pop();
516 scanObject(v);
517 units++;
518 }
519 } while (!values.isEmpty() && units < workLimit);
520 return values.isEmpty();
521 }
522
523 /**
524 * Flush any remembered sets pertaining to the current collection.
525 * Non-generational collectors do nothing.
526 */
527 protected void processRememberedSets() {}
528
529 /**
530 * Assert that the remsets have been flushed. This is critical to
531 * correctness. We need to maintain the invariant that remset entries
532 * do not accrue during GC. If the host JVM generates barrier entries
533 * it is its own responsibility to ensure that they are flushed before
534 * returning to MMTk.
535 */
536 private void assertMutatorRemsetsFlushed() {
537 /* FIXME: PNT
538 if (VM.VERIFY_ASSERTIONS) {
539 for (int m = 0; m < VM.activePlan.mutatorCount(); m++) {
540 VM.activePlan.mutator(m).assertRemsetsFlushed();
541 }
542 }
543 */
544 }
545
546 /**
547 * This method logs a message with prepended thread id, if the
548 * verbosity level is greater or equal to the passed level.
549 *
550 * @param minVerbose The required verbosity level
551 * @param message The message to display
552 */
553 @Inline
554 protected final void logMessage(int minVerbose, String message) {
555 if (Options.verbose.getValue() >= minVerbose) {
556 Log.prependThreadId();
557 Log.write(" ");
558 Log.writeln(message);
559 }
560 }
561 }