Topics

R? min value is negative, either use unsigned or 'var &= const' #verifier

Simon
 

I suspect I fall in another issue with verifier.

This code (taking from katran : I just changed data_size type to __u32):

__attribute__((__always_inline__))
static inline void ipv4_l4_csum(void *data_start, __u32 data_size,
                                __u64 *csum, struct iphdr *iph) {
  __u32 tmp = 0;
  *csum = bpf_csum_diff(0, 0, &iph->saddr, sizeof(__be32), *csum);
  *csum = bpf_csum_diff(0, 0, &iph->daddr, sizeof(__be32), *csum);
  tmp = __builtin_bswap32((__u32)(iph->protocol));
  *csum = bpf_csum_diff(0, 0, &tmp, sizeof(__u32), *csum);
  tmp = __builtin_bswap32((__u32)(data_size));
  *csum = bpf_csum_diff(0, 0, &tmp, sizeof(__u32), *csum);
  *csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);
  *csum = csum_fold_helper(*csum);
}
But it brings to this verifier issue :
93: (67) r0 <<= 32
294: (c7) r0 s>>= 32
295: (b7) r1 = 0
296: (b7) r2 = 0
297: (bf) r3 = r8
298: (79) r4 = *(u64 *)(r10 -40)
299: (bf) r5 = r0
300: (85) call bpf_csum_diff#28
R4 min value is negative, either use unsigned or 'var &= const'
The whole code is available here.
This is maybe relative to my previous issue.

Simon
 

I tried to understand again this verifier error again and probably my previous post does not contain enough information.

I  understand that :

93: (67) r0 <<= 32
294: (c7) r0 s>>= 32
295: (b7) r1 = 0
296: (b7) r2 = 0
297: (bf) r3 = r8
298: (79) r4 = *(u64 *)(r10 -40)
299: (bf) r5 = r0
300: (85) call bpf_csum_diff#28
R4 min value is negative, either use unsigned or 'var &= const'

is about this line  (in ipv4_l4_csum)

  *csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);

R1=0,
R2=0,
R3= R8=pkt(id=0,off=34,r=42,imm=0) = data_start =  a pointer to struct udphdr *udp
R4= something in the stack  = data_size = __u16 udp_len

So I can not understand how this bring to R4 min value is negative, either use unsigned or 'var &= const'

298: (79) r4 = *(u64 *)(r10 -40)

As I understand this line, r4 will get a value in the stack (R10=fp0,call_-1 fp-48=pkt) and cast  this value in a u64, so unsigned. (min value = 0)

(By the way I can not understand why this is a u64 and not a u16 as udp_len variable or u32 as  data_size parameter of ipv4_l4_csum function or u32 as tosize from bpf_csum_diff function...)

I tried to use the &= tricks like :

data_size = data_size & 0x1ff;
*csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);

Same issue ...

Here a more longer trace from the verifier :

R0=inv(id=0,umax_value=4295032831,var_off=(0x0; 0x1ffffffff)) 
R1=inv(id=0,umax_value=65536,var_off=(0x0; 0x1ffff))
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=30,r=42,imm=0)
R10=fp0,call_-1 fp-48=pkt 239: (57) r0 &= 65535 240: (0f) r0 += r1 241: (bf) r1 = r0 242: (77) r1 >>= 16 243: (0f) r1 += r0 244: (a7) r1 ^= -1 245: (6b) *(u16 *)(r7 +24) = r1 246: (b7) r1 = 0 247: (6b) *(u16 *)(r7 +40) = r1 248: (b7) r1 = 0 249: (b7) r2 = 0 250: (79) r3 = *(u64 *)(r10 -48) 251: (b7) r4 = 4 252: (b7) r5 = 0 253: (85) call bpf_csum_diff#28 254: (67) r0 <<= 32 255: (c7) r0 s>>= 32 256: (b7) r1 = 0 257: (b7) r2 = 0 258: (bf) r3 = r9 259: (b7) r4 = 4 260: (bf) r5 = r0 261: (85) call bpf_csum_diff#28 262: (71) r1 = *(u8 *)(r7 +23) 263: (dc) r1 = be32 r1 264: (63) *(u32 *)(r10 -24) = r1 265: (67) r0 <<= 32 266: (c7) r0 s>>= 32 267: (bf) r9 = r10 268: (07) r9 += -24 269: (b7) r1 = 0 270: (b7) r2 = 0 271: (bf) r3 = r9 272: (b7) r4 = 4 273: (bf) r5 = r0 274: (85) call bpf_csum_diff#28 275: (79) r1 = *(u64 *)(r10 -40) 276: (dc) r1 = be32 r1 277: (63) *(u32 *)(r10 -24) = r1 278: (67) r0 <<= 32 279: (c7) r0 s>>= 32 280: (b7) r1 = 0 281: (b7) r2 = 0 282: (bf) r3 = r9 283: (b7) r4 = 4 284: (bf) r5 = r0 285: (85) call bpf_csum_diff#28 286: (67) r0 <<= 32 287: (c7) r0 s>>= 32 288: (b7) r1 = 0 289: (b7) r2 = 0 290: (bf) r3 = r8 291: (79) r4 = *(u64 *)(r10 -40) 292: (bf) r5 = r0 293: (85) call bpf_csum_diff#28

