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