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
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 */
434 public StampedLock() {
435 state = ORIGIN;
436 }
437
438 private boolean casState(long expectedValue, long newValue) {
439 return STATE.compareAndSet(this, expectedValue, newValue);
440 }
441
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
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
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 */
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
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
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
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
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
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 */
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 */
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 */
657 private static long unlockWriteState(long s) {
658 return ((s += WBIT) == 0L) ? ORIGIN : s;
659 }
660
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
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
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
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 */
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 */
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 */
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
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
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 */
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 {
1079 public void lock() { readLock(); }
1080 public void lockInterruptibly() throws InterruptedException {
1081 readLockInterruptibly();
1082 }
1083 public boolean tryLock() { return tryReadLock() != 0L; }
1084 public boolean tryLock(long time, TimeUnit unit)
1085 throws InterruptedException {
1086 return tryReadLock(time, unit) != 0L;
1087 }
1088 public void unlock() { unstampedUnlockRead(); }
1089 public Condition newCondition() {
1090 throw new UnsupportedOperationException();
1091 }
1092 }
1093
1094 final class WriteLockView implements Lock {
1095 public void lock() { writeLock(); }
1096 public void lockInterruptibly() throws InterruptedException {
1097 writeLockInterruptibly();
1098 }
1099 public boolean tryLock() { return tryWriteLock() != 0L; }
1100 public boolean tryLock(long time, TimeUnit unit)
1101 throws InterruptedException {
1102 return tryWriteLock(time, unit) != 0L;
1103 }
1104 public void unlock() { unstampedUnlockWrite(); }
1105 public Condition newCondition() {
1106 throw new UnsupportedOperationException();
1107 }
1108 }
1109
1110 final class ReadWriteLockView implements ReadWriteLock {
1111 public Lock readLock() { return asReadLock(); }
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
1118 final void unstampedUnlockWrite() {
1119 long s;
1120 if (((s = state) & WBIT) == 0L)
1121 throw new IllegalMonitorStateException();
1122 unlockWriteInternal(s);
1123 }
1124
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
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 */
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 */
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 */
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 */
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 */
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 */
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 Error(e);
1618 }
1619 }
1620 }