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.29 by dl, Wed Jan 23 17:29:18 2013 UTC vs.
Revision 1.36 by dl, Wed Jun 19 14:55:40 2013 UTC

#	Line 5 | Line 5
5		*/
6
7		package jsr166e;
8	–
9	–	import java.util.concurrent.ThreadLocalRandom;
8		import java.util.concurrent.TimeUnit;
9	+	import java.util.concurrent.ThreadLocalRandom;
10		import java.util.concurrent.locks.Lock;
11		import java.util.concurrent.locks.Condition;
12		import java.util.concurrent.locks.ReadWriteLock;
#	Line 40 | Line 39 | import java.util.concurrent.locks.LockSu
39		*  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
40		*   returns a non-zero stamp only if the lock is not currently held
41		*   in write mode. Method {@link #validate} returns true if the lock
42	<	*   has not since been acquired in write mode. This mode can be
43	<	*   thought of as an extremely weak version of a read-lock, that can
44	<	*   be broken by a writer at any time.  The use of optimistic mode
45	<	*   for short read-only code segments often reduces contention and
46	<	*   improves throughput.  However, its use is inherently fragile.
47	<	*   Optimistic read sections should only read fields and hold them in
48	<	*   local variables for later use after validation. Fields read while
49	<	*   in optimistic mode may be wildly inconsistent, so usage applies
50	<	*   only when you are familiar enough with data representations to
51	<	*   check consistency and/or repeatedly invoke method {@code
52	<	*   validate()}.  For example, such steps are typically required when
53	<	*   first reading an object or array reference, and then accessing
54	<	*   one of its fields, elements or methods. </li>
42	>	*   has not been acquired in write mode since obtaining a given
43	>	*   stamp.  This mode can be thought of as an extremely weak version
44	>	*   of a read-lock, that can be broken by a writer at any time.  The
45	>	*   use of optimistic mode for short read-only code segments often
46	>	*   reduces contention and improves throughput.  However, its use is
47	>	*   inherently fragile.  Optimistic read sections should only read
48	>	*   fields and hold them in local variables for later use after
49	>	*   validation. Fields read while in optimistic mode may be wildly
50	>	*   inconsistent, so usage applies only when you are familiar enough
51	>	*   with data representations to check consistency and/or repeatedly
52	>	*   invoke method {@code validate()}.  For example, such steps are
53	>	*   typically required when first reading an object or array
54	>	*   reference, and then accessing one of its fields, elements or
55	>	*   methods. </li>
56		*
57		* </ul>
58		*
#	Line 118 | Line 118 | import java.util.concurrent.locks.LockSu
118		*     }
119		*   }
120		*
121	<	*   double distanceFromOriginV1() { // A read-only method
122	<	*     long stamp;
123	<	*     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
124	<	*       double currentX = x;
125	<	*       double currentY = y;
126	<	*       if (sl.validate(stamp))
127	<	*         return Math.sqrt(currentX * currentX + currentY * currentY);
128	<	*     }
129	<	*     stamp = sl.readLock(); // fall back to read lock
130	<	*     try {
131	<	*       double currentX = x;
132	<	*       double currentY = y;
133	<	*         return Math.sqrt(currentX * currentX + currentY * currentY);
134	<	*     } finally {
135	<	*       sl.unlockRead(stamp);
136	<	*     }
137	<	*   }
138	<	*
139	<	*   double distanceFromOriginV2() { // combines code paths
140	<	*     double currentX = 0.0, currentY = 0.0;
141	<	*     for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
142	<	*       try {
143	<	*         currentX = x;
144	<	*         currentY = y;
145	<	*       } finally {
146	<	*         if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
147	<	*           break;
148	<	*       }
121	>	*   double distanceFromOrigin() { // A read-only method
122	>	*     long stamp = sl.tryOptimisticRead();
123	>	*     double currentX = x, currentY = y;
124	>	*     if (!sl.validate(stamp)) {
125	>	*        stamp = sl.readLock();
126	>	*        try {
127	>	*          currentX = x;
128	>	*          currentY = y;
129	>	*        } finally {
130	>	*           sl.unlockRead(stamp);
131	>	*        }
132		*     }
133		*     return Math.sqrt(currentX * currentX + currentY * currentY);
134		*   }
#	Line 232 | Line 215 | public class StampedLock implements java
215		*
216		* Nearly all of these mechanics are carried out in methods
217		* acquireWrite and acquireRead, that, as typical of such code,
218	<	* sprawl out because actions and retries rely on consitent sets
218	>	* sprawl out because actions and retries rely on consistent sets
219		* of locally cached reads.
220		*
221		* As noted in Boehm's paper (above), sequence validation (mainly
#	Line 252 | Line 235 | public class StampedLock implements java
235		* motivation to further spread out contended locations, but might
236		* be subject to future improvements.
237		*/
238	+
239		private static final long serialVersionUID = -6001602636862214147L;
240
241		/** Number of processors, for spin control */
#	Line 331 | Line 315 | public class StampedLock implements java
315		* @return a stamp that can be used to unlock or convert mode
316		*/
317		public long writeLock() {
318	<	long s, next;  // bypass acquireWrite in fully onlocked case only
318	>	long s, next;  // bypass acquireWrite in fully unlocked case only
319		return ((((s = state) & ABITS) == 0L &&
320		U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
321		next : acquireWrite(false, 0L));
#	Line 356 | Line 340 | public class StampedLock implements java
340		* Behavior under timeout and interruption matches that specified
341		* for method {@link Lock#tryLock(long,TimeUnit)}.
342		*
343	+	* @param time the maximum time to wait for the lock
344	+	* @param unit the time unit of the {@code time} argument
345		* @return a stamp that can be used to unlock or convert mode,
346		* or zero if the lock is not available
347		* @throws InterruptedException if the current thread is interrupted
#	Line 403 | Line 389 | public class StampedLock implements java
389		* @return a stamp that can be used to unlock or convert mode
390		*/
391		public long readLock() {
392	<	long s, next;  // bypass acquireRead on fully onlocked case only
392	>	long s, next;  // bypass acquireRead on fully unlocked case only
393		return ((((s = state) & ABITS) == 0L &&
394		U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
395		next : acquireRead(false, 0L));
#	Line 435 | Line 421 | public class StampedLock implements java
421		* Behavior under timeout and interruption matches that specified
422		* for method {@link Lock#tryLock(long,TimeUnit)}.
423		*
424	+	* @param time the maximum time to wait for the lock
425	+	* @param unit the time unit of the {@code time} argument
426		* @return a stamp that can be used to unlock or convert mode,
427		* or zero if the lock is not available
428		* @throws InterruptedException if the current thread is interrupted
#	Line 442 | Line 430 | public class StampedLock implements java
430		*/
431		public long tryReadLock(long time, TimeUnit unit)
432		throws InterruptedException {
433	<	long next, deadline;
433	>	long s, m, next, deadline;
434		long nanos = unit.toNanos(time);
435		if (!Thread.interrupted()) {
436	<	if ((next = tryReadLock()) != 0L)
437	<	return next;
436	>	if ((m = (s = state) & ABITS) != WBIT) {
437	>	if (m < RFULL) {
438	>	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
439	>	return next;
440	>	}
441	>	else if ((next = tryIncReaderOverflow(s)) != 0L)
442	>	return next;
443	>	}
444		if (nanos <= 0L)
445		return 0L;
446		if ((deadline = System.nanoTime() + nanos) == 0L)
#	Line 490 | Line 484 | public class StampedLock implements java
484		* Returns true if the lock has not been exclusively acquired
485		* since issuance of the given stamp. Always returns false if the
486		* stamp is zero. Always returns true if the stamp represents a
487	<	* currently held lock.
487	>	* currently held lock. Invoking this method with a value not
488	>	* obtained from {@link #tryOptimisticRead} or a locking method
489	>	* for this lock has no defined effect or result.
490		*
491	<	* @return true if the lock has not been exclusively acquired
491	>	* @param stamp a stamp
492	>	* @return {@code true} if the lock has not been exclusively acquired
493		* since issuance of the given stamp; else false
494		*/
495		public boolean validate(long stamp) {
#	Line 705 | Line 702 | public class StampedLock implements java
702		* stamp value. This method may be useful for recovery after
703		* errors.
704		*
705	<	* @return true if the lock was held, else false
705	>	* @return {@code true} if the lock was held, else false
706		*/
707		public boolean tryUnlockWrite() {
708		long s; WNode h;
#	Line 723 | Line 720 | public class StampedLock implements java
720		* requiring a stamp value. This method may be useful for recovery
721		* after errors.
722		*
723	<	* @return true if the read lock was held, else false
723	>	* @return {@code true} if the read lock was held, else false
724		*/
725		public boolean tryUnlockRead() {
726		long s, m; WNode h;
#	Line 741 | Line 738 | public class StampedLock implements java
738		return false;
739		}
740
741	+	// status monitoring methods
742	+
743	+	/**
744	+	* Returns combined state-held and overflow read count for given
745	+	* state s.
746	+	*/
747	+	private int getReadLockCount(long s) {
748	+	long readers;
749	+	if ((readers = s & RBITS) >= RFULL)
750	+	readers = RFULL + readerOverflow;
751	+	return (int) readers;
752	+	}
753	+
754		/**
755	<	* Returns true if the lock is currently held exclusively.
755	>	* Returns {@code true} if the lock is currently held exclusively.
756		*
757	<	* @return true if the lock is currently held exclusively
757	>	* @return {@code true} if the lock is currently held exclusively
758		*/
759		public boolean isWriteLocked() {
760		return (state & WBIT) != 0L;
761		}
762
763		/**
764	<	* Returns true if the lock is currently held non-exclusively.
764	>	* Returns {@code true} if the lock is currently held non-exclusively.
765		*
766	<	* @return true if the lock is currently held non-exclusively
766	>	* @return {@code true} if the lock is currently held non-exclusively
767		*/
768		public boolean isReadLocked() {
769		return (state & RBITS) != 0L;
770		}
771
772	<	private void readObject(java.io.ObjectInputStream s)
773	<	throws java.io.IOException, ClassNotFoundException {
774	<	s.defaultReadObject();
775	<	state = ORIGIN; // reset to unlocked state
772	>	/**
773	>	* Queries the number of read locks held for this lock. This
774	>	* method is designed for use in monitoring system state, not for
775	>	* synchronization control.
776	>	* @return the number of read locks held
777	>	*/
778	>	public int getReadLockCount() {
779	>	return getReadLockCount(state);
780		}
781
782		/**
783	+	* Returns a string identifying this lock, as well as its lock
784	+	* state.  The state, in brackets, includes the String {@code
785	+	* "Unlocked"} or the String {@code "Write-locked"} or the String
786	+	* {@code "Read-locks:"} followed by the current number of
787	+	* read-locks held.
788	+	*
789	+	* @return a string identifying this lock, as well as its lock state
790	+	*/
791	+	public String toString() {
792	+	long s = state;
793	+	return super.toString() +
794	+	((s & ABITS) == 0L ? "[Unlocked]" :
795	+	(s & WBIT) != 0L ? "[Write-locked]" :
796	+	"[Read-locks:" + getReadLockCount(s) + "]");
797	+	}
798	+
799	+	// views
800	+
801	+	/**
802		* Returns a plain {@link Lock} view of this StampedLock in which
803		* the {@link Lock#lock} method is mapped to {@link #readLock},
804		* and similarly for other methods. The returned Lock does not
#	Line 879 | Line 912 | public class StampedLock implements java
912		}
913		}
914
915	+	private void readObject(java.io.ObjectInputStream s)
916	+	throws java.io.IOException, ClassNotFoundException {
917	+	s.defaultReadObject();
918	+	state = ORIGIN; // reset to unlocked state
919	+	}
920	+
921		// internals
922
923		/**
#	Line 886 | Line 925 | public class StampedLock implements java
925		* access bits value to RBITS, indicating hold of spinlock,
926		* then updating, then releasing.
927		*
928	<	* @param s, assumed that (s & ABITS) >= RFULL
928	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
929		* @return new stamp on success, else zero
930		*/
931		private long tryIncReaderOverflow(long s) {
932	+	// assert (s & ABITS) >= RFULL;
933		if ((s & ABITS) == RFULL) {
934		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
935		++readerOverflow;
#	Line 906 | Line 946 | public class StampedLock implements java
946		/**
947		* Tries to decrement readerOverflow.
948		*
949	<	* @param s, assumed that (s & ABITS) >= RFULL
949	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
950		* @return new stamp on success, else zero
951		*/
952		private long tryDecReaderOverflow(long s) {
953	+	// assert (s & ABITS) >= RFULL;
954		if ((s & ABITS) == RFULL) {
955		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
956		int r; long next;
#	Line 929 | Line 970 | public class StampedLock implements java
970		return 0L;
971		}
972
973	<	/*
973	>	/**
974		* Wakes up the successor of h (normally whead). This is normally
975		* just h.next, but may require traversal from wtail if next
976		* pointers are lagging. This may fail to wake up an acquiring
#	Line 1030 | Line 1071 | public class StampedLock implements java
1071		if (deadline == 0L)
1072		time = 0L;
1073		else if ((time = deadline - System.nanoTime()) <= 0L)
1074	<	return cancelWaiter(node, null, false);
1075	<	node.thread = Thread.currentThread();
1074	>	return cancelWaiter(node, node, false);
1075	>	Thread wt = Thread.currentThread();
1076	>	U.putObject(wt, PARKBLOCKER, this); // emulate LockSupport.park
1077	>	node.thread = wt;
1078		if (node.prev == p && p.status == WAITING && // recheck
1079	<	(p != whead || (state & ABITS) != 0L)) {
1079	>	(p != whead || (state & ABITS) != 0L))
1080		U.park(false, time);
1038	–	if (interruptible && Thread.interrupted())
1039	–	return cancelWaiter(node, null, true);
1040	–	}
1081		node.thread = null;
1082	+	U.putObject(wt, PARKBLOCKER, null);
1083	+	if (interruptible && Thread.interrupted())
1084	+	return cancelWaiter(node, node, true);
1085		}
1086		}
1087		}
#	Line 1112 | Line 1155 | public class StampedLock implements java
1155		node.thread = null;
1156		break;
1157		}
1158	+	Thread wt = Thread.currentThread();
1159	+	U.putObject(wt, PARKBLOCKER, this);
1160		if (node.thread == null) // must recheck
1161		break;
1162		U.park(false, time);
1163	+	U.putObject(wt, PARKBLOCKER, null);
1164		if (interruptible && Thread.interrupted())
1165		return cancelWaiter(node, p, true);
1166		}
#	Line 1171 | Line 1217 | public class StampedLock implements java
1217		if (deadline == 0L)
1218		time = 0L;
1219		else if ((time = deadline - System.nanoTime()) <= 0L)
1220	<	return cancelWaiter(node, null, false);
1221	<	node.thread = Thread.currentThread();
1220	>	return cancelWaiter(node, node, false);
1221	>	Thread wt = Thread.currentThread();
1222	>	U.putObject(wt, PARKBLOCKER, this);
1223	>	node.thread = wt;
1224		if (node.prev == p && p.status == WAITING &&
1225	<	(p != whead || (state & ABITS) != WBIT)) {
1225	>	(p != whead || (state & ABITS) != WBIT))
1226		U.park(false, time);
1179	–	if (interruptible && Thread.interrupted())
1180	–	return cancelWaiter(node, null, true);
1181	–	}
1227		node.thread = null;
1228	+	U.putObject(wt, PARKBLOCKER, null);
1229	+	if (interruptible && Thread.interrupted())
1230	+	return cancelWaiter(node, node, true);
1231		}
1232		}
1233		}
1234
1235		/**
1236	<	* If node non-null, forces cancel status and unsplices from queue
1237	<	* if possible. This is a variant of cancellation methods in
1236	>	* If node non-null, forces cancel status and unsplices it from
1237	>	* queue if possible and wakes up any cowaiters (of the node, or
1238	>	* group, as applicable), and in any case helps release current
1239	>	* first waiter if lock is free. (Calling with null arguments
1240	>	* serves as a conditional form of release, which is not currently
1241	>	* needed but may be needed under possible future cancellation
1242	>	* policies). This is a variant of cancellation methods in
1243		* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1244	<	* internal documentation) that more conservatively wakes up other
1245	<	* threads that may have had their links changed, so as to preserve
1246	<	* liveness in the main signalling methods.
1244	>	* internal documentation).
1245	>	*
1246	>	* @param node if nonnull, the waiter
1247	>	* @param group either node or the group node is cowaiting with
1248	>	* @param interrupted if already interrupted
1249	>	* @return INTERRUPTED if interrupted or Thread.interrupted, else zero
1250		*/
1251		private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1252	<	if (node != null) {
1253	<	node.thread = null;
1252	>	if (node != null && group != null) {
1253	>	Thread w;
1254		node.status = CANCELLED;
1255	<	if (group != null) {
1256	<	for (WNode p = group, q; p != null; p = q) {
1257	<	if ((q = p.cowait) != null && q.status == CANCELLED) {
1258	<	U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1259	<	break;
1255	>	node.thread = null;
1256	>	// unsplice cancelled nodes from group
1257	>	for (WNode p = group, q; (q = p.cowait) != null;) {
1258	>	if (q.status == CANCELLED)
1259	>	U.compareAndSwapObject(p, WNEXT, q, q.next);
1260	>	else
1261	>	p = q;
1262	>	}
1263	>	if (group == node) {
1264	>	WNode r; // detach and wake up uncancelled co-waiters
1265	>	while ((r = node.cowait) != null) {
1266	>	if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
1267	>	(w = r.thread) != null) {
1268	>	r.thread = null;
1269	>	U.unpark(w);
1270		}
1271		}
1272	<	}
1273	<	else {
1208	<	for (WNode pred = node.prev; pred != null; ) {
1209	<	WNode succ, pp; Thread w;
1272	>	for (WNode pred = node.prev; pred != null; ) { // unsplice
1273	>	WNode succ, pp;        // find valid successor
1274		while ((succ = node.next) == null ||
1275		succ.status == CANCELLED) {
1276	<	WNode q = null;
1276	>	WNode q = null;    // find successor the slow way
1277		for (WNode t = wtail; t != null && t != node; t = t.prev)
1278		if (t.status != CANCELLED)
1279	<	q = t;
1280	<	if (succ == q ||
1279	>	q = t;     // don't link if succ cancelled
1280	>	if (succ == q ||   // ensure accurate successor
1281		U.compareAndSwapObject(node, WNEXT,
1282		succ, succ = q)) {
1283		if (succ == null && node == wtail)
#	Line 1221 | Line 1285 | public class StampedLock implements java
1285		break;
1286		}
1287		}
1288	<	if (pred.next == node)
1288	>	if (pred.next == node) // unsplice pred link
1289		U.compareAndSwapObject(pred, WNEXT, node, succ);
1290	<	if (succ != null && (w = succ.thread) != null)
1291	<	U.unpark(w);
1290	>	if (succ != null && (w = succ.thread) != null) {
1291	>	succ.thread = null;
1292	>	U.unpark(w);       // wake up succ to observe new pred
1293	>	}
1294		if (pred.status != CANCELLED || (pp = pred.prev) == null)
1295		break;
1296	<	node.prev = pp; // repeat for new pred
1296	>	node.prev = pp;        // repeat if new pred wrong/cancelled
1297		U.compareAndSwapObject(pp, WNEXT, pred, succ);
1298		pred = pp;
1299		}
1300		}
1301		}
1302	<	release(whead);
1302	>	WNode h; // Possibly release first waiter
1303	>	while ((h = whead) != null) {
1304	>	long s; WNode q; // similar to release() but check eligibility
1305	>	if ((q = h.next) == null || q.status == CANCELLED) {
1306	>	for (WNode t = wtail; t != null && t != h; t = t.prev)
1307	>	if (t.status <= 0)
1308	>	q = t;
1309	>	}
1310	>	if (h == whead) {
1311	>	if (q != null && h.status == 0 &&
1312	>	((s = state) & ABITS) != WBIT && // waiter is eligible
1313	>	(s == 0L || q.mode == RMODE))
1314	>	release(h);
1315	>	break;
1316	>	}
1317	>	}
1318		return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1319		}
1320
#	Line 1245 | Line 1326 | public class StampedLock implements java
1326		private static final long WNEXT;
1327		private static final long WSTATUS;
1328		private static final long WCOWAIT;
1329	+	private static final long PARKBLOCKER;
1330
1331		static {
1332		try {
#	Line 1263 | Line 1345 | public class StampedLock implements java
1345		(wk.getDeclaredField("next"));
1346		WCOWAIT = U.objectFieldOffset
1347		(wk.getDeclaredField("cowait"));
1348	+	Class<?> tk = Thread.class;
1349	+	PARKBLOCKER = U.objectFieldOffset
1350	+	(tk.getDeclaredField("parkBlocker"));
1351
1352		} catch (Exception e) {
1353		throw new Error(e);

Diff Legend

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