1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef _LINUX_RCULIST_H
3 #define _LINUX_RCULIST_H
8 * RCU-protected list version
10 #include <linux/list.h>
11 #include <linux/rcupdate.h>
14 * Why is there no list_empty_rcu()? Because list_empty() serves this
15 * purpose. The list_empty() function fetches the RCU-protected pointer
16 * and compares it to the address of the list head, but neither dereferences
17 * this pointer itself nor provides this pointer to the caller. Therefore,
18 * it is not necessary to use rcu_dereference(), so that list_empty() can
19 * be used anywhere you would want to use a list_empty_rcu().
23 * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
24 * @list: list to be initialized
26 * You should instead use INIT_LIST_HEAD() for normal initialization and
27 * cleanup tasks, when readers have no access to the list being initialized.
28 * However, if the list being initialized is visible to readers, you
29 * need to keep the compiler from being too mischievous.
31 static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
33 WRITE_ONCE(list->next, list);
34 WRITE_ONCE(list->prev, list);
38 * return the ->next pointer of a list_head in an rcu safe
39 * way, we must not access it directly
41 #define list_next_rcu(list) (*((struct list_head __rcu **)(&(list)->next)))
44 * Insert a new entry between two known consecutive entries.
46 * This is only for internal list manipulation where we know
47 * the prev/next entries already!
49 static inline void __list_add_rcu(struct list_head *new,
50 struct list_head *prev, struct list_head *next)
52 if (!__list_add_valid(new, prev, next))
57 rcu_assign_pointer(list_next_rcu(prev), new);
62 * list_add_rcu - add a new entry to rcu-protected list
63 * @new: new entry to be added
64 * @head: list head to add it after
66 * Insert a new entry after the specified head.
67 * This is good for implementing stacks.
69 * The caller must take whatever precautions are necessary
70 * (such as holding appropriate locks) to avoid racing
71 * with another list-mutation primitive, such as list_add_rcu()
72 * or list_del_rcu(), running on this same list.
73 * However, it is perfectly legal to run concurrently with
74 * the _rcu list-traversal primitives, such as
75 * list_for_each_entry_rcu().
77 static inline void list_add_rcu(struct list_head *new, struct list_head *head)
79 __list_add_rcu(new, head, head->next);
83 * list_add_tail_rcu - add a new entry to rcu-protected list
84 * @new: new entry to be added
85 * @head: list head to add it before
87 * Insert a new entry before the specified head.
88 * This is useful for implementing queues.
90 * The caller must take whatever precautions are necessary
91 * (such as holding appropriate locks) to avoid racing
92 * with another list-mutation primitive, such as list_add_tail_rcu()
93 * or list_del_rcu(), running on this same list.
94 * However, it is perfectly legal to run concurrently with
95 * the _rcu list-traversal primitives, such as
96 * list_for_each_entry_rcu().
98 static inline void list_add_tail_rcu(struct list_head *new,
99 struct list_head *head)
101 __list_add_rcu(new, head->prev, head);
105 * list_del_rcu - deletes entry from list without re-initialization
106 * @entry: the element to delete from the list.
108 * Note: list_empty() on entry does not return true after this,
109 * the entry is in an undefined state. It is useful for RCU based
110 * lockfree traversal.
112 * In particular, it means that we can not poison the forward
113 * pointers that may still be used for walking the list.
115 * The caller must take whatever precautions are necessary
116 * (such as holding appropriate locks) to avoid racing
117 * with another list-mutation primitive, such as list_del_rcu()
118 * or list_add_rcu(), running on this same list.
119 * However, it is perfectly legal to run concurrently with
120 * the _rcu list-traversal primitives, such as
121 * list_for_each_entry_rcu().
123 * Note that the caller is not permitted to immediately free
124 * the newly deleted entry. Instead, either synchronize_rcu()
125 * or call_rcu() must be used to defer freeing until an RCU
126 * grace period has elapsed.
128 static inline void list_del_rcu(struct list_head *entry)
130 __list_del_entry(entry);
131 entry->prev = LIST_POISON2;
135 * hlist_del_init_rcu - deletes entry from hash list with re-initialization
136 * @n: the element to delete from the hash list.
138 * Note: list_unhashed() on the node return true after this. It is
139 * useful for RCU based read lockfree traversal if the writer side
140 * must know if the list entry is still hashed or already unhashed.
142 * In particular, it means that we can not poison the forward pointers
143 * that may still be used for walking the hash list and we can only
144 * zero the pprev pointer so list_unhashed() will return true after
147 * The caller must take whatever precautions are necessary (such as
148 * holding appropriate locks) to avoid racing with another
149 * list-mutation primitive, such as hlist_add_head_rcu() or
150 * hlist_del_rcu(), running on this same list. However, it is
151 * perfectly legal to run concurrently with the _rcu list-traversal
152 * primitives, such as hlist_for_each_entry_rcu().
154 static inline void hlist_del_init_rcu(struct hlist_node *n)
156 if (!hlist_unhashed(n)) {
163 * list_replace_rcu - replace old entry by new one
164 * @old : the element to be replaced
165 * @new : the new element to insert
167 * The @old entry will be replaced with the @new entry atomically.
168 * Note: @old should not be empty.
170 static inline void list_replace_rcu(struct list_head *old,
171 struct list_head *new)
173 new->next = old->next;
174 new->prev = old->prev;
175 rcu_assign_pointer(list_next_rcu(new->prev), new);
176 new->next->prev = new;
177 old->prev = LIST_POISON2;
181 * __list_splice_init_rcu - join an RCU-protected list into an existing list.
182 * @list: the RCU-protected list to splice
183 * @prev: points to the last element of the existing list
184 * @next: points to the first element of the existing list
185 * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
187 * The list pointed to by @prev and @next can be RCU-read traversed
188 * concurrently with this function.
190 * Note that this function blocks.
192 * Important note: the caller must take whatever action is necessary to prevent
193 * any other updates to the existing list. In principle, it is possible to
194 * modify the list as soon as sync() begins execution. If this sort of thing
195 * becomes necessary, an alternative version based on call_rcu() could be
196 * created. But only if -really- needed -- there is no shortage of RCU API
199 static inline void __list_splice_init_rcu(struct list_head *list,
200 struct list_head *prev,
201 struct list_head *next,
204 struct list_head *first = list->next;
205 struct list_head *last = list->prev;
208 * "first" and "last" tracking list, so initialize it. RCU readers
209 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
210 * instead of INIT_LIST_HEAD().
213 INIT_LIST_HEAD_RCU(list);
216 * At this point, the list body still points to the source list.
217 * Wait for any readers to finish using the list before splicing
218 * the list body into the new list. Any new readers will see
225 * Readers are finished with the source list, so perform splice.
226 * The order is important if the new list is global and accessible
227 * to concurrent RCU readers. Note that RCU readers are not
228 * permitted to traverse the prev pointers without excluding
233 rcu_assign_pointer(list_next_rcu(prev), first);
239 * list_splice_init_rcu - splice an RCU-protected list into an existing list,
240 * designed for stacks.
241 * @list: the RCU-protected list to splice
242 * @head: the place in the existing list to splice the first list into
243 * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
245 static inline void list_splice_init_rcu(struct list_head *list,
246 struct list_head *head,
249 if (!list_empty(list))
250 __list_splice_init_rcu(list, head, head->next, sync);
254 * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
255 * list, designed for queues.
256 * @list: the RCU-protected list to splice
257 * @head: the place in the existing list to splice the first list into
258 * @sync: synchronize_rcu, synchronize_rcu_expedited, ...
260 static inline void list_splice_tail_init_rcu(struct list_head *list,
261 struct list_head *head,
264 if (!list_empty(list))
265 __list_splice_init_rcu(list, head->prev, head, sync);
269 * list_entry_rcu - get the struct for this entry
270 * @ptr: the &struct list_head pointer.
271 * @type: the type of the struct this is embedded in.
272 * @member: the name of the list_head within the struct.
274 * This primitive may safely run concurrently with the _rcu list-mutation
275 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
277 #define list_entry_rcu(ptr, type, member) \
278 container_of(READ_ONCE(ptr), type, member)
281 * Where are list_empty_rcu() and list_first_entry_rcu()?
283 * Implementing those functions following their counterparts list_empty() and
284 * list_first_entry() is not advisable because they lead to subtle race
285 * conditions as the following snippet shows:
287 * if (!list_empty_rcu(mylist)) {
288 * struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
292 * The list may not be empty when list_empty_rcu checks it, but it may be when
293 * list_first_entry_rcu rereads the ->next pointer.
295 * Rereading the ->next pointer is not a problem for list_empty() and
296 * list_first_entry() because they would be protected by a lock that blocks
299 * See list_first_or_null_rcu for an alternative.
303 * list_first_or_null_rcu - get the first element from a list
304 * @ptr: the list head to take the element from.
305 * @type: the type of the struct this is embedded in.
306 * @member: the name of the list_head within the struct.
308 * Note that if the list is empty, it returns NULL.
310 * This primitive may safely run concurrently with the _rcu list-mutation
311 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
313 #define list_first_or_null_rcu(ptr, type, member) \
315 struct list_head *__ptr = (ptr); \
316 struct list_head *__next = READ_ONCE(__ptr->next); \
317 likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
321 * list_next_or_null_rcu - get the first element from a list
322 * @head: the head for the list.
323 * @ptr: the list head to take the next element from.
324 * @type: the type of the struct this is embedded in.
325 * @member: the name of the list_head within the struct.
327 * Note that if the ptr is at the end of the list, NULL is returned.
329 * This primitive may safely run concurrently with the _rcu list-mutation
330 * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
332 #define list_next_or_null_rcu(head, ptr, type, member) \
334 struct list_head *__head = (head); \
335 struct list_head *__ptr = (ptr); \
336 struct list_head *__next = READ_ONCE(__ptr->next); \
337 likely(__next != __head) ? list_entry_rcu(__next, type, \
342 * list_for_each_entry_rcu - iterate over rcu list of given type
343 * @pos: the type * to use as a loop cursor.
344 * @head: the head for your list.
345 * @member: the name of the list_head within the struct.
347 * This list-traversal primitive may safely run concurrently with
348 * the _rcu list-mutation primitives such as list_add_rcu()
349 * as long as the traversal is guarded by rcu_read_lock().
351 #define list_for_each_entry_rcu(pos, head, member) \
352 for (pos = list_entry_rcu((head)->next, typeof(*pos), member); \
353 &pos->member != (head); \
354 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
357 * list_entry_lockless - get the struct for this entry
358 * @ptr: the &struct list_head pointer.
359 * @type: the type of the struct this is embedded in.
360 * @member: the name of the list_head within the struct.
362 * This primitive may safely run concurrently with the _rcu
363 * list-mutation primitives such as list_add_rcu(), but requires some
364 * implicit RCU read-side guarding. One example is running within a special
365 * exception-time environment where preemption is disabled and where lockdep
366 * cannot be invoked. Another example is when items are added to the list,
369 #define list_entry_lockless(ptr, type, member) \
370 container_of((typeof(ptr))READ_ONCE(ptr), type, member)
373 * list_for_each_entry_lockless - iterate over rcu list of given type
374 * @pos: the type * to use as a loop cursor.
375 * @head: the head for your list.
376 * @member: the name of the list_struct within the struct.
378 * This primitive may safely run concurrently with the _rcu
379 * list-mutation primitives such as list_add_rcu(), but requires some
380 * implicit RCU read-side guarding. One example is running within a special
381 * exception-time environment where preemption is disabled and where lockdep
382 * cannot be invoked. Another example is when items are added to the list,
385 #define list_for_each_entry_lockless(pos, head, member) \
386 for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
387 &pos->member != (head); \
388 pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
391 * list_for_each_entry_continue_rcu - continue iteration over list of given type
392 * @pos: the type * to use as a loop cursor.
393 * @head: the head for your list.
394 * @member: the name of the list_head within the struct.
396 * Continue to iterate over list of given type, continuing after
397 * the current position which must have been in the list when the RCU read
399 * This would typically require either that you obtained the node from a
400 * previous walk of the list in the same RCU read-side critical section, or
401 * that you held some sort of non-RCU reference (such as a reference count)
402 * to keep the node alive *and* in the list.
404 * This iterator is similar to list_for_each_entry_from_rcu() except
405 * this starts after the given position and that one starts at the given
408 #define list_for_each_entry_continue_rcu(pos, head, member) \
409 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
410 &pos->member != (head); \
411 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
414 * list_for_each_entry_from_rcu - iterate over a list from current point
415 * @pos: the type * to use as a loop cursor.
416 * @head: the head for your list.
417 * @member: the name of the list_node within the struct.
419 * Iterate over the tail of a list starting from a given position,
420 * which must have been in the list when the RCU read lock was taken.
421 * This would typically require either that you obtained the node from a
422 * previous walk of the list in the same RCU read-side critical section, or
423 * that you held some sort of non-RCU reference (such as a reference count)
424 * to keep the node alive *and* in the list.
426 * This iterator is similar to list_for_each_entry_continue_rcu() except
427 * this starts from the given position and that one starts from the position
428 * after the given position.
430 #define list_for_each_entry_from_rcu(pos, head, member) \
431 for (; &(pos)->member != (head); \
432 pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
435 * hlist_del_rcu - deletes entry from hash list without re-initialization
436 * @n: the element to delete from the hash list.
438 * Note: list_unhashed() on entry does not return true after this,
439 * the entry is in an undefined state. It is useful for RCU based
440 * lockfree traversal.
442 * In particular, it means that we can not poison the forward
443 * pointers that may still be used for walking the hash list.
445 * The caller must take whatever precautions are necessary
446 * (such as holding appropriate locks) to avoid racing
447 * with another list-mutation primitive, such as hlist_add_head_rcu()
448 * or hlist_del_rcu(), running on this same list.
449 * However, it is perfectly legal to run concurrently with
450 * the _rcu list-traversal primitives, such as
451 * hlist_for_each_entry().
453 static inline void hlist_del_rcu(struct hlist_node *n)
456 n->pprev = LIST_POISON2;
460 * hlist_replace_rcu - replace old entry by new one
461 * @old : the element to be replaced
462 * @new : the new element to insert
464 * The @old entry will be replaced with the @new entry atomically.
466 static inline void hlist_replace_rcu(struct hlist_node *old,
467 struct hlist_node *new)
469 struct hlist_node *next = old->next;
472 new->pprev = old->pprev;
473 rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
475 new->next->pprev = &new->next;
476 old->pprev = LIST_POISON2;
480 * return the first or the next element in an RCU protected hlist
482 #define hlist_first_rcu(head) (*((struct hlist_node __rcu **)(&(head)->first)))
483 #define hlist_next_rcu(node) (*((struct hlist_node __rcu **)(&(node)->next)))
484 #define hlist_pprev_rcu(node) (*((struct hlist_node __rcu **)((node)->pprev)))
488 * @n: the element to add to the hash list.
489 * @h: the list to add to.
492 * Adds the specified element to the specified hlist,
493 * while permitting racing traversals.
495 * The caller must take whatever precautions are necessary
496 * (such as holding appropriate locks) to avoid racing
497 * with another list-mutation primitive, such as hlist_add_head_rcu()
498 * or hlist_del_rcu(), running on this same list.
499 * However, it is perfectly legal to run concurrently with
500 * the _rcu list-traversal primitives, such as
501 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
502 * problems on Alpha CPUs. Regardless of the type of CPU, the
503 * list-traversal primitive must be guarded by rcu_read_lock().
505 static inline void hlist_add_head_rcu(struct hlist_node *n,
506 struct hlist_head *h)
508 struct hlist_node *first = h->first;
511 n->pprev = &h->first;
512 rcu_assign_pointer(hlist_first_rcu(h), n);
514 first->pprev = &n->next;
519 * @n: the element to add to the hash list.
520 * @h: the list to add to.
523 * Adds the specified element to the specified hlist,
524 * while permitting racing traversals.
526 * The caller must take whatever precautions are necessary
527 * (such as holding appropriate locks) to avoid racing
528 * with another list-mutation primitive, such as hlist_add_head_rcu()
529 * or hlist_del_rcu(), running on this same list.
530 * However, it is perfectly legal to run concurrently with
531 * the _rcu list-traversal primitives, such as
532 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
533 * problems on Alpha CPUs. Regardless of the type of CPU, the
534 * list-traversal primitive must be guarded by rcu_read_lock().
536 static inline void hlist_add_tail_rcu(struct hlist_node *n,
537 struct hlist_head *h)
539 struct hlist_node *i, *last = NULL;
541 /* Note: write side code, so rcu accessors are not needed. */
542 for (i = h->first; i; i = i->next)
546 n->next = last->next;
547 n->pprev = &last->next;
548 rcu_assign_pointer(hlist_next_rcu(last), n);
550 hlist_add_head_rcu(n, h);
555 * hlist_add_before_rcu
556 * @n: the new element to add to the hash list.
557 * @next: the existing element to add the new element before.
560 * Adds the specified element to the specified hlist
561 * before the specified node while permitting racing traversals.
563 * The caller must take whatever precautions are necessary
564 * (such as holding appropriate locks) to avoid racing
565 * with another list-mutation primitive, such as hlist_add_head_rcu()
566 * or hlist_del_rcu(), running on this same list.
567 * However, it is perfectly legal to run concurrently with
568 * the _rcu list-traversal primitives, such as
569 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
570 * problems on Alpha CPUs.
572 static inline void hlist_add_before_rcu(struct hlist_node *n,
573 struct hlist_node *next)
575 n->pprev = next->pprev;
577 rcu_assign_pointer(hlist_pprev_rcu(n), n);
578 next->pprev = &n->next;
582 * hlist_add_behind_rcu
583 * @n: the new element to add to the hash list.
584 * @prev: the existing element to add the new element after.
587 * Adds the specified element to the specified hlist
588 * after the specified node while permitting racing traversals.
590 * The caller must take whatever precautions are necessary
591 * (such as holding appropriate locks) to avoid racing
592 * with another list-mutation primitive, such as hlist_add_head_rcu()
593 * or hlist_del_rcu(), running on this same list.
594 * However, it is perfectly legal to run concurrently with
595 * the _rcu list-traversal primitives, such as
596 * hlist_for_each_entry_rcu(), used to prevent memory-consistency
597 * problems on Alpha CPUs.
599 static inline void hlist_add_behind_rcu(struct hlist_node *n,
600 struct hlist_node *prev)
602 n->next = prev->next;
603 n->pprev = &prev->next;
604 rcu_assign_pointer(hlist_next_rcu(prev), n);
606 n->next->pprev = &n->next;
609 #define __hlist_for_each_rcu(pos, head) \
610 for (pos = rcu_dereference(hlist_first_rcu(head)); \
612 pos = rcu_dereference(hlist_next_rcu(pos)))
615 * hlist_for_each_entry_rcu - iterate over rcu list of given type
616 * @pos: the type * to use as a loop cursor.
617 * @head: the head for your list.
618 * @member: the name of the hlist_node within the struct.
620 * This list-traversal primitive may safely run concurrently with
621 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
622 * as long as the traversal is guarded by rcu_read_lock().
624 #define hlist_for_each_entry_rcu(pos, head, member) \
625 for (pos = hlist_entry_safe (rcu_dereference_raw(hlist_first_rcu(head)),\
626 typeof(*(pos)), member); \
628 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
629 &(pos)->member)), typeof(*(pos)), member))
632 * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
633 * @pos: the type * to use as a loop cursor.
634 * @head: the head for your list.
635 * @member: the name of the hlist_node within the struct.
637 * This list-traversal primitive may safely run concurrently with
638 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
639 * as long as the traversal is guarded by rcu_read_lock().
641 * This is the same as hlist_for_each_entry_rcu() except that it does
642 * not do any RCU debugging or tracing.
644 #define hlist_for_each_entry_rcu_notrace(pos, head, member) \
645 for (pos = hlist_entry_safe (rcu_dereference_raw_notrace(hlist_first_rcu(head)),\
646 typeof(*(pos)), member); \
648 pos = hlist_entry_safe(rcu_dereference_raw_notrace(hlist_next_rcu(\
649 &(pos)->member)), typeof(*(pos)), member))
652 * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
653 * @pos: the type * to use as a loop cursor.
654 * @head: the head for your list.
655 * @member: the name of the hlist_node within the struct.
657 * This list-traversal primitive may safely run concurrently with
658 * the _rcu list-mutation primitives such as hlist_add_head_rcu()
659 * as long as the traversal is guarded by rcu_read_lock().
661 #define hlist_for_each_entry_rcu_bh(pos, head, member) \
662 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
663 typeof(*(pos)), member); \
665 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
666 &(pos)->member)), typeof(*(pos)), member))
669 * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
670 * @pos: the type * to use as a loop cursor.
671 * @member: the name of the hlist_node within the struct.
673 #define hlist_for_each_entry_continue_rcu(pos, member) \
674 for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
675 &(pos)->member)), typeof(*(pos)), member); \
677 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
678 &(pos)->member)), typeof(*(pos)), member))
681 * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
682 * @pos: the type * to use as a loop cursor.
683 * @member: the name of the hlist_node within the struct.
685 #define hlist_for_each_entry_continue_rcu_bh(pos, member) \
686 for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
687 &(pos)->member)), typeof(*(pos)), member); \
689 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu( \
690 &(pos)->member)), typeof(*(pos)), member))
693 * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
694 * @pos: the type * to use as a loop cursor.
695 * @member: the name of the hlist_node within the struct.
697 #define hlist_for_each_entry_from_rcu(pos, member) \
699 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
700 &(pos)->member)), typeof(*(pos)), member))
702 #endif /* __KERNEL__ */