1/*
2 * Copyright 2016-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#include <algorithm>
18#include <thread>
19
20#include <folly/AtomicLinkedList.h>
21#include <folly/portability/GTest.h>
22
23class TestIntrusiveObject {
24 public:
25 explicit TestIntrusiveObject(size_t id__) : id_(id__) {}
26 size_t id() {
27 return id_;
28 }
29
30 private:
31 folly::AtomicIntrusiveLinkedListHook<TestIntrusiveObject> hook_;
32 size_t id_;
33
34 public:
35 using List = folly::AtomicIntrusiveLinkedList<
36 TestIntrusiveObject,
37 &TestIntrusiveObject::hook_>;
38};
39
40TEST(AtomicIntrusiveLinkedList, Basic) {
41 TestIntrusiveObject a(1), b(2), c(3);
42
43 TestIntrusiveObject::List list;
44
45 EXPECT_TRUE(list.empty());
46
47 {
48 EXPECT_TRUE(list.insertHead(&a));
49 EXPECT_FALSE(list.insertHead(&b));
50
51 EXPECT_FALSE(list.empty());
52
53 size_t id = 0;
54 list.sweep([&](TestIntrusiveObject* obj) mutable {
55 ++id;
56 EXPECT_EQ(id, obj->id());
57 });
58
59 EXPECT_TRUE(list.empty());
60 }
61
62 // Try re-inserting the same item (b) and a new item (c)
63 {
64 EXPECT_TRUE(list.insertHead(&b));
65 EXPECT_FALSE(list.insertHead(&c));
66
67 EXPECT_FALSE(list.empty());
68
69 size_t id = 1;
70 list.sweep([&](TestIntrusiveObject* obj) mutable {
71 ++id;
72 EXPECT_EQ(id, obj->id());
73 });
74
75 EXPECT_TRUE(list.empty());
76 }
77
78 TestIntrusiveObject::List movedList = std::move(list);
79}
80
81TEST(AtomicIntrusiveLinkedList, ReverseSweep) {
82 TestIntrusiveObject a(1), b(2), c(3);
83 TestIntrusiveObject::List list;
84 list.insertHead(&a);
85 list.insertHead(&b);
86 list.insertHead(&c);
87 size_t next_expected_id = 3;
88 list.reverseSweep([&](TestIntrusiveObject* obj) {
89 auto const expected = next_expected_id--;
90 EXPECT_EQ(expected, obj->id());
91 });
92 EXPECT_TRUE(list.empty());
93 // Test that we can still insert
94 list.insertHead(&a);
95 EXPECT_FALSE(list.empty());
96 list.reverseSweep([](TestIntrusiveObject*) {});
97}
98
99TEST(AtomicIntrusiveLinkedList, Move) {
100 TestIntrusiveObject a(1), b(2);
101
102 TestIntrusiveObject::List list1;
103
104 EXPECT_TRUE(list1.insertHead(&a));
105 EXPECT_FALSE(list1.insertHead(&b));
106
107 EXPECT_FALSE(list1.empty());
108
109 TestIntrusiveObject::List list2(std::move(list1));
110
111 EXPECT_TRUE(list1.empty());
112 EXPECT_FALSE(list2.empty());
113
114 TestIntrusiveObject::List list3;
115
116 EXPECT_TRUE(list3.empty());
117
118 list3 = std::move(list2);
119
120 EXPECT_TRUE(list2.empty());
121 EXPECT_FALSE(list3.empty());
122
123 size_t id = 0;
124 list3.sweep([&](TestIntrusiveObject* obj) mutable {
125 ++id;
126 EXPECT_EQ(id, obj->id());
127 });
128}
129
130TEST(AtomicIntrusiveLinkedList, Stress) {
131 static constexpr size_t kNumThreads = 32;
132 static constexpr size_t kNumElements = 100000;
133
134 std::vector<TestIntrusiveObject> elements;
135 for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
136 elements.emplace_back(i);
137 }
138
139 TestIntrusiveObject::List list;
140
141 std::vector<std::thread> threads;
142 for (size_t threadId = 0; threadId < kNumThreads; ++threadId) {
143 threads.emplace_back([threadId, &list, &elements] {
144 for (size_t id = 0; id < kNumElements; ++id) {
145 list.insertHead(&elements[threadId + kNumThreads * id]);
146 }
147 });
148 }
149
150 std::vector<size_t> ids;
151 TestIntrusiveObject* prev{nullptr};
152
153 while (ids.size() < kNumThreads * kNumElements) {
154 list.sweep([&](TestIntrusiveObject* current) {
155 ids.push_back(current->id());
156
157 if (prev && prev->id() % kNumThreads == current->id() % kNumThreads) {
158 EXPECT_EQ(prev->id() + kNumThreads, current->id());
159 }
160
161 prev = current;
162 });
163 }
164
165 std::sort(ids.begin(), ids.end());
166
167 for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
168 EXPECT_EQ(i, ids[i]);
169 }
170
171 for (auto& thread : threads) {
172 thread.join();
173 }
174}
175
176class TestObject {
177 public:
178 TestObject(size_t id__, const std::shared_ptr<void>& ptr)
179 : id_(id__), ptr_(ptr) {}
180
181 size_t id() {
182 return id_;
183 }
184
185 private:
186 size_t id_;
187 std::shared_ptr<void> ptr_;
188};
189
190TEST(AtomicLinkedList, Basic) {
191 constexpr size_t kNumElements = 10;
192
193 using List = folly::AtomicLinkedList<TestObject>;
194 List list;
195
196 std::shared_ptr<void> ptr = std::make_shared<int>(42);
197
198 for (size_t id = 0; id < kNumElements; ++id) {
199 list.insertHead({id, ptr});
200 }
201
202 size_t counter = 0;
203
204 list.sweep([&](TestObject object) {
205 EXPECT_EQ(counter, object.id());
206
207 EXPECT_EQ(1 + kNumElements - counter, ptr.use_count());
208
209 ++counter;
210 });
211
212 EXPECT_TRUE(ptr.unique());
213}
214