Re: cannot pass ebpf verify bound check due to compiler optimization

[Yonghong Song <yhs@fb.com>]

On 8/28/21 8:25 PM, rainkin wrote:
> Hi,
> 
> My kernel version is 4.19.
> 
> I have an eBPFprogram that accesses Map memory, and I check the bound
> of the Map value pointer offset when I use offset to access the Map.
> 
> However, I find a very strange situation: Although I have checked the
> bound in the source code, eBPF verify still reports an error saying
> that the bound is not checked and cannot pass the verification. But
> when I just a bpf_printk into the program, the program works well and
> passes the verification...
> 
> After investigating the disassembly code for several days, I finally
> figure out the root cause: eBPF verify logic is not compatible with
> LLVM compiler optimization.
> Specifically, there are two cases:
> 1. registers reloaded from the stack lose the state.
> The Map value pointer offset stored in a register is checked and eBPF
> verify successfully updates the bound state of the register. When
> registers are not enough, LLVM stores the register value in the stack
> and uses the register to perform other tasks. When the MAP needed to
> be accessed, the offset value is reloaded from the stack. However, the
> bound state of the offset is lost, which causing the verify error.
> 
> Intuitive solution: track the state of the stack value. In my
> understanding, the stack size is limited (512 bytes), it should be
> fine to track the whole stack and do not cause performance issues?
> 
> 2.  LLVM uses two registers to represent the same MAP pointer offset.
> When performing bound checking, register R1 is used and the bound
> check state is saved in R1.
> However, when accessing the MAP, register R2 is used which does not
> have bound checks, which causing the verify error...
> 
> Solution: It seems this issue cannot be solved easily by eBPF verify
> because the relationship between R1 and R2 is lost during LLVM
> compiler optimization.
> 
> These issues make me crazy... Do you guys have any workarounds to
> solve the above two issues before eBPF/LLVM is patched?

The above two issues are all due to register pressure in llvm 
optimization. Since there are not enough register, so spilling
happens for (1) above, and register allocator utilizes (2) above
to reduce spilling.

Recent kernel should have fix for both above cases.

In your case, adding a bpf_printk() and everything works fine.
llvm register allocator has its own heuristic. It is totally
possible that some code change might impact register allocation
quite dramatically w.r.t. kernel verification. It is hard to
give a good advice how to change your source code to have less
spills. But since you are using a old kernel, 4.19 should have
tail call support, maybe you want to break one program into
two to reduce potential register spills hence generate verifier
friendly code?

> 
> Thanks,
> rainkin
>