Commit | Line | Data |
---|---|---|
8ad4ce58 MD |
1 | #ifndef _URCU_WFCQUEUE_H |
2 | #define _URCU_WFCQUEUE_H | |
3 | ||
4 | /* | |
47215721 | 5 | * urcu/wfcqueue.h |
8ad4ce58 MD |
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 | * | |
ebfd2673 MD |
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. | |
8ad4ce58 MD |
44 | */ |
45 | ||
47215721 MD |
46 | #define CDS_WFCQ_WOULDBLOCK ((void *) -1UL) |
47 | ||
23773356 | 48 | enum cds_wfcq_ret { |
f878b49e | 49 | CDS_WFCQ_RET_WOULDBLOCK = -1, |
23773356 MD |
50 | CDS_WFCQ_RET_DEST_EMPTY = 0, |
51 | CDS_WFCQ_RET_DEST_NON_EMPTY = 1, | |
52 | CDS_WFCQ_RET_SRC_EMPTY = 2, | |
53 | }; | |
54 | ||
eec791af MD |
55 | enum cds_wfcq_state { |
56 | CDS_WFCQ_STATE_LAST = (1U << 0), | |
57 | }; | |
58 | ||
8ad4ce58 MD |
59 | struct cds_wfcq_node { |
60 | struct cds_wfcq_node *next; | |
61 | }; | |
62 | ||
63 | /* | |
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. | |
67 | */ | |
68 | struct cds_wfcq_head { | |
69 | struct cds_wfcq_node node; | |
70 | pthread_mutex_t lock; | |
71 | }; | |
72 | ||
73 | struct cds_wfcq_tail { | |
74 | struct cds_wfcq_node *p; | |
75 | }; | |
76 | ||
77 | #ifdef _LGPL_SOURCE | |
78 | ||
79 | #include <urcu/static/wfcqueue.h> | |
80 | ||
81 | #define cds_wfcq_node_init _cds_wfcq_node_init | |
82 | #define cds_wfcq_init _cds_wfcq_init | |
83 | #define cds_wfcq_empty _cds_wfcq_empty | |
84 | #define cds_wfcq_enqueue _cds_wfcq_enqueue | |
85 | ||
86 | /* Dequeue locking */ | |
87 | #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock | |
88 | #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock | |
89 | ||
90 | /* Locking performed within cds_wfcq calls. */ | |
91 | #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking | |
eec791af MD |
92 | #define cds_wfcq_dequeue_with_state_blocking \ |
93 | _cds_wfcq_dequeue_with_state_blocking | |
8ad4ce58 MD |
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 | |
97 | ||
98 | /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */ | |
99 | #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking | |
eec791af MD |
100 | #define __cds_wfcq_dequeue_with_state_blocking \ |
101 | ___cds_wfcq_dequeue_with_state_blocking | |
8ad4ce58 MD |
102 | #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking |
103 | #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking | |
104 | #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking | |
105 | ||
47215721 MD |
106 | /* |
107 | * Locking ensured by caller by holding cds_wfcq_dequeue_lock(). | |
108 | * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they | |
109 | * need to block. splice returns nonzero if it needs to block. | |
110 | */ | |
111 | #define __cds_wfcq_dequeue_nonblocking ___cds_wfcq_dequeue_nonblocking | |
eec791af MD |
112 | #define __cds_wfcq_dequeue_with_state_nonblocking \ |
113 | ___cds_wfcq_dequeue_with_state_nonblocking | |
47215721 MD |
114 | #define __cds_wfcq_splice_nonblocking ___cds_wfcq_splice_nonblocking |
115 | #define __cds_wfcq_first_nonblocking ___cds_wfcq_first_nonblocking | |
116 | #define __cds_wfcq_next_nonblocking ___cds_wfcq_next_nonblocking | |
117 | ||
8ad4ce58 MD |
118 | #else /* !_LGPL_SOURCE */ |
119 | ||
120 | /* | |
121 | * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API | |
122 | * | |
f878b49e MD |
123 | * Synchronization table: |
124 | * | |
125 | * External synchronization techniques described in the API below is | |
126 | * required between pairs marked with "X". No external synchronization | |
127 | * required between pairs marked with "-". | |
128 | * | |
129 | * Legend: | |
130 | * [1] cds_wfcq_enqueue | |
131 | * [2] __cds_wfcq_splice (destination queue) | |
132 | * [3] __cds_wfcq_dequeue | |
133 | * [4] __cds_wfcq_splice (source queue) | |
134 | * [5] __cds_wfcq_first | |
135 | * [6] __cds_wfcq_next | |
136 | * | |
137 | * [1] [2] [3] [4] [5] [6] | |
138 | * [1] - - - - - - | |
139 | * [2] - - - - - - | |
140 | * [3] - - X X X X | |
141 | * [4] - - X - X X | |
142 | * [5] - - X X - - | |
143 | * [6] - - X X - - | |
144 | * | |
8ad4ce58 MD |
145 | * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock(). |
146 | * | |
147 | * For convenience, cds_wfcq_dequeue_blocking() and | |
148 | * cds_wfcq_splice_blocking() hold the dequeue lock. | |
1fe734e1 MD |
149 | * |
150 | * Besides locking, mutual exclusion of dequeue, splice and iteration | |
151 | * can be ensured by performing all of those operations from a single | |
152 | * thread, without requiring any lock. | |
8ad4ce58 MD |
153 | */ |
154 | ||
155 | /* | |
156 | * cds_wfcq_node_init: initialize wait-free queue node. | |
157 | */ | |
158 | extern void cds_wfcq_node_init(struct cds_wfcq_node *node); | |
159 | ||
160 | /* | |
161 | * cds_wfcq_init: initialize wait-free queue. | |
162 | */ | |
163 | extern void cds_wfcq_init(struct cds_wfcq_head *head, | |
164 | struct cds_wfcq_tail *tail); | |
165 | ||
166 | /* | |
167 | * cds_wfcq_empty: return whether wait-free queue is empty. | |
168 | * | |
169 | * No memory barrier is issued. No mutual exclusion is required. | |
170 | */ | |
171 | extern bool cds_wfcq_empty(struct cds_wfcq_head *head, | |
172 | struct cds_wfcq_tail *tail); | |
173 | ||
174 | /* | |
175 | * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock. | |
176 | */ | |
177 | extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head, | |
178 | struct cds_wfcq_tail *tail); | |
179 | ||
180 | /* | |
181 | * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock. | |
182 | */ | |
183 | extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head, | |
184 | struct cds_wfcq_tail *tail); | |
185 | ||
186 | /* | |
187 | * cds_wfcq_enqueue: enqueue a node into a wait-free queue. | |
188 | * | |
189 | * Issues a full memory barrier before enqueue. No mutual exclusion is | |
190 | * required. | |
23773356 MD |
191 | * |
192 | * Returns false if the queue was empty prior to adding the node. | |
193 | * Returns true otherwise. | |
8ad4ce58 | 194 | */ |
23773356 | 195 | extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head, |
8ad4ce58 MD |
196 | struct cds_wfcq_tail *tail, |
197 | struct cds_wfcq_node *node); | |
198 | ||
199 | /* | |
200 | * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. | |
201 | * | |
202 | * Content written into the node before enqueue is guaranteed to be | |
203 | * consistent, but no other memory ordering is ensured. | |
204 | * It is valid to reuse and free a dequeued node immediately. | |
ffa11a18 | 205 | * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is |
1fe734e1 | 206 | * ensured. |
8ad4ce58 MD |
207 | */ |
208 | extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking( | |
209 | struct cds_wfcq_head *head, | |
210 | struct cds_wfcq_tail *tail); | |
211 | ||
eec791af MD |
212 | /* |
213 | * cds_wfcq_dequeue_with_state_blocking: dequeue with state. | |
214 | * | |
215 | * Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the | |
216 | * last node of the queue into state (CDS_WFCQ_STATE_LAST). | |
217 | */ | |
218 | extern struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking( | |
219 | struct cds_wfcq_head *head, | |
220 | struct cds_wfcq_tail *tail, | |
221 | int *state); | |
222 | ||
8ad4ce58 MD |
223 | /* |
224 | * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
225 | * | |
226 | * Dequeue all nodes from src_q. | |
227 | * dest_q must be already initialized. | |
228 | * Content written into the node before enqueue is guaranteed to be | |
229 | * consistent, but no other memory ordering is ensured. | |
ffa11a18 | 230 | * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is |
1fe734e1 | 231 | * ensured. |
23773356 MD |
232 | * |
233 | * Returns enum cds_wfcq_ret which indicates the state of the src or | |
234 | * dest queue. Cannot block. | |
8ad4ce58 | 235 | */ |
23773356 | 236 | extern enum cds_wfcq_ret cds_wfcq_splice_blocking( |
8ad4ce58 MD |
237 | struct cds_wfcq_head *dest_q_head, |
238 | struct cds_wfcq_tail *dest_q_tail, | |
239 | struct cds_wfcq_head *src_q_head, | |
240 | struct cds_wfcq_tail *src_q_tail); | |
241 | ||
242 | /* | |
47215721 | 243 | * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. |
8ad4ce58 MD |
244 | * |
245 | * Content written into the node before enqueue is guaranteed to be | |
246 | * consistent, but no other memory ordering is ensured. | |
247 | * It is valid to reuse and free a dequeued node immediately. | |
1fe734e1 MD |
248 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
249 | * caller. | |
8ad4ce58 MD |
250 | */ |
251 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( | |
252 | struct cds_wfcq_head *head, | |
253 | struct cds_wfcq_tail *tail); | |
254 | ||
eec791af MD |
255 | /* |
256 | * __cds_wfcq_dequeue_with_state_blocking: dequeue with state. | |
257 | * | |
258 | * Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the | |
259 | * last node of the queue into state (CDS_WFCQ_STATE_LAST). | |
260 | */ | |
261 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking( | |
262 | struct cds_wfcq_head *head, | |
263 | struct cds_wfcq_tail *tail, | |
264 | int *state); | |
265 | ||
47215721 MD |
266 | /* |
267 | * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue. | |
268 | * | |
269 | * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK | |
270 | * if it needs to block. | |
271 | */ | |
272 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking( | |
273 | struct cds_wfcq_head *head, | |
274 | struct cds_wfcq_tail *tail); | |
275 | ||
eec791af MD |
276 | /* |
277 | * __cds_wfcq_dequeue_with_state_blocking: dequeue with state. | |
278 | * | |
279 | * Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing | |
280 | * the last node of the queue into state (CDS_WFCQ_STATE_LAST). | |
281 | */ | |
282 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking( | |
283 | struct cds_wfcq_head *head, | |
284 | struct cds_wfcq_tail *tail, | |
285 | int *state); | |
286 | ||
8ad4ce58 MD |
287 | /* |
288 | * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
289 | * | |
290 | * Dequeue all nodes from src_q. | |
291 | * dest_q must be already initialized. | |
f878b49e MD |
292 | * Mutual exclusion for src_q should be ensured by the caller as |
293 | * specified in the "Synchronisation table". | |
23773356 | 294 | * Returns enum cds_wfcq_ret which indicates the state of the src or |
f878b49e | 295 | * dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK. |
8ad4ce58 | 296 | */ |
23773356 | 297 | extern enum cds_wfcq_ret __cds_wfcq_splice_blocking( |
8ad4ce58 MD |
298 | struct cds_wfcq_head *dest_q_head, |
299 | struct cds_wfcq_tail *dest_q_tail, | |
300 | struct cds_wfcq_head *src_q_head, | |
301 | struct cds_wfcq_tail *src_q_tail); | |
302 | ||
47215721 MD |
303 | /* |
304 | * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q. | |
305 | * | |
23773356 MD |
306 | * Same as __cds_wfcq_splice_blocking, but returns |
307 | * CDS_WFCQ_RET_WOULDBLOCK if it needs to block. | |
47215721 | 308 | */ |
23773356 | 309 | extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking( |
47215721 MD |
310 | struct cds_wfcq_head *dest_q_head, |
311 | struct cds_wfcq_tail *dest_q_tail, | |
312 | struct cds_wfcq_head *src_q_head, | |
313 | struct cds_wfcq_tail *src_q_tail); | |
314 | ||
8ad4ce58 MD |
315 | /* |
316 | * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing. | |
317 | * | |
318 | * Content written into the node before enqueue is guaranteed to be | |
319 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
320 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
321 | * caller. | |
f94061a3 MD |
322 | * |
323 | * Used by for-like iteration macros: | |
324 | * __cds_wfcq_for_each_blocking() | |
325 | * __cds_wfcq_for_each_blocking_safe() | |
131a29a6 MD |
326 | * |
327 | * Returns NULL if queue is empty, first node otherwise. | |
8ad4ce58 MD |
328 | */ |
329 | extern struct cds_wfcq_node *__cds_wfcq_first_blocking( | |
330 | struct cds_wfcq_head *head, | |
331 | struct cds_wfcq_tail *tail); | |
332 | ||
47215721 MD |
333 | /* |
334 | * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing. | |
335 | * | |
336 | * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if | |
337 | * it needs to block. | |
338 | */ | |
339 | extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking( | |
340 | struct cds_wfcq_head *head, | |
341 | struct cds_wfcq_tail *tail); | |
342 | ||
8ad4ce58 MD |
343 | /* |
344 | * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. | |
345 | * | |
346 | * Content written into the node before enqueue is guaranteed to be | |
347 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
348 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
349 | * caller. | |
f94061a3 MD |
350 | * |
351 | * Used by for-like iteration macros: | |
352 | * __cds_wfcq_for_each_blocking() | |
353 | * __cds_wfcq_for_each_blocking_safe() | |
131a29a6 MD |
354 | * |
355 | * Returns NULL if reached end of queue, non-NULL next queue node | |
356 | * otherwise. | |
8ad4ce58 MD |
357 | */ |
358 | extern struct cds_wfcq_node *__cds_wfcq_next_blocking( | |
359 | struct cds_wfcq_head *head, | |
360 | struct cds_wfcq_tail *tail, | |
361 | struct cds_wfcq_node *node); | |
362 | ||
47215721 MD |
363 | /* |
364 | * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. | |
365 | * | |
366 | * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if | |
367 | * it needs to block. | |
368 | */ | |
369 | extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking( | |
370 | struct cds_wfcq_head *head, | |
371 | struct cds_wfcq_tail *tail, | |
372 | struct cds_wfcq_node *node); | |
373 | ||
8ad4ce58 MD |
374 | #endif /* !_LGPL_SOURCE */ |
375 | ||
376 | /* | |
377 | * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue, | |
378 | * without dequeuing them. | |
379 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
380 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
381 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
382 | * | |
383 | * Content written into each node before enqueue is guaranteed to be | |
384 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
385 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
386 | * caller. | |
8ad4ce58 MD |
387 | */ |
388 | #define __cds_wfcq_for_each_blocking(head, tail, node) \ | |
389 | for (node = __cds_wfcq_first_blocking(head, tail); \ | |
390 | node != NULL; \ | |
391 | node = __cds_wfcq_next_blocking(head, tail, node)) | |
392 | ||
393 | /* | |
394 | * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue, | |
395 | * without dequeuing them. Safe against deletion. | |
396 | * @head: head of the queue (struct cds_wfcq_head pointer). | |
397 | * @tail: tail of the queue (struct cds_wfcq_tail pointer). | |
398 | * @node: iterator on the queue (struct cds_wfcq_node pointer). | |
399 | * @n: struct cds_wfcq_node pointer holding the next pointer (used | |
400 | * internally). | |
401 | * | |
402 | * Content written into each node before enqueue is guaranteed to be | |
403 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
404 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
405 | * caller. | |
8ad4ce58 MD |
406 | */ |
407 | #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \ | |
408 | for (node = __cds_wfcq_first_blocking(head, tail), \ | |
409 | n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL); \ | |
410 | node != NULL; \ | |
411 | node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL)) | |
412 | ||
413 | #ifdef __cplusplus | |
414 | } | |
415 | #endif | |
416 | ||
417 | #endif /* _URCU_WFCQUEUE_H */ |