#include <cassert>
#include <cstdio>

#include <atomic>
#include <thread>

#include <unistd.h>

// -- BLOCK STACK --------------------------------------------------------------

struct BlockStack {
  struct Block {
    Block* next{nullptr};
    unsigned mem{0};
  };

  void push(Block* blk) {
    printf("[%d] push blk->mem=%d\n", gettid(), blk->mem);

    do {
      blk->next = m_head;
    } while (!m_head.compare_exchange_weak(blk->next, blk));
  }

  Block* pop(int s = 0) {
    Block *blk, *next;
    do {
      blk  = m_head;
      next = blk->next;
      // Simulate thread being interrupted.
      if (s) {
        sleep(s);
      }
    } while (!m_head.compare_exchange_weak(blk, next));

    printf("[%d] pop blk->mem=%d\n", gettid(), blk->mem);
    return blk;
  }

private:
  std::atomic<Block*> m_head{nullptr};
};

// -- MAIN ---------------------------------------------------------------------

int main() {
  BlockStack::Block B1, B2, B3;
  B1.mem = 1;
  B2.mem = 2;
  B3.mem = 3;

  // Create free memory block list.
  // S: head -> 1 -> 2 -> 3.
  BlockStack S;
  S.push(&B3);
  S.push(&B2);
  S.push(&B1);

  auto T1 = std::thread([&S]() {
    // Read head=1 & next=2, then get interrupted (simulated by sleep).
    // After resuming, T2 already popped 1 & 2 and pushed again 1 (ABA).
    // The CAS will set head pointing to 2 and pop block 1. Block 2 is inserted
    // again into the free list, even it is not free.
    auto* B1 = S.pop(2);
    assert(B1->mem == 1);
    // Pops 2, which is currently owned by T2, double usage (broken).
    auto* B2 = S.pop();
    assert(B2->mem == 2);
  });

  auto T2 = std::thread([&S]() {
    // Artificial sleep, such that T1 entered pop and read head & next.
    sleep(1);

    // Pop 1 & 2.
    auto* B1 = S.pop();
    assert(B1->mem == 1);
    auto* B2 = S.pop();
    assert(B2->mem == 2);

    // Re-insert 1.
    S.push(B1);
  });

  T2.join();
  T1.join();
}