Skip to contentSkip to conversation

fix a verifier failure with xor

PATCH In review Yonghong Song 5 participants 17 messages Aug 25, 2020 – Sep 4, 2020

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

cover fix a verifier failure with xor

The bpf selftest test_progs/test_sk_assign failed with llvm11 and llvm12. The reason is that the verifier did not handle xor operation and generate very conservative register bound. Patch #1 tries to fix the verifier issue and Patch #2 added additional tests in selftest test_verifier.

Yonghong Song (2):
bpf: fix a verifier failure with xor selftests/bpf: add verifier tests for xor operation

 kernel/bpf/verifier.c                         |  66 ++++++++
 tools/testing/selftests/bpf/verifier/bounds.c | 146 ++++++++++++++++++
 2 files changed, 212 insertions(+)
Signature · 1 line
2.24.1
#1 lore raw

PATCH 1/2 bpf: fix a verifier failure with xor

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which is not handled properly in verifier. The following illustrates the problem:

16: (b4) w5 = 0
17: ... R5_w=inv0 ...
...
132: (a4) w5 ^= 1
133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
...
37: (bc) w8 = w5
38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))

          R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...

...
41: (bc) w3 = w8
42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... 45: (56) if w3 != 0x0 goto pc+1
... R3_w=inv0 ...
46: (b7) r1 = 34
47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
47: (0f) r7 += r1
48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
48: (b4) w9 = 0
49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
49: (69) r1 = *(u16 *)(r7 +0)
invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) R7 offset is outside of the packet

At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative value of w5. At insn 45, in reality the condition should be always false. But due to conservative value for w3, the verifier evaluates it could be true and this later leads to verifier failure complaining potential packet out-of-bound access.

This patch implemented proper XOR support in verifier. In the above example, we have:
132: R5=invP0
132: (a4) w5 ^= 1
133: R5_w=invP1
...
37: (bc) w8 = w5
...
41: (bc) w3 = w8
42: R3_w=invP1
...
45: (56) if w3 != 0x0 goto pc+1
47: R3_w=invP1
...
processed 353 insns ...
and the verifier can verify the program successfully.

---
 kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)
kernel/bpf/verifier.c +66 -0
index dd24503ab3d3..a08cabc0f683 100644
@@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg,
 	__update_reg_bounds(dst_reg);
 }
 
