include/urcu/wfstack.h

   1 #ifndef _URCU_WFSTACK_H
   2 #define _URCU_WFSTACK_H
   3
   4 /*
   5  * urcu/wfstack.h
   6  *
   7  * Userspace RCU library - Stack with wait-free push, blocking traversal.
   8  *
   9  * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2.1 of the License, or (at your option) any later version.
  15  *
  16  * This library is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with this library; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  24  */
  25
  26 #include <pthread.h>
  27 #include <stdbool.h>
  28 #include <urcu/compiler.h>
  29
  30 #ifdef __cplusplus
  31 extern "C" {
  32 #endif
  33
  34 /*
  35  * Stack with wait-free push, blocking traversal.
  36  *
  37  * Stack implementing push, pop, pop_all operations, as well as iterator
  38  * on the stack head returned by pop_all.
  39  *
  40  * Wait-free operations: cds_wfs_push, __cds_wfs_pop_all, cds_wfs_empty,
  41  *                       cds_wfs_first.
  42  * Blocking operations: cds_wfs_pop, cds_wfs_pop_all, cds_wfs_next,
  43  *                      iteration on stack head returned by pop_all.
  44  *
  45  * Synchronization table:
  46  *
  47  * External synchronization techniques described in the API below is
  48  * required between pairs marked with "X". No external synchronization
  49  * required between pairs marked with "-".
  50  *
  51  *                      cds_wfs_push  __cds_wfs_pop  __cds_wfs_pop_all
  52  * cds_wfs_push               -              -                  -
  53  * __cds_wfs_pop              -              X                  X
  54  * __cds_wfs_pop_all          -              X                  -
  55  *
  56  * cds_wfs_pop and cds_wfs_pop_all use an internal mutex to provide
  57  * synchronization.
  58  */
  59
  60 #define CDS_WFS_WOULDBLOCK      ((struct cds_wfs_node *) -1UL)
  61
  62 enum cds_wfs_state {
  63         CDS_WFS_STATE_LAST =            (1U << 0),
  64 };
  65
  66 /*
  67  * struct cds_wfs_node is returned by __cds_wfs_pop, and also used as
  68  * iterator on stack. It is not safe to dereference the node next
  69  * pointer when returned by __cds_wfs_pop_blocking.
  70  */
  71 struct cds_wfs_node {
  72         struct cds_wfs_node *next;
  73 };
  74
  75 /*
  76  * struct cds_wfs_head is returned by __cds_wfs_pop_all, and can be used
  77  * to begin iteration on the stack. "node" needs to be the first field of
  78  * cds_wfs_head, so the end-of-stack pointer value can be used for both
  79  * types.
  80  */
  81 struct cds_wfs_head {
  82         struct cds_wfs_node node;
  83 };
  84
  85 struct __cds_wfs_stack {
  86         struct cds_wfs_head *head;
  87 };
  88
  89 struct cds_wfs_stack {
  90         struct cds_wfs_head *head;
  91         pthread_mutex_t lock;
  92 };
  93
  94 /*
  95  * In C, the transparent union allows calling functions that work on both
  96  * struct cds_wfs_stack and struct __cds_wfs_stack on any of those two
  97  * types.
  98  *
  99  * In C++, implement static inline wrappers using function overloading
 100  * to obtain an API similar to C.
 101  *
 102  * Avoid complaints from clang++ not knowing the transparent union
 103  * attribute.
 104  */
 105 #if defined(__clang__)
 106 #pragma clang diagnostic push
 107 #pragma clang diagnostic ignored "-Wignored-attributes"
 108 #endif
 109 typedef union {
 110         struct __cds_wfs_stack *_s;
 111         struct cds_wfs_stack *s;
 112 } __attribute__((__transparent_union__)) cds_wfs_stack_ptr_t;
 113 #if defined(__clang__)
 114 #pragma clang diagnostic pop
 115 #endif
 116
 117 #ifdef _LGPL_SOURCE
 118
 119 #include <urcu/static/wfstack.h>
 120
 121 #define cds_wfs_node_init               _cds_wfs_node_init
 122 #define cds_wfs_init                    _cds_wfs_init
 123 #define cds_wfs_destroy                 _cds_wfs_destroy
 124 #define __cds_wfs_init                  ___cds_wfs_init
 125 #define cds_wfs_empty                   _cds_wfs_empty
 126 #define cds_wfs_push                    _cds_wfs_push
 127
 128 /* Locking performed internally */
 129 #define cds_wfs_pop_blocking            _cds_wfs_pop_blocking
 130 #define cds_wfs_pop_with_state_blocking _cds_wfs_pop_with_state_blocking
 131 #define cds_wfs_pop_all_blocking        _cds_wfs_pop_all_blocking
 132
 133 /*
 134  * For iteration on cds_wfs_head returned by __cds_wfs_pop_all or
 135  * cds_wfs_pop_all_blocking.
 136  */
 137 #define cds_wfs_first                   _cds_wfs_first
 138 #define cds_wfs_next_blocking           _cds_wfs_next_blocking
 139 #define cds_wfs_next_nonblocking        _cds_wfs_next_nonblocking
 140
 141 /* Pop locking with internal mutex */
 142 #define cds_wfs_pop_lock                _cds_wfs_pop_lock
 143 #define cds_wfs_pop_unlock              _cds_wfs_pop_unlock
 144
 145 /* Synchronization ensured by the caller. See synchronization table. */
 146 #define __cds_wfs_pop_blocking          ___cds_wfs_pop_blocking
 147 #define __cds_wfs_pop_with_state_blocking       \
 148                                         ___cds_wfs_pop_with_state_blocking
 149 #define __cds_wfs_pop_nonblocking       ___cds_wfs_pop_nonblocking
 150 #define __cds_wfs_pop_with_state_nonblocking    \
 151                                         ___cds_wfs_pop_with_state_nonblocking
 152 #define __cds_wfs_pop_all               ___cds_wfs_pop_all
 153
 154 #else /* !_LGPL_SOURCE */
 155
 156 /*
 157  * cds_wfs_node_init: initialize wait-free stack node.
 158  */
 159 extern void cds_wfs_node_init(struct cds_wfs_node *node);
 160
 161 /*
 162  * cds_wfs_init: initialize wait-free stack (with lock). Pair with
 163  * cds_wfs_destroy().
 164  */
 165 extern void cds_wfs_init(struct cds_wfs_stack *s);
 166
 167 /*
 168  * cds_wfs_destroy: destroy wait-free stack (with lock). Pair with
 169  * cds_wfs_init().
 170  */
 171 extern void cds_wfs_destroy(struct cds_wfs_stack *s);
 172
 173 /*
 174  * __cds_wfs_init: initialize wait-free stack (no lock). Don't pair with
 175  * any destroy function.
 176  */
 177 extern void __cds_wfs_init(struct __cds_wfs_stack *s);
 178
 179 /*
 180  * cds_wfs_empty: return whether wait-free stack is empty.
 181  *
 182  * No memory barrier is issued. No mutual exclusion is required.
 183  */
 184 extern bool cds_wfs_empty(cds_wfs_stack_ptr_t u_stack);
 185
 186 /*
 187  * cds_wfs_push: push a node into the stack.
 188  *
 189  * Issues a full memory barrier before push. No mutual exclusion is
 190  * required.
 191  *
 192  * Returns 0 if the stack was empty prior to adding the node.
 193  * Returns non-zero otherwise.
 194  */
 195 extern int cds_wfs_push(cds_wfs_stack_ptr_t u_stack, struct cds_wfs_node *node);
 196
 197 /*
 198  * cds_wfs_pop_blocking: pop a node from the stack.
 199  *
 200  * Calls __cds_wfs_pop_blocking with an internal pop mutex held.
 201  */
 202 extern struct cds_wfs_node *cds_wfs_pop_blocking(struct cds_wfs_stack *s);
 203
 204 /*
 205  * cds_wfs_pop_with_state_blocking: pop a node from the stack, with state.
 206  *
 207  * Same as cds_wfs_pop_blocking, but stores whether the stack was
 208  * empty into state (CDS_WFS_STATE_LAST).
 209  */
 210 extern struct cds_wfs_node *
 211         cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state);
 212
 213 /*
 214  * cds_wfs_pop_all_blocking: pop all nodes from a stack.
 215  *
 216  * Calls __cds_wfs_pop_all with an internal pop mutex held.
 217  */
 218 extern struct cds_wfs_head *cds_wfs_pop_all_blocking(struct cds_wfs_stack *s);
 219
 220 /*
 221  * cds_wfs_first: get first node of a popped stack.
 222  *
 223  * Content written into the node before enqueue is guaranteed to be
 224  * consistent, but no other memory ordering is ensured.
 225  *
 226  * Used by for-like iteration macros in urcu/wfstack.h:
 227  * cds_wfs_for_each_blocking()
 228  * cds_wfs_for_each_blocking_safe()
 229  *
 230  * Returns NULL if popped stack is empty, top stack node otherwise.
 231  */
 232 extern struct cds_wfs_node *cds_wfs_first(struct cds_wfs_head *head);
 233
 234 /*
 235  * cds_wfs_next_blocking: get next node of a popped stack.
 236  *
 237  * Content written into the node before enqueue is guaranteed to be
 238  * consistent, but no other memory ordering is ensured.
 239  *
 240  * Used by for-like iteration macros in urcu/wfstack.h:
 241  * cds_wfs_for_each_blocking()
 242  * cds_wfs_for_each_blocking_safe()
 243  *
 244  * Returns NULL if reached end of popped stack, non-NULL next stack
 245  * node otherwise.
 246  */
 247 extern struct cds_wfs_node *cds_wfs_next_blocking(struct cds_wfs_node *node);
 248
 249 /*
 250  * cds_wfs_next_nonblocking: get next node of a popped stack.
 251  *
 252  * Same as cds_wfs_next_blocking, but returns CDS_WFS_WOULDBLOCK if it
 253  * needs to block.
 254  */
 255 extern struct cds_wfs_node *cds_wfs_next_nonblocking(struct cds_wfs_node *node);
 256
 257 /*
 258  * cds_wfs_pop_lock: lock stack pop-protection mutex.
 259  */
 260 extern void cds_wfs_pop_lock(struct cds_wfs_stack *s);
 261
 262 /*
 263  * cds_wfs_pop_unlock: unlock stack pop-protection mutex.
 264  */
 265 extern void cds_wfs_pop_unlock(struct cds_wfs_stack *s);
 266
 267 /*
 268  * __cds_wfs_pop_blocking: pop a node from the stack.
 269  *
 270  * Returns NULL if stack is empty.
 271  *
 272  * __cds_wfs_pop_blocking needs to be synchronized using one of the
 273  * following techniques:
 274  *
 275  * 1) Calling __cds_wfs_pop_blocking under rcu read lock critical
 276  *    section. The caller must wait for a grace period to pass before
 277  *    freeing the returned node or modifying the cds_wfs_node structure.
 278  * 2) Using mutual exclusion (e.g. mutexes) to protect
 279  *     __cds_wfs_pop_blocking and __cds_wfs_pop_all callers.
 280  * 3) Ensuring that only ONE thread can call __cds_wfs_pop_blocking()
 281  *    and __cds_wfs_pop_all(). (multi-provider/single-consumer scheme).
 282  */
 283 extern struct cds_wfs_node *__cds_wfs_pop_blocking(cds_wfs_stack_ptr_t u_stack);
 284
 285 /*
 286  * __cds_wfs_pop_with_state_blocking: pop a node from the stack, with state.
 287  *
 288  * Same as __cds_wfs_pop_blocking, but stores whether the stack was
 289  * empty into state (CDS_WFS_STATE_LAST).
 290  */
 291 extern struct cds_wfs_node *
 292         __cds_wfs_pop_with_state_blocking(cds_wfs_stack_ptr_t u_stack,
 293                 int *state);
 294
 295 /*
 296  * __cds_wfs_pop_nonblocking: pop a node from the stack.
 297  *
 298  * Same as __cds_wfs_pop_blocking, but returns CDS_WFS_WOULDBLOCK if
 299  * it needs to block.
 300  */
 301 extern struct cds_wfs_node *__cds_wfs_pop_nonblocking(cds_wfs_stack_ptr_t u_stack);
 302
 303 /*
 304  * __cds_wfs_pop_with_state_nonblocking: pop a node from the stack, with state.
 305  *
 306  * Same as __cds_wfs_pop_nonblocking, but stores whether the stack was
 307  * empty into state (CDS_WFS_STATE_LAST).
 308  */
 309 extern struct cds_wfs_node *
 310         __cds_wfs_pop_with_state_nonblocking(cds_wfs_stack_ptr_t u_stack,
 311                 int *state);
 312
 313 /*
 314  * __cds_wfs_pop_all: pop all nodes from a stack.
 315  *
 316  * __cds_wfs_pop_all does not require any synchronization with other
 317  * push, nor with other __cds_wfs_pop_all, but requires synchronization
 318  * matching the technique used to synchronize __cds_wfs_pop_blocking:
 319  *
 320  * 1) If __cds_wfs_pop_blocking is called under rcu read lock critical
 321  *    section, both __cds_wfs_pop_blocking and cds_wfs_pop_all callers
 322  *    must wait for a grace period to pass before freeing the returned
 323  *    node or modifying the cds_wfs_node structure. However, no RCU
 324  *    read-side critical section is needed around __cds_wfs_pop_all.
 325  * 2) Using mutual exclusion (e.g. mutexes) to protect
 326  *     __cds_wfs_pop_blocking and __cds_wfs_pop_all callers.
 327  * 3) Ensuring that only ONE thread can call __cds_wfs_pop_blocking()
 328  *    and __cds_wfs_pop_all(). (multi-provider/single-consumer scheme).
 329  */
 330 extern struct cds_wfs_head *__cds_wfs_pop_all(cds_wfs_stack_ptr_t u_stack);
 331
 332 #endif /* !_LGPL_SOURCE */
 333
 334 /*
 335  * cds_wfs_for_each_blocking: Iterate over all nodes returned by
 336  * __cds_wfs_pop_all().
 337  * @head: head of the queue (struct cds_wfs_head pointer).
 338  * @node: iterator (struct cds_wfs_node pointer).
 339  *
 340  * Content written into each node before enqueue is guaranteed to be
 341  * consistent, but no other memory ordering is ensured.
 342  */
 343 #define cds_wfs_for_each_blocking(head, node)                   \
 344         for (node = cds_wfs_first(head);                        \
 345                 node != NULL;                                   \
 346                 node = cds_wfs_next_blocking(node))
 347
 348 /*
 349  * cds_wfs_for_each_blocking_safe: Iterate over all nodes returned by
 350  * __cds_wfs_pop_all(). Safe against deletion.
 351  * @head: head of the queue (struct cds_wfs_head pointer).
 352  * @node: iterator (struct cds_wfs_node pointer).
 353  * @n: struct cds_wfs_node pointer holding the next pointer (used
 354  *     internally).
 355  *
 356  * Content written into each node before enqueue is guaranteed to be
 357  * consistent, but no other memory ordering is ensured.
 358  */
 359 #define cds_wfs_for_each_blocking_safe(head, node, n)                      \
 360         for (node = cds_wfs_first(head),                                   \
 361                         n = (node ? cds_wfs_next_blocking(node) : NULL);   \
 362                 node != NULL;                                              \
 363                 node = n, n = (node ? cds_wfs_next_blocking(node) : NULL))
 364
 365 #ifdef __cplusplus
 366 }
 367
 368 /*
 369  * In C++, implement static inline wrappers using function overloading
 370  * to obtain an API similar to C.
 371  */
 372
 373 static inline cds_wfs_stack_ptr_t cds_wfs_stack_cast(struct __cds_wfs_stack *s)
 374 {
 375         cds_wfs_stack_ptr_t ret = {
 376                 ._s = s,
 377         };
 378         return ret;
 379 }
 380
 381 static inline cds_wfs_stack_ptr_t cds_wfs_stack_cast(struct cds_wfs_stack *s)
 382 {
 383         cds_wfs_stack_ptr_t ret = {
 384                 .s = s,
 385         };
 386         return ret;
 387 }
 388
 389 template<typename T> static inline bool cds_wfs_empty(T s)
 390 {
 391         return cds_wfs_empty(cds_wfs_stack_cast(s));
 392 }
 393
 394 template<typename T> static inline int cds_wfs_push(T s, struct cds_wfs_node *node)
 395 {
 396         return cds_wfs_push(cds_wfs_stack_cast(s), node);
 397 }
 398
 399 template<typename T> static inline struct cds_wfs_node *__cds_wfs_pop_blocking(T s)
 400 {
 401         return __cds_wfs_pop_blocking(cds_wfs_stack_cast(s));
 402 }
 403
 404 template<typename T> static inline struct cds_wfs_node *
 405         __cds_wfs_pop_with_state_blocking(T s, int *state)
 406 {
 407         return __cds_wfs_pop_with_state_blocking(cds_wfs_stack_cast(s), state);
 408 }
 409
 410 template<typename T> static inline struct cds_wfs_node *__cds_wfs_pop_nonblocking(T s)
 411
 412 {
 413         return __cds_wfs_pop_nonblocking(cds_wfs_stack_cast(s));
 414 }
 415
 416 template<typename T> static inline struct cds_wfs_node *
 417         __cds_wfs_pop_with_state_nonblocking(T s, int *state)
 418 {
 419         return __cds_wfs_pop_with_state_nonblocking(cds_wfs_stack_cast(s), state);
 420 }
 421
 422 template<typename T> static inline struct cds_wfs_head *__cds_wfs_pop_all(T s)
 423 {
 424         return __cds_wfs_pop_all(cds_wfs_stack_cast(s));
 425 }
 426
 427 #endif
 428
 429 #endif /* _URCU_WFSTACK_H */