urcu/wfstack-static.h

   1 #ifndef _URCU_WFSTACK_STATIC_H
   2 #define _URCU_WFSTACK_STATIC_H
   3
   4 /*
   5  * wfstack-static.h
   6  *
   7  * Userspace RCU library - Stack with Wait-Free push, Blocking pop.
   8  *
   9  * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See wfstack.h for linking
  10  * dynamically with the userspace rcu library.
  11  *
  12  * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  13  *
  14  * This library is free software; you can redistribute it and/or
  15  * modify it under the terms of the GNU Lesser General Public
  16  * License as published by the Free Software Foundation; either
  17  * version 2.1 of the License, or (at your option) any later version.
  18  *
  19  * This library is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  22  * Lesser General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Lesser General Public
  25  * License along with this library; if not, write to the Free Software
  26  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  27  */
  28
  29 #include <pthread.h>
  30 #include <assert.h>
  31 #include <urcu/compiler.h>
  32 #include <urcu/uatomic_arch.h>
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  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 void _wfs_node_init(struct wfs_node *node)
  43 {
  44         node->next = NULL;
  45 }
  46
  47 void _wfs_init(struct wfs_stack *s)
  48 {
  49         int ret;
  50
  51         s->head = WF_STACK_END;
  52         ret = pthread_mutex_init(&s->lock, NULL);
  53         assert(!ret);
  54 }
  55
  56 void _wfs_push(struct wfs_stack *s, struct wfs_node *node)
  57 {
  58         struct wfs_node *old_head;
  59
  60         assert(node->next == NULL);
  61         /*
  62          * uatomic_xchg() implicit memory barrier orders earlier stores to node
  63          * (setting it to NULL) before publication.
  64          */
  65         old_head = uatomic_xchg(&s->head, node);
  66         /*
  67          * At this point, dequeuers see a NULL node->next, they should busy-wait
  68          * until node->next is set to old_head.
  69          */
  70         STORE_SHARED(node->next, old_head);
  71 }
  72
  73 /*
  74  * Returns NULL if stack is empty.
  75  */
  76 struct wfs_node *
  77 ___wfs_pop_blocking(struct wfs_stack *s)
  78 {
  79         struct wfs_node *head, *next;
  80         int attempt = 0;
  81
  82 retry:
  83         head = LOAD_SHARED(s->head);
  84         if (head == WF_STACK_END)
  85                 return NULL;
  86         /*
  87          * Adaptative busy-looping waiting for push to complete.
  88          */
  89         while ((next = LOAD_SHARED(head->next)) == NULL) {
  90                 if (++attempt >= WFS_ADAPT_ATTEMPTS) {
  91                         poll(NULL, 0, WFS_WAIT);        /* Wait for 10ms */
  92                         attempt = 0;
  93                 } else
  94                         cpu_relax();
  95         }
  96         if (uatomic_cmpxchg(&s->head, head, next) == head)
  97                 return head;
  98         else
  99                 goto retry;             /* Concurrent modification. Retry. */
 100 }
 101
 102 struct wfs_node *
 103 _wfs_pop_blocking(struct wfs_stack *s)
 104 {
 105         struct wfs_node *retnode;
 106         int ret;
 107
 108         ret = pthread_mutex_lock(&s->lock);
 109         assert(!ret);
 110         retnode = ___wfs_pop_blocking(s);
 111         ret = pthread_mutex_unlock(&s->lock);
 112         assert(!ret);
 113         return retnode;
 114 }
 115
 116 #ifdef __cplusplus
 117 }
 118 #endif
 119
 120 #endif /* _URCU_WFSTACK_STATIC_H */