--- jsr166/src/jsr166e/StampedLock.java	2012/10/12 16:27:05	1.3
+++ jsr166/src/jsr166e/StampedLock.java	2012/10/17 00:02:47	1.22
@@ -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.  </li>
+ *   and all optimistic read validations will fail.  </li>
  *
  *  <li><b>Reading.</b> 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;
  * <p>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.
  *
- * <p>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
+ * <p>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.
  *
- * <p>The scheduling policy of StampedLock does not consistently prefer
- * readers over writers or vice versa.
+ * <p>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.
  *
  * <p><b>Sample Usage.</b> 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;
  *
  *  <pre>{@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;
@@ -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 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.
+     *
      * 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
@@ -235,16 +256,16 @@ public class StampedLock implements java
     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 +314,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 +324,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 +338,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 +350,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 +379,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 +399,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 +422,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 +440,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 +478,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 +515,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 +534,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 +544,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 +579,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 +611,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 +634,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 +672,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 +706,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 +730,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 +747,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 +780,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 +795,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 +815,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 +872,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 +890,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 +911,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 +924,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 +959,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 +982,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 +995,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);
                     }
                 }
             }
@@ -991,38 +1007,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 +1113,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 +1124,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 +1139,7 @@ public class StampedLock implements java
                     }
                     else {
                         U.compareAndSwapObject(pred, RNEXT, p, q);
-                        break;
+                        p = pred.next;
                     }
                 }
                 else {