1 // Copyright 2019 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "base/task/sequence_manager/atomic_flag_set.h"
6
7 #include <set>
8 #include <utility>
9 #include <vector>
10
11 #include "base/test/bind.h"
12 #include "testing/gmock/include/gmock/gmock.h"
13
14 using testing::ElementsAre;
15 using testing::IsNull;
16 using testing::NotNull;
17
18 namespace base {
19 namespace sequence_manager {
20 namespace internal {
21
22 class AtomicFlagSetForTest : public AtomicFlagSet {
23 public:
AtomicFlagSetForTest(scoped_refptr<AssociatedThreadId> associated_thread)24 explicit AtomicFlagSetForTest(
25 scoped_refptr<AssociatedThreadId> associated_thread)
26 : AtomicFlagSet(std::move(associated_thread)) {}
27
28 using AtomicFlagSet::GetAllocListForTesting;
29 using AtomicFlagSet::GetPartiallyFreeListForTesting;
30 using AtomicFlagSet::Group;
31 };
32
33 class AtomicFlagSetTest : public testing::Test {
34 public:
CreateFlags(size_t number_of_flags,RepeatingCallback<void (size_t index)> callback)35 void CreateFlags(size_t number_of_flags,
36 RepeatingCallback<void(size_t index)> callback) {
37 atomic_flags_.reserve(number_of_flags);
38 for (size_t i = 0; i < number_of_flags; i++) {
39 atomic_flags_.push_back(atomic_flag_set_.AddFlag(
40 base::BindRepeating([](RepeatingCallback<void(size_t index)> callback,
41 size_t i) { callback.Run(i); },
42 callback, i)));
43 }
44 }
45
46 AtomicFlagSetForTest atomic_flag_set_{AssociatedThreadId::CreateBound()};
47 std::vector<AtomicFlagSet::AtomicFlag> atomic_flags_;
48 };
49
TEST_F(AtomicFlagSetTest,VisitEmptyAtomicFlagSet)50 TEST_F(AtomicFlagSetTest, VisitEmptyAtomicFlagSet) {
51 atomic_flag_set_.RunActiveCallbacks(); // Shouldn't crash.
52 }
53
TEST_F(AtomicFlagSetTest,SetActiveOneFlag)54 TEST_F(AtomicFlagSetTest, SetActiveOneFlag) {
55 std::vector<size_t> flags_visited;
56
57 CreateFlags(3, BindLambdaForTesting(
58 [&](size_t index) { flags_visited.push_back(index); }));
59
60 atomic_flags_[1].SetActive(true);
61 EXPECT_TRUE(flags_visited.empty());
62
63 atomic_flag_set_.RunActiveCallbacks();
64 EXPECT_THAT(flags_visited, ElementsAre(1));
65
66 // A subsequent call to RunActiveCallbacks should not visit anything.
67 flags_visited.clear();
68 atomic_flag_set_.RunActiveCallbacks();
69 EXPECT_TRUE(flags_visited.empty());
70 }
71
TEST_F(AtomicFlagSetTest,SetActiveManyFlags)72 TEST_F(AtomicFlagSetTest, SetActiveManyFlags) {
73 constexpr size_t num_flags = 1000;
74 std::set<size_t> flags_visited;
75
76 CreateFlags(num_flags, BindLambdaForTesting([&](size_t index) {
77 flags_visited.insert(index);
78 }));
79
80 // Set active all even numbered flags.
81 for (size_t i = 0; i < num_flags; i += 2) {
82 atomic_flags_[i].SetActive(true);
83 }
84
85 atomic_flag_set_.RunActiveCallbacks();
86
87 ASSERT_EQ(flags_visited.size(), num_flags / 2);
88 for (size_t i = 0; i < flags_visited.size(); i++) {
89 ASSERT_EQ(flags_visited.count(i * 2), 1u);
90 }
91 }
92
TEST_F(AtomicFlagSetTest,SetActiveFalse)93 TEST_F(AtomicFlagSetTest, SetActiveFalse) {
94 std::vector<size_t> flags_visited;
95
96 CreateFlags(3, BindLambdaForTesting(
97 [&](size_t index) { flags_visited.push_back(index); }));
98
99 atomic_flags_[1].SetActive(true);
100 atomic_flags_[1].SetActive(false);
101
102 atomic_flag_set_.RunActiveCallbacks();
103 EXPECT_TRUE(flags_visited.empty());
104 }
105
TEST_F(AtomicFlagSetTest,ReleaseAtomicFlag)106 TEST_F(AtomicFlagSetTest, ReleaseAtomicFlag) {
107 constexpr size_t num_flags = 1000;
108 constexpr size_t half_num_flags = num_flags / 2;
109 std::set<size_t> flags_visited;
110
111 CreateFlags(num_flags, BindLambdaForTesting([&](size_t index) {
112 flags_visited.insert(index);
113 }));
114
115 // Set active all flags.
116 for (size_t i = 0; i < num_flags; i++) {
117 atomic_flags_[i].SetActive(true);
118 }
119
120 // Release half the AtomicFlags.
121 for (size_t i = 0; i < half_num_flags; i++) {
122 atomic_flags_[i].ReleaseAtomicFlag();
123 }
124
125 atomic_flag_set_.RunActiveCallbacks();
126
127 // We should only have visited the unreleased half.
128 ASSERT_EQ(flags_visited.size(), half_num_flags);
129 for (size_t i = 0; i < flags_visited.size(); i++) {
130 ASSERT_EQ(flags_visited.count(i + half_num_flags), 1u);
131 }
132 }
133
TEST_F(AtomicFlagSetTest,GroupBecomesFull)134 TEST_F(AtomicFlagSetTest, GroupBecomesFull) {
135 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags - 1,
136 BindLambdaForTesting([](size_t index) {}));
137 AtomicFlagSetForTest::Group* group1 =
138 atomic_flag_set_.GetAllocListForTesting();
139 EXPECT_THAT(group1->next.get(), IsNull());
140 EXPECT_EQ(group1, atomic_flag_set_.GetPartiallyFreeListForTesting());
141 EXPECT_FALSE(group1->IsFull());
142 EXPECT_FALSE(group1->IsEmpty());
143
144 // Add an extra flag to fill up the group.
145 atomic_flags_.push_back(
146 atomic_flag_set_.AddFlag(base::BindRepeating([]() {})));
147
148 EXPECT_TRUE(group1->IsFull());
149 EXPECT_THAT(atomic_flag_set_.GetPartiallyFreeListForTesting(), IsNull());
150 }
151
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyOnlyEntryInPartiallyFreeList)152 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyOnlyEntryInPartiallyFreeList) {
153 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags + 1,
154 BindLambdaForTesting([](size_t index) {}));
155
156 AtomicFlagSetForTest::Group* group1 =
157 atomic_flag_set_.GetAllocListForTesting();
158 ASSERT_THAT(group1, NotNull());
159 EXPECT_FALSE(group1->IsFull());
160 EXPECT_FALSE(group1->IsEmpty());
161 EXPECT_EQ(group1, atomic_flag_set_.GetPartiallyFreeListForTesting());
162 AtomicFlagSetForTest::Group* group2 = group1->next.get();
163 ASSERT_THAT(group2, NotNull());
164 EXPECT_THAT(group2->next.get(), IsNull());
165 EXPECT_TRUE(group2->IsFull());
166
167 // This will release |group1|.
168 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
169
170 EXPECT_THAT(group2->next.get(), IsNull());
171 EXPECT_THAT(atomic_flag_set_.GetPartiallyFreeListForTesting(), IsNull());
172 }
173
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyHeadOfPartiallyFreeList)174 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyHeadOfPartiallyFreeList) {
175 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags * 2 + 1,
176 BindLambdaForTesting([](size_t index) {}));
177
178 AtomicFlagSetForTest::Group* group1 =
179 atomic_flag_set_.GetAllocListForTesting();
180 ASSERT_THAT(group1, NotNull());
181 EXPECT_FALSE(group1->IsFull());
182 EXPECT_FALSE(group1->IsEmpty());
183 AtomicFlagSetForTest::Group* group2 = group1->next.get();
184 ASSERT_THAT(group2, NotNull());
185 EXPECT_TRUE(group2->IsFull());
186 AtomicFlagSetForTest::Group* group3 = group2->next.get();
187 ASSERT_THAT(group3, NotNull());
188 EXPECT_THAT(group3->next.get(), IsNull());
189 EXPECT_TRUE(group3->IsFull());
190
191 // |group1| is on the head of the partially free list, now add groups 2 and 3.
192 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
193 EXPECT_FALSE(group2->IsFull());
194 atomic_flags_[0].ReleaseAtomicFlag();
195 EXPECT_FALSE(group3->IsFull());
196
197 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
198 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
199 EXPECT_EQ(group3->partially_free_list_next, group2);
200 EXPECT_EQ(group2->partially_free_list_prev, group3);
201 EXPECT_EQ(group2->partially_free_list_next, group1);
202 EXPECT_EQ(group1->partially_free_list_prev, group2);
203 EXPECT_EQ(group1->partially_free_list_next, nullptr);
204 EXPECT_EQ(group1->prev, nullptr);
205 EXPECT_EQ(group2->prev, group1);
206 EXPECT_EQ(group3->prev, group2);
207
208 // This will release |group3|.
209 for (size_t i = 0; i < AtomicFlagSetForTest::Group::kNumFlags; i++) {
210 atomic_flags_[i].ReleaseAtomicFlag();
211 }
212 EXPECT_EQ(group2, atomic_flag_set_.GetPartiallyFreeListForTesting());
213 EXPECT_EQ(group2->partially_free_list_prev, nullptr);
214 EXPECT_EQ(group2->partially_free_list_next, group1);
215 EXPECT_EQ(group1->partially_free_list_prev, group2);
216 EXPECT_EQ(group1->partially_free_list_next, nullptr);
217 EXPECT_EQ(group1, atomic_flag_set_.GetAllocListForTesting());
218 EXPECT_EQ(group1->next.get(), group2);
219 EXPECT_EQ(group1->prev, nullptr);
220 EXPECT_EQ(group2->prev, group1);
221 EXPECT_EQ(group2->next.get(), nullptr);
222 }
223
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyMiddleOfPartiallyFreeList)224 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyMiddleOfPartiallyFreeList) {
225 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags * 2 + 1,
226 BindLambdaForTesting([](size_t index) {}));
227
228 AtomicFlagSetForTest::Group* group1 =
229 atomic_flag_set_.GetAllocListForTesting();
230 ASSERT_THAT(group1, NotNull());
231 EXPECT_FALSE(group1->IsFull());
232 EXPECT_FALSE(group1->IsEmpty());
233 AtomicFlagSetForTest::Group* group2 = group1->next.get();
234 ASSERT_THAT(group2, NotNull());
235 EXPECT_TRUE(group2->IsFull());
236 AtomicFlagSetForTest::Group* group3 = group2->next.get();
237 ASSERT_THAT(group3, NotNull());
238 EXPECT_THAT(group3->next.get(), IsNull());
239 EXPECT_TRUE(group3->IsFull());
240
241 // |group1| is on the head of the partially free list, now add groups 2 and 3.
242 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
243 EXPECT_FALSE(group2->IsFull());
244 atomic_flags_[0].ReleaseAtomicFlag();
245 EXPECT_FALSE(group3->IsFull());
246
247 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
248 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
249 EXPECT_EQ(group3->partially_free_list_next, group2);
250 EXPECT_EQ(group2->partially_free_list_prev, group3);
251 EXPECT_EQ(group2->partially_free_list_next, group1);
252 EXPECT_EQ(group1->partially_free_list_prev, group2);
253 EXPECT_EQ(group1->partially_free_list_next, nullptr);
254 EXPECT_EQ(group1->prev, nullptr);
255 EXPECT_EQ(group2->prev, group1);
256 EXPECT_EQ(group3->prev, group2);
257
258 // This will release |group2|.
259 for (size_t i = AtomicFlagSetForTest::Group::kNumFlags;
260 i < AtomicFlagSetForTest::Group::kNumFlags * 2; i++) {
261 atomic_flags_[i].ReleaseAtomicFlag();
262 }
263 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
264 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
265 EXPECT_EQ(group3->partially_free_list_next, group1);
266 EXPECT_EQ(group1->partially_free_list_prev, group3);
267 EXPECT_EQ(group1->partially_free_list_next, nullptr);
268 EXPECT_EQ(group1, atomic_flag_set_.GetAllocListForTesting());
269 EXPECT_EQ(group1->prev, nullptr);
270 EXPECT_EQ(group1->next.get(), group3);
271 EXPECT_EQ(group3->prev, group1);
272 EXPECT_EQ(group3->next.get(), nullptr);
273 }
274
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyTailOfPartiallyFreeList)275 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyTailOfPartiallyFreeList) {
276 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags * 2 + 1,
277 BindLambdaForTesting([](size_t index) {}));
278
279 AtomicFlagSetForTest::Group* group1 =
280 atomic_flag_set_.GetAllocListForTesting();
281 ASSERT_THAT(group1, NotNull());
282 EXPECT_FALSE(group1->IsFull());
283 EXPECT_FALSE(group1->IsEmpty());
284 AtomicFlagSetForTest::Group* group2 = group1->next.get();
285 ASSERT_THAT(group2, NotNull());
286 EXPECT_TRUE(group2->IsFull());
287 AtomicFlagSetForTest::Group* group3 = group2->next.get();
288 ASSERT_THAT(group3, NotNull());
289 EXPECT_THAT(group3->next.get(), IsNull());
290 EXPECT_TRUE(group3->IsFull());
291
292 // |group1| is on the head of the partially free list, now add groups 2 and 3.
293 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
294 EXPECT_FALSE(group2->IsFull());
295 atomic_flags_[0].ReleaseAtomicFlag();
296 EXPECT_FALSE(group3->IsFull());
297
298 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
299 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
300 EXPECT_EQ(group3->partially_free_list_next, group2);
301 EXPECT_EQ(group2->partially_free_list_prev, group3);
302 EXPECT_EQ(group2->partially_free_list_next, group1);
303 EXPECT_EQ(group1->partially_free_list_prev, group2);
304 EXPECT_EQ(group1->partially_free_list_next, nullptr);
305 EXPECT_EQ(group1->prev, nullptr);
306 EXPECT_EQ(group2->prev, group1);
307 EXPECT_EQ(group3->prev, group2);
308
309 // This will release |group1|.
310 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags * 2].ReleaseAtomicFlag();
311 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
312 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
313 EXPECT_EQ(group3->partially_free_list_next, group2);
314 EXPECT_EQ(group2->partially_free_list_prev, group3);
315 EXPECT_EQ(group2->partially_free_list_next, nullptr);
316 EXPECT_EQ(group2, atomic_flag_set_.GetAllocListForTesting());
317 EXPECT_EQ(group2->prev, nullptr);
318 EXPECT_EQ(group2->next.get(), group3);
319 EXPECT_EQ(group3->prev, group2);
320 EXPECT_EQ(group3->next.get(), nullptr);
321 }
322
323 } // namespace internal
324 } // namespace sequence_manager
325 } // namespace base
326