rt/emul/compact/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
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.
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).
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.
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
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
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/
36 package java.util.concurrent.locks;
38 import java.util.concurrent.*;
39 import java.util.concurrent.atomic.*;
40 import sun.misc.Unsafe;
43 * A version of {@link AbstractQueuedSynchronizer} in
44 * which synchronization state is maintained as a <tt>long</tt>.
45 * This class has exactly the same structure, properties, and methods
46 * as <tt>AbstractQueuedSynchronizer</tt> with the exception
47 * that all state-related parameters and results are defined
48 * as <tt>long</tt> rather than <tt>int</tt>. This class
49 * may be useful when creating synchronizers such as
50 * multilevel locks and barriers that require
53 * <p>See {@link AbstractQueuedSynchronizer} for usage
59 public abstract class AbstractQueuedLongSynchronizer
60 extends AbstractOwnableSynchronizer
61 implements java.io.Serializable {
63 private static final long serialVersionUID = 7373984972572414692L;
66 To keep sources in sync, the remainder of this source file is
67 exactly cloned from AbstractQueuedSynchronizer, replacing class
68 name and changing ints related with sync state to longs. Please
73 * Creates a new <tt>AbstractQueuedLongSynchronizer</tt> instance
74 * with initial synchronization state of zero.
76 protected AbstractQueuedLongSynchronizer() { }
79 * Wait queue node class.
81 * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
82 * Hagersten) lock queue. CLH locks are normally used for
83 * spinlocks. We instead use them for blocking synchronizers, but
84 * use the same basic tactic of holding some of the control
85 * information about a thread in the predecessor of its node. A
86 * "status" field in each node keeps track of whether a thread
87 * should block. A node is signalled when its predecessor
88 * releases. Each node of the queue otherwise serves as a
89 * specific-notification-style monitor holding a single waiting
90 * thread. The status field does NOT control whether threads are
91 * granted locks etc though. A thread may try to acquire if it is
92 * first in the queue. But being first does not guarantee success;
93 * it only gives the right to contend. So the currently released
94 * contender thread may need to rewait.
96 * <p>To enqueue into a CLH lock, you atomically splice it in as new
97 * tail. To dequeue, you just set the head field.
99 * +------+ prev +-----+ +-----+
100 * head | | <---- | | <---- | | tail
101 * +------+ +-----+ +-----+
104 * <p>Insertion into a CLH queue requires only a single atomic
105 * operation on "tail", so there is a simple atomic point of
106 * demarcation from unqueued to queued. Similarly, dequeing
107 * involves only updating the "head". However, it takes a bit
108 * more work for nodes to determine who their successors are,
109 * in part to deal with possible cancellation due to timeouts
112 * <p>The "prev" links (not used in original CLH locks), are mainly
113 * needed to handle cancellation. If a node is cancelled, its
114 * successor is (normally) relinked to a non-cancelled
115 * predecessor. For explanation of similar mechanics in the case
116 * of spin locks, see the papers by Scott and Scherer at
117 * http://www.cs.rochester.edu/u/scott/synchronization/
119 * <p>We also use "next" links to implement blocking mechanics.
120 * The thread id for each node is kept in its own node, so a
121 * predecessor signals the next node to wake up by traversing
122 * next link to determine which thread it is. Determination of
123 * successor must avoid races with newly queued nodes to set
124 * the "next" fields of their predecessors. This is solved
125 * when necessary by checking backwards from the atomically
126 * updated "tail" when a node's successor appears to be null.
127 * (Or, said differently, the next-links are an optimization
128 * so that we don't usually need a backward scan.)
130 * <p>Cancellation introduces some conservatism to the basic
131 * algorithms. Since we must poll for cancellation of other
132 * nodes, we can miss noticing whether a cancelled node is
133 * ahead or behind us. This is dealt with by always unparking
134 * successors upon cancellation, allowing them to stabilize on
135 * a new predecessor, unless we can identify an uncancelled
136 * predecessor who will carry this responsibility.
138 * <p>CLH queues need a dummy header node to get started. But
139 * we don't create them on construction, because it would be wasted
140 * effort if there is never contention. Instead, the node
141 * is constructed and head and tail pointers are set upon first
144 * <p>Threads waiting on Conditions use the same nodes, but
145 * use an additional link. Conditions only need to link nodes
146 * in simple (non-concurrent) linked queues because they are
147 * only accessed when exclusively held. Upon await, a node is
148 * inserted into a condition queue. Upon signal, the node is
149 * transferred to the main queue. A special value of status
150 * field is used to mark which queue a node is on.
152 * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
153 * Scherer and Michael Scott, along with members of JSR-166
154 * expert group, for helpful ideas, discussions, and critiques
155 * on the design of this class.
157 static final class Node {
158 /** Marker to indicate a node is waiting in shared mode */
159 static final Node SHARED = new Node();
160 /** Marker to indicate a node is waiting in exclusive mode */
161 static final Node EXCLUSIVE = null;
163 /** waitStatus value to indicate thread has cancelled */
164 static final int CANCELLED = 1;
165 /** waitStatus value to indicate successor's thread needs unparking */
166 static final int SIGNAL = -1;
167 /** waitStatus value to indicate thread is waiting on condition */
168 static final int CONDITION = -2;
170 * waitStatus value to indicate the next acquireShared should
171 * unconditionally propagate
173 static final int PROPAGATE = -3;
176 * Status field, taking on only the values:
177 * SIGNAL: The successor of this node is (or will soon be)
178 * blocked (via park), so the current node must
179 * unpark its successor when it releases or
180 * cancels. To avoid races, acquire methods must
181 * first indicate they need a signal,
182 * then retry the atomic acquire, and then,
184 * CANCELLED: This node is cancelled due to timeout or interrupt.
185 * Nodes never leave this state. In particular,
186 * a thread with cancelled node never again blocks.
187 * CONDITION: This node is currently on a condition queue.
188 * It will not be used as a sync queue node
189 * until transferred, at which time the status
190 * will be set to 0. (Use of this value here has
191 * nothing to do with the other uses of the
192 * field, but simplifies mechanics.)
193 * PROPAGATE: A releaseShared should be propagated to other
194 * nodes. This is set (for head node only) in
195 * doReleaseShared to ensure propagation
196 * continues, even if other operations have
198 * 0: None of the above
200 * The values are arranged numerically to simplify use.
201 * Non-negative values mean that a node doesn't need to
202 * signal. So, most code doesn't need to check for particular
203 * values, just for sign.
205 * The field is initialized to 0 for normal sync nodes, and
206 * CONDITION for condition nodes. It is modified using CAS
207 * (or when possible, unconditional volatile writes).
209 volatile int waitStatus;
212 * Link to predecessor node that current node/thread relies on
213 * for checking waitStatus. Assigned during enqueing, and nulled
214 * out (for sake of GC) only upon dequeuing. Also, upon
215 * cancellation of a predecessor, we short-circuit while
216 * finding a non-cancelled one, which will always exist
217 * because the head node is never cancelled: A node becomes
218 * head only as a result of successful acquire. A
219 * cancelled thread never succeeds in acquiring, and a thread only
220 * cancels itself, not any other node.
225 * Link to the successor node that the current node/thread
226 * unparks upon release. Assigned during enqueuing, adjusted
227 * when bypassing cancelled predecessors, and nulled out (for
228 * sake of GC) when dequeued. The enq operation does not
229 * assign next field of a predecessor until after attachment,
230 * so seeing a null next field does not necessarily mean that
231 * node is at end of queue. However, if a next field appears
232 * to be null, we can scan prev's from the tail to
233 * double-check. The next field of cancelled nodes is set to
234 * point to the node itself instead of null, to make life
235 * easier for isOnSyncQueue.
240 * The thread that enqueued this node. Initialized on
241 * construction and nulled out after use.
243 volatile Thread thread;
246 * Link to next node waiting on condition, or the special
247 * value SHARED. Because condition queues are accessed only
248 * when holding in exclusive mode, we just need a simple
249 * linked queue to hold nodes while they are waiting on
250 * conditions. They are then transferred to the queue to
251 * re-acquire. And because conditions can only be exclusive,
252 * we save a field by using special value to indicate shared
258 * Returns true if node is waiting in shared mode
260 final boolean isShared() {
261 return nextWaiter == SHARED;
265 * Returns previous node, or throws NullPointerException if null.
266 * Use when predecessor cannot be null. The null check could
267 * be elided, but is present to help the VM.
269 * @return the predecessor of this node
271 final Node predecessor() throws NullPointerException {
274 throw new NullPointerException();
279 Node() { // Used to establish initial head or SHARED marker
282 Node(Thread thread, Node mode) { // Used by addWaiter
283 this.nextWaiter = mode;
284 this.thread = thread;
287 Node(Thread thread, int waitStatus) { // Used by Condition
288 this.waitStatus = waitStatus;
289 this.thread = thread;
294 * Head of the wait queue, lazily initialized. Except for
295 * initialization, it is modified only via method setHead. Note:
296 * If head exists, its waitStatus is guaranteed not to be
299 private transient volatile Node head;
302 * Tail of the wait queue, lazily initialized. Modified only via
303 * method enq to add new wait node.
305 private transient volatile Node tail;
308 * The synchronization state.
310 private volatile long state;
313 * Returns the current value of synchronization state.
314 * This operation has memory semantics of a <tt>volatile</tt> read.
315 * @return current state value
317 protected final long getState() {
322 * Sets the value of synchronization state.
323 * This operation has memory semantics of a <tt>volatile</tt> write.
324 * @param newState the new state value
326 protected final void setState(long newState) {
331 * Atomically sets synchronization state to the given updated
332 * value if the current state value equals the expected value.
333 * This operation has memory semantics of a <tt>volatile</tt> read
336 * @param expect the expected value
337 * @param update the new value
338 * @return true if successful. False return indicates that the actual
339 * value was not equal to the expected value.
341 protected final boolean compareAndSetState(long expect, long update) {
342 // See below for intrinsics setup to support this
343 return unsafe.compareAndSwapLong(this, stateOffset, expect, update);
349 * The number of nanoseconds for which it is faster to spin
350 * rather than to use timed park. A rough estimate suffices
351 * to improve responsiveness with very short timeouts.
353 static final long spinForTimeoutThreshold = 1000L;
356 * Inserts node into queue, initializing if necessary. See picture above.
357 * @param node the node to insert
358 * @return node's predecessor
360 private Node enq(final Node node) {
363 if (t == null) { // Must initialize
364 if (compareAndSetHead(new Node()))
368 if (compareAndSetTail(t, node)) {
377 * Creates and enqueues node for current thread and given mode.
379 * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
380 * @return the new node
382 private Node addWaiter(Node mode) {
383 Node node = new Node(Thread.currentThread(), mode);
384 // Try the fast path of enq; backup to full enq on failure
388 if (compareAndSetTail(pred, node)) {
398 * Sets head of queue to be node, thus dequeuing. Called only by
399 * acquire methods. Also nulls out unused fields for sake of GC
400 * and to suppress unnecessary signals and traversals.
402 * @param node the node
404 private void setHead(Node node) {
411 * Wakes up node's successor, if one exists.
413 * @param node the node
415 private void unparkSuccessor(Node node) {
417 * If status is negative (i.e., possibly needing signal) try
418 * to clear in anticipation of signalling. It is OK if this
419 * fails or if status is changed by waiting thread.
421 int ws = node.waitStatus;
423 compareAndSetWaitStatus(node, ws, 0);
426 * Thread to unpark is held in successor, which is normally
427 * just the next node. But if cancelled or apparently null,
428 * traverse backwards from tail to find the actual
429 * non-cancelled successor.
432 if (s == null || s.waitStatus > 0) {
434 for (Node t = tail; t != null && t != node; t = t.prev)
435 if (t.waitStatus <= 0)
439 LockSupport.unpark(s.thread);
443 * Release action for shared mode -- signal successor and ensure
444 * propagation. (Note: For exclusive mode, release just amounts
445 * to calling unparkSuccessor of head if it needs signal.)
447 private void doReleaseShared() {
449 * Ensure that a release propagates, even if there are other
450 * in-progress acquires/releases. This proceeds in the usual
451 * way of trying to unparkSuccessor of head if it needs
452 * signal. But if it does not, status is set to PROPAGATE to
453 * ensure that upon release, propagation continues.
454 * Additionally, we must loop in case a new node is added
455 * while we are doing this. Also, unlike other uses of
456 * unparkSuccessor, we need to know if CAS to reset status
457 * fails, if so rechecking.
461 if (h != null && h != tail) {
462 int ws = h.waitStatus;
463 if (ws == Node.SIGNAL) {
464 if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
465 continue; // loop to recheck cases
469 !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
470 continue; // loop on failed CAS
472 if (h == head) // loop if head changed
478 * Sets head of queue, and checks if successor may be waiting
479 * in shared mode, if so propagating if either propagate > 0 or
480 * PROPAGATE status was set.
482 * @param node the node
483 * @param propagate the return value from a tryAcquireShared
485 private void setHeadAndPropagate(Node node, long propagate) {
486 Node h = head; // Record old head for check below
489 * Try to signal next queued node if:
490 * Propagation was indicated by caller,
491 * or was recorded (as h.waitStatus) by a previous operation
492 * (note: this uses sign-check of waitStatus because
493 * PROPAGATE status may transition to SIGNAL.)
495 * The next node is waiting in shared mode,
496 * or we don't know, because it appears null
498 * The conservatism in both of these checks may cause
499 * unnecessary wake-ups, but only when there are multiple
500 * racing acquires/releases, so most need signals now or soon
503 if (propagate > 0 || h == null || h.waitStatus < 0) {
505 if (s == null || s.isShared())
510 // Utilities for various versions of acquire
513 * Cancels an ongoing attempt to acquire.
515 * @param node the node
517 private void cancelAcquire(Node node) {
518 // Ignore if node doesn't exist
524 // Skip cancelled predecessors
525 Node pred = node.prev;
526 while (pred.waitStatus > 0)
527 node.prev = pred = pred.prev;
529 // predNext is the apparent node to unsplice. CASes below will
530 // fail if not, in which case, we lost race vs another cancel
531 // or signal, so no further action is necessary.
532 Node predNext = pred.next;
534 // Can use unconditional write instead of CAS here.
535 // After this atomic step, other Nodes can skip past us.
536 // Before, we are free of interference from other threads.
537 node.waitStatus = Node.CANCELLED;
539 // If we are the tail, remove ourselves.
540 if (node == tail && compareAndSetTail(node, pred)) {
541 compareAndSetNext(pred, predNext, null);
543 // If successor needs signal, try to set pred's next-link
544 // so it will get one. Otherwise wake it up to propagate.
547 ((ws = pred.waitStatus) == Node.SIGNAL ||
548 (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
549 pred.thread != null) {
550 Node next = node.next;
551 if (next != null && next.waitStatus <= 0)
552 compareAndSetNext(pred, predNext, next);
554 unparkSuccessor(node);
557 node.next = node; // help GC
562 * Checks and updates status for a node that failed to acquire.
563 * Returns true if thread should block. This is the main signal
564 * control in all acquire loops. Requires that pred == node.prev
566 * @param pred node's predecessor holding status
567 * @param node the node
568 * @return {@code true} if thread should block
570 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
571 int ws = pred.waitStatus;
572 if (ws == Node.SIGNAL)
574 * This node has already set status asking a release
575 * to signal it, so it can safely park.
580 * Predecessor was cancelled. Skip over predecessors and
584 node.prev = pred = pred.prev;
585 } while (pred.waitStatus > 0);
589 * waitStatus must be 0 or PROPAGATE. Indicate that we
590 * need a signal, but don't park yet. Caller will need to
591 * retry to make sure it cannot acquire before parking.
593 compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
599 * Convenience method to interrupt current thread.
601 private static void selfInterrupt() {
602 Thread.currentThread().interrupt();
606 * Convenience method to park and then check if interrupted
608 * @return {@code true} if interrupted
610 private final boolean parkAndCheckInterrupt() {
611 LockSupport.park(this);
612 return Thread.interrupted();
616 * Various flavors of acquire, varying in exclusive/shared and
617 * control modes. Each is mostly the same, but annoyingly
618 * different. Only a little bit of factoring is possible due to
619 * interactions of exception mechanics (including ensuring that we
620 * cancel if tryAcquire throws exception) and other control, at
621 * least not without hurting performance too much.
625 * Acquires in exclusive uninterruptible mode for thread already in
626 * queue. Used by condition wait methods as well as acquire.
628 * @param node the node
629 * @param arg the acquire argument
630 * @return {@code true} if interrupted while waiting
632 final boolean acquireQueued(final Node node, long arg) {
633 boolean failed = true;
635 boolean interrupted = false;
637 final Node p = node.predecessor();
638 if (p == head && tryAcquire(arg)) {
640 p.next = null; // help GC
644 if (shouldParkAfterFailedAcquire(p, node) &&
645 parkAndCheckInterrupt())
655 * Acquires in exclusive interruptible mode.
656 * @param arg the acquire argument
658 private void doAcquireInterruptibly(long arg)
659 throws InterruptedException {
660 final Node node = addWaiter(Node.EXCLUSIVE);
661 boolean failed = true;
664 final Node p = node.predecessor();
665 if (p == head && tryAcquire(arg)) {
667 p.next = null; // help GC
671 if (shouldParkAfterFailedAcquire(p, node) &&
672 parkAndCheckInterrupt())
673 throw new InterruptedException();
682 * Acquires in exclusive timed mode.
684 * @param arg the acquire argument
685 * @param nanosTimeout max wait time
686 * @return {@code true} if acquired
688 private boolean doAcquireNanos(long arg, long nanosTimeout)
689 throws InterruptedException {
690 long lastTime = System.nanoTime();
691 final Node node = addWaiter(Node.EXCLUSIVE);
692 boolean failed = true;
695 final Node p = node.predecessor();
696 if (p == head && tryAcquire(arg)) {
698 p.next = null; // help GC
702 if (nanosTimeout <= 0)
704 if (shouldParkAfterFailedAcquire(p, node) &&
705 nanosTimeout > spinForTimeoutThreshold)
706 LockSupport.parkNanos(this, nanosTimeout);
707 long now = System.nanoTime();
708 nanosTimeout -= now - lastTime;
710 if (Thread.interrupted())
711 throw new InterruptedException();
720 * Acquires in shared uninterruptible mode.
721 * @param arg the acquire argument
723 private void doAcquireShared(long arg) {
724 final Node node = addWaiter(Node.SHARED);
725 boolean failed = true;
727 boolean interrupted = false;
729 final Node p = node.predecessor();
731 long r = tryAcquireShared(arg);
733 setHeadAndPropagate(node, r);
734 p.next = null; // help GC
741 if (shouldParkAfterFailedAcquire(p, node) &&
742 parkAndCheckInterrupt())
752 * Acquires in shared interruptible mode.
753 * @param arg the acquire argument
755 private void doAcquireSharedInterruptibly(long arg)
756 throws InterruptedException {
757 final Node node = addWaiter(Node.SHARED);
758 boolean failed = true;
761 final Node p = node.predecessor();
763 long r = tryAcquireShared(arg);
765 setHeadAndPropagate(node, r);
766 p.next = null; // help GC
771 if (shouldParkAfterFailedAcquire(p, node) &&
772 parkAndCheckInterrupt())
773 throw new InterruptedException();
782 * Acquires in shared timed mode.
784 * @param arg the acquire argument
785 * @param nanosTimeout max wait time
786 * @return {@code true} if acquired
788 private boolean doAcquireSharedNanos(long arg, long nanosTimeout)
789 throws InterruptedException {
791 long lastTime = System.nanoTime();
792 final Node node = addWaiter(Node.SHARED);
793 boolean failed = true;
796 final Node p = node.predecessor();
798 long r = tryAcquireShared(arg);
800 setHeadAndPropagate(node, r);
801 p.next = null; // help GC
806 if (nanosTimeout <= 0)
808 if (shouldParkAfterFailedAcquire(p, node) &&
809 nanosTimeout > spinForTimeoutThreshold)
810 LockSupport.parkNanos(this, nanosTimeout);
811 long now = System.nanoTime();
812 nanosTimeout -= now - lastTime;
814 if (Thread.interrupted())
815 throw new InterruptedException();
823 // Main exported methods
826 * Attempts to acquire in exclusive mode. This method should query
827 * if the state of the object permits it to be acquired in the
828 * exclusive mode, and if so to acquire it.
830 * <p>This method is always invoked by the thread performing
831 * acquire. If this method reports failure, the acquire method
832 * may queue the thread, if it is not already queued, until it is
833 * signalled by a release from some other thread. This can be used
834 * to implement method {@link Lock#tryLock()}.
837 * implementation throws {@link UnsupportedOperationException}.
839 * @param arg the acquire argument. This value is always the one
840 * passed to an acquire method, or is the value saved on entry
841 * to a condition wait. The value is otherwise uninterpreted
842 * and can represent anything you like.
843 * @return {@code true} if successful. Upon success, this object has
845 * @throws IllegalMonitorStateException if acquiring would place this
846 * synchronizer in an illegal state. This exception must be
847 * thrown in a consistent fashion for synchronization to work
849 * @throws UnsupportedOperationException if exclusive mode is not supported
851 protected boolean tryAcquire(long arg) {
852 throw new UnsupportedOperationException();
856 * Attempts to set the state to reflect a release in exclusive
859 * <p>This method is always invoked by the thread performing release.
861 * <p>The default implementation throws
862 * {@link UnsupportedOperationException}.
864 * @param arg the release argument. This value is always the one
865 * passed to a release method, or the current state value upon
866 * entry to a condition wait. The value is otherwise
867 * uninterpreted and can represent anything you like.
868 * @return {@code true} if this object is now in a fully released
869 * state, so that any waiting threads may attempt to acquire;
870 * and {@code false} otherwise.
871 * @throws IllegalMonitorStateException if releasing would place this
872 * synchronizer in an illegal state. This exception must be
873 * thrown in a consistent fashion for synchronization to work
875 * @throws UnsupportedOperationException if exclusive mode is not supported
877 protected boolean tryRelease(long arg) {
878 throw new UnsupportedOperationException();
882 * Attempts to acquire in shared mode. This method should query if
883 * the state of the object permits it to be acquired in the shared
884 * mode, and if so to acquire it.
886 * <p>This method is always invoked by the thread performing
887 * acquire. If this method reports failure, the acquire method
888 * may queue the thread, if it is not already queued, until it is
889 * signalled by a release from some other thread.
891 * <p>The default implementation throws {@link
892 * UnsupportedOperationException}.
894 * @param arg the acquire argument. This value is always the one
895 * passed to an acquire method, or is the value saved on entry
896 * to a condition wait. The value is otherwise uninterpreted
897 * and can represent anything you like.
898 * @return a negative value on failure; zero if acquisition in shared
899 * mode succeeded but no subsequent shared-mode acquire can
900 * succeed; and a positive value if acquisition in shared
901 * mode succeeded and subsequent shared-mode acquires might
902 * also succeed, in which case a subsequent waiting thread
903 * must check availability. (Support for three different
904 * return values enables this method to be used in contexts
905 * where acquires only sometimes act exclusively.) Upon
906 * success, this object has been acquired.
907 * @throws IllegalMonitorStateException if acquiring would place this
908 * synchronizer in an illegal state. This exception must be
909 * thrown in a consistent fashion for synchronization to work
911 * @throws UnsupportedOperationException if shared mode is not supported
913 protected long tryAcquireShared(long arg) {
914 throw new UnsupportedOperationException();
918 * Attempts to set the state to reflect a release in shared mode.
920 * <p>This method is always invoked by the thread performing release.
922 * <p>The default implementation throws
923 * {@link UnsupportedOperationException}.
925 * @param arg the release argument. This value is always the one
926 * passed to a release method, or the current state value upon
927 * entry to a condition wait. The value is otherwise
928 * uninterpreted and can represent anything you like.
929 * @return {@code true} if this release of shared mode may permit a
930 * waiting acquire (shared or exclusive) to succeed; and
931 * {@code false} otherwise
932 * @throws IllegalMonitorStateException if releasing would place this
933 * synchronizer in an illegal state. This exception must be
934 * thrown in a consistent fashion for synchronization to work
936 * @throws UnsupportedOperationException if shared mode is not supported
938 protected boolean tryReleaseShared(long arg) {
939 throw new UnsupportedOperationException();
943 * Returns {@code true} if synchronization is held exclusively with
944 * respect to the current (calling) thread. This method is invoked
945 * upon each call to a non-waiting {@link ConditionObject} method.
946 * (Waiting methods instead invoke {@link #release}.)
948 * <p>The default implementation throws {@link
949 * UnsupportedOperationException}. This method is invoked
950 * internally only within {@link ConditionObject} methods, so need
951 * not be defined if conditions are not used.
953 * @return {@code true} if synchronization is held exclusively;
954 * {@code false} otherwise
955 * @throws UnsupportedOperationException if conditions are not supported
957 protected boolean isHeldExclusively() {
958 throw new UnsupportedOperationException();
962 * Acquires in exclusive mode, ignoring interrupts. Implemented
963 * by invoking at least once {@link #tryAcquire},
964 * returning on success. Otherwise the thread is queued, possibly
965 * repeatedly blocking and unblocking, invoking {@link
966 * #tryAcquire} until success. This method can be used
967 * to implement method {@link Lock#lock}.
969 * @param arg the acquire argument. This value is conveyed to
970 * {@link #tryAcquire} but is otherwise uninterpreted and
971 * can represent anything you like.
973 public final void acquire(long arg) {
974 if (!tryAcquire(arg) &&
975 acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
980 * Acquires in exclusive mode, aborting if interrupted.
981 * Implemented by first checking interrupt status, then invoking
982 * at least once {@link #tryAcquire}, returning on
983 * success. Otherwise the thread is queued, possibly repeatedly
984 * blocking and unblocking, invoking {@link #tryAcquire}
985 * until success or the thread is interrupted. This method can be
986 * used to implement method {@link Lock#lockInterruptibly}.
988 * @param arg the acquire argument. This value is conveyed to
989 * {@link #tryAcquire} but is otherwise uninterpreted and
990 * can represent anything you like.
991 * @throws InterruptedException if the current thread is interrupted
993 public final void acquireInterruptibly(long arg)
994 throws InterruptedException {
995 if (Thread.interrupted())
996 throw new InterruptedException();
997 if (!tryAcquire(arg))
998 doAcquireInterruptibly(arg);
1002 * Attempts to acquire in exclusive mode, aborting if interrupted,
1003 * and failing if the given timeout elapses. Implemented by first
1004 * checking interrupt status, then invoking at least once {@link
1005 * #tryAcquire}, returning on success. Otherwise, the thread is
1006 * queued, possibly repeatedly blocking and unblocking, invoking
1007 * {@link #tryAcquire} until success or the thread is interrupted
1008 * or the timeout elapses. This method can be used to implement
1009 * method {@link Lock#tryLock(long, TimeUnit)}.
1011 * @param arg the acquire argument. This value is conveyed to
1012 * {@link #tryAcquire} but is otherwise uninterpreted and
1013 * can represent anything you like.
1014 * @param nanosTimeout the maximum number of nanoseconds to wait
1015 * @return {@code true} if acquired; {@code false} if timed out
1016 * @throws InterruptedException if the current thread is interrupted
1018 public final boolean tryAcquireNanos(long arg, long nanosTimeout)
1019 throws InterruptedException {
1020 if (Thread.interrupted())
1021 throw new InterruptedException();
1022 return tryAcquire(arg) ||
1023 doAcquireNanos(arg, nanosTimeout);
1027 * Releases in exclusive mode. Implemented by unblocking one or
1028 * more threads if {@link #tryRelease} returns true.
1029 * This method can be used to implement method {@link Lock#unlock}.
1031 * @param arg the release argument. This value is conveyed to
1032 * {@link #tryRelease} but is otherwise uninterpreted and
1033 * can represent anything you like.
1034 * @return the value returned from {@link #tryRelease}
1036 public final boolean release(long arg) {
1037 if (tryRelease(arg)) {
1039 if (h != null && h.waitStatus != 0)
1047 * Acquires in shared mode, ignoring interrupts. Implemented by
1048 * first invoking at least once {@link #tryAcquireShared},
1049 * returning on success. Otherwise the thread is queued, possibly
1050 * repeatedly blocking and unblocking, invoking {@link
1051 * #tryAcquireShared} until success.
1053 * @param arg the acquire argument. This value is conveyed to
1054 * {@link #tryAcquireShared} but is otherwise uninterpreted
1055 * and can represent anything you like.
1057 public final void acquireShared(long arg) {
1058 if (tryAcquireShared(arg) < 0)
1059 doAcquireShared(arg);
1063 * Acquires in shared mode, aborting if interrupted. Implemented
1064 * by first checking interrupt status, then invoking at least once
1065 * {@link #tryAcquireShared}, returning on success. Otherwise the
1066 * thread is queued, possibly repeatedly blocking and unblocking,
1067 * invoking {@link #tryAcquireShared} until success or the thread
1069 * @param arg the acquire argument
1070 * This value is conveyed to {@link #tryAcquireShared} but is
1071 * otherwise uninterpreted and can represent anything
1073 * @throws InterruptedException if the current thread is interrupted
1075 public final void acquireSharedInterruptibly(long arg)
1076 throws InterruptedException {
1077 if (Thread.interrupted())
1078 throw new InterruptedException();
1079 if (tryAcquireShared(arg) < 0)
1080 doAcquireSharedInterruptibly(arg);
1084 * Attempts to acquire in shared mode, aborting if interrupted, and
1085 * failing if the given timeout elapses. Implemented by first
1086 * checking interrupt status, then invoking at least once {@link
1087 * #tryAcquireShared}, returning on success. Otherwise, the
1088 * thread is queued, possibly repeatedly blocking and unblocking,
1089 * invoking {@link #tryAcquireShared} until success or the thread
1090 * is interrupted or the timeout elapses.
1092 * @param arg the acquire argument. This value is conveyed to
1093 * {@link #tryAcquireShared} but is otherwise uninterpreted
1094 * and can represent anything you like.
1095 * @param nanosTimeout the maximum number of nanoseconds to wait
1096 * @return {@code true} if acquired; {@code false} if timed out
1097 * @throws InterruptedException if the current thread is interrupted
1099 public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout)
1100 throws InterruptedException {
1101 if (Thread.interrupted())
1102 throw new InterruptedException();
1103 return tryAcquireShared(arg) >= 0 ||
1104 doAcquireSharedNanos(arg, nanosTimeout);
1108 * Releases in shared mode. Implemented by unblocking one or more
1109 * threads if {@link #tryReleaseShared} returns true.
1111 * @param arg the release argument. This value is conveyed to
1112 * {@link #tryReleaseShared} but is otherwise uninterpreted
1113 * and can represent anything you like.
1114 * @return the value returned from {@link #tryReleaseShared}
1116 public final boolean releaseShared(long arg) {
1117 if (tryReleaseShared(arg)) {
1124 // Queue inspection methods
1127 * Queries whether any threads are waiting to acquire. Note that
1128 * because cancellations due to interrupts and timeouts may occur
1129 * at any time, a {@code true} return does not guarantee that any
1130 * other thread will ever acquire.
1132 * <p>In this implementation, this operation returns in
1135 * @return {@code true} if there may be other threads waiting to acquire
1137 public final boolean hasQueuedThreads() {
1138 return head != tail;
1142 * Queries whether any threads have ever contended to acquire this
1143 * synchronizer; that is if an acquire method has ever blocked.
1145 * <p>In this implementation, this operation returns in
1148 * @return {@code true} if there has ever been contention
1150 public final boolean hasContended() {
1151 return head != null;
1155 * Returns the first (longest-waiting) thread in the queue, or
1156 * {@code null} if no threads are currently queued.
1158 * <p>In this implementation, this operation normally returns in
1159 * constant time, but may iterate upon contention if other threads are
1160 * concurrently modifying the queue.
1162 * @return the first (longest-waiting) thread in the queue, or
1163 * {@code null} if no threads are currently queued
1165 public final Thread getFirstQueuedThread() {
1166 // handle only fast path, else relay
1167 return (head == tail) ? null : fullGetFirstQueuedThread();
1171 * Version of getFirstQueuedThread called when fastpath fails
1173 private Thread fullGetFirstQueuedThread() {
1175 * The first node is normally head.next. Try to get its
1176 * thread field, ensuring consistent reads: If thread
1177 * field is nulled out or s.prev is no longer head, then
1178 * some other thread(s) concurrently performed setHead in
1179 * between some of our reads. We try this twice before
1180 * resorting to traversal.
1184 if (((h = head) != null && (s = h.next) != null &&
1185 s.prev == head && (st = s.thread) != null) ||
1186 ((h = head) != null && (s = h.next) != null &&
1187 s.prev == head && (st = s.thread) != null))
1191 * Head's next field might not have been set yet, or may have
1192 * been unset after setHead. So we must check to see if tail
1193 * is actually first node. If not, we continue on, safely
1194 * traversing from tail back to head to find first,
1195 * guaranteeing termination.
1199 Thread firstThread = null;
1200 while (t != null && t != head) {
1201 Thread tt = t.thread;
1210 * Returns true if the given thread is currently queued.
1212 * <p>This implementation traverses the queue to determine
1213 * presence of the given thread.
1215 * @param thread the thread
1216 * @return {@code true} if the given thread is on the queue
1217 * @throws NullPointerException if the thread is null
1219 public final boolean isQueued(Thread thread) {
1221 throw new NullPointerException();
1222 for (Node p = tail; p != null; p = p.prev)
1223 if (p.thread == thread)
1229 * Returns {@code true} if the apparent first queued thread, if one
1230 * exists, is waiting in exclusive mode. If this method returns
1231 * {@code true}, and the current thread is attempting to acquire in
1232 * shared mode (that is, this method is invoked from {@link
1233 * #tryAcquireShared}) then it is guaranteed that the current thread
1234 * is not the first queued thread. Used only as a heuristic in
1235 * ReentrantReadWriteLock.
1237 final boolean apparentlyFirstQueuedIsExclusive() {
1239 return (h = head) != null &&
1240 (s = h.next) != null &&
1246 * Queries whether any threads have been waiting to acquire longer
1247 * than the current thread.
1249 * <p>An invocation of this method is equivalent to (but may be
1250 * more efficient than):
1252 * getFirstQueuedThread() != Thread.currentThread() &&
1253 * hasQueuedThreads()}</pre>
1255 * <p>Note that because cancellations due to interrupts and
1256 * timeouts may occur at any time, a {@code true} return does not
1257 * guarantee that some other thread will acquire before the current
1258 * thread. Likewise, it is possible for another thread to win a
1259 * race to enqueue after this method has returned {@code false},
1260 * due to the queue being empty.
1262 * <p>This method is designed to be used by a fair synchronizer to
1263 * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>.
1264 * Such a synchronizer's {@link #tryAcquire} method should return
1265 * {@code false}, and its {@link #tryAcquireShared} method should
1266 * return a negative value, if this method returns {@code true}
1267 * (unless this is a reentrant acquire). For example, the {@code
1268 * tryAcquire} method for a fair, reentrant, exclusive mode
1269 * synchronizer might look like this:
1272 * protected boolean tryAcquire(int arg) {
1273 * if (isHeldExclusively()) {
1274 * // A reentrant acquire; increment hold count
1276 * } else if (hasQueuedPredecessors()) {
1279 * // try to acquire normally
1283 * @return {@code true} if there is a queued thread preceding the
1284 * current thread, and {@code false} if the current thread
1285 * is at the head of the queue or the queue is empty
1288 public final boolean hasQueuedPredecessors() {
1289 // The correctness of this depends on head being initialized
1290 // before tail and on head.next being accurate if the current
1291 // thread is first in queue.
1292 Node t = tail; // Read fields in reverse initialization order
1296 ((s = h.next) == null || s.thread != Thread.currentThread());
1300 // Instrumentation and monitoring methods
1303 * Returns an estimate of the number of threads waiting to
1304 * acquire. The value is only an estimate because the number of
1305 * threads may change dynamically while this method traverses
1306 * internal data structures. This method is designed for use in
1307 * monitoring system state, not for synchronization
1310 * @return the estimated number of threads waiting to acquire
1312 public final int getQueueLength() {
1314 for (Node p = tail; p != null; p = p.prev) {
1315 if (p.thread != null)
1322 * Returns a collection containing threads that may be waiting to
1323 * acquire. Because the actual set of threads may change
1324 * dynamically while constructing this result, the returned
1325 * collection is only a best-effort estimate. The elements of the
1326 * returned collection are in no particular order. This method is
1327 * designed to facilitate construction of subclasses that provide
1328 * more extensive monitoring facilities.
1330 * @return the collection of threads
1332 public final Collection<Thread> getQueuedThreads() {
1333 ArrayList<Thread> list = new ArrayList<Thread>();
1334 for (Node p = tail; p != null; p = p.prev) {
1335 Thread t = p.thread;
1343 * Returns a collection containing threads that may be waiting to
1344 * acquire in exclusive mode. This has the same properties
1345 * as {@link #getQueuedThreads} except that it only returns
1346 * those threads waiting due to an exclusive acquire.
1348 * @return the collection of threads
1350 public final Collection<Thread> getExclusiveQueuedThreads() {
1351 ArrayList<Thread> list = new ArrayList<Thread>();
1352 for (Node p = tail; p != null; p = p.prev) {
1353 if (!p.isShared()) {
1354 Thread t = p.thread;
1363 * Returns a collection containing threads that may be waiting to
1364 * acquire in shared mode. This has the same properties
1365 * as {@link #getQueuedThreads} except that it only returns
1366 * those threads waiting due to a shared acquire.
1368 * @return the collection of threads
1370 public final Collection<Thread> getSharedQueuedThreads() {
1371 ArrayList<Thread> list = new ArrayList<Thread>();
1372 for (Node p = tail; p != null; p = p.prev) {
1374 Thread t = p.thread;
1383 * Returns a string identifying this synchronizer, as well as its state.
1384 * The state, in brackets, includes the String {@code "State ="}
1385 * followed by the current value of {@link #getState}, and either
1386 * {@code "nonempty"} or {@code "empty"} depending on whether the
1389 * @return a string identifying this synchronizer, as well as its state
1391 public String toString() {
1392 long s = getState();
1393 String q = hasQueuedThreads() ? "non" : "";
1394 return super.toString() +
1395 "[State = " + s + ", " + q + "empty queue]";
1399 // Internal support methods for Conditions
1402 * Returns true if a node, always one that was initially placed on
1403 * a condition queue, is now waiting to reacquire on sync queue.
1404 * @param node the node
1405 * @return true if is reacquiring
1407 final boolean isOnSyncQueue(Node node) {
1408 if (node.waitStatus == Node.CONDITION || node.prev == null)
1410 if (node.next != null) // If has successor, it must be on queue
1413 * node.prev can be non-null, but not yet on queue because
1414 * the CAS to place it on queue can fail. So we have to
1415 * traverse from tail to make sure it actually made it. It
1416 * will always be near the tail in calls to this method, and
1417 * unless the CAS failed (which is unlikely), it will be
1418 * there, so we hardly ever traverse much.
1420 return findNodeFromTail(node);
1424 * Returns true if node is on sync queue by searching backwards from tail.
1425 * Called only when needed by isOnSyncQueue.
1426 * @return true if present
1428 private boolean findNodeFromTail(Node node) {
1440 * Transfers a node from a condition queue onto sync queue.
1441 * Returns true if successful.
1442 * @param node the node
1443 * @return true if successfully transferred (else the node was
1444 * cancelled before signal).
1446 final boolean transferForSignal(Node node) {
1448 * If cannot change waitStatus, the node has been cancelled.
1450 if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
1454 * Splice onto queue and try to set waitStatus of predecessor to
1455 * indicate that thread is (probably) waiting. If cancelled or
1456 * attempt to set waitStatus fails, wake up to resync (in which
1457 * case the waitStatus can be transiently and harmlessly wrong).
1460 int ws = p.waitStatus;
1461 if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
1462 LockSupport.unpark(node.thread);
1467 * Transfers node, if necessary, to sync queue after a cancelled
1468 * wait. Returns true if thread was cancelled before being
1470 * @param current the waiting thread
1471 * @param node its node
1472 * @return true if cancelled before the node was signalled
1474 final boolean transferAfterCancelledWait(Node node) {
1475 if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
1480 * If we lost out to a signal(), then we can't proceed
1481 * until it finishes its enq(). Cancelling during an
1482 * incomplete transfer is both rare and transient, so just
1485 while (!isOnSyncQueue(node))
1491 * Invokes release with current state value; returns saved state.
1492 * Cancels node and throws exception on failure.
1493 * @param node the condition node for this wait
1494 * @return previous sync state
1496 final long fullyRelease(Node node) {
1497 boolean failed = true;
1499 long savedState = getState();
1500 if (release(savedState)) {
1504 throw new IllegalMonitorStateException();
1508 node.waitStatus = Node.CANCELLED;
1512 // Instrumentation methods for conditions
1515 * Queries whether the given ConditionObject
1516 * uses this synchronizer as its lock.
1518 * @param condition the condition
1519 * @return <tt>true</tt> if owned
1520 * @throws NullPointerException if the condition is null
1522 public final boolean owns(ConditionObject condition) {
1523 if (condition == null)
1524 throw new NullPointerException();
1525 return condition.isOwnedBy(this);
1529 * Queries whether any threads are waiting on the given condition
1530 * associated with this synchronizer. Note that because timeouts
1531 * and interrupts may occur at any time, a <tt>true</tt> return
1532 * does not guarantee that a future <tt>signal</tt> will awaken
1533 * any threads. This method is designed primarily for use in
1534 * monitoring of the system state.
1536 * @param condition the condition
1537 * @return <tt>true</tt> if there are any waiting threads
1538 * @throws IllegalMonitorStateException if exclusive synchronization
1540 * @throws IllegalArgumentException if the given condition is
1541 * not associated with this synchronizer
1542 * @throws NullPointerException if the condition is null
1544 public final boolean hasWaiters(ConditionObject condition) {
1545 if (!owns(condition))
1546 throw new IllegalArgumentException("Not owner");
1547 return condition.hasWaiters();
1551 * Returns an estimate of the number of threads waiting on the
1552 * given condition associated with this synchronizer. Note that
1553 * because timeouts and interrupts may occur at any time, the
1554 * estimate serves only as an upper bound on the actual number of
1555 * waiters. This method is designed for use in monitoring of the
1556 * system state, not for synchronization control.
1558 * @param condition the condition
1559 * @return the estimated number of waiting threads
1560 * @throws IllegalMonitorStateException if exclusive synchronization
1562 * @throws IllegalArgumentException if the given condition is
1563 * not associated with this synchronizer
1564 * @throws NullPointerException if the condition is null
1566 public final int getWaitQueueLength(ConditionObject condition) {
1567 if (!owns(condition))
1568 throw new IllegalArgumentException("Not owner");
1569 return condition.getWaitQueueLength();
1573 * Returns a collection containing those threads that may be
1574 * waiting on the given condition associated with this
1575 * synchronizer. Because the actual set of threads may change
1576 * dynamically while constructing this result, the returned
1577 * collection is only a best-effort estimate. The elements of the
1578 * returned collection are in no particular order.
1580 * @param condition the condition
1581 * @return the collection of threads
1582 * @throws IllegalMonitorStateException if exclusive synchronization
1584 * @throws IllegalArgumentException if the given condition is
1585 * not associated with this synchronizer
1586 * @throws NullPointerException if the condition is null
1588 public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1589 if (!owns(condition))
1590 throw new IllegalArgumentException("Not owner");
1591 return condition.getWaitingThreads();
1595 * Condition implementation for a {@link
1596 * AbstractQueuedLongSynchronizer} serving as the basis of a {@link
1597 * Lock} implementation.
1599 * <p>Method documentation for this class describes mechanics,
1600 * not behavioral specifications from the point of view of Lock
1601 * and Condition users. Exported versions of this class will in
1602 * general need to be accompanied by documentation describing
1603 * condition semantics that rely on those of the associated
1604 * <tt>AbstractQueuedLongSynchronizer</tt>.
1606 * <p>This class is Serializable, but all fields are transient,
1607 * so deserialized conditions have no waiters.
1611 public class ConditionObject implements Condition, java.io.Serializable {
1612 private static final long serialVersionUID = 1173984872572414699L;
1613 /** First node of condition queue. */
1614 private transient Node firstWaiter;
1615 /** Last node of condition queue. */
1616 private transient Node lastWaiter;
1619 * Creates a new <tt>ConditionObject</tt> instance.
1621 public ConditionObject() { }
1626 * Adds a new waiter to wait queue.
1627 * @return its new wait node
1629 private Node addConditionWaiter() {
1630 Node t = lastWaiter;
1631 // If lastWaiter is cancelled, clean out.
1632 if (t != null && t.waitStatus != Node.CONDITION) {
1633 unlinkCancelledWaiters();
1636 Node node = new Node(Thread.currentThread(), Node.CONDITION);
1640 t.nextWaiter = node;
1646 * Removes and transfers nodes until hit non-cancelled one or
1647 * null. Split out from signal in part to encourage compilers
1648 * to inline the case of no waiters.
1649 * @param first (non-null) the first node on condition queue
1651 private void doSignal(Node first) {
1653 if ( (firstWaiter = first.nextWaiter) == null)
1655 first.nextWaiter = null;
1656 } while (!transferForSignal(first) &&
1657 (first = firstWaiter) != null);
1661 * Removes and transfers all nodes.
1662 * @param first (non-null) the first node on condition queue
1664 private void doSignalAll(Node first) {
1665 lastWaiter = firstWaiter = null;
1667 Node next = first.nextWaiter;
1668 first.nextWaiter = null;
1669 transferForSignal(first);
1671 } while (first != null);
1675 * Unlinks cancelled waiter nodes from condition queue.
1676 * Called only while holding lock. This is called when
1677 * cancellation occurred during condition wait, and upon
1678 * insertion of a new waiter when lastWaiter is seen to have
1679 * been cancelled. This method is needed to avoid garbage
1680 * retention in the absence of signals. So even though it may
1681 * require a full traversal, it comes into play only when
1682 * timeouts or cancellations occur in the absence of
1683 * signals. It traverses all nodes rather than stopping at a
1684 * particular target to unlink all pointers to garbage nodes
1685 * without requiring many re-traversals during cancellation
1688 private void unlinkCancelledWaiters() {
1689 Node t = firstWaiter;
1692 Node next = t.nextWaiter;
1693 if (t.waitStatus != Node.CONDITION) {
1694 t.nextWaiter = null;
1698 trail.nextWaiter = next;
1711 * Moves the longest-waiting thread, if one exists, from the
1712 * wait queue for this condition to the wait queue for the
1715 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1716 * returns {@code false}
1718 public final void signal() {
1719 if (!isHeldExclusively())
1720 throw new IllegalMonitorStateException();
1721 Node first = firstWaiter;
1727 * Moves all threads from the wait queue for this condition to
1728 * the wait queue for the owning lock.
1730 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1731 * returns {@code false}
1733 public final void signalAll() {
1734 if (!isHeldExclusively())
1735 throw new IllegalMonitorStateException();
1736 Node first = firstWaiter;
1742 * Implements uninterruptible condition wait.
1744 * <li> Save lock state returned by {@link #getState}.
1745 * <li> Invoke {@link #release} with
1746 * saved state as argument, throwing
1747 * IllegalMonitorStateException if it fails.
1748 * <li> Block until signalled.
1749 * <li> Reacquire by invoking specialized version of
1750 * {@link #acquire} with saved state as argument.
1753 public final void awaitUninterruptibly() {
1754 Node node = addConditionWaiter();
1755 long savedState = fullyRelease(node);
1756 boolean interrupted = false;
1757 while (!isOnSyncQueue(node)) {
1758 LockSupport.park(this);
1759 if (Thread.interrupted())
1762 if (acquireQueued(node, savedState) || interrupted)
1767 * For interruptible waits, we need to track whether to throw
1768 * InterruptedException, if interrupted while blocked on
1769 * condition, versus reinterrupt current thread, if
1770 * interrupted while blocked waiting to re-acquire.
1773 /** Mode meaning to reinterrupt on exit from wait */
1774 private static final int REINTERRUPT = 1;
1775 /** Mode meaning to throw InterruptedException on exit from wait */
1776 private static final int THROW_IE = -1;
1779 * Checks for interrupt, returning THROW_IE if interrupted
1780 * before signalled, REINTERRUPT if after signalled, or
1781 * 0 if not interrupted.
1783 private int checkInterruptWhileWaiting(Node node) {
1784 return Thread.interrupted() ?
1785 (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
1790 * Throws InterruptedException, reinterrupts current thread, or
1791 * does nothing, depending on mode.
1793 private void reportInterruptAfterWait(int interruptMode)
1794 throws InterruptedException {
1795 if (interruptMode == THROW_IE)
1796 throw new InterruptedException();
1797 else if (interruptMode == REINTERRUPT)
1802 * Implements interruptible condition wait.
1804 * <li> If current thread is interrupted, throw InterruptedException.
1805 * <li> Save lock state returned by {@link #getState}.
1806 * <li> Invoke {@link #release} with
1807 * saved state as argument, throwing
1808 * IllegalMonitorStateException if it fails.
1809 * <li> Block until signalled or interrupted.
1810 * <li> Reacquire by invoking specialized version of
1811 * {@link #acquire} with saved state as argument.
1812 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1815 public final void await() throws InterruptedException {
1816 if (Thread.interrupted())
1817 throw new InterruptedException();
1818 Node node = addConditionWaiter();
1819 long savedState = fullyRelease(node);
1820 int interruptMode = 0;
1821 while (!isOnSyncQueue(node)) {
1822 LockSupport.park(this);
1823 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1826 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1827 interruptMode = REINTERRUPT;
1828 if (node.nextWaiter != null) // clean up if cancelled
1829 unlinkCancelledWaiters();
1830 if (interruptMode != 0)
1831 reportInterruptAfterWait(interruptMode);
1835 * Implements timed condition wait.
1837 * <li> If current thread is interrupted, throw InterruptedException.
1838 * <li> Save lock state returned by {@link #getState}.
1839 * <li> Invoke {@link #release} with
1840 * saved state as argument, throwing
1841 * IllegalMonitorStateException if it fails.
1842 * <li> Block until signalled, interrupted, or timed out.
1843 * <li> Reacquire by invoking specialized version of
1844 * {@link #acquire} with saved state as argument.
1845 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1848 public final long awaitNanos(long nanosTimeout)
1849 throws InterruptedException {
1850 if (Thread.interrupted())
1851 throw new InterruptedException();
1852 Node node = addConditionWaiter();
1853 long savedState = fullyRelease(node);
1854 long lastTime = System.nanoTime();
1855 int interruptMode = 0;
1856 while (!isOnSyncQueue(node)) {
1857 if (nanosTimeout <= 0L) {
1858 transferAfterCancelledWait(node);
1861 LockSupport.parkNanos(this, nanosTimeout);
1862 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1865 long now = System.nanoTime();
1866 nanosTimeout -= now - lastTime;
1869 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1870 interruptMode = REINTERRUPT;
1871 if (node.nextWaiter != null)
1872 unlinkCancelledWaiters();
1873 if (interruptMode != 0)
1874 reportInterruptAfterWait(interruptMode);
1875 return nanosTimeout - (System.nanoTime() - lastTime);
1879 * Implements absolute timed condition wait.
1881 * <li> If current thread is interrupted, throw InterruptedException.
1882 * <li> Save lock state returned by {@link #getState}.
1883 * <li> Invoke {@link #release} with
1884 * saved state as argument, throwing
1885 * IllegalMonitorStateException if it fails.
1886 * <li> Block until signalled, interrupted, or timed out.
1887 * <li> Reacquire by invoking specialized version of
1888 * {@link #acquire} with saved state as argument.
1889 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1890 * <li> If timed out while blocked in step 4, return false, else true.
1893 public final boolean awaitUntil(Date deadline)
1894 throws InterruptedException {
1895 if (deadline == null)
1896 throw new NullPointerException();
1897 long abstime = deadline.getTime();
1898 if (Thread.interrupted())
1899 throw new InterruptedException();
1900 Node node = addConditionWaiter();
1901 long savedState = fullyRelease(node);
1902 boolean timedout = false;
1903 int interruptMode = 0;
1904 while (!isOnSyncQueue(node)) {
1905 if (System.currentTimeMillis() > abstime) {
1906 timedout = transferAfterCancelledWait(node);
1909 LockSupport.parkUntil(this, abstime);
1910 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1913 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1914 interruptMode = REINTERRUPT;
1915 if (node.nextWaiter != null)
1916 unlinkCancelledWaiters();
1917 if (interruptMode != 0)
1918 reportInterruptAfterWait(interruptMode);
1923 * Implements timed condition wait.
1925 * <li> If current thread is interrupted, throw InterruptedException.
1926 * <li> Save lock state returned by {@link #getState}.
1927 * <li> Invoke {@link #release} with
1928 * saved state as argument, throwing
1929 * IllegalMonitorStateException if it fails.
1930 * <li> Block until signalled, interrupted, or timed out.
1931 * <li> Reacquire by invoking specialized version of
1932 * {@link #acquire} with saved state as argument.
1933 * <li> If interrupted while blocked in step 4, throw InterruptedException.
1934 * <li> If timed out while blocked in step 4, return false, else true.
1937 public final boolean await(long time, TimeUnit unit)
1938 throws InterruptedException {
1940 throw new NullPointerException();
1941 long nanosTimeout = unit.toNanos(time);
1942 if (Thread.interrupted())
1943 throw new InterruptedException();
1944 Node node = addConditionWaiter();
1945 long savedState = fullyRelease(node);
1946 long lastTime = System.nanoTime();
1947 boolean timedout = false;
1948 int interruptMode = 0;
1949 while (!isOnSyncQueue(node)) {
1950 if (nanosTimeout <= 0L) {
1951 timedout = transferAfterCancelledWait(node);
1954 if (nanosTimeout >= spinForTimeoutThreshold)
1955 LockSupport.parkNanos(this, nanosTimeout);
1956 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1958 long now = System.nanoTime();
1959 nanosTimeout -= now - lastTime;
1962 if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1963 interruptMode = REINTERRUPT;
1964 if (node.nextWaiter != null)
1965 unlinkCancelledWaiters();
1966 if (interruptMode != 0)
1967 reportInterruptAfterWait(interruptMode);
1971 // support for instrumentation
1974 * Returns true if this condition was created by the given
1975 * synchronization object.
1977 * @return {@code true} if owned
1979 final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1980 return sync == AbstractQueuedLongSynchronizer.this;
1984 * Queries whether any threads are waiting on this condition.
1985 * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters}.
1987 * @return {@code true} if there are any waiting threads
1988 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1989 * returns {@code false}
1991 protected final boolean hasWaiters() {
1992 if (!isHeldExclusively())
1993 throw new IllegalMonitorStateException();
1994 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1995 if (w.waitStatus == Node.CONDITION)
2002 * Returns an estimate of the number of threads waiting on
2004 * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength}.
2006 * @return the estimated number of waiting threads
2007 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2008 * returns {@code false}
2010 protected final int getWaitQueueLength() {
2011 if (!isHeldExclusively())
2012 throw new IllegalMonitorStateException();
2014 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2015 if (w.waitStatus == Node.CONDITION)
2022 * Returns a collection containing those threads that may be
2023 * waiting on this Condition.
2024 * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads}.
2026 * @return the collection of threads
2027 * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
2028 * returns {@code false}
2030 protected final Collection<Thread> getWaitingThreads() {
2031 if (!isHeldExclusively())
2032 throw new IllegalMonitorStateException();
2033 ArrayList<Thread> list = new ArrayList<Thread>();
2034 for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
2035 if (w.waitStatus == Node.CONDITION) {
2036 Thread t = w.thread;
2046 * Setup to support compareAndSet. We need to natively implement
2047 * this here: For the sake of permitting future enhancements, we
2048 * cannot explicitly subclass AtomicLong, which would be
2049 * efficient and useful otherwise. So, as the lesser of evils, we
2050 * natively implement using hotspot intrinsics API. And while we
2051 * are at it, we do the same for other CASable fields (which could
2052 * otherwise be done with atomic field updaters).
2054 private static final Unsafe unsafe = Unsafe.getUnsafe();
2055 private static final long stateOffset;
2056 private static final long headOffset;
2057 private static final long tailOffset;
2058 private static final long waitStatusOffset;
2059 private static final long nextOffset;
2063 stateOffset = unsafe.objectFieldOffset
2064 (AbstractQueuedLongSynchronizer.class.getDeclaredField("state"));
2065 headOffset = unsafe.objectFieldOffset
2066 (AbstractQueuedLongSynchronizer.class.getDeclaredField("head"));
2067 tailOffset = unsafe.objectFieldOffset
2068 (AbstractQueuedLongSynchronizer.class.getDeclaredField("tail"));
2069 waitStatusOffset = unsafe.objectFieldOffset
2070 (Node.class.getDeclaredField("waitStatus"));
2071 nextOffset = unsafe.objectFieldOffset
2072 (Node.class.getDeclaredField("next"));
2074 } catch (Exception ex) { throw new Error(ex); }
2078 * CAS head field. Used only by enq.
2080 private final boolean compareAndSetHead(Node update) {
2081 return unsafe.compareAndSwapObject(this, headOffset, null, update);
2085 * CAS tail field. Used only by enq.
2087 private final boolean compareAndSetTail(Node expect, Node update) {
2088 return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
2092 * CAS waitStatus field of a node.
2094 private static final boolean compareAndSetWaitStatus(Node node,
2097 return unsafe.compareAndSwapInt(node, waitStatusOffset,
2102 * CAS next field of a node.
2104 private static final boolean compareAndSetNext(Node node,
2107 return unsafe.compareAndSwapObject(node, nextOffset, expect, update);