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.utility;
014
015 import org.mmtk.plan.ParallelCollector;
016 import org.mmtk.plan.Plan;
017 import org.mmtk.plan.semispace.gctrace.GCTrace;
018 import org.mmtk.plan.TraceLocal;
019 import org.mmtk.policy.Space;
020 import org.mmtk.utility.deque.*;
021 import org.mmtk.utility.options.Options;
022 import org.mmtk.utility.options.TraceRate;
023
024 import org.mmtk.vm.VM;
025
026 import org.vmmagic.pragma.*;
027 import org.vmmagic.unboxed.*;
028
029 /**
030 * Class that supports scanning Objects and Arrays for references
031 * during tracing, handling those references, and computing death times
032 */
033 @Uninterruptible public final class TraceGenerator
034 implements Constants, TracingConstants {
035
036
037 /***********************************************************************
038 *
039 * Class variables
040 */
041
042 /** Type of lifetime analysis to be used */
043 public static final boolean MERLIN_ANALYSIS = true;
044
045 /* include the notion of build-time allocation to our list of allocators */
046 private static final int ALLOC_BOOT = GCTrace.ALLOCATORS;
047 private static final int ALLOCATORS = ALLOC_BOOT + 1;
048
049 /* Fields for tracing */
050 private static SortTODSharedDeque tracePool; // Buffers to hold raw trace
051 private static TraceBuffer trace;
052 private static boolean traceBusy; // If we are building the trace
053 private static Word lastGC; // Last time GC was performed
054 private static ObjectReferenceArray objectLinks; // Lists of active objs
055
056 /* Fields needed for Merlin lifetime analysis */
057 private static SortTODSharedDeque workListPool; // Holds objs to process
058 private static SortTODObjectReferenceStack worklist; // Objs to process
059 private static Word agePropagate; // Death time propagating
060
061 static {
062 traceBusy = false;
063 lastGC = Word.fromIntZeroExtend(4);
064 Options.traceRate = new TraceRate();
065 }
066
067
068 /***********************************************************************
069 *
070 * Public analysis methods
071 */
072
073 /**
074 * This is called at "build-time" and passes the necessary build image
075 * objects to the trace processor.
076 *
077 * @param worklist_ The dequeue that serves as the worklist for
078 * death time propagation
079 * @param trace_ The dequeue used to store and then output the trace
080 */
081 @Interruptible
082 public static void init(SortTODSharedDeque worklist_,
083 SortTODSharedDeque trace_) {
084 /* Objects are only needed for merlin tracing */
085 if (MERLIN_ANALYSIS) {
086 workListPool = worklist_;
087 worklist = new SortTODObjectReferenceStack(workListPool);
088 }
089
090 /* Trace objects */
091 tracePool = trace_;
092 trace = new TraceBuffer(tracePool);
093 objectLinks = ObjectReferenceArray.create(Space.MAX_SPACES);
094 }
095
096 /**
097 * This is called immediately before Jikes terminates. It will perform
098 * any death time processing that the analysis requires and then output
099 * any remaining information in the trace buffer.
100 *
101 * @param value The integer value for the reason Jikes is terminating
102 */
103 public static void notifyExit(int value) {
104 if (MERLIN_ANALYSIS)
105 findDeaths();
106 trace.process();
107 }
108
109 /**
110 * Add a newly allocated object into the linked list of objects in a region.
111 * This is typically called after each object allocation.
112 *
113 * @param ref The address of the object to be added to the linked list
114 * @param linkSpace The region to which the object should be added
115 */
116 public static void addTraceObject(ObjectReference ref, int linkSpace) {
117 VM.traceInterface.setLink(ref, objectLinks.get(linkSpace));
118 objectLinks.set(linkSpace, ref);
119 }
120
121 /**
122 * Do the work necessary following each garbage collection. This HAS to be
123 * called after EACH collection.
124 */
125 public static void postCollection() {
126 /* Find and output the object deaths */
127 traceBusy = true;
128 findDeaths();
129 traceBusy = false;
130 trace.process();
131 }
132
133
134 /***********************************************************************
135 *
136 * Trace generation code
137 */
138
139 /**
140 * Add the information in the bootImage to the trace. This should be
141 * called before any allocations and pointer updates have occurred.
142 *
143 * @param bootStart The address at which the bootimage starts
144 */
145 public static void boot(Address bootStart) {
146 Word nextOID = VM.traceInterface.getOID();
147 ObjectReference trav = VM.traceInterface.getBootImageLink().plus(bootStart.toWord().toOffset()).toObjectReference();
148 objectLinks.set(ALLOC_BOOT, trav);
149 /* Loop through all the objects within boot image */
150 while (!trav.isNull()) {
151 ObjectReference next = VM.traceInterface.getLink(trav);
152 Word thisOID = VM.traceInterface.getOID(trav);
153 /* Add the boot image object to the trace. */
154 trace.push(TRACE_BOOT_ALLOC);
155 trace.push(thisOID);
156 trace.push(nextOID.minus(thisOID).lsh(LOG_BYTES_IN_ADDRESS));
157 nextOID = thisOID;
158 /* Move to the next object & adjust for starting address of
159 the bootImage */
160 if (!next.isNull()) {
161 next = next.toAddress().plus(bootStart.toWord().toOffset()).toObjectReference();
162 VM.traceInterface.setLink(trav, next);
163 }
164 trav = next;
165 }
166 }
167
168 /**
169 * Do any tracing work required at each a pointer store operation. This
170 * will add the pointer store to the trace buffer and, when Merlin lifetime
171 * analysis is being used, performs the necessary timestamping.
172 *
173 * @param isScalar If this is a pointer store to a scalar object
174 * @param src The address of the source object
175 * @param slot The address within <code>src</code> into which
176 * <code>tgt</code> will be stored
177 * @param tgt The target of the pointer store
178 */
179 @NoInline
180 public static void processPointerUpdate(boolean isScalar,
181 ObjectReference src,
182 Address slot, ObjectReference tgt) {
183 // The trace can be busy only if this is a pointer update as a result of
184 // the garbage collection needed by tracing. For the moment, we will
185 // not report these updates.
186 if (!traceBusy) {
187 /* Process the old target potentially becoming unreachable when needed. */
188 if (MERLIN_ANALYSIS) {
189 ObjectReference oldTgt = slot.loadObjectReference();
190 if (!oldTgt.isNull())
191 VM.traceInterface.updateDeathTime(oldTgt);
192 }
193
194 traceBusy = true;
195 /* Add the pointer store to the trace */
196 Offset traceOffset = VM.traceInterface.adjustSlotOffset(isScalar, src, slot);
197 if (isScalar)
198 trace.push(TRACE_FIELD_SET);
199 else
200 trace.push(TRACE_ARRAY_SET);
201 trace.push(VM.traceInterface.getOID(src));
202 trace.push(traceOffset.toWord());
203 if (tgt.isNull())
204 trace.push(Word.zero());
205 else
206 trace.push(VM.traceInterface.getOID(tgt));
207 traceBusy = false;
208 }
209 }
210
211 /**
212 * Do any tracing work required at each object allocation. This will add the
213 * object allocation to the trace buffer, triggers the necessary collection
214 * work at exact allocations, and output the data in the trace buffer.
215 *
216 * @param ref The address of the object just allocated.
217 * @param typeRef the type reference for the instance being created
218 * @param bytes The size of the object being allocated
219 */
220 @LogicallyUninterruptible
221 @NoInline
222 public static void traceAlloc(boolean isImmortal, ObjectReference ref,
223 ObjectReference typeRef, int bytes) {
224 boolean gcAllowed = VM.traceInterface.gcEnabled() && Plan.isInitialized() && VM.activePlan.isMutator();
225 /* Test if it is time/possible for an exact allocation. */
226 Word oid = VM.traceInterface.getOID(ref);
227 Word allocType;
228 if (gcAllowed && (oid.GE(lastGC.plus(Word.fromIntZeroExtend(Options.traceRate.getValue())))))
229 allocType = TRACE_EXACT_ALLOC;
230 else {
231 allocType = TRACE_ALLOC;
232 }
233 /* Add the allocation into the trace. */
234 traceBusy = true;
235 /* When legally permissible, add the record to the trace buffer */
236 if (MERLIN_ANALYSIS) {
237 Address fp = (TraceBuffer.OMIT_ALLOCS) ? Address.zero() : VM.traceInterface.skipOwnFramesAndDump(typeRef);
238
239 if (isImmortal && allocType.EQ(TRACE_EXACT_ALLOC))
240 trace.push(TRACE_EXACT_IMMORTAL_ALLOC);
241 else if (isImmortal)
242 trace.push(TRACE_IMMORTAL_ALLOC);
243 else
244 trace.push(allocType);
245 trace.push(VM.traceInterface.getOID(ref));
246 trace.push(Word.fromIntZeroExtend(bytes - VM.traceInterface.getHeaderSize()));
247 trace.push(fp.toWord());
248 trace.push(Word.zero()); /* Magic.getThreadId() */
249 trace.push(TRACE_TIB_SET);
250 trace.push(VM.traceInterface.getOID(ref));
251 trace.push(VM.traceInterface.getOID(typeRef));
252 }
253 /* Perform the necessary work for death times. */
254 if (allocType.EQ(TRACE_EXACT_ALLOC)) {
255 if (MERLIN_ANALYSIS) {
256 lastGC = VM.traceInterface.getOID(ref);
257 VM.traceInterface.updateTime(lastGC);
258 // FIXME TODO: VM.collection.triggerCollection(Collection.INTERNAL_GC_TRIGGER);
259 } else {
260 // FIXME TODO: VM.collection.triggerCollection(Collection.RESOURCE_GC_TRIGGER);
261 lastGC = VM.traceInterface.getOID(ref);
262 }
263 }
264 /* Add the allocation record to the buffer if we have not yet done so. */
265 if (!MERLIN_ANALYSIS) {
266 Address fp = (TraceBuffer.OMIT_ALLOCS) ? Address.zero() : VM.traceInterface.skipOwnFramesAndDump(typeRef);
267 if (isImmortal && allocType.EQ(TRACE_EXACT_ALLOC))
268 trace.push(TRACE_EXACT_IMMORTAL_ALLOC);
269 else if (isImmortal)
270 trace.push(TRACE_IMMORTAL_ALLOC);
271 else
272 trace.push(allocType);
273 trace.push(VM.traceInterface.getOID(ref));
274 trace.push(Word.fromIntZeroExtend(bytes - VM.traceInterface.getHeaderSize()));
275 trace.push(fp.toWord());
276 trace.push(Word.zero()); /* Magic.getThreadId() */
277 trace.push(TRACE_TIB_SET);
278 trace.push(VM.traceInterface.getOID(ref));
279 trace.push(VM.traceInterface.getOID(typeRef));
280 }
281 trace.process();
282 traceBusy = false;
283 }
284
285 /***********************************************************************
286 *
287 * Merlin lifetime analysis methods
288 */
289
290 /**
291 * This computes and adds to the trace buffer the unreachable time for
292 * all of the objects that are _provably_ unreachable. This method
293 * should be called after garbage collection (but before the space has
294 * been reclaimed) and at program termination.
295 */
296 private static void findDeaths() {
297 /* Only the merlin analysis needs to compute death times */
298 if (MERLIN_ANALYSIS) {
299 /* Start with an empty stack. */
300 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(worklist.isEmpty());
301 /* Scan the linked list of objects within each region */
302 for (int allocator = 0; allocator < ALLOCATORS; allocator++) {
303 ObjectReference thisRef = objectLinks.get(allocator);
304 /* Start at the top of each linked list */
305 while (!thisRef.isNull()) {
306 /* Add the unreachable objects onto the worklist. */
307 if (!getTraceLocal().isReachable(thisRef))
308 worklist.push(thisRef);
309 thisRef = VM.traceInterface.getLink(thisRef);
310 }
311 }
312 /* Sort the objects on the worklist by their timestamp */
313 if (!worklist.isEmpty())
314 worklist.sort();
315 /* Now compute the death times. */
316 computeTransitiveClosure();
317 }
318 /* Output the death times for each object */
319 for (int allocator = 0; allocator < ALLOCATORS; allocator++) {
320 ObjectReference thisRef = objectLinks.get(allocator);
321 ObjectReference prevRef = ObjectReference.nullReference(); // the last live object seen
322 while (!thisRef.isNull()) {
323 ObjectReference nextRef = VM.traceInterface.getLink(thisRef);
324 /* Maintain reachable objects on the linked list of allocated objects */
325 if (getTraceLocal().isReachable(thisRef)) {
326 thisRef = getTraceLocal().getForwardedReference(thisRef);
327 VM.traceInterface.setLink(thisRef, prevRef);
328 prevRef = thisRef;
329 } else {
330 /* For brute force lifetime analysis, objects become
331 unreachable "now" */
332 Word deadTime;
333 if (MERLIN_ANALYSIS)
334 deadTime = VM.traceInterface.getDeathTime(thisRef);
335 else
336 deadTime = lastGC;
337 /* Add the death record to the trace for unreachable objects. */
338 trace.push(TRACE_DEATH);
339 trace.push(VM.traceInterface.getOID(thisRef));
340 trace.push(deadTime);
341 }
342 thisRef = nextRef;
343 }
344 /* Purge the list of unreachable objects... */
345 objectLinks.set(allocator, prevRef);
346 }
347 }
348
349 /**
350 * This method is called for each root-referenced object at every Merlin
351 * root enumeration. The method will update the death time of the parameter
352 * to the current trace time.
353 *
354 * @param obj The root-referenced object
355 */
356 public static void rootEnumerate(ObjectReference obj) {
357 VM.traceInterface.updateDeathTime(obj);
358 }
359
360 /**
361 * This propagates the death time being computed to the object passed as an
362 * address. If we find the unreachable time for the parameter, it will be
363 * pushed on to the processing stack.
364 *
365 * @param ref The address of the object to examine
366 */
367 public static void propagateDeathTime(ObjectReference ref) {
368 /* If this death time is more accurate, set it. */
369 if (VM.traceInterface.getDeathTime(ref).LT(agePropagate)) {
370 /* If we should add the object for further processing. */
371 if (!getTraceLocal().isReachable(ref)) {
372 VM.traceInterface.setDeathTime(ref, agePropagate);
373 worklist.push(ref);
374 } else {
375 VM.traceInterface.setDeathTime(getTraceLocal().getForwardedReference(ref), agePropagate);
376 }
377 }
378 }
379
380 /**
381 * This finds all object death times by computing the (limited)
382 * transitive closure of the dead objects. Death times are computed
383 * as the latest reaching death time to an object.
384 */
385 private static void computeTransitiveClosure() {
386 if (!worklist.isEmpty()) {
387 /* The latest time an object can die. */
388 agePropagate = Word.max();
389 /* Process through the entire buffer. */
390 ObjectReference ref = worklist.pop();
391 while (!ref.isNull()) {
392 Word currentAge = VM.traceInterface.getDeathTime(ref);
393 /* This is a cheap and simple test to process objects only once. */
394 if (currentAge.LE(agePropagate)) {
395 /* Set the "new" dead age. */
396 agePropagate = currentAge;
397 /* Scan the object, pushing the survivors */
398 VM.scanning.scanObject(getTraceLocal(), ref);
399 }
400 /* Get the next object to process */
401 ref = worklist.pop();
402 }
403 }
404 }
405
406 private static TraceLocal getTraceLocal() {
407 return ((ParallelCollector)VM.activePlan.collector()).getCurrentTrace();
408 }
409
410 }