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(): Only poisons the 'prev' pointer.
43 * The following functions are variations of the struct ovs_list functions with
44 * similar names, but are now restricted to the writer use:
46 * - rculist_back_protected()
47 * - rculist_is_short_protected()
48 * - rculist_is_singleton_protected()
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;
61 /* Doubly linked list head or element. */
63 /* Previous list element. */
64 struct rculist *prev OVS_GUARDED_BY(rculist_fake_mutex);
66 /* Next list element. */
67 OVSRCU_TYPE(struct rculist *) next;
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 *);
74 /* List initialization. */
75 #define RCUOVS_LIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) }
77 static inline void rculist_init(struct rculist *list);
78 static inline void rculist_poison(struct rculist *elem);
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);
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);
99 static inline const struct rculist *rculist_front(const struct rculist *);
100 static inline struct rculist *rculist_back_protected(const struct rculist *);
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 *);
109 /* Inline implementations. */
111 static inline const struct rculist *
112 rculist_next(const struct rculist *list)
114 return ovsrcu_get(struct rculist *, &list->next);
117 static inline struct rculist *
118 rculist_next_protected(const struct rculist *list)
121 return ovsrcu_get_protected(struct rculist *, &list->next);
125 rculist_init(struct rculist *list)
126 OVS_NO_THREAD_SAFETY_ANALYSIS
129 ovsrcu_init(&list->next, list);
132 #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc)
134 /* Initializes 'list' with pointers that will (probably) cause segfaults if
135 * dereferenced and, better yet, show up clearly in a debugger. */
137 rculist_poison(struct rculist *list)
138 OVS_NO_THREAD_SAFETY_ANALYSIS
140 list->prev = RCULIST_POISON;
143 /* Initializes 'list' with pointers that will (probably) cause segfaults if
144 * dereferenced and, better yet, show up clearly in a debugger.
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. */
149 rculist_poison__(struct rculist *list)
150 OVS_NO_THREAD_SAFETY_ANALYSIS
152 rculist_poison(list);
153 ovsrcu_set_hidden(&list->next, RCULIST_POISON);
156 /* rculist insertion. */
158 rculist_insert(struct rculist *before, struct rculist *elem)
159 OVS_NO_THREAD_SAFETY_ANALYSIS
161 elem->prev = before->prev;
162 ovsrcu_set_hidden(&elem->next, before);
163 ovsrcu_set(&before->prev->next, elem);
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'. */
171 rculist_splice_hidden(struct rculist *before, struct rculist *first,
172 struct rculist *last)
173 OVS_NO_THREAD_SAFETY_ANALYSIS
175 struct rculist *last_next;
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);
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);
194 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
197 rculist_push_front(struct rculist *list, struct rculist *elem)
199 rculist_insert(rculist_next_protected(list), elem);
202 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
205 rculist_push_back(struct rculist *list, struct rculist *elem)
207 rculist_insert(list, elem);
210 /* Puts 'element' in the position currently occupied by 'position'.
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). */
218 rculist_replace(struct rculist *element, struct rculist *position)
219 OVS_NO_THREAD_SAFETY_ANALYSIS
221 struct rculist *position_next = rculist_next_protected(position);
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);
227 rculist_poison(position);
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.
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(). */
237 rculist_move(struct rculist *dst, struct rculist *src)
238 OVS_NO_THREAD_SAFETY_ANALYSIS
240 if (!rculist_is_empty(src)) {
241 struct rculist *src_next = rculist_next_protected(src);
243 dst->prev = src->prev;
244 ovsrcu_set_hidden(&dst->next, src_next);
246 src_next->prev = dst;
247 ovsrcu_set(&src->prev->next, dst);
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.
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).
264 static inline struct rculist *
265 rculist_remove(struct rculist *elem)
266 OVS_NO_THREAD_SAFETY_ANALYSIS
268 struct rculist *elem_next = rculist_next_protected(elem);
270 elem_next->prev = elem->prev;
271 ovsrcu_set(&elem->prev->next, elem_next);
272 rculist_poison(elem);
276 /* Removes the front element from 'list' and returns it. Undefined behavior if
277 * 'list' is empty before removal.
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
288 struct rculist *front = rculist_next_protected(list);
289 rculist_remove(front);
293 /* Removes the back element from 'list' and returns it.
294 * Undefined behavior if 'list' is empty before removal.
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
305 struct rculist *back = list->prev;
306 rculist_remove(back);
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)
315 ovs_assert(!rculist_is_empty(list));
317 return rculist_next(list);
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
326 return CONST_CAST(struct rculist *, list)->prev;
329 /* Returns the number of elements in 'list'.
330 * Runs in O(n) in the number of elements. */
332 rculist_size(const struct rculist *list)
334 const struct rculist *e;
337 for (e = rculist_next(list); e != list; e = rculist_next(e)) {
343 /* Returns true if 'list' is empty, false otherwise. */
345 rculist_is_empty(const struct rculist *list)
347 return rculist_next(list) == list;
350 /* Returns true if 'list' has 0 or 1 elements, false otherwise. */
352 rculist_is_short_protected(const struct rculist *list)
353 OVS_NO_THREAD_SAFETY_ANALYSIS
355 return rculist_next_protected(list) == list->prev;
358 /* Returns true if 'list' has exactly 1 element, false otherwise. */
360 rculist_is_singleton_protected(const struct rculist *list)
361 OVS_NO_THREAD_SAFETY_ANALYSIS
363 const struct rculist *list_next = rculist_next_protected(list);
365 return list_next == list->prev && list_next != list;
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))
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))
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), \
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), \
399 #endif /* rculist.h */