* Re: Coding blog: lockless queues
[not found] <20130110165942.GA5133@Krystal>
@ 2013-01-21 22:59 ` Rusty Russell
0 siblings, 0 replies; 2+ messages in thread
From: Rusty Russell @ 2013-01-21 22:59 UTC (permalink / raw)
To: Mathieu Desnoyers
Cc: rp, lttng-dev, Alan Stern, Stephen Hemminger, Paul E. McKenney
Mathieu Desnoyers <mathieu.desnoyers@efficios.com> writes:
> Hi Rusty!
>
> I've stumbled on your blog post: http://rusty.ozlabs.org/?p=317
>
> and I find that you looked at the RCU lock-free queue implementation in
> the Userspace RCU project, but not at the wait-free concurrent queue
> implementation we have (wait-free enqueue, blocking dequeue), which does
> not require RCU at all and might be a much better fit for what you are
> trying to achieve.
Clearly, I stopped reading too early! It's a very nice
implementation...
If I revisit this, I'll do a code review and post it on my blog.
Thanks!
Rusty.
^ permalink raw reply [flat|nested] 2+ messages in thread
* Coding blog: lockless queues
@ 2013-01-10 16:59 Mathieu Desnoyers
0 siblings, 0 replies; 2+ messages in thread
From: Mathieu Desnoyers @ 2013-01-10 16:59 UTC (permalink / raw)
To: Rusty Russell
Cc: rp, lttng-dev, Alan Stern, Stephen Hemminger, Paul E. McKenney
Hi Rusty!
I've stumbled on your blog post: http://rusty.ozlabs.org/?p=317
and I find that you looked at the RCU lock-free queue implementation in
the Userspace RCU project, but not at the wait-free concurrent queue
implementation we have (wait-free enqueue, blocking dequeue), which does
not require RCU at all and might be a much better fit for what you are
trying to achieve.
A quick pointer to the implementation:
git://git.lttng.org/userspace-rcu.git master branch
files:
urcu/wfcqueue.h (public API)
urcu/static/wfcqueue.h (API implementation)
(https://git.lttng.org/?p=userspace-rcu.git;a=blob;f=urcu/static/wfcqueue.h;h=4b3535aaa83207a4f4eb801dc63150bef8f28bbc;hb=HEAD)
Some nice features of this wfcqueue is to allow this:
- enqueue is wait-free (uses xchg() and store),
- splice (a kind of dequeue_all) from queue is only needs mutual
exclusion with other dequeue, but not with other splice. We call it
"blocking" because it may have to busy-wait if enqueue is preempted
between xchg and store,
- synchronization needed when iterating on the queue (so we wait for
store to complete if we reach a node being enqueued) is performed
at the very last moment where it is needed: this is why we provide
"first" and "next" iterators.
- we also support "dequeue", to dequeue nodes one by one. The dequeue
operation needs mutual exclusion against other dequeue acting on that
queue (and against first/next iterators).
I'd be very interested to hear feedback from you on this implementation.
Thanks!
Mathieu
--
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2013-01-22 1:29 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <20130110165942.GA5133@Krystal>
2013-01-21 22:59 ` Coding blog: lockless queues Rusty Russell
2013-01-10 16:59 Mathieu Desnoyers
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.