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