Re: [PATCH bpf 03/12] selftests/bpf: fix bpf_loop_bench for new callback verification scheme

[Eduard Zingerman <eddyz87@gmail.com>]

On Fri, 2023-11-17 at 11:46 -0500, Andrii Nakryiko wrote:
[...]
> > This has dire implications for bpf_loop_bench:
> > 
> >     SEC("fentry/" SYS_PREFIX "sys_getpgid")
> >     int benchmark(void *ctx)
> >     {
> >             for (int i = 0; i < 1000; i++) {
> >                     bpf_loop(nr_loops, empty_callback, NULL, 0);
> >                     __sync_add_and_fetch(&hits, nr_loops);
> >             }
> >             return 0;
> >     }
> > 
> > W/o callbacks change for verifier it merely represents 1000 calls to
> > empty_callback(). However, with callbacks change things become
> > exponential:
> > - i=0: state exploring empty_callback is scheduled with i=0 (a);
> > - i=1: state exploring empty_callback is scheduled with i=1;
> >   ...
> > - i=999: state exploring empty_callback is scheduled with i=999;
> > - state (a) is popped from stack;
> > - i=1: state exploring empty_callback is scheduled with i=1;
> >   ...
> 
> would this still happen if you use an obfuscated zero initializer for i?
> 
> int zero = 0; /* global var */
> 
> ...
> 
> 
> for (i = zero; i < 1000; i++) {
>      ...
> }

In that case it fails with jump limit.
Mechanism for states explosion is similar, as far as I understand.