/*

 * 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 jdk.internal.misc.Unsafe;

import jdk.internal.vm.annotation.ReservedStackAccess;

/**

 * 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><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><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, in which

 *   case all actions prior to the most recent write lock release

 *   happen-before actions following the call to {@code tryOptimisticRead}.

 *   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 read 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 read 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.

 *

 * </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 read 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>Like {@link java.util.concurrent.Semaphore Semaphore}, but unlike most

 * {@link Lock} implementations, StampedLocks have no notion of ownership.

 * Locks acquired in one thread can be released or converted in another.

 *

 * <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>Memory Synchronization.</b> Methods with the effect of

 * successfully locking in any mode have the same memory

 * synchronization effects as a <em>Lock</em> action, as described in

 * Chapter 17 of <cite>The Java Language Specification</cite>.

 * Methods successfully unlocking in write mode have the same memory

 * synchronization effects as an <em>Unlock</em> action.  In optimistic

 * read usages, actions prior to the most recent write mode unlock action

 * are guaranteed to happen-before those following a tryOptimisticRead

 * only if a later validate returns true; otherwise there is no guarantee

 * that the reads between tryOptimisticRead and validate obtain a

 * consistent snapshot.

 *

 * <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.

 *

 * <pre> {@code

 * class Point {

 *   private double x, y;

 *   private final StampedLock sl = new StampedLock();

 *

 *   // an exclusively locked method

 *   void move(double deltaX, double deltaY) {

 *     long stamp = sl.writeLock();

 *     try {

 *       x += deltaX;

 *       y += deltaY;

 *     } finally {

 *       sl.unlockWrite(stamp);

 *     }

 *   }

 *

 *   // a read-only method

 *   // upgrade from optimistic read to read lock

 *   double distanceFromOrigin() {

 *     long stamp = sl.tryOptimisticRead();

 *     try {

 *       retryHoldingLock: for (;; stamp = sl.readLock()) {

 *         if (stamp == 0L)

 *           continue retryHoldingLock;

 *         // possibly racy reads

 *         double currentX = x;

 *         double currentY = y;

 *         if (!sl.validate(stamp))

 *           continue retryHoldingLock;

 *         return Math.hypot(currentX, currentY);

 *       }

 *     } finally {

 *       if (StampedLock.isReadLockStamp(stamp))

 *         sl.unlockRead(stamp);

 *     }

 *   }

 *

 *   // upgrade from optimistic read to write lock

 *   void moveIfAtOrigin(double newX, double newY) {

 *     long stamp = sl.tryOptimisticRead();

 *     try {

 *       retryHoldingLock: for (;; stamp = sl.writeLock()) {

 *         if (stamp == 0L)

 *           continue retryHoldingLock;

 *         // possibly racy reads

 *         double currentX = x;

 *         double currentY = y;

 *         if (!sl.validate(stamp))

 *           continue retryHoldingLock;

 *         if (currentX != 0.0 || currentY != 0.0)

 *           break;

 *         stamp = sl.tryConvertToWriteLock(stamp);

 *         if (stamp == 0L)

 *           continue retryHoldingLock;

 *         // exclusive access

 *         x = newX;

 *         y = newY;

 *         return;

 *       }

 *     } finally {

 *       if (StampedLock.isWriteLockStamp(stamp))

 *         sl.unlockWrite(stamp);

 *     }

 *   }

 *

 *   // upgrade read lock to write lock

 *   void moveIfAtOrigin2(double newX, double newY) {

 *     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>

 *

 * @jls 17.4 Memory Model

 * @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 (AQS; see its internal documentation

     * for a fuller account), where each node is either a ReaderNode

     * or WriterNode. Implementation of queued Writer mode is

     * identical to AQS except for lock-state operations.  Sets of

     * waiting readers are grouped (linked) under a common node (field

     * cowaiters) so act as a single node with respect to most CLH

     * mechanics.  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/).  Method release does not

     * itself wake up cowaiters. This is done by the primary thread,

     * but helped by other cowaiters as they awaken.

     *

     * These rules apply to threads actually queued. Threads may also

     * try to acquire locks before or in the process of enqueueing

     * regardless of preference rules, and so may "barge" their way

     * in.  Methods writeLock and readLock (but not the other variants

     * of each) first unconditionally try to CAS state, falling back

     * to test-and-test-and-set retries on failure, slightly shrinking

     * race windows on initial attempts, thus making success more

     * likely. Also, when some threads cancel (via interrupt or

     * timeout), phase-fairness is at best roughly approximated.

     *

     * 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.

     *

     * For an explanation of the use of acquireFence, see

     * http://gee.cs.oswego.edu/dl/html/j9mm.html as well as Boehm's

     * paper (above). Note that sequence validation (mainly method

     * validate()) requires stricter ordering rules than apply to

     * normal volatile reads (of "state").  To ensure that writeLock

     * acquisitions strictly precede subsequent writes in cases where

     * this is not already forced, we use a storeStoreFence.

     *

     * 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

     * 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;

    /** The number of bits to use for reader count before overflowing */

    private static final int LG_READERS = 7; // 127 readers

    // 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

    // not writing and conservatively non-overflowing

    private static final long RSAFE = ~(3L << (LG_READERS - 1));

    /*

     * 3 stamp modes can be distinguished by examining (m = stamp & ABITS):

     * write mode: m == WBIT

     * optimistic read mode: m == 0L (even when read lock is held)

     * read mode: m > 0L && m <= RFULL (the stamp is a copy of state, but the

     * read hold count in the stamp is unused other than to determine mode)

     *

     * This differs slightly from the encoding of state:

     * (state & ABITS) == 0L indicates the lock is currently unlocked.

     * (state & ABITS) == RBITS is a special transient value

     * indicating spin-locked to manipulate reader bits overflow.

     */

    /** Initial value for lock state; avoids 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;

    // Bits for Node.status

    static final int WAITING   = 1;

    static final int CANCELLED = 0x80000000; // must be negative

    /** CLH nodes */

    abstract static class Node {

        volatile Node prev;       // initially attached via casTail

        volatile Node next;       // visibly nonnull when signallable

        Thread waiter;            // visibly nonnull when enqueued

        volatile int status;      // written by owner, atomic bit ops by others

        // methods for atomic operations

        final boolean casPrev(Node c, Node v) {  // for cleanQueue

            return U.weakCompareAndSetReference(this, PREV, c, v);

        }

        final boolean casNext(Node c, Node v) {  // for cleanQueue

            return U.weakCompareAndSetReference(this, NEXT, c, v);

        }

        final int getAndUnsetStatus(int v) {     // for signalling

            return U.getAndBitwiseAndInt(this, STATUS, ~v);

        }

        final void setPrevRelaxed(Node p) {      // for off-queue assignment

            U.putReference(this, PREV, p);

        }

        final void setStatusRelaxed(int s) {     // for off-queue assignment

            U.putInt(this, STATUS, s);

        }

        final void clearStatus() {               // for reducing unneeded signals

            U.putIntOpaque(this, STATUS, 0);

        }

        private static final long STATUS

            = U.objectFieldOffset(Node.class, "status");

        private static final long NEXT

            = U.objectFieldOffset(Node.class, "next");

        private static final long PREV

            = U.objectFieldOffset(Node.class, "prev");

    }

    static final class WriterNode extends Node { // node for writers

    }

    static final class ReaderNode extends Node { // node for readers

        volatile ReaderNode cowaiters;           // list of linked readers

        final boolean casCowaiters(ReaderNode c, ReaderNode v) {

            return U.weakCompareAndSetReference(this, COWAITERS, c, v);

        }

        final void setCowaitersRelaxed(ReaderNode p) {

            U.putReference(this, COWAITERS, p);

        }

        private static final long COWAITERS

            = U.objectFieldOffset(ReaderNode.class, "cowaiters");

    }

    /** Head of CLH queue */

    private transient volatile Node head;

    /** Tail (last) of CLH queue */

    private transient volatile Node tail;

    // 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;

    }

    // internal lock methods

    private boolean casState(long expect, long update) {

        return U.compareAndSetLong(this, STATE, expect, update);

    }

    @ReservedStackAccess

    private long tryAcquireWrite() {

        long s, nextState;

        if (((s = state) & ABITS) == 0L && casState(s, nextState = s | WBIT)) {

            U.storeStoreFence();

            return nextState;

        }

        return 0L;

    }

    @ReservedStackAccess

    private long tryAcquireRead() {

        for (long s, m, nextState;;) {

            if ((m = (s = state) & ABITS) < RFULL) {

                if (casState(s, nextState = s + RUNIT))

                    return nextState;

            }

            else if (m == WBIT)

                return 0L;

            else if ((nextState = tryIncReaderOverflow(s)) != 0L)

                return nextState;

        }

    }

    /**

     * Returns an unlocked state, incrementing the version and

     * avoiding special failure value 0L.

     *

     * @param s a write-locked state (or stamp)

     */

    private static long unlockWriteState(long s) {

        return ((s += WBIT) == 0L) ? ORIGIN : s;

    }

    private long releaseWrite(long s) {

        long nextState = state = unlockWriteState(s);

        signalNext(head);

        return nextState;

    }

    /**

     * Exclusively acquires the lock, blocking if necessary

     * until available.

     *

     * @return a write stamp that can be used to unlock or convert mode

     */

    @ReservedStackAccess

    public long writeLock() {

        // try unconditional CAS confirming weak read

        long s = U.getLongOpaque(this, STATE) & ~ABITS, nextState;

        if (casState(s, nextState = s | WBIT)) {

            U.storeStoreFence();

            return nextState;

        }

        return acquireWrite(false, false, 0L);

    }

    /**

     * Exclusively acquires the lock if it is immediately available.

     *

     * @return a write stamp that can be used to unlock or convert mode,

     * or zero if the lock is not available

     */

    public long tryWriteLock() {

        return tryAcquireWrite();

    }

    /**

     * 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)}.

     *

     * @param time the maximum time to wait for the lock

     * @param unit the time unit of the {@code time} argument

     * @return a write 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 nextState;

            if ((nextState = tryAcquireWrite()) != 0L)

                return nextState;

            if (nanos <= 0L)

                return 0L;

            nextState = acquireWrite(true, true, System.nanoTime() + nanos);

            if (nextState != INTERRUPTED)

                return nextState;

        }

        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 write 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 nextState;

        if (!Thread.interrupted() &&

            ((nextState = tryAcquireWrite()) != 0L ||

             (nextState = acquireWrite(true, false, 0L)) != INTERRUPTED))

            return nextState;

        throw new InterruptedException();

    }

    /**

     * Non-exclusively acquires the lock, blocking if necessary

     * until available.

     *

     * @return a read stamp that can be used to unlock or convert mode

     */

    @ReservedStackAccess

    public long readLock() {

        // unconditionally optimistically try non-overflow case once

        long s = U.getLongOpaque(this, STATE) & RSAFE, nextState;

        if (casState(s, nextState = s + RUNIT))

            return nextState;

        else

            return acquireRead(false, false, 0L);

    }

    /**

     * Non-exclusively acquires the lock if it is immediately available.

     *

     * @return a read stamp that can be used to unlock or convert mode,

     * or zero if the lock is not available

     */

    public long tryReadLock() {

        return tryAcquireRead();

    }

    /**

     * 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)}.

     *

     * @param time the maximum time to wait for the lock

     * @param unit the time unit of the {@code time} argument

     * @return a read 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 nanos = unit.toNanos(time);

        if (!Thread.interrupted()) {

            long nextState;

            if (tail == head && (nextState = tryAcquireRead()) != 0L)

                return nextState;

            if (nanos <= 0L)

                return 0L;

            nextState = acquireRead(true, true, System.nanoTime() + nanos);

            if (nextState != INTERRUPTED)

                return nextState;

        }

        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 read 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 nextState;

        if (!Thread.interrupted() &&

            ((nextState = tryAcquireRead()) != 0L ||

             (nextState = acquireRead(true, false, 0L)) != INTERRUPTED))

            return nextState;

        throw new InterruptedException();

    }

    /**

     * Returns a stamp that can later be validated, or zero

     * if exclusively locked.

     *

     * @return a valid optimistic read 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.

     *

     * @param stamp a stamp

     * @return {@code 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

     */

    @ReservedStackAccess

    public void unlockWrite(long stamp) {

        if (state != stamp || (stamp & WBIT) == 0L)

            throw new IllegalMonitorStateException();

        releaseWrite(stamp);

    }

    /**

     * 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

     */

    @ReservedStackAccess

    public void unlockRead(long stamp) {

        long s, m;

        if ((stamp & RBITS) != 0L) {

            while (((s = state) & SBITS) == (stamp & SBITS) &&

                   ((m = s & RBITS) != 0L)) {

                if (m < RFULL) {

                    if (casState(s, s - RUNIT)) {

                        if (m == RUNIT)

                            signalNext(head);

                        return;

                    }

                }

                else if (tryDecReaderOverflow(s) != 0L)

                    return;

            }

        }

        throw new IllegalMonitorStateException();

    }

    /**

     * 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) {

        if ((stamp & WBIT) != 0L)

            unlockWrite(stamp);

        else

            unlockRead(stamp);

    }

    /**

     * If the lock state matches the given stamp, atomically 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, nextState;

        while (((s = state) & SBITS) == (stamp & SBITS)) {

            if ((m = s & ABITS) == 0L) {

                if (a != 0L)

                    break;

                if (casState(s, nextState = s | WBIT)) {

                    U.storeStoreFence();

                    return nextState;

                }

            } else if (m == WBIT) {

                if (a != m)

                    break;

                return stamp;

            } else if (m == RUNIT && a != 0L) {

                if (casState(s, nextState = s - RUNIT + WBIT))

                    return nextState;

            } else

                break;

        }

        return 0L;

    }

    /**

     * If the lock state matches the given stamp, atomically 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, s, nextState;

        while (((s = state) & SBITS) == (stamp & SBITS)) {

            if ((a = stamp & ABITS) >= WBIT) {

                if (s != stamp) // write stamp

                    break;

                nextState = state = unlockWriteState(s) + RUNIT;

                signalNext(head);

                return nextState;

            } else if (a == 0L) { // optimistic read stamp

                if ((s & ABITS) < RFULL) {

                    if (casState(s, nextState = s + RUNIT))

                        return nextState;

                } else if ((nextState = tryIncReaderOverflow(s)) != 0L)

                    return nextState;

            } else { // already a read stamp

                if ((s & ABITS) == 0L)

                    break;

                return stamp;

            }

        }

        return 0L;

    }

    /**

     * If the lock state matches the given stamp then, atomically, 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, m, s, nextState;

        U.loadFence();

        while (((s = state) & SBITS) == (stamp & SBITS)) {

            if ((a = stamp & ABITS) >= WBIT) {

                if (s != stamp)   // write stamp

                    break;

                return releaseWrite(s);

            } else if (a == 0L) { // already an optimistic read stamp

                return stamp;

            } else if ((m = s & ABITS) == 0L) { // invalid read stamp

                break;

            } else if (m < RFULL) {

                if (casState(s, nextState = s - RUNIT)) {

                    if (m == RUNIT)

                        signalNext(head);

                    return nextState & SBITS;

                }

            } else if ((nextState = tryDecReaderOverflow(s)) != 0L)

                return nextState & 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 {@code true} if the lock was held, else false

     */

    @ReservedStackAccess

    public boolean tryUnlockWrite() {

        long s;

        if (((s = state) & WBIT) != 0L) {

            releaseWrite(s);

            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 {@code true} if the read lock was held, else false

     */

    @ReservedStackAccess

    public boolean tryUnlockRead() {

        long s, m;

        while ((m = (s = state) & ABITS) != 0L && m < WBIT) {

            if (m < RFULL) {

                if (casState(s, s - RUNIT)) {

                    if (m == RUNIT)

                        signalNext(head);

                    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 {@code true} if the lock is currently held exclusively.

     *

     * @return {@code true} if the lock is currently held exclusively

     */

    public boolean isWriteLocked() {

        return (state & WBIT) != 0L;

    }

    /**

     * Returns {@code true} if the lock is currently held non-exclusively.

     *

     * @return {@code true} if the lock is currently held non-exclusively

     */

    public boolean isReadLocked() {

        return (state & RBITS) != 0L;

    }

    /**

     * Tells whether a stamp represents holding a lock exclusively.

     * This method may be useful in conjunction with

     * {@link #tryConvertToWriteLock}, for example: <pre> {@code

     * long stamp = sl.tryOptimisticRead();

     * try {

     *   ...

     *   stamp = sl.tryConvertToWriteLock(stamp);

     *   ...

     * } finally {

     *   if (StampedLock.isWriteLockStamp(stamp))

     *     sl.unlockWrite(stamp);

     * }}</pre>

     *

     * @param stamp a stamp returned by a previous StampedLock operation

     * @return {@code true} if the stamp was returned by a successful

     *   write-lock operation

     * @since 10

     */

    public static boolean isWriteLockStamp(long stamp) {

        return (stamp & ABITS) == WBIT;

    }

    /**

     * Tells whether a stamp represents holding a lock non-exclusively.

     * This method may be useful in conjunction with

     * {@link #tryConvertToReadLock}, for example: <pre> {@code

     * long stamp = sl.tryOptimisticRead();

     * try {

     *   ...

     *   stamp = sl.tryConvertToReadLock(stamp);

     *   ...

     * } finally {

     *   if (StampedLock.isReadLockStamp(stamp))

     *     sl.unlockRead(stamp);

     * }}</pre>

     *

     * @param stamp a stamp returned by a previous StampedLock operation

     * @return {@code true} if the stamp was returned by a successful

     *   read-lock operation

     * @since 10

     */

    public static boolean isReadLockStamp(long stamp) {

        return (stamp & RBITS) != 0L;

    }

    /**

     * Tells whether a stamp represents holding a lock.

     * This method may be useful in conjunction with

     * {@link #tryConvertToReadLock} and {@link #tryConvertToWriteLock},

     * for example: <pre> {@code

     * long stamp = sl.tryOptimisticRead();

     * try {

     *   ...

     *   stamp = sl.tryConvertToReadLock(stamp);

     *   ...

     *   stamp = sl.tryConvertToWriteLock(stamp);

     *   ...

     * } finally {

     *   if (StampedLock.isLockStamp(stamp))

     *     sl.unlock(stamp);

     * }}</pre>

     *

     * @param stamp a stamp returned by a previous StampedLock operation

     * @return {@code true} if the stamp was returned by a successful

     *   read-lock or write-lock operation

     * @since 10

     */

    public static boolean isLockStamp(long stamp) {

        return (stamp & ABITS) != 0L;

    }

    /**

     * Tells whether a stamp represents a successful optimistic read.

     *

     * @param stamp a stamp returned by a previous StampedLock operation

     * @return {@code true} if the stamp was returned by a successful

     *   optimistic read operation, that is, a non-zero return from

     *   {@link #tryOptimisticRead()} or

     *   {@link #tryConvertToOptimisticRead(long)}

     * @since 10

     */

    public static boolean isOptimisticReadStamp(long stamp) {

        return (stamp & ABITS) == 0L && stamp != 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;

        if ((v = readLockView) != null) return v;

        return 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;

        if ((v = writeLockView) != null) return v;

        return 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;

        if ((v = readWriteLockView) != null) return v;

        return 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() {

        long s;

        if (((s = state) & WBIT) == 0L)

            throw new IllegalMonitorStateException();

        releaseWrite(s);

    }

    final void unstampedUnlockRead() {

        long s, m;

        while ((m = (s = state) & RBITS) > 0L) {

            if (m < RFULL) {

                if (casState(s, s - RUNIT)) {

                    if (m == RUNIT)

                        signalNext(head);

                    return;

                }

            }

            else if (tryDecReaderOverflow(s) != 0L)

                return;

        }

        throw new IllegalMonitorStateException();

    }

    private void readObject(java.io.ObjectInputStream s)

        throws java.io.IOException, ClassNotFoundException {

        s.defaultReadObject();

        state = ORIGIN; // reset to unlocked state

    }

    // overflow handling methods

    /**

     * 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)

            Thread.onSpinWait();

        else if (casState(s, s | RBITS)) {

            ++readerOverflow;

            return state = s;

        }

        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)

            Thread.onSpinWait();

        else if (casState(s, s | RBITS)) {

            int r; long nextState;

            if ((r = readerOverflow) > 0) {

                readerOverflow = r - 1;

                nextState = s;

            }

            else

                nextState = s - RUNIT;

            return state = nextState;

        }

        return 0L;

    }

    // release methods

    /**

     * Wakes up the successor of given node, if one exists, and unsets its

     * WAITING status to avoid park race. This may fail to wake up an

     * eligible thread when one or more have been cancelled, but

     * cancelAcquire ensures liveness.

     */

    static final void signalNext(Node h) {

        Node s;

        if (h != null && (s = h.next) != null && s.status > 0) {

            s.getAndUnsetStatus(WAITING);

            LockSupport.unpark(s.waiter);

        }

    }

    /**

     * Removes and unparks all cowaiters of node, if it exists.

     */

    private static void signalCowaiters(ReaderNode node) {

        if (node != null) {

            for (ReaderNode c; (c = node.cowaiters) != null; ) {

                if (node.casCowaiters(c, c.cowaiters))

                    LockSupport.unpark(c.waiter);

            }

        }

    }

    // queue link methods

    private boolean casTail(Node c, Node v) {

        return U.compareAndSetReference(this, TAIL, c, v);

    }

    /** tries once to CAS a new dummy node for head */

    private void tryInitializeHead() {

        Node h = new WriterNode();

        if (U.compareAndSetReference(this, HEAD, null, h))

            tail = h;

    }

    /**

     * For explanation, see above and AbstractQueuedSynchronizer

     * internal documentation.

     *

     * @param interruptible true if should check interrupts and if so

     * return INTERRUPTED

     * @param timed if true use timed waits

     * @param time the System.nanoTime value to timeout at (and return zero)

     * @return next state, or INTERRUPTED

     */

    private long acquireWrite(boolean interruptible, boolean timed, long time) {

        byte spins = 0, postSpins = 0;   // retries upon unpark of first thread

        boolean interrupted = false, first = false;

        WriterNode node = null;

        Node pred = null;

        for (long s, nextState;;) {

            if (!first && (pred = (node == null) ? null : node.prev) != null &&

                !(first = (head == pred))) {

                if (pred.status < 0) {

                    cleanQueue();           // predecessor cancelled

                    continue;

                } else if (pred.prev == null) {

                    Thread.onSpinWait();    // ensure serialization

                    continue;

                }

            }

            if ((first || pred == null) && ((s = state) & ABITS) == 0L &&

                casState(s, nextState = s | WBIT)) {

                U.storeStoreFence();

                if (first) {

                    node.prev = null;

                    head = node;

                    pred.next = null;

                    node.waiter = null;

                    if (interrupted)

                        Thread.currentThread().interrupt();

                }

                return nextState;

            } else if (node == null) {          // retry before enqueuing

                node = new WriterNode();

            } else if (pred == null) {          // try to enqueue

                Node t = tail;

                node.setPrevRelaxed(t);

                if (t == null)

                    tryInitializeHead();

                else if (!casTail(t, node))

                    node.setPrevRelaxed(null);  // back out

                else

                    t.next = node;

            } else if (first && spins != 0) {   // reduce unfairness

                --spins;

                Thread.onSpinWait();

            } else if (node.status == 0) {      // enable signal

                if (node.waiter == null)

                    node.waiter = Thread.currentThread();

                node.status = WAITING;

            } else {

                long nanos;

                spins = postSpins = (byte)((postSpins << 1) | 1);

                if (!timed)

                    LockSupport.park(this);

                else if ((nanos = time - System.nanoTime()) > 0L)

                    LockSupport.parkNanos(this, nanos);

                else

                    break;

                node.clearStatus();

                if ((interrupted |= Thread.interrupted()) && interruptible)

                    break;

            }

        }

        return cancelAcquire(node, interrupted);

    }

    /**

     * See above for explanation.

     *

     * @param interruptible true if should check interrupts and if so

     * return INTERRUPTED

     * @param timed if true use timed waits

     * @param time the System.nanoTime value to timeout at (and return zero)

     * @return next state, or INTERRUPTED

     */

    private long acquireRead(boolean interruptible, boolean timed, long time) {

        boolean interrupted = false;

        ReaderNode node = null;

        /*

         * Loop:

         *   if empty, try to acquire

         *   if tail is Reader, try to cowait; restart if leader stale or cancels

         *   else try to create and enqueue node, and wait in 2nd loop below

         */

        for (;;) {