Name: mf23781			Date: 06/04/99



     Test Case and Failure Data:

         Description of Problem:
      
                The problem is that the (private) next field is used     
                for two different linked lists. The first list is the    
                "Pending" list of reference objects, which the garbage   
                collector prepares for the referenceHandler thread.      
                The second linked list is the list that implements the   
                queue of the reference objects. The user program may     
                invoke the enqueue method on an object in the Pending    
                list. If that happens, the Pending list and/or the queue 
                may be destroyed. They indeed are destroyed as the       
                following test shows.                                    
                       
                This problem was found following a code review which 
                was a part of a porting exercise.
                
        Test Case description
                
                
                The purpose of this test is to let the program enqueue   
                a reference object that is currently in the Pending      
                list. In order to do this, We create "iterations" number 
                of objects with referenced objects referecing them .     
                We then make the objects become weakly reachable so that 
                the garbage collector will put the reference objects in  
                Pending list. At the same time, the program enqueues     
                some of these reference objects (all the ones with odd   
                numbers). The test shows that most of the objects are    
                not properly queued. The number of queued object is      
                somewhat arbitrary as expected. (If we don't let the     
                program enqueue reference objects explicitly, but let    
                the collector do all the work by itself, then all the    
                reference objects are properly queued).                  
                                                         
        Test Case Source Code
           ---- test case code starts here ----
/**************************************************************
 *   This is a test program meant to expose a bug in the      *
 *   current implementation of the reference objects.         *
 *                                                            *
 *   A description of the bug:                                *
 *   -------------------------                                *
 *   The problem is that the (private) next field is used     *
 *   for two different linked lists. The first list is the    *
 *   "Pending" list of reference objects, which the garbage   *
 *   collector prepares for the referenceHandler thread.      *
 *   The second linked list is the list that implements the   *
 *   queue of the reference objects. The user program may     *
 *   invoke the enqueue method on an object in the Pending    *
 *   list. If that happens, the Pending list and/or the queue *
 *   may be destroyed. They indeed are destroyed as the       *
 *   following test shows.                                    *
 *                                                            *
 *   A descritpion of the test:                               *
 *   --------------------------                               *
 *   The purpose of this test is to let the program enqueue   *
 *   a reference object that is currently in the Pending      * 
 *   list. In order to do this, We create "iterations" number *
 *   of objects with referenced objects referecing them .     *
 *   We then make the objects become weakly reachable so that *
 *   the garbage collector will put the reference objects in  *
 *   Pending list. At the same time, the program enqueues     *
 *   some of these reference objects (all the ones with odd   *
 *   numbers). The test shows that most of the objects are    *
 *   not properly queued. The number of queued object is      *
 *   somewhat arbitrary as expected. (If we don't let the     *
 *   program enqueue reference objects explicitly, but let    *
 *   the collector do all the work by itself, then all the    *
 *   reference objects are properly queued).                  *
 *                                                            *
 ************************************************************** */


import java.lang.ref.*;
import java.lang.*;


public class ref_check {

  final static boolean debug = true;
  final static int iterations = 100;
  final static int gc_trigger = 10;
  static int[] a = new int[2 * iterations];
  // Keep all weak references alive with the following array. 
  static NumberedWeakReference[] b = new NumberedWeakReference[iterations];
  static int length;

  public static void main(String[] argv){

    // Get the runtime "object" so that we can force GC.
    Runtime RunT = Runtime.getRuntime();
    if (debug) System.out.println("Starting the test.");
    // Raise thread priority to match the referenceHandler 
    // priority, so that they can race also on a uniprocessor. 
    raisePriority();

    int i;
    ReferenceQueue Q = new ReferenceQueue();

    // Create many reference objects.
    // Each points to a unique integer object. 
    // Then, get the integers collected, and race with the 
    // collector on queuing (half of) the reference objects. 
    // The weak references are numbered, so we can later 
    // check which of them are queued. 
    Integer Obj = new Integer(0); 
    NumberedWeakReference weaky = new NumberedWeakReference(Obj,Q,0);
    for (i=1; i<iterations; i++) {
       // Create one object and kill another. 
       Obj = new Integer(i);
       // Trigger gc each gc_trigger iterations.
       if ( (i % gc_trigger) == 0 ) RunT.gc();
       // Enqueue the odd objects (from previous iteration). 
       if ( (i % 2) == 0 ) weaky.enqueue();
       // Keep previous weaky alive.
       b[i-1] = weaky;
       // Get a new weaky for the new object. 
       weaky = new NumberedWeakReference(Obj,Q,i);
    }


    //  Now do a final collection to round up. 
        RunT.gc();


    // Now, after everything has hopefully been queued, let's check 
    // that everything is indeed in the queue.
    if (debug) System.out.println("Reading the queue");
    //  Empty queue and record numbers into a[];
    i = 0;
    NumberedWeakReference weakRead = (NumberedWeakReference) Q.poll();
    while (weakRead != null) {
         a[i++] = weakRead.number;
         weakRead = (NumberedWeakReference) Q.poll();
    }
    length = i;
    if (debug) System.out.println("Number of elements in the queue = " + length);
    // Use the last object or the comipler kills it. 
    System.out.println("Sorry, I must write " + Obj + " to prevent compiler optimizations.");

    

    // Sort the first "length" elements in array "a[]".
    sort();
    
    // Check results: Are all enqueued? 
    if (debug) System.out.println("Start of final check");
    boolean fail = (length != (iterations -1));
    for (i=0; i<length; i++) {
      if (a[i] != i) {
	if (debug) System.out.println("a["+i+"] is not "+i+" but "+a[i]);
        fail = true;
      }
    }
    if (fail) {
       System.out.println("********   Test failed.   *********");
       int shouldBe = iterations - 1;
       System.out.println("Only "+length+" reference objects have been queued out of "+shouldBe+".");
       System.out.println(" The following numbers have not been queued: ");
       int missing = 0;
       int element = 0;
       for (i=0; i<length; i++) {
          while ( (a[i] != element) & (element < shouldBe) ) {
               System.out.print(element+" ");
               if (missing%20 == 19) System.out.println(" ");
               missing++; 
               element++;
          }
          element++;
       }
       System.out.print("\n");
    }
    else {
       System.out.println(" ********   Test succeeded.   *********");
    }

    if (debug) System.out.println("End of test");
    
  }

