activemq-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From tab...@apache.org
Subject svn commit: r1368228 - /activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/concurrent/locks/AbstractQueuedSynchronizer.cpp
Date Wed, 01 Aug 2012 20:07:55 GMT
Author: tabish
Date: Wed Aug  1 20:07:54 2012
New Revision: 1368228

URL: http://svn.apache.org/viewvc?rev=1368228&view=rev
Log:
Minor code cleanup and docs added

Modified:
    activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/concurrent/locks/AbstractQueuedSynchronizer.cpp

Modified: activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/concurrent/locks/AbstractQueuedSynchronizer.cpp
URL: http://svn.apache.org/viewvc/activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/concurrent/locks/AbstractQueuedSynchronizer.cpp?rev=1368228&r1=1368227&r2=1368228&view=diff
==============================================================================
--- activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/concurrent/locks/AbstractQueuedSynchronizer.cpp
(original)
+++ activemq/activemq-cpp/trunk/activemq-cpp/src/main/decaf/util/concurrent/locks/AbstractQueuedSynchronizer.cpp
Wed Aug  1 20:07:54 2012
@@ -41,6 +41,71 @@ using namespace decaf::internal::util::c
 ////////////////////////////////////////////////////////////////////////////////
 namespace {
 
+    /**
+     * Wait queue node class.
+     *
+     * The wait queue is a variant of a "CLH" (Craig, Landin, and Hagersten)
+     * lock queue. CLH locks are normally used for spinlocks.  We instead use
+     * them for blocking synchronizers, but use the same basic tactic of holding
+     * some of the control information about a thread in the predecessor of its
+     * node.  A "status" field in each node keeps track of whether a thread
+     * should block.  A node is signalled when its predecessor releases.  Each
+     * node of the queue otherwise serves as a specific-notification-style monitor
+     * holding a single waiting thread. The status field does NOT control whether
+     * threads are granted locks etc though.  A thread may try to acquire if it is
+     * first in the queue. But being first does not guarantee success; it only gives
+     * the right to contend.  So the currently released contender thread may need
+     * to rewait.
+     *
+     * To enqueue into a CLH lock, you atomically splice it in as new tail.
+     * To dequeue, you just set the head field.
+     * <pre>
+     *      +------+  prev +-----+       +-----+
+     * head |      | <---- |     | <---- |     |  tail
+     *      +------+       +-----+       +-----+
+     * </pre>
+     *
+     * Insertion into a CLH queue requires only a single atomic operation on "tail", so
+     * there is a simple atomic point of demarcation from unqueued to queued. Similarly,
+     * dequeing involves only updating the "head". However, it takes a bit more work for
+     * nodes to determine who their successors are, in part to deal with possible
+     * cancellation due to timeouts and interrupts.
+     *
+     * The "prev" links (not used in original CLH locks), are mainly needed to handle
+     * cancellation. If a node is cancelled, its successor is (normally) relinked to a
+     * non-cancelled predecessor. For explanation of similar mechanics in the case of
+     * spin locks, see the papers by Scott and Scherer at:
+     *
+     *     http://www.cs.rochester.edu/u/scott/synchronization/
+     *
+     * We also use "next" links to implement blocking mechanics. The thread id for
+     * each node is kept in its own node, so a predecessor signals the next node to
+     * wake up by traversing next link to determine which thread it is.  Determination
+     * of successor must avoid races with newly queued nodes to set the "next" fields
+     * of their predecessors.  This is solved when necessary by checking backwards
+     * from the atomically updated "tail" when a node's successor appears to be null.
+     * (Or, said differently, the next-links are an optimization so that we don't
+     * usually need a backward scan.)
+     *
+     * Cancellation introduces some conservatism to the basic algorithms.  Since we
+     * must poll for cancellation of other nodes, we can miss noticing whether a
+     * cancelled node is ahead or behind us. This is dealt with by always unparking
+     * successors upon cancellation, allowing them to stabilize on a new predecessor,
+     * unless we can identify an uncancelled predecessor who will carry this
+     * responsibility.
+     *
+     * CLH queues need a dummy header node to get started. But we don't create them on
+     * construction, because it would be wasted effort if there is never contention.
+     * Instead, the node is constructed and head and tail pointers are set upon first
+     * contention.
+     *
+     * Threads waiting on Conditions use the same nodes, but use an additional link.
+     * Conditions only need to link nodes in simple (non-concurrent) linked queues
+     * because they are only accessed when exclusively held.  Upon await, a node is
+     * inserted into a condition queue.  Upon signal, the node is transferred to the
+     * main queue.  A special value of status field is used to mark which queue a node
+     * is on.
+     */
     class Node {
     public:
 
@@ -87,39 +152,38 @@ namespace {
         /**
          * Link to predecessor node that current node/thread relies on
          * for checking waitStatus. Assigned during enqueing, and nulled
-         * out.  Also, upon cancellation of a predecessor, we short-circuit
-         * while finding a non-canceled one, which will always exist because
-         * the head node is never canceled: A node becomes head only as a
-         * result of successful acquire. A canceled thread never succeeds
-         * in acquiring, and a thread only cancels itself, not any other node.
+         * out only upon dequeuing.  Also, upon cancellation of a predecessor,
+         * we short-circuit while finding a non-canceled one, which will always
+         * exist because the head node is never canceled: A node becomes head
+         * only as a result of successful acquire. A canceled thread never
+         * succeeds in acquiring, and a thread only cancels itself, not any
+         * other node.
          */
         Node* prev;
 
         /**
-         * Link to the successor node that the current node/thread
-         * unparks upon release. Assigned during enqueuing, adjusted
-         * when bypassing canceled predecessors, and nulled out when
-         * dequeued.  The enq operation does not assign next field of
-         * a predecessor until after attachment, so seeing a NULL next
-         * field does not necessarily mean that node is at end of queue.
-         * However, if a next field appears to be NULL, we can scan
-         * prev's from the tail to double-check.
+         * Link to the successor node that the current node/thread unparks upon
+         * release. Assigned during enqueuing, adjusted when bypassing canceled
+         * predecessors, and nulled out when dequeued.  The enq operation does not
+         * assign next field of a predecessor until after attachment, so seeing a
+         * NULL next field does not necessarily mean that node is at end of queue.
+         * However, if a next field appears to be NULL, we can scan prev's from the
+         * tail to double-check.
          */
         Node* next;
 
         /**
-         * The thread that created this Node as is waiting to acquire the
-         * lock.
+         * The thread that created this Node as is waiting to acquire the lock.
          */
         Thread* thread;
 
         /**
-         * Link to next node waiting on condition, or the special value SHARED.
-         * Because condition queues are accessed only when holding in exclusive
-         * mode, we just need a simple linked queue to hold nodes while they are
-         * waiting on conditions. They are then transferred to the queue to
-         * re-acquire. And because conditions can only be exclusive, we save a
-         * field by using special value to indicate shared mode.
+         * Link to next node waiting on condition, or the special value SHARED. Because
+         * condition queues are accessed only when holding in exclusive mode, we just
+         * need a simple linked queue to hold nodes while they are waiting on conditions.
+         * They are then transferred to the queue to re-acquire. And because conditions
+         * can only be exclusive, we save a field by using special value to indicate
+         * shared mode.
          */
         Node* nextWaiter;
 
@@ -167,6 +231,10 @@ namespace util {
 namespace concurrent {
 namespace locks {
 
+    /**
+     * The real implementation of AQS hidden here to allow code fixes without
+     * altering ABI.
+     */
     class SynchronizerState {
     public:
 
@@ -193,23 +261,25 @@ namespace locks {
         decaf_rwmutex_t rwLock;
 
         /**
-         * Head of the wait queue, lazily initialized.  Except for initialization,
-         * it is modified only via method setHead.  Note: If head exists, its
-         * waitStatus is guaranteed not to be CANCELLED.
+         * Head of the wait queue, lazily initialized.  Except for initialization, it is
+         * modified only via method setHead.  Note: If head exists, its waitStatus is
+         * guaranteed not to be CANCELLED.
          */
         AtomicReference<Node> head;
 
         /**
          * Tail of the wait queue, lazily initialized.  Modified only via method
-         * enq to add new wait node.
+         * enqueue() to add new wait node.
          */
         AtomicReference<Node> tail;
 
     public:
 
-        SynchronizerState(AbstractQueuedSynchronizer* parent) : parent(parent), state(0),
rwLock(), head(), tail() {
+        SynchronizerState(AbstractQueuedSynchronizer* parent) :
+            parent(parent), state(0), rwLock(), head(), tail() {
             PlatformThread::createRWMutex(&rwLock);
         }
+
         virtual ~SynchronizerState() {
 
             // Ensure that the destructor waits for other operations to complete.
@@ -237,7 +307,7 @@ namespace locks {
          * @param node
          *      The new node to add.
          */
-        Node* enq(Node* node) {
+        Node* enqueue(Node* node) {
             for (;;) {
                 Node* t = tail.get();
                 if (t == NULL) { // Must initialize
@@ -276,7 +346,7 @@ namespace locks {
                 }
             }
 
-            enq(node);
+            enqueue(node);
             return node;
         }
 
@@ -875,7 +945,7 @@ namespace locks {
              * attempt to set waitStatus fails, wake up to resync (in which
              * case the waitStatus can be transiently and harmlessly wrong).
              */
-            Node* p = enq(node);
+            Node* p = enqueue(node);
             int ws = p->waitStatus;
             if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node::SIGNAL)) {
                 LockSupport::unpark((Thread*)node->thread);
@@ -900,7 +970,7 @@ namespace locks {
          */
         bool transferAfterCancelledWait(Node* node) {
             if (compareAndSetWaitStatus(node, Node::CONDITION, 0)) {
-                enq(node);
+                enqueue(node);
                 return true;
             }
 
@@ -941,7 +1011,7 @@ namespace locks {
                 if (failed) {
                     node->waitStatus = Node::CANCELLED;
                     // Enqueue it even though canceled so that it gets deleted
-                    enq(node);
+                    enqueue(node);
                 }
 
                 throw ex;



Mime
View raw message