How std::atomic wait operation works?

Question

Starting C++20, std::atomic has wait() and notify_one()/notify_all() operations. But I didn't get exactly how they are supposed to work. cppreference says:

Performs atomic waiting operations. Behaves as if it repeatedly performs the following steps:

• Compare the value representation of this->load(order) with that of old.
  • If those are equal, then blocks until *this is notified by notify_one() or notify_all(), or the thread is unblocked spuriously.
  • Otherwise, returns.

These functions are guaranteed to return only if value has changed, even if underlying implementation unblocks spuriously.

I don't exactly get how these 2 parts are related to each other. Does it mean that if the value if not changed, then the function does not return even if I use notify_one()/notify_all() method? meaning that the operation is somehow equal to following pseudocode?

while (*this == val) {
    // block thread
}

Answer 1

Yes, that is exactly it. notify_one/all simply provide the waiting thread a chance to check the value for change. If it remains the same, e.g. because a different thread has set the value back to its original value, the thread will remain blocking.

Note: A valid implementation for this code is to use a global array of mutexes and condition_variables. atomic variables are then mapped to these objects by their pointer via a hash function. That's why you get spurious wakeups. Some atomics share the same condition_variable.

Something like this:

std::mutex atomic_mutexes[64];
std::condition_variable atomic_conds[64];

template<class T>
std::size_t index_for_atomic(std::atomic<T>* ptr) noexcept
{ return reinterpret_cast<std::size_t>(ptr) / sizeof(T) % 64; }

void atomic<T>::wait(T value, std::memory_order order)
{
    if(this->load(order) != value)
        return;
    std::size_t index = index_for_atomic(this);
    std::unique_lock<std::mutex> lock(atomic_mutexes[index]);
    while(this->load(std::memory_order_relaxed) == value)
        atomic_conds[index].wait(lock);
}
template<class T>
void std::atomic_notify_one(std::atomic<T>* ptr)
{
    const std::size_t index = index_for_atomic(ptr);
    /*
     * normally we don't need to hold the mutex to notify
     * but in this case we updated the value without holding
     * the lock. Therefore without the mutex there would be
     * a race condition in wait() between the while-loop condition
     * and the loop body
     */
    std::lock_guard<std::mutex> lock(atomic_mutexes[index]);
    /*
     * needs to notify_all because we could have multiple waiters
     * in multiple atomics due to aliasing
     */
    atomic_conds[index].notify_all();
}

A real implementation would probably use the OS primitives, for example WaitForAddress on Windows or (at least for int-sized types) futex on Linux.