linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [RFC] saturate check_*_overflow() output?
@ 2020-08-03 18:29 Kees Cook
  2020-08-04  6:11 ` Rasmus Villemoes
  0 siblings, 1 reply; 7+ messages in thread
From: Kees Cook @ 2020-08-03 18:29 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Jason Gunthorpe, Leon Romanovsky, Gustavo A. R. Silva,
	Matthew Wilcox, linux-kernel, kernel-hardening

Hi,

I wonder if we should explicitly saturate the output of the overflow
helpers as a side-effect of overflow detection? (That way the output
is never available with a "bad" value, if the caller fails to check the
result or forgets that *d was written...) since right now, *d will hold
the wrapped value.

Also, if we enable arithmetic overflow detection sanitizers, we're going
to trip over the fallback implementation (since it'll wrap and then do
the overflow test in the macro).

e.g. I'm think of something like this (showing only "mul" here, and
untested):

diff --git a/include/linux/overflow.h b/include/linux/overflow.h
index 93fcef105061..00baf3a75dc7 100644
--- a/include/linux/overflow.h
+++ b/include/linux/overflow.h
@@ -71,12 +71,16 @@
 })
 
 #define check_mul_overflow(a, b, d) ({		\
+	bool __result;				\
 	typeof(a) __a = (a);			\
 	typeof(b) __b = (b);			\
 	typeof(d) __d = (d);			\
 	(void) (&__a == &__b);			\
 	(void) (&__a == __d);			\
-	__builtin_mul_overflow(__a, __b, __d);	\
+	__result = __builtin_mul_overflow(__a, __b, __d);\
+	if (unlikely(__result))			\
+		*__d = type_max(__a);		\
+	__result;				\
 })
 
 #else
@@ -105,15 +109,20 @@
  * If one of a or b is a compile-time constant, this avoids a division.
  */
 #define __unsigned_mul_overflow(a, b, d) ({		\
+	bool __result;					\
 	typeof(a) __a = (a);				\
 	typeof(b) __b = (b);				\
 	typeof(d) __d = (d);				\
 	(void) (&__a == &__b);				\
 	(void) (&__a == __d);				\
-	*__d = __a * __b;				\
-	__builtin_constant_p(__b) ?			\
+	__result = __builtin_constant_p(__b) ?		\
 	  __b > 0 && __a > type_max(typeof(__a)) / __b : \
 	  __a > 0 && __b > type_max(typeof(__b)) / __a;	 \
+	if (unlikely(__result))				\
+		*__d = type_max(typeof(__a));		\
+	else						\
+		*__d = __a * __b;			\
+	__result;
 })
 
 /*
@@ -176,6 +185,7 @@
  */
 
 #define __signed_mul_overflow(a, b, d) ({				\
+	bool __result;							\
 	typeof(a) __a = (a);						\
 	typeof(b) __b = (b);						\
 	typeof(d) __d = (d);						\
@@ -183,10 +193,14 @@
 	typeof(a) __tmin = type_min(typeof(a));				\
 	(void) (&__a == &__b);						\
 	(void) (&__a == __d);						\
-	*__d = (u64)__a * (u64)__b;					\
-	(__b > 0   && (__a > __tmax/__b || __a < __tmin/__b)) ||	\
-	(__b < (typeof(__b))-1  && (__a > __tmin/__b || __a < __tmax/__b)) || \
-	(__b == (typeof(__b))-1 && __a == __tmin);			\
+	__result = (__b > 0   && (__a > __tmax/__b || __a < __tmin/__b)) || \
+		   (__b < (typeof(__b))-1  && (__a > __tmin/__b || __a < __tmax/__b)) || \
+		   (__b == (typeof(__b))-1 && __a == __tmin);		\
+	if (unlikely(__result))						\
+		*__d = type_max(__a);					\
+	else								\
+		*__d = (u64)__a * (u64)__b;				\
+	__result;							\
 })
 
 

Thoughts?

-- 
Kees Cook

^ permalink raw reply related	[flat|nested] 7+ messages in thread

* Re: [RFC] saturate check_*_overflow() output?
  2020-08-03 18:29 [RFC] saturate check_*_overflow() output? Kees Cook
@ 2020-08-04  6:11 ` Rasmus Villemoes
  2020-08-04 19:23   ` Kees Cook
  0 siblings, 1 reply; 7+ messages in thread
From: Rasmus Villemoes @ 2020-08-04  6:11 UTC (permalink / raw)
  To: Kees Cook
  Cc: Jason Gunthorpe, Leon Romanovsky, Gustavo A. R. Silva,
	Matthew Wilcox, linux-kernel, kernel-hardening

On 03/08/2020 20.29, Kees Cook wrote:
> Hi,
> 
> I wonder if we should explicitly saturate the output of the overflow
> helpers as a side-effect of overflow detection? 

Please no.

(That way the output
> is never available with a "bad" value, if the caller fails to check the
> result or forgets that *d was written...) since right now, *d will hold
> the wrapped value.

Exactly. I designed the fallback ones so they would have the same
semantics as when using gcc's __builtin_* - though with the "all
operands have same type" restriction, since it would be completely
unwieldy to handle stuff like (s8) + (u64) -> (s32) in macros.

> Also, if we enable arithmetic overflow detection sanitizers, we're going
> to trip over the fallback implementation (since it'll wrap and then do
> the overflow test in the macro).

Huh? The fallback code only ever uses unsigned arithmetic, precisely to
avoid triggering such warnings. Or are you saying there are some
sanitizers out there which also warn for, say, (~0u) + 1u? Yes,
detecting overflow/underflow for a (s32)-(s32)->(s32) without relying on
-fwrapv is a bit messy, but it's done and AFAIK works just fine even
with UBSAN enabled.


What we might do, to deal with the "caller fails to check the result",
is to add a

static inline bool __must_check must_check_overflow(bool b) { return
unlikely(b); }

and wrap all the final "did it overflow" results in that one - perhaps
also for the __builtin_* cases, I don't know if those are automatically
equipped with that attribute. [I also don't know if gcc propagates
likely/unlikely out to the caller, but it shouldn't hurt to have it
there and might improve code gen if it does.]

Rasmus

PS: Another reason not to saturate is that there are two extreme values,
and choosing between them makes the code very messy (especially when
using the __builtins). 5u-10u should saturate to 0u, not UINT_MAX, and
even for for underflowing a signed computation like INT_MIN + (-7); it
makes no sense for that to saturate to INT_MAX.

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] saturate check_*_overflow() output?
  2020-08-04  6:11 ` Rasmus Villemoes
