[bpf-next,00/10] Add precision propagation for subprogs and callbacks

Message

Andrii Nakryiko April 25, 2023, 11:49 p.m. UTC

As more and more real-world BPF programs become more complex
and increasingly use subprograms (both static and global), scalar precision
tracking and its (previously weak) support for BPF subprograms (and callbacks
as a special case of that) is becoming more and more of an issue and
limitation. Couple that with increasing reliance on state equivalence (BPF
open-coded iterators have a hard requirement for state equivalence to converge
and successfully validate loops), and it becomes pretty critical to address
this limitation and make precision tracking universally supported for BPF
programs of any complexity and composition.

This patch set teaches BPF verifier to support SCALAR precision
backpropagation across multiple frames (for subprogram calls and callback
simulations) and addresses most practical situations (SCALAR stack
loads/stores using registers other than r10 being the last remaining
limitation, though thankfully rarely used in practice).

Main logic is explained in details in patch #8. The rest are preliminary
preparations, refactorings, clean ups, and fixes. See respective patches for
details.

Patch #8 has also veristat comparison of results for selftests, Cilium, and
some of Meta production BPF programs before and after these changes.

Andrii Nakryiko (10):
  veristat: add -t flag for adding BPF_F_TEST_STATE_FREQ program flag
  bpf: mark relevant stack slots scratched for register read instructions
  bpf: encapsulate precision backtracking bookkeeping
  bpf: improve precision backtrack logging
  bpf: maintain bitmasks across all active frames in __mark_chain_precision
  bpf: fix propagate_precision() logic for inner frames
  bpf: fix mark_all_scalars_precise use in mark_chain_precision
  bpf: support precision propagation in the presence of subprogs
  selftests/bpf: add precision propagation tests in the presence of subprogs
  selftests/bpf: revert iter test subprog precision workaround

 include/linux/bpf_verifier.h                  |  28 +-
 kernel/bpf/verifier.c                         | 608 ++++++++++++++----
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 tools/testing/selftests/bpf/progs/bpf_misc.h  |   4 +
 tools/testing/selftests/bpf/progs/iters.c     |  26 +-
 .../bpf/progs/verifier_subprog_precision.c    | 536 +++++++++++++++
 .../testing/selftests/bpf/verifier/precise.c  | 107 +--
 tools/testing/selftests/bpf/veristat.c        |   9 +
 8 files changed, 1107 insertions(+), 213 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_subprog_precision.c