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 | ||
8ad4ce58 MD |
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 | ||
47215721 MD |
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 | ||
8ad4ce58 MD |
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). | |
f94061a3 MD |
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. | |
8ad4ce58 MD |
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. | |
1fe734e1 MD |
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. | |
8ad4ce58 MD |
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. | |
1fe734e1 MD |
170 | * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is |
171 | * ensured. | |
8ad4ce58 MD |
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. | |
1fe734e1 MD |
184 | * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is |
185 | * ensured. | |
8ad4ce58 MD |
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 | /* | |
47215721 | 194 | * __cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. |
8ad4ce58 MD |
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. | |
1fe734e1 MD |
199 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
200 | * caller. | |
8ad4ce58 MD |
201 | */ |
202 | extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( | |
203 | struct cds_wfcq_head *head, | |
204 | struct cds_wfcq_tail *tail); | |
205 | ||
47215721 MD |
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 | ||
8ad4ce58 MD |
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. | |
1fe734e1 MD |
223 | * Dequeue/splice/iteration mutual exclusion for src_q should be ensured |
224 | * by the caller. | |
8ad4ce58 MD |
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 | ||
47215721 MD |
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 | ||
8ad4ce58 MD |
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. | |
1fe734e1 MD |
249 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
250 | * caller. | |
f94061a3 MD |
251 | * |
252 | * Used by for-like iteration macros: | |
253 | * __cds_wfcq_for_each_blocking() | |
254 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
255 | */ |
256 | extern struct cds_wfcq_node *__cds_wfcq_first_blocking( | |
257 | struct cds_wfcq_head *head, | |
258 | struct cds_wfcq_tail *tail); | |
259 | ||
47215721 MD |
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 | ||
8ad4ce58 MD |
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. | |
1fe734e1 MD |
275 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
276 | * caller. | |
f94061a3 MD |
277 | * |
278 | * Used by for-like iteration macros: | |
279 | * __cds_wfcq_for_each_blocking() | |
280 | * __cds_wfcq_for_each_blocking_safe() | |
8ad4ce58 MD |
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 | ||
47215721 MD |
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 | ||
8ad4ce58 MD |
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. | |
1fe734e1 MD |
309 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
310 | * caller. | |
8ad4ce58 MD |
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. | |
1fe734e1 MD |
328 | * Dequeue/splice/iteration mutual exclusion should be ensured by the |
329 | * caller. | |
8ad4ce58 MD |
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 */ |