I reference the commit instead of repository to keep the link consistent over the time : https://github.com/sbernard31/udploadbalancer/tree/5ca93d0893a60bc70a75f30eb5cfde496a9e5d93

Again do not hesitate to redirect me to better place if I'm not asking at the right place :)

Thx again for your time.

Yonghong Song
 

On Mon, Mar 11, 2019 at 4:08 AM Simon <contact@...> wrote:

I tried to understand again this verifier error again and probably my previous post does not contain enough information.

I understand that :

93: (67) r0 <<= 32
294: (c7) r0 s>>= 32
295: (b7) r1 = 0
296: (b7) r2 = 0
297: (bf) r3 = r8
298: (79) r4 = *(u64 *)(r10 -40)
299: (bf) r5 = r0
300: (85) call bpf_csum_diff#28
R4 min value is negative, either use unsigned or 'var &= const'

is about this line (in ipv4_l4_csum)

*csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);

R1=0,
R2=0,
R3= R8=pkt(id=0,off=34,r=42,imm=0) = data_start = a pointer to struct udphdr *udp
R4= something in the stack = data_size = __u16 udp_len

So I can not understand how this bring to R4 min value is negative, either use unsigned or 'var &= const'
I took a brief look. Indeed, it is very strange. I can see proper
value of udp_len is stored into
r10 - 40, but when it is retrieved later, the value became unkown....

I will try to experiment with this problem later this week.

Could you do me a favor to make it reproducible with python2? My env.
flexible to rebuild/retry with kernel is python2 friendly.


298: (79) r4 = *(u64 *)(r10 -40)

As I understand this line, r4 will get a value in the stack (R10=fp0,call_-1 fp-48=pkt) and cast this value in a u64, so unsigned. (min value = 0)

(By the way I can not understand why this is a u64 and not a u16 as udp_len variable or u32 as data_size parameter of ipv4_l4_csum function or u32 as tosize from bpf_csum_diff function...)

I tried to use the &= tricks like :

data_size = data_size & 0x1ff;
*csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);

Same issue ...

Here a more longer trace from the verifier :

R0=inv(id=0,umax_value=4295032831,var_off=(0x0; 0x1ffffffff))
R1=inv(id=0,umax_value=65536,var_off=(0x0; 0x1ffff))
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=30,r=42,imm=0)
R10=fp0,call_-1 fp-48=pkt
239: (57) r0 &= 65535
240: (0f) r0 += r1
241: (bf) r1 = r0
242: (77) r1 >>= 16
243: (0f) r1 += r0
244: (a7) r1 ^= -1
245: (6b) *(u16 *)(r7 +24) = r1
246: (b7) r1 = 0
247: (6b) *(u16 *)(r7 +40) = r1
248: (b7) r1 = 0
249: (b7) r2 = 0
250: (79) r3 = *(u64 *)(r10 -48)
251: (b7) r4 = 4
252: (b7) r5 = 0
253: (85) call bpf_csum_diff#28
254: (67) r0 <<= 32
255: (c7) r0 s>>= 32
256: (b7) r1 = 0
257: (b7) r2 = 0
258: (bf) r3 = r9
259: (b7) r4 = 4
260: (bf) r5 = r0
261: (85) call bpf_csum_diff#28
262: (71) r1 = *(u8 *)(r7 +23)
263: (dc) r1 = be32 r1
264: (63) *(u32 *)(r10 -24) = r1
265: (67) r0 <<= 32
266: (c7) r0 s>>= 32
267: (bf) r9 = r10
268: (07) r9 += -24
269: (b7) r1 = 0
270: (b7) r2 = 0
271: (bf) r3 = r9
272: (b7) r4 = 4
273: (bf) r5 = r0
274: (85) call bpf_csum_diff#28
275: (79) r1 = *(u64 *)(r10 -40)
276: (dc) r1 = be32 r1
277: (63) *(u32 *)(r10 -24) = r1
278: (67) r0 <<= 32
279: (c7) r0 s>>= 32
280: (b7) r1 = 0
281: (b7) r2 = 0
282: (bf) r3 = r9
283: (b7) r4 = 4
284: (bf) r5 = r0
285: (85) call bpf_csum_diff#28
286: (67) r0 <<= 32
287: (c7) r0 s>>= 32
288: (b7) r1 = 0
289: (b7) r2 = 0
290: (bf) r3 = r8
291: (79) r4 = *(u64 *)(r10 -40)
292: (bf) r5 = r0
293: (85) call bpf_csum_diff#28

