ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/jsr166e/StampedLock.java

Comparing jsr166/src/jsr166e/StampedLock.java (file contents):
Revision 1.28 by dl, Tue Jan 22 15:42:28 2013 UTC vs.
Revision 1.31 by dl, Thu Jan 24 21:35:03 2013 UTC

#	Line 8 | Line 8 | package jsr166e;
8
9		import java.util.concurrent.ThreadLocalRandom;
10		import java.util.concurrent.TimeUnit;
11	<	import java.util.concurrent.locks.*;
11	>	import java.util.concurrent.locks.Lock;
12	>	import java.util.concurrent.locks.Condition;
13	>	import java.util.concurrent.locks.ReadWriteLock;
14	>	import java.util.concurrent.locks.LockSupport;
15
16		/**
17		* A capability-based lock with three modes for controlling read/write
#	Line 198 | Line 201 | public class StampedLock implements java
201		*
202		* Waiters use a modified form of CLH lock used in
203		* AbstractQueuedSynchronizer (see its internal documentation for
204	<	* a fuller account), where each node it tagged (field mode) as
204	>	* a fuller account), where each node is tagged (field mode) as
205		* either a reader or writer. Sets of waiting readers are grouped
206		* (linked) under a common node (field cowait) so act as a single
207	<	* node with respect to most CLH mechanics.  By virtue of its
208	<	* structure, wait nodes need not actually carry sequence numbers;
209	<	* we know each is >= its predecessor.  These queue mechanics
210	<	* simplify the scheduling policy to a mainly-FIFO scheme that
207	>	* node with respect to most CLH mechanics.  By virtue of the
208	>	* queue structure, wait nodes need not actually carry sequence
209	>	* numbers; we know each is greater than its predecessor.  This
210	>	* simplifies the scheduling policy to a mainly-FIFO scheme that
211		* incorporates elements of Phase-Fair locks (see Brandenburg &
212		* Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
213		* particular, we use the phase-fair anti-barging rule: If an
#	Line 229 | Line 232 | public class StampedLock implements java
232		*
233		* Nearly all of these mechanics are carried out in methods
234		* acquireWrite and acquireRead, that, as typical of such code,
235	<	* sprawl out because actions and retries rely on consitent sets
236	<	* of locally cahced reads.
235	>	* sprawl out because actions and retries rely on consistent sets
236	>	* of locally cached reads.
237		*
238		* As noted in Boehm's paper (above), sequence validation (mainly
239		* method validate()) requires stricter ordering rules than apply
#	Line 249 | Line 252 | public class StampedLock implements java
252		* motivation to further spread out contended locations, but might
253		* be subject to future improvements.
254		*/
252	–
255		private static final long serialVersionUID = -6001602636862214147L;
256
257		/** Number of processors, for spin control */
#	Line 329 | Line 331 | public class StampedLock implements java
331		* @return a stamp that can be used to unlock or convert mode
332		*/
333		public long writeLock() {
334	<	long s, next;  // bypass acquireWrite in fully onlocked case only
334	>	long s, next;  // bypass acquireWrite in fully unlocked case only
335		return ((((s = state) & ABITS) == 0L &&
336		U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
337		next : acquireWrite(false, 0L));
#	Line 364 | Line 366 | public class StampedLock implements java
366		long nanos = unit.toNanos(time);
367		if (!Thread.interrupted()) {
368		long next, deadline;
369	<	if ((next = tryWriteLock()) != 0)
369	>	if ((next = tryWriteLock()) != 0L)
370		return next;
371		if (nanos <= 0L)
372		return 0L;
#	Line 401 | Line 403 | public class StampedLock implements java
403		* @return a stamp that can be used to unlock or convert mode
404		*/
405		public long readLock() {
406	<	long s, next;  // bypass acquireRead on fully onlocked case only
406	>	long s, next;  // bypass acquireRead on fully unlocked case only
407		return ((((s = state) & ABITS) == 0L &&
408		U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
409		next : acquireRead(false, 0L));
#	Line 443 | Line 445 | public class StampedLock implements java
445		long next, deadline;
446		long nanos = unit.toNanos(time);
447		if (!Thread.interrupted()) {
448	<	if ((next = tryReadLock()) != 0)
448	>	if ((next = tryReadLock()) != 0L)
449		return next;
450		if (nanos <= 0L)
451		return 0L;
#	Line 524 | Line 526 | public class StampedLock implements java
526		* not match the current state of this lock
527		*/
528		public void unlockRead(long stamp) {
529	<	long s, m;  WNode h;
530	<	if ((stamp & RBITS) != 0L) {
531	<	while (((s = state) & SBITS) == (stamp & SBITS)) {
532	<	if ((m = s & ABITS) == 0L)
529	>	long s, m; WNode h;
530	>	for (;;) {
531	>	if (((s = state) & SBITS) != (stamp & SBITS) ||
532	>	(stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
533	>	throw new IllegalMonitorStateException();
534	>	if (m < RFULL) {
535	>	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
536	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
537	>	release(h);
538		break;
532	–	else if (m < RFULL) {
533	–	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
534	–	if (m == RUNIT && (h = whead) != null && h.status != 0)
535	–	release(h);
536	–	return;
537	–	}
539		}
539	–	else if (m >= WBIT)
540	–	break;
541	–	else if (tryDecReaderOverflow(s) != 0L)
542	–	return;
540		}
541	+	else if (tryDecReaderOverflow(s) != 0L)
542	+	break;
543		}
545	–	throw new IllegalMonitorStateException();
544		}
545
546		/**
#	Line 825 | Line 823 | public class StampedLock implements java
823		throws InterruptedException {
824		return tryReadLock(time, unit) != 0L;
825		}
826	<	// note that we give up ability to check mode so just use current state
829	<	public void unlock() { unlockRead(state); }
826	>	public void unlock() { unstampedUnlockRead(); }
827		public Condition newCondition() {
828		throw new UnsupportedOperationException();
829		}
#	Line 842 | Line 839 | public class StampedLock implements java
839		throws InterruptedException {
840		return tryWriteLock(time, unit) != 0L;
841		}
842	<	public void unlock() { unlockWrite(state); }
842	>	public void unlock() { unstampedUnlockWrite(); }
843		public Condition newCondition() {
844		throw new UnsupportedOperationException();
845		}
#	Line 853 | Line 850 | public class StampedLock implements java
850		public Lock writeLock() { return asWriteLock(); }
851		}
852
853	+	// Unlock methods without stamp argument checks for view classes.
854	+	// Needed because view-class lock methods throw away stamps.
855	+
856	+	final void unstampedUnlockWrite() {
857	+	WNode h; long s;
858	+	if (((s = state) & WBIT) == 0L)
859	+	throw new IllegalMonitorStateException();
860	+	state = (s += WBIT) == 0L ? ORIGIN : s;
861	+	if ((h = whead) != null && h.status != 0)
862	+	release(h);
863	+	}
864	+
865	+	final void unstampedUnlockRead() {
866	+	for (;;) {
867	+	long s, m; WNode h;
868	+	if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
869	+	throw new IllegalMonitorStateException();
870	+	else if (m < RFULL) {
871	+	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
872	+	if (m == RUNIT && (h = whead) != null && h.status != 0)
873	+	release(h);
874	+	break;
875	+	}
876	+	}
877	+	else if (tryDecReaderOverflow(s) != 0L)
878	+	break;
879	+	}
880	+	}
881	+
882		// internals
883
884		/**
#	Line 977 | Line 1003 | public class StampedLock implements java
1003		(p = np).next = node;   // stale
1004		if (whead == p) {
1005		for (int k = spins;;) { // spin at head
1006	<	if (((s = state) & ABITS) == 0L &&
1007	<	U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) {
1008	<	whead = node;
1009	<	node.prev = null;
1010	<	return ns;
1006	>	if (((s = state) & ABITS) == 0L) {
1007	>	if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1008	>	whead = node;
1009	>	node.prev = null;
1010	>	return ns;
1011	>	}
1012		}
1013		else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1014		--k <= 0)
#	Line 1006 | Line 1033 | public class StampedLock implements java
1033		return cancelWaiter(node, null, false);
1034		node.thread = Thread.currentThread();
1035		if (node.prev == p && p.status == WAITING && // recheck
1036	<	(p != whead || (state & ABITS) != 0L)) {
1036	>	(p != whead || (state & ABITS) != 0L))
1037		U.park(false, time);
1011	–	if (interruptible && Thread.interrupted())
1012	–	return cancelWaiter(node, null, true);
1013	–	}
1038		node.thread = null;
1039	+	if (interruptible && Thread.interrupted())
1040	+	return cancelWaiter(node, null, true);
1041		}
1042		}
1043		}
#	Line 1033 | Line 1059 | public class StampedLock implements java
1059		if (group == null && (h = whead) != null &&
1060		(q = h.next) != null && q.mode != RMODE)
1061		break;
1062	<	if ((m = (s = state) & ABITS) == WBIT)
1037	<	break;
1038	<	if (m < RFULL ?
1062	>	if ((m = (s = state) & ABITS) < RFULL ?
1063		U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1064	<	(ns = tryIncReaderOverflow(s)) != 0L) {
1064	>	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1065		if (group != null) {  // help release others
1066		for (WNode r = group;;) {
1067		if ((w = r.thread) != null) {
#	Line 1051 | Line 1075 | public class StampedLock implements java
1075		}
1076		return ns;
1077		}
1078	+	if (m >= WBIT)
1079	+	break;
1080		}
1081		if (spins > 0) {
1082		if (ThreadLocalRandom.current().nextInt() >= 0)
#	Line 1074 | Line 1100 | public class StampedLock implements java
1100		node.cowait = p.cowait, node)) {
1101		node.thread = Thread.currentThread();
1102		for (long time;;) {
1103	+	if (interruptible && Thread.interrupted())
1104	+	return cancelWaiter(node, p, true);
1105		if (deadline == 0L)
1106		time = 0L;
1107		else if ((time = deadline - System.nanoTime()) <= 0L)
#	Line 1088 | Line 1116 | public class StampedLock implements java
1116		if (node.thread == null) // must recheck
1117		break;
1118		U.park(false, time);
1091	–	if (interruptible && Thread.interrupted())
1092	–	return cancelWaiter(node, p, true);
1119		}
1120		group = p;
1121		}
#	Line 1147 | Line 1173 | public class StampedLock implements java
1173		return cancelWaiter(node, null, false);
1174		node.thread = Thread.currentThread();
1175		if (node.prev == p && p.status == WAITING &&
1176	<	(p != whead || (state & ABITS) != WBIT)) {
1176	>	(p != whead || (state & ABITS) != WBIT))
1177		U.park(false, time);
1152	–	if (interruptible && Thread.interrupted())
1153	–	return cancelWaiter(node, null, true);
1154	–	}
1178		node.thread = null;
1179	+	if (interruptible && Thread.interrupted())
1180	+	return cancelWaiter(node, null, true);
1181		}
1182		}
1183		}
1184
1160	–	/**
1161	–	* If node non-null, forces cancel status and unsplices from queue
1162	–	* if possible. This is a variant of cancellation methods in
1163	–	* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1164	–	* internal documentation) that more conservatively wakes up other
1165	–	* threads that may have had their links changed, so as to preserve
1166	–	* liveness in the main signalling methods.
1167	–	*/
1168	–	private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1169	–	if (node != null) {
1170	–	node.thread = null;
1171	–	node.status = CANCELLED;
1172	–	if (group != null) {
1173	–	for (WNode p = group, q; p != null; p = q) {
1174	–	if ((q = p.cowait) != null && q.status == CANCELLED) {
1175	–	U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1176	–	break;
1177	–	}
1178	–	}
1179	–	}
1180	–	else {
1181	–	for (WNode pred = node.prev; pred != null; ) {
1182	–	WNode succ, pp; Thread w;
1183	–	while ((succ = node.next) == null ||
1184	–	succ.status == CANCELLED) {
1185	–	WNode q = null;
1186	–	for (WNode t = wtail; t != null && t != node; t = t.prev)
1187	–	if (t.status != CANCELLED)
1188	–	q = t;
1189	–	if (succ == q ||
1190	–	U.compareAndSwapObject(node, WNEXT,
1191	–	succ, succ = q)) {
1192	–	if (succ == null && node == wtail)
1193	–	U.compareAndSwapObject(this, WTAIL, node, pred);
1194	–	break;
1195	–	}
1196	–	}
1197	–	if (pred.next == node)
1198	–	U.compareAndSwapObject(pred, WNEXT, node, succ);
1199	–	if (succ != null && (w = succ.thread) != null)
1200	–	U.unpark(w);
1201	–	if (pred.status != CANCELLED || (pp = pred.prev) == null)
1202	–	break;
1203	–	node.prev = pp; // repeat for new pred
1204	–	U.compareAndSwapObject(pp, WNEXT, pred, succ);
1205	–	pred = pp;
1206	–	}
1207	–	}
1208	–	}
1209	–	release(whead);
1210	–	return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1211	–	}
1212	–
1213	–	// Unsafe mechanics
1214	–	private static final sun.misc.Unsafe U;
1215	–	private static final long STATE;
1216	–	private static final long WHEAD;
1217	–	private static final long WTAIL;
1218	–	private static final long WNEXT;
1219	–	private static final long WSTATUS;
1220	–	private static final long WCOWAIT;
1221	–
1222	–	static {
1223	–	try {
1224	–	U = getUnsafe();
1225	–	Class<?> k = StampedLock.class;
1226	–	Class<?> wk = WNode.class;
1227	–	STATE = U.objectFieldOffset
1228	–	(k.getDeclaredField("state"));
1229	–	WHEAD = U.objectFieldOffset
1230	–	(k.getDeclaredField("whead"));
1231	–	WTAIL = U.objectFieldOffset
1232	–	(k.getDeclaredField("wtail"));
1233	–	WSTATUS = U.objectFieldOffset
1234	–	(wk.getDeclaredField("status"));
1235	–	WNEXT = U.objectFieldOffset
1236	–	(wk.getDeclaredField("next"));
1237	–	WCOWAIT = U.objectFieldOffset
1238	–	(wk.getDeclaredField("cowait"));
1239	–
1240	–	} catch (Exception e) {
1241	–	throw new Error(e);
1242	–	}
1243	–	}
1244	–
1185		/**
1186		* Returns a sun.misc.Unsafe.  Suitable for use in a 3rd party package.
1187		* Replace with a simple call to Unsafe.getUnsafe when integrating

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines