Implement reference queuing in managed code.

This change adds a thread to the core library which receives a list of
references after a garbage collection and enqueues each element.  This
list is constructed by linking together the pendingNext field of cleared
references into a circular queue.

To support this change, the pendingNext field has been replaced by the
new zombie field for the purposes of providing a strongly reachable
location within a FinalizerReference class instance.

Change-Id: Id09133e44c850797e7f14c5471123a036d027c80

6 files changed, 121 insertions, 25 deletions

diff --git a/dalvik/src/main/java/dalvik/system/Zygote.java b/dalvik/src/main/java/dalvik/system/Zygote.java
index 791460b..1cdc52c 100644
--- a/dalvik/src/main/java/dalvik/system/Zygote.java
+++ b/dalvik/src/main/java/dalvik/system/Zygote.java
@@ -17,6 +17,7 @@
 package dalvik.system;
 
 import java.lang.FinalizerThread;
+import java.lang.ref.ReferenceQueueThread;
 
 /**
  * Provides access to the Dalvik "zygote" feature, which allows a VM instance to
@@ -48,10 +49,12 @@ public class Zygote {
     private Zygote() {}
 
     private static void preFork() {
+        ReferenceQueueThread.stopReferenceQueue();
         FinalizerThread.stopFinalizer();
     }
 
     private static void postFork() {
+        ReferenceQueueThread.startReferenceQueue();
         FinalizerThread.startFinalizer();
     }
 
diff --git a/luni/src/main/java/java/lang/FinalizerThread.java b/luni/src/main/java/java/lang/FinalizerThread.java
index 62e3b5a..8b6f337 100644
--- a/luni/src/main/java/java/lang/FinalizerThread.java
+++ b/luni/src/main/java/java/lang/FinalizerThread.java
@@ -27,10 +27,6 @@ public final class FinalizerThread extends Thread {
     private static FinalizerThread finalizerThread;
     private static boolean idle;
 
-    static {
-        startFinalizer();
-    }
-
     private FinalizerThread() {
         super("Finalizer");
         setDaemon(true);
diff --git a/luni/src/main/java/java/lang/ref/FinalizerReference.java b/luni/src/main/java/java/lang/ref/FinalizerReference.java
index 27e9f59..a3f9024 100644
--- a/luni/src/main/java/java/lang/ref/FinalizerReference.java
+++ b/luni/src/main/java/java/lang/ref/FinalizerReference.java
@@ -24,6 +24,8 @@ import java.lang.FinalizerThread;
 public final class FinalizerReference<T> extends Reference<T> {
     private static FinalizerReference head = null;
 
+    private T zombie;
+
     private FinalizerReference prev;
 
     private FinalizerReference next;
@@ -34,12 +36,12 @@ public final class FinalizerReference<T> extends Reference<T> {
 
     @Override
     public T get() {
-        return (T) pendingNext;
+        return zombie;
     }
 
     @Override
     public void clear() {
-        pendingNext = null;
+        zombie = null;
     }
 
     static void add(Object referent) {
diff --git a/luni/src/main/java/java/lang/ref/Reference.java b/luni/src/main/java/java/lang/ref/Reference.java
index aa12625..db33813 100644
--- a/luni/src/main/java/java/lang/ref/Reference.java
+++ b/luni/src/main/java/java/lang/ref/Reference.java
@@ -67,12 +67,12 @@ public abstract class Reference<T> {
     volatile Reference queueNext;
 
     /**
-     * Used internally by the VM.  This field forms a singly-linked
-     * list of reference objects awaiting processing by the garbage
-     * collector.
+     * Used internally by the VM.  This field forms a circular and
+     * singly linked list of reference objects discovered by the
+     * garbage collector and awaiting processing by the reference
+     * queue thread.
      */
