BPF Archive on lore.kernel.org
 help / color / Atom feed
* [PATCH bpf-next] bpf: Fix register equivalence tracking.
@ 2020-10-14 17:56 Alexei Starovoitov
  2020-10-14 23:09 ` Andrii Nakryiko
                   ` (2 more replies)
  0 siblings, 3 replies; 10+ messages in thread
From: Alexei Starovoitov @ 2020-10-14 17:56 UTC (permalink / raw)
  To: davem; +Cc: daniel, john.fastabend, netdev, bpf, kernel-team

From: Alexei Starovoitov <ast@kernel.org>

The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
true or false branch. In the case 'if (reg->id)' check was done on the other
branch the counter part register would have reg->id == 0 when called into
find_equal_scalars(). In such case the helper would incorrectly identify other
registers with id == 0 as equivalent and propagate the state incorrectly.
Fix it by preserving ID across reg_set_min_max().
In other words any kind of comparison operator on the scalar register
should preserve its ID to recognize:
r1 = r2
if (r1 == 20) {
  #1 here both r1 and r2 == 20
} else if (r2 < 20) {
  #2 here both r1 and r2 < 20
}

The patch is addressing #1 case. The #2 was working correctly already.

Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
---
 kernel/bpf/verifier.c                         | 38 ++++++++++++-------
 .../testing/selftests/bpf/verifier/regalloc.c | 26 +++++++++++++
 2 files changed, 51 insertions(+), 13 deletions(-)

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index c43a5e8f0818..39d7f44e7c92 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -1010,14 +1010,9 @@ static const int caller_saved[CALLER_SAVED_REGS] = {
 static void __mark_reg_not_init(const struct bpf_verifier_env *env,
 				struct bpf_reg_state *reg);
 
-/* Mark the unknown part of a register (variable offset or scalar value) as
- * known to have the value @imm.
- */
-static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
+/* This helper doesn't clear reg->id */
+static void ___mark_reg_known(struct bpf_reg_state *reg, u64 imm)
 {
-	/* Clear id, off, and union(map_ptr, range) */
-	memset(((u8 *)reg) + sizeof(reg->type), 0,
-	       offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
 	reg->var_off = tnum_const(imm);
 	reg->smin_value = (s64)imm;
 	reg->smax_value = (s64)imm;
@@ -1030,6 +1025,17 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
 	reg->u32_max_value = (u32)imm;
 }
 
+/* Mark the unknown part of a register (variable offset or scalar value) as
+ * known to have the value @imm.
+ */
+static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
+{
+	/* Clear id, off, and union(map_ptr, range) */
+	memset(((u8 *)reg) + sizeof(reg->type), 0,
+	       offsetof(struct bpf_reg_state, var_off) - sizeof(reg->type));
+	___mark_reg_known(reg, imm);
+}
+
 static void __mark_reg32_known(struct bpf_reg_state *reg, u64 imm)
 {
 	reg->var_off = tnum_const_subreg(reg->var_off, imm);
@@ -7001,14 +7007,18 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
 		struct bpf_reg_state *reg =
 			opcode == BPF_JEQ ? true_reg : false_reg;
 
-		/* For BPF_JEQ, if this is false we know nothing Jon Snow, but
-		 * if it is true we know the value for sure. Likewise for
-		 * BPF_JNE.
+		/* JEQ/JNE comparison doesn't change the register equivalence.
+		 * r1 = r2;
+		 * if (r1 == 42) goto label;
+		 * ...
+		 * label: // here both r1 and r2 are known to be 42.
+		 *
+		 * Hence when marking register as known preserve it's ID.
 		 */
 		if (is_jmp32)
 			__mark_reg32_known(reg, val32);
 		else
-			__mark_reg_known(reg, val);
+			___mark_reg_known(reg, val);
 		break;
 	}
 	case BPF_JSET:
@@ -7551,7 +7561,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 				reg_combine_min_max(&other_branch_regs[insn->src_reg],
 						    &other_branch_regs[insn->dst_reg],
 						    src_reg, dst_reg, opcode);
-			if (src_reg->id) {
+			if (src_reg->id &&
+			    !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) {
 				find_equal_scalars(this_branch, src_reg);
 				find_equal_scalars(other_branch, &other_branch_regs[insn->src_reg]);
 			}
@@ -7563,7 +7574,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
 					opcode, is_jmp32);
 	}
 
-	if (dst_reg->type == SCALAR_VALUE && dst_reg->id) {
+	if (dst_reg->type == SCALAR_VALUE && dst_reg->id &&
+	    !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) {
 		find_equal_scalars(this_branch, dst_reg);
 		find_equal_scalars(other_branch, &other_branch_regs[insn->dst_reg]);
 	}
diff --git a/tools/testing/selftests/bpf/verifier/regalloc.c b/tools/testing/selftests/bpf/verifier/regalloc.c
index ac71b824f97a..4ad7e05de706 100644
--- a/tools/testing/selftests/bpf/verifier/regalloc.c
+++ b/tools/testing/selftests/bpf/verifier/regalloc.c
@@ -241,3 +241,29 @@
 	.result = ACCEPT,
 	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
 },
+{
+	"regalloc, spill, JEQ",
+	.insns = {
+	BPF_MOV64_REG(BPF_REG_6, BPF_REG_1),
+	BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+	BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+	BPF_LD_MAP_FD(BPF_REG_1, 0),
+	BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem),
+	BPF_STX_MEM(BPF_DW, BPF_REG_10, BPF_REG_0, -8), /* spill r0 */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 0),
+	/* The verifier will walk the rest twice with r0 == 0 and r0 == map_value */
+	BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32),
+	BPF_MOV64_REG(BPF_REG_2, BPF_REG_0),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_2, 20, 0),
+	/* The verifier will walk the rest two more times with r0 == 20 and r0 == unknown */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_10, -8), /* fill r3 with map_value */
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_3, 0, 1), /* skip ldx if map_value == NULL */
+	/* Buggy verifier will think that r3 == 20 here */
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_3, 0), /* read from map_value */
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_48b = { 4 },
+	.result = ACCEPT,
+	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
+},
-- 
2.23.0


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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-14 17:56 [PATCH bpf-next] bpf: Fix register equivalence tracking Alexei Starovoitov
@ 2020-10-14 23:09 ` Andrii Nakryiko
  2020-10-15  4:04   ` John Fastabend
  2020-10-15  5:46 ` Yonghong Song
  2020-10-15 14:10 ` patchwork-bot+netdevbpf
  2 siblings, 1 reply; 10+ messages in thread
