From f1606dd0ac49230f5a5fa1a279210fdf0249c20f Mon Sep 17 00:00:00 2001 From: Alexei Starovoitov Date: Thu, 2 Apr 2026 19:44:19 -0700 Subject: bpf: Add bpf_compute_const_regs() and bpf_prune_dead_branches() passes Add two passes before the main verifier pass: bpf_compute_const_regs() is a forward dataflow analysis that tracks register values in R0-R9 across the program using fixed-point iteration in reverse postorder. Each register is tracked with a six-state lattice: UNVISITED -> CONST(val) / MAP_PTR(map_index) / MAP_VALUE(map_index, offset) / SUBPROG(num) -> UNKNOWN At merge points, if two paths produce the same state and value for a register, it stays; otherwise it becomes UNKNOWN. The analysis handles: - MOV, ADD, SUB, AND with immediate or register operands - LD_IMM64 for plain constants, map FDs, map values, and subprogs - LDX from read-only maps: constant-folds the load by reading the map value directly via bpf_map_direct_read() Results that fit in 32 bits are stored per-instruction in insn_aux_data and bitmasks. bpf_prune_dead_branches() uses the computed constants to evaluate conditional branches. When both operands of a conditional jump are known constants, the branch outcome is determined statically and the instruction is rewritten to an unconditional jump. The CFG postorder is then recomputed to reflect new control flow. This eliminates dead edges so that subsequent liveness analysis doesn't propagate through dead code. Also add runtime sanity check to validate that precomputed constants match the verifier's tracked state. Acked-by: Eduard Zingerman Link: https://lore.kernel.org/r/20260403024422.87231-5-alexei.starovoitov@gmail.com Signed-off-by: Alexei Starovoitov --- include/linux/bpf_verifier.h | 23 +++++++++++++++++++++++ 1 file changed, 23 insertions(+) (limited to 'include') diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index d21541f96ee9..c5e65cdb6328 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -595,6 +595,18 @@ struct bpf_insn_aux_data { u32 scc; /* registers alive before this instruction. */ u16 live_regs_before; + /* + * Bitmask of R0-R9 that hold known values at this instruction. + * const_reg_mask: scalar constants that fit in 32 bits. + * const_reg_map_mask: map pointers, val is map_index into used_maps[]. + * const_reg_subprog_mask: subprog pointers, val is subprog number. + * const_reg_vals[i] holds the 32-bit value for register i. + * Populated by compute_const_regs() pre-pass. + */ + u16 const_reg_mask; + u16 const_reg_map_mask; + u16 const_reg_subprog_mask; + u32 const_reg_vals[10]; }; #define MAX_USED_MAPS 64 /* max number of maps accessed by one eBPF program */ @@ -945,6 +957,10 @@ void bpf_free_kfunc_btf_tab(struct bpf_kfunc_btf_tab *tab); int mark_chain_precision(struct bpf_verifier_env *env, int regno); +bool bpf_map_is_rdonly(const struct bpf_map *map); +int bpf_map_direct_read(struct bpf_map *map, int off, int size, u64 *val, + bool is_ldsx); + #define BPF_BASE_TYPE_MASK GENMASK(BPF_BASE_TYPE_BITS - 1, 0) /* extract base type from bpf_{arg, return, reg}_type. */ @@ -1088,6 +1104,13 @@ struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx); void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask); bool bpf_calls_callback(struct bpf_verifier_env *env, int insn_idx); +int bpf_find_subprog(struct bpf_verifier_env *env, int off); +int bpf_compute_const_regs(struct bpf_verifier_env *env); +int bpf_prune_dead_branches(struct bpf_verifier_env *env); +int bpf_compute_postorder(struct bpf_verifier_env *env); +bool bpf_insn_is_cond_jump(u8 code); +bool bpf_is_may_goto_insn(struct bpf_insn *insn); + int bpf_stack_liveness_init(struct bpf_verifier_env *env); void bpf_stack_liveness_free(struct bpf_verifier_env *env); int bpf_update_live_stack(struct bpf_verifier_env *env); -- cgit v1.2.3