[lttng-dev] urcu stack and queues updates and documentation

[mathieu.desnoyers@efficios.com (Mathieu Desnoyers)]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Sun, Oct 14, 2012 at 01:53:32PM -0400, Mathieu Desnoyers wrote:
> > Hi Paul!
> > 
> > I know you are currently looking at documentation of urcu data
> > structures. I did quite a bit of work in that area these past days. Here
> > is my plan:
> 
> Actually, I diverted to the atomic operations, given that the stack/queue
> API seems to be in flux.  ;-)

That sounds like a wise decision ;-)

> 
> > 1) I would like to deprecate, at some point, rculfqueue, wfqueue, and
> >    rculfstack.
> > 
> > 2) For wfqueue, we replace it by wfcqueue, currently in the urcu master
> >    branch.
> > 
> > 3) For rculfstack, we replace it by lfstack available here (volatile
> >    branch):
> > 
> > git://git.dorsal.polymtl.ca/~compudj/userspace-rcu
> > branch: urcu/lfstack
> 
> I probably have to document them to have any chance of having an opinion,
> other than my usual advice to avoid disrupting users of the old interfaces.

My general plan is to leave the old interfaces in place, marking them as
"deprecated" by adding a __attribute__((deprecated("This interface is deprecated. Please refer to urcu/xxxqueue.h for its replacement."))).
Then we'll be able to drop the deprecated interfaces in a couple of
versions.

> 
> > 4) I did documentation improvements (and implemented pop_all as well as
> >    empty, and iterators) for wfstack here (volatile branch too):
> > 
> > git://git.dorsal.polymtl.ca/~compudj/userspace-rcu
> > branch: urcu/wfstack
> 
> I will be very happy to take advantage of this.  ;-)

I wonder how we should move forward with these ? I could pull the
urcu/wfstack, urcu/lfstack commits into master with your approval, and
mark rculfstack and wfqueue as deprecated. wfstack is simply extended. I
would wait a bit before deciding anything wrt rculfqueue. Thoughts ?

> 
> > 5) The last one to look into would be rculfqueue. I'd really like to
> >    create a lfcqueue derived from wfcqueue if possible. It's the next
> >    item on my todo list this weekend.
> 
> The piece I am missing is ABA avoidance.  Or is this the approach
> that assumes a single dequeuer?

If we look at the big picture, the main difference between the "wf" and
"lf" approaches, both for stack and queue, is that "wf" requires
traversal to busy-wait when it sees the intermediate NULL pointer state.
This allows wait-free push/enqueue with xchg. The "lf" approach ensures
that a simple traversal can be done on the structures, at the expense of
requiring a cmpxchg on the enqueue/push.

Luckily, for stacks, the nature of stacks makes "push" ABA-proof (see
the documentation in the code), even if we use cmpxchg.

Unluckily, for queues, using cmpxchg on enqueue is ABA-prone. dequeue
is ABA-prone too. Moreover, we need to have existance guarantees, so an
enqueue does not attempt to do a cmpxchg on the next pointer of a node
that has already been dequeued and reallocated. So, one approach is to
always rely on RCU, and require the RCU read-side lock to be held around
enqueue, and around dequeue. Now, the question is: can we rely on other,
non-rcu techniques, to protect lfqueue against ABA and offer existance
guarantees ?

A single-dequeuer approach would unfortunately not be sufficient,
because enqueue is ABA-prone, and due to lack of existance guarantees
for the node we are about to append after: if we have multiple enqueuers
and a single dequeuer, one enqueue could suffer from ABA, and try to
touch reallocated memory, due to dequeue+reallocation of a node.

Even forcing single-enqueuer/single-dequeuer would not suffice: if,
between the moment we get the tail node we plan to append after, and the
moment we perform the cmpxchg to that node next pointer, the node is
dequeued and freed, we would be touching freed memory (corruption).

Therefore, that would require a single mutex on _both_ enqueue and
dequeue operations, which really defeats the purpose of a lock-free
queue.

So my current understanding is that we might have to stay with a RCU
lfcqueue, requiring RCU read-side lock to be held for enqueue and
dequeue, and requiring to wait for a grace period to elapse before
freeing the memory returned by dequeue. The benefit of using rculfcqueue
over wfcqueue is that traversal of the nodes, and dequeue, don't need to
busy-loop on NULL next pointers.

Thoughts ?

Thanks!

Mathieu

> 
> 							Thanx, Paul
> 
> > Thoughts ?
> > 
> > Thanks,
> > 
> > Mathieu
> > 
> > -- 
> > Mathieu Desnoyers
> > Operating System Efficiency R&D Consultant
> > EfficiOS Inc.
> > http://www.efficios.com
> > 
> 

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