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.32 by dl, Sat Jan 26 01:22:37 2013 UTC vs.
Revision 1.38 by dl, Mon Aug 19 14:30:37 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.locks.Lock;
10		import java.util.concurrent.locks.Condition;
#	Line 119 | Line 117 | import java.util.concurrent.locks.LockSu
117		*     }
118		*   }
119		*
120	<	*   double distanceFromOriginV1() { // A read-only method
121	<	*     long stamp;
122	<	*     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
123	<	*       double currentX = x;
124	<	*       double currentY = y;
125	<	*       if (sl.validate(stamp))
126	<	*         return Math.sqrt(currentX * currentX + currentY * currentY);
127	<	*     }
128	<	*     stamp = sl.readLock(); // fall back to read lock
129	<	*     try {
130	<	*       double currentX = x;
133	<	*       double currentY = y;
134	<	*         return Math.sqrt(currentX * currentX + currentY * currentY);
135	<	*     } finally {
136	<	*       sl.unlockRead(stamp);
137	<	*     }
138	<	*   }
139	<	*
140	<	*   double distanceFromOriginV2() { // combines code paths
141	<	*     double currentX = 0.0, currentY = 0.0;
142	<	*     for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
143	<	*       try {
144	<	*         currentX = x;
145	<	*         currentY = y;
146	<	*       } finally {
147	<	*         if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
148	<	*           break;
149	<	*       }
120	>	*   double distanceFromOrigin() { // A read-only method
121	>	*     long stamp = sl.tryOptimisticRead();
122	>	*     double currentX = x, currentY = y;
123	>	*     if (!sl.validate(stamp)) {
124	>	*        stamp = sl.readLock();
125	>	*        try {
126	>	*          currentX = x;
127	>	*          currentY = y;
128	>	*        } finally {
129	>	*           sl.unlockRead(stamp);
130	>	*        }
131		*     }
132		*     return Math.sqrt(currentX * currentX + currentY * currentY);
133		*   }
#	Line 215 | Line 196 | public class StampedLock implements java
196		* incoming reader arrives while read lock is held but there is a
197		* queued writer, this incoming reader is queued.  (This rule is
198		* responsible for some of the complexity of method acquireRead,
199	<	* but without it, the lock becomes highly unfair.)
199	>	* but without it, the lock becomes highly unfair.) Method release
200	>	* does not (and sometimes cannot) itself wake up cowaiters. This
201	>	* is done by the primary thread, but helped by any other threads
202	>	* with nothing better to do in methods acquireRead and
203	>	* acquireWrite.
204		*
205		* These rules apply to threads actually queued. All tryLock forms
206		* opportunistically try to acquire locks regardless of preference
#	Line 253 | Line 238 | public class StampedLock implements java
238		* motivation to further spread out contended locations, but might
239		* be subject to future improvements.
240		*/
241	+
242		private static final long serialVersionUID = -6001602636862214147L;
243
244		/** Number of processors, for spin control */
245		private static final int NCPU = Runtime.getRuntime().availableProcessors();
246
247	<	/** Maximum number of retries before blocking on acquisition */
247	>	/** Maximum number of retries before enqueuing on acquisition */
248		private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;
249
250	+	/** Maximum number of retries before blocking at head on acquisition */
251	+	private static final int HEAD_SPINS = (NCPU > 1) ? 1 << 10 : 0;
252	+
253		/** Maximum number of retries before re-blocking */
254	<	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 0;
254	>	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 16 : 0;
255
256		/** The period for yielding when waiting for overflow spinlock */
257		private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
#	Line 357 | Line 346 | public class StampedLock implements java
346		* Behavior under timeout and interruption matches that specified
347		* for method {@link Lock#tryLock(long,TimeUnit)}.
348		*
349	+	* @param time the maximum time to wait for the lock
350	+	* @param unit the time unit of the {@code time} argument
351		* @return a stamp that can be used to unlock or convert mode,
352		* or zero if the lock is not available
353		* @throws InterruptedException if the current thread is interrupted
#	Line 404 | Line 395 | public class StampedLock implements java
395		* @return a stamp that can be used to unlock or convert mode
396		*/
397		public long readLock() {
398	<	long s, next;  // bypass acquireRead on fully unlocked case only
399	<	return ((((s = state) & ABITS) == 0L &&
398	>	long s = state, next;  // bypass acquireRead on common uncontended case
399	>	return ((whead == wtail && (s & ABITS) < RFULL &&
400		U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
401		next : acquireRead(false, 0L));
402		}
#	Line 436 | Line 427 | public class StampedLock implements java
427		* Behavior under timeout and interruption matches that specified
428		* for method {@link Lock#tryLock(long,TimeUnit)}.
429		*
430	+	* @param time the maximum time to wait for the lock
431	+	* @param unit the time unit of the {@code time} argument
432		* @return a stamp that can be used to unlock or convert mode,
433		* or zero if the lock is not available
434		* @throws InterruptedException if the current thread is interrupted
#	Line 443 | Line 436 | public class StampedLock implements java
436		*/
437		public long tryReadLock(long time, TimeUnit unit)
438		throws InterruptedException {
439	<	long next, deadline;
439	>	long s, m, next, deadline;
440		long nanos = unit.toNanos(time);
441		if (!Thread.interrupted()) {
442	<	if ((next = tryReadLock()) != 0L)
443	<	return next;
442	>	if ((m = (s = state) & ABITS) != WBIT) {
443	>	if (m < RFULL) {
444	>	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
445	>	return next;
446	>	}
447	>	else if ((next = tryIncReaderOverflow(s)) != 0L)
448	>	return next;
449	>	}
450		if (nanos <= 0L)
451		return 0L;
452		if ((deadline = System.nanoTime() + nanos) == 0L)
#	Line 495 | Line 494 | public class StampedLock implements java
494		* obtained from {@link #tryOptimisticRead} or a locking method
495		* for this lock has no defined effect or result.
496		*
497	<	* @return true if the lock has not been exclusively acquired
497	>	* @param stamp a stamp
498	>	* @return {@code true} if the lock has not been exclusively acquired
499		* since issuance of the given stamp; else false
500		*/
501		public boolean validate(long stamp) {
#	Line 673 | Line 673 | public class StampedLock implements java
673		long a = stamp & ABITS, m, s, next; WNode h;
674		for (;;) {
675		s = U.getLongVolatile(this, STATE); // see above
676	<	if ((s & SBITS) != (stamp & SBITS))
676	>	if (((s = state) & SBITS) != (stamp & SBITS))
677		break;
678		if ((m = s & ABITS) == 0L) {
679		if (a != 0L)
#	Line 708 | Line 708 | public class StampedLock implements java
708		* stamp value. This method may be useful for recovery after
709		* errors.
710		*
711	<	* @return true if the lock was held, else false
711	>	* @return {@code true} if the lock was held, else false
712		*/
713		public boolean tryUnlockWrite() {
714		long s; WNode h;
#	Line 726 | Line 726 | public class StampedLock implements java
726		* requiring a stamp value. This method may be useful for recovery
727		* after errors.
728		*
729	<	* @return true if the read lock was held, else false
729	>	* @return {@code true} if the read lock was held, else false
730		*/
731		public boolean tryUnlockRead() {
732		long s, m; WNode h;
#	Line 744 | Line 744 | public class StampedLock implements java
744		return false;
745		}
746
747	+	// status monitoring methods
748	+
749	+	/**
750	+	* Returns combined state-held and overflow read count for given
751	+	* state s.
752	+	*/
753	+	private int getReadLockCount(long s) {
754	+	long readers;
755	+	if ((readers = s & RBITS) >= RFULL)
756	+	readers = RFULL + readerOverflow;
757	+	return (int) readers;
758	+	}
759	+
760		/**
761	<	* Returns true if the lock is currently held exclusively.
761	>	* Returns {@code true} if the lock is currently held exclusively.
762		*
763	<	* @return true if the lock is currently held exclusively
763	>	* @return {@code true} if the lock is currently held exclusively
764		*/
765		public boolean isWriteLocked() {
766		return (state & WBIT) != 0L;
767		}
768
769		/**
770	<	* Returns true if the lock is currently held non-exclusively.
770	>	* Returns {@code true} if the lock is currently held non-exclusively.
771		*
772	<	* @return true if the lock is currently held non-exclusively
772	>	* @return {@code true} if the lock is currently held non-exclusively
773		*/
774		public boolean isReadLocked() {
775		return (state & RBITS) != 0L;
776		}
777
778	<	private void readObject(java.io.ObjectInputStream s)
779	<	throws java.io.IOException, ClassNotFoundException {
780	<	s.defaultReadObject();
781	<	state = ORIGIN; // reset to unlocked state
778	>	/**
779	>	* Queries the number of read locks held for this lock. This
780	>	* method is designed for use in monitoring system state, not for
781	>	* synchronization control.
782	>	* @return the number of read locks held
783	>	*/
784	>	public int getReadLockCount() {
785	>	return getReadLockCount(state);
786		}
787
788		/**
789	+	* Returns a string identifying this lock, as well as its lock
790	+	* state.  The state, in brackets, includes the String {@code
791	+	* "Unlocked"} or the String {@code "Write-locked"} or the String
792	+	* {@code "Read-locks:"} followed by the current number of
793	+	* read-locks held.
794	+	*
795	+	* @return a string identifying this lock, as well as its lock state
796	+	*/
797	+	public String toString() {
798	+	long s = state;
799	+	return super.toString() +
800	+	((s & ABITS) == 0L ? "[Unlocked]" :
801	+	(s & WBIT) != 0L ? "[Write-locked]" :
802	+	"[Read-locks:" + getReadLockCount(s) + "]");
803	+	}
804	+
805	+	// views
806	+
807	+	/**
808		* Returns a plain {@link Lock} view of this StampedLock in which
809		* the {@link Lock#lock} method is mapped to {@link #readLock},
810		* and similarly for other methods. The returned Lock does not
#	Line 882 | Line 918 | public class StampedLock implements java
918		}
919		}
920
921	+	private void readObject(java.io.ObjectInputStream s)
922	+	throws java.io.IOException, ClassNotFoundException {
923	+	s.defaultReadObject();
924	+	state = ORIGIN; // reset to unlocked state
925	+	}
926	+
927		// internals
928
929		/**
#	Line 889 | Line 931 | public class StampedLock implements java
931		* access bits value to RBITS, indicating hold of spinlock,
932		* then updating, then releasing.
933		*
934	<	* @param s, assumed that (s & ABITS) >= RFULL
934	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
935		* @return new stamp on success, else zero
936		*/
937		private long tryIncReaderOverflow(long s) {
938	+	// assert (s & ABITS) >= RFULL;
939		if ((s & ABITS) == RFULL) {
940		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
941		++readerOverflow;
#	Line 909 | Line 952 | public class StampedLock implements java
952		/**
953		* Tries to decrement readerOverflow.
954		*
955	<	* @param s, assumed that (s & ABITS) >= RFULL
955	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
956		* @return new stamp on success, else zero
957		*/
958		private long tryDecReaderOverflow(long s) {
959	+	// assert (s & ABITS) >= RFULL;
960		if ((s & ABITS) == RFULL) {
961		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
962		int r; long next;
#	Line 932 | Line 976 | public class StampedLock implements java
976		return 0L;
977		}
978
979	<	/*
979	>	/**
980		* Wakes up the successor of h (normally whead). This is normally
981		* just h.next, but may require traversal from wtail if next
982		* pointers are lagging. This may fail to wake up an acquiring
#	Line 948 | Line 992 | public class StampedLock implements java
992		if (t.status <= 0)
993		q = t;
994		}
995	<	if (q != null) {
996	<	for (WNode r = q;;) {  // release co-waiters too
953	<	if ((w = r.thread) != null) {
954	<	r.thread = null;
955	<	U.unpark(w);
956	<	}
957	<	if ((r = q.cowait) == null)
958	<	break;
959	<	U.compareAndSwapObject(q, WCOWAIT, r, r.cowait);
960	<	}
961	<	}
995	>	if (q != null && (w = q.thread) != null)
996	>	U.unpark(w);
997		}
998		}
999
#	Line 974 | Line 1009 | public class StampedLock implements java
1009		private long acquireWrite(boolean interruptible, long deadline) {
1010		WNode node = null, p;
1011		for (int spins = -1;;) { // spin while enqueuing
1012	<	long s, ns;
1013	<	if (((s = state) & ABITS) == 0L) {
1012	>	long m, s, ns;
1013	>	if ((m = (s = state) & ABITS) == 0L) {
1014		if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
1015		return ns;
1016		}
1017	+	else if (spins < 0)
1018	+	spins = (m == WBIT && wtail == whead) ? SPINS : 0;
1019		else if (spins > 0) {
1020		if (ThreadLocalRandom.current().nextInt() >= 0)
1021		--spins;
1022		}
1023		else if ((p = wtail) == null) { // initialize queue
1024	<	WNode h = new WNode(WMODE, null);
1025	<	if (U.compareAndSwapObject(this, WHEAD, null, h))
1026	<	wtail = h;
1024	>	WNode hd = new WNode(WMODE, null);
1025	>	if (U.compareAndSwapObject(this, WHEAD, null, hd))
1026	>	wtail = hd;
1027		}
991	–	else if (spins < 0)
992	–	spins = (p == whead) ? SPINS : 0;
1028		else if (node == null)
1029		node = new WNode(WMODE, p);
1030		else if (node.prev != p)
#	Line 1000 | Line 1035 | public class StampedLock implements java
1035		}
1036		}
1037
1038	<	for (int spins = SPINS;;) {
1039	<	WNode np, pp; int ps; long s, ns; Thread w;
1040	<	while ((np = node.prev) != p && np != null)
1041	<	(p = np).next = node;   // stale
1042	<	if (whead == p) {
1038	>	for (int spins = -1;;) {
1039	>	WNode h, np, pp; int ps;
1040	>	if ((h = whead) == p) {
1041	>	if (spins < 0)
1042	>	spins = HEAD_SPINS;
1043	>	else if (spins < MAX_HEAD_SPINS)
1044	>	spins <<= 1;
1045		for (int k = spins;;) { // spin at head
1046	+	long s, ns;
1047		if (((s = state) & ABITS) == 0L) {
1048	<	if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1048	>	if (U.compareAndSwapLong(this, STATE, s,
1049	>	ns = s + WBIT)) {
1050		whead = node;
1051		node.prev = null;
1052		return ns;
#	Line 1017 | Line 1056 | public class StampedLock implements java
1056		--k <= 0)
1057		break;
1058		}
1020	–	if (spins < MAX_HEAD_SPINS)
1021	–	spins <<= 1;
1059		}
1060	<	if ((ps = p.status) == 0)
1061	<	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1062	<	else if (ps == CANCELLED) {
1063	<	if ((pp = p.prev) != null) {
1064	<	node.prev = pp;
1065	<	pp.next = node;
1060	>	else if (h != null) { // help release stale waiters
1061	>	WNode c; Thread w;
1062	>	while ((c = h.cowait) != null) {
1063	>	if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
1064	>	(w = c.thread) != null)
1065	>	U.unpark(w);
1066		}
1067		}
1068	<	else {
1069	<	long time; // 0 argument to park means no timeout
1070	<	if (deadline == 0L)
1071	<	time = 0L;
1072	<	else if ((time = deadline - System.nanoTime()) <= 0L)
1073	<	return cancelWaiter(node, null, false);
1074	<	node.thread = Thread.currentThread();
1075	<	if (node.prev == p && p.status == WAITING && // recheck
1076	<	(p != whead || (state & ABITS) != 0L))
1077	<	U.park(false, time);
1078	<	node.thread = null;
1079	<	if (interruptible && Thread.interrupted())
1080	<	return cancelWaiter(node, null, true);
1068	>	if (whead == h) {
1069	>	if ((np = node.prev) != p) {
1070	>	if (np != null)
1071	>	(p = np).next = node;   // stale
1072	>	}
1073	>	else if ((ps = p.status) == 0)
1074	>	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1075	>	else if (ps == CANCELLED) {
1076	>	if ((pp = p.prev) != null) {
1077	>	node.prev = pp;
1078	>	pp.next = node;
1079	>	}
1080	>	}
1081	>	else {
1082	>	long time; // 0 argument to park means no timeout
1083	>	if (deadline == 0L)
1084	>	time = 0L;
1085	>	else if ((time = deadline - System.nanoTime()) <= 0L)
1086	>	return cancelWaiter(node, node, false);
1087	>	Thread wt = Thread.currentThread();
1088	>	U.putObject(wt, PARKBLOCKER, this);
1089	>	node.thread = wt;
1090	>	if (p.status < 0 && (p != h || (state & ABITS) != 0L) &&
1091	>	whead == h && node.prev == p)
1092	>	U.park(false, time);  // emulate LockSupport.park
1093	>	node.thread = null;
1094	>	U.putObject(wt, PARKBLOCKER, null);
1095	>	if (interruptible && Thread.interrupted())
1096	>	return cancelWaiter(node, node, true);
1097	>	}
1098		}
1099		}
1100		}
#	Line 1055 | Line 1109 | public class StampedLock implements java
1109		* @return next state, or INTERRUPTED
1110		*/
1111		private long acquireRead(boolean interruptible, long deadline) {
1112	<	WNode node = null, group = null, p;
1112	>	WNode node = null, p;
1113		for (int spins = -1;;) {
1114	<	for (;;) {
1115	<	long s, m, ns; WNode h, q; Thread w; // anti-barging guard
1116	<	if (group == null && (h = whead) != null &&
1117	<	(q = h.next) != null && q.mode != RMODE)
1118	<	break;
1119	<	if ((m = (s = state) & ABITS) < RFULL ?
1120	<	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1121	<	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1122	<	if (group != null) {  // help release others
1123	<	for (WNode r = group;;) {
1124	<	if ((w = r.thread) != null) {
1125	<	r.thread = null;
1126	<	U.unpark(w);
1114	>	WNode h;
1115	>	if ((h = whead) == (p = wtail)) {
1116	>	for (long m, s, ns;;) {
1117	>	if ((m = (s = state) & ABITS) < RFULL ?
1118	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1119	>	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L))
1120	>	return ns;
1121	>	else if (m >= WBIT) {
1122	>	if (spins > 0) {
1123	>	if (ThreadLocalRandom.current().nextInt() >= 0)
1124	>	--spins;
1125	>	}
1126	>	else {
1127	>	if (spins == 0) {
1128	>	WNode nh = whead, np = wtail;
1129	>	if ((nh == h && np == p) || (h = nh) != (p = np))
1130	>	break;
1131		}
1132	<	if ((r = group.cowait) == null)
1075	<	break;
1076	<	U.compareAndSwapObject(group, WCOWAIT, r, r.cowait);
1132	>	spins = SPINS;
1133		}
1134		}
1079	–	return ns;
1135		}
1081	–	if (m >= WBIT)
1082	–	break;
1083	–	}
1084	–	if (spins > 0) {
1085	–	if (ThreadLocalRandom.current().nextInt() >= 0)
1086	–	--spins;
1136		}
1137	<	else if ((p = wtail) == null) {
1138	<	WNode h = new WNode(WMODE, null);
1139	<	if (U.compareAndSwapObject(this, WHEAD, null, h))
1140	<	wtail = h;
1137	>	if (p == null) { // initialize queue
1138	>	WNode hd = new WNode(WMODE, null);
1139	>	if (U.compareAndSwapObject(this, WHEAD, null, hd))
1140	>	wtail = hd;
1141		}
1093	–	else if (spins < 0)
1094	–	spins = (p == whead) ? SPINS : 0;
1142		else if (node == null)
1143	<	node = new WNode(WMODE, p);
1144	<	else if (node.prev != p)
1145	<	node.prev = p;
1146	<	else if (p.mode == RMODE && p != whead) {
1147	<	WNode pp = p.prev;  // become co-waiter with group p
1148	<	if (pp != null && p == wtail &&
1149	<	U.compareAndSwapObject(p, WCOWAIT,
1150	<	node.cowait = p.cowait, node)) {
1151	<	node.thread = Thread.currentThread();
1152	<	for (long time;;) {
1153	<	if (interruptible && Thread.interrupted())
1154	<	return cancelWaiter(node, p, true);
1143	>	node = new WNode(RMODE, p);
1144	>	else if (h == p || p.mode != RMODE) {
1145	>	if (node.prev != p)
1146	>	node.prev = p;
1147	>	else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
1148	>	p.next = node;
1149	>	break;
1150	>	}
1151	>	}
1152	>	else if (!U.compareAndSwapObject(p, WCOWAIT,
1153	>	node.cowait = p.cowait, node))
1154	>	node.cowait = null;
1155	>	else {
1156	>	for (;;) {
1157	>	WNode pp, c; Thread w;
1158	>	if ((h = whead) != null && (c = h.cowait) != null &&
1159	>	U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
1160	>	(w = c.thread) != null) // help release
1161	>	U.unpark(w);
1162	>	if (h == (pp = p.prev) || h == p || pp == null) {
1163	>	long m, s, ns;
1164	>	do {
1165	>	if ((m = (s = state) & ABITS) < RFULL ?
1166	>	U.compareAndSwapLong(this, STATE, s,
1167	>	ns = s + RUNIT) :
1168	>	(m < WBIT &&
1169	>	(ns = tryIncReaderOverflow(s)) != 0L))
1170	>	return ns;
1171	>	} while (m < WBIT);
1172	>	}
1173	>	if (whead == h && p.prev == pp) {
1174	>	long time;
1175	>	if (pp == null || h == p || p.status > 0) {
1176	>	node = null; // throw away
1177	>	break;
1178	>	}
1179		if (deadline == 0L)
1180		time = 0L;
1181		else if ((time = deadline - System.nanoTime()) <= 0L)
1182		return cancelWaiter(node, p, false);
1183	<	if (node.thread == null)
1184	<	break;
1185	<	if (p.prev != pp || p.status == CANCELLED ||
1186	<	p == whead || p.prev != pp) {
1187	<	node.thread = null;
1188	<	break;
1189	<	}
1190	<	if (node.thread == null) // must recheck
1191	<	break;
1192	<	U.park(false, time);
1183	>	Thread wt = Thread.currentThread();
1184	>	U.putObject(wt, PARKBLOCKER, this);
1185	>	node.thread = wt;
1186	>	if ((h != pp || (state & ABITS) == WBIT) &&
1187	>	whead == h && p.prev == pp)
1188	>	U.park(false, time);
1189	>	node.thread = null;
1190	>	U.putObject(wt, PARKBLOCKER, null);
1191	>	if (interruptible && Thread.interrupted())
1192	>	return cancelWaiter(node, p, true);
1193		}
1123	–	group = p;
1194		}
1125	–	node = null; // throw away
1126	–	}
1127	–	else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
1128	–	p.next = node;
1129	–	break;
1195		}
1196		}
1197
1198	<	for (int spins = SPINS;;) {
1199	<	WNode np, pp, r; int ps; long m, s, ns; Thread w;
1200	<	while ((np = node.prev) != p && np != null)
1201	<	(p = np).next = node;
1202	<	if (whead == p) {
1203	<	for (int k = spins;;) {
1204	<	if ((m = (s = state) & ABITS) != WBIT) {
1205	<	if (m < RFULL ?
1206	<	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT):
1207	<	(ns = tryIncReaderOverflow(s)) != 0L) {
1208	<	whead = node;
1209	<	node.prev = null;
1210	<	while ((r = node.cowait) != null) {
1211	<	if (U.compareAndSwapObject(node, WCOWAIT,
1212	<	r, r.cowait) &&
1213	<	(w = r.thread) != null) {
1214	<	r.thread = null;
1215	<	U.unpark(w); // release co-waiter
1216	<	}
1217	<	}
1153	<	return ns;
1198	>	for (int spins = -1;;) {
1199	>	WNode h, np, pp; int ps;
1200	>	if ((h = whead) == p) {
1201	>	if (spins < 0)
1202	>	spins = HEAD_SPINS;
1203	>	else if (spins < MAX_HEAD_SPINS)
1204	>	spins <<= 1;
1205	>	for (int k = spins;;) { // spin at head
1206	>	long m, s, ns;
1207	>	if ((m = (s = state) & ABITS) < RFULL ?
1208	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1209	>	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1210	>	WNode c; Thread w;
1211	>	whead = node;
1212	>	node.prev = null;
1213	>	while ((c = node.cowait) != null) {
1214	>	if (U.compareAndSwapObject(node, WCOWAIT,
1215	>	c, c.cowait) &&
1216	>	(w = c.thread) != null)
1217	>	U.unpark(w);
1218		}
1219	+	return ns;
1220		}
1221	<	else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1222	<	--k <= 0)
1221	>	else if (m >= WBIT &&
1222	>	ThreadLocalRandom.current().nextInt() >= 0 && --k <= 0)
1223		break;
1224		}
1160	–	if (spins < MAX_HEAD_SPINS)
1161	–	spins <<= 1;
1225		}
1226	<	if ((ps = p.status) == 0)
1227	<	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1228	<	else if (ps == CANCELLED) {
1229	<	if ((pp = p.prev) != null) {
1230	<	node.prev = pp;
1231	<	pp.next = node;
1226	>	else if (h != null) {
1227	>	WNode c; Thread w;
1228	>	while ((c = h.cowait) != null) {
1229	>	if (U.compareAndSwapObject(h, WCOWAIT, c, c.cowait) &&
1230	>	(w = c.thread) != null)
1231	>	U.unpark(w);
1232		}
1233		}
1234	<	else {
1235	<	long time;
1236	<	if (deadline == 0L)
1237	<	time = 0L;
1238	<	else if ((time = deadline - System.nanoTime()) <= 0L)
1239	<	return cancelWaiter(node, null, false);
1240	<	node.thread = Thread.currentThread();
1241	<	if (node.prev == p && p.status == WAITING &&
1242	<	(p != whead || (state & ABITS) != WBIT))
1243	<	U.park(false, time);
1244	<	node.thread = null;
1245	<	if (interruptible && Thread.interrupted())
1246	<	return cancelWaiter(node, null, true);
1234	>	if (whead == h) {
1235	>	if ((np = node.prev) != p) {
1236	>	if (np != null)
1237	>	(p = np).next = node;   // stale
1238	>	}
1239	>	else if ((ps = p.status) == 0)
1240	>	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1241	>	else if (ps == CANCELLED) {
1242	>	if ((pp = p.prev) != null) {
1243	>	node.prev = pp;
1244	>	pp.next = node;
1245	>	}
1246	>	}
1247	>	else {
1248	>	long time;
1249	>	if (deadline == 0L)
1250	>	time = 0L;
1251	>	else if ((time = deadline - System.nanoTime()) <= 0L)
1252	>	return cancelWaiter(node, node, false);
1253	>	Thread wt = Thread.currentThread();
1254	>	U.putObject(wt, PARKBLOCKER, this);
1255	>	node.thread = wt;
1256	>	if (p.status < 0 &&
1257	>	(p != h || (state & ABITS) == WBIT) &&
1258	>	whead == h && node.prev == p)
1259	>	U.park(false, time);
1260	>	node.thread = null;
1261	>	U.putObject(wt, PARKBLOCKER, null);
1262	>	if (interruptible && Thread.interrupted())
1263	>	return cancelWaiter(node, node, true);
1264	>	}
1265		}
1266		}
1267		}
1268
1269		/**
1270		* If node non-null, forces cancel status and unsplices it from
1271	<	* queue if possible and wakes up any cowaiters. This is a variant
1272	<	* of cancellation methods in AbstractQueuedSynchronizer (see its
1273	<	* detailed explanation in AQS internal documentation) that more
1274	<	* conservatively wakes up other threads that may have had their
1275	<	* links changed, so as to preserve liveness in the main
1276	<	* signalling methods.
1271	>	* queue if possible and wakes up any cowaiters (of the node, or
1272	>	* group, as applicable), and in any case helps release current
1273	>	* first waiter if lock is free. (Calling with null arguments
1274	>	* serves as a conditional form of release, which is not currently
1275	>	* needed but may be needed under possible future cancellation
1276	>	* policies). This is a variant of cancellation methods in
1277	>	* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1278	>	* internal documentation).
1279		*
1280		* @param node if nonnull, the waiter
1281	<	* @param group, if nonnull, the group current thread is cowaiting with
1281	>	* @param group either node or the group node is cowaiting with
1282		* @param interrupted if already interrupted
1283		* @return INTERRUPTED if interrupted or Thread.interrupted, else zero
1284		*/
1285		private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1286	<	if (node != null) {
1287	<	node.thread = null;
1286	>	if (node != null && group != null) {
1287	>	Thread w;
1288		node.status = CANCELLED;
1289	<	Thread w; // wake up co-waiters; unsplice cancelled ones
1290	<	for (WNode q, p = (group != null) ? group : node; p != null; ) {
1291	<	if ((q = p.cowait) == null)
1209	<	break;
1210	<	if ((w = q.thread) != null) {
1211	<	q.thread = null;
1212	<	U.unpark(w);
1213	<	}
1214	<	if (q.status == CANCELLED)
1289	>	// unsplice cancelled nodes from group
1290	>	for (WNode p = group, q; (q = p.cowait) != null;) {
1291	>	if (q.status == CANCELLED) {
1292		U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1293	+	p = group; // restart
1294	+	}
1295		else
1296		p = q;
1297		}
1298	<	if (group == null)  {        // unsplice both prev and next links
1299	<	for (WNode pred = node.prev; pred != null; ) {
1300	<	WNode succ, pp;      // first unsplice next
1298	>	if (group == node) {
1299	>	for (WNode r = group.cowait; r != null; r = r.cowait) {
1300	>	if ((w = r.thread) != null)
1301	>	U.unpark(w);       // wake up uncancelled co-waiters
1302	>	}
1303	>	for (WNode pred = node.prev; pred != null; ) { // unsplice
1304	>	WNode succ, pp;        // find valid successor
1305		while ((succ = node.next) == null ||
1306		succ.status == CANCELLED) {
1307	<	WNode q = null;  // find successor the slow way
1307	>	WNode q = null;    // find successor the slow way
1308		for (WNode t = wtail; t != null && t != node; t = t.prev)
1309		if (t.status != CANCELLED)
1310	<	q = t;   // don't link if succ cancelled
1311	<	if (succ == q || // ensure accurate successor
1310	>	q = t;     // don't link if succ cancelled
1311	>	if (succ == q ||   // ensure accurate successor
1312		U.compareAndSwapObject(node, WNEXT,
1313		succ, succ = q)) {
1314		if (succ == null && node == wtail)
#	Line 1237 | Line 1320 | public class StampedLock implements java
1320		U.compareAndSwapObject(pred, WNEXT, node, succ);
1321		if (succ != null && (w = succ.thread) != null) {
1322		succ.thread = null;
1323	<	U.unpark(w);      // conservatively wake up new succ
1323	>	U.unpark(w);       // wake up succ to observe new pred
1324		}
1325		if (pred.status != CANCELLED || (pp = pred.prev) == null)
1326		break;
1327	<	node.prev = pp; // repeat in case new pred wrong/cancelled
1327	>	node.prev = pp;        // repeat if new pred wrong/cancelled
1328		U.compareAndSwapObject(pp, WNEXT, pred, succ);
1329		pred = pp;
1330		}
1331		}
1332		}
1333	<	release(whead);
1333	>	WNode h; // Possibly release first waiter
1334	>	while ((h = whead) != null) {
1335	>	long s; WNode q; // similar to release() but check eligibility
1336	>	if ((q = h.next) == null || q.status == CANCELLED) {
1337	>	for (WNode t = wtail; t != null && t != h; t = t.prev)
1338	>	if (t.status <= 0)
1339	>	q = t;
1340	>	}
1341	>	if (h == whead) {
1342	>	if (q != null && h.status == 0 &&
1343	>	((s = state) & ABITS) != WBIT && // waiter is eligible
1344	>	(s == 0L || q.mode == RMODE))
1345	>	release(h);
1346	>	break;
1347	>	}
1348	>	}
1349		return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1350		}
1351
#	Line 1259 | Line 1357 | public class StampedLock implements java
1357		private static final long WNEXT;
1358		private static final long WSTATUS;
1359		private static final long WCOWAIT;
1360	+	private static final long PARKBLOCKER;
1361
1362		static {
1363		try {
#	Line 1277 | Line 1376 | public class StampedLock implements java
1376		(wk.getDeclaredField("next"));
1377		WCOWAIT = U.objectFieldOffset
1378		(wk.getDeclaredField("cowait"));
1379	+	Class<?> tk = Thread.class;
1380	+	PARKBLOCKER = U.objectFieldOffset
1381	+	(tk.getDeclaredField("parkBlocker"));
1382
1383		} catch (Exception e) {
1384		throw new Error(e);

Diff Legend

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