urcu/wfcqueue.h

   1 #ifndef _URCU_WFCQUEUE_H
   2 #define _URCU_WFCQUEUE_H
   3
   4 /*
   5  * 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  * Inspired from half-wait-free/half-blocking queue implementation done by
  41  * Paul E. McKenney.
  42  */
  43
  44 struct cds_wfcq_node {
  45         struct cds_wfcq_node *next;
  46 };
  47
  48 /*
  49  * Do not put head and tail on the same cache-line if concurrent
  50  * enqueue/dequeue are expected from many CPUs. This eliminates
  51  * false-sharing between enqueue and dequeue.
  52  */
  53 struct cds_wfcq_head {
  54         struct cds_wfcq_node node;
  55         pthread_mutex_t lock;
  56 };
  57
  58 struct cds_wfcq_tail {
  59         struct cds_wfcq_node *p;
  60 };
  61
  62 #ifdef _LGPL_SOURCE
  63
  64 #include <urcu/static/wfcqueue.h>
  65
  66 #define cds_wfcq_node_init              _cds_wfcq_node_init
  67 #define cds_wfcq_init                   _cds_wfcq_init
  68 #define cds_wfcq_empty                  _cds_wfcq_empty
  69 #define cds_wfcq_enqueue                _cds_wfcq_enqueue
  70
  71 /* Dequeue locking */
  72 #define cds_wfcq_dequeue_lock           _cds_wfcq_dequeue_lock
  73 #define cds_wfcq_dequeue_unlock         _cds_wfcq_dequeue_unlock
  74
  75 /* Locking performed within cds_wfcq calls. */
  76 #define cds_wfcq_dequeue_blocking       _cds_wfcq_dequeue_blocking
  77 #define cds_wfcq_splice_blocking        _cds_wfcq_splice_blocking
  78 #define cds_wfcq_first_blocking         _cds_wfcq_first_blocking
  79 #define cds_wfcq_next_blocking          _cds_wfcq_next_blocking
  80
  81 /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
  82 #define __cds_wfcq_dequeue_blocking     ___cds_wfcq_dequeue_blocking
  83 #define __cds_wfcq_splice_blocking      ___cds_wfcq_splice_blocking
  84 #define __cds_wfcq_first_blocking       ___cds_wfcq_first_blocking
  85 #define __cds_wfcq_next_blocking        ___cds_wfcq_next_blocking
  86
  87 #else /* !_LGPL_SOURCE */
  88
  89 /*
  90  * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
  91  *
  92  * Unless otherwise stated, the caller must ensure mutual exclusion of
  93  * queue update operations "dequeue" and "splice" (for source queue).
  94  * Queue read operations "first" and "next", which are used by
  95  * "for_each" iterations, need to be protected against concurrent
  96  * "dequeue" and "splice" (for source queue) by the caller.
  97  * "enqueue", "splice" (for destination queue), and "empty" are the only
  98  * operations that can be used without any mutual exclusion.
  99  * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
 100  *
 101  * For convenience, cds_wfcq_dequeue_blocking() and
 102  * cds_wfcq_splice_blocking() hold the dequeue lock.
 103  */
 104
 105 /*
 106  * cds_wfcq_node_init: initialize wait-free queue node.
 107  */
 108 extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
 109
 110 /*
 111  * cds_wfcq_init: initialize wait-free queue.
 112  */
 113 extern void cds_wfcq_init(struct cds_wfcq_head *head,
 114                 struct cds_wfcq_tail *tail);
 115
 116 /*
 117  * cds_wfcq_empty: return whether wait-free queue is empty.
 118  *
 119  * No memory barrier is issued. No mutual exclusion is required.
 120  */
 121 extern bool cds_wfcq_empty(struct cds_wfcq_head *head,
 122                 struct cds_wfcq_tail *tail);
 123
 124 /*
 125  * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
 126  */
 127 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
 128                 struct cds_wfcq_tail *tail);
 129
 130 /*
 131  * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
 132  */
 133 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
 134                 struct cds_wfcq_tail *tail);
 135
 136 /*
 137  * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
 138  *
 139  * Issues a full memory barrier before enqueue. No mutual exclusion is
 140  * required.
 141  */
 142 extern void cds_wfcq_enqueue(struct cds_wfcq_head *head,
 143                 struct cds_wfcq_tail *tail,
 144                 struct cds_wfcq_node *node);
 145
 146 /*
 147  * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 148  *
 149  * Content written into the node before enqueue is guaranteed to be
 150  * consistent, but no other memory ordering is ensured.
 151  * It is valid to reuse and free a dequeued node immediately.
 152  * Mutual exlusion with dequeuers is ensured internally.
 153  */
 154 extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
 155                 struct cds_wfcq_head *head,
 156                 struct cds_wfcq_tail *tail);
 157
 158 /*
 159  * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 160  *
 161  * Dequeue all nodes from src_q.
 162  * dest_q must be already initialized.
 163  * Content written into the node before enqueue is guaranteed to be
 164  * consistent, but no other memory ordering is ensured.
 165  * Mutual exlusion with dequeuers is ensured internally.
 166  */
 167 extern void cds_wfcq_splice_blocking(
 168                 struct cds_wfcq_head *dest_q_head,
 169                 struct cds_wfcq_tail *dest_q_tail,
 170                 struct cds_wfcq_head *src_q_head,
 171                 struct cds_wfcq_tail *src_q_tail);
 172
 173 /*
 174  * __cds_wfcq_dequeue_blocking:
 175  *
 176  * Content written into the node before enqueue is guaranteed to be
 177  * consistent, but no other memory ordering is ensured.
 178  * It is valid to reuse and free a dequeued node immediately.
 179  * Should be called with cds_wfcq_dequeue_lock() held.
 180  */
 181 extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
 182                 struct cds_wfcq_head *head,
 183                 struct cds_wfcq_tail *tail);
 184
 185 /*
 186  * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 187  *
 188  * Dequeue all nodes from src_q.
 189  * dest_q must be already initialized.
 190  * Content written into the node before enqueue is guaranteed to be
 191  * consistent, but no other memory ordering is ensured.
 192  * Should be called with cds_wfcq_dequeue_lock() held.
 193  */
 194 extern void __cds_wfcq_splice_blocking(
 195                 struct cds_wfcq_head *dest_q_head,
 196                 struct cds_wfcq_tail *dest_q_tail,
 197                 struct cds_wfcq_head *src_q_head,
 198                 struct cds_wfcq_tail *src_q_tail);
 199
 200 /*
 201  * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
 202  *
 203  * Content written into the node before enqueue is guaranteed to be
 204  * consistent, but no other memory ordering is ensured.
 205  * Should be called with cds_wfcq_dequeue_lock() held.
 206  *
 207  * Used by for-like iteration macros:
 208  * __cds_wfcq_for_each_blocking()
 209  * __cds_wfcq_for_each_blocking_safe()
 210  */
 211 extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
 212                 struct cds_wfcq_head *head,
 213                 struct cds_wfcq_tail *tail);
 214
 215 /*
 216  * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 217  *
 218  * Content written into the node before enqueue is guaranteed to be
 219  * consistent, but no other memory ordering is ensured.
 220  * Should be called with cds_wfcq_dequeue_lock() held.
 221  *
 222  * Used by for-like iteration macros:
 223  * __cds_wfcq_for_each_blocking()
 224  * __cds_wfcq_for_each_blocking_safe()
 225  */
 226 extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
 227                 struct cds_wfcq_head *head,
 228                 struct cds_wfcq_tail *tail,
 229                 struct cds_wfcq_node *node);
 230
 231 #endif /* !_LGPL_SOURCE */
 232
 233 /*
 234  * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
 235  * without dequeuing them.
 236  * @head: head of the queue (struct cds_wfcq_head pointer).
 237  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 238  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 239  *
 240  * Content written into each node before enqueue is guaranteed to be
 241  * consistent, but no other memory ordering is ensured.
 242  * Should be called with cds_wfcq_dequeue_lock() held.
 243  */
 244 #define __cds_wfcq_for_each_blocking(head, tail, node)          \
 245         for (node = __cds_wfcq_first_blocking(head, tail);      \
 246                 node != NULL;                                   \
 247                 node = __cds_wfcq_next_blocking(head, tail, node))
 248
 249 /*
 250  * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
 251  * without dequeuing them. Safe against deletion.
 252  * @head: head of the queue (struct cds_wfcq_head pointer).
 253  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 254  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 255  * @n: struct cds_wfcq_node pointer holding the next pointer (used
 256  *     internally).
 257  *
 258  * Content written into each node before enqueue is guaranteed to be
 259  * consistent, but no other memory ordering is ensured.
 260  * Should be called with cds_wfcq_dequeue_lock() held.
 261  */
 262 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n)                 \
 263         for (node = __cds_wfcq_first_blocking(head, tail),                     \
 264                         n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
 265                 node != NULL;                                                  \
 266                 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
 267
 268 #ifdef __cplusplus
 269 }
 270 #endif
 271
 272 #endif /* _URCU_WFCQUEUE_H */