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