Add bpf_for_each helper
Subsystems (5)
cover Add bpf_for_each helper
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
Signature · 1 line
2.30.2
PATCH 1/3 bpf: Add bpf_for_each helper
This patch adds the kernel-side and API changes for a new helper function, bpf_for_each:
long bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);
bpf_for_each invokes the "callback_fn" nr_iterations number of times or until the callback_fn returns 1.
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_for_each (kernel/bpf/bpf_iter.c), bpf_callback_t is used as the callback function cast.
~ A program can have nested bpf_for_each calls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceed MAX_BPF_STACK))
~ The next patch will include the tests and 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 +++++++++++++++++++++++ 6 files changed, 109 insertions(+)
include/linux/bpf.h +1 -0
@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto; +extern const struct bpf_func_proto bpf_for_each_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct bpf_func_proto bpf_sk_getsockopt_proto;
include/uapi/linux/bpf.h +23 -0
@@ -4750,6 +4750,28 @@ union bpf_attr {* The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * +* long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_iterations**, 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. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the iteration. The index +* is zero-indexed. +* +* If **callback_fn** returns 0, the helper will continue to the next +* iteration. If return value is 1, the helper will skip the rest of +* the iterations and return. Other return values are not used now. +* +* Return +* The number of iterations performed, **-EINVAL** for invalid **flags** +* or a null **callback_fn**. +* * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len) * Description * Outputs a string into the **str** buffer of size **str_size**
@@ -5105,6 +5127,7 @@ union bpf_attr {FN (sock_from_file), \FN (check_mtu), \FN (for_each_map_elem), \ +FN (for_each), \FN (snprintf), \FN (sys_bpf), \ FN(btf_find_by_name_kind), \
kernel/bpf/bpf_iter.c +32 -0
@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = { .arg3_type = ARG_PTR_TO_STACK_OR_NULL, .arg4_type = ARG_ANYTHING, }; + +BPF_CALL_4(bpf_for_each, u32, nr_iterations, void *, callback_fn, void *, callback_ctx, + u64, flags) +{ +bpf_callback_t callback = (bpf_callback_t )callback_fn; +u64 err; +u32 i; + +if (flags) +return -EINVAL ; + +for (i =0 ; i < nr_iterations; i++) { + err =callback ((u64 )i, (u64 )(long )callback_ctx,0 ,0 ,0 ); +/* return value: 0 - continue, 1 - stop and return */ +if (err) { + i++; +break ; + } + } + +return i; +} + +const struct bpf_func_proto bpf_for_each_proto = { + .func = bpf_for_each, + .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_for_each: +return &bpf_for_each_proto;default :break ; }
kernel/bpf/verifier.c +28 -0
@@ -6103,6 +6103,27 @@ static int set_map_elem_callback_state(struct bpf_verifier_env *env,return 0 ; } +static int set_for_each_callback_state (struct bpf_verifier_env *env, +struct bpf_func_state *caller, +struct bpf_func_state *callee, +int insn_idx) +{ +/* bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, +* u64 flags); +* callback_fn(u32 index, void *callback_ctx); +*/ + callee->regs[BPF_REG_1 ].type =SCALAR_VALUE ; + callee->regs[BPF_REG_2 ] = caller->regs[BPF_REG_3 ]; + +/* unused */ +__mark_reg_not_init (env, &callee->regs[BPF_REG_3 ]); +__mark_reg_not_init (env, &callee->regs[BPF_REG_4 ]); +__mark_reg_not_init (env, &callee->regs[BPF_REG_5 ]); + + callee->in_callback_fn = true; +return 0 ; +} + static int set_timer_callback_state(struct bpf_verifier_env *env, struct bpf_func_state *caller, struct bpf_func_state *callee,
@@ -6482,6 +6503,13 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insnreturn -EINVAL ; } +if (func_id == BPF_FUNC_for_each) { + err =__check_func_call (env, insn, insn_idx_p, meta.subprogno, + set_for_each_callback_state); +if (err <0 ) +return -EINVAL ; + } +if (func_id == BPF_FUNC_timer_set_callback) { err =__check_func_call (env, insn, insn_idx_p, meta.subprogno, set_timer_callback_state);
tools/include/uapi/linux/bpf.h +23 -0
@@ -4750,6 +4750,28 @@ union bpf_attr {* The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * +* long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_iterations**, 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. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the iteration. The index +* is zero-indexed. +* +* If **callback_fn** returns 0, the helper will continue to the next +* iteration. If return value is 1, the helper will skip the rest of +* the iterations and return. Other return values are not used now. +* +* Return +* The number of iterations performed, **-EINVAL** for invalid **flags** +* or a null **callback_fn**. +* * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len) * Description * Outputs a string into the **str** buffer of size **str_size**
@@ -5105,6 +5127,7 @@ union bpf_attr {FN (sock_from_file), \FN (check_mtu), \FN (for_each_map_elem), \ +FN (for_each), \FN (snprintf), \FN (sys_bpf), \ FN(btf_find_by_name_kind), \
Signature · 1 line
2.30.2
Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper
Quoted 19 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_for_each:long
bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);
bpf_for_eachinvokes the "callback_fn"nr_iterationsnumber of times or until thecallback_fnreturns 1.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_for_each(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_for_eachcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ The next patch will include the tests and benchmark
Quoted 1 line
Signed-off-by Joanne Koong <[email protected]>
Great to see this! One small nit, below, but otherwise:
Quoted 36 lines
--- 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 +++++++++++++++++++++++ 6 files changed, 109 insertions(+)include/linux/bpf.h +1
-0@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto; +extern const struct bpf_func_proto bpf_for_each_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct bpf_func_proto bpf_sk_getsockopt_proto;include/uapi/linux/bpf.h +7
-0@@ -4750,6 +4750,28 @@ union bpf_attr {* The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * +* long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_iterations**, 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.
include/uapi/linux/bpf.h union bpf_attr { · line 4769
Quoted 10 lines
include/uapi/linux/bpf.h +10
-0+* Currently, the **flags** must be 0. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the iteration. The index +* is zero-indexed. +* +* If **callback_fn** returns 0, the helper will continue to the next +* iteration. If return value is 1, the helper will skip the rest of +* the iterations and return. Other return values are not used now.
The code will actually return for any non-zero value, though? So shouldn't the documentation reflect this? Or, alternatively, should the verifier enforce that the function can only return 0 or 1?
Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper
Quoted 70 lines · Toke Høiland-Jørgensen
Quoted 19 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_for_each:long
bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);
bpf_for_eachinvokes the "callback_fn"nr_iterationsnumber of times or until thecallback_fnreturns 1.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_for_each(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_for_eachcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ The next patch will include the tests and benchmarkQuoted 1 line
Signed-off-by Joanne Koong <[email protected]>Great to see this! One small nit, below, but otherwise:
Quoted 42 lines
--- 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 +++++++++++++++++++++++ 6 files changed, 109 insertions(+)include/linux/bpf.h +1
-0@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto; +extern const struct bpf_func_proto bpf_for_each_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct bpf_func_proto bpf_sk_getsockopt_proto;include/uapi/linux/bpf.h +13
-0@@ -4750,6 +4750,28 @@ union bpf_attr {* The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * +* long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_iterations**, 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. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the iteration. The index +* is zero-indexed.
Quoted 8 lines
include/uapi/linux/bpf.h union bpf_attr { · line 4769
Quoted 4 lines
include/uapi/linux/bpf.h +4
-0+* +* If **callback_fn** returns 0, the helper will continue to the next +* iteration. If return value is 1, the helper will skip the rest of +* the iterations and return. Other return values are not used now. The code will actually return for any non-zero value, though? So shouldn't the documentation reflect this? Or, alternatively, should the verifier enforce that the function can only return 0 or 1?
This is enforced in verifier.c prepare_func_exit().
if (callee->in_callback_fn) {
/* enforce R0 return value range [0, 1]. */
struct tnum range = tnum_range(0, 1);
if (r0->type != SCALAR_VALUE) {
verbose(env, "R0 not a scalar value\n");
return -EACCES;
}
if (!tnum_in(range, r0->var_off)) {
verbose_invalid_scalar(env, r0, &range,
"callback return", "R0");
return -EINVAL;
}
}Quoted 1 line
Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper
Quoted 82 lines · Yonghong Song
Quoted 70 lines · Toke Høiland-Jørgensen
Quoted 19 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_for_each:long
bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);
bpf_for_eachinvokes the "callback_fn"nr_iterationsnumber of times or until thecallback_fnreturns 1.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_for_each(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_for_eachcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ The next patch will include the tests and benchmarkQuoted 1 line
Signed-off-by Joanne Koong <[email protected]>Great to see this! One small nit, below, but otherwise:
Quoted 42 lines
--- 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 +++++++++++++++++++++++ 6 files changed, 109 insertions(+)include/linux/bpf.h +1
-0@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto; +extern const struct bpf_func_proto bpf_for_each_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct bpf_func_proto bpf_sk_getsockopt_proto;include/uapi/linux/bpf.h +13
-0@@ -4750,6 +4750,28 @@ union bpf_attr {* The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * +* long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_iterations**, 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. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the iteration. The index +* is zero-indexed. Quoted 8 lines
include/uapi/linux/bpf.h union bpf_attr { · line 4769
Quoted 4 lines
include/uapi/linux/bpf.h +4
-0+* +* If **callback_fn** returns 0, the helper will continue to the next +* iteration. If return value is 1, the helper will skip the rest of +* the iterations and return. Other return values are not used now. The code will actually return for any non-zero value, though? So shouldn't the documentation reflect this? Or, alternatively, should the verifier enforce that the function can only return 0 or 1?
This is enforced in
verifier.cprepare_func_exit().
Quoted 14 lines
if (callee->in_callback_fn) {
/* enforce R0 return value range [0, 1]. */
struct tnum range = tnum_range(0, 1);
if (r0->type != SCALAR_VALUE) {
verbose(env, "R0 not a scalar value\n");
return -EACCES;
}
if (!tnum_in(range, r0->var_off)) {
verbose_invalid_scalar(env, r0, &range,
"callback return", "R0");
return -EINVAL;
}
}Ah, right! I went looking for this but couldn't find it - thanks for the pointer!
-Toke
Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper
In reply to Joanne KoongQuoted 60 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_for_each:long
bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);
bpf_for_eachinvokes the "callback_fn"nr_iterationsnumber of times or until thecallback_fnreturns 1.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_for_each(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_for_eachcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ The next patch will include the tests and benchmarkSigned-off-by Joanne Koong <[email protected]>--- 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 +++++++++++++++++++++++ 6 files changed, 109 insertions(+)include/linux/bpf.h +1
-0@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto; +extern const struct bpf_func_proto bpf_for_each_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct bpf_func_proto bpf_sk_getsockopt_proto;include/uapi/linux/bpf.h +11
-0@@ -4750,6 +4750,28 @@ union bpf_attr {* The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * +* long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_iterations**, 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. +* +* long (\*callback_fn)(u32 index, void \*ctx); +*
include/uapi/linux/bpf.h union bpf_attr { · line 4773
Quoted 10 lines
include/uapi/linux/bpf.h +10
-0+* where **index** is the current index in the iteration. The index +* is zero-indexed. +* +* If **callback_fn** returns 0, the helper will continue to the next +* iteration. If return value is 1, the helper will skip the rest of +* the iterations and return. Other return values are not used now. +* +* Return +* The number of iterations performed, **-EINVAL** for invalid **flags** +* or a null **callback_fn**.
I think verifier enforced non-null callback_fn, right?
include/uapi/linux/bpf.h union bpf_attr { · line 5130
Quoted 9 lines
include/uapi/linux/bpf.h +2
-0+* * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len) * Description * Outputs a string into the **str** buffer of size **str_size** @@ -5105,6 +5127,7 @@ union bpf_attr {FN (sock_from_file), \FN (check_mtu), \FN (for_each_map_elem), \ + FN(for_each), \
Please put for_each helper at the end of list. Otherwise, it will break uapi.
Quoted 12 lines
include/uapi/linux/bpf.h +0
-0FN (snprintf), \FN (sys_bpf), \ FN(btf_find_by_name_kind), \kernel/bpf/bpf_iter.c +1
-0@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = { .arg3_type = ARG_PTR_TO_STACK_OR_NULL, .arg4_type = ARG_ANYTHING, }; +
[...]
Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper
Quoted 75 lines · Yonghong Song
Quoted 72 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_for_each:long
bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);
bpf_for_eachinvokes the "callback_fn"nr_iterationsnumber of times or until thecallback_fnreturns 1.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_for_each(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_for_eachcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ The next patch will include the tests and benchmarkSigned-off-by Joanne Koong <[email protected]>---
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 +++++++++++++++++++++++6 files changed, 109 insertions(+)include/linux/bpf.h +1
-0@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto; extern const struct bpf_func_proto bpf_task_storage_get_proto; extern const struct bpf_func_proto bpf_task_storage_delete_proto; extern const struct bpf_func_proto bpf_for_each_map_elem_proto; +extern const struct bpf_func_proto bpf_for_each_proto; extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto; extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct
bpf_func_protobpf_sk_getsockopt_proto;include/uapi/linux/bpf.h +7
-0@@ -4750,6 +4750,28 @@ union bpf_attr { * The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * + * long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) + * Description + * For **nr_iterations**, 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 thehelper.
+ * Currently, the **flags** must be 0.
+ *
+ * long (\*callback_fn)(u32 index, void \*ctx);
+ *
+ * where **index** is the current index in the iteration. The index
+ * is zero-indexed.
+ *
+ * If **callback_fn** returns 0, the helper will continue to the next
+ * iteration. If return value is 1, the helper will skip the rest of
+ * the iterations and return. Other return values are not
Quoted 9 lines
Quoted 6 lines
used now.
+ *
+ * Return
+ * The number of iterations performed, **-EINVAL** for invalid **flags**
+ * or a null **callback_fn**.I think verifier enforced non-null
callback_fn, right?
Yes, great point - I will remove the "or a null **callback_fn**" part.
Quoted 12 lines
include/uapi/linux/bpf.h union bpf_attr { · line 5130
Quoted 9 lines
+ *
* longbpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len)* Description
* Outputs a string into the **str** buffer of size **str_size**include/uapi/linux/bpf.h +1
-0@@ -5105,6 +5127,7 @@ union bpf_attr { FN(sock_from_file), \ FN(check_mtu), \ FN(for_each_map_elem), \ + FN(for_each), \Please put
for_eachhelper at the end of list. Otherwise, it will break uapi.
Gotcha. I will make this change for v2 and remember to do this in the future as well!
Quoted 14 lines
Quoted 13 lines
include/uapi/linux/bpf.h +0
-0FN(snprintf), \ FN(sys_bpf), \ FN(btf_find_by_name_kind), \kernel/bpf/bpf_iter.c +0
-0@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = { .arg3_type = ARG_PTR_TO_STACK_OR_NULL, .arg4_type = ARG_ANYTHING,};
+[...]
Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper
In reply to Joanne KoongQuoted 6 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_for_each:long
bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);
foreach in other languages are usually used when you are iterating elements of some data structure or stream of data, so the naming feels slightly off. bpf_loop() for bpf_for_range() seems to be more directly pointing to what's going on. My 2 cents, it's subjective, of course.
Quoted 3 lines
bpf_for_eachinvokes the "callback_fn"nr_iterationsnumber of times or until thecallback_fnreturns 1.
As Toke mentioned, we don't really check 1. Enforcing it on verifier side is just going to cause more troubles for users and doesn't seem important. I can see two ways to define the semantics, with error propagation and without.
For error propagation, we can define:
- >0, break and return number of iterations performed in total;
- 0, continue to next iteration, if no more iterations, return
number of iterations performed;
- <0, break and return that error value (but no way to know at which
iteration this happened, except through custom context);
Or we can make it simpler and just:
- 0, continue;
- != 0, break;
- always return number of iterations performed.
No strong preferences on my side, I see benefits to both ways.
Quoted 67 lines
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_for_each(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_for_eachcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ The next patch will include the tests and benchmarkSigned-off-by Joanne Koong <[email protected]>--- 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 +++++++++++++++++++++++ 6 files changed, 109 insertions(+)include/linux/bpf.h +1
-0@@ -2107,6 +2107,7 @@ extern const struct bpf_func_proto bpf_get_socket_ptr_cookie_proto;extern const struct bpf_func_proto bpf_task_storage_get_proto;extern const struct bpf_func_proto bpf_task_storage_delete_proto;extern const struct bpf_func_proto bpf_for_each_map_elem_proto; +extern const struct bpf_func_proto bpf_for_each_proto;extern const struct bpf_func_proto bpf_btf_find_by_name_kind_proto;extern const struct bpf_func_proto bpf_sk_setsockopt_proto;extern const struct bpf_func_proto bpf_sk_getsockopt_proto;include/uapi/linux/bpf.h +22
-0@@ -4750,6 +4750,28 @@ union bpf_attr {* The number of traversed map elements for success, **-EINVAL** for * invalid **flags**. * +* long bpf_for_each(u32 nr_iterations, void *callback_fn, void *callback_ctx, u64 flags) +* Description +* For **nr_iterations**, 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. +* +* long (\*callback_fn)(u32 index, void \*ctx); +* +* where **index** is the current index in the iteration. The index +* is zero-indexed. +* +* If **callback_fn** returns 0, the helper will continue to the next +* iteration. If return value is 1, the helper will skip the rest of +* the iterations and return. Other return values are not used now. +* +* Return +* The number of iterations performed, **-EINVAL** for invalid **flags** +* or a null **callback_fn**. +* * long bpf_snprintf(char *str, u32 str_size, const char *fmt, u64 *data, u32 data_len) * Description * Outputs a string into the **str** buffer of size **str_size**
include/uapi/linux/bpf.h union bpf_attr { · line 5130
Quoted 4 lines
include/uapi/linux/bpf.h +1
-0@@ -5105,6 +5127,7 @@ union bpf_attr {FN (sock_from_file), \FN (check_mtu), \FN (for_each_map_elem), \ + FN(for_each), \
you can't change the order of the function definitions, this breaks ABI, please add it at the end
Quoted 9 lines
include/uapi/linux/bpf.h +0
-0FN (snprintf), \FN (sys_bpf), \ FN(btf_find_by_name_kind), \kernel/bpf/bpf_iter.c +0
-0@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = { .arg3_type = ARG_PTR_TO_STACK_OR_NULL,
kernel/bpf/bpf_iter.c const struct bpf_func_proto bpf_for_each_map_elem_proto = { · line 724
Quoted 10 lines
kernel/bpf/bpf_iter.c +8
-0.arg4_type = ARG_ANYTHING, }; + +BPF_CALL_4(bpf_for_each, u32, nr_iterations, void *, callback_fn, void *, callback_ctx, + u64, flags) +{ +bpf_callback_t callback = (bpf_callback_t )callback_fn; +u64 err; +u32 i; +
I wonder if we should have some high but reasonable number of iteration limits. It would be too easy for users to cause some overflow and not notice it, and then pass 4bln iterations and freeze the kernel. I think limiting to something like 1mln or 8mln might be ok. Thoughts?
kernel/bpf/bpf_iter.c const struct bpf_func_proto bpf_for_each_map_elem_proto = { · line 731
Quoted 7 lines
kernel/bpf/bpf_iter.c +7
-0+if (flags) +return -EINVAL ; + +for (i =0 ; i < nr_iterations; i++) { + err =callback ((u64 )i, (u64 )(long )callback_ctx,0 ,0 ,0 ); +/* return value: 0 - continue, 1 - stop and return */ +if (err) {
nit: not really error (at least in the current semantics), "ret" would be more appropriate
Quoted 8 lines
kernel/bpf/bpf_iter.c +8
-0+ i++; +break ; + } + } + +return i; +} +
[...]
Quoted 4 lines
static int set_timer_callback_state(struct
bpf_verifier_env*env,
structbpf_func_state*caller, structbpf_func_state*callee,
kernel/bpf/bpf_iter.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 6512
Quoted 10 lines
kernel/bpf/bpf_iter.c +7
-0@@ -6482,6 +6503,13 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insnreturn -EINVAL ; } +if (func_id == BPF_FUNC_for_each) { + err =__check_func_call (env, insn, insn_idx_p, meta.subprogno, + set_for_each_callback_state); +if (err <0 ) +return -EINVAL ; + } +
we should convert these ifs (they are not even if elses!) into a switch. And move if (err < 0) return err; outside. It will only keep growing.
Quoted 3 lines
kernel/bpf/bpf_iter.c +0
-0if (func_id == BPF_FUNC_timer_set_callback) { err =__check_func_call (env, insn, insn_idx_p, meta.subprogno, set_timer_callback_state);
[...]
A message that is not in the archive (sent off-list or not yet received): [email protected]
Re: [PATCH bpf-next 1/3] bpf: Add bpf_for_each helper
Quoted 123 lines · Joanne Koong
Quoted 11 lines · Andrii Nakryiko
Quoted 5 lines · Joanne Koong
This patch adds the kernel-side and API changes for a new helper function,
bpf_for_each:long
bpf_for_each(u32 nr_interations, void *callback_fn, void *callback_ctx, u64 flags);foreach in other languages are usually used when you are iterating elements of some data structure or stream of data, so the naming feels slightly off.
bpf_loop()forbpf_for_range()seems to be more directly pointing to what's going on. My 2 cents, it's subjective, of course.Ooh, I really like "
bpf_loop()"! I will change it to this for v2.Quoted 14 lines
Quoted 2 lines
bpf_for_eachinvokes the "callback_fn"nr_iterationsnumber of times or until thecallback_fnreturns 1.As Toke mentioned, we don't really check 1. Enforcing it on verifier side is just going to cause more troubles for users and doesn't seem important. I can see two ways to define the semantics, with error propagation and without.
For error propagation, we can define:
- >0, break and return number of iterations performed in total;
- 0, continue to next iteration, if no more iterations, return
number of iterations performed;
- <0, break and return that error value (but no way to know at which
iteration this happened, except through custom context);Quoted 7 lines
Or we can make it simpler and just:
- 0, continue;
- != 0, break;
- always return number of iterations performed.No strong preferences on my side, I see benefits to both ways.
This is already enforced in the verifier (as Yonghong mentioned as well) in
prepare_func_exit()-if (callee->in_callback_fn) { /* enforce R0 return value range [0, 1]. */ struct tnum range = tnum_range(0, 1); if (r0->type != SCALAR_VALUE) { verbose(env, "R0 not a scalar value\n"); return -EACCES; } if (!tnum_in(range, r0->var_off)) { verbose_invalid_scalar(env, r0, &range, "callback return", "R0"); return -EINVAL; } }The verifier enforces that at callback return, the R0 register is always 0 or 1
Quoted 20 lines
Quoted 20 lines
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_for_each(kernel/bpf/bpf_iter.c),bpf_callback_tis used as the callback function cast.
~ A program can have nestedbpf_for_eachcalls but the program must still adhere to the verifier constraint of its stack depth (the stack depth cannot exceedMAX_BPF_STACK))
~ The next patch will include the tests and benchmarkSigned-off-by Joanne Koong<[email protected]>--- 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 +++++++++++++++++++++++ 6 files changed, 109 insertions(+)[...]
Quoted 13 lines
Quoted 13 lines
kernel/bpf/bpf_iter.c +5
-0@@ -714,3 +714,35 @@ const struct bpf_func_proto bpf_for_each_map_elem_proto = { .arg3_type = ARG_PTR_TO_STACK_OR_NULL, .arg4_type = ARG_ANYTHING, }; + +BPF_CALL_4(bpf_for_each, u32, nr_iterations, void *, callback_fn, void *, callback_ctx, + u64, flags) +{ +bpf_callback_t callback = (bpf_callback_t )callback_fn;Quoted 9 lines
kernel/bpf/bpf_iter.c const struct bpf_func_proto bpf_for_each_map_elem_proto = { · line 724
Quoted 3 lines
kernel/bpf/bpf_iter.c +3
-0+u64 err; +u32 i; +I wonder if we should have some high but reasonable number of iteration limits. It would be too easy for users to cause some overflow and not notice it, and then pass 4bln iterations and freeze the kernel. I think limiting to something like 1mln or 8mln might be ok. Thoughts?
I see the pros and cons of both. It doesn't seem that likely to me that users would accidentally pass in a negative u32 value. At the same time, I don't think limiting it to something like 1 or 8 million is unreasonable (though it might require the user to read the documentation more closely :)) - if the user wants to do more than 8 million loops then they can call the loop helper multiple times
As a user, I think I'd prefer u32 where I'd automatically know the limit is 2^32 - 1, but either approach sounds good to me!
[...]
Quoted 7 lines
Quoted 7 lines
kernel/bpf/bpf_iter.c +0
-0static int set_timer_callback_state(struct bpf_verifier_env *env, struct bpf_func_state *caller, struct bpf_func_state *callee,@@ -6482,6 +6503,13 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insnreturn -EINVAL ; }Quoted 10 lines
kernel/bpf/bpf_iter.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 6512
Quoted 7 lines
kernel/bpf/bpf_iter.c +7
-0+if (func_id == BPF_FUNC_for_each) { + err =__check_func_call (env, insn, insn_idx_p, meta.subprogno, + set_for_each_callback_state); +if (err <0 ) +return -EINVAL ; + } +we should convert these ifs (they are not even if elses!) into a switch. And move if (err < 0) return err; outside. It will only keep growing.
Quoted 2 lines
Sounds great, I will do this in v2!
Quoted 1 line
[...]
(resending this email to the vger mailing list because it didn't go through the first time)
PATCH 2/3 selftests/bpf: Add tests for bpf_for_each
In reply to Joanne KoongIn this patch -
1) Add a new prog "for_each_helper" which tests the basic functionality of the bpf_for_each helper.
2) Add pyperf600_foreach and strobemeta_foreach to test the performance of using bpf_for_each instead of a for loop
The results of pyperf600 and strobemeta are as follows:
~strobemeta~
Baseline
verification time 6808200 usec
stack depth 496
processed 592132 insns (limit 1000000) max_states_per_insn 14 total_states 16018 peak_states 13684 mark_read 3132 #188 verif_scale_strobemeta:OK (unrolled loop)
Using bpf_for_each
verification time 31589 usec
stack depth 96+408
processed 1630 insns (limit 1000000) max_states_per_insn 4 total_states 107 peak_states 107 mark_read 60 #189 verif_scale_strobemeta_foreach: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_for_each
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_foreach:OKUsing the bpf_for_each helper led to approximately a 100% decrease in the verification time and in the number of instructions.
--- .../bpf/prog_tests/bpf_verif_scale.c | 12 +++ .../selftests/bpf/prog_tests/for_each.c | 61 ++++++++++++++++ .../selftests/bpf/progs/for_each_helper.c | 69 ++++++++++++++++++ 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 +++ 7 files changed, 295 insertions(+), 4 deletions(-) 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
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_foreach (void ) +{ +/* use the bpf_for_each helper*/ +scale_test ("pyperf600_foreach.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_foreach (void ) +{ +/* use the bpf_for_each helper*/ +scale_test ("strobemeta_foreach.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); +} +void test_verif_scale_strobemeta_nounroll1 () {/* no unroll, tiny loops */
tools/testing/selftests/bpf/prog_tests/for_each.c +61 -0
77 lines not on this page · raw message
tools/testing/selftests/bpf/progs/for_each_helper.c new file +69 -0
69 lines not on this page · raw message
tools/testing/selftests/bpf/progs/pyperf.h +69 -1
92 lines not on this page · raw message
tools/testing/selftests/bpf/progs/pyperf600_foreach.c new file +5 -0
@@ -0,0 +1,5 @@ +// SPDX-License-Identifier: GPL-2.0 +// Copyright (c) 2021 Facebook +#define STACK_MAX_LEN 600 +#define USE_FOREACH +#include "pyperf.h"
tools/testing/selftests/bpf/progs/strobemeta.h +70 -3
104 lines not on this page · raw message
tools/testing/selftests/bpf/progs/strobemeta_foreach.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_FOREACH +#include "strobemeta.h"
Signature · 1 line
2.30.2
Re: [PATCH bpf-next 2/3] selftests/bpf: Add tests for bpf_for_each
Quoted 29 lines · Joanne Koong
In this patch -
1) Add a new prog "for_each_helper" which tests the basic functionality of thebpf_for_eachhelper.2) Add
pyperf600_foreachandstrobemeta_foreachto test the performance of usingbpf_for_eachinstead of a for loopThe results of pyperf600 and strobemeta are as follows:
~strobemeta~
Baseline
verification time 6808200 usec
stack depth 496
processed 592132 insns (limit 1000000)max_states_per_insn14total_states16018peak_states13684mark_read3132 #188 verif_scale_strobemeta:OK (unrolled loop)Using
bpf_for_each
verification time 31589 usec
stack depth 96+408
processed 1630 insns (limit 1000000)max_states_per_insn4total_states107peak_states107mark_read60 #189 verif_scale_strobemeta_foreach:OK~pyperf600~
Baseline
Quoted 8 lines
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_for_each
verification time 148488 usec
200x, this is awesome
Quoted 9 lines
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_foreach:OKUsing the
bpf_for_eachhelper led to approximately a 100% decrease in the verification time and in the number of instructions.Signed-off-by Joanne Koong <[email protected]>
Quoted 8 lines
--- .../bpf/prog_tests/bpf_verif_scale.c | 12 +++ .../selftests/bpf/prog_tests/for_each.c | 61 ++++++++++++++++ .../selftests/bpf/progs/for_each_helper.c | 69 ++++++++++++++++++ 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 +++
let's split out strobemeta and pyperf refactorings into a separate patch from dedicated tests for bpf_for_each helper, they are logically quite different and independent
Quoted 56 lines
7 files changed, 295 insertions(+), 4 deletions(-) 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.ctools/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_foreach (void ) +{ +/* use the bpf_for_each helper*/ +scale_test ("pyperf600_foreach.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_foreach (void ) +{ +/* use the bpf_for_each helper*/ +scale_test ("strobemeta_foreach.o" ,BPF_PROG_TYPE_RAW_TRACEPOINT , false); +} +void test_verif_scale_strobemeta_nounroll1 () {/* no unroll, tiny loops */ tools/testing/selftests/bpf/prog_tests/for_each.c +6
-0@@ -4,6 +4,7 @@#include <network_helpers.h> #include "for_each_hash_map_elem.skel.h" #include "for_each_array_map_elem.skel.h" +#include "for_each_helper.skel.h" static unsigned int duration;@@ -121,10 +122,70 @@ static void test_array_map(void)for_each_array_map_elem__destroy (skel); } +static void test_for_each_helper (void ) +{ +struct for_each_helper *skel; +__u32 retval; +int err;
tools/testing/selftests/bpf/prog_tests/for_each.c static void test_array_map(void) · line 139
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +10
-0+ + skel =for_each_helper__open_and_load (); +if (!ASSERT_OK_PTR (skel,"for_each_helper__open_and_load" )) +return ; + + skel->bss->nr_iterations =100 ; + err =bpf_prog_test_run (bpf_program__fd (skel->progs.test_prog), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); + if (CHECK(err || retval, "bpf_for_each helper test_prog",
please don't use CHECK() in new test, stick to ASSERT_XXX()
Quoted 41 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +41
-0+ "err %d errno %d retval %d\n", err, errno, retval)) + goto out; +ASSERT_EQ (skel->bss->nr_iterations_completed, skel->bss->nr_iterations, +"nr_iterations mismatch" ); +ASSERT_EQ (skel->bss->g_output, (100 *99 ) /2 ,"wrong output" ); + +/* test callback_fn returning 1 to stop iteration */ + skel->bss->nr_iterations =400 ; + skel->data->stop_index =50 ; + err =bpf_prog_test_run (bpf_program__fd (skel->progs.test_prog), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (CHECK (err || retval,"bpf_for_each helper test_prog" , +"err %d errno %d retval %d\n" , err, errno, retval)) + goto out; +ASSERT_EQ (skel->bss->nr_iterations_completed, skel->data->stop_index +1 , +"stop_index not followed" ); +ASSERT_EQ (skel->bss->g_output, (50 *49 ) /2 ,"wrong output" ); + +/* test passing in a null ctx */ + skel->bss->nr_iterations =10 ; + err =bpf_prog_test_run (bpf_program__fd (skel->progs.prog_null_ctx), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (CHECK (err || retval,"bpf_for_each helper prog_null_ctx" , +"err %d errno %d retval %d\n" , err, errno, retval)) + goto out; +ASSERT_EQ (skel->bss->nr_iterations_completed, skel->bss->nr_iterations, +"nr_iterations mismatch" ); + +/* test invalid flags */ + err =bpf_prog_test_run (bpf_program__fd (skel->progs.prog_invalid_flags), +1 , &pkt_v4,sizeof (pkt_v4),NULL ,NULL , + &retval, &duration); +if (CHECK (err || retval,"bpf_for_each helper prog_invalid_flags" , +"err %d errno %d retval %d\n" , err, errno, retval)) + goto out; +ASSERT_EQ (skel->bss->err, -EINVAL ,"invalid_flags" ); + +out: +for_each_helper__destroy (skel);
tools/testing/selftests/bpf/prog_tests/for_each.c static void test_array_map(void) · line 190
Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +4
-0+} +void test_for_each (void ) {if (test__start_subtest ("hash_map" ))test_hash_map ();if (test__start_subtest ("array_map" ))test_array_map (); +if (test__start_subtest ("for_each_helper" )) + test_for_each_helper();
those hash_map and array_map are conceptually very different tests, it's probably best to have a separate file under prog_tests dedicated to this new helper.
Quoted 66 lines
tools/testing/selftests/bpf/prog_tests/for_each.c +0
-0}tools/testing/selftests/bpf/progs/for_each_helper.c new file +59
-0@@ -0,0 +1,69 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2021 Facebook */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> + +char _license[] SEC("license") = "GPL"; + +struct callback_ctx { +int output; +}; + +/* This should be set by the user program */ +u32 nr_iterations; +u32 stop_index =-1 ; + +/* Making these global variables so that the userspace program +* can verify the output through the skeleton +*/ +int nr_iterations_completed; +int g_output; +int err; + +static int callback_fn (__u32 index,void *data) +{ +struct callback_ctx *ctx = data; + +if (index >= stop_index) +return 1 ; + + ctx->output += index; + +return 0 ; +} + +static int empty_callback_fn (__u32 index,void *data) +{ +return 0 ; +} + +SEC("tc") +int test_prog (struct __sk_buff *skb) +{ +struct callback_ctx data = {}; + + nr_iterations_completed =bpf_for_each (nr_iterations, callback_fn, &data,0 ); + + g_output = data.output; + +return 0 ; +} + +SEC("tc") +int prog_null_ctx (struct __sk_buff *skb) +{ + nr_iterations_completed =bpf_for_each (nr_iterations, empty_callback_fn,NULL ,0 ); + +return 0 ; +}
tools/testing/selftests/bpf/progs/for_each_helper.c line 69
Quoted 10 lines
tools/testing/selftests/bpf/progs/for_each_helper.c new file +10
-0+ +SEC("tc") +int prog_invalid_flags (struct __sk_buff *skb) +{ +struct callback_ctx data = {}; + + err =bpf_for_each (nr_iterations, callback_fn, &data,1 ); + +return 0 ; +}
You mentioned that nested loops works, let's have a test for that.
[...]
PATCH 3/3 selftest/bpf/benchs: add bpf_for_each benchmark
In reply to Joanne KoongAdd benchmark to measure the overhead of the bpf_for_each call for a specified number of iterations.
Testing this on qemu on my dev machine on 1 thread, the data is as follows:
nr_iterations: 1bpf_for_each helper - total callbacks called: 42.949 ± 1.404M/s
nr_iterations: 10bpf_for_each helper - total callbacks called: 73.645 ± 2.077M/s
nr_iterations: 100
bpf_for_each helper - total callbacks called: 73.058 ± 1.256M/s
nr_iterations: 500
bpf_for_each helper - total callbacks called: 78.255 ± 2.845M/s
nr_iterations: 1000
bpf_for_each helper - total callbacks called: 79.439 ± 1.805M/s
nr_iterations: 5000
bpf_for_each helper - total callbacks called: 81.639 ± 2.053M/s
nr_iterations: 10000
bpf_for_each helper - total callbacks called: 80.577 ± 1.824M/s
nr_iterations: 50000
bpf_for_each helper - total callbacks called: 76.773 ± 1.578M/s
nr_iterations: 100000
bpf_for_each helper - total callbacks called: 77.073 ± 2.200M/s
nr_iterations: 500000
bpf_for_each helper - total callbacks called: 75.136 ± 0.552M/s
nr_iterations: 1000000
bpf_for_each helper - total callbacks called: 76.364 ± 1.690M/s
From this data, we can see that we are able to run the loop at least 40 million times per second on an empty callback function.
From this data, we can also see that as the number of iterations increases, the overhead per iteration decreases and steadies towards a constant value.
--- 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 +++ .../selftests/bpf/progs/for_each_helper.c | 13 +++ 5 files changed, 140 insertions(+), 1 deletion(-) 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
tools/testing/selftests/bpf/Makefile +2 -1
@@ -537,7 +537,8 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o $(OUTPUT)/testing_helpers.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_for_each.o $(call msg,BINARY,,$@) $(Q)$(CC) $(LDFLAGS) -o $@ $(filter %.a %.o,$^) $(LDLIBS)
tools/testing/selftests/bpf/bench.c +4 -0
@@ -171,10 +171,12 @@ static const struct argp_option opts[] = {extern struct argp bench_ringbufs_argp;extern struct argp bench_bloom_map_argp; +extern struct argp bench_for_each_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_for_each_argp,0 ,"bpf_for_each helper benchmark" ,0 }, {}, };
@@ -368,6 +370,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_for_each_helper;static const struct bench *benchs[] = { &bench_count_global,
@@ -394,6 +397,7 @@ static const struct bench *benchs[] = { &bench_bloom_false_positive, &bench_hashmap_without_bloom, &bench_hashmap_with_bloom, + &bench_for_each_helper, };static void setup_benchmark ()
tools/testing/selftests/bpf/benchs/bench_for_each.c new file +105 -0
105 lines not on this page · raw message
tools/testing/selftests/bpf/benchs/run_bench_for_each.sh new file +16 -0
@@ -0,0 +1,16 @@ +#!/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 +printf "\n" +for i in 1 10 100 500 1000 5000 10000 50000 100000 500000 1000000; do +subtitle "nr_iterations: $i, nr_threads: $t" + summarize "bpf_for_each helper - total callbacks called: " \ + "$($RUN_BENCH -p $t --nr_iters $i for-each-helper)" + printf "\n" +done +done
tools/testing/selftests/bpf/progs/for_each_helper.c +13 -0
@@ -14,6 +14,8 @@ struct callback_ctx {u32 nr_iterations;u32 stop_index =-1 ; +long hits; +/* Making these global variables so that the userspace program * can verify the output through the skeleton */
@@ -67,3 +69,14 @@ int prog_invalid_flags(struct __sk_buff *skb)return 0 ; } + +SEC("fentry/__x64_sys_getpgid") +int benchmark (void *ctx) +{ +for (int i =0 ; i <1000 ; i++) { +bpf_for_each (nr_iterations, empty_callback_fn,NULL ,0 ); + +__sync_add_and_fetch (&hits, nr_iterations); + } +return 0 ; +}
Signature · 1 line
2.30.2
Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark
Quoted 5 lines · Joanne Koong
Add benchmark to measure the overhead of the
bpf_for_eachcall for a specified number of iterations.Testing this on qemu on my dev machine on 1 thread, the data is as follows:
Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?
-Toke
Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark
Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong
Add benchmark to measure the overhead of the
bpf_for_eachcall for a specified number of iterations.
Quoted 8 lines
Quoted 2 lines
Testing this on qemu on my dev machine on 1 thread, the data is as follows:
Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?
Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of bpf_for_each() helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.
But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.
And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.
I read those numbers as "plenty fast" :)
Quoted 3 lines
-Toke
Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark
Quoted 28 lines · Andrii Nakryiko
Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong
Add benchmark to measure the overhead of the
bpf_for_eachcall for a specified number of iterations.Quoted 8 lines
Quoted 2 lines
Testing this on qemu on my dev machine on 1 thread, the data is as follows:
Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?
Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of
bpf_for_each()helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.
Quoted 6 lines
And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.
I read those numbers as "plenty fast" :)
Hmm, okay, fair enough, but I think it would be good to have the "~12 ns per iteration" figure featured prominently in the commit message, then :)
-Toke
Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark
Quoted 36 lines · Toke Høiland-Jørgensen
Quoted 33 lines · Andrii Nakryiko
Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong
Add benchmark to measure the overhead of the
bpf_for_eachcall for a specified number of iterations.Quoted 8 lines
Quoted 2 lines
Testing this on qemu on my dev machine on 1 thread, the data is as follows:
Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?
Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of
bpf_for_each()helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.
And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.
Quoted 5 lines
Quoted 1 line
I read those numbers as "plenty fast" :)
Hmm, okay, fair enough, but I think it would be good to have the "~12 ns per iteration" figure featured prominently in the commit message, then :)
We discussed with Joanne offline adding an ops_report_final() helper that will output both throughput (X ops/s) and latency/overhead ( (1000000000/X) ns/op), so that no one had to do any math.
Quoted 2 lines
-Toke
Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark
Quoted 39 lines · Andrii Nakryiko
Quoted 38 lines · Toke Høiland-Jørgensen
Quoted 34 lines · Andrii Nakryiko
Quoted 6 lines · Toke Høiland-Jørgensen
Quoted 3 lines · Joanne Koong
Add benchmark to measure the overhead of the
bpf_for_eachcall for a specified number of iterations.Quoted 8 lines
Quoted 2 lines
Testing this on qemu on my dev machine on 1 thread, the data is as follows:
Absolute numbers from some random dev machine are not terribly useful; others have no way of replicating your tests. A more meaningful benchmark would need a baseline to compare to; in this case I guess that would be a regular loop? Do you have any numbers comparing the callback to just looping?
Measuring empty for (int i = 0; i < N; i++) is meaningless, you should expect a number in billions of "operations" per second on modern server CPUs. So that will give you no idea. Those numbers are useful as a ballpark number of what's the overhead of
bpf_for_each()helper and callbacks. And 12ns per "iteration" is meaningful to have a good idea of how slow that can be. Depending on your hardware it can be different by 2x, maybe 3x, but not 100x.But measuring inc + cmp + jne as a baseline is both unrealistic and doesn't give much more extra information. But you can assume 2B/s, give or take.
And you also can run this benchmark on your own on your hardware to get "real" numbers, as much as you can expect real numbers from artificial microbenchmark, of course.
I read those numbers as "plenty fast" :)
Quoted 7 lines
Quoted 3 lines
Hmm, okay, fair enough, but I think it would be good to have the "~12 ns per iteration" figure featured prominently in the commit message, then :)
We discussed with Joanne offline adding an
ops_report_final()helper that will output both throughput (X ops/s) and latency/overhead ( (1000000000/X) ns/op), so that no one had to do any math.
Alright, sounds good, thanks!
-Toke
Re: [PATCH bpf-next 3/3] selftest/bpf/benchs: add bpf_for_each benchmark
In reply to Joanne KoongQuoted 31 lines · Joanne Koong
Add benchmark to measure the overhead of the
bpf_for_eachcall for a specified number of iterations.Testing this on qemu on my dev machine on 1 thread, the data is as follows:
nr_iterations: 1bpf_for_eachhelper - total callbacks called: 42.949 ± 1.404M/s
nr_iterations: 10bpf_for_eachhelper - total callbacks called: 73.645 ± 2.077M/snr_iterations: 100
bpf_for_eachhelper - total callbacks called: 73.058 ± 1.256M/snr_iterations: 500
bpf_for_eachhelper - total callbacks called: 78.255 ± 2.845M/snr_iterations: 1000
bpf_for_eachhelper - total callbacks called: 79.439 ± 1.805M/snr_iterations: 5000
bpf_for_eachhelper - total callbacks called: 81.639 ± 2.053M/snr_iterations: 10000
bpf_for_eachhelper - total callbacks called: 80.577 ± 1.824M/snr_iterations: 50000
bpf_for_eachhelper - total callbacks called: 76.773 ± 1.578M/s
Quoted 8 lines
nr_iterations: 100000
bpf_for_eachhelper - total callbacks called: 77.073 ± 2.200M/snr_iterations: 500000
bpf_for_eachhelper - total callbacks called: 75.136 ± 0.552M/snr_iterations: 1000000
bpf_for_eachhelper - total callbacks called: 76.364 ± 1.690M/s
bit clear why numbers go down with increased nr_iterations, I'd expect them to stabilize. Try running bench with -a argument to set CPU affinity, that usually improves stability of test results
Quoted 8 lines
From this data, we can see that we are able to run the loop at least 40 million times per second on an empty callback function.
From this data, we can also see that as the number of iterations increases, the overhead per iteration decreases and steadies towards a constant value.
Quoted 7 lines
Signed-off-by Joanne Koong <[email protected]>--- 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 +++ .../selftests/bpf/progs/for_each_helper.c | 13 +++
$ ls progs/*bench* progs/bloom_filter_bench.c progs/perfbuf_bench.c progs/ringbuf_bench.c progs/trigger_bench.c
let's keep the naming pattern
Quoted 4 lines
5 files changed, 140 insertions(+), 1 deletion(-) 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
[...]
Quoted 11 lines · Joanne Koong
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_eachhelper moves the loop logic into the kernel and can thereby guarantee that the loop will always terminate. Thebpf_for_eachhelper 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.
Quoted 5 lines
From the test results, we see that using
bpf_for_eachin 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).
Quoted 18 lines · Toke Høiland-Jørgensen
Quoted 11 lines · Joanne Koong
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_eachhelper moves the loop logic into the kernel and can thereby guarantee that the loop will always terminate. Thebpf_for_eachhelper 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.Quoted 5 lines
From the test results, we see that using
bpf_for_eachin 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.
Quoted 6 lines
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!