16147f151SDave Marchevsky // SPDX-License-Identifier: GPL-2.0
26147f151SDave Marchevsky /* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */
36147f151SDave Marchevsky
46147f151SDave Marchevsky #include <vmlinux.h>
56147f151SDave Marchevsky #include <bpf/bpf_tracing.h>
66147f151SDave Marchevsky #include <bpf/bpf_helpers.h>
76147f151SDave Marchevsky #include <bpf/bpf_core_read.h>
86147f151SDave Marchevsky #include "bpf_misc.h"
96147f151SDave Marchevsky #include "bpf_experimental.h"
106147f151SDave Marchevsky
11*312aa5bdSDave Marchevsky extern void bpf_rcu_read_lock(void) __ksym;
12*312aa5bdSDave Marchevsky extern void bpf_rcu_read_unlock(void) __ksym;
13*312aa5bdSDave Marchevsky
146147f151SDave Marchevsky struct node_data {
156147f151SDave Marchevsky long key;
166147f151SDave Marchevsky long list_data;
176147f151SDave Marchevsky struct bpf_rb_node r;
186147f151SDave Marchevsky struct bpf_list_node l;
196147f151SDave Marchevsky struct bpf_refcount ref;
206147f151SDave Marchevsky };
216147f151SDave Marchevsky
226147f151SDave Marchevsky struct map_value {
236147f151SDave Marchevsky struct node_data __kptr *node;
246147f151SDave Marchevsky };
256147f151SDave Marchevsky
266147f151SDave Marchevsky struct {
276147f151SDave Marchevsky __uint(type, BPF_MAP_TYPE_ARRAY);
286147f151SDave Marchevsky __type(key, int);
296147f151SDave Marchevsky __type(value, struct map_value);
30fdf48dc2SDave Marchevsky __uint(max_entries, 2);
316147f151SDave Marchevsky } stashed_nodes SEC(".maps");
326147f151SDave Marchevsky
336147f151SDave Marchevsky struct node_acquire {
346147f151SDave Marchevsky long key;
356147f151SDave Marchevsky long data;
366147f151SDave Marchevsky struct bpf_rb_node node;
376147f151SDave Marchevsky struct bpf_refcount refcount;
386147f151SDave Marchevsky };
396147f151SDave Marchevsky
406147f151SDave Marchevsky #define private(name) SEC(".bss." #name) __hidden __attribute__((aligned(8)))
416147f151SDave Marchevsky private(A) struct bpf_spin_lock lock;
426147f151SDave Marchevsky private(A) struct bpf_rb_root root __contains(node_data, r);
436147f151SDave Marchevsky private(A) struct bpf_list_head head __contains(node_data, l);
446147f151SDave Marchevsky
456147f151SDave Marchevsky private(B) struct bpf_spin_lock alock;
466147f151SDave Marchevsky private(B) struct bpf_rb_root aroot __contains(node_acquire, node);
476147f151SDave Marchevsky
48fdf48dc2SDave Marchevsky private(C) struct bpf_spin_lock block;
49fdf48dc2SDave Marchevsky private(C) struct bpf_rb_root broot __contains(node_data, r);
50fdf48dc2SDave Marchevsky
less(struct bpf_rb_node * node_a,const struct bpf_rb_node * node_b)516147f151SDave Marchevsky static bool less(struct bpf_rb_node *node_a, const struct bpf_rb_node *node_b)
526147f151SDave Marchevsky {
536147f151SDave Marchevsky struct node_data *a;
546147f151SDave Marchevsky struct node_data *b;
556147f151SDave Marchevsky
566147f151SDave Marchevsky a = container_of(node_a, struct node_data, r);
576147f151SDave Marchevsky b = container_of(node_b, struct node_data, r);
586147f151SDave Marchevsky
596147f151SDave Marchevsky return a->key < b->key;
606147f151SDave Marchevsky }
616147f151SDave Marchevsky
less_a(struct bpf_rb_node * a,const struct bpf_rb_node * b)626147f151SDave Marchevsky static bool less_a(struct bpf_rb_node *a, const struct bpf_rb_node *b)
636147f151SDave Marchevsky {
646147f151SDave Marchevsky struct node_acquire *node_a;
656147f151SDave Marchevsky struct node_acquire *node_b;
666147f151SDave Marchevsky
676147f151SDave Marchevsky node_a = container_of(a, struct node_acquire, node);
686147f151SDave Marchevsky node_b = container_of(b, struct node_acquire, node);
696147f151SDave Marchevsky
706147f151SDave Marchevsky return node_a->key < node_b->key;
716147f151SDave Marchevsky }
726147f151SDave Marchevsky
__insert_in_tree_and_list(struct bpf_list_head * head,struct bpf_rb_root * root,struct bpf_spin_lock * lock)736147f151SDave Marchevsky static long __insert_in_tree_and_list(struct bpf_list_head *head,
746147f151SDave Marchevsky struct bpf_rb_root *root,
756147f151SDave Marchevsky struct bpf_spin_lock *lock)
766147f151SDave Marchevsky {
776147f151SDave Marchevsky struct node_data *n, *m;
786147f151SDave Marchevsky
796147f151SDave Marchevsky n = bpf_obj_new(typeof(*n));
806147f151SDave Marchevsky if (!n)
816147f151SDave Marchevsky return -1;
826147f151SDave Marchevsky
836147f151SDave Marchevsky m = bpf_refcount_acquire(n);
846147f151SDave Marchevsky m->key = 123;
856147f151SDave Marchevsky m->list_data = 456;
866147f151SDave Marchevsky
876147f151SDave Marchevsky bpf_spin_lock(lock);
886147f151SDave Marchevsky if (bpf_rbtree_add(root, &n->r, less)) {
896147f151SDave Marchevsky /* Failure to insert - unexpected */
906147f151SDave Marchevsky bpf_spin_unlock(lock);
916147f151SDave Marchevsky bpf_obj_drop(m);
926147f151SDave Marchevsky return -2;
936147f151SDave Marchevsky }
946147f151SDave Marchevsky bpf_spin_unlock(lock);
956147f151SDave Marchevsky
966147f151SDave Marchevsky bpf_spin_lock(lock);
976147f151SDave Marchevsky if (bpf_list_push_front(head, &m->l)) {
986147f151SDave Marchevsky /* Failure to insert - unexpected */
996147f151SDave Marchevsky bpf_spin_unlock(lock);
1006147f151SDave Marchevsky return -3;
1016147f151SDave Marchevsky }
1026147f151SDave Marchevsky bpf_spin_unlock(lock);
1036147f151SDave Marchevsky return 0;
1046147f151SDave Marchevsky }
1056147f151SDave Marchevsky
__stash_map_insert_tree(int idx,int val,struct bpf_rb_root * root,struct bpf_spin_lock * lock)1066147f151SDave Marchevsky static long __stash_map_insert_tree(int idx, int val, struct bpf_rb_root *root,
1076147f151SDave Marchevsky struct bpf_spin_lock *lock)
1086147f151SDave Marchevsky {
1096147f151SDave Marchevsky struct map_value *mapval;
1106147f151SDave Marchevsky struct node_data *n, *m;
1116147f151SDave Marchevsky
1126147f151SDave Marchevsky mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
1136147f151SDave Marchevsky if (!mapval)
1146147f151SDave Marchevsky return -1;
1156147f151SDave Marchevsky
1166147f151SDave Marchevsky n = bpf_obj_new(typeof(*n));
1176147f151SDave Marchevsky if (!n)
1186147f151SDave Marchevsky return -2;
1196147f151SDave Marchevsky
1206147f151SDave Marchevsky n->key = val;
1216147f151SDave Marchevsky m = bpf_refcount_acquire(n);
1226147f151SDave Marchevsky
1236147f151SDave Marchevsky n = bpf_kptr_xchg(&mapval->node, n);
1246147f151SDave Marchevsky if (n) {
1256147f151SDave Marchevsky bpf_obj_drop(n);
1266147f151SDave Marchevsky bpf_obj_drop(m);
1276147f151SDave Marchevsky return -3;
1286147f151SDave Marchevsky }
1296147f151SDave Marchevsky
1306147f151SDave Marchevsky bpf_spin_lock(lock);
1316147f151SDave Marchevsky if (bpf_rbtree_add(root, &m->r, less)) {
1326147f151SDave Marchevsky /* Failure to insert - unexpected */
1336147f151SDave Marchevsky bpf_spin_unlock(lock);
1346147f151SDave Marchevsky return -4;
1356147f151SDave Marchevsky }
1366147f151SDave Marchevsky bpf_spin_unlock(lock);
1376147f151SDave Marchevsky return 0;
1386147f151SDave Marchevsky }
1396147f151SDave Marchevsky
__read_from_tree(struct bpf_rb_root * root,struct bpf_spin_lock * lock,bool remove_from_tree)1406147f151SDave Marchevsky static long __read_from_tree(struct bpf_rb_root *root,
1416147f151SDave Marchevsky struct bpf_spin_lock *lock,
1426147f151SDave Marchevsky bool remove_from_tree)
1436147f151SDave Marchevsky {
1446147f151SDave Marchevsky struct bpf_rb_node *rb;
1456147f151SDave Marchevsky struct node_data *n;
1466147f151SDave Marchevsky long res = -99;
1476147f151SDave Marchevsky
1486147f151SDave Marchevsky bpf_spin_lock(lock);
1496147f151SDave Marchevsky
1506147f151SDave Marchevsky rb = bpf_rbtree_first(root);
1516147f151SDave Marchevsky if (!rb) {
1526147f151SDave Marchevsky bpf_spin_unlock(lock);
1536147f151SDave Marchevsky return -1;
1546147f151SDave Marchevsky }
1556147f151SDave Marchevsky
1566147f151SDave Marchevsky n = container_of(rb, struct node_data, r);
1576147f151SDave Marchevsky res = n->key;
1586147f151SDave Marchevsky
1596147f151SDave Marchevsky if (!remove_from_tree) {
1606147f151SDave Marchevsky bpf_spin_unlock(lock);
1616147f151SDave Marchevsky return res;
1626147f151SDave Marchevsky }
1636147f151SDave Marchevsky
1646147f151SDave Marchevsky rb = bpf_rbtree_remove(root, rb);
1656147f151SDave Marchevsky bpf_spin_unlock(lock);
1666147f151SDave Marchevsky if (!rb)
1676147f151SDave Marchevsky return -2;
1686147f151SDave Marchevsky n = container_of(rb, struct node_data, r);
1696147f151SDave Marchevsky bpf_obj_drop(n);
1706147f151SDave Marchevsky return res;
1716147f151SDave Marchevsky }
1726147f151SDave Marchevsky
__read_from_list(struct bpf_list_head * head,struct bpf_spin_lock * lock,bool remove_from_list)1736147f151SDave Marchevsky static long __read_from_list(struct bpf_list_head *head,
1746147f151SDave Marchevsky struct bpf_spin_lock *lock,
1756147f151SDave Marchevsky bool remove_from_list)
1766147f151SDave Marchevsky {
1776147f151SDave Marchevsky struct bpf_list_node *l;
1786147f151SDave Marchevsky struct node_data *n;
1796147f151SDave Marchevsky long res = -99;
1806147f151SDave Marchevsky
1816147f151SDave Marchevsky bpf_spin_lock(lock);
1826147f151SDave Marchevsky
1836147f151SDave Marchevsky l = bpf_list_pop_front(head);
1846147f151SDave Marchevsky if (!l) {
1856147f151SDave Marchevsky bpf_spin_unlock(lock);
1866147f151SDave Marchevsky return -1;
1876147f151SDave Marchevsky }
1886147f151SDave Marchevsky
1896147f151SDave Marchevsky n = container_of(l, struct node_data, l);
1906147f151SDave Marchevsky res = n->list_data;
1916147f151SDave Marchevsky
1926147f151SDave Marchevsky if (!remove_from_list) {
1936147f151SDave Marchevsky if (bpf_list_push_back(head, &n->l)) {
1946147f151SDave Marchevsky bpf_spin_unlock(lock);
1956147f151SDave Marchevsky return -2;
1966147f151SDave Marchevsky }
1976147f151SDave Marchevsky }
1986147f151SDave Marchevsky
1996147f151SDave Marchevsky bpf_spin_unlock(lock);
2006147f151SDave Marchevsky
2016147f151SDave Marchevsky if (remove_from_list)
2026147f151SDave Marchevsky bpf_obj_drop(n);
2036147f151SDave Marchevsky return res;
2046147f151SDave Marchevsky }
2056147f151SDave Marchevsky
__read_from_unstash(int idx)2066147f151SDave Marchevsky static long __read_from_unstash(int idx)
2076147f151SDave Marchevsky {
2086147f151SDave Marchevsky struct node_data *n = NULL;
2096147f151SDave Marchevsky struct map_value *mapval;
2106147f151SDave Marchevsky long val = -99;
2116147f151SDave Marchevsky
2126147f151SDave Marchevsky mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
2136147f151SDave Marchevsky if (!mapval)
2146147f151SDave Marchevsky return -1;
2156147f151SDave Marchevsky
2166147f151SDave Marchevsky n = bpf_kptr_xchg(&mapval->node, n);
2176147f151SDave Marchevsky if (!n)
2186147f151SDave Marchevsky return -2;
2196147f151SDave Marchevsky
2206147f151SDave Marchevsky val = n->key;
2216147f151SDave Marchevsky bpf_obj_drop(n);
2226147f151SDave Marchevsky return val;
2236147f151SDave Marchevsky }
2246147f151SDave Marchevsky
2256147f151SDave Marchevsky #define INSERT_READ_BOTH(rem_tree, rem_list, desc) \
2266147f151SDave Marchevsky SEC("tc") \
2276147f151SDave Marchevsky __description(desc) \
2284ab07209SDave Marchevsky __success __retval(579) \
2296147f151SDave Marchevsky long insert_and_remove_tree_##rem_tree##_list_##rem_list(void *ctx) \
2306147f151SDave Marchevsky { \
2316147f151SDave Marchevsky long err, tree_data, list_data; \
2326147f151SDave Marchevsky \
2336147f151SDave Marchevsky err = __insert_in_tree_and_list(&head, &root, &lock); \
2346147f151SDave Marchevsky if (err) \
2356147f151SDave Marchevsky return err; \
2366147f151SDave Marchevsky \
2376147f151SDave Marchevsky err = __read_from_tree(&root, &lock, rem_tree); \
2386147f151SDave Marchevsky if (err < 0) \
2396147f151SDave Marchevsky return err; \
2406147f151SDave Marchevsky else \
2416147f151SDave Marchevsky tree_data = err; \
2426147f151SDave Marchevsky \
2436147f151SDave Marchevsky err = __read_from_list(&head, &lock, rem_list); \
2446147f151SDave Marchevsky if (err < 0) \
2456147f151SDave Marchevsky return err; \
2466147f151SDave Marchevsky else \
2476147f151SDave Marchevsky list_data = err; \
2486147f151SDave Marchevsky \
2496147f151SDave Marchevsky return tree_data + list_data; \
2506147f151SDave Marchevsky }
2516147f151SDave Marchevsky
2526147f151SDave Marchevsky /* After successful insert of struct node_data into both collections:
2536147f151SDave Marchevsky * - it should have refcount = 2
2546147f151SDave Marchevsky * - removing / not removing the node_data from a collection after
2556147f151SDave Marchevsky * reading should have no effect on ability to read / remove from
2566147f151SDave Marchevsky * the other collection
2576147f151SDave Marchevsky */
2586147f151SDave Marchevsky INSERT_READ_BOTH(true, true, "insert_read_both: remove from tree + list");
2596147f151SDave Marchevsky INSERT_READ_BOTH(false, false, "insert_read_both: remove from neither");
2606147f151SDave Marchevsky INSERT_READ_BOTH(true, false, "insert_read_both: remove from tree");
2616147f151SDave Marchevsky INSERT_READ_BOTH(false, true, "insert_read_both: remove from list");
2626147f151SDave Marchevsky
2636147f151SDave Marchevsky #undef INSERT_READ_BOTH
2646147f151SDave Marchevsky #define INSERT_READ_BOTH(rem_tree, rem_list, desc) \
2656147f151SDave Marchevsky SEC("tc") \
2666147f151SDave Marchevsky __description(desc) \
2674ab07209SDave Marchevsky __success __retval(579) \
2686147f151SDave Marchevsky long insert_and_remove_lf_tree_##rem_tree##_list_##rem_list(void *ctx) \
2696147f151SDave Marchevsky { \
2706147f151SDave Marchevsky long err, tree_data, list_data; \
2716147f151SDave Marchevsky \
2726147f151SDave Marchevsky err = __insert_in_tree_and_list(&head, &root, &lock); \
2736147f151SDave Marchevsky if (err) \
2746147f151SDave Marchevsky return err; \
2756147f151SDave Marchevsky \
2766147f151SDave Marchevsky err = __read_from_list(&head, &lock, rem_list); \
2776147f151SDave Marchevsky if (err < 0) \
2786147f151SDave Marchevsky return err; \
2796147f151SDave Marchevsky else \
2806147f151SDave Marchevsky list_data = err; \
2816147f151SDave Marchevsky \
2826147f151SDave Marchevsky err = __read_from_tree(&root, &lock, rem_tree); \
2836147f151SDave Marchevsky if (err < 0) \
2846147f151SDave Marchevsky return err; \
2856147f151SDave Marchevsky else \
2866147f151SDave Marchevsky tree_data = err; \
2876147f151SDave Marchevsky \
2886147f151SDave Marchevsky return tree_data + list_data; \
2896147f151SDave Marchevsky }
2906147f151SDave Marchevsky
2916147f151SDave Marchevsky /* Similar to insert_read_both, but list data is read and possibly removed
2926147f151SDave Marchevsky * first
2936147f151SDave Marchevsky *
2946147f151SDave Marchevsky * Results should be no different than reading and possibly removing rbtree
2956147f151SDave Marchevsky * node first
2966147f151SDave Marchevsky */
2976147f151SDave Marchevsky INSERT_READ_BOTH(true, true, "insert_read_both_list_first: remove from tree + list");
2986147f151SDave Marchevsky INSERT_READ_BOTH(false, false, "insert_read_both_list_first: remove from neither");
2996147f151SDave Marchevsky INSERT_READ_BOTH(true, false, "insert_read_both_list_first: remove from tree");
3006147f151SDave Marchevsky INSERT_READ_BOTH(false, true, "insert_read_both_list_first: remove from list");
3016147f151SDave Marchevsky
3026147f151SDave Marchevsky #define INSERT_DOUBLE_READ_AND_DEL(read_fn, read_root, desc) \
3036147f151SDave Marchevsky SEC("tc") \
3046147f151SDave Marchevsky __description(desc) \
3054ab07209SDave Marchevsky __success __retval(-1) \
3066147f151SDave Marchevsky long insert_double_##read_fn##_and_del_##read_root(void *ctx) \
3076147f151SDave Marchevsky { \
3086147f151SDave Marchevsky long err, list_data; \
3096147f151SDave Marchevsky \
3106147f151SDave Marchevsky err = __insert_in_tree_and_list(&head, &root, &lock); \
3116147f151SDave Marchevsky if (err) \
3126147f151SDave Marchevsky return err; \
3136147f151SDave Marchevsky \
3146147f151SDave Marchevsky err = read_fn(&read_root, &lock, true); \
3156147f151SDave Marchevsky if (err < 0) \
3166147f151SDave Marchevsky return err; \
3176147f151SDave Marchevsky else \
3186147f151SDave Marchevsky list_data = err; \
3196147f151SDave Marchevsky \
3206147f151SDave Marchevsky err = read_fn(&read_root, &lock, true); \
3216147f151SDave Marchevsky if (err < 0) \
3226147f151SDave Marchevsky return err; \
3236147f151SDave Marchevsky \
3246147f151SDave Marchevsky return err + list_data; \
3256147f151SDave Marchevsky }
3266147f151SDave Marchevsky
3276147f151SDave Marchevsky /* Insert into both tree and list, then try reading-and-removing from either twice
3286147f151SDave Marchevsky *
3296147f151SDave Marchevsky * The second read-and-remove should fail on read step since the node has
3306147f151SDave Marchevsky * already been removed
3316147f151SDave Marchevsky */
3326147f151SDave Marchevsky INSERT_DOUBLE_READ_AND_DEL(__read_from_tree, root, "insert_double_del: 2x read-and-del from tree");
3336147f151SDave Marchevsky INSERT_DOUBLE_READ_AND_DEL(__read_from_list, head, "insert_double_del: 2x read-and-del from list");
3346147f151SDave Marchevsky
3356147f151SDave Marchevsky #define INSERT_STASH_READ(rem_tree, desc) \
3366147f151SDave Marchevsky SEC("tc") \
3376147f151SDave Marchevsky __description(desc) \
3384ab07209SDave Marchevsky __success __retval(84) \
3396147f151SDave Marchevsky long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \
3406147f151SDave Marchevsky { \
3416147f151SDave Marchevsky long err, tree_data, map_data; \
3426147f151SDave Marchevsky \
3436147f151SDave Marchevsky err = __stash_map_insert_tree(0, 42, &root, &lock); \
3446147f151SDave Marchevsky if (err) \
3456147f151SDave Marchevsky return err; \
3466147f151SDave Marchevsky \
3476147f151SDave Marchevsky err = __read_from_tree(&root, &lock, rem_tree); \
3486147f151SDave Marchevsky if (err < 0) \
3496147f151SDave Marchevsky return err; \
3506147f151SDave Marchevsky else \
3516147f151SDave Marchevsky tree_data = err; \
3526147f151SDave Marchevsky \
3536147f151SDave Marchevsky err = __read_from_unstash(0); \
3546147f151SDave Marchevsky if (err < 0) \
3556147f151SDave Marchevsky return err; \
3566147f151SDave Marchevsky else \
3576147f151SDave Marchevsky map_data = err; \
3586147f151SDave Marchevsky \
3596147f151SDave Marchevsky return tree_data + map_data; \
3606147f151SDave Marchevsky }
3616147f151SDave Marchevsky
3626147f151SDave Marchevsky /* Stash a refcounted node in map_val, insert same node into tree, then try
3636147f151SDave Marchevsky * reading data from tree then unstashed map_val, possibly removing from tree
3646147f151SDave Marchevsky *
3656147f151SDave Marchevsky * Removing from tree should have no effect on map_val kptr validity
3666147f151SDave Marchevsky */
3676147f151SDave Marchevsky INSERT_STASH_READ(true, "insert_stash_read: remove from tree");
3686147f151SDave Marchevsky INSERT_STASH_READ(false, "insert_stash_read: don't remove from tree");
3696147f151SDave Marchevsky
3706147f151SDave Marchevsky SEC("tc")
3716147f151SDave Marchevsky __success
rbtree_refcounted_node_ref_escapes(void * ctx)3726147f151SDave Marchevsky long rbtree_refcounted_node_ref_escapes(void *ctx)
3736147f151SDave Marchevsky {
3746147f151SDave Marchevsky struct node_acquire *n, *m;
3756147f151SDave Marchevsky
3766147f151SDave Marchevsky n = bpf_obj_new(typeof(*n));
3776147f151SDave Marchevsky if (!n)
3786147f151SDave Marchevsky return 1;
3796147f151SDave Marchevsky
3806147f151SDave Marchevsky bpf_spin_lock(&alock);
3816147f151SDave Marchevsky bpf_rbtree_add(&aroot, &n->node, less_a);
3826147f151SDave Marchevsky m = bpf_refcount_acquire(n);
3836147f151SDave Marchevsky bpf_spin_unlock(&alock);
3847793fc3bSDave Marchevsky if (!m)
3857793fc3bSDave Marchevsky return 2;
3866147f151SDave Marchevsky
3876147f151SDave Marchevsky m->key = 2;
3886147f151SDave Marchevsky bpf_obj_drop(m);
3896147f151SDave Marchevsky return 0;
3906147f151SDave Marchevsky }
3916147f151SDave Marchevsky
3926147f151SDave Marchevsky SEC("tc")
3936147f151SDave Marchevsky __success
rbtree_refcounted_node_ref_escapes_owning_input(void * ctx)3946147f151SDave Marchevsky long rbtree_refcounted_node_ref_escapes_owning_input(void *ctx)
3956147f151SDave Marchevsky {
3966147f151SDave Marchevsky struct node_acquire *n, *m;
3976147f151SDave Marchevsky
3986147f151SDave Marchevsky n = bpf_obj_new(typeof(*n));
3996147f151SDave Marchevsky if (!n)
4006147f151SDave Marchevsky return 1;
4016147f151SDave Marchevsky
4026147f151SDave Marchevsky m = bpf_refcount_acquire(n);
4036147f151SDave Marchevsky m->key = 2;
4046147f151SDave Marchevsky
4056147f151SDave Marchevsky bpf_spin_lock(&alock);
4066147f151SDave Marchevsky bpf_rbtree_add(&aroot, &n->node, less_a);
4076147f151SDave Marchevsky bpf_spin_unlock(&alock);
4086147f151SDave Marchevsky
4096147f151SDave Marchevsky bpf_obj_drop(m);
4106147f151SDave Marchevsky
4116147f151SDave Marchevsky return 0;
4126147f151SDave Marchevsky }
4136147f151SDave Marchevsky
__stash_map_empty_xchg(struct node_data * n,int idx)414fdf48dc2SDave Marchevsky static long __stash_map_empty_xchg(struct node_data *n, int idx)
415fdf48dc2SDave Marchevsky {
416fdf48dc2SDave Marchevsky struct map_value *mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
417fdf48dc2SDave Marchevsky
418fdf48dc2SDave Marchevsky if (!mapval) {
419fdf48dc2SDave Marchevsky bpf_obj_drop(n);
420fdf48dc2SDave Marchevsky return 1;
421fdf48dc2SDave Marchevsky }
422fdf48dc2SDave Marchevsky n = bpf_kptr_xchg(&mapval->node, n);
423fdf48dc2SDave Marchevsky if (n) {
424fdf48dc2SDave Marchevsky bpf_obj_drop(n);
425fdf48dc2SDave Marchevsky return 2;
426fdf48dc2SDave Marchevsky }
427fdf48dc2SDave Marchevsky return 0;
428fdf48dc2SDave Marchevsky }
429fdf48dc2SDave Marchevsky
430fdf48dc2SDave Marchevsky SEC("tc")
rbtree_wrong_owner_remove_fail_a1(void * ctx)431fdf48dc2SDave Marchevsky long rbtree_wrong_owner_remove_fail_a1(void *ctx)
432fdf48dc2SDave Marchevsky {
433fdf48dc2SDave Marchevsky struct node_data *n, *m;
434fdf48dc2SDave Marchevsky
435fdf48dc2SDave Marchevsky n = bpf_obj_new(typeof(*n));
436fdf48dc2SDave Marchevsky if (!n)
437fdf48dc2SDave Marchevsky return 1;
438fdf48dc2SDave Marchevsky m = bpf_refcount_acquire(n);
439fdf48dc2SDave Marchevsky
440fdf48dc2SDave Marchevsky if (__stash_map_empty_xchg(n, 0)) {
441fdf48dc2SDave Marchevsky bpf_obj_drop(m);
442fdf48dc2SDave Marchevsky return 2;
443fdf48dc2SDave Marchevsky }
444fdf48dc2SDave Marchevsky
445fdf48dc2SDave Marchevsky if (__stash_map_empty_xchg(m, 1))
446fdf48dc2SDave Marchevsky return 3;
447fdf48dc2SDave Marchevsky
448fdf48dc2SDave Marchevsky return 0;
449fdf48dc2SDave Marchevsky }
450fdf48dc2SDave Marchevsky
451fdf48dc2SDave Marchevsky SEC("tc")
rbtree_wrong_owner_remove_fail_b(void * ctx)452fdf48dc2SDave Marchevsky long rbtree_wrong_owner_remove_fail_b(void *ctx)
453fdf48dc2SDave Marchevsky {
454fdf48dc2SDave Marchevsky struct map_value *mapval;
455fdf48dc2SDave Marchevsky struct node_data *n;
456fdf48dc2SDave Marchevsky int idx = 0;
457fdf48dc2SDave Marchevsky
458fdf48dc2SDave Marchevsky mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
459fdf48dc2SDave Marchevsky if (!mapval)
460fdf48dc2SDave Marchevsky return 1;
461fdf48dc2SDave Marchevsky
462fdf48dc2SDave Marchevsky n = bpf_kptr_xchg(&mapval->node, NULL);
463fdf48dc2SDave Marchevsky if (!n)
464fdf48dc2SDave Marchevsky return 2;
465fdf48dc2SDave Marchevsky
466fdf48dc2SDave Marchevsky bpf_spin_lock(&block);
467fdf48dc2SDave Marchevsky
468fdf48dc2SDave Marchevsky bpf_rbtree_add(&broot, &n->r, less);
469fdf48dc2SDave Marchevsky
470fdf48dc2SDave Marchevsky bpf_spin_unlock(&block);
471fdf48dc2SDave Marchevsky return 0;
472fdf48dc2SDave Marchevsky }
473fdf48dc2SDave Marchevsky
474fdf48dc2SDave Marchevsky SEC("tc")
rbtree_wrong_owner_remove_fail_a2(void * ctx)475fdf48dc2SDave Marchevsky long rbtree_wrong_owner_remove_fail_a2(void *ctx)
476fdf48dc2SDave Marchevsky {
477fdf48dc2SDave Marchevsky struct map_value *mapval;
478fdf48dc2SDave Marchevsky struct bpf_rb_node *res;
479fdf48dc2SDave Marchevsky struct node_data *m;
480fdf48dc2SDave Marchevsky int idx = 1;
481fdf48dc2SDave Marchevsky
482fdf48dc2SDave Marchevsky mapval = bpf_map_lookup_elem(&stashed_nodes, &idx);
483fdf48dc2SDave Marchevsky if (!mapval)
484fdf48dc2SDave Marchevsky return 1;
485fdf48dc2SDave Marchevsky
486fdf48dc2SDave Marchevsky m = bpf_kptr_xchg(&mapval->node, NULL);
487fdf48dc2SDave Marchevsky if (!m)
488fdf48dc2SDave Marchevsky return 2;
489fdf48dc2SDave Marchevsky bpf_spin_lock(&lock);
490fdf48dc2SDave Marchevsky
491fdf48dc2SDave Marchevsky /* make m non-owning ref */
492fdf48dc2SDave Marchevsky bpf_list_push_back(&head, &m->l);
493fdf48dc2SDave Marchevsky res = bpf_rbtree_remove(&root, &m->r);
494fdf48dc2SDave Marchevsky
495fdf48dc2SDave Marchevsky bpf_spin_unlock(&lock);
496fdf48dc2SDave Marchevsky if (res) {
497fdf48dc2SDave Marchevsky bpf_obj_drop(container_of(res, struct node_data, r));
498fdf48dc2SDave Marchevsky return 3;
499fdf48dc2SDave Marchevsky }
500fdf48dc2SDave Marchevsky return 0;
501fdf48dc2SDave Marchevsky }
502fdf48dc2SDave Marchevsky
503*312aa5bdSDave Marchevsky SEC("?fentry.s/bpf_testmod_test_read")
504*312aa5bdSDave Marchevsky __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)505*312aa5bdSDave Marchevsky int BPF_PROG(rbtree_sleepable_rcu,
506*312aa5bdSDave Marchevsky struct file *file, struct kobject *kobj,
507*312aa5bdSDave Marchevsky struct bin_attribute *bin_attr, char *buf, loff_t off, size_t len)
508*312aa5bdSDave Marchevsky {
509*312aa5bdSDave Marchevsky struct bpf_rb_node *rb;
510*312aa5bdSDave Marchevsky struct node_data *n, *m = NULL;
511*312aa5bdSDave Marchevsky
512*312aa5bdSDave Marchevsky n = bpf_obj_new(typeof(*n));
513*312aa5bdSDave Marchevsky if (!n)
514*312aa5bdSDave Marchevsky return 0;
515*312aa5bdSDave Marchevsky
516*312aa5bdSDave Marchevsky bpf_rcu_read_lock();
517*312aa5bdSDave Marchevsky bpf_spin_lock(&lock);
518*312aa5bdSDave Marchevsky bpf_rbtree_add(&root, &n->r, less);
519*312aa5bdSDave Marchevsky rb = bpf_rbtree_first(&root);
520*312aa5bdSDave Marchevsky if (!rb)
521*312aa5bdSDave Marchevsky goto err_out;
522*312aa5bdSDave Marchevsky
523*312aa5bdSDave Marchevsky rb = bpf_rbtree_remove(&root, rb);
524*312aa5bdSDave Marchevsky if (!rb)
525*312aa5bdSDave Marchevsky goto err_out;
526*312aa5bdSDave Marchevsky
527*312aa5bdSDave Marchevsky m = container_of(rb, struct node_data, r);
528*312aa5bdSDave Marchevsky
529*312aa5bdSDave Marchevsky err_out:
530*312aa5bdSDave Marchevsky bpf_spin_unlock(&lock);
531*312aa5bdSDave Marchevsky bpf_rcu_read_unlock();
532*312aa5bdSDave Marchevsky if (m)
533*312aa5bdSDave Marchevsky bpf_obj_drop(m);
534*312aa5bdSDave Marchevsky return 0;
535*312aa5bdSDave Marchevsky }
536*312aa5bdSDave Marchevsky
537*312aa5bdSDave Marchevsky SEC("?fentry.s/bpf_testmod_test_read")
538*312aa5bdSDave Marchevsky __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)539*312aa5bdSDave Marchevsky int BPF_PROG(rbtree_sleepable_rcu_no_explicit_rcu_lock,
540*312aa5bdSDave Marchevsky struct file *file, struct kobject *kobj,
541*312aa5bdSDave Marchevsky struct bin_attribute *bin_attr, char *buf, loff_t off, size_t len)
542*312aa5bdSDave Marchevsky {
543*312aa5bdSDave Marchevsky struct bpf_rb_node *rb;
544*312aa5bdSDave Marchevsky struct node_data *n, *m = NULL;
545*312aa5bdSDave Marchevsky
546*312aa5bdSDave Marchevsky n = bpf_obj_new(typeof(*n));
547*312aa5bdSDave Marchevsky if (!n)
548*312aa5bdSDave Marchevsky return 0;
549*312aa5bdSDave Marchevsky
550*312aa5bdSDave Marchevsky /* No explicit bpf_rcu_read_lock */
551*312aa5bdSDave Marchevsky bpf_spin_lock(&lock);
552*312aa5bdSDave Marchevsky bpf_rbtree_add(&root, &n->r, less);
553*312aa5bdSDave Marchevsky rb = bpf_rbtree_first(&root);
554*312aa5bdSDave Marchevsky if (!rb)
555*312aa5bdSDave Marchevsky goto err_out;
556*312aa5bdSDave Marchevsky
557*312aa5bdSDave Marchevsky rb = bpf_rbtree_remove(&root, rb);
558*312aa5bdSDave Marchevsky if (!rb)
559*312aa5bdSDave Marchevsky goto err_out;
560*312aa5bdSDave Marchevsky
561*312aa5bdSDave Marchevsky m = container_of(rb, struct node_data, r);
562*312aa5bdSDave Marchevsky
563*312aa5bdSDave Marchevsky err_out:
564*312aa5bdSDave Marchevsky bpf_spin_unlock(&lock);
565*312aa5bdSDave Marchevsky /* No explicit bpf_rcu_read_unlock */
566*312aa5bdSDave Marchevsky if (m)
567*312aa5bdSDave Marchevsky bpf_obj_drop(m);
568*312aa5bdSDave Marchevsky return 0;
569*312aa5bdSDave Marchevsky }
570*312aa5bdSDave Marchevsky
5716147f151SDave Marchevsky char _license[] SEC("license") = "GPL";
572