LinuxLists.cc - [GIT] Networking

[permalink] [raw]

Subject: Re: [GIT] Networking

On 10/28/2015 02:39 AM, Linus Torvalds wrote:
>
> I'm sorry, but we don't add idiotic new interfaces like this for
> idiotic new code like that.

As one of the people who encouraged gcc to add this interface, I'll
speak up in its favor:

Getting overflow checking right in more complicated cases is a PITA.
I'll admit that the "subtract from an unsigned integer if it won't go
negative" isn't particularly useful, but there are other cases in which
it's much more useful.

The one I care about the most is for multiplication. Witness the
never-ending debates about the proper way to implement things like
kmalloc_array. We currently do:

static inline void *kmalloc_array(size_t n, size_t size, gfp_t flags)
{
if (size != 0 && n > SIZE_MAX / size)
return NULL;
return __kmalloc(n * size, flags);
}

This is correct, and it's even reasonably efficient if size is a
compile-time constant. (On x86, it still might not be quite optimal,
since there'll be an extra cmp instruction. Sure, the difference could
easily be a cycle or even less.)

But if size is not a constant, then, unless the compiler is quite
clever, this ends up generating a division, and that sucks.

If we were willing to do:

size_t total_bytes;
#if efficient_overflow_detection_works
if (__builtin_mul_overflow(n, size, &total_bytes))
return NULL;
#else
/* existing check goes here */
total_bytes = n * size;
#endif
return __kmalloc(n * size, flags);

then we get optimal code generation on new compilers and the result
isn't even that ugly to look at.

For compiler flag settings in which signed overflow can cause subtle
disasters, the signed addition overflow helpers can be nice, too.

--Andy

2015-11-02 21:16:20

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, Nov 2, 2015 at 12:34 PM, Andy Lutomirski <[email protected]> wrote:
> On 10/28/2015 02:39 AM, Linus Torvalds wrote:
>>
>> I'm sorry, but we don't add idiotic new interfaces like this for
>> idiotic new code like that.
>
>
> As one of the people who encouraged gcc to add this interface, I'll speak up
> in its favor:
>
> Getting overflow checking right in more complicated cases is a PITA.

No it is not. Not for unsigned values.

Stop this idiocy. Yes, overflow for signed integers can be complex.
But not for unsigned ones.

And that disgusting "overflow_usub()" in no way makes the code more
readable. EVER.

So stop just making things up. A helper function *could* have been
more legible and more efficient, if it had been about something
completely different.

But in this case it really wasn't. It wasn't more efficient, it wasn't
more legible, and it simply had no excuse for it. Stop making excuses
for shit.

Linus

2015-11-02 21:19:27

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, Nov 2, 2015 at 1:16 PM, Linus Torvalds
<[email protected]> wrote:
> On Mon, Nov 2, 2015 at 12:34 PM, Andy Lutomirski <[email protected]> wrote:
>>
>> Getting overflow checking right in more complicated cases is a PITA.
>
> No it is not. Not for unsigned values.

