1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  * Copyright (c) 1997, 2005, Oracle and/or its affiliates. All rights reserved.
4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5  *
6  * This code is free software; you can redistribute it and/or modify it
7  * under the terms of the GNU General Public License version 2 only, as
8  * published by the Free Software Foundation.  Oracle designates this
9  * particular file as subject to the "Classpath" exception as provided
10  * by Oracle in the LICENSE file that accompanied this code.
11  *
12  * This code is distributed in the hope that it will be useful, but WITHOUT
13  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15  * version 2 for more details (a copy is included in the LICENSE file that
16  * accompanied this code).
17  *
18  * You should have received a copy of the GNU General Public License version
19  * 2 along with this work; if not, write to the Free Software Foundation,
20  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21  *
22  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
23  * or visit www.oracle.com if you need additional information or have any
24  * questions.
25  */
26 
27 package java.lang.ref;
28 
29 import java.util.concurrent.atomic.AtomicInteger;
30 
31 /**
32  * Reference queues, to which registered reference objects are appended by the
33  * garbage collector after the appropriate reachability changes are detected.
34  *
35  * @author   Mark Reinhold
36  * @since    1.2
37  */
38 // BEGIN Android-changed: Reimplemented to accomodate a different GC and compiler.
39 
40 public class ReferenceQueue<T> {
41 
42     // Reference.queueNext will be set to sQueueNextUnenqueued to indicate
43     // when a reference has been enqueued and removed from its queue.
44     private static final Reference sQueueNextUnenqueued = new PhantomReference(null, null);
45 
46     // NOTE: This implementation of ReferenceQueue is FIFO (queue-like) whereas
47     // the OpenJdk implementation is LIFO (stack-like).
48     private Reference<? extends T> head = null;
49     private Reference<? extends T> tail = null;
50 
51     private final Object lock = new Object();
52 
53     // Current target of enqueuePending. Either a Cleaner or a ReferenceQueue.
54     private static Object currentTarget = null;
55 
56     /**
57      * Constructs a new reference-object queue.
58      */
ReferenceQueue()59     public ReferenceQueue() { }
60 
61     /**
62      * Enqueue the given reference onto this queue.
63      * The caller is responsible for ensuring the lock is held on this queue,
64      * and for calling notifyAll on this queue after the reference has been
65      * enqueued. Returns true if the reference was enqueued successfully,
66      * false if the reference had already been enqueued.
67      * @GuardedBy("lock")
68      */
enqueueLocked(Reference<? extends T> r)69     private boolean enqueueLocked(Reference<? extends T> r) {
70         // Verify the reference has not already been enqueued.
71         if (r.queueNext != null) {
72             return false;
73         }
74 
75         // Callers already handled sun.misc.Cleaner instances.
76         if (tail == null) {
77             head = r;
78         } else {
79             tail.queueNext = r;
80         }
81         tail = r;
82         tail.queueNext = r;
83         return true;
84     }
85 
86     /**
87      * The queue or Runnable from a sun.misc.Cleaner currently being targeted by enqueuePending.
88      * Used only to get slightly informative output for timeouts. May be read via a data race,
89      * but only for crash debugging output.
90      * @hide
91      */
getCurrentTarget()92     public static Object getCurrentTarget() {
93         if (currentTarget instanceof sun.misc.Cleaner cleaner) {
94             // The printed version of the Runnable is likely to be more informative than the
95             // Cleaner itself.
96             return cleaner.getThunk();
97         } else {
98             return currentTarget;
99         }
100     }
101 
102     /**
103      * Test if the given reference object has been enqueued but not yet
104      * removed from the queue, assuming this is the reference object's queue.
105      */
isEnqueued(Reference<? extends T> reference)106     boolean isEnqueued(Reference<? extends T> reference) {
107         synchronized (lock) {
108             return reference.queueNext != null && reference.queueNext != sQueueNextUnenqueued;
109         }
110     }
111 
112     /**
113      * Enqueue the reference object on the receiver.
114      *
115      * @param reference
116      *            reference object to be enqueued.
117      * @return true if the reference was enqueued.
118      */
enqueue(Reference<? extends T> reference)119     boolean enqueue(Reference<? extends T> reference) {
120         synchronized (lock) {
121             if (reference instanceof sun.misc.Cleaner cl) {
122                 // If this reference is a Cleaner, then simply invoke the clean method instead of
123                 // enqueueing it in the queue. Cleaners are associated with placeholder queues
124                 // that are never polled (except for error checking) and objects are never
125                 // enqueued on them.
126                 cl.clean();
127 
128                 // Update queueNext to indicate that the reference has been
129                 // enqueued, but is now removed from the queue.
130                 reference.queueNext = sQueueNextUnenqueued;
131                 return true;
132             }
133 
134             if (enqueueLocked(reference)) {
135                 lock.notifyAll();
136                 return true;
137             }
138             return false;
139         }
140     }
141 
142     // @GuardedBy("lock")
reallyPollLocked()143     private Reference<? extends T> reallyPollLocked() {
144         if (head != null) {
145             Reference<? extends T> r = head;
146             if (head == tail) {
147                 tail = null;
148                 head = null;
149             } else {
150                 head = head.queueNext;
151             }
152 
153             // Update queueNext to indicate that the reference has been
154             // enqueued, but is now removed from the queue.
155             r.queueNext = sQueueNextUnenqueued;
156             return r;
157         }
158 
159         return null;
160     }
161 
162     /**
163      * Polls this queue to see if a reference object is available.  If one is
164      * available without further delay then it is removed from the queue and
165      * returned.  Otherwise this method immediately returns <tt>null</tt>.
166      *
167      * @return  A reference object, if one was immediately available,
168      *          otherwise <code>null</code>
169      */
poll()170     public Reference<? extends T> poll() {
171         synchronized (lock) {
172             return reallyPollLocked();
173         }
174     }
175 
176     /**
177      * Removes the next reference object in this queue, blocking until either
178      * one becomes available or the given timeout period expires.
179      *
180      * <p> This method does not offer real-time guarantees: It schedules the
181      * timeout as if by invoking the {@link Object#wait(long)} method.
182      *
183      * @param  timeout  If positive, block for up to <code>timeout</code>
184      *                  milliseconds while waiting for a reference to be
185      *                  added to this queue.  If zero, block indefinitely.
186      *
187      * @return  A reference object, if one was available within the specified
188      *          timeout period, otherwise <code>null</code>
189      *
190      * @throws  IllegalArgumentException
191      *          If the value of the timeout argument is negative
192      *
193      * @throws  InterruptedException
194      *          If the timeout wait is interrupted
195      */
remove(long timeout)196     public Reference<? extends T> remove(long timeout)
197         throws IllegalArgumentException, InterruptedException
198     {
199         if (timeout < 0) {
200             throw new IllegalArgumentException("Negative timeout value");
201         }
202         synchronized (lock) {
203             Reference<? extends T> r = reallyPollLocked();
204             if (r != null) return r;
205             long start = (timeout == 0) ? 0 : System.nanoTime();
206             for (;;) {
207                 lock.wait(timeout);
208                 r = reallyPollLocked();
209                 if (r != null) return r;
210                 if (timeout != 0) {
211                     long end = System.nanoTime();
212                     timeout -= (end - start) / 1000_000;
213                     if (timeout <= 0) return null;
214                     start = end;
215                 }
216             }
217         }
218     }
219 
220     /**
221      * Removes the next reference object in this queue, blocking until one
222      * becomes available.
223      *
224      * @return A reference object, blocking until one becomes available
225      * @throws  InterruptedException  If the wait is interrupted
226      */
remove()227     public Reference<? extends T> remove() throws InterruptedException {
228         return remove(0);
229     }
230 
231     /**
232      * Enqueue the given list of currently pending (unenqueued) references.
233      *
234      * @hide
235      */
enqueuePending(Reference<?> list, AtomicInteger progressCounter)236     public static void enqueuePending(Reference<?> list, AtomicInteger progressCounter) {
237         Reference<?> start = list;
238         do {
239             ReferenceQueue queue = list.queue;
240             if (queue == null || sun.misc.Cleaner.isCleanerQueue(queue)) {
241                 Reference<?> next = list.pendingNext;
242                 // Always make pendingNext a self-loop to preserve the invariant that
243                 // once enqueued, pendingNext is non-null -- without leaking
244                 // the object pendingNext was previously pointing to.
245                 list.pendingNext = list;
246                 if (queue != null) {
247                     // This is a Cleaner. Run directly without additional synchronization.
248                     sun.misc.Cleaner cl = (sun.misc.Cleaner) list;
249                     currentTarget = cl;
250                     cl.clean();  // Idempotent. No need to check queueNext first. Handles all
251                                  // exceptions.
252                     list.queueNext = sQueueNextUnenqueued;
253                 }
254                 list = next;
255             } else {
256                 currentTarget = queue;
257                 // To improve performance, we try to avoid repeated
258                 // synchronization on the same queue by batching enqueueing of
259                 // consecutive references in the list that have the same
260                 // queue. We limit this so that progressCounter gets incremented
261                 // occasionally,
262                 final int MAX_ITERS = 100;
263                 int i = 0;
264                 synchronized (queue.lock) {
265                     // Nothing in here should throw, even OOME,
266                     do {
267                         Reference<?> next = list.pendingNext;
268                         list.pendingNext = list;
269                         queue.enqueueLocked(list);
270                         list = next;
271                     } while (list != start && list.queue == queue && ++i < MAX_ITERS);
272                     queue.lock.notifyAll();
273                 }
274             }
275             progressCounter.incrementAndGet();
276         } while (list != start);
277         currentTarget = null;
278         sun.misc.Cleaner.checkCleanerQueueEmpty();
279     }
280 
281     /**
282      * List of references that the GC says need to be enqueued.
283      * Protected by ReferenceQueue.class lock.
284      * @hide
285      */
286     public static Reference<?> unenqueued = null;
287 
add(Reference<?> list)288     static void add(Reference<?> list) {
289         synchronized (ReferenceQueue.class) {
290             if (unenqueued == null) {
291                 unenqueued = list;
292             } else {
293                 // Find the last element in unenqueued.
294                 Reference<?> last = unenqueued;
295                 while (last.pendingNext != unenqueued) {
296                   last = last.pendingNext;
297                 }
298                 // Add our list to the end. Update the pendingNext to point back to enqueued.
299                 last.pendingNext = list;
300                 last = list;
301                 while (last.pendingNext != list) {
302                     last = last.pendingNext;
303                 }
304                 last.pendingNext = unenqueued;
305             }
306             ReferenceQueue.class.notifyAll();
307         }
308     }
309 }
310 // END Android-changed: Reimplemented to accomodate a different GC and compiler.
311