Skip to contentSkip to conversation

bpf: Inline the numeric open-coded iterator kfuncs

PATCH Superseded Puranjay Mohan 4 participants 8 messages Jul 15

Subsystems (4)

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

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(): keeps the (s64)end - (s64)start overflow check (emitted with sign-extending moves) and returns the same -EINVAL / -E2BIG / 0 results 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.

The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no jit_required marking is needed.

Patch 4 adds a bench_bpf_for benchmark, modeled on the existing bpf_loop benchmark, that runs a bpf_for() loop with an empty body so the per-iteration iterator cost can be measured directly.

Results (./bench -p 1 --nr_loops 1000 bpf-for):

  +--------+----------------------+----------------------+--------------+
  |  arch  |       inlined        |     kfunc calls      |   result     |
  +--------+----------------------+----------------------+--------------+
  | x86-64 | 12884 M/s (0.078 ns) | 5812 M/s (0.172 ns)  | ~2.2x faster |
  +--------+----------------------+----------------------+--------------+
  | arm64  | 546.1 M/s (1.831 ns) | 545.8 M/s (1.832 ns) | neutral      |
  +--------+----------------------+----------------------+--------------+

On x86-64, removing the per-iteration call to bpf_iter_num_next() roughly doubles throughput. On arm64 the numbers are unchanged: 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.

Puranjay Mohan (4):
bpf: Inline bpf_iter_num_new() kfunc
bpf: Inline bpf_iter_num_next() kfunc
bpf: Inline bpf_iter_num_destroy() kfunc
selftests/bpf: Add bpf_for() benchmark

 kernel/bpf/verifier.c                         |  79 +++++++++++++
 tools/testing/selftests/bpf/Makefile          |   2 +
 tools/testing/selftests/bpf/bench.c           |   4 +
 .../selftests/bpf/benchs/bench_bpf_for.c      | 105 ++++++++++++++++++
 .../selftests/bpf/benchs/run_bench_bpf_for.sh |  15 +++
 .../selftests/bpf/progs/bpf_for_bench.c       |  32 ++++++
 6 files changed, 237 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: d1f4b56417a3dc1a0600f960b14f46bd25eda89d

Signature · 1 line
2.53.0-Meta
#1 lore raw

PATCH 1/4 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 (s64)end - (s64)start overflow check is emitted with sign-extending moves; the rest of 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 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 | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)
kernel/bpf/verifier.c +36 -0
index de816063ae63d..f578cebbade4f 100644
@@ -19715,6 +19715,40 @@ 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)
+{
+	/* if (start > end) goto einval; */
+	insn_buf[0] = BPF_JMP32_REG(BPF_JSGT, BPF_REG_2, BPF_REG_3, 9);
+	/* r0 = (s64)end - (s64)start; */
+	insn_buf[1] = BPF_MOVSX64_REG(BPF_REG_0, BPF_REG_3, 32);
+	insn_buf[2] = BPF_MOVSX64_REG(BPF_REG_4, BPF_REG_2, 32);
+	insn_buf[3] = BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_4);
+	/* if (r0 > BPF_MAX_LOOPS) goto e2big; */
+	insn_buf[4] = BPF_JMP_IMM(BPF_JSGT, BPF_REG_0, BPF_MAX_LOOPS, 8);
+	/* s->cur = start - 1; */
+	insn_buf[5] = BPF_ALU32_IMM(BPF_ADD, BPF_REG_2, -1);
+	insn_buf[6] = BPF_STX_MEM(BPF_W, BPF_REG_1, BPF_REG_2, 0);
+	/* s->end = end; */
+	insn_buf[7] = BPF_STX_MEM(BPF_W, BPF_REG_1, BPF_REG_3, 4);
+	/* return 0; */
+	insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insn_buf[9] = BPF_JMP_A(5);
+	/* einval: s->cur = s->end = 0; return -EINVAL; */
+	insn_buf[10] = BPF_ST_MEM(BPF_DW, BPF_REG_1, 0, 0);
+	insn_buf[11] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
+	insn_buf[12] = BPF_JMP_A(2);
+	/* e2big: s->cur = s->end = 0; return -E2BIG; */
+	insn_buf[13] = BPF_ST_MEM(BPF_DW, BPF_REG_1, 0, 0);
+	insn_buf[14] = BPF_MOV64_IMM(BPF_REG_0, -E2BIG);
+
+	return 15;
+}
+
 int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		     struct bpf_insn *insn_buf, int insn_idx, int *cnt)
 {
@@ -19844,6 +19878,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
#2 lore raw

Re: [PATCH bpf-next 1/4] bpf: Inline bpf_iter_num_new() kfunc

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] The inlined `bpf_iter_num_new` emits CPUv4 `BPF_MOVSX64_REG` instructions during the…

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] The inlined bpf_iter_num_new emits CPUv4 BPF_MOVSX64_REG instructions during the post-verification fixup pass. On architectures whose JIT compilers do not natively support CPUv4 (e.g. x86-32, MIPS32), BPF_MOVSX is miscompiled as a standard zero-extending 64-bit MOV because they ignore insn->off. This breaks the iterator's loop bounds check and causes a denial of service (unbounded BPF loop). --

