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 _______________________________________________ lttng-dev mailing list [email protected] http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
