blob: 8089e35d47aca865b660d7aca94ad01a59111652 [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 */
Dave Jones559f9ba2012-03-14 22:17:39 -040033#ifndef CONFIG_DEBUG_LIST
Franck Bui-Huu82524742008-05-12 21:21:05 +020034static inline void __list_add_rcu(struct list_head *new,
35 struct list_head *prev, struct list_head *next)
36{
37 new->next = next;
38 new->prev = prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010039 rcu_assign_pointer(list_next_rcu(prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +020040 next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +020041}
Dave Jones559f9ba2012-03-14 22:17:39 -040042#else
43extern void __list_add_rcu(struct list_head *new,
44 struct list_head *prev, struct list_head *next);
45#endif
Franck Bui-Huu82524742008-05-12 21:21:05 +020046
47/**
48 * list_add_rcu - add a new entry to rcu-protected list
49 * @new: new entry to be added
50 * @head: list head to add it after
51 *
52 * Insert a new entry after the specified head.
53 * This is good for implementing stacks.
54 *
55 * The caller must take whatever precautions are necessary
56 * (such as holding appropriate locks) to avoid racing
57 * with another list-mutation primitive, such as list_add_rcu()
58 * or list_del_rcu(), running on this same list.
59 * However, it is perfectly legal to run concurrently with
60 * the _rcu list-traversal primitives, such as
61 * list_for_each_entry_rcu().
62 */
63static inline void list_add_rcu(struct list_head *new, struct list_head *head)
64{
65 __list_add_rcu(new, head, head->next);
66}
67
68/**
69 * list_add_tail_rcu - add a new entry to rcu-protected list
70 * @new: new entry to be added
71 * @head: list head to add it before
72 *
73 * Insert a new entry before the specified head.
74 * This is useful for implementing queues.
75 *
76 * The caller must take whatever precautions are necessary
77 * (such as holding appropriate locks) to avoid racing
78 * with another list-mutation primitive, such as list_add_tail_rcu()
79 * or list_del_rcu(), running on this same list.
80 * However, it is perfectly legal to run concurrently with
81 * the _rcu list-traversal primitives, such as
82 * list_for_each_entry_rcu().
83 */
84static inline void list_add_tail_rcu(struct list_head *new,
85 struct list_head *head)
86{
87 __list_add_rcu(new, head->prev, head);
88}
89
90/**
91 * list_del_rcu - deletes entry from list without re-initialization
92 * @entry: the element to delete from the list.
93 *
94 * Note: list_empty() on entry does not return true after this,
95 * the entry is in an undefined state. It is useful for RCU based
96 * lockfree traversal.
97 *
98 * In particular, it means that we can not poison the forward
99 * pointers that may still be used for walking the list.
100 *
101 * The caller must take whatever precautions are necessary
102 * (such as holding appropriate locks) to avoid racing
103 * with another list-mutation primitive, such as list_del_rcu()
104 * or list_add_rcu(), running on this same list.
105 * However, it is perfectly legal to run concurrently with
106 * the _rcu list-traversal primitives, such as
107 * list_for_each_entry_rcu().
108 *
109 * Note that the caller is not permitted to immediately free
110 * the newly deleted entry. Instead, either synchronize_rcu()
111 * or call_rcu() must be used to defer freeing until an RCU
112 * grace period has elapsed.
113 */
114static inline void list_del_rcu(struct list_head *entry)
115{
Dave Jones559f9ba2012-03-14 22:17:39 -0400116 __list_del_entry(entry);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200117 entry->prev = LIST_POISON2;
118}
119
120/**
Andrea Arcangeli6beeac72008-07-28 15:46:22 -0700121 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
122 * @n: the element to delete from the hash list.
123 *
124 * Note: list_unhashed() on the node return true after this. It is
125 * useful for RCU based read lockfree traversal if the writer side
126 * must know if the list entry is still hashed or already unhashed.
127 *
128 * In particular, it means that we can not poison the forward pointers
129 * that may still be used for walking the hash list and we can only
130 * zero the pprev pointer so list_unhashed() will return true after
131 * this.
132 *
133 * The caller must take whatever precautions are necessary (such as
134 * holding appropriate locks) to avoid racing with another
135 * list-mutation primitive, such as hlist_add_head_rcu() or
136 * hlist_del_rcu(), running on this same list. However, it is
137 * perfectly legal to run concurrently with the _rcu list-traversal
138 * primitives, such as hlist_for_each_entry_rcu().
139 */
140static inline void hlist_del_init_rcu(struct hlist_node *n)
141{
142 if (!hlist_unhashed(n)) {
143 __hlist_del(n);
144 n->pprev = NULL;
145 }
146}
147
148/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200149 * list_replace_rcu - replace old entry by new one
150 * @old : the element to be replaced
151 * @new : the new element to insert
152 *
153 * The @old entry will be replaced with the @new entry atomically.
154 * Note: @old should not be empty.
155 */
156static inline void list_replace_rcu(struct list_head *old,
157 struct list_head *new)
158{
159 new->next = old->next;
160 new->prev = old->prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100161 rcu_assign_pointer(list_next_rcu(new->prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200162 new->next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200163 old->prev = LIST_POISON2;
164}
165
166/**
167 * list_splice_init_rcu - splice an RCU-protected list into an existing list.
168 * @list: the RCU-protected list to splice
169 * @head: the place in the list to splice the first list into
170 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
171 *
172 * @head can be RCU-read traversed concurrently with this function.
173 *
174 * Note that this function blocks.
175 *
176 * Important note: the caller must take whatever action is necessary to
177 * prevent any other updates to @head. In principle, it is possible
178 * to modify the list as soon as sync() begins execution.
179 * If this sort of thing becomes necessary, an alternative version
180 * based on call_rcu() could be created. But only if -really-
181 * needed -- there is no shortage of RCU API members.
182 */
183static inline void list_splice_init_rcu(struct list_head *list,
184 struct list_head *head,
185 void (*sync)(void))
186{
187 struct list_head *first = list->next;
188 struct list_head *last = list->prev;
189 struct list_head *at = head->next;
190
Jan H. Schönherr7f708932011-07-19 21:10:26 +0200191 if (list_empty(list))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200192 return;
193
194 /* "first" and "last" tracking list, so initialize it. */
195
196 INIT_LIST_HEAD(list);
197
198 /*
199 * At this point, the list body still points to the source list.
200 * Wait for any readers to finish using the list before splicing
201 * the list body into the new list. Any new readers will see
202 * an empty list.
203 */
204
205 sync();
206
207 /*
208 * Readers are finished with the source list, so perform splice.
209 * The order is important if the new list is global and accessible
210 * to concurrent RCU readers. Note that RCU readers are not
211 * permitted to traverse the prev pointers without excluding
212 * this function.
213 */
214
215 last->next = at;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100216 rcu_assign_pointer(list_next_rcu(head), first);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200217 first->prev = head;
218 at->prev = last;
219}
220
Jiri Pirko72c6a982009-04-14 17:33:57 +0200221/**
222 * list_entry_rcu - get the struct for this entry
223 * @ptr: the &struct list_head pointer.
224 * @type: the type of the struct this is embedded in.
225 * @member: the name of the list_struct within the struct.
226 *
227 * This primitive may safely run concurrently with the _rcu list-mutation
228 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
229 */
230#define list_entry_rcu(ptr, type, member) \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100231 ({typeof (*ptr) __rcu *__ptr = (typeof (*ptr) __rcu __force *)ptr; \
232 container_of((typeof(ptr))rcu_dereference_raw(__ptr), type, member); \
233 })
Jiri Pirko72c6a982009-04-14 17:33:57 +0200234
235/**
Michel Machadof88022a2012-04-10 14:07:40 -0400236 * Where are list_empty_rcu() and list_first_entry_rcu()?
237 *
238 * Implementing those functions following their counterparts list_empty() and
239 * list_first_entry() is not advisable because they lead to subtle race
240 * conditions as the following snippet shows:
241 *
242 * if (!list_empty_rcu(mylist)) {
243 * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
244 * do_something(bar);
245 * }
246 *
247 * The list may not be empty when list_empty_rcu checks it, but it may be when
248 * list_first_entry_rcu rereads the ->next pointer.
249 *
250 * Rereading the ->next pointer is not a problem for list_empty() and
251 * list_first_entry() because they would be protected by a lock that blocks
252 * writers.
253 *
254 * See list_first_or_null_rcu for an alternative.
255 */
256
257/**
258 * list_first_or_null_rcu - get the first element from a list
Jiri Pirko72c6a982009-04-14 17:33:57 +0200259 * @ptr: the list head to take the element from.
260 * @type: the type of the struct this is embedded in.
261 * @member: the name of the list_struct within the struct.
262 *
Michel Machadof88022a2012-04-10 14:07:40 -0400263 * Note that if the list is empty, it returns NULL.
Jiri Pirko72c6a982009-04-14 17:33:57 +0200264 *
265 * This primitive may safely run concurrently with the _rcu list-mutation
266 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
267 */
Michel Machadof88022a2012-04-10 14:07:40 -0400268#define list_first_or_null_rcu(ptr, type, member) \
269 ({struct list_head *__ptr = (ptr); \
270 struct list_head __rcu *__next = list_next_rcu(__ptr); \
271 likely(__ptr != __next) ? container_of(__next, type, member) : NULL; \
272 })
Jiri Pirko72c6a982009-04-14 17:33:57 +0200273
Franck Bui-Huu82524742008-05-12 21:21:05 +0200274/**
275 * list_for_each_entry_rcu - iterate over rcu list of given type
276 * @pos: the type * to use as a loop cursor.
277 * @head: the head for your list.
278 * @member: the name of the list_struct within the struct.
279 *
280 * This list-traversal primitive may safely run concurrently with
281 * the _rcu list-mutation primitives such as list_add_rcu()
282 * as long as the traversal is guarded by rcu_read_lock().
283 */
284#define list_for_each_entry_rcu(pos, head, member) \
Jiri Pirko72c6a982009-04-14 17:33:57 +0200285 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
Linus Torvaldse66eed62011-05-19 14:15:29 -0700286 &pos->member != (head); \
Jiri Pirko72c6a982009-04-14 17:33:57 +0200287 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200288
Franck Bui-Huu82524742008-05-12 21:21:05 +0200289/**
stephen hemminger254245d2009-11-10 07:54:47 +0000290 * list_for_each_entry_continue_rcu - continue iteration over list of given type
291 * @pos: the type * to use as a loop cursor.
292 * @head: the head for your list.
293 * @member: the name of the list_struct within the struct.
294 *
295 * Continue to iterate over list of given type, continuing after
296 * the current position.
297 */
298#define list_for_each_entry_continue_rcu(pos, head, member) \
299 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
Linus Torvaldse66eed62011-05-19 14:15:29 -0700300 &pos->member != (head); \
stephen hemminger254245d2009-11-10 07:54:47 +0000301 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
302
303/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200304 * hlist_del_rcu - deletes entry from hash list without re-initialization
305 * @n: the element to delete from the hash list.
306 *
307 * Note: list_unhashed() on entry does not return true after this,
308 * the entry is in an undefined state. It is useful for RCU based
309 * lockfree traversal.
310 *
311 * In particular, it means that we can not poison the forward
312 * pointers that may still be used for walking the hash list.
313 *
314 * The caller must take whatever precautions are necessary
315 * (such as holding appropriate locks) to avoid racing
316 * with another list-mutation primitive, such as hlist_add_head_rcu()
317 * or hlist_del_rcu(), running on this same list.
318 * However, it is perfectly legal to run concurrently with
319 * the _rcu list-traversal primitives, such as
320 * hlist_for_each_entry().
321 */
322static inline void hlist_del_rcu(struct hlist_node *n)
323{
324 __hlist_del(n);
325 n->pprev = LIST_POISON2;
326}
327
328/**
329 * hlist_replace_rcu - replace old entry by new one
330 * @old : the element to be replaced
331 * @new : the new element to insert
332 *
333 * The @old entry will be replaced with the @new entry atomically.
334 */
335static inline void hlist_replace_rcu(struct hlist_node *old,
336 struct hlist_node *new)
337{
338 struct hlist_node *next = old->next;
339
340 new->next = next;
341 new->pprev = old->pprev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100342 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200343 if (next)
344 new->next->pprev = &new->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200345 old->pprev = LIST_POISON2;
346}
347
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100348/*
349 * return the first or the next element in an RCU protected hlist
350 */
351#define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
352#define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
353#define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
354
Franck Bui-Huu82524742008-05-12 21:21:05 +0200355/**
356 * hlist_add_head_rcu
357 * @n: the element to add to the hash list.
358 * @h: the list to add to.
359 *
360 * Description:
361 * Adds the specified element to the specified hlist,
362 * while permitting racing traversals.
363 *
364 * The caller must take whatever precautions are necessary
365 * (such as holding appropriate locks) to avoid racing
366 * with another list-mutation primitive, such as hlist_add_head_rcu()
367 * or hlist_del_rcu(), running on this same list.
368 * However, it is perfectly legal to run concurrently with
369 * the _rcu list-traversal primitives, such as
370 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
371 * problems on Alpha CPUs. Regardless of the type of CPU, the
372 * list-traversal primitive must be guarded by rcu_read_lock().
373 */
374static inline void hlist_add_head_rcu(struct hlist_node *n,
375 struct hlist_head *h)
376{
377 struct hlist_node *first = h->first;
Franck Bui-Huu10aa9d22008-05-12 21:21:06 +0200378
Franck Bui-Huu82524742008-05-12 21:21:05 +0200379 n->next = first;
380 n->pprev = &h->first;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100381 rcu_assign_pointer(hlist_first_rcu(h), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200382 if (first)
383 first->pprev = &n->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200384}
385
386/**
387 * hlist_add_before_rcu
388 * @n: the new element to add to the hash list.
389 * @next: the existing element to add the new element before.
390 *
391 * Description:
392 * Adds the specified element to the specified hlist
393 * before the specified node while permitting racing traversals.
394 *
395 * The caller must take whatever precautions are necessary
396 * (such as holding appropriate locks) to avoid racing
397 * with another list-mutation primitive, such as hlist_add_head_rcu()
398 * or hlist_del_rcu(), running on this same list.
399 * However, it is perfectly legal to run concurrently with
400 * the _rcu list-traversal primitives, such as
401 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
402 * problems on Alpha CPUs.
403 */
404static inline void hlist_add_before_rcu(struct hlist_node *n,
405 struct hlist_node *next)
406{
407 n->pprev = next->pprev;
408 n->next = next;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100409 rcu_assign_pointer(hlist_pprev_rcu(n), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200410 next->pprev = &n->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200411}
412
413/**
414 * hlist_add_after_rcu
415 * @prev: the existing element to add the new element after.
416 * @n: the new element to add to the hash list.
417 *
418 * Description:
419 * Adds the specified element to the specified hlist
420 * after the specified node while permitting racing traversals.
421 *
422 * The caller must take whatever precautions are necessary
423 * (such as holding appropriate locks) to avoid racing
424 * with another list-mutation primitive, such as hlist_add_head_rcu()
425 * or hlist_del_rcu(), running on this same list.
426 * However, it is perfectly legal to run concurrently with
427 * the _rcu list-traversal primitives, such as
428 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
429 * problems on Alpha CPUs.
430 */
431static inline void hlist_add_after_rcu(struct hlist_node *prev,
432 struct hlist_node *n)
433{
434 n->next = prev->next;
435 n->pprev = &prev->next;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100436 rcu_assign_pointer(hlist_next_rcu(prev), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200437 if (n->next)
438 n->next->pprev = &n->next;
439}
440
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100441#define __hlist_for_each_rcu(pos, head) \
442 for (pos = rcu_dereference(hlist_first_rcu(head)); \
Linus Torvalds75d65a42011-05-19 13:50:07 -0700443 pos; \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100444 pos = rcu_dereference(hlist_next_rcu(pos)))
stephen hemminger1cc52322010-02-22 07:57:17 +0000445
Franck Bui-Huu82524742008-05-12 21:21:05 +0200446/**
447 * hlist_for_each_entry_rcu - iterate over rcu list of given type
Sasha Levinb67bfe02013-02-27 17:06:00 -0800448 * @pos: the type * to use as a loop cursor.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200449 * @head: the head for your list.
450 * @member: the name of the hlist_node within the struct.
451 *
452 * This list-traversal primitive may safely run concurrently with
453 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
454 * as long as the traversal is guarded by rcu_read_lock().
455 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800456#define hlist_for_each_entry_rcu(pos, head, member) \
457 for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
458 typeof(*(pos)), member); \
459 pos; \
460 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
461 &(pos)->member)), typeof(*(pos)), member))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200462
stephen hemminger5c578ae2010-03-17 20:31:11 +0000463/**
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000464 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
Sasha Levinb67bfe02013-02-27 17:06:00 -0800465 * @pos: the type * to use as a loop cursor.
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000466 * @head: the head for your list.
467 * @member: the name of the hlist_node within the struct.
468 *
469 * This list-traversal primitive may safely run concurrently with
470 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
471 * as long as the traversal is guarded by rcu_read_lock().
472 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800473#define hlist_for_each_entry_rcu_bh(pos, head, member) \
474 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
475 typeof(*(pos)), member); \
476 pos; \
477 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
478 &(pos)->member)), typeof(*(pos)), member))
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000479
480/**
stephen hemminger5c578ae2010-03-17 20:31:11 +0000481 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
Sasha Levinb67bfe02013-02-27 17:06:00 -0800482 * @pos: the type * to use as a loop cursor.
stephen hemminger5c578ae2010-03-17 20:31:11 +0000483 * @member: the name of the hlist_node within the struct.
484 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800485#define hlist_for_each_entry_continue_rcu(pos, member) \
486 for (pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
487 typeof(*(pos)), member); \
488 pos; \
489 pos = hlist_entry_safe(rcu_dereference((pos)->member.next),\
490 typeof(*(pos)), member))
stephen hemminger5c578ae2010-03-17 20:31:11 +0000491
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000492/**
493 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
Sasha Levinb67bfe02013-02-27 17:06:00 -0800494 * @pos: the type * to use as a loop cursor.
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000495 * @member: the name of the hlist_node within the struct.
496 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800497#define hlist_for_each_entry_continue_rcu_bh(pos, member) \
498 for (pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\
499 typeof(*(pos)), member); \
500 pos; \
501 pos = hlist_entry_safe(rcu_dereference_bh((pos)->member.next),\
502 typeof(*(pos)), member))
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000503
stephen hemminger5c578ae2010-03-17 20:31:11 +0000504
Franck Bui-Huu82524742008-05-12 21:21:05 +0200505#endif /* __KERNEL__ */
506#endif