OLD | NEW |
(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 |
OLD | NEW |