Add CMM memory model
[urcu.git] / include / urcu / wfstack.h
CommitLineData
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
17extern "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
48enum 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
57struct 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 */
67struct cds_wfs_head {
68 struct cds_wfs_node node;
69};
70
718eb63e
EW
71struct __cds_wfs_stack {
72 struct cds_wfs_head *head;
73};
74
16aa9ee8 75struct 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 95typedef 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 145extern 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 151extern 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 */
157extern 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 */
163extern 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 170extern 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 181extern 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 188extern 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 */
196extern 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 */
204extern 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 218extern 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 */
233extern 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 */
241extern 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 */
246extern void cds_wfs_pop_lock(struct cds_wfs_stack *s);
247
248/*
249 * cds_wfs_pop_unlock: unlock stack pop-protection mutex.
250 */
251extern 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 269extern 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 */
277extern 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 287extern 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 */
295extern 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 316extern 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 359static 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
367static 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 375template<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 380template<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 385template<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
390template<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 396template<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
402template<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 408template<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 */
This page took 0.0641699999999999 seconds and 4 git commands to generate.