src/third_party/WebKit/Source/heap/HeapTest.cpp

   1 /*
   2  * Copyright (C) 2013 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Redistributions in binary form must reproduce the above
  11  * copyright notice, this list of conditions and the following disclaimer
  12  * in the documentation and/or other materials provided with the
  13  * distribution.
  14  *     * Neither the name of Google Inc. nor the names of its
  15  * contributors may be used to endorse or promote products derived from
  16  * this software without specific prior written permission.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29  */
  30
  31 #include "config.h"
  32
  33 #include "heap/Handle.h"
  34 #include "heap/Heap.h"
  35 #include "heap/HeapLinkedStack.h"
  36 #include "heap/HeapTerminatedArrayBuilder.h"
  37 #include "heap/ThreadState.h"
  38 #include "heap/Visitor.h"
  39
  40 #include "wtf/HashTraits.h"
  41
  42 #include <gtest/gtest.h>
  43
  44 namespace WebCore {
  45
  46 class ThreadMarker {
  47 public:
  48     ThreadMarker() : m_creatingThread(reinterpret_cast<ThreadState*>(0)), m_num(0) { }
  49     ThreadMarker(unsigned i) : m_creatingThread(ThreadState::current()), m_num(i) { }
  50     ThreadMarker(WTF::HashTableDeletedValueType deleted) : m_creatingThread(reinterpret_cast<ThreadState*>(-1)), m_num(0) { }
  51     ~ThreadMarker()
  52     {
  53         EXPECT_TRUE((m_creatingThread == ThreadState::current())
  54             || (m_creatingThread == reinterpret_cast<ThreadState*>(0))
  55             || (m_creatingThread == reinterpret_cast<ThreadState*>(-1)));
  56     }
  57     bool isHashTableDeletedValue() const { return m_creatingThread == reinterpret_cast<ThreadState*>(-1); }
  58     bool operator==(const ThreadMarker& other) const { return other.m_creatingThread == m_creatingThread && other.m_num == m_num; }
  59     ThreadState* m_creatingThread;
  60     unsigned m_num;
  61 };
  62
  63 struct ThreadMarkerHash {
  64     static unsigned hash(const ThreadMarker& key)
  65     {
  66         return static_cast<unsigned>(reinterpret_cast<uintptr_t>(key.m_creatingThread) + key.m_num);
  67     }
  68
  69     static bool equal(const ThreadMarker& a, const ThreadMarker& b)
  70     {
  71         return a == b;
  72     }
  73
  74     static const bool safeToCompareToEmptyOrDeleted = false;
  75 };
  76
  77 }
  78
  79 namespace WTF {
  80
  81 template<typename T> struct DefaultHash;
  82 template<> struct DefaultHash<WebCore::ThreadMarker> {
  83     typedef WebCore::ThreadMarkerHash Hash;
  84 };
  85
  86 // ThreadMarkerHash is the default hash for ThreadMarker
  87 template<> struct HashTraits<WebCore::ThreadMarker> : GenericHashTraits<WebCore::ThreadMarker> {
  88     static const bool emptyValueIsZero = true;
  89     static void constructDeletedValue(WebCore::ThreadMarker& slot) { new (NotNull, &slot) WebCore::ThreadMarker(HashTableDeletedValue); }
  90     static bool isDeletedValue(const WebCore::ThreadMarker& slot) { return slot.isHashTableDeletedValue(); }
  91 };
  92
  93 }
  94
  95 namespace WebCore {
  96
  97 class TestGCScope {
  98 public:
  99     explicit TestGCScope(ThreadState::StackState state)
 100         : m_state(ThreadState::current())
 101         , m_safePointScope(state)
 102     {
 103         m_state->checkThread();
 104         ASSERT(!m_state->isInGC());
 105         ThreadState::stopThreads();
 106         m_state->enterGC();
 107     }
 108
 109     ~TestGCScope()
 110     {
 111         m_state->leaveGC();
 112         ASSERT(!m_state->isInGC());
 113         ThreadState::resumeThreads();
 114     }
 115
 116 private:
 117     ThreadState* m_state;
 118     ThreadState::SafePointScope m_safePointScope;
 119 };
 120
 121 static void getHeapStats(HeapStats* stats)
 122 {
 123     TestGCScope scope(ThreadState::NoHeapPointersOnStack);
 124     Heap::getStats(stats);
 125 }
 126
 127 #define DEFINE_VISITOR_METHODS(Type)                                       \
 128     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
 129     {                                                                      \
 130         if (object)                                                        \
 131             m_count++;                                                     \
 132     }                                                                      \
 133     virtual bool isMarked(const Type*) OVERRIDE { return false; }
 134
 135 class CountingVisitor : public Visitor {
 136 public:
 137     CountingVisitor()
 138         : m_count(0)
 139     {
 140     }
 141
 142     virtual void mark(const void* object, TraceCallback) OVERRIDE
 143     {
 144         if (object)
 145             m_count++;
 146     }
 147
 148     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
 149     {
 150         ASSERT(header->payload());
 151         m_count++;
 152     }
 153
 154     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 155     {
 156         ASSERT(header->payload());
 157         m_count++;
 158     }
 159
 160     virtual void registerWeakMembers(const void*, const void*, WeakPointerCallback) OVERRIDE { }
 161     virtual void registerWeakCell(void**, WeakPointerCallback) OVERRIDE { }
 162     virtual bool isMarked(const void*) OVERRIDE { return false; }
 163
 164     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 165
 166     size_t count() { return m_count; }
 167     void reset() { m_count = 0; }
 168
 169 private:
 170     size_t m_count;
 171 };
 172
 173 class SimpleObject : public GarbageCollected<SimpleObject> {
 174 public:
 175     static SimpleObject* create() { return new SimpleObject(); }
 176     void trace(Visitor*) { }
 177     char getPayload(int i) { return payload[i]; }
 178 protected:
 179     SimpleObject() { }
 180     char payload[64];
 181 };
 182
 183 #undef DEFINE_VISITOR_METHODS
 184
 185 class HeapTestSuperClass : public GarbageCollectedFinalized<HeapTestSuperClass> {
 186 public:
 187     static HeapTestSuperClass* create()
 188     {
 189         return new HeapTestSuperClass();
 190     }
 191
 192     virtual ~HeapTestSuperClass()
 193     {
 194         ++s_destructorCalls;
 195     }
 196
 197     static int s_destructorCalls;
 198     void trace(Visitor*) { }
 199
 200 protected:
 201     HeapTestSuperClass() { }
 202 };
 203
 204 int HeapTestSuperClass::s_destructorCalls = 0;
 205
 206 class HeapTestOtherSuperClass {
 207 public:
 208     int payload;
 209 };
 210
 211 static const size_t classMagic = 0xABCDDBCA;
 212
 213 class HeapTestSubClass : public HeapTestOtherSuperClass, public HeapTestSuperClass {
 214 public:
 215     static HeapTestSubClass* create()
 216     {
 217         return new HeapTestSubClass();
 218     }
 219
 220     virtual ~HeapTestSubClass()
 221     {
 222         EXPECT_EQ(classMagic, m_magic);
 223         ++s_destructorCalls;
 224     }
 225
 226     static int s_destructorCalls;
 227
 228 private:
 229
 230     HeapTestSubClass() : m_magic(classMagic) { }
 231
 232     const size_t m_magic;
 233 };
 234
 235 int HeapTestSubClass::s_destructorCalls = 0;
 236
 237 class HeapAllocatedArray : public GarbageCollected<HeapAllocatedArray> {
 238 public:
 239     HeapAllocatedArray()
 240     {
 241         for (int i = 0; i < s_arraySize; ++i) {
 242             m_array[i] = i % 128;
 243         }
 244     }
 245
 246     int8_t at(size_t i) { return m_array[i]; }
 247     void trace(Visitor*) { }
 248 private:
 249     static const int s_arraySize = 1000;
 250     int8_t m_array[s_arraySize];
 251 };
 252
 253 // Do several GCs to make sure that later GCs don't free up old memory from
 254 // previously run tests in this process.
 255 static void clearOutOldGarbage(HeapStats* heapStats)
 256 {
 257     while (true) {
 258         getHeapStats(heapStats);
 259         size_t used = heapStats->totalObjectSpace();
 260         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 261         getHeapStats(heapStats);
 262         if (heapStats->totalObjectSpace() >= used)
 263             break;
 264     }
 265 }
 266
 267 class IntWrapper : public GarbageCollectedFinalized<IntWrapper> {
 268 public:
 269     static IntWrapper* create(int x)
 270     {
 271         return new IntWrapper(x);
 272     }
 273
 274     virtual ~IntWrapper()
 275     {
 276         ++s_destructorCalls;
 277     }
 278
 279     static int s_destructorCalls;
 280     static void trace(Visitor*) { }
 281
 282     int value() const { return m_x; }
 283
 284     bool operator==(const IntWrapper& other) const { return other.value() == value(); }
 285
 286     unsigned hash() { return IntHash<int>::hash(m_x); }
 287
 288 protected:
 289     IntWrapper(int x) : m_x(x) { }
 290
 291 private:
 292     IntWrapper();
 293     int m_x;
 294 };
 295
 296 USED_FROM_MULTIPLE_THREADS(IntWrapper);
 297
 298 int IntWrapper::s_destructorCalls = 0;
 299
 300 class ThreadedTesterBase {
 301 protected:
 302     static void test(ThreadedTesterBase* tester)
 303     {
 304         for (int i = 0; i < numberOfThreads; i++)
 305             createThread(&threadFunc, tester, "testing thread");
 306         while (tester->m_threadsToFinish) {
 307             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 308             yield();
 309         }
 310         delete tester;
 311     }
 312
 313     virtual void runThread() = 0;
 314
 315 protected:
 316     static const int numberOfThreads = 10;
 317     static const int gcPerThread = 5;
 318     static const int numberOfAllocations = 50;
 319
 320     ThreadedTesterBase() : m_gcCount(0), m_threadsToFinish(numberOfThreads)
 321     {
 322     }
 323
 324     virtual ~ThreadedTesterBase()
 325     {
 326     }
 327
 328     inline bool done() const { return m_gcCount >= numberOfThreads * gcPerThread; }
 329
 330     volatile int m_gcCount;
 331     volatile int m_threadsToFinish;
 332
 333 private:
 334     static void threadFunc(void* data)
 335     {
 336         reinterpret_cast<ThreadedTesterBase*>(data)->runThread();
 337     }
 338 };
 339
 340 class ThreadedHeapTester : public ThreadedTesterBase {
 341 public:
 342     static void test()
 343     {
 344         ThreadedTesterBase::test(new ThreadedHeapTester);
 345     }
 346
 347 protected:
 348     virtual void runThread() OVERRIDE
 349     {
 350         ThreadState::attach();
 351
 352         int gcCount = 0;
 353         while (!done()) {
 354             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 355             {
 356                 Persistent<IntWrapper> wrapper;
 357
 358                 typedef Persistent<IntWrapper, GlobalPersistents> GlobalIntWrapperPersistent;
 359                 OwnPtr<GlobalIntWrapperPersistent> globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 360
 361                 for (int i = 0; i < numberOfAllocations; i++) {
 362                     wrapper = IntWrapper::create(0x0bbac0de);
 363                     if (!(i % 10)) {
 364                         globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 365                         ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 366                     }
 367                     yield();
 368                 }
 369
 370                 if (gcCount < gcPerThread) {
 371                     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 372                     gcCount++;
 373                     atomicIncrement(&m_gcCount);
 374                 }
 375
 376                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 377                 EXPECT_EQ(wrapper->value(), 0x0bbac0de);
 378                 EXPECT_EQ((*globalPersistent)->value(), 0x0ed0cabb);
 379             }
 380             yield();
 381         }
 382         ThreadState::detach();
 383         atomicDecrement(&m_threadsToFinish);
 384     }
 385 };
 386
 387 class ThreadedWeaknessTester : public ThreadedTesterBase {
 388 public:
 389     static void test()
 390     {
 391         ThreadedTesterBase::test(new ThreadedWeaknessTester);
 392     }
 393
 394 private:
 395     virtual void runThread() OVERRIDE
 396     {
 397         ThreadState::attach();
 398
 399         int gcCount = 0;
 400         while (!done()) {
 401             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 402             {
 403                 Persistent<HeapHashMap<ThreadMarker, WeakMember<IntWrapper> > > weakMap = new HeapHashMap<ThreadMarker, WeakMember<IntWrapper> >;
 404                 PersistentHeapHashMap<ThreadMarker, WeakMember<IntWrapper> > weakMap2;
 405
 406                 for (int i = 0; i < numberOfAllocations; i++) {
 407                     weakMap->add(static_cast<unsigned>(i), IntWrapper::create(0));
 408                     weakMap2.add(static_cast<unsigned>(i), IntWrapper::create(0));
 409                     if (!(i % 10)) {
 410                         ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 411                     }
 412                     yield();
 413                 }
 414
 415                 if (gcCount < gcPerThread) {
 416                     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 417                     gcCount++;
 418                     atomicIncrement(&m_gcCount);
 419                 }
 420
 421                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 422                 EXPECT_TRUE(weakMap->isEmpty());
 423                 EXPECT_TRUE(weakMap2.isEmpty());
 424             }
 425             yield();
 426         }
 427         ThreadState::detach();
 428         atomicDecrement(&m_threadsToFinish);
 429     }
 430 };
 431
 432 // The accounting for memory includes the memory used by rounding up object
 433 // sizes. This is done in a different way on 32 bit and 64 bit, so we have to
 434 // have some slack in the tests.
 435 template<typename T>
 436 void CheckWithSlack(T expected, T actual, int slack)
 437 {
 438     EXPECT_LE(expected, actual);
 439     EXPECT_GE((intptr_t)expected + slack, (intptr_t)actual);
 440 }
 441
 442 class TraceCounter : public GarbageCollectedFinalized<TraceCounter> {
 443 public:
 444     static TraceCounter* create()
 445     {
 446         return new TraceCounter();
 447     }
 448
 449     void trace(Visitor*) { m_traceCount++; }
 450
 451     int traceCount() { return m_traceCount; }
 452
 453 private:
 454     TraceCounter()
 455         : m_traceCount(0)
 456     {
 457     }
 458
 459     int m_traceCount;
 460 };
 461
 462 class ClassWithMember : public GarbageCollected<ClassWithMember> {
 463 public:
 464     static ClassWithMember* create()
 465     {
 466         return new ClassWithMember();
 467     }
 468
 469     void trace(Visitor* visitor)
 470     {
 471         EXPECT_TRUE(visitor->isMarked(this));
 472         if (!traceCount())
 473             EXPECT_FALSE(visitor->isMarked(m_traceCounter));
 474         else
 475             EXPECT_TRUE(visitor->isMarked(m_traceCounter));
 476
 477         visitor->trace(m_traceCounter);
 478     }
 479
 480     int traceCount() { return m_traceCounter->traceCount(); }
 481
 482 private:
 483     ClassWithMember()
 484         : m_traceCounter(TraceCounter::create())
 485     { }
 486
 487     Member<TraceCounter> m_traceCounter;
 488 };
 489
 490 class SimpleFinalizedObject : public GarbageCollectedFinalized<SimpleFinalizedObject> {
 491 public:
 492     static SimpleFinalizedObject* create()
 493     {
 494         return new SimpleFinalizedObject();
 495     }
 496
 497     ~SimpleFinalizedObject()
 498     {
 499         ++s_destructorCalls;
 500     }
 501
 502     static int s_destructorCalls;
 503
 504     void trace(Visitor*) { }
 505
 506 private:
 507     SimpleFinalizedObject() { }
 508 };
 509
 510 int SimpleFinalizedObject::s_destructorCalls = 0;
 511
 512 class TestTypedHeapClass : public GarbageCollected<TestTypedHeapClass> {
 513 public:
 514     static TestTypedHeapClass* create()
 515     {
 516         return new TestTypedHeapClass();
 517     }
 518
 519     void trace(Visitor*) { }
 520
 521 private:
 522     TestTypedHeapClass() { }
 523 };
 524
 525 class Bar : public GarbageCollectedFinalized<Bar> {
 526 public:
 527     static Bar* create()
 528     {
 529         return new Bar();
 530     }
 531
 532     void finalizeGarbageCollectedObject()
 533     {
 534         EXPECT_TRUE(m_magic == magic);
 535         m_magic = 0;
 536         s_live--;
 537     }
 538     bool hasBeenFinalized() const { return !m_magic; }
 539
 540     virtual void trace(Visitor* visitor) { }
 541     static unsigned s_live;
 542
 543 protected:
 544     static const int magic = 1337;
 545     int m_magic;
 546
 547     Bar()
 548         : m_magic(magic)
 549     {
 550         s_live++;
 551     }
 552 };
 553
 554 unsigned Bar::s_live = 0;
 555
 556 class Baz : public GarbageCollected<Baz> {
 557 public:
 558     static Baz* create(Bar* bar)
 559     {
 560         return new Baz(bar);
 561     }
 562
 563     void trace(Visitor* visitor)
 564     {
 565         visitor->trace(m_bar);
 566     }
 567
 568     void clear() { m_bar.release(); }
 569
 570     // willFinalize is called by FinalizationObserver.
 571     void willFinalize()
 572     {
 573         EXPECT_TRUE(!m_bar->hasBeenFinalized());
 574     }
 575
 576 private:
 577     explicit Baz(Bar* bar)
 578         : m_bar(bar)
 579     {
 580     }
 581
 582     Member<Bar> m_bar;
 583 };
 584
 585 class Foo : public Bar {
 586 public:
 587     static Foo* create(Bar* bar)
 588     {
 589         return new Foo(bar);
 590     }
 591
 592     static Foo* create(Foo* foo)
 593     {
 594         return new Foo(foo);
 595     }
 596
 597     virtual void trace(Visitor* visitor) OVERRIDE
 598     {
 599         if (m_pointsToFoo)
 600             visitor->mark(static_cast<Foo*>(m_bar));
 601         else
 602             visitor->mark(m_bar);
 603     }
 604
 605 private:
 606     Foo(Bar* bar)
 607         : Bar()
 608         , m_bar(bar)
 609         , m_pointsToFoo(false)
 610     {
 611     }
 612
 613     Foo(Foo* foo)
 614         : Bar()
 615         , m_bar(foo)
 616         , m_pointsToFoo(true)
 617     {
 618     }
 619
 620     Bar* m_bar;
 621     bool m_pointsToFoo;
 622 };
 623
 624 class Bars : public Bar {
 625 public:
 626     static Bars* create()
 627     {
 628         return new Bars();
 629     }
 630
 631     virtual void trace(Visitor* visitor) OVERRIDE
 632     {
 633         for (unsigned i = 0; i < m_width; i++)
 634             visitor->trace(m_bars[i]);
 635     }
 636
 637     unsigned getWidth() const
 638     {
 639         return m_width;
 640     }
 641
 642     static const unsigned width = 7500;
 643 private:
 644     Bars() : m_width(0)
 645     {
 646         for (unsigned i = 0; i < width; i++) {
 647             m_bars[i] = Bar::create();
 648             m_width++;
 649         }
 650     }
 651
 652     unsigned m_width;
 653     Member<Bar> m_bars[width];
 654 };
 655
 656 class ConstructorAllocation : public GarbageCollected<ConstructorAllocation> {
 657 public:
 658     static ConstructorAllocation* create() { return new ConstructorAllocation(); }
 659
 660     void trace(Visitor* visitor) { visitor->trace(m_intWrapper); }
 661
 662 private:
 663     ConstructorAllocation()
 664     {
 665         m_intWrapper = IntWrapper::create(42);
 666     }
 667
 668     Member<IntWrapper> m_intWrapper;
 669 };
 670
 671 class LargeObject : public GarbageCollectedFinalized<LargeObject> {
 672 public:
 673     ~LargeObject()
 674     {
 675         s_destructorCalls++;
 676     }
 677     static LargeObject* create() { return new LargeObject(); }
 678     char get(size_t i) { return m_data[i]; }
 679     void set(size_t i, char c) { m_data[i] = c; }
 680     size_t length() { return s_length; }
 681     void trace(Visitor* visitor)
 682     {
 683         visitor->trace(m_intWrapper);
 684     }
 685     static int s_destructorCalls;
 686
 687 private:
 688     static const size_t s_length = 1024*1024;
 689     LargeObject()
 690     {
 691         m_intWrapper = IntWrapper::create(23);
 692     }
 693     Member<IntWrapper> m_intWrapper;
 694     char m_data[s_length];
 695 };
 696
 697 int LargeObject::s_destructorCalls = 0;
 698
 699 class RefCountedAndGarbageCollected : public RefCountedGarbageCollected<RefCountedAndGarbageCollected> {
 700 public:
 701     static PassRefPtr<RefCountedAndGarbageCollected> create()
 702     {
 703         return adoptRef(new RefCountedAndGarbageCollected());
 704     }
 705
 706     ~RefCountedAndGarbageCollected()
 707     {
 708         ++s_destructorCalls;
 709     }
 710
 711     void trace(Visitor*) { }
 712
 713     static int s_destructorCalls;
 714
 715 private:
 716     RefCountedAndGarbageCollected()
 717     {
 718     }
 719 };
 720
 721 int RefCountedAndGarbageCollected::s_destructorCalls = 0;
 722
 723 class RefCountedAndGarbageCollected2 : public HeapTestOtherSuperClass, public RefCountedGarbageCollected<RefCountedAndGarbageCollected2> {
 724 public:
 725     static RefCountedAndGarbageCollected2* create()
 726     {
 727         return adoptRefCountedGarbageCollected(new RefCountedAndGarbageCollected2());
 728     }
 729
 730     ~RefCountedAndGarbageCollected2()
 731     {
 732         ++s_destructorCalls;
 733     }
 734
 735     void trace(Visitor*) { }
 736
 737     static int s_destructorCalls;
 738
 739 private:
 740     RefCountedAndGarbageCollected2()
 741     {
 742     }
 743 };
 744
 745 int RefCountedAndGarbageCollected2::s_destructorCalls = 0;
 746
 747 #define DEFINE_VISITOR_METHODS(Type)                                       \
 748     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
 749     {                                                                      \
 750         mark(object);                                                      \
 751     }                                                                      \
 752
 753 class RefCountedGarbageCollectedVisitor : public CountingVisitor {
 754 public:
 755     RefCountedGarbageCollectedVisitor(int expected, void** objects)
 756         : m_count(0)
 757         , m_expectedCount(expected)
 758         , m_expectedObjects(objects)
 759     {
 760     }
 761
 762     void mark(const void* ptr) { markNoTrace(ptr); }
 763
 764     virtual void markNoTrace(const void* ptr)
 765     {
 766         if (!ptr)
 767             return;
 768         if (m_count < m_expectedCount)
 769             EXPECT_TRUE(expectedObject(ptr));
 770         else
 771             EXPECT_FALSE(expectedObject(ptr));
 772         m_count++;
 773     }
 774
 775     virtual void mark(const void* ptr, TraceCallback) OVERRIDE
 776     {
 777         mark(ptr);
 778     }
 779
 780     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
 781     {
 782         mark(header->payload());
 783     }
 784
 785     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 786     {
 787         mark(header->payload());
 788     }
 789
 790     bool validate() { return m_count >= m_expectedCount; }
 791     void reset() { m_count = 0; }
 792
 793     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 794
 795 private:
 796     bool expectedObject(const void* ptr)
 797     {
 798         for (int i = 0; i < m_expectedCount; i++) {
 799             if (m_expectedObjects[i] == ptr)
 800                 return true;
 801         }
 802         return false;
 803     }
 804
 805     int m_count;
 806     int m_expectedCount;
 807     void** m_expectedObjects;
 808 };
 809
 810 #undef DEFINE_VISITOR_METHODS
 811
 812 class Weak : public Bar {
 813 public:
 814     static Weak* create(Bar* strong, Bar* weak)
 815     {
 816         return new Weak(strong, weak);
 817     }
 818
 819     virtual void trace(Visitor* visitor) OVERRIDE
 820     {
 821         visitor->trace(m_strongBar);
 822         visitor->registerWeakMembers(this, zapWeakMembers);
 823     }
 824
 825     static void zapWeakMembers(Visitor* visitor, void* self)
 826     {
 827         reinterpret_cast<Weak*>(self)->zapWeakMembers(visitor);
 828     }
 829
 830     bool strongIsThere() { return !!m_strongBar; }
 831     bool weakIsThere() { return !!m_weakBar; }
 832
 833 private:
 834     Weak(Bar* strongBar, Bar* weakBar)
 835         : Bar()
 836         , m_strongBar(strongBar)
 837         , m_weakBar(weakBar)
 838     {
 839     }
 840
 841     void zapWeakMembers(Visitor* visitor)
 842     {
 843         if (m_weakBar && !visitor->isAlive(m_weakBar))
 844             m_weakBar = 0;
 845     }
 846
 847     Member<Bar> m_strongBar;
 848     Bar* m_weakBar;
 849 };
 850
 851 class WithWeakMember : public Bar {
 852 public:
 853     static WithWeakMember* create(Bar* strong, Bar* weak)
 854     {
 855         return new WithWeakMember(strong, weak);
 856     }
 857
 858     virtual void trace(Visitor* visitor) OVERRIDE
 859     {
 860         visitor->trace(m_strongBar);
 861         visitor->trace(m_weakBar);
 862     }
 863
 864     bool strongIsThere() { return !!m_strongBar; }
 865     bool weakIsThere() { return !!m_weakBar; }
 866
 867 private:
 868     WithWeakMember(Bar* strongBar, Bar* weakBar)
 869         : Bar()
 870         , m_strongBar(strongBar)
 871         , m_weakBar(weakBar)
 872     {
 873     }
 874
 875     Member<Bar> m_strongBar;
 876     WeakMember<Bar> m_weakBar;
 877 };
 878
 879 class Observable : public GarbageCollectedFinalized<Observable> {
 880 public:
 881     static Observable* create(Bar* bar) { return new Observable(bar);  }
 882     ~Observable() { m_wasDestructed = true; }
 883     void trace(Visitor* visitor) { visitor->trace(m_bar); }
 884
 885     // willFinalize is called by FinalizationObserver. willFinalize can touch
 886     // other on-heap objects.
 887     void willFinalize()
 888     {
 889         EXPECT_FALSE(m_wasDestructed);
 890         EXPECT_FALSE(m_bar->hasBeenFinalized());
 891     }
 892
 893 private:
 894     explicit Observable(Bar* bar)
 895         : m_bar(bar)
 896         , m_wasDestructed(false)
 897     {
 898     }
 899
 900     Member<Bar> m_bar;
 901     bool m_wasDestructed;
 902 };
 903
 904 template <typename T> class FinalizationObserver : public GarbageCollected<FinalizationObserver<T> > {
 905 public:
 906     static FinalizationObserver* create(T* data) { return new FinalizationObserver(data); }
 907     bool didCallWillFinalize() const { return m_didCallWillFinalize; }
 908
 909     void trace(Visitor* visitor)
 910     {
 911         visitor->registerWeakMembers(this, zapWeakMembers);
 912     }
 913
 914 private:
 915     FinalizationObserver(T* data)
 916         : m_data(data)
 917         , m_didCallWillFinalize(false)
 918     {
 919     }
 920
 921     static void zapWeakMembers(Visitor* visitor, void* self)
 922     {
 923         FinalizationObserver* o = reinterpret_cast<FinalizationObserver*>(self);
 924         if (o->m_data && !visitor->isAlive(o->m_data)) {
 925             o->m_data->willFinalize();
 926             o->m_data = nullptr;
 927             o->m_didCallWillFinalize = true;
 928         }
 929     }
 930
 931     WeakMember<T> m_data;
 932     bool m_didCallWillFinalize;
 933 };
 934
 935 class FinalizationObserverWithHashMap {
 936 public:
 937     typedef HeapHashMap<WeakMember<Observable>, OwnPtr<FinalizationObserverWithHashMap> > ObserverMap;
 938
 939     explicit FinalizationObserverWithHashMap(Observable& target) : m_target(target) { }
 940     ~FinalizationObserverWithHashMap()
 941     {
 942         m_target.willFinalize();
 943         s_didCallWillFinalize = true;
 944     }
 945
 946     static ObserverMap& observe(Observable& target)
 947     {
 948         ObserverMap& map = observers();
 949         ObserverMap::AddResult result = map.add(&target, nullptr);
 950         if (result.isNewEntry)
 951             result.storedValue->value = adoptPtr(new FinalizationObserverWithHashMap(target));
 952         else
 953             ASSERT(result.storedValue->value);
 954         return map;
 955     }
 956
 957     static bool s_didCallWillFinalize;
 958
 959 private:
 960     static ObserverMap& observers()
 961     {
 962         DEFINE_STATIC_LOCAL(Persistent<ObserverMap>, observerMap, ());
 963         if (!observerMap)
 964             observerMap = new ObserverMap();
 965         return *observerMap;
 966     }
 967
 968     Observable& m_target;
 969 };
 970
 971 bool FinalizationObserverWithHashMap::s_didCallWillFinalize = false;
 972
 973 class SuperClass;
 974
 975 class PointsBack : public RefCountedWillBeGarbageCollectedFinalized<PointsBack> {
 976 public:
 977     static PassRefPtrWillBeRawPtr<PointsBack> create()
 978     {
 979         return adoptRefWillBeNoop(new PointsBack());
 980     }
 981
 982     ~PointsBack()
 983     {
 984         --s_aliveCount;
 985     }
 986
 987     void setBackPointer(SuperClass* backPointer)
 988     {
 989         m_backPointer = backPointer;
 990     }
 991
 992     SuperClass* backPointer() const { return m_backPointer; }
 993
 994     void trace(Visitor* visitor)
 995     {
 996 #if ENABLE_OILPAN
 997         visitor->trace(m_backPointer);
 998 #endif
 999     }
1000
1001     static int s_aliveCount;
1002 private:
1003     PointsBack() : m_backPointer(nullptr)
1004     {
1005         ++s_aliveCount;
1006     }
1007
1008     RawPtrWillBeWeakMember<SuperClass> m_backPointer;
1009 };
1010
1011 int PointsBack::s_aliveCount = 0;
1012
1013 class SuperClass : public RefCountedWillBeGarbageCollectedFinalized<SuperClass> {
1014 public:
1015     static PassRefPtrWillBeRawPtr<SuperClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1016     {
1017         return adoptRefWillBeNoop(new SuperClass(pointsBack));
1018     }
1019
1020     virtual ~SuperClass()
1021     {
1022 #if !ENABLE_OILPAN
1023         m_pointsBack->setBackPointer(0);
1024 #endif
1025         --s_aliveCount;
1026     }
1027
1028     void doStuff(PassRefPtrWillBeRawPtr<SuperClass> targetPass, PointsBack* pointsBack, int superClassCount)
1029     {
1030         RefPtrWillBeRawPtr<SuperClass> target = targetPass;
1031         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1032         EXPECT_EQ(pointsBack, target->pointsBack());
1033         EXPECT_EQ(superClassCount, SuperClass::s_aliveCount);
1034     }
1035
1036     virtual void trace(Visitor* visitor)
1037     {
1038 #if ENABLE_OILPAN
1039         visitor->trace(m_pointsBack);
1040 #endif
1041     }
1042
1043     PointsBack* pointsBack() const { return m_pointsBack.get(); }
1044
1045     static int s_aliveCount;
1046 protected:
1047     explicit SuperClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1048         : m_pointsBack(pointsBack)
1049     {
1050         m_pointsBack->setBackPointer(this);
1051         ++s_aliveCount;
1052     }
1053
1054 private:
1055     RefPtrWillBeMember<PointsBack> m_pointsBack;
1056 };
1057
1058 int SuperClass::s_aliveCount = 0;
1059 class SubData : public NoBaseWillBeGarbageCollectedFinalized<SubData> {
1060 public:
1061     SubData() { ++s_aliveCount; }
1062     ~SubData() { --s_aliveCount; }
1063
1064     void trace(Visitor*) { }
1065
1066     static int s_aliveCount;
1067 };
1068
1069 int SubData::s_aliveCount = 0;
1070
1071 class SubClass : public SuperClass {
1072 public:
1073     static PassRefPtrWillBeRawPtr<SubClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1074     {
1075         return adoptRefWillBeNoop(new SubClass(pointsBack));
1076     }
1077
1078     virtual ~SubClass()
1079     {
1080         --s_aliveCount;
1081     }
1082
1083     virtual void trace(Visitor* visitor)
1084     {
1085 #if ENABLE_OILPAN
1086         SuperClass::trace(visitor);
1087         visitor->trace(m_data);
1088 #endif
1089     }
1090
1091     static int s_aliveCount;
1092 private:
1093     explicit SubClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1094         : SuperClass(pointsBack)
1095         , m_data(adoptPtrWillBeNoop(new SubData()))
1096     {
1097         ++s_aliveCount;
1098     }
1099
1100 private:
1101     OwnPtrWillBeMember<SubData> m_data;
1102 };
1103
1104 int SubClass::s_aliveCount = 0;
1105
1106 class TransitionRefCounted : public RefCountedWillBeRefCountedGarbageCollected<TransitionRefCounted> {
1107 public:
1108     static PassRefPtrWillBeRawPtr<TransitionRefCounted> create()
1109     {
1110         return adoptRefWillBeRefCountedGarbageCollected(new TransitionRefCounted());
1111     }
1112
1113     ~TransitionRefCounted()
1114     {
1115         --s_aliveCount;
1116     }
1117
1118     void trace(Visitor* visitor) { }
1119
1120     static int s_aliveCount;
1121
1122 private:
1123     TransitionRefCounted()
1124     {
1125         ++s_aliveCount;
1126     }
1127 };
1128
1129 int TransitionRefCounted::s_aliveCount = 0;
1130
1131 class Mixin : public GarbageCollectedMixin {
1132 public:
1133     virtual void trace(Visitor* visitor) { }
1134
1135     char getPayload(int i) { return m_padding[i]; }
1136
1137 protected:
1138     // This is to force ptr diff for SimpleObject, Mixin, and UseMixin.
1139     int m_padding[8];
1140 };
1141
1142 class UseMixin : public SimpleObject, public Mixin {
1143     USING_GARBAGE_COLLECTED_MIXIN(UseMixin)
1144 public:
1145     static UseMixin* create()
1146     {
1147         return new UseMixin();
1148     }
1149
1150     static int s_traceCount;
1151     virtual void trace(Visitor* visitor)
1152     {
1153         SimpleObject::trace(visitor);
1154         Mixin::trace(visitor);
1155         ++s_traceCount;
1156     }
1157
1158 private:
1159     UseMixin()
1160     {
1161         s_traceCount = 0;
1162     }
1163 };
1164
1165 int UseMixin::s_traceCount = 0;
1166
1167 class VectorObject {
1168     ALLOW_ONLY_INLINE_ALLOCATION();
1169 public:
1170     VectorObject()
1171     {
1172         m_value = SimpleFinalizedObject::create();
1173     }
1174
1175     void trace(Visitor* visitor)
1176     {
1177         visitor->trace(m_value);
1178     }
1179
1180 private:
1181     Member<SimpleFinalizedObject> m_value;
1182 };
1183
1184 class VectorObjectInheritedTrace : public VectorObject { };
1185
1186 class VectorObjectNoTrace {
1187     ALLOW_ONLY_INLINE_ALLOCATION();
1188 public:
1189     VectorObjectNoTrace()
1190     {
1191         m_value = SimpleFinalizedObject::create();
1192     }
1193
1194 private:
1195     Member<SimpleFinalizedObject> m_value;
1196 };
1197
1198 class TerminatedArrayItem {
1199     ALLOW_ONLY_INLINE_ALLOCATION();
1200 public:
1201     TerminatedArrayItem(IntWrapper* payload) : m_payload(payload), m_isLast(false) { }
1202
1203     void trace(Visitor* visitor) { visitor->trace(m_payload); }
1204
1205     bool isLastInArray() const { return m_isLast; }
1206     void setLastInArray(bool value) { m_isLast = value; }
1207
1208     IntWrapper* payload() const { return m_payload; }
1209
1210 private:
1211     Member<IntWrapper> m_payload;
1212     bool m_isLast;
1213 };
1214
1215 } // WebCore namespace
1216
1217 namespace WTF {
1218
1219 // We need the below vector trait specialization for the above HeapVectors to behave correctly wrt. memset, memcmp etc.
1220 template<> struct VectorTraits<WebCore::VectorObject> : public SimpleClassVectorTraits<WebCore::VectorObject> { };
1221 template<> struct VectorTraits<WebCore::VectorObjectInheritedTrace> : public SimpleClassVectorTraits<WebCore::VectorObjectInheritedTrace> { };
1222 template<> struct VectorTraits<WebCore::VectorObjectNoTrace> : public SimpleClassVectorTraits<WebCore::VectorObjectNoTrace> { };
1223
1224 } // WTF namespace
1225
1226 namespace WebCore {
1227
1228 class OneKiloByteObject : public GarbageCollectedFinalized<OneKiloByteObject> {
1229 public:
1230     ~OneKiloByteObject() { s_destructorCalls++; }
1231     char* data() { return m_data; }
1232     void trace(Visitor* visitor) { }
1233     static int s_destructorCalls;
1234
1235 private:
1236     static const size_t s_length = 1024;
1237     char m_data[s_length];
1238 };
1239
1240 int OneKiloByteObject::s_destructorCalls = 0;
1241
1242 class DynamicallySizedObject : public GarbageCollected<DynamicallySizedObject> {
1243 public:
1244     static DynamicallySizedObject* create(size_t size)
1245     {
1246         void* slot = Heap::allocate<DynamicallySizedObject>(size);
1247         return new (slot) DynamicallySizedObject();
1248     }
1249
1250     void* operator new(std::size_t, void* location)
1251     {
1252         return location;
1253     }
1254
1255     uint8_t get(int i)
1256     {
1257         return *(reinterpret_cast<uint8_t*>(this) + i);
1258     }
1259
1260     void trace(Visitor*) { }
1261
1262 private:
1263     DynamicallySizedObject() { }
1264 };
1265
1266 class FinalizationAllocator : public GarbageCollectedFinalized<FinalizationAllocator> {
1267 public:
1268     FinalizationAllocator(Persistent<IntWrapper>* wrapper)
1269         : m_wrapper(wrapper)
1270     {
1271     }
1272
1273     ~FinalizationAllocator()
1274     {
1275         for (int i = 0; i < 10; ++i)
1276             *m_wrapper = IntWrapper::create(42);
1277         for (int i = 0; i < 512; ++i)
1278             new OneKiloByteObject();
1279     }
1280
1281     void trace(Visitor*) { }
1282
1283 private:
1284     Persistent<IntWrapper>* m_wrapper;
1285 };
1286
1287 TEST(HeapTest, Transition)
1288 {
1289     {
1290         RefPtr<TransitionRefCounted> refCounted = TransitionRefCounted::create();
1291         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
1292         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1293         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
1294     }
1295     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1296     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
1297
1298     RefPtrWillBePersistent<PointsBack> pointsBack1 = PointsBack::create();
1299     RefPtrWillBePersistent<PointsBack> pointsBack2 = PointsBack::create();
1300     RefPtrWillBePersistent<SuperClass> superClass = SuperClass::create(pointsBack1);
1301     RefPtrWillBePersistent<SubClass> subClass = SubClass::create(pointsBack2);
1302     EXPECT_EQ(2, PointsBack::s_aliveCount);
1303     EXPECT_EQ(2, SuperClass::s_aliveCount);
1304     EXPECT_EQ(1, SubClass::s_aliveCount);
1305     EXPECT_EQ(1, SubData::s_aliveCount);
1306
1307     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1308     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
1309     EXPECT_EQ(2, PointsBack::s_aliveCount);
1310     EXPECT_EQ(2, SuperClass::s_aliveCount);
1311     EXPECT_EQ(1, SubClass::s_aliveCount);
1312     EXPECT_EQ(1, SubData::s_aliveCount);
1313
1314     superClass->doStuff(superClass.release(), pointsBack1.get(), 2);
1315     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1316     EXPECT_EQ(2, PointsBack::s_aliveCount);
1317     EXPECT_EQ(1, SuperClass::s_aliveCount);
1318     EXPECT_EQ(1, SubClass::s_aliveCount);
1319     EXPECT_EQ(1, SubData::s_aliveCount);
1320     EXPECT_EQ(0, pointsBack1->backPointer());
1321
1322     pointsBack1.release();
1323     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1324     EXPECT_EQ(1, PointsBack::s_aliveCount);
1325     EXPECT_EQ(1, SuperClass::s_aliveCount);
1326     EXPECT_EQ(1, SubClass::s_aliveCount);
1327     EXPECT_EQ(1, SubData::s_aliveCount);
1328
1329     subClass->doStuff(subClass.release(), pointsBack2.get(), 1);
1330     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1331     EXPECT_EQ(1, PointsBack::s_aliveCount);
1332     EXPECT_EQ(0, SuperClass::s_aliveCount);
1333     EXPECT_EQ(0, SubClass::s_aliveCount);
1334     EXPECT_EQ(0, SubData::s_aliveCount);
1335     EXPECT_EQ(0, pointsBack2->backPointer());
1336
1337     pointsBack2.release();
1338     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1339     EXPECT_EQ(0, PointsBack::s_aliveCount);
1340     EXPECT_EQ(0, SuperClass::s_aliveCount);
1341     EXPECT_EQ(0, SubClass::s_aliveCount);
1342     EXPECT_EQ(0, SubData::s_aliveCount);
1343
1344     EXPECT_TRUE(superClass == subClass);
1345 }
1346
1347 TEST(HeapTest, Threading)
1348 {
1349     ThreadedHeapTester::test();
1350 }
1351
1352 TEST(HeapTest, ThreadedWeakness)
1353 {
1354     ThreadedWeaknessTester::test();
1355 }
1356
1357 TEST(HeapTest, BasicFunctionality)
1358 {
1359     HeapStats heapStats;
1360     clearOutOldGarbage(&heapStats);
1361     {
1362         size_t slack = 0;
1363
1364         // When the test starts there may already have been leaked some memory
1365         // on the heap, so we establish a base line.
1366         size_t baseLevel = heapStats.totalObjectSpace();
1367         bool testPagesAllocated = !baseLevel;
1368         if (testPagesAllocated)
1369             EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1370
1371         // This allocates objects on the general heap which should add a page of memory.
1372         DynamicallySizedObject* alloc32 = DynamicallySizedObject::create(32);
1373         slack += 4;
1374         memset(alloc32, 40, 32);
1375         DynamicallySizedObject* alloc64 = DynamicallySizedObject::create(64);
1376         slack += 4;
1377         memset(alloc64, 27, 64);
1378
1379         size_t total = 96;
1380
1381         getHeapStats(&heapStats);
1382         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1383         if (testPagesAllocated)
1384             EXPECT_EQ(heapStats.totalAllocatedSpace(), blinkPageSize);
1385
1386         CheckWithSlack(alloc32 + 32 + sizeof(HeapObjectHeader), alloc64, slack);
1387
1388         EXPECT_EQ(alloc32->get(0), 40);
1389         EXPECT_EQ(alloc32->get(31), 40);
1390         EXPECT_EQ(alloc64->get(0), 27);
1391         EXPECT_EQ(alloc64->get(63), 27);
1392
1393         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1394
1395         EXPECT_EQ(alloc32->get(0), 40);
1396         EXPECT_EQ(alloc32->get(31), 40);
1397         EXPECT_EQ(alloc64->get(0), 27);
1398         EXPECT_EQ(alloc64->get(63), 27);
1399     }
1400
1401     clearOutOldGarbage(&heapStats);
1402     size_t total = 0;
1403     size_t slack = 0;
1404     size_t baseLevel = heapStats.totalObjectSpace();
1405     bool testPagesAllocated = !baseLevel;
1406     if (testPagesAllocated)
1407         EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1408
1409     size_t big = 1008;
1410     Persistent<DynamicallySizedObject> bigArea = DynamicallySizedObject::create(big);
1411     total += big;
1412     slack += 4;
1413
1414     size_t persistentCount = 0;
1415     const size_t numPersistents = 100000;
1416     Persistent<DynamicallySizedObject>* persistents[numPersistents];
1417
1418     for (int i = 0; i < 1000; i++) {
1419         size_t size = 128 + i * 8;
1420         total += size;
1421         persistents[persistentCount++] = new Persistent<DynamicallySizedObject>(DynamicallySizedObject::create(size));
1422         slack += 4;
1423         getHeapStats(&heapStats);
1424         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1425         if (testPagesAllocated)
1426             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1427     }
1428
1429     {
1430         DynamicallySizedObject* alloc32b(DynamicallySizedObject::create(32));
1431         slack += 4;
1432         memset(alloc32b, 40, 32);
1433         DynamicallySizedObject* alloc64b(DynamicallySizedObject::create(64));
1434         slack += 4;
1435         memset(alloc64b, 27, 64);
1436         EXPECT_TRUE(alloc32b != alloc64b);
1437
1438         total += 96;
1439         getHeapStats(&heapStats);
1440         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1441         if (testPagesAllocated)
1442             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1443     }
1444
1445     clearOutOldGarbage(&heapStats);
1446     total -= 96;
1447     slack -= 8;
1448     if (testPagesAllocated)
1449         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1450
1451     DynamicallySizedObject* bigAreaRaw = bigArea;
1452     // Clear the persistent, so that the big area will be garbage collected.
1453     bigArea.release();
1454     clearOutOldGarbage(&heapStats);
1455
1456     total -= big;
1457     slack -= 4;
1458     getHeapStats(&heapStats);
1459     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1460     if (testPagesAllocated)
1461         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1462
1463     // Endless loop unless we eventually get the memory back that we just freed.
1464     while (true) {
1465         Persistent<DynamicallySizedObject>* alloc = new Persistent<DynamicallySizedObject>(DynamicallySizedObject::create(big / 2));
1466         slack += 4;
1467         persistents[persistentCount++] = alloc;
1468         EXPECT_LT(persistentCount, numPersistents);
1469         total += big / 2;
1470         if (bigAreaRaw == alloc->get())
1471             break;
1472     }
1473
1474     getHeapStats(&heapStats);
1475     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1476     if (testPagesAllocated)
1477         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1478
1479     for (size_t i = 0; i < persistentCount; i++) {
1480         delete persistents[i];
1481         persistents[i] = 0;
1482     }
1483
1484     uint8_t* address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(0, 100));
1485     for (int i = 0; i < 100; i++)
1486         address[i] = i;
1487     address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(address, 100000));
1488     for (int i = 0; i < 100; i++)
1489         EXPECT_EQ(address[i], i);
1490     address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(address, 50));
1491     for (int i = 0; i < 50; i++)
1492         EXPECT_EQ(address[i], i);
1493     // This should be equivalent to free(address).
1494     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<DynamicallySizedObject>(address, 0)), 0ul);
1495     // This should be equivalent to malloc(0).
1496     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<DynamicallySizedObject>(0, 0)), 0ul);
1497 }
1498
1499 TEST(HeapTest, SimpleAllocation)
1500 {
1501     HeapStats initialHeapStats;
1502     clearOutOldGarbage(&initialHeapStats);
1503     EXPECT_EQ(0ul, initialHeapStats.totalObjectSpace());
1504
1505     // Allocate an object in the heap.
1506     HeapAllocatedArray* array = new HeapAllocatedArray();
1507     HeapStats statsAfterAllocation;
1508     getHeapStats(&statsAfterAllocation);
1509     EXPECT_TRUE(statsAfterAllocation.totalObjectSpace() >= sizeof(HeapAllocatedArray));
1510
1511     // Sanity check of the contents in the heap.
1512     EXPECT_EQ(0, array->at(0));
1513     EXPECT_EQ(42, array->at(42));
1514     EXPECT_EQ(0, array->at(128));
1515     EXPECT_EQ(999 % 128, array->at(999));
1516 }
1517
1518 TEST(HeapTest, SimplePersistent)
1519 {
1520     Persistent<TraceCounter> traceCounter = TraceCounter::create();
1521     EXPECT_EQ(0, traceCounter->traceCount());
1522
1523     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1524     EXPECT_EQ(1, traceCounter->traceCount());
1525
1526     Persistent<ClassWithMember> classWithMember = ClassWithMember::create();
1527     EXPECT_EQ(0, classWithMember->traceCount());
1528
1529     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1530     EXPECT_EQ(1, classWithMember->traceCount());
1531     EXPECT_EQ(2, traceCounter->traceCount());
1532 }
1533
1534 TEST(HeapTest, SimpleFinalization)
1535 {
1536     {
1537         Persistent<SimpleFinalizedObject> finalized = SimpleFinalizedObject::create();
1538         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1539         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1540         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1541     }
1542
1543     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1544     EXPECT_EQ(1, SimpleFinalizedObject::s_destructorCalls);
1545 }
1546
1547 TEST(HeapTest, Finalization)
1548 {
1549     {
1550         HeapTestSubClass* t1 = HeapTestSubClass::create();
1551         HeapTestSubClass* t2 = HeapTestSubClass::create();
1552         HeapTestSuperClass* t3 = HeapTestSuperClass::create();
1553         // FIXME(oilpan): Ignore unused variables.
1554         (void)t1;
1555         (void)t2;
1556         (void)t3;
1557     }
1558     // Nothing is marked so the GC should free everything and call
1559     // the finalizer on all three objects.
1560     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1561     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1562     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1563     // Destructors not called again when GCing again.
1564     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1565     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1566     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1567 }
1568
1569 TEST(HeapTest, TypedHeapSanity)
1570 {
1571     // We use TraceCounter for allocating an object on the general heap.
1572     Persistent<TraceCounter> generalHeapObject = TraceCounter::create();
1573     Persistent<TestTypedHeapClass> typedHeapObject = TestTypedHeapClass::create();
1574     EXPECT_NE(pageHeaderAddress(reinterpret_cast<Address>(generalHeapObject.get())),
1575         pageHeaderAddress(reinterpret_cast<Address>(typedHeapObject.get())));
1576 }
1577
1578 TEST(HeapTest, NoAllocation)
1579 {
1580     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1581     {
1582         // Disallow allocation
1583         NoAllocationScope<AnyThread> noAllocationScope;
1584         EXPECT_FALSE(ThreadState::current()->isAllocationAllowed());
1585     }
1586     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1587 }
1588
1589 TEST(HeapTest, Members)
1590 {
1591     Bar::s_live = 0;
1592     {
1593         Persistent<Baz> h1;
1594         Persistent<Baz> h2;
1595         {
1596             h1 = Baz::create(Bar::create());
1597             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1598             EXPECT_EQ(1u, Bar::s_live);
1599             h2 = Baz::create(Bar::create());
1600             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1601             EXPECT_EQ(2u, Bar::s_live);
1602         }
1603         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1604         EXPECT_EQ(2u, Bar::s_live);
1605         h1->clear();
1606         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1607         EXPECT_EQ(1u, Bar::s_live);
1608     }
1609     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1610     EXPECT_EQ(0u, Bar::s_live);
1611 }
1612
1613 TEST(HeapTest, MarkTest)
1614 {
1615     {
1616         Bar::s_live = 0;
1617         Persistent<Bar> bar = Bar::create();
1618         EXPECT_TRUE(ThreadState::current()->contains(bar));
1619         EXPECT_EQ(1u, Bar::s_live);
1620         {
1621             Foo* foo = Foo::create(bar);
1622             EXPECT_TRUE(ThreadState::current()->contains(foo));
1623             EXPECT_EQ(2u, Bar::s_live);
1624             EXPECT_TRUE(reinterpret_cast<Address>(foo) != reinterpret_cast<Address>(bar.get()));
1625             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1626             EXPECT_TRUE(foo != bar); // To make sure foo is kept alive.
1627             EXPECT_EQ(2u, Bar::s_live);
1628         }
1629         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1630         EXPECT_EQ(1u, Bar::s_live);
1631     }
1632     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1633     EXPECT_EQ(0u, Bar::s_live);
1634 }
1635
1636 TEST(HeapTest, DeepTest)
1637 {
1638     const unsigned depth = 100000;
1639     Bar::s_live = 0;
1640     {
1641         Bar* bar = Bar::create();
1642         EXPECT_TRUE(ThreadState::current()->contains(bar));
1643         Foo* foo = Foo::create(bar);
1644         EXPECT_TRUE(ThreadState::current()->contains(foo));
1645         EXPECT_EQ(2u, Bar::s_live);
1646         for (unsigned i = 0; i < depth; i++) {
1647             Foo* foo2 = Foo::create(foo);
1648             foo = foo2;
1649             EXPECT_TRUE(ThreadState::current()->contains(foo));
1650         }
1651         EXPECT_EQ(depth + 2, Bar::s_live);
1652         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1653         EXPECT_TRUE(foo != bar); // To make sure foo and bar are kept alive.
1654         EXPECT_EQ(depth + 2, Bar::s_live);
1655     }
1656     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1657     EXPECT_EQ(0u, Bar::s_live);
1658 }
1659
1660 TEST(HeapTest, WideTest)
1661 {
1662     Bar::s_live = 0;
1663     {
1664         Bars* bars = Bars::create();
1665         unsigned width = Bars::width;
1666         EXPECT_EQ(width + 1, Bar::s_live);
1667         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1668         EXPECT_EQ(width + 1, Bar::s_live);
1669         // Use bars here to make sure that it will be on the stack
1670         // for the conservative stack scan to find.
1671         EXPECT_EQ(width, bars->getWidth());
1672     }
1673     EXPECT_EQ(Bars::width + 1, Bar::s_live);
1674     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1675     EXPECT_EQ(0u, Bar::s_live);
1676 }
1677
1678 TEST(HeapTest, HashMapOfMembers)
1679 {
1680     HeapStats initialHeapSize;
1681     IntWrapper::s_destructorCalls = 0;
1682
1683     clearOutOldGarbage(&initialHeapSize);
1684     {
1685         typedef HeapHashMap<
1686             Member<IntWrapper>,
1687             Member<IntWrapper>,
1688             DefaultHash<Member<IntWrapper> >::Hash,
1689             HashTraits<Member<IntWrapper> >,
1690             HashTraits<Member<IntWrapper> > > HeapObjectIdentityMap;
1691
1692         Persistent<HeapObjectIdentityMap> map = new HeapObjectIdentityMap();
1693
1694         map->clear();
1695         HeapStats afterSetWasCreated;
1696         getHeapStats(&afterSetWasCreated);
1697         EXPECT_TRUE(afterSetWasCreated.totalObjectSpace() > initialHeapSize.totalObjectSpace());
1698
1699         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1700         HeapStats afterGC;
1701         getHeapStats(&afterGC);
1702         EXPECT_EQ(afterGC.totalObjectSpace(), afterSetWasCreated.totalObjectSpace());
1703
1704         // If the additions below cause garbage collections, these
1705         // pointers should be found by conservative stack scanning.
1706         IntWrapper* one(IntWrapper::create(1));
1707         IntWrapper* anotherOne(IntWrapper::create(1));
1708
1709         map->add(one, one);
1710
1711         HeapStats afterOneAdd;
1712         getHeapStats(&afterOneAdd);
1713         EXPECT_TRUE(afterOneAdd.totalObjectSpace() > afterGC.totalObjectSpace());
1714
1715         HeapObjectIdentityMap::iterator it(map->begin());
1716         HeapObjectIdentityMap::iterator it2(map->begin());
1717         ++it;
1718         ++it2;
1719
1720         map->add(anotherOne, one);
1721
1722         // The addition above can cause an allocation of a new
1723         // backing store. We therefore garbage collect before
1724         // taking the heap stats in order to get rid of the old
1725         // backing store. We make sure to not use conservative
1726         // stack scanning as that could find a pointer to the
1727         // old backing.
1728         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1729         HeapStats afterAddAndGC;
1730         getHeapStats(&afterAddAndGC);
1731         EXPECT_TRUE(afterAddAndGC.totalObjectSpace() >= afterOneAdd.totalObjectSpace());
1732
1733         EXPECT_EQ(map->size(), 2u); // Two different wrappings of '1' are distinct.
1734
1735         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1736         EXPECT_TRUE(map->contains(one));
1737         EXPECT_TRUE(map->contains(anotherOne));
1738
1739         IntWrapper* gotten(map->get(one));
1740         EXPECT_EQ(gotten->value(), one->value());
1741         EXPECT_EQ(gotten, one);
1742
1743         HeapStats afterGC2;
1744         getHeapStats(&afterGC2);
1745         EXPECT_EQ(afterGC2.totalObjectSpace(), afterAddAndGC.totalObjectSpace());
1746
1747         IntWrapper* dozen = 0;
1748
1749         for (int i = 1; i < 1000; i++) { // 999 iterations.
1750             IntWrapper* iWrapper(IntWrapper::create(i));
1751             IntWrapper* iSquared(IntWrapper::create(i * i));
1752             map->add(iWrapper, iSquared);
1753             if (i == 12)
1754                 dozen = iWrapper;
1755         }
1756         HeapStats afterAdding1000;
1757         getHeapStats(&afterAdding1000);
1758         EXPECT_TRUE(afterAdding1000.totalObjectSpace() > afterGC2.totalObjectSpace());
1759
1760         IntWrapper* gross(map->get(dozen));
1761         EXPECT_EQ(gross->value(), 144);
1762
1763         // This should clear out junk created by all the adds.
1764         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1765         HeapStats afterGC3;
1766         getHeapStats(&afterGC3);
1767         EXPECT_TRUE(afterGC3.totalObjectSpace() < afterAdding1000.totalObjectSpace());
1768     }
1769
1770     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1771     // The objects 'one', anotherOne, and the 999 other pairs.
1772     EXPECT_EQ(IntWrapper::s_destructorCalls, 2000);
1773     HeapStats afterGC4;
1774     getHeapStats(&afterGC4);
1775     EXPECT_EQ(afterGC4.totalObjectSpace(), initialHeapSize.totalObjectSpace());
1776 }
1777
1778 TEST(HeapTest, NestedAllocation)
1779 {
1780     HeapStats initialHeapSize;
1781     clearOutOldGarbage(&initialHeapSize);
1782     {
1783         Persistent<ConstructorAllocation> constructorAllocation = ConstructorAllocation::create();
1784     }
1785     HeapStats afterFree;
1786     clearOutOldGarbage(&afterFree);
1787     EXPECT_TRUE(initialHeapSize == afterFree);
1788 }
1789
1790 TEST(HeapTest, LargeObjects)
1791 {
1792     HeapStats initialHeapSize;
1793     clearOutOldGarbage(&initialHeapSize);
1794     IntWrapper::s_destructorCalls = 0;
1795     LargeObject::s_destructorCalls = 0;
1796     {
1797         int slack = 8; // LargeObject points to an IntWrapper that is also allocated.
1798         Persistent<LargeObject> object = LargeObject::create();
1799         HeapStats afterAllocation;
1800         clearOutOldGarbage(&afterAllocation);
1801         {
1802             object->set(0, 'a');
1803             EXPECT_EQ('a', object->get(0));
1804             object->set(object->length() - 1, 'b');
1805             EXPECT_EQ('b', object->get(object->length() - 1));
1806             size_t expectedObjectSpace = sizeof(LargeObject) + sizeof(IntWrapper);
1807             size_t actualObjectSpace =
1808                 afterAllocation.totalObjectSpace() - initialHeapSize.totalObjectSpace();
1809             CheckWithSlack(expectedObjectSpace, actualObjectSpace, slack);
1810             // There is probably space for the IntWrapper in a heap page without
1811             // allocating extra pages. However, the IntWrapper allocation might cause
1812             // the addition of a heap page.
1813             size_t largeObjectAllocationSize =
1814                 sizeof(LargeObject) + sizeof(LargeHeapObject<FinalizedHeapObjectHeader>) + sizeof(FinalizedHeapObjectHeader);
1815             size_t allocatedSpaceLowerBound =
1816                 initialHeapSize.totalAllocatedSpace() + largeObjectAllocationSize;
1817             size_t allocatedSpaceUpperBound = allocatedSpaceLowerBound + slack + blinkPageSize;
1818             EXPECT_LE(allocatedSpaceLowerBound, afterAllocation.totalAllocatedSpace());
1819             EXPECT_LE(afterAllocation.totalAllocatedSpace(), allocatedSpaceUpperBound);
1820             EXPECT_EQ(0, IntWrapper::s_destructorCalls);
1821             EXPECT_EQ(0, LargeObject::s_destructorCalls);
1822             for (int i = 0; i < 10; i++)
1823                 object = LargeObject::create();
1824         }
1825         HeapStats oneLargeObject;
1826         clearOutOldGarbage(&oneLargeObject);
1827         EXPECT_TRUE(oneLargeObject == afterAllocation);
1828         EXPECT_EQ(10, IntWrapper::s_destructorCalls);
1829         EXPECT_EQ(10, LargeObject::s_destructorCalls);
1830     }
1831     HeapStats backToInitial;
1832     clearOutOldGarbage(&backToInitial);
1833     EXPECT_TRUE(initialHeapSize == backToInitial);
1834     EXPECT_EQ(11, IntWrapper::s_destructorCalls);
1835     EXPECT_EQ(11, LargeObject::s_destructorCalls);
1836     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1837 }
1838
1839 typedef std::pair<Member<IntWrapper>, int> PairWrappedUnwrapped;
1840 typedef std::pair<int, Member<IntWrapper> > PairUnwrappedWrapped;
1841 typedef std::pair<WeakMember<IntWrapper>, Member<IntWrapper> > PairWeakStrong;
1842 typedef std::pair<Member<IntWrapper>, WeakMember<IntWrapper> > PairStrongWeak;
1843 typedef std::pair<WeakMember<IntWrapper>, int> PairWeakUnwrapped;
1844 typedef std::pair<int, WeakMember<IntWrapper> > PairUnwrappedWeak;
1845
1846 class Container : public GarbageCollected<Container> {
1847 public:
1848     static Container* create() { return new Container(); }
1849     HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > map;
1850     HeapHashSet<Member<IntWrapper> > set;
1851     HeapHashSet<Member<IntWrapper> > set2;
1852     HeapVector<Member<IntWrapper>, 2> vector;
1853     HeapVector<PairWrappedUnwrapped, 2> vectorWU;
1854     HeapVector<PairUnwrappedWrapped, 2> vectorUW;
1855     void trace(Visitor* visitor)
1856     {
1857         visitor->trace(map);
1858         visitor->trace(set);
1859         visitor->trace(set2);
1860         visitor->trace(vector);
1861     }
1862 };
1863
1864 struct ShouldBeTraced {
1865     explicit ShouldBeTraced(IntWrapper* wrapper) : m_wrapper(wrapper) { }
1866     void trace(Visitor* visitor) { visitor->trace(m_wrapper); }
1867     Member<IntWrapper> m_wrapper;
1868 };
1869
1870 class OffHeapContainer : public GarbageCollectedFinalized<OffHeapContainer> {
1871 public:
1872     static OffHeapContainer* create() { return new OffHeapContainer(); }
1873
1874     OffHeapContainer()
1875     {
1876         m_deque1.append(ShouldBeTraced(IntWrapper::create(1)));
1877         m_vector1.append(ShouldBeTraced(IntWrapper::create(2)));
1878         m_deque2.append(IntWrapper::create(3));
1879         m_vector2.append(IntWrapper::create(4));
1880         m_hashSet.add(IntWrapper::create(5));
1881         m_hashMap.add(this, IntWrapper::create(6));
1882         m_listHashSet.add(IntWrapper::create(7));
1883     }
1884
1885     void trace(Visitor* visitor)
1886     {
1887         visitor->trace(m_deque1);
1888         visitor->trace(m_vector1);
1889         visitor->trace(m_deque2);
1890         visitor->trace(m_vector2);
1891         visitor->trace(m_hashSet);
1892         visitor->trace(m_hashMap);
1893         visitor->trace(m_listHashSet);
1894     }
1895
1896     Deque<ShouldBeTraced> m_deque1;
1897     Vector<ShouldBeTraced> m_vector1;
1898     Deque<Member<IntWrapper> > m_deque2;
1899     Vector<Member<IntWrapper> > m_vector2;
1900     HashSet<Member<IntWrapper> > m_hashSet;
1901     HashMap<void*, Member<IntWrapper> > m_hashMap;
1902     ListHashSet<Member<IntWrapper> > m_listHashSet;
1903 };
1904
1905
1906 // These class definitions test compile-time asserts with transition
1907 // types. They are therefore unused in test code and just need to
1908 // compile. This is intentional; do not delete the A and B classes below.
1909 class A : public WillBeGarbageCollectedMixin {
1910 };
1911
1912 class B : public NoBaseWillBeGarbageCollected<B>, public A {
1913     WILL_BE_USING_GARBAGE_COLLECTED_MIXIN(B);
1914 public:
1915     void trace(Visitor*) { }
1916 };
1917
1918 TEST(HeapTest, HeapVectorFilledWithValue)
1919 {
1920     IntWrapper* val = IntWrapper::create(1);
1921     HeapVector<Member<IntWrapper> > vector(10, val);
1922     EXPECT_EQ(10u, vector.size());
1923     for (size_t i = 0; i < vector.size(); i++)
1924         EXPECT_EQ(val, vector[i]);
1925 }
1926
1927 TEST(HeapTest, HeapVectorWithInlineCapacity)
1928 {
1929     IntWrapper* one = IntWrapper::create(1);
1930     IntWrapper* two = IntWrapper::create(2);
1931     IntWrapper* three = IntWrapper::create(3);
1932     IntWrapper* four = IntWrapper::create(4);
1933     IntWrapper* five = IntWrapper::create(5);
1934     IntWrapper* six = IntWrapper::create(6);
1935     {
1936         HeapVector<Member<IntWrapper>, 2> vector;
1937         vector.append(one);
1938         vector.append(two);
1939         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1940         EXPECT_TRUE(vector.contains(one));
1941         EXPECT_TRUE(vector.contains(two));
1942
1943         vector.append(three);
1944         vector.append(four);
1945         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1946         EXPECT_TRUE(vector.contains(one));
1947         EXPECT_TRUE(vector.contains(two));
1948         EXPECT_TRUE(vector.contains(three));
1949         EXPECT_TRUE(vector.contains(four));
1950
1951         vector.shrink(1);
1952         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1953         EXPECT_TRUE(vector.contains(one));
1954         EXPECT_FALSE(vector.contains(two));
1955         EXPECT_FALSE(vector.contains(three));
1956         EXPECT_FALSE(vector.contains(four));
1957     }
1958     {
1959         HeapVector<Member<IntWrapper>, 2> vector1;
1960         HeapVector<Member<IntWrapper>, 2> vector2;
1961
1962         vector1.append(one);
1963         vector2.append(two);
1964         vector1.swap(vector2);
1965         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1966         EXPECT_TRUE(vector1.contains(two));
1967         EXPECT_TRUE(vector2.contains(one));
1968     }
1969     {
1970         HeapVector<Member<IntWrapper>, 2> vector1;
1971         HeapVector<Member<IntWrapper>, 2> vector2;
1972
1973         vector1.append(one);
1974         vector1.append(two);
1975         vector2.append(three);
1976         vector2.append(four);
1977         vector2.append(five);
1978         vector2.append(six);
1979         vector1.swap(vector2);
1980         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1981         EXPECT_TRUE(vector1.contains(three));
1982         EXPECT_TRUE(vector1.contains(four));
1983         EXPECT_TRUE(vector1.contains(five));
1984         EXPECT_TRUE(vector1.contains(six));
1985         EXPECT_TRUE(vector2.contains(one));
1986         EXPECT_TRUE(vector2.contains(two));
1987     }
1988 }
1989
1990 TEST(HeapTest, HeapCollectionTypes)
1991 {
1992     HeapStats initialHeapSize;
1993     IntWrapper::s_destructorCalls = 0;
1994
1995     typedef HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > MemberMember;
1996     typedef HeapHashMap<Member<IntWrapper>, int> MemberPrimitive;
1997     typedef HeapHashMap<int, Member<IntWrapper> > PrimitiveMember;
1998
1999     typedef HeapHashSet<Member<IntWrapper> > MemberSet;
2000     typedef HeapHashSet<WeakMember<IntWrapper> > WeakMemberSet;
2001
2002     typedef HeapVector<Member<IntWrapper>, 2> MemberVector;
2003
2004     typedef HeapVector<PairWrappedUnwrapped, 2> VectorWU;
2005     typedef HeapVector<PairUnwrappedWrapped, 2> VectorUW;
2006
2007     Persistent<MemberMember> memberMember = new MemberMember();
2008     Persistent<MemberMember> memberMember2 = new MemberMember();
2009     Persistent<MemberMember> memberMember3 = new MemberMember();
2010     Persistent<MemberPrimitive> memberPrimitive = new MemberPrimitive();
2011     Persistent<PrimitiveMember> primitiveMember = new PrimitiveMember();
2012     Persistent<MemberSet> set = new MemberSet();
2013     Persistent<MemberSet> set2 = new MemberSet();
2014     Persistent<MemberVector> vector = new MemberVector();
2015     Persistent<MemberVector> vector2 = new MemberVector();
2016     Persistent<VectorWU> vectorWU = new VectorWU();
2017     Persistent<VectorWU> vectorWU2 = new VectorWU();
2018     Persistent<VectorUW> vectorUW = new VectorUW();
2019     Persistent<VectorUW> vectorUW2 = new VectorUW();
2020     Persistent<Container> container = Container::create();
2021
2022     clearOutOldGarbage(&initialHeapSize);
2023     {
2024         Persistent<IntWrapper> one(IntWrapper::create(1));
2025         Persistent<IntWrapper> two(IntWrapper::create(2));
2026         Persistent<IntWrapper> oneB(IntWrapper::create(1));
2027         Persistent<IntWrapper> twoB(IntWrapper::create(2));
2028         Persistent<IntWrapper> oneC(IntWrapper::create(1));
2029         Persistent<IntWrapper> oneD(IntWrapper::create(1));
2030         {
2031             IntWrapper* three(IntWrapper::create(3));
2032             IntWrapper* four(IntWrapper::create(4));
2033             IntWrapper* threeB(IntWrapper::create(3));
2034             IntWrapper* fourB(IntWrapper::create(4));
2035             IntWrapper* threeC(IntWrapper::create(3));
2036             IntWrapper* fourC(IntWrapper::create(4));
2037             IntWrapper* fiveC(IntWrapper::create(5));
2038             IntWrapper* threeD(IntWrapper::create(3));
2039             IntWrapper* fourD(IntWrapper::create(4));
2040             IntWrapper* fiveD(IntWrapper::create(5));
2041
2042             // Member Collections.
2043             memberMember2->add(one, two);
2044             memberMember2->add(two, three);
2045             memberMember2->add(three, four);
2046             memberMember2->add(four, one);
2047             primitiveMember->add(1, two);
2048             primitiveMember->add(2, three);
2049             primitiveMember->add(3, four);
2050             primitiveMember->add(4, one);
2051             memberPrimitive->add(one, 2);
2052             memberPrimitive->add(two, 3);
2053             memberPrimitive->add(three, 4);
2054             memberPrimitive->add(four, 1);
2055             set2->add(one);
2056             set2->add(two);
2057             set2->add(three);
2058             set2->add(four);
2059             set->add(oneB);
2060             vector->append(oneB);
2061             vector2->append(threeB);
2062             vector2->append(fourB);
2063             vectorWU->append(PairWrappedUnwrapped(&*oneC, 42));
2064             vectorWU2->append(PairWrappedUnwrapped(&*threeC, 43));
2065             vectorWU2->append(PairWrappedUnwrapped(&*fourC, 44));
2066             vectorWU2->append(PairWrappedUnwrapped(&*fiveC, 45));
2067             vectorUW->append(PairUnwrappedWrapped(1, &*oneD));
2068             vectorUW2->append(PairUnwrappedWrapped(103, &*threeD));
2069             vectorUW2->append(PairUnwrappedWrapped(104, &*fourD));
2070             vectorUW2->append(PairUnwrappedWrapped(105, &*fiveD));
2071
2072             // Collect garbage. This should change nothing since we are keeping
2073             // alive the IntWrapper objects with on-stack pointers.
2074             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2075             EXPECT_EQ(0u, memberMember->size());
2076             EXPECT_EQ(4u, memberMember2->size());
2077             EXPECT_EQ(4u, primitiveMember->size());
2078             EXPECT_EQ(4u, memberPrimitive->size());
2079             EXPECT_EQ(1u, set->size());
2080             EXPECT_EQ(4u, set2->size());
2081             EXPECT_EQ(1u, vector->size());
2082             EXPECT_EQ(2u, vector2->size());
2083             EXPECT_EQ(1u, vectorWU->size());
2084             EXPECT_EQ(3u, vectorWU2->size());
2085             EXPECT_EQ(1u, vectorUW->size());
2086             EXPECT_EQ(3u, vectorUW2->size());
2087
2088             MemberVector& cvec = container->vector;
2089             cvec.swap(*vector.get());
2090             vector2->swap(cvec);
2091             vector->swap(cvec);
2092
2093             VectorWU& cvecWU = container->vectorWU;
2094             cvecWU.swap(*vectorWU.get());
2095             vectorWU2->swap(cvecWU);
2096             vectorWU->swap(cvecWU);
2097
2098             VectorUW& cvecUW = container->vectorUW;
2099             cvecUW.swap(*vectorUW.get());
2100             vectorUW2->swap(cvecUW);
2101             vectorUW->swap(cvecUW);
2102
2103             // Swap set and set2 in a roundabout way.
2104             MemberSet& cset1 = container->set;
2105             MemberSet& cset2 = container->set2;
2106             set->swap(cset1);
2107             set2->swap(cset2);
2108             set->swap(cset2);
2109             cset1.swap(cset2);
2110             cset2.swap(set2);
2111
2112             // Triple swap.
2113             container->map.swap(memberMember2);
2114             MemberMember& containedMap = container->map;
2115             memberMember3->swap(containedMap);
2116             memberMember3->swap(memberMember);
2117
2118             EXPECT_TRUE(memberMember->get(one) == two);
2119             EXPECT_TRUE(memberMember->get(two) == three);
2120             EXPECT_TRUE(memberMember->get(three) == four);
2121             EXPECT_TRUE(memberMember->get(four) == one);
2122             EXPECT_TRUE(primitiveMember->get(1) == two);
2123             EXPECT_TRUE(primitiveMember->get(2) == three);
2124             EXPECT_TRUE(primitiveMember->get(3) == four);
2125             EXPECT_TRUE(primitiveMember->get(4) == one);
2126             EXPECT_EQ(1, memberPrimitive->get(four));
2127             EXPECT_EQ(2, memberPrimitive->get(one));
2128             EXPECT_EQ(3, memberPrimitive->get(two));
2129             EXPECT_EQ(4, memberPrimitive->get(three));
2130             EXPECT_TRUE(set->contains(one));
2131             EXPECT_TRUE(set->contains(two));
2132             EXPECT_TRUE(set->contains(three));
2133             EXPECT_TRUE(set->contains(four));
2134             EXPECT_TRUE(set2->contains(oneB));
2135             EXPECT_TRUE(vector->contains(threeB));
2136             EXPECT_TRUE(vector->contains(fourB));
2137             EXPECT_TRUE(vector2->contains(oneB));
2138             EXPECT_FALSE(vector2->contains(threeB));
2139             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*threeC, 43)));
2140             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fourC, 44)));
2141             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fiveC, 45)));
2142             EXPECT_TRUE(vectorWU2->contains(PairWrappedUnwrapped(&*oneC, 42)));
2143             EXPECT_FALSE(vectorWU2->contains(PairWrappedUnwrapped(&*threeC, 43)));
2144             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(103, &*threeD)));
2145             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(104, &*fourD)));
2146             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(105, &*fiveD)));
2147             EXPECT_TRUE(vectorUW2->contains(PairUnwrappedWrapped(1, &*oneD)));
2148             EXPECT_FALSE(vectorUW2->contains(PairUnwrappedWrapped(103, &*threeD)));
2149         }
2150
2151         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2152
2153         EXPECT_EQ(4u, memberMember->size());
2154         EXPECT_EQ(0u, memberMember2->size());
2155         EXPECT_EQ(4u, primitiveMember->size());
2156         EXPECT_EQ(4u, memberPrimitive->size());
2157         EXPECT_EQ(4u, set->size());
2158         EXPECT_EQ(1u, set2->size());
2159         EXPECT_EQ(2u, vector->size());
2160         EXPECT_EQ(1u, vector2->size());
2161         EXPECT_EQ(3u, vectorUW->size());
2162         EXPECT_EQ(1u, vector2->size());
2163
2164         EXPECT_TRUE(memberMember->get(one) == two);
2165         EXPECT_TRUE(primitiveMember->get(1) == two);
2166         EXPECT_TRUE(primitiveMember->get(4) == one);
2167         EXPECT_EQ(2, memberPrimitive->get(one));
2168         EXPECT_EQ(3, memberPrimitive->get(two));
2169         EXPECT_TRUE(set->contains(one));
2170         EXPECT_TRUE(set->contains(two));
2171         EXPECT_FALSE(set->contains(oneB));
2172         EXPECT_TRUE(set2->contains(oneB));
2173         EXPECT_EQ(3, vector->at(0)->value());
2174         EXPECT_EQ(4, vector->at(1)->value());
2175     }
2176
2177     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2178     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2179
2180     EXPECT_EQ(4u, memberMember->size());
2181     EXPECT_EQ(4u, primitiveMember->size());
2182     EXPECT_EQ(4u, memberPrimitive->size());
2183     EXPECT_EQ(4u, set->size());
2184     EXPECT_EQ(1u, set2->size());
2185     EXPECT_EQ(2u, vector->size());
2186     EXPECT_EQ(1u, vector2->size());
2187     EXPECT_EQ(3u, vectorWU->size());
2188     EXPECT_EQ(1u, vectorWU2->size());
2189     EXPECT_EQ(3u, vectorUW->size());
2190     EXPECT_EQ(1u, vectorUW2->size());
2191 }
2192
2193 template<typename T>
2194 void MapIteratorCheck(T& it, const T& end, int expected)
2195 {
2196     int found = 0;
2197     while (it != end) {
2198         found++;
2199         int key = it->key->value();
2200         int value = it->value->value();
2201         EXPECT_TRUE(key >= 0 && key < 1100);
2202         EXPECT_TRUE(value >= 0 && value < 1100);
2203         ++it;
2204     }
2205     EXPECT_EQ(expected, found);
2206 }
2207
2208 template<typename T>
2209 void SetIteratorCheck(T& it, const T& end, int expected)
2210 {
2211     int found = 0;
2212     while (it != end) {
2213         found++;
2214         int value = (*it)->value();
2215         EXPECT_TRUE(value >= 0 && value < 1100);
2216         ++it;
2217     }
2218     EXPECT_EQ(expected, found);
2219 }
2220
2221 TEST(HeapTest, HeapWeakCollectionSimple)
2222 {
2223
2224     IntWrapper::s_destructorCalls = 0;
2225
2226     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2227
2228     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
2229     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
2230     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
2231     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
2232
2233     Persistent<WeakStrong> weakStrong = new WeakStrong();
2234     Persistent<StrongWeak> strongWeak = new StrongWeak();
2235     Persistent<WeakWeak> weakWeak = new WeakWeak();
2236     Persistent<WeakSet> weakSet = new WeakSet();
2237
2238     Persistent<IntWrapper> two = IntWrapper::create(2);
2239
2240     keepNumbersAlive.append(IntWrapper::create(103));
2241     keepNumbersAlive.append(IntWrapper::create(10));
2242
2243     {
2244         weakStrong->add(IntWrapper::create(1), two);
2245         strongWeak->add(two, IntWrapper::create(1));
2246         weakWeak->add(two, IntWrapper::create(42));
2247         weakWeak->add(IntWrapper::create(42), two);
2248         weakSet->add(IntWrapper::create(0));
2249         weakSet->add(two);
2250         weakSet->add(keepNumbersAlive[0]);
2251         weakSet->add(keepNumbersAlive[1]);
2252         EXPECT_EQ(1u, weakStrong->size());
2253         EXPECT_EQ(1u, strongWeak->size());
2254         EXPECT_EQ(2u, weakWeak->size());
2255         EXPECT_EQ(4u, weakSet->size());
2256     }
2257
2258     keepNumbersAlive[0] = nullptr;
2259
2260     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2261
2262     EXPECT_EQ(0u, weakStrong->size());
2263     EXPECT_EQ(0u, strongWeak->size());
2264     EXPECT_EQ(0u, weakWeak->size());
2265     EXPECT_EQ(2u, weakSet->size());
2266 }
2267
2268 typedef HeapHashSet<PairWeakStrong> WeakStrongSet;
2269 typedef HeapHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2270 typedef HeapHashSet<PairStrongWeak> StrongWeakSet;
2271 typedef HeapHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2272
2273 void checkPairSets(
2274     Persistent<WeakStrongSet>& weakStrong,
2275     Persistent<StrongWeakSet>& strongWeak,
2276     Persistent<WeakUnwrappedSet>& weakUnwrapped,
2277     Persistent<UnwrappedWeakSet>& unwrappedWeak,
2278     bool ones,
2279     Persistent<IntWrapper>& two)
2280 {
2281     WeakStrongSet::iterator itWS = weakStrong->begin();
2282     StrongWeakSet::iterator itSW = strongWeak->begin();
2283     WeakUnwrappedSet::iterator itWU = weakUnwrapped->begin();
2284     UnwrappedWeakSet::iterator itUW = unwrappedWeak->begin();
2285
2286     EXPECT_EQ(2u, weakStrong->size());
2287     EXPECT_EQ(2u, strongWeak->size());
2288     EXPECT_EQ(2u, weakUnwrapped->size());
2289     EXPECT_EQ(2u, unwrappedWeak->size());
2290
2291     PairWeakStrong p = *itWS;
2292     PairStrongWeak p2 = *itSW;
2293     PairWeakUnwrapped p3 = *itWU;
2294     PairUnwrappedWeak p4 = *itUW;
2295     if (p.first == two && p.second == two)
2296         ++itWS;
2297     if (p2.first == two && p2.second == two)
2298         ++itSW;
2299     if (p3.first == two && p3.second == 2)
2300         ++itWU;
2301     if (p4.first == 2 && p4.second == two)
2302         ++itUW;
2303     p = *itWS;
2304     p2 = *itSW;
2305     p3 = *itWU;
2306     p4 = *itUW;
2307     IntWrapper* nullWrapper = 0;
2308     if (ones) {
2309         EXPECT_EQ(p.first->value(), 1);
2310         EXPECT_EQ(p2.second->value(), 1);
2311         EXPECT_EQ(p3.first->value(), 1);
2312         EXPECT_EQ(p4.second->value(), 1);
2313     } else {
2314         EXPECT_EQ(p.first, nullWrapper);
2315         EXPECT_EQ(p2.second, nullWrapper);
2316         EXPECT_EQ(p3.first, nullWrapper);
2317         EXPECT_EQ(p4.second, nullWrapper);
2318     }
2319
2320     EXPECT_EQ(p.second->value(), 2);
2321     EXPECT_EQ(p2.first->value(), 2);
2322     EXPECT_EQ(p3.second, 2);
2323     EXPECT_EQ(p4.first, 2);
2324
2325     EXPECT_TRUE(weakStrong->contains(PairWeakStrong(&*two, &*two)));
2326     EXPECT_TRUE(strongWeak->contains(PairStrongWeak(&*two, &*two)));
2327     EXPECT_TRUE(weakUnwrapped->contains(PairWeakUnwrapped(&*two, 2)));
2328     EXPECT_TRUE(unwrappedWeak->contains(PairUnwrappedWeak(2, &*two)));
2329 }
2330
2331 TEST(HeapTest, HeapWeakPairs)
2332 {
2333     IntWrapper::s_destructorCalls = 0;
2334
2335     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2336
2337     Persistent<WeakStrongSet> weakStrong = new WeakStrongSet();
2338     Persistent<StrongWeakSet> strongWeak = new StrongWeakSet();
2339     Persistent<WeakUnwrappedSet> weakUnwrapped = new WeakUnwrappedSet();
2340     Persistent<UnwrappedWeakSet> unwrappedWeak = new UnwrappedWeakSet();
2341
2342     Persistent<IntWrapper> two = IntWrapper::create(2);
2343
2344     weakStrong->add(PairWeakStrong(IntWrapper::create(1), &*two));
2345     weakStrong->add(PairWeakStrong(&*two, &*two));
2346     strongWeak->add(PairStrongWeak(&*two, IntWrapper::create(1)));
2347     strongWeak->add(PairStrongWeak(&*two, &*two));
2348     weakUnwrapped->add(PairWeakUnwrapped(IntWrapper::create(1), 2));
2349     weakUnwrapped->add(PairWeakUnwrapped(&*two, 2));
2350     unwrappedWeak->add(PairUnwrappedWeak(2, IntWrapper::create(1)));
2351     unwrappedWeak->add(PairUnwrappedWeak(2, &*two));
2352
2353     checkPairSets(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, true, two);
2354
2355     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2356     checkPairSets(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, false, two);
2357 }
2358
2359 TEST(HeapTest, HeapWeakCollectionTypes)
2360 {
2361     HeapStats initialHeapSize;
2362     IntWrapper::s_destructorCalls = 0;
2363
2364     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
2365     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
2366     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
2367     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
2368
2369     clearOutOldGarbage(&initialHeapSize);
2370
2371     const int weakStrongIndex = 0;
2372     const int strongWeakIndex = 1;
2373     const int weakWeakIndex = 2;
2374     const int numberOfMapIndices = 3;
2375     const int weakSetIndex = 3;
2376     const int numberOfCollections = 4;
2377
2378     for (int testRun = 0; testRun < 4; testRun++) {
2379         for (int collectionNumber = 0; collectionNumber < numberOfCollections; collectionNumber++) {
2380             bool testThatIteratorsMakeStrong = (testRun == weakSetIndex);
2381             bool deleteAfterwards = (testRun == 1);
2382             bool addAfterwards = (testRun == weakWeakIndex);
2383
2384             // The test doesn't work for strongWeak with deleting because we lost
2385             // the key from the keepNumbersAlive array, so we can't do the lookup.
2386             if (deleteAfterwards && collectionNumber == strongWeakIndex)
2387                 continue;
2388
2389             unsigned added = addAfterwards ? 100 : 0;
2390
2391             Persistent<WeakStrong> weakStrong = new WeakStrong();
2392             Persistent<StrongWeak> strongWeak = new StrongWeak();
2393             Persistent<WeakWeak> weakWeak = new WeakWeak();
2394
2395             Persistent<WeakSet> weakSet = new WeakSet();
2396
2397             PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2398             for (int i = 0; i < 128; i += 2) {
2399                 IntWrapper* wrapped = IntWrapper::create(i);
2400                 IntWrapper* wrapped2 = IntWrapper::create(i + 1);
2401                 keepNumbersAlive.append(wrapped);
2402                 keepNumbersAlive.append(wrapped2);
2403                 weakStrong->add(wrapped, wrapped2);
2404                 strongWeak->add(wrapped2, wrapped);
2405                 weakWeak->add(wrapped, wrapped2);
2406                 weakSet->add(wrapped);
2407             }
2408
2409             EXPECT_EQ(64u, weakStrong->size());
2410             EXPECT_EQ(64u, strongWeak->size());
2411             EXPECT_EQ(64u, weakWeak->size());
2412             EXPECT_EQ(64u, weakSet->size());
2413
2414             // Collect garbage. This should change nothing since we are keeping
2415             // alive the IntWrapper objects.
2416             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2417
2418             EXPECT_EQ(64u, weakStrong->size());
2419             EXPECT_EQ(64u, strongWeak->size());
2420             EXPECT_EQ(64u, weakWeak->size());
2421             EXPECT_EQ(64u, weakSet->size());
2422
2423             for (int i = 0; i < 128; i += 2) {
2424                 IntWrapper* wrapped = keepNumbersAlive[i];
2425                 IntWrapper* wrapped2 = keepNumbersAlive[i + 1];
2426                 EXPECT_EQ(wrapped2, weakStrong->get(wrapped));
2427                 EXPECT_EQ(wrapped, strongWeak->get(wrapped2));
2428                 EXPECT_EQ(wrapped2, weakWeak->get(wrapped));
2429                 EXPECT_TRUE(weakSet->contains(wrapped));
2430             }
2431
2432             for (int i = 0; i < 128; i += 3)
2433                 keepNumbersAlive[i] = nullptr;
2434
2435             if (collectionNumber != weakStrongIndex)
2436                 weakStrong->clear();
2437             if (collectionNumber != strongWeakIndex)
2438                 strongWeak->clear();
2439             if (collectionNumber != weakWeakIndex)
2440                 weakWeak->clear();
2441             if (collectionNumber != weakSetIndex)
2442                 weakSet->clear();
2443
2444             if (testThatIteratorsMakeStrong) {
2445                 WeakStrong::iterator it1 = weakStrong->begin();
2446                 StrongWeak::iterator it2 = strongWeak->begin();
2447                 WeakWeak::iterator it3 = weakWeak->begin();
2448                 WeakSet::iterator it4 = weakSet->begin();
2449                 // Collect garbage. This should change nothing since the
2450                 // iterators make the collections strong.
2451                 Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2452                 if (collectionNumber == weakStrongIndex) {
2453                     EXPECT_EQ(64u, weakStrong->size());
2454                     MapIteratorCheck(it1, weakStrong->end(), 64);
2455                 } else if (collectionNumber == strongWeakIndex) {
2456                     EXPECT_EQ(64u, strongWeak->size());
2457                     MapIteratorCheck(it2, strongWeak->end(), 64);
2458                 } else if (collectionNumber == weakWeakIndex) {
2459                     EXPECT_EQ(64u, weakWeak->size());
2460                     MapIteratorCheck(it3, weakWeak->end(), 64);
2461                 } else if (collectionNumber == weakSetIndex) {
2462                     EXPECT_EQ(64u, weakSet->size());
2463                     SetIteratorCheck(it4, weakSet->end(), 64);
2464                 }
2465             } else {
2466                 // Collect garbage. This causes weak processing to remove
2467                 // things from the collections.
2468                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2469                 unsigned count = 0;
2470                 for (int i = 0; i < 128; i += 2) {
2471                     bool firstAlive = keepNumbersAlive[i];
2472                     bool secondAlive = keepNumbersAlive[i + 1];
2473                     if (firstAlive && (collectionNumber == weakStrongIndex || collectionNumber == strongWeakIndex))
2474                         secondAlive = true;
2475                     if (firstAlive && secondAlive && collectionNumber < numberOfMapIndices) {
2476                         if (collectionNumber == weakStrongIndex) {
2477                             if (deleteAfterwards)
2478                                 EXPECT_EQ(i + 1, weakStrong->take(keepNumbersAlive[i])->value());
2479                         } else if (collectionNumber == strongWeakIndex) {
2480                             if (deleteAfterwards)
2481                                 EXPECT_EQ(i, strongWeak->take(keepNumbersAlive[i + 1])->value());
2482                         } else if (collectionNumber == weakWeakIndex) {
2483                             if (deleteAfterwards)
2484                                 EXPECT_EQ(i + 1, weakWeak->take(keepNumbersAlive[i])->value());
2485                         }
2486                         if (!deleteAfterwards)
2487                             count++;
2488                     } else if (collectionNumber == weakSetIndex && firstAlive) {
2489                         ASSERT_TRUE(weakSet->contains(keepNumbersAlive[i]));
2490                         if (deleteAfterwards)
2491                             weakSet->remove(keepNumbersAlive[i]);
2492                         else
2493                             count++;
2494                     }
2495                 }
2496                 if (addAfterwards) {
2497                     for (int i = 1000; i < 1100; i++) {
2498                         IntWrapper* wrapped = IntWrapper::create(i);
2499                         keepNumbersAlive.append(wrapped);
2500                         weakStrong->add(wrapped, wrapped);
2501                         strongWeak->add(wrapped, wrapped);
2502                         weakWeak->add(wrapped, wrapped);
2503                         weakSet->add(wrapped);
2504                     }
2505                 }
2506                 if (collectionNumber == weakStrongIndex)
2507                     EXPECT_EQ(count + added, weakStrong->size());
2508                 else if (collectionNumber == strongWeakIndex)
2509                     EXPECT_EQ(count + added, strongWeak->size());
2510                 else if (collectionNumber == weakWeakIndex)
2511                     EXPECT_EQ(count + added, weakWeak->size());
2512                 else if (collectionNumber == weakSetIndex)
2513                     EXPECT_EQ(count + added, weakSet->size());
2514                 WeakStrong::iterator it1 = weakStrong->begin();
2515                 StrongWeak::iterator it2 = strongWeak->begin();
2516                 WeakWeak::iterator it3 = weakWeak->begin();
2517                 WeakSet::iterator it4 = weakSet->begin();
2518                 MapIteratorCheck(it1, weakStrong->end(), (collectionNumber == weakStrongIndex ? count : 0) + added);
2519                 MapIteratorCheck(it2, strongWeak->end(), (collectionNumber == strongWeakIndex ? count : 0) + added);
2520                 MapIteratorCheck(it3, weakWeak->end(), (collectionNumber == weakWeakIndex ? count : 0) + added);
2521                 SetIteratorCheck(it4, weakSet->end(), (collectionNumber == weakSetIndex ? count : 0) + added);
2522             }
2523             for (unsigned i = 0; i < 128 + added; i++)
2524                 keepNumbersAlive[i] = nullptr;
2525             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2526             EXPECT_EQ(added, weakStrong->size());
2527             EXPECT_EQ(added, strongWeak->size());
2528             EXPECT_EQ(added, weakWeak->size());
2529             EXPECT_EQ(added, weakSet->size());
2530         }
2531     }
2532 }
2533
2534 TEST(HeapTest, RefCountedGarbageCollected)
2535 {
2536     RefCountedAndGarbageCollected::s_destructorCalls = 0;
2537     {
2538         RefPtr<RefCountedAndGarbageCollected> refPtr3;
2539         {
2540             Persistent<RefCountedAndGarbageCollected> persistent;
2541             {
2542                 RefPtr<RefCountedAndGarbageCollected> refPtr1 = RefCountedAndGarbageCollected::create();
2543                 RefPtr<RefCountedAndGarbageCollected> refPtr2 = RefCountedAndGarbageCollected::create();
2544                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2545                 EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2546                 persistent = refPtr1.get();
2547             }
2548             // Reference count is zero for both objects but one of
2549             // them is kept alive by a persistent handle.
2550             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2551             EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
2552             refPtr3 = persistent;
2553         }
2554         // The persistent handle is gone but the ref count has been
2555         // increased to 1.
2556         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2557         EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
2558     }
2559     // Both persistent handle is gone and ref count is zero so the
2560     // object can be collected.
2561     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2562     EXPECT_EQ(2, RefCountedAndGarbageCollected::s_destructorCalls);
2563 }
2564
2565 TEST(HeapTest, RefCountedGarbageCollectedWithStackPointers)
2566 {
2567     RefCountedAndGarbageCollected::s_destructorCalls = 0;
2568     RefCountedAndGarbageCollected2::s_destructorCalls = 0;
2569     {
2570         RefCountedAndGarbageCollected* pointer1 = 0;
2571         RefCountedAndGarbageCollected2* pointer2 = 0;
2572         {
2573             RefPtr<RefCountedAndGarbageCollected> object1 = RefCountedAndGarbageCollected::create();
2574             RefPtr<RefCountedAndGarbageCollected2> object2 = RefCountedAndGarbageCollected2::create();
2575             pointer1 = object1.get();
2576             pointer2 = object2.get();
2577             void* objects[2] = { object1.get(), object2.get() };
2578             RefCountedGarbageCollectedVisitor visitor(2, objects);
2579             ThreadState::current()->visitPersistents(&visitor);
2580             EXPECT_TRUE(visitor.validate());
2581
2582             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2583             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2584             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2585         }
2586         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2587         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2588         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2589
2590         // At this point, the reference counts of object1 and object2 are 0.
2591         // Only pointer1 and pointer2 keep references to object1 and object2.
2592         void* objects[] = { 0 };
2593         RefCountedGarbageCollectedVisitor visitor(0, objects);
2594         ThreadState::current()->visitPersistents(&visitor);
2595         EXPECT_TRUE(visitor.validate());
2596
2597         {
2598             RefPtr<RefCountedAndGarbageCollected> object1(pointer1);
2599             RefPtr<RefCountedAndGarbageCollected2> object2(pointer2);
2600             void* objects[2] = { object1.get(), object2.get() };
2601             RefCountedGarbageCollectedVisitor visitor(2, objects);
2602             ThreadState::current()->visitPersistents(&visitor);
2603             EXPECT_TRUE(visitor.validate());
2604
2605             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2606             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2607             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2608         }
2609
2610         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2611         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2612         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2613     }
2614
2615     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2616     EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
2617     EXPECT_EQ(1, RefCountedAndGarbageCollected2::s_destructorCalls);
2618 }
2619
2620 TEST(HeapTest, WeakMembers)
2621 {
2622     Bar::s_live = 0;
2623     {
2624         Persistent<Bar> h1 = Bar::create();
2625         Persistent<Weak> h4;
2626         Persistent<WithWeakMember> h5;
2627         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2628         ASSERT_EQ(1u, Bar::s_live); // h1 is live.
2629         {
2630             Bar* h2 = Bar::create();
2631             Bar* h3 = Bar::create();
2632             h4 = Weak::create(h2, h3);
2633             h5 = WithWeakMember::create(h2, h3);
2634             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2635             EXPECT_EQ(5u, Bar::s_live); // The on-stack pointer keeps h3 alive.
2636             EXPECT_TRUE(h4->strongIsThere());
2637             EXPECT_TRUE(h4->weakIsThere());
2638             EXPECT_TRUE(h5->strongIsThere());
2639             EXPECT_TRUE(h5->weakIsThere());
2640         }
2641         // h3 is collected, weak pointers from h4 and h5 don't keep it alive.
2642         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2643         EXPECT_EQ(4u, Bar::s_live);
2644         EXPECT_TRUE(h4->strongIsThere());
2645         EXPECT_FALSE(h4->weakIsThere()); // h3 is gone from weak pointer.
2646         EXPECT_TRUE(h5->strongIsThere());
2647         EXPECT_FALSE(h5->weakIsThere()); // h3 is gone from weak pointer.
2648         h1.release(); // Zero out h1.
2649         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2650         EXPECT_EQ(3u, Bar::s_live); // Only h4, h5 and h2 are left.
2651         EXPECT_TRUE(h4->strongIsThere()); // h2 is still pointed to from h4.
2652         EXPECT_TRUE(h5->strongIsThere()); // h2 is still pointed to from h5.
2653     }
2654     // h4 and h5 have gone out of scope now and they were keeping h2 alive.
2655     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2656     EXPECT_EQ(0u, Bar::s_live); // All gone.
2657 }
2658
2659 TEST(HeapTest, FinalizationObserver)
2660 {
2661     Persistent<FinalizationObserver<Observable> > o;
2662     {
2663         Observable* foo = Observable::create(Bar::create());
2664         // |o| observes |foo|.
2665         o = FinalizationObserver<Observable>::create(foo);
2666     }
2667     // FinalizationObserver doesn't have a strong reference to |foo|. So |foo|
2668     // and its member will be collected.
2669     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2670     EXPECT_EQ(0u, Bar::s_live);
2671     EXPECT_TRUE(o->didCallWillFinalize());
2672
2673     FinalizationObserverWithHashMap::s_didCallWillFinalize = false;
2674     Observable* foo = Observable::create(Bar::create());
2675     FinalizationObserverWithHashMap::ObserverMap& map = FinalizationObserverWithHashMap::observe(*foo);
2676     EXPECT_EQ(1u, map.size());
2677     foo = 0;
2678     // FinalizationObserverWithHashMap doesn't have a strong reference to
2679     // |foo|. So |foo| and its member will be collected.
2680     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2681     EXPECT_EQ(0u, Bar::s_live);
2682     EXPECT_EQ(0u, map.size());
2683     EXPECT_TRUE(FinalizationObserverWithHashMap::s_didCallWillFinalize);
2684 }
2685
2686 TEST(HeapTest, Comparisons)
2687 {
2688     Persistent<Bar> barPersistent = Bar::create();
2689     Persistent<Foo> fooPersistent = Foo::create(barPersistent);
2690     EXPECT_TRUE(barPersistent != fooPersistent);
2691     barPersistent = fooPersistent;
2692     EXPECT_TRUE(barPersistent == fooPersistent);
2693 }
2694
2695 TEST(HeapTest, CheckAndMarkPointer)
2696 {
2697     HeapStats initialHeapStats;
2698     clearOutOldGarbage(&initialHeapStats);
2699
2700     Vector<Address> objectAddresses;
2701     Vector<Address> endAddresses;
2702     Address largeObjectAddress;
2703     Address largeObjectEndAddress;
2704     CountingVisitor visitor;
2705     for (int i = 0; i < 10; i++) {
2706         SimpleObject* object = SimpleObject::create();
2707         Address objectAddress = reinterpret_cast<Address>(object);
2708         objectAddresses.append(objectAddress);
2709         endAddresses.append(objectAddress + sizeof(SimpleObject) - 1);
2710     }
2711     LargeObject* largeObject = LargeObject::create();
2712     largeObjectAddress = reinterpret_cast<Address>(largeObject);
2713     largeObjectEndAddress = largeObjectAddress + sizeof(LargeObject) - 1;
2714
2715     // This is a low-level test where we call checkAndMarkPointer. This method
2716     // causes the object start bitmap to be computed which requires the heap
2717     // to be in a consistent state (e.g. the free allocation area must be put
2718     // into a free list header). However when we call makeConsistentForGC it
2719     // also clears out the freelists so we have to rebuild those before trying
2720     // to allocate anything again. We do this by forcing a GC after doing the
2721     // checkAndMarkPointer tests.
2722     {
2723         TestGCScope scope(ThreadState::HeapPointersOnStack);
2724         Heap::makeConsistentForGC();
2725         for (size_t i = 0; i < objectAddresses.size(); i++) {
2726             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, objectAddresses[i]));
2727             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, endAddresses[i]));
2728         }
2729         EXPECT_EQ(objectAddresses.size() * 2, visitor.count());
2730         visitor.reset();
2731         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectAddress));
2732         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress));
2733         EXPECT_EQ(2ul, visitor.count());
2734         visitor.reset();
2735     }
2736     // This forces a GC without stack scanning which results in the objects
2737     // being collected. This will also rebuild the above mentioned freelists,
2738     // however we don't rely on that below since we don't have any allocations.
2739     clearOutOldGarbage(&initialHeapStats);
2740     {
2741         TestGCScope scope(ThreadState::HeapPointersOnStack);
2742         Heap::makeConsistentForGC();
2743         for (size_t i = 0; i < objectAddresses.size(); i++) {
2744             EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, objectAddresses[i]));
2745             EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, endAddresses[i]));
2746         }
2747         EXPECT_EQ(0ul, visitor.count());
2748         EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, largeObjectAddress));
2749         EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress));
2750         EXPECT_EQ(0ul, visitor.count());
2751     }
2752     // This round of GC is important to make sure that the object start
2753     // bitmap are cleared out and that the free lists are rebuild.
2754     clearOutOldGarbage(&initialHeapStats);
2755 }
2756
2757 TEST(HeapTest, VisitOffHeapCollections)
2758 {
2759     HeapStats initialHeapStats;
2760     clearOutOldGarbage(&initialHeapStats);
2761     IntWrapper::s_destructorCalls = 0;
2762     Persistent<OffHeapContainer> container = OffHeapContainer::create();
2763     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2764     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
2765     container = nullptr;
2766     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2767     EXPECT_EQ(7, IntWrapper::s_destructorCalls);
2768 }
2769
2770 TEST(HeapTest, PersistentHeapCollectionTypes)
2771 {
2772     HeapStats initialHeapSize;
2773     IntWrapper::s_destructorCalls = 0;
2774
2775     typedef HeapVector<Member<IntWrapper> > Vec;
2776     typedef PersistentHeapVector<Member<IntWrapper> > PVec;
2777     typedef PersistentHeapHashSet<Member<IntWrapper> > PSet;
2778     typedef PersistentHeapHashMap<Member<IntWrapper>, Member<IntWrapper> > PMap;
2779
2780     clearOutOldGarbage(&initialHeapSize);
2781     {
2782         PVec pVec;
2783         PSet pSet;
2784         PMap pMap;
2785
2786         IntWrapper* one(IntWrapper::create(1));
2787         IntWrapper* two(IntWrapper::create(2));
2788         IntWrapper* three(IntWrapper::create(3));
2789         IntWrapper* four(IntWrapper::create(4));
2790         IntWrapper* five(IntWrapper::create(5));
2791         IntWrapper* six(IntWrapper::create(6));
2792
2793         pVec.append(one);
2794         pVec.append(two);
2795
2796         Vec* vec = new Vec();
2797         vec->swap(pVec);
2798
2799         pVec.append(two);
2800         pVec.append(three);
2801
2802         pSet.add(four);
2803         pMap.add(five, six);
2804
2805         // Collect |vec| and |one|.
2806         vec = 0;
2807         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2808         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
2809
2810         EXPECT_EQ(2u, pVec.size());
2811         EXPECT_TRUE(pVec.at(0) == two);
2812         EXPECT_TRUE(pVec.at(1) == three);
2813
2814         EXPECT_EQ(1u, pSet.size());
2815         EXPECT_TRUE(pSet.contains(four));
2816
2817         EXPECT_EQ(1u, pMap.size());
2818         EXPECT_TRUE(pMap.get(five) == six);
2819     }
2820
2821     // Collect previous roots.
2822     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2823     EXPECT_EQ(6, IntWrapper::s_destructorCalls);
2824 }
2825
2826 TEST(HeapTest, CollectionNesting)
2827 {
2828     HeapStats initialStats;
2829     clearOutOldGarbage(&initialStats);
2830     void* key = &IntWrapper::s_destructorCalls;
2831     IntWrapper::s_destructorCalls = 0;
2832     typedef HeapVector<Member<IntWrapper> > IntVector;
2833     HeapHashMap<void*, IntVector>* map = new HeapHashMap<void*, IntVector>();
2834
2835     map->add(key, IntVector());
2836
2837     HeapHashMap<void*, IntVector>::iterator it = map->find(key);
2838     EXPECT_EQ(0u, map->get(key).size());
2839
2840     it->value.append(IntWrapper::create(42));
2841     EXPECT_EQ(1u, map->get(key).size());
2842
2843     Persistent<HeapHashMap<void*, IntVector> > keepAlive(map);
2844     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2845     EXPECT_EQ(1u, map->get(key).size());
2846     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
2847 }
2848
2849 TEST(heap, GarbageCollectedMixin)
2850 {
2851     HeapStats initialHeapStats;
2852     clearOutOldGarbage(&initialHeapStats);
2853
2854     Persistent<UseMixin> usemixin = UseMixin::create();
2855     ASSERT_EQ(0, UseMixin::s_traceCount);
2856     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2857     ASSERT_EQ(1, UseMixin::s_traceCount);
2858
2859     Persistent<Mixin> mixin = usemixin;
2860     usemixin = nullptr;
2861     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2862     ASSERT_EQ(2, UseMixin::s_traceCount);
2863 }
2864
2865 TEST(HeapTest, CollectionNesting2)
2866 {
2867     HeapStats initialStats;
2868     clearOutOldGarbage(&initialStats);
2869     void* key = &IntWrapper::s_destructorCalls;
2870     IntWrapper::s_destructorCalls = 0;
2871     typedef HeapHashSet<Member<IntWrapper> > IntSet;
2872     HeapHashMap<void*, IntSet>* map = new HeapHashMap<void*, IntSet>();
2873
2874     map->add(key, IntSet());
2875
2876     HeapHashMap<void*, IntSet>::iterator it = map->find(key);
2877     EXPECT_EQ(0u, map->get(key).size());
2878
2879     it->value.add(IntWrapper::create(42));
2880     EXPECT_EQ(1u, map->get(key).size());
2881
2882     Persistent<HeapHashMap<void*, IntSet> > keepAlive(map);
2883     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2884     EXPECT_EQ(1u, map->get(key).size());
2885     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
2886 }
2887
2888 TEST(HeapTest, CollectionNesting3)
2889 {
2890     HeapStats initialStats;
2891     clearOutOldGarbage(&initialStats);
2892     IntWrapper::s_destructorCalls = 0;
2893     typedef HeapVector<Member<IntWrapper> > IntVector;
2894     HeapVector<IntVector>* vector = new HeapVector<IntVector>();
2895
2896     vector->append(IntVector());
2897
2898     HeapVector<IntVector>::iterator it = vector->begin();
2899     EXPECT_EQ(0u, it->size());
2900
2901     it->append(IntWrapper::create(42));
2902     EXPECT_EQ(1u, it->size());
2903
2904     Persistent<HeapVector<IntVector> > keepAlive(vector);
2905     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2906     EXPECT_EQ(1u, it->size());
2907     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
2908 }
2909
2910 TEST(HeapTest, EmbeddedInVector)
2911 {
2912     HeapStats initialStats;
2913     clearOutOldGarbage(&initialStats);
2914     SimpleFinalizedObject::s_destructorCalls = 0;
2915     {
2916         PersistentHeapVector<VectorObject, 2> inlineVector;
2917         PersistentHeapVector<VectorObject> outlineVector;
2918         VectorObject i1, i2;
2919         inlineVector.append(i1);
2920         inlineVector.append(i2);
2921
2922         VectorObject o1, o2;
2923         outlineVector.append(o1);
2924         outlineVector.append(o2);
2925
2926         PersistentHeapVector<VectorObjectInheritedTrace> vectorInheritedTrace;
2927         VectorObjectInheritedTrace it1, it2;
2928         vectorInheritedTrace.append(it1);
2929         vectorInheritedTrace.append(it2);
2930
2931         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2932         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
2933
2934         // Since VectorObjectNoTrace has no trace method it will
2935         // not be traced and hence be collected when doing GC.
2936         // We trace items in a collection braced on the item's
2937         // having a trace method. This is determined via the
2938         // NeedsTracing trait in wtf/TypeTraits.h.
2939         PersistentHeapVector<VectorObjectNoTrace> vectorNoTrace;
2940         VectorObjectNoTrace n1, n2;
2941         vectorNoTrace.append(n1);
2942         vectorNoTrace.append(n2);
2943         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2944         EXPECT_EQ(2, SimpleFinalizedObject::s_destructorCalls);
2945     }
2946     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2947     EXPECT_EQ(8, SimpleFinalizedObject::s_destructorCalls);
2948 }
2949
2950 TEST(HeapTest, RawPtrInHash)
2951 {
2952     HashSet<RawPtr<int> > set;
2953     set.add(new int(42));
2954     set.add(new int(42));
2955     EXPECT_EQ(2u, set.size());
2956     for (HashSet<RawPtr<int> >::iterator it = set.begin(); it != set.end(); ++it)
2957         EXPECT_EQ(42, **it);
2958 }
2959
2960 TEST(HeapTest, HeapTerminatedArray)
2961 {
2962     HeapStats initialHeapSize;
2963     clearOutOldGarbage(&initialHeapSize);
2964     IntWrapper::s_destructorCalls = 0;
2965
2966     HeapTerminatedArray<TerminatedArrayItem>* arr = 0;
2967
2968     const size_t prefixSize = 4;
2969     const size_t suffixSize = 4;
2970
2971     {
2972         HeapTerminatedArrayBuilder<TerminatedArrayItem> builder(arr);
2973         builder.grow(prefixSize);
2974         for (size_t i = 0; i < prefixSize; i++)
2975             builder.append(TerminatedArrayItem(IntWrapper::create(i)));
2976         arr = builder.release();
2977     }
2978
2979     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2980     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
2981     EXPECT_EQ(prefixSize, arr->size());
2982     for (size_t i = 0; i < prefixSize; i++)
2983         EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
2984
2985     {
2986         HeapTerminatedArrayBuilder<TerminatedArrayItem> builder(arr);
2987         builder.grow(suffixSize);
2988         for (size_t i = 0; i < suffixSize; i++)
2989             builder.append(TerminatedArrayItem(IntWrapper::create(prefixSize + i)));
2990         arr = builder.release();
2991     }
2992
2993     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2994     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
2995     EXPECT_EQ(prefixSize + suffixSize, arr->size());
2996     for (size_t i = 0; i < prefixSize + suffixSize; i++)
2997         EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
2998
2999     {
3000         Persistent<HeapTerminatedArray<TerminatedArrayItem> > persistentArr = arr;
3001         arr = 0;
3002         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3003         arr = persistentArr.get();
3004         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3005         EXPECT_EQ(prefixSize + suffixSize, arr->size());
3006         for (size_t i = 0; i < prefixSize + suffixSize; i++)
3007             EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
3008     }
3009
3010     arr = 0;
3011     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3012     EXPECT_EQ(8, IntWrapper::s_destructorCalls);
3013 }
3014
3015 TEST(HeapTest, HeapLinkedStack)
3016 {
3017     HeapStats initialHeapSize;
3018     clearOutOldGarbage(&initialHeapSize);
3019     IntWrapper::s_destructorCalls = 0;
3020
3021     HeapLinkedStack<TerminatedArrayItem>* stack = new HeapLinkedStack<TerminatedArrayItem>();
3022
3023     const size_t stackSize = 10;
3024
3025     for (size_t i = 0; i < stackSize; i++)
3026         stack->push(TerminatedArrayItem(IntWrapper::create(i)));
3027
3028     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3029     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3030     EXPECT_EQ(stackSize, stack->size());
3031     while (!stack->isEmpty()) {
3032         EXPECT_EQ(stack->size() - 1, static_cast<size_t>(stack->peek().payload()->value()));
3033         stack->pop();
3034     }
3035
3036     Persistent<HeapLinkedStack<TerminatedArrayItem> > pStack = stack;
3037
3038     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3039     EXPECT_EQ(stackSize, static_cast<size_t>(IntWrapper::s_destructorCalls));
3040     EXPECT_EQ(0u, pStack->size());
3041 }
3042
3043 TEST(HeapTest, AllocationDuringFinalization)
3044 {
3045     HeapStats initialHeapSize;
3046     clearOutOldGarbage(&initialHeapSize);
3047     IntWrapper::s_destructorCalls = 0;
3048     OneKiloByteObject::s_destructorCalls = 0;
3049
3050     Persistent<IntWrapper> wrapper;
3051     new FinalizationAllocator(&wrapper);
3052
3053     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3054     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3055     // Check that the wrapper allocated during finalization is not
3056     // swept away and zapped later in the same sweeping phase.
3057     EXPECT_EQ(42, wrapper->value());
3058
3059     wrapper.clear();
3060     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3061     EXPECT_EQ(10, IntWrapper::s_destructorCalls);
3062     EXPECT_EQ(512, OneKiloByteObject::s_destructorCalls);
3063 }
3064
3065 } // WebCore namespace