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)Signed-off-by Eric Wong <[email protected]>Cc Mathieu Desnoyers <[email protected]>---
This is on top of my other patch to implement__wfcq_enqueueinclude/linux/wfcqueue.h | 35 +++++++++++++++++++++++++++-------- 1 file changed, 27 insertions(+), 8 deletions(-)include/linux/wfcqueue.h +1
-7@@ -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