I'm playing with bcc to prototype an UDP load balancer.

I'm facing an issue that I didn't succeed to understand...

In my code I tried to validate my UDP packet using code like this :

    struct udphdr *udp;
    udp = iph + 1;
    if (udp + 1 > data_end)
        return XDP_DROP;
    __u16 udp_len = bpf_ntohs(udp->len);
    //__u16 udp_len = 8;
    if (udp_len < 8)
        return XDP_DROP;
    if (udp_len > 512) // TODO use a more approriate max value
        return XDP_DROP;
    if ((void *) udp + udp_len > data_end)
        return XDP_DROP;

And the verifier does not like it ..

28: (71) r2 = *(u8 *)(r7 +23)
29: (b7) r0 = 2
30: (55) if r2 != 0x11 goto pc+334
 R0=inv2 R1=pkt_end(id=0,off=0,imm=0) R2=inv17 R3=inv5 R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=34,imm=0) R8=pkt(id=0,off=34,r=34,imm=0) R9=pkt(id=0,off=14,r=34,imm=0) R10=fp0,call_-1
31: (bf) r2 = r8
32: (07) r2 += 8
33: (b7) r0 = 1
34: (2d) if r2 > r1 goto pc+330
 R0=inv1 R1=pkt_end(id=0,off=0,imm=0) R2=pkt(id=0,off=42,r=42,imm=0) R3=inv5 R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=42,imm=0) R8=pkt(id=0,off=34,r=42,imm=0) R9=pkt(id=0,off=14,r=42,imm=0) R10=fp0,call_-1
35: (69) r3 = *(u16 *)(r7 +38)
36: (dc) r3 = be16 r3
37: (bf) r2 = r3
38: (07) r2 += -8
39: (57) r2 &= 65535
40: (b7) r0 = 1
41: (25) if r2 > 0x1f8 goto pc+323
 R0=inv1 R1=pkt_end(id=0,off=0,imm=0) R2=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R3=inv(id=0) R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=42,imm=0) R8=pkt(id=0,off=34,r=42,imm=0) R9=pkt(id=0,off=14,r=42,imm=0) R10=fp0,call_-1
42: (bf) r2 = r7
43: (0f) r2 += r3
math between pkt pointer and register with unbounded min value is not allowed

I'm pretty sure the issue is about udp_len, that's why I tried to validate its value before to use it ... but without success...
When I set udp_len to 8 (just for testing) this seems to works. Any idea about that ?

Full code is available here : https://gist.github.com/sbernard31/d4fee7518a1ff130452211c0d355b3f7

(I'm using python-bpfcc  0.8.0-4 from debian sid with a 4.19.12 kernel)
(I don't know if this is the right place for this kind of question, )

On Wed, Mar 6, 2019 at 7:08 AM <contact@...> wrote:

I'm playing with bcc to prototype an UDP load balancer.

I'm facing an issue that I didn't succeed to understand...

In my code I tried to validate my UDP packet using code like this :

struct udphdr *udp;
udp = iph + 1;
if (udp + 1 > data_end)
return XDP_DROP;
__u16 udp_len = bpf_ntohs(udp->len);
//__u16 udp_len = 8;
if (udp_len < 8)
return XDP_DROP;
if (udp_len > 512) // TODO use a more approriate max value
return XDP_DROP;
if ((void *) udp + udp_len > data_end)
return XDP_DROP;

And the verifier does not like it ..

This is caused by compiler optimizations.

28: (71) r2 = *(u8 *)(r7 +23)
29: (b7) r0 = 2
30: (55) if r2 != 0x11 goto pc+334
R0=inv2 R1=pkt_end(id=0,off=0,imm=0) R2=inv17 R3=inv5 R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=34,imm=0) R8=pkt(id=0,off=34,r=34,imm=0) R9=pkt(id=0,off=14,r=34,imm=0) R10=fp0,call_-1
31: (bf) r2 = r8
32: (07) r2 += 8
33: (b7) r0 = 1
34: (2d) if r2 > r1 goto pc+330
R0=inv1 R1=pkt_end(id=0,off=0,imm=0) R2=pkt(id=0,off=42,r=42,imm=0) R3=inv5 R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=42,imm=0) R8=pkt(id=0,off=34,r=42,imm=0) R9=pkt(id=0,off=14,r=42,imm=0) R10=fp0,call_-1
35: (69) r3 = *(u16 *)(r7 +38)
36: (dc) r3 = be16 r3