--- Patch [1]: [PATCH bpf-next 1/4] bpf: Inline bpf_iter_num_new() kfunc --- commit a284b42200c5d5b485b4d27a28c08c05022dfa70
Author: Puranjay Mohan <[email protected]>

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.

Quoted 4 lines
kernel/bpf/verifier.c +0 -0
index de816063ae63d..f578cebbade4f 100644

[ ... ]

Quoted 6 lines
kernel/bpf/verifier.c +2 -0
@@ -19715,6 +19715,40 @@ 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

kernel/bpf/verifier.c static void __fixup_collection_insert_kfunc(struct bpf_insn_aux_data *insn_aux, · line 19729

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+ * 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)
+{
+	/* if (start > end) goto einval; */
+	insn_buf[0] = BPF_JMP32_REG(BPF_JSGT, BPF_REG_2, BPF_REG_3, 9);
+	/* r0 = (s64)end - (s64)start; */
+	insn_buf[1] = BPF_MOVSX64_REG(BPF_REG_0, BPF_REG_3, 32);
+	insn_buf[2] = BPF_MOVSX64_REG(BPF_REG_4, BPF_REG_2, 32);

[Severity: High]
Does this code emit CPUv4 instructions (BPF_MOVSX64_REG) into the instruction stream post-verification?

Since inline_bpf_iter_num_new() is called from bpf_fixup_kfunc_call() after do_check() has completed, the verifier will not reject these instructions on older architectures.

On architectures whose JIT compilers do not natively support CPUv4 (such as x86-32 or MIPS32), BPF_MOVSX is miscompiled as a standard zero-extending 64-bit MOV because they ignore insn->off.

If start is a negative number and end is positive, start will be passed zero-extended in the 64-bit register. A normal 64-bit MOV fails to sign-extend this, and the subsequent subtraction r0 = end - start yields a large negative 64-bit integer instead of the actual positive distance.

kernel/bpf/verifier.c static void __fixup_collection_insert_kfunc(struct bpf_insn_aux_data *insn_aux, · line 19732

Quoted 3 lines
kernel/bpf/verifier.c +3 -0
+	insn_buf[3] = BPF_ALU64_REG(BPF_SUB, BPF_REG_0, BPF_REG_4);
+	/* if (r0 > BPF_MAX_LOOPS) goto e2big; */
+	insn_buf[4] = BPF_JMP_IMM(BPF_JSGT, BPF_REG_0, BPF_MAX_LOOPS, 8);

[Severity: High]
Could the signed comparison BPF_JSGT fail to enforce the loop bounds if the subtraction yields a large negative number on older JITs?

If the distance calculation evaluates as a negative 64-bit integer, this check would evaluate to false, bypassing the BPF_MAX_LOOPS limit. This could allow a BPF program to loop up to 4.29 billion times, potentially hanging the kernel.

Since the if (start > end) check already ensures end >= start, would it be safer to use standard 32-bit arithmetic? A 32-bit unsigned subtraction (u32)end - (u32)start evaluates to the exact distance and correctly zero-extends into the 64-bit register for the subsequent BPF_MAX_LOOPS check.

Quoted 18 lines
kernel/bpf/verifier.c +18 -0
+	/* s->cur = start - 1; */
+	insn_buf[5] = BPF_ALU32_IMM(BPF_ADD, BPF_REG_2, -1);
+	insn_buf[6] = BPF_STX_MEM(BPF_W, BPF_REG_1, BPF_REG_2, 0);
+	/* s->end = end; */
+	insn_buf[7] = BPF_STX_MEM(BPF_W, BPF_REG_1, BPF_REG_3, 4);
+	/* return 0; */
+	insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, 0);
+	insn_buf[9] = BPF_JMP_A(5);
+	/* einval: s->cur = s->end = 0; return -EINVAL; */
+	insn_buf[10] = BPF_ST_MEM(BPF_DW, BPF_REG_1, 0, 0);
+	insn_buf[11] = BPF_MOV64_IMM(BPF_REG_0, -EINVAL);
+	insn_buf[12] = BPF_JMP_A(2);
+	/* e2big: s->cur = s->end = 0; return -E2BIG; */
+	insn_buf[13] = BPF_ST_MEM(BPF_DW, BPF_REG_1, 0, 0);
+	insn_buf[14] = BPF_MOV64_IMM(BPF_REG_0, -E2BIG);
+
+	return 15;
+}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
#3 lore raw

