Problems with MCS lock implementation

Question

I'm trying to implement an MCS lock in C++ with atomics. But unfortunately threads get stuck in a deadlock. One thread is waiting for the flag to turn false in the acquire method, while the second thread is stuck in the do while loop in the release method. So the problem must be in storing/loading the next node atomically. Any ideas how to debug this or what I am doing wrong?

This is what I have so far:

#include <atomic>
#include <iostream>
#include <omp.h>

struct qnode {
  std::atomic<qnode *> next;
  std::atomic<bool> wait;
};

class mcs_lock {
  std::atomic<qnode *> tail;

public:
  void acquire(qnode *p) {
    p->next.store(nullptr);
    p->wait.store(true);

    qnode *prev = tail.exchange(p, std::memory_order_acq_rel);

    if (prev) {
      prev->next.store(p, std::memory_order_release);

      /* spin */
      while (p->wait.load(std::memory_order_acquire))
        ;
    }
  }

  void release(qnode *p) {
    qnode *succ = p->next.load(std::memory_order_acquire);

    if (!succ) {
      if (tail.compare_exchange_strong(p, nullptr, std::memory_order_acq_rel))
        return;

      do {
        succ = p->next.load(std::memory_order_acquire);
      } while (succ == nullptr);
    }

    succ->wait.store(false, std::memory_order_release);
  }
};

int main() {
  mcs_lock lock;
  qnode p;
  int counter = 0;

#pragma omp parallel for default(none) private(p) shared(lock, counter)
  for (int i = 0; i < 100000; i++) {
    lock.acquire(&p);
    ++counter;
    lock.release(&p);
  }

  std::cout << "counter=" << counter << "\n";

  return 0;
}

Answer 1

The problem is in your release implementation:

    if (!succ) {
      // if this compare-exchange fails, it loads the new value of tail
      // and stores it in p
      if (tail.compare_exchange_strong(p, nullptr, std::memory_order_acq_rel))
        return;

      do {
        succ = p->next.load(std::memory_order_acquire);
      } while (succ == nullptr);
    }

As indicated by the comment, a failing compare-exchange overwrites the value in p. That of course is the reason why the following loop does not terminate as expected. The fix is quite simple:

    if (!succ) {
      auto expected = p;
      if (tail.compare_exchange_strong(expected, nullptr, std::memory_order_acq_rel))
        return;

      do {
        succ = p->next.load(std::memory_order_acquire);
      } while (succ == nullptr);
    }