changeset 7460:36d25dc2b8f0

8005697: Add StampedLock Reviewed-by: chegar, alanb, dice, martin
author dl
date Sat, 09 Feb 2013 08:35:57 +0000
parents 522fb3867a3a
children d14cd2272b2d
files make/java/java/FILES_java.gmk src/share/classes/java/util/concurrent/locks/LockSupport.java src/share/classes/java/util/concurrent/locks/StampedLock.java test/java/util/concurrent/locks/StampedLock/Basic.java
diffstat 4 files changed, 2040 insertions(+), 24 deletions(-) [+]
line wrap: on
line diff
--- a/make/java/java/FILES_java.gmk	Fri Feb 08 16:00:23 2013 -0800
+++ b/make/java/java/FILES_java.gmk	Sat Feb 09 08:35:57 2013 +0000
@@ -389,6 +389,7 @@
     java/util/concurrent/locks/ReadWriteLock.java \
     java/util/concurrent/locks/ReentrantLock.java \
     java/util/concurrent/locks/ReentrantReadWriteLock.java \
+    java/util/concurrent/locks/StampedLock.java \
     java/util/regex/Pattern.java \
     java/util/regex/Matcher.java \
     java/util/regex/MatchResult.java \
--- a/src/share/classes/java/util/concurrent/locks/LockSupport.java	Fri Feb 08 16:00:23 2013 -0800
+++ b/src/share/classes/java/util/concurrent/locks/LockSupport.java	Sat Feb 09 08:35:57 2013 +0000
@@ -101,14 +101,14 @@
  *     // Block while not first in queue or cannot acquire lock
  *     while (waiters.peek() != current ||
  *            !locked.compareAndSet(false, true)) {
- *        LockSupport.park(this);
- *        if (Thread.interrupted()) // ignore interrupts while waiting
- *          wasInterrupted = true;
+ *       LockSupport.park(this);
+ *       if (Thread.interrupted()) // ignore interrupts while waiting
+ *         wasInterrupted = true;
  *     }
  *
  *     waiters.remove();
  *     if (wasInterrupted)          // reassert interrupt status on exit
