urcu/rculfqueue.h

   1 #ifndef _URCU_RCULFQUEUE_H
   2 #define _URCU_RCULFQUEUE_H
   3
   4 /*
   5  * rculfqueue.h
   6  *
   7  * Userspace RCU library - Lock-Free RCU Queue
   8  *
   9  * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  10  *
  11  * This library is free software; you can redistribute it and/or
  12  * modify it under the terms of the GNU Lesser General Public
  13  * License as published by the Free Software Foundation; either
  14  * version 2.1 of the License, or (at your option) any later version.
  15  *
  16  * This library is distributed in the hope that it will be useful,
  17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19  * Lesser General Public License for more details.
  20  *
  21  * You should have received a copy of the GNU Lesser General Public
  22  * License along with this library; if not, write to the Free Software
  23  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  24  */
  25
  26 #include <urcu/ref.h>
  27 #include <assert.h>
  28
  29 #ifdef __cplusplus
  30 extern "C" {
  31 #endif
  32
  33 /*
  34  * Lock-free RCU queue using reference counting. Enqueue and dequeue operations
  35  * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation
  36  * keeps a dummy head node to ensure we can always update the queue locklessly.
  37  * Given that this is a queue, the dummy head node must always advance as we
  38  * dequeue entries. Therefore, we keep a reference count on each entry we are
  39  * dequeueing, so they can be kept as dummy head node until the next dequeue, at
  40  * which point their reference count will be decremented.
  41  */
  42
  43 struct cds_lfq_queue_rcu;
  44
  45 struct cds_lfq_node_rcu {
  46         struct cds_lfq_node_rcu *next;
  47         struct urcu_ref ref;
  48         struct cds_lfq_queue_rcu *queue;
  49         struct rcu_head rcu_head;
  50 };
  51
  52 struct cds_lfq_queue_rcu {
  53         struct cds_lfq_node_rcu *head, *tail;
  54         struct cds_lfq_node_rcu init;   /* Dummy initialization node */
  55         void (*release)(struct urcu_ref *ref);
  56 };
  57
  58 #ifdef _LGPL_SOURCE
  59
  60 #include <urcu/static/rculfqueue.h>
  61
  62 #define cds_lfq_node_init_rcu           _cds_lfq_node_init_rcu
  63 #define cds_lfq_init_rcu                _cds_lfq_init_rcu
  64 #define cds_lfq_enqueue_rcu             _cds_lfq_enqueue_rcu
  65 #define cds_lfq_dequeue_rcu             _cds_lfq_dequeue_rcu
  66
  67 #else /* !_LGPL_SOURCE */
  68
  69 extern void cds_lfq_node_init_rcu(struct cds_lfq_node_rcu *node);
  70 extern void cds_lfq_init_rcu(struct cds_lfq_queue_rcu *q,
  71                              void (*release)(struct urcu_ref *ref));
  72
  73 /*
  74  * Should be called under rcu read lock critical section.
  75  */
  76 extern void cds_lfq_enqueue_rcu(struct cds_lfq_queue_rcu *q,
  77                                 struct cds_lfq_node_rcu *node);
  78
  79 /*
  80  * Should be called under rcu read lock critical section.
  81  *
  82  * The entry returned by dequeue must be taken care of by doing a
  83  * sequence of urcu_ref_put which release handler should do a call_rcu.
  84  *
  85  * In other words, the entry lfq node returned by dequeue must not be
  86  * modified/re-used/freed until the reference count reaches zero and a grace
  87  * period has elapsed (after the refcount reached 0).
  88  */
  89 extern
  90 struct cds_lfq_node_rcu *cds_lfq_dequeue_rcu(struct cds_lfq_queue_rcu *q);
  91
  92 #endif /* !_LGPL_SOURCE */
  93
  94 #ifdef __cplusplus
  95 }
  96 #endif
  97
  98 #endif /* _URCU_RCULFQUEUE_H */