Re: [PATCH 1/2] overflow: Implement size_t saturating arithmetic helpers

[Nick Desaulniers <ndesaulniers@google.com>]

On Mon, Sep 20, 2021 at 11:09 AM Kees Cook <keescook@chromium.org> wrote:
>
> In order to perform more open-coded replacements of common allocation
> size arithmetic, the kernel needs a saturating (SIZE_MAX) helper for
> addition and multiplication. It is common in allocators, especially on
> realloc, to add to an existing size. For example:
>
>         p = krealloc(map->patch,
>                      sizeof(struct reg_sequence) * (map->patch_regs + num_regs),
>                      GFP_KERNEL);
>
> There is no existing saturating replacement for this calculation, and
> just leaving the addition open coded inside array_size() could
> potentially overflow as well. For example, an overflow in an expression
> for a size_t argument might wrap to zero:
>
>         array_size(anything, something_at_size_max + 1) == 0
>
> Introduce size_mul() and size_add() helpers to perform size_t promotion
> and saturated calculations for use in such allocations. With these
> helpers it is also possible to redefine array_size(), array3_size(),
> flex_array_size(), and struct_size() in terms of the new helpers.
>
> As with the check_*_overflow() helpers, the helpers are wrapped in a
> __must_check function that passes through the size_t result. In order
> for the helpers to be composed with themselves, they must have unique
> variable names to avoid shadowing, so this uses a similar method to what
> is already done in minmax.h for constructing unique names to be passed
> in as arguments to the statement expression that does the actual work.
>
> Cc: Rasmus Villemoes <linux@rasmusvillemoes.dk>
> Cc: Gustavo A. R. Silva <gustavoars@kernel.org>
> Cc: Nathan Chancellor <nathan@kernel.org>
> Cc: Jason Gunthorpe <jgg@ziepe.ca>
> Cc: Nick Desaulniers <ndesaulniers@google.com>
> Cc: Leon Romanovsky <leon@kernel.org>
> Cc: Keith Busch <kbusch@kernel.org>
> Cc: Len Baker <len.baker@gmx.com>
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
>  include/linux/overflow.h | 140 ++++++++++++++++++++++++---------------
>  lib/test_overflow.c      |  61 +++++++++++++++++
>  2 files changed, 149 insertions(+), 52 deletions(-)
>
> diff --git a/include/linux/overflow.h b/include/linux/overflow.h
> index 4669632bd72b..cd154d47807c 100644
> --- a/include/linux/overflow.h
> +++ b/include/linux/overflow.h
> @@ -117,6 +117,77 @@ static inline bool __must_check __must_check_overflow(bool overflow)
>         (*_d >> _to_shift) != _a);                                      \
>  }))
>
> +/*
> + * As with __must_check_overflow() above, this is used to wrap the
> + * size_t output from a statement expression macro.
> + */
> +static inline size_t __must_check __must_check_size(size_t size)
> +{
> +       return size;
> +}
> +
> +/*
> + * Internal logic for size_mul(). Takes variable names from UNIQUE_ID
> + * so that the local variables here will never collide with other local
> + * variables (for example, with itself).
> + */
> +#define __size_mul(factor1, factor2, __factor1, __factor2, __product)  \
> +({                                                                     \
> +       size_t __product;                                               \
> +       size_t __factor1 = (factor1);                                   \
> +       size_t __factor2 = (factor2);                                   \
> +       if (check_mul_overflow(__factor1, __factor2, &__product))       \
> +               __product = SIZE_MAX;                                   \
> +       __product;                                                      \
> +})
> +
> +/**
> + * size_mul() - Calculate size_t multiplication with saturation at SIZE_MAX
> + *
> + * @factor1: first factor
> + * @factor2: second factor
> + *
> + * Returns: calculate @factor1 * @factor2, where both values are
> + * evaluated as size_t, with any overflow causing the return value to
> + * be SIZE_MAX.
> + */
> +#define size_mul(factor1, factor2)                                     \
> +       __must_check_size(__size_mul(factor1, factor2,                  \
> +                                    __UNIQUE_ID(__factor1_),           \
> +                                    __UNIQUE_ID(__factor2_),           \
> +                                    __UNIQUE_ID(__product_)))
> +
> +/*
> + * Internal logic for size_add(). Takes variable names from UNIQUE_ID
> + * so that the local variables here will never collide with other local
> + * variables (for example, with itself).
> + */
> +#define __size_add(addend1, addend2, __addend1, __addend2, __sum)      \
> +({                                                                     \
> +       size_t __sum;                                                   \
> +       size_t __addend1 = (addend1);                                   \
> +       size_t __addend2 = (addend2);                                   \
> +       if (check_add_overflow(__addend1, __addend2, &__sum))           \
> +               __sum = SIZE_MAX;                                       \
> +       __sum;                                                          \
> +})
> +
> +/**
> + * size_add() - Calculate size_t addition with saturation at SIZE_MAX
> + *
> + * @addend1: first addend
> + * @addend2: second addend
> + *
> + * Returns: calculate @addend1 + @addend2, where both values are
> + * evaluated as size_t, with any overflow causing the return value to
> + * be SIZE_MAX.
> + */
> +#define size_add(addend1, addend2)                                     \
> +       __must_check_size(__size_add(addend1, addend2,                  \
> +                                    __UNIQUE_ID(__addend1_),           \
> +                                    __UNIQUE_ID(__addend2_),           \
> +                                    __UNIQUE_ID(__sum_)))

