From: Yonghong Song <yonghong.song@linux.dev>
To: Alexei Starovoitov <alexei.starovoitov@gmail.com>
Cc: bpf <bpf@vger.kernel.org>, Alexei Starovoitov <ast@kernel.org>,
Andrii Nakryiko <andrii@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Kernel Team <kernel-team@fb.com>,
Martin KaFai Lau <martin.lau@kernel.org>,
Daniel Hodges <hodgesd@meta.com>
Subject: Re: [PATCH bpf-next] bpf, x64: Fix a jit convergence issue
Date: Wed, 28 Aug 2024 18:54:58 -0700 [thread overview]
Message-ID: <0723964d-97b9-4b48-995c-3c9efa980f5a@linux.dev> (raw)
In-Reply-To: <CAADnVQLbknLw9fOhgbSNaNzKi5gfQTP74vXQu3D1P2OVF81b+Q@mail.gmail.com>
On 8/28/24 4:44 PM, Alexei Starovoitov wrote:
> On Wed, Aug 28, 2024 at 3:47 PM Yonghong Song <yonghong.song@linux.dev> wrote:
>>> It can be je/je too, no?
>> Yes. It is possible.
>>
>>> so 128 - 4 instead of 128 - 3 ?
>> You probably mean "127 - 4 instead of 127 - 3" since
>> the maximum value is 127.
> Yes, of course :)
>
>> I checked 127 - 4 = 0x7c and indeed we should. See below examples:
>>
>> 20e: 48 85 ff test rdi,rdi
>> 211: XX XX je 0x291
>> 213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
>> ...
>> 28d: XX XX XX XX XX XX je 0x212
>> 293: bf 03 00 00 00 mov edi,0x3
>>
>> =>
>>
>> 20e: 48 85 ff test rdi,rdi
>> 211: XX XX XX XX XX XX je 0x297 (0x293 - 0x213)
>> 217: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
>> ...
>> 291: XX XX je 0x217 (0x217 - 0x293)
>> 293: bf 03 00 00 00 mov edi,0x3
>>
>> =>
>>
>> 20e: 48 85 ff test rdi,rdi
>> 211: XX XX je 0x28f (0x293 - 0x217)
>> 213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
>> ...
>> 28d: XX XX je 0x213 (0x213 - 0x293) // -0x80 allowed
>> 293: bf 03 00 00 00 mov edi,0x3
>>
>> =>
>>
>> 20e: 48 85 ff test rdi,rdi
>> 211: XX XX XX XX XX XX je 0x28f (0x293 - 0x213)
>> 217: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
>> ...
>> 291: XX XX je 0x217 (0x217 - 0x293)
>> 293: bf 03 00 00 00 mov edi,0x3
>>
>> =>
>> ...
>>
>>
>> Here 0x293 - 0x217 = 0x7c
> How did you craft such a test?
> Can we add it as a selftest somehow?
This is not from a complete test. I assumed some state during convergence
and from there to further derive states. But I will try to see whether
I can construct actual test cases or not.
>
>>>> +static bool is_imm8_cond_offset(int value)
>>>> +{
>>>> + return value <= 124 && value >= -128;
>>> the other side needs the same treatment, no ?
>> good question. From my understanding, the non-convergence in the
>> above needs both forward and backport conditions. The solution we
>> are using is based on putting a limitation on forward conditions
>> w.r.t. jit code gen.
>>
>> Another solution is actually to put a limitation on backward
>> conditions. For example, let us say the above is_imm8_cond_offset()
>> has
>> return value <= 127 && value > -124
>>
>> See below example:
>>
>> 20e: 48 85 ff test rdi,rdi
>> 211: XX XX je 0x291
>> 213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
>> ...
>> 28d: XX XX XX XX XX XX je 0x212
>> 293: bf 03 00 00 00 mov edi,0x3
>>
>> =>
>>
>> 20e: 48 85 ff test rdi,rdi
>> 211: XX XX XX XX XX XX je 0x297 (0x293 - 0x213)
>> 217: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
>> ...
>> 291: XX XX XX XX XX XX je 0x21b (0x217 - 0x293)
>> 297: bf 03 00 00 00 mov edi,0x3
>>
>> =>
>>
>> 20e: 48 85 ff test rdi,rdi
>> 211: XX XX XX XX XX XX je 0x297 (0x297 - 0x217)
>> 217: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
>> ...
>> 291: XX XX XX XX XX XX je 0x217 (0x217 - 0x297)
>> 297: bf 03 00 00 00 mov edi,0x3
>>
>> converged here.
>>
>> So I think we do not need to limit both sides. One side should be enough.
> I see and agree when both sides are je/je.
> What if the earlier one is a jmp ?
>
> Then we can hit:
> if (nops != 0 && nops != 3) {
> pr_err("unexpected jump padding: %d bytes\n",
> nops);
> ?
>
> So one side of "jmp_cond padding" and the same side in "jump padding"
> needs to do it?
I did some further experiments with pattern like
jmp <-> je
and
jmp <-> jmp
The below is the illustration (not from a complete test):
================
211: XX XX jmp 0x291
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28d: XX XX XX XX XX XX je 0x212
293: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX XX XX XX jmp (0x293 - 0x213)
216: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
291: XX XX je (0x216 - 0x293)
293: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX jmp (0x293 - 0x216 = 0x7d)
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28d: XX XX je (0x213 - 0x293)
293: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX XX XX XX jmp (0x293 - 0x213)
216: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
291: XX XX je (0x216 - 0x293)
293: bf 03 00 00 00 mov edi,0x3
=>
...
not converged!
================
211: XX XX jmp 0x291
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28c: XX XX XX XX XX XX je 0x212
292: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX jmp (0x292 - 0x213)
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28c: XX XX je (0x213 - 0x292)
28e: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX jmp (0x28e - 0x213 = 0x7b)
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28c: XX XX je (0x213 - 0x28e)
28e: bf 03 00 00 00 mov edi,0x3
converged!
=================
211: XX XX jmp 0x291
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28e: XX XX XX XX XX jmp 0x212
293: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX XX XX XX jmp (0x293 - 0x213)
216: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
292: XX XX jmp (0x216 - 0x293)
294: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX jmp (0x294 - 0x216 = 0x7e)
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28e: XX XX XX XX XX jmp (0x213 - 0x294)
294: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX jmp (0x294 - 0x216 = 0x7e)
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28e: XX XX XX XX XX jmp (0x213 - 0x294)
294: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX XX XX XX jmp (0x294 - 0x213)
216: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
292: XX XX jmp (0x216 - 0x294)
294: bf 03 00 00 00 mov edi,0x3
=>
...
no converged!
===================================
211: XX XX jmp 0x291
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28d: XX XX XX XX XX jmp 0x212
292: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX jmp (0x292 - 0x213)
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28d: XX XX jmp (0x213 - 0x292)
290: bf 03 00 00 00 mov edi,0x3
=>
211: XX XX jmp (0x290 - 0x213 = 0x7d)
213: 48 8b 77 00 mov rsi,QWORD PTR [rdi+0x0]
...
28d: XX XX jmp (0x213 - 0x290)
290: bf 03 00 00 00 mov edi,0x3
converged!
So I emulated je <-> je, je <-> jmp, jmp <-> je and jmp <-> jmp.
So we need to apply the same checking is_imm8_cond_offset() to jmp insn.
This should cover all cases.
Hitting the following
if (nops != 0 && nops != 3) {
pr_err("unexpected jump padding: %d bytes\n",
nops);
is not due to the above illustration with 'jmp' insn as indeed
its insn length changes with 0 or 3. But it is due to some jmp/cond_jmp
insn inside je/jmp <-> je/jmp.
next prev parent reply other threads:[~2024-08-29 1:55 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-08-25 20:04 [PATCH bpf-next] bpf, x64: Fix a jit convergence issue Yonghong Song
2024-08-27 23:44 ` Andrii Nakryiko
2024-08-28 22:50 ` Yonghong Song
2024-08-29 17:27 ` Andrii Nakryiko
2024-08-30 20:39 ` Yonghong Song
2024-08-28 2:24 ` Alexei Starovoitov
2024-08-28 22:47 ` Yonghong Song
2024-08-28 23:44 ` Alexei Starovoitov
2024-08-29 1:54 ` Yonghong Song [this message]
2024-08-29 16:37 ` Alexei Starovoitov
2024-08-29 16:50 ` Yonghong Song
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=0723964d-97b9-4b48-995c-3c9efa980f5a@linux.dev \
--to=yonghong.song@linux.dev \
--cc=alexei.starovoitov@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=hodgesd@meta.com \
--cc=kernel-team@fb.com \
--cc=martin.lau@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