xref: /linux/tools/testing/selftests/bpf/progs/linked_list.c (revision c532de5a67a70f8533d495f8f2aaa9a0491c3ad0) 
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