src/third_party/WebKit/Source/platform/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 "platform/heap/Handle.h"
  34 #include "platform/heap/Heap.h"
  35 #include "platform/heap/HeapLinkedStack.h"
  36 #include "platform/heap/HeapTerminatedArrayBuilder.h"
  37 #include "platform/heap/ThreadState.h"
  38 #include "platform/heap/Visitor.h"
  39 #include "public/platform/Platform.h"
  40 #include "wtf/HashTraits.h"
  41 #include "wtf/LinkedHashSet.h"
  42
  43 #include <gtest/gtest.h>
  44
  45 namespace WebCore {
  46
  47 class ThreadMarker {
  48 public:
  49     ThreadMarker() : m_creatingThread(reinterpret_cast<ThreadState*>(0)), m_num(0) { }
  50     ThreadMarker(unsigned i) : m_creatingThread(ThreadState::current()), m_num(i) { }
  51     ThreadMarker(WTF::HashTableDeletedValueType deleted) : m_creatingThread(reinterpret_cast<ThreadState*>(-1)), m_num(0) { }
  52     ~ThreadMarker()
  53     {
  54         EXPECT_TRUE((m_creatingThread == ThreadState::current())
  55             || (m_creatingThread == reinterpret_cast<ThreadState*>(0))
  56             || (m_creatingThread == reinterpret_cast<ThreadState*>(-1)));
  57     }
  58     bool isHashTableDeletedValue() const { return m_creatingThread == reinterpret_cast<ThreadState*>(-1); }
  59     bool operator==(const ThreadMarker& other) const { return other.m_creatingThread == m_creatingThread && other.m_num == m_num; }
  60     ThreadState* m_creatingThread;
  61     unsigned m_num;
  62 };
  63
  64 struct ThreadMarkerHash {
  65     static unsigned hash(const ThreadMarker& key)
  66     {
  67         return static_cast<unsigned>(reinterpret_cast<uintptr_t>(key.m_creatingThread) + key.m_num);
  68     }
  69
  70     static bool equal(const ThreadMarker& a, const ThreadMarker& b)
  71     {
  72         return a == b;
  73     }
  74
  75     static const bool safeToCompareToEmptyOrDeleted = false;
  76 };
  77
  78 }
  79
  80 namespace WTF {
  81
  82 template<typename T> struct DefaultHash;
  83 template<> struct DefaultHash<WebCore::ThreadMarker> {
  84     typedef WebCore::ThreadMarkerHash Hash;
  85 };
  86
  87 // ThreadMarkerHash is the default hash for ThreadMarker
  88 template<> struct HashTraits<WebCore::ThreadMarker> : GenericHashTraits<WebCore::ThreadMarker> {
  89     static const bool emptyValueIsZero = true;
  90     static void constructDeletedValue(WebCore::ThreadMarker& slot) { new (NotNull, &slot) WebCore::ThreadMarker(HashTableDeletedValue); }
  91     static bool isDeletedValue(const WebCore::ThreadMarker& slot) { return slot.isHashTableDeletedValue(); }
  92 };
  93
  94 }
  95
  96 namespace WebCore {
  97
  98 class TestGCScope {
  99 public:
 100     explicit TestGCScope(ThreadState::StackState state)
 101         : m_state(ThreadState::current())
 102         , m_safePointScope(state)
 103         , m_parkedAllThreads(false)
 104     {
 105         m_state->checkThread();
 106         EXPECT_FALSE(m_state->isInGC());
 107         if (LIKELY(ThreadState::stopThreads())) {
 108             m_state->enterGC();
 109             m_parkedAllThreads = true;
 110         }
 111     }
 112
 113     bool allThreadsParked() { return m_parkedAllThreads; }
 114
 115     ~TestGCScope()
 116     {
 117         // Only cleanup if we parked all threads in which case the GC happened
 118         // and we need to resume the other threads.
 119         if (LIKELY(m_parkedAllThreads)) {
 120             m_state->leaveGC();
 121             EXPECT_FALSE(m_state->isInGC());
 122             ThreadState::resumeThreads();
 123         }
 124     }
 125
 126 private:
 127     ThreadState* m_state;
 128     ThreadState::SafePointScope m_safePointScope;
 129     bool m_parkedAllThreads; // False if we fail to park all threads
 130 };
 131
 132 static void getHeapStats(HeapStats* stats)
 133 {
 134     TestGCScope scope(ThreadState::NoHeapPointersOnStack);
 135     EXPECT_TRUE(scope.allThreadsParked());
 136     Heap::getStats(stats);
 137 }
 138
 139 #define DEFINE_VISITOR_METHODS(Type)                                       \
 140     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
 141     {                                                                      \
 142         if (object)                                                        \
 143             m_count++;                                                     \
 144     }                                                                      \
 145     virtual bool isMarked(const Type*) OVERRIDE { return false; }
 146
 147 class CountingVisitor : public Visitor {
 148 public:
 149     CountingVisitor()
 150         : m_count(0)
 151     {
 152     }
 153
 154     virtual void mark(const void* object, TraceCallback) OVERRIDE
 155     {
 156         if (object)
 157             m_count++;
 158     }
 159
 160     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
 161     {
 162         ASSERT(header->payload());
 163         m_count++;
 164     }
 165
 166     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 167     {
 168         ASSERT(header->payload());
 169         m_count++;
 170     }
 171
 172     virtual void markConservatively(HeapObjectHeader* header) OVERRIDE
 173     {
 174         ASSERT_NOT_REACHED();
 175     }
 176
 177     virtual void markConservatively(FinalizedHeapObjectHeader* header) OVERRIDE
 178     {
 179         ASSERT_NOT_REACHED();
 180     }
 181
 182     virtual void registerWeakMembers(const void*, const void*, WeakPointerCallback) OVERRIDE { }
 183     virtual void registerWeakCell(void**, WeakPointerCallback) OVERRIDE { }
 184     virtual bool isMarked(const void*) OVERRIDE { return false; }
 185
 186     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 187
 188     size_t count() { return m_count; }
 189     void reset() { m_count = 0; }
 190
 191 private:
 192     size_t m_count;
 193 };
 194
 195 class SimpleObject : public GarbageCollected<SimpleObject> {
 196 public:
 197     static SimpleObject* create() { return new SimpleObject(); }
 198     void trace(Visitor*) { }
 199     char getPayload(int i) { return payload[i]; }
 200     // This virtual method is unused but it is here to make sure
 201     // that this object has a vtable. This object is used
 202     // as the super class for objects that also have garbage
 203     // collected mixins and having a virtual here makes sure
 204     // that adjustment is needed both for marking and for isAlive
 205     // checks.
 206     virtual void virtualMethod() { }
 207 protected:
 208     SimpleObject() { }
 209     char payload[64];
 210 };
 211
 212 #undef DEFINE_VISITOR_METHODS
 213
 214 class HeapTestSuperClass : public GarbageCollectedFinalized<HeapTestSuperClass> {
 215 public:
 216     static HeapTestSuperClass* create()
 217     {
 218         return new HeapTestSuperClass();
 219     }
 220
 221     virtual ~HeapTestSuperClass()
 222     {
 223         ++s_destructorCalls;
 224     }
 225
 226     static int s_destructorCalls;
 227     void trace(Visitor*) { }
 228
 229 protected:
 230     HeapTestSuperClass() { }
 231 };
 232
 233 int HeapTestSuperClass::s_destructorCalls = 0;
 234
 235 class HeapTestOtherSuperClass {
 236 public:
 237     int payload;
 238 };
 239
 240 static const size_t classMagic = 0xABCDDBCA;
 241
 242 class HeapTestSubClass : public HeapTestOtherSuperClass, public HeapTestSuperClass {
 243 public:
 244     static HeapTestSubClass* create()
 245     {
 246         return new HeapTestSubClass();
 247     }
 248
 249     virtual ~HeapTestSubClass()
 250     {
 251         EXPECT_EQ(classMagic, m_magic);
 252         ++s_destructorCalls;
 253     }
 254
 255     static int s_destructorCalls;
 256
 257 private:
 258
 259     HeapTestSubClass() : m_magic(classMagic) { }
 260
 261     const size_t m_magic;
 262 };
 263
 264 int HeapTestSubClass::s_destructorCalls = 0;
 265
 266 class HeapAllocatedArray : public GarbageCollected<HeapAllocatedArray> {
 267 public:
 268     HeapAllocatedArray()
 269     {
 270         for (int i = 0; i < s_arraySize; ++i) {
 271             m_array[i] = i % 128;
 272         }
 273     }
 274
 275     int8_t at(size_t i) { return m_array[i]; }
 276     void trace(Visitor*) { }
 277 private:
 278     static const int s_arraySize = 1000;
 279     int8_t m_array[s_arraySize];
 280 };
 281
 282 // Do several GCs to make sure that later GCs don't free up old memory from
 283 // previously run tests in this process.
 284 static void clearOutOldGarbage(HeapStats* heapStats)
 285 {
 286     while (true) {
 287         getHeapStats(heapStats);
 288         size_t used = heapStats->totalObjectSpace();
 289         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 290         getHeapStats(heapStats);
 291         if (heapStats->totalObjectSpace() >= used)
 292             break;
 293     }
 294 }
 295
 296 class IntWrapper : public GarbageCollectedFinalized<IntWrapper> {
 297 public:
 298     static IntWrapper* create(int x)
 299     {
 300         return new IntWrapper(x);
 301     }
 302
 303     virtual ~IntWrapper()
 304     {
 305         ++s_destructorCalls;
 306     }
 307
 308     static int s_destructorCalls;
 309     static void trace(Visitor*) { }
 310
 311     int value() const { return m_x; }
 312
 313     bool operator==(const IntWrapper& other) const { return other.value() == value(); }
 314
 315     unsigned hash() { return IntHash<int>::hash(m_x); }
 316
 317 protected:
 318     IntWrapper(int x) : m_x(x) { }
 319
 320 private:
 321     IntWrapper();
 322     int m_x;
 323 };
 324
 325 class OffHeapInt : public RefCounted<OffHeapInt> {
 326 public:
 327     static RefPtr<OffHeapInt> create(int x)
 328     {
 329         return adoptRef(new OffHeapInt(x));
 330     }
 331
 332     virtual ~OffHeapInt()
 333     {
 334         ++s_destructorCalls;
 335     }
 336
 337     static int s_destructorCalls;
 338
 339     int value() const { return m_x; }
 340
 341     bool operator==(const OffHeapInt& other) const { return other.value() == value(); }
 342
 343     unsigned hash() { return IntHash<int>::hash(m_x); }
 344
 345 protected:
 346     OffHeapInt(int x) : m_x(x) { }
 347
 348 private:
 349     OffHeapInt();
 350     int m_x;
 351 };
 352
 353 USED_FROM_MULTIPLE_THREADS(IntWrapper);
 354
 355 int IntWrapper::s_destructorCalls = 0;
 356 int OffHeapInt::s_destructorCalls = 0;
 357
 358 class ThreadedTesterBase {
 359 protected:
 360     static void test(ThreadedTesterBase* tester)
 361     {
 362         for (int i = 0; i < numberOfThreads; i++)
 363             createThread(&threadFunc, tester, "testing thread");
 364         while (tester->m_threadsToFinish) {
 365             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 366             yield();
 367         }
 368         delete tester;
 369     }
 370
 371     virtual void runThread() = 0;
 372
 373 protected:
 374     static const int numberOfThreads = 10;
 375     static const int gcPerThread = 5;
 376     static const int numberOfAllocations = 50;
 377
 378     ThreadedTesterBase() : m_gcCount(0), m_threadsToFinish(numberOfThreads)
 379     {
 380     }
 381
 382     virtual ~ThreadedTesterBase()
 383     {
 384     }
 385
 386     inline bool done() const { return m_gcCount >= numberOfThreads * gcPerThread; }
 387
 388     volatile int m_gcCount;
 389     volatile int m_threadsToFinish;
 390
 391 private:
 392     static void threadFunc(void* data)
 393     {
 394         reinterpret_cast<ThreadedTesterBase*>(data)->runThread();
 395     }
 396 };
 397
 398 class ThreadedHeapTester : public ThreadedTesterBase {
 399 public:
 400     static void test()
 401     {
 402         ThreadedTesterBase::test(new ThreadedHeapTester);
 403     }
 404
 405 protected:
 406     virtual void runThread() OVERRIDE
 407     {
 408         ThreadState::attach();
 409
 410         int gcCount = 0;
 411         while (!done()) {
 412             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 413             {
 414                 Persistent<IntWrapper> wrapper;
 415
 416                 typedef Persistent<IntWrapper, GlobalPersistents> GlobalIntWrapperPersistent;
 417                 OwnPtr<GlobalIntWrapperPersistent> globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 418
 419                 for (int i = 0; i < numberOfAllocations; i++) {
 420                     wrapper = IntWrapper::create(0x0bbac0de);
 421                     if (!(i % 10)) {
 422                         globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 423                     }
 424                     ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 425                     yield();
 426                 }
 427
 428                 if (gcCount < gcPerThread) {
 429                     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 430                     gcCount++;
 431                     atomicIncrement(&m_gcCount);
 432                 }
 433
 434                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 435                 EXPECT_EQ(wrapper->value(), 0x0bbac0de);
 436                 EXPECT_EQ((*globalPersistent)->value(), 0x0ed0cabb);
 437             }
 438             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 439             yield();
 440         }
 441         ThreadState::detach();
 442         atomicDecrement(&m_threadsToFinish);
 443     }
 444 };
 445
 446 class ThreadedWeaknessTester : public ThreadedTesterBase {
 447 public:
 448     static void test()
 449     {
 450         ThreadedTesterBase::test(new ThreadedWeaknessTester);
 451     }
 452
 453 private:
 454     virtual void runThread() OVERRIDE
 455     {
 456         ThreadState::attach();
 457
 458         int gcCount = 0;
 459         while (!done()) {
 460             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 461             {
 462                 Persistent<HeapHashMap<ThreadMarker, WeakMember<IntWrapper> > > weakMap = new HeapHashMap<ThreadMarker, WeakMember<IntWrapper> >;
 463                 PersistentHeapHashMap<ThreadMarker, WeakMember<IntWrapper> > weakMap2;
 464
 465                 for (int i = 0; i < numberOfAllocations; i++) {
 466                     weakMap->add(static_cast<unsigned>(i), IntWrapper::create(0));
 467                     weakMap2.add(static_cast<unsigned>(i), IntWrapper::create(0));
 468                     ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 469                     yield();
 470                 }
 471
 472                 if (gcCount < gcPerThread) {
 473                     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 474                     gcCount++;
 475                     atomicIncrement(&m_gcCount);
 476                 }
 477
 478                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 479                 EXPECT_TRUE(weakMap->isEmpty());
 480                 EXPECT_TRUE(weakMap2.isEmpty());
 481             }
 482             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 483             yield();
 484         }
 485         ThreadState::detach();
 486         atomicDecrement(&m_threadsToFinish);
 487     }
 488 };
 489
 490 // The accounting for memory includes the memory used by rounding up object
 491 // sizes. This is done in a different way on 32 bit and 64 bit, so we have to
 492 // have some slack in the tests.
 493 template<typename T>
 494 void CheckWithSlack(T expected, T actual, int slack)
 495 {
 496     EXPECT_LE(expected, actual);
 497     EXPECT_GE((intptr_t)expected + slack, (intptr_t)actual);
 498 }
 499
 500 class TraceCounter : public GarbageCollectedFinalized<TraceCounter> {
 501 public:
 502     static TraceCounter* create()
 503     {
 504         return new TraceCounter();
 505     }
 506
 507     void trace(Visitor*) { m_traceCount++; }
 508
 509     int traceCount() { return m_traceCount; }
 510
 511 private:
 512     TraceCounter()
 513         : m_traceCount(0)
 514     {
 515     }
 516
 517     int m_traceCount;
 518 };
 519
 520 class ClassWithMember : public GarbageCollected<ClassWithMember> {
 521 public:
 522     static ClassWithMember* create()
 523     {
 524         return new ClassWithMember();
 525     }
 526
 527     void trace(Visitor* visitor)
 528     {
 529         EXPECT_TRUE(visitor->isMarked(this));
 530         if (!traceCount())
 531             EXPECT_FALSE(visitor->isMarked(m_traceCounter));
 532         else
 533             EXPECT_TRUE(visitor->isMarked(m_traceCounter));
 534
 535         visitor->trace(m_traceCounter);
 536     }
 537
 538     int traceCount() { return m_traceCounter->traceCount(); }
 539
 540 private:
 541     ClassWithMember()
 542         : m_traceCounter(TraceCounter::create())
 543     { }
 544
 545     Member<TraceCounter> m_traceCounter;
 546 };
 547
 548 class SimpleFinalizedObject : public GarbageCollectedFinalized<SimpleFinalizedObject> {
 549 public:
 550     static SimpleFinalizedObject* create()
 551     {
 552         return new SimpleFinalizedObject();
 553     }
 554
 555     ~SimpleFinalizedObject()
 556     {
 557         ++s_destructorCalls;
 558     }
 559
 560     static int s_destructorCalls;
 561
 562     void trace(Visitor*) { }
 563
 564 private:
 565     SimpleFinalizedObject() { }
 566 };
 567
 568 int SimpleFinalizedObject::s_destructorCalls = 0;
 569
 570 class TestTypedHeapClass : public GarbageCollected<TestTypedHeapClass> {
 571 public:
 572     static TestTypedHeapClass* create()
 573     {
 574         return new TestTypedHeapClass();
 575     }
 576
 577     void trace(Visitor*) { }
 578
 579 private:
 580     TestTypedHeapClass() { }
 581 };
 582
 583 class Bar : public GarbageCollectedFinalized<Bar> {
 584 public:
 585     static Bar* create()
 586     {
 587         return new Bar();
 588     }
 589
 590     void finalizeGarbageCollectedObject()
 591     {
 592         EXPECT_TRUE(m_magic == magic);
 593         m_magic = 0;
 594         s_live--;
 595     }
 596     bool hasBeenFinalized() const { return !m_magic; }
 597
 598     virtual void trace(Visitor* visitor) { }
 599     static unsigned s_live;
 600
 601 protected:
 602     static const int magic = 1337;
 603     int m_magic;
 604
 605     Bar()
 606         : m_magic(magic)
 607     {
 608         s_live++;
 609     }
 610 };
 611
 612 unsigned Bar::s_live = 0;
 613
 614 class Baz : public GarbageCollected<Baz> {
 615 public:
 616     static Baz* create(Bar* bar)
 617     {
 618         return new Baz(bar);
 619     }
 620
 621     void trace(Visitor* visitor)
 622     {
 623         visitor->trace(m_bar);
 624     }
 625
 626     void clear() { m_bar.release(); }
 627
 628     // willFinalize is called by FinalizationObserver.
 629     void willFinalize()
 630     {
 631         EXPECT_TRUE(!m_bar->hasBeenFinalized());
 632     }
 633
 634 private:
 635     explicit Baz(Bar* bar)
 636         : m_bar(bar)
 637     {
 638     }
 639
 640     Member<Bar> m_bar;
 641 };
 642
 643 class Foo : public Bar {
 644 public:
 645     static Foo* create(Bar* bar)
 646     {
 647         return new Foo(bar);
 648     }
 649
 650     static Foo* create(Foo* foo)
 651     {
 652         return new Foo(foo);
 653     }
 654
 655     virtual void trace(Visitor* visitor) OVERRIDE
 656     {
 657         if (m_pointsToFoo)
 658             visitor->mark(static_cast<Foo*>(m_bar));
 659         else
 660             visitor->mark(m_bar);
 661     }
 662
 663 private:
 664     Foo(Bar* bar)
 665         : Bar()
 666         , m_bar(bar)
 667         , m_pointsToFoo(false)
 668     {
 669     }
 670
 671     Foo(Foo* foo)
 672         : Bar()
 673         , m_bar(foo)
 674         , m_pointsToFoo(true)
 675     {
 676     }
 677
 678     Bar* m_bar;
 679     bool m_pointsToFoo;
 680 };
 681
 682 class Bars : public Bar {
 683 public:
 684     static Bars* create()
 685     {
 686         return new Bars();
 687     }
 688
 689     virtual void trace(Visitor* visitor) OVERRIDE
 690     {
 691         for (unsigned i = 0; i < m_width; i++)
 692             visitor->trace(m_bars[i]);
 693     }
 694
 695     unsigned getWidth() const
 696     {
 697         return m_width;
 698     }
 699
 700     static const unsigned width = 7500;
 701 private:
 702     Bars() : m_width(0)
 703     {
 704         for (unsigned i = 0; i < width; i++) {
 705             m_bars[i] = Bar::create();
 706             m_width++;
 707         }
 708     }
 709
 710     unsigned m_width;
 711     Member<Bar> m_bars[width];
 712 };
 713
 714 class ConstructorAllocation : public GarbageCollected<ConstructorAllocation> {
 715 public:
 716     static ConstructorAllocation* create() { return new ConstructorAllocation(); }
 717
 718     void trace(Visitor* visitor) { visitor->trace(m_intWrapper); }
 719
 720 private:
 721     ConstructorAllocation()
 722     {
 723         m_intWrapper = IntWrapper::create(42);
 724     }
 725
 726     Member<IntWrapper> m_intWrapper;
 727 };
 728
 729 class LargeObject : public GarbageCollectedFinalized<LargeObject> {
 730 public:
 731     ~LargeObject()
 732     {
 733         s_destructorCalls++;
 734     }
 735     static LargeObject* create() { return new LargeObject(); }
 736     char get(size_t i) { return m_data[i]; }
 737     void set(size_t i, char c) { m_data[i] = c; }
 738     size_t length() { return s_length; }
 739     void trace(Visitor* visitor)
 740     {
 741         visitor->trace(m_intWrapper);
 742     }
 743     static int s_destructorCalls;
 744
 745 private:
 746     static const size_t s_length = 1024*1024;
 747     LargeObject()
 748     {
 749         m_intWrapper = IntWrapper::create(23);
 750     }
 751     Member<IntWrapper> m_intWrapper;
 752     char m_data[s_length];
 753 };
 754
 755 int LargeObject::s_destructorCalls = 0;
 756
 757 class RefCountedAndGarbageCollected : public RefCountedGarbageCollected<RefCountedAndGarbageCollected> {
 758 public:
 759     static PassRefPtr<RefCountedAndGarbageCollected> create()
 760     {
 761         return adoptRef(new RefCountedAndGarbageCollected());
 762     }
 763
 764     ~RefCountedAndGarbageCollected()
 765     {
 766         ++s_destructorCalls;
 767     }
 768
 769     // These are here with their default implementations so you can break in
 770     // them in the debugger.
 771     void ref() { RefCountedGarbageCollected<RefCountedAndGarbageCollected>::ref(); }
 772     void deref() { RefCountedGarbageCollected<RefCountedAndGarbageCollected>::deref(); }
 773
 774     void trace(Visitor*) { }
 775
 776     static int s_destructorCalls;
 777
 778 private:
 779     RefCountedAndGarbageCollected()
 780     {
 781     }
 782 };
 783
 784 int RefCountedAndGarbageCollected::s_destructorCalls = 0;
 785
 786 class RefCountedAndGarbageCollected2 : public HeapTestOtherSuperClass, public RefCountedGarbageCollected<RefCountedAndGarbageCollected2> {
 787 public:
 788     static RefCountedAndGarbageCollected2* create()
 789     {
 790         return adoptRefCountedGarbageCollected(new RefCountedAndGarbageCollected2());
 791     }
 792
 793     ~RefCountedAndGarbageCollected2()
 794     {
 795         ++s_destructorCalls;
 796     }
 797
 798     void trace(Visitor*) { }
 799
 800     static int s_destructorCalls;
 801
 802 private:
 803     RefCountedAndGarbageCollected2()
 804     {
 805     }
 806 };
 807
 808 int RefCountedAndGarbageCollected2::s_destructorCalls = 0;
 809
 810 #define DEFINE_VISITOR_METHODS(Type)                                       \
 811     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
 812     {                                                                      \
 813         mark(object);                                                      \
 814     }                                                                      \
 815
 816 class RefCountedGarbageCollectedVisitor : public CountingVisitor {
 817 public:
 818     RefCountedGarbageCollectedVisitor(int expected, void** objects)
 819         : m_count(0)
 820         , m_expectedCount(expected)
 821         , m_expectedObjects(objects)
 822     {
 823     }
 824
 825     void mark(const void* ptr) { markNoTrace(ptr); }
 826
 827     virtual void markNoTrace(const void* ptr)
 828     {
 829         if (!ptr)
 830             return;
 831         if (m_count < m_expectedCount)
 832             EXPECT_TRUE(expectedObject(ptr));
 833         else
 834             EXPECT_FALSE(expectedObject(ptr));
 835         m_count++;
 836     }
 837
 838     virtual void mark(const void* ptr, TraceCallback) OVERRIDE
 839     {
 840         mark(ptr);
 841     }
 842
 843     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
 844     {
 845         mark(header->payload());
 846     }
 847
 848     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 849     {
 850         mark(header->payload());
 851     }
 852
 853     bool validate() { return m_count >= m_expectedCount; }
 854     void reset() { m_count = 0; }
 855
 856     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 857
 858 private:
 859     bool expectedObject(const void* ptr)
 860     {
 861         for (int i = 0; i < m_expectedCount; i++) {
 862             if (m_expectedObjects[i] == ptr)
 863                 return true;
 864         }
 865         return false;
 866     }
 867
 868     int m_count;
 869     int m_expectedCount;
 870     void** m_expectedObjects;
 871 };
 872
 873 #undef DEFINE_VISITOR_METHODS
 874
 875 class Weak : public Bar {
 876 public:
 877     static Weak* create(Bar* strong, Bar* weak)
 878     {
 879         return new Weak(strong, weak);
 880     }
 881
 882     virtual void trace(Visitor* visitor) OVERRIDE
 883     {
 884         visitor->trace(m_strongBar);
 885         visitor->registerWeakMembers(this, zapWeakMembers);
 886     }
 887
 888     static void zapWeakMembers(Visitor* visitor, void* self)
 889     {
 890         reinterpret_cast<Weak*>(self)->zapWeakMembers(visitor);
 891     }
 892
 893     bool strongIsThere() { return !!m_strongBar; }
 894     bool weakIsThere() { return !!m_weakBar; }
 895
 896 private:
 897     Weak(Bar* strongBar, Bar* weakBar)
 898         : Bar()
 899         , m_strongBar(strongBar)
 900         , m_weakBar(weakBar)
 901     {
 902     }
 903
 904     void zapWeakMembers(Visitor* visitor)
 905     {
 906         if (!visitor->isAlive(m_weakBar))
 907             m_weakBar = 0;
 908     }
 909
 910     Member<Bar> m_strongBar;
 911     Bar* m_weakBar;
 912 };
 913
 914 class WithWeakMember : public Bar {
 915 public:
 916     static WithWeakMember* create(Bar* strong, Bar* weak)
 917     {
 918         return new WithWeakMember(strong, weak);
 919     }
 920
 921     virtual void trace(Visitor* visitor) OVERRIDE
 922     {
 923         visitor->trace(m_strongBar);
 924         visitor->trace(m_weakBar);
 925     }
 926
 927     bool strongIsThere() { return !!m_strongBar; }
 928     bool weakIsThere() { return !!m_weakBar; }
 929
 930 private:
 931     WithWeakMember(Bar* strongBar, Bar* weakBar)
 932         : Bar()
 933         , m_strongBar(strongBar)
 934         , m_weakBar(weakBar)
 935     {
 936     }
 937
 938     Member<Bar> m_strongBar;
 939     WeakMember<Bar> m_weakBar;
 940 };
 941
 942 class Observable : public GarbageCollectedFinalized<Observable> {
 943 public:
 944     static Observable* create(Bar* bar) { return new Observable(bar);  }
 945     ~Observable() { m_wasDestructed = true; }
 946     void trace(Visitor* visitor) { visitor->trace(m_bar); }
 947
 948     // willFinalize is called by FinalizationObserver. willFinalize can touch
 949     // other on-heap objects.
 950     void willFinalize()
 951     {
 952         EXPECT_FALSE(m_wasDestructed);
 953         EXPECT_FALSE(m_bar->hasBeenFinalized());
 954     }
 955
 956 private:
 957     explicit Observable(Bar* bar)
 958         : m_bar(bar)
 959         , m_wasDestructed(false)
 960     {
 961     }
 962
 963     Member<Bar> m_bar;
 964     bool m_wasDestructed;
 965 };
 966
 967 template <typename T> class FinalizationObserver : public GarbageCollected<FinalizationObserver<T> > {
 968 public:
 969     static FinalizationObserver* create(T* data) { return new FinalizationObserver(data); }
 970     bool didCallWillFinalize() const { return m_didCallWillFinalize; }
 971
 972     void trace(Visitor* visitor)
 973     {
 974         visitor->registerWeakMembers(this, zapWeakMembers);
 975     }
 976
 977 private:
 978     FinalizationObserver(T* data)
 979         : m_data(data)
 980         , m_didCallWillFinalize(false)
 981     {
 982     }
 983
 984     static void zapWeakMembers(Visitor* visitor, void* self)
 985     {
 986         FinalizationObserver* o = reinterpret_cast<FinalizationObserver*>(self);
 987         if (o->m_data && !visitor->isAlive(o->m_data)) {
 988             o->m_data->willFinalize();
 989             o->m_data = nullptr;
 990             o->m_didCallWillFinalize = true;
 991         }
 992     }
 993
 994     WeakMember<T> m_data;
 995     bool m_didCallWillFinalize;
 996 };
 997
 998 class FinalizationObserverWithHashMap {
 999 public:
1000     typedef HeapHashMap<WeakMember<Observable>, OwnPtr<FinalizationObserverWithHashMap> > ObserverMap;
1001
1002     explicit FinalizationObserverWithHashMap(Observable& target) : m_target(target) { }
1003     ~FinalizationObserverWithHashMap()
1004     {
1005         m_target.willFinalize();
1006         s_didCallWillFinalize = true;
1007     }
1008
1009     static ObserverMap& observe(Observable& target)
1010     {
1011         ObserverMap& map = observers();
1012         ObserverMap::AddResult result = map.add(&target, nullptr);
1013         if (result.isNewEntry)
1014             result.storedValue->value = adoptPtr(new FinalizationObserverWithHashMap(target));
1015         else
1016             ASSERT(result.storedValue->value);
1017         return map;
1018     }
1019
1020     static bool s_didCallWillFinalize;
1021
1022 private:
1023     static ObserverMap& observers()
1024     {
1025         DEFINE_STATIC_LOCAL(Persistent<ObserverMap>, observerMap, ());
1026         if (!observerMap)
1027             observerMap = new ObserverMap();
1028         return *observerMap;
1029     }
1030
1031     Observable& m_target;
1032 };
1033
1034 bool FinalizationObserverWithHashMap::s_didCallWillFinalize = false;
1035
1036 class SuperClass;
1037
1038 class PointsBack : public RefCountedWillBeGarbageCollectedFinalized<PointsBack> {
1039 public:
1040     static PassRefPtrWillBeRawPtr<PointsBack> create()
1041     {
1042         return adoptRefWillBeNoop(new PointsBack());
1043     }
1044
1045     ~PointsBack()
1046     {
1047         --s_aliveCount;
1048     }
1049
1050     void setBackPointer(SuperClass* backPointer)
1051     {
1052         m_backPointer = backPointer;
1053     }
1054
1055     SuperClass* backPointer() const { return m_backPointer; }
1056
1057     void trace(Visitor* visitor)
1058     {
1059 #if ENABLE_OILPAN
1060         visitor->trace(m_backPointer);
1061 #endif
1062     }
1063
1064     static int s_aliveCount;
1065 private:
1066     PointsBack() : m_backPointer(nullptr)
1067     {
1068         ++s_aliveCount;
1069     }
1070
1071     RawPtrWillBeWeakMember<SuperClass> m_backPointer;
1072 };
1073
1074 int PointsBack::s_aliveCount = 0;
1075
1076 class SuperClass : public RefCountedWillBeGarbageCollectedFinalized<SuperClass> {
1077 public:
1078     static PassRefPtrWillBeRawPtr<SuperClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1079     {
1080         return adoptRefWillBeNoop(new SuperClass(pointsBack));
1081     }
1082
1083     virtual ~SuperClass()
1084     {
1085 #if !ENABLE_OILPAN
1086         m_pointsBack->setBackPointer(0);
1087 #endif
1088         --s_aliveCount;
1089     }
1090
1091     void doStuff(PassRefPtrWillBeRawPtr<SuperClass> targetPass, PointsBack* pointsBack, int superClassCount)
1092     {
1093         RefPtrWillBeRawPtr<SuperClass> target = targetPass;
1094         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1095         EXPECT_EQ(pointsBack, target->pointsBack());
1096         EXPECT_EQ(superClassCount, SuperClass::s_aliveCount);
1097     }
1098
1099     virtual void trace(Visitor* visitor)
1100     {
1101 #if ENABLE_OILPAN
1102         visitor->trace(m_pointsBack);
1103 #endif
1104     }
1105
1106     PointsBack* pointsBack() const { return m_pointsBack.get(); }
1107
1108     static int s_aliveCount;
1109 protected:
1110     explicit SuperClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1111         : m_pointsBack(pointsBack)
1112     {
1113         m_pointsBack->setBackPointer(this);
1114         ++s_aliveCount;
1115     }
1116
1117 private:
1118     RefPtrWillBeMember<PointsBack> m_pointsBack;
1119 };
1120
1121 int SuperClass::s_aliveCount = 0;
1122 class SubData : public NoBaseWillBeGarbageCollectedFinalized<SubData> {
1123 public:
1124     SubData() { ++s_aliveCount; }
1125     ~SubData() { --s_aliveCount; }
1126
1127     void trace(Visitor*) { }
1128
1129     static int s_aliveCount;
1130 };
1131
1132 int SubData::s_aliveCount = 0;
1133
1134 class SubClass : public SuperClass {
1135 public:
1136     static PassRefPtrWillBeRawPtr<SubClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1137     {
1138         return adoptRefWillBeNoop(new SubClass(pointsBack));
1139     }
1140
1141     virtual ~SubClass()
1142     {
1143         --s_aliveCount;
1144     }
1145
1146     virtual void trace(Visitor* visitor)
1147     {
1148 #if ENABLE_OILPAN
1149         SuperClass::trace(visitor);
1150         visitor->trace(m_data);
1151 #endif
1152     }
1153
1154     static int s_aliveCount;
1155 private:
1156     explicit SubClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1157         : SuperClass(pointsBack)
1158         , m_data(adoptPtrWillBeNoop(new SubData()))
1159     {
1160         ++s_aliveCount;
1161     }
1162
1163 private:
1164     OwnPtrWillBeMember<SubData> m_data;
1165 };
1166
1167 int SubClass::s_aliveCount = 0;
1168
1169 class TransitionRefCounted : public RefCountedWillBeRefCountedGarbageCollected<TransitionRefCounted> {
1170 public:
1171     static PassRefPtrWillBeRawPtr<TransitionRefCounted> create()
1172     {
1173         return adoptRefWillBeRefCountedGarbageCollected(new TransitionRefCounted());
1174     }
1175
1176     ~TransitionRefCounted()
1177     {
1178         --s_aliveCount;
1179     }
1180
1181     void trace(Visitor* visitor) { }
1182
1183     static int s_aliveCount;
1184
1185 private:
1186     TransitionRefCounted()
1187     {
1188         ++s_aliveCount;
1189     }
1190 };
1191
1192 int TransitionRefCounted::s_aliveCount = 0;
1193
1194 class Mixin : public GarbageCollectedMixin {
1195 public:
1196     virtual void trace(Visitor* visitor) { }
1197
1198     virtual char getPayload(int i) { return m_padding[i]; }
1199
1200 protected:
1201     int m_padding[8];
1202 };
1203
1204 class UseMixin : public SimpleObject, public Mixin {
1205     USING_GARBAGE_COLLECTED_MIXIN(UseMixin)
1206 public:
1207     static UseMixin* create()
1208     {
1209         return new UseMixin();
1210     }
1211
1212     static int s_traceCount;
1213     virtual void trace(Visitor* visitor)
1214     {
1215         SimpleObject::trace(visitor);
1216         Mixin::trace(visitor);
1217         ++s_traceCount;
1218     }
1219
1220 private:
1221     UseMixin()
1222     {
1223         s_traceCount = 0;
1224     }
1225 };
1226
1227 int UseMixin::s_traceCount = 0;
1228
1229 class VectorObject {
1230     ALLOW_ONLY_INLINE_ALLOCATION();
1231 public:
1232     VectorObject()
1233     {
1234         m_value = SimpleFinalizedObject::create();
1235     }
1236
1237     void trace(Visitor* visitor)
1238     {
1239         visitor->trace(m_value);
1240     }
1241
1242 private:
1243     Member<SimpleFinalizedObject> m_value;
1244 };
1245
1246 class VectorObjectInheritedTrace : public VectorObject { };
1247
1248 class VectorObjectNoTrace {
1249     ALLOW_ONLY_INLINE_ALLOCATION();
1250 public:
1251     VectorObjectNoTrace()
1252     {
1253         m_value = SimpleFinalizedObject::create();
1254     }
1255
1256 private:
1257     Member<SimpleFinalizedObject> m_value;
1258 };
1259
1260 class TerminatedArrayItem {
1261     ALLOW_ONLY_INLINE_ALLOCATION();
1262 public:
1263     TerminatedArrayItem(IntWrapper* payload) : m_payload(payload), m_isLast(false) { }
1264
1265     void trace(Visitor* visitor) { visitor->trace(m_payload); }
1266
1267     bool isLastInArray() const { return m_isLast; }
1268     void setLastInArray(bool value) { m_isLast = value; }
1269
1270     IntWrapper* payload() const { return m_payload; }
1271
1272 private:
1273     Member<IntWrapper> m_payload;
1274     bool m_isLast;
1275 };
1276
1277 } // WebCore namespace
1278
1279 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(WebCore::VectorObject);
1280 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(WebCore::VectorObjectInheritedTrace);
1281 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(WebCore::VectorObjectNoTrace);
1282
1283 namespace WebCore {
1284
1285 class OneKiloByteObject : public GarbageCollectedFinalized<OneKiloByteObject> {
1286 public:
1287     ~OneKiloByteObject() { s_destructorCalls++; }
1288     char* data() { return m_data; }
1289     void trace(Visitor* visitor) { }
1290     static int s_destructorCalls;
1291
1292 private:
1293     static const size_t s_length = 1024;
1294     char m_data[s_length];
1295 };
1296
1297 int OneKiloByteObject::s_destructorCalls = 0;
1298
1299 class DynamicallySizedObject : public GarbageCollected<DynamicallySizedObject> {
1300 public:
1301     static DynamicallySizedObject* create(size_t size)
1302     {
1303         void* slot = Heap::allocate<DynamicallySizedObject>(size);
1304         return new (slot) DynamicallySizedObject();
1305     }
1306
1307     void* operator new(std::size_t, void* location)
1308     {
1309         return location;
1310     }
1311
1312     uint8_t get(int i)
1313     {
1314         return *(reinterpret_cast<uint8_t*>(this) + i);
1315     }
1316
1317     void trace(Visitor*) { }
1318
1319 private:
1320     DynamicallySizedObject() { }
1321 };
1322
1323 class FinalizationAllocator : public GarbageCollectedFinalized<FinalizationAllocator> {
1324 public:
1325     FinalizationAllocator(Persistent<IntWrapper>* wrapper)
1326         : m_wrapper(wrapper)
1327     {
1328     }
1329
1330     ~FinalizationAllocator()
1331     {
1332         for (int i = 0; i < 10; ++i)
1333             *m_wrapper = IntWrapper::create(42);
1334         for (int i = 0; i < 512; ++i)
1335             new OneKiloByteObject();
1336     }
1337
1338     void trace(Visitor*) { }
1339
1340 private:
1341     Persistent<IntWrapper>* m_wrapper;
1342 };
1343
1344 TEST(HeapTest, Transition)
1345 {
1346     {
1347         RefPtr<TransitionRefCounted> refCounted = TransitionRefCounted::create();
1348         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
1349         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1350         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
1351     }
1352     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1353     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
1354
1355     RefPtrWillBePersistent<PointsBack> pointsBack1 = PointsBack::create();
1356     RefPtrWillBePersistent<PointsBack> pointsBack2 = PointsBack::create();
1357     RefPtrWillBePersistent<SuperClass> superClass = SuperClass::create(pointsBack1);
1358     RefPtrWillBePersistent<SubClass> subClass = SubClass::create(pointsBack2);
1359     EXPECT_EQ(2, PointsBack::s_aliveCount);
1360     EXPECT_EQ(2, SuperClass::s_aliveCount);
1361     EXPECT_EQ(1, SubClass::s_aliveCount);
1362     EXPECT_EQ(1, SubData::s_aliveCount);
1363
1364     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1365     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
1366     EXPECT_EQ(2, PointsBack::s_aliveCount);
1367     EXPECT_EQ(2, SuperClass::s_aliveCount);
1368     EXPECT_EQ(1, SubClass::s_aliveCount);
1369     EXPECT_EQ(1, SubData::s_aliveCount);
1370
1371     superClass->doStuff(superClass.release(), pointsBack1.get(), 2);
1372     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1373     EXPECT_EQ(2, PointsBack::s_aliveCount);
1374     EXPECT_EQ(1, SuperClass::s_aliveCount);
1375     EXPECT_EQ(1, SubClass::s_aliveCount);
1376     EXPECT_EQ(1, SubData::s_aliveCount);
1377     EXPECT_EQ(0, pointsBack1->backPointer());
1378
1379     pointsBack1.release();
1380     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1381     EXPECT_EQ(1, PointsBack::s_aliveCount);
1382     EXPECT_EQ(1, SuperClass::s_aliveCount);
1383     EXPECT_EQ(1, SubClass::s_aliveCount);
1384     EXPECT_EQ(1, SubData::s_aliveCount);
1385
1386     subClass->doStuff(subClass.release(), pointsBack2.get(), 1);
1387     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1388     EXPECT_EQ(1, PointsBack::s_aliveCount);
1389     EXPECT_EQ(0, SuperClass::s_aliveCount);
1390     EXPECT_EQ(0, SubClass::s_aliveCount);
1391     EXPECT_EQ(0, SubData::s_aliveCount);
1392     EXPECT_EQ(0, pointsBack2->backPointer());
1393
1394     pointsBack2.release();
1395     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1396     EXPECT_EQ(0, PointsBack::s_aliveCount);
1397     EXPECT_EQ(0, SuperClass::s_aliveCount);
1398     EXPECT_EQ(0, SubClass::s_aliveCount);
1399     EXPECT_EQ(0, SubData::s_aliveCount);
1400
1401     EXPECT_TRUE(superClass == subClass);
1402 }
1403
1404 TEST(HeapTest, Threading)
1405 {
1406     ThreadedHeapTester::test();
1407 }
1408
1409 TEST(HeapTest, ThreadedWeakness)
1410 {
1411     ThreadedWeaknessTester::test();
1412 }
1413
1414 TEST(HeapTest, BasicFunctionality)
1415 {
1416     HeapStats heapStats;
1417     clearOutOldGarbage(&heapStats);
1418     {
1419         size_t slack = 0;
1420
1421         // When the test starts there may already have been leaked some memory
1422         // on the heap, so we establish a base line.
1423         size_t baseLevel = heapStats.totalObjectSpace();
1424         bool testPagesAllocated = !baseLevel;
1425         if (testPagesAllocated)
1426             EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1427
1428         // This allocates objects on the general heap which should add a page of memory.
1429         DynamicallySizedObject* alloc32 = DynamicallySizedObject::create(32);
1430         slack += 4;
1431         memset(alloc32, 40, 32);
1432         DynamicallySizedObject* alloc64 = DynamicallySizedObject::create(64);
1433         slack += 4;
1434         memset(alloc64, 27, 64);
1435
1436         size_t total = 96;
1437
1438         getHeapStats(&heapStats);
1439         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1440         if (testPagesAllocated)
1441             EXPECT_EQ(heapStats.totalAllocatedSpace(), blinkPageSize);
1442
1443         CheckWithSlack(alloc32 + 32 + sizeof(HeapObjectHeader), alloc64, slack);
1444
1445         EXPECT_EQ(alloc32->get(0), 40);
1446         EXPECT_EQ(alloc32->get(31), 40);
1447         EXPECT_EQ(alloc64->get(0), 27);
1448         EXPECT_EQ(alloc64->get(63), 27);
1449
1450         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1451
1452         EXPECT_EQ(alloc32->get(0), 40);
1453         EXPECT_EQ(alloc32->get(31), 40);
1454         EXPECT_EQ(alloc64->get(0), 27);
1455         EXPECT_EQ(alloc64->get(63), 27);
1456     }
1457
1458     clearOutOldGarbage(&heapStats);
1459     size_t total = 0;
1460     size_t slack = 0;
1461     size_t baseLevel = heapStats.totalObjectSpace();
1462     bool testPagesAllocated = !baseLevel;
1463     if (testPagesAllocated)
1464         EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1465
1466     size_t big = 1008;
1467     Persistent<DynamicallySizedObject> bigArea = DynamicallySizedObject::create(big);
1468     total += big;
1469     slack += 4;
1470
1471     size_t persistentCount = 0;
1472     const size_t numPersistents = 100000;
1473     Persistent<DynamicallySizedObject>* persistents[numPersistents];
1474
1475     for (int i = 0; i < 1000; i++) {
1476         size_t size = 128 + i * 8;
1477         total += size;
1478         persistents[persistentCount++] = new Persistent<DynamicallySizedObject>(DynamicallySizedObject::create(size));
1479         slack += 4;
1480         getHeapStats(&heapStats);
1481         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1482         if (testPagesAllocated)
1483             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1484     }
1485
1486     {
1487         DynamicallySizedObject* alloc32b(DynamicallySizedObject::create(32));
1488         slack += 4;
1489         memset(alloc32b, 40, 32);
1490         DynamicallySizedObject* alloc64b(DynamicallySizedObject::create(64));
1491         slack += 4;
1492         memset(alloc64b, 27, 64);
1493         EXPECT_TRUE(alloc32b != alloc64b);
1494
1495         total += 96;
1496         getHeapStats(&heapStats);
1497         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1498         if (testPagesAllocated)
1499             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1500     }
1501
1502     clearOutOldGarbage(&heapStats);
1503     total -= 96;
1504     slack -= 8;
1505     if (testPagesAllocated)
1506         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1507
1508     DynamicallySizedObject* bigAreaRaw = bigArea;
1509     // Clear the persistent, so that the big area will be garbage collected.
1510     bigArea.release();
1511     clearOutOldGarbage(&heapStats);
1512
1513     total -= big;
1514     slack -= 4;
1515     getHeapStats(&heapStats);
1516     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1517     if (testPagesAllocated)
1518         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1519
1520     // Endless loop unless we eventually get the memory back that we just freed.
1521     while (true) {
1522         Persistent<DynamicallySizedObject>* alloc = new Persistent<DynamicallySizedObject>(DynamicallySizedObject::create(big / 2));
1523         slack += 4;
1524         persistents[persistentCount++] = alloc;
1525         EXPECT_LT(persistentCount, numPersistents);
1526         total += big / 2;
1527         if (bigAreaRaw == alloc->get())
1528             break;
1529     }
1530
1531     getHeapStats(&heapStats);
1532     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1533     if (testPagesAllocated)
1534         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1535
1536     for (size_t i = 0; i < persistentCount; i++) {
1537         delete persistents[i];
1538         persistents[i] = 0;
1539     }
1540
1541     uint8_t* address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(0, 100));
1542     for (int i = 0; i < 100; i++)
1543         address[i] = i;
1544     address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(address, 100000));
1545     for (int i = 0; i < 100; i++)
1546         EXPECT_EQ(address[i], i);
1547     address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(address, 50));
1548     for (int i = 0; i < 50; i++)
1549         EXPECT_EQ(address[i], i);
1550     // This should be equivalent to free(address).
1551     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<DynamicallySizedObject>(address, 0)), 0ul);
1552     // This should be equivalent to malloc(0).
1553     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<DynamicallySizedObject>(0, 0)), 0ul);
1554 }
1555
1556 TEST(HeapTest, SimpleAllocation)
1557 {
1558     HeapStats initialHeapStats;
1559     clearOutOldGarbage(&initialHeapStats);
1560     EXPECT_EQ(0ul, initialHeapStats.totalObjectSpace());
1561
1562     // Allocate an object in the heap.
1563     HeapAllocatedArray* array = new HeapAllocatedArray();
1564     HeapStats statsAfterAllocation;
1565     getHeapStats(&statsAfterAllocation);
1566     EXPECT_TRUE(statsAfterAllocation.totalObjectSpace() >= sizeof(HeapAllocatedArray));
1567
1568     // Sanity check of the contents in the heap.
1569     EXPECT_EQ(0, array->at(0));
1570     EXPECT_EQ(42, array->at(42));
1571     EXPECT_EQ(0, array->at(128));
1572     EXPECT_EQ(999 % 128, array->at(999));
1573 }
1574
1575 TEST(HeapTest, SimplePersistent)
1576 {
1577     Persistent<TraceCounter> traceCounter = TraceCounter::create();
1578     EXPECT_EQ(0, traceCounter->traceCount());
1579
1580     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1581     EXPECT_EQ(1, traceCounter->traceCount());
1582
1583     Persistent<ClassWithMember> classWithMember = ClassWithMember::create();
1584     EXPECT_EQ(0, classWithMember->traceCount());
1585
1586     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1587     EXPECT_EQ(1, classWithMember->traceCount());
1588     EXPECT_EQ(2, traceCounter->traceCount());
1589 }
1590
1591 TEST(HeapTest, SimpleFinalization)
1592 {
1593     {
1594         Persistent<SimpleFinalizedObject> finalized = SimpleFinalizedObject::create();
1595         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1596         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1597         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1598     }
1599
1600     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1601     EXPECT_EQ(1, SimpleFinalizedObject::s_destructorCalls);
1602 }
1603
1604 TEST(HeapTest, Finalization)
1605 {
1606     {
1607         HeapTestSubClass* t1 = HeapTestSubClass::create();
1608         HeapTestSubClass* t2 = HeapTestSubClass::create();
1609         HeapTestSuperClass* t3 = HeapTestSuperClass::create();
1610         // FIXME(oilpan): Ignore unused variables.
1611         (void)t1;
1612         (void)t2;
1613         (void)t3;
1614     }
1615     // Nothing is marked so the GC should free everything and call
1616     // the finalizer on all three objects.
1617     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1618     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1619     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1620     // Destructors not called again when GCing again.
1621     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1622     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1623     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1624 }
1625
1626 TEST(HeapTest, TypedHeapSanity)
1627 {
1628     // We use TraceCounter for allocating an object on the general heap.
1629     Persistent<TraceCounter> generalHeapObject = TraceCounter::create();
1630     Persistent<TestTypedHeapClass> typedHeapObject = TestTypedHeapClass::create();
1631     EXPECT_NE(pageHeaderAddress(reinterpret_cast<Address>(generalHeapObject.get())),
1632         pageHeaderAddress(reinterpret_cast<Address>(typedHeapObject.get())));
1633 }
1634
1635 TEST(HeapTest, NoAllocation)
1636 {
1637     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1638     {
1639         // Disallow allocation
1640         NoAllocationScope<AnyThread> noAllocationScope;
1641         EXPECT_FALSE(ThreadState::current()->isAllocationAllowed());
1642     }
1643     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1644 }
1645
1646 TEST(HeapTest, Members)
1647 {
1648     Bar::s_live = 0;
1649     {
1650         Persistent<Baz> h1;
1651         Persistent<Baz> h2;
1652         {
1653             h1 = Baz::create(Bar::create());
1654             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1655             EXPECT_EQ(1u, Bar::s_live);
1656             h2 = Baz::create(Bar::create());
1657             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1658             EXPECT_EQ(2u, Bar::s_live);
1659         }
1660         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1661         EXPECT_EQ(2u, Bar::s_live);
1662         h1->clear();
1663         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1664         EXPECT_EQ(1u, Bar::s_live);
1665     }
1666     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1667     EXPECT_EQ(0u, Bar::s_live);
1668 }
1669
1670 TEST(HeapTest, MarkTest)
1671 {
1672     {
1673         Bar::s_live = 0;
1674         Persistent<Bar> bar = Bar::create();
1675         EXPECT_TRUE(ThreadState::current()->contains(bar));
1676         EXPECT_EQ(1u, Bar::s_live);
1677         {
1678             Foo* foo = Foo::create(bar);
1679             EXPECT_TRUE(ThreadState::current()->contains(foo));
1680             EXPECT_EQ(2u, Bar::s_live);
1681             EXPECT_TRUE(reinterpret_cast<Address>(foo) != reinterpret_cast<Address>(bar.get()));
1682             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1683             EXPECT_TRUE(foo != bar); // To make sure foo is kept alive.
1684             EXPECT_EQ(2u, Bar::s_live);
1685         }
1686         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1687         EXPECT_EQ(1u, Bar::s_live);
1688     }
1689     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1690     EXPECT_EQ(0u, Bar::s_live);
1691 }
1692
1693 TEST(HeapTest, DeepTest)
1694 {
1695     const unsigned depth = 100000;
1696     Bar::s_live = 0;
1697     {
1698         Bar* bar = Bar::create();
1699         EXPECT_TRUE(ThreadState::current()->contains(bar));
1700         Foo* foo = Foo::create(bar);
1701         EXPECT_TRUE(ThreadState::current()->contains(foo));
1702         EXPECT_EQ(2u, Bar::s_live);
1703         for (unsigned i = 0; i < depth; i++) {
1704             Foo* foo2 = Foo::create(foo);
1705             foo = foo2;
1706             EXPECT_TRUE(ThreadState::current()->contains(foo));
1707         }
1708         EXPECT_EQ(depth + 2, Bar::s_live);
1709         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1710         EXPECT_TRUE(foo != bar); // To make sure foo and bar are kept alive.
1711         EXPECT_EQ(depth + 2, Bar::s_live);
1712     }
1713     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1714     EXPECT_EQ(0u, Bar::s_live);
1715 }
1716
1717 TEST(HeapTest, WideTest)
1718 {
1719     Bar::s_live = 0;
1720     {
1721         Bars* bars = Bars::create();
1722         unsigned width = Bars::width;
1723         EXPECT_EQ(width + 1, Bar::s_live);
1724         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1725         EXPECT_EQ(width + 1, Bar::s_live);
1726         // Use bars here to make sure that it will be on the stack
1727         // for the conservative stack scan to find.
1728         EXPECT_EQ(width, bars->getWidth());
1729     }
1730     EXPECT_EQ(Bars::width + 1, Bar::s_live);
1731     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1732     EXPECT_EQ(0u, Bar::s_live);
1733 }
1734
1735 TEST(HeapTest, HashMapOfMembers)
1736 {
1737     HeapStats initialHeapSize;
1738     IntWrapper::s_destructorCalls = 0;
1739
1740     clearOutOldGarbage(&initialHeapSize);
1741     {
1742         typedef HeapHashMap<
1743             Member<IntWrapper>,
1744             Member<IntWrapper>,
1745             DefaultHash<Member<IntWrapper> >::Hash,
1746             HashTraits<Member<IntWrapper> >,
1747             HashTraits<Member<IntWrapper> > > HeapObjectIdentityMap;
1748
1749         Persistent<HeapObjectIdentityMap> map = new HeapObjectIdentityMap();
1750
1751         map->clear();
1752         HeapStats afterSetWasCreated;
1753         getHeapStats(&afterSetWasCreated);
1754         EXPECT_TRUE(afterSetWasCreated.totalObjectSpace() > initialHeapSize.totalObjectSpace());
1755
1756         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1757         HeapStats afterGC;
1758         getHeapStats(&afterGC);
1759         EXPECT_EQ(afterGC.totalObjectSpace(), afterSetWasCreated.totalObjectSpace());
1760
1761         // If the additions below cause garbage collections, these
1762         // pointers should be found by conservative stack scanning.
1763         IntWrapper* one(IntWrapper::create(1));
1764         IntWrapper* anotherOne(IntWrapper::create(1));
1765
1766         map->add(one, one);
1767
1768         HeapStats afterOneAdd;
1769         getHeapStats(&afterOneAdd);
1770         EXPECT_TRUE(afterOneAdd.totalObjectSpace() > afterGC.totalObjectSpace());
1771
1772         HeapObjectIdentityMap::iterator it(map->begin());
1773         HeapObjectIdentityMap::iterator it2(map->begin());
1774         ++it;
1775         ++it2;
1776
1777         map->add(anotherOne, one);
1778
1779         // The addition above can cause an allocation of a new
1780         // backing store. We therefore garbage collect before
1781         // taking the heap stats in order to get rid of the old
1782         // backing store. We make sure to not use conservative
1783         // stack scanning as that could find a pointer to the
1784         // old backing.
1785         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1786         HeapStats afterAddAndGC;
1787         getHeapStats(&afterAddAndGC);
1788         EXPECT_TRUE(afterAddAndGC.totalObjectSpace() >= afterOneAdd.totalObjectSpace());
1789
1790         EXPECT_EQ(map->size(), 2u); // Two different wrappings of '1' are distinct.
1791
1792         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1793         EXPECT_TRUE(map->contains(one));
1794         EXPECT_TRUE(map->contains(anotherOne));
1795
1796         IntWrapper* gotten(map->get(one));
1797         EXPECT_EQ(gotten->value(), one->value());
1798         EXPECT_EQ(gotten, one);
1799
1800         HeapStats afterGC2;
1801         getHeapStats(&afterGC2);
1802         EXPECT_EQ(afterGC2.totalObjectSpace(), afterAddAndGC.totalObjectSpace());
1803
1804         IntWrapper* dozen = 0;
1805
1806         for (int i = 1; i < 1000; i++) { // 999 iterations.
1807             IntWrapper* iWrapper(IntWrapper::create(i));
1808             IntWrapper* iSquared(IntWrapper::create(i * i));
1809             map->add(iWrapper, iSquared);
1810             if (i == 12)
1811                 dozen = iWrapper;
1812         }
1813         HeapStats afterAdding1000;
1814         getHeapStats(&afterAdding1000);
1815         EXPECT_TRUE(afterAdding1000.totalObjectSpace() > afterGC2.totalObjectSpace());
1816
1817         IntWrapper* gross(map->get(dozen));
1818         EXPECT_EQ(gross->value(), 144);
1819
1820         // This should clear out junk created by all the adds.
1821         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1822         HeapStats afterGC3;
1823         getHeapStats(&afterGC3);
1824         EXPECT_TRUE(afterGC3.totalObjectSpace() < afterAdding1000.totalObjectSpace());
1825     }
1826
1827     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1828     // The objects 'one', anotherOne, and the 999 other pairs.
1829     EXPECT_EQ(IntWrapper::s_destructorCalls, 2000);
1830     HeapStats afterGC4;
1831     getHeapStats(&afterGC4);
1832     EXPECT_EQ(afterGC4.totalObjectSpace(), initialHeapSize.totalObjectSpace());
1833 }
1834
1835 TEST(HeapTest, NestedAllocation)
1836 {
1837     HeapStats initialHeapSize;
1838     clearOutOldGarbage(&initialHeapSize);
1839     {
1840         Persistent<ConstructorAllocation> constructorAllocation = ConstructorAllocation::create();
1841     }
1842     HeapStats afterFree;
1843     clearOutOldGarbage(&afterFree);
1844     EXPECT_TRUE(initialHeapSize == afterFree);
1845 }
1846
1847 TEST(HeapTest, LargeObjects)
1848 {
1849     HeapStats initialHeapSize;
1850     clearOutOldGarbage(&initialHeapSize);
1851     IntWrapper::s_destructorCalls = 0;
1852     LargeObject::s_destructorCalls = 0;
1853     {
1854         int slack = 8; // LargeObject points to an IntWrapper that is also allocated.
1855         Persistent<LargeObject> object = LargeObject::create();
1856         EXPECT_TRUE(ThreadState::current()->contains(object));
1857         EXPECT_TRUE(ThreadState::current()->contains(reinterpret_cast<char*>(object.get()) + sizeof(LargeObject) - 1));
1858 #if ENABLE(GC_TRACING)
1859         const GCInfo* info = ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()));
1860         EXPECT_NE(reinterpret_cast<const GCInfo*>(0), info);
1861         EXPECT_EQ(info, ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()) + sizeof(LargeObject) - 1));
1862         EXPECT_NE(info, ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()) + sizeof(LargeObject)));
1863         EXPECT_NE(info, ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()) - 1));
1864 #endif
1865         HeapStats afterAllocation;
1866         clearOutOldGarbage(&afterAllocation);
1867         {
1868             object->set(0, 'a');
1869             EXPECT_EQ('a', object->get(0));
1870             object->set(object->length() - 1, 'b');
1871             EXPECT_EQ('b', object->get(object->length() - 1));
1872             size_t expectedObjectSpace = sizeof(LargeObject) + sizeof(IntWrapper);
1873             size_t actualObjectSpace =
1874                 afterAllocation.totalObjectSpace() - initialHeapSize.totalObjectSpace();
1875             CheckWithSlack(expectedObjectSpace, actualObjectSpace, slack);
1876             // There is probably space for the IntWrapper in a heap page without
1877             // allocating extra pages. However, the IntWrapper allocation might cause
1878             // the addition of a heap page.
1879             size_t largeObjectAllocationSize =
1880                 sizeof(LargeObject) + sizeof(LargeHeapObject<FinalizedHeapObjectHeader>) + sizeof(FinalizedHeapObjectHeader);
1881             size_t allocatedSpaceLowerBound =
1882                 initialHeapSize.totalAllocatedSpace() + largeObjectAllocationSize;
1883             size_t allocatedSpaceUpperBound = allocatedSpaceLowerBound + slack + blinkPageSize;
1884             EXPECT_LE(allocatedSpaceLowerBound, afterAllocation.totalAllocatedSpace());
1885             EXPECT_LE(afterAllocation.totalAllocatedSpace(), allocatedSpaceUpperBound);
1886             EXPECT_EQ(0, IntWrapper::s_destructorCalls);
1887             EXPECT_EQ(0, LargeObject::s_destructorCalls);
1888             for (int i = 0; i < 10; i++)
1889                 object = LargeObject::create();
1890         }
1891         HeapStats oneLargeObject;
1892         clearOutOldGarbage(&oneLargeObject);
1893         EXPECT_TRUE(oneLargeObject == afterAllocation);
1894         EXPECT_EQ(10, IntWrapper::s_destructorCalls);
1895         EXPECT_EQ(10, LargeObject::s_destructorCalls);
1896     }
1897     HeapStats backToInitial;
1898     clearOutOldGarbage(&backToInitial);
1899     EXPECT_TRUE(initialHeapSize == backToInitial);
1900     EXPECT_EQ(11, IntWrapper::s_destructorCalls);
1901     EXPECT_EQ(11, LargeObject::s_destructorCalls);
1902     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1903 }
1904
1905 typedef std::pair<Member<IntWrapper>, int> PairWrappedUnwrapped;
1906 typedef std::pair<int, Member<IntWrapper> > PairUnwrappedWrapped;
1907 typedef std::pair<WeakMember<IntWrapper>, Member<IntWrapper> > PairWeakStrong;
1908 typedef std::pair<Member<IntWrapper>, WeakMember<IntWrapper> > PairStrongWeak;
1909 typedef std::pair<WeakMember<IntWrapper>, int> PairWeakUnwrapped;
1910 typedef std::pair<int, WeakMember<IntWrapper> > PairUnwrappedWeak;
1911
1912 class Container : public GarbageCollected<Container> {
1913 public:
1914     static Container* create() { return new Container(); }
1915     HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > map;
1916     HeapHashSet<Member<IntWrapper> > set;
1917     HeapHashSet<Member<IntWrapper> > set2;
1918     HeapHashCountedSet<Member<IntWrapper> > set3;
1919     HeapVector<Member<IntWrapper>, 2> vector;
1920     HeapVector<PairWrappedUnwrapped, 2> vectorWU;
1921     HeapVector<PairUnwrappedWrapped, 2> vectorUW;
1922     HeapDeque<Member<IntWrapper>, 0> deque;
1923     HeapDeque<PairWrappedUnwrapped, 0> dequeWU;
1924     HeapDeque<PairUnwrappedWrapped, 0> dequeUW;
1925     void trace(Visitor* visitor)
1926     {
1927         visitor->trace(map);
1928         visitor->trace(set);
1929         visitor->trace(set2);
1930         visitor->trace(set3);
1931         visitor->trace(vector);
1932         visitor->trace(vectorWU);
1933         visitor->trace(vectorUW);
1934         visitor->trace(deque);
1935         visitor->trace(dequeWU);
1936         visitor->trace(dequeUW);
1937     }
1938 };
1939
1940 struct ShouldBeTraced {
1941     explicit ShouldBeTraced(IntWrapper* wrapper) : m_wrapper(wrapper) { }
1942     void trace(Visitor* visitor) { visitor->trace(m_wrapper); }
1943     Member<IntWrapper> m_wrapper;
1944 };
1945
1946 class OffHeapContainer : public GarbageCollectedFinalized<OffHeapContainer> {
1947 public:
1948     static OffHeapContainer* create() { return new OffHeapContainer(); }
1949
1950     static const int iterations = 300;
1951     static const int deadWrappers = 2700;
1952
1953     OffHeapContainer()
1954     {
1955         for (int i = 0; i < iterations; i++) {
1956             m_deque1.append(ShouldBeTraced(IntWrapper::create(i)));
1957             m_vector1.append(ShouldBeTraced(IntWrapper::create(i)));
1958             m_deque2.append(IntWrapper::create(i));
1959             m_vector2.append(IntWrapper::create(i));
1960             m_hashSet.add(IntWrapper::create(i));
1961             m_hashMap.add(i + 103, IntWrapper::create(i));
1962             m_listHashSet.add(IntWrapper::create(i));
1963             m_linkedHashSet.add(IntWrapper::create(i));
1964             m_ownedVector.append(adoptPtr(new ShouldBeTraced(IntWrapper::create(i))));
1965         }
1966
1967         Deque<ShouldBeTraced>::iterator d1Iterator(m_deque1.begin());
1968         Vector<ShouldBeTraced>::iterator v1Iterator(m_vector1.begin());
1969         Deque<Member<IntWrapper> >::iterator d2Iterator(m_deque2.begin());
1970         Vector<Member<IntWrapper> >::iterator v2Iterator(m_vector2.begin());
1971         HashSet<Member<IntWrapper> >::iterator setIterator(m_hashSet.begin());
1972         HashMap<int, Member<IntWrapper> >::iterator mapIterator(m_hashMap.begin());
1973         ListHashSet<Member<IntWrapper> >::iterator listSetIterator(m_listHashSet.begin());
1974         LinkedHashSet<Member<IntWrapper> >::iterator linkedSetIterator(m_linkedHashSet.begin());
1975         Vector<OwnPtr<ShouldBeTraced> >::iterator ownedVectorIterator(m_ownedVector.begin());
1976
1977         for (int i = 0; i < iterations; i++) {
1978             EXPECT_EQ(i, m_vector1[i].m_wrapper->value());
1979             EXPECT_EQ(i, m_vector2[i]->value());
1980             EXPECT_EQ(i, d1Iterator->m_wrapper->value());
1981             EXPECT_EQ(i, v1Iterator->m_wrapper->value());
1982             EXPECT_EQ(i, d2Iterator->get()->value());
1983             EXPECT_EQ(i, v2Iterator->get()->value());
1984             EXPECT_EQ(i, linkedSetIterator->get()->value());
1985             EXPECT_EQ(i, listSetIterator->get()->value());
1986             EXPECT_EQ(i, ownedVectorIterator->get()->m_wrapper->value());
1987             int value = setIterator->get()->value();
1988             EXPECT_LE(0, value);
1989             EXPECT_GT(iterations, value);
1990             value = mapIterator->value.get()->value();
1991             EXPECT_LE(0, value);
1992             EXPECT_GT(iterations, value);
1993             ++d1Iterator;
1994             ++v1Iterator;
1995             ++d2Iterator;
1996             ++v2Iterator;
1997             ++setIterator;
1998             ++mapIterator;
1999             ++listSetIterator;
2000             ++linkedSetIterator;
2001             ++ownedVectorIterator;
2002         }
2003         EXPECT_EQ(d1Iterator, m_deque1.end());
2004         EXPECT_EQ(v1Iterator, m_vector1.end());
2005         EXPECT_EQ(d2Iterator, m_deque2.end());
2006         EXPECT_EQ(v2Iterator, m_vector2.end());
2007         EXPECT_EQ(setIterator, m_hashSet.end());
2008         EXPECT_EQ(mapIterator, m_hashMap.end());
2009         EXPECT_EQ(listSetIterator, m_listHashSet.end());
2010         EXPECT_EQ(linkedSetIterator, m_linkedHashSet.end());
2011         EXPECT_EQ(ownedVectorIterator, m_ownedVector.end());
2012     }
2013
2014     void trace(Visitor* visitor)
2015     {
2016         visitor->trace(m_deque1);
2017         visitor->trace(m_vector1);
2018         visitor->trace(m_deque2);
2019         visitor->trace(m_vector2);
2020         visitor->trace(m_hashSet);
2021         visitor->trace(m_hashMap);
2022         visitor->trace(m_listHashSet);
2023         visitor->trace(m_linkedHashSet);
2024         visitor->trace(m_listHashSet);
2025         visitor->trace(m_ownedVector);
2026     }
2027
2028     Deque<ShouldBeTraced> m_deque1;
2029     Vector<ShouldBeTraced> m_vector1;
2030     Deque<Member<IntWrapper> > m_deque2;
2031     Vector<Member<IntWrapper> > m_vector2;
2032     HashSet<Member<IntWrapper> > m_hashSet;
2033     HashMap<int, Member<IntWrapper> > m_hashMap;
2034     ListHashSet<Member<IntWrapper> > m_listHashSet;
2035     LinkedHashSet<Member<IntWrapper> > m_linkedHashSet;
2036     Vector<OwnPtr<ShouldBeTraced> > m_ownedVector;
2037 };
2038
2039 const int OffHeapContainer::iterations;
2040 const int OffHeapContainer::deadWrappers;
2041
2042 // These class definitions test compile-time asserts with transition
2043 // types. They are therefore unused in test code and just need to
2044 // compile. This is intentional; do not delete the A and B classes below.
2045 class A : public WillBeGarbageCollectedMixin {
2046 };
2047
2048 class B : public NoBaseWillBeGarbageCollected<B>, public A {
2049     WILL_BE_USING_GARBAGE_COLLECTED_MIXIN(B);
2050 public:
2051     void trace(Visitor*) { }
2052 };
2053
2054 TEST(HeapTest, HeapVectorFilledWithValue)
2055 {
2056     IntWrapper* val = IntWrapper::create(1);
2057     HeapVector<Member<IntWrapper> > vector(10, val);
2058     EXPECT_EQ(10u, vector.size());
2059     for (size_t i = 0; i < vector.size(); i++)
2060         EXPECT_EQ(val, vector[i]);
2061 }
2062
2063 TEST(HeapTest, HeapVectorWithInlineCapacity)
2064 {
2065     IntWrapper* one = IntWrapper::create(1);
2066     IntWrapper* two = IntWrapper::create(2);
2067     IntWrapper* three = IntWrapper::create(3);
2068     IntWrapper* four = IntWrapper::create(4);
2069     IntWrapper* five = IntWrapper::create(5);
2070     IntWrapper* six = IntWrapper::create(6);
2071     {
2072         HeapVector<Member<IntWrapper>, 2> vector;
2073         vector.append(one);
2074         vector.append(two);
2075         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2076         EXPECT_TRUE(vector.contains(one));
2077         EXPECT_TRUE(vector.contains(two));
2078
2079         vector.append(three);
2080         vector.append(four);
2081         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2082         EXPECT_TRUE(vector.contains(one));
2083         EXPECT_TRUE(vector.contains(two));
2084         EXPECT_TRUE(vector.contains(three));
2085         EXPECT_TRUE(vector.contains(four));
2086
2087         vector.shrink(1);
2088         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2089         EXPECT_TRUE(vector.contains(one));
2090         EXPECT_FALSE(vector.contains(two));
2091         EXPECT_FALSE(vector.contains(three));
2092         EXPECT_FALSE(vector.contains(four));
2093     }
2094     {
2095         HeapVector<Member<IntWrapper>, 2> vector1;
2096         HeapVector<Member<IntWrapper>, 2> vector2;
2097
2098         vector1.append(one);
2099         vector2.append(two);
2100         vector1.swap(vector2);
2101         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2102         EXPECT_TRUE(vector1.contains(two));
2103         EXPECT_TRUE(vector2.contains(one));
2104     }
2105     {
2106         HeapVector<Member<IntWrapper>, 2> vector1;
2107         HeapVector<Member<IntWrapper>, 2> vector2;
2108
2109         vector1.append(one);
2110         vector1.append(two);
2111         vector2.append(three);
2112         vector2.append(four);
2113         vector2.append(five);
2114         vector2.append(six);
2115         vector1.swap(vector2);
2116         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2117         EXPECT_TRUE(vector1.contains(three));
2118         EXPECT_TRUE(vector1.contains(four));
2119         EXPECT_TRUE(vector1.contains(five));
2120         EXPECT_TRUE(vector1.contains(six));
2121         EXPECT_TRUE(vector2.contains(one));
2122         EXPECT_TRUE(vector2.contains(two));
2123     }
2124 }
2125
2126 template<typename T, size_t inlineCapacity, typename U>
2127 bool dequeContains(HeapDeque<T, inlineCapacity>& deque, U u)
2128 {
2129     typedef typename HeapDeque<T, inlineCapacity>::iterator iterator;
2130     for (iterator it = deque.begin(); it != deque.end(); ++it) {
2131         if (*it == u)
2132             return true;
2133     }
2134     return false;
2135 }
2136
2137 TEST(HeapTest, HeapCollectionTypes)
2138 {
2139     HeapStats initialHeapSize;
2140     IntWrapper::s_destructorCalls = 0;
2141
2142     typedef HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > MemberMember;
2143     typedef HeapHashMap<Member<IntWrapper>, int> MemberPrimitive;
2144     typedef HeapHashMap<int, Member<IntWrapper> > PrimitiveMember;
2145
2146     typedef HeapHashSet<Member<IntWrapper> > MemberSet;
2147     typedef HeapHashCountedSet<Member<IntWrapper> > MemberCountedSet;
2148
2149     typedef HeapVector<Member<IntWrapper>, 2> MemberVector;
2150     typedef HeapDeque<Member<IntWrapper>, 0> MemberDeque;
2151
2152     typedef HeapVector<PairWrappedUnwrapped, 2> VectorWU;
2153     typedef HeapVector<PairUnwrappedWrapped, 2> VectorUW;
2154     typedef HeapDeque<PairWrappedUnwrapped, 0> DequeWU;
2155     typedef HeapDeque<PairUnwrappedWrapped, 0> DequeUW;
2156
2157     Persistent<MemberMember> memberMember = new MemberMember();
2158     Persistent<MemberMember> memberMember2 = new MemberMember();
2159     Persistent<MemberMember> memberMember3 = new MemberMember();
2160     Persistent<MemberPrimitive> memberPrimitive = new MemberPrimitive();
2161     Persistent<PrimitiveMember> primitiveMember = new PrimitiveMember();
2162     Persistent<MemberSet> set = new MemberSet();
2163     Persistent<MemberSet> set2 = new MemberSet();
2164     Persistent<MemberCountedSet> set3 = new MemberCountedSet();
2165     Persistent<MemberVector> vector = new MemberVector();
2166     Persistent<MemberVector> vector2 = new MemberVector();
2167     Persistent<VectorWU> vectorWU = new VectorWU();
2168     Persistent<VectorWU> vectorWU2 = new VectorWU();
2169     Persistent<VectorUW> vectorUW = new VectorUW();
2170     Persistent<VectorUW> vectorUW2 = new VectorUW();
2171     Persistent<MemberDeque> deque = new MemberDeque();
2172     Persistent<MemberDeque> deque2 = new MemberDeque();
2173     Persistent<DequeWU> dequeWU = new DequeWU();
2174     Persistent<DequeWU> dequeWU2 = new DequeWU();
2175     Persistent<DequeUW> dequeUW = new DequeUW();
2176     Persistent<DequeUW> dequeUW2 = new DequeUW();
2177     Persistent<Container> container = Container::create();
2178
2179     clearOutOldGarbage(&initialHeapSize);
2180     {
2181         Persistent<IntWrapper> one(IntWrapper::create(1));
2182         Persistent<IntWrapper> two(IntWrapper::create(2));
2183         Persistent<IntWrapper> oneB(IntWrapper::create(1));
2184         Persistent<IntWrapper> twoB(IntWrapper::create(2));
2185         Persistent<IntWrapper> oneC(IntWrapper::create(1));
2186         Persistent<IntWrapper> oneD(IntWrapper::create(1));
2187         Persistent<IntWrapper> oneE(IntWrapper::create(1));
2188         Persistent<IntWrapper> oneF(IntWrapper::create(1));
2189         {
2190             IntWrapper* threeB(IntWrapper::create(3));
2191             IntWrapper* threeC(IntWrapper::create(3));
2192             IntWrapper* threeD(IntWrapper::create(3));
2193             IntWrapper* threeE(IntWrapper::create(3));
2194             IntWrapper* threeF(IntWrapper::create(3));
2195             IntWrapper* three(IntWrapper::create(3));
2196             IntWrapper* fourB(IntWrapper::create(4));
2197             IntWrapper* fourC(IntWrapper::create(4));
2198             IntWrapper* fourD(IntWrapper::create(4));
2199             IntWrapper* fourE(IntWrapper::create(4));
2200             IntWrapper* fourF(IntWrapper::create(4));
2201             IntWrapper* four(IntWrapper::create(4));
2202             IntWrapper* fiveC(IntWrapper::create(5));
2203             IntWrapper* fiveD(IntWrapper::create(5));
2204             IntWrapper* fiveE(IntWrapper::create(5));
2205             IntWrapper* fiveF(IntWrapper::create(5));
2206
2207             // Member Collections.
2208             memberMember2->add(one, two);
2209             memberMember2->add(two, three);
2210             memberMember2->add(three, four);
2211             memberMember2->add(four, one);
2212             primitiveMember->add(1, two);
2213             primitiveMember->add(2, three);
2214             primitiveMember->add(3, four);
2215             primitiveMember->add(4, one);
2216             memberPrimitive->add(one, 2);
2217             memberPrimitive->add(two, 3);
2218             memberPrimitive->add(three, 4);
2219             memberPrimitive->add(four, 1);
2220             set2->add(one);
2221             set2->add(two);
2222             set2->add(three);
2223             set2->add(four);
2224             set->add(oneB);
2225             set3->add(oneB);
2226             set3->add(oneB);
2227             vector->append(oneB);
2228             deque->append(oneB);
2229             vector2->append(threeB);
2230             vector2->append(fourB);
2231             deque2->append(threeE);
2232             deque2->append(fourE);
2233             vectorWU->append(PairWrappedUnwrapped(&*oneC, 42));
2234             dequeWU->append(PairWrappedUnwrapped(&*oneE, 42));
2235             vectorWU2->append(PairWrappedUnwrapped(&*threeC, 43));
2236             vectorWU2->append(PairWrappedUnwrapped(&*fourC, 44));
2237             vectorWU2->append(PairWrappedUnwrapped(&*fiveC, 45));
2238             dequeWU2->append(PairWrappedUnwrapped(&*threeE, 43));
2239             dequeWU2->append(PairWrappedUnwrapped(&*fourE, 44));
2240             dequeWU2->append(PairWrappedUnwrapped(&*fiveE, 45));
2241             vectorUW->append(PairUnwrappedWrapped(1, &*oneD));
2242             vectorUW2->append(PairUnwrappedWrapped(103, &*threeD));
2243             vectorUW2->append(PairUnwrappedWrapped(104, &*fourD));
2244             vectorUW2->append(PairUnwrappedWrapped(105, &*fiveD));
2245             dequeUW->append(PairUnwrappedWrapped(1, &*oneF));
2246             dequeUW2->append(PairUnwrappedWrapped(103, &*threeF));
2247             dequeUW2->append(PairUnwrappedWrapped(104, &*fourF));
2248             dequeUW2->append(PairUnwrappedWrapped(105, &*fiveF));
2249
2250             EXPECT_TRUE(dequeContains(*deque, oneB));
2251
2252             // Collect garbage. This should change nothing since we are keeping
2253             // alive the IntWrapper objects with on-stack pointers.
2254             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2255
2256             EXPECT_TRUE(dequeContains(*deque, oneB));
2257
2258             EXPECT_EQ(0u, memberMember->size());
2259             EXPECT_EQ(4u, memberMember2->size());
2260             EXPECT_EQ(4u, primitiveMember->size());
2261             EXPECT_EQ(4u, memberPrimitive->size());
2262             EXPECT_EQ(1u, set->size());
2263             EXPECT_EQ(4u, set2->size());
2264             EXPECT_EQ(1u, set3->size());
2265             EXPECT_EQ(1u, vector->size());
2266             EXPECT_EQ(2u, vector2->size());
2267             EXPECT_EQ(1u, vectorWU->size());
2268             EXPECT_EQ(3u, vectorWU2->size());
2269             EXPECT_EQ(1u, vectorUW->size());
2270             EXPECT_EQ(3u, vectorUW2->size());
2271             EXPECT_EQ(1u, deque->size());
2272             EXPECT_EQ(2u, deque2->size());
2273             EXPECT_EQ(1u, dequeWU->size());
2274             EXPECT_EQ(3u, dequeWU2->size());
2275             EXPECT_EQ(1u, dequeUW->size());
2276             EXPECT_EQ(3u, dequeUW2->size());
2277
2278             MemberVector& cvec = container->vector;
2279             cvec.swap(*vector.get());
2280             vector2->swap(cvec);
2281             vector->swap(cvec);
2282
2283             VectorWU& cvecWU = container->vectorWU;
2284             cvecWU.swap(*vectorWU.get());
2285             vectorWU2->swap(cvecWU);
2286             vectorWU->swap(cvecWU);
2287
2288             VectorUW& cvecUW = container->vectorUW;
2289             cvecUW.swap(*vectorUW.get());
2290             vectorUW2->swap(cvecUW);
2291             vectorUW->swap(cvecUW);
2292
2293             MemberDeque& cDeque = container->deque;
2294             cDeque.swap(*deque.get());
2295             deque2->swap(cDeque);
2296             deque->swap(cDeque);
2297
2298             DequeWU& cDequeWU = container->dequeWU;
2299             cDequeWU.swap(*dequeWU.get());
2300             dequeWU2->swap(cDequeWU);
2301             dequeWU->swap(cDequeWU);
2302
2303             DequeUW& cDequeUW = container->dequeUW;
2304             cDequeUW.swap(*dequeUW.get());
2305             dequeUW2->swap(cDequeUW);
2306             dequeUW->swap(cDequeUW);
2307
2308             // Swap set and set2 in a roundabout way.
2309             MemberSet& cset1 = container->set;
2310             MemberSet& cset2 = container->set2;
2311             set->swap(cset1);
2312             set2->swap(cset2);
2313             set->swap(cset2);
2314             cset1.swap(cset2);
2315             cset2.swap(set2);
2316
2317             MemberCountedSet& cCountedSet = container->set3;
2318             set3->swap(cCountedSet);
2319             EXPECT_EQ(0u, set3->size());
2320             set3->swap(cCountedSet);
2321
2322             // Triple swap.
2323             container->map.swap(memberMember2);
2324             MemberMember& containedMap = container->map;
2325             memberMember3->swap(containedMap);
2326             memberMember3->swap(memberMember);
2327
2328             EXPECT_TRUE(memberMember->get(one) == two);
2329             EXPECT_TRUE(memberMember->get(two) == three);
2330             EXPECT_TRUE(memberMember->get(three) == four);
2331             EXPECT_TRUE(memberMember->get(four) == one);
2332             EXPECT_TRUE(primitiveMember->get(1) == two);
2333             EXPECT_TRUE(primitiveMember->get(2) == three);
2334             EXPECT_TRUE(primitiveMember->get(3) == four);
2335             EXPECT_TRUE(primitiveMember->get(4) == one);
2336             EXPECT_EQ(1, memberPrimitive->get(four));
2337             EXPECT_EQ(2, memberPrimitive->get(one));
2338             EXPECT_EQ(3, memberPrimitive->get(two));
2339             EXPECT_EQ(4, memberPrimitive->get(three));
2340             EXPECT_TRUE(set->contains(one));
2341             EXPECT_TRUE(set->contains(two));
2342             EXPECT_TRUE(set->contains(three));
2343             EXPECT_TRUE(set->contains(four));
2344             EXPECT_TRUE(set2->contains(oneB));
2345             EXPECT_TRUE(set3->contains(oneB));
2346             EXPECT_TRUE(vector->contains(threeB));
2347             EXPECT_TRUE(vector->contains(fourB));
2348             EXPECT_TRUE(dequeContains(*deque, threeE));
2349             EXPECT_TRUE(dequeContains(*deque, fourE));
2350             EXPECT_TRUE(vector2->contains(oneB));
2351             EXPECT_FALSE(vector2->contains(threeB));
2352             EXPECT_TRUE(dequeContains(*deque2, oneB));
2353             EXPECT_FALSE(dequeContains(*deque2, threeE));
2354             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*threeC, 43)));
2355             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fourC, 44)));
2356             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fiveC, 45)));
2357             EXPECT_TRUE(vectorWU2->contains(PairWrappedUnwrapped(&*oneC, 42)));
2358             EXPECT_FALSE(vectorWU2->contains(PairWrappedUnwrapped(&*threeC, 43)));
2359             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(103, &*threeD)));
2360             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(104, &*fourD)));
2361             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(105, &*fiveD)));
2362             EXPECT_TRUE(vectorUW2->contains(PairUnwrappedWrapped(1, &*oneD)));
2363             EXPECT_FALSE(vectorUW2->contains(PairUnwrappedWrapped(103, &*threeD)));
2364             EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*threeE, 43)));
2365             EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*fourE, 44)));
2366             EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*fiveE, 45)));
2367             EXPECT_TRUE(dequeContains(*dequeWU2, PairWrappedUnwrapped(&*oneE, 42)));
2368             EXPECT_FALSE(dequeContains(*dequeWU2, PairWrappedUnwrapped(&*threeE, 43)));
2369             EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(103, &*threeF)));
2370             EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(104, &*fourF)));
2371             EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(105, &*fiveF)));
2372             EXPECT_TRUE(dequeContains(*dequeUW2, PairUnwrappedWrapped(1, &*oneF)));
2373             EXPECT_FALSE(dequeContains(*dequeUW2, PairUnwrappedWrapped(103, &*threeF)));
2374         }
2375
2376         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2377
2378         EXPECT_EQ(4u, memberMember->size());
2379         EXPECT_EQ(0u, memberMember2->size());
2380         EXPECT_EQ(4u, primitiveMember->size());
2381         EXPECT_EQ(4u, memberPrimitive->size());
2382         EXPECT_EQ(4u, set->size());
2383         EXPECT_EQ(1u, set2->size());
2384         EXPECT_EQ(1u, set3->size());
2385         EXPECT_EQ(2u, vector->size());
2386         EXPECT_EQ(1u, vector2->size());
2387         EXPECT_EQ(3u, vectorUW->size());
2388         EXPECT_EQ(1u, vector2->size());
2389         EXPECT_EQ(2u, deque->size());
2390         EXPECT_EQ(1u, deque2->size());
2391         EXPECT_EQ(3u, dequeUW->size());
2392         EXPECT_EQ(1u, deque2->size());
2393
2394         EXPECT_TRUE(memberMember->get(one) == two);
2395         EXPECT_TRUE(primitiveMember->get(1) == two);
2396         EXPECT_TRUE(primitiveMember->get(4) == one);
2397         EXPECT_EQ(2, memberPrimitive->get(one));
2398         EXPECT_EQ(3, memberPrimitive->get(two));
2399         EXPECT_TRUE(set->contains(one));
2400         EXPECT_TRUE(set->contains(two));
2401         EXPECT_FALSE(set->contains(oneB));
2402         EXPECT_TRUE(set2->contains(oneB));
2403         EXPECT_TRUE(set3->contains(oneB));
2404         EXPECT_EQ(2u, set3->find(oneB)->value);
2405         EXPECT_EQ(3, vector->at(0)->value());
2406         EXPECT_EQ(4, vector->at(1)->value());
2407         EXPECT_EQ(3, deque->begin()->get()->value());
2408     }
2409
2410     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2411     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2412
2413     EXPECT_EQ(4u, memberMember->size());
2414     EXPECT_EQ(4u, primitiveMember->size());
2415     EXPECT_EQ(4u, memberPrimitive->size());
2416     EXPECT_EQ(4u, set->size());
2417     EXPECT_EQ(1u, set2->size());
2418     EXPECT_EQ(2u, vector->size());
2419     EXPECT_EQ(1u, vector2->size());
2420     EXPECT_EQ(3u, vectorWU->size());
2421     EXPECT_EQ(1u, vectorWU2->size());
2422     EXPECT_EQ(3u, vectorUW->size());
2423     EXPECT_EQ(1u, vectorUW2->size());
2424     EXPECT_EQ(2u, deque->size());
2425     EXPECT_EQ(1u, deque2->size());
2426     EXPECT_EQ(3u, dequeWU->size());
2427     EXPECT_EQ(1u, dequeWU2->size());
2428     EXPECT_EQ(3u, dequeUW->size());
2429     EXPECT_EQ(1u, dequeUW2->size());
2430 }
2431
2432 template<typename T>
2433 void MapIteratorCheck(T& it, const T& end, int expected)
2434 {
2435     int found = 0;
2436     while (it != end) {
2437         found++;
2438         int key = it->key->value();
2439         int value = it->value->value();
2440         EXPECT_TRUE(key >= 0 && key < 1100);
2441         EXPECT_TRUE(value >= 0 && value < 1100);
2442         ++it;
2443     }
2444     EXPECT_EQ(expected, found);
2445 }
2446
2447 template<typename T>
2448 void SetIteratorCheck(T& it, const T& end, int expected)
2449 {
2450     int found = 0;
2451     while (it != end) {
2452         found++;
2453         int value = (*it)->value();
2454         EXPECT_TRUE(value >= 0 && value < 1100);
2455         ++it;
2456     }
2457     EXPECT_EQ(expected, found);
2458 }
2459
2460 TEST(HeapTest, HeapWeakCollectionSimple)
2461 {
2462     HeapStats initialHeapStats;
2463     clearOutOldGarbage(&initialHeapStats);
2464     IntWrapper::s_destructorCalls = 0;
2465
2466     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2467
2468     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
2469     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
2470     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
2471     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
2472     typedef HeapHashCountedSet<WeakMember<IntWrapper> > WeakCountedSet;
2473
2474     Persistent<WeakStrong> weakStrong = new WeakStrong();
2475     Persistent<StrongWeak> strongWeak = new StrongWeak();
2476     Persistent<WeakWeak> weakWeak = new WeakWeak();
2477     Persistent<WeakSet> weakSet = new WeakSet();
2478     Persistent<WeakCountedSet> weakCountedSet = new WeakCountedSet();
2479
2480     Persistent<IntWrapper> two = IntWrapper::create(2);
2481
2482     keepNumbersAlive.append(IntWrapper::create(103));
2483     keepNumbersAlive.append(IntWrapper::create(10));
2484
2485     {
2486         weakStrong->add(IntWrapper::create(1), two);
2487         strongWeak->add(two, IntWrapper::create(1));
2488         weakWeak->add(two, IntWrapper::create(42));
2489         weakWeak->add(IntWrapper::create(42), two);
2490         weakSet->add(IntWrapper::create(0));
2491         weakSet->add(two);
2492         weakSet->add(keepNumbersAlive[0]);
2493         weakSet->add(keepNumbersAlive[1]);
2494         weakCountedSet->add(IntWrapper::create(0));
2495         weakCountedSet->add(two);
2496         weakCountedSet->add(two);
2497         weakCountedSet->add(two);
2498         weakCountedSet->add(keepNumbersAlive[0]);
2499         weakCountedSet->add(keepNumbersAlive[1]);
2500         EXPECT_EQ(1u, weakStrong->size());
2501         EXPECT_EQ(1u, strongWeak->size());
2502         EXPECT_EQ(2u, weakWeak->size());
2503         EXPECT_EQ(4u, weakSet->size());
2504         EXPECT_EQ(4u, weakCountedSet->size());
2505         EXPECT_EQ(3u, weakCountedSet->find(two)->value);
2506         weakCountedSet->remove(two);
2507         EXPECT_EQ(2u, weakCountedSet->find(two)->value);
2508     }
2509
2510     keepNumbersAlive[0] = nullptr;
2511
2512     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2513
2514     EXPECT_EQ(0u, weakStrong->size());
2515     EXPECT_EQ(0u, strongWeak->size());
2516     EXPECT_EQ(0u, weakWeak->size());
2517     EXPECT_EQ(2u, weakSet->size());
2518     EXPECT_EQ(2u, weakCountedSet->size());
2519 }
2520
2521 template<typename Set>
2522 void orderedSetHelper(bool strong)
2523 {
2524     HeapStats initialHeapStats;
2525     clearOutOldGarbage(&initialHeapStats);
2526     IntWrapper::s_destructorCalls = 0;
2527
2528     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2529
2530     Persistent<Set> set1 = new Set();
2531     Persistent<Set> set2 = new Set();
2532
2533     const Set& constSet = *set1.get();
2534
2535     keepNumbersAlive.append(IntWrapper::create(2));
2536     keepNumbersAlive.append(IntWrapper::create(103));
2537     keepNumbersAlive.append(IntWrapper::create(10));
2538
2539     set1->add(IntWrapper::create(0));
2540     set1->add(keepNumbersAlive[0]);
2541     set1->add(keepNumbersAlive[1]);
2542     set1->add(keepNumbersAlive[2]);
2543
2544     set2->clear();
2545     set2->add(IntWrapper::create(42));
2546     set2->clear();
2547
2548     EXPECT_EQ(4u, set1->size());
2549     typename Set::iterator it(set1->begin());
2550     typename Set::reverse_iterator reverse(set1->rbegin());
2551     typename Set::const_iterator cit(constSet.begin());
2552     typename Set::const_reverse_iterator creverse(constSet.rbegin());
2553
2554     EXPECT_EQ(0, (*it)->value());
2555     EXPECT_EQ(0, (*cit)->value());
2556     ++it;
2557     ++cit;
2558     EXPECT_EQ(2, (*it)->value());
2559     EXPECT_EQ(2, (*cit)->value());
2560     --it;
2561     --cit;
2562     EXPECT_EQ(0, (*it)->value());
2563     EXPECT_EQ(0, (*cit)->value());
2564     ++it;
2565     ++cit;
2566     ++it;
2567     ++cit;
2568     EXPECT_EQ(103, (*it)->value());
2569     EXPECT_EQ(103, (*cit)->value());
2570     ++it;
2571     ++cit;
2572     EXPECT_EQ(10, (*it)->value());
2573     EXPECT_EQ(10, (*cit)->value());
2574     ++it;
2575     ++cit;
2576
2577     EXPECT_EQ(10, (*reverse)->value());
2578     EXPECT_EQ(10, (*creverse)->value());
2579     ++reverse;
2580     ++creverse;
2581     EXPECT_EQ(103, (*reverse)->value());
2582     EXPECT_EQ(103, (*creverse)->value());
2583     --reverse;
2584     --creverse;
2585     EXPECT_EQ(10, (*reverse)->value());
2586     EXPECT_EQ(10, (*creverse)->value());
2587     ++reverse;
2588     ++creverse;
2589     ++reverse;
2590     ++creverse;
2591     EXPECT_EQ(2, (*reverse)->value());
2592     EXPECT_EQ(2, (*creverse)->value());
2593     ++reverse;
2594     ++creverse;
2595     EXPECT_EQ(0, (*reverse)->value());
2596     EXPECT_EQ(0, (*creverse)->value());
2597     ++reverse;
2598     ++creverse;
2599
2600     EXPECT_EQ(set1->end(), it);
2601     EXPECT_EQ(constSet.end(), cit);
2602     EXPECT_EQ(set1->rend(), reverse);
2603     EXPECT_EQ(constSet.rend(), creverse);
2604
2605     typename Set::iterator iX(set2->begin());
2606     EXPECT_EQ(set2->end(), iX);
2607
2608     if (strong)
2609         set1->remove(keepNumbersAlive[0]);
2610
2611     keepNumbersAlive[0] = nullptr;
2612
2613     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2614
2615     EXPECT_EQ(2u + (strong ? 1u : 0u), set1->size());
2616
2617     EXPECT_EQ(2 + (strong ? 0 : 1), IntWrapper::s_destructorCalls);
2618
2619     typename Set::iterator i2(set1->begin());
2620     if (strong) {
2621         EXPECT_EQ(0, (*i2)->value());
2622         ++i2;
2623         EXPECT_NE(set1->end(), i2);
2624     }
2625     EXPECT_EQ(103, (*i2)->value());
2626     ++i2;
2627     EXPECT_NE(set1->end(), i2);
2628     EXPECT_EQ(10, (*i2)->value());
2629     ++i2;
2630     EXPECT_EQ(set1->end(), i2);
2631 }
2632
2633 TEST(HeapTest, HeapWeakLinkedHashSet)
2634 {
2635     orderedSetHelper<HeapLinkedHashSet<Member<IntWrapper> > >(true);
2636     orderedSetHelper<HeapLinkedHashSet<WeakMember<IntWrapper> > >(false);
2637     orderedSetHelper<HeapListHashSet<Member<IntWrapper> > >(true);
2638 }
2639
2640 class ThingWithDestructor {
2641 public:
2642     ThingWithDestructor()
2643         : m_x(emptyValue)
2644     {
2645         s_liveThingsWithDestructor++;
2646     }
2647
2648     ThingWithDestructor(int x)
2649         : m_x(x)
2650     {
2651         s_liveThingsWithDestructor++;
2652     }
2653
2654     ThingWithDestructor(const ThingWithDestructor&other)
2655     {
2656         *this = other;
2657         s_liveThingsWithDestructor++;
2658     }
2659
2660     ~ThingWithDestructor()
2661     {
2662         s_liveThingsWithDestructor--;
2663     }
2664
2665     int value() { return m_x; }
2666
2667     static int s_liveThingsWithDestructor;
2668
2669     unsigned hash() { return IntHash<int>::hash(m_x); }
2670
2671 private:
2672     static const int emptyValue = 0;
2673     int m_x;
2674 };
2675
2676 int ThingWithDestructor::s_liveThingsWithDestructor;
2677
2678 struct ThingWithDestructorTraits : public HashTraits<ThingWithDestructor> {
2679     static const bool needsDestruction = true;
2680 };
2681
2682 static void heapMapDestructorHelper(bool clearMaps)
2683 {
2684     HeapStats initialHeapStats;
2685     clearOutOldGarbage(&initialHeapStats);
2686     ThingWithDestructor::s_liveThingsWithDestructor = 0;
2687
2688     typedef HeapHashMap<WeakMember<IntWrapper>, RefPtr<RefCountedAndGarbageCollected> > RefMap;
2689
2690     typedef HeapHashMap<
2691         WeakMember<IntWrapper>,
2692         ThingWithDestructor,
2693         DefaultHash<WeakMember<IntWrapper> >::Hash,
2694         HashTraits<WeakMember<IntWrapper> >,
2695         ThingWithDestructorTraits> Map;
2696
2697     Persistent<Map> map(new Map());
2698     Persistent<RefMap> refMap(new RefMap());
2699
2700     Persistent<IntWrapper> luck(IntWrapper::create(103));
2701
2702     int baseLine, refBaseLine;
2703
2704     {
2705         Map stackMap;
2706         RefMap stackRefMap;
2707
2708         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2709         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2710
2711         stackMap.add(IntWrapper::create(42), ThingWithDestructor(1729));
2712         stackMap.add(luck, ThingWithDestructor(8128));
2713         stackRefMap.add(IntWrapper::create(42), RefCountedAndGarbageCollected::create());
2714         stackRefMap.add(luck, RefCountedAndGarbageCollected::create());
2715
2716         baseLine = ThingWithDestructor::s_liveThingsWithDestructor;
2717         refBaseLine = RefCountedAndGarbageCollected::s_destructorCalls;
2718
2719         // Although the heap maps are on-stack, we can't expect prompt
2720         // finalization of the elements, so when they go out of scope here we
2721         // will not necessarily have called the relevant destructors.
2722     }
2723
2724     // The RefCountedAndGarbageCollected things need an extra GC to discover
2725     // that they are no longer ref counted.
2726     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2727     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2728     EXPECT_EQ(baseLine - 2, ThingWithDestructor::s_liveThingsWithDestructor);
2729     EXPECT_EQ(refBaseLine + 2, RefCountedAndGarbageCollected::s_destructorCalls);
2730
2731     // Now use maps kept alive with persistents. Here we don't expect any
2732     // destructors to be called before there have been GCs.
2733
2734     map->add(IntWrapper::create(42), ThingWithDestructor(1729));
2735     map->add(luck, ThingWithDestructor(8128));
2736     refMap->add(IntWrapper::create(42), RefCountedAndGarbageCollected::create());
2737     refMap->add(luck, RefCountedAndGarbageCollected::create());
2738
2739     baseLine  =  ThingWithDestructor::s_liveThingsWithDestructor;
2740     refBaseLine = RefCountedAndGarbageCollected::s_destructorCalls;
2741
2742     luck.clear();
2743     if (clearMaps) {
2744         map->clear(); // Clear map.
2745         refMap->clear(); // Clear map.
2746     } else {
2747         map.clear(); // Clear Persistent handle, not map.
2748         refMap.clear(); // Clear Persistent handle, not map.
2749         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2750         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2751     }
2752
2753     EXPECT_EQ(baseLine - 2, ThingWithDestructor::s_liveThingsWithDestructor);
2754
2755     // Need a GC to make sure that the RefCountedAndGarbageCollected thing
2756     // noticies it's been decremented to zero.
2757     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2758     EXPECT_EQ(refBaseLine + 2, RefCountedAndGarbageCollected::s_destructorCalls);
2759 }
2760
2761 TEST(HeapTest, HeapMapDestructor)
2762 {
2763     heapMapDestructorHelper(true);
2764     heapMapDestructorHelper(false);
2765 }
2766
2767 typedef HeapHashSet<PairWeakStrong> WeakStrongSet;
2768 typedef HeapHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2769 typedef HeapHashSet<PairStrongWeak> StrongWeakSet;
2770 typedef HeapHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2771 typedef HeapLinkedHashSet<PairWeakStrong> WeakStrongLinkedSet;
2772 typedef HeapLinkedHashSet<PairWeakUnwrapped> WeakUnwrappedLinkedSet;
2773 typedef HeapLinkedHashSet<PairStrongWeak> StrongWeakLinkedSet;
2774 typedef HeapLinkedHashSet<PairUnwrappedWeak> UnwrappedWeakLinkedSet;
2775 typedef HeapHashCountedSet<PairWeakStrong> WeakStrongCountedSet;
2776 typedef HeapHashCountedSet<PairWeakUnwrapped> WeakUnwrappedCountedSet;
2777 typedef HeapHashCountedSet<PairStrongWeak> StrongWeakCountedSet;
2778 typedef HeapHashCountedSet<PairUnwrappedWeak> UnwrappedWeakCountedSet;
2779
2780 template<typename T>
2781 T& iteratorExtractor(WTF::KeyValuePair<T, unsigned>& pair)
2782 {
2783     return pair.key;
2784 }
2785
2786 template<typename T>
2787 T& iteratorExtractor(T& notAPair)
2788 {
2789     return notAPair;
2790 }
2791
2792 template<typename WSSet, typename SWSet, typename WUSet, typename UWSet>
2793 void checkPairSets(
2794     Persistent<WSSet>& weakStrong,
2795     Persistent<SWSet>& strongWeak,
2796     Persistent<WUSet>& weakUnwrapped,
2797     Persistent<UWSet>& unwrappedWeak,
2798     bool ones,
2799     Persistent<IntWrapper>& two)
2800 {
2801     typename WSSet::iterator itWS = weakStrong->begin();
2802     typename SWSet::iterator itSW = strongWeak->begin();
2803     typename WUSet::iterator itWU = weakUnwrapped->begin();
2804     typename UWSet::iterator itUW = unwrappedWeak->begin();
2805
2806     EXPECT_EQ(2u, weakStrong->size());
2807     EXPECT_EQ(2u, strongWeak->size());
2808     EXPECT_EQ(2u, weakUnwrapped->size());
2809     EXPECT_EQ(2u, unwrappedWeak->size());
2810
2811     PairWeakStrong p = iteratorExtractor(*itWS);
2812     PairStrongWeak p2 = iteratorExtractor(*itSW);
2813     PairWeakUnwrapped p3 = iteratorExtractor(*itWU);
2814     PairUnwrappedWeak p4 = iteratorExtractor(*itUW);
2815     if (p.first == two && p.second == two)
2816         ++itWS;
2817     if (p2.first == two && p2.second == two)
2818         ++itSW;
2819     if (p3.first == two && p3.second == 2)
2820         ++itWU;
2821     if (p4.first == 2 && p4.second == two)
2822         ++itUW;
2823     p = iteratorExtractor(*itWS);
2824     p2 = iteratorExtractor(*itSW);
2825     p3 = iteratorExtractor(*itWU);
2826     p4 = iteratorExtractor(*itUW);
2827     IntWrapper* nullWrapper = 0;
2828     if (ones) {
2829         EXPECT_EQ(p.first->value(), 1);
2830         EXPECT_EQ(p2.second->value(), 1);
2831         EXPECT_EQ(p3.first->value(), 1);
2832         EXPECT_EQ(p4.second->value(), 1);
2833     } else {
2834         EXPECT_EQ(p.first, nullWrapper);
2835         EXPECT_EQ(p2.second, nullWrapper);
2836         EXPECT_EQ(p3.first, nullWrapper);
2837         EXPECT_EQ(p4.second, nullWrapper);
2838     }
2839
2840     EXPECT_EQ(p.second->value(), 2);
2841     EXPECT_EQ(p2.first->value(), 2);
2842     EXPECT_EQ(p3.second, 2);
2843     EXPECT_EQ(p4.first, 2);
2844
2845     EXPECT_TRUE(weakStrong->contains(PairWeakStrong(&*two, &*two)));
2846     EXPECT_TRUE(strongWeak->contains(PairStrongWeak(&*two, &*two)));
2847     EXPECT_TRUE(weakUnwrapped->contains(PairWeakUnwrapped(&*two, 2)));
2848     EXPECT_TRUE(unwrappedWeak->contains(PairUnwrappedWeak(2, &*two)));
2849 }
2850
2851 template<typename WSSet, typename SWSet, typename WUSet, typename UWSet>
2852 void weakPairsHelper()
2853 {
2854     IntWrapper::s_destructorCalls = 0;
2855
2856     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2857
2858     Persistent<WSSet> weakStrong = new WSSet();
2859     Persistent<SWSet> strongWeak = new SWSet();
2860     Persistent<WUSet> weakUnwrapped = new WUSet();
2861     Persistent<UWSet> unwrappedWeak = new UWSet();
2862
2863     Persistent<IntWrapper> two = IntWrapper::create(2);
2864
2865     weakStrong->add(PairWeakStrong(IntWrapper::create(1), &*two));
2866     weakStrong->add(PairWeakStrong(&*two, &*two));
2867     strongWeak->add(PairStrongWeak(&*two, IntWrapper::create(1)));
2868     strongWeak->add(PairStrongWeak(&*two, &*two));
2869     weakUnwrapped->add(PairWeakUnwrapped(IntWrapper::create(1), 2));
2870     weakUnwrapped->add(PairWeakUnwrapped(&*two, 2));
2871     unwrappedWeak->add(PairUnwrappedWeak(2, IntWrapper::create(1)));
2872     unwrappedWeak->add(PairUnwrappedWeak(2, &*two));
2873
2874     checkPairSets<WSSet, SWSet, WUSet, UWSet>(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, true, two);
2875
2876     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2877     checkPairSets<WSSet, SWSet, WUSet, UWSet>(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, false, two);
2878 }
2879
2880 TEST(HeapTest, HeapWeakPairs)
2881 {
2882     {
2883         typedef HeapHashSet<PairWeakStrong> WeakStrongSet;
2884         typedef HeapHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2885         typedef HeapHashSet<PairStrongWeak> StrongWeakSet;
2886         typedef HeapHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2887         weakPairsHelper<WeakStrongSet, StrongWeakSet, WeakUnwrappedSet, UnwrappedWeakSet>();
2888     }
2889
2890     {
2891         typedef HeapListHashSet<PairWeakStrong> WeakStrongSet;
2892         typedef HeapListHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2893         typedef HeapListHashSet<PairStrongWeak> StrongWeakSet;
2894         typedef HeapListHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2895         weakPairsHelper<WeakStrongSet, StrongWeakSet, WeakUnwrappedSet, UnwrappedWeakSet>();
2896     }
2897
2898     {
2899         typedef HeapLinkedHashSet<PairWeakStrong> WeakStrongSet;
2900         typedef HeapLinkedHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2901         typedef HeapLinkedHashSet<PairStrongWeak> StrongWeakSet;
2902         typedef HeapLinkedHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2903         weakPairsHelper<WeakStrongSet, StrongWeakSet, WeakUnwrappedSet, UnwrappedWeakSet>();
2904     }
2905 }
2906
2907 TEST(HeapTest, HeapWeakCollectionTypes)
2908 {
2909     HeapStats initialHeapSize;
2910     IntWrapper::s_destructorCalls = 0;
2911
2912     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
2913     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
2914     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
2915     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
2916     typedef HeapLinkedHashSet<WeakMember<IntWrapper> > WeakOrderedSet;
2917
2918     clearOutOldGarbage(&initialHeapSize);
2919
2920     const int weakStrongIndex = 0;
2921     const int strongWeakIndex = 1;
2922     const int weakWeakIndex = 2;
2923     const int numberOfMapIndices = 3;
2924     const int weakSetIndex = 3;
2925     const int weakOrderedSetIndex = 4;
2926     const int numberOfCollections = 5;
2927
2928     for (int testRun = 0; testRun < 4; testRun++) {
2929         for (int collectionNumber = 0; collectionNumber < numberOfCollections; collectionNumber++) {
2930             bool deleteAfterwards = (testRun == 1);
2931             bool addAfterwards = (testRun == 2);
2932             bool testThatIteratorsMakeStrong = (testRun == 3);
2933
2934             // The test doesn't work for strongWeak with deleting because we lost
2935             // the key from the keepNumbersAlive array, so we can't do the lookup.
2936             if (deleteAfterwards && collectionNumber == strongWeakIndex)
2937                 continue;
2938
2939             unsigned added = addAfterwards ? 100 : 0;
2940
2941             Persistent<WeakStrong> weakStrong = new WeakStrong();
2942             Persistent<StrongWeak> strongWeak = new StrongWeak();
2943             Persistent<WeakWeak> weakWeak = new WeakWeak();
2944
2945             Persistent<WeakSet> weakSet = new WeakSet();
2946             Persistent<WeakOrderedSet> weakOrderedSet = new WeakOrderedSet();
2947
2948             PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2949             for (int i = 0; i < 128; i += 2) {
2950                 IntWrapper* wrapped = IntWrapper::create(i);
2951                 IntWrapper* wrapped2 = IntWrapper::create(i + 1);
2952                 keepNumbersAlive.append(wrapped);
2953                 keepNumbersAlive.append(wrapped2);
2954                 weakStrong->add(wrapped, wrapped2);
2955                 strongWeak->add(wrapped2, wrapped);
2956                 weakWeak->add(wrapped, wrapped2);
2957                 weakSet->add(wrapped);
2958                 weakOrderedSet->add(wrapped);
2959             }
2960
2961             EXPECT_EQ(64u, weakStrong->size());
2962             EXPECT_EQ(64u, strongWeak->size());
2963             EXPECT_EQ(64u, weakWeak->size());
2964             EXPECT_EQ(64u, weakSet->size());
2965             EXPECT_EQ(64u, weakOrderedSet->size());
2966
2967             // Collect garbage. This should change nothing since we are keeping
2968             // alive the IntWrapper objects.
2969             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2970
2971             EXPECT_EQ(64u, weakStrong->size());
2972             EXPECT_EQ(64u, strongWeak->size());
2973             EXPECT_EQ(64u, weakWeak->size());
2974             EXPECT_EQ(64u, weakSet->size());
2975             EXPECT_EQ(64u, weakOrderedSet->size());
2976
2977             for (int i = 0; i < 128; i += 2) {
2978                 IntWrapper* wrapped = keepNumbersAlive[i];
2979                 IntWrapper* wrapped2 = keepNumbersAlive[i + 1];
2980                 EXPECT_EQ(wrapped2, weakStrong->get(wrapped));
2981                 EXPECT_EQ(wrapped, strongWeak->get(wrapped2));
2982                 EXPECT_EQ(wrapped2, weakWeak->get(wrapped));
2983                 EXPECT_TRUE(weakSet->contains(wrapped));
2984                 EXPECT_TRUE(weakOrderedSet->contains(wrapped));
2985             }
2986
2987             for (int i = 0; i < 128; i += 3)
2988                 keepNumbersAlive[i] = nullptr;
2989
2990             if (collectionNumber != weakStrongIndex)
2991                 weakStrong->clear();
2992             if (collectionNumber != strongWeakIndex)
2993                 strongWeak->clear();
2994             if (collectionNumber != weakWeakIndex)
2995                 weakWeak->clear();
2996             if (collectionNumber != weakSetIndex)
2997                 weakSet->clear();
2998             if (collectionNumber != weakOrderedSetIndex)
2999                 weakOrderedSet->clear();
3000
3001             if (testThatIteratorsMakeStrong) {
3002                 WeakStrong::iterator it1 = weakStrong->begin();
3003                 StrongWeak::iterator it2 = strongWeak->begin();
3004                 WeakWeak::iterator it3 = weakWeak->begin();
3005                 WeakSet::iterator it4 = weakSet->begin();
3006                 WeakOrderedSet::iterator it5 = weakOrderedSet->begin();
3007                 // Collect garbage. This should change nothing since the
3008                 // iterators make the collections strong.
3009                 Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3010                 if (collectionNumber == weakStrongIndex) {
3011                     EXPECT_EQ(64u, weakStrong->size());
3012                     MapIteratorCheck(it1, weakStrong->end(), 64);
3013                 } else if (collectionNumber == strongWeakIndex) {
3014                     EXPECT_EQ(64u, strongWeak->size());
3015                     MapIteratorCheck(it2, strongWeak->end(), 64);
3016                 } else if (collectionNumber == weakWeakIndex) {
3017                     EXPECT_EQ(64u, weakWeak->size());
3018                     MapIteratorCheck(it3, weakWeak->end(), 64);
3019                 } else if (collectionNumber == weakSetIndex) {
3020                     EXPECT_EQ(64u, weakSet->size());
3021                     SetIteratorCheck(it4, weakSet->end(), 64);
3022                 } else if (collectionNumber == weakOrderedSetIndex) {
3023                     EXPECT_EQ(64u, weakOrderedSet->size());
3024                     SetIteratorCheck(it5, weakOrderedSet->end(), 64);
3025                 }
3026             } else {
3027                 // Collect garbage. This causes weak processing to remove
3028                 // things from the collections.
3029                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3030                 unsigned count = 0;
3031                 for (int i = 0; i < 128; i += 2) {
3032                     bool firstAlive = keepNumbersAlive[i];
3033                     bool secondAlive = keepNumbersAlive[i + 1];
3034                     if (firstAlive && (collectionNumber == weakStrongIndex || collectionNumber == strongWeakIndex))
3035                         secondAlive = true;
3036                     if (firstAlive && secondAlive && collectionNumber < numberOfMapIndices) {
3037                         if (collectionNumber == weakStrongIndex) {
3038                             if (deleteAfterwards)
3039                                 EXPECT_EQ(i + 1, weakStrong->take(keepNumbersAlive[i])->value());
3040                         } else if (collectionNumber == strongWeakIndex) {
3041                             if (deleteAfterwards)
3042                                 EXPECT_EQ(i, strongWeak->take(keepNumbersAlive[i + 1])->value());
3043                         } else if (collectionNumber == weakWeakIndex) {
3044                             if (deleteAfterwards)
3045                                 EXPECT_EQ(i + 1, weakWeak->take(keepNumbersAlive[i])->value());
3046                         }
3047                         if (!deleteAfterwards)
3048                             count++;
3049                     } else if (collectionNumber == weakSetIndex && firstAlive) {
3050                         ASSERT_TRUE(weakSet->contains(keepNumbersAlive[i]));
3051                         if (deleteAfterwards)
3052                             weakSet->remove(keepNumbersAlive[i]);
3053                         else
3054                             count++;
3055                     } else if (collectionNumber == weakOrderedSetIndex && firstAlive) {
3056                         ASSERT_TRUE(weakOrderedSet->contains(keepNumbersAlive[i]));
3057                         if (deleteAfterwards)
3058                             weakOrderedSet->remove(keepNumbersAlive[i]);
3059                         else
3060                             count++;
3061                     }
3062                 }
3063                 if (addAfterwards) {
3064                     for (int i = 1000; i < 1100; i++) {
3065                         IntWrapper* wrapped = IntWrapper::create(i);
3066                         keepNumbersAlive.append(wrapped);
3067                         weakStrong->add(wrapped, wrapped);
3068                         strongWeak->add(wrapped, wrapped);
3069                         weakWeak->add(wrapped, wrapped);
3070                         weakSet->add(wrapped);
3071                         weakOrderedSet->add(wrapped);
3072                     }
3073                 }
3074                 if (collectionNumber == weakStrongIndex)
3075                     EXPECT_EQ(count + added, weakStrong->size());
3076                 else if (collectionNumber == strongWeakIndex)
3077                     EXPECT_EQ(count + added, strongWeak->size());
3078                 else if (collectionNumber == weakWeakIndex)
3079                     EXPECT_EQ(count + added, weakWeak->size());
3080                 else if (collectionNumber == weakSetIndex)
3081                     EXPECT_EQ(count + added, weakSet->size());
3082                 else if (collectionNumber == weakOrderedSetIndex)
3083                     EXPECT_EQ(count + added, weakOrderedSet->size());
3084                 WeakStrong::iterator it1 = weakStrong->begin();
3085                 StrongWeak::iterator it2 = strongWeak->begin();
3086                 WeakWeak::iterator it3 = weakWeak->begin();
3087                 WeakSet::iterator it4 = weakSet->begin();
3088                 WeakOrderedSet::iterator it5 = weakOrderedSet->begin();
3089                 MapIteratorCheck(it1, weakStrong->end(), (collectionNumber == weakStrongIndex ? count : 0) + added);
3090                 MapIteratorCheck(it2, strongWeak->end(), (collectionNumber == strongWeakIndex ? count : 0) + added);
3091                 MapIteratorCheck(it3, weakWeak->end(), (collectionNumber == weakWeakIndex ? count : 0) + added);
3092                 SetIteratorCheck(it4, weakSet->end(), (collectionNumber == weakSetIndex ? count : 0) + added);
3093                 SetIteratorCheck(it5, weakOrderedSet->end(), (collectionNumber == weakOrderedSetIndex ? count : 0) + added);
3094             }
3095             for (unsigned i = 0; i < 128 + added; i++)
3096                 keepNumbersAlive[i] = nullptr;
3097             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3098             EXPECT_EQ(added, weakStrong->size());
3099             EXPECT_EQ(added, strongWeak->size());
3100             EXPECT_EQ(added, weakWeak->size());
3101             EXPECT_EQ(added, weakSet->size());
3102             EXPECT_EQ(added, weakOrderedSet->size());
3103         }
3104     }
3105 }
3106
3107 TEST(HeapTest, RefCountedGarbageCollected)
3108 {
3109     RefCountedAndGarbageCollected::s_destructorCalls = 0;
3110     {
3111         RefPtr<RefCountedAndGarbageCollected> refPtr3;
3112         {
3113             Persistent<RefCountedAndGarbageCollected> persistent;
3114             {
3115                 RefPtr<RefCountedAndGarbageCollected> refPtr1 = RefCountedAndGarbageCollected::create();
3116                 RefPtr<RefCountedAndGarbageCollected> refPtr2 = RefCountedAndGarbageCollected::create();
3117                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3118                 EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3119                 persistent = refPtr1.get();
3120             }
3121             // Reference count is zero for both objects but one of
3122             // them is kept alive by a persistent handle.
3123             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3124             EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
3125             refPtr3 = persistent;
3126         }
3127         // The persistent handle is gone but the ref count has been
3128         // increased to 1.
3129         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3130         EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
3131     }
3132     // Both persistent handle is gone and ref count is zero so the
3133     // object can be collected.
3134     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3135     EXPECT_EQ(2, RefCountedAndGarbageCollected::s_destructorCalls);
3136 }
3137
3138 TEST(HeapTest, RefCountedGarbageCollectedWithStackPointers)
3139 {
3140     RefCountedAndGarbageCollected::s_destructorCalls = 0;
3141     RefCountedAndGarbageCollected2::s_destructorCalls = 0;
3142     {
3143         RefCountedAndGarbageCollected* pointer1 = 0;
3144         RefCountedAndGarbageCollected2* pointer2 = 0;
3145         {
3146             RefPtr<RefCountedAndGarbageCollected> object1 = RefCountedAndGarbageCollected::create();
3147             RefPtr<RefCountedAndGarbageCollected2> object2 = RefCountedAndGarbageCollected2::create();
3148             pointer1 = object1.get();
3149             pointer2 = object2.get();
3150             void* objects[2] = { object1.get(), object2.get() };
3151             RefCountedGarbageCollectedVisitor visitor(2, objects);
3152             ThreadState::current()->visitPersistents(&visitor);
3153             EXPECT_TRUE(visitor.validate());
3154
3155             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3156             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3157             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3158         }
3159         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3160         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3161         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3162
3163         // At this point, the reference counts of object1 and object2 are 0.
3164         // Only pointer1 and pointer2 keep references to object1 and object2.
3165         void* objects[] = { 0 };
3166         RefCountedGarbageCollectedVisitor visitor(0, objects);
3167         ThreadState::current()->visitPersistents(&visitor);
3168         EXPECT_TRUE(visitor.validate());
3169
3170         {
3171             RefPtr<RefCountedAndGarbageCollected> object1(pointer1);
3172             RefPtr<RefCountedAndGarbageCollected2> object2(pointer2);
3173             void* objects[2] = { object1.get(), object2.get() };
3174             RefCountedGarbageCollectedVisitor visitor(2, objects);
3175             ThreadState::current()->visitPersistents(&visitor);
3176             EXPECT_TRUE(visitor.validate());
3177
3178             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3179             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3180             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3181         }
3182
3183         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3184         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3185         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3186     }
3187
3188     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3189     EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
3190     EXPECT_EQ(1, RefCountedAndGarbageCollected2::s_destructorCalls);
3191 }
3192
3193 TEST(HeapTest, WeakMembers)
3194 {
3195     Bar::s_live = 0;
3196     {
3197         Persistent<Bar> h1 = Bar::create();
3198         Persistent<Weak> h4;
3199         Persistent<WithWeakMember> h5;
3200         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3201         ASSERT_EQ(1u, Bar::s_live); // h1 is live.
3202         {
3203             Bar* h2 = Bar::create();
3204             Bar* h3 = Bar::create();
3205             h4 = Weak::create(h2, h3);
3206             h5 = WithWeakMember::create(h2, h3);
3207             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3208             EXPECT_EQ(5u, Bar::s_live); // The on-stack pointer keeps h3 alive.
3209             EXPECT_TRUE(h4->strongIsThere());
3210             EXPECT_TRUE(h4->weakIsThere());
3211             EXPECT_TRUE(h5->strongIsThere());
3212             EXPECT_TRUE(h5->weakIsThere());
3213         }
3214         // h3 is collected, weak pointers from h4 and h5 don't keep it alive.
3215         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3216         EXPECT_EQ(4u, Bar::s_live);
3217         EXPECT_TRUE(h4->strongIsThere());
3218         EXPECT_FALSE(h4->weakIsThere()); // h3 is gone from weak pointer.
3219         EXPECT_TRUE(h5->strongIsThere());
3220         EXPECT_FALSE(h5->weakIsThere()); // h3 is gone from weak pointer.
3221         h1.release(); // Zero out h1.
3222         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3223         EXPECT_EQ(3u, Bar::s_live); // Only h4, h5 and h2 are left.
3224         EXPECT_TRUE(h4->strongIsThere()); // h2 is still pointed to from h4.
3225         EXPECT_TRUE(h5->strongIsThere()); // h2 is still pointed to from h5.
3226     }
3227     // h4 and h5 have gone out of scope now and they were keeping h2 alive.
3228     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3229     EXPECT_EQ(0u, Bar::s_live); // All gone.
3230 }
3231
3232 TEST(HeapTest, FinalizationObserver)
3233 {
3234     Persistent<FinalizationObserver<Observable> > o;
3235     {
3236         Observable* foo = Observable::create(Bar::create());
3237         // |o| observes |foo|.
3238         o = FinalizationObserver<Observable>::create(foo);
3239     }
3240     // FinalizationObserver doesn't have a strong reference to |foo|. So |foo|
3241     // and its member will be collected.
3242     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3243     EXPECT_EQ(0u, Bar::s_live);
3244     EXPECT_TRUE(o->didCallWillFinalize());
3245
3246     FinalizationObserverWithHashMap::s_didCallWillFinalize = false;
3247     Observable* foo = Observable::create(Bar::create());
3248     FinalizationObserverWithHashMap::ObserverMap& map = FinalizationObserverWithHashMap::observe(*foo);
3249     EXPECT_EQ(1u, map.size());
3250     foo = 0;
3251     // FinalizationObserverWithHashMap doesn't have a strong reference to
3252     // |foo|. So |foo| and its member will be collected.
3253     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3254     EXPECT_EQ(0u, Bar::s_live);
3255     EXPECT_EQ(0u, map.size());
3256     EXPECT_TRUE(FinalizationObserverWithHashMap::s_didCallWillFinalize);
3257 }
3258
3259 TEST(HeapTest, Comparisons)
3260 {
3261     Persistent<Bar> barPersistent = Bar::create();
3262     Persistent<Foo> fooPersistent = Foo::create(barPersistent);
3263     EXPECT_TRUE(barPersistent != fooPersistent);
3264     barPersistent = fooPersistent;
3265     EXPECT_TRUE(barPersistent == fooPersistent);
3266 }
3267
3268 TEST(HeapTest, CheckAndMarkPointer)
3269 {
3270     HeapStats initialHeapStats;
3271     clearOutOldGarbage(&initialHeapStats);
3272
3273     Vector<Address> objectAddresses;
3274     Vector<Address> endAddresses;
3275     Address largeObjectAddress;
3276     Address largeObjectEndAddress;
3277     CountingVisitor visitor;
3278     for (int i = 0; i < 10; i++) {
3279         SimpleObject* object = SimpleObject::create();
3280         Address objectAddress = reinterpret_cast<Address>(object);
3281         objectAddresses.append(objectAddress);
3282         endAddresses.append(objectAddress + sizeof(SimpleObject) - 1);
3283     }
3284     LargeObject* largeObject = LargeObject::create();
3285     largeObjectAddress = reinterpret_cast<Address>(largeObject);
3286     largeObjectEndAddress = largeObjectAddress + sizeof(LargeObject) - 1;
3287
3288     // This is a low-level test where we call checkAndMarkPointer. This method
3289     // causes the object start bitmap to be computed which requires the heap
3290     // to be in a consistent state (e.g. the free allocation area must be put
3291     // into a free list header). However when we call makeConsistentForGC it
3292     // also clears out the freelists so we have to rebuild those before trying
3293     // to allocate anything again. We do this by forcing a GC after doing the
3294     // checkAndMarkPointer tests.
3295     {
3296         TestGCScope scope(ThreadState::HeapPointersOnStack);
3297         EXPECT_TRUE(scope.allThreadsParked()); // Fail the test if we could not park all threads.
3298         Heap::makeConsistentForGC();
3299         for (size_t i = 0; i < objectAddresses.size(); i++) {
3300             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, objectAddresses[i]));
3301             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, endAddresses[i]));
3302         }
3303         EXPECT_EQ(objectAddresses.size() * 2, visitor.count());
3304         visitor.reset();
3305         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectAddress));
3306         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress));
3307         EXPECT_EQ(2ul, visitor.count());
3308         visitor.reset();
3309     }
3310     // This forces a GC without stack scanning which results in the objects
3311     // being collected. This will also rebuild the above mentioned freelists,
3312     // however we don't rely on that below since we don't have any allocations.
3313     clearOutOldGarbage(&initialHeapStats);
3314     {
3315         TestGCScope scope(ThreadState::HeapPointersOnStack);
3316         EXPECT_TRUE(scope.allThreadsParked());
3317         Heap::makeConsistentForGC();
3318         for (size_t i = 0; i < objectAddresses.size(); i++) {
3319             EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, objectAddresses[i]));
3320             EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, endAddresses[i]));
3321         }
3322         EXPECT_EQ(0ul, visitor.count());
3323         EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, largeObjectAddress));
3324         EXPECT_FALSE(Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress));
3325         EXPECT_EQ(0ul, visitor.count());
3326     }
3327     // This round of GC is important to make sure that the object start
3328     // bitmap are cleared out and that the free lists are rebuild.
3329     clearOutOldGarbage(&initialHeapStats);
3330 }
3331
3332 TEST(HeapTest, VisitOffHeapCollections)
3333 {
3334     HeapStats initialHeapStats;
3335     clearOutOldGarbage(&initialHeapStats);
3336     IntWrapper::s_destructorCalls = 0;
3337     Persistent<OffHeapContainer> container = OffHeapContainer::create();
3338     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3339     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3340     container = nullptr;
3341     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3342     EXPECT_EQ(OffHeapContainer::deadWrappers, IntWrapper::s_destructorCalls);
3343 }
3344
3345 TEST(HeapTest, PersistentHeapCollectionTypes)
3346 {
3347     HeapStats initialHeapSize;
3348     IntWrapper::s_destructorCalls = 0;
3349
3350     typedef HeapVector<Member<IntWrapper> > Vec;
3351     typedef PersistentHeapVector<Member<IntWrapper> > PVec;
3352     typedef PersistentHeapHashSet<Member<IntWrapper> > PSet;
3353     typedef PersistentHeapListHashSet<Member<IntWrapper> > PListSet;
3354     typedef PersistentHeapLinkedHashSet<Member<IntWrapper> > PLinkedSet;
3355     typedef PersistentHeapHashMap<Member<IntWrapper>, Member<IntWrapper> > PMap;
3356     typedef PersistentHeapDeque<Member<IntWrapper> > PDeque;
3357
3358     clearOutOldGarbage(&initialHeapSize);
3359     {
3360         PVec pVec;
3361         PDeque pDeque;
3362         PSet pSet;
3363         PListSet pListSet;
3364         PLinkedSet pLinkedSet;
3365         PMap pMap;
3366
3367         IntWrapper* one(IntWrapper::create(1));
3368         IntWrapper* two(IntWrapper::create(2));
3369         IntWrapper* three(IntWrapper::create(3));
3370         IntWrapper* four(IntWrapper::create(4));
3371         IntWrapper* five(IntWrapper::create(5));
3372         IntWrapper* six(IntWrapper::create(6));
3373         IntWrapper* seven(IntWrapper::create(7));
3374         IntWrapper* eight(IntWrapper::create(8));
3375         IntWrapper* nine(IntWrapper::create(9));
3376
3377         pVec.append(one);
3378         pVec.append(two);
3379
3380         pDeque.append(seven);
3381         pDeque.append(two);
3382
3383         Vec* vec = new Vec();
3384         vec->swap(pVec);
3385
3386         pVec.append(two);
3387         pVec.append(three);
3388
3389         pSet.add(four);
3390         pListSet.add(eight);
3391         pLinkedSet.add(nine);
3392         pMap.add(five, six);
3393
3394         // Collect |vec| and |one|.
3395         vec = 0;
3396         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3397         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
3398
3399         EXPECT_EQ(2u, pVec.size());
3400         EXPECT_EQ(two, pVec.at(0));
3401         EXPECT_EQ(three, pVec.at(1));
3402
3403         EXPECT_EQ(2u, pDeque.size());
3404         EXPECT_EQ(seven, pDeque.first());
3405         EXPECT_EQ(seven, pDeque.takeFirst());
3406         EXPECT_EQ(two, pDeque.first());
3407
3408         EXPECT_EQ(1u, pDeque.size());
3409
3410         EXPECT_EQ(1u, pSet.size());
3411         EXPECT_TRUE(pSet.contains(four));
3412
3413         EXPECT_EQ(1u, pListSet.size());
3414         EXPECT_TRUE(pListSet.contains(eight));
3415
3416         EXPECT_EQ(1u, pLinkedSet.size());
3417         EXPECT_TRUE(pLinkedSet.contains(nine));
3418
3419         EXPECT_EQ(1u, pMap.size());
3420         EXPECT_EQ(six, pMap.get(five));
3421     }
3422
3423     // Collect previous roots.
3424     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3425     EXPECT_EQ(9, IntWrapper::s_destructorCalls);
3426 }
3427
3428 TEST(HeapTest, CollectionNesting)
3429 {
3430     HeapStats initialStats;
3431     clearOutOldGarbage(&initialStats);
3432     int* key = &IntWrapper::s_destructorCalls;
3433     IntWrapper::s_destructorCalls = 0;
3434     typedef HeapVector<Member<IntWrapper> > IntVector;
3435     typedef HeapDeque<Member<IntWrapper> > IntDeque;
3436     HeapHashMap<void*, IntVector>* map = new HeapHashMap<void*, IntVector>();
3437     HeapHashMap<void*, IntDeque>* map2 = new HeapHashMap<void*, IntDeque>();
3438
3439     map->add(key, IntVector());
3440     map2->add(key, IntDeque());
3441
3442     HeapHashMap<void*, IntVector>::iterator it = map->find(key);
3443     EXPECT_EQ(0u, map->get(key).size());
3444
3445     HeapHashMap<void*, IntDeque>::iterator it2 = map2->find(key);
3446     EXPECT_EQ(0u, map2->get(key).size());
3447
3448     it->value.append(IntWrapper::create(42));
3449     EXPECT_EQ(1u, map->get(key).size());
3450
3451     it2->value.append(IntWrapper::create(42));
3452     EXPECT_EQ(1u, map2->get(key).size());
3453
3454     Persistent<HeapHashMap<void*, IntVector> > keepAlive(map);
3455     Persistent<HeapHashMap<void*, IntDeque> > keepAlive2(map2);
3456
3457     for (int i = 0; i < 100; i++) {
3458         map->add(key + 1 + i, IntVector());
3459         map2->add(key + 1 + i, IntDeque());
3460     }
3461
3462     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3463
3464     EXPECT_EQ(1u, map->get(key).size());
3465     EXPECT_EQ(1u, map2->get(key).size());
3466     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3467
3468     keepAlive = nullptr;
3469     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3470     EXPECT_EQ(1, IntWrapper::s_destructorCalls);
3471 }
3472
3473 TEST(HeapTest, GarbageCollectedMixin)
3474 {
3475     HeapStats initialHeapStats;
3476     clearOutOldGarbage(&initialHeapStats);
3477
3478     Persistent<UseMixin> usemixin = UseMixin::create();
3479     EXPECT_EQ(0, UseMixin::s_traceCount);
3480     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3481     EXPECT_EQ(1, UseMixin::s_traceCount);
3482
3483     Persistent<Mixin> mixin = usemixin;
3484     usemixin = nullptr;
3485     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3486     EXPECT_EQ(2, UseMixin::s_traceCount);
3487
3488     PersistentHeapHashSet<WeakMember<Mixin> > weakMap;
3489     weakMap.add(UseMixin::create());
3490     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3491     EXPECT_EQ(0u, weakMap.size());
3492 }
3493
3494 TEST(HeapTest, CollectionNesting2)
3495 {
3496     HeapStats initialStats;
3497     clearOutOldGarbage(&initialStats);
3498     void* key = &IntWrapper::s_destructorCalls;
3499     IntWrapper::s_destructorCalls = 0;
3500     typedef HeapHashSet<Member<IntWrapper> > IntSet;
3501     HeapHashMap<void*, IntSet>* map = new HeapHashMap<void*, IntSet>();
3502
3503     map->add(key, IntSet());
3504
3505     HeapHashMap<void*, IntSet>::iterator it = map->find(key);
3506     EXPECT_EQ(0u, map->get(key).size());
3507
3508     it->value.add(IntWrapper::create(42));
3509     EXPECT_EQ(1u, map->get(key).size());
3510
3511     Persistent<HeapHashMap<void*, IntSet> > keepAlive(map);
3512     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3513     EXPECT_EQ(1u, map->get(key).size());
3514     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3515 }
3516
3517 TEST(HeapTest, CollectionNesting3)
3518 {
3519     HeapStats initialStats;
3520     clearOutOldGarbage(&initialStats);
3521     IntWrapper::s_destructorCalls = 0;
3522     typedef HeapVector<Member<IntWrapper> > IntVector;
3523     typedef HeapDeque<Member<IntWrapper> > IntDeque;
3524     HeapVector<IntVector>* vector = new HeapVector<IntVector>();
3525     HeapDeque<IntDeque>* deque = new HeapDeque<IntDeque>();
3526
3527     vector->append(IntVector());
3528     deque->append(IntDeque());
3529
3530     HeapVector<IntVector>::iterator it = vector->begin();
3531     HeapDeque<IntDeque>::iterator it2 = deque->begin();
3532     EXPECT_EQ(0u, it->size());
3533     EXPECT_EQ(0u, it2->size());
3534
3535     it->append(IntWrapper::create(42));
3536     it2->append(IntWrapper::create(42));
3537     EXPECT_EQ(1u, it->size());
3538     EXPECT_EQ(1u, it2->size());
3539
3540     Persistent<HeapVector<IntVector> > keepAlive(vector);
3541     Persistent<HeapDeque<IntDeque> > keepAlive2(deque);
3542     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3543     EXPECT_EQ(1u, it->size());
3544     EXPECT_EQ(1u, it2->size());
3545     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3546 }
3547
3548 TEST(HeapTest, EmbeddedInVector)
3549 {
3550     HeapStats initialStats;
3551     clearOutOldGarbage(&initialStats);
3552     SimpleFinalizedObject::s_destructorCalls = 0;
3553     {
3554         PersistentHeapVector<VectorObject, 2> inlineVector;
3555         PersistentHeapVector<VectorObject> outlineVector;
3556         VectorObject i1, i2;
3557         inlineVector.append(i1);
3558         inlineVector.append(i2);
3559
3560         VectorObject o1, o2;
3561         outlineVector.append(o1);
3562         outlineVector.append(o2);
3563
3564         PersistentHeapVector<VectorObjectInheritedTrace> vectorInheritedTrace;
3565         VectorObjectInheritedTrace it1, it2;
3566         vectorInheritedTrace.append(it1);
3567         vectorInheritedTrace.append(it2);
3568
3569         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3570         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
3571
3572         // Since VectorObjectNoTrace has no trace method it will
3573         // not be traced and hence be collected when doing GC.
3574         // We trace items in a collection braced on the item's
3575         // having a trace method. This is determined via the
3576         // NeedsTracing trait in wtf/TypeTraits.h.
3577         PersistentHeapVector<VectorObjectNoTrace> vectorNoTrace;
3578         VectorObjectNoTrace n1, n2;
3579         vectorNoTrace.append(n1);
3580         vectorNoTrace.append(n2);
3581         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3582         EXPECT_EQ(2, SimpleFinalizedObject::s_destructorCalls);
3583     }
3584     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3585     EXPECT_EQ(8, SimpleFinalizedObject::s_destructorCalls);
3586 }
3587
3588 TEST(HeapTest, EmbeddedInDeque)
3589 {
3590     HeapStats initialStats;
3591     clearOutOldGarbage(&initialStats);
3592     SimpleFinalizedObject::s_destructorCalls = 0;
3593     {
3594         PersistentHeapDeque<VectorObject, 2> inlineDeque;
3595         PersistentHeapDeque<VectorObject> outlineDeque;
3596         VectorObject i1, i2;
3597         inlineDeque.append(i1);
3598         inlineDeque.append(i2);
3599
3600         VectorObject o1, o2;
3601         outlineDeque.append(o1);
3602         outlineDeque.append(o2);
3603
3604         PersistentHeapDeque<VectorObjectInheritedTrace> dequeInheritedTrace;
3605         VectorObjectInheritedTrace it1, it2;
3606         dequeInheritedTrace.append(it1);
3607         dequeInheritedTrace.append(it2);
3608
3609         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3610         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
3611
3612         // Since VectorObjectNoTrace has no trace method it will
3613         // not be traced and hence be collected when doing GC.
3614         // We trace items in a collection braced on the item's
3615         // having a trace method. This is determined via the
3616         // NeedsTracing trait in wtf/TypeTraits.h.
3617         PersistentHeapDeque<VectorObjectNoTrace> dequeNoTrace;
3618         VectorObjectNoTrace n1, n2;
3619         dequeNoTrace.append(n1);
3620         dequeNoTrace.append(n2);
3621         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3622         EXPECT_EQ(2, SimpleFinalizedObject::s_destructorCalls);
3623     }
3624     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3625     EXPECT_EQ(8, SimpleFinalizedObject::s_destructorCalls);
3626 }
3627
3628 template<typename Set>
3629 void rawPtrInHashHelper()
3630 {
3631     Set set;
3632     set.add(new int(42));
3633     set.add(new int(42));
3634     EXPECT_EQ(2u, set.size());
3635     for (typename Set::iterator it = set.begin(); it != set.end(); ++it)
3636         EXPECT_EQ(42, **it);
3637 }
3638
3639 TEST(HeapTest, RawPtrInHash)
3640 {
3641     rawPtrInHashHelper<HashSet<RawPtr<int> > >();
3642     rawPtrInHashHelper<ListHashSet<RawPtr<int> > >();
3643     rawPtrInHashHelper<LinkedHashSet<RawPtr<int> > >();
3644 }
3645
3646 TEST(HeapTest, HeapTerminatedArray)
3647 {
3648     HeapStats initialHeapSize;
3649     clearOutOldGarbage(&initialHeapSize);
3650     IntWrapper::s_destructorCalls = 0;
3651
3652     HeapTerminatedArray<TerminatedArrayItem>* arr = 0;
3653
3654     const size_t prefixSize = 4;
3655     const size_t suffixSize = 4;
3656
3657     {
3658         HeapTerminatedArrayBuilder<TerminatedArrayItem> builder(arr);
3659         builder.grow(prefixSize);
3660         for (size_t i = 0; i < prefixSize; i++)
3661             builder.append(TerminatedArrayItem(IntWrapper::create(i)));
3662         arr = builder.release();
3663     }
3664
3665     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3666     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3667     EXPECT_EQ(prefixSize, arr->size());
3668     for (size_t i = 0; i < prefixSize; i++)
3669         EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
3670
3671     {
3672         HeapTerminatedArrayBuilder<TerminatedArrayItem> builder(arr);
3673         builder.grow(suffixSize);
3674         for (size_t i = 0; i < suffixSize; i++)
3675             builder.append(TerminatedArrayItem(IntWrapper::create(prefixSize + i)));
3676         arr = builder.release();
3677     }
3678
3679     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3680     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3681     EXPECT_EQ(prefixSize + suffixSize, arr->size());
3682     for (size_t i = 0; i < prefixSize + suffixSize; i++)
3683         EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
3684
3685     {
3686         Persistent<HeapTerminatedArray<TerminatedArrayItem> > persistentArr = arr;
3687         arr = 0;
3688         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3689         arr = persistentArr.get();
3690         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3691         EXPECT_EQ(prefixSize + suffixSize, arr->size());
3692         for (size_t i = 0; i < prefixSize + suffixSize; i++)
3693             EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
3694     }
3695
3696     arr = 0;
3697     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3698     EXPECT_EQ(8, IntWrapper::s_destructorCalls);
3699 }
3700
3701 TEST(HeapTest, HeapLinkedStack)
3702 {
3703     HeapStats initialHeapSize;
3704     clearOutOldGarbage(&initialHeapSize);
3705     IntWrapper::s_destructorCalls = 0;
3706
3707     HeapLinkedStack<TerminatedArrayItem>* stack = new HeapLinkedStack<TerminatedArrayItem>();
3708
3709     const size_t stackSize = 10;
3710
3711     for (size_t i = 0; i < stackSize; i++)
3712         stack->push(TerminatedArrayItem(IntWrapper::create(i)));
3713
3714     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3715     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3716     EXPECT_EQ(stackSize, stack->size());
3717     while (!stack->isEmpty()) {
3718         EXPECT_EQ(stack->size() - 1, static_cast<size_t>(stack->peek().payload()->value()));
3719         stack->pop();
3720     }
3721
3722     Persistent<HeapLinkedStack<TerminatedArrayItem> > pStack = stack;
3723
3724     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3725     EXPECT_EQ(stackSize, static_cast<size_t>(IntWrapper::s_destructorCalls));
3726     EXPECT_EQ(0u, pStack->size());
3727 }
3728
3729 TEST(HeapTest, AllocationDuringFinalization)
3730 {
3731     HeapStats initialHeapSize;
3732     clearOutOldGarbage(&initialHeapSize);
3733     IntWrapper::s_destructorCalls = 0;
3734     OneKiloByteObject::s_destructorCalls = 0;
3735
3736     Persistent<IntWrapper> wrapper;
3737     new FinalizationAllocator(&wrapper);
3738
3739     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3740     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3741     // Check that the wrapper allocated during finalization is not
3742     // swept away and zapped later in the same sweeping phase.
3743     EXPECT_EQ(42, wrapper->value());
3744
3745     wrapper.clear();
3746     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3747     EXPECT_EQ(10, IntWrapper::s_destructorCalls);
3748     EXPECT_EQ(512, OneKiloByteObject::s_destructorCalls);
3749 }
3750
3751 class SimpleClassWithDestructor {
3752 public:
3753     SimpleClassWithDestructor() { }
3754     ~SimpleClassWithDestructor()
3755     {
3756         s_wasDestructed = true;
3757     }
3758     static bool s_wasDestructed;
3759 };
3760
3761 bool SimpleClassWithDestructor::s_wasDestructed;
3762
3763 class RefCountedWithDestructor : public RefCounted<RefCountedWithDestructor> {
3764 public:
3765     RefCountedWithDestructor() { }
3766     ~RefCountedWithDestructor()
3767     {
3768         s_wasDestructed = true;
3769     }
3770     static bool s_wasDestructed;
3771 };
3772
3773 bool RefCountedWithDestructor::s_wasDestructed;
3774
3775 template<typename Set>
3776 void destructorsCalledOnGC(bool addLots)
3777 {
3778     RefCountedWithDestructor::s_wasDestructed = false;
3779     {
3780         Set set;
3781         RefCountedWithDestructor* hasDestructor = new RefCountedWithDestructor();
3782         set.add(adoptRef(hasDestructor));
3783         EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3784
3785         if (addLots) {
3786             for (int i = 0; i < 1000; i++) {
3787                 set.add(adoptRef(new RefCountedWithDestructor()));
3788             }
3789         }
3790
3791         EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3792         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3793         EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3794     }
3795     // The destructors of the sets don't call the destructors of the elements
3796     // in the heap sets. You have to actually remove the elments, call clear()
3797     // or have a GC to get the destructors called.
3798     EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3799     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3800     EXPECT_TRUE(RefCountedWithDestructor::s_wasDestructed);
3801 }
3802
3803 template<typename Set>
3804 void destructorsCalledOnClear(bool addLots)
3805 {
3806     RefCountedWithDestructor::s_wasDestructed = false;
3807     Set set;
3808     RefCountedWithDestructor* hasDestructor = new RefCountedWithDestructor();
3809     set.add(adoptRef(hasDestructor));
3810     EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3811
3812     if (addLots) {
3813         for (int i = 0; i < 1000; i++) {
3814             set.add(adoptRef(new RefCountedWithDestructor()));
3815         }
3816     }
3817
3818     EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3819     set.clear();
3820     EXPECT_TRUE(RefCountedWithDestructor::s_wasDestructed);
3821 }
3822
3823 TEST(HeapTest, DestructorsCalled)
3824 {
3825     HeapHashMap<SimpleClassWithDestructor*, OwnPtr<SimpleClassWithDestructor> > map;
3826     SimpleClassWithDestructor* hasDestructor = new SimpleClassWithDestructor();
3827     map.add(hasDestructor, adoptPtr(hasDestructor));
3828     SimpleClassWithDestructor::s_wasDestructed = false;
3829     map.clear();
3830     EXPECT_TRUE(SimpleClassWithDestructor::s_wasDestructed);
3831
3832     destructorsCalledOnClear<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3833     destructorsCalledOnClear<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3834     destructorsCalledOnClear<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3835     destructorsCalledOnClear<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3836     destructorsCalledOnClear<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3837     destructorsCalledOnClear<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3838
3839     destructorsCalledOnGC<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3840     destructorsCalledOnGC<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3841     destructorsCalledOnGC<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3842     destructorsCalledOnGC<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3843     destructorsCalledOnGC<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3844     destructorsCalledOnGC<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3845 }
3846
3847 class MixinA : public GarbageCollectedMixin {
3848 public:
3849     MixinA() : m_obj(IntWrapper::create(100)) { }
3850     virtual void trace(Visitor* visitor)
3851     {
3852         visitor->trace(m_obj);
3853     }
3854     Member<IntWrapper> m_obj;
3855 };
3856
3857 class MixinB : public GarbageCollectedMixin {
3858 public:
3859     MixinB() : m_obj(IntWrapper::create(101)) { }
3860     virtual void trace(Visitor* visitor)
3861     {
3862         visitor->trace(m_obj);
3863     }
3864     Member<IntWrapper> m_obj;
3865 };
3866
3867 class MultipleMixins : public GarbageCollected<MultipleMixins>, public MixinA, public MixinB {
3868     USING_GARBAGE_COLLECTED_MIXIN(MultipleMixins);
3869 public:
3870     MultipleMixins() : m_obj(IntWrapper::create(102)) { }
3871     virtual void trace(Visitor* visitor)
3872     {
3873         visitor->trace(m_obj);
3874         MixinA::trace(visitor);
3875         MixinB::trace(visitor);
3876     }
3877     Member<IntWrapper> m_obj;
3878 };
3879
3880 static const bool s_isMixinTrue = IsGarbageCollectedMixin<MultipleMixins>::value;
3881 static const bool s_isMixinFalse = IsGarbageCollectedMixin<IntWrapper>::value;
3882
3883 TEST(HeapTest, MultipleMixins)
3884 {
3885     EXPECT_TRUE(s_isMixinTrue);
3886     EXPECT_FALSE(s_isMixinFalse);
3887
3888     HeapStats initialHeapSize;
3889     clearOutOldGarbage(&initialHeapSize);
3890     IntWrapper::s_destructorCalls = 0;
3891     MultipleMixins* obj = new MultipleMixins();
3892     {
3893         Persistent<MixinA> a = obj;
3894         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3895         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3896     }
3897     {
3898         Persistent<MixinB> b = obj;
3899         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3900         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3901     }
3902     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3903     EXPECT_EQ(3, IntWrapper::s_destructorCalls);
3904 }
3905
3906 class GCParkingThreadTester {
3907 public:
3908     static void test()
3909     {
3910         createThread(&sleeperMainFunc, 0, "SleepingThread");
3911
3912         // Wait for the sleeper to run.
3913         while (!s_sleeperRunning) {
3914             yield();
3915         }
3916
3917         {
3918             // Expect the first attempt to park the sleeping thread to fail
3919             TestGCScope scope(ThreadState::NoHeapPointersOnStack);
3920             EXPECT_FALSE(scope.allThreadsParked());
3921         }
3922
3923         s_sleeperDone = true;
3924
3925         // Wait for the sleeper to finish.
3926         while (s_sleeperRunning) {
3927             // We enter the safepoint here since the sleeper thread will detach
3928             // causing it to GC.
3929             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
3930             yield();
3931         }
3932         {
3933             // Since the sleeper thread has detached this is the only thread.
3934             TestGCScope scope(ThreadState::NoHeapPointersOnStack);
3935             EXPECT_TRUE(scope.allThreadsParked());
3936         }
3937     }
3938
3939 private:
3940     static void sleeperMainFunc(void* data)
3941     {
3942         ThreadState::attach();
3943         s_sleeperRunning = true;
3944
3945         // Simulate a long running op that is not entering a safepoint.
3946         while (!s_sleeperDone) {
3947             yield();
3948         }
3949
3950         ThreadState::detach();
3951         s_sleeperRunning = false;
3952     }
3953
3954     static volatile bool s_sleeperRunning;
3955     static volatile bool s_sleeperDone;
3956 };
3957
3958 volatile bool GCParkingThreadTester::s_sleeperRunning = false;
3959 volatile bool GCParkingThreadTester::s_sleeperDone = false;
3960
3961 TEST(HeapTest, GCParkingTimeout)
3962 {
3963     GCParkingThreadTester::test();
3964 }
3965
3966 } // WebCore namespace