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