I reference the commit instead of repository to keep the link consistent over the time : https://github.com/sbernard31/udploadbalancer/tree/5ca93d0893a60bc70a75f30eb5cfde496a9e5d93

Again do not hesitate to redirect me to better place if I'm not asking at the right place :)

Thx again for your time.

Simon
 

Here a python 2 version.

Yonghong Song
 

On Mon, Mar 11, 2019 at 11:13 PM Yonghong Song via Lists.Iovisor.Org
<ys114321=gmail.com@...> wrote:

On Mon, Mar 11, 2019 at 4:08 AM Simon <contact@...> wrote:

I tried to understand again this verifier error again and probably my previous post does not contain enough information.

I understand that :

93: (67) r0 <<= 32
294: (c7) r0 s>>= 32
295: (b7) r1 = 0
296: (b7) r2 = 0
297: (bf) r3 = r8
298: (79) r4 = *(u64 *)(r10 -40)
299: (bf) r5 = r0
300: (85) call bpf_csum_diff#28
R4 min value is negative, either use unsigned or 'var &= const'

is about this line (in ipv4_l4_csum)

*csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);

R1=0,
R2=0,
R3= R8=pkt(id=0,off=34,r=42,imm=0) = data_start = a pointer to struct udphdr *udp
R4= something in the stack = data_size = __u16 udp_len

So I can not understand how this bring to R4 min value is negative, either use unsigned or 'var &= const'
I took a brief look. Indeed, it is very strange. I can see proper
value of udp_len is stored into
r10 - 40, but when it is retrieved later, the value became unkown....

I will try to experiment with this problem later this week.

Could you do me a favor to make it reproducible with python2? My env.
flexible to rebuild/retry with kernel is python2 friendly.



298: (79) r4 = *(u64 *)(r10 -40)

As I understand this line, r4 will get a value in the stack (R10=fp0,call_-1 fp-48=pkt) and cast this value in a u64, so unsigned. (min value = 0)
The reason for the failure is due spill/reload does not preserve the
original register state for scalar value.
Look at the kernel function:
static bool is_spillable_regtype(enum bpf_reg_type type)
{
switch (type) {
case PTR_TO_MAP_VALUE:
case PTR_TO_MAP_VALUE_OR_NULL:
case PTR_TO_STACK:
case PTR_TO_CTX:
case PTR_TO_PACKET:
case PTR_TO_PACKET_META:
case PTR_TO_PACKET_END:
case PTR_TO_FLOW_KEYS:
case CONST_PTR_TO_MAP:
case PTR_TO_SOCKET:
case PTR_TO_SOCKET_OR_NULL:
case PTR_TO_SOCK_COMMON:
case PTR_TO_SOCK_COMMON_OR_NULL:
case PTR_TO_TCP_SOCK:
case PTR_TO_TCP_SOCK_OR_NULL:
return true;
default:
return false;
}
}

The original variable udp_len is defined as
__u16 udp_len = bpf_ntohs(udp->len);
if (udp_len < 8)
return XDP_DROP;
if (udp_len > 512) // TODO use a more approriate max value
return XDP_DROP;
udp_len = udp_len & 0x1ff;

and it is saved to stack, and its register type is SCALAR_VALUE.
But since SCALAR_VALUE is not part of is_spillable_regtype() so
when the value is reloaded from stack to register, the original
state is not copied and the worst case scalar value is assumed
and this will incur the error you see.

