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 static inline
  60 void _cds_wfs_push(struct cds_wfs_stack *s, struct cds_wfs_node *node)
  61 {
  62         struct cds_wfs_node *old_head;
  63
  64         assert(node->next == NULL);
  65         /*
  66          * uatomic_xchg() implicit memory barrier orders earlier stores to node
  67          * (setting it to NULL) before publication.
  68          */
  69         old_head = uatomic_xchg(&s->head, node);
  70         /*
  71          * At this point, dequeuers see a NULL node->next, they should busy-wait
  72          * until node->next is set to old_head.
  73          */
  74         CMM_STORE_SHARED(node->next, old_head);
  75 }
  76
  77 /*
  78  * Returns NULL if stack is empty.
  79  */
  80 static inline
  81 struct cds_wfs_node *
  82 ___cds_wfs_pop_blocking(struct cds_wfs_stack *s)
  83 {
  84         struct cds_wfs_node *head, *next;
  85         int attempt = 0;
  86
  87 retry:
  88         head = CMM_LOAD_SHARED(s->head);
  89         if (head == CDS_WF_STACK_END)
  90                 return NULL;
  91         /*
  92          * Adaptative busy-looping waiting for push to complete.
  93          */
  94         while ((next = CMM_LOAD_SHARED(head->next)) == NULL) {
  95                 if (++attempt >= CDS_WFS_ADAPT_ATTEMPTS) {
  96                         poll(NULL, 0, CDS_WFS_WAIT);    /* Wait for 10ms */
  97                         attempt = 0;
  98                 } else
  99                         caa_cpu_relax();
 100         }
 101         if (uatomic_cmpxchg(&s->head, head, next) == head)
 102                 return head;
 103         else
 104                 goto retry;             /* Concurrent modification. Retry. */
 105 }
 106
 107 static inline
 108 struct cds_wfs_node *
 109 _cds_wfs_pop_blocking(struct cds_wfs_stack *s)
 110 {
 111         struct cds_wfs_node *retnode;
 112         int ret;
 113
 114         ret = pthread_mutex_lock(&s->lock);
 115         assert(!ret);
 116         retnode = ___cds_wfs_pop_blocking(s);
 117         ret = pthread_mutex_unlock(&s->lock);
 118         assert(!ret);
 119         return retnode;
 120 }
 121
 122 #ifdef __cplusplus
 123 }
 124 #endif
 125
 126 #endif /* _URCU_WFSTACK_STATIC_H */