From: Mathieu Desnoyers Date: Mon, 6 May 2013 13:33:36 +0000 (-0400) Subject: wfcqueue: return whether dequeue is dequeuing last element X-Git-Tag: v0.8.0~89 X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=commitdiff_plain;h=eec791af9cc9835682c2a72020171eb64737aff7 wfcqueue: return whether dequeue is dequeuing last element Newly introduced "with_state" dequeue API members return queue state atomically sampled with the dequeue operation. Allow testing behavior of dequeue with respect to number of enqueue-to-empty and splice-from-non-empty. Signed-off-by: Mathieu Desnoyers --- diff --git a/urcu/static/wfcqueue.h b/urcu/static/wfcqueue.h index af7a8c6..62e003f 100644 --- a/urcu/static/wfcqueue.h +++ b/urcu/static/wfcqueue.h @@ -350,18 +350,24 @@ ___cds_wfcq_next_nonblocking(struct cds_wfcq_head *head, } static inline struct cds_wfcq_node * -___cds_wfcq_dequeue(struct cds_wfcq_head *head, +___cds_wfcq_dequeue_with_state(struct cds_wfcq_head *head, struct cds_wfcq_tail *tail, + int *state, int blocking) { struct cds_wfcq_node *node, *next; - if (_cds_wfcq_empty(head, tail)) + if (state) + *state = 0; + + if (_cds_wfcq_empty(head, tail)) { return NULL; + } node = ___cds_wfcq_node_sync_next(&head->node, blocking); - if (!blocking && node == CDS_WFCQ_WOULDBLOCK) + if (!blocking && node == CDS_WFCQ_WOULDBLOCK) { return CDS_WFCQ_WOULDBLOCK; + } if ((next = CMM_LOAD_SHARED(node->next)) == NULL) { /* @@ -379,8 +385,11 @@ ___cds_wfcq_dequeue(struct cds_wfcq_head *head, * content. */ _cds_wfcq_node_init(&head->node); - if (uatomic_cmpxchg(&tail->p, node, &head->node) == node) + if (uatomic_cmpxchg(&tail->p, node, &head->node) == node) { + if (state) + *state |= CDS_WFCQ_STATE_LAST; return node; + } next = ___cds_wfcq_node_sync_next(node, blocking); /* * In nonblocking mode, if we would need to block to @@ -404,7 +413,7 @@ ___cds_wfcq_dequeue(struct cds_wfcq_head *head, } /* - * __cds_wfcq_dequeue_blocking: dequeue a node from the queue. + * __cds_wfcq_dequeue_with_state_blocking: dequeue node from queue, with state. * * Content written into the node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. @@ -413,23 +422,49 @@ ___cds_wfcq_dequeue(struct cds_wfcq_head *head, * caller. */ static inline struct cds_wfcq_node * +___cds_wfcq_dequeue_with_state_blocking(struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, int *state) +{ + return ___cds_wfcq_dequeue_with_state(head, tail, state, 1); +} + +/* + * ___cds_wfcq_dequeue_blocking: dequeue node from queue. + * + * Same as __cds_wfcq_dequeue_with_state_blocking, but without saving + * state. + */ +static inline struct cds_wfcq_node * ___cds_wfcq_dequeue_blocking(struct cds_wfcq_head *head, struct cds_wfcq_tail *tail) { - return ___cds_wfcq_dequeue(head, tail, 1); + return ___cds_wfcq_dequeue_with_state_blocking(head, tail, NULL); } /* - * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue. + * __cds_wfcq_dequeue_with_state_nonblocking: dequeue node, with state. * * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK * if it needs to block. */ static inline struct cds_wfcq_node * +___cds_wfcq_dequeue_with_state_nonblocking(struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, int *state) +{ + return ___cds_wfcq_dequeue_with_state(head, tail, state, 0); +} + +/* + * ___cds_wfcq_dequeue_nonblocking: dequeue node from queue. + * + * Same as __cds_wfcq_dequeue_with_state_nonblocking, but without saving + * state. + */ +static inline struct cds_wfcq_node * ___cds_wfcq_dequeue_nonblocking(struct cds_wfcq_head *head, struct cds_wfcq_tail *tail) { - return ___cds_wfcq_dequeue(head, tail, 0); + return ___cds_wfcq_dequeue_with_state_nonblocking(head, tail, NULL); } /* @@ -532,7 +567,7 @@ ___cds_wfcq_splice_nonblocking( } /* - * cds_wfcq_dequeue_blocking: dequeue a node from a wait-free queue. + * cds_wfcq_dequeue_with_state_blocking: dequeue a node from a wait-free queue. * * Content written into the node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. @@ -541,17 +576,29 @@ ___cds_wfcq_splice_nonblocking( * It is valid to reuse and free a dequeued node immediately. */ static inline struct cds_wfcq_node * -_cds_wfcq_dequeue_blocking(struct cds_wfcq_head *head, - struct cds_wfcq_tail *tail) +_cds_wfcq_dequeue_with_state_blocking(struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, int *state) { struct cds_wfcq_node *retval; _cds_wfcq_dequeue_lock(head, tail); - retval = ___cds_wfcq_dequeue_blocking(head, tail); + retval = ___cds_wfcq_dequeue_with_state_blocking(head, tail, state); _cds_wfcq_dequeue_unlock(head, tail); return retval; } +/* + * cds_wfcq_dequeue_blocking: dequeue node from queue. + * + * Same as cds_wfcq_dequeue_blocking, but without saving state. + */ +static inline struct cds_wfcq_node * +_cds_wfcq_dequeue_blocking(struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail) +{ + return _cds_wfcq_dequeue_with_state_blocking(head, tail, NULL); +} + /* * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. * diff --git a/urcu/wfcqueue.h b/urcu/wfcqueue.h index 4ce8fe9..652b42d 100644 --- a/urcu/wfcqueue.h +++ b/urcu/wfcqueue.h @@ -52,6 +52,10 @@ enum cds_wfcq_ret { CDS_WFCQ_RET_SRC_EMPTY = 2, }; +enum cds_wfcq_state { + CDS_WFCQ_STATE_LAST = (1U << 0), +}; + struct cds_wfcq_node { struct cds_wfcq_node *next; }; @@ -85,12 +89,16 @@ struct cds_wfcq_tail { /* Locking performed within cds_wfcq calls. */ #define cds_wfcq_dequeue_blocking _cds_wfcq_dequeue_blocking +#define cds_wfcq_dequeue_with_state_blocking \ + _cds_wfcq_dequeue_with_state_blocking #define cds_wfcq_splice_blocking _cds_wfcq_splice_blocking #define cds_wfcq_first_blocking _cds_wfcq_first_blocking #define cds_wfcq_next_blocking _cds_wfcq_next_blocking /* Locking ensured by caller by holding cds_wfcq_dequeue_lock() */ #define __cds_wfcq_dequeue_blocking ___cds_wfcq_dequeue_blocking +#define __cds_wfcq_dequeue_with_state_blocking \ + ___cds_wfcq_dequeue_with_state_blocking #define __cds_wfcq_splice_blocking ___cds_wfcq_splice_blocking #define __cds_wfcq_first_blocking ___cds_wfcq_first_blocking #define __cds_wfcq_next_blocking ___cds_wfcq_next_blocking @@ -101,6 +109,8 @@ struct cds_wfcq_tail { * need to block. splice returns nonzero if it needs to block. */ #define __cds_wfcq_dequeue_nonblocking ___cds_wfcq_dequeue_nonblocking +#define __cds_wfcq_dequeue_with_state_nonblocking \ + ___cds_wfcq_dequeue_with_state_nonblocking #define __cds_wfcq_splice_nonblocking ___cds_wfcq_splice_nonblocking #define __cds_wfcq_first_nonblocking ___cds_wfcq_first_nonblocking #define __cds_wfcq_next_nonblocking ___cds_wfcq_next_nonblocking @@ -199,6 +209,17 @@ extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking( struct cds_wfcq_head *head, struct cds_wfcq_tail *tail); +/* + * cds_wfcq_dequeue_with_state_blocking: dequeue with state. + * + * Same as cds_wfcq_dequeue_blocking, but saves whether dequeueing the + * last node of the queue into state (CDS_WFCQ_STATE_LAST). + */ +extern struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, + int *state); + /* * cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. * @@ -231,6 +252,17 @@ extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( struct cds_wfcq_head *head, struct cds_wfcq_tail *tail); +/* + * __cds_wfcq_dequeue_with_state_blocking: dequeue with state. + * + * Same as __cds_wfcq_dequeue_blocking, but saves whether dequeueing the + * last node of the queue into state (CDS_WFCQ_STATE_LAST). + */ +extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, + int *state); + /* * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue. * @@ -241,6 +273,17 @@ extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking( struct cds_wfcq_head *head, struct cds_wfcq_tail *tail); +/* + * __cds_wfcq_dequeue_with_state_blocking: dequeue with state. + * + * Same as __cds_wfcq_dequeue_nonblocking, but saves whether dequeueing + * the last node of the queue into state (CDS_WFCQ_STATE_LAST). + */ +extern struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, + int *state); + /* * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. * diff --git a/wfcqueue.c b/wfcqueue.c index ab0eb93..4950c10 100644 --- a/wfcqueue.c +++ b/wfcqueue.c @@ -73,6 +73,14 @@ struct cds_wfcq_node *cds_wfcq_dequeue_blocking( return _cds_wfcq_dequeue_blocking(head, tail); } +struct cds_wfcq_node *cds_wfcq_dequeue_with_state_blocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, + int *state) +{ + return _cds_wfcq_dequeue_with_state_blocking(head, tail, state); +} + enum cds_wfcq_ret cds_wfcq_splice_blocking( struct cds_wfcq_head *dest_q_head, struct cds_wfcq_tail *dest_q_tail, @@ -90,6 +98,14 @@ struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( return ___cds_wfcq_dequeue_blocking(head, tail); } +struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_blocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, + int *state) +{ + return ___cds_wfcq_dequeue_with_state_blocking(head, tail, state); +} + struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking( struct cds_wfcq_head *head, struct cds_wfcq_tail *tail) @@ -97,6 +113,14 @@ struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking( return ___cds_wfcq_dequeue_nonblocking(head, tail); } +struct cds_wfcq_node *__cds_wfcq_dequeue_with_state_nonblocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, + int *state) +{ + return ___cds_wfcq_dequeue_with_state_nonblocking(head, tail, state); +} + enum cds_wfcq_ret __cds_wfcq_splice_blocking( struct cds_wfcq_head *dest_q_head, struct cds_wfcq_tail *dest_q_tail,