FoldAndOrOfICmpsUsingRanges makes it hard to produce code compliant with BPF verifier

[Spikhalskiy]

Current llvm (17&18) when compiling code with BPF target make transformations that hurt further BPF verification and there are seemingly no real workarounds to this problem at the moment.

The problem is demonstrated by the following example:

Source code

id = ctx->protocol;
if (id < 4 || id > 12)
 return 0;
*(u64 *)((void *)v + id) = 0;

is getting translated into something like

/* pseudo IR */
id = ctx->protocol;
tmp = id;
tmp += -13;
if (tmp < 0xfffffff7) goto next; // <- tmp and defined bounds are discarded here
v += id;
*v = 0; // <- BPF verification fails because of unbounded variable
next:

which fails BPF verification and leads to BPF loading/verification failures that typically look like

invalid access to map value, value_size=2052 off=4 size=0
R3 min value is outside of the allowed memory range

or R0 unbounded memory access, make sure to bounds check any such access.

Rewriting the code with a slightly different structure does NOT solve this issue:

id = ctx->protocol;
if (id >= 5 && id <= 12) // <- this is again done in a separate registry of BPF machine and discarded
  *(u64 *)((void *)v + id) = 0; // <- id value is getting loaded here without knowledge of the bounds check just performed above
else
   return 0;

Neither volatile nor asm volatile("" : "+r"(var)) provides a direct workaround too.

This problem and the proposed solution were originally raised by @yonghong-song in
https://reviews.llvm.org/D147078
https://reviews.llvm.org/D147968
but there were seemingly no new developments in almost a year.

This problem was also raised in discussions like
https://lore.kernel.org/all/f9c2ab1f-42a9-f5eb-f9bf-63402c6a8a62@uliege.be/T/ https://lpc.events/event/17/contributions/1648/attachments/1242/2525/Generating%20BPF%20Verifier%20Friendly%20Code%20with%20Clang.pdf

This presents a major paint point because of the absence of a clear workaround, leading to time-sinking fights against LLVM. Could some workaround be implemented until a solid solution is discussed and introduced? It may take the form of a new pragma that would disable FoldAndOrOfICmpsUsingRanges transformation that seems to be causing this issue.

[nikic]

If the BPF verifier does not support the range check idiom, then the BPF backend should convert it back into two comparisons.

[Spikhalskiy]

From my understanding, the main problem here is not a range check (BPF does support upper and lower bounds), but in a way how the code is transformed.

LLVM introduces a new variable (for BPF it's a register) in the IR and performs checks on that variable. This variable is discarded and an original variable (original register) is used in the functional call later. Because LLVM performed the checks on the temporary register and discarded it, the knowledge about the boundaries is lost for BPF. While LLVM knows that it's the same value.

I may provide an example of the original source code vs the final BPF bytecode to demonstrate an issue.

It's the first problem that I investigate with LLVM. I don't have a good grasp on the project, terminology, and what pieces are responsible for what yet. If something in my explanations doesn't make sense, sorry in advance, it very likely doesn't.

[nikic]

Yes, I get what you mean :) In LLVM, (X - C1) < C2 is the standard way to represent a two-sided range check. The BPF verifier does not understand this idiom, so the BPF backend should convert (X - C1) < C2 back into X > C3 && X < C4 (or X < C3 || X > C4).

[Spikhalskiy]

@yonghong-song I rebased your work done in https://reviews.llvm.org/D147968 onto master to include & test it in our internal llvm fork and opened it as a draft PR #97073. Hope it may make it easier for you to return to this story when you get a chance.