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

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

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.

> 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