--- jsr166/src/jsr166e/StampedLock.java	2012/10/12 16:27:05	1.3
+++ jsr166/src/jsr166e/StampedLock.java	2012/10/13 11:51:12	1.8
@@ -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
@@ -76,8 +76,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 +90,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,7 +122,7 @@ import java.util.concurrent.TimeUnit;
  *   }
  *
  *   double distanceFromOriginV2() { // combines code paths
- *     for (long stamp = sl.optimisticRead(); ; stamp = sl.readLock()) {
+ *     for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
  *       double currentX, currentY;
  *       try {
  *         currentX = x;
@@ -177,7 +180,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 then 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 +216,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% probablility) 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,10 +252,10 @@ 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
@@ -303,7 +320,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;
@@ -329,16 +346,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 +375,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 +395,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 +418,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 +436,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 +474,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()) {
@@ -512,7 +529,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)
@@ -527,7 +544,7 @@ public class StampedLock implements java
      *
      * @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 +574,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;
@@ -707,7 +724,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 +741,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;
@@ -773,6 +790,7 @@ 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
      * @return new stamp on success, else zero
      */
@@ -792,6 +810,7 @@ public class StampedLock implements java
 
     /**
      * Tries to decrement readerOverflow.
+     *
      * @param stamp, assumed that (stamp & ABITS) >= RFULL
      * @return new stamp on success, else zero
      */
@@ -889,16 +908,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 +921,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;
@@ -947,8 +957,9 @@ public class StampedLock implements java
                 p.next = node;
                 for (int headSpins = SPINS;;) {
                     WNode np; int ps;
-                    if ((np = node.prev) != p && np != null)
-                        (p = np).next = node; // stale
+                    if ((np = node.prev) != p && np != null &&
+                        (p = np).next != node)
+                        p.next = node; // stale
                     if (p == whead) {
                         for (int k = headSpins;;) {
                             if (((s = state) & ABITS) == 0L) {
@@ -1005,16 +1016,18 @@ public class StampedLock implements java
             WNode predNext = pred.next;
             node.status = CANCELLED;
             if (predNext != null) {
-                Thread w = null;
+                Thread w;
                 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);
+                if (succ == null || succ.status == CANCELLED) {
+                    succ = 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);
+                }
                 U.compareAndSwapObject(pred, WNEXT, predNext, succ);
-                if (w != null)
+                if (succ != null && (w = succ.thread) != null)
                     U.unpark(w);
             }
         }
@@ -1022,7 +1035,7 @@ public class StampedLock implements java
         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
@@ -1101,8 +1114,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 +1129,7 @@ public class StampedLock implements java
                     }
                     else {
                         U.compareAndSwapObject(pred, RNEXT, p, q);
-                        break;
+                        p = pred.next;
                     }
                 }
                 else {