Skip to content

Complete BPF verifier precision tracking support for register spills

Andrii Nakryiko bpf 4 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest10 patches 6 repliesIn review 9 of 10 applied
  2. v310 patches 14 repliesSuperseded
  3. v210 patches 11 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v17 patches37 repliesSuperseded

v3->v3 from the cover letter

- fixed up Fixes tag (Alexei);
- fixed few more selftests to not use BPF_ST instruction in inline asm

Patches in v4 9 of 10 applied

#Subject and filesSizeRepliesApplied
1/10bpf: support non-r10 register spill/fill to/from stack in precision trackinginclude/linux/bpf_verifier.h kernel/bpf/verifier.c tools/testing/selftests/bpf/progs/verifier_subprog_precision.c +1 more+169 -980 repliesApplied
2/10selftests/bpf: add stack access precision testtools/testing/selftests/bpf/progs/verifier_subprog_precision.c+59 -50 repliesApplied
3/10bpf: fix check for attempt to corrupt spilled pointerkernel/bpf/verifier.c+1 -10 repliesApplied
4/10bpf: preserve STACK_ZERO slots on partial reg spillskernel/bpf/verifier.c+23 -50 repliesApplied
5/10selftests/bpf: validate STACK_ZERO is preserved on subreg spilltools/testing/selftests/bpf/progs/verifier_spill_fill.c+40 -00 repliesApplied
6/10bpf: preserve constant zero when doing partial register restorekernel/bpf/verifier.c+21 -40 repliesApplied
7/10selftests/bpf: validate zero preservation for sub-slot loadstools/testing/selftests/bpf/progs/verifier_spill_fill.c+71 -00 repliesApplied
8/10bpf: track aligned STACK_ZERO cases as imprecise spilled registerskernel/bpf/verifier.c+7 -30 repliesApplied
9/10selftests/bpf: validate precision logic in partial_stack_load_preserves_zerostools/testing/selftests/bpf/progs/verifier_spill_fill.c+16 -04 repliesApplied
10/10bpf: use common instruction history across all statesinclude/linux/bpf_verifier.h kernel/bpf/verifier.c+54 -602 replies

Reviews trailers per patch

8 of 10 patches have a Reviewed-by or Acked-by.

PatchEduard Zingerman
1/10A-b
2/10A-b
3/10
4/10A-b
5/10A-b
6/10A-b
7/10
8/10A-b
9/10A-b
10/10A-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v4 thread

Cover letter [PATCH v4 bpf-next 00/10] Complete BPF verifier precision tracking support for register spills

Add support to BPF verifier to track and support register spill/fill to/from stack regardless if it was done through read-only R10 register (which is the only form supported today), or through a general register after copying R10 into it, while also potentially modifying offset.

Once we add register this generic spill/fill support to precision backtracking, we can take advantage of it to stop doing eager STACK_ZERO conversion on register spill. Instead we can rely on (im)precision of spilled const zero register to improve verifier state pruning efficiency. This situation of using const zero register to initialize stack slots is very common with __builtin_memset() usage or just zero-initializing variables on the stack, and it causes unnecessary state duplication, as that STACK_ZERO knowledge is often not necessary for correctness, as those zero values are never used in precise context. Thus, relying on register imprecision helps tremendously, especially in real-world BPF programs.

To make spilled const zero register behave completely equivalently to STACK_ZERO, we need to improve few other small pieces, which is done in the second part of the patch set. See individual patches for details. There are also two small bug fixes spotted during STACK_ZERO debugging.

The patch set consists of logically three changes:
- patch #1 (and corresponding tests in patch #2) is fixing/impoving precision propagation for stack spills/fills. This can be landed as a stand-alone improvement;
- patches #3 through #9 is improving verification scalability by utilizing register (im)precision instead of eager STACK_ZERO. These changes depend on patch #1.
- patch #10 is a memory efficiency improvement to how instruction/jump history is tracked and maintained. It depends on patch #1, but is not strictly speaking required, even though I believe it's a good long-term solution to have a path-dependent per-instruction information. Kind of like a path-dependent counterpart to path-agnostic insn_aux array.

v3->v3:
- fixed up Fixes tag (Alexei);
- fixed few more selftests to not use BPF_ST instruction in inline asm

    directly, checked with CI, it was happy (CI);

v2->v3:
- BPF_ST instruction workaround (Eduard);
- force dereference in added tests to catch problems (Eduard);
- some commit message massaging (Alexei);
v1->v2:
- clean ups, WARN_ONCE(), insn_flags helpers added (Eduard);
- added more selftests for STACK_ZERO/STACK_MISC cases (Eduard);
- a bit more detailed explanation of effect of avoiding STACK_ZERO in favor

    of register spill in patch #8 commit (Alexei);

- global shared instruction history refactoring moved to be the last patch in the series to make it easier to revert it, if applied (Alexei).

Andrii Nakryiko (10):
bpf: support non-r10 register spill/fill to/from stack in precision
tracking
selftests/bpf: add stack access precision test
bpf: fix check for attempt to corrupt spilled pointer
bpf: preserve STACK_ZERO slots on partial reg spills selftests/bpf: validate STACK_ZERO is preserved on subreg spill
bpf: preserve constant zero when doing partial register restore selftests/bpf: validate zero preservation for sub-slot loads
bpf: track aligned STACK_ZERO cases as imprecise spilled registers selftests/bpf: validate precision logic in
partial_stack_load_preserves_zeros
bpf: use common instruction history across all states

 include/linux/bpf_verifier.h                  |  42 ++-
 kernel/bpf/verifier.c                         | 297 +++++++++++-------
 .../selftests/bpf/progs/verifier_spill_fill.c | 127 ++++++++
 .../bpf/progs/verifier_subprog_precision.c    |  87 ++++-
 .../testing/selftests/bpf/verifier/precise.c  |  38 ++-
 5 files changed, 438 insertions(+), 153 deletions(-)
Signature · 1 line
2.34.1