Skip to content

bpf: bounded loops and other features

Alexei Starovoitov bpf netdev 1 version New

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest9 patches 0 repliesNew

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/9bpf: track spill/fill of constantskernel/bpf/verifier.c+52 -150 replies
2/9selftests/bpf: fix tests due to const spill/filltools/testing/selftests/bpf/verifier/direct_packet_access.c tools/testing/selftests/bpf/verifier/helper_access_var_len.c+17 -140 replies
3/9bpf: extend is_branch_taken to registerskernel/bpf/verifier.c+13 -30 replies
4/9bpf: introduce bounded loopsinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+175 -90 replies
5/9bpf: fix callees pruning callerskernel/bpf/verifier.c+6 -50 replies
6/9selftests/bpf: fix teststools/testing/selftests/bpf/test_verifier.c tools/testing/selftests/bpf/verifier/calls.c tools/testing/selftests/bpf/verifier/cfg.c+24 -200 replies
7/9selftests/bpf: add basic verifier tests for loopstools/testing/selftests/bpf/verifier/loops1.c+161 -00 replies
8/9selftests/bpf: add realistic loop teststools/testing/selftests/bpf/prog_tests/bpf_verif_scale.c tools/testing/selftests/bpf/progs/loop1.c tools/testing/selftests/bpf/progs/loop2.c +12 more+1341 -120 replies
9/9bpf: precise scalar_value trackinginclude/linux/bpf_verifier.h kernel/bpf/verifier.c+469 -100 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH bpf-next 0/9] bpf: bounded loops and other features

Hi,

this patch set introduces verifier support for bounded loops and adds several other improvements.
Ideally they would be introduced one at a time,
but to support bounded loop the verifier needs to 'step back' in the patch 1. That patch introduces tracking of spill/fill of constants through the stack. Though it's a useful feature it hurts cilium tests.
Patch 3 introduces another feature by extending is_branch_taken logic to 'if rX op rY' conditions. This feature is also necessary to support bounded loops.
Then patch 4 adds support for the loops while adding key heuristics with jmp_processed.
Introduction of parentage chain of verifier states in patch 4 allows patch 9 to add backtracking of precise scalar registers which finally resolves degradation from patch 1.

The end result is much faster verifier for existing programs and new support for loops.
See patch 8 for many kinds of loops that are now validated. Patch 9 is the most tricky one and could be rewritten with a different algorithm in the future.

Alexei Starovoitov (9):
bpf: track spill/fill of constants selftests/bpf: fix tests due to const spill/fill
bpf: extend is_branch_taken to registers
bpf: introduce bounded loops
bpf: fix callees pruning callers selftests/bpf: fix tests
selftests/bpf: add basic verifier tests for loops selftests/bpf: add realistic loop tests
bpf: precise scalar_value tracking

 include/linux/bpf_verifier.h                  |  69 +-
 kernel/bpf/verifier.c                         | 688 ++++++++++++++++--
 .../bpf/prog_tests/bpf_verif_scale.c          |  67 +-
 tools/testing/selftests/bpf/progs/loop1.c     |  28 +
 tools/testing/selftests/bpf/progs/loop2.c     |  28 +
 tools/testing/selftests/bpf/progs/loop3.c     |  22 +
 tools/testing/selftests/bpf/progs/pyperf.h    |   6 +-
 tools/testing/selftests/bpf/progs/pyperf600.c |   9 +
 .../selftests/bpf/progs/pyperf600_nounroll.c  |   8 +
 .../testing/selftests/bpf/progs/strobemeta.c  |  10 +
 .../testing/selftests/bpf/progs/strobemeta.h  | 528 ++++++++++++++
 .../bpf/progs/strobemeta_nounroll1.c          |   9 +
 .../bpf/progs/strobemeta_nounroll2.c          |   9 +
 .../selftests/bpf/progs/test_seg6_loop.c      | 261 +++++++
 .../selftests/bpf/progs/test_sysctl_loop1.c   |  68 ++
 .../selftests/bpf/progs/test_sysctl_loop2.c   |  69 ++
 .../selftests/bpf/progs/test_xdp_loop.c       | 231 ++++++
 tools/testing/selftests/bpf/test_verifier.c   |  11 +-
 tools/testing/selftests/bpf/verifier/calls.c  |  22 +-
 tools/testing/selftests/bpf/verifier/cfg.c    |  11 +-
 .../bpf/verifier/direct_packet_access.c       |   3 +-
 .../bpf/verifier/helper_access_var_len.c      |  28 +-
 tools/testing/selftests/bpf/verifier/loops1.c | 161 ++++
 23 files changed, 2258 insertions(+), 88 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/loop1.c
 create mode 100644 tools/testing/selftests/bpf/progs/loop2.c
 create mode 100644 tools/testing/selftests/bpf/progs/loop3.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600.c
 create mode 100644 tools/testing/selftests/bpf/progs/pyperf600_nounroll.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta.h
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_nounroll1.c
 create mode 100644 tools/testing/selftests/bpf/progs/strobemeta_nounroll2.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_seg6_loop.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_sysctl_loop1.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_sysctl_loop2.c
 create mode 100644 tools/testing/selftests/bpf/progs/test_xdp_loop.c
 create mode 100644 tools/testing/selftests/bpf/verifier/loops1.c
Signature · 1 line
2.20.0