Re: [rvm-research] Sorting Greatest to Least with SortTODObjectReferenceStack

[Eddie A. <ea...@cs...>]

Hi everyone,

I created a JIRA entry and posted a patch for this issue.  You can find 
both here:
http://jira.codehaus.org/browse/RVM-626

My patches are against 2.9.1.  I briefly looked at 3.0.0 today, but I 
could not build it in the GCTrace configuration so I could not test the 
fix against that version.

-Eddie

Eddie Aftandilian wrote:
> No problem. :)  I'll create a JIRA entry and post a patch in the next 
> couple of days.
> 
> -Eddie
> 
> Steve Blackburn wrote:
>> On 07/08/2008, at 10:03 AM, Eddie Aftandilian wrote:
>>>  I submitted a patch to Steve for this a while back, 
>>> but I don't think it ever made it into the codebase. 
>> Ugh.  Sorry Eddie.  I'm not sure what you're referring to :-/   I did a 
>> deep look through my email, and the only thing I can find is something 
>> from October 2006, where it seems you and I were catching up while in 
>> Portland for OOPSLA (below).  
>>
>> I'm sorry if I let it slip.  The best thing to do is to put it in the 
>> JIRA.  That way there's a paper trail, so its more likely (and easier to 
>> pin blame on slack core team members).  Apols again.
>>
>> --Steve
>>
>>
>>
>> On 24/10/2006, at 3:43 PM, Eddie Aftandilian wrote:
>>
>> Hi Steve,
>>
>> I've attached two patches for the Merlin problems in JikesRVM.  These 
>> patches are against version 2.4.5.
>>
>> They need to be applied in this order:
>> 1) apply-tracing-patch
>> 2) test-scanobject
>>
>> apply-tracing-patch is a contribution by Matthew Hertz that is already 
>> in the patch tracker but hasn't made it into JikesRVM for some reason. 
>> Here is the link for 
>> that: http://sourceforge.net/tracker/index.php?func=detail&aid=1514837&group_id=128805&atid=712770 
>> <http://sourceforge.net/tracker/index.php?func=detail&aid=1514837&group_id=128805&atid=712770>
>>
>> test-scanobject is the fix for the issue with the Merlin code popping 
>> from the wrong end of the deque.  It's not totally clean since I wasn't 
>> expecting to submit it so soon.  There is a bit of debugging code left 
>> in there (but commented out), and my editor's tab/spacing convention is 
>> different from JikesRVM's.  But those problems are easily fixed.
>>
>> We can go through this tomorrow, just grab me after one of the sessions.
>>
>> Note that even after these two patches, Merlin will still fail about 1/2 
>> of the time with the threading error we were talking about today.
>>
>> -Eddie
>> Index: rvmRoot/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTrace.java
>> ===================================================================
>> --- rvmRoot.orig/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTrace.java
>> +++ rvmRoot/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTrace.java
>> @@ -91,11 +91,12 @@ public class GCTrace extends SS implemen
>>    */
>>
>>   /* Spaces */
>> -  public static final RawPageSpace traceSpace = new 
>> RawPageSpace("trace", DEFAULT_POLL_FREQUENCY, META_DATA_MB);
>> +  public static final RawPageSpace traceSpace = new 
>> RawPageSpace("trace", DEFAULT_POLL_FREQUENCY, META_DATA_MB<<2);
>>
>>   public static final int TRACE = traceSpace.getDescriptor();
>>
>>   /* GC state */
>> +  public static boolean lastGCWasTracing = false; // True when previous 
>> GC was for tracing
>>   public static boolean traceInducedGC = false; // True if trace 
>> triggered GC
>>   public static boolean deathScan = false;
>>   public static boolean finalDead = false;
>> @@ -185,6 +186,9 @@ public class GCTrace extends SS implemen
>>    */
>>
>>   public void collectionPhase(int phaseId) {
>> + if (phaseId == PREPARE) {
>> +   lastGCWasTracing = traceInducedGC;
>> + }
>>     if (phaseId == RELEASE) {
>>       if (traceInducedGC) {
>>         /* Clean up following a trace-induced scan */
>> @@ -218,7 +222,7 @@ public class GCTrace extends SS implemen
>>    *         their failure to return memory isn't cause for concern.
>>    */
>>   public boolean isLastGCFull() {
>> -    return !traceInducedGC;
>> +    return !lastGCWasTracing;
>>   }
>>
>>   /**
>> Index: 
>> rvmRoot/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTraceCollector.java
>> ===================================================================
>> --- 
>> rvmRoot.orig/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTraceCollector.java
>> +++ rvmRoot/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTraceCollector.java
>> @@ -73,11 +73,6 @@ public class GCTraceCollector extends SS
>>    * @param primary perform any single-threaded local activities.
>>    */
>>   public void collectionPhase(int phaseId, boolean primary) {
>> -    if (phaseId == SS.PREPARE) {
>> -      super.collectionPhase(phaseId, primary);
>> -      return;
>> -    }
>> -
>>     if (phaseId == GCTrace.START_CLOSURE) {
>>       inducedTrace.startTrace();
>>       return;
>> @@ -101,12 +96,10 @@ public class GCTraceCollector extends SS
>>         ((phaseId != StopTheWorld.SOFT_REFS) &&
>>          (phaseId != StopTheWorld.WEAK_REFS) &&
>>          (phaseId != StopTheWorld.PHANTOM_REFS) &&
>> -         (phaseId != StopTheWorld.FORWARD_REFS) &&
>> -         (phaseId != StopTheWorld.FORWARD_FINALIZABLE) &&
>> -         (phaseId != StopTheWorld.FINALIZABLE))) {
>> +         (phaseId != StopTheWorld.FINALIZABLE) &&
>> +  (phaseId != SS.PREPARE))) {
>>       // Delegate up.
>>       super.collectionPhase(phaseId, primary);
>> -      return;
>>     }
>>   }
>>
>> Index: rvmRoot/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTraceMutator.java
>> ===================================================================
>> --- 
>> rvmRoot.orig/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTraceMutator.java
>> +++ rvmRoot/MMTk/src/org/mmtk/plan/semispace/gctrace/GCTraceMutator.java
>> @@ -9,6 +9,7 @@ package org.mmtk.plan.semispace.gctrace;
>>
>> import org.mmtk.plan.semispace.SSMutator;
>> import org.mmtk.plan.semispace.*;
>> +import org.mmtk.plan.*;
>> import org.mmtk.utility.TraceGenerator;
>> import org.mmtk.vm.Barriers;
>>
>> @@ -148,15 +149,11 @@ public class GCTraceMutator extends SSMu
>>    * @param primary perform any single-threaded local activities.
>>    */
>>   public void collectionPhase(int phaseId, boolean primary) {
>> -    if (phaseId == SS.PREPARE_MUTATOR) {
>> -      if (!GCTrace.traceInducedGC) {
>> -        // rebind the semispace bump pointer to the appropriate semispace.
>> -        ss.rebind(SS.toSpace());
>> -      }
>> +    if (!GCTrace.traceInducedGC ||
>> +     (phaseId != StopTheWorld.PREPARE_MUTATOR) &&
>> +     (phaseId != StopTheWorld.RELEASE_MUTATOR)) {
>> +      // Delegate up
>>       super.collectionPhase(phaseId, primary);
>> -      return;
>>     }
>> -
>> -    super.collectionPhase(phaseId, primary);
>>   }
>> }
>> Index: rvmRoot/MMTk/src/org/mmtk/utility/TraceGenerator.java
>> ===================================================================
>> --- rvmRoot.orig/MMTk/src/org/mmtk/utility/TraceGenerator.java
>> +++ rvmRoot/MMTk/src/org/mmtk/utility/TraceGenerator.java
>> @@ -223,9 +223,6 @@ public final class TraceGenerator 
>>   public static final void traceAlloc(boolean isImmortal, 
>> ObjectReference ref,
>>       ObjectReference typeRef, int bytes)
>>       throws LogicallyUninterruptiblePragma, NoInlinePragma {
>> -    /* Assert that this isn't the result of tracing */
>> -    if (Assert.VERIFY_ASSERTIONS) Assert._assert(!traceBusy);
>> -
>>     boolean gcAllowed = TraceInterface.gcEnabled() && Plan.isInitialized()
>>         && !Plan.gcInProgress();
>>     /* Test if it is time/possible for an exact allocation. */
>> @@ -239,6 +236,24 @@ public final class TraceGenerator 
>>     }
>>     /* 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() : 
>> 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(TraceInterface.getOID(ref));
>> +   trace.push(Word.fromInt(bytes - TraceInterface.getHeaderSize()));
>> +   trace.push(fp.toWord());
>> +   trace.push(Word.fromInt(0 /* VM_Magic.getThreadId() */));
>> +   trace.push(TRACE_TIB_SET);
>> +   trace.push(TraceInterface.getOID(ref));
>> +   trace.push(TraceInterface.getOID(typeRef));
>> + }
>>     /* Perform the necessary work for death times. */
>>     if (allocType.EQ(TRACE_EXACT_ALLOC)) {
>>       if (MERLIN_ANALYSIS) {
>> @@ -250,20 +265,23 @@ public final class TraceGenerator 
>>         lastGC = TraceInterface.getOID(ref);
>>       }
>>     }
>> -    Address fp = 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(TraceInterface.getOID(ref));
>> -    trace.push(Word.fromInt(bytes - TraceInterface.getHeaderSize()));
>> -    trace.push(fp.toWord());
>> -    trace.push(Word.fromInt(0 /* VM_Magic.getThreadId() */));
>> -    trace.push(TRACE_TIB_SET);
>> -    trace.push(TraceInterface.getOID(ref));
>> -    trace.push(TraceInterface.getOID(typeRef));
>> + /* Add the allocation record to the buffer if we have not yet done so. */
>> + if (!MERLIN_ANALYSIS) {
>> +   Address fp = (TraceBuffer.OMIT_ALLOCS) ? Address.zero() : 
>> 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(TraceInterface.getOID(ref));
>> +   trace.push(Word.fromInt(bytes - TraceInterface.getHeaderSize()));
>> +   trace.push(fp.toWord());
>> +   trace.push(Word.fromInt(0 /* VM_Magic.getThreadId() */));
>> +   trace.push(TRACE_TIB_SET);
>> +   trace.push(TraceInterface.getOID(ref));
>> +   trace.push(TraceInterface.getOID(typeRef));
>> + }
>>     trace.process();
>>     traceBusy = false;
>>   }
>> @@ -297,7 +315,8 @@ public final class TraceGenerator 
>>         }
>>       }
>>       /* Sort the objects on the worklist by their timestamp */
>> -      worklist.sort();
>> +   if (!worklist.isEmpty())
>> +     worklist.sort();
>>       /* Now compute the death times. */
>>       computeTransitiveClosure();
>>     }
>> @@ -369,22 +388,23 @@ public final class TraceGenerator 
>>    * as the latest reaching death time to an object.
>>    */
>>   private static final void computeTransitiveClosure() {
>> -    /* The latest time an object can die. */
>> -    agePropagate = Word.max();
>> -    if (Assert.VERIFY_ASSERTIONS) Assert._assert(!worklist.isEmpty());
>> -    /* Process through the entire buffer. */
>> -    ObjectReference ref = worklist.pop();
>> -    while (!ref.isNull()) {
>> -      Word currentAge = 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 */
>> -        Scan.scanObject(getTraceLocal(), ref);
>> -      }
>> -      /* Get the next object to process */
>> -      ref = worklist.pop();
>> + 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 = 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 */
>> +   Scan.scanObject(getTraceLocal(), ref);
>> + }
>> + /* Get the next object to process */
>> + ref = worklist.pop();
>> +   }
>>     }
>>   }
>>
>> Index: rvmRoot/MMTk/src/org/mmtk/utility/deque/TraceBuffer.java
>> ===================================================================
>> --- rvmRoot.orig/MMTk/src/org/mmtk/utility/deque/TraceBuffer.java
>> +++ rvmRoot/MMTk/src/org/mmtk/utility/deque/TraceBuffer.java
>> @@ -42,6 +42,19 @@ public class TraceBuffer extends LocalQu
>>   private static final Word TRACE_STATIC_TARGET = Word.fromInt(17);
>>   private static final Word TRACE_BOOT_ALLOC_SIZE = Word.fromInt(18);
>>
>> +  /*
>> +   * Debugging and trace reducing constants
>> +   */
>> +  public static final boolean OMIT_ALLOCS = false;
>> +  public static final boolean OMIT_UPDATES = false;
>> +  public static final boolean OMIT_BOOTALLOCS = false;
>> +  public static final boolean OMIT_UNREACHABLES = false;
>> +  public static final boolean OMIT_OTHERS = false;
>> +  public static final boolean OMIT_OUTPUT = OMIT_ALLOCS && OMIT_UPDATES &&
>> +                                            OMIT_OTHERS;
>> +
>> +
>> +
>>   /***********************************************************************
>>    * 
>>    * Instance fields
>> @@ -80,8 +93,9 @@ public class TraceBuffer extends LocalQu
>>   public final void process() {
>>     Word traceState = TRACE_NEW_RECORD;
>>     int entriesNotFlushed = 0;
>> + boolean loggedRecord = false;
>>     /* First we must flush any remaining data */
>> -    Log.writeln();
>> + if (!OMIT_OUTPUT) Log.writeln();
>>
>>     /* Process through the entire buffer. */
>>     while (checkDequeue(1)) {
>> @@ -91,92 +105,130 @@ public class TraceBuffer extends LocalQu
>>         head = head.minus(BYTES_IN_ADDRESS);
>>         Word val = head.loadWord();
>>         if (traceState.EQ(TRACE_NEW_RECORD)) {
>> +   loggedRecord = false;
>>           if (val.EQ(TRACE_GCSTART)) {
>> -            Log.write('G');
>> -            Log.write('C');
>> -            Log.writeln('B', true);
>> +     if (!OMIT_OTHERS) {
>> +              Log.write('G');
>> +   Log.write('C');
>> +   Log.writeln('B', true);
>> + }
>>           } else if (val.EQ(TRACE_GCEND)) {
>> -            Log.write('G');
>> -            Log.write('C');
>> -            Log.writeln('E', true);
>> +     if (!OMIT_OTHERS) {
>> +              Log.write('G');
>> +   Log.write('C');
>> +   Log.writeln('E', true);
>> + }
>>           } else {
>>             traceState = val;
>>           }
>>         } else {
>>           if (traceState.EQ(TRACE_EXACT_ALLOC) ||
>>               traceState.EQ(TRACE_ALLOC)) {
>> -            Log.write((traceState.EQ(TRACE_EXACT_ALLOC)) ? 'A' : 'a');
>> -            Log.write(' ');
>> -            Log.write(val);
>> -            traceState = TRACE_ALLOC_SIZE;
>> + if (!OMIT_ALLOCS) {
>> +              Log.write((traceState.EQ(TRACE_EXACT_ALLOC)) ? 'A' : 'a');
>> +   Log.write(' ');
>> +   Log.write(val);
>> +   loggedRecord = true;
>> + }
>> + traceState = TRACE_ALLOC_SIZE;
>>           } else if (traceState.EQ(TRACE_EXACT_IMMORTAL_ALLOC) ||
>>                      traceState.EQ(TRACE_IMMORTAL_ALLOC)) {
>> -            Log.write((traceState.EQ(TRACE_EXACT_IMMORTAL_ALLOC)) ? 'I' 
>> : 'i');
>> -            Log.write(' ');
>> -            Log.write(val);
>> + if (!OMIT_ALLOCS) {
>> +              Log.write((traceState.EQ(TRACE_EXACT_IMMORTAL_ALLOC)) ? 
>> 'I' : 'i');
>> +   Log.write(' ');
>> +   Log.write(val);
>> +   loggedRecord = true;
>> + }
>>             traceState = TRACE_ALLOC_SIZE;
>>           } else if (traceState.EQ(TRACE_BOOT_ALLOC)) {
>> -            Log.write('B');
>> -            Log.write(' ');
>> -            Log.write(val);
>> + if (!OMIT_BOOTALLOCS) {
>> +              Log.write('B');
>> +   Log.write(' ');
>> +   Log.write(val);
>> +   loggedRecord = true;
>> + }
>>             traceState = TRACE_BOOT_ALLOC_SIZE;
>>           } else if (traceState.EQ(TRACE_DEATH)) {
>> -            Log.write('D');
>> -            Log.write(' ');
>> -            Log.write(val);
>> + if (!OMIT_UNREACHABLES) {
>> +              Log.write('D');
>> +   Log.write(' ');
>> +   Log.write(val);
>> +   loggedRecord = true;
>> + }
>>             traceState = TRACE_DEATH_TIME;
>>           } else if (traceState.EQ(TRACE_BOOT_ALLOC_SIZE)) {
>> -            Log.write(val);
>> +            if (!OMIT_BOOTALLOCS)
>> +   Log.write(val);
>>             traceState = TRACE_NEW_RECORD;
>>           } else if (traceState.EQ(TRACE_ALLOC_SIZE)) {
>> -            Log.write(val);
>> + if (!OMIT_ALLOCS)
>> +              Log.write(val);
>>             traceState = TRACE_ALLOC_FP;
>>           } else if (traceState.EQ(TRACE_ALLOC_FP)) {
>> -            Log.write(val);
>> + if (!OMIT_ALLOCS)
>> +              Log.write(val);
>>             traceState = TRACE_ALLOC_THREAD;
>>           } else if (traceState.EQ(TRACE_ALLOC_THREAD)) {
>> -            Log.write(val);
>> + if (!OMIT_ALLOCS)
>> +              Log.write(val);
>>             traceState = TRACE_NEW_RECORD;
>>           } else if (traceState.EQ(TRACE_TIB_SET)) {
>> -            Log.write('T');
>> -            Log.write(' ');
>> -            Log.write(val);
>> + if (!OMIT_UPDATES) {
>> +              Log.write('T');
>> +   Log.write(' ');
>> +   Log.write(val);
>> +   loggedRecord = true;
>> + }
>>             traceState = TRACE_TIB_VALUE;
>>           } else if (traceState.EQ(TRACE_STATIC_SET)) {
>> -            Log.write('S');
>> -            Log.write(' ');
>> -            Log.write(val);
>> + if (!OMIT_UPDATES) {
>> +              Log.write('S');
>> +   Log.write(' ');
>> +   Log.write(val);
>> +   loggedRecord = true;
>> + }
>>             traceState = TRACE_STATIC_TARGET;
>>           } else if (traceState.EQ(TRACE_TIB_VALUE) ||
>> -                     traceState.EQ(TRACE_DEATH_TIME) ||
>>                      traceState.EQ(TRACE_STATIC_TARGET)) {
>> -            Log.write(val);
>> + if (!OMIT_UPDATES)
>> +              Log.write(val);
>> + traceState = TRACE_NEW_RECORD;
>> +   } else if (traceState.EQ(TRACE_DEATH_TIME)) {
>> + if (!OMIT_UNREACHABLES)
>> +   Log.write(val);
>>             traceState = TRACE_NEW_RECORD;
>>           } else if (traceState.EQ(TRACE_FIELD_SET) || 
>>                      traceState.EQ(TRACE_ARRAY_SET)) {
>> -            Log.write('U');
>> -            Log.write(' ');
>> -            Log.write(val);
>> + if (!OMIT_UPDATES) {
>> +              Log.write('U');
>> +   Log.write(' ');
>> +   Log.write(val);
>> +   loggedRecord = true;
>> + }
>>             traceState = TRACE_FIELD_SLOT;
>>           } else if (traceState.EQ(TRACE_FIELD_TARGET) || 
>>                      traceState.EQ(TRACE_ARRAY_TARGET)) {
>> -            Log.write(val);
>> + if (!OMIT_UPDATES)
>> +              Log.write(val);
>>             traceState = TRACE_NEW_RECORD;
>>           } else if (traceState.EQ(TRACE_FIELD_SLOT) ||
>>                      traceState.EQ(TRACE_ARRAY_ELEMENT)) {
>> -            Log.write(val);
>> + if (!OMIT_UPDATES)
>> +              Log.write(val);
>>             traceState = TRACE_FIELD_TARGET;
>> -          } else
>> +          } else {
>>             Assert.fail("Cannot understand directive!\n");
>> -          if (traceState.EQ(TRACE_NEW_RECORD)) {
>> +   }
>> +   if (traceState.EQ(TRACE_NEW_RECORD) && loggedRecord) {
>>             entriesNotFlushed++;
>>             Log.writeln();
>> -          } else {
>> +          } else if (loggedRecord) {
>>             Log.write(' ');
>>           }
>>         }
>>         if (entriesNotFlushed == 10) {
>> -          Log.flush();
>> +   if (!OMIT_OUTPUT)
>> +            Log.flush();
>>           entriesNotFlushed = 0;
>>         }
>>       }
>> Index: rvmRoot/MMTk/src/org/mmtk/utility/TraceGenerator.java
>> ===================================================================
>> --- rvmRoot.orig/MMTk/src/org/mmtk/utility/TraceGenerator.java
>> +++ rvmRoot/MMTk/src/org/mmtk/utility/TraceGenerator.java
>> @@ -375,7 +375,7 @@ public final class TraceGenerator 
>>       /* If we should add the object for further processing. */
>>       if (!getTraceLocal().isReachable(ref)) {
>>         TraceInterface.setDeathTime(ref, agePropagate);
>> -        worklist.push(ref);
>> +        worklist.pushTail(ref);
>>       } else {
>>         TraceInterface.setDeathTime(getTraceLocal().getForwardedReference(ref), 
>> agePropagate);
>>       }
>> @@ -388,28 +388,37 @@ public final class TraceGenerator 
>>    * as the latest reaching death time to an object.
>>    */
>>   private static final 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 = 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 */
>> -   Scan.scanObject(getTraceLocal(), ref);
>> - }
>> - /* Get the next object to process */
>> - ref = worklist.pop();
>> + /* The latest time an object can die. */
>> + agePropagate = Word.max();
>> +    if (Assert.VERIFY_ASSERTIONS) Assert._assert(!worklist.isEmpty());
>> + /* Process through the entire buffer. */
>> + ObjectReference ref = worklist.popTail();
>> + while (!ref.isNull()) {
>> +   Word currentAge = TraceInterface.getDeathTime(ref);
>> +   /*
>> +   Log.write('Z');
>> +   Log.write(' ');
>> +   Log.write(TraceInterface.getOID(ref));
>> +   Log.write(' ');
>> +   Log.write(currentAge);
>> +   Log.write(' ');
>> +   Log.write(agePropagate);
>> +   Log.writeln();
>> +   */
>> +   /* 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 */
>> + Scan.scanObject(getTraceLocal(), ref);
>>   }
>> -    }
>> +   /* Get the next object to process */
>> +   ref = worklist.popTail();
>> + }
>>   }
>>
>> -  private static final TraceLocal getTraceLocal() {
>> -    return ActivePlan.collector().getCurrentTrace();
>> -  }
>> +private static final TraceLocal getTraceLocal() {
>> + return ActivePlan.collector().getCurrentTrace();
>> +}
>>
>> }
>> Index: rvmRoot/MMTk/src/org/mmtk/utility/deque/LocalDeque.java
>> ===================================================================
>> --- rvmRoot.orig/MMTk/src/org/mmtk/utility/deque/LocalDeque.java
>> +++ rvmRoot/MMTk/src/org/mmtk/utility/deque/LocalDeque.java
>> @@ -6,6 +6,7 @@ package org.mmtk.utility.deque;
>>
>> import org.mmtk.plan.Plan;
>> import org.mmtk.utility.Constants;
>> +import org.mmtk.utility.Log;
>>
>> import org.mmtk.vm.Assert;
>>
>> @@ -92,6 +93,43 @@ public class LocalDeque extends LocalQue
>>     // if (VM_Interface.VerifyAssertions) enqueued++;
>>   }
>>
>> + /**
>> +  * Check whether there are sufficient entries in the tail buffer for
>> +  * a pending dequeue from the tail of the deque.  If there are not 
>> sufficient 
>> +  * entries, acquire a new buffer from the shared deque. Return true if 
>> +  * there are enough entries for the pending pop, false if the deque has 
>> +  * been exhausted.
>> +  *
>> +  * @param arity The arity of the values stored in this deque: there
>> +  * must be at least this many values available.
>> +  * @return True if there are enough entries for the pending pop,
>> +  * false if the queue has been exhausted.
>> +  */
>> +  protected final boolean checkTailDequeue(int arity) throws InlinePragma {
>> +    if (tail.EQ(tailBufferEnd)) {
>> +      return tailDequeueUnderflow(arity);
>> +    } else {
>> +   if (Assert.VERIFY_ASSERTIONS) 
>> Assert._assert(bufferOffset(tail).sLT(bufferSentinel(queue.getArity())));
>> +      return true;
>> + }
>> +  }
>> +
>> + /**
>> +  * Dequeue an address value from the tail buffer.  This is 
>> <i>unchecked</i>.  
>> +  * The caller must first call <code>checkTailDequeue()</code> to ensure 
>> +  * the buffer has sufficient values.
>> +  *
>> +  * @return the next address in the buffer
>> +  */
>> +  protected final Address uncheckedTailDequeue() throws InlinePragma {
>> +    if (Assert.VERIFY_ASSERTIONS) Assert._assert(tail.LT(tailBufferEnd));
>> + Address retVal;
>> + retVal = tail.loadAddress();
>> + tail = tail.plus(BYTES_IN_ADDRESS);
>> +    if (Assert.VERIFY_ASSERTIONS) 
>> Assert._assert(!retVal.toObjectReference().isNull());
>> + return retVal;
>> +  }
>> +
>>   /****************************************************************************
>>    * 
>>    * Private instance methods and fields
>> @@ -113,6 +151,47 @@ public class LocalDeque extends LocalQue
>>   }
>>
>>   /**
>> +   * There are not sufficient entries in the tail buffer for a pending
>> +   * pop.  Acquire a new tail buffer.  If the shared deque has no
>> +   * buffers available, consume the head if necessary.  Return false
>> +   * if entries cannot be acquired.
>> +   *
>> +   * @param arity The arity of this buffer (used for sanity test only).
>> +   * @return True if the buffer has been successfully replenished.
>> +   */
>> +  private final boolean tailDequeueUnderflow(int arity) 
>> +   throws NoInlinePragma {
>> +    if (Assert.VERIFY_ASSERTIONS) Assert._assert(arity == 
>> queue.getArity());
>> + do {
>> +   if (tail.NE(Deque.TAIL_INITIAL_VALUE))
>> +     queue.free(bufferStart(tail));
>> +   /*
>> +   // TODO: this may be wrong.  Possibly should be 
>> +   // tailBufferEnd = bufferLast + 1
>> +   // to account for non-full buffers
>> +   tail = queue.dequeue(arity, true);
>> +   tailBufferEnd = bufferEnd(tail);
>> +   */
>> +   tailBufferEnd = queue.dequeue(arity, true);
>> +   tail = bufferStart(tailBufferEnd);
>> + } while (tail.NE(Deque.TAIL_INITIAL_VALUE) && tail.EQ(tailBufferEnd));
>> +
>> + /*
>> + Log.write('U');
>> + Log.write(' ');
>> + Log.write(tail);
>> + Log.write(' ');
>> + Log.write(tailBufferEnd);
>> + Log.writeln();
>> + */
>> +  
>> + if (tail.EQ(Deque.TAIL_INITIAL_VALUE))
>> +   return !tailStarved(arity);
>> +  
>> + return true;
>> +  }
>> +
>> +  /**
>>    * Close the head buffer and enqueue it at the front of the 
>>    * shared buffer deque.
>>    * 
>> @@ -134,7 +213,8 @@ public class LocalDeque extends LocalQue
>>    */
>>   private final boolean tailStarved(int arity) {
>>       if (Assert.VERIFY_ASSERTIONS) Assert._assert(arity == 
>> queue.getArity());
>> -    // entries in tail, so consume tail
>> +
>> +    // entries in head, so consume head
>>     if (!bufferOffset(head).isZero()) {
>>       tailBufferEnd = head;
>>       tail = bufferStart(tailBufferEnd);
>> Index: 
>> rvmRoot/MMTk/src/org/mmtk/utility/deque/SortTODObjectReferenceStack.java
>> ===================================================================
>> --- 
>> rvmRoot.orig/MMTk/src/org/mmtk/utility/deque/SortTODObjectReferenceStack.java
>> +++ rvmRoot/MMTk/src/org/mmtk/utility/deque/SortTODObjectReferenceStack.java
>> @@ -6,6 +6,8 @@ package org.mmtk.utility.deque;
>>
>> import org.mmtk.vm.Assert;
>> import org.mmtk.utility.Constants;
>> +import org.mmtk.utility.Log;
>> +import org.mmtk.vm.TraceInterface;
>>
>> import org.vmmagic.unboxed.*;
>> import org.vmmagic.pragma.*;
>> @@ -48,7 +50,7 @@ public class SortTODObjectReferenceStack
>>   }
>>
>>   /**
>> -   * Push an address onto the address stack.
>> +   * Push an address onto the head of the address stack.
>>    * 
>>    * @param object the object to be pushed onto the object queue
>>    */
>> @@ -59,9 +61,22 @@ public class SortTODObjectReferenceStack
>>     uncheckedHeadInsert(addr);
>>   }
>>
>> +
>> +  /**
>> +   * Push an address onto the tail of the address stack.
>> +   * 
>> +   * @param object the object to be pushed onto the object queue
>> +   */
>> +  public final void pushTail(ObjectReference object) throws InlinePragma {
>> +    Address addr = object.toAddress();
>> +    if (Assert.VERIFY_ASSERTIONS) Assert._assert(!addr.isZero());
>> +    checkTailInsert(1);
>> +    uncheckedTailInsert(addr);
>> +  }
>> +
>>   /**
>> -   * Pop an address from the address stack, return zero if the stack
>> -   * is empty.
>> +   * Pop an address from the head of the address stack, return zero if 
>> +   * the stack is empty.
>>    * 
>>    * @return The next address in the address stack, or zero if the
>>    * stack is empty
>> @@ -75,6 +90,21 @@ public class SortTODObjectReferenceStack
>>   }
>>
>>   /**
>> +   * Pop an address from the tail of the address stack, return zero 
>> +   * if the stack is empty.
>> +   * 
>> +   * @return The next address in the address stack, or zero if the
>> +   * stack is empty
>> +   */
>> +  public final ObjectReference popTail() throws InlinePragma {
>> +    if (checkTailDequeue(1)) {
>> +      return uncheckedTailDequeue().toObjectReference();
>> +    } else {
>> +      return ObjectReference.nullReference();
>> +    }
>> +  }
>> +
>> +  /**
>>    * Check if the (local and shared) stacks are empty.
>>    * 
>>    * @return True if there are no more entries on the local & shared stack,
>> Index: rvmRoot/MMTk/src/org/mmtk/utility/deque/SharedDeque.java
>> ===================================================================
>> --- rvmRoot.orig/MMTk/src/org/mmtk/utility/deque/SharedDeque.java
>> +++ rvmRoot/MMTk/src/org/mmtk/utility/deque/SharedDeque.java
>> @@ -216,7 +216,7 @@ public class SharedDeque extends Deque i
>>   /**
>>    * Set the "prev" pointer in a buffer forming the linked buffer chain.
>>    * 
>> -   * @param buf The buffer whose next field is to be set.
>> +   * @param buf The buffer whose prev field is to be set.
>>    * @param prev The reference to which prev should point.
>>    */
>>   private final void setPrev(Address buf, Address prev) {
>> @@ -224,10 +224,10 @@ public class SharedDeque extends Deque i
>>   }
>>
>>   /**
>> -   * Get the "next" pointer in a buffer forming the linked buffer chain.
>> +   * Get the "prev" pointer in a buffer forming the linked buffer chain.
>>    * 
>> -   * @param buf The buffer whose next field is to be returned.
>> -   * @return The next field for this buffer.
>> +   * @param buf The buffer whose prev field is to be returned.
>> +   * @return The prev field for this buffer.
>>    */
>>   protected final Address getPrev(Address buf) {
>>     return buf.loadAddress(PREV_OFFSET);
>>
>>
>> ------------------------------------------------------------------------
>>
>> -------------------------------------------------------------------------
>> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
>> Build the coolest Linux based applications with Moblin SDK & win great prizes
>> Grand prize is a trip for two to an Open Source event anywhere in the world
>> http://moblin-contest.org/redirect.php?banner_id=100&url=/
>>
>>
>> ------------------------------------------------------------------------
>>
>> _______________________________________________
>> Jikesrvm-researchers mailing list
>> Jik...@li...
>> https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers
> 
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> Jikesrvm-researchers mailing list
> Jik...@li...
> https://lists.sourceforge.net/lists/listinfo/jikesrvm-researchers