blob: 8beb98dcf14f066fc4e9075ed0b94cc29998c9bc [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/*
Paul E. McKenney2a855b62013-08-23 09:40:42 -070022 * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
23 * @list: list to be initialized
24 *
25 * You should instead use INIT_LIST_HEAD() for normal initialization and
26 * cleanup tasks, when readers have no access to the list being initialized.
27 * However, if the list being initialized is visible to readers, you
28 * need to keep the compiler from being too mischievous.
29 */
30static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
31{
Paul E. McKenney7d0ae802015-03-03 14:57:58 -080032 WRITE_ONCE(list->next, list);
33 WRITE_ONCE(list->prev, list);
Paul E. McKenney2a855b62013-08-23 09:40:42 -070034}
35
36/*
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010037 * return the ->next pointer of a list_head in an rcu safe
38 * way, we must not access it directly
39 */
40#define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
41
42/*
Franck Bui-Huu82524742008-05-12 21:21:05 +020043 * Insert a new entry between two known consecutive entries.
44 *
45 * This is only for internal list manipulation where we know
46 * the prev/next entries already!
47 */
Dave Jones559f9ba2012-03-14 22:17:39 -040048#ifndef CONFIG_DEBUG_LIST
Franck Bui-Huu82524742008-05-12 21:21:05 +020049static inline void __list_add_rcu(struct list_head *new,
50 struct list_head *prev, struct list_head *next)
51{
52 new->next = next;
53 new->prev = prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010054 rcu_assign_pointer(list_next_rcu(prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +020055 next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +020056}
Dave Jones559f9ba2012-03-14 22:17:39 -040057#else
Teodora Baluta584dc4c2013-11-11 17:11:23 +020058void __list_add_rcu(struct list_head *new,
59 struct list_head *prev, struct list_head *next);
Dave Jones559f9ba2012-03-14 22:17:39 -040060#endif
Franck Bui-Huu82524742008-05-12 21:21:05 +020061
62/**
63 * list_add_rcu - add a new entry to rcu-protected list
64 * @new: new entry to be added
65 * @head: list head to add it after
66 *
67 * Insert a new entry after the specified head.
68 * This is good for implementing stacks.
69 *
70 * The caller must take whatever precautions are necessary
71 * (such as holding appropriate locks) to avoid racing
72 * with another list-mutation primitive, such as list_add_rcu()
73 * or list_del_rcu(), running on this same list.
74 * However, it is perfectly legal to run concurrently with
75 * the _rcu list-traversal primitives, such as
76 * list_for_each_entry_rcu().
77 */
78static inline void list_add_rcu(struct list_head *new, struct list_head *head)
79{
80 __list_add_rcu(new, head, head->next);
81}
82
83/**
84 * list_add_tail_rcu - add a new entry to rcu-protected list
85 * @new: new entry to be added
86 * @head: list head to add it before
87 *
88 * Insert a new entry before the specified head.
89 * This is useful for implementing queues.
90 *
91 * The caller must take whatever precautions are necessary
92 * (such as holding appropriate locks) to avoid racing
93 * with another list-mutation primitive, such as list_add_tail_rcu()
94 * or list_del_rcu(), running on this same list.
95 * However, it is perfectly legal to run concurrently with
96 * the _rcu list-traversal primitives, such as
97 * list_for_each_entry_rcu().
98 */
99static inline void list_add_tail_rcu(struct list_head *new,
100 struct list_head *head)
101{
102 __list_add_rcu(new, head->prev, head);
103}
104
105/**
106 * list_del_rcu - deletes entry from list without re-initialization
107 * @entry: the element to delete from the list.
108 *
109 * Note: list_empty() on entry does not return true after this,
110 * the entry is in an undefined state. It is useful for RCU based
111 * lockfree traversal.
112 *
113 * In particular, it means that we can not poison the forward
114 * pointers that may still be used for walking the list.
115 *
116 * The caller must take whatever precautions are necessary
117 * (such as holding appropriate locks) to avoid racing
118 * with another list-mutation primitive, such as list_del_rcu()
119 * or list_add_rcu(), running on this same list.
120 * However, it is perfectly legal to run concurrently with
121 * the _rcu list-traversal primitives, such as
122 * list_for_each_entry_rcu().
123 *
124 * Note that the caller is not permitted to immediately free
125 * the newly deleted entry. Instead, either synchronize_rcu()
126 * or call_rcu() must be used to defer freeing until an RCU
127 * grace period has elapsed.
128 */
129static inline void list_del_rcu(struct list_head *entry)
130{
Dave Jones559f9ba2012-03-14 22:17:39 -0400131 __list_del_entry(entry);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200132 entry->prev = LIST_POISON2;
133}
134
135/**
Andrea Arcangeli6beeac72008-07-28 15:46:22 -0700136 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
137 * @n: the element to delete from the hash list.
138 *
139 * Note: list_unhashed() on the node return true after this. It is
140 * useful for RCU based read lockfree traversal if the writer side
141 * must know if the list entry is still hashed or already unhashed.
142 *
143 * In particular, it means that we can not poison the forward pointers
144 * that may still be used for walking the hash list and we can only
145 * zero the pprev pointer so list_unhashed() will return true after
146 * this.
147 *
148 * The caller must take whatever precautions are necessary (such as
149 * holding appropriate locks) to avoid racing with another
150 * list-mutation primitive, such as hlist_add_head_rcu() or
151 * hlist_del_rcu(), running on this same list. However, it is
152 * perfectly legal to run concurrently with the _rcu list-traversal
153 * primitives, such as hlist_for_each_entry_rcu().
154 */
155static inline void hlist_del_init_rcu(struct hlist_node *n)
156{
157 if (!hlist_unhashed(n)) {
158 __hlist_del(n);
159 n->pprev = NULL;
160 }
161}
162
163/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200164 * list_replace_rcu - replace old entry by new one
165 * @old : the element to be replaced
166 * @new : the new element to insert
167 *
168 * The @old entry will be replaced with the @new entry atomically.
169 * Note: @old should not be empty.
170 */
171static inline void list_replace_rcu(struct list_head *old,
172 struct list_head *new)
173{
174 new->next = old->next;
175 new->prev = old->prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100176 rcu_assign_pointer(list_next_rcu(new->prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200177 new->next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200178 old->prev = LIST_POISON2;
179}
180
181/**
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300182 * __list_splice_init_rcu - join an RCU-protected list into an existing list.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200183 * @list: the RCU-protected list to splice
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300184 * @prev: points to the last element of the existing list
185 * @next: points to the first element of the existing list
Franck Bui-Huu82524742008-05-12 21:21:05 +0200186 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
187 *
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300188 * The list pointed to by @prev and @next can be RCU-read traversed
189 * concurrently with this function.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200190 *
191 * Note that this function blocks.
192 *
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300193 * Important note: the caller must take whatever action is necessary to prevent
194 * any other updates to the existing list. In principle, it is possible to
195 * modify the list as soon as sync() begins execution. If this sort of thing
196 * becomes necessary, an alternative version based on call_rcu() could be
197 * created. But only if -really- needed -- there is no shortage of RCU API
198 * members.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200199 */
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300200static inline void __list_splice_init_rcu(struct list_head *list,
201 struct list_head *prev,
202 struct list_head *next,
203 void (*sync)(void))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200204{
205 struct list_head *first = list->next;
206 struct list_head *last = list->prev;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200207
Paul E. McKenney2a855b62013-08-23 09:40:42 -0700208 /*
209 * "first" and "last" tracking list, so initialize it. RCU readers
210 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
211 * instead of INIT_LIST_HEAD().
212 */
Franck Bui-Huu82524742008-05-12 21:21:05 +0200213
Paul E. McKenney2a855b62013-08-23 09:40:42 -0700214 INIT_LIST_HEAD_RCU(list);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200215
216 /*
217 * At this point, the list body still points to the source list.
218 * Wait for any readers to finish using the list before splicing
219 * the list body into the new list. Any new readers will see
220 * an empty list.
221 */
222
223 sync();
224
225 /*
226 * Readers are finished with the source list, so perform splice.
227 * The order is important if the new list is global and accessible
228 * to concurrent RCU readers. Note that RCU readers are not
229 * permitted to traverse the prev pointers without excluding
230 * this function.
231 */
232
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300233 last->next = next;
234 rcu_assign_pointer(list_next_rcu(prev), first);
235 first->prev = prev;
236 next->prev = last;
237}
238
239/**
240 * list_splice_init_rcu - splice an RCU-protected list into an existing list,
241 * designed for stacks.
242 * @list: the RCU-protected list to splice
243 * @head: the place in the existing list to splice the first list into
244 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
245 */
246static inline void list_splice_init_rcu(struct list_head *list,
247 struct list_head *head,
248 void (*sync)(void))
249{
250 if (!list_empty(list))
251 __list_splice_init_rcu(list, head, head->next, sync);
252}
253
254/**
255 * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
256 * list, designed for queues.
257 * @list: the RCU-protected list to splice
258 * @head: the place in the existing list to splice the first list into
259 * @sync: function to sync: synchronize_rcu(), synchronize_sched(), ...
260 */
261static inline void list_splice_tail_init_rcu(struct list_head *list,
262 struct list_head *head,
263 void (*sync)(void))
264{
265 if (!list_empty(list))
266 __list_splice_init_rcu(list, head->prev, head, sync);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200267}
268
Jiri Pirko72c6a982009-04-14 17:33:57 +0200269/**
270 * list_entry_rcu - get the struct for this entry
271 * @ptr: the &struct list_head pointer.
272 * @type: the type of the struct this is embedded in.
Andrey Utkin3943f422014-11-14 05:09:55 +0400273 * @member: the name of the list_head within the struct.
Jiri Pirko72c6a982009-04-14 17:33:57 +0200274 *
275 * This primitive may safely run concurrently with the _rcu list-mutation
276 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
277 */
278#define list_entry_rcu(ptr, type, member) \
Patrick Marlier8db70b12015-09-11 15:50:35 -0700279 container_of(lockless_dereference(ptr), type, member)
Jiri Pirko72c6a982009-04-14 17:33:57 +0200280
281/**
Michel Machadof88022a2012-04-10 14:07:40 -0400282 * Where are list_empty_rcu() and list_first_entry_rcu()?
283 *
284 * Implementing those functions following their counterparts list_empty() and
285 * list_first_entry() is not advisable because they lead to subtle race
286 * conditions as the following snippet shows:
287 *
288 * if (!list_empty_rcu(mylist)) {
289 * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
290 * do_something(bar);
291 * }
292 *
293 * The list may not be empty when list_empty_rcu checks it, but it may be when
294 * list_first_entry_rcu rereads the ->next pointer.
295 *
296 * Rereading the ->next pointer is not a problem for list_empty() and
297 * list_first_entry() because they would be protected by a lock that blocks
298 * writers.
299 *
300 * See list_first_or_null_rcu for an alternative.
301 */
302
303/**
304 * list_first_or_null_rcu - get the first element from a list
Jiri Pirko72c6a982009-04-14 17:33:57 +0200305 * @ptr: the list head to take the element from.
306 * @type: the type of the struct this is embedded in.
Andrey Utkin3943f422014-11-14 05:09:55 +0400307 * @member: the name of the list_head within the struct.
Jiri Pirko72c6a982009-04-14 17:33:57 +0200308 *
Michel Machadof88022a2012-04-10 14:07:40 -0400309 * Note that if the list is empty, it returns NULL.
Jiri Pirko72c6a982009-04-14 17:33:57 +0200310 *
311 * This primitive may safely run concurrently with the _rcu list-mutation
312 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
313 */
Michel Machadof88022a2012-04-10 14:07:40 -0400314#define list_first_or_null_rcu(ptr, type, member) \
Joe Perches0adab9b2013-12-05 16:19:15 -0800315({ \
316 struct list_head *__ptr = (ptr); \
Paul E. McKenney7d0ae802015-03-03 14:57:58 -0800317 struct list_head *__next = READ_ONCE(__ptr->next); \
Joe Perches0adab9b2013-12-05 16:19:15 -0800318 likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
319})
Jiri Pirko72c6a982009-04-14 17:33:57 +0200320
Franck Bui-Huu82524742008-05-12 21:21:05 +0200321/**
Tom Herbertff3c44e2016-03-07 14:11:00 -0800322 * list_next_or_null_rcu - get the first element from a list
323 * @head: the head for the list.
324 * @ptr: the list head to take the next element from.
325 * @type: the type of the struct this is embedded in.
326 * @member: the name of the list_head within the struct.
327 *
328 * Note that if the ptr is at the end of the list, NULL is returned.
329 *
330 * This primitive may safely run concurrently with the _rcu list-mutation
331 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
332 */
333#define list_next_or_null_rcu(head, ptr, type, member) \
334({ \
335 struct list_head *__head = (head); \
336 struct list_head *__ptr = (ptr); \
337 struct list_head *__next = READ_ONCE(__ptr->next); \
338 likely(__next != __head) ? list_entry_rcu(__next, type, \
339 member) : NULL; \
340})
341
342/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200343 * list_for_each_entry_rcu - iterate over rcu list of given type
344 * @pos: the type * to use as a loop cursor.
345 * @head: the head for your list.
Andrey Utkin3943f422014-11-14 05:09:55 +0400346 * @member: the name of the list_head within the struct.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200347 *
348 * This list-traversal primitive may safely run concurrently with
349 * the _rcu list-mutation primitives such as list_add_rcu()
350 * as long as the traversal is guarded by rcu_read_lock().
351 */
352#define list_for_each_entry_rcu(pos, head, member) \
Jiri Pirko72c6a982009-04-14 17:33:57 +0200353 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
Linus Torvaldse66eed62011-05-19 14:15:29 -0700354 &pos->member != (head); \
Jiri Pirko72c6a982009-04-14 17:33:57 +0200355 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200356
Franck Bui-Huu82524742008-05-12 21:21:05 +0200357/**
Alexey Kardashevskiy69b90722015-12-05 18:14:19 -0800358 * list_entry_lockless - get the struct for this entry
359 * @ptr: the &struct list_head pointer.
360 * @type: the type of the struct this is embedded in.
361 * @member: the name of the list_head within the struct.
362 *
363 * This primitive may safely run concurrently with the _rcu list-mutation
364 * primitives such as list_add_rcu(), but requires some implicit RCU
365 * read-side guarding. One example is running within a special
366 * exception-time environment where preemption is disabled and where
367 * lockdep cannot be invoked (in which case updaters must use RCU-sched,
368 * as in synchronize_sched(), call_rcu_sched(), and friends). Another
369 * example is when items are added to the list, but never deleted.
370 */
371#define list_entry_lockless(ptr, type, member) \
372 container_of((typeof(ptr))lockless_dereference(ptr), type, member)
373
374/**
375 * list_for_each_entry_lockless - iterate over rcu list of given type
376 * @pos: the type * to use as a loop cursor.
377 * @head: the head for your list.
378 * @member: the name of the list_struct within the struct.
379 *
380 * This primitive may safely run concurrently with the _rcu list-mutation
381 * primitives such as list_add_rcu(), but requires some implicit RCU
382 * read-side guarding. One example is running within a special
383 * exception-time environment where preemption is disabled and where
384 * lockdep cannot be invoked (in which case updaters must use RCU-sched,
385 * as in synchronize_sched(), call_rcu_sched(), and friends). Another
386 * example is when items are added to the list, but never deleted.
387 */
388#define list_for_each_entry_lockless(pos, head, member) \
389 for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
390 &pos->member != (head); \
391 pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
392
393/**
stephen hemminger254245d2009-11-10 07:54:47 +0000394 * list_for_each_entry_continue_rcu - continue iteration over list of given type
395 * @pos: the type * to use as a loop cursor.
396 * @head: the head for your list.
Andrey Utkin3943f422014-11-14 05:09:55 +0400397 * @member: the name of the list_head within the struct.
stephen hemminger254245d2009-11-10 07:54:47 +0000398 *
399 * Continue to iterate over list of given type, continuing after
400 * the current position.
401 */
402#define list_for_each_entry_continue_rcu(pos, head, member) \
403 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
Linus Torvaldse66eed62011-05-19 14:15:29 -0700404 &pos->member != (head); \
stephen hemminger254245d2009-11-10 07:54:47 +0000405 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
406
407/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200408 * hlist_del_rcu - deletes entry from hash list without re-initialization
409 * @n: the element to delete from the hash list.
410 *
411 * Note: list_unhashed() on entry does not return true after this,
412 * the entry is in an undefined state. It is useful for RCU based
413 * lockfree traversal.
414 *
415 * In particular, it means that we can not poison the forward
416 * pointers that may still be used for walking the hash list.
417 *
418 * The caller must take whatever precautions are necessary
419 * (such as holding appropriate locks) to avoid racing
420 * with another list-mutation primitive, such as hlist_add_head_rcu()
421 * or hlist_del_rcu(), running on this same list.
422 * However, it is perfectly legal to run concurrently with
423 * the _rcu list-traversal primitives, such as
424 * hlist_for_each_entry().
425 */
426static inline void hlist_del_rcu(struct hlist_node *n)
427{
428 __hlist_del(n);
429 n->pprev = LIST_POISON2;
430}
431
432/**
433 * hlist_replace_rcu - replace old entry by new one
434 * @old : the element to be replaced
435 * @new : the new element to insert
436 *
437 * The @old entry will be replaced with the @new entry atomically.
438 */
439static inline void hlist_replace_rcu(struct hlist_node *old,
440 struct hlist_node *new)
441{
442 struct hlist_node *next = old->next;
443
444 new->next = next;
445 new->pprev = old->pprev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100446 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200447 if (next)
448 new->next->pprev = &new->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200449 old->pprev = LIST_POISON2;
450}
451
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100452/*
453 * return the first or the next element in an RCU protected hlist
454 */
455#define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
456#define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
457#define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
458
Franck Bui-Huu82524742008-05-12 21:21:05 +0200459/**
460 * hlist_add_head_rcu
461 * @n: the element to add to the hash list.
462 * @h: the list to add to.
463 *
464 * Description:
465 * Adds the specified element to the specified hlist,
466 * while permitting racing traversals.
467 *
468 * The caller must take whatever precautions are necessary
469 * (such as holding appropriate locks) to avoid racing
470 * with another list-mutation primitive, such as hlist_add_head_rcu()
471 * or hlist_del_rcu(), running on this same list.
472 * However, it is perfectly legal to run concurrently with
473 * the _rcu list-traversal primitives, such as
474 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
475 * problems on Alpha CPUs. Regardless of the type of CPU, the
476 * list-traversal primitive must be guarded by rcu_read_lock().
477 */
478static inline void hlist_add_head_rcu(struct hlist_node *n,
479 struct hlist_head *h)
480{
481 struct hlist_node *first = h->first;
Franck Bui-Huu10aa9d22008-05-12 21:21:06 +0200482
Franck Bui-Huu82524742008-05-12 21:21:05 +0200483 n->next = first;
484 n->pprev = &h->first;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100485 rcu_assign_pointer(hlist_first_rcu(h), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200486 if (first)
487 first->pprev = &n->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200488}
489
490/**
David S. Miller1602f492016-04-23 18:26:24 -0400491 * hlist_add_tail_rcu
492 * @n: the element to add to the hash list.
493 * @h: the list to add to.
494 *
495 * Description:
496 * Adds the specified element to the specified hlist,
497 * while permitting racing traversals.
498 *
499 * The caller must take whatever precautions are necessary
500 * (such as holding appropriate locks) to avoid racing
501 * with another list-mutation primitive, such as hlist_add_head_rcu()
502 * or hlist_del_rcu(), running on this same list.
503 * However, it is perfectly legal to run concurrently with
504 * the _rcu list-traversal primitives, such as
505 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
506 * problems on Alpha CPUs. Regardless of the type of CPU, the
507 * list-traversal primitive must be guarded by rcu_read_lock().
508 */
509static inline void hlist_add_tail_rcu(struct hlist_node *n,
510 struct hlist_head *h)
511{
512 struct hlist_node *i, *last = NULL;
513
514 for (i = hlist_first_rcu(h); i; i = hlist_next_rcu(i))
515 last = i;
516
517 if (last) {
518 n->next = last->next;
519 n->pprev = &last->next;
520 rcu_assign_pointer(hlist_next_rcu(last), n);
521 } else {
522 hlist_add_head_rcu(n, h);
523 }
524}
525
526/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200527 * hlist_add_before_rcu
528 * @n: the new element to add to the hash list.
529 * @next: the existing element to add the new element before.
530 *
531 * Description:
532 * Adds the specified element to the specified hlist
533 * before the specified node while permitting racing traversals.
534 *
535 * The caller must take whatever precautions are necessary
536 * (such as holding appropriate locks) to avoid racing
537 * with another list-mutation primitive, such as hlist_add_head_rcu()
538 * or hlist_del_rcu(), running on this same list.
539 * However, it is perfectly legal to run concurrently with
540 * the _rcu list-traversal primitives, such as
541 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
542 * problems on Alpha CPUs.
543 */
544static inline void hlist_add_before_rcu(struct hlist_node *n,
545 struct hlist_node *next)
546{
547 n->pprev = next->pprev;
548 n->next = next;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100549 rcu_assign_pointer(hlist_pprev_rcu(n), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200550 next->pprev = &n->next;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200551}
552
553/**
Ken Helias1d023282014-08-06 16:09:16 -0700554 * hlist_add_behind_rcu
Franck Bui-Huu82524742008-05-12 21:21:05 +0200555 * @n: the new element to add to the hash list.
Ken Helias1d023282014-08-06 16:09:16 -0700556 * @prev: the existing element to add the new element after.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200557 *
558 * Description:
559 * Adds the specified element to the specified hlist
560 * after the specified node while permitting racing traversals.
561 *
562 * The caller must take whatever precautions are necessary
563 * (such as holding appropriate locks) to avoid racing
564 * with another list-mutation primitive, such as hlist_add_head_rcu()
565 * or hlist_del_rcu(), running on this same list.
566 * However, it is perfectly legal to run concurrently with
567 * the _rcu list-traversal primitives, such as
568 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
569 * problems on Alpha CPUs.
570 */
Ken Helias1d023282014-08-06 16:09:16 -0700571static inline void hlist_add_behind_rcu(struct hlist_node *n,
572 struct hlist_node *prev)
Franck Bui-Huu82524742008-05-12 21:21:05 +0200573{
574 n->next = prev->next;
575 n->pprev = &prev->next;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100576 rcu_assign_pointer(hlist_next_rcu(prev), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200577 if (n->next)
578 n->next->pprev = &n->next;
579}
580
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100581#define __hlist_for_each_rcu(pos, head) \
582 for (pos = rcu_dereference(hlist_first_rcu(head)); \
Linus Torvalds75d65a42011-05-19 13:50:07 -0700583 pos; \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100584 pos = rcu_dereference(hlist_next_rcu(pos)))
stephen hemminger1cc52322010-02-22 07:57:17 +0000585
Franck Bui-Huu82524742008-05-12 21:21:05 +0200586/**
587 * hlist_for_each_entry_rcu - iterate over rcu list of given type
Sasha Levinb67bfe02013-02-27 17:06:00 -0800588 * @pos: the type * to use as a loop cursor.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200589 * @head: the head for your list.
590 * @member: the name of the hlist_node within the struct.
591 *
592 * This list-traversal primitive may safely run concurrently with
593 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
594 * as long as the traversal is guarded by rcu_read_lock().
595 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800596#define hlist_for_each_entry_rcu(pos, head, member) \
597 for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
598 typeof(*(pos)), member); \
599 pos; \
600 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
601 &(pos)->member)), typeof(*(pos)), member))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200602
stephen hemminger5c578aed2010-03-17 20:31:11 +0000603/**
Steven Rostedt12bcbe62013-05-28 14:38:42 -0400604 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
605 * @pos: the type * to use as a loop cursor.
606 * @head: the head for your list.
607 * @member: the name of the hlist_node within the struct.
608 *
609 * This list-traversal primitive may safely run concurrently with
610 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
611 * as long as the traversal is guarded by rcu_read_lock().
612 *
613 * This is the same as hlist_for_each_entry_rcu() except that it does
614 * not do any RCU debugging or tracing.
615 */
616#define hlist_for_each_entry_rcu_notrace(pos, head, member) \
617 for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\
618 typeof(*(pos)), member); \
619 pos; \
620 pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\
621 &(pos)->member)), typeof(*(pos)), member))
622
623/**
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000624 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
Sasha Levinb67bfe02013-02-27 17:06:00 -0800625 * @pos: the type * to use as a loop cursor.
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000626 * @head: the head for your list.
627 * @member: the name of the hlist_node within the struct.
628 *
629 * This list-traversal primitive may safely run concurrently with
630 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
631 * as long as the traversal is guarded by rcu_read_lock().
632 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800633#define hlist_for_each_entry_rcu_bh(pos, head, member) \
634 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
635 typeof(*(pos)), member); \
636 pos; \
637 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
638 &(pos)->member)), typeof(*(pos)), member))
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000639
640/**
stephen hemminger5c578aed2010-03-17 20:31:11 +0000641 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
Sasha Levinb67bfe02013-02-27 17:06:00 -0800642 * @pos: the type * to use as a loop cursor.
stephen hemminger5c578aed2010-03-17 20:31:11 +0000643 * @member: the name of the hlist_node within the struct.
644 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800645#define hlist_for_each_entry_continue_rcu(pos, member) \
Ying Xuef520c982014-12-12 09:36:14 +0800646 for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
647 &(pos)->member)), typeof(*(pos)), member); \
Sasha Levinb67bfe02013-02-27 17:06:00 -0800648 pos; \
Ying Xuef520c982014-12-12 09:36:14 +0800649 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
650 &(pos)->member)), typeof(*(pos)), member))
stephen hemminger5c578aed2010-03-17 20:31:11 +0000651
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000652/**
653 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
Sasha Levinb67bfe02013-02-27 17:06:00 -0800654 * @pos: the type * to use as a loop cursor.
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000655 * @member: the name of the hlist_node within the struct.
656 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800657#define hlist_for_each_entry_continue_rcu_bh(pos, member) \
Ying Xuef520c982014-12-12 09:36:14 +0800658 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
659 &(pos)->member)), typeof(*(pos)), member); \
Sasha Levinb67bfe02013-02-27 17:06:00 -0800660 pos; \
Ying Xuef520c982014-12-12 09:36:14 +0800661 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
662 &(pos)->member)), typeof(*(pos)), member))
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000663
Ying Xue97ede292014-12-02 15:00:30 +0800664/**
665 * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
666 * @pos: the type * to use as a loop cursor.
667 * @member: the name of the hlist_node within the struct.
668 */
669#define hlist_for_each_entry_from_rcu(pos, member) \
670 for (; pos; \
Ying Xuef5177002015-03-26 13:27:08 +0800671 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
672 &(pos)->member)), typeof(*(pos)), member))
stephen hemminger5c578aed2010-03-17 20:31:11 +0000673
Franck Bui-Huu82524742008-05-12 21:21:05 +0200674#endif /* __KERNEL__ */
675#endif