- *        current.interrupt();
+ *       current.interrupt();
  *   }
  *
  *   public void unlock() {
@@ -120,20 +120,9 @@
 public class LockSupport {
     private LockSupport() {} // Cannot be instantiated.
 
-    // Hotspot implementation via intrinsics API
-    private static final Unsafe unsafe = Unsafe.getUnsafe();
-    private static final long parkBlockerOffset;
-
-    static {
-        try {
-            parkBlockerOffset = unsafe.objectFieldOffset
-                (java.lang.Thread.class.getDeclaredField("parkBlocker"));
-        } catch (Exception ex) { throw new Error(ex); }
-    }
-
     private static void setBlocker(Thread t, Object arg) {
         // Even though volatile, hotspot doesn't need a write barrier here.
-        unsafe.putObject(t, parkBlockerOffset, arg);
+        UNSAFE.putObject(t, parkBlockerOffset, arg);
     }
 
     /**
@@ -149,7 +138,7 @@
      */
     public static void unpark(Thread thread) {
         if (thread != null)
-            unsafe.unpark(thread);
+            UNSAFE.unpark(thread);
     }
 
     /**
@@ -183,7 +172,7 @@
     public static void park(Object blocker) {
         Thread t = Thread.currentThread();
         setBlocker(t, blocker);
-        unsafe.park(false, 0L);
+        UNSAFE.park(false, 0L);
         setBlocker(t, null);
     }
 
@@ -223,7 +212,7 @@
         if (nanos > 0) {
             Thread t = Thread.currentThread();
             setBlocker(t, blocker);
-            unsafe.park(false, nanos);
+            UNSAFE.park(false, nanos);
             setBlocker(t, null);
         }
     }
@@ -264,7 +253,7 @@
     public static void parkUntil(Object blocker, long deadline) {
         Thread t = Thread.currentThread();
         setBlocker(t, blocker);
-        unsafe.park(true, deadline);
+        UNSAFE.park(true, deadline);
         setBlocker(t, null);
     }
 
@@ -283,7 +272,7 @@
     public static Object getBlocker(Thread t) {
         if (t == null)
             throw new NullPointerException();
-        return unsafe.getObjectVolatile(t, parkBlockerOffset);
+        return UNSAFE.getObjectVolatile(t, parkBlockerOffset);
     }
 
     /**
@@ -312,7 +301,7 @@
      * for example, the interrupt status of the thread upon return.
      */
     public static void park() {
-        unsafe.park(false, 0L);
+        UNSAFE.park(false, 0L);
     }
 
     /**
@@ -346,7 +335,7 @@
      */
     public static void parkNanos(long nanos) {
         if (nanos > 0)
-            unsafe.park(false, nanos);
+            UNSAFE.park(false, nanos);
     }
 
     /**
@@ -380,6 +369,46 @@
      *        to wait until
      */
     public static void parkUntil(long deadline) {
-        unsafe.park(true, deadline);
+        UNSAFE.park(true, deadline);
     }
+
+    /**
+     * Returns the pseudo-randomly initialized or updated secondary seed.
+     * Copied from ThreadLocalRandom due to package access restrictions.
+     */
+    static final int nextSecondarySeed() {
+        int r;
+        Thread t = Thread.currentThread();
+        if ((r = UNSAFE.getInt(t, SECONDARY)) != 0) {
+            r ^= r << 13;   // xorshift
+            r ^= r >>> 17;
+            r ^= r << 5;
+        }
+        else if ((r = java.util.concurrent.ThreadLocalRandom.current().nextInt()) == 0)
+            r = 1; // avoid zero
+        UNSAFE.putInt(t, SECONDARY, r);
+        return r;
+    }
+
+    // Hotspot implementation via intrinsics API
+    private static final sun.misc.Unsafe UNSAFE;
+    private static final long parkBlockerOffset;
+    private static final long SEED;
+    private static final long PROBE;
+    private static final long SECONDARY;
+    static {
+        try {
+            UNSAFE = sun.misc.Unsafe.getUnsafe();
+            Class<?> tk = Thread.class;
+            parkBlockerOffset = UNSAFE.objectFieldOffset
+                (tk.getDeclaredField("parkBlocker"));
+            SEED = UNSAFE.objectFieldOffset
+                (tk.getDeclaredField("threadLocalRandomSeed"));
+            PROBE = UNSAFE.objectFieldOffset
+                (tk.getDeclaredField("threadLocalRandomProbe"));
+            SECONDARY = UNSAFE.objectFieldOffset
+                (tk.getDeclaredField("threadLocalRandomSecondarySeed"));
+        } catch (Exception ex) { throw new Error(ex); }
+    }
+
 }
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/share/classes/java/util/concurrent/locks/StampedLock.java	Sat Feb 09 08:35:57 2013 +0000
@@ -0,0 +1,1377 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.  Oracle designates this
+ * particular file as subject to the "Classpath" exception as provided
+ * by Oracle in the LICENSE file that accompanied this code.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+package java.util.concurrent.locks;
+
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.Condition;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.LockSupport;
+
+/**
+ * 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
+ * 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
+ * methods require stamps as arguments, and fail if they do not match
+ * the state of the lock. The three modes are:
+ *
+ * <ul>
+ *
+ *  <li><b>Writing.</b> Method {@link #writeLock} possibly blocks
+ *   waiting for exclusive access, returning a stamp that can be used
+ *   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 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
+ *   used in method {@link #unlockRead} to release the lock. Untimed
+ *   and timed versions of {@code tryReadLock} are also provided. </li>
+ *
+ *  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
+ *   returns a non-zero stamp only if the lock is not currently held
+ *   in write mode. Method {@link #validate} returns true if the lock
+ *   has not been acquired in write mode since obtaining a given
+ *   stamp.  This mode can be thought of as an extremely weak version
+ *   of a read-lock, that can be broken by a writer at any time.  The
+ *   use of optimistic mode for short read-only code segments often
+ *   reduces contention and improves throughput.  However, its use is
+ *   inherently fragile.  Optimistic read sections should only read
+ *   fields and hold them in local variables for later use after
+ *   validation. Fields read while in optimistic mode may be wildly
+ *   inconsistent, so usage applies only when you are familiar enough
+ *   with data representations to check consistency and/or repeatedly
+ *   invoke method {@code validate()}.  For example, such steps are
+ *   typically required when first reading an object or array
+ *   reference, and then accessing one of its fields, elements or
+ *   methods. </li>
+ *
+ * </ul>
+ *
+ * <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
+ * 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 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
+ * sooner than) one year of continuous operation. A stamp held without
+ * use or validation for longer than this period may fail to validate
+ * correctly.  StampedLocks are serializable, but always deserialize
+ * 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.  All "try" methods are
+ * best-effort and do not necessarily conform to any scheduling or
+ * fairness policy. 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>Because it supports coordinated usage across multiple lock
+ * modes, this class does not directly implement the {@link Lock} or
+ * {@link ReadWriteLock} interfaces. However, a StampedLock may be
+ * viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link
+ * #asReadWriteLock()} in applications requiring only the associated
+ * set of functionality.
+ *
+ * <p><b>Sample Usage.</b> The following illustrates some usage idioms
+ * in a class that maintains simple two-dimensional points. The sample
+ * code illustrates some try/catch conventions even though they are
+ * not strictly needed here because no exceptions can occur in their
+ * bodies.<br>
+ *
+ *  <pre>{@code
+ * class Point {
+ *   private double x, y;
+ *   private final StampedLock sl = new StampedLock();
+ *
+ *   void move(double deltaX, double deltaY) { // an exclusively locked method
+ *     long stamp = sl.writeLock();
+ *     try {
+ *       x += deltaX;
+ *       y += deltaY;
+ *     } finally {
+ *       sl.unlockWrite(stamp);
+ *     }
+ *   }
+ *
+ *   double distanceFromOrigin() { // A read-only method
+ *     long stamp = sl.tryOptimisticRead();
+ *     double currentX = x, currentY = y;
+ *     if (!sl.validate(stamp)) {
+ *        stamp = sl.readLock();
+ *        try {
+ *          currentX = x;
+ *          currentY = y;
+ *        } finally {
+ *           sl.unlockRead(stamp);
+ *        }
+ *     }
+ *     return Math.sqrt(currentX * currentX + currentY * currentY);
+ *   }
+ *
+ *   void moveIfAtOrigin(double newX, double newY) { // upgrade
+ *     // Could instead start with optimistic, not read mode
+ *     long stamp = sl.readLock();
+ *     try {
+ *       while (x == 0.0 && y == 0.0) {
+ *         long ws = sl.tryConvertToWriteLock(stamp);
+ *         if (ws != 0L) {
+ *           stamp = ws;
+ *           x = newX;
+ *           y = newY;
+ *           break;
+ *         }
+ *         else {
+ *           sl.unlockRead(stamp);
+ *           stamp = sl.writeLock();
+ *         }
+ *       }
+ *     } finally {
+ *       sl.unlock(stamp);
+ *     }
+ *   }
+ * }}</pre>
+ *
+ * @since 1.8
+ * @author Doug Lea
+ */
+public class StampedLock implements java.io.Serializable {
+    /*
+     * Algorithmic notes:
+     *
+     * The design employs elements of Sequence locks
+     * (as used in linux kernels; see Lameter's
+     * http://www.lameter.com/gelato2005.pdf
+     * and elsewhere; see
+     * Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)
+     * and Ordered RW locks (see Shirako et al
+     * http://dl.acm.org/citation.cfm?id=2312015)
+     *
+     * Conceptually, the primary state of the lock includes a sequence
+     * number that is odd when write-locked and even otherwise.
+     * However, this is offset by a reader count that is non-zero when
+     * 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
+     * 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.
+     *
+     * Waiters use a modified form of CLH lock used in
+     * AbstractQueuedSynchronizer (see its internal documentation for
+     * a fuller account), where each node is tagged (field mode) as
+     * either a reader or writer. Sets of waiting readers are grouped
+     * (linked) under a common node (field cowait) so act as a single
+     * node with respect to most CLH mechanics.  By virtue of the
+     * queue structure, wait nodes need not actually carry sequence
+     * numbers; we know each is greater than its predecessor.  This
+     * simplifies the scheduling policy to a mainly-FIFO scheme that
+     * incorporates elements of Phase-Fair locks (see Brandenburg &
+     * Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
+     * particular, we use the phase-fair anti-barging rule: If an
+     * incoming reader arrives while read lock is held but there is a
+     * queued writer, this incoming reader is queued.  (This rule is
+     * responsible for some of the complexity of method acquireRead,
+     * but without it, the lock becomes highly unfair.)
+     *
+     * These rules apply to threads actually queued. All tryLock forms
+     * opportunistically try to acquire locks regardless of preference
+     * rules, and so may "barge" their way in.  Randomized spinning is
+     * used in the acquire methods to reduce (increasingly expensive)
+     * context switching while also avoiding sustained memory
+     * thrashing among many threads.  We limit spins to the head of
+     * queue. A thread spin-waits up to SPINS times (where each
+     * iteration decreases spin count with 50% probability) 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.
+     *
+     * Nearly all of these mechanics are carried out in methods
+     * acquireWrite and acquireRead, that, as typical of such code,
+     * sprawl out because actions and retries rely on consistent sets
+     * of locally cached reads.
+     *
+     * As noted in Boehm's paper (above), sequence validation (mainly
+     * method validate()) requires stricter ordering rules than apply
+     * to normal volatile reads (of "state").  To force orderings of
+     * reads before a validation and the validation itself in those
+     * cases where this is not already forced, we use
+     * Unsafe.loadFence.
+     *
+     * The memory layout keeps lock state and queue pointers together
+     * (normally on the same cache line). This usually works well for
+     * read-mostly loads. In most other cases, the natural tendency of
+     * adaptive-spin CLH locks to reduce memory contention lessens
+     * motivation to further spread out contended locations, but might
+     * 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 : 0;
+
+    /** Maximum number of retries before re-blocking */
+    private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 0;
+
+    /** 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;
+
+    // Values for lock state and stamp operations
+    private static final long RUNIT = 1L;
+    private static final long WBIT  = 1L << LG_READERS;
+    private static final long RBITS = WBIT - 1L;
+    private static final long RFULL = RBITS - 1L;
+    private static final long ABITS = RBITS | WBIT;
+    private static final long SBITS = ~RBITS; // note overlap with ABITS
+
+    // Initial value for lock state; avoid failure value zero
+    private static final long ORIGIN = WBIT << 1;
+
+    // Special value from cancelled acquire methods so caller can throw IE
+    private static final long INTERRUPTED = 1L;
+
+    // Values for node status; order matters
+    private static final int WAITING   = -1;
+    private static final int CANCELLED =  1;
+
+    // Modes for nodes (int not boolean to allow arithmetic)
+    private static final int RMODE = 0;
+    private static final int WMODE = 1;
+
+    /** Wait nodes */
+    static final class WNode {
+        volatile WNode prev;
+        volatile WNode next;
+        volatile WNode cowait;    // list of linked readers
+        volatile Thread thread;   // non-null while possibly parked
+        volatile int status;      // 0, WAITING, or CANCELLED
+        final int mode;           // RMODE or WMODE
+        WNode(int m, WNode p) { mode = m; prev = p; }
+    }
+
+    /** Head of CLH queue */
+    private transient volatile WNode whead;
+    /** Tail (last) of CLH queue */
+    private transient volatile WNode wtail;
+
+    // views
+    transient ReadLockView readLockView;
+    transient WriteLockView writeLockView;
+    transient ReadWriteLockView readWriteLockView;
+
+    /** Lock sequence/state */
+    private transient volatile long state;
+    /** extra reader count when state read count saturated */
+    private transient int readerOverflow;
+
+    /**
+     * Creates a new lock, initially in unlocked state.
+     */
+    public StampedLock() {
+        state = ORIGIN;
+    }
+
+    /**
+     * Exclusively acquires the lock, blocking if necessary
+     * until available.
+     *
+     * @return a stamp that can be used to unlock or convert mode
+     */
+    public long writeLock() {
+        long s, next;  // bypass acquireWrite in fully unlocked case only
+        return ((((s = state) & ABITS) == 0L &&
+                 U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
+                next : acquireWrite(false, 0L));
+    }
+
+    /**
+     * 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
+     */
+    public long tryWriteLock() {
+        long s, next;
+        return ((((s = state) & ABITS) == 0L &&
+                 U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
+                next : 0L);
+    }
+
+    /**
+     * Exclusively acquires the lock if it is available within the
+     * given time and the current thread has not been interrupted.
+     * Behavior under timeout and interruption matches that specified
+     * for method {@link Lock#tryLock(long,TimeUnit)}.
+     *
+     * @return a stamp that can be used to unlock or convert mode,
+     * or zero if the lock is not available
+     * @throws InterruptedException if the current thread is interrupted
+     * before acquiring the lock
+     */
+    public long tryWriteLock(long time, TimeUnit unit)
+        throws InterruptedException {
+        long nanos = unit.toNanos(time);
+        if (!Thread.interrupted()) {
+            long next, deadline;
+            if ((next = tryWriteLock()) != 0L)
+                return next;
+            if (nanos <= 0L)
+                return 0L;
+            if ((deadline = System.nanoTime() + nanos) == 0L)
+                deadline = 1L;
+            if ((next = acquireWrite(true, deadline)) != INTERRUPTED)
+                return next;
+        }
+        throw new InterruptedException();
+    }
+
+    /**
+     * Exclusively acquires the lock, blocking if necessary
+     * until available or the current thread is interrupted.
+     * Behavior under interruption matches that specified
+     * for method {@link Lock#lockInterruptibly()}.
+     *
+     * @return a stamp that can be used to unlock or convert mode
+     * @throws InterruptedException if the current thread is interrupted
+     * before acquiring the lock
+     */
+    public long writeLockInterruptibly() throws InterruptedException {
+        long next;
+        if (!Thread.interrupted() &&
+            (next = acquireWrite(true, 0L)) != INTERRUPTED)
+            return next;
+        throw new InterruptedException();
+    }
+
+    /**
+     * Non-exclusively acquires the lock, blocking if necessary
+     * until available.
+     *
+     * @return a stamp that can be used to unlock or convert mode
+     */
+    public long readLock() {
+        long s, next;  // bypass acquireRead on fully unlocked case only
+        return ((((s = state) & ABITS) == 0L &&
+                 U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
+                next : acquireRead(false, 0L));
+    }
+
+    /**
+     * 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
+     */
+    public long tryReadLock() {
+        for (;;) {
+            long s, m, next;
+            if ((m = (s = state) & ABITS) == WBIT)
+                return 0L;
+            else if (m < RFULL) {
+                if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
+                    return next;
+            }
+            else if ((next = tryIncReaderOverflow(s)) != 0L)
+                return next;
+        }
+    }
+
+    /**
+     * Non-exclusively acquires the lock if it is available within the
+     * given time and the current thread has not been interrupted.
+     * Behavior under timeout and interruption matches that specified
+     * for method {@link Lock#tryLock(long,TimeUnit)}.
+     *
+     * @return a stamp that can be used to unlock or convert mode,
+     * or zero if the lock is not available
+     * @throws InterruptedException if the current thread is interrupted
+     * before acquiring the lock
+     */
+    public long tryReadLock(long time, TimeUnit unit)
+        throws InterruptedException {
+        long s, m, next, deadline;
+        long nanos = unit.toNanos(time);
+        if (!Thread.interrupted()) {
+            if ((m = (s = state) & ABITS) != WBIT) {
+                if (m < RFULL) {
+                    if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
+                        return next;
+                }
+                else if ((next = tryIncReaderOverflow(s)) != 0L)
+                    return next;
+            }
+            if (nanos <= 0L)
+                return 0L;
+            if ((deadline = System.nanoTime() + nanos) == 0L)
+                deadline = 1L;
+            if ((next = acquireRead(true, deadline)) != INTERRUPTED)
+                return next;
+        }
+        throw new InterruptedException();
+    }
+
+    /**
+     * Non-exclusively acquires the lock, blocking if necessary
+     * until available or the current thread is interrupted.
+     * Behavior under interruption matches that specified
+     * for method {@link Lock#lockInterruptibly()}.
+     *
+     * @return a stamp that can be used to unlock or convert mode
+     * @throws InterruptedException if the current thread is interrupted
+     * before acquiring the lock
+     */
+    public long readLockInterruptibly() throws InterruptedException {
+        long next;
+        if (!Thread.interrupted() &&
+            (next = acquireRead(true, 0L)) != INTERRUPTED)
+            return next;
+        throw new InterruptedException();
+    }
+
+    /**
+     * Returns a stamp that can later be validated, or zero
+     * if exclusively locked.
+     *
+     * @return a stamp, or zero if exclusively locked
+     */
+    public long tryOptimisticRead() {
+        long s;
+        return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L;
+    }
+
+    /**
+     * 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. Invoking this method with a value not
+     * obtained from {@link #tryOptimisticRead} or a locking method
+     * for this lock has no defined effect or result.
+     *
+     * @return true if the lock has not been exclusively acquired
+     * since issuance of the given stamp; else false
+     */
+    public boolean validate(long stamp) {
+        U.loadFence();
+        return (stamp & SBITS) == (state & SBITS);
+    }
+
+    /**
+     * If the lock state matches the given stamp, releases the
+     * exclusive lock.
+     *
+     * @param stamp a stamp returned by a write-lock operation
+     * @throws IllegalMonitorStateException if the stamp does
+     * not match the current state of this lock
+     */
+    public void unlockWrite(long stamp) {
+        WNode h;
+        if (state != stamp || (stamp & WBIT) == 0L)
+            throw new IllegalMonitorStateException();
+        state = (stamp += WBIT) == 0L ? ORIGIN : stamp;
+        if ((h = whead) != null && h.status != 0)
+            release(h);
+    }
+
+    /**
+     * 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
+     */
+    public void unlockRead(long stamp) {
+        long s, m; WNode h;
+        for (;;) {
+            if (((s = state) & SBITS) != (stamp & SBITS) ||
+                (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
+                throw new IllegalMonitorStateException();
+            if (m < RFULL) {
+                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
+                    if (m == RUNIT && (h = whead) != null && h.status != 0)
+                        release(h);
+                    break;
+                }
+            }
+            else if (tryDecReaderOverflow(s) != 0L)
+                break;
+        }
+    }
+
+    /**
+     * If the lock state matches the given stamp, releases the
+     * corresponding mode of the lock.
+     *
+     * @param stamp a stamp returned by a lock operation
+     * @throws IllegalMonitorStateException if the stamp does
+     * not match the current state of this lock
+     */
+    public void unlock(long stamp) {
+        long a = stamp & ABITS, m, s; WNode h;
+        while (((s = state) & SBITS) == (stamp & SBITS)) {
+            if ((m = s & ABITS) == 0L)
+                break;
+            else if (m == WBIT) {
+                if (a != m)
+                    break;
+                state = (s += WBIT) == 0L ? ORIGIN : s;
+                if ((h = whead) != null && h.status != 0)
+                    release(h);
+                return;
+            }
+            else if (a == 0L || a >= WBIT)
+                break;
+            else if (m < RFULL) {
+                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
+                    if (m == RUNIT && (h = whead) != null && h.status != 0)
+                        release(h);
+                    return;
+                }
+            }
+            else if (tryDecReaderOverflow(s) != 0L)
+                return;
+        }
+        throw new IllegalMonitorStateException();
+    }
+
+    /**
+     * If the lock state matches the given stamp, 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 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
+     */
+    public long tryConvertToWriteLock(long stamp) {
+        long a = stamp & ABITS, m, s, next;
+        while (((s = state) & SBITS) == (stamp & SBITS)) {
+            if ((m = s & ABITS) == 0L) {
+                if (a != 0L)
+                    break;
+                if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
+                    return next;
+            }
+            else if (m == WBIT) {
+                if (a != m)
+                    break;
+                return stamp;
+            }
+            else if (m == RUNIT && a != 0L) {
+                if (U.compareAndSwapLong(this, STATE, s,
+                                         next = s - RUNIT + WBIT))
+                    return next;
+            }
+            else
+                break;
+        }
+        return 0L;
+    }
+
+    /**
+     * If the lock state matches the given stamp, performs one of
+     * the following actions. If the stamp represents holding a write
+     * lock, releases it and obtains a read lock.  Or, if a read lock,
+     * returns it. Or, if an optimistic read, acquires a read lock and
+     * returns a read stamp only if immediately available. This method
+     * returns zero in all other cases.
+     *
+     * @param stamp a stamp
+     * @return a valid read stamp, or zero on failure
+     */
+    public long tryConvertToReadLock(long stamp) {
+        long a = stamp & ABITS, m, s, next; WNode h;
+        while (((s = state) & SBITS) == (stamp & SBITS)) {
+            if ((m = s & ABITS) == 0L) {
+                if (a != 0L)
+                    break;
+                else if (m < RFULL) {
+                    if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
+                        return next;
+                }
+                else if ((next = tryIncReaderOverflow(s)) != 0L)
+                    return next;
+            }
+            else if (m == WBIT) {
+                if (a != m)
+                    break;
+                state = next = s + (WBIT + RUNIT);
+                if ((h = whead) != null && h.status != 0)
+                    release(h);
+                return next;
+            }
+            else if (a != 0L && a < WBIT)
+                return stamp;
+            else
+                break;
+        }
+        return 0L;
+    }
+
+    /**
+     * If the lock state matches the given stamp then, if the stamp
+     * represents holding a lock, releases it and returns an
+     * observation stamp.  Or, if an optimistic read, returns it if
+     * validated. This method returns zero in all other cases, and so
+     * may be useful as a form of "tryUnlock".
+     *
+     * @param stamp a stamp
+     * @return a valid optimistic read stamp, or zero on failure
+     */
+    public long tryConvertToOptimisticRead(long stamp) {
+        long a = stamp & ABITS, m, s, next; WNode h;
+        U.loadFence();
+        for (;;) {
+            if (((s = state) & SBITS) != (stamp & SBITS))
+                break;
+            if ((m = s & ABITS) == 0L) {
+                if (a != 0L)
+                    break;
+                return s;
+            }
+            else if (m == WBIT) {
+                if (a != m)
+                    break;
+                state = next = (s += WBIT) == 0L ? ORIGIN : s;
+                if ((h = whead) != null && h.status != 0)
+                    release(h);
+                return next;
+            }
+            else if (a == 0L || a >= WBIT)
+                break;
+            else if (m < RFULL) {
+                if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {
+                    if (m == RUNIT && (h = whead) != null && h.status != 0)
+                        release(h);
+                    return next & SBITS;
+                }
+            }
+            else if ((next = tryDecReaderOverflow(s)) != 0L)
+                return next & SBITS;
+        }
+        return 0L;
+    }
+
+    /**
+     * Releases the write lock if it is held, without requiring a
+     * stamp value. This method may be useful for recovery after
+     * errors.
+     *
+     * @return true if the lock was held, else false
+     */
+    public boolean tryUnlockWrite() {
+        long s; WNode h;
+        if (((s = state) & WBIT) != 0L) {
+            state = (s += WBIT) == 0L ? ORIGIN : s;
+            if ((h = whead) != null && h.status != 0)
+                release(h);
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * Releases one hold of the read lock if it is held, without
+     * requiring a stamp value. This method may be useful for recovery
+     * after errors.
+     *
+     * @return true if the read lock was held, else false
+     */
+    public boolean tryUnlockRead() {
+        long s, m; WNode h;
+        while ((m = (s = state) & ABITS) != 0L && m < WBIT) {
+            if (m < RFULL) {
+                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
+                    if (m == RUNIT && (h = whead) != null && h.status != 0)
+                        release(h);
+                    return true;
+                }
+            }
+            else if (tryDecReaderOverflow(s) != 0L)
+                return true;
+        }
+        return false;
+    }
+
+    // status monitoring methods
+
+    /**
+     * Returns combined state-held and overflow read count for given
+     * state s.
+     */
+    private int getReadLockCount(long s) {
+        long readers;
+        if ((readers = s & RBITS) >= RFULL)
+            readers = RFULL + readerOverflow;
+        return (int) readers;
+    }
+
+    /**
+     * Returns true if the lock is currently held exclusively.
+     *
+     * @return true if the lock is currently held exclusively
+     */
+    public boolean isWriteLocked() {
+        return (state & WBIT) != 0L;
+    }
+
+    /**
+     * Returns true if the lock is currently held non-exclusively.
+     *
+     * @return true if the lock is currently held non-exclusively
+     */
+    public boolean isReadLocked() {
+        return (state & RBITS) != 0L;
+    }
+
+    /**
+     * Queries the number of read locks held for this lock. This
+     * method is designed for use in monitoring system state, not for
+     * synchronization control.
+     * @return the number of read locks held
+     */
+    public int getReadLockCount() {
+        return getReadLockCount(state);
+    }
+
+    /**
+     * Returns a string identifying this lock, as well as its lock
+     * state.  The state, in brackets, includes the String {@code
+     * "Unlocked"} or the String {@code "Write-locked"} or the String
+     * {@code "Read-locks:"} followed by the current number of
+     * read-locks held.
+     *
+     * @return a string identifying this lock, as well as its lock state
+     */
+    public String toString() {
+        long s = state;
+        return super.toString() +
+            ((s & ABITS) == 0L ? "[Unlocked]" :
+             (s & WBIT) != 0L ? "[Write-locked]" :
+             "[Read-locks:" + getReadLockCount(s) + "]");
+    }
+
+    // views
+
+    /**
+     * Returns a plain {@link Lock} view of this StampedLock in which
+     * the {@link Lock#lock} method is mapped to {@link #readLock},
+     * and similarly for other methods. The returned Lock does not
+     * support a {@link Condition}; method {@link
+     * Lock#newCondition()} throws {@code
+     * UnsupportedOperationException}.
+     *
+     * @return the lock
+     */
+    public Lock asReadLock() {
+        ReadLockView v;
+        return ((v = readLockView) != null ? v :
+                (readLockView = new ReadLockView()));
+    }
+
+    /**
+     * Returns a plain {@link Lock} view of this StampedLock in which
+     * the {@link Lock#lock} method is mapped to {@link #writeLock},
+     * and similarly for other methods. The returned Lock does not
+     * support a {@link Condition}; method {@link
+     * Lock#newCondition()} throws {@code
+     * UnsupportedOperationException}.
+     *
+     * @return the lock
+     */
+    public Lock asWriteLock() {
+        WriteLockView v;
+        return ((v = writeLockView) != null ? v :
+                (writeLockView = new WriteLockView()));
+    }
+
+    /**
+     * Returns a {@link ReadWriteLock} view of this StampedLock in
+     * which the {@link ReadWriteLock#readLock()} method is mapped to
+     * {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to
+     * {@link #asWriteLock()}.
+     *
+     * @return the lock
+     */
+    public ReadWriteLock asReadWriteLock() {
+        ReadWriteLockView v;
+        return ((v = readWriteLockView) != null ? v :
+                (readWriteLockView = new ReadWriteLockView()));
+    }
+
+    // view classes
+
+    final class ReadLockView implements Lock {
+        public void lock() { readLock(); }
+        public void lockInterruptibly() throws InterruptedException {
+            readLockInterruptibly();
+        }
+        public boolean tryLock() { return tryReadLock() != 0L; }
+        public boolean tryLock(long time, TimeUnit unit)
+            throws InterruptedException {
+            return tryReadLock(time, unit) != 0L;
+        }
+        public void unlock() { unstampedUnlockRead(); }
+        public Condition newCondition() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    final class WriteLockView implements Lock {
+        public void lock() { writeLock(); }
+        public void lockInterruptibly() throws InterruptedException {
+            writeLockInterruptibly();
+        }
+        public boolean tryLock() { return tryWriteLock() != 0L; }
+        public boolean tryLock(long time, TimeUnit unit)
+            throws InterruptedException {
+            return tryWriteLock(time, unit) != 0L;
+        }
+        public void unlock() { unstampedUnlockWrite(); }
+        public Condition newCondition() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    final class ReadWriteLockView implements ReadWriteLock {
+        public Lock readLock() { return asReadLock(); }
+        public Lock writeLock() { return asWriteLock(); }
+    }
+
+    // Unlock methods without stamp argument checks for view classes.
+    // Needed because view-class lock methods throw away stamps.
+
+    final void unstampedUnlockWrite() {
+        WNode h; long s;
+        if (((s = state) & WBIT) == 0L)
+            throw new IllegalMonitorStateException();
+        state = (s += WBIT) == 0L ? ORIGIN : s;
+        if ((h = whead) != null && h.status != 0)
+            release(h);
+    }
+
+    final void unstampedUnlockRead() {
+        for (;;) {
+            long s, m; WNode h;
+            if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
+                throw new IllegalMonitorStateException();
+            else if (m < RFULL) {
+                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
+                    if (m == RUNIT && (h = whead) != null && h.status != 0)
+                        release(h);
+                    break;
+                }
+            }
+            else if (tryDecReaderOverflow(s) != 0L)
+                break;
+        }
+    }
+
+    private void readObject(java.io.ObjectInputStream s)
+        throws java.io.IOException, ClassNotFoundException {
+        s.defaultReadObject();
+        state = ORIGIN; // reset to unlocked state
+    }
+
+    // internals
+
+    /**
+     * Tries to increment readerOverflow by first setting state
+     * access bits value to RBITS, indicating hold of spinlock,
+     * then updating, then releasing.
+     *
+     * @param s a reader overflow stamp: (s & ABITS) >= RFULL
+     * @return new stamp on success, else zero
+     */
+    private long tryIncReaderOverflow(long s) {
+        // assert (s & ABITS) >= RFULL;
+        if ((s & ABITS) == RFULL) {
+            if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
+                ++readerOverflow;
+                state = s;
+                return s;
+            }
+        }
+        else if ((LockSupport.nextSecondarySeed() &
+                  OVERFLOW_YIELD_RATE) == 0)
+            Thread.yield();
+        return 0L;
+    }
+
+    /**
+     * Tries to decrement readerOverflow.
+     *
+     * @param s a reader overflow stamp: (s & ABITS) >= RFULL
+     * @return new stamp on success, else zero
+     */
+    private long tryDecReaderOverflow(long s) {
+        // assert (s & ABITS) >= RFULL;
+        if ((s & ABITS) == RFULL) {
+            if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
+                int r; long next;
+                if ((r = readerOverflow) > 0) {
+                    readerOverflow = r - 1;
+                    next = s;
+                }
+                else
+                    next = s - RUNIT;
+                 state = next;
+                 return next;
+            }
+        }
+        else if ((LockSupport.nextSecondarySeed() &
+                  OVERFLOW_YIELD_RATE) == 0)
+            Thread.yield();
+        return 0L;
+    }
+
+    /**
+     * Wakes up the successor of h (normally whead). This is normally
+     * just h.next, but may require traversal from wtail if next
+     * pointers are lagging. This may fail to wake up an acquiring
+     * thread when one or more have been cancelled, but the cancel
+     * methods themselves provide extra safeguards to ensure liveness.
+     */
+    private void release(WNode h) {
+        if (h != null) {
+            WNode q; Thread w;
+            U.compareAndSwapInt(h, WSTATUS, WAITING, 0);
+            if ((q = h.next) == null || q.status == CANCELLED) {
+                for (WNode t = wtail; t != null && t != h; t = t.prev)
+                    if (t.status <= 0)
+                        q = t;
+            }
+            if (q != null) {
+                for (WNode r = q;;) {  // release co-waiters too
+                    if ((w = r.thread) != null) {
+                        r.thread = null;
+                        U.unpark(w);
+                    }
+                    if ((r = q.cowait) == null)
+                        break;
+                    U.compareAndSwapObject(q, WCOWAIT, r, r.cowait);
+                }
+            }
+        }
+    }
+
+    /**
+     * See above for explanation.
+     *
+     * @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)
+     * @return next state, or INTERRUPTED
+     */
+    private long acquireWrite(boolean interruptible, long deadline) {
+        WNode node = null, p;
+        for (int spins = -1;;) { // spin while enqueuing
+            long s, ns;
+            if (((s = state) & ABITS) == 0L) {
+                if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
+                    return ns;
+            }
+            else if (spins > 0) {
+                if (LockSupport.nextSecondarySeed() >= 0)
+                    --spins;
+            }
+            else if ((p = wtail) == null) { // initialize queue
+                WNode h = new WNode(WMODE, null);
+                if (U.compareAndSwapObject(this, WHEAD, null, h))
+                    wtail = h;
+            }
+            else if (spins < 0)
+                spins = (p == whead) ? SPINS : 0;
+            else if (node == null)
+                node = new WNode(WMODE, p);
+            else if (node.prev != p)
+                node.prev = p;
+            else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
+                p.next = node;
+                break;
+            }
+        }
+
+        for (int spins = SPINS;;) {
+            WNode np, pp; int ps; long s, ns; Thread w;
+            while ((np = node.prev) != p && np != null)
+                (p = np).next = node;   // stale
+            if (whead == p) {
+                for (int k = spins;;) { // spin at head
+                    if (((s = state) & ABITS) == 0L) {
+                        if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
+                            whead = node;
+                            node.prev = null;
+                            return ns;
+                        }
+                    }
+                    else if (LockSupport.nextSecondarySeed() >= 0 &&
+                             --k <= 0)
+                        break;
+                }
+                if (spins < MAX_HEAD_SPINS)
+                    spins <<= 1;
+            }
+            if ((ps = p.status) == 0)
+                U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
+            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)
+                    time = 0L;
+                else if ((time = deadline - System.nanoTime()) <= 0L)
+                    return cancelWaiter(node, node, false);
+                Thread wt = Thread.currentThread();
+                U.putObject(wt, PARKBLOCKER, this); // emulate LockSupport.park
+                node.thread = wt;
+                if (node.prev == p && p.status == WAITING && // recheck
+                    (p != whead || (state & ABITS) != 0L))
+                    U.park(false, time);
+                node.thread = null;
+                U.putObject(wt, PARKBLOCKER, null);
+                if (interruptible && Thread.interrupted())
+                    return cancelWaiter(node, node, true);
+            }
+        }
+    }
+
+    /**
+     * See above for explanation.
+     *
+     * @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)
+     * @return next state, or INTERRUPTED
+     */
+    private long acquireRead(boolean interruptible, long deadline) {
+        WNode node = null, group = null, p;
+        for (int spins = -1;;) {
+            for (;;) {
+                long s, m, ns; WNode h, q; Thread w; // anti-barging guard
+                if (group == null && (h = whead) != null &&
+                    (q = h.next) != null && q.mode != RMODE)
+                    break;
+                if ((m = (s = state) & ABITS) < RFULL ?
+                    U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
+                    (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
+                    if (group != null) {  // help release others
+                        for (WNode r = group;;) {
+                            if ((w = r.thread) != null) {
+                                r.thread = null;
+                                U.unpark(w);
+                            }
+                            if ((r = group.cowait) == null)
+                                break;
+                            U.compareAndSwapObject(group, WCOWAIT, r, r.cowait);
+                        }
+                    }
+                    return ns;
+                }
+                if (m >= WBIT)
+                    break;
+            }
+            if (spins > 0) {
+                if (LockSupport.nextSecondarySeed() >= 0)
+                    --spins;
+            }
+            else if ((p = wtail) == null) {
+                WNode h = new WNode(WMODE, null);
+                if (U.compareAndSwapObject(this, WHEAD, null, h))
+                    wtail = h;
+            }
+            else if (spins < 0)
+                spins = (p == whead) ? SPINS : 0;
+            else if (node == null)
+                node = new WNode(WMODE, p);
+            else if (node.prev != p)
+                node.prev = p;
+            else if (p.mode == RMODE && p != whead) {
+                WNode pp = p.prev;  // become co-waiter with group p
+                if (pp != null && p == wtail &&
+                    U.compareAndSwapObject(p, WCOWAIT,
+                                           node.cowait = p.cowait, node)) {
+                    node.thread = Thread.currentThread();
+                    for (long time;;) {
+                        if (deadline == 0L)
+                            time = 0L;
+                        else if ((time = deadline - System.nanoTime()) <= 0L)
+                            return cancelWaiter(node, p, false);
+                        if (node.thread == null)
+                            break;
+                        if (p.prev != pp || p.status == CANCELLED ||
+                            p == whead || p.prev != pp) {
+                            node.thread = null;
+                            break;
+                        }
+                        Thread wt = Thread.currentThread();
+                        U.putObject(wt, PARKBLOCKER, this);
+                        if (node.thread == null) // must recheck
+                            break;
+                        U.park(false, time);
+                        U.putObject(wt, PARKBLOCKER, null);
+                        if (interruptible && Thread.interrupted())
+                            return cancelWaiter(node, p, true);
+                    }
+                    group = p;
+                }
+                node = null; // throw away
+            }
+            else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
+                p.next = node;
+                break;
+            }
+        }
+
+        for (int spins = SPINS;;) {
+            WNode np, pp, r; int ps; long m, s, ns; Thread w;
+            while ((np = node.prev) != p && np != null)
+                (p = np).next = node;
+            if (whead == p) {
+                for (int k = spins;;) {
+                    if ((m = (s = state) & ABITS) != WBIT) {
+                        if (m < RFULL ?
+                            U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT):
+                            (ns = tryIncReaderOverflow(s)) != 0L) {
+                            whead = node;
+                            node.prev = null;
+                            while ((r = node.cowait) != null) {
+                                if (U.compareAndSwapObject(node, WCOWAIT,
+                                                           r, r.cowait) &&
+                                    (w = r.thread) != null) {
+                                    r.thread = null;
+                                    U.unpark(w); // release co-waiter
+                                }
+                            }
+                            return ns;
+                        }
+                    }
+                    else if (LockSupport.nextSecondarySeed() >= 0 &&
+                             --k <= 0)
+                        break;
+                }
+                if (spins < MAX_HEAD_SPINS)
+                    spins <<= 1;
+            }
+            if ((ps = p.status) == 0)
+                U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
+            else if (ps == CANCELLED) {
+                if ((pp = p.prev) != null) {
+                    node.prev = pp;
+                    pp.next = node;
+                }
+            }
+            else {
+                long time;
+                if (deadline == 0L)
+                    time = 0L;
+                else if ((time = deadline - System.nanoTime()) <= 0L)
+                    return cancelWaiter(node, node, false);
+                Thread wt = Thread.currentThread();
+                U.putObject(wt, PARKBLOCKER, this);
+                node.thread = wt;
+                if (node.prev == p && p.status == WAITING &&
+                    (p != whead || (state & ABITS) != WBIT))
+                    U.park(false, time);
+                node.thread = null;
+                U.putObject(wt, PARKBLOCKER, null);
+                if (interruptible && Thread.interrupted())
+                    return cancelWaiter(node, node, true);
+            }
+        }
+    }
+
+    /**
+     * If node non-null, forces cancel status and unsplices it from
+     * queue if possible and wakes up any cowaiters (of the node, or
+     * group, as applicable), and in any case helps release current
+     * first waiter if lock is free. (Calling with null arguments
+     * serves as a conditional form of release, which is not currently
+     * needed but may be needed under possible future cancellation
+     * policies). This is a variant of cancellation methods in
+     * AbstractQueuedSynchronizer (see its detailed explanation in AQS
+     * internal documentation).
+     *
+     * @param node if nonnull, the waiter
+     * @param group either node or the group node is cowaiting with
+     * @param interrupted if already interrupted
+     * @return INTERRUPTED if interrupted or Thread.interrupted, else zero
+     */
+    private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
+        if (node != null && group != null) {
+            Thread w;
+            node.status = CANCELLED;
+            node.thread = null;
+            // unsplice cancelled nodes from group
+            for (WNode p = group, q; (q = p.cowait) != null;) {
+                if (q.status == CANCELLED)
+                    U.compareAndSwapObject(p, WNEXT, q, q.next);
+                else
+                    p = q;
+            }
+            if (group == node) {
+                WNode r; // detach and wake up uncancelled co-waiters
+                while ((r = node.cowait) != null) {
+                    if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
+                        (w = r.thread) != null) {
+                        r.thread = null;
+                        U.unpark(w);
+                    }
+                }
+                for (WNode pred = node.prev; pred != null; ) { // unsplice
+                    WNode succ, pp;        // find valid successor
+                    while ((succ = node.next) == null ||
+                           succ.status == CANCELLED) {
+                        WNode q = null;    // find successor the slow way
+                        for (WNode t = wtail; t != null && t != node; t = t.prev)
+                            if (t.status != CANCELLED)
+                                q = t;     // don't link if succ cancelled
+                        if (succ == q ||   // ensure accurate successor
+                            U.compareAndSwapObject(node, WNEXT,
+                                                   succ, succ = q)) {
+                            if (succ == null && node == wtail)
+                                U.compareAndSwapObject(this, WTAIL, node, pred);
+                            break;
+                        }
+                    }
+                    if (pred.next == node) // unsplice pred link
+                        U.compareAndSwapObject(pred, WNEXT, node, succ);
+                    if (succ != null && (w = succ.thread) != null) {
+                        succ.thread = null;
+                        U.unpark(w);       // wake up succ to observe new pred
+                    }
+                    if (pred.status != CANCELLED || (pp = pred.prev) == null)
+                        break;
+                    node.prev = pp;        // repeat if new pred wrong/cancelled
+                    U.compareAndSwapObject(pp, WNEXT, pred, succ);
+                    pred = pp;
+                }
+            }
+        }
+        WNode h; // Possibly release first waiter
+        while ((h = whead) != null) {
+            long s; WNode q; // similar to release() but check eligibility
+            if ((q = h.next) == null || q.status == CANCELLED) {
+                for (WNode t = wtail; t != null && t != h; t = t.prev)
+                    if (t.status <= 0)
+                        q = t;
+            }
+            if (h == whead) {
+                if (q != null && h.status == 0 &&
+                    ((s = state) & ABITS) != WBIT && // waiter is eligible
+                    (s == 0L || q.mode == RMODE))
+                    release(h);
+                break;
+            }
+        }
+        return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
+    }
+
+    // Unsafe mechanics
+    private static final sun.misc.Unsafe U;
+    private static final long STATE;
+    private static final long WHEAD;
+    private static final long WTAIL;
+    private static final long WNEXT;
+    private static final long WSTATUS;
+    private static final long WCOWAIT;
+    private static final long PARKBLOCKER;
+
+    static {
+        try {
+            U = sun.misc.Unsafe.getUnsafe();
+            Class<?> k = StampedLock.class;
+            Class<?> wk = WNode.class;
+            STATE = U.objectFieldOffset
+                (k.getDeclaredField("state"));
+            WHEAD = U.objectFieldOffset
+                (k.getDeclaredField("whead"));
+            WTAIL = U.objectFieldOffset
+                (k.getDeclaredField("wtail"));
+            WSTATUS = U.objectFieldOffset
+                (wk.getDeclaredField("status"));
+            WNEXT = U.objectFieldOffset
+                (wk.getDeclaredField("next"));
+            WCOWAIT = U.objectFieldOffset
+                (wk.getDeclaredField("cowait"));
+            Class<?> tk = Thread.class;
+            PARKBLOCKER = U.objectFieldOffset
+                (tk.getDeclaredField("parkBlocker"));
+
+        } catch (Exception e) {
+            throw new Error(e);
+        }
+    }
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/test/java/util/concurrent/locks/StampedLock/Basic.java	Sat Feb 09 08:35:57 2013 +0000
@@ -0,0 +1,609 @@
+/*
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+
+/*
+ * This file is available under and governed by the GNU General Public
+ * License version 2 only, as published by the Free Software Foundation.
+ * However, the following notice accompanied the original version of this
+ * file:
+ *
+ * Written by Doug Lea with assistance from members of JCP JSR-166
+ * Expert Group and released to the public domain, as explained at
+ * http://creativecommons.org/publicdomain/zero/1.0/
+ */
+
+/*
+ * @test
+ * @bug 8005697
+ * @summary Basic tests for StampedLock
+ * @author Chris Hegarty
+ */
+
+import java.util.Iterator;
+import java.util.concurrent.Phaser;
+import java.util.concurrent.TimeUnit;
+import static java.util.concurrent.TimeUnit.*;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.concurrent.locks.Lock;
+import java.util.concurrent.locks.ReadWriteLock;
+import java.util.concurrent.locks.StampedLock;
+
+public class Basic {
+
+    static void checkResult(Locker l, Class<? extends Throwable> c) {
+        Throwable t = l.thrown();
+        if (! ((t == null && c == null) || (c != null && c.isInstance(t)))) {
+            fail("Mismatch in thread " +
+                 l.getName() + ": " +
+                 t + ", " +
+                 (c == null ? "<null>" : c.getName()));
+        }
+
+        if (c == null)
+            check(l.stamp() != 0L);  // must have acquired the lock
+        else
+            check(l.stamp() == 0L);  // must NOT have acquired the lock
+    }
+
+    //----------------------------------------------------------------
+    // Mechanism to get all test threads into "running" mode.
+    //----------------------------------------------------------------
+    static void toTheStartingGate(Phaser gate) {
+        try {
+            gate.arriveAndAwaitAdvance();
+        } catch (Throwable t) {
+            unexpected(t);
+        }
+    }
+
+    static abstract class Locker extends Thread {
+        static AtomicInteger count = new AtomicInteger(1);
+        private volatile Throwable thrown;
+        private volatile long stamp;;
+        protected void thrown(Throwable thrown) { this.thrown = thrown; }
+        public Throwable thrown() { return thrown; }
+        protected void stamp(long stamp) { this.stamp = stamp; }
+        public long stamp() { return stamp; }
+
+        Locker() {
+            this("Locker");
+        }
+
+        Locker(String name) {
+            this.setName(name + ":" + count.getAndIncrement());
+            this.setDaemon(true);
+        }
+    }
+
+    static abstract class Reader extends Locker {
+        Reader() { super("Reader"); }
+        Reader(String name) { super(name); }
+    }
+
+    static Reader reader(final StampedLock sl, final Phaser gate) {
+        return new Reader() { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            stamp(sl.readLock());
+            try {
+                check(sl.validate(stamp()));
+                check(sl.isReadLocked());
+                check(!sl.isWriteLocked());
+            } finally { sl.unlockRead(stamp()); } }};
+    }
+
+    static Reader readerView(final StampedLock sl, final Phaser gate) {
+        return new Reader("ReaderView") { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            final Lock rl = sl.asReadLock();
+            rl.lock();
+            try {
+                stamp(1L);   // got the lock
+                check(sl.isReadLocked());
+                check(!sl.isWriteLocked());
+            } finally { rl.unlock(); } }};
+    }
+
+    static Reader reader(StampedLock sl, Phaser gate, boolean view) {
+        return view ? readerView(sl, gate) : reader(sl, gate);
+    }
+
+    static Reader interruptibleReader(final StampedLock sl,
+                                      final long timeout,
+                                      final TimeUnit unit,
+                                      final Phaser gate) {
+        return new Reader("InterruptibleReader") { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            try {
+                if (timeout < 0)
+                    stamp(sl.readLockInterruptibly());
+                else
+                    stamp(sl.tryReadLock(timeout, unit));
+                check(sl.validate(stamp()));
+                check(sl.isReadLocked());
+                check(!sl.isWriteLocked());
+            } catch (Throwable x) { thrown(x);
+            } finally { if (stamp() != 0L) sl.unlockRead(stamp()); } }};
+    }
+
+    static Reader interruptibleReaderView(final StampedLock sl,
+                                          final long timeout,
+                                          final TimeUnit unit,
+                                          final Phaser gate) {
+        return new Reader("InterruptibleReaderView") { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            final Lock rl = sl.asReadLock();
+
+            try {
+                if (timeout < 0)
+                    rl.lockInterruptibly();
+                else
+                    rl.tryLock(timeout, unit);
+                stamp(1L);  // got the lock
+                check(sl.isReadLocked());
+                check(!sl.isWriteLocked());
+            } catch (Throwable x) { thrown(x);
+            } finally { if (stamp() != 0L) rl.unlock(); } }};
+    }
+
+    static Reader interruptibleReader(final StampedLock sl,
+                                      final long timeout,
+                                      final TimeUnit unit,
+                                      final Phaser gate,
+                                      final boolean view) {
+        return view ? interruptibleReaderView(sl, timeout, unit, gate)
+                    : interruptibleReader(sl, timeout, unit, gate);
+    }
+
+    static abstract class Writer extends Locker {
+        Writer() { super("Writer"); }
+        Writer(String name) { super(name); }
+    }
+
+    static Writer writer(final StampedLock sl, final Phaser gate) {
+        return new Writer() { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            try {
+                stamp(sl.writeLock());
+                check(sl.validate(stamp()));
+                check(!sl.isReadLocked());
+                check(sl.isWriteLocked());
+            } finally { sl.unlockWrite(stamp()); } }};
+    }
+
+    static Writer writerView(final StampedLock sl, final Phaser gate) {
+        return new Writer("WriterView") { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            Lock wl = sl.asWriteLock();
+            wl.lock();
+            try {
+                stamp(1L);  // got the lock
+                check(!sl.isReadLocked());
+                check(sl.isWriteLocked());
+            } finally { wl.unlock(); } }};
+    }
+
+    static Writer writer(StampedLock sl, Phaser gate, boolean view) {
+        return view ? writerView(sl, gate) : writer(sl, gate);
+    }
+
+    static Writer interruptibleWriter(final StampedLock sl,
+                                      final long timeout,
+                                      final TimeUnit unit,
+                                      final Phaser gate) {
+        return new Writer("InterruptibleWriter") { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            try {
+                if (timeout < 0)
+                    stamp(sl.writeLockInterruptibly());
+                else
+                    stamp(sl.tryWriteLock(timeout, unit));
+                check(sl.validate(stamp()));
+                check(!sl.isReadLocked());
+                check(sl.isWriteLocked());
+            } catch (Throwable x) { thrown(x);
+            } finally { if (stamp() != 0L) sl.unlockWrite(stamp()); } }};
+    }
+
+    static Writer interruptibleWriterView(final StampedLock sl,
+                                          final long timeout,
+                                          final TimeUnit unit,
+                                          final Phaser gate) {
+        return new Writer("InterruptibleWriterView") { public void run() {
+            if (gate != null ) toTheStartingGate(gate);
+            Lock wl = sl.asWriteLock();
+            try {
+                if (timeout < 0)
+                    wl.lockInterruptibly();
+                else
+                    wl.tryLock(timeout, unit);
+                stamp(1L);  // got the lock
+                check(!sl.isReadLocked());
+                check(sl.isWriteLocked());
+            } catch (Throwable x) { thrown(x);
+            } finally { if (stamp() != 0L) wl.unlock(); } }};
+    }
+
+    static Writer interruptibleWriter(final StampedLock sl,
+                                      final long timeout,
+                                      final TimeUnit unit,
+                                      final Phaser gate,
+                                      final boolean view) {
+        return view ? interruptibleWriterView(sl, timeout, unit, gate)
+                    : interruptibleWriter(sl, timeout, unit, gate);
+    }
+
+    // Returns an infinite lazy list of all possible reader combinations.
+    static Iterator<Reader> readerIterator(final StampedLock sl,
+                                           final Phaser gate) {
+        return new Iterator<Reader>() {
+            int i = 0;
+            boolean view = false;
+            public boolean hasNext() { return true; }
+            public Reader next() {
+                switch ((i++)&7) {
+                    case 1: case 4: case 7:
+                        return reader(sl, gate, view ^= true);
+                    case 2: case 5:
+                        return interruptibleReader(sl, -1, SECONDS, gate, view ^= true);
+                    default:
+                        return interruptibleReader(sl, 30, SECONDS, gate, view ^= true); }}
+            public void remove() {throw new UnsupportedOperationException();}};
+    }
+
+    // Returns an infinite lazy list of all possible writer combinations.
+    static Iterator<Writer> writerIterator(final StampedLock sl,
+                                           final Phaser gate) {
+        return new Iterator<Writer>() {
+            int i = 0;
+            boolean view = false;
+            public boolean hasNext() { return true; }
+            public Writer next() {
+                switch ((i++)&7) {
+                    case 1: case 4: case 7:
+                        return writer(sl, gate, view ^= true);
+                    case 2: case 5:
+                        return interruptibleWriter(sl, -1, SECONDS, gate, view ^= true);
+                    default:
+                        return interruptibleWriter(sl, 30, SECONDS, gate, view ^= true); }}
+            public void remove() {throw new UnsupportedOperationException();}};
+    }
+
+    private static void realMain(String[] args) throws Throwable {
+
+        Thread.currentThread().setName("mainThread");
+
+        //----------------------------------------------------------------
+        // Some basic sanity
+        //----------------------------------------------------------------
+        try {
+            final StampedLock sl = new StampedLock();
+            check(!sl.isReadLocked());
+            check(!sl.isWriteLocked());
+            long stamp = sl.tryOptimisticRead();
+            check(stamp != 0L);
+            check(sl.validate(stamp));
+            check(!sl.validate(0));
+
+            stamp = sl.writeLock();
+            try {
+                check(sl.validate(stamp));
+                check(!sl.isReadLocked());
+                check(sl.isWriteLocked());
+                check(sl.tryReadLock() == 0L);
+                check(sl.tryReadLock(100, MILLISECONDS) == 0L);
+                check(sl.tryOptimisticRead() == 0L);
+                check(sl.tryWriteLock() == 0L);
+                check(sl.tryWriteLock(100, MILLISECONDS) == 0L);
+                check(!sl.tryUnlockRead());
+                check(sl.tryConvertToWriteLock(stamp) == stamp);
+                try {
+                    sl.unlockRead(stamp);
+                    fail("Expected unlockRead to throw when not holding read lock");
+                } catch (IllegalMonitorStateException x) {
+                    pass();
+                }
+                check(sl.validate(stamp));
+            } finally {
+                sl.unlockWrite(stamp);
+            }
+            check(!sl.isWriteLocked());
+
+            stamp = sl.readLock();
+            try {
+                check(sl.validate(stamp));
+                check(sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(sl.tryOptimisticRead() != 0L);
+                check(sl.tryWriteLock() == 0L);
+                check(sl.tryWriteLock(100, MILLISECONDS) == 0L);
+                check(!sl.tryUnlockWrite());
+                check(sl.tryConvertToReadLock(stamp) == stamp);
+                try {
+                    sl.unlockWrite(stamp);
+                    fail("Expected unlockWrite to throw when not holding read lock");
+                } catch (IllegalMonitorStateException x) {
+                    pass();
+                }
+                check(sl.validate(stamp));
+            } finally {
+                sl.unlockRead(stamp);
+            }
+            check(!sl.isReadLocked());
+
+            stamp = sl.tryReadLock(100, MILLISECONDS);
+            try {
+                check(stamp != 0L);
+            } finally {
+                sl.unlockRead(stamp);
+            }
+        } catch (Throwable t) { unexpected(t); }
+
+        //----------------------------------------------------------------
+        // Multiple writers single reader
+        //----------------------------------------------------------------
+        try {
+            StampedLock sl = new StampedLock();
+            Phaser gate = new Phaser(102);
+            Iterator<Writer> writers = writerIterator(sl, gate);
+            Iterator<Reader> readers = readerIterator(sl, gate);
+            for (int i = 0; i < 10; i++) {
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(!sl.tryUnlockRead());
+                check(!sl.tryUnlockWrite());
+                check(sl.tryOptimisticRead() != 0L);
+                Locker[] wThreads = new Locker[100];;
+                for (int j=0; j<100; j++)
+                    wThreads[j] = writers.next();
+                for (int j=0; j<100; j++)
+                    wThreads[j].start();
+                Reader reader = readers.next(); reader.start();
+                toTheStartingGate(gate);
+                reader.join();
+                for (int j=0; j<100; j++)
+                    wThreads[j].join();
+                for (int j=0; j<100; j++)
+                    checkResult(wThreads[j], null);
+                checkResult(reader, null);
+            }
+        } catch (Throwable t) { unexpected(t); }
+
+        //----------------------------------------------------------------
+        // Multiple readers single writer
+        //----------------------------------------------------------------
+        try {
+            StampedLock sl = new StampedLock();
+            Phaser gate = new Phaser(102);
+            Iterator<Writer> writers = writerIterator(sl, gate);
+            Iterator<Reader> readers = readerIterator(sl, gate);
+            for (int i = 0; i < 10; i++) {
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(!sl.tryUnlockRead());
+                check(!sl.tryUnlockWrite());
+                check(sl.tryOptimisticRead() != 0L);
+                Locker[] rThreads = new Locker[100];;
+                for (int j=0; j<100; j++)
+                    rThreads[j] = readers.next();
+                for (int j=0; j<100; j++)
+                    rThreads[j].start();
+                Writer writer = writers.next(); writer.start();
+                toTheStartingGate(gate);
+                writer.join();
+                for (int j=0; j<100; j++)
+                    rThreads[j].join();
+                for (int j=0; j<100; j++)
+                    checkResult(rThreads[j], null);
+                checkResult(writer, null);
+            }
+        } catch (Throwable t) { unexpected(t); }
+
+        //----------------------------------------------------------------
+        // thread interrupted
+        //----------------------------------------------------------------
+        try {
+            boolean view = false;
+            StampedLock sl = new StampedLock();
+            for (long timeout : new long[] { -1L, 30L, -1L, 30L }) {
+                long stamp = sl.writeLock();
+                try {
+                    Reader r = interruptibleReader(sl, timeout, SECONDS, null, view);
+                    r.start();
+                    // allow r to block
+                    Thread.sleep(2000);
+                    r.interrupt();
+                    r.join();
+                    checkResult(r, InterruptedException.class);
+                } finally {
+                    sl.unlockWrite(stamp);
+                }
+                stamp = sl.readLock();
+                try {
+                    Writer w = interruptibleWriter(sl, timeout, SECONDS, null, view);
+                    w.start();
+                    // allow w to block
+                    Thread.sleep(2000);
+                    w.interrupt();
+                    w.join();
+                    checkResult(w, InterruptedException.class);
+                } finally {
+                    sl.unlockRead(stamp);
+                }
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(!sl.tryUnlockRead());
+                check(!sl.tryUnlockWrite());
+                check(sl.tryOptimisticRead() != 0L);
+                if (timeout == 30L)
+                    view = true;
+            }
+        } catch (Throwable t) { unexpected(t); }
+
+        //----------------------------------------------------------------
+        // timeout
+        //----------------------------------------------------------------
+        try {
+            StampedLock sl = new StampedLock();
+            for (long timeout : new long[] { 0L, 5L }) {
+                long stamp = sl.writeLock();
+                try {
+                    check(sl.tryReadLock(timeout, SECONDS) == 0L);
+                } finally {
+                    sl.unlockWrite(stamp);
+                }
+                stamp = sl.readLock();
+                try {
+                    check(sl.tryWriteLock(timeout, SECONDS) == 0L);
+                } finally {
+                    sl.unlockRead(stamp);
+                }
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(!sl.tryUnlockRead());
+                check(!sl.tryUnlockWrite());
+                check(sl.tryOptimisticRead() != 0L);
+            }
+        } catch (Throwable t) { unexpected(t); }
+
+        //----------------------------------------------------------------
+        // optimistic read
+        //----------------------------------------------------------------
+        try {
+            StampedLock sl = new StampedLock();
+            Iterator<Writer> writers = writerIterator(sl, null);
+            Iterator<Reader> readers = readerIterator(sl, null);
+            for (int i = 0; i < 10; i++) {
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(!sl.tryUnlockRead());
+                check(!sl.tryUnlockWrite());
+                long stamp = sl.tryOptimisticRead();
+                check(stamp != 0L);
+                check(sl.tryConvertToOptimisticRead(stamp) == stamp);
+                Reader r = readers.next(); r.start();
+                r.join();
+                checkResult(r, null);
+                check(sl.validate(stamp));
+                check(sl.tryConvertToOptimisticRead(stamp) == stamp);
+                Writer w = writers.next(); w.start();
+                w.join();
+                checkResult(w, null);
+                check(sl.validate(stamp) == false);
+            }
+        } catch (Throwable t) { unexpected(t); }
+
+        //----------------------------------------------------------------
+        // convert
+        //----------------------------------------------------------------
+        try {
+            StampedLock sl = new StampedLock();
+            for (int i = 0; i < 2; i++) {
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(!sl.tryUnlockRead());
+                check(!sl.tryUnlockWrite());
+                long stamp = sl.tryOptimisticRead();
+                check(stamp != 0L);
+                check((stamp = sl.tryConvertToReadLock(stamp)) != 0L);
+                check(sl.validate(stamp));
+                check(sl.isReadLocked());
+                check(sl.tryWriteLock() == 0L);
+                check(sl.tryWriteLock(1L, SECONDS) == 0L);
+                check((stamp = sl.tryConvertToWriteLock(stamp)) != 0L);
+                check(sl.validate(stamp));
+                check(!sl.isReadLocked());
+                check(sl.isWriteLocked());
+                check(sl.tryReadLock(1L, SECONDS) == 0L);
+                if (i != 0) {
+                    sl.unlockWrite(stamp);
+                    continue;
+                }
+                // convert down
+                check((stamp = sl.tryConvertToReadLock(stamp)) != 0L);
+                check(sl.validate(stamp));
+                check(sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(sl.tryWriteLock() == 0L);
+                check(sl.tryWriteLock(1L, SECONDS) == 0L);
+                check((stamp = sl.tryConvertToOptimisticRead(stamp)) != 0L);
+                check(sl.validate(stamp));
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+                check(sl.validate(stamp));
+            }
+        } catch (Throwable t) { unexpected(t); }
+
+        //----------------------------------------------------------------
+        // views
+        //----------------------------------------------------------------
+        try {
+            StampedLock sl = new StampedLock();
+
+            Lock rl = sl.asReadLock();
+            Lock wl = sl.asWriteLock();
+            for (int i = 0; i < 2; i++) {
+                rl.lock();
+                try {
+                    check(sl.isReadLocked());
+                    check(!sl.isWriteLocked());
+                    check(sl.tryWriteLock() == 0L);
+                    check(sl.tryWriteLock(1L, SECONDS) == 0L);
+                } finally {
+                    rl.unlock();
+                }
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+
+                wl.lock();
+                try {
+                    check(!sl.isReadLocked());
+                    check(sl.isWriteLocked());
+                    check(sl.tryWriteLock() == 0L);
+                    check(sl.tryWriteLock(1L, SECONDS) == 0L);
+                } finally {
+                    wl.unlock();
+                }
+                check(!sl.isReadLocked());
+                check(!sl.isWriteLocked());
+
+                ReadWriteLock rwl = sl.asReadWriteLock();
+                rl = rwl.readLock();
+                wl = rwl.writeLock();
+            }
+        } catch (Throwable t) { unexpected(t); }
+    }
+
+    //--------------------- Infrastructure ---------------------------
+    static volatile int passed = 0, failed = 0;
+    static void pass() {passed++;}
+    static void fail() {failed++; Thread.dumpStack();}
+    static void fail(String msg) {System.out.println(msg); fail();}
+    static void unexpected(Throwable t) {failed++; t.printStackTrace();}
+    static void check(boolean cond) {if (cond) pass(); else fail();}
+    static void equal(Object x, Object y) {
+        if (x == null ? y == null : x.equals(y)) pass();
+        else fail(x + " not equal to " + y);}
+    public static void main(String[] args) throws Throwable {
+        try {realMain(args);} catch (Throwable t) {unexpected(t);}
+        System.out.printf("%nPassed = %d, failed = %d%n%n", passed, failed);
+        if (failed > 0) throw new AssertionError("Some tests failed");}
+}