Re: [PATCH v3 bpf-next 4/4] selftests/bpf: Test may_goto

[John Fastabend <john.fastabend@gmail.com>]

John Fastabend wrote:
> Alexei Starovoitov wrote:
> > On Fri, Mar 1, 2024 at 11:47 AM John Fastabend <john.fastabend@gmail.com> wrote:
> > >
> > > Alexei Starovoitov wrote:
> > > > From: Alexei Starovoitov <ast@kernel.org>
> > > >
> > > > Add tests for may_goto instruction via cond_break macro.
> > > >
> > > > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > > > ---
> > > >  tools/testing/selftests/bpf/DENYLIST.s390x    |  1 +
> > > >  .../bpf/progs/verifier_iterating_callbacks.c  | 72 ++++++++++++++++++-
> > > >  2 files changed, 70 insertions(+), 3 deletions(-)
> > > >
> > > > diff --git a/tools/testing/selftests/bpf/DENYLIST.s390x b/tools/testing/selftests/bpf/DENYLIST.s390x
> > > > index 1a63996c0304..c6c31b960810 100644
> > > > --- a/tools/testing/selftests/bpf/DENYLIST.s390x
> > > > +++ b/tools/testing/selftests/bpf/DENYLIST.s390x
> > > > @@ -3,3 +3,4 @@
> > > >  exceptions                            # JIT does not support calling kfunc bpf_throw                                (exceptions)
> > > >  get_stack_raw_tp                         # user_stack corrupted user stack                                             (no backchain userspace)
> > > >  stacktrace_build_id                      # compare_map_keys stackid_hmap vs. stackmap err -2 errno 2                   (?)
> > > > +verifier_iter/cond_break
> > > > diff --git a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> > > > index 5905e036e0ea..8476dc47623f 100644
> > > > --- a/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> > > > +++ b/tools/testing/selftests/bpf/progs/verifier_iterating_callbacks.c
> > > > @@ -1,8 +1,6 @@
> > > >  // SPDX-License-Identifier: GPL-2.0
> > > > -
> > > > -#include <linux/bpf.h>
> > > > -#include <bpf/bpf_helpers.h>
> > > >  #include "bpf_misc.h"
> > > > +#include "bpf_experimental.h"
> > > >
> > > >  struct {
> > > >       __uint(type, BPF_MAP_TYPE_ARRAY);
> > > > @@ -239,4 +237,72 @@ int bpf_loop_iter_limit_nested(void *unused)
> > > >       return 1000 * a + b + c;
> > > >  }
> > > >
> > > > +#define ARR_SZ 1000000
> > > > +int zero;
> > > > +char arr[ARR_SZ];
> > > > +
> > > > +SEC("socket")
> > > > +__success __retval(0xd495cdc0)
> > > > +int cond_break1(const void *ctx)
> > > > +{
> > > > +     unsigned int i;
> > > > +     unsigned int sum = 0;
> > > > +
> > > > +     for (i = zero; i < ARR_SZ; cond_break, i++)
> > > > +             sum += i;
> > > > +     for (i = zero; i < ARR_SZ; i++) {
> > > > +             barrier_var(i);
> > > > +             sum += i + arr[i];
> > > > +             cond_break;
> > > > +     }
> > > > +
> > > > +     return sum;
> > > > +}
> > > > +
> > > > +SEC("socket")
> > > > +__success __retval(999000000)
> > > > +int cond_break2(const void *ctx)
> > > > +{
> > > > +     int i, j;
> > > > +     int sum = 0;
> > > > +
> > > > +     for (i = zero; i < 1000; cond_break, i++)
> > > > +             for (j = zero; j < 1000; j++) {
> > > > +                     sum += i + j;
> > > > +                     cond_break;
> > > > +             }
> > > > +
> > > > +     return sum;
> > > > +}
> > > > +
> > > > +static __noinline int loop(void)
> > > > +{
> > > > +     int i, sum = 0;
> > > > +
> > > > +     for (i = zero; i <= 1000000; i++, cond_break)
> > > > +             sum += i;
> > > > +
> > > > +     return sum;
> > > > +}
> > > > +
> > > > +SEC("socket")
> > > > +__success __retval(0x6a5a2920)
> > > > +int cond_break3(const void *ctx)
> > > > +{
> > > > +     return loop();
> > > > +}
> > > > +
> > > > +SEC("socket")
> > > > +__success __retval(0x800000) /* BPF_MAX_LOOPS */
> > > > +int cond_break4(const void *ctx)
> > > > +{
> > > > +     int cnt = 0;
> > > > +
> > > > +     for (;;) {
> > > > +             cond_break;
> > > > +             cnt++;
> > > > +     }
> > > > +     return cnt;
> > > > +}
> > >
> > > I found this test illustrative to show how the cond_break which
> > 
> > ohh. I shouldn't have exposed this implementation detail
> > in the test. I'll adjust it in the next revision.
> > 
> > > is to me "feels" like a global hidden iterator appears to not
> > > be reinitialized across calls?
> > ...
> > > I guess this is by design but I sort of expected each
> > > call to have its own context. It does make some sense to
> > > limit main and all calls to a max loop count so not
> > > complaining. Maybe consider adding the test? I at least
> > > thought it helped.
> > 
> > At the moment each subprog has its own hidden counter,
> 
> aha that is how I read the patch1 as well. But I'm trying to follow
> why I get two different answers here.
> 
> Below passes all good the total there in break5 is 2xMAX_LOOPS which
> is what I expect from above and reading patch. If I trace the code
> I have two subprogs and each does fixup,
> 
>    insn_buf[j] = BPF_ST_MEM(BPF_DW, BPF_REG_FP,
>      -subprogs[i].stack_depth + j * 8, BPF_MAX_LOOPS);
> 
> This is the good one.
> 
>  __noinline int full_loop(void)
>  {
> 	int cnt = 0;
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 
> 	bpf_printk("cnt==%d\n", cnt);
> 	return cnt;
>  }
> 
>  SEC("socket")
>  __success __retval(16777216)
>  int cond_break5(const void *ctx)
>  {
> 	int cnt = 0;
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 
> 	cnt += full_loop();
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 	return cnt;
>  }
> 
> But adding static fails :( which I didn't expect. Is it obvious
> why this is the case?
> 
> static  __noinline int full_loop(void)
>  {
> 	int cnt = 0;
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 
> 	bpf_printk("cnt==%d\n", cnt);
> 	return cnt;
>  }
> 
>  SEC("socket")
>  __success __retval(16777216)
>  int cond_break5(const void *ctx)
>  {
> 	int cnt = 0;
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 
> 	cnt += full_loop();
> 
> 	for (;;) {
> 		cond_break;
> 		cnt++;
> 	}
> 	return cnt;
>  }
> 
> From verifier side story is slightly different. There are still
> two subprogs, but for subprog[0] has stack_slots==0? Debugging
> now but maybe its obvious what that static is doing to you.

That was a typo its subprog[1] with stack_slots == 0. Also
tracing insn it seems in nonstatic case we hit multiple
insn->code (BPF_JMP| BPF_JMA) but in the static case only
find the first one. Object file seems to have multiples
though. I need to drop for the rest of the afternoon most
likely, but will try to see what sort of silly thing I did
later today or worse case Monday.

> k
> > but we might have different limits per program type.
> > Like sleepable might be allowed to loop longer.
> > The actual limit of BPF_MAX_LOOPS is a random number.
> > The bpf prog shouldn't rely on any particular loop count.
> > Most likely we'll add a watchdog soon and will start cancelling
> > bpf progs that were on cpu for more than a second
> > regardless of number of iterations.
> > Arena faults will be causing loops to terminate too.
> > And so on.
> > In other words "cond_break" is a contract between
> > the verifier and the program. The verifier allows the
> > program to loop assuming it's behaving well,
> > but reserves the right to terminate it.
> > So bpf author can assume that cond_break is a nop
> > if their program is well formed.
> > The loops with discoverable iteration count like
> > for (i = 0; i < 1000; i++)
> > are not really a target use case for cond_break.
> > It's mainly for loops that may have unbounded looping,
> > but should terminate quickly when code is correct.
> > Like walking a link list or strlen().
> 
> Yep we do this a lot and just create some artifical upper
> bound so this is nicer for sure. Lots of Tetragon code reads
> 
> 
>    for (i = 0; i < MAX_LOOP; i++) {
>      do_stuff
>      if (exit_cond)
>        break;
>   } 
> 
> .John