C ++ 11 simple stack stop

I have seen some overly complex (in my opinion, explicitly) implementation of the blocking stack in C ++ (using type tags here ) and I came up with what I believe is a simple and still valid implementation. Since I could not find this implementation anywhere (I saw that the Push function is implemented in a similar way to what I did, but not Pop), I assume that it is incorrect (most likely the ABA case does not work):

template<typename Data>
struct Element
{
  Data mData;
  Element<Data>* mNext;
};

template<typename Data>
class Stack
{
 public:
  using Obj = Element<Data>;
  std::atomic<Obj*> mHead;

  void Push(Obj *newObj)
  {
    newObj->mNext = mHead.load();
    //Should I be using std::memory_order_acq_rel below??
    while(!mHead.compare_exchange_weak(newObj->mNext, newObj));
  }

  Obj* Pop()
  {
    Obj* old_head = mHead.load();
    while (1)
    {
      if (old_head == nullptr)
        return nullptr;
      //Should I be using std::memory_order_acq_rel below??
      if(mHead.compare_exchange_weak(old_head, old_head->mNext)) ///<<< CL1
        return old_head;
    }
  }
};

      

I assume the Push and Pop subscribers will take care of memory allocation and deallocation. Another option is to make the above Push and Pop methods private and have new public functions that will take care of memory allocation and call those functions internally. I find the hardest part of this implementation is the line marked with "CL1". The reason I think it is correct and still works in the case of ABA is this:

Let's say the ABA affair happens. This means that the mHead in "CL1" will be equal to old_head, but the object they point to will actually be different from what old_head pointed to earlier when I assigned mHead to it. But, I think that even if it is a different object, we are still fine, since we know it as a valid "head". old_head points to the same object as mHead, so it is a valid stack header, which means old_head-> mNext is a valid next header. So, updating mHead to old_head-> mNext is still correct!

Summarizing:

  • If mHead! = Old_head (another thread preempted us and changed mHead) → old_head is updated as new mHead and we will start the loop again.
  • [NON-ABA] If mHead == old_head -> simple case, update mHead as old_head-> next (== mHead-> mNext) and return old_head.
  • [ABA] If mHead == old_head → works as described above.

So, is my implementation really valid? What am I missing?

+3


source to share


1 answer


ABA occurs when:

  • Thread A reads old_head->mNext

    and blocks before calling compare_exchange_weak

    .
  • Thread B pops the current node, pushes some other nodes, and then pops the original node onto the stack.
  • Thread A unlocks, compare_exchange_weak

    succeeds as it mHead

    has the same value, but stores the stale value mNext

    as new mHead

    .


See this answer for more details , you have problem # 2 (data race on mNext

) and problem # 3 (ABA).

+5


source







All Articles