Commit | Line | Data |
---|---|---|
d3d3857f MJ |
1 | // SPDX-FileCopyrightText: 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com> |
2 | // | |
3 | // SPDX-License-Identifier: LGPL-2.1-or-later | |
4 | ||
cb3f3d6b MD |
5 | #ifndef _URCU_WFSTACK_H |
6 | #define _URCU_WFSTACK_H | |
7 | ||
8 | /* | |
edac6b69 | 9 | * Userspace RCU library - Stack with wait-free push, blocking traversal. |
cb3f3d6b MD |
10 | */ |
11 | ||
12 | #include <pthread.h> | |
edac6b69 | 13 | #include <stdbool.h> |
cb3f3d6b MD |
14 | #include <urcu/compiler.h> |
15 | ||
16 | #ifdef __cplusplus | |
17 | extern "C" { | |
18 | #endif | |
19 | ||
edac6b69 MD |
20 | /* |
21 | * Stack with wait-free push, blocking traversal. | |
22 | * | |
23 | * Stack implementing push, pop, pop_all operations, as well as iterator | |
24 | * on the stack head returned by pop_all. | |
25 | * | |
c97c6ce5 MD |
26 | * Wait-free operations: cds_wfs_push, __cds_wfs_pop_all, cds_wfs_empty, |
27 | * cds_wfs_first. | |
28 | * Blocking operations: cds_wfs_pop, cds_wfs_pop_all, cds_wfs_next, | |
29 | * iteration on stack head returned by pop_all. | |
edac6b69 MD |
30 | * |
31 | * Synchronization table: | |
32 | * | |
33 | * External synchronization techniques described in the API below is | |
34 | * required between pairs marked with "X". No external synchronization | |
35 | * required between pairs marked with "-". | |
36 | * | |
37 | * cds_wfs_push __cds_wfs_pop __cds_wfs_pop_all | |
38 | * cds_wfs_push - - - | |
39 | * __cds_wfs_pop - X X | |
40 | * __cds_wfs_pop_all - X - | |
41 | * | |
42 | * cds_wfs_pop and cds_wfs_pop_all use an internal mutex to provide | |
43 | * synchronization. | |
44 | */ | |
45 | ||
28757437 | 46 | #define CDS_WFS_WOULDBLOCK ((struct cds_wfs_node *) -1UL) |
af67624d | 47 | |
c8975b94 MD |
48 | enum cds_wfs_state { |
49 | CDS_WFS_STATE_LAST = (1U << 0), | |
50 | }; | |
51 | ||
edac6b69 MD |
52 | /* |
53 | * struct cds_wfs_node is returned by __cds_wfs_pop, and also used as | |
54 | * iterator on stack. It is not safe to dereference the node next | |
55 | * pointer when returned by __cds_wfs_pop_blocking. | |
56 | */ | |
16aa9ee8 DG |
57 | struct cds_wfs_node { |
58 | struct cds_wfs_node *next; | |
cb3f3d6b MD |
59 | }; |
60 | ||
edac6b69 MD |
61 | /* |
62 | * struct cds_wfs_head is returned by __cds_wfs_pop_all, and can be used | |
63 | * to begin iteration on the stack. "node" needs to be the first field of | |
64 | * cds_wfs_head, so the end-of-stack pointer value can be used for both | |
65 | * types. | |
66 | */ | |
67 | struct cds_wfs_head { | |
68 | struct cds_wfs_node node; | |
69 | }; | |
70 | ||
718eb63e EW |
71 | struct __cds_wfs_stack { |
72 | struct cds_wfs_head *head; | |
73 | }; | |
74 | ||
16aa9ee8 | 75 | struct cds_wfs_stack { |
edac6b69 | 76 | struct cds_wfs_head *head; |
cb3f3d6b MD |
77 | pthread_mutex_t lock; |
78 | }; | |
79 | ||
718eb63e | 80 | /* |
3ad920b4 | 81 | * In C, the transparent union allows calling functions that work on both |
718eb63e EW |
82 | * struct cds_wfs_stack and struct __cds_wfs_stack on any of those two |
83 | * types. | |
28757437 | 84 | * |
3ad920b4 MD |
85 | * In C++, implement static inline wrappers using function overloading |
86 | * to obtain an API similar to C. | |
087bce43 MD |
87 | * |
88 | * Avoid complaints from clang++ not knowing the transparent union | |
89 | * attribute. | |
718eb63e | 90 | */ |
087bce43 MD |
91 | #if defined(__clang__) |
92 | #pragma clang diagnostic push | |
93 | #pragma clang diagnostic ignored "-Wignored-attributes" | |
94 | #endif | |
5135c0fd | 95 | typedef union { |
718eb63e EW |
96 | struct __cds_wfs_stack *_s; |
97 | struct cds_wfs_stack *s; | |
087bce43 MD |
98 | } __attribute__((__transparent_union__)) cds_wfs_stack_ptr_t; |
99 | #if defined(__clang__) | |
100 | #pragma clang diagnostic pop | |
101 | #endif | |
718eb63e | 102 | |
294d3396 | 103 | #ifdef _LGPL_SOURCE |
cb3f3d6b | 104 | |
af7c2dbe | 105 | #include <urcu/static/wfstack.h> |
cb3f3d6b | 106 | |
16aa9ee8 | 107 | #define cds_wfs_node_init _cds_wfs_node_init |
edac6b69 | 108 | #define cds_wfs_init _cds_wfs_init |
200d100e | 109 | #define cds_wfs_destroy _cds_wfs_destroy |
711ff0f9 | 110 | #define __cds_wfs_init ___cds_wfs_init |
edac6b69 MD |
111 | #define cds_wfs_empty _cds_wfs_empty |
112 | #define cds_wfs_push _cds_wfs_push | |
113 | ||
114 | /* Locking performed internally */ | |
115 | #define cds_wfs_pop_blocking _cds_wfs_pop_blocking | |
c8975b94 | 116 | #define cds_wfs_pop_with_state_blocking _cds_wfs_pop_with_state_blocking |
edac6b69 MD |
117 | #define cds_wfs_pop_all_blocking _cds_wfs_pop_all_blocking |
118 | ||
119 | /* | |
120 | * For iteration on cds_wfs_head returned by __cds_wfs_pop_all or | |
121 | * cds_wfs_pop_all_blocking. | |
122 | */ | |
c7ba06ba | 123 | #define cds_wfs_first _cds_wfs_first |
edac6b69 | 124 | #define cds_wfs_next_blocking _cds_wfs_next_blocking |
150fc1bb | 125 | #define cds_wfs_next_nonblocking _cds_wfs_next_nonblocking |
edac6b69 MD |
126 | |
127 | /* Pop locking with internal mutex */ | |
128 | #define cds_wfs_pop_lock _cds_wfs_pop_lock | |
129 | #define cds_wfs_pop_unlock _cds_wfs_pop_unlock | |
130 | ||
131 | /* Synchronization ensured by the caller. See synchronization table. */ | |
132 | #define __cds_wfs_pop_blocking ___cds_wfs_pop_blocking | |
c8975b94 MD |
133 | #define __cds_wfs_pop_with_state_blocking \ |
134 | ___cds_wfs_pop_with_state_blocking | |
150fc1bb | 135 | #define __cds_wfs_pop_nonblocking ___cds_wfs_pop_nonblocking |
c8975b94 MD |
136 | #define __cds_wfs_pop_with_state_nonblocking \ |
137 | ___cds_wfs_pop_with_state_nonblocking | |
edac6b69 | 138 | #define __cds_wfs_pop_all ___cds_wfs_pop_all |
cb3f3d6b | 139 | |
294d3396 | 140 | #else /* !_LGPL_SOURCE */ |
cb3f3d6b | 141 | |
edac6b69 MD |
142 | /* |
143 | * cds_wfs_node_init: initialize wait-free stack node. | |
144 | */ | |
16aa9ee8 | 145 | extern void cds_wfs_node_init(struct cds_wfs_node *node); |
edac6b69 MD |
146 | |
147 | /* | |
200d100e MD |
148 | * cds_wfs_init: initialize wait-free stack (with lock). Pair with |
149 | * cds_wfs_destroy(). | |
edac6b69 | 150 | */ |
16aa9ee8 | 151 | extern void cds_wfs_init(struct cds_wfs_stack *s); |
edac6b69 | 152 | |
718eb63e | 153 | /* |
200d100e MD |
154 | * cds_wfs_destroy: destroy wait-free stack (with lock). Pair with |
155 | * cds_wfs_init(). | |
156 | */ | |
157 | extern void cds_wfs_destroy(struct cds_wfs_stack *s); | |
158 | ||
159 | /* | |
160 | * __cds_wfs_init: initialize wait-free stack (no lock). Don't pair with | |
161 | * any destroy function. | |
718eb63e EW |
162 | */ |
163 | extern void __cds_wfs_init(struct __cds_wfs_stack *s); | |
164 | ||
edac6b69 MD |
165 | /* |
166 | * cds_wfs_empty: return whether wait-free stack is empty. | |
167 | * | |
168 | * No memory barrier is issued. No mutual exclusion is required. | |
169 | */ | |
718eb63e | 170 | extern bool cds_wfs_empty(cds_wfs_stack_ptr_t u_stack); |
edac6b69 MD |
171 | |
172 | /* | |
173 | * cds_wfs_push: push a node into the stack. | |
174 | * | |
175 | * Issues a full memory barrier before push. No mutual exclusion is | |
176 | * required. | |
177 | * | |
178 | * Returns 0 if the stack was empty prior to adding the node. | |
179 | * Returns non-zero otherwise. | |
180 | */ | |
718eb63e | 181 | extern int cds_wfs_push(cds_wfs_stack_ptr_t u_stack, struct cds_wfs_node *node); |
edac6b69 MD |
182 | |
183 | /* | |
184 | * cds_wfs_pop_blocking: pop a node from the stack. | |
185 | * | |
186 | * Calls __cds_wfs_pop_blocking with an internal pop mutex held. | |
187 | */ | |
16aa9ee8 | 188 | extern struct cds_wfs_node *cds_wfs_pop_blocking(struct cds_wfs_stack *s); |
cb3f3d6b | 189 | |
c8975b94 MD |
190 | /* |
191 | * cds_wfs_pop_with_state_blocking: pop a node from the stack, with state. | |
192 | * | |
193 | * Same as cds_wfs_pop_blocking, but stores whether the stack was | |
194 | * empty into state (CDS_WFS_STATE_LAST). | |
195 | */ | |
196 | extern struct cds_wfs_node * | |
197 | cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state); | |
198 | ||
edac6b69 MD |
199 | /* |
200 | * cds_wfs_pop_all_blocking: pop all nodes from a stack. | |
201 | * | |
202 | * Calls __cds_wfs_pop_all with an internal pop mutex held. | |
203 | */ | |
204 | extern struct cds_wfs_head *cds_wfs_pop_all_blocking(struct cds_wfs_stack *s); | |
205 | ||
206 | /* | |
c7ba06ba | 207 | * cds_wfs_first: get first node of a popped stack. |
edac6b69 MD |
208 | * |
209 | * Content written into the node before enqueue is guaranteed to be | |
210 | * consistent, but no other memory ordering is ensured. | |
211 | * | |
212 | * Used by for-like iteration macros in urcu/wfstack.h: | |
213 | * cds_wfs_for_each_blocking() | |
214 | * cds_wfs_for_each_blocking_safe() | |
8af2956c MD |
215 | * |
216 | * Returns NULL if popped stack is empty, top stack node otherwise. | |
edac6b69 | 217 | */ |
c7ba06ba | 218 | extern struct cds_wfs_node *cds_wfs_first(struct cds_wfs_head *head); |
edac6b69 MD |
219 | |
220 | /* | |
221 | * cds_wfs_next_blocking: get next node of a popped stack. | |
222 | * | |
223 | * Content written into the node before enqueue is guaranteed to be | |
224 | * consistent, but no other memory ordering is ensured. | |
225 | * | |
226 | * Used by for-like iteration macros in urcu/wfstack.h: | |
227 | * cds_wfs_for_each_blocking() | |
228 | * cds_wfs_for_each_blocking_safe() | |
8af2956c MD |
229 | * |
230 | * Returns NULL if reached end of popped stack, non-NULL next stack | |
231 | * node otherwise. | |
edac6b69 MD |
232 | */ |
233 | extern struct cds_wfs_node *cds_wfs_next_blocking(struct cds_wfs_node *node); | |
234 | ||
af67624d MD |
235 | /* |
236 | * cds_wfs_next_nonblocking: get next node of a popped stack. | |
237 | * | |
238 | * Same as cds_wfs_next_blocking, but returns CDS_WFS_WOULDBLOCK if it | |
239 | * needs to block. | |
240 | */ | |
241 | extern struct cds_wfs_node *cds_wfs_next_nonblocking(struct cds_wfs_node *node); | |
242 | ||
edac6b69 MD |
243 | /* |
244 | * cds_wfs_pop_lock: lock stack pop-protection mutex. | |
245 | */ | |
246 | extern void cds_wfs_pop_lock(struct cds_wfs_stack *s); | |
247 | ||
248 | /* | |
249 | * cds_wfs_pop_unlock: unlock stack pop-protection mutex. | |
250 | */ | |
251 | extern void cds_wfs_pop_unlock(struct cds_wfs_stack *s); | |
252 | ||
253 | /* | |
254 | * __cds_wfs_pop_blocking: pop a node from the stack. | |
255 | * | |
256 | * Returns NULL if stack is empty. | |
257 | * | |
258 | * __cds_wfs_pop_blocking needs to be synchronized using one of the | |
259 | * following techniques: | |
260 | * | |
261 | * 1) Calling __cds_wfs_pop_blocking under rcu read lock critical | |
262 | * section. The caller must wait for a grace period to pass before | |
263 | * freeing the returned node or modifying the cds_wfs_node structure. | |
264 | * 2) Using mutual exclusion (e.g. mutexes) to protect | |
265 | * __cds_wfs_pop_blocking and __cds_wfs_pop_all callers. | |
266 | * 3) Ensuring that only ONE thread can call __cds_wfs_pop_blocking() | |
267 | * and __cds_wfs_pop_all(). (multi-provider/single-consumer scheme). | |
268 | */ | |
711ff0f9 | 269 | extern struct cds_wfs_node *__cds_wfs_pop_blocking(cds_wfs_stack_ptr_t u_stack); |
edac6b69 | 270 | |
c8975b94 MD |
271 | /* |
272 | * __cds_wfs_pop_with_state_blocking: pop a node from the stack, with state. | |
273 | * | |
274 | * Same as __cds_wfs_pop_blocking, but stores whether the stack was | |
275 | * empty into state (CDS_WFS_STATE_LAST). | |
276 | */ | |
277 | extern struct cds_wfs_node * | |
711ff0f9 MD |
278 | __cds_wfs_pop_with_state_blocking(cds_wfs_stack_ptr_t u_stack, |
279 | int *state); | |
c8975b94 | 280 | |
af67624d MD |
281 | /* |
282 | * __cds_wfs_pop_nonblocking: pop a node from the stack. | |
283 | * | |
284 | * Same as __cds_wfs_pop_blocking, but returns CDS_WFS_WOULDBLOCK if | |
285 | * it needs to block. | |
286 | */ | |
711ff0f9 | 287 | extern struct cds_wfs_node *__cds_wfs_pop_nonblocking(cds_wfs_stack_ptr_t u_stack); |
af67624d | 288 | |
c8975b94 MD |
289 | /* |
290 | * __cds_wfs_pop_with_state_nonblocking: pop a node from the stack, with state. | |
291 | * | |
292 | * Same as __cds_wfs_pop_nonblocking, but stores whether the stack was | |
293 | * empty into state (CDS_WFS_STATE_LAST). | |
294 | */ | |
295 | extern struct cds_wfs_node * | |
711ff0f9 | 296 | __cds_wfs_pop_with_state_nonblocking(cds_wfs_stack_ptr_t u_stack, |
c8975b94 MD |
297 | int *state); |
298 | ||
edac6b69 MD |
299 | /* |
300 | * __cds_wfs_pop_all: pop all nodes from a stack. | |
301 | * | |
302 | * __cds_wfs_pop_all does not require any synchronization with other | |
303 | * push, nor with other __cds_wfs_pop_all, but requires synchronization | |
304 | * matching the technique used to synchronize __cds_wfs_pop_blocking: | |
305 | * | |
306 | * 1) If __cds_wfs_pop_blocking is called under rcu read lock critical | |
307 | * section, both __cds_wfs_pop_blocking and cds_wfs_pop_all callers | |
308 | * must wait for a grace period to pass before freeing the returned | |
309 | * node or modifying the cds_wfs_node structure. However, no RCU | |
310 | * read-side critical section is needed around __cds_wfs_pop_all. | |
311 | * 2) Using mutual exclusion (e.g. mutexes) to protect | |
312 | * __cds_wfs_pop_blocking and __cds_wfs_pop_all callers. | |
313 | * 3) Ensuring that only ONE thread can call __cds_wfs_pop_blocking() | |
314 | * and __cds_wfs_pop_all(). (multi-provider/single-consumer scheme). | |
315 | */ | |
711ff0f9 | 316 | extern struct cds_wfs_head *__cds_wfs_pop_all(cds_wfs_stack_ptr_t u_stack); |
edac6b69 | 317 | |
294d3396 | 318 | #endif /* !_LGPL_SOURCE */ |
cb3f3d6b | 319 | |
edac6b69 MD |
320 | /* |
321 | * cds_wfs_for_each_blocking: Iterate over all nodes returned by | |
322 | * __cds_wfs_pop_all(). | |
323 | * @head: head of the queue (struct cds_wfs_head pointer). | |
324 | * @node: iterator (struct cds_wfs_node pointer). | |
325 | * | |
326 | * Content written into each node before enqueue is guaranteed to be | |
327 | * consistent, but no other memory ordering is ensured. | |
328 | */ | |
329 | #define cds_wfs_for_each_blocking(head, node) \ | |
c7ba06ba | 330 | for (node = cds_wfs_first(head); \ |
edac6b69 MD |
331 | node != NULL; \ |
332 | node = cds_wfs_next_blocking(node)) | |
333 | ||
334 | /* | |
335 | * cds_wfs_for_each_blocking_safe: Iterate over all nodes returned by | |
336 | * __cds_wfs_pop_all(). Safe against deletion. | |
337 | * @head: head of the queue (struct cds_wfs_head pointer). | |
338 | * @node: iterator (struct cds_wfs_node pointer). | |
339 | * @n: struct cds_wfs_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. | |
344 | */ | |
345 | #define cds_wfs_for_each_blocking_safe(head, node, n) \ | |
c7ba06ba | 346 | for (node = cds_wfs_first(head), \ |
edac6b69 MD |
347 | n = (node ? cds_wfs_next_blocking(node) : NULL); \ |
348 | node != NULL; \ | |
349 | node = n, n = (node ? cds_wfs_next_blocking(node) : NULL)) | |
350 | ||
3ad920b4 MD |
351 | #ifdef __cplusplus |
352 | } | |
353 | ||
354 | /* | |
355 | * In C++, implement static inline wrappers using function overloading | |
356 | * to obtain an API similar to C. | |
357 | */ | |
358 | ||
94d0ecca | 359 | static inline cds_wfs_stack_ptr_t cds_wfs_stack_cast(struct __cds_wfs_stack *s) |
3ad920b4 MD |
360 | { |
361 | cds_wfs_stack_ptr_t ret = { | |
362 | ._s = s, | |
363 | }; | |
364 | return ret; | |
365 | } | |
366 | ||
367 | static inline cds_wfs_stack_ptr_t cds_wfs_stack_cast(struct cds_wfs_stack *s) | |
368 | { | |
369 | cds_wfs_stack_ptr_t ret = { | |
370 | .s = s, | |
371 | }; | |
372 | return ret; | |
373 | } | |
374 | ||
c38fa027 | 375 | template<typename T> static inline bool cds_wfs_empty(T s) |
3ad920b4 | 376 | { |
94d0ecca | 377 | return cds_wfs_empty(cds_wfs_stack_cast(s)); |
3ad920b4 MD |
378 | } |
379 | ||
c38fa027 | 380 | template<typename T> static inline int cds_wfs_push(T s, struct cds_wfs_node *node) |
3ad920b4 MD |
381 | { |
382 | return cds_wfs_push(cds_wfs_stack_cast(s), node); | |
383 | } | |
384 | ||
c38fa027 | 385 | template<typename T> static inline struct cds_wfs_node *__cds_wfs_pop_blocking(T s) |
3ad920b4 | 386 | { |
94d0ecca | 387 | return __cds_wfs_pop_blocking(cds_wfs_stack_cast(s)); |
3ad920b4 MD |
388 | } |
389 | ||
c38fa027 MD |
390 | template<typename T> static inline struct cds_wfs_node * |
391 | __cds_wfs_pop_with_state_blocking(T s, int *state) | |
3ad920b4 MD |
392 | { |
393 | return __cds_wfs_pop_with_state_blocking(cds_wfs_stack_cast(s), state); | |
394 | } | |
395 | ||
c38fa027 | 396 | template<typename T> static inline struct cds_wfs_node *__cds_wfs_pop_nonblocking(T s) |
3ad920b4 MD |
397 | |
398 | { | |
94d0ecca | 399 | return __cds_wfs_pop_nonblocking(cds_wfs_stack_cast(s)); |
3ad920b4 MD |
400 | } |
401 | ||
c38fa027 MD |
402 | template<typename T> static inline struct cds_wfs_node * |
403 | __cds_wfs_pop_with_state_nonblocking(T s, int *state) | |
3ad920b4 MD |
404 | { |
405 | return __cds_wfs_pop_with_state_nonblocking(cds_wfs_stack_cast(s), state); | |
406 | } | |
407 | ||
c38fa027 | 408 | template<typename T> static inline struct cds_wfs_head *__cds_wfs_pop_all(T s) |
3ad920b4 MD |
409 | { |
410 | return __cds_wfs_pop_all(cds_wfs_stack_cast(s)); | |
411 | } | |
412 | ||
413 | #endif | |
414 | ||
cb3f3d6b | 415 | #endif /* _URCU_WFSTACK_H */ |