--- jsr166/src/jsr166e/StampedLock.java 2012/10/12 16:27:05 1.3 +++ 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 @@ -26,7 +26,7 @@ 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 observer validations will fail. + * and all optimistic read validations will fail. * *
  • Reading. Method {@link #readLock} possibly blocks * waiting for non-exclusive access, returning a stamp that can be @@ -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 @@ -87,7 +93,7 @@ import java.util.concurrent.TimeUnit; * * 

    {@code
  * class Point {
- *   private volatile double x, y;
+ *   private double x, y;
  *   private final StampedLock sl = new StampedLock();
  *
  *   void move(double deltaX, double deltaY) { // an exclusively locked method
@@ -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 - * supplementatry 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,20 +252,22 @@ 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; + private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1; - /** Maximum number of retries before re-blocking on write lock */ - private static final int MAX_HEAD_SPINS = NCPU > 1 ? 1 << 12 : 1; + /** Maximum number of retries before re-blocking */ + private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1; /** 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; @@ -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; @@ -303,7 +326,7 @@ public class StampedLock implements java * Exclusively acquires the lock, blocking if necessary * until available. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode */ public long writeLock() { long s, next; @@ -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; @@ -329,16 +352,16 @@ public class StampedLock implements java /** * Exclusively acquires the lock if it is available within the - * given time and the current thread has not been interrupted + * given time and the current thread has not been interrupted. * * @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 * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long tryWriteLock(long time, TimeUnit unit) throws InterruptedException { - long nanos = unit.toNanos(time); + long nanos = unit.toNanos(time); if (!Thread.interrupted()) { long s, next, deadline; if (((s = state) & ABITS) == 0L && @@ -358,9 +381,9 @@ public class StampedLock implements java * Exclusively acquires the lock, blocking if necessary * until available or the current thread is interrupted. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long writeLockInterruptibly() throws InterruptedException { if (!Thread.interrupted()) { @@ -378,7 +401,7 @@ public class StampedLock implements java * Non-exclusively acquires the lock, blocking if necessary * until available. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode */ public long readLock() { for (;;) { @@ -401,7 +424,7 @@ public class StampedLock implements java * Non-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 tryReadLock() { for (;;) { @@ -419,12 +442,12 @@ 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 + * given time and the current thread has not been interrupted. * * @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 * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long tryReadLock(long time, TimeUnit unit) throws InterruptedException { @@ -457,9 +480,9 @@ public class StampedLock implements java * Non-exclusively acquires the lock, blocking if necessary * until available or the current thread is interrupted. * - * @return a stamp that can be used to unlock or convert mode. + * @return a stamp that can be used to unlock or convert mode * @throws InterruptedException if the current thread is interrupted - * before acquiring the lock. + * before acquiring the lock */ public long readLockInterruptibly() throws InterruptedException { if (!Thread.interrupted()) { @@ -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); } @@ -512,7 +536,7 @@ public class StampedLock implements java * * @param stamp a stamp returned by a write-lock operation * @throws IllegalMonitorStateException if the stamp does - * not match the current state of this lock. + * not match the current state of this lock */ public void unlockWrite(long stamp) { if (state != stamp || (stamp & WBIT) == 0L) @@ -522,12 +546,12 @@ 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 * @throws IllegalMonitorStateException if the stamp does - * not match the current state of this lock. + * not match the current state of this lock */ public void unlockRead(long stamp) { long s, m; @@ -557,7 +581,7 @@ public class StampedLock implements java * * @param stamp a stamp returned by a lock operation * @throws IllegalMonitorStateException if the stamp does - * not match the current state of this lock. + * not match the current state of this lock */ public void unlock(long stamp) { long a = stamp & ABITS, m, s; @@ -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; } @@ -707,7 +732,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 true if the lock was held, else false */ public boolean tryUnlockWrite() { long s; @@ -724,7 +749,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 true if the read lock was held, else false */ public boolean tryUnlockRead() { long s, m; @@ -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) @@ -773,7 +797,8 @@ public class StampedLock implements java * Tries to increment readerOverflow by first setting state * 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) { @@ -792,7 +817,8 @@ 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) { @@ -848,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; @@ -867,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; @@ -889,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) @@ -911,14 +926,14 @@ public class StampedLock implements java /** * Possibly spins trying to obtain write lock, then enqueues and - * blocks while not head of write queue or cannot aquire lock, + * blocks while not head of write queue or cannot acquire lock, * possibly spinning when at head; cancelling on timeout or * interrupt. * * @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). + * at (and return zero) */ private long awaitWrite(boolean interruptible, long deadline) { WNode node = null; @@ -946,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;;) { @@ -969,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) @@ -978,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); } } } @@ -991,38 +1009,46 @@ 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(); 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 @@ -1089,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); } } } @@ -1101,8 +1126,7 @@ public class StampedLock implements java /** * If node non-null, forces cancel status and unsplices from queue * if possible, by traversing entire queue looking for cancelled - * nodes, cleaning out all at head, but stopping upon first - * encounter otherwise. + * nodes. */ private long cancelReader(RNode node, boolean interrupted) { Thread w; @@ -1117,7 +1141,7 @@ public class StampedLock implements java } else { U.compareAndSwapObject(pred, RNEXT, p, q); - break; + p = pred.next; } } else { @@ -1182,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() { - public sun.misc.Unsafe run() throws Exception { - java.lang.reflect.Field f = sun.misc - .Unsafe.class.getDeclaredField("theUnsafe"); - f.setAccessible(true); - return (sun.misc.Unsafe) f.get(null); - }}); - } catch (java.security.PrivilegedActionException e) { - throw new RuntimeException("Could not initialize intrinsics", - e.getCause()); - } + } catch (SecurityException tryReflectionInstead) {} + try { + return java.security.AccessController.doPrivileged + (new java.security.PrivilegedExceptionAction() { + public sun.misc.Unsafe run() throws Exception { + Class k = sun.misc.Unsafe.class; + for (java.lang.reflect.Field f : k.getDeclaredFields()) { + f.setAccessible(true); + Object x = f.get(null); + if (k.isInstance(x)) + return k.cast(x); + } + throw new NoSuchFieldError("the Unsafe"); + }}); + } catch (java.security.PrivilegedActionException e) { + throw new RuntimeException("Could not initialize intrinsics", + e.getCause()); } } - }