+#ifndef _URCU_RCUWFSTACK_H
+#define _URCU_RCUWFSTACK_H
+
/*
* rcuwfstack.h
*
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
+#include <assert.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
#error "Dynamic loader LGPL wrappers not implemented yet"
#endif
+#define RCU_WF_STACK_END ((void *)0x1UL)
+#define RCU_WFS_ADAPT_ATTEMPTS 10 /* Retry if being set */
+#define RCU_WFS_WAIT 10 /* Wait 10 ms if being set */
+
+extern int rcu_wfs_futex;
+
struct rcu_wfs_node {
struct rcu_wfs_node *next;
};
struct rcu_wfs_stack {
struct rcu_wfs_node *head;
- struct rcu_wfs_node end;
};
void rcu_wfs_node_init(struct rcu_wfs_node *node)
void rcu_wfs_init(struct rcu_wfs_stack *s)
{
- s->head = &s->end;
- rcu_wfs_node_init(&s->end);
+ s->head = RCU_WF_STACK_END;
}
void rcu_wfs_push(struct rcu_wfs_stack *s, struct rcu_wfs_node *node)
{
struct rcu_wfs_node *old_head;
+ assert(node->next == NULL);
/*
* uatomic_xchg() implicit memory barrier orders earlier stores to node
* (setting it to NULL) before publication.
}
/*
- * The caller must wait for a grace period before freeing the returned node.
+ * The caller must wait for a grace period before:
+ * - freeing the returned node.
+ * - modifying the ->next pointer of the returned node. (be careful with unions)
+ * - passing the returned node back to push() on the same stack they got it
+ * from.
+ *
* Returns NULL if stack is empty.
*
* cmpxchg is protected from ABA races by holding a RCU read lock between
* s->head read and cmpxchg modifying s->head and requiring that dequeuers wait
* for a grace period before freeing the returned node.
- *
- * TODO: implement adaptative busy-wait and wait/wakeup scheme rather than busy
- * loops. Better for UP.
*/
struct rcu_wfs_node *
-rcu_wfs_pop(struct rcu_wfs_stack *s)
+rcu_wfs_pop_blocking(struct rcu_wfs_stack *s)
{
- rcu_read_lock();
+ int attempt = 0;
+
for (;;) {
- struct rcu_wfs_node *head = rcu_dereference(s->head);
+ struct rcu_wfs_node *head;
- if (head != &s->end) {
+ rcu_read_lock();
+ head = rcu_dereference(s->head);
+ if (head != RCU_WF_STACK_END) {
struct rcu_wfs_node *next = rcu_dereference(head->next);
/* Retry while head is being set by push(). */
- if (!next)
+ if (!next) {
+ rcu_read_unlock();
+ if (++attempt >= RCU_WFS_ADAPT_ATTEMPTS) {
+ /* Sleep for 10ms */
+ poll(NULL, 0, RCU_WFS_WAIT);
+ attempt = 0;
+ }
continue;
-
+ }
if (uatomic_cmpxchg(&s->head, head, next) == head) {
rcu_read_unlock();
return head;
} else {
/* Concurrent modification. Retry. */
+ rcu_read_unlock();
continue;
}
} else {
}
}
}
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _URCU_RCUWFSTACK_H */