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