+static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg,
+				 struct bpf_reg_state *src_reg)
+{
+	bool src_known = tnum_subreg_is_const(src_reg->var_off);
+	bool dst_known = tnum_subreg_is_const(dst_reg->var_off);
+	struct tnum var32_off = tnum_subreg(dst_reg->var_off);
+	s32 smin_val = src_reg->s32_min_value;
+
+	/* Assuming scalar64_min_max_xor will be called so it is safe
+	 * to skip updating register for known case.
+	 */
+	if (src_known && dst_known)
+		return;
+
+	/* We get both minimum and maximum from the var32_off. */
+	dst_reg->u32_min_value = var32_off.value;
+	dst_reg->u32_max_value = var32_off.value | var32_off.mask;
+
+	if (dst_reg->s32_min_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u32 result into s32.
+		 */
+		dst_reg->s32_min_value = dst_reg->u32_min_value;
+		dst_reg->s32_max_value = dst_reg->u32_max_value;
+	} else {
+		dst_reg->s32_min_value = S32_MIN;
+		dst_reg->s32_max_value = S32_MAX;
+	}
+}
+
+static void scalar_min_max_xor(struct bpf_reg_state *dst_reg,
+			       struct bpf_reg_state *src_reg)
+{
+	bool src_known = tnum_is_const(src_reg->var_off);
+	bool dst_known = tnum_is_const(dst_reg->var_off);
+	s64 smin_val = src_reg->smin_value;
+
+	if (src_known && dst_known) {
+		/* dst_reg->var_off.value has been updated earlier */
+		__mark_reg_known(dst_reg, dst_reg->var_off.value);
+		return;
+	}
+
+	/* We get both minimum and maximum from the var_off. */
+	dst_reg->umin_value = dst_reg->var_off.value;
+	dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask;
+
+	if (dst_reg->smin_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u64 result into s64.
+		 */
+		dst_reg->smin_value = dst_reg->umin_value;
+		dst_reg->smax_value = dst_reg->umax_value;
+	} else {
+		dst_reg->smin_value = S64_MIN;
+		dst_reg->smax_value = S64_MAX;
+	}
+
+	__update_reg_bounds(dst_reg);
+}
+
 static void __scalar32_min_max_lsh(struct bpf_reg_state *dst_reg,
 				   u64 umin_val, u64 umax_val)
 {
@@ -6109,6 +6170,11 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
 		scalar32_min_max_or(dst_reg, &src_reg);
 		scalar_min_max_or(dst_reg, &src_reg);
 		break;
+	case BPF_XOR:
+		dst_reg->var_off = tnum_xor(dst_reg->var_off, src_reg.var_off);
+		scalar32_min_max_xor(dst_reg, &src_reg);
+		scalar_min_max_xor(dst_reg, &src_reg);
+		break;
 	case BPF_LSH:
 		if (umax_val >= insn_bitness) {
 			/* Shifts greater than 31 or 63 are undefined.
Signature · 1 line
2.24.1
#2 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 69 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which is not handled properly in verifier. The following illustrates the problem:

16: (b4) w5 = 0
17: ... R5_w=inv0 ...
...
132: (a4) w5 ^= 1
133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
...
37: (bc) w8 = w5
38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))

          R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...

...
41: (bc) w3 = w8
42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... 45: (56) if w3 != 0x0 goto pc+1
... R3_w=inv0 ...
46: (b7) r1 = 34
47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
47: (0f) r7 += r1
48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
48: (b4) w9 = 0
49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
49: (69) r1 = *(u16 *)(r7 +0)
invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) R7 offset is outside of the packet

At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative value of w5. At insn 45, in reality the condition should be always false. But due to conservative value for w3, the verifier evaluates it could be true and this later leads to verifier failure complaining potential packet out-of-bound access.

This patch implemented proper XOR support in verifier. In the above example, we have:
132: R5=invP0
132: (a4) w5 ^= 1
133: R5_w=invP1
...
37: (bc) w8 = w5
...
41: (bc) w3 = w8
42: R3_w=invP1
...
45: (56) if w3 != 0x0 goto pc+1
47: R3_w=invP1
...
processed 353 insns ...
and the verifier can verify the program successfully.

---
 kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)
kernel/bpf/verifier.c +3 -0
index dd24503ab3d3..a08cabc0f683 100644
@@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg,
 	__update_reg_bounds(dst_reg);
 }
 
+static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg,
+				 struct bpf_reg_state *src_reg)
+{

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5816

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+	bool src_known = tnum_subreg_is_const(src_reg->var_off);
+	bool dst_known = tnum_subreg_is_const(dst_reg->var_off);
+	struct tnum var32_off = tnum_subreg(dst_reg->var_off);
+	s32 smin_val = src_reg->s32_min_value;
+
+	/* Assuming scalar64_min_max_xor will be called so it is safe
+	 * to skip updating register for known case.
+	 */
+	if (src_known && dst_known)
+		return;

why?
I've looked at _and() and _or() variants that do the same and couldn't quite remember why it's ok to do so.

Quoted 16 lines
kernel/bpf/verifier.c +16 -0
+
+	/* We get both minimum and maximum from the var32_off. */
+	dst_reg->u32_min_value = var32_off.value;
+	dst_reg->u32_max_value = var32_off.value | var32_off.mask;
+
+	if (dst_reg->s32_min_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u32 result into s32.
+		 */
+		dst_reg->s32_min_value = dst_reg->u32_min_value;
+		dst_reg->s32_max_value = dst_reg->u32_max_value;
+	} else {
+		dst_reg->s32_min_value = S32_MIN;
+		dst_reg->s32_max_value = S32_MAX;
+	}
+}

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5842

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+
+static void scalar_min_max_xor(struct bpf_reg_state *dst_reg,
+			       struct bpf_reg_state *src_reg)
+{
+	bool src_known = tnum_is_const(src_reg->var_off);
+	bool dst_known = tnum_is_const(dst_reg->var_off);
+	s64 smin_val = src_reg->smin_value;
+
+	if (src_known && dst_known) {
+		/* dst_reg->var_off.value has been updated earlier */

right, but that means that there is sort-of 'bug' (unnecessary operation) that caused me a lot of head scratching.
scalar_min_max_and() and scalar_min_max_or() do the alu in similar situation:

        if (src_known && dst_known) {
                __mark_reg_known(dst_reg, dst_reg->var_off.value |
                                          src_reg->var_off.value);

I guess it's still technically correct to repeat alu operation. second & and second | won't change the value of dst_reg, but it feels that it's correct by accident?
John ?

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5849

Quoted 7 lines
kernel/bpf/verifier.c +7 -0
+		__mark_reg_known(dst_reg, dst_reg->var_off.value);
+		return;
+	}
+
+	/* We get both minimum and maximum from the var_off. */
+	dst_reg->umin_value = dst_reg->var_off.value;
+	dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask;

I think this is correct, but I hope somebody else can analyze this as well. John, Ed ?

Quoted 14 lines
kernel/bpf/verifier.c +14 -0
+
+	if (dst_reg->smin_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u64 result into s64.
+		 */
+		dst_reg->smin_value = dst_reg->umin_value;
+		dst_reg->smax_value = dst_reg->umax_value;
+	} else {
+		dst_reg->smin_value = S64_MIN;
+		dst_reg->smax_value = S64_MAX;
+	}
+
+	__update_reg_bounds(dst_reg);
+}
#3 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 76 lines · Alexei Starovoitov
Quoted 75 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which is not handled properly in verifier. The following illustrates the problem:

   16: (b4) w5 = 0
   17: ... R5_w=inv0 ...
   ...
   132: (a4) w5 ^= 1
   133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   ...
   37: (bc) w8 = w5
   38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
           R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   ...
   41: (bc) w3 = w8
   42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   45: (56) if w3 != 0x0 goto pc+1
    ... R3_w=inv0 ...
   46: (b7) r1 = 34
   47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
   47: (0f) r7 += r1
   48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
   48: (b4) w9 = 0
   49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
   49: (69) r1 = *(u16 *)(r7 +0)
   invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38)
   R7 offset is outside of the packet

At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative value of w5. At insn 45, in reality the condition should be always false. But due to conservative value for w3, the verifier evaluates it could be true and this later leads to verifier failure complaining potential packet out-of-bound access.

This patch implemented proper XOR support in verifier. In the above example, we have:

   132: R5=invP0
   132: (a4) w5 ^= 1
   133: R5_w=invP1
   ...
   37: (bc) w8 = w5
   ...
   41: (bc) w3 = w8
   42: R3_w=invP1
   ...
   45: (56) if w3 != 0x0 goto pc+1
   47: R3_w=invP1
   ...
   processed 353 insns ...

and the verifier can verify the program successfully.

---
  kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 66 insertions(+)
kernel/bpf/verifier.c +9 -0
index dd24503ab3d3..a08cabc0f683 100644
@@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg,
  	__update_reg_bounds(dst_reg);
  }
 
