Re: [PATCH bpf-next] bpf, x64: Fix a jit convergence issue

[Yonghong Song <yonghong.song@linux.dev>]

On 8/29/24 10:27 AM, Andrii Nakryiko wrote:
> On Wed, Aug 28, 2024 at 3:50 PM Yonghong Song <yonghong.song@linux.dev> wrote:
>>
>> On 8/27/24 4:44 PM, Andrii Nakryiko wrote:
>>> On Sun, Aug 25, 2024 at 1:04 PM Yonghong Song <yonghong.song@linux.dev> wrote:
>>>> Daniel Hodges reported a jit error when playing with a sched-ext
>>>> program. The error message is:
>>>>     unexpected jmp_cond padding: -4 bytes
>>>>
>>>> But further investigation shows the error is actual due to failed
>>>> convergence. The following are some analysis:
>>>>
>>>>     ...
>>>>     pass4, final_proglen=4391:
>>>>       ...
>>>>       20e:    48 85 ff                test   rdi,rdi
>>>>       211:    74 7d                   je     0x290
>>>>       213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
>>>>       ...
>>>>       289:    48 85 ff                test   rdi,rdi
>>>>       28c:    74 17                   je     0x2a5
>>>>       28e:    e9 7f ff ff ff          jmp    0x212
>>>>       293:    bf 03 00 00 00          mov    edi,0x3
>>>>
>>>> Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
>>>> and insn at 0x28e is 5-byte jmp insn with offset -129.
>>>>
>>>>     pass5, final_proglen=4392:
>>>>       ...
>>>>       20e:    48 85 ff                test   rdi,rdi
>>>>       211:    0f 84 80 00 00 00       je     0x297
>>>>       217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
>>>>       ...
>>>>       28d:    48 85 ff                test   rdi,rdi
>>>>       290:    74 1a                   je     0x2ac
>>>>       292:    eb 84                   jmp    0x218
>>>>       294:    bf 03 00 00 00          mov    edi,0x3
>>>>
>>>> Note that insn at 0x211 is 5-byte cond jump insn now since its offset
>>>> becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
>>>> At the same time, insn at 0x292 is a 2-byte insn since its offset is
>>>> -124.
>>>>
>>>> pass6 will repeat the same code as in pass4. pass7 will repeat the same
>>>> code as in pass5, and so on. This will prevent eventual convergence.
>>>>
>>>> Passes 1-14 are with padding = 0. At pass15, padding is 1 and related
>>>> insn looks like:
>>>>
>>>>       211:    0f 84 80 00 00 00       je     0x297
>>>>       217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
>>>>       ...
>>>>       24d:    48 85 d2                test   rdx,rdx
>>>>
>>>> The similar code in pass14:
>>>>       211:    74 7d                   je     0x290
>>>>       213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
>>>>       ...
>>>>       249:    48 85 d2                test   rdx,rdx
>>>>       24c:    74 21                   je     0x26f
>>>>       24e:    48 01 f7                add    rdi,rsi
>>>>       ...
>>>>
>>>> Before generating the following insn,
>>>>     250:    74 21                   je     0x273
>>>> "padding = 1" enables some checking to ensure nops is either 0 or 4
>>>> where
>>>>     #define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
>>>>     nops = INSN_SZ_DIFF - 2
>>>>
>>>> In this specific case,
>>>>     addrs[i] = 0x24e // from pass14
>>>>     addrs[i-1] = 0x24d // from pass15
>>>>     prog - temp = 3 // from 'test rdx,rdx' in pass15
>>>> so
>>>>     nops = -4
>>>> and this triggers the failure.
>>>> Making jit prog convergable can fix the above error.
>>>>
>>>> Reported-by: Daniel Hodges <hodgesd@meta.com>
>>>> Signed-off-by: Yonghong Song <yonghong.song@linux.dev>
>>>> ---
>>>>    arch/x86/net/bpf_jit_comp.c | 47 ++++++++++++++++++++++++++++++++++++-
>>>>    1 file changed, 46 insertions(+), 1 deletion(-)
>>>>
>>> Probably a stupid question. But instead of hacking things like this to
>>> help convergence in some particular cases, why not just add a
>>> condition that we should stop jitting as soon as jitted length stops
>>> shrinking (and correct the comment that claims "JITed image shrinks
>>> with every pass" because that's not true).
>>>
>>> We have `if (proglen == oldproglen)` condition right now. What will
>>> happen if we just change it to `if (proglen >= oldproglen)`? That
>>> might be sup-optimal for these rare non-convergent cases, but that
>>> seems fine. We can of course do one extra pass to hopefully get back
>>> the second-to-last shorter image if proglen > oldproglen, but that
>>> seems excessive to me.
>> We need convergence. Looks at some comments below:
>>
>> + * pass5, final_proglen=4392:
>> + *   ...
>> + *   20e:    48 85 ff                test   rdi,rdi
>> + *   211:    0f 84 80 00 00 00       je     0x297
>> + *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
>> + *   ...
>> + *   28d:    48 85 ff                test   rdi,rdi
>> + *   290:    74 1a                   je     0x2ac
>> + *   292:    eb 84                   jmp    0x218
>> + *   294:    bf 03 00 00 00          mov    edi,0x3
>>
>> Without convergence, you can see je/jmp target may not be correct.
>>
> I see, thanks. As I said, probably was a stupid question, I didn't
> realize that do_jit() can generate invalid image.
>
> This whole guessing of acceptable range of relative offset still seems
> like a fragile game (what if you have few instructions that expand and
> then 124 bound isn't conservative enough anymore). I was wondering if
> there is some more generic solution where we can mark jump
> instructions that went from shorter to longer, and if that happened,
> on subsequent passes don't try to shorten them.

I digged out the git history and found that this pass convergence based
approach is actually implemented from the beginning from the following
patch

=====
commit 0a14842f5a3c0e88a1e59fac5c3025db39721f74 (HEAD -> t2)
Author: Eric Dumazet <eric.dumazet@gmail.com>
Date:   Wed Apr 20 09:27:32 2011 +0000

     net: filter: Just In Time compiler for x86-64
=====

I cannot find the discussion context for this patch then.
Do we have a better approach for this? I do not know, the issue
is that for the same branch/jmp insn, the length of the insn
could change depending on the 'offset' value. One possible
solution is to assume all branch/jmp insn is 8bit long and
whenever it won't work, replace previous one with 32bit and
continue to enumerate following branch/jmp insn with 8bit.
This may take a lot of time though.

>
> Again, I have no clue how actual code in JIT works and what are all
> the nuances, so feel free to ignore me completely, I won't be offended
> :)
>
>>>
>>>> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
>>>> index 074b41fafbe3..ec541aae5d9b 100644
>>>> --- a/arch/x86/net/bpf_jit_comp.c
>>>> +++ b/arch/x86/net/bpf_jit_comp.c
>>>> @@ -64,6 +64,51 @@ static bool is_imm8(int value)
>>>>           return value <= 127 && value >= -128;
>>>>    }
>>>>
>>>> +/*
>>>> + * Let us limit the positive offset to be <= 124.
>>>> + * This is to ensure eventual jit convergence For the following patterns:
>>>> + * ...
>>>> + * pass4, final_proglen=4391:
>>>> + *   ...
>>>> + *   20e:    48 85 ff                test   rdi,rdi
>>>> + *   211:    74 7d                   je     0x290
>>>> + *   213:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
>>>> + *   ...
>>>> + *   289:    48 85 ff                test   rdi,rdi
>>>> + *   28c:    74 17                   je     0x2a5
>>>> + *   28e:    e9 7f ff ff ff          jmp    0x212
>>>> + *   293:    bf 03 00 00 00          mov    edi,0x3
>>>> + * Note that insn at 0x211 is 2-byte cond jump insn for offset 0x7d (-125)
>>>> + * and insn at 0x28e is 5-byte jmp insn with offset -129.
>>>> + *
>>>> + * pass5, final_proglen=4392:
>>>> + *   ...
>>>> + *   20e:    48 85 ff                test   rdi,rdi
>>>> + *   211:    0f 84 80 00 00 00       je     0x297
>>>> + *   217:    48 8b 77 00             mov    rsi,QWORD PTR [rdi+0x0]
>>>> + *   ...
>>>> + *   28d:    48 85 ff                test   rdi,rdi
>>>> + *   290:    74 1a                   je     0x2ac
>>>> + *   292:    eb 84                   jmp    0x218
>>>> + *   294:    bf 03 00 00 00          mov    edi,0x3
>>>> + * Note that insn at 0x211 is 5-byte cond jump insn now since its offset
>>>> + * becomes 0x80 based on previous round (0x293 - 0x213 = 0x80).
>>>> + * At the same time, insn at 0x292 is a 2-byte insn since its offset is
>>>> + * -124.
>>>> + *
>>>> + * pass6 will repeat the same code as in pass4 and this will prevent
>>>> + * eventual convergence.
>>>> + *
>>>> + * To fix this issue, we need to break je (2->6 bytes) <-> jmp (5->2 bytes)
>>>> + * cycle in the above. Let us limit the positive offset for 8bit cond jump
>>>> + * insn to mamximum 124 (0x7c). This way, the jmp insn will be always 2-bytes,
>>>> + * and the jit pass can eventually converge.
>>>> + */
>>>> +static bool is_imm8_cond_offset(int value)
>>>> +{
>>>> +       return value <= 124 && value >= -128;
>>>> +}
>>>> +
>>>>    static bool is_simm32(s64 value)
>>>>    {
>>>>           return value == (s64)(s32)value;
>>>> @@ -2231,7 +2276,7 @@ st:                       if (is_imm8(insn->off))
>>>>                                   return -EFAULT;
>>>>                           }
>>>>                           jmp_offset = addrs[i + insn->off] - addrs[i];
>>>> -                       if (is_imm8(jmp_offset)) {
>>>> +                       if (is_imm8_cond_offset(jmp_offset)) {
>>>>                                   if (jmp_padding) {
>>>>                                           /* To keep the jmp_offset valid, the extra bytes are
>>>>                                            * padded before the jump insn, so we subtract the
>>>> --
>>>> 2.43.5
>>>>