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