folly::ConcurrentHashMap crashes under high contention

[DanielLiamAnderson]

When under significant contention and with a specific key distribution, folly::ConcurrentHashMap fails checks inside HazptrObjLinked.h. I've reproduced this on multiple machines.

OS: Ubuntu 20.04.6 LTS (reproduced on Ubuntu 22.04)
Compiler: GCC 13.1.0 (reproduced on GCC 11.4.0)

The following minimal reproducible example consistently reproduces the bug.

#include <cmath>
#include <cstdint>

#include <latch>
#include <limits>
#include <random>
#include <thread>
#include <vector>

#include <folly/concurrency/ConcurrentHashMap.h>
#include <folly/init/Init.h>


struct KeyDist {

  KeyDist(uint64_t num_items, double zipfian_const) :
      items_(num_items), theta_(zipfian_const), zeta_n_(num_items) {
    zeta_2_ = Zeta(2, theta_);
    zeta_n_ = Zeta(num_items, theta_);
    alpha_ = 1.0 / (1.0 - theta_);
    eta_ = Eta();
  }

  uint64_t operator () (size_t i) const {
    uint64_t r = hash64(i);
    double u = static_cast<double>(r) / static_cast<double>(std::numeric_limits<uint64_t>::max()); // uniform between 0.0 and 1.0
    double uz = u * zeta_n_;
    if (uz < 1.0) return 0;
    if (uz < 1.0 + std::pow(0.5, theta_)) return 1;
    return std::lround((items_-1) * std::pow(eta_ * u - eta_ + 1, alpha_));
  }

  double Eta() {
    return (1 - std::pow(2.0 / items_, 1 - theta_)) / (1 - zeta_2_ / zeta_n_);
  }

  static uint64_t hash64(uint64_t u) {
    uint64_t v = u * 3935559000370003845ul + 2691343689449507681ul;
    v ^= v >> 21;
    v ^= v << 37;
    v ^= v >> 4;
    v *= 4768777513237032717ul;
    v ^= v << 20;
    v ^= v >> 41;
    v ^= v << 5;
    return v;
  }

  static double Zeta(uint64_t cur_num, double theta) {
    double result = 0.0;
    for (int i = 0; i < cur_num; i++) {
      result += 1.0/ std::pow(i+1, theta);
    }
    return result;
  }

  uint64_t items_;
  double theta_, zeta_n_, eta_, alpha_, zeta_2_;
};


int main(int argc, char* argv[]) {

  // Should be set to a number much larger than the number of hardware threads
  constexpr unsigned num_threads = 100;

  folly::Init init(&argc, &argv);

  std::vector<std::jthread> threads;
  threads.reserve(num_threads);
  
  KeyDist z(100000, 0.99);
  
  folly::ConcurrentHashMap<long, long> T;
  
  std::latch start{num_threads};
  for (int i = 0; i < num_threads; i++) {
    threads.emplace_back([&, i]() {
      start.arrive_and_wait();
      long result = 0;
      for (int j = 0; j < 1000000; j++) {
        int key = z(j);
        if (j % 3 == 0) {
          auto v = T.find(key);
          if (v != T.end()) result += v->second;
        }
        else if (j % 3 == 1) {
          result += T.insert(std::make_pair(key, i)).second;
        }
        else {
          result += T.erase(key);
        }
      }
    });
  }
  
  for (auto& t : threads) {
    t.join();
  }
}

This outputs the following:

F1112 21:58:34.663033 12469 HazptrObjLinked.h:121] Check failed: oldval & kLinkMask < kLinkMask (4294901760 vs. 4294901760)
*** Check failure stack trace: ***
*** Aborted at 1699844314 (Unix time, try 'date -d @1699844314') ***
*** Signal 6 (SIGABRT) (0x3e8000030a8) received by PID 12456 (pthread TID 0x7feda4ed6640) (linux TID 12469) (maybe from PID 12456, UID 1000) (code: -6), stack trace: ***
./a.out(+0x2015a3)[0x557cafaeb5a3]
./a.out(+0x1bed9a)[0x557cafaa8d9a]
./a.out(+0x1bd1cf)[0x557cafaa71cf]
./a.out(+0x1bd2b6)[0x557cafaa72b6]
/lib/x86_64-linux-gnu/libc.so.6(+0x4251f)[0x7fedaaf7551f]
/lib/x86_64-linux-gnu/libc.so.6(pthread_kill+0x12c)[0x7fedaafc9a7c]
/lib/x86_64-linux-gnu/libc.so.6(raise+0x15)[0x7fedaaf75475]
/lib/x86_64-linux-gnu/libc.so.6(abort+0xd2)[0x7fedaaf5b7f2]
./a.out(+0x512fc)[0x557caf93b2fc]
/lib/x86_64-linux-gnu/libglog.so.0(_ZN6google10LogMessage4FailEv+0x12)[0x7fedab55eb02]
/lib/x86_64-linux-gnu/libglog.so.0(_ZN6google10LogMessage9SendToLogEv+0xb80)[0x7fedab5669d0]
/lib/x86_64-linux-gnu/libglog.so.0(_ZN6google10LogMessage5FlushEv+0xd1)[0x7fedab55e7c1]
/lib/x86_64-linux-gnu/libglog.so.0(_ZN6google15LogMessageFatalD2Ev+0xe)[0x7fedab56078e]
./a.out(+0x19108)[0x557caf903108]
/lib/x86_64-linux-gnu/libstdc++.so.6(+0xe62b2)[0x7fedab34c2b2]
/lib/x86_64-linux-gnu/libc.so.6(+0x94b42)[0x7fedaafc7b42]
/lib/x86_64-linux-gnu/libc.so.6(+0x1269ff)[0x7fedab0599ff]
(safe mode, symbolizer not available)
Aborted

We initially encountered this bug while running our own benchmarking code here, in which we consistently get a different crash, but also coming from the hazard pointer code:

F1112 21:06:54.969465  1702 HazptrObj.h:182] Check failed: next_ == this (0x7fdd00556650 vs. 0x7fdd09e416b0)
*** Check failure stack trace: ***
Aborted

[instw]

Thanks for the repro! This issue seems to be due to ConcurrentHashMap not being able to reclaim deleted entries fast enough.
Each entry in the ConcurrentHashMap is referenced by it's predecessor via a linked list, and this reference is kept track of using Hazard pointer link counting logic. Effectively when an erase is performed, the older map entry doesn't get cleaned up immediately, but rather as part of a reclamation process that's usually asynchronous. If the rate at which keys are erased is considerably higher than the rate at which keys are reclaimed, certain internal counters (which are 16 bits in size) overflow. The first error you posted is related directly to the overflow.

For the second - It seems your benchmarking code most likely runs without debug compilation, which causes some invariant checks to be skipped, leading to double reclamation and the second error.