d5c74288831d32e810a045fc068c668e7d60347f
[urcu.git] / 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/urcu_ref.h>
27 #include <assert.h>
28
29 #ifdef __cplusplus
30 extern "C" {
31 #endif
32
33 #if (!defined(_GNU_SOURCE) && !defined(_LGPL_SOURCE))
34 #error "Dynamic loader LGPL wrappers not implemented yet"
35 #endif
36
37 /*
38 * Lock-free RCU queue using reference counting. Enqueue and dequeue operations
39 * hold a RCU read lock to deal with cmpxchg ABA problem. This implementation
40 * keeps a dummy head node to ensure we can always update the queue locklessly.
41 * Given that this is a queue, the dummy head node must always advance as we
42 * dequeue entries. Therefore, we keep a reference count on each entry we are
43 * dequeueing, so they can be kept as dummy head node until the next dequeue, at
44 * which point their reference count will be decremented.
45 */
46
47 #define URCU_LFQ_PERMANENT_REF 128
48
49 struct rcu_lfq_node {
50 struct rcu_lfq_node *next;
51 struct urcu_ref ref;
52 };
53
54 struct rcu_lfq_queue {
55 struct rcu_lfq_node *head, *tail;
56 struct rcu_lfq_node init; /* Dummy initialization node */
57 };
58
59 void rcu_lfq_node_init(struct rcu_lfq_node *node)
60 {
61 node->next = NULL;
62 urcu_ref_init(&node->ref);
63 }
64
65 void rcu_lfq_init(struct rcu_lfq_queue *q)
66 {
67 rcu_lfq_node_init(&q->init);
68 /* Make sure the initial node is never freed. */
69 urcu_ref_set(&q->init.ref, URCU_LFQ_PERMANENT_REF);
70 q->head = q->tail = &q->init;
71 }
72
73 void rcu_lfq_enqueue(struct rcu_lfq_queue *q, struct rcu_lfq_node *node)
74 {
75 urcu_ref_get(&node->ref);
76
77 /*
78 * uatomic_cmpxchg() implicit memory barrier orders earlier stores to
79 * node before publication.
80 */
81
82 for (;;) {
83 struct rcu_lfq_node *tail, *next;
84
85 rcu_read_lock();
86 tail = rcu_dereference(q->tail);
87 /*
88 * Typically expect tail->next to be NULL.
89 */
90 next = uatomic_cmpxchg(&tail->next, NULL, node);
91 if (next == NULL) {
92 /*
93 * Tail was at the end of queue, we successfully
94 * appended to it.
95 * Now move tail (another enqueue might beat
96 * us to it, that's fine).
97 */
98 uatomic_cmpxchg(&q->tail, tail, node);
99 rcu_read_unlock();
100 return;
101 } else {
102 /*
103 * Failure to append to current tail. Help moving tail
104 * further and retry.
105 */
106 uatomic_cmpxchg(&q->tail, tail, next);
107 rcu_read_unlock();
108 continue;
109 }
110 }
111 }
112
113 /*
114 * The entry returned by dequeue must be taken care of by doing a urcu_ref_put,
115 * which calls the release primitive when the reference count drops to zero. A
116 * grace period must be waited after execution of the release callback before
117 * performing the actual memory reclamation or modifying the rcu_lfq_node
118 * structure.
119 * In other words, the entry lfq node returned by dequeue must not be
120 * modified/re-used/freed until the reference count reaches zero and a grace
121 * period has elapsed (after the refcount reached 0).
122 */
123 struct rcu_lfq_node *
124 rcu_lfq_dequeue(struct rcu_lfq_queue *q, void (*release)(struct urcu_ref *))
125 {
126 for (;;) {
127 struct rcu_lfq_node *head, *next;
128
129 rcu_read_lock();
130 head = rcu_dereference(q->head);
131 next = rcu_dereference(head->next);
132 if (next) {
133 if (uatomic_cmpxchg(&q->head, head, next) == head) {
134 rcu_read_unlock();
135 urcu_ref_put(&head->ref, release);
136 return next;
137 } else {
138 /* Concurrently pushed, retry */
139 rcu_read_unlock();
140 continue;
141 }
142 } else {
143 /* Empty */
144 rcu_read_unlock();
145 return NULL;
146 }
147 }
148 }
149
150 #ifdef __cplusplus
151 }
152 #endif
153
154 #endif /* _URCU_RCULFQUEUE_H */
This page took 0.044023 seconds and 4 git commands to generate.