+static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg,
+				 struct bpf_reg_state *src_reg)
+{
+	bool src_known = tnum_subreg_is_const(src_reg->var_off);
+	bool dst_known = tnum_subreg_is_const(dst_reg->var_off);
+	struct tnum var32_off = tnum_subreg(dst_reg->var_off);
+	s32 smin_val = src_reg->s32_min_value;
+
+	/* Assuming scalar64_min_max_xor will be called so it is safe
Quoted 8 lines

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5816

Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+	 * to skip updating register for known case.
+	 */
+	if (src_known && dst_known)
+		return;

why?
I've looked at _and() and _or() variants that do the same and couldn't quite remember why it's ok to do so.

Yes, I copied what _and() and _or() did. What I thought is if both known, 64bit scalar_min_max_xor() handled this and did not go though the approximation below, so that is why we return here. John, could you confirm?

Quoted 31 lines
Quoted 17 lines
kernel/bpf/verifier.c +16 -0
+
+	/* We get both minimum and maximum from the var32_off. */
+	dst_reg->u32_min_value = var32_off.value;
+	dst_reg->u32_max_value = var32_off.value | var32_off.mask;
+
+	if (dst_reg->s32_min_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u32 result into s32.
+		 */
+		dst_reg->s32_min_value = dst_reg->u32_min_value;
+		dst_reg->s32_max_value = dst_reg->u32_max_value;
+	} else {
+		dst_reg->s32_min_value = S32_MIN;
+		dst_reg->s32_max_value = S32_MAX;
+	}
+}

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5842

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+
+static void scalar_min_max_xor(struct bpf_reg_state *dst_reg,
+			       struct bpf_reg_state *src_reg)
+{
+	bool src_known = tnum_is_const(src_reg->var_off);
+	bool dst_known = tnum_is_const(dst_reg->var_off);
+	s64 smin_val = src_reg->smin_value;
+
+	if (src_known && dst_known) {
+		/* dst_reg->var_off.value has been updated earlier */

right, but that means that there is sort-of 'bug' (unnecessary operation) that caused me a lot of head scratching.
scalar_min_max_and() and scalar_min_max_or() do the alu in similar situation:

Quoted 7 lines
         if (src_known && dst_known) {
                 __mark_reg_known(dst_reg, dst_reg->var_off.value |
                                           src_reg->var_off.value);

I guess it's still technically correct to repeat alu operation. second & and second | won't change the value of dst_reg, but it feels that it's correct by accident?
John ?

I think for or and add, additional dst_reg op src_reg is okay. For example, for "and", the computation looks like
dst = dst & src
dst = dst & src
result will be the same as
dst = dst & src
and the second is redundant and can be replaced with dst.
The same for or,
dst = dst | src
dst = dst | src
is the same as "dst = dst | src" and the second is redundant. So
for and/or, the __mark_reg_known can just take dst_reg->var_off.value,
but the current code is also correct but can be simplified.

This is not the case xor (^). The extra computation will change expected value.

Quoted 11 lines

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5849

Quoted 8 lines
kernel/bpf/verifier.c +7 -0
+		__mark_reg_known(dst_reg, dst_reg->var_off.value);
+		return;
+	}
+
+	/* We get both minimum and maximum from the var_off. */
+	dst_reg->umin_value = dst_reg->var_off.value;
+	dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask;

I think this is correct, but I hope somebody else can analyze this as well. John, Ed ?

Please do double check. Thanks.

Quoted 15 lines
Quoted 15 lines
kernel/bpf/verifier.c +14 -0
+
+	if (dst_reg->smin_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u64 result into s64.
+		 */
+		dst_reg->smin_value = dst_reg->umin_value;
+		dst_reg->smax_value = dst_reg->umax_value;
+	} else {
+		dst_reg->smin_value = S64_MIN;
+		dst_reg->smax_value = S64_MAX;
+	}
+
+	__update_reg_bounds(dst_reg);
+}
reviewer Acked-by
#4 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 56 lines · Yonghong Song
Quoted 53 lines · Alexei Starovoitov
Quoted 52 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which is not handled properly in verifier. The following illustrates the problem:

   16: (b4) w5 = 0
   17: ... R5_w=inv0 ...
   ...
   132: (a4) w5 ^= 1
   133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   ...
   37: (bc) w8 = w5
   38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
           R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   ...
   41: (bc) w3 = w8
   42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   45: (56) if w3 != 0x0 goto pc+1
    ... R3_w=inv0 ...
   46: (b7) r1 = 34
   47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
   47: (0f) r7 += r1
   48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
   48: (b4) w9 = 0
   49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
   49: (69) r1 = *(u16 *)(r7 +0)
   invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38)
   R7 offset is outside of the packet

At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative value of w5. At insn 45, in reality the condition should be always false. But due to conservative value for w3, the verifier evaluates it could be true and this later leads to verifier failure complaining potential packet out-of-bound access.

This patch implemented proper XOR support in verifier. In the above example, we have:

   132: R5=invP0
   132: (a4) w5 ^= 1
   133: R5_w=invP1
   ...
   37: (bc) w8 = w5
   ...
   41: (bc) w3 = w8
   42: R3_w=invP1
   ...
   45: (56) if w3 != 0x0 goto pc+1
   47: R3_w=invP1
   ...
   processed 353 insns ...

and the verifier can verify the program successfully.

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

---

Thanks! Although we use llvm11 (+ some extra patches) and I haven't seen this yet if I get some time I'll try to see if I can get something to generate this code.

Quoted 29 lines
Quoted 20 lines
Quoted 20 lines
  kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 66 insertions(+)
kernel/bpf/verifier.c +9 -0
index dd24503ab3d3..a08cabc0f683 100644
@@ -5801,6 +5801,67 @@ static void scalar_min_max_or(struct bpf_reg_state *dst_reg,
  	__update_reg_bounds(dst_reg);
  }
 
