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