lib/classpath/external/jsr166/java/util/concurrent/locks/AbstractQueuedSynchronizer.java

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