New autoplacer tool leads to crash

[Aimylios]

I wanted to test Tom's new autoplacer tool, but whenever I try to use it, KiCad crashes with the following message:
/usr/include/c++/8/bits/stl_vector.h:932: std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::reference = int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]: Assertion '__builtin_expect(__n < this->size(), true)' failed.
Aborted (Speicherabzug geschrieben)

A minimal example project is attached, although I think that does not matter, as I can reproduce this problem with all the projects I have tried so far. I can try provide more detailed information about the crash, but you'll have to advise me how to do that.

My computer is a Lenovo T420s running Fedora 28.

---

Application: kicad
Version: 6.0.0-rc1-unknown-r13610.90788a5a7.fc28, debug build
Libraries:
    wxWidgets 3.0.4
    libcurl/7.59.0 OpenSSL/1.1.0h zlib/1.2.11 libidn2/2.0.5 libpsl/0.20.2 (+libidn2/2.0.4) libssh/0.8.1/openssl/zlib nghttp2/1.32.0
Platform: Linux 4.17.18-200.fc28.x86_64 x86_64, 64 bit, Little endian, wxGTK
Build Info:
    wxWidgets: 3.0.4 (wchar_t,wx containers,compatible with 2.8) GTK+ 2.24
    Boost: 1.66.0
    OpenCASCADE Community Edition: 6.9.1
    Curl: 7.59.0
    Compiler: GCC 8.1.1 with C++ ABI 1013

Build settings:
    USE_WX_GRAPHICS_CONTEXT=OFF
    USE_WX_OVERLAY=OFF
    KICAD_SCRIPTING=ON
    KICAD_SCRIPTING_MODULES=ON
    KICAD_SCRIPTING_WXPYTHON=ON
    KICAD_SCRIPTING_ACTION_MENU=ON
    BUILD_GITHUB_PLUGIN=ON
    KICAD_USE_OCE=ON
    KICAD_USE_OCC=OFF
    KICAD_SPICE=ON

[Fabián Inostroza (fabianinostroza)]

I'm unable to reproduce in debian testing

Application: kicad
Version: (6.0.0-rc1-dev-390-g56de78c13), debug build
Libraries:
    wxWidgets 3.0.4
    libcurl/7.61.0 GnuTLS/3.5.19 zlib/1.2.11 libidn2/2.0.4 libpsl/0.20.2 (+libidn2/2.0.4) libssh2/1.8.0 nghttp2/1.32.0 librtmp/2.3
Platform: Linux 4.17.0-3-amd64 x86_64, 64 bit, Little endian, wxGTK
Build Info:
    wxWidgets: 3.0.4 (wchar_t,wx containers,compatible with 2.8) GTK+ 2.24
    Boost: 1.62.0
    OpenCASCADE Community Edition: 6.9.1
    Curl: 7.61.0
    Compiler: GCC 8.2.0 with C++ ABI 1013

Build settings:
    USE_WX_GRAPHICS_CONTEXT=OFF
    USE_WX_OVERLAY=OFF
    KICAD_SCRIPTING=ON
    KICAD_SCRIPTING_MODULES=ON
    KICAD_SCRIPTING_WXPYTHON=OFF
    KICAD_SCRIPTING_ACTION_MENU=ON
    BUILD_GITHUB_PLUGIN=ON
    KICAD_USE_OCE=ON
    KICAD_USE_OCC=OFF
    KICAD_SPICE=OFF

[Aimylios (aimylios)]

I did some Google research and apparently this is a well known problem on Fedora 28, and not specific to KiCad. Hardening flags were added to the default build parameters, including _GLIBCXX_ASSERTIONS, which "turns on cheap range checks for C++ arrays, vectors, and strings" [1].

There is a minimal example how to trigger (and fix) this problem in the httpuv bug tracker [2]. Maybe this can help to fix this bug in KiCad as well.

[1] https://fedoraproject.org/wiki/Changes/HardeningFlags28
[2] https://github.com/rstudio/httpuv/issues/133#issuecomment-387499519

