Skip to contentSkip to conversation

bpf: Improve verifier u32 scalar equality checking

PATCH Superseded Yonghong Song 4 participants 8 messages Apr 16, 2023 – Apr 20, 2023

Subsystems (4)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

PATCH 1/2 bpf: Improve verifier u32 scalar equality checking

In [1], I tried to remove bpf-specific codes to prevent certain llvm optimizations, and add llvm TTI (target transform info) hooks to prevent those optimizations. During this process, I found
if I enable llvm SimplifyCFG:shouldFoldTwoEntryPHINode transformation, I will hit the following verification failure with selftests:

...
8: (18) r1 = 0xffffc900001b2230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
13: (bc) w2 = w1 ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (test < __NR_TESTS)
14: (a6) if w1 < 0x9 goto pc+1 16: R0=2 R1_w=scalar(umax=8,var_off=(0x0; 0xf)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6=ctx(off=0,imm=0) R10=fp0 ;

  16: (27) r2 *= 28                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
  17: (18) r3 = 0xffffc900001b2118      ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
  19: (0f) r3 += r2                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4) R3_w=map_value(off=280,ks=4,vs=564,umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)

20: (61) r2 = *(u32 *)(r3 +0)
R3 unbounded memory access, make sure to bounds check any such access
processed 97 insns (limit 1000000) max_states_per_insn 1 total_states 10 peak_states 10 mark_read 6 -- END PROG LOAD LOG --
libbpf: prog 'ingress_fwdns_prio100': failed to load: -13
libbpf: failed to load object 'test_tc_dtime'
libbpf: failed to load BPF skeleton 'test_tc_dtime': -13
...

At insn 14, with condition 'w1 < 9', register r1 is changed from an arbitrary u32 value to scalar(umax=8,var_off=(0x0; 0xf)). Register r2, however, remains as an arbitrary u32 value. Current verifier won't claim r1/r2 equality if the previous mov is alu32 ('w2 = w1').

If r1 upper 32bit value is not 0, we indeed cannot clamin r1/r2 equality after 'w2 = w1'. But in this particular case, we know r1 upper 32bit value is 0, so it is safe to claim r1/r2 equality. This patch exactly did this. For a 32bit subreg mov, if the src register upper 32bit is 0, it is okay to claim equality between src and dst registers.

With this patch, the above verification sequence becomes

...
8: (18) r1 = 0xffffc9000048e230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
13: (bc) w2 = w1 ; R1_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff))
; if (test < __NR_TESTS)
14: (a6) if w1 < 0x9 goto pc+1 ; R1_w=scalar(id=6,umin=9,umax=4294967295,var_off=(0x0; 0xffffffff))
...
from 14 to 16: R0=2 R1_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R2_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R6=ctx(off=0,imm=0) R10=fp0
16: (27) r2 *= 28 ; R2_w=scalar(umax=224,var_off=(0x0; 0xfc))
17: (18) r3 = 0xffffc9000048e118 ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
19: (0f) r3 += r2
20: (61) r2 = *(u32 *)(r3 +0) ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R3_w=map_value(off=280,ks=4,vs=564,umax=224,var_off=(0x0; 0xfc),s32_max=252,u32_max=252)
...

and eventually the bpf program can be verified successfully.

[1] https://reviews.llvm.org/D147968

---
 kernel/bpf/verifier.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +7 -2
