diff options
Diffstat (limited to 'openjdk/java/util/concurrent/locks/AbstractQueuedSynchronizer.java')
| -rw-r--r-- | openjdk/java/util/concurrent/locks/AbstractQueuedSynchronizer.java | 2299 |
1 files changed, 0 insertions, 2299 deletions
diff --git a/openjdk/java/util/concurrent/locks/AbstractQueuedSynchronizer.java b/openjdk/java/util/concurrent/locks/AbstractQueuedSynchronizer.java deleted file mode 100644 index 4a42dc11..00000000 --- a/openjdk/java/util/concurrent/locks/AbstractQueuedSynchronizer.java +++ /dev/null @@ -1,2299 +0,0 @@ -/* - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. Oracle designates this - * particular file as subject to the "Classpath" exception as provided - * by Oracle in the LICENSE file that accompanied this code. - * - * This code is distributed in the hope that it will be useful, but WITHOUT - * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or - * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License - * version 2 for more details (a copy is included in the LICENSE file that - * accompanied this code). - * - * You should have received a copy of the GNU General Public License version - * 2 along with this work; if not, write to the Free Software Foundation, - * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA - * or visit www.oracle.com if you need additional information or have any - * questions. - */ - -/* - * This file is available under and governed by the GNU General Public - * License version 2 only, as published by the Free Software Foundation. - * However, the following notice accompanied the original version of this - * file: - * - * Written by Doug Lea with assistance from members of JCP JSR-166 - * Expert Group and released to the public domain, as explained at - * http://creativecommons.org/publicdomain/zero/1.0/ - */ - -package java.util.concurrent.locks; -import java.util.*; -import java.util.concurrent.*; -import java.util.concurrent.atomic.*; - -/** - * Provides a framework for implementing blocking locks and related - * synchronizers (semaphores, events, etc) that rely on - * first-in-first-out (FIFO) wait queues. This class is designed to - * be a useful basis for most kinds of synchronizers that rely on a - * single atomic <tt>int</tt> value to represent state. Subclasses - * must define the protected methods that change this state, and which - * define what that state means in terms of this object being acquired - * or released. Given these, the other methods in this class carry - * out all queuing and blocking mechanics. Subclasses can maintain - * other state fields, but only the atomically updated <tt>int</tt> - * value manipulated using methods {@link #getState}, {@link - * #setState} and {@link #compareAndSetState} is tracked with respect - * to synchronization. - * - * <p>Subclasses should be defined as non-public internal helper - * classes that are used to implement the synchronization properties - * of their enclosing class. Class - * <tt>AbstractQueuedSynchronizer</tt> does not implement any - * synchronization interface. Instead it defines methods such as - * {@link #acquireInterruptibly} that can be invoked as - * appropriate by concrete locks and related synchronizers to - * implement their public methods. - * - * <p>This class supports either or both a default <em>exclusive</em> - * mode and a <em>shared</em> mode. When acquired in exclusive mode, - * attempted acquires by other threads cannot succeed. Shared mode - * acquires by multiple threads may (but need not) succeed. This class - * does not "understand" these differences except in the - * mechanical sense that when a shared mode acquire succeeds, the next - * waiting thread (if one exists) must also determine whether it can - * acquire as well. Threads waiting in the different modes share the - * same FIFO queue. Usually, implementation subclasses support only - * one of these modes, but both can come into play for example in a - * {@link ReadWriteLock}. Subclasses that support only exclusive or - * only shared modes need not define the methods supporting the unused mode. - * - * <p>This class defines a nested {@link ConditionObject} class that - * can be used as a {@link Condition} implementation by subclasses - * supporting exclusive mode for which method {@link - * #isHeldExclusively} reports whether synchronization is exclusively - * held with respect to the current thread, method {@link #release} - * invoked with the current {@link #getState} value fully releases - * this object, and {@link #acquire}, given this saved state value, - * eventually restores this object to its previous acquired state. No - * <tt>AbstractQueuedSynchronizer</tt> method otherwise creates such a - * condition, so if this constraint cannot be met, do not use it. The - * behavior of {@link ConditionObject} depends of course on the - * semantics of its synchronizer implementation. - * - * <p>This class provides inspection, instrumentation, and monitoring - * methods for the internal queue, as well as similar methods for - * condition objects. These can be exported as desired into classes - * using an <tt>AbstractQueuedSynchronizer</tt> for their - * synchronization mechanics. - * - * <p>Serialization of this class stores only the underlying atomic - * integer maintaining state, so deserialized objects have empty - * thread queues. Typical subclasses requiring serializability will - * define a <tt>readObject</tt> method that restores this to a known - * initial state upon deserialization. - * - * <h3>Usage</h3> - * - * <p>To use this class as the basis of a synchronizer, redefine the - * following methods, as applicable, by inspecting and/or modifying - * the synchronization state using {@link #getState}, {@link - * #setState} and/or {@link #compareAndSetState}: - * - * <ul> - * <li> {@link #tryAcquire} - * <li> {@link #tryRelease} - * <li> {@link #tryAcquireShared} - * <li> {@link #tryReleaseShared} - * <li> {@link #isHeldExclusively} - *</ul> - * - * Each of these methods by default throws {@link - * UnsupportedOperationException}. Implementations of these methods - * must be internally thread-safe, and should in general be short and - * not block. Defining these methods is the <em>only</em> supported - * means of using this class. All other methods are declared - * <tt>final</tt> because they cannot be independently varied. - * - * <p>You may also find the inherited methods from {@link - * AbstractOwnableSynchronizer} useful to keep track of the thread - * owning an exclusive synchronizer. You are encouraged to use them - * -- this enables monitoring and diagnostic tools to assist users in - * determining which threads hold locks. - * - * <p>Even though this class is based on an internal FIFO queue, it - * does not automatically enforce FIFO acquisition policies. The core - * of exclusive synchronization takes the form: - * - * <pre> - * Acquire: - * while (!tryAcquire(arg)) { - * <em>enqueue thread if it is not already queued</em>; - * <em>possibly block current thread</em>; - * } - * - * Release: - * if (tryRelease(arg)) - * <em>unblock the first queued thread</em>; - * </pre> - * - * (Shared mode is similar but may involve cascading signals.) - * - * <p><a name="barging">Because checks in acquire are invoked before - * enqueuing, a newly acquiring thread may <em>barge</em> ahead of - * others that are blocked and queued. However, you can, if desired, - * define <tt>tryAcquire</tt> and/or <tt>tryAcquireShared</tt> to - * disable barging by internally invoking one or more of the inspection - * methods, thereby providing a <em>fair</em> FIFO acquisition order. - * In particular, most fair synchronizers can define <tt>tryAcquire</tt> - * to return <tt>false</tt> if {@link #hasQueuedPredecessors} (a method - * specifically designed to be used by fair synchronizers) returns - * <tt>true</tt>. Other variations are possible. - * - * <p>Throughput and scalability are generally highest for the - * default barging (also known as <em>greedy</em>, - * <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy. - * While this is not guaranteed to be fair or starvation-free, earlier - * queued threads are allowed to recontend before later queued - * threads, and each recontention has an unbiased chance to succeed - * against incoming threads. Also, while acquires do not - * "spin" in the usual sense, they may perform multiple - * invocations of <tt>tryAcquire</tt> interspersed with other - * computations before blocking. This gives most of the benefits of - * spins when exclusive synchronization is only briefly held, without - * most of the liabilities when it isn't. If so desired, you can - * augment this by preceding calls to acquire methods with - * "fast-path" checks, possibly prechecking {@link #hasContended} - * and/or {@link #hasQueuedThreads} to only do so if the synchronizer - * is likely not to be contended. - * - * <p>This class provides an efficient and scalable basis for - * synchronization in part by specializing its range of use to - * synchronizers that can rely on <tt>int</tt> state, acquire, and - * release parameters, and an internal FIFO wait queue. When this does - * not suffice, you can build synchronizers from a lower level using - * {@link java.util.concurrent.atomic atomic} classes, your own custom - * {@link java.util.Queue} classes, and {@link LockSupport} blocking - * support. - * - * <h3>Usage Examples</h3> - * - * <p>Here is a non-reentrant mutual exclusion lock class that uses - * the value zero to represent the unlocked state, and one to - * represent the locked state. While a non-reentrant lock - * does not strictly require recording of the current owner - * thread, this class does so anyway to make usage easier to monitor. - * It also supports conditions and exposes - * one of the instrumentation methods: - * - * <pre> - * class Mutex implements Lock, java.io.Serializable { - * - * // Our internal helper class - * private static class Sync extends AbstractQueuedSynchronizer { - * // Report whether in locked state - * protected boolean isHeldExclusively() { - * return getState() == 1; - * } - * - * // Acquire the lock if state is zero - * public boolean tryAcquire(int acquires) { - * assert acquires == 1; // Otherwise unused - * if (compareAndSetState(0, 1)) { - * setExclusiveOwnerThread(Thread.currentThread()); - * return true; - * } - * return false; - * } - * - * // Release the lock by setting state to zero - * protected boolean tryRelease(int releases) { - * assert releases == 1; // Otherwise unused - * if (getState() == 0) throw new IllegalMonitorStateException(); - * setExclusiveOwnerThread(null); - * setState(0); - * return true; - * } - * - * // Provide a Condition - * Condition newCondition() { return new ConditionObject(); } - * - * // Deserialize properly - * private void readObject(ObjectInputStream s) - * throws IOException, ClassNotFoundException { - * s.defaultReadObject(); - * setState(0); // reset to unlocked state - * } - * } - * - * // The sync object does all the hard work. We just forward to it. - * private final Sync sync = new Sync(); - * - * public void lock() { sync.acquire(1); } - * public boolean tryLock() { return sync.tryAcquire(1); } - * public void unlock() { sync.release(1); } - * public Condition newCondition() { return sync.newCondition(); } - * public boolean isLocked() { return sync.isHeldExclusively(); } - * public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); } - * public void lockInterruptibly() throws InterruptedException { - * sync.acquireInterruptibly(1); - * } - * public boolean tryLock(long timeout, TimeUnit unit) - * throws InterruptedException { - * return sync.tryAcquireNanos(1, unit.toNanos(timeout)); - * } - * } - * </pre> - * - * <p>Here is a latch class that is like a {@link CountDownLatch} - * except that it only requires a single <tt>signal</tt> to - * fire. Because a latch is non-exclusive, it uses the <tt>shared</tt> - * acquire and release methods. - * - * <pre> - * class BooleanLatch { - * - * private static class Sync extends AbstractQueuedSynchronizer { - * boolean isSignalled() { return getState() != 0; } - * - * protected int tryAcquireShared(int ignore) { - * return isSignalled() ? 1 : -1; - * } - * - * protected boolean tryReleaseShared(int ignore) { - * setState(1); - * return true; - * } - * } - * - * private final Sync sync = new Sync(); - * public boolean isSignalled() { return sync.isSignalled(); } - * public void signal() { sync.releaseShared(1); } - * public void await() throws InterruptedException { - * sync.acquireSharedInterruptibly(1); - * } - * } - * </pre> - * - * @since 1.5 - * @author Doug Lea - */ -public abstract class AbstractQueuedSynchronizer - extends AbstractOwnableSynchronizer - implements java.io.Serializable { - - private static final long serialVersionUID = 7373984972572414691L; - - /** - * Creates a new <tt>AbstractQueuedSynchronizer</tt> instance - * with initial synchronization state of zero. - */ - protected AbstractQueuedSynchronizer() { } - - /** - * Wait queue node class. - * - * <p>The wait queue is a variant of a "CLH" (Craig, Landin, and - * Hagersten) lock queue. CLH locks are normally used for - * spinlocks. We instead use them for blocking synchronizers, but - * use the same basic tactic of holding some of the control - * information about a thread in the predecessor of its node. A - * "status" field in each node keeps track of whether a thread - * should block. A node is signalled when its predecessor - * releases. Each node of the queue otherwise serves as a - * specific-notification-style monitor holding a single waiting - * thread. The status field does NOT control whether threads are - * granted locks etc though. A thread may try to acquire if it is - * first in the queue. But being first does not guarantee success; - * it only gives the right to contend. So the currently released - * contender thread may need to rewait. - * - * <p>To enqueue into a CLH lock, you atomically splice it in as new - * tail. To dequeue, you just set the head field. - * <pre> - * +------+ prev +-----+ +-----+ - * head | | <---- | | <---- | | tail - * +------+ +-----+ +-----+ - * </pre> - * - * <p>Insertion into a CLH queue requires only a single atomic - * operation on "tail", so there is a simple atomic point of - * demarcation from unqueued to queued. Similarly, dequeing - * involves only updating the "head". However, it takes a bit - * more work for nodes to determine who their successors are, - * in part to deal with possible cancellation due to timeouts - * and interrupts. - * - * <p>The "prev" links (not used in original CLH locks), are mainly - * needed to handle cancellation. If a node is cancelled, its - * successor is (normally) relinked to a non-cancelled - * predecessor. For explanation of similar mechanics in the case - * of spin locks, see the papers by Scott and Scherer at - * http://www.cs.rochester.edu/u/scott/synchronization/ - * - * <p>We also use "next" links to implement blocking mechanics. - * The thread id for each node is kept in its own node, so a - * predecessor signals the next node to wake up by traversing - * next link to determine which thread it is. Determination of - * successor must avoid races with newly queued nodes to set - * the "next" fields of their predecessors. This is solved - * when necessary by checking backwards from the atomically - * updated "tail" when a node's successor appears to be null. - * (Or, said differently, the next-links are an optimization - * so that we don't usually need a backward scan.) - * - * <p>Cancellation introduces some conservatism to the basic - * algorithms. Since we must poll for cancellation of other - * nodes, we can miss noticing whether a cancelled node is - * ahead or behind us. This is dealt with by always unparking - * successors upon cancellation, allowing them to stabilize on - * a new predecessor, unless we can identify an uncancelled - * predecessor who will carry this responsibility. - * - * <p>CLH queues need a dummy header node to get started. But - * we don't create them on construction, because it would be wasted - * effort if there is never contention. Instead, the node - * is constructed and head and tail pointers are set upon first - * contention. - * - * <p>Threads waiting on Conditions use the same nodes, but - * use an additional link. Conditions only need to link nodes - * in simple (non-concurrent) linked queues because they are - * only accessed when exclusively held. Upon await, a node is - * inserted into a condition queue. Upon signal, the node is - * transferred to the main queue. A special value of status - * field is used to mark which queue a node is on. - * - * <p>Thanks go to Dave Dice, Mark Moir, Victor Luchangco, Bill - * Scherer and Michael Scott, along with members of JSR-166 - * expert group, for helpful ideas, discussions, and critiques - * on the design of this class. - */ - static final class Node { - static final AtomicReferenceFieldUpdater<Node, Node> nextUpdater = AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "next"); - /** Marker to indicate a node is waiting in shared mode */ - static final Node SHARED = new Node(); - /** Marker to indicate a node is waiting in exclusive mode */ - static final Node EXCLUSIVE = null; - - /** waitStatus value to indicate thread has cancelled */ - static final int CANCELLED = 1; - /** waitStatus value to indicate successor's thread needs unparking */ - static final int SIGNAL = -1; - /** waitStatus value to indicate thread is waiting on condition */ - static final int CONDITION = -2; - /** - * waitStatus value to indicate the next acquireShared should - * unconditionally propagate - */ - static final int PROPAGATE = -3; - - /** - * Status field, taking on only the values: - * SIGNAL: The successor of this node is (or will soon be) - * blocked (via park), so the current node must - * unpark its successor when it releases or - * cancels. To avoid races, acquire methods must - * first indicate they need a signal, - * then retry the atomic acquire, and then, - * on failure, block. - * CANCELLED: This node is cancelled due to timeout or interrupt. - * Nodes never leave this state. In particular, - * a thread with cancelled node never again blocks. - * CONDITION: This node is currently on a condition queue. - * It will not be used as a sync queue node - * until transferred, at which time the status - * will be set to 0. (Use of this value here has - * nothing to do with the other uses of the - * field, but simplifies mechanics.) - * PROPAGATE: A releaseShared should be propagated to other - * nodes. This is set (for head node only) in - * doReleaseShared to ensure propagation - * continues, even if other operations have - * since intervened. - * 0: None of the above - * - * The values are arranged numerically to simplify use. - * Non-negative values mean that a node doesn't need to - * signal. So, most code doesn't need to check for particular - * values, just for sign. - * - * The field is initialized to 0 for normal sync nodes, and - * CONDITION for condition nodes. It is modified using CAS - * (or when possible, unconditional volatile writes). - */ - volatile int waitStatus; - - /** - * Link to predecessor node that current node/thread relies on - * for checking waitStatus. Assigned during enqueing, and nulled - * out (for sake of GC) only upon dequeuing. Also, upon - * cancellation of a predecessor, we short-circuit while - * finding a non-cancelled one, which will always exist - * because the head node is never cancelled: A node becomes - * head only as a result of successful acquire. A - * cancelled thread never succeeds in acquiring, and a thread only - * cancels itself, not any other node. - */ - volatile Node prev; - - /** - * Link to the successor node that the current node/thread - * unparks upon release. Assigned during enqueuing, adjusted - * when bypassing cancelled predecessors, and nulled out (for - * sake of GC) when dequeued. The enq operation does not - * assign next field of a predecessor until after attachment, - * so seeing a null next field does not necessarily mean that - * node is at end of queue. However, if a next field appears - * to be null, we can scan prev's from the tail to - * double-check. The next field of cancelled nodes is set to - * point to the node itself instead of null, to make life - * easier for isOnSyncQueue. - */ - volatile Node next; - - /** - * The thread that enqueued this node. Initialized on - * construction and nulled out after use. - */ - volatile Thread thread; - - /** - * Link to next node waiting on condition, or the special - * value SHARED. Because condition queues are accessed only - * when holding in exclusive mode, we just need a simple - * linked queue to hold nodes while they are waiting on - * conditions. They are then transferred to the queue to - * re-acquire. And because conditions can only be exclusive, - * we save a field by using special value to indicate shared - * mode. - */ - Node nextWaiter; - - /** - * Returns true if node is waiting in shared mode - */ - final boolean isShared() { - return nextWaiter == SHARED; - } - - /** - * Returns previous node, or throws NullPointerException if null. - * Use when predecessor cannot be null. The null check could - * be elided, but is present to help the VM. - * - * @return the predecessor of this node - */ - final Node predecessor() throws NullPointerException { - Node p = prev; - if (p == null) - throw new NullPointerException(); - else - return p; - } - - Node() { // Used to establish initial head or SHARED marker - } - - Node(Thread thread, Node mode) { // Used by addWaiter - this.nextWaiter = mode; - this.thread = thread; - } - - Node(Thread thread, int waitStatus) { // Used by Condition - this.waitStatus = waitStatus; - this.thread = thread; - } - } - - /** - * Head of the wait queue, lazily initialized. Except for - * initialization, it is modified only via method setHead. Note: - * If head exists, its waitStatus is guaranteed not to be - * CANCELLED. - */ - private transient volatile Node head; - - /** - * Tail of the wait queue, lazily initialized. Modified only via - * method enq to add new wait node. - */ - private transient volatile Node tail; - - /** - * The synchronization state. - */ - private volatile int state; - - /** - * Returns the current value of synchronization state. - * This operation has memory semantics of a <tt>volatile</tt> read. - * @return current state value - */ - protected final int getState() { - return state; - } - - /** - * Sets the value of synchronization state. - * This operation has memory semantics of a <tt>volatile</tt> write. - * @param newState the new state value - */ - protected final void setState(int newState) { - state = newState; - } - - /** - * Atomically sets synchronization state to the given updated - * value if the current state value equals the expected value. - * This operation has memory semantics of a <tt>volatile</tt> read - * and write. - * - * @param expect the expected value - * @param update the new value - * @return true if successful. False return indicates that the actual - * value was not equal to the expected value. - */ - protected final native boolean compareAndSetState(int expect, int update); // implemented in map.xml - - // Queuing utilities - - /** - * The number of nanoseconds for which it is faster to spin - * rather than to use timed park. A rough estimate suffices - * to improve responsiveness with very short timeouts. - */ - static final long spinForTimeoutThreshold = 1000L; - - /** - * Inserts node into queue, initializing if necessary. See picture above. - * @param node the node to insert - * @return node's predecessor - */ - private Node enq(final Node node) { - for (;;) { - Node t = tail; - if (t == null) { // Must initialize - if (compareAndSetHead(new Node())) - tail = head; - } else { - node.prev = t; - if (compareAndSetTail(t, node)) { - t.next = node; - return t; - } - } - } - } - - /** - * Creates and enqueues node for current thread and given mode. - * - * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared - * @return the new node - */ - private Node addWaiter(Node mode) { - Node node = new Node(Thread.currentThread(), mode); - // Try the fast path of enq; backup to full enq on failure - Node pred = tail; - if (pred != null) { - node.prev = pred; - if (compareAndSetTail(pred, node)) { - pred.next = node; - return node; - } - } - enq(node); - return node; - } - - /** - * Sets head of queue to be node, thus dequeuing. Called only by - * acquire methods. Also nulls out unused fields for sake of GC - * and to suppress unnecessary signals and traversals. - * - * @param node the node - */ - private void setHead(Node node) { - head = node; - node.thread = null; - node.prev = null; - } - - /** - * Wakes up node's successor, if one exists. - * - * @param node the node - */ - private void unparkSuccessor(Node node) { - /* - * If status is negative (i.e., possibly needing signal) try - * to clear in anticipation of signalling. It is OK if this - * fails or if status is changed by waiting thread. - */ - int ws = node.waitStatus; - if (ws < 0) - compareAndSetWaitStatus(node, ws, 0); - - /* - * Thread to unpark is held in successor, which is normally - * just the next node. But if cancelled or apparently null, - * traverse backwards from tail to find the actual - * non-cancelled successor. - */ - Node s = node.next; - if (s == null || s.waitStatus > 0) { - s = null; - for (Node t = tail; t != null && t != node; t = t.prev) - if (t.waitStatus <= 0) - s = t; - } - if (s != null) - LockSupport.unpark(s.thread); - } - - /** - * Release action for shared mode -- signal successor and ensure - * propagation. (Note: For exclusive mode, release just amounts - * to calling unparkSuccessor of head if it needs signal.) - */ - private void doReleaseShared() { - /* - * Ensure that a release propagates, even if there are other - * in-progress acquires/releases. This proceeds in the usual - * way of trying to unparkSuccessor of head if it needs - * signal. But if it does not, status is set to PROPAGATE to - * ensure that upon release, propagation continues. - * Additionally, we must loop in case a new node is added - * while we are doing this. Also, unlike other uses of - * unparkSuccessor, we need to know if CAS to reset status - * fails, if so rechecking. - */ - for (;;) { - Node h = head; - if (h != null && h != tail) { - int ws = h.waitStatus; - if (ws == Node.SIGNAL) { - if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0)) - continue; // loop to recheck cases - unparkSuccessor(h); - } - else if (ws == 0 && - !compareAndSetWaitStatus(h, 0, Node.PROPAGATE)) - continue; // loop on failed CAS - } - if (h == head) // loop if head changed - break; - } - } - - /** - * Sets head of queue, and checks if successor may be waiting - * in shared mode, if so propagating if either propagate > 0 or - * PROPAGATE status was set. - * - * @param node the node - * @param propagate the return value from a tryAcquireShared - */ - private void setHeadAndPropagate(Node node, int propagate) { - Node h = head; // Record old head for check below - setHead(node); - /* - * Try to signal next queued node if: - * Propagation was indicated by caller, - * or was recorded (as h.waitStatus) by a previous operation - * (note: this uses sign-check of waitStatus because - * PROPAGATE status may transition to SIGNAL.) - * and - * The next node is waiting in shared mode, - * or we don't know, because it appears null - * - * The conservatism in both of these checks may cause - * unnecessary wake-ups, but only when there are multiple - * racing acquires/releases, so most need signals now or soon - * anyway. - */ - if (propagate > 0 || h == null || h.waitStatus < 0) { - Node s = node.next; - if (s == null || s.isShared()) - doReleaseShared(); - } - } - - // Utilities for various versions of acquire - - /** - * Cancels an ongoing attempt to acquire. - * - * @param node the node - */ - private void cancelAcquire(Node node) { - // Ignore if node doesn't exist - if (node == null) - return; - - node.thread = null; - - // Skip cancelled predecessors - Node pred = node.prev; - while (pred.waitStatus > 0) - node.prev = pred = pred.prev; - - // predNext is the apparent node to unsplice. CASes below will - // fail if not, in which case, we lost race vs another cancel - // or signal, so no further action is necessary. - Node predNext = pred.next; - - // Can use unconditional write instead of CAS here. - // After this atomic step, other Nodes can skip past us. - // Before, we are free of interference from other threads. - node.waitStatus = Node.CANCELLED; - - // If we are the tail, remove ourselves. - if (node == tail && compareAndSetTail(node, pred)) { - compareAndSetNext(pred, predNext, null); - } else { - // If successor needs signal, try to set pred's next-link - // so it will get one. Otherwise wake it up to propagate. - int ws; - if (pred != head && - ((ws = pred.waitStatus) == Node.SIGNAL || - (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) && - pred.thread != null) { - Node next = node.next; - if (next != null && next.waitStatus <= 0) - compareAndSetNext(pred, predNext, next); - } else { - unparkSuccessor(node); - } - - node.next = node; // help GC - } - } - - /** - * Checks and updates status for a node that failed to acquire. - * Returns true if thread should block. This is the main signal - * control in all acquire loops. Requires that pred == node.prev - * - * @param pred node's predecessor holding status - * @param node the node - * @return {@code true} if thread should block - */ - private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) { - int ws = pred.waitStatus; - if (ws == Node.SIGNAL) - /* - * This node has already set status asking a release - * to signal it, so it can safely park. - */ - return true; - if (ws > 0) { - /* - * Predecessor was cancelled. Skip over predecessors and - * indicate retry. - */ - do { - node.prev = pred = pred.prev; - } while (pred.waitStatus > 0); - pred.next = node; - } else { - /* - * waitStatus must be 0 or PROPAGATE. Indicate that we - * need a signal, but don't park yet. Caller will need to - * retry to make sure it cannot acquire before parking. - */ - compareAndSetWaitStatus(pred, ws, Node.SIGNAL); - } - return false; - } - - /** - * Convenience method to interrupt current thread. - */ - private static void selfInterrupt() { - Thread.currentThread().interrupt(); - } - - /** - * Convenience method to park and then check if interrupted - * - * @return {@code true} if interrupted - */ - private final boolean parkAndCheckInterrupt() { - LockSupport.park(this); - return Thread.interrupted(); - } - - /* - * Various flavors of acquire, varying in exclusive/shared and - * control modes. Each is mostly the same, but annoyingly - * different. Only a little bit of factoring is possible due to - * interactions of exception mechanics (including ensuring that we - * cancel if tryAcquire throws exception) and other control, at - * least not without hurting performance too much. - */ - - /** - * Acquires in exclusive uninterruptible mode for thread already in - * queue. Used by condition wait methods as well as acquire. - * - * @param node the node - * @param arg the acquire argument - * @return {@code true} if interrupted while waiting - */ - final boolean acquireQueued(final Node node, int arg) { - boolean failed = true; - try { - boolean interrupted = false; - for (;;) { - final Node p = node.predecessor(); - if (p == head && tryAcquire(arg)) { - setHead(node); - p.next = null; // help GC - failed = false; - return interrupted; - } - if (shouldParkAfterFailedAcquire(p, node) && - parkAndCheckInterrupt()) - interrupted = true; - } - } finally { - if (failed) - cancelAcquire(node); - } - } - - /** - * Acquires in exclusive interruptible mode. - * @param arg the acquire argument - */ - private void doAcquireInterruptibly(int arg) - throws InterruptedException { - final Node node = addWaiter(Node.EXCLUSIVE); - boolean failed = true; - try { - for (;;) { - final Node p = node.predecessor(); - if (p == head && tryAcquire(arg)) { - setHead(node); - p.next = null; // help GC - failed = false; - return; - } - if (shouldParkAfterFailedAcquire(p, node) && - parkAndCheckInterrupt()) - throw new InterruptedException(); - } - } finally { - if (failed) - cancelAcquire(node); - } - } - - /** - * Acquires in exclusive timed mode. - * - * @param arg the acquire argument - * @param nanosTimeout max wait time - * @return {@code true} if acquired - */ - private boolean doAcquireNanos(int arg, long nanosTimeout) - throws InterruptedException { - long lastTime = System.nanoTime(); - final Node node = addWaiter(Node.EXCLUSIVE); - boolean failed = true; - try { - for (;;) { - final Node p = node.predecessor(); - if (p == head && tryAcquire(arg)) { - setHead(node); - p.next = null; // help GC - failed = false; - return true; - } - if (nanosTimeout <= 0) - return false; - if (shouldParkAfterFailedAcquire(p, node) && - nanosTimeout > spinForTimeoutThreshold) - LockSupport.parkNanos(this, nanosTimeout); - long now = System.nanoTime(); - nanosTimeout -= now - lastTime; - lastTime = now; - if (Thread.interrupted()) - throw new InterruptedException(); - } - } finally { - if (failed) - cancelAcquire(node); - } - } - - /** - * Acquires in shared uninterruptible mode. - * @param arg the acquire argument - */ - private void doAcquireShared(int arg) { - final Node node = addWaiter(Node.SHARED); - boolean failed = true; - try { - boolean interrupted = false; - for (;;) { - final Node p = node.predecessor(); - if (p == head) { - int r = tryAcquireShared(arg); - if (r >= 0) { - setHeadAndPropagate(node, r); - p.next = null; // help GC - if (interrupted) - selfInterrupt(); - failed = false; - return; - } - } - if (shouldParkAfterFailedAcquire(p, node) && - parkAndCheckInterrupt()) - interrupted = true; - } - } finally { - if (failed) - cancelAcquire(node); - } - } - - /** - * Acquires in shared interruptible mode. - * @param arg the acquire argument - */ - private void doAcquireSharedInterruptibly(int arg) - throws InterruptedException { - final Node node = addWaiter(Node.SHARED); - boolean failed = true; - try { - for (;;) { - final Node p = node.predecessor(); - if (p == head) { - int r = tryAcquireShared(arg); - if (r >= 0) { - setHeadAndPropagate(node, r); - p.next = null; // help GC - failed = false; - return; - } - } - if (shouldParkAfterFailedAcquire(p, node) && - parkAndCheckInterrupt()) - throw new InterruptedException(); - } - } finally { - if (failed) - cancelAcquire(node); - } - } - - /** - * Acquires in shared timed mode. - * - * @param arg the acquire argument - * @param nanosTimeout max wait time - * @return {@code true} if acquired - */ - private boolean doAcquireSharedNanos(int arg, long nanosTimeout) - throws InterruptedException { - - long lastTime = System.nanoTime(); - final Node node = addWaiter(Node.SHARED); - boolean failed = true; - try { - for (;;) { - final Node p = node.predecessor(); - if (p == head) { - int r = tryAcquireShared(arg); - if (r >= 0) { - setHeadAndPropagate(node, r); - p.next = null; // help GC - failed = false; - return true; - } - } - if (nanosTimeout <= 0) - return false; - if (shouldParkAfterFailedAcquire(p, node) && - nanosTimeout > spinForTimeoutThreshold) - LockSupport.parkNanos(this, nanosTimeout); - long now = System.nanoTime(); - nanosTimeout -= now - lastTime; - lastTime = now; - if (Thread.interrupted()) - throw new InterruptedException(); - } - } finally { - if (failed) - cancelAcquire(node); - } - } - - // Main exported methods - - /** - * Attempts to acquire in exclusive mode. This method should query - * if the state of the object permits it to be acquired in the - * exclusive mode, and if so to acquire it. - * - * <p>This method is always invoked by the thread performing - * acquire. If this method reports failure, the acquire method - * may queue the thread, if it is not already queued, until it is - * signalled by a release from some other thread. This can be used - * to implement method {@link Lock#tryLock()}. - * - * <p>The default - * implementation throws {@link UnsupportedOperationException}. - * - * @param arg the acquire argument. This value is always the one - * passed to an acquire method, or is the value saved on entry - * to a condition wait. The value is otherwise uninterpreted - * and can represent anything you like. - * @return {@code true} if successful. Upon success, this object has - * been acquired. - * @throws IllegalMonitorStateException if acquiring would place this - * synchronizer in an illegal state. This exception must be - * thrown in a consistent fashion for synchronization to work - * correctly. - * @throws UnsupportedOperationException if exclusive mode is not supported - */ - protected boolean tryAcquire(int arg) { - throw new UnsupportedOperationException(); - } - - /** - * Attempts to set the state to reflect a release in exclusive - * mode. - * - * <p>This method is always invoked by the thread performing release. - * - * <p>The default implementation throws - * {@link UnsupportedOperationException}. - * - * @param arg the release argument. This value is always the one - * passed to a release method, or the current state value upon - * entry to a condition wait. The value is otherwise - * uninterpreted and can represent anything you like. - * @return {@code true} if this object is now in a fully released - * state, so that any waiting threads may attempt to acquire; - * and {@code false} otherwise. - * @throws IllegalMonitorStateException if releasing would place this - * synchronizer in an illegal state. This exception must be - * thrown in a consistent fashion for synchronization to work - * correctly. - * @throws UnsupportedOperationException if exclusive mode is not supported - */ - protected boolean tryRelease(int arg) { - throw new UnsupportedOperationException(); - } - - /** - * Attempts to acquire in shared mode. This method should query if - * the state of the object permits it to be acquired in the shared - * mode, and if so to acquire it. - * - * <p>This method is always invoked by the thread performing - * acquire. If this method reports failure, the acquire method - * may queue the thread, if it is not already queued, until it is - * signalled by a release from some other thread. - * - * <p>The default implementation throws {@link - * UnsupportedOperationException}. - * - * @param arg the acquire argument. This value is always the one - * passed to an acquire method, or is the value saved on entry - * to a condition wait. The value is otherwise uninterpreted - * and can represent anything you like. - * @return a negative value on failure; zero if acquisition in shared - * mode succeeded but no subsequent shared-mode acquire can - * succeed; and a positive value if acquisition in shared - * mode succeeded and subsequent shared-mode acquires might - * also succeed, in which case a subsequent waiting thread - * must check availability. (Support for three different - * return values enables this method to be used in contexts - * where acquires only sometimes act exclusively.) Upon - * success, this object has been acquired. - * @throws IllegalMonitorStateException if acquiring would place this - * synchronizer in an illegal state. This exception must be - * thrown in a consistent fashion for synchronization to work - * correctly. - * @throws UnsupportedOperationException if shared mode is not supported - */ - protected int tryAcquireShared(int arg) { - throw new UnsupportedOperationException(); - } - - /** - * Attempts to set the state to reflect a release in shared mode. - * - * <p>This method is always invoked by the thread performing release. - * - * <p>The default implementation throws - * {@link UnsupportedOperationException}. - * - * @param arg the release argument. This value is always the one - * passed to a release method, or the current state value upon - * entry to a condition wait. The value is otherwise - * uninterpreted and can represent anything you like. - * @return {@code true} if this release of shared mode may permit a - * waiting acquire (shared or exclusive) to succeed; and - * {@code false} otherwise - * @throws IllegalMonitorStateException if releasing would place this - * synchronizer in an illegal state. This exception must be - * thrown in a consistent fashion for synchronization to work - * correctly. - * @throws UnsupportedOperationException if shared mode is not supported - */ - protected boolean tryReleaseShared(int arg) { - throw new UnsupportedOperationException(); - } - - /** - * Returns {@code true} if synchronization is held exclusively with - * respect to the current (calling) thread. This method is invoked - * upon each call to a non-waiting {@link ConditionObject} method. - * (Waiting methods instead invoke {@link #release}.) - * - * <p>The default implementation throws {@link - * UnsupportedOperationException}. This method is invoked - * internally only within {@link ConditionObject} methods, so need - * not be defined if conditions are not used. - * - * @return {@code true} if synchronization is held exclusively; - * {@code false} otherwise - * @throws UnsupportedOperationException if conditions are not supported - */ - protected boolean isHeldExclusively() { - throw new UnsupportedOperationException(); - } - - /** - * Acquires in exclusive mode, ignoring interrupts. Implemented - * by invoking at least once {@link #tryAcquire}, - * returning on success. Otherwise the thread is queued, possibly - * repeatedly blocking and unblocking, invoking {@link - * #tryAcquire} until success. This method can be used - * to implement method {@link Lock#lock}. - * - * @param arg the acquire argument. This value is conveyed to - * {@link #tryAcquire} but is otherwise uninterpreted and - * can represent anything you like. - */ - public final void acquire(int arg) { - if (!tryAcquire(arg) && - acquireQueued(addWaiter(Node.EXCLUSIVE), arg)) - selfInterrupt(); - } - - /** - * Acquires in exclusive mode, aborting if interrupted. - * Implemented by first checking interrupt status, then invoking - * at least once {@link #tryAcquire}, returning on - * success. Otherwise the thread is queued, possibly repeatedly - * blocking and unblocking, invoking {@link #tryAcquire} - * until success or the thread is interrupted. This method can be - * used to implement method {@link Lock#lockInterruptibly}. - * - * @param arg the acquire argument. This value is conveyed to - * {@link #tryAcquire} but is otherwise uninterpreted and - * can represent anything you like. - * @throws InterruptedException if the current thread is interrupted - */ - public final void acquireInterruptibly(int arg) - throws InterruptedException { - if (Thread.interrupted()) - throw new InterruptedException(); - if (!tryAcquire(arg)) - doAcquireInterruptibly(arg); - } - - /** - * Attempts to acquire in exclusive mode, aborting if interrupted, - * and failing if the given timeout elapses. Implemented by first - * checking interrupt status, then invoking at least once {@link - * #tryAcquire}, returning on success. Otherwise, the thread is - * queued, possibly repeatedly blocking and unblocking, invoking - * {@link #tryAcquire} until success or the thread is interrupted - * or the timeout elapses. This method can be used to implement - * method {@link Lock#tryLock(long, TimeUnit)}. - * - * @param arg the acquire argument. This value is conveyed to - * {@link #tryAcquire} but is otherwise uninterpreted and - * can represent anything you like. - * @param nanosTimeout the maximum number of nanoseconds to wait - * @return {@code true} if acquired; {@code false} if timed out - * @throws InterruptedException if the current thread is interrupted - */ - public final boolean tryAcquireNanos(int arg, long nanosTimeout) - throws InterruptedException { - if (Thread.interrupted()) - throw new InterruptedException(); - return tryAcquire(arg) || - doAcquireNanos(arg, nanosTimeout); - } - - /** - * Releases in exclusive mode. Implemented by unblocking one or - * more threads if {@link #tryRelease} returns true. - * This method can be used to implement method {@link Lock#unlock}. - * - * @param arg the release argument. This value is conveyed to - * {@link #tryRelease} but is otherwise uninterpreted and - * can represent anything you like. - * @return the value returned from {@link #tryRelease} - */ - public final boolean release(int arg) { - if (tryRelease(arg)) { - Node h = head; - if (h != null && h.waitStatus != 0) - unparkSuccessor(h); - return true; - } - return false; - } - - /** - * Acquires in shared mode, ignoring interrupts. Implemented by - * first invoking at least once {@link #tryAcquireShared}, - * returning on success. Otherwise the thread is queued, possibly - * repeatedly blocking and unblocking, invoking {@link - * #tryAcquireShared} until success. - * - * @param arg the acquire argument. This value is conveyed to - * {@link #tryAcquireShared} but is otherwise uninterpreted - * and can represent anything you like. - */ - public final void acquireShared(int arg) { - if (tryAcquireShared(arg) < 0) - doAcquireShared(arg); - } - - /** - * Acquires in shared mode, aborting if interrupted. Implemented - * by first checking interrupt status, then invoking at least once - * {@link #tryAcquireShared}, returning on success. Otherwise the - * thread is queued, possibly repeatedly blocking and unblocking, - * invoking {@link #tryAcquireShared} until success or the thread - * is interrupted. - * @param arg the acquire argument - * This value is conveyed to {@link #tryAcquireShared} but is - * otherwise uninterpreted and can represent anything - * you like. - * @throws InterruptedException if the current thread is interrupted - */ - public final void acquireSharedInterruptibly(int arg) - throws InterruptedException { - if (Thread.interrupted()) - throw new InterruptedException(); - if (tryAcquireShared(arg) < 0) - doAcquireSharedInterruptibly(arg); - } - - /** - * Attempts to acquire in shared mode, aborting if interrupted, and - * failing if the given timeout elapses. Implemented by first - * checking interrupt status, then invoking at least once {@link - * #tryAcquireShared}, returning on success. Otherwise, the - * thread is queued, possibly repeatedly blocking and unblocking, - * invoking {@link #tryAcquireShared} until success or the thread - * is interrupted or the timeout elapses. - * - * @param arg the acquire argument. This value is conveyed to - * {@link #tryAcquireShared} but is otherwise uninterpreted - * and can represent anything you like. - * @param nanosTimeout the maximum number of nanoseconds to wait - * @return {@code true} if acquired; {@code false} if timed out - * @throws InterruptedException if the current thread is interrupted - */ - public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout) - throws InterruptedException { - if (Thread.interrupted()) - throw new InterruptedException(); - return tryAcquireShared(arg) >= 0 || - doAcquireSharedNanos(arg, nanosTimeout); - } - - /** - * Releases in shared mode. Implemented by unblocking one or more - * threads if {@link #tryReleaseShared} returns true. - * - * @param arg the release argument. This value is conveyed to - * {@link #tryReleaseShared} but is otherwise uninterpreted - * and can represent anything you like. - * @return the value returned from {@link #tryReleaseShared} - */ - public final boolean releaseShared(int arg) { - if (tryReleaseShared(arg)) { - doReleaseShared(); - return true; - } - return false; - } - - // Queue inspection methods - - /** - * Queries whether any threads are waiting to acquire. Note that - * because cancellations due to interrupts and timeouts may occur - * at any time, a {@code true} return does not guarantee that any - * other thread will ever acquire. - * - * <p>In this implementation, this operation returns in - * constant time. - * - * @return {@code true} if there may be other threads waiting to acquire - */ - public final boolean hasQueuedThreads() { - return head != tail; - } - - /** - * Queries whether any threads have ever contended to acquire this - * synchronizer; that is if an acquire method has ever blocked. - * - * <p>In this implementation, this operation returns in - * constant time. - * - * @return {@code true} if there has ever been contention - */ - public final boolean hasContended() { - return head != null; - } - - /** - * Returns the first (longest-waiting) thread in the queue, or - * {@code null} if no threads are currently queued. - * - * <p>In this implementation, this operation normally returns in - * constant time, but may iterate upon contention if other threads are - * concurrently modifying the queue. - * - * @return the first (longest-waiting) thread in the queue, or - * {@code null} if no threads are currently queued - */ - public final Thread getFirstQueuedThread() { - // handle only fast path, else relay - return (head == tail) ? null : fullGetFirstQueuedThread(); - } - - /** - * Version of getFirstQueuedThread called when fastpath fails - */ - private Thread fullGetFirstQueuedThread() { - /* - * The first node is normally head.next. Try to get its - * thread field, ensuring consistent reads: If thread - * field is nulled out or s.prev is no longer head, then - * some other thread(s) concurrently performed setHead in - * between some of our reads. We try this twice before - * resorting to traversal. - */ - Node h, s; - Thread st; - if (((h = head) != null && (s = h.next) != null && - s.prev == head && (st = s.thread) != null) || - ((h = head) != null && (s = h.next) != null && - s.prev == head && (st = s.thread) != null)) - return st; - - /* - * Head's next field might not have been set yet, or may have - * been unset after setHead. So we must check to see if tail - * is actually first node. If not, we continue on, safely - * traversing from tail back to head to find first, - * guaranteeing termination. - */ - - Node t = tail; - Thread firstThread = null; - while (t != null && t != head) { - Thread tt = t.thread; - if (tt != null) - firstThread = tt; - t = t.prev; - } - return firstThread; - } - - /** - * Returns true if the given thread is currently queued. - * - * <p>This implementation traverses the queue to determine - * presence of the given thread. - * - * @param thread the thread - * @return {@code true} if the given thread is on the queue - * @throws NullPointerException if the thread is null - */ - public final boolean isQueued(Thread thread) { - if (thread == null) - throw new NullPointerException(); - for (Node p = tail; p != null; p = p.prev) - if (p.thread == thread) - return true; - return false; - } - - /** - * Returns {@code true} if the apparent first queued thread, if one - * exists, is waiting in exclusive mode. If this method returns - * {@code true}, and the current thread is attempting to acquire in - * shared mode (that is, this method is invoked from {@link - * #tryAcquireShared}) then it is guaranteed that the current thread - * is not the first queued thread. Used only as a heuristic in - * ReentrantReadWriteLock. - */ - final boolean apparentlyFirstQueuedIsExclusive() { - Node h, s; - return (h = head) != null && - (s = h.next) != null && - !s.isShared() && - s.thread != null; - } - - /** - * Queries whether any threads have been waiting to acquire longer - * than the current thread. - * - * <p>An invocation of this method is equivalent to (but may be - * more efficient than): - * <pre> {@code - * getFirstQueuedThread() != Thread.currentThread() && - * hasQueuedThreads()}</pre> - * - * <p>Note that because cancellations due to interrupts and - * timeouts may occur at any time, a {@code true} return does not - * guarantee that some other thread will acquire before the current - * thread. Likewise, it is possible for another thread to win a - * race to enqueue after this method has returned {@code false}, - * due to the queue being empty. - * - * <p>This method is designed to be used by a fair synchronizer to - * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>. - * Such a synchronizer's {@link #tryAcquire} method should return - * {@code false}, and its {@link #tryAcquireShared} method should - * return a negative value, if this method returns {@code true} - * (unless this is a reentrant acquire). For example, the {@code - * tryAcquire} method for a fair, reentrant, exclusive mode - * synchronizer might look like this: - * - * <pre> {@code - * protected boolean tryAcquire(int arg) { - * if (isHeldExclusively()) { - * // A reentrant acquire; increment hold count - * return true; - * } else if (hasQueuedPredecessors()) { - * return false; - * } else { - * // try to acquire normally - * } - * }}</pre> - * - * @return {@code true} if there is a queued thread preceding the - * current thread, and {@code false} if the current thread - * is at the head of the queue or the queue is empty - * @since 1.7 - */ - public final boolean hasQueuedPredecessors() { - // The correctness of this depends on head being initialized - // before tail and on head.next being accurate if the current - // thread is first in queue. - Node t = tail; // Read fields in reverse initialization order - Node h = head; - Node s; - return h != t && - ((s = h.next) == null || s.thread != Thread.currentThread()); - } - - - // Instrumentation and monitoring methods - - /** - * Returns an estimate of the number of threads waiting to - * acquire. The value is only an estimate because the number of - * threads may change dynamically while this method traverses - * internal data structures. This method is designed for use in - * monitoring system state, not for synchronization - * control. - * - * @return the estimated number of threads waiting to acquire - */ - public final int getQueueLength() { - int n = 0; - for (Node p = tail; p != null; p = p.prev) { - if (p.thread != null) - ++n; - } - return n; - } - - /** - * Returns a collection containing threads that may be waiting to - * acquire. Because the actual set of threads may change - * dynamically while constructing this result, the returned - * collection is only a best-effort estimate. The elements of the - * returned collection are in no particular order. This method is - * designed to facilitate construction of subclasses that provide - * more extensive monitoring facilities. - * - * @return the collection of threads - */ - public final Collection<Thread> getQueuedThreads() { - ArrayList<Thread> list = new ArrayList<Thread>(); - for (Node p = tail; p != null; p = p.prev) { - Thread t = p.thread; - if (t != null) - list.add(t); - } - return list; - } - - /** - * Returns a collection containing threads that may be waiting to - * acquire in exclusive mode. This has the same properties - * as {@link #getQueuedThreads} except that it only returns - * those threads waiting due to an exclusive acquire. - * - * @return the collection of threads - */ - public final Collection<Thread> getExclusiveQueuedThreads() { - ArrayList<Thread> list = new ArrayList<Thread>(); - for (Node p = tail; p != null; p = p.prev) { - if (!p.isShared()) { - Thread t = p.thread; - if (t != null) - list.add(t); - } - } - return list; - } - - /** - * Returns a collection containing threads that may be waiting to - * acquire in shared mode. This has the same properties - * as {@link #getQueuedThreads} except that it only returns - * those threads waiting due to a shared acquire. - * - * @return the collection of threads - */ - public final Collection<Thread> getSharedQueuedThreads() { - ArrayList<Thread> list = new ArrayList<Thread>(); - for (Node p = tail; p != null; p = p.prev) { - if (p.isShared()) { - Thread t = p.thread; - if (t != null) - list.add(t); - } - } - return list; - } - - /** - * Returns a string identifying this synchronizer, as well as its state. - * The state, in brackets, includes the String {@code "State ="} - * followed by the current value of {@link #getState}, and either - * {@code "nonempty"} or {@code "empty"} depending on whether the - * queue is empty. - * - * @return a string identifying this synchronizer, as well as its state - */ - public String toString() { - int s = getState(); - String q = hasQueuedThreads() ? "non" : ""; - return super.toString() + - "[State = " + s + ", " + q + "empty queue]"; - } - - - // Internal support methods for Conditions - - /** - * Returns true if a node, always one that was initially placed on - * a condition queue, is now waiting to reacquire on sync queue. - * @param node the node - * @return true if is reacquiring - */ - final boolean isOnSyncQueue(Node node) { - if (node.waitStatus == Node.CONDITION || node.prev == null) - return false; - if (node.next != null) // If has successor, it must be on queue - return true; - /* - * node.prev can be non-null, but not yet on queue because - * the CAS to place it on queue can fail. So we have to - * traverse from tail to make sure it actually made it. It - * will always be near the tail in calls to this method, and - * unless the CAS failed (which is unlikely), it will be - * there, so we hardly ever traverse much. - */ - return findNodeFromTail(node); - } - - /** - * Returns true if node is on sync queue by searching backwards from tail. - * Called only when needed by isOnSyncQueue. - * @return true if present - */ - private boolean findNodeFromTail(Node node) { - Node t = tail; - for (;;) { - if (t == node) - return true; - if (t == null) - return false; - t = t.prev; - } - } - - /** - * Transfers a node from a condition queue onto sync queue. - * Returns true if successful. - * @param node the node - * @return true if successfully transferred (else the node was - * cancelled before signal). - */ - final boolean transferForSignal(Node node) { - /* - * If cannot change waitStatus, the node has been cancelled. - */ - if (!compareAndSetWaitStatus(node, Node.CONDITION, 0)) - return false; - - /* - * Splice onto queue and try to set waitStatus of predecessor to - * indicate that thread is (probably) waiting. If cancelled or - * attempt to set waitStatus fails, wake up to resync (in which - * case the waitStatus can be transiently and harmlessly wrong). - */ - Node p = enq(node); - int ws = p.waitStatus; - if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL)) - LockSupport.unpark(node.thread); - return true; - } - - /** - * Transfers node, if necessary, to sync queue after a cancelled - * wait. Returns true if thread was cancelled before being - * signalled. - * @param current the waiting thread - * @param node its node - * @return true if cancelled before the node was signalled - */ - final boolean transferAfterCancelledWait(Node node) { - if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) { - enq(node); - return true; - } - /* - * If we lost out to a signal(), then we can't proceed - * until it finishes its enq(). Cancelling during an - * incomplete transfer is both rare and transient, so just - * spin. - */ - while (!isOnSyncQueue(node)) - Thread.yield(); - return false; - } - - /** - * Invokes release with current state value; returns saved state. - * Cancels node and throws exception on failure. - * @param node the condition node for this wait - * @return previous sync state - */ - final int fullyRelease(Node node) { - boolean failed = true; - try { - int savedState = getState(); - if (release(savedState)) { - failed = false; - return savedState; - } else { - throw new IllegalMonitorStateException(); - } - } finally { - if (failed) - node.waitStatus = Node.CANCELLED; - } - } - - // Instrumentation methods for conditions - - /** - * Queries whether the given ConditionObject - * uses this synchronizer as its lock. - * - * @param condition the condition - * @return <tt>true</tt> if owned - * @throws NullPointerException if the condition is null - */ - public final boolean owns(ConditionObject condition) { - if (condition == null) - throw new NullPointerException(); - return condition.isOwnedBy(this); - } - - /** - * Queries whether any threads are waiting on the given condition - * associated with this synchronizer. Note that because timeouts - * and interrupts may occur at any time, a <tt>true</tt> return - * does not guarantee that a future <tt>signal</tt> will awaken - * any threads. This method is designed primarily for use in - * monitoring of the system state. - * - * @param condition the condition - * @return <tt>true</tt> if there are any waiting threads - * @throws IllegalMonitorStateException if exclusive synchronization - * is not held - * @throws IllegalArgumentException if the given condition is - * not associated with this synchronizer - * @throws NullPointerException if the condition is null - */ - public final boolean hasWaiters(ConditionObject condition) { - if (!owns(condition)) - throw new IllegalArgumentException("Not owner"); - return condition.hasWaiters(); - } - - /** - * Returns an estimate of the number of threads waiting on the - * given condition associated with this synchronizer. Note that - * because timeouts and interrupts may occur at any time, the - * estimate serves only as an upper bound on the actual number of - * waiters. This method is designed for use in monitoring of the - * system state, not for synchronization control. - * - * @param condition the condition - * @return the estimated number of waiting threads - * @throws IllegalMonitorStateException if exclusive synchronization - * is not held - * @throws IllegalArgumentException if the given condition is - * not associated with this synchronizer - * @throws NullPointerException if the condition is null - */ - public final int getWaitQueueLength(ConditionObject condition) { - if (!owns(condition)) - throw new IllegalArgumentException("Not owner"); - return condition.getWaitQueueLength(); - } - - /** - * Returns a collection containing those threads that may be - * waiting on the given condition associated with this - * synchronizer. Because the actual set of threads may change - * dynamically while constructing this result, the returned - * collection is only a best-effort estimate. The elements of the - * returned collection are in no particular order. - * - * @param condition the condition - * @return the collection of threads - * @throws IllegalMonitorStateException if exclusive synchronization - * is not held - * @throws IllegalArgumentException if the given condition is - * not associated with this synchronizer - * @throws NullPointerException if the condition is null - */ - public final Collection<Thread> getWaitingThreads(ConditionObject condition) { - if (!owns(condition)) - throw new IllegalArgumentException("Not owner"); - return condition.getWaitingThreads(); - } - - /** - * Condition implementation for a {@link - * AbstractQueuedSynchronizer} serving as the basis of a {@link - * Lock} implementation. - * - * <p>Method documentation for this class describes mechanics, - * not behavioral specifications from the point of view of Lock - * and Condition users. Exported versions of this class will in - * general need to be accompanied by documentation describing - * condition semantics that rely on those of the associated - * <tt>AbstractQueuedSynchronizer</tt>. - * - * <p>This class is Serializable, but all fields are transient, - * so deserialized conditions have no waiters. - */ - public class ConditionObject implements Condition, java.io.Serializable { - private static final long serialVersionUID = 1173984872572414699L; - /** First node of condition queue. */ - private transient Node firstWaiter; - /** Last node of condition queue. */ - private transient Node lastWaiter; - - /** - * Creates a new <tt>ConditionObject</tt> instance. - */ - public ConditionObject() { } - - // Internal methods - - /** - * Adds a new waiter to wait queue. - * @return its new wait node - */ - private Node addConditionWaiter() { - Node t = lastWaiter; - // If lastWaiter is cancelled, clean out. - if (t != null && t.waitStatus != Node.CONDITION) { - unlinkCancelledWaiters(); - t = lastWaiter; - } - Node node = new Node(Thread.currentThread(), Node.CONDITION); - if (t == null) - firstWaiter = node; - else - t.nextWaiter = node; - lastWaiter = node; - return node; - } - - /** - * Removes and transfers nodes until hit non-cancelled one or - * null. Split out from signal in part to encourage compilers - * to inline the case of no waiters. - * @param first (non-null) the first node on condition queue - */ - private void doSignal(Node first) { - do { - if ( (firstWaiter = first.nextWaiter) == null) - lastWaiter = null; - first.nextWaiter = null; - } while (!transferForSignal(first) && - (first = firstWaiter) != null); - } - - /** - * Removes and transfers all nodes. - * @param first (non-null) the first node on condition queue - */ - private void doSignalAll(Node first) { - lastWaiter = firstWaiter = null; - do { - Node next = first.nextWaiter; - first.nextWaiter = null; - transferForSignal(first); - first = next; - } while (first != null); - } - - /** - * Unlinks cancelled waiter nodes from condition queue. - * Called only while holding lock. This is called when - * cancellation occurred during condition wait, and upon - * insertion of a new waiter when lastWaiter is seen to have - * been cancelled. This method is needed to avoid garbage - * retention in the absence of signals. So even though it may - * require a full traversal, it comes into play only when - * timeouts or cancellations occur in the absence of - * signals. It traverses all nodes rather than stopping at a - * particular target to unlink all pointers to garbage nodes - * without requiring many re-traversals during cancellation - * storms. - */ - private void unlinkCancelledWaiters() { - Node t = firstWaiter; - Node trail = null; - while (t != null) { - Node next = t.nextWaiter; - if (t.waitStatus != Node.CONDITION) { - t.nextWaiter = null; - if (trail == null) - firstWaiter = next; - else - trail.nextWaiter = next; - if (next == null) - lastWaiter = trail; - } - else - trail = t; - t = next; - } - } - - // public methods - - /** - * Moves the longest-waiting thread, if one exists, from the - * wait queue for this condition to the wait queue for the - * owning lock. - * - * @throws IllegalMonitorStateException if {@link #isHeldExclusively} - * returns {@code false} - */ - public final void signal() { - if (!isHeldExclusively()) - throw new IllegalMonitorStateException(); - Node first = firstWaiter; - if (first != null) - doSignal(first); - } - - /** - * Moves all threads from the wait queue for this condition to - * the wait queue for the owning lock. - * - * @throws IllegalMonitorStateException if {@link #isHeldExclusively} - * returns {@code false} - */ - public final void signalAll() { - if (!isHeldExclusively()) - throw new IllegalMonitorStateException(); - Node first = firstWaiter; - if (first != null) - doSignalAll(first); - } - - /** - * Implements uninterruptible condition wait. - * <ol> - * <li> Save lock state returned by {@link #getState}. - * <li> Invoke {@link #release} with - * saved state as argument, throwing - * IllegalMonitorStateException if it fails. - * <li> Block until signalled. - * <li> Reacquire by invoking specialized version of - * {@link #acquire} with saved state as argument. - * </ol> - */ - public final void awaitUninterruptibly() { - Node node = addConditionWaiter(); - int savedState = fullyRelease(node); - boolean interrupted = false; - while (!isOnSyncQueue(node)) { - LockSupport.park(this); - if (Thread.interrupted()) - interrupted = true; - } - if (acquireQueued(node, savedState) || interrupted) - selfInterrupt(); - } - - /* - * For interruptible waits, we need to track whether to throw - * InterruptedException, if interrupted while blocked on - * condition, versus reinterrupt current thread, if - * interrupted while blocked waiting to re-acquire. - */ - - /** Mode meaning to reinterrupt on exit from wait */ - private static final int REINTERRUPT = 1; - /** Mode meaning to throw InterruptedException on exit from wait */ - private static final int THROW_IE = -1; - - /** - * Checks for interrupt, returning THROW_IE if interrupted - * before signalled, REINTERRUPT if after signalled, or - * 0 if not interrupted. - */ - private int checkInterruptWhileWaiting(Node node) { - return Thread.interrupted() ? - (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) : - 0; - } - - /** - * Throws InterruptedException, reinterrupts current thread, or - * does nothing, depending on mode. - */ - private void reportInterruptAfterWait(int interruptMode) - throws InterruptedException { - if (interruptMode == THROW_IE) - throw new InterruptedException(); - else if (interruptMode == REINTERRUPT) - selfInterrupt(); - } - - /** - * Implements interruptible condition wait. - * <ol> - * <li> If current thread is interrupted, throw InterruptedException. - * <li> Save lock state returned by {@link #getState}. - * <li> Invoke {@link #release} with - * saved state as argument, throwing - * IllegalMonitorStateException if it fails. - * <li> Block until signalled or interrupted. - * <li> Reacquire by invoking specialized version of - * {@link #acquire} with saved state as argument. - * <li> If interrupted while blocked in step 4, throw InterruptedException. - * </ol> - */ - public final void await() throws InterruptedException { - if (Thread.interrupted()) - throw new InterruptedException(); - Node node = addConditionWaiter(); - int savedState = fullyRelease(node); - int interruptMode = 0; - while (!isOnSyncQueue(node)) { - LockSupport.park(this); - if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) - break; - } - if (acquireQueued(node, savedState) && interruptMode != THROW_IE) - interruptMode = REINTERRUPT; - if (node.nextWaiter != null) // clean up if cancelled - unlinkCancelledWaiters(); - if (interruptMode != 0) - reportInterruptAfterWait(interruptMode); - } - - /** - * Implements timed condition wait. - * <ol> - * <li> If current thread is interrupted, throw InterruptedException. - * <li> Save lock state returned by {@link #getState}. - * <li> Invoke {@link #release} with - * saved state as argument, throwing - * IllegalMonitorStateException if it fails. - * <li> Block until signalled, interrupted, or timed out. - * <li> Reacquire by invoking specialized version of - * {@link #acquire} with saved state as argument. - * <li> If interrupted while blocked in step 4, throw InterruptedException. - * </ol> - */ - public final long awaitNanos(long nanosTimeout) - throws InterruptedException { - if (Thread.interrupted()) - throw new InterruptedException(); - Node node = addConditionWaiter(); - int savedState = fullyRelease(node); - long lastTime = System.nanoTime(); - int interruptMode = 0; - while (!isOnSyncQueue(node)) { - if (nanosTimeout <= 0L) { - transferAfterCancelledWait(node); - break; - } - LockSupport.parkNanos(this, nanosTimeout); - if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) - break; - - long now = System.nanoTime(); - nanosTimeout -= now - lastTime; - lastTime = now; - } - if (acquireQueued(node, savedState) && interruptMode != THROW_IE) - interruptMode = REINTERRUPT; - if (node.nextWaiter != null) - unlinkCancelledWaiters(); - if (interruptMode != 0) - reportInterruptAfterWait(interruptMode); - return nanosTimeout - (System.nanoTime() - lastTime); - } - - /** - * Implements absolute timed condition wait. - * <ol> - * <li> If current thread is interrupted, throw InterruptedException. - * <li> Save lock state returned by {@link #getState}. - * <li> Invoke {@link #release} with - * saved state as argument, throwing - * IllegalMonitorStateException if it fails. - * <li> Block until signalled, interrupted, or timed out. - * <li> Reacquire by invoking specialized version of - * {@link #acquire} with saved state as argument. - * <li> If interrupted while blocked in step 4, throw InterruptedException. - * <li> If timed out while blocked in step 4, return false, else true. - * </ol> - */ - public final boolean awaitUntil(Date deadline) - throws InterruptedException { - if (deadline == null) - throw new NullPointerException(); - long abstime = deadline.getTime(); - if (Thread.interrupted()) - throw new InterruptedException(); - Node node = addConditionWaiter(); - int savedState = fullyRelease(node); - boolean timedout = false; - int interruptMode = 0; - while (!isOnSyncQueue(node)) { - if (System.currentTimeMillis() > abstime) { - timedout = transferAfterCancelledWait(node); - break; - } - LockSupport.parkUntil(this, abstime); - if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) - break; - } - if (acquireQueued(node, savedState) && interruptMode != THROW_IE) - interruptMode = REINTERRUPT; - if (node.nextWaiter != null) - unlinkCancelledWaiters(); - if (interruptMode != 0) - reportInterruptAfterWait(interruptMode); - return !timedout; - } - - /** - * Implements timed condition wait. - * <ol> - * <li> If current thread is interrupted, throw InterruptedException. - * <li> Save lock state returned by {@link #getState}. - * <li> Invoke {@link #release} with - * saved state as argument, throwing - * IllegalMonitorStateException if it fails. - * <li> Block until signalled, interrupted, or timed out. - * <li> Reacquire by invoking specialized version of - * {@link #acquire} with saved state as argument. - * <li> If interrupted while blocked in step 4, throw InterruptedException. - * <li> If timed out while blocked in step 4, return false, else true. - * </ol> - */ - public final boolean await(long time, TimeUnit unit) - throws InterruptedException { - if (unit == null) - throw new NullPointerException(); - long nanosTimeout = unit.toNanos(time); - if (Thread.interrupted()) - throw new InterruptedException(); - Node node = addConditionWaiter(); - int savedState = fullyRelease(node); - long lastTime = System.nanoTime(); - boolean timedout = false; - int interruptMode = 0; - while (!isOnSyncQueue(node)) { - if (nanosTimeout <= 0L) { - timedout = transferAfterCancelledWait(node); - break; - } - if (nanosTimeout >= spinForTimeoutThreshold) - LockSupport.parkNanos(this, nanosTimeout); - if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) - break; - long now = System.nanoTime(); - nanosTimeout -= now - lastTime; - lastTime = now; - } - if (acquireQueued(node, savedState) && interruptMode != THROW_IE) - interruptMode = REINTERRUPT; - if (node.nextWaiter != null) - unlinkCancelledWaiters(); - if (interruptMode != 0) - reportInterruptAfterWait(interruptMode); - return !timedout; - } - - // support for instrumentation - - /** - * Returns true if this condition was created by the given - * synchronization object. - * - * @return {@code true} if owned - */ - final boolean isOwnedBy(AbstractQueuedSynchronizer sync) { - return sync == AbstractQueuedSynchronizer.this; - } - - /** - * Queries whether any threads are waiting on this condition. - * Implements {@link AbstractQueuedSynchronizer#hasWaiters}. - * - * @return {@code true} if there are any waiting threads - * @throws IllegalMonitorStateException if {@link #isHeldExclusively} - * returns {@code false} - */ - protected final boolean hasWaiters() { - if (!isHeldExclusively()) - throw new IllegalMonitorStateException(); - for (Node w = firstWaiter; w != null; w = w.nextWaiter) { - if (w.waitStatus == Node.CONDITION) - return true; - } - return false; - } - - /** - * Returns an estimate of the number of threads waiting on - * this condition. - * Implements {@link AbstractQueuedSynchronizer#getWaitQueueLength}. - * - * @return the estimated number of waiting threads - * @throws IllegalMonitorStateException if {@link #isHeldExclusively} - * returns {@code false} - */ - protected final int getWaitQueueLength() { - if (!isHeldExclusively()) - throw new IllegalMonitorStateException(); - int n = 0; - for (Node w = firstWaiter; w != null; w = w.nextWaiter) { - if (w.waitStatus == Node.CONDITION) - ++n; - } - return n; - } - - /** - * Returns a collection containing those threads that may be - * waiting on this Condition. - * Implements {@link AbstractQueuedSynchronizer#getWaitingThreads}. - * - * @return the collection of threads - * @throws IllegalMonitorStateException if {@link #isHeldExclusively} - * returns {@code false} - */ - protected final Collection<Thread> getWaitingThreads() { - if (!isHeldExclusively()) - throw new IllegalMonitorStateException(); - ArrayList<Thread> list = new ArrayList<Thread>(); - for (Node w = firstWaiter; w != null; w = w.nextWaiter) { - if (w.waitStatus == Node.CONDITION) { - Thread t = w.thread; - if (t != null) - list.add(t); - } - } - return list; - } - } - - /** - * IKVM specific. We use AtomicReferenceFieldUpdater instead of Unsafe primitives. - */ - private static final AtomicReferenceFieldUpdater<AbstractQueuedSynchronizer, Node> headUpdater = - AtomicReferenceFieldUpdater.newUpdater(AbstractQueuedSynchronizer.class, Node.class, "head"); - private static final AtomicReferenceFieldUpdater<AbstractQueuedSynchronizer, Node> tailUpdater = - AtomicReferenceFieldUpdater.newUpdater(AbstractQueuedSynchronizer.class, Node.class, "tail"); - - /** - * CAS head field. Used only by enq. - */ - private final boolean compareAndSetHead(Node update) { - return headUpdater.compareAndSet(this, null, update); - } - - /** - * CAS tail field. Used only by enq. - */ - private final boolean compareAndSetTail(Node expect, Node update) { - return tailUpdater.compareAndSet(this, expect, update); - } - - /** - * CAS waitStatus field of a node. - */ - private static final native boolean compareAndSetWaitStatus(Node node, - int expect, - int update); // implemented in map.xml - /** - * CAS next field of a node. - */ - private static final boolean compareAndSetNext(Node node, - Node expect, - Node update) { - return Node.nextUpdater.compareAndSet(node, expect, update); - } -} |