include/urcu/lfstack.h

   1 // SPDX-FileCopyrightText: 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
   2 //
   3 // SPDX-License-Identifier: LGPL-2.1-or-later
   4
   5 #ifndef _URCU_LFSTACK_H
   6 #define _URCU_LFSTACK_H
   7
   8 /*
   9  * Userspace RCU library - Lock-Free Stack
  10  */
  11
  12 #ifdef __cplusplus
  13 extern "C" {
  14 #endif
  15
  16 #include <stdbool.h>
  17 #include <pthread.h>
  18
  19 /*
  20  * Lock-free stack.
  21  *
  22  * Stack implementing push, pop, pop_all operations, as well as iterator
  23  * on the stack head returned by pop_all.
  24  *
  25  * Synchronization table:
  26  *
  27  * External synchronization techniques described in the API below is
  28  * required between pairs marked with "X". No external synchronization
  29  * required between pairs marked with "-".
  30  *
  31  *                      cds_lfs_push  __cds_lfs_pop  __cds_lfs_pop_all
  32  * cds_lfs_push               -              -                  -
  33  * __cds_lfs_pop              -              X                  X
  34  * __cds_lfs_pop_all          -              X                  -
  35  *
  36  * cds_lfs_pop_blocking and cds_lfs_pop_all_blocking use an internal
  37  * mutex to provide synchronization.
  38  */
  39
  40 /*
  41  * struct cds_lfs_node is returned by cds_lfs_pop, and also used as
  42  * iterator on stack. It is not safe to dereference the node next
  43  * pointer when returned by cds_lfs_pop.
  44  */
  45 struct cds_lfs_node {
  46         struct cds_lfs_node *next;
  47 };
  48
  49 /*
  50  * struct cds_lfs_head is returned by __cds_lfs_pop_all, and can be used
  51  * to begin iteration on the stack. "node" needs to be the first field
  52  * of cds_lfs_head, so the end-of-stack pointer value can be used for
  53  * both types.
  54  */
  55 struct cds_lfs_head {
  56         struct cds_lfs_node node;
  57 };
  58
  59 struct __cds_lfs_stack {
  60         struct cds_lfs_head *head;
  61 };
  62
  63 struct cds_lfs_stack {
  64         struct cds_lfs_head *head;
  65         pthread_mutex_t lock;
  66 };
  67
  68 /*
  69  * In C, the transparent union allows calling functions that work on
  70  * both struct cds_lfs_stack and struct __cds_lfs_stack on any of those
  71  * two types.
  72  *
  73  * In C++, implement static inline wrappers using function overloading
  74  * to obtain an API similar to C.
  75  *
  76  * Avoid complaints from clang++ not knowing the transparent union
  77  * attribute.
  78  */
  79 #if defined(__clang__)
  80 #pragma clang diagnostic push
  81 #pragma clang diagnostic ignored "-Wignored-attributes"
  82 #endif
  83 typedef union {
  84         struct __cds_lfs_stack *_s;
  85         struct cds_lfs_stack *s;
  86 } __attribute__((__transparent_union__)) cds_lfs_stack_ptr_t;
  87 #if defined(__clang__)
  88 #pragma clang diagnostic pop
  89 #endif
  90
  91 #ifdef _LGPL_SOURCE
  92
  93 #include <urcu/static/lfstack.h>
  94
  95 #define cds_lfs_node_init               _cds_lfs_node_init
  96 #define cds_lfs_init                    _cds_lfs_init
  97 #define cds_lfs_destroy                 _cds_lfs_destroy
  98 #define __cds_lfs_init                  ___cds_lfs_init
  99 #define cds_lfs_empty                   _cds_lfs_empty
 100 #define cds_lfs_push                    _cds_lfs_push
 101
 102 /* Locking performed internally */
 103 #define cds_lfs_pop_blocking            _cds_lfs_pop_blocking
 104 #define cds_lfs_pop_all_blocking        _cds_lfs_pop_all_blocking
 105
 106 /* Synchronize pop with internal mutex */
 107 #define cds_lfs_pop_lock                _cds_lfs_pop_lock
 108 #define cds_lfs_pop_unlock              _cds_lfs_pop_unlock
 109
 110 /* Synchronization ensured by the caller. See synchronization table. */
 111 #define __cds_lfs_pop                   ___cds_lfs_pop
 112 #define __cds_lfs_pop_all               ___cds_lfs_pop_all
 113
 114 #else /* !_LGPL_SOURCE */
 115
 116 /*
 117  * cds_lfs_node_init: initialize lock-free stack node.
 118  */
 119 extern void cds_lfs_node_init(struct cds_lfs_node *node);
 120
 121 /*
 122  * cds_lfs_init: initialize lock-free stack (with locking). Pair with
 123  * cds_lfs_destroy().
 124  */
 125 extern void cds_lfs_init(struct cds_lfs_stack *s);
 126
 127 /*
 128  * cds_lfs_destroy: destroy lock-free stack (with lock). Pair with
 129  * cds_lfs_init().
 130  */
 131 extern void cds_lfs_destroy(struct cds_lfs_stack *s);
 132
 133 /*
 134  * __cds_lfs_init: initialize lock-free stack (without lock).
 135  * Don't pair with any destroy function.
 136  */
 137 extern void __cds_lfs_init(struct __cds_lfs_stack *s);
 138
 139 /*
 140  * cds_lfs_empty: return whether lock-free stack is empty.
 141  *
 142  * No memory barrier is issued. No mutual exclusion is required.
 143  */
 144 extern bool cds_lfs_empty(cds_lfs_stack_ptr_t s);
 145
 146 /*
 147  * cds_lfs_push: push a node into the stack.
 148  *
 149  * Does not require any synchronization with other push nor pop.
 150  *
 151  * Returns 0 if the stack was empty prior to adding the node.
 152  * Returns non-zero otherwise.
 153  */
 154 extern bool cds_lfs_push(cds_lfs_stack_ptr_t s,
 155                         struct cds_lfs_node *node);
 156
 157 /*
 158  * cds_lfs_pop_blocking: pop a node from the stack.
 159  *
 160  * Calls __cds_lfs_pop with an internal pop mutex held.
 161  */
 162 extern struct cds_lfs_node *cds_lfs_pop_blocking(struct cds_lfs_stack *s);
 163
 164 /*
 165  * cds_lfs_pop_all_blocking: pop all nodes from a stack.
 166  *
 167  * Calls __cds_lfs_pop_all with an internal pop mutex held.
 168  */
 169 extern struct cds_lfs_head *cds_lfs_pop_all_blocking(struct cds_lfs_stack *s);
 170
 171 /*
 172  * cds_lfs_pop_lock: lock stack pop-protection mutex.
 173  */
 174 extern void cds_lfs_pop_lock(struct cds_lfs_stack *s);
 175
 176 /*
 177  * cds_lfs_pop_unlock: unlock stack pop-protection mutex.
 178  */
 179 extern void cds_lfs_pop_unlock(struct cds_lfs_stack *s);
 180
 181 /*
 182  * __cds_lfs_pop: pop a node from the stack.
 183  *
 184  * Returns NULL if stack is empty.
 185  *
 186  * __cds_lfs_pop needs to be synchronized using one of the following
 187  * techniques:
 188  *
 189  * 1) Calling __cds_lfs_pop under rcu read lock critical section.
 190  *    Both __cds_lfs_pop and __cds_lfs_pop_all callers must wait for a
 191  *    grace period to pass before freeing the returned node or pushing
 192  *    the node back into the stack. It is valid to overwrite the content
 193  *    of cds_lfs_node immediately after __cds_lfs_pop and
 194  *    __cds_lfs_pop_all.
 195  * 2) Using mutual exclusion (e.g. mutexes) to protect __cds_lfs_pop
 196  *    and __cds_lfs_pop_all callers.
 197  * 3) Ensuring that only ONE thread can call __cds_lfs_pop() and
 198  *    __cds_lfs_pop_all(). (multi-provider/single-consumer scheme).
 199  */
 200 extern struct cds_lfs_node *__cds_lfs_pop(cds_lfs_stack_ptr_t s);
 201
 202 /*
 203  * __cds_lfs_pop_all: pop all nodes from a stack.
 204  *
 205  * __cds_lfs_pop_all does not require any synchronization with other
 206  * push, nor with other __cds_lfs_pop_all, but requires synchronization
 207  * matching the technique used to synchronize __cds_lfs_pop:
 208  *
 209  * 1) If __cds_lfs_pop is called under rcu read lock critical section,
 210  *    both __cds_lfs_pop and __cds_lfs_pop_all callers must wait for a
 211  *    grace period to pass before freeing the returned node or pushing
 212  *    the node back into the stack. It is valid to overwrite the content
 213  *    of cds_lfs_node immediately after __cds_lfs_pop and
 214  *    __cds_lfs_pop_all. No RCU read-side critical section is needed
 215  *    around __cds_lfs_pop_all.
 216  * 2) Using mutual exclusion (e.g. mutexes) to protect __cds_lfs_pop and
 217  *    __cds_lfs_pop_all callers.
 218  * 3) Ensuring that only ONE thread can call __cds_lfs_pop() and
 219  *    __cds_lfs_pop_all(). (multi-provider/single-consumer scheme).
 220  */
 221 extern struct cds_lfs_head *__cds_lfs_pop_all(cds_lfs_stack_ptr_t s);
 222
 223 #endif /* !_LGPL_SOURCE */
 224
 225 /*
 226  * cds_lfs_for_each: Iterate over all nodes returned by
 227  *                   __cds_lfs_pop_all.
 228  * @__head: node returned by __cds_lfs_pop_all (struct cds_lfs_head pointer).
 229  * @__node: node to use as iterator (struct cds_lfs_node pointer).
 230  *
 231  * Content written into each node before push is guaranteed to be
 232  * consistent, but no other memory ordering is ensured.
 233  */
 234 #define cds_lfs_for_each(__head, __node)        \
 235         for (__node = &__head->node;            \
 236                 __node != NULL;                 \
 237                 __node = __node->next)
 238
 239 /*
 240  * cds_lfs_for_each_safe: Iterate over all nodes returned by
 241  *                        __cds_lfs_pop_all, safe against node deletion.
 242  * @__head: node returned by __cds_lfs_pop_all (struct cds_lfs_head pointer).
 243  * @__node: node to use as iterator (struct cds_lfs_node pointer).
 244  * @__n: struct cds_lfs_node pointer holding the next pointer (used
 245  *       internally).
 246  *
 247  * Content written into each node before push is guaranteed to be
 248  * consistent, but no other memory ordering is ensured.
 249  */
 250 #define cds_lfs_for_each_safe(__head, __node, __n)                         \
 251         for (__node = &__head->node, __n = (__node ? __node->next : NULL); \
 252                 __node != NULL;                                            \
 253                 __node = __n, __n = (__node ? __node->next : NULL))
 254
 255 #ifdef __cplusplus
 256 }
 257
 258 /*
 259  * In C++, implement static inline wrappers using function overloading
 260  * to obtain an API similar to C.
 261  */
 262
 263 static inline cds_lfs_stack_ptr_t cds_lfs_stack_cast(struct __cds_lfs_stack *s)
 264 {
 265         cds_lfs_stack_ptr_t ret = {
 266                 ._s = s,
 267         };
 268         return ret;
 269 }
 270
 271 static inline cds_lfs_stack_ptr_t cds_lfs_stack_cast(struct cds_lfs_stack *s)
 272 {
 273         cds_lfs_stack_ptr_t ret = {
 274                 .s = s,
 275         };
 276         return ret;
 277 }
 278
 279 template<typename T> static inline bool cds_lfs_empty(T s)
 280 {
 281         return cds_lfs_empty(cds_lfs_stack_cast(s));
 282 }
 283
 284 template<typename T> static inline bool cds_lfs_push(T s,
 285                         struct cds_lfs_node *node)
 286 {
 287         return cds_lfs_push(cds_lfs_stack_cast(s), node);
 288 }
 289
 290 template<typename T> static inline struct cds_lfs_node *__cds_lfs_pop(T s)
 291 {
 292         return __cds_lfs_pop(cds_lfs_stack_cast(s));
 293 }
 294
 295 template<typename T> static inline struct cds_lfs_head *__cds_lfs_pop_all(T s)
 296 {
 297         return __cds_lfs_pop_all(cds_lfs_stack_cast(s));
 298 }
 299
 300 #endif  /* __cplusplus */
 301
 302 #endif /* _URCU_LFSTACK_H */