Just to clarify. The "oevrflow" test for unsigned subtracts of "a-b"
(it's really an underflow, but whatever) really is just

(b > a)

Really. That's it. Claiming that that is "complicated" and needs a
helper function is not something sane people do. A fifth-grader that
isn't good at math can understand that.

In contrast, nobody sane understands "usub_overflow(a, b, &res)".

So really. Stop making inane arguments.

Linus

2015-11-02 21:30:54

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, Nov 2, 2015 at 1:19 PM, Linus Torvalds
<[email protected]> wrote:
> On Mon, Nov 2, 2015 at 1:16 PM, Linus Torvalds
> <[email protected]> wrote:
>> On Mon, Nov 2, 2015 at 12:34 PM, Andy Lutomirski <[email protected]> wrote:
>>>
>>> Getting overflow checking right in more complicated cases is a PITA.
>>
>> No it is not. Not for unsigned values.
>
> Just to clarify. The "oevrflow" test for unsigned subtracts of "a-b"
> (it's really an underflow, but whatever) really is just
>
> (b > a)
>
> Really. That's it. Claiming that that is "complicated" and needs a
> helper function is not something sane people do. A fifth-grader that
> isn't good at math can understand that.
>
> In contrast, nobody sane understands "usub_overflow(a, b, &res)".
>
> So really. Stop making inane arguments.

I'll stop making inane arguments if you stop bashing arguments I
didn't make. :) I said the helpers were useful for multiplication (by
which I meant both signed and unsigned) and, to a lesser extent, for
signed addition and subtraction.

I don't believe I even tried to justify usub_overflow as anything
other than an extremely minor optimization that probably isn't
worthwhile.

--Andy, who still has inline asm that does 'cmovo' and such in his
code for work, sigh.

2015-11-02 22:14:13

[permalink] [raw]

Subject: Re: [GIT] Networking

Hello,

On Mon, Nov 2, 2015, at 22:30, Andy Lutomirski wrote:
> On Mon, Nov 2, 2015 at 1:19 PM, Linus Torvalds
> <[email protected]> wrote:
> > On Mon, Nov 2, 2015 at 1:16 PM, Linus Torvalds
> > <[email protected]> wrote:
> >> On Mon, Nov 2, 2015 at 12:34 PM, Andy Lutomirski <[email protected]> wrote:
> >>>
> >>> Getting overflow checking right in more complicated cases is a PITA.
> >>
> >> No it is not. Not for unsigned values.
> >
> > Just to clarify. The "oevrflow" test for unsigned subtracts of "a-b"
> > (it's really an underflow, but whatever) really is just
> >
> > (b > a)
> >
> > Really. That's it. Claiming that that is "complicated" and needs a
> > helper function is not something sane people do. A fifth-grader that
> > isn't good at math can understand that.
> >
> > In contrast, nobody sane understands "usub_overflow(a, b, &res)".
> >
> > So really. Stop making inane arguments.
>
> I'll stop making inane arguments if you stop bashing arguments I
> didn't make. :) I said the helpers were useful for multiplication (by
> which I meant both signed and unsigned) and, to a lesser extent, for
> signed addition and subtraction.
>
> I don't believe I even tried to justify usub_overflow as anything
> other than an extremely minor optimization that probably isn't
> worthwhile.

overflow_usub was part of a larger header I already prepared to offer
support for *all* overflow_* checking builtins. While fixing this IPv6
bug I thought I could hopefully introduce this interface slowly and
simply cut away the other versions.

The reasoning from my side, while I totally agree that unsigned add/sub
is very easy to test for, is that after using those builtins for a while
I absolutely don't consider them in any way unpleasant to read (but
mainly with signed operations, I have to admit).

They do the one operation and if something overflows or wraps around,
error out and enforce the failure case on the true branch. I simply like
the name 'overflow' (also it could be changed to wraparound in unsigned
operations) in the code. Also chaining multiple operations where each
one could overflow can simply be put into a single if with short-eval
or.

Simply, my point in submitting overflow_usub was to provide all helpers
sometime soon in this way but not submit any without users. I simply was
working down the list.

> --Andy, who still has inline asm that does 'cmovo' and such in his
> code for work, sigh.

In the past I also prepared some inline asm functions with
__builtin_constant_p and inline asm to do those checks but considered
them to complicated for submission. ;)

Linus, I am totally fine with leaving out the usub and uadd operations
but hope you are willing to accept the multiplication and signed add/sub
versions.

Bye,
Hannes

2015-11-02 23:21:50

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, Nov 2, 2015 at 2:14 PM, Hannes Frederic Sowa
<[email protected]> wrote:
>
> overflow_usub was part of a larger header I already prepared to offer
> support for *all* overflow_* checking builtins. While fixing this IPv6
> bug I thought I could hopefully introduce this interface slowly and
> simply cut away the other versions.

Hell no.

Both you and Andy seem to argue that "since there are other totally
unrelated functions that look superficially similar and actually some
sense, we should add these stupid crap functions too".

In exactly *WHAT* crazy universe does that make sense as an argument?

It's like saying "I put literal shit on your plate, because there are
potentially nutritious sausages that look superficially a bit like the
dogshit I served you".

Seriously.

The fact that _valid_ overflow checking functions exist in _no_ way
support the crap that I got.

