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.12 by jsr166, Sat Oct 13 23:05:13 2012 UTC vs.
Revision 1.37 by jsr166, Sun Jul 14 19:55:05 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;
11	+	import java.util.concurrent.locks.ReadWriteLock;
12	+	import java.util.concurrent.locks.LockSupport;
13
14		/**
15		* A capability-based lock with three modes for controlling read/write
#	Line 36 | Line 38 | import java.util.concurrent.TimeUnit;
38		*  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
39		*   returns a non-zero stamp only if the lock is not currently held
40		*   in write mode. Method {@link #validate} returns true if the lock
41	<	*   has not since been acquired in write mode. This mode can be
42	<	*   thought of as an extremely weak version of a read-lock, that can
43	<	*   be broken by a writer at any time.  The use of optimistic mode
44	<	*   for short read-only code segments often reduces contention and
45	<	*   improves throughput.  However, its use is inherently fragile.
46	<	*   Optimistic read sections should only read fields and hold them in
47	<	*   local variables for later use after validation. Fields read while
48	<	*   in optimistic mode may be wildly inconsistent, so usage applies
49	<	*   only when you are familiar enough with data representations to
50	<	*   check consistency and/or repeatedly invoke method {@code
51	<	*   validate()}.  For example, such steps are typically required when
52	<	*   first reading an object or array reference, and then accessing
53	<	*   one of its fields, elements or methods. </li>
41	>	*   has not been acquired in write mode since obtaining a given
42	>	*   stamp.  This mode can be thought of as an extremely weak version
43	>	*   of a read-lock, that can be broken by a writer at any time.  The
44	>	*   use of optimistic mode for short read-only code segments often
45	>	*   reduces contention and improves throughput.  However, its use is
46	>	*   inherently fragile.  Optimistic read sections should only read
47	>	*   fields and hold them in local variables for later use after
48	>	*   validation. Fields read while in optimistic mode may be wildly
49	>	*   inconsistent, so usage applies only when you are familiar enough
50	>	*   with data representations to check consistency and/or repeatedly
51	>	*   invoke method {@code validate()}.  For example, such steps are
52	>	*   typically required when first reading an object or array
53	>	*   reference, and then accessing one of its fields, elements or
54	>	*   methods. </li>
55		*
56		* </ul>
57		*
#	Line 61 | Line 64 | import java.util.concurrent.TimeUnit;
64		* help reduce some of the code bloat that otherwise occurs in
65		* retry-based designs.
66		*
67	<	* <p>StampedLocks are designed for use in a different (and generally
68	<	* narrower) range of contexts than most other locks: They are not
69	<	* reentrant, so locked bodies should not call other unknown methods
70	<	* that may try to re-acquire locks (although you may pass a stamp to
71	<	* other methods that can use or convert it). Unvalidated optimistic
72	<	* read sections should further not call methods that are not known to
67	>	* <p>StampedLocks are designed for use as internal utilities in the
68	>	* development of thread-safe components. Their use relies on
69	>	* knowledge of the internal properties of the data, objects, and
70	>	* methods they are protecting.  They are not reentrant, so locked
71	>	* bodies should not call other unknown methods that may try to
72	>	* re-acquire locks (although you may pass a stamp to other methods
73	>	* that can use or convert it).  The use of read lock modes relies on
74	>	* the associated code sections being side-effect-free.  Unvalidated
75	>	* optimistic read sections cannot call methods that are not known to
76		* tolerate potential inconsistencies.  Stamps use finite
77		* representations, and are not cryptographically secure (i.e., a
78		* valid stamp may be guessable). Stamp values may recycle after (no
#	Line 77 | Line 83 | import java.util.concurrent.TimeUnit;
83		* locking.
84		*
85		* <p>The scheduling policy of StampedLock does not consistently
86	<	* prefer readers over writers or vice versa.  A zero return from any
87	<	* "try" method for acquiring or converting locks does not carry any
88	<	* information about the state of the lock; a subsequent invocation
89	<	* may succeed.
86	>	* prefer readers over writers or vice versa.  All "try" methods are
87	>	* best-effort and do not necessarily conform to any scheduling or
88	>	* fairness policy. A zero return from any "try" method for acquiring
89	>	* or converting locks does not carry any information about the state
90	>	* of the lock; a subsequent invocation may succeed.
91	>	*
92	>	* <p>Because it supports coordinated usage across multiple lock
93	>	* modes, this class does not directly implement the {@link Lock} or
94	>	* {@link ReadWriteLock} interfaces. However, a StampedLock may be
95	>	* viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link
96	>	* #asReadWriteLock()} in applications requiring only the associated
97	>	* set of functionality.
98		*
99		* <p><b>Sample Usage.</b> The following illustrates some usage idioms
100		* in a class that maintains simple two-dimensional points. The sample
#	Line 103 | Line 117 | import java.util.concurrent.TimeUnit;
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;
117	<	*       double currentY = y;
118	<	*         return Math.sqrt(currentX * currentX + currentY * currentY);
119	<	*     } finally {
120	<	*       sl.unlockRead(stamp);
121	<	*     }
122	<	*   }
123	<	*
124	<	*   double distanceFromOriginV2() { // combines code paths
125	<	*     for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
126	<	*       double currentX, currentY;
127	<	*       try {
128	<	*         currentX = x;
129	<	*         currentY = y;
130	<	*       } finally {
131	<	*         if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
132	<	*           return Math.sqrt(currentX * currentX + currentY * currentY);
133	<	*       }
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		*   }
134		*
135		*   void moveIfAtOrigin(double newX, double newY) { // upgrade
#	Line 139 | Line 137 | import java.util.concurrent.TimeUnit;
137		*     long stamp = sl.readLock();
138		*     try {
139		*       while (x == 0.0 && y == 0.0) {
140	<	*         long ws = tryConvertToWriteLock(stamp);
140	>	*         long ws = sl.tryConvertToWriteLock(stamp);
141		*         if (ws != 0L) {
142		*           stamp = ws;
143		*           x = newX;
#	Line 152 | Line 150 | import java.util.concurrent.TimeUnit;
150		*         }
151		*       }
152		*     } finally {
153	<	*        sl.unlock(stamp);
153	>	*       sl.unlock(stamp);
154		*     }
155		*   }
156		* }}</pre>
#	Line 169 | Line 167 | public class StampedLock implements java
167		* http://www.lameter.com/gelato2005.pdf
168		* and elsewhere; see
169		* Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)
170	<	* Ordered RW locks (see Shirako et al
170	>	* and Ordered RW locks (see Shirako et al
171		* http://dl.acm.org/citation.cfm?id=2312015)
174	–	* and Phase-Fair locks (see Brandenburg & Anderson, especially
175	–	* http://www.cs.unc.edu/~bbb/diss/).
172		*
173		* Conceptually, the primary state of the lock includes a sequence
174		* number that is odd when write-locked and even otherwise.
#	Line 180 | Line 176 | public class StampedLock implements java
176		* read-locked.  The read count is ignored when validating
177		* "optimistic" seqlock-reader-style stamps.  Because we must use
178		* a small finite number of bits (currently 7) for readers, a
179	<	* supplementary reader overflow word is used when then number of
179	>	* supplementary reader overflow word is used when the number of
180		* readers exceeds the count field. We do this by treating the max
181		* reader count value (RBITS) as a spinlock protecting overflow
182		* updates.
183		*
184	<	* Waiting readers and writers use different queues. The writer
185	<	* queue is a modified form of CLH lock.  (For discussion of CLH,
186	<	* see the internal documentation of AbstractQueuedSynchronizer.)
187	<	* The reader "queue" is a form of Treiber stack, that supports
188	<	* simpler/faster operations because order within a queue doesn't
189	<	* matter and all are signalled at once.  However the sequence of
190	<	* threads within the queue vs the current stamp does matter (see
191	<	* Shirako et al) so each carries its incoming stamp value.
192	<	* Waiting writers never need to track sequence values, so they
193	<	* don't.
194	<	*
195	<	* These queue mechanics hardwire the scheduling policy.  Ignoring
196	<	* trylocks, cancellation, and spinning, they implement Phase-Fair
197	<	* preferences:
198	<	*   1. Unlocked writers prefer to signal waiting readers
199	<	*   2. Fully unlocked readers prefer to signal waiting writers
204	<	*   3. When read-locked and a waiting writer exists, the writer
205	<	*      is preferred to incoming readers
184	>	* Waiters use a modified form of CLH lock used in
185	>	* AbstractQueuedSynchronizer (see its internal documentation for
186	>	* a fuller account), where each node is tagged (field mode) as
187	>	* either a reader or writer. Sets of waiting readers are grouped
188	>	* (linked) under a common node (field cowait) so act as a single
189	>	* node with respect to most CLH mechanics.  By virtue of the
190	>	* queue structure, wait nodes need not actually carry sequence
191	>	* numbers; we know each is greater than its predecessor.  This
192	>	* simplifies the scheduling policy to a mainly-FIFO scheme that
193	>	* incorporates elements of Phase-Fair locks (see Brandenburg &
194	>	* Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
195	>	* particular, we use the phase-fair anti-barging rule: If an
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.)
200		*
201		* These rules apply to threads actually queued. All tryLock forms
202		* opportunistically try to acquire locks regardless of preference
203	<	* rules, and so may "barge" their way in.  Additionally, initial
204	<	* phases of the await* methods (invoked from readLock() and
205	<	* writeLock()) use controlled spins that have similar effect.
206	<	* Phase-fair preferences may also be broken on cancellations due
207	<	* to timeouts and interrupts.  Rule #3 (incoming readers when a
208	<	* waiting writer) is approximated with varying precision in
209	<	* different contexts -- some checks do not account for
210	<	* in-progress spins/signals, and others do not account for
211	<	* cancellations.
212	<	*
213	<	* Controlled, randomized spinning is used in the two await
214	<	* methods to reduce (increasingly expensive) context switching
215	<	* while also avoiding sustained memory thrashing among many
216	<	* threads.  Both await methods use a similar spin strategy: If
217	<	* the associated queue appears to be empty, then the thread
218	<	* spin-waits up to SPINS times (where each iteration decreases
225	<	* spin count with 50% probablility) before enqueing, and then, if
226	<	* it is the first thread to be enqueued, spins again up to SPINS
227	<	* times before blocking. If, upon wakening it fails to obtain
228	<	* lock, and is still (or becomes) the first waiting thread (which
229	<	* indicates that some other thread barged and obtained lock), it
230	<	* escalates spins (up to MAX_HEAD_SPINS) to reduce the likelihood
231	<	* of continually losing to barging threads.
203	>	* rules, and so may "barge" their way in.  Randomized spinning is
204	>	* used in the acquire methods to reduce (increasingly expensive)
205	>	* context switching while also avoiding sustained memory
206	>	* thrashing among many threads.  We limit spins to the head of
207	>	* queue. A thread spin-waits up to SPINS times (where each
208	>	* iteration decreases spin count with 50% probability) before
209	>	* blocking. If, upon wakening it fails to obtain lock, and is
210	>	* still (or becomes) the first waiting thread (which indicates
211	>	* that some other thread barged and obtained lock), it escalates
212	>	* spins (up to MAX_HEAD_SPINS) to reduce the likelihood of
213	>	* continually losing to barging threads.
214	>	*
215	>	* Nearly all of these mechanics are carried out in methods
216	>	* acquireWrite and acquireRead, that, as typical of such code,
217	>	* sprawl out because actions and retries rely on consistent sets
218	>	* of locally cached reads.
219		*
220		* As noted in Boehm's paper (above), sequence validation (mainly
221		* method validate()) requires stricter ordering rules than apply
#	Line 248 | Line 235 | public class StampedLock implements java
235		* be subject to future improvements.
236		*/
237
238	+	private static final long serialVersionUID = -6001602636862214147L;
239	+
240		/** Number of processors, for spin control */
241		private static final int NCPU = Runtime.getRuntime().availableProcessors();
242
243		/** Maximum number of retries before blocking on acquisition */
244	<	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1;
244	>	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;
245
246		/** Maximum number of retries before re-blocking */
247	<	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1;
247	>	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 0;
248
249		/** The period for yielding when waiting for overflow spinlock */
250		private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
251
252		/** The number of bits to use for reader count before overflowing */
253	<	private static final int  LG_READERS = 7;
253	>	private static final int LG_READERS = 7;
254
255		// Values for lock state and stamp operations
256		private static final long RUNIT = 1L;
#	Line 274 | Line 263 | public class StampedLock implements java
263		// Initial value for lock state; avoid failure value zero
264		private static final long ORIGIN = WBIT << 1;
265
266	<	// Special value from cancelled await methods so caller can throw IE
266	>	// Special value from cancelled acquire methods so caller can throw IE
267		private static final long INTERRUPTED = 1L;
268
269	<	// Values for writer status; order matters
269	>	// Values for node status; order matters
270		private static final int WAITING   = -1;
271		private static final int CANCELLED =  1;
272
273	<	/** Wait nodes for readers */
274	<	static final class RNode {
275	<	final long seq;         // stamp value upon enqueue
287	<	volatile Thread waiter; // null if no longer waiting
288	<	volatile RNode next;
289	<	RNode(long s, Thread w) { seq = s; waiter = w; }
290	<	}
273	>	// Modes for nodes (int not boolean to allow arithmetic)
274	>	private static final int RMODE = 0;
275	>	private static final int WMODE = 1;
276
277	<	/** Wait nodes for writers */
277	>	/** Wait nodes */
278		static final class WNode {
294	–	volatile int status;   // 0, WAITING, or CANCELLED
279		volatile WNode prev;
280		volatile WNode next;
281	<	volatile Thread thread;
282	<	WNode(Thread t, WNode p) { thread = t; prev = p; }
281	>	volatile WNode cowait;    // list of linked readers
282	>	volatile Thread thread;   // non-null while possibly parked
283	>	volatile int status;      // 0, WAITING, or CANCELLED
284	>	final int mode;           // RMODE or WMODE
285	>	WNode(int m, WNode p) { mode = m; prev = p; }
286		}
287
288	<	/** Head of writer CLH queue */
288	>	/** Head of CLH queue */
289		private transient volatile WNode whead;
290	<	/** Tail (last) of writer CLH queue */
290	>	/** Tail (last) of CLH queue */
291		private transient volatile WNode wtail;
292	<	/** Head of read queue  */
293	<	private transient volatile RNode rhead;
294	<	/** The state of the lock -- high bits hold sequence, low bits read count */
292	>
293	>	// views
294	>	transient ReadLockView readLockView;
295	>	transient WriteLockView writeLockView;
296	>	transient ReadWriteLockView readWriteLockView;
297	>
298	>	/** Lock sequence/state */
299		private transient volatile long state;
300		/** extra reader count when state read count saturated */
301		private transient int readerOverflow;
302
303		/**
304	<	* Creates a new lock initially in unlocked state.
304	>	* Creates a new lock, initially in unlocked state.
305		*/
306		public StampedLock() {
307		state = ORIGIN;
#	Line 323 | Line 314 | public class StampedLock implements java
314		* @return a stamp that can be used to unlock or convert mode
315		*/
316		public long writeLock() {
317	<	long s, next;
318	<	if (((s = state) & ABITS) == 0L &&
319	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
320	<	return next;
330	<	return awaitWrite(false, 0L);
317	>	long s, next;  // bypass acquireWrite in fully unlocked case only
318	>	return ((((s = state) & ABITS) == 0L &&
319	>	U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
320	>	next : acquireWrite(false, 0L));
321		}
322
323		/**
324		* Exclusively acquires the lock if it is immediately available.
325		*
326		* @return a stamp that can be used to unlock or convert mode,
327	<	* or zero if the lock is not available.
327	>	* or zero if the lock is not available
328		*/
329		public long tryWriteLock() {
330		long s, next;
331	<	if (((s = state) & ABITS) == 0L &&
332	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
333	<	return next;
344	<	return 0L;
331	>	return ((((s = state) & ABITS) == 0L &&
332	>	U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
333	>	next : 0L);
334		}
335
336		/**
337		* Exclusively acquires the lock if it is available within the
338		* given time and the current thread has not been interrupted.
339	+	* Behavior under timeout and interruption matches that specified
340	+	* for method {@link Lock#tryLock(long,TimeUnit)}.
341		*
342	+	* @param time the maximum time to wait for the lock
343	+	* @param unit the time unit of the {@code time} argument
344		* @return a stamp that can be used to unlock or convert mode,
345		* or zero if the lock is not available
346		* @throws InterruptedException if the current thread is interrupted
#	Line 357 | Line 350 | public class StampedLock implements java
350		throws InterruptedException {
351		long nanos = unit.toNanos(time);
352		if (!Thread.interrupted()) {
353	<	long s, next, deadline;
354	<	if (((s = state) & ABITS) == 0L &&
362	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
353	>	long next, deadline;
354	>	if ((next = tryWriteLock()) != 0L)
355		return next;
356		if (nanos <= 0L)
357		return 0L;
358		if ((deadline = System.nanoTime() + nanos) == 0L)
359		deadline = 1L;
360	<	if ((next = awaitWrite(true, deadline)) != INTERRUPTED)
360	>	if ((next = acquireWrite(true, deadline)) != INTERRUPTED)
361		return next;
362		}
363		throw new InterruptedException();
#	Line 374 | Line 366 | public class StampedLock implements java
366		/**
367		* Exclusively acquires the lock, blocking if necessary
368		* until available or the current thread is interrupted.
369	+	* Behavior under interruption matches that specified
370	+	* for method {@link Lock#lockInterruptibly()}.
371		*
372		* @return a stamp that can be used to unlock or convert mode
373		* @throws InterruptedException if the current thread is interrupted
374		* before acquiring the lock
375		*/
376		public long writeLockInterruptibly() throws InterruptedException {
377	<	if (!Thread.interrupted()) {
378	<	long s, next;
379	<	if (((s = state) & ABITS) == 0L &&
380	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
387	<	return next;
388	<	if ((next = awaitWrite(true, 0L)) != INTERRUPTED)
389	<	return next;
390	<	}
377	>	long next;
378	>	if (!Thread.interrupted() &&
379	>	(next = acquireWrite(true, 0L)) != INTERRUPTED)
380	>	return next;
381		throw new InterruptedException();
382		}
383
#	Line 398 | Line 388 | public class StampedLock implements java
388		* @return a stamp that can be used to unlock or convert mode
389		*/
390		public long readLock() {
391	<	for (;;) {
392	<	long s, m, next;
393	<	if ((m = (s = state) & ABITS) == 0L ||
394	<	(m < WBIT && whead == wtail)) {
405	<	if (m < RFULL) {
406	<	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
407	<	return next;
408	<	}
409	<	else if ((next = tryIncReaderOverflow(s)) != 0L)
410	<	return next;
411	<	}
412	<	else
413	<	return awaitRead(s, false, 0L);
414	<	}
391	>	long s, next;  // bypass acquireRead on fully unlocked case only
392	>	return ((((s = state) & ABITS) == 0L &&
393	>	U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
394	>	next : acquireRead(false, 0L));
395		}
396
397		/**
#	Line 437 | Line 417 | public class StampedLock implements java
417		/**
418		* Non-exclusively acquires the lock if it is available within the
419		* given time and the current thread has not been interrupted.
420	+	* Behavior under timeout and interruption matches that specified
421	+	* for method {@link Lock#tryLock(long,TimeUnit)}.
422		*
423	+	* @param time the maximum time to wait for the lock
424	+	* @param unit the time unit of the {@code time} argument
425		* @return a stamp that can be used to unlock or convert mode,
426		* or zero if the lock is not available
427		* @throws InterruptedException if the current thread is interrupted
#	Line 445 | Line 429 | public class StampedLock implements java
429		*/
430		public long tryReadLock(long time, TimeUnit unit)
431		throws InterruptedException {
432	+	long s, m, next, deadline;
433		long nanos = unit.toNanos(time);
434		if (!Thread.interrupted()) {
435	<	for (;;) {
436	<	long s, m, next, deadline;
452	<	if ((m = (s = state) & ABITS) == WBIT ||
453	<	(m != 0L && whead != wtail)) {
454	<	if (nanos <= 0L)
455	<	return 0L;
456	<	if ((deadline = System.nanoTime() + nanos) == 0L)
457	<	deadline = 1L;
458	<	if ((next = awaitRead(s, true, deadline)) != INTERRUPTED)
459	<	return next;
460	<	break;
461	<	}
462	<	else if (m < RFULL) {
435	>	if ((m = (s = state) & ABITS) != WBIT) {
436	>	if (m < RFULL) {
437		if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
438		return next;
439		}
440		else if ((next = tryIncReaderOverflow(s)) != 0L)
441		return next;
442		}
443	+	if (nanos <= 0L)
444	+	return 0L;
445	+	if ((deadline = System.nanoTime() + nanos) == 0L)
446	+	deadline = 1L;
447	+	if ((next = acquireRead(true, deadline)) != INTERRUPTED)
448	+	return next;
449		}
450		throw new InterruptedException();
451		}
#	Line 473 | Line 453 | public class StampedLock implements java
453		/**
454		* Non-exclusively acquires the lock, blocking if necessary
455		* until available or the current thread is interrupted.
456	+	* Behavior under interruption matches that specified
457	+	* for method {@link Lock#lockInterruptibly()}.
458		*
459		* @return a stamp that can be used to unlock or convert mode
460		* @throws InterruptedException if the current thread is interrupted
461		* before acquiring the lock
462		*/
463		public long readLockInterruptibly() throws InterruptedException {
464	<	if (!Thread.interrupted()) {
465	<	for (;;) {
466	<	long s, next, m;
467	<	if ((m = (s = state) & ABITS) == WBIT ||
486	<	(m != 0L && whead != wtail)) {
487	<	if ((next = awaitRead(s, true, 0L)) != INTERRUPTED)
488	<	return next;
489	<	break;
490	<	}
491	<	else if (m < RFULL) {
492	<	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
493	<	return next;
494	<	}
495	<	else if ((next = tryIncReaderOverflow(s)) != 0L)
496	<	return next;
497	<	}
498	<	}
464	>	long next;
465	>	if (!Thread.interrupted() &&
466	>	(next = acquireRead(true, 0L)) != INTERRUPTED)
467	>	return next;
468		throw new InterruptedException();
469		}
470
#	Line 511 | Line 480 | public class StampedLock implements java
480		}
481
482		/**
483	<	* Returns true if the lock has not been exclusively held since
484	<	* issuance of the given stamp. Always returns false if the stamp
485	<	* is zero. Always returns true if the stamp represents a
486	<	* currently held lock.
483	>	* Returns true if the lock has not been exclusively acquired
484	>	* since issuance of the given stamp. Always returns false if the
485	>	* stamp is zero. Always returns true if the stamp represents a
486	>	* currently held lock. Invoking this method with a value not
487	>	* obtained from {@link #tryOptimisticRead} or a locking method
488	>	* for this lock has no defined effect or result.
489		*
490	<	* @return true if the lock has not been exclusively held since
491	<	* issuance of the given stamp; else false
490	>	* @param stamp a stamp
491	>	* @return {@code true} if the lock has not been exclusively acquired
492	>	* since issuance of the given stamp; else false
493		*/
494		public boolean validate(long stamp) {
495	+	// See above about current use of getLongVolatile here
496		return (stamp & SBITS) == (U.getLongVolatile(this, STATE) & SBITS);
497		}
498
#	Line 532 | Line 505 | public class StampedLock implements java
505		* not match the current state of this lock
506		*/
507		public void unlockWrite(long stamp) {
508	+	WNode h;
509		if (state != stamp || (stamp & WBIT) == 0L)
510		throw new IllegalMonitorStateException();
511		state = (stamp += WBIT) == 0L ? ORIGIN : stamp;
512	<	readerPrefSignal();
512	>	if ((h = whead) != null && h.status != 0)
513	>	release(h);
514		}
515
516		/**
#	Line 547 | Line 522 | public class StampedLock implements java
522		* not match the current state of this lock
523		*/
524		public void unlockRead(long stamp) {
525	<	long s, m;
526	<	if ((stamp & RBITS) != 0L) {
527	<	while (((s = state) & SBITS) == (stamp & SBITS)) {
528	<	if ((m = s & ABITS) == 0L)
525	>	long s, m; WNode h;
526	>	for (;;) {
527	>	if (((s = state) & SBITS) != (stamp & SBITS) ||
528	>	(stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
529	>	throw new IllegalMonitorStateException();
530	>	if (m < RFULL) {
531	>	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
532	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
533	>	release(h);
534		break;
555	–	else if (m < RFULL) {
556	–	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
557	–	if (m == RUNIT)
558	–	writerPrefSignal();
559	–	return;
560	–	}
535		}
562	–	else if (m >= WBIT)
563	–	break;
564	–	else if (tryDecReaderOverflow(s) != 0L)
565	–	return;
536		}
537	+	else if (tryDecReaderOverflow(s) != 0L)
538	+	break;
539		}
568	–	throw new IllegalMonitorStateException();
540		}
541
542		/**
#	Line 577 | Line 548 | public class StampedLock implements java
548		* not match the current state of this lock
549		*/
550		public void unlock(long stamp) {
551	<	long a = stamp & ABITS, m, s;
551	>	long a = stamp & ABITS, m, s; WNode h;
552		while (((s = state) & SBITS) == (stamp & SBITS)) {
553		if ((m = s & ABITS) == 0L)
554		break;
#	Line 585 | Line 556 | public class StampedLock implements java
556		if (a != m)
557		break;
558		state = (s += WBIT) == 0L ? ORIGIN : s;
559	<	readerPrefSignal();
559	>	if ((h = whead) != null && h.status != 0)
560	>	release(h);
561		return;
562		}
563		else if (a == 0L || a >= WBIT)
564		break;
565		else if (m < RFULL) {
566		if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
567	<	if (m == RUNIT)
568	<	writerPrefSignal();
567	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
568	>	release(h);
569		return;
570		}
571		}
#	Line 604 | Line 576 | public class StampedLock implements java
576		}
577
578		/**
579	<	* If the lock state matches the given stamp then performs one of
579	>	* If the lock state matches the given stamp, performs one of
580		* the following actions. If the stamp represents holding a write
581		* lock, returns it.  Or, if a read lock, if the write lock is
582		* available, releases the read lock and returns a write stamp.
#	Line 629 | Line 601 | public class StampedLock implements java
601		break;
602		return stamp;
603		}
604	<	else if (m == RUNIT && a != 0L && a < WBIT) {
604	>	else if (m == RUNIT && a != 0L) {
605		if (U.compareAndSwapLong(this, STATE, s,
606		next = s - RUNIT + WBIT))
607		return next;
#	Line 641 | Line 613 | public class StampedLock implements java
613		}
614
615		/**
616	<	* If the lock state matches the given stamp then performs one of
616	>	* If the lock state matches the given stamp, performs one of
617		* the following actions. If the stamp represents holding a write
618		* lock, releases it and obtains a read lock.  Or, if a read lock,
619		* returns it. Or, if an optimistic read, acquires a read lock and
#	Line 652 | Line 624 | public class StampedLock implements java
624		* @return a valid read stamp, or zero on failure
625		*/
626		public long tryConvertToReadLock(long stamp) {
627	<	long a = stamp & ABITS, m, s, next;
627	>	long a = stamp & ABITS, m, s, next; WNode h;
628		while (((s = state) & SBITS) == (stamp & SBITS)) {
629		if ((m = s & ABITS) == 0L) {
630		if (a != 0L)
#	Line 667 | Line 639 | public class StampedLock implements java
639		else if (m == WBIT) {
640		if (a != m)
641		break;
642	<	next = state = s + (WBIT + RUNIT);
643	<	readerPrefSignal();
642	>	state = next = s + (WBIT + RUNIT);
643	>	if ((h = whead) != null && h.status != 0)
644	>	release(h);
645		return next;
646		}
647		else if (a != 0L && a < WBIT)
#	Line 690 | Line 663 | public class StampedLock implements java
663		* @return a valid optimistic read stamp, or zero on failure
664		*/
665		public long tryConvertToOptimisticRead(long stamp) {
666	<	long a = stamp & ABITS, m, s, next;
667	<	while (((s = U.getLongVolatile(this, STATE)) &
668	<	SBITS) == (stamp & SBITS)) {
666	>	long a = stamp & ABITS, m, s, next; WNode h;
667	>	for (;;) {
668	>	s = U.getLongVolatile(this, STATE); // see above
669	>	if ((s & SBITS) != (stamp & SBITS))
670	>	break;
671		if ((m = s & ABITS) == 0L) {
672		if (a != 0L)
673		break;
#	Line 701 | Line 676 | public class StampedLock implements java
676		else if (m == WBIT) {
677		if (a != m)
678		break;
679	<	next = state = (s += WBIT) == 0L ? ORIGIN : s;
680	<	readerPrefSignal();
679	>	state = next = (s += WBIT) == 0L ? ORIGIN : s;
680	>	if ((h = whead) != null && h.status != 0)
681	>	release(h);
682		return next;
683		}
684		else if (a == 0L || a >= WBIT)
685		break;
686		else if (m < RFULL) {
687		if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {
688	<	if (m == RUNIT)
689	<	writerPrefSignal();
688	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
689	>	release(h);
690		return next & SBITS;
691		}
692		}
#	Line 725 | Line 701 | public class StampedLock implements java
701		* stamp value. This method may be useful for recovery after
702		* errors.
703		*
704	<	* @return true if the lock was held, else false
704	>	* @return {@code true} if the lock was held, else false
705		*/
706		public boolean tryUnlockWrite() {
707	<	long s;
707	>	long s; WNode h;
708		if (((s = state) & WBIT) != 0L) {
709		state = (s += WBIT) == 0L ? ORIGIN : s;
710	<	readerPrefSignal();
710	>	if ((h = whead) != null && h.status != 0)
711	>	release(h);
712		return true;
713		}
714		return false;
#	Line 742 | Line 719 | public class StampedLock implements java
719		* requiring a stamp value. This method may be useful for recovery
720		* after errors.
721		*
722	<	* @return true if the read lock was held, else false
722	>	* @return {@code true} if the read lock was held, else false
723		*/
724		public boolean tryUnlockRead() {
725	<	long s, m;
725	>	long s, m; WNode h;
726		while ((m = (s = state) & ABITS) != 0L && m < WBIT) {
727		if (m < RFULL) {
728		if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
729	<	if (m == RUNIT)
730	<	writerPrefSignal();
729	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
730	>	release(h);
731		return true;
732		}
733		}
#	Line 760 | Line 737 | public class StampedLock implements java
737		return false;
738		}
739
740	+	// status monitoring methods
741	+
742		/**
743	<	* Returns true if the lock is currently held exclusively.
743	>	* Returns combined state-held and overflow read count for given
744	>	* state s.
745	>	*/
746	>	private int getReadLockCount(long s) {
747	>	long readers;
748	>	if ((readers = s & RBITS) >= RFULL)
749	>	readers = RFULL + readerOverflow;
750	>	return (int) readers;
751	>	}
752	>
753	>	/**
754	>	* Returns {@code true} if the lock is currently held exclusively.
755		*
756	<	* @return true if the lock is currently held exclusively
756	>	* @return {@code true} if the lock is currently held exclusively
757		*/
758		public boolean isWriteLocked() {
759		return (state & WBIT) != 0L;
760		}
761
762		/**
763	<	* Returns true if the lock is currently held non-exclusively.
763	>	* Returns {@code true} if the lock is currently held non-exclusively.
764		*
765	<	* @return true if the lock is currently held non-exclusively
765	>	* @return {@code true} if the lock is currently held non-exclusively
766		*/
767		public boolean isReadLocked() {
768	<	long m;
769	<	return (m = state & ABITS) > 0L && m < WBIT;
768	>	return (state & RBITS) != 0L;
769	>	}
770	>
771	>	/**
772	>	* Queries the number of read locks held for this lock. This
773	>	* method is designed for use in monitoring system state, not for
774	>	* synchronization control.
775	>	* @return the number of read locks held
776	>	*/
777	>	public int getReadLockCount() {
778	>	return getReadLockCount(state);
779	>	}
780	>
781	>	/**
782	>	* Returns a string identifying this lock, as well as its lock
783	>	* state.  The state, in brackets, includes the String {@code
784	>	* "Unlocked"} or the String {@code "Write-locked"} or the String
785	>	* {@code "Read-locks:"} followed by the current number of
786	>	* read-locks held.
787	>	*
788	>	* @return a string identifying this lock, as well as its lock state
789	>	*/
790	>	public String toString() {
791	>	long s = state;
792	>	return super.toString() +
793	>	((s & ABITS) == 0L ? "[Unlocked]" :
794	>	(s & WBIT) != 0L ? "[Write-locked]" :
795	>	"[Read-locks:" + getReadLockCount(s) + "]");
796	>	}
797	>
798	>	// views
799	>
800	>	/**
801	>	* Returns a plain {@link Lock} view of this StampedLock in which
802	>	* the {@link Lock#lock} method is mapped to {@link #readLock},
803	>	* and similarly for other methods. The returned Lock does not
804	>	* support a {@link Condition}; method {@link
805	>	* Lock#newCondition()} throws {@code
806	>	* UnsupportedOperationException}.
807	>	*
808	>	* @return the lock
809	>	*/
810	>	public Lock asReadLock() {
811	>	ReadLockView v;
812	>	return ((v = readLockView) != null ? v :
813	>	(readLockView = new ReadLockView()));
814	>	}
815	>
816	>	/**
817	>	* Returns a plain {@link Lock} view of this StampedLock in which
818	>	* the {@link Lock#lock} method is mapped to {@link #writeLock},
819	>	* and similarly for other methods. The returned Lock does not
820	>	* support a {@link Condition}; method {@link
821	>	* Lock#newCondition()} throws {@code
822	>	* UnsupportedOperationException}.
823	>	*
824	>	* @return the lock
825	>	*/
826	>	public Lock asWriteLock() {
827	>	WriteLockView v;
828	>	return ((v = writeLockView) != null ? v :
829	>	(writeLockView = new WriteLockView()));
830	>	}
831	>
832	>	/**
833	>	* Returns a {@link ReadWriteLock} view of this StampedLock in
834	>	* which the {@link ReadWriteLock#readLock()} method is mapped to
835	>	* {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to
836	>	* {@link #asWriteLock()}.
837	>	*
838	>	* @return the lock
839	>	*/
840	>	public ReadWriteLock asReadWriteLock() {
841	>	ReadWriteLockView v;
842	>	return ((v = readWriteLockView) != null ? v :
843	>	(readWriteLockView = new ReadWriteLockView()));
844	>	}
845	>
846	>	// view classes
847	>
848	>	final class ReadLockView implements Lock {
849	>	public void lock() { readLock(); }
850	>	public void lockInterruptibly() throws InterruptedException {
851	>	readLockInterruptibly();
852	>	}
853	>	public boolean tryLock() { return tryReadLock() != 0L; }
854	>	public boolean tryLock(long time, TimeUnit unit)
855	>	throws InterruptedException {
856	>	return tryReadLock(time, unit) != 0L;
857	>	}
858	>	public void unlock() { unstampedUnlockRead(); }
859	>	public Condition newCondition() {
860	>	throw new UnsupportedOperationException();
861	>	}
862	>	}
863	>
864	>	final class WriteLockView implements Lock {
865	>	public void lock() { writeLock(); }
866	>	public void lockInterruptibly() throws InterruptedException {
867	>	writeLockInterruptibly();
868	>	}
869	>	public boolean tryLock() { return tryWriteLock() != 0L; }
870	>	public boolean tryLock(long time, TimeUnit unit)
871	>	throws InterruptedException {
872	>	return tryWriteLock(time, unit) != 0L;
873	>	}
874	>	public void unlock() { unstampedUnlockWrite(); }
875	>	public Condition newCondition() {
876	>	throw new UnsupportedOperationException();
877	>	}
878	>	}
879	>
880	>	final class ReadWriteLockView implements ReadWriteLock {
881	>	public Lock readLock() { return asReadLock(); }
882	>	public Lock writeLock() { return asWriteLock(); }
883	>	}
884	>
885	>	// Unlock methods without stamp argument checks for view classes.
886	>	// Needed because view-class lock methods throw away stamps.
887	>
888	>	final void unstampedUnlockWrite() {
889	>	WNode h; long s;
890	>	if (((s = state) & WBIT) == 0L)
891	>	throw new IllegalMonitorStateException();
892	>	state = (s += WBIT) == 0L ? ORIGIN : s;
893	>	if ((h = whead) != null && h.status != 0)
894	>	release(h);
895	>	}
896	>
897	>	final void unstampedUnlockRead() {
898	>	for (;;) {
899	>	long s, m; WNode h;
900	>	if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
901	>	throw new IllegalMonitorStateException();
902	>	else if (m < RFULL) {
903	>	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
904	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
905	>	release(h);
906	>	break;
907	>	}
908	>	}
909	>	else if (tryDecReaderOverflow(s) != 0L)
910	>	break;
911	>	}
912		}
913
914		private void readObject(java.io.ObjectInputStream s)
#	Line 792 | Line 924 | public class StampedLock implements java
924		* access bits value to RBITS, indicating hold of spinlock,
925		* then updating, then releasing.
926		*
927	<	* @param stamp, assumed that (stamp & ABITS) >= RFULL
927	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
928		* @return new stamp on success, else zero
929		*/
930		private long tryIncReaderOverflow(long s) {
931	+	// assert (s & ABITS) >= RFULL;
932		if ((s & ABITS) == RFULL) {
933		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
934		++readerOverflow;
#	Line 812 | Line 945 | public class StampedLock implements java
945		/**
946		* Tries to decrement readerOverflow.
947		*
948	<	* @param stamp, assumed that (stamp & ABITS) >= RFULL
948	>	* @param s a reader overflow stamp: (s & ABITS) >= RFULL
949		* @return new stamp on success, else zero
950		*/
951		private long tryDecReaderOverflow(long s) {
952	+	// assert (s & ABITS) >= RFULL;
953		if ((s & ABITS) == RFULL) {
954		if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
955		int r; long next;
#	Line 835 | Line 969 | public class StampedLock implements java
969		return 0L;
970		}
971
972	<	/*
973	<	* The two versions of signal implement the phase-fair policy.
974	<	* They include almost the same code, but repacked in different
975	<	* ways.  Integrating the policy with the mechanics eliminates
976	<	* state rechecks that would be needed with separate reader and
977	<	* writer signal methods.  Both methods assume that they are
978	<	* called when the lock is last known to be available, and
979	<	* continue until the lock is unavailable, or at least one thread
980	<	* is signalled, or there are no more waiting threads.  Signalling
981	<	* a reader entails popping (CASing) from rhead and unparking
982	<	* unless the thread already cancelled (indicated by a null waiter
849	<	* field). Signalling a writer requires finding the first node,
850	<	* i.e., the successor of whead. This is normally just head.next,
851	<	* but may require traversal from wtail if next pointers are
852	<	* lagging. These methods may fail to wake up an acquiring thread
853	<	* when one or more have been cancelled, but the cancel methods
854	<	* themselves provide extra safeguards to ensure liveness.
855	<	*/
856	<
857	<	private void readerPrefSignal() {
858	<	boolean readers = false;
859	<	RNode p; WNode h, q; long s; Thread w;
860	<	while ((p = rhead) != null) {
861	<	if (((s = state) & WBIT) != 0L)
862	<	return;
863	<	if (p.seq == (s & SBITS))
864	<	break;
865	<	readers = true;
866	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
867	<	(w = p.waiter) != null &&
868	<	U.compareAndSwapObject(p, WAITER, w, null))
869	<	U.unpark(w);
870	<	}
871	<	if (!readers && (state & ABITS) == 0L &&
872	<	(h = whead) != null && h.status != 0) {
873	<	U.compareAndSwapInt(h, STATUS, WAITING, 0);
874	<	if ((q = h.next) == null || q.status == CANCELLED) {
875	<	q = null;
876	<	for (WNode t = wtail; t != null && t != h; t = t.prev)
877	<	if (t.status <= 0)
878	<	q = t;
879	<	}
880	<	if (q != null && (w = q.thread) != null)
881	<	U.unpark(w);
882	<	}
883	<	}
884	<
885	<	private void writerPrefSignal() {
886	<	RNode p; WNode h, q; long s; Thread w;
887	<	if ((h = whead) != null && h.status != 0) {
888	<	U.compareAndSwapInt(h, STATUS, WAITING, 0);
972	>	/**
973	>	* Wakes up the successor of h (normally whead). This is normally
974	>	* just h.next, but may require traversal from wtail if next
975	>	* pointers are lagging. This may fail to wake up an acquiring
976	>	* thread when one or more have been cancelled, but the cancel
977	>	* methods themselves provide extra safeguards to ensure liveness.
978	>	*/
979	>	private void release(WNode h) {
980	>	if (h != null) {
981	>	WNode q; Thread w;
982	>	U.compareAndSwapInt(h, WSTATUS, WAITING, 0);
983		if ((q = h.next) == null || q.status == CANCELLED) {
890	–	q = null;
984		for (WNode t = wtail; t != null && t != h; t = t.prev)
985		if (t.status <= 0)
986		q = t;
987		}
988	<	if (q != null && (w = q.thread) != null)
989	<	U.unpark(w);
990	<	}
991	<	else {
992	<	while ((p = rhead) != null && ((s = state) & WBIT) == 0L &&
993	<	p.seq != (s & SBITS)) {
994	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
995	<	(w = p.waiter) != null &&
996	<	U.compareAndSwapObject(p, WAITER, w, null))
997	<	U.unpark(w);
988	>	if (q != null) {
989	>	for (WNode r = q;;) {  // release co-waiters too
990	>	if ((w = r.thread) != null) {
991	>	r.thread = null;
992	>	U.unpark(w);
993	>	}
994	>	if ((r = q.cowait) == null)
995	>	break;
996	>	U.compareAndSwapObject(q, WCOWAIT, r, r.cowait);
997	>	}
998		}
999		}
1000		}
1001
1002		/**
1003	<	* RNG for local spins. The first call from await{Read,Write}
911	<	* produces a thread-local value. Unless zero, subsequent calls
912	<	* use an xorShift to further reduce memory traffic.
913	<	*/
914	<	private static int nextRandom(int r) {
915	<	if (r == 0)
916	<	return ThreadLocalRandom.current().nextInt();
917	<	r ^= r << 1; // xorshift
918	<	r ^= r >>> 3;
919	<	r ^= r << 10;
920	<	return r;
921	<	}
922	<
923	<	/**
924	<	* Possibly spins trying to obtain write lock, then enqueues and
925	<	* blocks while not head of write queue or cannot acquire lock,
926	<	* possibly spinning when at head; cancelling on timeout or
927	<	* interrupt.
1003	>	* See above for explanation.
1004		*
1005		* @param interruptible true if should check interrupts and if so
1006		* return INTERRUPTED
1007		* @param deadline if nonzero, the System.nanoTime value to timeout
1008		* at (and return zero)
1009	+	* @return next state, or INTERRUPTED
1010		*/
1011	<	private long awaitWrite(boolean interruptible, long deadline) {
1012	<	WNode node = null;
1013	<	for (int r = 0, spins = -1;;) {
1014	<	WNode p; long s, next;
1011	>	private long acquireWrite(boolean interruptible, long deadline) {
1012	>	WNode node = null, p;
1013	>	for (int spins = -1;;) { // spin while enqueuing
1014	>	long s, ns;
1015		if (((s = state) & ABITS) == 0L) {
1016	<	if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
1017	<	return next;
1016	>	if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
1017	>	return ns;
1018		}
942	–	else if (spins < 0)
943	–	spins = whead == wtail ? SPINS : 0;
1019		else if (spins > 0) {
1020	<	if ((r = nextRandom(r)) >= 0)
1020	>	if (ThreadLocalRandom.current().nextInt() >= 0)
1021		--spins;
1022		}
1023		else if ((p = wtail) == null) { // initialize queue
1024	<	if (U.compareAndSwapObject(this, WHEAD, null,
1025	<	new WNode(null, null)))
1026	<	wtail = whead;
1024	>	WNode h = new WNode(WMODE, null);
1025	>	if (U.compareAndSwapObject(this, WHEAD, null, h))
1026	>	wtail = h;
1027		}
1028	+	else if (spins < 0)
1029	+	spins = (p == whead) ? SPINS : 0;
1030		else if (node == null)
1031	<	node = new WNode(Thread.currentThread(), p);
1031	>	node = new WNode(WMODE, p);
1032		else if (node.prev != p)
1033		node.prev = p;
1034		else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
1035		p.next = node;
1036	<	for (int headSpins = SPINS;;) {
1037	<	WNode np; int ps;
1038	<	if ((np = node.prev) != p && np != null &&
1039	<	(p = np).next != node)
1040	<	p.next = node; // stale
1041	<	if (p == whead) {
1042	<	for (int k = headSpins;;) {
1043	<	if (((s = state) & ABITS) == 0L) {
1044	<	if (U.compareAndSwapLong(this, STATE,
1045	<	s, next = s + WBIT)) {
1046	<	whead = node;
1047	<	node.thread = null;
1048	<	node.prev = null;
1049	<	return next;
1050	<	}
1051	<	break;
1036	>	break;
1037	>	}
1038	>	}
1039	>
1040	>	for (int spins = SPINS;;) {
1041	>	WNode np, pp; int ps; long s, ns; Thread w;
1042	>	while ((np = node.prev) != p && np != null)
1043	>	(p = np).next = node;   // stale
1044	>	if (whead == p) {
1045	>	for (int k = spins;;) { // spin at head
1046	>	if (((s = state) & ABITS) == 0L) {
1047	>	if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1048	>	whead = node;
1049	>	node.prev = null;
1050	>	return ns;
1051	>	}
1052	>	}
1053	>	else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1054	>	--k <= 0)
1055	>	break;
1056	>	}
1057	>	if (spins < MAX_HEAD_SPINS)
1058	>	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;
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, node, false);
1074	>	Thread wt = Thread.currentThread();
1075	>	U.putObject(wt, PARKBLOCKER, this); // emulate LockSupport.park
1076	>	node.thread = wt;
1077	>	if (node.prev == p && p.status == WAITING && // recheck
1078	>	(p != whead || (state & ABITS) != 0L))
1079	>	U.park(false, time);
1080	>	node.thread = null;
1081	>	U.putObject(wt, PARKBLOCKER, null);
1082	>	if (interruptible && Thread.interrupted())
1083	>	return cancelWaiter(node, node, true);
1084	>	}
1085	>	}
1086	>	}
1087	>
1088	>	/**
1089	>	* See above for explanation.
1090	>	*
1091	>	* @param interruptible true if should check interrupts and if so
1092	>	* return INTERRUPTED
1093	>	* @param deadline if nonzero, the System.nanoTime value to timeout
1094	>	* at (and return zero)
1095	>	* @return next state, or INTERRUPTED
1096	>	*/
1097	>	private long acquireRead(boolean interruptible, long deadline) {
1098	>	WNode node = null, group = null, p;
1099	>	for (int spins = -1;;) {
1100	>	for (;;) {
1101	>	long s, m, ns; WNode h, q; Thread w; // anti-barging guard
1102	>	if (group == null && (h = whead) != null &&
1103	>	(q = h.next) != null && q.mode != RMODE)
1104	>	break;
1105	>	if ((m = (s = state) & ABITS) < RFULL ?
1106	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1107	>	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1108	>	if (group != null) {  // help release others
1109	>	for (WNode r = group;;) {
1110	>	if ((w = r.thread) != null) {
1111	>	r.thread = null;
1112	>	U.unpark(w);
1113		}
1114	<	if ((r = nextRandom(r)) >= 0 && --k <= 0)
1114	>	if ((r = group.cowait) == null)
1115		break;
1116	+	U.compareAndSwapObject(group, WCOWAIT, r, r.cowait);
1117		}
979	–	if (headSpins < MAX_HEAD_SPINS)
980	–	headSpins <<= 1;
1118		}
1119	<	if ((ps = p.status) == 0)
1120	<	U.compareAndSwapInt(p, STATUS, 0, WAITING);
1121	<	else if (ps == CANCELLED)
1122	<	node.prev = p.prev;
1123	<	else {
1124	<	long time; // 0 argument to park means no timeout
1119	>	return ns;
1120	>	}
1121	>	if (m >= WBIT)
1122	>	break;
1123	>	}
1124	>	if (spins > 0) {
1125	>	if (ThreadLocalRandom.current().nextInt() >= 0)
1126	>	--spins;
1127	>	}
1128	>	else if ((p = wtail) == null) {
1129	>	WNode h = new WNode(WMODE, null);
1130	>	if (U.compareAndSwapObject(this, WHEAD, null, h))
1131	>	wtail = h;
1132	>	}
1133	>	else if (spins < 0)
1134	>	spins = (p == whead) ? SPINS : 0;
1135	>	else if (node == null)
1136	>	node = new WNode(WMODE, p);
1137	>	else if (node.prev != p)
1138	>	node.prev = p;
1139	>	else if (p.mode == RMODE && p != whead) {
1140	>	WNode pp = p.prev;  // become co-waiter with group p
1141	>	if (pp != null && p == wtail &&
1142	>	U.compareAndSwapObject(p, WCOWAIT,
1143	>	node.cowait = p.cowait, node)) {
1144	>	node.thread = Thread.currentThread();
1145	>	for (long time;;) {
1146		if (deadline == 0L)
1147		time = 0L;
1148		else if ((time = deadline - System.nanoTime()) <= 0L)
1149	<	return cancelWriter(node, false);
1150	<	if (node.prev == p && p.status == WAITING &&
1151	<	(p != whead || (state & WBIT) != 0L)) { // recheck
1152	<	U.park(false, time);
1153	<	if (interruptible && Thread.interrupted())
1154	<	return cancelWriter(node, true);
1149	>	return cancelWaiter(node, p, false);
1150	>	if (node.thread == null)
1151	>	break;
1152	>	if (p.prev != pp || p.status == CANCELLED ||
1153	>	p == whead || p.prev != pp) {
1154	>	node.thread = null;
1155	>	break;
1156		}
1157	+	Thread wt = Thread.currentThread();
1158	+	U.putObject(wt, PARKBLOCKER, this);
1159	+	if (node.thread == null) // must recheck
1160	+	break;
1161	+	U.park(false, time);
1162	+	U.putObject(wt, PARKBLOCKER, null);
1163	+	if (interruptible && Thread.interrupted())
1164	+	return cancelWaiter(node, p, true);
1165		}
1166	+	group = p;
1167		}
1168	+	node = null; // throw away
1169		}
1170	<	}
1171	<	}
1172	<
1004	<	/**
1005	<	* If node non-null, forces cancel status and unsplices from queue
1006	<	* if possible. This is a streamlined variant of cancellation
1007	<	* methods in AbstractQueuedSynchronizer that includes a detailed
1008	<	* explanation.
1009	<	*/
1010	<	private long cancelWriter(WNode node, boolean interrupted) {
1011	<	WNode pred;
1012	<	if (node != null && (pred = node.prev) != null) {
1013	<	WNode pp;
1014	<	node.thread = null;
1015	<	while (pred.status == CANCELLED && (pp = pred.prev) != null)
1016	<	pred = node.prev = pp;
1017	<	WNode predNext = pred.next;
1018	<	node.status = CANCELLED;
1019	<	if (predNext != null) {
1020	<	Thread w;
1021	<	WNode succ = node.next;
1022	<	if (succ == null || succ.status == CANCELLED) {
1023	<	succ = null;
1024	<	for (WNode t = wtail; t != null && t != node; t = t.prev)
1025	<	if (t.status <= 0)
1026	<	succ = t;
1027	<	if (succ == null && node == wtail)
1028	<	U.compareAndSwapObject(this, WTAIL, node, pred);
1029	<	}
1030	<	U.compareAndSwapObject(pred, WNEXT, predNext, succ);
1031	<	if (succ != null && (w = succ.thread) != null)
1032	<	U.unpark(w);
1170	>	else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
1171	>	p.next = node;
1172	>	break;
1173		}
1174		}
1035	–	writerPrefSignal();
1036	–	return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1037	–	}
1175
1176	<	/**
1177	<	* Waits for read lock or timeout or interrupt. The form of
1178	<	* awaitRead differs from awaitWrite mainly because it must
1179	<	* restart (with a new wait node) if the thread was unqueued and
1180	<	* unparked but could not the obtain lock.  We also need to help
1181	<	* with preference rules by not trying to acquire the lock before
1182	<	* enqueuing if there is a known waiting writer, but also helping
1183	<	* to release those threads that are still queued from the last
1184	<	* release.
1185	<	*/
1186	<	private long awaitRead(long stamp, boolean interruptible, long deadline) {
1187	<	long seq = stamp & SBITS;
1188	<	RNode node = null;
1189	<	boolean queued = false;
1190	<	for (int r = 0, headSpins = SPINS, spins = -1;;) {
1191	<	long s, m, next; RNode p; WNode wh; Thread w;
1192	<	if ((m = (s = state) & ABITS) != WBIT &&
1193	<	((s & SBITS) != seq || (wh = whead) == null ||
1194	<	wh.status == 0)) {
1195	<	if (m < RFULL ?
1196	<	U.compareAndSwapLong(this, STATE, s, next = s + RUNIT) :
1197	<	(next = tryIncReaderOverflow(s)) != 0L) {
1198	<	if (node != null && (w = node.waiter) != null)
1199	<	U.compareAndSwapObject(node, WAITER, w, null);
1200	<	if ((p = rhead) != null && (s & SBITS) != p.seq &&
1201	<	U.compareAndSwapObject(this, RHEAD, p, p.next) &&
1065	<	(w = p.waiter) != null &&
1066	<	U.compareAndSwapObject(p, WAITER, w, null))
1067	<	U.unpark(w); // help signal other waiters
1068	<	return next;
1176	>	for (int spins = SPINS;;) {
1177	>	WNode np, pp, r; int ps; long m, s, ns; Thread w;
1178	>	while ((np = node.prev) != p && np != null)
1179	>	(p = np).next = node;
1180	>	if (whead == p) {
1181	>	for (int k = spins;;) {
1182	>	if ((m = (s = state) & ABITS) != WBIT) {
1183	>	if (m < RFULL ?
1184	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT):
1185	>	(ns = tryIncReaderOverflow(s)) != 0L) {
1186	>	whead = node;
1187	>	node.prev = null;
1188	>	while ((r = node.cowait) != null) {
1189	>	if (U.compareAndSwapObject(node, WCOWAIT,
1190	>	r, r.cowait) &&
1191	>	(w = r.thread) != null) {
1192	>	r.thread = null;
1193	>	U.unpark(w); // release co-waiter
1194	>	}
1195	>	}
1196	>	return ns;
1197	>	}
1198	>	}
1199	>	else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1200	>	--k <= 0)
1201	>	break;
1202		}
1203	+	if (spins < MAX_HEAD_SPINS)
1204	+	spins <<= 1;
1205		}
1206	<	else if (m != WBIT && (p = rhead) != null &&
1207	<	(s & SBITS) != p.seq) { // help release old readers
1208	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
1209	<	(w = p.waiter) != null &&
1210	<	U.compareAndSwapObject(p, WAITER, w, null))
1211	<	U.unpark(w);
1212	<	}
1078	<	else if (queued && node != null && node.waiter == null) {
1079	<	node = null;    // restart
1080	<	queued = false;
1081	<	spins = -1;
1082	<	}
1083	<	else if (spins < 0) {
1084	<	if (rhead != node)
1085	<	spins = 0;
1086	<	else if ((spins = headSpins) < MAX_HEAD_SPINS && node != null)
1087	<	headSpins <<= 1;
1088	<	}
1089	<	else if (spins > 0) {
1090	<	if ((r = nextRandom(r)) >= 0)
1091	<	--spins;
1092	<	}
1093	<	else if (node == null)
1094	<	node = new RNode(seq, Thread.currentThread());
1095	<	else if (!queued) {
1096	<	if (queued = U.compareAndSwapObject(this, RHEAD,
1097	<	node.next = rhead, node))
1098	<	spins = -1;
1206	>	if ((ps = p.status) == 0)
1207	>	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1208	>	else if (ps == CANCELLED) {
1209	>	if ((pp = p.prev) != null) {
1210	>	node.prev = pp;
1211	>	pp.next = node;
1212	>	}
1213		}
1214		else {
1215		long time;
1216		if (deadline == 0L)
1217		time = 0L;
1218		else if ((time = deadline - System.nanoTime()) <= 0L)
1219	<	return cancelReader(node, false);
1220	<	if ((state & WBIT) != 0L && node.waiter != null) { // recheck
1219	>	return cancelWaiter(node, node, false);
1220	>	Thread wt = Thread.currentThread();
1221	>	U.putObject(wt, PARKBLOCKER, this);
1222	>	node.thread = wt;
1223	>	if (node.prev == p && p.status == WAITING &&
1224	>	(p != whead || (state & ABITS) != WBIT))
1225		U.park(false, time);
1226	<	if (interruptible && Thread.interrupted())
1227	<	return cancelReader(node, true);
1228	<	}
1226	>	node.thread = null;
1227	>	U.putObject(wt, PARKBLOCKER, null);
1228	>	if (interruptible && Thread.interrupted())
1229	>	return cancelWaiter(node, node, true);
1230		}
1231		}
1232		}
1233
1234		/**
1235	<	* If node non-null, forces cancel status and unsplices from queue
1236	<	* if possible, by traversing entire queue looking for cancelled
1237	<	* nodes.
1238	<	*/
1239	<	private long cancelReader(RNode node, boolean interrupted) {
1240	<	Thread w;
1241	<	if (node != null && (w = node.waiter) != null &&
1242	<	U.compareAndSwapObject(node, WAITER, w, null)) {
1243	<	for (RNode pred = null, p = rhead; p != null;) {
1244	<	RNode q = p.next;
1245	<	if (p.waiter == null) {
1246	<	if (pred == null) {
1247	<	U.compareAndSwapObject(this, RHEAD, p, q);
1248	<	p = rhead;
1249	<	}
1250	<	else {
1251	<	U.compareAndSwapObject(pred, RNEXT, p, q);
1252	<	p = pred.next;
1235	>	* If node non-null, forces cancel status and unsplices it from
1236	>	* queue if possible and wakes up any cowaiters (of the node, or
1237	>	* group, as applicable), and in any case helps release current
1238	>	* first waiter if lock is free. (Calling with null arguments
1239	>	* serves as a conditional form of release, which is not currently
1240	>	* needed but may be needed under possible future cancellation
1241	>	* policies). This is a variant of cancellation methods in
1242	>	* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1243	>	* internal documentation).
1244	>	*
1245	>	* @param node if nonnull, the waiter
1246	>	* @param group either node or the group node is cowaiting with
1247	>	* @param interrupted if already interrupted
1248	>	* @return INTERRUPTED if interrupted or Thread.interrupted, else zero
1249	>	*/
1250	>	private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1251	>	if (node != null && group != null) {
1252	>	Thread w;
1253	>	node.status = CANCELLED;
1254	>	node.thread = null;
1255	>	// unsplice cancelled nodes from group
1256	>	for (WNode p = group, q; (q = p.cowait) != null;) {
1257	>	if (q.status == CANCELLED)
1258	>	U.compareAndSwapObject(p, WNEXT, q, q.next);
1259	>	else
1260	>	p = q;
1261	>	}
1262	>	if (group == node) {
1263	>	WNode r; // detach and wake up uncancelled co-waiters
1264	>	while ((r = node.cowait) != null) {
1265	>	if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
1266	>	(w = r.thread) != null) {
1267	>	r.thread = null;
1268	>	U.unpark(w);
1269		}
1270		}
1271	<	else {
1272	<	pred = p;
1273	<	p = q;
1271	>	for (WNode pred = node.prev; pred != null; ) { // unsplice
1272	>	WNode succ, pp;        // find valid successor
1273	>	while ((succ = node.next) == null ||
1274	>	succ.status == CANCELLED) {
1275	>	WNode q = null;    // find successor the slow way
1276	>	for (WNode t = wtail; t != null && t != node; t = t.prev)
1277	>	if (t.status != CANCELLED)
1278	>	q = t;     // don't link if succ cancelled
1279	>	if (succ == q ||   // ensure accurate successor
1280	>	U.compareAndSwapObject(node, WNEXT,
1281	>	succ, succ = q)) {
1282	>	if (succ == null && node == wtail)
1283	>	U.compareAndSwapObject(this, WTAIL, node, pred);
1284	>	break;
1285	>	}
1286	>	}
1287	>	if (pred.next == node) // unsplice pred link
1288	>	U.compareAndSwapObject(pred, WNEXT, node, succ);
1289	>	if (succ != null && (w = succ.thread) != null) {
1290	>	succ.thread = null;
1291	>	U.unpark(w);       // wake up succ to observe new pred
1292	>	}
1293	>	if (pred.status != CANCELLED || (pp = pred.prev) == null)
1294	>	break;
1295	>	node.prev = pp;        // repeat if new pred wrong/cancelled
1296	>	U.compareAndSwapObject(pp, WNEXT, pred, succ);
1297	>	pred = pp;
1298		}
1299		}
1300		}
1301	<	readerPrefSignal();
1301	>	WNode h; // Possibly release first waiter
1302	>	while ((h = whead) != null) {
1303	>	long s; WNode q; // similar to release() but check eligibility
1304	>	if ((q = h.next) == null || q.status == CANCELLED) {
1305	>	for (WNode t = wtail; t != null && t != h; t = t.prev)
1306	>	if (t.status <= 0)
1307	>	q = t;
1308	>	}
1309	>	if (h == whead) {
1310	>	if (q != null && h.status == 0 &&
1311	>	((s = state) & ABITS) != WBIT && // waiter is eligible
1312	>	(s == 0L || q.mode == RMODE))
1313	>	release(h);
1314	>	break;
1315	>	}
1316	>	}
1317		return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1318		}
1319
1320		// Unsafe mechanics
1321		private static final sun.misc.Unsafe U;
1322		private static final long STATE;
1149	–	private static final long RHEAD;
1323		private static final long WHEAD;
1324		private static final long WTAIL;
1152	–	private static final long RNEXT;
1325		private static final long WNEXT;
1326	<	private static final long WPREV;
1327	<	private static final long WAITER;
1328	<	private static final long STATUS;
1326	>	private static final long WSTATUS;
1327	>	private static final long WCOWAIT;
1328	>	private static final long PARKBLOCKER;
1329
1330		static {
1331		try {
1332		U = getUnsafe();
1333		Class<?> k = StampedLock.class;
1162	–	Class<?> rk = RNode.class;
1334		Class<?> wk = WNode.class;
1335		STATE = U.objectFieldOffset
1336		(k.getDeclaredField("state"));
1166	–	RHEAD = U.objectFieldOffset
1167	–	(k.getDeclaredField("rhead"));
1337		WHEAD = U.objectFieldOffset
1338		(k.getDeclaredField("whead"));
1339		WTAIL = U.objectFieldOffset
1340		(k.getDeclaredField("wtail"));
1341	<	RNEXT = U.objectFieldOffset
1173	<	(rk.getDeclaredField("next"));
1174	<	WAITER = U.objectFieldOffset
1175	<	(rk.getDeclaredField("waiter"));
1176	<	STATUS = U.objectFieldOffset
1341	>	WSTATUS = U.objectFieldOffset
1342		(wk.getDeclaredField("status"));
1343		WNEXT = U.objectFieldOffset
1344		(wk.getDeclaredField("next"));
1345	<	WPREV = U.objectFieldOffset
1346	<	(wk.getDeclaredField("prev"));
1345	>	WCOWAIT = U.objectFieldOffset
1346	>	(wk.getDeclaredField("cowait"));
1347	>	Class<?> tk = Thread.class;
1348	>	PARKBLOCKER = U.objectFieldOffset
1349	>	(tk.getDeclaredField("parkBlocker"));
1350
1351		} catch (Exception e) {
1352		throw new Error(e);
#	Line 1195 | Line 1363 | public class StampedLock implements java
1363		private static sun.misc.Unsafe getUnsafe() {
1364		try {
1365		return sun.misc.Unsafe.getUnsafe();
1366	<	} catch (SecurityException se) {
1367	<	try {
1368	<	return java.security.AccessController.doPrivileged
1369	<	(new java.security
1370	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1371	<	public sun.misc.Unsafe run() throws Exception {
1372	<	java.lang.reflect.Field f = sun.misc
1373	<	.Unsafe.class.getDeclaredField("theUnsafe");
1374	<	f.setAccessible(true);
1375	<	return (sun.misc.Unsafe) f.get(null);
1376	<	}});
1377	<	} catch (java.security.PrivilegedActionException e) {
1378	<	throw new RuntimeException("Could not initialize intrinsics",
1379	<	e.getCause());
1380	<	}
1366	>	} catch (SecurityException tryReflectionInstead) {}
1367	>	try {
1368	>	return java.security.AccessController.doPrivileged
1369	>	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1370	>	public sun.misc.Unsafe run() throws Exception {
1371	>	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1372	>	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1373	>	f.setAccessible(true);
1374	>	Object x = f.get(null);
1375	>	if (k.isInstance(x))
1376	>	return k.cast(x);
1377	>	}
1378	>	throw new NoSuchFieldError("the Unsafe");
1379	>	}});
1380	>	} catch (java.security.PrivilegedActionException e) {
1381	>	throw new RuntimeException("Could not initialize intrinsics",
1382	>	e.getCause());
1383		}
1384		}
1215	–
1385		}

Diff Legend

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