dr-m/atomic_sync

Tiny mutex and rw-locks based on C++11 or C++20 std::atomic

atomic_sync's Issues

`atomic_condition_variable` might suffer from ABA problem

In examples/atomic_condition_variable.h, the atomic_condition_variable::wait function does this:

  template<class mutex> void wait(mutex &m)
  {
    const uint32_t val = fetch_add(1, std::memory_order_acquire);
    m.unlock();
    wait(1 + val);
    m.lock();
  }

If the same cv object is used to wait on different conditions, the loop inside wait(1 + val); might get waken up and see the same old value and sleep again, causing a deadlock.

Consider this code:

class single_producer_single_consumer_queue
{
private:
    static constexpr std::size_t N = 8;
    static constexpr std::size_t m_mask = N - 1;
    using data_t = std::array<int, N>;
    data_t m_data;
    atomic_mutex m_mutex;
    atomic_condition_variable m_cv;
    std::size_t m_tail{ 0 };
    std::size_t m_head{ 0 };
public:
    void push(int packet)
    {
        std::unique_lock<atomic_mutex> lock(m_mutex);
        for (;;)
        {
            if ((m_tail - m_head) & m_mask) != 1)
                break;
            m_cv.wait(lock);
        }
        m_data[m_head++] = packet;
        m_head &= m_mask;
        lock.unlock();
        m_cv.signal();//notify_one
    }
    int pull()
    {
        std::unique_lock<atomic_mutex> lock(m_mutex);
        for (;;)
        {
            if (m_head != m_tail)
                break;
            m_cv.wait(lock);
        }
        int r = m_data[m_tail++];
        m_tail &= m_mask;
        lock.unlock();
        m_cv.signal();//notify_one
        return r;
    }
};

single_producer_single_consumer_queue queue;

void thread1()
{
    for (int i = 0; i < 1000; ++i)
        queue.push(i);
    queue.push(-1);
}

void thread2()
{
    int sum = 0;
    for (;;)
    {
        int i = queue.pull();
        if (i == -1)
            break;
        sum += i;
    }
    std::cout << sum << std::endl;
}

These events might happen, in this order:

1. queue is empty, thread1 and thread2 start to run
2. thread2 blocks on queue.pull()->m_cv.wait(lock)->wait(1)
3. thread1 pushes one packet, resets the std::atomic<uint32_t> inside the atomic_condition_variable to 0 and wakes thread2
4. thread2 unblocks; and the thread gets scheduled out by the OS before checking the underlying std::atomic<uint32_t>'s value
5. thread1 continues to push packets to the queue, notifies nobody since no threads are blocking on the std::atomic<uint32_t>
6. the queue gets full and thread1 blocks on queue.push(i)->m_cv.wait(lock)->wait(1); the underlying std::atomic<uint32_t> is set to 1 before the blocking
7. thread2 continues to run and checks the underlying std::atomic<uint32_t>'s value, finds out that it's still 1 and blocks again
8. now everybody is blocking and deadlock occurs