r3 get the value from memory, its value could be any one as permitted
by the type.

37: (bf) r2 = r3
38: (07) r2 += -8
39: (57) r2 &= 65535
40: (b7) r0 = 1
41: (25) if r2 > 0x1f8 goto pc+323

test is done by r2. We indeed get better range for r2 (below:
R2=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) )
but r3 range is not tightened.

R0=inv1 R1=pkt_end(id=0,off=0,imm=0) R2=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R3=inv(id=0) R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=42,imm=0) R8=pkt(id=0,off=34,r=42,imm=0) R9=pkt(id=0,off=14,r=42,imm=0) R10=fp0,call_-1
42: (bf) r2 = r7
43: (0f) r2 += r3
math between pkt pointer and register with unbounded min value is not allowed

Here, we use r3 to do arith and the verifier not happy. If we use the
tightened old r2, it may work.
The compiler does the right thing, just verifier is not advanced enough.

I'm pretty sure the issue is about udp_len, that's why I tried to validate its value before to use it ... but without success...
When I set udp_len to 8 (just for testing) this seems to works. Any idea about that ?

Yes, you will need some source workaround. You could try below (untested):

if (udp_len > 512) // TODO use a more approriate max value
return XDP_DROP;
+ udp_len = udp_len & 0x1ff;
if ((void *) udp + udp_len > data_end)
return XDP_DROP;

Full code is available here : https://gist.github.com/sbernard31/d4fee7518a1ff130452211c0d355b3f7

(I'm using python-bpfcc 0.8.0-4 from debian sid with a 4.19.12 kernel)
(I don't know if this is the right place for this kind of question, )

Yonghong Song writes:

On Wed, Mar 6, 2019 at 7:08 AM <contact@...> wrote:

I'm playing with bcc to prototype an UDP load balancer.

I'm facing an issue that I didn't succeed to understand...

In my code I tried to validate my UDP packet using code like this :

struct udphdr *udp;
udp = iph + 1;
if (udp + 1 > data_end)
return XDP_DROP;
__u16 udp_len = bpf_ntohs(udp->len);
//__u16 udp_len = 8;
if (udp_len < 8)
return XDP_DROP;
if (udp_len > 512) // TODO use a more approriate max value
return XDP_DROP;
if ((void *) udp + udp_len > data_end)
return XDP_DROP;

And the verifier does not like it ..

This is caused by compiler optimizations.

28: (71) r2 = *(u8 *)(r7 +23)
29: (b7) r0 = 2
30: (55) if r2 != 0x11 goto pc+334
R0=inv2 R1=pkt_end(id=0,off=0,imm=0) R2=inv17 R3=inv5 R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=34,imm=0) R8=pkt(id=0,off=34,r=34,imm=0) R9=pkt(id=0,off=14,r=34,imm=0) R10=fp0,call_-1
31: (bf) r2 = r8
32: (07) r2 += 8
33: (b7) r0 = 1
34: (2d) if r2 > r1 goto pc+330
R0=inv1 R1=pkt_end(id=0,off=0,imm=0) R2=pkt(id=0,off=42,r=42,imm=0) R3=inv5 R6=ctx(id=0,off=0,imm=0) R7=pkt(id=0,off=0,r=42,imm=0) R8=pkt(id=0,off=34,r=42,imm=0) R9=pkt(id=0,off=14,r=42,imm=0) R10=fp0,call_-1
35: (69) r3 = *(u16 *)(r7 +38)
36: (dc) r3 = be16 r3

r3 get the value from memory, its value could be any one as permitted
by the type.

37: (bf) r2 = r3
38: (07) r2 += -8
39: (57) r2 &= 65535
40: (b7) r0 = 1
41: (25) if r2 > 0x1f8 goto pc+323

test is done by r2. We indeed get better range for r2 (below:
R2=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) )
but r3 range is not tightened.

