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 struct node_data {
10 long key;
11 long data;
12 struct bpf_rb_node node;
13 };
14
15 #define private(name) SEC(".data." #name) __hidden __attribute__((aligned(8)))
16 private(A) struct bpf_spin_lock glock;
17 private(A) struct bpf_rb_root groot __contains(node_data, node);
18 private(A) struct bpf_rb_root groot2 __contains(node_data, node);
19 private(B) struct bpf_res_spin_lock res_glock;
20
less(struct bpf_rb_node * a,const struct bpf_rb_node * b)21 static bool less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
22 {
23 struct node_data *node_a;
24 struct node_data *node_b;
25
26 node_a = container_of(a, struct node_data, node);
27 node_b = container_of(b, struct node_data, node);
28
29 return node_a->key < node_b->key;
30 }
31
32 SEC("?tc")
33 __failure __msg("bpf_spin_lock at off=16 must be held for bpf_rb_root")
rbtree_api_nolock_add(void * ctx)34 long rbtree_api_nolock_add(void *ctx)
35 {
36 struct node_data *n;
37
38 n = bpf_obj_new(typeof(*n));
39 if (!n)
40 return 1;
41
42 bpf_rbtree_add(&groot, &n->node, less);
43 return 0;
44 }
45
46 SEC("?tc")
47 __failure __msg("bpf_spin_lock at off=16 must be held for bpf_rb_root")
rbtree_api_nolock_remove(void * ctx)48 long rbtree_api_nolock_remove(void *ctx)
49 {
50 struct node_data *n;
51
52 n = bpf_obj_new(typeof(*n));
53 if (!n)
54 return 1;
55
56 bpf_spin_lock(&glock);
57 bpf_rbtree_add(&groot, &n->node, less);
58 bpf_spin_unlock(&glock);
59
60 bpf_rbtree_remove(&groot, &n->node);
61 return 0;
62 }
63
64 SEC("?tc")
65 __failure __msg("bpf_spin_lock at off=16 must be held for bpf_rb_root")
rbtree_api_nolock_first(void * ctx)66 long rbtree_api_nolock_first(void *ctx)
67 {
68 bpf_rbtree_first(&groot);
69 return 0;
70 }
71
72 SEC("?tc")
73 __retval(0)
rbtree_api_remove_unadded_node(void * ctx)74 long rbtree_api_remove_unadded_node(void *ctx)
75 {
76 struct node_data *n, *m;
77 struct bpf_rb_node *res_n, *res_m;
78
79 n = bpf_obj_new(typeof(*n));
80 if (!n)
81 return 1;
82
83 m = bpf_obj_new(typeof(*m));
84 if (!m) {
85 bpf_obj_drop(n);
86 return 1;
87 }
88
89 bpf_spin_lock(&glock);
90 bpf_rbtree_add(&groot, &n->node, less);
91
92 res_n = bpf_rbtree_remove(&groot, &n->node);
93
94 res_m = bpf_rbtree_remove(&groot, &m->node);
95 bpf_spin_unlock(&glock);
96
97 bpf_obj_drop(m);
98 if (res_n)
99 bpf_obj_drop(container_of(res_n, struct node_data, node));
100 if (res_m) {
101 bpf_obj_drop(container_of(res_m, struct node_data, node));
102 /* m was not added to the rbtree */
103 return 2;
104 }
105
106 return 0;
107 }
108
109 SEC("?tc")
110 __failure __msg("Unreleased reference id=3 alloc_insn={{[0-9]+}}")
rbtree_api_remove_no_drop(void * ctx)111 long rbtree_api_remove_no_drop(void *ctx)
112 {
113 struct bpf_rb_node *res;
114 struct node_data *n;
115
116 bpf_spin_lock(&glock);
117 res = bpf_rbtree_first(&groot);
118 if (!res)
119 goto unlock_err;
120
121 res = bpf_rbtree_remove(&groot, res);
122
123 if (res) {
124 n = container_of(res, struct node_data, node);
125 __sink(n);
126 }
127 bpf_spin_unlock(&glock);
128
129 /* if (res) { bpf_obj_drop(n); } is missing here */
130 return 0;
131
132 unlock_err:
133 bpf_spin_unlock(&glock);
134 return 1;
135 }
136
137 SEC("?tc")
138 __failure __msg("R2 expected pointer to allocated object")
rbtree_api_add_to_multiple_trees(void * ctx)139 long rbtree_api_add_to_multiple_trees(void *ctx)
140 {
141 struct node_data *n;
142
143 n = bpf_obj_new(typeof(*n));
144 if (!n)
145 return 1;
146
147 bpf_spin_lock(&glock);
148 bpf_rbtree_add(&groot, &n->node, less);
149
150 /* This add should fail since n already in groot's tree */
151 bpf_rbtree_add(&groot2, &n->node, less);
152 bpf_spin_unlock(&glock);
153 return 0;
154 }
155
156 SEC("?tc")
157 __failure __msg("Possibly NULL pointer passed to trusted R2")
rbtree_api_use_unchecked_remove_retval(void * ctx)158 long rbtree_api_use_unchecked_remove_retval(void *ctx)
159 {
160 struct bpf_rb_node *res;
161
162 bpf_spin_lock(&glock);
163
164 res = bpf_rbtree_first(&groot);
165 if (!res)
166 goto err_out;
167 res = bpf_rbtree_remove(&groot, res);
168
169 bpf_spin_unlock(&glock);
170
171 bpf_spin_lock(&glock);
172 /* Must check res for NULL before using in rbtree_add below */
173 bpf_rbtree_add(&groot, res, less);
174 bpf_spin_unlock(&glock);
175 return 0;
176
177 err_out:
178 bpf_spin_unlock(&glock);
179 return 1;
180 }
181
182 SEC("?tc")
183 __failure __msg("bpf_rbtree_remove can only take non-owning or refcounted bpf_rb_node pointer")
rbtree_api_add_release_unlock_escape(void * ctx)184 long rbtree_api_add_release_unlock_escape(void *ctx)
185 {
186 struct node_data *n;
187
188 n = bpf_obj_new(typeof(*n));
189 if (!n)
190 return 1;
191
192 bpf_spin_lock(&glock);
193 bpf_rbtree_add(&groot, &n->node, less);
194 bpf_spin_unlock(&glock);
195
196 bpf_spin_lock(&glock);
197 /* After add() in previous critical section, n should be
198 * release_on_unlock and released after previous spin_unlock,
199 * so should not be possible to use it here
200 */
201 bpf_rbtree_remove(&groot, &n->node);
202 bpf_spin_unlock(&glock);
203 return 0;
204 }
205
206 SEC("?tc")
207 __failure __msg("bpf_rbtree_remove can only take non-owning or refcounted bpf_rb_node pointer")
rbtree_api_first_release_unlock_escape(void * ctx)208 long rbtree_api_first_release_unlock_escape(void *ctx)
209 {
210 struct bpf_rb_node *res;
211 struct node_data *n;
212
213 bpf_spin_lock(&glock);
214 res = bpf_rbtree_first(&groot);
215 if (!res) {
216 bpf_spin_unlock(&glock);
217 return 1;
218 }
219 n = container_of(res, struct node_data, node);
220 bpf_spin_unlock(&glock);
221
222 bpf_spin_lock(&glock);
223 /* After first() in previous critical section, n should be
224 * release_on_unlock and released after previous spin_unlock,
225 * so should not be possible to use it here
226 */
227 bpf_rbtree_remove(&groot, &n->node);
228 bpf_spin_unlock(&glock);
229 return 0;
230 }
231
less__bad_fn_call_add(struct bpf_rb_node * a,const struct bpf_rb_node * b)232 static bool less__bad_fn_call_add(struct bpf_rb_node *a, const struct bpf_rb_node *b)
233 {
234 struct node_data *node_a;
235 struct node_data *node_b;
236
237 node_a = container_of(a, struct node_data, node);
238 node_b = container_of(b, struct node_data, node);
239 bpf_rbtree_add(&groot, &node_a->node, less);
240
241 return node_a->key < node_b->key;
242 }
243
less__bad_fn_call_remove(struct bpf_rb_node * a,const struct bpf_rb_node * b)244 static bool less__bad_fn_call_remove(struct bpf_rb_node *a, const struct bpf_rb_node *b)
245 {
246 struct node_data *node_a;
247 struct node_data *node_b;
248
249 node_a = container_of(a, struct node_data, node);
250 node_b = container_of(b, struct node_data, node);
251 bpf_rbtree_remove(&groot, &node_a->node);
252
253 return node_a->key < node_b->key;
254 }
255
less__bad_fn_call_first_unlock_after(struct bpf_rb_node * a,const struct bpf_rb_node * b)256 static bool less__bad_fn_call_first_unlock_after(struct bpf_rb_node *a, const struct bpf_rb_node *b)
257 {
258 struct node_data *node_a;
259 struct node_data *node_b;
260
261 node_a = container_of(a, struct node_data, node);
262 node_b = container_of(b, struct node_data, node);
263 bpf_rbtree_first(&groot);
264 bpf_spin_unlock(&glock);
265
266 return node_a->key < node_b->key;
267 }
268
less__bad_res_spin_unlock(struct bpf_rb_node * a,const struct bpf_rb_node * b)269 static bool less__bad_res_spin_unlock(struct bpf_rb_node *a, const struct bpf_rb_node *b)
270 {
271 bpf_res_spin_unlock(&res_glock);
272 return false;
273 }
274
rbtree_cb_unlock_relock(void)275 static __noinline void rbtree_cb_unlock_relock(void)
276 {
277 bpf_spin_unlock(&glock);
278 bpf_spin_lock(&glock);
279 }
280
rbtree_cb_nested_unlock(void)281 static __noinline void rbtree_cb_nested_unlock(void)
282 {
283 rbtree_cb_unlock_relock();
284 asm volatile ("");
285 }
286
less__bad_subprog_unlock(struct bpf_rb_node * a,const struct bpf_rb_node * b)287 static bool less__bad_subprog_unlock(struct bpf_rb_node *a, const struct bpf_rb_node *b)
288 {
289 struct node_data *node_a;
290 struct node_data *node_b;
291
292 node_a = container_of(a, struct node_data, node);
293 node_b = container_of(b, struct node_data, node);
294 rbtree_cb_nested_unlock();
295
296 return node_a->key < node_b->key;
297 }
298
rbtree_cb_noop(void)299 static __noinline void rbtree_cb_noop(void)
300 {
301 asm volatile ("");
302 }
303
less__subprog_allowed(struct bpf_rb_node * a,const struct bpf_rb_node * b)304 static bool less__subprog_allowed(struct bpf_rb_node *a, const struct bpf_rb_node *b)
305 {
306 struct node_data *node_a;
307 struct node_data *node_b;
308
309 node_a = container_of(a, struct node_data, node);
310 node_b = container_of(b, struct node_data, node);
311 rbtree_cb_noop();
312
313 return node_a->key < node_b->key;
314 }
315
316 static __always_inline
add_with_cb(bool (cb)(struct bpf_rb_node * a,const struct bpf_rb_node * b))317 long add_with_cb(bool (cb)(struct bpf_rb_node *a, const struct bpf_rb_node *b))
318 {
319 struct node_data *n;
320
321 n = bpf_obj_new(typeof(*n));
322 if (!n)
323 return 1;
324
325 bpf_spin_lock(&glock);
326 bpf_rbtree_add(&groot, &n->node, cb);
327 bpf_spin_unlock(&glock);
328 return 0;
329 }
330
331 SEC("?tc")
332 __failure __msg("R2 expected pointer to allocated object")
rbtree_api_add_bad_cb_bad_fn_call_add(void * ctx)333 long rbtree_api_add_bad_cb_bad_fn_call_add(void *ctx)
334 {
335 return add_with_cb(less__bad_fn_call_add);
336 }
337
338 SEC("?tc")
339 __failure __msg("rbtree_remove not allowed in rbtree cb")
rbtree_api_add_bad_cb_bad_fn_call_remove(void * ctx)340 long rbtree_api_add_bad_cb_bad_fn_call_remove(void *ctx)
341 {
342 return add_with_cb(less__bad_fn_call_remove);
343 }
344
345 SEC("?tc")
346 __failure __msg("can't spin_{lock,unlock} in rbtree cb")
rbtree_api_add_bad_cb_bad_fn_call_first_unlock_after(void * ctx)347 long rbtree_api_add_bad_cb_bad_fn_call_first_unlock_after(void *ctx)
348 {
349 return add_with_cb(less__bad_fn_call_first_unlock_after);
350 }
351
352 SEC("?tc")
353 __failure __msg("can't res_spin_{lock,unlock} in rbtree cb")
rbtree_api_add_bad_cb_res_spin_unlock(void * ctx)354 long rbtree_api_add_bad_cb_res_spin_unlock(void *ctx)
355 {
356 struct node_data *n;
357
358 n = bpf_obj_new(typeof(*n));
359 if (!n)
360 return 1;
361
362 bpf_spin_lock(&glock);
363 if (bpf_res_spin_lock(&res_glock)) {
364 bpf_spin_unlock(&glock);
365 bpf_obj_drop(n);
366 return 1;
367 }
368 bpf_rbtree_add(&groot, &n->node, less__bad_res_spin_unlock);
369 bpf_res_spin_unlock(&res_glock);
370 bpf_spin_unlock(&glock);
371 return 0;
372 }
373
374 SEC("?tc")
375 __failure __msg("can't spin_{lock,unlock} in rbtree cb")
rbtree_api_add_bad_cb_subprog_unlock(void * ctx)376 long rbtree_api_add_bad_cb_subprog_unlock(void *ctx)
377 {
378 return add_with_cb(less__bad_subprog_unlock);
379 }
380
381 SEC("?tc")
382 __success
rbtree_api_add_cb_subprog_allowed(void * ctx)383 long rbtree_api_add_cb_subprog_allowed(void *ctx)
384 {
385 return add_with_cb(less__subprog_allowed);
386 }
387
388 char _license[] SEC("license") = "GPL";
389