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