index d6db6de3e9ea..468f002d3248 100644
@@ -12409,12 +12409,17 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 						insn->src_reg);
 					return -EACCES;
 				} else if (src_reg->type == SCALAR_VALUE) {
+					bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
+
+					if (is_src_reg_u32 && !src_reg->id)
+						src_reg->id = ++env->id_gen;
 					copy_register_state(dst_reg, src_reg);
-					/* Make sure ID is cleared otherwise
+					/* Make sure ID is cleared if src_reg is not in u32 range otherwise
 					 * dst_reg min/max could be incorrectly
 					 * propagated into src_reg by find_equal_scalars()
 					 */
-					dst_reg->id = 0;
+					if (!is_src_reg_u32)
+						dst_reg->id = 0;
 					dst_reg->live |= REG_LIVE_WRITTEN;
 					dst_reg->subreg_def = env->insn_idx + 1;
 				} else {
Signature · 1 line
2.34.1
#1 lore raw

PATCH 2/2 selftests/bpf: Add a selftest for checking subreg equality

Add a selftest to ensure subreg equality if source register upper 32bit is 0. Without previous patch, the new test will fail verification.

---
 .../selftests/bpf/prog_tests/verifier.c       |  2 ++
 .../selftests/bpf/progs/verifier_reg_equal.c  | 27 +++++++++++++++++++
 2 files changed, 29 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_reg_equal.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 73dff693d411..25bc8958dbfe 100644
@@ -31,6 +31,7 @@
 #include "verifier_meta_access.skel.h"
 #include "verifier_raw_stack.skel.h"
 #include "verifier_raw_tp_writable.skel.h"
+#include "verifier_reg_equal.skel.h"
 #include "verifier_ringbuf.skel.h"
 #include "verifier_spill_fill.skel.h"
 #include "verifier_stack_ptr.skel.h"
@@ -95,6 +96,7 @@ void test_verifier_masking(void)              { RUN(verifier_masking); }
 void test_verifier_meta_access(void)          { RUN(verifier_meta_access); }
 void test_verifier_raw_stack(void)            { RUN(verifier_raw_stack); }
 void test_verifier_raw_tp_writable(void)      { RUN(verifier_raw_tp_writable); }
+void test_verifier_reg_equal(void)            { RUN(verifier_reg_equal); }
 void test_verifier_ringbuf(void)              { RUN(verifier_ringbuf); }
 void test_verifier_spill_fill(void)           { RUN(verifier_spill_fill); }
 void test_verifier_stack_ptr(void)            { RUN(verifier_stack_ptr); }
tools/testing/selftests/bpf/progs/verifier_reg_equal.c new file +27 -0
new file mode 100644
index 000000000000..91e42dec89ad
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+SEC("socket")
+__description("check w reg equal if r reg upper32 bits 0")
+__success
+__naked void subreg_equality(void)
+{
+	asm volatile ("					\
+	call %[bpf_ktime_get_ns];			\
+	*(u64 *)(r10 - 8) = r0;				\
+	r2 = *(u32 *)(r10 - 8);				\
+	w3 = w2;					\
+	if w2 < 9 goto l0_%=;				\
+	exit;						\
+l0_%=:	if r3 < 9 goto l1_%=;				\
+	r0 -= r1;					\
+l1_%=:	exit;						\
+"	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
Signature · 1 line
2.34.1
maintainer Acked-by on v1 2/2
#2 lore raw

Re: [PATCH bpf-next 2/2] selftests/bpf: Add a selftest for checking subreg equality

Quoted 5 lines · Yonghong Song

Add a selftest to ensure subreg equality if source register upper 32bit is 0. Without previous patch, the new test will fail verification.

Quoted 59 lines
---
 .../selftests/bpf/prog_tests/verifier.c       |  2 ++
 .../selftests/bpf/progs/verifier_reg_equal.c  | 27 +++++++++++++++++++
 2 files changed, 29 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_reg_equal.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 73dff693d411..25bc8958dbfe 100644
@@ -31,6 +31,7 @@
 #include "verifier_meta_access.skel.h"
 #include "verifier_raw_stack.skel.h"
 #include "verifier_raw_tp_writable.skel.h"
+#include "verifier_reg_equal.skel.h"
 #include "verifier_ringbuf.skel.h"
 #include "verifier_spill_fill.skel.h"
 #include "verifier_stack_ptr.skel.h"
@@ -95,6 +96,7 @@ void test_verifier_masking(void)              { RUN(verifier_masking); }
 void test_verifier_meta_access(void)          { RUN(verifier_meta_access); }
 void test_verifier_raw_stack(void)            { RUN(verifier_raw_stack); }
 void test_verifier_raw_tp_writable(void)      { RUN(verifier_raw_tp_writable); }
+void test_verifier_reg_equal(void)            { RUN(verifier_reg_equal); }
 void test_verifier_ringbuf(void)              { RUN(verifier_ringbuf); }
 void test_verifier_spill_fill(void)           { RUN(verifier_spill_fill); }
 void test_verifier_stack_ptr(void)            { RUN(verifier_stack_ptr); }
tools/testing/selftests/bpf/progs/verifier_reg_equal.c new file +27 -0
new file mode 100644
index 000000000000..91e42dec89ad
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+SEC("socket")
+__description("check w reg equal if r reg upper32 bits 0")
+__success
+__naked void subreg_equality(void)
+{
+	asm volatile ("					\
+	call %[bpf_ktime_get_ns];			\
+	*(u64 *)(r10 - 8) = r0;				\
+	r2 = *(u32 *)(r10 - 8);				\
+	w3 = w2;					\
+	if w2 < 9 goto l0_%=;				\
+	exit;						\
+l0_%=:	if r3 < 9 goto l1_%=;				\
+	r0 -= r1;					\
+l1_%=:	exit;						\
+"	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";
maintainer
#3 lore raw

Re: [PATCH bpf-next 2/2] selftests/bpf: Add a selftest for checking subreg equality

In reply to Yonghong Song
Quoted 54 lines · Yonghong Song

Add a selftest to ensure subreg equality if source register upper 32bit is 0. Without previous patch, the new test will fail verification.

---
 .../selftests/bpf/prog_tests/verifier.c       |  2 ++
 .../selftests/bpf/progs/verifier_reg_equal.c  | 27 +++++++++++++++++++
 2 files changed, 29 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_reg_equal.c
tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 73dff693d411..25bc8958dbfe 100644
@@ -31,6 +31,7 @@
 #include "verifier_meta_access.skel.h"
 #include "verifier_raw_stack.skel.h"
 #include "verifier_raw_tp_writable.skel.h"
+#include "verifier_reg_equal.skel.h"
 #include "verifier_ringbuf.skel.h"
 #include "verifier_spill_fill.skel.h"
 #include "verifier_stack_ptr.skel.h"
@@ -95,6 +96,7 @@ void test_verifier_masking(void)              { RUN(verifier_masking); }
 void test_verifier_meta_access(void)          { RUN(verifier_meta_access); }
 void test_verifier_raw_stack(void)            { RUN(verifier_raw_stack); }
 void test_verifier_raw_tp_writable(void)      { RUN(verifier_raw_tp_writable); }
+void test_verifier_reg_equal(void)            { RUN(verifier_reg_equal); }
 void test_verifier_ringbuf(void)              { RUN(verifier_ringbuf); }
 void test_verifier_spill_fill(void)           { RUN(verifier_spill_fill); }
 void test_verifier_stack_ptr(void)            { RUN(verifier_stack_ptr); }
tools/testing/selftests/bpf/progs/verifier_reg_equal.c new file +17 -0
new file mode 100644
index 000000000000..91e42dec89ad
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+SEC("socket")
+__description("check w reg equal if r reg upper32 bits 0")
+__success
+__naked void subreg_equality(void)
+{
+	asm volatile ("					\
+	call %[bpf_ktime_get_ns];			\
+	*(u64 *)(r10 - 8) = r0;				\
+	r2 = *(u32 *)(r10 - 8);				\
+	w3 = w2;					\
+	if w2 < 9 goto l0_%=;				\

tools/testing/selftests/bpf/progs/verifier_reg_equal.c line 27

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_reg_equal.c new file +10 -0
+	exit;						\
+l0_%=:	if r3 < 9 goto l1_%=;				\
+	r0 -= r1;					\
+l1_%=:	exit;						\
+"	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";

Maybe add a few comments in the test case?
E.g.:

tools/testing/selftests/bpf/progs/verifier_reg_equal.c +6 -0
@@ -13,10 +13,16 @@ __naked void subreg_equality(void)
        call %[bpf_ktime_get_ns];                       \
        *(u64 *)(r10 - 8) = r0;                         \
        r2 = *(u32 *)(r10 - 8);                         \
+       /* At this point upper 4-bytes of r2 are 0,     \
+        * thus the w3 = w2 should propagate register id, \
+        * so that w2 < 9 comparison would also propagate \
+        * range for r3.                                \
+        */                                             \
        w3 = w2;                                        \
        if w2 < 9 goto l0_%=;                           \
        exit;                                           \
 l0_%=: if r3 < 9 goto l1_%=;                           \
+       /* r1 read is illegal at this point */          \
        r0 -= r1;                                       \
 l1_%=: exit;                                           \
 "      :

Also, do we need a negative test?
(E.g. like this one but with r2 = r0 w/o u32 read from stack).

#4 lore raw

Re: [PATCH bpf-next 2/2] selftests/bpf: Add a selftest for checking subreg equality

Quoted 89 lines · Eduard Zingerman
Quoted 54 lines · Yonghong Song

Add a selftest to ensure subreg equality if source register upper 32bit is 0. Without previous patch, the new test will fail verification.

---
  .../selftests/bpf/prog_tests/verifier.c       |  2 ++
  .../selftests/bpf/progs/verifier_reg_equal.c  | 27 +++++++++++++++++++
  2 files changed, 29 insertions(+)

create mode 100644 tools/testing/selftests/bpf/progs/verifier_reg_equal.c

tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 73dff693d411..25bc8958dbfe 100644
@@ -31,6 +31,7 @@
  #include "verifier_meta_access.skel.h"
  #include "verifier_raw_stack.skel.h"
  #include "verifier_raw_tp_writable.skel.h"
+#include "verifier_reg_equal.skel.h"
  #include "verifier_ringbuf.skel.h"
  #include "verifier_spill_fill.skel.h"
  #include "verifier_stack_ptr.skel.h"
@@ -95,6 +96,7 @@ void test_verifier_masking(void)              { RUN(verifier_masking); }
  void test_verifier_meta_access(void)          { RUN(verifier_meta_access); }
  void test_verifier_raw_stack(void)            { RUN(verifier_raw_stack); }
  void test_verifier_raw_tp_writable(void)      { RUN(verifier_raw_tp_writable); }
+void test_verifier_reg_equal(void)            { RUN(verifier_reg_equal); }
  void test_verifier_ringbuf(void)              { RUN(verifier_ringbuf); }
  void test_verifier_spill_fill(void)           { RUN(verifier_spill_fill); }
  void test_verifier_stack_ptr(void)            { RUN(verifier_stack_ptr); }
tools/testing/selftests/bpf/progs/verifier_reg_equal.c new file +17 -0
new file mode 100644
index 000000000000..91e42dec89ad
@@ -0,0 +1,27 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+SEC("socket")
+__description("check w reg equal if r reg upper32 bits 0")
+__success
+__naked void subreg_equality(void)
+{
+	asm volatile ("					\
+	call %[bpf_ktime_get_ns];			\
+	*(u64 *)(r10 - 8) = r0;				\
+	r2 = *(u32 *)(r10 - 8);				\
+	w3 = w2;					\
+	if w2 < 9 goto l0_%=;				\

tools/testing/selftests/bpf/progs/verifier_reg_equal.c line 27

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_reg_equal.c new file +10 -0
+	exit;						\
+l0_%=:	if r3 < 9 goto l1_%=;				\
+	r0 -= r1;					\
+l1_%=:	exit;						\
+"	:
+	: __imm(bpf_ktime_get_ns)
+	: __clobber_all);
+}
+
+char _license[] SEC("license") = "GPL";

Maybe add a few comments in the test case?
E.g.:

tools/testing/selftests/bpf/progs/verifier_reg_equal.c +6 -0
@@ -13,10 +13,16 @@ __naked void subreg_equality(void)
         call %[bpf_ktime_get_ns];                       \
         *(u64 *)(r10 - 8) = r0;                         \
         r2 = *(u32 *)(r10 - 8);                         \
+       /* At this point upper 4-bytes of r2 are 0,     \
+        * thus the w3 = w2 should propagate register id, \
+        * so that w2 < 9 comparison would also propagate \
+        * range for r3.                                \
+        */                                             \
         w3 = w2;                                        \
         if w2 < 9 goto l0_%=;                           \
         exit;                                           \
  l0_%=: if r3 < 9 goto l1_%=;                           \
+       /* r1 read is illegal at this point */          \
         r0 -= r1;                                       \
  l1_%=: exit;                                           \
  "      :
Quoted 2 lines

Also, do we need a negative test?
(E.g. like this one but with r2 = r0 w/o u32 read from stack).

Thanks for the suggestion. Will add comments for some explanation and also add a negative test.

Quoted 1 line
Acked-by on v1 1/2
#5 lore raw
In reply to Yonghong Song
Quoted 34 lines · Yonghong Song

In [1], I tried to remove bpf-specific codes to prevent certain llvm optimizations, and add llvm TTI (target transform info) hooks to prevent those optimizations. During this process, I found
if I enable llvm SimplifyCFG:shouldFoldTwoEntryPHINode transformation, I will hit the following verification failure with selftests:

...
8: (18) r1 = 0xffffc900001b2230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
13: (bc) w2 = w1 ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (test < __NR_TESTS)
14: (a6) if w1 < 0x9 goto pc+1 16: R0=2 R1_w=scalar(umax=8,var_off=(0x0; 0xf)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6=ctx(off=0,imm=0) R10=fp0 ;

  16: (27) r2 *= 28                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
  17: (18) r3 = 0xffffc900001b2118      ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
  19: (0f) r3 += r2                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4) R3_w=map_value(off=280,ks=4,vs=564,umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)

20: (61) r2 = *(u32 *)(r3 +0)
R3 unbounded memory access, make sure to bounds check any such access
processed 97 insns (limit 1000000) max_states_per_insn 1 total_states 10 peak_states 10 mark_read 6 -- END PROG LOAD LOG --
libbpf: prog 'ingress_fwdns_prio100': failed to load: -13
libbpf: failed to load object 'test_tc_dtime'
libbpf: failed to load BPF skeleton 'test_tc_dtime': -13
...

At insn 14, with condition 'w1 < 9', register r1 is changed from an arbitrary u32 value to scalar(umax=8,var_off=(0x0; 0xf)). Register r2, however, remains as an arbitrary u32 value. Current verifier won't claim r1/r2 equality if the previous mov is alu32 ('w2 = w1').

Quoted 5 lines

If r1 upper 32bit value is not 0, we indeed cannot clamin r1/r2 equality after 'w2 = w1'. But in this particular case, we know r1 upper 32bit value is 0, so it is safe to claim r1/r2 equality. This patch exactly did this. For a 32bit subreg mov, if the src register upper 32bit is 0, it is okay to claim equality between src and dst registers.

Perhaps mention in the above paragraph that this works because 32-bit ALU operations clear the upper bits? Some along the line of

A special case where r1/r2 equality can be claimed after 'w2 = w1' is when r1 upper 32bit value is 0. This is because 32bit ALU operations always clear the upper 32 bits of the destination, so 'w2 = w1' in this case is the same as 'r2 = r1'...

Quoted 20 lines

With this patch, the above verification sequence becomes

...
8: (18) r1 = 0xffffc9000048e230 ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
10: (61) r1 = *(u32 *)(r1 +0) ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
11: (79) r2 = *(u64 *)(r6 +152) ; R2_w=scalar() R6=ctx(off=0,imm=0)
; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
12: (55) if r2 != 0xb9fbeef goto pc+10 ; R2_w=195018479
13: (bc) w2 = w1 ; R1_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff))
; if (test < __NR_TESTS)
14: (a6) if w1 < 0x9 goto pc+1 ; R1_w=scalar(id=6,umin=9,umax=4294967295,var_off=(0x0; 0xffffffff))
...
from 14 to 16: R0=2 R1_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R2_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R6=ctx(off=0,imm=0) R10=fp0
16: (27) r2 *= 28 ; R2_w=scalar(umax=224,var_off=(0x0; 0xfc))
17: (18) r3 = 0xffffc9000048e118 ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
19: (0f) r3 += r2
20: (61) r2 = *(u32 *)(r3 +0) ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R3_w=map_value(off=280,ks=4,vs=564,umax=224,var_off=(0x0; 0xfc),s32_max=252,u32_max=252)
...

Quoted 5 lines

and eventually the bpf program can be verified successfully.

[1] https://reviews.llvm.org/D147968

Quoted 31 lines
---
 kernel/bpf/verifier.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +7 -2
index d6db6de3e9ea..468f002d3248 100644
@@ -12409,12 +12409,17 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
 						insn->src_reg);
 					return -EACCES;
 				} else if (src_reg->type == SCALAR_VALUE) {
+					bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
+
+					if (is_src_reg_u32 && !src_reg->id)
+						src_reg->id = ++env->id_gen;
 					copy_register_state(dst_reg, src_reg);
-					/* Make sure ID is cleared otherwise
+					/* Make sure ID is cleared if src_reg is not in u32 range otherwise
 					 * dst_reg min/max could be incorrectly
 					 * propagated into src_reg by find_equal_scalars()
 					 */
-					dst_reg->id = 0;
+					if (!is_src_reg_u32)
+						dst_reg->id = 0;
 					dst_reg->live |= REG_LIVE_WRITTEN;
 					dst_reg->subreg_def = env->insn_idx + 1;
 				} else {
Signature · 1 line
2.34.1
#6 lore raw
Quoted 41 lines · Shung-Hsi Yu
Quoted 34 lines · Yonghong Song

In [1], I tried to remove bpf-specific codes to prevent certain llvm optimizations, and add llvm TTI (target transform info) hooks to prevent those optimizations. During this process, I found
if I enable llvm SimplifyCFG:shouldFoldTwoEntryPHINode transformation, I will hit the following verification failure with selftests:

   ...
   8: (18) r1 = 0xffffc900001b2230       ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
   10: (61) r1 = *(u32 *)(r1 +0)         ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   11: (79) r2 = *(u64 *)(r6 +152)       ; R2_w=scalar() R6=ctx(off=0,imm=0)
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   12: (55) if r2 != 0xb9fbeef goto pc+10        ; R2_w=195018479
   13: (bc) w2 = w1                      ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (test < __NR_TESTS)
   14: (a6) if w1 < 0x9 goto pc+1 16: R0=2 R1_w=scalar(umax=8,var_off=(0x0; 0xf)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6=ctx(off=0,imm=0) R10=fp0
   ;
   16: (27) r2 *= 28                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
   17: (18) r3 = 0xffffc900001b2118      ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
   19: (0f) r3 += r2                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4) R3_w=map_value(off=280,ks=4,vs=564,umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
   20: (61) r2 = *(u32 *)(r3 +0)
   R3 unbounded memory access, make sure to bounds check any such access
   processed 97 insns (limit 1000000) max_states_per_insn 1 total_states 10 peak_states 10 mark_read 6
   -- END PROG LOAD LOG --
   libbpf: prog 'ingress_fwdns_prio100': failed to load: -13
   libbpf: failed to load object 'test_tc_dtime'
   libbpf: failed to load BPF skeleton 'test_tc_dtime': -13
   ...

At insn 14, with condition 'w1 < 9', register r1 is changed from an arbitrary u32 value to scalar(umax=8,var_off=(0x0; 0xf)). Register r2, however, remains as an arbitrary u32 value. Current verifier won't claim r1/r2 equality if the previous mov is alu32 ('w2 = w1').

Quoted 5 lines

If r1 upper 32bit value is not 0, we indeed cannot clamin r1/r2 equality after 'w2 = w1'. But in this particular case, we know r1 upper 32bit value is 0, so it is safe to claim r1/r2 equality. This patch exactly did this. For a 32bit subreg mov, if the src register upper 32bit is 0, it is okay to claim equality between src and dst registers.

Quoted 7 lines

Perhaps mention in the above paragraph that this works because 32-bit ALU operations clear the upper bits? Some along the line of

A special case where r1/r2 equality can be claimed after 'w2 = w1' is when r1 upper 32bit value is 0. This is because 32bit ALU operations always clear the upper 32 bits of the destination, so 'w2 = w1' in this case is the same as 'r2 = r1'...

In BPF documentation (Documentation/bpf/instruction-set.rst), we have
...
for ``BPF_ALU`` the upper
32 bits of the destination register are zeroed

I asssume this is known and that is why I didn't explicitly mention this in the commit message. The patch has been merged...

Quoted 60 lines
Quoted 21 lines

With this patch, the above verification sequence becomes

   ...
   8: (18) r1 = 0xffffc9000048e230       ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
   10: (61) r1 = *(u32 *)(r1 +0)         ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   11: (79) r2 = *(u64 *)(r6 +152)       ; R2_w=scalar() R6=ctx(off=0,imm=0)
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   12: (55) if r2 != 0xb9fbeef goto pc+10        ; R2_w=195018479
   13: (bc) w2 = w1                      ; R1_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (test < __NR_TESTS)
   14: (a6) if w1 < 0x9 goto pc+1        ; R1_w=scalar(id=6,umin=9,umax=4294967295,var_off=(0x0; 0xffffffff))
   ...
   from 14 to 16: R0=2 R1_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R2_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R6=ctx(off=0,imm=0) R10=fp0
   16: (27) r2 *= 28                     ; R2_w=scalar(umax=224,var_off=(0x0; 0xfc))
   17: (18) r3 = 0xffffc9000048e118      ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
   19: (0f) r3 += r2
   20: (61) r2 = *(u32 *)(r3 +0)         ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R3_w=map_value(off=280,ks=4,vs=564,umax=224,var_off=(0x0; 0xfc),s32_max=252,u32_max=252)
   ...
Quoted 5 lines

and eventually the bpf program can be verified successfully.

   [1] https://reviews.llvm.org/D147968
Quoted 31 lines
---
  kernel/bpf/verifier.c | 9 +++++++--
  1 file changed, 7 insertions(+), 2 deletions(-)
kernel/bpf/verifier.c +7 -2
index d6db6de3e9ea..468f002d3248 100644
@@ -12409,12 +12409,17 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
  						insn->src_reg);
  					return -EACCES;
  				} else if (src_reg->type == SCALAR_VALUE) {
+					bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
+
+					if (is_src_reg_u32 && !src_reg->id)
+						src_reg->id = ++env->id_gen;
  					copy_register_state(dst_reg, src_reg);
-					/* Make sure ID is cleared otherwise
+					/* Make sure ID is cleared if src_reg is not in u32 range otherwise
  					 * dst_reg min/max could be incorrectly
  					 * propagated into src_reg by find_equal_scalars()
  					 */
-					dst_reg->id = 0;
+					if (!is_src_reg_u32)
+						dst_reg->id = 0;
  					dst_reg->live |= REG_LIVE_WRITTEN;
  					dst_reg->subreg_def = env->insn_idx + 1;
  				} else {
Signature · 1 line
2.34.1
#7 lore raw
Quoted 50 lines · Yonghong Song
Quoted 41 lines · Shung-Hsi Yu
Quoted 34 lines · Yonghong Song

In [1], I tried to remove bpf-specific codes to prevent certain llvm optimizations, and add llvm TTI (target transform info) hooks to prevent those optimizations. During this process, I found
if I enable llvm SimplifyCFG:shouldFoldTwoEntryPHINode transformation, I will hit the following verification failure with selftests:

   ...
   8: (18) r1 = 0xffffc900001b2230       ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
   10: (61) r1 = *(u32 *)(r1 +0)         ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   11: (79) r2 = *(u64 *)(r6 +152)       ; R2_w=scalar() R6=ctx(off=0,imm=0)
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   12: (55) if r2 != 0xb9fbeef goto pc+10        ; R2_w=195018479
   13: (bc) w2 = w1                      ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (test < __NR_TESTS)
   14: (a6) if w1 < 0x9 goto pc+1 16: R0=2 R1_w=scalar(umax=8,var_off=(0x0; 0xf)) R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R6=ctx(off=0,imm=0) R10=fp0
   ;
   16: (27) r2 *= 28                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
   17: (18) r3 = 0xffffc900001b2118      ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
   19: (0f) r3 += r2                     ; R2_w=scalar(umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4) R3_w=map_value(off=280,ks=4,vs=564,umax=120259084260,var_off=(0x0; 0x1ffffffffc),s32_max=2147483644,u32_max=-4)
   20: (61) r2 = *(u32 *)(r3 +0)
   R3 unbounded memory access, make sure to bounds check any such access
   processed 97 insns (limit 1000000) max_states_per_insn 1 total_states 10 peak_states 10 mark_read 6
   -- END PROG LOAD LOG --
   libbpf: prog 'ingress_fwdns_prio100': failed to load: -13
   libbpf: failed to load object 'test_tc_dtime'
   libbpf: failed to load BPF skeleton 'test_tc_dtime': -13
   ...

At insn 14, with condition 'w1 < 9', register r1 is changed from an arbitrary u32 value to scalar(umax=8,var_off=(0x0; 0xf)). Register r2, however, remains as an arbitrary u32 value. Current verifier won't claim r1/r2 equality if the previous mov is alu32 ('w2 = w1').

Quoted 5 lines

If r1 upper 32bit value is not 0, we indeed cannot clamin r1/r2 equality after 'w2 = w1'. But in this particular case, we know r1 upper 32bit value is 0, so it is safe to claim r1/r2 equality. This patch exactly did this. For a 32bit subreg mov, if the src register upper 32bit is 0, it is okay to claim equality between src and dst registers.

Quoted 7 lines

Perhaps mention in the above paragraph that this works because 32-bit ALU operations clear the upper bits? Some along the line of

A special case where r1/r2 equality can be claimed after 'w2 = w1' is when r1 upper 32bit value is 0. This is because 32bit ALU operations always clear the upper 32 bits of the destination, so 'w2 = w1' in this case is the same as 'r2 = r1'...

Quoted 7 lines

In BPF documentation (Documentation/bpf/instruction-set.rst), we have
...
for ``BPF_ALU`` the upper
32 bits of the destination register are zeroed

I asssume this is known and that is why I didn't explicitly mention this in the commit message. The patch has been merged...

Thanks for still replying even though it's already merged.

FWIW just thought it would makes the commit message slightly clearer, hence the suggestion.

Quoted 29 lines
Quoted 29 lines
Quoted 20 lines

With this patch, the above verification sequence becomes

   ...
   8: (18) r1 = 0xffffc9000048e230       ; R1_w=map_value(off=560,ks=4,vs=564,imm=0)
   10: (61) r1 = *(u32 *)(r1 +0)         ; R1_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   11: (79) r2 = *(u64 *)(r6 +152)       ; R2_w=scalar() R6=ctx(off=0,imm=0)
   ; if (skb->tstamp == EGRESS_ENDHOST_MAGIC)
   12: (55) if r2 != 0xb9fbeef goto pc+10        ; R2_w=195018479
   13: (bc) w2 = w1                      ; R1_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff)) R2_w=scalar(id=6,umax=4294967295,var_off=(0x0; 0xffffffff))
   ; if (test < __NR_TESTS)
   14: (a6) if w1 < 0x9 goto pc+1        ; R1_w=scalar(id=6,umin=9,umax=4294967295,var_off=(0x0; 0xffffffff))
   ...
   from 14 to 16: R0=2 R1_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R2_w=scalar(id=6,umax=8,var_off=(0x0; 0xf)) R6=ctx(off=0,imm=0) R10=fp0
   16: (27) r2 *= 28                     ; R2_w=scalar(umax=224,var_off=(0x0; 0xfc))
   17: (18) r3 = 0xffffc9000048e118      ; R3_w=map_value(off=280,ks=4,vs=564,imm=0)
   19: (0f) r3 += r2
   20: (61) r2 = *(u32 *)(r3 +0)         ; R2_w=scalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R3_w=map_value(off=280,ks=4,vs=564,umax=224,var_off=(0x0; 0xfc),s32_max=252,u32_max=252)
   ...
Quoted 5 lines

and eventually the bpf program can be verified successfully.

   [1] https://reviews.llvm.org/D147968
Quoted 1 line

...