[PATCH bpf-next v1 0/4] bpf: compute SCC for BPF program control flow graph

[Eduard Zingerman <eddyz87@gmail.com>]

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/3c6ac16b7578406e2ddd9ba889ce955748fe636b.camel@gmail.com/
[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(-)

-- 
2.48.1