From: Andrii Nakryiko @ 2020-10-14 23:09 UTC (permalink / raw)
  To: Alexei Starovoitov
  Cc: David S. Miller, Daniel Borkmann, john fastabend, Networking,
	bpf, Kernel Team

On Wed, Oct 14, 2020 at 10:59 AM Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> From: Alexei Starovoitov <ast@kernel.org>
>
> The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> true or false branch. In the case 'if (reg->id)' check was done on the other
> branch the counter part register would have reg->id == 0 when called into
> find_equal_scalars(). In such case the helper would incorrectly identify other
> registers with id == 0 as equivalent and propagate the state incorrectly.
> Fix it by preserving ID across reg_set_min_max().
> In other words any kind of comparison operator on the scalar register
> should preserve its ID to recognize:
> r1 = r2
> if (r1 == 20) {
>   #1 here both r1 and r2 == 20
> } else if (r2 < 20) {
>   #2 here both r1 and r2 < 20
> }
>
> The patch is addressing #1 case. The #2 was working correctly already.
>
> Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> ---

Number of underscores is a bit subtle a difference, but this fixes the bug, so:

Acked-by: Andrii Nakryiko <andrii@kernel.org>


>  kernel/bpf/verifier.c                         | 38 ++++++++++++-------
>  .../testing/selftests/bpf/verifier/regalloc.c | 26 +++++++++++++
>  2 files changed, 51 insertions(+), 13 deletions(-)
>

