[lttng-dev] [URCU PATCH 1/3] wfcqueue: implement concurrency-efficient queue

[Mathieu Desnoyers]

* Paolo Bonzini (pbonzini at redhat.com) wrote:
> Il 02/10/2012 16:14, Mathieu Desnoyers ha scritto:
> > +/*
> > + * Concurrent queue with wait-free enqueue/blocking dequeue.
> > + *
> > + * Inspired from half-wait-free/half-blocking queue implementation done by
> > + * Paul E. McKenney.
> > + *
> > + * Mutual exclusion of __cds_wfcq_* API
> > + *
> > + * Unless otherwise stated, the caller must ensure mutual exclusion of
> > + * queue update operations "dequeue" and "splice" (for source queue).
> > + * Queue read operations "first" and "next" need to be protected against
> > + * concurrent "dequeue" and "splice" (for source queue) by the caller.
> > + * "enqueue", "splice" (for destination queue), and "empty" are the only
> > + * operations that can be used without any mutual exclusion.
> > + * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
> > + *
> > + * For convenience, cds_wfcq_dequeue_blocking() and
> > + * cds_wfcq_splice_blocking() hold the dequeue lock.
> > + */
> 
> Hi,
> 
> can you add a for-like macro for iteration?  Iteration does not require
> holding the lock and assumes that you are the sole user of the data
> structure, which is useful together with splice.
> 
> Paolo

Hi Paolo,

We actually already have those, they are just not described in this
comment. I will fix this right away. By the way, you will notice the
wording:

+ * Queue read operations "first" and "next", which are used by
+ * "for_each" iterations, need to be protected against concurrent
+ * "dequeue" and "splice" (for source queue) by the caller.

Being the only one iterating on a queue with local head/tail after a
splice operation is one way to provide mutual exclusion. Holding a lock
is not the only way to achieve mutual exclusion.


commit f94061a3df4c9eab9ac869a19e4228de54771fcb
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date:   Mon Oct 8 12:11:30 2012 -0400

    wfcqueue documentation: hint at for_each iterators
    
    Reported-by: Paolo Bonzini <pbonzini at redhat.com>
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

diff --git a/urcu/static/wfcqueue.h b/urcu/static/wfcqueue.h
index a989984..944ee88 100644
--- a/urcu/static/wfcqueue.h
+++ b/urcu/static/wfcqueue.h
@@ -48,8 +48,9 @@ extern "C" {
  *
  * Unless otherwise stated, the caller must ensure mutual exclusion of
  * queue update operations "dequeue" and "splice" (for source queue).
- * Queue read operations "first" and "next" need to be protected against
- * concurrent "dequeue" and "splice" (for source queue) by the caller.
+ * Queue read operations "first" and "next", which are used by
+ * "for_each" iterations, need to be protected against concurrent
+ * "dequeue" and "splice" (for source queue) by the caller.
  * "enqueue", "splice" (for destination queue), and "empty" are the only
  * operations that can be used without any mutual exclusion.
  * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
@@ -190,6 +191,10 @@ ___cds_wfcq_node_sync_next(struct cds_wfcq_node *node)
  * Content written into the node before enqueue is guaranteed to be
  * consistent, but no other memory ordering is ensured.
  * Should be called with cds_wfcq_dequeue_lock() held.
+ *
+ * Used by for-like iteration macros in urcu/wfqueue.h:
+ * __cds_wfcq_for_each_blocking()
+ * __cds_wfcq_for_each_blocking_safe()
  */
 static inline struct cds_wfcq_node *
 ___cds_wfcq_first_blocking(struct cds_wfcq_head *head,
@@ -211,6 +216,10 @@ ___cds_wfcq_first_blocking(struct cds_wfcq_head *head,
  * Content written into the node before enqueue is guaranteed to be
  * consistent, but no other memory ordering is ensured.
  * Should be called with cds_wfcq_dequeue_lock() held.
+ *
+ * Used by for-like iteration macros in urcu/wfqueue.h:
+ * __cds_wfcq_for_each_blocking()
+ * __cds_wfcq_for_each_blocking_safe()
  */
 static inline struct cds_wfcq_node *
 ___cds_wfcq_next_blocking(struct cds_wfcq_head *head,
diff --git a/urcu/wfcqueue.h b/urcu/wfcqueue.h
index 5576cbf..501120b 100644
--- a/urcu/wfcqueue.h
+++ b/urcu/wfcqueue.h
@@ -91,8 +91,9 @@ struct cds_wfcq_tail {
  *
  * Unless otherwise stated, the caller must ensure mutual exclusion of
  * queue update operations "dequeue" and "splice" (for source queue).
- * Queue read operations "first" and "next" need to be protected against
- * concurrent "dequeue" and "splice" (for source queue) by the caller.
+ * Queue read operations "first" and "next", which are used by
+ * "for_each" iterations, need to be protected against concurrent
+ * "dequeue" and "splice" (for source queue) by the caller.
  * "enqueue", "splice" (for destination queue), and "empty" are the only
  * operations that can be used without any mutual exclusion.
  * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
@@ -202,6 +203,10 @@ extern void __cds_wfcq_splice_blocking(
  * Content written into the node before enqueue is guaranteed to be
  * consistent, but no other memory ordering is ensured.
  * Should be called with cds_wfcq_dequeue_lock() held.
+ *
+ * Used by for-like iteration macros:
+ * __cds_wfcq_for_each_blocking()
+ * __cds_wfcq_for_each_blocking_safe()
  */
 extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
 		struct cds_wfcq_head *head,
@@ -213,6 +218,10 @@ extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
  * Content written into the node before enqueue is guaranteed to be
  * consistent, but no other memory ordering is ensured.
  * Should be called with cds_wfcq_dequeue_lock() held.
+ *
+ * Used by for-like iteration macros:
+ * __cds_wfcq_for_each_blocking()
+ * __cds_wfcq_for_each_blocking_safe()
  */
 extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
 		struct cds_wfcq_head *head,


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com