bpf.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: Alexei Starovoitov <alexei.starovoitov@gmail.com>
To: davem@davemloft.net
Cc: daniel@iogearbox.net, john.fastabend@gmail.com,
	netdev@vger.kernel.org, bpf@vger.kernel.org, kernel-team@fb.com
Subject: [PATCH v2 bpf-next 2/4] bpf: Track spill/fill of bounded scalars.
Date: Thu,  8 Oct 2020 18:12:38 -0700	[thread overview]
Message-ID: <20201009011240.48506-3-alexei.starovoitov@gmail.com> (raw)
In-Reply-To: <20201009011240.48506-1-alexei.starovoitov@gmail.com>

From: Yonghong Song <yhs@fb.com>

Under register pressure the llvm may spill registers with bounds into the stack.
The verifier has to track them through spill/fill otherwise many kinds of bound
errors will be seen. The spill/fill of induction variables was already
happening. This patch extends this logic from tracking spill/fill of a constant
into any bounded register. There is no need to track spill/fill of unbounded,
since no new information will be retrieved from the stack during register fill.

Though extra stack difference could cause state pruning to be less effective, no
adverse affects were seen from this patch on selftests and on cilium programs.

Signed-off-by: Yonghong Song <yhs@fb.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Acked-by: Andrii Nakryiko <andrii@kernel.org>
---
 kernel/bpf/verifier.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index ba96f7e9bbc0..f3e36eade3d4 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2227,6 +2227,20 @@ static bool register_is_const(struct bpf_reg_state *reg)
 	return reg->type == SCALAR_VALUE && tnum_is_const(reg->var_off);
 }
 
+static bool __is_scalar_unbounded(struct bpf_reg_state *reg)
+{
+	return tnum_is_unknown(reg->var_off) &&
+	       reg->smin_value == S64_MIN && reg->smax_value == S64_MAX &&
+	       reg->umin_value == 0 && reg->umax_value == U64_MAX &&
+	       reg->s32_min_value == S32_MIN && reg->s32_max_value == S32_MAX &&
+	       reg->u32_min_value == 0 && reg->u32_max_value == U32_MAX;
+}
+
+static bool register_is_bounded(struct bpf_reg_state *reg)
+{
+	return reg->type == SCALAR_VALUE && !__is_scalar_unbounded(reg);
+}
+
 static bool __is_pointer_value(bool allow_ptr_leaks,
 			       const struct bpf_reg_state *reg)
 {
@@ -2278,7 +2292,7 @@ static int check_stack_write(struct bpf_verifier_env *env,
 	if (value_regno >= 0)
 		reg = &cur->regs[value_regno];
 
-	if (reg && size == BPF_REG_SIZE && register_is_const(reg) &&
+	if (reg && size == BPF_REG_SIZE && register_is_bounded(reg) &&
 	    !register_is_null(reg) && env->bpf_capable) {
 		if (dst_reg != BPF_REG_FP) {
 			/* The backtracking logic can only recognize explicit
-- 
2.23.0


  parent reply	other threads:[~2020-10-09  1:12 UTC|newest]

Thread overview: 21+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2020-10-09  1:12 [PATCH v2 bpf-next 0/4] bpf: Make the verifier recognize llvm register allocation patterns Alexei Starovoitov
2020-10-09  1:12 ` [PATCH v2 bpf-next 1/4] bpf: Propagate scalar ranges through register assignments Alexei Starovoitov
2020-10-09 19:42   ` John Fastabend
2020-10-09  1:12 ` Alexei Starovoitov [this message]
2020-10-09 19:49   ` [PATCH v2 bpf-next 2/4] bpf: Track spill/fill of bounded scalars John Fastabend
2020-10-09  1:12 ` [PATCH v2 bpf-next 3/4] selftests/bpf: Add profiler test Alexei Starovoitov
2020-10-09  6:49   ` Yonghong Song
2020-10-09 15:08     ` Alexei Starovoitov
2020-10-09 15:13       ` Yonghong Song
2020-10-13 19:56   ` Jiri Olsa
2020-10-13 21:03     ` Alexei Starovoitov
2020-10-13 21:56       ` Andrii Nakryiko
2020-10-15  6:09         ` Song Liu
2020-11-04 16:45           ` Jiri Olsa
2020-11-04 20:50             ` Andrii Nakryiko
2020-11-04 21:57               ` Jiri Olsa
2020-10-13 21:59       ` Jiri Olsa
2020-10-14  0:21     ` Song Liu
2020-10-09  1:12 ` [PATCH v2 bpf-next 4/4] selftests/bpf: Asm tests for the verifier regalloc tracking Alexei Starovoitov
2020-10-09 20:06   ` John Fastabend
2020-10-09 20:10 ` [PATCH v2 bpf-next 0/4] bpf: Make the verifier recognize llvm register allocation patterns patchwork-bot+netdevbpf

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20201009011240.48506-3-alexei.starovoitov@gmail.com \
    --to=alexei.starovoitov@gmail.com \
    --cc=bpf@vger.kernel.org \
    --cc=daniel@iogearbox.net \
    --cc=davem@davemloft.net \
    --cc=john.fastabend@gmail.com \
    --cc=kernel-team@fb.com \
    --cc=netdev@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body. 
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).