inline ASM helpers for proving bounds checks

inline ASM helpers for proving bounds checks

[Barret Rhoden]

hi -

i was chatting with a few people off-list and mentioned that i wrote a 
couple helpers for ensuring ints are bounds-checked for things like 
array accesses.  i used inline asm to prevent the compiler from doing 
things like copying the register, checking the copy, and using the 
original for the indexing operation.

i'll paste them below.

if this is the sort of thing that would be nice in one of the helper 
header files, let me know where you'd like it and i can send a patch.

thanks,

barret


/*
  * Returns pointer to idx element in the array arr, made of
  * arr_sz number of elements:
  *
  *      if (!arr)
  *              return NULL;
  *      if (idx >= arr_sz)
  *              return NULL; 

  *      return &arr[idx];
  */
#define BOUNDED_ARRAY_IDX(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]"i"((arr_sz)),                 \
                                [__size]"i"(sizeof(typeof((arr)[0])))   \
                              : "cc");                                  \
         }                                                              \
         ___arr;                                                        \
})


/*
  * Forces the verifier to ensure idx is less than bound.  Returns 0 if
  * idx is not less than bound.
  */
static inline size_t bounded_idx(size_t idx, int bound)
{
         asm volatile("if %[__idx] < %[__bound] goto 1f; \
                       %[__idx] = 0;                     \
                       1:"
                       : [__idx]"+r"(idx) : [__bound]"i"(bound) : "cc");
         return idx;
}

this one is a little simpler, but also more dangerous.  if the int isn't 
actually bounded, it'll set it to 0, which might not be what you want 
since you can't tell the difference between "out of bounds" and 
"actually 0".  i use this in a place where i know the int is bounded 
(barring other horrendous bugs) and can't check.

Re: inline ASM helpers for proving bounds checks

[Andrii Nakryiko]

On Sat, Mar 25, 2023 at 9:08 AM Barret Rhoden <brho@google.com> wrote:
>
> hi -
>
> i was chatting with a few people off-list and mentioned that i wrote a
> couple helpers for ensuring ints are bounds-checked for things like
> array accesses.  i used inline asm to prevent the compiler from doing
> things like copying the register, checking the copy, and using the
> original for the indexing operation.
>
> i'll paste them below.
>
> if this is the sort of thing that would be nice in one of the helper
> header files, let me know where you'd like it and i can send a patch.
>
> thanks,
>
> barret
>
>
> /*
>   * Returns pointer to idx element in the array arr, made of
>   * arr_sz number of elements:
>   *
>   *      if (!arr)
>   *              return NULL;
>   *      if (idx >= arr_sz)
>   *              return NULL;
>
>   *      return &arr[idx];
>   */
> #define BOUNDED_ARRAY_IDX(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]"i"((arr_sz)),                 \
>                                 [__size]"i"(sizeof(typeof((arr)[0])))   \
>                               : "cc");                                  \
>          }                                                              \
>          ___arr;                                                        \
> })
>

Hey, Barret!

This one looks pretty useful and common (especially to work around
Clang's smartness). I have related set of helpers waiting it's time,
see [0]. I'd say we should think about some good naming of them,
document them properly (including various gotchas), and include them
(initially) in bpf_misc.h and start using them in selftests. This way
we'll have upstream header to point to for eager users, we'll
test-drive their usefulness in selftests, and when we feel confident
they are generally useful and safe, we'll move them into libbpf's
bpf_helpers.h.


  [0] https://github.com/anakryiko/linux/commit/feef5205c05b282d4a6c73a0222474a805907864


>
> /*
>   * Forces the verifier to ensure idx is less than bound.  Returns 0 if
>   * idx is not less than bound.
>   */
> static inline size_t bounded_idx(size_t idx, int bound)
> {
>          asm volatile("if %[__idx] < %[__bound] goto 1f; \
>                        %[__idx] = 0;                     \
>                        1:"
>                        : [__idx]"+r"(idx) : [__bound]"i"(bound) : "cc");
>          return idx;
> }
>
> this one is a little simpler, but also more dangerous.  if the int isn't

yeah, I'm hesitant about this one. It is very similar to
bpf_clam_xxx() macros I referenced above, probably we should use those
instead.

> actually bounded, it'll set it to 0, which might not be what you want
> since you can't tell the difference between "out of bounds" and
> "actually 0".  i use this in a place where i know the int is bounded
> (barring other horrendous bugs) and can't check.
>
>

Re: inline ASM helpers for proving bounds checks

[Barret Rhoden]

On 3/28/23 17:32, Andrii Nakryiko wrote:
> This one looks pretty useful and common (especially to work around
> Clang's smartness). I have related set of helpers waiting it's time,
> see [0]. I'd say we should think about some good naming of them,
> document them properly (including various gotchas), and include them
> (initially) in bpf_misc.h and start using them in selftests. 

sounds good to me.

any preference for a name?  bpf_index_array()?
- no need to say "bounded".
- want to begin with bpf_.
- sticking with your clamp style, "index" would be the verb.  (instead 
of e.g. bpf_array_index, which sounds like it has something to do with a 
BPF array".

i'm up for anything though.  =)

> yeah, I'm hesitant about this one. It is very similar to
> bpf_clam_xxx() macros I referenced above, probably we should use those
> instead.

totally agree.  i can switch my stuff to use the clamp, which covers all 
of the use cases/signedness.  btw, good to know the "s<" is 
signed-less-than.  i imagine i'd have had trouble with that.  =)

thanks,

barret

Re: inline ASM helpers for proving bounds checks

[Andrii Nakryiko]

On Mon, Apr 10, 2023 at 10:46 AM Barret Rhoden <brho@google.com> wrote:
>
> On 3/28/23 17:32, Andrii Nakryiko wrote:
> > This one looks pretty useful and common (especially to work around
> > Clang's smartness). I have related set of helpers waiting it's time,
> > see [0]. I'd say we should think about some good naming of them,
> > document them properly (including various gotchas), and include them
> > (initially) in bpf_misc.h and start using them in selftests.
>
> sounds good to me.
>
> any preference for a name?  bpf_index_array()?
> - no need to say "bounded".
> - want to begin with bpf_.
> - sticking with your clamp style, "index" would be the verb.  (instead
> of e.g. bpf_array_index, which sounds like it has something to do with a
> BPF array".
>
> i'm up for anything though.  =)

bpf_index_array()/bpf_access_array() might be ok. But perhaps a bit
more natural in the code will be bpf_array_elem(), as it's actually an
accessor/expression, not really a stand-alone statement:

struct my_elem *elem = bpf_array_elem(arr, n);
if (!elem)
    return 0;
elem->field = <blah>;

WDYT?

Let's also maybe improve usability by inferring array size? I've seen
somewhere in kernel code a macro that validates that passed in arr is
actually an array (and not a pointer), it would be useful to use
similar approach here to make sure we determine size correctly. See
what ARRAY_SIZE() in the kernel does.

>
> > yeah, I'm hesitant about this one. It is very similar to
> > bpf_clam_xxx() macros I referenced above, probably we should use those
> > instead.
>
> totally agree.  i can switch my stuff to use the clamp, which covers all
> of the use cases/signedness.  btw, good to know the "s<" is
> signed-less-than.  i imagine i'd have had trouble with that.  =)

you are welcome :)

>
> thanks,
>
> barret
>
>