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.35 by jsr166, Mon Jan 28 22:22:08 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 37 | Line 40 | import java.util.concurrent.locks.*;
40		*  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
41		*   returns a non-zero stamp only if the lock is not currently held
42		*   in write mode. Method {@link #validate} returns true if the lock
43	<	*   has not since been acquired in write mode. This mode can be
44	<	*   thought of as an extremely weak version of a read-lock, that can
45	<	*   be broken by a writer at any time.  The use of optimistic mode
46	<	*   for short read-only code segments often reduces contention and
47	<	*   improves throughput.  However, its use is inherently fragile.
48	<	*   Optimistic read sections should only read fields and hold them in
49	<	*   local variables for later use after validation. Fields read while
50	<	*   in optimistic mode may be wildly inconsistent, so usage applies
51	<	*   only when you are familiar enough with data representations to
52	<	*   check consistency and/or repeatedly invoke method {@code
53	<	*   validate()}.  For example, such steps are typically required when
54	<	*   first reading an object or array reference, and then accessing
55	<	*   one of its fields, elements or methods. </li>
43	>	*   has not been acquired in write mode since obtaining a given
44	>	*   stamp.  This mode can be thought of as an extremely weak version
45	>	*   of a read-lock, that can be broken by a writer at any time.  The
46	>	*   use of optimistic mode for short read-only code segments often
47	>	*   reduces contention and improves throughput.  However, its use is
48	>	*   inherently fragile.  Optimistic read sections should only read
49	>	*   fields and hold them in local variables for later use after
50	>	*   validation. Fields read while in optimistic mode may be wildly
51	>	*   inconsistent, so usage applies only when you are familiar enough
52	>	*   with data representations to check consistency and/or repeatedly
53	>	*   invoke method {@code validate()}.  For example, such steps are
54	>	*   typically required when first reading an object or array
55	>	*   reference, and then accessing one of its fields, elements or
56	>	*   methods. </li>
57		*
58		* </ul>
59		*
#	Line 198 | Line 202 | public class StampedLock implements java
202		*
203		* Waiters use a modified form of CLH lock used in
204		* AbstractQueuedSynchronizer (see its internal documentation for
205	<	* a fuller account), where each node it tagged (field mode) as
205	>	* a fuller account), where each node is tagged (field mode) as
206		* either a reader or writer. Sets of waiting readers are grouped
207		* (linked) under a common node (field cowait) so act as a single
208	<	* node with respect to most CLH mechanics.  By virtue of its
209	<	* structure, wait nodes need not actually carry sequence numbers;
210	<	* we know each is >= its predecessor.  These queue mechanics
211	<	* simplify the scheduling policy to a mainly-FIFO scheme that
208	>	* node with respect to most CLH mechanics.  By virtue of the
209	>	* queue structure, wait nodes need not actually carry sequence
210	>	* numbers; we know each is greater than its predecessor.  This
211	>	* simplifies the scheduling policy to a mainly-FIFO scheme that
212		* incorporates elements of Phase-Fair locks (see Brandenburg &
213		* Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
214		* particular, we use the phase-fair anti-barging rule: If an
#	Line 229 | Line 233 | public class StampedLock implements java
233		*
234		* Nearly all of these mechanics are carried out in methods
235		* acquireWrite and acquireRead, that, as typical of such code,
236	<	* sprawl out because actions and retries rely on consitent sets
237	<	* of locally cahced reads.
236	>	* sprawl out because actions and retries rely on consistent sets
237	>	* of locally cached reads.
238		*
239		* As noted in Boehm's paper (above), sequence validation (mainly
240		* method validate()) requires stricter ordering rules than apply
#	Line 329 | Line 333 | public class StampedLock implements java
333		* @return a stamp that can be used to unlock or convert mode
334		*/
335		public long writeLock() {
336	<	long s, next;  // bypass acquireWrite in fully onlocked case only
336	>	long s, next;  // bypass acquireWrite in fully unlocked case only
337		return ((((s = state) & ABITS) == 0L &&
338		U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
339		next : acquireWrite(false, 0L));
#	Line 364 | Line 368 | public class StampedLock implements java
368		long nanos = unit.toNanos(time);
369		if (!Thread.interrupted()) {
370		long next, deadline;
371	<	if ((next = tryWriteLock()) != 0)
371	>	if ((next = tryWriteLock()) != 0L)
372		return next;
373		if (nanos <= 0L)
374		return 0L;
#	Line 401 | Line 405 | public class StampedLock implements java
405		* @return a stamp that can be used to unlock or convert mode
406		*/
407		public long readLock() {
408	<	long s, next;  // bypass acquireRead on fully onlocked case only
408	>	long s, next;  // bypass acquireRead on fully unlocked case only
409		return ((((s = state) & ABITS) == 0L &&
410		U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
411		next : acquireRead(false, 0L));
#	Line 440 | Line 444 | public class StampedLock implements java
444		*/
445		public long tryReadLock(long time, TimeUnit unit)
446		throws InterruptedException {
447	<	long next, deadline;
447	>	long s, m, next, deadline;
448		long nanos = unit.toNanos(time);
449		if (!Thread.interrupted()) {
450	<	if ((next = tryReadLock()) != 0)
451	<	return next;
450	>	if ((m = (s = state) & ABITS) != WBIT) {
451	>	if (m < RFULL) {
452	>	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
453	>	return next;
454	>	}
455	>	else if ((next = tryIncReaderOverflow(s)) != 0L)
456	>	return next;
457	>	}
458		if (nanos <= 0L)
459		return 0L;
460		if ((deadline = System.nanoTime() + nanos) == 0L)
#	Line 488 | Line 498 | public class StampedLock implements java
498		* Returns true if the lock has not been exclusively acquired
499		* since issuance of the given stamp. Always returns false if the
500		* stamp is zero. Always returns true if the stamp represents a
501	<	* currently held lock.
501	>	* currently held lock. Invoking this method with a value not
502	>	* obtained from {@link #tryOptimisticRead} or a locking method
503	>	* for this lock has no defined effect or result.
504		*
505		* @return true if the lock has not been exclusively acquired
506		* since issuance of the given stamp; else false
#	Line 524 | Line 536 | public class StampedLock implements java
536		* not match the current state of this lock
537		*/
538		public void unlockRead(long stamp) {
539	<	long s, m;  WNode h;
540	<	if ((stamp & RBITS) != 0L) {
541	<	while (((s = state) & SBITS) == (stamp & SBITS)) {
542	<	if ((m = s & ABITS) == 0L)
539	>	long s, m; WNode h;
540	>	for (;;) {
541	>	if (((s = state) & SBITS) != (stamp & SBITS) ||
542	>	(stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
543	>	throw new IllegalMonitorStateException();
544	>	if (m < RFULL) {
545	>	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
546	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
547	>	release(h);
548		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	–	}
549		}
539	–	else if (m >= WBIT)
540	–	break;
541	–	else if (tryDecReaderOverflow(s) != 0L)
542	–	return;
550		}
551	+	else if (tryDecReaderOverflow(s) != 0L)
552	+	break;
553		}
545	–	throw new IllegalMonitorStateException();
554		}
555
556		/**
#	Line 825 | Line 833 | public class StampedLock implements java
833		throws InterruptedException {
834		return tryReadLock(time, unit) != 0L;
835		}
836	<	// note that we give up ability to check mode so just use current state
829	<	public void unlock() { unlockRead(state); }
836	>	public void unlock() { unstampedUnlockRead(); }
837		public Condition newCondition() {
838		throw new UnsupportedOperationException();
839		}
#	Line 842 | Line 849 | public class StampedLock implements java
849		throws InterruptedException {
850		return tryWriteLock(time, unit) != 0L;
851		}
852	<	public void unlock() { unlockWrite(state); }
852	>	public void unlock() { unstampedUnlockWrite(); }
853		public Condition newCondition() {
854		throw new UnsupportedOperationException();
855		}
#	Line 853 | Line 860 | public class StampedLock implements java
860		public Lock writeLock() { return asWriteLock(); }
861		}
862
863	+	// Unlock methods without stamp argument checks for view classes.
864	+	// Needed because view-class lock methods throw away stamps.
865	+
866	+	final void unstampedUnlockWrite() {
867	+	WNode h; long s;
868	+	if (((s = state) & WBIT) == 0L)
869	+	throw new IllegalMonitorStateException();
870	+	state = (s += WBIT) == 0L ? ORIGIN : s;
871	+	if ((h = whead) != null && h.status != 0)
872	+	release(h);
873	+	}
874	+
875	+	final void unstampedUnlockRead() {
876	+	for (;;) {
877	+	long s, m; WNode h;
878	+	if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
879	+	throw new IllegalMonitorStateException();
880	+	else if (m < RFULL) {
881	+	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
882	+	if (m == RUNIT && (h = whead) != null && h.status != 0)
883	+	release(h);
884	+	break;
885	+	}
886	+	}
887	+	else if (tryDecReaderOverflow(s) != 0L)
888	+	break;
889	+	}
890	+	}
891	+
892		// internals
893
894		/**
#	Line 860 | Line 896 | public class StampedLock implements java
896		* access bits value to RBITS, indicating hold of spinlock,
897		* then updating, then releasing.
898		*
899	<	* @param s, assumed that (s & ABITS) >= RFULL
899	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
900		* @return new stamp on success, else zero
901		*/
902		private long tryIncReaderOverflow(long s) {
903	+	// assert (s & ABITS) >= RFULL
904		if ((s & ABITS) == RFULL) {
905		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
906		++readerOverflow;
#	Line 880 | Line 917 | public class StampedLock implements java
917		/**
918		* Tries to decrement readerOverflow.
919		*
920	<	* @param s, assumed that (s & ABITS) >= RFULL
920	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
921		* @return new stamp on success, else zero
922		*/
923		private long tryDecReaderOverflow(long s) {
924	+	// assert (s & ABITS) >= RFULL
925		if ((s & ABITS) == RFULL) {
926		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
927		int r; long next;
#	Line 903 | Line 941 | public class StampedLock implements java
941		return 0L;
942		}
943
944	<	/*
944	>	/**
945		* Wakes up the successor of h (normally whead). This is normally
946		* just h.next, but may require traversal from wtail if next
947		* pointers are lagging. This may fail to wake up an acquiring
#	Line 977 | Line 1015 | public class StampedLock implements java
1015		(p = np).next = node;   // stale
1016		if (whead == p) {
1017		for (int k = spins;;) { // spin at head
1018	<	if (((s = state) & ABITS) == 0L &&
1019	<	U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) {
1020	<	whead = node;
1021	<	node.prev = null;
1022	<	return ns;
1018	>	if (((s = state) & ABITS) == 0L) {
1019	>	if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1020	>	whead = node;
1021	>	node.prev = null;
1022	>	return ns;
1023	>	}
1024		}
1025		else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1026		--k <= 0)
#	Line 1003 | Line 1042 | public class StampedLock implements java
1042		if (deadline == 0L)
1043		time = 0L;
1044		else if ((time = deadline - System.nanoTime()) <= 0L)
1045	<	return cancelWaiter(node, null, false);
1045	>	return cancelWaiter(node, node, false);
1046		node.thread = Thread.currentThread();
1047		if (node.prev == p && p.status == WAITING && // recheck
1048	<	(p != whead || (state & ABITS) != 0L)) {
1048	>	(p != whead || (state & ABITS) != 0L))
1049		U.park(false, time);
1011	–	if (interruptible && Thread.interrupted())
1012	–	return cancelWaiter(node, null, true);
1013	–	}
1050		node.thread = null;
1051	+	if (interruptible && Thread.interrupted())
1052	+	return cancelWaiter(node, node, true);
1053		}
1054		}
1055		}
#	Line 1033 | Line 1071 | public class StampedLock implements java
1071		if (group == null && (h = whead) != null &&
1072		(q = h.next) != null && q.mode != RMODE)
1073		break;
1074	<	if ((m = (s = state) & ABITS) == WBIT)
1037	<	break;
1038	<	if (m < RFULL ?
1074	>	if ((m = (s = state) & ABITS) < RFULL ?
1075		U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1076	<	(ns = tryIncReaderOverflow(s)) != 0L) {
1076	>	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1077		if (group != null) {  // help release others
1078		for (WNode r = group;;) {
1079		if ((w = r.thread) != null) {
#	Line 1051 | Line 1087 | public class StampedLock implements java
1087		}
1088		return ns;
1089		}
1090	+	if (m >= WBIT)
1091	+	break;
1092		}
1093		if (spins > 0) {
1094		if (ThreadLocalRandom.current().nextInt() >= 0)
#	Line 1074 | Line 1112 | public class StampedLock implements java
1112		node.cowait = p.cowait, node)) {
1113		node.thread = Thread.currentThread();
1114		for (long time;;) {
1115	+	if (interruptible && Thread.interrupted())
1116	+	return cancelWaiter(node, p, true);
1117		if (deadline == 0L)
1118		time = 0L;
1119		else if ((time = deadline - System.nanoTime()) <= 0L)
#	Line 1088 | Line 1128 | public class StampedLock implements java
1128		if (node.thread == null) // must recheck
1129		break;
1130		U.park(false, time);
1091	–	if (interruptible && Thread.interrupted())
1092	–	return cancelWaiter(node, p, true);
1131		}
1132		group = p;
1133		}
#	Line 1144 | Line 1182 | public class StampedLock implements java
1182		if (deadline == 0L)
1183		time = 0L;
1184		else if ((time = deadline - System.nanoTime()) <= 0L)
1185	<	return cancelWaiter(node, null, false);
1185	>	return cancelWaiter(node, node, false);
1186		node.thread = Thread.currentThread();
1187		if (node.prev == p && p.status == WAITING &&
1188	<	(p != whead || (state & ABITS) != WBIT)) {
1188	>	(p != whead || (state & ABITS) != WBIT))
1189		U.park(false, time);
1152	–	if (interruptible && Thread.interrupted())
1153	–	return cancelWaiter(node, null, true);
1154	–	}
1190		node.thread = null;
1191	+	if (interruptible && Thread.interrupted())
1192	+	return cancelWaiter(node, node, true);
1193		}
1194		}
1195		}
1196
1197		/**
1198	<	* If node non-null, forces cancel status and unsplices from queue
1199	<	* if possible. This is a variant of cancellation methods in
1198	>	* If node non-null, forces cancel status and unsplices it from
1199	>	* queue if possible and wakes up any cowaiters (of the node, or
1200	>	* group, as applicable), and in any case helps release current
1201	>	* first waiter if lock is free. (Calling with null arguments
1202	>	* serves as a conditional form of release, which is not currently
1203	>	* needed but may be needed under possible future cancellation
1204	>	* policies). This is a variant of cancellation methods in
1205		* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1206	<	* internal documentation) that more conservatively wakes up other
1207	<	* threads that may have had their links changed, so as to preserve
1208	<	* liveness in the main signalling methods.
1206	>	* internal documentation).
1207	>	*
1208	>	* @param node if nonnull, the waiter
1209	>	* @param group either node or the group node is cowaiting with
1210	>	* @param interrupted if already interrupted
1211	>	* @return INTERRUPTED if interrupted or Thread.interrupted, else zero
1212		*/
1213		private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1214	<	if (node != null) {
1215	<	node.thread = null;
1214	>	if (node != null && group != null) {
1215	>	Thread w;
1216		node.status = CANCELLED;
1217	<	if (group != null) {
1218	<	for (WNode p = group, q; p != null; p = q) {
1219	<	if ((q = p.cowait) != null && q.status == CANCELLED) {
1220	<	U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1221	<	break;
1217	>	node.thread = null;
1218	>	// unsplice cancelled nodes from group
1219	>	for (WNode p = group, q; (q = p.cowait) != null;) {
1220	>	if (q.status == CANCELLED)
1221	>	U.compareAndSwapObject(p, WNEXT, q, q.next);
1222	>	else
1223	>	p = q;
1224	>	}
1225	>	if (group == node) {
1226	>	WNode r; // detach and wake up uncancelled co-waiters
1227	>	while ((r = node.cowait) != null) {
1228	>	if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
1229	>	(w = r.thread) != null) {
1230	>	r.thread = null;
1231	>	U.unpark(w);
1232		}
1233		}
1234	<	}
1235	<	else {
1181	<	for (WNode pred = node.prev; pred != null; ) {
1182	<	WNode succ, pp; Thread w;
1234	>	for (WNode pred = node.prev; pred != null; ) { // unsplice
1235	>	WNode succ, pp;        // find valid successor
1236		while ((succ = node.next) == null ||
1237		succ.status == CANCELLED) {
1238	<	WNode q = null;
1238	>	WNode q = null;    // find successor the slow way
1239		for (WNode t = wtail; t != null && t != node; t = t.prev)
1240		if (t.status != CANCELLED)
1241	<	q = t;
1242	<	if (succ == q ||
1241	>	q = t;     // don't link if succ cancelled
1242	>	if (succ == q ||   // ensure accurate successor
1243		U.compareAndSwapObject(node, WNEXT,
1244		succ, succ = q)) {
1245		if (succ == null && node == wtail)
#	Line 1194 | Line 1247 | public class StampedLock implements java
1247		break;
1248		}
1249		}
1250	<	if (pred.next == node)
1250	>	if (pred.next == node) // unsplice pred link
1251		U.compareAndSwapObject(pred, WNEXT, node, succ);
1252	<	if (succ != null && (w = succ.thread) != null)
1253	<	U.unpark(w);
1252	>	if (succ != null && (w = succ.thread) != null) {
1253	>	succ.thread = null;
1254	>	U.unpark(w);       // wake up succ to observe new pred
1255	>	}
1256		if (pred.status != CANCELLED || (pp = pred.prev) == null)
1257		break;
1258	<	node.prev = pp; // repeat for new pred
1258	>	node.prev = pp;        // repeat if new pred wrong/cancelled
1259		U.compareAndSwapObject(pp, WNEXT, pred, succ);
1260		pred = pp;
1261		}
1262		}
1263		}
1264	<	release(whead);
1264	>	WNode h; // Possibly release first waiter
1265	>	while ((h = whead) != null) {
1266	>	long s; WNode q; // similar to release() but check eligibility
1267	>	if ((q = h.next) == null || q.status == CANCELLED) {
1268	>	for (WNode t = wtail; t != null && t != h; t = t.prev)
1269	>	if (t.status <= 0)
1270	>	q = t;
1271	>	}
1272	>	if (h == whead) {
1273	>	if (q != null && h.status == 0 &&
1274	>	((s = state) & ABITS) != WBIT && // waiter is eligible
1275	>	(s == 0L || q.mode == RMODE))
1276	>	release(h);
1277	>	break;
1278	>	}
1279	>	}
1280		return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1281		}
1282

Diff Legend

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