--- jsr166/src/jsr166e/StampedLock.java 2012/10/13 23:05:13 1.12 +++ jsr166/src/jsr166e/StampedLock.java 2016/06/28 14:52:19 1.42 @@ -6,8 +6,10 @@ package jsr166e; -import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.TimeUnit; +import java.util.concurrent.locks.Lock; +import java.util.concurrent.locks.Condition; +import java.util.concurrent.locks.ReadWriteLock; /** * A capability-based lock with three modes for controlling read/write @@ -26,29 +28,30 @@ import java.util.concurrent.TimeUnit; * in method {@link #unlockWrite} to release the lock. Untimed and * timed versions of {@code tryWriteLock} are also provided. When * the lock is held in write mode, no read locks may be obtained, - * and all optimistic read validations will fail. + * and all optimistic read validations will fail. * *
StampedLocks are designed for use in a different (and generally - * narrower) range of contexts than most other locks: They are not - * reentrant, so locked bodies should not call other unknown methods - * that may try to re-acquire locks (although you may pass a stamp to - * other methods that can use or convert it). Unvalidated optimistic - * read sections should further not call methods that are not known to + *
StampedLocks are designed for use as internal utilities in the + * development of thread-safe components. Their use relies on + * knowledge of the internal properties of the data, objects, and + * methods they are protecting. They are not reentrant, so locked + * bodies should not call other unknown methods that may try to + * re-acquire locks (although you may pass a stamp to other methods + * that can use or convert it). The use of read lock modes relies on + * the associated code sections being side-effect-free. Unvalidated + * optimistic read sections cannot call methods that are not known to * tolerate potential inconsistencies. Stamps use finite * representations, and are not cryptographically secure (i.e., a * valid stamp may be guessable). Stamp values may recycle after (no @@ -77,10 +83,18 @@ import java.util.concurrent.TimeUnit; * locking. * *
The scheduling policy of StampedLock does not consistently - * prefer readers over writers or vice versa. A zero return from any - * "try" method for acquiring or converting locks does not carry any - * information about the state of the lock; a subsequent invocation - * may succeed. + * prefer readers over writers or vice versa. All "try" methods are + * best-effort and do not necessarily conform to any scheduling or + * fairness policy. A zero return from any "try" method for acquiring + * or converting locks does not carry any information about the state + * of the lock; a subsequent invocation may succeed. + * + *
Because it supports coordinated usage across multiple lock + * modes, this class does not directly implement the {@link Lock} or + * {@link ReadWriteLock} interfaces. However, a StampedLock may be + * viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link + * #asReadWriteLock()} in applications requiring only the associated + * set of functionality. * *
Sample Usage. The following illustrates some usage idioms
* in a class that maintains simple two-dimensional points. The sample
@@ -103,35 +117,19 @@ import java.util.concurrent.TimeUnit;
* }
* }
*
- * double distanceFromOriginV1() { // A read-only method
- * long stamp;
- * if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
- * double currentX = x;
- * double currentY = y;
- * if (sl.validate(stamp))
- * return Math.sqrt(currentX * currentX + currentY * currentY);
- * }
- * stamp = sl.readLock(); // fall back to read lock
- * try {
- * double currentX = x;
- * double currentY = y;
- * return Math.sqrt(currentX * currentX + currentY * currentY);
- * } finally {
- * sl.unlockRead(stamp);
- * }
- * }
- *
- * double distanceFromOriginV2() { // combines code paths
- * for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
- * double currentX, currentY;
- * try {
- * currentX = x;
- * currentY = y;
- * } finally {
- * if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
- * return Math.sqrt(currentX * currentX + currentY * currentY);
- * }
+ * double distanceFromOrigin() { // A read-only method
+ * long stamp = sl.tryOptimisticRead();
+ * double currentX = x, currentY = y;
+ * if (!sl.validate(stamp)) {
+ * stamp = sl.readLock();
+ * try {
+ * currentX = x;
+ * currentY = y;
+ * } finally {
+ * sl.unlockRead(stamp);
+ * }
* }
+ * return Math.sqrt(currentX * currentX + currentY * currentY);
* }
*
* void moveIfAtOrigin(double newX, double newY) { // upgrade
@@ -139,7 +137,7 @@ import java.util.concurrent.TimeUnit;
* long stamp = sl.readLock();
* try {
* while (x == 0.0 && y == 0.0) {
- * long ws = tryConvertToWriteLock(stamp);
+ * long ws = sl.tryConvertToWriteLock(stamp);
* if (ws != 0L) {
* stamp = ws;
* x = newX;
@@ -152,7 +150,7 @@ import java.util.concurrent.TimeUnit;
* }
* }
* } finally {
- * sl.unlock(stamp);
+ * sl.unlock(stamp);
* }
* }
* }}
@@ -169,10 +167,8 @@ public class StampedLock implements java
* http://www.lameter.com/gelato2005.pdf
* and elsewhere; see
* Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)
- * Ordered RW locks (see Shirako et al
+ * and Ordered RW locks (see Shirako et al
* http://dl.acm.org/citation.cfm?id=2312015)
- * and Phase-Fair locks (see Brandenburg & Anderson, especially
- * http://www.cs.unc.edu/~bbb/diss/).
*
* Conceptually, the primary state of the lock includes a sequence
* number that is odd when write-locked and even otherwise.
@@ -180,55 +176,50 @@ public class StampedLock implements java
* read-locked. The read count is ignored when validating
* "optimistic" seqlock-reader-style stamps. Because we must use
* a small finite number of bits (currently 7) for readers, a
- * supplementary reader overflow word is used when then number of
+ * supplementary reader overflow word is used when the number of
* readers exceeds the count field. We do this by treating the max
* reader count value (RBITS) as a spinlock protecting overflow
* updates.
*
- * Waiting readers and writers use different queues. The writer
- * queue is a modified form of CLH lock. (For discussion of CLH,
- * see the internal documentation of AbstractQueuedSynchronizer.)
- * The reader "queue" is a form of Treiber stack, that supports
- * simpler/faster operations because order within a queue doesn't
- * matter and all are signalled at once. However the sequence of
- * threads within the queue vs the current stamp does matter (see
- * Shirako et al) so each carries its incoming stamp value.
- * Waiting writers never need to track sequence values, so they
- * don't.
- *
- * These queue mechanics hardwire the scheduling policy. Ignoring
- * trylocks, cancellation, and spinning, they implement Phase-Fair
- * preferences:
- * 1. Unlocked writers prefer to signal waiting readers
- * 2. Fully unlocked readers prefer to signal waiting writers
- * 3. When read-locked and a waiting writer exists, the writer
- * is preferred to incoming readers
+ * Waiters use a modified form of CLH lock used in
+ * AbstractQueuedSynchronizer (see its internal documentation for
+ * a fuller account), where each node is tagged (field mode) as
+ * either a reader or writer. Sets of waiting readers are grouped
+ * (linked) under a common node (field cowait) so act as a single
+ * node with respect to most CLH mechanics. By virtue of the
+ * queue structure, wait nodes need not actually carry sequence
+ * numbers; we know each is greater than its predecessor. This
+ * simplifies the scheduling policy to a mainly-FIFO scheme that
+ * incorporates elements of Phase-Fair locks (see Brandenburg &
+ * Anderson, especially http://www.cs.unc.edu/~bbb/diss/). In
+ * particular, we use the phase-fair anti-barging rule: If an
+ * incoming reader arrives while read lock is held but there is a
+ * queued writer, this incoming reader is queued. (This rule is
+ * responsible for some of the complexity of method acquireRead,
+ * but without it, the lock becomes highly unfair.) Method release
+ * does not (and sometimes cannot) itself wake up cowaiters. This
+ * is done by the primary thread, but helped by any other threads
+ * with nothing better to do in methods acquireRead and
+ * acquireWrite.
*
* These rules apply to threads actually queued. All tryLock forms
* opportunistically try to acquire locks regardless of preference
- * rules, and so may "barge" their way in. Additionally, initial
- * phases of the await* methods (invoked from readLock() and
- * writeLock()) use controlled spins that have similar effect.
- * Phase-fair preferences may also be broken on cancellations due
- * to timeouts and interrupts. Rule #3 (incoming readers when a
- * waiting writer) is approximated with varying precision in
- * different contexts -- some checks do not account for
- * in-progress spins/signals, and others do not account for
- * cancellations.
- *
- * Controlled, randomized spinning is used in the two await
- * methods to reduce (increasingly expensive) context switching
- * while also avoiding sustained memory thrashing among many
- * threads. Both await methods use a similar spin strategy: If
- * the associated queue appears to be empty, then the thread
- * spin-waits up to SPINS times (where each iteration decreases
- * spin count with 50% probablility) before enqueing, and then, if
- * it is the first thread to be enqueued, spins again up to SPINS
- * times before blocking. If, upon wakening it fails to obtain
- * lock, and is still (or becomes) the first waiting thread (which
- * indicates that some other thread barged and obtained lock), it
- * escalates spins (up to MAX_HEAD_SPINS) to reduce the likelihood
- * of continually losing to barging threads.
+ * rules, and so may "barge" their way in. Randomized spinning is
+ * used in the acquire methods to reduce (increasingly expensive)
+ * context switching while also avoiding sustained memory
+ * thrashing among many threads. We limit spins to the head of
+ * queue. A thread spin-waits up to SPINS times (where each
+ * iteration decreases spin count with 50% probability) before
+ * blocking. If, upon wakening it fails to obtain lock, and is
+ * still (or becomes) the first waiting thread (which indicates
+ * that some other thread barged and obtained lock), it escalates
+ * spins (up to MAX_HEAD_SPINS) to reduce the likelihood of
+ * continually losing to barging threads.
+ *
+ * Nearly all of these mechanics are carried out in methods
+ * acquireWrite and acquireRead, that, as typical of such code,
+ * sprawl out because actions and retries rely on consistent sets
+ * of locally cached reads.
*
* As noted in Boehm's paper (above), sequence validation (mainly
* method validate()) requires stricter ordering rules than apply
@@ -248,20 +239,25 @@ public class StampedLock implements java
* be subject to future improvements.
*/
+ private static final long serialVersionUID = -6001602636862214147L;
+
/** Number of processors, for spin control */
private static final int NCPU = Runtime.getRuntime().availableProcessors();
- /** Maximum number of retries before blocking on acquisition */
- private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1;
+ /** Maximum number of retries before enqueuing on acquisition */
+ private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;
+
+ /** Maximum number of retries before blocking at head on acquisition */
+ private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;
/** Maximum number of retries before re-blocking */
- private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1;
+ private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0;
/** The period for yielding when waiting for overflow spinlock */
private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
/** The number of bits to use for reader count before overflowing */
- private static final int LG_READERS = 7;
+ private static final int LG_READERS = 7;
// Values for lock state and stamp operations
private static final long RUNIT = 1L;
@@ -274,43 +270,45 @@ public class StampedLock implements java
// Initial value for lock state; avoid failure value zero
private static final long ORIGIN = WBIT << 1;
- // Special value from cancelled await methods so caller can throw IE
+ // Special value from cancelled acquire methods so caller can throw IE
private static final long INTERRUPTED = 1L;
- // Values for writer status; order matters
+ // Values for node status; order matters
private static final int WAITING = -1;
private static final int CANCELLED = 1;
- /** Wait nodes for readers */
- static final class RNode {
- final long seq; // stamp value upon enqueue
- volatile Thread waiter; // null if no longer waiting
- volatile RNode next;
- RNode(long s, Thread w) { seq = s; waiter = w; }
- }
+ // Modes for nodes (int not boolean to allow arithmetic)
+ private static final int RMODE = 0;
+ private static final int WMODE = 1;
- /** Wait nodes for writers */
+ /** Wait nodes */
static final class WNode {
- volatile int status; // 0, WAITING, or CANCELLED
volatile WNode prev;
volatile WNode next;
- volatile Thread thread;
- WNode(Thread t, WNode p) { thread = t; prev = p; }
+ volatile WNode cowait; // list of linked readers
+ volatile Thread thread; // non-null while possibly parked
+ volatile int status; // 0, WAITING, or CANCELLED
+ final int mode; // RMODE or WMODE
+ WNode(int m, WNode p) { mode = m; prev = p; }
}
- /** Head of writer CLH queue */
+ /** Head of CLH queue */
private transient volatile WNode whead;
- /** Tail (last) of writer CLH queue */
+ /** Tail (last) of CLH queue */
private transient volatile WNode wtail;
- /** Head of read queue */
- private transient volatile RNode rhead;
- /** The state of the lock -- high bits hold sequence, low bits read count */
+
+ // views
+ transient ReadLockView readLockView;
+ transient WriteLockView writeLockView;
+ transient ReadWriteLockView readWriteLockView;
+
+ /** Lock sequence/state */
private transient volatile long state;
/** extra reader count when state read count saturated */
private transient int readerOverflow;
/**
- * Creates a new lock initially in unlocked state.
+ * Creates a new lock, initially in unlocked state.
*/
public StampedLock() {
state = ORIGIN;
@@ -323,31 +321,33 @@ public class StampedLock implements java
* @return a stamp that can be used to unlock or convert mode
*/
public long writeLock() {
- long s, next;
- if (((s = state) & ABITS) == 0L &&
- U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
- return next;
- return awaitWrite(false, 0L);
+ long s, next; // bypass acquireWrite in fully unlocked case only
+ return ((((s = state) & ABITS) == 0L &&
+ U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
+ next : acquireWrite(false, 0L));
}
/**
* Exclusively acquires the lock if it is immediately available.
*
* @return a stamp that can be used to unlock or convert mode,
- * or zero if the lock is not available.
+ * or zero if the lock is not available
*/
public long tryWriteLock() {
long s, next;
- if (((s = state) & ABITS) == 0L &&
- U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
- return next;
- return 0L;
+ return ((((s = state) & ABITS) == 0L &&
+ U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
+ next : 0L);
}
/**
* Exclusively acquires the lock if it is available within the
* given time and the current thread has not been interrupted.
+ * Behavior under timeout and interruption matches that specified
+ * for method {@link Lock#tryLock(long,TimeUnit)}.
*
+ * @param time the maximum time to wait for the lock
+ * @param unit the time unit of the {@code time} argument
* @return a stamp that can be used to unlock or convert mode,
* or zero if the lock is not available
* @throws InterruptedException if the current thread is interrupted
@@ -357,15 +357,14 @@ public class StampedLock implements java
throws InterruptedException {
long nanos = unit.toNanos(time);
if (!Thread.interrupted()) {
- long s, next, deadline;
- if (((s = state) & ABITS) == 0L &&
- U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
+ long next, deadline;
+ if ((next = tryWriteLock()) != 0L)
return next;
if (nanos <= 0L)
return 0L;
if ((deadline = System.nanoTime() + nanos) == 0L)
deadline = 1L;
- if ((next = awaitWrite(true, deadline)) != INTERRUPTED)
+ if ((next = acquireWrite(true, deadline)) != INTERRUPTED)
return next;
}
throw new InterruptedException();
@@ -374,20 +373,18 @@ public class StampedLock implements java
/**
* Exclusively acquires the lock, blocking if necessary
* until available or the current thread is interrupted.
+ * Behavior under interruption matches that specified
+ * for method {@link Lock#lockInterruptibly()}.
*
* @return a stamp that can be used to unlock or convert mode
* @throws InterruptedException if the current thread is interrupted
* before acquiring the lock
*/
public long writeLockInterruptibly() throws InterruptedException {
- if (!Thread.interrupted()) {
- long s, next;
- if (((s = state) & ABITS) == 0L &&
- U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
- return next;
- if ((next = awaitWrite(true, 0L)) != INTERRUPTED)
- return next;
- }
+ long next;
+ if (!Thread.interrupted() &&
+ (next = acquireWrite(true, 0L)) != INTERRUPTED)
+ return next;
throw new InterruptedException();
}
@@ -398,20 +395,10 @@ public class StampedLock implements java
* @return a stamp that can be used to unlock or convert mode
*/
public long readLock() {
- for (;;) {
- long s, m, next;
- if ((m = (s = state) & ABITS) == 0L ||
- (m < WBIT && whead == wtail)) {
- if (m < RFULL) {
- if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
- return next;
- }
- else if ((next = tryIncReaderOverflow(s)) != 0L)
- return next;
- }
- else
- return awaitRead(s, false, 0L);
- }
+ long s = state, next; // bypass acquireRead on common uncontended case
+ return ((whead == wtail && (s & ABITS) < RFULL &&
+ U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
+ next : acquireRead(false, 0L));
}
/**
@@ -437,7 +424,11 @@ public class StampedLock implements java
/**
* Non-exclusively acquires the lock if it is available within the
* given time and the current thread has not been interrupted.
+ * Behavior under timeout and interruption matches that specified
+ * for method {@link Lock#tryLock(long,TimeUnit)}.
*
+ * @param time the maximum time to wait for the lock
+ * @param unit the time unit of the {@code time} argument
* @return a stamp that can be used to unlock or convert mode,
* or zero if the lock is not available
* @throws InterruptedException if the current thread is interrupted
@@ -445,27 +436,23 @@ public class StampedLock implements java
*/
public long tryReadLock(long time, TimeUnit unit)
throws InterruptedException {
+ long s, m, next, deadline;
long nanos = unit.toNanos(time);
if (!Thread.interrupted()) {
- for (;;) {
- long s, m, next, deadline;
- if ((m = (s = state) & ABITS) == WBIT ||
- (m != 0L && whead != wtail)) {
- if (nanos <= 0L)
- return 0L;
- if ((deadline = System.nanoTime() + nanos) == 0L)
- deadline = 1L;
- if ((next = awaitRead(s, true, deadline)) != INTERRUPTED)
- return next;
- break;
- }
- else if (m < RFULL) {
+ if ((m = (s = state) & ABITS) != WBIT) {
+ if (m < RFULL) {
if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
return next;
}
else if ((next = tryIncReaderOverflow(s)) != 0L)
return next;
}
+ if (nanos <= 0L)
+ return 0L;
+ if ((deadline = System.nanoTime() + nanos) == 0L)
+ deadline = 1L;
+ if ((next = acquireRead(true, deadline)) != INTERRUPTED)
+ return next;
}
throw new InterruptedException();
}
@@ -473,29 +460,18 @@ public class StampedLock implements java
/**
* Non-exclusively acquires the lock, blocking if necessary
* until available or the current thread is interrupted.
+ * Behavior under interruption matches that specified
+ * for method {@link Lock#lockInterruptibly()}.
*
* @return a stamp that can be used to unlock or convert mode
* @throws InterruptedException if the current thread is interrupted
* before acquiring the lock
*/
public long readLockInterruptibly() throws InterruptedException {
- if (!Thread.interrupted()) {
- for (;;) {
- long s, next, m;
- if ((m = (s = state) & ABITS) == WBIT ||
- (m != 0L && whead != wtail)) {
- if ((next = awaitRead(s, true, 0L)) != INTERRUPTED)
- return next;
- break;
- }
- else if (m < RFULL) {
- if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
- return next;
- }
- else if ((next = tryIncReaderOverflow(s)) != 0L)
- return next;
- }
- }
+ long next;
+ if (!Thread.interrupted() &&
+ (next = acquireRead(true, 0L)) != INTERRUPTED)
+ return next;
throw new InterruptedException();
}
@@ -511,15 +487,19 @@ public class StampedLock implements java
}
/**
- * Returns true if the lock has not been exclusively held since
- * issuance of the given stamp. Always returns false if the stamp
- * is zero. Always returns true if the stamp represents a
- * currently held lock.
+ * Returns true if the lock has not been exclusively acquired
+ * since issuance of the given stamp. Always returns false if the
+ * stamp is zero. Always returns true if the stamp represents a
+ * currently held lock. Invoking this method with a value not
+ * obtained from {@link #tryOptimisticRead} or a locking method
+ * for this lock has no defined effect or result.
*
- * @return true if the lock has not been exclusively held since
- * issuance of the given stamp; else false
+ * @param stamp a stamp
+ * @return {@code true} if the lock has not been exclusively acquired
+ * since issuance of the given stamp; else false
*/
public boolean validate(long stamp) {
+ // See above about current use of getLongVolatile here
return (stamp & SBITS) == (U.getLongVolatile(this, STATE) & SBITS);
}
@@ -532,10 +512,12 @@ public class StampedLock implements java
* not match the current state of this lock
*/
public void unlockWrite(long stamp) {
+ WNode h;
if (state != stamp || (stamp & WBIT) == 0L)
throw new IllegalMonitorStateException();
state = (stamp += WBIT) == 0L ? ORIGIN : stamp;
- readerPrefSignal();
+ if ((h = whead) != null && h.status != 0)
+ release(h);
}
/**
@@ -547,25 +529,21 @@ public class StampedLock implements java
* not match the current state of this lock
*/
public void unlockRead(long stamp) {
- long s, m;
- if ((stamp & RBITS) != 0L) {
- while (((s = state) & SBITS) == (stamp & SBITS)) {
- if ((m = s & ABITS) == 0L)
+ long s, m; WNode h;
+ for (;;) {
+ if (((s = state) & SBITS) != (stamp & SBITS) ||
+ (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
+ throw new IllegalMonitorStateException();
+ if (m < RFULL) {
+ if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
+ if (m == RUNIT && (h = whead) != null && h.status != 0)
+ release(h);
break;
- else if (m < RFULL) {
- if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
- if (m == RUNIT)
- writerPrefSignal();
- return;
- }
}
- else if (m >= WBIT)
- break;
- else if (tryDecReaderOverflow(s) != 0L)
- return;
}
+ else if (tryDecReaderOverflow(s) != 0L)
+ break;
}
- throw new IllegalMonitorStateException();
}
/**
@@ -577,7 +555,7 @@ public class StampedLock implements java
* not match the current state of this lock
*/
public void unlock(long stamp) {
- long a = stamp & ABITS, m, s;
+ long a = stamp & ABITS, m, s; WNode h;
while (((s = state) & SBITS) == (stamp & SBITS)) {
if ((m = s & ABITS) == 0L)
break;
@@ -585,15 +563,16 @@ public class StampedLock implements java
if (a != m)
break;
state = (s += WBIT) == 0L ? ORIGIN : s;
- readerPrefSignal();
+ if ((h = whead) != null && h.status != 0)
+ release(h);
return;
}
else if (a == 0L || a >= WBIT)
break;
else if (m < RFULL) {
if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
- if (m == RUNIT)
- writerPrefSignal();
+ if (m == RUNIT && (h = whead) != null && h.status != 0)
+ release(h);
return;
}
}
@@ -604,7 +583,7 @@ public class StampedLock implements java
}
/**
- * If the lock state matches the given stamp then performs one of
+ * If the lock state matches the given stamp, performs one of
* the following actions. If the stamp represents holding a write
* lock, returns it. Or, if a read lock, if the write lock is
* available, releases the read lock and returns a write stamp.
@@ -629,7 +608,7 @@ public class StampedLock implements java
break;
return stamp;
}
- else if (m == RUNIT && a != 0L && a < WBIT) {
+ else if (m == RUNIT && a != 0L) {
if (U.compareAndSwapLong(this, STATE, s,
next = s - RUNIT + WBIT))
return next;
@@ -641,7 +620,7 @@ public class StampedLock implements java
}
/**
- * If the lock state matches the given stamp then performs one of
+ * If the lock state matches the given stamp, performs one of
* the following actions. If the stamp represents holding a write
* lock, releases it and obtains a read lock. Or, if a read lock,
* returns it. Or, if an optimistic read, acquires a read lock and
@@ -652,7 +631,7 @@ public class StampedLock implements java
* @return a valid read stamp, or zero on failure
*/
public long tryConvertToReadLock(long stamp) {
- long a = stamp & ABITS, m, s, next;
+ long a = stamp & ABITS, m, s, next; WNode h;
while (((s = state) & SBITS) == (stamp & SBITS)) {
if ((m = s & ABITS) == 0L) {
if (a != 0L)
@@ -667,8 +646,9 @@ public class StampedLock implements java
else if (m == WBIT) {
if (a != m)
break;
- next = state = s + (WBIT + RUNIT);
- readerPrefSignal();
+ state = next = s + (WBIT + RUNIT);
+ if ((h = whead) != null && h.status != 0)
+ release(h);
return next;
}
else if (a != 0L && a < WBIT)
@@ -690,9 +670,11 @@ public class StampedLock implements java
* @return a valid optimistic read stamp, or zero on failure
*/
public long tryConvertToOptimisticRead(long stamp) {
- long a = stamp & ABITS, m, s, next;
- while (((s = U.getLongVolatile(this, STATE)) &
- SBITS) == (stamp & SBITS)) {
+ long a = stamp & ABITS, m, s, next; WNode h;
+ for (;;) {
+ s = U.getLongVolatile(this, STATE); // see above
+ if (((s = state) & SBITS) != (stamp & SBITS))
+ break;
if ((m = s & ABITS) == 0L) {
if (a != 0L)
break;
@@ -701,16 +683,17 @@ public class StampedLock implements java
else if (m == WBIT) {
if (a != m)
break;
- next = state = (s += WBIT) == 0L ? ORIGIN : s;
- readerPrefSignal();
+ state = next = (s += WBIT) == 0L ? ORIGIN : s;
+ if ((h = whead) != null && h.status != 0)
+ release(h);
return next;
}
else if (a == 0L || a >= WBIT)
break;
else if (m < RFULL) {
if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {
- if (m == RUNIT)
- writerPrefSignal();
+ if (m == RUNIT && (h = whead) != null && h.status != 0)
+ release(h);
return next & SBITS;
}
}
@@ -725,13 +708,14 @@ public class StampedLock implements java
* stamp value. This method may be useful for recovery after
* errors.
*
- * @return true if the lock was held, else false
+ * @return {@code true} if the lock was held, else false
*/
public boolean tryUnlockWrite() {
- long s;
+ long s; WNode h;
if (((s = state) & WBIT) != 0L) {
state = (s += WBIT) == 0L ? ORIGIN : s;
- readerPrefSignal();
+ if ((h = whead) != null && h.status != 0)
+ release(h);
return true;
}
return false;
@@ -742,15 +726,15 @@ public class StampedLock implements java
* requiring a stamp value. This method may be useful for recovery
* after errors.
*
- * @return true if the read lock was held, else false
+ * @return {@code true} if the read lock was held, else false
*/
public boolean tryUnlockRead() {
- long s, m;
+ long s, m; WNode h;
while ((m = (s = state) & ABITS) != 0L && m < WBIT) {
if (m < RFULL) {
if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
- if (m == RUNIT)
- writerPrefSignal();
+ if (m == RUNIT && (h = whead) != null && h.status != 0)
+ release(h);
return true;
}
}
@@ -760,23 +744,178 @@ public class StampedLock implements java
return false;
}
+ // status monitoring methods
+
+ /**
+ * Returns combined state-held and overflow read count for given
+ * state s.
+ */
+ private int getReadLockCount(long s) {
+ long readers;
+ if ((readers = s & RBITS) >= RFULL)
+ readers = RFULL + readerOverflow;
+ return (int) readers;
+ }
+
/**
- * Returns true if the lock is currently held exclusively.
+ * Returns {@code true} if the lock is currently held exclusively.
*
- * @return true if the lock is currently held exclusively
+ * @return {@code true} if the lock is currently held exclusively
*/
public boolean isWriteLocked() {
return (state & WBIT) != 0L;
}
/**
- * Returns true if the lock is currently held non-exclusively.
+ * Returns {@code true} if the lock is currently held non-exclusively.
*
- * @return true if the lock is currently held non-exclusively
+ * @return {@code true} if the lock is currently held non-exclusively
*/
public boolean isReadLocked() {
- long m;
- return (m = state & ABITS) > 0L && m < WBIT;
+ return (state & RBITS) != 0L;
+ }
+
+ /**
+ * Queries the number of read locks held for this lock. This
+ * method is designed for use in monitoring system state, not for
+ * synchronization control.
+ * @return the number of read locks held
+ */
+ public int getReadLockCount() {
+ return getReadLockCount(state);
+ }
+
+ /**
+ * Returns a string identifying this lock, as well as its lock
+ * state. The state, in brackets, includes the String {@code
+ * "Unlocked"} or the String {@code "Write-locked"} or the String
+ * {@code "Read-locks:"} followed by the current number of
+ * read-locks held.
+ *
+ * @return a string identifying this lock, as well as its lock state
+ */
+ public String toString() {
+ long s = state;
+ return super.toString() +
+ ((s & ABITS) == 0L ? "[Unlocked]" :
+ (s & WBIT) != 0L ? "[Write-locked]" :
+ "[Read-locks:" + getReadLockCount(s) + "]");
+ }
+
+ // views
+
+ /**
+ * Returns a plain {@link Lock} view of this StampedLock in which
+ * the {@link Lock#lock} method is mapped to {@link #readLock},
+ * and similarly for other methods. The returned Lock does not
+ * support a {@link Condition}; method {@link
+ * Lock#newCondition()} throws {@code
+ * UnsupportedOperationException}.
+ *
+ * @return the lock
+ */
+ public Lock asReadLock() {
+ ReadLockView v;
+ return ((v = readLockView) != null ? v :
+ (readLockView = new ReadLockView()));
+ }
+
+ /**
+ * Returns a plain {@link Lock} view of this StampedLock in which
+ * the {@link Lock#lock} method is mapped to {@link #writeLock},
+ * and similarly for other methods. The returned Lock does not
+ * support a {@link Condition}; method {@link
+ * Lock#newCondition()} throws {@code
+ * UnsupportedOperationException}.
+ *
+ * @return the lock
+ */
+ public Lock asWriteLock() {
+ WriteLockView v;
+ return ((v = writeLockView) != null ? v :
+ (writeLockView = new WriteLockView()));
+ }
+
+ /**
+ * Returns a {@link ReadWriteLock} view of this StampedLock in
+ * which the {@link ReadWriteLock#readLock()} method is mapped to
+ * {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to
+ * {@link #asWriteLock()}.
+ *
+ * @return the lock
+ */
+ public ReadWriteLock asReadWriteLock() {
+ ReadWriteLockView v;
+ return ((v = readWriteLockView) != null ? v :
+ (readWriteLockView = new ReadWriteLockView()));
+ }
+
+ // view classes
+
+ final class ReadLockView implements Lock {
+ public void lock() { readLock(); }
+ public void lockInterruptibly() throws InterruptedException {
+ readLockInterruptibly();
+ }
+ public boolean tryLock() { return tryReadLock() != 0L; }
+ public boolean tryLock(long time, TimeUnit unit)
+ throws InterruptedException {
+ return tryReadLock(time, unit) != 0L;
+ }
+ public void unlock() { unstampedUnlockRead(); }
+ public Condition newCondition() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ final class WriteLockView implements Lock {
+ public void lock() { writeLock(); }
+ public void lockInterruptibly() throws InterruptedException {
+ writeLockInterruptibly();
+ }
+ public boolean tryLock() { return tryWriteLock() != 0L; }
+ public boolean tryLock(long time, TimeUnit unit)
+ throws InterruptedException {
+ return tryWriteLock(time, unit) != 0L;
+ }
+ public void unlock() { unstampedUnlockWrite(); }
+ public Condition newCondition() {
+ throw new UnsupportedOperationException();
+ }
+ }
+
+ final class ReadWriteLockView implements ReadWriteLock {
+ public Lock readLock() { return asReadLock(); }
+ public Lock writeLock() { return asWriteLock(); }
+ }
+
+ // Unlock methods without stamp argument checks for view classes.
+ // Needed because view-class lock methods throw away stamps.
+
+ final void unstampedUnlockWrite() {
+ WNode h; long s;
+ if (((s = state) & WBIT) == 0L)
+ throw new IllegalMonitorStateException();
+ state = (s += WBIT) == 0L ? ORIGIN : s;
+ if ((h = whead) != null && h.status != 0)
+ release(h);
+ }
+
+ final void unstampedUnlockRead() {
+ for (;;) {
+ long s, m; WNode h;
+ if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
+ throw new IllegalMonitorStateException();
+ else if (m < RFULL) {
+ if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
+ if (m == RUNIT && (h = whead) != null && h.status != 0)
+ release(h);
+ break;
+ }
+ }
+ else if (tryDecReaderOverflow(s) != 0L)
+ break;
+ }
}
private void readObject(java.io.ObjectInputStream s)
@@ -792,10 +931,11 @@ public class StampedLock implements java
* access bits value to RBITS, indicating hold of spinlock,
* then updating, then releasing.
*
- * @param stamp, assumed that (stamp & ABITS) >= RFULL
+ * @param s a reader overflow stamp: (s & ABITS) >= RFULL
* @return new stamp on success, else zero
*/
private long tryIncReaderOverflow(long s) {
+ // assert (s & ABITS) >= RFULL;
if ((s & ABITS) == RFULL) {
if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
++readerOverflow;
@@ -812,10 +952,11 @@ public class StampedLock implements java
/**
* Tries to decrement readerOverflow.
*
- * @param stamp, assumed that (stamp & ABITS) >= RFULL
+ * @param s a reader overflow stamp: (s & ABITS) >= RFULL
* @return new stamp on success, else zero
*/
private long tryDecReaderOverflow(long s) {
+ // assert (s & ABITS) >= RFULL;
if ((s & ABITS) == RFULL) {
if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
int r; long next;
@@ -835,59 +976,18 @@ public class StampedLock implements java
return 0L;
}
- /*
- * The two versions of signal implement the phase-fair policy.
- * They include almost the same code, but repacked in different
- * ways. Integrating the policy with the mechanics eliminates
- * state rechecks that would be needed with separate reader and
- * writer signal methods. Both methods assume that they are
- * called when the lock is last known to be available, and
- * continue until the lock is unavailable, or at least one thread
- * is signalled, or there are no more waiting threads. Signalling
- * a reader entails popping (CASing) from rhead and unparking
- * unless the thread already cancelled (indicated by a null waiter
- * field). Signalling a writer requires finding the first node,
- * i.e., the successor of whead. This is normally just head.next,
- * but may require traversal from wtail if next pointers are
- * lagging. These methods may fail to wake up an acquiring thread
- * when one or more have been cancelled, but the cancel methods
- * themselves provide extra safeguards to ensure liveness.
- */
-
- private void readerPrefSignal() {
- boolean readers = false;
- RNode p; WNode h, q; long s; Thread w;
- while ((p = rhead) != null) {
- if (((s = state) & WBIT) != 0L)
- return;
- if (p.seq == (s & SBITS))
- break;
- readers = true;
- if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
- (w = p.waiter) != null &&
- U.compareAndSwapObject(p, WAITER, w, null))
- U.unpark(w);
- }
- if (!readers && (state & ABITS) == 0L &&
- (h = whead) != null && h.status != 0) {
- U.compareAndSwapInt(h, STATUS, WAITING, 0);
- if ((q = h.next) == null || q.status == CANCELLED) {
- q = null;
- for (WNode t = wtail; t != null && t != h; t = t.prev)
- if (t.status <= 0)
- q = t;
- }
- if (q != null && (w = q.thread) != null)
- U.unpark(w);
- }
- }
-
- private void writerPrefSignal() {
- RNode p; WNode h, q; long s; Thread w;
- if ((h = whead) != null && h.status != 0) {
- U.compareAndSwapInt(h, STATUS, WAITING, 0);
+ /**
+ * Wakes up the successor of h (normally whead). This is normally
+ * just h.next, but may require traversal from wtail if next
+ * pointers are lagging. This may fail to wake up an acquiring
+ * thread when one or more have been cancelled, but the cancel
+ * methods themselves provide extra safeguards to ensure liveness.
+ */
+ private void release(WNode h) {
+ if (h != null) {
+ WNode q; Thread w;
+ U.compareAndSwapInt(h, WSTATUS, WAITING, 0);
if ((q = h.next) == null || q.status == CANCELLED) {
- q = null;
for (WNode t = wtail; t != null && t != h; t = t.prev)
if (t.status <= 0)
q = t;
@@ -895,290 +995,390 @@ public class StampedLock implements java
if (q != null && (w = q.thread) != null)
U.unpark(w);
}
- else {
- while ((p = rhead) != null && ((s = state) & WBIT) == 0L &&
- p.seq != (s & SBITS)) {
- if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
- (w = p.waiter) != null &&
- U.compareAndSwapObject(p, WAITER, w, null))
- U.unpark(w);
- }
- }
- }
-
- /**
- * RNG for local spins. The first call from await{Read,Write}
- * produces a thread-local value. Unless zero, subsequent calls
- * use an xorShift to further reduce memory traffic.
- */
- private static int nextRandom(int r) {
- if (r == 0)
- return ThreadLocalRandom.current().nextInt();
- r ^= r << 1; // xorshift
- r ^= r >>> 3;
- r ^= r << 10;
- return r;
}
/**
- * Possibly spins trying to obtain write lock, then enqueues and
- * blocks while not head of write queue or cannot acquire lock,
- * possibly spinning when at head; cancelling on timeout or
- * interrupt.
+ * See above for explanation.
*
* @param interruptible true if should check interrupts and if so
* return INTERRUPTED
* @param deadline if nonzero, the System.nanoTime value to timeout
* at (and return zero)
+ * @return next state, or INTERRUPTED
*/
- private long awaitWrite(boolean interruptible, long deadline) {
- WNode node = null;
- for (int r = 0, spins = -1;;) {
- WNode p; long s, next;
- if (((s = state) & ABITS) == 0L) {
- if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
- return next;
+ private long acquireWrite(boolean interruptible, long deadline) {
+ WNode node = null, p;
+ for (int spins = -1;;) { // spin while enqueuing
+ long m, s, ns;
+ if ((m = (s = state) & ABITS) == 0L) {
+ if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
+ return ns;
}
else if (spins < 0)
- spins = whead == wtail ? SPINS : 0;
+ spins = (m == WBIT && wtail == whead) ? SPINS : 0;
else if (spins > 0) {
- if ((r = nextRandom(r)) >= 0)
+ if (ThreadLocalRandom.current().nextInt() >= 0)
--spins;
}
else if ((p = wtail) == null) { // initialize queue
- if (U.compareAndSwapObject(this, WHEAD, null,
- new WNode(null, null)))
- wtail = whead;
+ WNode hd = new WNode(WMODE, null);
+ if (U.compareAndSwapObject(this, WHEAD, null, hd))
+ wtail = hd;
}
else if (node == null)
- node = new WNode(Thread.currentThread(), p);
+ node = new WNode(WMODE, p);
else if (node.prev != p)
node.prev = p;
else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
p.next = node;
- for (int headSpins = SPINS;;) {
- WNode np; int ps;
- if ((np = node.prev) != p && np != null &&
- (p = np).next != node)
- p.next = node; // stale
- if (p == whead) {
- for (int k = headSpins;;) {
- if (((s = state) & ABITS) == 0L) {
- if (U.compareAndSwapLong(this, STATE,
- s, next = s + WBIT)) {
- whead = node;
- node.thread = null;
- node.prev = null;
- return next;
- }
- break;
- }
- if ((r = nextRandom(r)) >= 0 && --k <= 0)
- break;
- }
- if (headSpins < MAX_HEAD_SPINS)
- headSpins <<= 1;
- }
- if ((ps = p.status) == 0)
- U.compareAndSwapInt(p, STATUS, 0, WAITING);
- else if (ps == CANCELLED)
- node.prev = p.prev;
- else {
- long time; // 0 argument to park means no timeout
- if (deadline == 0L)
- time = 0L;
- else if ((time = deadline - System.nanoTime()) <= 0L)
- return cancelWriter(node, false);
- if (node.prev == p && p.status == WAITING &&
- (p != whead || (state & WBIT) != 0L)) { // recheck
- U.park(false, time);
- if (interruptible && Thread.interrupted())
- return cancelWriter(node, true);
+ break;
+ }
+ }
+
+ for (int spins = -1;;) {
+ WNode h, np, pp; int ps;
+ if ((h = whead) == p) {
+ if (spins < 0)
+ spins = HEAD_SPINS;
+ else if (spins < MAX_HEAD_SPINS)
+ spins <<= 1;
+ for (int k = spins;;) { // spin at head
+ long s, ns;
+ if (((s = state) & ABITS) == 0L) {
+ if (U.compareAndSwapLong(this, STATE, s,
+ ns = s + WBIT)) {
+ whead = node;
+ node.prev = null;
+ return ns;
}
}
+ else if (ThreadLocalRandom.current().nextInt() >= 0 &&
+ --k <= 0)
+ break;
}
}
- }
- }
-
- /**
- * If node non-null, forces cancel status and unsplices from queue
- * if possible. This is a streamlined variant of cancellation
- * methods in AbstractQueuedSynchronizer that includes a detailed
- * explanation.
- */
- private long cancelWriter(WNode node, boolean interrupted) {
- WNode pred;
- if (node != null && (pred = node.prev) != null) {
- WNode pp;
- node.thread = null;
- while (pred.status == CANCELLED && (pp = pred.prev) != null)
- pred = node.prev = pp;
- WNode predNext = pred.next;
- node.status = CANCELLED;
- if (predNext != null) {
- Thread w;
- WNode succ = node.next;
- if (succ == null || succ.status == CANCELLED) {
- succ = null;
- for (WNode t = wtail; t != null && t != node; t = t.prev)
- if (t.status <= 0)
- succ = t;
- if (succ == null && node == wtail)
- U.compareAndSwapObject(this, WTAIL, node, pred);
- }
- U.compareAndSwapObject(pred, WNEXT, predNext, succ);
- if (succ != null && (w = succ.thread) != null)
- U.unpark(w);
+ else if (h != null) { // help release stale waiters
+ WNode c; Thread w;
+ while ((c = h.cowait) != null) {
+ if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
+ (w = c.thread) != null)
+ U.unpark(w);
+ }
+ }
+ if (whead == h) {
+ if ((np = node.prev) != p) {
+ if (np != null)
+ (p = np).next = node; // stale
+ }
+ else if ((ps = p.status) == 0)
+ U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
+ else if (ps == CANCELLED) {
+ if ((pp = p.prev) != null) {
+ node.prev = pp;
+ pp.next = node;
+ }
+ }
+ else {
+ long time; // 0 argument to park means no timeout
+ if (deadline == 0L)
+ time = 0L;
+ else if ((time = deadline - System.nanoTime()) <= 0L)
+ return cancelWaiter(node, node, false);
+ Thread wt = Thread.currentThread();
+ U.putObject(wt, PARKBLOCKER, this);
+ node.thread = wt;
+ if (p.status < 0 && (p != h || (state & ABITS) != 0L) &&
+ whead == h && node.prev == p)
+ U.park(false, time); // emulate LockSupport.park
+ node.thread = null;
+ U.putObject(wt, PARKBLOCKER, null);
+ if (interruptible && Thread.interrupted())
+ return cancelWaiter(node, node, true);
+ }
}
}
- writerPrefSignal();
- return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
}
/**
- * Waits for read lock or timeout or interrupt. The form of
- * awaitRead differs from awaitWrite mainly because it must
- * restart (with a new wait node) if the thread was unqueued and
- * unparked but could not the obtain lock. We also need to help
- * with preference rules by not trying to acquire the lock before
- * enqueuing if there is a known waiting writer, but also helping
- * to release those threads that are still queued from the last
- * release.
- */
- private long awaitRead(long stamp, boolean interruptible, long deadline) {
- long seq = stamp & SBITS;
- RNode node = null;
- boolean queued = false;
- for (int r = 0, headSpins = SPINS, spins = -1;;) {
- long s, m, next; RNode p; WNode wh; Thread w;
- if ((m = (s = state) & ABITS) != WBIT &&
- ((s & SBITS) != seq || (wh = whead) == null ||
- wh.status == 0)) {
- if (m < RFULL ?
- U.compareAndSwapLong(this, STATE, s, next = s + RUNIT) :
- (next = tryIncReaderOverflow(s)) != 0L) {
- if (node != null && (w = node.waiter) != null)
- U.compareAndSwapObject(node, WAITER, w, null);
- if ((p = rhead) != null && (s & SBITS) != p.seq &&
- U.compareAndSwapObject(this, RHEAD, p, p.next) &&
- (w = p.waiter) != null &&
- U.compareAndSwapObject(p, WAITER, w, null))
- U.unpark(w); // help signal other waiters
- return next;
+ * See above for explanation.
+ *
+ * @param interruptible true if should check interrupts and if so
+ * return INTERRUPTED
+ * @param deadline if nonzero, the System.nanoTime value to timeout
+ * at (and return zero)
+ * @return next state, or INTERRUPTED
+ */
+ private long acquireRead(boolean interruptible, long deadline) {
+ WNode node = null, p;
+ for (int spins = -1;;) {
+ WNode h;
+ if ((h = whead) == (p = wtail)) {
+ for (long m, s, ns;;) {
+ if ((m = (s = state) & ABITS) < RFULL ?
+ U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
+ (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L))
+ return ns;
+ else if (m >= WBIT) {
+ if (spins > 0) {
+ if (ThreadLocalRandom.current().nextInt() >= 0)
+ --spins;
+ }
+ else {
+ if (spins == 0) {
+ WNode nh = whead, np = wtail;
+ if ((nh == h && np == p) || (h = nh) != (p = np))
+ break;
+ }
+ spins = SPINS;
+ }
+ }
}
}
- else if (m != WBIT && (p = rhead) != null &&
- (s & SBITS) != p.seq) { // help release old readers
- if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
- (w = p.waiter) != null &&
- U.compareAndSwapObject(p, WAITER, w, null))
- U.unpark(w);
- }
- else if (queued && node != null && node.waiter == null) {
- node = null; // restart
- queued = false;
- spins = -1;
- }
- else if (spins < 0) {
- if (rhead != node)
- spins = 0;
- else if ((spins = headSpins) < MAX_HEAD_SPINS && node != null)
- headSpins <<= 1;
- }
- else if (spins > 0) {
- if ((r = nextRandom(r)) >= 0)
- --spins;
+ if (p == null) { // initialize queue
+ WNode hd = new WNode(WMODE, null);
+ if (U.compareAndSwapObject(this, WHEAD, null, hd))
+ wtail = hd;
}
else if (node == null)
- node = new RNode(seq, Thread.currentThread());
- else if (!queued) {
- if (queued = U.compareAndSwapObject(this, RHEAD,
- node.next = rhead, node))
- spins = -1;
+ node = new WNode(RMODE, p);
+ else if (h == p || p.mode != RMODE) {
+ if (node.prev != p)
+ node.prev = p;
+ else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
+ p.next = node;
+ break;
+ }
}
+ else if (!U.compareAndSwapObject(p, WCOWAIT,
+ node.cowait = p.cowait, node))
+ node.cowait = null;
else {
- long time;
- if (deadline == 0L)
- time = 0L;
- else if ((time = deadline - System.nanoTime()) <= 0L)
- return cancelReader(node, false);
- if ((state & WBIT) != 0L && node.waiter != null) { // recheck
- U.park(false, time);
- if (interruptible && Thread.interrupted())
- return cancelReader(node, true);
+ for (;;) {
+ WNode pp, c; Thread w;
+ if ((h = whead) != null && (c = h.cowait) != null &&
+ U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
+ (w = c.thread) != null) // help release
+ U.unpark(w);
+ if (h == (pp = p.prev) || h == p || pp == null) {
+ long m, s, ns;
+ do {
+ if ((m = (s = state) & ABITS) < RFULL ?
+ U.compareAndSwapLong(this, STATE, s,
+ ns = s + RUNIT) :
+ (m < WBIT &&
+ (ns = tryIncReaderOverflow(s)) != 0L))
+ return ns;
+ } while (m < WBIT);
+ }
+ if (whead == h && p.prev == pp) {
+ long time;
+ if (pp == null || h == p || p.status > 0) {
+ node = null; // throw away
+ break;
+ }
+ if (deadline == 0L)
+ time = 0L;
+ else if ((time = deadline - System.nanoTime()) <= 0L)
+ return cancelWaiter(node, p, false);
+ Thread wt = Thread.currentThread();
+ U.putObject(wt, PARKBLOCKER, this);
+ node.thread = wt;
+ if ((h != pp || (state & ABITS) == WBIT) &&
+ whead == h && p.prev == pp)
+ U.park(false, time);
+ node.thread = null;
+ U.putObject(wt, PARKBLOCKER, null);
+ if (interruptible && Thread.interrupted())
+ return cancelWaiter(node, p, true);
+ }
}
}
}
- }
- /**
- * If node non-null, forces cancel status and unsplices from queue
- * if possible, by traversing entire queue looking for cancelled
- * nodes.
- */
- private long cancelReader(RNode node, boolean interrupted) {
- Thread w;
- if (node != null && (w = node.waiter) != null &&
- U.compareAndSwapObject(node, WAITER, w, null)) {
- for (RNode pred = null, p = rhead; p != null;) {
- RNode q = p.next;
- if (p.waiter == null) {
- if (pred == null) {
- U.compareAndSwapObject(this, RHEAD, p, q);
- p = rhead;
+ for (int spins = -1;;) {
+ WNode h, np, pp; int ps;
+ if ((h = whead) == p) {
+ if (spins < 0)
+ spins = HEAD_SPINS;
+ else if (spins < MAX_HEAD_SPINS)
+ spins <<= 1;
+ for (int k = spins;;) { // spin at head
+ long m, s, ns;
+ if ((m = (s = state) & ABITS) < RFULL ?
+ U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
+ (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
+ WNode c; Thread w;
+ whead = node;
+ node.prev = null;
+ while ((c = node.cowait) != null) {
+ if (U.compareAndSwapObject(node, WCOWAIT,
+ c, c.cowait) &&
+ (w = c.thread) != null)
+ U.unpark(w);
+ }
+ return ns;
}
- else {
- U.compareAndSwapObject(pred, RNEXT, p, q);
- p = pred.next;
+ else if (m >= WBIT &&
+ ThreadLocalRandom.current().nextInt() >= 0 && --k <= 0)
+ break;
+ }
+ }
+ else if (h != null) {
+ WNode c; Thread w;
+ while ((c = h.cowait) != null) {
+ if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
+ (w = c.thread) != null)
+ U.unpark(w);
+ }
+ }
+ if (whead == h) {
+ if ((np = node.prev) != p) {
+ if (np != null)
+ (p = np).next = node; // stale
+ }
+ else if ((ps = p.status) == 0)
+ U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
+ else if (ps == CANCELLED) {
+ if ((pp = p.prev) != null) {
+ node.prev = pp;
+ pp.next = node;
}
}
else {
- pred = p;
+ long time;
+ if (deadline == 0L)
+ time = 0L;
+ else if ((time = deadline - System.nanoTime()) <= 0L)
+ return cancelWaiter(node, node, false);
+ Thread wt = Thread.currentThread();
+ U.putObject(wt, PARKBLOCKER, this);
+ node.thread = wt;
+ if (p.status < 0 &&
+ (p != h || (state & ABITS) == WBIT) &&
+ whead == h && node.prev == p)
+ U.park(false, time);
+ node.thread = null;
+ U.putObject(wt, PARKBLOCKER, null);
+ if (interruptible && Thread.interrupted())
+ return cancelWaiter(node, node, true);
+ }
+ }
+ }
+ }
+
+ /**
+ * If node non-null, forces cancel status and unsplices it from
+ * queue if possible and wakes up any cowaiters (of the node, or
+ * group, as applicable), and in any case helps release current
+ * first waiter if lock is free. (Calling with null arguments
+ * serves as a conditional form of release, which is not currently
+ * needed but may be needed under possible future cancellation
+ * policies). This is a variant of cancellation methods in
+ * AbstractQueuedSynchronizer (see its detailed explanation in AQS
+ * internal documentation).
+ *
+ * @param node if non-null, the waiter
+ * @param group either node or the group node is cowaiting with
+ * @param interrupted if already interrupted
+ * @return INTERRUPTED if interrupted or Thread.interrupted, else zero
+ */
+ private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
+ if (node != null && group != null) {
+ Thread w;
+ node.status = CANCELLED;
+ // unsplice cancelled nodes from group
+ for (WNode p = group, q; (q = p.cowait) != null;) {
+ if (q.status == CANCELLED) {
+ U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
+ p = group; // restart
+ }
+ else
p = q;
+ }
+ if (group == node) {
+ for (WNode r = group.cowait; r != null; r = r.cowait) {
+ if ((w = r.thread) != null)
+ U.unpark(w); // wake up uncancelled co-waiters
+ }
+ for (WNode pred = node.prev; pred != null; ) { // unsplice
+ WNode succ, pp; // find valid successor
+ while ((succ = node.next) == null ||
+ succ.status == CANCELLED) {
+ WNode q = null; // find successor the slow way
+ for (WNode t = wtail; t != null && t != node; t = t.prev)
+ if (t.status != CANCELLED)
+ q = t; // don't link if succ cancelled
+ if (succ == q || // ensure accurate successor
+ U.compareAndSwapObject(node, WNEXT,
+ succ, succ = q)) {
+ if (succ == null && node == wtail)
+ U.compareAndSwapObject(this, WTAIL, node, pred);
+ break;
+ }
+ }
+ if (pred.next == node) // unsplice pred link
+ U.compareAndSwapObject(pred, WNEXT, node, succ);
+ if (succ != null && (w = succ.thread) != null) {
+ succ.thread = null;
+ U.unpark(w); // wake up succ to observe new pred
+ }
+ if (pred.status != CANCELLED || (pp = pred.prev) == null)
+ break;
+ node.prev = pp; // repeat if new pred wrong/cancelled
+ U.compareAndSwapObject(pp, WNEXT, pred, succ);
+ pred = pp;
}
}
}
- readerPrefSignal();
+ WNode h; // Possibly release first waiter
+ while ((h = whead) != null) {
+ long s; WNode q; // similar to release() but check eligibility
+ if ((q = h.next) == null || q.status == CANCELLED) {
+ for (WNode t = wtail; t != null && t != h; t = t.prev)
+ if (t.status <= 0)
+ q = t;
+ }
+ if (h == whead) {
+ if (q != null && h.status == 0 &&
+ ((s = state) & ABITS) != WBIT && // waiter is eligible
+ (s == 0L || q.mode == RMODE))
+ release(h);
+ break;
+ }
+ }
return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
}
// Unsafe mechanics
private static final sun.misc.Unsafe U;
private static final long STATE;
- private static final long RHEAD;
private static final long WHEAD;
private static final long WTAIL;
- private static final long RNEXT;
private static final long WNEXT;
- private static final long WPREV;
- private static final long WAITER;
- private static final long STATUS;
+ private static final long WSTATUS;
+ private static final long WCOWAIT;
+ private static final long PARKBLOCKER;
static {
try {
U = getUnsafe();
Class> k = StampedLock.class;
- Class> rk = RNode.class;
Class> wk = WNode.class;
STATE = U.objectFieldOffset
(k.getDeclaredField("state"));
- RHEAD = U.objectFieldOffset
- (k.getDeclaredField("rhead"));
WHEAD = U.objectFieldOffset
(k.getDeclaredField("whead"));
WTAIL = U.objectFieldOffset
(k.getDeclaredField("wtail"));
- RNEXT = U.objectFieldOffset
- (rk.getDeclaredField("next"));
- WAITER = U.objectFieldOffset
- (rk.getDeclaredField("waiter"));
- STATUS = U.objectFieldOffset
+ WSTATUS = U.objectFieldOffset
(wk.getDeclaredField("status"));
WNEXT = U.objectFieldOffset
(wk.getDeclaredField("next"));
- WPREV = U.objectFieldOffset
- (wk.getDeclaredField("prev"));
+ WCOWAIT = U.objectFieldOffset
+ (wk.getDeclaredField("cowait"));
+ Class> tk = Thread.class;
+ PARKBLOCKER = U.objectFieldOffset
+ (tk.getDeclaredField("parkBlocker"));
} catch (Exception e) {
throw new Error(e);
@@ -1195,22 +1395,23 @@ public class StampedLock implements java
private static sun.misc.Unsafe getUnsafe() {
try {
return sun.misc.Unsafe.getUnsafe();
- } catch (SecurityException se) {
- try {
- return java.security.AccessController.doPrivileged
- (new java.security
- .PrivilegedExceptionAction