It's *exactly* the same argument as "dog poop superficially looks like
good sausages".

Is that really your argument?

There is never an excuse for "usub_overflow()". It's that simple.

No amount of _other_ overflow functions make that shit palatable.

Linus

2015-11-03 00:56:51

by Benjamin Herrenschmidt

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, 2015-11-02 at 13:30 -0800, Andy Lutomirski wrote:
>
> I'll stop making inane arguments if you stop bashing arguments I
> didn't make. :) I said the helpers were useful for multiplication (by
> which I meant both signed and unsigned) and, to a lesser extent, for
> signed addition and subtraction.
>
> I don't believe I even tried to justify usub_overflow as anything
> other than an extremely minor optimization that probably isn't
> worthwhile.

Also how much of the problem is simply that the function signature
(naming and choice of arguments) just plain sucks ?

Cheers,
Ben.

2015-11-03 01:55:45

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, Nov 2, 2015 at 4:56 PM, Benjamin Herrenschmidt
<[email protected]> wrote:
>
> Also how much of the problem is simply that the function signature
> (naming and choice of arguments) just plain sucks ?

Some of that is pretty much inevitable.

C really has no good way to return multiple values. The traditional
(pass pointer to fill in result) one simply doesn't result in
good-looking code.

We've occasionally done it by simply breaking C syntax: see "do_div()"
(which returns a value *and* just changes the first argument directly
as a macro). People have tended to absolutely hate it, and while it
can be very practical, it has certainly also resulted in people being
confused. It was originally done for printing numbers, where the whole
"return remainder and divide argument" model was really convenient.

Sometimes we've done it by knowing the value space: the whole "return
error value _or_ a resulting pointer value" by just knowing the
domains (ie "ERR_PTR()" end friends). That tends to work really badly
for arithmetic overflows, though.

And at other times, we've returned structures, which can efficiently
contain two words, and gcc generates reasonable code for.

The *natural* thing to do would actually be to trap and set a flag. We
do that with

put_user_try {
...
} put_user_catch(err);

which sets "err" if one of the "put_user_ex()" or calls in between traps.

The "try/catch" model would probably be the best one syntactically for
overflow handling. It could even be done with macros (ie the "catch"
thing would contain a special overflow label, and the "overflow
functions" would then just jump to that labeln in the error case as a
way to avoid the "return two different values" thing).

Of course, try/catch only really makes sense if you have multiple
operations that can overflow in different parts. That's can be the
pattern in many other cases, but for the kernel it's quite unusual.
It's seldom more than one single operation we need to worry about in
any particular sequence (the "put_user_try/catch" use we have is
exactly because signal handling writes multiple different values to
the same stack when it generates the stack frame).

And with all that said, realistically, in the kernel we seldom have a
ton of complex overflow issues. Most of the values we have are
unsigned, and we have historically just done them manually with

sum = a+b;
if (sum < a)
.. handle error ..

