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