bpf: Inline the numeric open-coded iterator kfuncs
Subsystems (4)
v3 cover bpf: Inline the numeric open-coded iterator kfuncs
The bpf_for(i, start, end) macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs: bpf_iter_num_new() to set the iterator up, bpf_iter_num_next() once per iteration, and bpf_iter_num_destroy() to tear it down. The verifier emits these as ordinary kfunc calls, so a bpf_for() loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration via bpf_iter_num_next().
All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct bpf_iter_num_kern { int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded in bpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:
- bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same -EINVAL / -E2BIG / 0 as the kfunc.
- bpf_iter_num_next(): the hot path. Since cur and end are int, the
kfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit
comparison of (s->cur + 1) against s->end, so the inlined code uses a
32-bit compare with no sign extension. - bpf_iter_num_destroy(): a single 8-byte store zeroing the state.
bpf_for() is frequently used with constant bounds; in that case the range checks in bpf_iter_num_new() are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new __xlated selftests, and a bench_bpf_for benchmark (modeled on the existing bpf_loop benchmark) runs a bpf_for() loop with an empty body to measure the per-iteration cost.
The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no jit_required marking is needed.
Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+
| arch | bpf_loop | bpf_for non-inlined | bpf_for inlined |
+--------+---------------------+---------------------+---------------------+
| x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) |
+--------+---------------------+---------------------+---------------------+
| arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) |
+--------+---------------------+---------------------+---------------------+On x86-64, removing the per-iteration call to bpf_iter_num_next() roughly doubles bpf_for() throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.
bpf_loop() is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64 bpf_for() is faster than bpf_loop() even before inlining, while on arm64 bpf_loop() is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.
Changelog:
v2: https://lore.kernel.org/bpf/[email protected]/
Changes in v3:
- Elide the range checks in bpf_iter_num_new() when start and end are constant, marking the registers precise so paths reaching the call with different constants are not pruned (Eduard Zingerman)
- Add __xlated selftests pinning the inlined new()/next()/destroy() shapes (Eduard Zingerman)
- Use the insn_buf[i++] idiom in the inline helpers (Eduard Zingerman)
- Pick up Acked-by on patch 3
v1: https://lore.kernel.org/all/[email protected]/
Changes in v2:
- Don't emit sign-extending (movsx) moves; some JITs (e.g. x86-32, mips32, sparc64) decode them as a plain move and would miscompile the range check
Puranjay Mohan (6):
bpf: Inline bpf_iter_num_new() kfunc
bpf: Inline bpf_iter_num_next() kfunc
bpf: Inline bpf_iter_num_destroy() kfunc
bpf: Elide range checks when inlining bpf_iter_num_new() for constant
bounds
selftests/bpf: Verify inlined numeric iterator shape with __xlated selftests/bpf: Add bpf_for() benchmark
include/linux/bpf_verifier.h | 13 ++ kernel/bpf/verifier.c | 157 ++++++++++++++++++ tools/testing/selftests/bpf/Makefile | 2 + tools/testing/selftests/bpf/bench.c | 4 + .../selftests/bpf/benchs/bench_bpf_for.c | 104 ++++++++++++ .../selftests/bpf/benchs/run_bench_bpf_for.sh | 15 ++ .../selftests/bpf/progs/bpf_for_bench.c | 32 ++++ tools/testing/selftests/bpf/progs/iters.c | 145 ++++++++++++++++ 8 files changed, 472 insertions(+) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_for.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_for.sh create mode 100644 tools/testing/selftests/bpf/progs/bpf_for_bench.c
base-commit: a23a71823352e2d792dcaae25f1ebb744acbfc0b
Signature · 1 line
2.53.0-Meta
PATCH v3 1/6 bpf: Inline bpf_iter_num_new() kfunc
The numeric iterator kfuncs bpf_iter_num_{new,next,destroy}() back the open-coded iterator macro bpf_for() and are emitted as regular kfunc calls by the verifier. bpf_iter_num_new() is small and only touches the on-stack iterator state, so the verifier can open-code it and avoid the call overhead of setting up an iterator.
Inline it in bpf_fixup_kfunc_call() by replacing the call with an equivalent instruction sequence. R1 holds the pointer to the on-stack bpf_iter_num, while R2 and R3 hold the start and end arguments. The arithmetic and the error paths mirror the kfunc exactly, so a program that inspects the return value keeps observing the same -EINVAL / -E2BIG / 0 results.
The kfunc guards against overflow with a (s64)end - (s64)start range check. The start > end case is rejected first, so start <= end at that point and the range end - start fits in a u32. The inlined code computes it with a 32-bit subtraction that zero-extends into a 64-bit register and compares the result against BPF_MAX_LOOPS. Sign-extending the operands with movsx instead would emit a cpuv4 instruction after verification; JITs that do not implement movsx (e.g. x86-32, mips32, sparc64) decode it as a plain move and would miscompile the check.
The emitted instructions are plain BPF and are handled by the interpreter, so interpreter fallback stays correct and no jit_required marking is needed.
--- kernel/bpf/verifier.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+)
kernel/bpf/verifier.c +39 -0
@@ -19770,6 +19770,43 @@ static void __fixup_collection_insert_kfunc(struct bpf_insn_aux_data *insn_aux, *cnt =4 ; } +/* +* Inline bpf_iter_num_new(). R1 holds the pointer to the iterator, R2 and R3 hold the (int) +* start and end arguments. Keep in sync with the kfunc in kernel/bpf/bpf_iter.c. +*/ +static int inline_bpf_iter_num_new (struct bpf_insn *insn_buf) +{ +int i =0 ; + +/* if (start > end) goto einval; */ + insn_buf[i++] =BPF_JMP32_REG (BPF_JSGT ,BPF_REG_2 ,BPF_REG_3 ,8 ); +/* +* start <= end here, so the range end - start fits in a u32; compute it as a 32-bit +* subtraction that zero-extends into r0. +*/ + insn_buf[i++] =BPF_MOV32_REG (BPF_REG_0 ,BPF_REG_3 ); + insn_buf[i++] =BPF_ALU32_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_2 ); +/* if (r0 > BPF_MAX_LOOPS) goto e2big; */ + insn_buf[i++] =BPF_JMP_IMM (BPF_JSGT ,BPF_REG_0 ,BPF_MAX_LOOPS ,8 ); +/* s->cur = start - 1; */ + insn_buf[i++] =BPF_ALU32_IMM (BPF_ADD ,BPF_REG_2 ,-1 ); + insn_buf[i++] =BPF_STX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_2 ,0 ); +/* s->end = end; */ + insn_buf[i++] =BPF_STX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_3 ,4 ); +/* return 0; */ + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insn_buf[i++] =BPF_JMP_A (5 ); +/* einval: s->cur = s->end = 0; return -EINVAL; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 , -EINVAL ); + insn_buf[i++] =BPF_JMP_A (2 ); +/* e2big: s->cur = s->end = 0; return -E2BIG; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 , -E2BIG ); + +return i; +} +int bpf_fixup_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,struct bpf_insn *insn_buf,int insn_idx,int *cnt) {
@@ -19899,6 +19936,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, insn_buf[4 ] =BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ); insn_buf[5 ] =BPF_ALU64_IMM (BPF_NEG ,BPF_REG_0 ,0 ); *cnt =6 ; + }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_new]) { + *cnt =inline_bpf_iter_num_new (insn_buf); }if (env->insn_aux_data[insn_idx].arg_prog) {
Signature · 1 line
2.53.0-Meta
Re: [PATCH bpf-next v3 1/6] bpf: Inline bpf_iter_num_new() kfunc
Quoted 48 lines · Puranjay Mohan
The numeric iterator kfuncs bpf_iter_num_{new,next,destroy}() back the open-coded iterator macro
bpf_for()and are emitted as regular kfunc calls by the verifier.bpf_iter_num_new()is small and only touches the on-stack iterator state, so the verifier can open-code it and avoid the call overhead of setting up an iterator.Inline it in
bpf_fixup_kfunc_call()by replacing the call with an equivalent instruction sequence. R1 holds the pointer to the on-stackbpf_iter_num, while R2 and R3 hold the start and end arguments. The arithmetic and the error paths mirror the kfunc exactly, so a program that inspects the return value keeps observing the same-EINVAL/-E2BIG/ 0 results.The kfunc guards against overflow with a (s64)end - (s64)start range check. The start > end case is rejected first, so start <= end at that point and the range end - start fits in a u32. The inlined code computes it with a 32-bit subtraction that zero-extends into a 64-bit register and compares the result against
BPF_MAX_LOOPS. Sign-extending the operands with movsx instead would emit a cpuv4 instruction after verification; JITs that do not implement movsx (e.g. x86-32, mips32, sparc64) decode it as a plain move and would miscompile the check.The emitted instructions are plain BPF and are handled by the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Signed-off-by Puranjay Mohan <[email protected]>--- kernel/bpf/verifier.c | 39 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 39 insertions(+)kernel/bpf/verifier.c +8
-0@@ -19770,6 +19770,43 @@ static void __fixup_collection_insert_kfunc(struct bpf_insn_aux_data *insn_aux, *cnt =4 ; } +/* +* Inline bpf_iter_num_new(). R1 holds the pointer to the iterator, R2 and R3 hold the (int) +* start and end arguments. Keep in sync with the kfunc in kernel/bpf/bpf_iter.c. +*/ +static int inline_bpf_iter_num_new (struct bpf_insn *insn_buf) +{ +int i =0 ; +
kernel/bpf/verifier.c static void __fixup_collection_insert_kfunc(struct bpf_insn_aux_data *insn_aux, · line 19790
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+/* if (start > end) goto einval; */ + insn_buf[i++] =BPF_JMP32_REG (BPF_JSGT ,BPF_REG_2 ,BPF_REG_3 ,8 ); +/* +* start <= end here, so the range end - start fits in a u32; compute it as a 32-bit +* subtraction that zero-extends into r0. +*/ + insn_buf[i++] =BPF_MOV32_REG (BPF_REG_0 ,BPF_REG_3 ); + insn_buf[i++] =BPF_ALU32_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_2 ); +/* if (r0 > BPF_MAX_LOOPS) goto e2big; */ + insn_buf[i++] =BPF_JMP_IMM (BPF_JSGT ,BPF_REG_0 ,BPF_MAX_LOOPS ,8 );
this should be an unsigned comparison, no? Otherwise INT_MAX - INT_MIN = -1 and this check will (erroneously) pass, or am I mistaken?
pw-bot: cr
Quoted 34 lines
kernel/bpf/verifier.c +21
-1+/* s->cur = start - 1; */ + insn_buf[i++] =BPF_ALU32_IMM (BPF_ADD ,BPF_REG_2 ,-1 ); + insn_buf[i++] =BPF_STX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_2 ,0 ); +/* s->end = end; */ + insn_buf[i++] =BPF_STX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_3 ,4 ); +/* return 0; */ + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + insn_buf[i++] =BPF_JMP_A (5 ); +/* einval: s->cur = s->end = 0; return -EINVAL; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 , -EINVAL ); + insn_buf[i++] =BPF_JMP_A (2 ); +/* e2big: s->cur = s->end = 0; return -E2BIG; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 , -E2BIG ); + +return i; +} +int bpf_fixup_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,struct bpf_insn *insn_buf,int insn_idx,int *cnt) {@@ -19899,6 +19936,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, insn_buf[4 ] =BPF_ALU64_REG (BPF_SUB ,BPF_REG_0 ,BPF_REG_1 ); insn_buf[5 ] =BPF_ALU64_IMM (BPF_NEG ,BPF_REG_0 ,0 ); *cnt =6 ; + }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_new]) { + *cnt =inline_bpf_iter_num_new (insn_buf); }if (env->insn_aux_data[insn_idx].arg_prog) { --2.53.0-Meta
PATCH v3 2/6 bpf: Inline bpf_iter_num_next() kfunc
In reply to Puranjay Mohanbpf_iter_num_next() is called on every iteration of a bpf_for() loop and is the hot path of the numeric open-coded iterator. It only advances the on-stack iterator state and returns a pointer to it, so open-coding it in the verifier removes a function call from each loop iteration.
Inline it in bpf_fixup_kfunc_call() by replacing the call with an equivalent instruction sequence. R1 holds the pointer to the on-stack bpf_iter_num; the returned pointer to s->cur is R1 itself since s->cur is the first member.
s->cur and s->end are int, so the kfunc's (s64)(s->cur + 1) >= s->end test is equivalent to a signed 32-bit comparison of (s->cur + 1) against s->end: s->cur + 1 is computed as a 32-bit int in the kfunc as well, and sign-extending both sides of a comparison of two int values does not change its result. The inlined code therefore uses a 32-bit compare and needs no sign extension.
--- kernel/bpf/verifier.c | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+)
kernel/bpf/verifier.c +30 -0
@@ -19807,6 +19807,34 @@ static int inline_bpf_iter_num_new(struct bpf_insn *insn_buf)return i; } +/* +* Inline bpf_iter_num_next(). R1 holds the pointer to the iterator. Keep in sync with the +* kfunc in kernel/bpf/bpf_iter.c. +*/ +static int inline_bpf_iter_num_next (struct bpf_insn *insn_buf) +{ +int i =0 ; + +/* +* s->cur and s->end are int, so the (s64)(s->cur + 1) >= s->end check is equivalent to a +* signed 32-bit comparison of (s->cur + 1) against s->end and needs no sign extension. +*/ + insn_buf[i++] =BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ); + insn_buf[i++] =BPF_ALU32_IMM (BPF_ADD ,BPF_REG_0 ,1 ); + insn_buf[i++] =BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 ,4 ); +/* if ((s32)(s->cur + 1) >= (s32)s->end) goto done; */ + insn_buf[i++] =BPF_JMP32_REG (BPF_JSGE ,BPF_REG_0 ,BPF_REG_2 ,3 ); +/* s->cur++; return &s->cur; */ + insn_buf[i++] =BPF_STX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_0 ,0 ); + insn_buf[i++] =BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ); + insn_buf[i++] =BPF_JMP_A (2 ); +/* done: s->cur = s->end = 0; return NULL; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + +return i; +} +int bpf_fixup_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,struct bpf_insn *insn_buf,int insn_idx,int *cnt) {
@@ -19938,6 +19966,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, *cnt =6 ; }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_new]) { *cnt =inline_bpf_iter_num_new (insn_buf); + }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { + *cnt =inline_bpf_iter_num_next (insn_buf); }if (env->insn_aux_data[insn_idx].arg_prog) {
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v3 2/6] bpf: Inline bpf_iter_num_next() kfunc
The commit message explains the performance motivation for this change, but could you provide more detailed analysis about how this was determined?
Quoted 40 lines
kernel/bpf/verifier.c +28
-0@@ -19807,6 +19807,34 @@ static int inline_bpf_iter_num_new(struct bpf_insn *insn_buf)return i; } +/* +* Inline bpf_iter_num_next(). R1 holds the pointer to the iterator. Keep in sync with the +* kfunc in kernel/bpf/bpf_iter.c. +*/ +static int inline_bpf_iter_num_next (struct bpf_insn *insn_buf) +{ +int i =0 ; + +/* +* s->cur and s->end are int, so the (s64)(s->cur + 1) >= s->end check is equivalent to a +* signed 32-bit comparison of (s->cur + 1) against s->end and needs no sign extension. +*/ + insn_buf[i++] =BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ); + insn_buf[i++] =BPF_ALU32_IMM (BPF_ADD ,BPF_REG_0 ,1 ); + insn_buf[i++] =BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 ,4 ); +/* if ((s32)(s->cur + 1) >= (s32)s->end) goto done; */ + insn_buf[i++] =BPF_JMP32_REG (BPF_JSGE ,BPF_REG_0 ,BPF_REG_2 ,3 ); +/* s->cur++; return &s->cur; */ + insn_buf[i++] =BPF_STX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_0 ,0 ); + insn_buf[i++] =BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ); + insn_buf[i++] =BPF_JMP_A (2 ); +/* done: s->cur = s->end = 0; return NULL; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + +return i; +} +int bpf_fixup_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,struct bpf_insn *insn_buf,int insn_idx,int *cnt) {
kernel/bpf/verifier.c int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, · line 19973
Quoted 8 lines
kernel/bpf/verifier.c +2
-0@@ -19938,6 +19966,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, *cnt =6 ; }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_new]) { *cnt =inline_bpf_iter_num_new (insn_buf); + }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { + *cnt =inline_bpf_iter_num_next (insn_buf); }if (env->insn_aux_data[insn_idx].arg_prog) {
The commit message explains the performance motivation for this change, but could you provide more detailed analysis about how this was determined?
What perf counters or measurements were used to validate the improvement on ARM64? The explanation focuses on the theoretical benefit of removing a function call, but it would be helpful to understand the actual measured impact.
Additionally, how does this compare against can_loop in terms of overhead? Understanding the relative performance would help evaluate whether this optimization is addressing the right bottleneck.
Reference: https://lore.kernel.org/bpf/[email protected]/
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/29924758865
Re: [PATCH bpf-next v3 2/6] bpf: Inline bpf_iter_num_next() kfunc
In reply to Puranjay MohanQuoted 33 lines · Puranjay Mohan
bpf_iter_num_next()is called on every iteration of abpf_for()loop and is the hot path of the numeric open-coded iterator. It only advances the on-stack iterator state and returns a pointer to it, so open-coding it in the verifier removes a function call from each loop iteration.Inline it in
bpf_fixup_kfunc_call()by replacing the call with an equivalent instruction sequence. R1 holds the pointer to the on-stackbpf_iter_num; the returned pointer tos->curis R1 itself sinces->curis the first member.
s->curands->endare int, so the kfunc's (s64)(s->cur + 1) >=s->endtest is equivalent to a signed 32-bit comparison of (s->cur+ 1) againsts->end:s->cur+ 1 is computed as a 32-bit int in the kfunc as well, and sign-extending both sides of a comparison of two int values does not change its result. The inlined code therefore uses a 32-bit compare and needs no sign extension.Signed-off-by Puranjay Mohan <[email protected]>--- kernel/bpf/verifier.c | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+)kernel/bpf/verifier.c +2
-0@@ -19807,6 +19807,34 @@ static int inline_bpf_iter_num_new(struct bpf_insn *insn_buf)return i; } +/* +* Inline bpf_iter_num_next(). R1 holds the pointer to the iterator. Keep in sync with the
kernel/bpf/verifier.c static int inline_bpf_iter_num_new(struct bpf_insn *insn_buf) · line 19821
Quoted 10 lines
kernel/bpf/verifier.c +10
-0+* kfunc in kernel/bpf/bpf_iter.c. +*/ +static int inline_bpf_iter_num_next (struct bpf_insn *insn_buf) +{ +int i =0 ; + +/* +* s->cur and s->end are int, so the (s64)(s->cur + 1) >= s->end check is equivalent to a +* signed 32-bit comparison of (s->cur + 1) against s->end and needs no sign extension. +*/
really?.. have you checked the original code and that large comment there?
/* check failed initialization or if we are done (same behavior);
* need to be careful about overflow, so convert to s64 for checks,
* e.g., if s->cur == s->end == INT_MAX, we can't just do
* s->cur + 1 >= s->end
*/
But I don't try my own judgement, so I did this:
$ cat test.c
#include <stdio.h>
#include <limits.h>
int main() {
int s = INT_MAX;
int e = INT_MAX;
s += 1;
printf("%d %d %u\n", s, e, (_Bool)(s > e));
return 0;
}
$ cc test.c
$ ./a.out
-2147483648 2147483647 0That zero means "false", doesn't it?..
And if we don't have tests for these corner case (blame me, doh), let's please add them.
pw-bot: cr
Quoted 31 lines
kernel/bpf/verifier.c +18
-1+ insn_buf[i++] =BPF_LDX_MEM (BPF_W ,BPF_REG_0 ,BPF_REG_1 ,0 ); + insn_buf[i++] =BPF_ALU32_IMM (BPF_ADD ,BPF_REG_0 ,1 ); + insn_buf[i++] =BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 ,4 ); +/* if ((s32)(s->cur + 1) >= (s32)s->end) goto done; */ + insn_buf[i++] =BPF_JMP32_REG (BPF_JSGE ,BPF_REG_0 ,BPF_REG_2 ,3 ); +/* s->cur++; return &s->cur; */ + insn_buf[i++] =BPF_STX_MEM (BPF_W ,BPF_REG_1 ,BPF_REG_0 ,0 ); + insn_buf[i++] =BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_1 ); + insn_buf[i++] =BPF_JMP_A (2 ); +/* done: s->cur = s->end = 0; return NULL; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + +return i; +} +int bpf_fixup_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,struct bpf_insn *insn_buf,int insn_idx,int *cnt) {@@ -19938,6 +19966,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, *cnt =6 ; }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_new]) { *cnt =inline_bpf_iter_num_new (insn_buf); + }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { + *cnt =inline_bpf_iter_num_next (insn_buf); }if (env->insn_aux_data[insn_idx].arg_prog) { --2.53.0-Meta
PATCH v3 3/6 bpf: Inline bpf_iter_num_destroy() kfunc
In reply to Puranjay Mohanbpf_iter_num_destroy() only zeroes the on-stack iterator state, which is a single 8-byte store. Open-code it in the verifier to drop the call emitted at the end of every bpf_for() loop.
Inline it in bpf_fixup_kfunc_call() by replacing the call with a store of zero to the iterator, matching the kfunc which clears both s->cur and s->end. R1 holds the pointer to the on-stack bpf_iter_num.
--- kernel/bpf/verifier.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
kernel/bpf/verifier.c +16 -0
@@ -19835,6 +19835,20 @@ static int inline_bpf_iter_num_next(struct bpf_insn *insn_buf)return i; } +/* +* Inline bpf_iter_num_destroy(). R1 holds the pointer to the iterator. Keep in sync with +* the kfunc in kernel/bpf/bpf_iter.c. +*/ +static int inline_bpf_iter_num_destroy (struct bpf_insn *insn_buf) +{ +int i =0 ; + +/* s->cur = s->end = 0; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + +return i; +} +int bpf_fixup_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,struct bpf_insn *insn_buf,int insn_idx,int *cnt) {
@@ -19968,6 +19982,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, *cnt =inline_bpf_iter_num_new (insn_buf); }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { *cnt =inline_bpf_iter_num_next (insn_buf); + }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) { + *cnt =inline_bpf_iter_num_destroy (insn_buf); }if (env->insn_aux_data[insn_idx].arg_prog) {
Signature · 1 line
2.53.0-Meta
Re: [PATCH bpf-next v3 3/6] bpf: Inline bpf_iter_num_destroy() kfunc
Quoted 9 lines · Puranjay Mohan
bpf_iter_num_destroy()only zeroes the on-stack iterator state, which is a single 8-byte store. Open-code it in the verifier to drop the call emitted at the end of everybpf_for()loop.Inline it in
bpf_fixup_kfunc_call()by replacing the call with a store of zero to the iterator, matching the kfunc which clears boths->curands->end. R1 holds the pointer to the on-stackbpf_iter_num.
Quoted 6 lines
Acked-by Eduard Zingerman <[email protected]>Signed-off-by Puranjay Mohan <[email protected]>--- kernel/bpf/verifier.c | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
as I mentioned before, I don't think we should do anything in destroy, remove function call for inlining case and simplify bpf_iter_num_destroy()?
Quoted 37 lines
kernel/bpf/verifier.c +16
-1@@ -19835,6 +19835,20 @@ static int inline_bpf_iter_num_next(struct bpf_insn *insn_buf)return i; } +/* +* Inline bpf_iter_num_destroy(). R1 holds the pointer to the iterator. Keep in sync with +* the kfunc in kernel/bpf/bpf_iter.c. +*/ +static int inline_bpf_iter_num_destroy (struct bpf_insn *insn_buf) +{ +int i =0 ; + +/* s->cur = s->end = 0; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + +return i; +} +int bpf_fixup_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,struct bpf_insn *insn_buf,int insn_idx,int *cnt) {@@ -19968,6 +19982,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, *cnt =inline_bpf_iter_num_new (insn_buf); }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { *cnt =inline_bpf_iter_num_next (insn_buf); + }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) { + *cnt =inline_bpf_iter_num_destroy (insn_buf); }if (env->insn_aux_data[insn_idx].arg_prog) { --2.53.0-Meta
PATCH v3 4/6 bpf: Elide range checks when inlining bpf_iter_num_new() for constant bounds
In reply to Puranjay Mohanbpf_for() is frequently used with constant bounds, e.g. bpf_for(i, 0, N) with a literal N. In that case bpf_iter_num_new()'s start > end and range > BPF_MAX_LOOPS checks, and their error paths, are decidable at verification time and need not be emitted at all.
Record, per call site, whether both the start and end arguments are constant with the same value on every visit, mirroring the state tracking bpf_loop() inlining already does. check_kfunc_call() stores this in bpf_insn_aux_data; the multi-visit merge matters because the same call site can be reached with different constants on different paths, in which case it falls back to the general sequence.
The fold relies on the exact constant values, so the start and end registers are marked precise. Without that the verifier could prune a path reaching the call with different constants before the merge above sees it, and the folded code would run with a stale value.
When the bounds are known, inline_bpf_iter_num_new() folds the checks and emits only the reachable tail: the iterator init for a valid range, or the zeroing store plus the -EINVAL / -E2BIG result otherwise. The runtime behaviour is identical to the general sequence and to the kfunc.
--- include/linux/bpf_verifier.h | 13 ++++++ kernel/bpf/verifier.c | 76 +++++++++++++++++++++++++++++++++++- 2 files changed, 87 insertions(+), 2 deletions(-)
include/linux/bpf_verifier.h +13 -0
@@ -612,6 +612,15 @@ struct bpf_loop_inline_state {u32 callback_subprogno;/* valid when fit_for_inline is true */ }; +struct bpf_iter_num_new_state { +unsigned int initialized:1 ;/* set to true upon first entry */ +unsigned int fit_for_inline:1 ;/* true if start and end are constant +* with the same value at each call +*/ +s32 start;/* valid when fit_for_inline is true */ +s32 end;/* valid when fit_for_inline is true */ +}; +/* pointer and state for maps */ struct bpf_map_ptr_state {struct bpf_map *map_ptr;
@@ -661,6 +670,10 @@ struct bpf_insn_aux_data {* the state of the relevant registers to make decision about inlining */ struct bpf_loop_inline_state loop_inline_state; +/* if instruction is a call to bpf_iter_num_new this field tracks its start/end +* arguments to make a decision about eliding the range checks when inlining +*/ +struct bpf_iter_num_new_state iter_num_new_state; };union {/* remember the size of type passed to bpf_obj_new to rewrite R1 */
kernel/bpf/verifier.c +74 -2
103 lines not on this page · raw message
Signature · 1 line
2.53.0-Meta
Re: [PATCH bpf-next v3 4/6] bpf: Elide range checks when inlining bpf_iter_num_new() for constant bounds
Quoted 23 lines · Puranjay Mohan
bpf_for()is frequently used with constant bounds, e.g.bpf_for(i, 0, N)with a literal N. In that case bpf_iter_num_new()'s start > end and range >BPF_MAX_LOOPSchecks, and their error paths, are decidable at verification time and need not be emitted at all.Record, per call site, whether both the start and end arguments are constant with the same value on every visit, mirroring the state tracking
bpf_loop()inlining already does.check_kfunc_call()stores this inbpf_insn_aux_data; the multi-visit merge matters because the same call site can be reached with different constants on different paths, in which case it falls back to the general sequence.The fold relies on the exact constant values, so the start and end registers are marked precise. Without that the verifier could prune a path reaching the call with different constants before the merge above sees it, and the folded code would run with a stale value.
When the bounds are known,
inline_bpf_iter_num_new()folds the checks and emits only the reachable tail: the iterator init for a valid range, or the zeroing store plus the-EINVAL/-E2BIGresult otherwise. The runtime behaviour is identical to the general sequence and to the kfunc.
Quoted 7 lines
Suggested-by Eduard Zingerman <[email protected]>Signed-off-by Puranjay Mohan <[email protected]>--- include/linux/bpf_verifier.h | 13 ++++++ kernel/bpf/verifier.c | 76 +++++++++++++++++++++++++++++++++++- 2 files changed, 87 insertions(+), 2 deletions(-)
oh my goodness, please no. you are micro-optimizing bpf_iter_num_new(), which is called just *ONCE* and adds all this complexity. It's not worth it, at all. please drop.
the only comparison worth eliminating would be the one done in bpf_iter_num_next, but you can't :)
Quoted 145 lines
include/linux/bpf_verifier.h +13
-0@@ -612,6 +612,15 @@ struct bpf_loop_inline_state {u32 callback_subprogno;/* valid when fit_for_inline is true */ }; +struct bpf_iter_num_new_state { +unsigned int initialized:1 ;/* set to true upon first entry */ +unsigned int fit_for_inline:1 ;/* true if start and end are constant +* with the same value at each call +*/ +s32 start;/* valid when fit_for_inline is true */ +s32 end;/* valid when fit_for_inline is true */ +}; +/* pointer and state for maps */ struct bpf_map_ptr_state {struct bpf_map *map_ptr;@@ -661,6 +670,10 @@ struct bpf_insn_aux_data {* the state of the relevant registers to make decision about inlining */ struct bpf_loop_inline_state loop_inline_state; +/* if instruction is a call to bpf_iter_num_new this field tracks its start/end +* arguments to make a decision about eliding the range checks when inlining +*/ +struct bpf_iter_num_new_state iter_num_new_state; };union {/* remember the size of type passed to bpf_obj_new to rewrite R1 */ kernel/bpf/verifier.c +74
-3@@ -12962,6 +12962,47 @@ static int check_special_kfunc(struct bpf_verifier_env *env, struct bpf_call_argstatic int check_return_code (struct bpf_verifier_env *env,int regno,const char *reg_name); +/* +* bpf_iter_num_new() can be inlined more tightly when its start and end arguments are constant, +* as the range checks and their error paths can then be resolved at rewrite time. Record, per +* call site, whether both arguments are constant with the same value on every visit. +*/ +static int update_iter_num_new_state (struct bpf_verifier_env *env) +{ +struct bpf_iter_num_new_state *state = &cur_aux (env)->iter_num_new_state; +struct bpf_reg_state *start_reg = &cur_regs (env)[BPF_REG_2 ]; +struct bpf_reg_state *end_reg = &cur_regs (env)[BPF_REG_3 ]; +bool known =tnum_is_const (start_reg->var_off) &&tnum_is_const (end_reg->var_off); +s32 start = start_reg->var_off.value; +s32 end = end_reg->var_off.value; +int err; + +if (!state->initialized) { + state->initialized =1 ; + state->fit_for_inline = known; + state->start = start; + state->end = end; + }else if (state->fit_for_inline) { + state->fit_for_inline = known && state->start == start && state->end == end; + } + +/* +* While folding is still viable the decision relies on the exact constant values, so mark +* the registers precise; otherwise the verifier could prune a path that reaches this call +* with different constants and the folded code would run with a stale value. +*/ +if (state->fit_for_inline) { + err =mark_chain_precision (env,BPF_REG_2 ); +if (err) +return err; + err =mark_chain_precision (env,BPF_REG_3 ); +if (err) +return err; + } + +return 0 ; +} +static int check_kfunc_call (struct bpf_verifier_env *env,struct bpf_insn *insn,int *insn_idx_p) {@@ -13163,6 +13204,12 @@ static int check_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, } } +if (meta.func_id == special_kfunc_list[KF_bpf_iter_num_new]) { + err =update_iter_num_new_state (env); +if (err) +return err; + } +for (i =0 ; i <CALLER_SAVED_REGS ; i++) {u32 regno = caller_saved[i];@@ -19774,10 +19821,34 @@ static void __fixup_collection_insert_kfunc(struct bpf_insn_aux_data *insn_aux,* Inline bpf_iter_num_new(). R1 holds the pointer to the iterator, R2 and R3 hold the (int) * start and end arguments. Keep in sync with the kfunc in kernel/bpf/bpf_iter.c. */ -static int inline_bpf_iter_num_new (struct bpf_insn *insn_buf) +static int inline_bpf_iter_num_new (struct bpf_insn *insn_buf,struct bpf_iter_num_new_state *state) {int i =0 ; +/* +* When start and end are constant the range checks and their error paths fold away, +* leaving just the state init or the error result. +*/ +if (state->fit_for_inline) { +s32 start = state->start, end = state->end; + +if (start > end) { +/* s->cur = s->end = 0; return -EINVAL; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 , -EINVAL ); + }else if ((s64 )end - (s64 )start >BPF_MAX_LOOPS ) { +/* s->cur = s->end = 0; return -E2BIG; */ + insn_buf[i++] =BPF_ST_MEM (BPF_DW ,BPF_REG_1 ,0 ,0 ); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 , -E2BIG ); + }else { +/* s->cur = start - 1; s->end = end; return 0; */ + insn_buf[i++] =BPF_ST_MEM (BPF_W ,BPF_REG_1 ,0 , start -1 ); + insn_buf[i++] =BPF_ST_MEM (BPF_W ,BPF_REG_1 ,4 , end); + insn_buf[i++] =BPF_MOV64_IMM (BPF_REG_0 ,0 ); + } +return i; + } +/* if (start > end) goto einval; */ insn_buf[i++] =BPF_JMP32_REG (BPF_JSGT ,BPF_REG_2 ,BPF_REG_3 ,8 );/* @@ -19979,7 +20050,8 @@ int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn, insn_buf[5 ] =BPF_ALU64_IMM (BPF_NEG ,BPF_REG_0 ,0 ); *cnt =6 ; }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_new]) { - *cnt =inline_bpf_iter_num_new (insn_buf); + *cnt =inline_bpf_iter_num_new (insn_buf, + &env->insn_aux_data[insn_idx].iter_num_new_state); }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_next]) { *cnt =inline_bpf_iter_num_next (insn_buf); }else if (desc->func_id == special_kfunc_list[KF_bpf_iter_num_destroy]) { --2.53.0-Meta
PATCH v3 5/6 selftests/bpf: Verify inlined numeric iterator shape with __xlated
In reply to Puranjay MohanAdd __xlated tests to the open-coded iterator suite that pin the shape of the inlined bpf_iter_num_{new,next,destroy}() rewrites. The programs are naked functions, so there is no compiler-generated glue and the whole inlined program is matched instruction for instruction:
- constant bounds: bpf_iter_num_new() folds to the state init, storing start - 1 and end directly;
- non-constant bound: bpf_iter_num_new() keeps the range check, with the distance computation and both the -EINVAL and -E2BIG paths.
bpf_iter_num_next() and bpf_iter_num_destroy() are inlined in both.
The tests are pinned to x86_64 and arm64 (bpf_jit_needs_zext() == false):
on arches that need explicit zero-extension the verifier interleaves "wN = wN" insns into the inlined body, which would not match the fixed instruction sequence. The inlining itself is arch independent, so checking it on these arches is sufficient.
--- tools/testing/selftests/bpf/progs/iters.c | 145 ++++++++++++++++++++++ 1 file changed, 145 insertions(+)
tools/testing/selftests/bpf/progs/iters.c +145 -0
@@ -88,6 +88,151 @@ int iter_err_unsafe_asm_loop(const void *ctx)return 0 ; } +/* +* Naked functions, so there is no compiler-generated glue and the whole inlined program can be +* matched. Pinned to arches whose JITs zero-extend 32-bit writes implicitly +* (bpf_jit_needs_zext() == false); on arches that need explicit zero-extension the verifier +* interleaves "wN = wN" insns and the fixed shape below would not match. The inlining itself is +* arch independent, so checking it on these arches is sufficient. +* +* With constant bounds bpf_iter_num_new() is inlined with the range checks folded away, just +* storing the initial state (s->cur = start - 1, s->end = end); bpf_iter_num_next() and +* bpf_iter_num_destroy() are inlined too, leaving a call-free loop. +*/ +SEC("raw_tp") +__arch_x86_64 +__arch_arm64 +__success +__xlated("r6 = r10") +__xlated("r6 += -8") +__xlated("r1 = r6") +__xlated("r2 = 0") +__xlated ("r3 = 10" ) +/* bpf_iter_num_new(&it, 0, 10) folded to the state init */ +__xlated("*(u32 *)(r1 +0) = -1") +__xlated("*(u32 *)(r1 +4) = 10") +__xlated("r0 = 0") +__xlated ("r1 = r6" ) +/* bpf_iter_num_next(&it) */ +__xlated("r0 = *(u32 *)(r1 +0)") +__xlated("w0 += 1") +__xlated("r2 = *(u32 *)(r1 +4)") +__xlated("if w0 s>= w2 goto pc+3") +__xlated("*(u32 *)(r1 +0) = r0") +__xlated("r0 = r1") +__xlated("goto pc+2") +__xlated("*(u64 *)(r1 +0) = 0") +__xlated("r0 = 0") +__xlated("if r0 != 0x0 goto pc-11") +__xlated ("r1 = r6" ) +/* bpf_iter_num_destroy(&it) */ +__xlated("*(u64 *)(r1 +0) = 0") +__xlated("r0 = 0") +__xlated("exit") +int __naked iter_num_new_const_folded (void ) +{ + asmvolatile ( +/* r6 points to struct bpf_iter_num on the stack */ +"r6 = r10;" +"r6 += -8;" +"r1 = r6;" +"r2 = 0;" +"r3 = 10;" +"call %[bpf_iter_num_new];" +"1:" +"r1 = r6;" +"call %[bpf_iter_num_next];" +"if r0 != 0 goto 1b;" +"r1 = r6;" +"call %[bpf_iter_num_destroy];" +"r0 = 0;" +"exit;" + : + : __imm(bpf_iter_num_new), +__imm (bpf_iter_num_next), +__imm (bpf_iter_num_destroy) + : __clobber_common, "r6" + ); +} + +/* +* Same arch pinning and naked-function rationale as above. With a non-constant bound +* bpf_iter_num_new() keeps the full range check: the distance is computed and both the -EINVAL +* and -E2BIG error paths remain. bpf_iter_num_next() and bpf_iter_num_destroy() are inlined too. +*/ +SEC("raw_tp") +__arch_x86_64 +__arch_arm64 +__success +__xlated("r6 = r10") +__xlated("r6 += -8") +__xlated("call unknown") +__xlated("r3 = r0") +__xlated("r3 &= 65535") +__xlated("r1 = r6") +__xlated ("r2 = 0" ) +/* bpf_iter_num_new(&it, 0, <non-const>) with the range check kept */ +__xlated("if w2 s> w3 goto pc+8") +__xlated("w0 = w3") +__xlated("w0 -= w2") +__xlated("if r0 s> 0x800000 goto pc+8") +__xlated("w2 += -1") +__xlated("*(u32 *)(r1 +0) = r2") +__xlated("*(u32 *)(r1 +4) = r3") +__xlated("r0 = 0") +__xlated("goto pc+5") +__xlated("*(u64 *)(r1 +0) = 0") +__xlated("r0 = -22") +__xlated("goto pc+2") +__xlated("*(u64 *)(r1 +0) = 0") +__xlated("r0 = -7") +__xlated ("r1 = r6" ) +/* bpf_iter_num_next(&it) */ +__xlated("r0 = *(u32 *)(r1 +0)") +__xlated("w0 += 1") +__xlated("r2 = *(u32 *)(r1 +4)") +__xlated("if w0 s>= w2 goto pc+3") +__xlated("*(u32 *)(r1 +0) = r0") +__xlated("r0 = r1") +__xlated("goto pc+2") +__xlated("*(u64 *)(r1 +0) = 0") +__xlated("r0 = 0") +__xlated("if r0 != 0x0 goto pc-11") +__xlated ("r1 = r6" ) +/* bpf_iter_num_destroy(&it) */ +__xlated("*(u64 *)(r1 +0) = 0") +__xlated("r0 = 0") +__xlated("exit") +int __naked iter_num_new_inlined (void ) +{ + asmvolatile ( +/* r6 points to struct bpf_iter_num on the stack */ +"r6 = r10;" +"r6 += -8;" +/* non-constant end so the range checks are kept */ +"call %[bpf_get_prandom_u32];" +"r3 = r0;" +"r3 &= 0xffff;" +"r1 = r6;" +"r2 = 0;" +"call %[bpf_iter_num_new];" +"1:" +"r1 = r6;" +"call %[bpf_iter_num_next];" +"if r0 != 0 goto 1b;" +"r1 = r6;" +"call %[bpf_iter_num_destroy];" +"r0 = 0;" +"exit;" + : + : __imm(bpf_get_prandom_u32), +__imm (bpf_iter_num_new), +__imm (bpf_iter_num_next), +__imm (bpf_iter_num_destroy) + : __clobber_common, "r6" + ); +} + SEC("raw_tp") __successint iter_while_loop (const void *ctx)
Signature · 1 line
2.53.0-Meta
PATCH v3 6/6 selftests/bpf: Add bpf_for() benchmark
In reply to Puranjay MohanThe bpf_for() macro builds on the numeric open-coded iterator kfuncs bpf_iter_num_{new,next,destroy}(). Add a benchmark, modelled on the existing bpf_loop benchmark, that repeatedly runs a bpf_for() loop so the per-iteration cost of the iterator can be measured, e.g. to quantify the effect of inlining the iterator kfuncs in the verifier.
The BPF program runs an inner bpf_for(i, 0, nr_loops) loop with an empty body 1000 times per trigger and accounts nr_loops hits per outer iteration, mirroring bench_bpf_loop so the two are directly comparable.
nr_loops defaults to 1000 so that the per-iteration bpf_iter_num_next() cost, rather than the one-time bpf_iter_num_new()/destroy() setup and teardown, dominates the reported numbers:
$ ./bench -p 1 --nr_loops 1000 bpf-for
--- tools/testing/selftests/bpf/Makefile | 2 + tools/testing/selftests/bpf/bench.c | 4 + .../selftests/bpf/benchs/bench_bpf_for.c | 104 ++++++++++++++++++ .../selftests/bpf/benchs/run_bench_bpf_for.sh | 15 +++ .../selftests/bpf/progs/bpf_for_bench.c | 32 ++++++ 5 files changed, 157 insertions(+) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_for.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_for.sh create mode 100644 tools/testing/selftests/bpf/progs/bpf_for_bench.c
tools/testing/selftests/bpf/Makefile +2 -0
@@ -965,6 +965,7 @@ $(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_bpf_for.o: $(OUTPUT)/bpf_for_bench.skel.h $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h $(OUTPUT)/bench_bpf_hashmap_full_update.o: $(OUTPUT)/bpf_hashmap_full_update_bench.skel.h $(OUTPUT)/bench_local_storage.o: $(OUTPUT)/local_storage_bench.skel.h
@@ -990,6 +991,7 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_ringbufs.o \ $(OUTPUT)/bench_bloom_filter_map.o \ $(OUTPUT)/bench_bpf_loop.o \ + $(OUTPUT)/bench_bpf_for.o \ $(OUTPUT)/bench_strncmp.o \ $(OUTPUT)/bench_bpf_hashmap_full_update.o \ $(OUTPUT)/bench_local_storage.o \
tools/testing/selftests/bpf/bench.c +4 -0
@@ -276,6 +276,7 @@ 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; +extern struct argp bench_bpf_for_argp;extern struct argp bench_local_storage_argp;extern struct argp bench_local_storage_rcu_tasks_trace_argp;extern struct argp bench_strncmp_argp;
@@ -292,6 +293,7 @@ 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 }, + { &bench_bpf_for_argp, 0, "bpf_for loop benchmark", 0 }, { &bench_local_storage_argp, 0, "local_storage benchmark", 0 }, { &bench_strncmp_argp, 0, "bpf_strncmp helper benchmark", 0 }, { &bench_local_storage_rcu_tasks_trace_argp, 0,
@@ -557,6 +559,7 @@ 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; +extern const struct bench bench_bpf_for;extern const struct bench bench_strncmp_no_helper;extern const struct bench bench_strncmp_helper;extern const struct bench bench_bpf_hashmap_full_update;
@@ -640,6 +643,7 @@ static const struct bench *benchs[] = { &bench_hashmap_without_bloom, &bench_hashmap_with_bloom, &bench_bpf_loop, + &bench_bpf_for, &bench_strncmp_no_helper, &bench_strncmp_helper, &bench_bpf_hashmap_full_update,
tools/testing/selftests/bpf/benchs/bench_bpf_for.c new file +104 -0
104 lines not on this page · raw message
tools/testing/selftests/bpf/benchs/run_bench_bpf_for.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 10 100 500 1000 5000 10000 50000 100000 500000 1000000; do +subtitle "nr_loops: $i, nr_threads: $t" + summarize_ops "bpf_for: " \ + "$($RUN_BENCH -p $t --nr_loops $i bpf-for)" + printf "\n" +done +done
tools/testing/selftests/bpf/progs/bpf_for_bench.c new file +32 -0
@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +char _license[] SEC("license") = "GPL"; + +u32 nr_loops; +long hits; + +static int outer_loop (__u32 index,void *data) +{ +int i; + +/* +* Empty body: the work being measured is the open-coded numeric iterator itself +* (bpf_iter_num_new/next/destroy behind bpf_for()). +*/ +bpf_for (i,0 , nr_loops) + ; +__sync_add_and_fetch (&hits, nr_loops); +return 0 ; +} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int benchmark (void *ctx) +{ +bpf_loop (1000 , outer_loop,NULL ,0 ); +return 0 ; +}
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewRe: [PATCH bpf-next v3 6/6] selftests/bpf: Add bpf_for() benchmark
An earlier question about this benchmark does not seem to have been answered yet: how does the bpf_for() loop here compare with a regular for loop that also reads its counter?
Quoted 18 lines
tools/testing/selftests/bpf/progs/bpf_for_bench.c new file +12
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +char _license[] SEC("license") = "GPL"; + +u32 nr_loops; +long hits; +
tools/testing/selftests/bpf/progs/bpf_for_bench.c line 22
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_for_bench.c new file +10
-0+static int outer_loop (__u32 index,void *data) +{ +int i; + +/* +* Empty body: the work being measured is the open-coded numeric iterator itself +* (bpf_iter_num_new/next/destroy behind bpf_for()). +*/ +bpf_for (i,0 , nr_loops) + ;
An earlier question about this benchmark does not seem to have been answered yet: how does the bpf_for() loop here compare with a regular for loop that also reads its counter?
The current benchmark only exercises bpf_for(). Would it be worth adding a regular-loop variant so the two can be compared directly?
tools/testing/selftests/bpf/progs/bpf_for_bench.c line 32
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_for_bench.c new file +10
-0+__sync_add_and_fetch (&hits, nr_loops); +return 0 ; +} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int benchmark (void *ctx) +{ +bpf_loop (1000 , outer_loop,NULL ,0 ); +return 0 ; +}
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/29924758865
Re: [PATCH bpf-next v3 6/6] selftests/bpf: Add bpf_for() benchmark
In reply to Puranjay MohanQuoted 222 lines · Puranjay Mohan
The
bpf_for()macro builds on the numeric open-coded iterator kfuncs bpf_iter_num_{new,next,destroy}(). Add a benchmark, modelled on the existingbpf_loopbenchmark, that repeatedly runs abpf_for()loop so the per-iteration cost of the iterator can be measured, e.g. to quantify the effect of inlining the iterator kfuncs in the verifier.The BPF program runs an inner
bpf_for(i, 0, nr_loops)loop with an empty body 1000 times per trigger and accountsnr_loopshits per outer iteration, mirroringbench_bpf_loopso the two are directly comparable.
nr_loopsdefaults to 1000 so that the per-iterationbpf_iter_num_next()cost, rather than the one-time bpf_iter_num_new()/destroy() setup and teardown, dominates the reported numbers:$ ./bench -p 1 --nr_loops 1000 bpf-forSigned-off-by Puranjay Mohan <[email protected]>--- tools/testing/selftests/bpf/Makefile | 2 + tools/testing/selftests/bpf/bench.c | 4 + .../selftests/bpf/benchs/bench_bpf_for.c | 104 ++++++++++++++++++ .../selftests/bpf/benchs/run_bench_bpf_for.sh | 15 +++ .../selftests/bpf/progs/bpf_for_bench.c | 32 ++++++ 5 files changed, 157 insertions(+) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_for.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_for.sh create mode 100644 tools/testing/selftests/bpf/progs/bpf_for_bench.ctools/testing/selftests/bpf/Makefile +2
-0@@ -965,6 +965,7 @@ $(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_bpf_for.o: $(OUTPUT)/bpf_for_bench.skel.h $(OUTPUT)/bench_strncmp.o: $(OUTPUT)/strncmp_bench.skel.h $(OUTPUT)/bench_bpf_hashmap_full_update.o: $(OUTPUT)/bpf_hashmap_full_update_bench.skel.h $(OUTPUT)/bench_local_storage.o: $(OUTPUT)/local_storage_bench.skel.h@@ -990,6 +991,7 @@ $(OUTPUT)/bench: $(OUTPUT)/bench.o \ $(OUTPUT)/bench_ringbufs.o \ $(OUTPUT)/bench_bloom_filter_map.o \ $(OUTPUT)/bench_bpf_loop.o \ + $(OUTPUT)/bench_bpf_for.o \ $(OUTPUT)/bench_strncmp.o \ $(OUTPUT)/bench_bpf_hashmap_full_update.o \ $(OUTPUT)/bench_local_storage.o \tools/testing/selftests/bpf/bench.c +4
-0@@ -276,6 +276,7 @@ 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; +extern struct argp bench_bpf_for_argp;extern struct argp bench_local_storage_argp;extern struct argp bench_local_storage_rcu_tasks_trace_argp;extern struct argp bench_strncmp_argp;@@ -292,6 +293,7 @@ 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 }, + { &bench_bpf_for_argp, 0, "bpf_for loop benchmark", 0 }, { &bench_local_storage_argp, 0, "local_storage benchmark", 0 }, { &bench_strncmp_argp, 0, "bpf_strncmp helper benchmark", 0 }, { &bench_local_storage_rcu_tasks_trace_argp, 0,@@ -557,6 +559,7 @@ 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; +extern const struct bench bench_bpf_for;extern const struct bench bench_strncmp_no_helper;extern const struct bench bench_strncmp_helper;extern const struct bench bench_bpf_hashmap_full_update;@@ -640,6 +643,7 @@ static const struct bench *benchs[] = { &bench_hashmap_without_bloom, &bench_hashmap_with_bloom, &bench_bpf_loop, + &bench_bpf_for, &bench_strncmp_no_helper, &bench_strncmp_helper, &bench_bpf_hashmap_full_update,tools/testing/selftests/bpf/benchs/bench_bpf_for.c new file +104
-0@@ -0,0 +1,104 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + +#include <argp.h> +#include "bench.h" +#include "bpf_for_bench.skel.h" + +/* BPF triggering benchmarks */ +static struct ctx { +struct bpf_for_bench *skel; +} ctx; + +static struct { +__u32 nr_loops; +} args = { +/* +* Default to a large loop count so the per-iteration bpf_iter_num_next() cost dominates +* the one-time bpf_iter_num_new()/destroy() setup and teardown. +*/ + .nr_loops =1000 , +}; + +enum { +ARG_NR_LOOPS =4000 , +}; + +static const struct argp_option opts[] = { + {"nr_loops" ,ARG_NR_LOOPS ,"nr_loops" ,0 , +"Set number of iterations for the bpf_for() loop" }, + {}, +}; + +static error_t parse_arg (int key,char *arg,struct argp_state *state) +{ +switch (key) { +case ARG_NR_LOOPS : + args.nr_loops =strtol (arg,NULL ,10 ); +break ; +default : +return ARGP_ERR_UNKNOWN ; + } + +return 0 ; +} + +/* exported into benchmark runner */ +const struct argp bench_bpf_for_argp = { + .options = opts, + .parser = parse_arg, +}; + +static void validate (void ) +{ +if (env.consumer_cnt !=0 ) { +fprintf (stderr,"benchmark doesn't support consumer!\n" ); +exit (1 ); + } +} + +static void *producer (void *input) +{ +while (true) +/* trigger the bpf program */ +syscall (__NR_getpgid); + +return NULL ; +} + +static void measure (struct bench_res *res) +{ + res->hits =atomic_swap (&ctx.skel->bss->hits,0 ); +} + +static void setup (void ) +{ +struct bpf_link *link; + +setup_libbpf (); + + ctx.skel =bpf_for_bench__open_and_load (); +if (!ctx.skel) { +fprintf (stderr,"failed to open skeleton\n" ); +exit (1 ); + } + + link =bpf_program__attach (ctx.skel->progs.benchmark); +if (!link) { +fprintf (stderr,"failed to attach program!\n" ); +exit (1 ); + } + + ctx.skel->bss->nr_loops = args.nr_loops; +} + +const struct bench bench_bpf_for = { + .name ="bpf-for" , + .argp = &bench_bpf_for_argp, + .validate = validate, + .setup = setup, + .producer_thread = producer, + .measure = measure, + .report_progress = ops_report_progress, + .report_final = ops_report_final, +};tools/testing/selftests/bpf/benchs/run_bench_bpf_for.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 10 100 500 1000 5000 10000 50000 100000 500000 1000000; do +subtitle "nr_loops: $i, nr_threads: $t" + summarize_ops "bpf_for: " \ + "$($RUN_BENCH -p $t --nr_loops $i bpf-for)" + printf "\n" +done +donetools/testing/selftests/bpf/progs/bpf_for_bench.c new file +0
-0
tools/testing/selftests/bpf/progs/bpf_for_bench.c line 10
Quoted 10 lines
tools/testing/selftests/bpf/progs/bpf_for_bench.c new file +10
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 +/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */ + +#include "vmlinux.h" +#include <bpf/bpf_helpers.h> +#include "bpf_misc.h" + +char _license[] SEC("license") = "GPL"; + +u32 nr_loops;
minor nit: nr_loops should be int, that's what bpf_for() expects
Quoted 25 lines
tools/testing/selftests/bpf/progs/bpf_for_bench.c new file +22
-1+long hits; + +static int outer_loop (__u32 index,void *data) +{ +int i; + +/* +* Empty body: the work being measured is the open-coded numeric iterator itself +* (bpf_iter_num_new/next/destroy behind bpf_for()). +*/ +bpf_for (i,0 , nr_loops) + ; +__sync_add_and_fetch (&hits, nr_loops); +return 0 ; +} + +SEC("fentry/" SYS_PREFIX "sys_getpgid") +int benchmark (void *ctx) +{ +bpf_loop (1000 , outer_loop,NULL ,0 ); +return 0 ; +} --2.53.0-Meta
Kumar Kartikeya Dwivedi
maintainerQuoted 46 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+
Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.
I find some of this explanation unsatisfying. How was this determined? Is this just your hypothesis, or did you actually observe different counters in perf state to corroborate this on arm64? I am no arm64 expert, so perhaps it does not do a bunch of things (store-load forwarding and memory disambiguation) that would help here, but it would still be good to understand why.
It would also be interesting to compare against can_loop. Adding it as a comparison and finding the result should be easy. Can you check what the overhead is in that case?
All that said, I am still fine with all this, bpf_for() being costly has been a known fact forever.
Quoted 48 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.Changelog:
v2: https://lore.kernel.org/bpf/[email protected]/
Changes in v3:
- Elide the range checks inbpf_iter_num_new()when start and end are constant, marking the registers precise so paths reaching the call with different constants are not pruned (Eduard Zingerman)
- Add__xlatedselftests pinning the inlined new()/next()/destroy() shapes (Eduard Zingerman)
- Use the insn_buf[i++] idiom in the inline helpers (Eduard Zingerman)
- Pick up Acked-by on patch 3v1: https://lore.kernel.org/all/[email protected]/
Changes in v2:
- Don't emit sign-extending (movsx) moves; some JITs (e.g. x86-32, mips32, sparc64) decode them as a plain move and would miscompile the range checkPuranjay Mohan (6):
bpf: Inlinebpf_iter_num_new()kfunc
bpf: Inlinebpf_iter_num_next()kfunc
bpf: Inlinebpf_iter_num_destroy()kfunc
bpf: Elide range checks when inliningbpf_iter_num_new()for constant
bounds
selftests/bpf: Verify inlined numeric iterator shape with__xlatedselftests/bpf: Addbpf_for()benchmarkinclude/linux/bpf_verifier.h | 13 ++ kernel/bpf/verifier.c | 157 ++++++++++++++++++ tools/testing/selftests/bpf/Makefile | 2 + tools/testing/selftests/bpf/bench.c | 4 + .../selftests/bpf/benchs/bench_bpf_for.c | 104 ++++++++++++ .../selftests/bpf/benchs/run_bench_bpf_for.sh | 15 ++ .../selftests/bpf/progs/bpf_for_bench.c | 32 ++++ tools/testing/selftests/bpf/progs/iters.c | 145 ++++++++++++++++ 8 files changed, 472 insertions(+) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_for.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_for.sh create mode 100644 tools/testing/selftests/bpf/progs/bpf_for_bench.cbase-commit:
a23a71823352e2d792dcaae25f1ebb744acbfc0b
Quoted 19 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.
Quoted 6 lines
-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.
tbh, I don't think we need to do *anything* in bpf_iter_num_destroy(), not sure why I added that zeroing out there. that stack slot will not be treated as iterator state after destroy() is called, so what is stored there doesn't matter, we can simplify (unless I'm missing something non-obvious, but I can't see it)
Quoted 22 lines
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+
Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.
exactly, and those removed calls should be noticeable in such microbenchmark... also, bpf_loop being faster than bpf_for() is a big surprise. let's dive deeper into this, this makes no sense
Quoted 7 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.
hm, again, I'm not sure I'm buying this. bpf_loop() does indirect function call, stack access can't be more expensive than that, can it?..
Quoted 44 lines
Changelog:
v2: https://lore.kernel.org/bpf/[email protected]/
Changes in v3:
- Elide the range checks inbpf_iter_num_new()when start and end are constant, marking the registers precise so paths reaching the call with different constants are not pruned (Eduard Zingerman)
- Add__xlatedselftests pinning the inlined new()/next()/destroy() shapes (Eduard Zingerman)
- Use the insn_buf[i++] idiom in the inline helpers (Eduard Zingerman)
- Pick up Acked-by on patch 3v1: https://lore.kernel.org/all/[email protected]/
Changes in v2:
- Don't emit sign-extending (movsx) moves; some JITs (e.g. x86-32, mips32, sparc64) decode them as a plain move and would miscompile the range checkPuranjay Mohan (6):
bpf: Inlinebpf_iter_num_new()kfunc
bpf: Inlinebpf_iter_num_next()kfunc
bpf: Inlinebpf_iter_num_destroy()kfunc
bpf: Elide range checks when inliningbpf_iter_num_new()for constant
bounds
selftests/bpf: Verify inlined numeric iterator shape with__xlatedselftests/bpf: Addbpf_for()benchmarkinclude/linux/bpf_verifier.h | 13 ++ kernel/bpf/verifier.c | 157 ++++++++++++++++++ tools/testing/selftests/bpf/Makefile | 2 + tools/testing/selftests/bpf/bench.c | 4 + .../selftests/bpf/benchs/bench_bpf_for.c | 104 ++++++++++++ .../selftests/bpf/benchs/run_bench_bpf_for.sh | 15 ++ .../selftests/bpf/progs/bpf_for_bench.c | 32 ++++ tools/testing/selftests/bpf/progs/iters.c | 145 ++++++++++++++++ 8 files changed, 472 insertions(+) create mode 100644 tools/testing/selftests/bpf/benchs/bench_bpf_for.c create mode 100755 tools/testing/selftests/bpf/benchs/run_bench_bpf_for.sh create mode 100644 tools/testing/selftests/bpf/progs/bpf_for_bench.cbase-commit:
a23a71823352e2d792dcaae25f1ebb744acbfc0b--
2.53.0-Meta
Quoted 62 lines · Andrii Nakryiko
Quoted 19 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.Quoted 6 lines
-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.tbh, I don't think we need to do *anything* in
bpf_iter_num_destroy(), not sure why I added that zeroing out there. that stack slot will not be treated as iterator state afterdestroy()is called, so what is stored there doesn't matter, we can simplify (unless I'm missing something non-obvious, but I can't see it)Quoted 22 lines
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.
Quoted 3 lines
exactly, and those removed calls should be noticeable in such microbenchmark... also,
bpf_loopbeing faster thanbpf_for()is a big surprise. let's dive deeper into this, this makes no sense
Yes, I will do more perf testing before posting the next version.
Quoted 10 lines
Quoted 6 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.hm, again, I'm not sure I'm buying this.
bpf_loop()does indirect function call, stack access can't be more expensive than that, can it?..
No, the above explanation given by me is not accurate, it was my theory but it didn't hold up when I looked into perf reports. So, I need to dive deeper into this.
Kumar Kartikeya Dwivedi
maintainerQuoted 77 lines · Puranjay Mohan
Quoted 62 lines · Andrii Nakryiko
Quoted 19 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.Quoted 6 lines
-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.tbh, I don't think we need to do *anything* in
bpf_iter_num_destroy(), not sure why I added that zeroing out there. that stack slot will not be treated as iterator state afterdestroy()is called, so what is stored there doesn't matter, we can simplify (unless I'm missing something non-obvious, but I can't see it)Quoted 22 lines
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.Quoted 3 lines
exactly, and those removed calls should be noticeable in such microbenchmark... also,
bpf_loopbeing faster thanbpf_for()is a big surprise. let's dive deeper into this, this makes no senseYes, I will do more perf testing before posting the next version.
Quoted 7 lines
Quoted 6 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.
Quoted 7 lines
Quoted 3 lines
hm, again, I'm not sure I'm buying this.
bpf_loop()does indirect function call, stack access can't be more expensive than that, can it?..No, the above explanation given by me is not accurate, it was my theory but it didn't hold up when I looked into perf reports. So, I need to dive deeper into this.
It might also be worth comparing cases where verifier does inline and does not inline bpf_loop, the latter can often be the common case for some programs, and may help appreciate the improvement more.
Quoted 83 lines · Kumar Kartikeya Dwivedi
Quoted 81 lines · Puranjay Mohan
Quoted 62 lines · Andrii Nakryiko
Quoted 19 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.Quoted 6 lines
-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.tbh, I don't think we need to do *anything* in
bpf_iter_num_destroy(), not sure why I added that zeroing out there. that stack slot will not be treated as iterator state afterdestroy()is called, so what is stored there doesn't matter, we can simplify (unless I'm missing something non-obvious, but I can't see it)Quoted 22 lines
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.Quoted 3 lines
exactly, and those removed calls should be noticeable in such microbenchmark... also,
bpf_loopbeing faster thanbpf_for()is a big surprise. let's dive deeper into this, this makes no senseYes, I will do more perf testing before posting the next version.
Quoted 10 lines
Quoted 6 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.hm, again, I'm not sure I'm buying this.
bpf_loop()does indirect function call, stack access can't be more expensive than that, can it?..
Quoted 7 lines
Quoted 3 lines
No, the above explanation given by me is not accurate, it was my theory but it didn't hold up when I looked into perf reports. So, I need to dive deeper into this.
It might also be worth comparing cases where verifier does inline and does not inline
bpf_loop, the latter can often be the common case for some programs, and may help appreciate the improvement more.
we actively discourage bpf_loop() in favor of bpf_for() or may_goto approach, so let's not invest in (complicating verifier for the benefit of) optimizing bpf_loop()
Kumar Kartikeya Dwivedi
maintainerQuoted 90 lines · Andrii Nakryiko
Quoted 87 lines · Kumar Kartikeya Dwivedi
Quoted 84 lines · Puranjay Mohan
Quoted 62 lines · Andrii Nakryiko
Quoted 19 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.Quoted 6 lines
-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.tbh, I don't think we need to do *anything* in
bpf_iter_num_destroy(), not sure why I added that zeroing out there. that stack slot will not be treated as iterator state afterdestroy()is called, so what is stored there doesn't matter, we can simplify (unless I'm missing something non-obvious, but I can't see it)Quoted 22 lines
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.Quoted 3 lines
exactly, and those removed calls should be noticeable in such microbenchmark... also,
bpf_loopbeing faster thanbpf_for()is a big surprise. let's dive deeper into this, this makes no senseYes, I will do more perf testing before posting the next version.
Quoted 10 lines
Quoted 6 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.hm, again, I'm not sure I'm buying this.
bpf_loop()does indirect function call, stack access can't be more expensive than that, can it?..No, the above explanation given by me is not accurate, it was my theory but it didn't hold up when I looked into perf reports. So, I need to dive deeper into this.
Quoted 7 lines
Quoted 3 lines
It might also be worth comparing cases where verifier does inline and does not inline
bpf_loop, the latter can often be the common case for some programs, and may help appreciate the improvement more.we actively discourage
bpf_loop()in favor ofbpf_for()ormay_gotoapproach, so let's not invest in (complicating verifier for the benefit of) optimizingbpf_loop()
It's not complicating the verifier, just comparing against bpf_loop in the benchmark where the loop count is not known to the verifier (probably 20 more lines in the BPF side to serve as a comparison point).
Quoted 96 lines · Kumar Kartikeya Dwivedi
Quoted 94 lines · Andrii Nakryiko
Quoted 90 lines · Kumar Kartikeya Dwivedi
Quoted 77 lines · Puranjay Mohan
Quoted 62 lines · Andrii Nakryiko
Quoted 19 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.Quoted 6 lines
-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.tbh, I don't think we need to do *anything* in
bpf_iter_num_destroy(), not sure why I added that zeroing out there. that stack slot will not be treated as iterator state afterdestroy()is called, so what is stored there doesn't matter, we can simplify (unless I'm missing something non-obvious, but I can't see it)Quoted 22 lines
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.Quoted 3 lines
exactly, and those removed calls should be noticeable in such microbenchmark... also,
bpf_loopbeing faster thanbpf_for()is a big surprise. let's dive deeper into this, this makes no senseYes, I will do more perf testing before posting the next version.
Quoted 7 lines
Quoted 6 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.Quoted 7 lines
Quoted 3 lines
hm, again, I'm not sure I'm buying this.
bpf_loop()does indirect function call, stack access can't be more expensive than that, can it?..No, the above explanation given by me is not accurate, it was my theory but it didn't hold up when I looked into perf reports. So, I need to dive deeper into this.
It might also be worth comparing cases where verifier does inline and does not inline
bpf_loop, the latter can often be the common case for some programs, and may help appreciate the improvement more.
Quoted 8 lines
Quoted 3 lines
we actively discourage
bpf_loop()in favor ofbpf_for()ormay_gotoapproach, so let's not invest in (complicating verifier for the benefit of) optimizingbpf_loop()It's not complicating the verifier, just comparing against
bpf_loopin the benchmark where the loop count is not known to the verifier (probably 20 more lines in the BPF side to serve as a comparison point).
ah, my bad, I somehow read your statement as suggestion to improve bpf_loop() inlining, sorry
Kumar Kartikeya Dwivedi
maintainerQuoted 96 lines · Kumar Kartikeya Dwivedi
Quoted 94 lines · Andrii Nakryiko
Quoted 90 lines · Kumar Kartikeya Dwivedi
Quoted 77 lines · Puranjay Mohan
Quoted 62 lines · Andrii Nakryiko
Quoted 19 lines · Puranjay Mohan
The
bpf_for(i, start, end)macro is BPF's open-coded numeric iterator. It expands into calls to three kfuncs:bpf_iter_num_new()to set the iterator up,bpf_iter_num_next()once per iteration, andbpf_iter_num_destroy()to tear it down. The verifier emits these as ordinary kfunc calls, so abpf_for()loop pays function-call overhead on setup, teardown, and — most importantly — on every single iteration viabpf_iter_num_next().All three kfuncs are tiny and only touch the 8-byte on-stack iterator state (struct
bpf_iter_num_kern{ int cur; int end; }). That makes them good candidates for inlining, the same way several other special kfuncs are already open-coded inbpf_fixup_kfunc_call(). This series replaces each of the three calls with an equivalent inline BPF instruction sequence:-
bpf_iter_num_new(): the (s64)end - (s64)start overflow check is done with 32-bit arithmetic (start <= end is checked first, so the range fits in a u32), avoiding cpuv4 sign-extension insns that some JITs do not implement. Returns the same-EINVAL/-E2BIG/ 0 as the kfunc.Quoted 6 lines
-
bpf_iter_num_next(): the hot path. Since cur and end are int, thekfunc's (s64)(s->cur + 1) >= s->end test reduces to a signed 32-bit comparison of (s->cur + 1) against s->end, so the inlined code uses a 32-bit compare with no sign extension.-
bpf_iter_num_destroy(): a single 8-byte store zeroing the state.tbh, I don't think we need to do *anything* in
bpf_iter_num_destroy(), not sure why I added that zeroing out there. that stack slot will not be treated as iterator state afterdestroy()is called, so what is stored there doesn't matter, we can simplify (unless I'm missing something non-obvious, but I can't see it)Quoted 22 lines
bpf_for()is frequently used with constant bounds; in that case the range checks inbpf_iter_num_new()are decidable at verification time, so a follow-up patch elides them and emits only the iterator init (or the error result). The inlined shapes are pinned by new__xlatedselftests, and abench_bpf_forbenchmark (modeled on the existingbpf_loopbenchmark) runs abpf_for()loop with an empty body to measure the per-iteration cost.The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no
jit_requiredmarking is needed.Benchmark (./bench -p 1 --nr_loops 1000000 {bpf-loop,bpf-for}):
+--------+---------------------+---------------------+---------------------+ | arch | bpf_loop | bpf_for non-inlined | bpf_for inlined | +--------+---------------------+---------------------+---------------------+ | x86-64 | 2946 M/s (0.339 ns) | 4281 M/s (0.234 ns) | 8981 M/s (0.111 ns) | +--------+---------------------+---------------------+---------------------+ | arm64 | 618 M/s (1.619 ns) | 543 M/s (1.843 ns) | 538 M/s (1.858 ns) | +--------+---------------------+---------------------+---------------------+Quoted 5 lines
On x86-64, removing the per-iteration call to
bpf_iter_num_next()roughly doublesbpf_for()throughput. On arm64 it is neutral: the loop is bound by the load/store dependency chain on the on-stack iterator state rather than by call overhead, so inlining neither helps nor hurts there. It still removes the calls.Quoted 3 lines
exactly, and those removed calls should be noticeable in such microbenchmark... also,
bpf_loopbeing faster thanbpf_for()is a big surprise. let's dive deeper into this, this makes no senseYes, I will do more perf testing before posting the next version.
Quoted 7 lines
Quoted 6 lines
bpf_loop()is shown for reference only; it is a different construct (a callback invoked per iteration), so the comparison is structural rather than a measure of the inlining: on x86-64bpf_for()is faster thanbpf_loop()even before inlining, while on arm64bpf_loop()is faster because bpf_for()'s per-iteration cost is dominated by the stack round-trip through the iterator state.Quoted 7 lines
Quoted 3 lines
hm, again, I'm not sure I'm buying this.
bpf_loop()does indirect function call, stack access can't be more expensive than that, can it?..No, the above explanation given by me is not accurate, it was my theory but it didn't hold up when I looked into perf reports. So, I need to dive deeper into this.
It might also be worth comparing cases where verifier does inline and does not inline
bpf_loop, the latter can often be the common case for some programs, and may help appreciate the improvement more.
Quoted 8 lines
Quoted 3 lines
we actively discourage
bpf_loop()in favor ofbpf_for()ormay_gotoapproach, so let's not invest in (complicating verifier for the benefit of) optimizingbpf_loop()It's not complicating the verifier, just comparing against
bpf_loopin the benchmark where the loop count is not known to the verifier (probably 20 more lines in the BPF side to serve as a comparison point).
... and I meant loop flag, not loop count. See update_loop_inline_state().