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(atomic_flag_set_.AddFlag(base::BindRepeating([] {})));
146
147 EXPECT_TRUE(group1->IsFull());
148 EXPECT_THAT(atomic_flag_set_.GetPartiallyFreeListForTesting(), IsNull());
149 }
150
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyOnlyEntryInPartiallyFreeList)151 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyOnlyEntryInPartiallyFreeList) {
152 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags + 1,
153 BindLambdaForTesting([](size_t index) {}));
154
155 AtomicFlagSetForTest::Group* group1 =
156 atomic_flag_set_.GetAllocListForTesting();
157 ASSERT_THAT(group1, NotNull());
158 EXPECT_FALSE(group1->IsFull());
159 EXPECT_FALSE(group1->IsEmpty());
160 EXPECT_EQ(group1, atomic_flag_set_.GetPartiallyFreeListForTesting());
161 AtomicFlagSetForTest::Group* group2 = group1->next.get();
162 ASSERT_THAT(group2, NotNull());
163 EXPECT_THAT(group2->next.get(), IsNull());
164 EXPECT_TRUE(group2->IsFull());
165
166 // This will release |group1|.
167 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
168
169 EXPECT_THAT(group2->next.get(), IsNull());
170 EXPECT_THAT(atomic_flag_set_.GetPartiallyFreeListForTesting(), IsNull());
171 }
172
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyHeadOfPartiallyFreeList)173 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyHeadOfPartiallyFreeList) {
174 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags * 2 + 1,
175 BindLambdaForTesting([](size_t index) {}));
176
177 AtomicFlagSetForTest::Group* group1 =
178 atomic_flag_set_.GetAllocListForTesting();
179 ASSERT_THAT(group1, NotNull());
180 EXPECT_FALSE(group1->IsFull());
181 EXPECT_FALSE(group1->IsEmpty());
182 AtomicFlagSetForTest::Group* group2 = group1->next.get();
183 ASSERT_THAT(group2, NotNull());
184 EXPECT_TRUE(group2->IsFull());
185 AtomicFlagSetForTest::Group* group3 = group2->next.get();
186 ASSERT_THAT(group3, NotNull());
187 EXPECT_THAT(group3->next.get(), IsNull());
188 EXPECT_TRUE(group3->IsFull());
189
190 // |group1| is on the head of the partially free list, now add groups 2 and 3.
191 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
192 EXPECT_FALSE(group2->IsFull());
193 atomic_flags_[0].ReleaseAtomicFlag();
194 EXPECT_FALSE(group3->IsFull());
195
196 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
197 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
198 EXPECT_EQ(group3->partially_free_list_next, group2);
199 EXPECT_EQ(group2->partially_free_list_prev, group3);
200 EXPECT_EQ(group2->partially_free_list_next, group1);
201 EXPECT_EQ(group1->partially_free_list_prev, group2);
202 EXPECT_EQ(group1->partially_free_list_next, nullptr);
203 EXPECT_EQ(group1->prev, nullptr);
204 EXPECT_EQ(group2->prev, group1);
205 EXPECT_EQ(group3->prev, group2);
206
207 // This will release |group3|.
208 for (size_t i = 0; i < AtomicFlagSetForTest::Group::kNumFlags; i++) {
209 atomic_flags_[i].ReleaseAtomicFlag();
210 }
211 EXPECT_EQ(group2, atomic_flag_set_.GetPartiallyFreeListForTesting());
212 EXPECT_EQ(group2->partially_free_list_prev, nullptr);
213 EXPECT_EQ(group2->partially_free_list_next, group1);
214 EXPECT_EQ(group1->partially_free_list_prev, group2);
215 EXPECT_EQ(group1->partially_free_list_next, nullptr);
216 EXPECT_EQ(group1, atomic_flag_set_.GetAllocListForTesting());
217 EXPECT_EQ(group1->next.get(), group2);
218 EXPECT_EQ(group1->prev, nullptr);
219 EXPECT_EQ(group2->prev, group1);
220 EXPECT_EQ(group2->next.get(), nullptr);
221 }
222
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyMiddleOfPartiallyFreeList)223 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyMiddleOfPartiallyFreeList) {
224 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags * 2 + 1,
225 BindLambdaForTesting([](size_t index) {}));
226
227 AtomicFlagSetForTest::Group* group1 =
228 atomic_flag_set_.GetAllocListForTesting();
229 ASSERT_THAT(group1, NotNull());
230 EXPECT_FALSE(group1->IsFull());
231 EXPECT_FALSE(group1->IsEmpty());
232 AtomicFlagSetForTest::Group* group2 = group1->next.get();
233 ASSERT_THAT(group2, NotNull());
234 EXPECT_TRUE(group2->IsFull());
235 AtomicFlagSetForTest::Group* group3 = group2->next.get();
236 ASSERT_THAT(group3, NotNull());
237 EXPECT_THAT(group3->next.get(), IsNull());
238 EXPECT_TRUE(group3->IsFull());
239
240 // |group1| is on the head of the partially free list, now add groups 2 and 3.
241 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
242 EXPECT_FALSE(group2->IsFull());
243 atomic_flags_[0].ReleaseAtomicFlag();
244 EXPECT_FALSE(group3->IsFull());
245
246 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
247 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
248 EXPECT_EQ(group3->partially_free_list_next, group2);
249 EXPECT_EQ(group2->partially_free_list_prev, group3);
250 EXPECT_EQ(group2->partially_free_list_next, group1);
251 EXPECT_EQ(group1->partially_free_list_prev, group2);
252 EXPECT_EQ(group1->partially_free_list_next, nullptr);
253 EXPECT_EQ(group1->prev, nullptr);
254 EXPECT_EQ(group2->prev, group1);
255 EXPECT_EQ(group3->prev, group2);
256
257 // This will release |group2|.
258 for (size_t i = AtomicFlagSetForTest::Group::kNumFlags;
259 i < AtomicFlagSetForTest::Group::kNumFlags * 2; i++) {
260 atomic_flags_[i].ReleaseAtomicFlag();
261 }
262 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
263 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
264 EXPECT_EQ(group3->partially_free_list_next, group1);
265 EXPECT_EQ(group1->partially_free_list_prev, group3);
266 EXPECT_EQ(group1->partially_free_list_next, nullptr);
267 EXPECT_EQ(group1, atomic_flag_set_.GetAllocListForTesting());
268 EXPECT_EQ(group1->prev, nullptr);
269 EXPECT_EQ(group1->next.get(), group3);
270 EXPECT_EQ(group3->prev, group1);
271 EXPECT_EQ(group3->next.get(), nullptr);
272 }
273
TEST_F(AtomicFlagSetTest,GroupBecomesEmptyTailOfPartiallyFreeList)274 TEST_F(AtomicFlagSetTest, GroupBecomesEmptyTailOfPartiallyFreeList) {
275 CreateFlags(AtomicFlagSetForTest::Group::kNumFlags * 2 + 1,
276 BindLambdaForTesting([](size_t index) {}));
277
278 AtomicFlagSetForTest::Group* group1 =
279 atomic_flag_set_.GetAllocListForTesting();
280 ASSERT_THAT(group1, NotNull());
281 EXPECT_FALSE(group1->IsFull());
282 EXPECT_FALSE(group1->IsEmpty());
283 AtomicFlagSetForTest::Group* group2 = group1->next.get();
284 ASSERT_THAT(group2, NotNull());
285 EXPECT_TRUE(group2->IsFull());
286 AtomicFlagSetForTest::Group* group3 = group2->next.get();
287 ASSERT_THAT(group3, NotNull());
288 EXPECT_THAT(group3->next.get(), IsNull());
289 EXPECT_TRUE(group3->IsFull());
290
291 // |group1| is on the head of the partially free list, now add groups 2 and 3.
292 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags].ReleaseAtomicFlag();
293 EXPECT_FALSE(group2->IsFull());
294 atomic_flags_[0].ReleaseAtomicFlag();
295 EXPECT_FALSE(group3->IsFull());
296
297 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
298 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
299 EXPECT_EQ(group3->partially_free_list_next, group2);
300 EXPECT_EQ(group2->partially_free_list_prev, group3);
301 EXPECT_EQ(group2->partially_free_list_next, group1);
302 EXPECT_EQ(group1->partially_free_list_prev, group2);
303 EXPECT_EQ(group1->partially_free_list_next, nullptr);
304 EXPECT_EQ(group1->prev, nullptr);
305 EXPECT_EQ(group2->prev, group1);
306 EXPECT_EQ(group3->prev, group2);
307
308 // This will release |group1|.
309 atomic_flags_[AtomicFlagSetForTest::Group::kNumFlags * 2].ReleaseAtomicFlag();
310 EXPECT_EQ(group3, atomic_flag_set_.GetPartiallyFreeListForTesting());
311 EXPECT_EQ(group3->partially_free_list_prev, nullptr);
312 EXPECT_EQ(group3->partially_free_list_next, group2);
313 EXPECT_EQ(group2->partially_free_list_prev, group3);
314 EXPECT_EQ(group2->partially_free_list_next, nullptr);
315 EXPECT_EQ(group2, atomic_flag_set_.GetAllocListForTesting());
316 EXPECT_EQ(group2->prev, nullptr);
317 EXPECT_EQ(group2->next.get(), group3);
318 EXPECT_EQ(group3->prev, group2);
319 EXPECT_EQ(group3->next.get(), nullptr);
320 }
321
322 } // namespace internal
323 } // namespace sequence_manager
324 } // namespace base
325