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

Issue

I wrote this C code to solve Advent of Code 13 2020. I know, it's probably not viable trying to solve it via brute force, but the program gives the correct answer for the example input.

If I try to let gcc optimize the code, it gives the correct result with -O1, but creates an endless loop with -O2. After all the research my conclusion is that there is undefined behavior in my code, I guess it has to do with the probability that "found" may never be higher than 0 and so "time" would overflow.

Here is the question: Does anybody know how to patch that undefined behavior?

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

I just can't find a solution. If I, for example, change the head of the while loop to (!found && time < 10000000000), so that no overflow can occur, it just breaks the loop right away with a time value of 10000000003 when compiled with -O2, but still gives the right result with -O1.

Here is the code, the correct result would be "1068781":

#include <stdio.h>
int main()
{
    unsigned int busses[] = {7, 0, 13, 2, 59, 1, 31, 0, 19};
    unsigned int busses_used = 9;
    unsigned int i = 0;
    unsigned int found = 0;
    unsigned long long time = 0;
    unsigned int offset = 0;
    unsigned int increment = 7;
    while (!found) {
        time += increment;
        offset = 0;
        for (i = 0; i < busses_used; i++) {
            if ((time + offset) % busses[i] == 0) {
                found = 1;
                offset++;
            } else {
                found = 0;
                break;
            }
            offset += busses[++i];
        }
    }
    printf("Endtime: %lld\n", time);
    return 0;
}

Edit: Thanks to KamilCuk for pointing out that the code is accessing the array out of bounds and teaching how to find out that it is doing so. The problem is solved by adding another 0 at the end of the "busses" array and therefore also setting "busses_used" to 10 instead of 9.

Solution

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.

Answered By - KamilCuk