We Need Hardware Traps for Integer Overflow • Hacker News Board

Re: We Need Hardware Traps for Integer Overflow

#101

Post by jacquesm » Thu, Jun 05, 2014, 10:21 AM UTC

acqq wrote: post #99

jacquesm wrote: post #95

Earlier quoted context omitted.

Setting a flag is not the same as raising an exception. When you get a segfault that's not because a flag was checked, that's because a chunk of hardware interrupted the next operation. So yes, you can check for overflow by inspecting a flag, but that's not all that much better from coding around the potential overflow to see if your operands + operation combo will cause an overflow. Imagine setting a flag on a divid…

No, I don't agree that "the author is most likely aware of the overflow flag" since the author says: "Processors should support integer math instructions that optionally trap on overflow. Because popular architectures lack this feature, otherwise excellent modern systems programming languages, such as Rust, Go, and D, have default integer types that wrap." In short, he believes there's no hardware support and therefo…

> "Processors should support integer math instructions that optionally trap on overflow. Because popular architectures lack this feature, otherwise excellent modern systems programming languages, such as Rust, Go, and D, have default integer types that wrap."

The operative word there is trap.

There is no hardware support for traps on overflow, period.

You can detect overflow in software and then you can generate an exception (or deal with it in some other fashion) like you describe, this is not the same as a trap.

Feel free to stick to your definition if you want to but the accepted one is that a trap operates much like an interrupt would.

http://en.wikipedia.org/wiki/Trap_%28computing%29

Re: We Need Hardware Traps for Integer Overflow

#102

Post by acqq » Thu, Jun 05, 2014, 10:38 AM UTC

jacquesm wrote: post #101

acqq wrote: post #99

Earlier quoted context omitted.

No, I don't agree that "the author is most likely aware of the overflow flag" since the author says: "Processors should support integer math instructions that optionally trap on overflow. Because popular architectures lack this feature, otherwise excellent modern systems programming languages, such as Rust, Go, and D, have default integer types that wrap." In short, he believes there's no hardware support and therefo…

> "Processors should support integer math instructions that optionally trap on overflow. Because popular architectures lack this feature, otherwise excellent modern systems programming languages, such as Rust, Go, and D, have default integer types that wrap." The operative word there is trap . There is no hardware support for traps on overflow, period. You can detect overflow in software and then you can generate an…

Of course I know the semantics of the "trap," the topic here is that the very "trap" is not necessary to have a reasonable high level language support for overflow checking, as there is the hardware flag already present and simply not used (according to the OP, in the sense of "not having the types that can produce an exception on overflow") in the languages mentioned by OP ("Rust, Go, and D").

I also gave an example of the language (Visual C++) which already implements exceptions (the application programmers sees only exceptions, not traps) on integer overflows, provided the programmer specifies that he wants such a type (declares them as SafeInt).

Re: We Need Hardware Traps for Integer Overflow

#103

Post by jacquesm » Thu, Jun 05, 2014, 10:44 AM UTC

acqq wrote: post #102

jacquesm wrote: post #101

Earlier quoted context omitted.

> "Processors should support integer math instructions that optionally trap on overflow. Because popular architectures lack this feature, otherwise excellent modern systems programming languages, such as Rust, Go, and D, have default integer types that wrap." The operative word there is trap . There is no hardware support for traps on overflow, period. You can detect overflow in software and then you can generate an…

Of course I know the semantics of the "trap," the topic here is that the very "trap" is not necessary to have a reasonable high level language support for overflow checking, as there is the hardware flag already present and simply not used (according to the OP, in the sense of "not having the types that can produce an exception on overflow") in the languages mentioned by OP ("Rust, Go, and D"). I also gave an example…

I think you're missing the point entirely, which is that if we had such a trap then integer overflow situations would be dealt with automatically rather than that they would rely on support by the individual languages.

Now whether or not the balance of burden (hardware/software) would favour a hardware solution or not is a different matter entirely. But I completely get what the author is trying to achieve and I'm well aware of the various bits in the flag registers of a whole pile of processors. I see having such a trap as a distinct advantage, just like I see division by 0 and floating point exceptions as advantageous.

The fact that you could do this in software right now has no bearing on his argument, that's a choice by the implementors of the various languages, which are usually built for speed rather than safety and where unchecked integer overlows are the norm. Retro-fitting a trap mechanism in hardware would likely turn up a whole pile of bugs in systems that we currently consider to be solid.

Re: We Need Hardware Traps for Integer Overflow

#104

Post by acqq » Thu, Jun 05, 2014, 10:50 AM UTC

jacquesm wrote: post #103

acqq wrote: post #102

Earlier quoted context omitted.

Of course I know the semantics of the "trap," the topic here is that the very "trap" is not necessary to have a reasonable high level language support for overflow checking, as there is the hardware flag already present and simply not used (according to the OP, in the sense of "not having the types that can produce an exception on overflow") in the languages mentioned by OP ("Rust, Go, and D"). I also gave an example…

