Skip to contentSkip to conversation

wfcqueue: implement concurrency-efficient queue

PATCH New Mathieu Desnoyers 4 participants 20 messages Oct 2, 2012 – Oct 10, 2012 15 messages not in the archive Kbuild

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): 20121002141307.GA4057@Krystal

#1 lore raw

PATCH 1/3 wfcqueue: implement concurrency-efficient queue

This new API simplify the wfqueue implementation, and brings a 2.3x to 2.6x performance boost due to the ability to eliminate false-sharing between enqueue and dequeue.

This work is derived from the patch from Lai Jiangshan submitted as "urcu: new wfqueue implementation"
(http://lists.lttng.org/pipermail/lttng-dev/2012-August/018379.html)

Its changelog:

Quoted 31 lines

Some guys would be surprised by this fact:
There are already TWO implementations of wfqueue in urcu.

The first one is in urcu/static/wfqueue.h:
1) enqueue: exchange the tail and then update previous->next
2) dequeue: wait for first node's next pointer and them shift, a dummy node

	is introduced to avoid the queue->tail become NULL when shift.

The second one shares some code with the first one, and the left code are spreading in urcu-call-rcu-impl.h:
1) enqueue: share with the first one
2) no dequeue operation: and no shift, so it don't need dummy node, Although the dummy node is queued when initialization, but it is removed after the first dequeue_all operation in call_rcu_thread(). call_rcu_data_free() forgets to handle the dummy node if it is not removed.
3)dequeue_all: record the old head and tail, and queue->head become the special
tail node.(atomic record the tail and change the tail).

The second implementation's code are spreading, bad for review, and it is not tested by tests/test_urcu_wfq.

So we need a better implementation avoid the dummy node dancing and can service both generic wfqueue APIs and dequeue_all API for call rcu.

The new implementation:
1) enqueue: share with the first one/original implementation.
2) dequeue: shift when node count >= 2, cmpxchg when node count = 1. no dummy node, save memory.
3) dequeue_all: simply set queue->head.next to NULL, xchg the tail and return the old head.next.

Quoted 2 lines

More implementation details are in the code. tests/test_urcu_wfq will be update in future for testing new APIs.

The patch proposed by Lai brings a very interesting simplification to the single-node handling (which is kept here), and moves all queue handling code away from call_rcu implementation, back into the wfqueue code. This has the benefit to allow testing enhancements.

I modified it so the API does not expose implementation details to the user (e.g. ___cds_wfq_node_sync_next). I added a "splice" operation and a for loop iterator which should allow wfqueue users to use the list very efficiently both from LGPL/GPL code and from non-LGPL-compatible code.

I also changed the API so the queue head and tail are now two separate
structures: it allows the queue user to place these as they like, either on different cache lines (to eliminate false-sharing), or close one to another (on same cache-line) in case a queue is spliced onto the stack and not concurrently accessed.

Benchmarks performed on Intel(R) Core(TM) i7-3520M CPU @ 2.90GHz (dual-core, with hyperthreading)

Benchmark invoked:
for a in $(seq 1 10); do ./test_urcu_wfq 1 1 10 -a 0 -a 2; done

(using cpu number 0 and 2, which should correspond to two cores of my Intel 2-core/hyperthread processor)

Before patch:

testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     97274297 nr_dequeues     80745742 successful enqueues     97274297 successful dequeues     80745321 end_dequeues 16528976 nr_ops    178020039
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     92300568 nr_dequeues     75019529 successful enqueues     92300568 successful dequeues     74973237 end_dequeues 17327331 nr_ops    167320097
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     93516443 nr_dequeues     75846726 successful enqueues     93516443 successful dequeues     75826578 end_dequeues 17689865 nr_ops    169363169
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94160362 nr_dequeues     77967638 successful enqueues     94160362 successful dequeues     77967638 end_dequeues 16192724 nr_ops    172128000
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     97491956 nr_dequeues     81001191 successful enqueues     97491956 successful dequeues     81000247 end_dequeues 16491709 nr_ops    178493147
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94101298 nr_dequeues     75650510 successful enqueues     94101298 successful dequeues     75649318 end_dequeues 18451980 nr_ops    169751808
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94742803 nr_dequeues     75402105 successful enqueues     94742803 successful dequeues     75341859 end_dequeues 19400944 nr_ops    170144908
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     92198835 nr_dequeues     75037877 successful enqueues     92198835 successful dequeues     75027605 end_dequeues 17171230 nr_ops    167236712
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94159560 nr_dequeues     77895972 successful enqueues     94159560 successful dequeues     77858442 end_dequeues 16301118 nr_ops    172055532
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     96059399 nr_dequeues     80115442 successful enqueues     96059399 successful dequeues     80066843 end_dequeues 15992556 nr_ops    176174841

After patch:

testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    221229322 nr_dequeues    210645491 successful enqueues    221229322 successful dequeues    210645088 end_dequeues 10584234 nr_ops    431874813
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    219803943 nr_dequeues    210377337 successful enqueues    219803943 successful dequeues    210368680 end_dequeues 9435263 nr_ops    430181280
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    237006358 nr_dequeues    237035340 successful enqueues    237006358 successful dequeues    236997050 end_dequeues 9308 nr_ops    474041698
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    235822443 nr_dequeues    235815942 successful enqueues    235822443 successful dequeues    235814020 end_dequeues 8423 nr_ops    471638385
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    235825567 nr_dequeues    235811803 successful enqueues    235825567 successful dequeues    235810526 end_dequeues 15041 nr_ops    471637370
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    221974953 nr_dequeues    210938190 successful enqueues    221974953 successful dequeues    210938190 end_dequeues 11036763 nr_ops    432913143
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    237994492 nr_dequeues    237938119 successful enqueues    237994492 successful dequeues    237930648 end_dequeues 63844 nr_ops    475932611
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    220634365 nr_dequeues    210491382 successful enqueues    220634365 successful dequeues    210490995 end_dequeues 10143370 nr_ops    431125747
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    237388065 nr_dequeues    237401251 successful enqueues    237388065 successful dequeues    237380295 end_dequeues 7770 nr_ops    474789316
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    221201436 nr_dequeues    210831162 successful enqueues    221201436 successful dequeues    210831162 end_dequeues 10370274 nr_ops    432032598

Summary: Both enqueue and dequeue speed increase: around 2.3x speedup for enqueue, and around 2.6x for dequeue.

We can verify that:
successful enqueues - successful dequeues = end_dequeues

For all runs (ensures correctness: no lost node).

CC Lai Jiangshan <[email protected]>
CC Paul McKenney <[email protected]>

---

Makefile.am +2 -2
index 2396fcf..ffdca9a 100644
@@ -16,7 +16,7 @@ nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \
 		urcu/uatomic/generic.h urcu/arch/generic.h urcu/wfstack.h \
 		urcu/wfqueue.h urcu/rculfstack.h urcu/rculfqueue.h \
 		urcu/ref.h urcu/cds.h urcu/urcu_ref.h urcu/urcu-futex.h \
-		urcu/uatomic_arch.h urcu/rculfhash.h \
+		urcu/uatomic_arch.h urcu/rculfhash.h urcu/wfcqueue.h \
 		$(top_srcdir)/urcu/map/*.h \
 		$(top_srcdir)/urcu/static/*.h \
 		urcu/tls-compat.h
@@ -53,7 +53,7 @@ lib_LTLIBRARIES = liburcu-common.la \
 # liburcu-common contains wait-free queues (needed by call_rcu) as well
 # as futex fallbacks.
 #
-liburcu_common_la_SOURCES = wfqueue.c wfstack.c $(COMPAT)
+liburcu_common_la_SOURCES = wfqueue.c wfcqueue.c wfstack.c $(COMPAT)
 
 liburcu_la_SOURCES = urcu.c urcu-pointer.c $(COMPAT)
 liburcu_la_LIBADD = liburcu-common.la
urcu/static/wfcqueue.h new file +380 -0

380 lines not on this page · raw message

urcu/wfcqueue.h new file +263 -0

263 lines not on this page · raw message

wfcqueue.c new file +116 -0

116 lines not on this page · raw message

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#2 lore raw

PATCH 2/3 wfcqueue test

In reply to a message not in the archive

---

tests/Makefile.am +9 -0
index 7d5ea82..81718bb 100644
@@ -14,7 +14,9 @@ noinst_PROGRAMS = test_urcu test_urcu_dynamic_link test_urcu_timing \
         test_uatomic test_urcu_assign test_urcu_assign_dynamic_link \
         test_urcu_bp test_urcu_bp_dynamic_link test_cycles_per_loop \
 	test_urcu_lfq test_urcu_wfq test_urcu_lfs test_urcu_wfs \
+	test_urcu_wfcq \
 	test_urcu_wfq_dynlink test_urcu_wfs_dynlink \
+	test_urcu_wfcq_dynlink \
 	test_urcu_lfq_dynlink test_urcu_lfs_dynlink test_urcu_hash
 noinst_HEADERS = rcutorture.h
 
@@ -169,6 +171,13 @@ test_urcu_wfq_dynlink_SOURCES = test_urcu_wfq.c
 test_urcu_wfq_dynlink_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS)
 test_urcu_wfq_dynlink_LDADD = $(URCU_COMMON_LIB)
 
+test_urcu_wfcq_SOURCES = test_urcu_wfcq.c $(COMPAT)
+test_urcu_wfcq_LDADD = $(URCU_COMMON_LIB)
+
+test_urcu_wfcq_dynlink_SOURCES = test_urcu_wfcq.c
+test_urcu_wfcq_dynlink_CFLAGS = -DDYNAMIC_LINK_TEST $(AM_CFLAGS)
+test_urcu_wfcq_dynlink_LDADD = $(URCU_COMMON_LIB)
+
 test_urcu_lfs_SOURCES = test_urcu_lfs.c $(URCU)
 test_urcu_lfs_LDADD = $(URCU_CDS_LIB)
 
tests/test_urcu_wfcq.c new file +418 -0

418 lines not on this page · raw message

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#3 lore raw

PATCH 3/3 call_rcu: use wfcqueue, eliminate false-sharing

In reply to a message not in the archive

Eliminate false-sharing between call_rcu (enqueuer) and worker threads on the queue head and tail.

---

tests/Makefile.am +6 -6
index 81718bb..c92bbe6 100644
@@ -30,14 +30,14 @@ if COMPAT_FUTEX
 COMPAT+=$(top_srcdir)/compat_futex.c
 endif
 
-URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_MB uses urcu.c but -DRCU_MB must be defined
-URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_SIGNAL uses urcu.c but -DRCU_SIGNAL must be defined
-URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 
 URCU_COMMON_LIB=$(top_builddir)/liburcu-common.la
 URCU_LIB=$(top_builddir)/liburcu.la
urcu-call-rcu-impl.h +35 -41

146 lines not on this page · raw message

urcu-call-rcu.h +2 -2
index f7eac8d..1dad0e2 100644
@@ -32,7 +32,7 @@
 #include <stdlib.h>
 #include <pthread.h>
 
-#include <urcu/wfqueue.h>
+#include <urcu/wfcqueue.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -55,7 +55,7 @@ struct call_rcu_data;
  */
 
 struct rcu_head {
-	struct cds_wfq_node next;
+	struct cds_wfcq_node next;
 	void (*func)(struct rcu_head *head);
 };
 
Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#4 lore raw

