Hash Map Insert Stuck in an infinite loop

[szhang0119]

Hi, there,

We used the robin-map/v0.6.1, and we observed the robin map stuck in an infinite loop here in insert_value_impl method.

We created tsl::robin_map<uint64_t, DataBlock*>, and we inserted monotonically increasing keys like: 0xc000000000001, 0xc000000000002, etc. We do not have concurrent modifications on the robin map.

We observed this issue both on Intel and ARM machines, but ARM machines showed up more often. However, we do not have a good reproducer, and we only observed this issue in our production fleet.

Could any one help us debug a bit to see if anything pops out? Any suggestions would be appreciated!

Thanks very much!

---

Here are some debug information we gathered.

The robin map has 8 buckets, but the number of elements are only 5 (although all 8 keys look valid to us). However, we observed a really large m_load_threshold = 18446744069414584320, and all 8 buckets show with m_dist_from_ideal_bucket = 32767.

We suspected somehow m_load_threshold overflowed, causing the robin map would not expand the size, and hence there are no empty buckets in the map anymore.

(gdb) p *this 
$35 = {<std::hash<unsigned long>> = {<std::__hash_base<unsigned long, unsigned long>> = {<No data fields>}, <No data fields>}, <std::equal_to<unsigned long>> = {<std::binary_function<unsigned long, unsigned long, bool>> = {<No data fields>}, <No data fields>}, <tsl::rh::power_of_two_growth_policy<2>> = {m_mask = 7}, 
  static STORE_HASH = false, static USE_STORED_HASH_ON_LOOKUP = false, static DEFAULT_INIT_BUCKETS_SIZE = 0, static DEFAULT_MAX_LOAD_FACTOR = 0.5, 
  static MINIMUM_MAX_LOAD_FACTOR = 0.200000003, static MAXIMUM_MAX_LOAD_FACTOR = 0.949999988, static DEFAULT_MIN_LOAD_FACTOR = 0, static MINIMUM_MIN_LOAD_FACTOR = 0, 
  static MAXIMUM_MIN_LOAD_FACTOR = 0.150000006, static REHASH_ON_HIGH_NB_PROBES__NPROBES = 128, static REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR = 0.150000006, 
  m_buckets_data = {<std::_Vector_base<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false>, std::allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> > >> = {
      _M_impl = {<std::allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> >> = {<__gnu_cxx::new_allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> >> = {<No data fields>}, <No data fields>}, _M_start = 0x40006630f040, 
        _M_finish = 0x40006630f100, _M_end_of_storage = 0x40006630f100}}, <No data fields>}, m_buckets = 0x40006630f040, m_bucket_count = 8, m_nb_elements = 5, 
  m_load_threshold = 18446744069414584320, m_max_load_factor = 0.5, m_grow_on_next_insert = true, m_min_load_factor = 0, m_try_skrink_on_next_insert = false}

(gdb) p m_buckets[0]
$36 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = false, m_value = {__data = "\t\000\000\000\000\000\f\000\000\000\000\000\000\000\000", __align = {<No data fields>}}}
(gdb) p m_buckets[1]
$37 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = false, m_value = {__data = "\002\000\000\000\000\000\f\000\340R\304#\v@\000", __align = {<No data fields>}}}
(gdb) p m_buckets[2]
$38 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = false, m_value = {__data = "\003\000\000\000\000\000\f\000\320P\304#\v@\000", __align = {<No data fields>}}}
(gdb) p m_buckets[3]
$39 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = false, m_value = {__data = "\004\000\000\000\000\000\f\000А?\034\v@\000", __align = {<No data fields>}}}
(gdb) p m_buckets[4]
$40 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = false, m_value = {__data = "\005\000\000\000\000\000\f\000\000\221?\034\v@\000", __align = {<No data fields>}}}
(gdb) p m_buckets[5]
$41 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = false, m_value = {__data = "\006\000\000\000\000\000\f\000\300$Fe\000@\000", __align = {<No data fields>}}}
(gdb) p m_buckets[6]
$42 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = false, m_value = {__data = "\a\000\000\000\000\000\f\000\240&Fe\000@\000", __align = {<No data fields>}}}
(gdb) p m_buckets[7]
$43 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, m_dist_from_ideal_bucket = 32767, 
  m_last_bucket = true, m_value = {__data = "\b\000\000\000\000\000\f\000\340\033Re\000@\000", __align = {<No data fields>}}}

Here are the list of keys in the map:

(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[0].m_value.__data)
$14 = 0xc000000000009
(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[1].m_value.__data)
$15 = 0xc000000000002
(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[2].m_value.__data)
$16 = 0xc000000000003
(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[3].m_value.__data)
$17 = 0xc000000000004
(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[4].m_value.__data)
$18 = 0xc000000000005
(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[5].m_value.__data)
$19 = 0xc000000000006
(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[6].m_value.__data)
$20 = 0xc000000000007
(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[7].m_value.__data)
$21 = 0xc000000000008

[Tessil]

Thank you for the report.

