Skip to contentSkip to conversation

wfcqueue: implement __wfcq_enqueue_head() (v2)

RFC PATCH In review Mathieu Desnoyers 2 participants 3 messages Apr 6, 2013 – Apr 7, 2013

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 wfcqueue: implement __wfcq_enqueue_head() (v2)

Implement enqueue-to-head. It can run concurrently with enqueue, splice to queue, and iteration, but requires a mutex against dequeue and splice from queue operations.

Useful for special-cases where a queue needs to have nodes enqueued into its head.

This patch is only compile-tested.

Changes since v1:
* Don't require mutual exclusion between traversals and __wfcq_enqueue_head().

---
 include/linux/wfcqueue.h |   67 ++++++++++++++++++++++++++++++++++++++++++-----
 1 file changed, 60 insertions(+), 7 deletions(-)
include/linux/wfcqueue.h +60 -7
Index: linux/include/linux/wfcqueue.h
===================================================================
@@ -55,14 +55,16 @@
  * [4] __wfcq_splice (source queue)
  * [5] __wfcq_first
  * [6] __wfcq_next
+ * [7] __wfcq_enqueue_head
  *
- *     [1] [2] [3] [4] [5] [6]
- * [1]  -   -   -   -   -   -
- * [2]  -   -   -   -   -   -
- * [3]  -   -   X   X   X   X
- * [4]  -   -   X   -   X   X
- * [5]  -   -   X   X   -   -
- * [6]  -   -   X   X   -   -
+ *     [1] [2] [3] [4] [5] [6] [7]
+ * [1]  -   -   -   -   -   -   -
+ * [2]  -   -   -   -   -   -   X
+ * [3]  -   -   X   X   X   X   X
+ * [4]  -   -   X   -   X   X   X
+ * [5]  -   -   X   X   -   -   -
+ * [6]  -   -   X   X   -   -   -
+ * [7]  -   X   X   X   -   -   X
  *
  * Besides locking, mutual exclusion of dequeue, splice and iteration
  * can be ensured by performing all of those operations from a single
@@ -230,6 +232,57 @@ ___wfcq_node_sync_next(struct wfcq_node
 }
 
 /*
+ * __wfcq_enqueue_head: prepend a node into a queue.
+ *
+ * No memory barriers are issued. Mutual exclusion is the responsibility
+ * of the caller.
+ *
+ * Returns false if the queue was empty prior to adding the node.
+ * Returns true otherwise.
+ */
+static inline bool __wfcq_enqueue_head(struct wfcq_head *head,
+		struct wfcq_tail *tail,
+		struct wfcq_node *node)
+{
+	bool not_empty = 0;
+
+        /*
+	 * Move tail if queue was empty. Tail pointer is the
+	 * linearization point of enqueuers.
+	 */
+	if (cmpxchg(&tail->p, &head->node, node) != &head->node) {
+		not_empty = 1;
+
+		/*
+		 * Queue was non-empty. We need to wait for
+		 * head->node.next to become non-NULL, because a
+		 * concurrent wfcq_append may be updating it.
+		 */
+		CMM_STORE_SHARED(node->next,
+			___wfcq_node_sync_next(&head->node));
+	}
+
+	/*
+	 * If cmpxchg succeeds (queue was empty), tail now points to
+	 * node, but head->node.next is still NULL. Concurrent
+	 * traversals seeing this state will busy-wait until we set
+	 * head->node.next.
+	 *
+	 * Else, if cmpxchg fails (queue was not empty), traversals will
+	 * only see node after we set head->node.next.
+	 */
+
+	/*
+	 * From this point, we know that wfcq_append cannot touch
+	 * head->node.next, either because we successfully moved tail->p
+	 * to node, or because we waited for head->node.next to become
+	 * non-NULL. It is therefore safe to update it.
+	 */
+	CMM_STORE_SHARED(head->node.next, node);
+	return not_empty;
+}
+
+/*
  * __wfcq_first: get first node of a queue, without dequeuing.
  *
  * Content written into the node before enqueue is guaranteed to be
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
Tested-by on v1 1/1
#1 lore raw
Quoted 7 lines · Mathieu Desnoyers

Implement enqueue-to-head. It can run concurrently with enqueue, splice to queue, and iteration, but requires a mutex against dequeue and splice from queue operations.

Useful for special-cases where a queue needs to have nodes enqueued into its head.

Quoted 7 lines

This patch is only compile-tested.

Changes since v1:
* Don't require mutual exclusion between traversals and __wfcq_enqueue_head().

Thanks! The first hunk (sync table comment) conflicted with my __wfcq_enqueue patch, but other than that I could not benchmark any regression with my 4-core machine with v4 of my
"epoll: avoid spinlock contention with wfcqueue" patch.

All I needed was "s/__wfcq_prepend/__wfcq_enqueue_head/g" to my original patch to use the updated API.

I was worried about the cmpxchg at first, but it does not seem to hurt performance on my 4-core system. In fact, it was slightly better (but within margin of error)

time ./eponeshotmt -c 1000000 -w 4 -t 4 -f 10

real    0m 5.78s
user    0m 1.20s
sys     0m 21.90s

Hopefully somebody can test my epoll patches with more cores/threads :)

#2 lore raw
Quoted 28 lines · * Eric Wong ([email protected]) wrote:
Quoted 7 lines · Mathieu Desnoyers

Implement enqueue-to-head. It can run concurrently with enqueue, splice to queue, and iteration, but requires a mutex against dequeue and splice from queue operations.

Useful for special-cases where a queue needs to have nodes enqueued into its head.

Quoted 7 lines

This patch is only compile-tested.

Changes since v1:
* Don't require mutual exclusion between traversals and __wfcq_enqueue_head().

Thanks! The first hunk (sync table comment) conflicted with my __wfcq_enqueue patch, but other than that I could not benchmark any regression with my 4-core machine with v4 of my
"epoll: avoid spinlock contention with wfcqueue" patch.

All I needed was "s/__wfcq_prepend/__wfcq_enqueue_head/g" to my original patch to use the updated API.

I was worried about the cmpxchg at first, but it does not seem to hurt performance on my 4-core system. In fact, it was slightly better (but within margin of error)

Quoted 8 lines

time ./eponeshotmt -c 1000000 -w 4 -t 4 -f 10

real    0m 5.78s
user    0m 1.20s
sys     0m 21.90s

Hopefully somebody can test my epoll patches with more cores/threads :)

Thanks for testing. Taking care of your comments, and of memory barriers, brings me to send a v3 of this patch shortly. Testing is welcome!

Thanks,

Mathieu

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com