-    @SuppressWarnings("unchecked")
-    volatile Object pendingNext;
+    volatile Reference<?> pendingNext;
 
     /**
      * Constructs a new instance of this class.
@@ -94,24 +94,12 @@ public abstract class Reference<T> {
     }
 
     /**
-     * An implementation of .enqueue() that is safe for the VM to call.
-     * If a Reference object is a subclass of any of the
-     * java.lang.ref.*Reference classes and that subclass overrides enqueue(),
-     * the VM may not call the overridden method.
-     * VM requirement: this method <em>must</em> be called "enqueueInternal",
-     * have the signature "()Z", and be private.
+     * Adds an object to its reference queue.
      *
      * @return {@code true} if this call has caused the {@code Reference} to
      * become enqueued, or {@code false} otherwise
      */
-    @SuppressWarnings("unchecked")
-    private synchronized boolean enqueueInternal() {
-        /* VM requirement:
-         * The VM assumes that this function only does work
-         * if "(queue != null && queueNext == null)".
-         * If that changes, Dalvik needs to change, too.
-         * (see MarkSweep.c:enqueueReference())
-         */
+    final synchronized boolean enqueueInternal() {
         if (queue != null && queueNext == null) {
             queue.enqueue(this);
             queue = null;
diff --git a/luni/src/main/java/java/lang/ref/ReferenceQueue.java b/luni/src/main/java/java/lang/ref/ReferenceQueue.java
index 3f02a59..0c04467 100644
--- a/luni/src/main/java/java/lang/ref/ReferenceQueue.java
+++ b/luni/src/main/java/java/lang/ref/ReferenceQueue.java
@@ -130,4 +130,19 @@ public class ReferenceQueue<T> {
         head = reference;
         notify();
     }
+
+    static Reference unenqueued = null;
+
+    static void add(Reference<?> list) {
+        synchronized (ReferenceQueue.class) {
+            if (unenqueued == null) {
+                unenqueued = list;
+            } else {
+                Reference<?> next = unenqueued.pendingNext;
+                unenqueued.pendingNext = list.pendingNext;
+                list.pendingNext = next;
+            }
+            ReferenceQueue.class.notifyAll();
+        }
+    }
 }
diff --git a/luni/src/main/java/java/lang/ref/ReferenceQueueThread.java b/luni/src/main/java/java/lang/ref/ReferenceQueueThread.java
new file mode 100644
index 0000000..201c240
--- /dev/null
+++ b/luni/src/main/java/java/lang/ref/ReferenceQueueThread.java
@@ -0,0 +1,92 @@
+/*
+ * Copyright (C) 2011 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package java.lang.ref;
+
+/**
+ * @hide
+ */
+public final class ReferenceQueueThread extends Thread {
+    private static ReferenceQueueThread thread = null;
+
+    public ReferenceQueueThread() {
+        super("ReferenceQueue");
+        setDaemon(true);
+    }
+
+    /**
+     * Moves each element from the pending list to the reference queue
+     * list.  The pendingNext field is owned by the garbage collector
+     * so no synchronization is required to perform the unlinking.
+     */
+    private static void doEnqueue(Reference list) {
+        while (list != null) {
+            Reference reference;
+            if (list == list.pendingNext) {
+                reference = list;
+                reference.pendingNext = null;
+                list = null;
+            } else {
+                reference = list.pendingNext;
+                list.pendingNext = reference.pendingNext;
+                reference.pendingNext = null;
+            }
+            reference.enqueueInternal();
+        }
+    }
+
+    public void run() {
+        for (;;) {
+            Reference list;
+            try {
+                synchronized (ReferenceQueue.class) {
+                    while (ReferenceQueue.unenqueued == null) {
+                        ReferenceQueue.class.wait();
+                    }
+                    list = ReferenceQueue.unenqueued;
+                    ReferenceQueue.unenqueued = null;
+                }
+            } catch (InterruptedException ex) {
+                break;
+            }
+            doEnqueue(list);
+        }
+    }
+
+    public static synchronized void startReferenceQueue() {
+        if (thread != null) {
+            throw new IllegalStateException("already started");
+        }
+        thread = new ReferenceQueueThread();
+        thread.start();
+    }
+
+    public static synchronized void stopReferenceQueue() {
+        if (thread == null) {
+            throw new IllegalStateException("not started");
+        }
+        thread.interrupt();
+        for (;;) {
+            try {
+                thread.join();
+            } catch (InterruptedException ex) {
+                continue;
+            }
+            break;
+        }
+        thread = null;
+    }
+}