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 <poll.h>
  32 #include <urcu/compiler.h>
  33 #include <urcu/uatomic_arch.h>
  34
  35 #ifdef __cplusplus
  36 extern "C" {
  37 #endif
  38
  39 #define CDS_WF_STACK_END                        ((void *)0x1UL)
  40 #define CDS_WFS_ADAPT_ATTEMPTS          10      /* Retry if being set */
  41 #define CDS_WFS_WAIT                    10      /* Wait 10 ms if being set */
  42
  43 void _cds_wfs_node_init(struct cds_wfs_node *node)
  44 {
  45         node->next = NULL;
  46 }
  47
  48 void _cds_wfs_init(struct cds_wfs_stack *s)
  49 {
  50         int ret;
  51
  52         s->head = CDS_WF_STACK_END;
  53         ret = pthread_mutex_init(&s->lock, NULL);
  54         assert(!ret);
  55 }
  56
  57 void _cds_wfs_push(struct cds_wfs_stack *s, struct cds_wfs_node *node)
  58 {
  59         struct cds_wfs_node *old_head;
  60
  61         assert(node->next == NULL);
  62         /*
  63          * uatomic_xchg() implicit memory barrier orders earlier stores to node
  64          * (setting it to NULL) before publication.
  65          */
  66         old_head = uatomic_xchg(&s->head, node);
  67         /*
  68          * At this point, dequeuers see a NULL node->next, they should busy-wait
  69          * until node->next is set to old_head.
  70          */
  71         CMM_STORE_SHARED(node->next, old_head);
  72 }
  73
  74 /*
  75  * Returns NULL if stack is empty.
  76  */
  77 struct cds_wfs_node *
  78 ___cds_wfs_pop_blocking(struct cds_wfs_stack *s)
  79 {
  80         struct cds_wfs_node *head, *next;
  81         int attempt = 0;
  82
  83 retry:
  84         head = CMM_LOAD_SHARED(s->head);
  85         if (head == CDS_WF_STACK_END)
  86                 return NULL;
  87         /*
  88          * Adaptative busy-looping waiting for push to complete.
  89          */
  90         while ((next = CMM_LOAD_SHARED(head->next)) == NULL) {
  91                 if (++attempt >= CDS_WFS_ADAPT_ATTEMPTS) {
  92                         poll(NULL, 0, CDS_WFS_WAIT);    /* Wait for 10ms */
  93                         attempt = 0;
  94                 } else
  95                         caa_cpu_relax();
  96         }
  97         if (uatomic_cmpxchg(&s->head, head, next) == head)
  98                 return head;
  99         else
 100                 goto retry;             /* Concurrent modification. Retry. */
 101 }
 102
 103 struct cds_wfs_node *
 104 _cds_wfs_pop_blocking(struct cds_wfs_stack *s)
 105 {
 106         struct cds_wfs_node *retnode;
 107         int ret;
 108
 109         ret = pthread_mutex_lock(&s->lock);
 110         assert(!ret);
 111         retnode = ___cds_wfs_pop_blocking(s);
 112         ret = pthread_mutex_unlock(&s->lock);
 113         assert(!ret);
 114         return retnode;
 115 }
 116
 117 #ifdef __cplusplus
 118 }
 119 #endif
 120
 121 #endif /* _URCU_WFSTACK_STATIC_H */