11 |
|
|
12 |
|
/** |
13 |
|
* A capability-based lock with three modes for controlling read/write |
14 |
< |
* access. The state of a StampedLock consists of a version and |
15 |
< |
* mode. Lock acquisition methods return a stamp that represents and |
14 |
> |
* access. The state of a StampedLock consists of a version and mode. |
15 |
> |
* Lock acquisition methods return a stamp that represents and |
16 |
|
* controls access with respect to a lock state; "try" versions of |
17 |
|
* these methods may instead return the special value zero to |
18 |
|
* represent failure to acquire access. Lock release and conversion |
26 |
|
* in method {@link #unlockWrite} to release the lock. Untimed and |
27 |
|
* timed versions of {@code tryWriteLock} are also provided. When |
28 |
|
* the lock is held in write mode, no read locks may be obtained, |
29 |
< |
* and all observer validations will fail. </li> |
29 |
> |
* and all optimistic read validations will fail. </li> |
30 |
|
* |
31 |
|
* <li><b>Reading.</b> Method {@link #readLock} possibly blocks |
32 |
|
* waiting for non-exclusive access, returning a stamp that can be |
55 |
|
* <p>This class also supports methods that conditionally provide |
56 |
|
* conversions across the three modes. For example, method {@link |
57 |
|
* #tryConvertToWriteLock} attempts to "upgrade" a mode, returning |
58 |
< |
* valid write stamp if (1) already in writing mode (2) in reading |
58 |
> |
* a valid write stamp if (1) already in writing mode (2) in reading |
59 |
|
* mode and there are no other readers or (3) in optimistic mode and |
60 |
|
* the lock is available. The forms of these methods are designed to |
61 |
|
* help reduce some of the code bloat that otherwise occurs in |
76 |
|
* into initial unlocked state, so they are not useful for remote |
77 |
|
* locking. |
78 |
|
* |
79 |
< |
* <p>The scheduling policy of StampedLock does not consistently prefer |
80 |
< |
* readers over writers or vice versa. |
79 |
> |
* <p>The scheduling policy of StampedLock does not consistently |
80 |
> |
* prefer readers over writers or vice versa. A zero return from any |
81 |
> |
* "try" method for acquiring or converting locks does not carry any |
82 |
> |
* information about the state of the lock; a subsequent invocation |
83 |
> |
* may succeed. |
84 |
|
* |
85 |
|
* <p><b>Sample Usage.</b> The following illustrates some usage idioms |
86 |
|
* in a class that maintains simple two-dimensional points. The sample |
90 |
|
* |
91 |
|
* <pre>{@code |
92 |
|
* class Point { |
93 |
< |
* private volatile double x, y; |
93 |
> |
* private double x, y; |
94 |
|
* private final StampedLock sl = new StampedLock(); |
95 |
|
* |
96 |
|
* void move(double deltaX, double deltaY) { // an exclusively locked method |
122 |
|
* } |
123 |
|
* |
124 |
|
* double distanceFromOriginV2() { // combines code paths |
125 |
< |
* for (long stamp = sl.optimisticRead(); ; stamp = sl.readLock()) { |
125 |
> |
* for (long stamp = sl.tryOptimisticRead(); ; stamp = sl.readLock()) { |
126 |
|
* double currentX, currentY; |
127 |
|
* try { |
128 |
|
* currentX = x; |
180 |
|
* read-locked. The read count is ignored when validating |
181 |
|
* "optimistic" seqlock-reader-style stamps. Because we must use |
182 |
|
* a small finite number of bits (currently 7) for readers, a |
183 |
< |
* supplementatry reader overflow word is used when then number of |
183 |
> |
* supplementary reader overflow word is used when the number of |
184 |
|
* readers exceeds the count field. We do this by treating the max |
185 |
|
* reader count value (RBITS) as a spinlock protecting overflow |
186 |
|
* updates. |
216 |
|
* in-progress spins/signals, and others do not account for |
217 |
|
* cancellations. |
218 |
|
* |
219 |
+ |
* Controlled, randomized spinning is used in the two await |
220 |
+ |
* methods to reduce (increasingly expensive) context switching |
221 |
+ |
* while also avoiding sustained memory thrashing among many |
222 |
+ |
* threads. Both await methods use a similar spin strategy: If |
223 |
+ |
* the associated queue appears to be empty, then the thread |
224 |
+ |
* 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. |
232 |
+ |
* |
233 |
|
* As noted in Boehm's paper (above), sequence validation (mainly |
234 |
|
* method validate()) requires stricter ordering rules than apply |
235 |
|
* to normal volatile reads (of "state"). In the absence of (but |
252 |
|
private static final int NCPU = Runtime.getRuntime().availableProcessors(); |
253 |
|
|
254 |
|
/** Maximum number of retries before blocking on acquisition */ |
255 |
< |
private static final int SPINS = NCPU > 1 ? 1 << 6 : 1; |
255 |
> |
private static final int SPINS = (NCPU > 1) ? 1 << 6 : 1; |
256 |
|
|
257 |
< |
/** Maximum number of retries before re-blocking on write lock */ |
258 |
< |
private static final int MAX_HEAD_SPINS = NCPU > 1 ? 1 << 12 : 1; |
257 |
> |
/** Maximum number of retries before re-blocking */ |
258 |
> |
private static final int MAX_HEAD_SPINS = (NCPU > 1) ? 1 << 12 : 1; |
259 |
|
|
260 |
|
/** The period for yielding when waiting for overflow spinlock */ |
261 |
|
private static final int OVERFLOW_YIELD_RATE = 7; // must be power 2 - 1 |
262 |
|
|
263 |
|
/** The number of bits to use for reader count before overflowing */ |
264 |
< |
private static final int LG_READERS = 7; |
264 |
> |
private static final int LG_READERS = 7; |
265 |
|
|
266 |
|
// Values for lock state and stamp operations |
267 |
|
private static final long RUNIT = 1L; |
310 |
|
private transient int readerOverflow; |
311 |
|
|
312 |
|
/** |
313 |
< |
* Creates a new lock initially in unlocked state. |
313 |
> |
* Creates a new lock, initially in unlocked state. |
314 |
|
*/ |
315 |
|
public StampedLock() { |
316 |
|
state = ORIGIN; |
320 |
|
* Exclusively acquires the lock, blocking if necessary |
321 |
|
* until available. |
322 |
|
* |
323 |
< |
* @return a stamp that can be used to unlock or convert mode. |
323 |
> |
* @return a stamp that can be used to unlock or convert mode |
324 |
|
*/ |
325 |
|
public long writeLock() { |
326 |
|
long s, next; |
334 |
|
* Exclusively acquires the lock if it is immediately available. |
335 |
|
* |
336 |
|
* @return a stamp that can be used to unlock or convert mode, |
337 |
< |
* or zero if the lock is not available. |
337 |
> |
* or zero if the lock is not available |
338 |
|
*/ |
339 |
|
public long tryWriteLock() { |
340 |
|
long s, next; |
346 |
|
|
347 |
|
/** |
348 |
|
* Exclusively acquires the lock if it is available within the |
349 |
< |
* given time and the current thread has not been interrupted |
349 |
> |
* given time and the current thread has not been interrupted. |
350 |
|
* |
351 |
|
* @return a stamp that can be used to unlock or convert mode, |
352 |
< |
* or zero if the lock is not available. |
352 |
> |
* or zero if the lock is not available |
353 |
|
* @throws InterruptedException if the current thread is interrupted |
354 |
< |
* before acquiring the lock. |
354 |
> |
* before acquiring the lock |
355 |
|
*/ |
356 |
|
public long tryWriteLock(long time, TimeUnit unit) |
357 |
|
throws InterruptedException { |
358 |
< |
long nanos = unit.toNanos(time); |
358 |
> |
long nanos = unit.toNanos(time); |
359 |
|
if (!Thread.interrupted()) { |
360 |
|
long s, next, deadline; |
361 |
|
if (((s = state) & ABITS) == 0L && |
375 |
|
* Exclusively acquires the lock, blocking if necessary |
376 |
|
* until available or the current thread is interrupted. |
377 |
|
* |
378 |
< |
* @return a stamp that can be used to unlock or convert mode. |
378 |
> |
* @return a stamp that can be used to unlock or convert mode |
379 |
|
* @throws InterruptedException if the current thread is interrupted |
380 |
< |
* before acquiring the lock. |
380 |
> |
* before acquiring the lock |
381 |
|
*/ |
382 |
|
public long writeLockInterruptibly() throws InterruptedException { |
383 |
|
if (!Thread.interrupted()) { |
395 |
|
* Non-exclusively acquires the lock, blocking if necessary |
396 |
|
* until available. |
397 |
|
* |
398 |
< |
* @return a stamp that can be used to unlock or convert mode. |
398 |
> |
* @return a stamp that can be used to unlock or convert mode |
399 |
|
*/ |
400 |
|
public long readLock() { |
401 |
|
for (;;) { |
418 |
|
* Non-exclusively acquires the lock if it is immediately available. |
419 |
|
* |
420 |
|
* @return a stamp that can be used to unlock or convert mode, |
421 |
< |
* or zero if the lock is not available. |
421 |
> |
* or zero if the lock is not available |
422 |
|
*/ |
423 |
|
public long tryReadLock() { |
424 |
|
for (;;) { |
436 |
|
|
437 |
|
/** |
438 |
|
* Non-exclusively acquires the lock if it is available within the |
439 |
< |
* given time and the current thread has not been interrupted |
439 |
> |
* given time and the current thread has not been interrupted. |
440 |
|
* |
441 |
|
* @return a stamp that can be used to unlock or convert mode, |
442 |
< |
* or zero if the lock is not available. |
442 |
> |
* or zero if the lock is not available |
443 |
|
* @throws InterruptedException if the current thread is interrupted |
444 |
< |
* before acquiring the lock. |
444 |
> |
* before acquiring the lock |
445 |
|
*/ |
446 |
|
public long tryReadLock(long time, TimeUnit unit) |
447 |
|
throws InterruptedException { |
474 |
|
* Non-exclusively acquires the lock, blocking if necessary |
475 |
|
* until available or the current thread is interrupted. |
476 |
|
* |
477 |
< |
* @return a stamp that can be used to unlock or convert mode. |
477 |
> |
* @return a stamp that can be used to unlock or convert mode |
478 |
|
* @throws InterruptedException if the current thread is interrupted |
479 |
< |
* before acquiring the lock. |
479 |
> |
* before acquiring the lock |
480 |
|
*/ |
481 |
|
public long readLockInterruptibly() throws InterruptedException { |
482 |
|
if (!Thread.interrupted()) { |
529 |
|
* |
530 |
|
* @param stamp a stamp returned by a write-lock operation |
531 |
|
* @throws IllegalMonitorStateException if the stamp does |
532 |
< |
* not match the current state of this lock. |
532 |
> |
* not match the current state of this lock |
533 |
|
*/ |
534 |
|
public void unlockWrite(long stamp) { |
535 |
|
if (state != stamp || (stamp & WBIT) == 0L) |
539 |
|
} |
540 |
|
|
541 |
|
/** |
542 |
< |
* If the lock state matches the given stamp, releases |
542 |
> |
* If the lock state matches the given stamp, releases the |
543 |
|
* non-exclusive lock. |
544 |
|
* |
545 |
|
* @param stamp a stamp returned by a read-lock operation |
546 |
|
* @throws IllegalMonitorStateException if the stamp does |
547 |
< |
* not match the current state of this lock. |
547 |
> |
* not match the current state of this lock |
548 |
|
*/ |
549 |
|
public void unlockRead(long stamp) { |
550 |
|
long s, m; |
574 |
|
* |
575 |
|
* @param stamp a stamp returned by a lock operation |
576 |
|
* @throws IllegalMonitorStateException if the stamp does |
577 |
< |
* not match the current state of this lock. |
577 |
> |
* not match the current state of this lock |
578 |
|
*/ |
579 |
|
public void unlock(long stamp) { |
580 |
|
long a = stamp & ABITS, m, s; |
606 |
|
/** |
607 |
|
* If the lock state matches the given stamp then performs one of |
608 |
|
* the following actions. If the stamp represents holding a write |
609 |
< |
* lock, returns it. Or, if a read lock, if the write lock is |
610 |
< |
* available, releases the read and returns a write stamp. Or, if |
611 |
< |
* an optimistic read, returns a write stamp only if immediately |
612 |
< |
* available. This method returns zero in all other cases. |
609 |
> |
* lock, returns it. Or, if a read lock, if the write lock is |
610 |
> |
* available, releases the read lock and returns a write stamp. |
611 |
> |
* Or, if an optimistic read, returns a write stamp only if |
612 |
> |
* immediately available. This method returns zero in all other |
613 |
> |
* cases. |
614 |
|
* |
615 |
|
* @param stamp a stamp |
616 |
|
* @return a valid write stamp, or zero on failure |
667 |
|
else if (m == WBIT) { |
668 |
|
if (a != m) |
669 |
|
break; |
670 |
< |
next = state = s + (WBIT + RUNIT); |
670 |
> |
state = next = s + (WBIT + RUNIT); |
671 |
|
readerPrefSignal(); |
672 |
|
return next; |
673 |
|
} |
691 |
|
*/ |
692 |
|
public long tryConvertToOptimisticRead(long stamp) { |
693 |
|
long a = stamp & ABITS, m, s, next; |
694 |
< |
while (((s = U.getLongVolatile(this, STATE)) & |
694 |
> |
while (((s = U.getLongVolatile(this, STATE)) & |
695 |
|
SBITS) == (stamp & SBITS)) { |
696 |
|
if ((m = s & ABITS) == 0L) { |
697 |
|
if (a != 0L) |
701 |
|
else if (m == WBIT) { |
702 |
|
if (a != m) |
703 |
|
break; |
704 |
< |
next = state = (s += WBIT) == 0L ? ORIGIN : s; |
704 |
> |
state = next = (s += WBIT) == 0L ? ORIGIN : s; |
705 |
|
readerPrefSignal(); |
706 |
|
return next; |
707 |
|
} |
725 |
|
* stamp value. This method may be useful for recovery after |
726 |
|
* errors. |
727 |
|
* |
728 |
< |
* @return true if the lock was held, else false. |
728 |
> |
* @return true if the lock was held, else false |
729 |
|
*/ |
730 |
|
public boolean tryUnlockWrite() { |
731 |
|
long s; |
742 |
|
* requiring a stamp value. This method may be useful for recovery |
743 |
|
* after errors. |
744 |
|
* |
745 |
< |
* @return true if the read lock was held, else false. |
745 |
> |
* @return true if the read lock was held, else false |
746 |
|
*/ |
747 |
|
public boolean tryUnlockRead() { |
748 |
|
long s, m; |
791 |
|
* Tries to increment readerOverflow by first setting state |
792 |
|
* access bits value to RBITS, indicating hold of spinlock, |
793 |
|
* then updating, then releasing. |
794 |
+ |
* |
795 |
|
* @param stamp, assumed that (stamp & ABITS) >= RFULL |
796 |
|
* @return new stamp on success, else zero |
797 |
|
*/ |
803 |
|
return s; |
804 |
|
} |
805 |
|
} |
806 |
< |
else if ((ThreadLocalRandom.current().nextInt() & |
806 |
> |
else if ((ThreadLocalRandom.current().nextInt() & |
807 |
|
OVERFLOW_YIELD_RATE) == 0) |
808 |
|
Thread.yield(); |
809 |
|
return 0L; |
811 |
|
|
812 |
|
/** |
813 |
|
* Tries to decrement readerOverflow. |
814 |
+ |
* |
815 |
|
* @param stamp, assumed that (stamp & ABITS) >= RFULL |
816 |
|
* @return new stamp on success, else zero |
817 |
|
*/ |
829 |
|
return next; |
830 |
|
} |
831 |
|
} |
832 |
< |
else if ((ThreadLocalRandom.current().nextInt() & |
832 |
> |
else if ((ThreadLocalRandom.current().nextInt() & |
833 |
|
OVERFLOW_YIELD_RATE) == 0) |
834 |
|
Thread.yield(); |
835 |
|
return 0L; |
909 |
|
/** |
910 |
|
* 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. Both await |
893 |
< |
* methods use a similar spin strategy: If associated queue |
894 |
< |
* appears to be empty, then the thread spin-waits up to SPINS |
895 |
< |
* times before enqueing, and then, if the first thread to be |
896 |
< |
* enqueued, spins again up to SPINS times before blocking. If, |
897 |
< |
* upon wakening it fails to obtain lock, and is still (or |
898 |
< |
* becomes) the first waiting thread (which indicates that some |
899 |
< |
* other thread barged and obtained lock), it escalates spins (up |
900 |
< |
* to MAX_HEAD_SPINS) to reduce the likelihood of continually |
901 |
< |
* losing to barging threads. |
912 |
> |
* use an xorShift to further reduce memory traffic. |
913 |
|
*/ |
914 |
|
private static int nextRandom(int r) { |
915 |
|
if (r == 0) |
922 |
|
|
923 |
|
/** |
924 |
|
* Possibly spins trying to obtain write lock, then enqueues and |
925 |
< |
* blocks while not head of write queue or cannot aquire lock, |
925 |
> |
* blocks while not head of write queue or cannot acquire lock, |
926 |
|
* possibly spinning when at head; cancelling on timeout or |
927 |
|
* interrupt. |
928 |
|
* |
929 |
|
* @param interruptible true if should check interrupts and if so |
930 |
|
* return INTERRUPTED |
931 |
|
* @param deadline if nonzero, the System.nanoTime value to timeout |
932 |
< |
* at (and return zero). |
932 |
> |
* at (and return zero) |
933 |
|
*/ |
934 |
|
private long awaitWrite(boolean interruptible, long deadline) { |
935 |
|
WNode node = null; |
958 |
|
p.next = node; |
959 |
|
for (int headSpins = SPINS;;) { |
960 |
|
WNode np; int ps; |
961 |
< |
if ((np = node.prev) != p && np != null) |
962 |
< |
(p = np).next = node; // stale |
961 |
> |
if ((np = node.prev) != p && np != null && |
962 |
> |
(p = np).next != node) |
963 |
> |
p.next = node; // stale |
964 |
|
if (p == whead) { |
965 |
|
for (int k = headSpins;;) { |
966 |
|
if (((s = state) & ABITS) == 0L) { |
1017 |
|
WNode predNext = pred.next; |
1018 |
|
node.status = CANCELLED; |
1019 |
|
if (predNext != null) { |
1020 |
< |
Thread w = null; |
1020 |
> |
Thread w; |
1021 |
|
WNode succ = node.next; |
1022 |
< |
while (succ != null && succ.status == CANCELLED) |
1023 |
< |
succ = succ.next; |
1024 |
< |
if (succ != null) |
1025 |
< |
w = succ.thread; |
1026 |
< |
else if (node == wtail) |
1027 |
< |
U.compareAndSwapObject(this, WTAIL, node, pred); |
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 (w != null) |
1031 |
> |
if (succ != null && (w = succ.thread) != null) |
1032 |
|
U.unpark(w); |
1033 |
|
} |
1034 |
|
} |
1035 |
|
writerPrefSignal(); |
1036 |
< |
return (interrupted || Thread.interrupted())? INTERRUPTED : 0L; |
1036 |
> |
return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L; |
1037 |
|
} |
1038 |
|
|
1039 |
< |
/* |
1039 |
> |
/** |
1040 |
|
* Waits for read lock or timeout or interrupt. The form of |
1041 |
|
* awaitRead differs from awaitWrite mainly because it must |
1042 |
|
* restart (with a new wait node) if the thread was unqueued and |
1115 |
|
/** |
1116 |
|
* If node non-null, forces cancel status and unsplices from queue |
1117 |
|
* if possible, by traversing entire queue looking for cancelled |
1118 |
< |
* nodes, cleaning out all at head, but stopping upon first |
1105 |
< |
* encounter otherwise. |
1118 |
> |
* nodes. |
1119 |
|
*/ |
1120 |
|
private long cancelReader(RNode node, boolean interrupted) { |
1121 |
|
Thread w; |
1130 |
|
} |
1131 |
|
else { |
1132 |
|
U.compareAndSwapObject(pred, RNEXT, p, q); |
1133 |
< |
break; |
1133 |
> |
p = pred.next; |
1134 |
|
} |
1135 |
|
} |
1136 |
|
else { |
1140 |
|
} |
1141 |
|
} |
1142 |
|
readerPrefSignal(); |
1143 |
< |
return (interrupted || Thread.interrupted())? INTERRUPTED : 0L; |
1143 |
> |
return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L; |
1144 |
|
} |
1145 |
|
|
1146 |
|
// Unsafe mechanics |
1214 |
|
} |
1215 |
|
|
1216 |
|
} |
1204 |
– |
|