--- jsr166/src/jsr166e/StampedLock.java	2012/10/12 16:48:15	1.4
+++ jsr166/src/jsr166e/StampedLock.java	2012/10/13 22:56:00	1.11
@@ -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,7 +55,7 @@ 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
@@ -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;
@@ -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
@@ -237,7 +254,7 @@ public class StampedLock implements java
     /** Maximum number of retries before blocking on acquisition */
     private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1;
 
-    /** Maximum number of retries before re-blocking on write lock */
+    /** 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 */
@@ -329,7 +346,7 @@ 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
@@ -419,7 +436,7 @@ 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
@@ -522,7 +539,7 @@ 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
@@ -891,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)
@@ -949,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) {
@@ -1007,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);
             }
         }
@@ -1103,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;
@@ -1119,7 +1129,7 @@ public class StampedLock implements java
                     }
                     else {
                         U.compareAndSwapObject(pred, RNEXT, p, q);
-                        break;
+                        p = pred.next;
                     }
                 }
                 else {