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" need to be protected against
  95  * concurrent "dequeue" and "splice" (for source queue) by the caller.
  96  * "enqueue", "splice" (for destination queue), and "empty" are the only
  97  * operations that can be used without any mutual exclusion.
  98  * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
  99  *
 100  * For convenience, cds_wfcq_dequeue_blocking() and
 101  * cds_wfcq_splice_blocking() hold the dequeue lock.
 102  */
 103
 104 /*
 105  * cds_wfcq_node_init: initialize wait-free queue node.
 106  */
 107 extern void cds_wfcq_node_init(struct cds_wfcq_node *node);
 108
 109 /*
 110  * cds_wfcq_init: initialize wait-free queue.
 111  */
 112 extern void cds_wfcq_init(struct cds_wfcq_head *head,
 113                 struct cds_wfcq_tail *tail);
 114
 115 /*
 116  * cds_wfcq_empty: return whether wait-free queue is empty.
 117  *
 118  * No memory barrier is issued. No mutual exclusion is required.
 119  */
 120 extern bool cds_wfcq_empty(struct cds_wfcq_head *head,
 121                 struct cds_wfcq_tail *tail);
 122
 123 /*
 124  * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
 125  */
 126 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head,
 127                 struct cds_wfcq_tail *tail);
 128
 129 /*
 130  * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
 131  */
 132 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head,
 133                 struct cds_wfcq_tail *tail);
 134
 135 /*
 136  * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
 137  *
 138  * Issues a full memory barrier before enqueue. No mutual exclusion is
 139  * required.
 140  */
 141 extern void cds_wfcq_enqueue(struct cds_wfcq_head *head,
 142                 struct cds_wfcq_tail *tail,
 143                 struct cds_wfcq_node *node);
 144
 145 /*
 146  * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
 147  *
 148  * Content written into the node before enqueue is guaranteed to be
 149  * consistent, but no other memory ordering is ensured.
 150  * It is valid to reuse and free a dequeued node immediately.
 151  * Mutual exlusion with dequeuers is ensured internally.
 152  */
 153 extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking(
 154                 struct cds_wfcq_head *head,
 155                 struct cds_wfcq_tail *tail);
 156
 157 /*
 158  * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 159  *
 160  * Dequeue all nodes from src_q.
 161  * dest_q must be already initialized.
 162  * Content written into the node before enqueue is guaranteed to be
 163  * consistent, but no other memory ordering is ensured.
 164  * Mutual exlusion with dequeuers is ensured internally.
 165  */
 166 extern void cds_wfcq_splice_blocking(
 167                 struct cds_wfcq_head *dest_q_head,
 168                 struct cds_wfcq_tail *dest_q_tail,
 169                 struct cds_wfcq_head *src_q_head,
 170                 struct cds_wfcq_tail *src_q_tail);
 171
 172 /*
 173  * __cds_wfcq_dequeue_blocking:
 174  *
 175  * Content written into the node before enqueue is guaranteed to be
 176  * consistent, but no other memory ordering is ensured.
 177  * It is valid to reuse and free a dequeued node immediately.
 178  * Should be called with cds_wfcq_dequeue_lock() held.
 179  */
 180 extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking(
 181                 struct cds_wfcq_head *head,
 182                 struct cds_wfcq_tail *tail);
 183
 184 /*
 185  * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
 186  *
 187  * Dequeue all nodes from src_q.
 188  * dest_q must be already initialized.
 189  * Content written into the node before enqueue is guaranteed to be
 190  * consistent, but no other memory ordering is ensured.
 191  * Should be called with cds_wfcq_dequeue_lock() held.
 192  */
 193 extern void __cds_wfcq_splice_blocking(
 194                 struct cds_wfcq_head *dest_q_head,
 195                 struct cds_wfcq_tail *dest_q_tail,
 196                 struct cds_wfcq_head *src_q_head,
 197                 struct cds_wfcq_tail *src_q_tail);
 198
 199 /*
 200  * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
 201  *
 202  * Content written into the node before enqueue is guaranteed to be
 203  * consistent, but no other memory ordering is ensured.
 204  * Should be called with cds_wfcq_dequeue_lock() held.
 205  */
 206 extern struct cds_wfcq_node *__cds_wfcq_first_blocking(
 207                 struct cds_wfcq_head *head,
 208                 struct cds_wfcq_tail *tail);
 209
 210 /*
 211  * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
 212  *
 213  * Content written into the node before enqueue is guaranteed to be
 214  * consistent, but no other memory ordering is ensured.
 215  * Should be called with cds_wfcq_dequeue_lock() held.
 216  */
 217 extern struct cds_wfcq_node *__cds_wfcq_next_blocking(
 218                 struct cds_wfcq_head *head,
 219                 struct cds_wfcq_tail *tail,
 220                 struct cds_wfcq_node *node);
 221
 222 #endif /* !_LGPL_SOURCE */
 223
 224 /*
 225  * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
 226  * without dequeuing them.
 227  * @head: head of the queue (struct cds_wfcq_head pointer).
 228  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 229  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 230  *
 231  * Content written into each node before enqueue is guaranteed to be
 232  * consistent, but no other memory ordering is ensured.
 233  * Should be called with cds_wfcq_dequeue_lock() held.
 234  */
 235 #define __cds_wfcq_for_each_blocking(head, tail, node)          \
 236         for (node = __cds_wfcq_first_blocking(head, tail);      \
 237                 node != NULL;                                   \
 238                 node = __cds_wfcq_next_blocking(head, tail, node))
 239
 240 /*
 241  * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
 242  * without dequeuing them. Safe against deletion.
 243  * @head: head of the queue (struct cds_wfcq_head pointer).
 244  * @tail: tail of the queue (struct cds_wfcq_tail pointer).
 245  * @node: iterator on the queue (struct cds_wfcq_node pointer).
 246  * @n: struct cds_wfcq_node pointer holding the next pointer (used
 247  *     internally).
 248  *
 249  * Content written into each node before enqueue is guaranteed to be
 250  * consistent, but no other memory ordering is ensured.
 251  * Should be called with cds_wfcq_dequeue_lock() held.
 252  */
 253 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n)                 \
 254         for (node = __cds_wfcq_first_blocking(head, tail),                     \
 255                         n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
 256                 node != NULL;                                                  \
 257                 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
 258
 259 #ifdef __cplusplus
 260 }
 261 #endif
 262
 263 #endif /* _URCU_WFCQUEUE_H */