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.31 by dl, Thu Jan 24 21:35:03 2013 UTC vs.
Revision 1.39 by jsr166, Sun Jan 18 20:17:33 2015 UTC

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

Diff Legend

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