The id map used to compare 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(), is a fixed array embedded in struct bpf_verifier_env and sized for the most registers and stack slots a state can possibly hold: 1312 entries, 10 KiB, for 512-byte frames, and four times that once frames may reach 2 KiB, which pushes the env allocation from 64 KiB to 128 KiB for every program verified. States compare a few dozen ids in practice. Turn the map and the set into arrays grown on demand, starting at 64 entries and doubling, and free them with the env. A map that cannot grow treats the states as different, an id set that cannot grow keeps the id, and the id stack reports -ENOMEM, so an allocation failure is never unsafe. This removes the last structure whose size scaled with the stack bound and shrinks the env by 10 KiB. Signed-off-by: Kumar Kartikeya Dwivedi --- include/linux/bpf_verifier.h | 29 ++++++++++++++---------- kernel/bpf/states.c | 44 +++++++++++++++++++++++++----------- kernel/bpf/verifier.c | 20 +++++++++------- 3 files changed, 60 insertions(+), 33 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 0f348ce81fe2..d8cafd3d74aa 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -408,10 +408,7 @@ 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]; @@ -842,18 +839,27 @@ 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; - struct bpf_id_pair map[BPF_ID_MAP_SIZE]; + u32 cap; + struct bpf_id_pair *map; }; +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; - struct { - u32 id; - u32 cnt; - } entries[BPF_ID_MAP_SIZE]; + u32 cap; + struct bpf_idset_entry *entries; }; /* see verifier.c:compute_scc_callchain() */ @@ -948,10 +954,8 @@ struct bpf_verifier_env { struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 2]; /* max + 2 for the fake and exception subprogs */ /* subprog indices sorted in topological order: leaves first, callers last */ int subprog_topo_order[BPF_MAX_SUBPROGS + 2]; - union { - struct bpf_idmap idmap_scratch; - struct bpf_idset idset_scratch; - }; + struct bpf_idmap idmap_scratch; + struct bpf_idset idset_scratch; struct { int *insn_state; int *insn_stack; @@ -1209,6 +1213,7 @@ 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); diff --git a/kernel/bpf/states.c b/kernel/bpf/states.c index e84f37d724d5..5078e4832c6e 100644 --- a/kernel/bpf/states.c +++ b/kernel/bpf/states.c @@ -335,21 +335,18 @@ static bool check_ids(u32 old_id, u32 cur_id, struct bpf_idmap *idmap) return false; } - /* Reached the end of known mappings; haven't seen this id before */ - if (idmap->cnt < BPF_ID_MAP_SIZE) { - map[idmap->cnt].old = old_id; - map[idmap->cnt].cur = cur_id; - idmap->cnt++; - return true; - } - /* - * idmap slots are bounded by the number of registers and stack slots. - * Since referenced dynptrs acquire intermediate references that do - * not live in either, so the map can be exhausted. Since it is unlikely, - * fail the verification by treating the states as not equivalent. + * Reached the end of known mappings; haven't seen this id before. If + * the map cannot grow, treat the states as not equivalent, which only + * costs pruning. */ - return false; + if (!bpf_id_scratch_reserve((void **)&idmap->map, &idmap->cap, idmap->cnt, sizeof(*map))) + return false; + map = idmap->map; + map[idmap->cnt].old = old_id; + map[idmap->cnt].cur = cur_id; + idmap->cnt++; + return true; } /* @@ -965,6 +962,27 @@ static bool func_states_equal(struct bpf_verifier_env *env, struct bpf_func_stat return true; } +/* + * Make room for one more entry in an id scratch array, doubling it as needed. + * Returns false if it could not grow; callers then treat the id as unknown + * or the states as different, which is always safe. + */ +bool bpf_id_scratch_reserve(void **arr, u32 *cap, u32 cnt, size_t elem_size) +{ + u32 new_cap; + void *p; + + if (cnt < *cap) + return true; + new_cap = *cap ? *cap * 2 : 64; + p = krealloc_array(*arr, new_cap, elem_size, GFP_KERNEL_ACCOUNT | __GFP_NOWARN); + if (!p) + return false; + *arr = p; + *cap = new_cap; + return true; +} + static void reset_idmap_scratch(struct bpf_verifier_env *env) { struct bpf_idmap *idmap = &env->idmap_scratch; diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index d8f43f3a8991..8641f1a8d017 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -10136,8 +10136,9 @@ static int idstack_push(struct bpf_idmap *idmap, u32 id) if (idmap->map[i].old == id) return 0; - if (WARN_ON_ONCE(idmap->cnt >= BPF_ID_MAP_SIZE)) - return -EFAULT; + if (!bpf_id_scratch_reserve((void **)&idmap->map, &idmap->cap, idmap->cnt, + sizeof(*idmap->map))) + return -ENOMEM; idmap->map[idmap->cnt++].old = id; return 0; @@ -18438,12 +18439,13 @@ static void idset_cnt_inc(struct bpf_idset *idset, u32 id) return; } } - /* New id */ - if (idset->num_ids < BPF_ID_MAP_SIZE) { - idset->entries[idset->num_ids].id = id; - idset->entries[idset->num_ids].cnt = 1; - idset->num_ids++; - } + /* New id; one that cannot be recorded counts as shared and is kept */ + if (!bpf_id_scratch_reserve((void **)&idset->entries, &idset->cap, idset->num_ids, + sizeof(*idset->entries))) + return; + idset->entries[idset->num_ids].id = id; + idset->entries[idset->num_ids].cnt = 1; + idset->num_ids++; } /* Find id in idset and return its count, or 0 if not found */ @@ -22003,6 +22005,8 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr, kvfree(env->scc_info); kvfree(env->succ); kvfree(env->gotox_tmp_buf); + kfree(env->idmap_scratch.map); + kfree(env->idset_scratch.entries); bpf_diag_free(env); kvfree(env); return ret; -- 2.53.0