1 /*
2 * Copyright 2014 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "include/core/SkTypes.h"
9 #include "include/private/base/SkAlign.h"
10 #include "src/base/SkBlockAllocator.h"
11 #include "src/base/SkTBlockList.h"
12 #include "tests/Test.h"
13
14 #include <cstddef>
15 #include <cstdint>
16 #include <limits>
17 #include <type_traits>
18 #include <utility>
19 #include <vector>
20
21 namespace {
22 struct C {
C__anon1dbda7ca0111::C23 C() : fID(-1) { ++gInstCnt; }
C__anon1dbda7ca0111::C24 C(int id) : fID(id) { ++gInstCnt; }
C__anon1dbda7ca0111::C25 C(C&& c) : C(c.fID) {}
C__anon1dbda7ca0111::C26 C(const C& c) : C(c.fID) {}
27
28 C& operator=(C&&) = default;
29 C& operator=(const C&) = default;
30
~C__anon1dbda7ca0111::C31 ~C() { --gInstCnt; }
32
33 int fID;
34
35 // Under the hood, SkTBlockList and SkBlockAllocator round up to max_align_t. If 'C' was
36 // just 4 bytes, that often means the internal blocks can squeeze a few extra instances in. This
37 // is fine, but makes predicting a little trickier, so make sure C is a bit bigger.
38 int fPadding[4];
39
40 static int gInstCnt;
41 };
42 int C::gInstCnt = 0;
43
44 struct D {
45 int fID;
46 };
47
48 } // namespace
49
50 class TBlockListTestAccess {
51 public:
52 template<int N>
ScratchBlockSize(SkTBlockList<C,N> & list)53 static size_t ScratchBlockSize(SkTBlockList<C, N>& list) {
54 return (size_t) list.fAllocator->scratchBlockSize();
55 }
56
57 template<int N>
TotalSize(SkTBlockList<C,N> & list)58 static size_t TotalSize(SkTBlockList<C, N>& list) {
59 return list.fAllocator->totalSize();
60 }
61
62 static constexpr size_t kAddressAlign = SkBlockAllocator::kAddressAlign;
63 };
64
65 // Checks that the allocator has the correct count, etc and that the element IDs are correct.
66 // Then pops popCnt items and checks again.
67 template<int N>
check_allocator_helper(SkTBlockList<C,N> * allocator,int cnt,int popCnt,skiatest::Reporter * reporter)68 static void check_allocator_helper(SkTBlockList<C, N>* allocator, int cnt, int popCnt,
69 skiatest::Reporter* reporter) {
70 REPORTER_ASSERT(reporter, (0 == cnt) == allocator->empty());
71 REPORTER_ASSERT(reporter, cnt == allocator->count());
72 REPORTER_ASSERT(reporter, cnt == C::gInstCnt);
73
74 int i = 0;
75 for (const C& c : allocator->items()) {
76 REPORTER_ASSERT(reporter, i == c.fID);
77 REPORTER_ASSERT(reporter, allocator->item(i).fID == i);
78 ++i;
79 }
80 REPORTER_ASSERT(reporter, i == cnt);
81
82 if (cnt > 0) {
83 REPORTER_ASSERT(reporter, cnt-1 == allocator->back().fID);
84 }
85
86 if (popCnt > 0) {
87 for (i = 0; i < popCnt; ++i) {
88 allocator->pop_back();
89 }
90 check_allocator_helper(allocator, cnt - popCnt, 0, reporter);
91 }
92 }
93
94 template<int N>
check_iterator_helper(SkTBlockList<C,N> * allocator,const std::vector<C * > & expected,skiatest::Reporter * reporter)95 static void check_iterator_helper(SkTBlockList<C, N>* allocator,
96 const std::vector<C*>& expected,
97 skiatest::Reporter* reporter) {
98 const SkTBlockList<C, N>* cAlloc = allocator;
99 REPORTER_ASSERT(reporter, (size_t) allocator->count() == expected.size());
100 // Forward+const
101 int i = 0;
102 for (const C& c : cAlloc->items()) {
103 REPORTER_ASSERT(reporter, (uintptr_t) &c == (uintptr_t) expected[i]);
104 ++i;
105 }
106 REPORTER_ASSERT(reporter, (size_t) i == expected.size());
107
108 // Forward+non-const
109 i = 0;
110 for (C& c : allocator->items()) {
111 REPORTER_ASSERT(reporter, (uintptr_t) &c == (uintptr_t) expected[i]);
112 ++i;
113 }
114 REPORTER_ASSERT(reporter, (size_t) i == expected.size());
115
116 // Reverse+const
117 i = (int) expected.size() - 1;
118 for (const C& c : cAlloc->ritems()) {
119 REPORTER_ASSERT(reporter, (uintptr_t) &c == (uintptr_t) expected[i]);
120 --i;
121 }
122 REPORTER_ASSERT(reporter, i == -1);
123
124 // Reverse+non-const
125 i = (int) expected.size() - 1;
126 for (C& c : allocator->ritems()) {
127 REPORTER_ASSERT(reporter, (uintptr_t) &c == (uintptr_t) expected[i]);
128 --i;
129 }
130 REPORTER_ASSERT(reporter, i == -1);
131
132 // Also test random access
133 for (i = 0; i < allocator->count(); ++i) {
134 REPORTER_ASSERT(reporter, (uintptr_t) &allocator->item(i) == (uintptr_t) expected[i]);
135 REPORTER_ASSERT(reporter, (uintptr_t) &cAlloc->item(i) == (uintptr_t) expected[i]);
136 }
137 }
138
139 // Adds cnt items to the allocator, tests the cnts and iterators, pops popCnt items and checks
140 // again. Finally it resets the allocator and checks again.
141 template<int N>
check_allocator(SkTBlockList<C,N> * allocator,int cnt,int popCnt,skiatest::Reporter * reporter)142 static void check_allocator(SkTBlockList<C, N>* allocator, int cnt, int popCnt,
143 skiatest::Reporter* reporter) {
144 enum ItemInitializer : int {
145 kCopyCtor,
146 kMoveCtor,
147 kCopyAssign,
148 kMoveAssign,
149 kEmplace,
150 };
151 static constexpr int kInitCount = (int) kEmplace + 1;
152
153 SkASSERT(allocator);
154 SkASSERT(allocator->empty());
155 std::vector<C*> items;
156 for (int i = 0; i < cnt; ++i) {
157 switch((ItemInitializer) (i % kInitCount)) {
158 case kCopyCtor:
159 allocator->push_back(C(i));
160 break;
161 case kMoveCtor:
162 allocator->push_back(std::move(C(i)));
163 break;
164 case kCopyAssign:
165 allocator->push_back() = C(i);
166 break;
167 case kMoveAssign:
168 allocator->push_back() = std::move(C(i));
169 break;
170 case kEmplace:
171 allocator->emplace_back(i);
172 break;
173 }
174 items.push_back(&allocator->back());
175 }
176 check_iterator_helper(allocator, items, reporter);
177 check_allocator_helper(allocator, cnt, popCnt, reporter);
178 allocator->reset();
179 check_iterator_helper(allocator, {}, reporter);
180 check_allocator_helper(allocator, 0, 0, reporter);
181 }
182
183 template<int N>
run_allocator_test(SkTBlockList<C,N> * allocator,skiatest::Reporter * reporter)184 static void run_allocator_test(SkTBlockList<C, N>* allocator, skiatest::Reporter* reporter) {
185 check_allocator(allocator, 0, 0, reporter);
186 check_allocator(allocator, 1, 1, reporter);
187 check_allocator(allocator, 2, 2, reporter);
188 check_allocator(allocator, 10, 1, reporter);
189 check_allocator(allocator, 10, 5, reporter);
190 check_allocator(allocator, 10, 10, reporter);
191 check_allocator(allocator, 100, 10, reporter);
192 }
193
194 template<int N1, int N2>
run_concat_test(skiatest::Reporter * reporter,int aCount,int bCount)195 static void run_concat_test(skiatest::Reporter* reporter, int aCount, int bCount) {
196
197 SkTBlockList<C, N1> listA;
198 SkTBlockList<C, N2> listB;
199
200 for (int i = 0; i < aCount; ++i) {
201 listA.emplace_back(i);
202 }
203 for (int i = 0; i < bCount; ++i) {
204 listB.emplace_back(aCount + i);
205 }
206
207 REPORTER_ASSERT(reporter, listA.count() == aCount && listB.count() == bCount);
208 REPORTER_ASSERT(reporter, C::gInstCnt == aCount + bCount);
209
210 // Concatenate B into A and verify.
211 listA.concat(std::move(listB));
212 REPORTER_ASSERT(reporter, listA.count() == aCount + bCount);
213 // SkTBlockList guarantees the moved list is empty, but clang-tidy doesn't know about it;
214 // in practice we won't really be using moved lists so this won't pollute our main code base
215 // with lots of warning disables.
216 REPORTER_ASSERT(reporter, listB.count() == 0); // NOLINT(bugprone-use-after-move)
217 REPORTER_ASSERT(reporter, C::gInstCnt == aCount + bCount);
218
219 int i = 0;
220 for (const C& item : listA.items()) {
221 // By construction of A and B originally, the concatenated id sequence is continuous
222 REPORTER_ASSERT(reporter, i == item.fID);
223 i++;
224 }
225 REPORTER_ASSERT(reporter, i == (aCount + bCount));
226 }
227
228 template<int N1, int N2>
run_concat_trivial_test(skiatest::Reporter * reporter,int aCount,int bCount)229 static void run_concat_trivial_test(skiatest::Reporter* reporter, int aCount, int bCount) {
230 static_assert(std::is_trivially_copyable<D>::value);
231
232 // This is similar to run_concat_test(), except since D is trivial we can't verify the instant
233 // counts that are tracked via ctor/dtor.
234 SkTBlockList<D, N1> listA;
235 SkTBlockList<D, N2> listB;
236
237 for (int i = 0; i < aCount; ++i) {
238 listA.push_back({i});
239 }
240 for (int i = 0; i < bCount; ++i) {
241 listB.push_back({aCount + i});
242 }
243
244 REPORTER_ASSERT(reporter, listA.count() == aCount && listB.count() == bCount);
245 // Concatenate B into A and verify.
246 listA.concat(std::move(listB));
247 REPORTER_ASSERT(reporter, listA.count() == aCount + bCount);
248 REPORTER_ASSERT(reporter, listB.count() == 0); // NOLINT(bugprone-use-after-move): see above
249
250 int i = 0;
251 for (const D& item : listA.items()) {
252 // By construction of A and B originally, the concatenated id sequence is continuous
253 REPORTER_ASSERT(reporter, i == item.fID);
254 i++;
255 }
256 REPORTER_ASSERT(reporter, i == (aCount + bCount));
257 }
258
259 template<int N>
run_reserve_test(skiatest::Reporter * reporter)260 static void run_reserve_test(skiatest::Reporter* reporter) {
261 constexpr int kItemsPerBlock = N + 4; // Make this a number > 1, even if N starting items == 1
262
263 SkTBlockList<C, N> list(kItemsPerBlock);
264 size_t initialSize = TBlockListTestAccess::TotalSize(list);
265 // Should be able to add N instances of T w/o changing size from initialSize
266 for (int i = 0; i < N; ++i) {
267 list.push_back(C(i));
268 }
269 REPORTER_ASSERT(reporter, initialSize == TBlockListTestAccess::TotalSize(list));
270
271 // Reserve room for 2*kItemsPerBlock items
272 list.reserve(2 * kItemsPerBlock);
273 REPORTER_ASSERT(reporter, list.count() == N); // count shouldn't change though
274
275 size_t reservedSize = TBlockListTestAccess::TotalSize(list);
276 REPORTER_ASSERT(reporter, reservedSize >= initialSize + 2 * kItemsPerBlock * sizeof(C));
277 for (int i = 0; i < 2 * kItemsPerBlock; ++i) {
278 list.push_back(C(i));
279 }
280 REPORTER_ASSERT(reporter, reservedSize == TBlockListTestAccess::TotalSize(list));
281
282 // Make the next block partially fully (N > 0 but < kItemsPerBlock)
283 for (int i = 0; i < N; ++i) {
284 list.push_back(C(i));
285 }
286
287 // Reserve room again for 2*kItemsPerBlock, but reserve should automatically take account of the
288 // (kItemsPerBlock-N) that are still available in the active block
289 list.reserve(2 * kItemsPerBlock);
290 int extraReservedCount = kItemsPerBlock + N;
291 // Because SkTBlockList normally allocates blocks in fixed sizes, and extraReservedCount >
292 // items-per-block, it will always use that size and not that of the growth policy.
293 REPORTER_ASSERT(reporter, TBlockListTestAccess::ScratchBlockSize(list) >=
294 extraReservedCount * sizeof(C));
295
296 reservedSize = TBlockListTestAccess::TotalSize(list);
297 for (int i = 0; i < 2 * kItemsPerBlock; ++i) {
298 list.push_back(C(i));
299 }
300 REPORTER_ASSERT(reporter, reservedSize == TBlockListTestAccess::TotalSize(list));
301
302 // If we reserve a count < items-per-block, it will use the fixed size from the growth policy.
303 list.reserve(2);
304 REPORTER_ASSERT(reporter, TBlockListTestAccess::ScratchBlockSize(list) >=
305 kItemsPerBlock * sizeof(C));
306
307 // Ensure the reservations didn't initialize any more D's than anticipated
308 int expectedInstanceCount = 2 * (N + 2 * kItemsPerBlock);
309 REPORTER_ASSERT(reporter, expectedInstanceCount == C::gInstCnt);
310
311 list.reset();
312 REPORTER_ASSERT(reporter, 0 == C::gInstCnt);
313 }
314
run_large_increment_test(skiatest::Reporter * reporter)315 void run_large_increment_test(skiatest::Reporter* reporter) {
316 static constexpr size_t kIncrementMax = std::numeric_limits<uint16_t>::max();
317 // Pick an item count such that count*sizeof(C)/max align exceeds uint16_t max.
318 int itemCount = (int) (sizeof(C) * kIncrementMax / TBlockListTestAccess::kAddressAlign) + 1;
319 SkTBlockList<C> largeIncrement(itemCount);
320 // Trigger a scratch block allocation, which given default fixed growth policy, will be one
321 // block increment.
322 largeIncrement.reserve(10);
323 size_t scratchSize = TBlockListTestAccess::ScratchBlockSize(largeIncrement);
324 // SkBlockAllocator aligns large blocks to 4k
325 size_t expected = SkAlignTo(kIncrementMax * TBlockListTestAccess::kAddressAlign, (1 << 12));
326 REPORTER_ASSERT(reporter, scratchSize == expected);
327 }
328
DEF_TEST(SkTBlockList,reporter)329 DEF_TEST(SkTBlockList, reporter) {
330 // Test combinations of allocators with and without stack storage and with different block sizes
331 SkTBlockList<C> a1(1);
332 run_allocator_test(&a1, reporter);
333
334 SkTBlockList<C> a2(2);
335 run_allocator_test(&a2, reporter);
336
337 SkTBlockList<C> a5(5);
338 run_allocator_test(&a5, reporter);
339
340 SkTBlockList<C, 1> sa1;
341 run_allocator_test(&sa1, reporter);
342
343 SkTBlockList<C, 3> sa3;
344 run_allocator_test(&sa3, reporter);
345
346 SkTBlockList<C, 4> sa4;
347 run_allocator_test(&sa4, reporter);
348
349 run_reserve_test<1>(reporter);
350 run_reserve_test<2>(reporter);
351 run_reserve_test<3>(reporter);
352 run_reserve_test<4>(reporter);
353 run_reserve_test<5>(reporter);
354
355 run_concat_test<1, 1>(reporter, 10, 10);
356 run_concat_test<5, 1>(reporter, 50, 10);
357 run_concat_test<1, 5>(reporter, 10, 50);
358 run_concat_test<5, 5>(reporter, 100, 100);
359
360 run_concat_trivial_test<1, 1>(reporter, 10, 10);
361 run_concat_trivial_test<5, 1>(reporter, 50, 10);
362 run_concat_trivial_test<1, 5>(reporter, 10, 50);
363 run_concat_trivial_test<5, 5>(reporter, 100, 100);
364
365 run_large_increment_test(reporter);
366 }
367