xref: /linux/tools/testing/selftests/bpf/progs/linked_list.c (revision a3a81d247651218e47153f2d2afd7aee236726fd) 
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 #define MAX_LIST_CLEAR_NODES 256
294 
295 static __always_inline
296 int clear_list(struct bpf_spin_lock *lock, struct bpf_list_head *head)
297 {
298 	struct bpf_list_node *n;
299 	int i;
300 
301 	for (i = 0; i < MAX_LIST_CLEAR_NODES; i++) {
302 		bpf_spin_lock(lock);
303 		n = bpf_list_pop_front(head);
304 		bpf_spin_unlock(lock);
305 		if (!n)
306 			return 0;
307 		bpf_obj_drop(container_of(n, struct foo, node2));
308 	}
309 	return 1;
310 }
311 
312 SEC("syscall")
313 int clear_map_list(void *ctx)
314 {
315 	struct map_value *v;
316 
317 	v = bpf_map_lookup_elem(&array_map, &(int){0});
318 	if (!v)
319 		return 1;
320 	return clear_list(&v->lock, &v->head);
321 }
322 
323 SEC("syscall")
324 int clear_inner_map_list(void *ctx)
325 {
326 	struct map_value *v;
327 	void *map;
328 
329 	map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
330 	if (!map)
331 		return 1;
332 	v = bpf_map_lookup_elem(map, &(int){0});
333 	if (!v)
334 		return 1;
335 	return clear_list(&v->lock, &v->head);
336 }
337 
338 SEC("syscall")
339 int clear_global_list(void *ctx)
340 {
341 	return clear_list(&glock, &ghead);
342 }
343 
344 SEC("syscall")
345 int clear_global_nested_list(void *ctx)
346 {
347 	return clear_list(&ghead_nested.inner.lock, &ghead_nested.inner.head);
348 }
349 
350 SEC("syscall")
351 int clear_global_array_list(void *ctx)
352 {
353 	int ret;
354 
355 	ret = clear_list(&glock_c, &ghead_array[0]);
356 	if (ret)
357 		return ret;
358 	ret = clear_list(&glock_c, &ghead_array[1]);
359 	if (ret)
360 		return ret;
361 	return clear_list(&glock_c, &ghead_array_one[0]);
362 }
363 
364 SEC("tc")
365 int map_list_push_pop(void *ctx)
366 {
367 	struct map_value *v;
368 
369 	v = bpf_map_lookup_elem(&array_map, &(int){0});
370 	if (!v)
371 		return 1;
372 	return test_list_push_pop(&v->lock, &v->head);
373 }
374 
375 SEC("tc")
376 int inner_map_list_push_pop(void *ctx)
377 {
378 	struct map_value *v;
379 	void *map;
380 
381 	map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
382 	if (!map)
383 		return 1;
384 	v = bpf_map_lookup_elem(map, &(int){0});
385 	if (!v)
386 		return 1;
387 	return test_list_push_pop(&v->lock, &v->head);
388 }
389 
390 SEC("tc")
391 int global_list_push_pop(void *ctx)
392 {
393 	return test_list_push_pop(&glock, &ghead);
394 }
395 
396 SEC("tc")
397 int global_list_push_pop_nested(void *ctx)
398 {
399 	return test_list_push_pop(&ghead_nested.inner.lock, &ghead_nested.inner.head);
400 }
401 
402 SEC("tc")
403 int global_list_array_push_pop(void *ctx)
404 {
405 	int r;
406 
407 	r = test_list_push_pop(&glock_c, &ghead_array[0]);
408 	if (r)
409 		return r;
410 
411 	r = test_list_push_pop(&glock_c, &ghead_array[1]);
412 	if (r)
413 		return r;
414 
415 	/* Arrays with only one element is a special case, being treated
416 	 * just like a bpf_list_head variable by the verifier, not an
417 	 * array.
418 	 */
419 	return test_list_push_pop(&glock_c, &ghead_array_one[0]);
420 }
421 
422 SEC("tc")
423 int map_list_push_pop_multiple(void *ctx)
424 {
425 	struct map_value *v;
426 
427 	v = bpf_map_lookup_elem(&array_map, &(int){0});
428 	if (!v)
429 		return 1;
430 	return test_list_push_pop_multiple(&v->lock, &v->head);
431 }
432 
433 SEC("tc")
434 int inner_map_list_push_pop_multiple(void *ctx)
435 {
436 	struct map_value *v;
437 	void *map;
438 
439 	map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
440 	if (!map)
441 		return 1;
442 	v = bpf_map_lookup_elem(map, &(int){0});
443 	if (!v)
444 		return 1;
445 	return test_list_push_pop_multiple(&v->lock, &v->head);
446 }
447 
448 SEC("tc")
449 int global_list_push_pop_multiple(void *ctx)
450 {
451 	int ret;
452 
453 	ret = list_push_pop_multiple(&glock, &ghead, false);
454 	if (ret)
455 		return ret;
456 	return list_push_pop_multiple(&glock, &ghead, true);
457 }
458 
459 SEC("tc")
460 int map_list_in_list(void *ctx)
461 {
462 	struct map_value *v;
463 
464 	v = bpf_map_lookup_elem(&array_map, &(int){0});
465 	if (!v)
466 		return 1;
467 	return test_list_in_list(&v->lock, &v->head);
468 }
469 
470 SEC("tc")
471 int inner_map_list_in_list(void *ctx)
472 {
473 	struct map_value *v;
474 	void *map;
475 
476 	map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
477 	if (!map)
478 		return 1;
479 	v = bpf_map_lookup_elem(map, &(int){0});
480 	if (!v)
481 		return 1;
482 	return test_list_in_list(&v->lock, &v->head);
483 }
484 
485 SEC("tc")
486 int global_list_in_list(void *ctx)
487 {
488 	return test_list_in_list(&glock, &ghead);
489 }
490 
491 char _license[] SEC("license") = "GPL";
492