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 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 public class ReferenceQueue<T> { 39 40 // Reference.queueNext will be set to sQueueNextUnenqueued to indicate 41 // when a reference has been enqueued and removed from its queue. 42 private static final Reference sQueueNextUnenqueued = new PhantomReference(null, null); 43 44 // NOTE: This implementation of ReferenceQueue is FIFO (queue-like) whereas 45 // the OpenJdk implementation is LIFO (stack-like). 46 private Reference<? extends T> head = null; 47 private Reference<? extends T> tail = null; 48 49 private final Object lock = new Object(); 50 51 /** 52 * Constructs a new reference-object queue. 53 */ ReferenceQueue()54 public ReferenceQueue() { } 55 56 /** 57 * Enqueue the given reference onto this queue. 58 * The caller is responsible for ensuring the lock is held on this queue, 59 * and for calling notifyAll on this queue after the reference has been 60 * enqueued. Returns true if the reference was enqueued successfully, 61 * false if the reference had already been enqueued. 62 * @GuardedBy("lock") 63 */ enqueueLocked(Reference<? extends T> r)64 private boolean enqueueLocked(Reference<? extends T> r) { 65 // Verify the reference has not already been enqueued. 66 if (r.queueNext != null) { 67 return false; 68 } 69 70 if (r instanceof Cleaner) { 71 // If this reference is a Cleaner, then simply invoke the clean method instead 72 // of enqueueing it in the queue. Cleaners are associated with dummy queues that 73 // are never polled and objects are never enqueued on them. 74 Cleaner cl = (sun.misc.Cleaner) r; 75 cl.clean(); 76 77 // Update queueNext to indicate that the reference has been 78 // enqueued, but is now removed from the queue. 79 r.queueNext = sQueueNextUnenqueued; 80 return true; 81 } 82 83 if (tail == null) { 84 head = r; 85 } else { 86 tail.queueNext = r; 87 } 88 tail = r; 89 tail.queueNext = r; 90 return true; 91 } 92 93 /** 94 * Test if the given reference object has been enqueued but not yet 95 * removed from the queue, assuming this is the reference object's queue. 96 */ isEnqueued(Reference<? extends T> reference)97 boolean isEnqueued(Reference<? extends T> reference) { 98 synchronized (lock) { 99 return reference.queueNext != null && reference.queueNext != sQueueNextUnenqueued; 100 } 101 } 102 103 /** 104 * Enqueue the reference object on the receiver. 105 * 106 * @param reference 107 * reference object to be enqueued. 108 * @return true if the reference was enqueued. 109 */ enqueue(Reference<? extends T> reference)110 boolean enqueue(Reference<? extends T> reference) { 111 synchronized (lock) { 112 if (enqueueLocked(reference)) { 113 lock.notifyAll(); 114 return true; 115 } 116 return false; 117 } 118 } 119 120 // @GuardedBy("lock") reallyPollLocked()121 private Reference<? extends T> reallyPollLocked() { 122 if (head != null) { 123 Reference<? extends T> r = head; 124 if (head == tail) { 125 tail = null; 126 head = null; 127 } else { 128 head = head.queueNext; 129 } 130 131 // Update queueNext to indicate that the reference has been 132 // enqueued, but is now removed from the queue. 133 r.queueNext = sQueueNextUnenqueued; 134 return r; 135 } 136 137 return null; 138 } 139 140 /** 141 * Polls this queue to see if a reference object is available. If one is 142 * available without further delay then it is removed from the queue and 143 * returned. Otherwise this method immediately returns <tt>null</tt>. 144 * 145 * @return A reference object, if one was immediately available, 146 * otherwise <code>null</code> 147 */ poll()148 public Reference<? extends T> poll() { 149 synchronized (lock) { 150 if (head == null) 151 return null; 152 153 return reallyPollLocked(); 154 } 155 } 156 157 /** 158 * Removes the next reference object in this queue, blocking until either 159 * one becomes available or the given timeout period expires. 160 * 161 * <p> This method does not offer real-time guarantees: It schedules the 162 * timeout as if by invoking the {@link Object#wait(long)} method. 163 * 164 * @param timeout If positive, block for up to <code>timeout</code> 165 * milliseconds while waiting for a reference to be 166 * added to this queue. If zero, block indefinitely. 167 * 168 * @return A reference object, if one was available within the specified 169 * timeout period, otherwise <code>null</code> 170 * 171 * @throws IllegalArgumentException 172 * If the value of the timeout argument is negative 173 * 174 * @throws InterruptedException 175 * If the timeout wait is interrupted 176 */ remove(long timeout)177 public Reference<? extends T> remove(long timeout) 178 throws IllegalArgumentException, InterruptedException 179 { 180 if (timeout < 0) { 181 throw new IllegalArgumentException("Negative timeout value"); 182 } 183 synchronized (lock) { 184 Reference<? extends T> r = reallyPollLocked(); 185 if (r != null) return r; 186 long start = (timeout == 0) ? 0 : System.nanoTime(); 187 for (;;) { 188 lock.wait(timeout); 189 r = reallyPollLocked(); 190 if (r != null) return r; 191 if (timeout != 0) { 192 long end = System.nanoTime(); 193 timeout -= (end - start) / 1000_000; 194 if (timeout <= 0) return null; 195 start = end; 196 } 197 } 198 } 199 } 200 201 /** 202 * Removes the next reference object in this queue, blocking until one 203 * becomes available. 204 * 205 * @return A reference object, blocking until one becomes available 206 * @throws InterruptedException If the wait is interrupted 207 */ remove()208 public Reference<? extends T> remove() throws InterruptedException { 209 return remove(0); 210 } 211 212 /** 213 * Enqueue the given list of currently pending (unenqueued) references. 214 * 215 * @hide 216 */ enqueuePending(Reference<?> list)217 public static void enqueuePending(Reference<?> list) { 218 Reference<?> start = list; 219 do { 220 ReferenceQueue queue = list.queue; 221 if (queue == null) { 222 Reference<?> next = list.pendingNext; 223 224 // Make pendingNext a self-loop to preserve the invariant that 225 // once enqueued, pendingNext is non-null -- without leaking 226 // the object pendingNext was previously pointing to. 227 list.pendingNext = list; 228 list = next; 229 } else { 230 // To improve performance, we try to avoid repeated 231 // synchronization on the same queue by batching enqueue of 232 // consecutive references in the list that have the same 233 // queue. 234 synchronized (queue.lock) { 235 do { 236 Reference<?> next = list.pendingNext; 237 238 // Make pendingNext a self-loop to preserve the 239 // invariant that once enqueued, pendingNext is 240 // non-null -- without leaking the object pendingNext 241 // was previously pointing to. 242 list.pendingNext = list; 243 queue.enqueueLocked(list); 244 list = next; 245 } while (list != start && list.queue == queue); 246 queue.lock.notifyAll(); 247 } 248 } 249 } while (list != start); 250 } 251 252 /** 253 * List of references that the GC says need to be enqueued. 254 * Protected by ReferenceQueue.class lock. 255 * @hide 256 */ 257 public static Reference<?> unenqueued = null; 258 add(Reference<?> list)259 static void add(Reference<?> list) { 260 synchronized (ReferenceQueue.class) { 261 if (unenqueued == null) { 262 unenqueued = list; 263 } else { 264 // Find the last element in unenqueued. 265 Reference<?> last = unenqueued; 266 while (last.pendingNext != unenqueued) { 267 last = last.pendingNext; 268 } 269 // Add our list to the end. Update the pendingNext to point back to enqueued. 270 last.pendingNext = list; 271 last = list; 272 while (last.pendingNext != list) { 273 last = last.pendingNext; 274 } 275 last.pendingNext = unenqueued; 276 } 277 ReferenceQueue.class.notifyAll(); 278 } 279 } 280 } 281