Branch data Line data Source code
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 : : *
29 : : * The API is almost the same as for struct ovs_list, with the following
30 : : * exeptions:
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(): Only poisons the 'prev' pointer.
42 : : *
43 : : * The following functions are variations of the struct ovs_list functions with
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
58 : : * struct ovs_list to rculist. */
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. */
75 : : #define RCUOVS_LIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) }
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 : :
109 : : /* Inline implementations. */
110 : :
111 : : static inline const struct rculist *
112 : 2646163 : rculist_next(const struct rculist *list)
113 : : {
114 : 2646163 : return ovsrcu_get(struct rculist *, &list->next);
115 : : }
116 : :
117 : : static inline struct rculist *
118 : 484263 : rculist_next_protected(const struct rculist *list)
119 : :
120 : : {
121 : 484263 : return ovsrcu_get_protected(struct rculist *, &list->next);
122 : : }
123 : :
124 : : static inline void
125 : 969501 : rculist_init(struct rculist *list)
126 : : OVS_NO_THREAD_SAFETY_ANALYSIS
127 : : {
128 : 969501 : list->prev = list;
129 : 969501 : ovsrcu_init(&list->next, list);
130 : 969501 : }
131 : :
132 : : #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc)
133 : :
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 : 960868 : rculist_poison(struct rculist *list)
138 : : OVS_NO_THREAD_SAFETY_ANALYSIS
139 : : {
140 : 960868 : list->prev = RCULIST_POISON;
141 : 960868 : }
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 : 476605 : rculist_poison__(struct rculist *list)
150 : : OVS_NO_THREAD_SAFETY_ANALYSIS
151 : : {
152 : 476605 : rculist_poison(list);
153 : 476605 : ovsrcu_set_hidden(&list->next, RCULIST_POISON);
154 : 476605 : }
155 : :
156 : : /* rculist insertion. */
157 : : static inline void
158 : 467846 : rculist_insert(struct rculist *before, struct rculist *elem)
159 : : OVS_NO_THREAD_SAFETY_ANALYSIS
160 : : {
161 : 467846 : elem->prev = before->prev;
162 : 467846 : ovsrcu_set_hidden(&elem->next, before);
163 : 467846 : ovsrcu_set(&before->prev->next, elem);
164 : 467846 : before->prev = elem;
165 : 467846 : }
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 : 467846 : rculist_push_back(struct rculist *list, struct rculist *elem)
206 : : {
207 : 467846 : rculist_insert(list, elem);
208 : 467846 : }
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 : 23075 : rculist_replace(struct rculist *element, struct rculist *position)
219 : : OVS_NO_THREAD_SAFETY_ANALYSIS
220 : : {
221 : 23075 : struct rculist *position_next = rculist_next_protected(position);
222 : :
223 : 23075 : ovsrcu_set_hidden(&element->next, position_next);
224 : 23075 : position_next->prev = element;
225 : 23075 : element->prev = position->prev;
226 : 23075 : ovsrcu_set(&element->prev->next, element);
227 : 23075 : rculist_poison(position);
228 : 23075 : }
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 : : }
251 : : rculist_poison(src);
252 : : }
253 : :
254 : : /* Removes 'elem' from its list and returns the element that followed it.
255 : : * Has no effect when 'elem' is initialized, but not in a list.
256 : : * Undefined behavior if 'elem' is not initialized.
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 : 461188 : rculist_remove(struct rculist *elem)
266 : : OVS_NO_THREAD_SAFETY_ANALYSIS
267 : : {
268 : 461188 : struct rculist *elem_next = rculist_next_protected(elem);
269 : :
270 : 461188 : elem_next->prev = elem->prev;
271 : 461188 : ovsrcu_set(&elem->prev->next, elem_next);
272 : 461188 : rculist_poison(elem);
273 : 461188 : 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_'.
321 : : * Returns the 'list_' itself, if 'list_' is empty. */
322 : : static inline struct rculist *
323 : : rculist_back_protected(const struct rculist *list)
324 : : OVS_NO_THREAD_SAFETY_ANALYSIS
325 : : {
326 : : return CONST_CAST(struct rculist *, list)->prev;
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 : 442234 : rculist_is_empty(const struct rculist *list)
346 : : {
347 : 442234 : 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 */
|
