1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation. Oracle designates this
7 * particular file as subject to the "Classpath" exception as provided
8 * by Oracle in the LICENSE file that accompanied this code.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 */
24
25 /*
26 * This file is available under and governed by the GNU General Public
27 * License version 2 only, as published by the Free Software Foundation.
28 * However, the following notice accompanied the original version of this
29 * file:
30 *
31 * Written by Doug Lea with assistance from members of JCP JSR-166
32 * Expert Group and released to the public domain, as explained at
33 * http://creativecommons.org/publicdomain/zero/1.0/
34 */
35
36 package java.util.concurrent.locks;
37
38 import java.lang.invoke.MethodHandles;
39 import java.lang.invoke.VarHandle;
40 import java.util.ArrayList;
41 import java.util.Collection;
42 import java.util.Date;
43 import java.util.concurrent.TimeUnit;
44
45 /**
46 * Provides a framework for implementing blocking locks and related
47 * synchronizers (semaphores, events, etc) that rely on
48 * first-in-first-out (FIFO) wait queues. This class is designed to
49 * be a useful basis for most kinds of synchronizers that rely on a
50 * single atomic {@code int} value to represent state. Subclasses
51 * must define the protected methods that change this state, and which
52 * define what that state means in terms of this object being acquired
53 * or released. Given these, the other methods in this class carry
54 * out all queuing and blocking mechanics. Subclasses can maintain
55 * other state fields, but only the atomically updated {@code int}
56 * value manipulated using methods {@link #getState}, {@link
57 * #setState} and {@link #compareAndSetState} is tracked with respect
58 * to synchronization.
59 *
60 * <p>Subclasses should be defined as non-public internal helper
61 * classes that are used to implement the synchronization properties
62 * of their enclosing class. Class
63 * {@code AbstractQueuedSynchronizer} does not implement any
64 * synchronization interface. Instead it defines methods such as
65 * {@link #acquireInterruptibly} that can be invoked as
66 * appropriate by concrete locks and related synchronizers to
67 * implement their public methods.
68 *
69 * <p>This class supports either or both a default <em>exclusive</em>
70 * mode and a <em>shared</em> mode. When acquired in exclusive mode,
71 * attempted acquires by other threads cannot succeed. Shared mode
72 * acquires by multiple threads may (but need not) succeed. This class
73 * does not "understand" these differences except in the
74 * mechanical sense that when a shared mode acquire succeeds, the next
75 * waiting thread (if one exists) must also determine whether it can
76 * acquire as well. Threads waiting in the different modes share the
77 * same FIFO queue. Usually, implementation subclasses support only
78 * one of these modes, but both can come into play for example in a
79 * {@link ReadWriteLock}. Subclasses that support only exclusive or
80 * only shared modes need not define the methods supporting the unused mode.
81 *
82 * <p>This class defines a nested {@link ConditionObject} class that
83 * can be used as a {@link Condition} implementation by subclasses
84 * supporting exclusive mode for which method {@link
85 * #isHeldExclusively} reports whether synchronization is exclusively
86 * held with respect to the current thread, method {@link #release}
87 * invoked with the current {@link #getState} value fully releases
88 * this object, and {@link #acquire}, given this saved state value,
89 * eventually restores this object to its previous acquired state. No
90 * {@code AbstractQueuedSynchronizer} method otherwise creates such a
91 * condition, so if this constraint cannot be met, do not use it. The
92 * behavior of {@link ConditionObject} depends of course on the
93 * semantics of its synchronizer implementation.
94 *
95 * <p>This class provides inspection, instrumentation, and monitoring
96 * methods for the internal queue, as well as similar methods for
97 * condition objects. These can be exported as desired into classes
98 * using an {@code AbstractQueuedSynchronizer} for their
99 * synchronization mechanics.
100 *
101 * <p>Serialization of this class stores only the underlying atomic
102 * integer maintaining state, so deserialized objects have empty
103 * thread queues. Typical subclasses requiring serializability will
104 * define a {@code readObject} method that restores this to a known
105 * initial state upon deserialization.
106 *
107 * <h3>Usage</h3>
108 *
109 * <p>To use this class as the basis of a synchronizer, redefine the
110 * following methods, as applicable, by inspecting and/or modifying
111 * the synchronization state using {@link #getState}, {@link
112 * #setState} and/or {@link #compareAndSetState}:
113 *
114 * <ul>
115 * <li>{@link #tryAcquire}
116 * <li>{@link #tryRelease}
117 * <li>{@link #tryAcquireShared}
118 * <li>{@link #tryReleaseShared}
119 * <li>{@link #isHeldExclusively}
120 * </ul>
121 *
122 * Each of these methods by default throws {@link
123 * UnsupportedOperationException}. Implementations of these methods
124 * must be internally thread-safe, and should in general be short and
125 * not block. Defining these methods is the <em>only</em> supported
126 * means of using this class. All other methods are declared
127 * {@code final} because they cannot be independently varied.
128 *
129 * <p>You may also find the inherited methods from {@link
130 * AbstractOwnableSynchronizer} useful to keep track of the thread
131 * owning an exclusive synchronizer. You are encouraged to use them
132 * -- this enables monitoring and diagnostic tools to assist users in
133 * determining which threads hold locks.
134 *
135 * <p>Even though this class is based on an internal FIFO queue, it
136 * does not automatically enforce FIFO acquisition policies. The core
137 * of exclusive synchronization takes the form:
138 *
139 * <pre>
140 * Acquire:
141 * while (!tryAcquire(arg)) {
142 * <em>enqueue thread if it is not already queued</em>;
143 * <em>possibly block current thread</em>;
144 * }
145 *
146 * Release:
147 * if (tryRelease(arg))
148 * <em>unblock the first queued thread</em>;
149 * </pre>
150 *
151 * (Shared mode is similar but may involve cascading signals.)
152 *
153 * <p id="barging">Because checks in acquire are invoked before
154 * enqueuing, a newly acquiring thread may <em>barge</em> ahead of
155 * others that are blocked and queued. However, you can, if desired,
156 * define {@code tryAcquire} and/or {@code tryAcquireShared} to
157 * disable barging by internally invoking one or more of the inspection
158 * methods, thereby providing a <em>fair</em> FIFO acquisition order.
159 * In particular, most fair synchronizers can define {@code tryAcquire}
160 * to return {@code false} if {@link #hasQueuedPredecessors} (a method
161 * specifically designed to be used by fair synchronizers) returns
162 * {@code true}. Other variations are possible.
163 *
164 * <p>Throughput and scalability are generally highest for the
165 * default barging (also known as <em>greedy</em>,
166 * <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy.
167 * While this is not guaranteed to be fair or starvation-free, earlier
168 * queued threads are allowed to recontend before later queued
169 * threads, and each recontention has an unbiased chance to succeed
170 * against incoming threads. Also, while acquires do not
171 * "spin" in the usual sense, they may perform multiple
172 * invocations of {@code tryAcquire} interspersed with other
173 * computations before blocking. This gives most of the benefits of
174 * spins when exclusive synchronization is only briefly held, without
175 * most of the liabilities when it isn't. If so desired, you can
176 * augment this by preceding calls to acquire methods with
177 * "fast-path" checks, possibly prechecking {@link #hasContended}
178 * and/or {@link #hasQueuedThreads} to only do so if the synchronizer
179 * is likely not to be contended.
180 *
181 * <p>This class provides an efficient and scalable basis for
182 * synchronization in part by specializing its range of use to
183 * synchronizers that can rely on {@code int} state, acquire, and
184 * release parameters, and an internal FIFO wait queue. When this does
185 * not suffice, you can build synchronizers from a lower level using
186 * {@link java.util.concurrent.atomic atomic} classes, your own custom
187 * {@link java.util.Queue} classes, and {@link LockSupport} blocking
188 * support.
189 *
190 * <h3>Usage Examples</h3>
191 *
192 * <p>Here is a non-reentrant mutual exclusion lock class that uses
193 * the value zero to represent the unlocked state, and one to
194 * represent the locked state. While a non-reentrant lock
195 * does not strictly require recording of the current owner
196 * thread, this class does so anyway to make usage easier to monitor.
197 * It also supports conditions and exposes some instrumentation methods:
198 *
199 * <pre> {@code
200 * class Mutex implements Lock, java.io.Serializable {
201 *
202 * // Our internal helper class
203 * private static class Sync extends AbstractQueuedSynchronizer {
204 * // Acquires the lock if state is zero
205 * public boolean tryAcquire(int acquires) {
206 * assert acquires == 1; // Otherwise unused
207 * if (compareAndSetState(0, 1)) {
208 * setExclusiveOwnerThread(Thread.currentThread());
209 * return true;
210 * }
211 * return false;
212 * }
213 *
214 * // Releases the lock by setting state to zero
215 * protected boolean tryRelease(int releases) {
216 * assert releases == 1; // Otherwise unused
217 * if (!isHeldExclusively())
218 * throw new IllegalMonitorStateException();
219 * setExclusiveOwnerThread(null);
220 * setState(0);
221 * return true;
222 * }
223 *
224 * // Reports whether in locked state
225 * public boolean isLocked() {
226 * return getState() != 0;
227 * }
228 *
229 * public boolean isHeldExclusively() {
230 * // a data race, but safe due to out-of-thin-air guarantees
231 * return getExclusiveOwnerThread() == Thread.currentThread();
232 * }
233 *
234 * // Provides a Condition
235 * public Condition newCondition() {
236 * return new ConditionObject();
237 * }
238 *
239 * // Deserializes properly
240 * private void readObject(ObjectInputStream s)
241 * throws IOException, ClassNotFoundException {
242 * s.defaultReadObject();
243 * setState(0); // reset to unlocked state
244 * }
245 * }
246 *
247 * // The sync object does all the hard work. We just forward to it.
248 * private final Sync sync = new Sync();
249 *
250 * public void lock() { sync.acquire(1); }
251 * public boolean tryLock() { return sync.tryAcquire(1); }
252 * public void unlock() { sync.release(1); }
253 * public Condition newCondition() { return sync.newCondition(); }
254 * public boolean isLocked() { return sync.isLocked(); }
255 * public boolean isHeldByCurrentThread() {
256 * return sync.isHeldExclusively();
257 * }
258 * public boolean hasQueuedThreads() {
259 * return sync.hasQueuedThreads();
260 * }
261 * public void lockInterruptibly() throws InterruptedException {
262 * sync.acquireInterruptibly(1);
263 * }
264 * public boolean tryLock(long timeout, TimeUnit unit)
265 * throws InterruptedException {
266 * return sync.tryAcquireNanos(1, unit.toNanos(timeout));
267 * }
268 * }}</pre>
269 *
270 * <p>Here is a latch class that is like a
271 * {@link java.util.concurrent.CountDownLatch CountDownLatch}
272 * except that it only requires a single {@code signal} to
273 * fire. Because a latch is non-exclusive, it uses the {@code shared}
274 * acquire and release methods.
275 *
276 * <pre> {@code
277 * class BooleanLatch {
278 *
279 * private static class Sync extends AbstractQueuedSynchronizer {
280 * boolean isSignalled() { return getState() != 0; }
281 *
282 * protected int tryAcquireShared(int ignore) {
283 * return isSignalled() ? 1 : -1;
284 * }
285 *
286 * protected boolean tryReleaseShared(int ignore) {
287 * setState(1);
288 * return true;
289 * }
290 * }
291 *
292 * private final Sync sync = new Sync();
293 * public boolean isSignalled() { return sync.isSignalled(); }
294 * public void signal() { sync.releaseShared(1); }
295 * public void await() throws InterruptedException {
296 * sync.acquireSharedInterruptibly(1);
297 * }
298 * }}</pre>
299 *
300 * @since 1.5
301 * @author Doug Lea
302 */
303 public abstract class AbstractQueuedSynchronizer
304 extends AbstractOwnableSynchronizer
305 implements java.io.Serializable {
306
307 private static final long serialVersionUID = 7373984972572414691L;
308
309 /**
310 * Creates a new {@code AbstractQueuedSynchronizer} instance
311 * with initial synchronization state of zero.
312 */
313 protected AbstractQueuedSynchronizer() { }
314
315 /**
316 * Wait queue node class.
317 *
318 * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
319 * Hagersten) lock queue. CLH locks are normally used for
320 * spinlocks. We instead use them for blocking synchronizers, but
321 * use the same basic tactic of holding some of the control
322 * information about a thread in the predecessor of its node. A
323 * "status" field in each node keeps track of whether a thread
324 * should block. A node is signalled when its predecessor
325 * releases. Each node of the queue otherwise serves as a
326 * specific-notification-style monitor holding a single waiting
327 * thread. The status field does NOT control whether threads are
328 * granted locks etc though. A thread may try to acquire if it is
329 * first in the queue. But being first does not guarantee success;
330 * it only gives the right to contend. So the currently released
331 * contender thread may need to rewait.
332 *
333 * <p>To enqueue into a CLH lock, you atomically splice it in as new
334 * tail. To dequeue, you just set the head field.
335 * <pre>
336 * +------+ prev +-----+ +-----+
337 * head | | <---- | | <---- | | tail
338 * +------+ +-----+ +-----+
339 * </pre>
340 *
341 * <p>Insertion into a CLH queue requires only a single atomic
342 * operation on "tail", so there is a simple atomic point of
343 * demarcation from unqueued to queued. Similarly, dequeuing
344 * involves only updating the "head". However, it takes a bit
345 * more work for nodes to determine who their successors are,
346 * in part to deal with possible cancellation due to timeouts
347 * and interrupts.
348 *
349 * <p>The "prev" links (not used in original CLH locks), are mainly
350 * needed to handle cancellation. If a node is cancelled, its
351 * successor is (normally) relinked to a non-cancelled
352 * predecessor. For explanation of similar mechanics in the case
353 * of spin locks, see the papers by Scott and Scherer at
354 * http://www.cs.rochester.edu/u/scott/synchronization/
355 *
356 * <p>We also use "next" links to implement blocking mechanics.
357 * The thread id for each node is kept in its own node, so a
358 * predecessor signals the next node to wake up by traversing
359 * next link to determine which thread it is. Determination of
360 * successor must avoid races with newly queued nodes to set
361 * the "next" fields of their predecessors. This is solved
362 * when necessary by checking backwards from the atomically
363 * updated "tail" when a node's successor appears to be null.
364 * (Or, said differently, the next-links are an optimization
365 * so that we don't usually need a backward scan.)
366 *
367 * <p>Cancellation introduces some conservatism to the basic
368 * algorithms. Since we must poll for cancellation of other
369 * nodes, we can miss noticing whether a cancelled node is
370 * ahead or behind us. This is dealt with by always unparking
371 * successors upon cancellation, allowing them to stabilize on
372 * a new predecessor, unless we can identify an uncancelled
373 * predecessor who will carry this responsibility.
374 *
375 * <p>CLH queues need a dummy header node to get started. But
376 * we don't create them on construction, because it would be wasted
377 * effort if there is never contention. Instead, the node
378 * is constructed and head and tail pointers are set upon first
379 * contention.
380 *
381 * <p>Threads waiting on Conditions use the same nodes, but
382 * use an additional link. Conditions only need to link nodes
383 * in simple (non-concurrent) linked queues because they are
384 * only accessed when exclusively held. Upon await, a node is
385 * inserted into a condition queue. Upon signal, the node is
386 * transferred to the main queue. A special value of status
387 * field is used to mark which queue a node is on.
388 *
389 * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
390 * Scherer and Michael Scott, along with members of JSR-166
391 * expert group, for helpful ideas, discussions, and critiques
392 * on the design of this class.
393 */
394 static final class Node {
395 /** Marker to indicate a node is waiting in shared mode */
396 static final Node SHARED = new Node();
397 /** Marker to indicate a node is waiting in exclusive mode */
398 static final Node EXCLUSIVE = null;
399
400 /** waitStatus value to indicate thread has cancelled. */
401 static final int CANCELLED = 1;
402 /** waitStatus value to indicate successor's thread needs unparking. */
403 static final int SIGNAL = -1;
404 /** waitStatus value to indicate thread is waiting on condition. */
405 static final int CONDITION = -2;
406 /**
407 * waitStatus value to indicate the next acquireShared should
408 * unconditionally propagate.
409 */
410 static final int PROPAGATE = -3;
411
412 /**
413 * Status field, taking on only the values:
414 * SIGNAL: The successor of this node is (or will soon be)
415 * blocked (via park), so the current node must
416 * unpark its successor when it releases or
417 * cancels. To avoid races, acquire methods must
418 * first indicate they need a signal,
419 * then retry the atomic acquire, and then,
420 * on failure, block.
421 * CANCELLED: This node is cancelled due to timeout or interrupt.
422 * Nodes never leave this state. In particular,
423 * a thread with cancelled node never again blocks.
424 * CONDITION: This node is currently on a condition queue.
425 * It will not be used as a sync queue node
426 * until transferred, at which time the status
427 * will be set to 0. (Use of this value here has
428 * nothing to do with the other uses of the
429 * field, but simplifies mechanics.)
430 * PROPAGATE: A releaseShared should be propagated to other
431 * nodes. This is set (for head node only) in
432 * doReleaseShared to ensure propagation
433 * continues, even if other operations have
434 * since intervened.
435 * 0: None of the above
436 *
437 * The values are arranged numerically to simplify use.
438 * Non-negative values mean that a node doesn't need to
439 * signal. So, most code doesn't need to check for particular
440 * values, just for sign.
441 *
442 * The field is initialized to 0 for normal sync nodes, and
443 * CONDITION for condition nodes. It is modified using CAS
444 * (or when possible, unconditional volatile writes).
445 */
446 volatile int waitStatus;
447
448 /**
449 * Link to predecessor node that current node/thread relies on
450 * for checking waitStatus. Assigned during enqueuing, and nulled
451 * out (for sake of GC) only upon dequeuing. Also, upon
452 * cancellation of a predecessor, we short-circuit while
453 * finding a non-cancelled one, which will always exist
454 * because the head node is never cancelled: A node becomes
455 * head only as a result of successful acquire. A
456 * cancelled thread never succeeds in acquiring, and a thread only
457 * cancels itself, not any other node.
458 */
459 volatile Node prev;
460
461 /**
462 * Link to the successor node that the current node/thread
463 * unparks upon release. Assigned during enqueuing, adjusted
464 * when bypassing cancelled predecessors, and nulled out (for
465 * sake of GC) when dequeued. The enq operation does not
466 * assign next field of a predecessor until after attachment,
467 * so seeing a null next field does not necessarily mean that
468 * node is at end of queue. However, if a next field appears
469 * to be null, we can scan prev's from the tail to
470 * double-check. The next field of cancelled nodes is set to
471 * point to the node itself instead of null, to make life
472 * easier for isOnSyncQueue.
473 */
474 volatile Node next;
475
476 /**
477 * The thread that enqueued this node. Initialized on
478 * construction and nulled out after use.
479 */
480 volatile Thread thread;
481
482 /**
483 * Link to next node waiting on condition, or the special
484 * value SHARED. Because condition queues are accessed only
485 * when holding in exclusive mode, we just need a simple
486 * linked queue to hold nodes while they are waiting on
487 * conditions. They are then transferred to the queue to
488 * re-acquire. And because conditions can only be exclusive,
489 * we save a field by using special value to indicate shared
490 * mode.
491 */
492 Node nextWaiter;
493
494 /**
495 * Returns true if node is waiting in shared mode.
496 */
497 final boolean isShared() {
498 return nextWaiter == SHARED;
499 }
500
501 /**
502 * Returns previous node, or throws NullPointerException if null.
503 * Use when predecessor cannot be null. The null check could
504 * be elided, but is present to help the VM.
505 *
506 * @return the predecessor of this node
507 */
508 final Node predecessor() {
509 Node p = prev;
510 if (p == null)
511 throw new NullPointerException();
512 else
513 return p;
514 }
515
516 /** Establishes initial head or SHARED marker. */
517 Node() {}
518
519 /** Constructor used by addWaiter. */
520 Node(Node nextWaiter) {
521 this.nextWaiter = nextWaiter;
522 THREAD.set(this, Thread.currentThread());
523 }
524
525 /** Constructor used by addConditionWaiter. */
526 Node(int waitStatus) {
527 WAITSTATUS.set(this, waitStatus);
528 THREAD.set(this, Thread.currentThread());
529 }
530
531 /** CASes waitStatus field. */
532 final boolean compareAndSetWaitStatus(int expect, int update) {
533 return WAITSTATUS.compareAndSet(this, expect, update);
534 }
535
536 /** CASes next field. */
537 final boolean compareAndSetNext(Node expect, Node update) {
538 return NEXT.compareAndSet(this, expect, update);
539 }
540
541 final void setPrevRelaxed(Node p) {
542 PREV.set(this, p);
543 }
544
545 // VarHandle mechanics
546 private static final VarHandle NEXT;
547 private static final VarHandle PREV;
548 private static final VarHandle THREAD;
549 private static final VarHandle WAITSTATUS;
550 static {
551 try {
552 MethodHandles.Lookup l = MethodHandles.lookup();
553 NEXT = l.findVarHandle(Node.class, "next", Node.class);
554 PREV = l.findVarHandle(Node.class, "prev", Node.class);
555 THREAD = l.findVarHandle(Node.class, "thread", Thread.class);
556 WAITSTATUS = l.findVarHandle(Node.class, "waitStatus", int.class);
557 } catch (ReflectiveOperationException e) {
558 throw new ExceptionInInitializerError(e);
559 }
560 }
561 }
562
563 /**
564 * Head of the wait queue, lazily initialized. Except for
565 * initialization, it is modified only via method setHead. Note:
566 * If head exists, its waitStatus is guaranteed not to be
567 * CANCELLED.
568 */
569 private transient volatile Node head;
570
571 /**
572 * Tail of the wait queue, lazily initialized. Modified only via
573 * method enq to add new wait node.
574 */
575 private transient volatile Node tail;
576
577 /**
578 * The synchronization state.
579 */
580 private volatile int state;
581
582 /**
583 * Returns the current value of synchronization state.
584 * This operation has memory semantics of a {@code volatile} read.
585 * @return current state value
586 */
587 protected final int getState() {
588 return state;
589 }
590
591 /**
592 * Sets the value of synchronization state.
593 * This operation has memory semantics of a {@code volatile} write.
594 * @param newState the new state value
595 */
596 protected final void setState(int newState) {
597 state = newState;
598 }
599
600 /**
601 * Atomically sets synchronization state to the given updated
602 * value if the current state value equals the expected value.
603 * This operation has memory semantics of a {@code volatile} read
604 * and write.
605 *
606 * @param expect the expected value
607 * @param update the new value
608 * @return {@code true} if successful. False return indicates that the actual
609 * value was not equal to the expected value.
610 */
611 protected final boolean compareAndSetState(int expect, int update) {
612 return STATE.compareAndSet(this, expect, update);
613 }
614
615 // Queuing utilities
616
617 /**
618 * The number of nanoseconds for which it is faster to spin
619 * rather than to use timed park. A rough estimate suffices
620 * to improve responsiveness with very short timeouts.
621 */
622 static final long SPIN_FOR_TIMEOUT_THRESHOLD = 1000L;
623
624 /**
625 * Inserts node into queue, initializing if necessary. See picture above.
626 * @param node the node to insert
627 * @return node's predecessor
628 */
629 private Node enq(Node node) {
630 for (;;) {
631 Node oldTail = tail;
632 if (oldTail != null) {
633 node.setPrevRelaxed(oldTail);
634 if (compareAndSetTail(oldTail, node)) {
635 oldTail.next = node;
636 return oldTail;
637 }
638 } else {
639 initializeSyncQueue();
640 }
641 }
642 }
643
644 /**
645 * Creates and enqueues node for current thread and given mode.
646 *
647 * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
648 * @return the new node
649 */
650 private Node addWaiter(Node mode) {
651 Node node = new Node(mode);
652
653 for (;;) {
654 Node oldTail = tail;
655 if (oldTail != null) {
656 node.setPrevRelaxed(oldTail);
657 if (compareAndSetTail(oldTail, node)) {
658 oldTail.next = node;
659 return node;
660 }
661 } else {
662 initializeSyncQueue();
663 }
664 }
665 }
666
667 /**
668 * Sets head of queue to be node, thus dequeuing. Called only by
669 * acquire methods. Also nulls out unused fields for sake of GC
670 * and to suppress unnecessary signals and traversals.
671 *
672 * @param node the node
673 */
674 private void setHead(Node node) {
675 head = node;
676 node.thread = null;
677 node.prev = null;
678 }
679
680 /**
681 * Wakes up node's successor, if one exists.
682 *
683 * @param node the node
684 */
685 private void unparkSuccessor(Node node) {
686 /*
687 * If status is negative (i.e., possibly needing signal) try
688 * to clear in anticipation of signalling. It is OK if this
689 * fails or if status is changed by waiting thread.
690 */
691 int ws = node.waitStatus;
692 if (ws < 0)
693 node.compareAndSetWaitStatus(ws, 0);
694
695 /*
696 * Thread to unpark is held in successor, which is normally
697 * just the next node. But if cancelled or apparently null,
698 * traverse backwards from tail to find the actual
699 * non-cancelled successor.
700 */
701 Node s = node.next;
702 if (s == null || s.waitStatus > 0) {
703 s = null;
704 for (Node p = tail; p != node && p != null; p = p.prev)
705 if (p.waitStatus <= 0)
706 s = p;
707 }
708 if (s != null)
709 LockSupport.unpark(s.thread);
710 }
711
712 /**
713 * Release action for shared mode -- signals successor and ensures
714 * propagation. (Note: For exclusive mode, release just amounts
715 * to calling unparkSuccessor of head if it needs signal.)
716 */
717 private void doReleaseShared() {
718 /*
719 * Ensure that a release propagates, even if there are other
720 * in-progress acquires/releases. This proceeds in the usual
721 * way of trying to unparkSuccessor of head if it needs
722 * signal. But if it does not, status is set to PROPAGATE to
723 * ensure that upon release, propagation continues.
724 * Additionally, we must loop in case a new node is added
725 * while we are doing this. Also, unlike other uses of
726 * unparkSuccessor, we need to know if CAS to reset status
727 * fails, if so rechecking.
728 */
729 for (;;) {
730 Node h = head;
731 if (h != null && h != tail) {
732 int ws = h.waitStatus;
733 if (ws == Node.SIGNAL) {
734 if (!h.compareAndSetWaitStatus(Node.SIGNAL, 0))
735 continue; // loop to recheck cases
736 unparkSuccessor(h);
737 }
738 else if (ws == 0 &&
739 !h.compareAndSetWaitStatus(0, Node.PROPAGATE))
740 continue; // loop on failed CAS
741 }
742 if (h == head) // loop if head changed
743 break;
744 }
745 }
746
747 /**
748 * Sets head of queue, and checks if successor may be waiting
749 * in shared mode, if so propagating if either propagate > 0 or
750 * PROPAGATE status was set.
751 *
752 * @param node the node
753 * @param propagate the return value from a tryAcquireShared
754 */
755 private void setHeadAndPropagate(Node node, int propagate) {
756 Node h = head; // Record old head for check below
757 setHead(node);
758 /*
759 * Try to signal next queued node if:
760 * Propagation was indicated by caller,
761 * or was recorded (as h.waitStatus either before
762 * or after setHead) by a previous operation
763 * (note: this uses sign-check of waitStatus because
764 * PROPAGATE status may transition to SIGNAL.)
765 * and
766 * The next node is waiting in shared mode,
767 * or we don't know, because it appears null
768 *
769 * The conservatism in both of these checks may cause
770 * unnecessary wake-ups, but only when there are multiple
771 * racing acquires/releases, so most need signals now or soon
772 * anyway.
773 */
774 if (propagate > 0 || h == null || h.waitStatus < 0 ||
775 (h = head) == null || h.waitStatus < 0) {
776 Node s = node.next;
777 if (s == null || s.isShared())
778 doReleaseShared();
779 }
780 }
781
782 // Utilities for various versions of acquire
783
784 /**
785 * Cancels an ongoing attempt to acquire.
786 *
787 * @param node the node
788 */
789 private void cancelAcquire(Node node) {
790 // Ignore if node doesn't exist
791 if (node == null)
792 return;
793
794 node.thread = null;
795
796 // Skip cancelled predecessors
797 Node pred = node.prev;
798 while (pred.waitStatus > 0)
799 node.prev = pred = pred.prev;
800
801 // predNext is the apparent node to unsplice. CASes below will
802 // fail if not, in which case, we lost race vs another cancel
803 // or signal, so no further action is necessary, although with
804 // a possibility that a cancelled node may transiently remain
805 // reachable.
806 Node predNext = pred.next;
807
808 // Can use unconditional write instead of CAS here.
809 // After this atomic step, other Nodes can skip past us.
810 // Before, we are free of interference from other threads.
811 node.waitStatus = Node.CANCELLED;
812
813 // If we are the tail, remove ourselves.
814 if (node == tail && compareAndSetTail(node, pred)) {
815 pred.compareAndSetNext(predNext, null);
816 } else {
817 // If successor needs signal, try to set pred's next-link
818 // so it will get one. Otherwise wake it up to propagate.
819 int ws;
820 if (pred != head &&
821 ((ws = pred.waitStatus) == Node.SIGNAL ||
822 (ws <= 0 && pred.compareAndSetWaitStatus(ws, Node.SIGNAL))) &&
823 pred.thread != null) {
824 Node next = node.next;
825 if (next != null && next.waitStatus <= 0)
826 pred.compareAndSetNext(predNext, next);
827 } else {
828 unparkSuccessor(node);
829 }
830
831 node.next = node; // help GC
832 }
833 }
834
835 /**
836 * Checks and updates status for a node that failed to acquire.
837 * Returns true if thread should block. This is the main signal
838 * control in all acquire loops. Requires that pred == node.prev.
839 *
840 * @param pred node's predecessor holding status
841 * @param node the node
842 * @return {@code true} if thread should block
843 */
844 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
845 int ws = pred.waitStatus;
846 if (ws == Node.SIGNAL)
847 /*
848 * This node has already set status asking a release
849 * to signal it, so it can safely park.
850 */
851 return true;
852 if (ws > 0) {
853 /*
854 * Predecessor was cancelled. Skip over predecessors and
855 * indicate retry.
856 */
857 do {
858 node.prev = pred = pred.prev;
859 } while (pred.waitStatus > 0);
860 pred.next = node;
861 } else {
862 /*
863 * waitStatus must be 0 or PROPAGATE. Indicate that we
864 * need a signal, but don't park yet. Caller will need to
865 * retry to make sure it cannot acquire before parking.
866 */
867 pred.compareAndSetWaitStatus(ws, Node.SIGNAL);
868 }
869 return false;
870 }
871
872 /**
873 * Convenience method to interrupt current thread.
874 */
875 static void selfInterrupt() {
876 Thread.currentThread().interrupt();
877 }
878
879 /**
880 * Convenience method to park and then check if interrupted.
881 *
882 * @return {@code true} if interrupted
883 */
884 private final boolean parkAndCheckInterrupt() {
885 LockSupport.park(this);
886 return Thread.interrupted();
887 }
888
889 /*
890 * Various flavors of acquire, varying in exclusive/shared and
891 * control modes. Each is mostly the same, but annoyingly
892 * different. Only a little bit of factoring is possible due to
893 * interactions of exception mechanics (including ensuring that we
894 * cancel if tryAcquire throws exception) and other control, at
895 * least not without hurting performance too much.
896 */
897
898 /**
899 * Acquires in exclusive uninterruptible mode for thread already in
900 * queue. Used by condition wait methods as well as acquire.
901 *
902 * @param node the node
903 * @param arg the acquire argument
904 * @return {@code true} if interrupted while waiting
905 */
906 final boolean acquireQueued(final Node node, int arg) {
907 boolean interrupted = false;
908 try {
909 for (;;) {
910 final Node p = node.predecessor();
911 if (p == head && tryAcquire(arg)) {
912 setHead(node);
913 p.next = null; // help GC
914 return interrupted;
915 }
916 if (shouldParkAfterFailedAcquire(p, node))
917 interrupted |= parkAndCheckInterrupt();
918 }
919 } catch (Throwable t) {
920 cancelAcquire(node);
921 if (interrupted)
922 selfInterrupt();
923 throw t;
924 }
925 }
926
927 /**
928 * Acquires in exclusive interruptible mode.
929 * @param arg the acquire argument
930 */
931 private void doAcquireInterruptibly(int arg)
932 throws InterruptedException {
933 final Node node = addWaiter(Node.EXCLUSIVE);
934 try {
935 for (;;) {
936 final Node p = node.predecessor();
937 if (p == head && tryAcquire(arg)) {
938 setHead(node);
939 p.next = null; // help GC
940 return;
941 }
942 if (shouldParkAfterFailedAcquire(p, node) &&
943 parkAndCheckInterrupt())
944 throw new InterruptedException();
945 }
946 } catch (Throwable t) {
947 cancelAcquire(node);
948 throw t;
949 }
950 }
951
952 /**
953 * Acquires in exclusive timed mode.
954 *
955 * @param arg the acquire argument
956 * @param nanosTimeout max wait time
957 * @return {@code true} if acquired
958 */
959 private boolean doAcquireNanos(int arg, long nanosTimeout)
960 throws InterruptedException {
961 if (nanosTimeout <= 0L)
962 return false;
963 final long deadline = System.nanoTime() + nanosTimeout;
964 final Node node = addWaiter(Node.EXCLUSIVE);
965 try {
966 for (;;) {
967 final Node p = node.predecessor();
968 if (p == head && tryAcquire(arg)) {
969 setHead(node);
970 p.next = null; // help GC
971 return true;
972 }
973 nanosTimeout = deadline - System.nanoTime();
974 if (nanosTimeout <= 0L) {
975 cancelAcquire(node);
976 return false;
977 }
978 if (shouldParkAfterFailedAcquire(p, node) &&
979 nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
980 LockSupport.parkNanos(this, nanosTimeout);
981 if (Thread.interrupted())
982 throw new InterruptedException();
983 }
984 } catch (Throwable t) {
985 cancelAcquire(node);
986 throw t;
987 }
988 }
989
990 /**
991 * Acquires in shared uninterruptible mode.
992 * @param arg the acquire argument
993 */
994 private void doAcquireShared(int arg) {
995 final Node node = addWaiter(Node.SHARED);
996 boolean interrupted = false;
997 try {
998 for (;;) {
999 final Node p = node.predecessor();
1000 if (p == head) {
1001 int r = tryAcquireShared(arg);
1002 if (r >= 0) {
1003 setHeadAndPropagate(node, r);
1004 p.next = null; // help GC
1005 return;
1006 }
1007 }
1008 if (shouldParkAfterFailedAcquire(p, node))
1009 interrupted |= parkAndCheckInterrupt();
1010 }
1011 } catch (Throwable t) {
1012 cancelAcquire(node);
1013 throw t;
1014 } finally {
1015 if (interrupted)
1016 selfInterrupt();
1017 }
1018 }
1019
1020 /**
1021 * Acquires in shared interruptible mode.
1022 * @param arg the acquire argument
1023 */
1024 private void doAcquireSharedInterruptibly(int arg)
1025 throws InterruptedException {
1026 final Node node = addWaiter(Node.SHARED);
1027 try {
1028 for (;;) {
1029 final Node p = node.predecessor();
1030 if (p == head) {
1031 int r = tryAcquireShared(arg);
1032 if (r >= 0) {
1033 setHeadAndPropagate(node, r);
1034 p.next = null; // help GC
1035 return;
1036 }
1037 }
1038 if (shouldParkAfterFailedAcquire(p, node) &&
1039 parkAndCheckInterrupt())
1040 throw new InterruptedException();
1041 }
1042 } catch (Throwable t) {
1043 cancelAcquire(node);
1044 throw t;
1045 }
1046 }
1047
1048 /**
1049 * Acquires in shared timed mode.
1050 *
1051 * @param arg the acquire argument
1052 * @param nanosTimeout max wait time
1053 * @return {@code true} if acquired
1054 */
1055 private boolean doAcquireSharedNanos(int arg, long nanosTimeout)
1056 throws InterruptedException {
1057 if (nanosTimeout <= 0L)
1058 return false;
1059 final long deadline = System.nanoTime() + nanosTimeout;
1060 final Node node = addWaiter(Node.SHARED);
1061 try {
1062 for (;;) {
1063 final Node p = node.predecessor();
1064 if (p == head) {
1065 int r = tryAcquireShared(arg);
1066 if (r >= 0) {
1067 setHeadAndPropagate(node, r);
1068 p.next = null; // help GC
1069 return true;
1070 }
1071 }
1072 nanosTimeout = deadline - System.nanoTime();
1073 if (nanosTimeout <= 0L) {
1074 cancelAcquire(node);
1075 return false;
1076 }
1077 if (shouldParkAfterFailedAcquire(p, node) &&
1078 nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
1079 LockSupport.parkNanos(this, nanosTimeout);
1080 if (Thread.interrupted())
1081 throw new InterruptedException();
1082 }
1083 } catch (Throwable t) {
1084 cancelAcquire(node);
1085 throw t;
1086 }
1087 }
1088
1089 // Main exported methods
1090
1091 /**
1092 * Attempts to acquire in exclusive mode. This method should query
1093 * if the state of the object permits it to be acquired in the
1094 * exclusive mode, and if so to acquire it.
1095 *
1096 * <p>This method is always invoked by the thread performing
1097 * acquire. If this method reports failure, the acquire method
1098 * may queue the thread, if it is not already queued, until it is
1099 * signalled by a release from some other thread. This can be used
1100 * to implement method {@link Lock#tryLock()}.
1101 *
1102 * <p>The default
1103 * implementation throws {@link UnsupportedOperationException}.
1104 *
1105 * @param arg the acquire argument. This value is always the one
1106 * passed to an acquire method, or is the value saved on entry
1107 * to a condition wait. The value is otherwise uninterpreted
1108 * and can represent anything you like.
1109 * @return {@code true} if successful. Upon success, this object has
1110 * been acquired.
1111 * @throws IllegalMonitorStateException if acquiring would place this
1112 * synchronizer in an illegal state. This exception must be
1113 * thrown in a consistent fashion for synchronization to work
1114 * correctly.
1115 * @throws UnsupportedOperationException if exclusive mode is not supported
1116 */
1117 protected boolean tryAcquire(int arg) {
1118 throw new UnsupportedOperationException();
1119 }
1120
1121 /**
1122 * Attempts to set the state to reflect a release in exclusive
1123 * mode.
1124 *
1125 * <p>This method is always invoked by the thread performing release.
1126 *
1127 * <p>The default implementation throws
1128 * {@link UnsupportedOperationException}.
1129 *
1130 * @param arg the release argument. This value is always the one
1131 * passed to a release method, or the current state value upon
1132 * entry to a condition wait. The value is otherwise
1133 * uninterpreted and can represent anything you like.
1134 * @return {@code true} if this object is now in a fully released
1135 * state, so that any waiting threads may attempt to acquire;
1136 * and {@code false} otherwise.
1137 * @throws IllegalMonitorStateException if releasing would place this
1138 * synchronizer in an illegal state. This exception must be
1139 * thrown in a consistent fashion for synchronization to work
1140 * correctly.
1141 * @throws UnsupportedOperationException if exclusive mode is not supported
1142 */
1143 protected boolean tryRelease(int arg) {
1144 throw new UnsupportedOperationException();
1145 }
1146
1147 /**
1148 * Attempts to acquire in shared mode. This method should query if
1149 * the state of the object permits it to be acquired in the shared
1150 * mode, and if so to acquire it.
1151 *
1152 * <p>This method is always invoked by the thread performing
1153 * acquire. If this method reports failure, the acquire method
1154 * may queue the thread, if it is not already queued, until it is
1155 * signalled by a release from some other thread.
1156 *
1157 * <p>The default implementation throws {@link
1158 * UnsupportedOperationException}.
1159 *
1160 * @param arg the acquire argument. This value is always the one
1161 * passed to an acquire method, or is the value saved on entry
1162 * to a condition wait. The value is otherwise uninterpreted
1163 * and can represent anything you like.
1164 * @return a negative value on failure; zero if acquisition in shared
1165 * mode succeeded but no subsequent shared-mode acquire can
1166 * succeed; and a positive value if acquisition in shared
1167 * mode succeeded and subsequent shared-mode acquires might
1168 * also succeed, in which case a subsequent waiting thread
1169 * must check availability. (Support for three different
1170 * return values enables this method to be used in contexts
1171 * where acquires only sometimes act exclusively.) Upon
1172 * success, this object has been acquired.
1173 * @throws IllegalMonitorStateException if acquiring would place this
1174 * synchronizer in an illegal state. This exception must be
1175 * thrown in a consistent fashion for synchronization to work
1176 * correctly.
1177 * @throws UnsupportedOperationException if shared mode is not supported
1178 */
1179 protected int tryAcquireShared(int arg) {
1180 throw new UnsupportedOperationException();
1181 }
1182
1183 /**
1184 * Attempts to set the state to reflect a release in shared mode.
1185 *
1186 * <p>This method is always invoked by the thread performing release.
1187 *
1188 * <p>The default implementation throws
1189 * {@link UnsupportedOperationException}.
1190 *
1191 * @param arg the release argument. This value is always the one
1192 * passed to a release method, or the current state value upon
1193 * entry to a condition wait. The value is otherwise
1194 * uninterpreted and can represent anything you like.
1195 * @return {@code true} if this release of shared mode may permit a
1196 * waiting acquire (shared or exclusive) to succeed; and
1197 * {@code false} otherwise
1198 * @throws IllegalMonitorStateException if releasing would place this
1199 * synchronizer in an illegal state. This exception must be
1200 * thrown in a consistent fashion for synchronization to work
1201 * correctly.
1202 * @throws UnsupportedOperationException if shared mode is not supported
1203 */
1204 protected boolean tryReleaseShared(int arg) {
1205 throw new UnsupportedOperationException();
1206 }
1207
1208 /**
1209 * Returns {@code true} if synchronization is held exclusively with
1210 * respect to the current (calling) thread. This method is invoked
1211 * upon each call to a {@link ConditionObject} method.
1212 *
1213 * <p>The default implementation throws {@link
1214 * UnsupportedOperationException}. This method is invoked
1215 * internally only within {@link ConditionObject} methods, so need
1216 * not be defined if conditions are not used.
1217 *
1218 * @return {@code true} if synchronization is held exclusively;
1219 * {@code false} otherwise
1220 * @throws UnsupportedOperationException if conditions are not supported
1221 */
1222 protected boolean isHeldExclusively() {
1223 throw new UnsupportedOperationException();
1224 }
1225
1226 /**
1227 * Acquires in exclusive mode, ignoring interrupts. Implemented
1228 * by invoking at least once {@link #tryAcquire},
1229 * returning on success. Otherwise the thread is queued, possibly
1230 * repeatedly blocking and unblocking, invoking {@link
1231 * #tryAcquire} until success. This method can be used
1232 * to implement method {@link Lock#lock}.
1233 *
1234 * @param arg the acquire argument. This value is conveyed to
1235 * {@link #tryAcquire} but is otherwise uninterpreted and
1236 * can represent anything you like.
1237 */
1238 public final void acquire(int arg) {
1239 if (!tryAcquire(arg) &&
1240 acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
1241 selfInterrupt();
1242 }
1243
1244 /**
1245 * Acquires in exclusive mode, aborting if interrupted.
1246 * Implemented by first checking interrupt status, then invoking
1247 * at least once {@link #tryAcquire}, returning on
1248 * success. Otherwise the thread is queued, possibly repeatedly
1249 * blocking and unblocking, invoking {@link #tryAcquire}
1250 * until success or the thread is interrupted. This method can be
1251 * used to implement method {@link Lock#lockInterruptibly}.
1252 *
1253 * @param arg the acquire argument. This value is conveyed to
1254 * {@link #tryAcquire} but is otherwise uninterpreted and
1255 * can represent anything you like.
1256 * @throws InterruptedException if the current thread is interrupted
1257 */
1258 public final void acquireInterruptibly(int arg)
1259 throws InterruptedException {
1260 if (Thread.interrupted())
1261 throw new InterruptedException();
1262 if (!tryAcquire(arg))
1263 doAcquireInterruptibly(arg);
1264 }
1265
1266 /**
1267 * Attempts to acquire in exclusive mode, aborting if interrupted,
1268 * and failing if the given timeout elapses. Implemented by first
1269 * checking interrupt status, then invoking at least once {@link
1270 * #tryAcquire}, returning on success. Otherwise, the thread is
1271 * queued, possibly repeatedly blocking and unblocking, invoking
1272 * {@link #tryAcquire} until success or the thread is interrupted
1273 * or the timeout elapses. This method can be used to implement
1274 * method {@link Lock#tryLock(long, TimeUnit)}.
1275 *
1276 * @param arg the acquire argument. This value is conveyed to
1277 * {@link #tryAcquire} but is otherwise uninterpreted and
1278 * can represent anything you like.
1279 * @param nanosTimeout the maximum number of nanoseconds to wait
1280 * @return {@code true} if acquired; {@code false} if timed out
1281 * @throws InterruptedException if the current thread is interrupted
1282 */
1283 public final boolean tryAcquireNanos(int arg, long nanosTimeout)
1284 throws InterruptedException {
1285 if (Thread.interrupted())
1286 throw new InterruptedException();
1287 return tryAcquire(arg) ||
1288 doAcquireNanos(arg, nanosTimeout);
1289 }
1290
1291 /**
1292 * Releases in exclusive mode. Implemented by unblocking one or
1293 * more threads if {@link #tryRelease} returns true.
1294 * This method can be used to implement method {@link Lock#unlock}.
1295 *
1296 * @param arg the release argument. This value is conveyed to
1297 * {@link #tryRelease} but is otherwise uninterpreted and
1298 * can represent anything you like.
1299 * @return the value returned from {@link #tryRelease}
1300 */
1301 public final boolean release(int arg) {
1302 if (tryRelease(arg)) {
1303 Node h = head;
1304 if (h != null && h.waitStatus != 0)
1305 unparkSuccessor(h);
1306 return true;
1307 }
1308 return false;
1309 }
1310
1311 /**
1312 * Acquires in shared mode, ignoring interrupts. Implemented by
1313 * first invoking at least once {@link #tryAcquireShared},
1314 * returning on success. Otherwise the thread is queued, possibly
1315 * repeatedly blocking and unblocking, invoking {@link
1316 * #tryAcquireShared} until success.
1317 *
1318 * @param arg the acquire argument. This value is conveyed to
1319 * {@link #tryAcquireShared} but is otherwise uninterpreted
1320 * and can represent anything you like.
1321 */
1322 public final void acquireShared(int arg) {
1323 if (tryAcquireShared(arg) < 0)
1324 doAcquireShared(arg);
1325 }
1326
1327 /**
1328 * Acquires in shared mode, aborting if interrupted. Implemented
1329 * by first checking interrupt status, then invoking at least once
1330 * {@link #tryAcquireShared}, returning on success. Otherwise the
1331 * thread is queued, possibly repeatedly blocking and unblocking,
1332 * invoking {@link #tryAcquireShared} until success or the thread
1333 * is interrupted.
1334 * @param arg the acquire argument.
1335 * This value is conveyed to {@link #tryAcquireShared} but is
1336 * otherwise uninterpreted and can represent anything
1337 * you like.
1338 * @throws InterruptedException if the current thread is interrupted
1339 */
1340 public final void acquireSharedInterruptibly(int arg)
1341 throws InterruptedException {
1342 if (Thread.interrupted())
1343 throw new InterruptedException();
1344 if (tryAcquireShared(arg) < 0)
1345 doAcquireSharedInterruptibly(arg);
1346 }
1347
1348 /**
1349 * Attempts to acquire in shared mode, aborting if interrupted, and
1350 * failing if the given timeout elapses. Implemented by first
1351 * checking interrupt status, then invoking at least once {@link
1352 * #tryAcquireShared}, returning on success. Otherwise, the
1353 * thread is queued, possibly repeatedly blocking and unblocking,
1354 * invoking {@link #tryAcquireShared} until success or the thread
1355 * is interrupted or the timeout elapses.
1356 *
1357 * @param arg the acquire argument. This value is conveyed to
1358 * {@link #tryAcquireShared} but is otherwise uninterpreted
1359 * and can represent anything you like.
1360 * @param nanosTimeout the maximum number of nanoseconds to wait
1361 * @return {@code true} if acquired; {@code false} if timed out
1362 * @throws InterruptedException if the current thread is interrupted
1363 */
1364 public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)
1365 throws InterruptedException {
1366 if (Thread.interrupted())
1367 throw new InterruptedException();
1368 return tryAcquireShared(arg) >= 0 ||
1369 doAcquireSharedNanos(arg, nanosTimeout);
1370 }
1371
1372 /**
1373 * Releases in shared mode. Implemented by unblocking one or more
1374 * threads if {@link #tryReleaseShared} returns true.
1375 *
1376 * @param arg the release argument. This value is conveyed to
1377 * {@link #tryReleaseShared} but is otherwise uninterpreted
1378 * and can represent anything you like.
1379 * @return the value returned from {@link #tryReleaseShared}
1380 */
1381 public final boolean releaseShared(int arg) {
1382 if (tryReleaseShared(arg)) {
1383 doReleaseShared();
1384 return true;
1385 }
1386 return false;
1387 }
1388
1389 // Queue inspection methods
1390
1391 /**
1392 * Queries whether any threads are waiting to acquire. Note that
1393 * because cancellations due to interrupts and timeouts may occur
1394 * at any time, a {@code true} return does not guarantee that any
1395 * other thread will ever acquire.
1396 *
1397 * @return {@code true} if there may be other threads waiting to acquire
1398 */
1399 public final boolean hasQueuedThreads() {
1400 for (Node p = tail, h = head; p != h && p != null; p = p.prev)
1401 if (p.waitStatus <= 0)
1402 return true;
1403 return false;
1404 }
1405
1406 /**
1407 * Queries whether any threads have ever contended to acquire this
1408 * synchronizer; that is, if an acquire method has ever blocked.
1409 *
1410 * <p>In this implementation, this operation returns in
1411 * constant time.
1412 *
1413 * @return {@code true} if there has ever been contention
1414 */
1415 public final boolean hasContended() {
1416 return head != null;
1417 }
1418
1419 /**
1420 * Returns the first (longest-waiting) thread in the queue, or
1421 * {@code null} if no threads are currently queued.
1422 *
1423 * <p>In this implementation, this operation normally returns in
1424 * constant time, but may iterate upon contention if other threads are
1425 * concurrently modifying the queue.
1426 *
1427 * @return the first (longest-waiting) thread in the queue, or
1428 * {@code null} if no threads are currently queued
1429 */
1430 public final Thread getFirstQueuedThread() {
1431 // handle only fast path, else relay
1432 return (head == tail) ? null : fullGetFirstQueuedThread();
1433 }
1434
1435 /**
1436 * Version of getFirstQueuedThread called when fastpath fails.
1437 */
1438 private Thread fullGetFirstQueuedThread() {
1439 /*
1440 * The first node is normally head.next. Try to get its
1441 * thread field, ensuring consistent reads: If thread
1442 * field is nulled out or s.prev is no longer head, then
1443 * some other thread(s) concurrently performed setHead in
1444 * between some of our reads. We try this twice before
1445 * resorting to traversal.
1446 */
1447 Node h, s;
1448 Thread st;
1449 if (((h = head) != null && (s = h.next) != null &&
1450 s.prev == head && (st = s.thread) != null) ||
1451 ((h = head) != null && (s = h.next) != null &&
1452 s.prev == head && (st = s.thread) != null))
1453 return st;
1454
1455 /*
1456 * Head's next field might not have been set yet, or may have
1457 * been unset after setHead. So we must check to see if tail
1458 * is actually first node. If not, we continue on, safely
1459 * traversing from tail back to head to find first,
1460 * guaranteeing termination.
1461 */
1462
1463 Thread firstThread = null;
1464 for (Node p = tail; p != null && p != head; p = p.prev) {
1465 Thread t = p.thread;
1466 if (t != null)
1467 firstThread = t;
1468 }
1469 return firstThread;
1470 }
1471
1472 /**
1473 * Returns true if the given thread is currently queued.
1474 *
1475 * <p>This implementation traverses the queue to determine
1476 * presence of the given thread.
1477 *
1478 * @param thread the thread
1479 * @return {@code true} if the given thread is on the queue
1480 * @throws NullPointerException if the thread is null
1481 */
1482 public final boolean isQueued(Thread thread) {
1483 if (thread == null)
1484 throw new NullPointerException();
1485 for (Node p = tail; p != null; p = p.prev)
1486 if (p.thread == thread)
1487 return true;
1488 return false;
1489 }
1490
1491 /**
1492 * Returns {@code true} if the apparent first queued thread, if one
1493 * exists, is waiting in exclusive mode. If this method returns
1494 * {@code true}, and the current thread is attempting to acquire in
1495 * shared mode (that is, this method is invoked from {@link
1496 * #tryAcquireShared}) then it is guaranteed that the current thread
1497 * is not the first queued thread. Used only as a heuristic in
1498 * ReentrantReadWriteLock.
1499 */
1500 final boolean apparentlyFirstQueuedIsExclusive() {
1501 Node h, s;
1502 return (h = head) != null &&
1503 (s = h.next) != null &&
1504 !s.isShared() &&
1505 s.thread != null;
1506 }
1507
1508 /**
1509 * Queries whether any threads have been waiting to acquire longer
1510 * than the current thread.
1511 *
1512 * <p>An invocation of this method is equivalent to (but may be
1513 * more efficient than):
1514 * <pre> {@code
1515 * getFirstQueuedThread() != Thread.currentThread()
1516 * && hasQueuedThreads()}</pre>
1517 *
1518 * <p>Note that because cancellations due to interrupts and
1519 * timeouts may occur at any time, a {@code true} return does not
1520 * guarantee that some other thread will acquire before the current
1521 * thread. Likewise, it is possible for another thread to win a
1522 * race to enqueue after this method has returned {@code false},
1523 * due to the queue being empty.
1524 *
1525 * <p>This method is designed to be used by a fair synchronizer to
1526 * avoid <a href="AbstractQueuedSynchronizer.html#barging">barging</a>.
1527 * Such a synchronizer's {@link #tryAcquire} method should return
1528 * {@code false}, and its {@link #tryAcquireShared} method should
1529 * return a negative value, if this method returns {@code true}
1530 * (unless this is a reentrant acquire). For example, the {@code
1531 * tryAcquire} method for a fair, reentrant, exclusive mode
1532 * synchronizer might look like this:
1533 *
1534 * <pre> {@code
1535 * protected boolean tryAcquire(int arg) {
1536 * if (isHeldExclusively()) {
1537 * // A reentrant acquire; increment hold count
1538 * return true;
1539 * } else if (hasQueuedPredecessors()) {
1540 * return false;
1541 * } else {
1542 * // try to acquire normally
1543 * }
1544 * }}</pre>
1545 *
1546 * @return {@code true} if there is a queued thread preceding the
1547 * current thread, and {@code false} if the current thread
1548 * is at the head of the queue or the queue is empty
1549 * @since 1.7
1550 */
1551 public final boolean hasQueuedPredecessors() {
1552 Node h, s;
1553 if ((h = head) != null) {
1554 if ((s = h.next) == null || s.waitStatus > 0) {
1555 s = null; // traverse in case of concurrent cancellation
1556 for (Node p = tail; p != h && p != null; p = p.prev) {
1557 if (p.waitStatus <= 0)
1558 s = p;
1559 }
1560 }
1561 if (s != null && s.thread != Thread.currentThread())
1562 return true;
1563 }
1564 return false;
1565 }
1566
1567 // Instrumentation and monitoring methods
1568
1569 /**
1570 * Returns an estimate of the number of threads waiting to
1571 * acquire. The value is only an estimate because the number of
1572 * threads may change dynamically while this method traverses
1573 * internal data structures. This method is designed for use in
1574 * monitoring system state, not for synchronization control.
1575 *
1576 * @return the estimated number of threads waiting to acquire
1577 */
1578 public final int getQueueLength() {
1579 int n = 0;
1580 for (Node p = tail; p != null; p = p.prev) {
1581 if (p.thread != null)
1582 ++n;
1583 }
1584 return n;
1585 }
1586
1587 /**
1588 * Returns a collection containing threads that may be waiting to
1589 * acquire. Because the actual set of threads may change
1590 * dynamically while constructing this result, the returned
1591 * collection is only a best-effort estimate. The elements of the
1592 * returned collection are in no particular order. This method is
1593 * designed to facilitate construction of subclasses that provide
1594 * more extensive monitoring facilities.
1595 *
1596 * @return the collection of threads
1597 */
1598 public final Collection<Thread> getQueuedThreads() {
1599 ArrayList<Thread> list = new ArrayList<>();
1600 for (Node p = tail; p != null; p = p.prev) {
1601 Thread t = p.thread;
1602 if (t != null)
1603 list.add(t);
1604 }
1605 return list;
1606 }
1607
1608 /**
1609 * Returns a collection containing threads that may be waiting to
1610 * acquire in exclusive mode. This has the same properties
1611 * as {@link #getQueuedThreads} except that it only returns
1612 * those threads waiting due to an exclusive acquire.
1613 *
1614 * @return the collection of threads
1615 */
1616 public final Collection<Thread> getExclusiveQueuedThreads() {
1617 ArrayList<Thread> list = new ArrayList<>();
1618 for (Node p = tail; p != null; p = p.prev) {
1619 if (!p.isShared()) {
1620 Thread t = p.thread;
1621 if (t != null)
1622 list.add(t);
1623 }
1624 }
1625 return list;
1626 }
1627
1628 /**
1629 * Returns a collection containing threads that may be waiting to
1630 * acquire in shared mode. This has the same properties
1631 * as {@link #getQueuedThreads} except that it only returns
1632 * those threads waiting due to a shared acquire.
1633 *
1634 * @return the collection of threads
1635 */
1636 public final Collection<Thread> getSharedQueuedThreads() {
1637 ArrayList<Thread> list = new ArrayList<>();
1638 for (Node p = tail; p != null; p = p.prev) {
1639 if (p.isShared()) {
1640 Thread t = p.thread;
1641 if (t != null)
1642 list.add(t);
1643 }
1644 }
1645 return list;
1646 }
1647
1648 /**
1649 * Returns a string identifying this synchronizer, as well as its state.
1650 * The state, in brackets, includes the String {@code "State ="}
1651 * followed by the current value of {@link #getState}, and either
1652 * {@code "nonempty"} or {@code "empty"} depending on whether the
1653 * queue is empty.
1654 *
1655 * @return a string identifying this synchronizer, as well as its state
1656 */
1657 public String toString() {
1658 return super.toString()
1659 + "[State = " + getState() + ", "
1660 + (hasQueuedThreads() ? "non" : "") + "empty queue]";
1661 }
1662
1663
1664 // Internal support methods for Conditions
1665
1666 /**
1667 * Returns true if a node, always one that was initially placed on
1668 * a condition queue, is now waiting to reacquire on sync queue.
1669 * @param node the node
1670 * @return true if is reacquiring
1671 */
1672 final boolean isOnSyncQueue(Node node) {
1673 if (node.waitStatus == Node.CONDITION || node.prev == null)
1674 return false;
1675 if (node.next != null) // If has successor, it must be on queue
1676 return true;
1677 /*
1678 * node.prev can be non-null, but not yet on queue because
1679 * the CAS to place it on queue can fail. So we have to
1680 * traverse from tail to make sure it actually made it. It
1681 * will always be near the tail in calls to this method, and
1682 * unless the CAS failed (which is unlikely), it will be
1683 * there, so we hardly ever traverse much.
1684 */
1685 return findNodeFromTail(node);
1686 }
1687
1688 /**
1689 * Returns true if node is on sync queue by searching backwards from tail.
1690 * Called only when needed by isOnSyncQueue.
1691 * @return true if present
1692 */
1693 private boolean findNodeFromTail(Node node) {
1694 // We check for node first, since it's likely to be at or near tail.
1695 // tail is known to be non-null, so we could re-order to "save"
1696 // one null check, but we leave it this way to help the VM.
1697 for (Node p = tail;;) {
1698 if (p == node)
1699 return true;
1700 if (p == null)
1701 return false;
1702 p = p.prev;
1703 }
1704 }
1705
1706 /**
1707 * Transfers a node from a condition queue onto sync queue.
1708 * Returns true if successful.
1709 * @param node the node
1710 * @return true if successfully transferred (else the node was
1711 * cancelled before signal)
1712 */
1713 final boolean transferForSignal(Node node) {
1714 /*
1715 * If cannot change waitStatus, the node has been cancelled.
1716 */
1717 if (!node.compareAndSetWaitStatus(Node.CONDITION, 0))
1718 return false;
1719
1720 /*
1721 * Splice onto queue and try to set waitStatus of predecessor to
1722 * indicate that thread is (probably) waiting. If cancelled or
1723 * attempt to set waitStatus fails, wake up to resync (in which
1724 * case the waitStatus can be transiently and harmlessly wrong).
1725 */
1726 Node p = enq(node);
1727 int ws = p.waitStatus;
1728 if (ws > 0 || !p.compareAndSetWaitStatus(ws, Node.SIGNAL))
1729 LockSupport.unpark(node.thread);
1730 return true;
1731 }
1732
1733 /**
1734 * Transfers node, if necessary, to sync queue after a cancelled wait.
1735 * Returns true if thread was cancelled before being signalled.
1736 *
1737 * @param node the node
1738 * @return true if cancelled before the node was signalled
1739 */
1740 final boolean transferAfterCancelledWait(Node node) {
1741 if (node.compareAndSetWaitStatus(Node.CONDITION, 0)) {
1742 enq(node);
1743 return true;
1744 }
1745 /*
1746 * If we lost out to a signal(), then we can't proceed
1747 * until it finishes its enq(). Cancelling during an
1748 * incomplete transfer is both rare and transient, so just
1749 * spin.
1750 */
1751 while (!isOnSyncQueue(node))
1752 Thread.yield();
1753 return false;
1754 }
1755
1756 /**
1757 * Invokes release with current state value; returns saved state.
1758 * Cancels node and throws exception on failure.
1759 * @param node the condition node for this wait
1760 * @return previous sync state
1761 */
1762 final int fullyRelease(Node node) {
1763 try {
1764 int savedState = getState();
1765 if (release(savedState))
1766 return savedState;
1767 throw new IllegalMonitorStateException();
1768 } catch (Throwable t) {
1769 node.waitStatus = Node.CANCELLED;
1770 throw t;
1771 }
1772 }
1773
1774 // Instrumentation methods for conditions
1775
1776 /**
1777 * Queries whether the given ConditionObject
1778 * uses this synchronizer as its lock.
1779 *
1780 * @param condition the condition
1781 * @return {@code true} if owned
1782 * @throws NullPointerException if the condition is null
1783 */
1784 public final boolean owns(ConditionObject condition) {
1785 return condition.isOwnedBy(this);
1786 }
1787
1788 /**
1789 * Queries whether any threads are waiting on the given condition
1790 * associated with this synchronizer. Note that because timeouts
1791 * and interrupts may occur at any time, a {@code true} return
1792 * does not guarantee that a future {@code signal} will awaken
1793 * any threads. This method is designed primarily for use in
1794 * monitoring of the system state.
1795 *
1796 * @param condition the condition
1797 * @return {@code true} if there are any waiting threads
1798 * @throws IllegalMonitorStateException if exclusive synchronization
1799 * is not held
1800 * @throws IllegalArgumentException if the given condition is
1801 * not associated with this synchronizer
1802 * @throws NullPointerException if the condition is null
1803 */
1804 public final boolean hasWaiters(ConditionObject condition) {
1805 if (!owns(condition))
1806 throw new IllegalArgumentException("Not owner");
1807 return condition.hasWaiters();
1808 }
1809
1810 /**
1811 * Returns an estimate of the number of threads waiting on the
1812 * given condition associated with this synchronizer. Note that
1813 * because timeouts and interrupts may occur at any time, the
1814 * estimate serves only as an upper bound on the actual number of
1815 * waiters. This method is designed for use in monitoring system
1816 * state, not for synchronization control.
1817 *
1818 * @param condition the condition
1819 * @return the estimated number of waiting threads
1820 * @throws IllegalMonitorStateException if exclusive synchronization
1821 * is not held
1822 * @throws IllegalArgumentException if the given condition is
1823 * not associated with this synchronizer
1824 * @throws NullPointerException if the condition is null
1825 */
1826 public final int getWaitQueueLength(ConditionObject condition) {
1827 if (!owns(condition))
1828 throw new IllegalArgumentException("Not owner");
1829 return condition.getWaitQueueLength();
1830 }
1831
1832 /**
1833 * Returns a collection containing those threads that may be
1834 * waiting on the given condition associated with this
1835 * synchronizer. Because the actual set of threads may change
1836 * dynamically while constructing this result, the returned
1837 * collection is only a best-effort estimate. The elements of the
1838 * returned collection are in no particular order.
1839 *
1840 * @param condition the condition
1841 * @return the collection of threads
1842 * @throws IllegalMonitorStateException if exclusive synchronization
1843 * is not held
1844 * @throws IllegalArgumentException if the given condition is
1845 * not associated with this synchronizer
1846 * @throws NullPointerException if the condition is null
1847 */
1848 public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1849 if (!owns(condition))
1850 throw new IllegalArgumentException("Not owner");
1851 return condition.getWaitingThreads();
1852 }
1853
1854 /**
1855 * Condition implementation for a {@link AbstractQueuedSynchronizer}
1856 * serving as the basis of a {@link Lock} implementation.
1857 *
1858 * <p>Method documentation for this class describes mechanics,
1859 * not behavioral specifications from the point of view of Lock
1860 * and Condition users. Exported versions of this class will in
1861 * general need to be accompanied by documentation describing
1862 * condition semantics that rely on those of the associated
1863 * {@code AbstractQueuedSynchronizer}.
1864 *
1865 * <p>This class is Serializable, but all fields are transient,
1866 * so deserialized conditions have no waiters.
1867 */
1868 public class ConditionObject implements Condition, java.io.Serializable {
1869 private static final long serialVersionUID = 1173984872572414699L;
1870 /** First node of condition queue. */
1871 private transient Node firstWaiter;
1872 /** Last node of condition queue. */
1873 private transient Node lastWaiter;
1874
1875 /**
1876 * Creates a new {@code ConditionObject} instance.
1877 */
1878 public ConditionObject() { }
1879
1880 // Internal methods
1881
1882 /**
1883 * Adds a new waiter to wait queue.
1884 * @return its new wait node
1885 */
1886 private Node addConditionWaiter() {
1887 if (!isHeldExclusively())
1888 throw new IllegalMonitorStateException();
1889 Node t = lastWaiter;
1890 // If lastWaiter is cancelled, clean out.
1891 if (t != null && t.waitStatus != Node.CONDITION) {
1892 unlinkCancelledWaiters();
1893 t = lastWaiter;
1894 }
1895
1896 Node node = new Node(Node.CONDITION);
1897
1898 if (t == null)
1899 firstWaiter = node;
1900 else
1901 t.nextWaiter = node;
1902 lastWaiter = node;
1903 return node;
1904 }
1905
1906 /**
1907 * Removes and transfers nodes until hit non-cancelled one or
1908 * null. Split out from signal in part to encourage compilers
1909 * to inline the case of no waiters.
1910 * @param first (non-null) the first node on condition queue
1911 */
1912 private void doSignal(Node first) {
1913 do {
1914 if ( (firstWaiter = first.nextWaiter) == null)
1915 lastWaiter = null;
1916 first.nextWaiter = null;
1917 } while (!transferForSignal(first) &&
1918 (first = firstWaiter) != null);
1919 }
1920
1921 /**
1922 * Removes and transfers all nodes.
1923 * @param first (non-null) the first node on condition queue
1924 */
1925 private void doSignalAll(Node first) {
1926 lastWaiter = firstWaiter = null;
1927 do {
1928 Node next = first.nextWaiter;
1929 first.nextWaiter = null;
1930 transferForSignal(first);
1931 first = next;
1932 } while (first != null);
1933 }
1934
1935 /**
1936 * Unlinks cancelled waiter nodes from condition queue.
1937 * Called only while holding lock. This is called when
1938 * cancellation occurred during condition wait, and upon
1939 * insertion of a new waiter when lastWaiter is seen to have
1940 * been cancelled. This method is needed to avoid garbage
1941 * retention in the absence of signals. So even though it may
1942 * require a full traversal, it comes into play only when
1943 * timeouts or cancellations occur in the absence of
1944 * signals. It traverses all nodes rather than stopping at a
1945 * particular target to unlink all pointers to garbage nodes
1946 * without requiring many re-traversals during cancellation
1947 * storms.
1948 */
1949 private void unlinkCancelledWaiters() {
1950 Node t = firstWaiter;
1951 Node trail = null;
1952 while (t != null) {
1953 Node next = t.nextWaiter;
1954 if (t.waitStatus != Node.CONDITION) {
1955 t.nextWaiter = null;
1956 if (trail == null)
1957 firstWaiter = next;
1958 else
1959 trail.nextWaiter = next;
1960 if (next == null)
1961 lastWaiter = trail;
1962 }
1963 else
1964 trail = t;
1965 t = next;
1966 }
1967 }
1968
1969 // public methods
1970
1971 /**
1972 * Moves the longest-waiting thread, if one exists, from the
1973 * wait queue for this condition to the wait queue for the
1974 * owning lock.
1975 *
1976 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1977 * returns {@code false}
1978 */
1979 public final void signal() {
1980 if (!isHeldExclusively())
1981 throw new IllegalMonitorStateException();
1982 Node first = firstWaiter;
1983 if (first != null)
1984 doSignal(first);
1985 }
1986
1987 /**
1988 * Moves all threads from the wait queue for this condition to
1989 * the wait queue for the owning lock.
1990 *
1991 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1992 * returns {@code false}
1993 */
1994 public final void signalAll() {
1995 if (!isHeldExclusively())
1996 throw new IllegalMonitorStateException();
1997 Node first = firstWaiter;
1998 if (first != null)
1999 doSignalAll(first);
2000 }
2001
2002 /**
2003 * Implements uninterruptible condition wait.
2004 * <ol>
2005 * <li>Save lock state returned by {@link #getState}.
2006 * <li>Invoke {@link #release} with saved state as argument,
2007 * throwing IllegalMonitorStateException if it fails.
2008 * <li>Block until signalled.
2009 * <li>Reacquire by invoking specialized version of
2010 * {@link #acquire} with saved state as argument.
2011 * </ol>
2012 */
2013 public final void awaitUninterruptibly() {
2014 Node node = addConditionWaiter();
2015 int savedState = fullyRelease(node);
2016 boolean interrupted = false;
2017 while (!isOnSyncQueue(node)) {
2018 LockSupport.park(this);
2019 if (Thread.interrupted())
2020 interrupted = true;
2021 }
2022 if (acquireQueued(node, savedState) || interrupted)
2023 selfInterrupt();
2024 }
2025
2026 /*
2027 * For interruptible waits, we need to track whether to throw
2028 * InterruptedException, if interrupted while blocked on
2029 * condition, versus reinterrupt current thread, if
2030 * interrupted while blocked waiting to re-acquire.
2031 */
2032
2033 /** Mode meaning to reinterrupt on exit from wait */
2034 private static final int REINTERRUPT = 1;
2035 /** Mode meaning to throw InterruptedException on exit from wait */
2036 private static final int THROW_IE = -1;
2037
2038 /**
2039 * Checks for interrupt, returning THROW_IE if interrupted
2040 * before signalled, REINTERRUPT if after signalled, or
2041 * 0 if not interrupted.
2042 */
2043 private int checkInterruptWhileWaiting(Node node) {
2044 return Thread.interrupted() ?
2045 (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
2046 0;
2047 }
2048
2049 /**
2050 * Throws InterruptedException, reinterrupts current thread, or
2051 * does nothing, depending on mode.
2052 */
2053 private void reportInterruptAfterWait(int interruptMode)
2054 throws InterruptedException {
2055 if (interruptMode == THROW_IE)
2056 throw new InterruptedException();
2057 else if (interruptMode == REINTERRUPT)
2058 selfInterrupt();
2059 }
2060
2061 /**
2062 * Implements interruptible condition wait.
2063 * <ol>
2064 * <li>If current thread is interrupted, throw InterruptedException.
2065 * <li>Save lock state returned by {@link #getState}.
2066 * <li>Invoke {@link #release} with saved state as argument,
2067 * throwing IllegalMonitorStateException if it fails.
2068 * <li>Block until signalled or interrupted.
2069 * <li>Reacquire by invoking specialized version of
2070 * {@link #acquire} with saved state as argument.
2071 * <li>If interrupted while blocked in step 4, throw InterruptedException.
2072 * </ol>
2073 */
2074 public final void await() throws InterruptedException {
2075 if (Thread.interrupted())
2076 throw new InterruptedException();
2077 Node node = addConditionWaiter();
2078 int savedState = fullyRelease(node);
2079 int interruptMode = 0;
2080 while (!isOnSyncQueue(node)) {
2081 LockSupport.park(this);
2082 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
2083 break;
2084 }
2085 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
2086 interruptMode = REINTERRUPT;
2087 if (node.nextWaiter != null) // clean up if cancelled
2088 unlinkCancelledWaiters();
2089 if (interruptMode != 0)
2090 reportInterruptAfterWait(interruptMode);
2091 }
2092
2093 /**
2094 * Implements timed condition wait.
2095 * <ol>
2096 * <li>If current thread is interrupted, throw InterruptedException.
2097 * <li>Save lock state returned by {@link #getState}.
2098 * <li>Invoke {@link #release} with saved state as argument,
2099 * throwing IllegalMonitorStateException if it fails.
2100 * <li>Block until signalled, interrupted, or timed out.
2101 * <li>Reacquire by invoking specialized version of
2102 * {@link #acquire} with saved state as argument.
2103 * <li>If interrupted while blocked in step 4, throw InterruptedException.
2104 * </ol>
2105 */
2106 public final long awaitNanos(long nanosTimeout)
2107 throws InterruptedException {
2108 if (Thread.interrupted())
2109 throw new InterruptedException();
2110 // We don't check for nanosTimeout <= 0L here, to allow
2111 // awaitNanos(0) as a way to "yield the lock".
2112 final long deadline = System.nanoTime() + nanosTimeout;
2113 long initialNanos = nanosTimeout;
2114 Node node = addConditionWaiter();
2115 int savedState = fullyRelease(node);
2116 int interruptMode = 0;
2117 while (!isOnSyncQueue(node)) {
2118 if (nanosTimeout <= 0L) {
2119 transferAfterCancelledWait(node);
2120 break;
2121 }
2122 if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
2123 LockSupport.parkNanos(this, nanosTimeout);
2124 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
2125 break;
2126 nanosTimeout = deadline - System.nanoTime();
2127 }
2128 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
2129 interruptMode = REINTERRUPT;
2130 if (node.nextWaiter != null)
2131 unlinkCancelledWaiters();
2132 if (interruptMode != 0)
2133 reportInterruptAfterWait(interruptMode);
2134 long remaining = deadline - System.nanoTime(); // avoid overflow
2135 return (remaining <= initialNanos) ? remaining : Long.MIN_VALUE;
2136 }
2137
2138 /**
2139 * Implements absolute timed condition wait.
2140 * <ol>
2141 * <li>If current thread is interrupted, throw InterruptedException.
2142 * <li>Save lock state returned by {@link #getState}.
2143 * <li>Invoke {@link #release} with saved state as argument,
2144 * throwing IllegalMonitorStateException if it fails.
2145 * <li>Block until signalled, interrupted, or timed out.
2146 * <li>Reacquire by invoking specialized version of
2147 * {@link #acquire} with saved state as argument.
2148 * <li>If interrupted while blocked in step 4, throw InterruptedException.
2149 * <li>If timed out while blocked in step 4, return false, else true.
2150 * </ol>
2151 */
2152 public final boolean awaitUntil(Date deadline)
2153 throws InterruptedException {
2154 long abstime = deadline.getTime();
2155 if (Thread.interrupted())
2156 throw new InterruptedException();
2157 Node node = addConditionWaiter();
2158 int savedState = fullyRelease(node);
2159 boolean timedout = false;
2160 int interruptMode = 0;
2161 while (!isOnSyncQueue(node)) {
2162 if (System.currentTimeMillis() >= abstime) {
2163 timedout = transferAfterCancelledWait(node);
2164 break;
2165 }
2166 LockSupport.parkUntil(this, abstime);
2167 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
2168 break;
2169 }
2170 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
2171 interruptMode = REINTERRUPT;
2172 if (node.nextWaiter != null)
2173 unlinkCancelledWaiters();
2174 if (interruptMode != 0)
2175 reportInterruptAfterWait(interruptMode);
2176 return !timedout;
2177 }
2178
2179 /**
2180 * Implements timed condition wait.
2181 * <ol>
2182 * <li>If current thread is interrupted, throw InterruptedException.
2183 * <li>Save lock state returned by {@link #getState}.
2184 * <li>Invoke {@link #release} with saved state as argument,
2185 * throwing IllegalMonitorStateException if it fails.
2186 * <li>Block until signalled, interrupted, or timed out.
2187 * <li>Reacquire by invoking specialized version of
2188 * {@link #acquire} with saved state as argument.
2189 * <li>If interrupted while blocked in step 4, throw InterruptedException.
2190 * <li>If timed out while blocked in step 4, return false, else true.
2191 * </ol>
2192 */
2193 public final boolean await(long time, TimeUnit unit)
2194 throws InterruptedException {
2195 long nanosTimeout = unit.toNanos(time);
2196 if (Thread.interrupted())
2197 throw new InterruptedException();
2198 // We don't check for nanosTimeout <= 0L here, to allow
2199 // await(0, unit) as a way to "yield the lock".
2200 final long deadline = System.nanoTime() + nanosTimeout;
2201 Node node = addConditionWaiter();
2202 int savedState = fullyRelease(node);
2203 boolean timedout = false;
2204 int interruptMode = 0;
2205 while (!isOnSyncQueue(node)) {
2206 if (nanosTimeout <= 0L) {
2207 timedout = transferAfterCancelledWait(node);
2208 break;
2209 }
2210 if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
2211 LockSupport.parkNanos(this, nanosTimeout);
2212 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
2213 break;
2214 nanosTimeout = deadline - System.nanoTime();
2215 }
2216 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
2217 interruptMode = REINTERRUPT;
2218 if (node.nextWaiter != null)
2219 unlinkCancelledWaiters();
2220 if (interruptMode != 0)
2221 reportInterruptAfterWait(interruptMode);
2222 return !timedout;
2223 }
2224
2225 // support for instrumentation
2226
2227 /**
2228 * Returns true if this condition was created by the given
2229 * synchronization object.
2230 *
2231 * @return {@code true} if owned
2232 */
2233 final boolean isOwnedBy(AbstractQueuedSynchronizer sync) {
2234 return sync == AbstractQueuedSynchronizer.this;
2235 }
2236
2237 /**
2238 * Queries whether any threads are waiting on this condition.
2239 * Implements {@link AbstractQueuedSynchronizer#hasWaiters(ConditionObject)}.
2240 *
2241 * @return {@code true} if there are any waiting threads
2242 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2243 * returns {@code false}
2244 */
2245 protected final boolean hasWaiters() {
2246 if (!isHeldExclusively())
2247 throw new IllegalMonitorStateException();
2248 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2249 if (w.waitStatus == Node.CONDITION)
2250 return true;
2251 }
2252 return false;
2253 }
2254
2255 /**
2256 * Returns an estimate of the number of threads waiting on
2257 * this condition.
2258 * Implements {@link AbstractQueuedSynchronizer#getWaitQueueLength(ConditionObject)}.
2259 *
2260 * @return the estimated number of waiting threads
2261 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2262 * returns {@code false}
2263 */
2264 protected final int getWaitQueueLength() {
2265 if (!isHeldExclusively())
2266 throw new IllegalMonitorStateException();
2267 int n = 0;
2268 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2269 if (w.waitStatus == Node.CONDITION)
2270 ++n;
2271 }
2272 return n;
2273 }
2274
2275 /**
2276 * Returns a collection containing those threads that may be
2277 * waiting on this Condition.
2278 * Implements {@link AbstractQueuedSynchronizer#getWaitingThreads(ConditionObject)}.
2279 *
2280 * @return the collection of threads
2281 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2282 * returns {@code false}
2283 */
2284 protected final Collection<Thread> getWaitingThreads() {
2285 if (!isHeldExclusively())
2286 throw new IllegalMonitorStateException();
2287 ArrayList<Thread> list = new ArrayList<>();
2288 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2289 if (w.waitStatus == Node.CONDITION) {
2290 Thread t = w.thread;
2291 if (t != null)
2292 list.add(t);
2293 }
2294 }
2295 return list;
2296 }
2297 }
2298
2299 // VarHandle mechanics
2300 private static final VarHandle STATE;
2301 private static final VarHandle HEAD;
2302 private static final VarHandle TAIL;
2303
2304 static {
2305 try {
2306 MethodHandles.Lookup l = MethodHandles.lookup();
2307 STATE = l.findVarHandle(AbstractQueuedSynchronizer.class, "state", int.class);
2308 HEAD = l.findVarHandle(AbstractQueuedSynchronizer.class, "head", Node.class);
2309 TAIL = l.findVarHandle(AbstractQueuedSynchronizer.class, "tail", Node.class);
2310 } catch (ReflectiveOperationException e) {
2311 throw new ExceptionInInitializerError(e);
2312 }
2313
2314 // Reduce the risk of rare disastrous classloading in first call to
2315 // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
2316 Class<?> ensureLoaded = LockSupport.class;
2317 }
2318
2319 /**
2320 * Initializes head and tail fields on first contention.
2321 */
2322 private final void initializeSyncQueue() {
2323 Node h;
2324 if (HEAD.compareAndSet(this, null, (h = new Node())))
2325 tail = h;
2326 }
2327
2328 /**
2329 * CASes tail field.
2330 */
2331 private final boolean compareAndSetTail(Node expect, Node update) {
2332 return TAIL.compareAndSet(this, expect, update);
2333 }
2334 }
2335