jdk-sandbox: comparison jdk/src/share/classes/java/util/concurrent/locks/StampedLock.java

equal deleted inserted replaced

-:5f7c7cdd74e9
+:459db4bb1df0
 * Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
 * particular, we use the phase-fair anti-barging rule: If an
 * incoming reader arrives while read lock is held but there is a
 * queued writer, this incoming reader is queued.  (This rule is
 * responsible for some of the complexity of method acquireRead,
-* but without it, the lock becomes highly unfair.)
+* but without it, the lock becomes highly unfair.) Method release
+* does not (and sometimes cannot) itself wake up cowaiters. This
+* is done by the primary thread, but helped by any other threads
+* with nothing better to do in methods acquireRead and
+* acquireWrite.
 *
 * These rules apply to threads actually queued. All tryLock forms
 * opportunistically try to acquire locks regardless of preference
 * rules, and so may "barge" their way in.  Randomized spinning is
 * used in the acquire methods to reduce (increasingly expensive)
 private static final long serialVersionUID = -6001602636862214147L;
 /** Number of processors, for spin control */
 private static final int NCPU = Runtime.getRuntime().availableProcessors();
-/** Maximum number of retries before blocking on acquisition */
+/** Maximum number of retries before enqueuing on acquisition */
 private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;
+/** Maximum number of retries before blocking at head on acquisition */
+private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;
 /** Maximum number of retries before re-blocking */
