CODEWITHSUNDEEP
c++boostlock-freecircular-bufferwait-free
Yunzhou Wu
Yunzhou Wu

Reputation: 71

memory ordering in boost example of lock-free ring buffer

When I read boost atomics about an example wait-free ring buffer implementation:

https://www.boost.org/doc/libs/1_66_0/doc/html/atomic/usage_examples.html#boost_atomic.usage_examples.example_ringbuffer

I am wondering if the memory_order_acquire is necessary at 

if (next_head == tail_.load(boost::memory_order_acquire))

seems memory_order_relaxed should work as well. My argument is that 

 value = ring_[tail];

happens-before

tail_.store(next(tail), boost::memory_order_release)

in pop() call. so we are sure data has been read before we store in push() call as

 ring_[head] = value;

I pasted the whole boost example code below for easy reference. Thanks!

#include <boost/atomic.hpp>

 template<typename T, size_t Size>
 class ringbuffer {
 public:
 ringbuffer() : head_(0), tail_(0) {}

 bool push(const T & value)
 {
    size_t head = head_.load(boost::memory_order_relaxed);
    size_t next_head = next(head);
    if (next_head == tail_.load(boost::memory_order_acquire))

//Could tail_.load above use boost::memory_order_relaxed?

    return false;
    ring_[head] = value;
    head_.store(next_head, boost::memory_order_release);
    return true;
 }
 bool pop(T & value)
{
    size_t tail = tail_.load(boost::memory_order_relaxed);
    if (tail == head_.load(boost::memory_order_acquire))
    return false;
   value = ring_[tail];
   tail_.store(next(tail), boost::memory_order_release);
   return true;
 }
 private:
   size_t next(size_t current)
   {
      return (current + 1) % Size;
   }
  T ring_[Size];
  boost::atomic<size_t> head_, tail_;

};

Upvotes: 2

Views: 623

Answers (2)

Peng Liu
Peng Liu

Reputation: 1

As far as I can see, both tail_.load(boost::memory_order_acquire) in push() and head_.load(boost::memory_order_acquire) in pop() can be relaxed and replaced with xx.load(boost::memory_order_relaxed).

Upvotes: 0

Maxim Egorushkin
Maxim Egorushkin

Reputation: 136256

One reason is that in sequence:

if(next_head == tail_.load(boost::memory_order_acquire))
    return false;
ring_[head] = value; // A non-atomic store.

memory_order_acquire ensures that the following non-atomic store does not get reordered to precede that load of tail_.

memory_order_relaxed, on the other hand, does not prevent reordering, and hence is not sufficient here.

(Assuming boost::memory_order is equivalent to std::memory_order.)

Release-Acquire ordering:

On strongly-ordered systems — x86, SPARC TSO, IBM mainframe, etc. — release-acquire ordering is automatic for the majority of operations. No additional CPU instructions are issued for this synchronization mode; only certain compiler optimizations are affected (e.g., the compiler is prohibited from moving non-atomic stores past the atomic store-release or performing non-atomic loads earlier than the atomic load-acquire). On weakly-ordered systems (ARM, Itanium, PowerPC), special CPU load or memory fence instructions are used.

Upvotes: 1

Related Questions