From a first glance I have troubles to understand how m_load_threshold ends up with such a large value. The only place where the variable is set (outside of copy/move constructor/operator and swap) is in max_load_factor and the value there is bounded by m_bucket_count and the clamped between [0.1;0.95] m_max_load_factor. As the m_bucket_count has a normal value of 8 and the m_max_load_factor is 0.5, m_load_threshold should be equal to 4. How does it end up with such value? The copy/move constructor/operator and swap seem correct. Could there be a memory bug somewhere in the implementation that somehow overrides the memory where m_load_threshold is?

I'll try to investigate more when I have some time.

In the meantime could you eventually try the latest version and define the TSL_DEBUG variable with assert enabled (so NDEBUG not defined)? It'll enable the assertions in the project and we might catch something with them.

[Tessil]

I really can't find how m_load_threshold could overflow like that considering how the variable is assigned. Could some parts of the program that uses the library write to some wrong memory locations? Could you try to compile it with the AddressSanitizer or run it with valgrind?

I'll try to investigate more as it's a worrying bug. Please let me know if you can eventually reproduce the problem in a self-contained example. Thanks.

[markpapadakis]

I have experienced the issue multiple times in the past which effectively prevents us from using this map implementation. I thought I filed an issue about this but looks like I haven't. It would be great if this is resolved.

[Tessil]

Thank you, I'll try to get a more in depth look then as it's really worrying if you also had the problem.

I have tried to insert the keys mentioned above in every way possible + tried with some extra ones and I can't reproduce the problem. If any of you eventually has a reproducible self-contained example it'd be immensely useful.

[markpapadakis]

