tools/testing/selftests/bpf/progs/iters.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */
   3
   4 #include <stdbool.h>
   5 #include <linux/bpf.h>
   6 #include <bpf/bpf_helpers.h>
   7 #include "bpf_misc.h"
   8
   9 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
  10
  11 static volatile int zero = 0;
  12
  13 int my_pid;
  14 int arr[256];
  15 int small_arr[16] SEC(".data.small_arr");
  16
  17 #ifdef REAL_TEST
  18 #define MY_PID_GUARD() if (my_pid != (bpf_get_current_pid_tgid() >> 32)) return 0
  19 #else
  20 #define MY_PID_GUARD() ({ })
  21 #endif
  22
  23 SEC("?raw_tp")
  24 __failure __msg("math between map_value pointer and register with unbounded min value is not allowed")
  25 int iter_err_unsafe_c_loop(const void *ctx)
  26 {
  27         struct bpf_iter_num it;
  28         int *v, i = zero; /* obscure initial value of i */
  29
  30         MY_PID_GUARD();
  31
  32         bpf_iter_num_new(&it, 0, 1000);
  33         while ((v = bpf_iter_num_next(&it))) {
  34                 i++;
  35         }
  36         bpf_iter_num_destroy(&it);
  37
  38         small_arr[i] = 123; /* invalid */
  39
  40         return 0;
  41 }
  42
  43 SEC("?raw_tp")
  44 __failure __msg("unbounded memory access")
  45 int iter_err_unsafe_asm_loop(const void *ctx)
  46 {
  47         struct bpf_iter_num it;
  48
  49         MY_PID_GUARD();
  50
  51         asm volatile (
  52                 "r6 = %[zero];" /* iteration counter */
  53                 "r1 = %[it];" /* iterator state */
  54                 "r2 = 0;"
  55                 "r3 = 1000;"
  56                 "r4 = 1;"
  57                 "call %[bpf_iter_num_new];"
  58         "loop:"
  59                 "r1 = %[it];"
  60                 "call %[bpf_iter_num_next];"
  61                 "if r0 == 0 goto out;"
  62                 "r6 += 1;"
  63                 "goto loop;"
  64         "out:"
  65                 "r1 = %[it];"
  66                 "call %[bpf_iter_num_destroy];"
  67                 "r1 = %[small_arr];"
  68                 "r2 = r6;"
  69                 "r2 <<= 2;"
  70                 "r1 += r2;"
  71                 "*(u32 *)(r1 + 0) = r6;" /* invalid */
  72                 :
  73                 : [it]"r"(&it),
  74                   [small_arr]"p"(small_arr),
  75                   [zero]"p"(zero),
  76                   __imm(bpf_iter_num_new),
  77                   __imm(bpf_iter_num_next),
  78                   __imm(bpf_iter_num_destroy)
  79                 : __clobber_common, "r6"
  80         );
  81
  82         return 0;
  83 }
  84
  85 SEC("raw_tp")
  86 __success
  87 int iter_while_loop(const void *ctx)
  88 {
  89         struct bpf_iter_num it;
  90         int *v;
  91
  92         MY_PID_GUARD();
  93
  94         bpf_iter_num_new(&it, 0, 3);
  95         while ((v = bpf_iter_num_next(&it))) {
  96                 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v);
  97         }
  98         bpf_iter_num_destroy(&it);
  99
 100         return 0;
 101 }
 102
 103 SEC("raw_tp")
 104 __success
 105 int iter_while_loop_auto_cleanup(const void *ctx)
 106 {
 107         __attribute__((cleanup(bpf_iter_num_destroy))) struct bpf_iter_num it;
 108         int *v;
 109
 110         MY_PID_GUARD();
 111
 112         bpf_iter_num_new(&it, 0, 3);
 113         while ((v = bpf_iter_num_next(&it))) {
 114                 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v);
 115         }
 116         /* (!) no explicit bpf_iter_num_destroy() */
 117
 118         return 0;
 119 }
 120
 121 SEC("raw_tp")
 122 __success
 123 int iter_for_loop(const void *ctx)
 124 {
 125         struct bpf_iter_num it;
 126         int *v;
 127
 128         MY_PID_GUARD();
 129
 130         bpf_iter_num_new(&it, 5, 10);
 131         for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) {
 132                 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v);
 133         }
 134         bpf_iter_num_destroy(&it);
 135
 136         return 0;
 137 }
 138
 139 SEC("raw_tp")
 140 __success
 141 int iter_bpf_for_each_macro(const void *ctx)
 142 {
 143         int *v;
 144
 145         MY_PID_GUARD();
 146
 147         bpf_for_each(num, v, 5, 10) {
 148                 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v);
 149         }
 150
 151         return 0;
 152 }
 153
 154 SEC("raw_tp")
 155 __success
 156 int iter_bpf_for_macro(const void *ctx)
 157 {
 158         int i;
 159
 160         MY_PID_GUARD();
 161
 162         bpf_for(i, 5, 10) {
 163                 bpf_printk("ITER_BASIC: E2 VAL: v=%d", i);
 164         }
 165
 166         return 0;
 167 }
 168
 169 SEC("raw_tp")
 170 __success
 171 int iter_pragma_unroll_loop(const void *ctx)
 172 {
 173         struct bpf_iter_num it;
 174         int *v, i;
 175
 176         MY_PID_GUARD();
 177
 178         bpf_iter_num_new(&it, 0, 2);
 179 #pragma nounroll
 180         for (i = 0; i < 3; i++) {
 181                 v = bpf_iter_num_next(&it);
 182                 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1);
 183         }
 184         bpf_iter_num_destroy(&it);
 185
 186         return 0;
 187 }
 188
 189 SEC("raw_tp")
 190 __success
 191 int iter_manual_unroll_loop(const void *ctx)
 192 {
 193         struct bpf_iter_num it;
 194         int *v;
 195
 196         MY_PID_GUARD();
 197
 198         bpf_iter_num_new(&it, 100, 200);
 199         v = bpf_iter_num_next(&it);
 200         bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
 201         v = bpf_iter_num_next(&it);
 202         bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
 203         v = bpf_iter_num_next(&it);
 204         bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
 205         v = bpf_iter_num_next(&it);
 206         bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1);
 207         bpf_iter_num_destroy(&it);
 208
 209         return 0;
 210 }
 211
 212 SEC("raw_tp")
 213 __success
 214 int iter_multiple_sequential_loops(const void *ctx)
 215 {
 216         struct bpf_iter_num it;
 217         int *v, i;
 218
 219         MY_PID_GUARD();
 220
 221         bpf_iter_num_new(&it, 0, 3);
 222         while ((v = bpf_iter_num_next(&it))) {
 223                 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v);
 224         }
 225         bpf_iter_num_destroy(&it);
 226
 227         bpf_iter_num_new(&it, 5, 10);
 228         for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) {
 229                 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v);
 230         }
 231         bpf_iter_num_destroy(&it);
 232
 233         bpf_iter_num_new(&it, 0, 2);
 234 #pragma nounroll
 235         for (i = 0; i < 3; i++) {
 236                 v = bpf_iter_num_next(&it);
 237                 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1);
 238         }
 239         bpf_iter_num_destroy(&it);
 240
 241         bpf_iter_num_new(&it, 100, 200);
 242         v = bpf_iter_num_next(&it);
 243         bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
 244         v = bpf_iter_num_next(&it);
 245         bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
 246         v = bpf_iter_num_next(&it);
 247         bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
 248         v = bpf_iter_num_next(&it);
 249         bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1);
 250         bpf_iter_num_destroy(&it);
 251
 252         return 0;
 253 }
 254
 255 SEC("raw_tp")
 256 __success
 257 int iter_limit_cond_break_loop(const void *ctx)
 258 {
 259         struct bpf_iter_num it;
 260         int *v, i = 0, sum = 0;
 261
 262         MY_PID_GUARD();
 263
 264         bpf_iter_num_new(&it, 0, 10);
 265         while ((v = bpf_iter_num_next(&it))) {
 266                 bpf_printk("ITER_SIMPLE: i=%d v=%d", i, *v);
 267                 sum += *v;
 268
 269                 i++;
 270                 if (i > 3)
 271                         break;
 272         }
 273         bpf_iter_num_destroy(&it);
 274
 275         bpf_printk("ITER_SIMPLE: sum=%d\n", sum);
 276
 277         return 0;
 278 }
 279
 280 SEC("raw_tp")
 281 __success
 282 int iter_obfuscate_counter(const void *ctx)
 283 {
 284         struct bpf_iter_num it;
 285         int *v, sum = 0;
 286         /* Make i's initial value unknowable for verifier to prevent it from
 287          * pruning if/else branch inside the loop body and marking i as precise.
 288          */
 289         int i = zero;
 290
 291         MY_PID_GUARD();
 292
 293         bpf_iter_num_new(&it, 0, 10);
 294         while ((v = bpf_iter_num_next(&it))) {
 295                 int x;
 296
 297                 i += 1;
 298
 299                 /* If we initialized i as `int i = 0;` above, verifier would
 300                  * track that i becomes 1 on first iteration after increment
 301                  * above, and here verifier would eagerly prune else branch
 302                  * and mark i as precise, ruining open-coded iterator logic
 303                  * completely, as each next iteration would have a different
 304                  * *precise* value of i, and thus there would be no
 305                  * convergence of state. This would result in reaching maximum
 306                  * instruction limit, no matter what the limit is.
 307                  */
 308                 if (i == 1)
 309                         x = 123;
 310                 else
 311                         x = i * 3 + 1;
 312
 313                 bpf_printk("ITER_OBFUSCATE_COUNTER: i=%d v=%d x=%d", i, *v, x);
 314
 315                 sum += x;
 316         }
 317         bpf_iter_num_destroy(&it);
 318
 319         bpf_printk("ITER_OBFUSCATE_COUNTER: sum=%d\n", sum);
 320
 321         return 0;
 322 }
 323
 324 SEC("raw_tp")
 325 __success
 326 int iter_search_loop(const void *ctx)
 327 {
 328         struct bpf_iter_num it;
 329         int *v, *elem = NULL;
 330         bool found = false;
 331
 332         MY_PID_GUARD();
 333
 334         bpf_iter_num_new(&it, 0, 10);
 335
 336         while ((v = bpf_iter_num_next(&it))) {
 337                 bpf_printk("ITER_SEARCH_LOOP: v=%d", *v);
 338
 339                 if (*v == 2) {
 340                         found = true;
 341                         elem = v;
 342                         barrier_var(elem);
 343                 }
 344         }
 345
 346         /* should fail to verify if bpf_iter_num_destroy() is here */
 347
 348         if (found)
 349                 /* here found element will be wrong, we should have copied
 350                  * value to a variable, but here we want to make sure we can
 351                  * access memory after the loop anyways
 352                  */
 353                 bpf_printk("ITER_SEARCH_LOOP: FOUND IT = %d!\n", *elem);
 354         else
 355                 bpf_printk("ITER_SEARCH_LOOP: NOT FOUND IT!\n");
 356
 357         bpf_iter_num_destroy(&it);
 358
 359         return 0;
 360 }
 361
 362 SEC("raw_tp")
 363 __success
 364 int iter_array_fill(const void *ctx)
 365 {
 366         int sum, i;
 367
 368         MY_PID_GUARD();
 369
 370         bpf_for(i, 0, ARRAY_SIZE(arr)) {
 371                 arr[i] = i * 2;
 372         }
 373
 374         sum = 0;
 375         bpf_for(i, 0, ARRAY_SIZE(arr)) {
 376                 sum += arr[i];
 377         }
 378
 379         bpf_printk("ITER_ARRAY_FILL: sum=%d (should be %d)\n", sum, 255 * 256);
 380
 381         return 0;
 382 }
 383
 384 static int arr2d[4][5];
 385 static int arr2d_row_sums[4];
 386 static int arr2d_col_sums[5];
 387
 388 SEC("raw_tp")
 389 __success
 390 int iter_nested_iters(const void *ctx)
 391 {
 392         int sum, row, col;
 393
 394         MY_PID_GUARD();
 395
 396         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 397                 bpf_for( col, 0, ARRAY_SIZE(arr2d[0])) {
 398                         arr2d[row][col] = row * col;
 399                 }
 400         }
 401
 402         /* zero-initialize sums */
 403         sum = 0;
 404         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 405                 arr2d_row_sums[row] = 0;
 406         }
 407         bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
 408                 arr2d_col_sums[col] = 0;
 409         }
 410
 411         /* calculate sums */
 412         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 413                 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
 414                         sum += arr2d[row][col];
 415                         arr2d_row_sums[row] += arr2d[row][col];
 416                         arr2d_col_sums[col] += arr2d[row][col];
 417                 }
 418         }
 419
 420         bpf_printk("ITER_NESTED_ITERS: total sum=%d", sum);
 421         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 422                 bpf_printk("ITER_NESTED_ITERS: row #%d sum=%d", row, arr2d_row_sums[row]);
 423         }
 424         bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
 425                 bpf_printk("ITER_NESTED_ITERS: col #%d sum=%d%s",
 426                            col, arr2d_col_sums[col],
 427                            col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : "");
 428         }
 429
 430         return 0;
 431 }
 432
 433 SEC("raw_tp")
 434 __success
 435 int iter_nested_deeply_iters(const void *ctx)
 436 {
 437         int sum = 0;
 438
 439         MY_PID_GUARD();
 440
 441         bpf_repeat(10) {
 442                 bpf_repeat(10) {
 443                         bpf_repeat(10) {
 444                                 bpf_repeat(10) {
 445                                         bpf_repeat(10) {
 446                                                 sum += 1;
 447                                         }
 448                                 }
 449                         }
 450                 }
 451                 /* validate that we can break from inside bpf_repeat() */
 452                 break;
 453         }
 454
 455         return sum;
 456 }
 457
 458 static __noinline void fill_inner_dimension(int row)
 459 {
 460         int col;
 461
 462         bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
 463                 arr2d[row][col] = row * col;
 464         }
 465 }
 466
 467 static __noinline int sum_inner_dimension(int row)
 468 {
 469         int sum = 0, col;
 470
 471         bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
 472                 sum += arr2d[row][col];
 473                 arr2d_row_sums[row] += arr2d[row][col];
 474                 arr2d_col_sums[col] += arr2d[row][col];
 475         }
 476
 477         return sum;
 478 }
 479
 480 SEC("raw_tp")
 481 __success
 482 int iter_subprog_iters(const void *ctx)
 483 {
 484         int sum, row, col;
 485
 486         MY_PID_GUARD();
 487
 488         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 489                 fill_inner_dimension(row);
 490         }
 491
 492         /* zero-initialize sums */
 493         sum = 0;
 494         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 495                 arr2d_row_sums[row] = 0;
 496         }
 497         bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
 498                 arr2d_col_sums[col] = 0;
 499         }
 500
 501         /* calculate sums */
 502         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 503                 sum += sum_inner_dimension(row);
 504         }
 505
 506         bpf_printk("ITER_SUBPROG_ITERS: total sum=%d", sum);
 507         bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
 508                 bpf_printk("ITER_SUBPROG_ITERS: row #%d sum=%d",
 509                            row, arr2d_row_sums[row]);
 510         }
 511         bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
 512                 bpf_printk("ITER_SUBPROG_ITERS: col #%d sum=%d%s",
 513                            col, arr2d_col_sums[col],
 514                            col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : "");
 515         }
 516
 517         return 0;
 518 }
 519
 520 struct {
 521         __uint(type, BPF_MAP_TYPE_ARRAY);
 522         __type(key, int);
 523         __type(value, int);
 524         __uint(max_entries, 1000);
 525 } arr_map SEC(".maps");
 526
 527 SEC("?raw_tp")
 528 __failure __msg("invalid mem access 'scalar'")
 529 int iter_err_too_permissive1(const void *ctx)
 530 {
 531         int *map_val = NULL;
 532         int key = 0;
 533
 534         MY_PID_GUARD();
 535
 536         map_val = bpf_map_lookup_elem(&arr_map, &key);
 537         if (!map_val)
 538                 return 0;
 539
 540         bpf_repeat(1000000) {
 541                 map_val = NULL;
 542         }
 543
 544         *map_val = 123;
 545
 546         return 0;
 547 }
 548
 549 SEC("?raw_tp")
 550 __failure __msg("invalid mem access 'map_value_or_null'")
 551 int iter_err_too_permissive2(const void *ctx)
 552 {
 553         int *map_val = NULL;
 554         int key = 0;
 555
 556         MY_PID_GUARD();
 557
 558         map_val = bpf_map_lookup_elem(&arr_map, &key);
 559         if (!map_val)
 560                 return 0;
 561
 562         bpf_repeat(1000000) {
 563                 map_val = bpf_map_lookup_elem(&arr_map, &key);
 564         }
 565
 566         *map_val = 123;
 567
 568         return 0;
 569 }
 570
 571 SEC("?raw_tp")
 572 __failure __msg("invalid mem access 'map_value_or_null'")
 573 int iter_err_too_permissive3(const void *ctx)
 574 {
 575         int *map_val = NULL;
 576         int key = 0;
 577         bool found = false;
 578
 579         MY_PID_GUARD();
 580
 581         bpf_repeat(1000000) {
 582                 map_val = bpf_map_lookup_elem(&arr_map, &key);
 583                 found = true;
 584         }
 585
 586         if (found)
 587                 *map_val = 123;
 588
 589         return 0;
 590 }
 591
 592 SEC("raw_tp")
 593 __success
 594 int iter_tricky_but_fine(const void *ctx)
 595 {
 596         int *map_val = NULL;
 597         int key = 0;
 598         bool found = false;
 599
 600         MY_PID_GUARD();
 601
 602         bpf_repeat(1000000) {
 603                 map_val = bpf_map_lookup_elem(&arr_map, &key);
 604                 if (map_val) {
 605                         found = true;
 606                         break;
 607                 }
 608         }
 609
 610         if (found)
 611                 *map_val = 123;
 612
 613         return 0;
 614 }
 615
 616 #define __bpf_memzero(p, sz) bpf_probe_read_kernel((p), (sz), 0)
 617
 618 SEC("raw_tp")
 619 __success
 620 int iter_stack_array_loop(const void *ctx)
 621 {
 622         long arr1[16], arr2[16], sum = 0;
 623         int i;
 624
 625         MY_PID_GUARD();
 626
 627         /* zero-init arr1 and arr2 in such a way that verifier doesn't know
 628          * it's all zeros; if we don't do that, we'll make BPF verifier track
 629          * all combination of zero/non-zero stack slots for arr1/arr2, which
 630          * will lead to O(2^(ARRAY_SIZE(arr1)+ARRAY_SIZE(arr2))) different
 631          * states
 632          */
 633         __bpf_memzero(arr1, sizeof(arr1));
 634         __bpf_memzero(arr2, sizeof(arr1));
 635
 636         /* validate that we can break and continue when using bpf_for() */
 637         bpf_for(i, 0, ARRAY_SIZE(arr1)) {
 638                 if (i & 1) {
 639                         arr1[i] = i;
 640                         continue;
 641                 } else {
 642                         arr2[i] = i;
 643                         break;
 644                 }
 645         }
 646
 647         bpf_for(i, 0, ARRAY_SIZE(arr1)) {
 648                 sum += arr1[i] + arr2[i];
 649         }
 650
 651         return sum;
 652 }
 653
 654 static __noinline void fill(struct bpf_iter_num *it, int *arr, __u32 n, int mul)
 655 {
 656         int *t, i;
 657
 658         while ((t = bpf_iter_num_next(it))) {
 659                 i = *t;
 660                 if (i >= n)
 661                         break;
 662                 arr[i] =  i * mul;
 663         }
 664 }
 665
 666 static __noinline int sum(struct bpf_iter_num *it, int *arr, __u32 n)
 667 {
 668         int *t, i, sum = 0;;
 669
 670         while ((t = bpf_iter_num_next(it))) {
 671                 i = *t;
 672                 if (i >= n)
 673                         break;
 674                 sum += arr[i];
 675         }
 676
 677         return sum;
 678 }
 679
 680 SEC("raw_tp")
 681 __success
 682 int iter_pass_iter_ptr_to_subprog(const void *ctx)
 683 {
 684         int arr1[16], arr2[32];
 685         struct bpf_iter_num it;
 686         int n, sum1, sum2;
 687
 688         MY_PID_GUARD();
 689
 690         /* fill arr1 */
 691         n = ARRAY_SIZE(arr1);
 692         bpf_iter_num_new(&it, 0, n);
 693         fill(&it, arr1, n, 2);
 694         bpf_iter_num_destroy(&it);
 695
 696         /* fill arr2 */
 697         n = ARRAY_SIZE(arr2);
 698         bpf_iter_num_new(&it, 0, n);
 699         fill(&it, arr2, n, 10);
 700         bpf_iter_num_destroy(&it);
 701
 702         /* sum arr1 */
 703         n = ARRAY_SIZE(arr1);
 704         bpf_iter_num_new(&it, 0, n);
 705         sum1 = sum(&it, arr1, n);
 706         bpf_iter_num_destroy(&it);
 707
 708         /* sum arr2 */
 709         n = ARRAY_SIZE(arr2);
 710         bpf_iter_num_new(&it, 0, n);
 711         sum2 = sum(&it, arr2, n);
 712         bpf_iter_num_destroy(&it);
 713
 714         bpf_printk("sum1=%d, sum2=%d", sum1, sum2);
 715
 716         return 0;
 717 }
 718
 719 char _license[] SEC("license") = "GPL";