1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */
3
4 #include <stdbool.h>
5 #include <linux/bpf.h>
6 #include <bpf/bpf_helpers.h>
7 #include "bpf_misc.h"
8
9 #define ARRAY_SIZE(x) (sizeof(x) / sizeof((x)[0]))
10
11 static volatile int zero = 0;
12
13 int my_pid;
14 int arr[256];
15 int small_arr[16] SEC(".data.small_arr");
16
17 #ifdef REAL_TEST
18 #define MY_PID_GUARD() if (my_pid != (bpf_get_current_pid_tgid() >> 32)) return 0
19 #else
20 #define MY_PID_GUARD() ({ })
21 #endif
22
23 SEC("?raw_tp")
24 __failure __msg("math between map_value pointer and register with unbounded min value is not allowed")
iter_err_unsafe_c_loop(const void * ctx)25 int iter_err_unsafe_c_loop(const void *ctx)
26 {
27 struct bpf_iter_num it;
28 int *v, i = zero; /* obscure initial value of i */
29
30 MY_PID_GUARD();
31
32 bpf_iter_num_new(&it, 0, 1000);
33 while ((v = bpf_iter_num_next(&it))) {
34 i++;
35 }
36 bpf_iter_num_destroy(&it);
37
38 small_arr[i] = 123; /* invalid */
39
40 return 0;
41 }
42
43 SEC("?raw_tp")
44 __failure __msg("unbounded memory access")
iter_err_unsafe_asm_loop(const void * ctx)45 int iter_err_unsafe_asm_loop(const void *ctx)
46 {
47 struct bpf_iter_num it;
48
49 MY_PID_GUARD();
50
51 asm volatile (
52 "r6 = %[zero];" /* iteration counter */
53 "r1 = %[it];" /* iterator state */
54 "r2 = 0;"
55 "r3 = 1000;"
56 "r4 = 1;"
57 "call %[bpf_iter_num_new];"
58 "loop:"
59 "r1 = %[it];"
60 "call %[bpf_iter_num_next];"
61 "if r0 == 0 goto out;"
62 "r6 += 1;"
63 "goto loop;"
64 "out:"
65 "r1 = %[it];"
66 "call %[bpf_iter_num_destroy];"
67 "r1 = %[small_arr];"
68 "r2 = r6;"
69 "r2 <<= 2;"
70 "r1 += r2;"
71 "*(u32 *)(r1 + 0) = r6;" /* invalid */
72 :
73 : [it]"r"(&it),
74 [small_arr]"p"(small_arr),
75 [zero]"p"(zero),
76 __imm(bpf_iter_num_new),
77 __imm(bpf_iter_num_next),
78 __imm(bpf_iter_num_destroy)
79 : __clobber_common, "r6"
80 );
81
82 return 0;
83 }
84
85 SEC("raw_tp")
86 __success
iter_while_loop(const void * ctx)87 int iter_while_loop(const void *ctx)
88 {
89 struct bpf_iter_num it;
90 int *v;
91
92 MY_PID_GUARD();
93
94 bpf_iter_num_new(&it, 0, 3);
95 while ((v = bpf_iter_num_next(&it))) {
96 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v);
97 }
98 bpf_iter_num_destroy(&it);
99
100 return 0;
101 }
102
103 SEC("raw_tp")
104 __success
iter_while_loop_auto_cleanup(const void * ctx)105 int iter_while_loop_auto_cleanup(const void *ctx)
106 {
107 __attribute__((cleanup(bpf_iter_num_destroy))) struct bpf_iter_num it;
108 int *v;
109
110 MY_PID_GUARD();
111
112 bpf_iter_num_new(&it, 0, 3);
113 while ((v = bpf_iter_num_next(&it))) {
114 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v);
115 }
116 /* (!) no explicit bpf_iter_num_destroy() */
117
118 return 0;
119 }
120
121 SEC("raw_tp")
122 __success
iter_for_loop(const void * ctx)123 int iter_for_loop(const void *ctx)
124 {
125 struct bpf_iter_num it;
126 int *v;
127
128 MY_PID_GUARD();
129
130 bpf_iter_num_new(&it, 5, 10);
131 for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) {
132 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v);
133 }
134 bpf_iter_num_destroy(&it);
135
136 return 0;
137 }
138
139 SEC("raw_tp")
140 __success
iter_bpf_for_each_macro(const void * ctx)141 int iter_bpf_for_each_macro(const void *ctx)
142 {
143 int *v;
144
145 MY_PID_GUARD();
146
147 bpf_for_each(num, v, 5, 10) {
148 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v);
149 }
150
151 return 0;
152 }
153
154 SEC("raw_tp")
155 __success
iter_bpf_for_macro(const void * ctx)156 int iter_bpf_for_macro(const void *ctx)
157 {
158 int i;
159
160 MY_PID_GUARD();
161
162 bpf_for(i, 5, 10) {
163 bpf_printk("ITER_BASIC: E2 VAL: v=%d", i);
164 }
165
166 return 0;
167 }
168
169 SEC("raw_tp")
170 __success
iter_pragma_unroll_loop(const void * ctx)171 int iter_pragma_unroll_loop(const void *ctx)
172 {
173 struct bpf_iter_num it;
174 int *v, i;
175
176 MY_PID_GUARD();
177
178 bpf_iter_num_new(&it, 0, 2);
179 #pragma nounroll
180 for (i = 0; i < 3; i++) {
181 v = bpf_iter_num_next(&it);
182 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1);
183 }
184 bpf_iter_num_destroy(&it);
185
186 return 0;
187 }
188
189 SEC("raw_tp")
190 __success
iter_manual_unroll_loop(const void * ctx)191 int iter_manual_unroll_loop(const void *ctx)
192 {
193 struct bpf_iter_num it;
194 int *v;
195
196 MY_PID_GUARD();
197
198 bpf_iter_num_new(&it, 100, 200);
199 v = bpf_iter_num_next(&it);
200 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
201 v = bpf_iter_num_next(&it);
202 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
203 v = bpf_iter_num_next(&it);
204 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
205 v = bpf_iter_num_next(&it);
206 bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1);
207 bpf_iter_num_destroy(&it);
208
209 return 0;
210 }
211
212 SEC("raw_tp")
213 __success
iter_multiple_sequential_loops(const void * ctx)214 int iter_multiple_sequential_loops(const void *ctx)
215 {
216 struct bpf_iter_num it;
217 int *v, i;
218
219 MY_PID_GUARD();
220
221 bpf_iter_num_new(&it, 0, 3);
222 while ((v = bpf_iter_num_next(&it))) {
223 bpf_printk("ITER_BASIC: E1 VAL: v=%d", *v);
224 }
225 bpf_iter_num_destroy(&it);
226
227 bpf_iter_num_new(&it, 5, 10);
228 for (v = bpf_iter_num_next(&it); v; v = bpf_iter_num_next(&it)) {
229 bpf_printk("ITER_BASIC: E2 VAL: v=%d", *v);
230 }
231 bpf_iter_num_destroy(&it);
232
233 bpf_iter_num_new(&it, 0, 2);
234 #pragma nounroll
235 for (i = 0; i < 3; i++) {
236 v = bpf_iter_num_next(&it);
237 bpf_printk("ITER_BASIC: E3 VAL: i=%d v=%d", i, v ? *v : -1);
238 }
239 bpf_iter_num_destroy(&it);
240
241 bpf_iter_num_new(&it, 100, 200);
242 v = bpf_iter_num_next(&it);
243 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
244 v = bpf_iter_num_next(&it);
245 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
246 v = bpf_iter_num_next(&it);
247 bpf_printk("ITER_BASIC: E4 VAL: v=%d", v ? *v : -1);
248 v = bpf_iter_num_next(&it);
249 bpf_printk("ITER_BASIC: E4 VAL: v=%d\n", v ? *v : -1);
250 bpf_iter_num_destroy(&it);
251
252 return 0;
253 }
254
255 SEC("raw_tp")
256 __success
iter_limit_cond_break_loop(const void * ctx)257 int iter_limit_cond_break_loop(const void *ctx)
258 {
259 struct bpf_iter_num it;
260 int *v, i = 0, sum = 0;
261
262 MY_PID_GUARD();
263
264 bpf_iter_num_new(&it, 0, 10);
265 while ((v = bpf_iter_num_next(&it))) {
266 bpf_printk("ITER_SIMPLE: i=%d v=%d", i, *v);
267 sum += *v;
268
269 i++;
270 if (i > 3)
271 break;
272 }
273 bpf_iter_num_destroy(&it);
274
275 bpf_printk("ITER_SIMPLE: sum=%d\n", sum);
276
277 return 0;
278 }
279
280 SEC("raw_tp")
281 __success
iter_obfuscate_counter(const void * ctx)282 int iter_obfuscate_counter(const void *ctx)
283 {
284 struct bpf_iter_num it;
285 int *v, sum = 0;
286 /* Make i's initial value unknowable for verifier to prevent it from
287 * pruning if/else branch inside the loop body and marking i as precise.
288 */
289 int i = zero;
290
291 MY_PID_GUARD();
292
293 bpf_iter_num_new(&it, 0, 10);
294 while ((v = bpf_iter_num_next(&it))) {
295 int x;
296
297 i += 1;
298
299 /* If we initialized i as `int i = 0;` above, verifier would
300 * track that i becomes 1 on first iteration after increment
301 * above, and here verifier would eagerly prune else branch
302 * and mark i as precise, ruining open-coded iterator logic
303 * completely, as each next iteration would have a different
304 * *precise* value of i, and thus there would be no
305 * convergence of state. This would result in reaching maximum
306 * instruction limit, no matter what the limit is.
307 */
308 if (i == 1)
309 x = 123;
310 else
311 x = i * 3 + 1;
312
313 bpf_printk("ITER_OBFUSCATE_COUNTER: i=%d v=%d x=%d", i, *v, x);
314
315 sum += x;
316 }
317 bpf_iter_num_destroy(&it);
318
319 bpf_printk("ITER_OBFUSCATE_COUNTER: sum=%d\n", sum);
320
321 return 0;
322 }
323
324 SEC("raw_tp")
325 __success
iter_search_loop(const void * ctx)326 int iter_search_loop(const void *ctx)
327 {
328 struct bpf_iter_num it;
329 int *v, *elem = NULL;
330 bool found = false;
331
332 MY_PID_GUARD();
333
334 bpf_iter_num_new(&it, 0, 10);
335
336 while ((v = bpf_iter_num_next(&it))) {
337 bpf_printk("ITER_SEARCH_LOOP: v=%d", *v);
338
339 if (*v == 2) {
340 found = true;
341 elem = v;
342 barrier_var(elem);
343 }
344 }
345
346 /* should fail to verify if bpf_iter_num_destroy() is here */
347
348 if (found)
349 /* here found element will be wrong, we should have copied
350 * value to a variable, but here we want to make sure we can
351 * access memory after the loop anyways
352 */
353 bpf_printk("ITER_SEARCH_LOOP: FOUND IT = %d!\n", *elem);
354 else
355 bpf_printk("ITER_SEARCH_LOOP: NOT FOUND IT!\n");
356
357 bpf_iter_num_destroy(&it);
358
359 return 0;
360 }
361
362 SEC("raw_tp")
363 __success
iter_array_fill(const void * ctx)364 int iter_array_fill(const void *ctx)
365 {
366 int sum, i;
367
368 MY_PID_GUARD();
369
370 bpf_for(i, 0, ARRAY_SIZE(arr)) {
371 arr[i] = i * 2;
372 }
373
374 sum = 0;
375 bpf_for(i, 0, ARRAY_SIZE(arr)) {
376 sum += arr[i];
377 }
378
379 bpf_printk("ITER_ARRAY_FILL: sum=%d (should be %d)\n", sum, 255 * 256);
380
381 return 0;
382 }
383
384 static int arr2d[4][5];
385 static int arr2d_row_sums[4];
386 static int arr2d_col_sums[5];
387
388 SEC("raw_tp")
389 __success
iter_nested_iters(const void * ctx)390 int iter_nested_iters(const void *ctx)
391 {
392 int sum, row, col;
393
394 MY_PID_GUARD();
395
396 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
397 bpf_for( col, 0, ARRAY_SIZE(arr2d[0])) {
398 arr2d[row][col] = row * col;
399 }
400 }
401
402 /* zero-initialize sums */
403 sum = 0;
404 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
405 arr2d_row_sums[row] = 0;
406 }
407 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
408 arr2d_col_sums[col] = 0;
409 }
410
411 /* calculate sums */
412 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
413 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
414 sum += arr2d[row][col];
415 arr2d_row_sums[row] += arr2d[row][col];
416 arr2d_col_sums[col] += arr2d[row][col];
417 }
418 }
419
420 bpf_printk("ITER_NESTED_ITERS: total sum=%d", sum);
421 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
422 bpf_printk("ITER_NESTED_ITERS: row #%d sum=%d", row, arr2d_row_sums[row]);
423 }
424 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
425 bpf_printk("ITER_NESTED_ITERS: col #%d sum=%d%s",
426 col, arr2d_col_sums[col],
427 col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : "");
428 }
429
430 return 0;
431 }
432
433 SEC("raw_tp")
434 __success
iter_nested_deeply_iters(const void * ctx)435 int iter_nested_deeply_iters(const void *ctx)
436 {
437 int sum = 0;
438
439 MY_PID_GUARD();
440
441 bpf_repeat(10) {
442 bpf_repeat(10) {
443 bpf_repeat(10) {
444 bpf_repeat(10) {
445 bpf_repeat(10) {
446 sum += 1;
447 }
448 }
449 }
450 }
451 /* validate that we can break from inside bpf_repeat() */
452 break;
453 }
454
455 return sum;
456 }
457
fill_inner_dimension(int row)458 static __noinline void fill_inner_dimension(int row)
459 {
460 int col;
461
462 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
463 arr2d[row][col] = row * col;
464 }
465 }
466
sum_inner_dimension(int row)467 static __noinline int sum_inner_dimension(int row)
468 {
469 int sum = 0, col;
470
471 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
472 sum += arr2d[row][col];
473 arr2d_row_sums[row] += arr2d[row][col];
474 arr2d_col_sums[col] += arr2d[row][col];
475 }
476
477 return sum;
478 }
479
480 SEC("raw_tp")
481 __success
iter_subprog_iters(const void * ctx)482 int iter_subprog_iters(const void *ctx)
483 {
484 int sum, row, col;
485
486 MY_PID_GUARD();
487
488 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
489 fill_inner_dimension(row);
490 }
491
492 /* zero-initialize sums */
493 sum = 0;
494 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
495 arr2d_row_sums[row] = 0;
496 }
497 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
498 arr2d_col_sums[col] = 0;
499 }
500
501 /* calculate sums */
502 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
503 sum += sum_inner_dimension(row);
504 }
505
506 bpf_printk("ITER_SUBPROG_ITERS: total sum=%d", sum);
507 bpf_for(row, 0, ARRAY_SIZE(arr2d)) {
508 bpf_printk("ITER_SUBPROG_ITERS: row #%d sum=%d",
509 row, arr2d_row_sums[row]);
510 }
511 bpf_for(col, 0, ARRAY_SIZE(arr2d[0])) {
512 bpf_printk("ITER_SUBPROG_ITERS: col #%d sum=%d%s",
513 col, arr2d_col_sums[col],
514 col == ARRAY_SIZE(arr2d[0]) - 1 ? "\n" : "");
515 }
516
517 return 0;
518 }
519
520 struct {
521 __uint(type, BPF_MAP_TYPE_ARRAY);
522 __type(key, int);
523 __type(value, int);
524 __uint(max_entries, 1000);
525 } arr_map SEC(".maps");
526
527 SEC("?raw_tp")
528 __failure __msg("invalid mem access 'scalar'")
iter_err_too_permissive1(const void * ctx)529 int iter_err_too_permissive1(const void *ctx)
530 {
531 int *map_val = NULL;
532 int key = 0;
533
534 MY_PID_GUARD();
535
536 map_val = bpf_map_lookup_elem(&arr_map, &key);
537 if (!map_val)
538 return 0;
539
540 bpf_repeat(1000000) {
541 map_val = NULL;
542 }
543
544 *map_val = 123;
545
546 return 0;
547 }
548
549 SEC("?raw_tp")
550 __failure __msg("invalid mem access 'map_value_or_null'")
iter_err_too_permissive2(const void * ctx)551 int iter_err_too_permissive2(const void *ctx)
552 {
553 int *map_val = NULL;
554 int key = 0;
555
556 MY_PID_GUARD();
557
558 map_val = bpf_map_lookup_elem(&arr_map, &key);
559 if (!map_val)
560 return 0;
561
562 bpf_repeat(1000000) {
563 map_val = bpf_map_lookup_elem(&arr_map, &key);
564 }
565
566 *map_val = 123;
567
568 return 0;
569 }
570
571 SEC("?raw_tp")
572 __failure __msg("invalid mem access 'map_value_or_null'")
iter_err_too_permissive3(const void * ctx)573 int iter_err_too_permissive3(const void *ctx)
574 {
575 int *map_val = NULL;
576 int key = 0;
577 bool found = false;
578
579 MY_PID_GUARD();
580
581 bpf_repeat(1000000) {
582 map_val = bpf_map_lookup_elem(&arr_map, &key);
583 found = true;
584 }
585
586 if (found)
587 *map_val = 123;
588
589 return 0;
590 }
591
592 SEC("raw_tp")
593 __success
iter_tricky_but_fine(const void * ctx)594 int iter_tricky_but_fine(const void *ctx)
595 {
596 int *map_val = NULL;
597 int key = 0;
598 bool found = false;
599
600 MY_PID_GUARD();
601
602 bpf_repeat(1000000) {
603 map_val = bpf_map_lookup_elem(&arr_map, &key);
604 if (map_val) {
605 found = true;
606 break;
607 }
608 }
609
610 if (found)
611 *map_val = 123;
612
613 return 0;
614 }
615
616 #define __bpf_memzero(p, sz) bpf_probe_read_kernel((p), (sz), 0)
617
618 SEC("raw_tp")
619 __success
iter_stack_array_loop(const void * ctx)620 int iter_stack_array_loop(const void *ctx)
621 {
622 long arr1[16], arr2[16], sum = 0;
623 int i;
624
625 MY_PID_GUARD();
626
627 /* zero-init arr1 and arr2 in such a way that verifier doesn't know
628 * it's all zeros; if we don't do that, we'll make BPF verifier track
629 * all combination of zero/non-zero stack slots for arr1/arr2, which
630 * will lead to O(2^(ARRAY_SIZE(arr1)+ARRAY_SIZE(arr2))) different
631 * states
632 */
633 __bpf_memzero(arr1, sizeof(arr1));
634 __bpf_memzero(arr2, sizeof(arr1));
635
636 /* validate that we can break and continue when using bpf_for() */
637 bpf_for(i, 0, ARRAY_SIZE(arr1)) {
638 if (i & 1) {
639 arr1[i] = i;
640 continue;
641 } else {
642 arr2[i] = i;
643 break;
644 }
645 }
646
647 bpf_for(i, 0, ARRAY_SIZE(arr1)) {
648 sum += arr1[i] + arr2[i];
649 }
650
651 return sum;
652 }
653
fill(struct bpf_iter_num * it,int * arr,__u32 n,int mul)654 static __noinline void fill(struct bpf_iter_num *it, int *arr, __u32 n, int mul)
655 {
656 int *t, i;
657
658 while ((t = bpf_iter_num_next(it))) {
659 i = *t;
660 if (i >= n)
661 break;
662 arr[i] = i * mul;
663 }
664 }
665
sum(struct bpf_iter_num * it,int * arr,__u32 n)666 static __noinline int sum(struct bpf_iter_num *it, int *arr, __u32 n)
667 {
668 int *t, i, sum = 0;;
669
670 while ((t = bpf_iter_num_next(it))) {
671 i = *t;
672 if (i >= n)
673 break;
674 sum += arr[i];
675 }
676
677 return sum;
678 }
679
680 SEC("raw_tp")
681 __success
iter_pass_iter_ptr_to_subprog(const void * ctx)682 int iter_pass_iter_ptr_to_subprog(const void *ctx)
683 {
684 int arr1[16], arr2[32];
685 struct bpf_iter_num it;
686 int n, sum1, sum2;
687
688 MY_PID_GUARD();
689
690 /* fill arr1 */
691 n = ARRAY_SIZE(arr1);
692 bpf_iter_num_new(&it, 0, n);
693 fill(&it, arr1, n, 2);
694 bpf_iter_num_destroy(&it);
695
696 /* fill arr2 */
697 n = ARRAY_SIZE(arr2);
698 bpf_iter_num_new(&it, 0, n);
699 fill(&it, arr2, n, 10);
700 bpf_iter_num_destroy(&it);
701
702 /* sum arr1 */
703 n = ARRAY_SIZE(arr1);
704 bpf_iter_num_new(&it, 0, n);
705 sum1 = sum(&it, arr1, n);
706 bpf_iter_num_destroy(&it);
707
708 /* sum arr2 */
709 n = ARRAY_SIZE(arr2);
710 bpf_iter_num_new(&it, 0, n);
711 sum2 = sum(&it, arr2, n);
712 bpf_iter_num_destroy(&it);
713
714 bpf_printk("sum1=%d, sum2=%d", sum1, sum2);
715
716 return 0;
717 }
718
719 char _license[] SEC("license") = "GPL";
720
