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")
iter_err_unsafe_c_loop(const void * ctx)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")
iter_err_unsafe_asm_loop(const void * ctx)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")
iter_num_new_inlined(void)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
iter_while_loop(const void * ctx)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
iter_while_loop_auto_cleanup(const void * ctx)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
iter_for_loop(const void * ctx)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
iter_bpf_for_each_macro(const void * ctx)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
iter_bpf_for_macro(const void * ctx)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
iter_pragma_unroll_loop(const void * ctx)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
iter_manual_unroll_loop(const void * ctx)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
iter_multiple_sequential_loops(const void * ctx)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
iter_limit_cond_break_loop(const void * ctx)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
iter_obfuscate_counter(const void * ctx)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
iter_search_loop(const void * ctx)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
iter_array_fill(const void * ctx)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
iter_nested_iters(const void * ctx)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
iter_nested_deeply_iters(const void * ctx)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
fill_inner_dimension(int row)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
sum_inner_dimension(int row)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
iter_subprog_iters(const void * ctx)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'")
iter_err_too_permissive1(const void * ctx)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'")
iter_err_too_permissive2(const void * ctx)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'")
iter_err_too_permissive3(const void * ctx)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
iter_tricky_but_fine(const void * ctx)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
iter_stack_array_loop(const void * ctx)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
fill(struct bpf_iter_num * it,int * arr,__u32 n,int mul)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
sum(struct bpf_iter_num * it,int * arr,__u32 n)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
iter_pass_iter_ptr_to_subprog(const void * ctx)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")
delayed_read_mark(void)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")
delayed_precision_mark(void)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")
__flag(BPF_F_TEST_STATE_FREQ)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")
__flag(BPF_F_TEST_STATE_FREQ)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")
__flag(BPF_F_TEST_STATE_FREQ)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
triple_continue(void)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
widen_spill(void)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
checkpoint_states_deletion(void)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
iter_arr_with_actual_elem_count(const void * ctx)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
nest_2(char * str)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
nest_1(int n)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
iter_subprog_check_stacksafe(const void * ctx)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 expected pointer to an iterator on stack")
iter_new_bad_arg(const void * ctx)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 expected pointer to an iterator on stack")
iter_next_bad_arg(const void * ctx)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 expected pointer to an iterator on stack")
iter_destroy_bad_arg(const void * ctx)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
clean_live_states(const void * ctx)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")
__flag(BPF_F_TEST_STATE_FREQ)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
noop(void)1802 static int noop(void)
1803 {
1804 asm volatile (
1805 "r0 = 0;"
1806 "exit;"
1807 );
1808 }
1809
1810 SEC("?raw_tp")
__flag(BPF_F_TEST_STATE_FREQ)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")
__flag(BPF_F_TEST_STATE_FREQ)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
loop1(void)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
loop1_wrapper(void)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")
__flag(BPF_F_TEST_STATE_FREQ)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
loop_cb4(void)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
stack_misc_vs_scalar_in_a_loop(void)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 char _license[] SEC("license") = "GPL";
2153