Skip to contentSkip to conversation

bpf: support to track BPF_JNE

PATCH Superseded Menglong Dong 3 participants 12 messages Dec 17, 2023 – Dec 19, 2023

Subsystems (4)

v4 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

v4 cover bpf: support to track BPF_JNE

For now, the reg bounds is not handled for BPF_JNE case, which can cause the failure of following case:

/* The type of "a" is u32 */

  if (a > 0 && a < 100) {
    /* the range of the register for a is [0, 99], not [1, 99],
     * and will cause the following error:
     *
     *   invalid zero-sized read
     *
     * as a can be 0.
     */
    bpf_skb_store_bytes(skb, xx, xx, a, 0);

}

In the code above, "a > 0" will be compiled to "if a == 0 goto xxx". In the TRUE branch, the dst_reg will be marked as known to 0. However, in the fallthrough(FALSE) branch, the dst_reg will not be handled, which makes the [min, max] for a is [0, 99], not [1, 99].

In the 1st patch, we reduce the range of the dst reg if the src reg is a const and is exactly the edge of the dst reg For BPF_JNE.

In the 2nd patch, we just activate the test case for this logic in range_cond(), which is committed by Andrii in the
commit 8863238993e2 ("selftests/bpf: BPF register range bounds tester").

In the 3rd patch, we convert the case above to a testcase and add it to verifier_bounds.c.

Changes since v3:
- do some adjustment to the crafted cases that we added in the 2nd patch
- add the 3rd patch

Changes since v2:
- fix a typo in the subject of the 1st patch
- add some comments to the 1st patch, as Eduard advised
- add some cases to the "crafted_cases"

Changes since v1:
- simplify the code in the 1st patch
- introduce the 2nd patch for the testing

Menglong Dong (3):
bpf: make the verifier tracks the "not equal" for regs selftests/bpf: activate the OP_NE login in range_cond() selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

 kernel/bpf/verifier.c                         | 38 ++++++++++++++++++-
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++---
 .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++
 3 files changed, 78 insertions(+), 7 deletions(-)
Signature · 1 line
2.39.2
#1 lore raw

PATCH v4 1/3 bpf: make the verifier tracks the "not equal" for regs

We can derive some new information for BPF_JNE in regs_refine_cond_op(). Take following code for example:

/* The type of "a" is u32 */

  if (a > 0 && a < 100) {
    /* the range of the register for a is [0, 99], not [1, 99],
     * and will cause the following error:
     *
     *   invalid zero-sized read
     *
     * as a can be 0.
     */
    bpf_skb_store_bytes(skb, xx, xx, a, 0);

}

In the code above, "a > 0" will be compiled to "jmp xxx if a == 0". In the TRUE branch, the dst_reg will be marked as known to 0. However, in the fallthrough(FALSE) branch, the dst_reg will not be handled, which makes the [min, max] for a is [0, 99], not [1, 99].

For BPF_JNE, we can reduce the range of the dst reg if the src reg is a const and is exactly the edge of the dst reg.

---
v2:
- fix a typo in the subject
- add some comments, as Eduard advised

---
 kernel/bpf/verifier.c | 38 +++++++++++++++++++++++++++++++++++++-
 1 file changed, 37 insertions(+), 1 deletion(-)
kernel/bpf/verifier.c +37 -1
index 1863826a4ac3..29c41d66ea6f 100644
@@ -14343,7 +14343,43 @@ static void regs_refine_cond_op(struct bpf_reg_state *reg1, struct bpf_reg_state
 		}
 		break;
 	case BPF_JNE:
