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 import java.util.concurrent.locks.AbstractQueuedSynchronizer.Node;
  45 
  46 import jdk.internal.misc.Strands;
  47 
  48 /**
  49  * A version of {@link AbstractQueuedSynchronizer} in
  50  * which synchronization state is maintained as a {@code long}.
  51  * This class has exactly the same structure, properties, and methods
  52  * as {@code AbstractQueuedSynchronizer} with the exception
  53  * that all state-related parameters and results are defined
  54  * as {@code long} rather than {@code int}. This class
  55  * may be useful when creating synchronizers such as
  56  * multilevel locks and barriers that require
  57  * 64 bits of state.
  58  *
  59  * <p>See {@link AbstractQueuedSynchronizer} for usage
  60  * notes and examples.
  61  *
  62  * @since 1.6
  63  * @author Doug Lea
  64  */
  65 public abstract class AbstractQueuedLongSynchronizer
  66     extends AbstractOwnableSynchronizer
  67     implements java.io.Serializable {
  68 
  69     private static final long serialVersionUID = 7373984972572414692L;
  70 
  71     /*
  72      * To keep sources in sync, the remainder of this source file is
  73      * exactly cloned from AbstractQueuedSynchronizer, replacing class
  74      * name and changing ints related with sync state to longs. Please
  75      * keep it that way.
  76      */
  77 
  78     /**
  79      * Creates a new {@code AbstractQueuedLongSynchronizer} instance
  80      * with initial synchronization state of zero.
  81      */
  82     protected AbstractQueuedLongSynchronizer() { }
  83 
  84     /**
  85      * Head of the wait queue, lazily initialized.  Except for
  86      * initialization, it is modified only via method setHead.  Note:
  87      * If head exists, its waitStatus is guaranteed not to be
  88      * CANCELLED.
  89      */
  90     private transient volatile Node head;
  91 
  92     /**
  93      * Tail of the wait queue, lazily initialized.  Modified only via
  94      * method enq to add new wait node.
  95      */
  96     private transient volatile Node tail;
  97 
  98     /**
  99      * The synchronization state.
 100      */
 101     private volatile long state;
 102 
 103     /**
 104      * Returns the current value of synchronization state.
 105      * This operation has memory semantics of a {@code volatile} read.
 106      * @return current state value
 107      */
 108     protected final long getState() {
 109         return state;
 110     }
 111 
 112     /**
 113      * Sets the value of synchronization state.
 114      * This operation has memory semantics of a {@code volatile} write.
 115      * @param newState the new state value
 116      */
 117     protected final void setState(long newState) {
 118         // See JDK-8180620: Clarify VarHandle mixed-access subtleties
 119         STATE.setVolatile(this, newState);
 120     }
 121 
 122     /**
 123      * Atomically sets synchronization state to the given updated
 124      * value if the current state value equals the expected value.
 125      * This operation has memory semantics of a {@code volatile} read
 126      * and write.
 127      *
 128      * @param expect the expected value
 129      * @param update the new value
 130      * @return {@code true} if successful. False return indicates that the actual
 131      *         value was not equal to the expected value.
 132      */
 133     protected final boolean compareAndSetState(long expect, long update) {
 134         return STATE.compareAndSet(this, expect, update);
 135     }
 136 
 137     // Queuing utilities
 138 
 139     /**
 140      * The number of nanoseconds for which it is faster to spin
 141      * rather than to use timed park. A rough estimate suffices
 142      * to improve responsiveness with very short timeouts.
 143      */
 144     static final long SPIN_FOR_TIMEOUT_THRESHOLD = 1000L;
 145 
 146     /**
 147      * Inserts node into queue, initializing if necessary. See picture above.
 148      * @param node the node to insert
 149      * @return node's predecessor
 150      */
 151     private Node enq(Node node) {
 152         for (;;) {
 153             Node oldTail = tail;
 154             if (oldTail != null) {
 155                 node.setPrevRelaxed(oldTail);
 156                 if (compareAndSetTail(oldTail, node)) {
 157                     oldTail.next = node;
 158                     return oldTail;
 159                 }
 160             } else {
 161                 initializeSyncQueue();
 162             }
 163         }
 164     }
 165 
 166     /**
 167      * Creates and enqueues node for current thread and given mode.
 168      *
 169      * @param mode Node.EXCLUSIVE for exclusive, Node.SHARED for shared
 170      * @return the new node
 171      */
 172     private Node addWaiter(Node mode) {
 173         Node node = new Node(mode);
 174 
 175         for (;;) {
 176             Node oldTail = tail;
 177             if (oldTail != null) {
 178                 node.setPrevRelaxed(oldTail);
 179                 if (compareAndSetTail(oldTail, node)) {
 180                     oldTail.next = node;
 181                     return node;
 182                 }
 183             } else {
 184                 initializeSyncQueue();
 185             }
 186         }
 187     }
 188 
 189     /**
 190      * Sets head of queue to be node, thus dequeuing. Called only by
 191      * acquire methods.  Also nulls out unused fields for sake of GC
 192      * and to suppress unnecessary signals and traversals.
 193      *
 194      * @param node the node
 195      */
 196     private void setHead(Node node) {
 197         head = node;
 198         node.strand = null;
 199         node.prev = null;
 200     }
 201 
 202     /**
 203      * Wakes up node's successor, if one exists.
 204      *
 205      * @param node the node
 206      */
 207     private void unparkSuccessor(Node node) {
 208         /*
 209          * If status is negative (i.e., possibly needing signal) try
 210          * to clear in anticipation of signalling.  It is OK if this
 211          * fails or if status is changed by waiting thread.
 212          */
 213         int ws = node.waitStatus;
 214         if (ws < 0)
 215             node.compareAndSetWaitStatus(ws, 0);
 216 
 217         /*
 218          * Thread to unpark is held in successor, which is normally
 219          * just the next node.  But if cancelled or apparently null,
 220          * traverse backwards from tail to find the actual
 221          * non-cancelled successor.
 222          */
 223         Node s = node.next;
 224         if (s == null || s.waitStatus > 0) {
 225             s = null;
 226             for (Node p = tail; p != node && p != null; p = p.prev)
 227                 if (p.waitStatus <= 0)
 228                     s = p;
 229         }
 230         if (s != null)
 231             LockSupport.unpark(s.strand);
 232     }
 233 
 234     /**
 235      * Release action for shared mode -- signals successor and ensures
 236      * propagation. (Note: For exclusive mode, release just amounts
 237      * to calling unparkSuccessor of head if it needs signal.)
 238      */
 239     private void doReleaseShared() {
 240         /*
 241          * Ensure that a release propagates, even if there are other
 242          * in-progress acquires/releases.  This proceeds in the usual
 243          * way of trying to unparkSuccessor of head if it needs
 244          * signal. But if it does not, status is set to PROPAGATE to
 245          * ensure that upon release, propagation continues.
 246          * Additionally, we must loop in case a new node is added
 247          * while we are doing this. Also, unlike other uses of
 248          * unparkSuccessor, we need to know if CAS to reset status
 249          * fails, if so rechecking.
 250          */
 251         for (;;) {
 252             Node h = head;
 253             if (h != null && h != tail) {
 254                 int ws = h.waitStatus;
 255                 if (ws == Node.SIGNAL) {
 256                     if (!h.compareAndSetWaitStatus(Node.SIGNAL, 0))
 257                         continue;            // loop to recheck cases
 258                     unparkSuccessor(h);
 259                 }
 260                 else if (ws == 0 &&
 261                          !h.compareAndSetWaitStatus(0, Node.PROPAGATE))
 262                     continue;                // loop on failed CAS
 263             }
 264             if (h == head)                   // loop if head changed
 265                 break;
 266         }
 267     }
 268 
 269     /**
 270      * Sets head of queue, and checks if successor may be waiting
 271      * in shared mode, if so propagating if either propagate > 0 or
 272      * PROPAGATE status was set.
 273      *
 274      * @param node the node
 275      * @param propagate the return value from a tryAcquireShared
 276      */
 277     private void setHeadAndPropagate(Node node, long propagate) {
 278         Node h = head; // Record old head for check below
 279         setHead(node);
 280         /*
 281          * Try to signal next queued node if:
 282          *   Propagation was indicated by caller,
 283          *     or was recorded (as h.waitStatus either before
 284          *     or after setHead) by a previous operation
 285          *     (note: this uses sign-check of waitStatus because
 286          *      PROPAGATE status may transition to SIGNAL.)
 287          * and
 288          *   The next node is waiting in shared mode,
 289          *     or we don't know, because it appears null
 290          *
 291          * The conservatism in both of these checks may cause
 292          * unnecessary wake-ups, but only when there are multiple
 293          * racing acquires/releases, so most need signals now or soon
 294          * anyway.
 295          */
 296         if (propagate > 0 || h == null || h.waitStatus < 0 ||
 297             (h = head) == null || h.waitStatus < 0) {
 298             Node s = node.next;
 299             if (s == null || s.isShared())
 300                 doReleaseShared();
 301         }
 302     }
 303 
 304     // Utilities for various versions of acquire
 305 
 306     /**
 307      * Cancels an ongoing attempt to acquire.
 308      *
 309      * @param node the node
 310      */
 311     private void cancelAcquire(Node node) {
 312         // Ignore if node doesn't exist
 313         if (node == null)
 314             return;
 315 
 316         node.strand = null;
 317 
 318         // Skip cancelled predecessors
 319         Node pred = node.prev;
 320         while (pred.waitStatus > 0)
 321             node.prev = pred = pred.prev;
 322 
 323         // predNext is the apparent node to unsplice. CASes below will
 324         // fail if not, in which case, we lost race vs another cancel
 325         // or signal, so no further action is necessary, although with
 326         // a possibility that a cancelled node may transiently remain
 327         // reachable.
 328         Node predNext = pred.next;
 329 
 330         // Can use unconditional write instead of CAS here.
 331         // After this atomic step, other Nodes can skip past us.
 332         // Before, we are free of interference from other threads.
 333         node.waitStatus = Node.CANCELLED;
 334 
 335         // If we are the tail, remove ourselves.
 336         if (node == tail && compareAndSetTail(node, pred)) {
 337             pred.compareAndSetNext(predNext, null);
 338         } else {
 339             // If successor needs signal, try to set pred's next-link
 340             // so it will get one. Otherwise wake it up to propagate.
 341             int ws;
 342             if (pred != head &&
 343                 ((ws = pred.waitStatus) == Node.SIGNAL ||
 344                  (ws <= 0 && pred.compareAndSetWaitStatus(ws, Node.SIGNAL))) &&
 345                 pred.strand != null) {
 346                 Node next = node.next;
 347                 if (next != null && next.waitStatus <= 0)
 348                     pred.compareAndSetNext(predNext, next);
 349             } else {
 350                 unparkSuccessor(node);
 351             }
 352 
 353             node.next = node; // help GC
 354         }
 355     }
 356 
 357     /**
 358      * Checks and updates status for a node that failed to acquire.
 359      * Returns true if thread should block. This is the main signal
 360      * control in all acquire loops.  Requires that pred == node.prev.
 361      *
 362      * @param pred node's predecessor holding status
 363      * @param node the node
 364      * @return {@code true} if thread should block
 365      */
 366     private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
 367         int ws = pred.waitStatus;
 368         if (ws == Node.SIGNAL)
 369             /*
 370              * This node has already set status asking a release
 371              * to signal it, so it can safely park.
 372              */
 373             return true;
 374         if (ws > 0) {
 375             /*
 376              * Predecessor was cancelled. Skip over predecessors and
 377              * indicate retry.
 378              */
 379             do {
 380                 node.prev = pred = pred.prev;
 381             } while (pred.waitStatus > 0);
 382             pred.next = node;
 383         } else {
 384             /*
 385              * waitStatus must be 0 or PROPAGATE.  Indicate that we
 386              * need a signal, but don't park yet.  Caller will need to
 387              * retry to make sure it cannot acquire before parking.
 388              */
 389             pred.compareAndSetWaitStatus(ws, Node.SIGNAL);
 390         }
 391         return false;
 392     }
 393 
 394     /**
 395      * Convenience method to interrupt current thread.
 396      */
 397     static void selfInterrupt() {
 398         Thread.currentThread().interrupt();
 399     }
 400 
 401     /**
 402      * Convenience method to park and then check if interrupted.
 403      *
 404      * @return {@code true} if interrupted
 405      */
 406     private final boolean parkAndCheckInterrupt() {
 407         LockSupport.park(this);
 408         return Thread.interrupted();
 409     }
 410 
 411     /*
 412      * Various flavors of acquire, varying in exclusive/shared and
 413      * control modes.  Each is mostly the same, but annoyingly
 414      * different.  Only a little bit of factoring is possible due to
 415      * interactions of exception mechanics (including ensuring that we
 416      * cancel if tryAcquire throws exception) and other control, at
 417      * least not without hurting performance too much.
 418      */
 419 
 420     /**
 421      * Acquires in exclusive uninterruptible mode for thread already in
 422      * queue. Used by condition wait methods as well as acquire.
 423      *
 424      * @param node the node
 425      * @param arg the acquire argument
 426      * @return {@code true} if interrupted while waiting
 427      */
 428     final boolean acquireQueued(final Node node, long arg) {
 429         boolean interrupted = false;
 430         try {
 431             for (;;) {
 432                 final Node p = node.predecessor();
 433                 if (p == head && tryAcquire(arg)) {
 434                     setHead(node);
 435                     p.next = null; // help GC
 436                     return interrupted;
 437                 }
 438                 if (shouldParkAfterFailedAcquire(p, node))
 439                     interrupted |= parkAndCheckInterrupt();
 440             }
 441         } catch (Throwable t) {
 442             cancelAcquire(node);
 443             if (interrupted)
 444                 selfInterrupt();
 445             throw t;
 446         }
 447     }
 448 
 449     /**
 450      * Acquires in exclusive interruptible mode.
 451      * @param arg the acquire argument
 452      */
 453     private void doAcquireInterruptibly(long arg)
 454         throws InterruptedException {
 455         final Node node = addWaiter(Node.EXCLUSIVE);
 456         try {
 457             for (;;) {
 458                 final Node p = node.predecessor();
 459                 if (p == head && tryAcquire(arg)) {
 460                     setHead(node);
 461                     p.next = null; // help GC
 462                     return;
 463                 }
 464                 if (shouldParkAfterFailedAcquire(p, node) &&
 465                     parkAndCheckInterrupt())
 466                     throw new InterruptedException();
 467             }
 468         } catch (Throwable t) {
 469             cancelAcquire(node);
 470             throw t;
 471         }
 472     }
 473 
 474     /**
 475      * Acquires in exclusive timed mode.
 476      *
 477      * @param arg the acquire argument
 478      * @param nanosTimeout max wait time
 479      * @return {@code true} if acquired
 480      */
 481     private boolean doAcquireNanos(long arg, long nanosTimeout)
 482             throws InterruptedException {
 483         if (nanosTimeout <= 0L)
 484             return false;
 485         final long deadline = System.nanoTime() + nanosTimeout;
 486         final Node node = addWaiter(Node.EXCLUSIVE);
 487         try {
 488             for (;;) {
 489                 final Node p = node.predecessor();
 490                 if (p == head && tryAcquire(arg)) {
 491                     setHead(node);
 492                     p.next = null; // help GC
 493                     return true;
 494                 }
 495                 nanosTimeout = deadline - System.nanoTime();
 496                 if (nanosTimeout <= 0L) {
 497                     cancelAcquire(node);
 498                     return false;
 499                 }
 500                 if (shouldParkAfterFailedAcquire(p, node) &&
 501                     nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
 502                     LockSupport.parkNanos(this, nanosTimeout);
 503                 if (Thread.interrupted())
 504                     throw new InterruptedException();
 505             }
 506         } catch (Throwable t) {
 507             cancelAcquire(node);
 508             throw t;
 509         }
 510     }
 511 
 512     /**
 513      * Acquires in shared uninterruptible mode.
 514      * @param arg the acquire argument
 515      */
 516     private void doAcquireShared(long arg) {
 517         final Node node = addWaiter(Node.SHARED);
 518         boolean interrupted = false;
 519         try {
 520             for (;;) {
 521                 final Node p = node.predecessor();
 522                 if (p == head) {
 523                     long r = tryAcquireShared(arg);
 524                     if (r >= 0) {
 525                         setHeadAndPropagate(node, r);
 526                         p.next = null; // help GC
 527                         return;
 528                     }
 529                 }
 530                 if (shouldParkAfterFailedAcquire(p, node))
 531                     interrupted |= parkAndCheckInterrupt();
 532             }
 533         } catch (Throwable t) {
 534             cancelAcquire(node);
 535             throw t;
 536         } finally {
 537             if (interrupted)
 538                 selfInterrupt();
 539         }
 540     }
 541 
 542     /**
 543      * Acquires in shared interruptible mode.
 544      * @param arg the acquire argument
 545      */
 546     private void doAcquireSharedInterruptibly(long arg)
 547         throws InterruptedException {
 548         final Node node = addWaiter(Node.SHARED);
 549         try {
 550             for (;;) {
 551                 final Node p = node.predecessor();
 552                 if (p == head) {
 553                     long r = tryAcquireShared(arg);
 554                     if (r >= 0) {
 555                         setHeadAndPropagate(node, r);
 556                         p.next = null; // help GC
 557                         return;
 558                     }
 559                 }
 560                 if (shouldParkAfterFailedAcquire(p, node) &&
 561                     parkAndCheckInterrupt())
 562                     throw new InterruptedException();
 563             }
 564         } catch (Throwable t) {
 565             cancelAcquire(node);
 566             throw t;
 567         }
 568     }
 569 
 570     /**
 571      * Acquires in shared timed mode.
 572      *
 573      * @param arg the acquire argument
 574      * @param nanosTimeout max wait time
 575      * @return {@code true} if acquired
 576      */
 577     private boolean doAcquireSharedNanos(long arg, long nanosTimeout)
 578             throws InterruptedException {
 579         if (nanosTimeout <= 0L)
 580             return false;
 581         final long deadline = System.nanoTime() + nanosTimeout;
 582         final Node node = addWaiter(Node.SHARED);
 583         try {
 584             for (;;) {
 585                 final Node p = node.predecessor();
 586                 if (p == head) {
 587                     long r = tryAcquireShared(arg);
 588                     if (r >= 0) {
 589                         setHeadAndPropagate(node, r);
 590                         p.next = null; // help GC
 591                         return true;
 592                     }
 593                 }
 594                 nanosTimeout = deadline - System.nanoTime();
 595                 if (nanosTimeout <= 0L) {
 596                     cancelAcquire(node);
 597                     return false;
 598                 }
 599                 if (shouldParkAfterFailedAcquire(p, node) &&
 600                     nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
 601                     LockSupport.parkNanos(this, nanosTimeout);
 602                 if (Thread.interrupted())
 603                     throw new InterruptedException();
 604             }
 605         } catch (Throwable t) {
 606             cancelAcquire(node);
 607             throw t;
 608         }
 609     }
 610 
 611     // Main exported methods
 612 
 613     /**
 614      * Attempts to acquire in exclusive mode. This method should query
 615      * if the state of the object permits it to be acquired in the
 616      * exclusive mode, and if so to acquire it.
 617      *
 618      * <p>This method is always invoked by the thread performing
 619      * acquire.  If this method reports failure, the acquire method
 620      * may queue the thread, if it is not already queued, until it is
 621      * signalled by a release from some other thread. This can be used
 622      * to implement method {@link Lock#tryLock()}.
 623      *
 624      * <p>The default
 625      * implementation throws {@link UnsupportedOperationException}.
 626      *
 627      * @param arg the acquire argument. This value is always the one
 628      *        passed to an acquire method, or is the value saved on entry
 629      *        to a condition wait.  The value is otherwise uninterpreted
 630      *        and can represent anything you like.
 631      * @return {@code true} if successful. Upon success, this object has
 632      *         been acquired.
 633      * @throws IllegalMonitorStateException if acquiring would place this
 634      *         synchronizer in an illegal state. This exception must be
 635      *         thrown in a consistent fashion for synchronization to work
 636      *         correctly.
 637      * @throws UnsupportedOperationException if exclusive mode is not supported
 638      */
 639     protected boolean tryAcquire(long arg) {
 640         throw new UnsupportedOperationException();
 641     }
 642 
 643     /**
 644      * Attempts to set the state to reflect a release in exclusive
 645      * mode.
 646      *
 647      * <p>This method is always invoked by the thread performing release.
 648      *
 649      * <p>The default implementation throws
 650      * {@link UnsupportedOperationException}.
 651      *
 652      * @param arg the release argument. This value is always the one
 653      *        passed to a release method, or the current state value upon
 654      *        entry to a condition wait.  The value is otherwise
 655      *        uninterpreted and can represent anything you like.
 656      * @return {@code true} if this object is now in a fully released
 657      *         state, so that any waiting threads may attempt to acquire;
 658      *         and {@code false} otherwise.
 659      * @throws IllegalMonitorStateException if releasing would place this
 660      *         synchronizer in an illegal state. This exception must be
 661      *         thrown in a consistent fashion for synchronization to work
 662      *         correctly.
 663      * @throws UnsupportedOperationException if exclusive mode is not supported
 664      */
 665     protected boolean tryRelease(long arg) {
 666         throw new UnsupportedOperationException();
 667     }
 668 
 669     /**
 670      * Attempts to acquire in shared mode. This method should query if
 671      * the state of the object permits it to be acquired in the shared
 672      * mode, and if so to acquire it.
 673      *
 674      * <p>This method is always invoked by the thread performing
 675      * acquire.  If this method reports failure, the acquire method
 676      * may queue the thread, if it is not already queued, until it is
 677      * signalled by a release from some other thread.
 678      *
 679      * <p>The default implementation throws {@link
 680      * UnsupportedOperationException}.
 681      *
 682      * @param arg the acquire argument. This value is always the one
 683      *        passed to an acquire method, or is the value saved on entry
 684      *        to a condition wait.  The value is otherwise uninterpreted
 685      *        and can represent anything you like.
 686      * @return a negative value on failure; zero if acquisition in shared
 687      *         mode succeeded but no subsequent shared-mode acquire can
 688      *         succeed; and a positive value if acquisition in shared
 689      *         mode succeeded and subsequent shared-mode acquires might
 690      *         also succeed, in which case a subsequent waiting thread
 691      *         must check availability. (Support for three different
 692      *         return values enables this method to be used in contexts
 693      *         where acquires only sometimes act exclusively.)  Upon
 694      *         success, this object has been acquired.
 695      * @throws IllegalMonitorStateException if acquiring would place this
 696      *         synchronizer in an illegal state. This exception must be
 697      *         thrown in a consistent fashion for synchronization to work
 698      *         correctly.
 699      * @throws UnsupportedOperationException if shared mode is not supported
 700      */
 701     protected long tryAcquireShared(long arg) {
 702         throw new UnsupportedOperationException();
 703     }
 704 
 705     /**
 706      * Attempts to set the state to reflect a release in shared mode.
 707      *
 708      * <p>This method is always invoked by the thread performing release.
 709      *
 710      * <p>The default implementation throws
 711      * {@link UnsupportedOperationException}.
 712      *
 713      * @param arg the release argument. This value is always the one
 714      *        passed to a release method, or the current state value upon
 715      *        entry to a condition wait.  The value is otherwise
 716      *        uninterpreted and can represent anything you like.
 717      * @return {@code true} if this release of shared mode may permit a
 718      *         waiting acquire (shared or exclusive) to succeed; and
 719      *         {@code false} otherwise
 720      * @throws IllegalMonitorStateException if releasing would place this
 721      *         synchronizer in an illegal state. This exception must be
 722      *         thrown in a consistent fashion for synchronization to work
 723      *         correctly.
 724      * @throws UnsupportedOperationException if shared mode is not supported
 725      */
 726     protected boolean tryReleaseShared(long arg) {
 727         throw new UnsupportedOperationException();
 728     }
 729 
 730     /**
 731      * Returns {@code true} if synchronization is held exclusively with
 732      * respect to the current (calling) thread.  This method is invoked
 733      * upon each call to a {@link ConditionObject} method.
 734      *
 735      * <p>The default implementation throws {@link
 736      * UnsupportedOperationException}. This method is invoked
 737      * internally only within {@link ConditionObject} methods, so need
 738      * not be defined if conditions are not used.
 739      *
 740      * @return {@code true} if synchronization is held exclusively;
 741      *         {@code false} otherwise
 742      * @throws UnsupportedOperationException if conditions are not supported
 743      */
 744     protected boolean isHeldExclusively() {
 745         throw new UnsupportedOperationException();
 746     }
 747 
 748     /**
 749      * Acquires in exclusive mode, ignoring interrupts.  Implemented
 750      * by invoking at least once {@link #tryAcquire},
 751      * returning on success.  Otherwise the thread is queued, possibly
 752      * repeatedly blocking and unblocking, invoking {@link
 753      * #tryAcquire} until success.  This method can be used
 754      * to implement method {@link Lock#lock}.
 755      *
 756      * @param arg the acquire argument.  This value is conveyed to
 757      *        {@link #tryAcquire} but is otherwise uninterpreted and
 758      *        can represent anything you like.
 759      */
 760     public final void acquire(long arg) {
 761         if (!tryAcquire(arg) &&
 762             acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
 763             selfInterrupt();
 764     }
 765 
 766     /**
 767      * Acquires in exclusive mode, aborting if interrupted.
 768      * Implemented by first checking interrupt status, then invoking
 769      * at least once {@link #tryAcquire}, returning on
 770      * success.  Otherwise the thread is queued, possibly repeatedly
 771      * blocking and unblocking, invoking {@link #tryAcquire}
 772      * until success or the thread is interrupted.  This method can be
 773      * used to implement method {@link Lock#lockInterruptibly}.
 774      *
 775      * @param arg the acquire argument.  This value is conveyed to
 776      *        {@link #tryAcquire} but is otherwise uninterpreted and
 777      *        can represent anything you like.
 778      * @throws InterruptedException if the current thread is interrupted
 779      */
 780     public final void acquireInterruptibly(long arg)
 781             throws InterruptedException {
 782         if (Thread.interrupted())
 783             throw new InterruptedException();
 784         if (!tryAcquire(arg))
 785             doAcquireInterruptibly(arg);
 786     }
 787 
 788     /**
 789      * Attempts to acquire in exclusive mode, aborting if interrupted,
 790      * and failing if the given timeout elapses.  Implemented by first
 791      * checking interrupt status, then invoking at least once {@link
 792      * #tryAcquire}, returning on success.  Otherwise, the thread is
 793      * queued, possibly repeatedly blocking and unblocking, invoking
 794      * {@link #tryAcquire} until success or the thread is interrupted
 795      * or the timeout elapses.  This method can be used to implement
 796      * method {@link Lock#tryLock(long, TimeUnit)}.
 797      *
 798      * @param arg the acquire argument.  This value is conveyed to
 799      *        {@link #tryAcquire} but is otherwise uninterpreted and
 800      *        can represent anything you like.
 801      * @param nanosTimeout the maximum number of nanoseconds to wait
 802      * @return {@code true} if acquired; {@code false} if timed out
 803      * @throws InterruptedException if the current thread is interrupted
 804      */
 805     public final boolean tryAcquireNanos(long arg, long nanosTimeout)
 806             throws InterruptedException {
 807         if (Thread.interrupted())
 808             throw new InterruptedException();
 809         return tryAcquire(arg) ||
 810             doAcquireNanos(arg, nanosTimeout);
 811     }
 812 
 813     /**
 814      * Releases in exclusive mode.  Implemented by unblocking one or
 815      * more threads if {@link #tryRelease} returns true.
 816      * This method can be used to implement method {@link Lock#unlock}.
 817      *
 818      * @param arg the release argument.  This value is conveyed to
 819      *        {@link #tryRelease} but is otherwise uninterpreted and
 820      *        can represent anything you like.
 821      * @return the value returned from {@link #tryRelease}
 822      */
 823     public final boolean release(long arg) {
 824         if (tryRelease(arg)) {
 825             Node h = head;
 826             if (h != null && h.waitStatus != 0)
 827                 unparkSuccessor(h);
 828             return true;
 829         }
 830         return false;
 831     }
 832 
 833     /**
 834      * Acquires in shared mode, ignoring interrupts.  Implemented by
 835      * first invoking at least once {@link #tryAcquireShared},
 836      * returning on success.  Otherwise the thread is queued, possibly
 837      * repeatedly blocking and unblocking, invoking {@link
 838      * #tryAcquireShared} until success.
 839      *
 840      * @param arg the acquire argument.  This value is conveyed to
 841      *        {@link #tryAcquireShared} but is otherwise uninterpreted
 842      *        and can represent anything you like.
 843      */
 844     public final void acquireShared(long arg) {
 845         if (tryAcquireShared(arg) < 0)
 846             doAcquireShared(arg);
 847     }
 848 
 849     /**
 850      * Acquires in shared mode, aborting if interrupted.  Implemented
 851      * by first checking interrupt status, then invoking at least once
 852      * {@link #tryAcquireShared}, returning on success.  Otherwise the
 853      * thread is queued, possibly repeatedly blocking and unblocking,
 854      * invoking {@link #tryAcquireShared} until success or the thread
 855      * is interrupted.
 856      * @param arg the acquire argument.
 857      * This value is conveyed to {@link #tryAcquireShared} but is
 858      * otherwise uninterpreted and can represent anything
 859      * you like.
 860      * @throws InterruptedException if the current thread is interrupted
 861      */
 862     public final void acquireSharedInterruptibly(long arg)
 863             throws InterruptedException {
 864         if (Thread.interrupted())
 865             throw new InterruptedException();
 866         if (tryAcquireShared(arg) < 0)
 867             doAcquireSharedInterruptibly(arg);
 868     }
 869 
 870     /**
 871      * Attempts to acquire in shared mode, aborting if interrupted, and
 872      * failing if the given timeout elapses.  Implemented by first
 873      * checking interrupt status, then invoking at least once {@link
 874      * #tryAcquireShared}, returning on success.  Otherwise, the
 875      * thread is queued, possibly repeatedly blocking and unblocking,
 876      * invoking {@link #tryAcquireShared} until success or the thread
 877      * is interrupted or the timeout elapses.
 878      *
 879      * @param arg the acquire argument.  This value is conveyed to
 880      *        {@link #tryAcquireShared} but is otherwise uninterpreted
 881      *        and can represent anything you like.
 882      * @param nanosTimeout the maximum number of nanoseconds to wait
 883      * @return {@code true} if acquired; {@code false} if timed out
 884      * @throws InterruptedException if the current thread is interrupted
 885      */
 886     public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout)
 887             throws InterruptedException {
 888         if (Thread.interrupted())
 889             throw new InterruptedException();
 890         return tryAcquireShared(arg) >= 0 ||
 891             doAcquireSharedNanos(arg, nanosTimeout);
 892     }
 893 
 894     /**
 895      * Releases in shared mode.  Implemented by unblocking one or more
 896      * threads if {@link #tryReleaseShared} returns true.
 897      *
 898      * @param arg the release argument.  This value is conveyed to
 899      *        {@link #tryReleaseShared} but is otherwise uninterpreted
 900      *        and can represent anything you like.
 901      * @return the value returned from {@link #tryReleaseShared}
 902      */
 903     public final boolean releaseShared(long arg) {
 904         if (tryReleaseShared(arg)) {
 905             doReleaseShared();
 906             return true;
 907         }
 908         return false;
 909     }
 910 
 911     // Queue inspection methods
 912 
 913     /**
 914      * Queries whether any threads are waiting to acquire. Note that
 915      * because cancellations due to interrupts and timeouts may occur
 916      * at any time, a {@code true} return does not guarantee that any
 917      * other thread will ever acquire.
 918      *
 919      * @return {@code true} if there may be other threads waiting to acquire
 920      */
 921     public final boolean hasQueuedThreads() {
 922         for (Node p = tail, h = head; p != h && p != null; p = p.prev)
 923             if (p.waitStatus <= 0)
 924                 return true;
 925         return false;
 926     }
 927 
 928     /**
 929      * Queries whether any threads have ever contended to acquire this
 930      * synchronizer; that is, if an acquire method has ever blocked.
 931      *
 932      * <p>In this implementation, this operation returns in
 933      * constant time.
 934      *
 935      * @return {@code true} if there has ever been contention
 936      */
 937     public final boolean hasContended() {
 938         return head != null;
 939     }
 940 
 941     /**
 942      * Returns the first (longest-waiting) thread in the queue, or
 943      * {@code null} if no threads are currently queued.
 944      *
 945      * <p>In this implementation, this operation normally returns in
 946      * constant time, but may iterate upon contention if other threads are
 947      * concurrently modifying the queue.
 948      *
 949      * @return the first (longest-waiting) thread in the queue, or
 950      *         {@code null} if no threads are currently queued
 951      */
 952     public final Thread getFirstQueuedThread() {
 953         // handle only fast path, else relay
 954         return (head == tail) ? null : (Thread) fullGetFirstQueuedStrand();
 955     }
 956 
 957     /**
 958      * Version of getFirstQueuedStrand called when fastpath fails.
 959      */
 960     private Object fullGetFirstQueuedStrand() {
 961         /*
 962          * The first node is normally head.next. Try to get its
 963          * thread field, ensuring consistent reads: If thread
 964          * field is nulled out or s.prev is no longer head, then
 965          * some other thread(s) concurrently performed setHead in
 966          * between some of our reads. We try this twice before
 967          * resorting to traversal.
 968          */
 969         Node h, s;
 970         Object st;
 971         if (((h = head) != null && (s = h.next) != null &&
 972              s.prev == head && (st = s.strand) != null) ||
 973             ((h = head) != null && (s = h.next) != null &&
 974              s.prev == head && (st = s.strand) != null))
 975             return st;
 976 
 977         /*
 978          * Head's next field might not have been set yet, or may have
 979          * been unset after setHead. So we must check to see if tail
 980          * is actually first node. If not, we continue on, safely
 981          * traversing from tail back to head to find first,
 982          * guaranteeing termination.
 983          */
 984 
 985         Object firstStrand = null;
 986         for (Node p = tail; p != null && p != head; p = p.prev) {
 987             Object strand = p.strand;
 988             if (strand != null)
 989                 firstStrand = strand;
 990         }
 991         return firstStrand;
 992     }
 993 
 994     /**
 995      * Returns true if the given thread is currently queued.
 996      *
 997      * <p>This implementation traverses the queue to determine
 998      * presence of the given thread.
 999      *
1000      * @param thread the thread
1001      * @return {@code true} if the given thread is on the queue
1002      * @throws NullPointerException if the thread is null
1003      */
1004     public final boolean isQueued(Thread thread) {
1005         if (thread == null)
1006             throw new NullPointerException();
1007         for (Node p = tail; p != null; p = p.prev)
1008             if (p.strand == thread)
1009                 return true;
1010         return false;
1011     }
1012 
1013     /**
1014      * Returns {@code true} if the apparent first queued thread, if one
1015      * exists, is waiting in exclusive mode.  If this method returns
1016      * {@code true}, and the current thread is attempting to acquire in
1017      * shared mode (that is, this method is invoked from {@link
1018      * #tryAcquireShared}) then it is guaranteed that the current thread
1019      * is not the first queued thread.  Used only as a heuristic in
1020      * ReentrantReadWriteLock.
1021      */
1022     final boolean apparentlyFirstQueuedIsExclusive() {
1023         Node h, s;
1024         return (h = head) != null &&
1025             (s = h.next)  != null &&
1026             !s.isShared()         &&
1027             s.strand != null;
1028     }
1029 
1030     /**
1031      * Queries whether any threads have been waiting to acquire longer
1032      * than the current thread.
1033      *
1034      * <p>An invocation of this method is equivalent to (but may be
1035      * more efficient than):
1036      * <pre> {@code
1037      * getFirstQueuedThread() != Thread.currentThread()
1038      *   && hasQueuedThreads()}</pre>
1039      *
1040      * <p>Note that because cancellations due to interrupts and
1041      * timeouts may occur at any time, a {@code true} return does not
1042      * guarantee that some other thread will acquire before the current
1043      * thread.  Likewise, it is possible for another thread to win a
1044      * race to enqueue after this method has returned {@code false},
1045      * due to the queue being empty.
1046      *
1047      * <p>This method is designed to be used by a fair synchronizer to
1048      * avoid <a href="AbstractQueuedSynchronizer.html#barging">barging</a>.
1049      * Such a synchronizer's {@link #tryAcquire} method should return
1050      * {@code false}, and its {@link #tryAcquireShared} method should
1051      * return a negative value, if this method returns {@code true}
1052      * (unless this is a reentrant acquire).  For example, the {@code
1053      * tryAcquire} method for a fair, reentrant, exclusive mode
1054      * synchronizer might look like this:
1055      *
1056      * <pre> {@code
1057      * protected boolean tryAcquire(int arg) {
1058      *   if (isHeldExclusively()) {
1059      *     // A reentrant acquire; increment hold count
1060      *     return true;
1061      *   } else if (hasQueuedPredecessors()) {
1062      *     return false;
1063      *   } else {
1064      *     // try to acquire normally
1065      *   }
1066      * }}</pre>
1067      *
1068      * @return {@code true} if there is a queued thread preceding the
1069      *         current thread, and {@code false} if the current thread
1070      *         is at the head of the queue or the queue is empty
1071      * @since 1.7
1072      */
1073     public final boolean hasQueuedPredecessors() {
1074         Node h, s;
1075         if ((h = head) != null) {
1076             if ((s = h.next) == null || s.waitStatus > 0) {
1077                 s = null; // traverse in case of concurrent cancellation
1078                 for (Node p = tail; p != h && p != null; p = p.prev) {
1079                     if (p.waitStatus <= 0)
1080                         s = p;
1081                 }
1082             }
1083             if (s != null && s.strand != Strands.currentStrand())
1084                 return true;
1085         }
1086         return false;
1087     }
1088 
1089     // Instrumentation and monitoring methods
1090 
1091     /**
1092      * Returns an estimate of the number of threads waiting to
1093      * acquire.  The value is only an estimate because the number of
1094      * threads may change dynamically while this method traverses
1095      * internal data structures.  This method is designed for use in
1096      * monitoring system state, not for synchronization control.
1097      *
1098      * @return the estimated number of threads waiting to acquire
1099      */
1100     public final int getQueueLength() {
1101         int n = 0;
1102         for (Node p = tail; p != null; p = p.prev) {
1103             if (p.strand != null)
1104                 ++n;
1105         }
1106         return n;
1107     }
1108 
1109     /**
1110      * Returns a collection containing threads that may be waiting to
1111      * acquire.  Because the actual set of threads may change
1112      * dynamically while constructing this result, the returned
1113      * collection is only a best-effort estimate.  The elements of the
1114      * returned collection are in no particular order.  This method is
1115      * designed to facilitate construction of subclasses that provide
1116      * more extensive monitoring facilities.
1117      *
1118      * @return the collection of threads
1119      */
1120     public final Collection<Thread> getQueuedThreads() {
1121         ArrayList<Thread> list = new ArrayList<>();
1122         for (Node p = tail; p != null; p = p.prev) {
1123             Object s = p.strand;
1124             if (s instanceof Thread)
1125                 list.add((Thread)s);
1126         }
1127         return list;
1128     }
1129 
1130     /**
1131      * Returns a collection containing threads that may be waiting to
1132      * acquire in exclusive mode. This has the same properties
1133      * as {@link #getQueuedThreads} except that it only returns
1134      * those threads waiting due to an exclusive acquire.
1135      *
1136      * @return the collection of threads
1137      */
1138     public final Collection<Thread> getExclusiveQueuedThreads() {
1139         ArrayList<Thread> list = new ArrayList<>();
1140         for (Node p = tail; p != null; p = p.prev) {
1141             if (!p.isShared()) {
1142                 Object s = p.strand;
1143                 if (s instanceof Thread)
1144                     list.add((Thread)s);
1145             }
1146         }
1147         return list;
1148     }
1149 
1150     /**
1151      * Returns a collection containing threads that may be waiting to
1152      * acquire in shared mode. This has the same properties
1153      * as {@link #getQueuedThreads} except that it only returns
1154      * those threads waiting due to a shared acquire.
1155      *
1156      * @return the collection of threads
1157      */
1158     public final Collection<Thread> getSharedQueuedThreads() {
1159         ArrayList<Thread> list = new ArrayList<>();
1160         for (Node p = tail; p != null; p = p.prev) {
1161             if (p.isShared()) {
1162                 Object s = p.strand;
1163                 if (s instanceof Thread)
1164                     list.add((Thread)s);
1165             }
1166         }
1167         return list;
1168     }
1169 
1170     /**
1171      * Returns a string identifying this synchronizer, as well as its state.
1172      * The state, in brackets, includes the String {@code "State ="}
1173      * followed by the current value of {@link #getState}, and either
1174      * {@code "nonempty"} or {@code "empty"} depending on whether the
1175      * queue is empty.
1176      *
1177      * @return a string identifying this synchronizer, as well as its state
1178      */
1179     public String toString() {
1180         return super.toString()
1181             + "[State = " + getState() + ", "
1182             + (hasQueuedThreads() ? "non" : "") + "empty queue]";
1183     }
1184 
1185 
1186     // Internal support methods for Conditions
1187 
1188     /**
1189      * Returns true if a node, always one that was initially placed on
1190      * a condition queue, is now waiting to reacquire on sync queue.
1191      * @param node the node
1192      * @return true if is reacquiring
1193      */
1194     final boolean isOnSyncQueue(Node node) {
1195         if (node.waitStatus == Node.CONDITION || node.prev == null)
1196             return false;
1197         if (node.next != null) // If has successor, it must be on queue
1198             return true;
1199         /*
1200          * node.prev can be non-null, but not yet on queue because
1201          * the CAS to place it on queue can fail. So we have to
1202          * traverse from tail to make sure it actually made it.  It
1203          * will always be near the tail in calls to this method, and
1204          * unless the CAS failed (which is unlikely), it will be
1205          * there, so we hardly ever traverse much.
1206          */
1207         return findNodeFromTail(node);
1208     }
1209 
1210     /**
1211      * Returns true if node is on sync queue by searching backwards from tail.
1212      * Called only when needed by isOnSyncQueue.
1213      * @return true if present
1214      */
1215     private boolean findNodeFromTail(Node node) {
1216         // We check for node first, since it's likely to be at or near tail.
1217         // tail is known to be non-null, so we could re-order to "save"
1218         // one null check, but we leave it this way to help the VM.
1219         for (Node p = tail;;) {
1220             if (p == node)
1221                 return true;
1222             if (p == null)
1223                 return false;
1224             p = p.prev;
1225         }
1226     }
1227 
1228     /**
1229      * Transfers a node from a condition queue onto sync queue.
1230      * Returns true if successful.
1231      * @param node the node
1232      * @return true if successfully transferred (else the node was
1233      * cancelled before signal)
1234      */
1235     final boolean transferForSignal(Node node) {
1236         /*
1237          * If cannot change waitStatus, the node has been cancelled.
1238          */
1239         if (!node.compareAndSetWaitStatus(Node.CONDITION, 0))
1240             return false;
1241 
1242         /*
1243          * Splice onto queue and try to set waitStatus of predecessor to
1244          * indicate that thread is (probably) waiting. If cancelled or
1245          * attempt to set waitStatus fails, wake up to resync (in which
1246          * case the waitStatus can be transiently and harmlessly wrong).
1247          */
1248         Node p = enq(node);
1249         int ws = p.waitStatus;
1250         if (ws > 0 || !p.compareAndSetWaitStatus(ws, Node.SIGNAL))
1251             LockSupport.unpark(node.strand);
1252         return true;
1253     }
1254 
1255     /**
1256      * Transfers node, if necessary, to sync queue after a cancelled wait.
1257      * Returns true if thread was cancelled before being signalled.
1258      *
1259      * @param node the node
1260      * @return true if cancelled before the node was signalled
1261      */
1262     final boolean transferAfterCancelledWait(Node node) {
1263         if (node.compareAndSetWaitStatus(Node.CONDITION, 0)) {
1264             enq(node);
1265             return true;
1266         }
1267         /*
1268          * If we lost out to a signal(), then we can't proceed
1269          * until it finishes its enq().  Cancelling during an
1270          * incomplete transfer is both rare and transient, so just
1271          * spin.
1272          */
1273         while (!isOnSyncQueue(node))
1274             Thread.yield();
1275         return false;
1276     }
1277 
1278     /**
1279      * Invokes release with current state value; returns saved state.
1280      * Cancels node and throws exception on failure.
1281      * @param node the condition node for this wait
1282      * @return previous sync state
1283      */
1284     final long fullyRelease(Node node) {
1285         try {
1286             long savedState = getState();
1287             if (release(savedState))
1288                 return savedState;
1289             throw new IllegalMonitorStateException();
1290         } catch (Throwable t) {
1291             node.waitStatus = Node.CANCELLED;
1292             throw t;
1293         }
1294     }
1295 
1296     // Instrumentation methods for conditions
1297 
1298     /**
1299      * Queries whether the given ConditionObject
1300      * uses this synchronizer as its lock.
1301      *
1302      * @param condition the condition
1303      * @return {@code true} if owned
1304      * @throws NullPointerException if the condition is null
1305      */
1306     public final boolean owns(ConditionObject condition) {
1307         return condition.isOwnedBy(this);
1308     }
1309 
1310     /**
1311      * Queries whether any threads are waiting on the given condition
1312      * associated with this synchronizer. Note that because timeouts
1313      * and interrupts may occur at any time, a {@code true} return
1314      * does not guarantee that a future {@code signal} will awaken
1315      * any threads.  This method is designed primarily for use in
1316      * monitoring of the system state.
1317      *
1318      * @param condition the condition
1319      * @return {@code true} if there are any waiting threads
1320      * @throws IllegalMonitorStateException if exclusive synchronization
1321      *         is not held
1322      * @throws IllegalArgumentException if the given condition is
1323      *         not associated with this synchronizer
1324      * @throws NullPointerException if the condition is null
1325      */
1326     public final boolean hasWaiters(ConditionObject condition) {
1327         if (!owns(condition))
1328             throw new IllegalArgumentException("Not owner");
1329         return condition.hasWaiters();
1330     }
1331 
1332     /**
1333      * Returns an estimate of the number of threads waiting on the
1334      * given condition associated with this synchronizer. Note that
1335      * because timeouts and interrupts may occur at any time, the
1336      * estimate serves only as an upper bound on the actual number of
1337      * waiters.  This method is designed for use in monitoring system
1338      * state, not for synchronization control.
1339      *
1340      * @param condition the condition
1341      * @return the estimated number of waiting threads
1342      * @throws IllegalMonitorStateException if exclusive synchronization
1343      *         is not held
1344      * @throws IllegalArgumentException if the given condition is
1345      *         not associated with this synchronizer
1346      * @throws NullPointerException if the condition is null
1347      */
1348     public final int getWaitQueueLength(ConditionObject condition) {
1349         if (!owns(condition))
1350             throw new IllegalArgumentException("Not owner");
1351         return condition.getWaitQueueLength();
1352     }
1353 
1354     /**
1355      * Returns a collection containing those threads that may be
1356      * waiting on the given condition associated with this
1357      * synchronizer.  Because the actual set of threads may change
1358      * dynamically while constructing this result, the returned
1359      * collection is only a best-effort estimate. The elements of the
1360      * returned collection are in no particular order.
1361      *
1362      * @param condition the condition
1363      * @return the collection of threads
1364      * @throws IllegalMonitorStateException if exclusive synchronization
1365      *         is not held
1366      * @throws IllegalArgumentException if the given condition is
1367      *         not associated with this synchronizer
1368      * @throws NullPointerException if the condition is null
1369      */
1370     public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
1371         if (!owns(condition))
1372             throw new IllegalArgumentException("Not owner");
1373         return condition.getWaitingThreads();
1374     }
1375 
1376     /**
1377      * Condition implementation for a {@link AbstractQueuedLongSynchronizer}
1378      * serving as the basis of a {@link Lock} implementation.
1379      *
1380      * <p>Method documentation for this class describes mechanics,
1381      * not behavioral specifications from the point of view of Lock
1382      * and Condition users. Exported versions of this class will in
1383      * general need to be accompanied by documentation describing
1384      * condition semantics that rely on those of the associated
1385      * {@code AbstractQueuedLongSynchronizer}.
1386      *
1387      * <p>This class is Serializable, but all fields are transient,
1388      * so deserialized conditions have no waiters.
1389      *
1390      * @since 1.6
1391      */
1392     public class ConditionObject implements Condition, java.io.Serializable {
1393         private static final long serialVersionUID = 1173984872572414699L;
1394         /** First node of condition queue. */
1395         private transient Node firstWaiter;
1396         /** Last node of condition queue. */
1397         private transient Node lastWaiter;
1398 
1399         /**
1400          * Creates a new {@code ConditionObject} instance.
1401          */
1402         public ConditionObject() { }
1403 
1404         // Internal methods
1405 
1406         /**
1407          * Adds a new waiter to wait queue.
1408          * @return its new wait node
1409          */
1410         private Node addConditionWaiter() {
1411             if (!isHeldExclusively())
1412                 throw new IllegalMonitorStateException();
1413             Node t = lastWaiter;
1414             // If lastWaiter is cancelled, clean out.
1415             if (t != null && t.waitStatus != Node.CONDITION) {
1416                 unlinkCancelledWaiters();
1417                 t = lastWaiter;
1418             }
1419 
1420             Node node = new Node(Node.CONDITION);
1421 
1422             if (t == null)
1423                 firstWaiter = node;
1424             else
1425                 t.nextWaiter = node;
1426             lastWaiter = node;
1427             return node;
1428         }
1429 
1430         /**
1431          * Removes and transfers nodes until hit non-cancelled one or
1432          * null. Split out from signal in part to encourage compilers
1433          * to inline the case of no waiters.
1434          * @param first (non-null) the first node on condition queue
1435          */
1436         private void doSignal(Node first) {
1437             do {
1438                 if ( (firstWaiter = first.nextWaiter) == null)
1439                     lastWaiter = null;
1440                 first.nextWaiter = null;
1441             } while (!transferForSignal(first) &&
1442                      (first = firstWaiter) != null);
1443         }
1444 
1445         /**
1446          * Removes and transfers all nodes.
1447          * @param first (non-null) the first node on condition queue
1448          */
1449         private void doSignalAll(Node first) {
1450             lastWaiter = firstWaiter = null;
1451             do {
1452                 Node next = first.nextWaiter;
1453                 first.nextWaiter = null;
1454                 transferForSignal(first);
1455                 first = next;
1456             } while (first != null);
1457         }
1458 
1459         /**
1460          * Unlinks cancelled waiter nodes from condition queue.
1461          * Called only while holding lock. This is called when
1462          * cancellation occurred during condition wait, and upon
1463          * insertion of a new waiter when lastWaiter is seen to have
1464          * been cancelled. This method is needed to avoid garbage
1465          * retention in the absence of signals. So even though it may
1466          * require a full traversal, it comes into play only when
1467          * timeouts or cancellations occur in the absence of
1468          * signals. It traverses all nodes rather than stopping at a
1469          * particular target to unlink all pointers to garbage nodes
1470          * without requiring many re-traversals during cancellation
1471          * storms.
1472          */
1473         private void unlinkCancelledWaiters() {
1474             Node t = firstWaiter;
1475             Node trail = null;
1476             while (t != null) {
1477                 Node next = t.nextWaiter;
1478                 if (t.waitStatus != Node.CONDITION) {
1479                     t.nextWaiter = null;
1480                     if (trail == null)
1481                         firstWaiter = next;
1482                     else
1483                         trail.nextWaiter = next;
1484                     if (next == null)
1485                         lastWaiter = trail;
1486                 }
1487                 else
1488                     trail = t;
1489                 t = next;
1490             }
1491         }
1492 
1493         // public methods
1494 
1495         /**
1496          * Moves the longest-waiting thread, if one exists, from the
1497          * wait queue for this condition to the wait queue for the
1498          * owning lock.
1499          *
1500          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1501          *         returns {@code false}
1502          */
1503         public final void signal() {
1504             if (!isHeldExclusively())
1505                 throw new IllegalMonitorStateException();
1506             Node first = firstWaiter;
1507             if (first != null)
1508                 doSignal(first);
1509         }
1510 
1511         /**
1512          * Moves all threads from the wait queue for this condition to
1513          * the wait queue for the owning lock.
1514          *
1515          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1516          *         returns {@code false}
1517          */
1518         public final void signalAll() {
1519             if (!isHeldExclusively())
1520                 throw new IllegalMonitorStateException();
1521             Node first = firstWaiter;
1522             if (first != null)
1523                 doSignalAll(first);
1524         }
1525 
1526         /**
1527          * Implements uninterruptible condition wait.
1528          * <ol>
1529          * <li>Save lock state returned by {@link #getState}.
1530          * <li>Invoke {@link #release} with saved state as argument,
1531          *     throwing IllegalMonitorStateException if it fails.
1532          * <li>Block until signalled.
1533          * <li>Reacquire by invoking specialized version of
1534          *     {@link #acquire} with saved state as argument.
1535          * </ol>
1536          */
1537         public final void awaitUninterruptibly() {
1538             Node node = addConditionWaiter();
1539             long savedState = fullyRelease(node);
1540             boolean interrupted = false;
1541             while (!isOnSyncQueue(node)) {
1542                 LockSupport.park(this);
1543                 if (Thread.interrupted())
1544                     interrupted = true;
1545             }
1546             if (acquireQueued(node, savedState) || interrupted)
1547                 selfInterrupt();
1548         }
1549 
1550         /*
1551          * For interruptible waits, we need to track whether to throw
1552          * InterruptedException, if interrupted while blocked on
1553          * condition, versus reinterrupt current thread, if
1554          * interrupted while blocked waiting to re-acquire.
1555          */
1556 
1557         /** Mode meaning to reinterrupt on exit from wait */
1558         private static final int REINTERRUPT =  1;
1559         /** Mode meaning to throw InterruptedException on exit from wait */
1560         private static final int THROW_IE    = -1;
1561 
1562         /**
1563          * Checks for interrupt, returning THROW_IE if interrupted
1564          * before signalled, REINTERRUPT if after signalled, or
1565          * 0 if not interrupted.
1566          */
1567         private int checkInterruptWhileWaiting(Node node) {
1568             return Thread.interrupted() ?
1569                 (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
1570                 0;
1571         }
1572 
1573         /**
1574          * Throws InterruptedException, reinterrupts current thread, or
1575          * does nothing, depending on mode.
1576          */
1577         private void reportInterruptAfterWait(int interruptMode)
1578             throws InterruptedException {
1579             if (interruptMode == THROW_IE)
1580                 throw new InterruptedException();
1581             else if (interruptMode == REINTERRUPT)
1582                 selfInterrupt();
1583         }
1584 
1585         /**
1586          * Implements interruptible condition wait.
1587          * <ol>
1588          * <li>If current thread is interrupted, throw InterruptedException.
1589          * <li>Save lock state returned by {@link #getState}.
1590          * <li>Invoke {@link #release} with saved state as argument,
1591          *     throwing IllegalMonitorStateException if it fails.
1592          * <li>Block until signalled or interrupted.
1593          * <li>Reacquire by invoking specialized version of
1594          *     {@link #acquire} with saved state as argument.
1595          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1596          * </ol>
1597          */
1598         public final void await() throws InterruptedException {
1599             if (Thread.interrupted())
1600                 throw new InterruptedException();
1601             Node node = addConditionWaiter();
1602             long savedState = fullyRelease(node);
1603             int interruptMode = 0;
1604             while (!isOnSyncQueue(node)) {
1605                 LockSupport.park(this);
1606                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1607                     break;
1608             }
1609             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1610                 interruptMode = REINTERRUPT;
1611             if (node.nextWaiter != null) // clean up if cancelled
1612                 unlinkCancelledWaiters();
1613             if (interruptMode != 0)
1614                 reportInterruptAfterWait(interruptMode);
1615         }
1616 
1617         /**
1618          * Implements timed condition wait.
1619          * <ol>
1620          * <li>If current thread is interrupted, throw InterruptedException.
1621          * <li>Save lock state returned by {@link #getState}.
1622          * <li>Invoke {@link #release} with saved state as argument,
1623          *     throwing IllegalMonitorStateException if it fails.
1624          * <li>Block until signalled, interrupted, or timed out.
1625          * <li>Reacquire by invoking specialized version of
1626          *     {@link #acquire} with saved state as argument.
1627          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1628          * </ol>
1629          */
1630         public final long awaitNanos(long nanosTimeout)
1631                 throws InterruptedException {
1632             if (Thread.interrupted())
1633                 throw new InterruptedException();
1634             // We don't check for nanosTimeout <= 0L here, to allow
1635             // awaitNanos(0) as a way to "yield the lock".
1636             final long deadline = System.nanoTime() + nanosTimeout;
1637             long initialNanos = nanosTimeout;
1638             Node node = addConditionWaiter();
1639             long savedState = fullyRelease(node);
1640             int interruptMode = 0;
1641             while (!isOnSyncQueue(node)) {
1642                 if (nanosTimeout <= 0L) {
1643                     transferAfterCancelledWait(node);
1644                     break;
1645                 }
1646                 if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
1647                     LockSupport.parkNanos(this, nanosTimeout);
1648                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1649                     break;
1650                 nanosTimeout = deadline - System.nanoTime();
1651             }
1652             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1653                 interruptMode = REINTERRUPT;
1654             if (node.nextWaiter != null)
1655                 unlinkCancelledWaiters();
1656             if (interruptMode != 0)
1657                 reportInterruptAfterWait(interruptMode);
1658             long remaining = deadline - System.nanoTime(); // avoid overflow
1659             return (remaining <= initialNanos) ? remaining : Long.MIN_VALUE;
1660         }
1661 
1662         /**
1663          * Implements absolute timed condition wait.
1664          * <ol>
1665          * <li>If current thread is interrupted, throw InterruptedException.
1666          * <li>Save lock state returned by {@link #getState}.
1667          * <li>Invoke {@link #release} with saved state as argument,
1668          *     throwing IllegalMonitorStateException if it fails.
1669          * <li>Block until signalled, interrupted, or timed out.
1670          * <li>Reacquire by invoking specialized version of
1671          *     {@link #acquire} with saved state as argument.
1672          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1673          * <li>If timed out while blocked in step 4, return false, else true.
1674          * </ol>
1675          */
1676         public final boolean awaitUntil(Date deadline)
1677                 throws InterruptedException {
1678             long abstime = deadline.getTime();
1679             if (Thread.interrupted())
1680                 throw new InterruptedException();
1681             Node node = addConditionWaiter();
1682             long savedState = fullyRelease(node);
1683             boolean timedout = false;
1684             int interruptMode = 0;
1685             while (!isOnSyncQueue(node)) {
1686                 if (System.currentTimeMillis() >= abstime) {
1687                     timedout = transferAfterCancelledWait(node);
1688                     break;
1689                 }
1690                 LockSupport.parkUntil(this, abstime);
1691                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1692                     break;
1693             }
1694             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1695                 interruptMode = REINTERRUPT;
1696             if (node.nextWaiter != null)
1697                 unlinkCancelledWaiters();
1698             if (interruptMode != 0)
1699                 reportInterruptAfterWait(interruptMode);
1700             return !timedout;
1701         }
1702 
1703         /**
1704          * Implements timed condition wait.
1705          * <ol>
1706          * <li>If current thread is interrupted, throw InterruptedException.
1707          * <li>Save lock state returned by {@link #getState}.
1708          * <li>Invoke {@link #release} with saved state as argument,
1709          *     throwing IllegalMonitorStateException if it fails.
1710          * <li>Block until signalled, interrupted, or timed out.
1711          * <li>Reacquire by invoking specialized version of
1712          *     {@link #acquire} with saved state as argument.
1713          * <li>If interrupted while blocked in step 4, throw InterruptedException.
1714          * <li>If timed out while blocked in step 4, return false, else true.
1715          * </ol>
1716          */
1717         public final boolean await(long time, TimeUnit unit)
1718                 throws InterruptedException {
1719             long nanosTimeout = unit.toNanos(time);
1720             if (Thread.interrupted())
1721                 throw new InterruptedException();
1722             // We don't check for nanosTimeout <= 0L here, to allow
1723             // await(0, unit) as a way to "yield the lock".
1724             final long deadline = System.nanoTime() + nanosTimeout;
1725             Node node = addConditionWaiter();
1726             long savedState = fullyRelease(node);
1727             boolean timedout = false;
1728             int interruptMode = 0;
1729             while (!isOnSyncQueue(node)) {
1730                 if (nanosTimeout <= 0L) {
1731                     timedout = transferAfterCancelledWait(node);
1732                     break;
1733                 }
1734                 if (nanosTimeout > SPIN_FOR_TIMEOUT_THRESHOLD)
1735                     LockSupport.parkNanos(this, nanosTimeout);
1736                 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
1737                     break;
1738                 nanosTimeout = deadline - System.nanoTime();
1739             }
1740             if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
1741                 interruptMode = REINTERRUPT;
1742             if (node.nextWaiter != null)
1743                 unlinkCancelledWaiters();
1744             if (interruptMode != 0)
1745                 reportInterruptAfterWait(interruptMode);
1746             return !timedout;
1747         }
1748 
1749         //  support for instrumentation
1750 
1751         /**
1752          * Returns true if this condition was created by the given
1753          * synchronization object.
1754          *
1755          * @return {@code true} if owned
1756          */
1757         final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) {
1758             return sync == AbstractQueuedLongSynchronizer.this;
1759         }
1760 
1761         /**
1762          * Queries whether any threads are waiting on this condition.
1763          * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters(ConditionObject)}.
1764          *
1765          * @return {@code true} if there are any waiting threads
1766          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1767          *         returns {@code false}
1768          */
1769         protected final boolean hasWaiters() {
1770             if (!isHeldExclusively())
1771                 throw new IllegalMonitorStateException();
1772             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1773                 if (w.waitStatus == Node.CONDITION)
1774                     return true;
1775             }
1776             return false;
1777         }
1778 
1779         /**
1780          * Returns an estimate of the number of threads waiting on
1781          * this condition.
1782          * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength(ConditionObject)}.
1783          *
1784          * @return the estimated number of waiting threads
1785          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1786          *         returns {@code false}
1787          */
1788         protected final int getWaitQueueLength() {
1789             if (!isHeldExclusively())
1790                 throw new IllegalMonitorStateException();
1791             int n = 0;
1792             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1793                 if (w.waitStatus == Node.CONDITION)
1794                     ++n;
1795             }
1796             return n;
1797         }
1798 
1799         /**
1800          * Returns a collection containing those threads that may be
1801          * waiting on this Condition.
1802          * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads(ConditionObject)}.
1803          *
1804          * @return the collection of threads
1805          * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
1806          *         returns {@code false}
1807          */
1808         protected final Collection<Thread> getWaitingThreads() {
1809             if (!isHeldExclusively())
1810                 throw new IllegalMonitorStateException();
1811             ArrayList<Thread> list = new ArrayList<>();
1812             for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
1813                 if (w.waitStatus == Node.CONDITION) {
1814                     Object s = w.strand;
1815                     if (s instanceof Thread)
1816                         list.add((Thread)s);
1817                 }
1818             }
1819             return list;
1820         }
1821     }
1822 
1823     // VarHandle mechanics
1824     private static final VarHandle STATE;
1825     private static final VarHandle HEAD;
1826     private static final VarHandle TAIL;
1827 
1828     static {
1829         try {
1830             MethodHandles.Lookup l = MethodHandles.lookup();
1831             STATE = l.findVarHandle(AbstractQueuedLongSynchronizer.class, "state", long.class);
1832             HEAD = l.findVarHandle(AbstractQueuedLongSynchronizer.class, "head", Node.class);
1833             TAIL = l.findVarHandle(AbstractQueuedLongSynchronizer.class, "tail", Node.class);
1834         } catch (ReflectiveOperationException e) {
1835             throw new ExceptionInInitializerError(e);
1836         }
1837 
1838         // Reduce the risk of rare disastrous classloading in first call to
1839         // LockSupport.park: https://bugs.openjdk.java.net/browse/JDK-8074773
1840         Class<?> ensureLoaded = LockSupport.class;
1841     }
1842 
1843     /**
1844      * Initializes head and tail fields on first contention.
1845      */
1846     private final void initializeSyncQueue() {
1847         Node h;
1848         if (HEAD.compareAndSet(this, null, (h = new Node())))
1849             tail = h;
1850     }
1851 
1852     /**
1853      * CASes tail field.
1854      */
1855     private final boolean compareAndSetTail(Node expect, Node update) {
1856         return TAIL.compareAndSet(this, expect, update);
1857     }
1858 }