We Need Hardware Traps for Integer Overflow • Hacker News Board

Re: We Need Hardware Traps for Integer Overflow

#71

Post by xenonflash » Wed, Jun 04, 2014, 10:46 PM UTC

stormbrew wrote: post #59

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…

Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.

He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps.

I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary duplication of computational effort. However, that is a lot of work and has the potential for hidden programmer introduced errors.

The real problem is that languages like C simply don't allow you to take advantage of hardware which already exists in the CPU without writing in-line assembler. A standard set of "checked" math macros which handled the portability issues would probably satisfy most C applications.

Edit: For addition, subtraction, and multiplication, you just take one operand, calculate the largest possible second operand for that data type which won't overflow, and check that the actual second operand doesn't exceed it (remembering to take signs into account). For division and modulus, check for division by zero. For multiplication, division, modulus, negation, and absolute value of signed values, check that you are not negating the maximum negative integer, as integer ranges are not symmetrical (e.g. one byte is -128 to +127).

If you are looping over arrays and have multiple checks for different cases (e.g. negative, positive, etc.), then you can have different loops for different cases and so avoid redundant checks for that data. I'm working on this sort of application, so the above works out best for that. If you're doing something a bit different, then different algorithms may make sense. Unfortunately, there's not universal one-size-fits-all solution to this problem in software.

Re: We Need Hardware Traps for Integer Overflow

#72

Post by stormbrew » Wed, Jun 04, 2014, 10:50 PM UTC

xenonflash wrote: post #71

stormbrew wrote: post #59

Earlier quoted context omitted.

Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.

He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps. I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary dupl…

It's surprising there aren't at least intrinsics for some of these things in GCC/clang. At least as far as I can tell.

Re: We Need Hardware Traps for Integer Overflow

#73

Post by danbruc » Wed, Jun 04, 2014, 10:56 PM UTC

stormbrew wrote: post #66

jcalvinowens wrote: post #62

Earlier quoted context omitted.

> Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). Yeah, you're absolutely right. > I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's prob…

Yeah that div check works I guess, but as you say is horribly expensive. For the latter it looks like at least on recent versions of gcc, you can do something like (WARNING: Just a vague proof of concept, please don't use it. It might kill kittens): uint64_t func(uint64_t a, uint64_t b) { unsigned __int128 res = (unsigned __int128)a * (unsigned __int128)b; if (res >> 64) { asm volatile ("nop;" ::); /* handle here */…

Looking at the GCC source [1] starting at line 150 this is almost what GCC actually does - perform the multiplication with twice the operand size and then check by shifting right but GCC compares the result of two shift operations differing by one in the shift amount.

[1] https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c

Re: We Need Hardware Traps for Integer Overflow

#74

Post by stormbrew » Wed, Jun 04, 2014, 10:58 PM UTC

danbruc wrote: post #73

stormbrew wrote: post #66

Earlier quoted context omitted.

Yeah that div check works I guess, but as you say is horribly expensive. For the latter it looks like at least on recent versions of gcc, you can do something like (WARNING: Just a vague proof of concept, please don't use it. It might kill kittens): uint64_t func(uint64_t a, uint64_t b) { unsigned __int128 res = (unsigned __int128)a * (unsigned __int128)b; if (res >> 64) { asm volatile ("nop;" ::); /* handle here */…

Looking at the GCC source [1] starting at line 150 this is almost what GCC actually does - perform the multiplication with twice the operand size and then check by shifting right but GCC compares the result of two shift operations differing by one in the shift amount. [1] https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c

For future reference, you can link to a specific line in github with #LNNN. Which you can get by clicking on the line number. Pretty handy.

https://github.com/mirrors/gcc/blob/master/libgcc/libgcc2.c#...

Re: We Need Hardware Traps for Integer Overflow

#75

Post by forrestthewoods » Wed, Jun 04, 2014, 10:58 PM UTC

pascal_cuoq wrote: post #68

forrestthewoods wrote: post #38

I'm gonna shill for a moment and link a post I wrote on integer overflows very recently. http://forrestthewoods.com/perfect-prevention-of-int-overflo... TLDR: Not accidentally performing an undefined operation is really really hard.

Hello, the comment system on your blog eats comments, that become lost forever when submitted. You might want to know that. Apart from that: 1) “2147483650f” is Java syntax. Also this number, written in C++ as 2147483650.0f, actually represents the number 2147483648 (assuming float is the single-precision IEEE 754 format). You might want to denote that number 2147483648.0f, which would be less confusing. 2) the line…

What login did you use for making the comments? It just uses Disqus which is pretty common these days. I was able to successfully make a comment with a Twitter login. Recent posts have had surprisingly few comments but not zero. Strange...

The 2147483648 vs 2147483650 is actually kind of interesting. Visual Studio watch window prints floats with one less digit of precision they they need as it actually displays (from memory) 2.14748365e9 when it should display as 2.147483648e9. Thanks for the catch.

I'll have to check spec docs to if the unsigned to signed overflow is undefined or implementation defined. I think you're correct but I need to verify.

Re: We Need Hardware Traps for Integer Overflow

#76

Post by xxs » Wed, Jun 04, 2014, 11:05 PM UTC

JoshTriplett wrote: post #39

jjoonathan wrote: post #16

Earlier quoted context omitted.

Checks are the smallest cost of bignums. Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive. It's one thing for a scripting language (where people expect poor, inconsistent performance) to have automatic bignums but it's quite another for a language in which people will be writing performant code to have automatic bignums. They introduce a thousand diffi…

> Dynamic allocation isn't free, it's terribly expensive. Dereferencing pointers isn't free, it's terribly expensive. So don't do either of those things until your arithmetic overflows the size of a word; until then, you can keep numbers in a register.

