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 sun.misc.Cleaner; 30 import java.util.concurrent.atomic.AtomicInteger; 31 32 /** 33 * Reference queues, to which registered reference objects are appended by the 34 * garbage collector after the appropriate reachability changes are detected. 35 * 36 * @author Mark Reinhold 37 * @since 1.2 38 */ 39 // BEGIN Android-changed: Reimplemented to accomodate a different GC and compiler. 40 41 public class ReferenceQueue<T> { 42 43 // Reference.queueNext will be set to sQueueNextUnenqueued to indicate 44 // when a reference has been enqueued and removed from its queue. 45 private static final Reference sQueueNextUnenqueued = new PhantomReference(null, null); 46 47 // NOTE: This implementation of ReferenceQueue is FIFO (queue-like) whereas 48 // the OpenJdk implementation is LIFO (stack-like). 49 private Reference<? extends T> head = null; 50 private Reference<? extends T> tail = null; 51 52 private final Object lock = new Object(); 53 54 // Current target of enqueuePending. Either a Cleaner or a ReferenceQueue. 55 private static Object currentTarget = null; 56 57 /** 58 * Constructs a new reference-object queue. 59 */ ReferenceQueue()60 public ReferenceQueue() { } 61 62 /** 63 * Enqueue the given reference onto this queue. 64 * The caller is responsible for ensuring the lock is held on this queue, 65 * and for calling notifyAll on this queue after the reference has been 66 * enqueued. Returns true if the reference was enqueued successfully, 67 * false if the reference had already been enqueued. 68 * @GuardedBy("lock") 69 */ enqueueLocked(Reference<? extends T> r)70 private boolean enqueueLocked(Reference<? extends T> r) { 71 // Verify the reference has not already been enqueued. 72 if (r.queueNext != null) { 73 return false; 74 } 75 76 if (r instanceof Cleaner) { 77 // If this reference is a Cleaner, then simply invoke the clean method instead 78 // of enqueueing it in the queue. Cleaners are associated with dummy queues that 79 // are never polled and objects are never enqueued on them. 80 Cleaner cl = (sun.misc.Cleaner) r; 81 cl.clean(); 82 83 // Update queueNext to indicate that the reference has been 84 // enqueued, but is now removed from the queue. 85 r.queueNext = sQueueNextUnenqueued; 86 return true; 87 } 88 89 if (tail == null) { 90 head = r; 91 } else { 92 tail.queueNext = r; 93 } 94 tail = r; 95 tail.queueNext = r; 96 return true; 97 } 98 99 /** 100 * The queue or Runnable from a sun.misc.Cleaner currently being targeted by enqueuePending. 101 * Used only to get slightly informative output for timeouts. May be read via a data race, 102 * but only for crash debugging output. 103 * @hide 104 */ getCurrentTarget()105 public static Object getCurrentTarget() { 106 if (currentTarget instanceof sun.misc.Cleaner cleaner) { 107 // The printed version of the Runnable is likely to be more informative than the 108 // Cleaner itself. 109 return cleaner.getThunk(); 110 } else { 111 return currentTarget; 112 } 113 } 114 115 /** 116 * Test if the given reference object has been enqueued but not yet 117 * removed from the queue, assuming this is the reference object's queue. 118 */ isEnqueued(Reference<? extends T> reference)119 boolean isEnqueued(Reference<? extends T> reference) { 120 synchronized (lock) { 121 return reference.queueNext != null && reference.queueNext != sQueueNextUnenqueued; 122 } 123 } 124 125 /** 126 * Enqueue the reference object on the receiver. 127 * 128 * @param reference 129 * reference object to be enqueued. 130 * @return true if the reference was enqueued. 131 */ enqueue(Reference<? extends T> reference)132 boolean enqueue(Reference<? extends T> reference) { 133 synchronized (lock) { 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 if (head == null) 173 return null; 174 175 return reallyPollLocked(); 176 } 177 } 178 179 /** 180 * Removes the next reference object in this queue, blocking until either 181 * one becomes available or the given timeout period expires. 182 * 183 * <p> This method does not offer real-time guarantees: It schedules the 184 * timeout as if by invoking the {@link Object#wait(long)} method. 185 * 186 * @param timeout If positive, block for up to <code>timeout</code> 187 * milliseconds while waiting for a reference to be 188 * added to this queue. If zero, block indefinitely. 189 * 190 * @return A reference object, if one was available within the specified 191 * timeout period, otherwise <code>null</code> 192 * 193 * @throws IllegalArgumentException 194 * If the value of the timeout argument is negative 195 * 196 * @throws InterruptedException 197 * If the timeout wait is interrupted 198 */ remove(long timeout)199 public Reference<? extends T> remove(long timeout) 200 throws IllegalArgumentException, InterruptedException 201 { 202 if (timeout < 0) { 203 throw new IllegalArgumentException("Negative timeout value"); 204 } 205 synchronized (lock) { 206 Reference<? extends T> r = reallyPollLocked(); 207 if (r != null) return r; 208 long start = (timeout == 0) ? 0 : System.nanoTime(); 209 for (;;) { 210 lock.wait(timeout); 211 r = reallyPollLocked(); 212 if (r != null) return r; 213 if (timeout != 0) { 214 long end = System.nanoTime(); 215 timeout -= (end - start) / 1000_000; 216 if (timeout <= 0) return null; 217 start = end; 218 } 219 } 220 } 221 } 222 223 /** 224 * Removes the next reference object in this queue, blocking until one 225 * becomes available. 226 * 227 * @return A reference object, blocking until one becomes available 228 * @throws InterruptedException If the wait is interrupted 229 */ remove()230 public Reference<? extends T> remove() throws InterruptedException { 231 return remove(0); 232 } 233 234 /** 235 * Enqueue the given list of currently pending (unenqueued) references. 236 * 237 * @hide 238 */ enqueuePending(Reference<?> list, AtomicInteger progressCounter)239 public static void enqueuePending(Reference<?> list, AtomicInteger progressCounter) { 240 Reference<?> start = list; 241 do { 242 ReferenceQueue queue = list.queue; 243 if (queue == null || Cleaner.isCleanerQueue(queue)) { 244 Reference<?> next = list.pendingNext; 245 // Always make pendingNext a self-loop to preserve the invariant that 246 // once enqueued, pendingNext is non-null -- without leaking 247 // the object pendingNext was previously pointing to. 248 list.pendingNext = list; 249 if (queue != null) { 250 // This is a Cleaner. Run directly without additional synchronization. 251 Cleaner cl = (sun.misc.Cleaner) list; 252 currentTarget = cl; 253 cl.clean(); // Idempotent. No need to check queueNext first. 254 list.queueNext = sQueueNextUnenqueued; 255 } 256 list = next; 257 } else { 258 currentTarget = queue; 259 // To improve performance, we try to avoid repeated 260 // synchronization on the same queue by batching enqueueing of 261 // consecutive references in the list that have the same 262 // queue. We limit this so that progressCounter gets incremented 263 // occasionally, 264 final int MAX_ITERS = 100; 265 int i = 0; 266 synchronized (queue.lock) { 267 do { 268 Reference<?> next = list.pendingNext; 269 list.pendingNext = list; 270 queue.enqueueLocked(list); 271 list = next; 272 } while (list != start && list.queue == queue && ++i <= MAX_ITERS); 273 queue.lock.notifyAll(); 274 } 275 } 276 progressCounter.incrementAndGet(); 277 } while (list != start); 278 currentTarget = null; 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