1/* @title: RCU list operations */
2#pragma once
3#include <compiler/atomic.h>
4#include <compiler/core.h>
5#include <container_of.h>
6#include <stdbool.h>
7#include <stddef.h>
8#include <structures/hlist.h>
9#include <structures/list.h>
10#include <sync/rcu.h>
11
12static inline void list_node_init_rcu(struct list_node *n) {
13 ca_write_once(n->next, n);
14 ca_write_once(n->prev, n);
15}
16
17static inline void list_head_init_rcu(struct list_head *h) {
18 list_node_init_rcu(n: &h->root);
19}
20
21#define list_next_rcu(list) (*((struct list_node **) &(list)->next))
22#define list_bidir_prev_rcu(list) (*((struct list_node **) &(list)->prev))
23#define list_tail_rcu(head) (*((struct list_node **) &(list_root(head))->prev))
24
25static inline void list_node_link_between_rcu(struct list_node *new,
26 struct list_node *prev,
27 struct list_node *next) {
28 list_add_check(new, prev, next);
29
30 new->next = next;
31 new->prev = prev;
32 rcu_assign_pointer(list_next_rcu(prev), new);
33 next->prev = new;
34}
35
36static inline void list_head_push_front_rcu(struct list_head *h,
37 struct list_node *n) {
38 list_node_link_between_rcu(new: n, prev: &h->root, next: h->root.next);
39}
40
41static inline void list_head_push_back_rcu(struct list_head *h,
42 struct list_node *n) {
43 list_node_link_between_rcu(new: n, prev: h->root.prev, next: &h->root);
44}
45
46/* TODO: Consider poisoning (not just NULL) and also maybe using
47 * an address_space for RCU lists */
48static inline void list_node_delete_rcu(struct list_node *n) {
49 list_del_check(entry: n);
50
51 list_node_unlink_between(prev: n->prev, next: n->next);
52 n->prev = NULL;
53}
54
55static inline void list_node_delete_bidir_rcu(struct list_node *n) {
56 list_del_check(entry: n);
57
58 list_node_unlink_between(prev: n->prev, next: n->next);
59}
60
61static inline void list_node_replace_rcu(struct list_node *old,
62 struct list_node *new) {
63 new->next = old->next;
64 new->prev = old->prev;
65 rcu_assign_pointer(list_next_rcu(new->prev), new);
66 new->next->prev = new;
67 old->prev = NULL;
68}
69
70static inline void list_splice_between_rcu(const struct list_node *list,
71 struct list_node *prev,
72 struct list_node *next) {
73 list_splice_check(list, prev, next);
74
75 struct list_node *first = list->next;
76 struct list_node *last = list->prev;
77
78 last->next = next;
79 first->prev = prev;
80 next->prev = last;
81 rcu_assign_pointer(list_next_rcu(prev), first);
82}
83
84/* copy src onto the front of dst */
85static inline void list_head_splice_front_rcu(struct list_head *dst,
86 struct list_head *src) {
87 if (!list_head_empty(h: src))
88 list_splice_between_rcu(list: &src->root, prev: &dst->root, next: dst->root.next);
89}
90
91static inline void list_splice_between_init_rcu(struct list_node *list,
92 struct list_node *prev,
93 struct list_node *next,
94 void (*sync)(void)) {
95 struct list_node *first = list->next;
96 struct list_node *last = list->prev;
97
98 list_node_init_rcu(n: list);
99
100 if (sync)
101 sync();
102
103 last->next = next;
104 rcu_assign_pointer(list_next_rcu(prev), first);
105 first->prev = prev;
106 next->prev = last;
107}
108
109static inline void list_head_splice_front_init_rcu(struct list_head *dst,
110 struct list_head *src,
111 void (*sync)(void)) {
112 if (!list_head_empty(h: src))
113 list_splice_between_init_rcu(list: &src->root, prev: &dst->root, next: dst->root.next,
114 sync);
115}
116
117static inline void list_head_splice_back_init_rcu(struct list_head *dst,
118 struct list_head *src,
119 void (*sync)(void)) {
120 if (!list_head_empty(h: src))
121 list_splice_between_init_rcu(list: &src->root, prev: dst->root.prev, next: &dst->root,
122 sync);
123}
124
125#define list_entry_rcu(ptr, type, member) \
126 container_of(rcu_dereference(ptr), type, member)
127
128#define list_first_or_null_rcu(ptr, type, member) \
129 ({ \
130 __auto_type __ptr = list_root(ptr); \
131 struct list_node *__next = rcu_dereference(__ptr->next); \
132 cc_likely(__ptr != __next) ? list_entry(__next, type, member) : NULL; \
133 })
134
135#define list_next_or_null_rcu(head, ptr, type, member) \
136 ({ \
137 __auto_type __head = list_root(head); \
138 struct list_node *__ptr = (ptr); \
139 struct list_node *__next = rcu_dereference(__ptr->next); \
140 cc_likely(__next != __head) ? list_entry(__next, type, member) : NULL; \
141 })
142
143#define list_for_each_rcu(pos, head) \
144 for (pos = rcu_dereference(list_root(head)->next); pos != list_root(head); \
145 pos = rcu_dereference(pos->next))
146
147#define list_for_each_entry_rcu(pos, head, member) \
148 for (pos = list_entry_rcu(list_root(head)->next, typeof(*pos), member); \
149 &pos->member != list_root(head); \
150 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
151
152#define list_for_each_entry_continue_rcu(pos, head, member) \
153 for (pos = list_entry_rcu(pos->member.next, typeof(*pos), member); \
154 &pos->member != list_root(head); \
155 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
156
157#define list_for_each_entry_from_rcu(pos, head, member) \
158 for (; &pos->member != list_root(head); \
159 pos = list_entry_rcu(pos->member.next, typeof(*pos), member))
160
161#define hlist_first_rcu(head) (*((struct hlist_node **) &(head)->first))
162#define hlist_next_rcu(node) (*((struct hlist_node **) &(node)->next))
163#define hlist_pprev_rcu(node) (*((struct hlist_node **) ((node)->pprev)))
164
165#define hlist_entry_rcu(ptr, type, member) \
166 container_of(rcu_dereference(ptr), type, member)
167
168static inline void hlist_node_unlink(struct hlist_node *n) {
169 struct hlist_node *next = n->next;
170 struct hlist_node **pprev = n->pprev;
171
172 *pprev = next;
173 if (next)
174 next->pprev = pprev;
175}
176
177static inline void hlist_del_rcu(struct hlist_node *n) {
178 hlist_node_unlink(n);
179 n->pprev = NULL;
180}
181
182static inline void hlist_del_init_rcu(struct hlist_node *n) {
183 if (!hlist_unhashed(h: n)) {
184 hlist_node_unlink(n);
185 ca_write_once(n->pprev, NULL);
186 }
187}
188
189static inline void hlist_replace_rcu(struct hlist_node *old,
190 struct hlist_node *new) {
191 struct hlist_node *next = old->next;
192
193 new->next = next;
194 new->pprev = old->pprev;
195 rcu_assign_pointer(*(struct hlist_node **) new->pprev, new);
196 if (next)
197 new->next->pprev = &new->next;
198 old->pprev = NULL;
199}
200
201static inline void hlists_swap_heads_rcu(struct hlist_head *left,
202 struct hlist_head *right) {
203 struct hlist_node *node1 = left->first;
204 struct hlist_node *node2 = right->first;
205
206 rcu_assign_pointer(left->first, node2);
207 rcu_assign_pointer(right->first, node1);
208 if (node2)
209 ca_write_once(node2->pprev, &left->first);
210 if (node1)
211 ca_write_once(node1->pprev, &right->first);
212}
213
214static inline void hlist_add_head_rcu(struct hlist_node *n,
215 struct hlist_head *h) {
216 struct hlist_node *first = h->first;
217
218 n->next = first;
219 n->pprev = &h->first;
220 rcu_assign_pointer(hlist_first_rcu(h), n);
221 if (first)
222 first->pprev = &n->next;
223}
224
225static inline void hlist_add_tail_rcu(struct hlist_node *n,
226 struct hlist_head *h) {
227 struct hlist_node *i, *last = NULL;
228
229 for (i = h->first; i; i = i->next)
230 last = i;
231
232 if (last) {
233 n->next = last->next;
234 n->pprev = &last->next;
235 rcu_assign_pointer(hlist_next_rcu(last), n);
236 } else {
237 hlist_add_head_rcu(n, h);
238 }
239}
240
241static inline void hlist_add_before_rcu(struct hlist_node *n,
242 struct hlist_node *next) {
243 n->pprev = next->pprev;
244 n->next = next;
245 rcu_assign_pointer(hlist_pprev_rcu(n), n);
246 next->pprev = &n->next;
247}
248
249static inline void hlist_add_behind_rcu(struct hlist_node *n,
250 struct hlist_node *prev) {
251 n->next = prev->next;
252 n->pprev = &prev->next;
253 rcu_assign_pointer(hlist_next_rcu(prev), n);
254 if (n->next)
255 n->next->pprev = &n->next;
256}
257
258#define hlist_for_each_node_rcu(pos, head) \
259 for (pos = rcu_dereference(hlist_first_rcu(head)); pos; \
260 pos = rcu_dereference(hlist_next_rcu(pos)))
261
262#define hlist_for_each_entry_rcu(pos, head, member) \
263 for (pos = hlist_entry_safe(rcu_dereference(hlist_first_rcu(head)), \
264 typeof(*(pos)), member); \
265 pos; pos = hlist_entry_safe( \
266 rcu_dereference(hlist_next_rcu(&(pos)->member)), \
267 typeof(*(pos)), member))
268
269#define hlist_for_each_entry_continue_rcu(pos, member) \
270 for (pos = \
271 hlist_entry_safe(rcu_dereference(hlist_next_rcu(&(pos)->member)), \
272 typeof(*(pos)), member); \
273 pos; pos = hlist_entry_safe( \
274 rcu_dereference(hlist_next_rcu(&(pos)->member)), \
275 typeof(*(pos)), member))
276
277#define hlist_for_each_entry_from_rcu(pos, member) \
278 for (; pos; pos = hlist_entry_safe( \
279 rcu_dereference(hlist_next_rcu(&(pos)->member)), \
280 typeof(*(pos)), member))
281