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