Index construction fails with g++ version 9.3.0

[mikael-s]

When compiling REINDEER with g++ version 9.3.0 the index construction specified in the README fails with a double free error.

Command: ./Reindeer --index -f test/fof_unitigs.txt -o quick_out

Output:

Indexing k-mers...

Minitigs and index constuction...
Partition created       26,927 kmers read 
0.063319 seconds.
Monocolor monotig computed, now regular indexing start
0.125823 seconds.
Super buckets created: 0.197136 seconds.
----------------------INDEX RECAP----------------------------
Kmer in graph: 25,615
Super Kmer in graph: 4,361
Average size of Super Kmer: 5
Total size of the partitionned graph: 156,448
Largest MPHF: 115
Largest Bucket: 880
Size of the partitionned graph (MBytes): 0
Total Positions size (MBytes): 0
Size of the partitionned graph (bit per kmer): 12.2151
Total Positions size (bit per kmer): 1.58028
TOTAL Bits per kmer (without bbhash): 13.7954
TOTAL Bits per kmer (with bbhash): 17.7954
TOTAL Size estimated (MBytes): 0.0543391
Indexes created: 0.648137 seconds.
The whole indexing took me 0.837279 seconds.
Building colors and equivalence classes matrix to be written on disk...
free(): double free detected in tcache 2
Abandon

The backtrace is :

#0  __GI_raise (sig=sig@entry=6) at ../sysdeps/unix/sysv/linux/raise.c:50
#1  0x00007ffff7dfb55b in __GI_abort () at abort.c:79
#2  0x00007ffff7e53ff8 in __libc_message (action=action@entry=do_abort, fmt=fmt@entry=0x7ffff7f60f3e "%s\n") at ../sysdeps/posix/libc_fatal.c:181
#3  0x00007ffff7e5b39a in malloc_printerr (str=str@entry=0x7ffff7f62b90 "free(): double free detected in tcache 2") at malloc.c:5339
#4  0x00007ffff7e5d1dd in _int_free (av=0x7ffff7f92b80 <main_arena>, p=0x5555556c93c0, have_lock=0) at malloc.c:4201
#5  0x000055555557bb86 in __gnu_cxx::new_allocator<long>::deallocate (this=<optimized out>, __p=<optimized out>, this=<optimized out>, __p=<optimized out>) at src/utils.cpp:11
#6  std::allocator_traits<std::allocator<long> >::deallocate (__a=..., __n=<optimized out>, __p=<optimized out>, __a=..., __p=<optimized out>, __n=<optimized out>)
    at /usr/include/c++/9/bits/alloc_traits.h:470
#7  std::_Vector_base<long, std::allocator<long> >::_M_deallocate (this=<optimized out>, __n=<optimized out>, __p=<optimized out>, this=<optimized out>, __p=<optimized out>, 
    __n=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:351
#8  std::_Vector_base<long, std::allocator<long> >::~_Vector_base (this=<optimized out>, this=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:332
#9  std::vector<long, std::allocator<long> >::~vector (this=<optimized out>, this=<optimized out>) at /usr/include/c++/9/bits/stl_vector.h:680
#10 write_matrix_in_bucket_files (color_load_file=..., color_dump_file=..., fof=..., record_reads=<optimized out>, nb_threads=1, exact=false, 
    compressed_colors=std::vector of length 0, capacity 0, compressed_colors_size=std::vector of length 0, capacity 0, nb_colors=2, do_query_on_disk=false, output_file=..., 
    output="quick_out", color_number=@0x7ffffffd4b90: 0, k=31, record_counts=<optimized out>, ksl=0x7ffffffd5090) at src/build_index.cpp:64
#11 do_coloring (color_load_file=..., color_dump_file=..., fof=..., ksl=0x7ffffffd5090, record_counts=true, record_reads=<optimized out>, k=31, color_number=@0x7ffffffd4b90: 0, nb_threads=1, 
    exact=false, output="quick_out", compr_monotig_color=std::vector of length 0, capacity 0, compr_monotig_color_size=std::vector of length 0, capacity 0, do_query_on_disk=false, 
    nb_eq_class_file="", nb_color_file="", eq_class_nb=@0x7ffffffd4b98: 0, nb_colors=@0x7ffffffd4b8e: 2) at src/build_index.cpp:167
#12 0x000055555556f099 in build_index (color_dump_file="quick_out/reindeer_matrix", fof="test/fof_unitigs.txt", output="quick_out", m1=10, m2=10, m3=5, c=<optimized out>, bit=0, 
    nb_colors=<optimized out>, do_log=<optimized out>, quantize=<optimized out>, do_query_on_disk=false, exact=false, nb_threads=1, ksl=..., color_number=@0x7ffffffd4b90: 0, 
    record_reads=false, record_counts=true, color_load_file="", k=31) at src/build_index.cpp:227
#13 reindeer_index(unsigned int, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, bool, bool, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >&, unsigned int, bool, bool, bool, bool) [clone .constprop.0] (k=31, record_counts=<optimized out>, record_reads=<optimized out>, color_load_file=..., threads=<optimized out>, exact=<optimized out>, 
    do_query_on_disk=<optimized out>, quantize=<optimized out>, do_log=<optimized out>, output="quick_out", color_dump_file="quick_out/reindeer_matrix", fof="test/fof_unitigs.txt")
    at src/reindeer.cpp:26
#14 0x00005555555606f4 in main (argc=<optimized out>, argv=0x7fffffffda78) at main.cpp:210

Which (unexpectedly) points to src/build_index.cpp:64:

        vector<int64_t> monotig_id;

Workaround index construction succeeds when compiled with g++ version 8 or 10. It also succeeds with g++ 9 when compiling with -O2 instead of -Ofast (eg. sed -i 's/Ofast/O2/g' makefile)

[rchikhi]

nicely spotted!

[rchikhi]

could be identified with https://developers.redhat.com/blog/2020/03/26/static-analysis-in-gcc-10/

[mikael-s]

Here is the (lengthy) report produced with -fanalyzer and g++ 10, after eating more than 20GB of RAM

[rchikhi]

nice! worth it. Double frees are at the end and one is

src/../blight/bmalloc.h:99:15: warning: double-‘free’ of ‘_6’ [CWE-415] [-Wanalyzer-double-free]
   99 |         ::free(p);
      |               ^
  ‘__dt_base ’: events 1-5
    |
    |src/../blight/bmbuffer.h:282:9:
    |  280 |     void free_buffer()
    |      |          ~
    |      |          |
    |      |          (3) first ‘free’ here
    |  281 |     {
    |  282 |         if (byte_buf_)
    |      |         ^
    |      |         |
    |      |         (1) following ‘true’ branch...
    |      |         (4) following ‘true’ branch...
    |  283 |         {
    |  284 |             allocator_type::deallocate((bm::word_t*)byte_buf_, alloc_factor_);
    |      |                                       ~
    |      |                                       |
    |      |                                       (2) ...to here
    |      |                                       (5) ...to here
    |
  ‘__dt_base ’: event 6
    |
    |src/../blight/bmalloc.h:99:15:
    |   99 |         ::free(p);
    |      |               ^
    |      |               |
    |      |               (6) second ‘free’ here; first ‘free’ was at (3)
    |