1 // Copyright 2021 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 "partition_alloc/starscan/state_bitmap.h"
6
7 #include <cstdint>
8
9 #include "partition_alloc/page_allocator.h"
10 #include "partition_alloc/partition_alloc_constants.h"
11 #include "testing/gtest/include/gtest/gtest.h"
12
13 namespace partition_alloc::internal {
14
15 namespace {
16
17 using TestBitmap = StateBitmap<kSuperPageSize, kSuperPageSize, kAlignment>;
18
19 class PageWithBitmap final {
20 public:
PageWithBitmap()21 PageWithBitmap()
22 : base_(AllocPages(kSuperPageSize,
23 kSuperPageAlignment,
24 PageAccessibilityConfiguration(
25 PageAccessibilityConfiguration::kReadWrite),
26 PageTag::kPartitionAlloc)),
27 bitmap_(new(reinterpret_cast<void*>(base_)) TestBitmap) {}
28
29 PageWithBitmap(const PageWithBitmap&) = delete;
30 PageWithBitmap& operator=(const PageWithBitmap&) = delete;
31
~PageWithBitmap()32 ~PageWithBitmap() { FreePages(base_, kSuperPageSize); }
33
bitmap() const34 TestBitmap& bitmap() const { return *bitmap_; }
35
base() const36 void* base() const { return reinterpret_cast<void*>(base_); }
size() const37 size_t size() const { return kSuperPageSize; }
38
39 uintptr_t base_;
40 TestBitmap* bitmap_;
41 };
42
43 class PartitionAllocStateBitmapTest : public ::testing::Test {
44 protected:
bitmap() const45 TestBitmap& bitmap() const { return page.bitmap(); }
46
AllocateObject(size_t object_position)47 void AllocateObject(size_t object_position) {
48 page.bitmap().Allocate(ObjectAddress(object_position));
49 }
50
FreeObject(size_t object_position)51 void FreeObject(size_t object_position) {
52 page.bitmap().Free(ObjectAddress(object_position));
53 }
54
QuarantineObject(size_t object_position,size_t epoch)55 bool QuarantineObject(size_t object_position, size_t epoch) {
56 return page.bitmap().Quarantine(ObjectAddress(object_position), epoch);
57 }
58
MarkQuarantinedObject(size_t object_position,size_t epoch)59 bool MarkQuarantinedObject(size_t object_position, size_t epoch) {
60 return page.bitmap().MarkQuarantinedAsReachable(
61 ObjectAddress(object_position), epoch);
62 }
63
IsAllocated(size_t object_position) const64 bool IsAllocated(size_t object_position) const {
65 return page.bitmap().IsAllocated(ObjectAddress(object_position));
66 }
67
IsQuarantined(size_t object_position) const68 bool IsQuarantined(size_t object_position) const {
69 return page.bitmap().IsQuarantined(ObjectAddress(object_position));
70 }
71
IsFreed(size_t object_position) const72 bool IsFreed(size_t object_position) const {
73 return page.bitmap().IsFreed(ObjectAddress(object_position));
74 }
75
AssertAllocated(size_t object_position) const76 void AssertAllocated(size_t object_position) const {
77 EXPECT_TRUE(IsAllocated(object_position));
78 EXPECT_FALSE(IsQuarantined(object_position));
79 EXPECT_FALSE(IsFreed(object_position));
80 }
81
AssertFreed(size_t object_position) const82 void AssertFreed(size_t object_position) const {
83 EXPECT_FALSE(IsAllocated(object_position));
84 EXPECT_FALSE(IsQuarantined(object_position));
85 EXPECT_TRUE(IsFreed(object_position));
86 }
87
AssertQuarantined(size_t object_position) const88 void AssertQuarantined(size_t object_position) const {
89 EXPECT_FALSE(IsAllocated(object_position));
90 EXPECT_TRUE(IsQuarantined(object_position));
91 EXPECT_FALSE(IsFreed(object_position));
92 }
93
CountAllocated() const94 size_t CountAllocated() const {
95 size_t count = 0;
96 bitmap().IterateAllocated([&count](uintptr_t) { count++; });
97 return count;
98 }
99
CountQuarantined() const100 size_t CountQuarantined() const {
101 size_t count = 0;
102 bitmap().IterateQuarantined([&count](uintptr_t) { count++; });
103 return count;
104 }
105
IsQuarantineEmpty() const106 bool IsQuarantineEmpty() const { return !CountQuarantined(); }
107
ObjectAddress(size_t pos) const108 uintptr_t ObjectAddress(size_t pos) const {
109 return reinterpret_cast<uintptr_t>(page.base()) + sizeof(TestBitmap) +
110 pos * kAlignment;
111 }
112
LastIndex()113 static constexpr uintptr_t LastIndex() {
114 return TestBitmap::kMaxEntries - (sizeof(TestBitmap) / kAlignment) - 1;
115 }
116
MiddleIndex()117 static constexpr uintptr_t MiddleIndex() { return LastIndex() / 2; }
118
119 private:
120 PageWithBitmap page;
121 };
122
123 constexpr size_t kTestEpoch = 0;
124
125 } // namespace
126
TEST_F(PartitionAllocStateBitmapTest,MoreThanZeroEntriesPossible)127 TEST_F(PartitionAllocStateBitmapTest, MoreThanZeroEntriesPossible) {
128 const size_t max_entries = TestBitmap::kMaxEntries;
129 EXPECT_LT(0u, max_entries);
130 }
131
TEST_F(PartitionAllocStateBitmapTest,InitialQuarantineEmpty)132 TEST_F(PartitionAllocStateBitmapTest, InitialQuarantineEmpty) {
133 EXPECT_TRUE(IsQuarantineEmpty());
134 }
135
TEST_F(PartitionAllocStateBitmapTest,QuarantineImpliesNonEmpty)136 TEST_F(PartitionAllocStateBitmapTest, QuarantineImpliesNonEmpty) {
137 AllocateObject(0);
138 EXPECT_TRUE(IsQuarantineEmpty());
139 QuarantineObject(0, kTestEpoch);
140 EXPECT_FALSE(IsQuarantineEmpty());
141 }
142
TEST_F(PartitionAllocStateBitmapTest,RepetitiveQuarantine)143 TEST_F(PartitionAllocStateBitmapTest, RepetitiveQuarantine) {
144 AllocateObject(MiddleIndex());
145 EXPECT_TRUE(QuarantineObject(MiddleIndex(), kTestEpoch));
146 EXPECT_FALSE(QuarantineObject(MiddleIndex(), kTestEpoch));
147 }
148
TEST_F(PartitionAllocStateBitmapTest,CountAllocated)149 TEST_F(PartitionAllocStateBitmapTest, CountAllocated) {
150 AllocateObject(0);
151 EXPECT_EQ(1u, CountAllocated());
152 QuarantineObject(0, kTestEpoch);
153 EXPECT_EQ(0u, CountAllocated());
154 }
155
TEST_F(PartitionAllocStateBitmapTest,StateTransititions)156 TEST_F(PartitionAllocStateBitmapTest, StateTransititions) {
157 for (auto i : {uintptr_t{0}, uintptr_t{1}, LastIndex() - 1, LastIndex()}) {
158 AssertFreed(i);
159
160 AllocateObject(i);
161 AssertAllocated(i);
162
163 QuarantineObject(i, kTestEpoch);
164 AssertQuarantined(i);
165
166 MarkQuarantinedObject(i, kTestEpoch);
167 AssertQuarantined(i);
168
169 FreeObject(i);
170 AssertFreed(i);
171 }
172 }
173
TEST_F(PartitionAllocStateBitmapTest,MultipleMarks)174 TEST_F(PartitionAllocStateBitmapTest, MultipleMarks) {
175 AllocateObject(0);
176 QuarantineObject(0, kTestEpoch);
177
178 EXPECT_TRUE(MarkQuarantinedObject(0, kTestEpoch));
179 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch));
180 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch));
181
182 EXPECT_TRUE(MarkQuarantinedObject(0, kTestEpoch + 1));
183 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch + 1));
184 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch + 1));
185
186 EXPECT_TRUE(MarkQuarantinedObject(0, kTestEpoch + 2));
187 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch + 2));
188 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch + 2));
189 }
190
TEST_F(PartitionAllocStateBitmapTest,MultipleMarksAdjacent)191 TEST_F(PartitionAllocStateBitmapTest, MultipleMarksAdjacent) {
192 AllocateObject(0);
193 QuarantineObject(0, kTestEpoch);
194
195 AllocateObject(1);
196 QuarantineObject(1, kTestEpoch);
197
198 AllocateObject(2);
199 QuarantineObject(2, kTestEpoch);
200
201 EXPECT_TRUE(MarkQuarantinedObject(0, kTestEpoch));
202 EXPECT_TRUE(MarkQuarantinedObject(1, kTestEpoch));
203 EXPECT_TRUE(MarkQuarantinedObject(2, kTestEpoch));
204 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch));
205 EXPECT_FALSE(MarkQuarantinedObject(1, kTestEpoch));
206 EXPECT_FALSE(MarkQuarantinedObject(2, kTestEpoch));
207
208 EXPECT_TRUE(MarkQuarantinedObject(0, kTestEpoch + 1));
209 EXPECT_TRUE(MarkQuarantinedObject(1, kTestEpoch + 1));
210 EXPECT_TRUE(MarkQuarantinedObject(2, kTestEpoch + 1));
211 EXPECT_FALSE(MarkQuarantinedObject(0, kTestEpoch + 1));
212 EXPECT_FALSE(MarkQuarantinedObject(1, kTestEpoch + 1));
213 EXPECT_FALSE(MarkQuarantinedObject(2, kTestEpoch + 1));
214 }
215
TEST_F(PartitionAllocStateBitmapTest,QuarantineFreeMultipleObjects)216 TEST_F(PartitionAllocStateBitmapTest, QuarantineFreeMultipleObjects) {
217 static constexpr size_t kCount = 256;
218 for (size_t i = 0; i < kCount; ++i) {
219 AllocateObject(i);
220 }
221 EXPECT_EQ(kCount, CountAllocated());
222 EXPECT_EQ(0u, CountQuarantined());
223
224 for (size_t i = 0; i < kCount; ++i) {
225 QuarantineObject(i, kTestEpoch);
226 }
227 EXPECT_EQ(0u, CountAllocated());
228 EXPECT_EQ(kCount, CountQuarantined());
229
230 for (size_t i = 0; i < kCount; ++i) {
231 FreeObject(i);
232 EXPECT_EQ(kCount - i - 1, CountQuarantined());
233 }
234 EXPECT_TRUE(IsQuarantineEmpty());
235 }
236
TEST_F(PartitionAllocStateBitmapTest,AdjacentQuarantinedObjectsAtBegin)237 TEST_F(PartitionAllocStateBitmapTest, AdjacentQuarantinedObjectsAtBegin) {
238 AllocateObject(0);
239 QuarantineObject(0, kTestEpoch);
240 AllocateObject(1);
241 QuarantineObject(1, kTestEpoch);
242
243 EXPECT_FALSE(IsQuarantined(2));
244 {
245 size_t count = 0;
246 this->bitmap().IterateQuarantined([&count, this](uintptr_t current) {
247 if (count == 0) {
248 EXPECT_EQ(ObjectAddress(0), current);
249 } else if (count == 1) {
250 EXPECT_EQ(ObjectAddress(1), current);
251 }
252 count++;
253 });
254
255 EXPECT_EQ(2u, count);
256 }
257 // Now mark only the first object.
258 {
259 MarkQuarantinedObject(0, kTestEpoch);
260
261 size_t count = 0;
262 this->bitmap().IterateUnmarkedQuarantined(
263 kTestEpoch, [&count, this](uintptr_t current) {
264 if (count == 0) {
265 EXPECT_EQ(ObjectAddress(1), current);
266 }
267 count++;
268 });
269
270 EXPECT_EQ(1u, count);
271 }
272 }
273
TEST_F(PartitionAllocStateBitmapTest,AdjacentQuarantinedObjectsAtMiddle)274 TEST_F(PartitionAllocStateBitmapTest, AdjacentQuarantinedObjectsAtMiddle) {
275 AllocateObject(MiddleIndex());
276 QuarantineObject(MiddleIndex(), kTestEpoch);
277 AllocateObject(MiddleIndex() + 1);
278 QuarantineObject(MiddleIndex() + 1, kTestEpoch);
279 {
280 size_t count = 0;
281 this->bitmap().IterateQuarantined([&count, this](uintptr_t current) {
282 if (count == 0) {
283 EXPECT_EQ(ObjectAddress(MiddleIndex()), current);
284 } else if (count == 1) {
285 EXPECT_EQ(ObjectAddress(MiddleIndex() + 1), current);
286 }
287 count++;
288 });
289
290 EXPECT_EQ(2u, count);
291 }
292 // Now mark only the first object.
293 {
294 MarkQuarantinedObject(MiddleIndex(), kTestEpoch);
295
296 size_t count = 0;
297 this->bitmap().IterateUnmarkedQuarantined(
298 kTestEpoch, [&count, this](uintptr_t current) {
299 if (count == 0) {
300 EXPECT_EQ(ObjectAddress(MiddleIndex() + 1), current);
301 }
302 count++;
303 });
304
305 EXPECT_EQ(1u, count);
306 }
307 }
308
TEST_F(PartitionAllocStateBitmapTest,AdjacentQuarantinedObjectsAtEnd)309 TEST_F(PartitionAllocStateBitmapTest, AdjacentQuarantinedObjectsAtEnd) {
310 AllocateObject(LastIndex());
311 QuarantineObject(LastIndex(), kTestEpoch);
312 AllocateObject(LastIndex() - 1);
313 QuarantineObject(LastIndex() - 1, kTestEpoch);
314
315 EXPECT_FALSE(IsQuarantined(LastIndex() - 2));
316 {
317 size_t count = 0;
318 this->bitmap().IterateQuarantined([&count, this](uintptr_t current) {
319 if (count == 0) {
320 EXPECT_EQ(ObjectAddress(LastIndex() - 1), current);
321 } else if (count == 1) {
322 EXPECT_EQ(ObjectAddress(LastIndex()), current);
323 }
324 count++;
325 });
326
327 EXPECT_EQ(2u, count);
328 }
329 // Now mark only the first object.
330 {
331 MarkQuarantinedObject(LastIndex(), kTestEpoch);
332
333 size_t count = 0;
334 this->bitmap().IterateUnmarkedQuarantined(
335 kTestEpoch, [&count, this](uintptr_t current) {
336 if (count == 0) {
337 EXPECT_EQ(ObjectAddress(LastIndex() - 1), current);
338 }
339 count++;
340 });
341
342 EXPECT_EQ(1u, count);
343 }
344 }
345
346 } // namespace partition_alloc::internal
347