I had run into similar issue when debugging some other rejection before
JMP32 introduced when LLVM was generating similar sequences under defult
64-bit mode, but IIRC LLVM generates betweer sequences with -mattr=alu32,
under which it will just use w3 (as the type should be optimized into
32-bit) for the comparison.

So, I guess this testcase could have easier sequence for verifier under
ALU32 mode. But for this case, BPF_END is used which doesn't have
sub-register code-gen support inside LLVM for be16 and be32 at the moment
(noticed this several days ago when doing some other benchmarking).

If I have .i file, I could do a quick prototype to see if ALU32 could
improve this.

Regards,
Jiong

35: (69) r3 = *(u16 *)(r7 +38)
36: (dc) r3 = be16 r3

r3 get the value from memory, its value could be any one as permitted
by the type.

Does it mean that r3 is considered as be16 ? I do not understand why as I explicitly convert it in u16.

This output language is a readable format of bpf bytecode, right ? Is there any documentation to lean/understand it ? 

The compiler does the right thing, just verifier is not advanced enough.

Is it worthy to share this issue of verifier.c with bpf maintainers ? The compiler which is used here is clang which is called by bcc, right ?

Yes, you will need some source workaround. You could try below (untested):
+ udp_len = udp_len & 0x1ff;

I tested it and it seems to work. Thx a lot !!

But that means I can not use the u16 max value ?

On Fri, Mar 8, 2019 at 9:22 AM Simon <contact@...> wrote:

35: (69) r3 = *(u16 *)(r7 +38)
36: (dc) r3 = be16 r3

r3 get the value from memory, its value could be any one as permitted
by the type.

Does it mean that r3 is considered as be16 ? I do not understand why as I explicitly convert it in u16.

The be16 is to convert r3 with big endian encoding. If the host system
is big endian, it will do nothing. Otherwise,
it will convert from little endian to big endian.

This output language is a readable format of bpf bytecode, right ? Is there any documentation to lean/understand it ?

Yes, there is no documentation. It intends to be self explanatory. I
guess "be16" is special and may need some documentation. Otherwise
assembly-style codes should be easy to understand.

The compiler does the right thing, just verifier is not advanced enough.

Is it worthy to share this issue of verifier.c with bpf maintainers ? The compiler which is used here is clang which is called by bcc, right ?

I am also a regular kernel/bpf reviewer. The bpf maintainers/community
are aware of this limitation. As you mentioned, the verifier is
already very complex. To implement complex tracking like described in
this thread will make verifier even more complex, hence this is
delayed. One of reason is that we have reasonable, although
unpleasant, workarounds.

Yes, it is compiled with clang.

Yes, you will need some source workaround. You could try below (untested):
+ udp_len = udp_len & 0x1ff;

I tested it and it seems to work. Thx a lot !!

But that means I can not use the u16 max value ?

You can. I add that because you have a test to limit the range of the
value to 511.

Hi Jiong,
   I didn't succeed to generate .i file using bcc, but since severals days I try to rewrite my code without bcc. (directly with bpf C api / clang / iproute2)

   I didn't finished yet, but I have a reduced version compared to the one I written for bcc and I face the same issue, so this time I can get .i file easily.

   So the .i file is as attachment.
   The corresponding code is available here : https://github.com/sbernard31/udploadbalancer/blob/44fe1ea549a55ab23c7d1b70e9651df6f61fb865/ulb.c

   The error is still  math between pkt pointer and register with unbounded min value is not allowed

   The verifier output is pretty much the same :