-private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 0;
+private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0;
 /** The period for yielding when waiting for overflow spinlock */
 private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
 /** The number of bits to use for reader count before overflowing */
 * until available.
 *
 * @return a stamp that can be used to unlock or convert mode
 */
 public long readLock() {
-long s, next;  // bypass acquireRead on fully unlocked case only
+long s = state, next;  // bypass acquireRead on common uncontended case
-return ((((s = state) & ABITS) == 0L &&
+return ((whead == wtail && (s & ABITS) < RFULL &&
 U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
 next : acquireRead(false, 0L));
 }
 /**
 if ((q = h.next) == null || q.status == CANCELLED) {
 for (WNode t = wtail; t != null && t != h; t = t.prev)
 if (t.status <= 0)
 q = t;
 }
-if (q != null) {
+if (q != null && (w = q.thread) != null)
-for (WNode r = q;;) {  // release co-waiters too
+U.unpark(w);
-if ((w = r.thread) != null) {
-r.thread = null;
-U.unpark(w);
-}
-if ((r = q.cowait) == null)
-break;
-U.compareAndSwapObject(q, WCOWAIT, r, r.cowait);
-}
-}
 }
 }
 /**
 * See above for explanation.
 * @return next state, or INTERRUPTED
 */
 private long acquireWrite(boolean interruptible, long deadline) {
 WNode node = null, p;
 for (int spins = -1;;) { // spin while enqueuing
-long s, ns;
+long m, s, ns;
-if (((s = state) & ABITS) == 0L) {
+if ((m = (s = state) & ABITS) == 0L) {
 if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
 return ns;
 }
+else if (spins < 0)
+spins = (m == WBIT && wtail == whead) ? SPINS : 0;
 else if (spins > 0) {
 if (LockSupport.nextSecondarySeed() >= 0)
 --spins;
 }
 else if ((p = wtail) == null) { // initialize queue
-WNode h = new WNode(WMODE, null);
+WNode hd = new WNode(WMODE, null);
-if (U.compareAndSwapObject(this, WHEAD, null, h))
+if (U.compareAndSwapObject(this, WHEAD, null, hd))
-wtail = h;
+wtail = hd;
 }
-else if (spins < 0)
-spins = (p == whead) ? SPINS : 0;
 else if (node == null)
 node = new WNode(WMODE, p);
 else if (node.prev != p)
 node.prev = p;
 else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
 p.next = node;
 break;
 }
 }
-for (int spins = SPINS;;) {
+for (int spins = -1;;) {
-WNode np, pp; int ps; long s, ns; Thread w;
+WNode h, np, pp; int ps;
-while ((np = node.prev) != p && np != null)
+if ((h = whead) == p) {
-(p = np).next = node;   // stale
+if (spins < 0)
-if (whead == p) {
+spins = HEAD_SPINS;
+else if (spins < MAX_HEAD_SPINS)
+spins <<= 1;
 for (int k = spins;;) { // spin at head
+long s, ns;
 if (((s = state) & ABITS) == 0L) {
-if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
+if (U.compareAndSwapLong(this, STATE, s,
+ns = s + WBIT)) {
 whead = node;
 node.prev = null;
 return ns;
 }
 }
 else if (LockSupport.nextSecondarySeed() >= 0 &&
 --k <= 0)
 break;
 }
-if (spins < MAX_HEAD_SPINS)
+}
-spins <<= 1;
+else if (h != null) { // help release stale waiters
-}
+WNode c; Thread w;
-if ((ps = p.status) == 0)
+while ((c = h.cowait) != null) {
-U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
+if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
-else if (ps == CANCELLED) {
+(w = c.thread) != null)
-if ((pp = p.prev) != null) {
+U.unpark(w);
-node.prev = pp;
+}
-pp.next = node;
+}
-}
+if (whead == h) {
-}
+if ((np = node.prev) != p) {
-else {
+if (np != null)
-long time; // 0 argument to park means no timeout
+(p = np).next = node;   // stale
-if (deadline == 0L)
+}
-time = 0L;
+else if ((ps = p.status) == 0)
-else if ((time = deadline - System.nanoTime()) <= 0L)
+U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
-return cancelWaiter(node, node, false);
+else if (ps == CANCELLED) {
-Thread wt = Thread.currentThread();
+if ((pp = p.prev) != null) {
-U.putObject(wt, PARKBLOCKER, this); // emulate LockSupport.park
+node.prev = pp;
-node.thread = wt;
+pp.next = node;
-if (node.prev == p && p.status == WAITING && // recheck
+}
-(p != whead || (state & ABITS) != 0L))
+}
-U.park(false, time);
+else {
-node.thread = null;
+long time; // 0 argument to park means no timeout
-U.putObject(wt, PARKBLOCKER, null);
+if (deadline == 0L)
-if (interruptible && Thread.interrupted())
+time = 0L;
-return cancelWaiter(node, node, true);
+else if ((time = deadline - System.nanoTime()) <= 0L)
+return cancelWaiter(node, node, false);
+Thread wt = Thread.currentThread();
+U.putObject(wt, PARKBLOCKER, this);
+node.thread = wt;
+if (p.status < 0 && (p != h || (state & ABITS) != 0L) &&
+whead == h && node.prev == p)
+U.park(false, time);  // emulate LockSupport.park
+node.thread = null;
+U.putObject(wt, PARKBLOCKER, null);
+if (interruptible && Thread.interrupted())
+return cancelWaiter(node, node, true);
+}
 }
 }
 }
 /**
 * @param deadline if nonzero, the System.nanoTime value to timeout
 * at (and return zero)
 * @return next state, or INTERRUPTED
 */
 private long acquireRead(boolean interruptible, long deadline) {
-WNode node = null, group = null, p;
+WNode node = null, p;
 for (int spins = -1;;) {
-for (;;) {
+WNode h;
-long s, m, ns; WNode h, q; Thread w; // anti-barging guard
+if ((h = whead) == (p = wtail)) {
-if (group == null && (h = whead) != null &&
+for (long m, s, ns;;) {
-(q = h.next) != null && q.mode != RMODE)
+if ((m = (s = state) & ABITS) < RFULL ?
-break;
+U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
-if ((m = (s = state) & ABITS) < RFULL ?
+(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L))
-U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
+return ns;
-(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
+else if (m >= WBIT) {
-if (group != null) {  // help release others
+if (spins > 0) {
-for (WNode r = group;;) {
+if (LockSupport.nextSecondarySeed() >= 0)
-if ((w = r.thread) != null) {
+--spins;
-r.thread = null;
+}
-U.unpark(w);
+else {
+if (spins == 0) {
+WNode nh = whead, np = wtail;
+if ((nh == h && np == p) || (h = nh) != (p = np))
+break;
 }
-if ((r = group.cowait) == null)
+spins = SPINS;
-break;
-U.compareAndSwapObject(group, WCOWAIT, r, r.cowait);
 }
 }
-return ns;
+}
 }
-if (m >= WBIT)
+if (p == null) { // initialize queue
+WNode hd = new WNode(WMODE, null);
+if (U.compareAndSwapObject(this, WHEAD, null, hd))
+wtail = hd;
+}
+else if (node == null)
+node = new WNode(RMODE, p);
+else if (h == p || p.mode != RMODE) {
+if (node.prev != p)
+node.prev = p;
+else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
+p.next = node;
 break;
 }
-if (spins > 0) {
+}
-if (LockSupport.nextSecondarySeed() >= 0)
+else if (!U.compareAndSwapObject(p, WCOWAIT,
---spins;
+node.cowait = p.cowait, node))
-}
+node.cowait = null;
-else if ((p = wtail) == null) {
+else {
-WNode h = new WNode(WMODE, null);
+for (;;) {
-if (U.compareAndSwapObject(this, WHEAD, null, h))
+WNode pp, c; Thread w;
-wtail = h;
+if ((h = whead) != null && (c = h.cowait) != null &&
-}
+U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
-else if (spins < 0)
+(w = c.thread) != null) // help release
-spins = (p == whead) ? SPINS : 0;
+U.unpark(w);
-else if (node == null)
+if (h == (pp = p.prev) || h == p || pp == null) {
-node = new WNode(WMODE, p);
+long m, s, ns;
-else if (node.prev != p)
+do {
-node.prev = p;
+if ((m = (s = state) & ABITS) < RFULL ?
-else if (p.mode == RMODE && p != whead) {
+U.compareAndSwapLong(this, STATE, s,
-WNode pp = p.prev;  // become co-waiter with group p
+ns = s + RUNIT) :
-if (pp != null && p == wtail &&
+(m < WBIT &&
-U.compareAndSwapObject(p, WCOWAIT,
+(ns = tryIncReaderOverflow(s)) != 0L))
-node.cowait = p.cowait, node)) {
+return ns;
-node.thread = Thread.currentThread();
+} while (m < WBIT);
-for (long time;;) {
+}
+if (whead == h && p.prev == pp) {
+long time;
+if (pp == null || h == p || p.status > 0) {
+node = null; // throw away
+break;
+}
 if (deadline == 0L)
 time = 0L;
 else if ((time = deadline - System.nanoTime()) <= 0L)
 return cancelWaiter(node, p, false);
-if (node.thread == null)
-break;
-if (p.prev != pp || p.status == CANCELLED ||
-p == whead || p.prev != pp) {
-node.thread = null;
-break;
-}
 Thread wt = Thread.currentThread();
 U.putObject(wt, PARKBLOCKER, this);
-if (node.thread == null) // must recheck
+node.thread = wt;
-break;
+if ((h != pp || (state & ABITS) == WBIT) &&
-U.park(false, time);
+whead == h && p.prev == pp)
+U.park(false, time);
+node.thread = null;
 U.putObject(wt, PARKBLOCKER, null);
 if (interruptible && Thread.interrupted())
 return cancelWaiter(node, p, true);
 }
-group = p;
+}
 }
-node = null; // throw away
+}
-}
-else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
+for (int spins = -1;;) {
-p.next = node;
+WNode h, np, pp; int ps;
-break;
+if ((h = whead) == p) {
-}
+if (spins < 0)
-}
+spins = HEAD_SPINS;
+else if (spins < MAX_HEAD_SPINS)
-for (int spins = SPINS;;) {
+spins <<= 1;
-WNode np, pp, r; int ps; long m, s, ns; Thread w;
+for (int k = spins;;) { // spin at head
-while ((np = node.prev) != p && np != null)
+long m, s, ns;
-(p = np).next = node;
+if ((m = (s = state) & ABITS) < RFULL ?
-if (whead == p) {
+U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
-for (int k = spins;;) {
+(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
-if ((m = (s = state) & ABITS) != WBIT) {
+WNode c; Thread w;
-if (m < RFULL ?
+whead = node;
-U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT):
+node.prev = null;
-(ns = tryIncReaderOverflow(s)) != 0L) {
+while ((c = node.cowait) != null) {
-whead = node;
+if (U.compareAndSwapObject(node, WCOWAIT,
-node.prev = null;
+c, c.cowait) &&
-while ((r = node.cowait) != null) {
+(w = c.thread) != null)
-if (U.compareAndSwapObject(node, WCOWAIT,
+U.unpark(w);
-r, r.cowait) &&
-(w = r.thread) != null) {
-r.thread = null;
-U.unpark(w); // release co-waiter
-}
-}
-return ns;
 }
+return ns;
 }
-else if (LockSupport.nextSecondarySeed() >= 0 &&
+else if (m >= WBIT &&
---k <= 0)
+LockSupport.nextSecondarySeed() >= 0 && --k <= 0)
 break;
 }
-if (spins < MAX_HEAD_SPINS)
+}
-spins <<= 1;
+else if (h != null) {
-}
+WNode c; Thread w;
-if ((ps = p.status) == 0)
+while ((c = h.cowait) != null) {
-U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
+if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
-else if (ps == CANCELLED) {
+(w = c.thread) != null)
-if ((pp = p.prev) != null) {
+U.unpark(w);
-node.prev = pp;
+}
-pp.next = node;
+}
-}
+if (whead == h) {
-}
+if ((np = node.prev) != p) {
-else {
+if (np != null)
-long time;
+(p = np).next = node;   // stale
-if (deadline == 0L)
+}
-time = 0L;
+else if ((ps = p.status) == 0)
-else if ((time = deadline - System.nanoTime()) <= 0L)
+U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
-return cancelWaiter(node, node, false);
+else if (ps == CANCELLED) {
-Thread wt = Thread.currentThread();
+if ((pp = p.prev) != null) {
-U.putObject(wt, PARKBLOCKER, this);
+node.prev = pp;
-node.thread = wt;
+pp.next = node;
-if (node.prev == p && p.status == WAITING &&
+}
-(p != whead || (state & ABITS) != WBIT))
+}
-U.park(false, time);
+else {
-node.thread = null;
+long time;
-U.putObject(wt, PARKBLOCKER, null);
+if (deadline == 0L)
-if (interruptible && Thread.interrupted())
+time = 0L;
-return cancelWaiter(node, node, true);
+else if ((time = deadline - System.nanoTime()) <= 0L)
+return cancelWaiter(node, node, false);
+Thread wt = Thread.currentThread();
+U.putObject(wt, PARKBLOCKER, this);
+node.thread = wt;
+if (p.status < 0 &&
+(p != h || (state & ABITS) == WBIT) &&
+whead == h && node.prev == p)
+U.park(false, time);
+node.thread = null;
+U.putObject(wt, PARKBLOCKER, null);
+if (interruptible && Thread.interrupted())
+return cancelWaiter(node, node, true);
+}
 }
 }
 }
 /**
 */
 private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
 if (node != null && group != null) {
 Thread w;
 node.status = CANCELLED;
-node.thread = null;
 // unsplice cancelled nodes from group
 for (WNode p = group, q; (q = p.cowait) != null;) {
-if (q.status == CANCELLED)
+if (q.status == CANCELLED) {
-U.compareAndSwapObject(p, WNEXT, q, q.next);
+U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
+p = group; // restart
+}
 else
 p = q;
 }
 if (group == node) {
-WNode r; // detach and wake up uncancelled co-waiters
+for (WNode r = group.cowait; r != null; r = r.cowait) {
-while ((r = node.cowait) != null) {
+if ((w = r.thread) != null)
-if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
+U.unpark(w);       // wake up uncancelled co-waiters
-(w = r.thread) != null) {
-r.thread = null;
-U.unpark(w);
-}
 }
 for (WNode pred = node.prev; pred != null; ) { // unsplice
 WNode succ, pp;        // find valid successor
 while ((succ = node.next) == null ||
 succ.status == CANCELLED) {

changeset 19589	459db4bb1df0
parent 18576	7a5c231327af