I think you're missing the point entirely, which is that if we had such a trap then integer overflow situations would be dealt with automatically rather than that they would rely on support by the individual languages. Now whether or not the balance of burden (hardware/software) would favour a hardware solution or not is a different matter entirely. But I completely get what the author is trying to achieve and I'm we…

Well I have the news for you (re "I see division by 0 and floating point exceptions as advantageous"): when you use floating point in any current language now the division with 0 would not trigger any "exception" and it's certainly not supported by any language directly. CPU traps for the FPU are disabled by default by the language std libs.

Even worse, Java's model doesn't allow anybody to reach to the hardware.

The author of IEEE 754, prof. Kahan lamented exactly that: that the languages of today effectively can't use a lot of the features he designed (in 2004, http://www.cs.berkeley.edu/~wkahan/JAVAhurt.pdf Page 20: "Java lacks these flags and cannot conform to IEEE 754 without them.").

That was the FP domain, but is instructive. The traps are relatively "all or nothing" thing. To have a language where some integer variables behave one way and some another way (you know, the types are important now), you already have the hardware flags and they simply aren't used in the languages OP mentions.

Just changing the compiler behavior would be absolutely enough to "turn up a whole pile of bugs in systems that we currently consider to be solid" that you suggest. You certainly don't need to wait for some new CPUs.

So we return to what Anon said: "Those who do not understand the hardware are doomed to blog about it, poorly." If somebody wants to have the language types that trigger exceptions on overflows, he doesn't have to wait for the new processors. It's possible now, if there's interest in it. And even as the real "traps" as the very specific CPU feature for FP already exist, no language I know of uses them for types.

Re: We Need Hardware Traps for Integer Overflow

#105

Post by userbinator » Thu, Jun 05, 2014, 11:58 AM UTC

TorKlingberg wrote: post #25

angersock wrote: post #12

One of the surprisingly annoying minor things we implemented for some safe code were C routines for "safe arithmetic"--explicitly and carefully catching overflows due to multiplication and addition, for example. This code proved invaluable when writing binary parsers designed to support "unsafe" mesh data coming off of the network--the file might be garbage, but we could at least safely parse it. I'd go so far to say…

Regehr, where this post is from, recently had an article about how to do safe arithmetic in C. http://blog.regehr.org/archives/1139 As you say, it is surprisingly different to it get right, especially if you want good performance. A common mistake is checking for signed integer overflow after the fact. It is too late when undefined behavior has already happened.

> It is too late when undefined behavior has already happened.

This seems more like a theoretical concern, as just about all the hardware out there is 2's complement and signed overflow wraps around in the usual way - because that's the simplest, most straightforward way to implement it. (This also means I think compilers that exploit this "loophole" in the language are seriously violating the principle of least surprise.) If you're working on the few exceptions to this, then integer overflow is probably going to be the least of your worries...

Re: We Need Hardware Traps for Integer Overflow

#106

Post by dspillett » Thu, Jun 05, 2014, 12:49 PM UTC

acqq wrote: post #91

"Those who do not understand the hardware are doomed to blog about it, poorly. Intel chips already detect overflow, that is what the OF (bit 11) flag in the flags/eflags register indicates. That the most recent operation overflowed. Testing, and generating a trap, for an overflow is a single instruction (JO – jump if overflow and JNO – jump if no overflow). This is true of almost all CPU’s. At the hardware/assembly p…

> Why, most likely because almost all of them are ultimately implemented in C

That isn't right: languages created before and after C exhibit the same behaviour. Some languages do explicitly check the overflow flag every time.

The reason for not always checking (or never checking) is that in a tight loop the extra instruction can significantly affect performance especially back when CPUs had a fraction of their current speediness capability. The reason for not exposing the value to the higher level constructs is similar: you have to check it every time it might change and update an appropriate structure, which is expensive given an overflow should be a rare occurrence so checking every time and saving the result is wasteful.

The linked article specifically mentions the performance effect of checking overflow flags in software. I believe what it is calling for is some form of interrupt that fires when the flag is switched on in a context where a handler for it is enabled - a fairly expensive event happens upon overflow but when all is well there is no difference in performance (no extra instructions run). Of course there would be complications here: how does the CPU keep track of what to call (if anything) in the current situation? Task/thread handling code in the OS would presumably need to be involved in helping maintain this information during context switches.

Re: We Need Hardware Traps for Integer Overflow

#107

Post by acqq » Thu, Jun 05, 2014, 2:42 PM UTC

dspillett wrote: post #106

acqq wrote: post #91

"Those who do not understand the hardware are doomed to blog about it, poorly. Intel chips already detect overflow, that is what the OF (bit 11) flag in the flags/eflags register indicates. That the most recent operation overflowed. Testing, and generating a trap, for an overflow is a single instruction (JO – jump if overflow and JNO – jump if no overflow). This is true of almost all CPU’s. At the hardware/assembly p…

> Why, most likely because almost all of them are ultimately implemented in C That isn't right: languages created before and after C exhibit the same behaviour. Some languages do explicitly check the overflow flag every time. The reason for not always checking (or never checking) is that in a tight loop the extra instruction can significantly affect performance especially back when CPUs had a fraction of their curren…