+static void scalar32_min_max_xor(struct bpf_reg_state *dst_reg,
+				 struct bpf_reg_state *src_reg)
+{
+	bool src_known = tnum_subreg_is_const(src_reg->var_off);
+	bool dst_known = tnum_subreg_is_const(dst_reg->var_off);
+	struct tnum var32_off = tnum_subreg(dst_reg->var_off);
+	s32 smin_val = src_reg->s32_min_value;
+
+	/* Assuming scalar64_min_max_xor will be called so it is safe
Quoted 8 lines

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5816

Quoted 4 lines
kernel/bpf/verifier.c +4 -0
+	 * to skip updating register for known case.
+	 */
+	if (src_known && dst_known)
+		return;

why?
I've looked at _and() and _or() variants that do the same and couldn't quite remember why it's ok to do so.

Quoted 43 lines

Yes, I copied what _and() and _or() did. What I thought is if both known, 64bit scalar_min_max_xor() handled this and did not go though the approximation below, so that is why we return here. John, could you confirm?

Quoted 38 lines
Quoted 17 lines
kernel/bpf/verifier.c +16 -0
+
+	/* We get both minimum and maximum from the var32_off. */
+	dst_reg->u32_min_value = var32_off.value;
+	dst_reg->u32_max_value = var32_off.value | var32_off.mask;
+
+	if (dst_reg->s32_min_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u32 result into s32.
+		 */
+		dst_reg->s32_min_value = dst_reg->u32_min_value;
+		dst_reg->s32_max_value = dst_reg->u32_max_value;
+	} else {
+		dst_reg->s32_min_value = S32_MIN;
+		dst_reg->s32_max_value = S32_MAX;
+	}
+}

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5842

Quoted 10 lines
kernel/bpf/verifier.c +10 -0
+
+static void scalar_min_max_xor(struct bpf_reg_state *dst_reg,
+			       struct bpf_reg_state *src_reg)
+{
+	bool src_known = tnum_is_const(src_reg->var_off);
+	bool dst_known = tnum_is_const(dst_reg->var_off);
+	s64 smin_val = src_reg->smin_value;
+
+	if (src_known && dst_known) {
+		/* dst_reg->var_off.value has been updated earlier */

right, but that means that there is sort-of 'bug' (unnecessary operation) that caused me a lot of head scratching.
scalar_min_max_and() and scalar_min_max_or() do the alu in similar situation:

         if (src_known && dst_known) {
                 __mark_reg_known(dst_reg, dst_reg->var_off.value |
                                           src_reg->var_off.value);

I guess it's still technically correct to repeat alu operation. second & and second | won't change the value of dst_reg, but it feels that it's correct by accident?
John ?

It is a hold-out from when we went from having a 32-bit var-off and a 64-bit var-off. I'll send a patch its clumsy and not needed for sure.

The other subtle piece here we should clean up. Its possible to have a const in the subreg but a non-const in the wider 64-bit reg. In this case we skip marking the 32-bit subreg as known and rely on the 64-bit case to handle it. But, we may if the 64-bit reg is not const fall through and update the 64-bit bounds. Then later we call __update_reg32_bounds() and this will use the var_off, previously updated. The 32-bit bounds are then updated using this var_off so they are correct even if less precise than we might expect. I believe xor is correct here as well.

I need to send another patch with a comment for the BTF_ID types. I'll add some test cases for this 64-bit non-const and subreg const so we don't break it later. I'm on the fence if we should tighten the bounds there as well. I'll see if it helps readability to do explicit 32-bit const handling there. I had it in one of the early series with the 32-bit bounds handling, but dropped for what we have now.

Quoted 15 lines

I think for or and add, additional dst_reg op src_reg is okay. For example, for "and", the computation looks like
dst = dst & src
dst = dst & src
result will be the same as
dst = dst & src
and the second is redundant and can be replaced with dst. The same for or,
dst = dst | src
dst = dst | src
is the same as "dst = dst | src" and the second is redundant. So for and/or, the __mark_reg_known can just take dst_reg->var_off.value, but the current code is also correct but can be simplified.

Quoted 2 lines

This is not the case xor (^). The extra computation will change expected value.

Right.

Quoted 13 lines
Quoted 12 lines

kernel/bpf/verifier.c static void scalar_min_max_or(struct bpf_reg_state *dst_reg, · line 5849

Quoted 9 lines
kernel/bpf/verifier.c +7 -0
+		__mark_reg_known(dst_reg, dst_reg->var_off.value);
+		return;
+	}
+
+	/* We get both minimum and maximum from the var_off. */
+	dst_reg->umin_value = dst_reg->var_off.value;
+	dst_reg->umax_value = dst_reg->var_off.value | dst_reg->var_off.mask;

I think this is correct, but I hope somebody else can analyze this as well. John, Ed ?

Quoted 1 line

Please do double check. Thanks.

LGTM, but I see a couple follow up patches with tests, comments, and dropping the duplicate ALU op I'll try to do those Friday, unless someone else does them first.

Quoted 16 lines
Quoted 16 lines
Quoted 16 lines
kernel/bpf/verifier.c +14 -0
+
+	if (dst_reg->smin_value >= 0 && smin_val >= 0) {
+		/* XORing two positive sign numbers gives a positive,
+		 * so safe to cast u64 result into s64.
+		 */
+		dst_reg->smin_value = dst_reg->umin_value;
+		dst_reg->smax_value = dst_reg->umax_value;
+	} else {
+		dst_reg->smin_value = S64_MIN;
+		dst_reg->smax_value = S64_MAX;
+	}
+
+	__update_reg_bounds(dst_reg);
+}
#5 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 4 lines · John Fastabend

It is a hold-out from when we went from having a 32-bit var-off and a 64-bit var-off. I'll send a patch its clumsy and not needed for sure.

please follow up with such patches.

Quoted 10 lines

The other subtle piece here we should clean up. Its possible to have a const in the subreg but a non-const in the wider 64-bit reg. In this case we skip marking the 32-bit subreg as known and rely on the 64-bit case to handle it. But, we may if the 64-bit reg is not const fall through and update the 64-bit bounds. Then later we call __update_reg32_bounds() and this will use the var_off, previously updated. The 32-bit bounds are then updated using this var_off so they are correct even if less precise than we might expect. I believe xor is correct here as well.

makes sense. I think it's correct now, but I agree that cleaning this up would be good as well.

Quoted 7 lines

I need to send another patch with a comment for the BTF_ID types. I'll add some test cases for this 64-bit non-const and subreg const so we don't break it later. I'm on the fence if we should tighten the bounds there as well. I'll see if it helps readability to do explicit 32-bit const handling there. I had it in one of the early series with the 32-bit bounds handling, but dropped for what we have now.

Not following. Why is this related to btf_id ?

Quoted 3 lines

LGTM, but I see a couple follow up patches with tests, comments, and dropping the duplicate ALU op I'll try to do those Friday, unless someone else does them first.

yes. please :)

I've pushed this set to bpf-next in the meantime.
Thanks everyone!

#6 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 7 lines · Alexei Starovoitov
Quoted 4 lines · John Fastabend

It is a hold-out from when we went from having a 32-bit var-off and a 64-bit var-off. I'll send a patch its clumsy and not needed for sure.

please follow up with such patches.

Great will go ahead and do this.

Quoted 23 lines
Quoted 11 lines

The other subtle piece here we should clean up. Its possible to have a const in the subreg but a non-const in the wider 64-bit reg. In this case we skip marking the 32-bit subreg as known and rely on the 64-bit case to handle it. But, we may if the 64-bit reg is not const fall through and update the 64-bit bounds. Then later we call __update_reg32_bounds() and this will use the var_off, previously updated. The 32-bit bounds are then updated using this var_off so they are correct even if less precise than we might expect. I believe xor is correct here as well.

makes sense. I think it's correct now, but I agree that cleaning this up would be good as well.

Quoted 7 lines

I need to send another patch with a comment for the BTF_ID types. I'll add some test cases for this 64-bit non-const and subreg const so we don't break it later. I'm on the fence if we should tighten the bounds there as well. I'll see if it helps readability to do explicit 32-bit const handling there. I had it in one of the early series with the 32-bit bounds handling, but dropped for what we have now.

Quoted 1 line

Not following. Why is this related to btf_id ?

Its not related at all. I was just looking at patches on my stack here and I have unrelated comment only patch to clarify PTR_TO_BTF_ID_OR_NULL and PTR_TO_BTF_ID.

Quoted 6 lines
Quoted 4 lines

LGTM, but I see a couple follow up patches with tests, comments, and dropping the duplicate ALU op I'll try to do those Friday, unless someone else does them first.

yes. please :)

