304 lines · c
1// SPDX-License-Identifier: GPL-2.02#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__failure __msg("rbtree_remove node input must be non-owning ref")73long 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 107SEC("?tc")108__failure __msg("Unreleased reference id=3 alloc_insn={{[0-9]+}}")109long 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 130unlock_err:131 bpf_spin_unlock(&glock);132 return 1;133}134 135SEC("?tc")136__failure __msg("arg#1 expected pointer to allocated object")137long 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 154SEC("?tc")155__failure __msg("dereference of modified ptr_or_null_ ptr R2 off=16 disallowed")156long 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 175err_out:176 bpf_spin_unlock(&glock);177 return 1;178}179 180SEC("?tc")181__failure __msg("rbtree_remove node input must be non-owning ref")182long 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 be196 * release_on_unlock and released after previous spin_unlock,197 * so should not be possible to use it here198 */199 bpf_rbtree_remove(&groot, &n->node);200 bpf_spin_unlock(&glock);201 return 0;202}203 204SEC("?tc")205__failure __msg("rbtree_remove node input must be non-owning ref")206long 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 be222 * release_on_unlock and released after previous spin_unlock,223 * so should not be possible to use it here224 */225 bpf_rbtree_remove(&groot, &n->node);226 bpf_spin_unlock(&glock);227 return 0;228}229 230static 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 242static 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 254static 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 267static __always_inline268long 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 282SEC("?tc")283__failure __msg("arg#1 expected pointer to allocated object")284long rbtree_api_add_bad_cb_bad_fn_call_add(void *ctx)285{286 return add_with_cb(less__bad_fn_call_add);287}288 289SEC("?tc")290__failure __msg("rbtree_remove not allowed in rbtree cb")291long rbtree_api_add_bad_cb_bad_fn_call_remove(void *ctx)292{293 return add_with_cb(less__bad_fn_call_remove);294}295 296SEC("?tc")297__failure __msg("can't spin_{lock,unlock} in rbtree cb")298long 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 303char _license[] SEC("license") = "GPL";304