which really doesn't get much better from any syntactic stuff around
it (because any other syntax will involve the whole "how do I return
two values" problem and make it less legible).

Gcc is even smart enough to turn that into a "just check the carry
flag" if the patterns are simple enough, so the simple approach can
even generate optimal code.

The biggest problem - and where the compiler could actually help us -
tends to be multiplication overflows. We have several (not *many*, but
certainly more than just a couple) cases where we simply check by
dividing MAX_INT or something.

See for example kmalloc_array(), which does

if (size != 0 && n > SIZE_MAX / size)
return NULL;

exactly to avoid the overflow when it does the "n*size" allocation.

So for multiplication, we really *could* use overflow logic. It's not
horribly common, but it definitely happens.

Signed integer overflows are annoying even for simple addition and
subtraction, but I can't off-hand recall any real case where that was
even an issue in the kernel.

Linus

2015-11-03 01:58:51

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, Nov 2, 2015 at 5:54 PM, Linus Torvalds
<[email protected]> wrote:
>
> The biggest problem - and where the compiler could actually help us -
> tends to be multiplication overflows. We have several (not *many*, but
> certainly more than just a couple) cases where we simply check by
> dividing MAX_INT or something.
>
> See for example kmalloc_array(), which does
>
> if (size != 0 && n > SIZE_MAX / size)
> return NULL;
>
> exactly to avoid the overflow when it does the "n*size" allocation.
>
> So for multiplication, we really *could* use overflow logic. It's not
> horribly common, but it definitely happens.
>

Based in part on an old patch by Sasha, what if we relied on CSE:

if (mul_would_overflow(size, n))
return NULL;
do_something_with(size * n);

I haven't checked, but it would be sad if gcc couldn't optimize this
correctly if we use the builtins.

The downside is that I don't see off the top of my head how this could
be implemented using inline asm if we want a fast fallback when the
builtins aren't available.

--Andy

2015-11-03 02:38:47

[permalink] [raw]

Subject: Re: [GIT] Networking

On Mon, Nov 2, 2015 at 5:58 PM, Andy Lutomirski <[email protected]> wrote:
>
> Based in part on an old patch by Sasha, what if we relied on CSE:
>
> if (mul_would_overflow(size, n))
> return NULL;
> do_something_with(size * n);

I suspect we wouldn't even have to rely on CSE. Are these things in
performance-critical areas? I suspect our current "use divides" is
actually slower than just using two multiplies, even if one is only
used for overflow checking.

That said, I also think that for something like this, where we
actually have a *reason* for using a special overflow helper function,
we could just try to use the gcc syntax.

I don't think it's wonderful syntax, but at least there's an excuse
for odd/ugly code in those kinds of situations. The reason I hated the
unsigned subtraction case so much was that the simple obvious code
just avoids all those issues entirely, and there wasn't any real
*reason* for the nasty syntax. For multiplication overflow, we'd at
least have a reason.

Sadly, the *nice* syntax, where we'd do something like "goto label"
when the multiply overflows, does not mesh well with inline asm. Yes,
gcc now has "asm goto", but you can't use it with an output value ;(

But from a syntactic standpoint, the best syntax might actually be
something like

mul = multiply_with_overflow(size, n, error_label);
do_something_with(mul);

error_label:
return NULL;

and it would *almost* be possible to do this with inline asm if it
wasn't for the annoying "no output values" case. There are many other
cases where I'd have wanted to do this (ie the whole "fetch value from
user space, but if an exception happens, point the exception handler
at the label).

Back in May, we talked to the gcc people about allowing output values
that are unspecified for the "goto" case (so only a fallthrough would
have them set), but I think that that doesn't match how gcc internally
thinks about branching instructions..

But you could still hide it inside a macro and make it expand to something like

#define multiply_with_overflow(size, n, error_label) ({
unsigned long result, error; \
.. do multiply in asm, set result and error... \
if (error) goto error_label;
result; })

which would allow the above kind of odd hand-coded try/catch model in
C. Which I think would be pretty understandable and not very prone to
getting it wrong. Hmm?

Linus

2015-11-03 12:55:12

[permalink] [raw]

Subject: Re: [GIT] Networking

Hello,

On Tue, Nov 3, 2015, at 03:38, Linus Torvalds wrote:
> On Mon, Nov 2, 2015 at 5:58 PM, Andy Lutomirski <[email protected]>
> wrote:
> >
> > Based in part on an old patch by Sasha, what if we relied on CSE:
> >
> > if (mul_would_overflow(size, n))
> > return NULL;
> > do_something_with(size * n);
>
> I suspect we wouldn't even have to rely on CSE. Are these things in
> performance-critical areas? I suspect our current "use divides" is
> actually slower than just using two multiplies, even if one is only
> used for overflow checking.

And furthermore we don't actually have to rely on CSE if we want to, our
overflow checks could look much more simpler as in "ordinary" C code
because we tell the compiler that signed overflow is defined throughout
the kernel ( -fno-strict-overflow). Thus the checks can be done after
the calculations.

> That said, I also think that for something like this, where we
> actually have a *reason* for using a special overflow helper function,
> we could just try to use the gcc syntax.
>
> I don't think it's wonderful syntax, but at least there's an excuse
> for odd/ugly code in those kinds of situations. The reason I hated the
> unsigned subtraction case so much was that the simple obvious code
> just avoids all those issues entirely, and there wasn't any real
> *reason* for the nasty syntax. For multiplication overflow, we'd at
> least have a reason.
>
> Sadly, the *nice* syntax, where we'd do something like "goto label"
> when the multiply overflows, does not mesh well with inline asm. Yes,
> gcc now has "asm goto", but you can't use it with an output value ;(

