1 // ©2014 Cameron Desrochers
2
3 #include "relacy/relacy/relacy_std.hpp"
4
5
6 template <typename N>
7 struct FreeListNode
8 {
FreeListNodeFreeListNode9 FreeListNode() : freeListRefs(0), freeListNext(nullptr) { }
10
11 std::atomic<std::uint32_t> freeListRefs;
12 std::atomic<N*> freeListNext;
13 };
14
15 // A simple CAS-based lock-free free list. Not the fastest thing in the world under heavy contention,
16 // but simple and correct (assuming nodes are never freed until after the free list is destroyed),
17 // and fairly speedy under low contention.
18 template<typename N> // N must inherit FreeListNode or have the same fields (and initialization)
19 struct FreeList
20 {
FreeListFreeList21 FreeList() : freeListHead(nullptr) { }
22
addFreeList23 inline void add(N* node)
24 {
25 // We know that the should-be-on-freelist bit is 0 at this point, so it's safe to
26 // set it using a fetch_add
27 if (node->freeListRefs.fetch_add(SHOULD_BE_ON_FREELIST, std::memory_order_acq_rel) == 0) {
28 // Oh look! We were the last ones referencing this node, and we know
29 // we want to add it to the free list, so let's do it!
30 add_knowing_refcount_is_zero(node);
31 }
32 }
33
try_getFreeList34 inline N* try_get()
35 {
36 auto head = freeListHead.load(std::memory_order_acquire);
37 while (head != nullptr) {
38 auto prevHead = head;
39 auto refs = head->freeListRefs.load(std::memory_order_relaxed);
40 if ((refs & REFS_MASK) == 0 || !head->freeListRefs.compare_exchange_strong(refs, refs + 1,
41 std::memory_order_acquire, std::memory_order_relaxed)) {
42 head = freeListHead.load(std::memory_order_acquire);
43 continue;
44 }
45
46 // Good, reference count has been incremented (it wasn't at zero), which means
47 // we can read the next and not worry about it changing between now and the time
48 // we do the CAS
49 auto next = head->freeListNext.load(std::memory_order_relaxed);
50 if (freeListHead.compare_exchange_strong(head, next,
51 std::memory_order_acquire, std::memory_order_relaxed)) {
52 // Yay, got the node. This means it was on the list, which means
53 // shouldBeOnFreeList must be false no matter the refcount (because
54 // nobody else knows it's been taken off yet, it can't have been put back on).
55 RL_ASSERT((head->freeListRefs.load(std::memory_order_relaxed) & SHOULD_BE_ON_FREELIST) == 0);
56
57 // Decrease refcount twice, once for our ref, and once for the list's ref
58 head->freeListRefs.fetch_add(-2, std::memory_order_release);
59
60 return head;
61 }
62
63 // OK, the head must have changed on us, but we still need to decrease the refcount we
64 // increased.
65 // Note that we don't need to release any memory effects, but we do need to ensure that the reference
66 // count decrement happens-after the CAS on the head.
67 refs = prevHead->freeListRefs.fetch_add(-1, std::memory_order_acq_rel);
68 if (refs == SHOULD_BE_ON_FREELIST + 1) {
69 add_knowing_refcount_is_zero(prevHead);
70 }
71 }
72
73 return nullptr;
74 }
75
76 // Useful for traversing the list when there's no contention (e.g. to destroy remaining nodes)
head_unsafeFreeList77 N* head_unsafe() const { return freeListHead.load(std::memory_order_relaxed); }
78
79 private:
add_knowing_refcount_is_zeroFreeList80 inline void add_knowing_refcount_is_zero(N* node)
81 {
82 // Since the refcount is zero, and nobody can increase it once it's zero (except us, and we
83 // run only one copy of this method per node at a time, i.e. the single thread case), then we
84 // know we can safely change the next pointer of the node; however, once the refcount is back
85 // above zero, then other threads could increase it (happens under heavy contention, when the
86 // refcount goes to zero in between a load and a refcount increment of a node in try_get, then
87 // back up to something non-zero, then the refcount increment is done by the other thread) --
88 // so, if the CAS to add the node to the actual list fails, decrease the refcount and leave
89 // the add operation to the next thread who puts the refcount back at zero (which could be us,
90 // hence the loop).
91 auto head = freeListHead.load(std::memory_order_relaxed);
92 while (true) {
93 node->freeListNext.store(head, std::memory_order_relaxed);
94 node->freeListRefs.store(1, std::memory_order_release);
95 if (!freeListHead.compare_exchange_strong(head, node,
96 std::memory_order_release, std::memory_order_relaxed)) {
97 // Hmm, the add failed, but we can only try again when the refcount goes back to zero
98 if (node->freeListRefs.fetch_add(SHOULD_BE_ON_FREELIST - 1, std::memory_order_release) == 1) {
99 continue;
100 }
101 }
102 return;
103 }
104 }
105
106 private:
107 static const std::uint32_t REFS_MASK = 0x7FFFFFFF;
108 static const std::uint32_t SHOULD_BE_ON_FREELIST = 0x80000000;
109
110 // Implemented like a stack, but where node order doesn't matter (nodes are
111 // inserted out of order under contention)
112 std::atomic<N*> freeListHead;
113 };
114
115
116 struct TestNode : FreeListNode<TestNode>
117 {
118 int value;
TestNodeTestNode119 TestNode() { }
TestNodeTestNode120 explicit TestNode(int value) : value(value) { }
121 };
122
123 struct basic_test : rl::test_suite<basic_test, 2>
124 {
125 FreeList<TestNode> freeList;
126 TestNode initialNodes[2];
127
beforebasic_test128 void before()
129 {
130 }
131
threadbasic_test132 void thread(unsigned int tid)
133 {
134 TestNode* node = &initialNodes[tid];
135 node->value = tid;
136 freeList.add(node);
137
138 node = freeList.try_get();
139 if (node != nullptr) {
140 freeList.add(node);
141 }
142 }
143
afterbasic_test144 void after()
145 {
146 }
147
invariantbasic_test148 void invariant()
149 {
150 }
151 };
152
153 struct full_test : rl::test_suite<full_test, 4>
154 {
155 FreeList<TestNode> freeList;
156 TestNode initialNodes[6];
157
beforefull_test158 void before()
159 {
160 }
161
threadfull_test162 void thread(unsigned int tid)
163 {
164 TestNode* node;
165 int myNodeCount = tid >= 4 ? 2 : 1;
166 for (int i = 0; i != myNodeCount; ++i) {
167 node = &initialNodes[tid + (tid >= 5 ? 1 : 0) + i];
168 node->value = tid;
169 freeList.add(node);
170 }
171
172 for (int i = 0; i != 3; ++i) {
173 node = freeList.try_get();
174 if (node != nullptr) {
175 freeList.add(node);
176 }
177 }
178 }
179
afterfull_test180 void after()
181 {
182 }
183
invariantfull_test184 void invariant()
185 {
186 }
187 };
188
main()189 int main()
190 {
191 rl::test_params params;
192 //params.search_type = rl::sched_full;
193 //params.iteration_count = 100000000;
194 params.search_type = rl::sched_random;
195 params.iteration_count = 1000000;
196 rl::simulate<basic_test>(params);
197 rl::simulate<full_test>(params);
198
199 return 0;
200 }
201