urcu/wfstack.h

   1 #ifndef _URCU_WFSTACK_H
   2 #define _URCU_WFSTACK_H
   3
   4 /*
   5  * rcuwfstack.h
   6  *
   7  * Userspace RCU library - 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 <pthread.h>
  27 #include <assert.h>
  28 #include <urcu/compiler.h>
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  34 #if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
  35 #error "Dynamic loader LGPL wrappers not implemented yet"
  36 #endif
  37
  38 #define WF_STACK_END                    ((void *)0x1UL)
  39 #define WFS_ADAPT_ATTEMPTS              10      /* Retry if being set */
  40 #define WFS_WAIT                        10      /* Wait 10 ms if being set */
  41
  42 struct wfs_node {
  43         struct wfs_node *next;
  44 };
  45
  46 struct wfs_stack {
  47         struct wfs_node *head;
  48         pthread_mutex_t lock;
  49 };
  50
  51 void wfs_node_init(struct wfs_node *node)
  52 {
  53         node->next = NULL;
  54 }
  55
  56 void wfs_init(struct wfs_stack *s)
  57 {
  58         int ret;
  59
  60         s->head = WF_STACK_END;
  61         ret = pthread_mutex_init(&s->lock, NULL);
  62         assert(!ret);
  63 }
  64
  65 void wfs_push(struct wfs_stack *s, struct wfs_node *node)
  66 {
  67         struct wfs_node *old_head;
  68
  69         assert(node->next == NULL);
  70         /*
  71          * uatomic_xchg() implicit memory barrier orders earlier stores to node
  72          * (setting it to NULL) before publication.
  73          */
  74         old_head = uatomic_xchg(&s->head, node);
  75         /*
  76          * At this point, dequeuers see a NULL node->next, they should busy-wait
  77          * until node->next is set to old_head.
  78          */
  79         STORE_SHARED(node->next, old_head);
  80 }
  81
  82 /*
  83  * Returns NULL if stack is empty.
  84  */
  85 struct wfs_node *
  86 __wfs_pop_blocking(struct wfs_stack *s)
  87 {
  88         struct wfs_node *head, *next;
  89         int attempt = 0;
  90
  91 retry:
  92         head = LOAD_SHARED(s->head);
  93         if (head == WF_STACK_END)
  94                 return NULL;
  95         /*
  96          * Adaptative busy-looping waiting for push to complete.
  97          */
  98         while ((next = LOAD_SHARED(head->next)) == NULL) {
  99                 if (++attempt >= WFS_ADAPT_ATTEMPTS) {
 100                         poll(NULL, 0, WFS_WAIT);        /* Wait for 10ms */
 101                         attempt = 0;
 102                 } else
 103                         cpu_relax();
 104         }
 105         if (uatomic_cmpxchg(&s->head, head, next) == head)
 106                 return head;
 107         else
 108                 goto retry;             /* Concurrent modification. Retry. */
 109 }
 110
 111 struct wfs_node *
 112 wfs_pop_blocking(struct wfs_stack *s)
 113 {
 114         struct wfs_node *retnode;
 115         int ret;
 116
 117         ret = pthread_mutex_lock(&s->lock);
 118         assert(!ret);
 119         retnode = __wfs_pop_blocking(s);
 120         ret = pthread_mutex_unlock(&s->lock);
 121         assert(!ret);
 122         return retnode;
 123 }
 124
 125 #ifdef __cplusplus
 126 }
 127 #endif
 128
 129 #endif /* _URCU_WFSTACK_H */