Back to index...

	/*
	* 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.) Method release
	* does not (and sometimes cannot) itself wake up cowaiters. This
	* is done by the primary thread, but helped by any other threads
	* with nothing better to do in methods acquireRead and
	* acquireWrite.
	*
	* 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 enqueuing on acquisition */
	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;

	/** Maximum number of retries before blocking at head on acquisition */
	private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;

	/** Maximum number of retries before re-blocking */
	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 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)}.
	*
	* @param time the maximum time to wait for the lock
	* @param unit the time unit of the {@code time} argument
	* @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 = state, next; // bypass acquireRead on common uncontended case
	return ((whead == wtail && (s & ABITS) < RFULL &&
	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)}.
	*
	* @param time the maximum time to wait for the lock
	* @param unit the time unit of the {@code time} argument
	* @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.
	*
	* @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
	*/
	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 {@code 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 {@code 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 {@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;
	}

	/**
	* 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 && (w = q.thread) != null)
	U.unpark(w);
	}
	}

	/**
	* 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 m, s, ns;
	if ((m = (s = state) & ABITS) == 0L) {
	if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
	return ns;
	}
	else if (spins < 0)
	spins = (m == WBIT && wtail == whead) ? SPINS : 0;
	else if (spins > 0) {
	if (LockSupport.nextSecondarySeed() >= 0)
	--spins;
	}
	else if ((p = wtail) == null) { // initialize queue
	WNode hd = new WNode(WMODE, null);
	if (U.compareAndSwapObject(this, WHEAD, null, hd))
	wtail = hd;
	}
	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 = -1;;) {
	WNode h, np, pp; int ps;
	if ((h = whead) == p) {
	if (spins < 0)
	spins = HEAD_SPINS;
	else if (spins < MAX_HEAD_SPINS)
	spins <<= 1;
	for (int k = spins;;) { // spin at head
	long s, ns;
	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;
	}
	}
	else if (h != null) { // help release stale waiters
	WNode c; Thread w;
	while ((c = h.cowait) != null) {
	if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
	(w = c.thread) != null)
	U.unpark(w);
	}
	}
	if (whead == h) {
	if ((np = node.prev) != p) {
	if (np != null)
	(p = np).next = node; // stale
	}
	else 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);
	node.thread = wt;
	if (p.status < 0 && (p != h \|\| (state & ABITS) != 0L) &&
	whead == h && node.prev == p)
	U.park(false, time); // emulate LockSupport.park
	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, p;
	for (int spins = -1;;) {
	WNode h;
	if ((h = whead) == (p = wtail)) {
	for (long m, s, ns;;) {
	if ((m = (s = state) & ABITS) < RFULL ?
	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L))
	return ns;
	else if (m >= WBIT) {
	if (spins > 0) {
	if (LockSupport.nextSecondarySeed() >= 0)
	--spins;
	}
	else {
	if (spins == 0) {
	WNode nh = whead, np = wtail;
	if ((nh == h && np == p) \|\| (h = nh) != (p = np))
	break;
	}
	spins = SPINS;
	}
	}
	}
	}
	if (p == null) { // initialize queue
	WNode hd = new WNode(WMODE, null);
	if (U.compareAndSwapObject(this, WHEAD, null, hd))
	wtail = hd;
	}
	else if (node == null)
	node = new WNode(RMODE, p);
	else if (h == p \|\| p.mode != RMODE) {
	if (node.prev != p)
	node.prev = p;
	else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
	p.next = node;
	break;
	}
	}
	else if (!U.compareAndSwapObject(p, WCOWAIT,
	node.cowait = p.cowait, node))
	node.cowait = null;
	else {
	for (;;) {
	WNode pp, c; Thread w;
	if ((h = whead) != null && (c = h.cowait) != null &&
	U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
	(w = c.thread) != null) // help release
	U.unpark(w);
	if (h == (pp = p.prev) \|\| h == p \|\| pp == null) {
	long m, s, ns;
	do {
	if ((m = (s = state) & ABITS) < RFULL ?
	U.compareAndSwapLong(this, STATE, s,
	ns = s + RUNIT) :
	(m < WBIT &&
	(ns = tryIncReaderOverflow(s)) != 0L))
	return ns;
	} while (m < WBIT);
	}
	if (whead == h && p.prev == pp) {
	long time;
	if (pp == null \|\| h == p \|\| p.status > 0) {
	node = null; // throw away
	break;
	}
	if (deadline == 0L)
	time = 0L;
	else if ((time = deadline - System.nanoTime()) <= 0L)
	return cancelWaiter(node, p, false);
	Thread wt = Thread.currentThread();
	U.putObject(wt, PARKBLOCKER, this);
	node.thread = wt;
	if ((h != pp \|\| (state & ABITS) == WBIT) &&
	whead == h && p.prev == pp)
	U.park(false, time);
	node.thread = null;
	U.putObject(wt, PARKBLOCKER, null);
	if (interruptible && Thread.interrupted())
	return cancelWaiter(node, p, true);
	}
	}
	}
	}

	for (int spins = -1;;) {
	WNode h, np, pp; int ps;
	if ((h = whead) == p) {
	if (spins < 0)
	spins = HEAD_SPINS;
	else if (spins < MAX_HEAD_SPINS)
	spins <<= 1;
	for (int k = spins;;) { // spin at head
	long m, s, ns;
	if ((m = (s = state) & ABITS) < RFULL ?
	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
	WNode c; Thread w;
	whead = node;
	node.prev = null;
	while ((c = node.cowait) != null) {
	if (U.compareAndSwapObject(node, WCOWAIT,
	c, c.cowait) &&
	(w = c.thread) != null)
	U.unpark(w);
	}
	return ns;
	}
	else if (m >= WBIT &&
	LockSupport.nextSecondarySeed() >= 0 && --k <= 0)
	break;
	}
	}
	else if (h != null) {
	WNode c; Thread w;
	while ((c = h.cowait) != null) {
	if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
	(w = c.thread) != null)
	U.unpark(w);
	}
	}
	if (whead == h) {
	if ((np = node.prev) != p) {
	if (np != null)
	(p = np).next = node; // stale
	}
	else 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 (p.status < 0 &&
	(p != h \|\| (state & ABITS) == WBIT) &&
	whead == h && node.prev == p)
	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;
	// unsplice cancelled nodes from group
	for (WNode p = group, q; (q = p.cowait) != null;) {
	if (q.status == CANCELLED) {
	U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
	p = group; // restart
	}
	else
	p = q;
	}
	if (group == node) {
	for (WNode r = group.cowait; r != null; r = r.cowait) {
	if ((w = r.thread) != null)
	U.unpark(w); // wake up uncancelled co-waiters
	}
	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);
	}
	}
	}

Back to index...