wfstack: implement mutex-free wfstack with transparent union
A message that is not in the archive (sent off-list or not yet received): [email protected]
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 unionThis saves space for users who use alternative synchronization mechanisms.
Signed-off-by Eric Wong <[email protected]>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@@ -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
-1assert (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@@ -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@@ -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]
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.
---
Quoted 6 lines
Quoted 2 lines
+ * The transparent union allows calling functions that work on both
+ * structcds_wfcq_headand struct__cds_wfcq_headon any of those twoshould be: struct
cds_wfs_stackand struct__cds_wfs_stackOther 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
@@ -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
@@ -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
@@ -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]
Mathieu Desnoyers
AppliedMerged, 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 unionThis allows users more freedom to use alternative synchronization mechanisms.
Changes since v1:
- Fix typos incds_wfs_stack_ptr_tdocumentation.
Thanks to Mathieu for spotting.Signed-off-by Eric Wong <[email protected]>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
+ * structcds_wfcq_headand struct__cds_wfcq_headon any of those twoshould be: struct
cds_wfs_stackand struct__cds_wfs_stackOther 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@@ -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
-1assert (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@@ -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@@ -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