The performance penalty you mention ("in a tight loop the extra instruction can significantly affect performance") doesn't happen if you add the new type in the language (that is, what in VC++ is a "SafeInt"). In the really tight loop you wouldn't use that type. That type is important exactly for the things I've given a MSFT's example (calculating how much to allocate -- overflow means you allocated much less and you don't catch that!) So no, you don't have to "check every time."

The reason it's not in standard C is to be portable with some odd old architecture which doesn't have the overflow flag at all. Some modern language can be clearly designed to depend on the overflow flag. The cost would happen only when the programmer really does access it (in a modern language: by using such a type) and the cost would be minimal, as there is a direct hardware support.

> I believe what it is calling for is some form of interrupt that fires when the flag is switched on in a context where a handler for it is enabled

And that is misguided, as it doesn't allow for fine grained control -- it's all or nothing, either all instructions generate "an interrupt" or none. If you want to change the behavior from the variable to variable, changing processor mode would cost. If you add a new instructions for all things that can overflow and trap, you'd add a lot of new instructions. So it's also bad. The simplest approach is: use what's already there. The flag is there in the CPU, it's not used by the languages OP mentions, but once the language supports it for the "safe" integer type, it will be checked only when it's really needed: for that type and nowhere else.

Finally, the maintenance of the exception handling code (what you name under "how does the CPU keep track of what to call") is something that modern compilers and even assembly writers must take care of and is very good understood among them: for example, Winx64 ABI expects every non-leaf function to maintain the stack unwinding information properly and even if I write assembly code I effectively have to support exceptions outside of my code for every non-trivial function I write. So this part is very good known, and the most is taken care of outside of the OS. The OS merely has some expectations, the compiler (in broader sense, that is, including native code generator and linker) writers must fulfill them.

Re: We Need Hardware Traps for Integer Overflow

#108

Post by osmala » Thu, Jun 05, 2014, 2:43 PM UTC

azakai wrote: post #67

rwallace wrote: post #42

I think the article overstates the cost of doing this in software and understates the cost of doing it in hardware. The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. The article presents no data on this cost. I have none to hand either, but I'm going to predict that on a modern CPU with typical w…

> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. The article presents no data on this cost. The article does mention a 5-10% cost on JavaScript VMs, as one datapoint. And as another, that languages like Rust choose to allow overflow to avoid the overhead, despite preferring the security of not…

Here's another point, how much clockspeed suffers from adding this feature? What about instruction latencies? Does it increase the pipeline length for bigger branch missprediction penalty? Does it interfere with microarchitecture optimizations we are using or could be using? All these are performance questions that may result from adding this instruction. There is reason why RISC eliminated most of mixing control flow with arithmetic.

As for his numbers on the performance penalty of doing it in software it surely depends on micro-architecture. All intel x86 processors before HASWELL did only ONE branch per cycle, then in haswell they increased that to two. So the cost of doing it in software should of went down recently. And Intel is adding new instructions to speed up arbitrary precision arithmetics in broadwell so they probably have already thought about this and decided its not worth the cost in hardware.

Re: We Need Hardware Traps for Integer Overflow

#109

Post by Gracana » Thu, Jun 05, 2014, 6:25 PM UTC

stephencanon wrote: post #90

Gracana wrote: post #15

ARMv5 and beyond have saturating arithmetic instructions , which can be pretty handy. It won't cause an exception, but it is at least one way to improve the situation. and a sticky saturation flag in the status register

Deprecated (and moved to NEON) in aarch64, FWIW.

Huh, okay, I guess that's sensible. Thanks for pointing that out, I haven't been paying much attention to the latest in ARM, so I hadn't heard that.

Re: We Need Hardware Traps for Integer Overflow

#110

Post by jcalvinowens » Fri, Jun 06, 2014, 12:55 AM UTC

cliffbean wrote: post #89

jcalvinowens wrote: post #58

Earlier quoted context omitted.

> The cost of doing it in software is just a highly predictable (not taken) branch after every integer arithmetic operation that the compiler can't prove stays within bounds. While I agree with you that hardware overflow traps are a bad idea, I think the article's author is referring more to the general overhead of a software BIGNUM implementation. Specifically with his JavaScript example, I think it's very plausible…

There probably is close to zero overhead in a small benchmark. Hardware branch prediction is indeed good. However, it's a finite resource. In a large application, lots of needless branches everywhere translates into fewer branch prediction resources available for the branches that matter, which means more mispredictions. Also, they take up icache, itlb, etc. It's not at all obvious that the overhead would be close to…

> It's not at all obvious that the overhead would be close to zero in context.

That's a fair point, although I think using a single function for all your checked addition like the one above would go a long way towards mitigating the resource waste you mention.

Maybe that's a naive assumption on my part: I suppose you could construct a branch predictor that maintains state based on the function call chain as opposed simply using the address of the branch... but that seems like it would be prohibitively complex.