blob: 2dea94fc44026a1048f912913be298b8df179873 [file] [log] [blame]
Franck Bui-Huu82524742008-05-12 21:21:05 +02001#ifndef _LINUX_RCULIST_H
2#define _LINUX_RCULIST_H
3
4#ifdef __KERNEL__
5
6/*
7 * RCU-protected list version
8 */
9#include <linux/list.h>
Franck Bui-Huu10aa9d22008-05-12 21:21:06 +020010#include <linux/rcupdate.h>
Franck Bui-Huu82524742008-05-12 21:21:05 +020011
12/*
Paul E. McKenney65e6bf42010-08-19 21:43:09 -070013 * Why is there no list_empty_rcu()? Because list_empty() serves this
14 * purpose. The list_empty() function fetches the RCU-protected pointer
15 * and compares it to the address of the list head, but neither dereferences
16 * this pointer itself nor provides this pointer to the caller. Therefore,
17 * it is not necessary to use rcu_dereference(), so that list_empty() can
18 * be used anywhere you would want to use a list_empty_rcu().
19 */
20
21/*
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010022 * return the ->next pointer of a list_head in an rcu safe
23 * way, we must not access it directly
24 */
25#define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
26
27/*
Franck Bui-Huu82524742008-05-12 21:21:05 +020028 * Insert a new entry between two known consecutive entries.
29 *
30 * This is only for internal list manipulation where we know
31 * the prev/next entries already!
32 */
33static inline void __list_add_rcu(struct list_head *new,
34 struct list_head *prev, struct list_head *next)
35{
36 new->next = next;
37 new->prev = prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010038 rcu_assign_pointer(list_next_rcu(prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +020039 next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +020040}
41
42/**
43 * list_add_rcu - add a new entry to rcu-protected list
44 * @new: new entry to be added
45 * @head: list head to add it after
46 *
47 * Insert a new entry after the specified head.
48 * This is good for implementing stacks.
49 *
50 * The caller must take whatever precautions are necessary
51 * (such as holding appropriate locks) to avoid racing
52 * with another list-mutation primitive, such as list_add_rcu()
53 * or list_del_rcu(), running on this same list.
54 * However, it is perfectly legal to run concurrently with
55 * the _rcu list-traversal primitives, such as
56 * list_for_each_entry_rcu().
57 */
58static inline void list_add_rcu(struct list_head *new, struct list_head *head)
59{
60 __list_add_rcu(new, head, head->next);
61}
62
63/**
64 * list_add_tail_rcu - add a new entry to rcu-protected list
65 * @new: new entry to be added
66 * @head: list head to add it before
67 *
68 * Insert a new entry before the specified head.
69 * This is useful for implementing queues.
70 *
71 * The caller must take whatever precautions are necessary
72 * (such as holding appropriate locks) to avoid racing
73 * with another list-mutation primitive, such as list_add_tail_rcu()
74 * or list_del_rcu(), running on this same list.
75 * However, it is perfectly legal to run concurrently with
76 * the _rcu list-traversal primitives, such as
77 * list_for_each_entry_rcu().
78 */
79static inline void list_add_tail_rcu(struct list_head *new,
80 struct list_head *head)
81{
82 __list_add_rcu(new, head->prev, head);
83}
84
85/**
86 * list_del_rcu - deletes entry from list without re-initialization
87 * @entry: the element to delete from the list.
88 *
89 * Note: list_empty() on entry does not return true after this,
90 * the entry is in an undefined state. It is useful for RCU based
91 * lockfree traversal.
92 *
93 * In particular, it means that we can not poison the forward
94 * pointers that may still be used for walking the list.
95 *
96 * The caller must take whatever precautions are necessary
97 * (such as holding appropriate locks) to avoid racing
98 * with another list-mutation primitive, such as list_del_rcu()
99 * or list_add_rcu(), running on this same list.
100 * However, it is perfectly legal to run concurrently with
101 * the _rcu list-traversal primitives, such as
102 * list_for_each_entry_rcu().
103 *
104 * Note that the caller is not permitted to immediately free
105 * the newly deleted entry. Instead, either synchronize_rcu()
106 * or call_rcu() must be used to defer freeing until an RCU
107 * grace period has elapsed.
108 */
109static inline void list_del_rcu(struct list_head *entry)
110{
111 __list_del(entry->prev, entry->next);
112 entry->prev = LIST_POISON2;
113}
114
115/**
Andrea Arcangeli6beeac72008-07-28 15:46:22 -0700116 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
117 * @n: the element to delete from the hash list.
118 *
119 * Note: list_unhashed() on the node return true after this. It is
120 * useful for RCU based read lockfree traversal if the writer side
121 * must know if the list entry is still hashed or already unhashed.
122 *
123 * In particular, it means that we can not poison the forward pointers
124 * that may still be used for walking the hash list and we can only
125 * zero the pprev pointer so list_unhashed() will return true after
126 * this.
127 *
128 * The caller must take whatever precautions are necessary (such as
129 * holding appropriate locks) to avoid racing with another
130 * list-mutation primitive, such as hlist_add_head_rcu() or
131 * hlist_del_rcu(), running on this same list. However, it is
132 * perfectly legal to run concurrently with the _rcu list-traversal
133 * primitives, such as hlist_for_each_entry_rcu().
134 */
135static inline void hlist_del_init_rcu(struct hlist_node *n)
136{
137 if (!hlist_unhashed(n)) {
138 __hlist_del(n);
139 n->pprev = NULL;
140 }
141}
142
143/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200144 * list_replace_rcu - replace old entry by new one
145 * @old : the element to be replaced
146 * @new : the new element to insert
147 *
148 * The @old entry will be replaced with the @new entry atomically.
149 * Note: @old should not be empty.
150 */
151static inline void list_replace_rcu(struct list_head *old,
152 struct list_head *new)
153{
154 new->next = old->next;
155 new->prev = old->prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100156 rcu_assign_pointer(list_next_rcu(new->prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200157 new->next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200158 old->prev = LIST_POISON2;
159}
160
161/**
162 * list_splice_init_rcu - splice an RCU-protected list into an existing list.
163 * @list: the RCU-protected list to splice
164 * @head: the place in the list to splice the first list into
165 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
166 *
167 * @head can be RCU-read traversed concurrently with this function.
168 *
169 * Note that this function blocks.
170 *
171 * Important note: the caller must take whatever action is necessary to
172 * prevent any other updates to @head. In principle, it is possible
173 * to modify the list as soon as sync() begins execution.
174 * If this sort of thing becomes necessary, an alternative version
175 * based on call_rcu() could be created. But only if -really-
176 * needed -- there is no shortage of RCU API members.
177 */
178static inline void list_splice_init_rcu(struct list_head *list,
179 struct list_head *head,
180 void (*sync)(void))
181{
182 struct list_head *first = list->next;
183 struct list_head *last = list->prev;
184 struct list_head *at = head->next;
185
186 if (list_empty(head))
187 return;
188
189 /* "first" and "last" tracking list, so initialize it. */
190
191 INIT_LIST_HEAD(list);
192
193 /*
194 * At this point, the list body still points to the source list.
195 * Wait for any readers to finish using the list before splicing
196 * the list body into the new list. Any new readers will see
197 * an empty list.
198 */
199
200 sync();
201
202 /*
203 * Readers are finished with the source list, so perform splice.
204 * The order is important if the new list is global and accessible
205 * to concurrent RCU readers. Note that RCU readers are not
206 * permitted to traverse the prev pointers without excluding
207 * this function.
208 */
209
210 last->next = at;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100211 rcu_assign_pointer(list_next_rcu(head), first);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200212 first->prev = head;
213 at->prev = last;
214}
215
Jiri Pirko72c6a982009-04-14 17:33:57 +0200216/**
217 * list_entry_rcu - get the struct for this entry
218 * @ptr: the &struct list_head pointer.
219 * @type: the type of the struct this is embedded in.
220 * @member: the name of the list_struct within the struct.
221 *
222 * This primitive may safely run concurrently with the _rcu list-mutation
223 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
224 */
225#define list_entry_rcu(ptr, type, member) \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100226 ({typeof (*ptr) __rcu *__ptr = (typeof (*ptr) __rcu __force *)ptr; \
227 container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
228 })
Jiri Pirko72c6a982009-04-14 17:33:57 +0200229
230/**
231 * list_first_entry_rcu - get the first element from a list
232 * @ptr: the list head to take the element from.
233 * @type: the type of the struct this is embedded in.
234 * @member: the name of the list_struct within the struct.
235 *
236 * Note, that list is expected to be not empty.
237 *
238 * This primitive may safely run concurrently with the _rcu list-mutation
239 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
240 */
241#define list_first_entry_rcu(ptr, type, member) \
242 list_entry_rcu((ptr)->next, type, member)
243
Franck Bui-Huu82524742008-05-12 21:21:05 +0200244/**
245 * list_for_each_entry_rcu - iterate over rcu list of given type
246 * @pos: the type * to use as a loop cursor.
247 * @head: the head for your list.
248 * @member: the name of the list_struct within the struct.
249 *
250 * This list-traversal primitive may safely run concurrently with
251 * the _rcu list-mutation primitives such as list_add_rcu()
252 * as long as the traversal is guarded by rcu_read_lock().
253 */
254#define list_for_each_entry_rcu(pos, head, member) \
Jiri Pirko72c6a982009-04-14 17:33:57 +0200255 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
Paul E. McKenney78b0e0e2008-05-12 21:21:06 +0200256 prefetch(pos->member.next), &pos->member != (head); \
Jiri Pirko72c6a982009-04-14 17:33:57 +0200257 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200258
259
260/**
261 * list_for_each_continue_rcu
262 * @pos: the &struct list_head to use as a loop cursor.
263 * @head: the head for your list.
264 *
265 * Iterate over an rcu-protected list, continuing after current point.
266 *
267 * This list-traversal primitive may safely run concurrently with
268 * the _rcu list-mutation primitives such as list_add_rcu()
269 * as long as the traversal is guarded by rcu_read_lock().
270 */
271#define list_for_each_continue_rcu(pos, head) \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100272 for ((pos) = rcu_dereference_raw(list_next_rcu(pos)); \
Paul E. McKenney78b0e0e2008-05-12 21:21:06 +0200273 prefetch((pos)->next), (pos) != (head); \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100274 (pos) = rcu_dereference_raw(list_next_rcu(pos)))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200275
276/**
stephen hemminger254245d2009-11-10 07:54:47 +0000277 * list_for_each_entry_continue_rcu - continue iteration over list of given type
278 * @pos: the type * to use as a loop cursor.
279 * @head: the head for your list.
280 * @member: the name of the list_struct within the struct.
281 *
282 * Continue to iterate over list of given type, continuing after
283 * the current position.
284 */
285#define list_for_each_entry_continue_rcu(pos, head, member) \
286 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
287 prefetch(pos->member.next), &pos->member != (head); \
288 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
289
290/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200291 * hlist_del_rcu - deletes entry from hash list without re-initialization
292 * @n: the element to delete from the hash list.
293 *
294 * Note: list_unhashed() on entry does not return true after this,
295 * the entry is in an undefined state. It is useful for RCU based
296 * lockfree traversal.
297 *
298 * In particular, it means that we can not poison the forward
299 * pointers that may still be used for walking the hash list.
300 *
301 * The caller must take whatever precautions are necessary
302 * (such as holding appropriate locks) to avoid racing
303 * with another list-mutation primitive, such as hlist_add_head_rcu()
304 * or hlist_del_rcu(), running on this same list.
305 * However, it is perfectly legal to run concurrently with
306 * the _rcu list-traversal primitives, such as
307 * hlist_for_each_entry().
308 */
309static inline void hlist_del_rcu(struct hlist_node *n)
310{
311 __hlist_del(n);
312 n->pprev = LIST_POISON2;
313}
314
315/**
316 * hlist_replace_rcu - replace old entry by new one
317 * @old : the element to be replaced
318 * @new : the new element to insert
319 *
320 * The @old entry will be replaced with the @new entry atomically.
321 */
322static inline void hlist_replace_rcu(struct hlist_node *old,
323 struct hlist_node *new)
324{
325 struct hlist_node *next = old->next;
326
327 new->next = next;
328 new->pprev = old->pprev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100329 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200330 if (next)
331 new->next->pprev = &new->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200332 old->pprev = LIST_POISON2;
333}
334
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100335/*
336 * return the first or the next element in an RCU protected hlist
337 */
338#define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
339#define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
340#define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
341
Franck Bui-Huu82524742008-05-12 21:21:05 +0200342/**
343 * hlist_add_head_rcu
344 * @n: the element to add to the hash list.
345 * @h: the list to add to.
346 *
347 * Description:
348 * Adds the specified element to the specified hlist,
349 * while permitting racing traversals.
350 *
351 * The caller must take whatever precautions are necessary
352 * (such as holding appropriate locks) to avoid racing
353 * with another list-mutation primitive, such as hlist_add_head_rcu()
354 * or hlist_del_rcu(), running on this same list.
355 * However, it is perfectly legal to run concurrently with
356 * the _rcu list-traversal primitives, such as
357 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
358 * problems on Alpha CPUs. Regardless of the type of CPU, the
359 * list-traversal primitive must be guarded by rcu_read_lock().
360 */
361static inline void hlist_add_head_rcu(struct hlist_node *n,
362 struct hlist_head *h)
363{
364 struct hlist_node *first = h->first;
Franck Bui-Huu10aa9d22008-05-12 21:21:06 +0200365
Franck Bui-Huu82524742008-05-12 21:21:05 +0200366 n->next = first;
367 n->pprev = &h->first;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100368 rcu_assign_pointer(hlist_first_rcu(h), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200369 if (first)
370 first->pprev = &n->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200371}
372
373/**
374 * hlist_add_before_rcu
375 * @n: the new element to add to the hash list.
376 * @next: the existing element to add the new element before.
377 *
378 * Description:
379 * Adds the specified element to the specified hlist
380 * before the specified node while permitting racing traversals.
381 *
382 * The caller must take whatever precautions are necessary
383 * (such as holding appropriate locks) to avoid racing
384 * with another list-mutation primitive, such as hlist_add_head_rcu()
385 * or hlist_del_rcu(), running on this same list.
386 * However, it is perfectly legal to run concurrently with
387 * the _rcu list-traversal primitives, such as
388 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
389 * problems on Alpha CPUs.
390 */
391static inline void hlist_add_before_rcu(struct hlist_node *n,
392 struct hlist_node *next)
393{
394 n->pprev = next->pprev;
395 n->next = next;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100396 rcu_assign_pointer(hlist_pprev_rcu(n), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200397 next->pprev = &n->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200398}
399
400/**
401 * hlist_add_after_rcu
402 * @prev: the existing element to add the new element after.
403 * @n: the new element to add to the hash list.
404 *
405 * Description:
406 * Adds the specified element to the specified hlist
407 * after the specified node while permitting racing traversals.
408 *
409 * The caller must take whatever precautions are necessary
410 * (such as holding appropriate locks) to avoid racing
411 * with another list-mutation primitive, such as hlist_add_head_rcu()
412 * or hlist_del_rcu(), running on this same list.
413 * However, it is perfectly legal to run concurrently with
414 * the _rcu list-traversal primitives, such as
415 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
416 * problems on Alpha CPUs.
417 */
418static inline void hlist_add_after_rcu(struct hlist_node *prev,
419 struct hlist_node *n)
420{
421 n->next = prev->next;
422 n->pprev = &prev->next;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100423 rcu_assign_pointer(hlist_next_rcu(prev), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200424 if (n->next)
425 n->next->pprev = &n->next;
426}
427
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100428#define __hlist_for_each_rcu(pos, head) \
429 for (pos = rcu_dereference(hlist_first_rcu(head)); \
430 pos && ({ prefetch(pos->next); 1; }); \
431 pos = rcu_dereference(hlist_next_rcu(pos)))
stephen hemminger1cc52322010-02-22 07:57:17 +0000432
Franck Bui-Huu82524742008-05-12 21:21:05 +0200433/**
434 * hlist_for_each_entry_rcu - iterate over rcu list of given type
435 * @tpos: the type * to use as a loop cursor.
436 * @pos: the &struct hlist_node to use as a loop cursor.
437 * @head: the head for your list.
438 * @member: the name of the hlist_node within the struct.
439 *
440 * This list-traversal primitive may safely run concurrently with
441 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
442 * as long as the traversal is guarded by rcu_read_lock().
443 */
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100444#define hlist_for_each_entry_rcu(tpos, pos, head, member) \
445 for (pos = rcu_dereference_raw(hlist_first_rcu(head)); \
Paul E. McKenney78b0e0e2008-05-12 21:21:06 +0200446 pos && ({ prefetch(pos->next); 1; }) && \
Franck Bui-Huu82524742008-05-12 21:21:05 +0200447 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100448 pos = rcu_dereference_raw(hlist_next_rcu(pos)))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200449
stephen hemminger5c578ae2010-03-17 20:31:11 +0000450/**
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000451 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
452 * @tpos: the type * to use as a loop cursor.
453 * @pos: the &struct hlist_node to use as a loop cursor.
454 * @head: the head for your list.
455 * @member: the name of the hlist_node within the struct.
456 *
457 * This list-traversal primitive may safely run concurrently with
458 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
459 * as long as the traversal is guarded by rcu_read_lock().
460 */
461#define hlist_for_each_entry_rcu_bh(tpos, pos, head, member) \
462 for (pos = rcu_dereference_bh((head)->first); \
463 pos && ({ prefetch(pos->next); 1; }) && \
464 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
465 pos = rcu_dereference_bh(pos->next))
466
467/**
stephen hemminger5c578ae2010-03-17 20:31:11 +0000468 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
469 * @tpos: the type * to use as a loop cursor.
470 * @pos: the &struct hlist_node to use as a loop cursor.
471 * @member: the name of the hlist_node within the struct.
472 */
473#define hlist_for_each_entry_continue_rcu(tpos, pos, member) \
474 for (pos = rcu_dereference((pos)->next); \
475 pos && ({ prefetch(pos->next); 1; }) && \
476 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
477 pos = rcu_dereference(pos->next))
478
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000479/**
480 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
481 * @tpos: the type * to use as a loop cursor.
482 * @pos: the &struct hlist_node to use as a loop cursor.
483 * @member: the name of the hlist_node within the struct.
484 */
485#define hlist_for_each_entry_continue_rcu_bh(tpos, pos, member) \
486 for (pos = rcu_dereference_bh((pos)->next); \
487 pos && ({ prefetch(pos->next); 1; }) && \
488 ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; }); \
489 pos = rcu_dereference_bh(pos->next))
490
stephen hemminger5c578ae2010-03-17 20:31:11 +0000491
Franck Bui-Huu82524742008-05-12 21:21:05 +0200492#endif /* __KERNEL__ */
493#endif