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