PATCH 2/4 bpf: Inline bpf_iter_num_next() kfunc

In reply to Puranjay Mohan

bpf_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 | 29 +++++++++++++++++++++++++++++
 1 file changed, 29 insertions(+)
kernel/bpf/verifier.c +29 -0
index f578cebbade4f..e8b66f56598dd 100644
@@ -19749,6 +19749,33 @@ static int inline_bpf_iter_num_new(struct bpf_insn *insn_buf)
 	return 15;
 }
 
+/*
+ * 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)
+{
+	/*
+	 * 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[0] = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_1, 0);
+	insn_buf[1] = BPF_ALU32_IMM(BPF_ADD, BPF_REG_0, 1);
+	insn_buf[2] = BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1, 4);
+	/* if ((s32)(s->cur + 1) >= (s32)s->end) goto done; */
+	insn_buf[3] = BPF_JMP32_REG(BPF_JSGE, BPF_REG_0, BPF_REG_2, 3);
+	/* s->cur++; return &s->cur; */
+	insn_buf[4] = BPF_STX_MEM(BPF_W, BPF_REG_1, BPF_REG_0, 0);
+	insn_buf[5] = BPF_MOV64_REG(BPF_REG_0, BPF_REG_1);
+	insn_buf[6] = BPF_JMP_A(2);
+	/* done: s->cur = s->end = 0; return NULL; */
+	insn_buf[7] = BPF_ST_MEM(BPF_DW, BPF_REG_1, 0, 0);
+	insn_buf[8] = BPF_MOV64_IMM(BPF_REG_0, 0);
+
+	return 9;
+}
+
 int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		     struct bpf_insn *insn_buf, int insn_idx, int *cnt)
 {
@@ -19880,6 +19907,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
#4 lore raw

PATCH 3/4 bpf: Inline bpf_iter_num_destroy() kfunc

In reply to 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 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 | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
kernel/bpf/verifier.c +14 -0
index e8b66f56598dd..082617adaba5b 100644
@@ -19776,6 +19776,18 @@ static int inline_bpf_iter_num_next(struct bpf_insn *insn_buf)
 	return 9;
 }
 
