1e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak/* 2e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Written by Doug Lea with assistance from members of JCP JSR-166 3e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Expert Group and released to the public domain, as explained at 4e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * http://creativecommons.org/publicdomain/zero/1.0/ 5e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 6e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 7e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakpackage java.util.concurrent.locks; 8e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 9e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakimport java.util.concurrent.TimeUnit; 10e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 11e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak/** 12e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * A capability-based lock with three modes for controlling read/write 13e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * access. The state of a StampedLock consists of a version and mode. 14e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Lock acquisition methods return a stamp that represents and 15e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * controls access with respect to a lock state; "try" versions of 16e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * these methods may instead return the special value zero to 17e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * represent failure to acquire access. Lock release and conversion 18e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * methods require stamps as arguments, and fail if they do not match 19e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the state of the lock. The three modes are: 20e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 21e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <ul> 22e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 23e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <li><b>Writing.</b> Method {@link #writeLock} possibly blocks 24e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * waiting for exclusive access, returning a stamp that can be used 25e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * in method {@link #unlockWrite} to release the lock. Untimed and 26e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * timed versions of {@code tryWriteLock} are also provided. When 27e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the lock is held in write mode, no read locks may be obtained, 28e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * and all optimistic read validations will fail. 29e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 30e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <li><b>Reading.</b> Method {@link #readLock} possibly blocks 31e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * waiting for non-exclusive access, returning a stamp that can be 32e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * used in method {@link #unlockRead} to release the lock. Untimed 33e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * and timed versions of {@code tryReadLock} are also provided. 34e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 35e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead} 36e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * returns a non-zero stamp only if the lock is not currently held 37e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * in write mode. Method {@link #validate} returns true if the lock 38e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * has not been acquired in write mode since obtaining a given 39e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * stamp. This mode can be thought of as an extremely weak version 40e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * of a read-lock, that can be broken by a writer at any time. The 41e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * use of optimistic mode for short read-only code segments often 42e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * reduces contention and improves throughput. However, its use is 43e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * inherently fragile. Optimistic read sections should only read 44e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * fields and hold them in local variables for later use after 45e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * validation. Fields read while in optimistic mode may be wildly 46e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * inconsistent, so usage applies only when you are familiar enough 47e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * with data representations to check consistency and/or repeatedly 48e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * invoke method {@code validate()}. For example, such steps are 49e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * typically required when first reading an object or array 50e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * reference, and then accessing one of its fields, elements or 51e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * methods. 52e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 53e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * </ul> 54e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 55e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>This class also supports methods that conditionally provide 56e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * conversions across the three modes. For example, method {@link 57e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * #tryConvertToWriteLock} attempts to "upgrade" a mode, returning 58e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * a valid write stamp if (1) already in writing mode (2) in reading 59e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * mode and there are no other readers or (3) in optimistic mode and 60e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the lock is available. The forms of these methods are designed to 61e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * help reduce some of the code bloat that otherwise occurs in 62e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * retry-based designs. 63e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 64e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>StampedLocks are designed for use as internal utilities in the 65e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * development of thread-safe components. Their use relies on 66e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * knowledge of the internal properties of the data, objects, and 67e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * methods they are protecting. They are not reentrant, so locked 68e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * bodies should not call other unknown methods that may try to 69e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * re-acquire locks (although you may pass a stamp to other methods 70e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * that can use or convert it). The use of read lock modes relies on 71e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the associated code sections being side-effect-free. Unvalidated 72e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * optimistic read sections cannot call methods that are not known to 73e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * tolerate potential inconsistencies. Stamps use finite 74e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * representations, and are not cryptographically secure (i.e., a 75e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * valid stamp may be guessable). Stamp values may recycle after (no 76e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * sooner than) one year of continuous operation. A stamp held without 77e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * use or validation for longer than this period may fail to validate 78e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * correctly. StampedLocks are serializable, but always deserialize 79e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * into initial unlocked state, so they are not useful for remote 80e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * locking. 81e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 82e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>The scheduling policy of StampedLock does not consistently 83e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * prefer readers over writers or vice versa. All "try" methods are 84e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * best-effort and do not necessarily conform to any scheduling or 85e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * fairness policy. A zero return from any "try" method for acquiring 86e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * or converting locks does not carry any information about the state 87e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * of the lock; a subsequent invocation may succeed. 88e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 89e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p>Because it supports coordinated usage across multiple lock 90e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * modes, this class does not directly implement the {@link Lock} or 91e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@link ReadWriteLock} interfaces. However, a StampedLock may be 92e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link 93e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * #asReadWriteLock()} in applications requiring only the associated 94e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * set of functionality. 95e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 96e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <p><b>Sample Usage.</b> The following illustrates some usage idioms 97e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * in a class that maintains simple two-dimensional points. The sample 98e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * code illustrates some try/catch conventions even though they are 99e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * not strictly needed here because no exceptions can occur in their 100e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * bodies.<br> 101e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 102e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * <pre> {@code 103e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * class Point { 104e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * private double x, y; 105e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * private final StampedLock sl = new StampedLock(); 106e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 107e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * void move(double deltaX, double deltaY) { // an exclusively locked method 108e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * long stamp = sl.writeLock(); 109e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * try { 110e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * x += deltaX; 111e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * y += deltaY; 112e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } finally { 113e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * sl.unlockWrite(stamp); 114e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 115e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 116e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 117e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * double distanceFromOrigin() { // A read-only method 118e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * long stamp = sl.tryOptimisticRead(); 119e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * double currentX = x, currentY = y; 120e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * if (!sl.validate(stamp)) { 121e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * stamp = sl.readLock(); 122e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * try { 123e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * currentX = x; 124e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * currentY = y; 125e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } finally { 126e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * sl.unlockRead(stamp); 127e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 128e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 129e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * return Math.sqrt(currentX * currentX + currentY * currentY); 130e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 131e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 132e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * void moveIfAtOrigin(double newX, double newY) { // upgrade 133e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * // Could instead start with optimistic, not read mode 134e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * long stamp = sl.readLock(); 135e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * try { 136e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * while (x == 0.0 && y == 0.0) { 137e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * long ws = sl.tryConvertToWriteLock(stamp); 138e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * if (ws != 0L) { 139e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * stamp = ws; 140e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * x = newX; 141e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * y = newY; 142e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * break; 143e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 144e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * else { 145e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * sl.unlockRead(stamp); 146e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * stamp = sl.writeLock(); 147e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 148e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 149e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } finally { 150e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * sl.unlock(stamp); 151e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 152e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * } 153e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * }}</pre> 154e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 155e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @since 1.8 156e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @author Doug Lea 157e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 158e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniakpublic class StampedLock implements java.io.Serializable { 159e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /* 160e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Algorithmic notes: 161e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 162e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * The design employs elements of Sequence locks 163e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (as used in linux kernels; see Lameter's 164e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * http://www.lameter.com/gelato2005.pdf 165e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * and elsewhere; see 166e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html) 167e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * and Ordered RW locks (see Shirako et al 168e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * http://dl.acm.org/citation.cfm?id=2312015) 169e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 170e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Conceptually, the primary state of the lock includes a sequence 171e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * number that is odd when write-locked and even otherwise. 172e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * However, this is offset by a reader count that is non-zero when 173e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * read-locked. The read count is ignored when validating 174e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * "optimistic" seqlock-reader-style stamps. Because we must use 175e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * a small finite number of bits (currently 7) for readers, a 176e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * supplementary reader overflow word is used when the number of 177e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * readers exceeds the count field. We do this by treating the max 178e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * reader count value (RBITS) as a spinlock protecting overflow 179e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * updates. 180e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 181e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Waiters use a modified form of CLH lock used in 182e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * AbstractQueuedSynchronizer (see its internal documentation for 183e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * a fuller account), where each node is tagged (field mode) as 184e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * either a reader or writer. Sets of waiting readers are grouped 185e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (linked) under a common node (field cowait) so act as a single 186e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * node with respect to most CLH mechanics. By virtue of the 187e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * queue structure, wait nodes need not actually carry sequence 188e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * numbers; we know each is greater than its predecessor. This 189e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * simplifies the scheduling policy to a mainly-FIFO scheme that 190e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * incorporates elements of Phase-Fair locks (see Brandenburg & 191e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Anderson, especially http://www.cs.unc.edu/~bbb/diss/). In 192e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * particular, we use the phase-fair anti-barging rule: If an 193e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * incoming reader arrives while read lock is held but there is a 194e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * queued writer, this incoming reader is queued. (This rule is 195e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * responsible for some of the complexity of method acquireRead, 196e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * but without it, the lock becomes highly unfair.) Method release 197e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * does not (and sometimes cannot) itself wake up cowaiters. This 198e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * is done by the primary thread, but helped by any other threads 199e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * with nothing better to do in methods acquireRead and 200e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * acquireWrite. 201e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 202e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * These rules apply to threads actually queued. All tryLock forms 203e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * opportunistically try to acquire locks regardless of preference 204e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * rules, and so may "barge" their way in. Randomized spinning is 205e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * used in the acquire methods to reduce (increasingly expensive) 206e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * context switching while also avoiding sustained memory 207e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * thrashing among many threads. We limit spins to the head of 208e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * queue. A thread spin-waits up to SPINS times (where each 209e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * iteration decreases spin count with 50% probability) before 210e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * blocking. If, upon wakening it fails to obtain lock, and is 211e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * still (or becomes) the first waiting thread (which indicates 212e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * that some other thread barged and obtained lock), it escalates 213e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * spins (up to MAX_HEAD_SPINS) to reduce the likelihood of 214e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * continually losing to barging threads. 215e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 216e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Nearly all of these mechanics are carried out in methods 217e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * acquireWrite and acquireRead, that, as typical of such code, 218e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * sprawl out because actions and retries rely on consistent sets 219e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * of locally cached reads. 220e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 221e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * As noted in Boehm's paper (above), sequence validation (mainly 222e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * method validate()) requires stricter ordering rules than apply 223e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * to normal volatile reads (of "state"). To force orderings of 224e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * reads before a validation and the validation itself in those 225e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * cases where this is not already forced, we use 226e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Unsafe.loadFence. 227e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 228e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * The memory layout keeps lock state and queue pointers together 229e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * (normally on the same cache line). This usually works well for 230e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * read-mostly loads. In most other cases, the natural tendency of 231e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * adaptive-spin CLH locks to reduce memory contention lessens 232e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * motivation to further spread out contended locations, but might 233e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * be subject to future improvements. 234e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 235e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 236e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long serialVersionUID = -6001602636862214147L; 237e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 238e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Number of processors, for spin control */ 239e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int NCPU = Runtime.getRuntime().availableProcessors(); 240e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 241e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Maximum number of retries before enqueuing on acquisition */ 242e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0; 243e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 244e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Maximum number of retries before blocking at head on acquisition */ 245e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0; 246e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 247e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Maximum number of retries before re-blocking */ 248e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0; 249e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 250e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** The period for yielding when waiting for overflow spinlock */ 251e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1 252e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 253e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** The number of bits to use for reader count before overflowing */ 254e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int LG_READERS = 7; 255e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 256e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Values for lock state and stamp operations 257e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long RUNIT = 1L; 258e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long WBIT = 1L << LG_READERS; 259e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long RBITS = WBIT - 1L; 260e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long RFULL = RBITS - 1L; 261e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long ABITS = RBITS | WBIT; 262e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long SBITS = ~RBITS; // note overlap with ABITS 263e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 264e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Initial value for lock state; avoid failure value zero 265e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long ORIGIN = WBIT << 1; 266e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 267e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Special value from cancelled acquire methods so caller can throw IE 268e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long INTERRUPTED = 1L; 269e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 270e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Values for node status; order matters 271e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int WAITING = -1; 272e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int CANCELLED = 1; 273e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 274e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Modes for nodes (int not boolean to allow arithmetic) 275e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int RMODE = 0; 276e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final int WMODE = 1; 277e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 278e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Wait nodes */ 279e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak static final class WNode { 280e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak volatile WNode prev; 281e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak volatile WNode next; 282e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak volatile WNode cowait; // list of linked readers 283e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak volatile Thread thread; // non-null while possibly parked 284e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak volatile int status; // 0, WAITING, or CANCELLED 285e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final int mode; // RMODE or WMODE 286e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode(int m, WNode p) { mode = m; prev = p; } 287e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 288e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 289e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Head of CLH queue */ 290e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private transient volatile WNode whead; 291e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Tail (last) of CLH queue */ 292e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private transient volatile WNode wtail; 293e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 294e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // views 295e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak transient ReadLockView readLockView; 296e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak transient WriteLockView writeLockView; 297e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak transient ReadWriteLockView readWriteLockView; 298e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 299e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** Lock sequence/state */ 300e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private transient volatile long state; 301e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** extra reader count when state read count saturated */ 302e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private transient int readerOverflow; 303e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 304e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 305e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Creates a new lock, initially in unlocked state. 306e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 307e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public StampedLock() { 308e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak state = ORIGIN; 309e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 310e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 311e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 312e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Exclusively acquires the lock, blocking if necessary 313e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * until available. 314e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 315e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode 316e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 317e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long writeLock() { 318e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, next; // bypass acquireWrite in fully unlocked case only 319e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ((((s = state) & ABITS) == 0L && 320e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? 321e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak next : acquireWrite(false, 0L)); 322e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 323e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 324e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 325e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Exclusively acquires the lock if it is immediately available. 326e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 327e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode, 328e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * or zero if the lock is not available 329e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 330e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryWriteLock() { 331e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, next; 332e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ((((s = state) & ABITS) == 0L && 333e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? 334e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak next : 0L); 335e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 336e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 337e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 338e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Exclusively acquires the lock if it is available within the 339e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * given time and the current thread has not been interrupted. 340e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Behavior under timeout and interruption matches that specified 341e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * for method {@link Lock#tryLock(long,TimeUnit)}. 342e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 343e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param time the maximum time to wait for the lock 344e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param unit the time unit of the {@code time} argument 345e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode, 346e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * or zero if the lock is not available 347e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws InterruptedException if the current thread is interrupted 348e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * before acquiring the lock 349e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 350e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryWriteLock(long time, TimeUnit unit) 351e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throws InterruptedException { 352e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long nanos = unit.toNanos(time); 353e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!Thread.interrupted()) { 354e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long next, deadline; 355e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((next = tryWriteLock()) != 0L) 356e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 357e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 358e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 359e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((deadline = System.nanoTime() + nanos) == 0L) 360e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak deadline = 1L; 361e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((next = acquireWrite(true, deadline)) != INTERRUPTED) 362e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 363e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 364e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new InterruptedException(); 365e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 366e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 367e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 368e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Exclusively acquires the lock, blocking if necessary 369e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * until available or the current thread is interrupted. 370e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Behavior under interruption matches that specified 371e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * for method {@link Lock#lockInterruptibly()}. 372e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 373e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode 374e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws InterruptedException if the current thread is interrupted 375e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * before acquiring the lock 376e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 377e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long writeLockInterruptibly() throws InterruptedException { 378e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long next; 379e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!Thread.interrupted() && 380e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (next = acquireWrite(true, 0L)) != INTERRUPTED) 381e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 382e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new InterruptedException(); 383e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 384e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 385e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 386e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Non-exclusively acquires the lock, blocking if necessary 387e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * until available. 388e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 389e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode 390e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 391e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long readLock() { 392e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s = state, next; // bypass acquireRead on common uncontended case 393e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ((whead == wtail && (s & ABITS) < RFULL && 394e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ? 395e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak next : acquireRead(false, 0L)); 396e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 397e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 398e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 399e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Non-exclusively acquires the lock if it is immediately available. 400e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 401e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode, 402e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * or zero if the lock is not available 403e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 404e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryReadLock() { 405e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (;;) { 406e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, m, next; 407e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = (s = state) & ABITS) == WBIT) 408e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 409e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m < RFULL) { 410e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) 411e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 412e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 413e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((next = tryIncReaderOverflow(s)) != 0L) 414e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 415e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 416e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 417e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 418e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 419e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Non-exclusively acquires the lock if it is available within the 420e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * given time and the current thread has not been interrupted. 421e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Behavior under timeout and interruption matches that specified 422e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * for method {@link Lock#tryLock(long,TimeUnit)}. 423e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 424e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param time the maximum time to wait for the lock 425e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param unit the time unit of the {@code time} argument 426e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode, 427e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * or zero if the lock is not available 428e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws InterruptedException if the current thread is interrupted 429e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * before acquiring the lock 430e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 431e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryReadLock(long time, TimeUnit unit) 432e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throws InterruptedException { 433e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, m, next, deadline; 434e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long nanos = unit.toNanos(time); 435e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!Thread.interrupted()) { 436e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = (s = state) & ABITS) != WBIT) { 437e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m < RFULL) { 438e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) 439e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 440e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 441e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((next = tryIncReaderOverflow(s)) != 0L) 442e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 443e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 444e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (nanos <= 0L) 445e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 446e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((deadline = System.nanoTime() + nanos) == 0L) 447e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak deadline = 1L; 448e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((next = acquireRead(true, deadline)) != INTERRUPTED) 449e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 450e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 451e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new InterruptedException(); 452e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 453e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 454e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 455e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Non-exclusively acquires the lock, blocking if necessary 456e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * until available or the current thread is interrupted. 457e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Behavior under interruption matches that specified 458e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * for method {@link Lock#lockInterruptibly()}. 459e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 460e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp that can be used to unlock or convert mode 461e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws InterruptedException if the current thread is interrupted 462e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * before acquiring the lock 463e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 464e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long readLockInterruptibly() throws InterruptedException { 465e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long next; 466e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (!Thread.interrupted() && 467e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (next = acquireRead(true, 0L)) != INTERRUPTED) 468e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 469e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new InterruptedException(); 470e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 471e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 472e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 473e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a stamp that can later be validated, or zero 474e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * if exclusively locked. 475e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 476e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a stamp, or zero if exclusively locked 477e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 478e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryOptimisticRead() { 479e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s; 480e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (((s = state) & WBIT) == 0L) ? (s & SBITS) : 0L; 481e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 482e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 483e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 484e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns true if the lock has not been exclusively acquired 485e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * since issuance of the given stamp. Always returns false if the 486e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * stamp is zero. Always returns true if the stamp represents a 487e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * currently held lock. Invoking this method with a value not 488e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * obtained from {@link #tryOptimisticRead} or a locking method 489e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * for this lock has no defined effect or result. 490e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 491e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param stamp a stamp 492e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return {@code true} if the lock has not been exclusively acquired 493e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * since issuance of the given stamp; else false 494e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 495e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean validate(long stamp) { 496e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.loadFence(); 497e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (stamp & SBITS) == (state & SBITS); 498e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 499e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 500e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 501e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * If the lock state matches the given stamp, releases the 502e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * exclusive lock. 503e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 504e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param stamp a stamp returned by a write-lock operation 505e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws IllegalMonitorStateException if the stamp does 506e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * not match the current state of this lock 507e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 508e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void unlockWrite(long stamp) { 509e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode h; 510e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (state != stamp || (stamp & WBIT) == 0L) 511e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new IllegalMonitorStateException(); 512e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, (stamp += WBIT) == 0L ? ORIGIN : stamp); 513e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) != null && h.status != 0) 514e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 515e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 516e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 517e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 518e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * If the lock state matches the given stamp, releases the 519e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * non-exclusive lock. 520e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 521e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param stamp a stamp returned by a read-lock operation 522e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws IllegalMonitorStateException if the stamp does 523e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * not match the current state of this lock 524e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 525e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void unlockRead(long stamp) { 526e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, m; WNode h; 527e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (;;) { 528e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (((s = state) & SBITS) != (stamp & SBITS) || 529e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT) 530e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new IllegalMonitorStateException(); 531e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m < RFULL) { 532e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 533e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m == RUNIT && (h = whead) != null && h.status != 0) 534e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 535e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 536e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 537e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 538e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (tryDecReaderOverflow(s) != 0L) 539e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 540e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 541e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 542e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 543e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 544e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * If the lock state matches the given stamp, releases the 545e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * corresponding mode of the lock. 546e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 547e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param stamp a stamp returned by a lock operation 548e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @throws IllegalMonitorStateException if the stamp does 549e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * not match the current state of this lock 550e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 551e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void unlock(long stamp) { 552e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long a = stamp & ABITS, m, s; WNode h; 553e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while (((s = state) & SBITS) == (stamp & SBITS)) { 554e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = s & ABITS) == 0L) 555e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 556e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m == WBIT) { 557e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (a != m) 558e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 559e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s); 560e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) != null && h.status != 0) 561e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 562e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return; 563e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 564e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (a == 0L || a >= WBIT) 565e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 566e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m < RFULL) { 567e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 568e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m == RUNIT && (h = whead) != null && h.status != 0) 569e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 570e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return; 571e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 572e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 573e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (tryDecReaderOverflow(s) != 0L) 574e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return; 575e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 576e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new IllegalMonitorStateException(); 577e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 578e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 579e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 580e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * If the lock state matches the given stamp, atomically performs one of 581e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the following actions. If the stamp represents holding a write 582e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * lock, returns it. Or, if a read lock, if the write lock is 583e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * available, releases the read lock and returns a write stamp. 584e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Or, if an optimistic read, returns a write stamp only if 585e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * immediately available. This method returns zero in all other 586e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * cases. 587e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 588e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param stamp a stamp 589e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a valid write stamp, or zero on failure 590e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 591e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryConvertToWriteLock(long stamp) { 592e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long a = stamp & ABITS, m, s, next; 593e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while (((s = state) & SBITS) == (stamp & SBITS)) { 594e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = s & ABITS) == 0L) { 595e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (a != 0L) 596e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 597e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) 598e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 599e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 600e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m == WBIT) { 601e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (a != m) 602e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 603e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return stamp; 604e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 605e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m == RUNIT && a != 0L) { 606e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, 607e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak next = s - RUNIT + WBIT)) 608e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 609e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 610e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else 611e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 612e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 613e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 614e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 615e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 616e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 617e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * If the lock state matches the given stamp, atomically performs one of 618e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the following actions. If the stamp represents holding a write 619e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * lock, releases it and obtains a read lock. Or, if a read lock, 620e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * returns it. Or, if an optimistic read, acquires a read lock and 621e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * returns a read stamp only if immediately available. This method 622e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * returns zero in all other cases. 623e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 624e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param stamp a stamp 625e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a valid read stamp, or zero on failure 626e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 627e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryConvertToReadLock(long stamp) { 628e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long a = stamp & ABITS, m, s, next; WNode h; 629e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while (((s = state) & SBITS) == (stamp & SBITS)) { 630e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = s & ABITS) == 0L) { 631e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (a != 0L) 632e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 633e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m < RFULL) { 634e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) 635e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 636e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 637e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((next = tryIncReaderOverflow(s)) != 0L) 638e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 639e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 640e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m == WBIT) { 641e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (a != m) 642e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 643e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, next = s + (WBIT + RUNIT)); 644e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) != null && h.status != 0) 645e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 646e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 647e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 648e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (a != 0L && a < WBIT) 649e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return stamp; 650e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else 651e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 652e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 653e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 654e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 655e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 656e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 657e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * If the lock state matches the given stamp then, atomically, if the stamp 658e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * represents holding a lock, releases it and returns an 659e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * observation stamp. Or, if an optimistic read, returns it if 660e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * validated. This method returns zero in all other cases, and so 661e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * may be useful as a form of "tryUnlock". 662e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 663e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param stamp a stamp 664e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a valid optimistic read stamp, or zero on failure 665e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 666e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public long tryConvertToOptimisticRead(long stamp) { 667e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long a = stamp & ABITS, m, s, next; WNode h; 668e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.loadFence(); 669e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (;;) { 670e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (((s = state) & SBITS) != (stamp & SBITS)) 671e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 672e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = s & ABITS) == 0L) { 673e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (a != 0L) 674e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 675e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return s; 676e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 677e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m == WBIT) { 678e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (a != m) 679e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 680e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, 681e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak next = (s += WBIT) == 0L ? ORIGIN : s); 682e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) != null && h.status != 0) 683e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 684e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 685e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 686e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (a == 0L || a >= WBIT) 687e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 688e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m < RFULL) { 689e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) { 690e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m == RUNIT && (h = whead) != null && h.status != 0) 691e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 692e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next & SBITS; 693e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 694e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 695e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((next = tryDecReaderOverflow(s)) != 0L) 696e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next & SBITS; 697e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 698e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 699e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 700e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 701e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 702e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Releases the write lock if it is held, without requiring a 703e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * stamp value. This method may be useful for recovery after 704e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * errors. 705e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 706e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return {@code true} if the lock was held, else false 707e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 708e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryUnlockWrite() { 709e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s; WNode h; 710e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (((s = state) & WBIT) != 0L) { 711e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s); 712e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) != null && h.status != 0) 713e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 714e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return true; 715e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 716e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return false; 717e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 718e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 719e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 720e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Releases one hold of the read lock if it is held, without 721e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * requiring a stamp value. This method may be useful for recovery 722e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * after errors. 723e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 724e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return {@code true} if the read lock was held, else false 725e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 726e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryUnlockRead() { 727e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, m; WNode h; 728e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while ((m = (s = state) & ABITS) != 0L && m < WBIT) { 729e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m < RFULL) { 730e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 731e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m == RUNIT && (h = whead) != null && h.status != 0) 732e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 733e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return true; 734e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 735e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 736e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (tryDecReaderOverflow(s) != 0L) 737e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return true; 738e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 739e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return false; 740e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 741e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 742e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // status monitoring methods 743e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 744e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 745e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns combined state-held and overflow read count for given 746e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * state s. 747e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 748e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private int getReadLockCount(long s) { 749e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long readers; 750e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((readers = s & RBITS) >= RFULL) 751e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak readers = RFULL + readerOverflow; 752e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (int) readers; 753e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 754e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 755e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 756e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns {@code true} if the lock is currently held exclusively. 757e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 758e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return {@code true} if the lock is currently held exclusively 759e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 760e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean isWriteLocked() { 761e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (state & WBIT) != 0L; 762e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 763e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 764e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 765e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns {@code true} if the lock is currently held non-exclusively. 766e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 767e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return {@code true} if the lock is currently held non-exclusively 768e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 769e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean isReadLocked() { 770e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (state & RBITS) != 0L; 771e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 772e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 773e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 774e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Queries the number of read locks held for this lock. This 775e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * method is designed for use in monitoring system state, not for 776e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * synchronization control. 777e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return the number of read locks held 778e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 779e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public int getReadLockCount() { 780e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return getReadLockCount(state); 781e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 782e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 783e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 784e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a string identifying this lock, as well as its lock 785e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * state. The state, in brackets, includes the String {@code 786e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * "Unlocked"} or the String {@code "Write-locked"} or the String 787e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@code "Read-locks:"} followed by the current number of 788e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * read-locks held. 789e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 790e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return a string identifying this lock, as well as its lock state 791e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 792e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public String toString() { 793e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s = state; 794e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return super.toString() + 795e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ((s & ABITS) == 0L ? "[Unlocked]" : 796e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (s & WBIT) != 0L ? "[Write-locked]" : 797e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak "[Read-locks:" + getReadLockCount(s) + "]"); 798e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 799e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 800e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // views 801e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 802e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 803e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a plain {@link Lock} view of this StampedLock in which 804e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the {@link Lock#lock} method is mapped to {@link #readLock}, 805e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * and similarly for other methods. The returned Lock does not 806e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * support a {@link Condition}; method {@link 807e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Lock#newCondition()} throws {@code 808e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * UnsupportedOperationException}. 809e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 810e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return the lock 811e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 812e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Lock asReadLock() { 813e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ReadLockView v; 814e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ((v = readLockView) != null ? v : 815e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (readLockView = new ReadLockView())); 816e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 817e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 818e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 819e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a plain {@link Lock} view of this StampedLock in which 820e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * the {@link Lock#lock} method is mapped to {@link #writeLock}, 821e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * and similarly for other methods. The returned Lock does not 822e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * support a {@link Condition}; method {@link 823e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Lock#newCondition()} throws {@code 824e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * UnsupportedOperationException}. 825e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 826e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return the lock 827e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 828e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Lock asWriteLock() { 829e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WriteLockView v; 830e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ((v = writeLockView) != null ? v : 831e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (writeLockView = new WriteLockView())); 832e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 833e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 834e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 835e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Returns a {@link ReadWriteLock} view of this StampedLock in 836e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * which the {@link ReadWriteLock#readLock()} method is mapped to 837e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to 838e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * {@link #asWriteLock()}. 839e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 840e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return the lock 841e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 842e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public ReadWriteLock asReadWriteLock() { 843e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ReadWriteLockView v; 844e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ((v = readWriteLockView) != null ? v : 845e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (readWriteLockView = new ReadWriteLockView())); 846e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 847e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 848e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // view classes 849e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 850e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final class ReadLockView implements Lock { 851e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void lock() { readLock(); } 852e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void lockInterruptibly() throws InterruptedException { 853e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak readLockInterruptibly(); 854e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 855e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryLock() { return tryReadLock() != 0L; } 856e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryLock(long time, TimeUnit unit) 857e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throws InterruptedException { 858e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return tryReadLock(time, unit) != 0L; 859e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 860e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void unlock() { unstampedUnlockRead(); } 861e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Condition newCondition() { 862e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new UnsupportedOperationException(); 863e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 864e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 865e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 866e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final class WriteLockView implements Lock { 867e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void lock() { writeLock(); } 868e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void lockInterruptibly() throws InterruptedException { 869e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak writeLockInterruptibly(); 870e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 871e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryLock() { return tryWriteLock() != 0L; } 872e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public boolean tryLock(long time, TimeUnit unit) 873e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throws InterruptedException { 874e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return tryWriteLock(time, unit) != 0L; 875e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 876e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public void unlock() { unstampedUnlockWrite(); } 877e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Condition newCondition() { 878e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new UnsupportedOperationException(); 879e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 880e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 881e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 882e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final class ReadWriteLockView implements ReadWriteLock { 883e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Lock readLock() { return asReadLock(); } 884e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak public Lock writeLock() { return asWriteLock(); } 885e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 886e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 887e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Unlock methods without stamp argument checks for view classes. 888e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Needed because view-class lock methods throw away stamps. 889e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 890e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final void unstampedUnlockWrite() { 891e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode h; long s; 892e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (((s = state) & WBIT) == 0L) 893e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new IllegalMonitorStateException(); 894e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, (s += WBIT) == 0L ? ORIGIN : s); 895e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) != null && h.status != 0) 896e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 897e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 898e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 899e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak final void unstampedUnlockRead() { 900e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (;;) { 901e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, m; WNode h; 902e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = (s = state) & ABITS) == 0L || m >= WBIT) 903e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new IllegalMonitorStateException(); 904e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m < RFULL) { 905e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { 906e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (m == RUNIT && (h = whead) != null && h.status != 0) 907e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 908e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 909e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 910e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 911e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (tryDecReaderOverflow(s) != 0L) 912e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 913e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 914e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 915e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 916e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private void readObject(java.io.ObjectInputStream s) 917e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throws java.io.IOException, ClassNotFoundException { 918e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak s.defaultReadObject(); 919e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, ORIGIN); // reset to unlocked state 920e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 921e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 922e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // internals 923e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 924e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 925e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Tries to increment readerOverflow by first setting state 926e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * access bits value to RBITS, indicating hold of spinlock, 927e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * then updating, then releasing. 928e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 929e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s a reader overflow stamp: (s & ABITS) >= RFULL 930e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return new stamp on success, else zero 931e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 932e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private long tryIncReaderOverflow(long s) { 933e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // assert (s & ABITS) >= RFULL; 934e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((s & ABITS) == RFULL) { 935e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) { 936e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ++readerOverflow; 937e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, s); 938e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return s; 939e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 940e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 941e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((LockSupport.nextSecondarySeed() & 942e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak OVERFLOW_YIELD_RATE) == 0) 943e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread.yield(); 944e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 945e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 946e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 947e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 948e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Tries to decrement readerOverflow. 949e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 950e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param s a reader overflow stamp: (s & ABITS) >= RFULL 951e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return new stamp on success, else zero 952e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 953e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private long tryDecReaderOverflow(long s) { 954e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // assert (s & ABITS) >= RFULL; 955e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((s & ABITS) == RFULL) { 956e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) { 957e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak int r; long next; 958e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((r = readerOverflow) > 0) { 959e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak readerOverflow = r - 1; 960e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak next = s; 961e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 962e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else 963e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak next = s - RUNIT; 964e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putLongVolatile(this, STATE, next); 965e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return next; 966e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 967e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 968e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((LockSupport.nextSecondarySeed() & 969e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak OVERFLOW_YIELD_RATE) == 0) 970e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread.yield(); 971e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return 0L; 972e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 973e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 974e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 975e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * Wakes up the successor of h (normally whead). This is normally 976e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * just h.next, but may require traversal from wtail if next 977e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * pointers are lagging. This may fail to wake up an acquiring 978e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * thread when one or more have been cancelled, but the cancel 979e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * methods themselves provide extra safeguards to ensure liveness. 980e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 981e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private void release(WNode h) { 982e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (h != null) { 983e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode q; Thread w; 984e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapInt(h, WSTATUS, WAITING, 0); 985e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((q = h.next) == null || q.status == CANCELLED) { 986e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (WNode t = wtail; t != null && t != h; t = t.prev) 987e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (t.status <= 0) 988e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q = t; 989e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 990e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (q != null && (w = q.thread) != null) 991e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.unpark(w); 992e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 993e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 994e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 995e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 996e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * See above for explanation. 997e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 998e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param interruptible true if should check interrupts and if so 999e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * return INTERRUPTED 1000e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param deadline if nonzero, the System.nanoTime value to timeout 1001e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * at (and return zero) 1002e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return next state, or INTERRUPTED 1003e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 1004e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private long acquireWrite(boolean interruptible, long deadline) { 1005e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode node = null, p; 1006e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (int spins = -1;;) { // spin while enqueuing 1007e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long m, s, ns; 1008e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = (s = state) & ABITS) == 0L) { 1009e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) 1010e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ns; 1011e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1012e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (spins < 0) 1013e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak spins = (m == WBIT && wtail == whead) ? SPINS : 0; 1014e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (spins > 0) { 1015e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (LockSupport.nextSecondarySeed() >= 0) 1016e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak --spins; 1017e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1018e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((p = wtail) == null) { // initialize queue 1019e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode hd = new WNode(WMODE, null); 1020e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapObject(this, WHEAD, null, hd)) 1021e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak wtail = hd; 1022e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1023e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (node == null) 1024e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node = new WNode(WMODE, p); 1025e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (node.prev != p) 1026e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.prev = p; 1027e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (U.compareAndSwapObject(this, WTAIL, p, node)) { 1028e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p.next = node; 1029e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1030e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1031e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1032e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1033e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak boolean wasInterrupted = false; 1034e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (int spins = -1;;) { 1035e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode h, np, pp; int ps; 1036e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) == p) { 1037e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (spins < 0) 1038e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak spins = HEAD_SPINS; 1039e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (spins < MAX_HEAD_SPINS) 1040e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak spins <<= 1; 1041e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (int k = spins;;) { // spin at head 1042e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s, ns; 1043e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (((s = state) & ABITS) == 0L) { 1044e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapLong(this, STATE, s, 1045e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ns = s + WBIT)) { 1046e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak whead = node; 1047e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.prev = null; 1048e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (wasInterrupted) 1049e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread.currentThread().interrupt(); 1050e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ns; 1051e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1052e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1053e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (LockSupport.nextSecondarySeed() >= 0 && 1054e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak --k <= 0) 1055e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1056e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1057e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1058e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (h != null) { // help release stale waiters 1059e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode c; Thread w; 1060e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while ((c = h.cowait) != null) { 1061e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) && 1062e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (w = c.thread) != null) 1063e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.unpark(w); 1064e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1065e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1066e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (whead == h) { 1067e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((np = node.prev) != p) { 1068e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (np != null) 1069e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (p = np).next = node; // stale 1070e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1071e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((ps = p.status) == 0) 1072e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapInt(p, WSTATUS, 0, WAITING); 1073e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (ps == CANCELLED) { 1074e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((pp = p.prev) != null) { 1075e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.prev = pp; 1076e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak pp.next = node; 1077e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1078e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1079e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else { 1080e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long time; // 0 argument to park means no timeout 1081e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (deadline == 0L) 1082e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak time = 0L; 1083e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((time = deadline - System.nanoTime()) <= 0L) 1084e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return cancelWaiter(node, node, false); 1085e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread wt = Thread.currentThread(); 1086e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putObject(wt, PARKBLOCKER, this); 1087e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.thread = wt; 1088e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (p.status < 0 && (p != h || (state & ABITS) != 0L) && 1089e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak whead == h && node.prev == p) 1090e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.park(false, time); // emulate LockSupport.park 1091e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.thread = null; 1092e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putObject(wt, PARKBLOCKER, null); 1093e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (Thread.interrupted()) { 1094e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (interruptible) 1095e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return cancelWaiter(node, node, true); 1096e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak wasInterrupted = true; 1097e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1098e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1099e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1100e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1101e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1102e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1103e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 1104e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * See above for explanation. 1105e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 1106e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param interruptible true if should check interrupts and if so 1107e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * return INTERRUPTED 1108e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param deadline if nonzero, the System.nanoTime value to timeout 1109e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * at (and return zero) 1110e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return next state, or INTERRUPTED 1111e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 1112e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private long acquireRead(boolean interruptible, long deadline) { 1113e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak boolean wasInterrupted = false; 1114e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode node = null, p; 1115e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (int spins = -1;;) { 1116e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode h; 1117e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) == (p = wtail)) { 1118e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (long m, s, ns;;) { 1119e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = (s = state) & ABITS) < RFULL ? 1120e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) : 1121e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) { 1122e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (wasInterrupted) 1123e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread.currentThread().interrupt(); 1124e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ns; 1125e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1126e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m >= WBIT) { 1127e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (spins > 0) { 1128e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (LockSupport.nextSecondarySeed() >= 0) 1129e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak --spins; 1130e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1131e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else { 1132e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (spins == 0) { 1133e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode nh = whead, np = wtail; 1134e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((nh == h && np == p) || (h = nh) != (p = np)) 1135e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1136e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1137e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak spins = SPINS; 1138e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1139e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1140e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1141e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1142e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (p == null) { // initialize queue 1143e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode hd = new WNode(WMODE, null); 1144e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapObject(this, WHEAD, null, hd)) 1145e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak wtail = hd; 1146e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1147e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (node == null) 1148e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node = new WNode(RMODE, p); 1149e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (h == p || p.mode != RMODE) { 1150e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (node.prev != p) 1151e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.prev = p; 1152e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (U.compareAndSwapObject(this, WTAIL, p, node)) { 1153e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p.next = node; 1154e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1155e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1156e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1157e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (!U.compareAndSwapObject(p, WCOWAIT, 1158e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.cowait = p.cowait, node)) 1159e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.cowait = null; 1160e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else { 1161e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (;;) { 1162e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode pp, c; Thread w; 1163e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) != null && (c = h.cowait) != null && 1164e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) && 1165e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (w = c.thread) != null) // help release 1166e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.unpark(w); 1167e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (h == (pp = p.prev) || h == p || pp == null) { 1168e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long m, s, ns; 1169e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak do { 1170e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = (s = state) & ABITS) < RFULL ? 1171e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, 1172e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ns = s + RUNIT) : 1173e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (m < WBIT && 1174e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (ns = tryIncReaderOverflow(s)) != 0L)) { 1175e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (wasInterrupted) 1176e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread.currentThread().interrupt(); 1177e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ns; 1178e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1179e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } while (m < WBIT); 1180e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1181e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (whead == h && p.prev == pp) { 1182e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long time; 1183e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (pp == null || h == p || p.status > 0) { 1184e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node = null; // throw away 1185e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1186e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1187e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (deadline == 0L) 1188e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak time = 0L; 1189e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((time = deadline - System.nanoTime()) <= 0L) { 1190e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (wasInterrupted) 1191e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread.currentThread().interrupt(); 1192e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return cancelWaiter(node, p, false); 1193e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1194e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread wt = Thread.currentThread(); 1195e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putObject(wt, PARKBLOCKER, this); 1196e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.thread = wt; 1197e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h != pp || (state & ABITS) == WBIT) && 1198e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak whead == h && p.prev == pp) 1199e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.park(false, time); 1200e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.thread = null; 1201e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putObject(wt, PARKBLOCKER, null); 1202e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (Thread.interrupted()) { 1203e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (interruptible) 1204e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return cancelWaiter(node, p, true); 1205e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak wasInterrupted = true; 1206e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1207e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1208e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1209e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1210e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1211e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1212e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (int spins = -1;;) { 1213e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode h, np, pp; int ps; 1214e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((h = whead) == p) { 1215e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (spins < 0) 1216e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak spins = HEAD_SPINS; 1217e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (spins < MAX_HEAD_SPINS) 1218e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak spins <<= 1; 1219e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (int k = spins;;) { // spin at head 1220e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long m, s, ns; 1221e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((m = (s = state) & ABITS) < RFULL ? 1222e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) : 1223e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) { 1224e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode c; Thread w; 1225e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak whead = node; 1226e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.prev = null; 1227e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while ((c = node.cowait) != null) { 1228e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapObject(node, WCOWAIT, 1229e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak c, c.cowait) && 1230e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (w = c.thread) != null) 1231e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.unpark(w); 1232e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1233e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (wasInterrupted) 1234e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread.currentThread().interrupt(); 1235e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return ns; 1236e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1237e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (m >= WBIT && 1238e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak LockSupport.nextSecondarySeed() >= 0 && --k <= 0) 1239e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1240e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1241e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1242e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (h != null) { 1243e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode c; Thread w; 1244e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while ((c = h.cowait) != null) { 1245e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) && 1246e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (w = c.thread) != null) 1247e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.unpark(w); 1248e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1249e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1250e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (whead == h) { 1251e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((np = node.prev) != p) { 1252e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (np != null) 1253e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (p = np).next = node; // stale 1254e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1255e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((ps = p.status) == 0) 1256e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapInt(p, WSTATUS, 0, WAITING); 1257e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if (ps == CANCELLED) { 1258e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((pp = p.prev) != null) { 1259e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.prev = pp; 1260e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak pp.next = node; 1261e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1262e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1263e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else { 1264e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long time; 1265e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (deadline == 0L) 1266e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak time = 0L; 1267e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else if ((time = deadline - System.nanoTime()) <= 0L) 1268e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return cancelWaiter(node, node, false); 1269e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread wt = Thread.currentThread(); 1270e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putObject(wt, PARKBLOCKER, this); 1271e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.thread = wt; 1272e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (p.status < 0 && 1273e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (p != h || (state & ABITS) == WBIT) && 1274e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak whead == h && node.prev == p) 1275e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.park(false, time); 1276e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.thread = null; 1277e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.putObject(wt, PARKBLOCKER, null); 1278e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (Thread.interrupted()) { 1279e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (interruptible) 1280e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return cancelWaiter(node, node, true); 1281e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak wasInterrupted = true; 1282e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1283e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1284e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1285e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1286e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1287e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1288e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak /** 1289e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * If node non-null, forces cancel status and unsplices it from 1290e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * queue if possible and wakes up any cowaiters (of the node, or 1291e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * group, as applicable), and in any case helps release current 1292e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * first waiter if lock is free. (Calling with null arguments 1293e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * serves as a conditional form of release, which is not currently 1294e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * needed but may be needed under possible future cancellation 1295e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * policies). This is a variant of cancellation methods in 1296e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * AbstractQueuedSynchronizer (see its detailed explanation in AQS 1297e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * internal documentation). 1298e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * 1299e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param node if nonnull, the waiter 1300e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param group either node or the group node is cowaiting with 1301e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @param interrupted if already interrupted 1302e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak * @return INTERRUPTED if interrupted or Thread.interrupted, else zero 1303e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak */ 1304e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private long cancelWaiter(WNode node, WNode group, boolean interrupted) { 1305e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (node != null && group != null) { 1306e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak Thread w; 1307e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.status = CANCELLED; 1308e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // unsplice cancelled nodes from group 1309e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (WNode p = group, q; (q = p.cowait) != null;) { 1310e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (q.status == CANCELLED) { 1311e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapObject(p, WCOWAIT, q, q.cowait); 1312e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p = group; // restart 1313e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1314e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak else 1315e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak p = q; 1316e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1317e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (group == node) { 1318e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (WNode r = group.cowait; r != null; r = r.cowait) { 1319e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((w = r.thread) != null) 1320e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.unpark(w); // wake up uncancelled co-waiters 1321e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1322e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (WNode pred = node.prev; pred != null; ) { // unsplice 1323e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode succ, pp; // find valid successor 1324e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while ((succ = node.next) == null || 1325e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak succ.status == CANCELLED) { 1326e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode q = null; // find successor the slow way 1327e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (WNode t = wtail; t != null && t != node; t = t.prev) 1328e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (t.status != CANCELLED) 1329e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q = t; // don't link if succ cancelled 1330e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (succ == q || // ensure accurate successor 1331e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapObject(node, WNEXT, 1332e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak succ, succ = q)) { 1333e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (succ == null && node == wtail) 1334e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapObject(this, WTAIL, node, pred); 1335e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1336e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1337e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1338e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (pred.next == node) // unsplice pred link 1339e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapObject(pred, WNEXT, node, succ); 1340e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (succ != null && (w = succ.thread) != null) { 1341e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak succ.thread = null; 1342e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.unpark(w); // wake up succ to observe new pred 1343e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1344e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (pred.status != CANCELLED || (pp = pred.prev) == null) 1345e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1346e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak node.prev = pp; // repeat if new pred wrong/cancelled 1347e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak U.compareAndSwapObject(pp, WNEXT, pred, succ); 1348e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak pred = pp; 1349e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1350e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1351e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1352e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNode h; // Possibly release first waiter 1353e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak while ((h = whead) != null) { 1354e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak long s; WNode q; // similar to release() but check eligibility 1355e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if ((q = h.next) == null || q.status == CANCELLED) { 1356e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak for (WNode t = wtail; t != null && t != h; t = t.prev) 1357e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (t.status <= 0) 1358e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak q = t; 1359e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1360e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (h == whead) { 1361e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak if (q != null && h.status == 0 && 1362e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak ((s = state) & ABITS) != WBIT && // waiter is eligible 1363e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (s == 0L || q.mode == RMODE)) 1364e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak release(h); 1365e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak break; 1366e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1367e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1368e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L; 1369e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1370e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1371e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak // Unsafe mechanics 1372e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final sun.misc.Unsafe U = sun.misc.Unsafe.getUnsafe(); 1373e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long STATE; 1374e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long WHEAD; 1375e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long WTAIL; 1376e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long WNEXT; 1377e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long WSTATUS; 1378e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long WCOWAIT; 1379e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak private static final long PARKBLOCKER; 1380e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1381e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak static { 1382e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak try { 1383e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak STATE = U.objectFieldOffset 1384e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (StampedLock.class.getDeclaredField("state")); 1385e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WHEAD = U.objectFieldOffset 1386e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (StampedLock.class.getDeclaredField("whead")); 1387e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WTAIL = U.objectFieldOffset 1388e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (StampedLock.class.getDeclaredField("wtail")); 1389e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1390e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WSTATUS = U.objectFieldOffset 1391e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (WNode.class.getDeclaredField("status")); 1392e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WNEXT = U.objectFieldOffset 1393e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (WNode.class.getDeclaredField("next")); 1394e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak WCOWAIT = U.objectFieldOffset 1395e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (WNode.class.getDeclaredField("cowait")); 1396e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak 1397e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak PARKBLOCKER = U.objectFieldOffset 1398e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak (Thread.class.getDeclaredField("parkBlocker")); 1399e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } catch (ReflectiveOperationException e) { 1400e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak throw new Error(e); 1401e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1402e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak } 1403e8b323c7cb7d55be9a4df579231e44f04f53d766Przemyslaw Szczepaniak} 1404