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

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

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

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

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

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

 {@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);
 *     }
 *   }
 * }}
* * @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(); U.putLongVolatile(this, 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; U.putLongVolatile(this, 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, 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, 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, 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 = 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; U.putLongVolatile(this, 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, 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 = 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; U.putLongVolatile(this, 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) { U.putLongVolatile(this, 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(); U.putLongVolatile(this, 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(); U.putLongVolatile(this, 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; U.putLongVolatile(this, 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; U.putLongVolatile(this, 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; } } boolean wasInterrupted = false; 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; if (wasInterrupted) Thread.currentThread().interrupt(); 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 (Thread.interrupted()) { if (interruptible) return cancelWaiter(node, node, true); wasInterrupted = 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) { boolean wasInterrupted = false; 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)) { if (wasInterrupted) Thread.currentThread().interrupt(); 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)) { if (wasInterrupted) Thread.currentThread().interrupt(); 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) { if (wasInterrupted) Thread.currentThread().interrupt(); 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 (Thread.interrupted()) { if (interruptible) return cancelWaiter(node, p, true); wasInterrupted = 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); } if (wasInterrupted) Thread.currentThread().interrupt(); 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 (Thread.interrupted()) { if (interruptible) return cancelWaiter(node, node, true); wasInterrupted = 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 = sun.misc.Unsafe.getUnsafe(); 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 { STATE = U.objectFieldOffset (StampedLock.class.getDeclaredField("state")); WHEAD = U.objectFieldOffset (StampedLock.class.getDeclaredField("whead")); WTAIL = U.objectFieldOffset (StampedLock.class.getDeclaredField("wtail")); WSTATUS = U.objectFieldOffset (WNode.class.getDeclaredField("status")); WNEXT = U.objectFieldOffset (WNode.class.getDeclaredField("next")); WCOWAIT = U.objectFieldOffset (WNode.class.getDeclaredField("cowait")); PARKBLOCKER = U.objectFieldOffset (Thread.class.getDeclaredField("parkBlocker")); } catch (ReflectiveOperationException e) { throw new Error(e); } } }