Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.compilers > #2205 > unrolled thread
| Started by | David Brown <david.brown@hesbynett.no> |
|---|---|
| First post | 2019-04-25 21:58 +0200 |
| Last post | 2019-05-07 16:38 +0200 |
| Articles | 20 on this page of 87 — 14 participants |
Back to article view | Back to comp.compilers
This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by
below is the oldest one visible, not the original post.
Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-25 21:58 +0200
Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-04-26 00:18 +0000
Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-04-28 23:49 +0200
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-04-29 00:31 +0100
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-29 17:08 +0200
Re: Optimization techniques and undefined behavior Christian Gollwitzer <auriocus@gmx.de> - 2019-04-29 18:10 +0200
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-30 14:46 +0200
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-01 13:53 +0100
Re: Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-02 11:29 +0100
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 00:48 +0100
Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-03 10:52 +0100
Re: Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-04 17:44 -0400
Re: Bounds checking, Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-05 17:10 -0400
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-06 08:14 +0200
Re: Optimization techniques and undefined behavior Gene Wirchenko <genew@telus.net> - 2019-05-11 22:25 -0700
Re: not a lot of memory, was Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 12:45 +0100
Re: Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-03 13:29 +0100
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 23:10 +0100
Re: Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-04 10:45 +0100
Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-05 11:14 +0100
Re: Bounds checking, Optimization techniques and undefined behavior Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-05 20:44 +0200
Re: Bounds checking, Optimization techniques and undefined behavior Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-06 10:15 +0200
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 11:04 +0200
Re: Bounds checking, Optimization techniques and undefined behavior "Nuno Lopes" <nuno.lopes@ist.utl.pt> - 2019-05-07 22:38 +0100
Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-08 01:14 +0100
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 09:55 +0200
Re: Bounds checking, Optimization techniques and undefined behavior "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2019-05-08 19:08 +0100
Re: Bounds checking, Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-08 01:42 +0100
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 10:16 +0200
Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-09 01:15 +0100
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-09 21:56 +0200
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 10:03 +0200
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-09 09:19 +0200
Re: Bounds checking, Optimization techniques and undefined behavior Kaz Kylheku <847-115-0292@kylheku.com> - 2019-05-10 03:38 +0000
Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-08 14:37 +0100
Re: Bounds checking, Optimization techniques and undefined behavior Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2019-05-06 05:05 -0400
Re: Bounds checking, Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-05 17:38 -0400
Re: Bounds checking, Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-06 13:07 +0100
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 14:01 +0200
Re: Bounds checking, Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-06 01:15 +0100
Re: Bounds checking, Optimization techniques and undefined behavior Andy Walker <anw@cuboid.co.uk> - 2019-05-06 14:40 +0100
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 15:05 +0200
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-08 10:18 +0200
Re: Bounds checking, Optimization techniques and undefined behavior Jan Ziak <0xe2.0x9a.0x9b@gmail.com> - 2019-05-06 05:39 -0700
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 15:42 +0200
Re: Bounds checking, Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-06 16:32 +0200
Re: Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-04 17:59 -0400
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-02 16:51 +0200
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-02 20:04 +0100
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-03 17:23 +0200
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-03 21:10 +0100
Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-06 13:25 +0100
Re: Optimization techniques and undefined behavior "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2019-05-06 16:32 +0100
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:03 +0200
Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-08 13:16 +0100
Re: Optimization techniques and undefined behavior George Neuner <gneuner2@comcast.net> - 2019-05-08 15:13 -0400
Re: Optimization techniques and undefined behavior "Robin Vowels" <robin51@dodo.com.au> - 2019-05-07 01:22 +1000
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:05 +0200
Re: Optimization techniques and undefined behavior Christian Gollwitzer <auriocus@gmx.de> - 2019-05-02 22:22 +0200
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-04-29 18:15 +0100
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-30 15:48 +0200
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-01 12:40 +0100
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-02 17:27 +0200
Re: Optimization techniques and undefined behavior Bart <bc@freeuk.com> - 2019-05-02 18:59 +0100
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:16 +0200
Re: Optimization techniques and undefined behavior Martin Ward <martin@gkc.org.uk> - 2019-05-02 14:54 +0100
Re: Optimization techniques and runtime checks Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-04-29 22:36 +0200
Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-07 16:29 +0200
Re: Optimization techniques and runtime checks Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-08 02:27 +0200
Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-08 10:31 +0200
Re: Optimization techniques and runtime checks Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2019-05-08 22:50 +0200
Re: Optimization techniques and runtime checks "Robin Vowels" <robin51@dodo.com.au> - 2019-05-11 19:26 +1000
Re: Optimization techniques and runtime checks Gene Wirchenko <genew@telus.net> - 2019-05-11 22:43 -0700
Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-12 20:17 +0200
Re: Optimization techniques and runtime checks Bart <bc@freeuk.com> - 2019-05-08 14:58 +0100
Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-08 23:02 +0200
Re: Optimization techniques and runtime checks Bart <bc@freeuk.com> - 2019-05-09 18:28 +0100
Re: Optimization techniques and runtime checks David Brown <david.brown@hesbynett.no> - 2019-05-09 22:07 +0200
Re: Optimization techniques Gene Wirchenko <genew@telus.net> - 2019-04-30 18:24 -0700
Re: Optimization techniques David Brown <david.brown@hesbynett.no> - 2019-05-01 09:20 +0200
Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-05-02 17:40 +0000
Re: Optimization techniques and error detection Gene Wirchenko <genew@telus.net> - 2019-05-03 10:16 -0700
Re: Optimization techniques "Robin Vowels" <robin51@dodo.com.au> - 2019-05-07 01:42 +1000
Re: Optimization techniques Kaz Kylheku <847-115-0292@kylheku.com> - 2019-04-26 02:26 +0000
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-04-29 00:12 +0200
Re: Optimization techniques and undefined behavior Kaz Kylheku <847-115-0292@kylheku.com> - 2019-05-02 17:18 +0000
Re: Optimization techniques and undefined behavior David Brown <david.brown@hesbynett.no> - 2019-05-07 16:38 +0200
Page 1 of 5 [1] 2 3 4 5 Next page →
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-04-25 21:58 +0200 |
| Subject | Re: Optimization techniques |
| Message-ID | <19-04-021@comp.compilers> |
On 25/04/2019 17:36, Martin Ward wrote:
> David Brown <david.brown@hesbynett.no> wrote:
>> And there are undefined behaviours which could be given definitions, but
>> doing so is not actually a positive thing. The prime example is signed
>> integer overflow. Since overflowing your integers is almost always an
>> error in the code anyway, there are no benefits in giving it defined
>> behaviour.
>
> This is completely backwards. If signed overflow was given a defined
> behaviour (such as the two's complement result), then compilers for
> CPUs which do not implement two's complement operations
> would have to generate less efficient code (but does anyone still
> make such a CPU?).
True - but as you say, such cpus are not realistic.
> Any program which guarantees not to overflow would be unaffected.
Incorrect. Its correctness would be unaffected, but efficiency can be
quite a bit different.
The compiler knows all sorts of things when signed integer arithmetic
does not overflow, and can use this for optimisation.
It knows that "x * 2 / 2" is "x". It knows that "x + 1 > x" is true.
It knows that "for (i = 0; i <= n; i++)" will always end, after n + 1
iterations - after checking for n being <= 0 at the start of the loop.
It knows that adding two non-negative numbers gives a non-negative
number. It knows that abs(x) is not negative. It knows that the
distributive and commutative laws of mathematical integers hold for C
signed integer types. It knows that it can simplify multiplications and
divisions using normal mathematics.
These are significant. With modern compilers doing all sorts of
inlining, function cloning, cross-module optimisation (link-time
optimisation), and with modern C++ code bases using templates, there is
a great deal of scope for this kind of manipulation and optimisation.
People don't write "x * 2 / 2" directly, but after inlining, constant
propagation, constants, macros, etc., these sorts of things turn up.
And knowing that the compiler will sort of the details to get the best
code here, means programmers can concentrate on writing their source in
the clearest and most maintainable manner.
The other big thing about making overflow undefined is that the compiler
and tools can help check for mistakes. Compilers can spot cases where
there are overflows with compile-time constants, and tools like
sanitizers can add run-time checks to help debug code. So when your
program has counted up 2147483647 apples, and you add another one to the
cart, your debugging tools can tell you you have made a mistake. If you
are using wrapping integers, the tools have to believe you meant that
adding another apple gives you -2147483648. Your code has a bug, but
the tools can't help you out.
It is a serious mistake to mix up "defined behaviour" and "correct
behaviour". Only defined behaviour can be correct, but you can't fix
incorrect code by making it defined behaviour.
> Any program which expects a two's complement
> result could now be relied upon to work correctly, and not suddenly
> produce random results when the next version of the compuler comes out!
If your code relies on two's complement wrapping integers, then you need
to use a language or a compiler that guarantees that behaviour.
Standard C doesn't give you that - if your code relies on it, your code
is not correct standard C code. Why should people who know the language
correctly have to pay a price for people who don't know what they are doing?
But in order to be as useful as possible to as many people as possible,
compilers such as gcc and clang offer command-line switches to help
here. If you want to program in a language that is mostly like C except
that signed integer overflow is defined with wrapping semantics, then
these compilers support that language via the "-fwrapv" switch. (Other
compilers may have similar switches - I only mention the ones I know.)
However, if you write your code in not-quite-C, you can't really expect
it to work on a standard C compiler.
It is certainly true that "two's complement wrapping" behaviour will not
turn a correct C program into an incorrect one, as any defined behaviour
satisfies "undefined behaviour" for correctness. But it will reduce the
efficiency of the correct C code, and it will reduce the compiler and
tools' ability to help find bugs. And that is a cost I don't want to pay.
> Any program which expected a different result (one's complement anyone?)
> would need additional code.
Yes, if there are any such systems still in use (I have only heard of one).
>
> With the current situation, anyone wanting to avoid
> undefined behaviour (and don't we all?) has to write code like
> this for any signed operation:
>
> signed int sum;
> if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
> ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
> /* Handle error */
> } else {
> sum = si_a + si_b;
> }
No, they don't.
When I want to add two integers, I usually write "a + b". But then, I
make a point of knowing what my code does, what my values are, what
their ranges are, and I don't write code that might not make sense.
(Barring bugs, of course - I am no more perfect than any other
programmer. That's why I want to give my tools the best chance they
have at helping spot problems.)
It is rare that you do arithmetic on data without any idea of what that
data might be or mean - and thus that you have a solid idea of what
ranges are valid. And when you are working with general functions that
handle raw values without meaning, you punt the problem to the client -
it is perfectly acceptable to write a function "sum" that is defined to
give the correct sum of two ints as long as the result is in the range
of an int - and thus the function has undefined behaviour outside that
range. That's just normal function specification, preconditions and
design by contract - something we all do in all coding, even though not
everyone knows it by name.
Finally, if you have an unusual case where you need to spot and handle
overflow errors, there are many ways to do it. In general it is best to
either be sure that the calculation is valid (such as by using larger
types), or to check ranges in advance, or (for code where efficiency is
more important than portability) use compiler features as necessary to
get the results you need. What you /don't/ do is say "my compiler
should be using two's complement arithmetic on my two's complement cpu.
I don't really care if the result is meaningless - it's defined, and
that's good enough for me".
> See:
>
> https://wiki.sei.cmu.edu/confluence/display/c/INT32-C.+Ensure+that+operations+on+signed+integers+do+not+result+in+overflow
>
>
>> But mathematical identities such as associativity and commutativity are
>> valid because signed integer overflow does not happen - thus "a * (b +
>> c)" can be changed to "(a * b) + (a * c)".
>
> The following slide set discusses some of the problems with undefined
> behaviour starting on slide 43:
>
> http://www0.cs.ucl.ac.uk/staff/B.Karp/3007/s2018/lectures/3007-lecture5-C-arith-undef-behav.pdf
>
>
> Examples of problems include privilege elevation exploits
> and denial of service attacks.
These are just program bugs, because programmers didn't do the right
thing. It happens - few programmers or programs are perfect, totally
regardless of the language and how particular operations are defined.
Some of these examples are obvious, and should never have passed code
review - they demonstrate failures in the development methodology, not
issues with undefined behaviour. You check first, then use the data -
not the other way round. You don't drive your car straight out into a
junction, then check if you hit something and back up - you check first,
then drive when it is safe. You don't dereference a pointer, and then
check if it is valid - you check first.
C is a language for engineers - for people who know what they are doing,
and want top efficiency. If you want a language that holds your hand
and checks everything, giving you polite warnings and exceptions when
there is a problem, then another language would suit you better. (This
is not a condemnation of other languages - I also write a fair bit of
Python, precisely because it manages lots of little things
automatically.) C is designed on the assumption that people know the
language - and C compilers assume that.
Many of the potential problems discussed in that paper can be identified
at compile time by the compiler. That does require that you use a good
compiler (or good static error checker), and that you know how to use
your tools - I don't have much patience for those that refuse to learn
their tools.
I am all in favour of ideas and methods that reduce the risk of bugs in
code. But making signed integer overflow defined as two's complement
would be a step backwards, not a step forwards. The same goes for
limiting optimisations that assume code is correct. Progress will be
made through better education and more awareness of the potential
problems (such as the earlier slides in your link, about the dangers of
mixing signed and unsigned types), through better tools, and through
better defaults for tools. Compilers like gcc can spot a good deal of
the problems discussed - but only if you enable the right warning flags.
I'd prefer lots of warning flags enabled by default, and provide a "I
write very weird code - trust me and turn off the warnings" flag for
those that don't like them.
>
> There was a discussion about undefined behaviour on this list
> in March/April last year. Some examples:
>
> https://blog.regehr.org/archives/213
> https://blog.regehr.org/archives/759
>
I have read a number of John Regehr's articles. He seems to be fond of
publishing unhelpful and condescending criticism.
> Gcc may optimize out tests for buffer overflows
> because of integer overflows:
>
> https://lwn.net/Articles/278137/
>
gcc has removed code that doesn't do anything useful. That is a /good/
thing - and something programmers rely on. Especially with C++
templates, removing dead code is an absolutely essential optimisation.
The trick is to write the tests correctly so that they make sense and do
what you want them to do.
[toc] | [next] | [standalone]
| From | Kaz Kylheku <847-115-0292@kylheku.com> |
|---|---|
| Date | 2019-04-26 00:18 +0000 |
| Message-ID | <19-04-023@comp.compilers> |
| In reply to | #2205 |
On 2019-04-25, David Brown <david.brown@hesbynett.no> wrote:
> On 25/04/2019 17:36, Martin Ward wrote:
>> David Brown <david.brown@hesbynett.no> wrote:
>>> And there are undefined behaviours which could be given definitions, but
>>> doing so is not actually a positive thing. The prime example is signed
>>> integer overflow. Since overflowing your integers is almost always an
>>> error in the code anyway, there are no benefits in giving it defined
>>> behaviour.
>>
>> This is completely backwards. If signed overflow was given a defined
>> behaviour (such as the two's complement result), then compilers for
>> CPUs which do not implement two's complement operations
>> would have to generate less efficient code (but does anyone still
>> make such a CPU?).
>
> True - but as you say, such cpus are not realistic.
>
>> Any program which guarantees not to overflow would be unaffected.
>
> Incorrect. Its correctness would be unaffected, but efficiency can be
> quite a bit different.
>
> The compiler knows all sorts of things when signed integer arithmetic
> does not overflow, and can use this for optimisation.
>
> It knows that "x * 2 / 2" is "x". It knows that "x + 1 > x" is true.
Problem is, all these propositions are not safe; they are based on
"the program has no mistake".
According to the original design of C, the programmer is supposed to
optimize for this kind of thing.
The compiler should only micro-optimize: deal with the code-generation
issues: eliminate wasteful instructions it has introduced itself via
peephole scanning, thread jumps, do some constant folding, unroll loops,
inlining, that sort of thing.
Think about it: why is it okay for assembly language instruction
sets to have defined overflow? Why don't we worry that, "Gee, if
the add instruction has defined overflow, then the assembler
can't deduce that 'cmp r1, r2' which follows it is always false, and
cannot remove that instruction, as well as the whole basic block of code
it controls."
Figuring out that cmp r1, r2 is always false for all the inputs that can
ever occur, and blowing away everything that is behind it, is the
programmer's responsibility.
> It knows that "for (i = 0; i <= n; i++)" will always end, after n + 1
> iterations - after checking for n being <= 0 at the start of the loop.
But the loop will not end if n is INT_MAX. It will predictably not end
if i++ is well-defined behavior, and it is not required to end if i++ is
undefined behavior.
All we usefully know is that, if the loop ends in a well-defined way,
then it must be that n < INT_MAX and, after the loop, i >= n.
We know this regardless of whether i++ is always defined or not.
> These are significant. With modern compilers doing all sorts of
> inlining, function cloning, cross-module optimisation (link-time
> optimisation)
Link-time optimizations can be readily shown to violate the "phases of
translation" abstract model given in the C standard; for that reason,
they are not enabled by default.
In the C language, the translated units of a program that are to be
linked to form the program have undergone semantic analysis.
So no further optimization is permissible; it constitutes semantic
analysis. Translation unit boundaries should be regarded as inviolable
optimization barriers.
>, and with modern C++ code bases using templates, there is
> a great deal of scope for this kind of manipulation and optimisation.
> People don't write "x * 2 / 2" directly, but after inlining, constant
> propagation, constants, macros, etc., these sorts of things turn up.
That's the most dangerous situation to be making these assumptions.
If * 2 came from one macro, and / 2 from another, maybe it wasn't meant
to be optimized.
Programmers who write labyrinths of macros and templates and whatnot in
medium-level languages like C and C++ should be punished by poor
performance.
> The other big thing about making overflow undefined is that the compiler
> and tools can help check for mistakes. Compilers can spot cases where
> there are overflows with compile-time constants, and tools like
> sanitizers can add run-time checks to help debug code.
Run-time checks for overflow can be had even when overflow is
well-defined.
Assembly language instruction sets have well-defined overflow *and*
ways to detect it (flags, exceptions and whatnot).
> So when your
> program has counted up 2147483647 apples, and you add another one to the
> cart, your debugging tools can tell you you have made a mistake. If you
> are using wrapping integers, the tools have to believe you meant that
> adding another apple gives you -2147483648. Your code has a bug, but
> the tools can't help you out.
That is simply false. We can diagnose this situation anyway.
If that results in millions of false positives, then maybe those
developers should rethink their abuse of wrap-around arithmetic.
Tools can provide configurations to deal with floods of false positives.
Diagnostic tools should never be limited to what is defined or undefined
at the language level. They should ideally be customizeable.
Well-defined conditions can be wrong in the given program.
E.g. "I'd like to trap when a value greater than 42 is written into the
variable x, even though it's well-defined to do so."
Just because something is made well-defined in the language doesn't mean
that it's blessed as a recommended practice; it's just "decriminalized".
The purpose of making it well-defined isn't that programmers "go to
town" wrapping 2147483647 to -2147483648 like it's going out of style.
The purpose is mainly to make the software predictable. When this mistake
happens, it will happen in the same way, with consequences deducible
from the abstract language semantics rather than "what version V of
compiler X does on platform Y".
Reproducibility first, then speed.
> It is a serious mistake to mix up "defined behaviour" and "correct
> behaviour". Only defined behaviour can be correct, but you can't fix
> incorrect code by making it defined behaviour.
Of course! Because: incorrect programs can be written in a language in
which no behavior is left undefined at all.
I have bignum integers and rational numbers in Common Lisp, and a great
numeric tower, yet still produce a garbage program where (sin x)
appears where (cos x) ought to have been written, or whatever.
Correct is with respect to the program's specification.
Undefined can be correct. If the program's specification is
"write a C program that dereferences a null pointer",
then something like "*((char *) 0) = 42" might appear in
that program. The program won't be "correct" if we delete that.
In C, "undefined behavior" is a large territory that encompasses
documented extensions.
It only means "not required by the ISO C standard". For instance, using
a platform-specific function is "undefined behavior". However, the
platform supplies a definition of behavior; the program isn't defined by
ISO C, but by the platform, so according to ISO C, it is nevertheless
undefined.
>> With the current situation, anyone wanting to avoid
>> undefined behaviour (and don't we all?) has to write code like
>> this for any signed operation:
>>
>> signed int sum;
>> if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
>> ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
>> /* Handle error */
>> } else {
>> sum = si_a + si_b;
>> }
>
> No, they don't.
>
> When I want to add two integers, I usually write "a + b". But then, I
I certainly have code like that in the implementation of a higher
level language that switches to bignum integers when the operands
oveflow, and so returns the arithmetically correct result under all
conditions, memory permitting.
The overflow check can be expressed more efficiently if we can rely
on wraparound.
A lot of people are doing computing with this sort of system nowadays,
and a lot of them, or portions of their runtimes, are written in C.
--
TXR Programming Lanuage: http://nongnu.org/txr
Music DIY Mailing List: http://www.kylheku.com/diy
ADA MP-1 Mailing List: http://www.kylheku.com/mp1
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-04-28 23:49 +0200 |
| Message-ID | <19-04-037@comp.compilers> |
| In reply to | #2207 |
On 26/04/2019 02:18, Kaz Kylheku wrote:
> On 2019-04-25, David Brown <david.brown@hesbynett.no> wrote:
>> On 25/04/2019 17:36, Martin Ward wrote:
>>> David Brown <david.brown@hesbynett.no> wrote:
>>>> And there are undefined behaviours which could be given definitions, but
>>>> doing so is not actually a positive thing. The prime example is signed
>>>> integer overflow. Since overflowing your integers is almost always an
>>>> error in the code anyway, there are no benefits in giving it defined
>>>> behaviour.
>>>
>>> This is completely backwards. If signed overflow was given a defined
>>> behaviour (such as the two's complement result), then compilers for
>>> CPUs which do not implement two's complement operations
>>> would have to generate less efficient code (but does anyone still
>>> make such a CPU?).
>>
>> True - but as you say, such cpus are not realistic.
>>
>>> Any program which guarantees not to overflow would be unaffected.
>>
>> Incorrect. Its correctness would be unaffected, but efficiency can be
>> quite a bit different.
>>
>> The compiler knows all sorts of things when signed integer arithmetic
>> does not overflow, and can use this for optimisation.
>>
>> It knows that "x * 2 / 2" is "x". It knows that "x + 1 > x" is true.
>
> Problem is, all these propositions are not safe; they are based on
> "the program has no mistake".
/All/ programming is based on the principle of "the program has no
mistake". It is absurd to single out something like this as though it
is a special case.
If I want to double a number, and write "x * 3" by mistake, it is a bug.
If I do arithmetic on signed integers, and they overflow, it is a bug.
The compiler is allowed to assume that when I write "x * 3", I mean
what the C language means - multiply x by 3. It is also allowed to
assume that when I write some signed arithmetic, I mean what the C
language means - give me the correct results when I give valid inputs,
otherwise it is "garbage in, garbage out".
Ask yourself, when would "x * 2 / 2" /not/ be equal to 2, given two's
complement wrapping overflows? It would happen when "x * 2" overflows.
For example (assuming 32-bit ints), take x = 1,500,000,000. When you
write "x * 2 / 2" with an optimising C compiler, the result is most
likely 1,500,000,000 (but there are no guarantees). When you use a
"two's complement signed overflow" compiler, you get -647,483,648. Tell
me, in what world is that a correct answer? Why do you think a
guaranteed wrong and meaningless answer is better than undefined
behaviour? Instead of the compiler generated faster code for valid use,
and debug tools being able to spot your error, you have slower code with
a guaranteed error and no way for tools to help you.
Ask yourself, when would "x + 1 > x" not be true? When x is INT_MAX and
you have wrapping, x + 1 is INT_MIN. Ask yourself, is that the clearest
and best way to check for that condition - rather than writing "x ==
INT_MAX" ? When does it make sense to take a large positive integer,
add 1, and get a large /negative/ integer? It is very rare that this
might be the right answer - occasionally you need wrapping counters,
timers, etc. But generally, it is simply wrong and your code will do
something stupid and unexpected if it happens.
My preference is to write code in a clear and sensible manner, and have
the compiler generate as efficient object code as it can from that
source. I really don't appreciate a compiler that has limited
optimisations just to give the "right" result for smart-arse code
written by someone who thinks it is cool to use obscure expressions
relying on questionable assumptions. (On the other hand, I am glad that
compilers like gcc offer an escape clause like -fwrapv, for people who
have to deal with this kind of code.)
> According to the original design of C, the programmer is supposed to
> optimize for this kind of thing.
Since the first standard, I believe C had the "as if" rule. And the
first standard was written to standardise existing practice. Optimising
compilers are not new.
> The compiler should only micro-optimize: deal with the code-generation
> issues: eliminate wasteful instructions it has introduced itself via
> peephole scanning, thread jumps, do some constant folding, unroll loops,
> inlining, that sort of thing.
I disagree. I have heard this argued many times, and have seen no good
justification for it. At best, any authoritative sources I have seen
mentioned are /old/ - pre-C90, and usually pre-K&R. Perhaps it is not
unreasonable to claim that originally, C compilers could be expected to
be dumb translators - but it is certainly not the case now, and has not
been the case for the last 25-30 years. The time to argue that C
"should" do arithmetic in the manner of the underlying hardware was when
ANSI started working on their standard - it is /way/ too late now.
> Think about it: why is it okay for assembly language instruction
> sets to have defined overflow? Why don't we worry that, "Gee, if
> the add instruction has defined overflow, then the assembler
> can't deduce that 'cmp r1, r2' which follows it is always false, and
> cannot remove that instruction, as well as the whole basic block of code
> it controls."
>
Do you know /why/ signed addition on almost all cpus has wrapping two's
complement semantics? Do you think it is because the cpu designers
thought it would be useful whenever people add two numbers? No. The
primary reason is because it is simpler, cheaper and faster to make it
work that way - much more so than doing something useful for the
programmer, such as saturating or trapping. With a wrapping add, you
can use the same hardware for addition, subtraction, and use the same
instructions for doing multi-precision arithmetic. Wrapping signed
arithmetic for signed integers is not a planned or intentional feature,
it is merely the easiest implementation. (And you need something like
that to get multi-precision arithmetic - a feature mostly obsoleted by
modern cpus.)
Assembly is intended to be a low-level language. Some assemblers do a
little bit of optimisation, but mostly it is a language designed to give
the programmer precise control - and full responsibility - over their
code. C is a high level language - it is not an assembler. It is
defined in terms of its semantics, not the implementation.
> Figuring out that cmp r1, r2 is always false for all the inputs that can
> ever occur, and blowing away everything that is behind it, is the
> programmer's responsibility.
>
Yes. And high-level languages, like C, are designed to relieve the
programmer of such responsibility. (With higher languages taking more
responsibility, and control, away from the programmer.) C is one of the
lowest-level high-level languages, but it is a high-level language.
>> It knows that "for (i = 0; i <= n; i++)" will always end, after n + 1
>> iterations - after checking for n being <= 0 at the start of the loop.
>
> But the loop will not end if n is INT_MAX. It will predictably not end
> if i++ is well-defined behavior, and it is not required to end if i++ is
> undefined behavior.
Read the C standards. It is assumed to end (depending on what is inside
the loop). This is stated clearly and explicitly in the standards -
6.8.5p6, along with footnote 157 saying that the rule is to aid
implementations optimisations.
The authors of the C standards were not stupid. They did not do a
perfect job, of course, but they did rather a good job. They
represented compiler development groups, user groups, programmers,
academics, and other interested parties. They did put emphasis on the
behaviours of existing tools, and even more emphasis on the expected
behaviour of existing code. And they wrote, explicitly, that loops can
be assumed to end if they satisfy certain conditions.
>
> All we usefully know is that, if the loop ends in a well-defined way,
> then it must be that n < INT_MAX and, after the loop, i >= n.
>
Agreed.
> We know this regardless of whether i++ is always defined or not.
>
Agreed.
And if the pre-conditions don't hold, we don't know anything. So if the
loop does not end, or does not end in a well-defined way, we know
nothing about n, i, or anything else.
>> These are significant. With modern compilers doing all sorts of
>> inlining, function cloning, cross-module optimisation (link-time
>> optimisation)
>
> Link-time optimizations can be readily shown to violate the "phases of
> translation" abstract model given in the C standard; for that reason,
> they are not enabled by default.
>
I have not heard that they cause any such trouble. (That doesn't mean
it is not the case - there are many things I have not heard!) The
principle of optimisations is that they do not change the observable
behaviour of correct code, as defined by the C standards, so this would
surprise me. I think it is much more believable that LTO breaks some
more of the invalid assumptions people often make, such as the idea that
calling a function in a different translation unit enforces certain
extra ordering or constraints in the code.
LTO is not enabled by default by most compilers (there are exceptions -
compilers for some small cpus have been using LTO for decades) for three
main reasons. One is that it can significantly increase the compile
times. Another is that it can make debugging very difficult. And it
can be harder to make sure the tools don't remove more code than the
developer wanted, especially if there are more code entry points than
just main(). (Again in the embedded world, this can include interrupt
code.)
> In the C language, the translated units of a program that are to be
> linked to form the program have undergone semantic analysis.
>
> So no further optimization is permissible; it constitutes semantic
> analysis. Translation unit boundaries should be regarded as inviolable
> optimization barriers.
>
Nonsense. There is no basis for that at all - excluding unwarranted
assumptions by many programmers.
>> , and with modern C++ code bases using templates, there is
>> a great deal of scope for this kind of manipulation and optimisation.
>> People don't write "x * 2 / 2" directly, but after inlining, constant
>> propagation, constants, macros, etc., these sorts of things turn up.
>
> That's the most dangerous situation to be making these assumptions.
>
> If * 2 came from one macro, and / 2 from another, maybe it wasn't meant
> to be optimized.
>
If you wanted to write something else in your code, you should have
written it. If your code says "x * 2 / 2" with signed integer x, the
compiler can treat it as "x" (plus the extra knowledge that x can't be
larger than INT_MAX / 2). It doesn't matter how that came about in code
manipulation.
> Programmers who write labyrinths of macros and templates and whatnot in
> medium-level languages like C and C++ should be punished by poor
> performance.
>
Again, nonsense. People who write code in a flexible and maintainable
way, in the knowledge that the compiler will handle details, should get
the best code. People who think their compiler is a dumb translator
should use compiler flags to tell it to be a dumb translator, and let
the rest of us use real tools to do real work.
>> The other big thing about making overflow undefined is that the compiler
>> and tools can help check for mistakes. Compilers can spot cases where
>> there are overflows with compile-time constants, and tools like
>> sanitizers can add run-time checks to help debug code.
>
> Run-time checks for overflow can be had even when overflow is
> well-defined.
>
Fair enough. But it is unlikely that you can conveniently get them
automatically from tools in debug modes, as you can for many types of
invalid or undefined behaviour checks.
> Assembly language instruction sets have well-defined overflow *and*
> ways to detect it (flags, exceptions and whatnot).
>
Some do, yes.
>
>> So when your
>> program has counted up 2147483647 apples, and you add another one to the
>> cart, your debugging tools can tell you you have made a mistake. If you
>> are using wrapping integers, the tools have to believe you meant that
>> adding another apple gives you -2147483648. Your code has a bug, but
>> the tools can't help you out.
>
> That is simply false. We can diagnose this situation anyway.
> If that results in millions of false positives, then maybe those
> developers should rethink their abuse of wrap-around arithmetic.
>
> Tools can provide configurations to deal with floods of false positives.
>
> Diagnostic tools should never be limited to what is defined or undefined
> at the language level. They should ideally be customizeable.
Agreed.
> Well-defined conditions can be wrong in the given program.
> E.g. "I'd like to trap when a value greater than 42 is written into the
> variable x, even though it's well-defined to do so."
>
Sure. But a tool can't apply that sort of check automatically - it
needs a way to know that you consider overflowing from 42 to be an error
at that point in the code. That means manual intervention and code,
such as an "assert". Since the language says that /all/ signed
arithmetic overflows are errors, it's easy for the compiler to add
checks for these without the programmer having to add checks manually.
> Just because something is made well-defined in the language doesn't mean
> that it's blessed as a recommended practice; it's just "decriminalized".
>
Agreed. It's good to hear you say that - many people who argue for
making signed integer overflow defined behaviour seem to think that it
becomes a good idea, because it is defined.
> The purpose of making it well-defined isn't that programmers "go to
> town" wrapping 2147483647 to -2147483648 like it's going out of style.
>
> The purpose is mainly to make the software predictable. When this mistake
> happens, it will happen in the same way, with consequences deducible
> from the abstract language semantics rather than "what version V of
> compiler X does on platform Y".
>
> Reproducibility first, then speed.
>
/Correctness/ first - then speed. Reproducibility of incorrect code
does not matter, except in how it sometimes aids identifying and
correcting bugs. Reproducibility of correct code does not matter
either, except that often there is only one set of correct behaviour.
>> It is a serious mistake to mix up "defined behaviour" and "correct
>> behaviour". Only defined behaviour can be correct, but you can't fix
>> incorrect code by making it defined behaviour.
>
> Of course! Because: incorrect programs can be written in a language in
> which no behavior is left undefined at all.
>
> I have bignum integers and rational numbers in Common Lisp, and a great
> numeric tower, yet still produce a garbage program where (sin x)
> appears where (cos x) ought to have been written, or whatever.
>
> Correct is with respect to the program's specification.
>
Yes.
But how do you know what the program's specification is? The answer is
that it is the source code, interpreted according to the language
definition (augmented by implementation-dependent features, and any
implementation extensions or additional definitions - which may, of
course, include a definition of signed integer overflow behaviour). If
the source code does not make sense according to the language
specification, then the program has no meaningful specification - it is
nonsense code.
This is exactly the same as mathematics. The "square root" function,
for real numbers, is defined for non-negative numbers. If someone asks
you for "sqrt(-4)", then the question is meaningless. Any answer given
can be considered incorrect - equally, any answer given can be
considered correct.
Incorrect inputs to code are as wrong as incorrect code. In C, the
behaviour of signed integer addition is defined for all inputs that
don't overflow - giving it inputs that /do/ overflow is as wrong as
writing multiplication when you meant addition, or passing a negative
number to a square root function.
> Undefined can be correct. If the program's specification is
> "write a C program that dereferences a null pointer",
> then something like "*((char *) 0) = 42" might appear in
> that program. The program won't be "correct" if we delete that.
>
It won't be correct. Undefined behaviour can /never/ be correct. It is
- by definition - meaningless.
There is no way in standard C to write such a program. It could be
written with many C implementations, with the addition of a "volatile",
but not standard C.
<https://www.youtube.com/watch?v=BKorP55Aqvg>
> In C, "undefined behavior" is a large territory that encompasses
> documented extensions.
>
Sure. I have been careful to talk about things being undefined in
standard C, rather than any specific C implementation. For C many
implementations, most things that are undefined by standard C are still
undefined, but sometimes specific points are defined. And sometimes
there are options for defining additional behaviour (I've already
mentioned gcc's -fwrapv flag). There is no problem writing code that
relies on behaviour that is undefined by standard C but defined by the
implementation you are using - as long as you understand the code is not
portable.
It is also fair to say that most real programs depend at least partly on
behaviour defined by an implementation but not by the C standards.
However, if the code's behaviour is not defined by the C standards or
the implementation, then it is not defined behaviour.
> It only means "not required by the ISO C standard". For instance, using
> a platform-specific function is "undefined behavior". However, the
> platform supplies a definition of behavior; the program isn't defined by
> ISO C, but by the platform, so according to ISO C, it is nevertheless
> undefined.
>
>>> With the current situation, anyone wanting to avoid
>>> undefined behaviour (and don't we all?) has to write code like
>>> this for any signed operation:
>>>
>>> signed int sum;
>>> if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
>>> ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
>>> /* Handle error */
>>> } else {
>>> sum = si_a + si_b;
>>> }
>>
>> No, they don't.
>>
>> When I want to add two integers, I usually write "a + b". But then, I
>
> I certainly have code like that in the implementation of a higher
> level language that switches to bignum integers when the operands
> oveflow, and so returns the arithmetically correct result under all
> conditions, memory permitting.
That's fine. Your addition there is defined in a different way from
addition in C.
>
> The overflow check can be expressed more efficiently if we can rely
> on wraparound.
That may or may not be the case - it depends on the target, and
alternative solutions (such as implementation-specific features like
gcc's overflow builtins, or using unsigned integers which /do/ have
defined wrapping).
>
> A lot of people are doing computing with this sort of system nowadays,
> and a lot of them, or portions of their runtimes, are written in C.
>
If you are writing your code in a "C with the extra feature of having
defined behaviour on signed integer overflow", and only compile it with
suitable compilers (or compiler flags), then that's okay. But don't
call it correct C code and blame compilers for your own mistakes or
unwarranted assumptions.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-04-29 00:31 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-04-039@comp.compilers> |
| In reply to | #2221 |
On 28/04/2019 22:49, David Brown wrote:
> On 26/04/2019 02:18, Kaz Kylheku wrote:
>> Problem is, all these propositions are not safe; they are based on
>> "the program has no mistake".
>
>
> /All/ programming is based on the principle of "the program has no
> mistake". It is absurd to single out something like this as though it
> is a special case.
>
> If I want to double a number, and write "x * 3" by mistake, it is a bug.
Yes, a bug that will probably give the wrong answer. But I want a
predictably wrong answer - see below.
> If I do arithmetic on signed integers, and they overflow, it is a bug.
> The compiler is allowed to assume that when I write "x * 3", I mean
> what the C language means - multiply x by 3. It is also allowed to
> assume that when I write some signed arithmetic, I mean what the C
> language means - give me the correct results when I give valid inputs,
> otherwise it is "garbage in, garbage out".
>
> Ask yourself, when would "x * 2 / 2" /not/ be equal to 2, given two's
> complement wrapping overflows? It would happen when "x * 2" overflows.
> For example (assuming 32-bit ints), take x = 1,500,000,000. When you
> write "x * 2 / 2" with an optimising C compiler, the result is most
> likely 1,500,000,000 (but there are no guarantees).
If you write x=(x*2)/2 expecting a result consistent with:
int y=(x*2); x=y/2;
then you don't want the compiler being clever about overflow. If
overflow has occurred, then you want to know about it by it giving a
result consistent with twos complement integer overflow.
You DON'T want the compiler giving you what looks like the right answer
and brushing the overflow under the carpet.
You also want a result that is portable across compilers, but I've just
tried 20 or so combinations of compilers and optimise flags, all give a
result of -647483648 - except gcc which gave 1500000000. And even gcc
gave -647483648 with some versions and some optimisation levels.
-------------------------
#include <stdio.h>
int main(void) {
int x=1500000000;
x=(x*2)/2;
printf("%d\n",x);
}
-------------------------
> When you use a
> "two's complement signed overflow" compiler, you get -647,483,648. Tell
> me, in what world is that a correct answer?
It's not a correct answer when you are trying to do pure arithmetic. It
CAN be correct when doing it via a computer ALU that uses a 32-bit twos
complement binary representation.
It is certainly what you might expect on such hardware.
> Why do you think a guaranteed wrong and meaningless answer is
> better than undefined behaviour?
Is it really meaningless? Try the above using x=x*2. It will still
overflow and produce a result of -1294967296, apparently incorrect. But
print the same bit-pattern using "%u" format, and you get 3000000000 -
the right answer. You can predict what's going to happen, /if/ you can
predict what a compiler is going to do. Unfortunately with ones like
gcc, you can't.
> Ask yourself, when would "x + 1 > x" not be true? When x is INT_MAX and
> you have wrapping, x + 1 is INT_MIN. Ask yourself, is that the clearest
> and best way to check for that condition - rather than writing "x ==
> INT_MAX" ? When does it make sense to take a large positive integer,
> add 1, and get a large /negative/ integer?
You get funny things happening with unsigned integers too; try:
-------------------
#include <stdio.h>
int main(void) {
unsigned int x=1500000000;
x=(x*4)/4;
printf("%u\n",x);
}
-------------------
This displays 426258176 rather than 1500000000.
So why is a 'wrong and meaningless answer' OK, in this case, just
because C deems it to be defined behaviour?
This marginalisation of signed integer overflows is out-dated, now that
every relevant machine is going to behave the same way.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-04-29 17:08 +0200 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-04-042@comp.compilers> |
| In reply to | #2223 |
On 29/04/2019 01:31, Bart wrote:
> On 28/04/2019 22:49, David Brown wrote:
>> On 26/04/2019 02:18, Kaz Kylheku wrote:
>
>>> Problem is, all these propositions are not safe; they are based on
>>> "the program has no mistake".
>>
>>
>> /All/ programming is based on the principle of "the program has no
>> mistake". It is absurd to single out something like this as though it
>> is a special case.
>>
>> If I want to double a number, and write "x * 3" by mistake, it is a bug.
>
> Yes, a bug that will probably give the wrong answer. But I want a
> predictably wrong answer - see below.
>
>
>> If I do arithmetic on signed integers, and they overflow, it is a bug.
>> The compiler is allowed to assume that when I write "x * 3", I mean
>> what the C language means - multiply x by 3. It is also allowed to
>> assume that when I write some signed arithmetic, I mean what the C
>> language means - give me the correct results when I give valid inputs,
>> otherwise it is "garbage in, garbage out".
>>
>> Ask yourself, when would "x * 2 / 2" /not/ be equal to 2, given two's
>> complement wrapping overflows? It would happen when "x * 2" overflows.
>> For example (assuming 32-bit ints), take x = 1,500,000,000. When you
>> write "x * 2 / 2" with an optimising C compiler, the result is most
>> likely 1,500,000,000 (but there are no guarantees).
>
> If you write x=(x*2)/2 expecting a result consistent with:
>
> int y=(x*2); x=y/2;
>
> then you don't want the compiler being clever about overflow.
I /do/ want a result consistent with a single expression, or splitting
up the expression. And I get such a consistent result - whether the
compiler does the "x = y / 2;" operation or just leaves "x" unchanged.
I really do not care what the compiler does about overflow, or how
clever it is (except in the sense that I want it to generate efficient
code). That is because I don't have any overflows.
Questions about what the compiler will do with overflows, like how
consistent it will be, are as sensible as asking how many miles per
gallon you get from your car when it has no tires. You would not drive
your car without tires - that would be a mistake, a bug in your driving
procedure. I don't write signed integer expressions that overflow -
barring bugs in my coding. And thus I don't care what the compiler does
about them, and have no interest in their consistency.
> If overflow has occurred, then you want to know about it by it giving a
> result consistent with twos complement integer overflow.
>
No, I don't - I don't care about consistency here. Any help the
compiler and tools can give me in finding my bugs is great, of course -
but consistency is not a requirement at all. The best thing my compiler
can do is give me a compile-time error - and that is certainly not
consistent with two's complement wrapping. The second best thing it can
do is through a run-time debug error when I have requested such checks -
again, that is not remotely consistent with two's complement wrapping.
At no point can I imagine that wrapping is in any way helpful in finding
bugs.
> You DON'T want the compiler giving you what looks like the right answer
> and brushing the overflow under the carpet.
>
I want the compiler to give me the right answer to valid questions - I
don't expect it to give me any consistent answer to invalid questions.
> You also want a result that is portable across compilers,
I want consistent results to valid inputs - why would I want consistent
or portable results to invalid inputs?
Have you not heard of "garbage in, garbage out" ? Why do you so
desperately want the garbage out to be a particular form of garbage?
> but I've just
> tried 20 or so combinations of compilers and optimise flags, all give a
> result of -647483648 - except gcc which gave 1500000000. And even gcc
> gave -647483648 with some versions and some optimisation levels.
>
Do you understand what "optimising compiler" means? It means the
compiler should try to give you code that runs as efficiently as
possible given valid inputs. C does not impose any requirements on code
efficiency, but compiler users certainly do - so a C compiler is not
going to go out of its way to give poorer quality code. So given "x * 2
/ 2;", a compiler will do one of two things - return "x" unchanged, or
carry out the operations using the most obvious assembly instructions.
A good compiler will thus give you 1500000000 in this case, as that is
the most efficient implementation consistent with the source code. A
weaker compiler, or a compiler without appropriate "optimise well"
options, will give -6474383648. Note, however, that this is just the
result of one operation in isolation. With this code:
void foo(int x) {
if (x < 0) return;
int y = x * 2 / 2;
if (y >= 0) {
printf("y is non-negative, value %i\n", y);
} else {
printf("y is negative, value %i\n", y);
}
}
the result for foo(1500000000) could well be :
y is non-negative, value -6474383648
> -------------------------
> #include <stdio.h>
>
> int main(void) {
> int x=1500000000;
>
> x=(x*2)/2;
>
> printf("%d\n",x);
>
> }
> -------------------------
>
>
>> When you use a
>> "two's complement signed overflow" compiler, you get -647,483,648. Tell
>> me, in what world is that a correct answer?
>
> It's not a correct answer when you are trying to do pure arithmetic. It
> CAN be correct when doing it via a computer ALU that uses a 32-bit twos
> complement binary representation.
It is not a correct answer for standard C signed arithmetic, because
there is no correct answer. It is not a correct answer in normal
mathematics, or almost any real-world problem you might want to model.
It is, however, correct if you have defined your signed arithmetic to be
wrapping. It is fine - but IMHO almost entirely useless and
counter-productive - for a programming language to define signed
arithmetic in that way. C does not define it that way, but other
languages (and particular C compilers) can do so.
>
> It is certainly what you might expect on such hardware.
>
>> Why do you think a guaranteed wrong and meaningless answer is
>> better than undefined behaviour?
>
> Is it really meaningless? Try the above using x=x*2. It will still
> overflow and produce a result of -1294967296, apparently incorrect. But
> print the same bit-pattern using "%u" format, and you get 3000000000 -
> the right answer. You can predict what's going to happen, /if/ you can
> predict what a compiler is going to do. Unfortunately with ones like
> gcc, you can't.
Again, it does not matter if you can predict what value you get if
something is nonsensical. It matters that you can predict what values
are valid inputs, of course, but not what the outputs are when the
inputs are invalid. When garbage goes in, I don't care what colour of
garbage comes out - if I care what is going to come out, I am careful
about what I put in.
If I want to see a result of 3000000000 when viewed as unsigned types,
then I'll use unsigned types in the first place.
>
>> Ask yourself, when would "x + 1 > x" not be true? When x is INT_MAX and
>> you have wrapping, x + 1 is INT_MIN. Ask yourself, is that the clearest
>> and best way to check for that condition - rather than writing "x ==
>> INT_MAX" ? When does it make sense to take a large positive integer,
>> add 1, and get a large /negative/ integer?
>
> You get funny things happening with unsigned integers too; try:
>
> -------------------
> #include <stdio.h>
> int main(void) {
> unsigned int x=1500000000;
>
> x=(x*4)/4;
>
> printf("%u\n",x);
> }
> -------------------
>
> This displays 426258176 rather than 1500000000.
>
Yes, agreed. Unsigned integers don't model mathematical integers, they
model a modulo arithmetic. If you don't think in terms of modulo,
"funny things" happen. If your clock shows half past ten, and you wait
11 hours, it now shows half past nine - funny things have happened.
That is modulo arithmetic for you.
> So why is a 'wrong and meaningless answer' OK, in this case, just
> because C deems it to be defined behaviour?
>
It is not meaningless - precisely because it has a defined behaviour to
give it meaning. It is often an inappropriate result, and a poor model
for real problems - unsigned overflow is often a bug as well. (I have
said before that I'd actually like it to be undefined, but it is
important that the language has some form of wrapping arithmetic to be
used on the few occasions when wrapping is useful.)
> This marginalisation of signed integer overflows is out-dated, now that
> every relevant machine is going to behave the same way.
>
Like many people, you misunderstand. C does not make signed overflow
undefined behaviour because it supports non-two's complement systems.
If that were the case, then it would have made the behaviour
implementation-defined. Signed overflow is /intentionally/ undefined
behaviour because there is no sensible definition to use, and because
there are advantages in optimisation and error checking in leaving it
undefined.
[toc] | [prev] | [next] | [standalone]
| From | Christian Gollwitzer <auriocus@gmx.de> |
|---|---|
| Date | 2019-04-29 18:10 +0200 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-04-044@comp.compilers> |
| In reply to | #2226 |
Am 29.04.19 um 17:08 schrieb David Brown: > I don't write signed integer expressions that overflow - > barring bugs in my coding. And thus I don't care what the compiler does > about them, and have no interest in their consistency. I find this to be a very bold claim. Maybe you write code where such things indeed are no issue, but consider the following, seemingly simple exercise: Write a subroutine which loads a PGM image file and returns a byte buffer (say, std::vector<uint8_t>) containing the data. An 8 bit PGM file is trivial to parse, it looks like basically like this: P5 100 200 255 ..jdk hlhdhqkd.. here comes the binary data The 100 and 200 are the width and height of the image data, the 255 is the highest possible value (for 16 bit it would be different). Obviously, you'd read in the width and height, then multiply them to compute the memory needed for the data, and - oops - how do you make sure that no overflow occurs? In the past, there had been security problems in image libraries with exactly this kind of problem: integer overflow due to unreasonable image sizes. The simplest thing would be to reject any width or height > 100,000, claiming that noone can handle this images, but what about an image of size 200,000 x 3 ? If C++ would provide an easy way to detect / branch on overflow, for example throw an exception, then this could be handled easily. I can't see how you can claim that your code never overflows, unless you don't handle untrusted user input data. Christian
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-04-30 14:46 +0200 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-04-047@comp.compilers> |
| In reply to | #2228 |
On 29/04/2019 18:10, Christian Gollwitzer wrote: > Am 29.04.19 um 17:08 schrieb David Brown: >> I don't write signed integer expressions that overflow - >> barring bugs in my coding. And thus I don't care what the compiler does >> about them, and have no interest in their consistency. > > I find this to be a very bold claim. Maybe you write code where such > things indeed are no issue, but consider the following, seemingly simple > exercise: Write a subroutine which loads a PGM image file and returns a > byte buffer (say, std::vector<uint8_t>) containing the data. An 8 bit > PGM file is trivial to parse, it looks like basically like this: > > P5 > 100 200 > 255 > ..jdk hlhdhqkd.. here comes the binary data > > > The 100 and 200 are the width and height of the image data, the 255 is > the highest possible value (for 16 bit it would be different). > Obviously, you'd read in the width and height, then multiply them to > compute the memory needed for the data, and - oops - how do you make > sure that no overflow occurs? In the past, there had been security > problems in image libraries with exactly this kind of problem: integer > overflow due to unreasonable image sizes. It is really incredibly simple (at least in this case). Do the multiplications using types that won't overflow. That might be an unsigned type if its range is suitable (not because it has defined overflow behaviour, but use it if it has enough range) or a bigger signed integer type. There are plenty of cases where it is difficult to write code that is efficient even on poorer compilers, and correct code so that it works on good compilers. No one claims that programming is always easy. And sometimes the best solution is code that is not portable or correct by the standards, but works well with the implementations you need to use. Most code, after all, is only ever compiled on the one compiler. > The simplest thing would be to reject any width or height > 100,000, > claiming that noone can handle this images, but what about an image of > size 200,000 x 3 ? If C++ would provide an easy way to detect / branch > on overflow, for example throw an exception, then this could be handled > easily. I can't see how you can claim that your code never overflows, > unless you don't handle untrusted user input data. > All C++ compilers with any self-respect support 64-bit integer types. Do you think it's reasonable to reject any image dimension greater than 2,000,000,000 ? I do. I am not saying that "use long long int" is always the answer, of course - nor saying that the answer is always that simple. I am not even saying that portable solutions are always right - sometimes non-portable choices give the best results. But there /is/ always an answer - one that is correct, with defined behaviour (even if it is only defined by the compiler, rather than the standards).
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-05-01 13:53 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-004@comp.compilers> |
| In reply to | #2231 |
On 30/04/2019 13:46, David Brown wrote:
> On 29/04/2019 18:10, Christian Gollwitzer wrote:
>> P5
>> 100 200
>> 255
>> ..jdk hlhdhqkd.. here comes the binary data
>>
>>
>> The 100 and 200 are the width and height of the image data, the 255 is
>> the highest possible value (for 16 bit it would be different).
>> Obviously, you'd read in the width and height, then multiply them to
>> compute the memory needed for the data, and - oops - how do you make
>> sure that no overflow occurs? In the past, there had been security
>> problems in image libraries with exactly this kind of problem: integer
>> overflow due to unreasonable image sizes.
>
> It is really incredibly simple (at least in this case). Do the
> multiplications using types that won't overflow. That might be an
> unsigned type if its range is suitable (not because it has defined
> overflow behaviour, but use it if it has enough range) or a bigger
> signed integer type.
That's just kicking the can further down the road.
If you have two unknown values A and B, and need to multiply, you won't
know if the result will overflow.
Using a type that is double the width might help, unless A and B are
already using the widest type. But if they are int32, and you do the
calculation like this:
(int64)A * (int64)B
then suppose you had to work out A*B*C; do you use:
(int128)*(int64)A * (int64)*B) * (int128)C ?
(Real example: imagebytes := width * height * bytes_per_pixel)
It doesn't really scale. And it doesn't help here:
int32 A, B, C;
C = (int64)A * (int64)B;
as you will need to check the int64 intermediate result for overflow. It
all gets very messy.
I think a lot of this can be handled with application code dealing with
validation; it doesn't really benefit from UB in the language.
In the example posed, you have the additional problem that the input can
be this:
P5
389000000000000000000000000000 9200000000000000000000000000
with both dimensions exceeding int64. You need to get past that first,
and that might indicate some error before you get around to doing any
multiplying.
These are all real, practical problems that are starting to get a long
way from UB in a language.
> There are plenty of cases where it is difficult to write code that is
> efficient even on poorer compilers, and correct code so that it works on
> good compilers. No one claims that programming is always easy. And
> sometimes the best solution is code that is not portable or correct by
> the standards, but works well with the implementations you need to use.
> Most code, after all, is only ever compiled on the one compiler.
>
>
>> The simplest thing would be to reject any width or height > 100,000,
>> claiming that noone can handle this images, but what about an image of
>> size 200,000 x 3 ? If C++ would provide an easy way to detect / branch
>> on overflow, for example throw an exception, then this could be handled
>> easily. I can't see how you can claim that your code never overflows,
>> unless you don't handle untrusted user input data.
>>
> All C++ compilers with any self-respect support 64-bit integer types.
> Do you think it's reasonable to reject any image dimension greater than
> 2,000,000,000 ? I do.
I remember being shown a typesetting machine some decades ago, which
(IIRC) was fed PostScript code and produced an image on film at some
16,000 dpi.
2 billion pixels (or dots) would be only 8 square inches of image. While
A4 scanners working at 9600dpi (1-bit depth) would result in an image of
some 9 billion pixels. So 2 billion pixels is not really that far out of
the ball-park.
[toc] | [prev] | [next] | [standalone]
| From | Andy Walker <anw@cuboid.co.uk> |
|---|---|
| Date | 2019-05-02 11:29 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-006@comp.compilers> |
| In reply to | #2240 |
On 01/05/2019 13:53, Bart wrote:
> If you have two unknown values A and B, and need to multiply, you won't
> know if the result will overflow.
int A := ..., B := ...;
int C := ( A = 0 | 0 |: abs B <= maxint % abs A | A*B | error (...); 0 );
E&OE. Convert to your own favourite language. Simplifies if you
already know that A and B are strictly positive.
Before anyone asks, yes, I know that can throw an unwonted error,
eg if A = -maxint-1 and B = 1; my view is that anyone doing arithmetic
should respect "maxint" and not exploit the vagaries of 2s-complement
arithmetic. If you really want to do that, use "unsigned" [or "bits"]
values properly, rather than "int".
Of course, in the old days, compilers used to build in range
checks on array indices and overflow checks on all arithmetic. A few
still do, esp interpreters, but the God of Speed dictates that most
languages in most circumstances don't. We see the results in the huge
amount of malware that exploits that failure.
[...]
> In the example posed, you have the additional problem that the input can
> be this:
> P5
> 389000000000000000000000000000 9200000000000000000000000000
> with both dimensions exceeding int64.
My own favourite language will throw an "on value error" exception
if you try to read those values [or any other unsuitable strings] into an
integer variable. By default, that will terminate your program with
suitable error messages/diagnostics, but you can substitute your own
"on value error" procedure if you want to print a "Don't be daft, please
type sensible values" message and try again. But it's not hard to write
equivalent code in any half-sensible language by reading that line into
a string and parsing that. If you have a string of digits starting with
a non-zero, and a string corresponding to "maxint", then you have a good
value if either (a) the input string is shorter than that for "maxint" or
(b) it is the same length and alphabetically not larger.
--
Andy Walker,
Nottingham.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-05-03 00:48 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-016@comp.compilers> |
| In reply to | #2242 |
On 02/05/2019 11:29, Andy Walker wrote:
> On 01/05/2019 13:53, Bart wrote:
>> If you have two unknown values A and B, and need to multiply, you won't
>> know if the result will overflow.
>
> int A := ..., B := ...;
> int C := ( A = 0 | 0 |: abs B <= maxint % abs A | A*B | error (...);
> 0 );
That sounds unmanageable (think about checks here: a*a+b*(c*d), and how
you might proceed from the error if not aborting) and inefficient if one
multiply turns into half a dozen operations including a divide.
If such overflow checks need to be routinely done, then it really needs
language support. Otherwise it's probably best handled by a guard
function similar to what someone posted:
if multiply_overflow(a,b) then
print "Overflow"
else
c := a * b # requires that a and b haven't changed
end
This at least isolates the actual expression we want and leaves it readable.
> Of course, in the old days, compilers used to build in range
> checks on array indices and overflow checks on all arithmetic.
Did they? Certainly not any of mine (not really practical on tiny 8-bit
computers on which both the compiler and the program being developed had
to run).
A few
> still do, esp interpreters, but the God of Speed dictates that most
> languages in most circumstances don't. We see the results in the huge
> amount of malware that exploits that failure.
I don't know how much that would help. And I think that if a program can
go seriously wrong through unchecked input, then that's a failure in
proper validation. It's rather sloppy to rely on a runtime check put
their by a compiler.
During development, yes, but perhaps not after a program is supposed to
be working.
(My interpreters (attached to apps) did do a number of runtime checks,
but one difference there is that users could write their own programs.
So that constitutes user input and therefore can't be fully trusted.)
>> In the example posed, you have the additional problem that the input can
>> be this:
>> P5
>> 389000000000000000000000000000 9200000000000000000000000000
>> with both dimensions exceeding int64.
>
> My own favourite language will throw an "on value error" exception
> if you try to read those values [or any other unsuitable strings] into an
> integer variable. By default, that will terminate your program with
> suitable error messages/diagnostics, but you can substitute your own
> "on value error" procedure if you want to print a "Don't be daft, please
> type sensible values" message and try again.
My favourite language would actually return those numbers as a type that
doesn't have any meaningful 'intmax' value:
sreadln(
"389000000000000000000000000000 9200000000000000000000000000")
read a, b
println a, a.type
println b, b.type
Output is:
389000000000000000000000000000 <longint>
9200000000000000000000000000 <longint>
So it gets past that hurdle, but then might be obliged to try creating
an image with 3578800000000000000000000000000000000000000000000000000000
pixels.
(I'm in the process of incorporating such a 'bignum' type into my main
language. It's handy for UI code where performance doesn't matter.)
[There have been plenty of compilers that did bound checking. Back in
the 1960s and 1970s the WATFOR Fortran compilers, originally for the
7040 and later IBM 360/370 and later PDP-11 did bound checking and
also checks for uninitialized variables.
IBM had two PL/I compilers, the checkout compiler that generated
interpreted code with extensive runtime checks and the optimizing
compiler that generated fast machine code. It was possible if painful
to compile part of your program with one and part with the other and
link the code together. Oh, and each compiler ran in 44K bytes of
RAM. Take that, 8-bit micros. -John]
[toc] | [prev] | [next] | [standalone]
| From | Martin Ward <martin@gkc.org.uk> |
|---|---|
| Date | 2019-05-03 10:52 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-017@comp.compilers> |
| In reply to | #2252 |
On 03/05/19 00:48, Bart wrote: > And I think that if a program can > go seriously wrong through unchecked input, then that's a failure in > proper validation. It's rather sloppy to rely on a runtime check put > their by a compiler. The car analogy for C is that C is a car with no seatbelts, crumple zones, roll bars, airbags etc. The car manual explicitly states that nudging the kerb with any tyre is "undefined behaviour" and could cause the car to explode in a fireball, killing all the passengers. On 2019-05-01, David Brown <david.brown@hesbynett.no> wrote: > Detecting signed overflow at run-time can be a significant cost. Firstly: the cost is not as high as the cost of security breaches due to buffer overflows. Secondly: if many popular languages specified suitable handling for signed overflow, buffer overruns and so on, then CPUs hardware would be developed which makes these tests efficient: because compiled code in these popular languages would run faster on such CPUs. > I was talking about a /dimension/ of 2 billion - that is, a width or > height of 2 billion. If you are reading from an unknown file (eg an image on a web page) then it would be foolish to assume that no dimension is bigger that 2 billion: security breaches due to carefully constructed image files have occurred in the past. Also, the netpbm library can be used for files containing data which is *not* image data: for example, as generic utilities for processing huge bit strings. These bit strings might well contain more than 2 billion bits (250 MB of data). Back in the early days of Unix there were many utilities for processing text files. It was discovered that many of these would crash or hang when fed random binary data: https://www.fuzzingbook.org/html/Fuzzer.html ftp://ftp.cs.wisc.edu/paradyn/technical_papers/fuzz-revisited.ps This is a problem because (1) a text utility can be used as a general-purpose data manupulation program which is fed binary data (2) more importantly: each crash is a potential security hole. -- Martin Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4
[toc] | [prev] | [next] | [standalone]
| From | George Neuner <gneuner2@comcast.net> |
|---|---|
| Date | 2019-05-04 17:44 -0400 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-026@comp.compilers> |
| In reply to | #2253 |
On Fri, 3 May 2019 10:52:27 +0100, Martin Ward <martin@gkc.org.uk> wrote: >On 2019-05-01, David Brown <david.brown@hesbynett.no> wrote: >> Detecting signed overflow at run-time can be a significant cost. > >Firstly: the cost is not as high as the cost of security breaches due >to buffer overflows. Exactly. In well written code, often it is possible to amortize up-front limit tests over a substantial block of code. Similar to hoisting common subexpressions. >Secondly: if many popular languages specified >suitable handling for signed overflow, buffer overruns and so on, then >CPUs hardware would be developed which makes these tests efficient: >because compiled code in these popular languages would run faster on >such CPUs. Intel and AMD CPUs have bounds check instructions: but they are cumbersome (similar to using segments), cause exceptions rather than setting flags, and the instructions are relatively slow because few compilers ever used them. George [Are you referring to the old BOUND instruction or the newer MPX feature. -John]
[toc] | [prev] | [next] | [standalone]
| From | George Neuner <gneuner2@comcast.net> |
|---|---|
| Date | 2019-05-05 17:10 -0400 |
| Subject | Re: Bounds checking, Optimization techniques and undefined behavior |
| Message-ID | <19-05-030@comp.compilers> |
| In reply to | #2261 |
>[Are you referring to the old BOUND instruction or the newer MPX feature. -John] Mostly I was referring to the new(ish, Skylake and later) MPX stuff. The larger point is that the architecture had at least some ability to check bounds in hardware for a very long time: BOUND existed at least from i286 onward (if not before). 64-bit mode dropped it, but the need for *something* to do the same job was deemed great enough that the MPX extensions were introduced. The MPX approach is more flexible and faster than BOUND was ... but it still is far too slow for heavy use. IMO it just rehashes many of the old problems that existed with segments: programmer visible registers, too few of them, too complicated setup of data structures in memory, etc. YMMV, George [Bounds checking in the x86 is pretty old. It wasn't in the 8086/88 but it was in the 286. -John]
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2019-05-06 08:14 +0200 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-033@comp.compilers> |
| In reply to | #2253 |
On 03/05/2019 11:52, Martin Ward wrote: > On 03/05/19 00:48, Bart wrote: >> And I think that if a program can >> go seriously wrong through unchecked input, then that's a failure in >> proper validation. It's rather sloppy to rely on a runtime check put >> their by a compiler. > > The car analogy for C is that C is a car with no seatbelts, crumple > zones, roll bars, airbags etc. The car manual explicitly states that > nudging the kerb with any tyre is "undefined behaviour" and could > cause the car to explode in a fireball, killing all the passengers. That is not /quite/ right. The C standards are like laws saying that a car has to have an engine and a number of wheels (but that is up to the manufacturer to decide how many, as long as they tell you). The regulations don't require seatbelts, but you can always make your own - and a manufacturer is free to add any extras they like as long as they don't hinder the basic function of the car. The manufacturer can also change details of how the car works depending on who is driving it, trimming the engine or adding ABS brakes according to preference. > > On 2019-05-01, David Brown <david.brown@hesbynett.no> wrote: >> Detecting signed overflow at run-time can be a significant cost. > > Firstly: the cost is not as high as the cost of security breaches due > to buffer overflows. Apples and oranges. The cost of adding run-time costs can often be significant, and in extreme cases it simply means the code can't be written in that language - C is an appropriate choice of programming language precisely when you want maximal efficiency. And this cost applies even when the programmer knows fine that the operations don't overflow. The consequences of bugs can be severe - of that there is no doubt. But run-time overflow checking does not stop security bugs - it is unlikely to make a significant dent in them. It is clearly absurd to take an example of a security bug (like the libpng one), blame it all on a minor part (the fault was failing to check unknown data, nothing to do with overflows), and then take that as "proof" that run-time overflow checking will solve security problems. Security problems are caused by /bugs/. That can be bugs in the specification of the program, bugs in the design, bugs in the management, just as much as bugs in the coding. Bugs in the coding can come from all sorts of sources. Overflows (whether they are arithmetic overflows, or buffer overflows) are just one of many types of potential bugs. Now, as I have said before, it makes a lot of sense to enable run-time checking while testing and debugging, to find and eliminate as many bugs as possible. That does not mean you want the checks in after you have tested the code - if your testing is good, your development process is good, and your code review process is good, then it is highly unlikely that there are such overflows left in the code. Having run-time checks means bigger and slower code, and lots of code paths that never get tested - which is a really bad idea. And often it would simply be better to use a different language, rather than C. > Secondly: if many popular languages specified > suitable handling for signed overflow, buffer overruns and so on, then > CPUs hardware would be developed which makes these tests efficient: > because compiled code in these popular languages would run faster on > such CPUs. Signed overflow and buffer overflow have little in common, expect coincidental names. You need to consider them separately, unless you are just talking about bugs in general. The inefficiency of signed overflow detection is not a matter of cpu instructions. Quite a few cpus have operations with "trap on overflow" behaviour, or at least a "trap if overflow flag set" operation. The major cost, in many cases, is in how it hinders re-arrangements of expressions, common expression elimination, simplifications, etc. A second case is that it severely limits the use SIMD or vector operations. Another point is that it rarely matches reality. What is so special about 2147483647 that you want to make sure "a + b" does not exceed it? It is more realistic that the limit is something entirely different. Maybe you are talking about percentages, and the limit is 100. When you have realistic requirements based on the code and the problem, rather than arbitrary limits based on some implementation type, you can quickly see that this would be hard to handle in cpu instructions. For buffer overflows, it can be both easier and harder. It is possible to have hardware that attaches a size to a pointer, and does some checking. It would be quite simple to check addressing modes of "base register + index" style, but a lot harder when addresses are pre-computed in other registers. You can do it if you ensure that the logical addresses of data objects are in distinct areas, but that puts a lot of overhead on the OS and memory allocators, and accesses involve a great deal more virtual page lookups. It is used by tools such as valgrind or address sanitizers - tools you want during development and testing to find the bugs, but not to have on released code. There have been many attempts through the ages to add special features in processors to aid security, run-time error checking, supporting checked languages (like Java), etc. Most of them have been failures. You are not the first person to think of this. > >> I was talking about a /dimension/ of 2 billion - that is, a width or >> height of 2 billion. > > If you are reading from an unknown file (eg an image on a web page) > then it would be foolish to assume that no dimension is bigger that 2 > billion: security breaches due to carefully constructed image files > have occurred in the past. You missed my point completely. When I say that the image file should not have a dimension of such ridiculous sizes, I mean you should check the dimensions given by the file, and reject the file as broken if its dimensions exceed such sizes. I repeatedly said you must check the unknown data for sanity. > Also, the netpbm library can be used for > files containing data which is *not* image data: for example, as > generic utilities for processing huge bit strings. These bit strings > might well contain more than 2 billion bits (250 MB of data). > It does not matter - the principle is the same. Check the unknown data for sanity. The sizes of the data will not be so big that you will be overflowing properly chosen types (in C or whatever language you want). You can do these checks safely and without overflows. > Back in the early days of Unix there were many utilities for > processing text files. It was discovered that many of these would > crash or hang when fed random binary data: > > https://www.fuzzingbook.org/html/Fuzzer.html > ftp://ftp.cs.wisc.edu/paradyn/technical_papers/fuzz-revisited.ps > > This is a problem because (1) a text utility can be used as a > general-purpose data manupulation program which is fed binary data (2) > more importantly: each crash is a potential security hole. > People used to be a lot more trusting of unknown data. It is not a good idea, and fortunately many programmers have learnt. Unfortunately, not /all/ programmers have learned. (And also those who have learned, are still fallible humans.)
[toc] | [prev] | [next] | [standalone]
| From | Gene Wirchenko <genew@telus.net> |
|---|---|
| Date | 2019-05-11 22:25 -0700 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-080@comp.compilers> |
| In reply to | #2253 |
On Fri, 3 May 2019 10:52:27 +0100, Martin Ward <martin@gkc.org.uk>
wrote:
>On 03/05/19 00:48, Bart wrote:
>> And I think that if a program can
>> go seriously wrong through unchecked input, then that's a failure in
>> proper validation. It's rather sloppy to rely on a runtime check put
>> their by a compiler.
>
>The car analogy for C is that C is a car with no seatbelts, crumple
>zones, roll bars, airbags etc. The car manual explicitly states that
>nudging the kerb with any tyre is "undefined behaviour" and could
>cause the car to explode in a fireball, killing all the passengers.
Not quite. The manual would end with "undefined behaviour".
Someone bringing up the possibility of a fireball explosion or nasal
demons or whatever would be told that that is merely a quality of
implementation issue.
[snip]
Sincerely,
Gene Wirchenko
[We're getting a bit far from compilers here. -John]
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-05-03 12:45 +0100 |
| Subject | Re: not a lot of memory, was Optimization techniques and undefined behavior |
| Message-ID | <19-05-018@comp.compilers> |
| In reply to | #2252 |
On 03/05/2019 00:48, Bart wrote: > [There have been plenty of compilers that did bound checking. Back in > the 1960s and 1970s the WATFOR Fortran compilers, originally for the > 7040 and later IBM 360/370 and later PDP-11 did bound checking and > also checks for uninitialized variables. > > IBM had two PL/I compilers, the checkout compiler that generated > interpreted code with extensive runtime checks and the optimizing > compiler that generated fast machine code. It was possible if painful > to compile part of your program with one and part with the other and > link the code together. Oh, and each compiler ran in 44K bytes of > RAM. Take that, 8-bit micros. -John] That's a little unfair on 8-bit micros. Those other machines probably had the benefit of better instruction sets and wider register and data sizes. So 44KB could go further. They also probably made use of hard drives, while the 8-bit machines I used had floppy disks a lot of the time, which were too slow to use for things like multi-pass compilers. So more had to be done with a given amount of RAM. Looking up this particular compiler, it seems it was written in assembly language, while the ones I did for Z80, after the first one, were written in their own HLL. But the main pressure was in keeping generated code small, and ensuring it ran fast enough. Adding array bounds and numeric overflow checking wouldn't have helped. I suspect the IBM 360 was also somewhat faster than my 4MHz Z80. [My sources say the checkout compiler was written in PL/S, a PL/I subset IBM used for system programming. The 360 came in different models. The smallest was a 360/30 which you could configure with 64K of disk and a 5MB disk and card reader/punch and printer which I think was enough to run the PL/I compilers. It was really slow. A register-register add took 22us, 16 bit memory-register add 27 us, 32 bit multiply 235us. The 360 instruction set has 32 bit registers but the /30 implemented it in microcode with 8 bit data paths and the "registers" in core. -John]
[toc] | [prev] | [next] | [standalone]
| From | Andy Walker <anw@cuboid.co.uk> |
|---|---|
| Date | 2019-05-03 13:29 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-020@comp.compilers> |
| In reply to | #2252 |
On 03/05/2019 00:48, Bart wrote: >>> If you have two unknown values A and B, and need to multiply, you won't >>> know if the result will overflow. >> int A := ..., B := ...; >> int C := ( A = 0 | 0 |: abs B <= maxint % abs A | A*B | error (...); 0 ); > That sounds unmanageable Indeed, but it was a proof of concept. Obviously, you can tuck that line away either using a macro definition or as a function/operator. > (think about checks here: a*a+b*(c*d), and how > you might proceed from the error if not aborting) and inefficient if one > multiply turns into half a dozen operations including a divide. How quickly do you want your buggy results? If you have to write code to check, then it takes time, both to write and to execute. Yes, if you have a complicated expression, it takes lots of time to execute, and your program will run much more slowly. > If such overflow checks need to be routinely done, then it really needs > language support. If you want to regain efficiency, then it needs not language so much as hardware support. Yes, you then need a language hook into that hardware. Early computers/languages typically had statements something like on overflow goto l arrayboundcheck off to give the programmer fine control over the checks and what to do if the traps were sprung. But it really only works well if the hardware can generate an interrupt. > Otherwise it's probably best handled by a guard > function similar to what someone posted: > if multiply_overflow(a,b) then > print "Overflow" > else > c := a * b # requires that a and b haven't changed > end I would prefer "c := a &* b;" or similar, where "&*" is a "safe multiply" [which you can write yourself in languages that support user- defined operators]. So your example above becomes a &* a &+ b &* (c &* d) You can solve the "abort?" problem by having a procedure that is called when "&*" detects overflow. > This at least isolates the actual expression we want and leaves it readable. Yes, but, in the absence of hardware support, it's not going to be any more efficient than my code [or some near equivalent] above. >> Of course, in the old days, compilers used to build in range >> checks on array indices and overflow checks on all arithmetic. > Did they? Certainly not any of mine (not really practical on tiny 8-bit > computers on which both the compiler and the program being developed had > to run). You're too young. C on a PDP-11/34 running Unix, in the mid-70s, was roughly the 10th serious language and the 5th computer/OS I used over 16 years or so, and the first that did not have array-bound checks and overflow checks compiled in and switched on by default. >> A few >> still do, esp interpreters, but the God of Speed dictates that most >> languages in most circumstances don't. We see the results in the huge >> amount of malware that exploits that failure. > I don't know how much that would help. And I think that if a program can > go seriously wrong through unchecked input, then that's a failure in > proper validation. It's rather sloppy to rely on a runtime check put > their by a compiler. Counsel of perfection. The reality is that every week I get bug fixes to major software on my computer that consists of cures for buffer over-runs, dereferencing null or dangling pointers, overflow conditions, race conditions, storage leakage, .... All of those can be exploited by carefully-crafted malware. All of them, except perhaps some race conditions, can be detected before the exploit by checks put there by a compiler. Most of the checks can be optimised away in well- written code for a decent language. > During development, yes, but perhaps not after a program is supposed to > be working. Dijkstra[?] wrote along the lines of "It's like wearing water wings to paddle around the swimming pool and discarding them when you swim out to sea". [I've looked for the exact quote, but can't find it.] -- Andy Walker, Nottingham.
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-05-03 23:10 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-024@comp.compilers> |
| In reply to | #2255 |
On 03/05/2019 13:29, Andy Walker wrote: > On 03/05/2019 00:48, Bart wrote: >>>> If you have two unknown values A and B, and need to multiply, you won't >>>> know if the result will overflow. >>> int A := ..., B := ...; >>> int C := ( A = 0 | 0 |: abs B <= maxint % abs A | A*B | error >>> (...); 0 ); >> That sounds unmanageable > > Indeed, but it was a proof of concept. Obviously, you can tuck > that line away either using a macro definition or as a function/operator. > >> (think about checks here: a*a+b*(c*d), and how >> you might proceed from the error if not aborting) and inefficient if one >> multiply turns into half a dozen operations including a divide. > > How quickly do you want your buggy results? If you have to write > code to check, then it takes time, both to write and to execute. Yes, if > you have a complicated expression, it takes lots of time to execute, and > your program will run much more slowly. I just haven't found overflow on numbers the huge problem that people say it is. I've spent 10 minutes adding overflow checks (for + - * ops on signed int64) on my latest compiler, and tested a range of applications. Nothing triggered it, except a tiny part of a compiler (some code which had to convert "18446744073709551615" into 64-bit binary), and there it was just because some mixed arithmetic was done as signed rather than signed. In my language, that shouldn't matter, not in that case. And that would have been something that was well tested. The upshot is that no overflows due to logic error were discovered in my brief tests. But you can also see how easy it can be to add such checks. (Although reporting the error location in the program source is a lot harder.) >> If such overflow checks need to be routinely done, then it really needs >> language support. > > If you want to regain efficiency, then it needs not language so > much as hardware support. The overflow check I did above is just one x64 instruction (jo <addr>) after each add, sub or mul. Is that the sort of hardware support you mean? > You're too young. C on a PDP-11/34 running Unix, in the mid-70s, > was roughly the 10th serious language and the 5th computer/OS I used over > 16 years or so, and the first that did not have array-bound checks and > overflow checks compiled in and switched on by default. (I did use the pdp11/34 actually, running Fortran on rsx11m. I have no idea whether that had any such checks. But at least Fortran makes it feasible with well-defined arrays and well-defined array bounds. [I'm pretty sure it didn't. -John] C is just a mess; it has arrays of sorts, but people generally use raw pointers without associated bounds. Maybe that's one reason why your C didn't have it. Or did it somehow manage it if enabled?) >> During development, yes, but perhaps not after a program is supposed to >> be working. > > Dijkstra[?] wrote along the lines of "It's like wearing water > wings to paddle around the swimming pool and discarding them when you > swim out to sea". Swimming out to sea would be foolhardy even wearing a buoyancy aid.
[toc] | [prev] | [next] | [standalone]
| From | Andy Walker <anw@cuboid.co.uk> |
|---|---|
| Date | 2019-05-04 10:45 +0100 |
| Subject | Re: Optimization techniques and undefined behavior |
| Message-ID | <19-05-025@comp.compilers> |
| In reply to | #2259 |
On 03/05/2019 23:10, Bart wrote: > I just haven't found overflow on numbers the huge problem that people > say it is. > I've spent 10 minutes adding overflow checks (for + - * ops on signed > int64) on my latest compiler, and tested a range of applications. > Nothing triggered it, except a tiny part of a compiler [...]. Well, of course it *shouldn't* be triggered at all in tried and tested code. The value comes during development, when the bug is found as it occurs, not when you eventually print some results and they're not what you expect. They're also less likely if 64-bit integers are your default [many of us were brought up on 16- or 32-bit integers] and if your applications are not working out [eg] large combinatorial problems. Not just integer overflow, of course; also floating point. In my days as an astrophysicist, it was easy to generate some very large numbers from things like the mass of a star [in grams], distance to a planet [cms], the speed of light [cm/s], .... We regularly found bugs in the floating-point accumulator, because it hadn't been that well tested with numbers around 10^100 [or 10^-100]. > The overflow check I did above is just one x64 instruction (jo <addr>) > after each add, sub or mul. Is that the sort of hardware support you mean? Well, it's one way, tho' it may be significantly expanding the size of your code and its run time [depending on the application]. The better way, really, is for overflow to "trap", which costs you virtually nothing in either code or execution. If an overflow flag is "persistent" then you may need to clear it before expressions as well as testing it during and after them. [...] > C is just a mess; it has arrays of sorts, but people generally use raw > pointers without associated bounds. Maybe that's one reason why your C > didn't have it. Or did it somehow manage it if enabled? This isn't really a problem with C, the language. It's clear in the reference manual right back to K&R C and in the various standards that pointers always have associated bounds. It's just that the K&R compiler with Unix didn't check, perhaps for decent reasons, and that the relatively few attempts to produce compilers that do have not been all that successful. You can't do the checking unless every pointer "knows" which object it is supposed to be pointing into, which rather implies "fat" pointers, which makes all pointer operations take longer and require more code. It very likely means that arrays too need to be implemented differently, with proper descriptors. As discussed over in "comp.lang.misc" recently, that's not a Bad Thing; it gives you extra facilities virtually free, as well as the added security. But it does result in larger executables and slower execution -- unless you really do have hardware support [cf Burroughs] -- so historically it's not been popular. I no longer recall how tight a squeeze K&R C was on the 11/34; we relatively soon upgraded to an 11/70, with full 64K instruction and 64K data spaces, which would have been ample. -- Andy Walker, Nottingham. [The K&R C compiler fit in about 12K words, but there was a lot of inventive to keep the code small for other reasons. Re hardware bounds checking, take a look at the MPX feature in recent Intel processors which more or less puts fat pointers into hardware. No idea how widely used it is. -John]
[toc] | [prev] | [next] | [standalone]
| From | Bart <bc@freeuk.com> |
|---|---|
| Date | 2019-05-05 11:14 +0100 |
| Subject | Re: Bounds checking, Optimization techniques and undefined behavior |
| Message-ID | <19-05-028@comp.compilers> |
| In reply to | #2260 |
On 04/05/2019 10:45, Andy Walker wrote:
> On 03/05/2019 23:10, Bart wrote:
>> C is just a mess; it has arrays of sorts, but people generally use raw
>> pointers without associated bounds. Maybe that's one reason why your C
>> didn't have it. Or did it somehow manage it if enabled?
>
> This isn't really a problem with C, the language. It's clear in
> the reference manual right back to K&R C and in the various standards
> that pointers always have associated bounds.
But how do they get there? Take this:
int A[10], *p;
p = &A[3];
You intend p to refer to the 4-element slice A[3..6], but how does the
language know that? How can it stop code from writing to p[5]?
Or you intend to index p[-2] to get at the preceding elements. Actually
using negative indexing is quite common, but surely all array bounds in
C are presumed to start from 0?
Or this:
struct {int a,b,c,d;} S;
p = &S.a;
You intend p to be used to access a,b,c,d as an int[4] array, but p's
bounds will say it's only one element long.
Or this:
int *p = malloc(sizeof(int)*1000);
int *q = p+400;
You are allocating one pool of memory than sub-allocating that into
smaller objects, here into a 20-element array headed by q. But how does
the language know that?
Or maybe p allocates memory for a 2D array, and q refers to one row of
that; you can't detect accesses beyond that row.
I can see how the language can figure out the overall bounds of the
block of memory a pointer refers to. But that can be a long way from
knowing the precise bounds of any array or sub-array, when represented
via a pointer to the first element.
So the problems are either that bounds transgressions can't be detected
properly as 'fat pointers' only have broad info about allocations, or
they will give false alarms when you want to do some pointer-offset
manipulations that C normally allows.
It's just that the K&R
> compiler with Unix didn't check, perhaps for decent reasons, and that
> the relatively few attempts to produce compilers that do have not been
> all that successful. You can't do the checking unless every pointer
> "knows" which object it is supposed to be pointing into, which rather
> implies "fat" pointers, which makes all pointer operations take longer
> and require more code. It very likely means that arrays too need to
> be implemented differently, with proper descriptors.
Which C is not going to have without breaking just about every existing
program. Besides, most array work in C doesn't actually use arrays, but
explicit pointers.
As discussed over
> in "comp.lang.misc" recently, that's not a Bad Thing; it gives you
> extra facilities virtually free, as well as the added security. But
> it does result in larger executables and slower execution -- unless you
> really do have hardware support [cf Burroughs] -- so historically it's
> not been popular.
With language support, it need have no cost. For example, suppose that
array A did carry its bounds with it (or are statically known), then in
code like this:
for i in A do # (iterate over bounds not values)
A[i] := 0
end
the compiler knows it doesn't need to bounds-check each access. Or here:
forall x in A do # (iterate over values)
print x
end
[Every pointer in C points either to a static object or to one that
comes from a handful of routines like malloc() or mmap() so it
shouldn't be too hard to do bounds checking within the allocated
object, give or take unsafe typecasts which I don't think are common
in application code. But you are certainly correct that C isn't
expressive enough to do slices or the like. -John]
[toc] | [prev] | [next] | [standalone]
Page 1 of 5 [1] 2 3 4 5 Next page →
Back to top | Article view | comp.compilers
csiph-web