bpf: compute SCC for BPF program control flow graph
Get series with b4
b4 am [email protected]Versions newest first
- v1 Latest4 patches 5 repliesIn review
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/4 | bpf: compute SCCs in program control flow graphinclude/ kernel/ | +182 | 0 replies | |
| 2/4 | bpf: frame_insn_idx() utility functionkernel/ | +9 | 0 replies | |
| 3/4 | bpf: use SCC info instead of loop_entryinclude/ kernel/ | +249 | 5 replies | |
| 4/4 | selftests/bpf: tests with a loop state missing read/precision marktools/ | +141 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [PATCH bpf-next v1 0/4] bpf: compute SCC for BPF program control flow graph
This change addresses the cases described in [1]. These cases can be illustrated with the following diagram:
.-> A --. Assume the states are visited in the order A, B, C. | | | Assume that state B reaches a state equivalent to state A. | v v At this point, state C is not processed yet, so state A has '-- B C not received read or precision marks from state C.
As a result, these marks won't be propagated to B.
If B has incomplete marks, it is unsafe to use it in states_equal() checks.
Patch #1 introduces the function compute_scc(), which uses a slightly modified version of Tarjan's algorithm to identify loops in the program's control flow graph. The function was tested by generating random graphs and comparing its outputs with results of a simple, slower algorithm. See [2] for details.
Patch #3 leverages computed SCC information to replace bpf_verifier_state->loop_entry based logic. Instead, for states within an iterator-based loop, all registers are marked as read and precise.
Patch #4 provides examples of unsafe programs that would be accepted without this patch-set.
The change has significant negative performance impact on a number of tests and sched_ext programs:
========= selftests: master vs patch =========
File Program Insns (A) Insns (B) Insns (DIFF) ---------------------------------- ---------------------------- --------- --------- ------------------- arena_list.bpf.o arena_list_add 374 406 +32 (+8.56%) iters.bpf.o checkpoint_states_deletion 1211 1216 +5 (+0.41%) iters.bpf.o clean_live_states 588 620 +32 (+5.44%) iters.bpf.o iter_subprog_check_stacksafe 128 112 -16 (-12.50%) iters.bpf.o iter_subprog_iters 664 571 -93 (-14.01%) pyperf600_iter.bpf.o on_event 2591 5929 +3338 (+128.83%) test_usdt.bpf.o usdt12 1803 1860 +57 (+3.16%) verifier_iterating_callbacks.bpf.o cond_break1 100 86633 +86533 (+86533.00%) verifier_iterating_callbacks.bpf.o cond_break2 90 110 +20 (+22.22%)
Total progs: 3587
Old success: 2070
New success: 2070
States diff min: -15.38%
States diff max: 78660.00%
-20 .. -10 %: 1 -10 .. 0 %: 1 0 .. 5 %: 3581 5 .. 15 %: 1 30 .. 40 %: 1 120 .. 130 %: 1
78660 .. 78665 %: 1
========= scx: master vs patch =========
File Program Insns (A) Insns (B) Insns (DIFF) -------------- --------------------- --------- --------- ---------------- bpf.bpf.o bpfland_init 975 1012 +37 (+3.79%) bpf.bpf.o chaos_dispatch 27025 27054 +29 (+0.11%) bpf.bpf.o chaos_init 6024 6180 +156 (+2.59%) bpf.bpf.o lavd_cpu_offline 1419 1627 +208 (+14.66%) bpf.bpf.o lavd_cpu_online 1419 1627 +208 (+14.66%) bpf.bpf.o lavd_dispatch 59090 96710 +37620 (+63.67%) bpf.bpf.o lavd_init 3066 3276 +210 (+6.85%) bpf.bpf.o layered_dispatch 9040 12450 +3410 (+37.72%) bpf.bpf.o layered_dump 1890 1615 -275 (-14.55%) bpf.bpf.o layered_enqueue 6443 6400 -43 (-0.67%) bpf.bpf.o layered_init 3874 4255 +381 (+9.83%) bpf.bpf.o layered_runnable 1706 1674 -32 (-1.88%) bpf.bpf.o p2dq_dispatch 1068 1102 +34 (+3.18%) bpf.bpf.o p2dq_init 5080 5371 +291 (+5.73%) bpf.bpf.o rusty_init 35707 35758 +51 (+0.14%) bpf.bpf.o tp_cgroup_attach_task 149 203 +54 (+36.24%) scx_pair.bpf.o pair_dispatch 891 659 -232 (-26.04%) scx_qmap.bpf.o qmap_dispatch 1703 3934 +2231 (+131.00%) scx_qmap.bpf.o qmap_dump 230 316 +86 (+37.39%) scx_qmap.bpf.o qmap_init 18548 23063 +4515 (+24.34%)
Total progs: 247 Old success: 217 New success: 217 States diff min: -25.88% States diff max: 132.62% -30 .. -20 %: 1 -20 .. -10 %: 1 -5 .. 0 %: 2 0 .. 5 %: 232 5 .. 15 %: 3 15 .. 25 %: 3 25 .. 35 %: 2 35 .. 45 %: 1 50 .. 60 %: 1 130 .. 135 %: 1
[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://github.com/eddyz87/scc-test
Eduard Zingerman (4):
bpf: compute SCCs in program control flow graph
bpf: frame_insn_idx() utility function
bpf: use SCC info instead of loop_entry
selftests/bpf: tests with a loop state missing read/precision mark
include/linux/bpf_verifier.h | 46 +- kernel/bpf/verifier.c | 630 ++++++++++++++-------- tools/testing/selftests/bpf/progs/iters.c | 141 +++++ 3 files changed, 581 insertions(+), 236 deletions(-)
Signature · 1 line
2.48.1