I can reproduce it, but it is practically impossible to share the code (its for out embeddable columnar store thing, that's not OSS). Certain SQL queries would cause this -- tried every sanitizer, nothing came up really (so almost certainly not a corruption). Had this issue with other programs (our application server, some other utilities etc) -- but I unfortunately can't share that codebase either. It is almost certainly not a matter of some memory corruption/buffer overrun issue though.

[Tessil]

Thank you very much for the useful infos. I'll look more into depth then as I currently can't understand how m_load_threshold could end up with a value of 18446744069414584320.

[szhang0119]

In our tests, we also saw a different stuck stack.

In this case, m_bucket_count=0, and it stuck in a different while loop here.

Here is some gdb information:

(gdb) p *this
$2 = {<std::hash<unsigned long>> = {<std::__hash_base<unsigned long, unsigned long>> = {<No data fields>}, <No data fields>}, <std::equal_to<unsigned long>> = {<std::binary_function<unsigned long, unsigned long, bool>> = {<No data fields>}, <No data fields>}, <tsl::rh::power_of_two_growth_policy<2>> = {m_mask = 0}, static STORE_HASH = false, static USE_STORED_HASH_ON_LOOKUP = false, static DEFAULT_INIT_BUCKETS_SIZE = 0, 
  static DEFAULT_MAX_LOAD_FACTOR = 0.5, static MINIMUM_MAX_LOAD_FACTOR = 0.200000003, static MAXIMUM_MAX_LOAD_FACTOR = 0.949999988, 
  static DEFAULT_MIN_LOAD_FACTOR = 0, static MINIMUM_MIN_LOAD_FACTOR = 0, static MAXIMUM_MIN_LOAD_FACTOR = 0.150000006, 
  static REHASH_ON_HIGH_NB_PROBES__NPROBES = 128, static REHASH_ON_HIGH_NB_PROBES__MIN_LOAD_FACTOR = 0.150000006, 
  m_buckets_data = {<std::_Vector_base<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false>, std::allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> > >> = {
      _M_impl = {<std::allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> >> = {<__gnu_cxx::new_allocator<tsl::detail_robin_hash::bucket_entry<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, false> >> = {<No data fields>}, <No data fields>}, _M_start = 0x0, _M_finish = 0x0, _M_end_of_storage = 0x0}}, <No data fields>}, 
  m_buckets = 0x400a4d6e2010 <tsl::detail_robin_hash::robin_hash<std::pair<unsigned long, MapGraph::Blocks::DataBlock*>, tsl::robin_map<unsigned long, MapGraph::Blocks::DataBlock*, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<std::pair<unsigned long, MapGraph::Blocks::DataBlock*> >, false, tsl::rh::power_of_two_growth_policy<2ul> >::KeySelect, tsl::robin_map<unsigned long, MapGraph::Blocks::DataBlock*, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<std::pair<unsigned long, MapGraph::Blocks::DataBlock*> >, false, tsl::rh::power_of_two_growth_policy<2ul> >::ValueSelect, std::hash<unsigned long>, std::equal_to<unsigned long>, std::allocator<std::pair<unsigned long, MapGraph::Blocks::DataBlock*> >, false, tsl::rh::power_of_two_growth_policy<2ul> >::static_empty_bucket_ptr()::empty_bucket>, m_bucket_count = 0, m_nb_elements = 0, 
  m_load_threshold = 0, m_max_load_factor = 0.5, m_grow_on_next_insert = false, m_min_load_factor = 0, m_try_skrink_on_next_insert = false}

Since the m_bucket_count is 0, the below information does not quite make sense. But I just want to show m_dist_from_ideal_bucket is also MAX_SHORT.

(gdb) p/x *reinterpret_cast<uint64_t*>(m_buckets[0].m_value.__data)
$4 = 0x2a000000000002
(gdb) p m_buckets[0]
$5 = {<tsl::detail_robin_hash::bucket_entry_hash<false>> = {<No data fields>}, static EMPTY_MARKER_DIST_FROM_IDEAL_BUCKET = -1, 
  m_dist_from_ideal_bucket = 32767, m_last_bucket = true, m_value = {__data = "\002\000\000\000\000\000*\000\000\000\000\000\000\000\000", 
    __align = {<No data fields>}}}

---

We also tried to upgrade to latest version (v1.0.1), but can still see the above stuck stacks in our tests.

[gabrieltanase42]

Hi Tessil; I am from same team with Song. For us the bug occurs rarely and there is always an infinite loop. We suspected that maybe some memory corruption on our side may mess robin map memory and cause teh infinite loop and we spent already two weeks investigating this. What is specific to our case is that in a highly multithreaded scenario each thread creates, inserts and destroys teh map. We do guard with mutexes the operations on map as the datastructure itself is not thread safe.

So now I wonder : do you in your tests also have this scenario where we create map/insert elements/delete map in a loop ; and maybe from lots of threads (each thread creates, inserts and destroy its own robin map). Maybe there is an issue on the delete part which I am thinking may not be heavily tested???

At this point we started replacing the robin map with STL unordered to see if we observe any hangs anymore :(

[markpapadakis]

For what it's worth, in cases where it fails, we don't erase any KVs. It's all insertions. It occurs when inserting elements.

[markpapadakis]

Also, we experimented with various many different hash maps implementations. None of them failed so it's perhaps safe to suggest that the issue's
specific to this implementation.

[Tessil]

Thanks all for the information.

I was not able to reproduce the problem but I looked carefully through the implementation. I couldn't find a problem in the insertion logic of the code but I noticed that the library can invoke some undefined behaviour with C++17.

P0137R1 introduced a change in the object model in C++17 which now requires to std::launder the reinterpreted pointer from std::aligned_storage. From my understanding and the discussion I have read, the change seems to be backward incompatible and could potentially make previously well-defined code become undefined. See the following discussion for some interesting details: https://stackoverflow.com/questions/47735657/does-reinterpret-casting-stdaligned-storage-to-t-without-stdlaunder-violat and https://groups.google.com/a/isocpp.org/g/std-discussion/c/xaAwFR6qUmY

I have fixed the problem with commit 4abcc97, could you try these latests changes? It may not be the reason of the bug you encounter but it would be tremendously useful for me to at least try as I can't reproduce the problem myself.

I also added some extra assertions so running the code with TSL_DEBUG defined and assertions enabled may also help to pinpoint the problem.

Sorry for the caused inconveniences.

[gabrieltanase42]

@markpapadakis Do you think you can try this patch and confirm that it fixes your problem. Now I am in the middle of replacing and benchmarking with an alternative. Also for some weird reason for us I need to let the server run with a constant load for a week or more before I notice a query stuck in infinite loop inside robin map.

[markpapadakis]

@gabrieltanase42: I just tried this commit and still fails.

[thompsonbry]

I am with the same team as Gabi. We were not using c++17 when we observed the problem. We have only been able to reproduce this in multi-day tests of the integrated software stack. We lack a clean reproducer based on a simple set of inputs and some sequence of their presentation. We do use a lock to guard access to the map from multiple threads in the code where we are observing the problem. We have only observed this for relatively small maps with numerically ordered keys which should be presented more or less in order (there might be some races involved, but there is a guarding lock).

We have also been using the robin map for several years in hash joins and have never observed an issue with that code. However, unless there is something very odd about the case where the map is behind a lock, we have to assume that we can encounter the same issue when building a hash index for a join.

[Tessil]

So I reviewed all the code of the library to check any eventual problem and I couldn't find anything really suspicious.

One part that could be problematic in a pre-C++11 multi-threaded program is the static initialization in https://github.com/Tessil/robin-map/blob/master/include/tsl/robin_hash.h#L1590 But it's thread-safe in C++11 and forward and this static variable is never modified once initialized. There are no other non-const shared variables.

Another slight doubt I have is the const_cast in https://github.com/Tessil/robin-map/blob/master/include/tsl/robin_hash.h#L1108 but as pos.m_bucket should always point to the non-const m_buckets_data/m_buckets or the end of it, it should be perfectly safe to cast-away the constness of it in non-const methods. One alternative would be to use the slower return iterator(m_buckets + (pos.m_bucket - m_buckets));.

I have not been able to reproduce the bug in a non-threaded program. I'll try to run some tests in a multi-threaded one as it seems it's a common premise both @szhang0119 and @markpapadakis have and maybe the static_empty_bucket_ptr has something to do with it.