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