From af67624df8d06ebaa5d72dd863a73d334611e900 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Wed, 5 Dec 2012 09:41:08 -0500 Subject: [PATCH] wfstack: implement nonblocking pop and next Signed-off-by: Mathieu Desnoyers --- urcu/static/wfstack.h | 86 ++++++++++++++++++++++++++++++++++--------- urcu/wfstack.h | 18 +++++++++ wfstack.c | 10 +++++ 3 files changed, 96 insertions(+), 18 deletions(-) diff --git a/urcu/static/wfstack.h b/urcu/static/wfstack.h index 018a121..9bc9519 100644 --- a/urcu/static/wfstack.h +++ b/urcu/static/wfstack.h @@ -137,7 +137,7 @@ int _cds_wfs_push(struct cds_wfs_stack *s, struct cds_wfs_node *node) * Waiting for push to complete enqueue and return the next node. */ static inline struct cds_wfs_node * -___cds_wfs_node_sync_next(struct cds_wfs_node *node) +___cds_wfs_node_sync_next(struct cds_wfs_node *node, int blocking) { struct cds_wfs_node *next; int attempt = 0; @@ -146,6 +146,8 @@ ___cds_wfs_node_sync_next(struct cds_wfs_node *node) * Adaptative busy-looping waiting for push to complete. */ while ((next = CMM_LOAD_SHARED(node->next)) == NULL) { + if (!blocking) + return CDS_WFS_WOULDBLOCK; if (++attempt >= CDS_WFS_ADAPT_ATTEMPTS) { poll(NULL, 0, CDS_WFS_WAIT); /* Wait for 10ms */ attempt = 0; @@ -157,6 +159,29 @@ ___cds_wfs_node_sync_next(struct cds_wfs_node *node) return next; } +static inline +struct cds_wfs_node * +___cds_wfs_pop(struct cds_wfs_stack *s, int blocking) +{ + struct cds_wfs_head *head, *new_head; + struct cds_wfs_node *next; + + for (;;) { + head = CMM_LOAD_SHARED(s->head); + if (___cds_wfs_end(head)) + return NULL; + next = ___cds_wfs_node_sync_next(&head->node, blocking); + if (!blocking && next == CDS_WFS_WOULDBLOCK) + return CDS_WFS_WOULDBLOCK; + new_head = caa_container_of(next, struct cds_wfs_head, node); + if (uatomic_cmpxchg(&s->head, head, new_head) == head) + return &head->node; + if (!blocking) + return CDS_WFS_WOULDBLOCK; + /* busy-loop if head changed under us */ + } +} + /* * __cds_wfs_pop_blocking: pop a node from the stack. * @@ -177,19 +202,20 @@ static inline struct cds_wfs_node * ___cds_wfs_pop_blocking(struct cds_wfs_stack *s) { - struct cds_wfs_head *head, *new_head; - struct cds_wfs_node *next; + return ___cds_wfs_pop(s, 1); +} - for (;;) { - head = CMM_LOAD_SHARED(s->head); - if (___cds_wfs_end(head)) - return NULL; - next = ___cds_wfs_node_sync_next(&head->node); - new_head = caa_container_of(next, struct cds_wfs_head, node); - if (uatomic_cmpxchg(&s->head, head, new_head) == head) - return &head->node; - /* busy-loop if head changed under us */ - } +/* + * __cds_wfs_pop_nonblocking: pop a node from the stack. + * + * Same as __cds_wfs_pop_blocking, but returns CDS_WFS_WOULDBLOCK if + * it needs to block. + */ +static inline +struct cds_wfs_node * +___cds_wfs_pop_nonblocking(struct cds_wfs_stack *s) +{ + return ___cds_wfs_pop(s, 0); } /* @@ -303,6 +329,22 @@ _cds_wfs_first(struct cds_wfs_head *head) return &head->node; } +static inline struct cds_wfs_node * +___cds_wfs_next(struct cds_wfs_node *node, int blocking) +{ + struct cds_wfs_node *next; + + next = ___cds_wfs_node_sync_next(node, blocking); + /* + * CDS_WFS_WOULDBLOCK != CSD_WFS_END, so we can check for end + * even if ___cds_wfs_node_sync_next returns CDS_WFS_WOULDBLOCK, + * and still return CDS_WFS_WOULDBLOCK. + */ + if (___cds_wfs_end(next)) + return NULL; + return next; +} + /* * cds_wfs_next_blocking: get next node of a popped stack. * @@ -319,12 +361,20 @@ _cds_wfs_first(struct cds_wfs_head *head) static inline struct cds_wfs_node * _cds_wfs_next_blocking(struct cds_wfs_node *node) { - struct cds_wfs_node *next; + return ___cds_wfs_next(node, 1); +} - next = ___cds_wfs_node_sync_next(node); - if (___cds_wfs_end(next)) - return NULL; - return next; + +/* + * cds_wfs_next_nonblocking: get next node of a popped stack. + * + * Same as cds_wfs_next_blocking, but returns CDS_WFS_WOULDBLOCK if it + * needs to block. + */ +static inline struct cds_wfs_node * +_cds_wfs_next_nonblocking(struct cds_wfs_node *node) +{ + return ___cds_wfs_next(node, 0); } #ifdef __cplusplus diff --git a/urcu/wfstack.h b/urcu/wfstack.h index 0e435ba..03fee8f 100644 --- a/urcu/wfstack.h +++ b/urcu/wfstack.h @@ -58,6 +58,8 @@ extern "C" { * synchronization. */ +#define CDS_WFS_WOULDBLOCK ((void *) -1UL) + /* * struct cds_wfs_node is returned by __cds_wfs_pop, and also used as * iterator on stack. It is not safe to dereference the node next @@ -183,6 +185,14 @@ extern struct cds_wfs_node *cds_wfs_first(struct cds_wfs_head *head); */ extern struct cds_wfs_node *cds_wfs_next_blocking(struct cds_wfs_node *node); +/* + * cds_wfs_next_nonblocking: get next node of a popped stack. + * + * Same as cds_wfs_next_blocking, but returns CDS_WFS_WOULDBLOCK if it + * needs to block. + */ +extern struct cds_wfs_node *cds_wfs_next_nonblocking(struct cds_wfs_node *node); + /* * cds_wfs_pop_lock: lock stack pop-protection mutex. */ @@ -211,6 +221,14 @@ extern void cds_wfs_pop_unlock(struct cds_wfs_stack *s); */ extern struct cds_wfs_node *__cds_wfs_pop_blocking(struct cds_wfs_stack *s); +/* + * __cds_wfs_pop_nonblocking: pop a node from the stack. + * + * Same as __cds_wfs_pop_blocking, but returns CDS_WFS_WOULDBLOCK if + * it needs to block. + */ +extern struct cds_wfs_node *__cds_wfs_pop_nonblocking(struct cds_wfs_stack *s); + /* * __cds_wfs_pop_all: pop all nodes from a stack. * diff --git a/wfstack.c b/wfstack.c index f0bae57..4ccb6b9 100644 --- a/wfstack.c +++ b/wfstack.c @@ -68,6 +68,11 @@ struct cds_wfs_node *cds_wfs_next_blocking(struct cds_wfs_node *node) return _cds_wfs_next_blocking(node); } +struct cds_wfs_node *cds_wfs_next_nonblocking(struct cds_wfs_node *node) +{ + return _cds_wfs_next_nonblocking(node); +} + void cds_wfs_pop_lock(struct cds_wfs_stack *s) { _cds_wfs_pop_lock(s); @@ -83,6 +88,11 @@ struct cds_wfs_node *__cds_wfs_pop_blocking(struct cds_wfs_stack *s) return ___cds_wfs_pop_blocking(s); } +struct cds_wfs_node *__cds_wfs_pop_nonblocking(struct cds_wfs_stack *s) +{ + return ___cds_wfs_pop_nonblocking(s); +} + struct cds_wfs_head *__cds_wfs_pop_all(struct cds_wfs_stack *s) { return ___cds_wfs_pop_all(s); -- 2.34.1