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#include "bpf_compiler.h" 9 10#define ARRAY_SIZE(x) (int)(sizeof(x) / sizeof((x)[0])) 11 12static volatile int zero = 0; 13 14int my_pid; 15int arr[256]; 16int small_arr[16] SEC(".data.small_arr"); 17 18struct { 19 __uint(type, BPF_MAP_TYPE_HASH); 20 __uint(max_entries, 10); 21 __type(key, int); 22 __type(value, int); 23} amap SEC(".maps"); 24 25#ifdef REAL_TEST 26#define MY_PID_GUARD() if (my_pid != (bpf_get_current_pid_tgid() >> 32)) return 0 27#else 28#define MY_PID_GUARD() ({ }) 29#endif 30 31SEC("?raw_tp") 32__failure __msg("math between map_value pointer and register with unbounded min value is not allowed") 33int iter_err_unsafe_c_loop(const void *ctx) 34{ 35 struct bpf_iter_num it; 36 int *v, i = zero; /* obscure initial value of i */ 37 38 MY_PID_GUARD(); 39 40 bpf_iter_num_new(&it, 0, 1000); 41 while ((v = bpf_iter_num_next(&it))) { 42 i++; 43 } 44 bpf_iter_num_destroy(&it); 45 46 small_arr[i] = 123; /* invalid */ 47 48 return 0; 49} 50 51SEC("?raw_tp") 52__failure __msg("unbounded memory access") 53int iter_err_unsafe_asm_loop(const void *ctx) 54{ 55 struct bpf_iter_num it; 56 57 MY_PID_GUARD(); 58 59 asm volatile ( 60 "r6 = %[zero];" /* iteration counter */ 61 "r1 = %[it];" /* iterator state */ 62 "r2 = 0;" 63 "r3 = 1000;" 64 "r4 = 1;" 65 "call %[bpf_iter_num_new];" 66 "loop:" 67 "r1 = %[it];" 68 "call %[bpf_iter_num_next];" 69 "if r0 == 0 goto out;" 70 "r6 += 1;" 71 "goto loop;" 72 "out:" 73 "r1 = %[it];" 74 "call %[bpf_iter_num_destroy];" 75 "r1 = %[small_arr];" 76 "r2 = r6;" 77 "r2 <<= 2;" 78 "r1 += r2;" 79 "*(u32 *)(r1 + 0) = r6;" /* invalid */ 80 : 81 : [it]"r"(&it), 82 [small_arr]"r"(small_arr), 83 [zero]"r"(zero), 84 __imm(bpf_iter_num_new), 85 __imm(bpf_iter_num_next), 86 __imm(bpf_iter_num_destroy) 87 : __clobber_common, "r6" 88 ); 89 90 return 0; 91} 92 93SEC("raw_tp") 94__success 95int iter_while_loop(const void *ctx) 96{ 97 struct bpf_iter_num it; 98 int *v; 99 100 MY_PID_GUARD(); 101 102 bpf_iter_num_new(&it, 0, 3); 103 while ((v = bpf_iter_num_next(&it))) { 104 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v); 105 } 106 bpf_iter_num_destroy(&it); 107 108 return 0; 109} 110 111SEC("raw_tp") 112__success 113int iter_while_loop_auto_cleanup(const void *ctx) 114{ 115 __attribute__((cleanup(bpf_iter_num_destroy))) struct bpf_iter_num it; 116 int *v; 117 118 MY_PID_GUARD(); 119 120 bpf_iter_num_new(&it, 0, 3); 121 while ((v = bpf_iter_num_next(&it))) { 122 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v); 123 } 124 /* (!) no explicit bpf_iter_num_destroy() */ 125 126 return 0; 127} 128 129SEC("raw_tp") 130__success 131int iter_for_loop(const void *ctx) 132{ 133 struct bpf_iter_num it; 134 int *v; 135 136 MY_PID_GUARD(); 137 138 bpf_iter_num_new(&it, 5, 10); 139 for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) { 140 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v); 141 } 142 bpf_iter_num_destroy(&it); 143 144 return 0; 145} 146 147SEC("raw_tp") 148__success 149int iter_bpf_for_each_macro(const void *ctx) 150{ 151 int *v; 152 153 MY_PID_GUARD(); 154 155 bpf_for_each(num, v, 5, 10) { 156 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v); 157 } 158 159 return 0; 160} 161 162SEC("raw_tp") 163__success 164int iter_bpf_for_macro(const void *ctx) 165{ 166 int i; 167 168 MY_PID_GUARD(); 169 170 bpf_for(i, 5, 10) { 171 bpf_printk("ITER_BASIC: E2 VAL: v=%d", i); 172 } 173 174 return 0; 175} 176 177SEC("raw_tp") 178__success 179int iter_pragma_unroll_loop(const void *ctx) 180{ 181 struct bpf_iter_num it; 182 int *v, i; 183 184 MY_PID_GUARD(); 185 186 bpf_iter_num_new(&it, 0, 2); 187 __pragma_loop_no_unroll 188 for (i = 0; i < 3; i++) { 189 v = bpf_iter_num_next(&it); 190 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1); 191 } 192 bpf_iter_num_destroy(&it); 193 194 return 0; 195} 196 197SEC("raw_tp") 198__success 199int iter_manual_unroll_loop(const void *ctx) 200{ 201 struct bpf_iter_num it; 202 int *v; 203 204 MY_PID_GUARD(); 205 206 bpf_iter_num_new(&it, 100, 200); 207 v = bpf_iter_num_next(&it); 208 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 209 v = bpf_iter_num_next(&it); 210 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 211 v = bpf_iter_num_next(&it); 212 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 213 v = bpf_iter_num_next(&it); 214 bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1); 215 bpf_iter_num_destroy(&it); 216 217 return 0; 218} 219 220SEC("raw_tp") 221__success 222int iter_multiple_sequential_loops(const void *ctx) 223{ 224 struct bpf_iter_num it; 225 int *v, i; 226 227 MY_PID_GUARD(); 228 229 bpf_iter_num_new(&it, 0, 3); 230 while ((v = bpf_iter_num_next(&it))) { 231 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v); 232 } 233 bpf_iter_num_destroy(&it); 234 235 bpf_iter_num_new(&it, 5, 10); 236 for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) { 237 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v); 238 } 239 bpf_iter_num_destroy(&it); 240 241 bpf_iter_num_new(&it, 0, 2); 242 __pragma_loop_no_unroll 243 for (i = 0; i < 3; i++) { 244 v = bpf_iter_num_next(&it); 245 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1); 246 } 247 bpf_iter_num_destroy(&it); 248 249 bpf_iter_num_new(&it, 100, 200); 250 v = bpf_iter_num_next(&it); 251 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 252 v = bpf_iter_num_next(&it); 253 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 254 v = bpf_iter_num_next(&it); 255 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 256 v = bpf_iter_num_next(&it); 257 bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1); 258 bpf_iter_num_destroy(&it); 259 260 return 0; 261} 262 263SEC("raw_tp") 264__success 265int iter_limit_cond_break_loop(const void *ctx) 266{ 267 struct bpf_iter_num it; 268 int *v, i = 0, sum = 0; 269 270 MY_PID_GUARD(); 271 272 bpf_iter_num_new(&it, 0, 10); 273 while ((v = bpf_iter_num_next(&it))) { 274 bpf_printk("ITER_SIMPLE: i=%d v=%d", i, *v); 275 sum += *v; 276 277 i++; 278 if (i > 3) 279 break; 280 } 281 bpf_iter_num_destroy(&it); 282 283 bpf_printk("ITER_SIMPLE: sum=%d\n", sum); 284 285 return 0; 286} 287 288SEC("raw_tp") 289__success 290int iter_obfuscate_counter(const void *ctx) 291{ 292 struct bpf_iter_num it; 293 int *v, sum = 0; 294 /* Make i's initial value unknowable for verifier to prevent it from 295 * pruning if/else branch inside the loop body and marking i as precise. 296 */ 297 int i = zero; 298 299 MY_PID_GUARD(); 300 301 bpf_iter_num_new(&it, 0, 10); 302 while ((v = bpf_iter_num_next(&it))) { 303 int x; 304 305 i += 1; 306 307 /* If we initialized i as `int i = 0;` above, verifier would 308 * track that i becomes 1 on first iteration after increment 309 * above, and here verifier would eagerly prune else branch 310 * and mark i as precise, ruining open-coded iterator logic 311 * completely, as each next iteration would have a different 312 * *precise* value of i, and thus there would be no 313 * convergence of state. This would result in reaching maximum 314 * instruction limit, no matter what the limit is. 315 */ 316 if (i == 1) 317 x = 123; 318 else 319 x = i * 3 + 1; 320 321 bpf_printk("ITER_OBFUSCATE_COUNTER: i=%d v=%d x=%d", i, *v, x); 322 323 sum += x; 324 } 325 bpf_iter_num_destroy(&it); 326 327 bpf_printk("ITER_OBFUSCATE_COUNTER: sum=%d\n", sum); 328 329 return 0; 330} 331 332SEC("raw_tp") 333__success 334int iter_search_loop(const void *ctx) 335{ 336 struct bpf_iter_num it; 337 int *v, *elem = NULL; 338 bool found = false; 339 340 MY_PID_GUARD(); 341 342 bpf_iter_num_new(&it, 0, 10); 343 344 while ((v = bpf_iter_num_next(&it))) { 345 bpf_printk("ITER_SEARCH_LOOP: v=%d", *v); 346 347 if (*v == 2) { 348 found = true; 349 elem = v; 350 barrier_var(elem); 351 } 352 } 353 354 /* should fail to verify if bpf_iter_num_destroy() is here */ 355 356 if (found) 357 /* here found element will be wrong, we should have copied 358 * value to a variable, but here we want to make sure we can 359 * access memory after the loop anyways 360 */ 361 bpf_printk("ITER_SEARCH_LOOP: FOUND IT = %d!\n", *elem); 362 else 363 bpf_printk("ITER_SEARCH_LOOP: NOT FOUND IT!\n"); 364 365 bpf_iter_num_destroy(&it); 366 367 return 0; 368} 369 370SEC("raw_tp") 371__success 372int iter_array_fill(const void *ctx) 373{ 374 int sum, i; 375 376 MY_PID_GUARD(); 377 378 bpf_for(i, 0, ARRAY_SIZE(arr)) { 379 arr[i] = i * 2; 380 } 381 382 sum = 0; 383 bpf_for(i, 0, ARRAY_SIZE(arr)) { 384 sum += arr[i]; 385 } 386 387 bpf_printk("ITER_ARRAY_FILL: sum=%d (should be %d)\n", sum, 255 * 256); 388 389 return 0; 390} 391 392static int arr2d[4][5]; 393static int arr2d_row_sums[4]; 394static int arr2d_col_sums[5]; 395 396SEC("raw_tp") 397__success 398int iter_nested_iters(const void *ctx) 399{ 400 int sum, row, col; 401 402 MY_PID_GUARD(); 403 404 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 405 bpf_for( col, 0, ARRAY_SIZE(arr2d[0])) { 406 arr2d[row][col] = row * col; 407 } 408 } 409 410 /* zero-initialize sums */ 411 sum = 0; 412 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 413 arr2d_row_sums[row] = 0; 414 } 415 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 416 arr2d_col_sums[col] = 0; 417 } 418 419 /* calculate sums */ 420 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 421 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 422 sum += arr2d[row][col]; 423 arr2d_row_sums[row] += arr2d[row][col]; 424 arr2d_col_sums[col] += arr2d[row][col]; 425 } 426 } 427 428 bpf_printk("ITER_NESTED_ITERS: total sum=%d", sum); 429 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 430 bpf_printk("ITER_NESTED_ITERS: row #%d sum=%d", row, arr2d_row_sums[row]); 431 } 432 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 433 bpf_printk("ITER_NESTED_ITERS: col #%d sum=%d%s", 434 col, arr2d_col_sums[col], 435 col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : ""); 436 } 437 438 return 0; 439} 440 441SEC("raw_tp") 442__success 443int iter_nested_deeply_iters(const void *ctx) 444{ 445 int sum = 0; 446 447 MY_PID_GUARD(); 448 449 bpf_repeat(10) { 450 bpf_repeat(10) { 451 bpf_repeat(10) { 452 bpf_repeat(10) { 453 bpf_repeat(10) { 454 sum += 1; 455 } 456 } 457 } 458 } 459 /* validate that we can break from inside bpf_repeat() */ 460 break; 461 } 462 463 return sum; 464} 465 466static __noinline void fill_inner_dimension(int row) 467{ 468 int col; 469 470 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 471 arr2d[row][col] = row * col; 472 } 473} 474 475static __noinline int sum_inner_dimension(int row) 476{ 477 int sum = 0, col; 478 479 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 480 sum += arr2d[row][col]; 481 arr2d_row_sums[row] += arr2d[row][col]; 482 arr2d_col_sums[col] += arr2d[row][col]; 483 } 484 485 return sum; 486} 487 488SEC("raw_tp") 489__success 490int iter_subprog_iters(const void *ctx) 491{ 492 int sum, row, col; 493 494 MY_PID_GUARD(); 495 496 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 497 fill_inner_dimension(row); 498 } 499 500 /* zero-initialize sums */ 501 sum = 0; 502 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 503 arr2d_row_sums[row] = 0; 504 } 505 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 506 arr2d_col_sums[col] = 0; 507 } 508 509 /* calculate sums */ 510 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 511 sum += sum_inner_dimension(row); 512 } 513 514 bpf_printk("ITER_SUBPROG_ITERS: total sum=%d", sum); 515 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 516 bpf_printk("ITER_SUBPROG_ITERS: row #%d sum=%d", 517 row, arr2d_row_sums[row]); 518 } 519 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 520 bpf_printk("ITER_SUBPROG_ITERS: col #%d sum=%d%s", 521 col, arr2d_col_sums[col], 522 col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : ""); 523 } 524 525 return 0; 526} 527 528struct { 529 __uint(type, BPF_MAP_TYPE_ARRAY); 530 __type(key, int); 531 __type(value, int); 532 __uint(max_entries, 1000); 533} arr_map SEC(".maps"); 534 535SEC("?raw_tp") 536__failure __msg("invalid mem access 'scalar'") 537int iter_err_too_permissive1(const void *ctx) 538{ 539 int *map_val = NULL; 540 int key = 0; 541 542 MY_PID_GUARD(); 543 544 map_val = bpf_map_lookup_elem(&arr_map, &key); 545 if (!map_val) 546 return 0; 547 548 bpf_repeat(1000000) { 549 map_val = NULL; 550 } 551 552 *map_val = 123; 553 554 return 0; 555} 556 557SEC("?raw_tp") 558__failure __msg("invalid mem access 'map_value_or_null'") 559int iter_err_too_permissive2(const void *ctx) 560{ 561 int *map_val = NULL; 562 int key = 0; 563 564 MY_PID_GUARD(); 565 566 map_val = bpf_map_lookup_elem(&arr_map, &key); 567 if (!map_val) 568 return 0; 569 570 bpf_repeat(1000000) { 571 map_val = bpf_map_lookup_elem(&arr_map, &key); 572 } 573 574 *map_val = 123; 575 576 return 0; 577} 578 579SEC("?raw_tp") 580__failure __msg("invalid mem access 'map_value_or_null'") 581int iter_err_too_permissive3(const void *ctx) 582{ 583 int *map_val = NULL; 584 int key = 0; 585 bool found = false; 586 587 MY_PID_GUARD(); 588 589 bpf_repeat(1000000) { 590 map_val = bpf_map_lookup_elem(&arr_map, &key); 591 found = true; 592 } 593 594 if (found) 595 *map_val = 123; 596 597 return 0; 598} 599 600SEC("raw_tp") 601__success 602int iter_tricky_but_fine(const void *ctx) 603{ 604 int *map_val = NULL; 605 int key = 0; 606 bool found = false; 607 608 MY_PID_GUARD(); 609 610 bpf_repeat(1000000) { 611 map_val = bpf_map_lookup_elem(&arr_map, &key); 612 if (map_val) { 613 found = true; 614 break; 615 } 616 } 617 618 if (found) 619 *map_val = 123; 620 621 return 0; 622} 623 624#define __bpf_memzero(p, sz) bpf_probe_read_kernel((p), (sz), 0) 625 626SEC("raw_tp") 627__success 628int iter_stack_array_loop(const void *ctx) 629{ 630 long arr1[16], arr2[16], sum = 0; 631 int i; 632 633 MY_PID_GUARD(); 634 635 /* zero-init arr1 and arr2 in such a way that verifier doesn't know 636 * it's all zeros; if we don't do that, we'll make BPF verifier track 637 * all combination of zero/non-zero stack slots for arr1/arr2, which 638 * will lead to O(2^(ARRAY_SIZE(arr1)+ARRAY_SIZE(arr2))) different 639 * states 640 */ 641 __bpf_memzero(arr1, sizeof(arr1)); 642 __bpf_memzero(arr2, sizeof(arr1)); 643 644 /* validate that we can break and continue when using bpf_for() */ 645 bpf_for(i, 0, ARRAY_SIZE(arr1)) { 646 if (i & 1) { 647 arr1[i] = i; 648 continue; 649 } else { 650 arr2[i] = i; 651 break; 652 } 653 } 654 655 bpf_for(i, 0, ARRAY_SIZE(arr1)) { 656 sum += arr1[i] + arr2[i]; 657 } 658 659 return sum; 660} 661 662static __noinline void fill(struct bpf_iter_num *it, int *arr, __u32 n, int mul) 663{ 664 int *t, i; 665 666 while ((t = bpf_iter_num_next(it))) { 667 i = *t; 668 if (i >= n) 669 break; 670 arr[i] = i * mul; 671 } 672} 673 674static __noinline int sum(struct bpf_iter_num *it, int *arr, __u32 n) 675{ 676 int *t, i, sum = 0; 677 678 while ((t = bpf_iter_num_next(it))) { 679 i = *t; 680 if ((__u32)i >= n) 681 break; 682 sum += arr[i]; 683 } 684 685 return sum; 686} 687 688SEC("raw_tp") 689__success 690int iter_pass_iter_ptr_to_subprog(const void *ctx) 691{ 692 int arr1[16], arr2[32]; 693 struct bpf_iter_num it; 694 int n, sum1, sum2; 695 696 MY_PID_GUARD(); 697 698 /* fill arr1 */ 699 n = ARRAY_SIZE(arr1); 700 bpf_iter_num_new(&it, 0, n); 701 fill(&it, arr1, n, 2); 702 bpf_iter_num_destroy(&it); 703 704 /* fill arr2 */ 705 n = ARRAY_SIZE(arr2); 706 bpf_iter_num_new(&it, 0, n); 707 fill(&it, arr2, n, 10); 708 bpf_iter_num_destroy(&it); 709 710 /* sum arr1 */ 711 n = ARRAY_SIZE(arr1); 712 bpf_iter_num_new(&it, 0, n); 713 sum1 = sum(&it, arr1, n); 714 bpf_iter_num_destroy(&it); 715 716 /* sum arr2 */ 717 n = ARRAY_SIZE(arr2); 718 bpf_iter_num_new(&it, 0, n); 719 sum2 = sum(&it, arr2, n); 720 bpf_iter_num_destroy(&it); 721 722 bpf_printk("sum1=%d, sum2=%d", sum1, sum2); 723 724 return 0; 725} 726 727SEC("?raw_tp") 728__failure 729__msg("R1 type=scalar expected=fp") 730__naked int delayed_read_mark(void) 731{ 732 /* This is equivalent to C program below. 733 * The call to bpf_iter_num_next() is reachable with r7 values &fp[-16] and 0xdead. 734 * State with r7=&fp[-16] is visited first and follows r6 != 42 ... continue branch. 735 * At this point iterator next() call is reached with r7 that has no read mark. 736 * Loop body with r7=0xdead would only be visited if verifier would decide to continue 737 * with second loop iteration. Absence of read mark on r7 might affect state 738 * equivalent logic used for iterator convergence tracking. 739 * 740 * r7 = &fp[-16] 741 * fp[-16] = 0 742 * r6 = bpf_get_prandom_u32() 743 * bpf_iter_num_new(&fp[-8], 0, 10) 744 * while (bpf_iter_num_next(&fp[-8])) { 745 * r6++ 746 * if (r6 != 42) { 747 * r7 = 0xdead 748 * continue; 749 * } 750 * bpf_probe_read_user(r7, 8, 0xdeadbeef); // this is not safe 751 * } 752 * bpf_iter_num_destroy(&fp[-8]) 753 * return 0 754 */ 755 asm volatile ( 756 "r7 = r10;" 757 "r7 += -16;" 758 "r0 = 0;" 759 "*(u64 *)(r7 + 0) = r0;" 760 "call %[bpf_get_prandom_u32];" 761 "r6 = r0;" 762 "r1 = r10;" 763 "r1 += -8;" 764 "r2 = 0;" 765 "r3 = 10;" 766 "call %[bpf_iter_num_new];" 767 "1:" 768 "r1 = r10;" 769 "r1 += -8;" 770 "call %[bpf_iter_num_next];" 771 "if r0 == 0 goto 2f;" 772 "r6 += 1;" 773 "if r6 != 42 goto 3f;" 774 "r7 = 0xdead;" 775 "goto 1b;" 776 "3:" 777 "r1 = r7;" 778 "r2 = 8;" 779 "r3 = 0xdeadbeef;" 780 "call %[bpf_probe_read_user];" 781 "goto 1b;" 782 "2:" 783 "r1 = r10;" 784 "r1 += -8;" 785 "call %[bpf_iter_num_destroy];" 786 "r0 = 0;" 787 "exit;" 788 : 789 : __imm(bpf_get_prandom_u32), 790 __imm(bpf_iter_num_new), 791 __imm(bpf_iter_num_next), 792 __imm(bpf_iter_num_destroy), 793 __imm(bpf_probe_read_user) 794 : __clobber_all 795 ); 796} 797 798SEC("?raw_tp") 799__failure 800__msg("math between fp pointer and register with unbounded") 801__naked int delayed_precision_mark(void) 802{ 803 /* This is equivalent to C program below. 804 * The test is similar to delayed_iter_mark but verifies that incomplete 805 * precision don't fool verifier. 806 * The call to bpf_iter_num_next() is reachable with r7 values -16 and -32. 807 * State with r7=-16 is visited first and follows r6 != 42 ... continue branch. 808 * At this point iterator next() call is reached with r7 that has no read 809 * and precision marks. 810 * Loop body with r7=-32 would only be visited if verifier would decide to continue 811 * with second loop iteration. Absence of precision mark on r7 might affect state 812 * equivalent logic used for iterator convergence tracking. 813 * 814 * r8 = 0 815 * fp[-16] = 0 816 * r7 = -16 817 * r6 = bpf_get_prandom_u32() 818 * bpf_iter_num_new(&fp[-8], 0, 10) 819 * while (bpf_iter_num_next(&fp[-8])) { 820 * if (r6 != 42) { 821 * r7 = -32 822 * r6 = bpf_get_prandom_u32() 823 * continue; 824 * } 825 * r0 = r10 826 * r0 += r7 827 * r8 = *(u64 *)(r0 + 0) // this is not safe 828 * r6 = bpf_get_prandom_u32() 829 * } 830 * bpf_iter_num_destroy(&fp[-8]) 831 * return r8 832 */ 833 asm volatile ( 834 "r8 = 0;" 835 "*(u64 *)(r10 - 16) = r8;" 836 "r7 = -16;" 837 "call %[bpf_get_prandom_u32];" 838 "r6 = r0;" 839 "r1 = r10;" 840 "r1 += -8;" 841 "r2 = 0;" 842 "r3 = 10;" 843 "call %[bpf_iter_num_new];" 844 "1:" 845 "r1 = r10;" 846 "r1 += -8;\n" 847 "call %[bpf_iter_num_next];" 848 "if r0 == 0 goto 2f;" 849 "if r6 != 42 goto 3f;" 850 "r7 = -33;" 851 "call %[bpf_get_prandom_u32];" 852 "r6 = r0;" 853 "goto 1b;\n" 854 "3:" 855 "r0 = r10;" 856 "r0 += r7;" 857 "r8 = *(u64 *)(r0 + 0);" 858 "call %[bpf_get_prandom_u32];" 859 "r6 = r0;" 860 "goto 1b;\n" 861 "2:" 862 "r1 = r10;" 863 "r1 += -8;" 864 "call %[bpf_iter_num_destroy];" 865 "r0 = r8;" 866 "exit;" 867 : 868 : __imm(bpf_get_prandom_u32), 869 __imm(bpf_iter_num_new), 870 __imm(bpf_iter_num_next), 871 __imm(bpf_iter_num_destroy), 872 __imm(bpf_probe_read_user) 873 : __clobber_all 874 ); 875} 876 877SEC("?raw_tp") 878__failure 879__msg("math between fp pointer and register with unbounded") 880__flag(BPF_F_TEST_STATE_FREQ) 881__naked int loop_state_deps1(void) 882{ 883 /* This is equivalent to C program below. 884 * 885 * The case turns out to be tricky in a sense that: 886 * - states with c=-25 are explored only on a second iteration 887 * of the outer loop; 888 * - states with read+precise mark on c are explored only on 889 * second iteration of the inner loop and in a state which 890 * is pushed to states stack first. 891 * 892 * Depending on the details of iterator convergence logic 893 * verifier might stop states traversal too early and miss 894 * unsafe c=-25 memory access. 895 * 896 * j = iter_new(); // fp[-16] 897 * a = 0; // r6 898 * b = 0; // r7 899 * c = -24; // r8 900 * while (iter_next(j)) { 901 * i = iter_new(); // fp[-8] 902 * a = 0; // r6 903 * b = 0; // r7 904 * while (iter_next(i)) { 905 * if (a == 1) { 906 * a = 0; 907 * b = 1; 908 * } else if (a == 0) { 909 * a = 1; 910 * if (random() == 42) 911 * continue; 912 * if (b == 1) { 913 * *(r10 + c) = 7; // this is not safe 914 * iter_destroy(i); 915 * iter_destroy(j); 916 * return; 917 * } 918 * } 919 * } 920 * iter_destroy(i); 921 * a = 0; 922 * b = 0; 923 * c = -25; 924 * } 925 * iter_destroy(j); 926 * return; 927 */ 928 asm volatile ( 929 "r1 = r10;" 930 "r1 += -16;" 931 "r2 = 0;" 932 "r3 = 10;" 933 "call %[bpf_iter_num_new];" 934 "r6 = 0;" 935 "r7 = 0;" 936 "r8 = -24;" 937 "j_loop_%=:" 938 "r1 = r10;" 939 "r1 += -16;" 940 "call %[bpf_iter_num_next];" 941 "if r0 == 0 goto j_loop_end_%=;" 942 "r1 = r10;" 943 "r1 += -8;" 944 "r2 = 0;" 945 "r3 = 10;" 946 "call %[bpf_iter_num_new];" 947 "r6 = 0;" 948 "r7 = 0;" 949 "i_loop_%=:" 950 "r1 = r10;" 951 "r1 += -8;" 952 "call %[bpf_iter_num_next];" 953 "if r0 == 0 goto i_loop_end_%=;" 954 "check_one_r6_%=:" 955 "if r6 != 1 goto check_zero_r6_%=;" 956 "r6 = 0;" 957 "r7 = 1;" 958 "goto i_loop_%=;" 959 "check_zero_r6_%=:" 960 "if r6 != 0 goto i_loop_%=;" 961 "r6 = 1;" 962 "call %[bpf_get_prandom_u32];" 963 "if r0 != 42 goto check_one_r7_%=;" 964 "goto i_loop_%=;" 965 "check_one_r7_%=:" 966 "if r7 != 1 goto i_loop_%=;" 967 "r0 = r10;" 968 "r0 += r8;" 969 "r1 = 7;" 970 "*(u64 *)(r0 + 0) = r1;" 971 "r1 = r10;" 972 "r1 += -8;" 973 "call %[bpf_iter_num_destroy];" 974 "r1 = r10;" 975 "r1 += -16;" 976 "call %[bpf_iter_num_destroy];" 977 "r0 = 0;" 978 "exit;" 979 "i_loop_end_%=:" 980 "r1 = r10;" 981 "r1 += -8;" 982 "call %[bpf_iter_num_destroy];" 983 "r6 = 0;" 984 "r7 = 0;" 985 "r8 = -25;" 986 "goto j_loop_%=;" 987 "j_loop_end_%=:" 988 "r1 = r10;" 989 "r1 += -16;" 990 "call %[bpf_iter_num_destroy];" 991 "r0 = 0;" 992 "exit;" 993 : 994 : __imm(bpf_get_prandom_u32), 995 __imm(bpf_iter_num_new), 996 __imm(bpf_iter_num_next), 997 __imm(bpf_iter_num_destroy) 998 : __clobber_all 999 ); 1000} 1001 1002SEC("?raw_tp") 1003__failure 1004__msg("math between fp pointer and register with unbounded") 1005__flag(BPF_F_TEST_STATE_FREQ) 1006__naked int loop_state_deps2(void) 1007{ 1008 /* This is equivalent to C program below. 1009 * 1010 * The case turns out to be tricky in a sense that: 1011 * - states with read+precise mark on c are explored only on a second 1012 * iteration of the first inner loop and in a state which is pushed to 1013 * states stack first. 1014 * - states with c=-25 are explored only on a second iteration of the 1015 * second inner loop and in a state which is pushed to states stack 1016 * first. 1017 * 1018 * Depending on the details of iterator convergence logic 1019 * verifier might stop states traversal too early and miss 1020 * unsafe c=-25 memory access. 1021 * 1022 * j = iter_new(); // fp[-16] 1023 * a = 0; // r6 1024 * b = 0; // r7 1025 * c = -24; // r8 1026 * while (iter_next(j)) { 1027 * i = iter_new(); // fp[-8] 1028 * a = 0; // r6 1029 * b = 0; // r7 1030 * while (iter_next(i)) { 1031 * if (a == 1) { 1032 * a = 0; 1033 * b = 1; 1034 * } else if (a == 0) { 1035 * a = 1; 1036 * if (random() == 42) 1037 * continue; 1038 * if (b == 1) { 1039 * *(r10 + c) = 7; // this is not safe 1040 * iter_destroy(i); 1041 * iter_destroy(j); 1042 * return; 1043 * } 1044 * } 1045 * } 1046 * iter_destroy(i); 1047 * i = iter_new(); // fp[-8] 1048 * a = 0; // r6 1049 * b = 0; // r7 1050 * while (iter_next(i)) { 1051 * if (a == 1) { 1052 * a = 0; 1053 * b = 1; 1054 * } else if (a == 0) { 1055 * a = 1; 1056 * if (random() == 42) 1057 * continue; 1058 * if (b == 1) { 1059 * a = 0; 1060 * c = -25; 1061 * } 1062 * } 1063 * } 1064 * iter_destroy(i); 1065 * } 1066 * iter_destroy(j); 1067 * return; 1068 */ 1069 asm volatile ( 1070 "r1 = r10;" 1071 "r1 += -16;" 1072 "r2 = 0;" 1073 "r3 = 10;" 1074 "call %[bpf_iter_num_new];" 1075 "r6 = 0;" 1076 "r7 = 0;" 1077 "r8 = -24;" 1078 "j_loop_%=:" 1079 "r1 = r10;" 1080 "r1 += -16;" 1081 "call %[bpf_iter_num_next];" 1082 "if r0 == 0 goto j_loop_end_%=;" 1083 1084 /* first inner loop */ 1085 "r1 = r10;" 1086 "r1 += -8;" 1087 "r2 = 0;" 1088 "r3 = 10;" 1089 "call %[bpf_iter_num_new];" 1090 "r6 = 0;" 1091 "r7 = 0;" 1092 "i_loop_%=:" 1093 "r1 = r10;" 1094 "r1 += -8;" 1095 "call %[bpf_iter_num_next];" 1096 "if r0 == 0 goto i_loop_end_%=;" 1097 "check_one_r6_%=:" 1098 "if r6 != 1 goto check_zero_r6_%=;" 1099 "r6 = 0;" 1100 "r7 = 1;" 1101 "goto i_loop_%=;" 1102 "check_zero_r6_%=:" 1103 "if r6 != 0 goto i_loop_%=;" 1104 "r6 = 1;" 1105 "call %[bpf_get_prandom_u32];" 1106 "if r0 != 42 goto check_one_r7_%=;" 1107 "goto i_loop_%=;" 1108 "check_one_r7_%=:" 1109 "if r7 != 1 goto i_loop_%=;" 1110 "r0 = r10;" 1111 "r0 += r8;" 1112 "r1 = 7;" 1113 "*(u64 *)(r0 + 0) = r1;" 1114 "r1 = r10;" 1115 "r1 += -8;" 1116 "call %[bpf_iter_num_destroy];" 1117 "r1 = r10;" 1118 "r1 += -16;" 1119 "call %[bpf_iter_num_destroy];" 1120 "r0 = 0;" 1121 "exit;" 1122 "i_loop_end_%=:" 1123 "r1 = r10;" 1124 "r1 += -8;" 1125 "call %[bpf_iter_num_destroy];" 1126 1127 /* second inner loop */ 1128 "r1 = r10;" 1129 "r1 += -8;" 1130 "r2 = 0;" 1131 "r3 = 10;" 1132 "call %[bpf_iter_num_new];" 1133 "r6 = 0;" 1134 "r7 = 0;" 1135 "i2_loop_%=:" 1136 "r1 = r10;" 1137 "r1 += -8;" 1138 "call %[bpf_iter_num_next];" 1139 "if r0 == 0 goto i2_loop_end_%=;" 1140 "check2_one_r6_%=:" 1141 "if r6 != 1 goto check2_zero_r6_%=;" 1142 "r6 = 0;" 1143 "r7 = 1;" 1144 "goto i2_loop_%=;" 1145 "check2_zero_r6_%=:" 1146 "if r6 != 0 goto i2_loop_%=;" 1147 "r6 = 1;" 1148 "call %[bpf_get_prandom_u32];" 1149 "if r0 != 42 goto check2_one_r7_%=;" 1150 "goto i2_loop_%=;" 1151 "check2_one_r7_%=:" 1152 "if r7 != 1 goto i2_loop_%=;" 1153 "r6 = 0;" 1154 "r8 = -25;" 1155 "goto i2_loop_%=;" 1156 "i2_loop_end_%=:" 1157 "r1 = r10;" 1158 "r1 += -8;" 1159 "call %[bpf_iter_num_destroy];" 1160 1161 "r6 = 0;" 1162 "r7 = 0;" 1163 "goto j_loop_%=;" 1164 "j_loop_end_%=:" 1165 "r1 = r10;" 1166 "r1 += -16;" 1167 "call %[bpf_iter_num_destroy];" 1168 "r0 = 0;" 1169 "exit;" 1170 : 1171 : __imm(bpf_get_prandom_u32), 1172 __imm(bpf_iter_num_new), 1173 __imm(bpf_iter_num_next), 1174 __imm(bpf_iter_num_destroy) 1175 : __clobber_all 1176 ); 1177} 1178 1179SEC("?raw_tp") 1180__success 1181__naked int triple_continue(void) 1182{ 1183 /* This is equivalent to C program below. 1184 * High branching factor of the loop body turned out to be 1185 * problematic for one of the iterator convergence tracking 1186 * algorithms explored. 1187 * 1188 * r6 = bpf_get_prandom_u32() 1189 * bpf_iter_num_new(&fp[-8], 0, 10) 1190 * while (bpf_iter_num_next(&fp[-8])) { 1191 * if (bpf_get_prandom_u32() != 42) 1192 * continue; 1193 * if (bpf_get_prandom_u32() != 42) 1194 * continue; 1195 * if (bpf_get_prandom_u32() != 42) 1196 * continue; 1197 * r0 += 0; 1198 * } 1199 * bpf_iter_num_destroy(&fp[-8]) 1200 * return 0 1201 */ 1202 asm volatile ( 1203 "r1 = r10;" 1204 "r1 += -8;" 1205 "r2 = 0;" 1206 "r3 = 10;" 1207 "call %[bpf_iter_num_new];" 1208 "loop_%=:" 1209 "r1 = r10;" 1210 "r1 += -8;" 1211 "call %[bpf_iter_num_next];" 1212 "if r0 == 0 goto loop_end_%=;" 1213 "call %[bpf_get_prandom_u32];" 1214 "if r0 != 42 goto loop_%=;" 1215 "call %[bpf_get_prandom_u32];" 1216 "if r0 != 42 goto loop_%=;" 1217 "call %[bpf_get_prandom_u32];" 1218 "if r0 != 42 goto loop_%=;" 1219 "r0 += 0;" 1220 "goto loop_%=;" 1221 "loop_end_%=:" 1222 "r1 = r10;" 1223 "r1 += -8;" 1224 "call %[bpf_iter_num_destroy];" 1225 "r0 = 0;" 1226 "exit;" 1227 : 1228 : __imm(bpf_get_prandom_u32), 1229 __imm(bpf_iter_num_new), 1230 __imm(bpf_iter_num_next), 1231 __imm(bpf_iter_num_destroy) 1232 : __clobber_all 1233 ); 1234} 1235 1236SEC("?raw_tp") 1237__success 1238__naked int widen_spill(void) 1239{ 1240 /* This is equivalent to C program below. 1241 * The counter is stored in fp[-16], if this counter is not widened 1242 * verifier states representing loop iterations would never converge. 1243 * 1244 * fp[-16] = 0 1245 * bpf_iter_num_new(&fp[-8], 0, 10) 1246 * while (bpf_iter_num_next(&fp[-8])) { 1247 * r0 = fp[-16]; 1248 * r0 += 1; 1249 * fp[-16] = r0; 1250 * } 1251 * bpf_iter_num_destroy(&fp[-8]) 1252 * return 0 1253 */ 1254 asm volatile ( 1255 "r0 = 0;" 1256 "*(u64 *)(r10 - 16) = r0;" 1257 "r1 = r10;" 1258 "r1 += -8;" 1259 "r2 = 0;" 1260 "r3 = 10;" 1261 "call %[bpf_iter_num_new];" 1262 "loop_%=:" 1263 "r1 = r10;" 1264 "r1 += -8;" 1265 "call %[bpf_iter_num_next];" 1266 "if r0 == 0 goto loop_end_%=;" 1267 "r0 = *(u64 *)(r10 - 16);" 1268 "r0 += 1;" 1269 "*(u64 *)(r10 - 16) = r0;" 1270 "goto loop_%=;" 1271 "loop_end_%=:" 1272 "r1 = r10;" 1273 "r1 += -8;" 1274 "call %[bpf_iter_num_destroy];" 1275 "r0 = 0;" 1276 "exit;" 1277 : 1278 : __imm(bpf_iter_num_new), 1279 __imm(bpf_iter_num_next), 1280 __imm(bpf_iter_num_destroy) 1281 : __clobber_all 1282 ); 1283} 1284 1285SEC("raw_tp") 1286__success 1287__naked int checkpoint_states_deletion(void) 1288{ 1289 /* This is equivalent to C program below. 1290 * 1291 * int *a, *b, *c, *d, *e, *f; 1292 * int i, sum = 0; 1293 * bpf_for(i, 0, 10) { 1294 * a = bpf_map_lookup_elem(&amap, &i); 1295 * b = bpf_map_lookup_elem(&amap, &i); 1296 * c = bpf_map_lookup_elem(&amap, &i); 1297 * d = bpf_map_lookup_elem(&amap, &i); 1298 * e = bpf_map_lookup_elem(&amap, &i); 1299 * f = bpf_map_lookup_elem(&amap, &i); 1300 * if (a) sum += 1; 1301 * if (b) sum += 1; 1302 * if (c) sum += 1; 1303 * if (d) sum += 1; 1304 * if (e) sum += 1; 1305 * if (f) sum += 1; 1306 * } 1307 * return 0; 1308 * 1309 * The body of the loop spawns multiple simulation paths 1310 * with different combination of NULL/non-NULL information for a/b/c/d/e/f. 1311 * Each combination is unique from states_equal() point of view. 1312 * Explored states checkpoint is created after each iterator next call. 1313 * Iterator convergence logic expects that eventually current state 1314 * would get equal to one of the explored states and thus loop 1315 * exploration would be finished (at-least for a specific path). 1316 * Verifier evicts explored states with high miss to hit ratio 1317 * to to avoid comparing current state with too many explored 1318 * states per instruction. 1319 * This test is designed to "stress test" eviction policy defined using formula: 1320 * 1321 * sl->miss_cnt > sl->hit_cnt * N + N // if true sl->state is evicted 1322 * 1323 * Currently N is set to 64, which allows for 6 variables in this test. 1324 */ 1325 asm volatile ( 1326 "r6 = 0;" /* a */ 1327 "r7 = 0;" /* b */ 1328 "r8 = 0;" /* c */ 1329 "*(u64 *)(r10 - 24) = r6;" /* d */ 1330 "*(u64 *)(r10 - 32) = r6;" /* e */ 1331 "*(u64 *)(r10 - 40) = r6;" /* f */ 1332 "r9 = 0;" /* sum */ 1333 "r1 = r10;" 1334 "r1 += -8;" 1335 "r2 = 0;" 1336 "r3 = 10;" 1337 "call %[bpf_iter_num_new];" 1338 "loop_%=:" 1339 "r1 = r10;" 1340 "r1 += -8;" 1341 "call %[bpf_iter_num_next];" 1342 "if r0 == 0 goto loop_end_%=;" 1343 1344 "*(u64 *)(r10 - 16) = r0;" 1345 1346 "r1 = %[amap] ll;" 1347 "r2 = r10;" 1348 "r2 += -16;" 1349 "call %[bpf_map_lookup_elem];" 1350 "r6 = r0;" 1351 1352 "r1 = %[amap] ll;" 1353 "r2 = r10;" 1354 "r2 += -16;" 1355 "call %[bpf_map_lookup_elem];" 1356 "r7 = r0;" 1357 1358 "r1 = %[amap] ll;" 1359 "r2 = r10;" 1360 "r2 += -16;" 1361 "call %[bpf_map_lookup_elem];" 1362 "r8 = r0;" 1363 1364 "r1 = %[amap] ll;" 1365 "r2 = r10;" 1366 "r2 += -16;" 1367 "call %[bpf_map_lookup_elem];" 1368 "*(u64 *)(r10 - 24) = r0;" 1369 1370 "r1 = %[amap] ll;" 1371 "r2 = r10;" 1372 "r2 += -16;" 1373 "call %[bpf_map_lookup_elem];" 1374 "*(u64 *)(r10 - 32) = r0;" 1375 1376 "r1 = %[amap] ll;" 1377 "r2 = r10;" 1378 "r2 += -16;" 1379 "call %[bpf_map_lookup_elem];" 1380 "*(u64 *)(r10 - 40) = r0;" 1381 1382 "if r6 == 0 goto +1;" 1383 "r9 += 1;" 1384 "if r7 == 0 goto +1;" 1385 "r9 += 1;" 1386 "if r8 == 0 goto +1;" 1387 "r9 += 1;" 1388 "r0 = *(u64 *)(r10 - 24);" 1389 "if r0 == 0 goto +1;" 1390 "r9 += 1;" 1391 "r0 = *(u64 *)(r10 - 32);" 1392 "if r0 == 0 goto +1;" 1393 "r9 += 1;" 1394 "r0 = *(u64 *)(r10 - 40);" 1395 "if r0 == 0 goto +1;" 1396 "r9 += 1;" 1397 1398 "goto loop_%=;" 1399 "loop_end_%=:" 1400 "r1 = r10;" 1401 "r1 += -8;" 1402 "call %[bpf_iter_num_destroy];" 1403 "r0 = 0;" 1404 "exit;" 1405 : 1406 : __imm(bpf_map_lookup_elem), 1407 __imm(bpf_iter_num_new), 1408 __imm(bpf_iter_num_next), 1409 __imm(bpf_iter_num_destroy), 1410 __imm_addr(amap) 1411 : __clobber_all 1412 ); 1413} 1414 1415struct { 1416 int data[32]; 1417 int n; 1418} loop_data; 1419 1420SEC("raw_tp") 1421__success 1422int iter_arr_with_actual_elem_count(const void *ctx) 1423{ 1424 int i, n = loop_data.n, sum = 0; 1425 1426 if (n > ARRAY_SIZE(loop_data.data)) 1427 return 0; 1428 1429 bpf_for(i, 0, n) { 1430 /* no rechecking of i against ARRAY_SIZE(loop_data.n) */ 1431 sum += loop_data.data[i]; 1432 } 1433 1434 return sum; 1435} 1436 1437char _license[] SEC("license") = "GPL"; 1438