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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.