will do.

Quoted 3 lines

I've pushed this set to bpf-next in the meantime.
Thanks everyone!

#7 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

In reply to Yonghong Song
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If yes, is there something that one can do to prevent Clang from using xor in such situations?

Quoted 56 lines

is not handled properly in verifier. The following illustrates the problem:

16: (b4) w5 = 0
17: ... R5_w=inv0 ...
...
132: (a4) w5 ^= 1
133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
...
37: (bc) w8 = w5
38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))

          R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...

...
41: (bc) w3 = w8
42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ... 45: (56) if w3 != 0x0 goto pc+1
... R3_w=inv0 ...
46: (b7) r1 = 34
47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
47: (0f) r7 += r1
48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
48: (b4) w9 = 0
49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
49: (69) r1 = *(u16 *)(r7 +0)
invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38) R7 offset is outside of the packet

At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative value of w5. At insn 45, in reality the condition should be always false. But due to conservative value for w3, the verifier evaluates it could be true and this later leads to verifier failure complaining potential packet out-of-bound access.

This patch implemented proper XOR support in verifier. In the above example, we have:
132: R5=invP0
132: (a4) w5 ^= 1
133: R5_w=invP1
...
37: (bc) w8 = w5
...
41: (bc) w3 = w8
42: R3_w=invP1
...
45: (56) if w3 != 0x0 goto pc+1
47: R3_w=invP1
...
processed 353 insns ...
and the verifier can verify the program successfully.

---
 kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)

[...]

#8 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Right.

Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

The following is a hack to prevent compiler from generating xor's.

tools/testing/selftests/bpf/progs/test_sk_assi renamed from tools/testing/selftests/bpf/progs/test_sk_assign.c +0 -0

gn.c
index 1ecd987005d2..b10ce8e9437e 100644

tools/testing/selftests/bpf/progs/test_sk_assign.c +45 -16

78 lines not on this page · raw message

The fundamental idea is the following. If you have code like

    if (cond) { BLOCK1; } else { BLOCK2; }
    BLOCK3;
    if (cond) { BLOCK4; } else { BLOCK5; }
change the source code to
    if (cond) { BLOCK1; BLOCK3; BLOCK4; }
    else { BLOCK2; BLOCK3; BLOCK4; }

If the condition is used in two different places, the compiler might do some transformation for control flow and later on instr simplification decides to use xor in certain cases.

The new code has some code duplication. Not sure whether we should refactor the code or just add some note to selftests README.rst to describe this particular failure.

Quoted 60 lines
Quoted 57 lines

is not handled properly in verifier. The following illustrates the problem:

   16: (b4) w5 = 0
   17: ... R5_w=inv0 ...
   ...
   132: (a4) w5 ^= 1
   133: ... R5_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   ...
   37: (bc) w8 = w5
   38: ... R5=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff))
           R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   ...
   41: (bc) w3 = w8
   42: ... R3_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) ...
   45: (56) if w3 != 0x0 goto pc+1
    ... R3_w=inv0 ...
   46: (b7) r1 = 34
   47: R1_w=inv34 R7=pkt(id=0,off=26,r=38,imm=0)
   47: (0f) r7 += r1
   48: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
   48: (b4) w9 = 0
   49: R1_w=invP34 R3_w=inv0 R7_w=pkt(id=0,off=60,r=38,imm=0)
   49: (69) r1 = *(u16 *)(r7 +0)
   invalid access to packet, off=60 size=2, R7(id=0,off=60,r=38)
   R7 offset is outside of the packet

