X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu%2Frcuwfstack.h;h=71ecce8cce1c492f9ec48ccd90fb4c07ee1e5287;hp=f2906cead9058af10f133e349734866bc1202111;hb=4afee0a75aa60a2640afc9ebccc417c3179b276e;hpb=a5eb5ffcbd3f901c8e56ab3649fd06056b27536f

diff --git a/urcu/rcuwfstack.h b/urcu/rcuwfstack.h
index f2906ce..71ecce8 100644
--- a/urcu/rcuwfstack.h
+++ b/urcu/rcuwfstack.h
@@ -1,3 +1,6 @@
+#ifndef _URCU_RCUWFSTACK_H
+#define _URCU_RCUWFSTACK_H
+
 /*
  * rcuwfstack.h
  *
@@ -20,17 +23,28 @@
  * 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)
@@ -40,14 +54,14 @@ 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.
@@ -61,35 +75,47 @@ void rcu_wfs_push(struct rcu_wfs_stack *s, struct rcu_wfs_node *node)
 }
 
 /*
- * 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 {
@@ -99,3 +125,9 @@ rcu_wfs_pop(struct rcu_wfs_stack *s)
 		}
 	}
 }
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _URCU_RCUWFSTACK_H */