On Mon, Dec 4, 2023 at 11:26 AM Andrii Nakryiko <andrii@xxxxxxxxxx> wrote: > > 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. > > v2->v3: > - BPF_ST instruction workaround (Eduard); ok, so I fixed this in the main partial_stack_load_preserves_zeros test, but there is at least spill_subregs_preserve_stack_zero that needs fixing as well. I'll audit all the tests thoroughly and will fix all BPF_ST uses. Eduard or Yonghong, what's the Clang version that does support BPF_ST instructions in inline asm? When would we be able to just assume those instructions are supported? > - 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 | 124 ++++++++ > .../bpf/progs/verifier_subprog_precision.c | 87 ++++- > .../testing/selftests/bpf/verifier/precise.c | 38 ++- > 5 files changed, 435 insertions(+), 153 deletions(-) > > -- > 2.34.1 >
