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