Change ReferenceQueue order from LIFO to FIFO.

LIFO order of FinalizerReference.queue breaks runFinalization().
runFinalization() creates a Sentinel finalizable object and waits
for it to be finalized. As FinalizerReference.queue is LIFO,
the Sentinel object is placed at the beginning of the queue and
then gets finalized first. So the method returns even though
objects placed in the queue before the Sentinel are not finalized.

This patch changes the queue order to FIFO to ensure that all
elements enqueued before the Sentinel are finalized before it.

bug: https://code.google.com/p/android/issues/detail?id=37980

Change-Id: Ie6bc96e6a3759bc36ce6586066052b6d6bbe8d52
Signed-off-by: Elena Sayapina <elena.v.sayapina@intel.com>

1 files changed, 12 insertions, 9 deletions

diff --git a/luni/src/main/java/java/lang/ref/ReferenceQueue.java b/luni/src/main/java/java/lang/ref/ReferenceQueue.java
index 2b8089c..7ddd97d 100644
--- a/luni/src/main/java/java/lang/ref/ReferenceQueue.java
+++ b/luni/src/main/java/java/lang/ref/ReferenceQueue.java
@@ -28,6 +28,7 @@ public class ReferenceQueue<T> {
     private static final int NANOS_PER_MILLI = 1000000;
 
     private Reference<? extends T> head;
+    private Reference<? extends T> tail;
 
     /**
      * Constructs a new instance of this class.
@@ -48,18 +49,16 @@ public class ReferenceQueue<T> {
             return null;
         }
 
-        Reference<? extends T> ret;
+        Reference<? extends T> ret = head;
 
-        ret = head;
-
-        if (head == head.queueNext) {
+        if (head == tail) {
+            tail = null;
             head = null;
         } else {
             head = head.queueNext;
         }
 
         ret.queueNext = null;
-
         return ret;
     }
 
@@ -133,12 +132,16 @@ public class ReferenceQueue<T> {
      *            reference object to be enqueued.
      */
     synchronized void enqueue(Reference<? extends T> reference) {
-        if (head == null) {
-            reference.queueNext = reference;
+        if (tail == null) {
+            head = reference;
         } else {
-            reference.queueNext = head;
+            tail.queueNext = reference;
         }
-        head = reference;
+
+        // The newly enqueued reference becomes the new tail, and always
+        // points to itself.
+        tail = reference;
+        tail.queueNext = reference;
         notify();
     }