[ltt-dev] [rp-private] [RFC] Lock-free RCU stack for userspace RCU library
Mathieu Desnoyers
mathieu.desnoyers at efficios.com
Tue Jul 13 11:54:28 EDT 2010
* Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> On Mon, Jul 12, 2010 at 09:50:38PM -0700, Paul E. McKenney wrote:
> > On Mon, Jul 12, 2010 at 08:54:13PM -0400, Mathieu Desnoyers wrote:
> > > * Paul E. McKenney (paulmck at linux.vnet.ibm.com) wrote:
> > > > On Mon, Jul 12, 2010 at 11:50:44AM -0400, Mathieu Desnoyers wrote:
> > > > > Hi,
> > > > >
> > > > > I just did the lock-free stack, which end up being much simpler than the queue
> > > > > because there is no need for dummy head pointer. Comments are welcome.
> > > > >
> > > > > Even though I did not do formal verification of the queue and stack, I feel
> > > > > sufficiently confident to push them in urcu mainline. I'll wait for feedback
> > > > > before cutting a release though. I also created test_urcu_lfq and test_urcu_lfs
> > > > > which will also be in the tree. They perform heavy enqueue/dequeue and push/pop
> > > > > to stress-test the algorithms. They check if the number of operations (e.g. push
> > > > > vs pop) balance.
> > > >
> > > > This one looks OK. You definitely need some comments stating that
> > > > pop() needs to refrain from touching the rcu_lfs_node until after an
> > > > RCU grace period elapses, though. ;-)
> > >
> > > Sure, I'll add this comment. Thanks !
> > >
> > > The discussion we had off-list made me wonder if a wait-free push, blocking pop
> > > implementation would not be better ? Here is the implementation of this variant:
> > >
> > > Thoughts ?
> >
> > Keeping in mind that the only atomic stack I have every used was for
> > a parallel memory allocator...
> >
> > My guess is that different applications would be better served by one
> > or the other. If a workload had a real-time component that did one
> > level of processing, then handed off to a non-real-time component,
> > but the situation was such that getting some of the work done by the
> > non-real-time component immediately was better than getting it all
> > done with a more uniform but longer delay, then your wait-free push
> > blocking pop might be just the ticket.
> >
> > However, if the stack was instead being used to communicate between
> > a pair of real-time components, the earlier implementation that
> > combined lock-free push and pop might be better.
> >
> > Some relatively minor comments below...
> >
> > Thanx, Paul
> >
> > > Thanks!
> > >
> > > Mathieu
> > >
> > > /*
> > > * rcuwfstack.h
> > > *
> > > * Userspace RCU library - RCU Stack with Wait-Free push, Blocking pop.
> > > *
> > > * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers at efficios.com>
> > > *
> > > * This library is free software; you can redistribute it and/or
> > > * modify it under the terms of the GNU Lesser General Public
> > > * License as published by the Free Software Foundation; either
> > > * version 2.1 of the License, or (at your option) any later version.
> > > *
> > > * This library is distributed in the hope that it will be useful,
> > > * but WITHOUT ANY WARRANTY; without even the implied warranty of
> > > * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
> > > * Lesser General Public License for more details.
> > > *
> > > * You should have received a copy of the GNU Lesser General Public
> > > * License along with this library; if not, write to the Free Software
> > > * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
> > > */
> > >
> > > #if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
> > > #error "Dynamic loader LGPL wrappers not implemented yet"
> > > #endif
> > >
> > > struct rcu_wfs_node {
> > > struct rcu_wfs_node *next;
> > > };
> > >
> > > struct rcu_wfs_stack {
> > > struct rcu_wfs_node *head;
> > > struct rcu_wfs_node end;
> >
> > ->end is the dummy node? Ah, a sentinel for the bottom of the stack.
> >
> > But how is ->end really different than a NULL pointer? You don't seem
> > to dereference it anywhere other than initializing it.
>
> Never mind... You need something non-NULL to differentiate from the
> half-pushed state. But you don't actually need storage, so you could
> just as easily use ->head as ->end, right? Or 0x1, for that matter.
Exactly. I changed it for 0x1.
Thanks!
Mathieu
>
> Thanx, Paul
>
> > > };
> > >
> > > void rcu_wfs_node_init(struct rcu_wfs_node *node)
> > > {
> > > node->next = NULL;
> > > }
> > >
> > > void rcu_wfs_init(struct rcu_wfs_stack *s)
> > > {
> > > s->head = &s->end;
> > > rcu_wfs_node_init(&s->end);
> > > }
> > >
> > > void rcu_wfs_push(struct rcu_wfs_stack *s, struct rcu_wfs_node *node)
> > > {
> > > struct rcu_wfs_node *old_head;
> > >
> > > /*
> > > * uatomic_xchg() implicit memory barrier orders earlier stores to node
> > > * (setting it to NULL) before publication.
> > > */
> > > old_head = uatomic_xchg(&s->head, node);
> >
> > Interesting... This can be in an implied RCU read-side critical section
> > because rcu_wfs_pop() might be waiting for this code while within an
> > RCU read-side critical section...
> >
> > > /*
> > > * At this point, dequeuers see a NULL node->next, they should busy-wait
> > > * until node->next is set to old_head.
> > > */
> > > STORE_SHARED(node->next, old_head);
> > > }
> > >
> > > /*
> > > * The caller must wait for a grace period before freeing the returned node.
> > > * Returns NULL if stack is empty.
> > > *
> > > * cmpxchg is protected from ABA races by holding a RCU read lock between
> > > * s->head read and cmpxchg modifying s->head and requiring that dequeuers wait
> > > * for a grace period before freeing the returned node.
> >
> > And they must also wait for a grace period before in any way modifying
> > the ->next pointer (so watch it with the unions!!!). And they cannot
> > pass the node back to push() on the same stack that they got it from
> > without also waiting for a grace period.
> >
> > > *
> > > * TODO: implement adaptative busy-wait and wait/wakeup scheme rather than busy
> > > * loops. Better for UP.
> > > */
> > > struct rcu_wfs_node *
> > > rcu_wfs_pop(struct rcu_wfs_stack *s)
> > > {
> > > rcu_read_lock();
> > > for (;;) {
> > > struct rcu_wfs_node *head = rcu_dereference(s->head);
> > >
> > > if (head != &s->end) {
> > > struct rcu_wfs_node *next = rcu_dereference(head->next);
> > >
> > > /* Retry while head is being set by push(). */
> > > if (!next)
> > > continue;
> > >
> > > if (uatomic_cmpxchg(&s->head, head, next) == head) {
> > > rcu_read_unlock();
> > > return head;
> > > } else {
> > > /* Concurrent modification. Retry. */
> > > continue;
> > > }
> > > } else {
> > > /* Empty stack */
> > > rcu_read_unlock();
> > > return NULL;
> > > }
> > > }
> > > }
> > >
> > > --
> > > Mathieu Desnoyers
> > > Operating System Efficiency R&D Consultant
> > > EfficiOS Inc.
> > > http://www.efficios.com
> >
> > _______________________________________________
> > rp-private mailing list
> > rp-private at svcs.cs.pdx.edu
> > http://svcs.cs.pdx.edu/mailman/listinfo/rp-private
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
More information about the lttng-dev
mailing list