@ 2020-08-04 19:23   ` Kees Cook
  2020-08-04 22:45     ` Matthew Wilcox
  2020-08-05 11:38     ` Rasmus Villemoes
  0 siblings, 2 replies; 7+ messages in thread
From: Kees Cook @ 2020-08-04 19:23 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Jason Gunthorpe, Leon Romanovsky, Gustavo A. R. Silva,
	Matthew Wilcox, linux-kernel, kernel-hardening

On Tue, Aug 04, 2020 at 08:11:45AM +0200, Rasmus Villemoes wrote:
> On 03/08/2020 20.29, Kees Cook wrote:
> > Hi,
> > 
> > I wonder if we should explicitly saturate the output of the overflow
> > helpers as a side-effect of overflow detection? 
> 
> Please no.

I'm entirely on the fence about this, so I'm fine with that answer. (And
I see your PS about why -- thanks!)

> 
> (That way the output
> > is never available with a "bad" value, if the caller fails to check the
> > result or forgets that *d was written...) since right now, *d will hold
> > the wrapped value.
> 
> Exactly. I designed the fallback ones so they would have the same
> semantics as when using gcc's __builtin_* - though with the "all
> operands have same type" restriction, since it would be completely
> unwieldy to handle stuff like (s8) + (u64) -> (s32) in macros.

Right -- a totally sane requirement. :)

> 
> > Also, if we enable arithmetic overflow detection sanitizers, we're going
> > to trip over the fallback implementation (since it'll wrap and then do
> > the overflow test in the macro).
> 
> Huh? The fallback code only ever uses unsigned arithmetic, precisely to
> avoid triggering such warnings. Or are you saying there are some
> sanitizers out there which also warn for, say, (~0u) + 1u? Yes,
> detecting overflow/underflow for a (s32)-(s32)->(s32) without relying on
> -fwrapv is a bit messy, but it's done and AFAIK works just fine even
> with UBSAN enabled.

GCC only has a signed overflow sanitizer. Clang has signed and unsigned.
Dealing with -fwrapv is yet another exercise.

And I can solve this differently, too, with a static inline helper that does
basic mul and carries a no-sanitize attribute.

> What we might do, to deal with the "caller fails to check the result",
> is to add a
> 
> static inline bool __must_check must_check_overflow(bool b) { return
> unlikely(b); }
> 
> and wrap all the final "did it overflow" results in that one - perhaps
> also for the __builtin_* cases, I don't know if those are automatically
> equipped with that attribute. [I also don't know if gcc propagates
> likely/unlikely out to the caller, but it shouldn't hurt to have it
> there and might improve code gen if it does.]

(What is the formal name for the ({ ...; return_value; }) C construct?)

Will that work as a macro return value? If so, that's extremely useful.

> PS: Another reason not to saturate is that there are two extreme values,
> and choosing between them makes the code very messy (especially when
> using the __builtins). 5u-10u should saturate to 0u, not UINT_MAX, and
> even for for underflowing a signed computation like INT_MIN + (-7); it
> makes no sense for that to saturate to INT_MAX.

Ah, gotcha.

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] saturate check_*_overflow() output?
  2020-08-04 19:23   ` Kees Cook
