How to solve the "R2 invalid mem access 'inv'" error when i try to loading the ebpf file named bpf_cubic.c

Question

The linux kernel source code version is 5.11.0

I tried to load the congestion control algorithm which is implemented by eBPF.
The file is linux-source-5.11.0\tools\testing\selftests\bpf\progs\bpf_cubic.c.
I used the libbpf-bootstrap so I made some changes of the code, but I don't think that's the problem, because I didn't change the part that went wrong. My change mainly focus on the user state code. The kernel state code is almost unchanged, except for the previous compilation error：

/* No prefix in SEC will also work.
 * The remaining tcp-cubic functions have an easier way.
 */
/*
* 
* changes:
*         comment out this sentence://SEC("no-sec-prefix-bictcp_cwnd_event")
*         add the code SEC("struct_ops/bictcp_cwnd_event")
*/
//SEC("no-sec-prefix-bictcp_cwnd_event")
SEC("struct_ops/bictcp_cwnd_event")
void BPF_PROG(bictcp_cwnd_event, struct sock *sk, enum tcp_ca_event event)
{
    if (event == CA_EVENT_TX_START) {
        struct bictcp *ca = inet_csk_ca(sk);
        __u32 now = tcp_jiffies32;
        __s32 delta;

        delta = now - tcp_sk(sk)->lsndtime;

        /* We were application limited (idle) for a while.
         * Shift epoch_start to keep cwnd growth to cubic curve.
         */
        if (ca->epoch_start && delta > 0) {
            ca->epoch_start += delta;
            if (after(ca->epoch_start, now))
                ca->epoch_start = now;
        }
        return;
    }
}

When I load this file, the compilation is successful, but an error is reported when loading. The error is：

R0=inv(id=26,umin_value=1152921504606846976,umax_value=11517967026549683715) 
R1_rw=invP(id=26,umin_value=1152921504606846976,umax_value=11517967026549683715) R2_r=inv0             
R3=invP(id=26,umin_value=1152921504606846976,umax_value=11517967026549683715) 
R4_w=inv1152921504606846976 R5_rw=invP63 R6_r=ptr_tcp_sock(id=0,off=0,imm=0) R7_r=inv(id=2) 
R8_r=ptr_tcp_sock(id=0,off=1296,imm=0) R9_r=inv(id=8,umax_value=4294967295,var_off=(0x0;0xffffffff)) R10=fp0 fp-8_r=inv
parent already had regs=2a stack=0 marks
; x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6;
232: (18) r2 = 0xffffa7ee80066000
234: (0f) r2 += r1
235: (71) r5 = *(u8 *)(r2 +0)
R2 invalid mem access 'inv'
processed 544 insns (limit 1000000) max_states_per_insn 2 total_states 30 peak_states 30 mark_read 10
-- END PROG LOAD LOG --
libbpf: failed to load program 'bictcp_cong_avoid'
libbpf: failed to load object 'bpf_cubic_bpf'
libbpf: failed to load BPF skeleton 'bpf_cubic_bpf': -13
Failed to load and verify BPF skeleton

I find the wrong code is x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6; in the function static __always_inline __u32 cubic_root(__u64 a)
If I comment out this sentence or replace shift with a number, I could load the project.
I tried to add some scope validation, but it still can't be loaded.

    if (shift >= 64){
        return 0;
    }else{
        x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6;

        /*
        * Newton-Raphson iteration
        *                         2
        * x    = ( 2 * x  +  a / x  ) / 3
        *  k+1          k         k
        */
        x = (2 * x + (__u32)div64_u64(a, (__u64)x * (__u64)(x - 1)));
        x = ((x * 341) >> 10);
    }
 

the whole code of the function is

/*
 * cbrt(x) MSB values for x MSB values in [0..63].
 * Precomputed then refined by hand - Willy Tarreau
 *
 * For x in [0..63],
 *   v = cbrt(x << 18) - 1
 *   cbrt(x) = (v[x] + 10) >> 6
 */
static const __u8 v[] = {
/* 0x00 */    0,   54,   54,   54,  118,  118,  118,  118,
/* 0x08 */  123,  129,  134,  138,  143,  147,  151,  156,
/* 0x10 */  157,  161,  164,  168,  170,  173,  176,  179,
/* 0x18 */  181,  185,  187,  190,  192,  194,  197,  199,
/* 0x20 */  200,  202,  204,  206,  209,  211,  213,  215,
/* 0x28 */  217,  219,  221,  222,  224,  225,  227,  229,
/* 0x30 */  231,  232,  234,  236,  237,  239,  240,  242,
/* 0x38 */  244,  245,  246,  248,  250,  251,  252,  254,
};

/* calculate the cubic root of x using a table lookup followed by one
 * Newton-Raphson iteration.
 * Avg err ~= 0.195%
 */
static __always_inline __u32 cubic_root(__u64 a)
{
    __u32 x=0, b, shift;

    if (a < 64) {
        /* a in [0..63] */
        return ((__u32)v[(__u32)a] + 35) >> 6;
    }

    b = fls64(a);
    b = ((b * 84) >> 8) - 1;
    shift = (a >> (b * 3));

    /* it is needed for verifier's bound check on v */
    if (shift >= 64){
        return 0;
    }else{
        x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6;

        /*
        * Newton-Raphson iteration
        *                         2
        * x    = ( 2 * x  +  a / x  ) / 3
        *  k+1          k         k
        */
        x = (2 * x + (__u32)div64_u64(a, (__u64)x * (__u64)(x - 1)));
        x = ((x * 341) >> 10);
    }
    return x;
}

Answer 1

Thank you for all the answers.

A friend of mine told me that I should verify it by:

if(v[shift]){
...
}

He told me that I should judge whether the corresponding position of the array exists, rather than directly judge the size of the "shift".
I modified it like this, and the program did pass the verification.