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