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) (int)(sizeof(x) / sizeof((x)[0]))
10#endif
11
12#include "linked_list.h"
13
14static __always_inline
15int 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, node2));
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, node2));
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->node2);
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, node2);
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->node2);
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, node2);
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, node2));
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, node2));
89 return 10;
90 }
91 return 0;
92}
93
94
95static __always_inline
96int 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[200], *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]->node2);
123 bpf_list_push_front(head, &f[i + 1]->node2);
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, node2);
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->node2);
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, node2);
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, node2));
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, node2));
172 return 8;
173 }
174 return 0;
175}
176
177static __always_inline
178int 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->node2);
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, node2);
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
247static __always_inline
248int 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
258static __always_inline
259int 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
269static __always_inline
270int 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
280SEC("tc")
281int 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
291SEC("tc")
292int 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
306SEC("tc")
307int global_list_push_pop(void *ctx)
308{
309 return test_list_push_pop(lock: &glock, head: &ghead);
310}
311
312SEC("tc")
313int map_list_push_pop_multiple(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 test_list_push_pop_multiple(&v->lock, &v->head);
321}
322
323SEC("tc")
324int inner_map_list_push_pop_multiple(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 test_list_push_pop_multiple(&v->lock, &v->head);
336}
337
338SEC("tc")
339int global_list_push_pop_multiple(void *ctx)
340{
341 int ret;
342
343 ret = list_push_pop_multiple(&glock, &ghead, false);
344 if (ret)
345 return ret;
346 return list_push_pop_multiple(&glock, &ghead, true);
347}
348
349SEC("tc")
350int map_list_in_list(void *ctx)
351{
352 struct map_value *v;
353
354 v = bpf_map_lookup_elem(&array_map, &(int){0});
355 if (!v)
356 return 1;
357 return test_list_in_list(&v->lock, &v->head);
358}
359
360SEC("tc")
361int inner_map_list_in_list(void *ctx)
362{
363 struct map_value *v;
364 void *map;
365
366 map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
367 if (!map)
368 return 1;
369 v = bpf_map_lookup_elem(map, &(int){0});
370 if (!v)
371 return 1;
372 return test_list_in_list(&v->lock, &v->head);
373}
374
375SEC("tc")
376int global_list_in_list(void *ctx)
377{
378 return test_list_in_list(lock: &glock, head: &ghead);
379}
380
381char _license[] SEC("license") = "GPL";
382

source code of linux/tools/testing/selftests/bpf/progs/linked_list.c