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