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

Diff Legend

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