diff options
author | Johannes Stoelp <johannes.stoelp@gmail.com> | 2023-11-15 02:36:11 +0100 |
---|---|---|
committer | Johannes Stoelp <johannes.stoelp@gmail.com> | 2023-11-15 02:36:11 +0100 |
commit | 824c3aa83d9acc45567421c0d08ca6eb4d718a43 (patch) | |
tree | 7c3cfd0eeba46285c773e4650f2eb3ef9cfef1b7 /content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc | |
parent | 93e0b1aa9be8e1f198d798e7b5d5df57fef4b15d (diff) | |
download | blog-824c3aa83d9acc45567421c0d08ca6eb4d718a43.tar.gz blog-824c3aa83d9acc45567421c0d08ca6eb4d718a43.zip |
post: cas, aba and ll/sc first draft
Diffstat (limited to 'content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc')
-rw-r--r-- | content/2023-09-01-cas-llsc-aba/cas-aba-issue.cc | 87 |
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(); +} |