I don't understand why you consider inline asm? Those builtins already
normally produce very reasonable code (and yes, I checked). We can wrap
the gcc builtins anyway and adapt the syntax as needed. inline asm does
prohibit constant folding etc, so a __builtin_constant_p check would be
necessary or helpful further adding complexity.

> But from a syntactic standpoint, the best syntax might actually be
> something like
>
> mul = multiply_with_overflow(size, n, error_label);
> do_something_with(mul);
>
> error_label:
> return NULL;
>
> and it would *almost* be possible to do this with inline asm if it
> wasn't for the annoying "no output values" case. There are many other
> cases where I'd have wanted to do this (ie the whole "fetch value from
> user space, but if an exception happens, point the exception handler
> at the label).

I don't see the problem with the

if (multiply_with_overflow(...))
overflowed_handle_error(...);

multiply_with_overflow can have a __must_check attribute, so we see
warnings if return value is not checked immediately.

It allows chaining easily

if (multiply_with_overflow(...) ||
multiply_with_overflow(...))
goto overflow;

without adding checks between the different stages or calculation. It
just composes nicely. The error handling is very explicit.

> Back in May, we talked to the gcc people about allowing output values
> that are unspecified for the "goto" case (so only a fallthrough would
> have them set), but I think that that doesn't match how gcc internally
> thinks about branching instructions..
>
> But you could still hide it inside a macro and make it expand to
> something like
>
> #define multiply_with_overflow(size, n, error_label) ({
> unsigned long result, error; \
> .. do multiply in asm, set result and error... \
> if (error) goto error_label;
> result; })
>
> which would allow the above kind of odd hand-coded try/catch model in
> C. Which I think would be pretty understandable and not very prone to
> getting it wrong. Hmm?

Hiding branches in macros seems not to be a good idea to me at all. I
actually think a lot of users in functions would simply check their
arguments and return -EINVAL in case they overflow. Forcing them to do a
jump seems inappropriate.

I also don't think that reordering the arguments makes a lot of sense:

bool overflow;
int a = multiply_with_overflow(b, c, &overflow);
if (overflow)
error out;

This scheme might be composable if we ||= the overflow flag in the
helper functions/macros and force the user to initialize the overflow
boolean it to false in the beginning. Way too many things that can go
wrong and an auditor has to verify.

Bye,
Hannes

2015-11-03 20:05:42

[permalink] [raw]

Subject: Re: [GIT] Networking

On Tue, Nov 3, 2015 at 4:53 AM, Hannes Frederic Sowa
<[email protected]> wrote:
>
> And furthermore we don't actually have to rely on CSE if we want to, our
> overflow checks could look much more simpler as in "ordinary" C code
> because we tell the compiler that signed overflow is defined throughout
> the kernel ( -fno-strict-overflow). Thus the checks can be done after
> the calculations.

Yes. We could actually do overflow checks by just verifying the
result, even for signed stuff.

> I don't understand why you consider inline asm? Those builtins already
> normally produce very reasonable code

Those built-ins only exist with gcc-5+, afaik.

We'll have people who rely on old versions of gcc for *years* after
gcc5 is commonly available. They'll be running enterprise distros or
debian-stable or things like that.

So we do need to have reasonable backwards compatibility functions.
For things like multiplication overflow, inline asm may be the best
way to do that.

That said, we'll be able to work around it, I'm sure. But no, we're
not going to be in the situation where we just know we can use the
builtins.

> I don't see the problem with the
>
> if (multiply_with_overflow(...))
> overflowed_handle_error(...);

I do agree that it's likely not a big issue.

That said, I may be influenced by hardware design, but I think I'm
also influenced by traditional good C rules: I like functions that
return the *result*, so that the result can be used in a chain of
calculations. Like hardware, the "overflow" bit is separate and I
actually think the gcc overflow functions did the calling convention
wrong.

