bpf: table based bpf_insn_successors()
authorEduard Zingerman <eddyz87@gmail.com>
Fri, 19 Sep 2025 02:18:43 +0000 (19:18 -0700)
committerAlexei Starovoitov <ast@kernel.org>
Fri, 19 Sep 2025 16:27:23 +0000 (09:27 -0700)
commit79f047c7d968b21ff4b72bd70c4533140553c56c
tree4f9b0a0eb47e015fcd8097b6abfd2e20fe5344de
parent107e169799057bc6a379ddb625cbe1e51cfc7d72
bpf: table based bpf_insn_successors()

Converting bpf_insn_successors() to use lookup table makes it ~1.5
times faster.

Also remove unnecessary conditionals:
- `idx + 1 < prog->len` is unnecessary because after check_cfg() all
  jump targets are guaranteed to be within a program;
- `i == 0 || succ[0] != dst` is unnecessary because any client of
  bpf_insn_successors() can handle duplicate edges:
  - compute_live_registers()
  - compute_scc()

Moving bpf_insn_successors() to liveness.c allows its inlining in
liveness.c:__update_stack_liveness().
Such inlining speeds up __update_stack_liveness() by ~40%.
bpf_insn_successors() is used in both verifier.c and liveness.c.
perf shows such move does not negatively impact users in verifier.c,
as these are executed only once before main varification pass.
Unlike __update_stack_liveness() which can be triggered multiple
times.

Signed-off-by: Eduard Zingerman <eddyz87@gmail.com>
Link: https://lore.kernel.org/r/20250918-callchain-sensitive-liveness-v3-10-c3cd27bacc60@gmail.com
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
include/linux/bpf_verifier.h
kernel/bpf/liveness.c
kernel/bpf/verifier.c