LLVM optimized code triggers error in verifier

[maxdml]

I have a piece of C code where BPF_HASH members are structs with array members:

struct datapoints {
    u16 n_points;
    u16 pad[2];
    long points[MAX_POINTS];
    u64 ts[MAX_POINTS];
}

BPF_HASH(datapoints_m, int, struct datapoints, MAX_REQS);

....
long min_dist = 15; 
struct datapoints *pts = datapoints_m.lookup(&req_id);
if (pts) {
    pts->points[pts->n_points] = min_dist;
...

Accessing the array member triggers a verifier error:

65: (85) call bpf_map_lookup_elem#1
66: (15) if r0 == 0x0 goto pc+5
 R0=map_value(id=0,off=0,ks=4,vs=136,imm=0) R6=inv(id=0) R7=inv(id=0) R10=fp0
67: (69) r1 = *(u16 *)(r0 +0)
 R0=map_value(id=0,off=0,ks=4,vs=136,imm=0) R6=inv(id=0) R7=inv(id=0) R10=fp0
68: (67) r1 <<= 3
69: (0f) r0 += r1
70: (b7) r1 = 15
71: (7b) *(u64 *)(r0 +8) = r1
 R0=map_value(id=0,off=0,ks=4,vs=136,umax_value=524280,var_off=(0x0; 0x7fff8)) R1=inv15 R6=inv(id=0) R7=inv(id=0) R10=fp0
invalid access to map value, value_size=136 off=524288 size=8
R0 max value is outside of the array range

This seems related to #235 or https://patchwork.codeaurora.org/patch/507977/: some optimization mess up the register r1 given as argument to the call. The offset value becomes the maximum value that r1<<=3 (which was originally a u16) can take, which is much larger than the value size of the BPF_HASH entries (136 here).

Playing around with different ways to set the element results in the same generated code, e.g.:

if (pts) {
    long *points = pts->points;
    u16 n_points = pts->n_points;
    *(points + n_points) = min_dist;
}

Am I missing something obvious here? Or is it indeed some conflict between LLVM optimizations and the BPF verifier?

[yonghong-song]

The verifier seems doing the right thing. The issue, the compiler does not ptr->n_points value, so it will have a range [0, 0xffff] , after the above insn 68, r1 range [0, 0x7fff8], which probably large than even map value size.

One possible way is to check ptr->n_points comparing to MAX_POINTS under which you do the rest of operations. Hopefully, verifier pruning functionality can kick in to permit the write.

[maxdml]

Ho, I see. Actually I saw the trick in https://patchwork.ozlabs.org/patch/664153/ but I did not pick it up.
I works by doing this check against MAX_POINTS. However, there is one more thing that I had to do:

if you code it as follow

struct datapoints *pts = datapoints_m.lookup(&req_id);
if (pts) {
    u16 index = 0;
    if (pts->n_points >= MAX_POINTS) {
        pts->n_points = index;
     } else {
         index = pts->n_points++;
    }
    pts->points[index] = some_value;
     ...

Then you will get an error because, if I understand well, we fall into this condition from the BPF doc :

Program that correctly checks map_lookup_elem() returned value for NULL and
accesses memory with correct alignment in one side of 'if' branch, but fails
to do so in the other side of 'if' branch

from 115 to 118: R0=map_value(id=0,off=0,ks=4,vs=136,imm=0) R1=inv0 R2=inv(id=0,umin_value=8,umax_value=65535,var_off=(0x0; 0xffff)) R3=inv0 R4=inv7 R6=inv(id=0) R7=inv(id=0) R10=fp0
118: (2d) if r2 > r4 goto pc+1
 R0=map_value(id=0,off=0,ks=4,vs=136,imm=0) R1=inv0 R2=inv(id=0,umin_value=8,umax_value=7,var_off=(0x0; 0xf)) R3=inv0 R4=inv7 R6=inv(id=0) R7=inv(id=0) R10=fp0
119: (bf) r1 = r2
120: (6b) *(u16 *)(r0 +128) = r3
 R0=map_value(id=0,off=0,ks=4,vs=136,imm=0) R1=inv(id=0,umin_value=8,umax_value=7,var_off=(0x0; 0xf)) R2=inv(id=0,umin_value=8,umax_value=7,var_off=(0x0; 0xf)) R3=inv0 R4=inv7 R6=inv(id=0) R7=inv(id=0) R10=fp0
121: (67) r1 <<= 3
122: (0f) r0 += r1
123: (b7) r1 = 15
124: (7b) *(u64 *)(r0 +0) = r1
R0 invalid mem access 'inv'

I got around this by separating getting the value from the struct and incrementing the struct member itself later

struct datapoints *pts = datapoints_m.lookup(&req_id);
if (pts) {
    u16 index = 0;
    if (pts->n_points >= MAX_POINTS) {
        pts->n_points = index;
     } else {
         index = pts->n_points;
    }
    pts->points[index] = some_value;
    pts->n_points++;
     ...