ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/jsr166e/StampedLock.java
(Generate patch)

Comparing jsr166/src/jsr166e/StampedLock.java (file contents):
Revision 1.28 by dl, Tue Jan 22 15:42:28 2013 UTC vs.
Revision 1.34 by jsr166, Mon Jan 28 17:23:04 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.*;
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 37 | Line 40 | import java.util.concurrent.locks.*;
40   *  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
41   *   returns a non-zero stamp only if the lock is not currently held
42   *   in write mode. Method {@link #validate} returns true if the lock
43 < *   has not since been acquired in write mode. This mode can be
44 < *   thought of as an extremely weak version of a read-lock, that can
45 < *   be broken by a writer at any time.  The use of optimistic mode
46 < *   for short read-only code segments often reduces contention and
47 < *   improves throughput.  However, its use is inherently fragile.
48 < *   Optimistic read sections should only read fields and hold them in
49 < *   local variables for later use after validation. Fields read while
50 < *   in optimistic mode may be wildly inconsistent, so usage applies
51 < *   only when you are familiar enough with data representations to
52 < *   check consistency and/or repeatedly invoke method {@code
53 < *   validate()}.  For example, such steps are typically required when
54 < *   first reading an object or array reference, and then accessing
55 < *   one of its fields, elements or methods. </li>
43 > *   has not been acquired in write mode since obtaining a given
44 > *   stamp.  This mode can be thought of as an extremely weak version
45 > *   of a read-lock, that can be broken by a writer at any time.  The
46 > *   use of optimistic mode for short read-only code segments often
47 > *   reduces contention and improves throughput.  However, its use is
48 > *   inherently fragile.  Optimistic read sections should only read
49 > *   fields and hold them in local variables for later use after
50 > *   validation. Fields read while in optimistic mode may be wildly
51 > *   inconsistent, so usage applies only when you are familiar enough
52 > *   with data representations to check consistency and/or repeatedly
53 > *   invoke method {@code validate()}.  For example, such steps are
54 > *   typically required when first reading an object or array
55 > *   reference, and then accessing one of its fields, elements or
56 > *   methods. </li>
57   *
58   * </ul>
59   *
# Line 198 | Line 202 | public class StampedLock implements java
202       *
203       * Waiters use a modified form of CLH lock used in
204       * AbstractQueuedSynchronizer (see its internal documentation for
205 <     * a fuller account), where each node it tagged (field mode) as
205 >     * a fuller account), where each node is tagged (field mode) as
206       * either a reader or writer. Sets of waiting readers are grouped
207       * (linked) under a common node (field cowait) so act as a single
208 <     * node with respect to most CLH mechanics.  By virtue of its
209 <     * structure, wait nodes need not actually carry sequence numbers;
210 <     * we know each is >= its predecessor.  These queue mechanics
211 <     * simplify the scheduling policy to a mainly-FIFO scheme that
208 >     * node with respect to most CLH mechanics.  By virtue of the
209 >     * queue structure, wait nodes need not actually carry sequence
210 >     * numbers; we know each is greater than its predecessor.  This
211 >     * simplifies the scheduling policy to a mainly-FIFO scheme that
212       * incorporates elements of Phase-Fair locks (see Brandenburg &
213       * Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
214       * particular, we use the phase-fair anti-barging rule: If an
# Line 229 | Line 233 | public class StampedLock implements java
233       *
234       * Nearly all of these mechanics are carried out in methods
235       * acquireWrite and acquireRead, that, as typical of such code,
236 <     * sprawl out because actions and retries rely on consitent sets
237 <     * of locally cahced reads.
236 >     * sprawl out because actions and retries rely on consistent sets
237 >     * of locally cached reads.
238       *
239       * As noted in Boehm's paper (above), sequence validation (mainly
240       * method validate()) requires stricter ordering rules than apply
# Line 329 | Line 333 | public class StampedLock implements java
333       * @return a stamp that can be used to unlock or convert mode
334       */
335      public long writeLock() {
336 <        long s, next;  // bypass acquireWrite in fully onlocked case only
336 >        long s, next;  // bypass acquireWrite in fully unlocked case only
337          return ((((s = state) & ABITS) == 0L &&
338                   U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
339                  next : acquireWrite(false, 0L));
# Line 364 | Line 368 | public class StampedLock implements java
368          long nanos = unit.toNanos(time);
369          if (!Thread.interrupted()) {
370              long next, deadline;
371 <            if ((next = tryWriteLock()) != 0)
371 >            if ((next = tryWriteLock()) != 0L)
372                  return next;
373              if (nanos <= 0L)
374                  return 0L;
# Line 401 | Line 405 | public class StampedLock implements java
405       * @return a stamp that can be used to unlock or convert mode
406       */
407      public long readLock() {
408 <        long s, next;  // bypass acquireRead on fully onlocked case only
408 >        long s, next;  // bypass acquireRead on fully unlocked case only
409          return ((((s = state) & ABITS) == 0L &&
410                   U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
411                  next : acquireRead(false, 0L));
# Line 440 | Line 444 | public class StampedLock implements java
444       */
445      public long tryReadLock(long time, TimeUnit unit)
446          throws InterruptedException {
447 <        long next, deadline;
447 >        long s, m, next, deadline;
448          long nanos = unit.toNanos(time);
449          if (!Thread.interrupted()) {
450 <            if ((next = tryReadLock()) != 0)
451 <                return next;
450 >            if ((m = (s = state) & ABITS) != WBIT) {
451 >                if (m < RFULL) {
452 >                    if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
453 >                        return next;
454 >                }
455 >                else if ((next = tryIncReaderOverflow(s)) != 0L)
456 >                    return next;
457 >            }
458              if (nanos <= 0L)
459                  return 0L;
460              if ((deadline = System.nanoTime() + nanos) == 0L)
# Line 488 | Line 498 | public class StampedLock implements java
498       * Returns true if the lock has not been exclusively acquired
499       * since issuance of the given stamp. Always returns false if the
500       * stamp is zero. Always returns true if the stamp represents a
501 <     * currently held lock.
501 >     * currently held lock. Invoking this method with a value not
502 >     * obtained from {@link #tryOptimisticRead} or a locking method
503 >     * for this lock has no defined effect or result.
504       *
505       * @return true if the lock has not been exclusively acquired
506       * since issuance of the given stamp; else false
# Line 524 | Line 536 | public class StampedLock implements java
536       * not match the current state of this lock
537       */
538      public void unlockRead(long stamp) {
539 <        long s, m;  WNode h;
540 <        if ((stamp & RBITS) != 0L) {
541 <            while (((s = state) & SBITS) == (stamp & SBITS)) {
542 <                if ((m = s & ABITS) == 0L)
539 >        long s, m; WNode h;
540 >        for (;;) {
541 >            if (((s = state) & SBITS) != (stamp & SBITS) ||
542 >                (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
543 >                throw new IllegalMonitorStateException();
544 >            if (m < RFULL) {
545 >                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
546 >                    if (m == RUNIT && (h = whead) != null && h.status != 0)
547 >                        release(h);
548                      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                    }
549                  }
539                else if (m >= WBIT)
540                    break;
541                else if (tryDecReaderOverflow(s) != 0L)
542                    return;
550              }
551 +            else if (tryDecReaderOverflow(s) != 0L)
552 +                break;
553          }
545        throw new IllegalMonitorStateException();
554      }
555  
556      /**
# Line 825 | Line 833 | public class StampedLock implements java
833              throws InterruptedException {
834              return tryReadLock(time, unit) != 0L;
835          }
836 <        // note that we give up ability to check mode so just use current state
829 <        public void unlock() { unlockRead(state); }
836 >        public void unlock() { unstampedUnlockRead(); }
837          public Condition newCondition() {
838              throw new UnsupportedOperationException();
839          }
# Line 842 | Line 849 | public class StampedLock implements java
849              throws InterruptedException {
850              return tryWriteLock(time, unit) != 0L;
851          }
852 <        public void unlock() { unlockWrite(state); }
852 >        public void unlock() { unstampedUnlockWrite(); }
853          public Condition newCondition() {
854              throw new UnsupportedOperationException();
855          }
# Line 853 | Line 860 | public class StampedLock implements java
860          public Lock writeLock() { return asWriteLock(); }
861      }
862  
863 +    // Unlock methods without stamp argument checks for view classes.
864 +    // Needed because view-class lock methods throw away stamps.
865 +
866 +    final void unstampedUnlockWrite() {
867 +        WNode h; long s;
868 +        if (((s = state) & WBIT) == 0L)
869 +            throw new IllegalMonitorStateException();
870 +        state = (s += WBIT) == 0L ? ORIGIN : s;
871 +        if ((h = whead) != null && h.status != 0)
872 +            release(h);
873 +    }
874 +
875 +    final void unstampedUnlockRead() {
876 +        for (;;) {
877 +            long s, m; WNode h;
878 +            if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
879 +                throw new IllegalMonitorStateException();
880 +            else if (m < RFULL) {
881 +                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
882 +                    if (m == RUNIT && (h = whead) != null && h.status != 0)
883 +                        release(h);
884 +                    break;
885 +                }
886 +            }
887 +            else if (tryDecReaderOverflow(s) != 0L)
888 +                break;
889 +        }
890 +    }
891 +
892      // internals
893  
894      /**
# Line 903 | Line 939 | public class StampedLock implements java
939          return 0L;
940      }
941  
942 <    /*
942 >    /**
943       * Wakes up the successor of h (normally whead). This is normally
944       * just h.next, but may require traversal from wtail if next
945       * pointers are lagging. This may fail to wake up an acquiring
# Line 977 | Line 1013 | public class StampedLock implements java
1013                  (p = np).next = node;   // stale
1014              if (whead == p) {
1015                  for (int k = spins;;) { // spin at head
1016 <                    if (((s = state) & ABITS) == 0L &&
1017 <                        U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) {
1018 <                        whead = node;
1019 <                        node.prev = null;
1020 <                        return ns;
1016 >                    if (((s = state) & ABITS) == 0L) {
1017 >                        if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1018 >                            whead = node;
1019 >                            node.prev = null;
1020 >                            return ns;
1021 >                        }
1022                      }
1023                      else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1024                               --k <= 0)
# Line 1003 | Line 1040 | public class StampedLock implements java
1040                  if (deadline == 0L)
1041                      time = 0L;
1042                  else if ((time = deadline - System.nanoTime()) <= 0L)
1043 <                    return cancelWaiter(node, null, false);
1043 >                    return cancelWaiter(node, node, false);
1044                  node.thread = Thread.currentThread();
1045                  if (node.prev == p && p.status == WAITING && // recheck
1046 <                    (p != whead || (state & ABITS) != 0L)) {
1046 >                    (p != whead || (state & ABITS) != 0L))
1047                      U.park(false, time);
1011                    if (interruptible && Thread.interrupted())
1012                        return cancelWaiter(node, null, true);
1013                }
1048                  node.thread = null;
1049 +                if (interruptible && Thread.interrupted())
1050 +                    return cancelWaiter(node, node, true);
1051              }
1052          }
1053      }
# Line 1033 | Line 1069 | public class StampedLock implements java
1069                  if (group == null && (h = whead) != null &&
1070                      (q = h.next) != null && q.mode != RMODE)
1071                      break;
1072 <                if ((m = (s = state) & ABITS) == WBIT)
1037 <                    break;
1038 <                if (m < RFULL ?
1072 >                if ((m = (s = state) & ABITS) < RFULL ?
1073                      U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1074 <                    (ns = tryIncReaderOverflow(s)) != 0L) {
1074 >                    (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1075                      if (group != null) {  // help release others
1076                          for (WNode r = group;;) {
1077                              if ((w = r.thread) != null) {
# Line 1051 | Line 1085 | public class StampedLock implements java
1085                      }
1086                      return ns;
1087                  }
1088 +                if (m >= WBIT)
1089 +                    break;
1090              }
1091              if (spins > 0) {
1092                  if (ThreadLocalRandom.current().nextInt() >= 0)
# Line 1074 | Line 1110 | public class StampedLock implements java
1110                                             node.cowait = p.cowait, node)) {
1111                      node.thread = Thread.currentThread();
1112                      for (long time;;) {
1113 +                        if (interruptible && Thread.interrupted())
1114 +                            return cancelWaiter(node, p, true);
1115                          if (deadline == 0L)
1116                              time = 0L;
1117                          else if ((time = deadline - System.nanoTime()) <= 0L)
# Line 1088 | Line 1126 | public class StampedLock implements java
1126                          if (node.thread == null) // must recheck
1127                              break;
1128                          U.park(false, time);
1091                        if (interruptible && Thread.interrupted())
1092                            return cancelWaiter(node, p, true);
1129                      }
1130                      group = p;
1131                  }
# Line 1144 | Line 1180 | public class StampedLock implements java
1180                  if (deadline == 0L)
1181                      time = 0L;
1182                  else if ((time = deadline - System.nanoTime()) <= 0L)
1183 <                    return cancelWaiter(node, null, false);
1183 >                    return cancelWaiter(node, node, false);
1184                  node.thread = Thread.currentThread();
1185                  if (node.prev == p && p.status == WAITING &&
1186 <                    (p != whead || (state & ABITS) != WBIT)) {
1186 >                    (p != whead || (state & ABITS) != WBIT))
1187                      U.park(false, time);
1152                    if (interruptible && Thread.interrupted())
1153                        return cancelWaiter(node, null, true);
1154                }
1188                  node.thread = null;
1189 +                if (interruptible && Thread.interrupted())
1190 +                    return cancelWaiter(node, node, true);
1191              }
1192          }
1193      }
1194  
1195      /**
1196 <     * If node non-null, forces cancel status and unsplices from queue
1197 <     * if possible. This is a variant of cancellation methods in
1196 >     * If node non-null, forces cancel status and unsplices it from
1197 >     * queue if possible and wakes up any cowaiters (of the node, or
1198 >     * group, as applicable), and in any case helps release current
1199 >     * first waiter if lock is free. (Calling with null arguments
1200 >     * serves as a conditional form of release, which is not currently
1201 >     * needed but may be needed under possible future cancellation
1202 >     * policies). This is a variant of cancellation methods in
1203       * AbstractQueuedSynchronizer (see its detailed explanation in AQS
1204 <     * internal documentation) that more conservatively wakes up other
1205 <     * threads that may have had their links changed, so as to preserve
1206 <     * liveness in the main signalling methods.
1204 >     * internal documentation).
1205 >     *
1206 >     * @param node if nonnull, the waiter
1207 >     * @param group, either node or the group node is cowaiting with
1208 >     * @param interrupted if already interrupted
1209 >     * @return INTERRUPTED if interrupted or Thread.interrupted, else zero
1210       */
1211      private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1212 <        if (node != null) {
1213 <            node.thread = null;
1212 >        if (node != null && group != null) {
1213 >            Thread w;
1214              node.status = CANCELLED;
1215 <            if (group != null) {
1216 <                for (WNode p = group, q; p != null; p = q) {
1217 <                    if ((q = p.cowait) != null && q.status == CANCELLED) {
1218 <                        U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1219 <                        break;
1215 >            node.thread = null;
1216 >            // unsplice cancelled nodes from group
1217 >            for (WNode p = group, q; (q = p.cowait) != null;) {
1218 >                if (q.status == CANCELLED)
1219 >                    U.compareAndSwapObject(p, WNEXT, q, q.next);
1220 >                else
1221 >                    p = q;
1222 >            }
1223 >            if (group == node) {
1224 >                WNode r; // detach and wake up uncancelled co-waiters
1225 >                while ((r = node.cowait) != null) {
1226 >                    if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
1227 >                        (w = r.thread) != null) {
1228 >                        r.thread = null;
1229 >                        U.unpark(w);
1230                      }
1231                  }
1232 <            }
1233 <            else {
1181 <                for (WNode pred = node.prev; pred != null; ) {
1182 <                    WNode succ, pp; Thread w;
1232 >                for (WNode pred = node.prev; pred != null; ) { // unsplice
1233 >                    WNode succ, pp;        // find valid successor
1234                      while ((succ = node.next) == null ||
1235                             succ.status == CANCELLED) {
1236 <                        WNode q = null;
1236 >                        WNode q = null;    // find successor the slow way
1237                          for (WNode t = wtail; t != null && t != node; t = t.prev)
1238                              if (t.status != CANCELLED)
1239 <                                q = t;
1240 <                        if (succ == q ||
1239 >                                q = t;     // don't link if succ cancelled
1240 >                        if (succ == q ||   // ensure accurate successor
1241                              U.compareAndSwapObject(node, WNEXT,
1242                                                     succ, succ = q)) {
1243                              if (succ == null && node == wtail)
# Line 1194 | Line 1245 | public class StampedLock implements java
1245                              break;
1246                          }
1247                      }
1248 <                    if (pred.next == node)
1248 >                    if (pred.next == node) // unsplice pred link
1249                          U.compareAndSwapObject(pred, WNEXT, node, succ);
1250 <                    if (succ != null && (w = succ.thread) != null)
1251 <                        U.unpark(w);
1250 >                    if (succ != null && (w = succ.thread) != null) {
1251 >                        succ.thread = null;
1252 >                        U.unpark(w);       // wake up succ to observe new pred
1253 >                    }
1254                      if (pred.status != CANCELLED || (pp = pred.prev) == null)
1255                          break;
1256 <                    node.prev = pp; // repeat for new pred
1256 >                    node.prev = pp;        // repeat if new pred wrong/cancelled
1257                      U.compareAndSwapObject(pp, WNEXT, pred, succ);
1258                      pred = pp;
1259                  }
1260              }
1261          }
1262 <        release(whead);
1262 >        WNode h; // Possibly release first waiter
1263 >        while ((h = whead) != null) {
1264 >            long s; WNode q; // similar to release() but check eligibility
1265 >            if ((q = h.next) == null || q.status == CANCELLED) {
1266 >                for (WNode t = wtail; t != null && t != h; t = t.prev)
1267 >                    if (t.status <= 0)
1268 >                        q = t;
1269 >            }
1270 >            if (h == whead) {
1271 >                if (q != null && h.status == 0 &&
1272 >                    ((s = state) & ABITS) != WBIT && // waiter is eligible
1273 >                    (s == 0L || q.mode == RMODE))
1274 >                    release(h);
1275 >                break;
1276 >            }
1277 >        }
1278          return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1279      }
1280  

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines