Packet pointers with 32-bit assignments

Packet pointers with 32-bit assignments

[Paul Chaignon]

Hi,

We're hitting the following verifier error in Cilium, on bpf-next
(86c7ecad3bf8) with LLVM 10.0.0 and mcpu=v3.

    ; return (void *)(unsigned long)ctx->data;
    2: (61) r9 = *(u32 *)(r7 +76)
    ; R7_w=ctx(id=0,off=0,imm=0) R9_w=pkt(id=0,off=0,r=0,imm=0)
    ; return (void *)(unsigned long)ctx->data;
    3: (bc) w6 = w9
    ; R6_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R9_w=pkt(id=0,off=0,r=0,imm=0)
    ; if (data + tot_len > data_end)
    4: (bf) r2 = r6
    ; R2_w=inv(id=1,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R6_w=inv(id=1,umax_value=4294967295,var_off=(0x0; 0xffffffff))
    5: (07) r2 += 54
    ; R2_w=inv(id=0,umin_value=54,umax_value=4294967349,var_off=(0x0; 0x1ffffffff))
    ; if (data + tot_len > data_end)
    6: (2d) if r2 > r1 goto pc+466
    ; R1_w=pkt_end(id=0,off=0,imm=0) R2_w=inv(id=0,umin_value=54,umax_value=4294967349,var_off=(0x0; 0x1ffffffff))
    ; tmp = a->d1 - b->d1;
    7: (71) r2 = *(u8 *)(r6 +22)
    R6 invalid mem access 'inv'

As seen above, the verifier loses track of the packet pointer at
instruction 3, which then leads to an invalid memory access. Since
ctx->data is on 32 bits, LLVM generated a 32-bit assignment at
instruction 3.

We're usually able to avoid this by removing all 32-bit comparisons and
additions with the 64-bit variables for data and data_end. But in this
case, all variables are already on 64 bits.

Is there maybe a compiler patch we're missing which prevents such
assignments? If not, could we teach the verifier to track and convert
such assignments?

Regards,
Paul

Re: Packet pointers with 32-bit assignments

[Yonghong Song]

On 2/2/22 12:59 PM, Paul Chaignon wrote:
> Hi,
> 
> We're hitting the following verifier error in Cilium, on bpf-next
> (86c7ecad3bf8) with LLVM 10.0.0 and mcpu=v3.
> 
>      ; return (void *)(unsigned long)ctx->data;
>      2: (61) r9 = *(u32 *)(r7 +76)
>      ; R7_w=ctx(id=0,off=0,imm=0) R9_w=pkt(id=0,off=0,r=0,imm=0)
>      ; return (void *)(unsigned long)ctx->data;
>      3: (bc) w6 = w9
>      ; R6_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R9_w=pkt(id=0,off=0,r=0,imm=0)
>      ; if (data + tot_len > data_end)
>      4: (bf) r2 = r6
>      ; R2_w=inv(id=1,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R6_w=inv(id=1,umax_value=4294967295,var_off=(0x0; 0xffffffff))
>      5: (07) r2 += 54
>      ; R2_w=inv(id=0,umin_value=54,umax_value=4294967349,var_off=(0x0; 0x1ffffffff))
>      ; if (data + tot_len > data_end)
>      6: (2d) if r2 > r1 goto pc+466
>      ; R1_w=pkt_end(id=0,off=0,imm=0) R2_w=inv(id=0,umin_value=54,umax_value=4294967349,var_off=(0x0; 0x1ffffffff))
>      ; tmp = a->d1 - b->d1;
>      7: (71) r2 = *(u8 *)(r6 +22)
>      R6 invalid mem access 'inv'
> 
> As seen above, the verifier loses track of the packet pointer at
> instruction 3, which then leads to an invalid memory access. Since
> ctx->data is on 32 bits, LLVM generated a 32-bit assignment at
> instruction 3.
> 
> We're usually able to avoid this by removing all 32-bit comparisons and
> additions with the 64-bit variables for data and data_end. But in this
> case, all variables are already on 64 bits.
> 
> Is there maybe a compiler patch we're missing which prevents such
> assignments? If not, could we teach the verifier to track and convert
> such assignments?

We kind of tackled this problem sometimes back. For example, the
following is a proposed llvm builtin for this purpose:
   https://reviews.llvm.org/D81479
   https://reviews.llvm.org/D81480
the builtin looks like
   void *ptr = __builtin_bpf_load_u32_to_ptr(void *base,
                   int const_offset);

The patches are abandoned since the functionality can be
achieved with bpf asm code. Something likes below
    asm("%0 = *(u32 *)(%1 + %2)" : "=r"(ptr) : "r"(ctx), "i"(76));
We could define the above asm insn as a macro and put it
in bpf_helpers.h.

Could you give a try?

> 
> Regards,
> Paul

Re: Packet pointers with 32-bit assignments

[Paul Chaignon]

On Wed, Feb 02, 2022 at 07:24:20PM -0800, Yonghong Song wrote:
> 
> 
> On 2/2/22 12:59 PM, Paul Chaignon wrote:
> > Hi,
> > 
> > We're hitting the following verifier error in Cilium, on bpf-next
> > (86c7ecad3bf8) with LLVM 10.0.0 and mcpu=v3.
> > 
> >      ; return (void *)(unsigned long)ctx->data;
> >      2: (61) r9 = *(u32 *)(r7 +76)
> >      ; R7_w=ctx(id=0,off=0,imm=0) R9_w=pkt(id=0,off=0,r=0,imm=0)
> >      ; return (void *)(unsigned long)ctx->data;
> >      3: (bc) w6 = w9
> >      ; R6_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R9_w=pkt(id=0,off=0,r=0,imm=0)
> >      ; if (data + tot_len > data_end)
> >      4: (bf) r2 = r6
> >      ; R2_w=inv(id=1,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R6_w=inv(id=1,umax_value=4294967295,var_off=(0x0; 0xffffffff))
> >      5: (07) r2 += 54
> >      ; R2_w=inv(id=0,umin_value=54,umax_value=4294967349,var_off=(0x0; 0x1ffffffff))
> >      ; if (data + tot_len > data_end)
> >      6: (2d) if r2 > r1 goto pc+466
> >      ; R1_w=pkt_end(id=0,off=0,imm=0) R2_w=inv(id=0,umin_value=54,umax_value=4294967349,var_off=(0x0; 0x1ffffffff))
> >      ; tmp = a->d1 - b->d1;
> >      7: (71) r2 = *(u8 *)(r6 +22)
> >      R6 invalid mem access 'inv'
> > 
> > As seen above, the verifier loses track of the packet pointer at
> > instruction 3, which then leads to an invalid memory access. Since
> > ctx->data is on 32 bits, LLVM generated a 32-bit assignment at
> > instruction 3.
> > 
> > We're usually able to avoid this by removing all 32-bit comparisons and
> > additions with the 64-bit variables for data and data_end. But in this
> > case, all variables are already on 64 bits.
> > 
> > Is there maybe a compiler patch we're missing which prevents such
> > assignments? If not, could we teach the verifier to track and convert
> > such assignments?
> 
> We kind of tackled this problem sometimes back. For example, the
> following is a proposed llvm builtin for this purpose:
>   https://reviews.llvm.org/D81479
>   https://reviews.llvm.org/D81480
> the builtin looks like
>   void *ptr = __builtin_bpf_load_u32_to_ptr(void *base,
>                   int const_offset);
> 
> The patches are abandoned since the functionality can be
> achieved with bpf asm code. Something likes below
>    asm("%0 = *(u32 *)(%1 + %2)" : "=r"(ptr) : "r"(ctx), "i"(76));
> We could define the above asm insn as a macro and put it
> in bpf_helpers.h.
> 
> Could you give a try?

It works fine! One more piece of asm bytecode in Cilium but who's
counting at this point :))

Thanks Yonghong!

> 
> > 
> > Regards,
> > Paul