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,
55 struct cds_wfcq_node
{
56 struct cds_wfcq_node
*next
;
60 * Do not put head and tail on the same cache-line if concurrent
61 * enqueue/dequeue are expected from many CPUs. This eliminates
62 * false-sharing between enqueue and dequeue.
64 struct cds_wfcq_head
{
65 struct cds_wfcq_node node
;
69 struct cds_wfcq_tail
{
70 struct cds_wfcq_node
*p
;
75 #include <urcu/static/wfcqueue.h>
77 #define cds_wfcq_node_init _cds_wfcq_node_init
78 #define cds_wfcq_init _cds_wfcq_init
79 #define cds_wfcq_empty _cds_wfcq_empty
80 #define cds_wfcq_enqueue _cds_wfcq_enqueue
83 #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock
84 #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock
86 /* Locking performed within cds_wfcq calls. */
87 #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking
88 #define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking
89 #define cds_wfcq_first_blocking _cds_wfcq_first_blocking
90 #define cds_wfcq_next_blocking _cds_wfcq_next_blocking
92 /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */
93 #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking
94 #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking
95 #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking
96 #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking
99 * Locking ensured by caller by holding cds_wfcq_dequeue_lock().
100 * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they
101 * need to block. splice returns nonzero if it needs to block.
103 #define __cds_wfcq_dequeue_nonblocking ___cds_wfcq_dequeue_nonblocking
104 #define __cds_wfcq_splice_nonblocking ___cds_wfcq_splice_nonblocking
105 #define __cds_wfcq_first_nonblocking ___cds_wfcq_first_nonblocking
106 #define __cds_wfcq_next_nonblocking ___cds_wfcq_next_nonblocking
108 #else /* !_LGPL_SOURCE */
111 * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API
113 * Unless otherwise stated, the caller must ensure mutual exclusion of
114 * queue update operations "dequeue" and "splice" (for source queue).
115 * Queue read operations "first" and "next", which are used by
116 * "for_each" iterations, need to be protected against concurrent
117 * "dequeue" and "splice" (for source queue) by the caller.
118 * "enqueue", "splice" (for destination queue), and "empty" are the only
119 * operations that can be used without any mutual exclusion.
120 * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock().
122 * For convenience, cds_wfcq_dequeue_blocking() and
123 * cds_wfcq_splice_blocking() hold the dequeue lock.
125 * Besides locking, mutual exclusion of dequeue, splice and iteration
126 * can be ensured by performing all of those operations from a single
127 * thread, without requiring any lock.
131 * cds_wfcq_node_init: initialize wait-free queue node.
133 extern void cds_wfcq_node_init(struct cds_wfcq_node
*node
);
136 * cds_wfcq_init: initialize wait-free queue.
138 extern void cds_wfcq_init(struct cds_wfcq_head
*head
,
139 struct cds_wfcq_tail
*tail
);
142 * cds_wfcq_empty: return whether wait-free queue is empty.
144 * No memory barrier is issued. No mutual exclusion is required.
146 extern bool cds_wfcq_empty(struct cds_wfcq_head
*head
,
147 struct cds_wfcq_tail
*tail
);
150 * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock.
152 extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head
*head
,
153 struct cds_wfcq_tail
*tail
);
156 * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock.
158 extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head
*head
,
159 struct cds_wfcq_tail
*tail
);
162 * cds_wfcq_enqueue: enqueue a node into a wait-free queue.
164 * Issues a full memory barrier before enqueue. No mutual exclusion is
167 * Returns false if the queue was empty prior to adding the node.
168 * Returns true otherwise.
170 extern bool cds_wfcq_enqueue(struct cds_wfcq_head
*head
,
171 struct cds_wfcq_tail
*tail
,
172 struct cds_wfcq_node
*node
);
175 * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
177 * Content written into the node before enqueue is guaranteed to be
178 * consistent, but no other memory ordering is ensured.
179 * It is valid to reuse and free a dequeued node immediately.
180 * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
183 extern struct cds_wfcq_node
*cds_wfcq_dequeue_blocking(
184 struct cds_wfcq_head
*head
,
185 struct cds_wfcq_tail
*tail
);
188 * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
190 * Dequeue all nodes from src_q.
191 * dest_q must be already initialized.
192 * Content written into the node before enqueue is guaranteed to be
193 * consistent, but no other memory ordering is ensured.
194 * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is
197 * Returns enum cds_wfcq_ret which indicates the state of the src or
198 * dest queue. Cannot block.
200 extern enum cds_wfcq_ret
cds_wfcq_splice_blocking(
201 struct cds_wfcq_head
*dest_q_head
,
202 struct cds_wfcq_tail
*dest_q_tail
,
203 struct cds_wfcq_head
*src_q_head
,
204 struct cds_wfcq_tail
*src_q_tail
);
207 * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue.
209 * Content written into the node before enqueue is guaranteed to be
210 * consistent, but no other memory ordering is ensured.
211 * It is valid to reuse and free a dequeued node immediately.
212 * Dequeue/splice/iteration mutual exclusion should be ensured by the
215 extern struct cds_wfcq_node
*__cds_wfcq_dequeue_blocking(
216 struct cds_wfcq_head
*head
,
217 struct cds_wfcq_tail
*tail
);
220 * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue.
222 * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK
223 * if it needs to block.
225 extern struct cds_wfcq_node
*__cds_wfcq_dequeue_nonblocking(
226 struct cds_wfcq_head
*head
,
227 struct cds_wfcq_tail
*tail
);
230 * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q.
232 * Dequeue all nodes from src_q.
233 * dest_q must be already initialized.
234 * Content written into the node before enqueue is guaranteed to be
235 * consistent, but no other memory ordering is ensured.
236 * Dequeue/splice/iteration mutual exclusion for src_q should be ensured
239 * Returns enum cds_wfcq_ret which indicates the state of the src or
240 * dest queue. Cannot block.
242 extern enum cds_wfcq_ret
__cds_wfcq_splice_blocking(
243 struct cds_wfcq_head
*dest_q_head
,
244 struct cds_wfcq_tail
*dest_q_tail
,
245 struct cds_wfcq_head
*src_q_head
,
246 struct cds_wfcq_tail
*src_q_tail
);
249 * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q.
251 * Same as __cds_wfcq_splice_blocking, but returns
252 * CDS_WFCQ_RET_WOULDBLOCK if it needs to block.
254 extern enum cds_wfcq_ret
__cds_wfcq_splice_nonblocking(
255 struct cds_wfcq_head
*dest_q_head
,
256 struct cds_wfcq_tail
*dest_q_tail
,
257 struct cds_wfcq_head
*src_q_head
,
258 struct cds_wfcq_tail
*src_q_tail
);
261 * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing.
263 * Content written into the node before enqueue is guaranteed to be
264 * consistent, but no other memory ordering is ensured.
265 * Dequeue/splice/iteration mutual exclusion should be ensured by the
268 * Used by for-like iteration macros:
269 * __cds_wfcq_for_each_blocking()
270 * __cds_wfcq_for_each_blocking_safe()
272 extern struct cds_wfcq_node
*__cds_wfcq_first_blocking(
273 struct cds_wfcq_head
*head
,
274 struct cds_wfcq_tail
*tail
);
277 * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing.
279 * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if
282 extern struct cds_wfcq_node
*__cds_wfcq_first_nonblocking(
283 struct cds_wfcq_head
*head
,
284 struct cds_wfcq_tail
*tail
);
287 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
289 * Content written into the node before enqueue is guaranteed to be
290 * consistent, but no other memory ordering is ensured.
291 * Dequeue/splice/iteration mutual exclusion should be ensured by the
294 * Used by for-like iteration macros:
295 * __cds_wfcq_for_each_blocking()
296 * __cds_wfcq_for_each_blocking_safe()
298 extern struct cds_wfcq_node
*__cds_wfcq_next_blocking(
299 struct cds_wfcq_head
*head
,
300 struct cds_wfcq_tail
*tail
,
301 struct cds_wfcq_node
*node
);
304 * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing.
306 * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if
309 extern struct cds_wfcq_node
*__cds_wfcq_next_nonblocking(
310 struct cds_wfcq_head
*head
,
311 struct cds_wfcq_tail
*tail
,
312 struct cds_wfcq_node
*node
);
314 #endif /* !_LGPL_SOURCE */
317 * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue,
318 * without dequeuing them.
319 * @head: head of the queue (struct cds_wfcq_head pointer).
320 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
321 * @node: iterator on the queue (struct cds_wfcq_node pointer).
323 * Content written into each node before enqueue is guaranteed to be
324 * consistent, but no other memory ordering is ensured.
325 * Dequeue/splice/iteration mutual exclusion should be ensured by the
328 #define __cds_wfcq_for_each_blocking(head, tail, node) \
329 for (node = __cds_wfcq_first_blocking(head, tail); \
331 node = __cds_wfcq_next_blocking(head, tail, node))
334 * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue,
335 * without dequeuing them. Safe against deletion.
336 * @head: head of the queue (struct cds_wfcq_head pointer).
337 * @tail: tail of the queue (struct cds_wfcq_tail pointer).
338 * @node: iterator on the queue (struct cds_wfcq_node pointer).
339 * @n: struct cds_wfcq_node pointer holding the next pointer (used
342 * Content written into each node before enqueue is guaranteed to be
343 * consistent, but no other memory ordering is ensured.
344 * Dequeue/splice/iteration mutual exclusion should be ensured by the
347 #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \
348 for (node = __cds_wfcq_first_blocking(head, tail), \
349 n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \
351 node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL))
357 #endif /* _URCU_WFCQUEUE_H */