So even if we do the "pass one of the results by reference" thing, I'd
much rather that "pas by reference" be for the overflow condition.

And hardware that does it well tends to not just give an "overflow"
result, but a "summary overflow", so that you can do multiple
operations in series, and then just check the "summary overflow" at
the end.

So my gut feel is that overflow should either be an exception (ie the
whole "jump to another place" model), or it should be a flag value,
but it shouldn't be the "result" of the function.

For example, one of the overflow issues we've had occasionally has
been not about a single op, but a series of operations:
"multiply-and-add". Look at __timespec64_to_jiffies(), for example,
where the operation that can overflow is "seconds * SEC_CONVERSION +
nsec * NSEC_CONVERSION".

Now, in that case we currently handle the overflow by just knowing
that 'nsec' had better follow certain rules, so we can simply check
seconds against a known maximum, and we don't need to get the "exact"
overflow condition. And quite honestly, that may end up *always* being
the right thing to do - there just isn't any real reason to worry
about individual operations overflowing.

But imagine that we did. The "summary overflow" interface would allow
us to do something like

bool overflow = 0;

result = add_overflow(
mul_overflow(sec, SEC_CONVERSION, &overflow),
mul_overflow(nsec, NSEC_CONVERSION, &overflow),
&overflow);

return overflow ? MAX_JIFFIES : result;

which I'm not at all actually advocating (because (a) I think the
current code is simpler and (b) I don't like the silly
"add_overflow()" anyway), but that I'm giving as an example of why I
think the gcc builtin result passing choice looks a bit odd to me.

> multiply_with_overflow can have a __must_check attribute, so we see
> warnings if return value is not checked immediately.

Yes. There may be advantages to that too. That said, I'm not seeing
that as a big deal. If you use the overflow functions and don't check
the overflow condition, you kind of have bigger issues than "I'd like
to get a compiler warning". That's more of a "WTF is the person doing"
thing).

Linus

2015-11-03 20:44:55

[permalink] [raw]

Subject: Re: [GIT] Networking

On Tue, Nov 3, 2015 at 12:05 PM, Linus Torvalds
<[email protected]> wrote:
> result = add_overflow(
> mul_overflow(sec, SEC_CONVERSION, &overflow),
> mul_overflow(nsec, NSEC_CONVERSION, &overflow),
> &overflow);
>
> return overflow ? MAX_JIFFIES : result;

Thinking more about this example, I think the gcc interface for
multiplication overflow is fine.

It would end up something like

if (mul_overflow(sec, SEC_CONVERSION, &sec))
return MAX_JIFFY_OFFSET;
if (mul_overflow(nsec, NSEC_CONVERSION, &nsec))
return MAX_JIFFY_OFFSET;
sum = sec + nsec;
if (sum < sec || sum > MAX_JIFFY_OFFSET)
return MAX_JIFFY_OFFSET;
return sum;

and that doesn't look horribly ugly to me.

That said, I do wonder how many of our interfaces really want
overflow, and how many just want saturation (or even clamping to a
maximum value).

For example, one of the *common* cases of multiplication overflow we
have had is for memory allocation where we do things like

buffer = kmalloc(sizeof(something) * nr, GFP_KERNEL);

and we've fixed them by moving them to 'kcalloc()'. But as with the
jiffies conversion above, it would actually be sufficient to just
saturate to a maximum value instead, and depending on that causing the
allocation to fail.

So it may actually be that most users really don't even *want* "overflow".

Does anybody have any particular other "uhhuh, overflow in
multiplication" issues in mind? Because the interface for a saturating
multiplication (or addition, for that matter) would actually be much
easier. And would be trivial to have as an inline asm for
compatibility with older versions of gcc too.

Then you could just do that jiffies conversion - or allocation, for
that matter - without any special overflow handling at all. Doing

buf = kmalloc(sat_mul(sizeof(x), nr), GFP_KERNEL);

would just magically work.

And the above jiffies conversion would still want to clamp things to
MAX_JIFFY_OFFSET (because we consider "jiffies" to be an offset from
now, and while it's "unsigned long", we clamp the offset to half the
range), but it would still be a rather natural model for it too.

