1 files changed, 87 insertions, 0 deletions
diff --git a/content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc b/content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc
new file mode 100644
index 0000000..2482781
--- /dev/null
+++ b/content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc
@@ -0,0 +1,87 @@
+#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();
+}