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