diff mbox series

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

Message ID 20231116021803.9982-4-eddyz87@gmail.com (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series verify callbacks as if they are called unknown number of times | expand

Checks

Context Check Description
netdev/series_format success Posting correctly formatted
netdev/tree_selection success Clearly marked for bpf, async
netdev/fixes_present fail Series targets non-next tree, but doesn't contain any Fixes tags
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 8 this patch: 8
netdev/cc_maintainers warning 9 maintainers not CCed: haoluo@google.com song@kernel.org kpsingh@kernel.org jolsa@kernel.org john.fastabend@gmail.com linux-kselftest@vger.kernel.org shuah@kernel.org sdf@google.com mykolal@fb.com
netdev/build_clang success Errors and warnings before: 8 this patch: 8
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 8 this patch: 8
netdev/checkpatch success total: 0 errors, 0 warnings, 0 checks, 21 lines checked
netdev/build_clang_rust success No Rust files in patch. Skipping build
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-VM_Test-0 success Logs for Lint
bpf/vmtest-bpf-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-VM_Test-2 success Logs for Validate matrix.py
bpf/vmtest-bpf-VM_Test-3 success Logs for aarch64-gcc / build / build for aarch64 with gcc
bpf/vmtest-bpf-VM_Test-8 success Logs for aarch64-gcc / veristat
bpf/vmtest-bpf-VM_Test-7 success Logs for aarch64-gcc / test (test_verifier, false, 360) / test_verifier on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-4 success Logs for aarch64-gcc / test (test_maps, false, 360) / test_maps on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-5 success Logs for aarch64-gcc / test (test_progs, false, 360) / test_progs on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-6 success Logs for aarch64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-VM_Test-9 success Logs for s390x-gcc / build / build for s390x with gcc
bpf/vmtest-bpf-VM_Test-14 success Logs for s390x-gcc / veristat
bpf/vmtest-bpf-VM_Test-15 success Logs for set-matrix
bpf/vmtest-bpf-VM_Test-16 success Logs for x86_64-gcc / build / build for x86_64 with gcc
bpf/vmtest-bpf-VM_Test-17 success Logs for x86_64-gcc / test (test_maps, false, 360) / test_maps on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-18 success Logs for x86_64-gcc / test (test_progs, false, 360) / test_progs on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-19 success Logs for x86_64-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-20 success Logs for x86_64-gcc / test (test_progs_no_alu32_parallel, true, 30) / test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-21 success Logs for x86_64-gcc / test (test_progs_parallel, true, 30) / test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-22 success Logs for x86_64-gcc / test (test_verifier, false, 360) / test_verifier on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-23 success Logs for x86_64-gcc / veristat / veristat on x86_64 with gcc
bpf/vmtest-bpf-VM_Test-24 success Logs for x86_64-llvm-16 / build / build for x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-25 success Logs for x86_64-llvm-16 / test (test_maps, false, 360) / test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-26 success Logs for x86_64-llvm-16 / test (test_progs, false, 360) / test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-27 success Logs for x86_64-llvm-16 / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-28 success Logs for x86_64-llvm-16 / test (test_verifier, false, 360) / test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-VM_Test-29 success Logs for x86_64-llvm-16 / veristat
bpf/vmtest-bpf-VM_Test-13 success Logs for s390x-gcc / test (test_verifier, false, 360) / test_verifier on s390x with gcc
bpf/vmtest-bpf-VM_Test-12 success Logs for s390x-gcc / test (test_progs_no_alu32, false, 360) / test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-VM_Test-11 success Logs for s390x-gcc / test (test_progs, false, 360) / test_progs on s390x with gcc
bpf/vmtest-bpf-PR success PR summary
bpf/vmtest-bpf-VM_Test-10 success Logs for s390x-gcc / test (test_maps, false, 360) / test_maps on s390x with gcc

Commit Message

Eduard Zingerman Nov. 16, 2023, 2:17 a.m. UTC 
The patch a few patches from this one changes logic for callbacks
handling. While previously callbacks were verified as a single
function call, new scheme takes into account that callbacks could be
executed unknown number of times.

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;
  ...

Avoid this issue by rewriting outer loop as bpf_loop().
Unfortunately, this adds a function call to a loop at runtime, which
negatively affects performance:

            throughput               latency
   before:  149.919 ± 0.168 M ops/s, 6.670 ns/op
   after :  137.040 ± 0.187 M ops/s, 7.297 ns/op

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
---
 tools/testing/selftests/bpf/progs/bpf_loop_bench.c | 13 ++++++++-----
 1 file changed, 8 insertions(+), 5 deletions(-)

Comments

Andrii Nakryiko Nov. 17, 2023, 4:46 p.m. UTC | #1 
On Wed, Nov 15, 2023 at 9:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> The patch a few patches from this one changes logic for callbacks
> handling. While previously callbacks were verified as a single
> function call, new scheme takes into account that callbacks could be
> executed unknown number of times.
>
> 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++) {
     ...
}

>
> Avoid this issue by rewriting outer loop as bpf_loop().
> Unfortunately, this adds a function call to a loop at runtime, which
> negatively affects performance:
>
>             throughput               latency
>    before:  149.919 ± 0.168 M ops/s, 6.670 ns/op
>    after :  137.040 ± 0.187 M ops/s, 7.297 ns/op
>
> Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
> ---
>  tools/testing/selftests/bpf/progs/bpf_loop_bench.c | 13 ++++++++-----
>  1 file changed, 8 insertions(+), 5 deletions(-)
>