That's not easy either as it'd require very heavy inlining by the compiler. Functions that accept just 'integer' have to check if the value is a native number or actual reference and process differently. C/C++,Java* ,C# have it easier there - when you pass 'int'/'long' the receiver knows it's a native number.

* Fixnums support (headless objects) needed for non-Java lanaguages on JVM is still unimplemented to my knowledge[0]

[0] http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6674617

Re: We Need Hardware Traps for Integer Overflow

#77

Post by Someone » Wed, Jun 04, 2014, 11:06 PM UTC

stormbrew wrote: post #59

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…

Note, in case someone blindly takes this as advice: This method of expressing it in C doesn't work for multiplication (you could wrap more than once). I'm not sure you can express an overflow check for multiplication purely in portable C (without library or intrinsic support), actually. Well, I guess you could break the multiplication into checked additions manually, but that's probably not a great idea.

A smarter way is to split both numbers to multiply into two halves, and pretend to do two-word arithmetic on a machine with words half the size.

In decimal, that means that you compute the product of two-digit numbers using single-digit multiplications and shifts (= multiplications by 10):

  23 x 67
  = (20+3) x (60+7)
  = (2x3) x 100 + (2x6) x 10 + (3x7) x 10 + 3x7

Re: We Need Hardware Traps for Integer Overflow

#78

Post by Someone » Wed, Jun 04, 2014, 11:14 PM UTC

stormbrew wrote: post #72

xenonflash wrote: post #71

Earlier quoted context omitted.

He also picked one of the most trivial cases - unsigned addition. Signed data, especially signed multiplication, requires a lot more steps. I'm working on a set of numerical problems in C now that involve checking for integer overflow. The best way of doing software overflow checks depends on the larger scope of the problem. You can knit your checks into various places in your code in ways that avoid unnecessary dupl…

It's surprising there aren't at least intrinsics for some of these things in GCC/clang. At least as far as I can tell.

http://clang.llvm.org/docs/LanguageExtensions.html#builtin-f..., the search for "Checked Arithmetic Builtins"

Re: We Need Hardware Traps for Integer Overflow

#79

Post by stormbrew » Wed, Jun 04, 2014, 11:20 PM UTC

Someone wrote: post #78

stormbrew wrote: post #72

Earlier quoted context omitted.

It's surprising there aren't at least intrinsics for some of these things in GCC/clang. At least as far as I can tell.

http://clang.llvm.org/docs/LanguageExtensions.html#builtin-f... , the search for "Checked Arithmetic Builtins"

Nice! Thanks for the link, I admit I didn't do as much looking on the clang side as gcc. Doesn't look like these exist in gcc though, unfortunately. :/

Re: We Need Hardware Traps for Integer Overflow

#80

Post by mikeash » Wed, Jun 04, 2014, 11:36 PM UTC

jjoonathan wrote: post #43

mikeash wrote: post #24

Earlier quoted context omitted.

Isn't the alternative introducing a thousand difficult-to-debug edge cases that cause your code to produce incorrect output, or crash? I'd rather the default setup be "can be slow sometimes". If you're writing performance-sensitive code where you want to control the overflow behavior, make that an option, but not the default. In the context of Swift, it would make a lot of sense to me for Int to be a bignum with no b…

First of all, I'm all for overflow traps and I'm quite happy with bignums in my scripting languages. I only claim: 1. There is a large class of languages where they do not make sense as a default. 2. The most sensible approach is to fastlane the all-int native case, but this comes at the cost of a preciptitous drop in speed the moment even a single bignum happens. > Isn't the alternative introducing a thousand diffic…

You sound like you have more experience with this than I, so take the following with that in mind....

My experience with this has mainly been in languages like Python, where bignum performance is way down on the list of worries, and C, where you wrap if you're lucky and end up with exploitable security vulnerabilities if you're not. I don't believe I've seen a language at work which traps overflows.

My experience with C has been that overflows (which would be unintentional bignums in another environment) are almost always one of:

1. Underflow of unsigned values used for sizes, especially for memory allocation, which causes a request for vast quantities of memory.

2. Computations on large quantities without thinking about how large they can be. File sizes are a really common example of this, especially since they fit into 32 bits for so long.

3. Reading textual data containing integers that either doesn't specify how large they can be, or specifies it but the specification got ignored. A fun example of this was the Twitpocalypse, when Twitter collected enough tweets for the tweet IDs to overflow signed 32-bit integers and broke a ton of clients.

#1 is an error, and crashing would be fine. That's usually what happens in C anyway, just in a somewhat more confusing manner because you get an error trying to allocate 4 billion bytes of memory rather than the more obvious "can't put -1 in here" that actually happened.

#2 is pretty much the poster child for automatic bignums. The downside being potential slowness, but most aren't performance sensitive.

#3 is an interesting case. I'm not sure that using a language "integer" type is even the right way to represent an ID from a remote service, even if that ID happens to be an integer. But automatic bignums would have prevented this problem, even if the design wasn't necessarily right to begin with.

As far as I know (and I realize it's probably hard to tell), I haven't seen bugs where automatic bignums would produce the wrong answer. They can be bugs (e.g. #1 above, possibly #3) but they don't involve incorrect output.

Anyway, to me it just makes sense for the default behavior to be correctness. When you write "a + b" without taking special measures, the result should be the right answer in a mathematical context. If you want bounds checking, that should be made explicit. (A way to create configurable integer types with arbitrary bounds could be nice.) If you want wrapping, that should be made explicit too. And if you want performance at the potential expense of correctness at the edges (presumably because you either know you won't hit the edges, or they behave the way you want them to) then that ought to be opt-in, not opt-out.