]>
Commit | Line | Data |
---|---|---|
9f22b0cf JR |
1 | /* |
2 | * Copyright (c) 2008, 2009, 2010, 2011, 2013, 2014 Nicira, Inc. | |
3 | * | |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); | |
5 | * you may not use this file except in compliance with the License. | |
6 | * You may obtain a copy of the License at: | |
7 | * | |
8 | * http://www.apache.org/licenses/LICENSE-2.0 | |
9 | * | |
10 | * Unless required by applicable law or agreed to in writing, software | |
11 | * distributed under the License is distributed on an "AS IS" BASIS, | |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
13 | * See the License for the specific language governing permissions and | |
14 | * limitations under the License. | |
15 | */ | |
16 | #ifndef RCULIST_H | |
17 | #define RCULIST_H 1 | |
18 | ||
19 | /* A single writer multiple RCU-reader doubly linked list. | |
20 | * | |
21 | * RCU readers may iterate over the list at the same time as a writer is | |
22 | * modifying the list. Multiple writers can be supported by use of mutual | |
23 | * exclusion, but rculist does not provide that, as the user of rculist | |
24 | * typically does that already. | |
25 | * | |
26 | * To be RCU-friendly, the struct rculist instances must be freed via | |
27 | * ovsrcu_postpone(). | |
28 | * | |
ca6ba700 TG |
29 | * The API is almost the same as for struct ovs_list, with the following |
30 | * exeptions: | |
9f22b0cf JR |
31 | * |
32 | * - The 'prev' pointer may not be accessed by the user. | |
33 | * - The 'next' pointer should be accessed via rculist_next() by readers, and | |
34 | * rculist_next_protected() by the writer. | |
35 | * - No rculist_moved(): due to the memory management limitation stated above, | |
36 | * rculist instances may not be reallocated, as realloc may instantly free | |
37 | * the old memory. | |
38 | * - rculist_front() returns a const pointer to accommodate for an RCU reader. | |
39 | * - rculist_splice_hidden(): Spliced elements may not have been visible to | |
40 | * RCU readers before the operation. | |
2541d759 | 41 | * - rculist_poison(): Only poisons the 'prev' pointer. |
9f22b0cf | 42 | * |
ca6ba700 | 43 | * The following functions are variations of the struct ovs_list functions with |
9f22b0cf JR |
44 | * similar names, but are now restricted to the writer use: |
45 | * | |
46 | * - rculist_back_protected() | |
47 | * - rculist_is_short_protected() | |
48 | * - rculist_is_singleton_protected() | |
49 | */ | |
50 | ||
51 | #include <stdbool.h> | |
52 | #include <stddef.h> | |
53 | #include "ovs-rcu.h" | |
54 | #include "util.h" | |
55 | ||
56 | /* A non-existing mutex to make it more difficult for an user to accidentally | |
57 | * keep using the 'prev' pointer. This may be helpful when porting code from | |
ca6ba700 | 58 | * struct ovs_list to rculist. */ |
9f22b0cf JR |
59 | extern struct ovs_mutex rculist_fake_mutex; |
60 | ||
61 | /* Doubly linked list head or element. */ | |
62 | struct rculist { | |
63 | /* Previous list element. */ | |
64 | struct rculist *prev OVS_GUARDED_BY(rculist_fake_mutex); | |
65 | ||
66 | /* Next list element. */ | |
67 | OVSRCU_TYPE(struct rculist *) next; | |
68 | }; | |
69 | ||
70 | /* Easier access to 'next' member. */ | |
71 | static inline const struct rculist *rculist_next(const struct rculist *); | |
72 | static inline struct rculist *rculist_next_protected(const struct rculist *); | |
73 | ||
74 | /* List initialization. */ | |
55951e15 | 75 | #define RCUOVS_LIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) } |
9f22b0cf JR |
76 | |
77 | static inline void rculist_init(struct rculist *list); | |
78 | static inline void rculist_poison(struct rculist *elem); | |
79 | ||
80 | /* List insertion. */ | |
81 | static inline void rculist_insert(struct rculist *list, struct rculist *elem); | |
82 | static inline void rculist_splice_hidden(struct rculist *before, | |
83 | struct rculist *first, | |
84 | struct rculist *last); | |
85 | static inline void rculist_push_front(struct rculist *list, | |
86 | struct rculist *elem); | |
87 | static inline void rculist_push_back(struct rculist *list, | |
88 | struct rculist *elem); | |
89 | static inline void rculist_replace(struct rculist *replacement, | |
90 | struct rculist *replaced); | |
91 | static inline void rculist_move(struct rculist *dst, struct rculist *src); | |
92 | ||
93 | /* List removal. */ | |
94 | static inline struct rculist *rculist_remove(struct rculist *elem); | |
95 | static inline struct rculist *rculist_pop_front(struct rculist *list); | |
96 | static inline struct rculist *rculist_pop_back(struct rculist *list); | |
97 | ||
98 | /* List elements. */ | |
99 | static inline const struct rculist *rculist_front(const struct rculist *); | |
100 | static inline struct rculist *rculist_back_protected(const struct rculist *); | |
101 | ||
102 | /* List properties. */ | |
103 | static inline size_t rculist_size(const struct rculist *); | |
104 | static inline bool rculist_is_empty(const struct rculist *); | |
105 | static inline bool rculist_is_singleton_protected(const struct rculist *); | |
106 | static inline bool rculist_is_short_protected(const struct rculist *); | |
107 | ||
108 | \f | |
109 | /* Inline implementations. */ | |
110 | ||
111 | static inline const struct rculist * | |
112 | rculist_next(const struct rculist *list) | |
113 | { | |
114 | return ovsrcu_get(struct rculist *, &list->next); | |
115 | } | |
116 | ||
117 | static inline struct rculist * | |
118 | rculist_next_protected(const struct rculist *list) | |
119 | ||
120 | { | |
121 | return ovsrcu_get_protected(struct rculist *, &list->next); | |
122 | } | |
123 | ||
124 | static inline void | |
125 | rculist_init(struct rculist *list) | |
126 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
127 | { | |
128 | list->prev = list; | |
129 | ovsrcu_init(&list->next, list); | |
130 | } | |
131 | ||
132 | #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc) | |
133 | ||
9f22b0cf JR |
134 | /* Initializes 'list' with pointers that will (probably) cause segfaults if |
135 | * dereferenced and, better yet, show up clearly in a debugger. */ | |
136 | static inline void | |
137 | rculist_poison(struct rculist *list) | |
138 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
139 | { | |
140 | list->prev = RCULIST_POISON; | |
2541d759 JR |
141 | } |
142 | ||
143 | /* Initializes 'list' with pointers that will (probably) cause segfaults if | |
144 | * dereferenced and, better yet, show up clearly in a debugger. | |
145 | * | |
146 | * This variant poisons also the next pointer, so this may not be called if | |
147 | * this list element is still visible to RCU readers. */ | |
148 | static inline void | |
149 | rculist_poison__(struct rculist *list) | |
150 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
151 | { | |
152 | rculist_poison(list); | |
153 | ovsrcu_set_hidden(&list->next, RCULIST_POISON); | |
9f22b0cf JR |
154 | } |
155 | ||
156 | /* rculist insertion. */ | |
157 | static inline void | |
158 | rculist_insert(struct rculist *before, struct rculist *elem) | |
159 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
160 | { | |
161 | elem->prev = before->prev; | |
162 | ovsrcu_set_hidden(&elem->next, before); | |
163 | ovsrcu_set(&before->prev->next, elem); | |
164 | before->prev = elem; | |
165 | } | |
166 | ||
167 | /* Removes elements 'first' though 'last' (exclusive) from their current list, | |
168 | * which may NOT be visible to any other threads (== be hidden from them), | |
169 | * then inserts them just before 'before'. */ | |
170 | static inline void | |
171 | rculist_splice_hidden(struct rculist *before, struct rculist *first, | |
172 | struct rculist *last) | |
173 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
174 | { | |
175 | struct rculist *last_next; | |
176 | ||
177 | if (first == last) { | |
178 | return; | |
179 | } | |
180 | last = last->prev; | |
181 | ||
182 | /* Cleanly remove 'first'...'last' from its current list. */ | |
183 | last_next = rculist_next_protected(last); | |
184 | last_next->prev = first->prev; | |
185 | ovsrcu_set_hidden(&first->prev->next, last_next); | |
186 | ||
187 | /* Splice 'first'...'last' into new list. */ | |
188 | first->prev = before->prev; | |
189 | ovsrcu_set(&last->next, before); | |
190 | ovsrcu_set(&before->prev->next, first); | |
191 | before->prev = last; | |
192 | } | |
193 | ||
194 | /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in | |
195 | * 'list'. */ | |
196 | static inline void | |
197 | rculist_push_front(struct rculist *list, struct rculist *elem) | |
198 | { | |
199 | rculist_insert(rculist_next_protected(list), elem); | |
200 | } | |
201 | ||
202 | /* Inserts 'elem' at the end of 'list', so that it becomes the back in | |
203 | * 'list'. */ | |
204 | static inline void | |
205 | rculist_push_back(struct rculist *list, struct rculist *elem) | |
206 | { | |
207 | rculist_insert(list, elem); | |
208 | } | |
209 | ||
210 | /* Puts 'element' in the position currently occupied by 'position'. | |
211 | * | |
212 | * Afterward, 'position' is not linked to from the list any more, but still | |
213 | * links to the nodes in the list, and may still be referenced by other threads | |
214 | * until all other threads quiesce. The replaced node ('position') may not be | |
215 | * re-inserted, re-initialized, or deleted until after all other threads have | |
216 | * quiesced (use ovsrcu_postpone). */ | |
217 | static inline void | |
218 | rculist_replace(struct rculist *element, struct rculist *position) | |
219 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
220 | { | |
221 | struct rculist *position_next = rculist_next_protected(position); | |
222 | ||
223 | ovsrcu_set_hidden(&element->next, position_next); | |
224 | position_next->prev = element; | |
225 | element->prev = position->prev; | |
226 | ovsrcu_set(&element->prev->next, element); | |
2541d759 | 227 | rculist_poison(position); |
9f22b0cf JR |
228 | } |
229 | ||
230 | /* Initializes 'dst' with the contents of 'src', compensating for moving it | |
231 | * around in memory. The effect is that, if 'src' was the head of a list, now | |
232 | * 'dst' is the head of a list containing the same elements. | |
233 | * | |
234 | * Memory for 'src' must be kept around until the next RCU quiescent period. | |
235 | * rculist cannot be simply reallocated, so there is no rculist_moved(). */ | |
236 | static inline void | |
237 | rculist_move(struct rculist *dst, struct rculist *src) | |
238 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
239 | { | |
240 | if (!rculist_is_empty(src)) { | |
241 | struct rculist *src_next = rculist_next_protected(src); | |
242 | ||
243 | dst->prev = src->prev; | |
244 | ovsrcu_set_hidden(&dst->next, src_next); | |
245 | ||
246 | src_next->prev = dst; | |
247 | ovsrcu_set(&src->prev->next, dst); | |
248 | } else { | |
249 | rculist_init(dst); | |
250 | } | |
2541d759 | 251 | rculist_poison(src); |
9f22b0cf JR |
252 | } |
253 | ||
254 | /* Removes 'elem' from its list and returns the element that followed it. | |
f47eef15 JR |
255 | * Has no effect when 'elem' is initialized, but not in a list. |
256 | * Undefined behavior if 'elem' is not initialized. | |
9f22b0cf JR |
257 | * |
258 | * Afterward, 'elem' is not linked to from the list any more, but still links | |
259 | * to the nodes in the list, and may still be referenced by other threads until | |
260 | * all other threads quiesce. The removed node ('elem') may not be | |
261 | * re-inserted, re-initialized, or deleted until after all other threads have | |
262 | * quiesced (use ovsrcu_postpone). | |
263 | */ | |
264 | static inline struct rculist * | |
265 | rculist_remove(struct rculist *elem) | |
266 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
267 | { | |
268 | struct rculist *elem_next = rculist_next_protected(elem); | |
269 | ||
270 | elem_next->prev = elem->prev; | |
271 | ovsrcu_set(&elem->prev->next, elem_next); | |
2541d759 | 272 | rculist_poison(elem); |
9f22b0cf JR |
273 | return elem_next; |
274 | } | |
275 | ||
276 | /* Removes the front element from 'list' and returns it. Undefined behavior if | |
277 | * 'list' is empty before removal. | |
278 | * | |
279 | * Afterward, teh returned former first node is not linked to from the list any | |
280 | * more, but still links to the nodes in the list, and may still be referenced | |
281 | * by other threads until all other threads quiesce. The returned node may not | |
282 | * be re-inserted, re-initialized, or deleted until after all other threads | |
283 | * have quiesced (use ovsrcu_postpone). */ | |
284 | static inline struct rculist * | |
285 | rculist_pop_front(struct rculist *list) | |
286 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
287 | { | |
288 | struct rculist *front = rculist_next_protected(list); | |
289 | rculist_remove(front); | |
290 | return front; | |
291 | } | |
292 | ||
293 | /* Removes the back element from 'list' and returns it. | |
294 | * Undefined behavior if 'list' is empty before removal. | |
295 | * | |
296 | * Afterward, teh returned former last node is not linked to from the list any | |
297 | * more, but still links to the nodes in the list, and may still be referenced | |
298 | * by other threads until all other threads quiesce. The returned node may not | |
299 | * be re-inserted, re-initialized, or deleted until after all other threads | |
300 | * have quiesced (use ovsrcu_postpone). */ | |
301 | static inline struct rculist * | |
302 | rculist_pop_back(struct rculist *list) | |
303 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
304 | { | |
305 | struct rculist *back = list->prev; | |
306 | rculist_remove(back); | |
307 | return back; | |
308 | } | |
309 | ||
310 | /* Returns the front element in 'list_'. | |
311 | * Undefined behavior if 'list_' is empty. */ | |
312 | static inline const struct rculist * | |
313 | rculist_front(const struct rculist *list) | |
314 | { | |
315 | ovs_assert(!rculist_is_empty(list)); | |
316 | ||
317 | return rculist_next(list); | |
318 | } | |
319 | ||
320 | /* Returns the back element in 'list_'. | |
f47eef15 | 321 | * Returns the 'list_' itself, if 'list_' is empty. */ |
9f22b0cf | 322 | static inline struct rculist * |
f47eef15 | 323 | rculist_back_protected(const struct rculist *list) |
9f22b0cf JR |
324 | OVS_NO_THREAD_SAFETY_ANALYSIS |
325 | { | |
f47eef15 | 326 | return CONST_CAST(struct rculist *, list)->prev; |
9f22b0cf JR |
327 | } |
328 | ||
329 | /* Returns the number of elements in 'list'. | |
330 | * Runs in O(n) in the number of elements. */ | |
331 | static inline size_t | |
332 | rculist_size(const struct rculist *list) | |
333 | { | |
334 | const struct rculist *e; | |
335 | size_t cnt = 0; | |
336 | ||
337 | for (e = rculist_next(list); e != list; e = rculist_next(e)) { | |
338 | cnt++; | |
339 | } | |
340 | return cnt; | |
341 | } | |
342 | ||
343 | /* Returns true if 'list' is empty, false otherwise. */ | |
344 | static inline bool | |
345 | rculist_is_empty(const struct rculist *list) | |
346 | { | |
347 | return rculist_next(list) == list; | |
348 | } | |
349 | ||
350 | /* Returns true if 'list' has 0 or 1 elements, false otherwise. */ | |
351 | static inline bool | |
352 | rculist_is_short_protected(const struct rculist *list) | |
353 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
354 | { | |
355 | return rculist_next_protected(list) == list->prev; | |
356 | } | |
357 | ||
358 | /* Returns true if 'list' has exactly 1 element, false otherwise. */ | |
359 | static inline bool | |
360 | rculist_is_singleton_protected(const struct rculist *list) | |
361 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
362 | { | |
363 | const struct rculist *list_next = rculist_next_protected(list); | |
364 | ||
365 | return list_next == list->prev && list_next != list; | |
366 | } | |
367 | ||
368 | #define RCULIST_FOR_EACH(ITER, MEMBER, RCULIST) \ | |
369 | for (INIT_CONTAINER(ITER, rculist_next(RCULIST), MEMBER); \ | |
370 | &(ITER)->MEMBER != (RCULIST); \ | |
371 | ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER)) | |
372 | #define RCULIST_FOR_EACH_CONTINUE(ITER, MEMBER, RCULIST) \ | |
373 | for (ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER); \ | |
374 | &(ITER)->MEMBER != (RCULIST); \ | |
375 | ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER)) | |
376 | ||
377 | #define RCULIST_FOR_EACH_REVERSE_PROTECTED(ITER, MEMBER, RCULIST) \ | |
378 | for (INIT_CONTAINER(ITER, (RCULIST)->prev, MEMBER); \ | |
379 | &(ITER)->MEMBER != (RCULIST); \ | |
380 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) | |
381 | #define RCULIST_FOR_EACH_REVERSE_PROTECTED_CONTINUE(ITER, MEMBER, RCULIST) \ | |
382 | for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER); \ | |
383 | &(ITER)->MEMBER != (RCULIST); \ | |
384 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) | |
385 | ||
386 | #define RCULIST_FOR_EACH_PROTECTED(ITER, MEMBER, RCULIST) \ | |
387 | for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \ | |
388 | &(ITER)->MEMBER != (RCULIST); \ | |
389 | ASSIGN_CONTAINER(ITER, rculist_next_protected(&(ITER)->MEMBER), \ | |
390 | MEMBER)) | |
391 | ||
392 | #define RCULIST_FOR_EACH_SAFE_PROTECTED(ITER, NEXT, MEMBER, RCULIST) \ | |
393 | for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \ | |
394 | (&(ITER)->MEMBER != (RCULIST) \ | |
395 | ? INIT_CONTAINER(NEXT, rculist_next_protected(&(ITER)->MEMBER), \ | |
396 | MEMBER), 1 : 0); \ | |
397 | (ITER) = (NEXT)) | |
398 | ||
399 | #endif /* rculist.h */ |