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 */