This patch-set introduces a simple live registers DFA analysis. Analysis is done as a separate step before main verification pass. Results are stored in the env->insn_aux_data for each instruction. The change helps with iterator/callback based loops handling, as regular register liveness marks are not finalized while loops are processed. See veristat results in patch #2. Note: for regular subprogram calls analysis conservatively assumes that r1-r5 are used, and r0 is used at each 'exit' instruction. Experiments show that adding logic handling these cases precisely has no impact on verification performance. The patch set was tested by disabling the current register parentage chain liveness computation, using DFA-based liveness for registers while assuming all stack slots as live. See discussion in [1]. Changes v1 -> v2: - added a refactoring commit extracting utility functions: jmp_offset(), verbose_insn() (Alexei); - added a refactoring commit extracting utility function get_call_summary() in order to share helper/kfunc related code with mark_fastcall_pattern_for_call() (Alexei); - comment in the compute_insn_live_regs() extended (Alexei). Changes RFC -> v1: - parameter count for helpers and kfuncs is taken into account; - copy_verifier_state() bugfix had been merged as a separate patch-set and is no longer a part of this patch set. RFC: https://lore.kernel.org/bpf/20250122120442.3536298-1-eddyz87@xxxxxxxxx/ v1: https://lore.kernel.org/bpf/20250228060032.1425870-1-eddyz87@xxxxxxxxx/ [1] https://lore.kernel.org/bpf/cc29975fbaf163d0c2ed904a9a4d6d9452177542.camel@xxxxxxxxx/ Eduard Zingerman (5): bpf: jmp_offset() and verbose_insn() utility functions bpf: get_call_summary() utility function bpf: simple DFA-based live registers analysis bpf: use register liveness information for func_states_equal selftests/bpf: test cases for compute_live_registers() include/linux/bpf_verifier.h | 6 + kernel/bpf/verifier.c | 484 ++++++++++++++---- .../testing/selftests/bpf/prog_tests/align.c | 11 +- .../bpf/prog_tests/compute_live_registers.c | 9 + tools/testing/selftests/bpf/progs/bpf_misc.h | 12 + .../bpf/progs/compute_live_registers.c | 397 ++++++++++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- 8 files changed, 829 insertions(+), 102 deletions(-) create mode 100644 tools/testing/selftests/bpf/prog_tests/compute_live_registers.c create mode 100644 tools/testing/selftests/bpf/progs/compute_live_registers.c -- 2.48.1
