Commit | Line | Data |
---|---|---|
3d02c34d MD |
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 | ||
e17d9985 | 29 | #include <urcu-call-rcu.h> |
a2e7bf9c | 30 | #include <urcu/uatomic.h> |
3d02c34d | 31 | #include <assert.h> |
e17d9985 | 32 | #include <errno.h> |
3d02c34d MD |
33 | |
34 | #ifdef __cplusplus | |
35 | extern "C" { | |
36 | #endif | |
37 | ||
e17d9985 MD |
38 | struct cds_lfq_node_rcu_dummy { |
39 | struct cds_lfq_node_rcu parent; | |
40 | struct rcu_head head; | |
41 | struct cds_lfq_queue_rcu *q; | |
42 | }; | |
43 | ||
3d02c34d | 44 | /* |
e17d9985 MD |
45 | * Lock-free RCU queue. Enqueue and dequeue operations hold a RCU read |
46 | * lock to deal with cmpxchg ABA problem. This queue is *not* circular: | |
47 | * head points to the oldest node, tail points to the newest node. | |
0cca1a2d | 48 | * A dummy node is kept to ensure enqueue and dequeue can always proceed |
e17d9985 MD |
49 | * concurrently. Keeping a separate head and tail helps with large |
50 | * queues: enqueue and dequeue can proceed concurrently without | |
51 | * wrestling for exclusive access to the same variables. | |
52 | * | |
0cca1a2d MD |
53 | * Dequeue retry if it detects that it would be dequeueing the last node |
54 | * (it means a dummy node dequeue-requeue is in progress). This ensures | |
55 | * that there is always at least one node in the queue. | |
e17d9985 | 56 | * |
0cca1a2d MD |
57 | * In the dequeue operation, we internally reallocate the dummy node |
58 | * upon dequeue/requeue and use call_rcu to free the old one after a | |
59 | * grace period. | |
3d02c34d MD |
60 | */ |
61 | ||
e17d9985 MD |
62 | static inline |
63 | struct cds_lfq_node_rcu *make_dummy(struct cds_lfq_queue_rcu *q, | |
64 | struct cds_lfq_node_rcu *next) | |
65 | { | |
66 | struct cds_lfq_node_rcu_dummy *dummy; | |
67 | ||
68 | dummy = malloc(sizeof(struct cds_lfq_node_rcu_dummy)); | |
8f03ed0d | 69 | assert(dummy); |
e17d9985 MD |
70 | dummy->parent.next = next; |
71 | dummy->q = q; | |
909292c2 | 72 | return &dummy->parent; |
e17d9985 MD |
73 | } |
74 | ||
75 | static inline | |
f6719811 | 76 | void free_dummy_cb(struct rcu_head *head) |
e17d9985 MD |
77 | { |
78 | struct cds_lfq_node_rcu_dummy *dummy = | |
79 | caa_container_of(head, struct cds_lfq_node_rcu_dummy, head); | |
80 | free(dummy); | |
81 | } | |
82 | ||
83 | static inline | |
84 | void rcu_free_dummy(struct cds_lfq_node_rcu *node) | |
85 | { | |
86 | struct cds_lfq_node_rcu_dummy *dummy; | |
3d02c34d | 87 | |
909292c2 | 88 | dummy = caa_container_of(node, struct cds_lfq_node_rcu_dummy, parent); |
f6719811 MD |
89 | dummy->q->queue_call_rcu(&dummy->head, free_dummy_cb); |
90 | } | |
91 | ||
92 | static inline | |
93 | void free_dummy(struct cds_lfq_node_rcu *node) | |
94 | { | |
95 | struct cds_lfq_node_rcu_dummy *dummy; | |
96 | ||
97 | dummy = caa_container_of(node, struct cds_lfq_node_rcu_dummy, parent); | |
98 | free(dummy); | |
e17d9985 MD |
99 | } |
100 | ||
101 | static inline | |
16aa9ee8 | 102 | void _cds_lfq_node_init_rcu(struct cds_lfq_node_rcu *node) |
3d02c34d MD |
103 | { |
104 | node->next = NULL; | |
3d02c34d MD |
105 | } |
106 | ||
e17d9985 | 107 | static inline |
d9b52143 | 108 | void _cds_lfq_init_rcu(struct cds_lfq_queue_rcu *q, |
e17d9985 MD |
109 | void queue_call_rcu(struct rcu_head *head, |
110 | void (*func)(struct rcu_head *head))) | |
111 | { | |
112 | q->tail = make_dummy(q, NULL); | |
909292c2 | 113 | q->dummy = q->tail; |
0cca1a2d | 114 | q->head = q->tail; |
e17d9985 MD |
115 | q->queue_call_rcu = queue_call_rcu; |
116 | } | |
117 | ||
118 | /* | |
119 | * The queue should be emptied before calling destroy. | |
120 | * | |
121 | * Return 0 on success, -EPERM if queue is not empty. | |
122 | */ | |
123 | static inline | |
124 | int _cds_lfq_destroy_rcu(struct cds_lfq_queue_rcu *q) | |
3d02c34d | 125 | { |
0cca1a2d | 126 | struct cds_lfq_node_rcu *head; |
e17d9985 MD |
127 | |
128 | head = rcu_dereference(q->head); | |
f6719811 | 129 | if (!(head == q->dummy && head->next == NULL)) |
e17d9985 | 130 | return -EPERM; /* not empty */ |
f6719811 | 131 | free_dummy(head); |
e17d9985 | 132 | return 0; |
3d02c34d MD |
133 | } |
134 | ||
d9b52143 MD |
135 | /* |
136 | * Should be called under rcu read lock critical section. | |
137 | */ | |
e17d9985 | 138 | static inline |
d9b52143 MD |
139 | void _cds_lfq_enqueue_rcu(struct cds_lfq_queue_rcu *q, |
140 | struct cds_lfq_node_rcu *node) | |
3d02c34d | 141 | { |
3d02c34d MD |
142 | /* |
143 | * uatomic_cmpxchg() implicit memory barrier orders earlier stores to | |
144 | * node before publication. | |
145 | */ | |
146 | ||
147 | for (;;) { | |
16aa9ee8 | 148 | struct cds_lfq_node_rcu *tail, *next; |
3d02c34d | 149 | |
3d02c34d | 150 | tail = rcu_dereference(q->tail); |
909292c2 | 151 | next = uatomic_cmpxchg(&tail->next, NULL, node); |
3d02c34d MD |
152 | if (next == NULL) { |
153 | /* | |
154 | * Tail was at the end of queue, we successfully | |
e17d9985 MD |
155 | * appended to it. Now move tail (another |
156 | * enqueue might beat us to it, that's fine). | |
3d02c34d | 157 | */ |
85b57703 | 158 | (void) uatomic_cmpxchg(&q->tail, tail, node); |
3d02c34d MD |
159 | return; |
160 | } else { | |
161 | /* | |
e17d9985 MD |
162 | * Failure to append to current tail. |
163 | * Help moving tail further and retry. | |
3d02c34d | 164 | */ |
85b57703 | 165 | (void) uatomic_cmpxchg(&q->tail, tail, next); |
3d02c34d MD |
166 | continue; |
167 | } | |
168 | } | |
169 | } | |
170 | ||
f6719811 MD |
171 | static inline |
172 | void reenqueue_dummy(struct cds_lfq_queue_rcu *q) | |
173 | { | |
174 | struct cds_lfq_node_rcu *node; | |
175 | ||
176 | /* We need to reallocate to protect from ABA. */ | |
177 | node = make_dummy(q, NULL); | |
178 | if (uatomic_cmpxchg(&q->dummy, NULL, node) != NULL) { | |
179 | /* other dequeue populated its new dummy */ | |
180 | free_dummy(node); | |
181 | return; | |
182 | } | |
183 | _cds_lfq_enqueue_rcu(q, node); | |
184 | } | |
185 | ||
3d02c34d | 186 | /* |
d9b52143 MD |
187 | * Should be called under rcu read lock critical section. |
188 | * | |
e17d9985 MD |
189 | * The caller must wait for a grace period to pass before freeing the returned |
190 | * node or modifying the cds_lfq_node_rcu structure. | |
191 | * Returns NULL if queue is empty. | |
3d02c34d | 192 | */ |
e17d9985 | 193 | static inline |
a34df756 | 194 | struct cds_lfq_node_rcu *_cds_lfq_dequeue_rcu(struct cds_lfq_queue_rcu *q) |
3d02c34d MD |
195 | { |
196 | for (;;) { | |
f6719811 | 197 | struct cds_lfq_node_rcu *head, *next, *dummy; |
3d02c34d | 198 | |
3d02c34d | 199 | head = rcu_dereference(q->head); |
909292c2 | 200 | next = rcu_dereference(head->next); |
f6719811 MD |
201 | dummy = rcu_dereference(q->dummy); |
202 | if (head == dummy && next == NULL) | |
e17d9985 MD |
203 | return NULL; /* empty */ |
204 | /* | |
205 | * We never, ever allow dequeue to get to a state where | |
206 | * the queue is empty (we need at least one node in the | |
207 | * queue). This is ensured by checking if the head next | |
f6719811 MD |
208 | * is NULL. This means a concurrent dummy node |
209 | * re-enqueue is in progress. We help it reach | |
210 | * completion, and retry. | |
e17d9985 | 211 | */ |
f6719811 MD |
212 | if (!next) { |
213 | /* | |
214 | * Dummy node re-enqueue is in progress. Try to | |
215 | * help. | |
216 | */ | |
217 | reenqueue_dummy(q); | |
218 | continue; /* try again */ | |
219 | } | |
220 | if (uatomic_cmpxchg(&q->head, head, next) != head) | |
221 | continue; /* Concurrently pushed. */ | |
222 | if (head == dummy) { | |
223 | /* Free old and requeue new dummy. */ | |
224 | rcu_set_pointer(&q->dummy, NULL); | |
225 | rcu_free_dummy(dummy); | |
226 | reenqueue_dummy(q); | |
227 | continue; /* try again */ | |
3d02c34d | 228 | } |
f6719811 | 229 | return head; |
3d02c34d MD |
230 | } |
231 | } | |
232 | ||
233 | #ifdef __cplusplus | |
234 | } | |
235 | #endif | |
236 | ||
237 | #endif /* _URCU_RCULFQUEUE_STATIC_H */ |