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