Skip to contentSkip to conversation

overflow: Introduce wrapping helpers

PATCH Superseded Kees Cook 2 participants 10 messages Jan 29, 2024

Subsystems (2)

v1 of 7 Superseded Latest is v7 →

lore
Share & tools
lore
author
#1 lore raw

PATCH 1/5 overflow: Adjust check_*_overflow() kern-doc to reflect results

In reply to Kees Cook

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.

Cc "Gustavo A. R. Silva" <[email protected]>
---
 include/linux/overflow.h | 18 ++++++------------
 1 file changed, 6 insertions(+), 12 deletions(-)
include/linux/overflow.h +6 -12
index 7b5cf4a5cd19..4e741ebb8005 100644
@@ -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
author
#3 lore raw

PATCH 3/5 overflow: Introduce add_would_overflow()

In reply to Kees Cook

For 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().

Cc Rasmus Villemoes <[email protected]>
Cc "Gustavo A. R. Silva" <[email protected]>
---
 include/linux/overflow.h | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
include/linux/overflow.h +16 -0
index 210e5602e89b..3c46c648d2e8 100644
@@ -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

Kees Cook

author
#0 lore raw

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
author
#2 lore raw

PATCH 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.

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]>
---
 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
index 6f1ca49306d2..d27b58fddfaa 100644
@@ -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
author
#4 lore raw

PATCH 4/5 overflow: Introduce add_wrap(), sub_wrap(), and mul_wrap()

In reply to 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
Cc Rasmus Villemoes <[email protected]>
Cc Mark Rutland <[email protected]>
---
 include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)
include/linux/overflow.h +54 -0
index 3c46c648d2e8..4f945e9e7881 100644
@@ -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
author
#7 lore raw

PATCH 5/5 overflow: Introduce inc_wrap() and dec_wrap()

In reply to Kees Cook

This 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.

Cc Rasmus Villemoes <[email protected]>
Cc Mark Rutland <[email protected]>
Cc "Gustavo A. R. Silva" <[email protected]>
---
 include/linux/overflow.h | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)
include/linux/overflow.h +32 -0
index 4f945e9e7881..080b18b84498 100644
@@ -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
#5 lore raw

Re: [PATCH 4/5] overflow: Introduce add_wrap(), sub_wrap(), and mul_wrap()

In reply to Kees Cook
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]>
---
 include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)
include/linux/overflow.h +0 -0
index 3c46c648d2e8..4f945e9e7881 100644

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

#8 lore raw

Re: [PATCH 5/5] overflow: Introduce inc_wrap() and dec_wrap()

In reply to Kees Cook
Quoted 18 lines · Kees Cook

This 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.

Cc Rasmus Villemoes <[email protected]>
Cc Mark Rutland <[email protected]>
Cc "Gustavo A. R. Silva" <[email protected]>
---
 include/linux/overflow.h | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)
include/linux/overflow.h +0 -0
index 4f945e9e7881..080b18b84498 100644

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

author
#6 lore raw

Re: [PATCH 4/5] overflow: Introduce add_wrap(), sub_wrap(), and mul_wrap()

In reply to Rasmus Villemoes
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) ==  196

s/add/mul/g I suppose.

Oops, yes.

Quoted 16 lines
Quoted 16 lines
Cc Rasmus Villemoes <[email protected]>
Cc Mark Rutland <[email protected]>
---
 include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)
include/linux/overflow.h +0 -0
index 3c46c648d2e8..4f945e9e7881 100644
@@ -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
author
#9 lore raw

Re: [PATCH 5/5] overflow: Introduce inc_wrap() and dec_wrap()

In reply to Rasmus Villemoes
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() and dec_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]>
---
 include/linux/overflow.h | 32 ++++++++++++++++++++++++++++++++
 1 file changed, 32 insertions(+)
include/linux/overflow.h +0 -0
index 4f945e9e7881..080b18b84498 100644
@@ -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->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

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