1 /* 2 * Written by Doug Lea with assistance from members of JCP JSR-166 3 * Expert Group and released to the public domain, as explained at 4 * http://creativecommons.org/publicdomain/zero/1.0/ 5 */ 6 7 package java.util.concurrent.locks; 8 9 import java.util.concurrent.TimeUnit; 10 11 /** 12 * A capability-based lock with three modes for controlling read/write 13 * access. The state of a StampedLock consists of a version and mode. 14 * Lock acquisition methods return a stamp that represents and 15 * controls access with respect to a lock state; "try" versions of 16 * these methods may instead return the special value zero to 17 * represent failure to acquire access. Lock release and conversion 18 * methods require stamps as arguments, and fail if they do not match 19 * the state of the lock. The three modes are: 20 * 21 * <ul> 22 * 23 * <li><b>Writing.</b> Method {@link #writeLock} possibly blocks 24 * waiting for exclusive access, returning a stamp that can be used 25 * in method {@link #unlockWrite} to release the lock. Untimed and 26 * timed versions of {@code tryWriteLock} are also provided. When 27 * the lock is held in write mode, no read locks may be obtained, 28 * and all optimistic read validations will fail. 29 * 30 * <li><b>Reading.</b> Method {@link #readLock} possibly blocks 31 * waiting for non-exclusive access, returning a stamp that can be 32 * used in method {@link #unlockRead} to release the lock. Untimed 33 * and timed versions of {@code tryReadLock} are also provided. 34 * 35 * <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead} 36 * returns a non-zero stamp only if the lock is not currently held 37 * in write mode. Method {@link #validate} returns true if the lock 38 * has not been acquired in write mode since obtaining a given 39 * stamp. This mode can be thought of as an extremely weak version 40 * of a read-lock, that can be broken by a writer at any time. The 41 * use of optimistic mode for short read-only code segments often 42 * reduces contention and improves throughput. However, its use is 43 * inherently fragile. Optimistic read sections should only read 44 * fields and hold them in local variables for later use after 45 * validation. Fields read while in optimistic mode may be wildly 46 * inconsistent, so usage applies only when you are familiar enough 47 * with data representations to check consistency and/or repeatedly 48 * invoke method {@code validate()}. For example, such steps are 49 * typically required when first reading an object or array 50 * reference, and then accessing one of its fields, elements or 51 * methods. 52 * 53 * </ul> 54 * 55 * <p>This class also supports methods that conditionally provide 56 * conversions across the three modes. For example, method {@link 57 * #tryConvertToWriteLock} attempts to "upgrade" a mode, returning 58 * a valid write stamp if (1) already in writing mode (2) in reading 59 * mode and there are no other readers or (3) in optimistic mode and 60 * the lock is available. The forms of these methods are designed to 61 * help reduce some of the code bloat that otherwise occurs in 62 * retry-based designs. 63 * 64 * <p>StampedLocks are designed for use as internal utilities in the 65 * development of thread-safe components. Their use relies on 66 * knowledge of the internal properties of the data, objects, and 67 * methods they are protecting. They are not reentrant, so locked 68 * bodies should not call other unknown methods that may try to 69 * re-acquire locks (although you may pass a stamp to other methods 70 * that can use or convert it). The use of read lock modes relies on 71 * the associated code sections being side-effect-free. Unvalidated 72 * optimistic read sections cannot call methods that are not known to 73 * tolerate potential inconsistencies. Stamps use finite 74 * representations, and are not cryptographically secure (i.e., a 75 * valid stamp may be guessable). Stamp values may recycle after (no 76 * sooner than) one year of continuous operation. A stamp held without 77 * use or validation for longer than this period may fail to validate 78 * correctly. StampedLocks are serializable, but always deserialize 79 * into initial unlocked state, so they are not useful for remote 80 * locking. 81 * 82 * <p>The scheduling policy of StampedLock does not consistently 83 * prefer readers over writers or vice versa. All "try" methods are 84 * best-effort and do not necessarily conform to any scheduling or 85 * fairness policy. A zero return from any "try" method for acquiring 86 * or converting locks does not carry any information about the state 87 * of the lock; a subsequent invocation may succeed. 88 * 89 * <p>Because it supports coordinated usage across multiple lock 90 * modes, this class does not directly implement the {@link Lock} or 91 * {@link ReadWriteLock} interfaces. However, a StampedLock may be 92 * viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link 93 * #asReadWriteLock()} in applications requiring only the associated 94 * set of functionality. 95 * 96 * <p><b>Sample Usage.</b> The following illustrates some usage idioms 97 * in a class that maintains simple two-dimensional points. The sample 98 * code illustrates some try/catch conventions even though they are 99 * not strictly needed here because no exceptions can occur in their 100 * bodies.<br> 101 * 102 * <pre> {@code 103 * class Point { 104 * private double x, y; 105 * private final StampedLock sl = new StampedLock(); 106 * 107 * void move(double deltaX, double deltaY) { // an exclusively locked method 108 * long stamp = sl.writeLock(); 109 * try { 110 * x += deltaX; 111 * y += deltaY; 112 * } finally { 113 * sl.unlockWrite(stamp); 114 * } 115 * } 116 * 117 * double distanceFromOrigin() { // A read-only method 118 * long stamp = sl.tryOptimisticRead(); 119 * double currentX = x, currentY = y; 120 * if (!sl.validate(stamp)) { 121 * stamp = sl.readLock(); 122 * try { 123 * currentX = x; 124 * currentY = y; 125 * } finally { 126 * sl.unlockRead(stamp); 127 * } 128 * } 129 * return Math.sqrt(currentX * currentX + currentY * currentY); 130 * } 131 * 132 * void moveIfAtOrigin(double newX, double newY) { // upgrade 133 * // Could instead start with optimistic, not read mode 134 * long stamp = sl.readLock(); 135 * try { 136 * while (x == 0.0 && y == 0.0) { 137 * long ws = sl.tryConvertToWriteLock(stamp); 138 * if (ws != 0L) { 139 * stamp = ws; 140 * x = newX; 141 * y = newY; 142 * break; 143 * } 144 * else { 145 * sl.unlockRead(stamp); 146 * stamp = sl.writeLock(); 147 * } 148 * } 149 * } finally { 150 * sl.unlock(stamp); 151 * } 152 * } 153 * }}</pre> 154 * 155 * @since 1.8 156 * @author Doug Lea 157 */ 158 public class StampedLock implements java.io.Serializable { 159 /* 160 * Algorithmic notes: 161 * 162 * The design employs elements of Sequence locks 163 * (as used in linux kernels; see Lameter's 164 * http://www.lameter.com/gelato2005.pdf 165 * and elsewhere; see 166 * Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html) 167 * and Ordered RW locks (see Shirako et al 168 * http://dl.acm.org/citation.cfm?id=2312015) 169 * 170 * Conceptually, the primary state of the lock includes a sequence 171 * number that is odd when write-locked and even otherwise. 172 * However, this is offset by a reader count that is non-zero when 173 * read-locked. The read count is ignored when validating 174 * "optimistic" seqlock-reader-style stamps. Because we must use 175 * a small finite number of bits (currently 7) for readers, a 176 * supplementary reader overflow word is used when the number of 177 * readers exceeds the count field. We do this by treating the max 178 * reader count value (RBITS) as a spinlock protecting overflow 179 * updates. 180 * 181 * Waiters use a modified form of CLH lock used in 182 * AbstractQueuedSynchronizer (see its internal documentation for 183 * a fuller account), where each node is tagged (field mode) as 184 * either a reader or writer. Sets of waiting readers are grouped 185 * (linked) under a common node (field cowait) so act as a single 186 * node with respect to most CLH mechanics. By virtue of the 187 * queue structure, wait nodes need not actually carry sequence 188 * numbers; we know each is greater than its predecessor. This 189 * simplifies the scheduling policy to a mainly-FIFO scheme that 190 * incorporates elements of Phase-Fair locks (see Brandenburg & 191 * Anderson, especially http://www.cs.unc.edu/~bbb/diss/). In 192 * particular, we use the phase-fair anti-barging rule: If an 193 * incoming reader arrives while read lock is held but there is a 194 * queued writer, this incoming reader is queued. (This rule is 195 * responsible for some of the complexity of method acquireRead, 196 * but without it, the lock becomes highly unfair.) Method release 197 * does not (and sometimes cannot) itself wake up cowaiters. This 198 * is done by the primary thread, but helped by any other threads 199 * with nothing better to do in methods acquireRead and 200 * acquireWrite. 201 * 202 * These rules apply to threads actually queued. All tryLock forms 203 * opportunistically try to acquire locks regardless of preference 204 * rules, and so may "barge" their way in. Randomized spinning is 205 * used in the acquire methods to reduce (increasingly expensive) 206 * context switching while also avoiding sustained memory 207 * thrashing among many threads. We limit spins to the head of 208 * queue. A thread spin-waits up to SPINS times (where each 209 * iteration decreases spin count with 50% probability) before 210 * blocking. If, upon wakening it fails to obtain lock, and is 211 * still (or becomes) the first waiting thread (which indicates 212 * that some other thread barged and obtained lock), it escalates 213 * spins (up to MAX_HEAD_SPINS) to reduce the likelihood of 214 * continually losing to barging threads. 215 * 216 * Nearly all of these mechanics are carried out in methods 217 * acquireWrite and acquireRead, that, as typical of such code, 218 * sprawl out because actions and retries rely on consistent sets 219 * of locally cached reads. 220 * 221 * As noted in Boehm's paper (above), sequence validation (mainly 222 * method validate()) requires stricter ordering rules than apply 223 * to normal volatile reads (of "state"). To force orderings of 224 * reads before a validation and the validation itself in those 225 * cases where this is not already forced, we use 226 * Unsafe.loadFence. 227 * 228 * The memory layout keeps lock state and queue pointers together 229 * (normally on the same cache line). This usually works well for 230 * read-mostly loads. In most other cases, the natural tendency of 231 * adaptive-spin CLH locks to reduce memory contention lessens 232 * motivation to further spread out contended locations, but might 233 * be subject to future improvements. 234 */ 235 236 private static final long serialVersionUID = -6001602636862214147L; 237 238 /** Number of processors, for spin control */ 239 private static final int NCPU = Runtime.getRuntime().availableProcessors(); 240 241 /** Maximum number of retries before enqueuing on acquisition */ 242 private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0; 243 244 /** Maximum number of retries before blocking at head on acquisition */ 245 private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0; 246 247 /** Maximum number of retries before re-blocking */ 248 private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0; 249 250 /** The period for yielding when waiting for overflow spinlock */ 251 private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1 252 253 /** The number of bits to use for reader count before overflowing */ 254 private static final int LG_READERS = 7; 255 256 // Values for lock state and stamp operations 257 private static final long RUNIT = 1L; 258 private static final long WBIT = 1L << LG_READERS; 259 private static final long RBITS = WBIT - 1L; 260 private static final long RFULL = RBITS - 1L; 261 private static final long ABITS = RBITS | WBIT; 262 private static final long SBITS = ~RBITS; // note overlap with ABITS 263 264 // Initial value for lock state; avoid failure value zero 265 private static final long ORIGIN = WBIT << 1; 266 267 // Special value from cancelled acquire methods so caller can throw IE 268 private static final long INTERRUPTED = 1L; 269 270 // Values for node status; order matters 271 private static final int WAITING = -1; 272 private static final int CANCELLED = 1; 273 274 // Modes for nodes (int not boolean to allow arithmetic) 275 private static final int RMODE = 0; 276 private static final int WMODE = 1; 277 278 /** Wait nodes */ 279 static final class WNode { 280 volatile WNode prev; 281 volatile WNode next; 282 volatile WNode cowait; // list of linked readers 283 volatile Thread thread; // non-null while possibly parked 284 volatile int status; // 0, WAITING, or CANCELLED 285 final int mode; // RMODE or WMODE WNode(int m, WNode p)286 WNode(int m, WNode p) { mode = m; prev = p; } 287 } 288 289 /** Head of CLH queue */ 290 private transient volatile WNode whead; 291 /** Tail (last) of CLH queue */ 292 private transient volatile WNode wtail; 293 294 // views 295 transient ReadLockView readLockView; 296 transient WriteLockView writeLockView; 297 transient ReadWriteLockView readWriteLockView; 298 299 /** Lock sequence/state */ 300 private transient volatile long state; 301 /** extra reader count when state read count saturated */ 302 private transient int readerOverflow; 303 304 /** 305 * Creates a new lock, initially in unlocked state. 306 */ StampedLock()307 public StampedLock() { 308 state = ORIGIN; 309 } 310 311 /** 312 * Exclusively acquires the lock, blocking if necessary 313 * until available. 314 * 315 * @return a stamp that can be used to unlock or convert mode 316 */ writeLock()317 public long writeLock() { 318 long s, next; // bypass acquireWrite in fully unlocked case only 319 return ((((s = state) & ABITS) == 0L && 320 U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? 321 next : acquireWrite(false, 0L)); 322 } 323 324 /** 325 * Exclusively acquires the lock if it is immediately available. 326 * 327 * @return a stamp that can be used to unlock or convert mode, 328 * or zero if the lock is not available 329 */ tryWriteLock()330 public long tryWriteLock() { 331 long s, next; 332 return ((((s = state) & ABITS) == 0L && 333 U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? 334 next : 0L); 335 } 336 337 /** 338 * Exclusively acquires the lock if it is available within the 339 * given time and the current thread has not been interrupted. 340 * Behavior under timeout and interruption matches that specified 341 * for method {@link Lock#tryLock(long,TimeUnit)}. 342 * 343 * @param time the maximum time to wait for the lock 344 * @param unit the time unit of the {@code time} argument 345 * @return a stamp that can be used to unlock or convert mode, 346 * or zero if the lock is not available 347 * @throws InterruptedException if the current thread is interrupted 348 * before acquiring the lock 349 */ tryWriteLock(long time, TimeUnit unit)350 public long tryWriteLock(long time, TimeUnit unit) 351 throws InterruptedException { 352 long nanos = unit.toNanos(time); 353 if (!Thread.interrupted()) { 354 long next, deadline; 355 if ((next = tryWriteLock()) != 0L) 356 return next; 357 if (nanos <= 0L) 358 return 0L; 359 if ((deadline = System.nanoTime() + nanos) == 0L) 360 deadline = 1L; 361 if ((next = acquireWrite(true, deadline)) != INTERRUPTED) 362 return next; 363 } 364 throw new InterruptedException(); 365 } 366 367 /** 368 * Exclusively acquires the lock, blocking if necessary 369 * until available or the current thread is interrupted. 370 * Behavior under interruption matches that specified 371 * for method {@link Lock#lockInterruptibly()}. 372 * 373 * @return a stamp that can be used to unlock or convert mode 374 * @throws InterruptedException if the current thread is interrupted 375 * before acquiring the lock 376 */ writeLockInterruptibly()377 public long writeLockInterruptibly() throws InterruptedException { 378 long next; 379 if (!Thread.interrupted() && 380 (next = acquireWrite(true, 0L)) != INTERRUPTED) 381 return next; 382 throw new InterruptedException(); 383 } 384 385 /** 386 * Non-exclusively acquires the lock, blocking if necessary 387 * until available. 388 * 389 * @return a stamp that can be used to unlock or convert mode 390 */ readLock()391 public long readLock() { 392 long s = state, next; // bypass acquireRead on common uncontended case 393 return ((whead == wtail && (s & ABITS) < RFULL && 394 U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ? 395 next : acquireRead(false, 0L)); 396 } 397 398 /** 399 * Non-exclusively acquires the lock if it is immediately available. 400 * 401 * @return a stamp that can be used to unlock or convert mode, 402 * or zero if the lock is not available 403 */ tryReadLock()404 public long tryReadLock() { 405 for (;;) { 406 long s, m, next; 407 if ((m = (s = state) & ABITS) == WBIT) 408 return 0L; 409 else if (m < RFULL) { 410 if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) 411 return next; 412 } 413 else if ((next = tryIncReaderOverflow(s)) != 0L) 414 return next; 415 } 416 } 417 418 /** 419 * Non-exclusively acquires the lock if it is available within the 420 * given time and the current thread has not been interrupted. 421 * Behavior under timeout and interruption matches that specified 422 * for method {@link Lock#tryLock(long,TimeUnit)}. 423 * 424 * @param time the maximum time to wait for the lock 425 * @param unit the time unit of the {@code time} argument 426 * @return a stamp that can be used to unlock or convert mode, 427 * or zero if the lock is not available 428 * @throws InterruptedException if the current thread is interrupted 429 * before acquiring the lock 430 */ tryReadLock(long time, TimeUnit unit)431 public long tryReadLock(long time, TimeUnit unit) 432 throws InterruptedException { 433 long s, m, next, deadline; 434 long nanos = unit.toNanos(time); 435 if (!Thread.interrupted()) { 436 if ((m = (s = state) & ABITS) != WBIT) { 437 if (m < RFULL) { 438 if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) 439 return next; 440 } 441 else if ((next = tryIncReaderOverflow(s)) != 0L) 442 return next; 443 } 444 if (nanos <= 0L) 445 return 0L; 446 if ((deadline = System.nanoTime() + nanos) == 0L) 447 deadline = 1L; 448 if ((next = acquireRead(true, deadline)) != INTERRUPTED) 449 return next; 450 } 451 throw new InterruptedException(); 452 } 453 454 /** 455 * Non-exclusively acquires the lock, blocking if necessary 456 * until available or the current thread is interrupted. 457 * Behavior under interruption matches that specified 458 * for method {@link Lock#lockInterruptibly()}. 459 * 460 * @return a stamp that can be used to unlock or convert mode 461 * @throws InterruptedException if the current thread is interrupted 462 * before acquiring the lock 463 */ readLockInterruptibly()464 public long readLockInterruptibly() throws InterruptedException { 465 long next; 466 if (!Thread.interrupted() && 467 (next = acquireRead(true, 0L)) != INTERRUPTED) 468 return next; 469 throw new InterruptedException(); 470 } 471 472 /** 473 * Returns a stamp that can later be validated, or zero 474 * if exclusively locked. 475 * 476 * @return a stamp, or zero if exclusively locked 477 */ tryOptimisticRead()478 public long tryOptimisticRead() { 479 long s; 480 return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L; 481 } 482 483 /** 484 * Returns true if the lock has not been exclusively acquired 485 * since issuance of the given stamp. Always returns false if the 486 * stamp is zero. Always returns true if the stamp represents a 487 * currently held lock. Invoking this method with a value not 488 * obtained from {@link #tryOptimisticRead} or a locking method 489 * for this lock has no defined effect or result. 490 * 491 * @param stamp a stamp 492 * @return {@code true} if the lock has not been exclusively acquired 493 * since issuance of the given stamp; else false 494 */ validate(long stamp)495 public boolean validate(long stamp) { 496 U.loadFence(); 497 return (stamp & SBITS) == (state & SBITS); 498 } 499 500 /** 501 * If the lock state matches the given stamp, releases the 502 * exclusive lock. 503 * 504 * @param stamp a stamp returned by a write-lock operation 505 * @throws IllegalMonitorStateException if the stamp does 506 * not match the current state of this lock 507 */ unlockWrite(long stamp)508 public void unlockWrite(long stamp) { 509 WNode h; 510 if (state != stamp || (stamp & WBIT) == 0L) 511 throw new IllegalMonitorStateException(); 512 U.putLongVolatile(this, STATE, (stamp += WBIT) == 0L ? ORIGIN : stamp); 513 if ((h = whead) != null && h.status != 0) 514 release(h); 515 } 516 517 /** 518 * If the lock state matches the given stamp, releases the 519 * non-exclusive lock. 520 * 521 * @param stamp a stamp returned by a read-lock operation 522 * @throws IllegalMonitorStateException if the stamp does 523 * not match the current state of this lock 524 */ unlockRead(long stamp)525 public void unlockRead(long stamp) { 526 long s, m; WNode h; 527 for (;;) { 528 if (((s = state) & SBITS) != (stamp & SBITS) || 529 (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT) 530 throw new IllegalMonitorStateException(); 531 if (m < RFULL) { 532 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 533 if (m == RUNIT && (h = whead) != null && h.status != 0) 534 release(h); 535 break; 536 } 537 } 538 else if (tryDecReaderOverflow(s) != 0L) 539 break; 540 } 541 } 542 543 /** 544 * If the lock state matches the given stamp, releases the 545 * corresponding mode of the lock. 546 * 547 * @param stamp a stamp returned by a lock operation 548 * @throws IllegalMonitorStateException if the stamp does 549 * not match the current state of this lock 550 */ unlock(long stamp)551 public void unlock(long stamp) { 552 long a = stamp & ABITS, m, s; WNode h; 553 while (((s = state) & SBITS) == (stamp & SBITS)) { 554 if ((m = s & ABITS) == 0L) 555 break; 556 else if (m == WBIT) { 557 if (a != m) 558 break; 559 U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s); 560 if ((h = whead) != null && h.status != 0) 561 release(h); 562 return; 563 } 564 else if (a == 0L || a >= WBIT) 565 break; 566 else if (m < RFULL) { 567 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 568 if (m == RUNIT && (h = whead) != null && h.status != 0) 569 release(h); 570 return; 571 } 572 } 573 else if (tryDecReaderOverflow(s) != 0L) 574 return; 575 } 576 throw new IllegalMonitorStateException(); 577 } 578 579 /** 580 * If the lock state matches the given stamp, atomically performs one of 581 * the following actions. If the stamp represents holding a write 582 * lock, returns it. Or, if a read lock, if the write lock is 583 * available, releases the read lock and returns a write stamp. 584 * Or, if an optimistic read, returns a write stamp only if 585 * immediately available. This method returns zero in all other 586 * cases. 587 * 588 * @param stamp a stamp 589 * @return a valid write stamp, or zero on failure 590 */ tryConvertToWriteLock(long stamp)591 public long tryConvertToWriteLock(long stamp) { 592 long a = stamp & ABITS, m, s, next; 593 while (((s = state) & SBITS) == (stamp & SBITS)) { 594 if ((m = s & ABITS) == 0L) { 595 if (a != 0L) 596 break; 597 if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) 598 return next; 599 } 600 else if (m == WBIT) { 601 if (a != m) 602 break; 603 return stamp; 604 } 605 else if (m == RUNIT && a != 0L) { 606 if (U.compareAndSwapLong(this, STATE, s, 607 next = s - RUNIT + WBIT)) 608 return next; 609 } 610 else 611 break; 612 } 613 return 0L; 614 } 615 616 /** 617 * If the lock state matches the given stamp, atomically performs one of 618 * the following actions. If the stamp represents holding a write 619 * lock, releases it and obtains a read lock. Or, if a read lock, 620 * returns it. Or, if an optimistic read, acquires a read lock and 621 * returns a read stamp only if immediately available. This method 622 * returns zero in all other cases. 623 * 624 * @param stamp a stamp 625 * @return a valid read stamp, or zero on failure 626 */ tryConvertToReadLock(long stamp)627 public long tryConvertToReadLock(long stamp) { 628 long a = stamp & ABITS, m, s, next; WNode h; 629 while (((s = state) & SBITS) == (stamp & SBITS)) { 630 if ((m = s & ABITS) == 0L) { 631 if (a != 0L) 632 break; 633 else if (m < RFULL) { 634 if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) 635 return next; 636 } 637 else if ((next = tryIncReaderOverflow(s)) != 0L) 638 return next; 639 } 640 else if (m == WBIT) { 641 if (a != m) 642 break; 643 U.putLongVolatile(this, STATE, next = s + (WBIT + RUNIT)); 644 if ((h = whead) != null && h.status != 0) 645 release(h); 646 return next; 647 } 648 else if (a != 0L && a < WBIT) 649 return stamp; 650 else 651 break; 652 } 653 return 0L; 654 } 655 656 /** 657 * If the lock state matches the given stamp then, atomically, if the stamp 658 * represents holding a lock, releases it and returns an 659 * observation stamp. Or, if an optimistic read, returns it if 660 * validated. This method returns zero in all other cases, and so 661 * may be useful as a form of "tryUnlock". 662 * 663 * @param stamp a stamp 664 * @return a valid optimistic read stamp, or zero on failure 665 */ tryConvertToOptimisticRead(long stamp)666 public long tryConvertToOptimisticRead(long stamp) { 667 long a = stamp & ABITS, m, s, next; WNode h; 668 U.loadFence(); 669 for (;;) { 670 if (((s = state) & SBITS) != (stamp & SBITS)) 671 break; 672 if ((m = s & ABITS) == 0L) { 673 if (a != 0L) 674 break; 675 return s; 676 } 677 else if (m == WBIT) { 678 if (a != m) 679 break; 680 U.putLongVolatile(this, STATE, 681 next = (s += WBIT) == 0L ? ORIGIN : s); 682 if ((h = whead) != null && h.status != 0) 683 release(h); 684 return next; 685 } 686 else if (a == 0L || a >= WBIT) 687 break; 688 else if (m < RFULL) { 689 if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) { 690 if (m == RUNIT && (h = whead) != null && h.status != 0) 691 release(h); 692 return next & SBITS; 693 } 694 } 695 else if ((next = tryDecReaderOverflow(s)) != 0L) 696 return next & SBITS; 697 } 698 return 0L; 699 } 700 701 /** 702 * Releases the write lock if it is held, without requiring a 703 * stamp value. This method may be useful for recovery after 704 * errors. 705 * 706 * @return {@code true} if the lock was held, else false 707 */ tryUnlockWrite()708 public boolean tryUnlockWrite() { 709 long s; WNode h; 710 if (((s = state) & WBIT) != 0L) { 711 U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s); 712 if ((h = whead) != null && h.status != 0) 713 release(h); 714 return true; 715 } 716 return false; 717 } 718 719 /** 720 * Releases one hold of the read lock if it is held, without 721 * requiring a stamp value. This method may be useful for recovery 722 * after errors. 723 * 724 * @return {@code true} if the read lock was held, else false 725 */ tryUnlockRead()726 public boolean tryUnlockRead() { 727 long s, m; WNode h; 728 while ((m = (s = state) & ABITS) != 0L && m < WBIT) { 729 if (m < RFULL) { 730 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 731 if (m == RUNIT && (h = whead) != null && h.status != 0) 732 release(h); 733 return true; 734 } 735 } 736 else if (tryDecReaderOverflow(s) != 0L) 737 return true; 738 } 739 return false; 740 } 741 742 // status monitoring methods 743 744 /** 745 * Returns combined state-held and overflow read count for given 746 * state s. 747 */ getReadLockCount(long s)748 private int getReadLockCount(long s) { 749 long readers; 750 if ((readers = s & RBITS) >= RFULL) 751 readers = RFULL + readerOverflow; 752 return (int) readers; 753 } 754 755 /** 756 * Returns {@code true} if the lock is currently held exclusively. 757 * 758 * @return {@code true} if the lock is currently held exclusively 759 */ isWriteLocked()760 public boolean isWriteLocked() { 761 return (state & WBIT) != 0L; 762 } 763 764 /** 765 * Returns {@code true} if the lock is currently held non-exclusively. 766 * 767 * @return {@code true} if the lock is currently held non-exclusively 768 */ isReadLocked()769 public boolean isReadLocked() { 770 return (state & RBITS) != 0L; 771 } 772 773 /** 774 * Queries the number of read locks held for this lock. This 775 * method is designed for use in monitoring system state, not for 776 * synchronization control. 777 * @return the number of read locks held 778 */ getReadLockCount()779 public int getReadLockCount() { 780 return getReadLockCount(state); 781 } 782 783 /** 784 * Returns a string identifying this lock, as well as its lock 785 * state. The state, in brackets, includes the String {@code 786 * "Unlocked"} or the String {@code "Write-locked"} or the String 787 * {@code "Read-locks:"} followed by the current number of 788 * read-locks held. 789 * 790 * @return a string identifying this lock, as well as its lock state 791 */ toString()792 public String toString() { 793 long s = state; 794 return super.toString() + 795 ((s & ABITS) == 0L ? "[Unlocked]" : 796 (s & WBIT) != 0L ? "[Write-locked]" : 797 "[Read-locks:" + getReadLockCount(s) + "]"); 798 } 799 800 // views 801 802 /** 803 * Returns a plain {@link Lock} view of this StampedLock in which 804 * the {@link Lock#lock} method is mapped to {@link #readLock}, 805 * and similarly for other methods. The returned Lock does not 806 * support a {@link Condition}; method {@link 807 * Lock#newCondition()} throws {@code 808 * UnsupportedOperationException}. 809 * 810 * @return the lock 811 */ asReadLock()812 public Lock asReadLock() { 813 ReadLockView v; 814 return ((v = readLockView) != null ? v : 815 (readLockView = new ReadLockView())); 816 } 817 818 /** 819 * Returns a plain {@link Lock} view of this StampedLock in which 820 * the {@link Lock#lock} method is mapped to {@link #writeLock}, 821 * and similarly for other methods. The returned Lock does not 822 * support a {@link Condition}; method {@link 823 * Lock#newCondition()} throws {@code 824 * UnsupportedOperationException}. 825 * 826 * @return the lock 827 */ asWriteLock()828 public Lock asWriteLock() { 829 WriteLockView v; 830 return ((v = writeLockView) != null ? v : 831 (writeLockView = new WriteLockView())); 832 } 833 834 /** 835 * Returns a {@link ReadWriteLock} view of this StampedLock in 836 * which the {@link ReadWriteLock#readLock()} method is mapped to 837 * {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to 838 * {@link #asWriteLock()}. 839 * 840 * @return the lock 841 */ asReadWriteLock()842 public ReadWriteLock asReadWriteLock() { 843 ReadWriteLockView v; 844 return ((v = readWriteLockView) != null ? v : 845 (readWriteLockView = new ReadWriteLockView())); 846 } 847 848 // view classes 849 850 final class ReadLockView implements Lock { lock()851 public void lock() { readLock(); } lockInterruptibly()852 public void lockInterruptibly() throws InterruptedException { 853 readLockInterruptibly(); 854 } tryLock()855 public boolean tryLock() { return tryReadLock() != 0L; } tryLock(long time, TimeUnit unit)856 public boolean tryLock(long time, TimeUnit unit) 857 throws InterruptedException { 858 return tryReadLock(time, unit) != 0L; 859 } unlock()860 public void unlock() { unstampedUnlockRead(); } newCondition()861 public Condition newCondition() { 862 throw new UnsupportedOperationException(); 863 } 864 } 865 866 final class WriteLockView implements Lock { lock()867 public void lock() { writeLock(); } lockInterruptibly()868 public void lockInterruptibly() throws InterruptedException { 869 writeLockInterruptibly(); 870 } tryLock()871 public boolean tryLock() { return tryWriteLock() != 0L; } tryLock(long time, TimeUnit unit)872 public boolean tryLock(long time, TimeUnit unit) 873 throws InterruptedException { 874 return tryWriteLock(time, unit) != 0L; 875 } unlock()876 public void unlock() { unstampedUnlockWrite(); } newCondition()877 public Condition newCondition() { 878 throw new UnsupportedOperationException(); 879 } 880 } 881 882 final class ReadWriteLockView implements ReadWriteLock { readLock()883 public Lock readLock() { return asReadLock(); } writeLock()884 public Lock writeLock() { return asWriteLock(); } 885 } 886 887 // Unlock methods without stamp argument checks for view classes. 888 // Needed because view-class lock methods throw away stamps. 889 unstampedUnlockWrite()890 final void unstampedUnlockWrite() { 891 WNode h; long s; 892 if (((s = state) & WBIT) == 0L) 893 throw new IllegalMonitorStateException(); 894 U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s); 895 if ((h = whead) != null && h.status != 0) 896 release(h); 897 } 898 unstampedUnlockRead()899 final void unstampedUnlockRead() { 900 for (;;) { 901 long s, m; WNode h; 902 if ((m = (s = state) & ABITS) == 0L || m >= WBIT) 903 throw new IllegalMonitorStateException(); 904 else if (m < RFULL) { 905 if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 906 if (m == RUNIT && (h = whead) != null && h.status != 0) 907 release(h); 908 break; 909 } 910 } 911 else if (tryDecReaderOverflow(s) != 0L) 912 break; 913 } 914 } 915 readObject(java.io.ObjectInputStream s)916 private void readObject(java.io.ObjectInputStream s) 917 throws java.io.IOException, ClassNotFoundException { 918 s.defaultReadObject(); 919 U.putLongVolatile(this, STATE, ORIGIN); // reset to unlocked state 920 } 921 922 // internals 923 924 /** 925 * Tries to increment readerOverflow by first setting state 926 * access bits value to RBITS, indicating hold of spinlock, 927 * then updating, then releasing. 928 * 929 * @param s a reader overflow stamp: (s & ABITS) >= RFULL 930 * @return new stamp on success, else zero 931 */ tryIncReaderOverflow(long s)932 private long tryIncReaderOverflow(long s) { 933 // assert (s & ABITS) >= RFULL; 934 if ((s & ABITS) == RFULL) { 935 if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) { 936 ++readerOverflow; 937 U.putLongVolatile(this, STATE, s); 938 return s; 939 } 940 } 941 else if ((LockSupport.nextSecondarySeed() & 942 OVERFLOW_YIELD_RATE) == 0) 943 Thread.yield(); 944 return 0L; 945 } 946 947 /** 948 * Tries to decrement readerOverflow. 949 * 950 * @param s a reader overflow stamp: (s & ABITS) >= RFULL 951 * @return new stamp on success, else zero 952 */ tryDecReaderOverflow(long s)953 private long tryDecReaderOverflow(long s) { 954 // assert (s & ABITS) >= RFULL; 955 if ((s & ABITS) == RFULL) { 956 if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) { 957 int r; long next; 958 if ((r = readerOverflow) > 0) { 959 readerOverflow = r - 1; 960 next = s; 961 } 962 else 963 next = s - RUNIT; 964 U.putLongVolatile(this, STATE, next); 965 return next; 966 } 967 } 968 else if ((LockSupport.nextSecondarySeed() & 969 OVERFLOW_YIELD_RATE) == 0) 970 Thread.yield(); 971 return 0L; 972 } 973 974 /** 975 * Wakes up the successor of h (normally whead). This is normally 976 * just h.next, but may require traversal from wtail if next 977 * pointers are lagging. This may fail to wake up an acquiring 978 * thread when one or more have been cancelled, but the cancel 979 * methods themselves provide extra safeguards to ensure liveness. 980 */ release(WNode h)981 private void release(WNode h) { 982 if (h != null) { 983 WNode q; Thread w; 984 U.compareAndSwapInt(h, WSTATUS, WAITING, 0); 985 if ((q = h.next) == null || q.status == CANCELLED) { 986 for (WNode t = wtail; t != null && t != h; t = t.prev) 987 if (t.status <= 0) 988 q = t; 989 } 990 if (q != null && (w = q.thread) != null) 991 U.unpark(w); 992 } 993 } 994 995 /** 996 * See above for explanation. 997 * 998 * @param interruptible true if should check interrupts and if so 999 * return INTERRUPTED 1000 * @param deadline if nonzero, the System.nanoTime value to timeout 1001 * at (and return zero) 1002 * @return next state, or INTERRUPTED 1003 */ acquireWrite(boolean interruptible, long deadline)1004 private long acquireWrite(boolean interruptible, long deadline) { 1005 WNode node = null, p; 1006 for (int spins = -1;;) { // spin while enqueuing 1007 long m, s, ns; 1008 if ((m = (s = state) & ABITS) == 0L) { 1009 if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) 1010 return ns; 1011 } 1012 else if (spins < 0) 1013 spins = (m == WBIT && wtail == whead) ? SPINS : 0; 1014 else if (spins > 0) { 1015 if (LockSupport.nextSecondarySeed() >= 0) 1016 --spins; 1017 } 1018 else if ((p = wtail) == null) { // initialize queue 1019 WNode hd = new WNode(WMODE, null); 1020 if (U.compareAndSwapObject(this, WHEAD, null, hd)) 1021 wtail = hd; 1022 } 1023 else if (node == null) 1024 node = new WNode(WMODE, p); 1025 else if (node.prev != p) 1026 node.prev = p; 1027 else if (U.compareAndSwapObject(this, WTAIL, p, node)) { 1028 p.next = node; 1029 break; 1030 } 1031 } 1032 1033 boolean wasInterrupted = false; 1034 for (int spins = -1;;) { 1035 WNode h, np, pp; int ps; 1036 if ((h = whead) == p) { 1037 if (spins < 0) 1038 spins = HEAD_SPINS; 1039 else if (spins < MAX_HEAD_SPINS) 1040 spins <<= 1; 1041 for (int k = spins;;) { // spin at head 1042 long s, ns; 1043 if (((s = state) & ABITS) == 0L) { 1044 if (U.compareAndSwapLong(this, STATE, s, 1045 ns = s + WBIT)) { 1046 whead = node; 1047 node.prev = null; 1048 if (wasInterrupted) 1049 Thread.currentThread().interrupt(); 1050 return ns; 1051 } 1052 } 1053 else if (LockSupport.nextSecondarySeed() >= 0 && 1054 --k <= 0) 1055 break; 1056 } 1057 } 1058 else if (h != null) { // help release stale waiters 1059 WNode c; Thread w; 1060 while ((c = h.cowait) != null) { 1061 if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) && 1062 (w = c.thread) != null) 1063 U.unpark(w); 1064 } 1065 } 1066 if (whead == h) { 1067 if ((np = node.prev) != p) { 1068 if (np != null) 1069 (p = np).next = node; // stale 1070 } 1071 else if ((ps = p.status) == 0) 1072 U.compareAndSwapInt(p, WSTATUS, 0, WAITING); 1073 else if (ps == CANCELLED) { 1074 if ((pp = p.prev) != null) { 1075 node.prev = pp; 1076 pp.next = node; 1077 } 1078 } 1079 else { 1080 long time; // 0 argument to park means no timeout 1081 if (deadline == 0L) 1082 time = 0L; 1083 else if ((time = deadline - System.nanoTime()) <= 0L) 1084 return cancelWaiter(node, node, false); 1085 Thread wt = Thread.currentThread(); 1086 U.putObject(wt, PARKBLOCKER, this); 1087 node.thread = wt; 1088 if (p.status < 0 && (p != h || (state & ABITS) != 0L) && 1089 whead == h && node.prev == p) 1090 U.park(false, time); // emulate LockSupport.park 1091 node.thread = null; 1092 U.putObject(wt, PARKBLOCKER, null); 1093 if (Thread.interrupted()) { 1094 if (interruptible) 1095 return cancelWaiter(node, node, true); 1096 wasInterrupted = true; 1097 } 1098 } 1099 } 1100 } 1101 } 1102 1103 /** 1104 * See above for explanation. 1105 * 1106 * @param interruptible true if should check interrupts and if so 1107 * return INTERRUPTED 1108 * @param deadline if nonzero, the System.nanoTime value to timeout 1109 * at (and return zero) 1110 * @return next state, or INTERRUPTED 1111 */ acquireRead(boolean interruptible, long deadline)1112 private long acquireRead(boolean interruptible, long deadline) { 1113 boolean wasInterrupted = false; 1114 WNode node = null, p; 1115 for (int spins = -1;;) { 1116 WNode h; 1117 if ((h = whead) == (p = wtail)) { 1118 for (long m, s, ns;;) { 1119 if ((m = (s = state) & ABITS) < RFULL ? 1120 U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) : 1121 (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) { 1122 if (wasInterrupted) 1123 Thread.currentThread().interrupt(); 1124 return ns; 1125 } 1126 else if (m >= WBIT) { 1127 if (spins > 0) { 1128 if (LockSupport.nextSecondarySeed() >= 0) 1129 --spins; 1130 } 1131 else { 1132 if (spins == 0) { 1133 WNode nh = whead, np = wtail; 1134 if ((nh == h && np == p) || (h = nh) != (p = np)) 1135 break; 1136 } 1137 spins = SPINS; 1138 } 1139 } 1140 } 1141 } 1142 if (p == null) { // initialize queue 1143 WNode hd = new WNode(WMODE, null); 1144 if (U.compareAndSwapObject(this, WHEAD, null, hd)) 1145 wtail = hd; 1146 } 1147 else if (node == null) 1148 node = new WNode(RMODE, p); 1149 else if (h == p || p.mode != RMODE) { 1150 if (node.prev != p) 1151 node.prev = p; 1152 else if (U.compareAndSwapObject(this, WTAIL, p, node)) { 1153 p.next = node; 1154 break; 1155 } 1156 } 1157 else if (!U.compareAndSwapObject(p, WCOWAIT, 1158 node.cowait = p.cowait, node)) 1159 node.cowait = null; 1160 else { 1161 for (;;) { 1162 WNode pp, c; Thread w; 1163 if ((h = whead) != null && (c = h.cowait) != null && 1164 U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) && 1165 (w = c.thread) != null) // help release 1166 U.unpark(w); 1167 if (h == (pp = p.prev) || h == p || pp == null) { 1168 long m, s, ns; 1169 do { 1170 if ((m = (s = state) & ABITS) < RFULL ? 1171 U.compareAndSwapLong(this, STATE, s, 1172 ns = s + RUNIT) : 1173 (m < WBIT && 1174 (ns = tryIncReaderOverflow(s)) != 0L)) { 1175 if (wasInterrupted) 1176 Thread.currentThread().interrupt(); 1177 return ns; 1178 } 1179 } while (m < WBIT); 1180 } 1181 if (whead == h && p.prev == pp) { 1182 long time; 1183 if (pp == null || h == p || p.status > 0) { 1184 node = null; // throw away 1185 break; 1186 } 1187 if (deadline == 0L) 1188 time = 0L; 1189 else if ((time = deadline - System.nanoTime()) <= 0L) { 1190 if (wasInterrupted) 1191 Thread.currentThread().interrupt(); 1192 return cancelWaiter(node, p, false); 1193 } 1194 Thread wt = Thread.currentThread(); 1195 U.putObject(wt, PARKBLOCKER, this); 1196 node.thread = wt; 1197 if ((h != pp || (state & ABITS) == WBIT) && 1198 whead == h && p.prev == pp) 1199 U.park(false, time); 1200 node.thread = null; 1201 U.putObject(wt, PARKBLOCKER, null); 1202 if (Thread.interrupted()) { 1203 if (interruptible) 1204 return cancelWaiter(node, p, true); 1205 wasInterrupted = true; 1206 } 1207 } 1208 } 1209 } 1210 } 1211 1212 for (int spins = -1;;) { 1213 WNode h, np, pp; int ps; 1214 if ((h = whead) == p) { 1215 if (spins < 0) 1216 spins = HEAD_SPINS; 1217 else if (spins < MAX_HEAD_SPINS) 1218 spins <<= 1; 1219 for (int k = spins;;) { // spin at head 1220 long m, s, ns; 1221 if ((m = (s = state) & ABITS) < RFULL ? 1222 U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) : 1223 (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) { 1224 WNode c; Thread w; 1225 whead = node; 1226 node.prev = null; 1227 while ((c = node.cowait) != null) { 1228 if (U.compareAndSwapObject(node, WCOWAIT, 1229 c, c.cowait) && 1230 (w = c.thread) != null) 1231 U.unpark(w); 1232 } 1233 if (wasInterrupted) 1234 Thread.currentThread().interrupt(); 1235 return ns; 1236 } 1237 else if (m >= WBIT && 1238 LockSupport.nextSecondarySeed() >= 0 && --k <= 0) 1239 break; 1240 } 1241 } 1242 else if (h != null) { 1243 WNode c; Thread w; 1244 while ((c = h.cowait) != null) { 1245 if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) && 1246 (w = c.thread) != null) 1247 U.unpark(w); 1248 } 1249 } 1250 if (whead == h) { 1251 if ((np = node.prev) != p) { 1252 if (np != null) 1253 (p = np).next = node; // stale 1254 } 1255 else if ((ps = p.status) == 0) 1256 U.compareAndSwapInt(p, WSTATUS, 0, WAITING); 1257 else if (ps == CANCELLED) { 1258 if ((pp = p.prev) != null) { 1259 node.prev = pp; 1260 pp.next = node; 1261 } 1262 } 1263 else { 1264 long time; 1265 if (deadline == 0L) 1266 time = 0L; 1267 else if ((time = deadline - System.nanoTime()) <= 0L) 1268 return cancelWaiter(node, node, false); 1269 Thread wt = Thread.currentThread(); 1270 U.putObject(wt, PARKBLOCKER, this); 1271 node.thread = wt; 1272 if (p.status < 0 && 1273 (p != h || (state & ABITS) == WBIT) && 1274 whead == h && node.prev == p) 1275 U.park(false, time); 1276 node.thread = null; 1277 U.putObject(wt, PARKBLOCKER, null); 1278 if (Thread.interrupted()) { 1279 if (interruptible) 1280 return cancelWaiter(node, node, true); 1281 wasInterrupted = true; 1282 } 1283 } 1284 } 1285 } 1286 } 1287 1288 /** 1289 * If node non-null, forces cancel status and unsplices it from 1290 * queue if possible and wakes up any cowaiters (of the node, or 1291 * group, as applicable), and in any case helps release current 1292 * first waiter if lock is free. (Calling with null arguments 1293 * serves as a conditional form of release, which is not currently 1294 * needed but may be needed under possible future cancellation 1295 * policies). This is a variant of cancellation methods in 1296 * AbstractQueuedSynchronizer (see its detailed explanation in AQS 1297 * internal documentation). 1298 * 1299 * @param node if nonnull, the waiter 1300 * @param group either node or the group node is cowaiting with 1301 * @param interrupted if already interrupted 1302 * @return INTERRUPTED if interrupted or Thread.interrupted, else zero 1303 */ cancelWaiter(WNode node, WNode group, boolean interrupted)1304 private long cancelWaiter(WNode node, WNode group, boolean interrupted) { 1305 if (node != null && group != null) { 1306 Thread w; 1307 node.status = CANCELLED; 1308 // unsplice cancelled nodes from group 1309 for (WNode p = group, q; (q = p.cowait) != null;) { 1310 if (q.status == CANCELLED) { 1311 U.compareAndSwapObject(p, WCOWAIT, q, q.cowait); 1312 p = group; // restart 1313 } 1314 else 1315 p = q; 1316 } 1317 if (group == node) { 1318 for (WNode r = group.cowait; r != null; r = r.cowait) { 1319 if ((w = r.thread) != null) 1320 U.unpark(w); // wake up uncancelled co-waiters 1321 } 1322 for (WNode pred = node.prev; pred != null; ) { // unsplice 1323 WNode succ, pp; // find valid successor 1324 while ((succ = node.next) == null || 1325 succ.status == CANCELLED) { 1326 WNode q = null; // find successor the slow way 1327 for (WNode t = wtail; t != null && t != node; t = t.prev) 1328 if (t.status != CANCELLED) 1329 q = t; // don't link if succ cancelled 1330 if (succ == q || // ensure accurate successor 1331 U.compareAndSwapObject(node, WNEXT, 1332 succ, succ = q)) { 1333 if (succ == null && node == wtail) 1334 U.compareAndSwapObject(this, WTAIL, node, pred); 1335 break; 1336 } 1337 } 1338 if (pred.next == node) // unsplice pred link 1339 U.compareAndSwapObject(pred, WNEXT, node, succ); 1340 if (succ != null && (w = succ.thread) != null) { 1341 succ.thread = null; 1342 U.unpark(w); // wake up succ to observe new pred 1343 } 1344 if (pred.status != CANCELLED || (pp = pred.prev) == null) 1345 break; 1346 node.prev = pp; // repeat if new pred wrong/cancelled 1347 U.compareAndSwapObject(pp, WNEXT, pred, succ); 1348 pred = pp; 1349 } 1350 } 1351 } 1352 WNode h; // Possibly release first waiter 1353 while ((h = whead) != null) { 1354 long s; WNode q; // similar to release() but check eligibility 1355 if ((q = h.next) == null || q.status == CANCELLED) { 1356 for (WNode t = wtail; t != null && t != h; t = t.prev) 1357 if (t.status <= 0) 1358 q = t; 1359 } 1360 if (h == whead) { 1361 if (q != null && h.status == 0 && 1362 ((s = state) & ABITS) != WBIT && // waiter is eligible 1363 (s == 0L || q.mode == RMODE)) 1364 release(h); 1365 break; 1366 } 1367 } 1368 return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L; 1369 } 1370 1371 // Unsafe mechanics 1372 private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 1373 private static final long STATE; 1374 private static final long WHEAD; 1375 private static final long WTAIL; 1376 private static final long WNEXT; 1377 private static final long WSTATUS; 1378 private static final long WCOWAIT; 1379 private static final long PARKBLOCKER; 1380 1381 static { 1382 try { 1383 STATE = U.objectFieldOffset 1384 (StampedLock.class.getDeclaredField("state")); 1385 WHEAD = U.objectFieldOffset 1386 (StampedLock.class.getDeclaredField("whead")); 1387 WTAIL = U.objectFieldOffset 1388 (StampedLock.class.getDeclaredField("wtail")); 1389 1390 WSTATUS = U.objectFieldOffset 1391 (WNode.class.getDeclaredField("status")); 1392 WNEXT = U.objectFieldOffset 1393 (WNode.class.getDeclaredField("next")); 1394 WCOWAIT = U.objectFieldOffset 1395 (WNode.class.getDeclaredField("cowait")); 1396 1397 PARKBLOCKER = U.objectFieldOffset 1398 (Thread.class.getDeclaredField("parkBlocker")); 1399 } catch (ReflectiveOperationException e) { 1400 throw new Error(e); 1401 } 1402 } 1403 } 1404