urcu/rcuwfstack.h

   1 /*
   2  * rcuwfstack.h
   3  *
   4  * Userspace RCU library - RCU Stack with Wait-Free push, Blocking pop.
   5  *
   6  * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   7  *
   8  * This library is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * This library is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with this library; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 #if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
  24 #error "Dynamic loader LGPL wrappers not implemented yet"
  25 #endif
  26
  27 struct rcu_wfs_node {
  28         struct rcu_wfs_node *next;
  29 };
  30
  31 struct rcu_wfs_stack {
  32         struct rcu_wfs_node *head;
  33         struct rcu_wfs_node end;
  34 };
  35
  36 void rcu_wfs_node_init(struct rcu_wfs_node *node)
  37 {
  38         node->next = NULL;
  39 }
  40
  41 void rcu_wfs_init(struct rcu_wfs_stack *s)
  42 {
  43         s->head = &s->end;
  44         rcu_wfs_node_init(&s->end);
  45 }
  46
  47 void rcu_wfs_push(struct rcu_wfs_stack *s, struct rcu_wfs_node *node)
  48 {
  49         struct rcu_wfs_node *old_head;
  50
  51         /*
  52          * uatomic_xchg() implicit memory barrier orders earlier stores to node
  53          * (setting it to NULL) before publication.
  54          */
  55         old_head = uatomic_xchg(&s->head, node);
  56         /*
  57          * At this point, dequeuers see a NULL node->next, they should busy-wait
  58          * until node->next is set to old_head.
  59          */
  60         STORE_SHARED(node->next, old_head);
  61 }
  62
  63 /*
  64  * The caller must wait for a grace period before freeing the returned node.
  65  * Returns NULL if stack is empty.
  66  *
  67  * cmpxchg is protected from ABA races by holding a RCU read lock between
  68  * s->head read and cmpxchg modifying s->head and requiring that dequeuers wait
  69  * for a grace period before freeing the returned node.
  70  *
  71  * TODO: implement adaptative busy-wait and wait/wakeup scheme rather than busy
  72  * loops. Better for UP.
  73  */
  74 struct rcu_wfs_node *
  75 rcu_wfs_pop(struct rcu_wfs_stack *s)
  76 {
  77         rcu_read_lock();
  78         for (;;) {
  79                 struct rcu_wfs_node *head = rcu_dereference(s->head);
  80
  81                 if (head != &s->end) {
  82                         struct rcu_wfs_node *next = rcu_dereference(head->next);
  83
  84                         /* Retry while head is being set by push(). */
  85                         if (!next)
  86                                 continue;
  87
  88                         if (uatomic_cmpxchg(&s->head, head, next) == head) {
  89                                 rcu_read_unlock();
  90                                 return head;
  91                         } else {
  92                                 /* Concurrent modification. Retry. */
  93                                 continue;
  94                         }
  95                 } else {
  96                         /* Empty stack */
  97                         rcu_read_unlock();
  98                         return NULL;
  99                 }
 100         }
 101 }