overflow: Introduce wrapping helpers
Subsystems (2)
cover overflow: Introduce wrapping helpers
Hi,
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 | 164 ++++++++++++++++++++++++++++++--- lib/overflow_kunit.c | 77 ++++++++++++++-- 3 files changed, 228 insertions(+), 23 deletions(-)
Signature · 1 line
2.34.1
PATCH 1/5 overflow: Adjust check_*_overflow() kern-doc to reflect results
The 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 2/5 overflow: Expand check_add_overflow() for pointer addition
In reply to Kees CookThe 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 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 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:
add_wrap(int, 50, 50) == 2500 add_wrap(u8, 50, 50) == 196
--- include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 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 to check overflow against +* @a: first addend +* @b: second addend +* +* Return the potentially wrapped-around addition without +* tripping any overflow sanitizers that may be enabled. +*/ +#define add_wrap (type, a, b) \ + ({ \ + type __sum; \ + if (check_add_overflow(a, b, &__sum)) { \ +/* do nothing */ \ + } \ + __sum; \ + }) +/** * 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 to check underflow against +* @a: minuend; value to subtract from +* @b: subtrahend; value to subtract from @a +* +* Return the potentially wrapped-around subtraction without +* tripping any overflow 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 to check underflow against +* @a: first factor +* @b: second factor +* +* Return the potentially wrapped-around multiplication without +* tripping any overflow 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
Signature · 1 line
2.34.1
Re: [PATCH 4/5] overflow: Introduce add_wrap(), sub_wrap(), and mul_wrap()
Quoted 7 lines · Kees Cook
Provide 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:
add_wrap(int, 50, 50) == 2500 add_wrap(u8, 50, 50) == 196
s/add/mul/g I suppose.
Quoted 13 lines
Cc Rasmus Villemoes <[email protected]>Cc Mark Rutland <[email protected]>Signed-off-by Kees Cook <[email protected]>--- include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+)include/linux/overflow.h +0
-0
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 125
Quoted 6 lines
include/linux/overflow.h +3
-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 to check overflow against
Well, nothing is "checked", so why not just say "type of result"?
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 156
Quoted 4 lines
include/linux/overflow.h +3
-0+/** +* sub_wrap() - Intentionally perform a wrapping subtraction +* @type: type to check underflow against
The terminology becomes muddy, is (INT_MAX) - (-1) an underflow or overflow? Anyway, see above.
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 187
Quoted 4 lines
include/linux/overflow.h +3
-0+/** +* mul_wrap() - Intentionally perform a wrapping multiplication +* @type: type to check underflow against
And here there's definitely a copy-pasto.
The code itself looks fine.
Rasmus
Re: [PATCH 4/5] overflow: Introduce add_wrap(), sub_wrap(), and mul_wrap()
Quoted 10 lines · Rasmus Villemoes
Quoted 7 lines · Kees Cook
Provide 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:
add_wrap(int, 50, 50) == 2500 add_wrap(u8, 50, 50) == 196s/add/mul/g I suppose.
Oops, yes.
Quoted 16 lines
Quoted 16 lines
Cc Rasmus Villemoes <[email protected]>Cc Mark Rutland <[email protected]>Signed-off-by Kees Cook <[email protected]>--- include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 54 insertions(+)include/linux/overflow.h +0
-0@@ -120,6 +120,24 @@ static inline bool __must_check __must_check_overflow(bool overflow)check_add_overflow (var, offset, &__result); \ }))
Quoted 5 lines
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 125
Quoted 3 lines
include/linux/overflow.h +3
-0+/** +* add_wrap() - Intentionally perform a wrapping addition +* @type: type to check overflow against Well, nothing is "checked", so why not just say "type of result"?
Yeah, that's better. I was trying to describe that @type will affect the value of the result.
Quoted 6 lines
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 156
Quoted 3 lines
include/linux/overflow.h +3
-0+/** +* sub_wrap() - Intentionally perform a wrapping subtraction +* @type: type to check underflow against The terminology becomes muddy, is (
INT_MAX) - (-1) an underflow or overflow? Anyway, see above.
Right, I should explicitly say "wrap-around".
Quoted 7 lines
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 187
Quoted 5 lines
include/linux/overflow.h +3
-0+/** +* mul_wrap() - Intentionally perform a wrapping multiplication +* @type: type to check underflow against And here there's definitely a copy-pasto.
Ek, yes.
Quoted 1 line
The code itself looks fine.
Thanks!
Signature · 1 line
Kees Cook
PATCH 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.
--- include/linux/overflow.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)
include/linux/overflow.h +32 -0
@@ -138,6 +138,22 @@ static inline bool __must_check __must_check_overflow(bool overflow) __sum; \ }) +/** +* add_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) \ + ({ \ + if (check_add_overflow(var, offset, &var)) { \ +/* do nothing */ \ + } \ + var; \ + }) +/** * check_sub_overflow() - Calculate subtraction with overflow checking * @a: minuend; value to subtract from
@@ -169,6 +185,22 @@ 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) \ + ({ \ + if (check_sub_overflow(var, offset, &var)) { \ +/* do nothing */ \ + } \ + var; \ + }) +/** * check_mul_overflow() - Calculate multiplication with overflow checking * @a: first factor
Signature · 1 line
2.34.1
Re: [PATCH 5/5] overflow: Introduce inc_wrap() and dec_wrap()
Quoted 18 lines · Kees Cook
This allows replacements of the idioms "var += offset" and "var -= offset" with the
inc_wrap()anddec_wrap()helpers respectively. They will avoid wrap-around sanitizer instrumentation.Cc Rasmus Villemoes <[email protected]>Cc Mark Rutland <[email protected]>Cc "Gustavo A. R. Silva" <[email protected]>Signed-off-by Kees Cook <[email protected]>--- include/linux/overflow.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)include/linux/overflow.h +0
-0
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 142
Quoted 5 lines
include/linux/overflow.h +2
-0@@ -138,6 +138,22 @@ static inline bool __must_check __must_check_overflow(bool overflow) __sum; \ }) +/** +* add_wrap() - Intentionally perform a wrapping increment
inc_wrap
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 154
Quoted 12 lines
include/linux/overflow.h +12
-0+* @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) \ + ({ \ + if (check_add_overflow(var, offset, &var)) { \ +/* do nothing */ \ + } \ + var; \
Hm. I wonder if multiple evaluations of var could be a problem. Obviously never if var is actually some automatic variable, nor if it is some simple foo->bar expression. But nothing really prevents var from being, say, foo[gimme_an_index()] or something similarly convoluted.
Does the compiler generate ok code if one does
typeof(var) *__pvar = &(var);
if (check_add_overflow(*__pvar, offset, __pvar)) {}
*__pvar;[in fact, does it even generate code, i.e. does it compile?]
I dunno, maybe it's overkill to worry about.
Rasmus
Re: [PATCH 5/5] overflow: Introduce inc_wrap() and dec_wrap()
Quoted 22 lines · Rasmus Villemoes
Quoted 21 lines · Kees Cook
This allows replacements of the idioms "var += offset" and "var -= offset" with the
inc_wrap()anddec_wrap()helpers respectively. They will avoid wrap-around sanitizer instrumentation.Cc Rasmus Villemoes <[email protected]>Cc Mark Rutland <[email protected]>Cc "Gustavo A. R. Silva" <[email protected]>Signed-off-by Kees Cook <[email protected]>--- include/linux/overflow.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)include/linux/overflow.h +0
-0@@ -138,6 +138,22 @@ static inline bool __must_check __must_check_overflow(bool overflow) __sum; \ })
Quoted 4 lines
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 142
Quoted 2 lines
include/linux/overflow.h +2
-0+/** +* add_wrap() - Intentionally perform a wrapping increment
inc_wrap
Thanks, fixed.
Quoted 15 lines
include/linux/overflow.h static inline bool __must_check __must_check_overflow(bool overflow) · line 154
Quoted 13 lines
include/linux/overflow.h +12
-0+* @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) \ + ({ \ + if (check_add_overflow(var, offset, &var)) { \ +/* do nothing */ \ + } \ + var; \Hm. I wonder if multiple evaluations of var could be a problem.
I am normally defensive about this, but due to @a normally being an lvalue, I lacked the imagination to think of other side-effects, but you've set me straight below.
Quoted 6 lines
Obviously never if var is actually some automatic variable, nor if it is some simple
foo->barexpression. But nothing really prevents var from being, say, foo[gimme_an_index()] or something similarly convoluted.Does the compiler generate ok code if one does
Quoted 7 lines
typeof(var) *__pvar = &(var); if (check_add_overflow(*__pvar, offset, __pvar)) {} *__pvar;[in fact, does it even generate code, i.e. does it compile?]
I dunno, maybe it's overkill to worry about.
Yeah, an index-fetch is a great example that would get lost here. I've updated these to be defined in terms of add/sub_wrap() and to use your pointer typing method to avoid side-effects.
Signature · 1 line
Kees Cook