urcu/wfcqueue.h

   1 #ifndef _URCU_WFCQUEUE_H
   2 #define _URCU_WFCQUEUE_H
   3
   4 /*
   5  * urcu/wfcqueue.h
   6  *
   7  * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
   8  *
   9  * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  10  * Copyright 2011-2012 - Lai Jiangshan <laijs@cn.fujitsu.com>
  11  *
  12  * This library is free software; you can redistribute it and/or
  13  * modify it under the terms of the GNU Lesser General Public
  14  * License as published by the Free Software Foundation; either
  15  * version 2.1 of the License, or (at your option) any later version.
  16  *
  17  * This library is distributed in the hope that it will be useful,
  18  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  19  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  20  * Lesser General Public License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with this library; if not, write to the Free Software
  24  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  25  */
  26
  27 #include <pthread.h>
  28 #include <assert.h>
  29 #include <stdbool.h>
  30 #include <urcu/compiler.h>
  31 #include <urcu/arch.h>
  32
  33 #ifdef __cplusplus
  34 extern "C" {
  35 #endif
  36
  37 /*
  38  * Concurrent queue with wait-free enqueue/blocking dequeue.
  39  *
  40  * This queue has been designed and implemented collaboratively by
  41  * Mathieu Desnoyers and Lai Jiangshan. Inspired from
  42  * half-wait-free/half-blocking queue implementation done by Paul E.
  43  * McKenney.
  44  */
  45
  46 #define CDS_WFCQ_WOULDBLOCK     ((struct cds_wfcq_node *) -1UL)
  47
  48 enum cds_wfcq_ret {
  49         CDS_WFCQ_RET_WOULDBLOCK =       -1,
  50         CDS_WFCQ_RET_DEST_EMPTY =       0,
  51         CDS_WFCQ_RET_DEST_NON_EMPTY =   1,
  52         CDS_WFCQ_RET_SRC_EMPTY =        2,
  53 };
  54
  55 enum cds_wfcq_state {
  56         CDS_WFCQ_STATE_LAST =           (1U << 0),
  57 };
  58
  59 struct cds_wfcq_node {
  60         struct cds_wfcq_node *next;
  61 };
  62
  63 /*
  64  * Do not put head and tail on the same cache-line if concurrent
  65  * enqueue/dequeue are expected from many CPUs. This eliminates
  66  * false-sharing between enqueue and dequeue.
  67  */
  68 struct __cds_wfcq_head {
  69         struct cds_wfcq_node node;
  70 };
  71
  72 struct cds_wfcq_head {
  73         struct cds_wfcq_node node;
  74         pthread_mutex_t lock;
  75 };
  76
  77 #ifndef __cplusplus
  78 /*
  79  * The transparent union allows calling functions that work on both
  80  * struct cds_wfcq_head and struct __cds_wfcq_head on any of those two
  81  * types.
  82  */
  83 typedef union {
  84         struct __cds_wfcq_head *_h;
  85         struct cds_wfcq_head *h;
  86 } __attribute__((__transparent_union__)) cds_wfcq_head_ptr_t;
  87
  88 /*
  89  * This static inline is only present for compatibility with C++. It is
  90  * effect-less in C.
  91  */
  92 static inline struct __cds_wfcq_head *__cds_wfcq_head_cast(struct __cds_wfcq_head *head)
  93 {
  94         return head;
  95 }
  96
  97 /*
  98  * This static inline is only present for compatibility with C++. It is
  99  * effect-less in C.
 100  */
 101 static inline struct cds_wfcq_head *cds_wfcq_head_cast(struct cds_wfcq_head *head)
 102 {
 103         return head;
 104 }
 105 #else /* #ifndef __cplusplus */
 106
 107 /* C++ ignores transparent union. */
 108 typedef union {
 109         struct __cds_wfcq_head *_h;
 110         struct cds_wfcq_head *h;
 111 } cds_wfcq_head_ptr_t;
 112
 113 /* C++ ignores transparent union. Requires an explicit conversion. */
 114 static inline cds_wfcq_head_ptr_t __cds_wfcq_head_cast(struct __cds_wfcq_head *head)
 115 {
 116         cds_wfcq_head_ptr_t ret = { ._h = head };
 117         return ret;
 118 }
 119 /* C++ ignores transparent union. Requires an explicit conversion. */
 120 static inline cds_wfcq_head_ptr_t cds_wfcq_head_cast(struct cds_wfcq_head *head)
 121 {
 122         cds_wfcq_head_ptr_t ret = { .h = head };
 123         return ret;
 124 }
 125 #endif /* #else #ifndef __cplusplus */
 126
 127 struct cds_wfcq_tail {
 128         struct cds_wfcq_node *p;
 129 };
 130
 131 #ifdef _LGPL_SOURCE
 132
 133 #include <urcu/static/wfcqueue.h>
 134
 135 #define cds_wfcq_node_init              _cds_wfcq_node_init
 136 #define cds_wfcq_init                   _cds_wfcq_init
 137 #define cds_wfcq_empty                  _cds_wfcq_empty
 138 #define cds_wfcq_enqueue                _cds_wfcq_enqueue
 139
 140 /* Dequeue locking */
 141 #define cds_wfcq_dequeue_lock           _cds_wfcq_dequeue_lock
 142 #define cds_wfcq_dequeue_unlock         _cds_wfcq_dequeue_unlock
 143
 144 /* Locking performed within cds_wfcq calls. */
 145 #define cds_wfcq_dequeue_blocking       _cds_wfcq_dequeue_blocking
 146 #define cds_wfcq_dequeue_with_state_blocking    \
 147                                         _cds_wfcq_dequeue_with_state_blocking
 148 #define cds_wfcq_splice_blocking        _cds_wfcq_splice_blocking
 149 #define cds_wfcq_first_blocking         _cds_wfcq_first_blocking
 150 #define cds_wfcq_next_blocking          _cds_wfcq_next_blocking
 151
 152 /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
 153 #define __cds_wfcq_dequeue_blocking     ___cds_wfcq_dequeue_blocking
 154 #define __cds_wfcq_dequeue_with_state_blocking  \
 155                                         ___cds_wfcq_dequeue_with_state_blocking
 156 #define __cds_wfcq_splice_blocking      ___cds_wfcq_splice_blocking
 157 #define __cds_wfcq_first_blocking       ___cds_wfcq_first_blocking
 158 #define __cds_wfcq_next_blocking        ___cds_wfcq_next_blocking
 159
 160 /*
 161  * Locking ensured by caller by holding cds_wfcq_dequeue_lock().
 162  * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
 163  * need to block. splice returns nonzero if it needs to block.
 164  */
 165 #define __cds_wfcq_dequeue_nonblocking  ___cds_wfcq_dequeue_nonblocking
 166 #define __cds_wfcq_dequeue_with_state_nonblocking       \
 167                                 ___cds_wfcq_dequeue_with_state_nonblocking
 168 #define __cds_wfcq_splice_nonblocking   ___cds_wfcq_splice_nonblocking
 169 #define __cds_wfcq_first_nonblocking    ___cds_wfcq_first_nonblocking
 170 #define __cds_wfcq_next_nonblocking     ___cds_wfcq_next_nonblocking
 171
 172 #else /* !_LGPL_SOURCE */
 173
 174 /*
 175  * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
 176  *
 177  * Synchronization table:
 178  *
 179  * External synchronization techniques described in the API below is
 180  * required between pairs marked with "X". No external synchronization
 181  * required between pairs marked with "-".
 182  *
 183  * Legend:
 184  * [1] cds_wfcq_enqueue
 185  * [2] __cds_wfcq_splice (destination queue)
 186  * [3] __cds_wfcq_dequeue
 187  * [4] __cds_wfcq_splice (source queue)
 188  * [5] __cds_wfcq_first
 189  * [6] __cds_wfcq_next
 190  *
 191  *     [1] [2] [3] [4] [5] [6]
 192  * [1]  -   -   -   -   -   -
 193  * [2]  -   -   -   -   -   -
 194  * [3]  -   -   X   X   X   X
 195  * [4]  -   -   X   -   X   X
 196  * [5]  -   -   X   X   -   -
 197  * [6]  -   -   X   X   -   -
 198  *
 199  * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
 200  *
 201  * For convenience, cds_wfcq_dequeue_blocking() and
 202  * cds_wfcq_splice_blocking() hold the dequeue lock.
 203  *
 204  * Besides locking, mutual exclusion of dequeue, splice and iteration
 205  * can be ensured by performing all of those operations from a single
 206  * thread, without requiring any lock.
 207  */
 208
 209 /*
 210  * cds_wfcq_node_init: initialize wait-free queue node.
 211  */
 212 extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
 213
 214 /*
 215  * cds_wfcq_init: initialize wait-free queue.
 216  */
 217 extern void cds_wfcq_init(struct cds_wfcq_head *head,
 218                 struct cds_wfcq_tail *tail);
 219
 220 /*
 221  * __cds_wfcq_init: initialize wait-free queue.
 222  */
 223 extern void __cds_wfcq_init(struct __cds_wfcq_head *head,
 224                 struct cds_wfcq_tail *tail);
 225
 226 /*
 227  * cds_wfcq_empty: return whether wait-free queue is empty.
 228  *
 229  * No memory barrier is issued. No mutual exclusion is required.
 230  */
 231 extern bool cds_wfcq_empty(cds_wfcq_head_ptr_t head,
 232                 struct cds_wfcq_tail *tail);
 233
 234 /*
 235  * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
 236  */
 237 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
 238                 struct cds_wfcq_tail *tail);
 239
 240 /*
 241  * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
 242  */
 243 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
 244                 struct cds_wfcq_tail *tail);
 245
 246 /*
 247  * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
 248  *
 249  * Issues a full memory barrier before enqueue. No mutual exclusion is
 250  * required.
 251  *
 252  * Returns false if the queue was empty prior to adding the node.
 253  * Returns true otherwise.
 254  */
 255 extern bool cds_wfcq_enqueue(cds_wfcq_head_ptr_t head,
 256                 struct cds_wfcq_tail *tail,
 257                 struct cds_wfcq_node *node);
 258
 259 /*
 260  * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 261  *
 262  * Content written into the node before enqueue is guaranteed to be
 263  * consistent, but no other memory ordering is ensured.
 264  * It is valid to reuse and free a dequeued node immediately.
 265  * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
 266  * ensured.
 267  */
 268 extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
 269                 struct cds_wfcq_head *head,
 270                 struct cds_wfcq_tail *tail);
 271
 272 /*
 273  * cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 274  *
 275  * Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the
 276  * last node of the queue into state (CDS_WFCQ_STATE_LAST).
 277  */
 278 extern struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking(
 279                 struct cds_wfcq_head *head,
 280                 struct cds_wfcq_tail *tail,
 281                 int *state);
 282
 283 /*
 284  * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 285  *
 286  * Dequeue all nodes from src_q.
 287  * dest_q must be already initialized.
 288  * Content written into the node before enqueue is guaranteed to be
 289  * consistent, but no other memory ordering is ensured.
 290  * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
 291  * ensured.
 292  *
 293  * Returns enum cds_wfcq_ret which indicates the state of the src or
 294  * dest queue.
 295  */
 296 extern enum cds_wfcq_ret cds_wfcq_splice_blocking(
 297                 struct cds_wfcq_head *dest_q_head,
 298                 struct cds_wfcq_tail *dest_q_tail,
 299                 struct cds_wfcq_head *src_q_head,
 300                 struct cds_wfcq_tail *src_q_tail);
 301
 302 /*
 303  * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 304  *
 305  * Content written into the node before enqueue is guaranteed to be
 306  * consistent, but no other memory ordering is ensured.
 307  * It is valid to reuse and free a dequeued node immediately.
 308  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 309  * caller.
 310  */
 311 extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
 312                 cds_wfcq_head_ptr_t head,
 313                 struct cds_wfcq_tail *tail);
 314
 315 /*
 316  * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 317  *
 318  * Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the
 319  * last node of the queue into state (CDS_WFCQ_STATE_LAST).
 320  */
 321 extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking(
 322                 cds_wfcq_head_ptr_t head,
 323                 struct cds_wfcq_tail *tail,
 324                 int *state);
 325
 326 /*
 327  * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
 328  *
 329  * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
 330  * if it needs to block.
 331  */
 332 extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking(
 333                 cds_wfcq_head_ptr_t head,
 334                 struct cds_wfcq_tail *tail);
 335
 336 /*
 337  * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 338  *
 339  * Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing
 340  * the last node of the queue into state (CDS_WFCQ_STATE_LAST).
 341  */
 342 extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking(
 343                 cds_wfcq_head_ptr_t head,
 344                 struct cds_wfcq_tail *tail,
 345                 int *state);
 346
 347 /*
 348  * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 349  *
 350  * Dequeue all nodes from src_q.
 351  * dest_q must be already initialized.
 352  * Mutual exclusion for src_q should be ensured by the caller as
 353  * specified in the "Synchronisation table".
 354  * Returns enum cds_wfcq_ret which indicates the state of the src or
 355  * dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK.
 356  */
 357 extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
 358                 cds_wfcq_head_ptr_t dest_q_head,
 359                 struct cds_wfcq_tail *dest_q_tail,
 360                 cds_wfcq_head_ptr_t src_q_head,
 361                 struct cds_wfcq_tail *src_q_tail);
 362
 363 /*
 364  * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
 365  *
 366  * Same as __cds_wfcq_splice_blocking, but returns
 367  * CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
 368  */
 369 extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking(
 370                 cds_wfcq_head_ptr_t dest_q_head,
 371                 struct cds_wfcq_tail *dest_q_tail,
 372                 cds_wfcq_head_ptr_t src_q_head,
 373                 struct cds_wfcq_tail *src_q_tail);
 374
 375 /*
 376  * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
 377  *
 378  * Content written into the node before enqueue is guaranteed to be
 379  * consistent, but no other memory ordering is ensured.
 380  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 381  * caller.
 382  *
 383  * Used by for-like iteration macros:
 384  * __cds_wfcq_for_each_blocking()
 385  * __cds_wfcq_for_each_blocking_safe()
 386  *
 387  * Returns NULL if queue is empty, first node otherwise.
 388  */
 389 extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
 390                 cds_wfcq_head_ptr_t head,
 391                 struct cds_wfcq_tail *tail);
 392
 393 /*
 394  * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
 395  *
 396  * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
 397  * it needs to block.
 398  */
 399 extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking(
 400                 cds_wfcq_head_ptr_t head,
 401                 struct cds_wfcq_tail *tail);
 402
 403 /*
 404  * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 405  *
 406  * Content written into the node before enqueue is guaranteed to be
 407  * consistent, but no other memory ordering is ensured.
 408  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 409  * caller.
 410  *
 411  * Used by for-like iteration macros:
 412  * __cds_wfcq_for_each_blocking()
 413  * __cds_wfcq_for_each_blocking_safe()
 414  *
 415  * Returns NULL if reached end of queue, non-NULL next queue node
 416  * otherwise.
 417  */
 418 extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
 419                 cds_wfcq_head_ptr_t head,
 420                 struct cds_wfcq_tail *tail,
 421                 struct cds_wfcq_node *node);
 422
 423 /*
 424  * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 425  *
 426  * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
 427  * it needs to block.
 428  */
 429 extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking(
 430                 cds_wfcq_head_ptr_t head,
 431                 struct cds_wfcq_tail *tail,
 432                 struct cds_wfcq_node *node);
 433
 434 #endif /* !_LGPL_SOURCE */
 435
 436 /*
 437  * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
 438  * without dequeuing them.
 439  * @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
 440  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 441  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 442  *
 443  * Content written into each node before enqueue is guaranteed to be
 444  * consistent, but no other memory ordering is ensured.
 445  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 446  * caller.
 447  */
 448 #define __cds_wfcq_for_each_blocking(head, tail, node)          \
 449         for (node = __cds_wfcq_first_blocking(head, tail);      \
 450                 node != NULL;                                   \
 451                 node = __cds_wfcq_next_blocking(head, tail, node))
 452
 453 /*
 454  * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
 455  * without dequeuing them. Safe against deletion.
 456  * @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
 457  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 458  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 459  * @n: struct cds_wfcq_node pointer holding the next pointer (used
 460  *     internally).
 461  *
 462  * Content written into each node before enqueue is guaranteed to be
 463  * consistent, but no other memory ordering is ensured.
 464  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 465  * caller.
 466  */
 467 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n)                 \
 468         for (node = __cds_wfcq_first_blocking(head, tail),                     \
 469                         n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
 470                 node != NULL;                                                  \
 471                 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
 472
 473 #ifdef __cplusplus
 474 }
 475 #endif
 476
 477 #endif /* _URCU_WFCQUEUE_H */