1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
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();
}
|
