public inbox for bpf@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH bpf-next 0/7] Complete BPF verifier precision tracking support for register spills
@ 2023-10-31  5:03 Andrii Nakryiko
  2023-10-31  5:03 ` [PATCH bpf-next 1/7] bpf: use common jump (instruction) history across all states Andrii Nakryiko
                   ` (6 more replies)
  0 siblings, 7 replies; 45+ messages in thread
From: Andrii Nakryiko @ 2023-10-31  5:03 UTC (permalink / raw)
  To: bpf, ast, daniel, martin.lau; +Cc: andrii, kernel-team

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.

Andrii Nakryiko (7):
  bpf: use common jump (instruction) history across all states
  bpf: support non-r10 register spill/fill to/from stack in precision
    tracking
  bpf: enforce precision for r0 on callback return
  bpf: fix check for attempt to corrupt spilled pointer
  bpf: preserve STACK_ZERO slots on partial reg spills
  bpf: preserve constant zero when doing partial register restore
  bpf: track aligned STACK_ZERO cases as imprecise spilled registers

 include/linux/bpf_verifier.h                  |  34 ++-
 kernel/bpf/verifier.c                         | 274 ++++++++++--------
 .../bpf/progs/verifier_subprog_precision.c    |  83 +++++-
 .../testing/selftests/bpf/verifier/precise.c  |  38 ++-
 4 files changed, 285 insertions(+), 144 deletions(-)

-- 
2.34.1


^ permalink raw reply	[flat|nested] 45+ messages in thread

end of thread, other threads:[~2023-11-12 14:05 UTC | newest]

Thread overview: 45+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2023-10-31  5:03 [PATCH bpf-next 0/7] Complete BPF verifier precision tracking support for register spills Andrii Nakryiko
2023-10-31  5:03 ` [PATCH bpf-next 1/7] bpf: use common jump (instruction) history across all states Andrii Nakryiko
2023-11-09 15:20   ` Eduard Zingerman
2023-11-09 16:13     ` Alexei Starovoitov
2023-11-09 17:28       ` Andrii Nakryiko
2023-11-09 19:29         ` Alexei Starovoitov
2023-11-09 19:49           ` Andrii Nakryiko
2023-11-09 20:39             ` Andrii Nakryiko
2023-11-09 22:05               ` Alexei Starovoitov
2023-11-09 22:57                 ` Andrii Nakryiko
2023-11-11  4:29                   ` Andrii Nakryiko
2023-10-31  5:03 ` [PATCH bpf-next 2/7] bpf: support non-r10 register spill/fill to/from stack in precision tracking Andrii Nakryiko
2023-11-09 15:20   ` Eduard Zingerman
2023-11-09 17:20     ` Andrii Nakryiko
2023-11-09 18:20       ` Eduard Zingerman
2023-11-10  5:48         ` Andrii Nakryiko
2023-11-12  1:57           ` Andrii Nakryiko
2023-11-12 14:05             ` Eduard Zingerman
2023-10-31  5:03 ` [PATCH bpf-next 3/7] bpf: enforce precision for r0 on callback return Andrii Nakryiko
2023-11-09 15:20   ` Eduard Zingerman
2023-11-09 17:32     ` Andrii Nakryiko
2023-11-09 17:38       ` Eduard Zingerman
2023-11-09 17:50         ` Andrii Nakryiko
2023-11-09 17:58           ` Alexei Starovoitov
2023-11-09 18:01             ` Andrii Nakryiko
2023-11-09 18:03               ` Eduard Zingerman
2023-11-09 18:00           ` Eduard Zingerman
2023-10-31  5:03 ` [PATCH bpf-next 4/7] bpf: fix check for attempt to corrupt spilled pointer Andrii Nakryiko
2023-11-09 15:20   ` Eduard Zingerman
2023-10-31  5:03 ` [PATCH bpf-next 5/7] bpf: preserve STACK_ZERO slots on partial reg spills Andrii Nakryiko
2023-11-09 15:20   ` Eduard Zingerman
2023-11-09 17:37     ` Andrii Nakryiko
2023-11-09 17:54       ` Eduard Zingerman
2023-10-31  5:03 ` [PATCH bpf-next 6/7] bpf: preserve constant zero when doing partial register restore Andrii Nakryiko
2023-11-09 15:20   ` Eduard Zingerman
2023-11-09 17:41     ` Andrii Nakryiko
2023-11-09 19:34       ` Eduard Zingerman
2023-10-31  5:03 ` [PATCH bpf-next 7/7] bpf: track aligned STACK_ZERO cases as imprecise spilled registers Andrii Nakryiko
2023-10-31  5:22   ` Andrii Nakryiko
2023-11-01  7:56     ` Jiri Olsa
2023-11-01 16:27       ` Andrii Nakryiko
2023-11-02  9:54         ` Jiri Olsa
2023-11-09 15:21   ` Eduard Zingerman
2023-11-09 17:43     ` Andrii Nakryiko
2023-11-09 17:44       ` Eduard Zingerman

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox