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.22 by jsr166, Wed Oct 17 00:02:47 2012 UTC vs.
Revision 1.32 by dl, Sat Jan 26 01:22:37 2013 UTC

#	Line 8 | Line 8 | package jsr166e;
8
9		import java.util.concurrent.ThreadLocalRandom;
10		import java.util.concurrent.TimeUnit;
11	+	import java.util.concurrent.locks.Lock;
12	+	import java.util.concurrent.locks.Condition;
13	+	import java.util.concurrent.locks.ReadWriteLock;
14	+	import java.util.concurrent.locks.LockSupport;
15
16		/**
17		* A capability-based lock with three modes for controlling read/write
#	Line 36 | Line 40 | import java.util.concurrent.TimeUnit;
40		*  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
41		*   returns a non-zero stamp only if the lock is not currently held
42		*   in write mode. Method {@link #validate} returns true if the lock
43	<	*   has not since been acquired in write mode. This mode can be
44	<	*   thought of as an extremely weak version of a read-lock, that can
45	<	*   be broken by a writer at any time.  The use of optimistic mode
46	<	*   for short read-only code segments often reduces contention and
47	<	*   improves throughput.  However, its use is inherently fragile.
48	<	*   Optimistic read sections should only read fields and hold them in
49	<	*   local variables for later use after validation. Fields read while
50	<	*   in optimistic mode may be wildly inconsistent, so usage applies
51	<	*   only when you are familiar enough with data representations to
52	<	*   check consistency and/or repeatedly invoke method {@code
53	<	*   validate()}.  For example, such steps are typically required when
54	<	*   first reading an object or array reference, and then accessing
55	<	*   one of its fields, elements or methods. </li>
43	>	*   has not been acquired in write mode since obtaining a given
44	>	*   stamp.  This mode can be thought of as an extremely weak version
45	>	*   of a read-lock, that can be broken by a writer at any time.  The
46	>	*   use of optimistic mode for short read-only code segments often
47	>	*   reduces contention and improves throughput.  However, its use is
48	>	*   inherently fragile.  Optimistic read sections should only read
49	>	*   fields and hold them in local variables for later use after
50	>	*   validation. Fields read while in optimistic mode may be wildly
51	>	*   inconsistent, so usage applies only when you are familiar enough
52	>	*   with data representations to check consistency and/or repeatedly
53	>	*   invoke method {@code validate()}.  For example, such steps are
54	>	*   typically required when first reading an object or array
55	>	*   reference, and then accessing one of its fields, elements or
56	>	*   methods. </li>
57		*
58		* </ul>
59		*
#	Line 80 | Line 85 | import java.util.concurrent.TimeUnit;
85		* locking.
86		*
87		* <p>The scheduling policy of StampedLock does not consistently
88	<	* prefer readers over writers or vice versa.  A zero return from any
89	<	* "try" method for acquiring or converting locks does not carry any
90	<	* information about the state of the lock; a subsequent invocation
91	<	* may succeed.
88	>	* prefer readers over writers or vice versa.  All "try" methods are
89	>	* best-effort and do not necessarily conform to any scheduling or
90	>	* fairness policy. A zero return from any "try" method for acquiring
91	>	* or converting locks does not carry any information about the state
92	>	* of the lock; a subsequent invocation may succeed.
93	>	*
94	>	* <p>Because it supports coordinated usage across multiple lock
95	>	* modes, this class does not directly implement the {@link Lock} or
96	>	* {@link ReadWriteLock} interfaces. However, a StampedLock may be
97	>	* viewed {@link #asReadLock()}, {@link #asWriteLock()}, or {@link
98	>	* #asReadWriteLock()} in applications requiring only the associated
99	>	* set of functionality.
100		*
101		* <p><b>Sample Usage.</b> The following illustrates some usage idioms
102		* in a class that maintains simple two-dimensional points. The sample
#	Line 156 | Line 169 | import java.util.concurrent.TimeUnit;
169		*         }
170		*       }
171		*     } finally {
172	<	*        sl.unlock(stamp);
172	>	*       sl.unlock(stamp);
173		*     }
174		*   }
175		* }}</pre>
#	Line 173 | Line 186 | public class StampedLock implements java
186		* http://www.lameter.com/gelato2005.pdf
187		* and elsewhere; see
188		* Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)
189	<	* Ordered RW locks (see Shirako et al
189	>	* and Ordered RW locks (see Shirako et al
190		* 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/).
191		*
192		* Conceptually, the primary state of the lock includes a sequence
193		* number that is odd when write-locked and even otherwise.
#	Line 189 | Line 200 | public class StampedLock implements java
200		* reader count value (RBITS) as a spinlock protecting overflow
201		* updates.
202		*
203	<	* Waiting readers and writers use different queues. The writer
204	<	* queue is a modified form of CLH lock.  (For discussion of CLH,
205	<	* see the internal documentation of AbstractQueuedSynchronizer.)
206	<	* The reader "queue" is a form of Treiber stack, that supports
207	<	* simpler/faster operations because order within a queue doesn't
208	<	* matter and all are signalled at once.  However the sequence of
209	<	* threads within the queue vs the current stamp does matter (see
210	<	* Shirako et al) so each carries its incoming stamp value.
211	<	* Waiting writers never need to track sequence values, so they
212	<	* don't.
213	<	*
214	<	* These queue mechanics hardwire the scheduling policy.  Ignoring
215	<	* trylocks, cancellation, and spinning, they implement Phase-Fair
216	<	* preferences:
217	<	*   1. Unlocked writers prefer to signal waiting readers
218	<	*   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
203	>	* Waiters use a modified form of CLH lock used in
204	>	* AbstractQueuedSynchronizer (see its internal documentation for
205	>	* a fuller account), where each node is tagged (field mode) as
206	>	* either a reader or writer. Sets of waiting readers are grouped
207	>	* (linked) under a common node (field cowait) so act as a single
208	>	* node with respect to most CLH mechanics.  By virtue of the
209	>	* queue structure, wait nodes need not actually carry sequence
210	>	* numbers; we know each is greater than its predecessor.  This
211	>	* simplifies the scheduling policy to a mainly-FIFO scheme that
212	>	* incorporates elements of Phase-Fair locks (see Brandenburg &
213	>	* Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
214	>	* particular, we use the phase-fair anti-barging rule: If an
215	>	* incoming reader arrives while read lock is held but there is a
216	>	* queued writer, this incoming reader is queued.  (This rule is
217	>	* responsible for some of the complexity of method acquireRead,
218	>	* but without it, the lock becomes highly unfair.)
219		*
220		* These rules apply to threads actually queued. All tryLock forms
221		* opportunistically try to acquire locks regardless of preference
222	<	* rules, and so may "barge" their way in.  Additionally, initial
223	<	* phases of the await* methods (invoked from readLock() and
224	<	* writeLock()) use controlled spins that have similar effect.
225	<	* Phase-fair preferences may also be broken on cancellations due
226	<	* to timeouts and interrupts.  Rule #3 (incoming readers when a
227	<	* waiting writer) is approximated with varying precision in
228	<	* different contexts -- some checks do not account for
229	<	* in-progress spins/signals, and others do not account for
230	<	* cancellations.
231	<	*
232	<	* Controlled, randomized spinning is used in the two await
233	<	* methods to reduce (increasingly expensive) context switching
234	<	* while also avoiding sustained memory thrashing among many
235	<	* threads.  Both await methods use a similar spin strategy: If
236	<	* the associated queue appears to be empty, then the thread
237	<	* 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.
222	>	* rules, and so may "barge" their way in.  Randomized spinning is
223	>	* used in the acquire methods to reduce (increasingly expensive)
224	>	* context switching while also avoiding sustained memory
225	>	* thrashing among many threads.  We limit spins to the head of
226	>	* queue. A thread spin-waits up to SPINS times (where each
227	>	* iteration decreases spin count with 50% probability) before
228	>	* blocking. If, upon wakening it fails to obtain lock, and is
229	>	* still (or becomes) the first waiting thread (which indicates
230	>	* that some other thread barged and obtained lock), it escalates
231	>	* spins (up to MAX_HEAD_SPINS) to reduce the likelihood of
232	>	* continually losing to barging threads.
233	>	*
234	>	* Nearly all of these mechanics are carried out in methods
235	>	* acquireWrite and acquireRead, that, as typical of such code,
236	>	* sprawl out because actions and retries rely on consistent sets
237	>	* of locally cached reads.
238		*
239		* As noted in Boehm's paper (above), sequence validation (mainly
240		* method validate()) requires stricter ordering rules than apply
#	Line 251 | Line 253 | public class StampedLock implements java
253		* motivation to further spread out contended locations, but might
254		* be subject to future improvements.
255		*/
256	+	private static final long serialVersionUID = -6001602636862214147L;
257
258		/** Number of processors, for spin control */
259		private static final int NCPU = Runtime.getRuntime().availableProcessors();
260
261		/** Maximum number of retries before blocking on acquisition */
262	<	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1;
262	>	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;
263
264		/** Maximum number of retries before re-blocking */
265	<	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1;
265	>	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 0;
266
267		/** The period for yielding when waiting for overflow spinlock */
268		private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
#	Line 278 | Line 281 | public class StampedLock implements java
281		// Initial value for lock state; avoid failure value zero
282		private static final long ORIGIN = WBIT << 1;
283
284	<	// Special value from cancelled await methods so caller can throw IE
284	>	// Special value from cancelled acquire methods so caller can throw IE
285		private static final long INTERRUPTED = 1L;
286
287	<	// Values for writer status; order matters
287	>	// Values for node status; order matters
288		private static final int WAITING   = -1;
289		private static final int CANCELLED =  1;
290
291	<	/** Wait nodes for readers */
292	<	static final class RNode {
293	<	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	<	}
291	>	// Modes for nodes (int not boolean to allow arithmetic)
292	>	private static final int RMODE = 0;
293	>	private static final int WMODE = 1;
294
295	<	/** Wait nodes for writers */
295	>	/** Wait nodes */
296		static final class WNode {
298	–	volatile int status;   // 0, WAITING, or CANCELLED
297		volatile WNode prev;
298		volatile WNode next;
299	<	volatile Thread thread;
300	<	WNode(Thread t, WNode p) { thread = t; prev = p; }
299	>	volatile WNode cowait;    // list of linked readers
300	>	volatile Thread thread;   // non-null while possibly parked
301	>	volatile int status;      // 0, WAITING, or CANCELLED
302	>	final int mode;           // RMODE or WMODE
303	>	WNode(int m, WNode p) { mode = m; prev = p; }
304		}
305
306	<	/** Head of writer CLH queue */
306	>	/** Head of CLH queue */
307		private transient volatile WNode whead;
308	<	/** Tail (last) of writer CLH queue */
308	>	/** Tail (last) of CLH queue */
309		private transient volatile WNode wtail;
310	<	/** Head of read queue  */
311	<	private transient volatile RNode rhead;
312	<	/** The state of the lock -- high bits hold sequence, low bits read count */
310	>
311	>	// views
312	>	transient ReadLockView readLockView;
313	>	transient WriteLockView writeLockView;
314	>	transient ReadWriteLockView readWriteLockView;
315	>
316	>	/** Lock sequence/state */
317		private transient volatile long state;
318		/** extra reader count when state read count saturated */
319		private transient int readerOverflow;
#	Line 327 | Line 332 | public class StampedLock implements java
332		* @return a stamp that can be used to unlock or convert mode
333		*/
334		public long writeLock() {
335	<	long s, next;
336	<	if (((s = state) & ABITS) == 0L &&
337	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
338	<	return next;
334	<	return awaitWrite(false, 0L);
335	>	long s, next;  // bypass acquireWrite in fully unlocked case only
336	>	return ((((s = state) & ABITS) == 0L &&
337	>	U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
338	>	next : acquireWrite(false, 0L));
339		}
340
341		/**
#	Line 342 | Line 346 | public class StampedLock implements java
346		*/
347		public long tryWriteLock() {
348		long s, next;
349	<	if (((s = state) & ABITS) == 0L &&
350	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
351	<	return next;
348	<	return 0L;
349	>	return ((((s = state) & ABITS) == 0L &&
350	>	U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
351	>	next : 0L);
352		}
353
354		/**
355		* Exclusively acquires the lock if it is available within the
356		* given time and the current thread has not been interrupted.
357	+	* Behavior under timeout and interruption matches that specified
358	+	* for method {@link Lock#tryLock(long,TimeUnit)}.
359		*
360		* @return a stamp that can be used to unlock or convert mode,
361		* or zero if the lock is not available
#	Line 361 | Line 366 | public class StampedLock implements java
366		throws InterruptedException {
367		long nanos = unit.toNanos(time);
368		if (!Thread.interrupted()) {
369	<	long s, next, deadline;
370	<	if (((s = state) & ABITS) == 0L &&
366	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
369	>	long next, deadline;
370	>	if ((next = tryWriteLock()) != 0L)
371		return next;
372		if (nanos <= 0L)
373		return 0L;
374		if ((deadline = System.nanoTime() + nanos) == 0L)
375		deadline = 1L;
376	<	if ((next = awaitWrite(true, deadline)) != INTERRUPTED)
376	>	if ((next = acquireWrite(true, deadline)) != INTERRUPTED)
377		return next;
378		}
379		throw new InterruptedException();
#	Line 378 | Line 382 | public class StampedLock implements java
382		/**
383		* Exclusively acquires the lock, blocking if necessary
384		* until available or the current thread is interrupted.
385	+	* Behavior under interruption matches that specified
386	+	* for method {@link Lock#lockInterruptibly()}.
387		*
388		* @return a stamp that can be used to unlock or convert mode
389		* @throws InterruptedException if the current thread is interrupted
390		* before acquiring the lock
391		*/
392		public long writeLockInterruptibly() throws InterruptedException {
393	<	if (!Thread.interrupted()) {
394	<	long s, next;
395	<	if (((s = state) & ABITS) == 0L &&
396	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
391	<	return next;
392	<	if ((next = awaitWrite(true, 0L)) != INTERRUPTED)
393	<	return next;
394	<	}
393	>	long next;
394	>	if (!Thread.interrupted() &&
395	>	(next = acquireWrite(true, 0L)) != INTERRUPTED)
396	>	return next;
397		throw new InterruptedException();
398		}
399
#	Line 402 | Line 404 | public class StampedLock implements java
404		* @return a stamp that can be used to unlock or convert mode
405		*/
406		public long readLock() {
407	<	for (;;) {
408	<	long s, m, next;
409	<	if ((m = (s = state) & ABITS) == 0L ||
410	<	(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	<	}
407	>	long s, next;  // bypass acquireRead on fully unlocked case only
408	>	return ((((s = state) & ABITS) == 0L &&
409	>	U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
410	>	next : acquireRead(false, 0L));
411		}
412
413		/**
#	Line 441 | Line 433 | public class StampedLock implements java
433		/**
434		* Non-exclusively acquires the lock if it is available within the
435		* given time and the current thread has not been interrupted.
436	+	* Behavior under timeout and interruption matches that specified
437	+	* for method {@link Lock#tryLock(long,TimeUnit)}.
438		*
439		* @return a stamp that can be used to unlock or convert mode,
440		* or zero if the lock is not available
#	Line 449 | Line 443 | public class StampedLock implements java
443		*/
444		public long tryReadLock(long time, TimeUnit unit)
445		throws InterruptedException {
446	+	long next, deadline;
447		long nanos = unit.toNanos(time);
448		if (!Thread.interrupted()) {
449	<	for (;;) {
450	<	long s, m, next, deadline;
451	<	if ((m = (s = state) & ABITS) == WBIT ||
452	<	(m != 0L && whead != wtail)) {
453	<	if (nanos <= 0L)
454	<	return 0L;
455	<	if ((deadline = System.nanoTime() + nanos) == 0L)
456	<	deadline = 1L;
462	<	if ((next = awaitRead(s, true, deadline)) != INTERRUPTED)
463	<	return next;
464	<	break;
465	<	}
466	<	else if (m < RFULL) {
467	<	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
468	<	return next;
469	<	}
470	<	else if ((next = tryIncReaderOverflow(s)) != 0L)
471	<	return next;
472	<	}
449	>	if ((next = tryReadLock()) != 0L)
450	>	return next;
451	>	if (nanos <= 0L)
452	>	return 0L;
453	>	if ((deadline = System.nanoTime() + nanos) == 0L)
454	>	deadline = 1L;
455	>	if ((next = acquireRead(true, deadline)) != INTERRUPTED)
456	>	return next;
457		}
458		throw new InterruptedException();
459		}
#	Line 477 | Line 461 | public class StampedLock implements java
461		/**
462		* Non-exclusively acquires the lock, blocking if necessary
463		* until available or the current thread is interrupted.
464	+	* Behavior under interruption matches that specified
465	+	* for method {@link Lock#lockInterruptibly()}.
466		*
467		* @return a stamp that can be used to unlock or convert mode
468		* @throws InterruptedException if the current thread is interrupted
469		* before acquiring the lock
470		*/
471		public long readLockInterruptibly() throws InterruptedException {
472	<	if (!Thread.interrupted()) {
473	<	for (;;) {
474	<	long s, next, m;
475	<	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	<	}
472	>	long next;
473	>	if (!Thread.interrupted() &&
474	>	(next = acquireRead(true, 0L)) != INTERRUPTED)
475	>	return next;
476		throw new InterruptedException();
477		}
478
#	Line 518 | Line 491 | public class StampedLock implements java
491		* Returns true if the lock has not been exclusively acquired
492		* since issuance of the given stamp. Always returns false if the
493		* stamp is zero. Always returns true if the stamp represents a
494	<	* currently held lock.
494	>	* currently held lock. Invoking this method with a value not
495	>	* obtained from {@link #tryOptimisticRead} or a locking method
496	>	* for this lock has no defined effect or result.
497		*
498		* @return true if the lock has not been exclusively acquired
499		* since issuance of the given stamp; else false
#	Line 537 | Line 512 | public class StampedLock implements java
512		* not match the current state of this lock
513		*/
514		public void unlockWrite(long stamp) {
515	+	WNode h;
516		if (state != stamp || (stamp & WBIT) == 0L)
517		throw new IllegalMonitorStateException();
518		state = (stamp += WBIT) == 0L ? ORIGIN : stamp;
519	<	readerPrefSignal();
519	>	if ((h = whead) != null && h.status != 0)
520	>	release(h);
521		}
522
523		/**
#	Line 552 | Line 529 | public class StampedLock implements java
529		* not match the current state of this lock
530		*/
531		public void unlockRead(long stamp) {
532	<	long s, m;
533	<	if ((stamp & RBITS) != 0L) {
534	<	while (((s = state) & SBITS) == (stamp & SBITS)) {
535	<	if ((m = s & ABITS) == 0L)
532	>	long s, m; WNode h;
533	>	for (;;) {
534	>	if (((s = state) & SBITS) != (stamp & SBITS) ||
535	>	(stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
536	>	throw new IllegalMonitorStateException();
537	>	if (m < RFULL) {
538	>	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
539	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
540	>	release(h);
541		break;
560	–	else if (m < RFULL) {
561	–	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
562	–	if (m == RUNIT)
563	–	writerPrefSignal();
564	–	return;
565	–	}
542		}
567	–	else if (m >= WBIT)
568	–	break;
569	–	else if (tryDecReaderOverflow(s) != 0L)
570	–	return;
543		}
544	+	else if (tryDecReaderOverflow(s) != 0L)
545	+	break;
546		}
573	–	throw new IllegalMonitorStateException();
547		}
548
549		/**
#	Line 582 | Line 555 | public class StampedLock implements java
555		* not match the current state of this lock
556		*/
557		public void unlock(long stamp) {
558	<	long a = stamp & ABITS, m, s;
558	>	long a = stamp & ABITS, m, s; WNode h;
559		while (((s = state) & SBITS) == (stamp & SBITS)) {
560		if ((m = s & ABITS) == 0L)
561		break;
#	Line 590 | Line 563 | public class StampedLock implements java
563		if (a != m)
564		break;
565		state = (s += WBIT) == 0L ? ORIGIN : s;
566	<	readerPrefSignal();
566	>	if ((h = whead) != null && h.status != 0)
567	>	release(h);
568		return;
569		}
570		else if (a == 0L || a >= WBIT)
571		break;
572		else if (m < RFULL) {
573		if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
574	<	if (m == RUNIT)
575	<	writerPrefSignal();
574	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
575	>	release(h);
576		return;
577		}
578		}
#	Line 609 | Line 583 | public class StampedLock implements java
583		}
584
585		/**
586	<	* If the lock state matches the given stamp then performs one of
586	>	* If the lock state matches the given stamp, performs one of
587		* the following actions. If the stamp represents holding a write
588		* lock, returns it.  Or, if a read lock, if the write lock is
589		* available, releases the read lock and returns a write stamp.
#	Line 646 | Line 620 | public class StampedLock implements java
620		}
621
622		/**
623	<	* If the lock state matches the given stamp then performs one of
623	>	* If the lock state matches the given stamp, performs one of
624		* the following actions. If the stamp represents holding a write
625		* lock, releases it and obtains a read lock.  Or, if a read lock,
626		* returns it. Or, if an optimistic read, acquires a read lock and
#	Line 657 | Line 631 | public class StampedLock implements java
631		* @return a valid read stamp, or zero on failure
632		*/
633		public long tryConvertToReadLock(long stamp) {
634	<	long a = stamp & ABITS, m, s, next;
634	>	long a = stamp & ABITS, m, s, next; WNode h;
635		while (((s = state) & SBITS) == (stamp & SBITS)) {
636		if ((m = s & ABITS) == 0L) {
637		if (a != 0L)
#	Line 673 | Line 647 | public class StampedLock implements java
647		if (a != m)
648		break;
649		state = next = s + (WBIT + RUNIT);
650	<	readerPrefSignal();
650	>	if ((h = whead) != null && h.status != 0)
651	>	release(h);
652		return next;
653		}
654		else if (a != 0L && a < WBIT)
#	Line 695 | Line 670 | public class StampedLock implements java
670		* @return a valid optimistic read stamp, or zero on failure
671		*/
672		public long tryConvertToOptimisticRead(long stamp) {
673	<	long a = stamp & ABITS, m, s, next;
674	<	while (((s = U.getLongVolatile(this, STATE)) &
675	<	SBITS) == (stamp & SBITS)) {
673	>	long a = stamp & ABITS, m, s, next; WNode h;
674	>	for (;;) {
675	>	s = U.getLongVolatile(this, STATE); // see above
676	>	if ((s & SBITS) != (stamp & SBITS))
677	>	break;
678		if ((m = s & ABITS) == 0L) {
679		if (a != 0L)
680		break;
#	Line 707 | Line 684 | public class StampedLock implements java
684		if (a != m)
685		break;
686		state = next = (s += WBIT) == 0L ? ORIGIN : s;
687	<	readerPrefSignal();
687	>	if ((h = whead) != null && h.status != 0)
688	>	release(h);
689		return next;
690		}
691		else if (a == 0L || a >= WBIT)
692		break;
693		else if (m < RFULL) {
694		if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {
695	<	if (m == RUNIT)
696	<	writerPrefSignal();
695	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
696	>	release(h);
697		return next & SBITS;
698		}
699		}
#	Line 733 | Line 711 | public class StampedLock implements java
711		* @return true if the lock was held, else false
712		*/
713		public boolean tryUnlockWrite() {
714	<	long s;
714	>	long s; WNode h;
715		if (((s = state) & WBIT) != 0L) {
716		state = (s += WBIT) == 0L ? ORIGIN : s;
717	<	readerPrefSignal();
717	>	if ((h = whead) != null && h.status != 0)
718	>	release(h);
719		return true;
720		}
721		return false;
#	Line 750 | Line 729 | public class StampedLock implements java
729		* @return true if the read lock was held, else false
730		*/
731		public boolean tryUnlockRead() {
732	<	long s, m;
732	>	long s, m; WNode h;
733		while ((m = (s = state) & ABITS) != 0L && m < WBIT) {
734		if (m < RFULL) {
735		if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
736	<	if (m == RUNIT)
737	<	writerPrefSignal();
736	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
737	>	release(h);
738		return true;
739		}
740		}
#	Line 789 | Line 768 | public class StampedLock implements java
768		state = ORIGIN; // reset to unlocked state
769		}
770
771	+	/**
772	+	* Returns a plain {@link Lock} view of this StampedLock in which
773	+	* the {@link Lock#lock} method is mapped to {@link #readLock},
774	+	* and similarly for other methods. The returned Lock does not
775	+	* support a {@link Condition}; method {@link
776	+	* Lock#newCondition()} throws {@code
777	+	* UnsupportedOperationException}.
778	+	*
779	+	* @return the lock
780	+	*/
781	+	public Lock asReadLock() {
782	+	ReadLockView v;
783	+	return ((v = readLockView) != null ? v :
784	+	(readLockView = new ReadLockView()));
785	+	}
786	+
787	+	/**
788	+	* Returns a plain {@link Lock} view of this StampedLock in which
789	+	* the {@link Lock#lock} method is mapped to {@link #writeLock},
790	+	* and similarly for other methods. The returned Lock does not
791	+	* support a {@link Condition}; method {@link
792	+	* Lock#newCondition()} throws {@code
793	+	* UnsupportedOperationException}.
794	+	*
795	+	* @return the lock
796	+	*/
797	+	public Lock asWriteLock() {
798	+	WriteLockView v;
799	+	return ((v = writeLockView) != null ? v :
800	+	(writeLockView = new WriteLockView()));
801	+	}
802	+
803	+	/**
804	+	* Returns a {@link ReadWriteLock} view of this StampedLock in
805	+	* which the {@link ReadWriteLock#readLock()} method is mapped to
806	+	* {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to
807	+	* {@link #asWriteLock()}.
808	+	*
809	+	* @return the lock
810	+	*/
811	+	public ReadWriteLock asReadWriteLock() {
812	+	ReadWriteLockView v;
813	+	return ((v = readWriteLockView) != null ? v :
814	+	(readWriteLockView = new ReadWriteLockView()));
815	+	}
816	+
817	+	// view classes
818	+
819	+	final class ReadLockView implements Lock {
820	+	public void lock() { readLock(); }
821	+	public void lockInterruptibly() throws InterruptedException {
822	+	readLockInterruptibly();
823	+	}
824	+	public boolean tryLock() { return tryReadLock() != 0L; }
825	+	public boolean tryLock(long time, TimeUnit unit)
826	+	throws InterruptedException {
827	+	return tryReadLock(time, unit) != 0L;
828	+	}
829	+	public void unlock() { unstampedUnlockRead(); }
830	+	public Condition newCondition() {
831	+	throw new UnsupportedOperationException();
832	+	}
833	+	}
834	+
835	+	final class WriteLockView implements Lock {
836	+	public void lock() { writeLock(); }
837	+	public void lockInterruptibly() throws InterruptedException {
838	+	writeLockInterruptibly();
839	+	}
840	+	public boolean tryLock() { return tryWriteLock() != 0L; }
841	+	public boolean tryLock(long time, TimeUnit unit)
842	+	throws InterruptedException {
843	+	return tryWriteLock(time, unit) != 0L;
844	+	}
845	+	public void unlock() { unstampedUnlockWrite(); }
846	+	public Condition newCondition() {
847	+	throw new UnsupportedOperationException();
848	+	}
849	+	}
850	+
851	+	final class ReadWriteLockView implements ReadWriteLock {
852	+	public Lock readLock() { return asReadLock(); }
853	+	public Lock writeLock() { return asWriteLock(); }
854	+	}
855	+
856	+	// Unlock methods without stamp argument checks for view classes.
857	+	// Needed because view-class lock methods throw away stamps.
858	+
859	+	final void unstampedUnlockWrite() {
860	+	WNode h; long s;
861	+	if (((s = state) & WBIT) == 0L)
862	+	throw new IllegalMonitorStateException();
863	+	state = (s += WBIT) == 0L ? ORIGIN : s;
864	+	if ((h = whead) != null && h.status != 0)
865	+	release(h);
866	+	}
867	+
868	+	final void unstampedUnlockRead() {
869	+	for (;;) {
870	+	long s, m; WNode h;
871	+	if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
872	+	throw new IllegalMonitorStateException();
873	+	else if (m < RFULL) {
874	+	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
875	+	if (m == RUNIT && (h = whead) != null && h.status != 0)
876	+	release(h);
877	+	break;
878	+	}
879	+	}
880	+	else if (tryDecReaderOverflow(s) != 0L)
881	+	break;
882	+	}
883	+	}
884	+
885		// internals
886
887		/**
#	Line 840 | Line 933 | public class StampedLock implements java
933		}
934
935		/*
936	<	* The two versions of signal implement the phase-fair policy.
937	<	* They include almost the same code, but repacked in different
938	<	* ways.  Integrating the policy with the mechanics eliminates
939	<	* state rechecks that would be needed with separate reader and
940	<	* writer signal methods.  Both methods assume that they are
941	<	* called when the lock is last known to be available, and
942	<	* continue until the lock is unavailable, or at least one thread
943	<	* is signalled, or there are no more waiting threads.  Signalling
944	<	* a reader entails popping (CASing) from rhead and unparking
945	<	* 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);
936	>	* Wakes up the successor of h (normally whead). This is normally
937	>	* just h.next, but may require traversal from wtail if next
938	>	* pointers are lagging. This may fail to wake up an acquiring
939	>	* thread when one or more have been cancelled, but the cancel
940	>	* methods themselves provide extra safeguards to ensure liveness.
941	>	*/
942	>	private void release(WNode h) {
943	>	if (h != null) {
944	>	WNode q; Thread w;
945	>	U.compareAndSwapInt(h, WSTATUS, WAITING, 0);
946		if ((q = h.next) == null || q.status == CANCELLED) {
947		for (WNode t = wtail; t != null && t != h; t = t.prev)
948		if (t.status <= 0)
949		q = t;
950		}
951	<	if (q != null && (w = q.thread) != null)
952	<	U.unpark(w);
953	<	}
954	<	}
955	<
956	<	private void writerPrefSignal() {
957	<	RNode p; WNode h, q; long s; Thread w;
958	<	if ((h = whead) != null && h.status != 0) {
959	<	U.compareAndSwapInt(h, STATUS, WAITING, 0);
960	<	if ((q = h.next) == null || q.status == CANCELLED) {
893	<	for (WNode t = wtail; t != null && t != h; t = t.prev)
894	<	if (t.status <= 0)
895	<	q = t;
896	<	}
897	<	if (q != null && (w = q.thread) != null)
898	<	U.unpark(w);
899	<	}
900	<	else {
901	<	while ((p = rhead) != null && ((s = state) & WBIT) == 0L &&
902	<	p.seq != (s & SBITS)) {
903	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
904	<	(w = p.waiter) != null &&
905	<	U.compareAndSwapObject(p, WAITER, w, null))
906	<	U.unpark(w);
951	>	if (q != null) {
952	>	for (WNode r = q;;) {  // release co-waiters too
953	>	if ((w = r.thread) != null) {
954	>	r.thread = null;
955	>	U.unpark(w);
956	>	}
957	>	if ((r = q.cowait) == null)
958	>	break;
959	>	U.compareAndSwapObject(q, WCOWAIT, r, r.cowait);
960	>	}
961		}
962		}
963		}
964
965		/**
966	<	* 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.
966	>	* See above for explanation.
967		*
968		* @param interruptible true if should check interrupts and if so
969		* return INTERRUPTED
970		* @param deadline if nonzero, the System.nanoTime value to timeout
971		* at (and return zero)
972	+	* @return next state, or INTERRUPTED
973		*/
974	<	private long awaitWrite(boolean interruptible, long deadline) {
975	<	WNode node = null;
976	<	for (int r = 0, spins = -1;;) {
977	<	WNode p; long s, next;
974	>	private long acquireWrite(boolean interruptible, long deadline) {
975	>	WNode node = null, p;
976	>	for (int spins = -1;;) { // spin while enqueuing
977	>	long s, ns;
978		if (((s = state) & ABITS) == 0L) {
979	<	if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
980	<	return next;
979	>	if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
980	>	return ns;
981		}
944	–	else if (spins < 0)
945	–	spins = whead == wtail ? SPINS : 0;
982		else if (spins > 0) {
983	<	if ((r = nextRandom(r)) >= 0)
983	>	if (ThreadLocalRandom.current().nextInt() >= 0)
984		--spins;
985		}
986		else if ((p = wtail) == null) { // initialize queue
987	<	if (U.compareAndSwapObject(this, WHEAD, null,
988	<	new WNode(null, null)))
989	<	wtail = whead;
987	>	WNode h = new WNode(WMODE, null);
988	>	if (U.compareAndSwapObject(this, WHEAD, null, h))
989	>	wtail = h;
990		}
991	+	else if (spins < 0)
992	+	spins = (p == whead) ? SPINS : 0;
993		else if (node == null)
994	<	node = new WNode(Thread.currentThread(), p);
994	>	node = new WNode(WMODE, p);
995		else if (node.prev != p)
996		node.prev = p;
997		else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
998		p.next = node;
999	<	for (int headSpins = SPINS;;) {
1000	<	WNode np, pp; int ps;
1001	<	while ((np = node.prev) != p && np != null)
1002	<	(p = np).next = node; // stale
1003	<	if (p == whead) {
1004	<	for (int k = headSpins;;) {
1005	<	if (((s = state) & ABITS) == 0L) {
1006	<	if (U.compareAndSwapLong(this, STATE,
1007	<	s, next = s + WBIT)) {
1008	<	whead = node;
1009	<	node.thread = null;
1010	<	node.prev = null;
1011	<	return next;
1012	<	}
1013	<	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;
999	>	break;
1000	>	}
1001	>	}
1002	>
1003	>	for (int spins = SPINS;;) {
1004	>	WNode np, pp; int ps; long s, ns; Thread w;
1005	>	while ((np = node.prev) != p && np != null)
1006	>	(p = np).next = node;   // stale
1007	>	if (whead == p) {
1008	>	for (int k = spins;;) { // spin at head
1009	>	if (((s = state) & ABITS) == 0L) {
1010	>	if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1011	>	whead = node;
1012	>	node.prev = null;
1013	>	return ns;
1014		}
1015		}
1016	<	else {
1017	<	long time; // 0 argument to park means no timeout
1018	<	if (deadline == 0L)
994	<	time = 0L;
995	<	else if ((time = deadline - System.nanoTime()) <= 0L)
996	<	return cancelWriter(node, false);
997	<	if (node.prev == p && p.status == WAITING &&
998	<	(p != whead || (state & WBIT) != 0L)) // recheck
999	<	U.park(false, time);
1000	<	if (interruptible && Thread.interrupted())
1001	<	return cancelWriter(node, true);
1002	<	}
1016	>	else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1017	>	--k <= 0)
1018	>	break;
1019		}
1020	+	if (spins < MAX_HEAD_SPINS)
1021	+	spins <<= 1;
1022	+	}
1023	+	if ((ps = p.status) == 0)
1024	+	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1025	+	else if (ps == CANCELLED) {
1026	+	if ((pp = p.prev) != null) {
1027	+	node.prev = pp;
1028	+	pp.next = node;
1029	+	}
1030	+	}
1031	+	else {
1032	+	long time; // 0 argument to park means no timeout
1033	+	if (deadline == 0L)
1034	+	time = 0L;
1035	+	else if ((time = deadline - System.nanoTime()) <= 0L)
1036	+	return cancelWaiter(node, null, false);
1037	+	node.thread = Thread.currentThread();
1038	+	if (node.prev == p && p.status == WAITING && // recheck
1039	+	(p != whead || (state & ABITS) != 0L))
1040	+	U.park(false, time);
1041	+	node.thread = null;
1042	+	if (interruptible && Thread.interrupted())
1043	+	return cancelWaiter(node, null, true);
1044		}
1045		}
1046		}
1047
1048		/**
1049	<	* If node non-null, forces cancel status and unsplices from queue
1050	<	* if possible. This is a variant of cancellation methods in
1051	<	* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1052	<	* internal documentation) that more conservatively wakes up other
1053	<	* threads that may have had their links changed, so as to preserve
1054	<	* liveness in the main signalling methods.
1049	>	* See above for explanation.
1050	>	*
1051	>	* @param interruptible true if should check interrupts and if so
1052	>	* return INTERRUPTED
1053	>	* @param deadline if nonzero, the System.nanoTime value to timeout
1054	>	* at (and return zero)
1055	>	* @return next state, or INTERRUPTED
1056		*/
1057	<	private long cancelWriter(WNode node, boolean interrupted) {
1058	<	if (node != null) {
1059	<	node.thread = null;
1060	<	node.status = CANCELLED;
1061	<	for (WNode pred = node.prev; pred != null; ) {
1062	<	WNode succ, pp; Thread w;
1063	<	while ((succ = node.next) == null || succ.status == CANCELLED) {
1064	<	WNode q = null;
1065	<	for (WNode t = wtail; t != null && t != node; t = t.prev)
1066	<	if (t.status != CANCELLED)
1067	<	q = t;
1068	<	if (succ == q ||
1069	<	U.compareAndSwapObject(node, WNEXT, succ, succ = q)) {
1070	<	if (succ == null && node == wtail)
1071	<	U.compareAndSwapObject(this, WTAIL, node, pred);
1072	<	break;
1057	>	private long acquireRead(boolean interruptible, long deadline) {
1058	>	WNode node = null, group = null, p;
1059	>	for (int spins = -1;;) {
1060	>	for (;;) {
1061	>	long s, m, ns; WNode h, q; Thread w; // anti-barging guard
1062	>	if (group == null && (h = whead) != null &&
1063	>	(q = h.next) != null && q.mode != RMODE)
1064	>	break;
1065	>	if ((m = (s = state) & ABITS) < RFULL ?
1066	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1067	>	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1068	>	if (group != null) {  // help release others
1069	>	for (WNode r = group;;) {
1070	>	if ((w = r.thread) != null) {
1071	>	r.thread = null;
1072	>	U.unpark(w);
1073	>	}
1074	>	if ((r = group.cowait) == null)
1075	>	break;
1076	>	U.compareAndSwapObject(group, WCOWAIT, r, r.cowait);
1077	>	}
1078		}
1079	+	return ns;
1080		}
1081	<	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)
1081	>	if (m >= WBIT)
1082		break;
1040	–	node.prev = pp; // repeat for new pred
1041	–	U.compareAndSwapObject(pp, WNEXT, pred, succ);
1042	–	pred = pp;
1083		}
1084	<	}
1085	<	writerPrefSignal();
1086	<	return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1047	<	}
1048	<
1049	<	/**
1050	<	* Waits for read lock or timeout or interrupt. The form of
1051	<	* awaitRead differs from awaitWrite mainly because it must
1052	<	* restart (with a new wait node) if the thread was unqueued and
1053	<	* unparked but could not the obtain lock.  We also need to help
1054	<	* with preference rules by not trying to acquire the lock before
1055	<	* enqueuing if there is a known waiting writer, but also helping
1056	<	* to release those threads that are still queued from the last
1057	<	* release.
1058	<	*/
1059	<	private long awaitRead(long stamp, boolean interruptible, long deadline) {
1060	<	long seq = stamp & SBITS;
1061	<	RNode node = null;
1062	<	boolean queued = false;
1063	<	for (int r = 0, headSpins = SPINS, spins = -1;;) {
1064	<	long s, m, next; RNode p; WNode wh; Thread w;
1065	<	if ((m = (s = state) & ABITS) != WBIT &&
1066	<	((s & SBITS) != seq || (wh = whead) == null ||
1067	<	wh.status == 0)) {
1068	<	if (m < RFULL ?
1069	<	U.compareAndSwapLong(this, STATE, s, next = s + RUNIT) :
1070	<	(next = tryIncReaderOverflow(s)) != 0L) {
1071	<	if (node != null && (w = node.waiter) != null)
1072	<	U.compareAndSwapObject(node, WAITER, w, null);
1073	<	if ((p = rhead) != null && (s & SBITS) != p.seq &&
1074	<	U.compareAndSwapObject(this, RHEAD, p, p.next) &&
1075	<	(w = p.waiter) != null &&
1076	<	U.compareAndSwapObject(p, WAITER, w, null))
1077	<	U.unpark(w); // help signal other waiters
1078	<	return next;
1079	<	}
1084	>	if (spins > 0) {
1085	>	if (ThreadLocalRandom.current().nextInt() >= 0)
1086	>	--spins;
1087		}
1088	<	else if (m != WBIT && (p = rhead) != null &&
1089	<	(s & SBITS) != p.seq) { // help release old readers
1090	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
1091	<	(w = p.waiter) != null &&
1085	<	U.compareAndSwapObject(p, WAITER, w, null))
1086	<	U.unpark(w);
1088	>	else if ((p = wtail) == null) {
1089	>	WNode h = new WNode(WMODE, null);
1090	>	if (U.compareAndSwapObject(this, WHEAD, null, h))
1091	>	wtail = h;
1092		}
1093	<	else if (queued && node != null && node.waiter == null) {
1094	<	node = null;    // restart
1095	<	queued = false;
1096	<	spins = -1;
1097	<	}
1098	<	else if (spins < 0) {
1099	<	if (rhead != node)
1100	<	spins = 0;
1101	<	else if ((spins = headSpins) < MAX_HEAD_SPINS && node != null)
1102	<	headSpins <<= 1;
1093	>	else if (spins < 0)
1094	>	spins = (p == whead) ? SPINS : 0;
1095	>	else if (node == null)
1096	>	node = new WNode(WMODE, p);
1097	>	else if (node.prev != p)
1098	>	node.prev = p;
1099	>	else if (p.mode == RMODE && p != whead) {
1100	>	WNode pp = p.prev;  // become co-waiter with group p
1101	>	if (pp != null && p == wtail &&
1102	>	U.compareAndSwapObject(p, WCOWAIT,
1103	>	node.cowait = p.cowait, node)) {
1104	>	node.thread = Thread.currentThread();
1105	>	for (long time;;) {
1106	>	if (interruptible && Thread.interrupted())
1107	>	return cancelWaiter(node, p, true);
1108	>	if (deadline == 0L)
1109	>	time = 0L;
1110	>	else if ((time = deadline - System.nanoTime()) <= 0L)
1111	>	return cancelWaiter(node, p, false);
1112	>	if (node.thread == null)
1113	>	break;
1114	>	if (p.prev != pp || p.status == CANCELLED ||
1115	>	p == whead || p.prev != pp) {
1116	>	node.thread = null;
1117	>	break;
1118	>	}
1119	>	if (node.thread == null) // must recheck
1120	>	break;
1121	>	U.park(false, time);
1122	>	}
1123	>	group = p;
1124	>	}
1125	>	node = null; // throw away
1126		}
1127	<	else if (spins > 0) {
1128	<	if ((r = nextRandom(r)) >= 0)
1129	<	--spins;
1127	>	else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
1128	>	p.next = node;
1129	>	break;
1130		}
1131	<	else if (node == null)
1132	<	node = new RNode(seq, Thread.currentThread());
1133	<	else if (!queued) {
1134	<	if (queued = U.compareAndSwapObject(this, RHEAD,
1135	<	node.next = rhead, node))
1136	<	spins = -1;
1131	>	}
1132	>
1133	>	for (int spins = SPINS;;) {
1134	>	WNode np, pp, r; int ps; long m, s, ns; Thread w;
1135	>	while ((np = node.prev) != p && np != null)
1136	>	(p = np).next = node;
1137	>	if (whead == p) {
1138	>	for (int k = spins;;) {
1139	>	if ((m = (s = state) & ABITS) != WBIT) {
1140	>	if (m < RFULL ?
1141	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT):
1142	>	(ns = tryIncReaderOverflow(s)) != 0L) {
1143	>	whead = node;
1144	>	node.prev = null;
1145	>	while ((r = node.cowait) != null) {
1146	>	if (U.compareAndSwapObject(node, WCOWAIT,
1147	>	r, r.cowait) &&
1148	>	(w = r.thread) != null) {
1149	>	r.thread = null;
1150	>	U.unpark(w); // release co-waiter
1151	>	}
1152	>	}
1153	>	return ns;
1154	>	}
1155	>	}
1156	>	else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1157	>	--k <= 0)
1158	>	break;
1159	>	}
1160	>	if (spins < MAX_HEAD_SPINS)
1161	>	spins <<= 1;
1162	>	}
1163	>	if ((ps = p.status) == 0)
1164	>	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1165	>	else if (ps == CANCELLED) {
1166	>	if ((pp = p.prev) != null) {
1167	>	node.prev = pp;
1168	>	pp.next = node;
1169	>	}
1170		}
1171		else {
1172		long time;
1173		if (deadline == 0L)
1174		time = 0L;
1175		else if ((time = deadline - System.nanoTime()) <= 0L)
1176	<	return cancelReader(node, false);
1177	<	if ((state & WBIT) != 0L && node.waiter != null) // recheck
1176	>	return cancelWaiter(node, null, false);
1177	>	node.thread = Thread.currentThread();
1178	>	if (node.prev == p && p.status == WAITING &&
1179	>	(p != whead || (state & ABITS) != WBIT))
1180		U.park(false, time);
1181	+	node.thread = null;
1182		if (interruptible && Thread.interrupted())
1183	<	return cancelReader(node, true);
1183	>	return cancelWaiter(node, null, true);
1184		}
1185		}
1186		}
1187
1188		/**
1189	<	* If node non-null, forces cancel status and unsplices from queue
1190	<	* if possible, by traversing entire queue looking for cancelled
1191	<	* nodes.
1189	>	* If node non-null, forces cancel status and unsplices it from
1190	>	* queue if possible and wakes up any cowaiters. This is a variant
1191	>	* of cancellation methods in AbstractQueuedSynchronizer (see its
1192	>	* detailed explanation in AQS internal documentation) that more
1193	>	* conservatively wakes up other threads that may have had their
1194	>	* links changed, so as to preserve liveness in the main
1195	>	* signalling methods.
1196	>	*
1197	>	* @param node if nonnull, the waiter
1198	>	* @param group, if nonnull, the group current thread is cowaiting with
1199	>	* @param interrupted if already interrupted
1200	>	* @return INTERRUPTED if interrupted or Thread.interrupted, else zero
1201		*/
1202	<	private long cancelReader(RNode node, boolean interrupted) {
1203	<	Thread w;
1204	<	if (node != null && (w = node.waiter) != null &&
1205	<	U.compareAndSwapObject(node, WAITER, w, null)) {
1206	<	for (RNode pred = null, p = rhead; p != null;) {
1207	<	RNode q = p.next;
1208	<	if (p.waiter == null) {
1209	<	if (pred == null) {
1210	<	U.compareAndSwapObject(this, RHEAD, p, q);
1211	<	p = rhead;
1212	<	}
1140	<	else {
1141	<	U.compareAndSwapObject(pred, RNEXT, p, q);
1142	<	p = pred.next;
1143	<	}
1202	>	private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1203	>	if (node != null) {
1204	>	node.thread = null;
1205	>	node.status = CANCELLED;
1206	>	Thread w; // wake up co-waiters; unsplice cancelled ones
1207	>	for (WNode q, p = (group != null) ? group : node; p != null; ) {
1208	>	if ((q = p.cowait) == null)
1209	>	break;
1210	>	if ((w = q.thread) != null) {
1211	>	q.thread = null;
1212	>	U.unpark(w);
1213		}
1214	<	else {
1215	<	pred = p;
1214	>	if (q.status == CANCELLED)
1215	>	U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1216	>	else
1217		p = q;
1218	+	}
1219	+	if (group == null)  {        // unsplice both prev and next links
1220	+	for (WNode pred = node.prev; pred != null; ) {
1221	+	WNode succ, pp;      // first unsplice next
1222	+	while ((succ = node.next) == null ||
1223	+	succ.status == CANCELLED) {
1224	+	WNode q = null;  // find successor the slow way
1225	+	for (WNode t = wtail; t != null && t != node; t = t.prev)
1226	+	if (t.status != CANCELLED)
1227	+	q = t;   // don't link if succ cancelled
1228	+	if (succ == q || // ensure accurate successor
1229	+	U.compareAndSwapObject(node, WNEXT,
1230	+	succ, succ = q)) {
1231	+	if (succ == null && node == wtail)
1232	+	U.compareAndSwapObject(this, WTAIL, node, pred);
1233	+	break;
1234	+	}
1235	+	}
1236	+	if (pred.next == node) // unsplice pred link
1237	+	U.compareAndSwapObject(pred, WNEXT, node, succ);
1238	+	if (succ != null && (w = succ.thread) != null) {
1239	+	succ.thread = null;
1240	+	U.unpark(w);      // conservatively wake up new succ
1241	+	}
1242	+	if (pred.status != CANCELLED || (pp = pred.prev) == null)
1243	+	break;
1244	+	node.prev = pp; // repeat in case new pred wrong/cancelled
1245	+	U.compareAndSwapObject(pp, WNEXT, pred, succ);
1246	+	pred = pp;
1247		}
1248		}
1249		}
1250	<	readerPrefSignal();
1250	>	release(whead);
1251		return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1252		}
1253
1254		// Unsafe mechanics
1255		private static final sun.misc.Unsafe U;
1256		private static final long STATE;
1158	–	private static final long RHEAD;
1257		private static final long WHEAD;
1258		private static final long WTAIL;
1161	–	private static final long RNEXT;
1259		private static final long WNEXT;
1260	<	private static final long WPREV;
1261	<	private static final long WAITER;
1165	<	private static final long STATUS;
1260	>	private static final long WSTATUS;
1261	>	private static final long WCOWAIT;
1262
1263		static {
1264		try {
1265		U = getUnsafe();
1266		Class<?> k = StampedLock.class;
1171	–	Class<?> rk = RNode.class;
1267		Class<?> wk = WNode.class;
1268		STATE = U.objectFieldOffset
1269		(k.getDeclaredField("state"));
1175	–	RHEAD = U.objectFieldOffset
1176	–	(k.getDeclaredField("rhead"));
1270		WHEAD = U.objectFieldOffset
1271		(k.getDeclaredField("whead"));
1272		WTAIL = U.objectFieldOffset
1273		(k.getDeclaredField("wtail"));
1274	<	RNEXT = U.objectFieldOffset
1182	<	(rk.getDeclaredField("next"));
1183	<	WAITER = U.objectFieldOffset
1184	<	(rk.getDeclaredField("waiter"));
1185	<	STATUS = U.objectFieldOffset
1274	>	WSTATUS = U.objectFieldOffset
1275		(wk.getDeclaredField("status"));
1276		WNEXT = U.objectFieldOffset
1277		(wk.getDeclaredField("next"));
1278	<	WPREV = U.objectFieldOffset
1279	<	(wk.getDeclaredField("prev"));
1278	>	WCOWAIT = U.objectFieldOffset
1279	>	(wk.getDeclaredField("cowait"));
1280
1281		} catch (Exception e) {
1282		throw new Error(e);
#	Line 1204 | Line 1293 | public class StampedLock implements java
1293		private static sun.misc.Unsafe getUnsafe() {
1294		try {
1295		return sun.misc.Unsafe.getUnsafe();
1296	<	} catch (SecurityException se) {
1297	<	try {
1298	<	return java.security.AccessController.doPrivileged
1299	<	(new java.security
1300	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1301	<	public sun.misc.Unsafe run() throws Exception {
1302	<	java.lang.reflect.Field f = sun.misc
1303	<	.Unsafe.class.getDeclaredField("theUnsafe");
1304	<	f.setAccessible(true);
1305	<	return (sun.misc.Unsafe) f.get(null);
1306	<	}});
1307	<	} catch (java.security.PrivilegedActionException e) {
1308	<	throw new RuntimeException("Could not initialize intrinsics",
1309	<	e.getCause());
1310	<	}
1296	>	} catch (SecurityException tryReflectionInstead) {}
1297	>	try {
1298	>	return java.security.AccessController.doPrivileged
1299	>	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1300	>	public sun.misc.Unsafe run() throws Exception {
1301	>	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1302	>	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1303	>	f.setAccessible(true);
1304	>	Object x = f.get(null);
1305	>	if (k.isInstance(x))
1306	>	return k.cast(x);
1307	>	}
1308	>	throw new NoSuchFieldError("the Unsafe");
1309	>	}});
1310	>	} catch (java.security.PrivilegedActionException e) {
1311	>	throw new RuntimeException("Could not initialize intrinsics",
1312	>	e.getCause());
1313		}
1314		}
1224	–
1315		}

Diff Legend

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