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.util.ArrayList;
  39 import java.util.Collection;
  40 import java.util.Date;
  41 import java.util.concurrent.TimeUnit;
  42 import java.util.concurrent.ForkJoinPool;
  43 import jdk.internal.misc.Unsafe;
  44 
  45 /**
  46  * A version of {@link AbstractQueuedSynchronizer} in
  47  * which synchronization state is maintained as a {@code long}.
  48  * This class has exactly the same structure, properties, and methods
  49  * as {@code AbstractQueuedSynchronizer} with the exception
  50  * that all state-related parameters and results are defined
  51  * as {@code long} rather than {@code int}. This class
  52  * may be useful when creating synchronizers such as
  53  * multilevel locks and barriers that require
  54  * 64 bits of state.
  55  *
  56  * <p>See {@link AbstractQueuedSynchronizer} for usage
  57  * notes and examples.
  58  *
  59  * @since 1.6
  60  * @author Doug Lea
  61  */
  62 public abstract class AbstractQueuedLongSynchronizer
  63     extends AbstractOwnableSynchronizer
  64     implements java.io.Serializable {
  65 
  66     private static final long serialVersionUID = 7373984972572414692L;
  67 
  68     /**
  69      * Constructor for subclasses to call.
  70      */
  71     public AbstractQueuedLongSynchronizer() {}
  72 
  73     /*
  74      * To keep sources in sync, the remainder of this source file is
  75      * exactly cloned from AbstractQueuedSynchronizer, replacing class
  76      * name and changing ints related with sync state to longs. Please
  77      * keep it that way.
  78      */
  79 
  80     // Node status bits, also used as argument and return values
  81     static final int WAITING   = 1;          // must be 1
  82     static final int CANCELLED = 0x80000000; // must be negative
  83     static final int COND      = 2;          // in a condition wait
  84 
  85     /** CLH Nodes */
  86     abstract static class Node {
  87         volatile Node prev;       // initially attached via casTail
  88         volatile Node next;       // visibly nonnull when signallable
  89         Thread waiter;            // visibly nonnull when enqueued
  90         volatile int status;      // written by owner, atomic bit ops by others
  91 
  92         // methods for atomic operations
  93         final boolean casPrev(Node c, Node v) {  // for cleanQueue
  94             return U.weakCompareAndSetReference(this, PREV, c, v);
  95         }
  96         final boolean casNext(Node c, Node v) {  // for cleanQueue
  97             return U.weakCompareAndSetReference(this, NEXT, c, v);
  98         }
  99         final int getAndUnsetStatus(int v) {     // for signalling
 100             return U.getAndBitwiseAndInt(this, STATUS, ~v);
 101         }
 102         final void setPrevRelaxed(Node p) {      // for off-queue assignment
 103             U.putReference(this, PREV, p);
 104         }
 105         final void setStatusRelaxed(int s) {     // for off-queue assignment
 106             U.putInt(this, STATUS, s);
 107         }
 108         final void clearStatus() {               // for reducing unneeded signals
 109             U.putIntOpaque(this, STATUS, 0);
 110         }
 111 
 112         private static final long STATUS
 113             = U.objectFieldOffset(Node.class, "status");
 114         private static final long NEXT
 115             = U.objectFieldOffset(Node.class, "next");
 116         private static final long PREV
 117             = U.objectFieldOffset(Node.class, "prev");
 118     }
 119 
 120     // Concrete classes tagged by type
 121     static final class ExclusiveNode extends Node { }
 122     static final class SharedNode extends Node { }
 123 
 124     static final class ConditionNode extends Node
 125         implements ForkJoinPool.ManagedBlocker {
 126         ConditionNode nextWaiter;            // link to next waiting node
 127 
 128         /**
 129          * Allows Conditions to be used in ForkJoinPools without
 130          * risking fixed pool exhaustion. This is usable only for
 131          * untimed Condition waits, not timed versions.
 132          */
 133         public final boolean isReleasable() {
 134             return status <= 1 || Thread.currentThread().isInterrupted();
 135         }
 136 
 137         public final boolean block() {
 138             while (!isReleasable()) LockSupport.park();
 139             return true;
 140         }
 141     }
 142 
 143     /**
 144      * Head of the wait queue, lazily initialized.
 145      */
 146     private transient volatile Node head;
 147 
 148     /**
 149      * Tail of the wait queue. After initialization, modified only via casTail.
 150      */
 151     private transient volatile Node tail;
 152 
 153     /**
 154      * The synchronization state.
 155      */
 156     private volatile long state;
 157 
 158     /**
 159      * Returns the current value of synchronization state.
 160      * This operation has memory semantics of a {@code volatile} read.
 161      * @return current state value
 162      */
 163     protected final long getState() {
 164         return state;
 165     }
 166 
 167     /**
 168      * Sets the value of synchronization state.
 169      * This operation has memory semantics of a {@code volatile} write.
 170      * @param newState the new state value
 171      */
 172     protected final void setState(long newState) {
 173         state = newState;
 174     }
 175 
 176     /**
 177      * Atomically sets synchronization state to the given updated
 178      * value if the current state value equals the expected value.
 179      * This operation has memory semantics of a {@code volatile} read
 180      * and write.
 181      *
 182      * @param expect the expected value
 183      * @param update the new value
 184      * @return {@code true} if successful. False return indicates that the actual
 185      *         value was not equal to the expected value.
 186      */
 187     protected final boolean compareAndSetState(long expect, long update) {
 188         return U.compareAndSetLong(this, STATE, expect, update);
 189     }
 190 
 191     // Queuing utilities
 192 
 193     private boolean casTail(Node c, Node v) {
 194         return U.compareAndSetReference(this, TAIL, c, v);
 195     }
 196 
 197     /** tries once to CAS a new dummy node for head */
 198     private void tryInitializeHead() {
 199         Node h = new ExclusiveNode();
 200         if (U.compareAndSetReference(this, HEAD, null, h))
 201             tail = h;
 202     }
 203 
 204     /**
 205      * Enqueues the node unless null. (Currently used only for
 206      * ConditionNodes; other cases are interleaved with acquires.)
 207      */
 208     final void enqueue(Node node) {
 209         if (node != null) {
 210             for (;;) {
 211                 Node t = tail;
 212                 node.setPrevRelaxed(t);        // avoid unnecessary fence
 213                 if (t == null)                 // initialize
 214                     tryInitializeHead();
 215                 else if (casTail(t, node)) {
 216                     t.next = node;
 217                     if (t.status < 0)          // wake up to clean link
 218                         LockSupport.unpark(node.waiter);
 219                     break;
 220                 }
 221             }
 222         }
 223     }
 224 
 225     /** Returns true if node is found in traversal from tail */
 226     final boolean isEnqueued(Node node) {
 227         for (Node t = tail; t != null; t = t.prev)
 228             if (t == node)
 229                 return true;
 230         return false;
 231     }
 232 
 233     /**
 234      * Wakes up the successor of given node, if one exists, and unsets its
 235      * WAITING status to avoid park race. This may fail to wake up an
 236      * eligible thread when one or more have been cancelled, but
 237      * cancelAcquire ensures liveness.
 238      */
 239     private static void signalNext(Node h) {
 240         Node s;
 241         if (h != null && (s = h.next) != null && s.status != 0) {
 242             s.getAndUnsetStatus(WAITING);
 243             LockSupport.unpark(s.waiter);
 244         }
 245     }
 246 
 247     /** Wakes up the given node if in shared mode */
 248     private static void signalNextIfShared(Node h) {
 249         Node s;
 250         if (h != null && (s = h.next) != null &&
 251             (s instanceof SharedNode) && s.status != 0) {
 252             s.getAndUnsetStatus(WAITING);
 253             LockSupport.unpark(s.waiter);
 254         }
 255     }
 256 
 257     /**
 258      * Main acquire method, invoked by all exported acquire methods.
 259      *
 260      * @param node null unless a reacquiring Condition
 261      * @param arg the acquire argument
 262      * @param shared true if shared mode else exclusive
 263      * @param interruptible if abort and return negative on interrupt
 264      * @param timed if true use timed waits
 265      * @param time if timed, the System.nanoTime value to timeout
 266      * @return positive if acquired, 0 if timed out, negative if interrupted
 267      */
 268     final int acquire(Node node, long arg, boolean shared,
 269                       boolean interruptible, boolean timed, long time) {
 270         Thread current = Thread.currentThread();
 271         byte spins = 0, postSpins = 0;   // retries upon unpark of first thread
 272         boolean interrupted = false, first = false;
 273         Node pred = null;                // predecessor of node when enqueued
 274 
 275         /*
 276          * Repeatedly:
 277          *  Check if node now first
 278          *    if so, ensure head stable, else ensure valid predecessor
 279          *  if node is first or not yet enqueued, try acquiring
 280          *  else if node not yet created, create it
 281          *  else if not yet enqueued, try once to enqueue
 282          *  else if woken from park, retry (up to postSpins times)
 283          *  else if WAITING status not set, set and retry
 284          *  else park and clear WAITING status, and check cancellation
 285          */
 286 
 287         for (;;) {
 288             if (!first && (pred = (node == null) ? null : node.prev) != null &&
 289                 !(first = (head == pred))) {
 290                 if (pred.status < 0) {
 291                     cleanQueue();           // predecessor cancelled
 292                     continue;
 293                 } else if (pred.prev == null) {
 294                     Thread.onSpinWait();    // ensure serialization
 295                     continue;
 296                 }
 297             }
 298             if (first || pred == null) {
 299                 boolean acquired;
 300                 try {
 301                     if (shared)
 302                         acquired = (tryAcquireShared(arg) >= 0);
 303                     else
 304                         acquired = tryAcquire(arg);
 305                 } catch (Throwable ex) {
 306                     cancelAcquire(node, interrupted, false);
 307                     throw ex;
 308                 }
 309                 if (acquired) {
 310                     if (first) {
 311                         node.prev = null;
 312                         head = node;
 313                         pred.next = null;
 314                         node.waiter = null;
 315                         if (shared)
 316                             signalNextIfShared(node);
 317                         if (interrupted)
 318                             current.interrupt();
 319                     }
 320                     return 1;
 321                 }
 322             }
 323             if (node == null) {                 // allocate; retry before enqueue
 324                 if (shared)
 325                     node = new SharedNode();
 326                 else
 327                     node = new ExclusiveNode();
 328             } else if (pred == null) {          // try to enqueue
 329                 node.waiter = current;
 330                 Node t = tail;
 331                 node.setPrevRelaxed(t);         // avoid unnecessary fence
 332                 if (t == null)
 333                     tryInitializeHead();
 334                 else if (!casTail(t, node))
 335                     node.setPrevRelaxed(null);  // back out
 336                 else
 337                     t.next = node;
 338             } else if (first && spins != 0) {
 339                 --spins;                        // reduce unfairness on rewaits
 340                 Thread.onSpinWait();
 341             } else if (node.status == 0) {
 342                 node.status = WAITING;          // enable signal and recheck
 343             } else {
 344                 long nanos;
 345                 spins = postSpins = (byte)((postSpins << 1) | 1);
 346                 if (!timed)
 347                     LockSupport.park(this);
 348                 else if ((nanos = time - System.nanoTime()) > 0L)
 349                     LockSupport.parkNanos(this, nanos);
 350                 else
 351                     break;
 352                 node.clearStatus();
 353                 if ((interrupted |= Thread.interrupted()) && interruptible)
 354                     break;
 355             }
 356         }
 357         return cancelAcquire(node, interrupted, interruptible);
 358     }
 359 
 360     /**
 361      * Possibly repeatedly traverses from tail, unsplicing cancelled
 362      * nodes until none are found.
 363      */
 364     private void cleanQueue() {
 365         for (;;) {                               // restart point
 366             for (Node q = tail, s = null, p, n;;) { // (p, q, s) triples
 367                 if (q == null || (p = q.prev) == null)
 368                     return;                      // end of list
 369                 if (s == null ? tail != q : (s.prev != q || s.status < 0))
 370                     break;                       // inconsistent
 371                 if (q.status < 0) {              // cancelled
 372                     if ((s == null ? casTail(q, p) : s.casPrev(q, p)) &&
 373                         q.prev == p) {
 374                         p.casNext(q, s);         // OK if fails
 375                         if (p.prev == null)
 376                             signalNext(p);
 377                     }
 378                     break;
 379                 }
 380                 if ((n = p.next) != q) {         // help finish
 381                     if (n != null && q.prev == p) {
 382                         p.casNext(n, q);
 383                         if (p.prev == null)
 384                             signalNext(p);
 385                     }
 386                     break;
 387                 }
 388                 s = q;
 389                 q = q.prev;
 390             }
 391         }
 392     }
 393 
 394     /**
 395      * Cancels an ongoing attempt to acquire.
 396      *
 397      * @param node the node (may be null if cancelled before enqueuing)
 398      * @param interrupted true if thread interrupted
 399      * @param interruptible if should report interruption vs reset
 400      */
 401     private int cancelAcquire(Node node, boolean interrupted,
 402                               boolean interruptible) {
 403         if (node != null) {
 404             node.waiter = null;
 405             node.status = CANCELLED;
 406             if (node.prev != null)
 407                 cleanQueue();
 408         }
 409         if (interrupted) {
 410             if (interruptible)
 411                 return CANCELLED;
 412             else
 413                 Thread.currentThread().interrupt();
 414         }
 415         return 0;
 416     }
 417 
 418     // Main exported methods
 419 
 420     /**
 421      * Attempts to acquire in exclusive mode. This method should query
 422      * if the state of the object permits it to be acquired in the
 423      * exclusive mode, and if so to acquire it.
 424      *
 425      * <p>This method is always invoked by the thread performing
 426      * acquire.  If this method reports failure, the acquire method
 427      * may queue the thread, if it is not already queued, until it is
 428      * signalled by a release from some other thread. This can be used
 429      * to implement method {@link Lock#tryLock()}.
 430      *
 431      * <p>The default
 432      * implementation throws {@link UnsupportedOperationException}.
 433      *
 434      * @param arg the acquire argument. This value is always the one
 435      *        passed to an acquire method, or is the value saved on entry
 436      *        to a condition wait.  The value is otherwise uninterpreted
 437      *        and can represent anything you like.
 438      * @return {@code true} if successful. Upon success, this object has
 439      *         been acquired.
 440      * @throws IllegalMonitorStateException if acquiring would place this
 441      *         synchronizer in an illegal state. This exception must be
 442      *         thrown in a consistent fashion for synchronization to work
 443      *         correctly.
 444      * @throws UnsupportedOperationException if exclusive mode is not supported
 445      */
 446     protected boolean tryAcquire(long arg) {
 447         throw new UnsupportedOperationException();
 448     }
 449 
 450     /**
 451      * Attempts to set the state to reflect a release in exclusive
 452      * mode.
 453      *
 454      * <p>This method is always invoked by the thread performing release.
 455      *
 456      * <p>The default implementation throws
 457      * {@link UnsupportedOperationException}.
 458      *
 459      * @param arg the release argument. This value is always the one
 460      *        passed to a release method, or the current state value upon
 461      *        entry to a condition wait.  The value is otherwise
 462      *        uninterpreted and can represent anything you like.
 463      * @return {@code true} if this object is now in a fully released
 464      *         state, so that any waiting threads may attempt to acquire;
 465      *         and {@code false} otherwise.
 466      * @throws IllegalMonitorStateException if releasing would place this
 467      *         synchronizer in an illegal state. This exception must be
 468      *         thrown in a consistent fashion for synchronization to work
 469      *         correctly.
 470      * @throws UnsupportedOperationException if exclusive mode is not supported
 471      */
 472     protected boolean tryRelease(long arg) {
 473         throw new UnsupportedOperationException();
 474     }
 475 
 476     /**
 477      * Attempts to acquire in shared mode. This method should query if
 478      * the state of the object permits it to be acquired in the shared
 479      * mode, and if so to acquire it.
 480      *
 481      * <p>This method is always invoked by the thread performing
 482      * acquire.  If this method reports failure, the acquire method
 483      * may queue the thread, if it is not already queued, until it is
 484      * signalled by a release from some other thread.
 485      *
 486      * <p>The default implementation throws {@link
 487      * UnsupportedOperationException}.
 488      *
 489      * @param arg the acquire argument. This value is always the one
 490      *        passed to an acquire method, or is the value saved on entry
 491      *        to a condition wait.  The value is otherwise uninterpreted
 492      *        and can represent anything you like.
 493      * @return a negative value on failure; zero if acquisition in shared
 494      *         mode succeeded but no subsequent shared-mode acquire can
 495      *         succeed; and a positive value if acquisition in shared
 496      *         mode succeeded and subsequent shared-mode acquires might
 497      *         also succeed, in which case a subsequent waiting thread
 498      *         must check availability. (Support for three different
 499      *         return values enables this method to be used in contexts
 500      *         where acquires only sometimes act exclusively.)  Upon
 501      *         success, this object has been acquired.
 502      * @throws IllegalMonitorStateException if acquiring would place this
 503      *         synchronizer in an illegal state. This exception must be
 504      *         thrown in a consistent fashion for synchronization to work
 505      *         correctly.
 506      * @throws UnsupportedOperationException if shared mode is not supported
 507      */
 508     protected long tryAcquireShared(long arg) {
 509         throw new UnsupportedOperationException();
 510     }
 511 
 512     /**
 513      * Attempts to set the state to reflect a release in shared mode.
 514      *
 515      * <p>This method is always invoked by the thread performing release.
 516      *
 517      * <p>The default implementation throws
 518      * {@link UnsupportedOperationException}.
 519      *
 520      * @param arg the release argument. This value is always the one
 521      *        passed to a release method, or the current state value upon
 522      *        entry to a condition wait.  The value is otherwise
 523      *        uninterpreted and can represent anything you like.
 524      * @return {@code true} if this release of shared mode may permit a
 525      *         waiting acquire (shared or exclusive) to succeed; and
 526      *         {@code false} otherwise
 527      * @throws IllegalMonitorStateException if releasing would place this
 528      *         synchronizer in an illegal state. This exception must be
 529      *         thrown in a consistent fashion for synchronization to work
 530      *         correctly.
 531      * @throws UnsupportedOperationException if shared mode is not supported
 532      */
 533     protected boolean tryReleaseShared(long arg) {
 534         throw new UnsupportedOperationException();
 535     }
 536 
 537     /**
 538      * Returns {@code true} if synchronization is held exclusively with
 539      * respect to the current (calling) thread.  This method is invoked
 540      * upon each call to a {@link ConditionObject} method.
 541      *
 542      * <p>The default implementation throws {@link
 543      * UnsupportedOperationException}. This method is invoked
 544      * internally only within {@link ConditionObject} methods, so need
 545      * not be defined if conditions are not used.
 546      *
 547      * @return {@code true} if synchronization is held exclusively;
 548      *         {@code false} otherwise
 549      * @throws UnsupportedOperationException if conditions are not supported
 550      */
 551     protected boolean isHeldExclusively() {
 552         throw new UnsupportedOperationException();
 553     }
 554 
 555     /**
 556      * Acquires in exclusive mode, ignoring interrupts.  Implemented
 557      * by invoking at least once {@link #tryAcquire},
 558      * returning on success.  Otherwise the thread is queued, possibly
 559      * repeatedly blocking and unblocking, invoking {@link
 560      * #tryAcquire} until success.  This method can be used
 561      * to implement method {@link Lock#lock}.
 562      *
 563      * @param arg the acquire argument.  This value is conveyed to
 564      *        {@link #tryAcquire} but is otherwise uninterpreted and
 565      *        can represent anything you like.
 566      */
 567     public final void acquire(long arg) {
 568         if (!tryAcquire(arg))
 569             acquire(null, arg, false, false, false, 0L);
 570     }
 571 
 572     /**
 573      * Acquires in exclusive mode, aborting if interrupted.
 574      * Implemented by first checking interrupt status, then invoking
 575      * at least once {@link #tryAcquire}, returning on
 576      * success.  Otherwise the thread is queued, possibly repeatedly
 577      * blocking and unblocking, invoking {@link #tryAcquire}
 578      * until success or the thread is interrupted.  This method can be
 579      * used to implement method {@link Lock#lockInterruptibly}.
 580      *
 581      * @param arg the acquire argument.  This value is conveyed to
 582      *        {@link #tryAcquire} but is otherwise uninterpreted and
 583      *        can represent anything you like.
 584      * @throws InterruptedException if the current thread is interrupted
 585      */
 586     public final void acquireInterruptibly(long arg)
 587         throws InterruptedException {
 588         if (Thread.interrupted() ||
 589             (!tryAcquire(arg) && acquire(null, arg, false, true, false, 0L) < 0))
 590             throw new InterruptedException();
 591     }
 592 
 593     /**
 594      * Attempts to acquire in exclusive mode, aborting if interrupted,
 595      * and failing if the given timeout elapses.  Implemented by first
 596      * checking interrupt status, then invoking at least once {@link
 597      * #tryAcquire}, returning on success.  Otherwise, the thread is
 598      * queued, possibly repeatedly blocking and unblocking, invoking
 599      * {@link #tryAcquire} until success or the thread is interrupted
 600      * or the timeout elapses.  This method can be used to implement
 601      * method {@link Lock#tryLock(long, TimeUnit)}.
 602      *
 603      * @param arg the acquire argument.  This value is conveyed to
 604      *        {@link #tryAcquire} but is otherwise uninterpreted and
 605      *        can represent anything you like.
 606      * @param nanosTimeout the maximum number of nanoseconds to wait
 607      * @return {@code true} if acquired; {@code false} if timed out
 608      * @throws InterruptedException if the current thread is interrupted
 609      */
 610     public final boolean tryAcquireNanos(long arg, long nanosTimeout)
 611         throws InterruptedException {
 612         if (!Thread.interrupted()) {
 613             if (tryAcquire(arg))
 614                 return true;
 615             if (nanosTimeout <= 0L)
 616                 return false;
 617             int stat = acquire(null, arg, false, true, true,
 618                                System.nanoTime() + nanosTimeout);
 619             if (stat > 0)
 620                 return true;
 621             if (stat == 0)
 622                 return false;
 623         }
 624         throw new InterruptedException();
 625     }
 626 
 627     /**
 628      * Releases in exclusive mode.  Implemented by unblocking one or
 629      * more threads if {@link #tryRelease} returns true.
 630      * This method can be used to implement method {@link Lock#unlock}.
 631      *
 632      * @param arg the release argument.  This value is conveyed to
 633      *        {@link #tryRelease} but is otherwise uninterpreted and
 634      *        can represent anything you like.
 635      * @return the value returned from {@link #tryRelease}
 636      */
 637     public final boolean release(long arg) {
 638         if (tryRelease(arg)) {
 639             signalNext(head);
 640             return true;
 641         }
 642         return false;
 643     }
 644 
 645     /**
 646      * Acquires in shared mode, ignoring interrupts.  Implemented by
 647      * first invoking at least once {@link #tryAcquireShared},
 648      * returning on success.  Otherwise the thread is queued, possibly
 649      * repeatedly blocking and unblocking, invoking {@link
 650      * #tryAcquireShared} until success.
 651      *
 652      * @param arg the acquire argument.  This value is conveyed to
 653      *        {@link #tryAcquireShared} but is otherwise uninterpreted
 654      *        and can represent anything you like.
 655      */
 656     public final void acquireShared(long arg) {
 657         if (tryAcquireShared(arg) < 0)
 658             acquire(null, arg, true, false, false, 0L);
 659     }
 660 
 661     /**
 662      * Acquires in shared mode, aborting if interrupted.  Implemented
 663      * by first checking interrupt status, then invoking at least once
 664      * {@link #tryAcquireShared}, returning on success.  Otherwise the
 665      * thread is queued, possibly repeatedly blocking and unblocking,
 666      * invoking {@link #tryAcquireShared} until success or the thread
 667      * is interrupted.
 668      * @param arg the acquire argument.
 669      * This value is conveyed to {@link #tryAcquireShared} but is
 670      * otherwise uninterpreted and can represent anything
 671      * you like.
 672      * @throws InterruptedException if the current thread is interrupted
 673      */
 674     public final void acquireSharedInterruptibly(long arg)
 675         throws InterruptedException {
 676         if (Thread.interrupted() ||
 677             (tryAcquireShared(arg) < 0 &&
 678              acquire(null, arg, true, true, false, 0L) < 0))
 679             throw new InterruptedException();
 680     }
 681 
 682     /**
 683      * Attempts to acquire in shared mode, aborting if interrupted, and
 684      * failing if the given timeout elapses.  Implemented by first
 685      * checking interrupt status, then invoking at least once {@link
 686      * #tryAcquireShared}, returning on success.  Otherwise, the
 687      * thread is queued, possibly repeatedly blocking and unblocking,
 688      * invoking {@link #tryAcquireShared} until success or the thread
 689      * is interrupted or the timeout elapses.
 690      *
 691      * @param arg the acquire argument.  This value is conveyed to
 692      *        {@link #tryAcquireShared} but is otherwise uninterpreted
 693      *        and can represent anything you like.
 694      * @param nanosTimeout the maximum number of nanoseconds to wait
 695      * @return {@code true} if acquired; {@code false} if timed out
 696      * @throws InterruptedException if the current thread is interrupted
 697      */
 698     public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout)
 699             throws InterruptedException {
 700         if (!Thread.interrupted()) {
 701             if (tryAcquireShared(arg) >= 0)
 702                 return true;
 703             if (nanosTimeout <= 0L)
 704                 return false;
 705             int stat = acquire(null, arg, true, true, true,
 706                                System.nanoTime() + nanosTimeout);
 707             if (stat > 0)
 708                 return true;
 709             if (stat == 0)
 710                 return false;
 711         }
 712         throw new InterruptedException();
 713     }
 714 
 715     /**
 716      * Releases in shared mode.  Implemented by unblocking one or more
 717      * threads if {@link #tryReleaseShared} returns true.
 718      *
 719      * @param arg the release argument.  This value is conveyed to
 720      *        {@link #tryReleaseShared} but is otherwise uninterpreted
 721      *        and can represent anything you like.
 722      * @return the value returned from {@link #tryReleaseShared}
 723      */
 724     public final boolean releaseShared(long arg) {
 725         if (tryReleaseShared(arg)) {
 726             signalNext(head);
 727             return true;
 728         }
 729         return false;
 730     }
 731 
 732     // Queue inspection methods
 733 
 734     /**
 735      * Queries whether any threads are waiting to acquire. Note that
 736      * because cancellations due to interrupts and timeouts may occur
 737      * at any time, a {@code true} return does not guarantee that any
 738      * other thread will ever acquire.
 739      *
 740      * @return {@code true} if there may be other threads waiting to acquire
 741      */
 742     public final boolean hasQueuedThreads() {
 743         for (Node p = tail, h = head; p != h && p != null; p = p.prev)
 744             if (p.status >= 0)
 745                 return true;
 746         return false;
 747     }
 748 
 749     /**
 750      * Queries whether any threads have ever contended to acquire this
 751      * synchronizer; that is, if an acquire method has ever blocked.
 752      *
 753      * <p>In this implementation, this operation returns in
 754      * constant time.
 755      *
 756      * @return {@code true} if there has ever been contention
 757      */
 758     public final boolean hasContended() {
 759         return head != null;
 760     }
 761 
 762     /**
 763      * Returns the first (longest-waiting) thread in the queue, or
 764      * {@code null} if no threads are currently queued.
 765      *
 766      * <p>In this implementation, this operation normally returns in
 767      * constant time, but may iterate upon contention if other threads are
 768      * concurrently modifying the queue.
 769      *
 770      * @return the first (longest-waiting) thread in the queue, or
 771      *         {@code null} if no threads are currently queued
 772      */
 773     public final Thread getFirstQueuedThread() {
 774         Thread first = null, w; Node h, s;
 775         if ((h = head) != null && ((s = h.next) == null ||
 776                                    (first = s.waiter) == null ||
 777                                    s.prev == null)) {
 778             // traverse from tail on stale reads
 779             for (Node p = tail, q; p != null && (q = p.prev) != null; p = q)
 780                 if ((w = p.waiter) != null)
 781                     first = w;
 782         }
 783         return first;
 784     }
 785 
 786     /**
 787      * Returns true if the given thread is currently queued.
 788      *
 789      * <p>This implementation traverses the queue to determine
 790      * presence of the given thread.
 791      *
 792      * @param thread the thread
 793      * @return {@code true} if the given thread is on the queue
 794      * @throws NullPointerException if the thread is null
 795      */
 796     public final boolean isQueued(Thread thread) {
 797         if (thread == null)
 798             throw new NullPointerException();
 799         for (Node p = tail; p != null; p = p.prev)
 800             if (p.waiter == thread)
 801                 return true;
 802         return false;
 803     }
 804 
 805     /**
 806      * Returns {@code true} if the apparent first queued thread, if one
 807      * exists, is waiting in exclusive mode.  If this method returns
 808      * {@code true}, and the current thread is attempting to acquire in
 809      * shared mode (that is, this method is invoked from {@link
 810      * #tryAcquireShared}) then it is guaranteed that the current thread
 811      * is not the first queued thread.  Used only as a heuristic in
 812      * ReentrantReadWriteLock.
 813      */
 814     final boolean apparentlyFirstQueuedIsExclusive() {
 815         Node h, s;
 816         return (h = head) != null && (s = h.next)  != null &&
 817             !(s instanceof SharedNode) && s.waiter != null;
 818     }
 819 
 820     /**
 821      * Queries whether any threads have been waiting to acquire longer
 822      * than the current thread.
 823      *
 824      * <p>An invocation of this method is equivalent to (but may be
 825      * more efficient than):
 826      * <pre> {@code
 827      * getFirstQueuedThread() != Thread.currentThread()
 828      *   && hasQueuedThreads()}</pre>
 829      *
 830      * <p>Note that because cancellations due to interrupts and
 831      * timeouts may occur at any time, a {@code true} return does not
 832      * guarantee that some other thread will acquire before the current
 833      * thread.  Likewise, it is possible for another thread to win a
 834      * race to enqueue after this method has returned {@code false},
 835      * due to the queue being empty.
 836      *
 837      * <p>This method is designed to be used by a fair synchronizer to
 838      * avoid <a href="AbstractQueuedSynchronizer.html#barging">barging</a>.
 839      * Such a synchronizer's {@link #tryAcquire} method should return
 840      * {@code false}, and its {@link #tryAcquireShared} method should
 841      * return a negative value, if this method returns {@code true}
 842      * (unless this is a reentrant acquire).  For example, the {@code
 843      * tryAcquire} method for a fair, reentrant, exclusive mode
 844      * synchronizer might look like this:
 845      *
 846      * <pre> {@code
 847      * protected boolean tryAcquire(long arg) {
 848      *   if (isHeldExclusively()) {
 849      *     // A reentrant acquire; increment hold count
 850      *     return true;
 851      *   } else if (hasQueuedPredecessors()) {
 852      *     return false;
 853      *   } else {
 854      *     // try to acquire normally
 855      *   }
 856      * }}</pre>
 857      *
 858      * @return {@code true} if there is a queued thread preceding the
 859      *         current thread, and {@code false} if the current thread
 860      *         is at the head of the queue or the queue is empty
 861      * @since 1.7
 862      */
 863     public final boolean hasQueuedPredecessors() {
 864         Thread first = null; Node h, s;
 865         if ((h = head) != null && ((s = h.next) == null ||
 866                                    (first = s.waiter) == null ||
 867                                    s.prev == null))
 868             first = getFirstQueuedThread(); // retry via getFirstQueuedThread
 869         return first != null && first != Thread.currentThread();
 870     }
 871 
 872     // Instrumentation and monitoring methods
 873 
 874     /**
 875      * Returns an estimate of the number of threads waiting to
 876      * acquire.  The value is only an estimate because the number of
 877      * threads may change dynamically while this method traverses
 878      * internal data structures.  This method is designed for use in
 879      * monitoring system state, not for synchronization control.
 880      *
 881      * @return the estimated number of threads waiting to acquire
 882      */
 883     public final int getQueueLength() {
 884         int n = 0;
 885         for (Node p = tail; p != null; p = p.prev) {
 886             if (p.waiter != null)
 887                 ++n;
 888         }
 889         return n;
 890     }
 891 
 892     /**
 893      * Returns a collection containing threads that may be waiting to
 894      * acquire.  Because the actual set of threads may change
 895      * dynamically while constructing this result, the returned
 896      * collection is only a best-effort estimate.  The elements of the
 897      * returned collection are in no particular order.  This method is
 898      * designed to facilitate construction of subclasses that provide
 899      * more extensive monitoring facilities.
 900      *
 901      * @return the collection of threads
 902      */
 903     public final Collection<Thread> getQueuedThreads() {
 904         ArrayList<Thread> list = new ArrayList<>();
 905         for (Node p = tail; p != null; p = p.prev) {
 906             Thread t = p.waiter;
 907             if (t != null)
 908                 list.add(t);
 909         }
 910         return list;
 911     }
 912 
 913     /**
 914      * Returns a collection containing threads that may be waiting to
 915      * acquire in exclusive mode. This has the same properties
 916      * as {@link #getQueuedThreads} except that it only returns
 917      * those threads waiting due to an exclusive acquire.
 918      *
 919      * @return the collection of threads
 920      */
 921     public final Collection<Thread> getExclusiveQueuedThreads() {
 922         ArrayList<Thread> list = new ArrayList<>();
 923         for (Node p = tail; p != null; p = p.prev) {
 924             if (!(p instanceof SharedNode)) {
 925                 Thread t = p.waiter;
 926                 if (t != null)
 927                     list.add(t);
 928             }
 929         }
 930         return list;
 931     }
 932 
 933     /**
 934      * Returns a collection containing threads that may be waiting to
 935      * acquire in shared mode. This has the same properties
 936      * as {@link #getQueuedThreads} except that it only returns
 937      * those threads waiting due to a shared acquire.
 938      *
 939      * @return the collection of threads
 940      */
 941     public final Collection<Thread> getSharedQueuedThreads() {
 942         ArrayList<Thread> list = new ArrayList<>();
 943         for (Node p = tail; p != null; p = p.prev) {
 944             if (p instanceof SharedNode) {
 945                 Thread t = p.waiter;
 946                 if (t != null)
 947                     list.add(t);
 948             }
 949         }
 950         return list;
 951     }
 952 
 953     /**
 954      * Returns a string identifying this synchronizer, as well as its state.
 955      * The state, in brackets, includes the String {@code "State ="}
 956      * followed by the current value of {@link #getState}, and either
 957      * {@code "nonempty"} or {@code "empty"} depending on whether the
 958      * queue is empty.
 959      *
 960      * @return a string identifying this synchronizer, as well as its state
 961      */
 962     public String toString() {
 963         return super.toString()
 964             + "[State = " + getState() + ", "
 965             + (hasQueuedThreads() ? "non" : "") + "empty queue]";
 966     }
 967 
 968     // Instrumentation methods for conditions
 969 
 970     /**
 971      * Queries whether the given ConditionObject
 972      * uses this synchronizer as its lock.
 973      *
 974      * @param condition the condition
 975      * @return {@code true} if owned
 976      * @throws NullPointerException if the condition is null
 977      */
 978     public final boolean owns(ConditionObject condition) {
 979         return condition.isOwnedBy(this);
 980     }
 981 
 982     /**
 983      * Queries whether any threads are waiting on the given condition
 984      * associated with this synchronizer. Note that because timeouts
 985      * and interrupts may occur at any time, a {@code true} return
 986      * does not guarantee that a future {@code signal} will awaken
 987      * any threads.  This method is designed primarily for use in
 988      * monitoring of the system state.
 989      *
 990      * @param condition the condition
 991      * @return {@code true} if there are any waiting threads
 992      * @throws IllegalMonitorStateException if exclusive synchronization
 993      *         is not held
 994      * @throws IllegalArgumentException if the given condition is
 995      *         not associated with this synchronizer
 996      * @throws NullPointerException if the condition is null
 997      */
 998     public final boolean hasWaiters(ConditionObject condition) {
 999         if (!owns(condition))
1000             throw new IllegalArgumentException("Not owner");
1001         return condition.hasWaiters();
1002     }
1003 
1004     /**
1005      * Returns an estimate of the number of threads waiting on the
1006      * given condition associated with this synchronizer. Note that
1007      * because timeouts and interrupts may occur at any time, the
1008      * estimate serves only as an upper bound on the actual number of
1009      * waiters.  This method is designed for use in monitoring system
1010      * state, not for synchronization control.
1011      *
1012      * @param condition the condition
1013      * @return the estimated number of waiting threads
1014      * @throws IllegalMonitorStateException if exclusive synchronization
1015      *         is not held
1016      * @throws IllegalArgumentException if the given condition is
1017      *         not associated with this synchronizer
1018      * @throws NullPointerException if the condition is null
1019      */
1020     public final int getWaitQueueLength(ConditionObject condition) {
1021         if (!owns(condition))
1022             throw new IllegalArgumentException("Not owner");
1023         return condition.getWaitQueueLength();
1024     }
1025 
1026     /**
1027      * Returns a collection containing those threads that may be
1028      * waiting on the given condition associated with this
1029      * synchronizer.  Because the actual set of threads may change
1030      * dynamically while constructing this result, the returned
1031      * collection is only a best-effort estimate. The elements of the
1032      * returned collection are in no particular order.
1033      *
1034      * @param condition the condition
1035      * @return the collection of threads
1036      * @throws IllegalMonitorStateException if exclusive synchronization
1037      *         is not held
1038      * @throws IllegalArgumentException if the given condition is
1039      *         not associated with this synchronizer
1040      * @throws NullPointerException if the condition is null
1041      */
1042     public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1043         if (!owns(condition))
1044             throw new IllegalArgumentException("Not owner");
1045         return condition.getWaitingThreads();
1046     }
1047 
1048     /**
1049      * Condition implementation for a {@link AbstractQueuedLongSynchronizer}
1050      * serving as the basis of a {@link Lock} implementation.
1051      *
1052      * <p>Method documentation for this class describes mechanics,
1053      * not behavioral specifications from the point of view of Lock
1054      * and Condition users. Exported versions of this class will in
1055      * general need to be accompanied by documentation describing
1056      * condition semantics that rely on those of the associated
1057      * {@code AbstractQueuedLongSynchronizer}.
1058      *
1059      * <p>This class is Serializable, but all fields are transient,
1060      * so deserialized conditions have no waiters.
1061      */
1062     public class ConditionObject implements Condition, java.io.Serializable {
1063         private static final long serialVersionUID = 1173984872572414699L;
1064         /** First node of condition queue. */
1065         private transient ConditionNode firstWaiter;
1066         /** Last node of condition queue. */
1067         private transient ConditionNode lastWaiter;
1068 
1069         /**
1070          * Creates a new {@code ConditionObject} instance.
1071          */
1072         public ConditionObject() { }
1073 
1074         // Signalling methods
1075 
1076         /**
1077          * Removes and transfers one or all waiters to sync queue.
1078          */
1079         private void doSignal(ConditionNode first, boolean all) {
1080             while (first != null) {
1081                 ConditionNode next = first.nextWaiter;
1082                 if ((firstWaiter = next) == null)
1083                     lastWaiter = null;
1084                 if ((first.getAndUnsetStatus(COND) & COND) != 0) {
1085                     enqueue(first);
1086                     if (!all)
1087                         break;
1088                 }
1089                 first = next;
1090             }
1091         }
1092 
1093         /**
1094          * Moves the longest-waiting thread, if one exists, from the
1095          * wait queue for this condition to the wait queue for the
1096          * owning lock.
1097          *
1098          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1099          *         returns {@code false}
1100          */
1101         public final void signal() {
1102             ConditionNode first = firstWaiter;
1103             if (!isHeldExclusively())
1104                 throw new IllegalMonitorStateException();
1105             if (first != null)
1106                 doSignal(first, false);
1107         }
1108 
1109         /**
1110          * Moves all threads from the wait queue for this condition to
1111          * the wait queue for the owning lock.
1112          *
1113          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1114          *         returns {@code false}
1115          */
1116         public final void signalAll() {
1117             ConditionNode first = firstWaiter;
1118             if (!isHeldExclusively())
1119                 throw new IllegalMonitorStateException();
1120             if (first != null)
1121                 doSignal(first, true);
1122         }
1123 
1124         // Waiting methods
1125 
1126         /**
1127          * Adds node to condition list and releases lock.
1128          *
1129          * @param node the node
1130          * @return savedState to reacquire after wait
1131          */
1132         private long enableWait(ConditionNode node) {
1133             if (isHeldExclusively()) {
1134                 node.waiter = Thread.currentThread();
1135                 node.setStatusRelaxed(COND | WAITING);
1136                 ConditionNode last = lastWaiter;
1137                 if (last == null)
1138                     firstWaiter = node;
1139                 else
1140                     last.nextWaiter = node;
1141                 lastWaiter = node;
1142                 long savedState = getState();
1143                 if (release(savedState))
1144                     return savedState;
1145             }
1146             node.status = CANCELLED; // lock not held or inconsistent
1147             throw new IllegalMonitorStateException();
1148         }
1149 
1150         /**
1151          * Returns true if a node that was initially placed on a condition
1152          * queue is now ready to reacquire on sync queue.
1153          * @param node the node
1154          * @return true if is reacquiring
1155          */
1156         private boolean canReacquire(ConditionNode node) {
1157             // check links, not status to avoid enqueue race
1158             return node != null && node.prev != null && isEnqueued(node);
1159         }
1160 
1161         /**
1162          * Unlinks the given node and other non-waiting nodes from
1163          * condition queue unless already unlinked.
1164          */
1165         private void unlinkCancelledWaiters(ConditionNode node) {
1166             if (node == null || node.nextWaiter != null || node == lastWaiter) {
1167                 ConditionNode w = firstWaiter, trail = null;
1168                 while (w != null) {
1169                     ConditionNode next = w.nextWaiter;
1170                     if ((w.status & COND) == 0) {
1171                         w.nextWaiter = null;
1172                         if (trail == null)
1173                             firstWaiter = next;
1174                         else
1175                             trail.nextWaiter = next;
1176                         if (next == null)
1177                             lastWaiter = trail;
1178                     } else
1179                         trail = w;
1180                     w = next;
1181                 }
1182             }
1183         }
1184 
1185         /**
1186          * Implements uninterruptible condition wait.
1187          * <ol>
1188          * <li>Save lock state returned by {@link #getState}.
1189          * <li>Invoke {@link #release} with saved state as argument,
1190          *     throwing IllegalMonitorStateException if it fails.
1191          * <li>Block until signalled.
1192          * <li>Reacquire by invoking specialized version of
1193          *     {@link #acquire} with saved state as argument.
1194          * </ol>
1195          */
1196         public final void awaitUninterruptibly() {
1197             ConditionNode node = new ConditionNode();
1198             long savedState = enableWait(node);
1199             LockSupport.setCurrentBlocker(this); // for back-compatibility
1200             boolean interrupted = false;
1201             while (!canReacquire(node)) {
1202                 if (Thread.interrupted())
1203                     interrupted = true;
1204                 else if ((node.status & COND) != 0) {
1205                     try {
1206                         ForkJoinPool.managedBlock(node);
1207                     } catch (InterruptedException ie) {
1208                         interrupted = true;
1209                     }
1210                 } else
1211                     Thread.onSpinWait();    // awoke while enqueuing
1212             }
1213             LockSupport.setCurrentBlocker(null);
1214             node.clearStatus();
1215             acquire(node, savedState, false, false, false, 0L);
1216             if (interrupted)
1217                 Thread.currentThread().interrupt();
1218         }
1219 
1220         /**
1221          * Implements interruptible condition wait.
1222          * <ol>
1223          * <li>If current thread is interrupted, throw InterruptedException.
1224          * <li>Save lock state returned by {@link #getState}.
1225          * <li>Invoke {@link #release} with saved state as argument,
1226          *     throwing IllegalMonitorStateException if it fails.
1227          * <li>Block until signalled or interrupted.
1228          * <li>Reacquire by invoking specialized version of
1229          *     {@link #acquire} with saved state as argument.
1230          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1231          * </ol>
1232          */
1233         public final void await() throws InterruptedException {
1234             if (Thread.interrupted())
1235                 throw new InterruptedException();
1236             ConditionNode node = new ConditionNode();
1237             long savedState = enableWait(node);
1238             LockSupport.setCurrentBlocker(this); // for back-compatibility
1239             boolean interrupted = false, cancelled = false;
1240             while (!canReacquire(node)) {
1241                 if (interrupted |= Thread.interrupted()) {
1242                     if (cancelled = (node.getAndUnsetStatus(COND) & COND) != 0)
1243                         break;              // else interrupted after signal
1244                 } else if ((node.status & COND) != 0) {
1245                     try {
1246                         ForkJoinPool.managedBlock(node);
1247                     } catch (InterruptedException ie) {
1248                         interrupted = true;
1249                     }
1250                 } else
1251                     Thread.onSpinWait();    // awoke while enqueuing
1252             }
1253             LockSupport.setCurrentBlocker(null);
1254             node.clearStatus();
1255             acquire(node, savedState, false, false, false, 0L);
1256             if (interrupted) {
1257                 if (cancelled) {
1258                     unlinkCancelledWaiters(node);
1259                     throw new InterruptedException();
1260                 }
1261                 Thread.currentThread().interrupt();
1262             }
1263         }
1264 
1265         /**
1266          * Implements timed condition wait.
1267          * <ol>
1268          * <li>If current thread is interrupted, throw InterruptedException.
1269          * <li>Save lock state returned by {@link #getState}.
1270          * <li>Invoke {@link #release} with saved state as argument,
1271          *     throwing IllegalMonitorStateException if it fails.
1272          * <li>Block until signalled, interrupted, or timed out.
1273          * <li>Reacquire by invoking specialized version of
1274          *     {@link #acquire} with saved state as argument.
1275          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1276          * </ol>
1277          */
1278         public final long awaitNanos(long nanosTimeout)
1279                 throws InterruptedException {
1280             if (Thread.interrupted())
1281                 throw new InterruptedException();
1282             ConditionNode node = new ConditionNode();
1283             long savedState = enableWait(node);
1284             long nanos = (nanosTimeout < 0L) ? 0L : nanosTimeout;
1285             long deadline = System.nanoTime() + nanos;
1286             boolean cancelled = false, interrupted = false;
1287             while (!canReacquire(node)) {
1288                 if ((interrupted |= Thread.interrupted()) ||
1289                     (nanos = deadline - System.nanoTime()) <= 0L) {
1290                     if (cancelled = (node.getAndUnsetStatus(COND) & COND) != 0)
1291                         break;
1292                 } else
1293                     LockSupport.parkNanos(this, nanos);
1294             }
1295             node.clearStatus();
1296             acquire(node, savedState, false, false, false, 0L);
1297             if (cancelled) {
1298                 unlinkCancelledWaiters(node);
1299                 if (interrupted)
1300                     throw new InterruptedException();
1301             } else if (interrupted)
1302                 Thread.currentThread().interrupt();
1303             long remaining = deadline - System.nanoTime(); // avoid overflow
1304             return (remaining <= nanosTimeout) ? remaining : Long.MIN_VALUE;
1305         }
1306 
1307         /**
1308          * Implements absolute timed condition wait.
1309          * <ol>
1310          * <li>If current thread is interrupted, throw InterruptedException.
1311          * <li>Save lock state returned by {@link #getState}.
1312          * <li>Invoke {@link #release} with saved state as argument,
1313          *     throwing IllegalMonitorStateException if it fails.
1314          * <li>Block until signalled, interrupted, or timed out.
1315          * <li>Reacquire by invoking specialized version of
1316          *     {@link #acquire} with saved state as argument.
1317          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1318          * <li>If timed out while blocked in step 4, return false, else true.
1319          * </ol>
1320          */
1321         public final boolean awaitUntil(Date deadline)
1322                 throws InterruptedException {
1323             long abstime = deadline.getTime();
1324             if (Thread.interrupted())
1325                 throw new InterruptedException();
1326             ConditionNode node = new ConditionNode();
1327             long savedState = enableWait(node);
1328             boolean cancelled = false, interrupted = false;
1329             while (!canReacquire(node)) {
1330                 if ((interrupted |= Thread.interrupted()) ||
1331                     System.currentTimeMillis() >= abstime) {
1332                     if (cancelled = (node.getAndUnsetStatus(COND) & COND) != 0)
1333                         break;
1334                 } else
1335                     LockSupport.parkUntil(this, abstime);
1336             }
1337             node.clearStatus();
1338             acquire(node, savedState, false, false, false, 0L);
1339             if (cancelled) {
1340                 unlinkCancelledWaiters(node);
1341                 if (interrupted)
1342                     throw new InterruptedException();
1343             } else if (interrupted)
1344                 Thread.currentThread().interrupt();
1345             return !cancelled;
1346         }
1347 
1348         /**
1349          * Implements timed condition wait.
1350          * <ol>
1351          * <li>If current thread is interrupted, throw InterruptedException.
1352          * <li>Save lock state returned by {@link #getState}.
1353          * <li>Invoke {@link #release} with saved state as argument,
1354          *     throwing IllegalMonitorStateException if it fails.
1355          * <li>Block until signalled, interrupted, or timed out.
1356          * <li>Reacquire by invoking specialized version of
1357          *     {@link #acquire} with saved state as argument.
1358          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1359          * <li>If timed out while blocked in step 4, return false, else true.
1360          * </ol>
1361          */
1362         public final boolean await(long time, TimeUnit unit)
1363                 throws InterruptedException {
1364             long nanosTimeout = unit.toNanos(time);
1365             if (Thread.interrupted())
1366                 throw new InterruptedException();
1367             ConditionNode node = new ConditionNode();
1368             long savedState = enableWait(node);
1369             long nanos = (nanosTimeout < 0L) ? 0L : nanosTimeout;
1370             long deadline = System.nanoTime() + nanos;
1371             boolean cancelled = false, interrupted = false;
1372             while (!canReacquire(node)) {
1373                 if ((interrupted |= Thread.interrupted()) ||
1374                     (nanos = deadline - System.nanoTime()) <= 0L) {
1375                     if (cancelled = (node.getAndUnsetStatus(COND) & COND) != 0)
1376                         break;
1377                 } else
1378                     LockSupport.parkNanos(this, nanos);
1379             }
1380             node.clearStatus();
1381             acquire(node, savedState, false, false, false, 0L);
1382             if (cancelled) {
1383                 unlinkCancelledWaiters(node);
1384                 if (interrupted)
1385                     throw new InterruptedException();
1386             } else if (interrupted)
1387                 Thread.currentThread().interrupt();
1388             return !cancelled;
1389         }
1390 
1391         //  support for instrumentation
1392 
1393         /**
1394          * Returns true if this condition was created by the given
1395          * synchronization object.
1396          *
1397          * @return {@code true} if owned
1398          */
1399         final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1400             return sync == AbstractQueuedLongSynchronizer.this;
1401         }
1402 
1403         /**
1404          * Queries whether any threads are waiting on this condition.
1405          * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters(ConditionObject)}.
1406          *
1407          * @return {@code true} if there are any waiting threads
1408          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1409          *         returns {@code false}
1410          */
1411         protected final boolean hasWaiters() {
1412             if (!isHeldExclusively())
1413                 throw new IllegalMonitorStateException();
1414             for (ConditionNode w = firstWaiter; w != null; w = w.nextWaiter) {
1415                 if ((w.status & COND) != 0)
1416                     return true;
1417             }
1418             return false;
1419         }
1420 
1421         /**
1422          * Returns an estimate of the number of threads waiting on
1423          * this condition.
1424          * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength(ConditionObject)}.
1425          *
1426          * @return the estimated number of waiting threads
1427          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1428          *         returns {@code false}
1429          */
1430         protected final int getWaitQueueLength() {
1431             if (!isHeldExclusively())
1432                 throw new IllegalMonitorStateException();
1433             int n = 0;
1434             for (ConditionNode w = firstWaiter; w != null; w = w.nextWaiter) {
1435                 if ((w.status & COND) != 0)
1436                     ++n;
1437             }
1438             return n;
1439         }
1440 
1441         /**
1442          * Returns a collection containing those threads that may be
1443          * waiting on this Condition.
1444          * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads(ConditionObject)}.
1445          *
1446          * @return the collection of threads
1447          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1448          *         returns {@code false}
1449          */
1450         protected final Collection<Thread> getWaitingThreads() {
1451             if (!isHeldExclusively())
1452                 throw new IllegalMonitorStateException();
1453             ArrayList<Thread> list = new ArrayList<>();
1454             for (ConditionNode w = firstWaiter; w != null; w = w.nextWaiter) {
1455                 if ((w.status & COND) != 0) {
1456                     Thread t = w.waiter;
1457                     if (t != null)
1458                         list.add(t);
1459                 }
1460             }
1461             return list;
1462         }
1463     }
1464 
1465     // Unsafe
1466     private static final Unsafe U = Unsafe.getUnsafe();
1467     private static final long STATE
1468         = U.objectFieldOffset(AbstractQueuedLongSynchronizer.class, "state");
1469     private static final long HEAD
1470         = U.objectFieldOffset(AbstractQueuedLongSynchronizer.class, "head");
1471     private static final long TAIL
1472         = U.objectFieldOffset(AbstractQueuedLongSynchronizer.class, "tail");
1473 
1474     static {
1475         Class<?> ensureLoaded = LockSupport.class;
1476     }
1477 }