wfqueue: ABI v1, simplify implementation, 2.3x to 2.6x performance boost
A message that is not in the archive (sent off-list or not yet received): 20120815213107.GB17224@Krystal
And here is the new ABI I propose.
Thanks,
Mathieu
Quoted 807 lines · * Mathieu Desnoyers ([email protected]) wrote:
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 updateprevious->next
2) dequeue: wait for first node's next pointer and them shift, a dummy nodeis 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 firstdequeue_alloperation incall_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, andqueue->headbecome 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_allAPI 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 setqueue->head.nextto 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_rcuimplementation, 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.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 176174841After 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 432032598Summary: 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_dequeuesFor all runs (ensures correctness: no lost node).
* Introduce wfqueue ABI v1 (false-sharing fix)
wfqueue v0 suffers from false-sharing between head and tail. By cache-aligning head and tail, we get a significant speedup on benchmarks. But in order to do that, we need to break the ABI to enlarge struct
cds_wfq_queue.Provide a backward compatibility ABI for the old wfqueue by defining the original symbols to the old implementation (which uses dummy node). Programs compiled against old headers, which are not
LGPL_SOURCE, will still use the old implementation.Any code compiled against the new header will directly use the new ABI.
This does not require any change in the way users call the API: the new ABI symbols are simply defined with _1 suffix, and wrapped by preprocessor macros.
Known limitation: users should *not* link together objects using the v0 and v1 APIs of wfqueue and exchange struct
cds_wfq_queuestructures between the two. The only way to run into this corner-case would be to combine objects compiled with different versions of theurcu/wfqueue.hheader.CC Lai Jiangshan <[email protected]>CC Paul McKenney <[email protected]>Signed-off-by Mathieu Desnoyers <[email protected]>---
Makefile.am +1
-1@@ -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 wfqueue0.c wfstack.c $(COMPAT) liburcu_la_SOURCES = urcu.c urcu-pointer.c $(COMPAT) liburcu_la_LIBADD = liburcu-common.laurcu-call-rcu-impl.h +24
-36@@ -21,6 +21,7 @@*/ #define _GNU_SOURCE +#define _LGPL_SOURCE#include <stdio.h> #include <pthread.h> #include <signal.h> @@ -220,10 +221,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 +241,30 @@ 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_wfq_queue cbs_tmp; +struct cds_wfq_node *cbs, *tmp_cbs; + +cds_wfq_init (&cbs_tmp); +__cds_wfq_splice_blocking (&cbs_tmp, &crdp->cbs); +if (!cds_wfq_empty (&cbs_tmp)) {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_wfq_for_each_blocking_safe (&cbs_tmp, + cbs, tmp_cbs) { +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_wfq_empty (&crdp->cbs)) {call_rcu_wait (crdp);poll (NULL ,0 ,10 );uatomic_dec (&crdp->futex);@@ -625,32 +618,27 @@ 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 ; } +if ((uatomic_read (&crdp->flags) &URCU_CALL_RCU_STOPPED ) ==0 ) {uatomic_or (&crdp->flags,URCU_CALL_RCU_STOP );wake_call_rcu_thread (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_wfq_empty (&crdp->cbs)) {/* 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_wfq_splice_blocking (&default_call_rcu_data->cbs, + &crdp->cbs); +uatomic_add (&default_call_rcu_data->qlen,uatomic_read (&crdp->qlen)); +wake_call_rcu_thread (default_call_rcu_data); }urcu/static/wfqueue.h +185
-38@@ -9,7 +9,8 @@* TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See wfqueue.h for linking * dynamically with the userspace rcu library. * -* Copyright 2010 - Mathieu Desnoyers <[email protected]> +* 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 @@ -29,6 +30,7 @@#include <pthread.h> #include <assert.h> #include <poll.h> +#include <stdbool.h> #include <urcu/compiler.h> #include <urcu/uatomic.h> @@ -38,11 +40,16 @@ extern "C" {/* * Queue with wait-free enqueue/blocking dequeue. -* This implementation adds a dummy head node when the queue is empty to ensure -* we can always update the queue locklessly. * * Inspired from half-wait-free/half-blocking queue implementation done by * Paul E. McKenney. +* +* Caller must ensure mutual exclusion of queue update operations +* "dequeue" and "splice" 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" +* (destination queue), and "empty" are the only operations that can be +* used without any mutual exclusion. */ #define WFQ_ADAPT_ATTEMPTS 10/* Retry if being set */ @@ -57,31 +64,55 @@ static inline void _cds_wfq_init(struct cds_wfq_queue *q) {int ret; -_cds_wfq_node_init (&q->dummy);/* Set queue head and tail */ - q->head = &q->dummy; - q->tail = &q->dummy.next; - ret =pthread_mutex_init (&q->lock,NULL ); +_cds_wfq_node_init (&q->dequeue.head); + q->enqueue.tail = &q->dequeue.head; + ret =pthread_mutex_init (&q->dequeue.lock,NULL );assert (!ret); } -static inline void _cds_wfq_enqueue (struct cds_wfq_queue *q, -struct cds_wfq_node *node) +static inline bool _cds_wfq_empty (struct cds_wfq_queue *q) { -struct cds_wfq_node **old_tail; +/* +* Queue is empty if no node is pointed by q->head.next nor +* q->tail. Even though the q->tail check is sufficient to find +* out of the queue is empty, we first check q->head.next as a +* common case to ensure that dequeuers do not frequently access +* enqueuer's q->tail cache line. +*/ +return CMM_LOAD_SHARED (q->dequeue.head.next) ==NULL + &&CMM_LOAD_SHARED (q->enqueue.tail) == &q->dequeue.head; +} + +static inline void ___cds_wfq_append (struct cds_wfq_queue *q, +struct cds_wfq_node *new_head, +struct cds_wfq_node *new_tail) +{ +struct cds_wfq_node *old_tail;/* -* uatomic_xchg() implicit memory barrier orders earlier stores to data -* structure containing node and setting node->next to NULL before -* publication. +* 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 (&q->tail, &node->next); + old_tail =uatomic_xchg (&q->enqueue.tail, new_tail); +/* -* At this point, dequeuers see a NULL old_tail->next, which indicates -* that the queue is being appended to. The following store will append -* "node" to the queue from a dequeuer perspective. +* Implicit memory barrier after uatomic_xchg() orders store to +* q->tail before store to old_tail->next. +* +* At this point, dequeuers see a NULL q->tail->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, node); +CMM_STORE_SHARED (old_tail->next, new_head); +} + +static inline void _cds_wfq_enqueue (struct cds_wfq_queue *q, +struct cds_wfq_node *new_tail) +{ +___cds_wfq_append (q, new_tail, new_tail); }/* @@ -100,14 +131,68 @@ ___cds_wfq_node_sync_next(struct cds_wfq_node *node)if (++attempt >=WFQ_ADAPT_ATTEMPTS ) {poll (NULL ,0 ,WFQ_WAIT );/* Wait for 10ms */ attempt =0 ; - }else + }else {caa_cpu_relax (); + } }return next; }/* +* ___cds_wfq_first_blocking: get first node of a queue, without dequeuing. +* +* Mutual exclusion with "dequeue" and "splice" operations must be ensured +* by the caller. +*/ +static inline struct cds_wfq_node * +___cds_wfq_first_blocking (struct cds_wfq_queue *q) +{ +struct cds_wfq_node *node; + +if (_cds_wfq_empty (q)) +return NULL ; + node =___cds_wfq_node_sync_next (&q->dequeue.head); +/* Load q->head.next before loading node's content */ +cmm_smp_read_barrier_depends (); +return node; +} + +/* +* ___cds_wfq_next_blocking: get next node of a queue, without dequeuing. +* +* Mutual exclusion with "dequeue" and "splice" operations must be ensured +* by the caller. +*/ +static inline struct cds_wfq_node * +___cds_wfq_next_blocking (struct cds_wfq_queue *q,struct cds_wfq_node *node) +{ +struct cds_wfq_node *next; + +/* +* Even though the following q->tail 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 q->tail cache line. +*/ +if ((next =CMM_LOAD_SHARED (node->next)) !=NULL ) { +/* Load node->next before loading next's content */ +cmm_smp_read_barrier_depends (); +return next; + } +/* Load node->next before q->tail */ +cmm_smp_rmb (); +if (CMM_LOAD_SHARED (q->enqueue.tail) == node) +return NULL ; + next =___cds_wfq_node_sync_next (node); +/* Load node->next before loading next's content */ +cmm_smp_read_barrier_depends (); +return next; +} + +/* +* ___cds_wfq_dequeue_blocking: dequeue a node from the queue. +* * It is valid to reuse and free a dequeued node immediately. * * No need to go on a waitqueue here, as there is no possible state in which the @@ -120,42 +205,104 @@ ___cds_wfq_dequeue_blocking(struct cds_wfq_queue *q) {struct cds_wfq_node *node, *next; -/* -* Queue is empty if it only contains the dummy node. -*/ -if (q->head == &q->dummy &&CMM_LOAD_SHARED (q->tail) == &q->dummy.next) +if (_cds_wfq_empty (q))return NULL ; - node = q->head; - next =___cds_wfq_node_sync_next (node); + node =___cds_wfq_node_sync_next (&q->dequeue.head); + +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_wfq_node_init (&q->dequeue.head); +if (uatomic_cmpxchg (&q->enqueue.tail, node, + &q->dequeue.head) == node) +return node; + next =___cds_wfq_node_sync_next (node); + }/* * Move queue head forward. */ - q->head = next; + q->dequeue.head.next = next; + +/* Load q->head.next before loading node's content */ +cmm_smp_read_barrier_depends (); +return node; +} + +/* +* ___cds_wfq_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. +* caller ensures mutual exclusion of dequeue and splice operations on +* src_q. +*/ +static inline void +___cds_wfq_splice_blocking (struct cds_wfq_queue *dest_q, +struct cds_wfq_queue *src_q) +{ +struct cds_wfq_node *head, *tail; + +if (_cds_wfq_empty (src_q)) +return ; + + head =___cds_wfq_node_sync_next (&src_q->dequeue.head); +_cds_wfq_node_init (&src_q->dequeue.head); +/* -* Requeue dummy node if we just dequeued it. +* 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. */ -if (node == &q->dummy) { -_cds_wfq_node_init (node); -_cds_wfq_enqueue (q, node); -return ___cds_wfq_dequeue_blocking (q); - } -return node; + tail =uatomic_xchg (&src_q->enqueue.tail, &src_q->dequeue.head); + +/* +* Append the spliced content of src_q into dest_q. Does not +* require mutual exclusion on dest_q (wait-free). +*/ +___cds_wfq_append (dest_q, head, tail); } +/* Locking performed within cds_wfq calls. */ static inline struct cds_wfq_node *_cds_wfq_dequeue_blocking (struct cds_wfq_queue *q) { -struct cds_wfq_node *retnode; +struct cds_wfq_node *retval; +int ret; + + ret =pthread_mutex_lock (&q->dequeue.lock); +assert (!ret); + retval =___cds_wfq_dequeue_blocking (q); + ret =pthread_mutex_unlock (&q->dequeue.lock); +assert (!ret); +return retval; +} + +static inline void +_cds_wfq_splice_blocking (struct cds_wfq_queue *dest_q, +struct cds_wfq_queue *src_q) +{int ret; - ret =pthread_mutex_lock (&q->lock); + ret =pthread_mutex_lock (&src_q->dequeue.lock);assert (!ret); - retnode =___cds_wfq_dequeue_blocking (q); - ret =pthread_mutex_unlock (&q->lock); +___cds_wfq_splice_blocking (dest_q, src_q); + ret =pthread_mutex_unlock (&src_q->dequeue.lock);assert (!ret); -return retnode; }#ifdef __cplusplusurcu/wfqueue.h +102
-15@@ -6,7 +6,8 @@* * Userspace RCU library - Queue with Wait-Free Enqueue/Blocking Dequeue * -* Copyright 2010 - Mathieu Desnoyers <[email protected]> +* 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 @@ -25,7 +26,9 @@#include <pthread.h> #include <assert.h> +#include <stdbool.h> #include <urcu/compiler.h> +#include <urcu/arch.h> #ifdef __cplusplusextern "C" {@@ -33,8 +36,6 @@ extern "C" {/* * Queue with wait-free enqueue/blocking dequeue. -* This implementation adds a dummy head node when the queue is empty to ensure -* we can always update the queue locklessly. * * Inspired from half-wait-free/half-blocking queue implementation done by * Paul E. McKenney. @@ -45,9 +46,13 @@ struct cds_wfq_node { };struct cds_wfq_queue { -struct cds_wfq_node *head, **tail; -struct cds_wfq_node dummy;/* Dummy node */ -pthread_mutex_t lock; +struct { +struct cds_wfq_node head; +pthread_mutex_t lock; + } __attribute__((aligned ((CAA_CACHE_LINE_SIZE )))) dequeue; +struct { +struct cds_wfq_node *tail; + } __attribute__((aligned ((CAA_CACHE_LINE_SIZE )))) enqueue; };#ifdef _LGPL_SOURCE@@ -55,22 +60,104 @@ struct cds_wfq_queue {#include <urcu/static/wfqueue.h> #define cds_wfq_node_init _cds_wfq_node_init -#define cds_wfq_init _cds_wfq_init -#define cds_wfq_enqueue _cds_wfq_enqueue -#define __cds_wfq_dequeue_blocking ___cds_wfq_dequeue_blocking +#define cds_wfq_init _cds_wfq_init +#define cds_wfq_empty _cds_wfq_empty +#define cds_wfq_enqueue _cds_wfq_enqueue + +/* Locking performed within cds_wfq calls. */ #define cds_wfq_dequeue_blocking _cds_wfq_dequeue_blocking +#define cds_wfq_splice_blocking _cds_wfq_splice_blocking +#define cds_wfq_first_blocking _cds_wfq_first_blocking +#define cds_wfq_next_blocking _cds_wfq_next_blocking + +/* Locking ensured by caller */ +#define __cds_wfq_dequeue_blocking ___cds_wfq_dequeue_blocking +#define __cds_wfq_splice_blocking ___cds_wfq_splice_blocking +#define __cds_wfq_first_blocking ___cds_wfq_first_blocking +#define __cds_wfq_next_blocking ___cds_wfq_next_blocking#else /* !_LGPL_SOURCE */ -extern void cds_wfq_node_init (struct cds_wfq_node *node); -extern void cds_wfq_init (struct cds_wfq_queue *q); -extern void cds_wfq_enqueue (struct cds_wfq_queue *q,struct cds_wfq_node *node); -/* __cds_wfq_dequeue_blocking: caller ensures mutual exclusion between dequeues */ -extern struct cds_wfq_node *__cds_wfq_dequeue_blocking (struct cds_wfq_queue *q); -extern struct cds_wfq_node *cds_wfq_dequeue_blocking (struct cds_wfq_queue *q); +extern void cds_wfq_node_init_1 (struct cds_wfq_node *node); +extern void cds_wfq_init_1 (struct cds_wfq_queue *q); +extern bool cds_wfq_empty_1 (struct cds_wfq_queue *q); +extern void cds_wfq_enqueue_1 (struct cds_wfq_queue *q,struct cds_wfq_node *node); + +/* Locking performed within cds_wfq calls. */ +extern struct cds_wfq_node *cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q); +extern void cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q, +struct cds_wfq_queue *src_q); + +/* +* __cds_wfq_dequeue_blocking: caller ensures mutual exclusion of dequeue +* and splice operations. +*/ +extern struct cds_wfq_node *__cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q); + +/* +* __cds_wfq_splice_blocking: caller ensures mutual exclusion of dequeue and +* splice operations on src_q. dest_q must be already initialized. +*/ +extern void __cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q, +struct cds_wfq_queue *src_q); + +/* +* __cds_wfq_first_blocking: mutual exclusion with "dequeue" and +* "splice" operations must be ensured by the caller. +*/ +extern struct cds_wfq_node *__cds_wfq_first_blocking_1 (struct cds_wfq_queue *q); + +/* +* __cds_wfq_next_blocking: mutual exclusion with "dequeue" and "splice" +* operations must be ensured by the caller. +*/ +extern struct cds_wfq_node *__cds_wfq_next_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node *node); + +#define cds_wfq_node_init cds_wfq_node_init_1 +#define cds_wfq_init cds_wfq_init_1 +#define cds_wfq_empty cds_wfq_empty_1 +#define cds_wfq_enqueue cds_wfq_enqueue_1 + +/* Locking performed within cds_wfq calls. */ +#define cds_wfq_dequeue_blocking cds_wfq_dequeue_blocking_1 +#define cds_wfq_splice_blocking cds_wfq_splice_blocking_1 +#define cds_wfq_first_blocking cds_wfq_first_blocking_1 +#define cds_wfq_next_blocking cds_wfq_next_blocking_1 + +/* Locking ensured by caller */ +#define __cds_wfq_dequeue_blocking __cds_wfq_dequeue_blocking_1 +#define __cds_wfq_splice_blocking __cds_wfq_splice_blocking_1 +#define __cds_wfq_first_blocking __cds_wfq_first_blocking_1 +#define __cds_wfq_next_blocking __cds_wfq_next_blocking_1#endif /* !_LGPL_SOURCE */ +/* +* __cds_wfq_for_each_blocking: Iterate over all nodes in a queue, +* without dequeuing them. +* +* Mutual exclusion with "dequeue" and "splice" operations must be +* ensured by the caller. +*/ +#define __cds_wfq_for_each_blocking (q, node) \ + for (node = __cds_wfq_first_blocking(q); \ + node != NULL; \ + node = __cds_wfq_next_blocking(q, node)) + +/* +* __cds_wfq_for_each_blocking_safe: Iterate over all nodes in a queue, +* without dequeuing them. Safe against deletion. +* +* Mutual exclusion with "dequeue" and "splice" operations must be +* ensured by the caller. +*/ +#define __cds_wfq_for_each_blocking_safe (q, node, n) \ + for (node = __cds_wfq_first_blocking(q), \ + n = (node ? __cds_wfq_next_blocking(q, node) : NULL); \ + node != NULL; \ + node = n, n = (node ? __cds_wfq_next_blocking(q, node) : NULL)) + #ifdef __cplusplus }#endif wfqueue.c +36
-7@@ -3,7 +3,8 @@* * Userspace RCU library - Queue with Wait-Free Enqueue/Blocking Dequeue * -* Copyright 2010 - Mathieu Desnoyers <[email protected]> +* 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 @@ -28,27 +29,55 @@* library wrappers to be used by non-LGPL compatible source code. */ -void cds_wfq_node_init (struct cds_wfq_node *node) +void cds_wfq_node_init_1 (struct cds_wfq_node *node) {_cds_wfq_node_init (node); } -void cds_wfq_init (struct cds_wfq_queue *q) +void cds_wfq_init_1 (struct cds_wfq_queue *q) {_cds_wfq_init (q); } -void cds_wfq_enqueue (struct cds_wfq_queue *q,struct cds_wfq_node *node) +bool cds_wfq_empty_1 (struct cds_wfq_queue *q) +{ +return _cds_wfq_empty (q); +} + +void cds_wfq_enqueue_1 (struct cds_wfq_queue *q,struct cds_wfq_node *node) {_cds_wfq_enqueue (q, node); } -struct cds_wfq_node *__cds_wfq_dequeue_blocking (struct cds_wfq_queue *q) +struct cds_wfq_node *cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q) +{ +return _cds_wfq_dequeue_blocking (q); +} + +void cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q, +struct cds_wfq_queue *src_q) +{ +_cds_wfq_splice_blocking (dest_q, src_q); +} + +struct cds_wfq_node *__cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q) {return ___cds_wfq_dequeue_blocking (q); } -struct cds_wfq_node *cds_wfq_dequeue_blocking (struct cds_wfq_queue *q) +void __cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q, +struct cds_wfq_queue *src_q) { -return _cds_wfq_dequeue_blocking (q); +___cds_wfq_splice_blocking (dest_q, src_q); +} + +struct cds_wfq_node *__cds_wfq_first_blocking_1 (struct cds_wfq_queue *q) +{ +return ___cds_wfq_first_blocking (q); +} + +struct cds_wfq_node *__cds_wfq_next_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node *node) +{ +return ___cds_wfq_next_blocking (q, node); }Signature · 10 lines
-- Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com _______________________________________________ lttng-dev mailing list [email protected] http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 4 lines · Mathieu Desnoyers
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)
Hi, Mathieu
please add this part to your patch.
Changes(item5 has alternative):
1) Reorder the head and the tail in struct cds_wfq_queue
Reason: wfq is enqueue-preference
2) Reorder the code of ___cds_wfq_next_blocking()
Reason: short code, better readability
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of struct cds_wfq_queue are not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIs
4) Add cds_wfq_node_sync_next(), cds_wfq_dequeue_all_blocking()
Reason: helper for for_each_*
5) Add more for_each_*, which default semantic is dequeuing
Reason: __cds_wfq_for_each_blocking_undequeue is enough for undequeuing loops
don't need to add more.
looping and dequeuing are the most probable use-cases.
dequeuing for_each_* make the queue like a pipe. make it act as a channel.(GO language)
Alternative: rename these dequeuing __cds_wfq_for_each*() to __cds_wfq_dequeue_for_each*
6) Remove __cds_wfq_for_each_blocking_safe
Reason: its semantic is not clear, hard to define a well-defined semantic to it.
when we use it, we have to delete none or delete all nodes, even when we delete all nodes, struct cds_wfq_queue still becomes stale while looping or after loop.
7) Rename old __cds_wfq_for_each_blocking() to __cds_wfq_for_each_blocking_undequeue()
Reason: the default semantic of the other for_each_* is dequeuing.
--- urcu-call-rcu-impl.h | 13 +--- urcu/static/wfqueue.h | 131 ++++++++++++++++++++++++++++-------------- urcu/wfqueue.h | 154 ++++++++++++++++++++++++++++++++++++-------------- wfqueue.c | 27 ++++++++ 4 files changed, 233 insertions(+), 92 deletions(-)
urcu-call-rcu-impl.h +6 -7
@@ -241,16 +241,15 @@ static void *call_rcu_thread(void *arg)cmm_smp_mb (); }for (;;) { -struct cds_wfq_queue cbs_tmp; -struct cds_wfq_node *cbs, *tmp_cbs; +while (!cds_wfq_empty (&crdp->cbs)) { +struct cds_wfq_node *cbs, *next, *tail; -cds_wfq_init (&cbs_tmp); -__cds_wfq_splice_blocking (&cbs_tmp, &crdp->cbs); -if (!cds_wfq_empty (&cbs_tmp)) { + next =__cds_wfq_dequeue_all_blocking (&crdp->cbs, &tail);synchronize_rcu (); cbcount =0 ; -__cds_wfq_for_each_blocking_safe (&cbs_tmp, - cbs, tmp_cbs) { + +__cds_wfq_for_each_blocking_nobreak_internal ( + next, cbs, next, tail) {struct rcu_head *rhp; rhp = caa_container_of(cbs,
urcu/static/wfqueue.h +87 -44
204 lines not on this page · raw message
urcu/wfqueue.h +113 -41
225 lines not on this page · raw message
wfqueue.c +27 -0
@@ -44,16 +44,37 @@ bool cds_wfq_empty_1(struct cds_wfq_queue *q)return _cds_wfq_empty (q); } +void cds_wfq_dequeue_lock_1 (struct cds_wfq_queue *q) +{ +cds_wfq_dequeue_lock (q); +} + +void cds_wfq_dequeue_unlock_1 (struct cds_wfq_queue *q) +{ +cds_wfq_dequeue_unlock (q); +} +void cds_wfq_enqueue_1 (struct cds_wfq_queue *q,struct cds_wfq_node *node) {_cds_wfq_enqueue (q, node); } +struct cds_wfq_node *cds_wfq_node_sync_next_1 (struct cds_wfq_node *node) +{ +return _cds_wfq_node_sync_next (node); +} +struct cds_wfq_node *cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q) {return _cds_wfq_dequeue_blocking (q); } +struct cds_wfq_node *cds_wfq_dequeue_all_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail) +{ +return _cds_wfq_dequeue_all_blocking (q, ret_tail); +} +void cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q,struct cds_wfq_queue *src_q) {
@@ -65,6 +86,12 @@ struct cds_wfq_node *__cds_wfq_dequeue_blocking_1(struct cds_wfq_queue *q)return ___cds_wfq_dequeue_blocking (q); } +struct cds_wfq_node *__cds_wfq_dequeue_all_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail) +{ +return ___cds_wfq_dequeue_all_blocking (q, ret_tail); +} +void __cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q,struct cds_wfq_queue *src_q) {
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 6 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
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)
Hi Lai,
Quoted 8 lines
Hi, Mathieu
please add this part to your patch.
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preference
Is this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
Quoted 2 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readability
Yes, I agree with this change. Can you extract it into a separate patch ?
Quoted 5 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIs
I agree with this change too. You can put it into the same patch as (2).
Quoted 3 lines
4) Add
cds_wfq_node_sync_next(),cds_wfq_dequeue_all_blocking()
Reason: helper for for_each_*
Points 4-5-6-7 will need more discussion.
I don't like exposing "cds_wfq_node_sync_next()", which should remain an internal implementation detail not exposed to queue users. The "get_first"/"get_next" API, as well as the dequeue, are providing an abstraction that hide the node synchronization, which makes it harder for the user to make mistakes. Given that the fast-path of cds_wfq_node_sync_next is just a pointer load and test, I don't think that skipping this the second time we iterate on the same queue would bring any significant performance improvement, but exposing sync_next adds in API complexity, which I would like to avoid.
About cds_wfq_dequeue_all_blocking(): the "cds_wfq_splice()" I introduced performs the same action as "cds_wfq_dequeue_all_blocking()", but ensures that we can splice lists multiple times (rather than only once), which is a very neat side-effect. Let's imagine a use-case like Tree RCU, where each CPU produce a queue of call_rcu callbacks, and we need to merge pairs of queues together recursively until we reach the tree root: by doing splice() at each level of the tree, we can combine the queues into a single queue without ever needing to do an iteration on each node: no node synchronization is needed until we actually need to traverse the queue at the root node level.
The cost of exposing dequeue_all is that we need to expose sync_next (more complexity for the user). As you exposed in your earlier email, the gain we get by exposing dequeue_all separately from splice is that dequeue_all is 1 xchg() operation, while splice is 2 xchg() operations. However, given that this operation is typically amortized over many nodes makes performance optimization a less compelling argument than simplicity of use.
Quoted 7 lines
5) Add more for_each_*, which default semantic is dequeuing
Reason:__cds_wfq_for_each_blocking_undequeueis enough for undequeuing loops
don't need to add more.
looping and dequeuing are the most probable use-cases.
dequeuing for_each_* make the queue like a pipe. make it act as a channel.(GO language)
Alternative: rename these dequeuing __cds_wfq_for_each*() to __cds_wfq_dequeue_for_each*
I notice, in the iterators you added, the presence of "cds_wfq_for_each_blocking_nobreak", and "cds_wfq_for_each_blocking_nobreak_internal", which document that this special flavor is needed for loops that do not have a "break" statement. That seems to be very much error-prone and counter-intuitive for users, and I would like to avoid that.
The "internal" flavor, along with "sync_next" are then used in the call_rcu code, since they are needed to get the best performance possible. I don't like to use special, internal APIs for call_rcu: the original motivation for refactoring the wfqueue code was testability, and I would really like to make sure that the APIs we use internally are also exposed to the outside world, mainly for testability, and also because if we need to directly access internal interfaces to have good performance, it means we did a poor job at exporting APIs that allow to do the same kind of highly-efficient use of the queue. Exposing an API with the "internal" keyword in it clearly discourages users from using it.
Quoted 5 lines
6) Remove
__cds_wfq_for_each_blocking_safe
Reason: its semantic is not clear, hard to define a well-defined semantic to it.
when we use it, we have to delete none or delete all nodes, even when we delete all nodes, structcds_wfq_queuestill becomes stale while looping or after loop.
The typical use-case I envision is:
- enqueue many nodes to queue A
- then, a dequeuer thread splice the content of queue A into its temporary queue T (which head is local on its stack).
- now, the thread is free to iterate on queue T, as many times as it likes, and it does not need to change the structure of the queue while iterating on it (read-only operation, without side-effect). The last time it iterates on queue T, it needs to use the _safe iteration and free the nodes.
- after the nodes have been deleted, the queue T can be simply discarded (if on stack, function return will do so; if dynamically allocated, can be simply reinitialized to an empty queue, or freed).
As you certainly noticed, we can iterate both on a queue being concurrently enqueued to, and on a queue that has been spliced into. Being able to use iterators and dequeue on any queue (initial enqueue, or queue spliced to) is a feature: we can therefore postpone the "sync_next" synchronization to the moment where loop iteration is really needed (lazy synchronization), which keeps optimal locality of reference of synchronization vs node data access.
Quoted 3 lines
7) Rename old
__cds_wfq_for_each_blocking()to__cds_wfq_for_each_blocking_undequeue()
Reason: the default semantic of the other for_each_* is dequeuing.
I'm not convinced that "__cds_wfq_for_each_blocking_nobreak", "__cds_wfq_for_each_blocking_nobreak_internal", and sync_next APIs are improvements over the API I propose. For call_rcu, this turns
cds_wfq_enqueue()cds_wfq_splice_blocking()__cds_wfq_for_each_blocking_safe() for iteration
into:
cds_wfq_enqueue()__cds_wfq_dequeue_all_blocking() __cds_wfq_for_each_blocking_nobreak_internal() for iteration
Maybe we could do some documentation improvement to "__cds_wfq_for_each_blocking(_safe)", __cds_wfq_first_blocking(), __cds_wfq_next_blocking() API members I proposed. Maybe I did not document them well enough ?
Thanks,
Mathieu
Quoted 538 lines
--- urcu-call-rcu-impl.h | 13 +--- urcu/static/wfqueue.h | 131 ++++++++++++++++++++++++++++-------------- urcu/wfqueue.h | 154 ++++++++++++++++++++++++++++++++++++-------------- wfqueue.c | 27 ++++++++ 4 files changed, 233 insertions(+), 92 deletions(-)urcu-call-rcu-impl.h +6
-7@@ -241,16 +241,15 @@ static void *call_rcu_thread(void *arg)cmm_smp_mb (); }for (;;) { -struct cds_wfq_queue cbs_tmp; -struct cds_wfq_node *cbs, *tmp_cbs; +while (!cds_wfq_empty (&crdp->cbs)) { +struct cds_wfq_node *cbs, *next, *tail; -cds_wfq_init (&cbs_tmp); -__cds_wfq_splice_blocking (&cbs_tmp, &crdp->cbs); -if (!cds_wfq_empty (&cbs_tmp)) { + next =__cds_wfq_dequeue_all_blocking (&crdp->cbs, &tail);synchronize_rcu (); cbcount =0 ; -__cds_wfq_for_each_blocking_safe (&cbs_tmp, - cbs, tmp_cbs) { + +__cds_wfq_for_each_blocking_nobreak_internal ( + next, cbs, next, tail) {struct rcu_head *rhp; rhp = caa_container_of(cbs,urcu/static/wfqueue.h +87
-44@@ -84,6 +84,22 @@ static inline bool _cds_wfq_empty(struct cds_wfq_queue *q) &&CMM_LOAD_SHARED (q->enqueue.tail) == &q->dequeue.head; } +static inline void _cds_wfq_dequeue_lock (struct cds_wfq_queue *q) +{ +int ret; + + ret =pthread_mutex_lock (&q->dequeue.lock); +assert (!ret); +} + +static inline void _cds_wfq_dequeue_unlock (struct cds_wfq_queue *q) +{ +int ret; + + ret =pthread_mutex_unlock (&q->dequeue.lock); +assert (!ret); +} +static inline void ___cds_wfq_append (struct cds_wfq_queue *q,struct cds_wfq_node *new_head,struct cds_wfq_node *new_tail)@@ -139,30 +155,33 @@ ___cds_wfq_node_sync_next(struct cds_wfq_node *node)return next; } +static inline struct cds_wfq_node * +_cds_wfq_node_sync_next (struct cds_wfq_node *node) +{ +struct cds_wfq_node *next =___cds_wfq_node_sync_next (node); + +/* Load node->next before loading next's content */ +cmm_smp_read_barrier_depends (); +return next; +} +/* * ___cds_wfq_first_blocking: get first node of a queue, without dequeuing. * -* Mutual exclusion with "dequeue" and "splice" operations must be ensured -* by the caller. +* Should be called with cds_wfq_dequeue_lock() held. */ static inline struct cds_wfq_node *___cds_wfq_first_blocking (struct cds_wfq_queue *q) { -struct cds_wfq_node *node; -if (_cds_wfq_empty (q))return NULL ; - node =___cds_wfq_node_sync_next (&q->dequeue.head); -/* Load q->head.next before loading node's content */ -cmm_smp_read_barrier_depends (); -return node; +return _cds_wfq_node_sync_next (&q->dequeue.head); }/* * ___cds_wfq_next_blocking: get next node of a queue, without dequeuing. * -* Mutual exclusion with "dequeue" and "splice" operations must be ensured -* by the caller. +* Should be called with cds_wfq_dequeue_lock() held. */ static inline struct cds_wfq_node *___cds_wfq_next_blocking (struct cds_wfq_queue *q,struct cds_wfq_node *node)@@ -175,16 +194,13 @@ ___cds_wfq_next_blocking(struct cds_wfq_queue *q, struct cds_wfq_node *node)* node->next as a common case to ensure that iteration on nodes * do not frequently access enqueuer's q->tail cache line. */ -if ((next =CMM_LOAD_SHARED (node->next)) !=NULL ) { -/* Load node->next before loading next's content */ -cmm_smp_read_barrier_depends (); -return next; +if ((next =CMM_LOAD_SHARED (node->next)) ==NULL ) { +/* Load node->next before q->tail */ +cmm_smp_rmb (); +if (CMM_LOAD_SHARED (q->enqueue.tail) == node) +return NULL ; + next =___cds_wfq_node_sync_next (node); } -/* Load node->next before q->tail */ -cmm_smp_rmb (); -if (CMM_LOAD_SHARED (q->enqueue.tail) == node) -return NULL ; - next =___cds_wfq_node_sync_next (node);/* Load node->next before loading next's content */ cmm_smp_read_barrier_depends ();return next;@@ -199,6 +215,8 @@ ___cds_wfq_next_blocking(struct cds_wfq_queue *q, struct cds_wfq_node *node)* 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. +* +* Should be called with cds_wfq_dequeue_lock() held. */ static inline struct cds_wfq_node *___cds_wfq_dequeue_blocking (struct cds_wfq_queue *q)@@ -243,12 +261,41 @@ ___cds_wfq_dequeue_blocking(struct cds_wfq_queue *q) }/* +* ___cds_wfq_dequeue_all_blocking: dequeue all nodes +* +* Dequeue all nodes from @q. +* Returns the head of the dequeued nodes which tail is saved in @ret_tail. +* Should be called with cds_wfq_dequeue_lock() held. +*/ +static inline struct cds_wfq_node * +___cds_wfq_dequeue_all_blocking (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail) +{ +struct cds_wfq_node *head; + +if (_cds_wfq_empty (q)) +return NULL ; + + head =___cds_wfq_node_sync_next (&q->dequeue.head); +_cds_wfq_node_init (&q->dequeue.head); + +/* +* Memory barrier implied before uatomic_xchg() orders store to +* q->dequeue.head before store to q->enqueue.tail. This is required +* by concurrent enqueue on q, which exchanges the tail before +* updating the previous tail's next pointer. +*/ + *ret_tail =uatomic_xchg (&q->enqueue.tail, &q->dequeue.head); + +return head; +} + +/* * ___cds_wfq_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. -* caller ensures mutual exclusion of dequeue and splice operations on -* src_q. +* Should be called with cds_wfq_dequeue_lock() held. */ static inline void ___cds_wfq_splice_blocking(struct cds_wfq_queue *dest_q,@@ -256,20 +303,9 @@ ___cds_wfq_splice_blocking(struct cds_wfq_queue *dest_q, {struct cds_wfq_node *head, *tail; -if (_cds_wfq_empty (src_q)) +if ((head =___cds_wfq_dequeue_all_blocking (src_q, &tail)) ==NULL )return ; - head =___cds_wfq_node_sync_next (&src_q->dequeue.head); -_cds_wfq_node_init (&src_q->dequeue.head); - -/* -* 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->enqueue.tail, &src_q->dequeue.head); -/* * Append the spliced content of src_q into dest_q. Does not * require mutual exclusion on dest_q (wait-free). @@ -282,27 +318,34 @@ static inline struct cds_wfq_node * _cds_wfq_dequeue_blocking(struct cds_wfq_queue *q) {struct cds_wfq_node *retval; -int ret; - ret =pthread_mutex_lock (&q->dequeue.lock); -assert (!ret); +_cds_wfq_dequeue_lock (q); retval =___cds_wfq_dequeue_blocking (q); - ret =pthread_mutex_unlock (&q->dequeue.lock); -assert (!ret); +_cds_wfq_dequeue_unlock (q); +return retval; } +static inline struct cds_wfq_node * +_cds_wfq_dequeue_all_blocking (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail) +{ +struct cds_wfq_node *head; + +_cds_wfq_dequeue_lock (q); + head =_cds_wfq_dequeue_all_blocking (q, ret_tail); +_cds_wfq_dequeue_unlock (q); + +return head; +} +static inline void _cds_wfq_splice_blocking (struct cds_wfq_queue *dest_q,struct cds_wfq_queue *src_q) { -int ret; - - ret =pthread_mutex_lock (&src_q->dequeue.lock); -assert (!ret); +_cds_wfq_dequeue_lock (src_q);___cds_wfq_splice_blocking (dest_q, src_q); - ret =pthread_mutex_unlock (&src_q->dequeue.lock); -assert (!ret); +_cds_wfq_dequeue_unlock (src_q); }#ifdef __cplusplusurcu/wfqueue.h +113
-41@@ -47,12 +47,12 @@ struct cds_wfq_node {struct cds_wfq_queue {struct { +struct cds_wfq_node *tail; + } __attribute__((aligned ((CAA_CACHE_LINE_SIZE )))) enqueue; +struct {struct cds_wfq_node head;pthread_mutex_t lock; } __attribute__((aligned ((CAA_CACHE_LINE_SIZE )))) dequeue; -struct { -struct cds_wfq_node *tail; - } __attribute__((aligned ((CAA_CACHE_LINE_SIZE )))) enqueue; };#ifdef _LGPL_SOURCE@@ -62,71 +62,97 @@ struct cds_wfq_queue {#define cds_wfq_node_init _cds_wfq_node_init#define cds_wfq_init _cds_wfq_init#define cds_wfq_empty _cds_wfq_empty + +/* Locking */ +#define cds_wfq_dequeue_lock _cds_wfq_dequeue_lock +#define cds_wfq_dequeue_unlock _cds_wfq_dequeue_unlock +#define cds_wfq_enqueue _cds_wfq_enqueue +/* +* Helpers for for_each_*: +* cds_wfq_node_sync_next() +* cds_wfq_dequeue_all_blocking() +* __cds_wfq_dequeue_all_blocking() +* __cds_wfq_first_blocking() +* __cds_wfq_next_blocking() +*/ +#define cds_wfq_node_sync_next _cds_wfq_node_sync_next +/* Locking performed within cds_wfq calls. */ #define cds_wfq_dequeue_blocking _cds_wfq_dequeue_blocking +#define cds_wfq_dequeue_all_blocking _cds_wfq_dequeue_all_blocking#define cds_wfq_splice_blocking _cds_wfq_splice_blocking -#define cds_wfq_first_blocking _cds_wfq_first_blocking -#define cds_wfq_next_blocking _cds_wfq_next_blocking -/* Locking ensured by caller */ +/* Locking ensured by caller(called with cds_wfq_dequeue_lock() held) */ #define __cds_wfq_dequeue_blocking ___cds_wfq_dequeue_blocking +#define __cds_wfq_dequeue_all_blocking ___cds_wfq_dequeue_all_blocking#define __cds_wfq_splice_blocking ___cds_wfq_splice_blocking#define __cds_wfq_first_blocking ___cds_wfq_first_blocking#define __cds_wfq_next_blocking ___cds_wfq_next_blocking#else /* !_LGPL_SOURCE */ +/* !_LGPL_SOURCE wrappers */ +extern void cds_wfq_node_init_1 (struct cds_wfq_node *node);extern void cds_wfq_init_1 (struct cds_wfq_queue *q);extern bool cds_wfq_empty_1 (struct cds_wfq_queue *q); + +extern void cds_wfq_dequeue_lock_1 (struct cds_wfq_queue *q); +extern void cds_wfq_dequeue_unlock_1 (struct cds_wfq_queue *q); +extern void cds_wfq_enqueue_1 (struct cds_wfq_queue *q,struct cds_wfq_node *node); +extern struct cds_wfq_node *cds_wfq_node_sync_next_1 (struct cds_wfq_node *node); +/* Locking performed within cds_wfq calls. */ extern struct cds_wfq_node *cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q); +extern struct cds_wfq_node *cds_wfq_dequeue_all_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail);extern void cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q,struct cds_wfq_queue *src_q); -/* -* __cds_wfq_dequeue_blocking: caller ensures mutual exclusion of dequeue -* and splice operations. -*/ +/* The following functions shouled be called with cds_wfq_dequeue_lock() held */ extern struct cds_wfq_node *__cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q); - -/* -* __cds_wfq_splice_blocking: caller ensures mutual exclusion of dequeue and -* splice operations on src_q. dest_q must be already initialized. -*/ +extern struct cds_wfq_node *__cds_wfq_dequeue_all_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail);extern void __cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q,struct cds_wfq_queue *src_q); - -/* -* __cds_wfq_first_blocking: mutual exclusion with "dequeue" and -* "splice" operations must be ensured by the caller. -*/ extern struct cds_wfq_node *__cds_wfq_first_blocking_1 (struct cds_wfq_queue *q); - -/* -* __cds_wfq_next_blocking: mutual exclusion with "dequeue" and "splice" -* operations must be ensured by the caller. -*/ extern struct cds_wfq_node *__cds_wfq_next_blocking_1 (struct cds_wfq_queue *q,struct cds_wfq_node *node); +/* !_LGPL_SOURCE APIs */ +#define cds_wfq_node_init cds_wfq_node_init_1#define cds_wfq_init cds_wfq_init_1#define cds_wfq_empty cds_wfq_empty_1 + +/* Locking */ +#define cds_wfq_dequeue_lock cds_wfq_dequeue_lock_1 +#define cds_wfq_dequeue_unlock cds_wfq_dequeue_unlock_1 +#define cds_wfq_enqueue cds_wfq_enqueue_1 +/* +* Helpers for for_each_*: +* cds_wfq_node_sync_next() +* cds_wfq_dequeue_all_blocking() +* __cds_wfq_dequeue_all_blocking() +* __cds_wfq_first_blocking() +* __cds_wfq_next_blocking() +*/ +#define cds_wfq_node_sync_next cds_wfq_node_sync_next_1 +/* Locking performed within cds_wfq calls. */ #define cds_wfq_dequeue_blocking cds_wfq_dequeue_blocking_1 +#define cds_wfq_dequeue_all_blocking cds_wfq_dequeue_all_blocking_1#define cds_wfq_splice_blocking cds_wfq_splice_blocking_1 -#define cds_wfq_first_blocking cds_wfq_first_blocking_1 -#define cds_wfq_next_blocking cds_wfq_next_blocking_1 -/* Locking ensured by caller */ +/* Locking ensured by caller(called with cds_wfq_dequeue_lock() held) */ #define __cds_wfq_dequeue_blocking __cds_wfq_dequeue_blocking_1 +#define __cds_wfq_dequeue_all_blocking __cds_wfq_dequeue_all_blocking_1#define __cds_wfq_splice_blocking __cds_wfq_splice_blocking_1#define __cds_wfq_first_blocking __cds_wfq_first_blocking_1#define __cds_wfq_next_blocking __cds_wfq_next_blocking_1@@ -134,29 +160,75 @@ extern struct cds_wfq_node *__cds_wfq_next_blocking_1(struct cds_wfq_queue *q,#endif /* !_LGPL_SOURCE */ /* -* __cds_wfq_for_each_blocking: Iterate over all nodes in a queue, +* for_each_* routines: Iterate over all nodes in a queue and dequeue +* the travlled nodes(except __cds_wfq_for_each_blocking_undequeue). +* +* All nodes which are un-dequeued && enqueued before the for_each_* +* will be travelled. +* +* Nodes which are enqueued after the for_each_* started MAY or may NOT +* be travelled. +*/ + +/* +* __cds_wfq_for_each_blocking_undequeue: Iterate over all nodes in a queue, * without dequeuing them. * -* Mutual exclusion with "dequeue" and "splice" operations must be -* ensured by the caller. +* Should be called with cds_wfq_dequeue_lock() held. */ -#define __cds_wfq_for_each_blocking (q, node) \ +#define __cds_wfq_for_each_blocking_undequeue (q, node) \ for (node = __cds_wfq_first_blocking(q); \ node != NULL; \ node = __cds_wfq_next_blocking(q, node)) +#define __cds_wfq_for_each_blocking_nobreak_internal (all, node, next, tail) \ + for (node = all, \ + next = ((node && node != tail) ? cds_wfq_node_sync_next(node) : NULL); \ + node != NULL; \ + node = next, \ + next = ((node && node != tail) ? cds_wfq_node_sync_next(node) : NULL)) +/* -* __cds_wfq_for_each_blocking_safe: Iterate over all nodes in a queue, -* without dequeuing them. Safe against deletion. +* __cds_wfq_for_each_blocking_nobreak: Iterate over all nodes in a queue, +* and dequeue them. * -* Mutual exclusion with "dequeue" and "splice" operations must be -* ensured by the caller. +* Should not use "break;" or other statement to leave the control flow +* from the loop body, otherwise it causes un-travelled nodes leak. +* +* Should be called with cds_wfq_dequeue_lock() held. +*/ +#define __cds_wfq_for_each_blocking_nobreak (q, node, next, tail) \ + __cds_wfq_for_each_blocking_nobreak_internal( \ + __cds_wfq_dequeue_all_blocking(q, &tail), node, next, tail) + +/* +* cds_wfq_for_each_blocking_nobreak: Iterate over all nodes in a queue, +* and dequeue them. +* +* Should not use "break;" or other statement to leave the control flow +* from the loop body, otherwise it causes un-travelled nodes leak. +*/ +#define cds_wfq_for_each_blocking_nobreak (q, node, next, tail) \ + __cds_wfq_for_each_blocking_nobreak_internal( \ + cds_wfq_dequeue_all_blocking(q, &tail), node, next, tail) + +/* +* __cds_wfq_for_each_blocking: Iterate over all nodes in a queue, +* and dequeue them. +* +* Should be called with cds_wfq_dequeue_lock() held. +*/ +#define __cds_wfq_for_each_blocking (q, node) \ + for (node = __cds_wfq_dequeue_blocking(q); node; \ + node = __cds_wfq_dequeue_blocking(q)) + +/* +* cds_wfq_for_each_blocking: Iterate over all nodes in a queue, +* and dequeue them. */ -#define __cds_wfq_for_each_blocking_safe (q, node, n) \ - for (node = __cds_wfq_first_blocking(q), \ - n = (node ? __cds_wfq_next_blocking(q, node) : NULL); \ - node != NULL; \ - node = n, n = (node ? __cds_wfq_next_blocking(q, node) : NULL)) +#define cds_wfq_for_each_blocking (q, node) \ + for (node = cds_wfq_dequeue_blocking(q); node; \ + node = cds_wfq_dequeue_blocking(q)) #ifdef __cplusplus }wfqueue.c +27
-0@@ -44,16 +44,37 @@ bool cds_wfq_empty_1(struct cds_wfq_queue *q)return _cds_wfq_empty (q); } +void cds_wfq_dequeue_lock_1 (struct cds_wfq_queue *q) +{ +cds_wfq_dequeue_lock (q); +} + +void cds_wfq_dequeue_unlock_1 (struct cds_wfq_queue *q) +{ +cds_wfq_dequeue_unlock (q); +} +void cds_wfq_enqueue_1 (struct cds_wfq_queue *q,struct cds_wfq_node *node) {_cds_wfq_enqueue (q, node); } +struct cds_wfq_node *cds_wfq_node_sync_next_1 (struct cds_wfq_node *node) +{ +return _cds_wfq_node_sync_next (node); +} +struct cds_wfq_node *cds_wfq_dequeue_blocking_1 (struct cds_wfq_queue *q) {return _cds_wfq_dequeue_blocking (q); } +struct cds_wfq_node *cds_wfq_dequeue_all_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail) +{ +return _cds_wfq_dequeue_all_blocking (q, ret_tail); +} +void cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q,struct cds_wfq_queue *src_q) {@@ -65,6 +86,12 @@ struct cds_wfq_node *__cds_wfq_dequeue_blocking_1(struct cds_wfq_queue *q)return ___cds_wfq_dequeue_blocking (q); } +struct cds_wfq_node *__cds_wfq_dequeue_all_blocking_1 (struct cds_wfq_queue *q, +struct cds_wfq_node **ret_tail) +{ +return ___cds_wfq_dequeue_all_blocking (q, ret_tail); +} +void __cds_wfq_splice_blocking_1 (struct cds_wfq_queue *dest_q,struct cds_wfq_queue *src_q) {
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): 20120820131642.GA551@Krystal
Quoted 14 lines · Mathieu Desnoyers
Quoted 6 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
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)Hi Lai,
Quoted 4 lines
Hi, Mathieu
please add this part to your patch.
Quoted 8 lines
Quoted 4 lines
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preferenceIs this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
struct astruct {
int foo; /* field offset = 0 */
int bar; /* field offset = 4 */
};
Access to p->foo and access to p->bar are different in CPU instruction. Access to p->bar will need to add a offset to p. (the addition may cost a very small time) instructions will be probably longer than the instructions access to p->foo.
If the code of access to p->bar is significant more than the code of access to p->foo, we should swap p->bar and p->foo field's order to shorten the total instruction size to reduce footprint.
Our enqueue is inline function, when this inline function is expanded in every call site, the code of access to the tail will much significant, so we need to put the tail at first.
Quoted 5 lines
Quoted 3 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readabilityYes, I agree with this change. Can you extract it into a separate patch ?
You merge it into your patch which ___cds_wfq_next_blocking() is introduced.
Quoted 8 lines
Quoted 6 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIsI agree with this change too. You can put it into the same patch as (2).
You merge it into your patch.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 33 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 14 lines · Mathieu Desnoyers
Quoted 6 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
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)Hi Lai,
Quoted 4 lines
Hi, Mathieu
please add this part to your patch.
Quoted 8 lines
Quoted 4 lines
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preferenceIs this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
struct astruct {
int foo; /* field offset = 0 */
int bar; /* field offset = 4 */
};Access to
p->fooand access top->barare different in CPU instruction. Access top->barwill need to add a offset to p. (the addition may cost a very small time) instructions will be probably longer than the instructions access top->foo.
Quoted 7 lines
If the code of access to
p->baris significant more than the code of access top->foo, we should swapp->barandp->foofield's order to shorten the total instruction size to reduce footprint.Our enqueue is inline function, when this inline function is expanded in every call site, the code of access to the tail will much significant, so we need to put the tail at first.
Very good point! I'm pulling this change too.
Quoted 10 lines
Quoted 7 lines
Quoted 5 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readabilityYes, I agree with this change. Can you extract it into a separate patch ?
You merge it into your patch which
___cds_wfq_next_blocking()is introduced.
OK. done,
Quoted 10 lines
Quoted 8 lines
Quoted 6 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIsI agree with this change too. You can put it into the same patch as (2).
You merge it into your patch.
OK, done too.
The current version (volatile branch) is at
git://git.dorsal.polymtl.ca/~compudj/userspace-rcu
branch: urcu/wfqueue-volatile
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): 20120821010351.GA7472@Krystal
Quoted 68 lines · Mathieu Desnoyers
Quoted 33 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 14 lines · Mathieu Desnoyers
Quoted 6 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
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)Hi Lai,
Quoted 4 lines
Hi, Mathieu
please add this part to your patch.
Quoted 8 lines
Quoted 4 lines
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preferenceIs this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
struct astruct {
int foo; /* field offset = 0 */
int bar; /* field offset = 4 */
};Access to
p->fooand access top->barare different in CPU instruction. Access top->barwill need to add a offset to p. (the addition may cost a very small time) instructions will be probably longer than the instructions access top->foo.Quoted 7 lines
If the code of access to
p->baris significant more than the code of access top->foo, we should swapp->barandp->foofield's order to shorten the total instruction size to reduce footprint.Our enqueue is inline function, when this inline function is expanded in every call site, the code of access to the tail will much significant, so we need to put the tail at first.
Very good point! I'm pulling this change too.
Quoted 10 lines
Quoted 7 lines
Quoted 5 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readabilityYes, I agree with this change. Can you extract it into a separate patch ?
You merge it into your patch which
___cds_wfq_next_blocking()is introduced.OK. done,
Quoted 10 lines
Quoted 8 lines
Quoted 6 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIsI agree with this change too. You can put it into the same patch as (2).
You merge it into your patch.
Quoted 9 lines
OK, done too.
The current version (volatile branch) is at
git://git.dorsal.polymtl.ca/~compudj/userspace-rcu
branch: urcu/wfqueue-volatileThanks!
We can merge all things into a single patch until the discussion are finished. I don't want to have several commits in the git-tree that every commit fix some thing of the previous commit.
When the big single patch is done, we can separate the patch properly. It will help others to understand the code from git-log.
I will be very appreciate if one or two small patch(s) is committed with my name.
Thanks,
Lai.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 76 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 75 lines · Mathieu Desnoyers
Quoted 33 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 14 lines · Mathieu Desnoyers
Quoted 6 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
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)Hi Lai,
Quoted 4 lines
Hi, Mathieu
please add this part to your patch.
Quoted 8 lines
Quoted 4 lines
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preferenceIs this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
struct astruct {
int foo; /* field offset = 0 */
int bar; /* field offset = 4 */
};Access to
p->fooand access top->barare different in CPU instruction. Access top->barwill need to add a offset to p. (the addition may cost a very small time) instructions will be probably longer than the instructions access top->foo.Quoted 7 lines
If the code of access to
p->baris significant more than the code of access top->foo, we should swapp->barandp->foofield's order to shorten the total instruction size to reduce footprint.Our enqueue is inline function, when this inline function is expanded in every call site, the code of access to the tail will much significant, so we need to put the tail at first.
Very good point! I'm pulling this change too.
Quoted 10 lines
Quoted 7 lines
Quoted 5 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readabilityYes, I agree with this change. Can you extract it into a separate patch ?
You merge it into your patch which
___cds_wfq_next_blocking()is introduced.OK. done,
Quoted 10 lines
Quoted 8 lines
Quoted 6 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIsI agree with this change too. You can put it into the same patch as (2).
You merge it into your patch.
OK, done too.
The current version (volatile branch) is at
git://git.dorsal.polymtl.ca/~compudj/userspace-rcu
branch: urcu/wfqueue-volatile
Quoted 7 lines
Quoted 2 lines
Thanks!
We can merge all things into a single patch until the discussion are finished. I don't want to have several commits in the git-tree that every commit fix some thing of the previous commit.
Yes, I agree.
Quoted 3 lines
When the big single patch is done, we can separate the patch properly. It will help others to understand the code from git-log.
Yes, that can be done. Hopefully we'll manage to find the time to do this.
Quoted 3 lines
I will be very appreciate if one or two small patch(s) is committed with my name.
Of course! The only reason why I set the From on the current patch to my own name is because I did not want to give you the blame for my own errors (although I kept the credits to you in the changelog). Splitting the work in sub-patches will make it easier to credit each of us for specific portions of the code.
Thanks!
Mathieu
Quoted 3 lines
Thanks,
Lai.
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 42 lines · Mathieu Desnoyers
Quoted 6 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
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)Hi Lai,
Quoted 8 lines
Hi, Mathieu
please add this part to your patch.
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preferenceIs this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
Quoted 2 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readabilityYes, I agree with this change. Can you extract it into a separate patch ?
Quoted 5 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIsI agree with this change too. You can put it into the same patch as (2).
Quoted 3 lines
4) Add
cds_wfq_node_sync_next(),cds_wfq_dequeue_all_blocking()
Reason: helper for for_each_*Points 4-5-6-7 will need more discussion.
Quoted 9 lines
I don't like exposing "
cds_wfq_node_sync_next()", which should remain an internal implementation detail not exposed to queue users. The "get_first"/"get_next" API, as well as the dequeue, are providing an abstraction that hide the node synchronization, which makes it harder for the user to make mistakes. Given that the fast-path ofcds_wfq_node_sync_nextis just a pointer load and test, I don't think that skipping this the second time we iterate on the same queue would bring any significant performance improvement, but exposingsync_nextadds in API complexity, which I would like to avoid.
If the name "cds_wfq_node_sync_next()" is bad and exposes the implementation, we can rename it to "__cds_wfq_next_blocking_nocheck()" to hide the implementation.
"get_next_nocheck": get next node of a queue, the caller ensure that the next node is existed. "get_next": get next node of a queue, it also finds out that whether the next node is existed or not.
Or just remove "cds_wfq_node_sync_next()", use "get_next" instead.
Quoted 12 lines
About
cds_wfq_dequeue_all_blocking(): the "cds_wfq_splice()" I introduced performs the same action as "cds_wfq_dequeue_all_blocking()", but ensures that we can splice lists multiple times (rather than only once), which is a very neat side-effect. Let's imagine a use-case like Tree RCU, where each CPU produce a queue ofcall_rcucallbacks, and we need to merge pairs of queues together recursively until we reach the tree root: by doingsplice()at each level of the tree, we can combine the queues into a single queue without ever needing to do an iteration on each node: no node synchronization is needed until we actually need to traverse the queue at the root node level.
Quoted 7 lines
The cost of exposing
dequeue_allis that we need to exposesync_next(more complexity for the user). As you exposed in your earlier email, the gain we get by exposingdequeue_allseparately from splice is thatdequeue_allis 1xchg()operation, while splice is 2xchg()operations. However, given that this operation is typically amortized over many nodes makes performance optimization a less compelling argument than simplicity of use.
Reducing the temporary big struct is also my tempt.
---
Related to "internal", see the bottom.
Quoted 9 lines
Quoted 8 lines
5) Add more for_each_*, which default semantic is dequeuing
Reason:__cds_wfq_for_each_blocking_undequeueis enough for undequeuing loops
don't need to add more.
looping and dequeuing are the most probable use-cases.
dequeuing for_each_* make the queue like a pipe. make it act as a channel.(GO language)
Alternative: rename these dequeuing __cds_wfq_for_each*() to __cds_wfq_dequeue_for_each*
Quoted 6 lines
I notice, in the iterators you added, the presence of "
cds_wfq_for_each_blocking_nobreak", and "cds_wfq_for_each_blocking_nobreak_internal", which document that this special flavor is needed for loops that do not have a "break" statement. That seems to be very much error-prone and counter-intuitive for users, and I would like to avoid that.
__cds_wfq_for_each_blocking_safe(remove-all) is also "no-break"(*), is it error-prone and ...?
So this is not a good reason to reject cds_wfq_for_each_blocking_nobreak(), if the user don't know how to use it, he should use cds_wfq_for_each_blocking() (the version in my patch which is dequeue()-based and we can break from the loop body)
__cds_wfq_for_each_blocking_safe() and cds_wfq_for_each_blocking_nobreak() are exactly the same semantic in "remove-all" and "no-break". but cds_wfq_for_each_blocking_nobreak() does NOT CORRUPT the queue.
So cds_wfq_for_each_blocking_nobreak() is yet another __cds_wfq_for_each_blocking_safe() and it don't corrupt the queue, it is really safer than __cds_wfq_for_each_blocking_safe().
""""footnote: (*)__cds_wfq_for_each_blocking_safe() should be used for "remove-none" or "remove-all"
We should use __cds_wfq_for_each_blocking_undequeue() instead of __cds_wfq_for_each_blocking_safe(remove-none) """
Quoted 12 lines
The "internal" flavor, along with "
sync_next" are then used in thecall_rcucode, since they are needed to get the best performance possible. I don't like to use special, internal APIs forcall_rcu: the original motivation for refactoring the wfqueue code was testability, and I would really like to make sure that the APIs we use internally are also exposed to the outside world, mainly for testability, and also because if we need to directly access internal interfaces to have good performance, it means we did a poor job at exporting APIs that allow to do the same kind of highly-efficient use of the queue. Exposing an API with the "internal" keyword in it clearly discourages users from using it.
Related to "internal" see the bottom.
Quoted 21 lines
Quoted 7 lines
6) Remove
__cds_wfq_for_each_blocking_safe
Reason: its semantic is not clear, hard to define a well-defined semantic to it.
when we use it, we have to delete none or delete all nodes, even when we delete all nodes, structcds_wfq_queuestill becomes stale while looping or after loop.The typical use-case I envision is:
- enqueue many nodes to queue A
- then, a dequeuer thread splice the content of queue A into its temporary queue T (which head is local on its stack).
- now, the thread is free to iterate on queue T, as many times as it likes, and it does not need to change the structure of the queue while iterating on it (read-only operation, without side-effect). The last time it iterates on queue T, it needs to use the
_safeiteration and free the nodes.
Quoted 3 lines
- after the nodes have been deleted, the queue T can be simply discarded (if on stack, function return will do so; if dynamically allocated, can be simply reinitialized to an empty queue, or freed).
My for_each_*() can do exactly the same thing in this use-case since we still have splice() and cds_wfq_for_each_blocking_nobreak()(safer **_safe()). Doesn't it?
The memory represented a struct queue is big.(two cache line), something we need to avoid to use it in the stack.(shorten the stack size or avoid to cost 2 or 3 additional cache line).
-----------a use case
All these local field are hot in the stack(and for some reason, it is not in the registers)
int count; struct cds_wfq_queue tmp; struct cds_wfq_node *node, *next;
It will use 4 cache line. Should we always recommend the users use splice()+tmp?
Quoted 23 lines
As you certainly noticed, we can iterate both on a queue being concurrently enqueued to, and on a queue that has been spliced into. Being able to use iterators and dequeue on any queue (initial enqueue, or queue spliced to) is a feature: we can therefore postpone the "
sync_next" synchronization to the moment where loop iteration is really needed (lazy synchronization), which keeps optimal locality of reference of synchronization vs node data access.Quoted 3 lines
7) Rename old
__cds_wfq_for_each_blocking()to__cds_wfq_for_each_blocking_undequeue()
Reason: the default semantic of the other for_each_* is dequeuing.I'm not convinced that "
__cds_wfq_for_each_blocking_nobreak", "__cds_wfq_for_each_blocking_nobreak_internal", andsync_nextAPIs are improvements over the API I propose. Forcall_rcu, this turns
cds_wfq_enqueue()cds_wfq_splice_blocking()__cds_wfq_for_each_blocking_safe()for iterationinto:
Quoted 9 lines
cds_wfq_enqueue()__cds_wfq_dequeue_all_blocking()__cds_wfq_for_each_blocking_nobreak_internal()for iterationMaybe we could do some documentation improvement to "
__cds_wfq_for_each_blocking(_safe)",__cds_wfq_first_blocking(),__cds_wfq_next_blocking()API members I proposed. Maybe I did not document them well enough ?
It does be not enough for __cds_wfq_for_each_blocking_safe().
I *STRONGLY OPPOSE* __cds_wfq_for_each_blocking_safe()(although it is suggested by me).
If you oppose the dequeue_all(), I agreed with this list:
Remove old __cds_wfq_for_each_blocking_safe()
Use manual splice()+get_first()+get_next() for call_rcu_thread(). Remove my proposed cds_wfq_for_each_blocking_nobreak() Remove my proposed sync_next(), dequeue_all().
Keep dequeue-based for_each() (alternative: introduce it in future)
If you also agreed this list, could you please partially merge my patch to your patch and send it for review to reduce the review cycle. (don't forget the other minimal fixes in my patch)
==========
About internals:
I want to expose the for_each_*, I don't want to expose these helpers:
cds_wfq_node_sync_next() cds_wfq_dequeue_all_blocking() __cds_wfq_dequeue_all_blocking() __cds_wfq_for_each_blocking_nobreak_internal()
(and I want to disallow the users use these helpers directly).
but the for_each_* use these helpers, so I have to declare it in the urcu/wfqueue.h, and they become a part of ABI.
So these helpers become internal things, how to handle internal things in a exposed *.h?
I found "__cds_list_del()" and "__tls_access_ ## name ()" are also internals, and they are exposed. Are they exposed correctly?
In my view, exposed internals is OK, what we can do is disallowing the users use it directly and ensuring the compatibility.
And we don't need to test exposed internals directly via testcases, because they are internals, just like we don't need to test so much un-exposed internals. When we test the exposed API, the internals will be also tested.
The call_rcu_thread() use the internal directly and can't be tested as you mentioned. It is not totally true. call_rcu_thread() need to inject a "synchronize_rcu()" to __cds_wfq_for_each_blocking_nobreak(), so I have to use __cds_wfq_for_each_blocking_nobreak_internal().
Tests for __cds_wfq_for_each_blocking_nobreak() are enough for call_rcu_thread().
In one word, I don't agreed full of your disgust to the exposed internals, but I agree to remove the ones introduced in my patch.
Thanks,
Lai
A message that is not in the archive (sent off-list or not yet received): [email protected]
ping
Quoted 264 lines · Lai Jiangshan
Quoted 42 lines · Mathieu Desnoyers
Quoted 6 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 4 lines · Mathieu Desnoyers
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)Hi Lai,
Quoted 8 lines
Hi, Mathieu
please add this part to your patch.
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preferenceIs this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
Quoted 2 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readabilityYes, I agree with this change. Can you extract it into a separate patch ?
Quoted 5 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIsI agree with this change too. You can put it into the same patch as (2).
Quoted 3 lines
4) Add
cds_wfq_node_sync_next(),cds_wfq_dequeue_all_blocking()
Reason: helper for for_each_*Points 4-5-6-7 will need more discussion.
Quoted 9 lines
I don't like exposing "
cds_wfq_node_sync_next()", which should remain an internal implementation detail not exposed to queue users. The "get_first"/"get_next" API, as well as the dequeue, are providing an abstraction that hide the node synchronization, which makes it harder for the user to make mistakes. Given that the fast-path ofcds_wfq_node_sync_nextis just a pointer load and test, I don't think that skipping this the second time we iterate on the same queue would bring any significant performance improvement, but exposingsync_nextadds in API complexity, which I would like to avoid.If the name "
cds_wfq_node_sync_next()" is bad and exposes the implementation, we can rename it to "__cds_wfq_next_blocking_nocheck()" to hide the implementation."
get_next_nocheck": get next node of a queue, the caller ensure that the next node is existed. "get_next": get next node of a queue, it also finds out that whether the next node is existed or not.Or just remove "
cds_wfq_node_sync_next()", use "get_next" instead.Quoted 12 lines
About
cds_wfq_dequeue_all_blocking(): the "cds_wfq_splice()" I introduced performs the same action as "cds_wfq_dequeue_all_blocking()", but ensures that we can splice lists multiple times (rather than only once), which is a very neat side-effect. Let's imagine a use-case like Tree RCU, where each CPU produce a queue ofcall_rcucallbacks, and we need to merge pairs of queues together recursively until we reach the tree root: by doingsplice()at each level of the tree, we can combine the queues into a single queue without ever needing to do an iteration on each node: no node synchronization is needed until we actually need to traverse the queue at the root node level.Quoted 7 lines
The cost of exposing
dequeue_allis that we need to exposesync_next(more complexity for the user). As you exposed in your earlier email, the gain we get by exposingdequeue_allseparately from splice is thatdequeue_allis 1xchg()operation, while splice is 2xchg()operations. However, given that this operation is typically amortized over many nodes makes performance optimization a less compelling argument than simplicity of use.Reducing the temporary big struct is also my tempt.
---
Related to "internal", see the bottom.Quoted 9 lines
Quoted 8 lines
5) Add more for_each_*, which default semantic is dequeuing
Reason:__cds_wfq_for_each_blocking_undequeueis enough for undequeuing loops
don't need to add more.
looping and dequeuing are the most probable use-cases.
dequeuing for_each_* make the queue like a pipe. make it act as a channel.(GO language)
Alternative: rename these dequeuing __cds_wfq_for_each*() to __cds_wfq_dequeue_for_each*Quoted 6 lines
I notice, in the iterators you added, the presence of "
cds_wfq_for_each_blocking_nobreak", and "cds_wfq_for_each_blocking_nobreak_internal", which document that this special flavor is needed for loops that do not have a "break" statement. That seems to be very much error-prone and counter-intuitive for users, and I would like to avoid that.
__cds_wfq_for_each_blocking_safe(remove-all)is also "no-break"(*), is it error-prone and ...?So this is not a good reason to reject
cds_wfq_for_each_blocking_nobreak(), if the user don't know how to use it, he should usecds_wfq_for_each_blocking()(the version in my patch which is dequeue()-based and we can break from the loop body)
__cds_wfq_for_each_blocking_safe()andcds_wfq_for_each_blocking_nobreak()are exactly the same semantic in "remove-all" and "no-break". butcds_wfq_for_each_blocking_nobreak()does NOT CORRUPT the queue.So
cds_wfq_for_each_blocking_nobreak()is yet another__cds_wfq_for_each_blocking_safe()and it don't corrupt the queue, it is really safer than__cds_wfq_for_each_blocking_safe().""""footnote: (*)
__cds_wfq_for_each_blocking_safe()should be used for "remove-none" or "remove-all"
We should use__cds_wfq_for_each_blocking_undequeue()instead of__cds_wfq_for_each_blocking_safe(remove-none)"""Quoted 12 lines
The "internal" flavor, along with "
sync_next" are then used in thecall_rcucode, since they are needed to get the best performance possible. I don't like to use special, internal APIs forcall_rcu: the original motivation for refactoring the wfqueue code was testability, and I would really like to make sure that the APIs we use internally are also exposed to the outside world, mainly for testability, and also because if we need to directly access internal interfaces to have good performance, it means we did a poor job at exporting APIs that allow to do the same kind of highly-efficient use of the queue. Exposing an API with the "internal" keyword in it clearly discourages users from using it.Related to "internal" see the bottom.
Quoted 21 lines
Quoted 7 lines
6) Remove
__cds_wfq_for_each_blocking_safe
Reason: its semantic is not clear, hard to define a well-defined semantic to it.
when we use it, we have to delete none or delete all nodes, even when we delete all nodes, structcds_wfq_queuestill becomes stale while looping or after loop.The typical use-case I envision is:
- enqueue many nodes to queue A
- then, a dequeuer thread splice the content of queue A into its temporary queue T (which head is local on its stack).
- now, the thread is free to iterate on queue T, as many times as it likes, and it does not need to change the structure of the queue while iterating on it (read-only operation, without side-effect). The last time it iterates on queue T, it needs to use the
_safeiteration and free the nodes.Quoted 3 lines
- after the nodes have been deleted, the queue T can be simply discarded (if on stack, function return will do so; if dynamically allocated, can be simply reinitialized to an empty queue, or freed).
My for_each_*() can do exactly the same thing in this use-case since we still have
splice()and cds_wfq_for_each_blocking_nobreak()(safer **_safe()). Doesn't it?The memory represented a struct queue is big.(two cache line), something we need to avoid to use it in the stack.(shorten the stack size or avoid to cost 2 or 3 additional cache line).
-----------a use case
All these local field are hot in thestack(and for some reason, it is not in the registers)int count; struct cds_wfq_queue tmp; struct cds_wfq_node *node, *next;It will use 4 cache line. Should we always recommend the users use splice()+tmp?
Quoted 23 lines
As you certainly noticed, we can iterate both on a queue being concurrently enqueued to, and on a queue that has been spliced into. Being able to use iterators and dequeue on any queue (initial enqueue, or queue spliced to) is a feature: we can therefore postpone the "
sync_next" synchronization to the moment where loop iteration is really needed (lazy synchronization), which keeps optimal locality of reference of synchronization vs node data access.Quoted 3 lines
7) Rename old
__cds_wfq_for_each_blocking()to__cds_wfq_for_each_blocking_undequeue()
Reason: the default semantic of the other for_each_* is dequeuing.I'm not convinced that "
__cds_wfq_for_each_blocking_nobreak", "__cds_wfq_for_each_blocking_nobreak_internal", andsync_nextAPIs are improvements over the API I propose. Forcall_rcu, this turns
cds_wfq_enqueue()cds_wfq_splice_blocking()__cds_wfq_for_each_blocking_safe()for iterationinto:
Quoted 9 lines
cds_wfq_enqueue()__cds_wfq_dequeue_all_blocking()__cds_wfq_for_each_blocking_nobreak_internal()for iterationMaybe we could do some documentation improvement to "
__cds_wfq_for_each_blocking(_safe)",__cds_wfq_first_blocking(),__cds_wfq_next_blocking()API members I proposed. Maybe I did not document them well enough ?It does be not enough for
__cds_wfq_for_each_blocking_safe().I *STRONGLY OPPOSE* __cds_wfq_for_each_blocking_safe()(although it is suggested by me).
If you oppose the
dequeue_all(), I agreed with this list:
Remove old__cds_wfq_for_each_blocking_safe()
Use manual splice()+get_first()+get_next() forcall_rcu_thread(). Remove my proposedcds_wfq_for_each_blocking_nobreak()Remove my proposedsync_next(),dequeue_all().
Keep dequeue-basedfor_each()(alternative: introduce it in future)If you also agreed this list, could you please partially merge my patch to your patch and send it for review to reduce the review cycle. (don't forget the other minimal fixes in my patch)
==========
About internals:I want to expose the for_each_*, I don't want to expose these helpers:
cds_wfq_node_sync_next()cds_wfq_dequeue_all_blocking()__cds_wfq_dequeue_all_blocking()__cds_wfq_for_each_blocking_nobreak_internal()
(and I want to disallow the users use these helpers directly).but the for_each_* use these helpers, so I have to declare it in the
urcu/wfqueue.h, and they become a part of ABI.So these helpers become internal things, how to handle internal things in a exposed *.h?
I found "
__cds_list_del()" and "__tls_access_## name ()" are also internals, and they are exposed. Are they exposed correctly?In my view, exposed internals is OK, what we can do is disallowing the users use it directly and ensuring the compatibility.
And we don't need to test exposed internals directly via testcases, because they are internals, just like we don't need to test so much un-exposed internals. When we test the exposed API, the internals will be also tested.
The
call_rcu_thread()use the internal directly and can't be tested as you mentioned. It is not totally true.call_rcu_thread()need to inject a "synchronize_rcu()" to__cds_wfq_for_each_blocking_nobreak(), so I have to use__cds_wfq_for_each_blocking_nobreak_internal().
Tests for__cds_wfq_for_each_blocking_nobreak()are enough forcall_rcu_thread().In one word, I don't agreed full of your disgust to the exposed internals, but I agree to remove the ones introduced in my patch.
Thanks,
Lai_______________________________________________
lttng-dev mailing list
[email protected]
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 1 line · * Lai Jiangshan ([email protected]) wrote:
ping
we discussed a "batch" design offline. Do you think you would have time to spin a patch implementing it ?
Thanks,
Mathieu
Quoted 267 lines · Lai Jiangshan
Quoted 264 lines · Mathieu Desnoyers
Quoted 42 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 6 lines · Mathieu Desnoyers
Quoted 4 lines
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)Hi Lai,
Quoted 8 lines
Hi, Mathieu
please add this part to your patch.
Changes(item5 has alternative):
1) Reorder the head and the tail in struct
cds_wfq_queue
Reason: wfq is enqueue-preferenceIs this a technical improvement over the original order ? Both cache lines are aligned, so it should not matter which one comes first. So I'm not sure why we should favor one order vs the other.
Quoted 2 lines
2) Reorder the code of
___cds_wfq_next_blocking()
Reason: short code, better readabilityYes, I agree with this change. Can you extract it into a separate patch ?
Quoted 5 lines
3) Add cds_wfq_dequeue_[un]lock
Reason: the fields of structcds_wfq_queueare not exposed to users of lib,
but some APIs needs to have this lock held. Add this locking function to allow the users use such APIsI agree with this change too. You can put it into the same patch as (2).
Quoted 3 lines
4) Add
cds_wfq_node_sync_next(),cds_wfq_dequeue_all_blocking()
Reason: helper for for_each_*Points 4-5-6-7 will need more discussion.
Quoted 9 lines
I don't like exposing "
cds_wfq_node_sync_next()", which should remain an internal implementation detail not exposed to queue users. The "get_first"/"get_next" API, as well as the dequeue, are providing an abstraction that hide the node synchronization, which makes it harder for the user to make mistakes. Given that the fast-path ofcds_wfq_node_sync_nextis just a pointer load and test, I don't think that skipping this the second time we iterate on the same queue would bring any significant performance improvement, but exposingsync_nextadds in API complexity, which I would like to avoid.If the name "
cds_wfq_node_sync_next()" is bad and exposes the implementation, we can rename it to "__cds_wfq_next_blocking_nocheck()" to hide the implementation."
get_next_nocheck": get next node of a queue, the caller ensure that the next node is existed. "get_next": get next node of a queue, it also finds out that whether the next node is existed or not.Or just remove "
cds_wfq_node_sync_next()", use "get_next" instead.Quoted 12 lines
About
cds_wfq_dequeue_all_blocking(): the "cds_wfq_splice()" I introduced performs the same action as "cds_wfq_dequeue_all_blocking()", but ensures that we can splice lists multiple times (rather than only once), which is a very neat side-effect. Let's imagine a use-case like Tree RCU, where each CPU produce a queue ofcall_rcucallbacks, and we need to merge pairs of queues together recursively until we reach the tree root: by doingsplice()at each level of the tree, we can combine the queues into a single queue without ever needing to do an iteration on each node: no node synchronization is needed until we actually need to traverse the queue at the root node level.Quoted 7 lines
The cost of exposing
dequeue_allis that we need to exposesync_next(more complexity for the user). As you exposed in your earlier email, the gain we get by exposingdequeue_allseparately from splice is thatdequeue_allis 1xchg()operation, while splice is 2xchg()operations. However, given that this operation is typically amortized over many nodes makes performance optimization a less compelling argument than simplicity of use.Reducing the temporary big struct is also my tempt.
---
Related to "internal", see the bottom.Quoted 9 lines
Quoted 8 lines
5) Add more for_each_*, which default semantic is dequeuing
Reason:__cds_wfq_for_each_blocking_undequeueis enough for undequeuing loops
don't need to add more.
looping and dequeuing are the most probable use-cases.
dequeuing for_each_* make the queue like a pipe. make it act as a channel.(GO language)
Alternative: rename these dequeuing __cds_wfq_for_each*() to __cds_wfq_dequeue_for_each*Quoted 6 lines
I notice, in the iterators you added, the presence of "
cds_wfq_for_each_blocking_nobreak", and "cds_wfq_for_each_blocking_nobreak_internal", which document that this special flavor is needed for loops that do not have a "break" statement. That seems to be very much error-prone and counter-intuitive for users, and I would like to avoid that.
__cds_wfq_for_each_blocking_safe(remove-all)is also "no-break"(*), is it error-prone and ...?So this is not a good reason to reject
cds_wfq_for_each_blocking_nobreak(), if the user don't know how to use it, he should usecds_wfq_for_each_blocking()(the version in my patch which is dequeue()-based and we can break from the loop body)
__cds_wfq_for_each_blocking_safe()andcds_wfq_for_each_blocking_nobreak()are exactly the same semantic in "remove-all" and "no-break". butcds_wfq_for_each_blocking_nobreak()does NOT CORRUPT the queue.So
cds_wfq_for_each_blocking_nobreak()is yet another__cds_wfq_for_each_blocking_safe()and it don't corrupt the queue, it is really safer than__cds_wfq_for_each_blocking_safe().""""footnote: (*)
__cds_wfq_for_each_blocking_safe()should be used for "remove-none" or "remove-all"
We should use__cds_wfq_for_each_blocking_undequeue()instead of__cds_wfq_for_each_blocking_safe(remove-none)"""Quoted 12 lines
The "internal" flavor, along with "
sync_next" are then used in thecall_rcucode, since they are needed to get the best performance possible. I don't like to use special, internal APIs forcall_rcu: the original motivation for refactoring the wfqueue code was testability, and I would really like to make sure that the APIs we use internally are also exposed to the outside world, mainly for testability, and also because if we need to directly access internal interfaces to have good performance, it means we did a poor job at exporting APIs that allow to do the same kind of highly-efficient use of the queue. Exposing an API with the "internal" keyword in it clearly discourages users from using it.Related to "internal" see the bottom.
Quoted 21 lines
Quoted 7 lines
6) Remove
__cds_wfq_for_each_blocking_safe
Reason: its semantic is not clear, hard to define a well-defined semantic to it.
when we use it, we have to delete none or delete all nodes, even when we delete all nodes, structcds_wfq_queuestill becomes stale while looping or after loop.The typical use-case I envision is:
- enqueue many nodes to queue A
- then, a dequeuer thread splice the content of queue A into its temporary queue T (which head is local on its stack).
- now, the thread is free to iterate on queue T, as many times as it likes, and it does not need to change the structure of the queue while iterating on it (read-only operation, without side-effect). The last time it iterates on queue T, it needs to use the
_safeiteration and free the nodes.Quoted 3 lines
- after the nodes have been deleted, the queue T can be simply discarded (if on stack, function return will do so; if dynamically allocated, can be simply reinitialized to an empty queue, or freed).
My for_each_*() can do exactly the same thing in this use-case since we still have
splice()and cds_wfq_for_each_blocking_nobreak()(safer **_safe()). Doesn't it?The memory represented a struct queue is big.(two cache line), something we need to avoid to use it in the stack.(shorten the stack size or avoid to cost 2 or 3 additional cache line).
-----------a use case
All these local field are hot in thestack(and for some reason, it is not in the registers)int count; struct cds_wfq_queue tmp; struct cds_wfq_node *node, *next;It will use 4 cache line. Should we always recommend the users use splice()+tmp?
Quoted 23 lines
As you certainly noticed, we can iterate both on a queue being concurrently enqueued to, and on a queue that has been spliced into. Being able to use iterators and dequeue on any queue (initial enqueue, or queue spliced to) is a feature: we can therefore postpone the "
sync_next" synchronization to the moment where loop iteration is really needed (lazy synchronization), which keeps optimal locality of reference of synchronization vs node data access.Quoted 3 lines
7) Rename old
__cds_wfq_for_each_blocking()to__cds_wfq_for_each_blocking_undequeue()
Reason: the default semantic of the other for_each_* is dequeuing.I'm not convinced that "
__cds_wfq_for_each_blocking_nobreak", "__cds_wfq_for_each_blocking_nobreak_internal", andsync_nextAPIs are improvements over the API I propose. Forcall_rcu, this turns
cds_wfq_enqueue()cds_wfq_splice_blocking()__cds_wfq_for_each_blocking_safe()for iterationinto:
Quoted 9 lines
cds_wfq_enqueue()__cds_wfq_dequeue_all_blocking()__cds_wfq_for_each_blocking_nobreak_internal()for iterationMaybe we could do some documentation improvement to "
__cds_wfq_for_each_blocking(_safe)",__cds_wfq_first_blocking(),__cds_wfq_next_blocking()API members I proposed. Maybe I did not document them well enough ?It does be not enough for
__cds_wfq_for_each_blocking_safe().I *STRONGLY OPPOSE* __cds_wfq_for_each_blocking_safe()(although it is suggested by me).
If you oppose the
dequeue_all(), I agreed with this list:
Remove old__cds_wfq_for_each_blocking_safe()
Use manual splice()+get_first()+get_next() forcall_rcu_thread(). Remove my proposedcds_wfq_for_each_blocking_nobreak()Remove my proposedsync_next(),dequeue_all().
Keep dequeue-basedfor_each()(alternative: introduce it in future)If you also agreed this list, could you please partially merge my patch to your patch and send it for review to reduce the review cycle. (don't forget the other minimal fixes in my patch)
==========
About internals:I want to expose the for_each_*, I don't want to expose these helpers:
cds_wfq_node_sync_next()cds_wfq_dequeue_all_blocking()__cds_wfq_dequeue_all_blocking()__cds_wfq_for_each_blocking_nobreak_internal()
(and I want to disallow the users use these helpers directly).but the for_each_* use these helpers, so I have to declare it in the
urcu/wfqueue.h, and they become a part of ABI.So these helpers become internal things, how to handle internal things in a exposed *.h?
I found "
__cds_list_del()" and "__tls_access_## name ()" are also internals, and they are exposed. Are they exposed correctly?In my view, exposed internals is OK, what we can do is disallowing the users use it directly and ensuring the compatibility.
And we don't need to test exposed internals directly via testcases, because they are internals, just like we don't need to test so much un-exposed internals. When we test the exposed API, the internals will be also tested.
The
call_rcu_thread()use the internal directly and can't be tested as you mentioned. It is not totally true.call_rcu_thread()need to inject a "synchronize_rcu()" to__cds_wfq_for_each_blocking_nobreak(), so I have to use__cds_wfq_for_each_blocking_nobreak_internal().
Tests for__cds_wfq_for_each_blocking_nobreak()are enough forcall_rcu_thread().In one word, I don't agreed full of your disgust to the exposed internals, but I agree to remove the ones introduced in my patch.
Thanks,
Lai_______________________________________________
lttng-dev mailing list
[email protected]
http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
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): 20120906134346.GE3630@Krystal
Quoted 6 lines · Mathieu Desnoyers
Quoted 1 line · * Lai Jiangshan ([email protected]) wrote:
ping
we discussed a "batch" design offline. Do you think you would have time to spin a patch implementing it ?
I prefer separated enqueue_struct dequeue_struct a little, so I'm waiting for you.
DEADLOCK!
thanks,
Lai
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 4 lines · * Lai Jiangshan ([email protected]) wrote:
Quoted 3 lines · Mathieu Desnoyers
Quoted 1 line · * Lai Jiangshan ([email protected]) wrote:
ping
Quoted 8 lines
Quoted 3 lines
we discussed a "batch" design offline. Do you think you would have time to spin a patch implementing it ?
I prefer separated
enqueue_structdequeue_structa little, so I'm waiting for you.DEADLOCK!
Hahaha :-)
OK, I'm planning to discuss this with Paul next week, to get a 3rd opinion. I don't want to make choices too quickly for APIs. So meanwhile, let's try to sum up the possible solutions, those I recall are:
1) The current API, with a single struct cds_wfqueue for enqueue and dequeue, with false-sharing between enqueue and dequeue, but on the plus side it provides a compact structure to put on the stack.
2) An API with cache-aligned fields of struct cds_wfqueue for enqueue and dequeue. Removes false-sharing, but requires a larger structure when extracted onto the stack with our new splice operation.
3) An API with two different queue representations: a "queue" and a "batch". The "queue" is bullet (2) above, and when we splice elements onto the stack, we put them in a "batch", described by bullet (1) above.
4) An API that takes separate enqueue/dequeue structures: it would allow the caller to decide the memory layout of those structures. We could possibly provide macros helpers for the common cases. E.g.
struct cds_enq {
struct cds_wfq_node *tail;
};
struct cds_deq {
struct cds_wfq_node head;
pthread_mutex_t lock;
};
#define DEFINE_CDS_Q_ON_STACK(q) \
struct wfenqueue __cds_wfqenqueue_##q = { NULL }; \
struct wfdequeue __cds_wfqdequeue_##q = \
{ { NULL }, PTHREAD_MUTEX_INITIALIZER, }/* For queue head/tail in data */
#define DEFINE_CDS_Q(q) \
struct cds_enq __cds_enq_##q \
__attribute__((aligned((CAA_CACHE_LINE_SIZE)))) \
= { NULL }; \
struct cds_deq __cds_deq_##q \
__attribute__((aligned((CAA_CACHE_LINE_SIZE)))) \
= { { NULL }, PTHREAD_MUTEX_INITIALIZER, }And for dynamic allocation, then the user could specify the alignment they want for their allocated memory (not sure it is worth it to do helpers for that).
#define CDS_Q(q) __cds_enq_##q, __cds_deq_##q
Then, when those structures would be passed to enqueue/dequeue:
static DEFINE_CDS_Q(myqueue);
void fct(void) {
...
cds_wfq_enqueue(CDS_Q(myqueue), somenode);
}
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