From c8975b945b18a70ab50beda755370896d30db8fe Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Mon, 6 May 2013 09:35:07 -0400 Subject: [PATCH] wfstack: return whether pop is popping the last element Newly introduced "with_state" pop API members return stack state atomically sampled with the pop operation. Allow testing behavior of pop with respect to number of push-to-empty and pop-all-from-non-empty. Signed-off-by: Mathieu Desnoyers --- urcu/static/wfstack.h | 64 +++++++++++++++++++++++++++++++++++-------- urcu/wfstack.h | 37 +++++++++++++++++++++++++ wfstack.c | 19 +++++++++++++ 3 files changed, 109 insertions(+), 11 deletions(-) diff --git a/urcu/static/wfstack.h b/urcu/static/wfstack.h index 9bc9519..db0d5b8 100644 --- a/urcu/static/wfstack.h +++ b/urcu/static/wfstack.h @@ -161,29 +161,37 @@ ___cds_wfs_node_sync_next(struct cds_wfs_node *node, int blocking) static inline struct cds_wfs_node * -___cds_wfs_pop(struct cds_wfs_stack *s, int blocking) +___cds_wfs_pop(struct cds_wfs_stack *s, int *state, int blocking) { struct cds_wfs_head *head, *new_head; struct cds_wfs_node *next; + if (state) + *state = 0; for (;;) { head = CMM_LOAD_SHARED(s->head); - if (___cds_wfs_end(head)) + if (___cds_wfs_end(head)) { return NULL; + } next = ___cds_wfs_node_sync_next(&head->node, blocking); - if (!blocking && next == CDS_WFS_WOULDBLOCK) + 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) + if (uatomic_cmpxchg(&s->head, head, new_head) == head) { + if (state && ___cds_wfs_end(new_head)) + *state |= CDS_WFS_STATE_LAST; return &head->node; - if (!blocking) + } + if (!blocking) { return CDS_WFS_WOULDBLOCK; + } /* busy-loop if head changed under us */ } } /* - * __cds_wfs_pop_blocking: pop a node from the stack. + * __cds_wfs_pop_with_state_blocking: pop a node from the stack, with state. * * Returns NULL if stack is empty. * @@ -197,12 +205,36 @@ ___cds_wfs_pop(struct cds_wfs_stack *s, int blocking) * __cds_wfs_pop_blocking and __cds_wfs_pop_all callers. * 3) Ensuring that only ONE thread can call __cds_wfs_pop_blocking() * and __cds_wfs_pop_all(). (multi-provider/single-consumer scheme). + * + * "state" saves state flags atomically sampled with pop operation. */ +static inline +struct cds_wfs_node * +___cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state) +{ + return ___cds_wfs_pop(s, state, 1); +} + static inline struct cds_wfs_node * ___cds_wfs_pop_blocking(struct cds_wfs_stack *s) { - return ___cds_wfs_pop(s, 1); + return ___cds_wfs_pop_with_state_blocking(s, NULL); +} + +/* + * __cds_wfs_pop_with_state_nonblocking: pop a node from the stack. + * + * Same as __cds_wfs_pop_with_state_blocking, but returns + * CDS_WFS_WOULDBLOCK if it needs to block. + * + * "state" saves state flags atomically sampled with pop operation. + */ +static inline +struct cds_wfs_node * +___cds_wfs_pop_with_state_nonblocking(struct cds_wfs_stack *s, int *state) +{ + return ___cds_wfs_pop(s, state, 0); } /* @@ -215,7 +247,7 @@ static inline struct cds_wfs_node * ___cds_wfs_pop_nonblocking(struct cds_wfs_stack *s) { - return ___cds_wfs_pop(s, 0); + return ___cds_wfs_pop_with_state_nonblocking(s, NULL); } /* @@ -280,20 +312,30 @@ static inline void _cds_wfs_pop_unlock(struct cds_wfs_stack *s) } /* - * Call __cds_wfs_pop_blocking with an internal pop mutex held. + * Call __cds_wfs_pop_with_state_blocking with an internal pop mutex held. */ static inline struct cds_wfs_node * -_cds_wfs_pop_blocking(struct cds_wfs_stack *s) +_cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state) { struct cds_wfs_node *retnode; _cds_wfs_pop_lock(s); - retnode = ___cds_wfs_pop_blocking(s); + retnode = ___cds_wfs_pop_with_state_blocking(s, state); _cds_wfs_pop_unlock(s); return retnode; } +/* + * Call _cds_wfs_pop_with_state_blocking without saving any state. + */ +static inline +struct cds_wfs_node * +_cds_wfs_pop_blocking(struct cds_wfs_stack *s) +{ + return _cds_wfs_pop_with_state_blocking(s, NULL); +} + /* * Call __cds_wfs_pop_all with an internal pop mutex held. */ diff --git a/urcu/wfstack.h b/urcu/wfstack.h index 34ddb3f..fc0b44b 100644 --- a/urcu/wfstack.h +++ b/urcu/wfstack.h @@ -60,6 +60,10 @@ extern "C" { #define CDS_WFS_WOULDBLOCK ((void *) -1UL) +enum cds_wfs_state { + CDS_WFS_STATE_LAST = (1U << 0), +}; + /* * 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 @@ -95,6 +99,7 @@ struct cds_wfs_stack { /* Locking performed internally */ #define cds_wfs_pop_blocking _cds_wfs_pop_blocking +#define cds_wfs_pop_with_state_blocking _cds_wfs_pop_with_state_blocking #define cds_wfs_pop_all_blocking _cds_wfs_pop_all_blocking /* @@ -111,7 +116,11 @@ struct cds_wfs_stack { /* Synchronization ensured by the caller. See synchronization table. */ #define __cds_wfs_pop_blocking ___cds_wfs_pop_blocking +#define __cds_wfs_pop_with_state_blocking \ + ___cds_wfs_pop_with_state_blocking #define __cds_wfs_pop_nonblocking ___cds_wfs_pop_nonblocking +#define __cds_wfs_pop_with_state_nonblocking \ + ___cds_wfs_pop_with_state_nonblocking #define __cds_wfs_pop_all ___cds_wfs_pop_all #else /* !_LGPL_SOURCE */ @@ -151,6 +160,15 @@ extern int cds_wfs_push(struct cds_wfs_stack *s, struct cds_wfs_node *node); */ extern struct cds_wfs_node *cds_wfs_pop_blocking(struct cds_wfs_stack *s); +/* + * cds_wfs_pop_with_state_blocking: pop a node from the stack, with state. + * + * Same as cds_wfs_pop_blocking, but stores whether the stack was + * empty into state (CDS_WFS_STATE_LAST). + */ +extern struct cds_wfs_node * + cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state); + /* * cds_wfs_pop_all_blocking: pop all nodes from a stack. * @@ -223,6 +241,15 @@ 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_with_state_blocking: pop a node from the stack, with state. + * + * Same as __cds_wfs_pop_blocking, but stores whether the stack was + * empty into state (CDS_WFS_STATE_LAST). + */ +extern struct cds_wfs_node * + __cds_wfs_pop_with_state_blocking(struct cds_wfs_stack *s, int *state); + /* * __cds_wfs_pop_nonblocking: pop a node from the stack. * @@ -231,6 +258,16 @@ extern struct cds_wfs_node *__cds_wfs_pop_blocking(struct cds_wfs_stack *s); */ extern struct cds_wfs_node *__cds_wfs_pop_nonblocking(struct cds_wfs_stack *s); +/* + * __cds_wfs_pop_with_state_nonblocking: pop a node from the stack, with state. + * + * Same as __cds_wfs_pop_nonblocking, but stores whether the stack was + * empty into state (CDS_WFS_STATE_LAST). + */ +extern struct cds_wfs_node * + __cds_wfs_pop_with_state_nonblocking(struct cds_wfs_stack *s, + int *state); + /* * __cds_wfs_pop_all: pop all nodes from a stack. * diff --git a/wfstack.c b/wfstack.c index 4ccb6b9..c8bd7e6 100644 --- a/wfstack.c +++ b/wfstack.c @@ -53,6 +53,12 @@ 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_with_state_blocking(struct cds_wfs_stack *s, int *state) +{ + return _cds_wfs_pop_with_state_blocking(s, state); +} + struct cds_wfs_head *cds_wfs_pop_all_blocking(struct cds_wfs_stack *s) { return _cds_wfs_pop_all_blocking(s); @@ -88,11 +94,24 @@ 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_with_state_blocking(struct cds_wfs_stack *s, int *state) +{ + return ___cds_wfs_pop_with_state_blocking(s, state); +} + struct cds_wfs_node *__cds_wfs_pop_nonblocking(struct cds_wfs_stack *s) { return ___cds_wfs_pop_nonblocking(s); } +struct cds_wfs_node * + __cds_wfs_pop_with_state_nonblocking(struct cds_wfs_stack *s, + int *state) +{ + return ___cds_wfs_pop_with_state_nonblocking(s, state); +} + struct cds_wfs_head *__cds_wfs_pop_all(struct cds_wfs_stack *s) { return ___cds_wfs_pop_all(s); -- 2.34.1