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

Commit Message

Alexei Starovoitov March 1, 2024, 3:37 a.m. UTC

From: Alexei Starovoitov <[e-mail]>

Add tests for may_goto instruction via cond_break macro.

Signed-off-by: Alexei Starovoitov <[e-mail]>
---
 tools/testing/selftests/bpf/DENYLIST.s390x    |  1 +
 .../bpf/progs/verifier_iterating_callbacks.c  | 72 ++++++++++++++++++-
 2 files changed, 70 insertions(+), 3 deletions(-)

Comments

John Fastabend March 1, 2024, 7:47 p.m. UTC | #1

Alexei Starovoitov wrote:
> From: Alexei Starovoitov <[e-mail]>
> 
> Add tests for may_goto instruction via cond_break macro.
> 
> Signed-off-by: Alexei Starovoitov <[e-mail]>
> ---
>  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
is to me "feels" like a global hidden iterator appears to not
be reinitialized across calls?

 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;
 }
  
This fails with,

do_prog_test_run:PASS:bpf_prog_test_run 0 nsec
run_subtest:FAIL:654 Unexpected retval: 8388608 != 16777216
#430/15  verifier_iterating_callbacks/cond_break5:FAIL
#430     verifier_iterating_callbacks:FAIL

;       cnt += full_loop();                                         
     118:       18 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 r1 = 0 ll
     120:       b4 02 00 00 0d 00 00 00 w2 = 13
     121:       bc 73 00 00 00 00 00 00 w3 = w7
     122:       85 00 00 00 06 00 00 00 call 6
;                                                            

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.

> +
>  char _license[] SEC("license") = "GPL";
> -- 
> 2.34.1
> 
>

Alexei Starovoitov March 1, 2024, 9:16 p.m. UTC | #2

On Fri, Mar 1, 2024 at 11:47 AM John Fastabend <[e-mail]> wrote:
>
> Alexei Starovoitov wrote:
> > From: Alexei Starovoitov <[e-mail]>
> >
> > Add tests for may_goto instruction via cond_break macro.
> >
> > Signed-off-by: Alexei Starovoitov <[e-mail]>
> > ---
> >  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,
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().

Alexei Starovoitov March 1, 2024, 9:22 p.m. UTC | #3

On Thu, Feb 29, 2024 at 7:37 PM Alexei Starovoitov
<[e-mail]> wrote:
>
> +#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;

This is the reason for CI -no_alu32 fail.
I'll fix it in the next revision with:

 int cond_break1(const void *ctx)
 {
-       unsigned int i;
+       unsigned long i;
        unsigned int sum = 0;

John Fastabend March 1, 2024, 9:47 p.m. UTC | #4

Alexei Starovoitov wrote:
> On Fri, Mar 1, 2024 at 11:47 AM John Fastabend <[e-mail]> wrote:
> >
> > Alexei Starovoitov wrote:
> > > From: Alexei Starovoitov <[e-mail]>
> > >
> > > Add tests for may_goto instruction via cond_break macro.
> > >
> > > Signed-off-by: Alexei Starovoitov <[e-mail]>
> > > ---
> > >  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

John Fastabend March 1, 2024, 10:06 p.m. UTC | #5

John Fastabend wrote:
> Alexei Starovoitov wrote:
> > On Fri, Mar 1, 2024 at 11:47 AM John Fastabend <[e-mail]> wrote:
> > >
> > > Alexei Starovoitov wrote:
> > > > From: Alexei Starovoitov <[e-mail]>
> > > >
> > > > Add tests for may_goto instruction via cond_break macro.
> > > >
> > > > Signed-off-by: Alexei Starovoitov <[e-mail]>
> > > > ---
> > > >  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

Alexei Starovoitov March 1, 2024, 10:12 p.m. UTC | #6

On Fri, Mar 1, 2024 at 2:07 PM John Fastabend <[e-mail]> wrote:
> >
> >  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.

Thanks for the bug report.
For static case:

$ bpftool p dump xlated id 36

int cond_break5(const void * ctx):
; int cond_break5(const void *ctx)
   0: (7a) *(u64 *)(r10 -8) = 8388608
   1: (b4) w6 = 0
; cond_break;
   2: (79) r11 = *(u64 *)(r10 -8)
   3: (15) if r11 == 0x0 goto pc+4
   4: (17) r11 -= 1
   5: (7b) *(u64 *)(r10 -8) = r11
; cnt++;
   6: (04) w6 += 1
   7: (05) goto pc-6
; cnt += full_loop();
   8: (85) call pc+2#bpf_prog_270866f75dae27c8_full_loop
; for (;;) {
   9: (0c) w0 += w6
; return cnt;
  10: (95) exit
int full_loop():
; static __noinline int full_loop(void)
  11: (b4) w6 = 0
; bpf_printk("cnt==%d\n", cnt);
  12: (18) r1 = map[id:35][0]+0
  14: (b4) w2 = 9
  15: (bc) w3 = w6
  16: (85) call bpf_trace_printk#-87376
; return cnt;
  17: (bc) w0 = w6
  18: (95) exit

Looks like I made a mistake in may_goto verification.
Only the first loop remains. Other loops were removed as dead code.
It's certainly a bug in the patch 1. Will fix in the next revision.

pw-bot: cr

Patch

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;
+}
+
 char _license[] SEC("license") = "GPL";