*
* Userspace RCU library - Stack with with wait-free push, blocking traversal.
*
- * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See wfstack.h for linking
- * dynamically with the userspace rcu library.
+ * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See urcu/wfstack.h for
+ * linking dynamically with the userspace rcu library.
*
- * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
+ * Copyright 2010-2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* Stack implementing push, pop, pop_all operations, as well as iterator
* on the stack head returned by pop_all.
*
- * Wait-free operations: cds_wfs_push, __cds_wfs_pop_all.
- * Blocking operations: cds_wfs_pop, cds_wfs_pop_all, iteration on stack
- * head returned by pop_all.
+ * Wait-free operations: cds_wfs_push, __cds_wfs_pop_all, cds_wfs_empty,
+ * cds_wfs_first.
+ * Blocking operations: cds_wfs_pop, cds_wfs_pop_all, cds_wfs_next,
+ * iteration on stack head returned by pop_all.
*
* Synchronization table:
*
* Waiting for push to complete enqueue and return the next node.
*/
static inline struct cds_wfs_node *
-___cds_wfs_node_sync_next(struct cds_wfs_node *node)
+___cds_wfs_node_sync_next(struct cds_wfs_node *node, int blocking)
{
struct cds_wfs_node *next;
int attempt = 0;
* Adaptative busy-looping waiting for push to complete.
*/
while ((next = CMM_LOAD_SHARED(node->next)) == NULL) {
+ if (!blocking)
+ return CDS_WFS_WOULDBLOCK;
if (++attempt >= CDS_WFS_ADAPT_ATTEMPTS) {
poll(NULL, 0, CDS_WFS_WAIT); /* Wait for 10ms */
attempt = 0;
return next;
}
+static inline
+struct cds_wfs_node *
+___cds_wfs_pop(struct cds_wfs_stack *s, int *state, int blocking)
+{
+ struct cds_wfs_head *head, *new_head;
+ struct cds_wfs_node *next;
+
+ if (state)
+ *state = 0;
+ for (;;) {
+ head = CMM_LOAD_SHARED(s->head);
+ if (___cds_wfs_end(head)) {
+ return NULL;
+ }
+ next = ___cds_wfs_node_sync_next(&head->node, blocking);
+ if (!blocking && next == CDS_WFS_WOULDBLOCK) {
+ return CDS_WFS_WOULDBLOCK;
+ }
+ new_head = caa_container_of(next, struct cds_wfs_head, node);
+ if (uatomic_cmpxchg(&s->head, head, new_head) == head) {
+ if (state && ___cds_wfs_end(new_head))
+ *state |= CDS_WFS_STATE_LAST;
+ return &head->node;
+ }
+ if (!blocking) {
+ return CDS_WFS_WOULDBLOCK;
+ }
+ /* busy-loop if head changed under us */
+ }
+}
+
/*
- * __cds_wfs_pop_blocking: pop a node from the stack.
+ * __cds_wfs_pop_with_state_blocking: pop a node from the stack, with state.
*
* Returns NULL if stack is empty.
*
* __cds_wfs_pop_blocking and __cds_wfs_pop_all callers.
* 3) Ensuring that only ONE thread can call __cds_wfs_pop_blocking()
* and __cds_wfs_pop_all(). (multi-provider/single-consumer scheme).
+ *
+ * "state" saves state flags atomically sampled with pop operation.
*/
+static inline
+struct cds_wfs_node *
+___cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state)
+{
+ return ___cds_wfs_pop(s, state, 1);
+}
+
static inline
struct cds_wfs_node *
___cds_wfs_pop_blocking(struct cds_wfs_stack *s)
{
- struct cds_wfs_head *head, *new_head;
- struct cds_wfs_node *next;
+ return ___cds_wfs_pop_with_state_blocking(s, NULL);
+}
- for (;;) {
- head = CMM_LOAD_SHARED(s->head);
- if (___cds_wfs_end(head))
- return NULL;
- next = ___cds_wfs_node_sync_next(&head->node);
- new_head = caa_container_of(next, struct cds_wfs_head, node);
- if (uatomic_cmpxchg(&s->head, head, new_head) == head)
- return &head->node;
- /* busy-loop if head changed under us */
- }
+/*
+ * __cds_wfs_pop_with_state_nonblocking: pop a node from the stack.
+ *
+ * Same as __cds_wfs_pop_with_state_blocking, but returns
+ * CDS_WFS_WOULDBLOCK if it needs to block.
+ *
+ * "state" saves state flags atomically sampled with pop operation.
+ */
+static inline
+struct cds_wfs_node *
+___cds_wfs_pop_with_state_nonblocking(struct cds_wfs_stack *s, int *state)
+{
+ return ___cds_wfs_pop(s, state, 0);
+}
+
+/*
+ * __cds_wfs_pop_nonblocking: pop a node from the stack.
+ *
+ * Same as __cds_wfs_pop_blocking, but returns CDS_WFS_WOULDBLOCK if
+ * it needs to block.
+ */
+static inline
+struct cds_wfs_node *
+___cds_wfs_pop_nonblocking(struct cds_wfs_stack *s)
+{
+ return ___cds_wfs_pop_with_state_nonblocking(s, NULL);
}
/*
}
/*
- * Call __cds_wfs_pop_blocking with an internal pop mutex held.
+ * Call __cds_wfs_pop_with_state_blocking with an internal pop mutex held.
*/
static inline
struct cds_wfs_node *
-_cds_wfs_pop_blocking(struct cds_wfs_stack *s)
+_cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state)
{
struct cds_wfs_node *retnode;
_cds_wfs_pop_lock(s);
- retnode = ___cds_wfs_pop_blocking(s);
+ retnode = ___cds_wfs_pop_with_state_blocking(s, state);
_cds_wfs_pop_unlock(s);
return retnode;
}
+/*
+ * Call _cds_wfs_pop_with_state_blocking without saving any state.
+ */
+static inline
+struct cds_wfs_node *
+_cds_wfs_pop_blocking(struct cds_wfs_stack *s)
+{
+ return _cds_wfs_pop_with_state_blocking(s, NULL);
+}
+
/*
* Call __cds_wfs_pop_all with an internal pop mutex held.
*/
}
/*
- * cds_wfs_first_blocking: get first node of a popped stack.
+ * cds_wfs_first: get first node of a popped stack.
*
* Content written into the node before enqueue is guaranteed to be
* consistent, but no other memory ordering is ensured.
* Used by for-like iteration macros in urcu/wfstack.h:
* cds_wfs_for_each_blocking()
* cds_wfs_for_each_blocking_safe()
+ *
+ * Returns NULL if popped stack is empty, top stack node otherwise.
*/
static inline struct cds_wfs_node *
-_cds_wfs_first_blocking(struct cds_wfs_head *head)
+_cds_wfs_first(struct cds_wfs_head *head)
{
if (___cds_wfs_end(head))
return NULL;
return &head->node;
}
+static inline struct cds_wfs_node *
+___cds_wfs_next(struct cds_wfs_node *node, int blocking)
+{
+ struct cds_wfs_node *next;
+
+ next = ___cds_wfs_node_sync_next(node, blocking);
+ /*
+ * CDS_WFS_WOULDBLOCK != CSD_WFS_END, so we can check for end
+ * even if ___cds_wfs_node_sync_next returns CDS_WFS_WOULDBLOCK,
+ * and still return CDS_WFS_WOULDBLOCK.
+ */
+ if (___cds_wfs_end(next))
+ return NULL;
+ return next;
+}
+
/*
* cds_wfs_next_blocking: get next node of a popped stack.
*
* Used by for-like iteration macros in urcu/wfstack.h:
* cds_wfs_for_each_blocking()
* cds_wfs_for_each_blocking_safe()
+ *
+ * Returns NULL if reached end of popped stack, non-NULL next stack
+ * node otherwise.
*/
static inline struct cds_wfs_node *
_cds_wfs_next_blocking(struct cds_wfs_node *node)
{
- struct cds_wfs_node *next;
+ return ___cds_wfs_next(node, 1);
+}
- next = ___cds_wfs_node_sync_next(node);
- if (___cds_wfs_end(next))
- return NULL;
- return next;
+
+/*
+ * cds_wfs_next_nonblocking: get next node of a popped stack.
+ *
+ * Same as cds_wfs_next_blocking, but returns CDS_WFS_WOULDBLOCK if it
+ * needs to block.
+ */
+static inline struct cds_wfs_node *
+_cds_wfs_next_nonblocking(struct cds_wfs_node *node)
+{
+ return ___cds_wfs_next(node, 0);
}
#ifdef __cplusplus