-		/* we don't derive any new information for inequality yet */
+		if (!is_reg_const(reg2, is_jmp32))
+			swap(reg1, reg2);
+		if (!is_reg_const(reg2, is_jmp32))
+			break;
+
+		/* try to recompute the bound of reg1 if reg2 is a const and
+		 * is exactly the edge of reg1.
+		 */
+		val = reg_const_value(reg2, is_jmp32);
+		if (is_jmp32) {
+			/* u32_min_value is not equal to 0xffffffff at this point,
+			 * because otherwise u32_max_value is 0xffffffff as well,
+			 * in such a case both reg1 and reg2 would be constants,
+			 * jump would be predicted and reg_set_min_max() won't
+			 * be called.
+			 *
+			 * Same reasoning works for all {u,s}{min,max}{32,64} cases
+			 * below.
+			 */
+			if (reg1->u32_min_value == (u32)val)
+				reg1->u32_min_value++;
+			if (reg1->u32_max_value == (u32)val)
+				reg1->u32_max_value--;
+			if (reg1->s32_min_value == (s32)val)
+				reg1->s32_min_value++;
+			if (reg1->s32_max_value == (s32)val)
+				reg1->s32_max_value--;
+		} else {
+			if (reg1->umin_value == (u64)val)
+				reg1->umin_value++;
+			if (reg1->umax_value == (u64)val)
+				reg1->umax_value--;
+			if (reg1->smin_value == (s64)val)
+				reg1->smin_value++;
+			if (reg1->smax_value == (s64)val)
+				reg1->smax_value--;
+		}
 		break;
 	case BPF_JSET:
 		if (!is_reg_const(reg2, is_jmp32))
Signature · 1 line
2.39.2
#2 lore raw

PATCH v4 2/3 selftests/bpf: activate the OP_NE login in range_cond()

In reply to Menglong Dong

The edge range checking for the registers is supported by the verifier now, so we can activate the extended login in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.

Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.

All reg bounds testings has passed in the SLOW_TESTS mode:

$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j
Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED

---
v3:
- do some adjustment to the crafted cases that we added v2:
- add some cases to the "crafted_cases"

---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +14 -6
index 0c9abd279e18..c9dc9fe73211 100644
@@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y,
 		*newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
 		break;
 	case OP_NE:
