1 // SPDX-License-Identifier: GPL-2.0
2 #include <vmlinux.h>
3 #include <bpf/bpf_tracing.h>
4 #include <bpf/bpf_helpers.h>
5 #include <bpf/bpf_core_read.h>
6 #include "bpf_experimental.h"
7 #include "bpf_misc.h"
8
9 #include "linked_list.h"
10
11 struct head_nested_inner {
12 struct bpf_spin_lock lock;
13 struct bpf_list_head head __contains(foo, node2);
14 };
15
16 struct head_nested {
17 int dummy;
18 struct head_nested_inner inner;
19 };
20
21 private(C) struct bpf_spin_lock glock_c;
22 private(C) struct bpf_list_head ghead_array[2] __contains(foo, node2);
23 private(C) struct bpf_list_head ghead_array_one[1] __contains(foo, node2);
24
25 private(D) struct head_nested ghead_nested;
26
27 static __always_inline
28 int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool leave_in_map)
29 {
30 struct bpf_list_node *n;
31 struct foo *f;
32
33 f = bpf_obj_new(typeof(*f));
34 if (!f)
35 return 2;
36
37 bpf_spin_lock(lock);
38 n = bpf_list_pop_front(head);
39 bpf_spin_unlock(lock);
40 if (n) {
41 bpf_obj_drop(container_of(n, struct foo, node2));
42 bpf_obj_drop(f);
43 return 3;
44 }
45
46 bpf_spin_lock(lock);
47 n = bpf_list_pop_back(head);
48 bpf_spin_unlock(lock);
49 if (n) {
50 bpf_obj_drop(container_of(n, struct foo, node2));
51 bpf_obj_drop(f);
52 return 4;
53 }
54
55
56 bpf_spin_lock(lock);
57 f->data = 42;
58 bpf_list_push_front(head, &f->node2);
59 bpf_spin_unlock(lock);
60 if (leave_in_map)
61 return 0;
62 bpf_spin_lock(lock);
63 n = bpf_list_pop_back(head);
64 bpf_spin_unlock(lock);
65 if (!n)
66 return 5;
67 f = container_of(n, struct foo, node2);
68 if (f->data != 42) {
69 bpf_obj_drop(f);
70 return 6;
71 }
72
73 bpf_spin_lock(lock);
74 f->data = 13;
75 bpf_list_push_front(head, &f->node2);
76 bpf_spin_unlock(lock);
77 bpf_spin_lock(lock);
78 n = bpf_list_pop_front(head);
79 bpf_spin_unlock(lock);
80 if (!n)
81 return 7;
82 f = container_of(n, struct foo, node2);
83 if (f->data != 13) {
84 bpf_obj_drop(f);
85 return 8;
86 }
87 bpf_obj_drop(f);
88
89 bpf_spin_lock(lock);
90 n = bpf_list_pop_front(head);
91 bpf_spin_unlock(lock);
92 if (n) {
93 bpf_obj_drop(container_of(n, struct foo, node2));
94 return 9;
95 }
96
97 bpf_spin_lock(lock);
98 n = bpf_list_pop_back(head);
99 bpf_spin_unlock(lock);
100 if (n) {
101 bpf_obj_drop(container_of(n, struct foo, node2));
102 return 10;
103 }
104 return 0;
105 }
106
107
108 static __always_inline
109 int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool leave_in_map)
110 {
111 struct bpf_list_node *n;
112 struct foo *f[200], *pf;
113 int i;
114
115 /* Loop following this check adds nodes 2-at-a-time in order to
116 * validate multiple release_on_unlock release logic
117 */
118 if (ARRAY_SIZE(f) % 2)
119 return 10;
120
121 for (i = 0; i < ARRAY_SIZE(f); i += 2) {
122 f[i] = bpf_obj_new(typeof(**f));
123 if (!f[i])
124 return 2;
125 f[i]->data = i;
126
127 f[i + 1] = bpf_obj_new(typeof(**f));
128 if (!f[i + 1]) {
129 bpf_obj_drop(f[i]);
130 return 9;
131 }
132 f[i + 1]->data = i + 1;
133
134 bpf_spin_lock(lock);
135 bpf_list_push_front(head, &f[i]->node2);
136 bpf_list_push_front(head, &f[i + 1]->node2);
137 bpf_spin_unlock(lock);
138 }
139
140 for (i = 0; i < ARRAY_SIZE(f); i++) {
141 bpf_spin_lock(lock);
142 n = bpf_list_pop_front(head);
143 bpf_spin_unlock(lock);
144 if (!n)
145 return 3;
146 pf = container_of(n, struct foo, node2);
147 if (pf->data != (ARRAY_SIZE(f) - i - 1)) {
148 bpf_obj_drop(pf);
149 return 4;
150 }
151 bpf_spin_lock(lock);
152 bpf_list_push_back(head, &pf->node2);
153 bpf_spin_unlock(lock);
154 }
155
156 if (leave_in_map)
157 return 0;
158
159 for (i = 0; i < ARRAY_SIZE(f); i++) {
160 bpf_spin_lock(lock);
161 n = bpf_list_pop_back(head);
162 bpf_spin_unlock(lock);
163 if (!n)
164 return 5;
165 pf = container_of(n, struct foo, node2);
166 if (pf->data != i) {
167 bpf_obj_drop(pf);
168 return 6;
169 }
170 bpf_obj_drop(pf);
171 }
172 bpf_spin_lock(lock);
173 n = bpf_list_pop_back(head);
174 bpf_spin_unlock(lock);
175 if (n) {
176 bpf_obj_drop(container_of(n, struct foo, node2));
177 return 7;
178 }
179
180 bpf_spin_lock(lock);
181 n = bpf_list_pop_front(head);
182 bpf_spin_unlock(lock);
183 if (n) {
184 bpf_obj_drop(container_of(n, struct foo, node2));
185 return 8;
186 }
187 return 0;
188 }
189
190 static __always_inline
191 int list_in_list(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool leave_in_map)
192 {
193 struct bpf_list_node *n;
194 struct bar *ba[8], *b;
195 struct foo *f;
196 int i;
197
198 f = bpf_obj_new(typeof(*f));
199 if (!f)
200 return 2;
201 for (i = 0; i < ARRAY_SIZE(ba); i++) {
202 b = bpf_obj_new(typeof(*b));
203 if (!b) {
204 bpf_obj_drop(f);
205 return 3;
206 }
207 b->data = i;
208 bpf_spin_lock(&f->lock);
209 bpf_list_push_back(&f->head, &b->node);
210 bpf_spin_unlock(&f->lock);
211 }
212
213 bpf_spin_lock(lock);
214 f->data = 42;
215 bpf_list_push_front(head, &f->node2);
216 bpf_spin_unlock(lock);
217
218 if (leave_in_map)
219 return 0;
220
221 bpf_spin_lock(lock);
222 n = bpf_list_pop_front(head);
223 bpf_spin_unlock(lock);
224 if (!n)
225 return 4;
226 f = container_of(n, struct foo, node2);
227 if (f->data != 42) {
228 bpf_obj_drop(f);
229 return 5;
230 }
231
232 for (i = 0; i < ARRAY_SIZE(ba); i++) {
233 bpf_spin_lock(&f->lock);
234 n = bpf_list_pop_front(&f->head);
235 bpf_spin_unlock(&f->lock);
236 if (!n) {
237 bpf_obj_drop(f);
238 return 6;
239 }
240 b = container_of(n, struct bar, node);
241 if (b->data != i) {
242 bpf_obj_drop(f);
243 bpf_obj_drop(b);
244 return 7;
245 }
246 bpf_obj_drop(b);
247 }
248 bpf_spin_lock(&f->lock);
249 n = bpf_list_pop_front(&f->head);
250 bpf_spin_unlock(&f->lock);
251 if (n) {
252 bpf_obj_drop(f);
253 bpf_obj_drop(container_of(n, struct bar, node));
254 return 8;
255 }
256 bpf_obj_drop(f);
257 return 0;
258 }
259
260 static __always_inline
261 int test_list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head)
262 {
263 int ret;
264
265 ret = list_push_pop(lock, head, false);
266 if (ret)
267 return ret;
268 return list_push_pop(lock, head, true);
269 }
270
271 static __always_inline
272 int test_list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *head)
273 {
274 int ret;
275
276 ret = list_push_pop_multiple(lock, head, false);
277 if (ret)
278 return ret;
279 return list_push_pop_multiple(lock, head, true);
280 }
281
282 static __always_inline
283 int test_list_in_list(struct bpf_spin_lock *lock, struct bpf_list_head *head)
284 {
285 int ret;
286
287 ret = list_in_list(lock, head, false);
288 if (ret)
289 return ret;
290 return list_in_list(lock, head, true);
291 }
292
293 SEC("tc")
294 int map_list_push_pop(void *ctx)
295 {
296 struct map_value *v;
297
298 v = bpf_map_lookup_elem(&array_map, &(int){0});
299 if (!v)
300 return 1;
301 return test_list_push_pop(&v->lock, &v->head);
302 }
303
304 SEC("tc")
305 int inner_map_list_push_pop(void *ctx)
306 {
307 struct map_value *v;
308 void *map;
309
310 map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
311 if (!map)
312 return 1;
313 v = bpf_map_lookup_elem(map, &(int){0});
314 if (!v)
315 return 1;
316 return test_list_push_pop(&v->lock, &v->head);
317 }
318
319 SEC("tc")
320 int global_list_push_pop(void *ctx)
321 {
322 return test_list_push_pop(&glock, &ghead);
323 }
324
325 SEC("tc")
326 int global_list_push_pop_nested(void *ctx)
327 {
328 return test_list_push_pop(&ghead_nested.inner.lock, &ghead_nested.inner.head);
329 }
330
331 SEC("tc")
332 int global_list_array_push_pop(void *ctx)
333 {
334 int r;
335
336 r = test_list_push_pop(&glock_c, &ghead_array[0]);
337 if (r)
338 return r;
339
340 r = test_list_push_pop(&glock_c, &ghead_array[1]);
341 if (r)
342 return r;
343
344 /* Arrays with only one element is a special case, being treated
345 * just like a bpf_list_head variable by the verifier, not an
346 * array.
347 */
348 return test_list_push_pop(&glock_c, &ghead_array_one[0]);
349 }
350
351 SEC("tc")
352 int map_list_push_pop_multiple(void *ctx)
353 {
354 struct map_value *v;
355
356 v = bpf_map_lookup_elem(&array_map, &(int){0});
357 if (!v)
358 return 1;
359 return test_list_push_pop_multiple(&v->lock, &v->head);
360 }
361
362 SEC("tc")
363 int inner_map_list_push_pop_multiple(void *ctx)
364 {
365 struct map_value *v;
366 void *map;
367
368 map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
369 if (!map)
370 return 1;
371 v = bpf_map_lookup_elem(map, &(int){0});
372 if (!v)
373 return 1;
374 return test_list_push_pop_multiple(&v->lock, &v->head);
375 }
376
377 SEC("tc")
378 int global_list_push_pop_multiple(void *ctx)
379 {
380 int ret;
381
382 ret = list_push_pop_multiple(&glock, &ghead, false);
383 if (ret)
384 return ret;
385 return list_push_pop_multiple(&glock, &ghead, true);
386 }
387
388 SEC("tc")
389 int map_list_in_list(void *ctx)
390 {
391 struct map_value *v;
392
393 v = bpf_map_lookup_elem(&array_map, &(int){0});
394 if (!v)
395 return 1;
396 return test_list_in_list(&v->lock, &v->head);
397 }
398
399 SEC("tc")
400 int inner_map_list_in_list(void *ctx)
401 {
402 struct map_value *v;
403 void *map;
404
405 map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
406 if (!map)
407 return 1;
408 v = bpf_map_lookup_elem(map, &(int){0});
409 if (!v)
410 return 1;
411 return test_list_in_list(&v->lock, &v->head);
412 }
413
414 SEC("tc")
415 int global_list_in_list(void *ctx)
416 {
417 return test_list_in_list(&glock, &ghead);
418 }
419
420 char _license[] SEC("license") = "GPL";
421
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.