diff mbox series

[bpf-next,1/2] bpf: Improve verifier u32 scalar equality checking

Message ID 20230416232808.2387432-1-yhs@fb.com (mailing list archive)
State Superseded
Delegated to: BPF
Headers show
Series [bpf-next,1/2] bpf: Improve verifier u32 scalar equality checking | expand

Checks

Context Check Description
bpf/vmtest-bpf-next-PR success PR summary
bpf/vmtest-bpf-next-VM_Test-1 success Logs for ShellCheck
bpf/vmtest-bpf-next-VM_Test-7 success Logs for set-matrix
bpf/vmtest-bpf-next-VM_Test-2 success Logs for build for aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-3 success Logs for build for aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-5 success Logs for build for x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-6 success Logs for build for x86_64 with llvm-16
netdev/series_format success Single patches do not need cover letters
netdev/tree_selection success Clearly marked for bpf-next, async
netdev/fixes_present success Fixes tag not required for -next series
netdev/header_inline success No static functions without inline keyword in header files
netdev/build_32bit success Errors and warnings before: 30 this patch: 30
netdev/cc_maintainers warning 11 maintainers not CCed: llvm@lists.linux.dev song@kernel.org sdf@google.com haoluo@google.com trix@redhat.com nathan@kernel.org john.fastabend@gmail.com ndesaulniers@google.com kpsingh@kernel.org jolsa@kernel.org martin.lau@linux.dev
netdev/build_clang success Errors and warnings before: 18 this patch: 18
netdev/verify_signedoff success Signed-off-by tag matches author and committer
netdev/deprecated_api success None detected
netdev/check_selftest success No net selftest shell script
netdev/verify_fixes success No Fixes tag
netdev/build_allmodconfig_warn success Errors and warnings before: 30 this patch: 30
netdev/checkpatch warning WARNING: line length of 107 exceeds 80 columns WARNING: line length of 93 exceeds 80 columns
netdev/kdoc success Errors and warnings before: 0 this patch: 0
netdev/source_inline success Was 0 now: 0
bpf/vmtest-bpf-next-VM_Test-4 success Logs for build for s390x with gcc
bpf/vmtest-bpf-next-VM_Test-32 success Logs for test_verifier on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-34 success Logs for test_verifier on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-35 success Logs for test_verifier on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-8 success Logs for test_maps on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-9 success Logs for test_maps on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-11 success Logs for test_maps on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-12 success Logs for test_maps on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-13 success Logs for test_progs on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-14 success Logs for test_progs on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-16 fail Logs for test_progs on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-17 fail Logs for test_progs on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-18 success Logs for test_progs_no_alu32 on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-19 success Logs for test_progs_no_alu32 on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-21 fail Logs for test_progs_no_alu32 on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-22 fail Logs for test_progs_no_alu32 on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-23 success Logs for test_progs_no_alu32_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-24 success Logs for test_progs_no_alu32_parallel on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-25 success Logs for test_progs_no_alu32_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-26 success Logs for test_progs_no_alu32_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-27 success Logs for test_progs_parallel on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-28 success Logs for test_progs_parallel on aarch64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-29 success Logs for test_progs_parallel on x86_64 with gcc
bpf/vmtest-bpf-next-VM_Test-30 success Logs for test_progs_parallel on x86_64 with llvm-16
bpf/vmtest-bpf-next-VM_Test-31 success Logs for test_verifier on aarch64 with gcc
bpf/vmtest-bpf-next-VM_Test-33 success Logs for test_verifier on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-20 success Logs for test_progs_no_alu32 on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-15 success Logs for test_progs on s390x with gcc
bpf/vmtest-bpf-next-VM_Test-10 success Logs for test_maps on s390x with gcc

Commit Message

Yonghong Song April 16, 2023, 11:28 p.m. UTC 
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

Signed-off-by: Yonghong Song <yhs@fb.com>
---
 kernel/bpf/verifier.c | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

Comments

Shung-Hsi Yu April 17, 2023, 12:40 p.m. UTC | #1 
On Sun, Apr 16, 2023 at 04:28:08PM -0700, Yonghong Song wrote:
> 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.

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'...

> 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
> 
> Signed-off-by: Yonghong Song <yhs@fb.com>

Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>

> ---
>  kernel/bpf/verifier.c | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index d6db6de3e9ea..468f002d3248 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -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 {
> -- 
> 2.34.1
>
Yonghong Song April 18, 2023, 5:54 p.m. UTC | #2 
On 4/17/23 5:40 AM, Shung-Hsi Yu wrote:
> On Sun, Apr 16, 2023 at 04:28:08PM -0700, Yonghong Song wrote:
>> 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.
> 
> 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...

> 
>> 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
>>
>> Signed-off-by: Yonghong Song <yhs@fb.com>
> 
> Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> 
>> ---
>>   kernel/bpf/verifier.c | 9 +++++++--
>>   1 file changed, 7 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index d6db6de3e9ea..468f002d3248 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -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 {
>> -- 
>> 2.34.1
>>
Shung-Hsi Yu April 20, 2023, 9:16 a.m. UTC | #3 
On Tue, Apr 18, 2023 at 10:54:39AM -0700, Yonghong Song wrote:
> On 4/17/23 5:40 AM, Shung-Hsi Yu wrote:
> > On Sun, Apr 16, 2023 at 04:28:08PM -0700, Yonghong Song wrote:
> > > 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.
> > 
> > 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...

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

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

> > > 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
> > > 
> > > Signed-off-by: Yonghong Song <yhs@fb.com>
> > 
> > Acked-by: Shung-Hsi Yu <shung-hsi.yu@suse.com>
> > 
> > > ...
diff mbox series

Patch

diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index d6db6de3e9ea..468f002d3248 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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 {