Re: [PATCH] bpf,x64: pad NOPs to make images converge more easily

[Gary Lin <glin@suse.com>]

On Mon, Dec 14, 2020 at 11:56:22AM +0800, Gary Lin wrote:
> On Fri, Dec 11, 2020 at 09:05:05PM +0100, Daniel Borkmann wrote:
> > On 12/11/20 9:19 AM, Gary Lin wrote:
> > > The x64 bpf jit expects bpf images converge within the given passes, but
> > > it could fail to do so with some corner cases. For example:
> > > 
> > >        l0:     ldh [4]
> > >        l1:     jeq #0x537d, l2, l40
> > >        l2:     ld [0]
> > >        l3:     jeq #0xfa163e0d, l4, l40
> > >        l4:     ldh [12]
> > >        l5:     ldx #0xe
> > >        l6:     jeq #0x86dd, l41, l7
> > >        l8:     ld [x+16]
> > >        l9:     ja 41
> > > 
> > >          [... repeated ja 41 ]
> > > 
> > >        l40:    ja 41
> > >        l41:    ret #0
> > >        l42:    ld #len
> > >        l43:    ret a
> > > 
> > > This bpf program contains 32 "ja 41" instructions which are effectively
> > > NOPs and designed to be replaced with valid code dynamically. Ideally,
> > > bpf jit should optimize those "ja 41" instructions out when translating
> > > the bpf instructions into x86_64 machine code. However, do_jit() can
> > > only remove one "ja 41" for offset==0 on each pass, so it requires at
> > > least 32 runs to eliminate those JMPs and exceeds the current limit of
> > > passes (20). In the end, the program got rejected when BPF_JIT_ALWAYS_ON
> > > is set even though it's legit as a classic socket filter.
> > > 
> > > To make the image more likely converge within 20 passes, this commit
> > > pads some instructions with NOPs in the last 5 passes:
> > > 
> > > 1. conditional jumps
> > >    A possible size variance comes from the adoption of imm8 JMP. If the
> > >    offset is imm8, we calculate the size difference of this BPF instruction
> > >    between the previous pass and the current pass and fill the gap with NOPs.
> > >    To avoid the recalculation of jump offset, those NOPs are inserted before
> > >    the JMP code, so we have to subtract the 2 bytes of imm8 JMP when
> > >    calculating the NOP number.
> > > 
> > > 2. BPF_JA
> > >    There are two conditions for BPF_JA.
> > >    a.) nop jumps
> > >      If this instruction is not optimized out in the previous pass,
> > >      instead of removing it, we insert the equivalent size of NOPs.
> > >    b.) label jumps
> > >      Similar to condition jumps, we prepend NOPs right before the JMP
> > >      code.
> > > 
> > > To make the code concise, emit_nops() is modified to use the signed len and
> > > return the number of inserted NOPs.
> > > 
> > > To support bpf-to-bpf, a new flag, padded, is introduced to 'struct bpf_prog'
> > > so that bpf_int_jit_compile() could know if the program is padded or not.
> > 
> > Please also add multiple hand-crafted test cases e.g. for bpf-to-bpf calls into
> > test_verifier (which is part of bpf kselftests) that would exercise this corner
> > case in x86 jit where we would start to nop pad so that there is proper coverage,
> > too.
> > 
> The corner case I had in the commit description is likely being rejected by
> the verifier because most of those "ja 41" are unreachable instructions.
> Is there any known test case that needs more than 15 passes in x86 jit?
> 
Just an idea. Besides the mentioned corner case, how about making
PADDING_PASSES dynamically configurable (sysfs?) and reusing the existing
test cases? So that we can have a script to set PADDING_PASSES from 1 to 20
and run the bpf selftests separately. This guarantees that the padding
strategy will be applied at least in a certain PADDING_PASSES settings.

Gary Lin