Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-4243978

(ref) Race condition in Reference.enqueue()

XMLWordPrintable

    • b14
    • generic, x86
    • generic, windows_95, windows_nt
    • Verified

      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

            ysr Y. Ramakrishna
            miflemi Mick Fleming
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated:
              Resolved:
              Imported:
              Indexed: