--- jsr166/src/jsr166e/StampedLock.java 2013/01/22 15:42:28 1.28 +++ jsr166/src/jsr166e/StampedLock.java 2013/01/24 21:35:03 1.31 @@ -8,7 +8,10 @@ package jsr166e; import java.util.concurrent.ThreadLocalRandom; import java.util.concurrent.TimeUnit; -import java.util.concurrent.locks.*; +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 @@ -198,13 +201,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 +232,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 @@ -249,7 +252,6 @@ 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 */ @@ -329,7 +331,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)); @@ -364,7 +366,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 +403,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)); @@ -443,7 +445,7 @@ public class StampedLock implements java long next, deadline; long nanos = unit.toNanos(time); if (!Thread.interrupted()) { - if ((next = tryReadLock()) != 0) + if ((next = tryReadLock()) != 0L) return next; if (nanos <= 0L) return 0L; @@ -524,25 +526,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(); } /** @@ -825,8 +823,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 +839,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 +850,35 @@ 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; + } + } + // internals /** @@ -977,11 +1003,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) @@ -1006,12 +1033,11 @@ public class StampedLock implements java return cancelWaiter(node, null, 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, null, true); } } } @@ -1033,11 +1059,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 +1075,8 @@ public class StampedLock implements java } return ns; } + if (m >= WBIT) + break; } if (spins > 0) { if (ThreadLocalRandom.current().nextInt() >= 0) @@ -1074,6 +1100,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) @@ -1088,8 +1116,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; } @@ -1147,101 +1173,15 @@ public class StampedLock implements java return cancelWaiter(node, null, 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, null, true); } } } - /** - * If node non-null, forces cancel status and unsplices from queue - * if possible. 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. - */ - private long cancelWaiter(WNode node, WNode group, boolean interrupted) { - if (node != null) { - node.thread = null; - 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; - } - } - } - else { - for (WNode pred = node.prev; pred != null; ) { - WNode succ, pp; Thread w; - while ((succ = node.next) == null || - succ.status == CANCELLED) { - WNode q = null; - for (WNode t = wtail; t != null && t != node; t = t.prev) - if (t.status != CANCELLED) - q = t; - if (succ == q || - U.compareAndSwapObject(node, WNEXT, - succ, succ = q)) { - if (succ == null && node == wtail) - U.compareAndSwapObject(this, WTAIL, node, pred); - break; - } - } - if (pred.next == node) - U.compareAndSwapObject(pred, WNEXT, node, succ); - if (succ != null && (w = succ.thread) != null) - U.unpark(w); - if (pred.status != CANCELLED || (pp = pred.prev) == null) - break; - node.prev = pp; // repeat for new pred - U.compareAndSwapObject(pp, WNEXT, pred, succ); - pred = pp; - } - } - } - release(whead); - return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L; - } - - // Unsafe mechanics - private static final sun.misc.Unsafe U; - private static final long STATE; - private static final long WHEAD; - private static final long WTAIL; - private static final long WNEXT; - private static final long WSTATUS; - private static final long WCOWAIT; - - static { - try { - U = getUnsafe(); - Class k = StampedLock.class; - Class wk = WNode.class; - STATE = U.objectFieldOffset - (k.getDeclaredField("state")); - WHEAD = U.objectFieldOffset - (k.getDeclaredField("whead")); - WTAIL = U.objectFieldOffset - (k.getDeclaredField("wtail")); - WSTATUS = U.objectFieldOffset - (wk.getDeclaredField("status")); - WNEXT = U.objectFieldOffset - (wk.getDeclaredField("next")); - WCOWAIT = U.objectFieldOffset - (wk.getDeclaredField("cowait")); - - } catch (Exception e) { - throw new Error(e); - } - } - /** * Returns a sun.misc.Unsafe. Suitable for use in a 3rd party package. * Replace with a simple call to Unsafe.getUnsafe when integrating