| /* |
| * This file is part of the Jikes RVM project (http://jikesrvm.org). |
| * |
| * This file is licensed to You under the Eclipse Public License (EPL); |
| * You may not use this file except in compliance with the License. You |
| * may obtain a copy of the License at |
| * |
| * http://www.opensource.org/licenses/eclipse-1.0.php |
| * |
| * See the COPYRIGHT.txt file distributed with this work for information |
| * regarding copyright ownership. |
| */ |
| package org.mmtk.utility; |
| |
| import org.mmtk.plan.Plan; |
| import org.mmtk.plan.semispace.gctrace.GCTrace; |
| import org.mmtk.plan.TraceLocal; |
| import org.mmtk.policy.Space; |
| import org.mmtk.utility.deque.*; |
| import org.mmtk.utility.options.Options; |
| import org.mmtk.utility.options.TraceRate; |
| |
| import org.mmtk.vm.VM; |
| import org.mmtk.vm.Collection; |
| |
| import org.vmmagic.pragma.*; |
| import org.vmmagic.unboxed.*; |
| |
| /** |
| * Class that supports scanning Objects and Arrays for references |
| * during tracing, handling those references, and computing death times |
| */ |
| @Uninterruptible public final class TraceGenerator |
| implements Constants, TracingConstants { |
| |
| |
| /*********************************************************************** |
| * |
| * Class variables |
| */ |
| |
| /* Type of lifetime analysis to be used */ |
| public static final boolean MERLIN_ANALYSIS = true; |
| |
| /* include the notion of build-time allocation to our list of allocators */ |
| private static final int ALLOC_BOOT = GCTrace.ALLOCATORS; |
| private static final int ALLOCATORS = ALLOC_BOOT + 1; |
| |
| /* Fields for tracing */ |
| private static SortTODSharedDeque tracePool; // Buffers to hold raw trace |
| private static TraceBuffer trace; |
| private static boolean traceBusy; // If we are building the trace |
| private static Word lastGC; // Last time GC was performed |
| private static ObjectReferenceArray objectLinks; // Lists of active objs |
| |
| /* Fields needed for Merlin lifetime analysis */ |
| private static SortTODSharedDeque workListPool; // Holds objs to process |
| private static SortTODObjectReferenceStack worklist; // Objs to process |
| private static Word agePropagate; // Death time propagating |
| |
| static { |
| traceBusy = false; |
| lastGC = Word.fromIntZeroExtend(4); |
| Options.traceRate = new TraceRate(); |
| } |
| |
| |
| /*********************************************************************** |
| * |
| * Public analysis methods |
| */ |
| |
| /** |
| * This is called at "build-time" and passes the necessary build image |
| * objects to the trace processor. |
| * |
| * @param worklist_ The dequeue that serves as the worklist for |
| * death time propagation |
| * @param trace_ The dequeue used to store and then output the trace |
| */ |
| @Interruptible |
| public static void init(SortTODSharedDeque worklist_, |
| SortTODSharedDeque trace_) { |
| /* Objects are only needed for merlin tracing */ |
| if (MERLIN_ANALYSIS) { |
| workListPool = worklist_; |
| worklist = new SortTODObjectReferenceStack(workListPool); |
| } |
| |
| /* Trace objects */ |
| tracePool = trace_; |
| trace = new TraceBuffer(tracePool); |
| objectLinks = ObjectReferenceArray.create(Space.MAX_SPACES); |
| } |
| |
| /** |
| * This is called immediately before Jikes terminates. It will perform |
| * any death time processing that the analysis requires and then output |
| * any remaining information in the trace buffer. |
| * |
| * @param value The integer value for the reason Jikes is terminating |
| */ |
| public static void notifyExit(int value) { |
| if (MERLIN_ANALYSIS) |
| findDeaths(); |
| trace.process(); |
| } |
| |
| /** |
| * Add a newly allocated object into the linked list of objects in a region. |
| * This is typically called after each object allocation. |
| * |
| * @param ref The address of the object to be added to the linked list |
| * @param linkSpace The region to which the object should be added |
| */ |
| public static void addTraceObject(ObjectReference ref, int linkSpace) { |
| VM.traceInterface.setLink(ref, objectLinks.get(linkSpace)); |
| objectLinks.set(linkSpace, ref); |
| } |
| |
| /** |
| * Do the work necessary following each garbage collection. This HAS to be |
| * called after EACH collection. |
| */ |
| public static void postCollection() { |
| /* Find and output the object deaths */ |
| traceBusy = true; |
| findDeaths(); |
| traceBusy = false; |
| trace.process(); |
| } |
| |
| |
| /*********************************************************************** |
| * |
| * Trace generation code |
| */ |
| |
| /** |
| * Add the information in the bootImage to the trace. This should be |
| * called before any allocations and pointer updates have occured. |
| * |
| * @param bootStart The address at which the bootimage starts |
| */ |
| public static void boot(Address bootStart) { |
| Word nextOID = VM.traceInterface.getOID(); |
| ObjectReference trav = VM.traceInterface.getBootImageLink().plus(bootStart.toWord().toOffset()).toObjectReference(); |
| objectLinks.set(ALLOC_BOOT, trav); |
| /* Loop through all the objects within boot image */ |
| while (!trav.isNull()) { |
| ObjectReference next = VM.traceInterface.getLink(trav); |
| Word thisOID = VM.traceInterface.getOID(trav); |
| /* Add the boot image object to the trace. */ |
| trace.push(TRACE_BOOT_ALLOC); |
| trace.push(thisOID); |
| trace.push(nextOID.minus(thisOID).lsh(LOG_BYTES_IN_ADDRESS)); |
| nextOID = thisOID; |
| /* Move to the next object & adjust for starting address of |
| the bootImage */ |
| if (!next.isNull()) { |
| next = next.toAddress().plus(bootStart.toWord().toOffset()).toObjectReference(); |
| VM.traceInterface.setLink(trav, next); |
| } |
| trav = next; |
| } |
| } |
| |
| /** |
| * Do any tracing work required at each a pointer store operation. This |
| * will add the pointer store to the trace buffer and, when Merlin lifetime |
| * analysis is being used, performs the necessary timestamping. |
| * |
| * @param isScalar If this is a pointer store to a scalar object |
| * @param src The address of the source object |
| * @param slot The address within <code>src</code> into which |
| * <code>tgt</code> will be stored |
| * @param tgt The target of the pointer store |
| */ |
| @NoInline |
| public static void processPointerUpdate(boolean isScalar, |
| ObjectReference src, |
| Address slot, ObjectReference tgt) { |
| // The trace can be busy only if this is a pointer update as a result of |
| // the garbage collection needed by tracing. For the moment, we will |
| // not report these updates. |
| if (!traceBusy) { |
| /* Process the old target potentially becoming unreachable when needed. */ |
| if (MERLIN_ANALYSIS) { |
| ObjectReference oldTgt = slot.loadObjectReference(); |
| if (!oldTgt.isNull()) |
| VM.traceInterface.updateDeathTime(oldTgt); |
| } |
| |
| traceBusy = true; |
| /* Add the pointer store to the trace */ |
| Offset traceOffset = VM.traceInterface.adjustSlotOffset(isScalar, src, slot); |
| if (isScalar) |
| trace.push(TRACE_FIELD_SET); |
| else |
| trace.push(TRACE_ARRAY_SET); |
| trace.push(VM.traceInterface.getOID(src)); |
| trace.push(traceOffset.toWord()); |
| if (tgt.isNull()) |
| trace.push(Word.zero()); |
| else |
| trace.push(VM.traceInterface.getOID(tgt)); |
| traceBusy = false; |
| } |
| } |
| |
| /** |
| * Do any tracing work required at each object allocation. This will add the |
| * object allocation to the trace buffer, triggers the necessary collection |
| * work at exact allocations, and output the data in the trace buffer. |
| * |
| * @param ref The address of the object just allocated. |
| * @param typeRef the type reference for the instance being created |
| * @param bytes The size of the object being allocated |
| */ |
| @LogicallyUninterruptible |
| @NoInline |
| public static void traceAlloc(boolean isImmortal, ObjectReference ref, |
| ObjectReference typeRef, int bytes) { |
| boolean gcAllowed = VM.traceInterface.gcEnabled() && Plan.isInitialized() && !Plan.gcInProgress(); |
| /* Test if it is time/possible for an exact allocation. */ |
| Word oid = VM.traceInterface.getOID(ref); |
| Word allocType; |
| if (gcAllowed && (oid.GE(lastGC.plus(Word.fromIntZeroExtend(Options.traceRate.getValue()))))) |
| allocType = TRACE_EXACT_ALLOC; |
| else { |
| allocType = TRACE_ALLOC; |
| } |
| /* Add the allocation into the trace. */ |
| traceBusy = true; |
| /* When legally permissible, add the record to the trace buffer */ |
| if (MERLIN_ANALYSIS) { |
| Address fp = (TraceBuffer.OMIT_ALLOCS) ? Address.zero() : VM.traceInterface.skipOwnFramesAndDump(typeRef); |
| |
| if (isImmortal && allocType.EQ(TRACE_EXACT_ALLOC)) |
| trace.push(TRACE_EXACT_IMMORTAL_ALLOC); |
| else if (isImmortal) |
| trace.push(TRACE_IMMORTAL_ALLOC); |
| else |
| trace.push(allocType); |
| trace.push(VM.traceInterface.getOID(ref)); |
| trace.push(Word.fromIntZeroExtend(bytes - VM.traceInterface.getHeaderSize())); |
| trace.push(fp.toWord()); |
| trace.push(Word.zero()); /* Magic.getThreadId() */ |
| trace.push(TRACE_TIB_SET); |
| trace.push(VM.traceInterface.getOID(ref)); |
| trace.push(VM.traceInterface.getOID(typeRef)); |
| } |
| /* Perform the necessary work for death times. */ |
| if (allocType.EQ(TRACE_EXACT_ALLOC)) { |
| if (MERLIN_ANALYSIS) { |
| lastGC = VM.traceInterface.getOID(ref); |
| VM.traceInterface.updateTime(lastGC); |
| VM.collection.triggerCollection(Collection.INTERNAL_GC_TRIGGER); |
| } else { |
| VM.collection.triggerCollection(Collection.RESOURCE_GC_TRIGGER); |
| lastGC = VM.traceInterface.getOID(ref); |
| } |
| } |
| /* Add the allocation record to the buffer if we have not yet done so. */ |
| if (!MERLIN_ANALYSIS) { |
| Address fp = (TraceBuffer.OMIT_ALLOCS) ? Address.zero() : VM.traceInterface.skipOwnFramesAndDump(typeRef); |
| if (isImmortal && allocType.EQ(TRACE_EXACT_ALLOC)) |
| trace.push(TRACE_EXACT_IMMORTAL_ALLOC); |
| else if (isImmortal) |
| trace.push(TRACE_IMMORTAL_ALLOC); |
| else |
| trace.push(allocType); |
| trace.push(VM.traceInterface.getOID(ref)); |
| trace.push(Word.fromIntZeroExtend(bytes - VM.traceInterface.getHeaderSize())); |
| trace.push(fp.toWord()); |
| trace.push(Word.zero()); /* Magic.getThreadId() */ |
| trace.push(TRACE_TIB_SET); |
| trace.push(VM.traceInterface.getOID(ref)); |
| trace.push(VM.traceInterface.getOID(typeRef)); |
| } |
| trace.process(); |
| traceBusy = false; |
| } |
| |
| /*********************************************************************** |
| * |
| * Merlin lifetime analysis methods |
| */ |
| |
| /** |
| * This computes and adds to the trace buffer the unreachable time for |
| * all of the objects that are _provably_ unreachable. This method |
| * should be called after garbage collection (but before the space has |
| * been reclaimed) and at program termination. |
| */ |
| private static void findDeaths() { |
| /* Only the merlin analysis needs to compute death times */ |
| if (MERLIN_ANALYSIS) { |
| /* Start with an empty stack. */ |
| if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(worklist.isEmpty()); |
| /* Scan the linked list of objects within each region */ |
| for (int allocator = 0; allocator < ALLOCATORS; allocator++) { |
| ObjectReference thisRef = objectLinks.get(allocator); |
| /* Start at the top of each linked list */ |
| while (!thisRef.isNull()) { |
| /* Add the unreachable objects onto the worklist. */ |
| if (!getTraceLocal().isReachable(thisRef)) |
| worklist.push(thisRef); |
| thisRef = VM.traceInterface.getLink(thisRef); |
| } |
| } |
| /* Sort the objects on the worklist by their timestamp */ |
| if (!worklist.isEmpty()) |
| worklist.sort(); |
| /* Now compute the death times. */ |
| computeTransitiveClosure(); |
| } |
| /* Output the death times for each object */ |
| for (int allocator = 0; allocator < ALLOCATORS; allocator++) { |
| ObjectReference thisRef = objectLinks.get(allocator); |
| ObjectReference prevRef = ObjectReference.nullReference(); // the last live object seen |
| while (!thisRef.isNull()) { |
| ObjectReference nextRef = VM.traceInterface.getLink(thisRef); |
| /* Maintain reachable objects on the linked list of allocated objects */ |
| if (getTraceLocal().isReachable(thisRef)) { |
| thisRef = getTraceLocal().getForwardedReference(thisRef); |
| VM.traceInterface.setLink(thisRef, prevRef); |
| prevRef = thisRef; |
| } else { |
| /* For brute force lifetime analysis, objects become |
| unreachable "now" */ |
| Word deadTime; |
| if (MERLIN_ANALYSIS) |
| deadTime = VM.traceInterface.getDeathTime(thisRef); |
| else |
| deadTime = lastGC; |
| /* Add the death record to the trace for unreachable objects. */ |
| trace.push(TRACE_DEATH); |
| trace.push(VM.traceInterface.getOID(thisRef)); |
| trace.push(deadTime); |
| } |
| thisRef = nextRef; |
| } |
| /* Purge the list of unreachable objects... */ |
| objectLinks.set(allocator, prevRef); |
| } |
| } |
| |
| /** |
| * This method is called for each root-referenced object at every Merlin |
| * root enumeration. The method will update the death time of the parameter |
| * to the current trace time. |
| * |
| * @param obj The root-referenced object |
| */ |
| public static void rootEnumerate(ObjectReference obj) { |
| VM.traceInterface.updateDeathTime(obj); |
| } |
| |
| /** |
| * This propagates the death time being computed to the object passed as an |
| * address. If we find the unreachable time for the parameter, it will be |
| * pushed on to the processing stack. |
| * |
| * @param ref The address of the object to examine |
| */ |
| public static void propagateDeathTime(ObjectReference ref) { |
| /* If this death time is more accurate, set it. */ |
| if (VM.traceInterface.getDeathTime(ref).LT(agePropagate)) { |
| /* If we should add the object for further processing. */ |
| if (!getTraceLocal().isReachable(ref)) { |
| VM.traceInterface.setDeathTime(ref, agePropagate); |
| worklist.push(ref); |
| } else { |
| VM.traceInterface.setDeathTime(getTraceLocal().getForwardedReference(ref), agePropagate); |
| } |
| } |
| } |
| |
| /** |
| * This finds all object death times by computing the (limited) |
| * transitive closure of the dead objects. Death times are computed |
| * as the latest reaching death time to an object. |
| */ |
| private static void computeTransitiveClosure() { |
| if (!worklist.isEmpty()) { |
| /* The latest time an object can die. */ |
| agePropagate = Word.max(); |
| /* Process through the entire buffer. */ |
| ObjectReference ref = worklist.pop(); |
| while (!ref.isNull()) { |
| Word currentAge = VM.traceInterface.getDeathTime(ref); |
| /* This is a cheap and simple test to process objects only once. */ |
| if (currentAge.LE(agePropagate)) { |
| /* Set the "new" dead age. */ |
| agePropagate = currentAge; |
| /* Scan the object, pushing the survivors */ |
| VM.scanning.scanObject(getTraceLocal(), ref); |
| } |
| /* Get the next object to process */ |
| ref = worklist.pop(); |
| } |
| } |
| } |
| |
| private static TraceLocal getTraceLocal() { |
| return VM.activePlan.collector().getCurrentTrace(); |
| } |
| |
| } |