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.36 by dl, Wed Jun 19 14:55:40 2013 UTC

# Line 5 | Line 5
5   */
6  
7   package jsr166e;
8
9 import java.util.concurrent.ThreadLocalRandom;
8   import java.util.concurrent.TimeUnit;
9 < import java.util.concurrent.locks.*;
9 > import java.util.concurrent.ThreadLocalRandom;
10 > import java.util.concurrent.locks.Lock;
11 > import java.util.concurrent.locks.Condition;
12 > import java.util.concurrent.locks.ReadWriteLock;
13 > import java.util.concurrent.locks.LockSupport;
14  
15   /**
16   * A capability-based lock with three modes for controlling read/write
# Line 37 | Line 39 | import java.util.concurrent.locks.*;
39   *  <li><b>Optimistic Reading.</b> Method {@link #tryOptimisticRead}
40   *   returns a non-zero stamp only if the lock is not currently held
41   *   in write mode. Method {@link #validate} returns true if the lock
42 < *   has not since been acquired in write mode. This mode can be
43 < *   thought of as an extremely weak version of a read-lock, that can
44 < *   be broken by a writer at any time.  The use of optimistic mode
45 < *   for short read-only code segments often reduces contention and
46 < *   improves throughput.  However, its use is inherently fragile.
47 < *   Optimistic read sections should only read fields and hold them in
48 < *   local variables for later use after validation. Fields read while
49 < *   in optimistic mode may be wildly inconsistent, so usage applies
50 < *   only when you are familiar enough with data representations to
51 < *   check consistency and/or repeatedly invoke method {@code
52 < *   validate()}.  For example, such steps are typically required when
53 < *   first reading an object or array reference, and then accessing
54 < *   one of its fields, elements or methods. </li>
42 > *   has not been acquired in write mode since obtaining a given
43 > *   stamp.  This mode can be thought of as an extremely weak version
44 > *   of a read-lock, that can be broken by a writer at any time.  The
45 > *   use of optimistic mode for short read-only code segments often
46 > *   reduces contention and improves throughput.  However, its use is
47 > *   inherently fragile.  Optimistic read sections should only read
48 > *   fields and hold them in local variables for later use after
49 > *   validation. Fields read while in optimistic mode may be wildly
50 > *   inconsistent, so usage applies only when you are familiar enough
51 > *   with data representations to check consistency and/or repeatedly
52 > *   invoke method {@code validate()}.  For example, such steps are
53 > *   typically required when first reading an object or array
54 > *   reference, and then accessing one of its fields, elements or
55 > *   methods. </li>
56   *
57   * </ul>
58   *
# Line 115 | Line 118 | import java.util.concurrent.locks.*;
118   *     }
119   *   }
120   *
121 < *   double distanceFromOriginV1() { // A read-only method
122 < *     long stamp;
123 < *     if ((stamp = sl.tryOptimisticRead()) != 0L) { // optimistic
124 < *       double currentX = x;
125 < *       double currentY = y;
126 < *       if (sl.validate(stamp))
127 < *         return Math.sqrt(currentX * currentX + currentY * currentY);
128 < *     }
129 < *     stamp = sl.readLock(); // fall back to read lock
130 < *     try {
131 < *       double currentX = x;
129 < *       double currentY = y;
130 < *         return Math.sqrt(currentX * currentX + currentY * currentY);
131 < *     } finally {
132 < *       sl.unlockRead(stamp);
133 < *     }
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()) {
139 < *       try {
140 < *         currentX = x;
141 < *         currentY = y;
142 < *       } finally {
143 < *         if (sl.tryConvertToOptimisticRead(stamp) != 0L) // unlock or validate
144 < *           break;
145 < *       }
121 > *   double distanceFromOrigin() { // A read-only method
122 > *     long stamp = sl.tryOptimisticRead();
123 > *     double currentX = x, currentY = y;
124 > *     if (!sl.validate(stamp)) {
125 > *        stamp = sl.readLock();
126 > *        try {
127 > *          currentX = x;
128 > *          currentY = y;
129 > *        } finally {
130 > *           sl.unlockRead(stamp);
131 > *        }
132   *     }
133   *     return Math.sqrt(currentX * currentX + currentY * currentY);
134   *   }
# Line 198 | Line 184 | public class StampedLock implements java
184       *
185       * Waiters use a modified form of CLH lock used in
186       * AbstractQueuedSynchronizer (see its internal documentation for
187 <     * a fuller account), where each node it tagged (field mode) as
187 >     * a fuller account), where each node is tagged (field mode) as
188       * either a reader or writer. Sets of waiting readers are grouped
189       * (linked) under a common node (field cowait) so act as a single
190 <     * node with respect to most CLH mechanics.  By virtue of its
191 <     * structure, wait nodes need not actually carry sequence numbers;
192 <     * we know each is >= its predecessor.  These queue mechanics
193 <     * simplify the scheduling policy to a mainly-FIFO scheme that
190 >     * node with respect to most CLH mechanics.  By virtue of the
191 >     * queue structure, wait nodes need not actually carry sequence
192 >     * numbers; we know each is greater than its predecessor.  This
193 >     * simplifies the scheduling policy to a mainly-FIFO scheme that
194       * incorporates elements of Phase-Fair locks (see Brandenburg &
195       * Anderson, especially http://www.cs.unc.edu/~bbb/diss/).  In
196       * particular, we use the phase-fair anti-barging rule: If an
# Line 229 | Line 215 | public class StampedLock implements java
215       *
216       * Nearly all of these mechanics are carried out in methods
217       * acquireWrite and acquireRead, that, as typical of such code,
218 <     * sprawl out because actions and retries rely on consitent sets
219 <     * of locally cahced reads.
218 >     * sprawl out because actions and retries rely on consistent sets
219 >     * of locally cached reads.
220       *
221       * As noted in Boehm's paper (above), sequence validation (mainly
222       * method validate()) requires stricter ordering rules than apply
# Line 329 | Line 315 | public class StampedLock implements java
315       * @return a stamp that can be used to unlock or convert mode
316       */
317      public long writeLock() {
318 <        long s, next;  // bypass acquireWrite in fully onlocked case only
318 >        long s, next;  // bypass acquireWrite in fully unlocked case only
319          return ((((s = state) & ABITS) == 0L &&
320                   U.compareAndSwapLong(this, STATE, s, next = s + WBIT)) ?
321                  next : acquireWrite(false, 0L));
# Line 354 | Line 340 | public class StampedLock implements java
340       * Behavior under timeout and interruption matches that specified
341       * for method {@link Lock#tryLock(long,TimeUnit)}.
342       *
343 +     * @param time the maximum time to wait for the lock
344 +     * @param unit the time unit of the {@code time} argument
345       * @return a stamp that can be used to unlock or convert mode,
346       * or zero if the lock is not available
347       * @throws InterruptedException if the current thread is interrupted
# Line 364 | Line 352 | public class StampedLock implements java
352          long nanos = unit.toNanos(time);
353          if (!Thread.interrupted()) {
354              long next, deadline;
355 <            if ((next = tryWriteLock()) != 0)
355 >            if ((next = tryWriteLock()) != 0L)
356                  return next;
357              if (nanos <= 0L)
358                  return 0L;
# Line 401 | Line 389 | public class StampedLock implements java
389       * @return a stamp that can be used to unlock or convert mode
390       */
391      public long readLock() {
392 <        long s, next;  // bypass acquireRead on fully onlocked case only
392 >        long s, next;  // bypass acquireRead on fully unlocked case only
393          return ((((s = state) & ABITS) == 0L &&
394                   U.compareAndSwapLong(this, STATE, s, next = s + RUNIT)) ?
395                  next : acquireRead(false, 0L));
# Line 433 | Line 421 | public class StampedLock implements java
421       * Behavior under timeout and interruption matches that specified
422       * for method {@link Lock#tryLock(long,TimeUnit)}.
423       *
424 +     * @param time the maximum time to wait for the lock
425 +     * @param unit the time unit of the {@code time} argument
426       * @return a stamp that can be used to unlock or convert mode,
427       * or zero if the lock is not available
428       * @throws InterruptedException if the current thread is interrupted
# Line 440 | Line 430 | public class StampedLock implements java
430       */
431      public long tryReadLock(long time, TimeUnit unit)
432          throws InterruptedException {
433 <        long next, deadline;
433 >        long s, m, next, deadline;
434          long nanos = unit.toNanos(time);
435          if (!Thread.interrupted()) {
436 <            if ((next = tryReadLock()) != 0)
437 <                return next;
436 >            if ((m = (s = state) & ABITS) != WBIT) {
437 >                if (m < RFULL) {
438 >                    if (U.compareAndSwapLong(this, STATE, s, next = s + RUNIT))
439 >                        return next;
440 >                }
441 >                else if ((next = tryIncReaderOverflow(s)) != 0L)
442 >                    return next;
443 >            }
444              if (nanos <= 0L)
445                  return 0L;
446              if ((deadline = System.nanoTime() + nanos) == 0L)
# Line 488 | Line 484 | public class StampedLock implements java
484       * Returns true if the lock has not been exclusively acquired
485       * since issuance of the given stamp. Always returns false if the
486       * stamp is zero. Always returns true if the stamp represents a
487 <     * currently held lock.
487 >     * currently held lock. Invoking this method with a value not
488 >     * obtained from {@link #tryOptimisticRead} or a locking method
489 >     * for this lock has no defined effect or result.
490       *
491 <     * @return true if the lock has not been exclusively acquired
491 >     * @param stamp a stamp
492 >     * @return {@code true} if the lock has not been exclusively acquired
493       * since issuance of the given stamp; else false
494       */
495      public boolean validate(long stamp) {
# Line 524 | Line 523 | public class StampedLock implements java
523       * not match the current state of this lock
524       */
525      public void unlockRead(long stamp) {
526 <        long s, m;  WNode h;
527 <        if ((stamp & RBITS) != 0L) {
528 <            while (((s = state) & SBITS) == (stamp & SBITS)) {
529 <                if ((m = s & ABITS) == 0L)
526 >        long s, m; WNode h;
527 >        for (;;) {
528 >            if (((s = state) & SBITS) != (stamp & SBITS) ||
529 >                (stamp & ABITS) == 0L || (m = s & ABITS) == 0L || m == WBIT)
530 >                throw new IllegalMonitorStateException();
531 >            if (m < RFULL) {
532 >                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
533 >                    if (m == RUNIT && (h = whead) != null && h.status != 0)
534 >                        release(h);
535                      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                    }
536                  }
539                else if (m >= WBIT)
540                    break;
541                else if (tryDecReaderOverflow(s) != 0L)
542                    return;
537              }
538 +            else if (tryDecReaderOverflow(s) != 0L)
539 +                break;
540          }
545        throw new IllegalMonitorStateException();
541      }
542  
543      /**
# Line 707 | Line 702 | public class StampedLock implements java
702       * stamp value. This method may be useful for recovery after
703       * errors.
704       *
705 <     * @return true if the lock was held, else false
705 >     * @return {@code true} if the lock was held, else false
706       */
707      public boolean tryUnlockWrite() {
708          long s; WNode h;
# Line 725 | Line 720 | public class StampedLock implements java
720       * requiring a stamp value. This method may be useful for recovery
721       * after errors.
722       *
723 <     * @return true if the read lock was held, else false
723 >     * @return {@code true} if the read lock was held, else false
724       */
725      public boolean tryUnlockRead() {
726          long s, m; WNode h;
# Line 743 | Line 738 | public class StampedLock implements java
738          return false;
739      }
740  
741 +    // status monitoring methods
742 +
743 +    /**
744 +     * Returns combined state-held and overflow read count for given
745 +     * state s.
746 +     */
747 +    private int getReadLockCount(long s) {
748 +        long readers;
749 +        if ((readers = s & RBITS) >= RFULL)
750 +            readers = RFULL + readerOverflow;
751 +        return (int) readers;
752 +    }
753 +
754      /**
755 <     * Returns true if the lock is currently held exclusively.
755 >     * Returns {@code true} if the lock is currently held exclusively.
756       *
757 <     * @return true if the lock is currently held exclusively
757 >     * @return {@code true} if the lock is currently held exclusively
758       */
759      public boolean isWriteLocked() {
760          return (state & WBIT) != 0L;
761      }
762  
763      /**
764 <     * Returns true if the lock is currently held non-exclusively.
764 >     * Returns {@code true} if the lock is currently held non-exclusively.
765       *
766 <     * @return true if the lock is currently held non-exclusively
766 >     * @return {@code true} if the lock is currently held non-exclusively
767       */
768      public boolean isReadLocked() {
769          return (state & RBITS) != 0L;
770      }
771  
772 <    private void readObject(java.io.ObjectInputStream s)
773 <        throws java.io.IOException, ClassNotFoundException {
774 <        s.defaultReadObject();
775 <        state = ORIGIN; // reset to unlocked state
772 >    /**
773 >     * Queries the number of read locks held for this lock. This
774 >     * method is designed for use in monitoring system state, not for
775 >     * synchronization control.
776 >     * @return the number of read locks held
777 >     */
778 >    public int getReadLockCount() {
779 >        return getReadLockCount(state);
780      }
781  
782      /**
783 +     * Returns a string identifying this lock, as well as its lock
784 +     * state.  The state, in brackets, includes the String {@code
785 +     * "Unlocked"} or the String {@code "Write-locked"} or the String
786 +     * {@code "Read-locks:"} followed by the current number of
787 +     * read-locks held.
788 +     *
789 +     * @return a string identifying this lock, as well as its lock state
790 +     */
791 +    public String toString() {
792 +        long s = state;
793 +        return super.toString() +
794 +            ((s & ABITS) == 0L ? "[Unlocked]" :
795 +             (s & WBIT) != 0L ? "[Write-locked]" :
796 +             "[Read-locks:" + getReadLockCount(s) + "]");
797 +    }
798 +
799 +    // views
800 +
801 +    /**
802       * Returns a plain {@link Lock} view of this StampedLock in which
803       * the {@link Lock#lock} method is mapped to {@link #readLock},
804       * and similarly for other methods. The returned Lock does not
# Line 825 | Line 856 | public class StampedLock implements java
856              throws InterruptedException {
857              return tryReadLock(time, unit) != 0L;
858          }
859 <        // note that we give up ability to check mode so just use current state
829 <        public void unlock() { unlockRead(state); }
859 >        public void unlock() { unstampedUnlockRead(); }
860          public Condition newCondition() {
861              throw new UnsupportedOperationException();
862          }
# Line 842 | Line 872 | public class StampedLock implements java
872              throws InterruptedException {
873              return tryWriteLock(time, unit) != 0L;
874          }
875 <        public void unlock() { unlockWrite(state); }
875 >        public void unlock() { unstampedUnlockWrite(); }
876          public Condition newCondition() {
877              throw new UnsupportedOperationException();
878          }
# Line 853 | Line 883 | public class StampedLock implements java
883          public Lock writeLock() { return asWriteLock(); }
884      }
885  
886 +    // Unlock methods without stamp argument checks for view classes.
887 +    // Needed because view-class lock methods throw away stamps.
888 +
889 +    final void unstampedUnlockWrite() {
890 +        WNode h; long s;
891 +        if (((s = state) & WBIT) == 0L)
892 +            throw new IllegalMonitorStateException();
893 +        state = (s += WBIT) == 0L ? ORIGIN : s;
894 +        if ((h = whead) != null && h.status != 0)
895 +            release(h);
896 +    }
897 +
898 +    final void unstampedUnlockRead() {
899 +        for (;;) {
900 +            long s, m; WNode h;
901 +            if ((m = (s = state) & ABITS) == 0L || m >= WBIT)
902 +                throw new IllegalMonitorStateException();
903 +            else if (m < RFULL) {
904 +                if (U.compareAndSwapLong(this, STATE, s, s - RUNIT)) {
905 +                    if (m == RUNIT && (h = whead) != null && h.status != 0)
906 +                        release(h);
907 +                    break;
908 +                }
909 +            }
910 +            else if (tryDecReaderOverflow(s) != 0L)
911 +                break;
912 +        }
913 +    }
914 +
915 +    private void readObject(java.io.ObjectInputStream s)
916 +        throws java.io.IOException, ClassNotFoundException {
917 +        s.defaultReadObject();
918 +        state = ORIGIN; // reset to unlocked state
919 +    }
920 +
921      // internals
922  
923      /**
# Line 860 | Line 925 | public class StampedLock implements java
925       * access bits value to RBITS, indicating hold of spinlock,
926       * then updating, then releasing.
927       *
928 <     * @param s, assumed that (s & ABITS) >= RFULL
928 >     * @param s a reader overflow stamp: (s & ABITS) >= RFULL
929       * @return new stamp on success, else zero
930       */
931      private long tryIncReaderOverflow(long s) {
932 +        // assert (s & ABITS) >= RFULL;
933          if ((s & ABITS) == RFULL) {
934              if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
935                  ++readerOverflow;
# Line 880 | Line 946 | public class StampedLock implements java
946      /**
947       * Tries to decrement readerOverflow.
948       *
949 <     * @param s, assumed that (s & ABITS) >= RFULL
949 >     * @param s a reader overflow stamp: (s & ABITS) >= RFULL
950       * @return new stamp on success, else zero
951       */
952      private long tryDecReaderOverflow(long s) {
953 +        // assert (s & ABITS) >= RFULL;
954          if ((s & ABITS) == RFULL) {
955              if (U.compareAndSwapLong(this, STATE, s, s | RBITS)) {
956                  int r; long next;
# Line 903 | Line 970 | public class StampedLock implements java
970          return 0L;
971      }
972  
973 <    /*
973 >    /**
974       * Wakes up the successor of h (normally whead). This is normally
975       * just h.next, but may require traversal from wtail if next
976       * pointers are lagging. This may fail to wake up an acquiring
# Line 977 | Line 1044 | public class StampedLock implements java
1044                  (p = np).next = node;   // stale
1045              if (whead == p) {
1046                  for (int k = spins;;) { // spin at head
1047 <                    if (((s = state) & ABITS) == 0L &&
1048 <                        U.compareAndSwapLong(this, STATE, s, ns = s + WBIT)) {
1049 <                        whead = node;
1050 <                        node.prev = null;
1051 <                        return ns;
1047 >                    if (((s = state) & ABITS) == 0L) {
1048 >                        if (U.compareAndSwapLong(this, STATE, s, ns = s+WBIT)) {
1049 >                            whead = node;
1050 >                            node.prev = null;
1051 >                            return ns;
1052 >                        }
1053                      }
1054                      else if (ThreadLocalRandom.current().nextInt() >= 0 &&
1055                               --k <= 0)
# Line 1003 | Line 1071 | public class StampedLock implements java
1071                  if (deadline == 0L)
1072                      time = 0L;
1073                  else if ((time = deadline - System.nanoTime()) <= 0L)
1074 <                    return cancelWaiter(node, null, false);
1075 <                node.thread = Thread.currentThread();
1074 >                    return cancelWaiter(node, node, false);
1075 >                Thread wt = Thread.currentThread();
1076 >                U.putObject(wt, PARKBLOCKER, this); // emulate LockSupport.park
1077 >                node.thread = wt;
1078                  if (node.prev == p && p.status == WAITING && // recheck
1079 <                    (p != whead || (state & ABITS) != 0L)) {
1079 >                    (p != whead || (state & ABITS) != 0L))
1080                      U.park(false, time);
1011                    if (interruptible && Thread.interrupted())
1012                        return cancelWaiter(node, null, true);
1013                }
1081                  node.thread = null;
1082 +                U.putObject(wt, PARKBLOCKER, null);
1083 +                if (interruptible && Thread.interrupted())
1084 +                    return cancelWaiter(node, node, true);
1085              }
1086          }
1087      }
# Line 1033 | Line 1103 | public class StampedLock implements java
1103                  if (group == null && (h = whead) != null &&
1104                      (q = h.next) != null && q.mode != RMODE)
1105                      break;
1106 <                if ((m = (s = state) & ABITS) == WBIT)
1037 <                    break;
1038 <                if (m < RFULL ?
1106 >                if ((m = (s = state) & ABITS) < RFULL ?
1107                      U.compareAndSwapLong(this, STATE, s, ns = s + RUNIT) :
1108 <                    (ns = tryIncReaderOverflow(s)) != 0L) {
1108 >                    (m < WBIT && (ns = tryIncReaderOverflow(s)) != 0L)) {
1109                      if (group != null) {  // help release others
1110                          for (WNode r = group;;) {
1111                              if ((w = r.thread) != null) {
# Line 1051 | Line 1119 | public class StampedLock implements java
1119                      }
1120                      return ns;
1121                  }
1122 +                if (m >= WBIT)
1123 +                    break;
1124              }
1125              if (spins > 0) {
1126                  if (ThreadLocalRandom.current().nextInt() >= 0)
# Line 1085 | Line 1155 | public class StampedLock implements java
1155                              node.thread = null;
1156                              break;
1157                          }
1158 +                        Thread wt = Thread.currentThread();
1159 +                        U.putObject(wt, PARKBLOCKER, this);
1160                          if (node.thread == null) // must recheck
1161                              break;
1162                          U.park(false, time);
1163 +                        U.putObject(wt, PARKBLOCKER, null);
1164                          if (interruptible && Thread.interrupted())
1165                              return cancelWaiter(node, p, true);
1166                      }
# Line 1144 | Line 1217 | public class StampedLock implements java
1217                  if (deadline == 0L)
1218                      time = 0L;
1219                  else if ((time = deadline - System.nanoTime()) <= 0L)
1220 <                    return cancelWaiter(node, null, false);
1221 <                node.thread = Thread.currentThread();
1220 >                    return cancelWaiter(node, node, false);
1221 >                Thread wt = Thread.currentThread();
1222 >                U.putObject(wt, PARKBLOCKER, this);
1223 >                node.thread = wt;
1224                  if (node.prev == p && p.status == WAITING &&
1225 <                    (p != whead || (state & ABITS) != WBIT)) {
1225 >                    (p != whead || (state & ABITS) != WBIT))
1226                      U.park(false, time);
1152                    if (interruptible && Thread.interrupted())
1153                        return cancelWaiter(node, null, true);
1154                }
1227                  node.thread = null;
1228 +                U.putObject(wt, PARKBLOCKER, null);
1229 +                if (interruptible && Thread.interrupted())
1230 +                    return cancelWaiter(node, node, true);
1231              }
1232          }
1233      }
1234  
1235      /**
1236 <     * If node non-null, forces cancel status and unsplices from queue
1237 <     * if possible. This is a variant of cancellation methods in
1236 >     * If node non-null, forces cancel status and unsplices it from
1237 >     * queue if possible and wakes up any cowaiters (of the node, or
1238 >     * group, as applicable), and in any case helps release current
1239 >     * first waiter if lock is free. (Calling with null arguments
1240 >     * serves as a conditional form of release, which is not currently
1241 >     * needed but may be needed under possible future cancellation
1242 >     * policies). This is a variant of cancellation methods in
1243       * AbstractQueuedSynchronizer (see its detailed explanation in AQS
1244 <     * internal documentation) that more conservatively wakes up other
1245 <     * threads that may have had their links changed, so as to preserve
1246 <     * liveness in the main signalling methods.
1244 >     * internal documentation).
1245 >     *
1246 >     * @param node if nonnull, the waiter
1247 >     * @param group either node or the group node is cowaiting with
1248 >     * @param interrupted if already interrupted
1249 >     * @return INTERRUPTED if interrupted or Thread.interrupted, else zero
1250       */
1251      private long cancelWaiter(WNode node, WNode group, boolean interrupted) {
1252 <        if (node != null) {
1253 <            node.thread = null;
1252 >        if (node != null && group != null) {
1253 >            Thread w;
1254              node.status = CANCELLED;
1255 <            if (group != null) {
1256 <                for (WNode p = group, q; p != null; p = q) {
1257 <                    if ((q = p.cowait) != null && q.status == CANCELLED) {
1258 <                        U.compareAndSwapObject(p, WCOWAIT, q, q.cowait);
1259 <                        break;
1255 >            node.thread = null;
1256 >            // unsplice cancelled nodes from group
1257 >            for (WNode p = group, q; (q = p.cowait) != null;) {
1258 >                if (q.status == CANCELLED)
1259 >                    U.compareAndSwapObject(p, WNEXT, q, q.next);
1260 >                else
1261 >                    p = q;
1262 >            }
1263 >            if (group == node) {
1264 >                WNode r; // detach and wake up uncancelled co-waiters
1265 >                while ((r = node.cowait) != null) {
1266 >                    if (U.compareAndSwapObject(node, WCOWAIT, r, r.cowait) &&
1267 >                        (w = r.thread) != null) {
1268 >                        r.thread = null;
1269 >                        U.unpark(w);
1270                      }
1271                  }
1272 <            }
1273 <            else {
1181 <                for (WNode pred = node.prev; pred != null; ) {
1182 <                    WNode succ, pp; Thread w;
1272 >                for (WNode pred = node.prev; pred != null; ) { // unsplice
1273 >                    WNode succ, pp;        // find valid successor
1274                      while ((succ = node.next) == null ||
1275                             succ.status == CANCELLED) {
1276 <                        WNode q = null;
1276 >                        WNode q = null;    // find successor the slow way
1277                          for (WNode t = wtail; t != null && t != node; t = t.prev)
1278                              if (t.status != CANCELLED)
1279 <                                q = t;
1280 <                        if (succ == q ||
1279 >                                q = t;     // don't link if succ cancelled
1280 >                        if (succ == q ||   // ensure accurate successor
1281                              U.compareAndSwapObject(node, WNEXT,
1282                                                     succ, succ = q)) {
1283                              if (succ == null && node == wtail)
# Line 1194 | Line 1285 | public class StampedLock implements java
1285                              break;
1286                          }
1287                      }
1288 <                    if (pred.next == node)
1288 >                    if (pred.next == node) // unsplice pred link
1289                          U.compareAndSwapObject(pred, WNEXT, node, succ);
1290 <                    if (succ != null && (w = succ.thread) != null)
1291 <                        U.unpark(w);
1290 >                    if (succ != null && (w = succ.thread) != null) {
1291 >                        succ.thread = null;
1292 >                        U.unpark(w);       // wake up succ to observe new pred
1293 >                    }
1294                      if (pred.status != CANCELLED || (pp = pred.prev) == null)
1295                          break;
1296 <                    node.prev = pp; // repeat for new pred
1296 >                    node.prev = pp;        // repeat if new pred wrong/cancelled
1297                      U.compareAndSwapObject(pp, WNEXT, pred, succ);
1298                      pred = pp;
1299                  }
1300              }
1301          }
1302 <        release(whead);
1302 >        WNode h; // Possibly release first waiter
1303 >        while ((h = whead) != null) {
1304 >            long s; WNode q; // similar to release() but check eligibility
1305 >            if ((q = h.next) == null || q.status == CANCELLED) {
1306 >                for (WNode t = wtail; t != null && t != h; t = t.prev)
1307 >                    if (t.status <= 0)
1308 >                        q = t;
1309 >            }
1310 >            if (h == whead) {
1311 >                if (q != null && h.status == 0 &&
1312 >                    ((s = state) & ABITS) != WBIT && // waiter is eligible
1313 >                    (s == 0L || q.mode == RMODE))
1314 >                    release(h);
1315 >                break;
1316 >            }
1317 >        }
1318          return (interrupted || Thread.interrupted()) ? INTERRUPTED : 0L;
1319      }
1320  
# Line 1218 | Line 1326 | public class StampedLock implements java
1326      private static final long WNEXT;
1327      private static final long WSTATUS;
1328      private static final long WCOWAIT;
1329 +    private static final long PARKBLOCKER;
1330  
1331      static {
1332          try {
# Line 1236 | Line 1345 | public class StampedLock implements java
1345                  (wk.getDeclaredField("next"));
1346              WCOWAIT = U.objectFieldOffset
1347                  (wk.getDeclaredField("cowait"));
1348 +            Class<?> tk = Thread.class;
1349 +            PARKBLOCKER = U.objectFieldOffset
1350 +                (tk.getDeclaredField("parkBlocker"));
1351  
1352          } catch (Exception e) {
1353              throw new Error(e);

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines