urcu/rculfqueue-static.h

   1 #ifndef _URCU_RCULFQUEUE_STATIC_H
   2 #define _URCU_RCULFQUEUE_STATIC_H
   3
   4 /*
   5  * rculfqueue-static.h
   6  *
   7  * Userspace RCU library - Lock-Free RCU Queue
   8  *
   9  * Copyright 2010 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
  10  *
  11  * TO BE INCLUDED ONLY IN LGPL-COMPATIBLE CODE. See rculfqueue.h for linking
  12  * dynamically with the userspace rcu library.
  13  *
  14  * This library is free software; you can redistribute it and/or
  15  * modify it under the terms of the GNU Lesser General Public
  16  * License as published by the Free Software Foundation; either
  17  * version 2.1 of the License, or (at your option) any later version.
  18  *
  19  * This library is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  22  * Lesser General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Lesser General Public
  25  * License along with this library; if not, write to the Free Software
  26  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  27  */
  28
  29 #include <urcu/urcu_ref.h>
  30 #include <urcu/uatomic_arch.h>
  31 #include <assert.h>
  32 /* A urcu implementation header should be already included. */
  33
  34 #ifdef __cplusplus
  35 extern "C" {
  36 #endif
  37
  38 /*
  39  * Lock-free RCU queue using reference counting. Enqueue and dequeue operations
  40  * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation
  41  * keeps a dummy head node to ensure we can always update the queue locklessly.
  42  * Given that this is a queue, the dummy head node must always advance as we
  43  * dequeue entries. Therefore, we keep a reference count on each entry we are
  44  * dequeueing, so they can be kept as dummy head node until the next dequeue, at
  45  * which point their reference count will be decremented.
  46  */
  47
  48 #define URCU_LFQ_PERMANENT_REF          128
  49
  50 void _rcu_lfq_node_init(struct rcu_lfq_node *node)
  51 {
  52         node->next = NULL;
  53         urcu_ref_init(&node->ref);
  54 }
  55
  56 void _rcu_lfq_init(struct rcu_lfq_queue *q)
  57 {
  58         _rcu_lfq_node_init(&q->init);
  59         /* Make sure the initial node is never freed. */
  60         urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF);
  61         q->head = q->tail = &q->init;
  62 }
  63
  64 void _rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node)
  65 {
  66         urcu_ref_get(&node->ref);
  67
  68         /*
  69          * uatomic_cmpxchg() implicit memory barrier orders earlier stores to
  70          * node before publication.
  71          */
  72
  73         for (;;) {
  74                 struct rcu_lfq_node *tail, *next;
  75
  76                 rcu_read_lock();
  77                 tail = rcu_dereference(q->tail);
  78                 /*
  79                  * Typically expect tail->next to be NULL.
  80                  */
  81                 next = uatomic_cmpxchg(&tail->next, NULL, node);
  82                 if (next == NULL) {
  83                         /*
  84                          * Tail was at the end of queue, we successfully
  85                          * appended to it.
  86                          * Now move tail (another enqueue might beat
  87                          * us to it, that's fine).
  88                          */
  89                         uatomic_cmpxchg(&q->tail, tail, node);
  90                         rcu_read_unlock();
  91                         return;
  92                 } else {
  93                         /*
  94                          * Failure to append to current tail. Help moving tail
  95                          * further and retry.
  96                          */
  97                         uatomic_cmpxchg(&q->tail, tail, next);
  98                         rcu_read_unlock();
  99                         continue;
 100                 }
 101         }
 102 }
 103
 104 /*
 105  * The entry returned by dequeue must be taken care of by doing a urcu_ref_put,
 106  * which calls the release primitive when the reference count drops to zero. A
 107  * grace period must be waited after execution of the release callback before
 108  * performing the actual memory reclamation or modifying the rcu_lfq_node
 109  * structure.
 110  * In other words, the entry lfq node returned by dequeue must not be
 111  * modified/re-used/freed until the reference count reaches zero and a grace
 112  * period has elapsed (after the refcount reached 0).
 113  */
 114 struct rcu_lfq_node *
 115 _rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *))
 116 {
 117         for (;;) {
 118                 struct rcu_lfq_node *head, *next;
 119
 120                 rcu_read_lock();
 121                 head = rcu_dereference(q->head);
 122                 next = rcu_dereference(head->next);
 123                 if (next) {
 124                         if (uatomic_cmpxchg(&q->head, head, next) == head) {
 125                                 rcu_read_unlock();
 126                                 urcu_ref_put(&head->ref, release);
 127                                 return next;
 128                         } else {
 129                                 /* Concurrently pushed, retry */
 130                                 rcu_read_unlock();
 131                                 continue;
 132                         }
 133                 } else {
 134                         /* Empty */
 135                         rcu_read_unlock();
 136                         return NULL;
 137                 }
 138         }
 139 }
 140
 141 #ifdef __cplusplus
 142 }
 143 #endif
 144
 145 #endif /* _URCU_RCULFQUEUE_STATIC_H */