* Paul E. McKenney ([email protected]) 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 ? Thanks! Mathieu /* * rcuwfstack.h * * Userspace RCU library - RCU Stack with Wait-Free push, Blocking pop. * * Copyright 2010 - Mathieu Desnoyers <[email protected]> * * 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; }; 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); /* * 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. * * 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 _______________________________________________ ltt-dev mailing list [email protected] http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
