Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

We Need Hardware Traps for Integer Overflow

blog.regehr.org

Post reply on HN
Print view View original

61–70 of 112 posts

Re: We Need Hardware Traps for Integer Overflow

#61

Post by sounds »

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.

In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul

Checking for overflow is just a matter of testing if the high-order bits are zero.

Re: We Need Hardware Traps for Integer Overflow

#62

Post by jcalvinowens »

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.

> 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 probably not a great idea.

I've never tried to implement this, but couldn't you look at the position of the most significant bit in the multiplicands to guess if the multiply will overflow? You'd have to be okay with false positives I suppose? Naively it would be slow, but if you have a hardware CLZ instruction it could be pretty fast.

I did find this on SO:

  x = a * b;
  if (a != 0 && x / a != b) {
    // overflow handling
  }
That makes sense, but of course it would be HORRENDOUSLY expensive.

If you're willing to not be non-portable, you could just do expanding multiplies and check the high word:

  struct exmulres {
        unsigned long hi;
        unsigned long lo;
  };

  static inline __attribute__((always_inline)) struct exmulres do_one_expanding_multiply(unsigned long a, unsigned long b)
  {
        struct exmulres res;
        #if defined(__x86_64__)
                asm ("movq %0,%%rax; mulq %1; movq %%rdx,%1; movq %%rax,%0"
                : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%rax","%rdx");
        #elif defined(__i386__)
                asm ("movl %0,%%eax; mull %1; movl %%edx,%1; movl %%eax,%0"
                : "=r" (res.lo), "=r" (res.hi) : "0" (a), "1" (b) : "%eax","%edx");
        #elif defined(__arm__)
                asm ("umull %0,%1,%2,%3"
                : "=r" (res.lo), "=r" (res.hi) : "r" (a), "r" (b) :);
        #else
                #error "No expanding multiply assembly has been written for your architecture"
        #endif
        return res;
  }
It probably wouldn't be very difficult to fill that out for all the CPU architectures Linux supports, which would cover all your bases unless you're doing super embedded stuff.

EDIT: Typo

Re: We Need Hardware Traps for Integer Overflow

#63

Post by stormbrew »

sounds wrote: post #61
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.

In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul Checking for overflow is just a matter of testing if the high-order bits are zero.

Yep, in assembly it's usually no question possible. That's why I specified portable C.

C has some interesting gaps for something that's long been described as a macro for assembly. A rotate operator would also be nice.

Re: We Need Hardware Traps for Integer Overflow

#65

Post by pbsd »

sounds wrote: post #61
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.

In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul Checking for overflow is just a matter of testing if the high-order bits are zero.

The correct thing to do is also to check the carry and overflow flags after (I)MUL, which does the right thing even when only the lower bits of the multiplication are saved.

Here's an example where there is overflow, but your suggestion would not catch it:

    mov eax, 0x7fffffff
    mov ecx, 2
    imul ecx ; edx:eax = eax * ecx
    ; edx = 0
    ; eax = 0xfffffffe
    ; overflow flag = 1
There is signed overflow here, but testing edx (the higher word of the result) would not catch it.

Re: We Need Hardware Traps for Integer Overflow

#66

Post by stormbrew »

jcalvinowens wrote: post #62
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.

> 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 */
        }
        return (uint64_t)res;
    }
Which compiles to this in gcc -Os and -O3:

    0:	48 89 f8             	mov    %rdi,%rax
    3:	48 f7 e6             	mul    %rsi
    6:	48 85 d2             	test   %rdx,%rdx
    9:	74 01                	je     c 
    b:	90                   	nop
    c:	f3 c3                	repz retq
Which I'm pretty sure could be optimized further by using the overflow flag, but the compiler doesn't seem to want to ignore the upper word.

edit: and it probably suffers the same problem as described here: https://news.ycombinator.com/item?id=7848771 -- and also probably has general issues with signedness that would need to be further checked.

edit2: changed it to uints to simplify and avoid a whole class of problem. I still don't think you should go use this, though.

(inspiration from SO: http://stackoverflow.com/a/13187798)

Re: We Need Hardware Traps for Integer Overflow

#67

Post by azakai »

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 having silent overflows (implying they measured a slowdown they find unacceptable).

Re: We Need Hardware Traps for Integer Overflow

#68

Post by pascal_cuoq »

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 “const int min = 0x80000000;” does NOT contain undefined behavior. The overflows occurs during a conversion from an integer type to a signed integer type. Overflow during such a conversion is implementation-defined (or an implementation-defined signal is raised). Even an implementation-defined signal is not undefined behavior, but in practice, the compiler you use produces wrap-around behavior, and it will continue to do so, because it has been forced to document it.

Re: We Need Hardware Traps for Integer Overflow

#69

Post by sounds »

pbsd wrote: post #65
sounds wrote: post #61

Earlier quoted context omitted.

In x86 assembly almost all multiplication operations return a result double the width of the inputs: http://www.aldeid.com/wiki/X86-assembly/Instructions/mul Checking for overflow is just a matter of testing if the high-order bits are zero.

The correct thing to do is also to check the carry and overflow flags after (I)MUL, which does the right thing even when only the lower bits of the multiplication are saved. Here's an example where there is overflow, but your suggestion would not catch it: mov eax, 0x7fffffff mov ecx, 2 imul ecx ; edx:eax = eax * ecx ; edx = 0 ; eax = 0xfffffffe ; overflow flag = 1 There is signed overflow here, but testing edx (the…

Yes. I decided not to mention IMUL to keep the post simple.

There are also issues with detecting overflow of SSE multiplies (signed and unsigned).

Re: We Need Hardware Traps for Integer Overflow

#70

Post by danbruc »

throwawayaway wrote: post #60
danbruc wrote: post #35

Earlier quoted context omitted.

Of course and this is what actually happens if you enable overflow checking but it comes at a price - if your code is correct you will never need the checks but you will execute them every time.

here's the best guide i could find on enabling those checks in gcc. it is unclear whether they take advantage of the carry bits, do you have a source for that information? http://www.pixelbeat.org/programming/gcc/integer_overflow.ht...

You can see the implementation in GCC here [1], for example addition starting on line 74. What machine code gets emitted for that obviously depends on the target architecture but it is reasonable to assume that the optimizer recognizes these patterns and uses hardware flags where available.

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

Post reply on HN