Linus

2015-11-06 15:28:44

by David Laight

[permalink] [raw]

Subject: RE: [GIT] Networking

> From: Linus Torvalds
> Sent: 03 November 2015 20:45
> On Tue, Nov 3, 2015 at 12:05 PM, Linus Torvalds
> <[email protected]> wrote:
> > result = add_overflow(
> > mul_overflow(sec, SEC_CONVERSION, &overflow),
> > mul_overflow(nsec, NSEC_CONVERSION, &overflow),
> > &overflow);
> >
> > return overflow ? MAX_JIFFIES : result;
>
> Thinking more about this example, I think the gcc interface for
> multiplication overflow is fine.
>
> It would end up something like
>
> if (mul_overflow(sec, SEC_CONVERSION, &sec))
> return MAX_JIFFY_OFFSET;
> if (mul_overflow(nsec, NSEC_CONVERSION, &nsec))
> return MAX_JIFFY_OFFSET;
> sum = sec + nsec;
> if (sum < sec || sum > MAX_JIFFY_OFFSET)
> return MAX_JIFFY_OFFSET;
> return sum;
>
> and that doesn't look horribly ugly to me.

If mul_overflow() is a real function you've just forced some of the
values out to memory, generating a 'clobber' for all memory
(unless 'strict-aliasing' is enabled) and making a mess of other
optimisations.
(If it is a static inline that might not happen.)

If you assume that no one is stupid enough to multiply very large
values by 1 and not get an error you could have mul_overflow()
return the largest prime if the multiply overflowed.

David

