blob: d29740be4833e22c604298046784443a87e73338 [file] [log] [blame]
Greg Kroah-Hartmanb2441312017-11-01 15:07:57 +01001/* SPDX-License-Identifier: GPL-2.0 */
Franck Bui-Huu82524742008-05-12 21:21:05 +02002#ifndef _LINUX_RCULIST_H
3#define _LINUX_RCULIST_H
4
5#ifdef __KERNEL__
6
7/*
8 * RCU-protected list version
9 */
10#include <linux/list.h>
Franck Bui-Huu10aa9d22008-05-12 21:21:06 +020011#include <linux/rcupdate.h>
Franck Bui-Huu82524742008-05-12 21:21:05 +020012
13/*
Paul E. McKenney2a855b62013-08-23 09:40:42 -070014 * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
15 * @list: list to be initialized
16 *
17 * You should instead use INIT_LIST_HEAD() for normal initialization and
18 * cleanup tasks, when readers have no access to the list being initialized.
19 * However, if the list being initialized is visible to readers, you
20 * need to keep the compiler from being too mischievous.
21 */
22static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
23{
Paul E. McKenney7d0ae802015-03-03 14:57:58 -080024 WRITE_ONCE(list->next, list);
25 WRITE_ONCE(list->prev, list);
Paul E. McKenney2a855b62013-08-23 09:40:42 -070026}
27
28/*
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010029 * return the ->next pointer of a list_head in an rcu safe
30 * way, we must not access it directly
31 */
32#define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
33
Madhuparna Bhowmikafa47fd2019-12-09 13:20:43 +053034/**
35 * list_tail_rcu - returns the prev pointer of the head of the list
36 * @head: the head of the list
37 *
38 * Note: This should only be used with the list header, and even then
39 * only if list_del() and similar primitives are not also used on the
40 * list header.
41 */
42#define list_tail_rcu(head) (*((struct list_head __rcu **)(&(head)->prev)))
43
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010044/*
Joel Fernandes (Google)28875942019-07-16 18:12:22 -040045 * Check during list traversal that we are within an RCU reader
46 */
47
48#define check_arg_count_one(dummy)
49
50#ifdef CONFIG_PROVE_RCU_LIST
51#define __list_check_rcu(dummy, cond, extra...) \
52 ({ \
53 check_arg_count_one(extra); \
Amol Grover4dfd5cd2020-01-18 22:24:18 +053054 RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(), \
Joel Fernandes (Google)28875942019-07-16 18:12:22 -040055 "RCU-list traversed in non-reader section!"); \
Amol Grover4dfd5cd2020-01-18 22:24:18 +053056 })
Madhuparna Bhowmikae2212a2020-07-12 18:40:02 +053057
58#define __list_check_srcu(cond) \
59 ({ \
60 RCU_LOCKDEP_WARN(!(cond), \
61 "RCU-list traversed without holding the required lock!");\
62 })
Joel Fernandes (Google)28875942019-07-16 18:12:22 -040063#else
64#define __list_check_rcu(dummy, cond, extra...) \
65 ({ check_arg_count_one(extra); })
Madhuparna Bhowmikae2212a2020-07-12 18:40:02 +053066
67#define __list_check_srcu(cond) ({ })
Joel Fernandes (Google)28875942019-07-16 18:12:22 -040068#endif
69
70/*
Franck Bui-Huu82524742008-05-12 21:21:05 +020071 * Insert a new entry between two known consecutive entries.
72 *
73 * This is only for internal list manipulation where we know
74 * the prev/next entries already!
75 */
76static inline void __list_add_rcu(struct list_head *new,
77 struct list_head *prev, struct list_head *next)
78{
Kees Cook54acd432016-08-17 14:42:09 -070079 if (!__list_add_valid(new, prev, next))
80 return;
81
Franck Bui-Huu82524742008-05-12 21:21:05 +020082 new->next = next;
83 new->prev = prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +010084 rcu_assign_pointer(list_next_rcu(prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +020085 next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +020086}
87
88/**
89 * list_add_rcu - add a new entry to rcu-protected list
90 * @new: new entry to be added
91 * @head: list head to add it after
92 *
93 * Insert a new entry after the specified head.
94 * This is good for implementing stacks.
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_add_rcu()
99 * or list_del_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 */
104static inline void list_add_rcu(struct list_head *new, struct list_head *head)
105{
106 __list_add_rcu(new, head, head->next);
107}
108
109/**
110 * list_add_tail_rcu - add a new entry to rcu-protected list
111 * @new: new entry to be added
112 * @head: list head to add it before
113 *
114 * Insert a new entry before the specified head.
115 * This is useful for implementing queues.
116 *
117 * The caller must take whatever precautions are necessary
118 * (such as holding appropriate locks) to avoid racing
119 * with another list-mutation primitive, such as list_add_tail_rcu()
120 * or list_del_rcu(), running on this same list.
121 * However, it is perfectly legal to run concurrently with
122 * the _rcu list-traversal primitives, such as
123 * list_for_each_entry_rcu().
124 */
125static inline void list_add_tail_rcu(struct list_head *new,
126 struct list_head *head)
127{
128 __list_add_rcu(new, head->prev, head);
129}
130
131/**
132 * list_del_rcu - deletes entry from list without re-initialization
133 * @entry: the element to delete from the list.
134 *
135 * Note: list_empty() on entry does not return true after this,
136 * the entry is in an undefined state. It is useful for RCU based
137 * lockfree traversal.
138 *
139 * In particular, it means that we can not poison the forward
140 * pointers that may still be used for walking the list.
141 *
142 * The caller must take whatever precautions are necessary
143 * (such as holding appropriate locks) to avoid racing
144 * with another list-mutation primitive, such as list_del_rcu()
145 * or list_add_rcu(), running on this same list.
146 * However, it is perfectly legal to run concurrently with
147 * the _rcu list-traversal primitives, such as
148 * list_for_each_entry_rcu().
149 *
150 * Note that the caller is not permitted to immediately free
151 * the newly deleted entry. Instead, either synchronize_rcu()
152 * or call_rcu() must be used to defer freeing until an RCU
153 * grace period has elapsed.
154 */
155static inline void list_del_rcu(struct list_head *entry)
156{
Dave Jones559f9ba2012-03-14 22:17:39 -0400157 __list_del_entry(entry);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200158 entry->prev = LIST_POISON2;
159}
160
161/**
Andrea Arcangeli6beeac72008-07-28 15:46:22 -0700162 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
163 * @n: the element to delete from the hash list.
164 *
165 * Note: list_unhashed() on the node return true after this. It is
166 * useful for RCU based read lockfree traversal if the writer side
167 * must know if the list entry is still hashed or already unhashed.
168 *
169 * In particular, it means that we can not poison the forward pointers
170 * that may still be used for walking the hash list and we can only
171 * zero the pprev pointer so list_unhashed() will return true after
172 * this.
173 *
174 * The caller must take whatever precautions are necessary (such as
175 * holding appropriate locks) to avoid racing with another
176 * list-mutation primitive, such as hlist_add_head_rcu() or
177 * hlist_del_rcu(), running on this same list. However, it is
178 * perfectly legal to run concurrently with the _rcu list-traversal
179 * primitives, such as hlist_for_each_entry_rcu().
180 */
181static inline void hlist_del_init_rcu(struct hlist_node *n)
182{
183 if (!hlist_unhashed(n)) {
184 __hlist_del(n);
Eric Dumazetc54a2742019-11-07 11:37:37 -0800185 WRITE_ONCE(n->pprev, NULL);
Andrea Arcangeli6beeac72008-07-28 15:46:22 -0700186 }
187}
188
189/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200190 * list_replace_rcu - replace old entry by new one
191 * @old : the element to be replaced
192 * @new : the new element to insert
193 *
194 * The @old entry will be replaced with the @new entry atomically.
195 * Note: @old should not be empty.
196 */
197static inline void list_replace_rcu(struct list_head *old,
198 struct list_head *new)
199{
200 new->next = old->next;
201 new->prev = old->prev;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100202 rcu_assign_pointer(list_next_rcu(new->prev), new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200203 new->next->prev = new;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200204 old->prev = LIST_POISON2;
205}
206
207/**
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300208 * __list_splice_init_rcu - join an RCU-protected list into an existing list.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200209 * @list: the RCU-protected list to splice
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300210 * @prev: points to the last element of the existing list
211 * @next: points to the first element of the existing list
Paul E. McKenneyaff5f032018-07-07 18:12:26 -0700212 * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
Franck Bui-Huu82524742008-05-12 21:21:05 +0200213 *
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300214 * The list pointed to by @prev and @next can be RCU-read traversed
215 * concurrently with this function.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200216 *
217 * Note that this function blocks.
218 *
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300219 * Important note: the caller must take whatever action is necessary to prevent
220 * any other updates to the existing list. In principle, it is possible to
221 * modify the list as soon as sync() begins execution. If this sort of thing
222 * becomes necessary, an alternative version based on call_rcu() could be
223 * created. But only if -really- needed -- there is no shortage of RCU API
224 * members.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200225 */
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300226static inline void __list_splice_init_rcu(struct list_head *list,
227 struct list_head *prev,
228 struct list_head *next,
229 void (*sync)(void))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200230{
231 struct list_head *first = list->next;
232 struct list_head *last = list->prev;
Franck Bui-Huu82524742008-05-12 21:21:05 +0200233
Paul E. McKenney2a855b62013-08-23 09:40:42 -0700234 /*
235 * "first" and "last" tracking list, so initialize it. RCU readers
236 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
237 * instead of INIT_LIST_HEAD().
238 */
Franck Bui-Huu82524742008-05-12 21:21:05 +0200239
Paul E. McKenney2a855b62013-08-23 09:40:42 -0700240 INIT_LIST_HEAD_RCU(list);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200241
242 /*
243 * At this point, the list body still points to the source list.
244 * Wait for any readers to finish using the list before splicing
245 * the list body into the new list. Any new readers will see
246 * an empty list.
247 */
248
249 sync();
Paul E. McKenneyc93773c2020-02-12 13:29:15 -0800250 ASSERT_EXCLUSIVE_ACCESS(*first);
251 ASSERT_EXCLUSIVE_ACCESS(*last);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200252
253 /*
254 * Readers are finished with the source list, so perform splice.
255 * The order is important if the new list is global and accessible
256 * to concurrent RCU readers. Note that RCU readers are not
257 * permitted to traverse the prev pointers without excluding
258 * this function.
259 */
260
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300261 last->next = next;
262 rcu_assign_pointer(list_next_rcu(prev), first);
263 first->prev = prev;
264 next->prev = last;
265}
266
267/**
268 * list_splice_init_rcu - splice an RCU-protected list into an existing list,
269 * designed for stacks.
270 * @list: the RCU-protected list to splice
271 * @head: the place in the existing list to splice the first list into
Paul E. McKenneyaff5f032018-07-07 18:12:26 -0700272 * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300273 */
274static inline void list_splice_init_rcu(struct list_head *list,
275 struct list_head *head,
276 void (*sync)(void))
277{
278 if (!list_empty(list))
279 __list_splice_init_rcu(list, head, head->next, sync);
280}
281
282/**
283 * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
284 * list, designed for queues.
285 * @list: the RCU-protected list to splice
286 * @head: the place in the existing list to splice the first list into
Paul E. McKenneyaff5f032018-07-07 18:12:26 -0700287 * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
Petko Manolov7d86dcc2015-10-12 18:23:51 +0300288 */
289static inline void list_splice_tail_init_rcu(struct list_head *list,
290 struct list_head *head,
291 void (*sync)(void))
292{
293 if (!list_empty(list))
294 __list_splice_init_rcu(list, head->prev, head, sync);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200295}
296
Jiri Pirko72c6a982009-04-14 17:33:57 +0200297/**
298 * list_entry_rcu - get the struct for this entry
299 * @ptr: the &struct list_head pointer.
300 * @type: the type of the struct this is embedded in.
Andrey Utkin3943f422014-11-14 05:09:55 +0400301 * @member: the name of the list_head within the struct.
Jiri Pirko72c6a982009-04-14 17:33:57 +0200302 *
303 * This primitive may safely run concurrently with the _rcu list-mutation
304 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
305 */
306#define list_entry_rcu(ptr, type, member) \
Will Deacon506458e2017-10-24 11:22:48 +0100307 container_of(READ_ONCE(ptr), type, member)
Jiri Pirko72c6a982009-04-14 17:33:57 +0200308
Paul E. McKenney27fdb352017-10-19 14:26:21 -0700309/*
Michel Machadof88022a2012-04-10 14:07:40 -0400310 * Where are list_empty_rcu() and list_first_entry_rcu()?
311 *
Julian Wiedmann751b1712021-05-21 12:08:29 +0200312 * They do not exist because they would lead to subtle race conditions:
Michel Machadof88022a2012-04-10 14:07:40 -0400313 *
314 * if (!list_empty_rcu(mylist)) {
315 * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
316 * do_something(bar);
317 * }
318 *
Julian Wiedmann751b1712021-05-21 12:08:29 +0200319 * The list might be non-empty when list_empty_rcu() checks it, but it
320 * might have become empty by the time that list_first_entry_rcu() rereads
321 * the ->next pointer, which would result in a SEGV.
Michel Machadof88022a2012-04-10 14:07:40 -0400322 *
Julian Wiedmann751b1712021-05-21 12:08:29 +0200323 * When not using RCU, it is OK for list_first_entry() to re-read that
324 * pointer because both functions should be protected by some lock that
325 * blocks writers.
326 *
327 * When using RCU, list_empty() uses READ_ONCE() to fetch the
328 * RCU-protected ->next pointer and then compares it to the address of the
329 * list head. However, it neither dereferences this pointer nor provides
330 * this pointer to its caller. Thus, READ_ONCE() suffices (that is,
331 * rcu_dereference() is not needed), which means that list_empty() can be
332 * used anywhere you would want to use list_empty_rcu(). Just don't
333 * expect anything useful to happen if you do a subsequent lockless
334 * call to list_first_entry_rcu()!!!
Michel Machadof88022a2012-04-10 14:07:40 -0400335 *
336 * See list_first_or_null_rcu for an alternative.
337 */
338
339/**
340 * list_first_or_null_rcu - get the first element from a list
Jiri Pirko72c6a982009-04-14 17:33:57 +0200341 * @ptr: the list head to take the element from.
342 * @type: the type of the struct this is embedded in.
Andrey Utkin3943f422014-11-14 05:09:55 +0400343 * @member: the name of the list_head within the struct.
Jiri Pirko72c6a982009-04-14 17:33:57 +0200344 *
Michel Machadof88022a2012-04-10 14:07:40 -0400345 * Note that if the list is empty, it returns NULL.
Jiri Pirko72c6a982009-04-14 17:33:57 +0200346 *
347 * This primitive may safely run concurrently with the _rcu list-mutation
348 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
349 */
Michel Machadof88022a2012-04-10 14:07:40 -0400350#define list_first_or_null_rcu(ptr, type, member) \
Joe Perches0adab9b2013-12-05 16:19:15 -0800351({ \
352 struct list_head *__ptr = (ptr); \
Paul E. McKenney7d0ae802015-03-03 14:57:58 -0800353 struct list_head *__next = READ_ONCE(__ptr->next); \
Joe Perches0adab9b2013-12-05 16:19:15 -0800354 likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
355})
Jiri Pirko72c6a982009-04-14 17:33:57 +0200356
Franck Bui-Huu82524742008-05-12 21:21:05 +0200357/**
Tom Herbertff3c44e2016-03-07 14:11:00 -0800358 * list_next_or_null_rcu - get the first element from a list
359 * @head: the head for the list.
360 * @ptr: the list head to take the next element from.
361 * @type: the type of the struct this is embedded in.
362 * @member: the name of the list_head within the struct.
363 *
364 * Note that if the ptr is at the end of the list, NULL is returned.
365 *
366 * This primitive may safely run concurrently with the _rcu list-mutation
367 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
368 */
369#define list_next_or_null_rcu(head, ptr, type, member) \
370({ \
371 struct list_head *__head = (head); \
372 struct list_head *__ptr = (ptr); \
373 struct list_head *__next = READ_ONCE(__ptr->next); \
374 likely(__next != __head) ? list_entry_rcu(__next, type, \
375 member) : NULL; \
376})
377
378/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200379 * list_for_each_entry_rcu - iterate over rcu list of given type
380 * @pos: the type * to use as a loop cursor.
381 * @head: the head for your list.
Andrey Utkin3943f422014-11-14 05:09:55 +0400382 * @member: the name of the list_head within the struct.
Jonathan Neuschäferddc465932020-03-05 23:22:55 +0100383 * @cond: optional lockdep expression if called from non-RCU protection.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200384 *
385 * This list-traversal primitive may safely run concurrently with
386 * the _rcu list-mutation primitives such as list_add_rcu()
387 * as long as the traversal is guarded by rcu_read_lock().
388 */
Joel Fernandes (Google)28875942019-07-16 18:12:22 -0400389#define list_for_each_entry_rcu(pos, head, member, cond...) \
390 for (__list_check_rcu(dummy, ## cond, 0), \
391 pos = list_entry_rcu((head)->next, typeof(*pos), member); \
392 &pos->member != (head); \
Jiri Pirko72c6a982009-04-14 17:33:57 +0200393 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200394
Franck Bui-Huu82524742008-05-12 21:21:05 +0200395/**
Madhuparna Bhowmikae2212a2020-07-12 18:40:02 +0530396 * list_for_each_entry_srcu - iterate over rcu list of given type
397 * @pos: the type * to use as a loop cursor.
398 * @head: the head for your list.
399 * @member: the name of the list_head within the struct.
400 * @cond: lockdep expression for the lock required to traverse the list.
401 *
402 * This list-traversal primitive may safely run concurrently with
403 * the _rcu list-mutation primitives such as list_add_rcu()
404 * as long as the traversal is guarded by srcu_read_lock().
405 * The lockdep expression srcu_read_lock_held() can be passed as the
406 * cond argument from read side.
407 */
408#define list_for_each_entry_srcu(pos, head, member, cond) \
409 for (__list_check_srcu(cond), \
410 pos = list_entry_rcu((head)->next, typeof(*pos), member); \
411 &pos->member != (head); \
412 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
413
414/**
Alexey Kardashevskiy69b90722015-12-05 18:14:19 -0800415 * list_entry_lockless - get the struct for this entry
416 * @ptr: the &struct list_head pointer.
417 * @type: the type of the struct this is embedded in.
418 * @member: the name of the list_head within the struct.
419 *
Paul E. McKenneyaff5f032018-07-07 18:12:26 -0700420 * This primitive may safely run concurrently with the _rcu
421 * list-mutation primitives such as list_add_rcu(), but requires some
422 * implicit RCU read-side guarding. One example is running within a special
423 * exception-time environment where preemption is disabled and where lockdep
424 * cannot be invoked. Another example is when items are added to the list,
425 * but never deleted.
Alexey Kardashevskiy69b90722015-12-05 18:14:19 -0800426 */
427#define list_entry_lockless(ptr, type, member) \
Will Deacon506458e2017-10-24 11:22:48 +0100428 container_of((typeof(ptr))READ_ONCE(ptr), type, member)
Alexey Kardashevskiy69b90722015-12-05 18:14:19 -0800429
430/**
431 * list_for_each_entry_lockless - iterate over rcu list of given type
432 * @pos: the type * to use as a loop cursor.
433 * @head: the head for your list.
434 * @member: the name of the list_struct within the struct.
435 *
Paul E. McKenneyaff5f032018-07-07 18:12:26 -0700436 * This primitive may safely run concurrently with the _rcu
437 * list-mutation primitives such as list_add_rcu(), but requires some
438 * implicit RCU read-side guarding. One example is running within a special
439 * exception-time environment where preemption is disabled and where lockdep
440 * cannot be invoked. Another example is when items are added to the list,
441 * but never deleted.
Alexey Kardashevskiy69b90722015-12-05 18:14:19 -0800442 */
443#define list_for_each_entry_lockless(pos, head, member) \
444 for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
445 &pos->member != (head); \
446 pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
447
448/**
stephen hemminger254245d2009-11-10 07:54:47 +0000449 * list_for_each_entry_continue_rcu - continue iteration over list of given type
450 * @pos: the type * to use as a loop cursor.
451 * @head: the head for your list.
Andrey Utkin3943f422014-11-14 05:09:55 +0400452 * @member: the name of the list_head within the struct.
stephen hemminger254245d2009-11-10 07:54:47 +0000453 *
454 * Continue to iterate over list of given type, continuing after
NeilBrownb7b6f942018-06-18 14:22:40 +1000455 * the current position which must have been in the list when the RCU read
456 * lock was taken.
457 * This would typically require either that you obtained the node from a
458 * previous walk of the list in the same RCU read-side critical section, or
459 * that you held some sort of non-RCU reference (such as a reference count)
460 * to keep the node alive *and* in the list.
461 *
462 * This iterator is similar to list_for_each_entry_from_rcu() except
463 * this starts after the given position and that one starts at the given
464 * position.
stephen hemminger254245d2009-11-10 07:54:47 +0000465 */
466#define list_for_each_entry_continue_rcu(pos, head, member) \
467 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
Linus Torvaldse66eed62011-05-19 14:15:29 -0700468 &pos->member != (head); \
stephen hemminger254245d2009-11-10 07:54:47 +0000469 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
470
471/**
NeilBrownead9ad72018-04-30 14:31:30 +1000472 * list_for_each_entry_from_rcu - iterate over a list from current point
473 * @pos: the type * to use as a loop cursor.
474 * @head: the head for your list.
475 * @member: the name of the list_node within the struct.
476 *
477 * Iterate over the tail of a list starting from a given position,
478 * which must have been in the list when the RCU read lock was taken.
NeilBrownb7b6f942018-06-18 14:22:40 +1000479 * This would typically require either that you obtained the node from a
480 * previous walk of the list in the same RCU read-side critical section, or
481 * that you held some sort of non-RCU reference (such as a reference count)
482 * to keep the node alive *and* in the list.
483 *
484 * This iterator is similar to list_for_each_entry_continue_rcu() except
485 * this starts from the given position and that one starts from the position
486 * after the given position.
NeilBrownead9ad72018-04-30 14:31:30 +1000487 */
488#define list_for_each_entry_from_rcu(pos, head, member) \
489 for (; &(pos)->member != (head); \
490 pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
491
492/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200493 * hlist_del_rcu - deletes entry from hash list without re-initialization
494 * @n: the element to delete from the hash list.
495 *
496 * Note: list_unhashed() on entry does not return true after this,
497 * the entry is in an undefined state. It is useful for RCU based
498 * lockfree traversal.
499 *
500 * In particular, it means that we can not poison the forward
501 * pointers that may still be used for walking the hash list.
502 *
503 * The caller must take whatever precautions are necessary
504 * (such as holding appropriate locks) to avoid racing
505 * with another list-mutation primitive, such as hlist_add_head_rcu()
506 * or hlist_del_rcu(), running on this same list.
507 * However, it is perfectly legal to run concurrently with
508 * the _rcu list-traversal primitives, such as
509 * hlist_for_each_entry().
510 */
511static inline void hlist_del_rcu(struct hlist_node *n)
512{
513 __hlist_del(n);
Eric Dumazetc54a2742019-11-07 11:37:37 -0800514 WRITE_ONCE(n->pprev, LIST_POISON2);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200515}
516
517/**
518 * hlist_replace_rcu - replace old entry by new one
519 * @old : the element to be replaced
520 * @new : the new element to insert
521 *
522 * The @old entry will be replaced with the @new entry atomically.
523 */
524static inline void hlist_replace_rcu(struct hlist_node *old,
525 struct hlist_node *new)
526{
527 struct hlist_node *next = old->next;
528
529 new->next = next;
Eric Dumazetc54a2742019-11-07 11:37:37 -0800530 WRITE_ONCE(new->pprev, old->pprev);
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100531 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200532 if (next)
Eric Dumazetc54a2742019-11-07 11:37:37 -0800533 WRITE_ONCE(new->next->pprev, &new->next);
534 WRITE_ONCE(old->pprev, LIST_POISON2);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200535}
536
Eric W. Biederman35fc0e32020-04-24 11:19:10 -0500537/**
538 * hlists_swap_heads_rcu - swap the lists the hlist heads point to
539 * @left: The hlist head on the left
540 * @right: The hlist head on the right
541 *
542 * The lists start out as [@left ][node1 ... ] and
Mauro Carvalho Chehab24692fa2020-06-15 08:46:49 +0200543 * [@right ][node2 ... ]
Eric W. Biederman35fc0e32020-04-24 11:19:10 -0500544 * The lists end up as [@left ][node2 ... ]
545 * [@right ][node1 ... ]
546 */
547static inline void hlists_swap_heads_rcu(struct hlist_head *left, struct hlist_head *right)
548{
549 struct hlist_node *node1 = left->first;
550 struct hlist_node *node2 = right->first;
551
552 rcu_assign_pointer(left->first, node2);
553 rcu_assign_pointer(right->first, node1);
554 WRITE_ONCE(node2->pprev, &left->first);
555 WRITE_ONCE(node1->pprev, &right->first);
556}
557
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100558/*
559 * return the first or the next element in an RCU protected hlist
560 */
561#define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
562#define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
563#define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
564
Franck Bui-Huu82524742008-05-12 21:21:05 +0200565/**
566 * hlist_add_head_rcu
567 * @n: the element to add to the hash list.
568 * @h: the list to add to.
569 *
570 * Description:
571 * Adds the specified element to the specified hlist,
572 * while permitting racing traversals.
573 *
574 * The caller must take whatever precautions are necessary
575 * (such as holding appropriate locks) to avoid racing
576 * with another list-mutation primitive, such as hlist_add_head_rcu()
577 * or hlist_del_rcu(), running on this same list.
578 * However, it is perfectly legal to run concurrently with
579 * the _rcu list-traversal primitives, such as
580 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
581 * problems on Alpha CPUs. Regardless of the type of CPU, the
582 * list-traversal primitive must be guarded by rcu_read_lock().
583 */
584static inline void hlist_add_head_rcu(struct hlist_node *n,
585 struct hlist_head *h)
586{
587 struct hlist_node *first = h->first;
Franck Bui-Huu10aa9d22008-05-12 21:21:06 +0200588
Franck Bui-Huu82524742008-05-12 21:21:05 +0200589 n->next = first;
Eric Dumazetc54a2742019-11-07 11:37:37 -0800590 WRITE_ONCE(n->pprev, &h->first);
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100591 rcu_assign_pointer(hlist_first_rcu(h), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200592 if (first)
Eric Dumazetc54a2742019-11-07 11:37:37 -0800593 WRITE_ONCE(first->pprev, &n->next);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200594}
595
596/**
David S. Miller1602f492016-04-23 18:26:24 -0400597 * hlist_add_tail_rcu
598 * @n: the element to add to the hash list.
599 * @h: the list to add to.
600 *
601 * Description:
602 * Adds the specified element to the specified hlist,
603 * while permitting racing traversals.
604 *
605 * The caller must take whatever precautions are necessary
606 * (such as holding appropriate locks) to avoid racing
607 * with another list-mutation primitive, such as hlist_add_head_rcu()
608 * or hlist_del_rcu(), running on this same list.
609 * However, it is perfectly legal to run concurrently with
610 * the _rcu list-traversal primitives, such as
611 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
612 * problems on Alpha CPUs. Regardless of the type of CPU, the
613 * list-traversal primitive must be guarded by rcu_read_lock().
614 */
615static inline void hlist_add_tail_rcu(struct hlist_node *n,
616 struct hlist_head *h)
617{
618 struct hlist_node *i, *last = NULL;
619
Michael S. Tsirkin48ac3462017-02-27 21:14:19 +0200620 /* Note: write side code, so rcu accessors are not needed. */
621 for (i = h->first; i; i = i->next)
David S. Miller1602f492016-04-23 18:26:24 -0400622 last = i;
623
624 if (last) {
625 n->next = last->next;
Eric Dumazetc54a2742019-11-07 11:37:37 -0800626 WRITE_ONCE(n->pprev, &last->next);
David S. Miller1602f492016-04-23 18:26:24 -0400627 rcu_assign_pointer(hlist_next_rcu(last), n);
628 } else {
629 hlist_add_head_rcu(n, h);
630 }
631}
632
633/**
Franck Bui-Huu82524742008-05-12 21:21:05 +0200634 * hlist_add_before_rcu
635 * @n: the new element to add to the hash list.
636 * @next: the existing element to add the new element before.
637 *
638 * Description:
639 * Adds the specified element to the specified hlist
640 * before the specified node while permitting racing traversals.
641 *
642 * The caller must take whatever precautions are necessary
643 * (such as holding appropriate locks) to avoid racing
644 * with another list-mutation primitive, such as hlist_add_head_rcu()
645 * or hlist_del_rcu(), running on this same list.
646 * However, it is perfectly legal to run concurrently with
647 * the _rcu list-traversal primitives, such as
648 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
649 * problems on Alpha CPUs.
650 */
651static inline void hlist_add_before_rcu(struct hlist_node *n,
652 struct hlist_node *next)
653{
Eric Dumazetc54a2742019-11-07 11:37:37 -0800654 WRITE_ONCE(n->pprev, next->pprev);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200655 n->next = next;
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100656 rcu_assign_pointer(hlist_pprev_rcu(n), n);
Eric Dumazetc54a2742019-11-07 11:37:37 -0800657 WRITE_ONCE(next->pprev, &n->next);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200658}
659
660/**
Ken Helias1d023282014-08-06 16:09:16 -0700661 * hlist_add_behind_rcu
Franck Bui-Huu82524742008-05-12 21:21:05 +0200662 * @n: the new element to add to the hash list.
Ken Helias1d023282014-08-06 16:09:16 -0700663 * @prev: the existing element to add the new element after.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200664 *
665 * Description:
666 * Adds the specified element to the specified hlist
667 * after the specified node while permitting racing traversals.
668 *
669 * The caller must take whatever precautions are necessary
670 * (such as holding appropriate locks) to avoid racing
671 * with another list-mutation primitive, such as hlist_add_head_rcu()
672 * or hlist_del_rcu(), running on this same list.
673 * However, it is perfectly legal to run concurrently with
674 * the _rcu list-traversal primitives, such as
675 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
676 * problems on Alpha CPUs.
677 */
Ken Helias1d023282014-08-06 16:09:16 -0700678static inline void hlist_add_behind_rcu(struct hlist_node *n,
679 struct hlist_node *prev)
Franck Bui-Huu82524742008-05-12 21:21:05 +0200680{
681 n->next = prev->next;
Eric Dumazetc54a2742019-11-07 11:37:37 -0800682 WRITE_ONCE(n->pprev, &prev->next);
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100683 rcu_assign_pointer(hlist_next_rcu(prev), n);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200684 if (n->next)
Eric Dumazetc54a2742019-11-07 11:37:37 -0800685 WRITE_ONCE(n->next->pprev, &n->next);
Franck Bui-Huu82524742008-05-12 21:21:05 +0200686}
687
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100688#define __hlist_for_each_rcu(pos, head) \
689 for (pos = rcu_dereference(hlist_first_rcu(head)); \
Linus Torvalds75d65a42011-05-19 13:50:07 -0700690 pos; \
Arnd Bergmann67bdbff2010-02-25 16:55:13 +0100691 pos = rcu_dereference(hlist_next_rcu(pos)))
stephen hemminger1cc52322010-02-22 07:57:17 +0000692
Franck Bui-Huu82524742008-05-12 21:21:05 +0200693/**
694 * hlist_for_each_entry_rcu - iterate over rcu list of given type
Sasha Levinb67bfe02013-02-27 17:06:00 -0800695 * @pos: the type * to use as a loop cursor.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200696 * @head: the head for your list.
697 * @member: the name of the hlist_node within the struct.
Jonathan Neuschäferddc465932020-03-05 23:22:55 +0100698 * @cond: optional lockdep expression if called from non-RCU protection.
Franck Bui-Huu82524742008-05-12 21:21:05 +0200699 *
700 * This list-traversal primitive may safely run concurrently with
701 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
702 * as long as the traversal is guarded by rcu_read_lock().
703 */
Joel Fernandes (Google)28875942019-07-16 18:12:22 -0400704#define hlist_for_each_entry_rcu(pos, head, member, cond...) \
705 for (__list_check_rcu(dummy, ## cond, 0), \
706 pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
Sasha Levinb67bfe02013-02-27 17:06:00 -0800707 typeof(*(pos)), member); \
708 pos; \
709 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
710 &(pos)->member)), typeof(*(pos)), member))
Franck Bui-Huu82524742008-05-12 21:21:05 +0200711
stephen hemminger5c578aed2010-03-17 20:31:11 +0000712/**
Madhuparna Bhowmikae2212a2020-07-12 18:40:02 +0530713 * hlist_for_each_entry_srcu - iterate over rcu list of given type
714 * @pos: the type * to use as a loop cursor.
715 * @head: the head for your list.
716 * @member: the name of the hlist_node within the struct.
717 * @cond: lockdep expression for the lock required to traverse the list.
718 *
719 * This list-traversal primitive may safely run concurrently with
720 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
721 * as long as the traversal is guarded by srcu_read_lock().
722 * The lockdep expression srcu_read_lock_held() can be passed as the
723 * cond argument from read side.
724 */
725#define hlist_for_each_entry_srcu(pos, head, member, cond) \
726 for (__list_check_srcu(cond), \
727 pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
728 typeof(*(pos)), member); \
729 pos; \
730 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
731 &(pos)->member)), typeof(*(pos)), member))
732
733/**
Steven Rostedt12bcbe62013-05-28 14:38:42 -0400734 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
735 * @pos: the type * to use as a loop cursor.
736 * @head: the head for your list.
737 * @member: the name of the hlist_node within the struct.
738 *
739 * This list-traversal primitive may safely run concurrently with
740 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
741 * as long as the traversal is guarded by rcu_read_lock().
742 *
743 * This is the same as hlist_for_each_entry_rcu() except that it does
744 * not do any RCU debugging or tracing.
745 */
746#define hlist_for_each_entry_rcu_notrace(pos, head, member) \
Joel Fernandes (Google)0a5b99f2019-07-11 16:45:41 -0400747 for (pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_first_rcu(head)),\
Steven Rostedt12bcbe62013-05-28 14:38:42 -0400748 typeof(*(pos)), member); \
749 pos; \
Joel Fernandes (Google)0a5b99f2019-07-11 16:45:41 -0400750 pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_next_rcu(\
Steven Rostedt12bcbe62013-05-28 14:38:42 -0400751 &(pos)->member)), typeof(*(pos)), member))
752
753/**
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000754 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
Sasha Levinb67bfe02013-02-27 17:06:00 -0800755 * @pos: the type * to use as a loop cursor.
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000756 * @head: the head for your list.
757 * @member: the name of the hlist_node within the struct.
758 *
759 * This list-traversal primitive may safely run concurrently with
760 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
761 * as long as the traversal is guarded by rcu_read_lock().
762 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800763#define hlist_for_each_entry_rcu_bh(pos, head, member) \
764 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
765 typeof(*(pos)), member); \
766 pos; \
767 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
768 &(pos)->member)), typeof(*(pos)), member))
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000769
770/**
stephen hemminger5c578aed2010-03-17 20:31:11 +0000771 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
Sasha Levinb67bfe02013-02-27 17:06:00 -0800772 * @pos: the type * to use as a loop cursor.
stephen hemminger5c578aed2010-03-17 20:31:11 +0000773 * @member: the name of the hlist_node within the struct.
774 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800775#define hlist_for_each_entry_continue_rcu(pos, member) \
Ying Xuef520c982014-12-12 09:36:14 +0800776 for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
777 &(pos)->member)), typeof(*(pos)), member); \
Sasha Levinb67bfe02013-02-27 17:06:00 -0800778 pos; \
Ying Xuef520c982014-12-12 09:36:14 +0800779 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
780 &(pos)->member)), typeof(*(pos)), member))
stephen hemminger5c578aed2010-03-17 20:31:11 +0000781
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000782/**
783 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
Sasha Levinb67bfe02013-02-27 17:06:00 -0800784 * @pos: the type * to use as a loop cursor.
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000785 * @member: the name of the hlist_node within the struct.
786 */
Sasha Levinb67bfe02013-02-27 17:06:00 -0800787#define hlist_for_each_entry_continue_rcu_bh(pos, member) \
Ying Xuef520c982014-12-12 09:36:14 +0800788 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
789 &(pos)->member)), typeof(*(pos)), member); \
Sasha Levinb67bfe02013-02-27 17:06:00 -0800790 pos; \
Ying Xuef520c982014-12-12 09:36:14 +0800791 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
792 &(pos)->member)), typeof(*(pos)), member))
Eric Dumazet4f70ecc2010-05-03 10:50:14 +0000793
Ying Xue97ede292014-12-02 15:00:30 +0800794/**
795 * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
796 * @pos: the type * to use as a loop cursor.
797 * @member: the name of the hlist_node within the struct.
798 */
799#define hlist_for_each_entry_from_rcu(pos, member) \
800 for (; pos; \
Ying Xuef5177002015-03-26 13:27:08 +0800801 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
802 &(pos)->member)), typeof(*(pos)), member))
stephen hemminger5c578aed2010-03-17 20:31:11 +0000803
Franck Bui-Huu82524742008-05-12 21:21:05 +0200804#endif /* __KERNEL__ */
805#endif