lkml.org 
[lkml]   [2021]   [Sep]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 1/2] overflow: Implement size_t saturating arithmetic helpers
    Date
    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_)))
    +
    /**
    * 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);
    +
    + 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
    \
     
     \ /
      Last update: 2021-09-21 03:36    [W:4.096 / U:0.792 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site