Skip to contentSkip to conversation

DISCUSSION Mathieu Desnoyers 1 participant 1 message Apr 6, 2013

lore
Share & tools
lore
#0 lore raw

Bcc:
Subject: Re: [PATCH] wfcqueue: add function for unsynchronized prepend Reply-To:
In-Reply-To: <[email protected]>
X-Editor: vi
X-Info: http://www.efficios.com

Quoted 31 lines · * Eric Wong ([email protected]) wrote:

In some situations, it is necessary to prepend a node to a queue. For epoll, this is necessary for two rare conditions:

* when the user triggers -EFAULT
* when reinjecting elements from the ovflist (implemented as a stack)

Cc Mathieu Desnoyers <[email protected]>

---
This is on top of my other patch to implement __wfcq_enqueue

 include/linux/wfcqueue.h | 35 +++++++++++++++++++++++++++--------
 1 file changed, 27 insertions(+), 8 deletions(-)
include/linux/wfcqueue.h +1 -7
index a452ab9..4cb8f22 100644
@@ -56,15 +56,17 @@
  * [5] __wfcq_first
  * [6] __wfcq_next
  * [7] __wfcq_enqueue
+ * [8] __wfcq_prepend
  *
- *     [1] [2] [3] [4] [5] [6] [7]
- * [1]  -   -   -   -   -   -   X
- * [2]  -   -   -   -   -   -   X
- * [3]  -   -   X   X   X   X   X
- * [4]  -   -   X   -   X   X   X
- * [5]  -   -   X   X   -   -   X
- * [6]  -   -   X   X   -   -   X

include/linux/wfcqueue.h line 69

Quoted 10 lines
include/linux/wfcqueue.h +9 -1
- * [7]  X   X   X   X   X   X   X
+ *     [1] [2] [3] [4] [5] [6] [7] [8]
+ * [1]  -   -   -   -   -   -   X   X
+ * [2]  -   -   -   -   -   -   X   X
+ * [3]  -   -   X   X   X   X   X   X
+ * [4]  -   -   X   -   X   X   X   X
+ * [5]  -   -   X   X   -   -   X   X
+ * [6]  -   -   X   X   -   -   X   X
+ * [7]  X   X   X   X   X   X   X   X
+ * [8]  X   X   X   X   X   X   X   X

I don't think this table is accurate, and there is likely an issue with the implementation below.

AFAIU, you plan to use wait-free enqueue (to tail) concurrently with enqueue to head (prepend). Therefore, the table above should reflect this.

I'll look into this and try to come up with a correct implementation.

Thanks,

Mathieu

Quoted 30 lines
include/linux/wfcqueue.h +17 -0
  *
  * Besides locking, mutual exclusion of dequeue, splice and iteration
  * can be ensured by performing all of those operations from a single
@@ -441,6 +443,23 @@ static inline enum wfcq_ret __wfcq_splice(
 }
 
 /*
+ * __wfcq_prepend: prepend a node into a queue, requiring mutual exclusion.
+ *
+ * No memory barriers are issued.  Mutual exclusion is the responsibility
+ * of the caller.
+ */
+static inline void __wfcq_prepend(struct wfcq_head *head,
+				struct wfcq_tail *tail, struct wfcq_node *node)
+{
+	node->next = head->node.next;
+	head->node.next = node;
+
+	/* if the queue was empty before, it is no longer empty now */
+	if (tail->p == &head->node)
+		tail->p = node;
+}
+
+/*
  * __wfcq_for_each: Iterate over all nodes in a queue,
  * without dequeuing them.
  * @head: head of the queue (struct wfcq_head pointer).
Signature · 1 line
Eric Wong
Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com