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 static volatile int zero = 0; 11 12 int my_pid; 13 int arr[256]; 14 int small_arr[16] SEC(".data.small_arr"); 15 16 struct { 17 __uint(type, BPF_MAP_TYPE_HASH); 18 __uint(max_entries, 10); 19 __type(key, int); 20 __type(value, int); 21 } amap SEC(".maps"); 22 23 #ifdef REAL_TEST 24 #define MY_PID_GUARD() if (my_pid != (bpf_get_current_pid_tgid() >> 32)) return 0 25 #else 26 #define MY_PID_GUARD() ({ }) 27 #endif 28 29 SEC("?raw_tp") 30 __failure __msg("math between map_value pointer and register with unbounded min value is not allowed") 31 int iter_err_unsafe_c_loop(const void *ctx) 32 { 33 struct bpf_iter_num it; 34 int *v, i = zero; /* obscure initial value of i */ 35 36 MY_PID_GUARD(); 37 38 bpf_iter_num_new(&it, 0, 1000); 39 while ((v = bpf_iter_num_next(&it))) { 40 i++; 41 } 42 bpf_iter_num_destroy(&it); 43 44 small_arr[i] = 123; /* invalid */ 45 46 return 0; 47 } 48 49 SEC("?raw_tp") 50 __failure __msg("unbounded memory access") 51 int iter_err_unsafe_asm_loop(const void *ctx) 52 { 53 struct bpf_iter_num it; 54 55 MY_PID_GUARD(); 56 57 asm volatile ( 58 "r6 = %[zero];" /* iteration counter */ 59 "r1 = %[it];" /* iterator state */ 60 "r2 = 0;" 61 "r3 = 1000;" 62 "r4 = 1;" 63 "call %[bpf_iter_num_new];" 64 "loop:" 65 "r1 = %[it];" 66 "call %[bpf_iter_num_next];" 67 "if r0 == 0 goto out;" 68 "r6 += 1;" 69 "goto loop;" 70 "out:" 71 "r1 = %[it];" 72 "call %[bpf_iter_num_destroy];" 73 "r1 = %[small_arr];" 74 "r2 = r6;" 75 "r2 <<= 2;" 76 "r1 += r2;" 77 "*(u32 *)(r1 + 0) = r6;" /* invalid */ 78 : 79 : [it]"r"(&it), 80 [small_arr]"r"(small_arr), 81 [zero]"r"(zero), 82 __imm(bpf_iter_num_new), 83 __imm(bpf_iter_num_next), 84 __imm(bpf_iter_num_destroy) 85 : __clobber_common, "r6" 86 ); 87 88 return 0; 89 } 90 91 /* 92 * Naked function, so there is no compiler-generated glue and the whole inlined program can be 93 * matched. Pinned to arches whose JITs zero-extend 32-bit writes implicitly 94 * (bpf_jit_needs_zext() == false); on arches that need explicit zero-extension the verifier 95 * interleaves "wN = wN" insns and the fixed shape below would not match. The inlining itself is 96 * arch independent, so checking it on these arches is sufficient. 97 * 98 * bpf_iter_num_new() emits the full range check (distance computation and both the -EINVAL and 99 * -E2BIG error paths); bpf_iter_num_next() and bpf_iter_num_destroy() are inlined too. 100 */ 101 SEC("raw_tp") 102 __arch_x86_64 103 __arch_arm64 104 __success 105 __xlated("r6 = r10") 106 __xlated("r6 += -8") 107 __xlated("call unknown") 108 __xlated("r3 = r0") 109 __xlated("r3 &= 65535") 110 __xlated("r1 = r6") 111 __xlated("r2 = 0") 112 /* bpf_iter_num_new(&it, 0, <non-const>) with the range check kept */ 113 __xlated("if w2 s> w3 goto pc+8") 114 __xlated("w0 = w3") 115 __xlated("w0 -= w2") 116 __xlated("if r0 > 0x800000 goto pc+8") 117 __xlated("w2 += -1") 118 __xlated("*(u32 *)(r1 +0) = r2") 119 __xlated("*(u32 *)(r1 +4) = r3") 120 __xlated("r0 = 0") 121 __xlated("goto pc+5") 122 __xlated("*(u64 *)(r1 +0) = 0") 123 __xlated("r0 = -22") 124 __xlated("goto pc+2") 125 __xlated("*(u64 *)(r1 +0) = 0") 126 __xlated("r0 = -7") 127 __xlated("r1 = r6") 128 /* bpf_iter_num_next(&it) */ 129 __xlated("r0 = *(u32 *)(r1 +0)") 130 __xlated("w0 += 1") 131 __xlated("r2 = *(u32 *)(r1 +4)") 132 __xlated("if w0 s>= w2 goto pc+3") 133 __xlated("*(u32 *)(r1 +0) = r0") 134 __xlated("r0 = r1") 135 __xlated("goto pc+2") 136 __xlated("*(u64 *)(r1 +0) = 0") 137 __xlated("r0 = 0") 138 __xlated("if r0 != 0x0 goto pc-11") 139 __xlated("r1 = r6") 140 /* bpf_iter_num_destroy(&it) is inlined to a nop */ 141 __xlated("goto pc+0") 142 __xlated("r0 = 0") 143 __xlated("exit") 144 int __naked iter_num_new_inlined(void) 145 { 146 asm volatile ( 147 /* r6 points to struct bpf_iter_num on the stack */ 148 "r6 = r10;" 149 "r6 += -8;" 150 /* non-constant end so the range checks are kept */ 151 "call %[bpf_get_prandom_u32];" 152 "r3 = r0;" 153 "r3 &= 0xffff;" 154 "r1 = r6;" 155 "r2 = 0;" 156 "call %[bpf_iter_num_new];" 157 "1:" 158 "r1 = r6;" 159 "call %[bpf_iter_num_next];" 160 "if r0 != 0 goto 1b;" 161 "r1 = r6;" 162 "call %[bpf_iter_num_destroy];" 163 "r0 = 0;" 164 "exit;" 165 : 166 : __imm(bpf_get_prandom_u32), 167 __imm(bpf_iter_num_new), 168 __imm(bpf_iter_num_next), 169 __imm(bpf_iter_num_destroy) 170 : __clobber_common, "r6" 171 ); 172 } 173 174 SEC("raw_tp") 175 __success 176 int iter_while_loop(const void *ctx) 177 { 178 struct bpf_iter_num it; 179 int *v; 180 181 MY_PID_GUARD(); 182 183 bpf_iter_num_new(&it, 0, 3); 184 while ((v = bpf_iter_num_next(&it))) { 185 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v); 186 } 187 bpf_iter_num_destroy(&it); 188 189 return 0; 190 } 191 192 SEC("raw_tp") 193 __success 194 int iter_while_loop_auto_cleanup(const void *ctx) 195 { 196 __attribute__((cleanup(bpf_iter_num_destroy))) struct bpf_iter_num it; 197 int *v; 198 199 MY_PID_GUARD(); 200 201 bpf_iter_num_new(&it, 0, 3); 202 while ((v = bpf_iter_num_next(&it))) { 203 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v); 204 } 205 /* (!) no explicit bpf_iter_num_destroy() */ 206 207 return 0; 208 } 209 210 SEC("raw_tp") 211 __success 212 int iter_for_loop(const void *ctx) 213 { 214 struct bpf_iter_num it; 215 int *v; 216 217 MY_PID_GUARD(); 218 219 bpf_iter_num_new(&it, 5, 10); 220 for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) { 221 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v); 222 } 223 bpf_iter_num_destroy(&it); 224 225 return 0; 226 } 227 228 SEC("raw_tp") 229 __success 230 int iter_bpf_for_each_macro(const void *ctx) 231 { 232 int *v; 233 234 MY_PID_GUARD(); 235 236 bpf_for_each(num, v, 5, 10) { 237 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v); 238 } 239 240 return 0; 241 } 242 243 SEC("raw_tp") 244 __success 245 int iter_bpf_for_macro(const void *ctx) 246 { 247 int i; 248 249 MY_PID_GUARD(); 250 251 bpf_for(i, 5, 10) { 252 bpf_printk("ITER_BASIC: E2 VAL: v=%d", i); 253 } 254 255 return 0; 256 } 257 258 SEC("raw_tp") 259 __success 260 int iter_pragma_unroll_loop(const void *ctx) 261 { 262 struct bpf_iter_num it; 263 int *v, i; 264 265 MY_PID_GUARD(); 266 267 bpf_iter_num_new(&it, 0, 2); 268 __pragma_loop_no_unroll 269 for (i = 0; i < 3; i++) { 270 v = bpf_iter_num_next(&it); 271 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1); 272 } 273 bpf_iter_num_destroy(&it); 274 275 return 0; 276 } 277 278 SEC("raw_tp") 279 __success 280 int iter_manual_unroll_loop(const void *ctx) 281 { 282 struct bpf_iter_num it; 283 int *v; 284 285 MY_PID_GUARD(); 286 287 bpf_iter_num_new(&it, 100, 200); 288 v = bpf_iter_num_next(&it); 289 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 290 v = bpf_iter_num_next(&it); 291 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 292 v = bpf_iter_num_next(&it); 293 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 294 v = bpf_iter_num_next(&it); 295 bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1); 296 bpf_iter_num_destroy(&it); 297 298 return 0; 299 } 300 301 SEC("raw_tp") 302 __success 303 int iter_multiple_sequential_loops(const void *ctx) 304 { 305 struct bpf_iter_num it; 306 int *v, i; 307 308 MY_PID_GUARD(); 309 310 bpf_iter_num_new(&it, 0, 3); 311 while ((v = bpf_iter_num_next(&it))) { 312 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v); 313 } 314 bpf_iter_num_destroy(&it); 315 316 bpf_iter_num_new(&it, 5, 10); 317 for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) { 318 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v); 319 } 320 bpf_iter_num_destroy(&it); 321 322 bpf_iter_num_new(&it, 0, 2); 323 __pragma_loop_no_unroll 324 for (i = 0; i < 3; i++) { 325 v = bpf_iter_num_next(&it); 326 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1); 327 } 328 bpf_iter_num_destroy(&it); 329 330 bpf_iter_num_new(&it, 100, 200); 331 v = bpf_iter_num_next(&it); 332 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 333 v = bpf_iter_num_next(&it); 334 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 335 v = bpf_iter_num_next(&it); 336 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1); 337 v = bpf_iter_num_next(&it); 338 bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1); 339 bpf_iter_num_destroy(&it); 340 341 return 0; 342 } 343 344 SEC("raw_tp") 345 __success 346 int iter_limit_cond_break_loop(const void *ctx) 347 { 348 struct bpf_iter_num it; 349 int *v, i = 0, sum = 0; 350 351 MY_PID_GUARD(); 352 353 bpf_iter_num_new(&it, 0, 10); 354 while ((v = bpf_iter_num_next(&it))) { 355 bpf_printk("ITER_SIMPLE: i=%d v=%d", i, *v); 356 sum += *v; 357 358 i++; 359 if (i > 3) 360 break; 361 } 362 bpf_iter_num_destroy(&it); 363 364 bpf_printk("ITER_SIMPLE: sum=%d\n", sum); 365 366 return 0; 367 } 368 369 SEC("raw_tp") 370 __success 371 int iter_obfuscate_counter(const void *ctx) 372 { 373 struct bpf_iter_num it; 374 int *v, sum = 0; 375 /* Make i's initial value unknowable for verifier to prevent it from 376 * pruning if/else branch inside the loop body and marking i as precise. 377 */ 378 int i = zero; 379 380 MY_PID_GUARD(); 381 382 bpf_iter_num_new(&it, 0, 10); 383 while ((v = bpf_iter_num_next(&it))) { 384 int x; 385 386 i += 1; 387 388 /* If we initialized i as `int i = 0;` above, verifier would 389 * track that i becomes 1 on first iteration after increment 390 * above, and here verifier would eagerly prune else branch 391 * and mark i as precise, ruining open-coded iterator logic 392 * completely, as each next iteration would have a different 393 * *precise* value of i, and thus there would be no 394 * convergence of state. This would result in reaching maximum 395 * instruction limit, no matter what the limit is. 396 */ 397 if (i == 1) 398 x = 123; 399 else 400 x = i * 3 + 1; 401 402 bpf_printk("ITER_OBFUSCATE_COUNTER: i=%d v=%d x=%d", i, *v, x); 403 404 sum += x; 405 } 406 bpf_iter_num_destroy(&it); 407 408 bpf_printk("ITER_OBFUSCATE_COUNTER: sum=%d\n", sum); 409 410 return 0; 411 } 412 413 SEC("raw_tp") 414 __success 415 int iter_search_loop(const void *ctx) 416 { 417 struct bpf_iter_num it; 418 int *v, *elem = NULL; 419 bool found = false; 420 421 MY_PID_GUARD(); 422 423 bpf_iter_num_new(&it, 0, 10); 424 425 while ((v = bpf_iter_num_next(&it))) { 426 bpf_printk("ITER_SEARCH_LOOP: v=%d", *v); 427 428 if (*v == 2) { 429 found = true; 430 elem = v; 431 barrier_var(elem); 432 } 433 } 434 435 /* should fail to verify if bpf_iter_num_destroy() is here */ 436 437 if (found) 438 /* here found element will be wrong, we should have copied 439 * value to a variable, but here we want to make sure we can 440 * access memory after the loop anyways 441 */ 442 bpf_printk("ITER_SEARCH_LOOP: FOUND IT = %d!\n", *elem); 443 else 444 bpf_printk("ITER_SEARCH_LOOP: NOT FOUND IT!\n"); 445 446 bpf_iter_num_destroy(&it); 447 448 return 0; 449 } 450 451 SEC("raw_tp") 452 __success 453 int iter_array_fill(const void *ctx) 454 { 455 int sum, i; 456 457 MY_PID_GUARD(); 458 459 bpf_for(i, 0, ARRAY_SIZE(arr)) { 460 arr[i] = i * 2; 461 } 462 463 sum = 0; 464 bpf_for(i, 0, ARRAY_SIZE(arr)) { 465 sum += arr[i]; 466 } 467 468 bpf_printk("ITER_ARRAY_FILL: sum=%d (should be %d)\n", sum, 255 * 256); 469 470 return 0; 471 } 472 473 static int arr2d[4][5]; 474 static int arr2d_row_sums[4]; 475 static int arr2d_col_sums[5]; 476 477 SEC("raw_tp") 478 __success 479 int iter_nested_iters(const void *ctx) 480 { 481 int sum, row, col; 482 483 MY_PID_GUARD(); 484 485 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 486 bpf_for( col, 0, ARRAY_SIZE(arr2d[0])) { 487 arr2d[row][col] = row * col; 488 } 489 } 490 491 /* zero-initialize sums */ 492 sum = 0; 493 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 494 arr2d_row_sums[row] = 0; 495 } 496 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 497 arr2d_col_sums[col] = 0; 498 } 499 500 /* calculate sums */ 501 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 502 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 503 sum += arr2d[row][col]; 504 arr2d_row_sums[row] += arr2d[row][col]; 505 arr2d_col_sums[col] += arr2d[row][col]; 506 } 507 } 508 509 bpf_printk("ITER_NESTED_ITERS: total sum=%d", sum); 510 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 511 bpf_printk("ITER_NESTED_ITERS: row #%d sum=%d", row, arr2d_row_sums[row]); 512 } 513 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 514 bpf_printk("ITER_NESTED_ITERS: col #%d sum=%d%s", 515 col, arr2d_col_sums[col], 516 col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : ""); 517 } 518 519 return 0; 520 } 521 522 SEC("raw_tp") 523 __success 524 int iter_nested_deeply_iters(const void *ctx) 525 { 526 int sum = 0; 527 528 MY_PID_GUARD(); 529 530 bpf_repeat(10) { 531 bpf_repeat(10) { 532 bpf_repeat(10) { 533 bpf_repeat(10) { 534 bpf_repeat(10) { 535 sum += 1; 536 } 537 } 538 } 539 } 540 /* validate that we can break from inside bpf_repeat() */ 541 break; 542 } 543 544 return sum; 545 } 546 547 static __noinline void fill_inner_dimension(int row) 548 { 549 int col; 550 551 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 552 arr2d[row][col] = row * col; 553 } 554 } 555 556 static __noinline int sum_inner_dimension(int row) 557 { 558 int sum = 0, col; 559 560 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 561 sum += arr2d[row][col]; 562 arr2d_row_sums[row] += arr2d[row][col]; 563 arr2d_col_sums[col] += arr2d[row][col]; 564 } 565 566 return sum; 567 } 568 569 SEC("raw_tp") 570 __success 571 int iter_subprog_iters(const void *ctx) 572 { 573 int sum, row, col; 574 575 MY_PID_GUARD(); 576 577 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 578 fill_inner_dimension(row); 579 } 580 581 /* zero-initialize sums */ 582 sum = 0; 583 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 584 arr2d_row_sums[row] = 0; 585 } 586 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 587 arr2d_col_sums[col] = 0; 588 } 589 590 /* calculate sums */ 591 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 592 sum += sum_inner_dimension(row); 593 } 594 595 bpf_printk("ITER_SUBPROG_ITERS: total sum=%d", sum); 596 bpf_for(row, 0, ARRAY_SIZE(arr2d)) { 597 bpf_printk("ITER_SUBPROG_ITERS: row #%d sum=%d", 598 row, arr2d_row_sums[row]); 599 } 600 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) { 601 bpf_printk("ITER_SUBPROG_ITERS: col #%d sum=%d%s", 602 col, arr2d_col_sums[col], 603 col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : ""); 604 } 605 606 return 0; 607 } 608 609 struct { 610 __uint(type, BPF_MAP_TYPE_HASH); 611 __type(key, int); 612 __type(value, int); 613 __uint(max_entries, 1000); 614 } hash_map SEC(".maps"); 615 616 SEC("?raw_tp") 617 __failure __msg("invalid mem access 'scalar'") 618 int iter_err_too_permissive1(const void *ctx) 619 { 620 int *map_val = NULL; 621 int key = 0; 622 623 MY_PID_GUARD(); 624 625 map_val = bpf_map_lookup_elem(&hash_map, &key); 626 if (!map_val) 627 return 0; 628 629 bpf_repeat(1000000) { 630 map_val = NULL; 631 } 632 633 *map_val = 123; 634 635 return 0; 636 } 637 638 SEC("?raw_tp") 639 __failure __msg("invalid mem access 'map_value_or_null'") 640 int iter_err_too_permissive2(const void *ctx) 641 { 642 int *map_val = NULL; 643 int key = 0; 644 645 MY_PID_GUARD(); 646 647 map_val = bpf_map_lookup_elem(&hash_map, &key); 648 if (!map_val) 649 return 0; 650 651 bpf_repeat(1000000) { 652 map_val = bpf_map_lookup_elem(&hash_map, &key); 653 } 654 655 *map_val = 123; 656 657 return 0; 658 } 659 660 SEC("?raw_tp") 661 __failure __msg("invalid mem access 'map_value_or_null'") 662 int iter_err_too_permissive3(const void *ctx) 663 { 664 int *map_val = NULL; 665 int key = 0; 666 bool found = false; 667 668 MY_PID_GUARD(); 669 670 bpf_repeat(1000000) { 671 map_val = bpf_map_lookup_elem(&hash_map, &key); 672 found = true; 673 } 674 675 if (found) 676 *map_val = 123; 677 678 return 0; 679 } 680 681 SEC("raw_tp") 682 __success 683 int iter_tricky_but_fine(const void *ctx) 684 { 685 int *map_val = NULL; 686 int key = 0; 687 bool found = false; 688 689 MY_PID_GUARD(); 690 691 bpf_repeat(1000000) { 692 map_val = bpf_map_lookup_elem(&hash_map, &key); 693 if (map_val) { 694 found = true; 695 break; 696 } 697 } 698 699 if (found) 700 *map_val = 123; 701 702 return 0; 703 } 704 705 #define __bpf_memzero(p, sz) bpf_probe_read_kernel((p), (sz), 0) 706 707 SEC("raw_tp") 708 __success 709 int iter_stack_array_loop(const void *ctx) 710 { 711 long arr1[16], arr2[16], sum = 0; 712 int i; 713 714 MY_PID_GUARD(); 715 716 /* zero-init arr1 and arr2 in such a way that verifier doesn't know 717 * it's all zeros; if we don't do that, we'll make BPF verifier track 718 * all combination of zero/non-zero stack slots for arr1/arr2, which 719 * will lead to O(2^(ARRAY_SIZE(arr1)+ARRAY_SIZE(arr2))) different 720 * states 721 */ 722 __bpf_memzero(arr1, sizeof(arr1)); 723 __bpf_memzero(arr2, sizeof(arr1)); 724 725 /* validate that we can break and continue when using bpf_for() */ 726 bpf_for(i, 0, ARRAY_SIZE(arr1)) { 727 if (i & 1) { 728 arr1[i] = i; 729 continue; 730 } else { 731 arr2[i] = i; 732 break; 733 } 734 } 735 736 bpf_for(i, 0, ARRAY_SIZE(arr1)) { 737 sum += arr1[i] + arr2[i]; 738 } 739 740 return sum; 741 } 742 743 static __noinline void fill(struct bpf_iter_num *it, int *arr, __u32 n, int mul) 744 { 745 int *t, i; 746 747 while ((t = bpf_iter_num_next(it))) { 748 i = *t; 749 if (i >= n) 750 break; 751 arr[i] = i * mul; 752 } 753 } 754 755 static __noinline int sum(struct bpf_iter_num *it, int *arr, __u32 n) 756 { 757 int *t, i, sum = 0; 758 759 while ((t = bpf_iter_num_next(it))) { 760 i = *t; 761 if ((__u32)i >= n) 762 break; 763 sum += arr[i]; 764 } 765 766 return sum; 767 } 768 769 SEC("raw_tp") 770 __success 771 int iter_pass_iter_ptr_to_subprog(const void *ctx) 772 { 773 int arr1[16], arr2[32]; 774 struct bpf_iter_num it; 775 int n, sum1, sum2; 776 777 MY_PID_GUARD(); 778 779 /* fill arr1 */ 780 n = ARRAY_SIZE(arr1); 781 bpf_iter_num_new(&it, 0, n); 782 fill(&it, arr1, n, 2); 783 bpf_iter_num_destroy(&it); 784 785 /* fill arr2 */ 786 n = ARRAY_SIZE(arr2); 787 bpf_iter_num_new(&it, 0, n); 788 fill(&it, arr2, n, 10); 789 bpf_iter_num_destroy(&it); 790 791 /* sum arr1 */ 792 n = ARRAY_SIZE(arr1); 793 bpf_iter_num_new(&it, 0, n); 794 sum1 = sum(&it, arr1, n); 795 bpf_iter_num_destroy(&it); 796 797 /* sum arr2 */ 798 n = ARRAY_SIZE(arr2); 799 bpf_iter_num_new(&it, 0, n); 800 sum2 = sum(&it, arr2, n); 801 bpf_iter_num_destroy(&it); 802 803 bpf_printk("sum1=%d, sum2=%d", sum1, sum2); 804 805 return 0; 806 } 807 808 SEC("?raw_tp") 809 __failure 810 __msg("R1 type=scalar expected=fp") 811 __naked int delayed_read_mark(void) 812 { 813 /* This is equivalent to C program below. 814 * The call to bpf_iter_num_next() is reachable with r7 values &fp[-16] and 0xdead. 815 * State with r7=&fp[-16] is visited first and follows r6 != 42 ... continue branch. 816 * At this point iterator next() call is reached with r7 that has no read mark. 817 * Loop body with r7=0xdead would only be visited if verifier would decide to continue 818 * with second loop iteration. Absence of read mark on r7 might affect state 819 * equivalent logic used for iterator convergence tracking. 820 * 821 * r7 = &fp[-16] 822 * fp[-16] = 0 823 * r6 = bpf_get_prandom_u32() 824 * bpf_iter_num_new(&fp[-8], 0, 10) 825 * while (bpf_iter_num_next(&fp[-8])) { 826 * r6++ 827 * if (r6 != 42) { 828 * r7 = 0xdead 829 * continue; 830 * } 831 * bpf_probe_read_user(r7, 8, 0xdeadbeef); // this is not safe 832 * } 833 * bpf_iter_num_destroy(&fp[-8]) 834 * return 0 835 */ 836 asm volatile ( 837 "r7 = r10;" 838 "r7 += -16;" 839 "r0 = 0;" 840 "*(u64 *)(r7 + 0) = r0;" 841 "call %[bpf_get_prandom_u32];" 842 "r6 = r0;" 843 "r1 = r10;" 844 "r1 += -8;" 845 "r2 = 0;" 846 "r3 = 10;" 847 "call %[bpf_iter_num_new];" 848 "1:" 849 "r1 = r10;" 850 "r1 += -8;" 851 "call %[bpf_iter_num_next];" 852 "if r0 == 0 goto 2f;" 853 "r6 += 1;" 854 "if r6 != 42 goto 3f;" 855 "r7 = 0xdead;" 856 "goto 1b;" 857 "3:" 858 "r1 = r7;" 859 "r2 = 8;" 860 "r3 = 0xdeadbeef;" 861 "call %[bpf_probe_read_user];" 862 "goto 1b;" 863 "2:" 864 "r1 = r10;" 865 "r1 += -8;" 866 "call %[bpf_iter_num_destroy];" 867 "r0 = 0;" 868 "exit;" 869 : 870 : __imm(bpf_get_prandom_u32), 871 __imm(bpf_iter_num_new), 872 __imm(bpf_iter_num_next), 873 __imm(bpf_iter_num_destroy), 874 __imm(bpf_probe_read_user) 875 : __clobber_all 876 ); 877 } 878 879 SEC("?raw_tp") 880 __failure 881 __msg("math between fp pointer and register with unbounded") 882 __naked int delayed_precision_mark(void) 883 { 884 /* This is equivalent to C program below. 885 * The test is similar to delayed_iter_mark but verifies that incomplete 886 * precision don't fool verifier. 887 * The call to bpf_iter_num_next() is reachable with r7 values -16 and -32. 888 * State with r7=-16 is visited first and follows r6 != 42 ... continue branch. 889 * At this point iterator next() call is reached with r7 that has no read 890 * and precision marks. 891 * Loop body with r7=-32 would only be visited if verifier would decide to continue 892 * with second loop iteration. Absence of precision mark on r7 might affect state 893 * equivalent logic used for iterator convergence tracking. 894 * 895 * r8 = 0 896 * fp[-16] = 0 897 * r7 = -16 898 * r6 = bpf_get_prandom_u32() 899 * bpf_iter_num_new(&fp[-8], 0, 10) 900 * while (bpf_iter_num_next(&fp[-8])) { 901 * if (r6 != 42) { 902 * r7 = -32 903 * r6 = bpf_get_prandom_u32() 904 * continue; 905 * } 906 * r0 = r10 907 * r0 += r7 908 * r8 = *(u64 *)(r0 + 0) // this is not safe 909 * r6 = bpf_get_prandom_u32() 910 * } 911 * bpf_iter_num_destroy(&fp[-8]) 912 * return r8 913 */ 914 asm volatile ( 915 "r8 = 0;" 916 "*(u64 *)(r10 - 16) = r8;" 917 "r7 = -16;" 918 "call %[bpf_get_prandom_u32];" 919 "r6 = r0;" 920 "r1 = r10;" 921 "r1 += -8;" 922 "r2 = 0;" 923 "r3 = 10;" 924 "call %[bpf_iter_num_new];" 925 "1:" 926 "r1 = r10;" 927 "r1 += -8;\n" 928 "call %[bpf_iter_num_next];" 929 "if r0 == 0 goto 2f;" 930 "if r6 != 42 goto 3f;" 931 "r7 = -33;" 932 "call %[bpf_get_prandom_u32];" 933 "r6 = r0;" 934 "goto 1b;\n" 935 "3:" 936 "r0 = r10;" 937 "r0 += r7;" 938 "r8 = *(u64 *)(r0 + 0);" 939 "call %[bpf_get_prandom_u32];" 940 "r6 = r0;" 941 "goto 1b;\n" 942 "2:" 943 "r1 = r10;" 944 "r1 += -8;" 945 "call %[bpf_iter_num_destroy];" 946 "r0 = r8;" 947 "exit;" 948 : 949 : __imm(bpf_get_prandom_u32), 950 __imm(bpf_iter_num_new), 951 __imm(bpf_iter_num_next), 952 __imm(bpf_iter_num_destroy), 953 __imm(bpf_probe_read_user) 954 : __clobber_all 955 ); 956 } 957 958 SEC("?raw_tp") 959 __failure 960 __msg("math between fp pointer and register with unbounded") 961 __flag(BPF_F_TEST_STATE_FREQ) 962 __naked int loop_state_deps1(void) 963 { 964 /* This is equivalent to C program below. 965 * 966 * The case turns out to be tricky in a sense that: 967 * - states with c=-25 are explored only on a second iteration 968 * of the outer loop; 969 * - states with read+precise mark on c are explored only on 970 * second iteration of the inner loop and in a state which 971 * is pushed to states stack first. 972 * 973 * Depending on the details of iterator convergence logic 974 * verifier might stop states traversal too early and miss 975 * unsafe c=-25 memory access. 976 * 977 * j = iter_new(); // fp[-16] 978 * a = 0; // r6 979 * b = 0; // r7 980 * c = -24; // r8 981 * while (iter_next(j)) { 982 * i = iter_new(); // fp[-8] 983 * a = 0; // r6 984 * b = 0; // r7 985 * while (iter_next(i)) { 986 * if (a == 1) { 987 * a = 0; 988 * b = 1; 989 * } else if (a == 0) { 990 * a = 1; 991 * if (random() == 42) 992 * continue; 993 * if (b == 1) { 994 * *(r10 + c) = 7; // this is not safe 995 * iter_destroy(i); 996 * iter_destroy(j); 997 * return; 998 * } 999 * } 1000 * } 1001 * iter_destroy(i); 1002 * a = 0; 1003 * b = 0; 1004 * c = -25; 1005 * } 1006 * iter_destroy(j); 1007 * return; 1008 */ 1009 asm volatile ( 1010 "r1 = r10;" 1011 "r1 += -16;" 1012 "r2 = 0;" 1013 "r3 = 10;" 1014 "call %[bpf_iter_num_new];" 1015 "r6 = 0;" 1016 "r7 = 0;" 1017 "r8 = -24;" 1018 "j_loop_%=:" 1019 "r1 = r10;" 1020 "r1 += -16;" 1021 "call %[bpf_iter_num_next];" 1022 "if r0 == 0 goto j_loop_end_%=;" 1023 "r1 = r10;" 1024 "r1 += -8;" 1025 "r2 = 0;" 1026 "r3 = 10;" 1027 "call %[bpf_iter_num_new];" 1028 "r6 = 0;" 1029 "r7 = 0;" 1030 "i_loop_%=:" 1031 "r1 = r10;" 1032 "r1 += -8;" 1033 "call %[bpf_iter_num_next];" 1034 "if r0 == 0 goto i_loop_end_%=;" 1035 "check_one_r6_%=:" 1036 "if r6 != 1 goto check_zero_r6_%=;" 1037 "r6 = 0;" 1038 "r7 = 1;" 1039 "goto i_loop_%=;" 1040 "check_zero_r6_%=:" 1041 "if r6 != 0 goto i_loop_%=;" 1042 "r6 = 1;" 1043 "call %[bpf_get_prandom_u32];" 1044 "if r0 != 42 goto check_one_r7_%=;" 1045 "goto i_loop_%=;" 1046 "check_one_r7_%=:" 1047 "if r7 != 1 goto i_loop_%=;" 1048 "r0 = r10;" 1049 "r0 += r8;" 1050 "r1 = 7;" 1051 "*(u64 *)(r0 + 0) = r1;" 1052 "r1 = r10;" 1053 "r1 += -8;" 1054 "call %[bpf_iter_num_destroy];" 1055 "r1 = r10;" 1056 "r1 += -16;" 1057 "call %[bpf_iter_num_destroy];" 1058 "r0 = 0;" 1059 "exit;" 1060 "i_loop_end_%=:" 1061 "r1 = r10;" 1062 "r1 += -8;" 1063 "call %[bpf_iter_num_destroy];" 1064 "r6 = 0;" 1065 "r7 = 0;" 1066 "r8 = -25;" 1067 "goto j_loop_%=;" 1068 "j_loop_end_%=:" 1069 "r1 = r10;" 1070 "r1 += -16;" 1071 "call %[bpf_iter_num_destroy];" 1072 "r0 = 0;" 1073 "exit;" 1074 : 1075 : __imm(bpf_get_prandom_u32), 1076 __imm(bpf_iter_num_new), 1077 __imm(bpf_iter_num_next), 1078 __imm(bpf_iter_num_destroy) 1079 : __clobber_all 1080 ); 1081 } 1082 1083 SEC("?raw_tp") 1084 __failure 1085 __msg("math between fp pointer and register with unbounded") 1086 __flag(BPF_F_TEST_STATE_FREQ) 1087 __naked int loop_state_deps2(void) 1088 { 1089 /* This is equivalent to C program below. 1090 * 1091 * The case turns out to be tricky in a sense that: 1092 * - states with read+precise mark on c are explored only on a second 1093 * iteration of the first inner loop and in a state which is pushed to 1094 * states stack first. 1095 * - states with c=-25 are explored only on a second iteration of the 1096 * second inner loop and in a state which is pushed to states stack 1097 * first. 1098 * 1099 * Depending on the details of iterator convergence logic 1100 * verifier might stop states traversal too early and miss 1101 * unsafe c=-25 memory access. 1102 * 1103 * j = iter_new(); // fp[-16] 1104 * a = 0; // r6 1105 * b = 0; // r7 1106 * c = -24; // r8 1107 * while (iter_next(j)) { 1108 * i = iter_new(); // fp[-8] 1109 * a = 0; // r6 1110 * b = 0; // r7 1111 * while (iter_next(i)) { 1112 * if (a == 1) { 1113 * a = 0; 1114 * b = 1; 1115 * } else if (a == 0) { 1116 * a = 1; 1117 * if (random() == 42) 1118 * continue; 1119 * if (b == 1) { 1120 * *(r10 + c) = 7; // this is not safe 1121 * iter_destroy(i); 1122 * iter_destroy(j); 1123 * return; 1124 * } 1125 * } 1126 * } 1127 * iter_destroy(i); 1128 * i = iter_new(); // fp[-8] 1129 * a = 0; // r6 1130 * b = 0; // r7 1131 * while (iter_next(i)) { 1132 * if (a == 1) { 1133 * a = 0; 1134 * b = 1; 1135 * } else if (a == 0) { 1136 * a = 1; 1137 * if (random() == 42) 1138 * continue; 1139 * if (b == 1) { 1140 * a = 0; 1141 * c = -25; 1142 * } 1143 * } 1144 * } 1145 * iter_destroy(i); 1146 * } 1147 * iter_destroy(j); 1148 * return; 1149 */ 1150 asm volatile ( 1151 "r1 = r10;" 1152 "r1 += -16;" 1153 "r2 = 0;" 1154 "r3 = 10;" 1155 "call %[bpf_iter_num_new];" 1156 "r6 = 0;" 1157 "r7 = 0;" 1158 "r8 = -24;" 1159 "j_loop_%=:" 1160 "r1 = r10;" 1161 "r1 += -16;" 1162 "call %[bpf_iter_num_next];" 1163 "if r0 == 0 goto j_loop_end_%=;" 1164 1165 /* first inner loop */ 1166 "r1 = r10;" 1167 "r1 += -8;" 1168 "r2 = 0;" 1169 "r3 = 10;" 1170 "call %[bpf_iter_num_new];" 1171 "r6 = 0;" 1172 "r7 = 0;" 1173 "i_loop_%=:" 1174 "r1 = r10;" 1175 "r1 += -8;" 1176 "call %[bpf_iter_num_next];" 1177 "if r0 == 0 goto i_loop_end_%=;" 1178 "check_one_r6_%=:" 1179 "if r6 != 1 goto check_zero_r6_%=;" 1180 "r6 = 0;" 1181 "r7 = 1;" 1182 "goto i_loop_%=;" 1183 "check_zero_r6_%=:" 1184 "if r6 != 0 goto i_loop_%=;" 1185 "r6 = 1;" 1186 "call %[bpf_get_prandom_u32];" 1187 "if r0 != 42 goto check_one_r7_%=;" 1188 "goto i_loop_%=;" 1189 "check_one_r7_%=:" 1190 "if r7 != 1 goto i_loop_%=;" 1191 "r0 = r10;" 1192 "r0 += r8;" 1193 "r1 = 7;" 1194 "*(u64 *)(r0 + 0) = r1;" 1195 "r1 = r10;" 1196 "r1 += -8;" 1197 "call %[bpf_iter_num_destroy];" 1198 "r1 = r10;" 1199 "r1 += -16;" 1200 "call %[bpf_iter_num_destroy];" 1201 "r0 = 0;" 1202 "exit;" 1203 "i_loop_end_%=:" 1204 "r1 = r10;" 1205 "r1 += -8;" 1206 "call %[bpf_iter_num_destroy];" 1207 1208 /* second inner loop */ 1209 "r1 = r10;" 1210 "r1 += -8;" 1211 "r2 = 0;" 1212 "r3 = 10;" 1213 "call %[bpf_iter_num_new];" 1214 "r6 = 0;" 1215 "r7 = 0;" 1216 "i2_loop_%=:" 1217 "r1 = r10;" 1218 "r1 += -8;" 1219 "call %[bpf_iter_num_next];" 1220 "if r0 == 0 goto i2_loop_end_%=;" 1221 "check2_one_r6_%=:" 1222 "if r6 != 1 goto check2_zero_r6_%=;" 1223 "r6 = 0;" 1224 "r7 = 1;" 1225 "goto i2_loop_%=;" 1226 "check2_zero_r6_%=:" 1227 "if r6 != 0 goto i2_loop_%=;" 1228 "r6 = 1;" 1229 "call %[bpf_get_prandom_u32];" 1230 "if r0 != 42 goto check2_one_r7_%=;" 1231 "goto i2_loop_%=;" 1232 "check2_one_r7_%=:" 1233 "if r7 != 1 goto i2_loop_%=;" 1234 "r6 = 0;" 1235 "r8 = -25;" 1236 "goto i2_loop_%=;" 1237 "i2_loop_end_%=:" 1238 "r1 = r10;" 1239 "r1 += -8;" 1240 "call %[bpf_iter_num_destroy];" 1241 1242 "r6 = 0;" 1243 "r7 = 0;" 1244 "goto j_loop_%=;" 1245 "j_loop_end_%=:" 1246 "r1 = r10;" 1247 "r1 += -16;" 1248 "call %[bpf_iter_num_destroy];" 1249 "r0 = 0;" 1250 "exit;" 1251 : 1252 : __imm(bpf_get_prandom_u32), 1253 __imm(bpf_iter_num_new), 1254 __imm(bpf_iter_num_next), 1255 __imm(bpf_iter_num_destroy) 1256 : __clobber_all 1257 ); 1258 } 1259 1260 SEC("?raw_tp") 1261 __failure 1262 __msg("math between fp pointer and register with unbounded") 1263 __flag(BPF_F_TEST_STATE_FREQ) 1264 __naked int loop_state_deps3(void) 1265 { 1266 /* This is equivalent to a C program below. 1267 * 1268 * if (random() != 24) { // assume false branch is placed first 1269 * i = iter_new(); // fp[-8] 1270 * while (iter_next(i)); 1271 * iter_destroy(i); 1272 * return; 1273 * } 1274 * 1275 * for (i = 10; i > 0; i--); // increase dfs_depth for child states 1276 * 1277 * i = iter_new(); // fp[-8] 1278 * b = -24; // r8 1279 * for (;;) { // checkpoint (L) 1280 * if (iter_next(i)) // checkpoint (N) 1281 * break; 1282 * if (random() == 77) { // assume false branch is placed first 1283 * *(u64 *)(r10 + b) = 7; // this is not safe when b == -25 1284 * iter_destroy(i); 1285 * return; 1286 * } 1287 * if (random() == 42) { // assume false branch is placed first 1288 * b = -25; 1289 * } 1290 * } 1291 * iter_destroy(i); 1292 * 1293 * In case of a buggy verifier first loop might poison 1294 * env->cur_state->loop_entry with a state having 0 branches 1295 * and small dfs_depth. This would trigger NOT_EXACT states 1296 * comparison for some states within second loop. 1297 * Specifically, checkpoint (L) might be problematic if: 1298 * - branch with '*(u64 *)(r10 + b) = 7' is not explored yet; 1299 * - checkpoint (L) is first reached in state {b=-24}; 1300 * - traversal is pruned at checkpoint (N) setting checkpoint's (L) 1301 * branch count to 0, thus making it eligible for use in pruning; 1302 * - checkpoint (L) is next reached in state {b=-25}, 1303 * this would cause NOT_EXACT comparison with a state {b=-24} 1304 * while 'b' is not marked precise yet. 1305 */ 1306 asm volatile ( 1307 "call %[bpf_get_prandom_u32];" 1308 "if r0 == 24 goto 2f;" 1309 "r1 = r10;" 1310 "r1 += -8;" 1311 "r2 = 0;" 1312 "r3 = 5;" 1313 "call %[bpf_iter_num_new];" 1314 "1:" 1315 "r1 = r10;" 1316 "r1 += -8;" 1317 "call %[bpf_iter_num_next];" 1318 "if r0 != 0 goto 1b;" 1319 "r1 = r10;" 1320 "r1 += -8;" 1321 "call %[bpf_iter_num_destroy];" 1322 "r0 = 0;" 1323 "exit;" 1324 "2:" 1325 /* loop to increase dfs_depth */ 1326 "r0 = 10;" 1327 "3:" 1328 "r0 -= 1;" 1329 "if r0 != 0 goto 3b;" 1330 /* end of loop */ 1331 "r1 = r10;" 1332 "r1 += -8;" 1333 "r2 = 0;" 1334 "r3 = 10;" 1335 "call %[bpf_iter_num_new];" 1336 "r8 = -24;" 1337 "main_loop_%=:" 1338 "r1 = r10;" 1339 "r1 += -8;" 1340 "call %[bpf_iter_num_next];" 1341 "if r0 == 0 goto main_loop_end_%=;" 1342 /* first if */ 1343 "call %[bpf_get_prandom_u32];" 1344 "if r0 == 77 goto unsafe_write_%=;" 1345 /* second if */ 1346 "call %[bpf_get_prandom_u32];" 1347 "if r0 == 42 goto poison_r8_%=;" 1348 /* iterate */ 1349 "goto main_loop_%=;" 1350 "main_loop_end_%=:" 1351 "r1 = r10;" 1352 "r1 += -8;" 1353 "call %[bpf_iter_num_destroy];" 1354 "r0 = 0;" 1355 "exit;" 1356 1357 "unsafe_write_%=:" 1358 "r0 = r10;" 1359 "r0 += r8;" 1360 "r1 = 7;" 1361 "*(u64 *)(r0 + 0) = r1;" 1362 "goto main_loop_end_%=;" 1363 1364 "poison_r8_%=:" 1365 "r8 = -25;" 1366 "goto main_loop_%=;" 1367 : 1368 : __imm(bpf_get_prandom_u32), 1369 __imm(bpf_iter_num_new), 1370 __imm(bpf_iter_num_next), 1371 __imm(bpf_iter_num_destroy) 1372 : __clobber_all 1373 ); 1374 } 1375 1376 SEC("?raw_tp") 1377 __success 1378 __naked int triple_continue(void) 1379 { 1380 /* This is equivalent to C program below. 1381 * High branching factor of the loop body turned out to be 1382 * problematic for one of the iterator convergence tracking 1383 * algorithms explored. 1384 * 1385 * r6 = bpf_get_prandom_u32() 1386 * bpf_iter_num_new(&fp[-8], 0, 10) 1387 * while (bpf_iter_num_next(&fp[-8])) { 1388 * if (bpf_get_prandom_u32() != 42) 1389 * continue; 1390 * if (bpf_get_prandom_u32() != 42) 1391 * continue; 1392 * if (bpf_get_prandom_u32() != 42) 1393 * continue; 1394 * r0 += 0; 1395 * } 1396 * bpf_iter_num_destroy(&fp[-8]) 1397 * return 0 1398 */ 1399 asm volatile ( 1400 "r1 = r10;" 1401 "r1 += -8;" 1402 "r2 = 0;" 1403 "r3 = 10;" 1404 "call %[bpf_iter_num_new];" 1405 "loop_%=:" 1406 "r1 = r10;" 1407 "r1 += -8;" 1408 "call %[bpf_iter_num_next];" 1409 "if r0 == 0 goto loop_end_%=;" 1410 "call %[bpf_get_prandom_u32];" 1411 "if r0 != 42 goto loop_%=;" 1412 "call %[bpf_get_prandom_u32];" 1413 "if r0 != 42 goto loop_%=;" 1414 "call %[bpf_get_prandom_u32];" 1415 "if r0 != 42 goto loop_%=;" 1416 "r0 += 0;" 1417 "goto loop_%=;" 1418 "loop_end_%=:" 1419 "r1 = r10;" 1420 "r1 += -8;" 1421 "call %[bpf_iter_num_destroy];" 1422 "r0 = 0;" 1423 "exit;" 1424 : 1425 : __imm(bpf_get_prandom_u32), 1426 __imm(bpf_iter_num_new), 1427 __imm(bpf_iter_num_next), 1428 __imm(bpf_iter_num_destroy) 1429 : __clobber_all 1430 ); 1431 } 1432 1433 SEC("?raw_tp") 1434 __success 1435 __naked int widen_spill(void) 1436 { 1437 /* This is equivalent to C program below. 1438 * The counter is stored in fp[-16], if this counter is not widened 1439 * verifier states representing loop iterations would never converge. 1440 * 1441 * fp[-16] = 0 1442 * bpf_iter_num_new(&fp[-8], 0, 10) 1443 * while (bpf_iter_num_next(&fp[-8])) { 1444 * r0 = fp[-16]; 1445 * r0 += 1; 1446 * fp[-16] = r0; 1447 * } 1448 * bpf_iter_num_destroy(&fp[-8]) 1449 * return 0 1450 */ 1451 asm volatile ( 1452 "r0 = 0;" 1453 "*(u64 *)(r10 - 16) = r0;" 1454 "r1 = r10;" 1455 "r1 += -8;" 1456 "r2 = 0;" 1457 "r3 = 10;" 1458 "call %[bpf_iter_num_new];" 1459 "loop_%=:" 1460 "r1 = r10;" 1461 "r1 += -8;" 1462 "call %[bpf_iter_num_next];" 1463 "if r0 == 0 goto loop_end_%=;" 1464 "r0 = *(u64 *)(r10 - 16);" 1465 "r0 += 1;" 1466 "*(u64 *)(r10 - 16) = r0;" 1467 "goto loop_%=;" 1468 "loop_end_%=:" 1469 "r1 = r10;" 1470 "r1 += -8;" 1471 "call %[bpf_iter_num_destroy];" 1472 "r0 = 0;" 1473 "exit;" 1474 : 1475 : __imm(bpf_iter_num_new), 1476 __imm(bpf_iter_num_next), 1477 __imm(bpf_iter_num_destroy) 1478 : __clobber_all 1479 ); 1480 } 1481 1482 SEC("raw_tp") 1483 __success 1484 __naked int checkpoint_states_deletion(void) 1485 { 1486 /* This is equivalent to C program below. 1487 * 1488 * int *a, *b, *c, *d, *e, *f; 1489 * int i, sum = 0; 1490 * bpf_for(i, 0, 10) { 1491 * a = bpf_map_lookup_elem(&amap, &i); 1492 * b = bpf_map_lookup_elem(&amap, &i); 1493 * c = bpf_map_lookup_elem(&amap, &i); 1494 * d = bpf_map_lookup_elem(&amap, &i); 1495 * e = bpf_map_lookup_elem(&amap, &i); 1496 * f = bpf_map_lookup_elem(&amap, &i); 1497 * if (a) sum += 1; 1498 * if (b) sum += 1; 1499 * if (c) sum += 1; 1500 * if (d) sum += 1; 1501 * if (e) sum += 1; 1502 * if (f) sum += 1; 1503 * } 1504 * return 0; 1505 * 1506 * The body of the loop spawns multiple simulation paths 1507 * with different combination of NULL/non-NULL information for a/b/c/d/e/f. 1508 * Each combination is unique from states_equal() point of view. 1509 * Explored states checkpoint is created after each iterator next call. 1510 * Iterator convergence logic expects that eventually current state 1511 * would get equal to one of the explored states and thus loop 1512 * exploration would be finished (at-least for a specific path). 1513 * Verifier evicts explored states with high miss to hit ratio 1514 * to to avoid comparing current state with too many explored 1515 * states per instruction. 1516 * This test is designed to "stress test" eviction policy defined using formula: 1517 * 1518 * sl->miss_cnt > sl->hit_cnt * N + N // if true sl->state is evicted 1519 * 1520 * Currently N is set to 64, which allows for 6 variables in this test. 1521 */ 1522 asm volatile ( 1523 "r6 = 0;" /* a */ 1524 "r7 = 0;" /* b */ 1525 "r8 = 0;" /* c */ 1526 "*(u64 *)(r10 - 24) = r6;" /* d */ 1527 "*(u64 *)(r10 - 32) = r6;" /* e */ 1528 "*(u64 *)(r10 - 40) = r6;" /* f */ 1529 "r9 = 0;" /* sum */ 1530 "r1 = r10;" 1531 "r1 += -8;" 1532 "r2 = 0;" 1533 "r3 = 10;" 1534 "call %[bpf_iter_num_new];" 1535 "loop_%=:" 1536 "r1 = r10;" 1537 "r1 += -8;" 1538 "call %[bpf_iter_num_next];" 1539 "if r0 == 0 goto loop_end_%=;" 1540 1541 "*(u64 *)(r10 - 16) = r0;" 1542 1543 "r1 = %[amap] ll;" 1544 "r2 = r10;" 1545 "r2 += -16;" 1546 "call %[bpf_map_lookup_elem];" 1547 "r6 = r0;" 1548 1549 "r1 = %[amap] ll;" 1550 "r2 = r10;" 1551 "r2 += -16;" 1552 "call %[bpf_map_lookup_elem];" 1553 "r7 = r0;" 1554 1555 "r1 = %[amap] ll;" 1556 "r2 = r10;" 1557 "r2 += -16;" 1558 "call %[bpf_map_lookup_elem];" 1559 "r8 = r0;" 1560 1561 "r1 = %[amap] ll;" 1562 "r2 = r10;" 1563 "r2 += -16;" 1564 "call %[bpf_map_lookup_elem];" 1565 "*(u64 *)(r10 - 24) = r0;" 1566 1567 "r1 = %[amap] ll;" 1568 "r2 = r10;" 1569 "r2 += -16;" 1570 "call %[bpf_map_lookup_elem];" 1571 "*(u64 *)(r10 - 32) = r0;" 1572 1573 "r1 = %[amap] ll;" 1574 "r2 = r10;" 1575 "r2 += -16;" 1576 "call %[bpf_map_lookup_elem];" 1577 "*(u64 *)(r10 - 40) = r0;" 1578 1579 "if r6 == 0 goto +1;" 1580 "r9 += 1;" 1581 "if r7 == 0 goto +1;" 1582 "r9 += 1;" 1583 "if r8 == 0 goto +1;" 1584 "r9 += 1;" 1585 "r0 = *(u64 *)(r10 - 24);" 1586 "if r0 == 0 goto +1;" 1587 "r9 += 1;" 1588 "r0 = *(u64 *)(r10 - 32);" 1589 "if r0 == 0 goto +1;" 1590 "r9 += 1;" 1591 "r0 = *(u64 *)(r10 - 40);" 1592 "if r0 == 0 goto +1;" 1593 "r9 += 1;" 1594 1595 "goto loop_%=;" 1596 "loop_end_%=:" 1597 "r1 = r10;" 1598 "r1 += -8;" 1599 "call %[bpf_iter_num_destroy];" 1600 "r0 = 0;" 1601 "exit;" 1602 : 1603 : __imm(bpf_map_lookup_elem), 1604 __imm(bpf_iter_num_new), 1605 __imm(bpf_iter_num_next), 1606 __imm(bpf_iter_num_destroy), 1607 __imm_addr(amap) 1608 : __clobber_all 1609 ); 1610 } 1611 1612 struct { 1613 int data[32]; 1614 int n; 1615 } loop_data; 1616 1617 SEC("raw_tp") 1618 __success 1619 int iter_arr_with_actual_elem_count(const void *ctx) 1620 { 1621 int i, n = loop_data.n, sum = 0; 1622 1623 if (n > ARRAY_SIZE(loop_data.data)) 1624 return 0; 1625 1626 bpf_for(i, 0, n) { 1627 /* no rechecking of i against ARRAY_SIZE(loop_data.n) */ 1628 sum += loop_data.data[i]; 1629 } 1630 1631 return sum; 1632 } 1633 1634 __u32 upper, select_n, result; 1635 __u64 global; 1636 1637 static __noinline bool nest_2(char *str) 1638 { 1639 /* some insns (including branch insns) to ensure stacksafe() is triggered 1640 * in nest_2(). This way, stacksafe() can compare frame associated with nest_1(). 1641 */ 1642 if (str[0] == 't') 1643 return true; 1644 if (str[1] == 'e') 1645 return true; 1646 if (str[2] == 's') 1647 return true; 1648 if (str[3] == 't') 1649 return true; 1650 return false; 1651 } 1652 1653 static __noinline bool nest_1(int n) 1654 { 1655 /* case 0: allocate stack, case 1: no allocate stack */ 1656 switch (n) { 1657 case 0: { 1658 char comm[16]; 1659 1660 if (bpf_get_current_comm(comm, 16)) 1661 return false; 1662 return nest_2(comm); 1663 } 1664 case 1: 1665 return nest_2((char *)&global); 1666 default: 1667 return false; 1668 } 1669 } 1670 1671 SEC("raw_tp") 1672 __success 1673 int iter_subprog_check_stacksafe(const void *ctx) 1674 { 1675 long i; 1676 1677 bpf_for(i, 0, upper) { 1678 if (!nest_1(select_n)) { 1679 result = 1; 1680 return 0; 1681 } 1682 } 1683 1684 result = 2; 1685 return 0; 1686 } 1687 1688 struct bpf_iter_num global_it; 1689 1690 SEC("raw_tp") 1691 __failure __msg("R1 type=map_value expected=fp") 1692 int iter_new_bad_arg(const void *ctx) 1693 { 1694 bpf_iter_num_new(&global_it, 0, 1); 1695 return 0; 1696 } 1697 1698 SEC("raw_tp") 1699 __failure __msg("R1 type=map_value expected=fp") 1700 int iter_next_bad_arg(const void *ctx) 1701 { 1702 bpf_iter_num_next(&global_it); 1703 return 0; 1704 } 1705 1706 SEC("raw_tp") 1707 __failure __msg("R1 type=map_value expected=fp") 1708 int iter_destroy_bad_arg(const void *ctx) 1709 { 1710 bpf_iter_num_destroy(&global_it); 1711 return 0; 1712 } 1713 1714 SEC("raw_tp") 1715 __success 1716 int clean_live_states(const void *ctx) 1717 { 1718 char buf[1]; 1719 int i, j, k, l, m, n, o; 1720 1721 bpf_for(i, 0, 10) 1722 bpf_for(j, 0, 10) 1723 bpf_for(k, 0, 10) 1724 bpf_for(l, 0, 10) 1725 bpf_for(m, 0, 10) 1726 bpf_for(n, 0, 10) 1727 bpf_for(o, 0, 10) { 1728 if (unlikely(bpf_get_prandom_u32())) 1729 buf[0] = 42; 1730 bpf_printk("%s", buf); 1731 } 1732 return 0; 1733 } 1734 1735 SEC("?raw_tp") 1736 __flag(BPF_F_TEST_STATE_FREQ) 1737 __failure __msg("misaligned stack access off -31+0 size 8") 1738 __naked int absent_mark_in_the_middle_state(void) 1739 { 1740 /* This is equivalent to C program below. 1741 * 1742 * r8 = bpf_get_prandom_u32(); 1743 * r6 = -32; 1744 * bpf_iter_num_new(&fp[-8], 0, 10); 1745 * if (unlikely(bpf_get_prandom_u32())) 1746 * r6 = -31; 1747 * while (bpf_iter_num_next(&fp[-8])) { 1748 * if (unlikely(bpf_get_prandom_u32())) 1749 * *(fp + r6) = 7; 1750 * } 1751 * bpf_iter_num_destroy(&fp[-8]) 1752 * return 0 1753 */ 1754 asm volatile ( 1755 "call %[bpf_get_prandom_u32];" 1756 "r8 = r0;" 1757 "r7 = 0;" 1758 "r6 = -32;" 1759 "r0 = 0;" 1760 "*(u64 *)(r10 - 16) = r0;" 1761 "r1 = r10;" 1762 "r1 += -8;" 1763 "r2 = 0;" 1764 "r3 = 10;" 1765 "call %[bpf_iter_num_new];" 1766 "call %[bpf_get_prandom_u32];" 1767 "if r0 == r8 goto change_r6_%=;" 1768 "loop_%=:" 1769 "call noop;" 1770 "r1 = r10;" 1771 "r1 += -8;" 1772 "call %[bpf_iter_num_next];" 1773 "if r0 == 0 goto loop_end_%=;" 1774 "call %[bpf_get_prandom_u32];" 1775 "if r0 == r8 goto use_r6_%=;" 1776 "goto loop_%=;" 1777 "loop_end_%=:" 1778 "r1 = r10;" 1779 "r1 += -8;" 1780 "call %[bpf_iter_num_destroy];" 1781 "r0 = 0;" 1782 "exit;" 1783 "use_r6_%=:" 1784 "r0 = r10;" 1785 "r0 += r6;" 1786 "r1 = 7;" 1787 "*(u64 *)(r0 + 0) = r1;" 1788 "goto loop_%=;" 1789 "change_r6_%=:" 1790 "r6 = -31;" 1791 "goto loop_%=;" 1792 : 1793 : __imm(bpf_iter_num_new), 1794 __imm(bpf_iter_num_next), 1795 __imm(bpf_iter_num_destroy), 1796 __imm(bpf_get_prandom_u32) 1797 : __clobber_all 1798 ); 1799 } 1800 1801 __used __naked 1802 static int noop(void) 1803 { 1804 asm volatile ( 1805 "r0 = 0;" 1806 "exit;" 1807 ); 1808 } 1809 1810 SEC("?raw_tp") 1811 __flag(BPF_F_TEST_STATE_FREQ) 1812 __failure __msg("misaligned stack access off -31+0 size 8") 1813 __naked int absent_mark_in_the_middle_state2(void) 1814 { 1815 /* This is equivalent to C program below. 1816 * 1817 * r8 = bpf_get_prandom_u32(); 1818 * r6 = -32; 1819 * bpf_iter_num_new(&fp[-8], 0, 10); 1820 * if (unlikely(bpf_get_prandom_u32())) { 1821 * r6 = -31; 1822 * jump_into_loop: 1823 * goto +0; 1824 * goto loop; 1825 * } 1826 * if (unlikely(bpf_get_prandom_u32())) 1827 * goto jump_into_loop; 1828 * loop: 1829 * while (bpf_iter_num_next(&fp[-8])) { 1830 * if (unlikely(bpf_get_prandom_u32())) 1831 * *(fp + r6) = 7; 1832 * } 1833 * bpf_iter_num_destroy(&fp[-8]) 1834 * return 0 1835 */ 1836 asm volatile ( 1837 "call %[bpf_get_prandom_u32];" 1838 "r8 = r0;" 1839 "r7 = 0;" 1840 "r6 = -32;" 1841 "r0 = 0;" 1842 "*(u64 *)(r10 - 16) = r0;" 1843 "r1 = r10;" 1844 "r1 += -8;" 1845 "r2 = 0;" 1846 "r3 = 10;" 1847 "call %[bpf_iter_num_new];" 1848 "call %[bpf_get_prandom_u32];" 1849 "if r0 == r8 goto change_r6_%=;" 1850 "call %[bpf_get_prandom_u32];" 1851 "if r0 == r8 goto jump_into_loop_%=;" 1852 "loop_%=:" 1853 "r1 = r10;" 1854 "r1 += -8;" 1855 "call %[bpf_iter_num_next];" 1856 "if r0 == 0 goto loop_end_%=;" 1857 "call %[bpf_get_prandom_u32];" 1858 "if r0 == r8 goto use_r6_%=;" 1859 "goto loop_%=;" 1860 "loop_end_%=:" 1861 "r1 = r10;" 1862 "r1 += -8;" 1863 "call %[bpf_iter_num_destroy];" 1864 "r0 = 0;" 1865 "exit;" 1866 "use_r6_%=:" 1867 "r0 = r10;" 1868 "r0 += r6;" 1869 "r1 = 7;" 1870 "*(u64 *)(r0 + 0) = r1;" 1871 "goto loop_%=;" 1872 "change_r6_%=:" 1873 "r6 = -31;" 1874 "jump_into_loop_%=: " 1875 "goto +0;" 1876 "goto loop_%=;" 1877 : 1878 : __imm(bpf_iter_num_new), 1879 __imm(bpf_iter_num_next), 1880 __imm(bpf_iter_num_destroy), 1881 __imm(bpf_get_prandom_u32) 1882 : __clobber_all 1883 ); 1884 } 1885 1886 SEC("?raw_tp") 1887 __flag(BPF_F_TEST_STATE_FREQ) 1888 __failure __msg("misaligned stack access off -31+0 size 8") 1889 __naked int absent_mark_in_the_middle_state3(void) 1890 { 1891 /* 1892 * bpf_iter_num_new(&fp[-8], 0, 10) 1893 * loop1(-32, &fp[-8]) 1894 * loop1_wrapper(&fp[-8]) 1895 * bpf_iter_num_destroy(&fp[-8]) 1896 */ 1897 asm volatile ( 1898 "r1 = r10;" 1899 "r1 += -8;" 1900 "r2 = 0;" 1901 "r3 = 10;" 1902 "call %[bpf_iter_num_new];" 1903 /* call #1 */ 1904 "r1 = -32;" 1905 "r2 = r10;" 1906 "r2 += -8;" 1907 "call loop1;" 1908 "r1 = r10;" 1909 "r1 += -8;" 1910 "call %[bpf_iter_num_destroy];" 1911 /* call #2 */ 1912 "r1 = r10;" 1913 "r1 += -8;" 1914 "r2 = 0;" 1915 "r3 = 10;" 1916 "call %[bpf_iter_num_new];" 1917 "r1 = r10;" 1918 "r1 += -8;" 1919 "call loop1_wrapper;" 1920 /* return */ 1921 "r1 = r10;" 1922 "r1 += -8;" 1923 "call %[bpf_iter_num_destroy];" 1924 "r0 = 0;" 1925 "exit;" 1926 : 1927 : __imm(bpf_iter_num_new), 1928 __imm(bpf_iter_num_destroy), 1929 __imm(bpf_get_prandom_u32) 1930 : __clobber_all 1931 ); 1932 } 1933 1934 __used __naked 1935 static int loop1(void) 1936 { 1937 /* 1938 * int loop1(num, iter) { 1939 * r6 = num; 1940 * r7 = iter; 1941 * while (bpf_iter_num_next(r7)) { 1942 * if (unlikely(bpf_get_prandom_u32())) 1943 * *(fp + r6) = 7; 1944 * } 1945 * return 0 1946 * } 1947 */ 1948 asm volatile ( 1949 "r6 = r1;" 1950 "r7 = r2;" 1951 "call %[bpf_get_prandom_u32];" 1952 "r8 = r0;" 1953 "loop_%=:" 1954 "r1 = r7;" 1955 "call %[bpf_iter_num_next];" 1956 "if r0 == 0 goto loop_end_%=;" 1957 "call %[bpf_get_prandom_u32];" 1958 "if r0 == r8 goto use_r6_%=;" 1959 "goto loop_%=;" 1960 "loop_end_%=:" 1961 "r0 = 0;" 1962 "exit;" 1963 "use_r6_%=:" 1964 "r0 = r10;" 1965 "r0 += r6;" 1966 "r1 = 7;" 1967 "*(u64 *)(r0 + 0) = r1;" 1968 "goto loop_%=;" 1969 : 1970 : __imm(bpf_iter_num_next), 1971 __imm(bpf_get_prandom_u32) 1972 : __clobber_all 1973 ); 1974 } 1975 1976 __used __naked 1977 static int loop1_wrapper(void) 1978 { 1979 /* 1980 * int loop1_wrapper(iter) { 1981 * r6 = -32; 1982 * r7 = iter; 1983 * if (unlikely(bpf_get_prandom_u32())) 1984 * r6 = -31; 1985 * loop1(r6, r7); 1986 * return 0; 1987 * } 1988 */ 1989 asm volatile ( 1990 "r6 = -32;" 1991 "r7 = r1;" 1992 "call %[bpf_get_prandom_u32];" 1993 "r8 = r0;" 1994 "call %[bpf_get_prandom_u32];" 1995 "if r0 == r8 goto change_r6_%=;" 1996 "loop_%=:" 1997 "r1 = r6;" 1998 "r2 = r7;" 1999 "call loop1;" 2000 "r0 = 0;" 2001 "exit;" 2002 "change_r6_%=:" 2003 "r6 = -31;" 2004 "goto loop_%=;" 2005 : 2006 : __imm(bpf_iter_num_next), 2007 __imm(bpf_get_prandom_u32) 2008 : __clobber_all 2009 ); 2010 } 2011 2012 /* 2013 * This is similar to a test case absent_mark_in_the_middle_state(), 2014 * but adapted for use with bpf_loop(). 2015 */ 2016 SEC("raw_tp") 2017 __flag(BPF_F_TEST_STATE_FREQ) 2018 __failure __msg("math between fp pointer and register with unbounded min value is not allowed") 2019 __naked void absent_mark_in_the_middle_state4(void) 2020 { 2021 /* 2022 * Equivalent to a C program below: 2023 * 2024 * int main(void) { 2025 * fp[-8] = bpf_get_prandom_u32(); 2026 * fp[-16] = -32; // used in a memory access below 2027 * bpf_loop(7, loop_cb4, fp, 0); 2028 * return 0; 2029 * } 2030 * 2031 * int loop_cb4(int i, void *ctx) { 2032 * if (unlikely(ctx[-8] > bpf_get_prandom_u32())) 2033 * *(u64 *)(fp + ctx[-16]) = 42; // aligned access expected 2034 * if (unlikely(fp[-8] > bpf_get_prandom_u32())) 2035 * ctx[-16] = -31; // makes said access unaligned 2036 * return 0; 2037 * } 2038 */ 2039 asm volatile ( 2040 "call %[bpf_get_prandom_u32];" 2041 "r8 = r0;" 2042 "*(u64 *)(r10 - 8) = r0;" 2043 "*(u64 *)(r10 - 16) = -32;" 2044 "r1 = 7;" 2045 "r2 = loop_cb4 ll;" 2046 "r3 = r10;" 2047 "r4 = 0;" 2048 "call %[bpf_loop];" 2049 "r0 = 0;" 2050 "exit;" 2051 : 2052 : __imm(bpf_loop), 2053 __imm(bpf_get_prandom_u32) 2054 : __clobber_all 2055 ); 2056 } 2057 2058 __used __naked 2059 static void loop_cb4(void) 2060 { 2061 asm volatile ( 2062 "r9 = r2;" 2063 "r8 = *(u64 *)(r9 - 8);" 2064 "r6 = *(u64 *)(r9 - 16);" 2065 "call %[bpf_get_prandom_u32];" 2066 "if r0 > r8 goto use_fp16_%=;" 2067 "1:" 2068 "call %[bpf_get_prandom_u32];" 2069 "if r0 > r8 goto update_fp16_%=;" 2070 "2:" 2071 "r0 = 0;" 2072 "exit;" 2073 "use_fp16_%=:" 2074 "r1 = r10;" 2075 "r1 += r6;" 2076 "*(u64 *)(r1 + 0) = 42;" 2077 "goto 1b;" 2078 "update_fp16_%=:" 2079 "*(u64 *)(r9 - 16) = -31;" 2080 "goto 2b;" 2081 : 2082 : __imm(bpf_get_prandom_u32) 2083 ); 2084 } 2085 2086 SEC("raw_tp") 2087 __success 2088 __naked int stack_misc_vs_scalar_in_a_loop(void) 2089 { 2090 asm volatile( 2091 "*(u8 *)(r10 - 15) = 1;" /* This marks stack slot fp[-16] as STACK_MISC. */ 2092 "*(u8 *)(r10 - 23) = 1;" 2093 "*(u8 *)(r10 - 31) = 1;" 2094 "*(u8 *)(r10 - 39) = 1;" 2095 "*(u8 *)(r10 - 47) = 1;" 2096 "*(u8 *)(r10 - 55) = 1;" 2097 "*(u8 *)(r10 - 63) = 1;" 2098 "*(u8 *)(r10 - 71) = 1;" 2099 "*(u8 *)(r10 - 79) = 1;" 2100 "r1 = r10;" 2101 "r1 += -8;" 2102 "r2 = 0;" 2103 "r3 = 10;" 2104 "call %[bpf_iter_num_new];" 2105 "loop_%=:" 2106 "r1 = r10;" 2107 "r1 += -8;" 2108 "call %[bpf_iter_num_next];" 2109 "if r0 == 0 goto loop_end_%=;" 2110 2111 #define maybe_change_stack_slot(off) \ 2112 "call %[bpf_get_prandom_u32];" \ 2113 "if r0 == 42 goto +1;" \ 2114 "goto +1;" \ 2115 "*(u64 *)(r10 " #off ") = r0;" 2116 2117 /* 2118 * When comparing verifier states fp[-16] will be 2119 * either STACK_MISC or SCALAR. Pruning logic should 2120 * consider old STACK_MISC equivalent to current SCALAR 2121 * to avoid states explosion. 2122 */ 2123 maybe_change_stack_slot(-16) 2124 maybe_change_stack_slot(-24) 2125 maybe_change_stack_slot(-32) 2126 maybe_change_stack_slot(-40) 2127 maybe_change_stack_slot(-48) 2128 maybe_change_stack_slot(-56) 2129 maybe_change_stack_slot(-64) 2130 maybe_change_stack_slot(-72) 2131 maybe_change_stack_slot(-80) 2132 2133 #undef maybe_change_stack_slot 2134 2135 "goto loop_%=;" 2136 "loop_end_%=:" 2137 "r1 = r10;" 2138 "r1 += -8;" 2139 "call %[bpf_iter_num_destroy];" 2140 "r0 = 0;" 2141 "exit;" 2142 : 2143 : __imm(bpf_get_prandom_u32), 2144 __imm(bpf_iter_num_new), 2145 __imm(bpf_iter_num_next), 2146 __imm(bpf_iter_num_destroy), 2147 __imm_addr(amap) 2148 : __clobber_all 2149 ); 2150 } 2151 2152 __used 2153 static int loop_cb5(int i, __u64 *ctx) 2154 { 2155 /* unsafe on a second iteration */ 2156 small_arr[*ctx] = i; 2157 *ctx = 100500; 2158 return 0; 2159 } 2160 2161 SEC("raw_tp") 2162 __flag(BPF_F_TEST_STATE_FREQ) 2163 __failure __msg("memory access is {{.*}} and is outside of the object of size 64") 2164 __naked void loop_counter_precision_2nd_iter(void) 2165 { 2166 asm volatile ( 2167 "call %[bpf_get_prandom_u32];" 2168 "*(u64 *)(r10 - 8) = 0;" 2169 "r1 = 2;" 2170 "if r0 == 42 goto +1;" 2171 "r1 = 1;" 2172 "r2 = loop_cb5 ll;" 2173 "r3 = r10;" 2174 "r3 += -8;" 2175 "r4 = 0;" 2176 /* 2177 * Explore with nr_loops=1 on a first path and nr_loops=2 on a second path. 2178 * Buggy verifier did not propagate r1 precision properly, 2179 * and thus checkpoints created for nr_loops=1 case matched nr_loops=2 case. 2180 */ 2181 "call %[bpf_loop];" 2182 "r0 = 0;" 2183 "exit;" 2184 : 2185 : __imm(bpf_loop), 2186 __imm(bpf_get_prandom_u32) 2187 : __clobber_all 2188 ); 2189 } 2190 2191 /* 2192 * An iterator that is destroyed and created again inside its loop starts from 2193 * the beginning and the loop never ends. In the first four progs the first 2194 * prune point after bpf_iter_num_new() is the call of bpf_iter_num_next(). 2195 */ 2196 SEC("socket") 2197 __description("iter: remake in the loop, jump to next") 2198 __failure __msg("infinite loop detected") 2199 __naked void iter_remake_jmp(void) 2200 { 2201 asm volatile ( 2202 "r1 = r10;" 2203 "r1 += -8;" 2204 "r2 = 0;" 2205 "r3 = 10;" 2206 "call %[bpf_iter_num_new];" 2207 "1:" 2208 "call %[bpf_ktime_get_ns];" 2209 "if r0 != 0 goto 3f;" 2210 "r1 = r10;" 2211 "r1 += -8;" 2212 "2:" 2213 "call %[bpf_iter_num_next];" 2214 "if r0 != 0 goto 1b;" 2215 "r1 = r10;" 2216 "r1 += -8;" 2217 "call %[bpf_iter_num_destroy];" 2218 "r0 = 0;" 2219 "exit;" 2220 "3:" 2221 "r1 = r10;" 2222 "r1 += -8;" 2223 "call %[bpf_iter_num_destroy];" 2224 "r1 = r10;" 2225 "r1 += -8;" 2226 "r2 = 0;" 2227 "r3 = 10;" 2228 "call %[bpf_iter_num_new];" 2229 "r1 = r10;" 2230 "r1 += -8;" 2231 "goto 2b;" 2232 : 2233 : __imm(bpf_iter_num_new), 2234 __imm(bpf_iter_num_next), 2235 __imm(bpf_iter_num_destroy), 2236 __imm(bpf_ktime_get_ns) 2237 : __clobber_all); 2238 } 2239 2240 __used __naked static void iter_remake(void) 2241 { 2242 asm volatile ( 2243 "r6 = r1;" 2244 "call %[bpf_iter_num_destroy];" 2245 "r1 = r6;" 2246 "r2 = 0;" 2247 "r3 = 10;" 2248 "call %[bpf_iter_num_new];" 2249 "r0 = 0;" 2250 "exit;" 2251 : 2252 : __imm(bpf_iter_num_new), 2253 __imm(bpf_iter_num_destroy) 2254 : __clobber_all); 2255 } 2256 2257 SEC("socket") 2258 __description("iter: remake in a callee, jump to next") 2259 __failure __msg("infinite loop detected") 2260 __naked void iter_remake_callee_jmp(void) 2261 { 2262 asm volatile ( 2263 "r1 = r10;" 2264 "r1 += -8;" 2265 "r2 = 0;" 2266 "r3 = 10;" 2267 "call %[bpf_iter_num_new];" 2268 "1:" 2269 "call %[bpf_ktime_get_ns];" 2270 "if r0 != 0 goto 3f;" 2271 "r1 = r10;" 2272 "r1 += -8;" 2273 "2:" 2274 "call %[bpf_iter_num_next];" 2275 "if r0 != 0 goto 1b;" 2276 "r1 = r10;" 2277 "r1 += -8;" 2278 "call %[bpf_iter_num_destroy];" 2279 "r0 = 0;" 2280 "exit;" 2281 "3:" 2282 "r1 = r10;" 2283 "r1 += -8;" 2284 "call iter_remake;" 2285 "r1 = r10;" 2286 "r1 += -8;" 2287 "goto 2b;" 2288 : 2289 : __imm(bpf_iter_num_new), 2290 __imm(bpf_iter_num_next), 2291 __imm(bpf_iter_num_destroy), 2292 __imm(bpf_ktime_get_ns) 2293 : __clobber_all); 2294 } 2295 2296 SEC("socket") 2297 __description("iter: remake after next, jump to next") 2298 __failure __msg("infinite loop detected") 2299 __naked void iter_remake_after_next_jmp(void) 2300 { 2301 asm volatile ( 2302 "r1 = r10;" 2303 "r1 += -8;" 2304 "r2 = 0;" 2305 "r3 = 10;" 2306 "call %[bpf_iter_num_new];" 2307 "r1 = r10;" 2308 "r1 += -8;" 2309 "1:" 2310 "call %[bpf_iter_num_next];" 2311 "if r0 == 0 goto 2f;" 2312 "r1 = r10;" 2313 "r1 += -8;" 2314 "call %[bpf_iter_num_destroy];" 2315 "r1 = r10;" 2316 "r1 += -8;" 2317 "r2 = 0;" 2318 "r3 = 10;" 2319 "call %[bpf_iter_num_new];" 2320 "r1 = r10;" 2321 "r1 += -8;" 2322 "goto 1b;" 2323 "2:" 2324 "r1 = r10;" 2325 "r1 += -8;" 2326 "call %[bpf_iter_num_destroy];" 2327 "r0 = 0;" 2328 "exit;" 2329 : 2330 : __imm(bpf_iter_num_new), 2331 __imm(bpf_iter_num_next), 2332 __imm(bpf_iter_num_destroy), 2333 __imm(bpf_ktime_get_ns) 2334 : __clobber_all); 2335 } 2336 2337 SEC("socket") 2338 __description("iter: two iterators, remake each after its next") 2339 __failure __msg("infinite loop detected") 2340 __naked void iter_remake_two_jmp(void) 2341 { 2342 asm volatile ( 2343 "r1 = r10;" 2344 "r1 += -8;" 2345 "r2 = 0;" 2346 "r3 = 10;" 2347 "call %[bpf_iter_num_new];" 2348 "r1 = r10;" 2349 "r1 += -16;" 2350 "r2 = 0;" 2351 "r3 = 10;" 2352 "call %[bpf_iter_num_new];" 2353 "r1 = r10;" 2354 "r1 += -8;" 2355 "1:" 2356 "call %[bpf_iter_num_next];" 2357 "if r0 == 0 goto 2f;" 2358 "r1 = r10;" 2359 "r1 += -8;" 2360 "call %[bpf_iter_num_destroy];" 2361 "r1 = r10;" 2362 "r1 += -8;" 2363 "r2 = 0;" 2364 "r3 = 10;" 2365 "call %[bpf_iter_num_new];" 2366 "r1 = r10;" 2367 "r1 += -16;" 2368 "call %[bpf_iter_num_next];" 2369 "if r0 == 0 goto 2f;" 2370 "r1 = r10;" 2371 "r1 += -16;" 2372 "call %[bpf_iter_num_destroy];" 2373 "r1 = r10;" 2374 "r1 += -16;" 2375 "r2 = 0;" 2376 "r3 = 10;" 2377 "call %[bpf_iter_num_new];" 2378 "r1 = r10;" 2379 "r1 += -8;" 2380 "goto 1b;" 2381 "2:" 2382 "r1 = r10;" 2383 "r1 += -8;" 2384 "call %[bpf_iter_num_destroy];" 2385 "r1 = r10;" 2386 "r1 += -16;" 2387 "call %[bpf_iter_num_destroy];" 2388 "r0 = 0;" 2389 "exit;" 2390 : 2391 : __imm(bpf_iter_num_new), 2392 __imm(bpf_iter_num_next), 2393 __imm(bpf_iter_num_destroy), 2394 __imm(bpf_ktime_get_ns) 2395 : __clobber_all); 2396 } 2397 2398 /* Same loops with a prune point in front of bpf_iter_num_next() */ 2399 SEC("socket") 2400 __description("iter: remake in the loop") 2401 __failure __msg("infinite loop detected") 2402 __flag(BPF_F_TEST_STATE_FREQ) 2403 __naked void iter_remake_inline(void) 2404 { 2405 asm volatile ( 2406 "r1 = r10;" 2407 "r1 += -8;" 2408 "r2 = 0;" 2409 "r3 = 10;" 2410 "call %[bpf_iter_num_new];" 2411 "1:" 2412 "call %[bpf_ktime_get_ns];" 2413 "if r0 == 0 goto 2f;" 2414 "r1 = r10;" 2415 "r1 += -8;" 2416 "call %[bpf_iter_num_destroy];" 2417 "r1 = r10;" 2418 "r1 += -8;" 2419 "r2 = 0;" 2420 "r3 = 10;" 2421 "call %[bpf_iter_num_new];" 2422 "2:" 2423 "r1 = r10;" 2424 "r1 += -8;" 2425 "call %[bpf_iter_num_next];" 2426 "if r0 != 0 goto 1b;" 2427 "r1 = r10;" 2428 "r1 += -8;" 2429 "call %[bpf_iter_num_destroy];" 2430 "r0 = 0;" 2431 "exit;" 2432 : 2433 : __imm(bpf_iter_num_new), 2434 __imm(bpf_iter_num_next), 2435 __imm(bpf_iter_num_destroy), 2436 __imm(bpf_ktime_get_ns) 2437 : __clobber_all); 2438 } 2439 2440 SEC("socket") 2441 __description("iter: remake in a callee") 2442 __failure __msg("infinite loop detected") 2443 __flag(BPF_F_TEST_STATE_FREQ) 2444 __naked void iter_remake_callee(void) 2445 { 2446 asm volatile ( 2447 "r1 = r10;" 2448 "r1 += -8;" 2449 "r2 = 0;" 2450 "r3 = 10;" 2451 "call %[bpf_iter_num_new];" 2452 "1:" 2453 "call %[bpf_ktime_get_ns];" 2454 "if r0 == 0 goto 2f;" 2455 "r1 = r10;" 2456 "r1 += -8;" 2457 "call iter_remake;" 2458 "2:" 2459 "r1 = r10;" 2460 "r1 += -8;" 2461 "call %[bpf_iter_num_next];" 2462 "if r0 != 0 goto 1b;" 2463 "r1 = r10;" 2464 "r1 += -8;" 2465 "call %[bpf_iter_num_destroy];" 2466 "r0 = 0;" 2467 "exit;" 2468 : 2469 : __imm(bpf_iter_num_new), 2470 __imm(bpf_iter_num_next), 2471 __imm(bpf_iter_num_destroy), 2472 __imm(bpf_ktime_get_ns) 2473 : __clobber_all); 2474 } 2475 2476 SEC("socket") 2477 __description("iter: remake after next") 2478 __failure __msg("infinite loop detected") 2479 __flag(BPF_F_TEST_STATE_FREQ) 2480 __naked void iter_remake_after_next(void) 2481 { 2482 asm volatile ( 2483 "r1 = r10;" 2484 "r1 += -8;" 2485 "r2 = 0;" 2486 "r3 = 10;" 2487 "call %[bpf_iter_num_new];" 2488 "1:" 2489 "r1 = r10;" 2490 "r1 += -8;" 2491 "call %[bpf_iter_num_next];" 2492 "if r0 == 0 goto 2f;" 2493 "r1 = r10;" 2494 "r1 += -8;" 2495 "call %[bpf_iter_num_destroy];" 2496 "r1 = r10;" 2497 "r1 += -8;" 2498 "r2 = 0;" 2499 "r3 = 10;" 2500 "call %[bpf_iter_num_new];" 2501 "goto 1b;" 2502 "2:" 2503 "r1 = r10;" 2504 "r1 += -8;" 2505 "call %[bpf_iter_num_destroy];" 2506 "r0 = 0;" 2507 "exit;" 2508 : 2509 : __imm(bpf_iter_num_new), 2510 __imm(bpf_iter_num_next), 2511 __imm(bpf_iter_num_destroy), 2512 __imm(bpf_ktime_get_ns) 2513 : __clobber_all); 2514 } 2515 2516 SEC("socket") 2517 __description("iter: remake when drained") 2518 __failure __msg("infinite loop detected") 2519 __flag(BPF_F_TEST_STATE_FREQ) 2520 __naked void iter_remake_drained(void) 2521 { 2522 asm volatile ( 2523 "r1 = r10;" 2524 "r1 += -8;" 2525 "r2 = 0;" 2526 "r3 = 10;" 2527 "call %[bpf_iter_num_new];" 2528 "1:" 2529 "call %[bpf_ktime_get_ns];" 2530 "if r0 == 119 goto 2f;" 2531 "r1 = r10;" 2532 "r1 += -8;" 2533 "call %[bpf_iter_num_next];" 2534 "if r0 != 0 goto 1b;" 2535 "r1 = r10;" 2536 "r1 += -8;" 2537 "call %[bpf_iter_num_destroy];" 2538 "r1 = r10;" 2539 "r1 += -8;" 2540 "r2 = 0;" 2541 "r3 = 10;" 2542 "call %[bpf_iter_num_new];" 2543 "goto 1b;" 2544 "2:" 2545 "r1 = r10;" 2546 "r1 += -8;" 2547 "call %[bpf_iter_num_destroy];" 2548 "r0 = 0;" 2549 "exit;" 2550 : 2551 : __imm(bpf_iter_num_new), 2552 __imm(bpf_iter_num_next), 2553 __imm(bpf_iter_num_destroy), 2554 __imm(bpf_ktime_get_ns) 2555 : __clobber_all); 2556 } 2557 2558 /* The inner iterator is created in every iteration of the outer loop */ 2559 SEC("socket") 2560 __description("iter: nested loops") 2561 __success __retval(12) 2562 int iter_nested_remake(void *ctx) 2563 { 2564 int i, j, sum = 0; 2565 2566 bpf_for(i, 0, 3) { 2567 bpf_for(j, 0, 4) 2568 sum++; 2569 } 2570 return sum; 2571 } 2572 2573 char _license[] SEC("license") = "GPL"; 2574