overflow: Introduce wrapping helpers
Subsystems (2)
v2 cover overflow: Introduce wrapping helpers
Hi,
v2:
- Define inc/dec_wrap() in terms of add/sub_wrap() and avoid side-effects (Rasmus)
- Fix various typos (Rasmus)
- Add selftests for all the new helpers
v1: https://lore.kernel.org/lkml/[email protected]/
In preparation for gaining instrumentation for signed[1], unsigned[2], and pointer[3] wrap-around, expand the overflow header to include wrap-around helpers that can be used to annotate arithmetic where wrapped calculations are expected (e.g. atomics).
After spending time getting the unsigned integer wrap-around sanitizer running warning-free on a basic x86_64 boot[4], I think the *_wrap() helpers first argument being the output type makes the most sense (as suggested by Rasmus).
-Kees
Kees Cook (5):
overflow: Adjust check_*_overflow() kern-doc to reflect results
overflow: Expand check_add_overflow() for pointer addition
overflow: Introduce add_would_overflow()
overflow: Introduce add_wrap(), sub_wrap(), and mul_wrap()
overflow: Introduce inc_wrap() and dec_wrap()
include/linux/compiler_types.h | 10 +++ include/linux/overflow.h | 160 ++++++++++++++++++++++++++++++--- lib/overflow_kunit.c | 132 ++++++++++++++++++++++++--- 3 files changed, 277 insertions(+), 25 deletions(-)
Signature · 1 line
2.34.1
PATCH v2 2/5 overflow: Expand check_add_overflow() for pointer addition
The check_add_overflow() helper is mostly a wrapper around __builtin_add_overflow(), but GCC and Clang refuse to operate on pointer arguments that would normally be allowed if the addition were open-coded.
For example, we have many places where pointer overflow is tested:
struct foo *ptr; ... /* Check for overflow */ if (ptr + count < ptr) ...
And in order to avoid running into the overflow sanitizers in the future, we need to rewrite these "intended" overflow checks:
if (check_add_overflow(ptr, count, &result)) ...
Frustratingly the argument type validation for __builtin_add_overflow() is done before evaluating __builtin_choose_expr(), so for arguments to be valid simultaneously for sizeof(*p) (when p may not be a pointer), and __builtin_add_overflow(a, ...) (when a may be a pointer), we must introduce wrappers that always produce a specific type (but they are only used in the places where the bogus arguments will be ignored).
To test whether a variable is a pointer or not, introduce the __is_ptr() helper, which uses __builtin_classify_type() to find arrays and pointers (via the new __is_ptr_or_array() helper), and then decays arrays into pointers (via the new __decay() helper), to distinguish pointers from arrays.
Additionally update the unit tests to cover pointer addition.
--- include/linux/compiler_types.h | 10 +++++ include/linux/overflow.h | 44 ++++++++++++++++++- lib/overflow_kunit.c | 77 ++++++++++++++++++++++++++++++---- 3 files changed, 120 insertions(+), 11 deletions(-)
include/linux/compiler_types.h +10 -0
@@ -375,6 +375,16 @@ struct ftrace_likely_data {/* Are two types/vars the same type (ignoring qualifiers)? */ #define __same_type (a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) +/* Is variable addressable? */ +#define __is_ptr_or_array (p) (__builtin_classify_type(p) == 5) + +/* Return an array decayed to a pointer. */ +#define __decay (p) \ + (&*__builtin_choose_expr(__is_ptr_or_array(p), p, NULL)) + +/* Report if variable is a pointer type. */ +#define __is_ptr (p) __same_type(p, __decay(p)) +/* * __unqual_scalar_typeof(x) - Declare an unqualified scalar type, leaving * non-scalar types unchanged.
include/linux/overflow.h +42 -2
56 lines not on this page · raw message
lib/overflow_kunit.c +68 -9
114 lines not on this page · raw message
Signature · 1 line
2.34.1
PATCH v2 3/5 overflow: Introduce add_would_overflow()
In reply to Kees CookFor instances where only the overflow needs to be checked (and the sum isn't used), provide the new helper add_would_overflow(), which is a wrapper for check_add_overflow().
--- include/linux/overflow.h | 16 ++++++++++++++++ 1 file changed, 16 insertions(+)
include/linux/overflow.h +16 -0
@@ -104,6 +104,22 @@ static inline bool __must_check __must_check_overflow(bool overflow) __builtin_add_overflow(__filter_integral(a), b, \ __filter_ptrint(d)))) +/** +* add_would_overflow() - Check if an addition would overflow +* @var: variable to add to that is checked for overflow +* @offset: value to add +* +* Returns true if the sum would overflow. +* +* To keep a copy of the sum when the addition doesn't overflow, use +* check_add_overflow() instead. +*/ +#define add_would_overflow (var, offset) \ + __must_check_overflow(({ \ + typeof(var) __result; \ + check_add_overflow(var, offset, &__result); \ + })) +/** * check_sub_overflow() - Calculate subtraction with overflow checking * @a: minuend; value to subtract from
Signature · 1 line
2.34.1
PATCH v2 4/5 overflow: Introduce add_wrap(), sub_wrap(), and mul_wrap()
In reply to Kees CookProvide helpers that will perform wrapping addition, subtraction, or multiplication without tripping the arithmetic wrap-around sanitizers. The first argument is the type under which the wrap-around should happen with. In other words, these two calls will get very different results:
mul_wrap(int, 50, 50) == 2500 mul_wrap(u8, 50, 50) == 196
Add to the selftests to validate behavior and lack of side-effects.
--- include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++ lib/overflow_kunit.c | 11 ++++++++ 2 files changed, 65 insertions(+)
include/linux/overflow.h +54 -0
@@ -120,6 +120,24 @@ static inline bool __must_check __must_check_overflow(bool overflow)check_add_overflow (var, offset, &__result); \ })) +/** +* add_wrap() - Intentionally perform a wrapping addition +* @type: type for result of calculation +* @a: first addend +* @b: second addend +* +* Return the potentially wrapped-around addition without +* tripping any wrap-around sanitizers that may be enabled. +*/ +#define add_wrap (type, a, b) \ + ({ \ + type __val; \ + if (check_add_overflow(a, b, &__val)) { \ +/* do nothing */ \ + } \ + __val; \ + }) +/** * check_sub_overflow() - Calculate subtraction with overflow checking * @a: minuend; value to subtract from
@@ -133,6 +151,24 @@ static inline bool __must_check __must_check_overflow(bool overflow)#define check_sub_overflow (a, b, d) \ __must_check_overflow(__builtin_sub_overflow(a, b, d)) +/** +* sub_wrap() - Intentionally perform a wrapping subtraction +* @type: type for result of calculation +* @a: minuend; value to subtract from +* @b: subtrahend; value to subtract from @a +* +* Return the potentially wrapped-around subtraction without +* tripping any wrap-around sanitizers that may be enabled. +*/ +#define sub_wrap (type, a, b) \ + ({ \ + type __val; \ + if (check_sub_overflow(a, b, &__val)) { \ +/* do nothing */ \ + } \ + __val; \ + }) +/** * check_mul_overflow() - Calculate multiplication with overflow checking * @a: first factor
@@ -146,6 +182,24 @@ static inline bool __must_check __must_check_overflow(bool overflow)#define check_mul_overflow (a, b, d) \ __must_check_overflow(__builtin_mul_overflow(a, b, d)) +/** +* mul_wrap() - Intentionally perform a wrapping multiplication +* @type: type for result of calculation +* @a: first factor +* @b: second factor +* +* Return the potentially wrapped-around multiplication without +* tripping any wrap-around sanitizers that may be enabled. +*/ +#define mul_wrap (type, a, b) \ + ({ \ + type __val; \ + if (check_mul_overflow(a, b, &__val)) { \ +/* do nothing */ \ + } \ + __val; \ + }) +/** * check_shl_overflow() - Calculate a left-shifted value and check overflow * @a: Value to be shifted
lib/overflow_kunit.c +11 -0
@@ -273,6 +273,17 @@ DEFINE_TEST_ARRAY(s64) = {/* Check for internal macro side-effects. */ \ _of = check_ ## op ## _overflow(_a_orig++, _b_orig++, &_r); \ KUNIT_EXPECT_TRUE_MSG(test, _a_orig == _a_bump, "Unexpected " #op " macro side-effect!\n"); \ + KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected " #op " macro side-effect!\n"); \ + \ + _r = op ## _wrap(t, a, b); \ + KUNIT_EXPECT_TRUE_MSG(test, _r == r, \ + "expected "fmt" "sym" "fmt" == "fmt", got "fmt" (type %s)\n", \ + a, b, r, _r, #t); \ +/* Check for internal macro side-effects. */ \ + _a_orig = a; \ + _b_orig = b; \ + _r = op ## _wrap(t, _a_orig++, _b_orig++); \ + KUNIT_EXPECT_TRUE_MSG(test, _a_orig == _a_bump, "Unexpected " #op " macro side-effect!\n"); \ KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected " #op " macro side-effect!\n"); \ } while (0)
Signature · 1 line
2.34.1
PATCH v2 1/5 overflow: Adjust check_*_overflow() kern-doc to reflect results
In reply to Kees CookThe check_*_overflow() helpers will return results with potentially wrapped-around values. These values have always been checked by the selftests, so avoid the confusing language in the kern-doc. The idea of "safe for use" was relative to the expectation of whether or not the caller wants a wrapped value -- the calculation itself will always follow arithmetic wrapping rules.
--- include/linux/overflow.h | 18 ++++++------------ 1 file changed, 6 insertions(+), 12 deletions(-)
include/linux/overflow.h +6 -12
@@ -57,11 +57,9 @@ static inline bool __must_check __must_check_overflow(bool overflow)* @b: second addend * @d: pointer to store sum * -* Returns 0 on success. +* Returns 0 on success, 1 on wrap-around. * -* *@d holds the results of the attempted addition, but is not considered -* "safe for use" on a non-zero return value, which indicates that the -* sum has overflowed or been truncated. +* *@d holds the results of the attempted addition, which may wrap-around. */ #define check_add_overflow (a, b, d) \ __must_check_overflow(__builtin_add_overflow(a, b, d))
@@ -72,11 +70,9 @@ static inline bool __must_check __must_check_overflow(bool overflow)* @b: subtrahend; value to subtract from @a * @d: pointer to store difference * -* Returns 0 on success. +* Returns 0 on success, 1 on wrap-around. * -* *@d holds the results of the attempted subtraction, but is not considered -* "safe for use" on a non-zero return value, which indicates that the -* difference has underflowed or been truncated. +* *@d holds the results of the attempted subtraction, which may wrap-around. */ #define check_sub_overflow (a, b, d) \ __must_check_overflow(__builtin_sub_overflow(a, b, d))
@@ -87,11 +83,9 @@ static inline bool __must_check __must_check_overflow(bool overflow)* @b: second factor * @d: pointer to store product * -* Returns 0 on success. +* Returns 0 on success, 1 on wrap-around. * -* *@d holds the results of the attempted multiplication, but is not -* considered "safe for use" on a non-zero return value, which indicates -* that the product has overflowed or been truncated. +* *@d holds the results of the attempted multiplication, which may wrap-around. */ #define check_mul_overflow (a, b, d) \ __must_check_overflow(__builtin_mul_overflow(a, b, d))
Signature · 1 line
2.34.1
PATCH v2 5/5 overflow: Introduce inc_wrap() and dec_wrap()
In reply to Kees CookThis allows replacements of the idioms "var += offset" and "var -= offset" with the inc_wrap() and dec_wrap() helpers respectively. They will avoid wrap-around sanitizer instrumentation.
Add to the selftests to validate behavior and lack of side-effects.
--- include/linux/overflow.h | 28 +++++++++++++++++++++ lib/overflow_kunit.c | 54 ++++++++++++++++++++++++++++++++++------ 2 files changed, 75 insertions(+), 7 deletions(-)
include/linux/overflow.h +28 -0
@@ -138,6 +138,20 @@ static inline bool __must_check __must_check_overflow(bool overflow) __val; \ }) +/** +* inc_wrap() - Intentionally perform a wrapping increment +* @a: variable to be incremented +* @b: amount to add +* +* Increments @a by @b with wrap-around. Returns the resulting +* value of @a. Will not trip any wrap-around sanitizers. +*/ +#define inc_wrap (var, offset) \ + ({ \ + typeof(var) *__ptr = &(var); \ + *__ptr = add_wrap(typeof(var), *__ptr, offset); \ + }) +/** * check_sub_overflow() - Calculate subtraction with overflow checking * @a: minuend; value to subtract from
@@ -169,6 +183,20 @@ static inline bool __must_check __must_check_overflow(bool overflow) __val; \ }) +/** +* dec_wrap() - Intentionally perform a wrapping decrement +* @a: variable to be decremented +* @b: amount to subtract +* +* Decrements @a by @b with wrap-around. Returns the resulting +* value of @a. Will not trip any wrap-around sanitizers. +*/ +#define dec_wrap (var, offset) \ + ({ \ + typeof(var) *__ptr = &(var); \ + *__ptr = sub_wrap(typeof(var), *__ptr, offset); \ + }) +/** * check_mul_overflow() - Calculate multiplication with overflow checking * @a: first factor
lib/overflow_kunit.c +47 -7
83 lines not on this page · raw message
Signature · 1 line
2.34.1
Re: [PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition
In reply to Kees CookQuoted 52 lines · Kees Cook
The
check_add_overflow()helper is mostly a wrapper around__builtin_add_overflow(), but GCC and Clang refuse to operate on pointer arguments that would normally be allowed if the addition were open-coded.For example, we have many places where pointer overflow is tested:
struct foo *ptr; ... /* Check for overflow */ if (ptr + count < ptr) ...And in order to avoid running into the overflow sanitizers in the future, we need to rewrite these "intended" overflow checks:
if (
check_add_overflow(ptr, count, &result)) ...Frustratingly the argument type validation for
__builtin_add_overflow()is done before evaluating__builtin_choose_expr(), so for arguments to be valid simultaneously forsizeof(*p)(when p may not be a pointer), and__builtin_add_overflow(a, ...)(when a may be a pointer), we must introduce wrappers that always produce a specific type (but they are only used in the places where the bogus arguments will be ignored).To test whether a variable is a pointer or not, introduce the
__is_ptr()helper, which uses__builtin_classify_type()to find arrays and pointers (via the new__is_ptr_or_array()helper), and then decays arrays into pointers (via the new__decay()helper), to distinguish pointers from arrays.Additionally update the unit tests to cover pointer addition.
Cc Rasmus Villemoes <[email protected]>Cc "Gustavo A. R. Silva" <[email protected]>Cc Andrew Morton <[email protected]>Cc Nathan Chancellor <[email protected]>Cc Nick Desaulniers <[email protected]>Cc Bill Wendling <[email protected]>Cc Justin Stitt <[email protected]>Signed-off-by Kees Cook <[email protected]>--- include/linux/compiler_types.h | 10 +++++ include/linux/overflow.h | 44 ++++++++++++++++++- lib/overflow_kunit.c | 77 ++++++++++++++++++++++++++++++---- 3 files changed, 120 insertions(+), 11 deletions(-)include/linux/compiler_types.h +0
-0
include/linux/compiler_types.h struct ftrace_likely_data { · line 379
Quoted 5 lines
include/linux/compiler_types.h +2
-0@@ -375,6 +375,16 @@ struct ftrace_likely_data {/* Are two types/vars the same type (ignoring qualifiers)? */ #define __same_type (a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) +/* Is variable addressable? */ +#define __is_ptr_or_array (p) (__builtin_classify_type(p) == 5)
That magic constant is a bit ugly, but I don't think there's a better way. However, a comment saying "pointer_type_class in gcc/typeclass.h in gcc source code" or something like that might help. Do we know for sure that clang uses the same value? I can't find it documented anywhere.
__check_ptr_add_overflow() - Calculate pointer addition with overflow checking
Quoted 12 lines
include/linux/compiler_types.h +12
-0+* @a: pointer addend +* @b: numeric addend +* @d: pointer to store sum +* +* Returns 0 on success, 1 on wrap-around. +* +* Do not use this function directly, use check_add_overflow() instead. +* +* *@d holds the results of the attempted addition, which may wrap-around. +*/ +#define __check_ptr_add_overflow (a, b, d) \ + ({ \
include/linux/compiler_types.h struct ftrace_likely_data {
Quoted 10 lines
include/linux/compiler_types.h +10
-0+typeof (a) __a = (a); \ +typeof (b) __b = (b); \ +size_t __bytes; \ +bool __overflow; \ + \ +/* we want to perform the wrap-around, but retain the result */ \ + __overflow =__builtin_mul_overflow (sizeof (*(__a)), __b, &__bytes); \ +__builtin_add_overflow ((unsigned long )(__a), __bytes, (unsigned long *)(d)) || \ + __overflow; \ + })
So I've tried to wrap my head around all these layers of macros, and it seems ok. However, here I'm a bit worried that there's no type checking of the destination. In particular, the user could perhaps end up doing
check_add_overflow(p, x, p)
which will go horribly wrong. Do we have any infrastructure for testing "this should fail to compile"? It would be good to have, not just for this, but in general for checking our sanity checks.
Another thing is that this will always fail with negative offsets (if b has signed type and a negative value, the multiplication won't fit in an unsigned type). I think __bytes should be ptrdiff_t.
Rasmus
Re: [PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition
In reply to Kees CookQuoted 23 lines · Kees Cook
The
check_add_overflow()helper is mostly a wrapper around__builtin_add_overflow(), but GCC and Clang refuse to operate on pointer arguments that would normally be allowed if the addition were open-coded.For example, we have many places where pointer overflow is tested:
struct foo *ptr; ... /* Check for overflow */ if (ptr + count < ptr) ...And in order to avoid running into the overflow sanitizers in the future, we need to rewrite these "intended" overflow checks:
if (
check_add_overflow(ptr, count, &result)) ...Frustratingly the argument type validation for
__builtin_add_overflow()is done before evaluating__builtin_choose_expr(), so for arguments to be valid simultaneously forsizeof(*p)(when p may not be a pointer), and__builtin_add_overflow(a, ...)(when a may be a pointer), we must introduce wrappers that always produce a specific type (but they are only used in the places where the bogus arguments will be ignored).
Quoted 5 lines
To test whether a variable is a pointer or not, introduce the
__is_ptr()helper, which uses__builtin_classify_type()to find arrays and pointers (via the new__is_ptr_or_array()helper), and then decays arrays into pointers (via the new__decay()helper), to distinguish pointers from arrays.
This is (not just commit msg but together with impl), at first glance, too complicated for regular developers to grasp (that is perhaps fine), but could we make it simpler by, say _Generic() or other trick?
Quoted 225 lines
Additionally update the unit tests to cover pointer addition.
Cc Rasmus Villemoes <[email protected]>Cc "Gustavo A. R. Silva" <[email protected]>Cc Andrew Morton <[email protected]>Cc Nathan Chancellor <[email protected]>Cc Nick Desaulniers <[email protected]>Cc Bill Wendling <[email protected]>Cc Justin Stitt <[email protected]>Signed-off-by Kees Cook <[email protected]>--- include/linux/compiler_types.h | 10 +++++ include/linux/overflow.h | 44 ++++++++++++++++++- lib/overflow_kunit.c | 77 ++++++++++++++++++++++++++++++---- 3 files changed, 120 insertions(+), 11 deletions(-)include/linux/compiler_types.h +10
-0@@ -375,6 +375,16 @@ struct ftrace_likely_data {/* Are two types/vars the same type (ignoring qualifiers)? */ #define __same_type (a, b) __builtin_types_compatible_p(typeof(a), typeof(b)) +/* Is variable addressable? */ +#define __is_ptr_or_array (p) (__builtin_classify_type(p) == 5) + +/* Return an array decayed to a pointer. */ +#define __decay (p) \ + (&*__builtin_choose_expr(__is_ptr_or_array(p), p, NULL)) + +/* Report if variable is a pointer type. */ +#define __is_ptr (p) __same_type(p, __decay(p)) +/* * __unqual_scalar_typeof(x) - Declare an unqualified scalar type, leaving * non-scalar types unchanged. include/linux/overflow.h +42
-2@@ -51,6 +51,43 @@ static inline bool __must_check __must_check_overflow(bool overflow)return unlikely (overflow); } +/* Always produce an integral variable expression. */ +#define __filter_integral (x) \ + __builtin_choose_expr(!__is_ptr(x), (x), 0) + +/* Always produce a pointer value. */ +#define __filter_ptr (x) \ + __builtin_choose_expr(__is_ptr(x), (x), NULL) + +/* Always produce a pointer to an integral value. */ +#define __filter_ptrint (x) \ + __builtin_choose_expr(!__is_ptr(*(x)), x, &(int){ 0 }) + +/** +* __check_ptr_add_overflow() - Calculate pointer addition with overflow checking +* @a: pointer addend +* @b: numeric addend +* @d: pointer to store sum +* +* Returns 0 on success, 1 on wrap-around. +* +* Do not use this function directly, use check_add_overflow() instead. +* +* *@d holds the results of the attempted addition, which may wrap-around. +*/ +#define __check_ptr_add_overflow (a, b, d) \ + ({ \ + typeof(a) __a = (a); \ + typeof(b) __b = (b); \ + size_t __bytes; \ + bool __overflow; \ + \ +/* we want to perform the wrap-around, but retain the result */ \ + __overflow =__builtin_mul_overflow (sizeof (*(__a)), __b, &__bytes); \ +__builtin_add_overflow ((unsigned long )(__a), __bytes, (unsigned long *)(d)) || \ + __overflow; \ + }) +/** * check_add_overflow() - Calculate addition with overflow checking * @a: first addend @@ -61,8 +98,11 @@ static inline bool __must_check __must_check_overflow(bool overflow)* * *@d holds the results of the attempted addition, which may wrap-around. */ -#define check_add_overflow (a, b, d) \ - __must_check_overflow(__builtin_add_overflow(a, b, d)) +#define check_add_overflow (a, b, d) \ + __must_check_overflow(__builtin_choose_expr(__is_ptr(a), \ + __check_ptr_add_overflow(__filter_ptr(a), b, d), \ + __builtin_add_overflow(__filter_integral(a), b, \ + __filter_ptrint(d))))/** * check_sub_overflow() - Calculate subtraction with overflow checking lib/overflow_kunit.c +68
-9@@ -45,13 +45,18 @@# define SKIP_64_ON_32 (t) do { } while (0)#endif -#define DEFINE_TEST_ARRAY_TYPED (t1, t2, t) \ - static const struct test_ ## t1 ## _ ## t2 ## __ ## t { \ +#define DEFINE_TEST_ARRAY_NAMED_TYPED (n1, n2, n, t1, t2, t) \ + static const struct test_ ## n1 ## _ ## n2 ## __ ## n { \ t1 a; \ t2 b; \ - t sum, diff, prod; \ + t sum; \ + t diff; \ + t prod; \ bool s_of, d_of, p_of; \ - } t1 ## _ ## t2 ## __ ## t ## _tests[] + } n1 ## _ ## n2 ## __ ## n ## _tests[] + +#define DEFINE_TEST_ARRAY_TYPED (t1, t2, t) \ + DEFINE_TEST_ARRAY_NAMED_TYPED(t1, t2, t, t1, t2, t)#define DEFINE_TEST_ARRAY (t) DEFINE_TEST_ARRAY_TYPED(t, t, t)@@ -251,8 +256,10 @@ DEFINE_TEST_ARRAY(s64) = { };#define check_one_op (t, fmt, op, sym, a, b, r, of) do { \ - int _a_orig = a, _a_bump = a + 1; \ - int _b_orig = b, _b_bump = b + 1; \ + typeof(a + 0) _a_orig = a; \ + typeof(a + 0) _a_bump = a + 1; \ + typeof(b + 0) _b_orig = b; \ + typeof(b + 0) _b_bump = b + 1; \ bool _of; \ t _r; \ \@@ -260,13 +267,13 @@ DEFINE_TEST_ARRAY(s64) = { KUNIT_EXPECT_EQ_MSG(test, _of, of, \ "expected "fmt" "sym" "fmt" to%s overflow (type %s)\n", \ a, b, of ? "" : " not", #t); \ - KUNIT_EXPECT_EQ_MSG(test, _r, r, \ + KUNIT_EXPECT_TRUE_MSG(test, _r == r, \ "expected "fmt" "sym" "fmt" == "fmt", got "fmt" (type %s)\n", \ a, b, r, _r, #t); \ /* Check for internal macro side-effects. */ \ _of = check_ ## op ## _overflow(_a_orig++, _b_orig++, &_r); \ - KUNIT_EXPECT_EQ_MSG(test, _a_orig, _a_bump, "Unexpected " #op " macro side-effect!\n"); \ - KUNIT_EXPECT_EQ_MSG(test, _b_orig, _b_bump, "Unexpected " #op " macro side-effect!\n"); \ + KUNIT_EXPECT_TRUE_MSG(test, _a_orig == _a_bump, "Unexpected " #op " macro side-effect!\n"); \ + KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected " #op " macro side-effect!\n"); \ } while (0)#define DEFINE_TEST_FUNC_TYPED (n, t, fmt) \@@ -333,6 +340,55 @@ DEFINE_TEST_ARRAY_TYPED(int, int, u8) = { };DEFINE_TEST_FUNC_TYPED (int_int__u8, u8,"%d" ); +#define DEFINE_TEST_PTR_FUNC_TYPED (n, t, fmt) \ +static void do_ptr_test_ ## n(struct kunit *test, const struct test_ ## n *p) \ +{ \ +/* we're only doing single-direction sums, no product or division */ \ +check_one_op (t, fmt, add,"+" , p->a, p->b, p->sum, p->s_of);\ +} \ + \ +static void n ## _overflow_test(struct kunit *test) { \ +unsigned i; \ + \ + for (i = 0; i < ARRAY_SIZE(n ## _tests); ++i) \ + do_ptr_test_ ## n(test, &n ## _tests[i]); \ + kunit_info(test, "%zu %s arithmetic tests finished\n", \ + ARRAY_SIZE(n ## _tests), #n); \ +} + +DEFINE_TEST_ARRAY_NAMED_TYPED(void, int, void, void *, int, void *) = { + {NULL, 0, NULL, NULL, NULL, false, false, false}, + {(void *)0x30, 0x10, (void *)0x40, NULL, NULL, false, false, false}, + {(void *)ULONG_MAX, 0, (void *)ULONG_MAX, NULL, NULL, false, false, false}, + {(void *)ULONG_MAX, 1, NULL, NULL, NULL, true, false, false}, + {(void *)ULONG_MAX, INT_MAX, (void *)(INT_MAX - 1), NULL, NULL, true, false, false}, +}; +DEFINE_TEST_PTR_FUNC_TYPED(void_int__void, void *, "%lx"); + +struct _sized { +int a; +char b; +}; + +DEFINE_TEST_ARRAY_NAMED_TYPED(sized, int, sized, struct _sized *, int, struct _sized *) = { + {NULL, 0, NULL, NULL, NULL, false, false, false}, + {NULL, 1, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, false, false, false}, + {NULL, 0x10, (struct _sized *)(sizeof(struct _sized) * 0x10), NULL, NULL, false, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized)), 1, (struct _sized *)ULONG_MAX, NULL, NULL, false, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 1, NULL, NULL, NULL, true, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 2, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, true, false, false}, + {(void *)(ULONG_MAX - sizeof(struct _sized) + 1), 3, (struct _sized *)(sizeof(struct _sized) * 2), NULL, NULL, true, false, false}, +}; +DEFINE_TEST_PTR_FUNC_TYPED(sized_int__sized, struct _sized *, "%lx"); + +DEFINE_TEST_ARRAY_NAMED_TYPED(sized, size_t, sized, struct _sized *, size_t, struct _sized *) = { + {NULL, 0, NULL, NULL, NULL, false, false, false}, + {NULL, 1, (struct _sized *)(sizeof(struct _sized)), NULL, NULL, false, false, false}, + {NULL, 0x10, (struct _sized *)(sizeof(struct _sized) * 0x10), NULL, NULL, false, false, false}, + {NULL, SIZE_MAX - 10, (struct _sized *)18446744073709551528UL, NULL, NULL, true, false, false}, +}; +DEFINE_TEST_PTR_FUNC_TYPED(sized_size_t__sized, struct _sized *, "%zu"); +/* Args are: value, shift, type, expected result, overflow expected */ #define TEST_ONE_SHIFT (a, s, t, expect, of) do { \ typeof(a) __a = (a); \@@ -1122,6 +1178,9 @@ static struct kunit_case overflow_test_cases[] = {KUNIT_CASE (s32_s32__s32_overflow_test),KUNIT_CASE (u64_u64__u64_overflow_test),KUNIT_CASE (s64_s64__s64_overflow_test), +KUNIT_CASE (void_int__void_overflow_test), +KUNIT_CASE (sized_int__sized_overflow_test), +KUNIT_CASE (sized_size_t__sized_overflow_test),KUNIT_CASE (u32_u32__int_overflow_test),KUNIT_CASE (u32_u32__u8_overflow_test), KUNIT_CASE(u8_u8__int_overflow_test),
Re: [PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition
Quoted 30 lines · Przemek Kitszel
Quoted 23 lines · Kees Cook
The
check_add_overflow()helper is mostly a wrapper around__builtin_add_overflow(), but GCC and Clang refuse to operate on pointer arguments that would normally be allowed if the addition were open-coded.For example, we have many places where pointer overflow is tested:
struct foo *ptr; ... /* Check for overflow */ if (ptr + count < ptr) ...And in order to avoid running into the overflow sanitizers in the future, we need to rewrite these "intended" overflow checks:
if (
check_add_overflow(ptr, count, &result)) ...Frustratingly the argument type validation for
__builtin_add_overflow()is done before evaluating__builtin_choose_expr(), so for arguments to be valid simultaneously forsizeof(*p)(when p may not be a pointer), and__builtin_add_overflow(a, ...)(when a may be a pointer), we must introduce wrappers that always produce a specific type (but they are only used in the places where the bogus arguments will be ignored).Quoted 5 lines
To test whether a variable is a pointer or not, introduce the
__is_ptr()helper, which uses__builtin_classify_type()to find arrays and pointers (via the new__is_ptr_or_array()helper), and then decays arrays into pointers (via the new__decay()helper), to distinguish pointers from arrays.
Quoted 3 lines
This is (not just commit msg but together with impl), at first glance, too complicated for regular developers to grasp (that is perhaps fine), but could we make it simpler by, say
_Generic()or other trick?
I haven't been able to find a way to do this, unfortunately. :( I would *love* to find something simpler, but it eludes me.
Signature · 1 line
Kees Cook
Re: [PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition
In reply to Rasmus VillemoesQuoted 10 lines · Rasmus Villemoes
Quoted 9 lines · Kees Cook
[...]
include/linux/compiler_types.h +0
-0@@ -375,6 +375,16 @@ struct ftrace_likely_data {/* Are two types/vars the same type (ignoring qualifiers)? */ #define __same_type (a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
Quoted 7 lines
include/linux/compiler_types.h struct ftrace_likely_data { · line 379
Quoted 2 lines
include/linux/compiler_types.h +2
-0+/* Is variable addressable? */ +#define __is_ptr_or_array (p) (__builtin_classify_type(p) == 5)That magic constant is a bit ugly, but I don't think there's a better way. However, a comment saying "
pointer_type_classingcc/typeclass.hin gcc source code" or something like that might help. Do we know for sure that clang uses the same value? I can't find it documented anywhere.
Very true. Offlist, Keith Packard suggested I switch to this, so we can avoid the constant:
+#define __is_ptr_or_array(p) (__builtin_classify_type(p) == \
__builtin_classify_type(NULL))
Quoted 30 lines
__check_ptr_add_overflow()- Calculate pointer addition with overflow checkingQuoted 12 lines
include/linux/compiler_types.h +12
-0+* @a: pointer addend +* @b: numeric addend +* @d: pointer to store sum +* +* Returns 0 on success, 1 on wrap-around. +* +* Do not use this function directly, use check_add_overflow() instead. +* +* *@d holds the results of the attempted addition, which may wrap-around. +*/ +#define __check_ptr_add_overflow (a, b, d) \ + ({ \include/linux/compiler_types.h struct ftrace_likely_data {
Quoted 10 lines
include/linux/compiler_types.h +10
-0+typeof (a) __a = (a); \ +typeof (b) __b = (b); \ +size_t __bytes; \ +bool __overflow; \ + \ +/* we want to perform the wrap-around, but retain the result */ \ + __overflow =__builtin_mul_overflow (sizeof (*(__a)), __b, &__bytes); \ +__builtin_add_overflow ((unsigned long )(__a), __bytes, (unsigned long *)(d)) || \ + __overflow; \ + })So I've tried to wrap my head around all these layers of macros, and it seems ok. However, here I'm a bit worried that there's no type checking of the destination. In particular, the user could perhaps end up doing
Quoted 1 line
check_add_overflow(p, x, p)
I tried to make sure the top-level filtering would require a pointer to an integral type. I'm sure there is a way to foot-gun it, if one tries hard enough. :)
Quoted 8 lines
which will go horribly wrong. Do we have any infrastructure for testing "this should fail to compile"? It would be good to have, not just for this, but in general for checking our sanity checks.
Another thing is that this will always fail with negative offsets (if b has signed type and a negative value, the multiplication won't fit in an unsigned type). I think
__bytesshould beptrdiff_t.
Ew. A negative "add"... yes. I'll take a closer look.
Thanks for the review!
As it turns out, I may not need this patch at all yet, so I may hold off on it until I can prove that we really will need it.
-Kees
Signature · 1 line
Kees Cook