Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
Date:   Wed, 21 Apr 2021 09:41:13 -0700
From:   John Fastabend <john.fastabend@gmail.com>
To:     Brendan Jackman <jackmanb@google.com>, bpf@vger.kernel.org
Cc:     ast@kernel.org, daniel@iogearbox.net, andrii@kernel.org,
        linux-kernel@vger.kernel.org, Brendan Jackman <jackmanb@google.com>
Message-ID: <608055a9a6f4d_46b9208b0@john-XPS-13-9370.notmuch>
In-Reply-To: <20210421122348.547922-1-jackmanb@google.com>
References: <20210421122348.547922-1-jackmanb@google.com>
Subject: RE: Help with verifier failure
Mime-Version: 1.0
Content-Type: text/plain;
 charset=utf-8
Content-Transfer-Encoding: 7bit
Precedence: bulk

Brendan Jackman wrote:
> Hi,
> 
> Recently when our internal Clang build was updated to 0e92cbd6a652 we started
> hitting a verifier issue that I can't see an easy fix for. I've narrowed it down
> to a minimal reproducer - this email is a patch to add that repro as a prog
> test (./test_progs -t example).
> 
> Here's the BPF code I get from the attached source:
> 

[...]

> 
> w2 can't exceed 4096 but the verifier doesn't seem to "backpropagate" those
> bounds from r8 (note the umax_value for R8 goes to 4095 after the branch from 36
> to 20, but R2's umax_value is still 266342399)
> 
> from 31 to 34: R0_w=inv(id=0) R1_w=inv2097152 R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2093056 R8_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> ; int BPF_PROG(exec, struct linux_binprm *bprm) {
> 34: (bf) r7 = r1
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 35: (bc) w2 = w8
> 36: (a5) if r8 < 0x1000 goto pc-17
> 
> from 36 to 20: R0_w=inv(id=0) R1_w=inv2097152 R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> ; void *src = (void *)(char *)bprm->p + offset;
> 20: (79) r1 = *(u64 *)(r10 -24)
> 21: (79) r3 = *(u64 *)(r1 +24)
> ; uint64_t read_size = args_size - offset;
> 22: (0f) r3 += r7
> 23: (07) r3 += -4096
> ; (void) bpf_probe_read_user(buf, read_size, src);
> 24: (79) r1 = *(u64 *)(r10 -16)
> 25: (85) call bpf_probe_read_user#112
>  R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
>  R0_w=inv(id=0) R1_w=map_value(id=0,off=0,ks=4,vs=4096,imm=0) R2_w=inv(id=0,umax_value=266342399,var_off=(0x0; 0xfffffff)) R3_w=inv(id=0) R6=inv(id=2,umin_value=2093057,umax_value=268435455,var_off=(0x0; 0xfffffff)) R7_w=inv2097152 R8_w=inv(id=0,umax_value=4095,var_off=(0x0; 0xfff)) R9_w=invP511 R10=fp0 fp-8=mmmm???? fp-16=map_value fp-24=ptr_
> invalid access to map value, value_size=4096 off=0 size=266342399
> R1 min value is outside of the allowed memory range
> processed 9239 insns (limit 1000000) max_states_per_insn 4 total_states 133 peak_states 133 mark_read 2
> 
> This seems like it must be a common pitfall, any idea what we can do to fix it
> and avoid it in future? Am I misunderstanding the issue?

We also hit this from time to time. I have asm blocks to work-around
at the moment. I was going to see how ugly propagating the bounds
backwards gets. I had some code for this some time ago but never
pushed it, it was smashed in with some CFG building for loops back
before loops were possible. I can take a look next week unless someone
beats me there.

> 
> Cheers,
> Brendan
>