GNU Linux-libre 6.9.2-gnu
[releases.git] / include / linux / rculist_nulls.h
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 static inline void hlist_nulls_del_init_rcu(struct hlist_nulls_node *n)
34 {
35         if (!hlist_nulls_unhashed(n)) {
36                 __hlist_nulls_del(n);
37                 WRITE_ONCE(n->pprev, NULL);
38         }
39 }
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 static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
100                                         struct hlist_nulls_head *h)
101 {
102         struct hlist_nulls_node *first = h->first;
103
104         WRITE_ONCE(n->next, first);
105         WRITE_ONCE(n->pprev, &h->first);
106         rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
107         if (!is_a_nulls(first))
108                 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                 WRITE_ONCE(n->next, last->next);
141                 n->pprev = &last->next;
142                 rcu_assign_pointer(hlist_nulls_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/memory-barriers.txt around line 1533
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