urcu/rcuwfstack.h

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