bpf: Return the id scratch to a fixed array sized for the stack budget
Kumar Kartikeya Dwivedi
maintainerPATCH 1/1 bpf: Return the id scratch to a fixed array sized for the stack budget
Commit 9f3d900a69be ("bpf: Grow the verifier id scratch on demand") turned the id map comparing the ids of two states, which also serves as the id stack of release_reference() and as the id set of bpf_clear_singular_ids(), into arrays grown on demand, so that the env would not embed a map sized for 2 KiB frames. That gave the map a way to fail, and with it release_reference() and the iterator destroy path an -ENOMEM to hand up, states_equal() a case where states compare unequal for lack of memory, and bpf_clear_singular_ids() a flag to keep every id when the set could not record them all.
The env is allocated once per program load, so the map can afford to be sized for the largest state again: MAX_BPF_STACK_SLOTS in each of MAX_CALL_FRAMES frames, which a state on a private stack can reach since every frame there may use the whole budget. That makes the map 34 KiB instead of 10 KiB, a small price per load for having no growth that can fail. Make the map and the set a fixed union in the env again and drop the growth and its failure handling.
--- include/linux/bpf_verifier.h | 29 +++++++++------------ kernel/bpf/states.c | 44 ++++++++++--------------------- kernel/bpf/verifier.c | 50 +++++++++++------------------------- 3 files changed, 40 insertions(+), 83 deletions(-)
include/linux/bpf_verifier.h +12 -17
@@ -411,7 +411,10 @@ struct bpf_jmp_history_entry {static_assert (MAX_CALL_FRAMES <= (1 <<4 ));static_assert (MAX_BPF_STACK_SLOTS <= (1 <<12 )); +/* Maximum number of bpf_reg_state objects that can exist at once */ #define MAX_STACK_ARG_SLOTS (MAX_BPF_FUNC_ARGS - MAX_BPF_FUNC_REG_ARGS) +#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK_SLOTS + MAX_STACK_ARG_SLOTS) * \ + MAX_CALL_FRAMES)struct bpf_verifier_state {/* call stack tracking */ struct bpf_func_state *frame[MAX_CALL_FRAMES ];
@@ -866,27 +869,18 @@ struct bpf_id_pair {u32 cur; }; -/* -* Scratch map from the ids of one verifier state to those of another, also -* used as a stack of ids. Grown on demand by bpf_id_scratch_reserve(). -*/ struct bpf_idmap {u32 tmp_id_gen;u32 cnt; -u32 cap; -struct bpf_id_pair *map; +struct bpf_id_pair map[BPF_ID_MAP_SIZE ]; }; -struct bpf_idset_entry { -u32 id; -u32 cnt; -}; - -/* Scratch set of ids with a use count each, grown on demand */ struct bpf_idset {u32 num_ids; -u32 cap; -struct bpf_idset_entry *entries; +struct { +u32 id; +u32 cnt; + } entries[BPF_ID_MAP_SIZE ]; };/* see verifier.c:compute_scc_callchain() */
@@ -995,8 +989,10 @@ struct bpf_verifier_env {* via callx. Allocated when the first such edge is recorded. */ unsigned long *callx_edges; -struct bpf_idmap idmap_scratch; -struct bpf_idset idset_scratch; +union { +struct bpf_idmap idmap_scratch; +struct bpf_idset idset_scratch; + };struct {int *insn_state;int *insn_stack;
@@ -1264,7 +1260,6 @@ int bpf_copy_verifier_state(struct bpf_verifier_state *dst_state,struct list_head *bpf_explored_state (struct bpf_verifier_env *env,int idx);void bpf_free_verifier_state (struct bpf_verifier_state *state,bool free_self);void bpf_free_backedges (struct bpf_scc_visit *visit); -bool bpf_id_scratch_reserve (void **arr,u32 *cap,u32 cnt,size_t elem_size);int bpf_push_jmp_history (struct bpf_verifier_env *env,struct bpf_verifier_state *cur,int insn_flags,int spi,int frame,const u16 *linked_regs,u8 linked_regs_cnt);
kernel/bpf/states.c +13 -31
58 lines not on this page · raw message
kernel/bpf/verifier.c +15 -35
102 lines not on this page · raw message
--
2.53.0
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This patch was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 11 lines · On Thu, 24 Sep 2026 21:34:01 +0200 you wrote:
Commit
9f3d900a69be("bpf: Grow the verifier id scratch on demand") turned the id map comparing the ids of two states, which also serves as the id stack ofrelease_reference()and as the id set ofbpf_clear_singular_ids(), into arrays grown on demand, so that the env would not embed a map sized for 2 KiB frames. That gave the map a way to fail, and with itrelease_reference()and the iterator destroy path an-ENOMEMto hand up,states_equal()a case where states compare unequal for lack of memory, andbpf_clear_singular_ids()a flag to keep every id when the set could not record them all.[...]
Here is the summary with links:
- [bpf-next] bpf: Return the id scratch to a fixed array sized for the stack budget
https://git.kernel.org/bpf/bpf-next/c/9bf1f086e7dd
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html