I tried to add SCALAR_VALUE to the is_spillable_regtype()
and it does not work and more changes in verifier is required.

The trick like `data_size = data_size & 0x1ff` may not work
as the compiler may optimize it away and the original spill
may still exist.

The workaound could be to repeat
__u16 udp_len = bpf_ntohs(udp->len);
here udp is a pointer to the package, even it is spilled, its register
state can be restored.

I will take a look at SCALAR_VALUE issue later on.
But if you or anybody has cycles and want to look into this issue,
feel free to do so.

Thanks!

Yonghong


(By the way I can not understand why this is a u64 and not a u16 as udp_len variable or u32 as data_size parameter of ipv4_l4_csum function or u32 as tosize from bpf_csum_diff function...)

I tried to use the &= tricks like :

data_size = data_size & 0x1ff;
*csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);

Same issue ...

Here a more longer trace from the verifier :

R0=inv(id=0,umax_value=4295032831,var_off=(0x0; 0x1ffffffff))
R1=inv(id=0,umax_value=65536,var_off=(0x0; 0x1ffff))
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=30,r=42,imm=0)
R10=fp0,call_-1 fp-48=pkt
239: (57) r0 &= 65535
240: (0f) r0 += r1
241: (bf) r1 = r0
242: (77) r1 >>= 16
243: (0f) r1 += r0
244: (a7) r1 ^= -1
245: (6b) *(u16 *)(r7 +24) = r1
246: (b7) r1 = 0
247: (6b) *(u16 *)(r7 +40) = r1
248: (b7) r1 = 0
249: (b7) r2 = 0
250: (79) r3 = *(u64 *)(r10 -48)
251: (b7) r4 = 4
252: (b7) r5 = 0
253: (85) call bpf_csum_diff#28
254: (67) r0 <<= 32
255: (c7) r0 s>>= 32
256: (b7) r1 = 0
257: (b7) r2 = 0
258: (bf) r3 = r9
259: (b7) r4 = 4
260: (bf) r5 = r0
261: (85) call bpf_csum_diff#28
262: (71) r1 = *(u8 *)(r7 +23)
263: (dc) r1 = be32 r1
264: (63) *(u32 *)(r10 -24) = r1
265: (67) r0 <<= 32
266: (c7) r0 s>>= 32
267: (bf) r9 = r10
268: (07) r9 += -24
269: (b7) r1 = 0
270: (b7) r2 = 0
271: (bf) r3 = r9
272: (b7) r4 = 4
273: (bf) r5 = r0
274: (85) call bpf_csum_diff#28
275: (79) r1 = *(u64 *)(r10 -40)
276: (dc) r1 = be32 r1
277: (63) *(u32 *)(r10 -24) = r1
278: (67) r0 <<= 32
279: (c7) r0 s>>= 32
280: (b7) r1 = 0
281: (b7) r2 = 0
282: (bf) r3 = r9
283: (b7) r4 = 4
284: (bf) r5 = r0
285: (85) call bpf_csum_diff#28
286: (67) r0 <<= 32
287: (c7) r0 s>>= 32
288: (b7) r1 = 0
289: (b7) r2 = 0
290: (bf) r3 = r8
291: (79) r4 = *(u64 *)(r10 -40)
292: (bf) r5 = r0
293: (85) call bpf_csum_diff#28

I reference the commit instead of repository to keep the link consistent over the time : https://github.com/sbernard31/udploadbalancer/tree/5ca93d0893a60bc70a75f30eb5cfde496a9e5d93

Again do not hesitate to redirect me to better place if I'm not asking at the right place :)

Thx again for your time.


Simon
 

Thx a lot again for your time and your detailed explanation.

About the workaround you proposed, I didn't get where I should repeat __u16 udp_len = bpf_ntohs(udp->len);.. I tried several spot but didn't succeed to make it works.
By the way repeat it, means probably shifting byte again ... so I pretty sure I didn't  get well what you mean :/ ... Did you succeed to make it works with this workaround ?

This is maybe a stupid question, but it seems to me that I'm not doing so exotic code here. I mean calculate a checksum with XDP and I fall in not so easy "issues". Is there something I do which is totally wrong or uncommon ?

I will take a look at SCALAR_VALUE issue later on.But if you or anybody has cycles and want to look into this issue,feel free to do so.
I didn't have enough skill to do that, I'm not even sure to understand what "spill/reload" means ?

