Request for review of memory orders of mpsc queue

user_1487069 0
Viewed 128

I converted the C code of http://www.1024cores.net/home/lock-free-algorithms/queues/intrusive-mpsc-node-based-queue to C++.

At the time of writing this looks as follows:

struct MpscNode
{
  std::atomic<MpscNode*> m_next;
};

class MpscQueue
{
 private:
  std::atomic<MpscNode*> m_head;
  MpscNode*              m_tail;
  MpscNode               m_stub;

 public:
  MpscQueue() : m_head(&m_stub), m_tail(&m_stub), m_stub{{nullptr}} { }

  void push(MpscNode* node)
  {
    node->m_next.store(nullptr, std::memory_order_relaxed);
    MpscNode* prev = m_head.exchange(node, std::memory_order_relaxed);
    prev->m_next.store(node, std::memory_order_release);
  }

  MpscNode* pop()
  {
    MpscNode* tail = m_tail;
    MpscNode* next = tail->m_next.load(std::memory_order_acquire);
    if (tail == &m_stub)
    {
      if (nullptr == next)
        return nullptr;
      m_tail = next;
      tail = next;
      next = next->m_next.load(std::memory_order_acquire);
    }
    if (next)
    {
      m_tail = next;
      return tail;
    }
    MpscNode* head = m_head.load(std::memory_order_relaxed);
    if (tail != head)
      return nullptr;
    push(&m_stub);
    next = tail->m_next.load(std::memory_order_acquire);
    if (next)
    {
      // Remove node and return it.
      m_tail = next;
      return tail;
    }
    return nullptr;
  }
};

You can see the latest version, including my comments, here: https://github.com/CarloWood/ai-utils/blob/master/threading/MpscQueue.h

My question is about the second line in push:

MpscNode* prev = m_head.exchange(node, std::memory_order_relaxed);

I do not feel entirely sure about the memory order used here. It seems right, but I'd like a review of the memory orders that I used.

I can't test it, because I only have an Intel CPU - not one with weak atomic (like -say- ARM).

stdatomic memory-barriers memory-model thread-safety c++
1 Answers

Yes, your code is correct! The operations on m_head can be relaxed, because they are not used for any synchronization. pop only loads m_head to check if it equals tail, but there are not operations that depend on a synchronize-with relation on m_head.

The important operations are on m_next which is used to establish the necessary synchronization, and there your correctly use acquire/release orders.

So from my perspective this code looks fine!

FWIW: you don't necessarily need a CPU with a weak memory model to detect data races; thread-sanitizer does a pretty good job on x86 CPUs too.

Edit:

Let me try to elaborate... First of all, let's note some general observations.

  1. The queue always holds at least one node, i.e., m_tail and m_head always point to some node and are never null.
  2. The queue is empty if and only if m_tail and m_head point to m_stub. If m_tail and m_head both point to some node that is not m_stub, the queue contains one element (namely that node), so we have to push m_stub in order to be enable to dequeue that node and satisfay our requirement that the queue always holds at least one node.
  3. The queue is not linearizable!

When reasoning about memory orders we first need to identify our requirements, i.e., what are the necessary happens-before relations. Let's use the following notation:

happens-before    -hb->
synchronize-with  -sw->
sequenced-before  -sb->
read-from         -rf->

In this case it is simple - we need a happens-before relation between the push and pop operations. In particular we need to show the following (node1 and node2 are separate variables, but both point to the same node; init and consume are some arbitrary functions that operate on the node):

init(node1) -sb-> push(node1) -hb-> node2 = pop() -sb-> consume(node2)

Due to the transitivity of the happens-before relation it follows that init(node1) -hb-> consume(node2). So how can we ensure that? Let's look at the push operation:

node->m_next.store() -sb-> m_head.exchange() -sb-> prev-m_next.store()

The store to prev->m_next is our synchronization point. The node can only be consume once this store becomes visible to the consumer.

Now let's look at the pop operation. First of all, we can note that there are two paths that do not return a nullptr, and both of these paths return the variable tail. There are two assignments to tail, one from m_tail and one from next if tail == &m_stub. We will ignore the latter case here since it is easy to formulate similar arguments. m_tail cannot be used to establish an inter-thread-happens-before relation with pop, so we have to consider how m_tail receives its value.

There are two assignments to m_tail (we keep ignoring the tail == &m_stub case), both assigning next which itself is assigned the result of tail->m_next.load(). So we end up with the following (simplified):

                         pop_1                                        pop_2
v-------------------------^---------------------v    v-----------------^----------------v
next=tail->m_next.load() -sb-> m_tail=next -sb-> ... -sb-> tail=m_tail -sb-> return tail

Note: pop_1 is the pop call preceeding pop_2.

This code path contains only a single atomic operation - the load of tail->m_next - so this operation has to establish the necessary happens-before relation. This is achieved by using acquire/release orders. If the load in the pop operation observes the value written by the store in push, then these two operations establish a synchronize-with relation. It is worth noting that the inter-thread-happens-before relation required by pop_2 is actually established by pop_1:

                thread1                                      thread2
  v----------------^-------------v     v------------------------^---------------------v
   prev->m_next.store(mo_release) -rf-> next=tail->m_next.load(mo_acquire) -sb-> pop_2
=> prev->m_next.store(mo_release) -sw-> next=tail->m_next.load(mo_acquire) -sb-> pop_2
=> prev->m_next.store(mo_release) -hb-> next=tail->m_next.load(mo_acquire) -sb-> pop_2
=>                           push -hb-> pop_2

Now let's look at the code path that performs a load of m_head. First, this path is only relevant if next is null. Second, if m_head is different from tail, we immediately return with a nullptr (this can happen if a push has performed the exchange, but not yet the store to m_next - recall, this queue is not linearizable). So we only continue if m_head is equal to tail (i.e., that is the case were we have a single node left in the queue that is not m_stub), but we just discussed how we have already established the necessary happens-before relation for tail, so we don't need m_head for that! And if there is no acquire-operation on m_head there is no point in using memory_order_release for the exchange operation, because there is nothing that would synchronize-with that exchange.

user_127478330
Related