[ltt-dev] [RFC] Lock-free RCU stack for userspace RCU library

[Paul E. McKenney]

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

							Thanx, Paul

> Thanks,
> 
> Mathieu
> 
> 
> /*
>  * rculfstack.h
>  *
>  * Userspace RCU library - Lock-Free RCU Stack
>  *
>  * 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
>  */
> 
> struct rcu_lfs_node {
> 	struct rcu_lfs_node *next;
> };
> 
> struct rcu_lfs_stack {
> 	struct rcu_lfs_node *head;
> };
> 
> void rcu_lfs_node_init(struct rcu_lfs_node *node)
> {
> }
> 
> void rcu_lfs_init(struct rcu_lfs_stack *s)
> {
> 	s->head = NULL;
> }
> 
> void rcu_lfs_push(struct rcu_lfs_stack *s, struct rcu_lfs_node *node)
> {
> 	rcu_read_lock();
> 	for (;;) {
> 		struct rcu_lfs_node *head = rcu_dereference(s->head);
> 
> 		node->next = head;
> 		/*
> 		 * uatomic_cmpxchg() implicit memory barrier orders earlier
> 		 * stores to node before publication.
> 		 */
> 		if (uatomic_cmpxchg(&s->head, head, node) == head) {
> 			rcu_read_unlock();
> 			return;
> 		} else {
> 			/* Failure to prepend. Retry. */
> 			continue;
> 		}
> 	}
> }
> 
> struct rcu_lfs_node *
> rcu_lfs_pop(struct rcu_lfs_stack *s)
> {
> 	rcu_read_lock();
> 	for (;;) {
> 		struct rcu_lfs_node *head = rcu_dereference(s->head);
> 
> 		if (head) {
> 			struct rcu_lfs_node *next = rcu_dereference(head->next);
> 
> 			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