X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu%2Fwfcqueue.h;h=c65780e35887d93915849d7af4cff3e5bcc28b98;hp=ddf6b87c478eb808d72fbeb8242fb294726933c5;hb=b4edfa8157bb45827c3236809e550b4d13c0ae22;hpb=23773356a9fd12bf12627df437d0c7bd20e8ef01 diff --git a/urcu/wfcqueue.h b/urcu/wfcqueue.h index ddf6b87..c65780e 100644 --- a/urcu/wfcqueue.h +++ b/urcu/wfcqueue.h @@ -43,15 +43,19 @@ extern "C" { * McKenney. */ -#define CDS_WFCQ_WOULDBLOCK ((void *) -1UL) +#define CDS_WFCQ_WOULDBLOCK ((struct cds_wfcq_node *) -1UL) enum cds_wfcq_ret { - CDS_WFCQ_RET_WOULDBLOCK = -1, + CDS_WFCQ_RET_WOULDBLOCK = -1, CDS_WFCQ_RET_DEST_EMPTY = 0, CDS_WFCQ_RET_DEST_NON_EMPTY = 1, 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; }; @@ -61,11 +65,65 @@ struct cds_wfcq_node { * enqueue/dequeue are expected from many CPUs. This eliminates * false-sharing between enqueue and dequeue. */ +struct __cds_wfcq_head { + struct cds_wfcq_node node; +}; + struct cds_wfcq_head { struct cds_wfcq_node node; pthread_mutex_t lock; }; +#ifndef __cplusplus +/* + * The transparent union allows calling functions that work on both + * struct cds_wfcq_head and struct __cds_wfcq_head on any of those two + * types. + */ +typedef union { + struct __cds_wfcq_head *_h; + struct cds_wfcq_head *h; +} __attribute__((__transparent_union__)) cds_wfcq_head_ptr_t; + +/* + * This static inline is only present for compatibility with C++. It is + * effect-less in C. + */ +static inline struct __cds_wfcq_head *__cds_wfcq_head_cast(struct __cds_wfcq_head *head) +{ + return head; +} + +/* + * This static inline is only present for compatibility with C++. It is + * effect-less in C. + */ +static inline struct cds_wfcq_head *cds_wfcq_head_cast(struct cds_wfcq_head *head) +{ + return head; +} +#else /* #ifndef __cplusplus */ + +/* C++ ignores transparent union. */ +typedef union { + struct __cds_wfcq_head *_h; + struct cds_wfcq_head *h; +} cds_wfcq_head_ptr_t; + +/* C++ ignores transparent union. Requires an explicit conversion. */ +static inline cds_wfcq_head_ptr_t __cds_wfcq_head_cast(struct __cds_wfcq_head *head) +{ + cds_wfcq_head_ptr_t ret = { ._h = head }; + return ret; +} +/* C++ ignores transparent union. Requires an explicit conversion. */ +static inline cds_wfcq_head_ptr_t cds_wfcq_head_cast(struct cds_wfcq_head *head) +{ + cds_wfcq_head_ptr_t ret = { .h = head }; + return ret; +} +#endif /* #else #ifndef __cplusplus */ + struct cds_wfcq_tail { struct cds_wfcq_node *p; }; @@ -76,6 +134,7 @@ struct cds_wfcq_tail { #define cds_wfcq_node_init _cds_wfcq_node_init #define cds_wfcq_init _cds_wfcq_init +#define __cds_wfcq_init ___cds_wfcq_init #define cds_wfcq_empty _cds_wfcq_empty #define cds_wfcq_enqueue _cds_wfcq_enqueue @@ -85,12 +144,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 +164,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 @@ -110,13 +175,28 @@ struct cds_wfcq_tail { /* * Mutual exclusion of cds_wfcq_* / __cds_wfcq_* API * - * Unless otherwise stated, the caller must ensure mutual exclusion of - * queue update operations "dequeue" and "splice" (for source queue). - * Queue read operations "first" and "next", which are used by - * "for_each" iterations, need to be protected against concurrent - * "dequeue" and "splice" (for source queue) by the caller. - * "enqueue", "splice" (for destination queue), and "empty" are the only - * operations that can be used without any mutual exclusion. + * Synchronization table: + * + * External synchronization techniques described in the API below is + * required between pairs marked with "X". No external synchronization + * required between pairs marked with "-". + * + * Legend: + * [1] cds_wfcq_enqueue + * [2] __cds_wfcq_splice (destination queue) + * [3] __cds_wfcq_dequeue + * [4] __cds_wfcq_splice (source queue) + * [5] __cds_wfcq_first + * [6] __cds_wfcq_next + * + * [1] [2] [3] [4] [5] [6] + * [1] - - - - - - + * [2] - - - - - - + * [3] - - X X X X + * [4] - - X - X X + * [5] - - X X - - + * [6] - - X X - - + * * Mutual exclusion can be ensured by holding cds_wfcq_dequeue_lock(). * * For convenience, cds_wfcq_dequeue_blocking() and @@ -138,12 +218,18 @@ extern void cds_wfcq_node_init(struct cds_wfcq_node *node); extern void cds_wfcq_init(struct cds_wfcq_head *head, struct cds_wfcq_tail *tail); +/* + * __cds_wfcq_init: initialize wait-free queue. + */ +extern void __cds_wfcq_init(struct __cds_wfcq_head *head, + struct cds_wfcq_tail *tail); + /* * cds_wfcq_empty: return whether wait-free queue is empty. * * No memory barrier is issued. No mutual exclusion is required. */ -extern bool cds_wfcq_empty(struct cds_wfcq_head *head, +extern bool cds_wfcq_empty(cds_wfcq_head_ptr_t head, struct cds_wfcq_tail *tail); /* @@ -167,7 +253,7 @@ extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head, * Returns false if the queue was empty prior to adding the node. * Returns true otherwise. */ -extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head, +extern bool cds_wfcq_enqueue(cds_wfcq_head_ptr_t head, struct cds_wfcq_tail *tail, struct cds_wfcq_node *node); @@ -177,13 +263,24 @@ extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head, * Content written into the node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. * It is valid to reuse and free a dequeued node immediately. - * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is + * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is * ensured. */ 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. * @@ -191,11 +288,11 @@ extern struct cds_wfcq_node *cds_wfcq_dequeue_blocking( * dest_q must be already initialized. * Content written into the node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. - * Mutual exlusion with cds_wfcq_dequeue_blocking and dequeue lock is + * Mutual exclusion with cds_wfcq_dequeue_blocking and dequeue lock is * ensured. * * Returns enum cds_wfcq_ret which indicates the state of the src or - * dest queue. Cannot block. + * dest queue. */ extern enum cds_wfcq_ret cds_wfcq_splice_blocking( struct cds_wfcq_head *dest_q_head, @@ -213,9 +310,20 @@ extern enum cds_wfcq_ret cds_wfcq_splice_blocking( * caller. */ extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( - struct cds_wfcq_head *head, + cds_wfcq_head_ptr_t 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( + cds_wfcq_head_ptr_t head, + struct cds_wfcq_tail *tail, + int *state); + /* * __cds_wfcq_dequeue_nonblocking: dequeue a node from a wait-free queue. * @@ -223,26 +331,34 @@ extern struct cds_wfcq_node *__cds_wfcq_dequeue_blocking( * if it needs to block. */ extern struct cds_wfcq_node *__cds_wfcq_dequeue_nonblocking( - struct cds_wfcq_head *head, + cds_wfcq_head_ptr_t 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( + cds_wfcq_head_ptr_t head, + struct cds_wfcq_tail *tail, + int *state); + /* * __cds_wfcq_splice_blocking: enqueue all src_q nodes at the end of dest_q. * * Dequeue all nodes from src_q. * dest_q must be already initialized. - * Content written into the node before enqueue is guaranteed to be - * consistent, but no other memory ordering is ensured. - * Dequeue/splice/iteration mutual exclusion for src_q should be ensured - * by the caller. - * + * Mutual exclusion for src_q should be ensured by the caller as + * specified in the "Synchronisation table". * Returns enum cds_wfcq_ret which indicates the state of the src or - * dest queue. Cannot block. + * dest queue. Never returns CDS_WFCQ_RET_WOULDBLOCK. */ extern enum cds_wfcq_ret __cds_wfcq_splice_blocking( - struct cds_wfcq_head *dest_q_head, + cds_wfcq_head_ptr_t dest_q_head, struct cds_wfcq_tail *dest_q_tail, - struct cds_wfcq_head *src_q_head, + cds_wfcq_head_ptr_t src_q_head, struct cds_wfcq_tail *src_q_tail); /* @@ -252,9 +368,9 @@ extern enum cds_wfcq_ret __cds_wfcq_splice_blocking( * CDS_WFCQ_RET_WOULDBLOCK if it needs to block. */ extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking( - struct cds_wfcq_head *dest_q_head, + cds_wfcq_head_ptr_t dest_q_head, struct cds_wfcq_tail *dest_q_tail, - struct cds_wfcq_head *src_q_head, + cds_wfcq_head_ptr_t src_q_head, struct cds_wfcq_tail *src_q_tail); /* @@ -268,9 +384,11 @@ extern enum cds_wfcq_ret __cds_wfcq_splice_nonblocking( * Used by for-like iteration macros: * __cds_wfcq_for_each_blocking() * __cds_wfcq_for_each_blocking_safe() + * + * Returns NULL if queue is empty, first node otherwise. */ extern struct cds_wfcq_node *__cds_wfcq_first_blocking( - struct cds_wfcq_head *head, + cds_wfcq_head_ptr_t head, struct cds_wfcq_tail *tail); /* @@ -280,7 +398,7 @@ extern struct cds_wfcq_node *__cds_wfcq_first_blocking( * it needs to block. */ extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking( - struct cds_wfcq_head *head, + cds_wfcq_head_ptr_t head, struct cds_wfcq_tail *tail); /* @@ -294,9 +412,12 @@ extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking( * Used by for-like iteration macros: * __cds_wfcq_for_each_blocking() * __cds_wfcq_for_each_blocking_safe() + * + * Returns NULL if reached end of queue, non-NULL next queue node + * otherwise. */ extern struct cds_wfcq_node *__cds_wfcq_next_blocking( - struct cds_wfcq_head *head, + cds_wfcq_head_ptr_t head, struct cds_wfcq_tail *tail, struct cds_wfcq_node *node); @@ -307,7 +428,7 @@ extern struct cds_wfcq_node *__cds_wfcq_next_blocking( * it needs to block. */ extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking( - struct cds_wfcq_head *head, + cds_wfcq_head_ptr_t head, struct cds_wfcq_tail *tail, struct cds_wfcq_node *node); @@ -316,7 +437,7 @@ extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking( /* * __cds_wfcq_for_each_blocking: Iterate over all nodes in a queue, * without dequeuing them. - * @head: head of the queue (struct cds_wfcq_head pointer). + * @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer). * @tail: tail of the queue (struct cds_wfcq_tail pointer). * @node: iterator on the queue (struct cds_wfcq_node pointer). * @@ -333,7 +454,7 @@ extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking( /* * __cds_wfcq_for_each_blocking_safe: Iterate over all nodes in a queue, * without dequeuing them. Safe against deletion. - * @head: head of the queue (struct cds_wfcq_head pointer). + * @head: head of the queue (struct cds_wfcq_head or __cds_wfcq_head pointer). * @tail: tail of the queue (struct cds_wfcq_tail pointer). * @node: iterator on the queue (struct cds_wfcq_node pointer). * @n: struct cds_wfcq_node pointer holding the next pointer (used