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.7 by dl, Fri Oct 12 23:11:14 2012 UTC vs.
Revision 1.27 by jsr166, Mon Jan 14 19:00:01 2013 UTC

#	Line 11 | Line 11 | import java.util.concurrent.TimeUnit;
11
12		/**
13		* A capability-based lock with three modes for controlling read/write
14	<	* access.  The state of a StampedLock consists of a version and
15	<	* mode. Lock acquisition methods return a stamp that represents and
14	>	* access.  The state of a StampedLock consists of a version and mode.
15	>	* Lock acquisition methods return a stamp that represents and
16		* controls access with respect to a lock state; "try" versions of
17		* these methods may instead return the special value zero to
18		* represent failure to acquire access. Lock release and conversion
#	Line 55 | Line 55 | import java.util.concurrent.TimeUnit;
55		* <p>This class also supports methods that conditionally provide
56		* conversions across the three modes. For example, method {@link
57		* #tryConvertToWriteLock} attempts to "upgrade" a mode, returning
58	<	* valid write stamp if (1) already in writing mode (2) in reading
58	>	* a valid write stamp if (1) already in writing mode (2) in reading
59		* mode and there are no other readers or (3) in optimistic mode and
60		* the lock is available. The forms of these methods are designed to
61		* help reduce some of the code bloat that otherwise occurs in
62		* retry-based designs.
63		*
64	<	* <p>StampedLocks are designed for use in a different (and generally
65	<	* narrower) range of contexts than most other locks: They are not
66	<	* reentrant, so locked bodies should not call other unknown methods
67	<	* that may try to re-acquire locks (although you may pass a stamp to
68	<	* other methods that can use or convert it). Unvalidated optimistic
69	<	* read sections should further not call methods that are not known to
64	>	* <p>StampedLocks are designed for use as internal utilities in the
65	>	* development of thread-safe components. Their use relies on
66	>	* knowledge of the internal properties of the data, objects, and
67	>	* methods they are protecting.  They are not reentrant, so locked
68	>	* bodies should not call other unknown methods that may try to
69	>	* re-acquire locks (although you may pass a stamp to other methods
70	>	* that can use or convert it).  The use of read lock modes relies on
71	>	* the associated code sections being side-effect-free.  Unvalidated
72	>	* optimistic read sections cannot call methods that are not known to
73		* tolerate potential inconsistencies.  Stamps use finite
74		* representations, and are not cryptographically secure (i.e., a
75		* valid stamp may be guessable). Stamp values may recycle after (no
#	Line 78 | Line 81 | import java.util.concurrent.TimeUnit;
81		*
82		* <p>The scheduling policy of StampedLock does not consistently
83		* prefer readers over writers or vice versa.  A zero return from any
84	<	* "try" method for acquiring or converting locks does carry any
84	>	* "try" method for acquiring or converting locks does not carry any
85		* information about the state of the lock; a subsequent invocation
86		* may succeed.
87		*
#	Line 122 | Line 125 | import java.util.concurrent.TimeUnit;
125		*   }
126		*
127		*   double distanceFromOriginV2() { // combines code paths
128	+	*     double currentX = 0.0, currentY = 0.0;
129		*     for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
126	–	*       double currentX, currentY;
130		*       try {
131		*         currentX = x;
132		*         currentY = y;
133		*       } finally {
134		*         if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
135	<	*           return Math.sqrt(currentX * currentX + currentY * currentY);
135	>	*           break;
136		*       }
137		*     }
138	+	*     return Math.sqrt(currentX * currentX + currentY * currentY);
139		*   }
140		*
141		*   void moveIfAtOrigin(double newX, double newY) { // upgrade
#	Line 139 | Line 143 | import java.util.concurrent.TimeUnit;
143		*     long stamp = sl.readLock();
144		*     try {
145		*       while (x == 0.0 && y == 0.0) {
146	<	*         long ws = tryConvertToWriteLock(stamp);
146	>	*         long ws = sl.tryConvertToWriteLock(stamp);
147		*         if (ws != 0L) {
148		*           stamp = ws;
149		*           x = newX;
#	Line 152 | Line 156 | import java.util.concurrent.TimeUnit;
156		*         }
157		*       }
158		*     } finally {
159	<	*        sl.unlock(stamp);
159	>	*       sl.unlock(stamp);
160		*     }
161		*   }
162		* }}</pre>
#	Line 180 | Line 184 | public class StampedLock implements java
184		* read-locked.  The read count is ignored when validating
185		* "optimistic" seqlock-reader-style stamps.  Because we must use
186		* a small finite number of bits (currently 7) for readers, a
187	<	* supplementary reader overflow word is used when then number of
187	>	* supplementary reader overflow word is used when the number of
188		* readers exceeds the count field. We do this by treating the max
189		* reader count value (RBITS) as a spinlock protecting overflow
190		* updates.
#	Line 216 | Line 220 | public class StampedLock implements java
220		* in-progress spins/signals, and others do not account for
221		* cancellations.
222		*
223	+	* Controlled, randomized spinning is used in the two await
224	+	* methods to reduce (increasingly expensive) context switching
225	+	* while also avoiding sustained memory thrashing among many
226	+	* threads.  Both await methods use a similar spin strategy: If
227	+	* the associated queue appears to be empty, then the thread
228	+	* spin-waits up to SPINS times (where each iteration decreases
229	+	* spin count with 50% probability) before enqueuing, and then, if
230	+	* it is the first thread to be enqueued, spins again up to SPINS
231	+	* times before blocking. If, upon wakening it fails to obtain
232	+	* lock, and is still (or becomes) the first waiting thread (which
233	+	* indicates that some other thread barged and obtained lock), it
234	+	* escalates spins (up to MAX_HEAD_SPINS) to reduce the likelihood
235	+	* of continually losing to barging threads.
236	+	*
237		* As noted in Boehm's paper (above), sequence validation (mainly
238		* method validate()) requires stricter ordering rules than apply
239		* to normal volatile reads (of "state").  In the absence of (but
#	Line 234 | Line 252 | public class StampedLock implements java
252		* be subject to future improvements.
253		*/
254
255	+	private static final long serialVersionUID = -6001602636862214147L;
256	+
257		/** Number of processors, for spin control */
258		private static final int NCPU = Runtime.getRuntime().availableProcessors();
259
#	Line 247 | Line 267 | public class StampedLock implements java
267		private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
268
269		/** The number of bits to use for reader count before overflowing */
270	<	private static final int  LG_READERS = 7;
270	>	private static final int LG_READERS = 7;
271
272		// Values for lock state and stamp operations
273		private static final long RUNIT = 1L;
#	Line 296 | Line 316 | public class StampedLock implements java
316		private transient int readerOverflow;
317
318		/**
319	<	* Creates a new lock initially in unlocked state.
319	>	* Creates a new lock, initially in unlocked state.
320		*/
321		public StampedLock() {
322		state = ORIGIN;
#	Line 320 | Line 340 | public class StampedLock implements java
340		* Exclusively acquires the lock if it is immediately available.
341		*
342		* @return a stamp that can be used to unlock or convert mode,
343	<	* or zero if the lock is not available.
343	>	* or zero if the lock is not available
344		*/
345		public long tryWriteLock() {
346		long s, next;
#	Line 497 | Line 517 | public class StampedLock implements java
517		}
518
519		/**
520	<	* Returns true if the lock has not been exclusively held since
521	<	* issuance of the given stamp. Always returns false if the stamp
522	<	* is zero. Always returns true if the stamp represents a
520	>	* Returns true if the lock has not been exclusively acquired
521	>	* since issuance of the given stamp. Always returns false if the
522	>	* stamp is zero. Always returns true if the stamp represents a
523		* currently held lock.
524		*
525	<	* @return true if the lock has not been exclusively held since
526	<	* issuance of the given stamp; else false
525	>	* @return true if the lock has not been exclusively acquired
526	>	* since issuance of the given stamp; else false
527		*/
528		public boolean validate(long stamp) {
529	+	// See above about current use of getLongVolatile here
530		return (stamp & SBITS) == (U.getLongVolatile(this, STATE) & SBITS);
531		}
532
#	Line 525 | Line 546 | public class StampedLock implements java
546		}
547
548		/**
549	<	* If the lock state matches the given stamp, releases
549	>	* If the lock state matches the given stamp, releases the
550		* non-exclusive lock.
551		*
552		* @param stamp a stamp returned by a read-lock operation
#	Line 592 | Line 613 | public class StampedLock implements java
613		/**
614		* If the lock state matches the given stamp then performs one of
615		* the following actions. If the stamp represents holding a write
616	<	* lock, returns it. Or, if a read lock, if the write lock is
617	<	* available, releases the read and returns a write stamp. Or, if
618	<	* an optimistic read, returns a write stamp only if immediately
619	<	* available. This method returns zero in all other cases.
616	>	* lock, returns it.  Or, if a read lock, if the write lock is
617	>	* available, releases the read lock and returns a write stamp.
618	>	* Or, if an optimistic read, returns a write stamp only if
619	>	* immediately available. This method returns zero in all other
620	>	* cases.
621		*
622		* @param stamp a stamp
623		* @return a valid write stamp, or zero on failure
#	Line 614 | Line 636 | public class StampedLock implements java
636		break;
637		return stamp;
638		}
639	<	else if (m == RUNIT && a != 0L && a < WBIT) {
639	>	else if (m == RUNIT && a != 0L) {
640		if (U.compareAndSwapLong(this, STATE, s,
641		next = s - RUNIT + WBIT))
642		return next;
#	Line 652 | Line 674 | public class StampedLock implements java
674		else if (m == WBIT) {
675		if (a != m)
676		break;
677	<	next = state = s + (WBIT + RUNIT);
677	>	state = next = s + (WBIT + RUNIT);
678		readerPrefSignal();
679		return next;
680		}
#	Line 686 | Line 708 | public class StampedLock implements java
708		else if (m == WBIT) {
709		if (a != m)
710		break;
711	<	next = state = (s += WBIT) == 0L ? ORIGIN : s;
711	>	state = next = (s += WBIT) == 0L ? ORIGIN : s;
712		readerPrefSignal();
713		return next;
714		}
#	Line 760 | Line 782 | public class StampedLock implements java
782		* @return true if the lock is currently held non-exclusively
783		*/
784		public boolean isReadLocked() {
785	<	long m;
764	<	return (m = state & ABITS) > 0L && m < WBIT;
785	>	return (state & RBITS) != 0L;
786		}
787
788		private void readObject(java.io.ObjectInputStream s)
#	Line 777 | Line 798 | public class StampedLock implements java
798		* access bits value to RBITS, indicating hold of spinlock,
799		* then updating, then releasing.
800		*
801	<	* @param stamp, assumed that (stamp & ABITS) >= RFULL
801	>	* @param s, assumed that (s & ABITS) >= RFULL
802		* @return new stamp on success, else zero
803		*/
804		private long tryIncReaderOverflow(long s) {
#	Line 797 | Line 818 | public class StampedLock implements java
818		/**
819		* Tries to decrement readerOverflow.
820		*
821	<	* @param stamp, assumed that (stamp & ABITS) >= RFULL
821	>	* @param s, assumed that (s & ABITS) >= RFULL
822		* @return new stamp on success, else zero
823		*/
824		private long tryDecReaderOverflow(long s) {
#	Line 853 | Line 874 | public class StampedLock implements java
874		U.compareAndSwapObject(p, WAITER, w, null))
875		U.unpark(w);
876		}
877	<	if (!readers && (state & ABITS) == 0L &&
878	<	(h = whead) != null && h.status != 0) {
877	>	if (!readers && (h = whead) != null && h.status != 0 &&
878	>	(state & ABITS) == 0L) {
879		U.compareAndSwapInt(h, STATUS, WAITING, 0);
880		if ((q = h.next) == null || q.status == CANCELLED) {
860	–	q = null;
881		for (WNode t = wtail; t != null && t != h; t = t.prev)
882		if (t.status <= 0)
883		q = t;
#	Line 872 | Line 892 | public class StampedLock implements java
892		if ((h = whead) != null && h.status != 0) {
893		U.compareAndSwapInt(h, STATUS, WAITING, 0);
894		if ((q = h.next) == null || q.status == CANCELLED) {
875	–	q = null;
895		for (WNode t = wtail; t != null && t != h; t = t.prev)
896		if (t.status <= 0)
897		q = t;
#	Line 894 | Line 913 | public class StampedLock implements java
913		/**
914		* RNG for local spins. The first call from await{Read,Write}
915		* produces a thread-local value. Unless zero, subsequent calls
916	<	* use an xorShift to further reduce memory traffic.  Both await
898	<	* methods use a similar spin strategy: If associated queue
899	<	* appears to be empty, then the thread spin-waits up to SPINS
900	<	* times before enqueing, and then, if the first thread to be
901	<	* enqueued, spins again up to SPINS times before blocking. If,
902	<	* upon wakening it fails to obtain lock, and is still (or
903	<	* becomes) the first waiting thread (which indicates that some
904	<	* other thread barged and obtained lock), it escalates spins (up
905	<	* to MAX_HEAD_SPINS) to reduce the likelihood of continually
906	<	* losing to barging threads.
916	>	* use an xorShift to further reduce memory traffic.
917		*/
918		private static int nextRandom(int r) {
919		if (r == 0)
#	Line 951 | Line 961 | public class StampedLock implements java
961		else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
962		p.next = node;
963		for (int headSpins = SPINS;;) {
964	<	WNode np; int ps;
965	<	if ((np = node.prev) != p && np != null)
964	>	WNode np, pp; int ps;
965	>	while ((np = node.prev) != p && np != null)
966		(p = np).next = node; // stale
967		if (p == whead) {
968		for (int k = headSpins;;) {
#	Line 974 | Line 984 | public class StampedLock implements java
984		}
985		if ((ps = p.status) == 0)
986		U.compareAndSwapInt(p, STATUS, 0, WAITING);
987	<	else if (ps == CANCELLED)
988	<	node.prev = p.prev;
987	>	else if (ps == CANCELLED) {
988	>	if ((pp = p.prev) != null) {
989	>	node.prev = pp;
990	>	pp.next = node;
991	>	}
992	>	}
993		else {
994		long time; // 0 argument to park means no timeout
995		if (deadline == 0L)
#	Line 983 | Line 997 | public class StampedLock implements java
997		else if ((time = deadline - System.nanoTime()) <= 0L)
998		return cancelWriter(node, false);
999		if (node.prev == p && p.status == WAITING &&
1000	<	(p != whead || (state & WBIT) != 0L)) { // recheck
1000	>	(p != whead || (state & ABITS) != 0L)) // recheck
1001		U.park(false, time);
1002	<	if (interruptible && Thread.interrupted())
1003	<	return cancelWriter(node, true);
990	<	}
1002	>	if (interruptible && Thread.interrupted())
1003	>	return cancelWriter(node, true);
1004		}
1005		}
1006		}
#	Line 996 | Line 1009 | public class StampedLock implements java
1009
1010		/**
1011		* If node non-null, forces cancel status and unsplices from queue
1012	<	* if possible. This is a streamlined variant of cancellation
1013	<	* methods in AbstractQueuedSynchronizer that includes a detailed
1014	<	* explanation.
1012	>	* if possible. This is a variant of cancellation methods in
1013	>	* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1014	>	* internal documentation) that more conservatively wakes up other
1015	>	* threads that may have had their links changed, so as to preserve
1016	>	* liveness in the main signalling methods.
1017		*/
1018		private long cancelWriter(WNode node, boolean interrupted) {
1019	<	WNode pred;
1005	<	if (node != null && (pred = node.prev) != null) {
1006	<	WNode pp;
1019	>	if (node != null) {
1020		node.thread = null;
1008	–	while (pred.status == CANCELLED && (pp = pred.prev) != null)
1009	–	pred = node.prev = pp;
1010	–	WNode predNext = pred.next;
1021		node.status = CANCELLED;
1022	<	if (predNext != null) {
1023	<	Thread w = null;
1024	<	WNode succ = node.next;
1025	<	while (succ != null && succ.status == CANCELLED)
1026	<	succ = succ.next;
1027	<	if (succ != null)
1028	<	w = succ.thread;
1029	<	else if (node == wtail)
1030	<	U.compareAndSwapObject(this, WTAIL, node, pred);
1031	<	U.compareAndSwapObject(pred, WNEXT, predNext, succ);
1032	<	if (w != null)
1022	>	for (WNode pred = node.prev; pred != null; ) {
1023	>	WNode succ, pp; Thread w;
1024	>	while ((succ = node.next) == null || succ.status == CANCELLED) {
1025	>	WNode q = null;
1026	>	for (WNode t = wtail; t != null && t != node; t = t.prev)
1027	>	if (t.status != CANCELLED)
1028	>	q = t;
1029	>	if (succ == q ||
1030	>	U.compareAndSwapObject(node, WNEXT, succ, succ = q)) {
1031	>	if (succ == null && node == wtail)
1032	>	U.compareAndSwapObject(this, WTAIL, node, pred);
1033	>	break;
1034	>	}
1035	>	}
1036	>	if (pred.next == node)
1037	>	U.compareAndSwapObject(pred, WNEXT, node, succ);
1038	>	if (succ != null && (w = succ.thread) != null)
1039		U.unpark(w);
1040	+	if (pred.status != CANCELLED || (pp = pred.prev) == null)
1041	+	break;
1042	+	node.prev = pp; // repeat for new pred
1043	+	U.compareAndSwapObject(pp, WNEXT, pred, succ);
1044	+	pred = pp;
1045		}
1046		}
1047		writerPrefSignal();
#	Line 1094 | Line 1115 | public class StampedLock implements java
1115		time = 0L;
1116		else if ((time = deadline - System.nanoTime()) <= 0L)
1117		return cancelReader(node, false);
1118	<	if ((state & WBIT) != 0L && node.waiter != null) { // recheck
1118	>	if ((state & WBIT) != 0L && node.waiter != null) // recheck
1119		U.park(false, time);
1120	<	if (interruptible && Thread.interrupted())
1121	<	return cancelReader(node, true);
1101	<	}
1120	>	if (interruptible && Thread.interrupted())
1121	>	return cancelReader(node, true);
1122		}
1123		}
1124		}
#	Line 1186 | Line 1206 | public class StampedLock implements java
1206		private static sun.misc.Unsafe getUnsafe() {
1207		try {
1208		return sun.misc.Unsafe.getUnsafe();
1209	<	} catch (SecurityException se) {
1210	<	try {
1211	<	return java.security.AccessController.doPrivileged
1212	<	(new java.security
1213	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1214	<	public sun.misc.Unsafe run() throws Exception {
1215	<	java.lang.reflect.Field f = sun.misc
1216	<	.Unsafe.class.getDeclaredField("theUnsafe");
1217	<	f.setAccessible(true);
1218	<	return (sun.misc.Unsafe) f.get(null);
1219	<	}});
1220	<	} catch (java.security.PrivilegedActionException e) {
1221	<	throw new RuntimeException("Could not initialize intrinsics",
1222	<	e.getCause());
1223	<	}
1209	>	} catch (SecurityException tryReflectionInstead) {}
1210	>	try {
1211	>	return java.security.AccessController.doPrivileged
1212	>	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1213	>	public sun.misc.Unsafe run() throws Exception {
1214	>	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1215	>	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1216	>	f.setAccessible(true);
1217	>	Object x = f.get(null);
1218	>	if (k.isInstance(x))
1219	>	return k.cast(x);
1220	>	}
1221	>	throw new NoSuchFieldError("the Unsafe");
1222	>	}});
1223	>	} catch (java.security.PrivilegedActionException e) {
1224	>	throw new RuntimeException("Could not initialize intrinsics",
1225	>	e.getCause());
1226		}
1227		}
1206	–
1228		}

Diff Legend

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