robin-map: Hash Map Insert Stuck in an infinite loop

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