Line data    Source code

       1             : /* SPDX-License-Identifier: GPL-2.0 */
       2             : #ifndef _LINUX_RCULIST_NULLS_H
       3             : #define _LINUX_RCULIST_NULLS_H
       4             : 
       5             : #ifdef __KERNEL__
       6             : 
       7             : /*
       8             :  * RCU-protected list version
       9             :  */
      10             : #include <linux/list_nulls.h>
      11             : #include <linux/rcupdate.h>
      12             : 
      13             : /**
      14             :  * hlist_nulls_del_init_rcu - deletes entry from hash list with re-initialization
      15             :  * @n: the element to delete from the hash list.
      16             :  *
      17             :  * Note: hlist_nulls_unhashed() on the node return true after this. It is
      18             :  * useful for RCU based read lockfree traversal if the writer side
      19             :  * must know if the list entry is still hashed or already unhashed.
      20             :  *
      21             :  * In particular, it means that we can not poison the forward pointers
      22             :  * that may still be used for walking the hash list and we can only
      23             :  * zero the pprev pointer so list_unhashed() will return true after
      24             :  * this.
      25             :  *
      26             :  * The caller must take whatever precautions are necessary (such as
      27             :  * holding appropriate locks) to avoid racing with another
      28             :  * list-mutation primitive, such as hlist_nulls_add_head_rcu() or
      29             :  * hlist_nulls_del_rcu(), running on this same list.  However, it is
      30             :  * perfectly legal to run concurrently with the _rcu list-traversal
      31             :  * primitives, such as hlist_nulls_for_each_entry_rcu().
      32             :  */
      33           8 : static inline void hlist_nulls_del_init_rcu(struct hlist_nulls_node *n)
      34             : {
      35           8 :         if (!hlist_nulls_unhashed(n)) {
      36           8 :                 __hlist_nulls_del(n);
      37           8 :                 WRITE_ONCE(n->pprev, NULL);
      38             :         }
      39           8 : }
      40             : 
      41             : /**
      42             :  * hlist_nulls_first_rcu - returns the first element of the hash list.
      43             :  * @head: the head of the list.
      44             :  */
      45             : #define hlist_nulls_first_rcu(head) \
      46             :         (*((struct hlist_nulls_node __rcu __force **)&(head)->first))
      47             : 
      48             : /**
      49             :  * hlist_nulls_next_rcu - returns the element of the list after @node.
      50             :  * @node: element of the list.
      51             :  */
      52             : #define hlist_nulls_next_rcu(node) \
      53             :         (*((struct hlist_nulls_node __rcu __force **)&(node)->next))
      54             : 
      55             : /**
      56             :  * hlist_nulls_del_rcu - deletes entry from hash list without re-initialization
      57             :  * @n: the element to delete from the hash list.
      58             :  *
      59             :  * Note: hlist_nulls_unhashed() on entry does not return true after this,
      60             :  * the entry is in an undefined state. It is useful for RCU based
      61             :  * lockfree traversal.
      62             :  *
      63             :  * In particular, it means that we can not poison the forward
      64             :  * pointers that may still be used for walking the hash list.
      65             :  *
      66             :  * The caller must take whatever precautions are necessary
      67             :  * (such as holding appropriate locks) to avoid racing
      68             :  * with another list-mutation primitive, such as hlist_nulls_add_head_rcu()
      69             :  * or hlist_nulls_del_rcu(), running on this same list.
      70             :  * However, it is perfectly legal to run concurrently with
      71             :  * the _rcu list-traversal primitives, such as
      72             :  * hlist_nulls_for_each_entry().
      73             :  */
      74             : static inline void hlist_nulls_del_rcu(struct hlist_nulls_node *n)
      75             : {
      76             :         __hlist_nulls_del(n);
      77             :         WRITE_ONCE(n->pprev, LIST_POISON2);
      78             : }
      79             : 
      80             : /**
      81             :  * hlist_nulls_add_head_rcu
      82             :  * @n: the element to add to the hash list.
      83             :  * @h: the list to add to.
      84             :  *
      85             :  * Description:
      86             :  * Adds the specified element to the specified hlist_nulls,
      87             :  * while permitting racing traversals.
      88             :  *
      89             :  * The caller must take whatever precautions are necessary
      90             :  * (such as holding appropriate locks) to avoid racing
      91             :  * with another list-mutation primitive, such as hlist_nulls_add_head_rcu()
      92             :  * or hlist_nulls_del_rcu(), running on this same list.
      93             :  * However, it is perfectly legal to run concurrently with
      94             :  * the _rcu list-traversal primitives, such as
      95             :  * hlist_nulls_for_each_entry_rcu(), used to prevent memory-consistency
      96             :  * problems on Alpha CPUs.  Regardless of the type of CPU, the
      97             :  * list-traversal primitive must be guarded by rcu_read_lock().
      98             :  */
      99          11 : static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
     100             :                                         struct hlist_nulls_head *h)
     101             : {
     102          11 :         struct hlist_nulls_node *first = h->first;
     103             : 
     104          11 :         n->next = first;
     105          11 :         WRITE_ONCE(n->pprev, &h->first);
     106          11 :         rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
     107          11 :         if (!is_a_nulls(first))
     108           3 :                 WRITE_ONCE(first->pprev, &n->next);
     109             : }
     110             : 
     111             : /**
     112             :  * hlist_nulls_add_tail_rcu
     113             :  * @n: the element to add to the hash list.
     114             :  * @h: the list to add to.
     115             :  *
     116             :  * Description:
     117             :  * Adds the specified element to the specified hlist_nulls,
     118             :  * while permitting racing traversals.
     119             :  *
     120             :  * The caller must take whatever precautions are necessary
     121             :  * (such as holding appropriate locks) to avoid racing
     122             :  * with another list-mutation primitive, such as hlist_nulls_add_head_rcu()
     123             :  * or hlist_nulls_del_rcu(), running on this same list.
     124             :  * However, it is perfectly legal to run concurrently with
     125             :  * the _rcu list-traversal primitives, such as
     126             :  * hlist_nulls_for_each_entry_rcu(), used to prevent memory-consistency
     127             :  * problems on Alpha CPUs.  Regardless of the type of CPU, the
     128             :  * list-traversal primitive must be guarded by rcu_read_lock().
     129             :  */
     130             : static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
     131             :                                             struct hlist_nulls_head *h)
     132             : {
     133             :         struct hlist_nulls_node *i, *last = NULL;
     134             : 
     135             :         /* Note: write side code, so rcu accessors are not needed. */
     136             :         for (i = h->first; !is_a_nulls(i); i = i->next)
     137             :                 last = i;
     138             : 
     139             :         if (last) {
     140             :                 n->next = last->next;
     141             :                 n->pprev = &last->next;
     142             :                 rcu_assign_pointer(hlist_next_rcu(last), n);
     143             :         } else {
     144             :                 hlist_nulls_add_head_rcu(n, h);
     145             :         }
     146             : }
     147             : 
     148             : /* after that hlist_nulls_del will work */
     149             : static inline void hlist_nulls_add_fake(struct hlist_nulls_node *n)
     150             : {
     151             :         n->pprev = &n->next;
     152             :         n->next = (struct hlist_nulls_node *)NULLS_MARKER(NULL);
     153             : }
     154             : 
     155             : /**
     156             :  * hlist_nulls_for_each_entry_rcu - iterate over rcu list of given type
     157             :  * @tpos:       the type * to use as a loop cursor.
     158             :  * @pos:        the &struct hlist_nulls_node to use as a loop cursor.
     159             :  * @head:       the head of the list.
     160             :  * @member:     the name of the hlist_nulls_node within the struct.
     161             :  *
     162             :  * The barrier() is needed to make sure compiler doesn't cache first element [1],
     163             :  * as this loop can be restarted [2]
     164             :  * [1] Documentation/core-api/atomic_ops.rst around line 114
     165             :  * [2] Documentation/RCU/rculist_nulls.rst around line 146
     166             :  */
     167             : #define hlist_nulls_for_each_entry_rcu(tpos, pos, head, member)                 \
     168             :         for (({barrier();}),                                                    \
     169             :              pos = rcu_dereference_raw(hlist_nulls_first_rcu(head));            \
     170             :                 (!is_a_nulls(pos)) &&                                           \
     171             :                 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1; }); \
     172             :                 pos = rcu_dereference_raw(hlist_nulls_next_rcu(pos)))
     173             : 
     174             : /**
     175             :  * hlist_nulls_for_each_entry_safe -
     176             :  *   iterate over list of given type safe against removal of list entry
     177             :  * @tpos:       the type * to use as a loop cursor.
     178             :  * @pos:        the &struct hlist_nulls_node to use as a loop cursor.
     179             :  * @head:       the head of the list.
     180             :  * @member:     the name of the hlist_nulls_node within the struct.
     181             :  */
     182             : #define hlist_nulls_for_each_entry_safe(tpos, pos, head, member)                \
     183             :         for (({barrier();}),                                                    \
     184             :              pos = rcu_dereference_raw(hlist_nulls_first_rcu(head));            \
     185             :                 (!is_a_nulls(pos)) &&                                           \
     186             :                 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member);        \
     187             :                    pos = rcu_dereference_raw(hlist_nulls_next_rcu(pos)); 1; });)
     188             : #endif
     189             : #endif