urcu/static/rculfqueue.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/ref.h>
  30 #include <urcu/uatomic.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 _cds_lfq_node_init_rcu(struct cds_lfq_node_rcu *node)
  51 {
  52         node->next = NULL;
  53         urcu_ref_init(&node->ref);
  54 }
  55
  56 void _cds_lfq_init_rcu(struct cds_lfq_queue_rcu *q,
  57                        void (*release)(struct urcu_ref *ref))
  58 {
  59         _cds_lfq_node_init_rcu(&q->init);
  60         /* Make sure the initial node is never freed. */
  61         urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF);
  62         q->head = q->tail = &q->init;
  63         q->release = release;
  64 }
  65
  66 /*
  67  * Should be called under rcu read lock critical section.
  68  */
  69 void _cds_lfq_enqueue_rcu(struct cds_lfq_queue_rcu *q,
  70                           struct cds_lfq_node_rcu *node)
  71 {
  72         urcu_ref_get(&node->ref);
  73         node->queue = q;
  74
  75         /*
  76          * uatomic_cmpxchg() implicit memory barrier orders earlier stores to
  77          * node before publication.
  78          */
  79
  80         for (;;) {
  81                 struct cds_lfq_node_rcu *tail, *next;
  82
  83                 tail = rcu_dereference(q->tail);
  84                 /*
  85                  * Typically expect tail->next to be NULL.
  86                  */
  87                 next = uatomic_cmpxchg(&tail->next, NULL, node);
  88                 if (next == NULL) {
  89                         /*
  90                          * Tail was at the end of queue, we successfully
  91                          * appended to it.
  92                          * Now move tail (another enqueue might beat
  93                          * us to it, that's fine).
  94                          */
  95                         (void) uatomic_cmpxchg(&q->tail, tail, node);
  96                         return;
  97                 } else {
  98                         /*
  99                          * Failure to append to current tail. Help moving tail
 100                          * further and retry.
 101                          */
 102                         (void) uatomic_cmpxchg(&q->tail, tail, next);
 103                         continue;
 104                 }
 105         }
 106 }
 107
 108 /*
 109  * Should be called under rcu read lock critical section.
 110  *
 111  * The entry returned by dequeue must be taken care of by doing a
 112  * sequence of urcu_ref_put which release handler should do a call_rcu.
 113  *
 114  * In other words, the entry lfq node returned by dequeue must not be
 115  * modified/re-used/freed until the reference count reaches zero and a grace
 116  * period has elapsed.
 117  */
 118 struct cds_lfq_node_rcu *_cds_lfq_dequeue_rcu(struct cds_lfq_queue_rcu *q)
 119 {
 120         for (;;) {
 121                 struct cds_lfq_node_rcu *head, *next;
 122
 123                 head = rcu_dereference(q->head);
 124                 next = rcu_dereference(head->next);
 125                 if (next) {
 126                         if (uatomic_cmpxchg(&q->head, head, next) == head) {
 127                                 urcu_ref_put(&head->ref, q->release);
 128                                 return next;
 129                         } else {
 130                                 /* Concurrently pushed, retry */
 131                                 continue;
 132                         }
 133                 } else {
 134                         /* Empty */
 135                         return NULL;
 136                 }
 137         }
 138 }
 139
 140 #ifdef __cplusplus
 141 }
 142 #endif
 143
 144 #endif /* _URCU_RCULFQUEUE_STATIC_H */