Skip to contentSkip to conversation

wfqueue: ABI v1, simplify implementation, 2.3x to 2.6x performance boost

RFC PATCH Mathieu Desnoyers 2 participants 12 messages Aug 17, 2012 – Sep 7, 2012 10 messages not in the archive

lore
Share & tools
lore

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

#1 lore raw

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 update previous->next
2) dequeue: wait for first node's next pointer and them shift, a dummy node

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

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

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

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

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

Quoted 2 lines

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

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

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

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

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

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

Before patch:

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

After patch:

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

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

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

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

* 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_queue structures between the two. The only way to run into this corner-case would be to combine objects compiled with different versions of the urcu/wfqueue.h header.

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

---

Makefile.am +1 -1
index 2396fcf..31052ef 100644
@@ -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.la
urcu-call-rcu-impl.h +24 -36
index 13b24ff..d8537d0 100644
@@ -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
index 636e1af..52e452d 100644
@@ -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 __cplusplus
urcu/wfqueue.h +102 -15
index 03a73f1..446c94c 100644
@@ -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 __cplusplus
 extern "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
index 3337171..b5fba7b 100644
@@ -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
#2 lore raw
In reply to a message not in the archive
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
index d8537d0..061c2d4 100644
@@ -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
index b5fba7b..eee1fd8 100644
@@ -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]

#4 lore raw
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 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

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

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, struct cds_wfq_queue still 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
index d8537d0..061c2d4 100644
@@ -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
index 52e452d..e5a01ec 100644
@@ -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 __cplusplus
urcu/wfqueue.h +113 -41
index 446c94c..a3627ac 100644
@@ -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
index b5fba7b..eee1fd8 100644
@@ -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

#6 lore raw
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-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.

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 readability

Yes, 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 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

I 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]

#8 lore raw
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-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.

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.

Quoted 7 lines

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.

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 readability

Yes, 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 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

I 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

#10 lore raw
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-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.

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.

Quoted 7 lines

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.

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 readability

Yes, 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 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

I 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-volatile

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.

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]

#12 lore raw
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-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.

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.

Quoted 7 lines

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.

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 readability

Yes, 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 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

I 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
#13 lore raw
In reply to a message not in the archive
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-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 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

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.

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

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

Quoted 7 lines

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.

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

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

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, struct cds_wfq_queue still 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.

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", 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:

Quoted 9 lines

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 ?

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]

#15 lore raw

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

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.

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

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

Quoted 7 lines

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.

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

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

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, struct cds_wfq_queue still 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.

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", 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:

Quoted 9 lines

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 ?

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

_______________________________________________
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]

#17 lore raw
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-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 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

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.

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

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

Quoted 7 lines

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.

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

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

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, struct cds_wfq_queue still 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.

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", 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:

Quoted 9 lines

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 ?

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

_______________________________________________
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

#19 lore raw
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]

#21 lore raw
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_struct dequeue_struct a 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