At above insn 132, w5 = 0, but after w5 ^= 1, we give a really conservative value of w5. At insn 45, in reality the condition should be always false. But due to conservative value for w3, the verifier evaluates it could be true and this later leads to verifier failure complaining potential packet out-of-bound access.

This patch implemented proper XOR support in verifier. In the above example, we have:

   132: R5=invP0
   132: (a4) w5 ^= 1
   133: R5_w=invP1
   ...
   37: (bc) w8 = w5
   ...
   41: (bc) w3 = w8
   42: R3_w=invP1
   ...
   45: (56) if w3 != 0x0 goto pc+1
   47: R3_w=invP1
   ...
   processed 353 insns ...

and the verifier can verify the program successfully.

---
  kernel/bpf/verifier.c | 66 +++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 66 insertions(+)

[...]

#9 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 11 lines · Yonghong Song
Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Quoted 7 lines

Right.

Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

Another option would be to move it out of the isAsCheapAsAMove on the llvm side. But, probably better to force the workaround until kernels get support. Even with it being more expensive it wouldn't mean we never get it so likely not a great idea. Just thought it might be worth mentioning. If you have your own llvm and don't have these kernels yet it looks like a win.

Quoted 2 lines

The following is a hack to prevent compiler from generating xor's.

#10 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 14 lines · John Fastabend
Quoted 13 lines · Yonghong Song
Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Right.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

Another option would be to move it out of the isAsCheapAsAMove on the

John, do you mean the following change?

llvm/lib/Target/BPF/BPFInstrInfo.td +1 -1
index 4298e2eaec04..7448a2499d40 100644
@@ -293,9 +293,9 @@ let isAsCheapAsAMove = 1 in {
   defm AND : ALU<BPF_AND, "&=", and>;
   defm SLL : ALU<BPF_LSH, "<<=", shl>;
   defm SRL : ALU<BPF_RSH, ">>=", srl>;
-  defm XOR : ALU<BPF_XOR, "^=", xor>;
   defm SRA : ALU<BPF_ARSH, "s>>=", sra>;
 }
+  defm XOR : ALU<BPF_XOR, "^=", xor>;
   defm MUL : ALU<BPF_MUL, "*=", mul>;
   defm DIV : ALU<BPF_DIV, "/=", udiv>;
 }

Tried the above change with latest trunk. xor still generated :-( I did not trace down to exact llvm optimization location for this particular optimization instance.

Quoted 8 lines

llvm side. But, probably better to force the workaround until kernels get support. Even with it being more expensive it wouldn't mean we never get it so likely not a great idea. Just thought it might be worth mentioning. If you have your own llvm and don't have these kernels yet it looks like a win.

Quoted 2 lines

The following is a hack to prevent compiler from generating xor's.

#11 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 44 lines · Yonghong Song
Quoted 14 lines · John Fastabend
Quoted 13 lines · Yonghong Song
Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Right.

Quoted 7 lines
Quoted 5 lines
Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

Another option would be to move it out of the isAsCheapAsAMove on the

John, do you mean the following change?

llvm/lib/Target/BPF/BPFInstrInfo.td +1 -1
index 4298e2eaec04..7448a2499d40 100644
@@ -293,9 +293,9 @@ let isAsCheapAsAMove = 1 in {
    defm AND : ALU<BPF_AND, "&=", and>;
    defm SLL : ALU<BPF_LSH, "<<=", shl>;
    defm SRL : ALU<BPF_RSH, ">>=", srl>;
-  defm XOR : ALU<BPF_XOR, "^=", xor>;
    defm SRA : ALU<BPF_ARSH, "s>>=", sra>;
  }
+  defm XOR : ALU<BPF_XOR, "^=", xor>;
    defm MUL : ALU<BPF_MUL, "*=", mul>;
    defm DIV : ALU<BPF_DIV, "/=", udiv>;
  }
Quoted 3 lines