[...]

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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-14 23:09 ` Andrii Nakryiko
@ 2020-10-15  4:04   ` John Fastabend
  2020-10-15  4:19     ` Alexei Starovoitov
  0 siblings, 1 reply; 10+ messages in thread
From: John Fastabend @ 2020-10-15  4:04 UTC (permalink / raw)
  To: Andrii Nakryiko, Alexei Starovoitov
  Cc: David S. Miller, Daniel Borkmann, john fastabend, Networking,
	bpf, Kernel Team

Andrii Nakryiko wrote:
> On Wed, Oct 14, 2020 at 10:59 AM Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > From: Alexei Starovoitov <ast@kernel.org>
> >
> > The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> > true or false branch. In the case 'if (reg->id)' check was done on the other
> > branch the counter part register would have reg->id == 0 when called into
> > find_equal_scalars(). In such case the helper would incorrectly identify other
> > registers with id == 0 as equivalent and propagate the state incorrectly.

One thought. It seems we should never have reg->id=0 in find_equal_scalars()
would it be worthwhile to add an additional check here? Something like,

  if (known_reg->id == 0)
	return

Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking
about.

> > Fix it by preserving ID across reg_set_min_max().
> > In other words any kind of comparison operator on the scalar register
> > should preserve its ID to recognize:
> > r1 = r2
> > if (r1 == 20) {
> >   #1 here both r1 and r2 == 20
> > } else if (r2 < 20) {
> >   #2 here both r1 and r2 < 20
> > }
> >
> > The patch is addressing #1 case. The #2 was working correctly already.
> >
> > Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> > Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> > ---
> 
> Number of underscores is a bit subtle a difference, but this fixes the bug, so:
> 
> Acked-by: Andrii Nakryiko <andrii@kernel.org>
> 

Nice catch,

Acked-by: John Fastabend <john.fastabend@gmail.com>

> 
> >  kernel/bpf/verifier.c                         | 38 ++++++++++++-------
> >  .../testing/selftests/bpf/verifier/regalloc.c | 26 +++++++++++++
> >  2 files changed, 51 insertions(+), 13 deletions(-)
> >
> 
> [...]

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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-15  4:04   ` John Fastabend
@ 2020-10-15  4:19     ` Alexei Starovoitov
  2020-10-15  4:27       ` John Fastabend
  0 siblings, 1 reply; 10+ messages in thread
From: Alexei Starovoitov @ 2020-10-15  4:19 UTC (permalink / raw)
  To: John Fastabend
  Cc: Andrii Nakryiko, David S. Miller, Daniel Borkmann, Networking,
	bpf, Kernel Team

On Wed, Oct 14, 2020 at 09:04:23PM -0700, John Fastabend wrote:
> Andrii Nakryiko wrote:
> > On Wed, Oct 14, 2020 at 10:59 AM Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > From: Alexei Starovoitov <ast@kernel.org>
> > >
> > > The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> > > true or false branch. In the case 'if (reg->id)' check was done on the other
> > > branch the counter part register would have reg->id == 0 when called into
> > > find_equal_scalars(). In such case the helper would incorrectly identify other
> > > registers with id == 0 as equivalent and propagate the state incorrectly.
> 
> One thought. It seems we should never have reg->id=0 in find_equal_scalars()
> would it be worthwhile to add an additional check here? Something like,
> 
>   if (known_reg->id == 0)
> 	return
>
> Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking
> about.

That cannot happen anymore due to
if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id))
check in the caller.
I prefer not to repeat the same check twice. Also I really don't like defensive programming.
if (known_reg->id == 0)
       return;
