[PATCH v2 0/5] overflow: Introduce wrapping helpers

[PATCH v2 0/5] overflow: Introduce wrapping helpers

[Kees Cook]

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/20240129182845.work.694-kees@kernel.org/

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

Link: https://github.com/KSPP/linux/issues/26 [1]
Link: https://github.com/KSPP/linux/issues/27 [2]
Link: https://github.com/KSPP/linux/issues/344 [3]
Link: https://git.kernel.org/pub/scm/linux/kernel/git/kees/linux.git/log/?h=devel/overflow/enable-unsigned-sanitizer [4]

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

-- 
2.34.1

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

[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" <gustavoars@kernel.org>
Cc: Justin Stitt <justinstitt@google.com>
Cc: linux-hardening@vger.kernel.org
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 include/linux/overflow.h | 18 ++++++------------
 1 file changed, 6 insertions(+), 12 deletions(-)

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 7b5cf4a5cd19..4e741ebb8005 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -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))
-- 
2.34.1

[PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition

[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 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 <rasmus.villemoes@prevas.dk>
Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Nathan Chancellor <nathan@kernel.org>
Cc: Nick Desaulniers <ndesaulniers@google.com>
Cc: Bill Wendling <morbo@google.com>
Cc: Justin Stitt <justinstitt@google.com>
Cc: llvm@lists.linux.dev
Cc: linux-hardening@vger.kernel.org
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 include/linux/compiler_types.h | 10 +++++
 include/linux/overflow.h       | 44 ++++++++++++++++++-
 lib/overflow_kunit.c           | 77 ++++++++++++++++++++++++++++++----
 3 files changed, 120 insertions(+), 11 deletions(-)

diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h
index 6f1ca49306d2..d27b58fddfaa 100644
--- a/include/linux/compiler_types.h
+++ b/include/linux/compiler_types.h
@@ -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.
diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 4e741ebb8005..210e5602e89b 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -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
diff --git a/lib/overflow_kunit.c b/lib/overflow_kunit.c
index c527f6b75789..2d106e880956 100644
--- a/lib/overflow_kunit.c
+++ b/lib/overflow_kunit.c
@@ -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),
-- 
2.34.1

Re: [PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition

[Rasmus Villemoes]

On 30/01/2024 23.06, Kees Cook wrote:
> 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 <rasmus.villemoes@prevas.dk>
> Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Nathan Chancellor <nathan@kernel.org>
> Cc: Nick Desaulniers <ndesaulniers@google.com>
> Cc: Bill Wendling <morbo@google.com>
> Cc: Justin Stitt <justinstitt@google.com>
> Cc: llvm@lists.linux.dev
> Cc: linux-hardening@vger.kernel.org
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
>  include/linux/compiler_types.h | 10 +++++
>  include/linux/overflow.h       | 44 ++++++++++++++++++-
>  lib/overflow_kunit.c           | 77 ++++++++++++++++++++++++++++++----
>  3 files changed, 120 insertions(+), 11 deletions(-)
> 
> diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h
> index 6f1ca49306d2..d27b58fddfaa 100644
> --- a/include/linux/compiler_types.h
> +++ b/include/linux/compiler_types.h
> @@ -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
> + * @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;				\
> +	})

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

[Kees Cook]

On Wed, Jan 31, 2024 at 09:35:35AM +0100, Rasmus Villemoes wrote:
> On 30/01/2024 23.06, Kees Cook wrote:
> > [...]
> > diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h
> > index 6f1ca49306d2..d27b58fddfaa 100644
> > --- a/include/linux/compiler_types.h
> > +++ b/include/linux/compiler_types.h
> > @@ -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.

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))

> 
> __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;				\
> > +	})
> 
> 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)

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. :)

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

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

-- 
Kees Cook

Re: [PATCH v2 2/5] overflow: Expand check_add_overflow() for pointer addition

[Przemek Kitszel]

On 1/30/24 23:06, Kees Cook wrote:
> 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.

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?

