wfstack: implement mutex-free wfstack with transparent union

This allows users more freedom to use alternative synchronization
mechanisms.

Changes since v1:
- Fix typos in cds_wfs_stack_ptr_t documentation.
  Thanks to Mathieu for spotting.

Signed-off-by: Eric Wong <normalperson@yhbt.net>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Lai Jiangshan <laijs@cn.fujitsu.com>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

diff --git a/urcu/static/wfstack.h b/urcu/static/wfstack.h
index db0d5b8b1abda178f7cf0e14a0530d5bae43f8aa..eb12f377d1e1d974c43b2705bd6eab73d5634550 100644 (file)
--- a/urcu/static/wfstack.h
+++ b/urcu/static/wfstack.h
@@ -76,6 +76,14 @@ void _cds_wfs_node_init(struct cds_wfs_node *node)
        node->next = NULL;
 }
 
        node->next = NULL;
 }
 

+/*
+ * __cds_wfs_init: initialize wait-free stack.
+ */
+static inline void ___cds_wfs_init(struct __cds_wfs_stack *s)
+{
+       s->head = CDS_WFS_END;
+}
+

 /*
  * cds_wfs_init: initialize wait-free stack.
  */
 /*
  * cds_wfs_init: initialize wait-free stack.
  */


@@ -99,8 +107,10 @@ static inline bool ___cds_wfs_end(void *node)
  *
  * No memory barrier is issued. No mutual exclusion is required.
  */
  *
  * No memory barrier is issued. No mutual exclusion is required.
  */

-static inline bool _cds_wfs_empty(struct cds_wfs_stack *s)
+static inline bool _cds_wfs_empty(cds_wfs_stack_ptr_t u_stack)

 {
 {

+       struct __cds_wfs_stack *s = u_stack._s;
+

        return ___cds_wfs_end(CMM_LOAD_SHARED(s->head));
 }
 
        return ___cds_wfs_end(CMM_LOAD_SHARED(s->head));
 }
 


@@ -114,8 +124,9 @@ static inline bool _cds_wfs_empty(struct cds_wfs_stack *s)
  * Returns non-zero otherwise.
  */
 static inline
  * Returns non-zero otherwise.
  */
 static inline

