From: Yonghong Song <yhs@fb.com>
To: Brendan Jackman <jackmanb@google.com>
Cc: bpf <bpf@vger.kernel.org>, Alexei Starovoitov <ast@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Andrii Nakryiko <andrii@kernel.org>,
LKML <linux-kernel@vger.kernel.org>
Subject: Re: Help with verifier failure
Date: Thu, 22 Apr 2021 07:35:08 -0700 [thread overview]
Message-ID: <0da3a605-198f-cd1b-f6f2-7ca95082fd94@fb.com> (raw)
In-Reply-To: <CA+i-1C0tV0m+HY1WwivrYE-iouF9b8NGVSXhL_ZmRz6JL36TzA@mail.gmail.com>
On 4/22/21 6:55 AM, Brendan Jackman wrote:
> On Wed, 21 Apr 2021 at 18:59, Yonghong Song <yhs@fb.com> wrote:
>> On 4/21/21 8:06 AM, Yonghong Song wrote:
>>> On 4/21/21 5:23 AM, Brendan Jackman wrote:
>>> Thanks, Brendan. Looks at least the verifier failure is triggered
>>> by recent clang changes. I will take a look whether we could
>>> improve verifier for such a case and whether we could improve
>>> clang to avoid generate such codes the verifier doesn't like.
>>> Will get back to you once I had concrete analysis.
>>>
>>>>
>>>> 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?
>>
>> First, for the example code you provided, I checked with llvm11, llvm12
>> and latest trunk llvm (llvm13-dev) and they all generated similar codes,
>> which may trigger verifier failure. Somehow you original code could be
>> different may only show up with a recent llvm, I guess.
>>
>> Checking llvm IR, the divergence between "w2 = w8" and "if r8 < 0x1000"
>> appears in insn scheduling phase related handling PHIs. Need to further
>> check whether it is possible to prevent the compiler from generating
>> such codes.
>>
>> The latest kernel already had the ability to track register equivalence.
>> However, the tracking is conservative for 32bit mov like "w2 = w8" as
>> you described in the above. if we have code like "r2 = r8; if r8 <
>> 0x1000 ...", we will be all good.
>>
>> The following hack fixed the issue,
>>
>> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
>> index 58730872f7e5..54f418fd6a4a 100644
>> --- a/kernel/bpf/verifier.c
>> +++ b/kernel/bpf/verifier.c
>> @@ -7728,12 +7728,20 @@ 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) {
>> + /* If src_reg is in 32bit range,
>> there is
>> + * no need to reset the ID.
>> + */
>> + bool is_32bit_src =
>> src_reg->umax_value <= 0x7fffffff;
>> +
>> + if (is_32bit_src && !src_reg->id)
>> + src_reg->id = ++env->id_gen;
>> *dst_reg = *src_reg;
>> /* Make sure ID is cleared
>> otherwise
>> * dst_reg min/max could be
>> incorrectly
>> * propagated into src_reg by
>> find_equal_scalars()
>> */
>> - dst_reg->id = 0;
>> + if (!is_32bit_src)
>> + dst_reg->id = 0;
>> dst_reg->live |= REG_LIVE_WRITTEN;
>> dst_reg->subreg_def =
>> env->insn_idx + 1;
>> } else {
>>
>> Basically, for a 32bit mov insn like "w2 = w8", if we can ensure
>> that "w8" is 32bit and has no possibility that upper 32bit is set
>> for r8, we can declare them equivalent. This fixed your issue.
>>
>> Will try to submit a formal patch later.
>
> Ah.. I did not realise this equivalence tracking with reg.id was there
> for scalar values! I also didn't take any notice of the use of 32-bit
> operations in the assembly, thanks for pointing that out.
>
> Yes it sounds like this is certainly worth fixing in the kernel - even
> if Clang stops generating the code today it will probably start doing
> so again in the future. I can also help with the verifier work if
> needed.
I won't have time for this in the next few days.
Considering the current upstream merge window is close, yes, please
go head to work on this. Thanks!
next prev parent reply other threads:[~2021-04-22 14:35 UTC|newest]
Thread overview: 8+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-04-21 12:23 Help with verifier failure Brendan Jackman
2021-04-21 15:06 ` Yonghong Song
2021-04-21 16:59 ` Yonghong Song
2021-04-22 13:55 ` Brendan Jackman
2021-04-22 14:35 ` Yonghong Song [this message]
2021-05-07 15:05 ` Brendan Jackman
2021-05-07 18:32 ` Yonghong Song
2021-04-21 16:41 ` John Fastabend
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=0da3a605-198f-cd1b-f6f2-7ca95082fd94@fb.com \
--to=yhs@fb.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=jackmanb@google.com \
--cc=linux-kernel@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).