Data race on lock-array growth: get_current_locks() reads all_locks_.back() without synchronization

Summary

When a table grows its lock array, maybe_resize_locks() appends a newly built
lock container to all_locks_ (a std::list). Concurrently, lock_one() /
lock_two() obtain the current container through get_current_locks(), which is
a plain all_locks_.back(), and index into it before taking any spinlock.
Nothing orders the resizer's construction of the new container before that read.

ThreadSanitizer reports this as a data race with the small reproducer below, and
a release/acquire publication of the current container makes the reports go
away. Under the C++ memory model this is undefined behavior. On weakly ordered
CPUs (e.g. AArch64) we believe a reader can observe the newly linked node while
its contents (the vector's data pointer and the new spinlocks) are not yet
visible. On x86 the hardware (TSO) hides it.

Version / environment

libcuckoo master at 6a2555d (CMake project version 0.3.1).
Line numbers below refer to this commit.
x86_64 Linux, GCC 11.5.0, -std=c++11 -O1 -g -fsanitize=thread (GCC's libtsan).

Details

Reader side, lock_one() (lock_two() does the same):

LockManager lock_one(ResizeCounter resize_counter, size_type i,
                     normal_mode) const {
  locks_t &locks = get_current_locks();   // plain all_locks_.back(), no lock held
  const size_type l = lock_ind(i);
  spinlock &lock = locks[l];              // container dereferenced before any lock
  lock.lock();
  check_resize_counter(resize_counter, lock);
  ...
}

locks_t &get_current_locks() const { return all_locks_.back(); }

Resizer side, maybe_resize_locks(), which runs while holding all current locks:

locks_t new_locks(get_allocator());
new_locks.resize(std::min(size_type(kMaxNumLocks), new_bucket_count));
std::copy(current_locks.begin(), current_locks.end(), new_locks.begin());
for (spinlock &lock : new_locks) {
  lock.lock();
}
all_locks_.emplace_back(std::move(new_locks));   // plain append to std::list

Interleaving:

A resizer holds all locks of the current container, builds a new container,
and appends it with std::list::emplace_back. These are plain writes to the
new node and the list links.
A thread in find(), or in insert() via the cuckoo-path search
(slot_search -> lock_one), calls get_current_locks(). That reads the list
tail and the node's vector header with plain loads, and then computes
&locks[l].
The thread has not acquired any spinlock yet, so it has no happens-before edge
to step 1. The acquire in lock.lock() and check_resize_counter() comes
after the container has already been dereferenced.

The window is narrow. A thread must load the old resize counter and hashpower,
and then read the list after the append but before the new hashpower is
published. A thread that blocks on an old spinlock during the resize gets ordered
by the resizer's unlock. The race is reachable for any map whose lock array is
still below kMaxNumLocks (2^16) and grows while other threads use it, for
example a map constructed with a small initial size.

Reproducer

A standalone stress test that depends only on libcuckoo:

Each round creates a map with 1 bucket, so its lock array starts at the
minimum size.
2 writer threads insert distinct keys, forcing about 13 lock-array growths per
round, while 16 reader threads keep calling find().
A custom allocator sleeps on large allocations to widen the resize's critical
section. It changes no library logic.
At the end, every key is checked for presence and value.

The test is probabilistic and runs 2000 rounds by default (argv[1] overrides).

tests/stress-tests/stress_lock_growth.cc

// Reproducer for the lock-array publication race: concurrent readers run while
// the table grows its lock array.
//
// The map starts with a tiny table, so its lock array is small (it has
// min(bucket_count(), kMaxNumLocks) locks). Writer threads insert distinct keys,
// which forces repeated expansions. While the lock array is still below
// kMaxNumLocks, each expansion goes through maybe_resize_locks(), which appends a
// freshly built lock container to all_locks_. Reader threads concurrently call
// find(), which reaches the current lock container through get_current_locks()
// before taking any lock.
//
// Before the fix the reader got the container with a plain all_locks_.back()
// read, with no happens-before edge to the resizer's construction of the new
// container. That is a data race under the C++ memory model, and on weakly
// ordered CPUs (e.g. AArch64) a reader could observe the new list node while the
// container's contents (its spinlock array pointer) are still stale.
//
// The racy window is narrow: a reader must load the old resize counter and
// hashpower, and then read the lock list after the resizer appended the new
// container but before it published the new hashpower. Readers that already
// see the new hashpower (or that were blocked on an old lock) are ordered by
// those acquires. So the test is probabilistic: it runs many rounds of small
// maps (each round grows the lock array ~12 times) with readers that keep
// re-arriving. Under ThreadSanitizer (-fsanitize=thread), the original code
// reported this race (lock_two/get_current_locks reading the new list node vs
// its allocation in maybe_resize_locks) in a 2000-round run; with the fix it
// reports none.
//
// The test also checks functional correctness: every inserted key must be found
// with its value once all writers are done.

#include <atomic>
#include <chrono>
#include <functional>
#include <memory>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <thread>
#include <vector>

#include <libcuckoo/cuckoohash_map.hh>

namespace {

// Allocator that sleeps on large allocations. This lengthens each resize's
// critical section (allocations made while all locks are held), which perturbs
// thread interleavings around the resize. It does not change any library logic.
template <class T> struct SlowLargeAllocator {
  using value_type = T;
  SlowLargeAllocator() = default;
  template <class U> SlowLargeAllocator(const SlowLargeAllocator<U> &) {}
  T *allocate(std::size_t n) {
    if (n * sizeof(T) >= 4096) {
      std::this_thread::sleep_for(std::chrono::milliseconds(1));
    }
    return std::allocator<T>().allocate(n);
  }
  void deallocate(T *p, std::size_t n) { std::allocator<T>().deallocate(p, n); }
  template <class U> bool operator==(const SlowLargeAllocator<U> &) const {
    return true;
  }
  template <class U> bool operator!=(const SlowLargeAllocator<U> &) const {
    return false;
  }
};

using Map = libcuckoo::cuckoohash_map<
    uint64_t, uint64_t, std::hash<uint64_t>, std::equal_to<uint64_t>,
    SlowLargeAllocator<std::pair<const uint64_t, uint64_t>>>;

constexpr size_t kWriters = 2;
constexpr size_t kReaders = 16;
// Each round grows a fresh map from 1 bucket to ~2^12 buckets, i.e. through ~12
// lock-array growth steps. Small maps keep each round fast, so the many rounds
// produce thousands of growth events.
constexpr uint64_t kKeysPerWriter = 1u << 13;
// Each map only grows its lock array ~16 times, and the racy window is the
// instant between the resizer taking all locks and appending the new container,
// so repeat with fresh maps to make the race likely to be observed. Override
// with argv[1].
constexpr int kDefaultRounds = 2000;

uint64_t value_of(uint64_t key) { return key * 2654435761u + 1; }

} // namespace

int run_round(int round) {
  Map map(1); // smallest table, so its lock array starts at its minimum size

  std::atomic<bool> writers_done{false};
  std::atomic<uint64_t> lookups{0};

  std::vector<std::thread> threads;
  for (size_t w = 0; w < kWriters; ++w) {
    threads.emplace_back([&map, w] {
      for (uint64_t i = 0; i < kKeysPerWriter; ++i) {
        const uint64_t key = i * kWriters + w;
        map.insert(key, value_of(key));
      }
    });
  }
  for (size_t r = 0; r < kReaders; ++r) {
    threads.emplace_back([&map, &writers_done, &lookups, r] {
      uint64_t key = r;
      uint64_t value = 0;
      uint64_t n = 0;
      while (!writers_done.load(std::memory_order_acquire)) {
        map.find(key, value);
        // Idle between lookups, like a caller doing other work. A reader that is
        // blocked on an old lock during a resize gets a happens-before edge from
        // the resizer's unlock; the race needs a reader that does not touch the
        // map while the resizer takes the locks, and whose first access after the
        // append goes straight to the new lock container.
        if (n % 4 == 0) {
          std::this_thread::yield();
        }
        key = (key * 6364136223846793005ull + 1442695040888963407ull) %
              (kKeysPerWriter * kWriters);
        ++n;
      }
      lookups.fetch_add(n, std::memory_order_relaxed);
    });
  }

  for (size_t w = 0; w < kWriters; ++w) {
    threads[w].join();
  }
  writers_done.store(true, std::memory_order_release);
  for (size_t t = kWriters; t < threads.size(); ++t) {
    threads[t].join();
  }

  const uint64_t total = kKeysPerWriter * kWriters;
  if (map.size() != total) {
    std::cerr << "FAIL: size " << map.size() << " != " << total << "\n";
    return EXIT_FAILURE;
  }
  for (uint64_t key = 0; key < total; ++key) {
    uint64_t value = 0;
    if (!map.find(key, value) || value != value_of(key)) {
      std::cerr << "FAIL: key " << key << " missing or wrong value\n";
      return EXIT_FAILURE;
    }
  }
  if (round == 0) {
    std::cout << "round 0: " << total << " keys, bucket_count="
              << map.bucket_count() << ", concurrent lookups=" << lookups.load()
              << "\n";
  }
  return EXIT_SUCCESS;
}

int main(int argc, char **argv) {
  const int rounds = argc > 1 ? std::atoi(argv[1]) : kDefaultRounds;
  for (int round = 0; round < rounds; ++round) {
    if (run_round(round) != EXIT_SUCCESS) {
      return EXIT_FAILURE;
    }
  }
  std::cout << "PASS: " << rounds << " rounds\n";
  return EXIT_SUCCESS;
}

Build and run from the repository root:

g++ -std=c++11 -O1 -g -fsanitize=thread -pthread -I. \
    tests/stress-tests/stress_lock_growth.cc -o stress_lock_growth
./stress_lock_growth 2000

Or add it next to the existing stress tests:

# tests/stress-tests/CMakeLists.txt
add_executable(stress_lock_growth stress_lock_growth.cc)
target_link_libraries(stress_lock_growth PRIVATE libcuckoo)
add_test(NAME stress_lock_growth COMMAND stress_lock_growth)

Observed

Run	Reproducer	Header	TSan data races	Functional check
1	one large map per run (grown to 262,144 buckets), 3 runs	`master`	0	PASS
2	many small maps, 2000 rounds (above)	`master`	5	PASS
3	same as 2	with the proposed fix	0	PASS
4	same as 2, without TSan	`master` and fix	n/a	PASS (about 2 min)

Run 1 vs run 2: a single large map grows its lock array only about 16
times before reaching kMaxNumLocks. That's why the reproducer uses many small
maps instead, giving about 26,000 growth events per run.
Run 4: without TSan the test passes on x86 both before and after, which is
consistent with TSO hiding the reordering.

All 5 reports in run 2 follow one of two shapes:

Reports	Racing access	Conflicting access (resizer, `maybe_resize_locks`)
1, 4, 5	8-byte read in `operator[]` on the container, from `lock_two` (`find`) or `lock_one` (`insert`)	allocation of the new `std::list` node by `emplace_back` (line 1895)
2, 3	atomic `test_and_set` in `spinlock::lock()`, from `lock_one` (`insert`) or `lock_two` (`find`)	allocation and construction of the new spinlock vector by `new_locks.resize(...)` (line 1889)

In every report the "previous write" is operator new inside maybe_resize_locks.
So the thread touches memory the resizer just created, with no publication edge
between them.

Report 1, cleaned up (template arguments and binary offsets removed):

WARNING: ThreadSanitizer: data race
  Read of size 8 at 0x7b0c00001e40 by thread T26:
    #0 operator[] bits/stl_vector.h:1046
    #1 lock_two libcuckoo/cuckoohash_map.hh:1042
    #2 snapshot_and_lock_two libcuckoo/cuckoohash_map.hh:1111
    #3 find_fn libcuckoo/cuckoohash_map.hh:466
    #4 find libcuckoo/cuckoohash_map.hh:600
    #5 operator() tests/stress-tests/stress_lock_growth.cc:105
    #6 __invoke_impl bits/invoke.h:61
    #7 __invoke bits/invoke.h:96
    #8 _M_invoke bits/std_thread.h:259
    #9 operator() bits/std_thread.h:266
    #10 _M_run bits/std_thread.h:211
    #11 execute_native_thread_routine <null>

  Previous write of size 8 at 0x7b0c00001e40 by thread T16:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Location is heap block of size 40 at 0x7b0c00001e30 allocated by thread T16:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Thread T26 (tid=2199225, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

  Thread T16 (tid=2199213, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

All 5 TSan reports

Report 1

WARNING: ThreadSanitizer: data race
  Read of size 8 at 0x7b0c00001e40 by thread T26:
    #0 operator[] bits/stl_vector.h:1046
    #1 lock_two libcuckoo/cuckoohash_map.hh:1042
    #2 snapshot_and_lock_two libcuckoo/cuckoohash_map.hh:1111
    #3 find_fn libcuckoo/cuckoohash_map.hh:466
    #4 find libcuckoo/cuckoohash_map.hh:600
    #5 operator() tests/stress-tests/stress_lock_growth.cc:105
    #6 __invoke_impl bits/invoke.h:61
    #7 __invoke bits/invoke.h:96
    #8 _M_invoke bits/std_thread.h:259
    #9 operator() bits/std_thread.h:266
    #10 _M_run bits/std_thread.h:211
    #11 execute_native_thread_routine <null>

  Previous write of size 8 at 0x7b0c00001e40 by thread T16:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Location is heap block of size 40 at 0x7b0c00001e30 allocated by thread T16:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Thread T26 (tid=2199225, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

  Thread T16 (tid=2199213, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

Report 2

WARNING: ThreadSanitizer: data race
  Atomic write of size 1 at 0x7bb000019b00 by thread T29:
    #0 __tsan_atomic8_exchange <null>
    #1 std::atomic_flag::test_and_set(std::memory_order) bits/atomic_base.h:212
    #2 lock libcuckoo/cuckoohash_map.hh:837
    #3 lock_one libcuckoo/cuckoohash_map.hh:1019
    #4 slot_search libcuckoo/cuckoohash_map.hh:1683
    #5 cuckoopath_search libcuckoo/cuckoohash_map.hh:1456
    #6 run_cuckoo libcuckoo/cuckoohash_map.hh:1415
    #7 cuckoo_insert libcuckoo/cuckoohash_map.hh:1292
    #8 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1230
    #9 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #10 upsert libcuckoo/cuckoohash_map.hh:587
    #11 insert libcuckoo/cuckoohash_map.hh:645
    #12 operator() tests/stress-tests/stress_lock_growth.cc:95
    #13 __invoke_impl bits/invoke.h:61
    #14 __invoke bits/invoke.h:96
    #15 _M_invoke bits/std_thread.h:259
    #16 operator() bits/std_thread.h:266
    #17 _M_run bits/std_thread.h:211
    #18 execute_native_thread_routine <null>

  Previous write of size 8 at 0x7bb000019b00 by thread T30:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_allocate bits/stl_vector.h:346
    #5 _M_default_append bits/vector.tcc:635
    #6 resize bits/stl_vector.h:940
    #7 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1889
    #8 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #9 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #10 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #11 upsert libcuckoo/cuckoohash_map.hh:587
    #12 insert libcuckoo/cuckoohash_map.hh:645
    #13 operator() tests/stress-tests/stress_lock_growth.cc:95
    #14 __invoke_impl bits/invoke.h:61
    #15 __invoke bits/invoke.h:96
    #16 _M_invoke bits/std_thread.h:259
    #17 operator() bits/std_thread.h:266
    #18 _M_run bits/std_thread.h:211
    #19 execute_native_thread_routine <null>

  Location is heap block of size 32768 at 0x7bb000018000 allocated by thread T30:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_allocate bits/stl_vector.h:346
    #5 _M_default_append bits/vector.tcc:635
    #6 resize bits/stl_vector.h:940
    #7 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1889
    #8 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #9 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #10 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #11 upsert libcuckoo/cuckoohash_map.hh:587
    #12 insert libcuckoo/cuckoohash_map.hh:645
    #13 operator() tests/stress-tests/stress_lock_growth.cc:95
    #14 __invoke_impl bits/invoke.h:61
    #15 __invoke bits/invoke.h:96
    #16 _M_invoke bits/std_thread.h:259
    #17 operator() bits/std_thread.h:266
    #18 _M_run bits/std_thread.h:211
    #19 execute_native_thread_routine <null>

  Thread T29 (tid=2266090, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

  Thread T30 (tid=2266091, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

Report 3

WARNING: ThreadSanitizer: data race
  Atomic write of size 1 at 0x7b8000030580 by thread T21:
    #0 __tsan_atomic8_exchange <null>
    #1 std::atomic_flag::test_and_set(std::memory_order) bits/atomic_base.h:212
    #2 lock libcuckoo/cuckoohash_map.hh:837
    #3 lock_two libcuckoo/cuckoohash_map.hh:1042
    #4 snapshot_and_lock_two libcuckoo/cuckoohash_map.hh:1111
    #5 find_fn libcuckoo/cuckoohash_map.hh:466
    #6 find libcuckoo/cuckoohash_map.hh:600
    #7 operator() tests/stress-tests/stress_lock_growth.cc:105
    #8 __invoke_impl bits/invoke.h:61
    #9 __invoke bits/invoke.h:96
    #10 _M_invoke bits/std_thread.h:259
    #11 operator() bits/std_thread.h:266
    #12 _M_run bits/std_thread.h:211
    #13 execute_native_thread_routine <null>

  Previous write of size 8 at 0x7b8000030580 by thread T17:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_allocate bits/stl_vector.h:346
    #5 _M_default_append bits/vector.tcc:635
    #6 resize bits/stl_vector.h:940
    #7 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1889
    #8 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #9 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #10 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #11 upsert libcuckoo/cuckoohash_map.hh:587
    #12 insert libcuckoo/cuckoohash_map.hh:645
    #13 operator() tests/stress-tests/stress_lock_growth.cc:95
    #14 __invoke_impl bits/invoke.h:61
    #15 __invoke bits/invoke.h:96
    #16 _M_invoke bits/std_thread.h:259
    #17 operator() bits/std_thread.h:266
    #18 _M_run bits/std_thread.h:211
    #19 execute_native_thread_routine <null>

  Location is heap block of size 4096 at 0x7b8000030000 allocated by thread T17:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_allocate bits/stl_vector.h:346
    #5 _M_default_append bits/vector.tcc:635
    #6 resize bits/stl_vector.h:940
    #7 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1889
    #8 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #9 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #10 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #11 upsert libcuckoo/cuckoohash_map.hh:587
    #12 insert libcuckoo/cuckoohash_map.hh:645
    #13 operator() tests/stress-tests/stress_lock_growth.cc:95
    #14 __invoke_impl bits/invoke.h:61
    #15 __invoke bits/invoke.h:96
    #16 _M_invoke bits/std_thread.h:259
    #17 operator() bits/std_thread.h:266
    #18 _M_run bits/std_thread.h:211
    #19 execute_native_thread_routine <null>

  Thread T21 (tid=2266285, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

  Thread T17 (tid=2266276, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

Report 4

WARNING: ThreadSanitizer: data race
  Read of size 8 at 0x7b0c00003ee0 by thread T19:
    #0 operator[] bits/stl_vector.h:1046
    #1 lock_one libcuckoo/cuckoohash_map.hh:1018
    #2 slot_search libcuckoo/cuckoohash_map.hh:1683
    #3 cuckoopath_search libcuckoo/cuckoohash_map.hh:1456
    #4 run_cuckoo libcuckoo/cuckoohash_map.hh:1415
    #5 cuckoo_insert libcuckoo/cuckoohash_map.hh:1292
    #6 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1230
    #7 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #8 upsert libcuckoo/cuckoohash_map.hh:587
    #9 insert libcuckoo/cuckoohash_map.hh:645
    #10 operator() tests/stress-tests/stress_lock_growth.cc:95
    #11 __invoke_impl bits/invoke.h:61
    #12 __invoke bits/invoke.h:96
    #13 _M_invoke bits/std_thread.h:259
    #14 operator() bits/std_thread.h:266
    #15 _M_run bits/std_thread.h:211
    #16 execute_native_thread_routine <null>

  Previous write of size 8 at 0x7b0c00003ee0 by thread T20:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Location is heap block of size 40 at 0x7b0c00003ed0 allocated by thread T20:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Thread T19 (tid=2266796, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

  Thread T20 (tid=2266797, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

Report 5

WARNING: ThreadSanitizer: data race
  Read of size 8 at 0x7b0c00000eb0 by thread T11:
    #0 operator[] bits/stl_vector.h:1046
    #1 lock_two libcuckoo/cuckoohash_map.hh:1042
    #2 cuckoopath_move libcuckoo/cuckoohash_map.hh:1554
    #3 run_cuckoo libcuckoo/cuckoohash_map.hh:1421
    #4 cuckoo_insert libcuckoo/cuckoohash_map.hh:1292
    #5 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1230
    #6 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #7 upsert libcuckoo/cuckoohash_map.hh:587
    #8 insert libcuckoo/cuckoohash_map.hh:645
    #9 operator() tests/stress-tests/stress_lock_growth.cc:95
    #10 __invoke_impl bits/invoke.h:61
    #11 __invoke bits/invoke.h:96
    #12 _M_invoke bits/std_thread.h:259
    #13 operator() bits/std_thread.h:266
    #14 _M_run bits/std_thread.h:211
    #15 execute_native_thread_routine <null>

  Previous write of size 8 at 0x7b0c00000eb0 by thread T12:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Location is heap block of size 40 at 0x7b0c00000ea0 allocated by thread T12:
    #0 operator new(unsigned long) <null>
    #1 allocate ext/new_allocator.h:127
    #2 allocate tests/stress-tests/stress_lock_growth.cc:53
    #3 allocate bits/alloc_traits.h:318
    #4 _M_get_node bits/stl_list.h:443
    #5 _M_create_node bits/stl_list.h:635
    #6 _M_insert bits/stl_list.h:1912
    #7 emplace_back bits/stl_list.h:1228
    #8 maybe_resize_locks libcuckoo/cuckoohash_map.hh:1895
    #9 cuckoo_fast_double libcuckoo/cuckoohash_map.hh:1755
    #10 cuckoo_insert_loop libcuckoo/cuckoohash_map.hh:1237
    #11 uprase_fn libcuckoo/cuckoohash_map.hh:557
    #12 upsert libcuckoo/cuckoohash_map.hh:587
    #13 insert libcuckoo/cuckoohash_map.hh:645
    #14 operator() tests/stress-tests/stress_lock_growth.cc:95
    #15 __invoke_impl bits/invoke.h:61
    #16 __invoke bits/invoke.h:96
    #17 _M_invoke bits/std_thread.h:259
    #18 operator() bits/std_thread.h:266
    #19 _M_run bits/std_thread.h:211
    #20 execute_native_thread_routine <null>

  Thread T11 (tid=2269992, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

  Thread T12 (tid=2269993, running) created by main thread at:
    #0 pthread_create <null>
    #1 std::thread::_M_start_thread(std::unique_ptr, void (*)()) <null>
    #2 main tests/stress-tests/stress_lock_growth.cc:153

Proposed fix

Keep the std::list, so containers never move and old ones stay valid for
threads still holding them. Publish the current container through an atomic
pointer:

Wrap the list in a small class holding std::atomic<locks_t *> current_.
Append a fully constructed container with push_back, then
current_.store(&list_.back(), std::memory_order_release).
get_current_locks() returns *current_.load(std::memory_order_acquire).
lock_all() starts from the container that load returns, not from
std::prev(all_locks_.end()).
Copy, move, assignment and swap re-publish current_.
The constructor and add_locks_from_other() build the container fully before
appending it, instead of emplace_back followed by resize/copy on
back().

The locking protocol is unchanged. The only hot-path cost is the acquire load,
which is a plain mov on x86 and ldar on AArch64.

class all_locks_t {
public:
  // During construction, or by a thread holding all current locks.
  void push_back(locks_t &&locks) {
    list_.push_back(std::move(locks));
    current_.store(&list_.back(), std::memory_order_release);
  }
  locks_t &current() const noexcept {
    return *current_.load(std::memory_order_acquire);
  }
  // ... copy/move/swap re-publish; empty(), current_iterator(), end()
private:
  std::list<locks_t, rebind_alloc<locks_t>> list_;
  std::atomic<locks_t *> current_{nullptr};
};

locks_t &get_current_locks() const { return all_locks_.current(); }

With this change, the reproducer reports 0 races (run 3). The existing tests also
pass: the unit tests (81/81) and stress_checked / stress_unchecked (power 20,
8 threads, 20 s).

We're happy to open a PR with the fix if no concern raised.

Questions

Is there an invariant we missed that guarantees a thread always acquires an
old spinlock, released by the resizer, before it can observe the new list tail?
Do you have a preferred shape for the fix? For example, a different node-based
structure, or publishing an index or size atomically instead of a pointer.

The same all_locks_ race was also reproduced in our integration under ThreadSanitizer, including concurrent table snapshots through lock_table() while other threads insert elements and trigger growth.

A local regression test uses eight writer threads inserting 8 192 keys in total while another thread takes table snapshots. The original header reproduced the TSAN race, the patched version passed 20 repetitions without reports.

The local fix uses a dedicated metadata spinlock to protect publication, lookup, and traversal of the lock-array list. That lock is released before acquiring bucket locks, and existing lock arrays remain alive.

@DzemalMemic

@DzemalMemic Thanks for confirming the issue. Indeed, taking a spin lock would fix the issue but it seems too much. A simple wrapper class with some additional fences should be enough to fix the race here. Any specific reason why you choose to use spinlock?

The spinlock was a straightforward local fix covering both the current lock lookup and list traversal during lock_table(). It passed our TSAN regression, but I agree it may add unnecessary contention. Your atomic publication approach looks lighter; I’d just want to verify that it also handles concurrent list traversal during growth.

While testing the atomic publication approach, I found a separate resize bug in snapshot_and_lock_two(). A resize between reading hashpower() and the resize counter can leave an operation using stale bucket indices. This reproduces with both the spinlock and atomic publication fixes.

@DzemalMemic

Good find @DzemalMemic . I have submitted a PR for the atomic publication fixes.

Navigation Menu

Repository navigation

Data race on lock-array growth: get_current_locks() reads all_locks_.back() without synchronization #174

Summary

Version / environment

Details

Reproducer

Observed

Proposed fix

Questions

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Data race on lock-array growth: get_current_locks() reads all_locks_.back() without synchronization #174

Description

Summary

Version / environment

Details

Reproducer

Observed

Proposed fix

Questions

Activity

DzemalMemic commented on Oct 5, 2026

mrmitzh commented on Oct 5, 2026

DzemalMemic commented on Oct 6, 2026

DzemalMemic commented on Oct 6, 2026

mrmitzh commented on Oct 6, 2026

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions