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 *
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 VM._assert(false,"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.yield(); // (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 * Scan through all references and forward.
267 *
268 * Collectors like MarkCompact determine liveness and move objects
269 * using separate traces.
270 *
271 * Currently ignores the nursery hint.
272 *
273 * TODO parallelise this code
274 *
275 * @param trace The trace
276 * @param nursery Is this a nursery collection ?
277 */
278 @Override
279 public void forward(TraceLocal trace, boolean nursery) {
280 if (VM.VerifyAssertions) VM._assert(unforwardedReferences != null);
281 if (TRACE) VM.sysWriteln("Starting ReferenceGlue.forward(",semanticsStr,")");
282 if (TRACE_DETAIL) {
283 VM.sysWrite(semanticsStr," Reference table is ",
284 Magic.objectAsAddress(references));
285 VM.sysWriteln("unforwardedReferences is ",
286 Magic.objectAsAddress(unforwardedReferences));
287 }
288 for (int i=0; i < maxIndex; i++) {
289 if (TRACE_DETAIL) VM.sysWrite("slot ",i,": ");
290 ObjectReference reference = unforwardedReferences.get(i).toObjectReference();
291 if (TRACE_DETAIL) VM.sysWriteln("forwarding ",reference);
292 setReferent(reference, trace.getForwardedReferent(getReferent(reference)));
293 ObjectReference newReference = trace.getForwardedReference(reference);
294 unforwardedReferences.set(i, newReference.toAddress());
295 }
296 if (TRACE) VM.sysWriteln("Ending ReferenceGlue.forward(",semanticsStr,")");
297 unforwardedReferences = null;
298 }
299
300 /**
301 * Clear the contents of the table. This is called when reference types are
302 * disabled to make it easier for VMs to change this setting at runtime.
303 */
304 @Override
305 public void clear() {
306 maxIndex = 0;
307 }
308
309 /**
310 * Scan through the list of references. Calls ReferenceProcessor's
311 * processReference method for each reference and builds a new
312 * list of those references still active.
313 *
314 * Depending on the value of <code>nursery</code>, we will either
315 * scan all references, or just those created since the last scan.
316 *
317 * TODO parallelise this code
318 *
319 * @param nursery Scan only the newly created references
320 */
321 @Override
322 public void scan(TraceLocal trace, boolean nursery) {
323 unforwardedReferences = references;
324
325 if (TRACE) VM.sysWriteln("Starting ReferenceGlue.scan(",semanticsStr,")");
326 int toIndex = nursery ? nurseryIndex : 0;
327
328 if (TRACE_DETAIL) VM.sysWriteln(semanticsStr," Reference table is ",Magic.objectAsAddress(references));
329 for (int fromIndex = toIndex; fromIndex < maxIndex; fromIndex++) {
330 ObjectReference reference = getReference(fromIndex);
331
332 /* Determine liveness (and forward if necessary) the reference */
333 ObjectReference newReference = processReference(trace,reference);
334 if (!newReference.isNull()) {
335 setReference(toIndex++,newReference);
336 if (TRACE_DETAIL) {
337 int index = toIndex-1;
338 VM.sysWrite("SCANNED ",index);
339 VM.sysWrite(" ",references.get(index));
340 VM.sysWrite(" -> ");
341 VM.sysWriteln(getReferent(references.get(index).toObjectReference()));
342 }
343 }
344 }
345 if (Options.verbose.getValue() >= 3) {
346 VM.sysWrite(semanticsStr);
347 VM.sysWriteln(" references: ",maxIndex," -> ",toIndex);
348 }
349 nurseryIndex = maxIndex = toIndex;
350
351 /* flush out any remset entries generated during the above activities */
352 Selected.Mutator.get().flushRememberedSets();
353 if (TRACE) VM.sysWriteln("Ending ReferenceGlue.scan(",semanticsStr,")");
354 }
355
356 /**
357 * Put this Reference object on its ReferenceQueue (if it has one)
358 * when its referent is no longer sufficiently reachable. The
359 * definition of "reachable" is defined by the semantics of the
360 * particular subclass of Reference. The implementation of this
361 * routine is determined by the the implementation of
362 * java.lang.ref.ReferenceQueue in GNU classpath. It is in this
363 * class rather than the public Reference class to ensure that Jikes
364 * has a safe way of enqueueing the object, one that cannot be
365 * overridden by the application program.
366 *
367 * ************************ TODO *********************************
368 * Change this so that we don't call reference.enqueue directly
369 * as this can be overridden by the user.
370 * ***************************************************************
371 *
372 * @see java.lang.ref.ReferenceQueue
373 * @param addr the address of the Reference object
374 * @return <code>true</code> if the reference was enqueued
375 */
376 @Unpreemptible
377 public boolean enqueueReference(ObjectReference addr) {
378 Reference<?> reference = (Reference<?>)addr.toObject();
379 return reference.enqueueInternal();
380 }
381
382 /**
383 * Add a reference to the list of soft references.
384 * @param ref the SoftReference to add
385 */
386 @Interruptible
387 public static void addSoftCandidate(SoftReference<?> ref, ObjectReference referent) {
388 softReferenceProcessor.addCandidate(ref, referent);
389 }
390
391 /**
392 * Add a reference to the list of weak references.
393 * @param ref the WeakReference to add
394 */
395 @Interruptible
396 public static void addWeakCandidate(WeakReference<?> ref, ObjectReference referent) {
397 weakReferenceProcessor.addCandidate(ref, referent);
398 }
399
400 /**
401 * Add a reference to the list of phantom references.
402 * @param ref the PhantomReference to add
403 */
404 @Interruptible
405 public static void addPhantomCandidate(PhantomReference<?> ref, ObjectReference referent) {
406 phantomReferenceProcessor.addCandidate(ref, referent);
407 }
408
409 /****************************************************************************
410 *
411 * Semantics of reference types
412 *
413 */
414
415 /**
416 * Process a reference with the current semantics.
417 * @param reference the address of the reference. This may or may not
418 * be the address of a heap object, depending on the VM.
419 * @param trace the thread local trace element.
420 */
421 @UninterruptibleNoWarn("Call out to ReferenceQueue API")
422 public ObjectReference processReference(TraceLocal trace, ObjectReference reference) {
423 if (VM.VerifyAssertions) VM._assert(!reference.isNull());
424
425 if (TRACE_DETAIL) {
426 VM.sysWrite("Processing reference: ",reference);
427 }
428 /*
429 * If the reference is dead, we're done with it. Let it (and
430 * possibly its referent) be garbage-collected.
431 */
432 if (!trace.isLive(reference)) {
433 clearReferent(reference); // Too much paranoia ...
434 if (TRACE_UNREACHABLE) { VM.sysWriteln(" UNREACHABLE reference: ",reference); }
435 if (TRACE_DETAIL) {
436 VM.sysWriteln(" (unreachable)");
437 }
438 return ObjectReference.nullReference();
439 }
440
441 /* The reference object is live */
442 ObjectReference newReference = trace.getForwardedReference(reference);
443 ObjectReference oldReferent = getReferent(reference);
444
445 if (TRACE_DETAIL) {
446 VM.sysWrite(" ~> ",oldReferent);
447 }
448
449 /*
450 * If the application has cleared the referent the Java spec says
451 * this does not cause the Reference object to be enqueued. We
452 * simply allow the Reference object to fall out of our
453 * waiting list.
454 */
455 if (oldReferent.isNull()) {
456 if (TRACE_DETAIL) VM.sysWriteln(" (null referent)");
457 return ObjectReference.nullReference();
458 }
459
460 if (TRACE_DETAIL) VM.sysWrite(" => ",newReference);
461
462 if (semantics == Semantics.SOFT) {
463 /*
464 * Unless we've completely run out of memory, we keep
465 * softly reachable objects alive.
466 */
467 if (!Plan.isEmergencyCollection()) {
468 if (TRACE_DETAIL) VM.sysWrite(" (soft) ");
469 trace.retainReferent(oldReferent);
470 }
471 } else if (semantics == Semantics.PHANTOM) {
472 /*
473 * The spec says we should forward the reference. Without unsafe uses of
474 * reflection, the application can't tell the difference whether we do or not,
475 * so we don't forward the reference.
476 */
477 // trace.retainReferent(oldReferent);
478 }
479
480 if (trace.isLive(oldReferent)) {
481 if (VM.VerifyAssertions) {
482 if (!DebugUtil.validRef(oldReferent)) {
483 VM.sysWriteln("Error in old referent.");
484 DebugUtil.dumpRef(oldReferent);
485 VM.sysFail("Invalid reference");
486 }
487 }
488 /*
489 * Referent is still reachable in a way that is as strong as
490 * or stronger than the current reference level.
491 */
492 ObjectReference newReferent = trace.getForwardedReferent(oldReferent);
493
494 if (TRACE_DETAIL) VM.sysWriteln(" ~> ",newReferent);
495
496 if (VM.VerifyAssertions) {
497 if (!DebugUtil.validRef(newReferent)) {
498 VM.sysWriteln("Error forwarding reference object.");
499 DebugUtil.dumpRef(oldReferent);
500 VM.sysFail("Invalid reference");
501 }
502 VM._assert(trace.isLive(newReferent));
503 }
504
505 /*
506 * The reference object stays on the waiting list, and the
507 * referent is untouched. The only thing we must do is
508 * ensure that the former addresses are updated with the
509 * new forwarding addresses in case the collector is a
510 * copying collector.
511 */
512
513 /* Update the referent */
514 setReferent(newReference, newReferent);
515 return newReference;
516 } else {
517 /* Referent is unreachable. Clear the referent and enqueue the reference object. */
518
519 if (TRACE_DETAIL) VM.sysWriteln(" UNREACHABLE");
520 else if (TRACE_UNREACHABLE) VM.sysWriteln(" UNREACHABLE referent: ",oldReferent);
521
522 clearReferent(newReference);
523 enqueueReference(newReference);
524 return ObjectReference.nullReference();
525 }
526 }
527
528 /**
529 * Weak and soft references always clear the referent
530 * before enqueueing. We don't actually call
531 * Reference.clear() as the user could have overridden the
532 * implementation and we don't want any side-effects to
533 * occur.
534 */
535 protected void clearReferent(ObjectReference newReference) {
536 setReferent(newReference, ObjectReference.nullReference());
537 }
538
539 /***********************************************************************
540 *
541 * Reference object field accessors
542 */
543
544 /**
545 * Get the referent from a reference. For Java the reference
546 * is a Reference object.
547 * @param object the object reference.
548 * @return the referent object reference.
549 */
550 protected ObjectReference getReferent(ObjectReference object) {
551 if (VM.VerifyAssertions) VM._assert(!object.isNull());
552 return object.toAddress().loadObjectReference(Entrypoints.referenceReferentField.getOffset());
553 }
554
555 /**
556 * Set the referent in a reference. For Java the reference is
557 * a Reference object.
558 * @param ref the ObjectReference for the reference (confusing eh?).
559 * @param referent the referent object reference.
560 */
561 protected void setReferent(ObjectReference ref, ObjectReference referent) {
562 ref.toAddress().store(referent, Entrypoints.referenceReferentField.getOffset());
563 }
564
565 /***********************************************************************
566 *
567 * Statistics and debugging
568 */
569
570 public int countWaitingReferences() {
571 return maxIndex;
572 }
573 }