--- jsr166/src/jsr166e/StampedLock.java 2013/01/22 15:42:28 1.28 +++ jsr166/src/jsr166e/StampedLock.java 2013/06/19 14:55:40 1.36 @@ -5,10 +5,12 @@ */ package jsr166e; - -import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.TimeUnit; -import java.util.concurrent.locks.*; +import java.util.concurrent.ThreadLocalRandom; +import java.util.concurrent.locks.Lock; +import java.util.concurrent.locks.Condition; +import java.util.concurrent.locks.ReadWriteLock; +import java.util.concurrent.locks.LockSupport; /** * A capability-based lock with three modes for controlling read/write @@ -37,19 +39,20 @@ import java.util.concurrent.locks.*; *
  • Optimistic Reading. Method {@link #tryOptimisticRead} * returns a non-zero stamp only if the lock is not currently held * in write mode. Method {@link #validate} returns true if the lock - * has not since been acquired in write mode. This mode can be - * thought of as an extremely weak version of a read-lock, that can - * be broken by a writer at any time. The use of optimistic mode - * for short read-only code segments often reduces contention and - * improves throughput. However, its use is inherently fragile. - * Optimistic read sections should only read fields and hold them in - * local variables for later use after validation. Fields read while - * in optimistic mode may be wildly inconsistent, so usage applies - * only when you are familiar enough with data representations to - * check consistency and/or repeatedly invoke method {@code - * validate()}. For example, such steps are typically required when - * first reading an object or array reference, and then accessing - * one of its fields, elements or methods.
    • + * has not been acquired in write mode since obtaining a given + * stamp. This mode can be thought of as an extremely weak version + * of a read-lock, that can be broken by a writer at any time. The + * use of optimistic mode for short read-only code segments often + * reduces contention and improves throughput. However, its use is + * inherently fragile. Optimistic read sections should only read + * fields and hold them in local variables for later use after + * validation. Fields read while in optimistic mode may be wildly + * inconsistent, so usage applies only when you are familiar enough + * with data representations to check consistency and/or repeatedly + * invoke method {@code validate()}. For example, such steps are + * typically required when first reading an object or array + * reference, and then accessing one of its fields, elements or + * methods. * * * @@ -115,34 +118,17 @@ import java.util.concurrent.locks.*; * } * } * - * double distanceFromOriginV1() { // A read-only method - * long stamp; - * if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic - * double currentX = x; - * double currentY = y; - * if (sl.validate(stamp)) - * return Math.sqrt(currentX * currentX + currentY * currentY); - * } - * stamp = sl.readLock(); // fall back to read lock - * try { - * double currentX = x; - * double currentY = y; - * return Math.sqrt(currentX * currentX + currentY * currentY); - * } finally { - * sl.unlockRead(stamp); - * } - * } - * - * double distanceFromOriginV2() { // combines code paths - * double currentX = 0.0, currentY = 0.0; - * for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) { - * try { - * currentX = x; - * currentY = y; - * } finally { - * if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate - * break; - * } + * double distanceFromOrigin() { // A read-only method + * long stamp = sl.tryOptimisticRead(); + * double currentX = x, currentY = y; + * if (!sl.validate(stamp)) { + * stamp = sl.readLock(); + * try { + * currentX = x; + * currentY = y; + * } finally { + * sl.unlockRead(stamp); + * } * } * return Math.sqrt(currentX * currentX + currentY * currentY); * } @@ -198,13 +184,13 @@ public class StampedLock implements java * * Waiters use a modified form of CLH lock used in * AbstractQueuedSynchronizer (see its internal documentation for - * a fuller account), where each node it tagged (field mode) as + * a fuller account), where each node is tagged (field mode) as * either a reader or writer. Sets of waiting readers are grouped * (linked) under a common node (field cowait) so act as a single - * node with respect to most CLH mechanics. By virtue of its - * structure, wait nodes need not actually carry sequence numbers; - * we know each is >= its predecessor. These queue mechanics - * simplify the scheduling policy to a mainly-FIFO scheme that + * node with respect to most CLH mechanics. By virtue of the + * queue structure, wait nodes need not actually carry sequence + * numbers; we know each is greater than its predecessor. This + * simplifies the scheduling policy to a mainly-FIFO scheme that * incorporates elements of Phase-Fair locks (see Brandenburg & * Anderson, especially http://www.cs.unc.edu/~bbb/diss/). In * particular, we use the phase-fair anti-barging rule: If an @@ -229,8 +215,8 @@ public class StampedLock implements java * * Nearly all of these mechanics are carried out in methods * acquireWrite and acquireRead, that, as typical of such code, - * sprawl out because actions and retries rely on consitent sets - * of locally cahced reads. + * sprawl out because actions and retries rely on consistent sets + * of locally cached reads. * * As noted in Boehm's paper (above), sequence validation (mainly * method validate()) requires stricter ordering rules than apply @@ -329,7 +315,7 @@ public class StampedLock implements java * @return a stamp that can be used to unlock or convert mode */ public long writeLock() { - long s, next; // bypass acquireWrite in fully onlocked case only + long s, next; // bypass acquireWrite in fully unlocked case only return ((((s = state) & ABITS) == 0L && U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ? next : acquireWrite(false, 0L)); @@ -354,6 +340,8 @@ public class StampedLock implements java * Behavior under timeout and interruption matches that specified * for method {@link Lock#tryLock(long,TimeUnit)}. * + * @param time the maximum time to wait for the lock + * @param unit the time unit of the {@code time} argument * @return a stamp that can be used to unlock or convert mode, * or zero if the lock is not available * @throws InterruptedException if the current thread is interrupted @@ -364,7 +352,7 @@ public class StampedLock implements java long nanos = unit.toNanos(time); if (!Thread.interrupted()) { long next, deadline; - if ((next = tryWriteLock()) != 0) + if ((next = tryWriteLock()) != 0L) return next; if (nanos <= 0L) return 0L; @@ -401,7 +389,7 @@ public class StampedLock implements java * @return a stamp that can be used to unlock or convert mode */ public long readLock() { - long s, next; // bypass acquireRead on fully onlocked case only + long s, next; // bypass acquireRead on fully unlocked case only return ((((s = state) & ABITS) == 0L && U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ? next : acquireRead(false, 0L)); @@ -433,6 +421,8 @@ public class StampedLock implements java * Behavior under timeout and interruption matches that specified * for method {@link Lock#tryLock(long,TimeUnit)}. * + * @param time the maximum time to wait for the lock + * @param unit the time unit of the {@code time} argument * @return a stamp that can be used to unlock or convert mode, * or zero if the lock is not available * @throws InterruptedException if the current thread is interrupted @@ -440,11 +430,17 @@ public class StampedLock implements java */ public long tryReadLock(long time, TimeUnit unit) throws InterruptedException { - long next, deadline; + long s, m, next, deadline; long nanos = unit.toNanos(time); if (!Thread.interrupted()) { - if ((next = tryReadLock()) != 0) - return next; + if ((m = (s = state) & ABITS) != WBIT) { + if (m < RFULL) { + if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) + return next; + } + else if ((next = tryIncReaderOverflow(s)) != 0L) + return next; + } if (nanos <= 0L) return 0L; if ((deadline = System.nanoTime() + nanos) == 0L) @@ -488,9 +484,12 @@ public class StampedLock implements java * Returns true if the lock has not been exclusively acquired * since issuance of the given stamp. Always returns false if the * stamp is zero. Always returns true if the stamp represents a - * currently held lock. + * currently held lock. Invoking this method with a value not + * obtained from {@link #tryOptimisticRead} or a locking method + * for this lock has no defined effect or result. * - * @return true if the lock has not been exclusively acquired + * @param stamp a stamp + * @return {@code true} if the lock has not been exclusively acquired * since issuance of the given stamp; else false */ public boolean validate(long stamp) { @@ -524,25 +523,21 @@ public class StampedLock implements java * not match the current state of this lock */ public void unlockRead(long stamp) { - long s, m; WNode h; - if ((stamp & RBITS) != 0L) { - while (((s = state) & SBITS) == (stamp & SBITS)) { - if ((m = s & ABITS) == 0L) + long s, m; WNode h; + for (;;) { + if (((s = state) & SBITS) != (stamp & SBITS) || + (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT) + throw new IllegalMonitorStateException(); + if (m < RFULL) { + if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { + if (m == RUNIT && (h = whead) != null && h.status != 0) + release(h); break; - else if (m < RFULL) { - if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { - if (m == RUNIT && (h = whead) != null && h.status != 0) - release(h); - return; - } } - else if (m >= WBIT) - break; - else if (tryDecReaderOverflow(s) != 0L) - return; } + else if (tryDecReaderOverflow(s) != 0L) + break; } - throw new IllegalMonitorStateException(); } /** @@ -707,7 +702,7 @@ public class StampedLock implements java * stamp value. This method may be useful for recovery after * errors. * - * @return true if the lock was held, else false + * @return {@code true} if the lock was held, else false */ public boolean tryUnlockWrite() { long s; WNode h; @@ -725,7 +720,7 @@ public class StampedLock implements java * requiring a stamp value. This method may be useful for recovery * after errors. * - * @return true if the read lock was held, else false + * @return {@code true} if the read lock was held, else false */ public boolean tryUnlockRead() { long s, m; WNode h; @@ -743,31 +738,67 @@ public class StampedLock implements java return false; } + // status monitoring methods + + /** + * Returns combined state-held and overflow read count for given + * state s. + */ + private int getReadLockCount(long s) { + long readers; + if ((readers = s & RBITS) >= RFULL) + readers = RFULL + readerOverflow; + return (int) readers; + } + /** - * Returns true if the lock is currently held exclusively. + * Returns {@code true} if the lock is currently held exclusively. * - * @return true if the lock is currently held exclusively + * @return {@code true} if the lock is currently held exclusively */ public boolean isWriteLocked() { return (state & WBIT) != 0L; } /** - * Returns true if the lock is currently held non-exclusively. + * Returns {@code true} if the lock is currently held non-exclusively. * - * @return true if the lock is currently held non-exclusively + * @return {@code true} if the lock is currently held non-exclusively */ public boolean isReadLocked() { return (state & RBITS) != 0L; } - private void readObject(java.io.ObjectInputStream s) - throws java.io.IOException, ClassNotFoundException { - s.defaultReadObject(); - state = ORIGIN; // reset to unlocked state + /** + * Queries the number of read locks held for this lock. This + * method is designed for use in monitoring system state, not for + * synchronization control. + * @return the number of read locks held + */ + public int getReadLockCount() { + return getReadLockCount(state); } /** + * Returns a string identifying this lock, as well as its lock + * state. The state, in brackets, includes the String {@code + * "Unlocked"} or the String {@code "Write-locked"} or the String + * {@code "Read-locks:"} followed by the current number of + * read-locks held. + * + * @return a string identifying this lock, as well as its lock state + */ + public String toString() { + long s = state; + return super.toString() + + ((s & ABITS) == 0L ? "[Unlocked]" : + (s & WBIT) != 0L ? "[Write-locked]" : + "[Read-locks:" + getReadLockCount(s) + "]"); + } + + // views + + /** * Returns a plain {@link Lock} view of this StampedLock in which * the {@link Lock#lock} method is mapped to {@link #readLock}, * and similarly for other methods. The returned Lock does not @@ -825,8 +856,7 @@ public class StampedLock implements java throws InterruptedException { return tryReadLock(time, unit) != 0L; } - // note that we give up ability to check mode so just use current state - public void unlock() { unlockRead(state); } + public void unlock() { unstampedUnlockRead(); } public Condition newCondition() { throw new UnsupportedOperationException(); } @@ -842,7 +872,7 @@ public class StampedLock implements java throws InterruptedException { return tryWriteLock(time, unit) != 0L; } - public void unlock() { unlockWrite(state); } + public void unlock() { unstampedUnlockWrite(); } public Condition newCondition() { throw new UnsupportedOperationException(); } @@ -853,6 +883,41 @@ public class StampedLock implements java public Lock writeLock() { return asWriteLock(); } } + // Unlock methods without stamp argument checks for view classes. + // Needed because view-class lock methods throw away stamps. + + final void unstampedUnlockWrite() { + WNode h; long s; + if (((s = state) & WBIT) == 0L) + throw new IllegalMonitorStateException(); + state = (s += WBIT) == 0L ? ORIGIN : s; + if ((h = whead) != null && h.status != 0) + release(h); + } + + final void unstampedUnlockRead() { + for (;;) { + long s, m; WNode h; + if ((m = (s = state) & ABITS) == 0L || m >= WBIT) + throw new IllegalMonitorStateException(); + else if (m < RFULL) { + if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { + if (m == RUNIT && (h = whead) != null && h.status != 0) + release(h); + break; + } + } + else if (tryDecReaderOverflow(s) != 0L) + break; + } + } + + private void readObject(java.io.ObjectInputStream s) + throws java.io.IOException, ClassNotFoundException { + s.defaultReadObject(); + state = ORIGIN; // reset to unlocked state + } + // internals /** @@ -860,10 +925,11 @@ public class StampedLock implements java * access bits value to RBITS, indicating hold of spinlock, * then updating, then releasing. * - * @param s, assumed that (s & ABITS) >= RFULL + * @param s a reader overflow stamp: (s & ABITS) >= RFULL * @return new stamp on success, else zero */ private long tryIncReaderOverflow(long s) { + // assert (s & ABITS) >= RFULL; if ((s & ABITS) == RFULL) { if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) { ++readerOverflow; @@ -880,10 +946,11 @@ public class StampedLock implements java /** * Tries to decrement readerOverflow. * - * @param s, assumed that (s & ABITS) >= RFULL + * @param s a reader overflow stamp: (s & ABITS) >= RFULL * @return new stamp on success, else zero */ private long tryDecReaderOverflow(long s) { + // assert (s & ABITS) >= RFULL; if ((s & ABITS) == RFULL) { if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) { int r; long next; @@ -903,7 +970,7 @@ public class StampedLock implements java return 0L; } - /* + /** * Wakes up the successor of h (normally whead). This is normally * just h.next, but may require traversal from wtail if next * pointers are lagging. This may fail to wake up an acquiring @@ -977,11 +1044,12 @@ public class StampedLock implements java (p = np).next = node; // stale if (whead == p) { for (int k = spins;;) { // spin at head - if (((s = state) & ABITS) == 0L && - U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) { - whead = node; - node.prev = null; - return ns; + if (((s = state) & ABITS) == 0L) { + if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) { + whead = node; + node.prev = null; + return ns; + } } else if (ThreadLocalRandom.current().nextInt() >= 0 && --k <= 0) @@ -1003,15 +1071,17 @@ public class StampedLock implements java if (deadline == 0L) time = 0L; else if ((time = deadline - System.nanoTime()) <= 0L) - return cancelWaiter(node, null, false); - node.thread = Thread.currentThread(); + return cancelWaiter(node, node, false); + Thread wt = Thread.currentThread(); + U.putObject(wt, PARKBLOCKER, this); // emulate LockSupport.park + node.thread = wt; if (node.prev == p && p.status == WAITING && // recheck - (p != whead || (state & ABITS) != 0L)) { + (p != whead || (state & ABITS) != 0L)) U.park(false, time); - if (interruptible && Thread.interrupted()) - return cancelWaiter(node, null, true); - } node.thread = null; + U.putObject(wt, PARKBLOCKER, null); + if (interruptible && Thread.interrupted()) + return cancelWaiter(node, node, true); } } } @@ -1033,11 +1103,9 @@ public class StampedLock implements java if (group == null && (h = whead) != null && (q = h.next) != null && q.mode != RMODE) break; - if ((m = (s = state) & ABITS) == WBIT) - break; - if (m < RFULL ? + if ((m = (s = state) & ABITS) < RFULL ? U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) : - (ns = tryIncReaderOverflow(s)) != 0L) { + (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) { if (group != null) { // help release others for (WNode r = group;;) { if ((w = r.thread) != null) { @@ -1051,6 +1119,8 @@ public class StampedLock implements java } return ns; } + if (m >= WBIT) + break; } if (spins > 0) { if (ThreadLocalRandom.current().nextInt() >= 0) @@ -1085,9 +1155,12 @@ public class StampedLock implements java node.thread = null; break; } + Thread wt = Thread.currentThread(); + U.putObject(wt, PARKBLOCKER, this); if (node.thread == null) // must recheck break; U.park(false, time); + U.putObject(wt, PARKBLOCKER, null); if (interruptible && Thread.interrupted()) return cancelWaiter(node, p, true); } @@ -1144,49 +1217,67 @@ public class StampedLock implements java if (deadline == 0L) time = 0L; else if ((time = deadline - System.nanoTime()) <= 0L) - return cancelWaiter(node, null, false); - node.thread = Thread.currentThread(); + return cancelWaiter(node, node, false); + Thread wt = Thread.currentThread(); + U.putObject(wt, PARKBLOCKER, this); + node.thread = wt; if (node.prev == p && p.status == WAITING && - (p != whead || (state & ABITS) != WBIT)) { + (p != whead || (state & ABITS) != WBIT)) U.park(false, time); - if (interruptible && Thread.interrupted()) - return cancelWaiter(node, null, true); - } node.thread = null; + U.putObject(wt, PARKBLOCKER, null); + if (interruptible && Thread.interrupted()) + return cancelWaiter(node, node, true); } } } /** - * If node non-null, forces cancel status and unsplices from queue - * if possible. This is a variant of cancellation methods in + * If node non-null, forces cancel status and unsplices it from + * queue if possible and wakes up any cowaiters (of the node, or + * group, as applicable), and in any case helps release current + * first waiter if lock is free. (Calling with null arguments + * serves as a conditional form of release, which is not currently + * needed but may be needed under possible future cancellation + * policies). This is a variant of cancellation methods in * AbstractQueuedSynchronizer (see its detailed explanation in AQS - * internal documentation) that more conservatively wakes up other - * threads that may have had their links changed, so as to preserve - * liveness in the main signalling methods. + * internal documentation). + * + * @param node if nonnull, the waiter + * @param group either node or the group node is cowaiting with + * @param interrupted if already interrupted + * @return INTERRUPTED if interrupted or Thread.interrupted, else zero */ private long cancelWaiter(WNode node, WNode group, boolean interrupted) { - if (node != null) { - node.thread = null; + if (node != null && group != null) { + Thread w; node.status = CANCELLED; - if (group != null) { - for (WNode p = group, q; p != null; p = q) { - if ((q = p.cowait) != null && q.status == CANCELLED) { - U.compareAndSwapObject(p, WCOWAIT, q, q.cowait); - break; + node.thread = null; + // unsplice cancelled nodes from group + for (WNode p = group, q; (q = p.cowait) != null;) { + if (q.status == CANCELLED) + U.compareAndSwapObject(p, WNEXT, q, q.next); + else + p = q; + } + if (group == node) { + WNode r; // detach and wake up uncancelled co-waiters + while ((r = node.cowait) != null) { + if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) && + (w = r.thread) != null) { + r.thread = null; + U.unpark(w); } } - } - else { - for (WNode pred = node.prev; pred != null; ) { - WNode succ, pp; Thread w; + for (WNode pred = node.prev; pred != null; ) { // unsplice + WNode succ, pp; // find valid successor while ((succ = node.next) == null || succ.status == CANCELLED) { - WNode q = null; + WNode q = null; // find successor the slow way for (WNode t = wtail; t != null && t != node; t = t.prev) if (t.status != CANCELLED) - q = t; - if (succ == q || + q = t; // don't link if succ cancelled + if (succ == q || // ensure accurate successor U.compareAndSwapObject(node, WNEXT, succ, succ = q)) { if (succ == null && node == wtail) @@ -1194,19 +1285,36 @@ public class StampedLock implements java break; } } - if (pred.next == node) + if (pred.next == node) // unsplice pred link U.compareAndSwapObject(pred, WNEXT, node, succ); - if (succ != null && (w = succ.thread) != null) - U.unpark(w); + if (succ != null && (w = succ.thread) != null) { + succ.thread = null; + U.unpark(w); // wake up succ to observe new pred + } if (pred.status != CANCELLED || (pp = pred.prev) == null) break; - node.prev = pp; // repeat for new pred + node.prev = pp; // repeat if new pred wrong/cancelled U.compareAndSwapObject(pp, WNEXT, pred, succ); pred = pp; } } } - release(whead); + WNode h; // Possibly release first waiter + while ((h = whead) != null) { + long s; WNode q; // similar to release() but check eligibility + if ((q = h.next) == null || q.status == CANCELLED) { + for (WNode t = wtail; t != null && t != h; t = t.prev) + if (t.status <= 0) + q = t; + } + if (h == whead) { + if (q != null && h.status == 0 && + ((s = state) & ABITS) != WBIT && // waiter is eligible + (s == 0L || q.mode == RMODE)) + release(h); + break; + } + } return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L; } @@ -1218,6 +1326,7 @@ public class StampedLock implements java private static final long WNEXT; private static final long WSTATUS; private static final long WCOWAIT; + private static final long PARKBLOCKER; static { try { @@ -1236,6 +1345,9 @@ public class StampedLock implements java (wk.getDeclaredField("next")); WCOWAIT = U.objectFieldOffset (wk.getDeclaredField("cowait")); + Class tk = Thread.class; + PARKBLOCKER = U.objectFieldOffset + (tk.getDeclaredField("parkBlocker")); } catch (Exception e) { throw new Error(e);