From 0e2e9380d93d73c246abdeef52c7a97b01deecca Mon Sep 17 00:00:00 2001
From: Mathieu Desnoyers <mathieu.desnoyers@polymtl.ca>
Date: Tue, 13 Jul 2010 18:21:33 -0400
Subject: [PATCH] ifdef C, wait-free stack adaptative pop wait

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
---
 urcu/rculfqueue.h |  8 ++++++++
 urcu/rculfstack.h |  8 ++++++++
 urcu/rcuwfqueue.h | 19 +++++++++++++++++--
 urcu/rcuwfstack.h | 22 +++++++++++++++++++---
 4 files changed, 52 insertions(+), 5 deletions(-)

diff --git a/urcu/rculfqueue.h b/urcu/rculfqueue.h
index b712998..01c2092 100644
--- a/urcu/rculfqueue.h
+++ b/urcu/rculfqueue.h
@@ -26,6 +26,10 @@
 #include <urcu/urcu_ref.h>
 #include <assert.h>
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 #if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
 #error "Dynamic loader LGPL wrappers not implemented yet"
 #endif
@@ -142,4 +146,8 @@ rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *))
 	}
 }
 
+#ifdef __cplusplus
+}
+#endif
+
 #endif /* _URCU_RCULFQUEUE_H */
diff --git a/urcu/rculfstack.h b/urcu/rculfstack.h
index a9e624c..f80c7fe 100644
--- a/urcu/rculfstack.h
+++ b/urcu/rculfstack.h
@@ -23,6 +23,10 @@
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  */
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 #if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
 #error "Dynamic loader LGPL wrappers not implemented yet"
 #endif
@@ -99,4 +103,8 @@ rcu_lfs_pop(struct rcu_lfs_stack *s)
 	}
 }
 
+#ifdef __cplusplus
+}
+#endif
+
 #endif /* _URCU_RCULFSTACK_H */
diff --git a/urcu/rcuwfqueue.h b/urcu/rcuwfqueue.h
index 857233b..8c1d4a1 100644
--- a/urcu/rcuwfqueue.h
+++ b/urcu/rcuwfqueue.h
@@ -1,3 +1,6 @@
+#ifndef _URCU_RCUWFQUEUE_H
+#define _URCU_RCUWFQUEUE_H
+
 /*
  * rcuwfqueue.h
  *
@@ -23,6 +26,10 @@
 #include <urcu/urcu_ref.h>
 #include <assert.h>
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 #if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
 #error "Dynamic loader LGPL wrappers not implemented yet"
 #endif
@@ -92,8 +99,10 @@ void rcu_wfq_enqueue(struct rcu_wfq_queue *q, struct rcu_wfq_node *node)
  * modified/re-used/freed until the reference count reaches zero and a grace
  * period has elapsed (after the refcount reached 0).
  *
- * TODO: implement adaptative busy-wait and wait/wakeup scheme rather than busy
- * loops. Better for UP.
+ * No need to go on a waitqueue here, as there is no possible state in which the
+ * list could cause dequeue to busy-loop needlessly while waiting for another
+ * thread to be scheduled. The queue appears empty until tail->next is set by
+ * enqueue.
  */
 struct rcu_wfq_node *
 rcu_wfq_dequeue_blocking(struct rcu_wfq_queue *q,
@@ -122,3 +131,9 @@ rcu_wfq_dequeue_blocking(struct rcu_wfq_queue *q,
 		}
 	}
 }
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* _URCU_RCUWFQUEUE_H */
diff --git a/urcu/rcuwfstack.h b/urcu/rcuwfstack.h
index 300c95e..71ecce8 100644
--- a/urcu/rcuwfstack.h
+++ b/urcu/rcuwfstack.h
@@ -25,11 +25,19 @@
 
 #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;
@@ -78,13 +86,12 @@ void rcu_wfs_push(struct rcu_wfs_stack *s, struct rcu_wfs_node *node)
  * 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_blocking(struct rcu_wfs_stack *s)
 {
+	int attempt = 0;
+
 	for (;;) {
 		struct rcu_wfs_node *head;
 
@@ -96,6 +103,11 @@ rcu_wfs_pop_blocking(struct rcu_wfs_stack *s)
 			/* Retry while head is being set by push(). */
 			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) {
@@ -114,4 +126,8 @@ rcu_wfs_pop_blocking(struct rcu_wfs_stack *s)
 	}
 }
 
+#ifdef __cplusplus
+}
+#endif
+
 #endif /* _URCU_RCUWFSTACK_H */
-- 
2.34.1