Skip to contentSkip to conversation

x86 BPF JIT failed to load a program with continuous JMPs

DISCUSSION Gary Lin 1 participant 1 message Nov 3, 2020 BPF

lore
Share & tools
lore

Gary Lin

author
#0 lore raw

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