jdk-sandbox: comparison jdk/src/share/classes/java/util/concurrent/locks/AbstractQueuedLongSynchronizer.java

equal deleted inserted replaced

-:8ea224e457c6
+:975a98680ae8
 static final int CANCELLED =  1;
 /** waitStatus value to indicate successor's thread needs unparking */
 static final int SIGNAL    = -1;
 /** waitStatus value to indicate thread is waiting on condition */
 static final int CONDITION = -2;
+/**
+* waitStatus value to indicate the next acquireShared should
+* unconditionally propagate
+*/
+static final int PROPAGATE = -3;
 /**
 * Status field, taking on only the values:
 *   SIGNAL:     The successor of this node is (or will soon be)
 *               blocked (via park), so the current node must
 *               on failure, block.
 *   CANCELLED:  This node is cancelled due to timeout or interrupt.
 *               Nodes never leave this state. In particular,
 *               a thread with cancelled node never again blocks.
 *   CONDITION:  This node is currently on a condition queue.
-*               It will not be used as a sync queue node until
+*               It will not be used as a sync queue node
-*               transferred. (Use of this value here
+*               until transferred, at which time the status
-*               has nothing to do with the other uses
+*               will be set to 0. (Use of this value here has
-*               of the field, but simplifies mechanics.)
+*               nothing to do with the other uses of the
+*               field, but simplifies mechanics.)
+*   PROPAGATE:  A releaseShared should be propagated to other
+*               nodes. This is set (for head node only) in
+*               doReleaseShared to ensure propagation
+*               continues, even if other operations have
+*               since intervened.
 *   0:          None of the above
 *
 * The values are arranged numerically to simplify use.
 * Non-negative values mean that a node doesn't need to
 * signal. So, most code doesn't need to check for particular
 *
 * @param node the node
 */
 private void unparkSuccessor(Node node) {
 /*
-* Try to clear status in anticipation of signalling.  It is
+* If status is negative (i.e., possibly needing signal) try
-* OK if this fails or if status is changed by waiting thread.
+* to clear in anticipation of signalling.  It is OK if this
-*/
+* fails or if status is changed by waiting thread.
-compareAndSetWaitStatus(node, Node.SIGNAL, 0);
+*/
+int ws = node.waitStatus;
+if (ws < 0)
+compareAndSetWaitStatus(node, ws, 0);
 /*
 * Thread to unpark is held in successor, which is normally
 * just the next node.  But if cancelled or apparently null,
 * traverse backwards from tail to find the actual
 if (s != null)
 LockSupport.unpark(s.thread);
 }
 /**
+* Release action for shared mode -- signal successor and ensure
+* propagation. (Note: For exclusive mode, release just amounts
+* to calling unparkSuccessor of head if it needs signal.)
+*/
+private void doReleaseShared() {
+/*
+* Ensure that a release propagates, even if there are other
+* in-progress acquires/releases.  This proceeds in the usual
+* way of trying to unparkSuccessor of head if it needs
+* signal. But if it does not, status is set to PROPAGATE to
+* ensure that upon release, propagation continues.
+* Additionally, we must loop in case a new node is added
+* while we are doing this. Also, unlike other uses of
+* unparkSuccessor, we need to know if CAS to reset status
+* fails, if so rechecking.
+*/
+for (;;) {
+Node h = head;
+if (h != null && h != tail) {
+int ws = h.waitStatus;
+if (ws == Node.SIGNAL) {
+if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
+continue;            // loop to recheck cases
+unparkSuccessor(h);
+}
+else if (ws == 0 &&
+!compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
+continue;                // loop on failed CAS
+}
+if (h == head)                   // loop if head changed
+break;
+}
+}
+/**
 * Sets head of queue, and checks if successor may be waiting
-* in shared mode, if so propagating if propagate > 0.
+* in shared mode, if so propagating if either propagate > 0 or
-*
+* PROPAGATE status was set.
-* @param pred the node holding waitStatus for node
+*
 * @param node the node
 * @param propagate the return value from a tryAcquireShared
 */
 private void setHeadAndPropagate(Node node, long propagate) {
+Node h = head; // Record old head for check below
 setHead(node);
-if (propagate > 0 && node.waitStatus != 0) {
+/*
-/*
+* Try to signal next queued node if:
-* Don't bother fully figuring out successor.  If it
+*   Propagation was indicated by caller,
-* looks null, call unparkSuccessor anyway to be safe.
+*     or was recorded (as h.waitStatus) by a previous operation
-*/
+*     (note: this uses sign-check of waitStatus because
+*      PROPAGATE status may transition to SIGNAL.)
+* and
+*   The next node is waiting in shared mode,
+*     or we don't know, because it appears null
+*
+* The conservatism in both of these checks may cause
+* unnecessary wake-ups, but only when there are multiple
+* racing acquires/releases, so most need signals now or soon
+* anyway.
+*/
+if (propagate > 0 || h == null || h.waitStatus < 0) {
 Node s = node.next;
 if (s == null || s.isShared())
-unparkSuccessor(node);
+doReleaseShared();
 }
 }
 // Utilities for various versions of acquire
 // Skip cancelled predecessors
 Node pred = node.prev;
 while (pred.waitStatus > 0)
 node.prev = pred = pred.prev;
-// Getting this before setting waitStatus ensures staleness
+// predNext is the apparent node to unsplice. CASes below will
+// fail if not, in which case, we lost race vs another cancel
+// or signal, so no further action is necessary.
 Node predNext = pred.next;
-// Can use unconditional write instead of CAS here
+// Can use unconditional write instead of CAS here.
+// After this atomic step, other Nodes can skip past us.
+// Before, we are free of interference from other threads.
 node.waitStatus = Node.CANCELLED;
-// If we are the tail, remove ourselves
+// If we are the tail, remove ourselves.
 if (node == tail && compareAndSetTail(node, pred)) {
 compareAndSetNext(pred, predNext, null);
 } else {
-// If "active" predecessor found...
+// If successor needs signal, try to set pred's next-link
-if (pred != head
+// so it will get one. Otherwise wake it up to propagate.
-&& (pred.waitStatus == Node.SIGNAL
+int ws;
-|| compareAndSetWaitStatus(pred, 0, Node.SIGNAL))
+if (pred != head &&
-&& pred.thread != null) {
+((ws = pred.waitStatus) == Node.SIGNAL ||
+(ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
-// If successor is active, set predecessor's next link
+pred.thread != null) {
 Node next = node.next;
 if (next != null && next.waitStatus <= 0)
 compareAndSetNext(pred, predNext, next);
 } else {
 unparkSuccessor(node);
 * @param pred node's predecessor holding status
 * @param node the node
 * @return {@code true} if thread should block
 */
 private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
-int s = pred.waitStatus;
+int ws = pred.waitStatus;
-if (s < 0)
+if (ws == Node.SIGNAL)
 /*
 * This node has already set status asking a release
 * to signal it, so it can safely park.
 */
 return true;
-if (s > 0) {
+if (ws > 0) {
 /*
 * Predecessor was cancelled. Skip over predecessors and
 * indicate retry.
 */
 do {
 node.prev = pred = pred.prev;
 } while (pred.waitStatus > 0);
 pred.next = node;
-}
+} else {
-else
 /*
-* Indicate that we need a signal, but don't park yet. Caller
+* waitStatus must be 0 or PROPAGATE.  Indicate that we
-* will need to retry to make sure it cannot acquire before
+* need a signal, but don't park yet.  Caller will need to
-* parking.
+* retry to make sure it cannot acquire before parking.
 */
-compareAndSetWaitStatus(pred, 0, Node.SIGNAL);
+compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
+}
 return false;
 }
 /**
 * Convenience method to interrupt current thread.
 *        and can represent anything you like.
 * @return the value returned from {@link #tryReleaseShared}
 */
 public final boolean releaseShared(long arg) {
 if (tryReleaseShared(arg)) {
-Node h = head;
+doReleaseShared();
-if (h != null && h.waitStatus != 0)
-unparkSuccessor(h);
 return true;
 }
 return false;
 }
 * indicate that thread is (probably) waiting. If cancelled or
 * attempt to set waitStatus fails, wake up to resync (in which
 * case the waitStatus can be transiently and harmlessly wrong).
 */
 Node p = enq(node);
-int c = p.waitStatus;
+int ws = p.waitStatus;
-if (c > 0 || !compareAndSetWaitStatus(p, c, Node.SIGNAL))
+if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
 LockSupport.unpark(node.thread);
 return true;
 }
 /**

changeset 2430	975a98680ae8
parent 2165	98373487fcf4
child 5506	202f599c92aa