Assertion `get_segment(i) < allocated_segments_' failed

[jxiw]

There is a member variable in a class, defined as cuckoohash_map<Key, std::shared_ptr, CityHasher> versions.

I try to call versions.find(key, ret). However I got "Assertion `get_segment(i) < allocated_segments_' failed". Can you give me some hints about why it happens? Thank you.

[manugoyal]

Hi @ovss! I think this could be a bug in the table. Would you be able to provide a stack trace, or ever better a short code sample that re-produces the issue?

[jxiw]

I expect to implement a thrift non-blocking server with a thread pool.
The stack trace is

0x000000000040d2b0 in std::_Base_bitset<1ul>::_M_getword (this=0x7ffff613b0d8) at /usr/include/c++/5/bitset:411
411 { return _M_w; }

#0 0x000000000040d2b0 in std::_Base_bitset<1ul>::_M_getword (this=0x7ffff613b0d8) at /usr/include/c++/5/bitset:411
#1 0x0000000000411230 in std::bitset<4ul>::_Unchecked_test (this=0x7ffff613b0d8, __pos=0) at /usr/include/c++/5/bitset:1058
#2 0x0000000000411273 in std::bitset<4ul>::operator[] (this=0x7ffff613b0d8, __position=0) at /usr/include/c++/5/bitset:1160
#3 0x00000000004115eb in cuckoohash_map<long, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >, CityHasher, std::equal_to, std::allocator<std::pair<long const, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > > >, 4ul>::Bucket::occupied (this=0x7ffff613b0d0, ind=0)
at /home/jwang/include/libcuckoo/cuckoohash_map.hh:922
#4 0x0000000000410d6e in cuckoohash_map<long, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >, CityHasher, std::equal_to, std::allocator<std::pair<long const, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > > >, 4ul>::try_read_from_bucket (this=0x686328, b=...,
partial=240 '\360', key=@0x7ffff2f6d898: 50001) at /home/jwang/include/libcuckoo/cuckoohash_map.hh:1105
#5 0x000000000040f3a7 in cuckoohash_map<long, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >, CityHasher, std::equal_to, std::allocator<std::pair<long const, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > > >, 4ul>::cuckoo_find (this=0x686328, key=@0x7ffff2f6d898: 50001,
partial=240 '\360', i1=64588, i2=6409) at /home/jwang/include/libcuckoo/cuckoohash_map.hh:1086
#6 0x000000000040ea33 in cuckoohash_map<long, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >, CityHasher, std::equal_to, std::allocator<std::pair<long const, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > > >, 4ul>::find_fn<long, bool cuckoohash_map<long, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >, CityHasher, std::equal_to, std::allocator<std::pair<long const, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > > >, 4ul>::find(long const&, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >&) const::{lambda(std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > const&)#1}>(long const&, bool cuckoohash_map<long, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >, CityHasher, std::equal_to, std::allocator<std::pair<long const, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > > >, 4ul>::find(long const&, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >&) const::{lambda(std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > const&)#1}) const (
this=0x686328, key=@0x7ffff2f6d898: 50001, fn=...) at /home/jwang/include/libcuckoo/cuckoohash_map.hh:305
#7 0x000000000040dc2d in cuckoohash_map<long, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator<---Type to continue, or q to quit---
char> > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > >, CityHasher, std::equal_to, std::allocator<std::pair<long const, std::unordered_set<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::hash<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > > >, 4ul>::find (this=0x686328, key=@0x7ffff2f6d898: 50001,
val=std::unordered_set with 0 elements) at /home/jwang/include/libcuckoo/cuckoohash_map.hh:411

[jxiw]

Let me specify the problem. I try to implement a concurrency control protocol on top of thrift non-blocking server. To keep track the write key set of the transaction, I use a variable, as cuckoohash_map<TransactionId, std::unordered_set, CityHasher> write_key.
Thus this variable is shared by all the thrift server threads (normally I set 100).

And I invoke function write_key.find(tid, key_set);
Then the exception appears. The stack trace is shown before.

Thank you.

[manugoyal]

I see. Sorry for the late reply. I'm currently rewriting some of the locking code, which might fix your issue. I'll let you know when I have an update merged into master. Thanks!

[manugoyal]

Could you try the latest version of master?

[jxiw]

I try the least version of master and I got the following error.

#0 0x00000000004159fc in std::atomic_flag::test_and_set (__m=std::memory_order_acq_rel, this=0x1195c0) at /usr/include/c++/5/bits/atomic_base.h:176
No locals.
#1 cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::spinlock::lock (this=0x1195c0)
at /home/jwang/install/include/libcuckoo/cuckoohash_map.hh:575
No locals.
#2 0x000000000041322b in cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::lock_two (this=0x68d328, hp=140737291722768, i1=55025,
i2=18007) at /home/jwang/install/include/libcuckoo/cuckoohash_map.hh:698
l1 = 18007
l2 = 55025
locks = std::vector of length 0, capacity 0
#3 0x0000000000410dc9 in cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::snapshot_and_lock_two<std::integral_constant<bool, false> > (this=0x68d328, hv=...) at /home/jwang/install/include/libcuckoo/cuckoohash_map.hh:759
hp = 140737291722768
i1 = 55025
i2 = 18007
#4 0x00000000004115ee in cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::find_fn<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, bool cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::find<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >(std::__cxx11::basic_string<char, std::char_traits, std::allocator > const&, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >&) const::{lambda(std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > const&)#1}>(std::__cxx11::basic_string<char, std::char_traits, std::allocator > const&, bool cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::find<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >(std::_cxx11::basic_string<char, std::char_traits, std::allocator > const&, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >&) const::{lambda(std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > const&)#1}) const (this=0x68d328, key="fa37", fn=...)
at /home/jwang/install/include/libcuckoo/cuckoohash_map.hh:276
hv = {hash = 8140040866657064689, partial = 141 '\215'}
b = {i1 = 0, i2 = 0,
first_manager = std::unique_ptr<cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::_cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::spinlock> containing 0x7ffff1a6bb20,
second_manager = std::unique_ptr<cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::spinlock> containing 0x18}
pos = {index = 140737247623376, slot = 140737354116324, status = 4054235392}
#5 0x000000000040f713 in cuckoohash_map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > >, CityHasher<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::equal_to<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::pair<LockOperation, std::shared_ptr<std::unordered_set<long, std::hash, std::equal_to, std::allocator > > > > >, 4ul>::find<std::__cxx11::basic_string<char, std::char_traits, std::allocator > > (this=0x68d328, key="fa37", val=...) at /home/jwang/install/include/libcuckoo/cuckoohash_map.hh:375
No locals.

[manugoyal]

This looks like some sort of memory corruption. I noticed one of your locals read hp=140737291722768, which would mean the size of the table is 2^140737291722768 elements (obviously unreasonably large).

Are you perhaps rehashing the table to a very large value, or somehow letting the table grow too large? Would you mind pasting the code you ran that reproduces the issue?

Thanks!

[manugoyal]

Closing this for now. Let me know if you're still having issues.