rt/emul/compact/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rt/emul/compact/src/main/java/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java Sat Mar 19 10:46:31 2016 +0100
1.3 @@ -0,0 +1,2109 @@
1.4 +/*
1.5 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.6 + *
1.7 + * This code is free software; you can redistribute it and/or modify it
1.8 + * under the terms of the GNU General Public License version 2 only, as
1.9 + * published by the Free Software Foundation. Oracle designates this
1.10 + * particular file as subject to the "Classpath" exception as provided
1.11 + * by Oracle in the LICENSE file that accompanied this code.
1.12 + *
1.13 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.14 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.15 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.16 + * version 2 for more details (a copy is included in the LICENSE file that
1.17 + * accompanied this code).
1.18 + *
1.19 + * You should have received a copy of the GNU General Public License version
1.20 + * 2 along with this work; if not, write to the Free Software Foundation,
1.21 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.22 + *
1.23 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.24 + * or visit www.oracle.com if you need additional information or have any
1.25 + * questions.
1.26 + */
1.27 +
1.28 +/*
1.29 + * This file is available under and governed by the GNU General Public
1.30 + * License version 2 only, as published by the Free Software Foundation.
1.31 + * However, the following notice accompanied the original version of this
1.32 + * file:
1.33 + *
1.34 + * Written by Doug Lea with assistance from members of JCP JSR-166
1.35 + * Expert Group and released to the public domain, as explained at
1.36 + * http://creativecommons.org/publicdomain/zero/1.0/
1.37 + */
1.38 +
1.39 +package java.util.concurrent.locks;
1.40 +import java.util.*;
1.41 +import java.util.concurrent.*;
1.42 +import java.util.concurrent.atomic.*;
1.43 +import sun.misc.Unsafe;
1.44 +
1.45 +/**
1.46 + * A version of {@link AbstractQueuedSynchronizer} in
1.47 + * which synchronization state is maintained as a <tt>long</tt>.
1.48 + * This class has exactly the same structure, properties, and methods
1.49 + * as <tt>AbstractQueuedSynchronizer</tt> with the exception
1.50 + * that all state-related parameters and results are defined
1.51 + * as <tt>long</tt> rather than <tt>int</tt>. This class
1.52 + * may be useful when creating synchronizers such as
1.53 + * multilevel locks and barriers that require
1.54 + * 64 bits of state.
1.55 + *
1.56 + * <p>See {@link AbstractQueuedSynchronizer} for usage
1.57 + * notes and examples.
1.58 + *
1.59 + * @since 1.6
1.60 + * @author Doug Lea
1.61 + */
1.62 +public abstract class AbstractQueuedLongSynchronizer
1.63 + extends AbstractOwnableSynchronizer
1.64 + implements java.io.Serializable {
1.65 +
1.66 + private static final long serialVersionUID = 7373984972572414692L;
1.67 +
1.68 + /*
1.69 + To keep sources in sync, the remainder of this source file is
1.70 + exactly cloned from AbstractQueuedSynchronizer, replacing class
1.71 + name and changing ints related with sync state to longs. Please
1.72 + keep it that way.
1.73 + */
1.74 +
1.75 + /**
1.76 + * Creates a new <tt>AbstractQueuedLongSynchronizer</tt> instance
1.77 + * with initial synchronization state of zero.
1.78 + */
1.79 + protected AbstractQueuedLongSynchronizer() { }
1.80 +
1.81 + /**
1.82 + * Wait queue node class.
1.83 + *
1.84 + * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and
1.85 + * Hagersten) lock queue. CLH locks are normally used for
1.86 + * spinlocks. We instead use them for blocking synchronizers, but
1.87 + * use the same basic tactic of holding some of the control
1.88 + * information about a thread in the predecessor of its node. A
1.89 + * "status" field in each node keeps track of whether a thread
1.90 + * should block. A node is signalled when its predecessor
1.91 + * releases. Each node of the queue otherwise serves as a
1.92 + * specific-notification-style monitor holding a single waiting
1.93 + * thread. The status field does NOT control whether threads are
1.94 + * granted locks etc though. A thread may try to acquire if it is
1.95 + * first in the queue. But being first does not guarantee success;
1.96 + * it only gives the right to contend. So the currently released
1.97 + * contender thread may need to rewait.
1.98 + *
1.99 + * <p>To enqueue into a CLH lock, you atomically splice it in as new
1.100 + * tail. To dequeue, you just set the head field.
1.101 + * <pre>
1.102 + * +------+ prev +-----+ +-----+
1.103 + * head | | <---- | | <---- | | tail
1.104 + * +------+ +-----+ +-----+
1.105 + * </pre>
1.106 + *
1.107 + * <p>Insertion into a CLH queue requires only a single atomic
1.108 + * operation on "tail", so there is a simple atomic point of
1.109 + * demarcation from unqueued to queued. Similarly, dequeing
1.110 + * involves only updating the "head". However, it takes a bit
1.111 + * more work for nodes to determine who their successors are,
1.112 + * in part to deal with possible cancellation due to timeouts
1.113 + * and interrupts.
1.114 + *
1.115 + * <p>The "prev" links (not used in original CLH locks), are mainly
1.116 + * needed to handle cancellation. If a node is cancelled, its
1.117 + * successor is (normally) relinked to a non-cancelled
1.118 + * predecessor. For explanation of similar mechanics in the case
1.119 + * of spin locks, see the papers by Scott and Scherer at
1.120 + * http://www.cs.rochester.edu/u/scott/synchronization/
1.121 + *
1.122 + * <p>We also use "next" links to implement blocking mechanics.
1.123 + * The thread id for each node is kept in its own node, so a
1.124 + * predecessor signals the next node to wake up by traversing
1.125 + * next link to determine which thread it is. Determination of
1.126 + * successor must avoid races with newly queued nodes to set
1.127 + * the "next" fields of their predecessors. This is solved
1.128 + * when necessary by checking backwards from the atomically
1.129 + * updated "tail" when a node's successor appears to be null.
1.130 + * (Or, said differently, the next-links are an optimization
1.131 + * so that we don't usually need a backward scan.)
1.132 + *
1.133 + * <p>Cancellation introduces some conservatism to the basic
1.134 + * algorithms. Since we must poll for cancellation of other
1.135 + * nodes, we can miss noticing whether a cancelled node is
1.136 + * ahead or behind us. This is dealt with by always unparking
1.137 + * successors upon cancellation, allowing them to stabilize on
1.138 + * a new predecessor, unless we can identify an uncancelled
1.139 + * predecessor who will carry this responsibility.
1.140 + *
1.141 + * <p>CLH queues need a dummy header node to get started. But
1.142 + * we don't create them on construction, because it would be wasted
1.143 + * effort if there is never contention. Instead, the node
1.144 + * is constructed and head and tail pointers are set upon first
1.145 + * contention.
1.146 + *
1.147 + * <p>Threads waiting on Conditions use the same nodes, but
1.148 + * use an additional link. Conditions only need to link nodes
1.149 + * in simple (non-concurrent) linked queues because they are
1.150 + * only accessed when exclusively held. Upon await, a node is
1.151 + * inserted into a condition queue. Upon signal, the node is
1.152 + * transferred to the main queue. A special value of status
1.153 + * field is used to mark which queue a node is on.
1.154 + *
1.155 + * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill
1.156 + * Scherer and Michael Scott, along with members of JSR-166
1.157 + * expert group, for helpful ideas, discussions, and critiques
1.158 + * on the design of this class.
1.159 + */
1.160 + static final class Node {
1.161 + /** Marker to indicate a node is waiting in shared mode */
1.162 + static final Node SHARED = new Node();
1.163 + /** Marker to indicate a node is waiting in exclusive mode */
1.164 + static final Node EXCLUSIVE = null;
1.165 +
1.166 + /** waitStatus value to indicate thread has cancelled */
1.167 + static final int CANCELLED = 1;
1.168 + /** waitStatus value to indicate successor's thread needs unparking */
1.169 + static final int SIGNAL = -1;
1.170 + /** waitStatus value to indicate thread is waiting on condition */
1.171 + static final int CONDITION = -2;
1.172 + /**
1.173 + * waitStatus value to indicate the next acquireShared should
1.174 + * unconditionally propagate
1.175 + */
1.176 + static final int PROPAGATE = -3;
1.177 +
1.178 + /**
1.179 + * Status field, taking on only the values:
1.180 + * SIGNAL: The successor of this node is (or will soon be)
1.181 + * blocked (via park), so the current node must
1.182 + * unpark its successor when it releases or
1.183 + * cancels. To avoid races, acquire methods must
1.184 + * first indicate they need a signal,
1.185 + * then retry the atomic acquire, and then,
1.186 + * on failure, block.
1.187 + * CANCELLED: This node is cancelled due to timeout or interrupt.
1.188 + * Nodes never leave this state. In particular,
1.189 + * a thread with cancelled node never again blocks.
1.190 + * CONDITION: This node is currently on a condition queue.
1.191 + * It will not be used as a sync queue node
1.192 + * until transferred, at which time the status
1.193 + * will be set to 0. (Use of this value here has
1.194 + * nothing to do with the other uses of the
1.195 + * field, but simplifies mechanics.)
1.196 + * PROPAGATE: A releaseShared should be propagated to other
1.197 + * nodes. This is set (for head node only) in
1.198 + * doReleaseShared to ensure propagation
1.199 + * continues, even if other operations have
1.200 + * since intervened.
1.201 + * 0: None of the above
1.202 + *
1.203 + * The values are arranged numerically to simplify use.
1.204 + * Non-negative values mean that a node doesn't need to
1.205 + * signal. So, most code doesn't need to check for particular
1.206 + * values, just for sign.
1.207 + *
1.208 + * The field is initialized to 0 for normal sync nodes, and
1.209 + * CONDITION for condition nodes. It is modified using CAS
1.210 + * (or when possible, unconditional volatile writes).
1.211 + */
1.212 + volatile int waitStatus;
1.213 +
1.214 + /**
1.215 + * Link to predecessor node that current node/thread relies on
1.216 + * for checking waitStatus. Assigned during enqueing, and nulled
1.217 + * out (for sake of GC) only upon dequeuing. Also, upon
1.218 + * cancellation of a predecessor, we short-circuit while
1.219 + * finding a non-cancelled one, which will always exist
1.220 + * because the head node is never cancelled: A node becomes
1.221 + * head only as a result of successful acquire. A
1.222 + * cancelled thread never succeeds in acquiring, and a thread only
1.223 + * cancels itself, not any other node.
1.224 + */
1.225 + volatile Node prev;
1.226 +
1.227 + /**
1.228 + * Link to the successor node that the current node/thread
1.229 + * unparks upon release. Assigned during enqueuing, adjusted
1.230 + * when bypassing cancelled predecessors, and nulled out (for
1.231 + * sake of GC) when dequeued. The enq operation does not
1.232 + * assign next field of a predecessor until after attachment,
1.233 + * so seeing a null next field does not necessarily mean that
1.234 + * node is at end of queue. However, if a next field appears
1.235 + * to be null, we can scan prev's from the tail to
1.236 + * double-check. The next field of cancelled nodes is set to
1.237 + * point to the node itself instead of null, to make life
1.238 + * easier for isOnSyncQueue.
1.239 + */
1.240 + volatile Node next;
1.241 +
1.242 + /**
1.243 + * The thread that enqueued this node. Initialized on
1.244 + * construction and nulled out after use.
1.245 + */
1.246 + volatile Thread thread;
1.247 +
1.248 + /**
1.249 + * Link to next node waiting on condition, or the special
1.250 + * value SHARED. Because condition queues are accessed only
1.251 + * when holding in exclusive mode, we just need a simple
1.252 + * linked queue to hold nodes while they are waiting on
1.253 + * conditions. They are then transferred to the queue to
1.254 + * re-acquire. And because conditions can only be exclusive,
1.255 + * we save a field by using special value to indicate shared
1.256 + * mode.
1.257 + */
1.258 + Node nextWaiter;
1.259 +
1.260 + /**
1.261 + * Returns true if node is waiting in shared mode
1.262 + */
1.263 + final boolean isShared() {
1.264 + return nextWaiter == SHARED;
1.265 + }
1.266 +
1.267 + /**
1.268 + * Returns previous node, or throws NullPointerException if null.
1.269 + * Use when predecessor cannot be null. The null check could
1.270 + * be elided, but is present to help the VM.
1.271 + *
1.272 + * @return the predecessor of this node
1.273 + */
1.274 + final Node predecessor() throws NullPointerException {
1.275 + Node p = prev;
1.276 + if (p == null)
1.277 + throw new NullPointerException();
1.278 + else
1.279 + return p;
1.280 + }
1.281 +
1.282 + Node() { // Used to establish initial head or SHARED marker
1.283 + }
1.284 +
1.285 + Node(Thread thread, Node mode) { // Used by addWaiter
1.286 + this.nextWaiter = mode;
1.287 + this.thread = thread;
1.288 + }
1.289 +
1.290 + Node(Thread thread, int waitStatus) { // Used by Condition
1.291 + this.waitStatus = waitStatus;
1.292 + this.thread = thread;
1.293 + }
1.294 + }
1.295 +
1.296 + /**
1.297 + * Head of the wait queue, lazily initialized. Except for
1.298 + * initialization, it is modified only via method setHead. Note:
1.299 + * If head exists, its waitStatus is guaranteed not to be
1.300 + * CANCELLED.
1.301 + */
1.302 + private transient volatile Node head;
1.303 +
1.304 + /**
1.305 + * Tail of the wait queue, lazily initialized. Modified only via
1.306 + * method enq to add new wait node.
1.307 + */
1.308 + private transient volatile Node tail;
1.309 +
1.310 + /**
1.311 + * The synchronization state.
1.312 + */
1.313 + private volatile long state;
1.314 +
1.315 + /**
1.316 + * Returns the current value of synchronization state.
1.317 + * This operation has memory semantics of a <tt>volatile</tt> read.
1.318 + * @return current state value
1.319 + */
1.320 + protected final long getState() {
1.321 + return state;
1.322 + }
1.323 +
1.324 + /**
1.325 + * Sets the value of synchronization state.
1.326 + * This operation has memory semantics of a <tt>volatile</tt> write.
1.327 + * @param newState the new state value
1.328 + */
1.329 + protected final void setState(long newState) {
1.330 + state = newState;
1.331 + }
1.332 +
1.333 + /**
1.334 + * Atomically sets synchronization state to the given updated
1.335 + * value if the current state value equals the expected value.
1.336 + * This operation has memory semantics of a <tt>volatile</tt> read
1.337 + * and write.
1.338 + *
1.339 + * @param expect the expected value
1.340 + * @param update the new value
1.341 + * @return true if successful. False return indicates that the actual
1.342 + * value was not equal to the expected value.
1.343 + */
1.344 + protected final boolean compareAndSetState(long expect, long update) {
1.345 + // See below for intrinsics setup to support this
1.346 + return unsafe.compareAndSwapLong(this, stateOffset, expect, update);
1.347 + }
1.348 +
1.349 + // Queuing utilities
1.350 +
1.351 + /**
1.352 + * The number of nanoseconds for which it is faster to spin
1.353 + * rather than to use timed park. A rough estimate suffices
1.354 + * to improve responsiveness with very short timeouts.
1.355 + */
1.356 + static final long spinForTimeoutThreshold = 1000L;
1.357 +
1.358 + /**
1.359 + * Inserts node into queue, initializing if necessary. See picture above.
1.360 + * @param node the node to insert
1.361 + * @return node's predecessor
1.362 + */
1.363 + private Node enq(final Node node) {
1.364 + for (;;) {
1.365 + Node t = tail;
1.366 + if (t == null) { // Must initialize
1.367 + if (compareAndSetHead(new Node()))
1.368 + tail = head;
1.369 + } else {
1.370 + node.prev = t;
1.371 + if (compareAndSetTail(t, node)) {
1.372 + t.next = node;
1.373 + return t;
1.374 + }
1.375 + }
1.376 + }
1.377 + }
1.378 +
1.379 + /**
1.380 + * Creates and enqueues node for current thread and given mode.
1.381 + *
1.382 + * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
1.383 + * @return the new node
1.384 + */
1.385 + private Node addWaiter(Node mode) {
1.386 + Node node = new Node(Thread.currentThread(), mode);
1.387 + // Try the fast path of enq; backup to full enq on failure
1.388 + Node pred = tail;
1.389 + if (pred != null) {
1.390 + node.prev = pred;
1.391 + if (compareAndSetTail(pred, node)) {
1.392 + pred.next = node;
1.393 + return node;
1.394 + }
1.395 + }
1.396 + enq(node);
1.397 + return node;
1.398 + }
1.399 +
1.400 + /**
1.401 + * Sets head of queue to be node, thus dequeuing. Called only by
1.402 + * acquire methods. Also nulls out unused fields for sake of GC
1.403 + * and to suppress unnecessary signals and traversals.
1.404 + *
1.405 + * @param node the node
1.406 + */
1.407 + private void setHead(Node node) {
1.408 + head = node;
1.409 + node.thread = null;
1.410 + node.prev = null;
1.411 + }
1.412 +
1.413 + /**
1.414 + * Wakes up node's successor, if one exists.
1.415 + *
1.416 + * @param node the node
1.417 + */
1.418 + private void unparkSuccessor(Node node) {
1.419 + /*
1.420 + * If status is negative (i.e., possibly needing signal) try
1.421 + * to clear in anticipation of signalling. It is OK if this
1.422 + * fails or if status is changed by waiting thread.
1.423 + */
1.424 + int ws = node.waitStatus;
1.425 + if (ws < 0)
1.426 + compareAndSetWaitStatus(node, ws, 0);
1.427 +
1.428 + /*
1.429 + * Thread to unpark is held in successor, which is normally
1.430 + * just the next node. But if cancelled or apparently null,
1.431 + * traverse backwards from tail to find the actual
1.432 + * non-cancelled successor.
1.433 + */
1.434 + Node s = node.next;
1.435 + if (s == null || s.waitStatus > 0) {
1.436 + s = null;
1.437 + for (Node t = tail; t != null && t != node; t = t.prev)
1.438 + if (t.waitStatus <= 0)
1.439 + s = t;
1.440 + }
1.441 + if (s != null)
1.442 + LockSupport.unpark(s.thread);
1.443 + }
1.444 +
1.445 + /**
1.446 + * Release action for shared mode -- signal successor and ensure
1.447 + * propagation. (Note: For exclusive mode, release just amounts
1.448 + * to calling unparkSuccessor of head if it needs signal.)
1.449 + */
1.450 + private void doReleaseShared() {
1.451 + /*
1.452 + * Ensure that a release propagates, even if there are other
1.453 + * in-progress acquires/releases. This proceeds in the usual
1.454 + * way of trying to unparkSuccessor of head if it needs
1.455 + * signal. But if it does not, status is set to PROPAGATE to
1.456 + * ensure that upon release, propagation continues.
1.457 + * Additionally, we must loop in case a new node is added
1.458 + * while we are doing this. Also, unlike other uses of
1.459 + * unparkSuccessor, we need to know if CAS to reset status
1.460 + * fails, if so rechecking.
1.461 + */
1.462 + for (;;) {
1.463 + Node h = head;
1.464 + if (h != null && h != tail) {
1.465 + int ws = h.waitStatus;
1.466 + if (ws == Node.SIGNAL) {
1.467 + if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
1.468 + continue; // loop to recheck cases
1.469 + unparkSuccessor(h);
1.470 + }
1.471 + else if (ws == 0 &&
1.472 + !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
1.473 + continue; // loop on failed CAS
1.474 + }
1.475 + if (h == head) // loop if head changed
1.476 + break;
1.477 + }
1.478 + }
1.479 +
1.480 + /**
1.481 + * Sets head of queue, and checks if successor may be waiting
1.482 + * in shared mode, if so propagating if either propagate > 0 or
1.483 + * PROPAGATE status was set.
1.484 + *
1.485 + * @param node the node
1.486 + * @param propagate the return value from a tryAcquireShared
1.487 + */
1.488 + private void setHeadAndPropagate(Node node, long propagate) {
1.489 + Node h = head; // Record old head for check below
1.490 + setHead(node);
1.491 + /*
1.492 + * Try to signal next queued node if:
1.493 + * Propagation was indicated by caller,
1.494 + * or was recorded (as h.waitStatus) by a previous operation
1.495 + * (note: this uses sign-check of waitStatus because
1.496 + * PROPAGATE status may transition to SIGNAL.)
1.497 + * and
1.498 + * The next node is waiting in shared mode,
1.499 + * or we don't know, because it appears null
1.500 + *
1.501 + * The conservatism in both of these checks may cause
1.502 + * unnecessary wake-ups, but only when there are multiple
1.503 + * racing acquires/releases, so most need signals now or soon
1.504 + * anyway.
1.505 + */
1.506 + if (propagate > 0 || h == null || h.waitStatus < 0) {
1.507 + Node s = node.next;
1.508 + if (s == null || s.isShared())
1.509 + doReleaseShared();
1.510 + }
1.511 + }
1.512 +
1.513 + // Utilities for various versions of acquire
1.514 +
1.515 + /**
1.516 + * Cancels an ongoing attempt to acquire.
1.517 + *
1.518 + * @param node the node
1.519 + */
1.520 + private void cancelAcquire(Node node) {
1.521 + // Ignore if node doesn't exist
1.522 + if (node == null)
1.523 + return;
1.524 +
1.525 + node.thread = null;
1.526 +
1.527 + // Skip cancelled predecessors
1.528 + Node pred = node.prev;
1.529 + while (pred.waitStatus > 0)
1.530 + node.prev = pred = pred.prev;
1.531 +
1.532 + // predNext is the apparent node to unsplice. CASes below will
1.533 + // fail if not, in which case, we lost race vs another cancel
1.534 + // or signal, so no further action is necessary.
1.535 + Node predNext = pred.next;
1.536 +
1.537 + // Can use unconditional write instead of CAS here.
1.538 + // After this atomic step, other Nodes can skip past us.
1.539 + // Before, we are free of interference from other threads.
1.540 + node.waitStatus = Node.CANCELLED;
1.541 +
1.542 + // If we are the tail, remove ourselves.
1.543 + if (node == tail && compareAndSetTail(node, pred)) {
1.544 + compareAndSetNext(pred, predNext, null);
1.545 + } else {
1.546 + // If successor needs signal, try to set pred's next-link
1.547 + // so it will get one. Otherwise wake it up to propagate.
1.548 + int ws;
1.549 + if (pred != head &&
1.550 + ((ws = pred.waitStatus) == Node.SIGNAL ||
1.551 + (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
1.552 + pred.thread != null) {
1.553 + Node next = node.next;
1.554 + if (next != null && next.waitStatus <= 0)
1.555 + compareAndSetNext(pred, predNext, next);
1.556 + } else {
1.557 + unparkSuccessor(node);
1.558 + }
1.559 +
1.560 + node.next = node; // help GC
1.561 + }
1.562 + }
1.563 +
1.564 + /**
1.565 + * Checks and updates status for a node that failed to acquire.
1.566 + * Returns true if thread should block. This is the main signal
1.567 + * control in all acquire loops. Requires that pred == node.prev
1.568 + *
1.569 + * @param pred node's predecessor holding status
1.570 + * @param node the node
1.571 + * @return {@code true} if thread should block
1.572 + */
1.573 + private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
1.574 + int ws = pred.waitStatus;
1.575 + if (ws == Node.SIGNAL)
1.576 + /*
1.577 + * This node has already set status asking a release
1.578 + * to signal it, so it can safely park.
1.579 + */
1.580 + return true;
1.581 + if (ws > 0) {
1.582 + /*
1.583 + * Predecessor was cancelled. Skip over predecessors and
1.584 + * indicate retry.
1.585 + */
1.586 + do {
1.587 + node.prev = pred = pred.prev;
1.588 + } while (pred.waitStatus > 0);
1.589 + pred.next = node;
1.590 + } else {
1.591 + /*
1.592 + * waitStatus must be 0 or PROPAGATE. Indicate that we
1.593 + * need a signal, but don't park yet. Caller will need to
1.594 + * retry to make sure it cannot acquire before parking.
1.595 + */
1.596 + compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
1.597 + }
1.598 + return false;
1.599 + }
1.600 +
1.601 + /**
1.602 + * Convenience method to interrupt current thread.
1.603 + */
1.604 + private static void selfInterrupt() {
1.605 + Thread.currentThread().interrupt();
1.606 + }
1.607 +
1.608 + /**
1.609 + * Convenience method to park and then check if interrupted
1.610 + *
1.611 + * @return {@code true} if interrupted
1.612 + */
1.613 + private final boolean parkAndCheckInterrupt() {
1.614 + LockSupport.park(this);
1.615 + return Thread.interrupted();
1.616 + }
1.617 +
1.618 + /*
1.619 + * Various flavors of acquire, varying in exclusive/shared and
1.620 + * control modes. Each is mostly the same, but annoyingly
1.621 + * different. Only a little bit of factoring is possible due to
1.622 + * interactions of exception mechanics (including ensuring that we
1.623 + * cancel if tryAcquire throws exception) and other control, at
1.624 + * least not without hurting performance too much.
1.625 + */
1.626 +
1.627 + /**
1.628 + * Acquires in exclusive uninterruptible mode for thread already in
1.629 + * queue. Used by condition wait methods as well as acquire.
1.630 + *
1.631 + * @param node the node
1.632 + * @param arg the acquire argument
1.633 + * @return {@code true} if interrupted while waiting
1.634 + */
1.635 + final boolean acquireQueued(final Node node, long arg) {
1.636 + boolean failed = true;
1.637 + try {
1.638 + boolean interrupted = false;
1.639 + for (;;) {
1.640 + final Node p = node.predecessor();
1.641 + if (p == head && tryAcquire(arg)) {
1.642 + setHead(node);
1.643 + p.next = null; // help GC
1.644 + failed = false;
1.645 + return interrupted;
1.646 + }
1.647 + if (shouldParkAfterFailedAcquire(p, node) &&
1.648 + parkAndCheckInterrupt())
1.649 + interrupted = true;
1.650 + }
1.651 + } finally {
1.652 + if (failed)
1.653 + cancelAcquire(node);
1.654 + }
1.655 + }
1.656 +
1.657 + /**
1.658 + * Acquires in exclusive interruptible mode.
1.659 + * @param arg the acquire argument
1.660 + */
1.661 + private void doAcquireInterruptibly(long arg)
1.662 + throws InterruptedException {
1.663 + final Node node = addWaiter(Node.EXCLUSIVE);
1.664 + boolean failed = true;
1.665 + try {
1.666 + for (;;) {
1.667 + final Node p = node.predecessor();
1.668 + if (p == head && tryAcquire(arg)) {
1.669 + setHead(node);
1.670 + p.next = null; // help GC
1.671 + failed = false;
1.672 + return;
1.673 + }
1.674 + if (shouldParkAfterFailedAcquire(p, node) &&
1.675 + parkAndCheckInterrupt())
1.676 + throw new InterruptedException();
1.677 + }
1.678 + } finally {
1.679 + if (failed)
1.680 + cancelAcquire(node);
1.681 + }
1.682 + }
1.683 +
1.684 + /**
1.685 + * Acquires in exclusive timed mode.
1.686 + *
1.687 + * @param arg the acquire argument
1.688 + * @param nanosTimeout max wait time
1.689 + * @return {@code true} if acquired
1.690 + */
1.691 + private boolean doAcquireNanos(long arg, long nanosTimeout)
1.692 + throws InterruptedException {
1.693 + long lastTime = System.nanoTime();
1.694 + final Node node = addWaiter(Node.EXCLUSIVE);
1.695 + boolean failed = true;
1.696 + try {
1.697 + for (;;) {
1.698 + final Node p = node.predecessor();
1.699 + if (p == head && tryAcquire(arg)) {
1.700 + setHead(node);
1.701 + p.next = null; // help GC
1.702 + failed = false;
1.703 + return true;
1.704 + }
1.705 + if (nanosTimeout <= 0)
1.706 + return false;
1.707 + if (shouldParkAfterFailedAcquire(p, node) &&
1.708 + nanosTimeout > spinForTimeoutThreshold)
1.709 + LockSupport.parkNanos(this, nanosTimeout);
1.710 + long now = System.nanoTime();
1.711 + nanosTimeout -= now - lastTime;
1.712 + lastTime = now;
1.713 + if (Thread.interrupted())
1.714 + throw new InterruptedException();
1.715 + }
1.716 + } finally {
1.717 + if (failed)
1.718 + cancelAcquire(node);
1.719 + }
1.720 + }
1.721 +
1.722 + /**
1.723 + * Acquires in shared uninterruptible mode.
1.724 + * @param arg the acquire argument
1.725 + */
1.726 + private void doAcquireShared(long arg) {
1.727 + final Node node = addWaiter(Node.SHARED);
1.728 + boolean failed = true;
1.729 + try {
1.730 + boolean interrupted = false;
1.731 + for (;;) {
1.732 + final Node p = node.predecessor();
1.733 + if (p == head) {
1.734 + long r = tryAcquireShared(arg);
1.735 + if (r >= 0) {
1.736 + setHeadAndPropagate(node, r);
1.737 + p.next = null; // help GC
1.738 + if (interrupted)
1.739 + selfInterrupt();
1.740 + failed = false;
1.741 + return;
1.742 + }
1.743 + }
1.744 + if (shouldParkAfterFailedAcquire(p, node) &&
1.745 + parkAndCheckInterrupt())
1.746 + interrupted = true;
1.747 + }
1.748 + } finally {
1.749 + if (failed)
1.750 + cancelAcquire(node);
1.751 + }
1.752 + }
1.753 +
1.754 + /**
1.755 + * Acquires in shared interruptible mode.
1.756 + * @param arg the acquire argument
1.757 + */
1.758 + private void doAcquireSharedInterruptibly(long arg)
1.759 + throws InterruptedException {
1.760 + final Node node = addWaiter(Node.SHARED);
1.761 + boolean failed = true;
1.762 + try {
1.763 + for (;;) {
1.764 + final Node p = node.predecessor();
1.765 + if (p == head) {
1.766 + long r = tryAcquireShared(arg);
1.767 + if (r >= 0) {
1.768 + setHeadAndPropagate(node, r);
1.769 + p.next = null; // help GC
1.770 + failed = false;
1.771 + return;
1.772 + }
1.773 + }
1.774 + if (shouldParkAfterFailedAcquire(p, node) &&
1.775 + parkAndCheckInterrupt())
1.776 + throw new InterruptedException();
1.777 + }
1.778 + } finally {
1.779 + if (failed)
1.780 + cancelAcquire(node);
1.781 + }
1.782 + }
1.783 +
1.784 + /**
1.785 + * Acquires in shared timed mode.
1.786 + *
1.787 + * @param arg the acquire argument
1.788 + * @param nanosTimeout max wait time
1.789 + * @return {@code true} if acquired
1.790 + */
1.791 + private boolean doAcquireSharedNanos(long arg, long nanosTimeout)
1.792 + throws InterruptedException {
1.793 +
1.794 + long lastTime = System.nanoTime();
1.795 + final Node node = addWaiter(Node.SHARED);
1.796 + boolean failed = true;
1.797 + try {
1.798 + for (;;) {
1.799 + final Node p = node.predecessor();
1.800 + if (p == head) {
1.801 + long r = tryAcquireShared(arg);
1.802 + if (r >= 0) {
1.803 + setHeadAndPropagate(node, r);
1.804 + p.next = null; // help GC
1.805 + failed = false;
1.806 + return true;
1.807 + }
1.808 + }
1.809 + if (nanosTimeout <= 0)
1.810 + return false;
1.811 + if (shouldParkAfterFailedAcquire(p, node) &&
1.812 + nanosTimeout > spinForTimeoutThreshold)
1.813 + LockSupport.parkNanos(this, nanosTimeout);
1.814 + long now = System.nanoTime();
1.815 + nanosTimeout -= now - lastTime;
1.816 + lastTime = now;
1.817 + if (Thread.interrupted())
1.818 + throw new InterruptedException();
1.819 + }
1.820 + } finally {
1.821 + if (failed)
1.822 + cancelAcquire(node);
1.823 + }
1.824 + }
1.825 +
1.826 + // Main exported methods
1.827 +
1.828 + /**
1.829 + * Attempts to acquire in exclusive mode. This method should query
1.830 + * if the state of the object permits it to be acquired in the
1.831 + * exclusive mode, and if so to acquire it.
1.832 + *
1.833 + * <p>This method is always invoked by the thread performing
1.834 + * acquire. If this method reports failure, the acquire method
1.835 + * may queue the thread, if it is not already queued, until it is
1.836 + * signalled by a release from some other thread. This can be used
1.837 + * to implement method {@link Lock#tryLock()}.
1.838 + *
1.839 + * <p>The default
1.840 + * implementation throws {@link UnsupportedOperationException}.
1.841 + *
1.842 + * @param arg the acquire argument. This value is always the one
1.843 + * passed to an acquire method, or is the value saved on entry
1.844 + * to a condition wait. The value is otherwise uninterpreted
1.845 + * and can represent anything you like.
1.846 + * @return {@code true} if successful. Upon success, this object has
1.847 + * been acquired.
1.848 + * @throws IllegalMonitorStateException if acquiring would place this
1.849 + * synchronizer in an illegal state. This exception must be
1.850 + * thrown in a consistent fashion for synchronization to work
1.851 + * correctly.
1.852 + * @throws UnsupportedOperationException if exclusive mode is not supported
1.853 + */
1.854 + protected boolean tryAcquire(long arg) {
1.855 + throw new UnsupportedOperationException();
1.856 + }
1.857 +
1.858 + /**
1.859 + * Attempts to set the state to reflect a release in exclusive
1.860 + * mode.
1.861 + *
1.862 + * <p>This method is always invoked by the thread performing release.
1.863 + *
1.864 + * <p>The default implementation throws
1.865 + * {@link UnsupportedOperationException}.
1.866 + *
1.867 + * @param arg the release argument. This value is always the one
1.868 + * passed to a release method, or the current state value upon
1.869 + * entry to a condition wait. The value is otherwise
1.870 + * uninterpreted and can represent anything you like.
1.871 + * @return {@code true} if this object is now in a fully released
1.872 + * state, so that any waiting threads may attempt to acquire;
1.873 + * and {@code false} otherwise.
1.874 + * @throws IllegalMonitorStateException if releasing would place this
1.875 + * synchronizer in an illegal state. This exception must be
1.876 + * thrown in a consistent fashion for synchronization to work
1.877 + * correctly.
1.878 + * @throws UnsupportedOperationException if exclusive mode is not supported
1.879 + */
1.880 + protected boolean tryRelease(long arg) {
1.881 + throw new UnsupportedOperationException();
1.882 + }
1.883 +
1.884 + /**
1.885 + * Attempts to acquire in shared mode. This method should query if
1.886 + * the state of the object permits it to be acquired in the shared
1.887 + * mode, and if so to acquire it.
1.888 + *
1.889 + * <p>This method is always invoked by the thread performing
1.890 + * acquire. If this method reports failure, the acquire method
1.891 + * may queue the thread, if it is not already queued, until it is
1.892 + * signalled by a release from some other thread.
1.893 + *
1.894 + * <p>The default implementation throws {@link
1.895 + * UnsupportedOperationException}.
1.896 + *
1.897 + * @param arg the acquire argument. This value is always the one
1.898 + * passed to an acquire method, or is the value saved on entry
1.899 + * to a condition wait. The value is otherwise uninterpreted
1.900 + * and can represent anything you like.
1.901 + * @return a negative value on failure; zero if acquisition in shared
1.902 + * mode succeeded but no subsequent shared-mode acquire can
1.903 + * succeed; and a positive value if acquisition in shared
1.904 + * mode succeeded and subsequent shared-mode acquires might
1.905 + * also succeed, in which case a subsequent waiting thread
1.906 + * must check availability. (Support for three different
1.907 + * return values enables this method to be used in contexts
1.908 + * where acquires only sometimes act exclusively.) Upon
1.909 + * success, this object has been acquired.
1.910 + * @throws IllegalMonitorStateException if acquiring would place this
1.911 + * synchronizer in an illegal state. This exception must be
1.912 + * thrown in a consistent fashion for synchronization to work
1.913 + * correctly.
1.914 + * @throws UnsupportedOperationException if shared mode is not supported
1.915 + */
1.916 + protected long tryAcquireShared(long arg) {
1.917 + throw new UnsupportedOperationException();
1.918 + }
1.919 +
1.920 + /**
1.921 + * Attempts to set the state to reflect a release in shared mode.
1.922 + *
1.923 + * <p>This method is always invoked by the thread performing release.
1.924 + *
1.925 + * <p>The default implementation throws
1.926 + * {@link UnsupportedOperationException}.
1.927 + *
1.928 + * @param arg the release argument. This value is always the one
1.929 + * passed to a release method, or the current state value upon
1.930 + * entry to a condition wait. The value is otherwise
1.931 + * uninterpreted and can represent anything you like.
1.932 + * @return {@code true} if this release of shared mode may permit a
1.933 + * waiting acquire (shared or exclusive) to succeed; and
1.934 + * {@code false} otherwise
1.935 + * @throws IllegalMonitorStateException if releasing would place this
1.936 + * synchronizer in an illegal state. This exception must be
1.937 + * thrown in a consistent fashion for synchronization to work
1.938 + * correctly.
1.939 + * @throws UnsupportedOperationException if shared mode is not supported
1.940 + */
1.941 + protected boolean tryReleaseShared(long arg) {
1.942 + throw new UnsupportedOperationException();
1.943 + }
1.944 +
1.945 + /**
1.946 + * Returns {@code true} if synchronization is held exclusively with
1.947 + * respect to the current (calling) thread. This method is invoked
1.948 + * upon each call to a non-waiting {@link ConditionObject} method.
1.949 + * (Waiting methods instead invoke {@link #release}.)
1.950 + *
1.951 + * <p>The default implementation throws {@link
1.952 + * UnsupportedOperationException}. This method is invoked
1.953 + * internally only within {@link ConditionObject} methods, so need
1.954 + * not be defined if conditions are not used.
1.955 + *
1.956 + * @return {@code true} if synchronization is held exclusively;
1.957 + * {@code false} otherwise
1.958 + * @throws UnsupportedOperationException if conditions are not supported
1.959 + */
1.960 + protected boolean isHeldExclusively() {
1.961 + throw new UnsupportedOperationException();
1.962 + }
1.963 +
1.964 + /**
1.965 + * Acquires in exclusive mode, ignoring interrupts. Implemented
1.966 + * by invoking at least once {@link #tryAcquire},
1.967 + * returning on success. Otherwise the thread is queued, possibly
1.968 + * repeatedly blocking and unblocking, invoking {@link
1.969 + * #tryAcquire} until success. This method can be used
1.970 + * to implement method {@link Lock#lock}.
1.971 + *
1.972 + * @param arg the acquire argument. This value is conveyed to
1.973 + * {@link #tryAcquire} but is otherwise uninterpreted and
1.974 + * can represent anything you like.
1.975 + */
1.976 + public final void acquire(long arg) {
1.977 + if (!tryAcquire(arg) &&
1.978 + acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
1.979 + selfInterrupt();
1.980 + }
1.981 +
1.982 + /**
1.983 + * Acquires in exclusive mode, aborting if interrupted.
1.984 + * Implemented by first checking interrupt status, then invoking
1.985 + * at least once {@link #tryAcquire}, returning on
1.986 + * success. Otherwise the thread is queued, possibly repeatedly
1.987 + * blocking and unblocking, invoking {@link #tryAcquire}
1.988 + * until success or the thread is interrupted. This method can be
1.989 + * used to implement method {@link Lock#lockInterruptibly}.
1.990 + *
1.991 + * @param arg the acquire argument. This value is conveyed to
1.992 + * {@link #tryAcquire} but is otherwise uninterpreted and
1.993 + * can represent anything you like.
1.994 + * @throws InterruptedException if the current thread is interrupted
1.995 + */
1.996 + public final void acquireInterruptibly(long arg)
1.997 + throws InterruptedException {
1.998 + if (Thread.interrupted())
1.999 + throw new InterruptedException();
1.1000 + if (!tryAcquire(arg))
1.1001 + doAcquireInterruptibly(arg);
1.1002 + }
1.1003 +
1.1004 + /**
1.1005 + * Attempts to acquire in exclusive mode, aborting if interrupted,
1.1006 + * and failing if the given timeout elapses. Implemented by first
1.1007 + * checking interrupt status, then invoking at least once {@link
1.1008 + * #tryAcquire}, returning on success. Otherwise, the thread is
1.1009 + * queued, possibly repeatedly blocking and unblocking, invoking
1.1010 + * {@link #tryAcquire} until success or the thread is interrupted
1.1011 + * or the timeout elapses. This method can be used to implement
1.1012 + * method {@link Lock#tryLock(long, TimeUnit)}.
1.1013 + *
1.1014 + * @param arg the acquire argument. This value is conveyed to
1.1015 + * {@link #tryAcquire} but is otherwise uninterpreted and
1.1016 + * can represent anything you like.
1.1017 + * @param nanosTimeout the maximum number of nanoseconds to wait
1.1018 + * @return {@code true} if acquired; {@code false} if timed out
1.1019 + * @throws InterruptedException if the current thread is interrupted
1.1020 + */
1.1021 + public final boolean tryAcquireNanos(long arg, long nanosTimeout)
1.1022 + throws InterruptedException {
1.1023 + if (Thread.interrupted())
1.1024 + throw new InterruptedException();
1.1025 + return tryAcquire(arg) ||
1.1026 + doAcquireNanos(arg, nanosTimeout);
1.1027 + }
1.1028 +
1.1029 + /**
1.1030 + * Releases in exclusive mode. Implemented by unblocking one or
1.1031 + * more threads if {@link #tryRelease} returns true.
1.1032 + * This method can be used to implement method {@link Lock#unlock}.
1.1033 + *
1.1034 + * @param arg the release argument. This value is conveyed to
1.1035 + * {@link #tryRelease} but is otherwise uninterpreted and
1.1036 + * can represent anything you like.
1.1037 + * @return the value returned from {@link #tryRelease}
1.1038 + */
1.1039 + public final boolean release(long arg) {
1.1040 + if (tryRelease(arg)) {
1.1041 + Node h = head;
1.1042 + if (h != null && h.waitStatus != 0)
1.1043 + unparkSuccessor(h);
1.1044 + return true;
1.1045 + }
1.1046 + return false;
1.1047 + }
1.1048 +
1.1049 + /**
1.1050 + * Acquires in shared mode, ignoring interrupts. Implemented by
1.1051 + * first invoking at least once {@link #tryAcquireShared},
1.1052 + * returning on success. Otherwise the thread is queued, possibly
1.1053 + * repeatedly blocking and unblocking, invoking {@link
1.1054 + * #tryAcquireShared} until success.
1.1055 + *
1.1056 + * @param arg the acquire argument. This value is conveyed to
1.1057 + * {@link #tryAcquireShared} but is otherwise uninterpreted
1.1058 + * and can represent anything you like.
1.1059 + */
1.1060 + public final void acquireShared(long arg) {
1.1061 + if (tryAcquireShared(arg) < 0)
1.1062 + doAcquireShared(arg);
1.1063 + }
1.1064 +
1.1065 + /**
1.1066 + * Acquires in shared mode, aborting if interrupted. Implemented
1.1067 + * by first checking interrupt status, then invoking at least once
1.1068 + * {@link #tryAcquireShared}, returning on success. Otherwise the
1.1069 + * thread is queued, possibly repeatedly blocking and unblocking,
1.1070 + * invoking {@link #tryAcquireShared} until success or the thread
1.1071 + * is interrupted.
1.1072 + * @param arg the acquire argument
1.1073 + * This value is conveyed to {@link #tryAcquireShared} but is
1.1074 + * otherwise uninterpreted and can represent anything
1.1075 + * you like.
1.1076 + * @throws InterruptedException if the current thread is interrupted
1.1077 + */
1.1078 + public final void acquireSharedInterruptibly(long arg)
1.1079 + throws InterruptedException {
1.1080 + if (Thread.interrupted())
1.1081 + throw new InterruptedException();
1.1082 + if (tryAcquireShared(arg) < 0)
1.1083 + doAcquireSharedInterruptibly(arg);
1.1084 + }
1.1085 +
1.1086 + /**
1.1087 + * Attempts to acquire in shared mode, aborting if interrupted, and
1.1088 + * failing if the given timeout elapses. Implemented by first
1.1089 + * checking interrupt status, then invoking at least once {@link
1.1090 + * #tryAcquireShared}, returning on success. Otherwise, the
1.1091 + * thread is queued, possibly repeatedly blocking and unblocking,
1.1092 + * invoking {@link #tryAcquireShared} until success or the thread
1.1093 + * is interrupted or the timeout elapses.
1.1094 + *
1.1095 + * @param arg the acquire argument. This value is conveyed to
1.1096 + * {@link #tryAcquireShared} but is otherwise uninterpreted
1.1097 + * and can represent anything you like.
1.1098 + * @param nanosTimeout the maximum number of nanoseconds to wait
1.1099 + * @return {@code true} if acquired; {@code false} if timed out
1.1100 + * @throws InterruptedException if the current thread is interrupted
1.1101 + */
1.1102 + public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout)
1.1103 + throws InterruptedException {
1.1104 + if (Thread.interrupted())
1.1105 + throw new InterruptedException();
1.1106 + return tryAcquireShared(arg) >= 0 ||
1.1107 + doAcquireSharedNanos(arg, nanosTimeout);
1.1108 + }
1.1109 +
1.1110 + /**
1.1111 + * Releases in shared mode. Implemented by unblocking one or more
1.1112 + * threads if {@link #tryReleaseShared} returns true.
1.1113 + *
1.1114 + * @param arg the release argument. This value is conveyed to
1.1115 + * {@link #tryReleaseShared} but is otherwise uninterpreted
1.1116 + * and can represent anything you like.
1.1117 + * @return the value returned from {@link #tryReleaseShared}
1.1118 + */
1.1119 + public final boolean releaseShared(long arg) {
1.1120 + if (tryReleaseShared(arg)) {
1.1121 + doReleaseShared();
1.1122 + return true;
1.1123 + }
1.1124 + return false;
1.1125 + }
1.1126 +
1.1127 + // Queue inspection methods
1.1128 +
1.1129 + /**
1.1130 + * Queries whether any threads are waiting to acquire. Note that
1.1131 + * because cancellations due to interrupts and timeouts may occur
1.1132 + * at any time, a {@code true} return does not guarantee that any
1.1133 + * other thread will ever acquire.
1.1134 + *
1.1135 + * <p>In this implementation, this operation returns in
1.1136 + * constant time.
1.1137 + *
1.1138 + * @return {@code true} if there may be other threads waiting to acquire
1.1139 + */
1.1140 + public final boolean hasQueuedThreads() {
1.1141 + return head != tail;
1.1142 + }
1.1143 +
1.1144 + /**
1.1145 + * Queries whether any threads have ever contended to acquire this
1.1146 + * synchronizer; that is if an acquire method has ever blocked.
1.1147 + *
1.1148 + * <p>In this implementation, this operation returns in
1.1149 + * constant time.
1.1150 + *
1.1151 + * @return {@code true} if there has ever been contention
1.1152 + */
1.1153 + public final boolean hasContended() {
1.1154 + return head != null;
1.1155 + }
1.1156 +
1.1157 + /**
1.1158 + * Returns the first (longest-waiting) thread in the queue, or
1.1159 + * {@code null} if no threads are currently queued.
1.1160 + *
1.1161 + * <p>In this implementation, this operation normally returns in
1.1162 + * constant time, but may iterate upon contention if other threads are
1.1163 + * concurrently modifying the queue.
1.1164 + *
1.1165 + * @return the first (longest-waiting) thread in the queue, or
1.1166 + * {@code null} if no threads are currently queued
1.1167 + */
1.1168 + public final Thread getFirstQueuedThread() {
1.1169 + // handle only fast path, else relay
1.1170 + return (head == tail) ? null : fullGetFirstQueuedThread();
1.1171 + }
1.1172 +
1.1173 + /**
1.1174 + * Version of getFirstQueuedThread called when fastpath fails
1.1175 + */
1.1176 + private Thread fullGetFirstQueuedThread() {
1.1177 + /*
1.1178 + * The first node is normally head.next. Try to get its
1.1179 + * thread field, ensuring consistent reads: If thread
1.1180 + * field is nulled out or s.prev is no longer head, then
1.1181 + * some other thread(s) concurrently performed setHead in
1.1182 + * between some of our reads. We try this twice before
1.1183 + * resorting to traversal.
1.1184 + */
1.1185 + Node h, s;
1.1186 + Thread st;
1.1187 + if (((h = head) != null && (s = h.next) != null &&
1.1188 + s.prev == head && (st = s.thread) != null) ||
1.1189 + ((h = head) != null && (s = h.next) != null &&
1.1190 + s.prev == head && (st = s.thread) != null))
1.1191 + return st;
1.1192 +
1.1193 + /*
1.1194 + * Head's next field might not have been set yet, or may have
1.1195 + * been unset after setHead. So we must check to see if tail
1.1196 + * is actually first node. If not, we continue on, safely
1.1197 + * traversing from tail back to head to find first,
1.1198 + * guaranteeing termination.
1.1199 + */
1.1200 +
1.1201 + Node t = tail;
1.1202 + Thread firstThread = null;
1.1203 + while (t != null && t != head) {
1.1204 + Thread tt = t.thread;
1.1205 + if (tt != null)
1.1206 + firstThread = tt;
1.1207 + t = t.prev;
1.1208 + }
1.1209 + return firstThread;
1.1210 + }
1.1211 +
1.1212 + /**
1.1213 + * Returns true if the given thread is currently queued.
1.1214 + *
1.1215 + * <p>This implementation traverses the queue to determine
1.1216 + * presence of the given thread.
1.1217 + *
1.1218 + * @param thread the thread
1.1219 + * @return {@code true} if the given thread is on the queue
1.1220 + * @throws NullPointerException if the thread is null
1.1221 + */
1.1222 + public final boolean isQueued(Thread thread) {
1.1223 + if (thread == null)
1.1224 + throw new NullPointerException();
1.1225 + for (Node p = tail; p != null; p = p.prev)
1.1226 + if (p.thread == thread)
1.1227 + return true;
1.1228 + return false;
1.1229 + }
1.1230 +
1.1231 + /**
1.1232 + * Returns {@code true} if the apparent first queued thread, if one
1.1233 + * exists, is waiting in exclusive mode. If this method returns
1.1234 + * {@code true}, and the current thread is attempting to acquire in
1.1235 + * shared mode (that is, this method is invoked from {@link
1.1236 + * #tryAcquireShared}) then it is guaranteed that the current thread
1.1237 + * is not the first queued thread. Used only as a heuristic in
1.1238 + * ReentrantReadWriteLock.
1.1239 + */
1.1240 + final boolean apparentlyFirstQueuedIsExclusive() {
1.1241 + Node h, s;
1.1242 + return (h = head) != null &&
1.1243 + (s = h.next) != null &&
1.1244 + !s.isShared() &&
1.1245 + s.thread != null;
1.1246 + }
1.1247 +
1.1248 + /**
1.1249 + * Queries whether any threads have been waiting to acquire longer
1.1250 + * than the current thread.
1.1251 + *
1.1252 + * <p>An invocation of this method is equivalent to (but may be
1.1253 + * more efficient than):
1.1254 + * <pre> {@code
1.1255 + * getFirstQueuedThread() != Thread.currentThread() &&
1.1256 + * hasQueuedThreads()}</pre>
1.1257 + *
1.1258 + * <p>Note that because cancellations due to interrupts and
1.1259 + * timeouts may occur at any time, a {@code true} return does not
1.1260 + * guarantee that some other thread will acquire before the current
1.1261 + * thread. Likewise, it is possible for another thread to win a
1.1262 + * race to enqueue after this method has returned {@code false},
1.1263 + * due to the queue being empty.
1.1264 + *
1.1265 + * <p>This method is designed to be used by a fair synchronizer to
1.1266 + * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>.
1.1267 + * Such a synchronizer's {@link #tryAcquire} method should return
1.1268 + * {@code false}, and its {@link #tryAcquireShared} method should
1.1269 + * return a negative value, if this method returns {@code true}
1.1270 + * (unless this is a reentrant acquire). For example, the {@code
1.1271 + * tryAcquire} method for a fair, reentrant, exclusive mode
1.1272 + * synchronizer might look like this:
1.1273 + *
1.1274 + * <pre> {@code
1.1275 + * protected boolean tryAcquire(int arg) {
1.1276 + * if (isHeldExclusively()) {
1.1277 + * // A reentrant acquire; increment hold count
1.1278 + * return true;
1.1279 + * } else if (hasQueuedPredecessors()) {
1.1280 + * return false;
1.1281 + * } else {
1.1282 + * // try to acquire normally
1.1283 + * }
1.1284 + * }}</pre>
1.1285 + *
1.1286 + * @return {@code true} if there is a queued thread preceding the
1.1287 + * current thread, and {@code false} if the current thread
1.1288 + * is at the head of the queue or the queue is empty
1.1289 + * @since 1.7
1.1290 + */
1.1291 + public final boolean hasQueuedPredecessors() {
1.1292 + // The correctness of this depends on head being initialized
1.1293 + // before tail and on head.next being accurate if the current
1.1294 + // thread is first in queue.
1.1295 + Node t = tail; // Read fields in reverse initialization order
1.1296 + Node h = head;
1.1297 + Node s;
1.1298 + return h != t &&
1.1299 + ((s = h.next) == null || s.thread != Thread.currentThread());
1.1300 + }
1.1301 +
1.1302 +
1.1303 + // Instrumentation and monitoring methods
1.1304 +
1.1305 + /**
1.1306 + * Returns an estimate of the number of threads waiting to
1.1307 + * acquire. The value is only an estimate because the number of
1.1308 + * threads may change dynamically while this method traverses
1.1309 + * internal data structures. This method is designed for use in
1.1310 + * monitoring system state, not for synchronization
1.1311 + * control.
1.1312 + *
1.1313 + * @return the estimated number of threads waiting to acquire
1.1314 + */
1.1315 + public final int getQueueLength() {
1.1316 + int n = 0;
1.1317 + for (Node p = tail; p != null; p = p.prev) {
1.1318 + if (p.thread != null)
1.1319 + ++n;
1.1320 + }
1.1321 + return n;
1.1322 + }
1.1323 +
1.1324 + /**
1.1325 + * Returns a collection containing threads that may be waiting to
1.1326 + * acquire. Because the actual set of threads may change
1.1327 + * dynamically while constructing this result, the returned
1.1328 + * collection is only a best-effort estimate. The elements of the
1.1329 + * returned collection are in no particular order. This method is
1.1330 + * designed to facilitate construction of subclasses that provide
1.1331 + * more extensive monitoring facilities.
1.1332 + *
1.1333 + * @return the collection of threads
1.1334 + */
1.1335 + public final Collection<Thread> getQueuedThreads() {
1.1336 + ArrayList<Thread> list = new ArrayList<Thread>();
1.1337 + for (Node p = tail; p != null; p = p.prev) {
1.1338 + Thread t = p.thread;
1.1339 + if (t != null)
1.1340 + list.add(t);
1.1341 + }
1.1342 + return list;
1.1343 + }
1.1344 +
1.1345 + /**
1.1346 + * Returns a collection containing threads that may be waiting to
1.1347 + * acquire in exclusive mode. This has the same properties
1.1348 + * as {@link #getQueuedThreads} except that it only returns
1.1349 + * those threads waiting due to an exclusive acquire.
1.1350 + *
1.1351 + * @return the collection of threads
1.1352 + */
1.1353 + public final Collection<Thread> getExclusiveQueuedThreads() {
1.1354 + ArrayList<Thread> list = new ArrayList<Thread>();
1.1355 + for (Node p = tail; p != null; p = p.prev) {
1.1356 + if (!p.isShared()) {
1.1357 + Thread t = p.thread;
1.1358 + if (t != null)
1.1359 + list.add(t);
1.1360 + }
1.1361 + }
1.1362 + return list;
1.1363 + }
1.1364 +
1.1365 + /**
1.1366 + * Returns a collection containing threads that may be waiting to
1.1367 + * acquire in shared mode. This has the same properties
1.1368 + * as {@link #getQueuedThreads} except that it only returns
1.1369 + * those threads waiting due to a shared acquire.
1.1370 + *
1.1371 + * @return the collection of threads
1.1372 + */
1.1373 + public final Collection<Thread> getSharedQueuedThreads() {
1.1374 + ArrayList<Thread> list = new ArrayList<Thread>();
1.1375 + for (Node p = tail; p != null; p = p.prev) {
1.1376 + if (p.isShared()) {
1.1377 + Thread t = p.thread;
1.1378 + if (t != null)
1.1379 + list.add(t);
1.1380 + }
1.1381 + }
1.1382 + return list;
1.1383 + }
1.1384 +
1.1385 + /**
1.1386 + * Returns a string identifying this synchronizer, as well as its state.
1.1387 + * The state, in brackets, includes the String {@code "State ="}
1.1388 + * followed by the current value of {@link #getState}, and either
1.1389 + * {@code "nonempty"} or {@code "empty"} depending on whether the
1.1390 + * queue is empty.
1.1391 + *
1.1392 + * @return a string identifying this synchronizer, as well as its state
1.1393 + */
1.1394 + public String toString() {
1.1395 + long s = getState();
1.1396 + String q = hasQueuedThreads() ? "non" : "";
1.1397 + return super.toString() +
1.1398 + "[State = " + s + ", " + q + "empty queue]";
1.1399 + }
1.1400 +
1.1401 +
1.1402 + // Internal support methods for Conditions
1.1403 +
1.1404 + /**
1.1405 + * Returns true if a node, always one that was initially placed on
1.1406 + * a condition queue, is now waiting to reacquire on sync queue.
1.1407 + * @param node the node
1.1408 + * @return true if is reacquiring
1.1409 + */
1.1410 + final boolean isOnSyncQueue(Node node) {
1.1411 + if (node.waitStatus == Node.CONDITION || node.prev == null)
1.1412 + return false;
1.1413 + if (node.next != null) // If has successor, it must be on queue
1.1414 + return true;
1.1415 + /*
1.1416 + * node.prev can be non-null, but not yet on queue because
1.1417 + * the CAS to place it on queue can fail. So we have to
1.1418 + * traverse from tail to make sure it actually made it. It
1.1419 + * will always be near the tail in calls to this method, and
1.1420 + * unless the CAS failed (which is unlikely), it will be
1.1421 + * there, so we hardly ever traverse much.
1.1422 + */
1.1423 + return findNodeFromTail(node);
1.1424 + }
1.1425 +
1.1426 + /**
1.1427 + * Returns true if node is on sync queue by searching backwards from tail.
1.1428 + * Called only when needed by isOnSyncQueue.
1.1429 + * @return true if present
1.1430 + */
1.1431 + private boolean findNodeFromTail(Node node) {
1.1432 + Node t = tail;
1.1433 + for (;;) {
1.1434 + if (t == node)
1.1435 + return true;
1.1436 + if (t == null)
1.1437 + return false;
1.1438 + t = t.prev;
1.1439 + }
1.1440 + }
1.1441 +
1.1442 + /**
1.1443 + * Transfers a node from a condition queue onto sync queue.
1.1444 + * Returns true if successful.
1.1445 + * @param node the node
1.1446 + * @return true if successfully transferred (else the node was
1.1447 + * cancelled before signal).
1.1448 + */
1.1449 + final boolean transferForSignal(Node node) {
1.1450 + /*
1.1451 + * If cannot change waitStatus, the node has been cancelled.
1.1452 + */
1.1453 + if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
1.1454 + return false;
1.1455 +
1.1456 + /*
1.1457 + * Splice onto queue and try to set waitStatus of predecessor to
1.1458 + * indicate that thread is (probably) waiting. If cancelled or
1.1459 + * attempt to set waitStatus fails, wake up to resync (in which
1.1460 + * case the waitStatus can be transiently and harmlessly wrong).
1.1461 + */
1.1462 + Node p = enq(node);
1.1463 + int ws = p.waitStatus;
1.1464 + if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
1.1465 + LockSupport.unpark(node.thread);
1.1466 + return true;
1.1467 + }
1.1468 +
1.1469 + /**
1.1470 + * Transfers node, if necessary, to sync queue after a cancelled
1.1471 + * wait. Returns true if thread was cancelled before being
1.1472 + * signalled.
1.1473 + * @param current the waiting thread
1.1474 + * @param node its node
1.1475 + * @return true if cancelled before the node was signalled
1.1476 + */
1.1477 + final boolean transferAfterCancelledWait(Node node) {
1.1478 + if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
1.1479 + enq(node);
1.1480 + return true;
1.1481 + }
1.1482 + /*
1.1483 + * If we lost out to a signal(), then we can't proceed
1.1484 + * until it finishes its enq(). Cancelling during an
1.1485 + * incomplete transfer is both rare and transient, so just
1.1486 + * spin.
1.1487 + */
1.1488 + while (!isOnSyncQueue(node))
1.1489 + Thread.yield();
1.1490 + return false;
1.1491 + }
1.1492 +
1.1493 + /**
1.1494 + * Invokes release with current state value; returns saved state.
1.1495 + * Cancels node and throws exception on failure.
1.1496 + * @param node the condition node for this wait
1.1497 + * @return previous sync state
1.1498 + */
1.1499 + final long fullyRelease(Node node) {
1.1500 + boolean failed = true;
1.1501 + try {
1.1502 + long savedState = getState();
1.1503 + if (release(savedState)) {
1.1504 + failed = false;
1.1505 + return savedState;
1.1506 + } else {
1.1507 + throw new IllegalMonitorStateException();
1.1508 + }
1.1509 + } finally {
1.1510 + if (failed)
1.1511 + node.waitStatus = Node.CANCELLED;
1.1512 + }
1.1513 + }
1.1514 +
1.1515 + // Instrumentation methods for conditions
1.1516 +
1.1517 + /**
1.1518 + * Queries whether the given ConditionObject
1.1519 + * uses this synchronizer as its lock.
1.1520 + *
1.1521 + * @param condition the condition
1.1522 + * @return <tt>true</tt> if owned
1.1523 + * @throws NullPointerException if the condition is null
1.1524 + */
1.1525 + public final boolean owns(ConditionObject condition) {
1.1526 + if (condition == null)
1.1527 + throw new NullPointerException();
1.1528 + return condition.isOwnedBy(this);
1.1529 + }
1.1530 +
1.1531 + /**
1.1532 + * Queries whether any threads are waiting on the given condition
1.1533 + * associated with this synchronizer. Note that because timeouts
1.1534 + * and interrupts may occur at any time, a <tt>true</tt> return
1.1535 + * does not guarantee that a future <tt>signal</tt> will awaken
1.1536 + * any threads. This method is designed primarily for use in
1.1537 + * monitoring of the system state.
1.1538 + *
1.1539 + * @param condition the condition
1.1540 + * @return <tt>true</tt> if there are any waiting threads
1.1541 + * @throws IllegalMonitorStateException if exclusive synchronization
1.1542 + * is not held
1.1543 + * @throws IllegalArgumentException if the given condition is
1.1544 + * not associated with this synchronizer
1.1545 + * @throws NullPointerException if the condition is null
1.1546 + */
1.1547 + public final boolean hasWaiters(ConditionObject condition) {
1.1548 + if (!owns(condition))
1.1549 + throw new IllegalArgumentException("Not owner");
1.1550 + return condition.hasWaiters();
1.1551 + }
1.1552 +
1.1553 + /**
1.1554 + * Returns an estimate of the number of threads waiting on the
1.1555 + * given condition associated with this synchronizer. Note that
1.1556 + * because timeouts and interrupts may occur at any time, the
1.1557 + * estimate serves only as an upper bound on the actual number of
1.1558 + * waiters. This method is designed for use in monitoring of the
1.1559 + * system state, not for synchronization control.
1.1560 + *
1.1561 + * @param condition the condition
1.1562 + * @return the estimated number of waiting threads
1.1563 + * @throws IllegalMonitorStateException if exclusive synchronization
1.1564 + * is not held
1.1565 + * @throws IllegalArgumentException if the given condition is
1.1566 + * not associated with this synchronizer
1.1567 + * @throws NullPointerException if the condition is null
1.1568 + */
1.1569 + public final int getWaitQueueLength(ConditionObject condition) {
1.1570 + if (!owns(condition))
1.1571 + throw new IllegalArgumentException("Not owner");
1.1572 + return condition.getWaitQueueLength();
1.1573 + }
1.1574 +
1.1575 + /**
1.1576 + * Returns a collection containing those threads that may be
1.1577 + * waiting on the given condition associated with this
1.1578 + * synchronizer. Because the actual set of threads may change
1.1579 + * dynamically while constructing this result, the returned
1.1580 + * collection is only a best-effort estimate. The elements of the
1.1581 + * returned collection are in no particular order.
1.1582 + *
1.1583 + * @param condition the condition
1.1584 + * @return the collection of threads
1.1585 + * @throws IllegalMonitorStateException if exclusive synchronization
1.1586 + * is not held
1.1587 + * @throws IllegalArgumentException if the given condition is
1.1588 + * not associated with this synchronizer
1.1589 + * @throws NullPointerException if the condition is null
1.1590 + */
1.1591 + public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1.1592 + if (!owns(condition))
1.1593 + throw new IllegalArgumentException("Not owner");
1.1594 + return condition.getWaitingThreads();
1.1595 + }
1.1596 +
1.1597 + /**
1.1598 + * Condition implementation for a {@link
1.1599 + * AbstractQueuedLongSynchronizer} serving as the basis of a {@link
1.1600 + * Lock} implementation.
1.1601 + *
1.1602 + * <p>Method documentation for this class describes mechanics,
1.1603 + * not behavioral specifications from the point of view of Lock
1.1604 + * and Condition users. Exported versions of this class will in
1.1605 + * general need to be accompanied by documentation describing
1.1606 + * condition semantics that rely on those of the associated
1.1607 + * <tt>AbstractQueuedLongSynchronizer</tt>.
1.1608 + *
1.1609 + * <p>This class is Serializable, but all fields are transient,
1.1610 + * so deserialized conditions have no waiters.
1.1611 + *
1.1612 + * @since 1.6
1.1613 + */
1.1614 + public class ConditionObject implements Condition, java.io.Serializable {
1.1615 + private static final long serialVersionUID = 1173984872572414699L;
1.1616 + /** First node of condition queue. */
1.1617 + private transient Node firstWaiter;
1.1618 + /** Last node of condition queue. */
1.1619 + private transient Node lastWaiter;
1.1620 +
1.1621 + /**
1.1622 + * Creates a new <tt>ConditionObject</tt> instance.
1.1623 + */
1.1624 + public ConditionObject() { }
1.1625 +
1.1626 + // Internal methods
1.1627 +
1.1628 + /**
1.1629 + * Adds a new waiter to wait queue.
1.1630 + * @return its new wait node
1.1631 + */
1.1632 + private Node addConditionWaiter() {
1.1633 + Node t = lastWaiter;
1.1634 + // If lastWaiter is cancelled, clean out.
1.1635 + if (t != null && t.waitStatus != Node.CONDITION) {
1.1636 + unlinkCancelledWaiters();
1.1637 + t = lastWaiter;
1.1638 + }
1.1639 + Node node = new Node(Thread.currentThread(), Node.CONDITION);
1.1640 + if (t == null)
1.1641 + firstWaiter = node;
1.1642 + else
1.1643 + t.nextWaiter = node;
1.1644 + lastWaiter = node;
1.1645 + return node;
1.1646 + }
1.1647 +
1.1648 + /**
1.1649 + * Removes and transfers nodes until hit non-cancelled one or
1.1650 + * null. Split out from signal in part to encourage compilers
1.1651 + * to inline the case of no waiters.
1.1652 + * @param first (non-null) the first node on condition queue
1.1653 + */
1.1654 + private void doSignal(Node first) {
1.1655 + do {
1.1656 + if ( (firstWaiter = first.nextWaiter) == null)
1.1657 + lastWaiter = null;
1.1658 + first.nextWaiter = null;
1.1659 + } while (!transferForSignal(first) &&
1.1660 + (first = firstWaiter) != null);
1.1661 + }
1.1662 +
1.1663 + /**
1.1664 + * Removes and transfers all nodes.
1.1665 + * @param first (non-null) the first node on condition queue
1.1666 + */
1.1667 + private void doSignalAll(Node first) {
1.1668 + lastWaiter = firstWaiter = null;
1.1669 + do {
1.1670 + Node next = first.nextWaiter;
1.1671 + first.nextWaiter = null;
1.1672 + transferForSignal(first);
1.1673 + first = next;
1.1674 + } while (first != null);
1.1675 + }
1.1676 +
1.1677 + /**
1.1678 + * Unlinks cancelled waiter nodes from condition queue.
1.1679 + * Called only while holding lock. This is called when
1.1680 + * cancellation occurred during condition wait, and upon
1.1681 + * insertion of a new waiter when lastWaiter is seen to have
1.1682 + * been cancelled. This method is needed to avoid garbage
1.1683 + * retention in the absence of signals. So even though it may
1.1684 + * require a full traversal, it comes into play only when
1.1685 + * timeouts or cancellations occur in the absence of
1.1686 + * signals. It traverses all nodes rather than stopping at a
1.1687 + * particular target to unlink all pointers to garbage nodes
1.1688 + * without requiring many re-traversals during cancellation
1.1689 + * storms.
1.1690 + */
1.1691 + private void unlinkCancelledWaiters() {
1.1692 + Node t = firstWaiter;
1.1693 + Node trail = null;
1.1694 + while (t != null) {
1.1695 + Node next = t.nextWaiter;
1.1696 + if (t.waitStatus != Node.CONDITION) {
1.1697 + t.nextWaiter = null;
1.1698 + if (trail == null)
1.1699 + firstWaiter = next;
1.1700 + else
1.1701 + trail.nextWaiter = next;
1.1702 + if (next == null)
1.1703 + lastWaiter = trail;
1.1704 + }
1.1705 + else
1.1706 + trail = t;
1.1707 + t = next;
1.1708 + }
1.1709 + }
1.1710 +
1.1711 + // public methods
1.1712 +
1.1713 + /**
1.1714 + * Moves the longest-waiting thread, if one exists, from the
1.1715 + * wait queue for this condition to the wait queue for the
1.1716 + * owning lock.
1.1717 + *
1.1718 + * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1.1719 + * returns {@code false}
1.1720 + */
1.1721 + public final void signal() {
1.1722 + if (!isHeldExclusively())
1.1723 + throw new IllegalMonitorStateException();
1.1724 + Node first = firstWaiter;
1.1725 + if (first != null)
1.1726 + doSignal(first);
1.1727 + }
1.1728 +
1.1729 + /**
1.1730 + * Moves all threads from the wait queue for this condition to
1.1731 + * the wait queue for the owning lock.
1.1732 + *
1.1733 + * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1.1734 + * returns {@code false}
1.1735 + */
1.1736 + public final void signalAll() {
1.1737 + if (!isHeldExclusively())
1.1738 + throw new IllegalMonitorStateException();
1.1739 + Node first = firstWaiter;
1.1740 + if (first != null)
1.1741 + doSignalAll(first);
1.1742 + }
1.1743 +
1.1744 + /**
1.1745 + * Implements uninterruptible condition wait.
1.1746 + * <ol>
1.1747 + * <li> Save lock state returned by {@link #getState}.
1.1748 + * <li> Invoke {@link #release} with
1.1749 + * saved state as argument, throwing
1.1750 + * IllegalMonitorStateException if it fails.
1.1751 + * <li> Block until signalled.
1.1752 + * <li> Reacquire by invoking specialized version of
1.1753 + * {@link #acquire} with saved state as argument.
1.1754 + * </ol>
1.1755 + */
1.1756 + public final void awaitUninterruptibly() {
1.1757 + Node node = addConditionWaiter();
1.1758 + long savedState = fullyRelease(node);
1.1759 + boolean interrupted = false;
1.1760 + while (!isOnSyncQueue(node)) {
1.1761 + LockSupport.park(this);
1.1762 + if (Thread.interrupted())
1.1763 + interrupted = true;
1.1764 + }
1.1765 + if (acquireQueued(node, savedState) || interrupted)
1.1766 + selfInterrupt();
1.1767 + }
1.1768 +
1.1769 + /*
1.1770 + * For interruptible waits, we need to track whether to throw
1.1771 + * InterruptedException, if interrupted while blocked on
1.1772 + * condition, versus reinterrupt current thread, if
1.1773 + * interrupted while blocked waiting to re-acquire.
1.1774 + */
1.1775 +
1.1776 + /** Mode meaning to reinterrupt on exit from wait */
1.1777 + private static final int REINTERRUPT = 1;
1.1778 + /** Mode meaning to throw InterruptedException on exit from wait */
1.1779 + private static final int THROW_IE = -1;
1.1780 +
1.1781 + /**
1.1782 + * Checks for interrupt, returning THROW_IE if interrupted
1.1783 + * before signalled, REINTERRUPT if after signalled, or
1.1784 + * 0 if not interrupted.
1.1785 + */
1.1786 + private int checkInterruptWhileWaiting(Node node) {
1.1787 + return Thread.interrupted() ?
1.1788 + (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
1.1789 + 0;
1.1790 + }
1.1791 +
1.1792 + /**
1.1793 + * Throws InterruptedException, reinterrupts current thread, or
1.1794 + * does nothing, depending on mode.
1.1795 + */
1.1796 + private void reportInterruptAfterWait(int interruptMode)
1.1797 + throws InterruptedException {
1.1798 + if (interruptMode == THROW_IE)
1.1799 + throw new InterruptedException();
1.1800 + else if (interruptMode == REINTERRUPT)
1.1801 + selfInterrupt();
1.1802 + }
1.1803 +
1.1804 + /**
1.1805 + * Implements interruptible condition wait.
1.1806 + * <ol>
1.1807 + * <li> If current thread is interrupted, throw InterruptedException.
1.1808 + * <li> Save lock state returned by {@link #getState}.
1.1809 + * <li> Invoke {@link #release} with
1.1810 + * saved state as argument, throwing
1.1811 + * IllegalMonitorStateException if it fails.
1.1812 + * <li> Block until signalled or interrupted.
1.1813 + * <li> Reacquire by invoking specialized version of
1.1814 + * {@link #acquire} with saved state as argument.
1.1815 + * <li> If interrupted while blocked in step 4, throw InterruptedException.
1.1816 + * </ol>
1.1817 + */
1.1818 + public final void await() throws InterruptedException {
1.1819 + if (Thread.interrupted())
1.1820 + throw new InterruptedException();
1.1821 + Node node = addConditionWaiter();
1.1822 + long savedState = fullyRelease(node);
1.1823 + int interruptMode = 0;
1.1824 + while (!isOnSyncQueue(node)) {
1.1825 + LockSupport.park(this);
1.1826 + if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1.1827 + break;
1.1828 + }
1.1829 + if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1.1830 + interruptMode = REINTERRUPT;
1.1831 + if (node.nextWaiter != null) // clean up if cancelled
1.1832 + unlinkCancelledWaiters();
1.1833 + if (interruptMode != 0)
1.1834 + reportInterruptAfterWait(interruptMode);
1.1835 + }
1.1836 +
1.1837 + /**
1.1838 + * Implements timed condition wait.
1.1839 + * <ol>
1.1840 + * <li> If current thread is interrupted, throw InterruptedException.
1.1841 + * <li> Save lock state returned by {@link #getState}.
1.1842 + * <li> Invoke {@link #release} with
1.1843 + * saved state as argument, throwing
1.1844 + * IllegalMonitorStateException if it fails.
1.1845 + * <li> Block until signalled, interrupted, or timed out.
1.1846 + * <li> Reacquire by invoking specialized version of
1.1847 + * {@link #acquire} with saved state as argument.
1.1848 + * <li> If interrupted while blocked in step 4, throw InterruptedException.
1.1849 + * </ol>
1.1850 + */
1.1851 + public final long awaitNanos(long nanosTimeout)
1.1852 + throws InterruptedException {
1.1853 + if (Thread.interrupted())
1.1854 + throw new InterruptedException();
1.1855 + Node node = addConditionWaiter();
1.1856 + long savedState = fullyRelease(node);
1.1857 + long lastTime = System.nanoTime();
1.1858 + int interruptMode = 0;
1.1859 + while (!isOnSyncQueue(node)) {
1.1860 + if (nanosTimeout <= 0L) {
1.1861 + transferAfterCancelledWait(node);
1.1862 + break;
1.1863 + }
1.1864 + LockSupport.parkNanos(this, nanosTimeout);
1.1865 + if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1.1866 + break;
1.1867 +
1.1868 + long now = System.nanoTime();
1.1869 + nanosTimeout -= now - lastTime;
1.1870 + lastTime = now;
1.1871 + }
1.1872 + if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1.1873 + interruptMode = REINTERRUPT;
1.1874 + if (node.nextWaiter != null)
1.1875 + unlinkCancelledWaiters();
1.1876 + if (interruptMode != 0)
1.1877 + reportInterruptAfterWait(interruptMode);
1.1878 + return nanosTimeout - (System.nanoTime() - lastTime);
1.1879 + }
1.1880 +
1.1881 + /**
1.1882 + * Implements absolute timed condition wait.
1.1883 + * <ol>
1.1884 + * <li> If current thread is interrupted, throw InterruptedException.
1.1885 + * <li> Save lock state returned by {@link #getState}.
1.1886 + * <li> Invoke {@link #release} with
1.1887 + * saved state as argument, throwing
1.1888 + * IllegalMonitorStateException if it fails.
1.1889 + * <li> Block until signalled, interrupted, or timed out.
1.1890 + * <li> Reacquire by invoking specialized version of
1.1891 + * {@link #acquire} with saved state as argument.
1.1892 + * <li> If interrupted while blocked in step 4, throw InterruptedException.
1.1893 + * <li> If timed out while blocked in step 4, return false, else true.
1.1894 + * </ol>
1.1895 + */
1.1896 + public final boolean awaitUntil(Date deadline)
1.1897 + throws InterruptedException {
1.1898 + if (deadline == null)
1.1899 + throw new NullPointerException();
1.1900 + long abstime = deadline.getTime();
1.1901 + if (Thread.interrupted())
1.1902 + throw new InterruptedException();
1.1903 + Node node = addConditionWaiter();
1.1904 + long savedState = fullyRelease(node);
1.1905 + boolean timedout = false;
1.1906 + int interruptMode = 0;
1.1907 + while (!isOnSyncQueue(node)) {
1.1908 + if (System.currentTimeMillis() > abstime) {
1.1909 + timedout = transferAfterCancelledWait(node);
1.1910 + break;
1.1911 + }
1.1912 + LockSupport.parkUntil(this, abstime);
1.1913 + if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1.1914 + break;
1.1915 + }
1.1916 + if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1.1917 + interruptMode = REINTERRUPT;
1.1918 + if (node.nextWaiter != null)
1.1919 + unlinkCancelledWaiters();
1.1920 + if (interruptMode != 0)
1.1921 + reportInterruptAfterWait(interruptMode);
1.1922 + return !timedout;
1.1923 + }
1.1924 +
1.1925 + /**
1.1926 + * Implements timed condition wait.
1.1927 + * <ol>
1.1928 + * <li> If current thread is interrupted, throw InterruptedException.
1.1929 + * <li> Save lock state returned by {@link #getState}.
1.1930 + * <li> Invoke {@link #release} with
1.1931 + * saved state as argument, throwing
1.1932 + * IllegalMonitorStateException if it fails.
1.1933 + * <li> Block until signalled, interrupted, or timed out.
1.1934 + * <li> Reacquire by invoking specialized version of
1.1935 + * {@link #acquire} with saved state as argument.
1.1936 + * <li> If interrupted while blocked in step 4, throw InterruptedException.
1.1937 + * <li> If timed out while blocked in step 4, return false, else true.
1.1938 + * </ol>
1.1939 + */
1.1940 + public final boolean await(long time, TimeUnit unit)
1.1941 + throws InterruptedException {
1.1942 + if (unit == null)
1.1943 + throw new NullPointerException();
1.1944 + long nanosTimeout = unit.toNanos(time);
1.1945 + if (Thread.interrupted())
1.1946 + throw new InterruptedException();
1.1947 + Node node = addConditionWaiter();
1.1948 + long savedState = fullyRelease(node);
1.1949 + long lastTime = System.nanoTime();
1.1950 + boolean timedout = false;
1.1951 + int interruptMode = 0;
1.1952 + while (!isOnSyncQueue(node)) {
1.1953 + if (nanosTimeout <= 0L) {
1.1954 + timedout = transferAfterCancelledWait(node);
1.1955 + break;
1.1956 + }
1.1957 + if (nanosTimeout >= spinForTimeoutThreshold)
1.1958 + LockSupport.parkNanos(this, nanosTimeout);
1.1959 + if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1.1960 + break;
1.1961 + long now = System.nanoTime();
1.1962 + nanosTimeout -= now - lastTime;
1.1963 + lastTime = now;
1.1964 + }
1.1965 + if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1.1966 + interruptMode = REINTERRUPT;
1.1967 + if (node.nextWaiter != null)
1.1968 + unlinkCancelledWaiters();
1.1969 + if (interruptMode != 0)
1.1970 + reportInterruptAfterWait(interruptMode);
1.1971 + return !timedout;
1.1972 + }
1.1973 +
1.1974 + // support for instrumentation
1.1975 +
1.1976 + /**
1.1977 + * Returns true if this condition was created by the given
1.1978 + * synchronization object.
1.1979 + *
1.1980 + * @return {@code true} if owned
1.1981 + */
1.1982 + final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1.1983 + return sync == AbstractQueuedLongSynchronizer.this;
1.1984 + }
1.1985 +
1.1986 + /**
1.1987 + * Queries whether any threads are waiting on this condition.
1.1988 + * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters}.
1.1989 + *
1.1990 + * @return {@code true} if there are any waiting threads
1.1991 + * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1.1992 + * returns {@code false}
1.1993 + */
1.1994 + protected final boolean hasWaiters() {
1.1995 + if (!isHeldExclusively())
1.1996 + throw new IllegalMonitorStateException();
1.1997 + for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1.1998 + if (w.waitStatus == Node.CONDITION)
1.1999 + return true;
1.2000 + }
1.2001 + return false;
1.2002 + }
1.2003 +
1.2004 + /**
1.2005 + * Returns an estimate of the number of threads waiting on
1.2006 + * this condition.
1.2007 + * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength}.
1.2008 + *
1.2009 + * @return the estimated number of waiting threads
1.2010 + * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1.2011 + * returns {@code false}
1.2012 + */
1.2013 + protected final int getWaitQueueLength() {
1.2014 + if (!isHeldExclusively())
1.2015 + throw new IllegalMonitorStateException();
1.2016 + int n = 0;
1.2017 + for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1.2018 + if (w.waitStatus == Node.CONDITION)
1.2019 + ++n;
1.2020 + }
1.2021 + return n;
1.2022 + }
1.2023 +
1.2024 + /**
1.2025 + * Returns a collection containing those threads that may be
1.2026 + * waiting on this Condition.
1.2027 + * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads}.
1.2028 + *
1.2029 + * @return the collection of threads
1.2030 + * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1.2031 + * returns {@code false}
1.2032 + */
1.2033 + protected final Collection<Thread> getWaitingThreads() {
1.2034 + if (!isHeldExclusively())
1.2035 + throw new IllegalMonitorStateException();
1.2036 + ArrayList<Thread> list = new ArrayList<Thread>();
1.2037 + for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1.2038 + if (w.waitStatus == Node.CONDITION) {
1.2039 + Thread t = w.thread;
1.2040 + if (t != null)
1.2041 + list.add(t);
1.2042 + }
1.2043 + }
1.2044 + return list;
1.2045 + }
1.2046 + }
1.2047 +
1.2048 + /**
1.2049 + * Setup to support compareAndSet. We need to natively implement
1.2050 + * this here: For the sake of permitting future enhancements, we
1.2051 + * cannot explicitly subclass AtomicLong, which would be
1.2052 + * efficient and useful otherwise. So, as the lesser of evils, we
1.2053 + * natively implement using hotspot intrinsics API. And while we
1.2054 + * are at it, we do the same for other CASable fields (which could
1.2055 + * otherwise be done with atomic field updaters).
1.2056 + */
1.2057 + private static final Unsafe unsafe = Unsafe.getUnsafe();
1.2058 + private static final long stateOffset;
1.2059 + private static final long headOffset;
1.2060 + private static final long tailOffset;
1.2061 + private static final long waitStatusOffset;
1.2062 + private static final long nextOffset;
1.2063 +
1.2064 + static {
1.2065 + try {
1.2066 + stateOffset = unsafe.objectFieldOffset
1.2067 + (AbstractQueuedLongSynchronizer.class.getDeclaredField("state"));
1.2068 + headOffset = unsafe.objectFieldOffset
1.2069 + (AbstractQueuedLongSynchronizer.class.getDeclaredField("head"));
1.2070 + tailOffset = unsafe.objectFieldOffset
1.2071 + (AbstractQueuedLongSynchronizer.class.getDeclaredField("tail"));
1.2072 + waitStatusOffset = unsafe.objectFieldOffset
1.2073 + (Node.class.getDeclaredField("waitStatus"));
1.2074 + nextOffset = unsafe.objectFieldOffset
1.2075 + (Node.class.getDeclaredField("next"));
1.2076 +
1.2077 + } catch (Exception ex) { throw new Error(ex); }
1.2078 + }
1.2079 +
1.2080 + /**
1.2081 + * CAS head field. Used only by enq.
1.2082 + */
1.2083 + private final boolean compareAndSetHead(Node update) {
1.2084 + return unsafe.compareAndSwapObject(this, headOffset, null, update);
1.2085 + }
1.2086 +
1.2087 + /**
1.2088 + * CAS tail field. Used only by enq.
1.2089 + */
1.2090 + private final boolean compareAndSetTail(Node expect, Node update) {
1.2091 + return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
1.2092 + }
1.2093 +
1.2094 + /**
1.2095 + * CAS waitStatus field of a node.
1.2096 + */
1.2097 + private static final boolean compareAndSetWaitStatus(Node node,
1.2098 + int expect,
1.2099 + int update) {
1.2100 + return unsafe.compareAndSwapInt(node, waitStatusOffset,
1.2101 + expect, update);
1.2102 + }
1.2103 +
1.2104 + /**
1.2105 + * CAS next field of a node.
1.2106 + */
1.2107 + private static final boolean compareAndSetNext(Node node,
1.2108 + Node expect,
1.2109 + Node update) {
1.2110 + return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
1.2111 + }
1.2112 +}