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 list, with the following exeptions:
31 * - The 'prev' pointer may not be accessed by the user.
32 * - The 'next' pointer should be accessed via rculist_next() by readers, and
33 * rculist_next_protected() by the writer.
34 * - No rculist_moved(): due to the memory management limitation stated above,
35 * rculist instances may not be reallocated, as realloc may instantly free
37 * - rculist_front() returns a const pointer to accommodate for an RCU reader.
38 * - rculist_splice_hidden(): Spliced elements may not have been visible to
39 * RCU readers before the operation.
40 * - rculist_poison(): Immediately poisons the 'prev' pointer, and schedules
41 * ovsrcu_postpone() to poison the 'next' pointer. This issues a memory
42 * write operation to the list element, hopefully crashing the program if
43 * the list node was freed or re-used too early.
45 * The following functions are variations of the struct list functions with
46 * similar names, but are now restricted to the writer use:
48 * - rculist_back_protected()
49 * - rculist_is_short_protected()
50 * - rculist_is_singleton_protected()
58 /* A non-existing mutex to make it more difficult for an user to accidentally
59 * keep using the 'prev' pointer. This may be helpful when porting code from
60 * struct list to rculist. */
61 extern struct ovs_mutex rculist_fake_mutex
;
63 /* Doubly linked list head or element. */
65 /* Previous list element. */
66 struct rculist
*prev
OVS_GUARDED_BY(rculist_fake_mutex
);
68 /* Next list element. */
69 OVSRCU_TYPE(struct rculist
*) next
;
72 /* Easier access to 'next' member. */
73 static inline const struct rculist
*rculist_next(const struct rculist
*);
74 static inline struct rculist
*rculist_next_protected(const struct rculist
*);
76 /* List initialization. */
77 #define RCULIST_INITIALIZER(LIST) { LIST, OVSRCU_INITIALIZER(LIST) }
79 static inline void rculist_init(struct rculist
*list
);
80 static inline void rculist_poison(struct rculist
*elem
);
83 static inline void rculist_insert(struct rculist
*list
, struct rculist
*elem
);
84 static inline void rculist_splice_hidden(struct rculist
*before
,
85 struct rculist
*first
,
86 struct rculist
*last
);
87 static inline void rculist_push_front(struct rculist
*list
,
88 struct rculist
*elem
);
89 static inline void rculist_push_back(struct rculist
*list
,
90 struct rculist
*elem
);
91 static inline void rculist_replace(struct rculist
*replacement
,
92 struct rculist
*replaced
);
93 static inline void rculist_move(struct rculist
*dst
, struct rculist
*src
);
96 static inline struct rculist
*rculist_remove(struct rculist
*elem
);
97 static inline struct rculist
*rculist_pop_front(struct rculist
*list
);
98 static inline struct rculist
*rculist_pop_back(struct rculist
*list
);
101 static inline const struct rculist
*rculist_front(const struct rculist
*);
102 static inline struct rculist
*rculist_back_protected(const struct rculist
*);
104 /* List properties. */
105 static inline size_t rculist_size(const struct rculist
*);
106 static inline bool rculist_is_empty(const struct rculist
*);
107 static inline bool rculist_is_singleton_protected(const struct rculist
*);
108 static inline bool rculist_is_short_protected(const struct rculist
*);
111 /* Inline implementations. */
113 static inline const struct rculist
*
114 rculist_next(const struct rculist
*list
)
116 return ovsrcu_get(struct rculist
*, &list
->next
);
119 static inline struct rculist
*
120 rculist_next_protected(const struct rculist
*list
)
123 return ovsrcu_get_protected(struct rculist
*, &list
->next
);
127 rculist_init(struct rculist
*list
)
128 OVS_NO_THREAD_SAFETY_ANALYSIS
131 ovsrcu_init(&list
->next
, list
);
134 #define RCULIST_POISON (struct rculist *)(UINTPTR_MAX / 0xf * 0xc)
136 void rculist_poison__(struct rculist
*list
);
138 /* Initializes 'list' with pointers that will (probably) cause segfaults if
139 * dereferenced and, better yet, show up clearly in a debugger. */
141 rculist_poison(struct rculist
*list
)
142 OVS_NO_THREAD_SAFETY_ANALYSIS
144 list
->prev
= RCULIST_POISON
;
145 ovsrcu_postpone(rculist_poison__
, list
);
148 /* rculist insertion. */
150 rculist_insert(struct rculist
*before
, struct rculist
*elem
)
151 OVS_NO_THREAD_SAFETY_ANALYSIS
153 elem
->prev
= before
->prev
;
154 ovsrcu_set_hidden(&elem
->next
, before
);
155 ovsrcu_set(&before
->prev
->next
, elem
);
159 /* Removes elements 'first' though 'last' (exclusive) from their current list,
160 * which may NOT be visible to any other threads (== be hidden from them),
161 * then inserts them just before 'before'. */
163 rculist_splice_hidden(struct rculist
*before
, struct rculist
*first
,
164 struct rculist
*last
)
165 OVS_NO_THREAD_SAFETY_ANALYSIS
167 struct rculist
*last_next
;
174 /* Cleanly remove 'first'...'last' from its current list. */
175 last_next
= rculist_next_protected(last
);
176 last_next
->prev
= first
->prev
;
177 ovsrcu_set_hidden(&first
->prev
->next
, last_next
);
179 /* Splice 'first'...'last' into new list. */
180 first
->prev
= before
->prev
;
181 ovsrcu_set(&last
->next
, before
);
182 ovsrcu_set(&before
->prev
->next
, first
);
186 /* Inserts 'elem' at the beginning of 'list', so that it becomes the front in
189 rculist_push_front(struct rculist
*list
, struct rculist
*elem
)
191 rculist_insert(rculist_next_protected(list
), elem
);
194 /* Inserts 'elem' at the end of 'list', so that it becomes the back in
197 rculist_push_back(struct rculist
*list
, struct rculist
*elem
)
199 rculist_insert(list
, elem
);
202 /* Puts 'element' in the position currently occupied by 'position'.
204 * Afterward, 'position' is not linked to from the list any more, but still
205 * links to the nodes in the list, and may still be referenced by other threads
206 * until all other threads quiesce. The replaced node ('position') may not be
207 * re-inserted, re-initialized, or deleted until after all other threads have
208 * quiesced (use ovsrcu_postpone). */
210 rculist_replace(struct rculist
*element
, struct rculist
*position
)
211 OVS_NO_THREAD_SAFETY_ANALYSIS
213 struct rculist
*position_next
= rculist_next_protected(position
);
215 ovsrcu_set_hidden(&element
->next
, position_next
);
216 position_next
->prev
= element
;
217 element
->prev
= position
->prev
;
218 ovsrcu_set(&element
->prev
->next
, element
);
221 rculist_poison(position
); /* XXX: Some overhead due to ovsrcu_postpone() */
225 /* Initializes 'dst' with the contents of 'src', compensating for moving it
226 * around in memory. The effect is that, if 'src' was the head of a list, now
227 * 'dst' is the head of a list containing the same elements.
229 * Memory for 'src' must be kept around until the next RCU quiescent period.
230 * rculist cannot be simply reallocated, so there is no rculist_moved(). */
232 rculist_move(struct rculist
*dst
, struct rculist
*src
)
233 OVS_NO_THREAD_SAFETY_ANALYSIS
235 if (!rculist_is_empty(src
)) {
236 struct rculist
*src_next
= rculist_next_protected(src
);
238 dst
->prev
= src
->prev
;
239 ovsrcu_set_hidden(&dst
->next
, src_next
);
241 src_next
->prev
= dst
;
242 ovsrcu_set(&src
->prev
->next
, dst
);
248 rculist_poison(src
); /* XXX: Some overhead due to ovsrcu_postpone() */
252 /* Removes 'elem' from its list and returns the element that followed it.
253 * Undefined behavior if 'elem' is not in a list.
255 * Afterward, 'elem' is not linked to from the list any more, but still links
256 * to the nodes in the list, and may still be referenced by other threads until
257 * all other threads quiesce. The removed node ('elem') may not be
258 * re-inserted, re-initialized, or deleted until after all other threads have
259 * quiesced (use ovsrcu_postpone).
261 static inline struct rculist
*
262 rculist_remove(struct rculist
*elem
)
263 OVS_NO_THREAD_SAFETY_ANALYSIS
265 struct rculist
*elem_next
= rculist_next_protected(elem
);
267 elem_next
->prev
= elem
->prev
;
268 ovsrcu_set(&elem
->prev
->next
, elem_next
);
271 rculist_poison(elem
); /* XXX: Some overhead due to ovsrcu_postpone() */
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 * Undefined behavior if 'list_' is empty. */
322 static inline struct rculist
*
323 rculist_back_protected(const struct rculist
*list_
)
324 OVS_NO_THREAD_SAFETY_ANALYSIS
326 struct rculist
*list
= CONST_CAST(struct rculist
*, list_
);
328 ovs_assert(!rculist_is_empty(list
));
333 /* Returns the number of elements in 'list'.
334 * Runs in O(n) in the number of elements. */
336 rculist_size(const struct rculist
*list
)
338 const struct rculist
*e
;
341 for (e
= rculist_next(list
); e
!= list
; e
= rculist_next(e
)) {
347 /* Returns true if 'list' is empty, false otherwise. */
349 rculist_is_empty(const struct rculist
*list
)
351 return rculist_next(list
) == list
;
354 /* Returns true if 'list' has 0 or 1 elements, false otherwise. */
356 rculist_is_short_protected(const struct rculist
*list
)
357 OVS_NO_THREAD_SAFETY_ANALYSIS
359 return rculist_next_protected(list
) == list
->prev
;
362 /* Returns true if 'list' has exactly 1 element, false otherwise. */
364 rculist_is_singleton_protected(const struct rculist
*list
)
365 OVS_NO_THREAD_SAFETY_ANALYSIS
367 const struct rculist
*list_next
= rculist_next_protected(list
);
369 return list_next
== list
->prev
&& list_next
!= list
;
372 #define RCULIST_FOR_EACH(ITER, MEMBER, RCULIST) \
373 for (INIT_CONTAINER(ITER, rculist_next(RCULIST), MEMBER); \
374 &(ITER)->MEMBER != (RCULIST); \
375 ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
376 #define RCULIST_FOR_EACH_CONTINUE(ITER, MEMBER, RCULIST) \
377 for (ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER); \
378 &(ITER)->MEMBER != (RCULIST); \
379 ASSIGN_CONTAINER(ITER, rculist_next(&(ITER)->MEMBER), MEMBER))
381 #define RCULIST_FOR_EACH_REVERSE_PROTECTED(ITER, MEMBER, RCULIST) \
382 for (INIT_CONTAINER(ITER, (RCULIST)->prev, MEMBER); \
383 &(ITER)->MEMBER != (RCULIST); \
384 ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
385 #define RCULIST_FOR_EACH_REVERSE_PROTECTED_CONTINUE(ITER, MEMBER, RCULIST) \
386 for (ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER); \
387 &(ITER)->MEMBER != (RCULIST); \
388 ASSIGN_CONTAINER(ITER, (ITER)->MEMBER.prev, MEMBER))
390 #define RCULIST_FOR_EACH_PROTECTED(ITER, MEMBER, RCULIST) \
391 for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
392 &(ITER)->MEMBER != (RCULIST); \
393 ASSIGN_CONTAINER(ITER, rculist_next_protected(&(ITER)->MEMBER), \
396 #define RCULIST_FOR_EACH_SAFE_PROTECTED(ITER, NEXT, MEMBER, RCULIST) \
397 for (INIT_CONTAINER(ITER, rculist_next_protected(RCULIST), MEMBER); \
398 (&(ITER)->MEMBER != (RCULIST) \
399 ? INIT_CONTAINER(NEXT, rculist_next_protected(&(ITER)->MEMBER), \
403 #endif /* rculist.h */