1 // SPDX-FileCopyrightText: 2010-2012 Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
3 // SPDX-License-Identifier: LGPL-2.1-or-later
5 #ifndef _URCU_WFSTACK_H
6 #define _URCU_WFSTACK_H
9 * Userspace RCU library - Stack with wait-free push, blocking traversal.
14 #include <urcu/compiler.h>
21 * Stack with wait-free push, blocking traversal.
23 * Stack implementing push, pop, pop_all operations, as well as iterator
24 * on the stack head returned by pop_all.
26 * Wait-free operations: cds_wfs_push, __cds_wfs_pop_all, cds_wfs_empty,
28 * Blocking operations: cds_wfs_pop, cds_wfs_pop_all, cds_wfs_next,
29 * iteration on stack head returned by pop_all.
31 * Synchronization table:
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 "-".
37 * cds_wfs_push __cds_wfs_pop __cds_wfs_pop_all
40 * __cds_wfs_pop_all - X -
42 * cds_wfs_pop and cds_wfs_pop_all use an internal mutex to provide
46 #define CDS_WFS_WOULDBLOCK ((struct cds_wfs_node *) -1UL)
49 CDS_WFS_STATE_LAST
= (1U << 0),
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.
58 struct cds_wfs_node
*next
;
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
68 struct cds_wfs_node node
;
71 struct __cds_wfs_stack
{
72 struct cds_wfs_head
*head
;
75 struct cds_wfs_stack
{
76 struct cds_wfs_head
*head
;
81 * In C, the transparent union allows calling functions that work on both
82 * struct cds_wfs_stack and struct __cds_wfs_stack on any of those two
85 * In C++, implement static inline wrappers using function overloading
86 * to obtain an API similar to C.
88 * Avoid complaints from clang++ not knowing the transparent union
91 #if defined(__clang__)
92 #pragma clang diagnostic push
93 #pragma clang diagnostic ignored "-Wignored-attributes"
96 struct __cds_wfs_stack
*_s
;
97 struct cds_wfs_stack
*s
;
98 } __attribute__((__transparent_union__
)) cds_wfs_stack_ptr_t
;
99 #if defined(__clang__)
100 #pragma clang diagnostic pop
105 #include <urcu/static/wfstack.h>
107 #define cds_wfs_node_init _cds_wfs_node_init
108 #define cds_wfs_init _cds_wfs_init
109 #define cds_wfs_destroy _cds_wfs_destroy
110 #define __cds_wfs_init ___cds_wfs_init
111 #define cds_wfs_empty _cds_wfs_empty
112 #define cds_wfs_push _cds_wfs_push
114 /* Locking performed internally */
115 #define cds_wfs_pop_blocking _cds_wfs_pop_blocking
116 #define cds_wfs_pop_with_state_blocking _cds_wfs_pop_with_state_blocking
117 #define cds_wfs_pop_all_blocking _cds_wfs_pop_all_blocking
120 * For iteration on cds_wfs_head returned by __cds_wfs_pop_all or
121 * cds_wfs_pop_all_blocking.
123 #define cds_wfs_first _cds_wfs_first
124 #define cds_wfs_next_blocking _cds_wfs_next_blocking
125 #define cds_wfs_next_nonblocking _cds_wfs_next_nonblocking
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
131 /* Synchronization ensured by the caller. See synchronization table. */
132 #define __cds_wfs_pop_blocking ___cds_wfs_pop_blocking
133 #define __cds_wfs_pop_with_state_blocking \
134 ___cds_wfs_pop_with_state_blocking
135 #define __cds_wfs_pop_nonblocking ___cds_wfs_pop_nonblocking
136 #define __cds_wfs_pop_with_state_nonblocking \
137 ___cds_wfs_pop_with_state_nonblocking
138 #define __cds_wfs_pop_all ___cds_wfs_pop_all
140 #else /* !_LGPL_SOURCE */
143 * cds_wfs_node_init: initialize wait-free stack node.
145 extern void cds_wfs_node_init(struct cds_wfs_node
*node
);
148 * cds_wfs_init: initialize wait-free stack (with lock). Pair with
151 extern void cds_wfs_init(struct cds_wfs_stack
*s
);
154 * cds_wfs_destroy: destroy wait-free stack (with lock). Pair with
157 extern void cds_wfs_destroy(struct cds_wfs_stack
*s
);
160 * __cds_wfs_init: initialize wait-free stack (no lock). Don't pair with
161 * any destroy function.
163 extern void __cds_wfs_init(struct __cds_wfs_stack
*s
);
166 * cds_wfs_empty: return whether wait-free stack is empty.
168 * No memory barrier is issued. No mutual exclusion is required.
170 extern bool cds_wfs_empty(cds_wfs_stack_ptr_t u_stack
);
173 * cds_wfs_push: push a node into the stack.
175 * Issues a full memory barrier before push. No mutual exclusion is
178 * Returns 0 if the stack was empty prior to adding the node.
179 * Returns non-zero otherwise.
181 extern int cds_wfs_push(cds_wfs_stack_ptr_t u_stack
, struct cds_wfs_node
*node
);
184 * cds_wfs_pop_blocking: pop a node from the stack.
186 * Calls __cds_wfs_pop_blocking with an internal pop mutex held.
188 extern struct cds_wfs_node
*cds_wfs_pop_blocking(struct cds_wfs_stack
*s
);
191 * cds_wfs_pop_with_state_blocking: pop a node from the stack, with state.
193 * Same as cds_wfs_pop_blocking, but stores whether the stack was
194 * empty into state (CDS_WFS_STATE_LAST).
196 extern struct cds_wfs_node
*
197 cds_wfs_pop_with_state_blocking(struct cds_wfs_stack
*s
, int *state
);
200 * cds_wfs_pop_all_blocking: pop all nodes from a stack.
202 * Calls __cds_wfs_pop_all with an internal pop mutex held.
204 extern struct cds_wfs_head
*cds_wfs_pop_all_blocking(struct cds_wfs_stack
*s
);
207 * cds_wfs_first: get first node of a popped stack.
209 * Content written into the node before enqueue is guaranteed to be
210 * consistent, but no other memory ordering is ensured.
212 * Used by for-like iteration macros in urcu/wfstack.h:
213 * cds_wfs_for_each_blocking()
214 * cds_wfs_for_each_blocking_safe()
216 * Returns NULL if popped stack is empty, top stack node otherwise.
218 extern struct cds_wfs_node
*cds_wfs_first(struct cds_wfs_head
*head
);
221 * cds_wfs_next_blocking: get next node of a popped stack.
223 * Content written into the node before enqueue is guaranteed to be
224 * consistent, but no other memory ordering is ensured.
226 * Used by for-like iteration macros in urcu/wfstack.h:
227 * cds_wfs_for_each_blocking()
228 * cds_wfs_for_each_blocking_safe()
230 * Returns NULL if reached end of popped stack, non-NULL next stack
233 extern struct cds_wfs_node
*cds_wfs_next_blocking(struct cds_wfs_node
*node
);
236 * cds_wfs_next_nonblocking: get next node of a popped stack.
238 * Same as cds_wfs_next_blocking, but returns CDS_WFS_WOULDBLOCK if it
241 extern struct cds_wfs_node
*cds_wfs_next_nonblocking(struct cds_wfs_node
*node
);
244 * cds_wfs_pop_lock: lock stack pop-protection mutex.
246 extern void cds_wfs_pop_lock(struct cds_wfs_stack
*s
);
249 * cds_wfs_pop_unlock: unlock stack pop-protection mutex.
251 extern void cds_wfs_pop_unlock(struct cds_wfs_stack
*s
);
254 * __cds_wfs_pop_blocking: pop a node from the stack.
256 * Returns NULL if stack is empty.
258 * __cds_wfs_pop_blocking needs to be synchronized using one of the
259 * following techniques:
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).
269 extern struct cds_wfs_node
*__cds_wfs_pop_blocking(cds_wfs_stack_ptr_t u_stack
);
272 * __cds_wfs_pop_with_state_blocking: pop a node from the stack, with state.
274 * Same as __cds_wfs_pop_blocking, but stores whether the stack was
275 * empty into state (CDS_WFS_STATE_LAST).
277 extern struct cds_wfs_node
*
278 __cds_wfs_pop_with_state_blocking(cds_wfs_stack_ptr_t u_stack
,
282 * __cds_wfs_pop_nonblocking: pop a node from the stack.
284 * Same as __cds_wfs_pop_blocking, but returns CDS_WFS_WOULDBLOCK if
287 extern struct cds_wfs_node
*__cds_wfs_pop_nonblocking(cds_wfs_stack_ptr_t u_stack
);
290 * __cds_wfs_pop_with_state_nonblocking: pop a node from the stack, with state.
292 * Same as __cds_wfs_pop_nonblocking, but stores whether the stack was
293 * empty into state (CDS_WFS_STATE_LAST).
295 extern struct cds_wfs_node
*
296 __cds_wfs_pop_with_state_nonblocking(cds_wfs_stack_ptr_t u_stack
,
300 * __cds_wfs_pop_all: pop all nodes from a stack.
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:
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).
316 extern struct cds_wfs_head
*__cds_wfs_pop_all(cds_wfs_stack_ptr_t u_stack
);
318 #endif /* !_LGPL_SOURCE */
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).
326 * Content written into each node before enqueue is guaranteed to be
327 * consistent, but no other memory ordering is ensured.
329 #define cds_wfs_for_each_blocking(head, node) \
330 for (node = cds_wfs_first(head); \
332 node = cds_wfs_next_blocking(node))
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
342 * Content written into each node before enqueue is guaranteed to be
343 * consistent, but no other memory ordering is ensured.
345 #define cds_wfs_for_each_blocking_safe(head, node, n) \
346 for (node = cds_wfs_first(head), \
347 n = (node ? cds_wfs_next_blocking(node) : NULL); \
349 node = n, n = (node ? cds_wfs_next_blocking(node) : NULL))
355 * In C++, implement static inline wrappers using function overloading
356 * to obtain an API similar to C.
359 static inline cds_wfs_stack_ptr_t
cds_wfs_stack_cast(struct __cds_wfs_stack
*s
)
361 cds_wfs_stack_ptr_t ret
= {
367 static inline cds_wfs_stack_ptr_t
cds_wfs_stack_cast(struct cds_wfs_stack
*s
)
369 cds_wfs_stack_ptr_t ret
= {
375 template<typename T
> static inline bool cds_wfs_empty(T s
)
377 return cds_wfs_empty(cds_wfs_stack_cast(s
));
380 template<typename T
> static inline int cds_wfs_push(T s
, struct cds_wfs_node
*node
)
382 return cds_wfs_push(cds_wfs_stack_cast(s
), node
);
385 template<typename T
> static inline struct cds_wfs_node
*__cds_wfs_pop_blocking(T s
)
387 return __cds_wfs_pop_blocking(cds_wfs_stack_cast(s
));
390 template<typename T
> static inline struct cds_wfs_node
*
391 __cds_wfs_pop_with_state_blocking(T s
, int *state
)
393 return __cds_wfs_pop_with_state_blocking(cds_wfs_stack_cast(s
), state
);
396 template<typename T
> static inline struct cds_wfs_node
*__cds_wfs_pop_nonblocking(T s
)
399 return __cds_wfs_pop_nonblocking(cds_wfs_stack_cast(s
));
402 template<typename T
> static inline struct cds_wfs_node
*
403 __cds_wfs_pop_with_state_nonblocking(T s
, int *state
)
405 return __cds_wfs_pop_with_state_nonblocking(cds_wfs_stack_cast(s
), state
);
408 template<typename T
> static inline struct cds_wfs_head
*__cds_wfs_pop_all(T s
)
410 return __cds_wfs_pop_all(cds_wfs_stack_cast(s
));
415 #endif /* _URCU_WFSTACK_H */