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 
20 static bool less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
21 {
22 	struct node_data *node_a;
23 	struct node_data *node_b;
24 
25 	node_a = container_of(a, struct node_data, node);
26 	node_b = container_of(b, struct node_data, node);
27 
28 	return node_a->key < node_b->key;
29 }
30 
31 SEC("?tc")
32 __failure __msg("bpf_spin_lock at off=16 must be held for bpf_rb_root")
33 long rbtree_api_nolock_add(void *ctx)
34 {
35 	struct node_data *n;
36 
37 	n = bpf_obj_new(typeof(*n));
38 	if (!n)
39 		return 1;
40 
41 	bpf_rbtree_add(&groot, &n->node, less);
42 	return 0;
43 }
44 
45 SEC("?tc")
46 __failure __msg("bpf_spin_lock at off=16 must be held for bpf_rb_root")
47 long rbtree_api_nolock_remove(void *ctx)
48 {
49 	struct node_data *n;
50 
51 	n = bpf_obj_new(typeof(*n));
52 	if (!n)
53 		return 1;
54 
55 	bpf_spin_lock(&glock);
56 	bpf_rbtree_add(&groot, &n->node, less);
57 	bpf_spin_unlock(&glock);
58 
59 	bpf_rbtree_remove(&groot, &n->node);
60 	return 0;
61 }
62 
63 SEC("?tc")
64 __failure __msg("bpf_spin_lock at off=16 must be held for bpf_rb_root")
65 long rbtree_api_nolock_first(void *ctx)
66 {
67 	bpf_rbtree_first(&groot);
68 	return 0;
69 }
70 
71 SEC("?tc")
72 __failure __msg("rbtree_remove node input must be non-owning ref")
73 long rbtree_api_remove_unadded_node(void *ctx)
74 {
75 	struct node_data *n, *m;
76 	struct bpf_rb_node *res;
77 
78 	n = bpf_obj_new(typeof(*n));
79 	if (!n)
80 		return 1;
81 
82 	m = bpf_obj_new(typeof(*m));
83 	if (!m) {
84 		bpf_obj_drop(n);
85 		return 1;
86 	}
87 
88 	bpf_spin_lock(&glock);
89 	bpf_rbtree_add(&groot, &n->node, less);
90 
91 	/* This remove should pass verifier */
92 	res = bpf_rbtree_remove(&groot, &n->node);
93 	n = container_of(res, struct node_data, node);
94 
95 	/* This remove shouldn't, m isn't in an rbtree */
96 	res = bpf_rbtree_remove(&groot, &m->node);
97 	m = container_of(res, struct node_data, node);
98 	bpf_spin_unlock(&glock);
99 
100 	if (n)
101 		bpf_obj_drop(n);
102 	if (m)
103 		bpf_obj_drop(m);
104 	return 0;
105 }
106 
107 SEC("?tc")
108 __failure __msg("Unreleased reference id=3 alloc_insn=10")
109 long rbtree_api_remove_no_drop(void *ctx)
110 {
111 	struct bpf_rb_node *res;
112 	struct node_data *n;
113 
114 	bpf_spin_lock(&glock);
115 	res = bpf_rbtree_first(&groot);
116 	if (!res)
117 		goto unlock_err;
118 
119 	res = bpf_rbtree_remove(&groot, res);
120 
121 	if (res) {
122 		n = container_of(res, struct node_data, node);
123 		__sink(n);
124 	}
125 	bpf_spin_unlock(&glock);
126 
127 	/* if (res) { bpf_obj_drop(n); } is missing here */
128 	return 0;
129 
130 unlock_err:
131 	bpf_spin_unlock(&glock);
132 	return 1;
133 }
134 
135 SEC("?tc")
136 __failure __msg("arg#1 expected pointer to allocated object")
137 long rbtree_api_add_to_multiple_trees(void *ctx)
138 {
139 	struct node_data *n;
140 
141 	n = bpf_obj_new(typeof(*n));
142 	if (!n)
143 		return 1;
144 
145 	bpf_spin_lock(&glock);
146 	bpf_rbtree_add(&groot, &n->node, less);
147 
148 	/* This add should fail since n already in groot's tree */
149 	bpf_rbtree_add(&groot2, &n->node, less);
150 	bpf_spin_unlock(&glock);
151 	return 0;
152 }
153 
154 SEC("?tc")
155 __failure __msg("dereference of modified ptr_or_null_ ptr R2 off=16 disallowed")
156 long rbtree_api_use_unchecked_remove_retval(void *ctx)
157 {
158 	struct bpf_rb_node *res;
159 
160 	bpf_spin_lock(&glock);
161 
162 	res = bpf_rbtree_first(&groot);
163 	if (!res)
164 		goto err_out;
165 	res = bpf_rbtree_remove(&groot, res);
166 
167 	bpf_spin_unlock(&glock);
168 
169 	bpf_spin_lock(&glock);
170 	/* Must check res for NULL before using in rbtree_add below */
171 	bpf_rbtree_add(&groot, res, less);
172 	bpf_spin_unlock(&glock);
173 	return 0;
174 
175 err_out:
176 	bpf_spin_unlock(&glock);
177 	return 1;
178 }
179 
180 SEC("?tc")
181 __failure __msg("rbtree_remove node input must be non-owning ref")
182 long rbtree_api_add_release_unlock_escape(void *ctx)
183 {
184 	struct node_data *n;
185 
186 	n = bpf_obj_new(typeof(*n));
187 	if (!n)
188 		return 1;
189 
190 	bpf_spin_lock(&glock);
191 	bpf_rbtree_add(&groot, &n->node, less);
192 	bpf_spin_unlock(&glock);
193 
194 	bpf_spin_lock(&glock);
195 	/* After add() in previous critical section, n should be
196 	 * release_on_unlock and released after previous spin_unlock,
197 	 * so should not be possible to use it here
198 	 */
199 	bpf_rbtree_remove(&groot, &n->node);
200 	bpf_spin_unlock(&glock);
201 	return 0;
202 }
203 
204 SEC("?tc")
205 __failure __msg("rbtree_remove node input must be non-owning ref")
206 long rbtree_api_first_release_unlock_escape(void *ctx)
207 {
208 	struct bpf_rb_node *res;
209 	struct node_data *n;
210 
211 	bpf_spin_lock(&glock);
212 	res = bpf_rbtree_first(&groot);
213 	if (!res) {
214 		bpf_spin_unlock(&glock);
215 		return 1;
216 	}
217 	n = container_of(res, struct node_data, node);
218 	bpf_spin_unlock(&glock);
219 
220 	bpf_spin_lock(&glock);
221 	/* After first() in previous critical section, n should be
222 	 * release_on_unlock and released after previous spin_unlock,
223 	 * so should not be possible to use it here
224 	 */
225 	bpf_rbtree_remove(&groot, &n->node);
226 	bpf_spin_unlock(&glock);
227 	return 0;
228 }
229 
230 static bool less__bad_fn_call_add(struct bpf_rb_node *a, const struct bpf_rb_node *b)
231 {
232 	struct node_data *node_a;
233 	struct node_data *node_b;
234 
235 	node_a = container_of(a, struct node_data, node);
236 	node_b = container_of(b, struct node_data, node);
237 	bpf_rbtree_add(&groot, &node_a->node, less);
238 
239 	return node_a->key < node_b->key;
240 }
241 
242 static bool less__bad_fn_call_remove(struct bpf_rb_node *a, const struct bpf_rb_node *b)
243 {
244 	struct node_data *node_a;
245 	struct node_data *node_b;
246 
247 	node_a = container_of(a, struct node_data, node);
248 	node_b = container_of(b, struct node_data, node);
249 	bpf_rbtree_remove(&groot, &node_a->node);
250 
251 	return node_a->key < node_b->key;
252 }
253 
254 static bool less__bad_fn_call_first_unlock_after(struct bpf_rb_node *a, const struct bpf_rb_node *b)
255 {
256 	struct node_data *node_a;
257 	struct node_data *node_b;
258 
259 	node_a = container_of(a, struct node_data, node);
260 	node_b = container_of(b, struct node_data, node);
261 	bpf_rbtree_first(&groot);
262 	bpf_spin_unlock(&glock);
263 
264 	return node_a->key < node_b->key;
265 }
266 
267 static __always_inline
268 long add_with_cb(bool (cb)(struct bpf_rb_node *a, const struct bpf_rb_node *b))
269 {
270 	struct node_data *n;
271 
272 	n = bpf_obj_new(typeof(*n));
273 	if (!n)
274 		return 1;
275 
276 	bpf_spin_lock(&glock);
277 	bpf_rbtree_add(&groot, &n->node, cb);
278 	bpf_spin_unlock(&glock);
279 	return 0;
280 }
281 
282 SEC("?tc")
283 __failure __msg("arg#1 expected pointer to allocated object")
284 long rbtree_api_add_bad_cb_bad_fn_call_add(void *ctx)
285 {
286 	return add_with_cb(less__bad_fn_call_add);
287 }
288 
289 SEC("?tc")
290 __failure __msg("rbtree_remove not allowed in rbtree cb")
291 long rbtree_api_add_bad_cb_bad_fn_call_remove(void *ctx)
292 {
293 	return add_with_cb(less__bad_fn_call_remove);
294 }
295 
296 SEC("?tc")
297 __failure __msg("can't spin_{lock,unlock} in rbtree cb")
298 long rbtree_api_add_bad_cb_bad_fn_call_first_unlock_after(void *ctx)
299 {
300 	return add_with_cb(less__bad_fn_call_first_unlock_after);
301 }
302 
303 char _license[] SEC("license") = "GPL";
304