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 | |
23 | class 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 | |
40 | TEST(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 | |
81 | TEST(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 | |
99 | TEST(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 | |
130 | TEST(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 | |
176 | class 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 | |
190 | TEST(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 | |