rbtree_fail.c

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