2 * Copyright (c) 2008, 2009, 2010, 2011, 2013, 2014 Nicira, Inc.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
19 /* A single writer multiple RCU-reader doubly linked list.
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.
26 * To be RCU-friendly, the struct rculist instances must be freed via
29 * The API is almost the same as for struct ovs_list, with the following
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
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.
46 * The following functions are variations of the struct ovs_list functions with
47 * similar names, but are now restricted to the writer use:
49 * - rculist_back_protected()
50 * - rculist_is_short_protected()
51 * - rculist_is_singleton_protected()
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
61 * struct ovs_list to rculist. */
62 extern struct ovs_mutex rculist_fake_mutex;
64 /* Doubly linked list head or element. */
66 /* Previous list element. */
67 struct rculist *prev OVS_GUARDED_BY(rculist_fake_mutex);
69 /* Next list element. */
70 OVSRCU_TYPE(struct rculist *) next;
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 *);
77 /* List initialization. */
78 #define RCUOVS_LIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) }
80 static inline void rculist_init(struct rculist *list);
81 static inline void rculist_poison(struct rculist *elem);
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);
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);
102 static inline const struct rculist *rculist_front(const struct rculist *);
103 static inline struct rculist *rculist_back_protected(const struct rculist *);
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 *);
112 /* Inline implementations. */
114 static inline const struct rculist *
115 rculist_next(const struct rculist *list)
117 return ovsrcu_get(struct rculist *, &list->next);
120 static inline struct rculist *
121 rculist_next_protected(const struct rculist *list)
124 return ovsrcu_get_protected(struct rculist *, &list->next);
128 rculist_init(struct rculist *list)
129 OVS_NO_THREAD_SAFETY_ANALYSIS
132 ovsrcu_init(&list->next, list);
135 #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc)
137 void rculist_poison__(struct rculist *list);
139 /* Initializes 'list' with pointers that will (probably) cause segfaults if
140 * dereferenced and, better yet, show up clearly in a debugger. */
142 rculist_poison(struct rculist *list)
143 OVS_NO_THREAD_SAFETY_ANALYSIS
145 list->prev = RCULIST_POISON;
146 ovsrcu_postpone(rculist_poison__, list);
149 /* rculist insertion. */
151 rculist_insert(struct rculist *before, struct rculist *elem)
152 OVS_NO_THREAD_SAFETY_ANALYSIS
154 elem->prev = before->prev;
155 ovsrcu_set_hidden(&elem->next, before);
156 ovsrcu_set(&before->prev->next, elem);
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'. */
164 rculist_splice_hidden(struct rculist *before, struct rculist *first,
165 struct rculist *last)
166 OVS_NO_THREAD_SAFETY_ANALYSIS
168 struct rculist *last_next;
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);
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);
187 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
190 rculist_push_front(struct rculist *list, struct rculist *elem)
192 rculist_insert(rculist_next_protected(list), elem);
195 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
198 rculist_push_back(struct rculist *list, struct rculist *elem)
200 rculist_insert(list, elem);
203 /* Puts 'element' in the position currently occupied by 'position'.
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). */
211 rculist_replace(struct rculist *element, struct rculist *position)
212 OVS_NO_THREAD_SAFETY_ANALYSIS
214 struct rculist *position_next = rculist_next_protected(position);
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);
222 rculist_poison(position); /* XXX: Some overhead due to ovsrcu_postpone() */
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.
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(). */
233 rculist_move(struct rculist *dst, struct rculist *src)
234 OVS_NO_THREAD_SAFETY_ANALYSIS
236 if (!rculist_is_empty(src)) {
237 struct rculist *src_next = rculist_next_protected(src);
239 dst->prev = src->prev;
240 ovsrcu_set_hidden(&dst->next, src_next);
242 src_next->prev = dst;
243 ovsrcu_set(&src->prev->next, dst);
249 rculist_poison(src); /* XXX: Some overhead due to ovsrcu_postpone() */
253 /* Removes 'elem' from its list and returns the element that followed it.
254 * Has no effect when 'elem' is initialized, but not in a list.
255 * Undefined behavior if 'elem' is not initialized.
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).
263 static inline struct rculist *
264 rculist_remove(struct rculist *elem)
265 OVS_NO_THREAD_SAFETY_ANALYSIS
267 struct rculist *elem_next = rculist_next_protected(elem);
269 elem_next->prev = elem->prev;
270 ovsrcu_set(&elem->prev->next, elem_next);
273 rculist_poison(elem); /* XXX: Some overhead due to ovsrcu_postpone() */
278 /* Removes the front element from 'list' and returns it. Undefined behavior if
279 * 'list' is empty before removal.
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
290 struct rculist *front = rculist_next_protected(list);
291 rculist_remove(front);
295 /* Removes the back element from 'list' and returns it.
296 * Undefined behavior if 'list' is empty before removal.
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
307 struct rculist *back = list->prev;
308 rculist_remove(back);
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)
317 ovs_assert(!rculist_is_empty(list));
319 return rculist_next(list);
322 /* Returns the back element in 'list_'.
323 * Returns the 'list_' itself, if 'list_' is empty. */
324 static inline struct rculist *
325 rculist_back_protected(const struct rculist *list)
326 OVS_NO_THREAD_SAFETY_ANALYSIS
328 return CONST_CAST(struct rculist *, list)->prev;
331 /* Returns the number of elements in 'list'.
332 * Runs in O(n) in the number of elements. */
334 rculist_size(const struct rculist *list)
336 const struct rculist *e;
339 for (e = rculist_next(list); e != list; e = rculist_next(e)) {
345 /* Returns true if 'list' is empty, false otherwise. */
347 rculist_is_empty(const struct rculist *list)
349 return rculist_next(list) == list;
352 /* Returns true if 'list' has 0 or 1 elements, false otherwise. */
354 rculist_is_short_protected(const struct rculist *list)
355 OVS_NO_THREAD_SAFETY_ANALYSIS
357 return rculist_next_protected(list) == list->prev;
360 /* Returns true if 'list' has exactly 1 element, false otherwise. */
362 rculist_is_singleton_protected(const struct rculist *list)
363 OVS_NO_THREAD_SAFETY_ANALYSIS
365 const struct rculist *list_next = rculist_next_protected(list);
367 return list_next == list->prev && list_next != list;
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))
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))
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), \
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), \
401 #endif /* rculist.h */