> 
> Additionally update the unit tests to cover pointer addition.
> 
> Cc: Rasmus Villemoes <rasmus.villemoes@prevas.dk>
> Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Nathan Chancellor <nathan@kernel.org>
> Cc: Nick Desaulniers <ndesaulniers@google.com>
> Cc: Bill Wendling <morbo@google.com>
> Cc: Justin Stitt <justinstitt@google.com>
> Cc: llvm@lists.linux.dev
> Cc: linux-hardening@vger.kernel.org
> Signed-off-by: Kees Cook <keescook@chromium.org>
> ---
>   include/linux/compiler_types.h | 10 +++++
>   include/linux/overflow.h       | 44 ++++++++++++++++++-
>   lib/overflow_kunit.c           | 77 ++++++++++++++++++++++++++++++----
>   3 files changed, 120 insertions(+), 11 deletions(-)
> 
> diff --git a/include/linux/compiler_types.h b/include/linux/compiler_types.h
> index 6f1ca49306d2..d27b58fddfaa 100644
> --- a/include/linux/compiler_types.h
> +++ b/include/linux/compiler_types.h
> @@ -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.
> diff --git a/include/linux/overflow.h b/include/linux/overflow.h
> index 4e741ebb8005..210e5602e89b 100644
> --- a/include/linux/overflow.h
> +++ b/include/linux/overflow.h
> @@ -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
> diff --git a/lib/overflow_kunit.c b/lib/overflow_kunit.c
> index c527f6b75789..2d106e880956 100644
> --- a/lib/overflow_kunit.c
> +++ b/lib/overflow_kunit.c
> @@ -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

[Kees Cook]

On Thu, Feb 01, 2024 at 10:19:15AM +0100, Przemek Kitszel wrote:
> On 1/30/24 23:06, Kees Cook wrote:
> > 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.
> 
> 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.

-- 
Kees Cook

[PATCH v2 3/5] overflow: Introduce add_would_overflow()

