Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(76)

Side by Side Diff: third_party/WebKit/Source/platform/heap/HeapCompactTest.cpp

Issue 2531973002: Simple BlinkGC heap compaction. (Closed)
Patch Set: add more comments Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(Empty)
1 // Copyright 2016 Opera Software AS. All rights reserved.
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 "platform/heap/HeapCompact.h"
6
7 #include "platform/heap/Handle.h"
8 #include "platform/heap/SparseHeapBitmap.h"
9 #include "testing/gtest/include/gtest/gtest.h"
10 #include "wtf/Deque.h"
11 #include "wtf/HashMap.h"
12 #include "wtf/LinkedHashSet.h"
13 #include "wtf/Vector.h"
14
15 #include <memory>
16
17 namespace blink {
18 class IntWrapper;
19 }
20
21 using IntVector = blink::HeapVector<blink::Member<blink::IntWrapper>>;
22 using IntDeque = blink::HeapDeque<blink::Member<blink::IntWrapper>>;
23 using IntMap = blink::HeapHashMap<blink::Member<blink::IntWrapper>, int>;
24 // TODO(sof): decide if this ought to be a global trait specialization.
25 // (i.e., for HeapHash*<T>.)
26 WTF_ALLOW_CLEAR_UNUSED_SLOTS_WITH_MEM_FUNCTIONS(IntMap);
27
28 namespace blink {
29
30 static const size_t chunkSize = SparseHeapBitmap::s_maxRange;
31
32 TEST(HeapCompactTest, SparseBitmapBasic) {
33 Address base = reinterpret_cast<Address>(0x1000u);
34 std::unique_ptr<SparseHeapBitmap> bitmap = SparseHeapBitmap::create(base);
35
36 // 101010... starting at |base|.
37 for (unsigned i = 0; i < 2 * chunkSize; i += 2)
38 bitmap->add(base + i);
39
40 // Check that hasRange() returns a bitmap subtree, if any, for a given
41 // address.
42 EXPECT_TRUE(!!bitmap->hasRange(base, 1));
43 EXPECT_TRUE(!!bitmap->hasRange(base + 1, 1));
44 EXPECT_FALSE(!!bitmap->hasRange(base - 1, 1));
45
46 // Test implementation details.. that each SparseHeapBitmap node maps
47 // |s_maxRange|
48 // ranges only.
49 EXPECT_EQ(bitmap->hasRange(base + 1, 1), bitmap->hasRange(base + 2, 1));
50 EXPECT_NE(bitmap->hasRange(base, 1), bitmap->hasRange(base + chunkSize, 1));
51
52 SparseHeapBitmap* start = bitmap->hasRange(base + 2, 20);
53 EXPECT_TRUE(!!start);
54 for (unsigned i = 2; i < chunkSize * 2; i += 2) {
55 EXPECT_TRUE(start->isSet(base + i));
56 EXPECT_FALSE(start->isSet(base + i + 1));
57 }
58 }
59
60 TEST(HeapCompactTest, SparseBitmapBuild) {
61 Address base = reinterpret_cast<Address>(0x1000u);
62 std::unique_ptr<SparseHeapBitmap> bitmap = SparseHeapBitmap::create(base);
63
64 size_t doubleChunk = 2 * chunkSize;
65
66 // Create a sparse bitmap tree,
67 bitmap->add(base - doubleChunk);
68 bitmap->add(base + doubleChunk);
69
70 SparseHeapBitmap* start = bitmap->hasRange(base - doubleChunk - 2, 20);
71 EXPECT_TRUE(!!start);
72 EXPECT_TRUE(start->isSet(base - doubleChunk));
73 EXPECT_FALSE(start->isSet(base - doubleChunk + 1));
74 EXPECT_FALSE(start->isSet(base));
75 EXPECT_FALSE(start->isSet(base + 1));
76 EXPECT_FALSE(start->isSet(base + doubleChunk));
77 EXPECT_FALSE(start->isSet(base + doubleChunk + 1));
78
79 start = bitmap->hasRange(base - doubleChunk - 2, 2048);
80 EXPECT_TRUE(!!start);
81 EXPECT_TRUE(start->isSet(base - doubleChunk));
82 EXPECT_FALSE(start->isSet(base - doubleChunk + 1));
83 EXPECT_TRUE(start->isSet(base));
84 EXPECT_FALSE(start->isSet(base + 1));
85 EXPECT_TRUE(start->isSet(base + doubleChunk));
86 EXPECT_FALSE(start->isSet(base + doubleChunk + 1));
87
88 start = bitmap->hasRange(base, 20);
89 EXPECT_TRUE(!!start);
90 // Probing for values outside of hasRange() should be considered
91 // undefined, but do it to exercise the (left) tree traversal.
92 EXPECT_TRUE(start->isSet(base - doubleChunk));
93 EXPECT_FALSE(start->isSet(base - doubleChunk + 1));
94 EXPECT_TRUE(start->isSet(base));
95 EXPECT_FALSE(start->isSet(base + 1));
96 EXPECT_TRUE(start->isSet(base + doubleChunk));
97 EXPECT_FALSE(start->isSet(base + doubleChunk + 1));
98
99 start = bitmap->hasRange(base + chunkSize + 2, 2048);
100 EXPECT_TRUE(!!start);
101 // Probing for values outside of hasRange() should be considered
102 // undefined, but do it to exercise the (left) tree traversal.
103 EXPECT_FALSE(start->isSet(base - doubleChunk));
104 EXPECT_FALSE(start->isSet(base - doubleChunk + 1));
105 EXPECT_FALSE(start->isSet(base));
106 EXPECT_FALSE(start->isSet(base + 1));
107 EXPECT_FALSE(start->isSet(base + chunkSize));
108 EXPECT_TRUE(start->isSet(base + doubleChunk));
109 EXPECT_FALSE(start->isSet(base + doubleChunk + 1));
110 }
111
112 TEST(HeapCompactTest, SparseBitmapLeftExtension) {
113 Address base = reinterpret_cast<Address>(0x1000u);
114 std::unique_ptr<SparseHeapBitmap> bitmap = SparseHeapBitmap::create(base);
115
116 SparseHeapBitmap* start = bitmap->hasRange(base, 1);
117 EXPECT_TRUE(start);
118
119 // Verify that re-adding is a no-op.
120 bitmap->add(base);
121 EXPECT_EQ(start, bitmap->hasRange(base, 1));
122
123 // Adding an Address |A| before a single-address SparseHeapBitmap node should
124 // cause that node to be "left extended" to use |A| as its new base.
125 bitmap->add(base - 2);
126 EXPECT_EQ(bitmap->hasRange(base, 1), bitmap->hasRange(base - 2, 1));
127
128 // Reset.
129 bitmap = SparseHeapBitmap::create(base);
130
131 // If attempting same as above, but the Address |A| is outside the
132 // chunk size of a node, a new SparseHeapBitmap node needs to be
133 // created to the left of |bitmap|.
134 bitmap->add(base - chunkSize);
135 EXPECT_NE(bitmap->hasRange(base, 1), bitmap->hasRange(base - 2, 1));
136
137 bitmap = SparseHeapBitmap::create(base);
138 bitmap->add(base - chunkSize + 1);
139 // This address is just inside the horizon and shouldn't create a new chunk.
140 EXPECT_EQ(bitmap->hasRange(base, 1), bitmap->hasRange(base - 2, 1));
141 // ..but this one should, like for the sub-test above.
142 bitmap->add(base - chunkSize);
143 EXPECT_EQ(bitmap->hasRange(base, 1), bitmap->hasRange(base - 2, 1));
144 EXPECT_NE(bitmap->hasRange(base, 1), bitmap->hasRange(base - chunkSize, 1));
145 }
146
147 static void preciselyCollectGarbage() {
148 ThreadState::current()->collectGarbage(
149 BlinkGC::NoHeapPointersOnStack, BlinkGC::GCWithSweep, BlinkGC::ForcedGC);
150 }
151
152 static void performHeapCompaction() {
153 EXPECT_FALSE(HeapCompact::scheduleCompactionGCForTesting(true));
154 preciselyCollectGarbage();
155 EXPECT_FALSE(HeapCompact::scheduleCompactionGCForTesting(false));
156 }
157
158 // Do several GCs to make sure that later GCs don't free up old memory from
159 // previously run tests in this process.
160 static void clearOutOldGarbage() {
161 ThreadHeap& heap = ThreadState::current()->heap();
162 while (true) {
163 size_t used = heap.objectPayloadSizeForTesting();
164 preciselyCollectGarbage();
165 if (heap.objectPayloadSizeForTesting() >= used)
166 break;
167 }
168 }
169
170 class IntWrapper : public GarbageCollectedFinalized<IntWrapper> {
171 public:
172 static IntWrapper* create(int x) { return new IntWrapper(x); }
173
174 virtual ~IntWrapper() { ++s_destructorCalls; }
175
176 static int s_destructorCalls;
177 DEFINE_INLINE_TRACE() {}
178
179 int value() const { return m_x; }
180
181 bool operator==(const IntWrapper& other) const {
182 return other.value() == value();
183 }
184
185 unsigned hash() { return IntHash<int>::hash(m_x); }
186
187 IntWrapper(int x) : m_x(x) {}
188
189 private:
190 IntWrapper();
191 int m_x;
192 };
193 static_assert(WTF::IsTraceable<IntWrapper>::value,
194 "IsTraceable<> template failed to recognize trace method.");
195
196 TEST(HeapCompactTest, CompactVector) {
197 clearOutOldGarbage();
198
199 IntWrapper* val = IntWrapper::create(1);
200 Persistent<IntVector> vector = new IntVector(10, val);
201 EXPECT_EQ(10u, vector->size());
202
203 for (size_t i = 0; i < vector->size(); ++i)
204 EXPECT_EQ(val, (*vector)[i]);
205
206 performHeapCompaction();
207
208 for (size_t i = 0; i < vector->size(); ++i)
209 EXPECT_EQ(val, (*vector)[i]);
210 }
211
212 TEST(HeapCompactTest, CompactHashMap) {
213 clearOutOldGarbage();
214
215 Persistent<IntMap> intMap = new IntMap();
216 for (size_t i = 0; i < 100; ++i) {
217 IntWrapper* val = IntWrapper::create(i);
218 intMap->add(val, 100 - i);
219 }
220
221 EXPECT_EQ(100u, intMap->size());
222 for (auto k : *intMap)
223 EXPECT_EQ(k.key->value(), 100 - k.value);
224
225 performHeapCompaction();
226
227 for (auto k : *intMap)
228 EXPECT_EQ(k.key->value(), 100 - k.value);
229 }
230
231 TEST(HeapCompactTest, CompactVectorPartHashMap) {
232 clearOutOldGarbage();
233
234 using IntMapVector = HeapVector<IntMap>;
235
236 Persistent<IntMapVector> intMapVector = new IntMapVector();
237 for (size_t i = 0; i < 10; ++i) {
238 IntMap map;
239 for (size_t j = 0; j < 10; ++j) {
240 IntWrapper* val = IntWrapper::create(j);
241 map.add(val, 10 - j);
242 }
243 intMapVector->append(map);
244 }
245
246 EXPECT_EQ(10u, intMapVector->size());
247 for (auto map : *intMapVector) {
248 EXPECT_EQ(10u, map.size());
249 for (auto k : map) {
250 EXPECT_EQ(k.key->value(), 10 - k.value);
251 }
252 }
253
254 performHeapCompaction();
255
256 EXPECT_EQ(10u, intMapVector->size());
257 for (auto map : *intMapVector) {
258 EXPECT_EQ(10u, map.size());
259 for (auto k : map) {
260 EXPECT_EQ(k.key->value(), 10 - k.value);
261 }
262 }
263 }
264
265 TEST(HeapCompactTest, CompactHashPartVector) {
266 clearOutOldGarbage();
267
268 using IntVectorMap = HeapHashMap<int, IntVector>;
269
270 Persistent<IntVectorMap> intVectorMap = new IntVectorMap();
271 for (size_t i = 0; i < 10; ++i) {
272 IntVector vector;
273 for (size_t j = 0; j < 10; ++j) {
274 vector.append(IntWrapper::create(j));
275 }
276 intVectorMap->add(1 + i, vector);
277 }
278
279 EXPECT_EQ(10u, intVectorMap->size());
280 for (const IntVector& intVector : intVectorMap->values()) {
281 EXPECT_EQ(10u, intVector.size());
282 for (size_t i = 0; i < intVector.size(); ++i) {
283 EXPECT_EQ(static_cast<int>(i), intVector[i]->value());
284 }
285 }
286
287 performHeapCompaction();
288
289 EXPECT_EQ(10u, intVectorMap->size());
290 for (const IntVector& intVector : intVectorMap->values()) {
291 EXPECT_EQ(10u, intVector.size());
292 for (size_t i = 0; i < intVector.size(); ++i) {
293 EXPECT_EQ(static_cast<int>(i), intVector[i]->value());
294 }
295 }
296 }
297
298 TEST(HeapCompactTest, CompactDeques) {
299 Persistent<IntDeque> deque = new IntDeque;
300 for (int i = 0; i < 8; ++i) {
301 deque->prepend(IntWrapper::create(i));
302 }
303 EXPECT_EQ(8u, deque->size());
304
305 for (size_t i = 0; i < deque->size(); ++i)
306 EXPECT_EQ(static_cast<int>(7 - i), deque->at(i)->value());
307
308 performHeapCompaction();
309
310 for (size_t i = 0; i < deque->size(); ++i)
311 EXPECT_EQ(static_cast<int>(7 - i), deque->at(i)->value());
312 }
313
314 TEST(HeapCompactTest, CompactDequeVectors) {
315 Persistent<HeapDeque<IntVector>> deque = new HeapDeque<IntVector>;
316 for (int i = 0; i < 8; ++i) {
317 IntWrapper* value = IntWrapper::create(i);
318 IntVector vector = IntVector(8, value);
319 deque->prepend(vector);
320 }
321 EXPECT_EQ(8u, deque->size());
322
323 for (size_t i = 0; i < deque->size(); ++i)
324 EXPECT_EQ(static_cast<int>(7 - i), deque->at(i).at(i)->value());
325
326 performHeapCompaction();
327
328 for (size_t i = 0; i < deque->size(); ++i)
329 EXPECT_EQ(static_cast<int>(7 - i), deque->at(i).at(i)->value());
330 }
331
332 TEST(HeapCompactTest, CompactLinkedHashSet) {
333 using OrderedHashSet = HeapLinkedHashSet<Member<IntWrapper>>;
334 Persistent<OrderedHashSet> set = new OrderedHashSet;
335 for (int i = 0; i < 13; ++i) {
336 IntWrapper* value = IntWrapper::create(i);
337 set->add(value);
338 }
339 EXPECT_EQ(13u, set->size());
340
341 int expected = 0;
342 for (IntWrapper* v : *set) {
343 EXPECT_EQ(expected, v->value());
344 expected++;
345 }
346
347 performHeapCompaction();
348
349 expected = 0;
350 for (IntWrapper* v : *set) {
351 EXPECT_EQ(expected, v->value());
352 expected++;
353 }
354 }
355
356 TEST(HeapCompactTest, CompactLinkedHashSetVector) {
357 using OrderedHashSet = HeapLinkedHashSet<Member<IntVector>>;
358 Persistent<OrderedHashSet> set = new OrderedHashSet;
359 for (int i = 0; i < 13; ++i) {
360 IntWrapper* value = IntWrapper::create(i);
361 IntVector* vector = new IntVector(19, value);
362 set->add(vector);
363 }
364 EXPECT_EQ(13u, set->size());
365
366 int expected = 0;
367 for (IntVector* v : *set) {
368 EXPECT_EQ(expected, (*v)[0]->value());
369 expected++;
370 }
371
372 performHeapCompaction();
373
374 expected = 0;
375 for (IntVector* v : *set) {
376 EXPECT_EQ(expected, (*v)[0]->value());
377 expected++;
378 }
379 }
380
381 TEST(HeapCompactTest, CompactLinkedHashSetMap) {
382 using Inner = HeapHashSet<Member<IntWrapper>>;
383 using OrderedHashSet = HeapLinkedHashSet<Member<Inner>>;
384
385 Persistent<OrderedHashSet> set = new OrderedHashSet;
386 for (int i = 0; i < 13; ++i) {
387 IntWrapper* value = IntWrapper::create(i);
388 Inner* inner = new Inner;
389 inner->add(value);
390 set->add(inner);
391 }
392 EXPECT_EQ(13u, set->size());
393
394 int expected = 0;
395 for (const Inner* v : *set) {
396 EXPECT_EQ(1u, v->size());
397 EXPECT_EQ(expected, (*v->begin())->value());
398 expected++;
399 }
400
401 performHeapCompaction();
402
403 expected = 0;
404 for (const Inner* v : *set) {
405 EXPECT_EQ(1u, v->size());
406 EXPECT_EQ(expected, (*v->begin())->value());
407 expected++;
408 }
409 }
410
411 TEST(HeapCompactTest, CompactLinkedHashSetNested) {
412 using Inner = HeapLinkedHashSet<Member<IntWrapper>>;
413 using OrderedHashSet = HeapLinkedHashSet<Member<Inner>>;
414
415 Persistent<OrderedHashSet> set = new OrderedHashSet;
416 for (int i = 0; i < 13; ++i) {
417 IntWrapper* value = IntWrapper::create(i);
418 Inner* inner = new Inner;
419 inner->add(value);
420 set->add(inner);
421 }
422 EXPECT_EQ(13u, set->size());
423
424 int expected = 0;
425 for (const Inner* v : *set) {
426 EXPECT_EQ(1u, v->size());
427 EXPECT_EQ(expected, (*v->begin())->value());
428 expected++;
429 }
430
431 performHeapCompaction();
432
433 expected = 0;
434 for (const Inner* v : *set) {
435 EXPECT_EQ(1u, v->size());
436 EXPECT_EQ(expected, (*v->begin())->value());
437 expected++;
438 }
439 }
440
441 } // namespace blink
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698