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 */
added
removed
lib/rculist.h
