tools/testing/selftests/bpf/progs/linked_list.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
   8 #ifndef ARRAY_SIZE
   9 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
  10 #endif
  11
  12 #include "linked_list.h"
  13
  14 static __always_inline
  15 int list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool leave_in_map)
  16 {
  17         struct bpf_list_node *n;
  18         struct foo *f;
  19
  20         f = bpf_obj_new(typeof(*f));
  21         if (!f)
  22                 return 2;
  23
  24         bpf_spin_lock(lock);
  25         n = bpf_list_pop_front(head);
  26         bpf_spin_unlock(lock);
  27         if (n) {
  28                 bpf_obj_drop(container_of(n, struct foo, node2));
  29                 bpf_obj_drop(f);
  30                 return 3;
  31         }
  32
  33         bpf_spin_lock(lock);
  34         n = bpf_list_pop_back(head);
  35         bpf_spin_unlock(lock);
  36         if (n) {
  37                 bpf_obj_drop(container_of(n, struct foo, node2));
  38                 bpf_obj_drop(f);
  39                 return 4;
  40         }
  41
  42
  43         bpf_spin_lock(lock);
  44         f->data = 42;
  45         bpf_list_push_front(head, &f->node2);
  46         bpf_spin_unlock(lock);
  47         if (leave_in_map)
  48                 return 0;
  49         bpf_spin_lock(lock);
  50         n = bpf_list_pop_back(head);
  51         bpf_spin_unlock(lock);
  52         if (!n)
  53                 return 5;
  54         f = container_of(n, struct foo, node2);
  55         if (f->data != 42) {
  56                 bpf_obj_drop(f);
  57                 return 6;
  58         }
  59
  60         bpf_spin_lock(lock);
  61         f->data = 13;
  62         bpf_list_push_front(head, &f->node2);
  63         bpf_spin_unlock(lock);
  64         bpf_spin_lock(lock);
  65         n = bpf_list_pop_front(head);
  66         bpf_spin_unlock(lock);
  67         if (!n)
  68                 return 7;
  69         f = container_of(n, struct foo, node2);
  70         if (f->data != 13) {
  71                 bpf_obj_drop(f);
  72                 return 8;
  73         }
  74         bpf_obj_drop(f);
  75
  76         bpf_spin_lock(lock);
  77         n = bpf_list_pop_front(head);
  78         bpf_spin_unlock(lock);
  79         if (n) {
  80                 bpf_obj_drop(container_of(n, struct foo, node2));
  81                 return 9;
  82         }
  83
  84         bpf_spin_lock(lock);
  85         n = bpf_list_pop_back(head);
  86         bpf_spin_unlock(lock);
  87         if (n) {
  88                 bpf_obj_drop(container_of(n, struct foo, node2));
  89                 return 10;
  90         }
  91         return 0;
  92 }
  93
  94
  95 static __always_inline
  96 int list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool leave_in_map)
  97 {
  98         struct bpf_list_node *n;
  99         struct foo *f[200], *pf;
 100         int i;
 101
 102         /* Loop following this check adds nodes 2-at-a-time in order to
 103          * validate multiple release_on_unlock release logic
 104          */
 105         if (ARRAY_SIZE(f) % 2)
 106                 return 10;
 107
 108         for (i = 0; i < ARRAY_SIZE(f); i += 2) {
 109                 f[i] = bpf_obj_new(typeof(**f));
 110                 if (!f[i])
 111                         return 2;
 112                 f[i]->data = i;
 113
 114                 f[i + 1] = bpf_obj_new(typeof(**f));
 115                 if (!f[i + 1]) {
 116                         bpf_obj_drop(f[i]);
 117                         return 9;
 118                 }
 119                 f[i + 1]->data = i + 1;
 120
 121                 bpf_spin_lock(lock);
 122                 bpf_list_push_front(head, &f[i]->node2);
 123                 bpf_list_push_front(head, &f[i + 1]->node2);
 124                 bpf_spin_unlock(lock);
 125         }
 126
 127         for (i = 0; i < ARRAY_SIZE(f); i++) {
 128                 bpf_spin_lock(lock);
 129                 n = bpf_list_pop_front(head);
 130                 bpf_spin_unlock(lock);
 131                 if (!n)
 132                         return 3;
 133                 pf = container_of(n, struct foo, node2);
 134                 if (pf->data != (ARRAY_SIZE(f) - i - 1)) {
 135                         bpf_obj_drop(pf);
 136                         return 4;
 137                 }
 138                 bpf_spin_lock(lock);
 139                 bpf_list_push_back(head, &pf->node2);
 140                 bpf_spin_unlock(lock);
 141         }
 142
 143         if (leave_in_map)
 144                 return 0;
 145
 146         for (i = 0; i < ARRAY_SIZE(f); i++) {
 147                 bpf_spin_lock(lock);
 148                 n = bpf_list_pop_back(head);
 149                 bpf_spin_unlock(lock);
 150                 if (!n)
 151                         return 5;
 152                 pf = container_of(n, struct foo, node2);
 153                 if (pf->data != i) {
 154                         bpf_obj_drop(pf);
 155                         return 6;
 156                 }
 157                 bpf_obj_drop(pf);
 158         }
 159         bpf_spin_lock(lock);
 160         n = bpf_list_pop_back(head);
 161         bpf_spin_unlock(lock);
 162         if (n) {
 163                 bpf_obj_drop(container_of(n, struct foo, node2));
 164                 return 7;
 165         }
 166
 167         bpf_spin_lock(lock);
 168         n = bpf_list_pop_front(head);
 169         bpf_spin_unlock(lock);
 170         if (n) {
 171                 bpf_obj_drop(container_of(n, struct foo, node2));
 172                 return 8;
 173         }
 174         return 0;
 175 }
 176
 177 static __always_inline
 178 int list_in_list(struct bpf_spin_lock *lock, struct bpf_list_head *head, bool leave_in_map)
 179 {
 180         struct bpf_list_node *n;
 181         struct bar *ba[8], *b;
 182         struct foo *f;
 183         int i;
 184
 185         f = bpf_obj_new(typeof(*f));
 186         if (!f)
 187                 return 2;
 188         for (i = 0; i < ARRAY_SIZE(ba); i++) {
 189                 b = bpf_obj_new(typeof(*b));
 190                 if (!b) {
 191                         bpf_obj_drop(f);
 192                         return 3;
 193                 }
 194                 b->data = i;
 195                 bpf_spin_lock(&f->lock);
 196                 bpf_list_push_back(&f->head, &b->node);
 197                 bpf_spin_unlock(&f->lock);
 198         }
 199
 200         bpf_spin_lock(lock);
 201         f->data = 42;
 202         bpf_list_push_front(head, &f->node2);
 203         bpf_spin_unlock(lock);
 204
 205         if (leave_in_map)
 206                 return 0;
 207
 208         bpf_spin_lock(lock);
 209         n = bpf_list_pop_front(head);
 210         bpf_spin_unlock(lock);
 211         if (!n)
 212                 return 4;
 213         f = container_of(n, struct foo, node2);
 214         if (f->data != 42) {
 215                 bpf_obj_drop(f);
 216                 return 5;
 217         }
 218
 219         for (i = 0; i < ARRAY_SIZE(ba); i++) {
 220                 bpf_spin_lock(&f->lock);
 221                 n = bpf_list_pop_front(&f->head);
 222                 bpf_spin_unlock(&f->lock);
 223                 if (!n) {
 224                         bpf_obj_drop(f);
 225                         return 6;
 226                 }
 227                 b = container_of(n, struct bar, node);
 228                 if (b->data != i) {
 229                         bpf_obj_drop(f);
 230                         bpf_obj_drop(b);
 231                         return 7;
 232                 }
 233                 bpf_obj_drop(b);
 234         }
 235         bpf_spin_lock(&f->lock);
 236         n = bpf_list_pop_front(&f->head);
 237         bpf_spin_unlock(&f->lock);
 238         if (n) {
 239                 bpf_obj_drop(f);
 240                 bpf_obj_drop(container_of(n, struct bar, node));
 241                 return 8;
 242         }
 243         bpf_obj_drop(f);
 244         return 0;
 245 }
 246
 247 static __always_inline
 248 int test_list_push_pop(struct bpf_spin_lock *lock, struct bpf_list_head *head)
 249 {
 250         int ret;
 251
 252         ret = list_push_pop(lock, head, false);
 253         if (ret)
 254                 return ret;
 255         return list_push_pop(lock, head, true);
 256 }
 257
 258 static __always_inline
 259 int test_list_push_pop_multiple(struct bpf_spin_lock *lock, struct bpf_list_head *head)
 260 {
 261         int ret;
 262
 263         ret = list_push_pop_multiple(lock, head, false);
 264         if (ret)
 265                 return ret;
 266         return list_push_pop_multiple(lock, head, true);
 267 }
 268
 269 static __always_inline
 270 int test_list_in_list(struct bpf_spin_lock *lock, struct bpf_list_head *head)
 271 {
 272         int ret;
 273
 274         ret = list_in_list(lock, head, false);
 275         if (ret)
 276                 return ret;
 277         return list_in_list(lock, head, true);
 278 }
 279
 280 SEC("tc")
 281 int map_list_push_pop(void *ctx)
 282 {
 283         struct map_value *v;
 284
 285         v = bpf_map_lookup_elem(&array_map, &(int){0});
 286         if (!v)
 287                 return 1;
 288         return test_list_push_pop(&v->lock, &v->head);
 289 }
 290
 291 SEC("tc")
 292 int inner_map_list_push_pop(void *ctx)
 293 {
 294         struct map_value *v;
 295         void *map;
 296
 297         map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
 298         if (!map)
 299                 return 1;
 300         v = bpf_map_lookup_elem(map, &(int){0});
 301         if (!v)
 302                 return 1;
 303         return test_list_push_pop(&v->lock, &v->head);
 304 }
 305
 306 SEC("tc")
 307 int global_list_push_pop(void *ctx)
 308 {
 309         return test_list_push_pop(&glock, &ghead);
 310 }
 311
 312 SEC("tc")
 313 int map_list_push_pop_multiple(void *ctx)
 314 {
 315         struct map_value *v;
 316
 317         v = bpf_map_lookup_elem(&array_map, &(int){0});
 318         if (!v)
 319                 return 1;
 320         return test_list_push_pop_multiple(&v->lock, &v->head);
 321 }
 322
 323 SEC("tc")
 324 int inner_map_list_push_pop_multiple(void *ctx)
 325 {
 326         struct map_value *v;
 327         void *map;
 328
 329         map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
 330         if (!map)
 331                 return 1;
 332         v = bpf_map_lookup_elem(map, &(int){0});
 333         if (!v)
 334                 return 1;
 335         return test_list_push_pop_multiple(&v->lock, &v->head);
 336 }
 337
 338 SEC("tc")
 339 int global_list_push_pop_multiple(void *ctx)
 340 {
 341         int ret;
 342
 343         ret = list_push_pop_multiple(&glock, &ghead, false);
 344         if (ret)
 345                 return ret;
 346         return list_push_pop_multiple(&glock, &ghead, true);
 347 }
 348
 349 SEC("tc")
 350 int map_list_in_list(void *ctx)
 351 {
 352         struct map_value *v;
 353
 354         v = bpf_map_lookup_elem(&array_map, &(int){0});
 355         if (!v)
 356                 return 1;
 357         return test_list_in_list(&v->lock, &v->head);
 358 }
 359
 360 SEC("tc")
 361 int inner_map_list_in_list(void *ctx)
 362 {
 363         struct map_value *v;
 364         void *map;
 365
 366         map = bpf_map_lookup_elem(&map_of_maps, &(int){0});
 367         if (!map)
 368                 return 1;
 369         v = bpf_map_lookup_elem(map, &(int){0});
 370         if (!v)
 371                 return 1;
 372         return test_list_in_list(&v->lock, &v->head);
 373 }
 374
 375 SEC("tc")
 376 int global_list_in_list(void *ctx)
 377 {
 378         return test_list_in_list(&glock, &ghead);
 379 }
 380
 381 char _license[] SEC("license") = "GPL";