Skip to contentSkip to conversation

wfstack: implement mutex-free wfstack with transparent union

PATCH New Mathieu Desnoyers 2 participants 3 messages Sep 1, 2014 – Sep 2, 2014 3 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

#1 lore raw

Hi Eric,

Good idea to do it also for wfstack.

A few comments below,

----- Original Message -----

Quoted 84 lines

From: "Eric Wong" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], "Paul E. McKenney" <[email protected]>, "Lai Jiangshan" <[email protected]>
Sent: Monday, August 18, 2014 1:02:54 AM
Subject: [PATCH urcu] wfstack: implement mutex-free wfstack with transparent union

This saves space for users who use alternative synchronization mechanisms.

Cc Paul E. McKenney <[email protected]>
Cc Lai Jiangshan <[email protected]>
Cc Mathieu Desnoyers <[email protected]>
---
 urcu/static/wfstack.h | 18 +++++++++++++++---
 urcu/wfstack.h        | 23 +++++++++++++++++++++--
 wfstack.c             |  9 +++++++--
 3 files changed, 43 insertions(+), 7 deletions(-)
urcu/static/wfstack.h +13 -2
index db0d5b8..eb12f37 100644
@@ -77,6 +77,14 @@ void _cds_wfs_node_init(struct cds_wfs_node *node)
 }
 
 /*
+ * __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.
  */
 static inline
@@ -99,8 +107,10 @@ static inline bool ___cds_wfs_end(void *node)
  *
  * 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));
 }
 
@@ -114,8 +124,9 @@ static inline bool _cds_wfs_empty(struct cds_wfs_stack
 *s)
  * 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;
 
urcu/static/wfstack.h +2 -1
 	assert(node->next == NULL);
@@ -269,8 +280,9 @@ ___cds_wfs_pop_nonblocking(struct cds_wfs_stack *s)
  */
 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;
 
 	/*
urcu/wfstack.h +2 -0
index fc0b44b..8d6f22c 100644
@@ -83,11 +83,25 @@ struct cds_wfs_head {
 	struct cds_wfs_node node;
 };
 
+struct __cds_wfs_stack {
+	struct cds_wfs_head *head;

urcu/wfstack.h struct cds_wfs_head { · line 97

Quoted 10 lines
urcu/wfstack.h +5 -0
+};
+
 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_wfcq_head and struct __cds_wfcq_head on any of those two

should be: struct cds_wfs_stack and struct __cds_wfs_stack

Other than that, looks good! Can you send an updated version ?

Thanks,

Mathieu

Quoted 69 lines
urcu/wfstack.h +13 -1
+ * 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>
@@ -136,11 +150,16 @@ extern void cds_wfs_node_init(struct cds_wfs_node
 *node);
 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.
  */
-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.

urcu/wfstack.h +1 -1
@@ -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.
  */
-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.

wfstack.c +7 -3
index c8bd7e6..fec9e47 100644
@@ -38,6 +38,11 @@ void cds_wfs_init(struct cds_wfs_stack *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);
@@ -112,7 +117,7 @@ struct cds_wfs_node *
 	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);
 }
--

EW

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

A message that is not in the archive (sent off-list or not yet received): [email protected]

#3 lore raw

PATCH v2 1/1 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.

Cc Paul E. McKenney <[email protected]>
Cc Lai Jiangshan <[email protected]>
Cc Mathieu Desnoyers <[email protected]>

---

Quoted 6 lines
Quoted 2 lines

+ * The transparent union allows calling functions that work on both
+ * struct cds_wfcq_head and struct __cds_wfcq_head on any of those two

should be: struct cds_wfs_stack and struct __cds_wfs_stack

Other than that, looks good! Can you send an updated version ?

 urcu/static/wfstack.h | 18 +++++++++++++++---
 urcu/wfstack.h        | 23 +++++++++++++++++++++--
 wfstack.c             |  9 +++++++--
 3 files changed, 43 insertions(+), 7 deletions(-)
