folly::ConcurrentHashMap crashes under high contention
- Dominant language
- C++
- Stars
- 30.5k
- Forks
- 5.9k
- PR merge metrics
- No merged PRs in 30d
Description
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.
```c++
#include
#include
#include
#include
#include
#include
#include
#include
#include
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(r) / static_cast(std::numeric_limits::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 threads;
threads.reserve(num_threads);
KeyDist z(100000, 0.99);
folly::ConcurrentHashMap 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](https://github.com/cmuparlay/parlayhash/blob/bigatomic/benchmarks/test_map.cpp), 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
```
Contributor guide
Assessment
This issue has not been assessed yet.