Re: [PATCH v2 bpf-next 2/2] selftests/bpf: add inline assembly helpers to access array elements

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

 



On Thu, Jan 4, 2024 at 1:30 PM Barret Rhoden <brho@xxxxxxxxxx> wrote:
>
> On 1/4/24 12:31, Yonghong Song wrote:
> [snip]
>
> >>> +/*
> >>> + * Access an array element within a bound, such that the verifier
> >>> knows the
> >>> + * access is safe.
> >>> + *
> >>> + * This macro asm is the equivalent of:
> >>> + *
> >>> + *    if (!arr)
> >>> + *        return NULL;
> >>> + *    if (idx >= arr_sz)
> >>> + *        return NULL;
> >>> + *    return &arr[idx];
> >>> + *
> >>> + * The index (___idx below) needs to be a u64, at least for certain
> >>> versions of
> >>> + * the BPF ISA, since there aren't u32 conditional jumps.
> >>> + */
> >>> +#define bpf_array_elem(arr, arr_sz, idx) ({                \
> >>> +    typeof(&(arr)[0]) ___arr = arr;                    \
> >>> +    __u64 ___idx = idx;                        \
> >>> +    if (___arr) {                            \
> >>> +        asm volatile("if %[__idx] >= %[__bound] goto 1f;    \
> >>> +                  %[__idx] *= %[__size];        \
> >>> +                  %[__arr] += %[__idx];        \
> >>> +                  goto 2f;                \
> >>> +                  1:;                \
> >>> +                  %[__arr] = 0;            \
> >>> +                  2:                \
> >>> +                  "                        \
> >>> +                 : [__arr]"+r"(___arr), [__idx]"+r"(___idx)    \
> >>> +                 : [__bound]"r"((arr_sz)),                \
> >>> +                   [__size]"i"(sizeof(typeof((arr)[0])))    \
> >>> +                 : "cc");                    \
> >>> +    }                                \
> >>> +    ___arr;                                \
> >>> +})
> >
> > The LLVM bpf backend has made some improvement to handle the case like
> >    r1 = ...
> >    r2 = r1 + 1
> >    if (r2 < num) ...
> >    using r1
> > by preventing generating the above code pattern.
> >
> > The implementation is a pattern matching style so surely it won't be
> > able to cover all cases.
> >
> > Do you have specific examples which has verification failure due to
> > false array out of bound access?
>
> Not in a small example.  =(
>
> This bug has an example, but it was part of a larger program:
> https://github.com/google/ghost-userspace/issues/31
>
> The rough progression was:
> - sometimes the compiler optimizes out the checks.  So we added a macro
> to make the compiler not know the value of the variable anymore.
> - then, the compiler would occasionally do the check on a copy of the
> register, so we did the comparison and index operation all in assembly.
>
>
> I tried using bpf_cmp_likely() in my actual program (not just a one-off
> test), and still had a verifier issue.  It's a large and convoluted
> program, so it might be hard to get a small reproducer.  But it a
> different compiler issue than the one you mentioned.
>
> Specifically, I swapped out my array-access-macro for this one, using
> bpf_cmp_likely():
>
> #define bpf_array_elem(arr, arr_sz, idx) ({ \
>          typeof(&(arr)[0]) ___arr = arr;        \
>          typeof(&(arr)[0]) ___ret = 0;          \
>          u64 ___idx = idx;                      \
>          if (___arr && bpf_cmp_likely(___idx, <, arr_sz))   \
>                  ___ret = &___arr[___idx];\
>          ___ret;                          \
> })
>
> which should be the same logic as before:
>
>   *      if (!arr)
>   *              return NULL;
>   *      if (idx >= arr_sz)
>   *              return NULL;
>   *      return &arr[idx];
>
> The issue I run into is different than the one you had.  The compiler
> did the bounds check, but then for some reason recreated the index.  The
> index is coming from another map.
>
> Arguably, the verifier is doing its job - that value could have changed.
>   I just don't want the compiler to do the reread or any other
> shenanigans in between the bounds check and the usage.
>
> The guts of the error:
> - r0 is the map (L127)
> - r1 is the index, read from another map (L128)
> - r1 gets verified to be less than 0x200 (L129)
> - some other stuff happens
> - r1 gets read again, and is no longer bound (L132)
> - r1 gets scaled up by 896.
>    (896*0x200 = 0x70000, would be the real bound, but r1 lost the 0x200
> bound)
> - r0 indexed by the bad r1 (L134)
> - blow up (L143)
>
> 127: (15) if r0 == 0x0 goto pc+1218   ;
> R0=map_value(off=0,ks=4,vs=458752,imm=0)
>
> 128: (79) r1 = *(u64 *)(r10 -40)      ;
> R1_w=Pscalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0
>
> 129: (35) if r1 >= 0x200 goto pc+1216         ;
> R1_w=Pscalar(umax=511,var_off=(0x0; 0x1ff))
>
> 130: (79) r4 = *(u64 *)(r10 -56)      ; R4_w=Pscalar() R10=fp0;
>
> 131: (37) r4 /= 1000                  ; R4_w=Pscalar()
>
> 132: (79) r1 = *(u64 *)(r10 -40)      ;
> R1_w=Pscalar(umax=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0;
>
> 133: (27) r1 *= 896                   ;
> R1_w=Pscalar(umax=3848290696320,var_off=(0x0;
> 0x3ffffffff80),s32_max=2147483520,u32_max=-128)
>
> 134: (0f) r0 += r1                    ;
> R0_w=map_value(off=0,ks=4,vs=458752,umax=3848290696320,var_off=(0x0;
> 0x3ffffffff80),s32_max=2147483520,u32_max=-128)
> R1_w=Pscalar(umax=3848290696320,var_off=(0x0;
> 0x3ffffffff80),s32_max=2147483520,u32_max=-128)
>
> 135: (79) r3 = *(u64 *)(r10 -48)      ;
> R3_w=map_value(off=0,ks=4,vs=15728640,imm=0) R10=fp0;
>
> 136: (0f) r3 += r8                    ;
> R3_w=map_value(off=0,ks=4,vs=15728640,umax=15728400,var_off=(0x0;
> 0xfffff0),s32_max=16777200,u32_max=16777200)
> R8=Pscalar(umax=15728400,var_off=(0x0; 0xfffff0))
>
> 137: (61) r1 = *(u32 *)(r7 +16)       ;
> R1_w=Pscalar(umax=4294967295,var_off=(0x0; 0xffffffff))
> R7=map_value(id=18779,off=0,ks=4,vs=224,imm=0)
>
> 138: (79) r2 = *(u64 *)(r3 +88)       ; R2=Pscalar()
> R3=map_value(off=0,ks=4,vs=15728640,umax=15728400,var_off=(0x0;
> 0xfffff0),s32_max=16777200,u32_max=16777200)
>
> 139: (a5) if r1 < 0x9 goto pc+1       ;
> R1=Pscalar(umin=9,umax=4294967295,var_off=(0x0; 0xffffffff))
>
> 140: (b7) r1 = 0                      ; R1_w=P0
>
> 141: (27) r1 *= 72                    ; R1_w=P0
>
> 142: (0f) r0 += r1                    ;
> R0_w=map_value(off=0,ks=4,vs=458752,umax=3848290696320,var_off=(0x0;
> 0x3ffffffff80),s32_max=2147483520,u32_max=-128) R1_w=P0
>
> 143: (7b) *(u64 *)(r0 +152) = r2
>
>
> if i put in a little ASM magic to tell the compiler to not recreate the
> index, it works, like so:
>
> #define BPF_MUST_CHECK(x) ({ asm volatile ("" : "+r"(x)); x; })
>
> #define bpf_array_elem(arr, arr_sz, idx) ({ \
>          typeof(&(arr)[0]) ___arr = arr;        \
>          typeof(&(arr)[0]) ___ret = 0;          \
>          u64 ___idx = idx;                      \
>          BPF_MUST_CHECK(___idx);                \
>         if (___arr && bpf_cmp_likely(___idx, <, arr_sz))   \
>                  ___ret = &___arr[___idx];\
>          ___ret;                          \
> })
>
> though anecdotally, that only stops the "reread the index from its map"
> problem, similar to a READ_ONCE.  the compiler is still free to just use
> another register for the check.
>
> The bit of ASM i had from a while back that did that was:
>
>   *      r2 = r8
>   *      r2 <<= 32
>
>   *      r2 >>= 32
>   *      if r2 > 0x3ff goto pc+29
>
>   *      r8 <<= 32
>
>   *      r8 >>= 32
>
>   *      r8 <<= 6
>
>   *      r0 += r8
>   *      *(u64 *)(r0 +48) = r3
>
>
> where r2 was bounds checked, but r8 was used instead.
>
> I'll play around and see if I can come up with a selftest that can run
> into any of these "you did the check, but threw the check away" scenarios.

Before we add full asm bpf_array_elem() macros let's fully
understand the issue first. Maybe it's a llvm deficiency
or verifier miss that can be addressed.
asm everywhere isn't a viable approach long term.

First start with:
asm volatile ("" : "+r"((short)x));

It will avoid unnecessary <<=32, >>=32 in -mcpu=v3,v4.

Then do:
if (likely(___arr) && bpf_cmp_likely(___idx, <, arr_sz))
    ^^^
just to have the expected basic block layout,
because that's what your asm does.

And, of course, a selftest is necessary to debug this further.





[Index of Archives]     [Linux Samsung SoC]     [Linux Rockchip SoC]     [Linux Actions SoC]     [Linux for Synopsys ARC Processors]     [Linux NFS]     [Linux NILFS]     [Linux USB Devel]     [Video for Linux]     [Linux Audio Users]     [Yosemite News]     [Linux Kernel]     [Linux SCSI]


  Powered by Linux