]>
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. | |
41 | * - rculist_poison(): Immediately poisons the 'prev' pointer, and schedules | |
42 | * ovsrcu_postpone() to poison the 'next' pointer. This issues a memory | |
43 | * write operation to the list element, hopefully crashing the program if | |
44 | * the list node was freed or re-used too early. | |
45 | * | |
ca6ba700 | 46 | * The following functions are variations of the struct ovs_list functions with |
9f22b0cf JR |
47 | * similar names, but are now restricted to the writer use: |
48 | * | |
49 | * - rculist_back_protected() | |
50 | * - rculist_is_short_protected() | |
51 | * - rculist_is_singleton_protected() | |
52 | */ | |
53 | ||
54 | #include <stdbool.h> | |
55 | #include <stddef.h> | |
56 | #include "ovs-rcu.h" | |
57 | #include "util.h" | |
58 | ||
59 | /* A non-existing mutex to make it more difficult for an user to accidentally | |
60 | * keep using the 'prev' pointer. This may be helpful when porting code from | |
ca6ba700 | 61 | * struct ovs_list to rculist. */ |
9f22b0cf JR |
62 | extern struct ovs_mutex rculist_fake_mutex; |
63 | ||
64 | /* Doubly linked list head or element. */ | |
65 | struct rculist { | |
66 | /* Previous list element. */ | |
67 | struct rculist *prev OVS_GUARDED_BY(rculist_fake_mutex); | |
68 | ||
69 | /* Next list element. */ | |
70 | OVSRCU_TYPE(struct rculist *) next; | |
71 | }; | |
72 | ||
73 | /* Easier access to 'next' member. */ | |
74 | static inline const struct rculist *rculist_next(const struct rculist *); | |
75 | static inline struct rculist *rculist_next_protected(const struct rculist *); | |
76 | ||
77 | /* List initialization. */ | |
55951e15 | 78 | #define RCUOVS_LIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) } |
9f22b0cf JR |
79 | |
80 | static inline void rculist_init(struct rculist *list); | |
81 | static inline void rculist_poison(struct rculist *elem); | |
82 | ||
83 | /* List insertion. */ | |
84 | static inline void rculist_insert(struct rculist *list, struct rculist *elem); | |
85 | static inline void rculist_splice_hidden(struct rculist *before, | |
86 | struct rculist *first, | |
87 | struct rculist *last); | |
88 | static inline void rculist_push_front(struct rculist *list, | |
89 | struct rculist *elem); | |
90 | static inline void rculist_push_back(struct rculist *list, | |
91 | struct rculist *elem); | |
92 | static inline void rculist_replace(struct rculist *replacement, | |
93 | struct rculist *replaced); | |
94 | static inline void rculist_move(struct rculist *dst, struct rculist *src); | |
95 | ||
96 | /* List removal. */ | |
97 | static inline struct rculist *rculist_remove(struct rculist *elem); | |
98 | static inline struct rculist *rculist_pop_front(struct rculist *list); | |
99 | static inline struct rculist *rculist_pop_back(struct rculist *list); | |
100 | ||
101 | /* List elements. */ | |
102 | static inline const struct rculist *rculist_front(const struct rculist *); | |
103 | static inline struct rculist *rculist_back_protected(const struct rculist *); | |
104 | ||
105 | /* List properties. */ | |
106 | static inline size_t rculist_size(const struct rculist *); | |
107 | static inline bool rculist_is_empty(const struct rculist *); | |
108 | static inline bool rculist_is_singleton_protected(const struct rculist *); | |
109 | static inline bool rculist_is_short_protected(const struct rculist *); | |
110 | ||
111 | \f | |
112 | /* Inline implementations. */ | |
113 | ||
114 | static inline const struct rculist * | |
115 | rculist_next(const struct rculist *list) | |
116 | { | |
117 | return ovsrcu_get(struct rculist *, &list->next); | |
118 | } | |
119 | ||
120 | static inline struct rculist * | |
121 | rculist_next_protected(const struct rculist *list) | |
122 | ||
123 | { | |
124 | return ovsrcu_get_protected(struct rculist *, &list->next); | |
125 | } | |
126 | ||
127 | static inline void | |
128 | rculist_init(struct rculist *list) | |
129 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
130 | { | |
131 | list->prev = list; | |
132 | ovsrcu_init(&list->next, list); | |
133 | } | |
134 | ||
135 | #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc) | |
136 | ||
137 | void rculist_poison__(struct rculist *list); | |
138 | ||
139 | /* Initializes 'list' with pointers that will (probably) cause segfaults if | |
140 | * dereferenced and, better yet, show up clearly in a debugger. */ | |
141 | static inline void | |
142 | rculist_poison(struct rculist *list) | |
143 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
144 | { | |
145 | list->prev = RCULIST_POISON; | |
146 | ovsrcu_postpone(rculist_poison__, list); | |
147 | } | |
148 | ||
149 | /* rculist insertion. */ | |
150 | static inline void | |
151 | rculist_insert(struct rculist *before, struct rculist *elem) | |
152 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
153 | { | |
154 | elem->prev = before->prev; | |
155 | ovsrcu_set_hidden(&elem->next, before); | |
156 | ovsrcu_set(&before->prev->next, elem); | |
157 | before->prev = elem; | |
158 | } | |
159 | ||
160 | /* Removes elements 'first' though 'last' (exclusive) from their current list, | |
161 | * which may NOT be visible to any other threads (== be hidden from them), | |
162 | * then inserts them just before 'before'. */ | |
163 | static inline void | |
164 | rculist_splice_hidden(struct rculist *before, struct rculist *first, | |
165 | struct rculist *last) | |
166 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
167 | { | |
168 | struct rculist *last_next; | |
169 | ||
170 | if (first == last) { | |
171 | return; | |
172 | } | |
173 | last = last->prev; | |
174 | ||
175 | /* Cleanly remove 'first'...'last' from its current list. */ | |
176 | last_next = rculist_next_protected(last); | |
177 | last_next->prev = first->prev; | |
178 | ovsrcu_set_hidden(&first->prev->next, last_next); | |
179 | ||
180 | /* Splice 'first'...'last' into new list. */ | |
181 | first->prev = before->prev; | |
182 | ovsrcu_set(&last->next, before); | |
183 | ovsrcu_set(&before->prev->next, first); | |
184 | before->prev = last; | |
185 | } | |
186 | ||
187 | /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in | |
188 | * 'list'. */ | |
189 | static inline void | |
190 | rculist_push_front(struct rculist *list, struct rculist *elem) | |
191 | { | |
192 | rculist_insert(rculist_next_protected(list), elem); | |
193 | } | |
194 | ||
195 | /* Inserts 'elem' at the end of 'list', so that it becomes the back in | |
196 | * 'list'. */ | |
197 | static inline void | |
198 | rculist_push_back(struct rculist *list, struct rculist *elem) | |
199 | { | |
200 | rculist_insert(list, elem); | |
201 | } | |
202 | ||
203 | /* Puts 'element' in the position currently occupied by 'position'. | |
204 | * | |
205 | * Afterward, 'position' is not linked to from the list any more, but still | |
206 | * links to the nodes in the list, and may still be referenced by other threads | |
207 | * until all other threads quiesce. The replaced node ('position') may not be | |
208 | * re-inserted, re-initialized, or deleted until after all other threads have | |
209 | * quiesced (use ovsrcu_postpone). */ | |
210 | static inline void | |
211 | rculist_replace(struct rculist *element, struct rculist *position) | |
212 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
213 | { | |
214 | struct rculist *position_next = rculist_next_protected(position); | |
215 | ||
216 | ovsrcu_set_hidden(&element->next, position_next); | |
217 | position_next->prev = element; | |
218 | element->prev = position->prev; | |
219 | ovsrcu_set(&element->prev->next, element); | |
220 | ||
221 | #ifndef NDEBUG | |
222 | rculist_poison(position); /* XXX: Some overhead due to ovsrcu_postpone() */ | |
223 | #endif | |
224 | } | |
225 | ||
226 | /* Initializes 'dst' with the contents of 'src', compensating for moving it | |
227 | * around in memory. The effect is that, if 'src' was the head of a list, now | |
228 | * 'dst' is the head of a list containing the same elements. | |
229 | * | |
230 | * Memory for 'src' must be kept around until the next RCU quiescent period. | |
231 | * rculist cannot be simply reallocated, so there is no rculist_moved(). */ | |
232 | static inline void | |
233 | rculist_move(struct rculist *dst, struct rculist *src) | |
234 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
235 | { | |
236 | if (!rculist_is_empty(src)) { | |
237 | struct rculist *src_next = rculist_next_protected(src); | |
238 | ||
239 | dst->prev = src->prev; | |
240 | ovsrcu_set_hidden(&dst->next, src_next); | |
241 | ||
242 | src_next->prev = dst; | |
243 | ovsrcu_set(&src->prev->next, dst); | |
244 | } else { | |
245 | rculist_init(dst); | |
246 | } | |
247 | ||
248 | #ifndef NDEBUG | |
249 | rculist_poison(src); /* XXX: Some overhead due to ovsrcu_postpone() */ | |
250 | #endif | |
251 | } | |
252 | ||
253 | /* Removes 'elem' from its list and returns the element that followed it. | |
f47eef15 JR |
254 | * Has no effect when 'elem' is initialized, but not in a list. |
255 | * Undefined behavior if 'elem' is not initialized. | |
9f22b0cf JR |
256 | * |
257 | * Afterward, 'elem' is not linked to from the list any more, but still links | |
258 | * to the nodes in the list, and may still be referenced by other threads until | |
259 | * all other threads quiesce. The removed node ('elem') may not be | |
260 | * re-inserted, re-initialized, or deleted until after all other threads have | |
261 | * quiesced (use ovsrcu_postpone). | |
262 | */ | |
263 | static inline struct rculist * | |
264 | rculist_remove(struct rculist *elem) | |
265 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
266 | { | |
267 | struct rculist *elem_next = rculist_next_protected(elem); | |
268 | ||
269 | elem_next->prev = elem->prev; | |
270 | ovsrcu_set(&elem->prev->next, elem_next); | |
271 | ||
272 | #ifndef NDEBUG | |
273 | rculist_poison(elem); /* XXX: Some overhead due to ovsrcu_postpone() */ | |
274 | #endif | |
275 | return elem_next; | |
276 | } | |
277 | ||
278 | /* Removes the front element from 'list' and returns it. Undefined behavior if | |
279 | * 'list' is empty before removal. | |
280 | * | |
281 | * Afterward, teh returned former first node is not linked to from the list any | |
282 | * more, but still links to the nodes in the list, and may still be referenced | |
283 | * by other threads until all other threads quiesce. The returned node may not | |
284 | * be re-inserted, re-initialized, or deleted until after all other threads | |
285 | * have quiesced (use ovsrcu_postpone). */ | |
286 | static inline struct rculist * | |
287 | rculist_pop_front(struct rculist *list) | |
288 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
289 | { | |
290 | struct rculist *front = rculist_next_protected(list); | |
291 | rculist_remove(front); | |
292 | return front; | |
293 | } | |
294 | ||
295 | /* Removes the back element from 'list' and returns it. | |
296 | * Undefined behavior if 'list' is empty before removal. | |
297 | * | |
298 | * Afterward, teh returned former last node is not linked to from the list any | |
299 | * more, but still links to the nodes in the list, and may still be referenced | |
300 | * by other threads until all other threads quiesce. The returned node may not | |
301 | * be re-inserted, re-initialized, or deleted until after all other threads | |
302 | * have quiesced (use ovsrcu_postpone). */ | |
303 | static inline struct rculist * | |
304 | rculist_pop_back(struct rculist *list) | |
305 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
306 | { | |
307 | struct rculist *back = list->prev; | |
308 | rculist_remove(back); | |
309 | return back; | |
310 | } | |
311 | ||
312 | /* Returns the front element in 'list_'. | |
313 | * Undefined behavior if 'list_' is empty. */ | |
314 | static inline const struct rculist * | |
315 | rculist_front(const struct rculist *list) | |
316 | { | |
317 | ovs_assert(!rculist_is_empty(list)); | |
318 | ||
319 | return rculist_next(list); | |
320 | } | |
321 | ||
322 | /* Returns the back element in 'list_'. | |
f47eef15 | 323 | * Returns the 'list_' itself, if 'list_' is empty. */ |
9f22b0cf | 324 | static inline struct rculist * |
f47eef15 | 325 | rculist_back_protected(const struct rculist *list) |
9f22b0cf JR |
326 | OVS_NO_THREAD_SAFETY_ANALYSIS |
327 | { | |
f47eef15 | 328 | return CONST_CAST(struct rculist *, list)->prev; |
9f22b0cf JR |
329 | } |
330 | ||
331 | /* Returns the number of elements in 'list'. | |
332 | * Runs in O(n) in the number of elements. */ | |
333 | static inline size_t | |
334 | rculist_size(const struct rculist *list) | |
335 | { | |
336 | const struct rculist *e; | |
337 | size_t cnt = 0; | |
338 | ||
339 | for (e = rculist_next(list); e != list; e = rculist_next(e)) { | |
340 | cnt++; | |
341 | } | |
342 | return cnt; | |
343 | } | |
344 | ||
345 | /* Returns true if 'list' is empty, false otherwise. */ | |
346 | static inline bool | |
347 | rculist_is_empty(const struct rculist *list) | |
348 | { | |
349 | return rculist_next(list) == list; | |
350 | } | |
351 | ||
352 | /* Returns true if 'list' has 0 or 1 elements, false otherwise. */ | |
353 | static inline bool | |
354 | rculist_is_short_protected(const struct rculist *list) | |
355 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
356 | { | |
357 | return rculist_next_protected(list) == list->prev; | |
358 | } | |
359 | ||
360 | /* Returns true if 'list' has exactly 1 element, false otherwise. */ | |
361 | static inline bool | |
362 | rculist_is_singleton_protected(const struct rculist *list) | |
363 | OVS_NO_THREAD_SAFETY_ANALYSIS | |
364 | { | |
365 | const struct rculist *list_next = rculist_next_protected(list); | |
366 | ||
367 | return list_next == list->prev && list_next != list; | |
368 | } | |
369 | ||
370 | #define RCULIST_FOR_EACH(ITER, MEMBER, RCULIST) \ | |
371 | for (INIT_CONTAINER(ITER, rculist_next(RCULIST), MEMBER); \ | |
372 | &(ITER)->MEMBER != (RCULIST); \ | |
373 | ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER)) | |
374 | #define RCULIST_FOR_EACH_CONTINUE(ITER, MEMBER, RCULIST) \ | |
375 | for (ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER); \ | |
376 | &(ITER)->MEMBER != (RCULIST); \ | |
377 | ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER)) | |
378 | ||
379 | #define RCULIST_FOR_EACH_REVERSE_PROTECTED(ITER, MEMBER, RCULIST) \ | |
380 | for (INIT_CONTAINER(ITER, (RCULIST)->prev, MEMBER); \ | |
381 | &(ITER)->MEMBER != (RCULIST); \ | |
382 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) | |
383 | #define RCULIST_FOR_EACH_REVERSE_PROTECTED_CONTINUE(ITER, MEMBER, RCULIST) \ | |
384 | for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER); \ | |
385 | &(ITER)->MEMBER != (RCULIST); \ | |
386 | ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER)) | |
387 | ||
388 | #define RCULIST_FOR_EACH_PROTECTED(ITER, MEMBER, RCULIST) \ | |
389 | for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \ | |
390 | &(ITER)->MEMBER != (RCULIST); \ | |
391 | ASSIGN_CONTAINER(ITER, rculist_next_protected(&(ITER)->MEMBER), \ | |
392 | MEMBER)) | |
393 | ||
394 | #define RCULIST_FOR_EACH_SAFE_PROTECTED(ITER, NEXT, MEMBER, RCULIST) \ | |
395 | for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \ | |
396 | (&(ITER)->MEMBER != (RCULIST) \ | |
397 | ? INIT_CONTAINER(NEXT, rculist_next_protected(&(ITER)->MEMBER), \ | |
398 | MEMBER), 1 : 0); \ | |
399 | (ITER) = (NEXT)) | |
400 | ||
401 | #endif /* rculist.h */ |