Re: [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

In reply to a message not in the archive
Quoted 15 lines · Mathieu Desnoyers

Implement wait-free concurrent queues, with a new API different from wfqueue.h, which is already provided by Userspace RCU. The advantage of splitting the head and tail objects of the queue into different arguments is to allow these to sit on different cache-lines, thus eliminating false-sharing, leading to a 2.3x speed increase.

This API also introduces a "splice" operation, which moves all nodes from one queue into another, and postpones the synchronization to either dequeue or iteration on the list. The splice operation does not need to touch every single node of the queue it moves them from. Moreover, the splice operation only needs to ensure mutual exclusion with other dequeuers, iterations, and splice operations from the list it splices from, but acts as a simple enqueuer on the list it splices into (no mutual exclusion needed for that list).

Quoted 1 line

Feedback is welcome,

These look sane to me, though I must confess that the tail pointer referencing the node rather than the node's next pointer did throw me for a bit. ;-)

Thanx, Paul

A message that is not in the archive (sent off-list or not yet received): [email protected]

#6 lore raw

Re: [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

Quoted 16 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 15 lines · Mathieu Desnoyers

Implement wait-free concurrent queues, with a new API different from wfqueue.h, which is already provided by Userspace RCU. The advantage of splitting the head and tail objects of the queue into different arguments is to allow these to sit on different cache-lines, thus eliminating false-sharing, leading to a 2.3x speed increase.

This API also introduces a "splice" operation, which moves all nodes from one queue into another, and postpones the synchronization to either dequeue or iteration on the list. The splice operation does not need to touch every single node of the queue it moves them from. Moreover, the splice operation only needs to ensure mutual exclusion with other dequeuers, iterations, and splice operations from the list it splices from, but acts as a simple enqueuer on the list it splices into (no mutual exclusion needed for that list).

Quoted 5 lines
Quoted 1 line

Feedback is welcome,

These look sane to me, though I must confess that the tail pointer referencing the node rather than the node's next pointer did throw me for a bit. ;-)

Yes, this was originally introduced with Lai's original patch to wfqueue, which I think is a nice simplification: it's pretty much the same thing to use the last node address as tail rather than the address of its first member (its next pointer address (_not_ value)). It ends up being the same address in this case, but more interestingly, we don't have to use a struct cds_wfcq_node ** type: a simple struct cds_wfcq_node * suffice.

Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Lai, you are welcome to provide improvements to this code against the master branch. I will gladly consider any change you propose.

Thanks!

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20121003210436.GB25090@Krystal

#8 lore raw

Re: [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

Quoted 31 lines · Mathieu Desnoyers
Quoted 16 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 15 lines · Mathieu Desnoyers

Implement wait-free concurrent queues, with a new API different from wfqueue.h, which is already provided by Userspace RCU. The advantage of splitting the head and tail objects of the queue into different arguments is to allow these to sit on different cache-lines, thus eliminating false-sharing, leading to a 2.3x speed increase.

This API also introduces a "splice" operation, which moves all nodes from one queue into another, and postpones the synchronization to either dequeue or iteration on the list. The splice operation does not need to touch every single node of the queue it moves them from. Moreover, the splice operation only needs to ensure mutual exclusion with other dequeuers, iterations, and splice operations from the list it splices from, but acts as a simple enqueuer on the list it splices into (no mutual exclusion needed for that list).

Quoted 5 lines
Quoted 1 line

Feedback is welcome,

These look sane to me, though I must confess that the tail pointer referencing the node rather than the node's next pointer did throw me for a bit. ;-)

Yes, this was originally introduced with Lai's original patch to wfqueue, which I think is a nice simplification: it's pretty much the same thing to use the last node address as tail rather than the address of its first member (its next pointer address (_not_ value)). It ends up being the same address in this case, but more interestingly, we don't have to use a struct cds_wfcq_node ** type: a simple struct cds_wfcq_node * suffice.

Quoted 1 line

Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Good point -- just confirming:

Quoted 18 lines

Lai, you are welcome to provide improvements to this code against the master branch. I will gladly consider any change you propose.

Thanks!

Mathieu

Signature · 9 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

_______________________________________________
rp mailing list
[email protected]
http://svcs.cs.pdx.edu/mailman/listinfo/rp
#9 lore raw

Re: [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

In reply to a message not in the archive
Quoted 31 lines · Mathieu Desnoyers
Quoted 16 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 15 lines · Mathieu Desnoyers

Implement wait-free concurrent queues, with a new API different from wfqueue.h, which is already provided by Userspace RCU. The advantage of splitting the head and tail objects of the queue into different arguments is to allow these to sit on different cache-lines, thus eliminating false-sharing, leading to a 2.3x speed increase.

This API also introduces a "splice" operation, which moves all nodes from one queue into another, and postpones the synchronization to either dequeue or iteration on the list. The splice operation does not need to touch every single node of the queue it moves them from. Moreover, the splice operation only needs to ensure mutual exclusion with other dequeuers, iterations, and splice operations from the list it splices from, but acts as a simple enqueuer on the list it splices into (no mutual exclusion needed for that list).

Quoted 5 lines
Quoted 1 line

Feedback is welcome,

These look sane to me, though I must confess that the tail pointer referencing the node rather than the node's next pointer did throw me for a bit. ;-)

Yes, this was originally introduced with Lai's original patch to wfqueue, which I think is a nice simplification: it's pretty much the same thing to use the last node address as tail rather than the address of its first member (its next pointer address (_not_ value)). It ends up being the same address in this case, but more interestingly, we don't have to use a struct cds_wfcq_node ** type: a simple struct cds_wfcq_node * suffice.

Quoted 5 lines

Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Lai, you are welcome to provide improvements to this code against the master branch. I will gladly consider any change you propose.

I did not remember that there is any improvement idea not included. The patchset is OK for me.

I think you can reimplement wfqueue via wfcqueue without cacheline opt.

Thanks,
Lai

A message that is not in the archive (sent off-list or not yet received): [email protected]

#11 lore raw

Re: [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

Quoted 32 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 31 lines · Mathieu Desnoyers
Quoted 16 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 15 lines · Mathieu Desnoyers

Implement wait-free concurrent queues, with a new API different from wfqueue.h, which is already provided by Userspace RCU. The advantage of splitting the head and tail objects of the queue into different arguments is to allow these to sit on different cache-lines, thus eliminating false-sharing, leading to a 2.3x speed increase.

This API also introduces a "splice" operation, which moves all nodes from one queue into another, and postpones the synchronization to either dequeue or iteration on the list. The splice operation does not need to touch every single node of the queue it moves them from. Moreover, the splice operation only needs to ensure mutual exclusion with other dequeuers, iterations, and splice operations from the list it splices from, but acts as a simple enqueuer on the list it splices into (no mutual exclusion needed for that list).

Quoted 5 lines
Quoted 1 line

Feedback is welcome,

These look sane to me, though I must confess that the tail pointer referencing the node rather than the node's next pointer did throw me for a bit. ;-)

Yes, this was originally introduced with Lai's original patch to wfqueue, which I think is a nice simplification: it's pretty much the same thing to use the last node address as tail rather than the address of its first member (its next pointer address (_not_ value)). It ends up being the same address in this case, but more interestingly, we don't have to use a struct cds_wfcq_node ** type: a simple struct cds_wfcq_node * suffice.

Quoted 8 lines
Quoted 5 lines

Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Lai, you are welcome to provide improvements to this code against the master branch. I will gladly consider any change you propose.

I did not remember that there is any improvement idea not included. The patchset is OK for me.

Great! Would you be OK if I commit the following patch ? Let me know if you want me to put your signed-off-by on this (I can even put your email as From if you like):

wfcqueue: update credits in patch documentation

Give credits to those responsible for the design and implementation of commit 8ad4ce587f001ae026d5560ac509c2e48986130b, "wfcqueue: implement concurrency-efficient queue", which happened through rounds of email and patch exchanges.

---

urcu/static/wfcqueue.h +4 -2
index a989984..153143d 100644
@@ -41,8 +41,10 @@ extern "C" {
 /*
  * Concurrent queue with wait-free enqueue/blocking dequeue.
  *
- * Inspired from half-wait-free/half-blocking queue implementation done by
- * Paul E. McKenney.
+ * This queue has been designed and implemented collaboratively by
+ * Mathieu Desnoyers and Lai Jiangshan. Inspired from
+ * half-wait-free/half-blocking queue implementation done by Paul E.
+ * McKenney.
  *
  * Mutual exclusion of __cds_wfcq_* API
  *
urcu/wfcqueue.h +4 -2
index 5576cbf..940dc7d 100644
@@ -37,8 +37,10 @@ extern "C" {
 /*
  * Concurrent queue with wait-free enqueue/blocking dequeue.
  *
- * Inspired from half-wait-free/half-blocking queue implementation done by
- * Paul E. McKenney.
+ * This queue has been designed and implemented collaboratively by
+ * Mathieu Desnoyers and Lai Jiangshan. Inspired from
+ * half-wait-free/half-blocking queue implementation done by Paul E.
+ * McKenney.
  */
 
 struct cds_wfcq_node {
Quoted 1 line

I think you can reimplement wfqueue via wfcqueue without cacheline opt.

Hrm, semantically this can indeed be done, but I fear that we might not be strictly ABI-compatible with the old wfqueue. So I would be tempted to leave the old wfqueue implementation as-is, and maybe deprecate it at some point. Thoughts ?

Thanks!

Mathieu

Quoted 3 lines

Thanks,
Lai

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20121008150729.GB29352@Krystal

#13 lore raw

Re: [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

Quoted 92 lines · Mathieu Desnoyers
Quoted 32 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 31 lines · Mathieu Desnoyers
Quoted 16 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 15 lines · Mathieu Desnoyers

Implement wait-free concurrent queues, with a new API different from wfqueue.h, which is already provided by Userspace RCU. The advantage of splitting the head and tail objects of the queue into different arguments is to allow these to sit on different cache-lines, thus eliminating false-sharing, leading to a 2.3x speed increase.

This API also introduces a "splice" operation, which moves all nodes from one queue into another, and postpones the synchronization to either dequeue or iteration on the list. The splice operation does not need to touch every single node of the queue it moves them from. Moreover, the splice operation only needs to ensure mutual exclusion with other dequeuers, iterations, and splice operations from the list it splices from, but acts as a simple enqueuer on the list it splices into (no mutual exclusion needed for that list).

Quoted 5 lines
Quoted 1 line

Feedback is welcome,

These look sane to me, though I must confess that the tail pointer referencing the node rather than the node's next pointer did throw me for a bit. ;-)

Yes, this was originally introduced with Lai's original patch to wfqueue, which I think is a nice simplification: it's pretty much the same thing to use the last node address as tail rather than the address of its first member (its next pointer address (_not_ value)). It ends up being the same address in this case, but more interestingly, we don't have to use a struct cds_wfcq_node ** type: a simple struct cds_wfcq_node * suffice.

Quoted 8 lines
Quoted 5 lines

Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Lai, you are welcome to provide improvements to this code against the master branch. I will gladly consider any change you propose.

I did not remember that there is any improvement idea not included. The patchset is OK for me.

Great! Would you be OK if I commit the following patch ? Let me know if you want me to put your signed-off-by on this (I can even put your email as From if you like):

wfcqueue: update credits in patch documentation

Give credits to those responsible for the design and implementation of commit 8ad4ce587f001ae026d5560ac509c2e48986130b, "wfcqueue: implement concurrency-efficient queue", which happened through rounds of email and patch exchanges.

---

urcu/static/wfcqueue.h +4 -2
index a989984..153143d 100644
@@ -41,8 +41,10 @@ extern "C" {
 /*
  * Concurrent queue with wait-free enqueue/blocking dequeue.
  *
- * Inspired from half-wait-free/half-blocking queue implementation done by
- * Paul E. McKenney.
+ * This queue has been designed and implemented collaboratively by
+ * Mathieu Desnoyers and Lai Jiangshan. Inspired from
+ * half-wait-free/half-blocking queue implementation done by Paul E.
+ * McKenney.
  *
  * Mutual exclusion of __cds_wfcq_* API
  *
urcu/wfcqueue.h +4 -2
index 5576cbf..940dc7d 100644
@@ -37,8 +37,10 @@ extern "C" {
 /*
  * Concurrent queue with wait-free enqueue/blocking dequeue.
  *
- * Inspired from half-wait-free/half-blocking queue implementation done by
- * Paul E. McKenney.
+ * This queue has been designed and implemented collaboratively by
+ * Mathieu Desnoyers and Lai Jiangshan. Inspired from
+ * half-wait-free/half-blocking queue implementation done by Paul E.
+ * McKenney.
  */
 
 struct cds_wfcq_node {
Quoted 7 lines
Quoted 1 line

I think you can reimplement wfqueue via wfcqueue without cacheline opt.

Hrm, semantically this can indeed be done, but I fear that we might not be strictly ABI-compatible with the old wfqueue. So I would be tempted to leave the old wfqueue implementation as-is, and maybe deprecate it at some point. Thoughts ?

All APIs is not changed, they are forwarded to wfcqueue APIs in implementation, so ABI of APIs is compatible. The only thing is struct cds_wfq_queue:

struct cds_wfq_queue {
	struct cds_wfq_node *head, **tail;
	struct cds_wfq_node dummy;	/* Dummy node */
	pthread_mutex_t lock;
};

We can redefine it as:

#define cds_wfq_node cds_wfcq_node

struct cds_wfq_queue {
	union {
		struct cds_wfq_node *head; /* make bug-user who wrongly directly access to ->head happy */
		struct cds_wfcq_node *__pad; /* not used in new implement */
	};
	union {
		struct cds_wfq_node **tail;  /* make bug-user who wrongly directly access to ->tail happy */
		struct cds_wfcq_tail real_tail;
	};
	union {
		struct {
			struct cds_wfq_node dummy;	/* Dummy node */
			pthread_mutex_t lock;
		}
		struct cds_wfcq_head real_head;
	};
}

static inline void _cds_wfq_init(struct cds_wfq_queue *q)

{
	q->head = &q->dummy; /* make bug-user who wrongly directly access to ->head happy */
	_cds_wfcq_init(&q->real_head, &q->real_tail);
}

after this change, struct cds_wfq_queue is not changed.
Even bug-user wrongly directly access to struct cds_wfq_queue by old-view, the queue is compatible:

	head->dummy node->real node->real node....
	tail->real tail node(or dummy node)

the only different is that: dummy node is always the first node by old-view.

And if we deprecate struct cds_wfq_queue, I think we should provide a new default wfqueue to users.

Thanks,
Lai

A message that is not in the archive (sent off-list or not yet received): [email protected]

#15 lore raw

Re: [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

Quoted 48 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 47 lines · Mathieu Desnoyers
Quoted 32 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 31 lines · Mathieu Desnoyers
Quoted 16 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 15 lines · Mathieu Desnoyers

Implement wait-free concurrent queues, with a new API different from wfqueue.h, which is already provided by Userspace RCU. The advantage of splitting the head and tail objects of the queue into different arguments is to allow these to sit on different cache-lines, thus eliminating false-sharing, leading to a 2.3x speed increase.

This API also introduces a "splice" operation, which moves all nodes from one queue into another, and postpones the synchronization to either dequeue or iteration on the list. The splice operation does not need to touch every single node of the queue it moves them from. Moreover, the splice operation only needs to ensure mutual exclusion with other dequeuers, iterations, and splice operations from the list it splices from, but acts as a simple enqueuer on the list it splices into (no mutual exclusion needed for that list).

Quoted 5 lines
Quoted 1 line

Feedback is welcome,

These look sane to me, though I must confess that the tail pointer referencing the node rather than the node's next pointer did throw me for a bit. ;-)

Yes, this was originally introduced with Lai's original patch to wfqueue, which I think is a nice simplification: it's pretty much the same thing to use the last node address as tail rather than the address of its first member (its next pointer address (_not_ value)). It ends up being the same address in this case, but more interestingly, we don't have to use a struct cds_wfcq_node ** type: a simple struct cds_wfcq_node * suffice.

Quoted 8 lines
Quoted 5 lines

Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Lai, you are welcome to provide improvements to this code against the master branch. I will gladly consider any change you propose.

I did not remember that there is any improvement idea not included. The patchset is OK for me.

Great! Would you be OK if I commit the following patch ? Let me know if you want me to put your signed-off-by on this (I can even put your email as From if you like):

Quoted 8 lines
Quoted 8 lines

wfcqueue: update credits in patch documentation

Give credits to those responsible for the design and implementation of commit 8ad4ce587f001ae026d5560ac509c2e48986130b, "wfcqueue: implement concurrency-efficient queue", which happened through rounds of email and patch exchanges.

Hi Lai,

Are you OK with this credits patch ?

Quoted 86 lines
Quoted 37 lines

---

urcu/static/wfcqueue.h +4 -2
index a989984..153143d 100644
@@ -41,8 +41,10 @@ extern "C" {
 /*
  * Concurrent queue with wait-free enqueue/blocking dequeue.
  *
- * Inspired from half-wait-free/half-blocking queue implementation done by
- * Paul E. McKenney.
+ * This queue has been designed and implemented collaboratively by
+ * Mathieu Desnoyers and Lai Jiangshan. Inspired from
+ * half-wait-free/half-blocking queue implementation done by Paul E.
+ * McKenney.
  *
  * Mutual exclusion of __cds_wfcq_* API
  *
urcu/wfcqueue.h +4 -2
index 5576cbf..940dc7d 100644
@@ -37,8 +37,10 @@ extern "C" {
 /*
  * Concurrent queue with wait-free enqueue/blocking dequeue.
  *
- * Inspired from half-wait-free/half-blocking queue implementation done by
- * Paul E. McKenney.
+ * This queue has been designed and implemented collaboratively by
+ * Mathieu Desnoyers and Lai Jiangshan. Inspired from
+ * half-wait-free/half-blocking queue implementation done by Paul E.
+ * McKenney.
  */
 
 struct cds_wfcq_node {
Quoted 7 lines
Quoted 1 line

I think you can reimplement wfqueue via wfcqueue without cacheline opt.

Hrm, semantically this can indeed be done, but I fear that we might not be strictly ABI-compatible with the old wfqueue. So I would be tempted to leave the old wfqueue implementation as-is, and maybe deprecate it at some point. Thoughts ?

All APIs is not changed, they are forwarded to wfcqueue APIs in implementation, so ABI of APIs is compatible. The only thing is struct cds_wfq_queue:

struct cds_wfq_queue {
	struct cds_wfq_node *head, **tail;
	struct cds_wfq_node dummy;	/* Dummy node */
	pthread_mutex_t lock;
};

We can redefine it as:

#define cds_wfq_node cds_wfcq_node

struct cds_wfq_queue {
	union {
		struct cds_wfq_node *head; /* make bug-user who wrongly directly access to ->head happy */
		struct cds_wfcq_node *__pad; /* not used in new implement */
	};
	union {
		struct cds_wfq_node **tail;  /* make bug-user who wrongly directly access to ->tail happy */
		struct cds_wfcq_tail real_tail;
	};
	union {
		struct {
			struct cds_wfq_node dummy;	/* Dummy node */
			pthread_mutex_t lock;
		}
		struct cds_wfcq_head real_head;
	};
}

static inline void _cds_wfq_init(struct cds_wfq_queue *q)

{
	q->head = &q->dummy; /* make bug-user who wrongly directly access to ->head happy */
	_cds_wfcq_init(&q->real_head, &q->real_tail);
}

after this change, struct cds_wfq_queue is not changed.
Even bug-user wrongly directly access to struct cds_wfq_queue by old-view, the queue is compatible:

Quoted 8 lines
	head->dummy node->real node->real node....
	tail->real tail node(or dummy node)

the only different is that: dummy node is always the first node by old-view.

And if we deprecate struct cds_wfq_queue, I think we should provide a new default wfqueue to users.

I guess the objective is nice, but I'm wondering if your mapping of wfqueue onto wfcqueue covers scenarios where we have objects that uses both the old and new view statically linked into the same program ?

My ABI concern is not just about queue users directly accessing the fields of the queue, but also about binary-level compatibility of mixed old-new queues.

Thoughts ?

Thanks,

Mathieu

Quoted 3 lines

Thanks,
Lai

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20121002141638.GD4057@Krystal

#17 lore raw

Re: [URCU PATCH 3/3] call_rcu: use wfcqueue, eliminate false-sharing

Quoted 54 lines · Mathieu Desnoyers

Eliminate false-sharing between call_rcu (enqueuer) and worker threads on the queue head and tail.

---

tests/Makefile.am +6 -6
index 81718bb..c92bbe6 100644
@@ -30,14 +30,14 @@ if COMPAT_FUTEX
 COMPAT+=$(top_srcdir)/compat_futex.c
 endif
 
-URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_MB uses urcu.c but -DRCU_MB must be defined
-URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_SIGNAL uses urcu.c but -DRCU_SIGNAL must be defined
-URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 
 URCU_COMMON_LIB=$(top_builddir)/liburcu-common.la
 URCU_LIB=$(top_builddir)/liburcu.la
urcu-call-rcu-impl.h +2 -1
index 13b24ff..cf65992 100644
@@ -21,6 +21,7 @@
  */
 
 #define _GNU_SOURCE
+#define _LGPL_SOURCE
 #include <stdio.h>
 #include <pthread.h>
 #include <signal.h>
@@ -35,7 +36,7 @@
 #include <sched.h>
 
 #include "config.h"
-#include "urcu/wfqueue.h"
+#include "urcu/wfcqueue.h"
 #include "urcu-call-rcu.h"
 #include "urcu-pointer.h"
 #include "urcu/list.h"
@@ -46,7 +47,14 @@
 /* Data structure that identifies a call_rcu thread. */
 

urcu-call-rcu-impl.h line 57

Quoted 10 lines
urcu-call-rcu-impl.h +8 -1
 struct call_rcu_data {
-	struct cds_wfq_queue cbs;
+	/*
+	 * Align the tail on cache line size to eliminate false-sharing
+	 * with head.
+	 */
+	struct cds_wfcq_tail __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_tail;
+	/* Alignment on cache line size will add padding here */
+
+	struct cds_wfcq_head cbs_head;

wrong here. In this code, cbs_tail and cbs_head are in the same cache line.

---

struct call_rcu_data {
	struct cds_wfcq_tail cbs_tail;
	struct cds_wfcq_head __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_head;
	/* other fields, can move some fields up to use the room between tail and head */
};
# cat test.c
struct a {
	int __attribute__((aligned(64))) i;
	int j;
};
struct b {
	int i;
	int __attribute__((aligned(64))) j;
};

void main(void)

{
	printf("%d,%d\n", sizeof(struct a), sizeof(struct b));
}
# ./a.out
64,128
Quoted 147 lines
urcu-call-rcu-impl.h +25 -39
 	unsigned long flags;
 	int32_t futex;
 	unsigned long qlen; /* maintained for debugging. */
@@ -220,10 +228,7 @@ static void call_rcu_wake_up(struct call_rcu_data *crdp)
 static void *call_rcu_thread(void *arg)
 {
 	unsigned long cbcount;
-	struct cds_wfq_node *cbs;
-	struct cds_wfq_node **cbs_tail;
-	struct call_rcu_data *crdp = (struct call_rcu_data *)arg;
-	struct rcu_head *rhp;
+	struct call_rcu_data *crdp = (struct call_rcu_data *) arg;
 	int rt = !!(uatomic_read(&crdp->flags) & URCU_CALL_RCU_RT);
 	int ret;
 
@@ -243,35 +248,33 @@ static void *call_rcu_thread(void *arg)
 		cmm_smp_mb();
 	}
 	for (;;) {
-		if (&crdp->cbs.head != _CMM_LOAD_SHARED(crdp->cbs.tail)) {
-			while ((cbs = _CMM_LOAD_SHARED(crdp->cbs.head)) == NULL)
-				poll(NULL, 0, 1);
-			_CMM_STORE_SHARED(crdp->cbs.head, NULL);
-			cbs_tail = (struct cds_wfq_node **)
-				uatomic_xchg(&crdp->cbs.tail, &crdp->cbs.head);
+		struct cds_wfcq_head cbs_tmp_head;
+		struct cds_wfcq_tail cbs_tmp_tail;
+		struct cds_wfcq_node *cbs, *cbs_tmp_n;
+
+		cds_wfcq_init(&cbs_tmp_head, &cbs_tmp_tail);
+		__cds_wfcq_splice_blocking(&cbs_tmp_head, &cbs_tmp_tail,
+			&crdp->cbs_head, &crdp->cbs_tail);
+		if (!cds_wfcq_empty(&cbs_tmp_head, &cbs_tmp_tail)) {
 			synchronize_rcu();
 			cbcount = 0;
-			do {
-				while (cbs->next == NULL &&
-				       &cbs->next != cbs_tail)
-				       	poll(NULL, 0, 1);
-				if (cbs == &crdp->cbs.dummy) {
-					cbs = cbs->next;
-					continue;
-				}
-				rhp = (struct rcu_head *)cbs;
-				cbs = cbs->next;
+			__cds_wfcq_for_each_blocking_safe(&cbs_tmp_head,
+					&cbs_tmp_tail, cbs, cbs_tmp_n) {
+				struct rcu_head *rhp;
+
+				rhp = caa_container_of(cbs,
+					struct rcu_head, next);
 				rhp->func(rhp);
 				cbcount++;
-			} while (cbs != NULL);
+			}
 			uatomic_sub(&crdp->qlen, cbcount);
 		}
 		if (uatomic_read(&crdp->flags) & URCU_CALL_RCU_STOP)
 			break;
 		rcu_thread_offline();
 		if (!rt) {
-			if (&crdp->cbs.head
-			    == _CMM_LOAD_SHARED(crdp->cbs.tail)) {
+			if (cds_wfcq_empty(&crdp->cbs_head,
+					&crdp->cbs_tail)) {
 				call_rcu_wait(crdp);
 				poll(NULL, 0, 10);
 				uatomic_dec(&crdp->futex);
@@ -317,7 +320,7 @@ static void call_rcu_data_init(struct call_rcu_data **crdpp,
 	if (crdp == NULL)
 		urcu_die(errno);
 	memset(crdp, '\0', sizeof(*crdp));
-	cds_wfq_init(&crdp->cbs);
+	cds_wfcq_init(&crdp->cbs_head, &crdp->cbs_tail);
 	crdp->qlen = 0;
 	crdp->futex = 0;
 	crdp->flags = flags;
@@ -590,12 +593,12 @@ void call_rcu(struct rcu_head *head,
 {
 	struct call_rcu_data *crdp;
 
-	cds_wfq_node_init(&head->next);
+	cds_wfcq_node_init(&head->next);
 	head->func = func;
 	/* Holding rcu read-side lock across use of per-cpu crdp */
 	rcu_read_lock();
 	crdp = get_call_rcu_data();
-	cds_wfq_enqueue(&crdp->cbs, &head->next);
+	cds_wfcq_enqueue(&crdp->cbs_head, &crdp->cbs_tail, &head->next);
 	uatomic_inc(&crdp->qlen);
 	wake_call_rcu_thread(crdp);
 	rcu_read_unlock();
@@ -625,10 +628,6 @@ void call_rcu(struct rcu_head *head,
  */
 void call_rcu_data_free(struct call_rcu_data *crdp)
 {
-	struct cds_wfq_node *cbs;
-	struct cds_wfq_node **cbs_tail;
-	struct cds_wfq_node **cbs_endprev;
-
 	if (crdp == NULL || crdp == default_call_rcu_data) {
 		return;
 	}
@@ -638,17 +637,12 @@ void call_rcu_data_free(struct call_rcu_data *crdp)
 		while ((uatomic_read(&crdp->flags) & URCU_CALL_RCU_STOPPED) == 0)
 			poll(NULL, 0, 1);
 	}
-	if (&crdp->cbs.head != _CMM_LOAD_SHARED(crdp->cbs.tail)) {
-		while ((cbs = _CMM_LOAD_SHARED(crdp->cbs.head)) == NULL)
-			poll(NULL, 0, 1);
-		_CMM_STORE_SHARED(crdp->cbs.head, NULL);
-		cbs_tail = (struct cds_wfq_node **)
-			uatomic_xchg(&crdp->cbs.tail, &crdp->cbs.head);
+	if (!cds_wfcq_empty(&crdp->cbs_head, &crdp->cbs_tail)) {
 		/* Create default call rcu data if need be */
 		(void) get_default_call_rcu_data();
-		cbs_endprev = (struct cds_wfq_node **)
-			uatomic_xchg(&default_call_rcu_data, cbs_tail);
-		*cbs_endprev = cbs;
+		__cds_wfcq_splice_blocking(&default_call_rcu_data->cbs_head,
+			&default_call_rcu_data->cbs_tail,
+			&crdp->cbs_head, &crdp->cbs_tail);
 		uatomic_add(&default_call_rcu_data->qlen,
 			    uatomic_read(&crdp->qlen));
 		wake_call_rcu_thread(default_call_rcu_data);
urcu-call-rcu.h +2 -2
index f7eac8d..1dad0e2 100644
@@ -32,7 +32,7 @@
 #include <stdlib.h>
 #include <pthread.h>
 
-#include <urcu/wfqueue.h>
+#include <urcu/wfcqueue.h>
 
 #ifdef __cplusplus
 extern "C" {
@@ -55,7 +55,7 @@ struct call_rcu_data;
  */
 
 struct rcu_head {
-	struct cds_wfq_node next;
+	struct cds_wfcq_node next;
 	void (*func)(struct rcu_head *head);
 };
 

A message that is not in the archive (sent off-list or not yet received): [email protected]

#19 lore raw

Re: [URCU PATCH 3/3] call_rcu: use wfcqueue, eliminate false-sharing

Quoted 88 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 54 lines · Mathieu Desnoyers

Eliminate false-sharing between call_rcu (enqueuer) and worker threads on the queue head and tail.

---

tests/Makefile.am +6 -6
index 81718bb..c92bbe6 100644
@@ -30,14 +30,14 @@ if COMPAT_FUTEX
 COMPAT+=$(top_srcdir)/compat_futex.c
 endif
 
-URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_MB uses urcu.c but -DRCU_MB must be defined
-URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_SIGNAL uses urcu.c but -DRCU_SIGNAL must be defined
-URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 
 URCU_COMMON_LIB=$(top_builddir)/liburcu-common.la
 URCU_LIB=$(top_builddir)/liburcu.la
urcu-call-rcu-impl.h +2 -1
index 13b24ff..cf65992 100644
@@ -21,6 +21,7 @@
  */
 
 #define _GNU_SOURCE
+#define _LGPL_SOURCE
 #include <stdio.h>
 #include <pthread.h>
 #include <signal.h>
@@ -35,7 +36,7 @@
 #include <sched.h>
 
 #include "config.h"
-#include "urcu/wfqueue.h"
+#include "urcu/wfcqueue.h"
 #include "urcu-call-rcu.h"
 #include "urcu-pointer.h"
 #include "urcu/list.h"
@@ -46,7 +47,14 @@
 /* Data structure that identifies a call_rcu thread. */
 

urcu-call-rcu-impl.h line 57

Quoted 10 lines
urcu-call-rcu-impl.h +8 -1
 struct call_rcu_data {
-	struct cds_wfq_queue cbs;
+	/*
+	 * Align the tail on cache line size to eliminate false-sharing
+	 * with head.
+	 */
+	struct cds_wfcq_tail __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_tail;
+	/* Alignment on cache line size will add padding here */
+
+	struct cds_wfcq_head cbs_head;

wrong here. In this code, cbs_tail and cbs_head are in the same cache line.

---

struct call_rcu_data {
	struct cds_wfcq_tail cbs_tail;
	struct cds_wfcq_head __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_head;
	/* other fields, can move some fields up to use the room between tail and head */
};
# cat test.c
struct a {
	int __attribute__((aligned(64))) i;
	int j;
};
struct b {
	int i;
	int __attribute__((aligned(64))) j;
};
Quoted 8 lines

void main(void)

{
	printf("%d,%d\n", sizeof(struct a), sizeof(struct b));
}
# ./a.out
64,128

Good point! While we are there, I notice that the "qlen" count, kept for debugging, is causing false-sharing too. I wonder if we should split this counter in two counters: nr_enqueue and nr_dequeue, which would sit in two different cache lines ? It's mainly Paul who cares about this counter. Thoughts ?

Here is the fix to the problem you noticed above:

commit b9f893b69fbc31baea418794938f4eb74cc4923a

Author: Mathieu Desnoyers <[email protected]>
Date:   Mon Oct 8 10:44:38 2012 -0400
    Fix urcu-call-rcu-impl.h: false-sharing
    
    > >  struct call_rcu_data {
    > > -   struct cds_wfq_queue cbs;
    > > +   /*
    > > +    * Align the tail on cache line size to eliminate false-sharing
    > > +    * with head.
    > > +    */
    > > +   struct cds_wfcq_tail __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_tail;
    > > +   /* Alignment on cache line size will add padding here */
    > > +
    > > +   struct cds_wfcq_head cbs_head;
    >
    >
    > wrong here. In this code, cbs_tail and cbs_head are in the same cache line.
    
    Reported-by: Lai Jiangshan <[email protected]>
    Signed-off-by: Mathieu Desnoyers <[email protected]>

Thanks!

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20121008144916.GA29352@Krystal

#21 lore raw

Re: [URCU PATCH 3/3] call_rcu: use wfcqueue, eliminate false-sharing

Quoted 98 lines · Mathieu Desnoyers
Quoted 88 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 54 lines · Mathieu Desnoyers

Eliminate false-sharing between call_rcu (enqueuer) and worker threads on the queue head and tail.

---

tests/Makefile.am +6 -6
index 81718bb..c92bbe6 100644
@@ -30,14 +30,14 @@ if COMPAT_FUTEX
 COMPAT+=$(top_srcdir)/compat_futex.c
 endif
 
-URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_QSBR=$(top_srcdir)/urcu-qsbr.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_MB uses urcu.c but -DRCU_MB must be defined
-URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_MB=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 # URCU_SIGNAL uses urcu.c but -DRCU_SIGNAL must be defined
-URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
-URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfqueue.c $(COMPAT)
+URCU_SIGNAL=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_BP=$(top_srcdir)/urcu-bp.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
+URCU_DEFER=$(top_srcdir)/urcu.c $(top_srcdir)/urcu-pointer.c $(top_srcdir)/wfcqueue.c $(COMPAT)
 
 URCU_COMMON_LIB=$(top_builddir)/liburcu-common.la
 URCU_LIB=$(top_builddir)/liburcu.la
urcu-call-rcu-impl.h +2 -1
index 13b24ff..cf65992 100644
@@ -21,6 +21,7 @@
  */
 
 #define _GNU_SOURCE
+#define _LGPL_SOURCE
 #include <stdio.h>
 #include <pthread.h>
 #include <signal.h>
@@ -35,7 +36,7 @@
 #include <sched.h>
 
 #include "config.h"
-#include "urcu/wfqueue.h"
+#include "urcu/wfcqueue.h"
 #include "urcu-call-rcu.h"
 #include "urcu-pointer.h"
 #include "urcu/list.h"
@@ -46,7 +47,14 @@
 /* Data structure that identifies a call_rcu thread. */
 

urcu-call-rcu-impl.h line 57

Quoted 10 lines
urcu-call-rcu-impl.h +8 -1
 struct call_rcu_data {
-	struct cds_wfq_queue cbs;
+	/*
+	 * Align the tail on cache line size to eliminate false-sharing
+	 * with head.
+	 */
+	struct cds_wfcq_tail __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_tail;
+	/* Alignment on cache line size will add padding here */
+
+	struct cds_wfcq_head cbs_head;

wrong here. In this code, cbs_tail and cbs_head are in the same cache line.

---

struct call_rcu_data {
	struct cds_wfcq_tail cbs_tail;
	struct cds_wfcq_head __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_head;
	/* other fields, can move some fields up to use the room between tail and head */
};
# cat test.c
struct a {
	int __attribute__((aligned(64))) i;
	int j;
};
struct b {
	int i;
	int __attribute__((aligned(64))) j;
};
Quoted 8 lines

void main(void)

{
	printf("%d,%d\n", sizeof(struct a), sizeof(struct b));
}
# ./a.out
64,128
Quoted 5 lines

Good point! While we are there, I notice that the "qlen" count, kept for debugging, is causing false-sharing too. I wonder if we should split this counter in two counters: nr_enqueue and nr_dequeue, which would sit in two different cache lines ? It's mainly Paul who cares about this counter. Thoughts ?

Works for me, as long as nr_enqueue and nr_dequeue are both unsigned long to avoid issues with overflow.

Thanx, Paul

Quoted 35 lines

Here is the fix to the problem you noticed above:

commit b9f893b69fbc31baea418794938f4eb74cc4923a

Author: Mathieu Desnoyers <[email protected]>
Date:   Mon Oct 8 10:44:38 2012 -0400
    Fix urcu-call-rcu-impl.h: false-sharing
    
    > >  struct call_rcu_data {
    > > -   struct cds_wfq_queue cbs;
    > > +   /*
    > > +    * Align the tail on cache line size to eliminate false-sharing
    > > +    * with head.
    > > +    */
    > > +   struct cds_wfcq_tail __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_tail;
    > > +   /* Alignment on cache line size will add padding here */
    > > +
    > > +   struct cds_wfcq_head cbs_head;
    >
    >
    > wrong here. In this code, cbs_tail and cbs_head are in the same cache line.
    
    Reported-by: Lai Jiangshan <[email protected]>
    Signed-off-by: Mathieu Desnoyers <[email protected]>

Thanks!

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): [email protected]

#23 lore raw

Re: [URCU PATCH 3/3] call_rcu: use wfcqueue, eliminate false-sharing

Quoted 1 line · * Paul E. McKenney ([email protected]) wrote:

On Mon, Oct 08, 2012 at 10:49:16AM -0400, Mathieu Desnoyers wrote:

[...]

Quoted 10 lines
Quoted 6 lines

Good point! While we are there, I notice that the "qlen" count, kept for debugging, is causing false-sharing too. I wonder if we should split this counter in two counters: nr_enqueue and nr_dequeue, which would sit in two different cache lines ? It's mainly Paul who cares about this counter. Thoughts ?

Works for me, as long as nr_enqueue and nr_dequeue are both unsigned long to avoid issues with overflow.

How about the following ? The 0.7% performance increase (which is this small probably due to call rcu batching) makes me wonder if it's really worth all the trouble through. If not, then we might want to consider removing the head alignment altogether. Carefully placing head/tail into different cache lines is really worth it if we have frequent dequeue, but in this case we batch through "splice" operations on large queues. Thoughts ?

Fix wfcqueue: false-sharing of qlen, flags, futex fields

The "qlen" count, kept for debugging, is causing false-sharing. Split this counter into two: nr_enqueue and nr_dequeue, which sit in two different cache lines.

The flags field is read-only by enqueue, and read-mostly by dequeue. We can eliminate all false-sharing between enqueue and dequeue by having one copy of the flag for enqueue and one for dequeue. The STOP and STOPPED flags are only used for dequeue (at "free" time), and the RT flag is set at init time, and used by both enqueue and dequeue.

The "futex" field is very often read by enqueue, and less often read and modified by dequeue (only when dequeue has emptied the queue). Move it to the enqueuer cache-line too.

With these modifications, the test "test_urcu_hash 0 1 10" (one updater for hash table, which uses call_rcu heavily for reclaim) gains 0.7%. The small performance improvement in this case can be associated to the fact that call_rcu dequeuer batches dequeuing of rcu head elements.

---

urcu-call-rcu-impl.h +26 -20
index dca98e4..3f46be6 100644
@@ -49,17 +49,18 @@
 struct call_rcu_data {
 	/*
 	 * Align the tail on cache line size to eliminate false-sharing
-	 * with head. Small note, however: the "qlen" field, kept for
-	 * debugging, will cause false-sharing between enqueue and
-	 * dequeue.
+	 * with head.
 	 */
 	struct cds_wfcq_tail cbs_tail;
+	unsigned long nr_enqueue;	/* maintained for debugging. */
+	unsigned long flags_enqueue;
+	int32_t futex;
+
 	/* Alignment on cache line size will add padding here */
 
 	struct cds_wfcq_head __attribute__((aligned(CAA_CACHE_LINE_SIZE))) cbs_head;
-	unsigned long flags;
-	int32_t futex;
-	unsigned long qlen; /* maintained for debugging. */
+	unsigned long nr_dequeue;	/* maintained for debugging. */
+	unsigned long flags_dequeue;
 	pthread_t tid;
 	int cpu_affinity;
 	struct cds_list_head list;
@@ -231,7 +232,7 @@ static void *call_rcu_thread(void *arg)
 {
 	unsigned long cbcount;
 	struct call_rcu_data *crdp = (struct call_rcu_data *) arg;
-	int rt = !!(uatomic_read(&crdp->flags) & URCU_CALL_RCU_RT);
+	int rt = !!(uatomic_read(&crdp->flags_dequeue) & URCU_CALL_RCU_RT);
 	int ret;
 
 	ret = set_thread_cpu_affinity(crdp);
@@ -269,9 +270,9 @@ static void *call_rcu_thread(void *arg)
 				rhp->func(rhp);
 				cbcount++;
 			}
-			uatomic_sub(&crdp->qlen, cbcount);
+			uatomic_add(&crdp->nr_dequeue, cbcount);
 		}
-		if (uatomic_read(&crdp->flags) & URCU_CALL_RCU_STOP)
+		if (uatomic_read(&crdp->flags_dequeue) & URCU_CALL_RCU_STOP)
 			break;
 		rcu_thread_offline();
 		if (!rt) {
@@ -300,7 +301,7 @@ static void *call_rcu_thread(void *arg)
 		cmm_smp_mb();
 		uatomic_set(&crdp->futex, 0);
 	}
-	uatomic_or(&crdp->flags, URCU_CALL_RCU_STOPPED);
+	uatomic_or(&crdp->flags_dequeue, URCU_CALL_RCU_STOPPED);
 	rcu_unregister_thread();
 	return NULL;
 }
@@ -323,9 +324,12 @@ static void call_rcu_data_init(struct call_rcu_data **crdpp,
 		urcu_die(errno);
 	memset(crdp, '\0', sizeof(*crdp));
 	cds_wfcq_init(&crdp->cbs_head, &crdp->cbs_tail);
-	crdp->qlen = 0;
+	crdp->nr_enqueue = 0;
+	crdp->flags_enqueue = flags;
 	crdp->futex = 0;
-	crdp->flags = flags;
+
+	crdp->nr_dequeue = 0;
+	crdp->flags_dequeue = flags;
 	cds_list_add(&crdp->list, &call_rcu_data_list);
 	crdp->cpu_affinity = cpu_affinity;
 	cmm_smp_mb();  /* Structure initialized before pointer is planted. */
@@ -571,7 +575,7 @@ int create_all_cpu_call_rcu_data(unsigned long flags)
  */
 static void wake_call_rcu_thread(struct call_rcu_data *crdp)
 {
-	if (!(_CMM_LOAD_SHARED(crdp->flags) & URCU_CALL_RCU_RT))
+	if (!(_CMM_LOAD_SHARED(crdp->flags_enqueue) & URCU_CALL_RCU_RT))
 		call_rcu_wake_up(crdp);
 }
 
@@ -601,7 +605,7 @@ void call_rcu(struct rcu_head *head,
 	rcu_read_lock();
 	crdp = get_call_rcu_data();
 	cds_wfcq_enqueue(&crdp->cbs_head, &crdp->cbs_tail, &head->next);
-	uatomic_inc(&crdp->qlen);
+	uatomic_inc(&crdp->nr_enqueue);
 	wake_call_rcu_thread(crdp);
 	rcu_read_unlock();
 }
@@ -633,10 +637,10 @@ void call_rcu_data_free(struct call_rcu_data *crdp)
 	if (crdp == NULL || crdp == default_call_rcu_data) {
 		return;
 	}
-	if ((uatomic_read(&crdp->flags) & URCU_CALL_RCU_STOPPED) == 0) {
-		uatomic_or(&crdp->flags, URCU_CALL_RCU_STOP);
+	if ((uatomic_read(&crdp->flags_dequeue) & URCU_CALL_RCU_STOPPED) == 0) {
+		uatomic_or(&crdp->flags_dequeue, URCU_CALL_RCU_STOP);
 		wake_call_rcu_thread(crdp);
-		while ((uatomic_read(&crdp->flags) & URCU_CALL_RCU_STOPPED) == 0)
+		while ((uatomic_read(&crdp->flags_dequeue) & URCU_CALL_RCU_STOPPED) == 0)
 			poll(NULL, 0, 1);
 	}
 	if (!cds_wfcq_empty(&crdp->cbs_head, &crdp->cbs_tail)) {
@@ -645,8 +649,10 @@ void call_rcu_data_free(struct call_rcu_data *crdp)
 		__cds_wfcq_splice_blocking(&default_call_rcu_data->cbs_head,
 			&default_call_rcu_data->cbs_tail,
 			&crdp->cbs_head, &crdp->cbs_tail);
-		uatomic_add(&default_call_rcu_data->qlen,
-			    uatomic_read(&crdp->qlen));
+		uatomic_add(&default_call_rcu_data->nr_enqueue,
+			    uatomic_read(&crdp->nr_enqueue));
+		uatomic_add(&default_call_rcu_data->nr_dequeue,
+			    uatomic_read(&crdp->nr_dequeue));
 		wake_call_rcu_thread(default_call_rcu_data);
 	}
 
@@ -750,7 +756,7 @@ void call_rcu_after_fork_child(void)
 	cds_list_for_each_entry_safe(crdp, next, &call_rcu_data_list, list) {
 		if (crdp == default_call_rcu_data)
 			continue;
-		uatomic_set(&crdp->flags, URCU_CALL_RCU_STOPPED);
+		uatomic_set(&crdp->flags_dequeue, URCU_CALL_RCU_STOPPED);
 		call_rcu_data_free(crdp);
 	}
 }
Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20121002141444.GB4057@Krystal

#25 lore raw

Il 02/10/2012 16:14, Mathieu Desnoyers ha scritto:

Quoted 11 lines

+/*
+ * 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

Quoted 8 lines

+ * 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

A message that is not in the archive (sent off-list or not yet received): [email protected]

#27 lore raw
Quoted 21 lines · * Paolo Bonzini ([email protected]) wrote:

Il 02/10/2012 16:14, Mathieu Desnoyers ha scritto:

Quoted 11 lines

+/*
+ * 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

Quoted 8 lines

+ * 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.
+ */

Quoted 7 lines

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 <[email protected]>
Date:   Mon Oct 8 12:11:30 2012 -0400

wfcqueue documentation: hint at for_each iterators

urcu/static/wfcqueue.h +11 -2
index a989984..944ee88 100644
@@ -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,
urcu/wfcqueue.h +11 -2
index 5576cbf..501120b 100644
@@ -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,
Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): 20121008161544.GB30083@Krystal

#29 lore raw

Il 08/10/2012 18:15, Mathieu Desnoyers ha scritto:

Quoted 6 lines

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:

Quoted 7 lines

+ * 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.

Uh, I was confused by the _blocking suffix. But when used together with splice you know it is not blocking---only the splice will block.

Paolo

A message that is not in the archive (sent off-list or not yet received): [email protected]

#31 lore raw
Quoted 11 lines · * Paolo Bonzini ([email protected]) wrote:

Il 08/10/2012 18:15, Mathieu Desnoyers ha scritto:

Quoted 10 lines

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.

Quoted 6 lines
Quoted 3 lines

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.

Uh, I was confused by the _blocking suffix. But when used together with splice you know it is not blocking---only the splice will block.

Well, in this case, the "blocking" can be understood as busy-waiting (and actual blocking that invokes the OS happens if busy-waiting for long periods only).

for_each iteration can indeed busy-wait: ___cds_wfcq_first_blocking() and ___cds_wfcq_next_blocking() can both call ___cds_wfcq_node_sync_next(), which busy-waits if it encounters a NULL next pointer that is not located in the tail node.

Seen through the use-case of splice to local queue + for_each, here is what happens:

- splice moves the content of the queue into a "local" queue. However, it does _not_ issue a ___cds_wfcq_node_sync_next() on each node: no traversal is performed.

- then, within the for_each iteration, we perform the ___cds_wfcq_node_sync_next() synchronization as we iterate on the local queue.

This ensures that the synchronization performed for each node is only performed lazily, only when those nodes are actually traversed. This approach has the advantage of increasing the locality of reference, and also to diminish the odds that this synchronization actually needs to be executed uselessly by postponing it to the point where it is actually needed.

Does it make more sense ?

Thanks,

Mathieu

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
#32 lore raw
In reply to a message not in the archive
Quoted 572 lines · Mathieu Desnoyers

This new API simplify the wfqueue implementation, and brings a 2.3x to 2.6x performance boost due to the ability to eliminate false-sharing between enqueue and dequeue.

This work is derived from the patch from Lai Jiangshan submitted as "urcu: new wfqueue implementation"
(http://lists.lttng.org/pipermail/lttng-dev/2012-August/018379.html)

Its changelog:

Quoted 31 lines

Some guys would be surprised by this fact:
There are already TWO implementations of wfqueue in urcu.

The first one is in urcu/static/wfqueue.h:
1) enqueue: exchange the tail and then update previous->next
2) dequeue: wait for first node's next pointer and them shift, a dummy node

	is introduced to avoid the queue->tail become NULL when shift.

The second one shares some code with the first one, and the left code are spreading in urcu-call-rcu-impl.h:
1) enqueue: share with the first one
2) no dequeue operation: and no shift, so it don't need dummy node, Although the dummy node is queued when initialization, but it is removed after the first dequeue_all operation in call_rcu_thread(). call_rcu_data_free() forgets to handle the dummy node if it is not removed.
3)dequeue_all: record the old head and tail, and queue->head become the special
tail node.(atomic record the tail and change the tail).

The second implementation's code are spreading, bad for review, and it is not tested by tests/test_urcu_wfq.

So we need a better implementation avoid the dummy node dancing and can service both generic wfqueue APIs and dequeue_all API for call rcu.

The new implementation:
1) enqueue: share with the first one/original implementation.
2) dequeue: shift when node count >= 2, cmpxchg when node count = 1. no dummy node, save memory.
3) dequeue_all: simply set queue->head.next to NULL, xchg the tail and return the old head.next.

Quoted 2 lines

More implementation details are in the code. tests/test_urcu_wfq will be update in future for testing new APIs.

The patch proposed by Lai brings a very interesting simplification to the single-node handling (which is kept here), and moves all queue handling code away from call_rcu implementation, back into the wfqueue code. This has the benefit to allow testing enhancements.

I modified it so the API does not expose implementation details to the user (e.g. ___cds_wfq_node_sync_next). I added a "splice" operation and a for loop iterator which should allow wfqueue users to use the list very efficiently both from LGPL/GPL code and from non-LGPL-compatible code.

I also changed the API so the queue head and tail are now two separate
structures: it allows the queue user to place these as they like, either on different cache lines (to eliminate false-sharing), or close one to another (on same cache-line) in case a queue is spliced onto the stack and not concurrently accessed.

Benchmarks performed on Intel(R) Core(TM) i7-3520M CPU @ 2.90GHz (dual-core, with hyperthreading)

Benchmark invoked:
for a in $(seq 1 10); do ./test_urcu_wfq 1 1 10 -a 0 -a 2; done

(using cpu number 0 and 2, which should correspond to two cores of my Intel 2-core/hyperthread processor)

Before patch:

testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     97274297 nr_dequeues     80745742 successful enqueues     97274297 successful dequeues     80745321 end_dequeues 16528976 nr_ops    178020039
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     92300568 nr_dequeues     75019529 successful enqueues     92300568 successful dequeues     74973237 end_dequeues 17327331 nr_ops    167320097
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     93516443 nr_dequeues     75846726 successful enqueues     93516443 successful dequeues     75826578 end_dequeues 17689865 nr_ops    169363169
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94160362 nr_dequeues     77967638 successful enqueues     94160362 successful dequeues     77967638 end_dequeues 16192724 nr_ops    172128000
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     97491956 nr_dequeues     81001191 successful enqueues     97491956 successful dequeues     81000247 end_dequeues 16491709 nr_ops    178493147
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94101298 nr_dequeues     75650510 successful enqueues     94101298 successful dequeues     75649318 end_dequeues 18451980 nr_ops    169751808
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94742803 nr_dequeues     75402105 successful enqueues     94742803 successful dequeues     75341859 end_dequeues 19400944 nr_ops    170144908
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     92198835 nr_dequeues     75037877 successful enqueues     92198835 successful dequeues     75027605 end_dequeues 17171230 nr_ops    167236712
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     94159560 nr_dequeues     77895972 successful enqueues     94159560 successful dequeues     77858442 end_dequeues 16301118 nr_ops    172055532
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues     96059399 nr_dequeues     80115442 successful enqueues     96059399 successful dequeues     80066843 end_dequeues 15992556 nr_ops    176174841

After patch:

testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    221229322 nr_dequeues    210645491 successful enqueues    221229322 successful dequeues    210645088 end_dequeues 10584234 nr_ops    431874813
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    219803943 nr_dequeues    210377337 successful enqueues    219803943 successful dequeues    210368680 end_dequeues 9435263 nr_ops    430181280
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    237006358 nr_dequeues    237035340 successful enqueues    237006358 successful dequeues    236997050 end_dequeues 9308 nr_ops    474041698
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    235822443 nr_dequeues    235815942 successful enqueues    235822443 successful dequeues    235814020 end_dequeues 8423 nr_ops    471638385
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    235825567 nr_dequeues    235811803 successful enqueues    235825567 successful dequeues    235810526 end_dequeues 15041 nr_ops    471637370
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    221974953 nr_dequeues    210938190 successful enqueues    221974953 successful dequeues    210938190 end_dequeues 11036763 nr_ops    432913143
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    237994492 nr_dequeues    237938119 successful enqueues    237994492 successful dequeues    237930648 end_dequeues 63844 nr_ops    475932611
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    220634365 nr_dequeues    210491382 successful enqueues    220634365 successful dequeues    210490995 end_dequeues 10143370 nr_ops    431125747
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    237388065 nr_dequeues    237401251 successful enqueues    237388065 successful dequeues    237380295 end_dequeues 7770 nr_ops    474789316
testdur   10 nr_enqueuers   1 wdelay      0 nr_dequeuers   1 rdur      0 nr_enqueues    221201436 nr_dequeues    210831162 successful enqueues    221201436 successful dequeues    210831162 end_dequeues 10370274 nr_ops    432032598

Summary: Both enqueue and dequeue speed increase: around 2.3x speedup for enqueue, and around 2.6x for dequeue.

We can verify that:
successful enqueues - successful dequeues = end_dequeues

For all runs (ensures correctness: no lost node).

CC Lai Jiangshan <[email protected]>
CC Paul McKenney <[email protected]>

---

Makefile.am +2 -2
index 2396fcf..ffdca9a 100644
@@ -16,7 +16,7 @@ nobase_dist_include_HEADERS = urcu/compiler.h urcu/hlist.h urcu/list.h \
 		urcu/uatomic/generic.h urcu/arch/generic.h urcu/wfstack.h \
 		urcu/wfqueue.h urcu/rculfstack.h urcu/rculfqueue.h \
 		urcu/ref.h urcu/cds.h urcu/urcu_ref.h urcu/urcu-futex.h \
-		urcu/uatomic_arch.h urcu/rculfhash.h \
+		urcu/uatomic_arch.h urcu/rculfhash.h urcu/wfcqueue.h \
 		$(top_srcdir)/urcu/map/*.h \
 		$(top_srcdir)/urcu/static/*.h \
 		urcu/tls-compat.h
@@ -53,7 +53,7 @@ lib_LTLIBRARIES = liburcu-common.la \
 # liburcu-common contains wait-free queues (needed by call_rcu) as well
 # as futex fallbacks.
 #
-liburcu_common_la_SOURCES = wfqueue.c wfstack.c $(COMPAT)
+liburcu_common_la_SOURCES = wfqueue.c wfcqueue.c wfstack.c $(COMPAT)
 
 liburcu_la_SOURCES = urcu.c urcu-pointer.c $(COMPAT)
 liburcu_la_LIBADD = liburcu-common.la
urcu/static/wfcqueue.h new file +380 -0
new file mode 100644
index 0000000..a989984
@@ -0,0 +1,380 @@
+#ifndef _URCU_WFCQUEUE_STATIC_H
+#define _URCU_WFCQUEUE_STATIC_H
+
+/*
+ * wfcqueue-static.h
+ *
+ * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
+ *
+ * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See wfcqueue.h for linking
+ * dynamically with the userspace rcu library.
+ *
+ * Copyright 2010-2012 - Mathieu Desnoyers <[email protected]>
+ * Copyright 2011-2012 - Lai Jiangshan <[email protected]>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <pthread.h>
+#include <assert.h>
+#include <poll.h>
+#include <stdbool.h>
+#include <urcu/compiler.h>
+#include <urcu/uatomic.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/*
+ * 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.
+ */
+
+#define WFCQ_ADAPT_ATTEMPTS		10	/* Retry if being set */
+#define WFCQ_WAIT			10	/* Wait 10 ms if being set */
+
+/*
+ * cds_wfcq_node_init: initialize wait-free queue node.
+ */
+static inline void _cds_wfcq_node_init(struct cds_wfcq_node *node)
+{
+	node->next = NULL;
+}
+
+/*
+ * cds_wfcq_init: initialize wait-free queue.
+ */
+static inline void _cds_wfcq_init(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail)
+{
+	int ret;
+
+	/* Set queue head and tail */
+	_cds_wfcq_node_init(&head->node);
+	tail->p = &head->node;
+	ret = pthread_mutex_init(&head->lock, NULL);
+	assert(!ret);
+}
+
+/*
+ * cds_wfcq_empty: return whether wait-free queue is empty.
+ *
+ * No memory barrier is issued. No mutual exclusion is required.
+ */
+static inline bool _cds_wfcq_empty(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail)
+{
+	/*
+	 * Queue is empty if no node is pointed by head->node.next nor
+	 * tail->p. Even though the tail->p check is sufficient to find
+	 * out of the queue is empty, we first check head->node.next as a
+	 * common case to ensure that dequeuers do not frequently access
+	 * enqueuer's tail->p cache line.
+	 */
+	return CMM_LOAD_SHARED(head->node.next) == NULL
+		&& CMM_LOAD_SHARED(tail->p) == &head->node;
+}
+
+static inline void _cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail)
+{
+	int ret;
+
+	ret = pthread_mutex_lock(&head->lock);
+	assert(!ret);
+}
+
+static inline void _cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail)
+{
+	int ret;
+
+	ret = pthread_mutex_unlock(&head->lock);
+	assert(!ret);
+}
+
+static inline void ___cds_wfcq_append(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail,
+		struct cds_wfcq_node *new_head,
+		struct cds_wfcq_node *new_tail)
+{
+	struct cds_wfcq_node *old_tail;
+
+	/*
+	 * Implicit memory barrier before uatomic_xchg() orders earlier
+	 * stores to data structure containing node and setting
+	 * node->next to NULL before publication.
+	 */
+	old_tail = uatomic_xchg(&tail->p, new_tail);
+
+	/*
+	 * Implicit memory barrier after uatomic_xchg() orders store to
+	 * q->tail before store to old_tail->next.
+	 *
+	 * At this point, dequeuers see a NULL tail->p->next, which
+	 * indicates that the queue is being appended to. The following
+	 * store will append "node" to the queue from a dequeuer
+	 * perspective.
+	 */
+	CMM_STORE_SHARED(old_tail->next, new_head);
+}
+
+/*
+ * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
+ *
+ * Issues a full memory barrier before enqueue. No mutual exclusion is
+ * required.
+ */
+static inline void _cds_wfcq_enqueue(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail,
+		struct cds_wfcq_node *new_tail)
+{
+	___cds_wfcq_append(head, tail, new_tail, new_tail);
+}
+
+/*
+ * Waiting for enqueuer to complete enqueue and return the next node.
+ */
+static inline struct cds_wfcq_node *
+___cds_wfcq_node_sync_next(struct cds_wfcq_node *node)
+{
+	struct cds_wfcq_node *next;
+	int attempt = 0;
+
+	/*
+	 * Adaptative busy-looping waiting for enqueuer to complete enqueue.
+	 */
+	while ((next = CMM_LOAD_SHARED(node->next)) == NULL) {
+		if (++attempt >= WFCQ_ADAPT_ATTEMPTS) {
+			poll(NULL, 0, WFCQ_WAIT);	/* Wait for 10ms */
+			attempt = 0;
+		} else {
+			caa_cpu_relax();
+		}
+	}
+
+	return next;
+}
+
+/*
+ * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
+ *
+ * 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.
+ */
+static inline struct cds_wfcq_node *
+___cds_wfcq_first_blocking(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail)
+{
+	struct cds_wfcq_node *node;
+
+	if (_cds_wfcq_empty(head, tail))
+		return NULL;
+	node = ___cds_wfcq_node_sync_next(&head->node);
+	/* Load head->node.next before loading node's content */
+	cmm_smp_read_barrier_depends();
+	return node;
+}
+
+/*
+ * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
+ *
+ * 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.
+ */
+static inline struct cds_wfcq_node *
+___cds_wfcq_next_blocking(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail,
+		struct cds_wfcq_node *node)
+{
+	struct cds_wfcq_node *next;
+
+	/*
+	 * Even though the following tail->p check is sufficient to find
+	 * out if we reached the end of the queue, we first check
+	 * node->next as a common case to ensure that iteration on nodes
+	 * do not frequently access enqueuer's tail->p cache line.
+	 */
+	if ((next = CMM_LOAD_SHARED(node->next)) == NULL) {
+		/* Load node->next before tail->p */
+		cmm_smp_rmb();
+		if (CMM_LOAD_SHARED(tail->p) == node)
+			return NULL;
+		next = ___cds_wfcq_node_sync_next(node);
+	}
+	/* Load node->next before loading next's content */
+	cmm_smp_read_barrier_depends();
+	return next;
+}
+
+/*
+ * __cds_wfcq_dequeue_blocking: dequeue a node from the queue.
+ *
+ * No need to go on a waitqueue here, as there is no possible state in which the
+ * list could cause dequeue to busy-loop needlessly while waiting for another
+ * thread to be scheduled. The queue appears empty until tail->next is set by
+ * enqueue.
+ *
+ * Content written into the node before enqueue is guaranteed to be
+ * consistent, but no other memory ordering is ensured.
+ * It is valid to reuse and free a dequeued node immediately.
+ * Should be called with cds_wfcq_dequeue_lock() held.
+ */
+static inline struct cds_wfcq_node *
+___cds_wfcq_dequeue_blocking(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail)
+{
+	struct cds_wfcq_node *node, *next;
+
+	if (_cds_wfcq_empty(head, tail))
+		return NULL;
+
+	node = ___cds_wfcq_node_sync_next(&head->node);
+
+	if ((next = CMM_LOAD_SHARED(node->next)) == NULL) {
+		/*
+		 * @node is probably the only node in the queue.
+		 * Try to move the tail to &q->head.
+		 * q->head.next is set to NULL here, and stays
+		 * NULL if the cmpxchg succeeds. Should the
+		 * cmpxchg fail due to a concurrent enqueue, the
+		 * q->head.next will be set to the next node.
+		 * The implicit memory barrier before
+		 * uatomic_cmpxchg() orders load node->next
+		 * before loading q->tail.
+		 * The implicit memory barrier before uatomic_cmpxchg
+		 * orders load q->head.next before loading node's
+		 * content.
+		 */
+		_cds_wfcq_node_init(&head->node);
+		if (uatomic_cmpxchg(&tail->p, node, &head->node) == node)
+			return node;
+		next = ___cds_wfcq_node_sync_next(node);
+	}
+
+	/*
+	 * Move queue head forward.
+	 */
+	head->node.next = next;
+
+	/* Load q->head.next before loading node's content */
+	cmm_smp_read_barrier_depends();
+	return node;
+}
+
+/*
+ * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
+ *
+ * Dequeue all nodes from src_q.
+ * dest_q must be already initialized.
+ * Should be called with cds_wfcq_dequeue_lock() held on src_q.
+ */
+static inline void
+___cds_wfcq_splice_blocking(
+		struct cds_wfcq_head *dest_q_head,
+		struct cds_wfcq_tail *dest_q_tail,
+		struct cds_wfcq_head *src_q_head,
+		struct cds_wfcq_tail *src_q_tail)
+{
+	struct cds_wfcq_node *head, *tail;
+
+	if (_cds_wfcq_empty(src_q_head, src_q_tail))
+		return;
+
+	head = ___cds_wfcq_node_sync_next(&src_q_head->node);
+	_cds_wfcq_node_init(&src_q_head->node);
+
+	/*
+	 * Memory barrier implied before uatomic_xchg() orders store to
+	 * src_q->head before store to src_q->tail. This is required by
+	 * concurrent enqueue on src_q, which exchanges the tail before
+	 * updating the previous tail's next pointer.
+	 */
+	tail = uatomic_xchg(&src_q_tail->p, &src_q_head->node);
+
+	/*
+	 * Append the spliced content of src_q into dest_q. Does not
+	 * require mutual exclusion on dest_q (wait-free).
+	 */
+	___cds_wfcq_append(dest_q_head, dest_q_tail, head, tail);
+}
+
+/*
+ * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
+ *
+ * Content written into the node before enqueue is guaranteed to be
+ * consistent, but no other memory ordering is ensured.
+ * Mutual exlusion with (and only with) cds_wfcq_splice_blocking is
+ * ensured.
+ * It is valid to reuse and free a dequeued node immediately.
+ */
+static inline struct cds_wfcq_node *
+_cds_wfcq_dequeue_blocking(struct cds_wfcq_head *head,
+		struct cds_wfcq_tail *tail)
+{
+	struct cds_wfcq_node *retval;
+
+	_cds_wfcq_dequeue_lock(head, tail);
+	retval = ___cds_wfcq_dequeue_blocking(head, tail);
+	_cds_wfcq_dequeue_unlock(head, tail);
+	return retval;
+}
+
+/*
+ * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
+ *
+ * Dequeue all nodes from src_q.
+ * dest_q must be already initialized.
+ * Content written into the node before enqueue is guaranteed to be
+ * consistent, but no other memory ordering is ensured.
+ * Mutual exlusion with (and only with) cds_wfcq_dequeue_blocking is
+ * ensured.
+ */
+static inline void
+_cds_wfcq_splice_blocking(
+		struct cds_wfcq_head *dest_q_head,
+		struct cds_wfcq_tail *dest_q_tail,
+		struct cds_wfcq_head *src_q_head,
+		struct cds_wfcq_tail *src_q_tail)
+{
+	_cds_wfcq_dequeue_lock(src_q_head, src_q_tail);
+	___cds_wfcq_splice_blocking(dest_q_head, dest_q_tail,
+			src_q_head, src_q_tail);
+	_cds_wfcq_dequeue_unlock(src_q_head, src_q_tail);
+}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _URCU_WFCQUEUE_STATIC_H */
urcu/wfcqueue.h new file +50 -0
new file mode 100644
index 0000000..5576cbf
@@ -0,0 +1,263 @@
+#ifndef _URCU_WFCQUEUE_H
+#define _URCU_WFCQUEUE_H
+
+/*
+ * wfcqueue.h
+ *
+ * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
+ *
+ * Copyright 2010-2012 - Mathieu Desnoyers <[email protected]>
+ * Copyright 2011-2012 - Lai Jiangshan <[email protected]>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <pthread.h>
+#include <assert.h>
+#include <stdbool.h>
+#include <urcu/compiler.h>
+#include <urcu/arch.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/*
+ * Concurrent queue with wait-free enqueue/blocking dequeue.
+ *
+ * Inspired from half-wait-free/half-blocking queue implementation done by
+ * Paul E. McKenney.
+ */
+
+struct cds_wfcq_node {
+	struct cds_wfcq_node *next;
+};
+
+/*
+ * Do not put head and tail on the same cache-line if concurrent
+ * enqueue/dequeue are expected from many CPUs. This eliminates

urcu/wfcqueue.h line 60

Quoted 10 lines
urcu/wfcqueue.h new file +10 -0
+ * false-sharing between enqueue and dequeue.
+ */
+struct cds_wfcq_head {
+	struct cds_wfcq_node node;
+	pthread_mutex_t lock;
+};
+
+struct cds_wfcq_tail {
+	struct cds_wfcq_node *p;
+};

Why use "p" here?

I don't see the commits in the public git-tree. Or you forgot to update the tree and make "http" address happy.

Thanks,
Lai

A message that is not in the archive (sent off-list or not yet received): [email protected]

#34 lore raw
Quoted 1 line · * Lai Jiangshan ([email protected]) wrote:

On 10/02/2012 10:14 PM, Mathieu Desnoyers wrote:

[...]

Quoted 57 lines
Quoted 57 lines
urcu/wfcqueue.h new file +54 -0
@@ -0,0 +1,263 @@
+#ifndef _URCU_WFCQUEUE_H
+#define _URCU_WFCQUEUE_H
+
+/*
+ * wfcqueue.h
+ *
+ * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
+ *
+ * Copyright 2010-2012 - Mathieu Desnoyers <[email protected]>
+ * Copyright 2011-2012 - Lai Jiangshan <[email protected]>
+ *
+ * This library is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * This library is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this library; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include <pthread.h>
+#include <assert.h>
+#include <stdbool.h>
+#include <urcu/compiler.h>
+#include <urcu/arch.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/*
+ * Concurrent queue with wait-free enqueue/blocking dequeue.
+ *
+ * Inspired from half-wait-free/half-blocking queue implementation done by
+ * Paul E. McKenney.
+ */
+
+struct cds_wfcq_node {
+	struct cds_wfcq_node *next;
+};
+
+/*
+ * Do not put head and tail on the same cache-line if concurrent
+ * enqueue/dequeue are expected from many CPUs. This eliminates
+ * false-sharing between enqueue and dequeue.
+ */
+struct cds_wfcq_head {
+	struct cds_wfcq_node node;
Quoted 8 lines

urcu/wfcqueue.h line 60

Quoted 6 lines
urcu/wfcqueue.h new file +6 -0
+	pthread_mutex_t lock;
+};
+
+struct cds_wfcq_tail {
+	struct cds_wfcq_node *p;
+};

Why use "p" here?

For lack of imagination. ;) Do you have something better to propose ?

Quoted 3 lines

I don't see the commits in the public git-tree. Or you forgot to update the tree and make "http" address happy.

I have pushed those into the userspace RCU master branch a couple of days after posting them to the mailing lists. I just synchronized my urcu/wfcqueue volatile dev branch, but I expect to drop it soon, since it's now merged back into master.

Thanks!

Mathieu

Quoted 3 lines

Thanks,
Lai

Signature · 4 lines
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com