x86 BPF JIT failed to load a program with continuous JMPs

[Gary Lin <glin@suse.com>]

Hi,

We recently got a bug report from a customer about the x86 BPF JIT, and
the bpf program is like this:

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
l7:     jeq #0x800, l8, l41
l8:     ld [x+16]
l9:     ja 41
  [... repeated ja 41 ]
l40:    ja 41
l41:    ret #0
l42:    ld #len
l43:    ret a

They declared a sock_filter array with a lot of "ja 41" in order to
replace them dynamically with other BPF instructions and attached the
program to a socket with setsockopt(SO_ATTACH_FILTER). It worked fine
with BPF interpreter until upgrading to the kernel with
BPF_JIT_ALWAYS_ON.

In the beginning, I thought it's rejected by the verifier due to
unreachable instructions. However, the verifier didn't involve since
it's attached through SO_ATTACH_FILTER. The program was sent to BPF
JIT directly and rejected with ENOTSUPP. In the end, I found that it
failed in bpf_int_jit_compile()(*). Every time do_jit() was invoked,
it removed one "ja 41" right before "ret #0", so bpf_int_jit_compile()
failed to remove all "ja 41" within 20 runs. If I reduced the number of
JMPs to 19, BPF JIT accepted the program. It seems a corner case that
BPF JIT could not handle.

A quick "fix" might be iterating do_jit() until the image converges,
but I guess the limited iteration is designed to bound the compilation
time of BPF JIT, so I'm not sure if this is a good option.

BTW, as a workaround, I suggested the customer to replace the JMPs with
0 offset JMPs so that do_jit() can optimize them out in 1 pass. But I
still would like to know how to handle this kind of programs properly.

Thanks

Gary Lin

(*) https://github.com/torvalds/linux/blob/v5.9/arch/x86/net/bpf_jit_comp.c#L1876-L1921