  // This bubble sorts the first "length" elements in array "a".
  public static void sort(){
    int hold, pass, i;
    if (debug) System.out.println("Sorting. Length="+length);
    for (pass = 1; pass < length; pass++) { // passes over the array
      for (i=0; i < length-pass ; i++){  //  a single pass
        if ( a[i] > a[i+1] ) {  // then swap
           hold = a[i];
           a[i] = a[i+1];
           a[i+1] = hold;
        }

      }  // End of i loop 
    } // End of pass loop
  }


  // Raise thread priority to compete with the referce handler. 
  // This is (probably) only required for a uniprocessor.
  static void raisePriority(){
        	Thread tr = Thread.currentThread();
        	tr.setPriority(Thread.MAX_PRIORITY);
  }


}   // ENd of class ref_check 

class NumberedWeakReference extends WeakReference {
  //  Add an integer to identify the weak reference object.
  int number;
  
  public NumberedWeakReference(Object referent, ReferenceQueue q, int i){
    super(referent,q);
    number = i;
  }
  
}

           ---- test case code ends here ----
        
        

        
(4) Targeted FCS Release:
     
       1.2.2? As this was found as part of a porting exercise a "description
       of how it is to be fixed" is more important at this stage than the fix.

(5) Operational/Business Justification:

       Impact of bug on affected product:
           Will affect the design of a JVM port.
           This design (and others that use concurrent GC) could be affected
           by this problem.
       
(6) Suggested Fix:

        Suggested Fix:
           The problem arises when a enqueue requested is made to the reference
           object.  As this could be in the pending state, the chain of
           pending references/reference queue could be damaged.
           
           Could a doubly linked list be implemented that could 
           potentially remove an element from the pending list
           without losing any other information.
           
           Are these lists interacted with in any other location other
           than the java.lang.ref package?
        
        Documentation of how root cause was found:
            Found as part of code review.  Test case written to expose the problem.
        
        Alternative Fixes (advantages/disadvntages):
            A large fix is to use two different queues for the pending
            and the enqueue lists.  This would prevent any difficulties
            with confusing the two lists.
        
        Results of testing in application/customer environment:
            Test case only provided.  Attempting to incorporate the
            doubly linked list
        
        Regression Test Run Status/Results:
            Regression test case provided.  This indicates the results
            of what reference were able to be recovered from the queue.
        
        JCK Test run status:
           n/a
        


(Review ID: 83933)

======================================================================

Also from the Licensee :
Solaris does also show the problem based on the test case!  It tends
towards passing, but if you reduce the heap size to 2048kb then it fails
regularly.
On NT increasing the heap size, to the maximum 65Mb.  then it will pass -
the trend though is towards failure.

I'm beginning to suspect that the test case may be mistaken in what it is
testing.  Can you confirm what is actually happening to items on the
reference queue ?

Items are added to the reference queue when there is a change to its
reachability, eg a change from strongly reference to weak referenced.  How
do items get removed from the ReferenceQueue.  The api spec seems to
suggest that the application program generally would take responsbility for
clearing the queue.
But it does suggest that this may be required for weak or soft references.
When do the refereants actually get reclaimed for each of the weak, soft,
phantom refs?

mick.fleming@Ireland 1999-06-09

Name: akC45999			Date: 10/04/99


The following JCK-13beta test is failed due to this bug:
api/java_lang/ref/ReferenceQueue/index.html#ReferenceQueue0600


======================================================================
###@###.### 10/22/04 14:02 GMT