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