-		/* generic case, can't derive more information */
-		*newx = range(t, x.a, x.b);
-		*newy = range(t, y.a, y.b);
-		break;
-
-		/* below extended logic is not supported by verifier just yet */
+		/* below logic is supported by the verifier now */
 		if (x.a == x.b && x.a == y.a) {
 			/* X is a constant matching left side of Y */
 			*newx = range(t, x.a, x.b);
@@ -2101,6 +2096,19 @@ static struct subtest_case crafted_cases[] = {
 	{S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},
 	{S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
 	{S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+
+	/* edge overlap testings for BPF_NE, skipped some cases that already
+	 * exist above.
+	 */
+	{U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},
+	{U64, U64, {0, U64_MAX}, {0, 0}},
+	{S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},
+	{S64, U64, {S64_MIN, 0}, {0, 0}},
+	{S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},
+	{U32, U32, {0, U32_MAX}, {0, 0}},
+	{S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
+	{S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+	{S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
 };
 
 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
Signature · 1 line
2.39.2
#3 lore raw

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

Quoted 49 lines · Menglong Dong

The edge range checking for the registers is supported by the verifier now, so we can activate the extended login in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.

Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.

All reg bounds testings has passed in the SLOW_TESTS mode:

$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j
Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED

---
v3:
- do some adjustment to the crafted cases that we added v2:
- add some cases to the "crafted_cases"

---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +4 -6
index 0c9abd279e18..c9dc9fe73211 100644
@@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y,
                *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
                break;
        case OP_NE:
-               /* generic case, can't derive more information */
-               *newx = range(t, x.a, x.b);
-               *newy = range(t, y.a, y.b);
-               break;
-
-               /* below extended logic is not supported by verifier just yet */
+               /* below logic is supported by the verifier now */
                if (x.a == x.b && x.a == y.a) {
                        /* X is a constant matching left side of Y */
                        *newx = range(t, x.a, x.b);
@@ -2101,6 +2096,19 @@ static struct subtest_case crafted_cases[] = {
        {S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},
        {S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
        {S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+
+       /* edge overlap testings for BPF_NE, skipped some cases that already
+        * exist above.

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct subtest_case crafted_cases[] = { · line 2111

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +10 -0
+        */
+       {U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},
+       {U64, U64, {0, U64_MAX}, {0, 0}},
+       {S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},
+       {S64, U64, {S64_MIN, 0}, {0, 0}},
+       {S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},
+       {U32, U32, {0, U32_MAX}, {0, 0}},
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+       {S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},

I think you're copying the style of the casts from few lines above, but (s32)S32_MIN is unnecessary. S32_MIN includes the cast already. Please remove and fix the above lines too.

#4 lore raw

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

Quoted 57 lines · Alexei Starovoitov
Quoted 55 lines · Menglong Dong

The edge range checking for the registers is supported by the verifier now, so we can activate the extended login in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.

Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.

All reg bounds testings has passed in the SLOW_TESTS mode:

$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j
Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED

---
v3:
- do some adjustment to the crafted cases that we added v2:
- add some cases to the "crafted_cases"

---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +10 -6
index 0c9abd279e18..c9dc9fe73211 100644
@@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y,
                *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
                break;
        case OP_NE:
-               /* generic case, can't derive more information */
-               *newx = range(t, x.a, x.b);
-               *newy = range(t, y.a, y.b);
-               break;
-
-               /* below extended logic is not supported by verifier just yet */
+               /* below logic is supported by the verifier now */
                if (x.a == x.b && x.a == y.a) {
                        /* X is a constant matching left side of Y */
                        *newx = range(t, x.a, x.b);
@@ -2101,6 +2096,19 @@ static struct subtest_case crafted_cases[] = {
        {S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},
        {S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
        {S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+
+       /* edge overlap testings for BPF_NE, skipped some cases that already
+        * exist above.
+        */
+       {U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},
+       {U64, U64, {0, U64_MAX}, {0, 0}},
+       {S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},
+       {S64, U64, {S64_MIN, 0}, {0, 0}},
+       {S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},
Quoted 8 lines

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct subtest_case crafted_cases[] = { · line 2111

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +4 -0
+       {U32, U32, {0, U32_MAX}, {0, 0}},
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+       {S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},

I think you're copying the style of the casts from few lines above, but (s32)S32_MIN is unnecessary. S32_MIN includes the cast already. Please remove and fix the above lines too.

Enn...yes, I simulated the usage of S32_MIN from the lines above. You are right, the s32 casting is unnecessary, I'll just keep the u32 casting.

I'll wait a while before sending the next version to see if someone else any comments on this series.

Thanks!
Menglong Dong

#5 lore raw

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

In reply to Menglong Dong
Quoted 46 lines · Menglong Dong

The edge range checking for the registers is supported by the verifier now, so we can activate the extended login in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.

Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.

All reg bounds testings has passed in the SLOW_TESTS mode:

$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j
Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED

---
v3:
- do some adjustment to the crafted cases that we added v2:
- add some cases to the "crafted_cases"

---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +1 -6
index 0c9abd279e18..c9dc9fe73211 100644
@@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y,
                *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
                break;
        case OP_NE:
-               /* generic case, can't derive more information */
-               *newx = range(t, x.a, x.b);
-               *newy = range(t, y.a, y.b);
-               break;
-
-               /* below extended logic is not supported by verifier just yet */
+               /* below logic is supported by the verifier now */
                if (x.a == x.b && x.a == y.a) {
                        /* X is a constant matching left side of Y */
                        *newx = range(t, x.a, x.b);
@@ -2101,6 +2096,19 @@ static struct subtest_case crafted_cases[] = {
        {S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},
        {S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
        {S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct subtest_case crafted_cases[] = { · line 2108

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +10 -0
+
+       /* edge overlap testings for BPF_NE, skipped some cases that already
+        * exist above.
+        */
+       {U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},
+       {U64, U64, {0, U64_MAX}, {0, 0}},
+       {S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},
+       {S64, U64, {S64_MIN, 0}, {0, 0}},
+       {S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},
+       {U32, U32, {0, U32_MAX}, {0, 0}},

missing case where we compare against U32_MAX constant?

Quoted 9 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +3 -1
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+       {S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
 };
 
 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
--

2.39.2

#6 lore raw

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

Quoted 52 lines · Andrii Nakryiko
Quoted 50 lines · Menglong Dong

The edge range checking for the registers is supported by the verifier now, so we can activate the extended login in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.

Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.

All reg bounds testings has passed in the SLOW_TESTS mode:

$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j
Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED

---
v3:
- do some adjustment to the crafted cases that we added v2:
- add some cases to the "crafted_cases"

---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +5 -6
index 0c9abd279e18..c9dc9fe73211 100644
@@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y,
                *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
                break;
        case OP_NE:
-               /* generic case, can't derive more information */
-               *newx = range(t, x.a, x.b);
-               *newy = range(t, y.a, y.b);
-               break;
-
-               /* below extended logic is not supported by verifier just yet */
+               /* below logic is supported by the verifier now */
                if (x.a == x.b && x.a == y.a) {
                        /* X is a constant matching left side of Y */
                        *newx = range(t, x.a, x.b);
@@ -2101,6 +2096,19 @@ static struct subtest_case crafted_cases[] = {
        {S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},
        {S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
        {S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+
+       /* edge overlap testings for BPF_NE, skipped some cases that already
+        * exist above.
+        */
Quoted 9 lines

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct subtest_case crafted_cases[] = { · line 2108

Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +6 -0
+       {U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},
+       {U64, U64, {0, U64_MAX}, {0, 0}},
+       {S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},
+       {S64, U64, {S64_MIN, 0}, {0, 0}},
+       {S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},
+       {U32, U32, {0, U32_MAX}, {0, 0}},

missing case where we compare against U32_MAX constant?

Hello,

There seems to already be one existing above:

{U32, S32, {0, U32_MAX}, {U32_MAX, U32_MAX}},

Quoted 9 lines
Quoted 9 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +3 -1
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+       {S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
 };
 
 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
--

2.39.2

#7 lore raw

Re: [PATCH bpf-next v4 2/3] selftests/bpf: activate the OP_NE login in range_cond()

Quoted 65 lines · Menglong Dong
Quoted 52 lines · Andrii Nakryiko
Quoted 50 lines · Menglong Dong

The edge range checking for the registers is supported by the verifier now, so we can activate the extended login in tools/testing/selftests/bpf/prog_tests/reg_bounds.c/range_cond() to test such logic.

Besides, I added some cases to the "crafted_cases" array for this logic. These cases are mainly used to test the edge of the src reg and dst reg.

All reg bounds testings has passed in the SLOW_TESTS mode:

$ export SLOW_TESTS=1 && ./test_progs -t reg_bounds -j
Summary: 65/18959832 PASSED, 0 SKIPPED, 0 FAILED

---
v3:
- do some adjustment to the crafted cases that we added v2:
- add some cases to the "crafted_cases"

---
 .../selftests/bpf/prog_tests/reg_bounds.c     | 20 +++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +5 -6
index 0c9abd279e18..c9dc9fe73211 100644
@@ -590,12 +590,7 @@ static void range_cond(enum num_t t, struct range x, struct range y,
                *newy = range(t, max_t(t, x.a, y.a), min_t(t, x.b, y.b));
                break;
        case OP_NE:
-               /* generic case, can't derive more information */
-               *newx = range(t, x.a, x.b);
-               *newy = range(t, y.a, y.b);
-               break;
-
-               /* below extended logic is not supported by verifier just yet */
+               /* below logic is supported by the verifier now */
                if (x.a == x.b && x.a == y.a) {
                        /* X is a constant matching left side of Y */
                        *newx = range(t, x.a, x.b);
@@ -2101,6 +2096,19 @@ static struct subtest_case crafted_cases[] = {
        {S32, S64, {(u32)(s32)S32_MIN, (u32)(s32)-255}, {(u32)(s32)-2, 0}},
        {S32, S64, {0, 1}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
        {S32, U32, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+
+       /* edge overlap testings for BPF_NE, skipped some cases that already
+        * exist above.
+        */
Quoted 9 lines

tools/testing/selftests/bpf/prog_tests/reg_bounds.c static struct subtest_case crafted_cases[] = { · line 2108

Quoted 6 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +6 -0
+       {U64, U64, {0, U64_MAX}, {U64_MAX, U64_MAX}},
+       {U64, U64, {0, U64_MAX}, {0, 0}},
+       {S64, U64, {S64_MIN, 0}, {S64_MIN, S64_MIN}},
+       {S64, U64, {S64_MIN, 0}, {0, 0}},
+       {S64, U64, {S64_MIN, S64_MAX}, {S64_MAX, S64_MAX}},
+       {U32, U32, {0, U32_MAX}, {0, 0}},

missing case where we compare against U32_MAX constant?

Quoted 6 lines

Hello,

There seems to already be one existing above:

{U32, S32, {0, U32_MAX}, {U32_MAX, U32_MAX}},

This one is doing S32 comparisons. For == and != it doesn't matter, but it is a different use case. So I'd add U32, U32 case nevertheless.

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
tools/testing/selftests/bpf/prog_tests/reg_bounds.c +3 -1
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {0, 0}},
+       {S32, U32, {(u32)(s32)S32_MIN, 0}, {(u32)(s32)S32_MIN, (u32)(s32)S32_MIN}},
+       {S32, U32, {(u32)(s32)S32_MIN, S32_MAX}, {S32_MAX, S32_MAX}},
 };
 
 /* Go over crafted hard-coded cases. This is fast, so we do it as part of
--

2.39.2

#8 lore raw

PATCH v4 3/3 selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

In reply to Menglong Dong

Add testcase for the logic that the verifier tracks the BPF_JNE for regs. The assembly function "reg_not_equal()" that we add is exactly converted from the following case:

  u32 a = bpf_get_prandom_u32();
  u64 b = 0;

  a %= 8;
  /* the "a > 0" here will be optimized to "a != 0" */
  if (a > 0) {
    /* now the range of a should be [1, 7] */
    bpf_skb_store_bytes(skb, 0, &b, a, 0);
  }
---
 .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
 1 file changed, 27 insertions(+)
tools/testing/selftests/bpf/progs/verifier_bounds.c +27 -0
index ec430b71730b..3fe2ce2b3f21 100644
@@ -1075,4 +1075,31 @@ l0_%=:	r0 = 0;						\
 	: __clobber_all);
 }
 
+SEC("tc")
+__description("bounds check with JMP_NE for reg edge")
+__success __retval(0)
+__naked void reg_not_equal(void)
+{
+	asm volatile ("					\
+	r6 = r1;					\
+	r1 = 0;						\
+	*(u64*)(r10 - 8) = r1;				\
+	call %[bpf_get_prandom_u32];			\
+	r4 = r0;					\
+	r4 &= 7;					\
+	if r4 == 0 goto l0_%=;				\
+	r1 = r6;					\
+	r2 = 0;						\
+	r3 = r10;					\
+	r3 += -8;					\
+	r5 = 0;						\
+	call %[bpf_skb_store_bytes];			\
+l0_%=:	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_get_prandom_u32),
+	  __imm(bpf_skb_store_bytes)
+	: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.39.2
#9 lore raw

Re: [PATCH bpf-next v4 3/3] selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

Quoted 15 lines · Menglong Dong

Add testcase for the logic that the verifier tracks the BPF_JNE for regs. The assembly function "reg_not_equal()" that we add is exactly converted from the following case:

  u32 a = bpf_get_prandom_u32();
  u64 b = 0;

  a %= 8;
  /* the "a > 0" here will be optimized to "a != 0" */
  if (a > 0) {
    /* now the range of a should be [1, 7] */
    bpf_skb_store_bytes(skb, 0, &b, a, 0);
  }
Quoted 5 lines
---
 .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
 1 file changed, 27 insertions(+)

LGTM, but please add a comment that we rely on bpf_skb_store_byte's 4th argument being defined as ARG_CONST_SIZE, so zero is not allowed. And that r4 == 0 check is providing us this exclusion of zero from initial [0, 7] range.

tools/testing/selftests/bpf/progs/verifier_bounds.c l0_%=: r0 = 0; \ · line 1081

Quoted 12 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +4 -0
index ec430b71730b..3fe2ce2b3f21 100644
@@ -1075,4 +1075,31 @@ l0_%=:   r0 = 0;                                         \
        : __clobber_all);
 }
 
+SEC("tc")
+__description("bounds check with JMP_NE for reg edge")
+__success __retval(0)
+__naked void reg_not_equal(void)

technically, you are testing r4 == 0 :) so maybe call the test reg_equal_const or something. And then add similar test where you actually have r4 != 0, called req_no_equal_const?

Quoted 27 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +23 -1
+{
+       asm volatile ("                                 \
+       r6 = r1;                                        \
+       r1 = 0;                                         \
+       *(u64*)(r10 - 8) = r1;                          \
+       call %[bpf_get_prandom_u32];                    \
+       r4 = r0;                                        \
+       r4 &= 7;                                        \
+       if r4 == 0 goto l0_%=;                          \
+       r1 = r6;                                        \
+       r2 = 0;                                         \
+       r3 = r10;                                       \
+       r3 += -8;                                       \
+       r5 = 0;                                         \
+       call %[bpf_skb_store_bytes];                    \
+l0_%=: r0 = 0;                                         \
+       exit;                                           \
+"      :
+       : __imm(bpf_get_prandom_u32),
+         __imm(bpf_skb_store_bytes)
+       : __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
--

2.39.2

#10 lore raw

Re: [PATCH bpf-next v4 3/3] selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

Quoted 23 lines · Andrii Nakryiko
Quoted 15 lines · Menglong Dong

Add testcase for the logic that the verifier tracks the BPF_JNE for regs. The assembly function "reg_not_equal()" that we add is exactly converted from the following case:

  u32 a = bpf_get_prandom_u32();
  u64 b = 0;

  a %= 8;
  /* the "a > 0" here will be optimized to "a != 0" */
  if (a > 0) {
    /* now the range of a should be [1, 7] */
    bpf_skb_store_bytes(skb, 0, &b, a, 0);
  }
Quoted 5 lines
---
 .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
 1 file changed, 27 insertions(+)
Quoted 5 lines

LGTM, but please add a comment that we rely on bpf_skb_store_byte's 4th argument being defined as ARG_CONST_SIZE, so zero is not allowed. And that r4 == 0 check is providing us this exclusion of zero from initial [0, 7] range.

Okay, sounds great! BTW, should I add such a comment to the commit log or to the assembly function?

Quoted 9 lines
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +0 -0
index ec430b71730b..3fe2ce2b3f21 100644
@@ -1075,4 +1075,31 @@ l0_%=:   r0 = 0;                                         \
        : __clobber_all);
 }
 
Quoted 9 lines

tools/testing/selftests/bpf/progs/verifier_bounds.c l0_%=: r0 = 0; \ · line 1081

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +4 -0
+SEC("tc")
+__description("bounds check with JMP_NE for reg edge")
+__success __retval(0)
+__naked void reg_not_equal(void)

technically, you are testing r4 == 0 :) so maybe call the test reg_equal_const or something. And then add similar test where you actually have r4 != 0, called req_no_equal_const?

Yeah, that makes sense. I'll add such a test in the next version.

Thanks!
Menglong Dong

Quoted 27 lines
Quoted 27 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +23 -1
+{
+       asm volatile ("                                 \
+       r6 = r1;                                        \
+       r1 = 0;                                         \
+       *(u64*)(r10 - 8) = r1;                          \
+       call %[bpf_get_prandom_u32];                    \
+       r4 = r0;                                        \
+       r4 &= 7;                                        \
+       if r4 == 0 goto l0_%=;                          \
+       r1 = r6;                                        \
+       r2 = 0;                                         \
+       r3 = r10;                                       \
+       r3 += -8;                                       \
+       r5 = 0;                                         \
+       call %[bpf_skb_store_bytes];                    \
+l0_%=: r0 = 0;                                         \
+       exit;                                           \
+"      :
+       : __imm(bpf_get_prandom_u32),
+         __imm(bpf_skb_store_bytes)
+       : __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
--

2.39.2

#11 lore raw

Re: [PATCH bpf-next v4 3/3] selftests/bpf: add testcase to verifier_bounds.c for JMP_NE

Quoted 26 lines · Menglong Dong
Quoted 23 lines · Andrii Nakryiko
Quoted 20 lines · Menglong Dong

Add testcase for the logic that the verifier tracks the BPF_JNE for regs. The assembly function "reg_not_equal()" that we add is exactly converted from the following case:

  u32 a = bpf_get_prandom_u32();
  u64 b = 0;

  a %= 8;
  /* the "a > 0" here will be optimized to "a != 0" */
  if (a > 0) {
    /* now the range of a should be [1, 7] */
    bpf_skb_store_bytes(skb, 0, &b, a, 0);
  }
---
 .../selftests/bpf/progs/verifier_bounds.c     | 27 +++++++++++++++++++
 1 file changed, 27 insertions(+)
Quoted 9 lines
Quoted 5 lines

LGTM, but please add a comment that we rely on bpf_skb_store_byte's 4th argument being defined as ARG_CONST_SIZE, so zero is not allowed. And that r4 == 0 check is providing us this exclusion of zero from initial [0, 7] range.

Okay, sounds great! BTW, should I add such a comment to the commit log or to the assembly function?

I'd leave it in the code, next to the function itself

Quoted 51 lines
Quoted 9 lines
Quoted 9 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +0 -0
index ec430b71730b..3fe2ce2b3f21 100644
@@ -1075,4 +1075,31 @@ l0_%=:   r0 = 0;                                         \
        : __clobber_all);
 }
 
Quoted 9 lines

tools/testing/selftests/bpf/progs/verifier_bounds.c l0_%=: r0 = 0; \ · line 1081

Quoted 4 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +4 -0
+SEC("tc")
+__description("bounds check with JMP_NE for reg edge")
+__success __retval(0)
+__naked void reg_not_equal(void)

technically, you are testing r4 == 0 :) so maybe call the test reg_equal_const or something. And then add similar test where you actually have r4 != 0, called req_no_equal_const?

Yeah, that makes sense. I'll add such a test in the next version.

Thanks!
Menglong Dong

Quoted 27 lines
Quoted 27 lines
tools/testing/selftests/bpf/progs/verifier_bounds.c +23 -1
+{
+       asm volatile ("                                 \
+       r6 = r1;                                        \
+       r1 = 0;                                         \
+       *(u64*)(r10 - 8) = r1;                          \
+       call %[bpf_get_prandom_u32];                    \
+       r4 = r0;                                        \
+       r4 &= 7;                                        \
+       if r4 == 0 goto l0_%=;                          \
+       r1 = r6;                                        \
+       r2 = 0;                                         \
+       r3 = r10;                                       \
+       r3 += -8;                                       \
+       r5 = 0;                                         \
+       call %[bpf_skb_store_bytes];                    \
+l0_%=: r0 = 0;                                         \
+       exit;                                           \
+"      :
+       : __imm(bpf_get_prandom_u32),
+         __imm(bpf_skb_store_bytes)
+       : __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
--

2.39.2