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/ThreadState.h"
  36 #include "heap/Visitor.h"
  37
  38 #include <gtest/gtest.h>
  39
  40 namespace WebCore {
  41
  42 class TestGCScope {
  43 public:
  44     explicit TestGCScope(ThreadState::StackState state)
  45         : m_state(ThreadState::current())
  46         , m_safePointScope(state)
  47     {
  48         m_state->checkThread();
  49         ASSERT(!m_state->isInGC());
  50         ThreadState::stopThreads();
  51         m_state->enterGC();
  52     }
  53
  54     ~TestGCScope()
  55     {
  56         m_state->leaveGC();
  57         ASSERT(!m_state->isInGC());
  58         ThreadState::resumeThreads();
  59     }
  60
  61 private:
  62     ThreadState* m_state;
  63     ThreadState::SafePointScope m_safePointScope;
  64 };
  65
  66 static void getHeapStats(HeapStats* stats)
  67 {
  68     TestGCScope scope(ThreadState::NoHeapPointersOnStack);
  69     Heap::getStats(stats);
  70 }
  71
  72 #define DEFINE_VISITOR_METHODS(Type)                                       \
  73     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
  74     {                                                                      \
  75         if (object)                                                        \
  76             m_count++;                                                     \
  77     }                                                                      \
  78     virtual bool isMarked(const Type*) OVERRIDE { return false; }
  79
  80 class CountingVisitor : public Visitor {
  81 public:
  82     CountingVisitor()
  83         : m_count(0)
  84     {
  85     }
  86
  87     virtual void mark(const void* object, TraceCallback) OVERRIDE
  88     {
  89         if (object)
  90             m_count++;
  91     }
  92
  93     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
  94     {
  95         ASSERT(header->payload());
  96         m_count++;
  97     }
  98
  99     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 100     {
 101         ASSERT(header->payload());
 102         m_count++;
 103     }
 104
 105     virtual void registerWeakMembers(const void*, WeakPointerCallback) OVERRIDE { }
 106     virtual bool isMarked(const void*) OVERRIDE { return false; }
 107
 108     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 109
 110     size_t count() { return m_count; }
 111     void reset() { m_count = 0; }
 112
 113 private:
 114     size_t m_count;
 115 };
 116
 117 class SimpleObject : public GarbageCollected<SimpleObject> {
 118     DECLARE_GC_INFO;
 119 public:
 120     static SimpleObject* create() { return new SimpleObject(); }
 121     void trace(Visitor*) { }
 122     char getPayload(int i) { return payload[i]; }
 123 private:
 124     SimpleObject() { }
 125     char payload[64];
 126 };
 127
 128 #undef DEFINE_VISITOR_METHODS
 129
 130 class HeapTestSuperClass : public GarbageCollectedFinalized<HeapTestSuperClass> {
 131     DECLARE_GC_INFO
 132 public:
 133     static HeapTestSuperClass* create()
 134     {
 135         return new HeapTestSuperClass();
 136     }
 137
 138     virtual ~HeapTestSuperClass()
 139     {
 140         ++s_destructorCalls;
 141     }
 142
 143     static int s_destructorCalls;
 144     void trace(Visitor*) { }
 145
 146 protected:
 147     HeapTestSuperClass() { }
 148 };
 149
 150 int HeapTestSuperClass::s_destructorCalls = 0;
 151
 152 class HeapTestOtherSuperClass {
 153 public:
 154     int payload;
 155 };
 156
 157 static const size_t classMagic = 0xABCDDBCA;
 158
 159 class HeapTestSubClass : public HeapTestOtherSuperClass, public HeapTestSuperClass {
 160 public:
 161     static HeapTestSubClass* create()
 162     {
 163         return new HeapTestSubClass();
 164     }
 165
 166     virtual ~HeapTestSubClass()
 167     {
 168         EXPECT_EQ(classMagic, m_magic);
 169         ++s_destructorCalls;
 170     }
 171
 172     static int s_destructorCalls;
 173
 174 private:
 175
 176     HeapTestSubClass() : m_magic(classMagic) { }
 177
 178     const size_t m_magic;
 179 };
 180
 181 int HeapTestSubClass::s_destructorCalls = 0;
 182
 183 class HeapAllocatedArray : public GarbageCollected<HeapAllocatedArray> {
 184     DECLARE_GC_INFO
 185 public:
 186     HeapAllocatedArray()
 187     {
 188         for (int i = 0; i < s_arraySize; ++i) {
 189             m_array[i] = i % 128;
 190         }
 191     }
 192
 193     int8_t at(size_t i) { return m_array[i]; }
 194     void trace(Visitor*) { }
 195 private:
 196     static const int s_arraySize = 1000;
 197     int8_t m_array[s_arraySize];
 198 };
 199
 200 // Do several GCs to make sure that later GCs don't free up old memory from
 201 // previously run tests in this process.
 202 static void clearOutOldGarbage(HeapStats* heapStats)
 203 {
 204     while (true) {
 205         getHeapStats(heapStats);
 206         size_t used = heapStats->totalObjectSpace();
 207         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 208         getHeapStats(heapStats);
 209         if (heapStats->totalObjectSpace() >= used)
 210             break;
 211     }
 212 }
 213
 214 class IntWrapper : public GarbageCollectedFinalized<IntWrapper> {
 215     DECLARE_GC_INFO
 216 public:
 217     static IntWrapper* create(int x)
 218     {
 219         return new IntWrapper(x);
 220     }
 221
 222     virtual ~IntWrapper()
 223     {
 224         ++s_destructorCalls;
 225     }
 226
 227     static int s_destructorCalls;
 228     static void trace(Visitor*) { }
 229
 230     int value() const { return m_x; }
 231
 232     bool operator==(const IntWrapper& other) const { return other.value() == value(); }
 233
 234     unsigned hash() { return IntHash<int>::hash(m_x); }
 235
 236 protected:
 237     IntWrapper(int x) : m_x(x) { }
 238
 239 private:
 240     IntWrapper();
 241     int m_x;
 242 };
 243
 244 USED_FROM_MULTIPLE_THREADS(IntWrapper);
 245
 246 int IntWrapper::s_destructorCalls = 0;
 247
 248 class ThreadedHeapTester {
 249 public:
 250     static void test()
 251     {
 252         ThreadedHeapTester* tester = new ThreadedHeapTester();
 253         for (int i = 0; i < numberOfThreads; i++)
 254             createThread(&threadFunc, tester, "testing thread");
 255         while (tester->m_threadsToFinish) {
 256             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 257             yield();
 258         }
 259     }
 260
 261 private:
 262     static const int numberOfThreads = 10;
 263     static const int gcPerThread = 5;
 264     static const int numberOfAllocations = 50;
 265
 266     inline bool done() const { return m_gcCount >= numberOfThreads * gcPerThread; }
 267
 268     ThreadedHeapTester() : m_gcCount(0), m_threadsToFinish(numberOfThreads)
 269     {
 270     }
 271
 272     static void threadFunc(void* data)
 273     {
 274         reinterpret_cast<ThreadedHeapTester*>(data)->runThread();
 275     }
 276
 277     void runThread()
 278     {
 279         ThreadState::attach();
 280
 281         int gcCount = 0;
 282         while (!done()) {
 283             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 284             {
 285                 IntWrapper* wrapper;
 286
 287                 typedef Persistent<IntWrapper, GlobalPersistents> GlobalIntWrapperPersistent;
 288                 OwnPtr<GlobalIntWrapperPersistent> globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 289
 290                 for (int i = 0; i < numberOfAllocations; i++) {
 291                     wrapper = IntWrapper::create(0x0bbac0de);
 292                     if (!(i % 10)) {
 293                         globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 294                         ThreadState::current()->safePoint(ThreadState::HeapPointersOnStack);
 295                     }
 296                     yield();
 297                 }
 298
 299                 if (gcCount < gcPerThread) {
 300                     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
 301                     gcCount++;
 302                     atomicIncrement(&m_gcCount);
 303                 }
 304
 305                 EXPECT_EQ(wrapper->value(), 0x0bbac0de);
 306                 EXPECT_EQ((*globalPersistent)->value(), 0x0ed0cabb);
 307             }
 308             yield();
 309         }
 310         ThreadState::current()->cleanup();
 311         ThreadState::detach();
 312         atomicDecrement(&m_threadsToFinish);
 313     }
 314
 315     volatile int m_gcCount;
 316     volatile int m_threadsToFinish;
 317 };
 318
 319 // The accounting for memory includes the memory used by rounding up object
 320 // sizes. This is done in a different way on 32 bit and 64 bit, so we have to
 321 // have some slack in the tests.
 322 template<typename T>
 323 void CheckWithSlack(T expected, T actual, int slack)
 324 {
 325     EXPECT_LE(expected, actual);
 326     EXPECT_GE((intptr_t)expected + slack, (intptr_t)actual);
 327 }
 328
 329 class TraceCounter : public GarbageCollectedFinalized<TraceCounter> {
 330     DECLARE_GC_INFO
 331 public:
 332     static TraceCounter* create()
 333     {
 334         return new TraceCounter();
 335     }
 336
 337     void trace(Visitor*) { m_traceCount++; }
 338
 339     int traceCount() { return m_traceCount; }
 340
 341 private:
 342     TraceCounter()
 343         : m_traceCount(0)
 344     {
 345     }
 346
 347     int m_traceCount;
 348 };
 349
 350 class ClassWithMember : public GarbageCollected<ClassWithMember> {
 351     DECLARE_GC_INFO
 352 public:
 353     static ClassWithMember* create()
 354     {
 355         return new ClassWithMember();
 356     }
 357
 358     void trace(Visitor* visitor)
 359     {
 360         EXPECT_TRUE(visitor->isMarked(this));
 361         if (!traceCount())
 362             EXPECT_FALSE(visitor->isMarked(m_traceCounter));
 363         else
 364             EXPECT_TRUE(visitor->isMarked(m_traceCounter));
 365
 366         visitor->trace(m_traceCounter);
 367     }
 368
 369     int traceCount() { return m_traceCounter->traceCount(); }
 370
 371 private:
 372     ClassWithMember()
 373         : m_traceCounter(TraceCounter::create())
 374     { }
 375
 376     Member<TraceCounter> m_traceCounter;
 377 };
 378
 379 class SimpleFinalizedObject : public GarbageCollectedFinalized<SimpleFinalizedObject> {
 380     DECLARE_GC_INFO
 381 public:
 382     static SimpleFinalizedObject* create()
 383     {
 384         return new SimpleFinalizedObject();
 385     }
 386
 387     ~SimpleFinalizedObject()
 388     {
 389         ++s_destructorCalls;
 390     }
 391
 392     static int s_destructorCalls;
 393
 394     void trace(Visitor*) { }
 395
 396 private:
 397     SimpleFinalizedObject() { }
 398 };
 399
 400 int SimpleFinalizedObject::s_destructorCalls = 0;
 401
 402 class TestTypedHeapClass : public GarbageCollected<TestTypedHeapClass> {
 403     DECLARE_GC_INFO
 404 public:
 405     static TestTypedHeapClass* create()
 406     {
 407         return new TestTypedHeapClass();
 408     }
 409
 410     void trace(Visitor*) { }
 411
 412 private:
 413     TestTypedHeapClass() { }
 414 };
 415
 416 class Bar : public GarbageCollectedFinalized<Bar> {
 417     DECLARE_GC_INFO
 418 public:
 419     static Bar* create()
 420     {
 421         return new Bar();
 422     }
 423
 424     void finalize()
 425     {
 426         EXPECT_TRUE(m_magic == magic);
 427         m_magic = 0;
 428         s_live--;
 429     }
 430
 431     virtual void trace(Visitor* visitor) { }
 432     static unsigned s_live;
 433
 434 protected:
 435     static const int magic = 1337;
 436     int m_magic;
 437
 438     Bar()
 439         : m_magic(magic)
 440     {
 441         s_live++;
 442     }
 443 };
 444
 445 unsigned Bar::s_live = 0;
 446
 447 class Baz : public GarbageCollected<Baz> {
 448     DECLARE_GC_INFO
 449 public:
 450     static Baz* create(Bar* bar)
 451     {
 452         return new Baz(bar);
 453     }
 454
 455     void trace(Visitor* visitor)
 456     {
 457         visitor->trace(m_bar);
 458     }
 459
 460     void clear() { m_bar.release(); }
 461
 462 private:
 463     explicit Baz(Bar* bar)
 464         : m_bar(bar)
 465     {
 466     }
 467
 468     Member<Bar> m_bar;
 469 };
 470
 471 class Foo : public Bar {
 472 public:
 473     static Foo* create(Bar* bar)
 474     {
 475         return new Foo(bar);
 476     }
 477
 478     static Foo* create(Foo* foo)
 479     {
 480         return new Foo(foo);
 481     }
 482
 483     virtual void trace(Visitor* visitor) OVERRIDE
 484     {
 485         if (m_pointsToFoo)
 486             visitor->mark(static_cast<Foo*>(m_bar));
 487         else
 488             visitor->mark(m_bar);
 489     }
 490
 491 private:
 492     Foo(Bar* bar)
 493         : Bar()
 494         , m_bar(bar)
 495         , m_pointsToFoo(false)
 496     {
 497     }
 498
 499     Foo(Foo* foo)
 500         : Bar()
 501         , m_bar(foo)
 502         , m_pointsToFoo(true)
 503     {
 504     }
 505
 506     Bar* m_bar;
 507     bool m_pointsToFoo;
 508 };
 509
 510 class Bars : public Bar {
 511 public:
 512     static Bars* create()
 513     {
 514         return new Bars();
 515     }
 516
 517     virtual void trace(Visitor* visitor) OVERRIDE
 518     {
 519         for (unsigned i = 0; i < m_width; i++)
 520             visitor->trace(m_bars[i]);
 521     }
 522
 523     unsigned getWidth() const
 524     {
 525         return m_width;
 526     }
 527
 528     static const unsigned width = 7500;
 529 private:
 530     Bars() : m_width(0)
 531     {
 532         for (unsigned i = 0; i < width; i++) {
 533             m_bars[i] = Bar::create();
 534             m_width++;
 535         }
 536     }
 537
 538     unsigned m_width;
 539     Member<Bar> m_bars[width];
 540 };
 541
 542 class ConstructorAllocation : public GarbageCollected<ConstructorAllocation> {
 543     DECLARE_GC_INFO
 544 public:
 545     static ConstructorAllocation* create() { return new ConstructorAllocation(); }
 546
 547     void trace(Visitor* visitor) { visitor->trace(m_intWrapper); }
 548
 549 private:
 550     ConstructorAllocation()
 551     {
 552         m_intWrapper = IntWrapper::create(42);
 553     }
 554
 555     Member<IntWrapper> m_intWrapper;
 556 };
 557
 558 class LargeObject : public GarbageCollectedFinalized<LargeObject> {
 559     DECLARE_GC_INFO
 560 public:
 561     ~LargeObject()
 562     {
 563         s_destructorCalls++;
 564     }
 565     static LargeObject* create() { return new LargeObject(); }
 566     char get(size_t i) { return m_data[i]; }
 567     void set(size_t i, char c) { m_data[i] = c; }
 568     size_t length() { return s_length; }
 569     void trace(Visitor* visitor)
 570     {
 571         visitor->trace(m_intWrapper);
 572     }
 573     static int s_destructorCalls;
 574
 575 private:
 576     static const size_t s_length = 1024*1024;
 577     LargeObject()
 578     {
 579         m_intWrapper = IntWrapper::create(23);
 580     }
 581     Member<IntWrapper> m_intWrapper;
 582     char m_data[s_length];
 583 };
 584
 585 int LargeObject::s_destructorCalls = 0;
 586
 587 class RefCountedAndGarbageCollected : public RefCountedGarbageCollected<RefCountedAndGarbageCollected> {
 588     DECLARE_GC_INFO
 589 public:
 590     static PassRefPtr<RefCountedAndGarbageCollected> create()
 591     {
 592         return adoptRef(new RefCountedAndGarbageCollected());
 593     }
 594
 595     ~RefCountedAndGarbageCollected()
 596     {
 597         ++s_destructorCalls;
 598     }
 599
 600     void trace(Visitor*) { }
 601
 602     static int s_destructorCalls;
 603
 604 private:
 605     RefCountedAndGarbageCollected()
 606     {
 607     }
 608 };
 609
 610 int RefCountedAndGarbageCollected::s_destructorCalls = 0;
 611
 612 class RefCountedAndGarbageCollected2 : public HeapTestOtherSuperClass, public RefCountedGarbageCollected<RefCountedAndGarbageCollected2> {
 613     DECLARE_GC_INFO
 614 public:
 615     static RefCountedAndGarbageCollected2* create()
 616     {
 617         return adoptRefCountedGarbageCollected(new RefCountedAndGarbageCollected2());
 618     }
 619
 620     ~RefCountedAndGarbageCollected2()
 621     {
 622         ++s_destructorCalls;
 623     }
 624
 625     void trace(Visitor*) { }
 626
 627     static int s_destructorCalls;
 628
 629 private:
 630     RefCountedAndGarbageCollected2()
 631     {
 632     }
 633 };
 634
 635 int RefCountedAndGarbageCollected2::s_destructorCalls = 0;
 636
 637 #define DEFINE_VISITOR_METHODS(Type)                                       \
 638     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
 639     {                                                                      \
 640         mark(object);                                                      \
 641     }                                                                      \
 642
 643 class RefCountedGarbageCollectedVisitor : public CountingVisitor {
 644 public:
 645     RefCountedGarbageCollectedVisitor(int expected, void** objects)
 646         : m_count(0)
 647         , m_expectedCount(expected)
 648         , m_expectedObjects(objects)
 649     {
 650     }
 651
 652     void mark(const void* ptr) { markNoTrace(ptr); }
 653
 654     virtual void markNoTrace(const void* ptr)
 655     {
 656         if (!ptr)
 657             return;
 658         if (m_count < m_expectedCount)
 659             EXPECT_TRUE(expectedObject(ptr));
 660         else
 661             EXPECT_FALSE(expectedObject(ptr));
 662         m_count++;
 663     }
 664
 665     virtual void mark(const void* ptr, TraceCallback) OVERRIDE
 666     {
 667         mark(ptr);
 668     }
 669
 670     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
 671     {
 672         mark(header->payload());
 673     }
 674
 675     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 676     {
 677         mark(header->payload());
 678     }
 679
 680     bool validate() { return m_count >= m_expectedCount; }
 681     void reset() { m_count = 0; }
 682
 683     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 684
 685 private:
 686     bool expectedObject(const void* ptr)
 687     {
 688         for (int i = 0; i < m_expectedCount; i++) {
 689             if (m_expectedObjects[i] == ptr)
 690                 return true;
 691         }
 692         return false;
 693     }
 694
 695     int m_count;
 696     int m_expectedCount;
 697     void** m_expectedObjects;
 698 };
 699
 700 #undef DEFINE_VISITOR_METHODS
 701
 702 class Weak : public Bar {
 703 public:
 704     static Weak* create(Bar* strong, Bar* weak)
 705     {
 706         return new Weak(strong, weak);
 707     }
 708
 709     virtual void trace(Visitor* visitor) OVERRIDE
 710     {
 711         visitor->trace(m_strongBar);
 712         visitor->registerWeakMembers(this, zapWeakMembers);
 713     }
 714
 715     static void zapWeakMembers(Visitor* visitor, void* self)
 716     {
 717         reinterpret_cast<Weak*>(self)->zapWeakMembers(visitor);
 718     }
 719
 720     bool strongIsThere() { return !!m_strongBar; }
 721     bool weakIsThere() { return !!m_weakBar; }
 722
 723 private:
 724     Weak(Bar* strongBar, Bar* weakBar)
 725         : Bar()
 726         , m_strongBar(strongBar)
 727         , m_weakBar(weakBar)
 728     {
 729     }
 730
 731     void zapWeakMembers(Visitor* visitor)
 732     {
 733         if (m_weakBar && !visitor->isAlive(m_weakBar))
 734             m_weakBar = 0;
 735     }
 736
 737     Member<Bar> m_strongBar;
 738     Bar* m_weakBar;
 739 };
 740
 741 class WithWeakMember : public Bar {
 742 public:
 743     static WithWeakMember* create(Bar* strong, Bar* weak)
 744     {
 745         return new WithWeakMember(strong, weak);
 746     }
 747
 748     virtual void trace(Visitor* visitor) OVERRIDE
 749     {
 750         visitor->trace(m_strongBar);
 751         visitor->trace(m_weakBar);
 752     }
 753
 754     bool strongIsThere() { return !!m_strongBar; }
 755     bool weakIsThere() { return !!m_weakBar; }
 756
 757 private:
 758     WithWeakMember(Bar* strongBar, Bar* weakBar)
 759         : Bar()
 760         , m_strongBar(strongBar)
 761         , m_weakBar(weakBar)
 762     {
 763     }
 764
 765     Member<Bar> m_strongBar;
 766     WeakMember<Bar> m_weakBar;
 767 };
 768
 769
 770 class SuperClass;
 771
 772 class PointsBack : public RefCountedWillBeGarbageCollectedFinalized<PointsBack> {
 773     DECLARE_GC_INFO;
 774 public:
 775     static PassRefPtrWillBeRawPtr<PointsBack> create()
 776     {
 777         return adoptRefWillBeNoop(new PointsBack());
 778     }
 779
 780     ~PointsBack()
 781     {
 782         --s_aliveCount;
 783     }
 784
 785     void setBackPointer(SuperClass* backPointer)
 786     {
 787         m_backPointer = backPointer;
 788     }
 789
 790     SuperClass* backPointer() const { return m_backPointer; }
 791
 792     void trace(Visitor* visitor)
 793     {
 794 #if ENABLE_OILPAN
 795         visitor->trace(m_backPointer);
 796 #endif
 797     }
 798
 799     static int s_aliveCount;
 800 private:
 801     PointsBack() : m_backPointer(0)
 802     {
 803         ++s_aliveCount;
 804     }
 805
 806     RawPtrWillBeWeakMember<SuperClass> m_backPointer;
 807 };
 808
 809 int PointsBack::s_aliveCount = 0;
 810
 811 class SuperClass : public RefCountedWillBeGarbageCollectedFinalized<SuperClass> {
 812     DECLARE_GC_INFO;
 813 public:
 814     static PassRefPtrWillBeRawPtr<SuperClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
 815     {
 816         return adoptRefWillBeNoop(new SuperClass(pointsBack));
 817     }
 818
 819     virtual ~SuperClass()
 820     {
 821 #if !ENABLE_OILPAN
 822         m_pointsBack->setBackPointer(0);
 823 #endif
 824         --s_aliveCount;
 825     }
 826
 827     void doStuff(PassRefPtrWillBeRawPtr<SuperClass> targetPass, PointsBack* pointsBack, int superClassCount)
 828     {
 829         RefPtrWillBeRawPtr<SuperClass> target = targetPass;
 830         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
 831         EXPECT_EQ(pointsBack, target->pointsBack());
 832         EXPECT_EQ(superClassCount, SuperClass::s_aliveCount);
 833     }
 834
 835     virtual void trace(Visitor* visitor)
 836     {
 837 #if ENABLE_OILPAN
 838         visitor->trace(m_pointsBack);
 839 #endif
 840     }
 841
 842     PointsBack* pointsBack() const { return m_pointsBack.get(); }
 843
 844     static int s_aliveCount;
 845 protected:
 846     explicit SuperClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
 847         : m_pointsBack(pointsBack)
 848     {
 849         m_pointsBack->setBackPointer(this);
 850         ++s_aliveCount;
 851     }
 852
 853 private:
 854     RefPtrWillBeMember<PointsBack> m_pointsBack;
 855 };
 856
 857 int SuperClass::s_aliveCount = 0;
 858 class SubData : public NoBaseWillBeGarbageCollectedFinalized<SubData> {
 859     DECLARE_GC_INFO
 860 public:
 861     SubData() { ++s_aliveCount; }
 862     ~SubData() { --s_aliveCount; }
 863
 864     void trace(Visitor*) { }
 865
 866     static int s_aliveCount;
 867 };
 868
 869 int SubData::s_aliveCount = 0;
 870
 871 class SubClass : public SuperClass {
 872 public:
 873     static PassRefPtrWillBeRawPtr<SubClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
 874     {
 875         return adoptRefWillBeNoop(new SubClass(pointsBack));
 876     }
 877
 878     virtual ~SubClass()
 879     {
 880         --s_aliveCount;
 881     }
 882
 883     virtual void trace(Visitor* visitor)
 884     {
 885 #if ENABLE_OILPAN
 886         SuperClass::trace(visitor);
 887         visitor->trace(m_data);
 888 #endif
 889     }
 890
 891     static int s_aliveCount;
 892 private:
 893     explicit SubClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
 894         : SuperClass(pointsBack)
 895         , m_data(adoptPtrWillBeNoop(new SubData()))
 896     {
 897         ++s_aliveCount;
 898     }
 899
 900 private:
 901     OwnPtrWillBeMember<SubData> m_data;
 902 };
 903
 904 int SubClass::s_aliveCount = 0;
 905
 906 class TransitionRefCounted : public RefCountedWillBeRefCountedGarbageCollected<TransitionRefCounted> {
 907     DECLARE_GC_INFO
 908 public:
 909     static PassRefPtrWillBeRawPtr<TransitionRefCounted> create()
 910     {
 911         return adoptRefCountedWillBeRefCountedGarbageCollected(new TransitionRefCounted());
 912     }
 913
 914     ~TransitionRefCounted()
 915     {
 916         --s_aliveCount;
 917     }
 918
 919     void trace(Visitor* visitor) { }
 920
 921     static int s_aliveCount;
 922
 923 private:
 924     TransitionRefCounted()
 925     {
 926         ++s_aliveCount;
 927     }
 928 };
 929
 930 int TransitionRefCounted::s_aliveCount = 0;
 931
 932 TEST(HeapTest, Transition)
 933 {
 934     {
 935         RefPtr<TransitionRefCounted> refCounted = TransitionRefCounted::create();
 936         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
 937         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 938         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
 939     }
 940     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 941     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
 942
 943     RefPtrWillBePersistent<PointsBack> pointsBack1 = PointsBack::create();
 944     RefPtrWillBePersistent<PointsBack> pointsBack2 = PointsBack::create();
 945     RefPtrWillBePersistent<SuperClass> superClass = SuperClass::create(pointsBack1);
 946     RefPtrWillBePersistent<SubClass> subClass = SubClass::create(pointsBack2);
 947     EXPECT_EQ(2, PointsBack::s_aliveCount);
 948     EXPECT_EQ(2, SuperClass::s_aliveCount);
 949     EXPECT_EQ(1, SubClass::s_aliveCount);
 950     EXPECT_EQ(1, SubData::s_aliveCount);
 951
 952     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 953     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
 954     EXPECT_EQ(2, PointsBack::s_aliveCount);
 955     EXPECT_EQ(2, SuperClass::s_aliveCount);
 956     EXPECT_EQ(1, SubClass::s_aliveCount);
 957     EXPECT_EQ(1, SubData::s_aliveCount);
 958
 959     superClass->doStuff(superClass.release(), pointsBack1.get(), 2);
 960     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 961     EXPECT_EQ(2, PointsBack::s_aliveCount);
 962     EXPECT_EQ(1, SuperClass::s_aliveCount);
 963     EXPECT_EQ(1, SubClass::s_aliveCount);
 964     EXPECT_EQ(1, SubData::s_aliveCount);
 965     EXPECT_EQ(0, pointsBack1->backPointer());
 966
 967     pointsBack1.release();
 968     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 969     EXPECT_EQ(1, PointsBack::s_aliveCount);
 970     EXPECT_EQ(1, SuperClass::s_aliveCount);
 971     EXPECT_EQ(1, SubClass::s_aliveCount);
 972     EXPECT_EQ(1, SubData::s_aliveCount);
 973
 974     subClass->doStuff(subClass.release(), pointsBack2.get(), 1);
 975     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 976     EXPECT_EQ(1, PointsBack::s_aliveCount);
 977     EXPECT_EQ(0, SuperClass::s_aliveCount);
 978     EXPECT_EQ(0, SubClass::s_aliveCount);
 979     EXPECT_EQ(0, SubData::s_aliveCount);
 980     EXPECT_EQ(0, pointsBack2->backPointer());
 981
 982     pointsBack2.release();
 983     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 984     EXPECT_EQ(0, PointsBack::s_aliveCount);
 985     EXPECT_EQ(0, SuperClass::s_aliveCount);
 986     EXPECT_EQ(0, SubClass::s_aliveCount);
 987     EXPECT_EQ(0, SubData::s_aliveCount);
 988
 989     EXPECT_TRUE(superClass == subClass);
 990 }
 991
 992 TEST(HeapTest, Threading)
 993 {
 994     ThreadedHeapTester::test();
 995 }
 996
 997 TEST(HeapTest, BasicFunctionality)
 998 {
 999     HeapStats heapStats;
1000     clearOutOldGarbage(&heapStats);
1001     {
1002         size_t slack = 0;
1003
1004         // When the test starts there may already have been leaked some memory
1005         // on the heap, so we establish a base line.
1006         size_t baseLevel = heapStats.totalObjectSpace();
1007         bool testPagesAllocated = !baseLevel;
1008         if (testPagesAllocated)
1009             EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1010
1011         // This allocates objects on the general heap which should add a page of memory.
1012         uint8_t* alloc32(Heap::allocate<uint8_t>(32));
1013         slack += 4;
1014         memset(alloc32, 40, 32);
1015         uint8_t* alloc64(Heap::allocate<uint8_t>(64));
1016         slack += 4;
1017         memset(alloc64, 27, 64);
1018
1019         size_t total = 96;
1020
1021         getHeapStats(&heapStats);
1022         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1023         if (testPagesAllocated)
1024             EXPECT_EQ(heapStats.totalAllocatedSpace(), blinkPageSize);
1025
1026         CheckWithSlack(alloc32 + 32 + sizeof(HeapObjectHeader), alloc64, slack);
1027
1028         EXPECT_EQ(alloc32[0], 40);
1029         EXPECT_EQ(alloc32[31], 40);
1030         EXPECT_EQ(alloc64[0], 27);
1031         EXPECT_EQ(alloc64[63], 27);
1032
1033         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1034
1035         EXPECT_EQ(alloc32[0], 40);
1036         EXPECT_EQ(alloc32[31], 40);
1037         EXPECT_EQ(alloc64[0], 27);
1038         EXPECT_EQ(alloc64[63], 27);
1039     }
1040
1041     clearOutOldGarbage(&heapStats);
1042     size_t total = 0;
1043     size_t slack = 0;
1044     size_t baseLevel = heapStats.totalObjectSpace();
1045     bool testPagesAllocated = !baseLevel;
1046     if (testPagesAllocated)
1047         EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1048
1049     const size_t big = 1008;
1050     Persistent<uint8_t> bigArea = Heap::allocate<uint8_t>(big);
1051     total += big;
1052     slack += 4;
1053
1054     size_t persistentCount = 0;
1055     const size_t numPersistents = 100000;
1056     Persistent<uint8_t>* persistents[numPersistents];
1057
1058     for (int i = 0; i < 1000; i++) {
1059         size_t size = 128 + i * 8;
1060         total += size;
1061         persistents[persistentCount++] = new Persistent<uint8_t>(Heap::allocate<uint8_t>(size));
1062         slack += 4;
1063         getHeapStats(&heapStats);
1064         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1065         if (testPagesAllocated)
1066             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1067     }
1068
1069     {
1070         uint8_t* alloc32b(Heap::allocate<uint8_t>(32));
1071         slack += 4;
1072         memset(alloc32b, 40, 32);
1073         uint8_t* alloc64b(Heap::allocate<uint8_t>(64));
1074         slack += 4;
1075         memset(alloc64b, 27, 64);
1076         EXPECT_TRUE(alloc32b != alloc64b);
1077
1078         total += 96;
1079         getHeapStats(&heapStats);
1080         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1081         if (testPagesAllocated)
1082             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1083     }
1084
1085     clearOutOldGarbage(&heapStats);
1086     total -= 96;
1087     slack -= 8;
1088     if (testPagesAllocated)
1089         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1090
1091     Address bigAreaRaw = bigArea;
1092     // Clear the persistent, so that the big area will be garbage collected.
1093     bigArea.release();
1094     clearOutOldGarbage(&heapStats);
1095
1096     total -= big;
1097     slack -= 4;
1098     getHeapStats(&heapStats);
1099     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1100     if (testPagesAllocated)
1101         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1102
1103     // Endless loop unless we eventually get the memory back that we just freed.
1104     while (true) {
1105         Persistent<uint8_t>* alloc = new Persistent<uint8_t>(Heap::allocate<uint8_t>(big / 2));
1106         slack += 4;
1107         persistents[persistentCount++] = alloc;
1108         EXPECT_LT(persistentCount, numPersistents);
1109         total += big / 2;
1110         if (bigAreaRaw == alloc->get())
1111             break;
1112     }
1113
1114     getHeapStats(&heapStats);
1115     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1116     if (testPagesAllocated)
1117         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1118
1119     for (size_t i = 0; i < persistentCount; i++) {
1120         delete persistents[i];
1121         persistents[i] = 0;
1122     }
1123
1124     uint8_t* address = Heap::reallocate<uint8_t>(0, 100);
1125     for (int i = 0; i < 100; i++)
1126         address[i] = i;
1127     address = Heap::reallocate<uint8_t>(address, 100000);
1128     for (int i = 0; i < 100; i++)
1129         EXPECT_EQ(address[i], i);
1130     address = Heap::reallocate<uint8_t>(address, 50);
1131     for (int i = 0; i < 50; i++)
1132         EXPECT_EQ(address[i], i);
1133     // This should be equivalent to free(address).
1134     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<uint8_t>(address, 0)), 0ul);
1135     // This should be equivalent to malloc(0).
1136     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<uint8_t>(0, 0)), 0ul);
1137 }
1138
1139 TEST(HeapTest, SimpleAllocation)
1140 {
1141     HeapStats initialHeapStats;
1142     clearOutOldGarbage(&initialHeapStats);
1143     EXPECT_EQ(0ul, initialHeapStats.totalObjectSpace());
1144
1145     // Allocate an object in the heap.
1146     HeapAllocatedArray* array = new HeapAllocatedArray();
1147     HeapStats statsAfterAllocation;
1148     getHeapStats(&statsAfterAllocation);
1149     EXPECT_TRUE(statsAfterAllocation.totalObjectSpace() >= sizeof(HeapAllocatedArray));
1150
1151     // Sanity check of the contents in the heap.
1152     EXPECT_EQ(0, array->at(0));
1153     EXPECT_EQ(42, array->at(42));
1154     EXPECT_EQ(0, array->at(128));
1155     EXPECT_EQ(999 % 128, array->at(999));
1156 }
1157
1158 TEST(HeapTest, SimplePersistent)
1159 {
1160     Persistent<TraceCounter> traceCounter = TraceCounter::create();
1161     EXPECT_EQ(0, traceCounter->traceCount());
1162
1163     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1164     EXPECT_EQ(1, traceCounter->traceCount());
1165
1166     Persistent<ClassWithMember> classWithMember = ClassWithMember::create();
1167     EXPECT_EQ(0, classWithMember->traceCount());
1168
1169     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1170     EXPECT_EQ(1, classWithMember->traceCount());
1171     EXPECT_EQ(2, traceCounter->traceCount());
1172 }
1173
1174 TEST(HeapTest, SimpleFinalization)
1175 {
1176     {
1177         Persistent<SimpleFinalizedObject> finalized = SimpleFinalizedObject::create();
1178         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1179         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1180         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1181     }
1182
1183     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1184     EXPECT_EQ(1, SimpleFinalizedObject::s_destructorCalls);
1185 }
1186
1187 TEST(HeapTest, Finalization)
1188 {
1189     {
1190         HeapTestSubClass* t1 = HeapTestSubClass::create();
1191         HeapTestSubClass* t2 = HeapTestSubClass::create();
1192         HeapTestSuperClass* t3 = HeapTestSuperClass::create();
1193         // FIXME(oilpan): Ignore unused variables.
1194         (void)t1;
1195         (void)t2;
1196         (void)t3;
1197     }
1198     // Nothing is marked so the GC should free everything and call
1199     // the finalizer on all three objects.
1200     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1201     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1202     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1203     // Destructors not called again when GCing again.
1204     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1205     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1206     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1207 }
1208
1209 TEST(HeapTest, TypedHeapSanity)
1210 {
1211     // We use TraceCounter for allocating an object on the general heap.
1212     Persistent<TraceCounter> generalHeapObject = TraceCounter::create();
1213     Persistent<TestTypedHeapClass> typedHeapObject = TestTypedHeapClass::create();
1214     EXPECT_NE(pageHeaderAddress(reinterpret_cast<Address>(generalHeapObject.get())),
1215         pageHeaderAddress(reinterpret_cast<Address>(typedHeapObject.get())));
1216 }
1217
1218 TEST(HeapTest, NoAllocation)
1219 {
1220     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1221     {
1222         // Disallow allocation
1223         NoAllocationScope<AnyThread> noAllocationScope;
1224         EXPECT_FALSE(ThreadState::current()->isAllocationAllowed());
1225     }
1226     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1227 }
1228
1229 TEST(HeapTest, Members)
1230 {
1231     Bar::s_live = 0;
1232     {
1233         Persistent<Baz> h1;
1234         Persistent<Baz> h2;
1235         {
1236             h1 = Baz::create(Bar::create());
1237             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1238             EXPECT_EQ(1u, Bar::s_live);
1239             h2 = Baz::create(Bar::create());
1240             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1241             EXPECT_EQ(2u, Bar::s_live);
1242         }
1243         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1244         EXPECT_EQ(2u, Bar::s_live);
1245         h1->clear();
1246         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1247         EXPECT_EQ(1u, Bar::s_live);
1248     }
1249     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1250     EXPECT_EQ(0u, Bar::s_live);
1251 }
1252
1253 TEST(HeapTest, MarkTest)
1254 {
1255     {
1256         Bar::s_live = 0;
1257         Persistent<Bar> bar = Bar::create();
1258         EXPECT_TRUE(ThreadState::current()->contains(bar));
1259         EXPECT_EQ(1u, Bar::s_live);
1260         {
1261             Foo* foo = Foo::create(bar);
1262             EXPECT_TRUE(ThreadState::current()->contains(foo));
1263             EXPECT_EQ(2u, Bar::s_live);
1264             EXPECT_TRUE(reinterpret_cast<Address>(foo) != reinterpret_cast<Address>(bar.get()));
1265             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1266             EXPECT_TRUE(foo != bar); // To make sure foo is kept alive.
1267             EXPECT_EQ(2u, Bar::s_live);
1268         }
1269         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1270         EXPECT_EQ(1u, Bar::s_live);
1271     }
1272     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1273     EXPECT_EQ(0u, Bar::s_live);
1274 }
1275
1276 TEST(HeapTest, DeepTest)
1277 {
1278     const unsigned depth = 100000;
1279     Bar::s_live = 0;
1280     {
1281         Bar* bar = Bar::create();
1282         EXPECT_TRUE(ThreadState::current()->contains(bar));
1283         Foo* foo = Foo::create(bar);
1284         EXPECT_TRUE(ThreadState::current()->contains(foo));
1285         EXPECT_EQ(2u, Bar::s_live);
1286         for (unsigned i = 0; i < depth; i++) {
1287             Foo* foo2 = Foo::create(foo);
1288             foo = foo2;
1289             EXPECT_TRUE(ThreadState::current()->contains(foo));
1290         }
1291         EXPECT_EQ(depth + 2, Bar::s_live);
1292         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1293         EXPECT_TRUE(foo != bar); // To make sure foo and bar are kept alive.
1294         EXPECT_EQ(depth + 2, Bar::s_live);
1295     }
1296     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1297     EXPECT_EQ(0u, Bar::s_live);
1298 }
1299
1300 TEST(HeapTest, WideTest)
1301 {
1302     Bar::s_live = 0;
1303     {
1304         Bars* bars = Bars::create();
1305         unsigned width = Bars::width;
1306         EXPECT_EQ(width + 1, Bar::s_live);
1307         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1308         EXPECT_EQ(width + 1, Bar::s_live);
1309         // Use bars here to make sure that it will be on the stack
1310         // for the conservative stack scan to find.
1311         EXPECT_EQ(width, bars->getWidth());
1312     }
1313     EXPECT_EQ(Bars::width + 1, Bar::s_live);
1314     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1315     EXPECT_EQ(0u, Bar::s_live);
1316 }
1317
1318 TEST(HeapTest, HashMapOfMembers)
1319 {
1320     HeapStats initialHeapSize;
1321     IntWrapper::s_destructorCalls = 0;
1322
1323     clearOutOldGarbage(&initialHeapSize);
1324     {
1325         typedef HashMap<
1326             Member<IntWrapper>,
1327             Member<IntWrapper>,
1328             DefaultHash<Member<IntWrapper> >::Hash,
1329             HashTraits<Member<IntWrapper> >,
1330             HashTraits<Member<IntWrapper> >,
1331             HeapAllocator> HeapObjectIdentityMap;
1332
1333         HeapObjectIdentityMap* map(new HeapObjectIdentityMap());
1334
1335         map->clear();
1336         HeapStats afterSetWasCreated;
1337         getHeapStats(&afterSetWasCreated);
1338         EXPECT_TRUE(afterSetWasCreated.totalObjectSpace() > initialHeapSize.totalObjectSpace());
1339
1340         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1341         HeapStats afterGC;
1342         getHeapStats(&afterGC);
1343         EXPECT_EQ(afterGC.totalObjectSpace(), afterSetWasCreated.totalObjectSpace());
1344
1345         IntWrapper* one(IntWrapper::create(1));
1346         IntWrapper* anotherOne(IntWrapper::create(1));
1347         map->add(one, one);
1348
1349         HeapStats afterOneAdd;
1350         getHeapStats(&afterOneAdd);
1351         EXPECT_TRUE(afterOneAdd.totalObjectSpace() > afterGC.totalObjectSpace());
1352
1353         HeapObjectIdentityMap::iterator it(map->begin());
1354         HeapObjectIdentityMap::iterator it2(map->begin());
1355         ++it;
1356         ++it2;
1357
1358         map->add(anotherOne, one);
1359
1360         // the addition above can cause an allocation of a new
1361         // backing store. We therefore garbage collect before
1362         // taking the heap stats in order to get rid of the old
1363         // backing store.
1364         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1365         HeapStats afterAddAndGC;
1366         getHeapStats(&afterAddAndGC);
1367         EXPECT_TRUE(afterAddAndGC.totalObjectSpace() >= afterOneAdd.totalObjectSpace());
1368
1369         EXPECT_EQ(map->size(), 2u); // Two different wrappings of '1' are distinct.
1370
1371         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1372         EXPECT_TRUE(map->contains(one));
1373         EXPECT_TRUE(map->contains(anotherOne));
1374
1375         IntWrapper* gotten(map->get(one));
1376         EXPECT_EQ(gotten->value(), one->value());
1377         EXPECT_EQ(gotten, one);
1378
1379         HeapStats afterGC2;
1380         getHeapStats(&afterGC2);
1381         EXPECT_EQ(afterGC2.totalObjectSpace(), afterAddAndGC.totalObjectSpace());
1382
1383         IntWrapper* dozen = 0;
1384
1385         for (int i = 1; i < 1000; i++) { // 999 iterations.
1386             IntWrapper* iWrapper(IntWrapper::create(i));
1387             IntWrapper* iSquared(IntWrapper::create(i * i));
1388             map->add(iWrapper, iSquared);
1389             if (i == 12)
1390                 dozen = iWrapper;
1391         }
1392         HeapStats afterAdding1000;
1393         getHeapStats(&afterAdding1000);
1394         EXPECT_TRUE(afterAdding1000.totalObjectSpace() > afterGC2.totalObjectSpace());
1395
1396         IntWrapper* gross(map->get(dozen));
1397         EXPECT_EQ(gross->value(), 144);
1398
1399         // This should clear out junk created by all the adds.
1400         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1401         HeapStats afterGC3;
1402         getHeapStats(&afterGC3);
1403         EXPECT_TRUE(afterGC3.totalObjectSpace() < afterAdding1000.totalObjectSpace());
1404     }
1405
1406     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1407     // The objects 'one', anotherOne, and the 999 other pairs.
1408     EXPECT_EQ(IntWrapper::s_destructorCalls, 2000);
1409     HeapStats afterGC4;
1410     getHeapStats(&afterGC4);
1411     EXPECT_EQ(afterGC4.totalObjectSpace(), initialHeapSize.totalObjectSpace());
1412 }
1413
1414 TEST(HeapTest, NestedAllocation)
1415 {
1416     HeapStats initialHeapSize;
1417     clearOutOldGarbage(&initialHeapSize);
1418     {
1419         Persistent<ConstructorAllocation> constructorAllocation = ConstructorAllocation::create();
1420     }
1421     HeapStats afterFree;
1422     clearOutOldGarbage(&afterFree);
1423     EXPECT_TRUE(initialHeapSize == afterFree);
1424 }
1425
1426 TEST(HeapTest, LargeObjects)
1427 {
1428     HeapStats initialHeapSize;
1429     clearOutOldGarbage(&initialHeapSize);
1430     IntWrapper::s_destructorCalls = 0;
1431     LargeObject::s_destructorCalls = 0;
1432     {
1433         int slack = 8; // LargeObject points to an IntWrapper that is also allocated.
1434         Persistent<LargeObject> object = LargeObject::create();
1435         HeapStats afterAllocation;
1436         clearOutOldGarbage(&afterAllocation);
1437         {
1438             object->set(0, 'a');
1439             EXPECT_EQ('a', object->get(0));
1440             object->set(object->length() - 1, 'b');
1441             EXPECT_EQ('b', object->get(object->length() - 1));
1442             size_t expectedObjectSpace = sizeof(LargeObject) + sizeof(IntWrapper);
1443             size_t actualObjectSpace =
1444                 afterAllocation.totalObjectSpace() - initialHeapSize.totalObjectSpace();
1445             CheckWithSlack(expectedObjectSpace, actualObjectSpace, slack);
1446             // There is probably space for the IntWrapper in a heap page without
1447             // allocating extra pages. However, the IntWrapper allocation might cause
1448             // the addition of a heap page.
1449             size_t largeObjectAllocationSize =
1450                 sizeof(LargeObject) + sizeof(LargeHeapObject<FinalizedHeapObjectHeader>) + sizeof(FinalizedHeapObjectHeader);
1451             size_t allocatedSpaceLowerBound =
1452                 initialHeapSize.totalAllocatedSpace() + largeObjectAllocationSize;
1453             size_t allocatedSpaceUpperBound = allocatedSpaceLowerBound + slack + blinkPageSize;
1454             EXPECT_LE(allocatedSpaceLowerBound, afterAllocation.totalAllocatedSpace());
1455             EXPECT_LE(afterAllocation.totalAllocatedSpace(), allocatedSpaceUpperBound);
1456             EXPECT_EQ(0, IntWrapper::s_destructorCalls);
1457             EXPECT_EQ(0, LargeObject::s_destructorCalls);
1458             for (int i = 0; i < 10; i++)
1459                 object = LargeObject::create();
1460         }
1461         HeapStats oneLargeObject;
1462         clearOutOldGarbage(&oneLargeObject);
1463         EXPECT_TRUE(oneLargeObject == afterAllocation);
1464         EXPECT_EQ(10, IntWrapper::s_destructorCalls);
1465         EXPECT_EQ(10, LargeObject::s_destructorCalls);
1466     }
1467     HeapStats backToInitial;
1468     clearOutOldGarbage(&backToInitial);
1469     EXPECT_TRUE(initialHeapSize == backToInitial);
1470     EXPECT_EQ(11, IntWrapper::s_destructorCalls);
1471     EXPECT_EQ(11, LargeObject::s_destructorCalls);
1472     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1473 }
1474
1475 class Container : public GarbageCollected<Container> {
1476     DECLARE_GC_INFO
1477 public:
1478     static Container* create() { return new Container(); }
1479     HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > map;
1480     HeapHashSet<Member<IntWrapper> > set;
1481     HeapHashSet<Member<IntWrapper> > set2;
1482     HeapVector<Member<IntWrapper>, 2> vector;
1483     void trace(Visitor* visitor)
1484     {
1485         visitor->trace(map);
1486         visitor->trace(set);
1487         visitor->trace(set2);
1488         visitor->trace(vector);
1489     }
1490 };
1491
1492 struct ShouldBeTraced {
1493     explicit ShouldBeTraced(IntWrapper* wrapper) : m_wrapper(wrapper) { }
1494     void trace(Visitor* visitor) { visitor->trace(m_wrapper); }
1495     Member<IntWrapper> m_wrapper;
1496 };
1497
1498 class OffHeapContainer : public GarbageCollectedFinalized<OffHeapContainer> {
1499     DECLARE_GC_INFO
1500 public:
1501     static OffHeapContainer* create() { return new OffHeapContainer(); }
1502
1503     OffHeapContainer()
1504     {
1505         m_deque1.append(ShouldBeTraced(IntWrapper::create(1)));
1506         m_vector1.append(ShouldBeTraced(IntWrapper::create(2)));
1507         m_deque2.append(IntWrapper::create(3));
1508         m_vector2.append(IntWrapper::create(4));
1509         m_hashSet.add(IntWrapper::create(5));
1510         m_hashMap.add(this, IntWrapper::create(6));
1511         m_listHashSet.add(IntWrapper::create(7));
1512     }
1513
1514     void trace(Visitor* visitor)
1515     {
1516         visitor->trace(m_deque1);
1517         visitor->trace(m_vector1);
1518         visitor->trace(m_deque2);
1519         visitor->trace(m_vector2);
1520         visitor->trace(m_hashSet);
1521         visitor->trace(m_hashMap);
1522         visitor->trace(m_listHashSet);
1523     }
1524
1525     Deque<ShouldBeTraced> m_deque1;
1526     Vector<ShouldBeTraced> m_vector1;
1527     Deque<Member<IntWrapper> > m_deque2;
1528     Vector<Member<IntWrapper> > m_vector2;
1529     HashSet<Member<IntWrapper> > m_hashSet;
1530     HashMap<void*, Member<IntWrapper> > m_hashMap;
1531     ListHashSet<Member<IntWrapper> > m_listHashSet;
1532 };
1533
1534 TEST(HeapTest, HeapVectorWithInlineCapacity)
1535 {
1536     IntWrapper* one = IntWrapper::create(1);
1537     IntWrapper* two = IntWrapper::create(2);
1538     IntWrapper* three = IntWrapper::create(3);
1539     IntWrapper* four = IntWrapper::create(4);
1540     IntWrapper* five = IntWrapper::create(5);
1541     IntWrapper* six = IntWrapper::create(6);
1542     {
1543         HeapVector<Member<IntWrapper>, 2> vector;
1544         vector.append(one);
1545         vector.append(two);
1546         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1547         EXPECT_TRUE(vector.contains(one));
1548         EXPECT_TRUE(vector.contains(two));
1549
1550         vector.append(three);
1551         vector.append(four);
1552         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1553         EXPECT_TRUE(vector.contains(one));
1554         EXPECT_TRUE(vector.contains(two));
1555         EXPECT_TRUE(vector.contains(three));
1556         EXPECT_TRUE(vector.contains(four));
1557
1558         vector.shrink(1);
1559         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1560         EXPECT_TRUE(vector.contains(one));
1561         EXPECT_FALSE(vector.contains(two));
1562         EXPECT_FALSE(vector.contains(three));
1563         EXPECT_FALSE(vector.contains(four));
1564     }
1565     {
1566         HeapVector<Member<IntWrapper>, 2> vector1;
1567         HeapVector<Member<IntWrapper>, 2> vector2;
1568
1569         vector1.append(one);
1570         vector2.append(two);
1571         vector1.swap(vector2);
1572         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1573         EXPECT_TRUE(vector1.contains(two));
1574         EXPECT_TRUE(vector2.contains(one));
1575     }
1576     {
1577         HeapVector<Member<IntWrapper>, 2> vector1;
1578         HeapVector<Member<IntWrapper>, 2> vector2;
1579
1580         vector1.append(one);
1581         vector1.append(two);
1582         vector2.append(three);
1583         vector2.append(four);
1584         vector2.append(five);
1585         vector2.append(six);
1586         vector1.swap(vector2);
1587         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1588         EXPECT_TRUE(vector1.contains(three));
1589         EXPECT_TRUE(vector1.contains(four));
1590         EXPECT_TRUE(vector1.contains(five));
1591         EXPECT_TRUE(vector1.contains(six));
1592         EXPECT_TRUE(vector2.contains(one));
1593         EXPECT_TRUE(vector2.contains(two));
1594     }
1595 }
1596
1597 TEST(HeapTest, HeapCollectionTypes)
1598 {
1599     HeapStats initialHeapSize;
1600     IntWrapper::s_destructorCalls = 0;
1601
1602     typedef HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > MemberMember;
1603     typedef HeapHashMap<Member<IntWrapper>, int> MemberPrimitive;
1604     typedef HeapHashMap<int, Member<IntWrapper> > PrimitiveMember;
1605
1606     typedef HeapHashSet<Member<IntWrapper> > MemberSet;
1607     typedef HeapHashSet<WeakMember<IntWrapper> > WeakMemberSet;
1608
1609     typedef HeapVector<Member<IntWrapper>, 2> MemberVector;
1610
1611     Persistent<MemberMember> memberMember = new MemberMember();
1612     Persistent<MemberMember> memberMember2 = new MemberMember();
1613     Persistent<MemberMember> memberMember3 = new MemberMember();
1614     Persistent<MemberPrimitive> memberPrimitive = new MemberPrimitive();
1615     Persistent<PrimitiveMember> primitiveMember = new PrimitiveMember();
1616     Persistent<MemberSet> set = new MemberSet();
1617     Persistent<MemberSet> set2 = new MemberSet();
1618     Persistent<MemberVector> vector = new MemberVector();
1619     Persistent<MemberVector> vector2 = new MemberVector();
1620     Persistent<Container> container = Container::create();
1621
1622     clearOutOldGarbage(&initialHeapSize);
1623     {
1624         Persistent<IntWrapper> one(IntWrapper::create(1));
1625         Persistent<IntWrapper> two(IntWrapper::create(2));
1626         Persistent<IntWrapper> oneB(IntWrapper::create(1));
1627         Persistent<IntWrapper> twoB(IntWrapper::create(2));
1628         Persistent<IntWrapper> oneC(IntWrapper::create(1));
1629         Persistent<IntWrapper> twoC(IntWrapper::create(2));
1630         {
1631             IntWrapper* three(IntWrapper::create(3));
1632             IntWrapper* four(IntWrapper::create(4));
1633             IntWrapper* threeB(IntWrapper::create(3));
1634             IntWrapper* fourB(IntWrapper::create(4));
1635
1636             // Member Collections.
1637             memberMember2->add(one, two);
1638             memberMember2->add(two, three);
1639             memberMember2->add(three, four);
1640             memberMember2->add(four, one);
1641             primitiveMember->add(1, two);
1642             primitiveMember->add(2, three);
1643             primitiveMember->add(3, four);
1644             primitiveMember->add(4, one);
1645             memberPrimitive->add(one, 2);
1646             memberPrimitive->add(two, 3);
1647             memberPrimitive->add(three, 4);
1648             memberPrimitive->add(four, 1);
1649             set2->add(one);
1650             set2->add(two);
1651             set2->add(three);
1652             set2->add(four);
1653             set->add(oneB);
1654             vector->append(oneB);
1655             vector2->append(threeB);
1656             vector2->append(fourB);
1657
1658             // Collect garbage. This should change nothing since we are keeping
1659             // alive the IntWrapper objects with on-stack pointers.
1660             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1661             EXPECT_EQ(0u, memberMember->size());
1662             EXPECT_EQ(4u, memberMember2->size());
1663             EXPECT_EQ(4u, primitiveMember->size());
1664             EXPECT_EQ(4u, memberPrimitive->size());
1665             EXPECT_EQ(1u, set->size());
1666             EXPECT_EQ(4u, set2->size());
1667             EXPECT_EQ(1u, vector->size());
1668             EXPECT_EQ(2u, vector2->size());
1669
1670             MemberVector& cvec = container->vector;
1671             cvec.swap(*vector.get());
1672             vector2->swap(cvec);
1673             vector->swap(cvec);
1674
1675             // Swap set and set2 in a roundabout way.
1676             MemberSet& cset1 = container->set;
1677             MemberSet& cset2 = container->set2;
1678             set->swap(cset1);
1679             set2->swap(cset2);
1680             set->swap(cset2);
1681             cset1.swap(cset2);
1682             cset2.swap(set2);
1683
1684             // Triple swap.
1685             container->map.swap(memberMember2);
1686             MemberMember& containedMap = container->map;
1687             memberMember3->swap(containedMap);
1688             memberMember3->swap(memberMember);
1689
1690             EXPECT_TRUE(memberMember->get(one) == two);
1691             EXPECT_TRUE(memberMember->get(two) == three);
1692             EXPECT_TRUE(memberMember->get(three) == four);
1693             EXPECT_TRUE(memberMember->get(four) == one);
1694             EXPECT_TRUE(primitiveMember->get(1) == two);
1695             EXPECT_TRUE(primitiveMember->get(2) == three);
1696             EXPECT_TRUE(primitiveMember->get(3) == four);
1697             EXPECT_TRUE(primitiveMember->get(4) == one);
1698             EXPECT_EQ(1, memberPrimitive->get(four));
1699             EXPECT_EQ(2, memberPrimitive->get(one));
1700             EXPECT_EQ(3, memberPrimitive->get(two));
1701             EXPECT_EQ(4, memberPrimitive->get(three));
1702             EXPECT_TRUE(set->contains(one));
1703             EXPECT_TRUE(set->contains(two));
1704             EXPECT_TRUE(set->contains(three));
1705             EXPECT_TRUE(set->contains(four));
1706             EXPECT_TRUE(set2->contains(oneB));
1707             EXPECT_TRUE(vector->contains(threeB));
1708             EXPECT_TRUE(vector->contains(fourB));
1709             EXPECT_TRUE(vector2->contains(oneB));
1710             EXPECT_FALSE(vector2->contains(threeB));
1711         }
1712
1713         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1714
1715         EXPECT_EQ(4u, memberMember->size());
1716         EXPECT_EQ(0u, memberMember2->size());
1717         EXPECT_EQ(4u, primitiveMember->size());
1718         EXPECT_EQ(4u, memberPrimitive->size());
1719         EXPECT_EQ(4u, set->size());
1720         EXPECT_EQ(1u, set2->size());
1721         EXPECT_EQ(2u, vector->size());
1722         EXPECT_EQ(1u, vector2->size());
1723
1724         EXPECT_TRUE(memberMember->get(one) == two);
1725         EXPECT_TRUE(primitiveMember->get(1) == two);
1726         EXPECT_TRUE(primitiveMember->get(4) == one);
1727         EXPECT_EQ(2, memberPrimitive->get(one));
1728         EXPECT_EQ(3, memberPrimitive->get(two));
1729         EXPECT_TRUE(set->contains(one));
1730         EXPECT_TRUE(set->contains(two));
1731         EXPECT_FALSE(set->contains(oneB));
1732         EXPECT_TRUE(set2->contains(oneB));
1733         EXPECT_EQ(3, vector->at(0)->value());
1734         EXPECT_EQ(4, vector->at(1)->value());
1735     }
1736
1737     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1738     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1739
1740     EXPECT_EQ(4u, memberMember->size());
1741     EXPECT_EQ(4u, primitiveMember->size());
1742     EXPECT_EQ(4u, memberPrimitive->size());
1743     EXPECT_EQ(4u, set->size());
1744     EXPECT_EQ(1u, set2->size());
1745     EXPECT_EQ(2u, vector->size());
1746     EXPECT_EQ(1u, vector2->size());
1747     EXPECT_EQ(2u, vector->size());
1748     EXPECT_EQ(1u, vector2->size());
1749 }
1750
1751 template<typename T>
1752 void MapIteratorCheck(T& it, const T& end, int expected)
1753 {
1754     int found = 0;
1755     while (it != end) {
1756         found++;
1757         int key = it->key->value();
1758         int value = it->value->value();
1759         EXPECT_TRUE(key >= 0 && key < 1100);
1760         EXPECT_TRUE(value >= 0 && value < 1100);
1761         ++it;
1762     }
1763     EXPECT_EQ(expected, found);
1764 }
1765
1766 template<typename T>
1767 void SetIteratorCheck(T& it, const T& end, int expected)
1768 {
1769     int found = 0;
1770     while (it != end) {
1771         found++;
1772         int value = (*it)->value();
1773         EXPECT_TRUE(value >= 0 && value < 1100);
1774         ++it;
1775     }
1776     EXPECT_EQ(expected, found);
1777 }
1778
1779 TEST(HeapTest, CollectionPersistent)
1780 {
1781     HeapStats empty;
1782     clearOutOldGarbage(&empty);
1783     IntWrapper::s_destructorCalls = 0;
1784
1785     CollectionPersistent<Vector<Member<IntWrapper> > > vector;
1786     CollectionPersistent<HashSet<Member<IntWrapper> > > set;
1787     CollectionPersistent<HashMap<Member<IntWrapper>, Member<IntWrapper> > > map;
1788     CollectionPersistent<ListHashSet<Member<IntWrapper> > > listSet;
1789
1790     vector->append(IntWrapper::create(42));
1791     set->add(IntWrapper::create(103));
1792     map->add(IntWrapper::create(137), IntWrapper::create(139));
1793     listSet->add(IntWrapper::create(167));
1794     listSet->add(IntWrapper::create(671));
1795     listSet->add(IntWrapper::create(176));
1796
1797     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
1798
1799     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1800
1801     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
1802
1803     typedef HashSet<Member<IntWrapper> >::iterator SetIterator;
1804     typedef HashMap<Member<IntWrapper>, Member<IntWrapper> >::iterator MapIterator;
1805     typedef ListHashSet<Member<IntWrapper> >::iterator ListSetIterator;
1806
1807     SetIterator setIterator = set->begin();
1808     MapIterator mapIterator = map->begin();
1809     ListSetIterator listSetIterator = listSet->begin();
1810
1811     EXPECT_EQ(42, vector[0]->value());
1812     EXPECT_EQ(103, (*setIterator)->value());
1813     EXPECT_EQ(137, mapIterator->key->value());
1814     EXPECT_EQ(139, mapIterator->value->value());
1815     EXPECT_EQ(167, (*listSetIterator)->value());
1816 }
1817
1818 TEST(HeapTest, HeapWeakCollectionSimple)
1819 {
1820
1821     IntWrapper::s_destructorCalls = 0;
1822
1823     CollectionPersistent<Vector<Member<IntWrapper> > > keepNumbersAlive;
1824
1825     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
1826     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
1827     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
1828     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
1829
1830     Persistent<WeakStrong> weakStrong = new WeakStrong();
1831     Persistent<StrongWeak> strongWeak = new StrongWeak();
1832     Persistent<WeakWeak> weakWeak = new WeakWeak();
1833     Persistent<WeakSet> weakSet = new WeakSet();
1834
1835     Persistent<IntWrapper> two = IntWrapper::create(2);
1836
1837     keepNumbersAlive->append(IntWrapper::create(103));
1838     keepNumbersAlive->append(IntWrapper::create(10));
1839
1840     {
1841         weakStrong->add(IntWrapper::create(1), two);
1842         strongWeak->add(two, IntWrapper::create(1));
1843         weakWeak->add(two, IntWrapper::create(42));
1844         weakWeak->add(IntWrapper::create(42), two);
1845         weakSet->add(IntWrapper::create(0));
1846         weakSet->add(two);
1847         weakSet->add(keepNumbersAlive[0]);
1848         weakSet->add(keepNumbersAlive[1]);
1849         EXPECT_EQ(1u, weakStrong->size());
1850         EXPECT_EQ(1u, strongWeak->size());
1851         EXPECT_EQ(2u, weakWeak->size());
1852         EXPECT_EQ(4u, weakSet->size());
1853     }
1854
1855     keepNumbersAlive[0] = 0;
1856
1857     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1858
1859     EXPECT_EQ(0u, weakStrong->size());
1860     EXPECT_EQ(0u, strongWeak->size());
1861     EXPECT_EQ(0u, weakWeak->size());
1862     EXPECT_EQ(2u, weakSet->size());
1863 }
1864
1865 TEST(HeapTest, HeapWeakCollectionTypes)
1866 {
1867     HeapStats initialHeapSize;
1868     IntWrapper::s_destructorCalls = 0;
1869
1870     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
1871     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
1872     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
1873     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
1874
1875     clearOutOldGarbage(&initialHeapSize);
1876
1877     const int weakStrongIndex = 0;
1878     const int strongWeakIndex = 1;
1879     const int weakWeakIndex = 2;
1880     const int numberOfMapIndices = 3;
1881     const int weakSetIndex = 3;
1882     const int numberOfCollections = 4;
1883
1884     for (int testRun = 0; testRun < 4; testRun++) {
1885         for (int collectionNumber = 0; collectionNumber < numberOfCollections; collectionNumber++) {
1886             bool testThatIteratorsMakeStrong = (testRun == weakSetIndex);
1887             bool deleteAfterwards = (testRun == 1);
1888             bool addAfterwards = (testRun == weakWeakIndex);
1889
1890             // The test doesn't work for strongWeak with deleting because we lost
1891             // the key from the keepNumbersAlive array, so we can't do the lookup.
1892             if (deleteAfterwards && collectionNumber == strongWeakIndex)
1893                 continue;
1894
1895             unsigned added = addAfterwards ? 100 : 0;
1896
1897             Persistent<WeakStrong> weakStrong = new WeakStrong();
1898             Persistent<StrongWeak> strongWeak = new StrongWeak();
1899             Persistent<WeakWeak> weakWeak = new WeakWeak();
1900
1901             Persistent<WeakSet> weakSet = new WeakSet();
1902
1903             CollectionPersistent<Vector<Member<IntWrapper> > > keepNumbersAlive;
1904             for (int i = 0; i < 128; i += 2) {
1905                 IntWrapper* wrapped = IntWrapper::create(i);
1906                 IntWrapper* wrapped2 = IntWrapper::create(i + 1);
1907                 keepNumbersAlive->append(wrapped);
1908                 keepNumbersAlive->append(wrapped2);
1909                 weakStrong->add(wrapped, wrapped2);
1910                 strongWeak->add(wrapped2, wrapped);
1911                 weakWeak->add(wrapped, wrapped2);
1912                 weakSet->add(wrapped);
1913             }
1914
1915             EXPECT_EQ(64u, weakStrong->size());
1916             EXPECT_EQ(64u, strongWeak->size());
1917             EXPECT_EQ(64u, weakWeak->size());
1918             EXPECT_EQ(64u, weakSet->size());
1919
1920             // Collect garbage. This should change nothing since we are keeping
1921             // alive the IntWrapper objects.
1922             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1923
1924             EXPECT_EQ(64u, weakStrong->size());
1925             EXPECT_EQ(64u, strongWeak->size());
1926             EXPECT_EQ(64u, weakWeak->size());
1927             EXPECT_EQ(64u, weakSet->size());
1928
1929             for (int i = 0; i < 128; i += 2) {
1930                 IntWrapper* wrapped = keepNumbersAlive[i];
1931                 IntWrapper* wrapped2 = keepNumbersAlive[i + 1];
1932                 EXPECT_EQ(wrapped2, weakStrong->get(wrapped));
1933                 EXPECT_EQ(wrapped, strongWeak->get(wrapped2));
1934                 EXPECT_EQ(wrapped2, weakWeak->get(wrapped));
1935                 EXPECT_TRUE(weakSet->contains(wrapped));
1936             }
1937
1938             for (int i = 0; i < 128; i += 3)
1939                 keepNumbersAlive[i] = 0;
1940
1941             if (collectionNumber != weakStrongIndex)
1942                 weakStrong->clear();
1943             if (collectionNumber != strongWeakIndex)
1944                 strongWeak->clear();
1945             if (collectionNumber != weakWeakIndex)
1946                 weakWeak->clear();
1947             if (collectionNumber != weakSetIndex)
1948                 weakSet->clear();
1949
1950             if (testThatIteratorsMakeStrong) {
1951                 WeakStrong::iterator it1 = weakStrong->begin();
1952                 StrongWeak::iterator it2 = strongWeak->begin();
1953                 WeakWeak::iterator it3 = weakWeak->begin();
1954                 WeakSet::iterator it4 = weakSet->begin();
1955                 // Collect garbage. This should change nothing since the
1956                 // iterators make the collections strong.
1957                 Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1958                 if (collectionNumber == weakStrongIndex) {
1959                     EXPECT_EQ(64u, weakStrong->size());
1960                     MapIteratorCheck(it1, weakStrong->end(), 64);
1961                 } else if (collectionNumber == strongWeakIndex) {
1962                     EXPECT_EQ(64u, strongWeak->size());
1963                     MapIteratorCheck(it2, strongWeak->end(), 64);
1964                 } else if (collectionNumber == weakWeakIndex) {
1965                     EXPECT_EQ(64u, weakWeak->size());
1966                     MapIteratorCheck(it3, weakWeak->end(), 64);
1967                 } else if (collectionNumber == weakSetIndex) {
1968                     EXPECT_EQ(64u, weakSet->size());
1969                     SetIteratorCheck(it4, weakSet->end(), 64);
1970                 }
1971             } else {
1972                 // Collect garbage. This causes weak processing to remove
1973                 // things from the collections.
1974                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1975                 unsigned count = 0;
1976                 for (int i = 0; i < 128; i += 2) {
1977                     bool firstAlive = keepNumbersAlive[i];
1978                     bool secondAlive = keepNumbersAlive[i + 1];
1979                     if (firstAlive && (collectionNumber == weakStrongIndex || collectionNumber == strongWeakIndex))
1980                         secondAlive = true;
1981                     if (firstAlive && secondAlive && collectionNumber < numberOfMapIndices) {
1982                         if (collectionNumber == weakStrongIndex) {
1983                             if (deleteAfterwards)
1984                                 EXPECT_EQ(i + 1, weakStrong->take(keepNumbersAlive[i])->value());
1985                         } else if (collectionNumber == strongWeakIndex) {
1986                             if (deleteAfterwards)
1987                                 EXPECT_EQ(i, strongWeak->take(keepNumbersAlive[i + 1])->value());
1988                         } else if (collectionNumber == weakWeakIndex) {
1989                             if (deleteAfterwards)
1990                                 EXPECT_EQ(i + 1, weakWeak->take(keepNumbersAlive[i])->value());
1991                         }
1992                         if (!deleteAfterwards)
1993                             count++;
1994                     } else if (collectionNumber == weakSetIndex && firstAlive) {
1995                         ASSERT_TRUE(weakSet->contains(keepNumbersAlive[i]));
1996                         if (deleteAfterwards)
1997                             weakSet->remove(keepNumbersAlive[i]);
1998                         else
1999                             count++;
2000                     }
2001                 }
2002                 if (addAfterwards) {
2003                     for (int i = 1000; i < 1100; i++) {
2004                         IntWrapper* wrapped = IntWrapper::create(i);
2005                         keepNumbersAlive->append(wrapped);
2006                         weakStrong->add(wrapped, wrapped);
2007                         strongWeak->add(wrapped, wrapped);
2008                         weakWeak->add(wrapped, wrapped);
2009                         weakSet->add(wrapped);
2010                     }
2011                 }
2012                 if (collectionNumber == weakStrongIndex)
2013                     EXPECT_EQ(count + added, weakStrong->size());
2014                 else if (collectionNumber == strongWeakIndex)
2015                     EXPECT_EQ(count + added, strongWeak->size());
2016                 else if (collectionNumber == weakWeakIndex)
2017                     EXPECT_EQ(count + added, weakWeak->size());
2018                 else if (collectionNumber == weakSetIndex)
2019                     EXPECT_EQ(count + added, weakSet->size());
2020                 WeakStrong::iterator it1 = weakStrong->begin();
2021                 StrongWeak::iterator it2 = strongWeak->begin();
2022                 WeakWeak::iterator it3 = weakWeak->begin();
2023                 WeakSet::iterator it4 = weakSet->begin();
2024                 MapIteratorCheck(it1, weakStrong->end(), (collectionNumber == weakStrongIndex ? count : 0) + added);
2025                 MapIteratorCheck(it2, strongWeak->end(), (collectionNumber == strongWeakIndex ? count : 0) + added);
2026                 MapIteratorCheck(it3, weakWeak->end(), (collectionNumber == weakWeakIndex ? count : 0) + added);
2027                 SetIteratorCheck(it4, weakSet->end(), (collectionNumber == weakSetIndex ? count : 0) + added);
2028             }
2029             for (unsigned i = 0; i < 128 + added; i++)
2030                 keepNumbersAlive[i] = 0;
2031             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2032             EXPECT_EQ(added, weakStrong->size());
2033             EXPECT_EQ(added, strongWeak->size());
2034             EXPECT_EQ(added, weakWeak->size());
2035             EXPECT_EQ(added, weakSet->size());
2036         }
2037     }
2038 }
2039
2040 TEST(HeapTest, RefCountedGarbageCollected)
2041 {
2042     RefCountedAndGarbageCollected::s_destructorCalls = 0;
2043     {
2044         RefPtr<RefCountedAndGarbageCollected> refPtr3;
2045         {
2046             Persistent<RefCountedAndGarbageCollected> persistent;
2047             {
2048                 RefPtr<RefCountedAndGarbageCollected> refPtr1 = RefCountedAndGarbageCollected::create();
2049                 RefPtr<RefCountedAndGarbageCollected> refPtr2 = RefCountedAndGarbageCollected::create();
2050                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2051                 EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2052                 persistent = refPtr1.get();
2053             }
2054             // Reference count is zero for both objects but one of
2055             // them is kept alive by a persistent handle.
2056             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2057             EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
2058             refPtr3 = persistent;
2059         }
2060         // The persistent handle is gone but the ref count has been
2061         // increased to 1.
2062         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2063         EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
2064     }
2065     // Both persistent handle is gone and ref count is zero so the
2066     // object can be collected.
2067     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2068     EXPECT_EQ(2, RefCountedAndGarbageCollected::s_destructorCalls);
2069 }
2070
2071 TEST(HeapTest, RefCountedGarbageCollectedWithStackPointers)
2072 {
2073     RefCountedAndGarbageCollected::s_destructorCalls = 0;
2074     RefCountedAndGarbageCollected2::s_destructorCalls = 0;
2075     {
2076         RefCountedAndGarbageCollected* pointer1 = 0;
2077         RefCountedAndGarbageCollected2* pointer2 = 0;
2078         {
2079             RefPtr<RefCountedAndGarbageCollected> object1 = RefCountedAndGarbageCollected::create();
2080             RefPtr<RefCountedAndGarbageCollected2> object2 = RefCountedAndGarbageCollected2::create();
2081             pointer1 = object1.get();
2082             pointer2 = object2.get();
2083             void* objects[2] = { object1.get(), object2.get() };
2084             RefCountedGarbageCollectedVisitor visitor(2, objects);
2085             ThreadState::current()->visitPersistents(&visitor);
2086             EXPECT_TRUE(visitor.validate());
2087
2088             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2089             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2090             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2091         }
2092         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2093         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2094         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2095
2096         // At this point, the reference counts of object1 and object2 are 0.
2097         // Only pointer1 and pointer2 keep references to object1 and object2.
2098         void* objects[] = { 0 };
2099         RefCountedGarbageCollectedVisitor visitor(0, objects);
2100         ThreadState::current()->visitPersistents(&visitor);
2101         EXPECT_TRUE(visitor.validate());
2102
2103         {
2104             RefPtr<RefCountedAndGarbageCollected> object1(pointer1);
2105             RefPtr<RefCountedAndGarbageCollected2> object2(pointer2);
2106             void* objects[2] = { object1.get(), object2.get() };
2107             RefCountedGarbageCollectedVisitor visitor(2, objects);
2108             ThreadState::current()->visitPersistents(&visitor);
2109             EXPECT_TRUE(visitor.validate());
2110
2111             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2112             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2113             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2114         }
2115
2116         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2117         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
2118         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
2119     }
2120
2121     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2122     EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
2123     EXPECT_EQ(1, RefCountedAndGarbageCollected2::s_destructorCalls);
2124 }
2125
2126 TEST(HeapTest, WeakMembers)
2127 {
2128     Bar::s_live = 0;
2129     {
2130         Persistent<Bar> h1 = Bar::create();
2131         Persistent<Weak> h4;
2132         Persistent<WithWeakMember> h5;
2133         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2134         ASSERT_EQ(1u, Bar::s_live); // h1 is live.
2135         {
2136             Bar* h2 = Bar::create();
2137             Bar* h3 = Bar::create();
2138             h4 = Weak::create(h2, h3);
2139             h5 = WithWeakMember::create(h2, h3);
2140             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2141             EXPECT_EQ(5u, Bar::s_live); // The on-stack pointer keeps h3 alive.
2142             EXPECT_TRUE(h4->strongIsThere());
2143             EXPECT_TRUE(h4->weakIsThere());
2144             EXPECT_TRUE(h5->strongIsThere());
2145             EXPECT_TRUE(h5->weakIsThere());
2146         }
2147         // h3 is collected, weak pointers from h4 and h5 don't keep it alive.
2148         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2149         EXPECT_EQ(4u, Bar::s_live);
2150         EXPECT_TRUE(h4->strongIsThere());
2151         EXPECT_FALSE(h4->weakIsThere()); // h3 is gone from weak pointer.
2152         EXPECT_TRUE(h5->strongIsThere());
2153         EXPECT_FALSE(h5->weakIsThere()); // h3 is gone from weak pointer.
2154         h1.release(); // Zero out h1.
2155         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2156         EXPECT_EQ(3u, Bar::s_live); // Only h4, h5 and h2 are left.
2157         EXPECT_TRUE(h4->strongIsThere()); // h2 is still pointed to from h4.
2158         EXPECT_TRUE(h5->strongIsThere()); // h2 is still pointed to from h5.
2159     }
2160     // h4 and h5 have gone out of scope now and they were keeping h2 alive.
2161     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2162     EXPECT_EQ(0u, Bar::s_live); // All gone.
2163 }
2164
2165 TEST(HeapTest, Comparisons)
2166 {
2167     Persistent<Bar> barPersistent = Bar::create();
2168     Persistent<Foo> fooPersistent = Foo::create(barPersistent);
2169     EXPECT_TRUE(barPersistent != fooPersistent);
2170     barPersistent = fooPersistent;
2171     EXPECT_TRUE(barPersistent == fooPersistent);
2172 }
2173
2174 TEST(HeapTest, CheckAndMarkPointer)
2175 {
2176     HeapStats initialHeapStats;
2177     clearOutOldGarbage(&initialHeapStats);
2178
2179     Vector<Address> objectAddresses;
2180     Vector<Address> endAddresses;
2181     Address largeObjectAddress;
2182     Address largeObjectEndAddress;
2183     CountingVisitor visitor;
2184     for (int i = 0; i < 10; i++) {
2185         SimpleObject* object = SimpleObject::create();
2186         Address objectAddress = reinterpret_cast<Address>(object);
2187         objectAddresses.append(objectAddress);
2188         endAddresses.append(objectAddress + sizeof(SimpleObject) - 1);
2189     }
2190     LargeObject* largeObject = LargeObject::create();
2191     largeObjectAddress = reinterpret_cast<Address>(largeObject);
2192     largeObjectEndAddress = largeObjectAddress + sizeof(LargeObject) - 1;
2193
2194     // This is a low-level test where we call checkAndMarkPointer. This method
2195     // causes the object start bitmap to be computed which requires the heap
2196     // to be in a consistent state (e.g. the free allocation area must be put
2197     // into a free list header). However when we call makeConsistentForGC it
2198     // also clears out the freelists so we have to rebuild those before trying
2199     // to allocate anything again. We do this by forcing a GC after doing the
2200     // checkAndMarkPointer tests.
2201     {
2202         TestGCScope scope(ThreadState::HeapPointersOnStack);
2203         Heap::makeConsistentForGC();
2204         for (size_t i = 0; i < objectAddresses.size(); i++) {
2205             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, objectAddresses[i]));
2206             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, endAddresses[i]));
2207         }
2208         EXPECT_EQ(objectAddresses.size() * 2, visitor.count());
2209         visitor.reset();
2210         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectAddress));
2211         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress));
2212         EXPECT_EQ(2ul, visitor.count());
2213         visitor.reset();
2214     }
2215     // This forces a GC without stack scanning which results in the objects
2216     // being collected. This will also rebuild the above mentioned freelists,
2217     // however we don't rely on that below since we don't have any allocations.
2218     clearOutOldGarbage(&initialHeapStats);
2219     {
2220         TestGCScope scope(ThreadState::HeapPointersOnStack);
2221         Heap::makeConsistentForGC();
2222         for (size_t i = 0; i < objectAddresses.size(); i++) {
2223             EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, objectAddresses[i]));
2224             EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, endAddresses[i]));
2225         }
2226         EXPECT_EQ(0ul, visitor.count());
2227         EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, largeObjectAddress));
2228         EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress));
2229         EXPECT_EQ(0ul, visitor.count());
2230     }
2231     // This round of GC is important to make sure that the object start
2232     // bitmap are cleared out and that the free lists are rebuild.
2233     clearOutOldGarbage(&initialHeapStats);
2234 }
2235
2236 TEST(HeapTest, VisitOffHeapCollections)
2237 {
2238     HeapStats initialHeapStats;
2239     clearOutOldGarbage(&initialHeapStats);
2240     IntWrapper::s_destructorCalls = 0;
2241     Persistent<OffHeapContainer> container = OffHeapContainer::create();
2242     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2243     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
2244     container = 0;
2245     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2246     EXPECT_EQ(7, IntWrapper::s_destructorCalls);
2247 }
2248
2249 TEST(HeapTest, PersistentHeapCollectionTypes)
2250 {
2251     HeapStats initialHeapSize;
2252     IntWrapper::s_destructorCalls = 0;
2253
2254     typedef HeapVector<Member<IntWrapper> > Vec;
2255     typedef PersistentHeapVector<Member<IntWrapper> > PVec;
2256     typedef PersistentHeapHashSet<Member<IntWrapper> > PSet;
2257     typedef PersistentHeapHashMap<Member<IntWrapper>, Member<IntWrapper> > PMap;
2258
2259     clearOutOldGarbage(&initialHeapSize);
2260     {
2261         PVec pVec;
2262         PSet pSet;
2263         PMap pMap;
2264
2265         IntWrapper* one(IntWrapper::create(1));
2266         IntWrapper* two(IntWrapper::create(2));
2267         IntWrapper* three(IntWrapper::create(3));
2268         IntWrapper* four(IntWrapper::create(4));
2269         IntWrapper* five(IntWrapper::create(5));
2270         IntWrapper* six(IntWrapper::create(6));
2271
2272         pVec.append(one);
2273         pVec.append(two);
2274
2275         Vec* vec = new Vec();
2276         vec->swap(pVec);
2277
2278         pVec.append(two);
2279         pVec.append(three);
2280
2281         pSet.add(four);
2282         pMap.add(five, six);
2283
2284         // Collect |vec| and |one|.
2285         vec = 0;
2286         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2287         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
2288
2289         EXPECT_EQ(2u, pVec.size());
2290         EXPECT_TRUE(pVec.at(0) == two);
2291         EXPECT_TRUE(pVec.at(1) == three);
2292
2293         EXPECT_EQ(1u, pSet.size());
2294         EXPECT_TRUE(pSet.contains(four));
2295
2296         EXPECT_EQ(1u, pMap.size());
2297         EXPECT_TRUE(pMap.get(five) == six);
2298     }
2299
2300     // Collect previous roots.
2301     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2302     EXPECT_EQ(6, IntWrapper::s_destructorCalls);
2303 }
2304
2305 DEFINE_GC_INFO(Bar);
2306 DEFINE_GC_INFO(Baz);
2307 DEFINE_GC_INFO(ClassWithMember);
2308 DEFINE_GC_INFO(ConstructorAllocation);
2309 DEFINE_GC_INFO(Container);
2310 DEFINE_GC_INFO(HeapAllocatedArray);
2311 DEFINE_GC_INFO(HeapTestSuperClass);
2312 DEFINE_GC_INFO(IntWrapper);
2313 DEFINE_GC_INFO(LargeObject);
2314 DEFINE_GC_INFO(OffHeapContainer);
2315 DEFINE_GC_INFO(PointsBack);
2316 DEFINE_GC_INFO(RefCountedAndGarbageCollected);
2317 DEFINE_GC_INFO(RefCountedAndGarbageCollected2);
2318 DEFINE_GC_INFO(SimpleFinalizedObject);
2319 DEFINE_GC_INFO(SimpleObject);
2320 DEFINE_GC_INFO(SuperClass);
2321 DEFINE_GC_INFO(SubData);
2322 DEFINE_GC_INFO(TestTypedHeapClass);
2323 DEFINE_GC_INFO(TraceCounter);
2324 DEFINE_GC_INFO(TransitionRefCounted);
2325
2326 } // namespace