Messages in this thread Patch in this message | | | From | Kees Cook <> | Subject | [PATCH 1/2] overflow: Implement size_t saturating arithmetic helpers | Date | Mon, 20 Sep 2021 11:08:52 -0700 |
| |
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
| |