Either way, it doesn't seem like a big deal to me.

Acked-by: Andrii Nakryiko <andrii@kernel.org>



> diff --git a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
> index 4ce76eb064c4..d461746fd3c1 100644
> --- a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
> +++ b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
> @@ -15,13 +15,16 @@ static int empty_callback(__u32 index, void *data)
>         return 0;
>  }
>
> +static int outer_loop(__u32 index, void *data)
> +{
> +       bpf_loop(nr_loops, empty_callback, NULL, 0);
> +       __sync_add_and_fetch(&hits, nr_loops);
> +       return 0;
> +}
> +
>  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);
> -       }
> +       bpf_loop(1000, outer_loop, NULL, 0);
>         return 0;
>  }
> --
> 2.42.0
>
Eduard Zingerman Nov. 17, 2023, 6:52 p.m. UTC | #2 
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.
Alexei Starovoitov Nov. 17, 2023, 9:38 p.m. UTC | #3 
On Wed, Nov 15, 2023 at 6:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> The patch a few patches from this one changes logic for callbacks
> handling.

That's a wordsmith level 10. I'm far below this level.
Could you please rephrase it? 'The next patch changes ...' or something?
Eduard Zingerman Nov. 17, 2023, 9:43 p.m. UTC | #4 
On Fri, 2023-11-17 at 13:38 -0800, Alexei Starovoitov wrote:
> On Wed, Nov 15, 2023 at 6:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > 
> > The patch a few patches from this one changes logic for callbacks
> > handling.
> 
> That's a wordsmith level 10. I'm far below this level.
> Could you please rephrase it? 'The next patch changes ...' or something?

This is patch #3, and actual changes are in patch #6, I can change it to:

  A follow-up patch "bpf: verify callbacks as if they are called
  unknown number of times" changes logic for callbacks handling.
  While previously callbacks were verified as a single function
  call, new scheme takes into account that callbacks could be
  executed unknown number of times.
  ...

Would that work?
Alexei Starovoitov Nov. 17, 2023, 9:47 p.m. UTC | #5 
On Fri, Nov 17, 2023 at 1:43 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 13:38 -0800, Alexei Starovoitov wrote:
> > On Wed, Nov 15, 2023 at 6:18 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
> > >
> > > The patch a few patches from this one changes logic for callbacks
> > > handling.
> >
> > That's a wordsmith level 10. I'm far below this level.
> > Could you please rephrase it? 'The next patch changes ...' or something?
>
> This is patch #3, and actual changes are in patch #6, I can change it to:
>
>   A follow-up patch "bpf: verify callbacks as if they are called
>   unknown number of times" changes logic for callbacks handling.
>   While previously callbacks were verified as a single function
>   call, new scheme takes into account that callbacks could be
>   executed unknown number of times.
>   ...
>
> Would that work?

... or just drop it. The commit log typically describes only what's
happening in this commit or links to prior commits.
Future commit references are unusual.
Eduard Zingerman Nov. 17, 2023, 9:50 p.m. UTC | #6 
On Fri, 2023-11-17 at 13:47 -0800, Alexei Starovoitov wrote:
[...]
> > This is patch #3, and actual changes are in patch #6, I can change it to:
> > 
> >   A follow-up patch "bpf: verify callbacks as if they are called
> >   unknown number of times" changes logic for callbacks handling.
> >   While previously callbacks were verified as a single function
> >   call, new scheme takes into account that callbacks could be
> >   executed unknown number of times.
> >   ...
> > 
> > Would that work?
> 
> ... or just drop it. The commit log typically describes only what's
> happening in this commit or links to prior commits.
> Future commit references are unusual.

But there needs to be some justification.
Since this is not a test, maybe move it after patch #6 and refer to a
changes from a previous commit?
Alexei Starovoitov Nov. 17, 2023, 9:55 p.m. UTC | #7 
On Fri, Nov 17, 2023 at 1:50 PM Eduard Zingerman <eddyz87@gmail.com> wrote:
>
> On Fri, 2023-11-17 at 13:47 -0800, Alexei Starovoitov wrote:
> [...]
> > > This is patch #3, and actual changes are in patch #6, I can change it to:
> > >
> > >   A follow-up patch "bpf: verify callbacks as if they are called
> > >   unknown number of times" changes logic for callbacks handling.
> > >   While previously callbacks were verified as a single function
> > >   call, new scheme takes into account that callbacks could be
> > >   executed unknown number of times.
> > >   ...
> > >
> > > Would that work?
> >
> > ... or just drop it. The commit log typically describes only what's
> > happening in this commit or links to prior commits.
> > Future commit references are unusual.
>
> But there needs to be some justification.
> Since this is not a test, maybe move it after patch #6 and refer to a
> changes from a previous commit?

Better to keep it here to avoid breaking this test.
Use the above wording then.
diff mbox series

Patch

diff --git a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
index 4ce76eb064c4..d461746fd3c1 100644
--- a/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
+++ b/tools/testing/selftests/bpf/progs/bpf_loop_bench.c
@@ -15,13 +15,16 @@  static int empty_callback(__u32 index, void *data)
 	return 0;
 }
 
+static int outer_loop(__u32 index, void *data)
+{
+	bpf_loop(nr_loops, empty_callback, NULL, 0);
+	__sync_add_and_fetch(&hits, nr_loops);
+	return 0;
+}
+
 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);
-	}
+	bpf_loop(1000, outer_loop, NULL, 0);
 	return 0;
 }