RFC bpf: improvements for iterator-based loops convergence
Get series with b4
b4 am [email protected]Versions newest first
- v1 RFC Latest7 patches 1 replyIn review
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/7 | bpf: copy_verifier_state() should copy 'loop_entry' fieldkernel/ | +3 | 0 replies | |
| 2/7 | selftests/bpf: test correct loop_entry update in copy_verifier_statetools/ | +116 | 0 replies | |
| 3/7 | bpf: don't do clean_live_states when state->loop_entry->branches > 0kernel/ | +4 | 0 replies | |
| 4/7 | selftests/bpf: check states pruning for deeply nested iteratortools/ | +23 | 0 replies | |
| 5/7 | bpf: DFA-based liveness analysis for program registersinclude/ kernel/ tools/ | +344 | 1 reply | |
| 6/7 | bpf: use register liveness information for func_states_equalkernel/ | +10 | 0 replies | |
| 7/7 | selftests/bpf: test cases for compute_live_registers()tools/ tools/ tools/ +2 more | +386 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [RFC bpf-next v1 0/7] bpf: improvements for iterator-based loops convergence
This RFC consists of a bug fix and two improvements for iterator/callback based loops handling:
- Patch #1 fixes a bug in copy_verifier_state(), where field 'loop_entry' was not copied. The fix has negative impact on verification performance.
- Patch #3 mitigates negative impact from patch #1 by avoiding clean_live_states() for states that have loop_entry that is still being verified. This reduces amount of processed instructions for sched_ext by 28-92% for some programs.
- Patches #5,6 introduce a simple live registers DFA analysis. Results of this analysis are used in func_states_equal() and further reduce amount of processed instructions for sched_ext by 17-30% for some programs.
Below are veristat results comparing master to this RFC.
selftests:
File Program Insns (DIFF) States (DIFF) --------------------- -------------------------- ----------------- ---------------- arena_htab.bpf.o arena_htab_llvm -294 (-41.00%) -20 (-35.09%) arena_htab_asm.bpf.o arena_htab_asm -152 (-25.46%) -10 (-21.28%) arena_list.bpf.o arena_list_add +329 (+22.04%) +7 (+23.33%) arena_list.bpf.o arena_list_del -161 (-52.10%) -12 (-52.17%) iters.bpf.o checkpoint_states_deletion -16914 (-93.32%) -778 (-95.11%) iters.bpf.o iter_nested_deeply_iters -293 (-49.41%) -30 (-44.78%) iters.bpf.o iter_nested_iters -181 (-22.26%) -17 (-21.52%) iters.bpf.o iter_subprog_iters -430 (-39.31%) -29 (-32.95%) iters.bpf.o loop_state_deps2 -158 (-32.99%) -14 (-30.43%) pyperf600_iter.bpf.o on_event -8633 (-69.97%) -189 (-42.86%)
sched_ext:
Program Insns (DIFF) States (DIFF) ---------------------- ----------------- ---------------- lavd_dispatch -34018 (-22.00%) -1885 (-21.06%) layered_dispatch -5378 (-46.81%) -313 (-36.91%) layered_dump -3689 (-49.71%) -455 (-66.81%) layered_enqueue -4038 (-30.90%) -351 (-29.80%) layered_init -995483 (-99.55%) -84233 (-99.48%) layered_runnable -1587 (-49.32%) -172 (-58.31%) refresh_layer_cpumasks -15597 (-94.60%) -1684 (-95.14%) rustland_init -85 (-17.07%) -7 (-17.07%) rustland_init -85 (-17.07%) -7 (-17.07%) rusty_select_cpu -706 (-33.65%) -55 (-30.39%) rusty_set_cpumask -15934 (-78.67%) -1359 (-81.62%) tp_cgroup_attach_task -57 (-27.67%) -4 (-22.22%) central_dispatch -87 (-13.68%) -9 (-14.29%)
central_init -476 (-52.19%) -12 (-25.00%)pair_dispatch -998423 (-99.84%) -58264 (-99.78%)qmap_dispatch -581 (-24.28%) -48 (-24.49%)userland_dispatch -36 (-22.78%) -4 (-23.53%)
('layered_init' and 'pair_dispatch' hit 1M on master,
but are verified ok with this patch-set).
sched_ext used for testing:
commit 2b7f3bba928f ("Merge pull request #1197 from devnexen/code_simpl4")
Eduard Zingerman (7):
bpf: copy_verifier_state() should copy 'loop_entry' field selftests/bpf: test correct loop_entry update in copy_verifier_state
bpf: don't do clean_live_states when state->loop_entry->branches > 0 selftests/bpf: check states pruning for deeply nested iterator
bpf: DFA-based liveness analysis for program registers
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 | 372 ++++++++++++++++-- .../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 | 363 +++++++++++++++++ tools/testing/selftests/bpf/progs/iters.c | 139 +++++++ .../selftests/bpf/progs/verifier_gotol.c | 6 +- .../bpf/progs/verifier_iterating_callbacks.c | 6 +- 9 files changed, 886 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
Signature · 1 line
2.47.1