+/*
+ * 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)
+{
+	/* s->cur = s->end = 0; */
+	insn_buf[0] = BPF_ST_MEM(BPF_DW, BPF_REG_1, 0, 0);
+
+	return 1;
+}
+
 int bpf_fixup_kfunc_call(struct bpf_verifier_env *env, struct bpf_insn *insn,
 		     struct bpf_insn *insn_buf, int insn_idx, int *cnt)
 {
@@ -19909,6 +19921,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
#5 lore raw

PATCH 4/4 selftests/bpf: Add bpf_for() benchmark

In reply to 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 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      | 105 ++++++++++++++++++
 .../selftests/bpf/benchs/run_bench_bpf_for.sh |  15 +++
 .../selftests/bpf/progs/bpf_for_bench.c       |  32 ++++++
 5 files changed, 158 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
index b642ee489ea64..00b6ff636e3c1 100644
@@ -967,6 +967,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
@@ -992,6 +993,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
index 3d9d2cd7764bd..b86b73456d3ca 100644
@@ -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 +105 -0

105 lines not on this page · raw message

tools/testing/selftests/bpf/benchs/run_bench_bpf_for.sh new file +15 -0
new file mode 100755
index 0000000000000..7da6453920dab
@@ -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
new file mode 100644
index 0000000000000..920f8f188e864
@@ -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
#6 lore raw
In reply to Puranjay Mohan
Quoted 34 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, 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(): keeps the (s64)end - (s64)start overflow check (emitted with sign-extending moves) and returns the same -EINVAL / -E2BIG / 0 results 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.

The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no jit_required marking is needed.

Patch 4 adds a bench_bpf_for benchmark, modeled on the existing bpf_loop benchmark, that runs a bpf_for() loop with an empty body so the per-iteration iterator cost can be measured directly.

Results (./bench -p 1 --nr_loops 1000 bpf-for):

Quoted 8 lines
  +--------+----------------------+----------------------+--------------+
  |  arch  |       inlined        |     kfunc calls      |   result     |
  +--------+----------------------+----------------------+--------------+
  | x86-64 | 12884 M/s (0.078 ns) | 5812 M/s (0.172 ns)  | ~2.2x faster |
  +--------+----------------------+----------------------+--------------+
  | arm64  | 546.1 M/s (1.831 ns) | 545.8 M/s (1.832 ns) | neutral      |
  +--------+----------------------+----------------------+--------------+

The bench results are excellent on x86-64.

However, after looking through patch #1 and patch #2, hmm, they seem quite complex.

Alexei suggested that the kfuncs could be inlined by the kernel disasm approach [1]. With that approach, it should be possible to inline many kfuncs and helpers on both x86-64 and arm64.

I think we should try hard to implement the disasm approach.

[1]
https://lore.kernel.org/bpf/CAADnVQLNmQGKf5S5ZNwHYzScYBhnWFmnzLg=5Xxy4SgYKE3EfQ@mail.gmail.com/

Thanks,
Leon

Quoted 7 lines

On x86-64, removing the per-iteration call to bpf_iter_num_next() roughly doubles throughput. On arm64 the numbers are unchanged: 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.

[...]

#7 lore raw
Quoted 46 lines · Leon Hwang
Quoted 34 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, 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(): keeps the (s64)end - (s64)start overflow check (emitted with sign-extending moves) and returns the same -EINVAL / -E2BIG / 0 results 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.

The emitted instructions are plain BPF and remain valid for the interpreter, so interpreter fallback stays correct and no jit_required marking is needed.

Patch 4 adds a bench_bpf_for benchmark, modeled on the existing bpf_loop benchmark, that runs a bpf_for() loop with an empty body so the per-iteration iterator cost can be measured directly.

Results (./bench -p 1 --nr_loops 1000 bpf-for):

Quoted 8 lines
  +--------+----------------------+----------------------+--------------+
  |  arch  |       inlined        |     kfunc calls      |   result     |
  +--------+----------------------+----------------------+--------------+
  | x86-64 | 12884 M/s (0.078 ns) | 5812 M/s (0.172 ns)  | ~2.2x faster |
  +--------+----------------------+----------------------+--------------+
  | arm64  | 546.1 M/s (1.831 ns) | 545.8 M/s (1.832 ns) | neutral      |
  +--------+----------------------+----------------------+--------------+
Quoted 8 lines

The bench results are excellent on x86-64.

However, after looking through patch #1 and patch #2, hmm, they seem quite complex.

Alexei suggested that the kfuncs could be inlined by the kernel disasm approach [1]. With that approach, it should be possible to inline many kfuncs and helpers on both x86-64 and arm64.

Alexei was talking about inlining in the JITs, but here we are inlining through the verifier which means it works out of the box for every JIT.

Let's see what others have to say, if there is consensus then I will try out other approaches.

Thanks,
Puranjay