[v2,bpf-next,0/4] Add bpf_loop_helper

Message

Joanne Koong Nov. 23, 2021, 6:34 p.m. UTC

This patchset add a new helper, bpf_loop.

One of the complexities of using for loops in bpf programs is that the verifier
needs to ensure that in every possibility of the loop logic, the loop will always
terminate. As such, there is a limit on how many iterations the loop can do.

The bpf_loop helper moves the loop logic into the kernel and can thereby
guarantee that the loop will always terminate. The bpf_loop helper simplifies
a lot of the complexity the verifier needs to check, as well as removes the
constraint on the number of loops able to be run.

From the test results, we see that using bpf_loop in place
of the traditional for loop led to a decrease in verification time
and number of bpf instructions by 100%. The benchmark results show
that as the number of iterations increases, the overhead per iteration
decreases.

The high-level overview of the patches -
Patch 1 - kernel-side + API changes for adding bpf_loop
Patch 2 - tests
Patch 3 - use bpf_loop in strobemeta + pyperf600 and measure verifier performance
Patch 4 - benchmark for throughput + latency of bpf_loop call

v1 -> v2:
~ Change helper name to bpf_loop (instead of bpf_for_each)
~ Set max nr_loops (~8 million loops) for bpf_loop call
~ Split tests + strobemeta/pyperf600 changes into two patches
~ Add new ops_report_final helper for outputting throughput and latency


Joanne Koong (4):
  bpf: Add bpf_loop helper
  selftests/bpf: Add bpf_loop test
  selftests/bpf: measure bpf_loop verifier performance
  selftest/bpf/benchs: add bpf_loop benchmark

 include/linux/bpf.h                           |   1 +
 include/uapi/linux/bpf.h                      |  25 ++++
 kernel/bpf/bpf_iter.c                         |  35 +++++
 kernel/bpf/helpers.c                          |   2 +
 kernel/bpf/verifier.c                         |  97 +++++++-----
 tools/include/uapi/linux/bpf.h                |  25 ++++
 tools/testing/selftests/bpf/Makefile          |   4 +-
 tools/testing/selftests/bpf/bench.c           |  26 ++++
 tools/testing/selftests/bpf/bench.h           |   1 +
 .../selftests/bpf/benchs/bench_bpf_loop.c     | 105 +++++++++++++
 .../bpf/benchs/run_bench_bpf_loop.sh          |  15 ++
 .../selftests/bpf/benchs/run_common.sh        |  15 ++
 .../selftests/bpf/prog_tests/bpf_loop.c       | 138 ++++++++++++++++++
 .../bpf/prog_tests/bpf_verif_scale.c          |  12 ++
 tools/testing/selftests/bpf/progs/bpf_loop.c  |  99 +++++++++++++
 .../selftests/bpf/progs/bpf_loop_bench.c      |  26 ++++
 tools/testing/selftests/bpf/progs/pyperf.h    |  71 ++++++++-
 .../selftests/bpf/progs/pyperf600_bpf_loop.c  |   6 +
 .../testing/selftests/bpf/progs/strobemeta.h  |  75 +++++++++-
 .../selftests/bpf/progs/strobemeta_bpf_loop.c |   9 ++
 20 files changed, 745 insertions(+), 42 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_loop.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh
 create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop_bench.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c

Comments

Joanne Koong Nov. 23, 2021, 6:47 p.m. UTC | #1

On 11/23/21 10:34 AM, Joanne Koong wrote:

> This patchset add a new helper, bpf_loop.
>
> One of the complexities of using for loops in bpf programs is that the verifier
> needs to ensure that in every possibility of the loop logic, the loop will always
> terminate. As such, there is a limit on how many iterations the loop can do.
>
> The bpf_loop helper moves the loop logic into the kernel and can thereby
> guarantee that the loop will always terminate. The bpf_loop helper simplifies
> a lot of the complexity the verifier needs to check, as well as removes the
> constraint on the number of loops able to be run.
>
>  From the test results, we see that using bpf_loop in place
> of the traditional for loop led to a decrease in verification time
> and number of bpf instructions by 100%. The benchmark results show
> that as the number of iterations increases, the overhead per iteration
> decreases.
I will change the wording here to "led to a decrease in verification 
time and number
of bpf instructions by approximately ~99%". I changed this in patch 3 
but forgot to update
this here as well.
> The high-level overview of the patches -
> Patch 1 - kernel-side + API changes for adding bpf_loop
> Patch 2 - tests
> Patch 3 - use bpf_loop in strobemeta + pyperf600 and measure verifier performance
> Patch 4 - benchmark for throughput + latency of bpf_loop call
>
> v1 -> v2:
> ~ Change helper name to bpf_loop (instead of bpf_for_each)
> ~ Set max nr_loops (~8 million loops) for bpf_loop call
> ~ Split tests + strobemeta/pyperf600 changes into two patches
> ~ Add new ops_report_final helper for outputting throughput and latency
>
>
> Joanne Koong (4):
>    bpf: Add bpf_loop helper
>    selftests/bpf: Add bpf_loop test
>    selftests/bpf: measure bpf_loop verifier performance
>    selftest/bpf/benchs: add bpf_loop benchmark
>
>   include/linux/bpf.h                           |   1 +
>   include/uapi/linux/bpf.h                      |  25 ++++
>   kernel/bpf/bpf_iter.c                         |  35 +++++
>   kernel/bpf/helpers.c                          |   2 +
>   kernel/bpf/verifier.c                         |  97 +++++++-----
>   tools/include/uapi/linux/bpf.h                |  25 ++++
>   tools/testing/selftests/bpf/Makefile          |   4 +-
>   tools/testing/selftests/bpf/bench.c           |  26 ++++
>   tools/testing/selftests/bpf/bench.h           |   1 +
>   .../selftests/bpf/benchs/bench_bpf_loop.c     | 105 +++++++++++++
>   .../bpf/benchs/run_bench_bpf_loop.sh          |  15 ++
>   .../selftests/bpf/benchs/run_common.sh        |  15 ++
>   .../selftests/bpf/prog_tests/bpf_loop.c       | 138 ++++++++++++++++++
>   .../bpf/prog_tests/bpf_verif_scale.c          |  12 ++
>   tools/testing/selftests/bpf/progs/bpf_loop.c  |  99 +++++++++++++
>   .../selftests/bpf/progs/bpf_loop_bench.c      |  26 ++++
>   tools/testing/selftests/bpf/progs/pyperf.h    |  71 ++++++++-
>   .../selftests/bpf/progs/pyperf600_bpf_loop.c  |   6 +
>   .../testing/selftests/bpf/progs/strobemeta.h  |  75 +++++++++-
>   .../selftests/bpf/progs/strobemeta_bpf_loop.c |   9 ++
>   20 files changed, 745 insertions(+), 42 deletions(-)
>   create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_loop.c
>   create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh
>   create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c
>   create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.c
>   create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop_bench.c
>   create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c
>   create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c
>