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