[Concurrency] Lost wakeup in ThreadPool: generation bump + notify_all outside idle_mutex can hang parallel_for permanently

[Czile-create]

Summary

While studying the generated multi-threaded TPC-H artifacts (bespoke_tpch_multithreading/), we found a lost-wakeup (missed-notification) defect in thread_pool.hpp that can cause parallel_for — and the destructor's join() — to block permanently.

The defect is a textbook violation of the std::condition_variable discipline: the predicate variable (generation) is modified, and notify_all() is issued, outside the idle_mutex that workers hold while evaluating the wait predicate. Making the predicate an std::atomic does not make this safe.

ID	Type	Severity	Location
R1	liveness — lost wakeup → permanent hang	High	thread_pool.hpp:145-146 (dispatch) / :75-79 (destructor) vs :109-112 (worker wait)

---

Where

ThreadPool uses an std::atomic<int> generation as the wakeup predicate. Workers use a two-phase idle strategy: spin first, then sleep on idle_cv once idle_spin_limit is reached.

Worker, sleep path (predicate evaluated under idle_mutex):

// thread_pool.hpp:109-112
std::unique_lock<std::mutex> lk(idle_mutex);
idle_cv.wait(lk, [&]{
    return generation.load(std::memory_order_relaxed) != my_gen;
});

Dispatch (parallel_for) — the generation bump and the notify happen outside idle_mutex:

// thread_pool.hpp:144-146
done_count.store(0, std::memory_order_relaxed);
generation.fetch_add(1, std::memory_order_release); // wakes spinning workers
idle_cv.notify_all();                                // wakes sleeping workers

Destructor has the same shape:

// thread_pool.hpp:75-79
shutdown.store(true, std::memory_order_relaxed);
generation.fetch_add(1, std::memory_order_release);
idle_cv.notify_all();
for (auto& t : workers) t.join();

Why it is a real bug

std::condition_variable requires that the shared state the predicate depends on be modified while holding the same mutex the waiter uses, so the change is correctly published relative to the waiter's "evaluate predicate → enqueue onto the wait set" step. std::condition_variable::wait(lk, pred) expands to:

while (!pred()) { /* (a) evaluate pred → (b) atomically unlock + enqueue on wait set */ }

There is a gap between (a) and (b). Because parallel_for bumps generation and calls notify_all() without holding idle_mutex, that bump+notify can land inside the gap: at notify_all() time the worker has already evaluated the predicate as false but has not yet been placed on the wait set, so the notification reaches an empty wait set and is lost. The worker then blocks on a generation it will never be notified about again.

The atomicity of generation does not help here: it only makes the load/store of that one variable well-defined; it does not order the store against the condition variable's internal wait-set transition.

Note: the code comment at thread_pool.hpp:49-50 correctly reasons about publishing task_fn/task_ctx via release/acquire ("No data race"), but the same release store on generation is not sufficient to publish the wakeup to a thread that is about to sleep — that requires the bump to be done under idle_mutex.

Interleaving (W = worker, M = main thread in parallel_for)

time   W (worker, :103-116)                       M (parallel_for, :145-146, NOT holding idle_mutex)
----   --------------------------------------      ---------------------------------------------------
t0     :103 while(generation==my_gen) spin
t1     :107 ++spins >= idle_spin_limit  -> sleep
t2     :109 unique_lock lk(idle_mutex)
t3     :110 wait -> :111 pred:
         generation(my_gen)!=my_gen? -> FALSE      <- reads old value, not yet on wait set
t4                                                 :144 done_count.store(0)
t5                                                 :145 generation.fetch_add -> my_gen+1   (no idle_mutex)
t6                                                 :146 idle_cv.notify_all()
                                                      -> wait set empty (W not enqueued) -> *** wakeup lost ***
t7     wait internally: unlock + enqueue + block
       -> generation is already my_gen+1, but the notify is gone -> never wakes
t8                                                 :148 f(0, num_threads)   // main runs tid 0
t9                                                 :153 while(done_count < need)
                                                      W never wakes -> never :121 done_count.fetch_add
                                                      -> done_count < need forever -> *** main spins forever ***

The window is genuinely narrow (sub-microsecond) and lies entirely inside the idle_mutex critical section, so it almost never fires under natural scheduling — but it is a legal interleaving, and once it fires the hang is permanent and unrecoverable. The destructor path (:75-79) has the identical race: a worker that misses the shutdown bump blocks forever and join() (:79) never returns.

Impact

An intermittent, very hard to reproduce permanent hang between queries: either the main thread spins forever at :153, or ~ThreadPool() blocks forever at :79. This is a liveness failure, not a data race or UB.

Fix

Bump generation while holding idle_mutex, at both the dispatch site and the destructor. notify_all() may stay outside the lock.

// parallel_for
{
    std::lock_guard<std::mutex> lk(idle_mutex);
    done_count.store(0, std::memory_order_relaxed);
    generation.fetch_add(1, std::memory_order_release);
}
idle_cv.notify_all();

Apply the same pattern in ~ThreadPool() for the shutdown + generation bump.

Environment / reproduction

• Affected file: bespoke_tpch_multithreading/thread_pool.hpp (line numbers verified against the current HEAD at audit time).
• x86 build (_mm_pause), multi-threaded TPC-H variant.
• The natural window is sub-microsecond; deterministic reproduction requires widening the (a)->(b) gap (e.g. a small injected delay between the predicate evaluation and the internal enqueue).

Found by @LittleS321, @hemnd, @Czile-create and Claude Code via formal concurrency analysis.