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