[bpf-next,0/3] Add bpf_for_each helper

Message

Joanne Koong Nov. 18, 2021, 1:04 a.m. UTC

This patchset add a new helper, bpf_for_each.

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_for_each helper moves the loop logic into the kernel and can thereby
guarantee that the loop will always terminate. The bpf_for_each 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_for_each 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_for_each
Patch 2 - tests
Patch 3 - benchmark for overhead of a bpf_for_each call


Joanne Koong (3):
  bpf: Add bpf_for_each helper
  selftests/bpf: Add tests for bpf_for_each
  selftest/bpf/benchs: add bpf_for_each benchmark

 include/linux/bpf.h                           |   1 +
 include/uapi/linux/bpf.h                      |  23 ++++
 kernel/bpf/bpf_iter.c                         |  32 ++++++
 kernel/bpf/helpers.c                          |   2 +
 kernel/bpf/verifier.c                         |  28 +++++
 tools/include/uapi/linux/bpf.h                |  23 ++++
 tools/testing/selftests/bpf/Makefile          |   3 +-
 tools/testing/selftests/bpf/bench.c           |   4 +
 .../selftests/bpf/benchs/bench_for_each.c     | 105 ++++++++++++++++++
 .../bpf/benchs/run_bench_for_each.sh          |  16 +++
 .../bpf/prog_tests/bpf_verif_scale.c          |  12 ++
 .../selftests/bpf/prog_tests/for_each.c       |  61 ++++++++++
 .../selftests/bpf/progs/for_each_helper.c     |  82 ++++++++++++++
 tools/testing/selftests/bpf/progs/pyperf.h    |  70 +++++++++++-
 .../selftests/bpf/progs/pyperf600_foreach.c   |   5 +
 .../testing/selftests/bpf/progs/strobemeta.h  |  73 +++++++++++-
 .../selftests/bpf/progs/strobemeta_foreach.c  |   9 ++
 17 files changed, 544 insertions(+), 5 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/benchs/bench_for_each.c
 create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_for_each.sh
 create mode 100644 tools/testing/selftests/bpf/progs/for_each_helper.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_foreach.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_foreach.c

Comments

Toke Høiland-Jørgensen Nov. 18, 2021, 11:14 a.m. UTC | #1

Joanne Koong <[e-mail]> writes:

> This patchset add a new helper, bpf_for_each.
>
> 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_for_each helper moves the loop logic into the kernel and can thereby
> guarantee that the loop will always terminate. The bpf_for_each 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_for_each 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.

Small nit with the "by 100%" formulation: when giving such relative
quantities 100% has a particular meaning, namely "eliminates entirely".
Which this doesn't, obviously, it *almost* eliminates the verification
overhead. So I'd change this to 99.5% instead (which is the actual value
from your numbers in patch 2).

Joanne Koong Nov. 19, 2021, 2:35 a.m. UTC | #2

On 11/18/21 3:14 AM, Toke Høiland-Jørgensen wrote:

> Joanne Koong <[e-mail]> writes:
>
>> This patchset add a new helper, bpf_for_each.
>>
>> 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_for_each helper moves the loop logic into the kernel and can thereby
>> guarantee that the loop will always terminate. The bpf_for_each 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_for_each 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.
> Small nit with the "by 100%" formulation: when giving such relative
> quantities 100% has a particular meaning, namely "eliminates entirely".
> Which this doesn't, obviously, it *almost* eliminates the verification
> overhead. So I'd change this to 99.5% instead (which is the actual value
> from your numbers in patch 2).
>
Great point!! I will change this to "~99%" (and make this change in 
patch #2's
commit message as well). Thanks for reviewing this patchset!