Why Does Integer Overflow on X86 With Gcc Cause an Infinite Loop

Why does integer overflow on x86 with GCC cause an infinite loop?

When the standard says it's undefined behavior, it means it. Anything can happen. "Anything" includes "usually integers wrap around, but on occasion weird stuff happens".

Yes, on x86 CPUs, integers usually wrap the way you expect. This is one of those exceptions. The compiler assumes you won't cause undefined behavior, and optimizes away the loop test. If you really want wraparound, pass -fwrapv to g++ or gcc when compiling; this gives you well-defined (twos-complement) overflow semantics, but can hurt performance.

gcc -O2 creates an endless loop, probably because of undefined behaviour

I do not understand the code and not indent to, but the loop is strange. Anyway:

"-Wall -Wextra -pedantic" don't even issue a warning or something.

And there are also other ways to detect UB! Compiling your code with some more -fsanitize=* options results with:

+ gcc -Wall -Wextra -ggdb3 -fsanitize=address -fsanitize=undefined -fsanitize=pointer-compare -fsanitize=pointer-subtract -fsanitize-address-use-after-scope /tmp/1.c
/tmp/1.c:22:29: runtime error: index 9 out of bounds for type 'unsigned int [9]'
/tmp/1.c:22:29: runtime error: load of address 0x7ffc48c7a894 with insufficient space for an object of type 'unsigned int'
0x7ffc48c7a894: note: pointer points here
  13 00 00 00 60 60 00 00  00 00 00 00 00 00 00 00  01 00 00 00 00 00 00 00  08 aa c7 48 fc 7f 00 00
              ^ 
=================================================================
==73835==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffc48c7a894 at pc 0x55c28a5bf773 bp 0x7ffc48c7a800 sp 0x7ffc48c7a7f0
READ of size 4 at 0x7ffc48c7a894 thread T0
    #0 0x55c28a5bf772 in main /tmp/1.c:22
    #1 0x7f0060bd1151 in __libc_start_main (/usr/lib/libc.so.6+0x28151)
    #2 0x55c28a5bf12d in _start (/tmp/tmp.qv8ZsZofOJ.out+0x112d)

Address 0x7ffc48c7a894 is located in stack of thread T0 at offset 84 in frame
    #0 0x55c28a5bf208 in main /tmp/1.c:3

  This frame has 1 object(s):
    [48, 84) 'busses' (line 4) <== Memory access at offset 84 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow /tmp/1.c:22 in main
Shadow bytes around the buggy address:
  0x1000091874c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000091874d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000091874e0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x1000091874f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100009187500: 00 00 00 00 00 00 00 00 f1 f1 f1 f1 f1 f1 00 00
=>0x100009187510: 00 00[04]f3 f3 f3 f3 f3 00 00 00 00 00 00 00 00
  0x100009187520: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100009187530: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100009187540: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100009187550: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x100009187560: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==73835==ABORTING

After quick inspection the out of bounds access to busses happens here:

offset += busses[++i];

Does anybody know how to patch that undefined behavior?

No idea, but write an algorithm that doesn't access the array out of bounds.

Will variable declaration inside infinite loop in c cause stack overflow

Am I correct in saying that in the 1st code snippet, this code would eventually cause a stack overflow because of the variables continually being declared inside of the infinite loop?

No:

6.2.4 Storage durations of objects

...

6 For such an object that does not have a variable length array type, its lifetime extends from entry into the block with which it is associated until execution of that block ends in any way. (Entering an enclosed block or calling a function suspends, but does not end, execution of the current block.) If the block is entered recursively, a new instance of the object is created each time. The initial value of the object is indeterminate. If an initialization is specified for the object, it is performed each time the declaration or compound literal is reached in the execution of the block; otherwise, the value becomes indeterminate each time the declaration is reached.


7 For such an object that does have a variable length array type, its lifetime extends from the declaration of the object until execution of the program leaves the scope of the declaration.³⁵⁾ If the scope is entered recursively, a new instance of the object is created each time. The initial value of the object is indeterminate.

---

^{35) Leaving the innermost block containing the declaration, or jumping to a point in that block or an embedded block prior to the declaration, leaves the scope of the declaration.}

^{C 2011 Online Draft}

Each time through the loop new instances of some_int and some_pointer will be created at the beginning of the loop body and destroyed at the end of it - logically speaking, anyway. On most implementations I've used, storage for those items will be allocated once at function entry and released at function exit. However, that's an implementation detail, and while it's common you shouldn't rely on it being true everywhere.

If some_function dynamically allocates memory or some other resource that doesn't get freed before the end of the loop you could exhaust your dynamic memory pool or whatever, but it shouldn't cause a stack overflow as such.

behavior when for-loop variable overflow and compiler optimization

… then i will be assigned INT_MAX+1, which would overflow to an undefined value such as between 0 and INT_MAX.

No, that is not correct. That is written as if the rule were:

• If ++i overflows, then i will be given some int value, although it is not specified which one.

However, the rule is:

• If ++i overflows, the entire behavior of the program is undefined by the C standard.

That is, if ++i overflows, the C standard allows any of these things to happen:

• i stays at INT_MAX.
• i changes to INT_MIN.
• i changes to zero.
• i changes to 37.
• The processor generates a trap, and the operating system terminates your process.
• Some other variable changes value.
• Program control jumps out of the loop, as if it had ended normally.
• Anything.

Now consider this assumption used in optimization by the compiler:

… the compiler can assume that the loop will iterate exactly N+1 times…

If ++i can only set i to some int value, then the loop will not terminate, as you conclude. On the other hand, if the compiler generates code that assumes the loop will iterate exactly N+1 times, then something else will happen in the case when ++i overflows. Exactly what happens depends on the contents of the loop and what the compiler does with them. But it does not matter what: Generating this code is allowed by the C standard because whatever happens when ++i overflows is allowed by the C standard.

How disastrous is integer overflow in C++?

As pointed out by @Xeo in the comments (I actually brought it up in the C++ chat first):

Undefined behavior really means it and it can hit you when you least expect it.

The best example of this is here: Why does integer overflow on x86 with GCC cause an infinite loop?

On x86, signed integer overflow is just a simple wrap-around. So normally, you'd expect the same thing to happen in C or C++. However, the compiler can intervene - and use undefined behavior as an opportunity to optimize.

In the example taken from that question:

#include <iostream>
using namespace std;

int main(){
    int i = 0x10000000;

    int c = 0;
    do{
        c++;
        i += i;
        cout << i << endl;
    }while (i > 0);

    cout << c << endl;
    return 0;
}

When compiled with GCC, GCC optimizes out the loop test and makes this an infinite loop.

C++ infinite loop when assigning and post incrementing the loop iterator (gcc bug?)

The behaviour of i = i++ is undefined (simultaneous read write in an unsequenced step - and that is in the standard). Never use it.

Note that i = ++i is defined from C++11.

As for thinking in terms of compiler bugs. It's not impossible that you'll find one, but it's extremely unlikely, particularly if the suspected expression is so small.

---

Related Topics