????{.n?+???????+%?????ݶ??w??{.n?+????{??G?????{ay?ʇڙ?,j??f???h?????????z_??(?階?ݢj"???m??????G????????????&???~???iO???z??v?^?m????????????I?

2015-11-07 00:49:41

[permalink] [raw]

Subject: Re: [GIT] Networking

On Fri, Nov 6, 2015 at 7:27 AM, David Laight <[email protected]> wrote:
>> From: Linus Torvalds
>> Sent: 03 November 2015 20:45
>> On Tue, Nov 3, 2015 at 12:05 PM, Linus Torvalds
>> <[email protected]> wrote:
>> > result = add_overflow(
>> > mul_overflow(sec, SEC_CONVERSION, &overflow),
>> > mul_overflow(nsec, NSEC_CONVERSION, &overflow),
>> > &overflow);
>> >
>> > return overflow ? MAX_JIFFIES : result;
>>
>> Thinking more about this example, I think the gcc interface for
>> multiplication overflow is fine.
>>
>> It would end up something like
>>
>> if (mul_overflow(sec, SEC_CONVERSION, &sec))
>> return MAX_JIFFY_OFFSET;
>> if (mul_overflow(nsec, NSEC_CONVERSION, &nsec))
>> return MAX_JIFFY_OFFSET;
>> sum = sec + nsec;
>> if (sum < sec || sum > MAX_JIFFY_OFFSET)
>> return MAX_JIFFY_OFFSET;
>> return sum;
>>
>> and that doesn't look horribly ugly to me.
>
> If mul_overflow() is a real function you've just forced some of the
> values out to memory, generating a 'clobber' for all memory
> (unless 'strict-aliasing' is enabled) and making a mess of other
> optimisations.
> (If it is a static inline that might not happen.)

I doubt anyone would ever make it a real function. On new gcc, it
would be an inline backed by an intrinsic. On old gcc it would be a
normal inline or perhaps an inline with inline asm in it.

--Andy

2015-11-09 08:12:27

by Ingo Molnar

[permalink] [raw]

Subject: Re: [GIT] Networking

* Linus Torvalds <[email protected]> wrote:

> Does anybody have any particular other "uhhuh, overflow in multiplication"
> issues in mind? Because the interface for a saturating multiplication (or
> addition, for that matter) would actually be much easier. And would be trivial
> to have as an inline asm for compatibility with older versions of gcc too.
>
> Then you could just do that jiffies conversion - or allocation, for that matter
> - without any special overflow handling at all. Doing
>
> buf = kmalloc(sat_mul(sizeof(x), nr), GFP_KERNEL);
>
> would just magically work.

Exactly: saturation is the default behavior for many GPU vector/pixel attributes
as well, to simplify and speed up the code and the hardware. I always wanted our
ABIs to saturate instead of duplicating complexity with overflow failure logic.

In the kernel the first point of failure is missing overflow checks. The second
point of failure are buggy overflow checks. We can eliminate both if we just use
safe operations that produce output that never exit the valid range. This also
happens to result in the simplest code. We should start thinking of overflow
checks as rootkit enablers.

And note how much this simplifies review and static analysis: if this is the
dominant model used in new kernel code then the analysis (human or machine) would
only have to ensure that no untrusted input values get multiplied (or added) in an
unsafe way. It would not have to be able to understand and track any 'overflow
logic' through a maze of return paths, and validate whether the 'overflow logic'
is correct for all input parameter ranges...

The flip side is marginally less ABI robustness: random input parameters due to
memory corruption will just saturate and produce nonsensical results. I don't
think it's a big issue, and I also think the simplicity of input parameter
validation is _way_ more important than our behavior to random input - but I've
been overruled in the past when trying to introduce saturating ABIs, so saturation
is something people sometimes find inelegant.

Thanks,

Ingo

2015-11-09 10:38:14

[permalink] [raw]

Subject: Re: [GIT] Networking

Hello,

Ingo Molnar <[email protected]> writes:

> * Linus Torvalds <[email protected]> wrote:
>
>> Does anybody have any particular other "uhhuh, overflow in multiplication"
>> issues in mind? Because the interface for a saturating multiplication (or
>> addition, for that matter) would actually be much easier. And would be trivial
>> to have as an inline asm for compatibility with older versions of gcc too.
>>
>> Then you could just do that jiffies conversion - or allocation, for that matter
>> - without any special overflow handling at all. Doing
>>
>> buf = kmalloc(sat_mul(sizeof(x), nr), GFP_KERNEL);
>>
>> would just magically work.
>
> Exactly: saturation is the default behavior for many GPU vector/pixel attributes
> as well, to simplify and speed up the code and the hardware. I always wanted our
> ABIs to saturate instead of duplicating complexity with overflow failure logic.

I don't think saturation arithmetic is useful at all in the kernel as a
replacement for overflow/wrap-around checks. Linus' example has a
discrepancy between what the caller expects and the actual number of
bytes allocated. Imagine sat_mul does the operation in signed char and
kmalloc takes only signed chars as an argument, it could actually be a
huge discrepancy that could lead to security vulnerabilities. The call
should definitely error out here and not try to allocate memory of some
different size and return it to the caller.

> In the kernel the first point of failure is missing overflow checks. The second
> point of failure are buggy overflow checks. We can eliminate both if we just use
> safe operations that produce output that never exit the valid range. This also
> happens to result in the simplest code. We should start thinking of overflow
> checks as rootkit enablers.

Sorry, I don't understand that at all. sat_mul is a rootkit enabler, I
fear. If you allocate a smalelr portion of memory as the caller actually
asked for because of saturation logic, this definitely could lead to
memory corruption and hard to diagnose bugs.

> And note how much this simplifies review and static analysis: if this is the
> dominant model used in new kernel code then the analysis (human or machine) would
> only have to ensure that no untrusted input values get multiplied (or added) in an
> unsafe way. It would not have to be able to understand and track any 'overflow
> logic' through a maze of return paths, and validate whether the 'overflow logic'
> is correct for all input parameter ranges...

Sorry, I don't really understand that proposal. :/

> The flip side is marginally less ABI robustness: random input parameters due to
> memory corruption will just saturate and produce nonsensical results. I don't
> think it's a big issue, and I also think the simplicity of input parameter
> validation is _way_ more important than our behavior to random input - but I've
> been overruled in the past when trying to introduce saturating ABIs, so saturation
> is something people sometimes find inelegant.

If those nonsensical results are memory corruptions I also don't
agree. I think we need to be very much accurate when dealing with
overflows.

Bye,
Hannes

2015-11-09 10:38:30

[permalink] [raw]

Subject: Re: [GIT] Networking

2015-11-09 12:09:28