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

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

[Mathieu Desnoyers]

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:

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

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

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.

Thoughts ?

Thanks,

Mathieu

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

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

[Paul E. McKenney]

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.  ;-)

> 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.

> 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.  ;-)

> 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?

							Thanx, Paul

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

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

[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

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

[Paul E. McKenney]

On Wed, Oct 17, 2012 at 11:19:46AM -0400, Mathieu Desnoyers wrote:
> * 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.

Fair enough.  Should enough users protest, we can of course leave them
in place.

> > > 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 ?

I would be in favor of pulling them in -- we can fix if need be.
That said, I am not so sure that getting rid of wfqueue is a good idea,
given your analysis below.

> > > 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 ?

Heh! It would indeed seem that we didn't think through the conversion
from wfqueue as thoroughly as we might have.  ;-)

							Thanx, Paul

> 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
> 

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

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Wed, Oct 17, 2012 at 11:19:46AM -0400, Mathieu Desnoyers wrote:
> > * 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.
> 
> Fair enough.  Should enough users protest, we can of course leave them
> in place.

OK.

> 
> > > > 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 ?
> 
> I would be in favor of pulling them in -- we can fix if need be.
> That said, I am not so sure that getting rid of wfqueue is a good idea,
> given your analysis below.

My analysis below is about rculfqueue, not wfqueue. I think you got both
of them mixed up.

> 
> > > > 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 ?
> 
> Heh! It would indeed seem that we didn't think through the conversion
> from wfqueue as thoroughly as we might have.  ;-)

The transition from wfqueue to wfcqueue does not pose any problem. It's
transition from rculfqueue that is the concern here.

Thanks,

Mathieu

> 
> 							Thanx, Paul
> 
> > 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
> > 
> 
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

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

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

[Mathieu Desnoyers]

* Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > On Wed, Oct 17, 2012 at 11:19:46AM -0400, Mathieu Desnoyers wrote:
> > > * 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.
> > 
> > Fair enough.  Should enough users protest, we can of course leave them
> > in place.
> 
> OK.
> 
> > 
> > > > > 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 ?
> > 
> > I would be in favor of pulling them in -- we can fix if need be.
> > That said, I am not so sure that getting rid of wfqueue is a good idea,
> > given your analysis below.
> 
> My analysis below is about rculfqueue, not wfqueue. I think you got both
> of them mixed up.

I just merged the content of the urcu/wfstack, urcu/lfstack,
urcu/wfcqueue branches into master.

As explained below, urcu/rculfqueue needs more work.

Thanks!

Mathieu

> 
> > 
> > > > > 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 ?
> > 
> > Heh! It would indeed seem that we didn't think through the conversion
> > from wfqueue as thoroughly as we might have.  ;-)
> 
> The transition from wfqueue to wfcqueue does not pose any problem. It's
> transition from rculfqueue that is the concern here.
> 
> Thanks,
> 
> Mathieu
> 
> > 
> > 							Thanx, Paul
> > 
> > > 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
> > > 
> > 
> > 
> > _______________________________________________
> > lttng-dev mailing list
> > lttng-dev at lists.lttng.org
> > http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
> 
> _______________________________________________
> lttng-dev mailing list
> lttng-dev at lists.lttng.org
> http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev

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

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

[Mathieu Desnoyers]

* Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> * Mathieu Desnoyers (mathieu.desnoyers at efficios.com) wrote:
> > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > > On Wed, Oct 17, 2012 at 11:19:46AM -0400, Mathieu Desnoyers wrote:
> > > > * 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.
> > > 
> > > Fair enough.  Should enough users protest, we can of course leave them
> > > in place.
> > 
> > OK.

FYI, wfqueue and rculfstack are now deprecated:

commit 147485105cf7b5c8ea96d7f68df973b9c5a94e8e
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date:   Tue Oct 23 08:43:33 2012 -0400

    Deprecate wfqueue
    
    Replaced by "wfcqueue", which has a semantic that allows placing head
    and tail on different cache lines, and does not allocate memory
    internally. wfqueue users can easily migrate to wfcqueue.
    
    We choose to deprecate wfqueue rather than reimplementing it on top of
    wfcqueue to ensure we keep strong ABI compatibility for existing wfqueue
    users.
    
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

commit d89ec7629b8cafdc12e619cf5f07ceb5b0279275
Author: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
Date:   Tue Oct 23 08:36:42 2012 -0400

    Deprecate rculfstack
    
    Replaced by "lfstack", which has a less restrictive semantic, and covers
    rculfstack completely.
    
    Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers at efficios.com>

wfstack is kept as-is (and has been recently extended with pop_all(),
iterators, and empty() APIs). rculfqueue needs more work. I'd be tempted
not to detail rculfqueue in the upcoming LWN article, but detailing
wfqueue, wfstack and lfstack should be fine.

Thanks!

Mathieu

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