@ 2020-08-04 22:45     ` Matthew Wilcox
  2020-08-05 11:38     ` Rasmus Villemoes
  1 sibling, 0 replies; 7+ messages in thread
From: Matthew Wilcox @ 2020-08-04 22:45 UTC (permalink / raw)
  To: Kees Cook
  Cc: Rasmus Villemoes, Jason Gunthorpe, Leon Romanovsky,
	Gustavo A. R. Silva, linux-kernel, kernel-hardening

On Tue, Aug 04, 2020 at 12:23:03PM -0700, Kees Cook wrote:
> > What we might do, to deal with the "caller fails to check the result",
> > is to add a
> > 
> > static inline bool __must_check must_check_overflow(bool b) { return
> > unlikely(b); }
> > 
> > and wrap all the final "did it overflow" results in that one - perhaps
> > also for the __builtin_* cases, I don't know if those are automatically
> > equipped with that attribute. [I also don't know if gcc propagates
> > likely/unlikely out to the caller, but it shouldn't hurt to have it
> > there and might improve code gen if it does.]
> 
> (What is the formal name for the ({ ...; return_value; }) C construct?)

'Statement Exprs'.

A compound statement enclosed in parentheses may appear as an expression
in GNU C.  This allows you to use loops, switches, and local variables
within an expression.


^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] saturate check_*_overflow() output?
  2020-08-04 19:23   ` Kees Cook
  2020-08-04 22:45     ` Matthew Wilcox
@ 2020-08-05 11:38     ` Rasmus Villemoes
  2020-08-05 20:50       ` Kees Cook
  2020-08-05 23:22       ` Segher Boessenkool
  1 sibling, 2 replies; 7+ messages in thread
From: Rasmus Villemoes @ 2020-08-05 11:38 UTC (permalink / raw)
  To: Kees Cook
  Cc: Jason Gunthorpe, Leon Romanovsky, Gustavo A. R. Silva,
	Matthew Wilcox, linux-kernel, kernel-hardening,
	Segher Boessenkool

On 04/08/2020 21.23, Kees Cook wrote:
> On Tue, Aug 04, 2020 at 08:11:45AM +0200, Rasmus Villemoes wrote:

>> What we might do, to deal with the "caller fails to check the result",
>> is to add a
>>
>> static inline bool __must_check must_check_overflow(bool b) { return
>> unlikely(b); }
>>
>> and wrap all the final "did it overflow" results in that one - perhaps
>> also for the __builtin_* cases, I don't know if those are automatically
>> equipped with that attribute. [I also don't know if gcc propagates
>> likely/unlikely out to the caller, but it shouldn't hurt to have it
>> there and might improve code gen if it does.]
> 
> (What is the formal name for the ({ ...; return_value; }) C construct?)

https://gcc.gnu.org/onlinedocs/gcc/Statement-Exprs.html

> Will that work as a macro return value? If so, that's extremely useful.

Yes and no. Just wrapping the last expression in the statement
expression with my must_check_overflow(), as in

@@ -67,17 +72,18 @@
        typeof(d) __d = (d);                    \
        (void) (&__a == &__b);                  \
        (void) (&__a == __d);                   \
-       __builtin_sub_overflow(__a, __b, __d);  \
+       must_check_overflow(__builtin_sub_overflow(__a, __b, __d));     \
 })

does not appear to work. For some reason, this can't be (ab)used to
overrule the __must_check this simply:

  - kstrtoint(a, b, c);
  + ({ kstrtoint(a, b, c); });

still gives a warning for kstrtoint(). But failing to use the result of
check_sub_overflow() as patched above does not give a warning.

I'm guessing gcc has some internal very early simplification that
replaces single-expression statement-exprs with just that expression,
and the warn-unused-result triggers later. But as soon as the
statement-expr becomes a little non-trivial (e.g. above), my guess is
that the whole thing gets assigned to some internal "variable"
representing the result, and that assignment then counts as a use of the
return value from must_check_overflow() - cc'ing Segher, as he usually
knows these details.

Anyway, we don't need to apply it to the last expression inside ({}), we
can just pass the whole ({}) to must_check_overflow() as in

-#define check_sub_overflow(a, b, d) ({         \
+#define check_sub_overflow(a, b, d) must_check_overflow(({             \
        typeof(a) __a = (a);                    \
        typeof(b) __b = (b);                    \
        typeof(d) __d = (d);                    \
        (void) (&__a == &__b);                  \
        (void) (&__a == __d);                   \
        __builtin_sub_overflow(__a, __b, __d);  \
-})
+}))

and that's even more natural for the fallback cases which would be

 #define check_sub_overflow(a, b, d)                                    \
+       must_check_overflow(                                            \
        __builtin_choose_expr(is_signed_type(typeof(a)),                \
                        __signed_sub_overflow(a, b, d),                 \
-                       __unsigned_sub_overflow(a, b, d))
+                       __unsigned_sub_overflow(a, b, d)))

(in all cases with some whitespace reflowing).

Rasmus

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] saturate check_*_overflow() output?
  2020-08-05 11:38     ` Rasmus Villemoes