is exactly that.
If we had that already, as Andrii argued in the original thread, we would have
never noticed this issue. <, >, <= ops would have worked, but == would be
sort-of working. It would mark one branch instead of both, and sometimes
neither of the branches. I'd rather have bugs like this one hurting and caught
quickly instead of warm feeling of being safe and sailing into unknown.

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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-15  4:19     ` Alexei Starovoitov
@ 2020-10-15  4:27       ` John Fastabend
  2020-10-15  4:33         ` Alexei Starovoitov
  0 siblings, 1 reply; 10+ messages in thread
From: John Fastabend @ 2020-10-15  4:27 UTC (permalink / raw)
  To: Alexei Starovoitov, John Fastabend
  Cc: Andrii Nakryiko, David S. Miller, Daniel Borkmann, Networking,
	bpf, Kernel Team

Alexei Starovoitov wrote:
> On Wed, Oct 14, 2020 at 09:04:23PM -0700, John Fastabend wrote:
> > Andrii Nakryiko wrote:
> > > On Wed, Oct 14, 2020 at 10:59 AM Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > From: Alexei Starovoitov <ast@kernel.org>
> > > >
> > > > The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> > > > true or false branch. In the case 'if (reg->id)' check was done on the other
> > > > branch the counter part register would have reg->id == 0 when called into
> > > > find_equal_scalars(). In such case the helper would incorrectly identify other
> > > > registers with id == 0 as equivalent and propagate the state incorrectly.
> > 
> > One thought. It seems we should never have reg->id=0 in find_equal_scalars()
> > would it be worthwhile to add an additional check here? Something like,
> > 
> >   if (known_reg->id == 0)
> > 	return
> >
> > Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking
> > about.
> 
> That cannot happen anymore due to
> if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id))
> check in the caller.
> I prefer not to repeat the same check twice. Also I really don't like defensive programming.
> if (known_reg->id == 0)
>        return;
> is exactly that.
> If we had that already, as Andrii argued in the original thread, we would have
> never noticed this issue. <, >, <= ops would have worked, but == would be
> sort-of working. It would mark one branch instead of both, and sometimes
> neither of the branches. I'd rather have bugs like this one hurting and caught
> quickly instead of warm feeling of being safe and sailing into unknown.

Agree. Although a WARN_ON_ONCE would have also been caught.

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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-15  4:27       ` John Fastabend
@ 2020-10-15  4:33         ` Alexei Starovoitov
  2020-10-15  5:23           ` John Fastabend
  0 siblings, 1 reply; 10+ messages in thread
From: Alexei Starovoitov @ 2020-10-15  4:33 UTC (permalink / raw)
  To: John Fastabend
  Cc: Andrii Nakryiko, David S. Miller, Daniel Borkmann, Networking,
	bpf, Kernel Team

On Wed, Oct 14, 2020 at 09:27:17PM -0700, John Fastabend wrote:
> Alexei Starovoitov wrote:
> > On Wed, Oct 14, 2020 at 09:04:23PM -0700, John Fastabend wrote:
> > > Andrii Nakryiko wrote:
> > > > On Wed, Oct 14, 2020 at 10:59 AM Alexei Starovoitov
> > > > <alexei.starovoitov@gmail.com> wrote:
> > > > >
> > > > > From: Alexei Starovoitov <ast@kernel.org>
> > > > >
> > > > > The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> > > > > true or false branch. In the case 'if (reg->id)' check was done on the other
> > > > > branch the counter part register would have reg->id == 0 when called into
> > > > > find_equal_scalars(). In such case the helper would incorrectly identify other
> > > > > registers with id == 0 as equivalent and propagate the state incorrectly.
> > > 
> > > One thought. It seems we should never have reg->id=0 in find_equal_scalars()
> > > would it be worthwhile to add an additional check here? Something like,
> > > 
> > >   if (known_reg->id == 0)
> > > 	return
> > >
> > > Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking
> > > about.
> > 
> > That cannot happen anymore due to
> > if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id))
> > check in the caller.
> > I prefer not to repeat the same check twice. Also I really don't like defensive programming.
> > if (known_reg->id == 0)
> >        return;
> > is exactly that.
> > If we had that already, as Andrii argued in the original thread, we would have
> > never noticed this issue. <, >, <= ops would have worked, but == would be
> > sort-of working. It would mark one branch instead of both, and sometimes
> > neither of the branches. I'd rather have bugs like this one hurting and caught
> > quickly instead of warm feeling of being safe and sailing into unknown.
> 
> Agree. Although a WARN_ON_ONCE would have also been caught.

Right. Such WARN_ON_ONCE would definitely have been nice either in the caller
or in the callee. If I could have thought that id could be zero somehow here.
In retrospect it makes sense that there is possibility that IDs of regs in
this_branch and other_branch may diverge.
Hence I'm adding the warn to check for this specific divergence.

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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-15  4:33         ` Alexei Starovoitov
@ 2020-10-15  5:23           ` John Fastabend
  0 siblings, 0 replies; 10+ messages in thread
From: John Fastabend @ 2020-10-15  5:23 UTC (permalink / raw)
  To: Alexei Starovoitov, John Fastabend
  Cc: Andrii Nakryiko, David S. Miller, Daniel Borkmann, Networking,
	bpf, Kernel Team

