8 |
|
|
9 |
|
import java.util.concurrent.ThreadLocalRandom; |
10 |
|
import java.util.concurrent.TimeUnit; |
11 |
< |
import java.util.concurrent.locks.*; |
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 |
201 |
|
* |
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 it tagged (field mode) as |
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 its |
208 |
< |
* structure, wait nodes need not actually carry sequence numbers; |
209 |
< |
* we know each is >= its predecessor. These queue mechanics |
210 |
< |
* simplify the scheduling policy to a mainly-FIFO scheme that |
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 |
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 consitent sets |
236 |
< |
* of locally cahced reads. |
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 |
252 |
|
* motivation to further spread out contended locations, but might |
253 |
|
* be subject to future improvements. |
254 |
|
*/ |
252 |
– |
|
255 |
|
private static final long serialVersionUID = -6001602636862214147L; |
256 |
|
|
257 |
|
/** Number of processors, for spin control */ |
331 |
|
* @return a stamp that can be used to unlock or convert mode |
332 |
|
*/ |
333 |
|
public long writeLock() { |
334 |
< |
long s, next; // bypass acquireWrite in fully onlocked case only |
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)); |
366 |
|
long nanos = unit.toNanos(time); |
367 |
|
if (!Thread.interrupted()) { |
368 |
|
long next, deadline; |
369 |
< |
if ((next = tryWriteLock()) != 0) |
369 |
> |
if ((next = tryWriteLock()) != 0L) |
370 |
|
return next; |
371 |
|
if (nanos <= 0L) |
372 |
|
return 0L; |
403 |
|
* @return a stamp that can be used to unlock or convert mode |
404 |
|
*/ |
405 |
|
public long readLock() { |
406 |
< |
long s, next; // bypass acquireRead on fully onlocked case only |
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)); |
445 |
|
long next, deadline; |
446 |
|
long nanos = unit.toNanos(time); |
447 |
|
if (!Thread.interrupted()) { |
448 |
< |
if ((next = tryReadLock()) != 0) |
448 |
> |
if ((next = tryReadLock()) != 0L) |
449 |
|
return next; |
450 |
|
if (nanos <= 0L) |
451 |
|
return 0L; |
526 |
|
* not match the current state of this lock |
527 |
|
*/ |
528 |
|
public void unlockRead(long stamp) { |
529 |
< |
long s, m; WNode h; |
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; |
532 |
– |
else if (m < RFULL) { |
533 |
– |
if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) { |
534 |
– |
if (m == RUNIT && (h = whead) != null && h.status != 0) |
535 |
– |
release(h); |
536 |
– |
return; |
537 |
– |
} |
539 |
|
} |
539 |
– |
else if (m >= WBIT) |
540 |
– |
break; |
541 |
– |
else if (tryDecReaderOverflow(s) != 0L) |
542 |
– |
return; |
540 |
|
} |
541 |
+ |
else if (tryDecReaderOverflow(s) != 0L) |
542 |
+ |
break; |
543 |
|
} |
545 |
– |
throw new IllegalMonitorStateException(); |
544 |
|
} |
545 |
|
|
546 |
|
/** |
823 |
|
throws InterruptedException { |
824 |
|
return tryReadLock(time, unit) != 0L; |
825 |
|
} |
826 |
< |
// note that we give up ability to check mode so just use current state |
829 |
< |
public void unlock() { unlockRead(state); } |
826 |
> |
public void unlock() { unstampedUnlockRead(); } |
827 |
|
public Condition newCondition() { |
828 |
|
throw new UnsupportedOperationException(); |
829 |
|
} |
839 |
|
throws InterruptedException { |
840 |
|
return tryWriteLock(time, unit) != 0L; |
841 |
|
} |
842 |
< |
public void unlock() { unlockWrite(state); } |
842 |
> |
public void unlock() { unstampedUnlockWrite(); } |
843 |
|
public Condition newCondition() { |
844 |
|
throw new UnsupportedOperationException(); |
845 |
|
} |
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 |
|
/** |
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 |
< |
U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) { |
1008 |
< |
whead = node; |
1009 |
< |
node.prev = null; |
1010 |
< |
return ns; |
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) |
1060 |
|
if (group == null && (h = whead) != null && |
1061 |
|
(q = h.next) != null && q.mode != RMODE) |
1062 |
|
break; |
1063 |
< |
if ((m = (s = state) & ABITS) == WBIT) |
1037 |
< |
break; |
1038 |
< |
if (m < RFULL ? |
1063 |
> |
if ((m = (s = state) & ABITS) < RFULL ? |
1064 |
|
U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) : |
1065 |
< |
(ns = tryIncReaderOverflow(s)) != 0L) { |
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) { |
1076 |
|
} |
1077 |
|
return ns; |
1078 |
|
} |
1079 |
+ |
if (m >= WBIT) |
1080 |
+ |
break; |
1081 |
|
} |
1082 |
|
if (spins > 0) { |
1083 |
|
if (ThreadLocalRandom.current().nextInt() >= 0) |