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