-int _cds_wfs_push(struct cds_wfs_stack *s, struct cds_wfs_node *node)
+int _cds_wfs_push(cds_wfs_stack_ptr_t u_stack, struct cds_wfs_node *node)

 {
 {

+       struct __cds_wfs_stack *s = u_stack._s;

        struct cds_wfs_head *old_head, *new_head;
 
        assert(node->next == NULL);
        struct cds_wfs_head *old_head, *new_head;
 
        assert(node->next == NULL);


@@ -269,8 +280,9 @@ ___cds_wfs_pop_nonblocking(struct cds_wfs_stack *s)
  */
 static inline
 struct cds_wfs_head *
  */
 static inline
 struct cds_wfs_head *

-___cds_wfs_pop_all(struct cds_wfs_stack *s)
+___cds_wfs_pop_all(cds_wfs_stack_ptr_t u_stack)

 {
 {

+       struct __cds_wfs_stack *s = u_stack._s;

        struct cds_wfs_head *head;
 
        /*
        struct cds_wfs_head *head;
 
        /*

diff --git a/urcu/wfstack.h b/urcu/wfstack.h
index fc0b44b791fcf218c56714711e235cc40465296f..b914f41e6cfdd17e42648ef0867bf92b4526da1c 100644 (file)
--- a/urcu/wfstack.h
+++ b/urcu/wfstack.h
@@ -83,11 +83,25 @@ struct cds_wfs_head {
        struct cds_wfs_node node;
 };
 
        struct cds_wfs_node node;
 };
 

+struct __cds_wfs_stack {
+       struct cds_wfs_head *head;
+};
+

 struct cds_wfs_stack {
        struct cds_wfs_head *head;
        pthread_mutex_t lock;
 };
 
 struct cds_wfs_stack {
        struct cds_wfs_head *head;
        pthread_mutex_t lock;
 };
 

+/*
+ * The transparent union allows calling functions that work on both
+ * struct cds_wfs_stack and struct __cds_wfs_stack on any of those two
+ * types.
+ */
+typedef union __attribute__((__transparent_union__)) {
+       struct __cds_wfs_stack *_s;
+       struct cds_wfs_stack *s;
+} cds_wfs_stack_ptr_t;
+

 #ifdef _LGPL_SOURCE
 
 #include <urcu/static/wfstack.h>
 #ifdef _LGPL_SOURCE
 
 #include <urcu/static/wfstack.h>


@@ -135,12 +149,17 @@ extern void cds_wfs_node_init(struct cds_wfs_node *node);
  */
 extern void cds_wfs_init(struct cds_wfs_stack *s);
 
  */
 extern void cds_wfs_init(struct cds_wfs_stack *s);
 

+/*
+ * __cds_wfs_init: initialize wait-free stack.
+ */
+extern void __cds_wfs_init(struct __cds_wfs_stack *s);
+

 /*
  * cds_wfs_empty: return whether wait-free stack is empty.
  *
  * No memory barrier is issued. No mutual exclusion is required.
  */
 /*
  * cds_wfs_empty: return whether wait-free stack is empty.
  *
  * No memory barrier is issued. No mutual exclusion is required.
  */

-extern bool cds_wfs_empty(struct cds_wfs_stack *s);
+extern bool cds_wfs_empty(cds_wfs_stack_ptr_t u_stack);

 
 /*
  * cds_wfs_push: push a node into the stack.
 
 /*
  * cds_wfs_push: push a node into the stack.


@@ -151,7 +170,7 @@ extern bool cds_wfs_empty(struct cds_wfs_stack *s);
  * Returns 0 if the stack was empty prior to adding the node.
  * Returns non-zero otherwise.
  */
  * Returns 0 if the stack was empty prior to adding the node.
  * Returns non-zero otherwise.
  */

-extern int cds_wfs_push(struct cds_wfs_stack *s, struct cds_wfs_node *node);
+extern int cds_wfs_push(cds_wfs_stack_ptr_t u_stack, struct cds_wfs_node *node);

 
 /*
  * cds_wfs_pop_blocking: pop a node from the stack.
 
 /*
  * cds_wfs_pop_blocking: pop a node from the stack.

diff --git a/wfstack.c b/wfstack.c
index c8bd7e6214211190be827474c301718882daf7c9..fec9e477c20b3c561b74352ad1acb97004d68ad8 100644 (file)
--- a/wfstack.c
+++ b/wfstack.c
@@ -38,6 +38,11 @@ void cds_wfs_init(struct cds_wfs_stack *s)
        _cds_wfs_init(s);
 }
 
        _cds_wfs_init(s);
 }
 

+void __cds_wfs_init(struct __cds_wfs_stack *s)
+{
+       ___cds_wfs_init(s);
+}
+

 bool cds_wfs_empty(struct cds_wfs_stack *s)
 {
        return _cds_wfs_empty(s);
 bool cds_wfs_empty(struct cds_wfs_stack *s)
 {
        return _cds_wfs_empty(s);


@@ -112,7 +117,7 @@ struct cds_wfs_node *
        return ___cds_wfs_pop_with_state_nonblocking(s, state);
 }
 
        return ___cds_wfs_pop_with_state_nonblocking(s, state);
 }
 

-struct cds_wfs_head *__cds_wfs_pop_all(struct cds_wfs_stack *s)
+struct cds_wfs_head *__cds_wfs_pop_all(cds_wfs_stack_ptr_t u_stack)

 {
 {

-       return ___cds_wfs_pop_all(s);
+       return ___cds_wfs_pop_all(u_stack);

 }
 }