1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2022 Meta Platforms, Inc. and affiliates. */
5 #include <bpf/bpf_tracing.h>
6 #include <bpf/bpf_helpers.h>
7 #include <bpf/bpf_core_read.h>
8 #include "bpf_experimental.h"
13 struct bpf_rb_node node;
16 long less_callback_ran = -1;
17 long removed_key = -1;
18 long first_data[2] = {-1, -1};
20 #define private(name) SEC(".data." #name) __hidden __attribute__((aligned(8)))
21 private(A) struct bpf_spin_lock glock;
22 private(A) struct bpf_rb_root groot __contains(node_data, node);
24 static bool less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
26 struct node_data *node_a;
27 struct node_data *node_b;
29 node_a = container_of(a, struct node_data, node);
30 node_b = container_of(b, struct node_data, node);
31 less_callback_ran = 1;
33 return node_a->key < node_b->key;
36 static long __add_three(struct bpf_rb_root *root, struct bpf_spin_lock *lock)
38 struct node_data *n, *m;
40 n = bpf_obj_new(typeof(*n));
45 m = bpf_obj_new(typeof(*m));
52 bpf_spin_lock(&glock);
53 bpf_rbtree_add(&groot, &n->node, less);
54 bpf_rbtree_add(&groot, &m->node, less);
55 bpf_spin_unlock(&glock);
57 n = bpf_obj_new(typeof(*n));
62 bpf_spin_lock(&glock);
63 bpf_rbtree_add(&groot, &n->node, less);
64 bpf_spin_unlock(&glock);
69 long rbtree_add_nodes(void *ctx)
71 return __add_three(&groot, &glock);
75 long rbtree_add_and_remove(void *ctx)
77 struct bpf_rb_node *res = NULL;
78 struct node_data *n, *m = NULL;
80 n = bpf_obj_new(typeof(*n));
85 m = bpf_obj_new(typeof(*m));
90 bpf_spin_lock(&glock);
91 bpf_rbtree_add(&groot, &n->node, less);
92 bpf_rbtree_add(&groot, &m->node, less);
93 res = bpf_rbtree_remove(&groot, &n->node);
94 bpf_spin_unlock(&glock);
99 n = container_of(res, struct node_data, node);
100 removed_key = n->key;
113 long rbtree_first_and_remove(void *ctx)
115 struct bpf_rb_node *res = NULL;
116 struct node_data *n, *m, *o;
118 n = bpf_obj_new(typeof(*n));
124 m = bpf_obj_new(typeof(*m));
130 o = bpf_obj_new(typeof(*o));
136 bpf_spin_lock(&glock);
137 bpf_rbtree_add(&groot, &n->node, less);
138 bpf_rbtree_add(&groot, &m->node, less);
139 bpf_rbtree_add(&groot, &o->node, less);
141 res = bpf_rbtree_first(&groot);
143 bpf_spin_unlock(&glock);
147 o = container_of(res, struct node_data, node);
148 first_data[0] = o->data;
150 res = bpf_rbtree_remove(&groot, &o->node);
151 bpf_spin_unlock(&glock);
156 o = container_of(res, struct node_data, node);
157 removed_key = o->key;
160 bpf_spin_lock(&glock);
161 res = bpf_rbtree_first(&groot);
163 bpf_spin_unlock(&glock);
167 o = container_of(res, struct node_data, node);
168 first_data[1] = o->data;
169 bpf_spin_unlock(&glock);
181 long rbtree_api_release_aliasing(void *ctx)
183 struct node_data *n, *m, *o;
184 struct bpf_rb_node *res, *res2;
186 n = bpf_obj_new(typeof(*n));
192 bpf_spin_lock(&glock);
193 bpf_rbtree_add(&groot, &n->node, less);
194 bpf_spin_unlock(&glock);
196 bpf_spin_lock(&glock);
198 /* m and o point to the same node,
199 * but verifier doesn't know this
201 res = bpf_rbtree_first(&groot);
204 o = container_of(res, struct node_data, node);
206 res = bpf_rbtree_first(&groot);
209 m = container_of(res, struct node_data, node);
211 res = bpf_rbtree_remove(&groot, &m->node);
212 /* Retval of previous remove returns an owning reference to m,
213 * which is the same node non-owning ref o is pointing at.
214 * We can safely try to remove o as the second rbtree_remove will
215 * return NULL since the node isn't in a tree.
217 * Previously we relied on the verifier type system + rbtree_remove
218 * invalidating non-owning refs to ensure that rbtree_remove couldn't
219 * fail, but now rbtree_remove does runtime checking so we no longer
220 * invalidate non-owning refs after remove.
222 res2 = bpf_rbtree_remove(&groot, &o->node);
224 bpf_spin_unlock(&glock);
227 o = container_of(res, struct node_data, node);
228 first_data[0] = o->data;
232 /* The second remove fails, so res2 is null and this doesn't
235 m = container_of(res2, struct node_data, node);
236 first_data[1] = m->data;
242 bpf_spin_unlock(&glock);
246 char _license[] SEC("license") = "GPL";