@ 2020-08-05 20:50       ` Kees Cook
  2020-08-05 23:22       ` Segher Boessenkool
  1 sibling, 0 replies; 7+ messages in thread
From: Kees Cook @ 2020-08-05 20:50 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Jason Gunthorpe, Leon Romanovsky, Gustavo A. R. Silva,
	Matthew Wilcox, linux-kernel, kernel-hardening,
	Segher Boessenkool

On Wed, Aug 05, 2020 at 01:38:58PM +0200, Rasmus Villemoes wrote:
> Anyway, we don't need to apply it to the last expression inside ({}), we
> can just pass the whole ({}) to must_check_overflow() as in
> 
> -#define check_sub_overflow(a, b, d) ({         \
> +#define check_sub_overflow(a, b, d) must_check_overflow(({             \

Oh! Yes, of course. I was blinded by looking inside the macro and not
wanting to spoil the type magic. Yes, that's perfect. I will spin a
patch...

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [RFC] saturate check_*_overflow() output?
  2020-08-05 11:38     ` Rasmus Villemoes
  2020-08-05 20:50       ` Kees Cook
@ 2020-08-05 23:22       ` Segher Boessenkool
  1 sibling, 0 replies; 7+ messages in thread
From: Segher Boessenkool @ 2020-08-05 23:22 UTC (permalink / raw)
  To: Rasmus Villemoes
  Cc: Kees Cook, Jason Gunthorpe, Leon Romanovsky, Gustavo A. R. Silva,
	Matthew Wilcox, linux-kernel, kernel-hardening

Hi Rasmus,

On Wed, Aug 05, 2020 at 01:38:58PM +0200, Rasmus Villemoes wrote:
> I'm guessing gcc has some internal very early simplification that
> replaces single-expression statement-exprs with just that expression,
> and the warn-unused-result triggers later. But as soon as the
> statement-expr becomes a little non-trivial (e.g. above), my guess is
> that the whole thing gets assigned to some internal "variable"
> representing the result, and that assignment then counts as a use of the
> return value from must_check_overflow() - cc'ing Segher, as he usually
> knows these details.

A statement expression is not a statement (it's an expression), which
turns half of the world upside down.  This GCC extension often has weird
(or at least non-intuitive) side effects, together with other extensions
(like attributes), etc.

This may be a convoluted way of saying "I don't know, look at c/c-decl.c
(and maybe c/c-parser.c) to see if you can find out" ;-)


> Anyway, we don't need to apply it to the last expression inside ({}), we
> can just pass the whole ({}) to must_check_overflow() as in

<snip>

Yes, much nicer :-)  Crisis averted, etc.


Segher

^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2020-08-05 23:22 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-08-03 18:29 [RFC] saturate check_*_overflow() output? Kees Cook
2020-08-04  6:11 ` Rasmus Villemoes
2020-08-04 19:23   ` Kees Cook
2020-08-04 22:45     ` Matthew Wilcox
2020-08-05 11:38     ` Rasmus Villemoes
2020-08-05 20:50       ` Kees Cook
2020-08-05 23:22       ` Segher Boessenkool

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).