Yonghong Song
 

On Mon, Mar 18, 2019 at 4:18 AM Simon <contact@...> wrote:

Thx a lot again for your time and your detailed explanation.

About the workaround you proposed, I didn't get where I should repeat __u16 udp_len = bpf_ntohs(udp->len);.. I tried several spot but didn't succeed to make it works.
This is a tough issue. I spent a couple of hours trying various source
workaround and did not succeed.
To illustrate my experiment, the following is what I tried to do to
move the code udp_len calculation and its usage closer to each other
to avoid register spill/refills.

```
-bash-4.4$ diff ulb.c ulb.c.org
61,62c61,62
< static inline int ipv4_l4_csum(struct udphdr *data_start, __u32 data_size,
< __u64 *csum, struct iphdr *iph, void
*data_end) {
---
static inline void ipv4_l4_csum(void *data_start, __u32 data_size,
__u64 *csum, struct iphdr *iph) {
70,87c70,71
<
< data_start = iph + 1;
< if (data_start + 1 > data_end)
< return XDP_DROP;
< data_size = bpf_ntohs(data_start->len);
< if (data_size < 8)
< return -1;
< if (data_size > 512)
< return -1;
< data_size = data_size & 0x1ff;
< data_start = (void *)data_start + data_size;
< if ((void *) data_start <= data_end) {
< *csum = bpf_csum_diff(0, 0, (void *)data_start - data_size,
data_size, *csum);
< *csum = csum_fold_helper(*csum);
< return 0;
< }
<
< return -1;
---
*csum = bpf_csum_diff(0, 0, data_start, data_size, *csum);
*csum = csum_fold_helper(*csum);140a125,132
__u16 udp_len = bpf_ntohs(udp->len);
if (udp_len < 8)
return XDP_DROP;
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;
200,203c192
< __u16 udp_len = 0;
< int ret = ipv4_l4_csum(udp, udp_len, &cs, iph, data_end) ;
< if (ret == -1)
< return XDP_DROP;
---
ipv4_l4_csum(udp, udp_len, &cs, iph) ;
-bash-4.4$
```

But my attempt above not working. The main reason is the compiler is
always trying to
use the original assignment register
data_start = iph + 1; /* data_start is in r8 */
/* r1 = r8, and below r1 is used for data_start */
if (data_start + 1 > data_end)
return XDP_DROP;
...
*csum = bpf_csum_diff(0, 0, (void *)data_start - data_size,
data_size, *csum); /* data_start in r8 */

The data_start is refined in r1 while r8 is used in the final argument passing.

I think I need to look at kernel verifier side and compiler side.

By the way repeat it, means probably shifting byte again ... so I pretty sure I didn't get well what you mean :/ ... Did you succeed to make it works with this workaround ?

This is maybe a stupid question, but it seems to me that I'm not doing so exotic code here. I mean calculate a checksum with XDP and I fall in not so easy "issues". Is there something I do which is totally wrong or uncommon ?
You are not. The compiler is doing optimization which make verifier
fail. It is possible an early compiler with less optimizations may
work.


I will take a look at SCALAR_VALUE issue later on.But if you or anybody has cycles and want to look into this issue,feel free to do so.

I didn't have enough skill to do that, I'm not even sure to understand what "spill/reload" means ?
Something like:
udp_len = ...
...
... = udp_len

The generated code:
store_to_stack for udp_len;
...
get udp_len value from stack
use udp_len

Simon
 

The compiler is doing optimization which make verifier fail. It is possible an early compiler with less optimizations may work.

Maybe a silly question, but does it make sense to try to change compiler optimization option ? (I tried  to play with -O option without success)

Please keep me informed about your progress about this issue :)

Thx again.

 

Yonghong Song
 

On Tue, Mar 19, 2019 at 9:06 AM Simon <contact@...> wrote:

The compiler is doing optimization which make verifier fail. It is possible an early compiler with less optimizations may work.

Maybe a silly question, but does it make sense to try to change compiler optimization option ? (I tried to play with -O option without success)
Maybe. I have not looked at this yet from compiler side. Sometimes you
won't have an easy compiler option to turn off. Tuning -O may not
help. Lowering -O to -O1/-O0 may help to remove this particular
optimization, but may introduce more spills which verifier will also
reject.


Please keep me informed about your progress about this issue :)
Sure. Will let you know if I have made progress in this.


Thx again.