[Tomasz Wlostowski (twlostow)]

Can you send a full stack trace of this assert?

Tom

[Aimylios (aimylios)]

I'd love to do that, but gdb doesn't seem to like KiCad and segfaults. I have no idea why.

---

$ gdb kicad
GNU gdb (GDB) Fedora 8.1.1-3.fc28
[...]
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from kicad...Reading symbols from /usr/lib/debug/usr/bin/kicad-r13610.90788a5a7-nightly.fc28.x86_64.debug...done.
done.
Segmentation fault (Speicherabzug geschrieben)

[Tomasz Wlostowski (twlostow)]

Try lldb or Hopper. Maybe your system is so hardened it doesn't permit debugging ;-)

T.

[Aimylios (aimylios)]

OK, thanks for the tip, lldb seems to work. Is the following backtrace sufficient to locate the source of the problem?

---

/usr/include/c++/8/bits/stl_vector.h:932: std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::reference = int&; std::vector<_Tp, _Alloc>::size_type = long unsigned int]: Assertion '__builtin_expect(__n < this->size(), true)' failed.
Process 2771 stopped
* thread #1, name = 'kicad', stop reason = signal SIGABRT
    frame #0: 0x00007ffff34bbfeb libc.so.6`__GI_raise + 267
libc.so.6`__GI_raise:
-> 0x7ffff34bbfeb <+267>: movq 0x108(%rsp), %rcx
    0x7ffff34bbff3 <+275>: xorq %fs:0x28, %rcx
    0x7ffff34bbffc <+284>: movl %r8d, %eax
    0x7ffff34bbfff <+287>: jne 0x7ffff34bc01e ; <+318>
(lldb) bt
* thread #1, name = 'kicad', stop reason = signal SIGABRT
  * frame #0: 0x00007ffff34bbfeb libc.so.6`__GI_raise + 267
    frame #1: 0x00007ffff34a65c1 libc.so.6`__GI_abort + 299
    frame #2: 0x00007fffc95de38c _pcbnew.kiface`AR_AUTOPLACER::propagate() + 140
    frame #3: 0x00007fffc95de608 _pcbnew.kiface`AR_AUTOPLACER::genPlacementRoutingMatrix() + 424
    frame #4: 0x00007fffc95dfddb _pcbnew.kiface`AR_AUTOPLACER::AutoplaceModules(std::vector<MODULE*, std::allocator<MODULE*> >, BOARD_COMMIT*, bool) + 91
    frame #5: 0x00007fffc95e43e8 _pcbnew.kiface`AUTOPLACE_TOOL::autoplace(std::vector<MODULE*, std::allocator<MODULE*> >&, bool) + 936
    frame #6: 0x00007fffc95e4c70 _pcbnew.kiface`AUTOPLACE_TOOL::autoplaceOffboard(TOOL_EVENT const&) + 64
    frame #7: 0x00007fffc9cf14f4 _pcbnew.kiface`COROUTINE<int, TOOL_EVENT const&>::callerStub(long) + 68
    frame #8: 0x00007fffc9d4a131 _pcbnew.kiface`make_fcontext + 33

[Aimylios (aimylios)]

I have made a local build and gave gdb another shot. Fortunately it doesn't crash and this is the backtrace I get:

---

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

Thread 1 "kicad" received signal SIGABRT, Aborted.
0x00007ffff375afeb in raise () from /lib64/libc.so.6
(gdb) bt
#0 0x00007ffff375afeb in raise () at /lib64/libc.so.6
#1 0x00007ffff37455c1 in abort () at /lib64/libc.so.6
#2 0x00007fffcad12120 in std::__replacement_assert(char const*, int, char const*, char const*) (__file=0x7fffcb5ed0c0 "/usr/include/c++/8/bits/stl_vector.h", __line=932, __function=0x7fffcb5ed2e0 <std::vector<int, std::allocator<int> >::operator[](unsigned long)::__PRETTY_FUNCTION__> "std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](std::vector<_Tp, _Alloc>::size_type) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::reference = int&;"..., __condition=0x7fffcb5ed090 "__builtin_expect(__n < this->size(), true)")
    at /usr/include/c++/8/x86_64-redhat-linux/bits/c++config.h:2389
