[lttng-dev] [rp] [URCU PATCH 0/3] wait-free concurrent queues (wfcqueue)

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Tue, Oct 02, 2012 at 10:13:07AM -0400, Mathieu Desnoyers wrote:
> > Implement wait-free concurrent queues, with a new API different from
> > wfqueue.h, which is already provided by Userspace RCU. The advantage of
> > splitting the head and tail objects of the queue into different
> > arguments is to allow these to sit on different cache-lines, thus
> > eliminating false-sharing, leading to a 2.3x speed increase.
> > 
> > This API also introduces a "splice" operation, which moves all nodes
> > from one queue into another, and postpones the synchronization to either
> > dequeue or iteration on the list. The splice operation does not need to
> > touch every single node of the queue it moves them from. Moreover, the
> > splice operation only needs to ensure mutual exclusion with other
> > dequeuers, iterations, and splice operations from the list it splices
> > from, but acts as a simple enqueuer on the list it splices into (no
> > mutual exclusion needed for that list).
> > 
> > Feedback is welcome,
> 
> These look sane to me, though I must confess that the tail pointer
> referencing the node rather than the node's next pointer did throw
> me for a bit.  ;-)

Yes, this was originally introduced with Lai's original patch to
wfqueue, which I think is a nice simplification: it's pretty much the
same thing to use the last node address as tail rather than the address
of its first member (its next pointer address (_not_ value)). It ends up
being the same address in this case, but more interestingly, we don't
have to use a struct cds_wfcq_node ** type: a simple struct
cds_wfcq_node *  suffice.

Thanks Paul, I will therefore merge these 3 patches with your Acked-by.

Lai, you are welcome to provide improvements to this code against the
master branch. I will gladly consider any change you propose.

Thanks!

Mathieu

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com