Segfault in bucket_container copy constructor

[robomics]

The following code snipped (which is a slight modification of the hellohash example) causes a SEGV when $iters \ge 327672$

#include <iostream>
#include <string>
#include <cassert>

#include <libcuckoo/cuckoohash_map.hh>

void test(int iters) {
  using Table = libcuckoo::cuckoohash_map<int, std::string>;

  Table table1{};

  for (int i = 0; i < iters; i++) {
    table1.insert(i, "found");
  }

  const auto table2 = table1;  // Segfaults occurs here when iters >= 327672

  {
    Table tmp{};
    std::swap(tmp, table1);
  }

  std::string out;
  for (int i = 0; i < iters + 10; i++) {
    assert(table2.find(i, out) == i < iters);
  }
}

int main() {
  const int i0 = 327670;
  const int i1 = 327680;
  for (int iters = i0; iters < i1; ++iters) {
    std::cerr << "Testing w/ iters=" << iters << "...";
    test(iters);
    std::cerr << " OK!\n";
  }
}

Compiling the code with ASAN reveals that the segfaults happens at bucker_container.hh:328 when checking if a bucket is occupied.

I am afraid I know too little about libcuckoo internals to further debug this issue, but I couldn't help to notice that $\frac{327672 + 8}{8192} = 40$.

All the above was tested on a Linux machine, compiling the code with gcc 12.1.0 and clang 13.0.1.

ASAN backtrace

``` Testing w/ iters=327670... OK! Testing w/ iters=327671... OK! Testing w/ iters=327672...AddressSanitizer:DEADLYSIGNAL ================================================================= ==3158150==ERROR: AddressSanitizer: SEGV on unknown address 0x0000000000a4 (pc 0x5588b53274fd bp 0x7fffb7de0e20 sp 0x7fffb7de0d10 T0) ==3158150==The signal is caused by a READ memory access. ==3158150==Hint: address points to the zero page. #0 0x5588b53274fd in libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul>::bucket* libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul>::transfer(unsigned long, std::conditional, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul>&, libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul> const&>::type, std::integral_constant) /tmp/libcuckoo/libcuckoo/bucket_container.hh:328 #1 0x5588b5325bf4 in libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul>::bucket_container(libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul> const&) /tmp/libcuckoo/libcuckoo/bucket_container.hh:130 #2 0x5588b5324e22 in libcuckoo::cuckoohash_map, std::allocator >, std::hash, std::equal_to, std::allocator, std::allocator > > >, 4ul>::cuckoohash_map(libcuckoo::cuckoohash_map, std::allocator >, std::hash, std::equal_to, std::allocator, std::allocator > > >, 4ul> const&) /tmp/libcuckoo/libcuckoo/cuckoohash_map.hh:148 #3 0x5588b532389c in test(int) /tmp/libcuckoo/examples/hellohash.cc:16 #4 0x5588b5323e10 in main /tmp/libcuckoo/examples/hellohash.cc:34 #5 0x7fd9e421f28f (/usr/lib/libc.so.6+0x2928f) #6 0x7fd9e421f349 in __libc_start_main (/usr/lib/libc.so.6+0x29349) #7 0x5588b53234f4 in _start (/tmp/libcuckoo/cmake-build-debug-asan/examples/hellohash+0x314f4) AddressSanitizer can not provide additional info. SUMMARY: AddressSanitizer: SEGV /tmp/libcuckoo/libcuckoo/bucket_container.hh:328 in libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul>::bucket* libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul>::transfer(unsigned long, std::conditional, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul>&, libcuckoo::bucket_container, std::allocator >, std::allocator, std::allocator > > >, unsigned char, 4ul> const&>::type, std::integral_constant) ==3158150==ABORTING ```

[manugoyal]

Thanks for finding this! Turns out we were missing the logic for copying a bucket_container after it had been deallocated (in which case the copied container should also be "deallocated"). Fixed in cff72f146687b4252e771c5de69c4f4e2a85abac.

[robomics]

Thanks for the quick fix!

Would you mind making a release/tag the latest commit?

About a week ago I submitted a package for libcuckoo to Conan (link), and they require a tagged version to submit/update a package.

[manugoyal]

No problem, just added a tag for v0.3.1 here: https://github.com/efficient/libcuckoo/releases/tag/v0.3.1.