urcu/static/wfstack.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.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 static inline
  44 void _cds_wfs_node_init(struct cds_wfs_node *node)
  45 {
  46         node->next = NULL;
  47 }
  48
  49 static inline
  50 void _cds_wfs_init(struct cds_wfs_stack *s)
  51 {
  52         int ret;
  53
  54         s->head = CDS_WF_STACK_END;
  55         ret = pthread_mutex_init(&s->lock, NULL);
  56         assert(!ret);
  57 }
  58
  59 /*
  60  * Returns 0 if stack was empty, 1 otherwise.
  61  */
  62 static inline
  63 int _cds_wfs_push(struct cds_wfs_stack *s, struct cds_wfs_node *node)
  64 {
  65         struct cds_wfs_node *old_head;
  66
  67         assert(node->next == NULL);
  68         /*
  69          * uatomic_xchg() implicit memory barrier orders earlier stores to node
  70          * (setting it to NULL) before publication.
  71          */
  72         old_head = uatomic_xchg(&s->head, node);
  73         /*
  74          * At this point, dequeuers see a NULL node->next, they should busy-wait
  75          * until node->next is set to old_head.
  76          */
  77         CMM_STORE_SHARED(node->next, old_head);
  78         return (old_head != CDS_WF_STACK_END);
  79 }
  80
  81 /*
  82  * Returns NULL if stack is empty.
  83  */
  84 static inline
  85 struct cds_wfs_node *
  86 ___cds_wfs_pop_blocking(struct cds_wfs_stack *s)
  87 {
  88         struct cds_wfs_node *head, *next;
  89         int attempt = 0;
  90
  91 retry:
  92         head = CMM_LOAD_SHARED(s->head);
  93         if (head == CDS_WF_STACK_END)
  94                 return NULL;
  95         /*
  96          * Adaptative busy-looping waiting for push to complete.
  97          */
  98         while ((next = CMM_LOAD_SHARED(head->next)) == NULL) {
  99                 if (++attempt >= CDS_WFS_ADAPT_ATTEMPTS) {
 100                         poll(NULL, 0, CDS_WFS_WAIT);    /* Wait for 10ms */
 101                         attempt = 0;
 102                 } else
 103                         caa_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 static inline
 112 struct cds_wfs_node *
 113 _cds_wfs_pop_blocking(struct cds_wfs_stack *s)
 114 {
 115         struct cds_wfs_node *retnode;
 116         int ret;
 117
 118         ret = pthread_mutex_lock(&s->lock);
 119         assert(!ret);
 120         retnode = ___cds_wfs_pop_blocking(s);
 121         ret = pthread_mutex_unlock(&s->lock);
 122         assert(!ret);
 123         return retnode;
 124 }
 125
 126 #ifdef __cplusplus
 127 }
 128 #endif
 129
 130 #endif /* _URCU_WFSTACK_STATIC_H */