[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 <rasmus.villemoes@prevas.dk>
Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org>
Cc: Justin Stitt <justinstitt@google.com>
Cc: linux-hardening@vger.kernel.org
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 include/linux/overflow.h | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 210e5602e89b..3c46c648d2e8 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -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
-- 
2.34.1

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

[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:

	mul_wrap(int, 50, 50) == 2500
	mul_wrap(u8,  50, 50) ==  196

Add to the selftests to validate behavior and lack of side-effects.

Cc: Rasmus Villemoes <rasmus.villemoes@prevas.dk>
Cc: Mark Rutland <mark.rutland@arm.com>
Cc: Justin Stitt <justinstitt@google.com>
Cc: linux-hardening@vger.kernel.org
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 include/linux/overflow.h | 54 ++++++++++++++++++++++++++++++++++++++++
 lib/overflow_kunit.c     | 11 ++++++++
 2 files changed, 65 insertions(+)

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 3c46c648d2e8..c9139f88578b 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -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
diff --git a/lib/overflow_kunit.c b/lib/overflow_kunit.c
index 2d106e880956..319f950872bd 100644
--- a/lib/overflow_kunit.c
+++ b/lib/overflow_kunit.c
@@ -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)
 
-- 
2.34.1

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

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

Add to the selftests to validate behavior and lack of side-effects.

Cc: Rasmus Villemoes <rasmus.villemoes@prevas.dk>
Cc: Mark Rutland <mark.rutland@arm.com>
Cc: "Gustavo A. R. Silva" <gustavoars@kernel.org>
Cc: Justin Stitt <justinstitt@google.com>
Cc: linux-hardening@vger.kernel.org
Signed-off-by: Kees Cook <keescook@chromium.org>
---
 include/linux/overflow.h | 28 +++++++++++++++++++++
 lib/overflow_kunit.c     | 54 ++++++++++++++++++++++++++++++++++------
 2 files changed, 75 insertions(+), 7 deletions(-)

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index c9139f88578b..075c30218145 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -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
diff --git a/lib/overflow_kunit.c b/lib/overflow_kunit.c
index 319f950872bd..46af7ccde0c6 100644
--- a/lib/overflow_kunit.c
+++ b/lib/overflow_kunit.c
@@ -265,36 +265,76 @@ DEFINE_TEST_ARRAY(s64) = {
 									\
 	_of = check_ ## op ## _overflow(a, b, &_r);			\
 	KUNIT_EXPECT_EQ_MSG(test, _of, of,				\
-		"expected "fmt" "sym" "fmt" to%s overflow (type %s)\n",	\
+		"expected check "fmt" "sym" "fmt" to%s overflow (type %s)\n",	\
 		a, b, of ? "" : " not", #t);				\
 	KUNIT_EXPECT_TRUE_MSG(test, _r == r,				\
-		"expected "fmt" "sym" "fmt" == "fmt", got "fmt" (type %s)\n", \
+		"expected check "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_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"); \
+	KUNIT_EXPECT_TRUE_MSG(test, _a_orig == _a_bump, "Unexpected check " #op " macro side-effect!\n"); \
+	KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected check " #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", \
+		"expected wrap "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"); \
+	KUNIT_EXPECT_TRUE_MSG(test, _a_orig == _a_bump, "Unexpected wrap " #op " macro side-effect!\n"); \
+	KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected wrap " #op " macro side-effect!\n"); \
+} while (0)
+
+static int global_counter;
+static void bump_counter(void) {
+	global_counter ++;
+}
+
+static int get_index(void) {
+	volatile int index = 0;
+	bump_counter();
+	return index;
+}
+
+#define check_self_op(fmt, op, sym, a, b) do {				\
+	typeof(a + 0) _a = a;						\
+	typeof(b + 0) _b = b;						\
+	typeof(a + 0) _a_sym = a;					\
+	typeof(a + 0) _a_orig[1] = { a };				\
+	typeof(b + 0) _b_orig = b;					\
+	typeof(b + 0) _b_bump = b + 1;					\
+	typeof(a + 0) _r;						\
+									\
+	_a_sym sym _b;							\
+	_r = op ## _wrap(_a, _b);					\
+	KUNIT_EXPECT_TRUE_MSG(test, _r == _a_sym,			\
+		"expected "fmt" "#op" "fmt" == "fmt", got "fmt"\n",	\
+		a, b, _a_sym, _r);					\
+	KUNIT_EXPECT_TRUE_MSG(test, _a == _a_sym,			\
+		"expected "fmt" "#op" "fmt" == "fmt", got "fmt"\n",	\
+		a, b, _a_sym, _a);					\
+	/* Check for internal macro side-effects. */			\
+	global_counter = 0;						\
+	op ## _wrap(_a_orig[get_index()], _b_orig++);			\
+	KUNIT_EXPECT_EQ_MSG(test, global_counter, 1, "Unexpected " #op "_wrap() macro side-effect on arg1!\n"); \
+	KUNIT_EXPECT_TRUE_MSG(test, _b_orig == _b_bump, "Unexpected " #op "_wrap() macro side-effect on arg2!\n"); \
 } while (0)
 
 #define DEFINE_TEST_FUNC_TYPED(n, t, fmt)				\
 static void do_test_ ## n(struct kunit *test, const struct test_ ## n *p) \
 {									\
+	/* check_{add,sub,mul}_overflow() and {add,sub,mul}_wrap() */	\
 	check_one_op(t, fmt, add, "+", p->a, p->b, p->sum, p->s_of);	\
 	check_one_op(t, fmt, add, "+", p->b, p->a, p->sum, p->s_of);	\
 	check_one_op(t, fmt, sub, "-", p->a, p->b, p->diff, p->d_of);	\
 	check_one_op(t, fmt, mul, "*", p->a, p->b, p->prod, p->p_of);	\
 	check_one_op(t, fmt, mul, "*", p->b, p->a, p->prod, p->p_of);	\
+	/* {inc,dec}_wrap() */						\
+	check_self_op(fmt, inc, +=, p->a, p->b);			\
+	check_self_op(fmt, inc, +=, p->b, p->a);			\
+	check_self_op(fmt, dec, -=, p->a, p->b);			\
 }									\
 									\
 static void n ## _overflow_test(struct kunit *test) {			\
-- 
2.34.1