From 824c3aa83d9acc45567421c0d08ca6eb4d718a43 Mon Sep 17 00:00:00 2001
From: Johannes Stoelp <johannes.stoelp@gmail.com>
Date: Wed, 15 Nov 2023 02:36:11 +0100
Subject: post: cas, aba and ll/sc first draft

---
 content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc | 87 ++++++++++++++++++++++++
 1 file changed, 87 insertions(+)
 create mode 100644 content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc

(limited to 'content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc')

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();
+}
-- 
cgit v1.2.3