LCOV - code coverage report
Current view: top level - include/linux - rculist.h (source / functions) Hit Total Coverage
Test: landlock.info Lines: 53 77 68.8 %
Date: 2021-04-22 12:43:58 Functions: 1 1 100.0 %

          Line data    Source code
       1             : /* SPDX-License-Identifier: GPL-2.0 */
       2             : #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>
      11             : #include <linux/rcupdate.h>
      12             : 
      13             : /*
      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().
      20             :  */
      21             : 
      22             : /*
      23             :  * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers
      24             :  * @list: list to be initialized
      25             :  *
      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.
      30             :  */
      31           7 : static inline void INIT_LIST_HEAD_RCU(struct list_head *list)
      32             : {
      33           7 :         WRITE_ONCE(list->next, list);
      34           7 :         WRITE_ONCE(list->prev, list);
      35             : }
      36             : 
      37             : /*
      38             :  * return the ->next pointer of a list_head in an rcu safe
      39             :  * way, we must not access it directly
      40             :  */
      41             : #define list_next_rcu(list)     (*((struct list_head __rcu **)(&(list)->next)))
      42             : 
      43             : /**
      44             :  * list_tail_rcu - returns the prev pointer of the head of the list
      45             :  * @head: the head of the list
      46             :  *
      47             :  * Note: This should only be used with the list header, and even then
      48             :  * only if list_del() and similar primitives are not also used on the
      49             :  * list header.
      50             :  */
      51             : #define list_tail_rcu(head)     (*((struct list_head __rcu **)(&(head)->prev)))
      52             : 
      53             : /*
      54             :  * Check during list traversal that we are within an RCU reader
      55             :  */
      56             : 
      57             : #define check_arg_count_one(dummy)
      58             : 
      59             : #ifdef CONFIG_PROVE_RCU_LIST
      60             : #define __list_check_rcu(dummy, cond, extra...)                         \
      61             :         ({                                                              \
      62             :         check_arg_count_one(extra);                                     \
      63             :         RCU_LOCKDEP_WARN(!(cond) && !rcu_read_lock_any_held(),          \
      64             :                          "RCU-list traversed in non-reader section!");        \
      65             :         })
      66             : 
      67             : #define __list_check_srcu(cond)                                  \
      68             :         ({                                                               \
      69             :         RCU_LOCKDEP_WARN(!(cond),                                        \
      70             :                 "RCU-list traversed without holding the required lock!");\
      71             :         })
      72             : #else
      73             : #define __list_check_rcu(dummy, cond, extra...)                         \
      74             :         ({ check_arg_count_one(extra); })
      75             : 
      76             : #define __list_check_srcu(cond) ({ })
      77             : #endif
      78             : 
      79             : /*
      80             :  * Insert a new entry between two known consecutive entries.
      81             :  *
      82             :  * This is only for internal list manipulation where we know
      83             :  * the prev/next entries already!
      84             :  */
      85      729035 : static inline void __list_add_rcu(struct list_head *new,
      86             :                 struct list_head *prev, struct list_head *next)
      87             : {
      88      729035 :         if (!__list_add_valid(new, prev, next))
      89             :                 return;
      90             : 
      91      729035 :         new->next = next;
      92      728122 :         new->prev = prev;
      93      728122 :         rcu_assign_pointer(list_next_rcu(prev), new);
      94      729035 :         next->prev = new;
      95             : }
      96             : 
      97             : /**
      98             :  * list_add_rcu - add a new entry to rcu-protected list
      99             :  * @new: new entry to be added
     100             :  * @head: list head to add it after
     101             :  *
     102             :  * Insert a new entry after the specified head.
     103             :  * This is good for implementing stacks.
     104             :  *
     105             :  * The caller must take whatever precautions are necessary
     106             :  * (such as holding appropriate locks) to avoid racing
     107             :  * with another list-mutation primitive, such as list_add_rcu()
     108             :  * or list_del_rcu(), running on this same list.
     109             :  * However, it is perfectly legal to run concurrently with
     110             :  * the _rcu list-traversal primitives, such as
     111             :  * list_for_each_entry_rcu().
     112             :  */
     113          86 : static inline void list_add_rcu(struct list_head *new, struct list_head *head)
     114             : {
     115          86 :         __list_add_rcu(new, head, head->next);
     116          73 : }
     117             : 
     118             : /**
     119             :  * list_add_tail_rcu - add a new entry to rcu-protected list
     120             :  * @new: new entry to be added
     121             :  * @head: list head to add it before
     122             :  *
     123             :  * Insert a new entry before the specified head.
     124             :  * This is useful for implementing queues.
     125             :  *
     126             :  * The caller must take whatever precautions are necessary
     127             :  * (such as holding appropriate locks) to avoid racing
     128             :  * with another list-mutation primitive, such as list_add_tail_rcu()
     129             :  * or list_del_rcu(), running on this same list.
     130             :  * However, it is perfectly legal to run concurrently with
     131             :  * the _rcu list-traversal primitives, such as
     132             :  * list_for_each_entry_rcu().
     133             :  */
     134      728036 : static inline void list_add_tail_rcu(struct list_head *new,
     135             :                                         struct list_head *head)
     136             : {
     137      728943 :         __list_add_rcu(new, head->prev, head);
     138      721513 : }
     139             : 
     140             : /**
     141             :  * list_del_rcu - deletes entry from list without re-initialization
     142             :  * @entry: the element to delete from the list.
     143             :  *
     144             :  * Note: list_empty() on entry does not return true after this,
     145             :  * the entry is in an undefined state. It is useful for RCU based
     146             :  * lockfree traversal.
     147             :  *
     148             :  * In particular, it means that we can not poison the forward
     149             :  * pointers that may still be used for walking the list.
     150             :  *
     151             :  * The caller must take whatever precautions are necessary
     152             :  * (such as holding appropriate locks) to avoid racing
     153             :  * with another list-mutation primitive, such as list_del_rcu()
     154             :  * or list_add_rcu(), running on this same list.
     155             :  * However, it is perfectly legal to run concurrently with
     156             :  * the _rcu list-traversal primitives, such as
     157             :  * list_for_each_entry_rcu().
     158             :  *
     159             :  * Note that the caller is not permitted to immediately free
     160             :  * the newly deleted entry.  Instead, either synchronize_rcu()
     161             :  * or call_rcu() must be used to defer freeing until an RCU
     162             :  * grace period has elapsed.
     163             :  */
     164      641256 : static inline void list_del_rcu(struct list_head *entry)
     165             : {
     166      641256 :         __list_del_entry(entry);
     167      641256 :         entry->prev = LIST_POISON2;
     168           2 : }
     169             : 
     170             : /**
     171             :  * hlist_del_init_rcu - deletes entry from hash list with re-initialization
     172             :  * @n: the element to delete from the hash list.
     173             :  *
     174             :  * Note: list_unhashed() on the node return true after this. It is
     175             :  * useful for RCU based read lockfree traversal if the writer side
     176             :  * must know if the list entry is still hashed or already unhashed.
     177             :  *
     178             :  * In particular, it means that we can not poison the forward pointers
     179             :  * that may still be used for walking the hash list and we can only
     180             :  * zero the pprev pointer so list_unhashed() will return true after
     181             :  * this.
     182             :  *
     183             :  * The caller must take whatever precautions are necessary (such as
     184             :  * holding appropriate locks) to avoid racing with another
     185             :  * list-mutation primitive, such as hlist_add_head_rcu() or
     186             :  * hlist_del_rcu(), running on this same list.  However, it is
     187             :  * perfectly legal to run concurrently with the _rcu list-traversal
     188             :  * primitives, such as hlist_for_each_entry_rcu().
     189             :  */
     190        2317 : static inline void hlist_del_init_rcu(struct hlist_node *n)
     191             : {
     192        2317 :         if (!hlist_unhashed(n)) {
     193        2086 :                 __hlist_del(n);
     194        2317 :                 WRITE_ONCE(n->pprev, NULL);
     195             :         }
     196             : }
     197             : 
     198             : /**
     199             :  * list_replace_rcu - replace old entry by new one
     200             :  * @old : the element to be replaced
     201             :  * @new : the new element to insert
     202             :  *
     203             :  * The @old entry will be replaced with the @new entry atomically.
     204             :  * Note: @old should not be empty.
     205             :  */
     206           0 : static inline void list_replace_rcu(struct list_head *old,
     207             :                                 struct list_head *new)
     208             : {
     209           0 :         new->next = old->next;
     210           0 :         new->prev = old->prev;
     211           0 :         rcu_assign_pointer(list_next_rcu(new->prev), new);
     212           0 :         new->next->prev = new;
     213           0 :         old->prev = LIST_POISON2;
     214             : }
     215             : 
     216             : /**
     217             :  * __list_splice_init_rcu - join an RCU-protected list into an existing list.
     218             :  * @list:       the RCU-protected list to splice
     219             :  * @prev:       points to the last element of the existing list
     220             :  * @next:       points to the first element of the existing list
     221             :  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
     222             :  *
     223             :  * The list pointed to by @prev and @next can be RCU-read traversed
     224             :  * concurrently with this function.
     225             :  *
     226             :  * Note that this function blocks.
     227             :  *
     228             :  * Important note: the caller must take whatever action is necessary to prevent
     229             :  * any other updates to the existing list.  In principle, it is possible to
     230             :  * modify the list as soon as sync() begins execution. If this sort of thing
     231             :  * becomes necessary, an alternative version based on call_rcu() could be
     232             :  * created.  But only if -really- needed -- there is no shortage of RCU API
     233             :  * members.
     234             :  */
     235             : static inline void __list_splice_init_rcu(struct list_head *list,
     236             :                                           struct list_head *prev,
     237             :                                           struct list_head *next,
     238             :                                           void (*sync)(void))
     239             : {
     240             :         struct list_head *first = list->next;
     241             :         struct list_head *last = list->prev;
     242             : 
     243             :         /*
     244             :          * "first" and "last" tracking list, so initialize it.  RCU readers
     245             :          * have access to this list, so we must use INIT_LIST_HEAD_RCU()
     246             :          * instead of INIT_LIST_HEAD().
     247             :          */
     248             : 
     249             :         INIT_LIST_HEAD_RCU(list);
     250             : 
     251             :         /*
     252             :          * At this point, the list body still points to the source list.
     253             :          * Wait for any readers to finish using the list before splicing
     254             :          * the list body into the new list.  Any new readers will see
     255             :          * an empty list.
     256             :          */
     257             : 
     258             :         sync();
     259             :         ASSERT_EXCLUSIVE_ACCESS(*first);
     260             :         ASSERT_EXCLUSIVE_ACCESS(*last);
     261             : 
     262             :         /*
     263             :          * Readers are finished with the source list, so perform splice.
     264             :          * The order is important if the new list is global and accessible
     265             :          * to concurrent RCU readers.  Note that RCU readers are not
     266             :          * permitted to traverse the prev pointers without excluding
     267             :          * this function.
     268             :          */
     269             : 
     270             :         last->next = next;
     271             :         rcu_assign_pointer(list_next_rcu(prev), first);
     272             :         first->prev = prev;
     273             :         next->prev = last;
     274             : }
     275             : 
     276             : /**
     277             :  * list_splice_init_rcu - splice an RCU-protected list into an existing list,
     278             :  *                        designed for stacks.
     279             :  * @list:       the RCU-protected list to splice
     280             :  * @head:       the place in the existing list to splice the first list into
     281             :  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
     282             :  */
     283             : static inline void list_splice_init_rcu(struct list_head *list,
     284             :                                         struct list_head *head,
     285             :                                         void (*sync)(void))
     286             : {
     287             :         if (!list_empty(list))
     288             :                 __list_splice_init_rcu(list, head, head->next, sync);
     289             : }
     290             : 
     291             : /**
     292             :  * list_splice_tail_init_rcu - splice an RCU-protected list into an existing
     293             :  *                             list, designed for queues.
     294             :  * @list:       the RCU-protected list to splice
     295             :  * @head:       the place in the existing list to splice the first list into
     296             :  * @sync:       synchronize_rcu, synchronize_rcu_expedited, ...
     297             :  */
     298             : static inline void list_splice_tail_init_rcu(struct list_head *list,
     299             :                                              struct list_head *head,
     300             :                                              void (*sync)(void))
     301             : {
     302             :         if (!list_empty(list))
     303             :                 __list_splice_init_rcu(list, head->prev, head, sync);
     304             : }
     305             : 
     306             : /**
     307             :  * list_entry_rcu - get the struct for this entry
     308             :  * @ptr:        the &struct list_head pointer.
     309             :  * @type:       the type of the struct this is embedded in.
     310             :  * @member:     the name of the list_head within the struct.
     311             :  *
     312             :  * This primitive may safely run concurrently with the _rcu list-mutation
     313             :  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
     314             :  */
     315             : #define list_entry_rcu(ptr, type, member) \
     316             :         container_of(READ_ONCE(ptr), type, member)
     317             : 
     318             : /*
     319             :  * Where are list_empty_rcu() and list_first_entry_rcu()?
     320             :  *
     321             :  * Implementing those functions following their counterparts list_empty() and
     322             :  * list_first_entry() is not advisable because they lead to subtle race
     323             :  * conditions as the following snippet shows:
     324             :  *
     325             :  * if (!list_empty_rcu(mylist)) {
     326             :  *      struct foo *bar = list_first_entry_rcu(mylist, struct foo, list_member);
     327             :  *      do_something(bar);
     328             :  * }
     329             :  *
     330             :  * The list may not be empty when list_empty_rcu checks it, but it may be when
     331             :  * list_first_entry_rcu rereads the ->next pointer.
     332             :  *
     333             :  * Rereading the ->next pointer is not a problem for list_empty() and
     334             :  * list_first_entry() because they would be protected by a lock that blocks
     335             :  * writers.
     336             :  *
     337             :  * See list_first_or_null_rcu for an alternative.
     338             :  */
     339             : 
     340             : /**
     341             :  * list_first_or_null_rcu - get the first element from a list
     342             :  * @ptr:        the list head to take the element from.
     343             :  * @type:       the type of the struct this is embedded in.
     344             :  * @member:     the name of the list_head within the struct.
     345             :  *
     346             :  * Note that if the list is empty, it returns NULL.
     347             :  *
     348             :  * This primitive may safely run concurrently with the _rcu list-mutation
     349             :  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
     350             :  */
     351             : #define list_first_or_null_rcu(ptr, type, member) \
     352             : ({ \
     353             :         struct list_head *__ptr = (ptr); \
     354             :         struct list_head *__next = READ_ONCE(__ptr->next); \
     355             :         likely(__ptr != __next) ? list_entry_rcu(__next, type, member) : NULL; \
     356             : })
     357             : 
     358             : /**
     359             :  * list_next_or_null_rcu - get the first element from a list
     360             :  * @head:       the head for the list.
     361             :  * @ptr:        the list head to take the next element from.
     362             :  * @type:       the type of the struct this is embedded in.
     363             :  * @member:     the name of the list_head within the struct.
     364             :  *
     365             :  * Note that if the ptr is at the end of the list, NULL is returned.
     366             :  *
     367             :  * This primitive may safely run concurrently with the _rcu list-mutation
     368             :  * primitives such as list_add_rcu() as long as it's guarded by rcu_read_lock().
     369             :  */
     370             : #define list_next_or_null_rcu(head, ptr, type, member) \
     371             : ({ \
     372             :         struct list_head *__head = (head); \
     373             :         struct list_head *__ptr = (ptr); \
     374             :         struct list_head *__next = READ_ONCE(__ptr->next); \
     375             :         likely(__next != __head) ? list_entry_rcu(__next, type, \
     376             :                                                   member) : NULL; \
     377             : })
     378             : 
     379             : /**
     380             :  * list_for_each_entry_rcu      -       iterate over rcu list of given type
     381             :  * @pos:        the type * to use as a loop cursor.
     382             :  * @head:       the head for your list.
     383             :  * @member:     the name of the list_head within the struct.
     384             :  * @cond:       optional lockdep expression if called from non-RCU protection.
     385             :  *
     386             :  * This list-traversal primitive may safely run concurrently with
     387             :  * the _rcu list-mutation primitives such as list_add_rcu()
     388             :  * as long as the traversal is guarded by rcu_read_lock().
     389             :  */
     390             : #define list_for_each_entry_rcu(pos, head, member, cond...)             \
     391             :         for (__list_check_rcu(dummy, ## cond, 0),                       \
     392             :              pos = list_entry_rcu((head)->next, typeof(*pos), member);       \
     393             :                 &pos->member != (head);                                  \
     394             :                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
     395             : 
     396             : /**
     397             :  * list_for_each_entry_srcu     -       iterate over rcu list of given type
     398             :  * @pos:        the type * to use as a loop cursor.
     399             :  * @head:       the head for your list.
     400             :  * @member:     the name of the list_head within the struct.
     401             :  * @cond:       lockdep expression for the lock required to traverse the list.
     402             :  *
     403             :  * This list-traversal primitive may safely run concurrently with
     404             :  * the _rcu list-mutation primitives such as list_add_rcu()
     405             :  * as long as the traversal is guarded by srcu_read_lock().
     406             :  * The lockdep expression srcu_read_lock_held() can be passed as the
     407             :  * cond argument from read side.
     408             :  */
     409             : #define list_for_each_entry_srcu(pos, head, member, cond)               \
     410             :         for (__list_check_srcu(cond),                                   \
     411             :              pos = list_entry_rcu((head)->next, typeof(*pos), member);       \
     412             :                 &pos->member != (head);                                  \
     413             :                 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
     414             : 
     415             : /**
     416             :  * list_entry_lockless - get the struct for this entry
     417             :  * @ptr:        the &struct list_head pointer.
     418             :  * @type:       the type of the struct this is embedded in.
     419             :  * @member:     the name of the list_head within the struct.
     420             :  *
     421             :  * This primitive may safely run concurrently with the _rcu
     422             :  * list-mutation primitives such as list_add_rcu(), but requires some
     423             :  * implicit RCU read-side guarding.  One example is running within a special
     424             :  * exception-time environment where preemption is disabled and where lockdep
     425             :  * cannot be invoked.  Another example is when items are added to the list,
     426             :  * but never deleted.
     427             :  */
     428             : #define list_entry_lockless(ptr, type, member) \
     429             :         container_of((typeof(ptr))READ_ONCE(ptr), type, member)
     430             : 
     431             : /**
     432             :  * list_for_each_entry_lockless - iterate over rcu list of given type
     433             :  * @pos:        the type * to use as a loop cursor.
     434             :  * @head:       the head for your list.
     435             :  * @member:     the name of the list_struct within the struct.
     436             :  *
     437             :  * This primitive may safely run concurrently with the _rcu
     438             :  * list-mutation primitives such as list_add_rcu(), but requires some
     439             :  * implicit RCU read-side guarding.  One example is running within a special
     440             :  * exception-time environment where preemption is disabled and where lockdep
     441             :  * cannot be invoked.  Another example is when items are added to the list,
     442             :  * but never deleted.
     443             :  */
     444             : #define list_for_each_entry_lockless(pos, head, member) \
     445             :         for (pos = list_entry_lockless((head)->next, typeof(*pos), member); \
     446             :              &pos->member != (head); \
     447             :              pos = list_entry_lockless(pos->member.next, typeof(*pos), member))
     448             : 
     449             : /**
     450             :  * list_for_each_entry_continue_rcu - continue iteration over list of given type
     451             :  * @pos:        the type * to use as a loop cursor.
     452             :  * @head:       the head for your list.
     453             :  * @member:     the name of the list_head within the struct.
     454             :  *
     455             :  * Continue to iterate over list of given type, continuing after
     456             :  * the current position which must have been in the list when the RCU read
     457             :  * lock was taken.
     458             :  * This would typically require either that you obtained the node from a
     459             :  * previous walk of the list in the same RCU read-side critical section, or
     460             :  * that you held some sort of non-RCU reference (such as a reference count)
     461             :  * to keep the node alive *and* in the list.
     462             :  *
     463             :  * This iterator is similar to list_for_each_entry_from_rcu() except
     464             :  * this starts after the given position and that one starts at the given
     465             :  * position.
     466             :  */
     467             : #define list_for_each_entry_continue_rcu(pos, head, member)             \
     468             :         for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
     469             :              &pos->member != (head);     \
     470             :              pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
     471             : 
     472             : /**
     473             :  * list_for_each_entry_from_rcu - iterate over a list from current point
     474             :  * @pos:        the type * to use as a loop cursor.
     475             :  * @head:       the head for your list.
     476             :  * @member:     the name of the list_node within the struct.
     477             :  *
     478             :  * Iterate over the tail of a list starting from a given position,
     479             :  * which must have been in the list when the RCU read lock was taken.
     480             :  * This would typically require either that you obtained the node from a
     481             :  * previous walk of the list in the same RCU read-side critical section, or
     482             :  * that you held some sort of non-RCU reference (such as a reference count)
     483             :  * to keep the node alive *and* in the list.
     484             :  *
     485             :  * This iterator is similar to list_for_each_entry_continue_rcu() except
     486             :  * this starts from the given position and that one starts from the position
     487             :  * after the given position.
     488             :  */
     489             : #define list_for_each_entry_from_rcu(pos, head, member)                 \
     490             :         for (; &(pos)->member != (head);                                 \
     491             :                 pos = list_entry_rcu(pos->member.next, typeof(*(pos)), member))
     492             : 
     493             : /**
     494             :  * hlist_del_rcu - deletes entry from hash list without re-initialization
     495             :  * @n: the element to delete from the hash list.
     496             :  *
     497             :  * Note: list_unhashed() on entry does not return true after this,
     498             :  * the entry is in an undefined state. It is useful for RCU based
     499             :  * lockfree traversal.
     500             :  *
     501             :  * In particular, it means that we can not poison the forward
     502             :  * pointers that may still be used for walking the hash list.
     503             :  *
     504             :  * The caller must take whatever precautions are necessary
     505             :  * (such as holding appropriate locks) to avoid racing
     506             :  * with another list-mutation primitive, such as hlist_add_head_rcu()
     507             :  * or hlist_del_rcu(), running on this same list.
     508             :  * However, it is perfectly legal to run concurrently with
     509             :  * the _rcu list-traversal primitives, such as
     510             :  * hlist_for_each_entry().
     511             :  */
     512        3789 : static inline void hlist_del_rcu(struct hlist_node *n)
     513             : {
     514        3789 :         __hlist_del(n);
     515        3789 :         WRITE_ONCE(n->pprev, LIST_POISON2);
     516           0 : }
     517             : 
     518             : /**
     519             :  * hlist_replace_rcu - replace old entry by new one
     520             :  * @old : the element to be replaced
     521             :  * @new : the new element to insert
     522             :  *
     523             :  * The @old entry will be replaced with the @new entry atomically.
     524             :  */
     525           0 : static inline void hlist_replace_rcu(struct hlist_node *old,
     526             :                                         struct hlist_node *new)
     527             : {
     528           0 :         struct hlist_node *next = old->next;
     529             : 
     530           0 :         new->next = next;
     531           0 :         WRITE_ONCE(new->pprev, old->pprev);
     532           0 :         rcu_assign_pointer(*(struct hlist_node __rcu **)new->pprev, new);
     533           0 :         if (next)
     534           0 :                 WRITE_ONCE(new->next->pprev, &new->next);
     535           0 :         WRITE_ONCE(old->pprev, LIST_POISON2);
     536             : }
     537             : 
     538             : /**
     539             :  * hlists_swap_heads_rcu - swap the lists the hlist heads point to
     540             :  * @left:  The hlist head on the left
     541             :  * @right: The hlist head on the right
     542             :  *
     543             :  * The lists start out as [@left  ][node1 ... ] and
     544             :  *                        [@right ][node2 ... ]
     545             :  * The lists end up as    [@left  ][node2 ... ]
     546             :  *                        [@right ][node1 ... ]
     547             :  */
     548           0 : static inline void hlists_swap_heads_rcu(struct hlist_head *left, struct hlist_head *right)
     549             : {
     550           0 :         struct hlist_node *node1 = left->first;
     551           0 :         struct hlist_node *node2 = right->first;
     552             : 
     553           0 :         rcu_assign_pointer(left->first, node2);
     554           0 :         rcu_assign_pointer(right->first, node1);
     555           0 :         WRITE_ONCE(node2->pprev, &left->first);
     556           0 :         WRITE_ONCE(node1->pprev, &right->first);
     557             : }
     558             : 
     559             : /*
     560             :  * return the first or the next element in an RCU protected hlist
     561             :  */
     562             : #define hlist_first_rcu(head)   (*((struct hlist_node __rcu **)(&(head)->first)))
     563             : #define hlist_next_rcu(node)    (*((struct hlist_node __rcu **)(&(node)->next)))
     564             : #define hlist_pprev_rcu(node)   (*((struct hlist_node __rcu **)((node)->pprev)))
     565             : 
     566             : /**
     567             :  * hlist_add_head_rcu
     568             :  * @n: the element to add to the hash list.
     569             :  * @h: the list to add to.
     570             :  *
     571             :  * Description:
     572             :  * Adds the specified element to the specified hlist,
     573             :  * while permitting racing traversals.
     574             :  *
     575             :  * The caller must take whatever precautions are necessary
     576             :  * (such as holding appropriate locks) to avoid racing
     577             :  * with another list-mutation primitive, such as hlist_add_head_rcu()
     578             :  * or hlist_del_rcu(), running on this same list.
     579             :  * However, it is perfectly legal to run concurrently with
     580             :  * the _rcu list-traversal primitives, such as
     581             :  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
     582             :  * problems on Alpha CPUs.  Regardless of the type of CPU, the
     583             :  * list-traversal primitive must be guarded by rcu_read_lock().
     584             :  */
     585       21027 : static inline void hlist_add_head_rcu(struct hlist_node *n,
     586             :                                         struct hlist_head *h)
     587             : {
     588       21027 :         struct hlist_node *first = h->first;
     589             : 
     590       21027 :         n->next = first;
     591       21027 :         WRITE_ONCE(n->pprev, &h->first);
     592       21063 :         rcu_assign_pointer(hlist_first_rcu(h), n);
     593       21027 :         if (first)
     594       17861 :                 WRITE_ONCE(first->pprev, &n->next);
     595             : }
     596             : 
     597             : /**
     598             :  * hlist_add_tail_rcu
     599             :  * @n: the element to add to the hash list.
     600             :  * @h: the list to add to.
     601             :  *
     602             :  * Description:
     603             :  * Adds the specified element to the specified hlist,
     604             :  * while permitting racing traversals.
     605             :  *
     606             :  * The caller must take whatever precautions are necessary
     607             :  * (such as holding appropriate locks) to avoid racing
     608             :  * with another list-mutation primitive, such as hlist_add_head_rcu()
     609             :  * or hlist_del_rcu(), running on this same list.
     610             :  * However, it is perfectly legal to run concurrently with
     611             :  * the _rcu list-traversal primitives, such as
     612             :  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
     613             :  * problems on Alpha CPUs.  Regardless of the type of CPU, the
     614             :  * list-traversal primitive must be guarded by rcu_read_lock().
     615             :  */
     616          38 : static inline void hlist_add_tail_rcu(struct hlist_node *n,
     617             :                                       struct hlist_head *h)
     618             : {
     619          38 :         struct hlist_node *i, *last = NULL;
     620             : 
     621             :         /* Note: write side code, so rcu accessors are not needed. */
     622          40 :         for (i = h->first; i; i = i->next)
     623           2 :                 last = i;
     624             : 
     625          38 :         if (last) {
     626           2 :                 n->next = last->next;
     627           2 :                 WRITE_ONCE(n->pprev, &last->next);
     628           2 :                 rcu_assign_pointer(hlist_next_rcu(last), n);
     629             :         } else {
     630          36 :                 hlist_add_head_rcu(n, h);
     631             :         }
     632          38 : }
     633             : 
     634             : /**
     635             :  * hlist_add_before_rcu
     636             :  * @n: the new element to add to the hash list.
     637             :  * @next: the existing element to add the new element before.
     638             :  *
     639             :  * Description:
     640             :  * Adds the specified element to the specified hlist
     641             :  * before the specified node while permitting racing traversals.
     642             :  *
     643             :  * The caller must take whatever precautions are necessary
     644             :  * (such as holding appropriate locks) to avoid racing
     645             :  * with another list-mutation primitive, such as hlist_add_head_rcu()
     646             :  * or hlist_del_rcu(), running on this same list.
     647             :  * However, it is perfectly legal to run concurrently with
     648             :  * the _rcu list-traversal primitives, such as
     649             :  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
     650             :  * problems on Alpha CPUs.
     651             :  */
     652           8 : static inline void hlist_add_before_rcu(struct hlist_node *n,
     653             :                                         struct hlist_node *next)
     654             : {
     655           8 :         WRITE_ONCE(n->pprev, next->pprev);
     656           8 :         n->next = next;
     657           8 :         rcu_assign_pointer(hlist_pprev_rcu(n), n);
     658           8 :         WRITE_ONCE(next->pprev, &n->next);
     659           0 : }
     660             : 
     661             : /**
     662             :  * hlist_add_behind_rcu
     663             :  * @n: the new element to add to the hash list.
     664             :  * @prev: the existing element to add the new element after.
     665             :  *
     666             :  * Description:
     667             :  * Adds the specified element to the specified hlist
     668             :  * after the specified node while permitting racing traversals.
     669             :  *
     670             :  * The caller must take whatever precautions are necessary
     671             :  * (such as holding appropriate locks) to avoid racing
     672             :  * with another list-mutation primitive, such as hlist_add_head_rcu()
     673             :  * or hlist_del_rcu(), running on this same list.
     674             :  * However, it is perfectly legal to run concurrently with
     675             :  * the _rcu list-traversal primitives, such as
     676             :  * hlist_for_each_entry_rcu(), used to prevent memory-consistency
     677             :  * problems on Alpha CPUs.
     678             :  */
     679           5 : static inline void hlist_add_behind_rcu(struct hlist_node *n,
     680             :                                         struct hlist_node *prev)
     681             : {
     682           5 :         n->next = prev->next;
     683           5 :         WRITE_ONCE(n->pprev, &prev->next);
     684           5 :         rcu_assign_pointer(hlist_next_rcu(prev), n);
     685           5 :         if (n->next)
     686           0 :                 WRITE_ONCE(n->next->pprev, &n->next);
     687             : }
     688             : 
     689             : #define __hlist_for_each_rcu(pos, head)                         \
     690             :         for (pos = rcu_dereference(hlist_first_rcu(head));      \
     691             :              pos;                                               \
     692             :              pos = rcu_dereference(hlist_next_rcu(pos)))
     693             : 
     694             : /**
     695             :  * hlist_for_each_entry_rcu - iterate over rcu list of given type
     696             :  * @pos:        the type * to use as a loop cursor.
     697             :  * @head:       the head for your list.
     698             :  * @member:     the name of the hlist_node within the struct.
     699             :  * @cond:       optional lockdep expression if called from non-RCU protection.
     700             :  *
     701             :  * This list-traversal primitive may safely run concurrently with
     702             :  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
     703             :  * as long as the traversal is guarded by rcu_read_lock().
     704             :  */
     705             : #define hlist_for_each_entry_rcu(pos, head, member, cond...)            \
     706             :         for (__list_check_rcu(dummy, ## cond, 0),                       \
     707             :              pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
     708             :                         typeof(*(pos)), member);                        \
     709             :                 pos;                                                    \
     710             :                 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
     711             :                         &(pos)->member)), typeof(*(pos)), member))
     712             : 
     713             : /**
     714             :  * hlist_for_each_entry_srcu - iterate over rcu list of given type
     715             :  * @pos:        the type * to use as a loop cursor.
     716             :  * @head:       the head for your list.
     717             :  * @member:     the name of the hlist_node within the struct.
     718             :  * @cond:       lockdep expression for the lock required to traverse the list.
     719             :  *
     720             :  * This list-traversal primitive may safely run concurrently with
     721             :  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
     722             :  * as long as the traversal is guarded by srcu_read_lock().
     723             :  * The lockdep expression srcu_read_lock_held() can be passed as the
     724             :  * cond argument from read side.
     725             :  */
     726             : #define hlist_for_each_entry_srcu(pos, head, member, cond)              \
     727             :         for (__list_check_srcu(cond),                                   \
     728             :              pos = hlist_entry_safe(rcu_dereference_raw(hlist_first_rcu(head)),\
     729             :                         typeof(*(pos)), member);                        \
     730             :                 pos;                                                    \
     731             :                 pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu(\
     732             :                         &(pos)->member)), typeof(*(pos)), member))
     733             : 
     734             : /**
     735             :  * hlist_for_each_entry_rcu_notrace - iterate over rcu list of given type (for tracing)
     736             :  * @pos:        the type * to use as a loop cursor.
     737             :  * @head:       the head for your list.
     738             :  * @member:     the name of the hlist_node within the struct.
     739             :  *
     740             :  * This list-traversal primitive may safely run concurrently with
     741             :  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
     742             :  * as long as the traversal is guarded by rcu_read_lock().
     743             :  *
     744             :  * This is the same as hlist_for_each_entry_rcu() except that it does
     745             :  * not do any RCU debugging or tracing.
     746             :  */
     747             : #define hlist_for_each_entry_rcu_notrace(pos, head, member)                     \
     748             :         for (pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_first_rcu(head)),\
     749             :                         typeof(*(pos)), member);                        \
     750             :                 pos;                                                    \
     751             :                 pos = hlist_entry_safe(rcu_dereference_raw_check(hlist_next_rcu(\
     752             :                         &(pos)->member)), typeof(*(pos)), member))
     753             : 
     754             : /**
     755             :  * hlist_for_each_entry_rcu_bh - iterate over rcu list of given type
     756             :  * @pos:        the type * to use as a loop cursor.
     757             :  * @head:       the head for your list.
     758             :  * @member:     the name of the hlist_node within the struct.
     759             :  *
     760             :  * This list-traversal primitive may safely run concurrently with
     761             :  * the _rcu list-mutation primitives such as hlist_add_head_rcu()
     762             :  * as long as the traversal is guarded by rcu_read_lock().
     763             :  */
     764             : #define hlist_for_each_entry_rcu_bh(pos, head, member)                  \
     765             :         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_first_rcu(head)),\
     766             :                         typeof(*(pos)), member);                        \
     767             :                 pos;                                                    \
     768             :                 pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(\
     769             :                         &(pos)->member)), typeof(*(pos)), member))
     770             : 
     771             : /**
     772             :  * hlist_for_each_entry_continue_rcu - iterate over a hlist continuing after current point
     773             :  * @pos:        the type * to use as a loop cursor.
     774             :  * @member:     the name of the hlist_node within the struct.
     775             :  */
     776             : #define hlist_for_each_entry_continue_rcu(pos, member)                  \
     777             :         for (pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
     778             :                         &(pos)->member)), typeof(*(pos)), member);       \
     779             :              pos;                                                       \
     780             :              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
     781             :                         &(pos)->member)), typeof(*(pos)), member))
     782             : 
     783             : /**
     784             :  * hlist_for_each_entry_continue_rcu_bh - iterate over a hlist continuing after current point
     785             :  * @pos:        the type * to use as a loop cursor.
     786             :  * @member:     the name of the hlist_node within the struct.
     787             :  */
     788             : #define hlist_for_each_entry_continue_rcu_bh(pos, member)               \
     789             :         for (pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
     790             :                         &(pos)->member)), typeof(*(pos)), member);       \
     791             :              pos;                                                       \
     792             :              pos = hlist_entry_safe(rcu_dereference_bh(hlist_next_rcu(  \
     793             :                         &(pos)->member)), typeof(*(pos)), member))
     794             : 
     795             : /**
     796             :  * hlist_for_each_entry_from_rcu - iterate over a hlist continuing from current point
     797             :  * @pos:        the type * to use as a loop cursor.
     798             :  * @member:     the name of the hlist_node within the struct.
     799             :  */
     800             : #define hlist_for_each_entry_from_rcu(pos, member)                      \
     801             :         for (; pos;                                                     \
     802             :              pos = hlist_entry_safe(rcu_dereference_raw(hlist_next_rcu( \
     803             :                         &(pos)->member)), typeof(*(pos)), member))
     804             : 
     805             : #endif  /* __KERNEL__ */
     806             : #endif

Generated by: LCOV version 1.14