#3 0x00007fffcae3a409 in std::vector<int, std::allocator<int> >::operator[](unsigned long) (this=0x2e05820, __n=0) at /usr/include/c++/8/bits/stl_vector.h:932
#4 0x00007fffcaef1fbe in AR_AUTOPLACER::propagate() (this=0x2e05c60) at /home/xxx/kicad/pcbnew/autorouter/ar_autoplacer.cpp:241
#5 0x00007fffcaef1d53 in AR_AUTOPLACER::genPlacementRoutingMatrix() (this=0x2e05c60) at /home/xxx/kicad/pcbnew/autorouter/ar_autoplacer.cpp:167
#6 0x00007fffcaef4091 in AR_AUTOPLACER::AutoplaceModules(std::vector<MODULE*, std::allocator<MODULE*> >, BOARD_COMMIT*, bool) (this=0x2e05c60, aModules=std::vector of length 0, capacity 0,
    aCommit=0x2e05c00, aPlaceOffboardModules=true) at /home/xxx/kicad/pcbnew/autorouter/ar_autoplacer.cpp:889
#7 0x00007fffcaef9012 in AUTOPLACE_TOOL::autoplace(std::vector<MODULE*, std::allocator<MODULE*> >&, bool) (this=0x34636d0, aModules=std::vector of length 0, capacity 0, aPlaceOffboard=true)
    at /home/xxx/kicad/pcbnew/autorouter/autoplacer_tool.cpp:87
#8 0x00007fffcaef9301 in AUTOPLACE_TOOL::autoplaceOffboard(TOOL_EVENT const&) (this=0x34636d0, aEvent=...) at /home/xxx/kicad/pcbnew/autorouter/autoplacer_tool.cpp:116
#9 0x00007fffcaefc1f8 in std::__invoke_impl<int, int (AUTOPLACE_TOOL::*&)(TOOL_EVENT const&), AUTOPLACE_TOOL*&, TOOL_EVENT const&>(std::__invoke_memfun_deref, int (AUTOPLACE_TOOL::*&)(TOOL_EVENT const&), AUTOPLACE_TOOL*&, TOOL_EVENT const&) (__f=
    @0x2c046b0: (int (AUTOPLACE_TOOL::*)(AUTOPLACE_TOOL * const, const TOOL_EVENT &)) 0x7fffcaef92cc <AUTOPLACE_TOOL::autoplaceOffboard(TOOL_EVENT const&)>, __t=@0x2c046c0: 0x34636d0, __args#0=...) at /usr/include/c++/8/bits/invoke.h:73
#10 0x00007fffcaefc029 in std::__invoke<int (AUTOPLACE_TOOL::*&)(TOOL_EVENT const&), AUTOPLACE_TOOL*&, TOOL_EVENT const&>(int (AUTOPLACE_TOOL::*&)(TOOL_EVENT const&), AUTOPLACE_TOOL*&, TOOL_EVENT const&) (__fn=
  ...

[Jeff Young (jeyjey)]

If I'm reading the tea-leaves correctly, it looks like their hardener can't handle std::vector::reserve()/std::fill(). It's checking the index against size(), which isn't set by reserve() (or fill()).

We could probably fix it by replacing reserve()/fill() with resize().

[Jeff Young (jeyjey)]

@Aimylios, if you do your own builds could you try the attached patch and let us know if it fixes the problem?

[Jeff Young (jeyjey)]

I went ahead an merged the patch, as it shouldn't do any harm either way.

[Jeff Young (jeyjey)]

^an^and^

[Aimylios (aimylios)]

I just finished my tests with a local build of the master branch (commit dd228b60a) both with and without your patch, and I can confirm that it fixes the issue. Thank you!