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