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.23 by dl, Sun Oct 28 22:35:46 2012 UTC vs.
Revision 1.36 by dl, Wed Jun 19 14:55:40 2013 UTC

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

Diff Legend

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