1 #ifndef _URCU_WFCQUEUE_H
2 #define _URCU_WFCQUEUE_H
7 * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue
9 * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
10 * Copyright 2011-2012 - Lai Jiangshan <laijs@cn.fujitsu.com>
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.
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.
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
30 #include <urcu/compiler.h>
31 #include <urcu/arch.h>
38 * Concurrent queue with wait-free enqueue/blocking dequeue.
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.
46 #define CDS_WFCQ_WOULDBLOCK ((void *) -1UL)
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,
56 CDS_WFCQ_STATE_LAST
= (1U << 0),
59 struct cds_wfcq_node
{
60 struct cds_wfcq_node
*next
;
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.
68 struct cds_wfcq_head
{
69 struct cds_wfcq_node node
;
73 struct cds_wfcq_tail
{
74 struct cds_wfcq_node
*p
;
79 #include <urcu/static/wfcqueue.h>
81 #define cds_wfcq_node_init _cds_wfcq_node_init
82 #define cds_wfcq_init _cds_wfcq_init
83 #define cds_wfcq_destroy _cds_wfcq_destroy
84 #define cds_wfcq_empty _cds_wfcq_empty
85 #define cds_wfcq_enqueue _cds_wfcq_enqueue
88 #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock
89 #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock
91 /* Locking performed within cds_wfcq calls. */
92 #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking
93 #define cds_wfcq_dequeue_with_state_blocking \
94 _cds_wfcq_dequeue_with_state_blocking
95 #define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking
96 #define cds_wfcq_first_blocking _cds_wfcq_first_blocking
97 #define cds_wfcq_next_blocking _cds_wfcq_next_blocking
99 /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
100 #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking
101 #define __cds_wfcq_dequeue_with_state_blocking \
102 ___cds_wfcq_dequeue_with_state_blocking
103 #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking
104 #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking
105 #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking
108 * Locking ensured by caller by holding cds_wfcq_dequeue_lock().
109 * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
110 * need to block. splice returns nonzero if it needs to block.
112 #define __cds_wfcq_dequeue_nonblocking ___cds_wfcq_dequeue_nonblocking
113 #define __cds_wfcq_dequeue_with_state_nonblocking \
114 ___cds_wfcq_dequeue_with_state_nonblocking
115 #define __cds_wfcq_splice_nonblocking ___cds_wfcq_splice_nonblocking
116 #define __cds_wfcq_first_nonblocking ___cds_wfcq_first_nonblocking
117 #define __cds_wfcq_next_nonblocking ___cds_wfcq_next_nonblocking
119 #else /* !_LGPL_SOURCE */
122 * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
124 * Synchronization table:
126 * External synchronization techniques described in the API below is
127 * required between pairs marked with "X". No external synchronization
128 * required between pairs marked with "-".
131 * [1] cds_wfcq_enqueue
132 * [2] __cds_wfcq_splice (destination queue)
133 * [3] __cds_wfcq_dequeue
134 * [4] __cds_wfcq_splice (source queue)
135 * [5] __cds_wfcq_first
136 * [6] __cds_wfcq_next
138 * [1] [2] [3] [4] [5] [6]
146 * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
148 * For convenience, cds_wfcq_dequeue_blocking() and
149 * cds_wfcq_splice_blocking() hold the dequeue lock.
151 * Besides locking, mutual exclusion of dequeue, splice and iteration
152 * can be ensured by performing all of those operations from a single
153 * thread, without requiring any lock.
157 * cds_wfcq_node_init: initialize wait-free queue node.
159 extern void cds_wfcq_node_init(struct cds_wfcq_node
*node
);
162 * cds_wfcq_init: initialize wait-free queue. Pair with
163 * cds_wfcq_destroy().
165 extern void cds_wfcq_init(struct cds_wfcq_head
*head
,
166 struct cds_wfcq_tail
*tail
);
169 * cds_wfcq_destroy: destroy wait-free queue. Pair with
172 extern void cds_wfcq_destroy(struct cds_wfcq_head
*head
,
173 struct cds_wfcq_tail
*tail
);
176 * cds_wfcq_empty: return whether wait-free queue is empty.
178 * No memory barrier is issued. No mutual exclusion is required.
180 extern bool cds_wfcq_empty(struct cds_wfcq_head
*head
,
181 struct cds_wfcq_tail
*tail
);
184 * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
186 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head
*head
,
187 struct cds_wfcq_tail
*tail
);
190 * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
192 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head
*head
,
193 struct cds_wfcq_tail
*tail
);
196 * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
198 * Issues a full memory barrier before enqueue. No mutual exclusion is
201 * Returns false if the queue was empty prior to adding the node.
202 * Returns true otherwise.
204 extern bool cds_wfcq_enqueue(struct cds_wfcq_head
*head
,
205 struct cds_wfcq_tail
*tail
,
206 struct cds_wfcq_node
*node
);
209 * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
211 * Content written into the node before enqueue is guaranteed to be
212 * consistent, but no other memory ordering is ensured.
213 * It is valid to reuse and free a dequeued node immediately.
214 * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
217 extern struct cds_wfcq_node
*cds_wfcq_dequeue_blocking(
218 struct cds_wfcq_head
*head
,
219 struct cds_wfcq_tail
*tail
);
222 * cds_wfcq_dequeue_with_state_blocking: dequeue with state.
224 * Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the
225 * last node of the queue into state (CDS_WFCQ_STATE_LAST).
227 extern struct cds_wfcq_node
*cds_wfcq_dequeue_with_state_blocking(
228 struct cds_wfcq_head
*head
,
229 struct cds_wfcq_tail
*tail
,
233 * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
235 * Dequeue all nodes from src_q.
236 * dest_q must be already initialized.
237 * Content written into the node before enqueue is guaranteed to be
238 * consistent, but no other memory ordering is ensured.
239 * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is
242 * Returns enum cds_wfcq_ret which indicates the state of the src or
243 * dest queue. Cannot block.
245 extern enum cds_wfcq_ret
cds_wfcq_splice_blocking(
246 struct cds_wfcq_head
*dest_q_head
,
247 struct cds_wfcq_tail
*dest_q_tail
,
248 struct cds_wfcq_head
*src_q_head
,
249 struct cds_wfcq_tail
*src_q_tail
);
252 * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
254 * Content written into the node before enqueue is guaranteed to be
255 * consistent, but no other memory ordering is ensured.
256 * It is valid to reuse and free a dequeued node immediately.
257 * Dequeue/splice/iteration mutual exclusion should be ensured by the
260 extern struct cds_wfcq_node
*__cds_wfcq_dequeue_blocking(
261 struct cds_wfcq_head
*head
,
262 struct cds_wfcq_tail
*tail
);
265 * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
267 * Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the
268 * last node of the queue into state (CDS_WFCQ_STATE_LAST).
270 extern struct cds_wfcq_node
*__cds_wfcq_dequeue_with_state_blocking(
271 struct cds_wfcq_head
*head
,
272 struct cds_wfcq_tail
*tail
,
276 * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
278 * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
279 * if it needs to block.
281 extern struct cds_wfcq_node
*__cds_wfcq_dequeue_nonblocking(
282 struct cds_wfcq_head
*head
,
283 struct cds_wfcq_tail
*tail
);
286 * __cds_wfcq_dequeue_with_state_blocking: dequeue with state.
288 * Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing
289 * the last node of the queue into state (CDS_WFCQ_STATE_LAST).
291 extern struct cds_wfcq_node
*__cds_wfcq_dequeue_with_state_nonblocking(
292 struct cds_wfcq_head
*head
,
293 struct cds_wfcq_tail
*tail
,
297 * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
299 * Dequeue all nodes from src_q.
300 * dest_q must be already initialized.
301 * Mutual exclusion for src_q should be ensured by the caller as
302 * specified in the "Synchronisation table".
303 * Returns enum cds_wfcq_ret which indicates the state of the src or
304 * dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK.
306 extern enum cds_wfcq_ret
__cds_wfcq_splice_blocking(
307 struct cds_wfcq_head
*dest_q_head
,
308 struct cds_wfcq_tail
*dest_q_tail
,
309 struct cds_wfcq_head
*src_q_head
,
310 struct cds_wfcq_tail
*src_q_tail
);
313 * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
315 * Same as __cds_wfcq_splice_blocking, but returns
316 * CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
318 extern enum cds_wfcq_ret
__cds_wfcq_splice_nonblocking(
319 struct cds_wfcq_head
*dest_q_head
,
320 struct cds_wfcq_tail
*dest_q_tail
,
321 struct cds_wfcq_head
*src_q_head
,
322 struct cds_wfcq_tail
*src_q_tail
);
325 * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
327 * Content written into the node before enqueue is guaranteed to be
328 * consistent, but no other memory ordering is ensured.
329 * Dequeue/splice/iteration mutual exclusion should be ensured by the
332 * Used by for-like iteration macros:
333 * __cds_wfcq_for_each_blocking()
334 * __cds_wfcq_for_each_blocking_safe()
336 * Returns NULL if queue is empty, first node otherwise.
338 extern struct cds_wfcq_node
*__cds_wfcq_first_blocking(
339 struct cds_wfcq_head
*head
,
340 struct cds_wfcq_tail
*tail
);
343 * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
345 * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
348 extern struct cds_wfcq_node
*__cds_wfcq_first_nonblocking(
349 struct cds_wfcq_head
*head
,
350 struct cds_wfcq_tail
*tail
);
353 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
355 * Content written into the node before enqueue is guaranteed to be
356 * consistent, but no other memory ordering is ensured.
357 * Dequeue/splice/iteration mutual exclusion should be ensured by the
360 * Used by for-like iteration macros:
361 * __cds_wfcq_for_each_blocking()
362 * __cds_wfcq_for_each_blocking_safe()
364 * Returns NULL if reached end of queue, non-NULL next queue node
367 extern struct cds_wfcq_node
*__cds_wfcq_next_blocking(
368 struct cds_wfcq_head
*head
,
369 struct cds_wfcq_tail
*tail
,
370 struct cds_wfcq_node
*node
);
373 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
375 * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
378 extern struct cds_wfcq_node
*__cds_wfcq_next_nonblocking(
379 struct cds_wfcq_head
*head
,
380 struct cds_wfcq_tail
*tail
,
381 struct cds_wfcq_node
*node
);
383 #endif /* !_LGPL_SOURCE */
386 * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
387 * without dequeuing them.
388 * @head: head of the queue (struct cds_wfcq_head pointer).
389 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
390 * @node: iterator on the queue (struct cds_wfcq_node pointer).
392 * Content written into each node before enqueue is guaranteed to be
393 * consistent, but no other memory ordering is ensured.
394 * Dequeue/splice/iteration mutual exclusion should be ensured by the
397 #define __cds_wfcq_for_each_blocking(head, tail, node) \
398 for (node = __cds_wfcq_first_blocking(head, tail); \
400 node = __cds_wfcq_next_blocking(head, tail, node))
403 * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
404 * without dequeuing them. Safe against deletion.
405 * @head: head of the queue (struct cds_wfcq_head pointer).
406 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
407 * @node: iterator on the queue (struct cds_wfcq_node pointer).
408 * @n: struct cds_wfcq_node pointer holding the next pointer (used
411 * Content written into each node before enqueue is guaranteed to be
412 * consistent, but no other memory ordering is ensured.
413 * Dequeue/splice/iteration mutual exclusion should be ensured by the
416 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
417 for (node = __cds_wfcq_first_blocking(head, tail), \
418 n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
420 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
426 #endif /* _URCU_WFCQUEUE_H */