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
 11struct head_nested_inner {
 12	struct bpf_spin_lock lock;
 13	struct bpf_list_head head __contains(foo, node2);
 14};
 15
 16struct head_nested {
 17	int dummy;
 18	struct head_nested_inner inner;
 19};
 20
 21private(C) struct bpf_spin_lock glock_c;
 22private(C) struct bpf_list_head ghead_array[2] __contains(foo, node2);
 23private(C) struct bpf_list_head ghead_array_one[1] __contains(foo, node2);
 24
 25private(D) struct head_nested ghead_nested;
 26
 27static __always_inline
 28int 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
108static __always_inline
109int 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
190static __always_inline
191int 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
260static __always_inline
261int 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
271static __always_inline
272int 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
282static __always_inline
283int 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
293SEC("tc")
294int 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
304SEC("tc")
305int 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
319SEC("tc")
320int global_list_push_pop(void *ctx)
321{
322	return test_list_push_pop(&glock, &ghead);
323}
324
325SEC("tc")
326int global_list_push_pop_nested(void *ctx)
327{
328	return test_list_push_pop(&ghead_nested.inner.lock, &ghead_nested.inner.head);
329}
330
331SEC("tc")
332int 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
351SEC("tc")
352int 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
362SEC("tc")
363int 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
377SEC("tc")
378int 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
388SEC("tc")
389int 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
399SEC("tc")
400int 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
414SEC("tc")
415int global_list_in_list(void *ctx)
416{
417	return test_list_in_list(&glock, &ghead);
418}
419
420char _license[] SEC("license") = "GPL";