Add bpf_loop helper
Subsystems (5)
v3 cover Add bpf_loop helper
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 ~99%. 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
v2 -> v3:
~ Rerun benchmarks on physical machine, update results ~ Propagate original error codes in the verifier
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 | 88 ++++++----- tools/include/uapi/linux/bpf.h | 25 ++++ tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/bench.c | 37 +++++ tools/testing/selftests/bpf/bench.h | 2 + .../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, 751 insertions(+), 39 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
Signature · 1 line
2.30.2
PATCH v3 1/4 bpf: Add bpf_loop helper
This patch adds the kernel-side and API changes for a new helper function, bpf_loop:
long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags);
where long (*callback_fn)(u32 index, void *ctx);
bpf_loop invokes the "callback_fn" **nr_loops** times or until the callback_fn returns 1. The callback_fn can only return 0 or 1, and this is enforced by the verifier. The callback_fn index is zero-indexed.
A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation of bpf_loop (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_loop calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ Recursive callback_fns do not pass the verifier, due to the call stack for these being too deep.
~ The next patch will include the tests and 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 | 88 +++++++++++++++++++++------------- tools/include/uapi/linux/bpf.h | 25 ++++++++++ 6 files changed, 142 insertions(+), 34 deletions(-)
include/linux/bpf.h +1 -0
@@ -2164,6 +2164,7 @@ extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct bpf_func_proto bpf_sk_getsockopt_proto;extern const struct bpf_func_proto bpf_kallsyms_lookup_name_proto;extern const struct bpf_func_proto bpf_find_vma_proto; +extern const struct bpf_func_proto bpf_loop_proto;const struct bpf_func_proto *tracing_prog_func_proto (enum bpf_func_id func_id,const struct bpf_prog *prog);
include/uapi/linux/bpf.h +25 -0
@@ -4957,6 +4957,30 @@ union bpf_attr {* **-ENOENT** if *task->mm* is NULL, or no vma contains *addr*. * **-EBUSY** if failed to try lock mmap_lock. * **-EINVAL** for invalid **flags**. +* +* long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_loops**, call **callback_fn** function +* with **callback_ctx** as the context parameter. +* The **callback_fn** should be a static function and +* the **callback_ctx** should be a pointer to the stack. +* The **flags** is used to control certain aspects of the helper. +* Currently, the **flags** must be 0. Currently, nr_loops is +* limited to 1 << 23 (~8 million) loops. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the loop. The index +* is zero-indexed. +* +* If **callback_fn** returns 0, the helper will continue to the next +* loop. If return value is 1, the helper will skip the rest of +* the loops and return. Other return values are not used now, +* and will be rejected by the verifier. +* +* Return +* The number of loops performed, **-EINVAL** for invalid **flags**, +* **-E2BIG** if **nr_loops** exceeds the maximum number of loops. */ #define __BPF_FUNC_MAPPER (FN ) \ FN(unspec), \
@@ -5140,6 +5164,7 @@ union bpf_attr {FN (skc_to_unix_sock), \FN (kallsyms_lookup_name), \FN (find_vma), \ +FN (loop), \/* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper
kernel/bpf/bpf_iter.c +35 -0
@@ -714,3 +714,38 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = { .arg3_type = ARG_PTR_TO_STACK_OR_NULL, .arg4_type = ARG_ANYTHING, }; + +/* maximum number of loops */ +#define MAX_LOOPS BIT(23) + +BPF_CALL_4(bpf_loop, u32, nr_loops, void *, callback_fn, void *, callback_ctx, + u64, flags) +{ +bpf_callback_t callback = (bpf_callback_t )callback_fn; +u64 ret; +u32 i; + +if (flags) +return -EINVAL ; +if (nr_loops >MAX_LOOPS ) +return -E2BIG ; + +for (i =0 ; i < nr_loops; i++) { + ret =callback ((u64 )i, (u64 )(long )callback_ctx,0 ,0 ,0 ); +/* return value: 0 - continue, 1 - stop and return */ +if (ret) +return i +1 ; + } + +return i; +} + +const struct bpf_func_proto bpf_loop_proto = { + .func = bpf_loop, + .gpl_only = false, + .ret_type =RET_INTEGER , + .arg1_type =ARG_ANYTHING , + .arg2_type =ARG_PTR_TO_FUNC , + .arg3_type =ARG_PTR_TO_STACK_OR_NULL , + .arg4_type =ARG_ANYTHING , +};
kernel/bpf/helpers.c +2 -0
@@ -1378,6 +1378,8 @@ bpf_base_func_proto(enum bpf_func_id func_id)return &bpf_ringbuf_query_proto;case BPF_FUNC_for_each_map_elem:return &bpf_for_each_map_elem_proto; +case BPF_FUNC_loop: +return &bpf_loop_proto;default :break ; }
kernel/bpf/verifier.c +54 -34
115 lines not on this page · raw message
tools/include/uapi/linux/bpf.h +25 -0
@@ -4957,6 +4957,30 @@ union bpf_attr {* **-ENOENT** if *task->mm* is NULL, or no vma contains *addr*. * **-EBUSY** if failed to try lock mmap_lock. * **-EINVAL** for invalid **flags**. +* +* long bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_loops**, call **callback_fn** function +* with **callback_ctx** as the context parameter. +* The **callback_fn** should be a static function and +* the **callback_ctx** should be a pointer to the stack. +* The **flags** is used to control certain aspects of the helper. +* Currently, the **flags** must be 0. Currently, nr_loops is +* limited to 1 << 23 (~8 million) loops. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the loop. The index +* is zero-indexed. +* +* If **callback_fn** returns 0, the helper will continue to the next +* loop. If return value is 1, the helper will skip the rest of +* the loops and return. Other return values are not used now, +* and will be rejected by the verifier. +* +* Return +* The number of loops performed, **-EINVAL** for invalid **flags**, +* **-E2BIG** if **nr_loops** exceeds the maximum number of loops. */ #define __BPF_FUNC_MAPPER (FN ) \ FN(unspec), \
@@ -5140,6 +5164,7 @@ union bpf_attr {FN (skc_to_unix_sock), \FN (kallsyms_lookup_name), \FN (find_vma), \ +FN (loop), \/* */ /* integer value in 'imm' field of BPF_CALL instruction selects which helper
Signature · 1 line
2.30.2
Re: [PATCH v3 bpf-next 1/4] bpf: Add bpf_loop helper
Quoted 25 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_loop:long
bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags);where long (*callback_fn)(u32 index, void *ctx);
bpf_loopinvokes the "callback_fn" **nr_loops** times or until thecallback_fnreturns 1. Thecallback_fncan only return 0 or 1, and this is enforced by the verifier. Thecallback_fnindex is zero-indexed.A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation ofbpf_loop(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_loopcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ Recursivecallback_fnsdo not pass the verifier, due to the call stack for these being too deep.
~ The next patch will include the tests and benchmark
Quoted 2 lines
Signed-off-by Joanne Koong <[email protected]>---
LGTM.
Quoted 8 lines
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 | 88 +++++++++++++++++++++------------- tools/include/uapi/linux/bpf.h | 25 ++++++++++ 6 files changed, 142 insertions(+), 34 deletions(-)
[...]
Re: [PATCH v3 bpf-next 1/4] bpf: Add bpf_loop helper
In reply to Joanne KoongQuoted 24 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_loop:long
bpf_loop(u32 nr_loops, void *callback_fn, void *callback_ctx, u64 flags);where long (*callback_fn)(u32 index, void *ctx);
bpf_loopinvokes the "callback_fn" **nr_loops** times or until thecallback_fnreturns 1. Thecallback_fncan only return 0 or 1, and this is enforced by the verifier. Thecallback_fnindex is zero-indexed.A few things to please note:
~ The "u64 flags" parameter is currently unused but is included in case a future use case for it arises.
~ In the kernel-side implementation ofbpf_loop(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_loopcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ Recursivecallback_fnsdo not pass the verifier, due to the call stack for these being too deep.
~ The next patch will include the tests and benchmark
Quoted 1 line
Signed-off-by Joanne Koong <[email protected]>
PATCH v3 2/4 selftests/bpf: Add bpf_loop test
In reply to Joanne KoongAdd test for bpf_loop testing a variety of cases:
various nr_loops, null callback ctx, invalid flags, nested callbacks.
--- .../selftests/bpf/prog_tests/bpf_loop.c | 138 ++++++++++++++++++ tools/testing/selftests/bpf/progs/bpf_loop.c | 99 +++++++++++++ 2 files changed, 237 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.c
tools/testing/selftests/bpf/prog_tests/bpf_loop.c new file +138 -0
@@ -0,0 +1,138 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include <test_progs.h> +#include <network_helpers.h> +#include "bpf_loop.skel.h" + +static void check_nr_loops (struct bpf_loop *skel) +{ +__u32 retval, duration; +int err; + +/* test 0 loops */ + skel->bss->nr_loops =0 ; + err =bpf_prog_test_run (bpf_program__fd (skel->progs.test_prog), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (!ASSERT_OK (err,"err" ) || !ASSERT_OK (retval,"retval" )) +return ; +ASSERT_EQ (skel->bss->nr_loops_returned, skel->bss->nr_loops, +"0 loops" ); + +/* test 500 loops */ + skel->bss->nr_loops =500 ; + err =bpf_prog_test_run (bpf_program__fd (skel->progs.test_prog), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (!ASSERT_OK (err,"err" ) || + !ASSERT_OK (retval,"retval" )) +return ; +ASSERT_EQ (skel->bss->nr_loops_returned, skel->bss->nr_loops, +"500 loops" ); +ASSERT_EQ (skel->bss->g_output, (500 *499 ) /2 ,"g_output" ); + +/* test exceeding the max limit */ + skel->bss->nr_loops =-1 ; + err =bpf_prog_test_run (bpf_program__fd (skel->progs.test_prog), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (!ASSERT_OK (err,"err" ) || !ASSERT_OK (retval,"retval" )) +return ; +ASSERT_EQ (skel->bss->err, -E2BIG ,"over max limit" ); +} + +static void check_callback_fn_stop (struct bpf_loop *skel) +{ +__u32 retval, duration; +int err; + + skel->bss->nr_loops =400 ; + skel->data->stop_index =50 ; + +/* testing that loop is stopped when callback_fn returns 1 */ + err =bpf_prog_test_run (bpf_program__fd (skel->progs.test_prog), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); + +if (!ASSERT_OK (err,"err" ) || !ASSERT_OK (retval,"retval" )) +return ; + +ASSERT_EQ (skel->bss->nr_loops_returned, skel->data->stop_index +1 , +"nr_loops_returned" ); +ASSERT_EQ (skel->bss->g_output, (50 *49 ) /2 , +"g_output" ); +} + +static void check_null_callback_ctx (struct bpf_loop *skel) +{ +__u32 retval, duration; +int err; + + skel->bss->nr_loops =10 ; + +/* check that user is able to pass in a null callback_ctx */ + err =bpf_prog_test_run (bpf_program__fd (skel->progs.prog_null_ctx), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); + +if (!ASSERT_OK (err,"err" ) || !ASSERT_OK (retval,"retval" )) +return ; + +ASSERT_EQ (skel->bss->nr_loops_returned, skel->bss->nr_loops, +"nr_loops_returned" ); +} + +static void check_invalid_flags (struct bpf_loop *skel) +{ +__u32 retval, duration; +int err; + +/* check that passing in non-zero flags returns -EINVAL */ + err =bpf_prog_test_run (bpf_program__fd (skel->progs.prog_invalid_flags), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); + +if (!ASSERT_OK (err,"err" ) || !ASSERT_OK (retval,"retval" )) +return ; + +ASSERT_EQ (skel->bss->err, -EINVAL ,"err" ); +} + +static void check_nested_calls (struct bpf_loop *skel) +{ +__u32 nr_loops =100 , nested_callback_nr_loops =4 ; +__u32 retval, duration; +int err; + + skel->bss->nr_loops = nr_loops; + skel->bss->nested_callback_nr_loops = nested_callback_nr_loops; + +/* check that nested calls are supported */ + err =bpf_prog_test_run (bpf_program__fd (skel->progs.prog_nested_calls), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (!ASSERT_OK (err,"err" ) || !ASSERT_OK (retval,"retval" )) +return ; +ASSERT_EQ (skel->bss->nr_loops_returned, nr_loops * nested_callback_nr_loops + * nested_callback_nr_loops,"nr_loops_returned" ); +ASSERT_EQ (skel->bss->g_output, (4 *3 ) /2 * nested_callback_nr_loops + * nr_loops,"g_output" ); +} + +void test_bpf_loop (void ) +{ +struct bpf_loop *skel; + + skel =bpf_loop__open_and_load (); +if (!ASSERT_OK_PTR (skel,"bpf_loop__open_and_load" )) +return ; + +check_nr_loops (skel); +check_callback_fn_stop (skel); +check_null_callback_ctx (skel); +check_invalid_flags (skel); +check_nested_calls (skel); + +bpf_loop__destroy (skel); +}
tools/testing/selftests/bpf/progs/bpf_loop.c new file +99 -0
99 lines not on this page · raw message
Signature · 1 line
2.30.2
Re: [PATCH v3 bpf-next 2/4] selftests/bpf: Add bpf_loop test
Quoted 6 lines · Joanne Koong
Add test for
bpf_looptesting a variety of cases:
variousnr_loops, null callback ctx, invalid flags, nested callbacks.Signed-off-by Joanne Koong <[email protected]>---
LGTM, one small nit below.
tools/testing/selftests/bpf/prog_tests/bpf_loop.c line 19
Quoted 12 lines
.../selftests/bpf/prog_tests/bpf_loop.c | 138 ++++++++++++++++++ tools/testing/selftests/bpf/progs/bpf_loop.c | 99 +++++++++++++ 2 files changed, 237 insertions(+) create mode 100644 tools/testing/selftests/bpf/prog_tests/bpf_loop.c create mode 100644 tools/testing/selftests/bpf/progs/bpf_loop.ctools/testing/selftests/bpf/prog_tests/bpf_loop.c new file +5
-0+ err =bpf_prog_test_run (bpf_program__fd (skel->progs.test_prog), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (!ASSERT_OK (err,"err" ) || !ASSERT_OK (retval,"retval" )) +return ;
Still think that usleep(1) is better and cleaner... pkt_v4 has nothing to do with what you are testing.
Quoted 5 lines
tools/testing/selftests/bpf/prog_tests/bpf_loop.c new file +5
-0+ASSERT_EQ (skel->bss->nr_loops_returned, skel->bss->nr_loops, +"0 loops" ); + +/* test 500 loops */ + skel->bss->nr_loops =500 ;
[...]
PATCH v3 3/4 selftests/bpf: measure bpf_loop verifier performance
In reply to Joanne KoongThis patch tests bpf_loop in pyperf and strobemeta, and measures the verifier performance of replacing the traditional for loop with bpf_loop.
The results are as follows:
~strobemeta~
Baseline
verification time 6808200 usec
stack depth 496
processed 554252 insns (limit 1000000) max_states_per_insn 16 total_states 15878 peak_states 13489 mark_read 3110 #192 verif_scale_strobemeta:OK (unrolled loop)
Using bpf_loop
verification time 31589 usec
stack depth 96+400
processed 1513 insns (limit 1000000) max_states_per_insn 2 total_states 106 peak_states 106 mark_read 60 #193 verif_scale_strobemeta_bpf_loop:OK
~pyperf600~
Baseline
verification time 29702486 usec
stack depth 368
processed 626838 insns (limit 1000000) max_states_per_insn 7
total_states 30368 peak_states 30279 mark_read 748
#182 verif_scale_pyperf600:OK (unrolled loop)Using bpf_loop
verification time 148488 usec
stack depth 320+40
processed 10518 insns (limit 1000000) max_states_per_insn 10
total_states 705 peak_states 517 mark_read 38
#183 verif_scale_pyperf600_bpf_loop:OKUsing the bpf_loop helper led to approximately a 99% decrease in the verification time and in the number of instructions.
--- .../bpf/prog_tests/bpf_verif_scale.c | 12 +++ 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 +++ 5 files changed, 169 insertions(+), 4 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c
tools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c +12 -0
@@ -115,6 +115,12 @@ void test_verif_scale_pyperf600()scale_test ("pyperf600.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); } +void test_verif_scale_pyperf600_bpf_loop (void ) +{ +/* use the bpf_loop helper*/ +scale_test ("pyperf600_bpf_loop.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); +} +void test_verif_scale_pyperf600_nounroll () {/* no unroll at all.
@@ -165,6 +171,12 @@ void test_verif_scale_strobemeta()scale_test ("strobemeta.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); } +void test_verif_scale_strobemeta_bpf_loop (void ) +{ +/* use the bpf_loop helper*/ +scale_test ("strobemeta_bpf_loop.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); +} +void test_verif_scale_strobemeta_nounroll1 () {/* no unroll, tiny loops */
tools/testing/selftests/bpf/progs/pyperf.h +70 -1
93 lines not on this page · raw message
tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c new file +6 -0
@@ -0,0 +1,6 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2021 Facebook + +#define STACK_MAX_LEN 600 +#define USE_BPF_LOOP +#include "pyperf.h"
tools/testing/selftests/bpf/progs/strobemeta.h +72 -3
106 lines not on this page · raw message
tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c new file +9 -0
@@ -0,0 +1,9 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +// Copyright (c) 2021 Facebook + +#define STROBE_MAX_INTS 2 +#define STROBE_MAX_STRS 25 +#define STROBE_MAX_MAPS 100 +#define STROBE_MAX_MAP_ENTRIES 20 +#define USE_BPF_LOOP +#include "strobemeta.h"
Signature · 1 line
2.30.2
Re: [PATCH v3 bpf-next 3/4] selftests/bpf: measure bpf_loop verifier performance
Quoted 39 lines · Joanne Koong
This patch tests
bpf_loopin pyperf and strobemeta, and measures the verifier performance of replacing the traditional for loop withbpf_loop.The results are as follows:
~strobemeta~
Baseline
verification time 6808200 usec
stack depth 496
processed 554252 insns (limit 1000000)max_states_per_insn16total_states15878peak_states13489mark_read3110 #192 verif_scale_strobemeta:OK (unrolled loop)Using
bpf_loop
verification time 31589 usec
stack depth 96+400
processed 1513 insns (limit 1000000)max_states_per_insn2total_states106peak_states106mark_read60 #193 verif_scale_strobemeta_bpf_loop:OK~pyperf600~
Baseline
verification time 29702486 usec stack depth 368 processed 626838 insns (limit 1000000) max_states_per_insn 7 total_states 30368 peak_states 30279 mark_read 748 #182 verif_scale_pyperf600:OK (unrolled loop)Using
bpf_loopverification time 148488 usec stack depth 320+40 processed 10518 insns (limit 1000000) max_states_per_insn 10 total_states 705 peak_states 517 mark_read 38 #183 verif_scale_pyperf600_bpf_loop:OK
Quoted 5 lines
Using the
bpf_loophelper led to approximately a 99% decrease in the verification time and in the number of instructions.Signed-off-by Joanne Koong <[email protected]>---
Quoted 9 lines
.../bpf/prog_tests/bpf_verif_scale.c | 12 +++ 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 +++ 5 files changed, 169 insertions(+), 4 deletions(-) create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c
[...]
Quoted 17 lines
/* Unwind python stack */ for (int i = 0; i < STACK_MAX_LEN; ++i) { if (frame_ptr && get_frame_data(frame_ptr, pidData, &frame, &sym)) {tools/testing/selftests/bpf/progs/pyperf.h +1
-0@@ -251,6 +319,7 @@ int __on_event(struct bpf_raw_tracepoint_args *ctx) frame_ptr = frame.f_back; } } +#endif /* USE_BPF_LOOP */ event->stack_complete = frame_ptr ==NULL ; }else { event->stack_complete =1 ;tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c new file +0
-0
tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c line 2
Quoted 2 lines
tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c new file +2
-0@@ -0,0 +1,6 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2021 Facebook
nit: should be /* ... */
Quoted 4 lines
tools/testing/selftests/bpf/progs/pyperf600_bpf_loop.c new file +4
-0+ +#define STACK_MAX_LEN 600 +#define USE_BPF_LOOP +#include "pyperf.h"
[...]
tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c line 2
Quoted 8 lines
tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c new file +2
-0@@ -0,0 +1,9 @@ +// SPDX-License-Identifier: (LGPL-2.1 OR BSD-2-Clause) +// Copyright (c) 2021 Facebook
same
Quoted 10 lines
tools/testing/selftests/bpf/progs/strobemeta_bpf_loop.c new file +7
-1+ +#define STROBE_MAX_INTS 2 +#define STROBE_MAX_STRS 25 +#define STROBE_MAX_MAPS 100 +#define STROBE_MAX_MAP_ENTRIES 20 +#define USE_BPF_LOOP +#include "strobemeta.h" --2.30.2
PATCH v3 4/4 selftest/bpf/benchs: add bpf_loop benchmark
In reply to Joanne KoongAdd benchmark to measure the throughput and latency of the bpf_loop call.
Testing this on my dev machine on 1 thread, the data is as follows:
nr_loops: 10
bpf_loop - throughput: 198.519 ± 0.155 M ops/s, latency: 5.037 ns/op
nr_loops: 100
bpf_loop - throughput: 247.448 ± 0.305 M ops/s, latency: 4.041 ns/op
nr_loops: 500
bpf_loop - throughput: 260.839 ± 0.380 M ops/s, latency: 3.834 ns/op
nr_loops: 1000
bpf_loop - throughput: 262.806 ± 0.629 M ops/s, latency: 3.805 ns/op
nr_loops: 5000
bpf_loop - throughput: 264.211 ± 1.508 M ops/s, latency: 3.785 ns/op
nr_loops: 10000
bpf_loop - throughput: 265.366 ± 3.054 M ops/s, latency: 3.768 ns/op
nr_loops: 50000
bpf_loop - throughput: 235.986 ± 20.205 M ops/s, latency: 4.238 ns/op
nr_loops: 100000
bpf_loop - throughput: 264.482 ± 0.279 M ops/s, latency: 3.781 ns/op
nr_loops: 500000
bpf_loop - throughput: 309.773 ± 87.713 M ops/s, latency: 3.228 ns/op
nr_loops: 1000000
bpf_loop - throughput: 262.818 ± 4.143 M ops/s, latency: 3.805 ns/op
From this data, we can see that the latency per loop decreases as the number of loops increases. On this particular machine, each loop had an overhead of about ~4 ns, and we were able to run ~250 million loops per second.
--- tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/bench.c | 37 ++++++ tools/testing/selftests/bpf/bench.h | 2 + .../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/progs/bpf_loop_bench.c | 26 +++++ 7 files changed, 203 insertions(+), 1 deletion(-) 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/progs/bpf_loop_bench.c
tools/testing/selftests/bpf/Makefile +3 -1
@@ -531,6 +531,7 @@ $(OUTPUT)/bench_trigger.o: $(OUTPUT)/trigger_bench.skel.h $(OUTPUT)/bench_ringbufs.o: $(OUTPUT)/ringbuf_bench.skel.h \ $(OUTPUT)/perfbuf_bench.skel.h $(OUTPUT)/bench_bloom_filter_map.o: $(OUTPUT)/bloom_filter_bench.skel.h +$(OUTPUT)/bench_bpf_loop.o: $(OUTPUT)/bpf_loop_bench.skel.h $(OUTPUT)/bench.o: bench.h testing_helpers.h $(BPFOBJ) $(OUTPUT)/bench: LDLIBS += -lm $(OUTPUT)/bench: $(OUTPUT)/bench.o \
@@ -540,7 +541,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_rename.o \ $(OUTPUT)/bench_trigger.o \ $(OUTPUT)/bench_ringbufs.o \ - $(OUTPUT)/bench_bloom_filter_map.o + $(OUTPUT)/bench_bloom_filter_map.o \ + $(OUTPUT)/bench_bpf_loop.o $(call msg,BINARY,,$@) $(Q)$(CC) $(LDFLAGS) $(filter %.a %.o,$^) $(LDLIBS) -o $@
tools/testing/selftests/bpf/bench.c +37 -0
@@ -134,6 +134,39 @@ void hits_drops_report_final(struct bench_res res[], int res_cnt) total_ops_mean, total_ops_stddev); } +void ops_report_progress (int iter,struct bench_res *res,long delta_ns) +{ +double hits_per_sec, hits_per_prod; + + hits_per_sec = res->hits /1000000.0 / (delta_ns /1000000000.0 ); + hits_per_prod = hits_per_sec / env.producer_cnt; + +printf ("Iter %3d (%7.3lfus): " , iter, (delta_ns -1000000000 ) /1000.0 ); + +printf ("hits %8.3lfM/s (%7.3lfM/prod)\n" , hits_per_sec, hits_per_prod); +} + +void ops_report_final (struct bench_res res[],int res_cnt) +{ +double hits_mean =0.0 , hits_stddev =0.0 ; +int i; + +for (i =0 ; i < res_cnt; i++) + hits_mean += res[i].hits /1000000.0 / (0.0 + res_cnt); + +if (res_cnt >1 ) { +for (i =0 ; i < res_cnt; i++) + hits_stddev += (hits_mean - res[i].hits /1000000.0 ) * + (hits_mean - res[i].hits /1000000.0 ) / + (res_cnt -1.0 ); + + hits_stddev =sqrt (hits_stddev); + } +printf ("Summary: throughput %8.3lf \u00B1 %5.3lf M ops/s (%7.3lfM ops/prod), " , + hits_mean, hits_stddev, hits_mean / env.producer_cnt); +printf ("latency %8.3lf ns/op\n" ,1000.0 / hits_mean * env.producer_cnt); +} +const char *argp_program_version ="benchmark" ;const char *argp_program_bug_address ="<[email protected]>" ; const char argp_program_doc[] =
@@ -171,10 +204,12 @@ static const struct argp_option opts[] = {extern struct argp bench_ringbufs_argp;extern struct argp bench_bloom_map_argp; +extern struct argp bench_bpf_loop_argp;static const struct argp_child bench_parsers[] = { { &bench_ringbufs_argp,0 ,"Ring buffers benchmark" ,0 }, { &bench_bloom_map_argp,0 ,"Bloom filter map benchmark" ,0 }, + { &bench_bpf_loop_argp,0 ,"bpf_loop helper benchmark" ,0 }, {}, };
@@ -373,6 +408,7 @@ extern const struct bench bench_bloom_update;extern const struct bench bench_bloom_false_positive;extern const struct bench bench_hashmap_without_bloom;extern const struct bench bench_hashmap_with_bloom; +extern const struct bench bench_bpf_loop;static const struct bench *benchs[] = { &bench_count_global,
@@ -404,6 +440,7 @@ static const struct bench *benchs[] = { &bench_bloom_false_positive, &bench_hashmap_without_bloom, &bench_hashmap_with_bloom, + &bench_bpf_loop, };static void setup_benchmark ()
tools/testing/selftests/bpf/bench.h +2 -0
@@ -59,6 +59,8 @@ void hits_drops_report_progress(int iter, struct bench_res *res, long delta_ns);void hits_drops_report_final (struct bench_res res[],int res_cnt);void false_hits_report_progress (int iter,struct bench_res *res,long delta_ns);void false_hits_report_final (struct bench_res res[],int res_cnt); +void ops_report_progress (int iter,struct bench_res *res,long delta_ns); +void ops_report_final (struct bench_res res[],int res_cnt);static inline __u64 get_time_ns () {struct timespec t;
tools/testing/selftests/bpf/benchs/bench_bpf_loop.c new file +105 -0
105 lines not on this page · raw message
tools/testing/selftests/bpf/benchs/run_bench_bpf_loop.sh new file +15 -0
@@ -0,0 +1,15 @@ +#!/bin/bash +# SPDX-License-Identifier: GPL-2.0 + +source ./benchs/run_common.sh + +set -eufo pipefail + +for t in 1 4 8 12 16; do +for i in 1 10 100 500 1000 5000 10000 50000 100000 500000 1000000; do +subtitle "nr_loops: $i, nr_threads: $t" + summarize_ops "bpf_loop: " \ + "$($RUN_BENCH -p $t --nr_loops $i bpf-loop)" + printf "\n" +done +done
tools/testing/selftests/bpf/benchs/run_common.sh +15 -0
@@ -33,6 +33,14 @@ function percentage() echo "$*" | sed -E "s/.*Percentage\s=\s+([0-9]+\.[0-9]+).*/\1/" } +function ops() +{ + echo -n "throughput: " + echo -n "$*" | sed -E "s/.*throughput\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+\sM\sops\/s).*/\1/" + echo -n -e ", latency: " + echo "$*" | sed -E "s/.*latency\s+([0-9]+\.[0-9]+\sns\/op).*/\1/" +} + function total() { echo "$*" | sed -E "s/.*total operations\s+([0-9]+\.[0-9]+ ± [0-9]+\.[0-9]+M\/s).*/\1/"
@@ -52,6 +60,13 @@ function summarize_percentage() printf "%-20s %s%%\n" "$bench" "$(percentage $summary)" } +function summarize_ops() +{ + bench="$1" + summary=$(echo $2 | tail -n1) + printf "%-20s %s\n" "$bench" "$(ops $summary)" +} + function summarize_total() { bench="$1"
tools/testing/selftests/bpf/progs/bpf_loop_bench.c new file +26 -0
@@ -0,0 +1,26 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2021 Facebook + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> + +char _license[] SEC("license") = "GPL"; + +u32 nr_loops; +long hits; + +static int empty_callback (__u32 index,void *data) +{ +return 0 ; +} + +SEC("fentry/__x64_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 ; +}
Signature · 1 line
2.30.2
Re: [PATCH v3 bpf-next 4/4] selftest/bpf/benchs: add bpf_loop benchmark
Quoted 36 lines · Joanne Koong
Add benchmark to measure the throughput and latency of the
bpf_loopcall.Testing this on my dev machine on 1 thread, the data is as follows:
nr_loops: 10
bpf_loop- throughput: 198.519 ± 0.155 M ops/s, latency: 5.037 ns/opnr_loops: 100
bpf_loop- throughput: 247.448 ± 0.305 M ops/s, latency: 4.041 ns/opnr_loops: 500
bpf_loop- throughput: 260.839 ± 0.380 M ops/s, latency: 3.834 ns/opnr_loops: 1000
bpf_loop- throughput: 262.806 ± 0.629 M ops/s, latency: 3.805 ns/opnr_loops: 5000
bpf_loop- throughput: 264.211 ± 1.508 M ops/s, latency: 3.785 ns/opnr_loops: 10000
bpf_loop- throughput: 265.366 ± 3.054 M ops/s, latency: 3.768 ns/opnr_loops: 50000
bpf_loop- throughput: 235.986 ± 20.205 M ops/s, latency: 4.238 ns/opnr_loops: 100000
bpf_loop- throughput: 264.482 ± 0.279 M ops/s, latency: 3.781 ns/opnr_loops: 500000
bpf_loop- throughput: 309.773 ± 87.713 M ops/s, latency: 3.228 ns/opnr_loops: 1000000
bpf_loop- throughput: 262.818 ± 4.143 M ops/s, latency: 3.805 ns/op
Quoted 7 lines
From this data, we can see that the latency per loop decreases as the number of loops increases. On this particular machine, each loop had an overhead of about ~4 ns, and we were able to run ~250 million loops per second.
Signed-off-by Joanne Koong <[email protected]>---
LGTM.
Quoted 11 lines
tools/testing/selftests/bpf/Makefile | 4 +- tools/testing/selftests/bpf/bench.c | 37 ++++++ tools/testing/selftests/bpf/bench.h | 2 + .../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/progs/bpf_loop_bench.c | 26 +++++ 7 files changed, 203 insertions(+), 1 deletion(-) 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/progs/bpf_loop_bench.c
[...]
Re: [PATCH v3 bpf-next 4/4] selftest/bpf/benchs: add bpf_loop benchmark
In reply to Joanne KoongQuoted 33 lines · Joanne Koong
Add benchmark to measure the throughput and latency of the
bpf_loopcall.Testing this on my dev machine on 1 thread, the data is as follows:
nr_loops: 10
bpf_loop- throughput: 198.519 ± 0.155 M ops/s, latency: 5.037 ns/opnr_loops: 100
bpf_loop- throughput: 247.448 ± 0.305 M ops/s, latency: 4.041 ns/opnr_loops: 500
bpf_loop- throughput: 260.839 ± 0.380 M ops/s, latency: 3.834 ns/opnr_loops: 1000
bpf_loop- throughput: 262.806 ± 0.629 M ops/s, latency: 3.805 ns/opnr_loops: 5000
bpf_loop- throughput: 264.211 ± 1.508 M ops/s, latency: 3.785 ns/opnr_loops: 10000
bpf_loop- throughput: 265.366 ± 3.054 M ops/s, latency: 3.768 ns/opnr_loops: 50000
bpf_loop- throughput: 235.986 ± 20.205 M ops/s, latency: 4.238 ns/opnr_loops: 100000
bpf_loop- throughput: 264.482 ± 0.279 M ops/s, latency: 3.781 ns/opnr_loops: 500000
bpf_loop- throughput: 309.773 ± 87.713 M ops/s, latency: 3.228 ns/opnr_loops: 1000000
Quoted 8 lines
bpf_loop- throughput: 262.818 ± 4.143 M ops/s, latency: 3.805 ns/opFrom this data, we can see that the latency per loop decreases as the number of loops increases. On this particular machine, each loop had an overhead of about ~4 ns, and we were able to run ~250 million loops per second.
Signed-off-by Joanne Koong <[email protected]>