diff mbox series

[bpf-next,2/3] bpf: Track spill/fill of bounded scalars.

Message ID 20201006200955.12350-3-alexei.starovoitov@gmail.com (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series bpf: Make the verifier recognize llvm register allocation patterns. | expand

Commit Message

Alexei Starovoitov Oct. 6, 2020, 8:09 p.m. UTC
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>
---
 kernel/bpf/verifier.c | 16 +++++++++++++++-
 1 file changed, 15 insertions(+), 1 deletion(-)

Comments

Andrii Nakryiko Oct. 7, 2020, 3:35 a.m. UTC | #1
On Tue, Oct 6, 2020 at 1:10 PM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> 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 mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 09e17b483b0b..7553ef14c2b1 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