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/licenses/publicdomain 34 */ 35 36 package java.util.concurrent.locks; 37 import java.util.*; 38 import java.util.concurrent.*; 39 import java.util.concurrent.atomic.*; 40 import 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 */ 59 public 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) throws InterruptedException { 994 if (Thread.interrupted()) 995 throw new InterruptedException(); 996 if (!tryAcquire(arg)) 997 doAcquireInterruptibly(arg); 998 } 999 1000 /** 1001 * Attempts to acquire in exclusive mode, aborting if interrupted, 1002 * and failing if the given timeout elapses. Implemented by first 1003 * checking interrupt status, then invoking at least once {@link 1004 * #tryAcquire}, returning on success. Otherwise, the thread is 1005 * queued, possibly repeatedly blocking and unblocking, invoking 1006 * {@link #tryAcquire} until success or the thread is interrupted 1007 * or the timeout elapses. This method can be used to implement 1008 * method {@link Lock#tryLock(long, TimeUnit)}. 1009 * 1010 * @param arg the acquire argument. This value is conveyed to 1011 * {@link #tryAcquire} but is otherwise uninterpreted and 1012 * can represent anything you like. 1013 * @param nanosTimeout the maximum number of nanoseconds to wait 1014 * @return {@code true} if acquired; {@code false} if timed out 1015 * @throws InterruptedException if the current thread is interrupted 1016 */ 1017 public final boolean tryAcquireNanos(long arg, long nanosTimeout) throws InterruptedException { 1018 if (Thread.interrupted()) 1019 throw new InterruptedException(); 1020 return tryAcquire(arg) || 1021 doAcquireNanos(arg, nanosTimeout); 1022 } 1023 1024 /** 1025 * Releases in exclusive mode. Implemented by unblocking one or 1026 * more threads if {@link #tryRelease} returns true. 1027 * This method can be used to implement method {@link Lock#unlock}. 1028 * 1029 * @param arg the release argument. This value is conveyed to 1030 * {@link #tryRelease} but is otherwise uninterpreted and 1031 * can represent anything you like. 1032 * @return the value returned from {@link #tryRelease} 1033 */ 1034 public final boolean release(long arg) { 1035 if (tryRelease(arg)) { 1036 Node h = head; 1037 if (h != null && h.waitStatus != 0) 1038 unparkSuccessor(h); 1039 return true; 1040 } 1041 return false; 1042 } 1043 1044 /** 1045 * Acquires in shared mode, ignoring interrupts. Implemented by 1046 * first invoking at least once {@link #tryAcquireShared}, 1047 * returning on success. Otherwise the thread is queued, possibly 1048 * repeatedly blocking and unblocking, invoking {@link 1049 * #tryAcquireShared} until success. 1050 * 1051 * @param arg the acquire argument. This value is conveyed to 1052 * {@link #tryAcquireShared} but is otherwise uninterpreted 1053 * and can represent anything you like. 1054 */ 1055 public final void acquireShared(long arg) { 1056 if (tryAcquireShared(arg) < 0) 1057 doAcquireShared(arg); 1058 } 1059 1060 /** 1061 * Acquires in shared mode, aborting if interrupted. Implemented 1062 * by first checking interrupt status, then invoking at least once 1063 * {@link #tryAcquireShared}, returning on success. Otherwise the 1064 * thread is queued, possibly repeatedly blocking and unblocking, 1065 * invoking {@link #tryAcquireShared} until success or the thread 1066 * is interrupted. 1067 * @param arg the acquire argument 1068 * This value is conveyed to {@link #tryAcquireShared} but is 1069 * otherwise uninterpreted and can represent anything 1070 * you like. 1071 * @throws InterruptedException if the current thread is interrupted 1072 */ 1073 public final void acquireSharedInterruptibly(long arg) throws InterruptedException { 1074 if (Thread.interrupted()) 1075 throw new InterruptedException(); 1076 if (tryAcquireShared(arg) < 0) 1077 doAcquireSharedInterruptibly(arg); 1078 } 1079 1080 /** 1081 * Attempts to acquire in shared mode, aborting if interrupted, and 1082 * failing if the given timeout elapses. Implemented by first 1083 * checking interrupt status, then invoking at least once {@link 1084 * #tryAcquireShared}, returning on success. Otherwise, the 1085 * thread is queued, possibly repeatedly blocking and unblocking, 1086 * invoking {@link #tryAcquireShared} until success or the thread 1087 * is interrupted or the timeout elapses. 1088 * 1089 * @param arg the acquire argument. This value is conveyed to 1090 * {@link #tryAcquireShared} but is otherwise uninterpreted 1091 * and can represent anything you like. 1092 * @param nanosTimeout the maximum number of nanoseconds to wait 1093 * @return {@code true} if acquired; {@code false} if timed out 1094 * @throws InterruptedException if the current thread is interrupted 1095 */ 1096 public final boolean tryAcquireSharedNanos(long arg, long nanosTimeout) throws InterruptedException { 1097 if (Thread.interrupted()) 1098 throw new InterruptedException(); 1099 return tryAcquireShared(arg) >= 0 || 1100 doAcquireSharedNanos(arg, nanosTimeout); 1101 } 1102 1103 /** 1104 * Releases in shared mode. Implemented by unblocking one or more 1105 * threads if {@link #tryReleaseShared} returns true. 1106 * 1107 * @param arg the release argument. This value is conveyed to 1108 * {@link #tryReleaseShared} but is otherwise uninterpreted 1109 * and can represent anything you like. 1110 * @return the value returned from {@link #tryReleaseShared} 1111 */ 1112 public final boolean releaseShared(long arg) { 1113 if (tryReleaseShared(arg)) { 1114 doReleaseShared(); 1115 return true; 1116 } 1117 return false; 1118 } 1119 1120 // Queue inspection methods 1121 1122 /** 1123 * Queries whether any threads are waiting to acquire. Note that 1124 * because cancellations due to interrupts and timeouts may occur 1125 * at any time, a {@code true} return does not guarantee that any 1126 * other thread will ever acquire. 1127 * 1128 * <p>In this implementation, this operation returns in 1129 * constant time. 1130 * 1131 * @return {@code true} if there may be other threads waiting to acquire 1132 */ 1133 public final boolean hasQueuedThreads() { 1134 return head != tail; 1135 } 1136 1137 /** 1138 * Queries whether any threads have ever contended to acquire this 1139 * synchronizer; that is if an acquire method has ever blocked. 1140 * 1141 * <p>In this implementation, this operation returns in 1142 * constant time. 1143 * 1144 * @return {@code true} if there has ever been contention 1145 */ 1146 public final boolean hasContended() { 1147 return head != null; 1148 } 1149 1150 /** 1151 * Returns the first (longest-waiting) thread in the queue, or 1152 * {@code null} if no threads are currently queued. 1153 * 1154 * <p>In this implementation, this operation normally returns in 1155 * constant time, but may iterate upon contention if other threads are 1156 * concurrently modifying the queue. 1157 * 1158 * @return the first (longest-waiting) thread in the queue, or 1159 * {@code null} if no threads are currently queued 1160 */ 1161 public final Thread getFirstQueuedThread() { 1162 // handle only fast path, else relay 1163 return (head == tail) ? null : fullGetFirstQueuedThread(); 1164 } 1165 1166 /** 1167 * Version of getFirstQueuedThread called when fastpath fails 1168 */ 1169 private Thread fullGetFirstQueuedThread() { 1170 /* 1171 * The first node is normally head.next. Try to get its 1172 * thread field, ensuring consistent reads: If thread 1173 * field is nulled out or s.prev is no longer head, then 1174 * some other thread(s) concurrently performed setHead in 1175 * between some of our reads. We try this twice before 1176 * resorting to traversal. 1177 */ 1178 Node h, s; 1179 Thread st; 1180 if (((h = head) != null && (s = h.next) != null && 1181 s.prev == head && (st = s.thread) != null) || 1182 ((h = head) != null && (s = h.next) != null && 1183 s.prev == head && (st = s.thread) != null)) 1184 return st; 1185 1186 /* 1187 * Head's next field might not have been set yet, or may have 1188 * been unset after setHead. So we must check to see if tail 1189 * is actually first node. If not, we continue on, safely 1190 * traversing from tail back to head to find first, 1191 * guaranteeing termination. 1192 */ 1193 1194 Node t = tail; 1195 Thread firstThread = null; 1196 while (t != null && t != head) { 1197 Thread tt = t.thread; 1198 if (tt != null) 1199 firstThread = tt; 1200 t = t.prev; 1201 } 1202 return firstThread; 1203 } 1204 1205 /** 1206 * Returns true if the given thread is currently queued. 1207 * 1208 * <p>This implementation traverses the queue to determine 1209 * presence of the given thread. 1210 * 1211 * @param thread the thread 1212 * @return {@code true} if the given thread is on the queue 1213 * @throws NullPointerException if the thread is null 1214 */ 1215 public final boolean isQueued(Thread thread) { 1216 if (thread == null) 1217 throw new NullPointerException(); 1218 for (Node p = tail; p != null; p = p.prev) 1219 if (p.thread == thread) 1220 return true; 1221 return false; 1222 } 1223 1224 /** 1225 * Returns {@code true} if the apparent first queued thread, if one 1226 * exists, is waiting in exclusive mode. If this method returns 1227 * {@code true}, and the current thread is attempting to acquire in 1228 * shared mode (that is, this method is invoked from {@link 1229 * #tryAcquireShared}) then it is guaranteed that the current thread 1230 * is not the first queued thread. Used only as a heuristic in 1231 * ReentrantReadWriteLock. 1232 */ 1233 final boolean apparentlyFirstQueuedIsExclusive() { 1234 Node h, s; 1235 return (h = head) != null && 1236 (s = h.next) != null && 1237 !s.isShared() && 1238 s.thread != null; 1239 } 1240 1241 /** 1242 * Queries whether any threads have been waiting to acquire longer 1243 * than the current thread. 1244 * 1245 * <p>An invocation of this method is equivalent to (but may be 1246 * more efficient than): 1247 * <pre> {@code 1248 * getFirstQueuedThread() != Thread.currentThread() && 1249 * hasQueuedThreads()}</pre> 1250 * 1251 * <p>Note that because cancellations due to interrupts and 1252 * timeouts may occur at any time, a {@code true} return does not 1253 * guarantee that some other thread will acquire before the current 1254 * thread. Likewise, it is possible for another thread to win a 1255 * race to enqueue after this method has returned {@code false}, 1256 * due to the queue being empty. 1257 * 1258 * <p>This method is designed to be used by a fair synchronizer to 1259 * avoid <a href="AbstractQueuedSynchronizer#barging">barging</a>. 1260 * Such a synchronizer's {@link #tryAcquire} method should return 1261 * {@code false}, and its {@link #tryAcquireShared} method should 1262 * return a negative value, if this method returns {@code true} 1263 * (unless this is a reentrant acquire). For example, the {@code 1264 * tryAcquire} method for a fair, reentrant, exclusive mode 1265 * synchronizer might look like this: 1266 * 1267 * <pre> {@code 1268 * protected boolean tryAcquire(int arg) { 1269 * if (isHeldExclusively()) { 1270 * // A reentrant acquire; increment hold count 1271 * return true; 1272 * } else if (hasQueuedPredecessors()) { 1273 * return false; 1274 * } else { 1275 * // try to acquire normally 1276 * } 1277 * }}</pre> 1278 * 1279 * @return {@code true} if there is a queued thread preceding the 1280 * current thread, and {@code false} if the current thread 1281 * is at the head of the queue or the queue is empty 1282 * @since 1.7 1283 */ 1284 public final boolean hasQueuedPredecessors() { 1285 // The correctness of this depends on head being initialized 1286 // before tail and on head.next being accurate if the current 1287 // thread is first in queue. 1288 Node t = tail; // Read fields in reverse initialization order 1289 Node h = head; 1290 Node s; 1291 return h != t && 1292 ((s = h.next) == null || s.thread != Thread.currentThread()); 1293 } 1294 1295 1296 // Instrumentation and monitoring methods 1297 1298 /** 1299 * Returns an estimate of the number of threads waiting to 1300 * acquire. The value is only an estimate because the number of 1301 * threads may change dynamically while this method traverses 1302 * internal data structures. This method is designed for use in 1303 * monitoring system state, not for synchronization 1304 * control. 1305 * 1306 * @return the estimated number of threads waiting to acquire 1307 */ 1308 public final int getQueueLength() { 1309 int n = 0; 1310 for (Node p = tail; p != null; p = p.prev) { 1311 if (p.thread != null) 1312 ++n; 1313 } 1314 return n; 1315 } 1316 1317 /** 1318 * Returns a collection containing threads that may be waiting to 1319 * acquire. Because the actual set of threads may change 1320 * dynamically while constructing this result, the returned 1321 * collection is only a best-effort estimate. The elements of the 1322 * returned collection are in no particular order. This method is 1323 * designed to facilitate construction of subclasses that provide 1324 * more extensive monitoring facilities. 1325 * 1326 * @return the collection of threads 1327 */ 1328 public final Collection<Thread> getQueuedThreads() { 1329 ArrayList<Thread> list = new ArrayList<Thread>(); 1330 for (Node p = tail; p != null; p = p.prev) { 1331 Thread t = p.thread; 1332 if (t != null) 1333 list.add(t); 1334 } 1335 return list; 1336 } 1337 1338 /** 1339 * Returns a collection containing threads that may be waiting to 1340 * acquire in exclusive mode. This has the same properties 1341 * as {@link #getQueuedThreads} except that it only returns 1342 * those threads waiting due to an exclusive acquire. 1343 * 1344 * @return the collection of threads 1345 */ 1346 public final Collection<Thread> getExclusiveQueuedThreads() { 1347 ArrayList<Thread> list = new ArrayList<Thread>(); 1348 for (Node p = tail; p != null; p = p.prev) { 1349 if (!p.isShared()) { 1350 Thread t = p.thread; 1351 if (t != null) 1352 list.add(t); 1353 } 1354 } 1355 return list; 1356 } 1357 1358 /** 1359 * Returns a collection containing threads that may be waiting to 1360 * acquire in shared mode. This has the same properties 1361 * as {@link #getQueuedThreads} except that it only returns 1362 * those threads waiting due to a shared acquire. 1363 * 1364 * @return the collection of threads 1365 */ 1366 public final Collection<Thread> getSharedQueuedThreads() { 1367 ArrayList<Thread> list = new ArrayList<Thread>(); 1368 for (Node p = tail; p != null; p = p.prev) { 1369 if (p.isShared()) { 1370 Thread t = p.thread; 1371 if (t != null) 1372 list.add(t); 1373 } 1374 } 1375 return list; 1376 } 1377 1378 /** 1379 * Returns a string identifying this synchronizer, as well as its state. 1380 * The state, in brackets, includes the String {@code "State ="} 1381 * followed by the current value of {@link #getState}, and either 1382 * {@code "nonempty"} or {@code "empty"} depending on whether the 1383 * queue is empty. 1384 * 1385 * @return a string identifying this synchronizer, as well as its state 1386 */ 1387 public String toString() { 1388 long s = getState(); 1389 String q = hasQueuedThreads() ? "non" : ""; 1390 return super.toString() + 1391 "[State = " + s + ", " + q + "empty queue]"; 1392 } 1393 1394 1395 // Internal support methods for Conditions 1396 1397 /** 1398 * Returns true if a node, always one that was initially placed on 1399 * a condition queue, is now waiting to reacquire on sync queue. 1400 * @param node the node 1401 * @return true if is reacquiring 1402 */ 1403 final boolean isOnSyncQueue(Node node) { 1404 if (node.waitStatus == Node.CONDITION || node.prev == null) 1405 return false; 1406 if (node.next != null) // If has successor, it must be on queue 1407 return true; 1408 /* 1409 * node.prev can be non-null, but not yet on queue because 1410 * the CAS to place it on queue can fail. So we have to 1411 * traverse from tail to make sure it actually made it. It 1412 * will always be near the tail in calls to this method, and 1413 * unless the CAS failed (which is unlikely), it will be 1414 * there, so we hardly ever traverse much. 1415 */ 1416 return findNodeFromTail(node); 1417 } 1418 1419 /** 1420 * Returns true if node is on sync queue by searching backwards from tail. 1421 * Called only when needed by isOnSyncQueue. 1422 * @return true if present 1423 */ 1424 private boolean findNodeFromTail(Node node) { 1425 Node t = tail; 1426 for (;;) { 1427 if (t == node) 1428 return true; 1429 if (t == null) 1430 return false; 1431 t = t.prev; 1432 } 1433 } 1434 1435 /** 1436 * Transfers a node from a condition queue onto sync queue. 1437 * Returns true if successful. 1438 * @param node the node 1439 * @return true if successfully transferred (else the node was 1440 * cancelled before signal). 1441 */ 1442 final boolean transferForSignal(Node node) { 1443 /* 1444 * If cannot change waitStatus, the node has been cancelled. 1445 */ 1446 if (!compareAndSetWaitStatus(node, Node.CONDITION, 0)) 1447 return false; 1448 1449 /* 1450 * Splice onto queue and try to set waitStatus of predecessor to 1451 * indicate that thread is (probably) waiting. If cancelled or 1452 * attempt to set waitStatus fails, wake up to resync (in which 1453 * case the waitStatus can be transiently and harmlessly wrong). 1454 */ 1455 Node p = enq(node); 1456 int ws = p.waitStatus; 1457 if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL)) 1458 LockSupport.unpark(node.thread); 1459 return true; 1460 } 1461 1462 /** 1463 * Transfers node, if necessary, to sync queue after a cancelled 1464 * wait. Returns true if thread was cancelled before being 1465 * signalled. 1466 * @param current the waiting thread 1467 * @param node its node 1468 * @return true if cancelled before the node was signalled 1469 */ 1470 final boolean transferAfterCancelledWait(Node node) { 1471 if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) { 1472 enq(node); 1473 return true; 1474 } 1475 /* 1476 * If we lost out to a signal(), then we can't proceed 1477 * until it finishes its enq(). Cancelling during an 1478 * incomplete transfer is both rare and transient, so just 1479 * spin. 1480 */ 1481 while (!isOnSyncQueue(node)) 1482 Thread.yield(); 1483 return false; 1484 } 1485 1486 /** 1487 * Invokes release with current state value; returns saved state. 1488 * Cancels node and throws exception on failure. 1489 * @param node the condition node for this wait 1490 * @return previous sync state 1491 */ 1492 final long fullyRelease(Node node) { 1493 boolean failed = true; 1494 try { 1495 long savedState = getState(); 1496 if (release(savedState)) { 1497 failed = false; 1498 return savedState; 1499 } else { 1500 throw new IllegalMonitorStateException(); 1501 } 1502 } finally { 1503 if (failed) 1504 node.waitStatus = Node.CANCELLED; 1505 } 1506 } 1507 1508 // Instrumentation methods for conditions 1509 1510 /** 1511 * Queries whether the given ConditionObject 1512 * uses this synchronizer as its lock. 1513 * 1514 * @param condition the condition 1515 * @return <tt>true</tt> if owned 1516 * @throws NullPointerException if the condition is null 1517 */ 1518 public final boolean owns(ConditionObject condition) { 1519 if (condition == null) 1520 throw new NullPointerException(); 1521 return condition.isOwnedBy(this); 1522 } 1523 1524 /** 1525 * Queries whether any threads are waiting on the given condition 1526 * associated with this synchronizer. Note that because timeouts 1527 * and interrupts may occur at any time, a <tt>true</tt> return 1528 * does not guarantee that a future <tt>signal</tt> will awaken 1529 * any threads. This method is designed primarily for use in 1530 * monitoring of the system state. 1531 * 1532 * @param condition the condition 1533 * @return <tt>true</tt> if there are any waiting threads 1534 * @throws IllegalMonitorStateException if exclusive synchronization 1535 * is not held 1536 * @throws IllegalArgumentException if the given condition is 1537 * not associated with this synchronizer 1538 * @throws NullPointerException if the condition is null 1539 */ 1540 public final boolean hasWaiters(ConditionObject condition) { 1541 if (!owns(condition)) 1542 throw new IllegalArgumentException("Not owner"); 1543 return condition.hasWaiters(); 1544 } 1545 1546 /** 1547 * Returns an estimate of the number of threads waiting on the 1548 * given condition associated with this synchronizer. Note that 1549 * because timeouts and interrupts may occur at any time, the 1550 * estimate serves only as an upper bound on the actual number of 1551 * waiters. This method is designed for use in monitoring of the 1552 * system state, not for synchronization control. 1553 * 1554 * @param condition the condition 1555 * @return the estimated number of waiting threads 1556 * @throws IllegalMonitorStateException if exclusive synchronization 1557 * is not held 1558 * @throws IllegalArgumentException if the given condition is 1559 * not associated with this synchronizer 1560 * @throws NullPointerException if the condition is null 1561 */ 1562 public final int getWaitQueueLength(ConditionObject condition) { 1563 if (!owns(condition)) 1564 throw new IllegalArgumentException("Not owner"); 1565 return condition.getWaitQueueLength(); 1566 } 1567 1568 /** 1569 * Returns a collection containing those threads that may be 1570 * waiting on the given condition associated with this 1571 * synchronizer. Because the actual set of threads may change 1572 * dynamically while constructing this result, the returned 1573 * collection is only a best-effort estimate. The elements of the 1574 * returned collection are in no particular order. 1575 * 1576 * @param condition the condition 1577 * @return the collection of threads 1578 * @throws IllegalMonitorStateException if exclusive synchronization 1579 * is not held 1580 * @throws IllegalArgumentException if the given condition is 1581 * not associated with this synchronizer 1582 * @throws NullPointerException if the condition is null 1583 */ 1584 public final Collection<Thread> getWaitingThreads(ConditionObject condition) { 1585 if (!owns(condition)) 1586 throw new IllegalArgumentException("Not owner"); 1587 return condition.getWaitingThreads(); 1588 } 1589 1590 /** 1591 * Condition implementation for a {@link 1592 * AbstractQueuedLongSynchronizer} serving as the basis of a {@link 1593 * Lock} implementation. 1594 * 1595 * <p>Method documentation for this class describes mechanics, 1596 * not behavioral specifications from the point of view of Lock 1597 * and Condition users. Exported versions of this class will in 1598 * general need to be accompanied by documentation describing 1599 * condition semantics that rely on those of the associated 1600 * <tt>AbstractQueuedLongSynchronizer</tt>. 1601 * 1602 * <p>This class is Serializable, but all fields are transient, 1603 * so deserialized conditions have no waiters. 1604 * 1605 * @since 1.6 1606 */ 1607 public class ConditionObject implements Condition, java.io.Serializable { 1608 private static final long serialVersionUID = 1173984872572414699L; 1609 /** First node of condition queue. */ 1610 private transient Node firstWaiter; 1611 /** Last node of condition queue. */ 1612 private transient Node lastWaiter; 1613 1614 /** 1615 * Creates a new <tt>ConditionObject</tt> instance. 1616 */ 1617 public ConditionObject() { } 1618 1619 // Internal methods 1620 1621 /** 1622 * Adds a new waiter to wait queue. 1623 * @return its new wait node 1624 */ 1625 private Node addConditionWaiter() { 1626 Node t = lastWaiter; 1627 // If lastWaiter is cancelled, clean out. 1628 if (t != null && t.waitStatus != Node.CONDITION) { 1629 unlinkCancelledWaiters(); 1630 t = lastWaiter; 1631 } 1632 Node node = new Node(Thread.currentThread(), Node.CONDITION); 1633 if (t == null) 1634 firstWaiter = node; 1635 else 1636 t.nextWaiter = node; 1637 lastWaiter = node; 1638 return node; 1639 } 1640 1641 /** 1642 * Removes and transfers nodes until hit non-cancelled one or 1643 * null. Split out from signal in part to encourage compilers 1644 * to inline the case of no waiters. 1645 * @param first (non-null) the first node on condition queue 1646 */ 1647 private void doSignal(Node first) { 1648 do { 1649 if ( (firstWaiter = first.nextWaiter) == null) 1650 lastWaiter = null; 1651 first.nextWaiter = null; 1652 } while (!transferForSignal(first) && 1653 (first = firstWaiter) != null); 1654 } 1655 1656 /** 1657 * Removes and transfers all nodes. 1658 * @param first (non-null) the first node on condition queue 1659 */ 1660 private void doSignalAll(Node first) { 1661 lastWaiter = firstWaiter = null; 1662 do { 1663 Node next = first.nextWaiter; 1664 first.nextWaiter = null; 1665 transferForSignal(first); 1666 first = next; 1667 } while (first != null); 1668 } 1669 1670 /** 1671 * Unlinks cancelled waiter nodes from condition queue. 1672 * Called only while holding lock. This is called when 1673 * cancellation occurred during condition wait, and upon 1674 * insertion of a new waiter when lastWaiter is seen to have 1675 * been cancelled. This method is needed to avoid garbage 1676 * retention in the absence of signals. So even though it may 1677 * require a full traversal, it comes into play only when 1678 * timeouts or cancellations occur in the absence of 1679 * signals. It traverses all nodes rather than stopping at a 1680 * particular target to unlink all pointers to garbage nodes 1681 * without requiring many re-traversals during cancellation 1682 * storms. 1683 */ 1684 private void unlinkCancelledWaiters() { 1685 Node t = firstWaiter; 1686 Node trail = null; 1687 while (t != null) { 1688 Node next = t.nextWaiter; 1689 if (t.waitStatus != Node.CONDITION) { 1690 t.nextWaiter = null; 1691 if (trail == null) 1692 firstWaiter = next; 1693 else 1694 trail.nextWaiter = next; 1695 if (next == null) 1696 lastWaiter = trail; 1697 } 1698 else 1699 trail = t; 1700 t = next; 1701 } 1702 } 1703 1704 // public methods 1705 1706 /** 1707 * Moves the longest-waiting thread, if one exists, from the 1708 * wait queue for this condition to the wait queue for the 1709 * owning lock. 1710 * 1711 * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 1712 * returns {@code false} 1713 */ 1714 public final void signal() { 1715 if (!isHeldExclusively()) 1716 throw new IllegalMonitorStateException(); 1717 Node first = firstWaiter; 1718 if (first != null) 1719 doSignal(first); 1720 } 1721 1722 /** 1723 * Moves all threads from the wait queue for this condition to 1724 * the wait queue for the owning lock. 1725 * 1726 * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 1727 * returns {@code false} 1728 */ 1729 public final void signalAll() { 1730 if (!isHeldExclusively()) 1731 throw new IllegalMonitorStateException(); 1732 Node first = firstWaiter; 1733 if (first != null) 1734 doSignalAll(first); 1735 } 1736 1737 /** 1738 * Implements uninterruptible condition wait. 1739 * <ol> 1740 * <li> Save lock state returned by {@link #getState}. 1741 * <li> Invoke {@link #release} with 1742 * saved state as argument, throwing 1743 * IllegalMonitorStateException if it fails. 1744 * <li> Block until signalled. 1745 * <li> Reacquire by invoking specialized version of 1746 * {@link #acquire} with saved state as argument. 1747 * </ol> 1748 */ 1749 public final void awaitUninterruptibly() { 1750 Node node = addConditionWaiter(); 1751 long savedState = fullyRelease(node); 1752 boolean interrupted = false; 1753 while (!isOnSyncQueue(node)) { 1754 LockSupport.park(this); 1755 if (Thread.interrupted()) 1756 interrupted = true; 1757 } 1758 if (acquireQueued(node, savedState) || interrupted) 1759 selfInterrupt(); 1760 } 1761 1762 /* 1763 * For interruptible waits, we need to track whether to throw 1764 * InterruptedException, if interrupted while blocked on 1765 * condition, versus reinterrupt current thread, if 1766 * interrupted while blocked waiting to re-acquire. 1767 */ 1768 1769 /** Mode meaning to reinterrupt on exit from wait */ 1770 private static final int REINTERRUPT = 1; 1771 /** Mode meaning to throw InterruptedException on exit from wait */ 1772 private static final int THROW_IE = -1; 1773 1774 /** 1775 * Checks for interrupt, returning THROW_IE if interrupted 1776 * before signalled, REINTERRUPT if after signalled, or 1777 * 0 if not interrupted. 1778 */ 1779 private int checkInterruptWhileWaiting(Node node) { 1780 return Thread.interrupted() ? 1781 (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) : 1782 0; 1783 } 1784 1785 /** 1786 * Throws InterruptedException, reinterrupts current thread, or 1787 * does nothing, depending on mode. 1788 */ 1789 private void reportInterruptAfterWait(int interruptMode) 1790 throws InterruptedException { 1791 if (interruptMode == THROW_IE) 1792 throw new InterruptedException(); 1793 else if (interruptMode == REINTERRUPT) 1794 selfInterrupt(); 1795 } 1796 1797 /** 1798 * Implements interruptible condition wait. 1799 * <ol> 1800 * <li> If current thread is interrupted, throw InterruptedException. 1801 * <li> Save lock state returned by {@link #getState}. 1802 * <li> Invoke {@link #release} with 1803 * saved state as argument, throwing 1804 * IllegalMonitorStateException if it fails. 1805 * <li> Block until signalled or interrupted. 1806 * <li> Reacquire by invoking specialized version of 1807 * {@link #acquire} with saved state as argument. 1808 * <li> If interrupted while blocked in step 4, throw InterruptedException. 1809 * </ol> 1810 */ 1811 public final void await() throws InterruptedException { 1812 if (Thread.interrupted()) 1813 throw new InterruptedException(); 1814 Node node = addConditionWaiter(); 1815 long savedState = fullyRelease(node); 1816 int interruptMode = 0; 1817 while (!isOnSyncQueue(node)) { 1818 LockSupport.park(this); 1819 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 1820 break; 1821 } 1822 if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 1823 interruptMode = REINTERRUPT; 1824 if (node.nextWaiter != null) // clean up if cancelled 1825 unlinkCancelledWaiters(); 1826 if (interruptMode != 0) 1827 reportInterruptAfterWait(interruptMode); 1828 } 1829 1830 /** 1831 * Implements timed condition wait. 1832 * <ol> 1833 * <li> If current thread is interrupted, throw InterruptedException. 1834 * <li> Save lock state returned by {@link #getState}. 1835 * <li> Invoke {@link #release} with 1836 * saved state as argument, throwing 1837 * 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) throws InterruptedException { 1845 if (Thread.interrupted()) 1846 throw new InterruptedException(); 1847 Node node = addConditionWaiter(); 1848 long savedState = fullyRelease(node); 1849 long lastTime = System.nanoTime(); 1850 int interruptMode = 0; 1851 while (!isOnSyncQueue(node)) { 1852 if (nanosTimeout <= 0L) { 1853 transferAfterCancelledWait(node); 1854 break; 1855 } 1856 LockSupport.parkNanos(this, nanosTimeout); 1857 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 1858 break; 1859 1860 long now = System.nanoTime(); 1861 nanosTimeout -= now - lastTime; 1862 lastTime = now; 1863 } 1864 if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 1865 interruptMode = REINTERRUPT; 1866 if (node.nextWaiter != null) 1867 unlinkCancelledWaiters(); 1868 if (interruptMode != 0) 1869 reportInterruptAfterWait(interruptMode); 1870 return nanosTimeout - (System.nanoTime() - lastTime); 1871 } 1872 1873 /** 1874 * Implements absolute timed condition wait. 1875 * <ol> 1876 * <li> If current thread is interrupted, throw InterruptedException. 1877 * <li> Save lock state returned by {@link #getState}. 1878 * <li> Invoke {@link #release} with 1879 * saved state as argument, throwing 1880 * IllegalMonitorStateException if it fails. 1881 * <li> Block until signalled, interrupted, or timed out. 1882 * <li> Reacquire by invoking specialized version of 1883 * {@link #acquire} with saved state as argument. 1884 * <li> If interrupted while blocked in step 4, throw InterruptedException. 1885 * <li> If timed out while blocked in step 4, return false, else true. 1886 * </ol> 1887 */ 1888 public final boolean awaitUntil(Date deadline) throws InterruptedException { 1889 if (deadline == null) 1890 throw new NullPointerException(); 1891 long abstime = deadline.getTime(); 1892 if (Thread.interrupted()) 1893 throw new InterruptedException(); 1894 Node node = addConditionWaiter(); 1895 long savedState = fullyRelease(node); 1896 boolean timedout = false; 1897 int interruptMode = 0; 1898 while (!isOnSyncQueue(node)) { 1899 if (System.currentTimeMillis() > abstime) { 1900 timedout = transferAfterCancelledWait(node); 1901 break; 1902 } 1903 LockSupport.parkUntil(this, abstime); 1904 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 1905 break; 1906 } 1907 if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 1908 interruptMode = REINTERRUPT; 1909 if (node.nextWaiter != null) 1910 unlinkCancelledWaiters(); 1911 if (interruptMode != 0) 1912 reportInterruptAfterWait(interruptMode); 1913 return !timedout; 1914 } 1915 1916 /** 1917 * Implements timed condition wait. 1918 * <ol> 1919 * <li> If current thread is interrupted, throw InterruptedException. 1920 * <li> Save lock state returned by {@link #getState}. 1921 * <li> Invoke {@link #release} with 1922 * saved state as argument, throwing 1923 * IllegalMonitorStateException if it fails. 1924 * <li> Block until signalled, interrupted, or timed out. 1925 * <li> Reacquire by invoking specialized version of 1926 * {@link #acquire} with saved state as argument. 1927 * <li> If interrupted while blocked in step 4, throw InterruptedException. 1928 * <li> If timed out while blocked in step 4, return false, else true. 1929 * </ol> 1930 */ 1931 public final boolean await(long time, TimeUnit unit) throws InterruptedException { 1932 if (unit == null) 1933 throw new NullPointerException(); 1934 long nanosTimeout = unit.toNanos(time); 1935 if (Thread.interrupted()) 1936 throw new InterruptedException(); 1937 Node node = addConditionWaiter(); 1938 long savedState = fullyRelease(node); 1939 long lastTime = System.nanoTime(); 1940 boolean timedout = false; 1941 int interruptMode = 0; 1942 while (!isOnSyncQueue(node)) { 1943 if (nanosTimeout <= 0L) { 1944 timedout = transferAfterCancelledWait(node); 1945 break; 1946 } 1947 if (nanosTimeout >= spinForTimeoutThreshold) 1948 LockSupport.parkNanos(this, nanosTimeout); 1949 if ((interruptMode = checkInterruptWhileWaiting(node)) != 0) 1950 break; 1951 long now = System.nanoTime(); 1952 nanosTimeout -= now - lastTime; 1953 lastTime = now; 1954 } 1955 if (acquireQueued(node, savedState) && interruptMode != THROW_IE) 1956 interruptMode = REINTERRUPT; 1957 if (node.nextWaiter != null) 1958 unlinkCancelledWaiters(); 1959 if (interruptMode != 0) 1960 reportInterruptAfterWait(interruptMode); 1961 return !timedout; 1962 } 1963 1964 // support for instrumentation 1965 1966 /** 1967 * Returns true if this condition was created by the given 1968 * synchronization object. 1969 * 1970 * @return {@code true} if owned 1971 */ 1972 final boolean isOwnedBy(AbstractQueuedLongSynchronizer sync) { 1973 return sync == AbstractQueuedLongSynchronizer.this; 1974 } 1975 1976 /** 1977 * Queries whether any threads are waiting on this condition. 1978 * Implements {@link AbstractQueuedLongSynchronizer#hasWaiters}. 1979 * 1980 * @return {@code true} if there are any waiting threads 1981 * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 1982 * returns {@code false} 1983 */ 1984 protected final boolean hasWaiters() { 1985 if (!isHeldExclusively()) 1986 throw new IllegalMonitorStateException(); 1987 for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 1988 if (w.waitStatus == Node.CONDITION) 1989 return true; 1990 } 1991 return false; 1992 } 1993 1994 /** 1995 * Returns an estimate of the number of threads waiting on 1996 * this condition. 1997 * Implements {@link AbstractQueuedLongSynchronizer#getWaitQueueLength}. 1998 * 1999 * @return the estimated number of waiting threads 2000 * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 2001 * returns {@code false} 2002 */ 2003 protected final int getWaitQueueLength() { 2004 if (!isHeldExclusively()) 2005 throw new IllegalMonitorStateException(); 2006 int n = 0; 2007 for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2008 if (w.waitStatus == Node.CONDITION) 2009 ++n; 2010 } 2011 return n; 2012 } 2013 2014 /** 2015 * Returns a collection containing those threads that may be 2016 * waiting on this Condition. 2017 * Implements {@link AbstractQueuedLongSynchronizer#getWaitingThreads}. 2018 * 2019 * @return the collection of threads 2020 * @throws IllegalMonitorStateException if {@link #isHeldExclusively} 2021 * returns {@code false} 2022 */ 2023 protected final Collection<Thread> getWaitingThreads() { 2024 if (!isHeldExclusively()) 2025 throw new IllegalMonitorStateException(); 2026 ArrayList<Thread> list = new ArrayList<Thread>(); 2027 for (Node w = firstWaiter; w != null; w = w.nextWaiter) { 2028 if (w.waitStatus == Node.CONDITION) { 2029 Thread t = w.thread; 2030 if (t != null) 2031 list.add(t); 2032 } 2033 } 2034 return list; 2035 } 2036 } 2037 2038 /** 2039 * Setup to support compareAndSet. We need to natively implement 2040 * this here: For the sake of permitting future enhancements, we 2041 * cannot explicitly subclass AtomicLong, which would be 2042 * efficient and useful otherwise. So, as the lesser of evils, we 2043 * natively implement using hotspot intrinsics API. And while we 2044 * are at it, we do the same for other CASable fields (which could 2045 * otherwise be done with atomic field updaters). 2046 */ 2047 private static final Unsafe unsafe = Unsafe.getUnsafe(); 2048 private static final long stateOffset; 2049 private static final long headOffset; 2050 private static final long tailOffset; 2051 private static final long waitStatusOffset; 2052 private static final long nextOffset; 2053 2054 static { 2055 try { 2056 stateOffset = unsafe.objectFieldOffset 2057 (AbstractQueuedLongSynchronizer.class.getDeclaredField("state")); 2058 headOffset = unsafe.objectFieldOffset 2059 (AbstractQueuedLongSynchronizer.class.getDeclaredField("head")); 2060 tailOffset = unsafe.objectFieldOffset 2061 (AbstractQueuedLongSynchronizer.class.getDeclaredField("tail")); 2062 waitStatusOffset = unsafe.objectFieldOffset 2063 (Node.class.getDeclaredField("waitStatus")); 2064 nextOffset = unsafe.objectFieldOffset 2065 (Node.class.getDeclaredField("next")); 2066 2067 } catch (Exception ex) { throw new Error(ex); } 2068 } 2069 2070 /** 2071 * CAS head field. Used only by enq. 2072 */ 2073 private final boolean compareAndSetHead(Node update) { 2074 return unsafe.compareAndSwapObject(this, headOffset, null, update); 2075 } 2076 2077 /** 2078 * CAS tail field. Used only by enq. 2079 */ 2080 private final boolean compareAndSetTail(Node expect, Node update) { 2081 return unsafe.compareAndSwapObject(this, tailOffset, expect, update); 2082 } 2083 2084 /** 2085 * CAS waitStatus field of a node. 2086 */ 2087 private final static boolean compareAndSetWaitStatus(Node node, 2088 int expect, 2089 int update) { 2090 return unsafe.compareAndSwapInt(node, waitStatusOffset, 2091 expect, update); 2092 } 2093 2094 /** 2095 * CAS next field of a node. 2096 */ 2097 private final static boolean compareAndSetNext(Node node, 2098 Node expect, 2099 Node update) { 2100 return unsafe.compareAndSwapObject(node, nextOffset, expect, update); 2101 } 2102 }