Alexei Starovoitov wrote:
> On Wed, Oct 14, 2020 at 09:27:17PM -0700, John Fastabend wrote:
> > Alexei Starovoitov wrote:
> > > On Wed, Oct 14, 2020 at 09:04:23PM -0700, John Fastabend wrote:
> > > > Andrii Nakryiko wrote:
> > > > > On Wed, Oct 14, 2020 at 10:59 AM Alexei Starovoitov
> > > > > <alexei.starovoitov@gmail.com> wrote:
> > > > > >
> > > > > > From: Alexei Starovoitov <ast@kernel.org>
> > > > > >
> > > > > > The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> > > > > > true or false branch. In the case 'if (reg->id)' check was done on the other
> > > > > > branch the counter part register would have reg->id == 0 when called into
> > > > > > find_equal_scalars(). In such case the helper would incorrectly identify other
> > > > > > registers with id == 0 as equivalent and propagate the state incorrectly.
> > > > 
> > > > One thought. It seems we should never have reg->id=0 in find_equal_scalars()
> > > > would it be worthwhile to add an additional check here? Something like,
> > > > 
> > > >   if (known_reg->id == 0)
> > > > 	return
> > > >
> > > > Or even a WARN_ON_ONCE() there? Not sold either way, but maybe worth thinking
> > > > about.
> > > 
> > > That cannot happen anymore due to
> > > if (dst_reg->id && !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id))
> > > check in the caller.
> > > I prefer not to repeat the same check twice. Also I really don't like defensive programming.
> > > if (known_reg->id == 0)
> > >        return;
> > > is exactly that.
> > > If we had that already, as Andrii argued in the original thread, we would have
> > > never noticed this issue. <, >, <= ops would have worked, but == would be
> > > sort-of working. It would mark one branch instead of both, and sometimes
> > > neither of the branches. I'd rather have bugs like this one hurting and caught
> > > quickly instead of warm feeling of being safe and sailing into unknown.
> > 
> > Agree. Although a WARN_ON_ONCE would have also been caught.
> 
> Right. Such WARN_ON_ONCE would definitely have been nice either in the caller
> or in the callee. If I could have thought that id could be zero somehow here.
> In retrospect it makes sense that there is possibility that IDs of regs in
> this_branch and other_branch may diverge.
> Hence I'm adding the warn to check for this specific divergence.

LGTM thanks.

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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-14 17:56 [PATCH bpf-next] bpf: Fix register equivalence tracking Alexei Starovoitov
  2020-10-14 23:09 ` Andrii Nakryiko
@ 2020-10-15  5:46 ` Yonghong Song
  2020-10-15  5:48   ` Yonghong Song
  2020-10-15 14:10 ` patchwork-bot+netdevbpf
  2 siblings, 1 reply; 10+ messages in thread
From: Yonghong Song @ 2020-10-15  5:46 UTC (permalink / raw)
  To: Alexei Starovoitov, davem
  Cc: daniel, john.fastabend, netdev, bpf, kernel-team



On 10/14/20 10:56 AM, Alexei Starovoitov wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> true or false branch. In the case 'if (reg->id)' check was done on the other
> branch the counter part register would have reg->id == 0 when called into
> find_equal_scalars(). In such case the helper would incorrectly identify other
> registers with id == 0 as equivalent and propagate the state incorrectly.
> Fix it by preserving ID across reg_set_min_max().
> In other words any kind of comparison operator on the scalar register
> should preserve its ID to recognize:
> r1 = r2
> if (r1 == 20) {
>    #1 here both r1 and r2 == 20
> } else if (r2 < 20) {
>    #2 here both r1 and r2 < 20
> }
> 
> The patch is addressing #1 case. The #2 was working correctly already.
> 
> Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register assignments.")
> Signed-off-by: Alexei Starovoitov <ast@kernel.org>

This fixed an issue appeared in our production system where packets may
be incorrectly dropped.

Test-by: Yonghong Song <yhs@fb.com>


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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-15  5:46 ` Yonghong Song
@ 2020-10-15  5:48   ` Yonghong Song
  0 siblings, 0 replies; 10+ messages in thread
From: Yonghong Song @ 2020-10-15  5:48 UTC (permalink / raw)
  To: Alexei Starovoitov, davem
  Cc: daniel, john.fastabend, netdev, bpf, kernel-team



