include/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_init                 ___cds_wfcq_init
 138 #define cds_wfcq_destroy                _cds_wfcq_destroy
 139 #define cds_wfcq_empty                  _cds_wfcq_empty
 140 #define cds_wfcq_enqueue                _cds_wfcq_enqueue
 141
 142 /* Dequeue locking */
 143 #define cds_wfcq_dequeue_lock           _cds_wfcq_dequeue_lock
 144 #define cds_wfcq_dequeue_unlock         _cds_wfcq_dequeue_unlock
 145
 146 /* Locking performed within cds_wfcq calls. */
 147 #define cds_wfcq_dequeue_blocking       _cds_wfcq_dequeue_blocking
 148 #define cds_wfcq_dequeue_with_state_blocking    \
 149                                         _cds_wfcq_dequeue_with_state_blocking
 150 #define cds_wfcq_splice_blocking        _cds_wfcq_splice_blocking
 151 #define cds_wfcq_first_blocking         _cds_wfcq_first_blocking
 152 #define cds_wfcq_next_blocking          _cds_wfcq_next_blocking
 153
 154 /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
 155 #define __cds_wfcq_dequeue_blocking     ___cds_wfcq_dequeue_blocking
 156 #define __cds_wfcq_dequeue_with_state_blocking  \
 157                                         ___cds_wfcq_dequeue_with_state_blocking
 158 #define __cds_wfcq_splice_blocking      ___cds_wfcq_splice_blocking
 159 #define __cds_wfcq_first_blocking       ___cds_wfcq_first_blocking
 160 #define __cds_wfcq_next_blocking        ___cds_wfcq_next_blocking
 161
 162 /*
 163  * Locking ensured by caller by holding cds_wfcq_dequeue_lock().
 164  * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
 165  * need to block. splice returns nonzero if it needs to block.
 166  */
 167 #define __cds_wfcq_dequeue_nonblocking  ___cds_wfcq_dequeue_nonblocking
 168 #define __cds_wfcq_dequeue_with_state_nonblocking       \
 169                                 ___cds_wfcq_dequeue_with_state_nonblocking
 170 #define __cds_wfcq_splice_nonblocking   ___cds_wfcq_splice_nonblocking
 171 #define __cds_wfcq_first_nonblocking    ___cds_wfcq_first_nonblocking
 172 #define __cds_wfcq_next_nonblocking     ___cds_wfcq_next_nonblocking
 173
 174 #else /* !_LGPL_SOURCE */
 175
 176 /*
 177  * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
 178  *
 179  * Synchronization table:
 180  *
 181  * External synchronization techniques described in the API below is
 182  * required between pairs marked with "X". No external synchronization
 183  * required between pairs marked with "-".
 184  *
 185  * Legend:
 186  * [1] cds_wfcq_enqueue
 187  * [2] __cds_wfcq_splice (destination queue)
 188  * [3] __cds_wfcq_dequeue
 189  * [4] __cds_wfcq_splice (source queue)
 190  * [5] __cds_wfcq_first
 191  * [6] __cds_wfcq_next
 192  *
 193  *     [1] [2] [3] [4] [5] [6]
 194  * [1]  -   -   -   -   -   -
 195  * [2]  -   -   -   -   -   -
 196  * [3]  -   -   X   X   X   X
 197  * [4]  -   -   X   -   X   X
 198  * [5]  -   -   X   X   -   -
 199  * [6]  -   -   X   X   -   -
 200  *
 201  * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
 202  *
 203  * For convenience, cds_wfcq_dequeue_blocking() and
 204  * cds_wfcq_splice_blocking() hold the dequeue lock.
 205  *
 206  * Besides locking, mutual exclusion of dequeue, splice and iteration
 207  * can be ensured by performing all of those operations from a single
 208  * thread, without requiring any lock.
 209  */
 210
 211 /*
 212  * cds_wfcq_node_init: initialize wait-free queue node.
 213  */
 214 extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
 215
 216 /*
 217  * cds_wfcq_init: initialize wait-free queue. Pair with
 218  * cds_wfcq_destroy().
 219  */
 220 extern void cds_wfcq_init(struct cds_wfcq_head *head,
 221                 struct cds_wfcq_tail *tail);
 222
 223 /*
 224  * cds_wfcq_destroy: destroy wait-free queue. Pair with
 225  * cds_wfcq_init().
 226  */
 227 extern void cds_wfcq_destroy(struct cds_wfcq_head *head,
 228                 struct cds_wfcq_tail *tail);
 229
 230 /*
 231  * __cds_wfcq_init: initialize wait-free queue (without lock). Don't
 232  * pair with any destroy function.
 233  */
 234 extern void __cds_wfcq_init(struct __cds_wfcq_head *head,
 235                 struct cds_wfcq_tail *tail);
 236
 237 /*
 238  * cds_wfcq_empty: return whether wait-free queue is empty.
 239  *
 240  * No memory barrier is issued. No mutual exclusion is required.
 241  */
 242 extern bool cds_wfcq_empty(cds_wfcq_head_ptr_t head,
 243                 struct cds_wfcq_tail *tail);
 244
 245 /*
 246  * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
 247  */
 248 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
 249                 struct cds_wfcq_tail *tail);
 250
 251 /*
 252  * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
 253  */
 254 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
 255                 struct cds_wfcq_tail *tail);
 256
 257 /*
 258  * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
 259  *
 260  * Issues a full memory barrier before enqueue. No mutual exclusion is
 261  * required.
 262  *
 263  * Returns false if the queue was empty prior to adding the node.
 264  * Returns true otherwise.
 265  */
 266 extern bool cds_wfcq_enqueue(cds_wfcq_head_ptr_t head,
 267                 struct cds_wfcq_tail *tail,
 268                 struct cds_wfcq_node *node);
 269
 270 /*
 271  * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 272  *
 273  * Content written into the node before enqueue is guaranteed to be
 274  * consistent, but no other memory ordering is ensured.
 275  * It is valid to reuse and free a dequeued node immediately.
 276  * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
 277  * ensured.
 278  */
 279 extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
 280                 struct cds_wfcq_head *head,
 281                 struct cds_wfcq_tail *tail);
 282
 283 /*
 284  * cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 285  *
 286  * Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the
 287  * last node of the queue into state (CDS_WFCQ_STATE_LAST).
 288  */
 289 extern struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking(
 290                 struct cds_wfcq_head *head,
 291                 struct cds_wfcq_tail *tail,
 292                 int *state);
 293
 294 /*
 295  * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 296  *
 297  * Dequeue all nodes from src_q.
 298  * dest_q must be already initialized.
 299  * Content written into the node before enqueue is guaranteed to be
 300  * consistent, but no other memory ordering is ensured.
 301  * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
 302  * ensured.
 303  *
 304  * Returns enum cds_wfcq_ret which indicates the state of the src or
 305  * dest queue.
 306  */
 307 extern enum cds_wfcq_ret cds_wfcq_splice_blocking(
 308                 struct cds_wfcq_head *dest_q_head,
 309                 struct cds_wfcq_tail *dest_q_tail,
 310                 struct cds_wfcq_head *src_q_head,
 311                 struct cds_wfcq_tail *src_q_tail);
 312
 313 /*
 314  * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 315  *
 316  * Content written into the node before enqueue is guaranteed to be
 317  * consistent, but no other memory ordering is ensured.
 318  * It is valid to reuse and free a dequeued node immediately.
 319  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 320  * caller.
 321  */
 322 extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
 323                 cds_wfcq_head_ptr_t head,
 324                 struct cds_wfcq_tail *tail);
 325
 326 /*
 327  * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 328  *
 329  * Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the
 330  * last node of the queue into state (CDS_WFCQ_STATE_LAST).
 331  */
 332 extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking(
 333                 cds_wfcq_head_ptr_t head,
 334                 struct cds_wfcq_tail *tail,
 335                 int *state);
 336
 337 /*
 338  * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
 339  *
 340  * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
 341  * if it needs to block.
 342  */
 343 extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking(
 344                 cds_wfcq_head_ptr_t head,
 345                 struct cds_wfcq_tail *tail);
 346
 347 /*
 348  * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
 349  *
 350  * Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing
 351  * the last node of the queue into state (CDS_WFCQ_STATE_LAST).
 352  */
 353 extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking(
 354                 cds_wfcq_head_ptr_t head,
 355                 struct cds_wfcq_tail *tail,
 356                 int *state);
 357
 358 /*
 359  * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 360  *
 361  * Dequeue all nodes from src_q.
 362  * dest_q must be already initialized.
 363  * Mutual exclusion for src_q should be ensured by the caller as
 364  * specified in the "Synchronisation table".
 365  * Returns enum cds_wfcq_ret which indicates the state of the src or
 366  * dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK.
 367  */
 368 extern enum cds_wfcq_ret __cds_wfcq_splice_blocking(
 369                 cds_wfcq_head_ptr_t dest_q_head,
 370                 struct cds_wfcq_tail *dest_q_tail,
 371                 cds_wfcq_head_ptr_t src_q_head,
 372                 struct cds_wfcq_tail *src_q_tail);
 373
 374 /*
 375  * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
 376  *
 377  * Same as __cds_wfcq_splice_blocking, but returns
 378  * CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
 379  */
 380 extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking(
 381                 cds_wfcq_head_ptr_t dest_q_head,
 382                 struct cds_wfcq_tail *dest_q_tail,
 383                 cds_wfcq_head_ptr_t src_q_head,
 384                 struct cds_wfcq_tail *src_q_tail);
 385
 386 /*
 387  * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
 388  *
 389  * Content written into the node before enqueue is guaranteed to be
 390  * consistent, but no other memory ordering is ensured.
 391  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 392  * caller.
 393  *
 394  * Used by for-like iteration macros:
 395  * __cds_wfcq_for_each_blocking()
 396  * __cds_wfcq_for_each_blocking_safe()
 397  *
 398  * Returns NULL if queue is empty, first node otherwise.
 399  */
 400 extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
 401                 cds_wfcq_head_ptr_t head,
 402                 struct cds_wfcq_tail *tail);
 403
 404 /*
 405  * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
 406  *
 407  * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
 408  * it needs to block.
 409  */
 410 extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking(
 411                 cds_wfcq_head_ptr_t head,
 412                 struct cds_wfcq_tail *tail);
 413
 414 /*
 415  * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 416  *
 417  * Content written into the node before enqueue is guaranteed to be
 418  * consistent, but no other memory ordering is ensured.
 419  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 420  * caller.
 421  *
 422  * Used by for-like iteration macros:
 423  * __cds_wfcq_for_each_blocking()
 424  * __cds_wfcq_for_each_blocking_safe()
 425  *
 426  * Returns NULL if reached end of queue, non-NULL next queue node
 427  * otherwise.
 428  */
 429 extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
 430                 cds_wfcq_head_ptr_t head,
 431                 struct cds_wfcq_tail *tail,
 432                 struct cds_wfcq_node *node);
 433
 434 /*
 435  * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 436  *
 437  * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
 438  * it needs to block.
 439  */
 440 extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking(
 441                 cds_wfcq_head_ptr_t head,
 442                 struct cds_wfcq_tail *tail,
 443                 struct cds_wfcq_node *node);
 444
 445 #endif /* !_LGPL_SOURCE */
 446
 447 /*
 448  * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
 449  * without dequeuing them.
 450  * @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
 451  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 452  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 453  *
 454  * Content written into each node before enqueue is guaranteed to be
 455  * consistent, but no other memory ordering is ensured.
 456  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 457  * caller.
 458  */
 459 #define __cds_wfcq_for_each_blocking(head, tail, node)          \
 460         for (node = __cds_wfcq_first_blocking(head, tail);      \
 461                 node != NULL;                                   \
 462                 node = __cds_wfcq_next_blocking(head, tail, node))
 463
 464 /*
 465  * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
 466  * without dequeuing them. Safe against deletion.
 467  * @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer).
 468  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 469  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 470  * @n: struct cds_wfcq_node pointer holding the next pointer (used
 471  *     internally).
 472  *
 473  * Content written into each node before enqueue is guaranteed to be
 474  * consistent, but no other memory ordering is ensured.
 475  * Dequeue/splice/iteration mutual exclusion should be ensured by the
 476  * caller.
 477  */
 478 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n)                 \
 479         for (node = __cds_wfcq_first_blocking(head, tail),                     \
 480                         n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
 481                 node != NULL;                                                  \
 482                 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
 483
 484 #ifdef __cplusplus
 485 }
 486 #endif
 487
 488 #endif /* _URCU_WFCQUEUE_H */