gvinciguerra / PGM-index

🏅State-of-the-art learned data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes
https://pgm.di.unipi.it/
Apache License 2.0
775 stars 91 forks source link

fixed crash on indexing PGM #37

Closed tomatolog closed 2 years ago

tomatolog commented 2 years ago

I've just fixed crash on build PGM index with short vector with only one large value

Seems similar issue was already fixed at #23 however not all cases got covered. I've just refactored that fix to cover more cases.

I also added test case named PGM-index out of bonds to tests that crashes on building PGM index prior to fix and passed well after fix.

tomatolog commented 2 years ago

Here is a BT from the GDB at the crash event

#0  0x00000000004c88ae in pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::build<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, unsigned long, unsigned long, std::vector<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment, std::allocator<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment> >&, std::vector<unsigned long, std::allocator<unsigned long> >&)::{lambda(auto:1, auto:2, auto:3)#1}::operator()<unsigned long, pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::build<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, unsigned long, unsigned long, std::vector<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment, std::allocator<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment> >&, std::vector<unsigned long, std::allocator<unsigned long> >&)::{lambda(auto:1)#1}, pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::build<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, unsigned long, unsigned long, std::vector<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment, std::allocator<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment> >&, std::vector<unsigned long, std::allocator<unsigned long> >&)::{lambda(auto:1)#2}>(unsigned long, pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::build<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, unsigned long, unsigned long, std::vector<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment, std::allocator<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment> >&, std::vector<unsigned long, std::allocator<unsigned long> >&)::{lambda(auto:1)#1}, pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::build<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, unsigned long, unsigned long, std::vector<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment, std::allocator<pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::Segment> >&, std::vector<unsigned long, std::allocator<unsigned long> >&)::{lambda(auto:1)#2}) const (this=0x7ffea33e49b8, epsilon=64, in_fun=..., out_fun=...) at /sysroot/root/PGM-index/include/pgm/pgm_index.hpp:99
#1  0x00000000004c86eb in pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::build<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > > (first=4294967295, last=4294967295, epsilon=64, epsilon_recursive=4, segments=std::vector of length 0, capacity 0,
    levels_offsets=std::vector of length 1, capacity 1 = {...}) at /sysroot/root/PGM-index/include/pgm/pgm_index.hpp:117
#2  0x00000000004c797f in pgm::PGMIndex<unsigned int, 64ul, 4ul, float>::PGMIndex<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > > (this=0x7ffea33e4af0, first=4294967295, last=0) at /sysroot/root/PGM-index/include/pgm/pgm_index.hpp:184
#3  0x00000000003b6a0a in ____C_A_T_C_H____T_E_S_T____32 () at /sysroot/root/PGM-index/test/tests.cpp:282
#4  0x00000000002ff543 in Catch::TestInvokerAsFunction::invoke (this=0x2489a80) at /sysroot/root/PGM-index/test/catch.hpp:14222

along with variables

(gdb) p segments
$3 = std::vector of length 0, capacity 0
(gdb) p last_n
$4 = (unsigned long &) @0x7ffea33e49d0: 0
gvinciguerra commented 2 years ago

Thanks a lot!