Is the use of __UNIQUE_ID really necessary? Is the point to avoid some
kind of variable shadowing?  (As opposed to just using names for the
new variables in the scope of the statement expressions? ie.

+#define __size_add(addend1, addend2, __sum)      \
+({                                                                     \
+       size_t __sum;                                                   \
+       if (check_add_overflow((size_t)__addend1, (size_t)__addend2,
&__sum))           \
+               __sum = SIZE_MAX;                                       \
+       __sum;                                                          \
+})

Do the double-underscore-prefixed really need to be a separate
#define, or can their definitions be inlined into the expansion sites;
there seems like there's no other users of the
double-underscore-prefixed versions otherwise. ie.

#define size_add(addend1, addend2) \
  __must_check_size(({ \
    size_t sum;  \
    if (check_add_overflow((size_t)addend1, (size_t)addend2), &sum;  \
      sum = SIZE_MAX;  \
    sum;  \
})

> +
>  /**
>   * array_size() - Calculate size of 2-dimensional array.
>   *
> @@ -128,15 +199,7 @@ static inline bool __must_check __must_check_overflow(bool overflow)
>   * Returns: number of bytes needed to represent the array or SIZE_MAX on
>   * overflow.
>   */
> -static inline __must_check size_t array_size(size_t a, size_t b)
> -{
> -       size_t bytes;
> -
> -       if (check_mul_overflow(a, b, &bytes))
> -               return SIZE_MAX;
> -
> -       return bytes;
> -}
> +#define array_size(a, b)       size_mul(a, b)
>
>  /**
>   * array3_size() - Calculate size of 3-dimensional array.
> @@ -150,65 +213,38 @@ static inline __must_check size_t array_size(size_t a, size_t b)
>   * Returns: number of bytes needed to represent the array or SIZE_MAX on
>   * overflow.
>   */
> -static inline __must_check size_t array3_size(size_t a, size_t b, size_t c)
> -{
> -       size_t bytes;
> -
> -       if (check_mul_overflow(a, b, &bytes))
> -               return SIZE_MAX;
> -       if (check_mul_overflow(bytes, c, &bytes))
> -               return SIZE_MAX;
> -
> -       return bytes;
> -}
> -
> -/*
> - * Compute a*b+c, returning SIZE_MAX on overflow. Internal helper for
> - * struct_size() below.
> - */
> -static inline __must_check size_t __ab_c_size(size_t a, size_t b, size_t c)
> -{
> -       size_t bytes;
> -
> -       if (check_mul_overflow(a, b, &bytes))
> -               return SIZE_MAX;
> -       if (check_add_overflow(bytes, c, &bytes))
> -               return SIZE_MAX;
> -
> -       return bytes;
> -}
> +#define array3_size(a, b, c)   size_mul(size_mul(a, b), c)
>
>  /**
> - * struct_size() - Calculate size of structure with trailing array.
> + * flex_array_size() - Calculate size of a flexible array member
> + *                     within an enclosing structure.
> + *
>   * @p: Pointer to the structure.
> - * @member: Name of the array member.
> + * @member: Name of the flexible array member.
>   * @count: Number of elements in the array.
>   *
> - * Calculates size of memory needed for structure @p followed by an
> - * array of @count number of @member elements.
> + * Calculates size of a flexible array of @count number of @member
> + * elements, at the end of structure @p.
>   *
>   * Return: number of bytes needed or SIZE_MAX on overflow.
>   */
> -#define struct_size(p, member, count)                                  \
> -       __ab_c_size(count,                                              \
> -                   sizeof(*(p)->member) + __must_be_array((p)->member),\
> -                   sizeof(*(p)))
> +#define flex_array_size(p, member, count)                              \
> +       size_mul(count,                                                 \
> +                sizeof(*(p)->member) + __must_be_array((p)->member))
>
>  /**
> - * flex_array_size() - Calculate size of a flexible array member
> - *                     within an enclosing structure.
> + * struct_size() - Calculate size of structure with trailing flexible array.
>   *
>   * @p: Pointer to the structure.
> - * @member: Name of the flexible array member.
> + * @member: Name of the array member.
>   * @count: Number of elements in the array.
>   *
> - * Calculates size of a flexible array of @count number of @member
> - * elements, at the end of structure @p.
> + * Calculates size of memory needed for structure @p followed by an
> + * array of @count number of @member elements.
>   *
>   * Return: number of bytes needed or SIZE_MAX on overflow.
>   */
> -#define flex_array_size(p, member, count)                              \
> -       array_size(count,                                               \
> -                   sizeof(*(p)->member) + __must_be_array((p)->member))
> +#define struct_size(p, member, count)                                  \
> +       size_add(sizeof(*(p)), flex_array_size(p, member, count))
>
>  #endif /* __LINUX_OVERFLOW_H */
> diff --git a/lib/test_overflow.c b/lib/test_overflow.c
> index 7a4b6f6c5473..01a469ff7ff6 100644
> --- a/lib/test_overflow.c
> +++ b/lib/test_overflow.c
> @@ -588,12 +588,73 @@ static int __init test_overflow_allocation(void)
>         return err;
>  }
>
> +struct __test_flex_array {
> +       unsigned long flags;
> +       size_t count;
> +       unsigned long data[];
> +};
> +
> +static int __init test_overflow_size_helpers(void)
> +{
> +       struct __test_flex_array *obj;
> +       int count = 0;
> +       int err = 0;
> +
> +#define check_one_size_helper(expected, func, args...) ({      \
> +       bool __failure = false;                                 \
> +       size_t _r;                                              \
> +                                                               \
> +       _r = func(args);                                        \
> +       if (_r != (expected)) {                                 \
> +               pr_warn("expected " #func "(" #args ") "        \
> +                       "to return %zu but got %zu instead\n",  \
> +                       (size_t)(expected), _r);                \
> +               __failure = true;                               \
> +       }                                                       \
> +       count++;                                                \
> +       __failure;                                              \
> +})
> +
> +       err |= check_one_size_helper(5,        size_add, 2, 3);
> +       err |= check_one_size_helper(SIZE_MAX, size_add, SIZE_MAX,  1);
> +       err |= check_one_size_helper(SIZE_MAX, size_add, SIZE_MAX,  3);
> +       err |= check_one_size_helper(SIZE_MAX, size_add, SIZE_MAX, -3);

Sorry, is this ^ case saying that we expect SIZE_MAX + -3 == SIZE_MAX?
This is because the helpers performed unsigned arithmetic on size_t?

> +
> +       err |= check_one_size_helper(6,        size_mul, 2, 3);
> +       err |= check_one_size_helper(SIZE_MAX, size_mul, SIZE_MAX,  1);
> +       err |= check_one_size_helper(SIZE_MAX, size_mul, SIZE_MAX,  3);
> +       err |= check_one_size_helper(SIZE_MAX, size_mul, SIZE_MAX, -3);
> +
> +       err |= check_one_size_helper(0, flex_array_size, obj, data, 0);
> +       err |= check_one_size_helper(sizeof(*obj->data),
> +                                    flex_array_size, obj, data, 1);
> +       err |= check_one_size_helper(7 * sizeof(*obj->data),
> +                                    flex_array_size, obj, data, 7);
> +       err |= check_one_size_helper(SIZE_MAX,
> +                                    flex_array_size, obj, data, -1);
> +       err |= check_one_size_helper(SIZE_MAX,
> +                                    flex_array_size, obj, data, SIZE_MAX - 4);
> +
> +       err |= check_one_size_helper(sizeof(*obj), struct_size, obj, data, 0);
> +       err |= check_one_size_helper(sizeof(*obj) + sizeof(*obj->data),
> +                                    struct_size, obj, data, 1);
> +       err |= check_one_size_helper(SIZE_MAX,
> +                                    struct_size, obj, data, -3);
> +       err |= check_one_size_helper(SIZE_MAX,
> +                                    struct_size, obj, data, SIZE_MAX - 3);
> +
> +       pr_info("%d overflow size helper tests finished\n", count);
> +
> +       return err;
> +}
> +
>  static int __init test_module_init(void)
>  {
>         int err = 0;
>
>         err |= test_overflow_calculation();
>         err |= test_overflow_shift();
> +       err |= test_overflow_size_helpers();
>         err |= test_overflow_allocation();
>
>         if (err) {
> --
> 2.30.2
>


-- 
Thanks,
~Nick Desaulniers