Tried the above change with latest trunk. xor still generated :-( I did not trace down to exact llvm optimization location for this particular optimization instance.

Agh I assumed that would work. I might have some time to mess around with it tomorrow. Now I'm just curious why that is being generated.

Thanks for trying!

#12 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

In reply to Yonghong Song
Quoted 11 lines · Yonghong Song
Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Right.

Quoted 7 lines
Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

The following is a hack to prevent compiler from generating xor's.

Wait, so this means that we can no longer tell people to just use the newest LLVM version - now we have to keep track of a minimum *and* maximum LLVM version for each kernel version?

Could we maybe try to not *keep* making it harder for people to use BPF? :/

As for the patch, sure, make the verifier smarter, but I also feel like LLVM should be fixed to not suddenly emit such xor instructions...

-Toke

#13 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 16 lines · Toke Høiland-Jørgensen
Quoted 14 lines · Yonghong Song
Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Right.

Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

Quoted 8 lines
Quoted 4 lines

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

The following is a hack to prevent compiler from generating xor's.

Wait, so this means that we can no longer tell people to just use the newest LLVM version - now we have to keep track of a minimum *and* maximum LLVM version for each kernel version?

No. The only way is forward. Everyone has to upgrade their llvm periodically.

Quoted 1 line

Could we maybe try to not *keep* making it harder for people to use BPF? :/

Whom do you mean by "we" ?

Quoted 2 lines

As for the patch, sure, make the verifier smarter, but I also feel like LLVM should be fixed to not suddenly emit such xor instructions...

I don't think there is anything to be "fixed". It's not a bug form llvm developers point of view. At least I suspect that's the response you will get if you post the same sentence on llvm-dev mailing list. If you care to help, please bisect which llvm commit introduced this change. May be author (whoever that was) will have ideas how to pessimize it specifically for bpf backend. But I suspect they will refuse to do so. The discussion about partial disable of optimizations was brought up several times. tldr optimizations cannot be disabled effectively. Pretty much all of them may cause trouble for the verifier and all of them are often necessary for the verifier as well.
Please read this thread:
http://clang-developers.42468.n3.nabble.com/Disable-certain-llvm-optimizations-at-clang-frontend-tp4068601.html

#14 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 20 lines · Alexei Starovoitov
Quoted 19 lines · Toke Høiland-Jørgensen
Quoted 17 lines · Yonghong Song
Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Right.

Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

Quoted 7 lines
Quoted 5 lines
Quoted 1 line

The following is a hack to prevent compiler from generating xor's.

Wait, so this means that we can no longer tell people to just use the newest LLVM version - now we have to keep track of a minimum *and* maximum LLVM version for each kernel version?

No. The only way is forward. Everyone has to upgrade their llvm periodically.

Right, great! But surely that implies that a regression such as that described here, where a new LLVM version turns a previously-valid program into one that no longer verifies is a bug, no?

Quoted 3 lines
Quoted 1 line

Could we maybe try to not *keep* making it harder for people to use BPF? :/

Whom do you mean by "we" ?

I mean "we as a community who would like BPF to be as useful as possible to as many people as possible". Usability is a big part of this.

Quoted 15 lines
Quoted 2 lines

As for the patch, sure, make the verifier smarter, but I also feel like LLVM should be fixed to not suddenly emit such xor instructions...

I don't think there is anything to be "fixed". It's not a bug form llvm developers point of view. At least I suspect that's the response you will get if you post the same sentence on llvm-dev mailing list. If you care to help, please bisect which llvm commit introduced this change. May be author (whoever that was) will have ideas how to pessimize it specifically for bpf backend. But I suspect they will refuse to do so. The discussion about partial disable of optimizations was brought up several times. tldr optimizations cannot be disabled effectively. Pretty much all of them may cause trouble for the verifier and all of them are often necessary for the verifier as well. Please read this thread:
http://clang-developers.42468.n3.nabble.com/Disable-certain-llvm-optimizations-at-clang-frontend-tp4068601.html

I am not enough of a compiler person to get the nuances of that discussion, but it seems that the last message[0] by Y Song seems to imply that you guys do want to fix such issues in LLVM, just not by disabling the optimisation, but at a later stage in the processing pipeline?

-Toke

[0] http://lists.llvm.org/pipermail/cfe-dev/2020-June/066015.html

#15 lore raw

Re: [PATCH bpf-next 1/2] bpf: fix a verifier failure with xor

Quoted 28 lines · Toke Høiland-Jørgensen
Quoted 26 lines · Alexei Starovoitov
Quoted 24 lines · Toke Høiland-Jørgensen
Quoted 11 lines · Yonghong Song
Quoted 7 lines · Andrii Nakryiko
Quoted 3 lines · Yonghong Song

bpf selftest test_progs/test_sk_assign failed with llvm 11 and llvm 12. Compared to llvm 10, llvm 11 and 12 generates xor instruction which

Does this mean that some perfectly working BPF programs will now fail to verify on older kernels, if compiled with llvm 11 or llvm 12? If

Right.

Quoted 7 lines
Quoted 2 lines

yes, is there something that one can do to prevent Clang from using xor in such situations?

The xor is generated by the combination of llvm simplifyCFG and instrCombine phase.

The following is a hack to prevent compiler from generating xor's.

Wait, so this means that we can no longer tell people to just use the newest LLVM version - now we have to keep track of a minimum *and* maximum LLVM version for each kernel version?

Quoted 5 lines
Quoted 1 line

No. The only way is forward. Everyone has to upgrade their llvm periodically.

Right, great! But surely that implies that a regression such as that described here, where a new LLVM version turns a previously-valid program into one that no longer verifies is a bug, no?

It's not a regression. Previous valid _compiled_ programs will load. Nothing guarantees that recompiled program will keep loading.
Even if you keep compiler and source code constant the environment could change. That risk always existed in libbcc and in anything that compiles on the fly. A new version of bpftrace may suddenly start failing existing bpftrace scripts. No one wants this, of course, but we cannot guarantee 100%.

Quoted 7 lines
Quoted 4 lines
Quoted 2 lines

Could we maybe try to not *keep* making it harder for people to use BPF? :/

Whom do you mean by "we" ?

I mean "we as a community who would like BPF to be as useful as possible to as many people as possible". Usability is a big part of this.

Of course. I completely agree, but your previous statement said that somebody "is making it harder for people to use BPF"... and I asked whom did you point finger at.
Sounds like you're saying that you are not a compiler person, so it's not your fault and some compiler person must be responsible? Well, we are all in the same boat and all are responsible for the outcome.

Quoted 17 lines
Quoted 4 lines
Quoted 3 lines

As for the patch, sure, make the verifier smarter, but I also feel like LLVM should be fixed to not suddenly emit such xor instructions...

Quoted 12 lines

I don't think there is anything to be "fixed". It's not a bug form llvm developers point of view. At least I suspect that's the response you will get if you post the same sentence on llvm-dev mailing list. If you care to help, please bisect which llvm commit introduced this change. May be author (whoever that was) will have ideas how to pessimize it specifically for bpf backend. But I suspect they will refuse to do so. The discussion about partial disable of optimizations was brought up several times. tldr optimizations cannot be disabled effectively. Pretty much all of them may cause trouble for the verifier and all of them are often necessary for the verifier as well. Please read this thread:
http://clang-developers.42468.n3.nabble.com/Disable-certain-llvm-optimizations-at-clang-frontend-tp4068601.html

Quoted 5 lines

I am not enough of a compiler person to get the nuances of that discussion, but it seems that the last message[0] by Y Song seems to imply that you guys do want to fix such issues in LLVM, just not by disabling the optimisation, but at a later stage in the processing pipeline?

Not really. The "fix such issues in LLVM" statement is missing the point. There is no _issue_ in LLVM and there is no _issue_ in the verifier. The word "fix" assigns the blame and implies a bug.
The verifier is getting smarter. LLVM is getting smarter, but they follow different religions, so to speak. Reconciling the differences is what should happen.
Inserting inline asm barriers at different stages of the compilation is a fragile hack. Both the verifier and the LLVM need to work towards each other. BPF programs are a pain to write. People keep fighting the verifier and fighting LLVM. Large progs are full of inline asm hacks (mostly written by humans) to please the verifier and force LLVM to do something that is against LLVM objectives. Yonghong is trying to come up with a set of heuristics to do this asm insertion automatically. It will help, for sure, but won't close every corner case. The verifier needs to get smarter too. Recognizing XORs in the verifier is the right thing to do. Missing XORs in older kernels is not a bug, but we might consider it a bug and backport this verifier feature to older kernels. LLVM vs verifier contest is outside of typical kernel bug vs feature classification of patches. I think we need to be creative here.

#16 lore raw

PATCH 2/2 selftests/bpf: add verifier tests for xor operation

In reply to Yonghong Song

Added some test_verifier bounds check test cases for xor operations.

  $ ./test_verifier
  ...
  #78/u bounds check for reg = 0, reg xor 1 OK
  #78/p bounds check for reg = 0, reg xor 1 OK
  #79/u bounds check for reg32 = 0, reg32 xor 1 OK
  #79/p bounds check for reg32 = 0, reg32 xor 1 OK
  #80/u bounds check for reg = 2, reg xor 3 OK
  #80/p bounds check for reg = 2, reg xor 3 OK
  #81/u bounds check for reg = any, reg xor 3 OK
  #81/p bounds check for reg = any, reg xor 3 OK
  #82/u bounds check for reg32 = any, reg32 xor 3 OK
  #82/p bounds check for reg32 = any, reg32 xor 3 OK
  #83/u bounds check for reg > 0, reg xor 3 OK
  #83/p bounds check for reg > 0, reg xor 3 OK
  #84/u bounds check for reg32 > 0, reg32 xor 3 OK
  #84/p bounds check for reg32 > 0, reg32 xor 3 OK
  ...
---
 tools/testing/selftests/bpf/verifier/bounds.c | 146 ++++++++++++++++++
 1 file changed, 146 insertions(+)
tools/testing/selftests/bpf/verifier/bounds.c +146 -0
index 4d6645f2874c..dac40de3f868 100644
@@ -557,3 +557,149 @@
 	.result = ACCEPT,
 	.flags = F_NEEDS_EFFICIENT_UNALIGNED_ACCESS,
 },
