bpf: simple DFA-based live registers analysis
Status from this message: This series was applied to bpf/bpf-next.git (master)
Get series with b4
b4 am [email protected]Versions newest first · linked by author and title
- v3 Latest5 patches 0 repliesApplied 5/5
- v25 patches 2 repliesSuperseded
- v13 patches 7 repliesSuperseded
Changes in v3 from the cover letter
- added support for BPF_LOAD_ACQ, BPF_STORE_REL atomics (Alexei);
- correct use marks for r0 for BPF_CMPXCHG.
Patches in v3 All 5 applied
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/5 | bpf: jmp_offset() and verbose_insn() utility functionskernel/ | +23 | 0 replies | Applied |
| 2/5 | bpf: get_call_summary() utility functionkernel/ | +57 | 0 replies | Applied |
| 3/5 | bpf: simple DFA-based live registers analysisinclude/ kernel/ tools/ | +330 | 0 replies | Applied |
| 4/5 | bpf: use register liveness information for func_states_equalkernel/ | +10 | 0 replies | Applied |
| 5/5 | selftests/bpf: test cases for compute_live_registers()tools/ tools/ tools/ +3 more | +455 | 0 replies | Applied |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v3 yet.
Cover letter [PATCH bpf-next v3 0/5] bpf: simple DFA-based live registers analysis
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 v2 -> v3:
- added support for BPF_LOAD_ACQ, BPF_STORE_REL atomics (Alexei);
- correct use marks for r0 for BPF_CMPXCHG.
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/[email protected]/ v1: https://lore.kernel.org/bpf/[email protected]/ v2: https://lore.kernel.org/bpf/[email protected]/
[1] https://lore.kernel.org/bpf/[email protected]/
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 | 495 ++++++++++++++---- .../testing/selftests/bpf/prog_tests/align.c | 11 +- .../bpf/prog_tests/compute_live_registers.c | 9 + tools/testing/selftests/bpf/progs/bpf_misc.h | 17 + .../bpf/progs/compute_live_registers.c | 424 +++++++++++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- .../bpf/progs/verifier_load_acquire.c | 7 +- 9 files changed, 875 insertions(+), 106 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
Signature · 1 line
2.48.1