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 MD |
48 | enum cds_wfcq_ret { |
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, | |
53 | }; | |
54 | ||
8ad4ce58 MD |
55 | struct cds_wfcq_node { |
56 | struct cds_wfcq_node *next; | |
57 | }; | |
58 | ||
59 | /* | |
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. | |
63 | */ | |
64 | struct cds_wfcq_head { | |
65 | struct cds_wfcq_node node; | |
66 | pthread_mutex_t lock; | |
67 | }; | |
68 | ||
69 | struct cds_wfcq_tail { | |
70 | struct cds_wfcq_node *p; | |
71 | }; | |
72 | ||
73 | #ifdef _LGPL_SOURCE | |
74 | ||
75 | #include <urcu/static/wfcqueue.h> | |
76 | ||
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 | |
81 | ||
82 | /* Dequeue locking */ | |
83 | #define cds_wfcq_dequeue_lock _cds_wfcq_dequeue_lock | |
84 | #define cds_wfcq_dequeue_unlock _cds_wfcq_dequeue_unlock | |
85 | ||
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 | |
91 | ||
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 | |
97 | ||
47215721 MD |
98 | /* |
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. | |
102 | */ | |
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 | |
107 | ||
8ad4ce58 MD |
108 | #else /* !_LGPL_SOURCE */ |
109 | ||
110 | /* | |
111 | * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API | |
112 | * | |
113 | * Unless otherwise stated, the caller must ensure mutual exclusion of | |
114 | * queue update operations "dequeue" and "splice" (for source queue). | |
f94061a3 MD |
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. | |
8ad4ce58 MD |
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(). | |
121 | * | |
122 | * For convenience, cds_wfcq_dequeue_blocking() and | |
123 | * cds_wfcq_splice_blocking() hold the dequeue lock. | |
1fe734e1 MD |
124 | * |
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. | |
8ad4ce58 MD |
128 | */ |
129 | ||
130 | /* | |
131 | * cds_wfcq_node_init: initialize wait-free queue node. | |
132 | */ | |
133 | extern void cds_wfcq_node_init(struct cds_wfcq_node *node); | |
134 | ||
135 | /* | |
136 | * cds_wfcq_init: initialize wait-free queue. | |
137 | */ | |
138 | extern void cds_wfcq_init(struct cds_wfcq_head *head, | |
139 | struct cds_wfcq_tail *tail); | |
140 | ||
141 | /* | |
142 | * cds_wfcq_empty: return whether wait-free queue is empty. | |
143 | * | |
144 | * No memory barrier is issued. No mutual exclusion is required. | |
145 | */ | |
146 | extern bool cds_wfcq_empty(struct cds_wfcq_head *head, | |
147 | struct cds_wfcq_tail *tail); | |
148 | ||
149 | /* | |
150 | * cds_wfcq_dequeue_lock: take the dequeue mutual exclusion lock. | |
151 | */ | |
152 | extern void cds_wfcq_dequeue_lock(struct cds_wfcq_head *head, | |
153 | struct cds_wfcq_tail *tail); | |
154 | ||
155 | /* | |
156 | * cds_wfcq_dequeue_unlock: release the dequeue mutual exclusion lock. | |
157 | */ | |
158 | extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head, | |
159 | struct cds_wfcq_tail *tail); | |
160 | ||
161 | /* | |
162 | * cds_wfcq_enqueue: enqueue a node into a wait-free queue. | |
163 | * | |
164 | * Issues a full memory barrier before enqueue. No mutual exclusion is | |
165 | * required. | |
23773356 MD |
166 | * |
167 | * Returns false if the queue was empty prior to adding the node. | |
168 | * Returns true otherwise. | |
8ad4ce58 | 169 | */ |
23773356 | 170 | extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head, |
8ad4ce58 MD |
171 | struct cds_wfcq_tail *tail, |
172 | struct cds_wfcq_node *node); | |
173 | ||
174 | /* | |
175 | * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. | |
176 | * | |
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. | |
1fe734e1 MD |
180 | * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is |
181 | * ensured. | |
8ad4ce58 MD |
182 | */ |
183 | extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking( | |
184 | struct cds_wfcq_head *head, | |
185 | struct cds_wfcq_tail *tail); | |
186 | ||
187 | /* | |
188 | * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
189 | * | |
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. | |
1fe734e1 MD |
194 | * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is |
195 | * ensured. | |
23773356 MD |
196 | * |
197 | * Returns enum cds_wfcq_ret which indicates the state of the src or | |
198 | * dest queue. Cannot block. | |
8ad4ce58 | 199 | */ |
23773356 | 200 | extern enum cds_wfcq_ret cds_wfcq_splice_blocking( |
8ad4ce58 MD |
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); | |
205 | ||
206 | /* | |
47215721 | 207 | * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. |
8ad4ce58 MD |
208 | * |
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. | |
1fe734e1 MD |
212 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
213 | * caller. | |
8ad4ce58 MD |
214 | */ |
215 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( | |
216 | struct cds_wfcq_head *head, | |
217 | struct cds_wfcq_tail *tail); | |
218 | ||
47215721 MD |
219 | /* |
220 | * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue. | |
221 | * | |
222 | * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK | |
223 | * if it needs to block. | |
224 | */ | |
225 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking( | |
226 | struct cds_wfcq_head *head, | |
227 | struct cds_wfcq_tail *tail); | |
228 | ||
8ad4ce58 MD |
229 | /* |
230 | * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. | |
231 | * | |
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. | |
1fe734e1 MD |
236 | * Dequeue/splice/iteration mutual exclusion for src_q should be ensured |
237 | * by the caller. | |
23773356 MD |
238 | * |
239 | * Returns enum cds_wfcq_ret which indicates the state of the src or | |
240 | * dest queue. Cannot block. | |
8ad4ce58 | 241 | */ |
23773356 | 242 | extern enum cds_wfcq_ret __cds_wfcq_splice_blocking( |
8ad4ce58 MD |
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); | |
247 | ||
47215721 MD |
248 | /* |
249 | * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q. | |
250 | * | |
23773356 MD |
251 | * Same as __cds_wfcq_splice_blocking, but returns |
252 | * CDS_WFCQ_RET_WOULDBLOCK if it needs to block. | |
47215721 | 253 | */ |
23773356 | 254 | extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking( |
47215721 MD |
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); | |
259 | ||
8ad4ce58 MD |
260 | /* |
261 | * __cds_wfcq_first_blocking: get first node of a queue, without dequeuing. | |
262 | * | |
263 | * Content written into the node before enqueue is guaranteed to be | |
264 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
265 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
266 | * caller. | |
f94061a3 MD |
267 | * |
268 | * Used by for-like iteration macros: | |
269 | * __cds_wfcq_for_each_blocking() | |
270 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
271 | */ |
272 | extern struct cds_wfcq_node *__cds_wfcq_first_blocking( | |
273 | struct cds_wfcq_head *head, | |
274 | struct cds_wfcq_tail *tail); | |
275 | ||
47215721 MD |
276 | /* |
277 | * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing. | |
278 | * | |
279 | * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if | |
280 | * it needs to block. | |
281 | */ | |
282 | extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking( | |
283 | struct cds_wfcq_head *head, | |
284 | struct cds_wfcq_tail *tail); | |
285 | ||
8ad4ce58 MD |
286 | /* |
287 | * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. | |
288 | * | |
289 | * Content written into the node before enqueue is guaranteed to be | |
290 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
291 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
292 | * caller. | |
f94061a3 MD |
293 | * |
294 | * Used by for-like iteration macros: | |
295 | * __cds_wfcq_for_each_blocking() | |
296 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
297 | */ |
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); | |
302 | ||
47215721 MD |
303 | /* |
304 | * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. | |
305 | * | |
306 | * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if | |
307 | * it needs to block. | |
308 | */ | |
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); | |
313 | ||
8ad4ce58 MD |
314 | #endif /* !_LGPL_SOURCE */ |
315 | ||
316 | /* | |
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). | |
322 | * | |
323 | * Content written into each node before enqueue is guaranteed to be | |
324 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
325 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
326 | * caller. | |
8ad4ce58 MD |
327 | */ |
328 | #define __cds_wfcq_for_each_blocking(head, tail, node) \ | |
329 | for (node = __cds_wfcq_first_blocking(head, tail); \ | |
330 | node != NULL; \ | |
331 | node = __cds_wfcq_next_blocking(head, tail, node)) | |
332 | ||
333 | /* | |
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 | |
340 | * internally). | |
341 | * | |
342 | * Content written into each node before enqueue is guaranteed to be | |
343 | * consistent, but no other memory ordering is ensured. | |
1fe734e1 MD |
344 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
345 | * caller. | |
8ad4ce58 MD |
346 | */ |
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); \ | |
350 | node != NULL; \ | |
351 | node = n, n = (node ? __cds_wfcq_next_blocking(head, tail, node) : NULL)) | |
352 | ||
353 | #ifdef __cplusplus | |
354 | } | |
355 | #endif | |
356 | ||
357 | #endif /* _URCU_WFCQUEUE_H */ |