27: (71) r4 = *(u8 *)(r1 +23)
28: (b7) r0 = 2
29: (55) if r4 != 0x11 goto pc+15
 R0=inv2 R1=pkt(id=0,off=0,r=34,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=34,r=34,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
30: (07) r3 += 8
31: (b7) r0 = 1
32: (2d) if r3 > r2 goto pc+12
 R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=42,r=42,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
33: (69) r3 = *(u16 *)(r1 +38)
34: (dc) r3 = be16 r3
35: (bf) r4 = r3
36: (07) r4 += -8
37: (57) r4 &= 65535
38: (b7) r0 = 1
39: (25) if r4 > 0x1f8 goto pc+5
 R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

I'm pretty sure the bcc version I used before linked statically clang/llvm v7.0.
Here I use a v6.0.

The funny part ...  This modification about just adding some logs/printk makes this error disappear : https://github.com/sbernard31/udploadbalancer/commit/0145538c7b35e2a6bb92225f69a45f4bee120a6d

All of those erifier errors make me a bit crazy (╥_╥)

HTH

Simon

On 27 Mar 2019, at 14:53, Simon <contact@...> wrote:

Hi Jiong,
I didn't succeed to generate .i file using bcc, but since severals days I try to rewrite my code without bcc. (directly with bpf C api / clang / iproute2)

I didn't finished yet, but I have a reduced version compared to the one I written for bcc and I face the same issue, so this time I can get .i file easily.

So the .i file is as attachment.
The corresponding code is available here : https://github.com/sbernard31/udploadbalancer/blob/44fe1ea549a55ab23c7d1b70e9651df6f61fb865/ulb.c

Hi Simon,

Thanks for the .i, I prototyped some byteswap code-gen change, but
seems doesn’t help your issue which could narrow down to the following
general code pattern:

unsigned char cal(unsigned int a, unsigned char *b)
{
if (a < 8 || a > 512)
return 0;

return b[a];
}

LLVM is doing some optimisation, instead of generating two separate comparison,
a < 8 and a > 512, it is combining them because a negative value when casted
into unsigned must be bigger than 504, so above code turned into

unsigned char cal(unsigned int a, unsigned char *b)
{
unsigned tmp = a - 8;
if (tmp > 504)
return 0;

return b[a];
}

The consequence of such optimisation is new variable “tmp” is used for comparison
And verifier now know “tmp”'s value range instead of the original “a” which is used
later adding to a packet pointer. A unknown value range of “a” then caused the
verifier rejection.

So, I suspect any code using above c code pattern will likely be rejected.

1. combinable comparisons
2. the variable involved in the comparison used later in places requiring value range

Regards,
Jiong

The error is still math between pkt pointer and register with unbounded min value is not allowed

The verifier output is pretty much the same :

27: (71) r4 = *(u8 *)(r1 +23)
28: (b7) r0 = 2
29: (55) if r4 != 0x11 goto pc+15
R0=inv2 R1=pkt(id=0,off=0,r=34,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=34,r=34,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
30: (07) r3 += 8
31: (b7) r0 = 1
32: (2d) if r3 > r2 goto pc+12
R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=42,r=42,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
33: (69) r3 = *(u16 *)(r1 +38)
34: (dc) r3 = be16 r3
35: (bf) r4 = r3
36: (07) r4 += -8
37: (57) r4 &= 65535
38: (b7) r0 = 1
39: (25) if r4 > 0x1f8 goto pc+5
R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

I'm pretty sure the bcc version I used before linked statically clang/llvm v7.0.
Here I use a v6.0.

The funny part ... This modification about just adding some logs/printk makes this error disappear : https://github.com/sbernard31/udploadbalancer/commit/0145538c7b35e2a6bb92225f69a45f4bee120a6d

All of those erifier errors make me a bit crazy (╥_╥)

HTH

Simon


<ulb.i>

On 27 Mar 2019, at 16:11, Jiong Wang via Lists.Iovisor.Org <jiong.wang=netronome.com@...> wrote:

On 27 Mar 2019, at 14:53, Simon <contact@...> wrote:

Hi Jiong,
I didn't succeed to generate .i file using bcc, but since severals days I try to rewrite my code without bcc. (directly with bpf C api / clang / iproute2)

I didn't finished yet, but I have a reduced version compared to the one I written for bcc and I face the same issue, so this time I can get .i file easily.

So the .i file is as attachment.
The corresponding code is available here : https://github.com/sbernard31/udploadbalancer/blob/44fe1ea549a55ab23c7d1b70e9651df6f61fb865/ulb.c

Hi Simon,

Thanks for the .i, I prototyped some byteswap code-gen change, but
seems doesn’t help your issue which could narrow down to the following
general code pattern:

unsigned char cal(unsigned int a, unsigned char *b)
{
if (a < 8 || a > 512)
return 0;

return b[a];
}

LLVM is doing some optimisation, instead of generating two separate comparison,
a < 8 and a > 512, it is combining them because a negative value when casted
into unsigned must be bigger than 504, so above code turned into

unsigned char cal(unsigned int a, unsigned char *b)
{
unsigned tmp = a - 8;
if (tmp > 504)
return 0;

return b[a];
}

The consequence of such optimisation is new variable “tmp” is used for comparison
And verifier now know “tmp”'s value range instead of the original “a” which is used
later adding to a packet pointer. A unknown value range of “a” then caused the
verifier rejection.

So, I suspect any code using above c code pattern will likely be rejected.

1. combinable comparisons
2. the variable involved in the comparison used later in places requiring value range

And in your code, after you insert those printk, they made the following
two comparisons non-combinable any more, so udp_len is used for the
comparison and got correct value range to pass the later pkt pointer
addition check.


if (udp_len < 8) {
return XDP_DROP;
}
if (udp_len > 512) {
return XDP_DROP;
}

Regards,
Jiong

The error is still math between pkt pointer and register with unbounded min value is not allowed

The verifier output is pretty much the same :

27: (71) r4 = *(u8 *)(r1 +23)
28: (b7) r0 = 2
29: (55) if r4 != 0x11 goto pc+15
R0=inv2 R1=pkt(id=0,off=0,r=34,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=34,r=34,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
30: (07) r3 += 8
31: (b7) r0 = 1
32: (2d) if r3 > r2 goto pc+12
R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=pkt(id=0,off=42,r=42,imm=0) R4=inv17 R5=inv5 R10=fp0,call_-1
33: (69) r3 = *(u16 *)(r1 +38)
34: (dc) r3 = be16 r3
35: (bf) r4 = r3
36: (07) r4 += -8
37: (57) r4 &= 65535
38: (b7) r0 = 1
39: (25) if r4 > 0x1f8 goto pc+5
R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

I'm pretty sure the bcc version I used before linked statically clang/llvm v7.0.
Here I use a v6.0.

The funny part ... This modification about just adding some logs/printk makes this error disappear : https://github.com/sbernard31/udploadbalancer/commit/0145538c7b35e2a6bb92225f69a45f4bee120a6d

All of those erifier errors make me a bit crazy (╥_╥)

HTH

Simon


<ulb.i>

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

On 27 Mar 2019, at 16:43, Simon <contact@...> wrote:

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

Just my humble opinion, I would recommend:

1. get used to verifier rejection information, for example:

R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

It tells you the status of each registers at the rejection point,
for example, now R3 is “inv”, meaning a scalar value (not a pointer),
and is without value range, then r4 has value range, and maximum value
is 504.

2. known what verifier will reject. Could refer to:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/verifier?id=473c5daa86ffe91e937856cc32b4faa61db2e3e3

those are unit examples of what will be rejected, and some of them are with
meaningful test name or comments so could be easy to understand.

Regards,
Jiong

On Wed, Mar 27, 2019 at 10:17 AM Jiong Wang <jiong.wang@...> wrote:

On 27 Mar 2019, at 16:43, Simon <contact@...> wrote:

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

Just my humble opinion, I would recommend:

1. get used to verifier rejection information, for example:

R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

It tells you the status of each registers at the rejection point,
for example, now R3 is “inv”, meaning a scalar value (not a pointer),
and is without value range, then r4 has value range, and maximum value
is 504.

If you use BPF constructor debug=16 flag, it will print out the
register state for every insn if you are even more curious.

2. known what verifier will reject. Could refer to:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/verifier?id=473c5daa86ffe91e937856cc32b4faa61db2e3e3

those are unit examples of what will be rejected, and some of them are with
meaningful test name or comments so could be easy to understand.

To resolve this issue, llvm may need to do more:
- prevent/undo optimization which may cause ultimate verifier rejections.
- provide hints (e.g., through BTF) to verifier so verifier may
selectively do some analysis
or enable some tracking for the cases where BTF instructed to
handle. For example,
BTF may tell verifier two register have the same state at a
particular point and verifier
only needs to check these two registers with limited range and no
others, etc.

Regards,
Jiong

Why is it required that llvm compile the BPF code with -O2? That seems to be part of what is causing these verifier problems...

On Wed, Mar 27, 2019 at 1:48 PM Pablo Alvarez via Lists.Iovisor.Org
<palvarez=akamai.com@...> wrote:

Why is it required that llvm compile the BPF code with -O2? That seems
to be part of what is causing these verifier problems...

-O0 won't work as helper call will become an indirect call
static void *(*bpf_map_lookup_elem)(void *map, void *key) =
(void *) BPF_FUNC_map_lookup_elem;
Another reason is below value tracking in verifier.

The verifier does not handle value spill well. It kept track of map
pointers, packet pointers, etc.
But if a particular value is spilled, later on, when reload from
stack, it will become unknown.
For example,
r1 = 10; /* verifier state: r1 = 10 */
*(r10 - 40) = r1;
r2 = *(r10 - 40); /* verifier state: r2, unknown */

The reason is that keep tracking of values could increase verification
time quite a bit.
This is measured sometime back, but it may warrant to do some measurement again
at this moment to see whether can relax this restriction.

So practically -O0 won't work. -O1 may or may not work and most people
do not use it.
-O2 is preferred. Also for performance reasons, we want to make -O2
work as BPF JIT
inside the kernel does not do any optimization, it is simple one insn
each time translation.

On 3/27/19 4:23 PM, Yonghong Song wrote:

On Wed, Mar 27, 2019 at 10:17 AM Jiong Wang <jiong.wang@...> wrote:

On 27 Mar 2019, at 16:43, Simon <contact@...> wrote:

Thx a lot for your time Jiong.

The more I played with bpf/xdp, the more I understand that the challenge is about making "optimized byte code" compliant for the verifier.

How could I do this kind of checks my self ? I mean looking how llvm optimized my code ? (to be able to do same kind of analyses you do above?)

Just my humble opinion, I would recommend:

1. get used to verifier rejection information, for example:

R0=inv1 R1=pkt(id=0,off=0,r=42,imm=0) R2=pkt_end(id=0,off=0,imm=0) R3=inv(id=0) R4=inv(id=0,umax_value=504,var_off=(0x0; 0x1ff)) R5=inv5 R10=fp0,call_-1
40: (0f) r1 += r3
math between pkt pointer and register with unbounded min value is not allowed

It tells you the status of each registers at the rejection point,
for example, now R3 is “inv”, meaning a scalar value (not a pointer),
and is without value range, then r4 has value range, and maximum value
is 504.

If you use BPF constructor debug=16 flag, it will print out the
register state for every insn if you are even more curious.

2. known what verifier will reject. Could refer to:

https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git/tree/tools/testing/selftests/bpf/verifier?id=473c5daa86ffe91e937856cc32b4faa61db2e3e3

those are unit examples of what will be rejected, and some of them are with
meaningful test name or comments so could be easy to understand.

To resolve this issue, llvm may need to do more:
- prevent/undo optimization which may cause ultimate verifier rejections.
- provide hints (e.g., through BTF) to verifier so verifier may
selectively do some analysis
or enable some tracking for the cases where BTF instructed to
handle. For example,
BTF may tell verifier two register have the same state at a
particular point and verifier
only needs to check these two registers with limited range and no
others, etc.

Regards,
Jiong

Hi, Simon,

Finally got some time to deep dive into the verifier for this issue.
I filed an issue https://github.com/iovisor/bcc/issues/2463 with
possible suggestion to add a new checksum calculation helper
for xdp. I forgot what is your ultimate workaround for this issue.
Could you comment on the issue?

Thanks!

Yonghong