Out-of-bounds array access

[V02460]

While trying to package HyperRogue as Flatpak app, the game crashes because of a failed assertion. Flatpak by default enables the _GLIBCXX_ASSERTIONS flag for compilation, which in turn inserts the runtime range checks/assertions into the binary. The code where the problem arises is this:

https://github.com/zenorogue/hyperrogue/blob/bcc96ffa1195dd058c046cc856056845ff5b4f48/drawing.cpp#L1960-L1963

When starting the game, at one point the ptds vector has 538 entries and is accessed at position 538 (out-of-bounds). Right then qp and qp0 look like this:

(gdb) print qp0
$3 = {0 <repeats 29 times>, 393 <repeats 17 times>, 521 <repeats 15 times>, 525 <repeats 17 times>, 
  527, 533, 533, 533, 534, 535, 535, 535, 535, 535, 536, 537 <repeats 16 times>, 538, 538, 538, 538, 
  538, 538, 538, 538, 538, 538}
(gdb) print qp
$10 = {0 <repeats 28 times>, 393 <repeats 17 times>, 521 <repeats 15 times>, 525 <repeats 17 times>, 
  527, 533, 533, 533, 534, 535, 535, 535, 535, 535, 536, 537 <repeats 16 times>, 
  538 <repeats 11 times>}

The exact assertion error message is this:

/usr/include/c++/9.2.0/bits/stl_vector.h:1042: std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::unique_ptr<hr::drawqueueitem>; _Alloc = std::allocator<std::unique_ptr<hr::drawqueueitem> >; std::vector<_Tp, _Alloc>::reference = std::unique_ptr<hr::drawqueueitem>&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]: Assertion '__builtin_expect(__n < this->size(), true)' failed.

(Sry to have this really low-level technical bug, but I didn't get through the logic of the code in a reasonable amount of time)

[zenorogue]

I think this is a false positive: what happens here is that ptds has 538 elements, and std::sort is called to sort the range which starts at position 538 and ends at position 538. This is a valid (empty) range, so it should not be a reason to worry about.

Anyway, I have added a check so that std::sort is not called for empty ranges, this should fix the problem.

[emmiegit]

Should this issue be closed, if it's resolved?

[l29ah]

Not sure if the same, but i just hit a very similar issue on 13.0:

/usr/lib/gcc/x86_64-pc-linux-gnu/12/include/g++-v12/bits/stl_vector.h:1123: std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = std::unique_ptr<hr::drawqueueitem>; _Alloc = std::allocator<std::unique_ptr<hr::drawqueueitem> >; reference = std::unique_ptr<hr::drawqueueitem>&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

Backtrace:

#0  0x00007f1f79deec5c in __pthread_kill_implementation () from /lib64/libc.so.6
#1  0x00007f1f79d9fe76 in raise () from /lib64/libc.so.6
#2  0x00007f1f79d888bc in abort () from /lib64/libc.so.6
#3  0x00007f1f7a0deb6f in std::__glibcxx_assert_fail (file=<optimized out>, line=<optimized out>, function=<optimized out>, condition=<optimized out>)
    at /var/tmp/portage/sys-devel/gcc-13.2.1_p20231216/work/gcc-13-20231216/libstdc++-v3/src/c++11/assert_fail.cc:41
#4  0x0000557e482cae9b in std::vector<std::unique_ptr<hr::drawqueueitem, std::default_delete<hr::drawqueueitem> >, std::allocator<std::unique_ptr<hr::drawqueueitem, std::default_delete<hr::drawqueueitem> > > >::operator[] (
    this=0x557e48d32990 <hr::ptds>, __n=1780) at /usr/lib/gcc/x86_64-pc-linux-gnu/12/include/g++-v12/bits/stl_vector.h:1123
#5  0x0000557e482c3dfb in hr::drawqueue () at drawing.cpp:2600
#6  0x0000557e485bd803 in hr::drawfullmap () at graph.cpp:5635
#7  0x0000557e47d51cab in hr::function_state<void (*)(), void>::call (this=0x557e4a0fa0e0) at /var/tmp/portage/games-roguelike/hyperrogue-9999/work/hyperrogue-9999/hyper_function.h:27
#8  0x0000557e47d3a0f5 in hr::function<void ()>::operator()() const (this=0x557e49664fb8 <hr::wrap_drawfullmap>) at /var/tmp/portage/games-roguelike/hyperrogue-9999/work/hyperrogue-9999/hyper_function.h:64
#9  0x0000557e485bdc0f in hr::gamescreen () at graph.cpp:5709
#10 0x0000557e485bdec5 in hr::normalscreen () at graph.cpp:5772
#11 0x0000557e47d51cab in hr::function_state<void (*)(), void>::call (this=0x557e4a0fa140) at /var/tmp/portage/games-roguelike/hyperrogue-9999/work/hyperrogue-9999/hyper_function.h:27
#12 0x0000557e47d3a0f5 in hr::function<void ()>::operator()() const (this=0x557e54b0d780) at /var/tmp/portage/games-roguelike/hyperrogue-9999/work/hyperrogue-9999/hyper_function.h:64
#13 0x0000557e485be6e9 in hr::drawscreen () at graph.cpp:5898
#14 0x0000557e48516b27 in hr::mainloopiter () at control.cpp:815
#15 0x0000557e48518b21 in hr::mainloop () at control.cpp:1296
#16 0x0000557e486903a7 in hr::hyper_main (argc=1, argv=0x7fffd1736b48) at hyper-main.cpp:90
#17 0x0000557e486903d7 in main (argc=1, argv=0x7fffd1736b48) at hyper-main.cpp:98

[l29ah]

3692ef68b9983681f88a81cc79aac34f0461305c is the first bad commit

Could be imprecise though due to the intermittent nature of the bug.