Skip to contentSkip to conversation

inline ASM helpers for proving bounds checks

DISCUSSION Barret Rhoden 2 participants 4 messages Mar 25, 2023 – Apr 12, 2023 BPF

lore
Share & tools
lore
#0 lore raw

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.

#1 lore raw
Quoted 41 lines · 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:                                \
Quoted 9 lines
                               "                                 \
                              : [__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

Quoted 14 lines

/*
* 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;
}
Quoted 1 line

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.

Quoted 6 lines

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.

#2 lore raw
Quoted 5 lines · Andrii Nakryiko

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. =)

Quoted 3 lines

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

#3 lore raw
Quoted 10 lines · Barret Rhoden
Quoted 5 lines · Andrii Nakryiko

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.

Quoted 8 lines

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.

Quoted 8 lines
Quoted 4 lines

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 :)

Quoted 6 lines

thanks,

barret