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.jikesrvm.mm.mmtk;
014
015 import org.mmtk.plan.Plan;
016 import org.mmtk.plan.TraceLocal;
017 import org.mmtk.utility.options.Options;
018
019 import org.vmmagic.pragma.*;
020 import org.vmmagic.unboxed.*;
021
022 import org.jikesrvm.VM;
023 import org.jikesrvm.mm.mminterface.DebugUtil;
024 import org.jikesrvm.mm.mminterface.Selected;
025 import org.jikesrvm.runtime.Entrypoints;
026 import org.jikesrvm.runtime.Magic;
027 import org.jikesrvm.scheduler.RVMThread;
028
029 import java.lang.ref.Reference;
030 import java.lang.ref.SoftReference;
031 import java.lang.ref.WeakReference;
032 import java.lang.ref.PhantomReference;
033
034
035 /**
036 * This class manages SoftReferences, WeakReferences, and
037 * PhantomReferences. When a java/lang/ref/Reference object is created,
038 * its address is added to a table of pending reference objects of the
039 * appropriate type. An address is used so the reference will not stay
040 * alive during GC if it isn't in use elsewhere the mutator. During
041 * GC, the various lists are processed in the proper order to
042 * determine if any Reference objects are ready to be enqueued or
043 * whether referents that have died should be kept alive until the
044 * Reference is explicitly cleared. MMTk drives this processing and
045 * uses this class, via the VM interface, to scan the lists of pending
046 * reference objects.
047 * <p>
048 * As an optimization for generational collectors, each reference type
049 * maintains two queues: a nursery queue and the main queue.
050 */
051 @Uninterruptible
052 public final class ReferenceProcessor extends org.mmtk.vm.ReferenceProcessor {
053
054 /********************************************************************
055 * Class fields
056 */
057
058 private static final Lock lock = new Lock("ReferenceProcessor");
059
060 private static final ReferenceProcessor softReferenceProcessor =
061 new ReferenceProcessor(Semantics.SOFT);
062 private static final ReferenceProcessor weakReferenceProcessor =
063 new ReferenceProcessor(Semantics.WEAK);
064 private static final ReferenceProcessor phantomReferenceProcessor =
065 new ReferenceProcessor(Semantics.PHANTOM);
066
067 // Debug flags
068 private static final boolean TRACE = false;
069 private static final boolean TRACE_UNREACHABLE = false;
070 private static final boolean TRACE_DETAIL = false;
071 private static final boolean STRESS = false || VM.ForceFrequentGC;
072
073 /** Initial size of the reference object table */
074 private static final int INITIAL_SIZE = STRESS ? 1 : 256;
075
076 /**
077 * Grow the reference object table by this multiplier
078 * on overflow
079 */
080 private static final double GROWTH_FACTOR = 2.0;
081
082
083 /*************************************************************************
084 * Instance fields
085 */
086
087 /**
088 * The table of reference objects for the current semantics
089 */
090 private volatile AddressArray references = AddressArray.create(INITIAL_SIZE);
091
092 /**
093 * In a MarkCompact (or similar) collector, we need to update the {@code references}
094 * field, and then update its contents. We implement this by saving the pointer in
095 * this untraced field for use during the {@code forward} pass.
096 */
097 @Untraced
098 private volatile AddressArray unforwardedReferences = null;
099
100 /**
101 * Index into the <code>references</code> table for the start of
102 * the reference nursery.
103 */
104 private int nurseryIndex = 0;
105
106 /**
107 * Index of the first free slot in the reference table.
108 */
109 private volatile int maxIndex = 0;
110
111 /**
112 * Flag to prevent a race between threads growing the reference object
113 * table.
114 */
115 private volatile boolean growingTable = false;
116
117 /**
118 * Semantics
119 */
120 private final Semantics semantics;
121
122 /** Copy of semantics.toString() for use in uninterruptible code */
123 private final String semanticsStr;
124
125
126 /**
127 * Create a reference processor for a given semantics
128 *
129 * @param semantics
130 */
131 private ReferenceProcessor(Semantics semantics) {
132 this.semantics = semantics;
133 this.semanticsStr = semantics.toString();
134 }
135
136 /**
137 * Factory method.
138 * Creates an instance of the appropriate reference type processor.
139 * @return the reference processor
140 */
141 @Interruptible
142 public static ReferenceProcessor get(Semantics semantics) {
143 switch(semantics) {
144 case WEAK: return weakReferenceProcessor;
145 case SOFT: return softReferenceProcessor;
146 case PHANTOM: return phantomReferenceProcessor;
147 default:
148 if (VM.VerifyAssertions) VM._assert(VM.NOT_REACHED,"Unrecognized semantics");
149 return null;
150 }
151 }
152
153 /**
154 * Add a reference at the end of the table
155 * @param ref The reference to add
156 */
157 private void addReference(Reference<?> ref, ObjectReference referent) {
158 ObjectReference reference = ObjectReference.fromObject(ref);
159 setReferent(reference, referent);
160 setReference(maxIndex++,reference);
161 }
162
163 /**
164 * Update the reference table
165 *
166 * @param i The table index
167 * @param ref The reference to insert
168 */
169 private void setReference(int i, ObjectReference ref) {
170 if (TRACE_DETAIL) {
171 VM.sysWrite("slot ",i);
172 VM.sysWriteln(" => ",ref);
173 }
174 references.set(i,ref.toAddress());
175 }
176
177 /**
178 * Retrieve from the reference table
179 *
180 * @param i Table index
181 * @return The reference object at index i
182 */
183 private ObjectReference getReference(int i) {
184 return references.get(i).toObjectReference();
185 }
186
187 /**
188 * Grow the reference table by GROWTH_FACTOR.
189 *
190 * <p>Logically Uninterruptible because it can GC when it allocates, but
191 * the rest of the code can't tolerate GC.
192 *
193 * <p>This method is called without the reference processor lock held,
194 * but with the flag <code>growingTable</code> set.
195 */
196 @UninterruptibleNoWarn
197 private AddressArray growReferenceTable() {
198 int newLength = STRESS ? references.length() + 1 : (int)(references.length() * GROWTH_FACTOR);
199 if (TRACE) VM.sysWriteln("Expanding reference type table ",semanticsStr," to ",newLength);
200 AddressArray newReferences = AddressArray.create(newLength);
201 for (int i=0; i < references.length(); i++)
202 newReferences.set(i,references.get(i));
203 return newReferences;
204 }
205
206 /**
207 * Add a reference to the list of references. This method is responsible
208 * for installing the address of the referent into the Reference object
209 * so that the referent is traced at all yield points before the Reference
210 * is correctly installed in the reference table.
211 *
212 * (SJF: This method must NOT be inlined into an inlined allocation
213 * sequence, since it contains a lock!)
214 *
215 * @param referent The referent of the reference
216 * @param ref The reference to add
217 */
218 @NoInline
219 @Unpreemptible("Non-preemptible but yield when table needs to be grown")
220 private void addCandidate(Reference<?> ref, ObjectReference referent) {
221 if (TRACE) {
222 ObjectReference referenceAsAddress = ObjectReference.fromObject(ref);
223 VM.sysWrite("Adding Reference: ", referenceAsAddress);
224 VM.sysWriteln(" ~> ", referent);
225 }
226
227 /*
228 * Ensure that only one thread at a time can grow the
229 * table of references. The volatile flag <code>growingTable</code> is
230 * used to allow growing the table to trigger GC, but to prevent
231 * any other thread from accessing the table while it is being grown.
232 *
233 * If the table has space, threads will add the reference, incrementing maxIndex
234 * and exit.
235 *
236 * If the table is full, the first thread to notice will grow the table.
237 * Subsequent threads will release the lock and yield at (1) while the
238 * first thread
239 */
240 lock.acquire();
241 while (growingTable || maxIndex >= references.length()) {
242 if (growingTable) {
243 // FIXME: We should probably speculatively allocate a new table instead.
244 // note, we can copy without the lock after installing the new table (unint during copy).
245 lock.release();
246 RVMThread.yieldWithHandshake(); // (1) Allow another thread to grow the table
247 lock.acquire();
248 } else {
249 growingTable = true; // Prevent other threads from growing table while lock is released
250 lock.release(); // Can't hold the lock while allocating
251 AddressArray newTable = growReferenceTable();
252 lock.acquire();
253 references = newTable;
254 growingTable = false; // Allow other threads to grow the table rather than waiting for us
255 }
256 }
257 addReference(ref,referent);
258 lock.release();
259 }
260
261 /***********************************************************************
262 * GC time processing
263 */
264
265 /**
266 * {@inheritDoc}
267 * <p>
268 * Collectors like MarkCompact determine liveness and move objects
269 * using separate traces.
270 * <p>
271 * Currently ignores the nursery hint.
272 * <p>
273 * TODO parallelise this code
274 *
275 */
276 @Override
277 public void forward(TraceLocal trace, boolean nursery) {
278 if (VM.VerifyAssertions) VM._assert(unforwardedReferences != null);
279 if (TRACE) VM.sysWriteln("Starting ReferenceGlue.forward(",semanticsStr,")");
280 if (TRACE_DETAIL) {
281 VM.sysWrite(semanticsStr," Reference table is ",
282 Magic.objectAsAddress(references));
283 VM.sysWriteln("unforwardedReferences is ",
284 Magic.objectAsAddress(unforwardedReferences));
285 }
286 for (int i=0; i < maxIndex; i++) {
287 if (TRACE_DETAIL) VM.sysWrite("slot ",i,": ");
288 ObjectReference reference = unforwardedReferences.get(i).toObjectReference();
289 if (TRACE_DETAIL) VM.sysWriteln("forwarding ",reference);
290 setReferent(reference, trace.getForwardedReferent(getReferent(reference)));
291 ObjectReference newReference = trace.getForwardedReference(reference);
292 unforwardedReferences.set(i, newReference.toAddress());
293 }
294 if (TRACE) VM.sysWriteln("Ending ReferenceGlue.forward(",semanticsStr,")");
295 unforwardedReferences = null;
296 }
297
298 @Override
299 public void clear() {
300 maxIndex = 0;
301 }
302
303 /**
304 * {@inheritDoc} Calls ReferenceProcessor's
305 * processReference method for each reference and builds a new
306 * list of those references still active.
307 * <p>
308 * Depending on the value of <code>nursery</code>, we will either
309 * scan all references, or just those created since the last scan.
310 * <p>
311 * TODO parallelise this code
312 *
313 * @param nursery Scan only the newly created references
314 */
315 @Override
316 public void scan(TraceLocal trace, boolean nursery) {
317 unforwardedReferences = references;
318
319 if (TRACE) VM.sysWriteln("Starting ReferenceGlue.scan(",semanticsStr,")");
320 int toIndex = nursery ? nurseryIndex : 0;
321
322 if (TRACE_DETAIL) VM.sysWriteln(semanticsStr," Reference table is ",Magic.objectAsAddress(references));
323 for (int fromIndex = toIndex; fromIndex < maxIndex; fromIndex++) {
324 ObjectReference reference = getReference(fromIndex);
325
326 /* Determine liveness (and forward if necessary) the reference */
327 ObjectReference newReference = processReference(trace,reference);
328 if (!newReference.isNull()) {
329 setReference(toIndex++,newReference);
330 if (TRACE_DETAIL) {
331 int index = toIndex-1;
332 VM.sysWrite("SCANNED ",index);
333 VM.sysWrite(" ",references.get(index));
334 VM.sysWrite(" -> ");
335 VM.sysWriteln(getReferent(references.get(index).toObjectReference()));
336 }
337 }
338 }
339 if (Options.verbose.getValue() >= 3) {
340 VM.sysWrite(semanticsStr);
341 VM.sysWriteln(" references: ",maxIndex," -> ",toIndex);
342 }
343 nurseryIndex = maxIndex = toIndex;
344
345 /* flush out any remset entries generated during the above activities */
346 Selected.Mutator.get().flushRememberedSets();
347 if (TRACE) VM.sysWriteln("Ending ReferenceGlue.scan(",semanticsStr,")");
348 }
349
350 /**
351 * Put this Reference object on its ReferenceQueue (if it has one)
352 * when its referent is no longer sufficiently reachable. The
353 * definition of "reachable" is defined by the semantics of the
354 * particular subclass of Reference. The implementation of this
355 * routine is determined by the the implementation of
356 * java.lang.ref.ReferenceQueue in GNU classpath. It is in this
357 * class rather than the public Reference class to ensure that Jikes
358 * has a safe way of enqueueing the object, one that cannot be
359 * overridden by the application program.
360 *
361 * ************************ TODO *********************************
362 * Change this so that we don't call reference.enqueue directly
363 * as this can be overridden by the user.
364 * ***************************************************************
365 *
366 * @see java.lang.ref.ReferenceQueue
367 * @param addr the address of the Reference object
368 * @return <code>true</code> if the reference was enqueued
369 */
370 @Unpreemptible
371 public boolean enqueueReference(ObjectReference addr) {
372 Reference<?> reference = (Reference<?>)addr.toObject();
373 return reference.enqueueInternal();
374 }
375
376 /**
377 * Add a reference to the list of soft references.
378 * @param ref the SoftReference to add
379 */
380 @Interruptible
381 public static void addSoftCandidate(SoftReference<?> ref, ObjectReference referent) {
382 softReferenceProcessor.addCandidate(ref, referent);
383 }
384
385 /**
386 * Add a reference to the list of weak references.
387 * @param ref the WeakReference to add
388 */
389 @Interruptible
390 public static void addWeakCandidate(WeakReference<?> ref, ObjectReference referent) {
391 weakReferenceProcessor.addCandidate(ref, referent);
392 }
393
394 /**
395 * Add a reference to the list of phantom references.
396 * @param ref the PhantomReference to add
397 */
398 @Interruptible
399 public static void addPhantomCandidate(PhantomReference<?> ref, ObjectReference referent) {
400 phantomReferenceProcessor.addCandidate(ref, referent);
401 }
402
403 /****************************************************************************
404 *
405 * Semantics of reference types
406 *
407 */
408
409 /**
410 * Process a reference with the current semantics.
411 * @param reference the address of the reference. This may or may not
412 * be the address of a heap object, depending on the VM.
413 * @param trace the thread local trace element.
414 */
415 @UninterruptibleNoWarn("Call out to ReferenceQueue API")
416 public ObjectReference processReference(TraceLocal trace, ObjectReference reference) {
417 if (VM.VerifyAssertions) VM._assert(!reference.isNull());
418
419 if (TRACE_DETAIL) {
420 VM.sysWrite("Processing reference: ",reference);
421 }
422 /*
423 * If the reference is dead, we're done with it. Let it (and
424 * possibly its referent) be garbage-collected.
425 */
426 if (!trace.isLive(reference)) {
427 clearReferent(reference); // Too much paranoia ...
428 if (TRACE_UNREACHABLE) { VM.sysWriteln(" UNREACHABLE reference: ",reference); }
429 if (TRACE_DETAIL) {
430 VM.sysWriteln(" (unreachable)");
431 }
432 return ObjectReference.nullReference();
433 }
434
435 /* The reference object is live */
436 ObjectReference newReference = trace.getForwardedReference(reference);
437 ObjectReference oldReferent = getReferent(reference);
438
439 if (TRACE_DETAIL) {
440 VM.sysWrite(" ~> ",oldReferent);
441 }
442
443 /*
444 * If the application has cleared the referent the Java spec says
445 * this does not cause the Reference object to be enqueued. We
446 * simply allow the Reference object to fall out of our
447 * waiting list.
448 */
449 if (oldReferent.isNull()) {
450 if (TRACE_DETAIL) VM.sysWriteln(" (null referent)");
451 return ObjectReference.nullReference();
452 }
453
454 if (TRACE_DETAIL) VM.sysWrite(" => ",newReference);
455
456 if (semantics == Semantics.SOFT) {
457 /*
458 * Unless we've completely run out of memory, we keep
459 * softly reachable objects alive.
460 */
461 if (!Plan.isEmergencyCollection()) {
462 if (TRACE_DETAIL) VM.sysWrite(" (soft) ");
463 trace.retainReferent(oldReferent);
464 }
465 } else if (semantics == Semantics.PHANTOM) {
466 /*
467 * The spec says we should forward the reference. Without unsafe uses of
468 * reflection, the application can't tell the difference whether we do or not,
469 * so we don't forward the reference.
470 */
471 // trace.retainReferent(oldReferent);
472 }
473
474 if (trace.isLive(oldReferent)) {
475 if (VM.VerifyAssertions) {
476 if (!DebugUtil.validRef(oldReferent)) {
477 VM.sysWriteln("Error in old referent.");
478 DebugUtil.dumpRef(oldReferent);
479 VM.sysFail("Invalid reference");
480 }
481 }
482 /*
483 * Referent is still reachable in a way that is as strong as
484 * or stronger than the current reference level.
485 */
486 ObjectReference newReferent = trace.getForwardedReferent(oldReferent);
487
488 if (TRACE_DETAIL) VM.sysWriteln(" ~> ",newReferent);
489
490 if (VM.VerifyAssertions) {
491 if (!DebugUtil.validRef(newReferent)) {
492 VM.sysWriteln("Error forwarding reference object.");
493 DebugUtil.dumpRef(oldReferent);
494 VM.sysFail("Invalid reference");
495 }
496 VM._assert(trace.isLive(newReferent));
497 }
498
499 /*
500 * The reference object stays on the waiting list, and the
501 * referent is untouched. The only thing we must do is
502 * ensure that the former addresses are updated with the
503 * new forwarding addresses in case the collector is a
504 * copying collector.
505 */
506
507 /* Update the referent */
508 setReferent(newReference, newReferent);
509 return newReference;
510 } else {
511 /* Referent is unreachable. Clear the referent and enqueue the reference object. */
512
513 if (TRACE_DETAIL) VM.sysWriteln(" UNREACHABLE");
514 else if (TRACE_UNREACHABLE) VM.sysWriteln(" UNREACHABLE referent: ",oldReferent);
515
516 clearReferent(newReference);
517 enqueueReference(newReference);
518 return ObjectReference.nullReference();
519 }
520 }
521
522 /**
523 * Weak and soft references always clear the referent
524 * before enqueueing. We don't actually call
525 * Reference.clear() as the user could have overridden the
526 * implementation and we don't want any side-effects to
527 * occur.
528 */
529 protected void clearReferent(ObjectReference newReference) {
530 setReferent(newReference, ObjectReference.nullReference());
531 }
532
533 /***********************************************************************
534 *
535 * Reference object field accessors
536 */
537
538 /**
539 * Get the referent from a reference. For Java the reference
540 * is a Reference object.
541 * @param object the object reference.
542 * @return the referent object reference.
543 */
544 protected ObjectReference getReferent(ObjectReference object) {
545 if (VM.VerifyAssertions) VM._assert(!object.isNull());
546 return object.toAddress().loadObjectReference(Entrypoints.referenceReferentField.getOffset());
547 }
548
549 /**
550 * Set the referent in a reference. For Java the reference is
551 * a Reference object.
552 * @param ref the ObjectReference for the reference (confusing eh?).
553 * @param referent the referent object reference.
554 */
555 protected void setReferent(ObjectReference ref, ObjectReference referent) {
556 ref.toAddress().store(referent, Entrypoints.referenceReferentField.getOffset());
557 }
558
559 /***********************************************************************
560 *
561 * Statistics and debugging
562 */
563
564 @Override
565 public int countWaitingReferences() {
566 return maxIndex;
567 }
568 }