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 private static ReferenceQueue currentQueue = null; // Current target of enqueuePending. 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 if (r instanceof Cleaner) { 76 // If this reference is a Cleaner, then simply invoke the clean method instead 77 // of enqueueing it in the queue. Cleaners are associated with dummy queues that 78 // are never polled and objects are never enqueued on them. 79 Cleaner cl = (sun.misc.Cleaner) r; 80 cl.clean(); 81 82 // Update queueNext to indicate that the reference has been 83 // enqueued, but is now removed from the queue. 84 r.queueNext = sQueueNextUnenqueued; 85 return true; 86 } 87 88 if (tail == null) { 89 head = r; 90 } else { 91 tail.queueNext = r; 92 } 93 tail = r; 94 tail.queueNext = r; 95 return true; 96 } 97 98 /** 99 * The queue currently being targeted by enqueuePending. Used only to get slightly 100 * informative output for timeouts. May be read via a data race, but only for crash 101 * debugging output. 102 * @hide 103 */ getCurrentQueue()104 public static ReferenceQueue getCurrentQueue() { 105 return currentQueue; 106 } 107 108 /** 109 * Test if the given reference object has been enqueued but not yet 110 * removed from the queue, assuming this is the reference object's queue. 111 */ isEnqueued(Reference<? extends T> reference)112 boolean isEnqueued(Reference<? extends T> reference) { 113 synchronized (lock) { 114 return reference.queueNext != null && reference.queueNext != sQueueNextUnenqueued; 115 } 116 } 117 118 /** 119 * Enqueue the reference object on the receiver. 120 * 121 * @param reference 122 * reference object to be enqueued. 123 * @return true if the reference was enqueued. 124 */ enqueue(Reference<? extends T> reference)125 boolean enqueue(Reference<? extends T> reference) { 126 synchronized (lock) { 127 if (enqueueLocked(reference)) { 128 lock.notifyAll(); 129 return true; 130 } 131 return false; 132 } 133 } 134 135 // @GuardedBy("lock") reallyPollLocked()136 private Reference<? extends T> reallyPollLocked() { 137 if (head != null) { 138 Reference<? extends T> r = head; 139 if (head == tail) { 140 tail = null; 141 head = null; 142 } else { 143 head = head.queueNext; 144 } 145 146 // Update queueNext to indicate that the reference has been 147 // enqueued, but is now removed from the queue. 148 r.queueNext = sQueueNextUnenqueued; 149 return r; 150 } 151 152 return null; 153 } 154 155 /** 156 * Polls this queue to see if a reference object is available. If one is 157 * available without further delay then it is removed from the queue and 158 * returned. Otherwise this method immediately returns <tt>null</tt>. 159 * 160 * @return A reference object, if one was immediately available, 161 * otherwise <code>null</code> 162 */ poll()163 public Reference<? extends T> poll() { 164 synchronized (lock) { 165 if (head == null) 166 return null; 167 168 return reallyPollLocked(); 169 } 170 } 171 172 /** 173 * Removes the next reference object in this queue, blocking until either 174 * one becomes available or the given timeout period expires. 175 * 176 * <p> This method does not offer real-time guarantees: It schedules the 177 * timeout as if by invoking the {@link Object#wait(long)} method. 178 * 179 * @param timeout If positive, block for up to <code>timeout</code> 180 * milliseconds while waiting for a reference to be 181 * added to this queue. If zero, block indefinitely. 182 * 183 * @return A reference object, if one was available within the specified 184 * timeout period, otherwise <code>null</code> 185 * 186 * @throws IllegalArgumentException 187 * If the value of the timeout argument is negative 188 * 189 * @throws InterruptedException 190 * If the timeout wait is interrupted 191 */ remove(long timeout)192 public Reference<? extends T> remove(long timeout) 193 throws IllegalArgumentException, InterruptedException 194 { 195 if (timeout < 0) { 196 throw new IllegalArgumentException("Negative timeout value"); 197 } 198 synchronized (lock) { 199 Reference<? extends T> r = reallyPollLocked(); 200 if (r != null) return r; 201 long start = (timeout == 0) ? 0 : System.nanoTime(); 202 for (;;) { 203 lock.wait(timeout); 204 r = reallyPollLocked(); 205 if (r != null) return r; 206 if (timeout != 0) { 207 long end = System.nanoTime(); 208 timeout -= (end - start) / 1000_000; 209 if (timeout <= 0) return null; 210 start = end; 211 } 212 } 213 } 214 } 215 216 /** 217 * Removes the next reference object in this queue, blocking until one 218 * becomes available. 219 * 220 * @return A reference object, blocking until one becomes available 221 * @throws InterruptedException If the wait is interrupted 222 */ remove()223 public Reference<? extends T> remove() throws InterruptedException { 224 return remove(0); 225 } 226 227 /** 228 * Enqueue the given list of currently pending (unenqueued) references. 229 * 230 * @hide 231 */ enqueuePending(Reference<?> list, AtomicInteger progressCounter)232 public static void enqueuePending(Reference<?> list, AtomicInteger progressCounter) { 233 Reference<?> start = list; 234 do { 235 ReferenceQueue queue = list.queue; 236 currentQueue = queue; 237 if (queue == null) { 238 Reference<?> next = list.pendingNext; 239 240 // Make pendingNext a self-loop to preserve the invariant that 241 // once enqueued, pendingNext is non-null -- without leaking 242 // the object pendingNext was previously pointing to. 243 list.pendingNext = list; 244 list = next; 245 } else { 246 // To improve performance, we try to avoid repeated 247 // synchronization on the same queue by batching enqueueing of 248 // consecutive references in the list that have the same 249 // queue. We limit this so that progressCounter gets incremented 250 // occasionally, 251 final int MAX_ITERS = 100; 252 int i = 0; 253 synchronized (queue.lock) { 254 do { 255 Reference<?> next = list.pendingNext; 256 257 // Make pendingNext a self-loop to preserve the 258 // invariant that once enqueued, pendingNext is 259 // non-null -- without leaking the object pendingNext 260 // was previously pointing to. 261 list.pendingNext = list; 262 queue.enqueueLocked(list); 263 list = next; 264 } while (list != start && list.queue == queue && ++i <= MAX_ITERS); 265 queue.lock.notifyAll(); 266 } 267 } 268 progressCounter.incrementAndGet(); 269 } while (list != start); 270 } 271 272 /** 273 * List of references that the GC says need to be enqueued. 274 * Protected by ReferenceQueue.class lock. 275 * @hide 276 */ 277 public static Reference<?> unenqueued = null; 278 add(Reference<?> list)279 static void add(Reference<?> list) { 280 synchronized (ReferenceQueue.class) { 281 if (unenqueued == null) { 282 unenqueued = list; 283 } else { 284 // Find the last element in unenqueued. 285 Reference<?> last = unenqueued; 286 while (last.pendingNext != unenqueued) { 287 last = last.pendingNext; 288 } 289 // Add our list to the end. Update the pendingNext to point back to enqueued. 290 last.pendingNext = list; 291 last = list; 292 while (last.pendingNext != list) { 293 last = last.pendingNext; 294 } 295 last.pendingNext = unenqueued; 296 } 297 ReferenceQueue.class.notifyAll(); 298 } 299 } 300 } 301 // END Android-changed: Reimplemented to accomodate a different GC and compiler. 302