--- jsr166/src/jsr166e/StampedLock.java 2013/01/23 17:29:18 1.29 +++ jsr166/src/jsr166e/StampedLock.java 2013/01/26 15:00:15 1.33 @@ -40,19 +40,20 @@ import java.util.concurrent.locks.LockSu *
  • 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. * * * @@ -232,7 +233,7 @@ 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 + * sprawl out because actions and retries rely on consistent sets * of locally cached reads. * * As noted in Boehm's paper (above), sequence validation (mainly @@ -252,6 +253,7 @@ public class StampedLock implements java * motivation to further spread out contended locations, but might * be subject to future improvements. */ + private static final long serialVersionUID = -6001602636862214147L; /** Number of processors, for spin control */ @@ -331,7 +333,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)); @@ -403,7 +405,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)); @@ -442,11 +444,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()) != 0L) - 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) @@ -490,7 +498,9 @@ 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 * since issuance of the given stamp; else false @@ -1030,15 +1040,14 @@ public class StampedLock implements java if (deadline == 0L) time = 0L; else if ((time = deadline - System.nanoTime()) <= 0L) - return cancelWaiter(node, null, false); + return cancelWaiter(node, node, false); node.thread = Thread.currentThread(); 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; + if (interruptible && Thread.interrupted()) + return cancelWaiter(node, node, true); } } } @@ -1101,6 +1110,8 @@ public class StampedLock implements java node.cowait = p.cowait, node)) { node.thread = Thread.currentThread(); for (long time;;) { + if (interruptible && Thread.interrupted()) + return cancelWaiter(node, p, true); if (deadline == 0L) time = 0L; else if ((time = deadline - System.nanoTime()) <= 0L) @@ -1115,8 +1126,6 @@ public class StampedLock implements java if (node.thread == null) // must recheck break; U.park(false, time); - if (interruptible && Thread.interrupted()) - return cancelWaiter(node, p, true); } group = p; } @@ -1171,49 +1180,64 @@ public class StampedLock implements java if (deadline == 0L) time = 0L; else if ((time = deadline - System.nanoTime()) <= 0L) - return cancelWaiter(node, null, false); + return cancelWaiter(node, node, false); node.thread = Thread.currentThread(); 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; + 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) @@ -1221,19 +1245,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; }