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 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 @@ -123,7 +126,7 @@ import java.util.concurrent.TimeUnit; * * double distanceFromOriginV2() { // combines code paths * for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) { - * double currentX, currentY; + * double currentX = 0.0, currentY = 0.0; * try { * currentX = x; * currentY = y; @@ -139,7 +142,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; @@ -511,15 +514,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); } @@ -629,7 +633,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; @@ -775,8 +779,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) @@ -792,7 +795,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) { @@ -812,7 +815,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) { @@ -868,11 +871,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; @@ -887,7 +889,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; @@ -957,10 +958,9 @@ 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 && - (p = np).next != node) - p.next = node; // stale + WNode np, pp; int ps; + while ((np = node.prev) != p && np != null) + (p = np).next = node; // stale if (p == whead) { for (int k = headSpins;;) { if (((s = state) & ABITS) == 0L) { @@ -981,8 +981,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) @@ -990,11 +994,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 & WBIT) != 0L)) // recheck U.park(false, time); - if (interruptible && Thread.interrupted()) - return cancelWriter(node, true); - } + if (interruptible && Thread.interrupted()) + return cancelWriter(node, true); } } } @@ -1003,33 +1006,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 + * 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; - WNode succ = node.next; - if (succ == null || succ.status == CANCELLED) { - succ = 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 <= 0) - succ = t; - if (succ == null && node == wtail) - U.compareAndSwapObject(this, WTAIL, node, pred); + 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; + } } - U.compareAndSwapObject(pred, WNEXT, predNext, succ); + 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(); @@ -1103,11 +1112,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); } } }