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 <[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
> */
>
> 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
_______________________________________________
ltt-dev mailing list
[email protected]
http://lists.casi.polymtl.ca/cgi-bin/mailman/listinfo/ltt-dev