+{
+	"bounds check for reg = 0, reg xor 1",
+	.insns = {
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_MOV64_IMM(BPF_REG_1, 0),
+	BPF_ALU64_IMM(BPF_XOR, BPF_REG_1, 1),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, 1),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 8),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.result = ACCEPT,
+},
+{
+	"bounds check for reg32 = 0, reg32 xor 1",
+	.insns = {
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_MOV32_IMM(BPF_REG_1, 0),
+	BPF_ALU32_IMM(BPF_XOR, BPF_REG_1, 1),
+	BPF_JMP32_IMM(BPF_JNE, BPF_REG_1, 0, 1),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 8),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.result = ACCEPT,
+},
+{
+	"bounds check for reg = 2, reg xor 3",
+	.insns = {
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_MOV64_IMM(BPF_REG_1, 2),
+	BPF_ALU64_IMM(BPF_XOR, BPF_REG_1, 3),
+	BPF_JMP_IMM(BPF_JGT, BPF_REG_1, 0, 1),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 8),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.result = ACCEPT,
+},
+{
+	"bounds check for reg = any, reg xor 3",
+	.insns = {
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
+	BPF_ALU64_IMM(BPF_XOR, BPF_REG_1, 3),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_1, 0, 1),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 8),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.result = REJECT,
+	.errstr = "invalid access to map value",
+	.errstr_unpriv = "invalid access to map value",
+},
+{
+	"bounds check for reg32 = any, reg32 xor 3",
+	.insns = {
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
+	BPF_ALU32_IMM(BPF_XOR, BPF_REG_1, 3),
+	BPF_JMP32_IMM(BPF_JNE, BPF_REG_1, 0, 1),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 8),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.result = REJECT,
+	.errstr = "invalid access to map value",
+	.errstr_unpriv = "invalid access to map value",
+},
+{
+	"bounds check for reg > 0, reg xor 3",
+	.insns = {
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
+	BPF_JMP_IMM(BPF_JLE, BPF_REG_1, 0, 3),
+	BPF_ALU64_IMM(BPF_XOR, BPF_REG_1, 3),
+	BPF_JMP_IMM(BPF_JGE, BPF_REG_1, 0, 1),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 8),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.result = ACCEPT,
+},
+{
+	"bounds check for reg32 > 0, reg32 xor 3",
+	.insns = {
+	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_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+	BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_1, BPF_REG_0, 0),
+	BPF_JMP32_IMM(BPF_JLE, BPF_REG_1, 0, 3),
+	BPF_ALU32_IMM(BPF_XOR, BPF_REG_1, 3),
+	BPF_JMP32_IMM(BPF_JGE, BPF_REG_1, 0, 1),
+	BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 8),
+	BPF_MOV64_IMM(BPF_REG_0, 0),
+	BPF_EXIT_INSN(),
+	},
+	.fixup_map_hash_8b = { 3 },
+	.result = ACCEPT,
+},
Signature · 1 line
2.24.1