| Message ID | 20210920180853.1825195-2-keescook@chromium.org (mailing list archive) |
|---|---|
| State | Changes Requested |
| Headers | show |
| Series | overflow: Implement size_t saturating arithmetic helpers | expand |
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 = 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 >
On Mon, Sep 20, 2021 at 03:06:33PM -0700, Nick Desaulniers wrote: > On Mon, Sep 20, 2021 at 11:09 AM Kees Cook <keescook@chromium.org> wrote: > > [...] > > +/* > > + * 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. Yes, when composed[1], they would shadow (under -Wshadow). I'd rather not knowingly add yet more[2] shadowed variables to the kernel. :) [1] https://godbolt.org/z/1rM6Ko1j3 [2] https://github.com/KSPP/linux/issues/152 > +#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 = SIZE_MAX; \ > sum; \ > }) Right, there aren't, but that's the way to pass such variable names in. (See minmax.h.) This also leaves the door open for using these helpers as constant expressions, if the need arises. > > + 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? Correct. When I wrote this I hadn't yet found any cases of needing to shrink an allocation size that followed a common pattern like this. But it turns out we do have some: drivers/infiniband/core/sa_query.c: sa_dev = kzalloc(struct_size(sa_dev, port, e - s + 1), GFP_KERNEL); drivers/infiniband/core/user_mad.c: umad_dev = kzalloc(struct_size(umad_dev, ports, e - s + 1), GFP_KERNEL); drivers/net/ethernet/intel/iavf/iavf_virtchnl.c: len = struct_size(vti, list, adapter->num_tc - 1); I'll need to add size_sub() as well. Thanks for looking this over!
On 20/09/2021 20.08, Kees Cook wrote: > + * 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; \ > +}) > + Why can't this just be a static inline taking and returning size_ts, avoiding all the unique_id ritual and triple layers of macros? > -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) For example, it could be the very function that you remove here and then add a compat alias. IDGI, if you want that functionality by another name, just rename array_size, or let size_mul be a #define for array_size. And we don't have a size_add, but that could just as well be a static inline that has the __must_check itself. Not that I can see that the __must_check matters much for these anyway; if anybody does size_mul(foo, bar); that's just a statement with no side effects, so probably the compiler would warn anyway, or at least nobody can then go on to do anything "wrong". Unlike the check_*_overflow(), which have the (possibly wrapped) result in a output-pointer and the "did it overflow" as the return value, so you can do check_mul_overflow(a, b, &d); do_stuff_with(d); were it not for the __must_check wrapper. [Reminder: __must_check is a bit of a misnomer, the attribute is really warn_unused_result, and there's no requirement that the result is part of the controlling expression of an if() or while() - just passing the result on directly to some other function counts as a "use", which is indeed what we do with the size wrappers.] Rasmus
On Tue, Sep 21, 2021 at 08:51:53AM +0200, Rasmus Villemoes wrote: > On 20/09/2021 20.08, Kees Cook wrote: > > > + * 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; \ > > +}) > > + > > Why can't this just be a static inline taking and returning size_ts, > avoiding all the unique_id ritual and triple layers of macros? *hold face* Yeah. I've been doing so much type-agnostic macro work lately that I completely looked past the characteristics I was describing for this macro are ... in fact ... how functions actually work. *sigh* Yes, I'll change all of these to just be static inlines. If we ever need them as constant expressions, we can fix them then. > Not that I can see that the __must_check matters much for these anyway; > if anybody does > > size_mul(foo, bar); > > that's just a statement with no side effects, so probably the compiler > would warn anyway, or at least nobody can then go on to do anything > "wrong". Unlike the check_*_overflow(), which have the (possibly > wrapped) result in a output-pointer and the "did it overflow" as the > return value, so you can do > > check_mul_overflow(a, b, &d); > do_stuff_with(d); > > were it not for the __must_check wrapper. > > [Reminder: __must_check is a bit of a misnomer, the attribute is really > warn_unused_result, and there's no requirement that the result is part > of the controlling expression of an if() or while() - just passing the > result on directly to some other function counts as a "use", which is > indeed what we do with the size wrappers.] Yeah, all a good point. My knee-jerk reaction is to include __must_check just because it's "free" here. Thanks! -Kees
*thread necromancy* On Tue, Sep 21, 2021 at 08:51:53AM +0200, Rasmus Villemoes wrote: > Not that I can see that the __must_check matters much for these anyway; > if anybody does > > size_mul(foo, bar); > > that's just a statement with no side effects, so probably the compiler > would warn anyway, or at least nobody can then go on to do anything > "wrong". Unlike the check_*_overflow(), which have the (possibly > wrapped) result in a output-pointer and the "did it overflow" as the > return value, so you can do > > check_mul_overflow(a, b, &d); > do_stuff_with(d); > > were it not for the __must_check wrapper. > > [Reminder: __must_check is a bit of a misnomer, the attribute is really > warn_unused_result, and there's no requirement that the result is part > of the controlling expression of an if() or while() - just passing the > result on directly to some other function counts as a "use", which is > indeed what we do with the size wrappers.] What I'd really like is a "store this in a size_t" check to catch dumb storage size problems (or related overflows). In other words: size_t big1 = 2147483647; size_t big2 = 2147483647; /* Doesn't overflow, but 4611686014132420609 becomes a 1 for int */ int size = size_mul(big1, big2); ... ptr = kmalloc(size, GFP_KERNEL); /* Allocates a 1 instead... */ I could solve this but removing the assignment, but then I can't compose calls: static inline size_t __size_mul(size_t f1, size_t f2) { size_t out; if (check_mul_overflow(f1, f2, &out)) out = SIZE_MAX; return out; } #define size_mul(f1, f2, out) do { \ BUILD_BUG_ON(!__same_type(out, size_t)); \ out = __size_mul(f1, f2); \ } while (0) i.e. now I can't do size_mul(size_add(...), size_add(...)) Better would be to build the entire kernel with -Wconversion. :)
On Mon, Jan 24, 2022 at 1:13 PM Kees Cook <keescook@chromium.org> wrote: > > What I'd really like is a "store this in a size_t" check to catch dumb > storage size problems (or related overflows). In other words: > > size_t big1 = 2147483647; > size_t big2 = 2147483647; > > /* Doesn't overflow, but 4611686014132420609 becomes a 1 for int */ > int size = size_mul(big1, big2); > ... > ptr = kmalloc(size, GFP_KERNEL); /* Allocates a 1 instead... */ -Wshorten-64-to-32 ?
On Mon, Jan 24, 2022 at 01:13:20PM -0800, Kees Cook wrote: > *thread necromancy* > > On Tue, Sep 21, 2021 at 08:51:53AM +0200, Rasmus Villemoes wrote: > > Not that I can see that the __must_check matters much for these anyway; > > if anybody does > > > > size_mul(foo, bar); > > > > that's just a statement with no side effects, so probably the compiler > > would warn anyway, or at least nobody can then go on to do anything > > "wrong". Unlike the check_*_overflow(), which have the (possibly > > wrapped) result in a output-pointer and the "did it overflow" as the > > return value, so you can do > > > > check_mul_overflow(a, b, &d); > > do_stuff_with(d); > > > > were it not for the __must_check wrapper. > > > > [Reminder: __must_check is a bit of a misnomer, the attribute is really > > warn_unused_result, and there's no requirement that the result is part > > of the controlling expression of an if() or while() - just passing the > > result on directly to some other function counts as a "use", which is > > indeed what we do with the size wrappers.] > > What I'd really like is a "store this in a size_t" check to catch dumb > storage size problems (or related overflows). In other words: Yes, this. The overflow things are nice, but quite often we need to get things into a size_t to use with an allocator and the rigorous type checking in the normal overflows is a problem. Jason
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) {
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(-)