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.15 by jsr166, Sun Oct 14 16:42:07 2012 UTC vs.
Revision 1.30 by jsr166, Thu Jan 24 04:10:44 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 61 | Line 65 | import java.util.concurrent.TimeUnit;
65		* help reduce some of the code bloat that otherwise occurs in
66		* retry-based designs.
67		*
68	<	* <p>StampedLocks are designed for use in a different (and generally
69	<	* narrower) range of contexts than most other locks: They are not
70	<	* reentrant, so locked bodies should not call other unknown methods
71	<	* that may try to re-acquire locks (although you may pass a stamp to
72	<	* other methods that can use or convert it). Unvalidated optimistic
73	<	* read sections should further not call methods that are not known to
68	>	* <p>StampedLocks are designed for use as internal utilities in the
69	>	* development of thread-safe components. Their use relies on
70	>	* knowledge of the internal properties of the data, objects, and
71	>	* methods they are protecting.  They are not reentrant, so locked
72	>	* bodies should not call other unknown methods that may try to
73	>	* re-acquire locks (although you may pass a stamp to other methods
74	>	* that can use or convert it).  The use of read lock modes relies on
75	>	* the associated code sections being side-effect-free.  Unvalidated
76	>	* optimistic read sections cannot call methods that are not known to
77		* tolerate potential inconsistencies.  Stamps use finite
78		* representations, and are not cryptographically secure (i.e., a
79		* valid stamp may be guessable). Stamp values may recycle after (no
#	Line 77 | 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 122 | Line 137 | import java.util.concurrent.TimeUnit;
137		*   }
138		*
139		*   double distanceFromOriginV2() { // combines code paths
140	+	*     double currentX = 0.0, currentY = 0.0;
141		*     for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) {
126	–	*       double currentX, currentY;
142		*       try {
143		*         currentX = x;
144		*         currentY = y;
145		*       } finally {
146		*         if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
147	<	*           return Math.sqrt(currentX * currentX + currentY * currentY);
147	>	*           break;
148		*       }
149		*     }
150	+	*     return Math.sqrt(currentX * currentX + currentY * currentY);
151		*   }
152		*
153		*   void moveIfAtOrigin(double newX, double newY) { // upgrade
#	Line 139 | Line 155 | import java.util.concurrent.TimeUnit;
155		*     long stamp = sl.readLock();
156		*     try {
157		*       while (x == 0.0 && y == 0.0) {
158	<	*         long ws = tryConvertToWriteLock(stamp);
158	>	*         long ws = sl.tryConvertToWriteLock(stamp);
159		*         if (ws != 0L) {
160		*           stamp = ws;
161		*           x = newX;
#	Line 152 | Line 168 | import java.util.concurrent.TimeUnit;
168		*         }
169		*       }
170		*     } finally {
171	<	*        sl.unlock(stamp);
171	>	*       sl.unlock(stamp);
172		*     }
173		*   }
174		* }}</pre>
#	Line 169 | Line 185 | public class StampedLock implements java
185		* http://www.lameter.com/gelato2005.pdf
186		* and elsewhere; see
187		* Boehm's http://www.hpl.hp.com/techreports/2012/HPL-2012-68.html)
188	<	* Ordered RW locks (see Shirako et al
188	>	* and Ordered RW locks (see Shirako et al
189		* http://dl.acm.org/citation.cfm?id=2312015)
174	–	* and Phase-Fair locks (see Brandenburg & Anderson, especially
175	–	* http://www.cs.unc.edu/~bbb/diss/).
190		*
191		* Conceptually, the primary state of the lock includes a sequence
192		* number that is odd when write-locked and even otherwise.
#	Line 185 | Line 199 | public class StampedLock implements java
199		* reader count value (RBITS) as a spinlock protecting overflow
200		* updates.
201		*
202	<	* Waiting readers and writers use different queues. The writer
203	<	* queue is a modified form of CLH lock.  (For discussion of CLH,
204	<	* see the internal documentation of AbstractQueuedSynchronizer.)
205	<	* The reader "queue" is a form of Treiber stack, that supports
206	<	* simpler/faster operations because order within a queue doesn't
207	<	* matter and all are signalled at once.  However the sequence of
208	<	* threads within the queue vs the current stamp does matter (see
209	<	* Shirako et al) so each carries its incoming stamp value.
210	<	* Waiting writers never need to track sequence values, so they
211	<	* don't.
212	<	*
213	<	* These queue mechanics hardwire the scheduling policy.  Ignoring
214	<	* trylocks, cancellation, and spinning, they implement Phase-Fair
215	<	* preferences:
216	<	*   1. Unlocked writers prefer to signal waiting readers
217	<	*   2. Fully unlocked readers prefer to signal waiting writers
204	<	*   3. When read-locked and a waiting writer exists, the writer
205	<	*      is preferred to incoming readers
202	>	* Waiters use a modified form of CLH lock used in
203	>	* AbstractQueuedSynchronizer (see its internal documentation for
204	>	* a fuller account), where each node is tagged (field mode) as
205	>	* either a reader or writer. Sets of waiting readers are grouped
206	>	* (linked) under a common node (field cowait) so act as a single
207	>	* node with respect to most CLH mechanics.  By virtue of the
208	>	* queue structure, wait nodes need not actually carry sequence
209	>	* numbers; we know each is greater than its predecessor.  This
210	>	* simplifies the scheduling policy to a mainly-FIFO scheme that
211	>	* incorporates elements of Phase-Fair locks (see Brandenburg &
212	>	* Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
213	>	* particular, we use the phase-fair anti-barging rule: If an
214	>	* incoming reader arrives while read lock is held but there is a
215	>	* queued writer, this incoming reader is queued.  (This rule is
216	>	* responsible for some of the complexity of method acquireRead,
217	>	* but without it, the lock becomes highly unfair.)
218		*
219		* These rules apply to threads actually queued. All tryLock forms
220		* opportunistically try to acquire locks regardless of preference
221	<	* rules, and so may "barge" their way in.  Additionally, initial
222	<	* phases of the await* methods (invoked from readLock() and
223	<	* writeLock()) use controlled spins that have similar effect.
224	<	* Phase-fair preferences may also be broken on cancellations due
225	<	* to timeouts and interrupts.  Rule #3 (incoming readers when a
226	<	* waiting writer) is approximated with varying precision in
227	<	* different contexts -- some checks do not account for
228	<	* in-progress spins/signals, and others do not account for
229	<	* cancellations.
230	<	*
231	<	* Controlled, randomized spinning is used in the two await
232	<	* methods to reduce (increasingly expensive) context switching
233	<	* while also avoiding sustained memory thrashing among many
234	<	* threads.  Both await methods use a similar spin strategy: If
235	<	* the associated queue appears to be empty, then the thread
236	<	* spin-waits up to SPINS times (where each iteration decreases
225	<	* spin count with 50% probablility) before enqueing, and then, if
226	<	* it is the first thread to be enqueued, spins again up to SPINS
227	<	* times before blocking. If, upon wakening it fails to obtain
228	<	* lock, and is still (or becomes) the first waiting thread (which
229	<	* indicates that some other thread barged and obtained lock), it
230	<	* escalates spins (up to MAX_HEAD_SPINS) to reduce the likelihood
231	<	* of continually losing to barging threads.
221	>	* rules, and so may "barge" their way in.  Randomized spinning is
222	>	* used in the acquire methods to reduce (increasingly expensive)
223	>	* context switching while also avoiding sustained memory
224	>	* thrashing among many threads.  We limit spins to the head of
225	>	* queue. A thread spin-waits up to SPINS times (where each
226	>	* iteration decreases spin count with 50% probability) before
227	>	* blocking. If, upon wakening it fails to obtain lock, and is
228	>	* still (or becomes) the first waiting thread (which indicates
229	>	* that some other thread barged and obtained lock), it escalates
230	>	* spins (up to MAX_HEAD_SPINS) to reduce the likelihood of
231	>	* continually losing to barging threads.
232	>	*
233	>	* Nearly all of these mechanics are carried out in methods
234	>	* acquireWrite and acquireRead, that, as typical of such code,
235	>	* sprawl out because actions and retries rely on consistent sets
236	>	* of locally cached reads.
237		*
238		* As noted in Boehm's paper (above), sequence validation (mainly
239		* method validate()) requires stricter ordering rules than apply
#	Line 247 | Line 252 | public class StampedLock implements java
252		* motivation to further spread out contended locations, but might
253		* be subject to future improvements.
254		*/
255	+	private static final long serialVersionUID = -6001602636862214147L;
256
257		/** Number of processors, for spin control */
258		private static final int NCPU = Runtime.getRuntime().availableProcessors();
259
260		/** Maximum number of retries before blocking on acquisition */
261	<	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1;
261	>	private static final int SPINS = (NCPU > 1) ? 1 << 6 : 0;
262
263		/** Maximum number of retries before re-blocking */
264	<	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1;
264	>	private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 0;
265
266		/** The period for yielding when waiting for overflow spinlock */
267		private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1
#	Line 274 | Line 280 | public class StampedLock implements java
280		// Initial value for lock state; avoid failure value zero
281		private static final long ORIGIN = WBIT << 1;
282
283	<	// Special value from cancelled await methods so caller can throw IE
283	>	// Special value from cancelled acquire methods so caller can throw IE
284		private static final long INTERRUPTED = 1L;
285
286	<	// Values for writer status; order matters
286	>	// Values for node status; order matters
287		private static final int WAITING   = -1;
288		private static final int CANCELLED =  1;
289
290	<	/** Wait nodes for readers */
291	<	static final class RNode {
292	<	final long seq;         // stamp value upon enqueue
287	<	volatile Thread waiter; // null if no longer waiting
288	<	volatile RNode next;
289	<	RNode(long s, Thread w) { seq = s; waiter = w; }
290	<	}
290	>	// Modes for nodes (int not boolean to allow arithmetic)
291	>	private static final int RMODE = 0;
292	>	private static final int WMODE = 1;
293
294	<	/** Wait nodes for writers */
294	>	/** Wait nodes */
295		static final class WNode {
294	–	volatile int status;   // 0, WAITING, or CANCELLED
296		volatile WNode prev;
297		volatile WNode next;
298	<	volatile Thread thread;
299	<	WNode(Thread t, WNode p) { thread = t; prev = p; }
298	>	volatile WNode cowait;    // list of linked readers
299	>	volatile Thread thread;   // non-null while possibly parked
300	>	volatile int status;      // 0, WAITING, or CANCELLED
301	>	final int mode;           // RMODE or WMODE
302	>	WNode(int m, WNode p) { mode = m; prev = p; }
303		}
304
305	<	/** Head of writer CLH queue */
305	>	/** Head of CLH queue */
306		private transient volatile WNode whead;
307	<	/** Tail (last) of writer CLH queue */
307	>	/** Tail (last) of CLH queue */
308		private transient volatile WNode wtail;
309	<	/** Head of read queue  */
310	<	private transient volatile RNode rhead;
311	<	/** The state of the lock -- high bits hold sequence, low bits read count */
309	>
310	>	// views
311	>	transient ReadLockView readLockView;
312	>	transient WriteLockView writeLockView;
313	>	transient ReadWriteLockView readWriteLockView;
314	>
315	>	/** Lock sequence/state */
316		private transient volatile long state;
317		/** extra reader count when state read count saturated */
318		private transient int readerOverflow;
319
320		/**
321	<	* Creates a new lock initially in unlocked state.
321	>	* Creates a new lock, initially in unlocked state.
322		*/
323		public StampedLock() {
324		state = ORIGIN;
#	Line 323 | Line 331 | public class StampedLock implements java
331		* @return a stamp that can be used to unlock or convert mode
332		*/
333		public long writeLock() {
334	<	long s, next;
335	<	if (((s = state) & ABITS) == 0L &&
336	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
337	<	return next;
330	<	return awaitWrite(false, 0L);
334	>	long s, next;  // bypass acquireWrite in fully unlocked case only
335	>	return ((((s = state) & ABITS) == 0L &&
336	>	U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
337	>	next : acquireWrite(false, 0L));
338		}
339
340		/**
#	Line 338 | Line 345 | public class StampedLock implements java
345		*/
346		public long tryWriteLock() {
347		long s, next;
348	<	if (((s = state) & ABITS) == 0L &&
349	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
350	<	return next;
344	<	return 0L;
348	>	return ((((s = state) & ABITS) == 0L &&
349	>	U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
350	>	next : 0L);
351		}
352
353		/**
354		* Exclusively acquires the lock if it is available within the
355		* given time and the current thread has not been interrupted.
356	+	* Behavior under timeout and interruption matches that specified
357	+	* for method {@link Lock#tryLock(long,TimeUnit)}.
358		*
359		* @return a stamp that can be used to unlock or convert mode,
360		* or zero if the lock is not available
#	Line 357 | Line 365 | public class StampedLock implements java
365		throws InterruptedException {
366		long nanos = unit.toNanos(time);
367		if (!Thread.interrupted()) {
368	<	long s, next, deadline;
369	<	if (((s = state) & ABITS) == 0L &&
362	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
368	>	long next, deadline;
369	>	if ((next = tryWriteLock()) != 0L)
370		return next;
371		if (nanos <= 0L)
372		return 0L;
373		if ((deadline = System.nanoTime() + nanos) == 0L)
374		deadline = 1L;
375	<	if ((next = awaitWrite(true, deadline)) != INTERRUPTED)
375	>	if ((next = acquireWrite(true, deadline)) != INTERRUPTED)
376		return next;
377		}
378		throw new InterruptedException();
#	Line 374 | Line 381 | public class StampedLock implements java
381		/**
382		* Exclusively acquires the lock, blocking if necessary
383		* until available or the current thread is interrupted.
384	+	* Behavior under interruption matches that specified
385	+	* for method {@link Lock#lockInterruptibly()}.
386		*
387		* @return a stamp that can be used to unlock or convert mode
388		* @throws InterruptedException if the current thread is interrupted
389		* before acquiring the lock
390		*/
391		public long writeLockInterruptibly() throws InterruptedException {
392	<	if (!Thread.interrupted()) {
393	<	long s, next;
394	<	if (((s = state) & ABITS) == 0L &&
395	<	U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
387	<	return next;
388	<	if ((next = awaitWrite(true, 0L)) != INTERRUPTED)
389	<	return next;
390	<	}
392	>	long next;
393	>	if (!Thread.interrupted() &&
394	>	(next = acquireWrite(true, 0L)) != INTERRUPTED)
395	>	return next;
396		throw new InterruptedException();
397		}
398
#	Line 398 | Line 403 | public class StampedLock implements java
403		* @return a stamp that can be used to unlock or convert mode
404		*/
405		public long readLock() {
406	<	for (;;) {
407	<	long s, m, next;
408	<	if ((m = (s = state) & ABITS) == 0L ||
409	<	(m < WBIT && whead == wtail)) {
405	<	if (m < RFULL) {
406	<	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
407	<	return next;
408	<	}
409	<	else if ((next = tryIncReaderOverflow(s)) != 0L)
410	<	return next;
411	<	}
412	<	else
413	<	return awaitRead(s, false, 0L);
414	<	}
406	>	long s, next;  // bypass acquireRead on fully unlocked case only
407	>	return ((((s = state) & ABITS) == 0L &&
408	>	U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
409	>	next : acquireRead(false, 0L));
410		}
411
412		/**
#	Line 437 | Line 432 | public class StampedLock implements java
432		/**
433		* Non-exclusively acquires the lock if it is available within the
434		* given time and the current thread has not been interrupted.
435	+	* Behavior under timeout and interruption matches that specified
436	+	* for method {@link Lock#tryLock(long,TimeUnit)}.
437		*
438		* @return a stamp that can be used to unlock or convert mode,
439		* or zero if the lock is not available
#	Line 445 | Line 442 | public class StampedLock implements java
442		*/
443		public long tryReadLock(long time, TimeUnit unit)
444		throws InterruptedException {
445	+	long next, deadline;
446		long nanos = unit.toNanos(time);
447		if (!Thread.interrupted()) {
448	<	for (;;) {
449	<	long s, m, next, deadline;
450	<	if ((m = (s = state) & ABITS) == WBIT ||
451	<	(m != 0L && whead != wtail)) {
452	<	if (nanos <= 0L)
453	<	return 0L;
454	<	if ((deadline = System.nanoTime() + nanos) == 0L)
455	<	deadline = 1L;
458	<	if ((next = awaitRead(s, true, deadline)) != INTERRUPTED)
459	<	return next;
460	<	break;
461	<	}
462	<	else if (m < RFULL) {
463	<	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
464	<	return next;
465	<	}
466	<	else if ((next = tryIncReaderOverflow(s)) != 0L)
467	<	return next;
468	<	}
448	>	if ((next = tryReadLock()) != 0L)
449	>	return next;
450	>	if (nanos <= 0L)
451	>	return 0L;
452	>	if ((deadline = System.nanoTime() + nanos) == 0L)
453	>	deadline = 1L;
454	>	if ((next = acquireRead(true, deadline)) != INTERRUPTED)
455	>	return next;
456		}
457		throw new InterruptedException();
458		}
#	Line 473 | Line 460 | public class StampedLock implements java
460		/**
461		* Non-exclusively acquires the lock, blocking if necessary
462		* until available or the current thread is interrupted.
463	+	* Behavior under interruption matches that specified
464	+	* for method {@link Lock#lockInterruptibly()}.
465		*
466		* @return a stamp that can be used to unlock or convert mode
467		* @throws InterruptedException if the current thread is interrupted
468		* before acquiring the lock
469		*/
470		public long readLockInterruptibly() throws InterruptedException {
471	<	if (!Thread.interrupted()) {
472	<	for (;;) {
473	<	long s, next, m;
474	<	if ((m = (s = state) & ABITS) == WBIT ||
486	<	(m != 0L && whead != wtail)) {
487	<	if ((next = awaitRead(s, true, 0L)) != INTERRUPTED)
488	<	return next;
489	<	break;
490	<	}
491	<	else if (m < RFULL) {
492	<	if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
493	<	return next;
494	<	}
495	<	else if ((next = tryIncReaderOverflow(s)) != 0L)
496	<	return next;
497	<	}
498	<	}
471	>	long next;
472	>	if (!Thread.interrupted() &&
473	>	(next = acquireRead(true, 0L)) != INTERRUPTED)
474	>	return next;
475		throw new InterruptedException();
476		}
477
#	Line 511 | Line 487 | public class StampedLock implements java
487		}
488
489		/**
490	<	* Returns true if the lock has not been exclusively held since
491	<	* issuance of the given stamp. Always returns false if the stamp
492	<	* is zero. Always returns true if the stamp represents a
490	>	* Returns true if the lock has not been exclusively acquired
491	>	* since issuance of the given stamp. Always returns false if the
492	>	* stamp is zero. Always returns true if the stamp represents a
493		* currently held lock.
494		*
495	<	* @return true if the lock has not been exclusively held since
496	<	* issuance of the given stamp; else false
495	>	* @return true if the lock has not been exclusively acquired
496	>	* since issuance of the given stamp; else false
497		*/
498		public boolean validate(long stamp) {
499	+	// See above about current use of getLongVolatile here
500		return (stamp & SBITS) == (U.getLongVolatile(this, STATE) & SBITS);
501		}
502
#	Line 532 | Line 509 | public class StampedLock implements java
509		* not match the current state of this lock
510		*/
511		public void unlockWrite(long stamp) {
512	+	WNode h;
513		if (state != stamp || (stamp & WBIT) == 0L)
514		throw new IllegalMonitorStateException();
515		state = (stamp += WBIT) == 0L ? ORIGIN : stamp;
516	<	readerPrefSignal();
516	>	if ((h = whead) != null && h.status != 0)
517	>	release(h);
518		}
519
520		/**
#	Line 547 | Line 526 | public class StampedLock implements java
526		* not match the current state of this lock
527		*/
528		public void unlockRead(long stamp) {
529	<	long s, m;
530	<	if ((stamp & RBITS) != 0L) {
531	<	while (((s = state) & SBITS) == (stamp & SBITS)) {
532	<	if ((m = s & ABITS) == 0L)
529	>	long s, m; WNode h;
530	>	for (;;) {
531	>	if (((s = state) & SBITS) != (stamp & SBITS) ||
532	>	(stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
533	>	throw new IllegalMonitorStateException();
534	>	if (m < RFULL) {
535	>	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
536	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
537	>	release(h);
538		break;
555	–	else if (m < RFULL) {
556	–	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
557	–	if (m == RUNIT)
558	–	writerPrefSignal();
559	–	return;
560	–	}
539		}
562	–	else if (m >= WBIT)
563	–	break;
564	–	else if (tryDecReaderOverflow(s) != 0L)
565	–	return;
540		}
541	+	else if (tryDecReaderOverflow(s) != 0L)
542	+	break;
543		}
568	–	throw new IllegalMonitorStateException();
544		}
545
546		/**
#	Line 577 | Line 552 | public class StampedLock implements java
552		* not match the current state of this lock
553		*/
554		public void unlock(long stamp) {
555	<	long a = stamp & ABITS, m, s;
555	>	long a = stamp & ABITS, m, s; WNode h;
556		while (((s = state) & SBITS) == (stamp & SBITS)) {
557		if ((m = s & ABITS) == 0L)
558		break;
#	Line 585 | Line 560 | public class StampedLock implements java
560		if (a != m)
561		break;
562		state = (s += WBIT) == 0L ? ORIGIN : s;
563	<	readerPrefSignal();
563	>	if ((h = whead) != null && h.status != 0)
564	>	release(h);
565		return;
566		}
567		else if (a == 0L || a >= WBIT)
568		break;
569		else if (m < RFULL) {
570		if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
571	<	if (m == RUNIT)
572	<	writerPrefSignal();
571	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
572	>	release(h);
573		return;
574		}
575		}
#	Line 604 | Line 580 | public class StampedLock implements java
580		}
581
582		/**
583	<	* If the lock state matches the given stamp then performs one of
583	>	* If the lock state matches the given stamp, performs one of
584		* the following actions. If the stamp represents holding a write
585		* lock, returns it.  Or, if a read lock, if the write lock is
586		* available, releases the read lock and returns a write stamp.
#	Line 629 | Line 605 | public class StampedLock implements java
605		break;
606		return stamp;
607		}
608	<	else if (m == RUNIT && a != 0L && a < WBIT) {
608	>	else if (m == RUNIT && a != 0L) {
609		if (U.compareAndSwapLong(this, STATE, s,
610		next = s - RUNIT + WBIT))
611		return next;
#	Line 641 | Line 617 | public class StampedLock implements java
617		}
618
619		/**
620	<	* If the lock state matches the given stamp then performs one of
620	>	* If the lock state matches the given stamp, performs one of
621		* the following actions. If the stamp represents holding a write
622		* lock, releases it and obtains a read lock.  Or, if a read lock,
623		* returns it. Or, if an optimistic read, acquires a read lock and
#	Line 652 | Line 628 | public class StampedLock implements java
628		* @return a valid read stamp, or zero on failure
629		*/
630		public long tryConvertToReadLock(long stamp) {
631	<	long a = stamp & ABITS, m, s, next;
631	>	long a = stamp & ABITS, m, s, next; WNode h;
632		while (((s = state) & SBITS) == (stamp & SBITS)) {
633		if ((m = s & ABITS) == 0L) {
634		if (a != 0L)
#	Line 667 | Line 643 | public class StampedLock implements java
643		else if (m == WBIT) {
644		if (a != m)
645		break;
646	<	next = state = s + (WBIT + RUNIT);
647	<	readerPrefSignal();
646	>	state = next = s + (WBIT + RUNIT);
647	>	if ((h = whead) != null && h.status != 0)
648	>	release(h);
649		return next;
650		}
651		else if (a != 0L && a < WBIT)
#	Line 690 | Line 667 | public class StampedLock implements java
667		* @return a valid optimistic read stamp, or zero on failure
668		*/
669		public long tryConvertToOptimisticRead(long stamp) {
670	<	long a = stamp & ABITS, m, s, next;
671	<	while (((s = U.getLongVolatile(this, STATE)) &
672	<	SBITS) == (stamp & SBITS)) {
670	>	long a = stamp & ABITS, m, s, next; WNode h;
671	>	for (;;) {
672	>	s = U.getLongVolatile(this, STATE); // see above
673	>	if ((s & SBITS) != (stamp & SBITS))
674	>	break;
675		if ((m = s & ABITS) == 0L) {
676		if (a != 0L)
677		break;
#	Line 701 | Line 680 | public class StampedLock implements java
680		else if (m == WBIT) {
681		if (a != m)
682		break;
683	<	next = state = (s += WBIT) == 0L ? ORIGIN : s;
684	<	readerPrefSignal();
683	>	state = next = (s += WBIT) == 0L ? ORIGIN : s;
684	>	if ((h = whead) != null && h.status != 0)
685	>	release(h);
686		return next;
687		}
688		else if (a == 0L || a >= WBIT)
689		break;
690		else if (m < RFULL) {
691		if (U.compareAndSwapLong(this, STATE, s, next = s - RUNIT)) {
692	<	if (m == RUNIT)
693	<	writerPrefSignal();
692	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
693	>	release(h);
694		return next & SBITS;
695		}
696		}
#	Line 728 | Line 708 | public class StampedLock implements java
708		* @return true if the lock was held, else false
709		*/
710		public boolean tryUnlockWrite() {
711	<	long s;
711	>	long s; WNode h;
712		if (((s = state) & WBIT) != 0L) {
713		state = (s += WBIT) == 0L ? ORIGIN : s;
714	<	readerPrefSignal();
714	>	if ((h = whead) != null && h.status != 0)
715	>	release(h);
716		return true;
717		}
718		return false;
#	Line 745 | Line 726 | public class StampedLock implements java
726		* @return true if the read lock was held, else false
727		*/
728		public boolean tryUnlockRead() {
729	<	long s, m;
729	>	long s, m; WNode h;
730		while ((m = (s = state) & ABITS) != 0L && m < WBIT) {
731		if (m < RFULL) {
732		if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
733	<	if (m == RUNIT)
734	<	writerPrefSignal();
733	>	if (m == RUNIT && (h = whead) != null && h.status != 0)
734	>	release(h);
735		return true;
736		}
737		}
#	Line 775 | Line 756 | public class StampedLock implements java
756		* @return true if the lock is currently held non-exclusively
757		*/
758		public boolean isReadLocked() {
759	<	long m;
779	<	return (m = state & ABITS) > 0L && m < WBIT;
759	>	return (state & RBITS) != 0L;
760		}
761
762		private void readObject(java.io.ObjectInputStream s)
#	Line 785 | Line 765 | public class StampedLock implements java
765		state = ORIGIN; // reset to unlocked state
766		}
767
768	+	/**
769	+	* Returns a plain {@link Lock} view of this StampedLock in which
770	+	* the {@link Lock#lock} method is mapped to {@link #readLock},
771	+	* and similarly for other methods. The returned Lock does not
772	+	* support a {@link Condition}; method {@link
773	+	* Lock#newCondition()} throws {@code
774	+	* UnsupportedOperationException}.
775	+	*
776	+	* @return the lock
777	+	*/
778	+	public Lock asReadLock() {
779	+	ReadLockView v;
780	+	return ((v = readLockView) != null ? v :
781	+	(readLockView = new ReadLockView()));
782	+	}
783	+
784	+	/**
785	+	* Returns a plain {@link Lock} view of this StampedLock in which
786	+	* the {@link Lock#lock} method is mapped to {@link #writeLock},
787	+	* and similarly for other methods. The returned Lock does not
788	+	* support a {@link Condition}; method {@link
789	+	* Lock#newCondition()} throws {@code
790	+	* UnsupportedOperationException}.
791	+	*
792	+	* @return the lock
793	+	*/
794	+	public Lock asWriteLock() {
795	+	WriteLockView v;
796	+	return ((v = writeLockView) != null ? v :
797	+	(writeLockView = new WriteLockView()));
798	+	}
799	+
800	+	/**
801	+	* Returns a {@link ReadWriteLock} view of this StampedLock in
802	+	* which the {@link ReadWriteLock#readLock()} method is mapped to
803	+	* {@link #asReadLock()}, and {@link ReadWriteLock#writeLock()} to
804	+	* {@link #asWriteLock()}.
805	+	*
806	+	* @return the lock
807	+	*/
808	+	public ReadWriteLock asReadWriteLock() {
809	+	ReadWriteLockView v;
810	+	return ((v = readWriteLockView) != null ? v :
811	+	(readWriteLockView = new ReadWriteLockView()));
812	+	}
813	+
814	+	// view classes
815	+
816	+	final class ReadLockView implements Lock {
817	+	public void lock() { readLock(); }
818	+	public void lockInterruptibly() throws InterruptedException {
819	+	readLockInterruptibly();
820	+	}
821	+	public boolean tryLock() { return tryReadLock() != 0L; }
822	+	public boolean tryLock(long time, TimeUnit unit)
823	+	throws InterruptedException {
824	+	return tryReadLock(time, unit) != 0L;
825	+	}
826	+	public void unlock() { unstampedUnlockRead(); }
827	+	public Condition newCondition() {
828	+	throw new UnsupportedOperationException();
829	+	}
830	+	}
831	+
832	+	final class WriteLockView implements Lock {
833	+	public void lock() { writeLock(); }
834	+	public void lockInterruptibly() throws InterruptedException {
835	+	writeLockInterruptibly();
836	+	}
837	+	public boolean tryLock() { return tryWriteLock() != 0L; }
838	+	public boolean tryLock(long time, TimeUnit unit)
839	+	throws InterruptedException {
840	+	return tryWriteLock(time, unit) != 0L;
841	+	}
842	+	public void unlock() { unstampedUnlockWrite(); }
843	+	public Condition newCondition() {
844	+	throw new UnsupportedOperationException();
845	+	}
846	+	}
847	+
848	+	final class ReadWriteLockView implements ReadWriteLock {
849	+	public Lock readLock() { return asReadLock(); }
850	+	public Lock writeLock() { return asWriteLock(); }
851	+	}
852	+
853	+	// Unlock methods without stamp argument checks for view classes.
854	+	// Needed because view-class lock methods throw away stamps.
855	+
856	+	final void unstampedUnlockWrite() {
857	+	WNode h; long s;
858	+	if (((s = state) & WBIT) == 0L)
859	+	throw new IllegalMonitorStateException();
860	+	state = (s += WBIT) == 0L ? ORIGIN : s;
861	+	if ((h = whead) != null && h.status != 0)
862	+	release(h);
863	+	}
864	+
865	+	final void unstampedUnlockRead() {
866	+	for (;;) {
867	+	long s, m; WNode h;
868	+	if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
869	+	throw new IllegalMonitorStateException();
870	+	else if (m < RFULL) {
871	+	if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
872	+	if (m == RUNIT && (h = whead) != null && h.status != 0)
873	+	release(h);
874	+	break;
875	+	}
876	+	}
877	+	else if (tryDecReaderOverflow(s) != 0L)
878	+	break;
879	+	}
880	+	}
881	+
882		// internals
883
884		/**
#	Line 792 | Line 886 | public class StampedLock implements java
886		* access bits value to RBITS, indicating hold of spinlock,
887		* then updating, then releasing.
888		*
889	<	* @param stamp, assumed that (stamp & ABITS) >= RFULL
889	>	* @param s, assumed that (s & ABITS) >= RFULL
890		* @return new stamp on success, else zero
891		*/
892		private long tryIncReaderOverflow(long s) {
#	Line 812 | Line 906 | public class StampedLock implements java
906		/**
907		* Tries to decrement readerOverflow.
908		*
909	<	* @param stamp, assumed that (stamp & ABITS) >= RFULL
909	>	* @param s, assumed that (s & ABITS) >= RFULL
910		* @return new stamp on success, else zero
911		*/
912		private long tryDecReaderOverflow(long s) {
#	Line 836 | Line 930 | public class StampedLock implements java
930		}
931
932		/*
933	<	* The two versions of signal implement the phase-fair policy.
934	<	* They include almost the same code, but repacked in different
935	<	* ways.  Integrating the policy with the mechanics eliminates
936	<	* state rechecks that would be needed with separate reader and
937	<	* writer signal methods.  Both methods assume that they are
938	<	* called when the lock is last known to be available, and
939	<	* continue until the lock is unavailable, or at least one thread
940	<	* is signalled, or there are no more waiting threads.  Signalling
941	<	* a reader entails popping (CASing) from rhead and unparking
942	<	* unless the thread already cancelled (indicated by a null waiter
849	<	* field). Signalling a writer requires finding the first node,
850	<	* i.e., the successor of whead. This is normally just head.next,
851	<	* but may require traversal from wtail if next pointers are
852	<	* lagging. These methods may fail to wake up an acquiring thread
853	<	* when one or more have been cancelled, but the cancel methods
854	<	* themselves provide extra safeguards to ensure liveness.
855	<	*/
856	<
857	<	private void readerPrefSignal() {
858	<	boolean readers = false;
859	<	RNode p; WNode h, q; long s; Thread w;
860	<	while ((p = rhead) != null) {
861	<	if (((s = state) & WBIT) != 0L)
862	<	return;
863	<	if (p.seq == (s & SBITS))
864	<	break;
865	<	readers = true;
866	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
867	<	(w = p.waiter) != null &&
868	<	U.compareAndSwapObject(p, WAITER, w, null))
869	<	U.unpark(w);
870	<	}
871	<	if (!readers && (state & ABITS) == 0L &&
872	<	(h = whead) != null && h.status != 0) {
873	<	U.compareAndSwapInt(h, STATUS, WAITING, 0);
933	>	* Wakes up the successor of h (normally whead). This is normally
934	>	* just h.next, but may require traversal from wtail if next
935	>	* pointers are lagging. This may fail to wake up an acquiring
936	>	* thread when one or more have been cancelled, but the cancel
937	>	* methods themselves provide extra safeguards to ensure liveness.
938	>	*/
939	>	private void release(WNode h) {
940	>	if (h != null) {
941	>	WNode q; Thread w;
942	>	U.compareAndSwapInt(h, WSTATUS, WAITING, 0);
943		if ((q = h.next) == null || q.status == CANCELLED) {
875	–	q = null;
944		for (WNode t = wtail; t != null && t != h; t = t.prev)
945		if (t.status <= 0)
946		q = t;
947		}
948	<	if (q != null && (w = q.thread) != null)
949	<	U.unpark(w);
950	<	}
951	<	}
952	<
953	<	private void writerPrefSignal() {
954	<	RNode p; WNode h, q; long s; Thread w;
955	<	if ((h = whead) != null && h.status != 0) {
956	<	U.compareAndSwapInt(h, STATUS, WAITING, 0);
957	<	if ((q = h.next) == null || q.status == CANCELLED) {
890	<	q = null;
891	<	for (WNode t = wtail; t != null && t != h; t = t.prev)
892	<	if (t.status <= 0)
893	<	q = t;
894	<	}
895	<	if (q != null && (w = q.thread) != null)
896	<	U.unpark(w);
897	<	}
898	<	else {
899	<	while ((p = rhead) != null && ((s = state) & WBIT) == 0L &&
900	<	p.seq != (s & SBITS)) {
901	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
902	<	(w = p.waiter) != null &&
903	<	U.compareAndSwapObject(p, WAITER, w, null))
904	<	U.unpark(w);
948	>	if (q != null) {
949	>	for (WNode r = q;;) {  // release co-waiters too
950	>	if ((w = r.thread) != null) {
951	>	r.thread = null;
952	>	U.unpark(w);
953	>	}
954	>	if ((r = q.cowait) == null)
955	>	break;
956	>	U.compareAndSwapObject(q, WCOWAIT, r, r.cowait);
957	>	}
958		}
959		}
960		}
961
962		/**
963	<	* RNG for local spins. The first call from await{Read,Write}
911	<	* produces a thread-local value. Unless zero, subsequent calls
912	<	* use an xorShift to further reduce memory traffic.
913	<	*/
914	<	private static int nextRandom(int r) {
915	<	if (r == 0)
916	<	return ThreadLocalRandom.current().nextInt();
917	<	r ^= r << 1; // xorshift
918	<	r ^= r >>> 3;
919	<	r ^= r << 10;
920	<	return r;
921	<	}
922	<
923	<	/**
924	<	* Possibly spins trying to obtain write lock, then enqueues and
925	<	* blocks while not head of write queue or cannot acquire lock,
926	<	* possibly spinning when at head; cancelling on timeout or
927	<	* interrupt.
963	>	* See above for explanation.
964		*
965		* @param interruptible true if should check interrupts and if so
966		* return INTERRUPTED
967		* @param deadline if nonzero, the System.nanoTime value to timeout
968		* at (and return zero)
969	+	* @return next state, or INTERRUPTED
970		*/
971	<	private long awaitWrite(boolean interruptible, long deadline) {
972	<	WNode node = null;
973	<	for (int r = 0, spins = -1;;) {
974	<	WNode p; long s, next;
971	>	private long acquireWrite(boolean interruptible, long deadline) {
972	>	WNode node = null, p;
973	>	for (int spins = -1;;) { // spin while enqueuing
974	>	long s, ns;
975		if (((s = state) & ABITS) == 0L) {
976	<	if (U.compareAndSwapLong(this, STATE, s, next = s + WBIT))
977	<	return next;
976	>	if (U.compareAndSwapLong(this, STATE, s, ns = s + WBIT))
977	>	return ns;
978		}
942	–	else if (spins < 0)
943	–	spins = whead == wtail ? SPINS : 0;
979		else if (spins > 0) {
980	<	if ((r = nextRandom(r)) >= 0)
980	>	if (ThreadLocalRandom.current().nextInt() >= 0)
981		--spins;
982		}
983		else if ((p = wtail) == null) { // initialize queue
984	<	if (U.compareAndSwapObject(this, WHEAD, null,
985	<	new WNode(null, null)))
986	<	wtail = whead;
984	>	WNode h = new WNode(WMODE, null);
985	>	if (U.compareAndSwapObject(this, WHEAD, null, h))
986	>	wtail = h;
987		}
988	+	else if (spins < 0)
989	+	spins = (p == whead) ? SPINS : 0;
990		else if (node == null)
991	<	node = new WNode(Thread.currentThread(), p);
991	>	node = new WNode(WMODE, p);
992		else if (node.prev != p)
993		node.prev = p;
994		else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
995		p.next = node;
996	<	for (int headSpins = SPINS;;) {
997	<	WNode np; int ps;
998	<	if ((np = node.prev) != p && np != null &&
999	<	(p = np).next != node)
1000	<	p.next = node; // stale
1001	<	if (p == whead) {
1002	<	for (int k = headSpins;;) {
1003	<	if (((s = state) & ABITS) == 0L) {
1004	<	if (U.compareAndSwapLong(this, STATE,
1005	<	s, next = s + WBIT)) {
1006	<	whead = node;
1007	<	node.thread = null;
1008	<	node.prev = null;
1009	<	return next;
1010	<	}
1011	<	break;
996	>	break;
997	>	}
998	>	}
999	>
1000	>	for (int spins = SPINS;;) {
1001	>	WNode np, pp; int ps; long s, ns; Thread w;
1002	>	while ((np = node.prev) != p && np != null)
1003	>	(p = np).next = node;   // stale
1004	>	if (whead == p) {
1005	>	for (int k = spins;;) { // spin at head
1006	>	if (((s = state) & ABITS) == 0L) {
1007	>	if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1008	>	whead = node;
1009	>	node.prev = null;
1010	>	return ns;
1011	>	}
1012	>	}
1013	>	else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1014	>	--k <= 0)
1015	>	break;
1016	>	}
1017	>	if (spins < MAX_HEAD_SPINS)
1018	>	spins <<= 1;
1019	>	}
1020	>	if ((ps = p.status) == 0)
1021	>	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1022	>	else if (ps == CANCELLED) {
1023	>	if ((pp = p.prev) != null) {
1024	>	node.prev = pp;
1025	>	pp.next = node;
1026	>	}
1027	>	}
1028	>	else {
1029	>	long time; // 0 argument to park means no timeout
1030	>	if (deadline == 0L)
1031	>	time = 0L;
1032	>	else if ((time = deadline - System.nanoTime()) <= 0L)
1033	>	return cancelWaiter(node, null, false);
1034	>	node.thread = Thread.currentThread();
1035	>	if (node.prev == p && p.status == WAITING && // recheck
1036	>	(p != whead || (state & ABITS) != 0L)) {
1037	>	U.park(false, time);
1038	>	if (interruptible && Thread.interrupted())
1039	>	return cancelWaiter(node, null, true);
1040	>	}
1041	>	node.thread = null;
1042	>	}
1043	>	}
1044	>	}
1045	>
1046	>	/**
1047	>	* See above for explanation.
1048	>	*
1049	>	* @param interruptible true if should check interrupts and if so
1050	>	* return INTERRUPTED
1051	>	* @param deadline if nonzero, the System.nanoTime value to timeout
1052	>	* at (and return zero)
1053	>	* @return next state, or INTERRUPTED
1054	>	*/
1055	>	private long acquireRead(boolean interruptible, long deadline) {
1056	>	WNode node = null, group = null, p;
1057	>	for (int spins = -1;;) {
1058	>	for (;;) {
1059	>	long s, m, ns; WNode h, q; Thread w; // anti-barging guard
1060	>	if (group == null && (h = whead) != null &&
1061	>	(q = h.next) != null && q.mode != RMODE)
1062	>	break;
1063	>	if ((m = (s = state) & ABITS) < RFULL ?
1064	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1065	>	(m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1066	>	if (group != null) {  // help release others
1067	>	for (WNode r = group;;) {
1068	>	if ((w = r.thread) != null) {
1069	>	r.thread = null;
1070	>	U.unpark(w);
1071		}
1072	<	if ((r = nextRandom(r)) >= 0 && --k <= 0)
1072	>	if ((r = group.cowait) == null)
1073		break;
1074	+	U.compareAndSwapObject(group, WCOWAIT, r, r.cowait);
1075		}
979	–	if (headSpins < MAX_HEAD_SPINS)
980	–	headSpins <<= 1;
1076		}
1077	<	if ((ps = p.status) == 0)
1078	<	U.compareAndSwapInt(p, STATUS, 0, WAITING);
1079	<	else if (ps == CANCELLED)
1080	<	node.prev = p.prev;
1081	<	else {
1082	<	long time; // 0 argument to park means no timeout
1077	>	return ns;
1078	>	}
1079	>	if (m >= WBIT)
1080	>	break;
1081	>	}
1082	>	if (spins > 0) {
1083	>	if (ThreadLocalRandom.current().nextInt() >= 0)
1084	>	--spins;
1085	>	}
1086	>	else if ((p = wtail) == null) {
1087	>	WNode h = new WNode(WMODE, null);
1088	>	if (U.compareAndSwapObject(this, WHEAD, null, h))
1089	>	wtail = h;
1090	>	}
1091	>	else if (spins < 0)
1092	>	spins = (p == whead) ? SPINS : 0;
1093	>	else if (node == null)
1094	>	node = new WNode(WMODE, p);
1095	>	else if (node.prev != p)
1096	>	node.prev = p;
1097	>	else if (p.mode == RMODE && p != whead) {
1098	>	WNode pp = p.prev;  // become co-waiter with group p
1099	>	if (pp != null && p == wtail &&
1100	>	U.compareAndSwapObject(p, WCOWAIT,
1101	>	node.cowait = p.cowait, node)) {
1102	>	node.thread = Thread.currentThread();
1103	>	for (long time;;) {
1104		if (deadline == 0L)
1105		time = 0L;
1106		else if ((time = deadline - System.nanoTime()) <= 0L)
1107	<	return cancelWriter(node, false);
1108	<	if (node.prev == p && p.status == WAITING &&
1109	<	(p != whead || (state & WBIT) != 0L)) { // recheck
1110	<	U.park(false, time);
1111	<	if (interruptible && Thread.interrupted())
1112	<	return cancelWriter(node, true);
1107	>	return cancelWaiter(node, p, false);
1108	>	if (node.thread == null)
1109	>	break;
1110	>	if (p.prev != pp || p.status == CANCELLED ||
1111	>	p == whead || p.prev != pp) {
1112	>	node.thread = null;
1113	>	break;
1114		}
1115	+	if (node.thread == null) // must recheck
1116	+	break;
1117	+	U.park(false, time);
1118	+	if (interruptible && Thread.interrupted())
1119	+	return cancelWaiter(node, p, true);
1120		}
1121	+	group = p;
1122		}
1123	+	node = null; // throw away
1124		}
1125	<	}
1126	<	}
1127	<
1004	<	/**
1005	<	* If node non-null, forces cancel status and unsplices from queue
1006	<	* if possible. This is a streamlined variant of cancellation
1007	<	* methods in AbstractQueuedSynchronizer that includes a detailed
1008	<	* explanation.
1009	<	*/
1010	<	private long cancelWriter(WNode node, boolean interrupted) {
1011	<	WNode pred;
1012	<	if (node != null && (pred = node.prev) != null) {
1013	<	WNode pp;
1014	<	node.thread = null;
1015	<	while (pred.status == CANCELLED && (pp = pred.prev) != null)
1016	<	pred = node.prev = pp;
1017	<	WNode predNext = pred.next;
1018	<	node.status = CANCELLED;
1019	<	if (predNext != null) {
1020	<	Thread w;
1021	<	WNode succ = node.next;
1022	<	if (succ == null || succ.status == CANCELLED) {
1023	<	succ = null;
1024	<	for (WNode t = wtail; t != null && t != node; t = t.prev)
1025	<	if (t.status <= 0)
1026	<	succ = t;
1027	<	if (succ == null && node == wtail)
1028	<	U.compareAndSwapObject(this, WTAIL, node, pred);
1029	<	}
1030	<	U.compareAndSwapObject(pred, WNEXT, predNext, succ);
1031	<	if (succ != null && (w = succ.thread) != null)
1032	<	U.unpark(w);
1125	>	else if (U.compareAndSwapObject(this, WTAIL, p, node)) {
1126	>	p.next = node;
1127	>	break;
1128		}
1129		}
1035	–	writerPrefSignal();
1036	–	return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1037	–	}
1130
1131	<	/**
1132	<	* Waits for read lock or timeout or interrupt. The form of
1133	<	* awaitRead differs from awaitWrite mainly because it must
1134	<	* restart (with a new wait node) if the thread was unqueued and
1135	<	* unparked but could not the obtain lock.  We also need to help
1136	<	* with preference rules by not trying to acquire the lock before
1137	<	* enqueuing if there is a known waiting writer, but also helping
1138	<	* to release those threads that are still queued from the last
1139	<	* release.
1140	<	*/
1141	<	private long awaitRead(long stamp, boolean interruptible, long deadline) {
1142	<	long seq = stamp & SBITS;
1143	<	RNode node = null;
1144	<	boolean queued = false;
1145	<	for (int r = 0, headSpins = SPINS, spins = -1;;) {
1146	<	long s, m, next; RNode p; WNode wh; Thread w;
1147	<	if ((m = (s = state) & ABITS) != WBIT &&
1148	<	((s & SBITS) != seq || (wh = whead) == null ||
1149	<	wh.status == 0)) {
1150	<	if (m < RFULL ?
1151	<	U.compareAndSwapLong(this, STATE, s, next = s + RUNIT) :
1152	<	(next = tryIncReaderOverflow(s)) != 0L) {
1153	<	if (node != null && (w = node.waiter) != null)
1154	<	U.compareAndSwapObject(node, WAITER, w, null);
1155	<	if ((p = rhead) != null && (s & SBITS) != p.seq &&
1156	<	U.compareAndSwapObject(this, RHEAD, p, p.next) &&
1065	<	(w = p.waiter) != null &&
1066	<	U.compareAndSwapObject(p, WAITER, w, null))
1067	<	U.unpark(w); // help signal other waiters
1068	<	return next;
1131	>	for (int spins = SPINS;;) {
1132	>	WNode np, pp, r; int ps; long m, s, ns; Thread w;
1133	>	while ((np = node.prev) != p && np != null)
1134	>	(p = np).next = node;
1135	>	if (whead == p) {
1136	>	for (int k = spins;;) {
1137	>	if ((m = (s = state) & ABITS) != WBIT) {
1138	>	if (m < RFULL ?
1139	>	U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT):
1140	>	(ns = tryIncReaderOverflow(s)) != 0L) {
1141	>	whead = node;
1142	>	node.prev = null;
1143	>	while ((r = node.cowait) != null) {
1144	>	if (U.compareAndSwapObject(node, WCOWAIT,
1145	>	r, r.cowait) &&
1146	>	(w = r.thread) != null) {
1147	>	r.thread = null;
1148	>	U.unpark(w); // release co-waiter
1149	>	}
1150	>	}
1151	>	return ns;
1152	>	}
1153	>	}
1154	>	else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1155	>	--k <= 0)
1156	>	break;
1157		}
1158	+	if (spins < MAX_HEAD_SPINS)
1159	+	spins <<= 1;
1160		}
1161	<	else if (m != WBIT && (p = rhead) != null &&
1162	<	(s & SBITS) != p.seq) { // help release old readers
1163	<	if (U.compareAndSwapObject(this, RHEAD, p, p.next) &&
1164	<	(w = p.waiter) != null &&
1165	<	U.compareAndSwapObject(p, WAITER, w, null))
1166	<	U.unpark(w);
1167	<	}
1078	<	else if (queued && node != null && node.waiter == null) {
1079	<	node = null;    // restart
1080	<	queued = false;
1081	<	spins = -1;
1082	<	}
1083	<	else if (spins < 0) {
1084	<	if (rhead != node)
1085	<	spins = 0;
1086	<	else if ((spins = headSpins) < MAX_HEAD_SPINS && node != null)
1087	<	headSpins <<= 1;
1088	<	}
1089	<	else if (spins > 0) {
1090	<	if ((r = nextRandom(r)) >= 0)
1091	<	--spins;
1092	<	}
1093	<	else if (node == null)
1094	<	node = new RNode(seq, Thread.currentThread());
1095	<	else if (!queued) {
1096	<	if (queued = U.compareAndSwapObject(this, RHEAD,
1097	<	node.next = rhead, node))
1098	<	spins = -1;
1161	>	if ((ps = p.status) == 0)
1162	>	U.compareAndSwapInt(p, WSTATUS, 0, WAITING);
1163	>	else if (ps == CANCELLED) {
1164	>	if ((pp = p.prev) != null) {
1165	>	node.prev = pp;
1166	>	pp.next = node;
1167	>	}
1168		}
1169		else {
1170		long time;
1171		if (deadline == 0L)
1172		time = 0L;
1173		else if ((time = deadline - System.nanoTime()) <= 0L)
1174	<	return cancelReader(node, false);
1175	<	if ((state & WBIT) != 0L && node.waiter != null) { // recheck
1174	>	return cancelWaiter(node, null, false);
1175	>	node.thread = Thread.currentThread();
1176	>	if (node.prev == p && p.status == WAITING &&
1177	>	(p != whead || (state & ABITS) != WBIT)) {
1178		U.park(false, time);
1179		if (interruptible && Thread.interrupted())
1180	<	return cancelReader(node, true);
1180	>	return cancelWaiter(node, null, true);
1181		}
1182	+	node.thread = null;
1183		}
1184		}
1185		}
1186
1187		/**
1188		* If node non-null, forces cancel status and unsplices from queue
1189	<	* if possible, by traversing entire queue looking for cancelled
1190	<	* nodes.
1189	>	* if possible. This is a variant of cancellation methods in
1190	>	* AbstractQueuedSynchronizer (see its detailed explanation in AQS
1191	>	* internal documentation) that more conservatively wakes up other
1192	>	* threads that may have had their links changed, so as to preserve
1193	>	* liveness in the main signalling methods.
1194		*/
1195	<	private long cancelReader(RNode node, boolean interrupted) {
1196	<	Thread w;
1197	<	if (node != null && (w = node.waiter) != null &&
1198	<	U.compareAndSwapObject(node, WAITER, w, null)) {
1199	<	for (RNode pred = null, p = rhead; p != null;) {
1200	<	RNode q = p.next;
1201	<	if (p.waiter == null) {
1202	<	if (pred == null) {
1203	<	U.compareAndSwapObject(this, RHEAD, p, q);
1129	<	p = rhead;
1130	<	}
1131	<	else {
1132	<	U.compareAndSwapObject(pred, RNEXT, p, q);
1133	<	p = pred.next;
1195	>	private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1196	>	if (node != null) {
1197	>	node.thread = null;
1198	>	node.status = CANCELLED;
1199	>	if (group != null) {
1200	>	for (WNode p = group, q; p != null; p = q) {
1201	>	if ((q = p.cowait) != null && q.status == CANCELLED) {
1202	>	U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1203	>	break;
1204		}
1205		}
1206	<	else {
1207	<	pred = p;
1208	<	p = q;
1206	>	}
1207	>	else {
1208	>	for (WNode pred = node.prev; pred != null; ) {
1209	>	WNode succ, pp; Thread w;
1210	>	while ((succ = node.next) == null ||
1211	>	succ.status == CANCELLED) {
1212	>	WNode q = null;
1213	>	for (WNode t = wtail; t != null && t != node; t = t.prev)
1214	>	if (t.status != CANCELLED)
1215	>	q = t;
1216	>	if (succ == q ||
1217	>	U.compareAndSwapObject(node, WNEXT,
1218	>	succ, succ = q)) {
1219	>	if (succ == null && node == wtail)
1220	>	U.compareAndSwapObject(this, WTAIL, node, pred);
1221	>	break;
1222	>	}
1223	>	}
1224	>	if (pred.next == node)
1225	>	U.compareAndSwapObject(pred, WNEXT, node, succ);
1226	>	if (succ != null && (w = succ.thread) != null)
1227	>	U.unpark(w);
1228	>	if (pred.status != CANCELLED || (pp = pred.prev) == null)
1229	>	break;
1230	>	node.prev = pp; // repeat for new pred
1231	>	U.compareAndSwapObject(pp, WNEXT, pred, succ);
1232	>	pred = pp;
1233		}
1234		}
1235		}
1236	<	readerPrefSignal();
1236	>	release(whead);
1237		return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1238		}
1239
1240		// Unsafe mechanics
1241		private static final sun.misc.Unsafe U;
1242		private static final long STATE;
1149	–	private static final long RHEAD;
1243		private static final long WHEAD;
1244		private static final long WTAIL;
1152	–	private static final long RNEXT;
1245		private static final long WNEXT;
1246	<	private static final long WPREV;
1247	<	private static final long WAITER;
1156	<	private static final long STATUS;
1246	>	private static final long WSTATUS;
1247	>	private static final long WCOWAIT;
1248
1249		static {
1250		try {
1251		U = getUnsafe();
1252		Class<?> k = StampedLock.class;
1162	–	Class<?> rk = RNode.class;
1253		Class<?> wk = WNode.class;
1254		STATE = U.objectFieldOffset
1255		(k.getDeclaredField("state"));
1166	–	RHEAD = U.objectFieldOffset
1167	–	(k.getDeclaredField("rhead"));
1256		WHEAD = U.objectFieldOffset
1257		(k.getDeclaredField("whead"));
1258		WTAIL = U.objectFieldOffset
1259		(k.getDeclaredField("wtail"));
1260	<	RNEXT = U.objectFieldOffset
1173	<	(rk.getDeclaredField("next"));
1174	<	WAITER = U.objectFieldOffset
1175	<	(rk.getDeclaredField("waiter"));
1176	<	STATUS = U.objectFieldOffset
1260	>	WSTATUS = U.objectFieldOffset
1261		(wk.getDeclaredField("status"));
1262		WNEXT = U.objectFieldOffset
1263		(wk.getDeclaredField("next"));
1264	<	WPREV = U.objectFieldOffset
1265	<	(wk.getDeclaredField("prev"));
1264	>	WCOWAIT = U.objectFieldOffset
1265	>	(wk.getDeclaredField("cowait"));
1266
1267		} catch (Exception e) {
1268		throw new Error(e);
#	Line 1195 | Line 1279 | public class StampedLock implements java
1279		private static sun.misc.Unsafe getUnsafe() {
1280		try {
1281		return sun.misc.Unsafe.getUnsafe();
1282	<	} catch (SecurityException se) {
1283	<	try {
1284	<	return java.security.AccessController.doPrivileged
1285	<	(new java.security
1286	<	.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1287	<	public sun.misc.Unsafe run() throws Exception {
1288	<	java.lang.reflect.Field f = sun.misc
1289	<	.Unsafe.class.getDeclaredField("theUnsafe");
1290	<	f.setAccessible(true);
1291	<	return (sun.misc.Unsafe) f.get(null);
1292	<	}});
1293	<	} catch (java.security.PrivilegedActionException e) {
1294	<	throw new RuntimeException("Could not initialize intrinsics",
1295	<	e.getCause());
1296	<	}
1282	>	} catch (SecurityException tryReflectionInstead) {}
1283	>	try {
1284	>	return java.security.AccessController.doPrivileged
1285	>	(new java.security.PrivilegedExceptionAction<sun.misc.Unsafe>() {
1286	>	public sun.misc.Unsafe run() throws Exception {
1287	>	Class<sun.misc.Unsafe> k = sun.misc.Unsafe.class;
1288	>	for (java.lang.reflect.Field f : k.getDeclaredFields()) {
1289	>	f.setAccessible(true);
1290	>	Object x = f.get(null);
1291	>	if (k.isInstance(x))
1292	>	return k.cast(x);
1293	>	}
1294	>	throw new NoSuchFieldError("the Unsafe");
1295	>	}});
1296	>	} catch (java.security.PrivilegedActionException e) {
1297	>	throw new RuntimeException("Could not initialize intrinsics",
1298	>	e.getCause());
1299		}
1300		}
1215	–
1301		}

Diff Legend

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