On 10/14/20 10:46 PM, Yonghong Song wrote:
> 
> 
> On 10/14/20 10:56 AM, Alexei Starovoitov wrote:
>> From: Alexei Starovoitov <ast@kernel.org>
>>
>> The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id 
>> in either
>> true or false branch. In the case 'if (reg->id)' check was done on the 
>> other
>> branch the counter part register would have reg->id == 0 when called into
>> find_equal_scalars(). In such case the helper would incorrectly 
>> identify other
>> registers with id == 0 as equivalent and propagate the state incorrectly.
>> Fix it by preserving ID across reg_set_min_max().
>> In other words any kind of comparison operator on the scalar register
>> should preserve its ID to recognize:
>> r1 = r2
>> if (r1 == 20) {
>>    #1 here both r1 and r2 == 20
>> } else if (r2 < 20) {
>>    #2 here both r1 and r2 < 20
>> }
>>
>> The patch is addressing #1 case. The #2 was working correctly already.
>>
>> Fixes: 75748837b7e5 ("bpf: Propagate scalar ranges through register 
>> assignments.")
>> Signed-off-by: Alexei Starovoitov <ast@kernel.org>
> 
> This fixed an issue appeared in our production system where packets may
> be incorrectly dropped.
> 
> Test-by: Yonghong Song <yhs@fb.com>
Sorry for typo, it should be:
   Tested-by: Yonghong Song <yhs@fb.com>

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

* Re: [PATCH bpf-next] bpf: Fix register equivalence tracking.
  2020-10-14 17:56 [PATCH bpf-next] bpf: Fix register equivalence tracking Alexei Starovoitov
  2020-10-14 23:09 ` Andrii Nakryiko
  2020-10-15  5:46 ` Yonghong Song
@ 2020-10-15 14:10 ` patchwork-bot+netdevbpf
  2 siblings, 0 replies; 10+ messages in thread
From: patchwork-bot+netdevbpf @ 2020-10-15 14:10 UTC (permalink / raw)
  To: Alexei Starovoitov
  Cc: davem, daniel, john.fastabend, netdev, bpf, kernel-team

Hello:

This patch was applied to bpf/bpf-next.git (refs/heads/master):

On Wed, 14 Oct 2020 10:56:08 -0700 you wrote:
> From: Alexei Starovoitov <ast@kernel.org>
> 
> The 64-bit JEQ/JNE handling in reg_set_min_max() was clearing reg->id in either
> true or false branch. In the case 'if (reg->id)' check was done on the other
> branch the counter part register would have reg->id == 0 when called into
> find_equal_scalars(). In such case the helper would incorrectly identify other
> registers with id == 0 as equivalent and propagate the state incorrectly.
> Fix it by preserving ID across reg_set_min_max().
> In other words any kind of comparison operator on the scalar register
> should preserve its ID to recognize:
> r1 = r2
> if (r1 == 20) {
>   #1 here both r1 and r2 == 20
> } else if (r2 < 20) {
>   #2 here both r1 and r2 < 20
> }
> 
> [...]

Here is the summary with links:
  - [bpf-next] bpf: Fix register equivalence tracking.
    https://git.kernel.org/bpf/bpf-next/c/e688c3db7ca6

You are awesome, thank you!
--
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html



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

end of thread, back to index

Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-10-14 17:56 [PATCH bpf-next] bpf: Fix register equivalence tracking Alexei Starovoitov
2020-10-14 23:09 ` Andrii Nakryiko
2020-10-15  4:04   ` John Fastabend
2020-10-15  4:19     ` Alexei Starovoitov
2020-10-15  4:27       ` John Fastabend
2020-10-15  4:33         ` Alexei Starovoitov
2020-10-15  5:23           ` John Fastabend
2020-10-15  5:46 ` Yonghong Song
2020-10-15  5:48   ` Yonghong Song
2020-10-15 14:10 ` patchwork-bot+netdevbpf

BPF Archive on lore.kernel.org

Archives are clonable:
	git clone --mirror https://lore.kernel.org/bpf/0 bpf/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 bpf bpf/ https://lore.kernel.org/bpf \
		bpf@vger.kernel.org
	public-inbox-index bpf

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://nntp.lore.kernel.org/org.kernel.vger.bpf


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git