tools/testing/selftests/bpf/progs/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
   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";