X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=urcu%2Frculfqueue.h;h=e1d64f13d5229e251674919189c8f28d780c8d50;hp=09e5d41ea0db7b7f40032419b070ed55daecdfdd;hb=6e5f88cf94a225b155719046d87bfd32ba47e06a;hpb=23086b720b7edf8b402f22a899568bc6cbcb8235 diff --git a/urcu/rculfqueue.h b/urcu/rculfqueue.h index 09e5d41..e1d64f1 100644 --- a/urcu/rculfqueue.h +++ b/urcu/rculfqueue.h @@ -1,3 +1,6 @@ +#ifndef _URCU_RCULFQUEUE_H +#define _URCU_RCULFQUEUE_H + /* * rculfqueue.h * @@ -20,120 +23,93 @@ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ -#include #include +#include -#if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE)) -#error "Dynamic loader LGPL wrappers not implemented yet" +#ifdef __cplusplus +extern "C" { #endif -/* - * Lock-free RCU queue using reference counting. Enqueue and dequeue operations - * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation - * keeps a dummy head node to ensure we can always update the queue locklessly. - * Given that this is a queue, the dummy head node must always advance as we - * dequeue entries. Therefore, we keep a reference count on each entry we are - * dequeueing, so they can be kept as dummy head node until the next dequeue, at - * which point their reference count will be decremented. - */ - -#define URCU_LFQ_PERMANENT_REF 128 +struct cds_lfq_queue_rcu; -struct rcu_lfq_node { - struct rcu_lfq_node *next; - struct urcu_ref ref; +struct cds_lfq_node_rcu { + struct cds_lfq_node_rcu *next; + int dummy; }; -struct rcu_lfq_queue { - struct rcu_lfq_node *head, *tail; - struct rcu_lfq_node init; /* Dummy initialization node */ +struct cds_lfq_queue_rcu { + struct cds_lfq_node_rcu *head, *tail; + void (*queue_call_rcu)(struct rcu_head *head, + void (*func)(struct rcu_head *head)); }; -void rcu_lfq_node_init(struct rcu_lfq_node *node) -{ - node->next = NULL; - urcu_ref_init(&node->ref); -} +#ifdef _LGPL_SOURCE -void rcu_lfq_init(struct rcu_lfq_queue *q) -{ - rcu_lfq_node_init(&q->init); - /* Make sure the initial node is never freed. */ - urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF); - q->head = q->tail = &q->init; -} +#include -void rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node) -{ - urcu_ref_get(&node->ref); - - /* - * uatomic_cmpxchg() implicit memory barrier orders earlier stores to - * node before publication. - */ - - for (;;) { - struct rcu_lfq_node *tail, *next; - - rcu_read_lock(); - tail = rcu_dereference(q->tail); - /* - * Typically expect tail->next to be NULL. - */ - next = uatomic_cmpxchg(&tail->next, NULL, node); - if (next == NULL) { - /* - * Tail was at the end of queue, we successfully - * appended to it. - * Now move tail (another enqueue might beat - * us to it, that's fine). - */ - uatomic_cmpxchg(&q->tail, tail, node); - rcu_read_unlock(); - return; - } else { - /* - * Failure to append to current tail. Help moving tail - * further and retry. - */ - uatomic_cmpxchg(&q->tail, tail, next); - rcu_read_unlock(); - continue; - } - } -} +#define cds_lfq_node_init_rcu_qsbr _cds_lfq_node_init_rcu +#define cds_lfq_init_rcu_qsbr _cds_lfq_init_rcu +#define cds_lfq_destroy_rcu_qsbr _cds_lfq_destroy_rcu +#define cds_lfq_enqueue_rcu_qsbr _cds_lfq_enqueue_rcu +#define cds_lfq_dequeue_rcu_qsbr _cds_lfq_dequeue_rcu + +#define cds_lfq_node_init_rcu_bp _cds_lfq_node_init_rcu +#define cds_lfq_init_rcu_bp _cds_lfq_init_rcu +#define cds_lfq_destroy_rcu_bp _cds_lfq_destroy_rcu +#define cds_lfq_enqueue_rcu_bp _cds_lfq_enqueue_rcu +#define cds_lfq_dequeue_rcu_bp _cds_lfq_dequeue_rcu + +#define cds_lfq_node_init_rcu_memb _cds_lfq_node_init_rcu +#define cds_lfq_init_rcu_memb _cds_lfq_init_rcu +#define cds_lfq_destroy_rcu_memb _cds_lfq_destroy_rcu +#define cds_lfq_enqueue_rcu_memb _cds_lfq_enqueue_rcu +#define cds_lfq_dequeue_rcu_memb _cds_lfq_dequeue_rcu + +#define cds_lfq_node_init_rcu_mb _cds_lfq_node_init_rcu +#define cds_lfq_init_rcu_mb _cds_lfq_init_rcu +#define cds_lfq_destroy_rcu_mb _cds_lfq_destroy_rcu +#define cds_lfq_enqueue_rcu_mb _cds_lfq_enqueue_rcu +#define cds_lfq_dequeue_rcu_mb _cds_lfq_dequeue_rcu + +#define cds_lfq_node_init_rcu_sig _cds_lfq_node_init_rcu +#define cds_lfq_init_rcu_sig _cds_lfq_init_rcu +#define cds_lfq_destroy_rcu_sig _cds_lfq_destroy_rcu +#define cds_lfq_enqueue_rcu_sig _cds_lfq_enqueue_rcu +#define cds_lfq_dequeue_rcu_sig _cds_lfq_dequeue_rcu + +#else /* !_LGPL_SOURCE */ +extern void cds_lfq_node_init_rcu(struct cds_lfq_node_rcu *node); +extern void cds_lfq_init_rcu(struct cds_lfq_queue_rcu *q, + void queue_call_rcu(struct rcu_head *head, + void (*func)(struct rcu_head *head))); /* - * The entry returned by dequeue must be taken care of by doing a urcu_ref_put, - * which calls the release primitive when the reference count drops to zero. A - * grace period must be waited before performing the actual memory reclamation - * in the release primitive. - * The entry lfq node returned by dequeue must not be re-used before the - * reference count reaches zero. + * The queue should be emptied before calling destroy. + * + * Return 0 on success, -EPERM if queue is not empty. + */ +extern int cds_lfq_destroy_rcu(struct cds_lfq_queue_rcu *q); + +/* + * Should be called under rcu read lock critical section. + */ +extern void cds_lfq_enqueue_rcu(struct cds_lfq_queue_rcu *q, + struct cds_lfq_node_rcu *node); + +/* + * Should be called under rcu read lock critical section. + * + * The caller must wait for a grace period to pass before freeing the returned + * node or modifying the cds_lfq_node_rcu structure. + * Returns NULL if queue is empty. */ -struct rcu_lfq_node * -rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *)) -{ - for (;;) { - struct rcu_lfq_node *head, *next; - - rcu_read_lock(); - head = rcu_dereference(q->head); - next = rcu_dereference(head->next); - if (next) { - if (uatomic_cmpxchg(&q->head, head, next) == head) { - rcu_read_unlock(); - urcu_ref_put(&head->ref, release); - return next; - } else { - /* Concurrently pushed, retry */ - rcu_read_unlock(); - continue; - } - } else { - /* Empty */ - rcu_read_unlock(); - return NULL; - } - } +extern +struct cds_lfq_node_rcu *cds_lfq_dequeue_rcu(struct cds_lfq_queue_rcu *q); + +#endif /* !_LGPL_SOURCE */ + +#ifdef __cplusplus } +#endif + +#endif /* _URCU_RCULFQUEUE_H */