--- jsr166/src/jsr166e/StampedLock.java 2013/01/22 15:42:28 1.28
+++ jsr166/src/jsr166e/StampedLock.java 2013/07/14 19:55:05 1.37
@@ -5,10 +5,11 @@
*/
package jsr166e;
-
-import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
-import java.util.concurrent.locks.*;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.LockSupport;
/**
* A capability-based lock with three modes for controlling read/write
@@ -37,19 +38,20 @@ import java.util.concurrent.locks.*;
*
Optimistic Reading. Method {@link #tryOptimisticRead}
* returns a non-zero stamp only if the lock is not currently held
* in write mode. Method {@link #validate} returns true if the lock
- * has not since been acquired in write mode. This mode can be
- * thought of as an extremely weak version of a read-lock, that can
- * be broken by a writer at any time. The use of optimistic mode
- * for short read-only code segments often reduces contention and
- * improves throughput. However, its use is inherently fragile.
- * Optimistic read sections should only read fields and hold them in
- * local variables for later use after validation. Fields read while
- * in optimistic mode may be wildly inconsistent, so usage applies
- * only when you are familiar enough with data representations to
- * check consistency and/or repeatedly invoke method {@code
- * validate()}. For example, such steps are typically required when
- * first reading an object or array reference, and then accessing
- * one of its fields, elements or methods.
+ * has not been acquired in write mode since obtaining a given
+ * stamp. This mode can be thought of as an extremely weak version
+ * of a read-lock, that can be broken by a writer at any time. The
+ * use of optimistic mode for short read-only code segments often
+ * reduces contention and improves throughput. However, its use is
+ * inherently fragile. Optimistic read sections should only read
+ * fields and hold them in local variables for later use after
+ * validation. Fields read while in optimistic mode may be wildly
+ * inconsistent, so usage applies only when you are familiar enough
+ * with data representations to check consistency and/or repeatedly
+ * invoke method {@code validate()}. For example, such steps are
+ * typically required when first reading an object or array
+ * reference, and then accessing one of its fields, elements or
+ * methods.
*
*
*
@@ -115,34 +117,17 @@ import java.util.concurrent.locks.*;
* }
* }
*
- * 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
- * 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
- * break;
- * }
+ * 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);
* }
@@ -198,13 +183,13 @@ public class StampedLock implements java
*
* Waiters use a modified form of CLH lock used in
* AbstractQueuedSynchronizer (see its internal documentation for
- * a fuller account), where each node it tagged (field mode) as
+ * 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 its
- * structure, wait nodes need not actually carry sequence numbers;
- * we know each is >= its predecessor. These queue mechanics
- * simplify the scheduling policy to a mainly-FIFO scheme that
+ * 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
@@ -229,8 +214,8 @@ public class StampedLock implements java
*
* 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 consitent sets
- * of locally cahced reads.
+ * 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
@@ -329,7 +314,7 @@ public class StampedLock implements java
* @return a stamp that can be used to unlock or convert mode
*/
public long writeLock() {
- long s, next; // bypass acquireWrite in fully onlocked case only
+ 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));
@@ -354,6 +339,8 @@ public class StampedLock implements java
* 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
@@ -364,7 +351,7 @@ public class StampedLock implements java
long nanos = unit.toNanos(time);
if (!Thread.interrupted()) {
long next, deadline;
- if ((next = tryWriteLock()) != 0)
+ if ((next = tryWriteLock()) != 0L)
return next;
if (nanos <= 0L)
return 0L;
@@ -401,7 +388,7 @@ public class StampedLock implements java
* @return a stamp that can be used to unlock or convert mode
*/
public long readLock() {
- long s, next; // bypass acquireRead on fully onlocked case only
+ long s, next; // bypass acquireRead on fully unlocked case only
return ((((s = state) & ABITS) == 0L &&
U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
next : acquireRead(false, 0L));
@@ -433,6 +420,8 @@ public class StampedLock implements java
* 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
@@ -440,11 +429,17 @@ public class StampedLock implements java
*/
public long tryReadLock(long time, TimeUnit unit)
throws InterruptedException {
- long next, deadline;
+ long s, m, next, deadline;
long nanos = unit.toNanos(time);
if (!Thread.interrupted()) {
- if ((next = tryReadLock()) != 0)
- return next;
+ 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)
@@ -488,9 +483,12 @@ public class StampedLock implements java
* 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.
+ * 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 acquired
+ * @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) {
@@ -524,25 +522,21 @@ public class StampedLock implements java
* not match the current state of this lock
*/
public void unlockRead(long stamp) {
- long s, m; WNode h;
- 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 && (h = whead) != null && h.status != 0)
- release(h);
- return;
- }
}
- else if (m >= WBIT)
- break;
- else if (tryDecReaderOverflow(s) != 0L)
- return;
}
+ else if (tryDecReaderOverflow(s) != 0L)
+ break;
}
- throw new IllegalMonitorStateException();
}
/**
@@ -707,7 +701,7 @@ 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; WNode h;
@@ -725,7 +719,7 @@ 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; WNode h;
@@ -743,30 +737,66 @@ public class StampedLock implements java
return false;
}
+ // status monitoring methods
+
/**
- * Returns true if the lock is currently held exclusively.
+ * 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 {@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() {
return (state & RBITS) != 0L;
}
- private void readObject(java.io.ObjectInputStream s)
- throws java.io.IOException, ClassNotFoundException {
- s.defaultReadObject();
- state = ORIGIN; // reset to unlocked state
+ /**
+ * 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},
@@ -825,8 +855,7 @@ public class StampedLock implements java
throws InterruptedException {
return tryReadLock(time, unit) != 0L;
}
- // note that we give up ability to check mode so just use current state
- public void unlock() { unlockRead(state); }
+ public void unlock() { unstampedUnlockRead(); }
public Condition newCondition() {
throw new UnsupportedOperationException();
}
@@ -842,7 +871,7 @@ public class StampedLock implements java
throws InterruptedException {
return tryWriteLock(time, unit) != 0L;
}
- public void unlock() { unlockWrite(state); }
+ public void unlock() { unstampedUnlockWrite(); }
public Condition newCondition() {
throw new UnsupportedOperationException();
}
@@ -853,6 +882,41 @@ public class StampedLock implements java
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)
+ throws java.io.IOException, ClassNotFoundException {
+ s.defaultReadObject();
+ state = ORIGIN; // reset to unlocked state
+ }
+
// internals
/**
@@ -860,10 +924,11 @@ public class StampedLock implements java
* access bits value to RBITS, indicating hold of spinlock,
* then updating, then releasing.
*
- * @param s, assumed that (s & 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;
@@ -880,10 +945,11 @@ public class StampedLock implements java
/**
* Tries to decrement readerOverflow.
*
- * @param s, assumed that (s & 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;
@@ -903,7 +969,7 @@ public class StampedLock implements java
return 0L;
}
- /*
+ /**
* 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
@@ -977,11 +1043,12 @@ public class StampedLock implements java
(p = np).next = node; // stale
if (whead == p) {
for (int k = spins;;) { // spin at head
- if (((s = state) & ABITS) == 0L &&
- U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) {
- whead = node;
- node.prev = null;
- return 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)
@@ -1003,15 +1070,17 @@ public class StampedLock implements java
if (deadline == 0L)
time = 0L;
else if ((time = deadline - System.nanoTime()) <= 0L)
- return cancelWaiter(node, null, false);
- node.thread = Thread.currentThread();
+ return cancelWaiter(node, node, false);
+ Thread wt = Thread.currentThread();
+ U.putObject(wt, PARKBLOCKER, this); // emulate LockSupport.park
+ node.thread = wt;
if (node.prev == p && p.status == WAITING && // recheck
- (p != whead || (state & ABITS) != 0L)) {
+ (p != whead || (state & ABITS) != 0L))
U.park(false, time);
- if (interruptible && Thread.interrupted())
- return cancelWaiter(node, null, true);
- }
node.thread = null;
+ U.putObject(wt, PARKBLOCKER, null);
+ if (interruptible && Thread.interrupted())
+ return cancelWaiter(node, node, true);
}
}
}
@@ -1033,11 +1102,9 @@ public class StampedLock implements java
if (group == null && (h = whead) != null &&
(q = h.next) != null && q.mode != RMODE)
break;
- if ((m = (s = state) & ABITS) == WBIT)
- break;
- if (m < RFULL ?
+ if ((m = (s = state) & ABITS) < RFULL ?
U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
- (ns = tryIncReaderOverflow(s)) != 0L) {
+ (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
if (group != null) { // help release others
for (WNode r = group;;) {
if ((w = r.thread) != null) {
@@ -1051,6 +1118,8 @@ public class StampedLock implements java
}
return ns;
}
+ if (m >= WBIT)
+ break;
}
if (spins > 0) {
if (ThreadLocalRandom.current().nextInt() >= 0)
@@ -1085,9 +1154,12 @@ public class StampedLock implements java
node.thread = null;
break;
}
+ Thread wt = Thread.currentThread();
+ U.putObject(wt, PARKBLOCKER, this);
if (node.thread == null) // must recheck
break;
U.park(false, time);
+ U.putObject(wt, PARKBLOCKER, null);
if (interruptible && Thread.interrupted())
return cancelWaiter(node, p, true);
}
@@ -1144,49 +1216,67 @@ public class StampedLock implements java
if (deadline == 0L)
time = 0L;
else if ((time = deadline - System.nanoTime()) <= 0L)
- return cancelWaiter(node, null, false);
- node.thread = Thread.currentThread();
+ return cancelWaiter(node, node, false);
+ Thread wt = Thread.currentThread();
+ U.putObject(wt, PARKBLOCKER, this);
+ node.thread = wt;
if (node.prev == p && p.status == WAITING &&
- (p != whead || (state & ABITS) != WBIT)) {
+ (p != whead || (state & ABITS) != WBIT))
U.park(false, time);
- if (interruptible && Thread.interrupted())
- return cancelWaiter(node, null, true);
- }
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 from queue
- * if possible. This is a variant of cancellation methods in
+ * 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) that more conservatively wakes up other
- * threads that may have had their links changed, so as to preserve
- * liveness in the main signalling methods.
+ * internal documentation).
+ *
+ * @param node if nonnull, 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) {
- node.thread = null;
+ if (node != null && group != null) {
+ Thread w;
node.status = CANCELLED;
- if (group != null) {
- for (WNode p = group, q; p != null; p = q) {
- if ((q = p.cowait) != null && q.status == CANCELLED) {
- U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
- break;
+ node.thread = null;
+ // unsplice cancelled nodes from group
+ for (WNode p = group, q; (q = p.cowait) != null;) {
+ if (q.status == CANCELLED)
+ U.compareAndSwapObject(p, WNEXT, q, q.next);
+ else
+ p = q;
+ }
+ if (group == node) {
+ WNode r; // detach and wake up uncancelled co-waiters
+ while ((r = node.cowait) != null) {
+ if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
+ (w = r.thread) != null) {
+ r.thread = null;
+ U.unpark(w);
}
}
- }
- else {
- for (WNode pred = node.prev; pred != null; ) {
- WNode succ, pp; Thread w;
+ 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;
+ 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;
- if (succ == q ||
+ 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)
@@ -1194,19 +1284,36 @@ public class StampedLock implements java
break;
}
}
- if (pred.next == node)
+ if (pred.next == node) // unsplice pred link
U.compareAndSwapObject(pred, WNEXT, node, succ);
- if (succ != null && (w = succ.thread) != null)
- U.unpark(w);
+ 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 for new pred
+ node.prev = pp; // repeat if new pred wrong/cancelled
U.compareAndSwapObject(pp, WNEXT, pred, succ);
pred = pp;
}
}
}
- release(whead);
+ 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;
}
@@ -1218,6 +1325,7 @@ public class StampedLock implements java
private static final long WNEXT;
private static final long WSTATUS;
private static final long WCOWAIT;
+ private static final long PARKBLOCKER;
static {
try {
@@ -1236,6 +1344,9 @@ public class StampedLock implements java
(wk.getDeclaredField("next"));
WCOWAIT = U.objectFieldOffset
(wk.getDeclaredField("cowait"));
+ Class> tk = Thread.class;
+ PARKBLOCKER = U.objectFieldOffset
+ (tk.getDeclaredField("parkBlocker"));
} catch (Exception e) {
throw new Error(e);