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=2 alloc_insn=11") 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 n = container_of(res, struct node_data, node); 122 bpf_spin_unlock(&glock); 123 124 /* bpf_obj_drop(n) is missing here */ 125 return 0; 126 127 unlock_err: 128 bpf_spin_unlock(&glock); 129 return 1; 130 } 131 132 SEC("?tc") 133 __failure __msg("arg#1 expected pointer to allocated object") 134 long rbtree_api_add_to_multiple_trees(void *ctx) 135 { 136 struct node_data *n; 137 138 n = bpf_obj_new(typeof(*n)); 139 if (!n) 140 return 1; 141 142 bpf_spin_lock(&glock); 143 bpf_rbtree_add(&groot, &n->node, less); 144 145 /* This add should fail since n already in groot's tree */ 146 bpf_rbtree_add(&groot2, &n->node, less); 147 bpf_spin_unlock(&glock); 148 return 0; 149 } 150 151 SEC("?tc") 152 __failure __msg("rbtree_remove node input must be non-owning ref") 153 long rbtree_api_add_release_unlock_escape(void *ctx) 154 { 155 struct node_data *n; 156 157 n = bpf_obj_new(typeof(*n)); 158 if (!n) 159 return 1; 160 161 bpf_spin_lock(&glock); 162 bpf_rbtree_add(&groot, &n->node, less); 163 bpf_spin_unlock(&glock); 164 165 bpf_spin_lock(&glock); 166 /* After add() in previous critical section, n should be 167 * release_on_unlock and released after previous spin_unlock, 168 * so should not be possible to use it here 169 */ 170 bpf_rbtree_remove(&groot, &n->node); 171 bpf_spin_unlock(&glock); 172 return 0; 173 } 174 175 SEC("?tc") 176 __failure __msg("rbtree_remove node input must be non-owning ref") 177 long rbtree_api_release_aliasing(void *ctx) 178 { 179 struct node_data *n, *m, *o; 180 struct bpf_rb_node *res; 181 182 n = bpf_obj_new(typeof(*n)); 183 if (!n) 184 return 1; 185 186 bpf_spin_lock(&glock); 187 bpf_rbtree_add(&groot, &n->node, less); 188 bpf_spin_unlock(&glock); 189 190 bpf_spin_lock(&glock); 191 192 /* m and o point to the same node, 193 * but verifier doesn't know this 194 */ 195 res = bpf_rbtree_first(&groot); 196 if (!res) 197 return 1; 198 o = container_of(res, struct node_data, node); 199 200 res = bpf_rbtree_first(&groot); 201 if (!res) 202 return 1; 203 m = container_of(res, struct node_data, node); 204 205 bpf_rbtree_remove(&groot, &m->node); 206 /* This second remove shouldn't be possible. Retval of previous 207 * remove returns owning reference to m, which is the same 208 * node o's non-owning ref is pointing at 209 * 210 * In order to preserve property 211 * * owning ref must not be in rbtree 212 * * non-owning ref must be in rbtree 213 * 214 * o's ref must be invalidated after previous remove. Otherwise 215 * we'd have non-owning ref to node that isn't in rbtree, and 216 * verifier wouldn't be able to use type system to prevent remove 217 * of ref that already isn't in any tree. Would have to do runtime 218 * checks in that case. 219 */ 220 bpf_rbtree_remove(&groot, &o->node); 221 222 bpf_spin_unlock(&glock); 223 return 0; 224 } 225 226 SEC("?tc") 227 __failure __msg("rbtree_remove node input must be non-owning ref") 228 long rbtree_api_first_release_unlock_escape(void *ctx) 229 { 230 struct bpf_rb_node *res; 231 struct node_data *n; 232 233 bpf_spin_lock(&glock); 234 res = bpf_rbtree_first(&groot); 235 if (!res) { 236 bpf_spin_unlock(&glock); 237 return 1; 238 } 239 n = container_of(res, struct node_data, node); 240 bpf_spin_unlock(&glock); 241 242 bpf_spin_lock(&glock); 243 /* After first() in previous critical section, n should be 244 * release_on_unlock and released after previous spin_unlock, 245 * so should not be possible to use it here 246 */ 247 bpf_rbtree_remove(&groot, &n->node); 248 bpf_spin_unlock(&glock); 249 return 0; 250 } 251 252 static bool less__bad_fn_call_add(struct bpf_rb_node *a, const struct bpf_rb_node *b) 253 { 254 struct node_data *node_a; 255 struct node_data *node_b; 256 257 node_a = container_of(a, struct node_data, node); 258 node_b = container_of(b, struct node_data, node); 259 bpf_rbtree_add(&groot, &node_a->node, less); 260 261 return node_a->key < node_b->key; 262 } 263 264 static bool less__bad_fn_call_remove(struct bpf_rb_node *a, const struct bpf_rb_node *b) 265 { 266 struct node_data *node_a; 267 struct node_data *node_b; 268 269 node_a = container_of(a, struct node_data, node); 270 node_b = container_of(b, struct node_data, node); 271 bpf_rbtree_remove(&groot, &node_a->node); 272 273 return node_a->key < node_b->key; 274 } 275 276 static bool less__bad_fn_call_first_unlock_after(struct bpf_rb_node *a, const struct bpf_rb_node *b) 277 { 278 struct node_data *node_a; 279 struct node_data *node_b; 280 281 node_a = container_of(a, struct node_data, node); 282 node_b = container_of(b, struct node_data, node); 283 bpf_rbtree_first(&groot); 284 bpf_spin_unlock(&glock); 285 286 return node_a->key < node_b->key; 287 } 288 289 static __always_inline 290 long add_with_cb(bool (cb)(struct bpf_rb_node *a, const struct bpf_rb_node *b)) 291 { 292 struct node_data *n; 293 294 n = bpf_obj_new(typeof(*n)); 295 if (!n) 296 return 1; 297 298 bpf_spin_lock(&glock); 299 bpf_rbtree_add(&groot, &n->node, cb); 300 bpf_spin_unlock(&glock); 301 return 0; 302 } 303 304 SEC("?tc") 305 __failure __msg("arg#1 expected pointer to allocated object") 306 long rbtree_api_add_bad_cb_bad_fn_call_add(void *ctx) 307 { 308 return add_with_cb(less__bad_fn_call_add); 309 } 310 311 SEC("?tc") 312 __failure __msg("rbtree_remove not allowed in rbtree cb") 313 long rbtree_api_add_bad_cb_bad_fn_call_remove(void *ctx) 314 { 315 return add_with_cb(less__bad_fn_call_remove); 316 } 317 318 SEC("?tc") 319 __failure __msg("can't spin_{lock,unlock} in rbtree cb") 320 long rbtree_api_add_bad_cb_bad_fn_call_first_unlock_after(void *ctx) 321 { 322 return add_with_cb(less__bad_fn_call_first_unlock_after); 323 } 324 325 char _license[] SEC("license") = "GPL"; 326