[PATCH bpf-next v1 0/3] bpf: simple DFA-based live registers analysis

[Eduard Zingerman <eddyz87@gmail.com>]

This patch set introduces a simple live register DFA analysis.
The analysis is performed as a separate step before the main
verification pass, and results are stored in `env->insn_aux_data` for
each instruction.

This change improves handling of iterator/callback-based loops, as
regular register liveness marks are not finalized while loops are
being processed. See veristat results for selftests and sched_ext in
patch #2.

The patch set was tested in branch [1] by disabling the current
register parentage chain liveness computation, using DFA-based
liveness for registers while assuming all stack slots as live.
No notable regressions were found in test_progs-based tests.

Note: For regular subprogram calls, the analysis conservatively
assumes that registers r1-r5 are used and that r0 is used at each
`exit` instruction. Experiments in [1] show that adding precise
handling for these cases has no impact on verification performance for
selftests and sched_ext.

This was previously shared as RFC [2].
Changes since RFC:
- The parameter count for helpers and kfuncs is now taken into
  account.
- The analysis is now enabled only in privileged mode (Alexei);
- The `copy_verifier_state()` bug fix was merged separately and is no
  longer a part of this patch set.

[1] https://github.com/eddyz87/bpf/tree/liveregs-dfa-std-liveregs-off
[2] https://lore.kernel.org/bpf/20250122120442.3536298-1-eddyz87@gmail.com/

Eduard Zingerman (3):
  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                  |   7 +
 kernel/bpf/verifier.c                         | 394 +++++++++++++++--
 .../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, 804 insertions(+), 38 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