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