1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */
3
4 #include <vmlinux.h>
5 #include <bpf/bpf_tracing.h>
6 #include <bpf/bpf_helpers.h>
7 #include <bpf/bpf_core_read.h>
8 #include "bpf_misc.h"
9 #include "bpf_experimental.h"
10
11 extern void bpf_rcu_read_lock(void) __ksym;
12 extern void bpf_rcu_read_unlock(void) __ksym;
13
14 struct node_data {
15 long key;
16 long list_data;
17 struct bpf_rb_node r;
18 struct bpf_list_node l;
19 struct bpf_refcount ref;
20 };
21
22 struct map_value {
23 struct node_data __kptr *node;
24 };
25
26 struct node_refcount_only {
27 long key;
28 struct bpf_refcount refcount;
29 };
30
31 struct map_value_refcount_only {
32 struct node_refcount_only __kptr *node;
33 };
34
35 struct {
36 __uint(type, BPF_MAP_TYPE_ARRAY);
37 __type(key, int);
38 __type(value, struct map_value);
39 __uint(max_entries, 2);
40 } stashed_nodes SEC(".maps");
41
42 struct {
43 __uint(type, BPF_MAP_TYPE_ARRAY);
44 __type(key, int);
45 __type(value, struct map_value_refcount_only);
46 __uint(max_entries, 1);
47 } stashed_refcount_only SEC(".maps");
48
49 struct node_acquire {
50 long key;
51 long data;
52 struct bpf_rb_node node;
53 struct bpf_refcount refcount;
54 };
55
56 #define private(name) SEC(".bss." #name) __hidden __attribute__((aligned(8)))
57 private(A) struct bpf_spin_lock lock;
58 private(A) struct bpf_rb_root root __contains(node_data, r);
59 private(A) struct bpf_list_head head __contains(node_data, l);
60
61 private(B) struct bpf_spin_lock alock;
62 private(B) struct bpf_rb_root aroot __contains(node_acquire, node);
63
64 private(C) struct bpf_spin_lock block;
65 private(C) struct bpf_rb_root broot __contains(node_data, r);
66
less(struct bpf_rb_node * node_a,const struct bpf_rb_node * node_b)67 static bool less(struct bpf_rb_node *node_a, const struct bpf_rb_node *node_b)
68 {
69 struct node_data *a;
70 struct node_data *b;
71
72 a = container_of(node_a, struct node_data, r);
73 b = container_of(node_b, struct node_data, r);
74
75 return a->key < b->key;
76 }
77
less_a(struct bpf_rb_node * a,const struct bpf_rb_node * b)78 static bool less_a(struct bpf_rb_node *a, const struct bpf_rb_node *b)
79 {
80 struct node_acquire *node_a;
81 struct node_acquire *node_b;
82
83 node_a = container_of(a, struct node_acquire, node);
84 node_b = container_of(b, struct node_acquire, node);
85
86 return node_a->key < node_b->key;
87 }
88
__insert_in_tree_and_list(struct bpf_list_head * head,struct bpf_rb_root * root,struct bpf_spin_lock * lock)89 static long __insert_in_tree_and_list(struct bpf_list_head *head,
90 struct bpf_rb_root *root,
91 struct bpf_spin_lock *lock)
92 {
93 struct node_data *n, *m;
94
95 n = bpf_obj_new(typeof(*n));
96 if (!n)
97 return -1;
98
99 m = bpf_refcount_acquire(n);
100 m->key = 123;
101 m->list_data = 456;
102
103 bpf_spin_lock(lock);
104 if (bpf_rbtree_add(root, &n->r, less)) {
105 /* Failure to insert - unexpected */
106 bpf_spin_unlock(lock);
107 bpf_obj_drop(m);
108 return -2;
109 }
110 bpf_spin_unlock(lock);
111
112 bpf_spin_lock(lock);
113 if (bpf_list_push_front(head, &m->l)) {
114 /* Failure to insert - unexpected */
115 bpf_spin_unlock(lock);
116 return -3;
117 }
118 bpf_spin_unlock(lock);
119 return 0;
120 }
121
__stash_map_insert_tree(int idx,int val,struct bpf_rb_root * root,struct bpf_spin_lock * lock)122 static long __stash_map_insert_tree(int idx, int val, struct bpf_rb_root *root,
123 struct bpf_spin_lock *lock)
124 {
125 struct map_value *mapval;
126 struct node_data *n, *m;
127
128 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
129 if (!mapval)
130 return -1;
131
132 n = bpf_obj_new(typeof(*n));
133 if (!n)
134 return -2;
135
136 n->key = val;
137 m = bpf_refcount_acquire(n);
138
139 n = bpf_kptr_xchg(&mapval->node, n);
140 if (n) {
141 bpf_obj_drop(n);
142 bpf_obj_drop(m);
143 return -3;
144 }
145
146 bpf_spin_lock(lock);
147 if (bpf_rbtree_add(root, &m->r, less)) {
148 /* Failure to insert - unexpected */
149 bpf_spin_unlock(lock);
150 return -4;
151 }
152 bpf_spin_unlock(lock);
153 return 0;
154 }
155
__read_from_tree(struct bpf_rb_root * root,struct bpf_spin_lock * lock,bool remove_from_tree)156 static long __read_from_tree(struct bpf_rb_root *root,
157 struct bpf_spin_lock *lock,
158 bool remove_from_tree)
159 {
160 struct bpf_rb_node *rb;
161 struct node_data *n;
162 long res = -99;
163
164 bpf_spin_lock(lock);
165
166 rb = bpf_rbtree_first(root);
167 if (!rb) {
168 bpf_spin_unlock(lock);
169 return -1;
170 }
171
172 n = container_of(rb, struct node_data, r);
173 res = n->key;
174
175 if (!remove_from_tree) {
176 bpf_spin_unlock(lock);
177 return res;
178 }
179
180 rb = bpf_rbtree_remove(root, rb);
181 bpf_spin_unlock(lock);
182 if (!rb)
183 return -2;
184 n = container_of(rb, struct node_data, r);
185 bpf_obj_drop(n);
186 return res;
187 }
188
__read_from_list(struct bpf_list_head * head,struct bpf_spin_lock * lock,bool remove_from_list)189 static long __read_from_list(struct bpf_list_head *head,
190 struct bpf_spin_lock *lock,
191 bool remove_from_list)
192 {
193 struct bpf_list_node *l;
194 struct node_data *n;
195 long res = -99;
196
197 bpf_spin_lock(lock);
198
199 l = bpf_list_pop_front(head);
200 if (!l) {
201 bpf_spin_unlock(lock);
202 return -1;
203 }
204
205 n = container_of(l, struct node_data, l);
206 res = n->list_data;
207
208 if (!remove_from_list) {
209 if (bpf_list_push_back(head, &n->l)) {
210 bpf_spin_unlock(lock);
211 return -2;
212 }
213 }
214
215 bpf_spin_unlock(lock);
216
217 if (remove_from_list)
218 bpf_obj_drop(n);
219 return res;
220 }
221
__read_from_unstash(int idx)222 static long __read_from_unstash(int idx)
223 {
224 struct node_data *n = NULL;
225 struct map_value *mapval;
226 long val = -99;
227
228 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
229 if (!mapval)
230 return -1;
231
232 n = bpf_kptr_xchg(&mapval->node, n);
233 if (!n)
234 return -2;
235
236 val = n->key;
237 bpf_obj_drop(n);
238 return val;
239 }
240
241 #define INSERT_READ_BOTH(rem_tree, rem_list, desc) \
242 SEC("tc") \
243 __description(desc) \
244 __success __retval(579) \
245 long insert_and_remove_tree_##rem_tree##_list_##rem_list(void *ctx) \
246 { \
247 long err, tree_data, list_data; \
248 \
249 err = __insert_in_tree_and_list(&head, &root, &lock); \
250 if (err) \
251 return err; \
252 \
253 err = __read_from_tree(&root, &lock, rem_tree); \
254 if (err < 0) \
255 return err; \
256 else \
257 tree_data = err; \
258 \
259 err = __read_from_list(&head, &lock, rem_list); \
260 if (err < 0) \
261 return err; \
262 else \
263 list_data = err; \
264 \
265 return tree_data + list_data; \
266 }
267
268 /* After successful insert of struct node_data into both collections:
269 * - it should have refcount = 2
270 * - removing / not removing the node_data from a collection after
271 * reading should have no effect on ability to read / remove from
272 * the other collection
273 */
274 INSERT_READ_BOTH(true, true, "insert_read_both: remove from tree + list");
275 INSERT_READ_BOTH(false, false, "insert_read_both: remove from neither");
276 INSERT_READ_BOTH(true, false, "insert_read_both: remove from tree");
277 INSERT_READ_BOTH(false, true, "insert_read_both: remove from list");
278
279 #undef INSERT_READ_BOTH
280 #define INSERT_READ_BOTH(rem_tree, rem_list, desc) \
281 SEC("tc") \
282 __description(desc) \
283 __success __retval(579) \
284 long insert_and_remove_lf_tree_##rem_tree##_list_##rem_list(void *ctx) \
285 { \
286 long err, tree_data, list_data; \
287 \
288 err = __insert_in_tree_and_list(&head, &root, &lock); \
289 if (err) \
290 return err; \
291 \
292 err = __read_from_list(&head, &lock, rem_list); \
293 if (err < 0) \
294 return err; \
295 else \
296 list_data = err; \
297 \
298 err = __read_from_tree(&root, &lock, rem_tree); \
299 if (err < 0) \
300 return err; \
301 else \
302 tree_data = err; \
303 \
304 return tree_data + list_data; \
305 }
306
307 /* Similar to insert_read_both, but list data is read and possibly removed
308 * first
309 *
310 * Results should be no different than reading and possibly removing rbtree
311 * node first
312 */
313 INSERT_READ_BOTH(true, true, "insert_read_both_list_first: remove from tree + list");
314 INSERT_READ_BOTH(false, false, "insert_read_both_list_first: remove from neither");
315 INSERT_READ_BOTH(true, false, "insert_read_both_list_first: remove from tree");
316 INSERT_READ_BOTH(false, true, "insert_read_both_list_first: remove from list");
317
318 #define INSERT_DOUBLE_READ_AND_DEL(read_fn, read_root, desc) \
319 SEC("tc") \
320 __description(desc) \
321 __success __retval(-1) \
322 long insert_double_##read_fn##_and_del_##read_root(void *ctx) \
323 { \
324 long err, list_data; \
325 \
326 err = __insert_in_tree_and_list(&head, &root, &lock); \
327 if (err) \
328 return err; \
329 \
330 err = read_fn(&read_root, &lock, true); \
331 if (err < 0) \
332 return err; \
333 else \
334 list_data = err; \
335 \
336 err = read_fn(&read_root, &lock, true); \
337 if (err < 0) \
338 return err; \
339 \
340 return err + list_data; \
341 }
342
343 /* Insert into both tree and list, then try reading-and-removing from either twice
344 *
345 * The second read-and-remove should fail on read step since the node has
346 * already been removed
347 */
348 INSERT_DOUBLE_READ_AND_DEL(__read_from_tree, root, "insert_double_del: 2x read-and-del from tree");
349 INSERT_DOUBLE_READ_AND_DEL(__read_from_list, head, "insert_double_del: 2x read-and-del from list");
350
351 #define INSERT_STASH_READ(rem_tree, desc) \
352 SEC("tc") \
353 __description(desc) \
354 __success __retval(84) \
355 long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \
356 { \
357 long err, tree_data, map_data; \
358 \
359 err = __stash_map_insert_tree(0, 42, &root, &lock); \
360 if (err) \
361 return err; \
362 \
363 err = __read_from_tree(&root, &lock, rem_tree); \
364 if (err < 0) \
365 return err; \
366 else \
367 tree_data = err; \
368 \
369 err = __read_from_unstash(0); \
370 if (err < 0) \
371 return err; \
372 else \
373 map_data = err; \
374 \
375 return tree_data + map_data; \
376 }
377
378 /* Stash a refcounted node in map_val, insert same node into tree, then try
379 * reading data from tree then unstashed map_val, possibly removing from tree
380 *
381 * Removing from tree should have no effect on map_val kptr validity
382 */
383 INSERT_STASH_READ(true, "insert_stash_read: remove from tree");
384 INSERT_STASH_READ(false, "insert_stash_read: don't remove from tree");
385
386 SEC("tc")
387 __description("list_empty_test: list empty before add, non-empty after add")
388 __success __retval(0)
list_empty_test(void * ctx)389 int list_empty_test(void *ctx)
390 {
391 struct node_data *node_new;
392
393 bpf_spin_lock(&lock);
394 if (!bpf_list_empty(&head)) {
395 bpf_spin_unlock(&lock);
396 return -1;
397 }
398 bpf_spin_unlock(&lock);
399
400 node_new = bpf_obj_new(typeof(*node_new));
401 if (!node_new)
402 return -2;
403
404 bpf_spin_lock(&lock);
405 bpf_list_push_front(&head, &node_new->l);
406
407 if (bpf_list_empty(&head)) {
408 bpf_spin_unlock(&lock);
409 return -3;
410 }
411 bpf_spin_unlock(&lock);
412 return 0;
413 }
414
__add_in_list(struct bpf_list_head * head,struct bpf_spin_lock * lock)415 static struct node_data *__add_in_list(struct bpf_list_head *head,
416 struct bpf_spin_lock *lock)
417 {
418 struct node_data *node_new, *node_ref;
419
420 node_new = bpf_obj_new(typeof(*node_new));
421 if (!node_new)
422 return NULL;
423
424 node_ref = bpf_refcount_acquire(node_new);
425
426 bpf_spin_lock(lock);
427 bpf_list_push_front(head, &node_new->l);
428 bpf_spin_unlock(lock);
429 return node_ref;
430 }
431
432 SEC("tc")
433 __description("list_is_edge_test1: is_first on first node, is_last on last node")
434 __success __retval(0)
list_is_edge_test1(void * ctx)435 int list_is_edge_test1(void *ctx)
436 {
437 struct node_data *node_first, *node_last;
438 int err = 0;
439
440 node_last = __add_in_list(&head, &lock);
441 if (!node_last)
442 return -1;
443
444 node_first = __add_in_list(&head, &lock);
445 if (!node_first) {
446 bpf_obj_drop(node_last);
447 return -2;
448 }
449
450 bpf_spin_lock(&lock);
451 if (!bpf_list_is_first(&head, &node_first->l)) {
452 err = -3;
453 goto fail;
454 }
455 if (!bpf_list_is_last(&head, &node_last->l))
456 err = -4;
457
458 fail:
459 bpf_spin_unlock(&lock);
460 bpf_obj_drop(node_first);
461 bpf_obj_drop(node_last);
462 return err;
463 }
464
465 SEC("tc")
466 __description("list_is_edge_test2: accept list_front/list_back return value")
467 __success __retval(0)
list_is_edge_test2(void * ctx)468 int list_is_edge_test2(void *ctx)
469 {
470 struct bpf_list_node *front, *back;
471 struct node_data *a, *b;
472 long err = 0;
473
474 a = __add_in_list(&head, &lock);
475 if (!a)
476 return -1;
477
478 b = __add_in_list(&head, &lock);
479 if (!b) {
480 bpf_obj_drop(a);
481 return -2;
482 }
483
484 bpf_spin_lock(&lock);
485 front = bpf_list_front(&head);
486 back = bpf_list_back(&head);
487 if (!front || !back) {
488 err = -3;
489 goto out_unlock;
490 }
491
492 if (!bpf_list_is_first(&head, front) || bpf_list_is_last(&head, front)) {
493 err = -4;
494 goto out_unlock;
495 }
496
497 if (!bpf_list_is_last(&head, back) || bpf_list_is_first(&head, back)) {
498 err = -5;
499 goto out_unlock;
500 }
501
502 out_unlock:
503 bpf_spin_unlock(&lock);
504 bpf_obj_drop(a);
505 bpf_obj_drop(b);
506 return err;
507 }
508
509 SEC("tc")
510 __description("list_is_edge_test3: single node is both first and last")
511 __success __retval(0)
list_is_edge_test3(void * ctx)512 int list_is_edge_test3(void *ctx)
513 {
514 struct node_data *tmp;
515 struct bpf_list_node *node;
516 long err = 0;
517
518 tmp = __add_in_list(&head, &lock);
519 if (!tmp)
520 return -1;
521
522 bpf_spin_lock(&lock);
523 node = bpf_list_front(&head);
524 if (!node) {
525 bpf_spin_unlock(&lock);
526 bpf_obj_drop(tmp);
527 return -2;
528 }
529
530 if (!bpf_list_is_first(&head, node) || !bpf_list_is_last(&head, node))
531 err = -3;
532 bpf_spin_unlock(&lock);
533
534 bpf_obj_drop(tmp);
535 return err;
536 }
537
538 SEC("tc")
539 __description("list_del_test1: del returns removed nodes")
540 __success __retval(0)
list_del_test1(void * ctx)541 int list_del_test1(void *ctx)
542 {
543 struct node_data *node_first, *node_last;
544 struct bpf_list_node *bpf_node_first, *bpf_node_last;
545 int err = 0;
546
547 node_last = __add_in_list(&head, &lock);
548 if (!node_last)
549 return -1;
550
551 node_first = __add_in_list(&head, &lock);
552 if (!node_first) {
553 bpf_obj_drop(node_last);
554 return -2;
555 }
556
557 bpf_spin_lock(&lock);
558 bpf_node_last = bpf_list_del(&head, &node_last->l);
559 bpf_node_first = bpf_list_del(&head, &node_first->l);
560 bpf_spin_unlock(&lock);
561
562 if (bpf_node_first)
563 bpf_obj_drop(container_of(bpf_node_first, struct node_data, l));
564 else
565 err = -3;
566
567 if (bpf_node_last)
568 bpf_obj_drop(container_of(bpf_node_last, struct node_data, l));
569 else
570 err = -4;
571
572 bpf_obj_drop(node_first);
573 bpf_obj_drop(node_last);
574 return err;
575 }
576
577 SEC("tc")
578 __description("list_del_test2: remove an arbitrary node from the list")
579 __success __retval(0)
list_del_test2(void * ctx)580 int list_del_test2(void *ctx)
581 {
582 struct bpf_rb_node *rb;
583 struct bpf_list_node *l;
584 struct node_data *n;
585 long err;
586
587 err = __insert_in_tree_and_list(&head, &root, &lock);
588 if (err)
589 return err;
590
591 bpf_spin_lock(&lock);
592 rb = bpf_rbtree_first(&root);
593 if (!rb) {
594 bpf_spin_unlock(&lock);
595 return -4;
596 }
597
598 rb = bpf_rbtree_remove(&root, rb);
599 if (!rb) {
600 bpf_spin_unlock(&lock);
601 return -5;
602 }
603
604 n = container_of(rb, struct node_data, r);
605 l = bpf_list_del(&head, &n->l);
606 bpf_spin_unlock(&lock);
607 bpf_obj_drop(n);
608 if (!l)
609 return -6;
610
611 bpf_obj_drop(container_of(l, struct node_data, l));
612 return 0;
613 }
614
615 SEC("tc")
616 __description("list_del_test3: list_del accepts list_front return value as node")
617 __success __retval(0)
list_del_test3(void * ctx)618 int list_del_test3(void *ctx)
619 {
620 struct node_data *tmp;
621 struct bpf_list_node *bpf_node, *l;
622 long err = 0;
623
624 tmp = __add_in_list(&head, &lock);
625 if (!tmp)
626 return -1;
627
628 bpf_spin_lock(&lock);
629 bpf_node = bpf_list_front(&head);
630 if (!bpf_node) {
631 bpf_spin_unlock(&lock);
632 err = -2;
633 goto fail;
634 }
635
636 l = bpf_list_del(&head, bpf_node);
637 bpf_spin_unlock(&lock);
638 if (!l) {
639 err = -3;
640 goto fail;
641 }
642
643 bpf_obj_drop(container_of(l, struct node_data, l));
644 bpf_obj_drop(tmp);
645 return 0;
646
647 fail:
648 bpf_obj_drop(tmp);
649 return err;
650 }
651
652 SEC("tc")
653 __description("list_add_test1: insert new node after prev")
654 __success __retval(0)
list_add_test1(void * ctx)655 int list_add_test1(void *ctx)
656 {
657 struct node_data *node_first;
658 struct node_data *new_node;
659 long err = 0;
660
661 node_first = __add_in_list(&head, &lock);
662 if (!node_first)
663 return -1;
664
665 new_node = bpf_obj_new(typeof(*new_node));
666 if (!new_node) {
667 err = -2;
668 goto fail;
669 }
670
671 bpf_spin_lock(&lock);
672 err = bpf_list_add(&head, &new_node->l, &node_first->l);
673 bpf_spin_unlock(&lock);
674 if (err) {
675 err = -3;
676 goto fail;
677 }
678
679 fail:
680 bpf_obj_drop(node_first);
681 return err;
682 }
683
684 SEC("tc")
685 __description("list_add_test2: list_add accepts list_front return value as prev")
686 __success __retval(0)
list_add_test2(void * ctx)687 int list_add_test2(void *ctx)
688 {
689 struct node_data *new_node, *tmp;
690 struct bpf_list_node *bpf_node;
691 long err = 0;
692
693 tmp = __add_in_list(&head, &lock);
694 if (!tmp)
695 return -1;
696
697 new_node = bpf_obj_new(typeof(*new_node));
698 if (!new_node) {
699 err = -2;
700 goto fail;
701 }
702
703 bpf_spin_lock(&lock);
704 bpf_node = bpf_list_front(&head);
705 if (!bpf_node) {
706 bpf_spin_unlock(&lock);
707 bpf_obj_drop(new_node);
708 err = -3;
709 goto fail;
710 }
711
712 err = bpf_list_add(&head, &new_node->l, bpf_node);
713 bpf_spin_unlock(&lock);
714 if (err) {
715 err = -4;
716 goto fail;
717 }
718
719 fail:
720 bpf_obj_drop(tmp);
721 return err;
722 }
723
724 struct uninit_head_val {
725 struct bpf_spin_lock lock;
726 struct bpf_list_head head __contains(node_data, l);
727 };
728
729 struct {
730 __uint(type, BPF_MAP_TYPE_ARRAY);
731 __type(key, int);
732 __type(value, struct uninit_head_val);
733 __uint(max_entries, 1);
734 } uninit_head_map SEC(".maps");
735
736 SEC("tc")
737 __description("list_push_back_uninit_head: push_back on 0-initialized list head")
738 __success __retval(0)
list_push_back_uninit_head(void * ctx)739 int list_push_back_uninit_head(void *ctx)
740 {
741 struct uninit_head_val *st;
742 struct node_data *node;
743 int ret = -1, key = 0;
744
745 st = bpf_map_lookup_elem(&uninit_head_map, &key);
746 if (!st)
747 return -1;
748
749 node = bpf_obj_new(typeof(*node));
750 if (!node)
751 return -1;
752
753 bpf_spin_lock(&st->lock);
754 ret = bpf_list_push_back(&st->head, &node->l);
755 bpf_spin_unlock(&st->lock);
756
757 return ret;
758 }
759
760 SEC("?tc")
761 __failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head")
list_del_without_lock_fail(void * ctx)762 long list_del_without_lock_fail(void *ctx)
763 {
764 struct node_data *n;
765 struct bpf_list_node *l;
766
767 n = bpf_obj_new(typeof(*n));
768 if (!n)
769 return -1;
770
771 /* Error case: delete list node without holding lock */
772 l = bpf_list_del(&head, &n->l);
773 bpf_obj_drop(n);
774 if (!l)
775 return -2;
776 bpf_obj_drop(container_of(l, struct node_data, l));
777
778 return 0;
779 }
780
781 SEC("?tc")
782 __failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head")
list_add_without_lock_fail(void * ctx)783 long list_add_without_lock_fail(void *ctx)
784 {
785 struct node_data *n, *prev;
786 long err;
787
788 n = bpf_obj_new(typeof(*n));
789 if (!n)
790 return -1;
791
792 prev = bpf_obj_new(typeof(*prev));
793 if (!prev) {
794 bpf_obj_drop(n);
795 return -1;
796 }
797
798 /* Error case: add list node without holding lock */
799 err = bpf_list_add(&head, &n->l, &prev->l);
800 bpf_obj_drop(prev);
801 if (err)
802 return -2;
803
804 return 0;
805 }
806
807 SEC("tc")
808 __success
rbtree_refcounted_node_ref_escapes(void * ctx)809 long rbtree_refcounted_node_ref_escapes(void *ctx)
810 {
811 struct node_acquire *n, *m;
812
813 n = bpf_obj_new(typeof(*n));
814 if (!n)
815 return 1;
816
817 bpf_spin_lock(&alock);
818 bpf_rbtree_add(&aroot, &n->node, less_a);
819 m = bpf_refcount_acquire(n);
820 bpf_spin_unlock(&alock);
821 if (!m)
822 return 2;
823
824 m->key = 2;
825 bpf_obj_drop(m);
826 return 0;
827 }
828
829 SEC("tc")
830 __success
rbtree_refcounted_node_ref_escapes_owning_input(void * ctx)831 long rbtree_refcounted_node_ref_escapes_owning_input(void *ctx)
832 {
833 struct node_acquire *n, *m;
834
835 n = bpf_obj_new(typeof(*n));
836 if (!n)
837 return 1;
838
839 m = bpf_refcount_acquire(n);
840 m->key = 2;
841
842 bpf_spin_lock(&alock);
843 bpf_rbtree_add(&aroot, &n->node, less_a);
844 bpf_spin_unlock(&alock);
845
846 bpf_obj_drop(m);
847
848 return 0;
849 }
850
851 SEC("tc")
852 __success
refcount_acquire_owning_input_no_null_check(void * ctx)853 long refcount_acquire_owning_input_no_null_check(void *ctx)
854 {
855 struct node_refcount_only *n, *m;
856
857 n = bpf_obj_new(typeof(*n));
858 if (!n)
859 return 1;
860
861 m = bpf_refcount_acquire(n);
862 bpf_obj_drop(m);
863 bpf_obj_drop(n);
864
865 return 0;
866 }
867
868 SEC("?syscall")
869 __success
refcount_acquire_rcu_map_kptr_null_checked(void * ctx)870 long refcount_acquire_rcu_map_kptr_null_checked(void *ctx)
871 {
872 struct map_value_refcount_only *mapval;
873 struct node_refcount_only *n, *m;
874 int idx = 0;
875
876 mapval = bpf_map_lookup_elem(&stashed_refcount_only, &idx);
877 if (!mapval)
878 return 1;
879
880 bpf_rcu_read_lock();
881 n = mapval->node;
882 if (!n) {
883 bpf_rcu_read_unlock();
884 return 2;
885 }
886 m = bpf_refcount_acquire(n);
887 bpf_rcu_read_unlock();
888
889 if (!m)
890 return 3;
891 bpf_obj_drop(m);
892
893 return 0;
894 }
895
__stash_map_empty_xchg(struct node_data * n,int idx)896 static long __stash_map_empty_xchg(struct node_data *n, int idx)
897 {
898 struct map_value *mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
899
900 if (!mapval) {
901 bpf_obj_drop(n);
902 return 1;
903 }
904 n = bpf_kptr_xchg(&mapval->node, n);
905 if (n) {
906 bpf_obj_drop(n);
907 return 2;
908 }
909 return 0;
910 }
911
912 SEC("tc")
rbtree_wrong_owner_remove_fail_a1(void * ctx)913 long rbtree_wrong_owner_remove_fail_a1(void *ctx)
914 {
915 struct node_data *n, *m;
916
917 n = bpf_obj_new(typeof(*n));
918 if (!n)
919 return 1;
920 m = bpf_refcount_acquire(n);
921
922 if (__stash_map_empty_xchg(n, 0)) {
923 bpf_obj_drop(m);
924 return 2;
925 }
926
927 if (__stash_map_empty_xchg(m, 1))
928 return 3;
929
930 return 0;
931 }
932
933 SEC("tc")
rbtree_wrong_owner_remove_fail_b(void * ctx)934 long rbtree_wrong_owner_remove_fail_b(void *ctx)
935 {
936 struct map_value *mapval;
937 struct node_data *n;
938 int idx = 0;
939
940 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
941 if (!mapval)
942 return 1;
943
944 n = bpf_kptr_xchg(&mapval->node, NULL);
945 if (!n)
946 return 2;
947
948 bpf_spin_lock(&block);
949
950 bpf_rbtree_add(&broot, &n->r, less);
951
952 bpf_spin_unlock(&block);
953 return 0;
954 }
955
956 SEC("tc")
rbtree_wrong_owner_remove_fail_a2(void * ctx)957 long rbtree_wrong_owner_remove_fail_a2(void *ctx)
958 {
959 struct map_value *mapval;
960 struct bpf_rb_node *res;
961 struct node_data *m;
962 int idx = 1;
963
964 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
965 if (!mapval)
966 return 1;
967
968 m = bpf_kptr_xchg(&mapval->node, NULL);
969 if (!m)
970 return 2;
971 bpf_spin_lock(&lock);
972
973 /* make m non-owning ref */
974 bpf_list_push_back(&head, &m->l);
975 res = bpf_rbtree_remove(&root, &m->r);
976
977 bpf_spin_unlock(&lock);
978 if (res) {
979 bpf_obj_drop(container_of(res, struct node_data, r));
980 return 3;
981 }
982 return 0;
983 }
984
985 SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
986 __success
BPF_PROG(rbtree_sleepable_rcu,struct file * file,struct kobject * kobj,struct bin_attribute * bin_attr,char * buf,loff_t off,size_t len)987 int BPF_PROG(rbtree_sleepable_rcu,
988 struct file *file, struct kobject *kobj,
989 struct bin_attribute *bin_attr, char *buf, loff_t off, size_t len)
990 {
991 struct bpf_rb_node *rb;
992 struct node_data *n, *m = NULL;
993
994 n = bpf_obj_new(typeof(*n));
995 if (!n)
996 return 0;
997
998 bpf_rcu_read_lock();
999 bpf_spin_lock(&lock);
1000 bpf_rbtree_add(&root, &n->r, less);
1001 rb = bpf_rbtree_first(&root);
1002 if (!rb)
1003 goto err_out;
1004
1005 rb = bpf_rbtree_remove(&root, rb);
1006 if (!rb)
1007 goto err_out;
1008
1009 m = container_of(rb, struct node_data, r);
1010
1011 err_out:
1012 bpf_spin_unlock(&lock);
1013 bpf_rcu_read_unlock();
1014 if (m)
1015 bpf_obj_drop(m);
1016 return 0;
1017 }
1018
1019 SEC("?fentry.s/" SYS_PREFIX "sys_getpgid")
1020 __success
BPF_PROG(rbtree_sleepable_rcu_no_explicit_rcu_lock,struct file * file,struct kobject * kobj,struct bin_attribute * bin_attr,char * buf,loff_t off,size_t len)1021 int BPF_PROG(rbtree_sleepable_rcu_no_explicit_rcu_lock,
1022 struct file *file, struct kobject *kobj,
1023 struct bin_attribute *bin_attr, char *buf, loff_t off, size_t len)
1024 {
1025 struct bpf_rb_node *rb;
1026 struct node_data *n, *m = NULL;
1027
1028 n = bpf_obj_new(typeof(*n));
1029 if (!n)
1030 return 0;
1031
1032 /* No explicit bpf_rcu_read_lock */
1033 bpf_spin_lock(&lock);
1034 bpf_rbtree_add(&root, &n->r, less);
1035 rb = bpf_rbtree_first(&root);
1036 if (!rb)
1037 goto err_out;
1038
1039 rb = bpf_rbtree_remove(&root, rb);
1040 if (!rb)
1041 goto err_out;
1042
1043 m = container_of(rb, struct node_data, r);
1044
1045 err_out:
1046 bpf_spin_unlock(&lock);
1047 /* No explicit bpf_rcu_read_unlock */
1048 if (m)
1049 bpf_obj_drop(m);
1050 return 0;
1051 }
1052
private(kptr_ref)1053 private(kptr_ref) u64 ref;
1054
1055 static int probe_read_refcount(void)
1056 {
1057 u32 refcount;
1058
1059 bpf_probe_read_kernel(&refcount, sizeof(refcount), (void *) ref);
1060 return refcount;
1061 }
1062
__insert_in_list(struct bpf_list_head * head,struct bpf_spin_lock * lock,struct node_data __kptr ** node)1063 static int __insert_in_list(struct bpf_list_head *head, struct bpf_spin_lock *lock,
1064 struct node_data __kptr **node)
1065 {
1066 struct node_data *node_new, *node_ref, *node_old;
1067
1068 node_new = bpf_obj_new(typeof(*node_new));
1069 if (!node_new)
1070 return -1;
1071
1072 node_ref = bpf_refcount_acquire(node_new);
1073 node_old = bpf_kptr_xchg(node, node_new);
1074 if (node_old) {
1075 bpf_obj_drop(node_old);
1076 bpf_obj_drop(node_ref);
1077 return -2;
1078 }
1079
1080 bpf_spin_lock(lock);
1081 bpf_list_push_front(head, &node_ref->l);
1082 ref = (u64)(void *) &node_ref->ref;
1083 bpf_spin_unlock(lock);
1084 return probe_read_refcount();
1085 }
1086
1087 struct {
1088 __uint(type, BPF_MAP_TYPE_PERCPU_HASH);
1089 __type(key, int);
1090 __type(value, struct map_value);
1091 __uint(max_entries, 1);
1092 } percpu_hash SEC(".maps");
1093
1094 SEC("tc")
percpu_hash_refcount_leak(void * ctx)1095 int percpu_hash_refcount_leak(void *ctx)
1096 {
1097 struct map_value *v;
1098 int key = 0;
1099
1100 v = bpf_map_lookup_percpu_elem(&percpu_hash, &key, 0);
1101 if (!v)
1102 return 0;
1103
1104 return __insert_in_list(&head, &lock, &v->node);
1105 }
1106
1107 SEC("syscall")
clear_percpu_hash_kptr(void * ctx)1108 int clear_percpu_hash_kptr(void *ctx)
1109 {
1110 struct node_data *n;
1111 struct map_value *v;
1112 int key = 0;
1113
1114 v = bpf_map_lookup_percpu_elem(&percpu_hash, &key, 0);
1115 if (!v)
1116 return 0;
1117
1118 n = bpf_kptr_xchg(&v->node, NULL);
1119 if (!n)
1120 return 0;
1121 bpf_obj_drop(n);
1122 return probe_read_refcount();
1123 }
1124
1125 SEC("tc")
check_percpu_hash_refcount(void * ctx)1126 int check_percpu_hash_refcount(void *ctx)
1127 {
1128 return probe_read_refcount();
1129 }
1130
1131 char _license[] SEC("license") = "GPL";
1132