urcu/static/wfstack.h +15 -3
index db0d5b8..eb12f37 100644
@@ -77,6 +77,14 @@ void _cds_wfs_node_init(struct cds_wfs_node *node)
 }
 
 /*
+ * __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.
  */
 static inline
@@ -99,8 +107,10 @@ static inline bool ___cds_wfs_end(void *node)
  *
  * 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));
 }
 
@@ -114,8 +124,9 @@ static inline bool _cds_wfs_empty(struct cds_wfs_stack *s)
  * 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);
@@ -269,8 +280,9 @@ ___cds_wfs_pop_nonblocking(struct cds_wfs_stack *s)
  */
 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;
 
 	/*
urcu/wfstack.h +21 -2
index fc0b44b..b914f41 100644
@@ -83,11 +83,25 @@ struct cds_wfs_head {
 	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;
 };
 
+/*
+ * 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>
@@ -136,11 +150,16 @@ extern void cds_wfs_node_init(struct cds_wfs_node *node);
 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.
  */
-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.
@@ -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.
  */
-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.
wfstack.c +7 -2
index c8bd7e6..fec9e47 100644
@@ -38,6 +38,11 @@ void cds_wfs_init(struct cds_wfs_stack *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);
@@ -112,7 +117,7 @@ struct cds_wfs_node *
 	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);
 }
Signature · 1 line
EW

A message that is not in the archive (sent off-list or not yet received): [email protected]

author Applied
#5 lore raw

Merged, thanks!

Mathieu

----- Original Message -----

Quoted 174 lines

From: "Eric Wong" <[email protected]>
To: "Mathieu Desnoyers" <[email protected]>
Cc: [email protected], "Paul E. McKenney" <[email protected]>, "Lai Jiangshan" <[email protected]>
Sent: Monday, September 1, 2014 5:25:06 PM
Subject: [PATCH v2] 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.

Cc Paul E. McKenney <[email protected]>
Cc Lai Jiangshan <[email protected]>
Cc Mathieu Desnoyers <[email protected]>

---

Quoted 6 lines
Quoted 2 lines

+ * The transparent union allows calling functions that work on both
+ * struct cds_wfcq_head and struct __cds_wfcq_head on any of those two

should be: struct cds_wfs_stack and struct __cds_wfs_stack

Other than that, looks good! Can you send an updated version ?

 urcu/static/wfstack.h | 18 +++++++++++++++---
 urcu/wfstack.h        | 23 +++++++++++++++++++++--
 wfstack.c             |  9 +++++++--
 3 files changed, 43 insertions(+), 7 deletions(-)
urcu/static/wfstack.h +13 -2
index db0d5b8..eb12f37 100644
@@ -77,6 +77,14 @@ void _cds_wfs_node_init(struct cds_wfs_node *node)
 }
 
 /*
+ * __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.
  */
 static inline
@@ -99,8 +107,10 @@ static inline bool ___cds_wfs_end(void *node)
  *
  * 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));
 }
 
@@ -114,8 +124,9 @@ static inline bool _cds_wfs_empty(struct cds_wfs_stack
 *s)
  * 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;
 
urcu/static/wfstack.h +2 -1
 	assert(node->next == NULL);
@@ -269,8 +280,9 @@ ___cds_wfs_pop_nonblocking(struct cds_wfs_stack *s)
  */
 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;
 
 	/*
urcu/wfstack.h +20 -1
index fc0b44b..b914f41 100644
@@ -83,11 +83,25 @@ struct cds_wfs_head {
 	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;
 };
 
+/*
+ * 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>
@@ -136,11 +150,16 @@ extern void cds_wfs_node_init(struct cds_wfs_node
 *node);
 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.
  */
-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.

urcu/wfstack.h +1 -1
@@ -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.
  */
-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.

wfstack.c +7 -3
index c8bd7e6..fec9e47 100644
@@ -38,6 +38,11 @@ void cds_wfs_init(struct cds_wfs_stack *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);
@@ -112,7 +117,7 @@ struct cds_wfs_node *
 	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);
 }
--

EW

Signature · 3 lines
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com