X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu%2Fwfcqueue.h;h=4e836601bb57220611145fe402a8f7f4cd4a5181;hp=5576cbf4a5c0d928a068817019fea196b5f9174e;hb=b94aaf6f355f45182b46682bd561006c1123e4ab;hpb=8ad4ce587f001ae026d5560ac509c2e48986130b diff --git a/urcu/wfcqueue.h b/urcu/wfcqueue.h index 5576cbf..4e83660 100644 --- a/urcu/wfcqueue.h +++ b/urcu/wfcqueue.h @@ -2,7 +2,7 @@ #define _URCU_WFCQUEUE_H /* - * wfcqueue.h + * urcu/wfcqueue.h * * Userspace RCU library - Concurrent Queue with Wait-Free Enqueue/Blocking Dequeue * @@ -37,10 +37,25 @@ extern "C" { /* * Concurrent queue with wait-free enqueue/blocking dequeue. * - * Inspired from half-wait-free/half-blocking queue implementation done by - * Paul E. McKenney. + * This queue has been designed and implemented collaboratively by + * Mathieu Desnoyers and Lai Jiangshan. Inspired from + * half-wait-free/half-blocking queue implementation done by Paul E. + * McKenney. */ +#define CDS_WFCQ_WOULDBLOCK ((void *) -1UL) + +enum cds_wfcq_ret { + 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; }; @@ -74,31 +89,67 @@ 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 +/* + * Locking ensured by caller by holding cds_wfcq_dequeue_lock(). + * Non-blocking: deque, first, next return CDS_WFCQ_WOULDBLOCK if they + * 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 + #else /* !_LGPL_SOURCE */ /* * 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" 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 * cds_wfcq_splice_blocking() hold the dequeue lock. + * + * Besides locking, mutual exclusion of dequeue, splice and iteration + * can be ensured by performing all of those operations from a single + * thread, without requiring any lock. */ /* @@ -137,8 +188,11 @@ extern void cds_wfcq_dequeue_unlock(struct cds_wfcq_head *head, * * Issues a full memory barrier before enqueue. No mutual exclusion is * required. + * + * Returns false if the queue was empty prior to adding the node. + * Returns true otherwise. */ -extern void cds_wfcq_enqueue(struct cds_wfcq_head *head, +extern bool cds_wfcq_enqueue(struct cds_wfcq_head *head, struct cds_wfcq_tail *tail, struct cds_wfcq_node *node); @@ -148,12 +202,24 @@ extern void 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 dequeuers is ensured internally. + * 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. * @@ -161,36 +227,86 @@ 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 dequeuers is ensured internally. + * 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. */ -extern void cds_wfcq_splice_blocking( +extern enum cds_wfcq_ret cds_wfcq_splice_blocking( struct cds_wfcq_head *dest_q_head, struct cds_wfcq_tail *dest_q_tail, struct cds_wfcq_head *src_q_head, struct cds_wfcq_tail *src_q_tail); /* - * __cds_wfcq_dequeue_blocking: + * __cds_wfcq_dequeue_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. * It is valid to reuse and free a dequeued node immediately. - * Should be called with cds_wfcq_dequeue_lock() held. + * Dequeue/splice/iteration mutual exclusion should be ensured by the + * caller. */ 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. + * + * Same as __cds_wfcq_dequeue_blocking, but returns CDS_WFCQ_WOULDBLOCK + * if it needs to block. + */ +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. * * 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. - * Should be called with cds_wfcq_dequeue_lock() held. + * 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. Never returns CDS_WFCQ_RET_WOULDBLOCK. */ -extern void __cds_wfcq_splice_blocking( +extern enum cds_wfcq_ret __cds_wfcq_splice_blocking( + struct cds_wfcq_head *dest_q_head, + struct cds_wfcq_tail *dest_q_tail, + struct cds_wfcq_head *src_q_head, + struct cds_wfcq_tail *src_q_tail); + +/* + * __cds_wfcq_splice_nonblocking: enqueue all src_q nodes at the end of dest_q. + * + * Same as __cds_wfcq_splice_blocking, but returns + * 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, struct cds_wfcq_tail *dest_q_tail, struct cds_wfcq_head *src_q_head, @@ -201,24 +317,60 @@ extern void __cds_wfcq_splice_blocking( * * Content written into the node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. - * Should be called with cds_wfcq_dequeue_lock() held. + * Dequeue/splice/iteration mutual exclusion should be ensured by the + * caller. + * + * 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, struct cds_wfcq_tail *tail); +/* + * __cds_wfcq_first_nonblocking: get first node of a queue, without dequeuing. + * + * Same as __cds_wfcq_first_blocking, but returns CDS_WFCQ_WOULDBLOCK if + * it needs to block. + */ +extern struct cds_wfcq_node *__cds_wfcq_first_nonblocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail); + /* * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. * * Content written into the node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. - * Should be called with cds_wfcq_dequeue_lock() held. + * Dequeue/splice/iteration mutual exclusion should be ensured by the + * caller. + * + * 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, struct cds_wfcq_tail *tail, struct cds_wfcq_node *node); +/* + * __cds_wfcq_next_blocking: get next node of a queue, without dequeuing. + * + * Same as __cds_wfcq_next_blocking, but returns CDS_WFCQ_WOULDBLOCK if + * it needs to block. + */ +extern struct cds_wfcq_node *__cds_wfcq_next_nonblocking( + struct cds_wfcq_head *head, + struct cds_wfcq_tail *tail, + struct cds_wfcq_node *node); + #endif /* !_LGPL_SOURCE */ /* @@ -230,7 +382,8 @@ extern struct cds_wfcq_node *__cds_wfcq_next_blocking( * * Content written into each node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. - * Should be called with cds_wfcq_dequeue_lock() held. + * Dequeue/splice/iteration mutual exclusion should be ensured by the + * caller. */ #define __cds_wfcq_for_each_blocking(head, tail, node) \ for (node = __cds_wfcq_first_blocking(head, tail); \ @@ -248,7 +401,8 @@ extern struct cds_wfcq_node *__cds_wfcq_next_blocking( * * Content written into each node before enqueue is guaranteed to be * consistent, but no other memory ordering is ensured. - * Should be called with cds_wfcq_dequeue_lock() held. + * Dequeue/splice/iteration mutual exclusion should be ensured by the + * caller. */ #define __cds_wfcq_for_each_blocking_safe(head, tail, node, n) \ for (node = __cds_wfcq_first_blocking(head, tail), \