--- jsr166/src/jsr166e/StampedLock.java 2012/10/12 17:35:29 1.6 +++ jsr166/src/jsr166e/StampedLock.java 2013/01/14 19:00:01 1.27 @@ -11,8 +11,8 @@ import java.util.concurrent.TimeUnit; /** * A capability-based lock with three modes for controlling read/write - * access. The state of a StampedLock consists of a version and - * mode. Lock acquisition methods return a stamp that represents and + * access. The state of a StampedLock consists of a version and mode. + * Lock acquisition methods return a stamp that represents and * controls access with respect to a lock state; "try" versions of * these methods may instead return the special value zero to * represent failure to acquire access. Lock release and conversion @@ -55,18 +55,21 @@ import java.util.concurrent.TimeUnit; *
This class also supports methods that conditionally provide * conversions across the three modes. For example, method {@link * #tryConvertToWriteLock} attempts to "upgrade" a mode, returning - * valid write stamp if (1) already in writing mode (2) in reading + * a valid write stamp if (1) already in writing mode (2) in reading * mode and there are no other readers or (3) in optimistic mode and * the lock is available. The forms of these methods are designed to * help reduce some of the code bloat that otherwise occurs in * retry-based designs. * - *
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 @@ -76,8 +79,11 @@ import java.util.concurrent.TimeUnit; * into initial unlocked state, so they are not useful for remote * locking. * - *
The scheduling policy of StampedLock does not consistently prefer - * readers over writers or vice versa. + *
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. * *
Sample Usage. The following illustrates some usage idioms
* in a class that maintains simple two-dimensional points. The sample
@@ -119,16 +125,17 @@ import java.util.concurrent.TimeUnit;
* }
*
* double distanceFromOriginV2() { // combines code paths
- * for (long stamp = sl.optimisticRead(); ; stamp = sl.readLock()) {
- * double currentX, currentY;
+ * double currentX = 0.0, currentY = 0.0;
+ * for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
* try {
* currentX = x;
* currentY = y;
* } finally {
* if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
- * return Math.sqrt(currentX * currentX + currentY * currentY);
+ * break;
* }
* }
+ * return Math.sqrt(currentX * currentX + currentY * currentY);
* }
*
* void moveIfAtOrigin(double newX, double newY) { // upgrade
@@ -136,7 +143,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;
@@ -149,7 +156,7 @@ import java.util.concurrent.TimeUnit;
* }
* }
* } finally {
- * sl.unlock(stamp);
+ * sl.unlock(stamp);
* }
* }
* }}
@@ -177,7 +184,7 @@ 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.
@@ -213,6 +220,20 @@ public class StampedLock implements java
* 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% probability) before enqueuing, 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.
+ *
* As noted in Boehm's paper (above), sequence validation (mainly
* method validate()) requires stricter ordering rules than apply
* to normal volatile reads (of "state"). In the absence of (but
@@ -231,6 +252,8 @@ 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();
@@ -244,7 +267,7 @@ public class StampedLock implements java
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;
@@ -293,7 +316,7 @@ public class StampedLock implements java
private transient int readerOverflow;
/**
- * Creates a new lock initially in unlocked state.
+ * Creates a new lock, initially in unlocked state.
*/
public StampedLock() {
state = ORIGIN;
@@ -317,7 +340,7 @@ public class StampedLock implements java
* 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;
@@ -494,15 +517,16 @@ 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
+ * 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.
*
- * @return true if the lock has not been exclusively held since
- * issuance of the given stamp; else false
+ * @return 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);
}
@@ -522,7 +546,7 @@ public class StampedLock implements java
}
/**
- * If the lock state matches the given stamp, releases
+ * If the lock state matches the given stamp, releases the
* non-exclusive lock.
*
* @param stamp a stamp returned by a read-lock operation
@@ -589,10 +613,11 @@ public class StampedLock implements java
/**
* If the lock state matches the given stamp then 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 and returns a write stamp. Or, if
- * an optimistic read, returns a write stamp only if immediately
- * available. This method returns zero in all other cases.
+ * lock, returns it. Or, if a read lock, if the write lock is
+ * available, releases the read lock and returns a write stamp.
+ * Or, if an optimistic read, returns a write stamp only if
+ * immediately available. This method returns zero in all other
+ * cases.
*
* @param stamp a stamp
* @return a valid write stamp, or zero on failure
@@ -611,7 +636,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;
@@ -649,7 +674,7 @@ public class StampedLock implements java
else if (m == WBIT) {
if (a != m)
break;
- next = state = s + (WBIT + RUNIT);
+ state = next = s + (WBIT + RUNIT);
readerPrefSignal();
return next;
}
@@ -683,7 +708,7 @@ public class StampedLock implements java
else if (m == WBIT) {
if (a != m)
break;
- next = state = (s += WBIT) == 0L ? ORIGIN : s;
+ state = next = (s += WBIT) == 0L ? ORIGIN : s;
readerPrefSignal();
return next;
}
@@ -757,8 +782,7 @@ public class StampedLock implements java
* @return 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;
}
private void readObject(java.io.ObjectInputStream s)
@@ -774,7 +798,7 @@ 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, assumed that (s & ABITS) >= RFULL
* @return new stamp on success, else zero
*/
private long tryIncReaderOverflow(long s) {
@@ -794,7 +818,7 @@ public class StampedLock implements java
/**
* Tries to decrement readerOverflow.
*
- * @param stamp, assumed that (stamp & ABITS) >= RFULL
+ * @param s, assumed that (s & ABITS) >= RFULL
* @return new stamp on success, else zero
*/
private long tryDecReaderOverflow(long s) {
@@ -850,11 +874,10 @@ public class StampedLock implements java
U.compareAndSwapObject(p, WAITER, w, null))
U.unpark(w);
}
- if (!readers && (state & ABITS) == 0L &&
- (h = whead) != null && h.status != 0) {
+ if (!readers && (h = whead) != null && h.status != 0 &&
+ (state & ABITS) == 0L) {
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;
@@ -869,7 +892,6 @@ public class StampedLock implements java
if ((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;
@@ -891,16 +913,7 @@ public class StampedLock implements java
/**
* 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. Both await
- * methods use a similar spin strategy: If associated queue
- * appears to be empty, then the thread spin-waits up to SPINS
- * times before enqueing, and then, if 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.
+ * use an xorShift to further reduce memory traffic.
*/
private static int nextRandom(int r) {
if (r == 0)
@@ -948,8 +961,8 @@ public class StampedLock implements java
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)
+ WNode np, pp; int ps;
+ while ((np = node.prev) != p && np != null)
(p = np).next = node; // stale
if (p == whead) {
for (int k = headSpins;;) {
@@ -971,8 +984,12 @@ public class StampedLock implements java
}
if ((ps = p.status) == 0)
U.compareAndSwapInt(p, STATUS, 0, WAITING);
- else if (ps == CANCELLED)
- node.prev = p.prev;
+ 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)
@@ -980,11 +997,10 @@ public class StampedLock implements java
else if ((time = deadline - System.nanoTime()) <= 0L)
return cancelWriter(node, false);
if (node.prev == p && p.status == WAITING &&
- (p != whead || (state & WBIT) != 0L)) { // recheck
+ (p != whead || (state & ABITS) != 0L)) // recheck
U.park(false, time);
- if (interruptible && Thread.interrupted())
- return cancelWriter(node, true);
- }
+ if (interruptible && Thread.interrupted())
+ return cancelWriter(node, true);
}
}
}
@@ -993,31 +1009,39 @@ public class StampedLock implements java
/**
* 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.
+ * if possible. This is a variant of cancellation methods in
+ * AbstractQueuedSynchronizer (see its detailed explanation in AQS
+ * internal documentation) that more conservatively wakes up other
+ * threads that may have had their links changed, so as to preserve
+ * liveness in the main signalling methods.
*/
private long cancelWriter(WNode node, boolean interrupted) {
- WNode pred;
- if (node != null && (pred = node.prev) != null) {
- WNode pp;
+ if (node != null) {
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 = null;
- WNode succ = node.next;
- while (succ != null && succ.status == CANCELLED)
- succ = succ.next;
- if (succ != null)
- w = succ.thread;
- else if (node == wtail)
- U.compareAndSwapObject(this, WTAIL, node, pred);
- U.compareAndSwapObject(pred, WNEXT, predNext, succ);
- if (w != null)
+ for (WNode pred = node.prev; pred != null; ) {
+ WNode succ, pp; Thread w;
+ while ((succ = node.next) == null || succ.status == CANCELLED) {
+ WNode q = null;
+ for (WNode t = wtail; t != null && t != node; t = t.prev)
+ if (t.status != CANCELLED)
+ q = t;
+ if (succ == q ||
+ U.compareAndSwapObject(node, WNEXT, succ, succ = q)) {
+ if (succ == null && node == wtail)
+ U.compareAndSwapObject(this, WTAIL, node, pred);
+ break;
+ }
+ }
+ if (pred.next == node)
+ U.compareAndSwapObject(pred, WNEXT, node, succ);
+ if (succ != null && (w = succ.thread) != null)
U.unpark(w);
+ if (pred.status != CANCELLED || (pp = pred.prev) == null)
+ break;
+ node.prev = pp; // repeat for new pred
+ U.compareAndSwapObject(pp, WNEXT, pred, succ);
+ pred = pp;
}
}
writerPrefSignal();
@@ -1091,11 +1115,10 @@ public class StampedLock implements java
time = 0L;
else if ((time = deadline - System.nanoTime()) <= 0L)
return cancelReader(node, false);
- if ((state & WBIT) != 0L && node.waiter != null) { // recheck
+ if ((state & WBIT) != 0L && node.waiter != null) // recheck
U.park(false, time);
- if (interruptible && Thread.interrupted())
- return cancelReader(node, true);
- }
+ if (interruptible && Thread.interrupted())
+ return cancelReader(node, true);
}
}
}
@@ -1183,22 +1206,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