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 blink {
  46
  47 class IntWrapper : public GarbageCollectedFinalized<IntWrapper> {
  48 public:
  49     static IntWrapper* create(int x)
  50     {
  51         return new IntWrapper(x);
  52     }
  53
  54     virtual ~IntWrapper()
  55     {
  56         ++s_destructorCalls;
  57     }
  58
  59     static int s_destructorCalls;
  60     static void trace(Visitor*) { }
  61
  62     int value() const { return m_x; }
  63
  64     bool operator==(const IntWrapper& other) const { return other.value() == value(); }
  65
  66     unsigned hash() { return IntHash<int>::hash(m_x); }
  67
  68 protected:
  69     IntWrapper(int x) : m_x(x) { }
  70
  71 private:
  72     IntWrapper();
  73     int m_x;
  74 };
  75
  76 USED_FROM_MULTIPLE_THREADS(IntWrapper);
  77
  78 class ThreadMarker {
  79 public:
  80     ThreadMarker() : m_creatingThread(reinterpret_cast<ThreadState*>(0)), m_num(0) { }
  81     ThreadMarker(unsigned i) : m_creatingThread(ThreadState::current()), m_num(i) { }
  82     ThreadMarker(WTF::HashTableDeletedValueType deleted) : m_creatingThread(reinterpret_cast<ThreadState*>(-1)), m_num(0) { }
  83     ~ThreadMarker()
  84     {
  85         EXPECT_TRUE((m_creatingThread == ThreadState::current())
  86             || (m_creatingThread == reinterpret_cast<ThreadState*>(0))
  87             || (m_creatingThread == reinterpret_cast<ThreadState*>(-1)));
  88     }
  89     bool isHashTableDeletedValue() const { return m_creatingThread == reinterpret_cast<ThreadState*>(-1); }
  90     bool operator==(const ThreadMarker& other) const { return other.m_creatingThread == m_creatingThread && other.m_num == m_num; }
  91     ThreadState* m_creatingThread;
  92     unsigned m_num;
  93 };
  94
  95 struct ThreadMarkerHash {
  96     static unsigned hash(const ThreadMarker& key)
  97     {
  98         return static_cast<unsigned>(reinterpret_cast<uintptr_t>(key.m_creatingThread) + key.m_num);
  99     }
 100
 101     static bool equal(const ThreadMarker& a, const ThreadMarker& b)
 102     {
 103         return a == b;
 104     }
 105
 106     static const bool safeToCompareToEmptyOrDeleted = false;
 107 };
 108
 109 typedef std::pair<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeakPair;
 110
 111 struct PairWithWeakHandling : public StrongWeakPair {
 112     ALLOW_ONLY_INLINE_ALLOCATION();
 113
 114 public:
 115     // Regular constructor.
 116     PairWithWeakHandling(IntWrapper* one, IntWrapper* two)
 117         : StrongWeakPair(one, two)
 118     {
 119         ASSERT(one); // We use null first field to indicate empty slots in the hash table.
 120     }
 121
 122     // The HashTable (via the HashTrait) calls this constructor with a
 123     // placement new to mark slots in the hash table as being deleted. We will
 124     // never call trace or the destructor on these slots. We mark ourselves deleted
 125     // with a pointer to -1 in the first field.
 126     PairWithWeakHandling(WTF::HashTableDeletedValueType)
 127         : StrongWeakPair(reinterpret_cast<IntWrapper*>(-1), nullptr)
 128     {
 129     }
 130
 131     // Used by the HashTable (via the HashTrait) to skip deleted slots in the
 132     // table. Recognizes objects that were 'constructed' using the above
 133     // constructor.
 134     bool isHashTableDeletedValue() const { return first == reinterpret_cast<IntWrapper*>(-1); }
 135
 136     // Since we don't allocate independent objects of this type, we don't need
 137     // a regular trace method. Instead, we use a traceInCollection method. If
 138     // the entry should be deleted from the collection we return true and don't
 139     // trace the strong pointer.
 140     bool traceInCollection(Visitor* visitor, WTF::ShouldWeakPointersBeMarkedStrongly strongify)
 141     {
 142         visitor->traceInCollection(second, strongify);
 143         if (!visitor->isAlive(second))
 144             return true;
 145         visitor->trace(first);
 146         return false;
 147     }
 148 };
 149
 150 }
 151
 152 namespace WTF {
 153
 154 template<typename T> struct DefaultHash;
 155 template<> struct DefaultHash<blink::ThreadMarker> {
 156     typedef blink::ThreadMarkerHash Hash;
 157 };
 158
 159 // ThreadMarkerHash is the default hash for ThreadMarker
 160 template<> struct HashTraits<blink::ThreadMarker> : GenericHashTraits<blink::ThreadMarker> {
 161     static const bool emptyValueIsZero = true;
 162     static void constructDeletedValue(blink::ThreadMarker& slot) { new (NotNull, &slot) blink::ThreadMarker(HashTableDeletedValue); }
 163     static bool isDeletedValue(const blink::ThreadMarker& slot) { return slot.isHashTableDeletedValue(); }
 164 };
 165
 166 // The hash algorithm for our custom pair class is just the standard double
 167 // hash for pairs. Note that this means you can't mutate either of the parts of
 168 // the pair while they are in the hash table, as that would change their hash
 169 // code and thus their preferred placement in the table.
 170 template<> struct DefaultHash<blink::PairWithWeakHandling> {
 171     typedef PairHash<blink::Member<blink::IntWrapper>, blink::WeakMember<blink::IntWrapper> > Hash;
 172 };
 173
 174 // Custom traits for the pair. These are weakness handling traits, which means
 175 // PairWithWeakHandling must implement the traceInCollection method.
 176 // In addition, these traits are concerned with the two magic values for the
 177 // object, that represent empty and deleted slots in the hash table. The
 178 // SimpleClassHashTraits allow empty slots in the table to be initialzed with
 179 // memset to zero, and we use -1 in the first part of the pair to represent
 180 // deleted slots.
 181 template<> struct HashTraits<blink::PairWithWeakHandling> : blink::WeakHandlingHashTraits<blink::PairWithWeakHandling> {
 182     static const bool needsDestruction = false;
 183     static const bool hasIsEmptyValueFunction = true;
 184     static bool isEmptyValue(const blink::PairWithWeakHandling& value) { return !value.first; }
 185     static void constructDeletedValue(blink::PairWithWeakHandling& slot) { new (NotNull, &slot) blink::PairWithWeakHandling(HashTableDeletedValue); }
 186     static bool isDeletedValue(const blink::PairWithWeakHandling& value) { return value.isHashTableDeletedValue(); }
 187 };
 188
 189 }
 190
 191 namespace blink {
 192
 193 class TestGCScope {
 194 public:
 195     explicit TestGCScope(ThreadState::StackState state)
 196         : m_state(ThreadState::current())
 197         , m_safePointScope(state)
 198         , m_parkedAllThreads(false)
 199     {
 200         m_state->checkThread();
 201         EXPECT_FALSE(m_state->isInGC());
 202         if (LIKELY(ThreadState::stopThreads())) {
 203             m_state->enterGC();
 204             m_parkedAllThreads = true;
 205         }
 206     }
 207
 208     bool allThreadsParked() { return m_parkedAllThreads; }
 209
 210     ~TestGCScope()
 211     {
 212         // Only cleanup if we parked all threads in which case the GC happened
 213         // and we need to resume the other threads.
 214         if (LIKELY(m_parkedAllThreads)) {
 215             m_state->leaveGC();
 216             EXPECT_FALSE(m_state->isInGC());
 217             ThreadState::resumeThreads();
 218         }
 219     }
 220
 221 private:
 222     ThreadState* m_state;
 223     ThreadState::SafePointScope m_safePointScope;
 224     bool m_parkedAllThreads; // False if we fail to park all threads
 225 };
 226
 227 static void getHeapStats(HeapStats* stats)
 228 {
 229     TestGCScope scope(ThreadState::NoHeapPointersOnStack);
 230     EXPECT_TRUE(scope.allThreadsParked());
 231     Heap::getStats(stats);
 232 }
 233
 234 #define DEFINE_VISITOR_METHODS(Type)                                       \
 235     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
 236     {                                                                      \
 237         if (object)                                                        \
 238             m_count++;                                                     \
 239     }                                                                      \
 240     virtual bool isMarked(const Type*) OVERRIDE { return false; }
 241
 242 class CountingVisitor : public Visitor {
 243 public:
 244     CountingVisitor()
 245         : m_count(0)
 246     {
 247     }
 248
 249     virtual void mark(const void* object, TraceCallback) OVERRIDE
 250     {
 251         if (object)
 252             m_count++;
 253     }
 254
 255     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
 256     {
 257         ASSERT(header->payload());
 258         m_count++;
 259     }
 260
 261     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 262     {
 263         ASSERT(header->payload());
 264         m_count++;
 265     }
 266
 267     virtual void registerWeakMembers(const void*, const void*, WeakPointerCallback) OVERRIDE { }
 268     virtual void registerWeakTable(const void*, EphemeronCallback, EphemeronCallback) OVERRIDE { }
 269 #if ENABLE(ASSERT)
 270     virtual bool weakTableRegistered(const void*) OVERRIDE { return false; }
 271 #endif
 272     virtual void registerWeakCell(void**, WeakPointerCallback) OVERRIDE { }
 273     virtual bool isMarked(const void*) OVERRIDE { return false; }
 274
 275     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 276
 277     size_t count() { return m_count; }
 278     void reset() { m_count = 0; }
 279
 280 private:
 281     size_t m_count;
 282 };
 283
 284 class SimpleObject : public GarbageCollected<SimpleObject> {
 285 public:
 286     static SimpleObject* create() { return new SimpleObject(); }
 287     void trace(Visitor*) { }
 288     char getPayload(int i) { return payload[i]; }
 289     // This virtual method is unused but it is here to make sure
 290     // that this object has a vtable. This object is used
 291     // as the super class for objects that also have garbage
 292     // collected mixins and having a virtual here makes sure
 293     // that adjustment is needed both for marking and for isAlive
 294     // checks.
 295     virtual void virtualMethod() { }
 296 protected:
 297     SimpleObject() { }
 298     char payload[64];
 299 };
 300
 301 #undef DEFINE_VISITOR_METHODS
 302
 303 class HeapTestSuperClass : public GarbageCollectedFinalized<HeapTestSuperClass> {
 304 public:
 305     static HeapTestSuperClass* create()
 306     {
 307         return new HeapTestSuperClass();
 308     }
 309
 310     virtual ~HeapTestSuperClass()
 311     {
 312         ++s_destructorCalls;
 313     }
 314
 315     static int s_destructorCalls;
 316     void trace(Visitor*) { }
 317
 318 protected:
 319     HeapTestSuperClass() { }
 320 };
 321
 322 int HeapTestSuperClass::s_destructorCalls = 0;
 323
 324 class HeapTestOtherSuperClass {
 325 public:
 326     int payload;
 327 };
 328
 329 static const size_t classMagic = 0xABCDDBCA;
 330
 331 class HeapTestSubClass : public HeapTestOtherSuperClass, public HeapTestSuperClass {
 332 public:
 333     static HeapTestSubClass* create()
 334     {
 335         return new HeapTestSubClass();
 336     }
 337
 338     virtual ~HeapTestSubClass()
 339     {
 340         EXPECT_EQ(classMagic, m_magic);
 341         ++s_destructorCalls;
 342     }
 343
 344     static int s_destructorCalls;
 345
 346 private:
 347
 348     HeapTestSubClass() : m_magic(classMagic) { }
 349
 350     const size_t m_magic;
 351 };
 352
 353 int HeapTestSubClass::s_destructorCalls = 0;
 354
 355 class HeapAllocatedArray : public GarbageCollected<HeapAllocatedArray> {
 356 public:
 357     HeapAllocatedArray()
 358     {
 359         for (int i = 0; i < s_arraySize; ++i) {
 360             m_array[i] = i % 128;
 361         }
 362     }
 363
 364     int8_t at(size_t i) { return m_array[i]; }
 365     void trace(Visitor*) { }
 366 private:
 367     static const int s_arraySize = 1000;
 368     int8_t m_array[s_arraySize];
 369 };
 370
 371 // Do several GCs to make sure that later GCs don't free up old memory from
 372 // previously run tests in this process.
 373 static void clearOutOldGarbage(HeapStats* heapStats)
 374 {
 375     while (true) {
 376         getHeapStats(heapStats);
 377         size_t used = heapStats->totalObjectSpace();
 378         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 379         getHeapStats(heapStats);
 380         if (heapStats->totalObjectSpace() >= used)
 381             break;
 382     }
 383 }
 384
 385 class OffHeapInt : public RefCounted<OffHeapInt> {
 386 public:
 387     static RefPtr<OffHeapInt> create(int x)
 388     {
 389         return adoptRef(new OffHeapInt(x));
 390     }
 391
 392     virtual ~OffHeapInt()
 393     {
 394         ++s_destructorCalls;
 395     }
 396
 397     static int s_destructorCalls;
 398
 399     int value() const { return m_x; }
 400
 401     bool operator==(const OffHeapInt& other) const { return other.value() == value(); }
 402
 403     unsigned hash() { return IntHash<int>::hash(m_x); }
 404     void voidFunction() { }
 405
 406 protected:
 407     OffHeapInt(int x) : m_x(x) { }
 408
 409 private:
 410     OffHeapInt();
 411     int m_x;
 412 };
 413
 414 int IntWrapper::s_destructorCalls = 0;
 415 int OffHeapInt::s_destructorCalls = 0;
 416
 417 class ThreadedTesterBase {
 418 protected:
 419     static void test(ThreadedTesterBase* tester)
 420     {
 421         for (int i = 0; i < numberOfThreads; i++)
 422             createThread(&threadFunc, tester, "testing thread");
 423         while (tester->m_threadsToFinish) {
 424             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 425             yield();
 426         }
 427         delete tester;
 428     }
 429
 430     virtual void runThread() = 0;
 431
 432 protected:
 433     static const int numberOfThreads = 10;
 434     static const int gcPerThread = 5;
 435     static const int numberOfAllocations = 50;
 436
 437     ThreadedTesterBase() : m_gcCount(0), m_threadsToFinish(numberOfThreads)
 438     {
 439     }
 440
 441     virtual ~ThreadedTesterBase()
 442     {
 443     }
 444
 445     inline bool done() const { return m_gcCount >= numberOfThreads * gcPerThread; }
 446
 447     volatile int m_gcCount;
 448     volatile int m_threadsToFinish;
 449
 450 private:
 451     static void threadFunc(void* data)
 452     {
 453         reinterpret_cast<ThreadedTesterBase*>(data)->runThread();
 454     }
 455 };
 456
 457 class ThreadedHeapTester : public ThreadedTesterBase {
 458 public:
 459     static void test()
 460     {
 461         ThreadedTesterBase::test(new ThreadedHeapTester);
 462     }
 463
 464 protected:
 465     virtual void runThread() OVERRIDE
 466     {
 467         ThreadState::attach();
 468
 469         int gcCount = 0;
 470         while (!done()) {
 471             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 472             {
 473                 Persistent<IntWrapper> wrapper;
 474
 475                 typedef Persistent<IntWrapper, GlobalPersistents> GlobalIntWrapperPersistent;
 476                 OwnPtr<GlobalIntWrapperPersistent> globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 477
 478                 for (int i = 0; i < numberOfAllocations; i++) {
 479                     wrapper = IntWrapper::create(0x0bbac0de);
 480                     if (!(i % 10)) {
 481                         globalPersistent = adoptPtr(new GlobalIntWrapperPersistent(IntWrapper::create(0x0ed0cabb)));
 482                     }
 483                     ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 484                     yield();
 485                 }
 486
 487                 if (gcCount < gcPerThread) {
 488                     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 489                     gcCount++;
 490                     atomicIncrement(&m_gcCount);
 491                 }
 492
 493                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 494                 EXPECT_EQ(wrapper->value(), 0x0bbac0de);
 495                 EXPECT_EQ((*globalPersistent)->value(), 0x0ed0cabb);
 496             }
 497             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 498             yield();
 499         }
 500         ThreadState::detach();
 501         atomicDecrement(&m_threadsToFinish);
 502     }
 503 };
 504
 505 class ThreadedWeaknessTester : public ThreadedTesterBase {
 506 public:
 507     static void test()
 508     {
 509         ThreadedTesterBase::test(new ThreadedWeaknessTester);
 510     }
 511
 512 private:
 513     virtual void runThread() OVERRIDE
 514     {
 515         ThreadState::attach();
 516
 517         int gcCount = 0;
 518         while (!done()) {
 519             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
 520             {
 521                 Persistent<HeapHashMap<ThreadMarker, WeakMember<IntWrapper> > > weakMap = new HeapHashMap<ThreadMarker, WeakMember<IntWrapper> >;
 522                 PersistentHeapHashMap<ThreadMarker, WeakMember<IntWrapper> > weakMap2;
 523
 524                 for (int i = 0; i < numberOfAllocations; i++) {
 525                     weakMap->add(static_cast<unsigned>(i), IntWrapper::create(0));
 526                     weakMap2.add(static_cast<unsigned>(i), IntWrapper::create(0));
 527                     ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 528                     yield();
 529                 }
 530
 531                 if (gcCount < gcPerThread) {
 532                     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 533                     gcCount++;
 534                     atomicIncrement(&m_gcCount);
 535                 }
 536
 537                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
 538                 EXPECT_TRUE(weakMap->isEmpty());
 539                 EXPECT_TRUE(weakMap2.isEmpty());
 540             }
 541             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
 542             yield();
 543         }
 544         ThreadState::detach();
 545         atomicDecrement(&m_threadsToFinish);
 546     }
 547 };
 548
 549 // The accounting for memory includes the memory used by rounding up object
 550 // sizes. This is done in a different way on 32 bit and 64 bit, so we have to
 551 // have some slack in the tests.
 552 template<typename T>
 553 void CheckWithSlack(T expected, T actual, int slack)
 554 {
 555     EXPECT_LE(expected, actual);
 556     EXPECT_GE((intptr_t)expected + slack, (intptr_t)actual);
 557 }
 558
 559 class TraceCounter : public GarbageCollectedFinalized<TraceCounter> {
 560 public:
 561     static TraceCounter* create()
 562     {
 563         return new TraceCounter();
 564     }
 565
 566     void trace(Visitor*) { m_traceCount++; }
 567
 568     int traceCount() { return m_traceCount; }
 569
 570 private:
 571     TraceCounter()
 572         : m_traceCount(0)
 573     {
 574     }
 575
 576     int m_traceCount;
 577 };
 578
 579 class ClassWithMember : public GarbageCollected<ClassWithMember> {
 580 public:
 581     static ClassWithMember* create()
 582     {
 583         return new ClassWithMember();
 584     }
 585
 586     void trace(Visitor* visitor)
 587     {
 588         EXPECT_TRUE(visitor->isMarked(this));
 589         if (!traceCount())
 590             EXPECT_FALSE(visitor->isMarked(m_traceCounter));
 591         else
 592             EXPECT_TRUE(visitor->isMarked(m_traceCounter));
 593
 594         visitor->trace(m_traceCounter);
 595     }
 596
 597     int traceCount() { return m_traceCounter->traceCount(); }
 598
 599 private:
 600     ClassWithMember()
 601         : m_traceCounter(TraceCounter::create())
 602     { }
 603
 604     Member<TraceCounter> m_traceCounter;
 605 };
 606
 607 class SimpleFinalizedObject : public GarbageCollectedFinalized<SimpleFinalizedObject> {
 608 public:
 609     static SimpleFinalizedObject* create()
 610     {
 611         return new SimpleFinalizedObject();
 612     }
 613
 614     ~SimpleFinalizedObject()
 615     {
 616         ++s_destructorCalls;
 617     }
 618
 619     static int s_destructorCalls;
 620
 621     void trace(Visitor*) { }
 622
 623 private:
 624     SimpleFinalizedObject() { }
 625 };
 626
 627 int SimpleFinalizedObject::s_destructorCalls = 0;
 628
 629 class Node : public GarbageCollected<Node> {
 630 public:
 631     static Node* create()
 632     {
 633         return new Node();
 634     }
 635
 636     void trace(Visitor*) { }
 637
 638 private:
 639     Node() { }
 640 };
 641
 642 class Bar : public GarbageCollectedFinalized<Bar> {
 643 public:
 644     static Bar* create()
 645     {
 646         return new Bar();
 647     }
 648
 649     void finalizeGarbageCollectedObject()
 650     {
 651         EXPECT_TRUE(m_magic == magic);
 652         m_magic = 0;
 653         s_live--;
 654     }
 655     bool hasBeenFinalized() const { return !m_magic; }
 656
 657     virtual void trace(Visitor* visitor) { }
 658     static unsigned s_live;
 659
 660 protected:
 661     static const int magic = 1337;
 662     int m_magic;
 663
 664     Bar()
 665         : m_magic(magic)
 666     {
 667         s_live++;
 668     }
 669 };
 670
 671 unsigned Bar::s_live = 0;
 672
 673 class Baz : public GarbageCollected<Baz> {
 674 public:
 675     static Baz* create(Bar* bar)
 676     {
 677         return new Baz(bar);
 678     }
 679
 680     void trace(Visitor* visitor)
 681     {
 682         visitor->trace(m_bar);
 683     }
 684
 685     void clear() { m_bar.release(); }
 686
 687     // willFinalize is called by FinalizationObserver.
 688     void willFinalize()
 689     {
 690         EXPECT_TRUE(!m_bar->hasBeenFinalized());
 691     }
 692
 693 private:
 694     explicit Baz(Bar* bar)
 695         : m_bar(bar)
 696     {
 697     }
 698
 699     Member<Bar> m_bar;
 700 };
 701
 702 class Foo : public Bar {
 703 public:
 704     static Foo* create(Bar* bar)
 705     {
 706         return new Foo(bar);
 707     }
 708
 709     static Foo* create(Foo* foo)
 710     {
 711         return new Foo(foo);
 712     }
 713
 714     virtual void trace(Visitor* visitor) OVERRIDE
 715     {
 716         if (m_pointsToFoo)
 717             visitor->mark(static_cast<Foo*>(m_bar));
 718         else
 719             visitor->mark(m_bar);
 720     }
 721
 722 private:
 723     Foo(Bar* bar)
 724         : Bar()
 725         , m_bar(bar)
 726         , m_pointsToFoo(false)
 727     {
 728     }
 729
 730     Foo(Foo* foo)
 731         : Bar()
 732         , m_bar(foo)
 733         , m_pointsToFoo(true)
 734     {
 735     }
 736
 737     Bar* m_bar;
 738     bool m_pointsToFoo;
 739 };
 740
 741 class Bars : public Bar {
 742 public:
 743     static Bars* create()
 744     {
 745         return new Bars();
 746     }
 747
 748     virtual void trace(Visitor* visitor) OVERRIDE
 749     {
 750         for (unsigned i = 0; i < m_width; i++)
 751             visitor->trace(m_bars[i]);
 752     }
 753
 754     unsigned getWidth() const
 755     {
 756         return m_width;
 757     }
 758
 759     static const unsigned width = 7500;
 760 private:
 761     Bars() : m_width(0)
 762     {
 763         for (unsigned i = 0; i < width; i++) {
 764             m_bars[i] = Bar::create();
 765             m_width++;
 766         }
 767     }
 768
 769     unsigned m_width;
 770     Member<Bar> m_bars[width];
 771 };
 772
 773 class ConstructorAllocation : public GarbageCollected<ConstructorAllocation> {
 774 public:
 775     static ConstructorAllocation* create() { return new ConstructorAllocation(); }
 776
 777     void trace(Visitor* visitor) { visitor->trace(m_intWrapper); }
 778
 779 private:
 780     ConstructorAllocation()
 781     {
 782         m_intWrapper = IntWrapper::create(42);
 783     }
 784
 785     Member<IntWrapper> m_intWrapper;
 786 };
 787
 788 class LargeObject : public GarbageCollectedFinalized<LargeObject> {
 789 public:
 790     ~LargeObject()
 791     {
 792         s_destructorCalls++;
 793     }
 794     static LargeObject* create() { return new LargeObject(); }
 795     char get(size_t i) { return m_data[i]; }
 796     void set(size_t i, char c) { m_data[i] = c; }
 797     size_t length() { return s_length; }
 798     void trace(Visitor* visitor)
 799     {
 800         visitor->trace(m_intWrapper);
 801     }
 802     static int s_destructorCalls;
 803
 804 private:
 805     static const size_t s_length = 1024*1024;
 806     LargeObject()
 807     {
 808         m_intWrapper = IntWrapper::create(23);
 809     }
 810     Member<IntWrapper> m_intWrapper;
 811     char m_data[s_length];
 812 };
 813
 814 int LargeObject::s_destructorCalls = 0;
 815
 816 class RefCountedAndGarbageCollected : public RefCountedGarbageCollected<RefCountedAndGarbageCollected> {
 817 public:
 818     static PassRefPtr<RefCountedAndGarbageCollected> create()
 819     {
 820         return adoptRef(new RefCountedAndGarbageCollected());
 821     }
 822
 823     ~RefCountedAndGarbageCollected()
 824     {
 825         ++s_destructorCalls;
 826     }
 827
 828     // These are here with their default implementations so you can break in
 829     // them in the debugger.
 830     void ref() { RefCountedGarbageCollected<RefCountedAndGarbageCollected>::ref(); }
 831     void deref() { RefCountedGarbageCollected<RefCountedAndGarbageCollected>::deref(); }
 832
 833     void trace(Visitor*) { }
 834
 835     static int s_destructorCalls;
 836
 837 private:
 838     RefCountedAndGarbageCollected()
 839     {
 840     }
 841 };
 842
 843 int RefCountedAndGarbageCollected::s_destructorCalls = 0;
 844
 845 class RefCountedAndGarbageCollected2 : public HeapTestOtherSuperClass, public RefCountedGarbageCollected<RefCountedAndGarbageCollected2> {
 846 public:
 847     static RefCountedAndGarbageCollected2* create()
 848     {
 849         return adoptRefCountedGarbageCollected(new RefCountedAndGarbageCollected2());
 850     }
 851
 852     ~RefCountedAndGarbageCollected2()
 853     {
 854         ++s_destructorCalls;
 855     }
 856
 857     void trace(Visitor*) { }
 858
 859     static int s_destructorCalls;
 860
 861 private:
 862     RefCountedAndGarbageCollected2()
 863     {
 864     }
 865 };
 866
 867 int RefCountedAndGarbageCollected2::s_destructorCalls = 0;
 868
 869 #define DEFINE_VISITOR_METHODS(Type)                                       \
 870     virtual void mark(const Type* object, TraceCallback callback) OVERRIDE \
 871     {                                                                      \
 872         mark(object);                                                      \
 873     }                                                                      \
 874
 875 class RefCountedGarbageCollectedVisitor : public CountingVisitor {
 876 public:
 877     RefCountedGarbageCollectedVisitor(int expected, void** objects)
 878         : m_count(0)
 879         , m_expectedCount(expected)
 880         , m_expectedObjects(objects)
 881     {
 882     }
 883
 884     void mark(const void* ptr) { markNoTrace(ptr); }
 885
 886     virtual void markNoTrace(const void* ptr)
 887     {
 888         if (!ptr)
 889             return;
 890         if (m_count < m_expectedCount)
 891             EXPECT_TRUE(expectedObject(ptr));
 892         else
 893             EXPECT_FALSE(expectedObject(ptr));
 894         m_count++;
 895     }
 896
 897     virtual void mark(const void* ptr, TraceCallback) OVERRIDE
 898     {
 899         mark(ptr);
 900     }
 901
 902     virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
 903     {
 904         mark(header->payload());
 905     }
 906
 907     virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
 908     {
 909         mark(header->payload());
 910     }
 911
 912     bool validate() { return m_count >= m_expectedCount; }
 913     void reset() { m_count = 0; }
 914
 915     FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
 916
 917 private:
 918     bool expectedObject(const void* ptr)
 919     {
 920         for (int i = 0; i < m_expectedCount; i++) {
 921             if (m_expectedObjects[i] == ptr)
 922                 return true;
 923         }
 924         return false;
 925     }
 926
 927     int m_count;
 928     int m_expectedCount;
 929     void** m_expectedObjects;
 930 };
 931
 932 #undef DEFINE_VISITOR_METHODS
 933
 934 class Weak : public Bar {
 935 public:
 936     static Weak* create(Bar* strong, Bar* weak)
 937     {
 938         return new Weak(strong, weak);
 939     }
 940
 941     virtual void trace(Visitor* visitor) OVERRIDE
 942     {
 943         visitor->trace(m_strongBar);
 944         visitor->registerWeakMembers(this, zapWeakMembers);
 945     }
 946
 947     static void zapWeakMembers(Visitor* visitor, void* self)
 948     {
 949         reinterpret_cast<Weak*>(self)->zapWeakMembers(visitor);
 950     }
 951
 952     bool strongIsThere() { return !!m_strongBar; }
 953     bool weakIsThere() { return !!m_weakBar; }
 954
 955 private:
 956     Weak(Bar* strongBar, Bar* weakBar)
 957         : Bar()
 958         , m_strongBar(strongBar)
 959         , m_weakBar(weakBar)
 960     {
 961     }
 962
 963     void zapWeakMembers(Visitor* visitor)
 964     {
 965         if (!visitor->isAlive(m_weakBar))
 966             m_weakBar = 0;
 967     }
 968
 969     Member<Bar> m_strongBar;
 970     Bar* m_weakBar;
 971 };
 972
 973 class WithWeakMember : public Bar {
 974 public:
 975     static WithWeakMember* create(Bar* strong, Bar* weak)
 976     {
 977         return new WithWeakMember(strong, weak);
 978     }
 979
 980     virtual void trace(Visitor* visitor) OVERRIDE
 981     {
 982         visitor->trace(m_strongBar);
 983         visitor->trace(m_weakBar);
 984     }
 985
 986     bool strongIsThere() { return !!m_strongBar; }
 987     bool weakIsThere() { return !!m_weakBar; }
 988
 989 private:
 990     WithWeakMember(Bar* strongBar, Bar* weakBar)
 991         : Bar()
 992         , m_strongBar(strongBar)
 993         , m_weakBar(weakBar)
 994     {
 995     }
 996
 997     Member<Bar> m_strongBar;
 998     WeakMember<Bar> m_weakBar;
 999 };
1000
1001 class Observable : public GarbageCollectedFinalized<Observable> {
1002 public:
1003     static Observable* create(Bar* bar) { return new Observable(bar);  }
1004     ~Observable() { m_wasDestructed = true; }
1005     void trace(Visitor* visitor) { visitor->trace(m_bar); }
1006
1007     // willFinalize is called by FinalizationObserver. willFinalize can touch
1008     // other on-heap objects.
1009     void willFinalize()
1010     {
1011         EXPECT_FALSE(m_wasDestructed);
1012         EXPECT_FALSE(m_bar->hasBeenFinalized());
1013     }
1014
1015 private:
1016     explicit Observable(Bar* bar)
1017         : m_bar(bar)
1018         , m_wasDestructed(false)
1019     {
1020     }
1021
1022     Member<Bar> m_bar;
1023     bool m_wasDestructed;
1024 };
1025
1026 template <typename T> class FinalizationObserver : public GarbageCollected<FinalizationObserver<T> > {
1027 public:
1028     static FinalizationObserver* create(T* data) { return new FinalizationObserver(data); }
1029     bool didCallWillFinalize() const { return m_didCallWillFinalize; }
1030
1031     void trace(Visitor* visitor)
1032     {
1033         visitor->registerWeakMembers(this, zapWeakMembers);
1034     }
1035
1036 private:
1037     FinalizationObserver(T* data)
1038         : m_data(data)
1039         , m_didCallWillFinalize(false)
1040     {
1041     }
1042
1043     static void zapWeakMembers(Visitor* visitor, void* self)
1044     {
1045         FinalizationObserver* o = reinterpret_cast<FinalizationObserver*>(self);
1046         if (o->m_data && !visitor->isAlive(o->m_data)) {
1047             o->m_data->willFinalize();
1048             o->m_data = nullptr;
1049             o->m_didCallWillFinalize = true;
1050         }
1051     }
1052
1053     WeakMember<T> m_data;
1054     bool m_didCallWillFinalize;
1055 };
1056
1057 class FinalizationObserverWithHashMap {
1058 public:
1059     typedef HeapHashMap<WeakMember<Observable>, OwnPtr<FinalizationObserverWithHashMap> > ObserverMap;
1060
1061     explicit FinalizationObserverWithHashMap(Observable& target) : m_target(target) { }
1062     ~FinalizationObserverWithHashMap()
1063     {
1064         m_target.willFinalize();
1065         s_didCallWillFinalize = true;
1066     }
1067
1068     static ObserverMap& observe(Observable& target)
1069     {
1070         ObserverMap& map = observers();
1071         ObserverMap::AddResult result = map.add(&target, nullptr);
1072         if (result.isNewEntry)
1073             result.storedValue->value = adoptPtr(new FinalizationObserverWithHashMap(target));
1074         else
1075             ASSERT(result.storedValue->value);
1076         return map;
1077     }
1078
1079     static bool s_didCallWillFinalize;
1080
1081 private:
1082     static ObserverMap& observers()
1083     {
1084         DEFINE_STATIC_LOCAL(Persistent<ObserverMap>, observerMap, ());
1085         if (!observerMap)
1086             observerMap = new ObserverMap();
1087         return *observerMap;
1088     }
1089
1090     Observable& m_target;
1091 };
1092
1093 bool FinalizationObserverWithHashMap::s_didCallWillFinalize = false;
1094
1095 class SuperClass;
1096
1097 class PointsBack : public RefCountedWillBeGarbageCollectedFinalized<PointsBack> {
1098 public:
1099     static PassRefPtrWillBeRawPtr<PointsBack> create()
1100     {
1101         return adoptRefWillBeNoop(new PointsBack());
1102     }
1103
1104     ~PointsBack()
1105     {
1106         --s_aliveCount;
1107     }
1108
1109     void setBackPointer(SuperClass* backPointer)
1110     {
1111         m_backPointer = backPointer;
1112     }
1113
1114     SuperClass* backPointer() const { return m_backPointer; }
1115
1116     void trace(Visitor* visitor)
1117     {
1118 #if ENABLE_OILPAN
1119         visitor->trace(m_backPointer);
1120 #endif
1121     }
1122
1123     static int s_aliveCount;
1124 private:
1125     PointsBack() : m_backPointer(nullptr)
1126     {
1127         ++s_aliveCount;
1128     }
1129
1130     RawPtrWillBeWeakMember<SuperClass> m_backPointer;
1131 };
1132
1133 int PointsBack::s_aliveCount = 0;
1134
1135 class SuperClass : public RefCountedWillBeGarbageCollectedFinalized<SuperClass> {
1136 public:
1137     static PassRefPtrWillBeRawPtr<SuperClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1138     {
1139         return adoptRefWillBeNoop(new SuperClass(pointsBack));
1140     }
1141
1142     virtual ~SuperClass()
1143     {
1144 #if !ENABLE_OILPAN
1145         m_pointsBack->setBackPointer(0);
1146 #endif
1147         --s_aliveCount;
1148     }
1149
1150     void doStuff(PassRefPtrWillBeRawPtr<SuperClass> targetPass, PointsBack* pointsBack, int superClassCount)
1151     {
1152         RefPtrWillBeRawPtr<SuperClass> target = targetPass;
1153         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1154         EXPECT_EQ(pointsBack, target->pointsBack());
1155         EXPECT_EQ(superClassCount, SuperClass::s_aliveCount);
1156     }
1157
1158     virtual void trace(Visitor* visitor)
1159     {
1160 #if ENABLE_OILPAN
1161         visitor->trace(m_pointsBack);
1162 #endif
1163     }
1164
1165     PointsBack* pointsBack() const { return m_pointsBack.get(); }
1166
1167     static int s_aliveCount;
1168 protected:
1169     explicit SuperClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1170         : m_pointsBack(pointsBack)
1171     {
1172         m_pointsBack->setBackPointer(this);
1173         ++s_aliveCount;
1174     }
1175
1176 private:
1177     RefPtrWillBeMember<PointsBack> m_pointsBack;
1178 };
1179
1180 int SuperClass::s_aliveCount = 0;
1181 class SubData : public NoBaseWillBeGarbageCollectedFinalized<SubData> {
1182 public:
1183     SubData() { ++s_aliveCount; }
1184     ~SubData() { --s_aliveCount; }
1185
1186     void trace(Visitor*) { }
1187
1188     static int s_aliveCount;
1189 };
1190
1191 int SubData::s_aliveCount = 0;
1192
1193 class SubClass : public SuperClass {
1194 public:
1195     static PassRefPtrWillBeRawPtr<SubClass> create(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1196     {
1197         return adoptRefWillBeNoop(new SubClass(pointsBack));
1198     }
1199
1200     virtual ~SubClass()
1201     {
1202         --s_aliveCount;
1203     }
1204
1205     virtual void trace(Visitor* visitor)
1206     {
1207 #if ENABLE_OILPAN
1208         SuperClass::trace(visitor);
1209         visitor->trace(m_data);
1210 #endif
1211     }
1212
1213     static int s_aliveCount;
1214 private:
1215     explicit SubClass(PassRefPtrWillBeRawPtr<PointsBack> pointsBack)
1216         : SuperClass(pointsBack)
1217         , m_data(adoptPtrWillBeNoop(new SubData()))
1218     {
1219         ++s_aliveCount;
1220     }
1221
1222 private:
1223     OwnPtrWillBeMember<SubData> m_data;
1224 };
1225
1226 int SubClass::s_aliveCount = 0;
1227
1228 class TransitionRefCounted : public RefCountedWillBeRefCountedGarbageCollected<TransitionRefCounted> {
1229 public:
1230     static PassRefPtrWillBeRawPtr<TransitionRefCounted> create()
1231     {
1232         return adoptRefWillBeRefCountedGarbageCollected(new TransitionRefCounted());
1233     }
1234
1235     ~TransitionRefCounted()
1236     {
1237         --s_aliveCount;
1238     }
1239
1240     void trace(Visitor* visitor) { }
1241
1242     static int s_aliveCount;
1243
1244 private:
1245     TransitionRefCounted()
1246     {
1247         ++s_aliveCount;
1248     }
1249 };
1250
1251 int TransitionRefCounted::s_aliveCount = 0;
1252
1253 class Mixin : public GarbageCollectedMixin {
1254 public:
1255     virtual void trace(Visitor* visitor) { }
1256
1257     virtual char getPayload(int i) { return m_padding[i]; }
1258
1259 protected:
1260     int m_padding[8];
1261 };
1262
1263 class UseMixin : public SimpleObject, public Mixin {
1264     USING_GARBAGE_COLLECTED_MIXIN(UseMixin)
1265 public:
1266     static UseMixin* create()
1267     {
1268         return new UseMixin();
1269     }
1270
1271     static int s_traceCount;
1272     virtual void trace(Visitor* visitor)
1273     {
1274         SimpleObject::trace(visitor);
1275         Mixin::trace(visitor);
1276         ++s_traceCount;
1277     }
1278
1279 private:
1280     UseMixin()
1281     {
1282         s_traceCount = 0;
1283     }
1284 };
1285
1286 int UseMixin::s_traceCount = 0;
1287
1288 class VectorObject {
1289     ALLOW_ONLY_INLINE_ALLOCATION();
1290 public:
1291     VectorObject()
1292     {
1293         m_value = SimpleFinalizedObject::create();
1294     }
1295
1296     void trace(Visitor* visitor)
1297     {
1298         visitor->trace(m_value);
1299     }
1300
1301 private:
1302     Member<SimpleFinalizedObject> m_value;
1303 };
1304
1305 class VectorObjectInheritedTrace : public VectorObject { };
1306
1307 class VectorObjectNoTrace {
1308     ALLOW_ONLY_INLINE_ALLOCATION();
1309 public:
1310     VectorObjectNoTrace()
1311     {
1312         m_value = SimpleFinalizedObject::create();
1313     }
1314
1315 private:
1316     Member<SimpleFinalizedObject> m_value;
1317 };
1318
1319 class TerminatedArrayItem {
1320     ALLOW_ONLY_INLINE_ALLOCATION();
1321 public:
1322     TerminatedArrayItem(IntWrapper* payload) : m_payload(payload), m_isLast(false) { }
1323
1324     void trace(Visitor* visitor) { visitor->trace(m_payload); }
1325
1326     bool isLastInArray() const { return m_isLast; }
1327     void setLastInArray(bool value) { m_isLast = value; }
1328
1329     IntWrapper* payload() const { return m_payload; }
1330
1331 private:
1332     Member<IntWrapper> m_payload;
1333     bool m_isLast;
1334 };
1335
1336 } // namespace blink
1337
1338 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(blink::VectorObject);
1339 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(blink::VectorObjectInheritedTrace);
1340 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(blink::VectorObjectNoTrace);
1341
1342 namespace blink {
1343
1344 class OneKiloByteObject : public GarbageCollectedFinalized<OneKiloByteObject> {
1345 public:
1346     ~OneKiloByteObject() { s_destructorCalls++; }
1347     char* data() { return m_data; }
1348     void trace(Visitor* visitor) { }
1349     static int s_destructorCalls;
1350
1351 private:
1352     static const size_t s_length = 1024;
1353     char m_data[s_length];
1354 };
1355
1356 int OneKiloByteObject::s_destructorCalls = 0;
1357
1358 class DynamicallySizedObject : public GarbageCollected<DynamicallySizedObject> {
1359 public:
1360     static DynamicallySizedObject* create(size_t size)
1361     {
1362         void* slot = Heap::allocate<DynamicallySizedObject>(size);
1363         return new (slot) DynamicallySizedObject();
1364     }
1365
1366     void* operator new(std::size_t, void* location)
1367     {
1368         return location;
1369     }
1370
1371     uint8_t get(int i)
1372     {
1373         return *(reinterpret_cast<uint8_t*>(this) + i);
1374     }
1375
1376     void trace(Visitor*) { }
1377
1378 private:
1379     DynamicallySizedObject() { }
1380 };
1381
1382 class FinalizationAllocator : public GarbageCollectedFinalized<FinalizationAllocator> {
1383 public:
1384     FinalizationAllocator(Persistent<IntWrapper>* wrapper)
1385         : m_wrapper(wrapper)
1386     {
1387     }
1388
1389     ~FinalizationAllocator()
1390     {
1391         for (int i = 0; i < 10; ++i)
1392             *m_wrapper = IntWrapper::create(42);
1393         for (int i = 0; i < 512; ++i)
1394             new OneKiloByteObject();
1395     }
1396
1397     void trace(Visitor*) { }
1398
1399 private:
1400     Persistent<IntWrapper>* m_wrapper;
1401 };
1402
1403 TEST(HeapTest, Transition)
1404 {
1405     {
1406         RefPtr<TransitionRefCounted> refCounted = TransitionRefCounted::create();
1407         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
1408         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1409         EXPECT_EQ(1, TransitionRefCounted::s_aliveCount);
1410     }
1411     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1412     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
1413
1414     RefPtrWillBePersistent<PointsBack> pointsBack1 = PointsBack::create();
1415     RefPtrWillBePersistent<PointsBack> pointsBack2 = PointsBack::create();
1416     RefPtrWillBePersistent<SuperClass> superClass = SuperClass::create(pointsBack1);
1417     RefPtrWillBePersistent<SubClass> subClass = SubClass::create(pointsBack2);
1418     EXPECT_EQ(2, PointsBack::s_aliveCount);
1419     EXPECT_EQ(2, SuperClass::s_aliveCount);
1420     EXPECT_EQ(1, SubClass::s_aliveCount);
1421     EXPECT_EQ(1, SubData::s_aliveCount);
1422
1423     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1424     EXPECT_EQ(0, TransitionRefCounted::s_aliveCount);
1425     EXPECT_EQ(2, PointsBack::s_aliveCount);
1426     EXPECT_EQ(2, SuperClass::s_aliveCount);
1427     EXPECT_EQ(1, SubClass::s_aliveCount);
1428     EXPECT_EQ(1, SubData::s_aliveCount);
1429
1430     superClass->doStuff(superClass.release(), pointsBack1.get(), 2);
1431     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1432     EXPECT_EQ(2, PointsBack::s_aliveCount);
1433     EXPECT_EQ(1, SuperClass::s_aliveCount);
1434     EXPECT_EQ(1, SubClass::s_aliveCount);
1435     EXPECT_EQ(1, SubData::s_aliveCount);
1436     EXPECT_EQ(0, pointsBack1->backPointer());
1437
1438     pointsBack1.release();
1439     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1440     EXPECT_EQ(1, PointsBack::s_aliveCount);
1441     EXPECT_EQ(1, SuperClass::s_aliveCount);
1442     EXPECT_EQ(1, SubClass::s_aliveCount);
1443     EXPECT_EQ(1, SubData::s_aliveCount);
1444
1445     subClass->doStuff(subClass.release(), pointsBack2.get(), 1);
1446     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1447     EXPECT_EQ(1, PointsBack::s_aliveCount);
1448     EXPECT_EQ(0, SuperClass::s_aliveCount);
1449     EXPECT_EQ(0, SubClass::s_aliveCount);
1450     EXPECT_EQ(0, SubData::s_aliveCount);
1451     EXPECT_EQ(0, pointsBack2->backPointer());
1452
1453     pointsBack2.release();
1454     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1455     EXPECT_EQ(0, PointsBack::s_aliveCount);
1456     EXPECT_EQ(0, SuperClass::s_aliveCount);
1457     EXPECT_EQ(0, SubClass::s_aliveCount);
1458     EXPECT_EQ(0, SubData::s_aliveCount);
1459
1460     EXPECT_TRUE(superClass == subClass);
1461 }
1462
1463 TEST(HeapTest, Threading)
1464 {
1465     ThreadedHeapTester::test();
1466 }
1467
1468 TEST(HeapTest, ThreadedWeakness)
1469 {
1470     ThreadedWeaknessTester::test();
1471 }
1472
1473 TEST(HeapTest, BasicFunctionality)
1474 {
1475     HeapStats heapStats;
1476     clearOutOldGarbage(&heapStats);
1477     {
1478         size_t slack = 0;
1479
1480         // When the test starts there may already have been leaked some memory
1481         // on the heap, so we establish a base line.
1482         size_t baseLevel = heapStats.totalObjectSpace();
1483         bool testPagesAllocated = !baseLevel;
1484         if (testPagesAllocated)
1485             EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1486
1487         // This allocates objects on the general heap which should add a page of memory.
1488         DynamicallySizedObject* alloc32 = DynamicallySizedObject::create(32);
1489         slack += 4;
1490         memset(alloc32, 40, 32);
1491         DynamicallySizedObject* alloc64 = DynamicallySizedObject::create(64);
1492         slack += 4;
1493         memset(alloc64, 27, 64);
1494
1495         size_t total = 96;
1496
1497         getHeapStats(&heapStats);
1498         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1499         if (testPagesAllocated)
1500             EXPECT_EQ(heapStats.totalAllocatedSpace(), blinkPageSize);
1501
1502         CheckWithSlack(alloc32 + 32 + sizeof(HeapObjectHeader), alloc64, slack);
1503
1504         EXPECT_EQ(alloc32->get(0), 40);
1505         EXPECT_EQ(alloc32->get(31), 40);
1506         EXPECT_EQ(alloc64->get(0), 27);
1507         EXPECT_EQ(alloc64->get(63), 27);
1508
1509         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1510
1511         EXPECT_EQ(alloc32->get(0), 40);
1512         EXPECT_EQ(alloc32->get(31), 40);
1513         EXPECT_EQ(alloc64->get(0), 27);
1514         EXPECT_EQ(alloc64->get(63), 27);
1515     }
1516
1517     clearOutOldGarbage(&heapStats);
1518     size_t total = 0;
1519     size_t slack = 0;
1520     size_t baseLevel = heapStats.totalObjectSpace();
1521     bool testPagesAllocated = !baseLevel;
1522     if (testPagesAllocated)
1523         EXPECT_EQ(heapStats.totalAllocatedSpace(), 0ul);
1524
1525     size_t big = 1008;
1526     Persistent<DynamicallySizedObject> bigArea = DynamicallySizedObject::create(big);
1527     total += big;
1528     slack += 4;
1529
1530     size_t persistentCount = 0;
1531     const size_t numPersistents = 100000;
1532     Persistent<DynamicallySizedObject>* persistents[numPersistents];
1533
1534     for (int i = 0; i < 1000; i++) {
1535         size_t size = 128 + i * 8;
1536         total += size;
1537         persistents[persistentCount++] = new Persistent<DynamicallySizedObject>(DynamicallySizedObject::create(size));
1538         slack += 4;
1539         getHeapStats(&heapStats);
1540         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1541         if (testPagesAllocated)
1542             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1543     }
1544
1545     {
1546         DynamicallySizedObject* alloc32b(DynamicallySizedObject::create(32));
1547         slack += 4;
1548         memset(alloc32b, 40, 32);
1549         DynamicallySizedObject* alloc64b(DynamicallySizedObject::create(64));
1550         slack += 4;
1551         memset(alloc64b, 27, 64);
1552         EXPECT_TRUE(alloc32b != alloc64b);
1553
1554         total += 96;
1555         getHeapStats(&heapStats);
1556         CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1557         if (testPagesAllocated)
1558             EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1559     }
1560
1561     clearOutOldGarbage(&heapStats);
1562     total -= 96;
1563     slack -= 8;
1564     if (testPagesAllocated)
1565         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1566
1567     DynamicallySizedObject* bigAreaRaw = bigArea;
1568     // Clear the persistent, so that the big area will be garbage collected.
1569     bigArea.release();
1570     clearOutOldGarbage(&heapStats);
1571
1572     total -= big;
1573     slack -= 4;
1574     getHeapStats(&heapStats);
1575     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1576     if (testPagesAllocated)
1577         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1578
1579     // Endless loop unless we eventually get the memory back that we just freed.
1580     while (true) {
1581         Persistent<DynamicallySizedObject>* alloc = new Persistent<DynamicallySizedObject>(DynamicallySizedObject::create(big / 2));
1582         slack += 4;
1583         persistents[persistentCount++] = alloc;
1584         EXPECT_LT(persistentCount, numPersistents);
1585         total += big / 2;
1586         if (bigAreaRaw == alloc->get())
1587             break;
1588     }
1589
1590     getHeapStats(&heapStats);
1591     CheckWithSlack(baseLevel + total, heapStats.totalObjectSpace(), slack);
1592     if (testPagesAllocated)
1593         EXPECT_EQ(0ul, heapStats.totalAllocatedSpace() & (blinkPageSize - 1));
1594
1595     for (size_t i = 0; i < persistentCount; i++) {
1596         delete persistents[i];
1597         persistents[i] = 0;
1598     }
1599
1600     uint8_t* address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(0, 100));
1601     for (int i = 0; i < 100; i++)
1602         address[i] = i;
1603     address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(address, 100000));
1604     for (int i = 0; i < 100; i++)
1605         EXPECT_EQ(address[i], i);
1606     address = reinterpret_cast<uint8_t*>(Heap::reallocate<DynamicallySizedObject>(address, 50));
1607     for (int i = 0; i < 50; i++)
1608         EXPECT_EQ(address[i], i);
1609     // This should be equivalent to free(address).
1610     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<DynamicallySizedObject>(address, 0)), 0ul);
1611     // This should be equivalent to malloc(0).
1612     EXPECT_EQ(reinterpret_cast<uintptr_t>(Heap::reallocate<DynamicallySizedObject>(0, 0)), 0ul);
1613 }
1614
1615 TEST(HeapTest, SimpleAllocation)
1616 {
1617     HeapStats initialHeapStats;
1618     clearOutOldGarbage(&initialHeapStats);
1619     EXPECT_EQ(0ul, initialHeapStats.totalObjectSpace());
1620
1621     // Allocate an object in the heap.
1622     HeapAllocatedArray* array = new HeapAllocatedArray();
1623     HeapStats statsAfterAllocation;
1624     getHeapStats(&statsAfterAllocation);
1625     EXPECT_TRUE(statsAfterAllocation.totalObjectSpace() >= sizeof(HeapAllocatedArray));
1626
1627     // Sanity check of the contents in the heap.
1628     EXPECT_EQ(0, array->at(0));
1629     EXPECT_EQ(42, array->at(42));
1630     EXPECT_EQ(0, array->at(128));
1631     EXPECT_EQ(999 % 128, array->at(999));
1632 }
1633
1634 TEST(HeapTest, SimplePersistent)
1635 {
1636     Persistent<TraceCounter> traceCounter = TraceCounter::create();
1637     EXPECT_EQ(0, traceCounter->traceCount());
1638
1639     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1640     EXPECT_EQ(1, traceCounter->traceCount());
1641
1642     Persistent<ClassWithMember> classWithMember = ClassWithMember::create();
1643     EXPECT_EQ(0, classWithMember->traceCount());
1644
1645     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1646     EXPECT_EQ(1, classWithMember->traceCount());
1647     EXPECT_EQ(2, traceCounter->traceCount());
1648 }
1649
1650 TEST(HeapTest, SimpleFinalization)
1651 {
1652     {
1653         Persistent<SimpleFinalizedObject> finalized = SimpleFinalizedObject::create();
1654         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1655         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1656         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
1657     }
1658
1659     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1660     EXPECT_EQ(1, SimpleFinalizedObject::s_destructorCalls);
1661 }
1662
1663 TEST(HeapTest, Finalization)
1664 {
1665     {
1666         HeapTestSubClass* t1 = HeapTestSubClass::create();
1667         HeapTestSubClass* t2 = HeapTestSubClass::create();
1668         HeapTestSuperClass* t3 = HeapTestSuperClass::create();
1669         // FIXME(oilpan): Ignore unused variables.
1670         (void)t1;
1671         (void)t2;
1672         (void)t3;
1673     }
1674     // Nothing is marked so the GC should free everything and call
1675     // the finalizer on all three objects.
1676     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1677     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1678     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1679     // Destructors not called again when GCing again.
1680     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1681     EXPECT_EQ(2, HeapTestSubClass::s_destructorCalls);
1682     EXPECT_EQ(3, HeapTestSuperClass::s_destructorCalls);
1683 }
1684
1685 TEST(HeapTest, TypedHeapSanity)
1686 {
1687     // We use TraceCounter for allocating an object on the general heap.
1688     Persistent<TraceCounter> generalHeapObject = TraceCounter::create();
1689     Persistent<Node> typedHeapObject = Node::create();
1690     EXPECT_NE(pageHeaderFromObject(generalHeapObject.get()),
1691         pageHeaderFromObject(typedHeapObject.get()));
1692 }
1693
1694 TEST(HeapTest, NoAllocation)
1695 {
1696     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1697     {
1698         // Disallow allocation
1699         NoAllocationScope<AnyThread> noAllocationScope;
1700         EXPECT_FALSE(ThreadState::current()->isAllocationAllowed());
1701     }
1702     EXPECT_TRUE(ThreadState::current()->isAllocationAllowed());
1703 }
1704
1705 TEST(HeapTest, Members)
1706 {
1707     Bar::s_live = 0;
1708     {
1709         Persistent<Baz> h1;
1710         Persistent<Baz> h2;
1711         {
1712             h1 = Baz::create(Bar::create());
1713             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1714             EXPECT_EQ(1u, Bar::s_live);
1715             h2 = Baz::create(Bar::create());
1716             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1717             EXPECT_EQ(2u, Bar::s_live);
1718         }
1719         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1720         EXPECT_EQ(2u, Bar::s_live);
1721         h1->clear();
1722         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1723         EXPECT_EQ(1u, Bar::s_live);
1724     }
1725     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1726     EXPECT_EQ(0u, Bar::s_live);
1727 }
1728
1729 TEST(HeapTest, MarkTest)
1730 {
1731     {
1732         Bar::s_live = 0;
1733         Persistent<Bar> bar = Bar::create();
1734         EXPECT_TRUE(ThreadState::current()->contains(bar));
1735         EXPECT_EQ(1u, Bar::s_live);
1736         {
1737             Foo* foo = Foo::create(bar);
1738             EXPECT_TRUE(ThreadState::current()->contains(foo));
1739             EXPECT_EQ(2u, Bar::s_live);
1740             EXPECT_TRUE(reinterpret_cast<Address>(foo) != reinterpret_cast<Address>(bar.get()));
1741             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1742             EXPECT_TRUE(foo != bar); // To make sure foo is kept alive.
1743             EXPECT_EQ(2u, Bar::s_live);
1744         }
1745         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1746         EXPECT_EQ(1u, Bar::s_live);
1747     }
1748     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1749     EXPECT_EQ(0u, Bar::s_live);
1750 }
1751
1752 TEST(HeapTest, DeepTest)
1753 {
1754     const unsigned depth = 100000;
1755     Bar::s_live = 0;
1756     {
1757         Bar* bar = Bar::create();
1758         EXPECT_TRUE(ThreadState::current()->contains(bar));
1759         Foo* foo = Foo::create(bar);
1760         EXPECT_TRUE(ThreadState::current()->contains(foo));
1761         EXPECT_EQ(2u, Bar::s_live);
1762         for (unsigned i = 0; i < depth; i++) {
1763             Foo* foo2 = Foo::create(foo);
1764             foo = foo2;
1765             EXPECT_TRUE(ThreadState::current()->contains(foo));
1766         }
1767         EXPECT_EQ(depth + 2, Bar::s_live);
1768         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1769         EXPECT_TRUE(foo != bar); // To make sure foo and bar are kept alive.
1770         EXPECT_EQ(depth + 2, Bar::s_live);
1771     }
1772     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1773     EXPECT_EQ(0u, Bar::s_live);
1774 }
1775
1776 TEST(HeapTest, WideTest)
1777 {
1778     Bar::s_live = 0;
1779     {
1780         Bars* bars = Bars::create();
1781         unsigned width = Bars::width;
1782         EXPECT_EQ(width + 1, Bar::s_live);
1783         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
1784         EXPECT_EQ(width + 1, Bar::s_live);
1785         // Use bars here to make sure that it will be on the stack
1786         // for the conservative stack scan to find.
1787         EXPECT_EQ(width, bars->getWidth());
1788     }
1789     EXPECT_EQ(Bars::width + 1, Bar::s_live);
1790     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1791     EXPECT_EQ(0u, Bar::s_live);
1792 }
1793
1794 TEST(HeapTest, HashMapOfMembers)
1795 {
1796     HeapStats initialHeapSize;
1797     IntWrapper::s_destructorCalls = 0;
1798
1799     clearOutOldGarbage(&initialHeapSize);
1800     {
1801         typedef HeapHashMap<
1802             Member<IntWrapper>,
1803             Member<IntWrapper>,
1804             DefaultHash<Member<IntWrapper> >::Hash,
1805             HashTraits<Member<IntWrapper> >,
1806             HashTraits<Member<IntWrapper> > > HeapObjectIdentityMap;
1807
1808         Persistent<HeapObjectIdentityMap> map = new HeapObjectIdentityMap();
1809
1810         map->clear();
1811         HeapStats afterSetWasCreated;
1812         getHeapStats(&afterSetWasCreated);
1813         EXPECT_TRUE(afterSetWasCreated.totalObjectSpace() > initialHeapSize.totalObjectSpace());
1814
1815         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1816         HeapStats afterGC;
1817         getHeapStats(&afterGC);
1818         EXPECT_EQ(afterGC.totalObjectSpace(), afterSetWasCreated.totalObjectSpace());
1819
1820         // If the additions below cause garbage collections, these
1821         // pointers should be found by conservative stack scanning.
1822         IntWrapper* one(IntWrapper::create(1));
1823         IntWrapper* anotherOne(IntWrapper::create(1));
1824
1825         map->add(one, one);
1826
1827         HeapStats afterOneAdd;
1828         getHeapStats(&afterOneAdd);
1829         EXPECT_TRUE(afterOneAdd.totalObjectSpace() > afterGC.totalObjectSpace());
1830
1831         HeapObjectIdentityMap::iterator it(map->begin());
1832         HeapObjectIdentityMap::iterator it2(map->begin());
1833         ++it;
1834         ++it2;
1835
1836         map->add(anotherOne, one);
1837
1838         // The addition above can cause an allocation of a new
1839         // backing store. We therefore garbage collect before
1840         // taking the heap stats in order to get rid of the old
1841         // backing store. We make sure to not use conservative
1842         // stack scanning as that could find a pointer to the
1843         // old backing.
1844         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1845         HeapStats afterAddAndGC;
1846         getHeapStats(&afterAddAndGC);
1847         EXPECT_TRUE(afterAddAndGC.totalObjectSpace() >= afterOneAdd.totalObjectSpace());
1848
1849         EXPECT_EQ(map->size(), 2u); // Two different wrappings of '1' are distinct.
1850
1851         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1852         EXPECT_TRUE(map->contains(one));
1853         EXPECT_TRUE(map->contains(anotherOne));
1854
1855         IntWrapper* gotten(map->get(one));
1856         EXPECT_EQ(gotten->value(), one->value());
1857         EXPECT_EQ(gotten, one);
1858
1859         HeapStats afterGC2;
1860         getHeapStats(&afterGC2);
1861         EXPECT_EQ(afterGC2.totalObjectSpace(), afterAddAndGC.totalObjectSpace());
1862
1863         IntWrapper* dozen = 0;
1864
1865         for (int i = 1; i < 1000; i++) { // 999 iterations.
1866             IntWrapper* iWrapper(IntWrapper::create(i));
1867             IntWrapper* iSquared(IntWrapper::create(i * i));
1868             map->add(iWrapper, iSquared);
1869             if (i == 12)
1870                 dozen = iWrapper;
1871         }
1872         HeapStats afterAdding1000;
1873         getHeapStats(&afterAdding1000);
1874         EXPECT_TRUE(afterAdding1000.totalObjectSpace() > afterGC2.totalObjectSpace());
1875
1876         IntWrapper* gross(map->get(dozen));
1877         EXPECT_EQ(gross->value(), 144);
1878
1879         // This should clear out junk created by all the adds.
1880         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1881         HeapStats afterGC3;
1882         getHeapStats(&afterGC3);
1883         EXPECT_TRUE(afterGC3.totalObjectSpace() < afterAdding1000.totalObjectSpace());
1884     }
1885
1886     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1887     // The objects 'one', anotherOne, and the 999 other pairs.
1888     EXPECT_EQ(IntWrapper::s_destructorCalls, 2000);
1889     HeapStats afterGC4;
1890     getHeapStats(&afterGC4);
1891     EXPECT_EQ(afterGC4.totalObjectSpace(), initialHeapSize.totalObjectSpace());
1892 }
1893
1894 TEST(HeapTest, NestedAllocation)
1895 {
1896     HeapStats initialHeapSize;
1897     clearOutOldGarbage(&initialHeapSize);
1898     {
1899         Persistent<ConstructorAllocation> constructorAllocation = ConstructorAllocation::create();
1900     }
1901     HeapStats afterFree;
1902     clearOutOldGarbage(&afterFree);
1903     EXPECT_TRUE(initialHeapSize == afterFree);
1904 }
1905
1906 TEST(HeapTest, LargeObjects)
1907 {
1908     HeapStats initialHeapSize;
1909     clearOutOldGarbage(&initialHeapSize);
1910     IntWrapper::s_destructorCalls = 0;
1911     LargeObject::s_destructorCalls = 0;
1912     {
1913         int slack = 8; // LargeObject points to an IntWrapper that is also allocated.
1914         Persistent<LargeObject> object = LargeObject::create();
1915         EXPECT_TRUE(ThreadState::current()->contains(object));
1916         EXPECT_TRUE(ThreadState::current()->contains(reinterpret_cast<char*>(object.get()) + sizeof(LargeObject) - 1));
1917 #if ENABLE(GC_PROFILE_MARKING)
1918         const GCInfo* info = ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()));
1919         EXPECT_NE(reinterpret_cast<const GCInfo*>(0), info);
1920         EXPECT_EQ(info, ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()) + sizeof(LargeObject) - 1));
1921         EXPECT_NE(info, ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()) + sizeof(LargeObject)));
1922         EXPECT_NE(info, ThreadState::current()->findGCInfo(reinterpret_cast<Address>(object.get()) - 1));
1923 #endif
1924         HeapStats afterAllocation;
1925         clearOutOldGarbage(&afterAllocation);
1926         {
1927             object->set(0, 'a');
1928             EXPECT_EQ('a', object->get(0));
1929             object->set(object->length() - 1, 'b');
1930             EXPECT_EQ('b', object->get(object->length() - 1));
1931             size_t expectedObjectSpace = sizeof(LargeObject) + sizeof(IntWrapper);
1932             size_t actualObjectSpace =
1933                 afterAllocation.totalObjectSpace() - initialHeapSize.totalObjectSpace();
1934             CheckWithSlack(expectedObjectSpace, actualObjectSpace, slack);
1935             // There is probably space for the IntWrapper in a heap page without
1936             // allocating extra pages. However, the IntWrapper allocation might cause
1937             // the addition of a heap page.
1938             size_t largeObjectAllocationSize =
1939                 sizeof(LargeObject) + sizeof(LargeHeapObject<FinalizedHeapObjectHeader>) + sizeof(FinalizedHeapObjectHeader);
1940             size_t allocatedSpaceLowerBound =
1941                 initialHeapSize.totalAllocatedSpace() + largeObjectAllocationSize;
1942             size_t allocatedSpaceUpperBound = allocatedSpaceLowerBound + slack + blinkPageSize;
1943             EXPECT_LE(allocatedSpaceLowerBound, afterAllocation.totalAllocatedSpace());
1944             EXPECT_LE(afterAllocation.totalAllocatedSpace(), allocatedSpaceUpperBound);
1945             EXPECT_EQ(0, IntWrapper::s_destructorCalls);
1946             EXPECT_EQ(0, LargeObject::s_destructorCalls);
1947             for (int i = 0; i < 10; i++)
1948                 object = LargeObject::create();
1949         }
1950         HeapStats oneLargeObject;
1951         clearOutOldGarbage(&oneLargeObject);
1952         EXPECT_TRUE(oneLargeObject == afterAllocation);
1953         EXPECT_EQ(10, IntWrapper::s_destructorCalls);
1954         EXPECT_EQ(10, LargeObject::s_destructorCalls);
1955     }
1956     HeapStats backToInitial;
1957     clearOutOldGarbage(&backToInitial);
1958     EXPECT_TRUE(initialHeapSize == backToInitial);
1959     EXPECT_EQ(11, IntWrapper::s_destructorCalls);
1960     EXPECT_EQ(11, LargeObject::s_destructorCalls);
1961     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
1962 }
1963
1964 typedef std::pair<Member<IntWrapper>, int> PairWrappedUnwrapped;
1965 typedef std::pair<int, Member<IntWrapper> > PairUnwrappedWrapped;
1966 typedef std::pair<WeakMember<IntWrapper>, Member<IntWrapper> > PairWeakStrong;
1967 typedef std::pair<Member<IntWrapper>, WeakMember<IntWrapper> > PairStrongWeak;
1968 typedef std::pair<WeakMember<IntWrapper>, int> PairWeakUnwrapped;
1969 typedef std::pair<int, WeakMember<IntWrapper> > PairUnwrappedWeak;
1970
1971 class Container : public GarbageCollected<Container> {
1972 public:
1973     static Container* create() { return new Container(); }
1974     HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > map;
1975     HeapHashSet<Member<IntWrapper> > set;
1976     HeapHashSet<Member<IntWrapper> > set2;
1977     HeapHashCountedSet<Member<IntWrapper> > set3;
1978     HeapVector<Member<IntWrapper>, 2> vector;
1979     HeapVector<PairWrappedUnwrapped, 2> vectorWU;
1980     HeapVector<PairUnwrappedWrapped, 2> vectorUW;
1981     HeapDeque<Member<IntWrapper>, 0> deque;
1982     HeapDeque<PairWrappedUnwrapped, 0> dequeWU;
1983     HeapDeque<PairUnwrappedWrapped, 0> dequeUW;
1984     void trace(Visitor* visitor)
1985     {
1986         visitor->trace(map);
1987         visitor->trace(set);
1988         visitor->trace(set2);
1989         visitor->trace(set3);
1990         visitor->trace(vector);
1991         visitor->trace(vectorWU);
1992         visitor->trace(vectorUW);
1993         visitor->trace(deque);
1994         visitor->trace(dequeWU);
1995         visitor->trace(dequeUW);
1996     }
1997 };
1998
1999 struct ShouldBeTraced {
2000     explicit ShouldBeTraced(IntWrapper* wrapper) : m_wrapper(wrapper) { }
2001     void trace(Visitor* visitor) { visitor->trace(m_wrapper); }
2002     Member<IntWrapper> m_wrapper;
2003 };
2004
2005 class OffHeapContainer : public GarbageCollectedFinalized<OffHeapContainer> {
2006 public:
2007     static OffHeapContainer* create() { return new OffHeapContainer(); }
2008
2009     static const int iterations = 300;
2010     static const int deadWrappers = 1200;
2011
2012     OffHeapContainer()
2013     {
2014         for (int i = 0; i < iterations; i++) {
2015             m_deque1.append(ShouldBeTraced(IntWrapper::create(i)));
2016             m_vector1.append(ShouldBeTraced(IntWrapper::create(i)));
2017             m_deque2.append(IntWrapper::create(i));
2018             m_vector2.append(IntWrapper::create(i));
2019         }
2020
2021         Deque<ShouldBeTraced>::iterator d1Iterator(m_deque1.begin());
2022         Vector<ShouldBeTraced>::iterator v1Iterator(m_vector1.begin());
2023         Deque<Member<IntWrapper> >::iterator d2Iterator(m_deque2.begin());
2024         Vector<Member<IntWrapper> >::iterator v2Iterator(m_vector2.begin());
2025
2026         for (int i = 0; i < iterations; i++) {
2027             EXPECT_EQ(i, m_vector1[i].m_wrapper->value());
2028             EXPECT_EQ(i, m_vector2[i]->value());
2029             EXPECT_EQ(i, d1Iterator->m_wrapper->value());
2030             EXPECT_EQ(i, v1Iterator->m_wrapper->value());
2031             EXPECT_EQ(i, d2Iterator->get()->value());
2032             EXPECT_EQ(i, v2Iterator->get()->value());
2033             ++d1Iterator;
2034             ++v1Iterator;
2035             ++d2Iterator;
2036             ++v2Iterator;
2037         }
2038         EXPECT_EQ(d1Iterator, m_deque1.end());
2039         EXPECT_EQ(v1Iterator, m_vector1.end());
2040         EXPECT_EQ(d2Iterator, m_deque2.end());
2041         EXPECT_EQ(v2Iterator, m_vector2.end());
2042     }
2043
2044     void trace(Visitor* visitor)
2045     {
2046         visitor->trace(m_deque1);
2047         visitor->trace(m_vector1);
2048         visitor->trace(m_deque2);
2049         visitor->trace(m_vector2);
2050     }
2051
2052     Deque<ShouldBeTraced> m_deque1;
2053     Vector<ShouldBeTraced> m_vector1;
2054     Deque<Member<IntWrapper> > m_deque2;
2055     Vector<Member<IntWrapper> > m_vector2;
2056 };
2057
2058 const int OffHeapContainer::iterations;
2059 const int OffHeapContainer::deadWrappers;
2060
2061 // These class definitions test compile-time asserts with transition
2062 // types. They are therefore unused in test code and just need to
2063 // compile. This is intentional; do not delete the A and B classes below.
2064 class A : public WillBeGarbageCollectedMixin {
2065 };
2066
2067 class B : public NoBaseWillBeGarbageCollected<B>, public A {
2068     WILL_BE_USING_GARBAGE_COLLECTED_MIXIN(B);
2069 public:
2070     void trace(Visitor*) { }
2071 };
2072
2073 TEST(HeapTest, HeapVectorFilledWithValue)
2074 {
2075     IntWrapper* val = IntWrapper::create(1);
2076     HeapVector<Member<IntWrapper> > vector(10, val);
2077     EXPECT_EQ(10u, vector.size());
2078     for (size_t i = 0; i < vector.size(); i++)
2079         EXPECT_EQ(val, vector[i]);
2080 }
2081
2082 TEST(HeapTest, HeapVectorWithInlineCapacity)
2083 {
2084     IntWrapper* one = IntWrapper::create(1);
2085     IntWrapper* two = IntWrapper::create(2);
2086     IntWrapper* three = IntWrapper::create(3);
2087     IntWrapper* four = IntWrapper::create(4);
2088     IntWrapper* five = IntWrapper::create(5);
2089     IntWrapper* six = IntWrapper::create(6);
2090     {
2091         HeapVector<Member<IntWrapper>, 2> vector;
2092         vector.append(one);
2093         vector.append(two);
2094         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2095         EXPECT_TRUE(vector.contains(one));
2096         EXPECT_TRUE(vector.contains(two));
2097
2098         vector.append(three);
2099         vector.append(four);
2100         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2101         EXPECT_TRUE(vector.contains(one));
2102         EXPECT_TRUE(vector.contains(two));
2103         EXPECT_TRUE(vector.contains(three));
2104         EXPECT_TRUE(vector.contains(four));
2105
2106         vector.shrink(1);
2107         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2108         EXPECT_TRUE(vector.contains(one));
2109         EXPECT_FALSE(vector.contains(two));
2110         EXPECT_FALSE(vector.contains(three));
2111         EXPECT_FALSE(vector.contains(four));
2112     }
2113     {
2114         HeapVector<Member<IntWrapper>, 2> vector1;
2115         HeapVector<Member<IntWrapper>, 2> vector2;
2116
2117         vector1.append(one);
2118         vector2.append(two);
2119         vector1.swap(vector2);
2120         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2121         EXPECT_TRUE(vector1.contains(two));
2122         EXPECT_TRUE(vector2.contains(one));
2123     }
2124     {
2125         HeapVector<Member<IntWrapper>, 2> vector1;
2126         HeapVector<Member<IntWrapper>, 2> vector2;
2127
2128         vector1.append(one);
2129         vector1.append(two);
2130         vector2.append(three);
2131         vector2.append(four);
2132         vector2.append(five);
2133         vector2.append(six);
2134         vector1.swap(vector2);
2135         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2136         EXPECT_TRUE(vector1.contains(three));
2137         EXPECT_TRUE(vector1.contains(four));
2138         EXPECT_TRUE(vector1.contains(five));
2139         EXPECT_TRUE(vector1.contains(six));
2140         EXPECT_TRUE(vector2.contains(one));
2141         EXPECT_TRUE(vector2.contains(two));
2142     }
2143 }
2144
2145 template<typename T, size_t inlineCapacity, typename U>
2146 bool dequeContains(HeapDeque<T, inlineCapacity>& deque, U u)
2147 {
2148     typedef typename HeapDeque<T, inlineCapacity>::iterator iterator;
2149     for (iterator it = deque.begin(); it != deque.end(); ++it) {
2150         if (*it == u)
2151             return true;
2152     }
2153     return false;
2154 }
2155
2156 TEST(HeapTest, HeapCollectionTypes)
2157 {
2158     HeapStats initialHeapSize;
2159     IntWrapper::s_destructorCalls = 0;
2160
2161     typedef HeapHashMap<Member<IntWrapper>, Member<IntWrapper> > MemberMember;
2162     typedef HeapHashMap<Member<IntWrapper>, int> MemberPrimitive;
2163     typedef HeapHashMap<int, Member<IntWrapper> > PrimitiveMember;
2164
2165     typedef HeapHashSet<Member<IntWrapper> > MemberSet;
2166     typedef HeapHashCountedSet<Member<IntWrapper> > MemberCountedSet;
2167
2168     typedef HeapVector<Member<IntWrapper>, 2> MemberVector;
2169     typedef HeapDeque<Member<IntWrapper>, 0> MemberDeque;
2170
2171     typedef HeapVector<PairWrappedUnwrapped, 2> VectorWU;
2172     typedef HeapVector<PairUnwrappedWrapped, 2> VectorUW;
2173     typedef HeapDeque<PairWrappedUnwrapped, 0> DequeWU;
2174     typedef HeapDeque<PairUnwrappedWrapped, 0> DequeUW;
2175
2176     Persistent<MemberMember> memberMember = new MemberMember();
2177     Persistent<MemberMember> memberMember2 = new MemberMember();
2178     Persistent<MemberMember> memberMember3 = new MemberMember();
2179     Persistent<MemberPrimitive> memberPrimitive = new MemberPrimitive();
2180     Persistent<PrimitiveMember> primitiveMember = new PrimitiveMember();
2181     Persistent<MemberSet> set = new MemberSet();
2182     Persistent<MemberSet> set2 = new MemberSet();
2183     Persistent<MemberCountedSet> set3 = new MemberCountedSet();
2184     Persistent<MemberVector> vector = new MemberVector();
2185     Persistent<MemberVector> vector2 = new MemberVector();
2186     Persistent<VectorWU> vectorWU = new VectorWU();
2187     Persistent<VectorWU> vectorWU2 = new VectorWU();
2188     Persistent<VectorUW> vectorUW = new VectorUW();
2189     Persistent<VectorUW> vectorUW2 = new VectorUW();
2190     Persistent<MemberDeque> deque = new MemberDeque();
2191     Persistent<MemberDeque> deque2 = new MemberDeque();
2192     Persistent<DequeWU> dequeWU = new DequeWU();
2193     Persistent<DequeWU> dequeWU2 = new DequeWU();
2194     Persistent<DequeUW> dequeUW = new DequeUW();
2195     Persistent<DequeUW> dequeUW2 = new DequeUW();
2196     Persistent<Container> container = Container::create();
2197
2198     clearOutOldGarbage(&initialHeapSize);
2199     {
2200         Persistent<IntWrapper> one(IntWrapper::create(1));
2201         Persistent<IntWrapper> two(IntWrapper::create(2));
2202         Persistent<IntWrapper> oneB(IntWrapper::create(1));
2203         Persistent<IntWrapper> twoB(IntWrapper::create(2));
2204         Persistent<IntWrapper> oneC(IntWrapper::create(1));
2205         Persistent<IntWrapper> oneD(IntWrapper::create(1));
2206         Persistent<IntWrapper> oneE(IntWrapper::create(1));
2207         Persistent<IntWrapper> oneF(IntWrapper::create(1));
2208         {
2209             IntWrapper* threeB(IntWrapper::create(3));
2210             IntWrapper* threeC(IntWrapper::create(3));
2211             IntWrapper* threeD(IntWrapper::create(3));
2212             IntWrapper* threeE(IntWrapper::create(3));
2213             IntWrapper* threeF(IntWrapper::create(3));
2214             IntWrapper* three(IntWrapper::create(3));
2215             IntWrapper* fourB(IntWrapper::create(4));
2216             IntWrapper* fourC(IntWrapper::create(4));
2217             IntWrapper* fourD(IntWrapper::create(4));
2218             IntWrapper* fourE(IntWrapper::create(4));
2219             IntWrapper* fourF(IntWrapper::create(4));
2220             IntWrapper* four(IntWrapper::create(4));
2221             IntWrapper* fiveC(IntWrapper::create(5));
2222             IntWrapper* fiveD(IntWrapper::create(5));
2223             IntWrapper* fiveE(IntWrapper::create(5));
2224             IntWrapper* fiveF(IntWrapper::create(5));
2225
2226             // Member Collections.
2227             memberMember2->add(one, two);
2228             memberMember2->add(two, three);
2229             memberMember2->add(three, four);
2230             memberMember2->add(four, one);
2231             primitiveMember->add(1, two);
2232             primitiveMember->add(2, three);
2233             primitiveMember->add(3, four);
2234             primitiveMember->add(4, one);
2235             memberPrimitive->add(one, 2);
2236             memberPrimitive->add(two, 3);
2237             memberPrimitive->add(three, 4);
2238             memberPrimitive->add(four, 1);
2239             set2->add(one);
2240             set2->add(two);
2241             set2->add(three);
2242             set2->add(four);
2243             set->add(oneB);
2244             set3->add(oneB);
2245             set3->add(oneB);
2246             vector->append(oneB);
2247             deque->append(oneB);
2248             vector2->append(threeB);
2249             vector2->append(fourB);
2250             deque2->append(threeE);
2251             deque2->append(fourE);
2252             vectorWU->append(PairWrappedUnwrapped(&*oneC, 42));
2253             dequeWU->append(PairWrappedUnwrapped(&*oneE, 42));
2254             vectorWU2->append(PairWrappedUnwrapped(&*threeC, 43));
2255             vectorWU2->append(PairWrappedUnwrapped(&*fourC, 44));
2256             vectorWU2->append(PairWrappedUnwrapped(&*fiveC, 45));
2257             dequeWU2->append(PairWrappedUnwrapped(&*threeE, 43));
2258             dequeWU2->append(PairWrappedUnwrapped(&*fourE, 44));
2259             dequeWU2->append(PairWrappedUnwrapped(&*fiveE, 45));
2260             vectorUW->append(PairUnwrappedWrapped(1, &*oneD));
2261             vectorUW2->append(PairUnwrappedWrapped(103, &*threeD));
2262             vectorUW2->append(PairUnwrappedWrapped(104, &*fourD));
2263             vectorUW2->append(PairUnwrappedWrapped(105, &*fiveD));
2264             dequeUW->append(PairUnwrappedWrapped(1, &*oneF));
2265             dequeUW2->append(PairUnwrappedWrapped(103, &*threeF));
2266             dequeUW2->append(PairUnwrappedWrapped(104, &*fourF));
2267             dequeUW2->append(PairUnwrappedWrapped(105, &*fiveF));
2268
2269             EXPECT_TRUE(dequeContains(*deque, oneB));
2270
2271             // Collect garbage. This should change nothing since we are keeping
2272             // alive the IntWrapper objects with on-stack pointers.
2273             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
2274
2275             EXPECT_TRUE(dequeContains(*deque, oneB));
2276
2277             EXPECT_EQ(0u, memberMember->size());
2278             EXPECT_EQ(4u, memberMember2->size());
2279             EXPECT_EQ(4u, primitiveMember->size());
2280             EXPECT_EQ(4u, memberPrimitive->size());
2281             EXPECT_EQ(1u, set->size());
2282             EXPECT_EQ(4u, set2->size());
2283             EXPECT_EQ(1u, set3->size());
2284             EXPECT_EQ(1u, vector->size());
2285             EXPECT_EQ(2u, vector2->size());
2286             EXPECT_EQ(1u, vectorWU->size());
2287             EXPECT_EQ(3u, vectorWU2->size());
2288             EXPECT_EQ(1u, vectorUW->size());
2289             EXPECT_EQ(3u, vectorUW2->size());
2290             EXPECT_EQ(1u, deque->size());
2291             EXPECT_EQ(2u, deque2->size());
2292             EXPECT_EQ(1u, dequeWU->size());
2293             EXPECT_EQ(3u, dequeWU2->size());
2294             EXPECT_EQ(1u, dequeUW->size());
2295             EXPECT_EQ(3u, dequeUW2->size());
2296
2297             MemberVector& cvec = container->vector;
2298             cvec.swap(*vector.get());
2299             vector2->swap(cvec);
2300             vector->swap(cvec);
2301
2302             VectorWU& cvecWU = container->vectorWU;
2303             cvecWU.swap(*vectorWU.get());
2304             vectorWU2->swap(cvecWU);
2305             vectorWU->swap(cvecWU);
2306
2307             VectorUW& cvecUW = container->vectorUW;
2308             cvecUW.swap(*vectorUW.get());
2309             vectorUW2->swap(cvecUW);
2310             vectorUW->swap(cvecUW);
2311
2312             MemberDeque& cDeque = container->deque;
2313             cDeque.swap(*deque.get());
2314             deque2->swap(cDeque);
2315             deque->swap(cDeque);
2316
2317             DequeWU& cDequeWU = container->dequeWU;
2318             cDequeWU.swap(*dequeWU.get());
2319             dequeWU2->swap(cDequeWU);
2320             dequeWU->swap(cDequeWU);
2321
2322             DequeUW& cDequeUW = container->dequeUW;
2323             cDequeUW.swap(*dequeUW.get());
2324             dequeUW2->swap(cDequeUW);
2325             dequeUW->swap(cDequeUW);
2326
2327             // Swap set and set2 in a roundabout way.
2328             MemberSet& cset1 = container->set;
2329             MemberSet& cset2 = container->set2;
2330             set->swap(cset1);
2331             set2->swap(cset2);
2332             set->swap(cset2);
2333             cset1.swap(cset2);
2334             cset2.swap(set2);
2335
2336             MemberCountedSet& cCountedSet = container->set3;
2337             set3->swap(cCountedSet);
2338             EXPECT_EQ(0u, set3->size());
2339             set3->swap(cCountedSet);
2340
2341             // Triple swap.
2342             container->map.swap(memberMember2);
2343             MemberMember& containedMap = container->map;
2344             memberMember3->swap(containedMap);
2345             memberMember3->swap(memberMember);
2346
2347             EXPECT_TRUE(memberMember->get(one) == two);
2348             EXPECT_TRUE(memberMember->get(two) == three);
2349             EXPECT_TRUE(memberMember->get(three) == four);
2350             EXPECT_TRUE(memberMember->get(four) == one);
2351             EXPECT_TRUE(primitiveMember->get(1) == two);
2352             EXPECT_TRUE(primitiveMember->get(2) == three);
2353             EXPECT_TRUE(primitiveMember->get(3) == four);
2354             EXPECT_TRUE(primitiveMember->get(4) == one);
2355             EXPECT_EQ(1, memberPrimitive->get(four));
2356             EXPECT_EQ(2, memberPrimitive->get(one));
2357             EXPECT_EQ(3, memberPrimitive->get(two));
2358             EXPECT_EQ(4, memberPrimitive->get(three));
2359             EXPECT_TRUE(set->contains(one));
2360             EXPECT_TRUE(set->contains(two));
2361             EXPECT_TRUE(set->contains(three));
2362             EXPECT_TRUE(set->contains(four));
2363             EXPECT_TRUE(set2->contains(oneB));
2364             EXPECT_TRUE(set3->contains(oneB));
2365             EXPECT_TRUE(vector->contains(threeB));
2366             EXPECT_TRUE(vector->contains(fourB));
2367             EXPECT_TRUE(dequeContains(*deque, threeE));
2368             EXPECT_TRUE(dequeContains(*deque, fourE));
2369             EXPECT_TRUE(vector2->contains(oneB));
2370             EXPECT_FALSE(vector2->contains(threeB));
2371             EXPECT_TRUE(dequeContains(*deque2, oneB));
2372             EXPECT_FALSE(dequeContains(*deque2, threeE));
2373             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*threeC, 43)));
2374             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fourC, 44)));
2375             EXPECT_TRUE(vectorWU->contains(PairWrappedUnwrapped(&*fiveC, 45)));
2376             EXPECT_TRUE(vectorWU2->contains(PairWrappedUnwrapped(&*oneC, 42)));
2377             EXPECT_FALSE(vectorWU2->contains(PairWrappedUnwrapped(&*threeC, 43)));
2378             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(103, &*threeD)));
2379             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(104, &*fourD)));
2380             EXPECT_TRUE(vectorUW->contains(PairUnwrappedWrapped(105, &*fiveD)));
2381             EXPECT_TRUE(vectorUW2->contains(PairUnwrappedWrapped(1, &*oneD)));
2382             EXPECT_FALSE(vectorUW2->contains(PairUnwrappedWrapped(103, &*threeD)));
2383             EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*threeE, 43)));
2384             EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*fourE, 44)));
2385             EXPECT_TRUE(dequeContains(*dequeWU, PairWrappedUnwrapped(&*fiveE, 45)));
2386             EXPECT_TRUE(dequeContains(*dequeWU2, PairWrappedUnwrapped(&*oneE, 42)));
2387             EXPECT_FALSE(dequeContains(*dequeWU2, PairWrappedUnwrapped(&*threeE, 43)));
2388             EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(103, &*threeF)));
2389             EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(104, &*fourF)));
2390             EXPECT_TRUE(dequeContains(*dequeUW, PairUnwrappedWrapped(105, &*fiveF)));
2391             EXPECT_TRUE(dequeContains(*dequeUW2, PairUnwrappedWrapped(1, &*oneF)));
2392             EXPECT_FALSE(dequeContains(*dequeUW2, PairUnwrappedWrapped(103, &*threeF)));
2393         }
2394
2395         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2396
2397         EXPECT_EQ(4u, memberMember->size());
2398         EXPECT_EQ(0u, memberMember2->size());
2399         EXPECT_EQ(4u, primitiveMember->size());
2400         EXPECT_EQ(4u, memberPrimitive->size());
2401         EXPECT_EQ(4u, set->size());
2402         EXPECT_EQ(1u, set2->size());
2403         EXPECT_EQ(1u, set3->size());
2404         EXPECT_EQ(2u, vector->size());
2405         EXPECT_EQ(1u, vector2->size());
2406         EXPECT_EQ(3u, vectorUW->size());
2407         EXPECT_EQ(1u, vector2->size());
2408         EXPECT_EQ(2u, deque->size());
2409         EXPECT_EQ(1u, deque2->size());
2410         EXPECT_EQ(3u, dequeUW->size());
2411         EXPECT_EQ(1u, deque2->size());
2412
2413         EXPECT_TRUE(memberMember->get(one) == two);
2414         EXPECT_TRUE(primitiveMember->get(1) == two);
2415         EXPECT_TRUE(primitiveMember->get(4) == one);
2416         EXPECT_EQ(2, memberPrimitive->get(one));
2417         EXPECT_EQ(3, memberPrimitive->get(two));
2418         EXPECT_TRUE(set->contains(one));
2419         EXPECT_TRUE(set->contains(two));
2420         EXPECT_FALSE(set->contains(oneB));
2421         EXPECT_TRUE(set2->contains(oneB));
2422         EXPECT_TRUE(set3->contains(oneB));
2423         EXPECT_EQ(2u, set3->find(oneB)->value);
2424         EXPECT_EQ(3, vector->at(0)->value());
2425         EXPECT_EQ(4, vector->at(1)->value());
2426         EXPECT_EQ(3, deque->begin()->get()->value());
2427     }
2428
2429     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2430     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2431
2432     EXPECT_EQ(4u, memberMember->size());
2433     EXPECT_EQ(4u, primitiveMember->size());
2434     EXPECT_EQ(4u, memberPrimitive->size());
2435     EXPECT_EQ(4u, set->size());
2436     EXPECT_EQ(1u, set2->size());
2437     EXPECT_EQ(2u, vector->size());
2438     EXPECT_EQ(1u, vector2->size());
2439     EXPECT_EQ(3u, vectorWU->size());
2440     EXPECT_EQ(1u, vectorWU2->size());
2441     EXPECT_EQ(3u, vectorUW->size());
2442     EXPECT_EQ(1u, vectorUW2->size());
2443     EXPECT_EQ(2u, deque->size());
2444     EXPECT_EQ(1u, deque2->size());
2445     EXPECT_EQ(3u, dequeWU->size());
2446     EXPECT_EQ(1u, dequeWU2->size());
2447     EXPECT_EQ(3u, dequeUW->size());
2448     EXPECT_EQ(1u, dequeUW2->size());
2449 }
2450
2451 template<typename T>
2452 void MapIteratorCheck(T& it, const T& end, int expected)
2453 {
2454     int found = 0;
2455     while (it != end) {
2456         found++;
2457         int key = it->key->value();
2458         int value = it->value->value();
2459         EXPECT_TRUE(key >= 0 && key < 1100);
2460         EXPECT_TRUE(value >= 0 && value < 1100);
2461         ++it;
2462     }
2463     EXPECT_EQ(expected, found);
2464 }
2465
2466 template<typename T>
2467 void SetIteratorCheck(T& it, const T& end, int expected)
2468 {
2469     int found = 0;
2470     while (it != end) {
2471         found++;
2472         int value = (*it)->value();
2473         EXPECT_TRUE(value >= 0 && value < 1100);
2474         ++it;
2475     }
2476     EXPECT_EQ(expected, found);
2477 }
2478
2479 TEST(HeapTest, HeapWeakCollectionSimple)
2480 {
2481     HeapStats initialHeapStats;
2482     clearOutOldGarbage(&initialHeapStats);
2483     IntWrapper::s_destructorCalls = 0;
2484
2485     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2486
2487     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
2488     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
2489     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
2490     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
2491     typedef HeapHashCountedSet<WeakMember<IntWrapper> > WeakCountedSet;
2492
2493     Persistent<WeakStrong> weakStrong = new WeakStrong();
2494     Persistent<StrongWeak> strongWeak = new StrongWeak();
2495     Persistent<WeakWeak> weakWeak = new WeakWeak();
2496     Persistent<WeakSet> weakSet = new WeakSet();
2497     Persistent<WeakCountedSet> weakCountedSet = new WeakCountedSet();
2498
2499     Persistent<IntWrapper> two = IntWrapper::create(2);
2500
2501     keepNumbersAlive.append(IntWrapper::create(103));
2502     keepNumbersAlive.append(IntWrapper::create(10));
2503
2504     {
2505         weakStrong->add(IntWrapper::create(1), two);
2506         strongWeak->add(two, IntWrapper::create(1));
2507         weakWeak->add(two, IntWrapper::create(42));
2508         weakWeak->add(IntWrapper::create(42), two);
2509         weakSet->add(IntWrapper::create(0));
2510         weakSet->add(two);
2511         weakSet->add(keepNumbersAlive[0]);
2512         weakSet->add(keepNumbersAlive[1]);
2513         weakCountedSet->add(IntWrapper::create(0));
2514         weakCountedSet->add(two);
2515         weakCountedSet->add(two);
2516         weakCountedSet->add(two);
2517         weakCountedSet->add(keepNumbersAlive[0]);
2518         weakCountedSet->add(keepNumbersAlive[1]);
2519         EXPECT_EQ(1u, weakStrong->size());
2520         EXPECT_EQ(1u, strongWeak->size());
2521         EXPECT_EQ(2u, weakWeak->size());
2522         EXPECT_EQ(4u, weakSet->size());
2523         EXPECT_EQ(4u, weakCountedSet->size());
2524         EXPECT_EQ(3u, weakCountedSet->find(two)->value);
2525         weakCountedSet->remove(two);
2526         EXPECT_EQ(2u, weakCountedSet->find(two)->value);
2527     }
2528
2529     keepNumbersAlive[0] = nullptr;
2530
2531     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2532
2533     EXPECT_EQ(0u, weakStrong->size());
2534     EXPECT_EQ(0u, strongWeak->size());
2535     EXPECT_EQ(0u, weakWeak->size());
2536     EXPECT_EQ(2u, weakSet->size());
2537     EXPECT_EQ(2u, weakCountedSet->size());
2538 }
2539
2540 template<typename Set>
2541 void orderedSetHelper(bool strong)
2542 {
2543     HeapStats initialHeapStats;
2544     clearOutOldGarbage(&initialHeapStats);
2545     IntWrapper::s_destructorCalls = 0;
2546
2547     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2548
2549     Persistent<Set> set1 = new Set();
2550     Persistent<Set> set2 = new Set();
2551
2552     const Set& constSet = *set1.get();
2553
2554     keepNumbersAlive.append(IntWrapper::create(2));
2555     keepNumbersAlive.append(IntWrapper::create(103));
2556     keepNumbersAlive.append(IntWrapper::create(10));
2557
2558     set1->add(IntWrapper::create(0));
2559     set1->add(keepNumbersAlive[0]);
2560     set1->add(keepNumbersAlive[1]);
2561     set1->add(keepNumbersAlive[2]);
2562
2563     set2->clear();
2564     set2->add(IntWrapper::create(42));
2565     set2->clear();
2566
2567     EXPECT_EQ(4u, set1->size());
2568     typename Set::iterator it(set1->begin());
2569     typename Set::reverse_iterator reverse(set1->rbegin());
2570     typename Set::const_iterator cit(constSet.begin());
2571     typename Set::const_reverse_iterator creverse(constSet.rbegin());
2572
2573     EXPECT_EQ(0, (*it)->value());
2574     EXPECT_EQ(0, (*cit)->value());
2575     ++it;
2576     ++cit;
2577     EXPECT_EQ(2, (*it)->value());
2578     EXPECT_EQ(2, (*cit)->value());
2579     --it;
2580     --cit;
2581     EXPECT_EQ(0, (*it)->value());
2582     EXPECT_EQ(0, (*cit)->value());
2583     ++it;
2584     ++cit;
2585     ++it;
2586     ++cit;
2587     EXPECT_EQ(103, (*it)->value());
2588     EXPECT_EQ(103, (*cit)->value());
2589     ++it;
2590     ++cit;
2591     EXPECT_EQ(10, (*it)->value());
2592     EXPECT_EQ(10, (*cit)->value());
2593     ++it;
2594     ++cit;
2595
2596     EXPECT_EQ(10, (*reverse)->value());
2597     EXPECT_EQ(10, (*creverse)->value());
2598     ++reverse;
2599     ++creverse;
2600     EXPECT_EQ(103, (*reverse)->value());
2601     EXPECT_EQ(103, (*creverse)->value());
2602     --reverse;
2603     --creverse;
2604     EXPECT_EQ(10, (*reverse)->value());
2605     EXPECT_EQ(10, (*creverse)->value());
2606     ++reverse;
2607     ++creverse;
2608     ++reverse;
2609     ++creverse;
2610     EXPECT_EQ(2, (*reverse)->value());
2611     EXPECT_EQ(2, (*creverse)->value());
2612     ++reverse;
2613     ++creverse;
2614     EXPECT_EQ(0, (*reverse)->value());
2615     EXPECT_EQ(0, (*creverse)->value());
2616     ++reverse;
2617     ++creverse;
2618
2619     EXPECT_EQ(set1->end(), it);
2620     EXPECT_EQ(constSet.end(), cit);
2621     EXPECT_EQ(set1->rend(), reverse);
2622     EXPECT_EQ(constSet.rend(), creverse);
2623
2624     typename Set::iterator iX(set2->begin());
2625     EXPECT_EQ(set2->end(), iX);
2626
2627     if (strong)
2628         set1->remove(keepNumbersAlive[0]);
2629
2630     keepNumbersAlive[0] = nullptr;
2631
2632     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2633
2634     EXPECT_EQ(2u + (strong ? 1u : 0u), set1->size());
2635
2636     EXPECT_EQ(2 + (strong ? 0 : 1), IntWrapper::s_destructorCalls);
2637
2638     typename Set::iterator i2(set1->begin());
2639     if (strong) {
2640         EXPECT_EQ(0, (*i2)->value());
2641         ++i2;
2642         EXPECT_NE(set1->end(), i2);
2643     }
2644     EXPECT_EQ(103, (*i2)->value());
2645     ++i2;
2646     EXPECT_NE(set1->end(), i2);
2647     EXPECT_EQ(10, (*i2)->value());
2648     ++i2;
2649     EXPECT_EQ(set1->end(), i2);
2650 }
2651
2652 TEST(HeapTest, HeapWeakLinkedHashSet)
2653 {
2654     orderedSetHelper<HeapLinkedHashSet<Member<IntWrapper> > >(true);
2655     orderedSetHelper<HeapLinkedHashSet<WeakMember<IntWrapper> > >(false);
2656     orderedSetHelper<HeapListHashSet<Member<IntWrapper> > >(true);
2657 }
2658
2659 class ThingWithDestructor {
2660 public:
2661     ThingWithDestructor()
2662         : m_x(emptyValue)
2663     {
2664         s_liveThingsWithDestructor++;
2665     }
2666
2667     ThingWithDestructor(int x)
2668         : m_x(x)
2669     {
2670         s_liveThingsWithDestructor++;
2671     }
2672
2673     ThingWithDestructor(const ThingWithDestructor&other)
2674     {
2675         *this = other;
2676         s_liveThingsWithDestructor++;
2677     }
2678
2679     ~ThingWithDestructor()
2680     {
2681         s_liveThingsWithDestructor--;
2682     }
2683
2684     int value() { return m_x; }
2685
2686     static int s_liveThingsWithDestructor;
2687
2688     unsigned hash() { return IntHash<int>::hash(m_x); }
2689
2690 private:
2691     static const int emptyValue = 0;
2692     int m_x;
2693 };
2694
2695 int ThingWithDestructor::s_liveThingsWithDestructor;
2696
2697 struct ThingWithDestructorTraits : public HashTraits<ThingWithDestructor> {
2698     static const bool needsDestruction = true;
2699 };
2700
2701 static void heapMapDestructorHelper(bool clearMaps)
2702 {
2703     HeapStats initialHeapStats;
2704     clearOutOldGarbage(&initialHeapStats);
2705     ThingWithDestructor::s_liveThingsWithDestructor = 0;
2706
2707     typedef HeapHashMap<WeakMember<IntWrapper>, RefPtr<RefCountedAndGarbageCollected> > RefMap;
2708
2709     typedef HeapHashMap<
2710         WeakMember<IntWrapper>,
2711         ThingWithDestructor,
2712         DefaultHash<WeakMember<IntWrapper> >::Hash,
2713         HashTraits<WeakMember<IntWrapper> >,
2714         ThingWithDestructorTraits> Map;
2715
2716     Persistent<Map> map(new Map());
2717     Persistent<RefMap> refMap(new RefMap());
2718
2719     Persistent<IntWrapper> luck(IntWrapper::create(103));
2720
2721     int baseLine, refBaseLine;
2722
2723     {
2724         Map stackMap;
2725         RefMap stackRefMap;
2726
2727         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2728         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2729
2730         stackMap.add(IntWrapper::create(42), ThingWithDestructor(1729));
2731         stackMap.add(luck, ThingWithDestructor(8128));
2732         stackRefMap.add(IntWrapper::create(42), RefCountedAndGarbageCollected::create());
2733         stackRefMap.add(luck, RefCountedAndGarbageCollected::create());
2734
2735         baseLine = ThingWithDestructor::s_liveThingsWithDestructor;
2736         refBaseLine = RefCountedAndGarbageCollected::s_destructorCalls;
2737
2738         // Although the heap maps are on-stack, we can't expect prompt
2739         // finalization of the elements, so when they go out of scope here we
2740         // will not necessarily have called the relevant destructors.
2741     }
2742
2743     // The RefCountedAndGarbageCollected things need an extra GC to discover
2744     // that they are no longer ref counted.
2745     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2746     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2747     EXPECT_EQ(baseLine - 2, ThingWithDestructor::s_liveThingsWithDestructor);
2748     EXPECT_EQ(refBaseLine + 2, RefCountedAndGarbageCollected::s_destructorCalls);
2749
2750     // Now use maps kept alive with persistents. Here we don't expect any
2751     // destructors to be called before there have been GCs.
2752
2753     map->add(IntWrapper::create(42), ThingWithDestructor(1729));
2754     map->add(luck, ThingWithDestructor(8128));
2755     refMap->add(IntWrapper::create(42), RefCountedAndGarbageCollected::create());
2756     refMap->add(luck, RefCountedAndGarbageCollected::create());
2757
2758     baseLine  =  ThingWithDestructor::s_liveThingsWithDestructor;
2759     refBaseLine = RefCountedAndGarbageCollected::s_destructorCalls;
2760
2761     luck.clear();
2762     if (clearMaps) {
2763         map->clear(); // Clear map.
2764         refMap->clear(); // Clear map.
2765     } else {
2766         map.clear(); // Clear Persistent handle, not map.
2767         refMap.clear(); // Clear Persistent handle, not map.
2768         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2769         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2770     }
2771
2772     EXPECT_EQ(baseLine - 2, ThingWithDestructor::s_liveThingsWithDestructor);
2773
2774     // Need a GC to make sure that the RefCountedAndGarbageCollected thing
2775     // noticies it's been decremented to zero.
2776     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2777     EXPECT_EQ(refBaseLine + 2, RefCountedAndGarbageCollected::s_destructorCalls);
2778 }
2779
2780 TEST(HeapTest, HeapMapDestructor)
2781 {
2782     heapMapDestructorHelper(true);
2783     heapMapDestructorHelper(false);
2784 }
2785
2786 typedef HeapHashSet<PairWeakStrong> WeakStrongSet;
2787 typedef HeapHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2788 typedef HeapHashSet<PairStrongWeak> StrongWeakSet;
2789 typedef HeapHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2790 typedef HeapLinkedHashSet<PairWeakStrong> WeakStrongLinkedSet;
2791 typedef HeapLinkedHashSet<PairWeakUnwrapped> WeakUnwrappedLinkedSet;
2792 typedef HeapLinkedHashSet<PairStrongWeak> StrongWeakLinkedSet;
2793 typedef HeapLinkedHashSet<PairUnwrappedWeak> UnwrappedWeakLinkedSet;
2794 typedef HeapHashCountedSet<PairWeakStrong> WeakStrongCountedSet;
2795 typedef HeapHashCountedSet<PairWeakUnwrapped> WeakUnwrappedCountedSet;
2796 typedef HeapHashCountedSet<PairStrongWeak> StrongWeakCountedSet;
2797 typedef HeapHashCountedSet<PairUnwrappedWeak> UnwrappedWeakCountedSet;
2798
2799 template<typename T>
2800 T& iteratorExtractor(WTF::KeyValuePair<T, unsigned>& pair)
2801 {
2802     return pair.key;
2803 }
2804
2805 template<typename T>
2806 T& iteratorExtractor(T& notAPair)
2807 {
2808     return notAPair;
2809 }
2810
2811 template<typename WSSet, typename SWSet, typename WUSet, typename UWSet>
2812 void checkPairSets(
2813     Persistent<WSSet>& weakStrong,
2814     Persistent<SWSet>& strongWeak,
2815     Persistent<WUSet>& weakUnwrapped,
2816     Persistent<UWSet>& unwrappedWeak,
2817     bool ones,
2818     Persistent<IntWrapper>& two)
2819 {
2820     typename WSSet::iterator itWS = weakStrong->begin();
2821     typename SWSet::iterator itSW = strongWeak->begin();
2822     typename WUSet::iterator itWU = weakUnwrapped->begin();
2823     typename UWSet::iterator itUW = unwrappedWeak->begin();
2824
2825     EXPECT_EQ(2u, weakStrong->size());
2826     EXPECT_EQ(2u, strongWeak->size());
2827     EXPECT_EQ(2u, weakUnwrapped->size());
2828     EXPECT_EQ(2u, unwrappedWeak->size());
2829
2830     PairWeakStrong p = iteratorExtractor(*itWS);
2831     PairStrongWeak p2 = iteratorExtractor(*itSW);
2832     PairWeakUnwrapped p3 = iteratorExtractor(*itWU);
2833     PairUnwrappedWeak p4 = iteratorExtractor(*itUW);
2834     if (p.first == two && p.second == two)
2835         ++itWS;
2836     if (p2.first == two && p2.second == two)
2837         ++itSW;
2838     if (p3.first == two && p3.second == 2)
2839         ++itWU;
2840     if (p4.first == 2 && p4.second == two)
2841         ++itUW;
2842     p = iteratorExtractor(*itWS);
2843     p2 = iteratorExtractor(*itSW);
2844     p3 = iteratorExtractor(*itWU);
2845     p4 = iteratorExtractor(*itUW);
2846     IntWrapper* nullWrapper = 0;
2847     if (ones) {
2848         EXPECT_EQ(p.first->value(), 1);
2849         EXPECT_EQ(p2.second->value(), 1);
2850         EXPECT_EQ(p3.first->value(), 1);
2851         EXPECT_EQ(p4.second->value(), 1);
2852     } else {
2853         EXPECT_EQ(p.first, nullWrapper);
2854         EXPECT_EQ(p2.second, nullWrapper);
2855         EXPECT_EQ(p3.first, nullWrapper);
2856         EXPECT_EQ(p4.second, nullWrapper);
2857     }
2858
2859     EXPECT_EQ(p.second->value(), 2);
2860     EXPECT_EQ(p2.first->value(), 2);
2861     EXPECT_EQ(p3.second, 2);
2862     EXPECT_EQ(p4.first, 2);
2863
2864     EXPECT_TRUE(weakStrong->contains(PairWeakStrong(&*two, &*two)));
2865     EXPECT_TRUE(strongWeak->contains(PairStrongWeak(&*two, &*two)));
2866     EXPECT_TRUE(weakUnwrapped->contains(PairWeakUnwrapped(&*two, 2)));
2867     EXPECT_TRUE(unwrappedWeak->contains(PairUnwrappedWeak(2, &*two)));
2868 }
2869
2870 template<typename WSSet, typename SWSet, typename WUSet, typename UWSet>
2871 void weakPairsHelper()
2872 {
2873     IntWrapper::s_destructorCalls = 0;
2874
2875     PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2876
2877     Persistent<WSSet> weakStrong = new WSSet();
2878     Persistent<SWSet> strongWeak = new SWSet();
2879     Persistent<WUSet> weakUnwrapped = new WUSet();
2880     Persistent<UWSet> unwrappedWeak = new UWSet();
2881
2882     Persistent<IntWrapper> two = IntWrapper::create(2);
2883
2884     weakStrong->add(PairWeakStrong(IntWrapper::create(1), &*two));
2885     weakStrong->add(PairWeakStrong(&*two, &*two));
2886     strongWeak->add(PairStrongWeak(&*two, IntWrapper::create(1)));
2887     strongWeak->add(PairStrongWeak(&*two, &*two));
2888     weakUnwrapped->add(PairWeakUnwrapped(IntWrapper::create(1), 2));
2889     weakUnwrapped->add(PairWeakUnwrapped(&*two, 2));
2890     unwrappedWeak->add(PairUnwrappedWeak(2, IntWrapper::create(1)));
2891     unwrappedWeak->add(PairUnwrappedWeak(2, &*two));
2892
2893     checkPairSets<WSSet, SWSet, WUSet, UWSet>(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, true, two);
2894
2895     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2896     checkPairSets<WSSet, SWSet, WUSet, UWSet>(weakStrong, strongWeak, weakUnwrapped, unwrappedWeak, false, two);
2897 }
2898
2899 TEST(HeapTest, HeapWeakPairs)
2900 {
2901     {
2902         typedef HeapHashSet<PairWeakStrong> WeakStrongSet;
2903         typedef HeapHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2904         typedef HeapHashSet<PairStrongWeak> StrongWeakSet;
2905         typedef HeapHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2906         weakPairsHelper<WeakStrongSet, StrongWeakSet, WeakUnwrappedSet, UnwrappedWeakSet>();
2907     }
2908
2909     {
2910         typedef HeapListHashSet<PairWeakStrong> WeakStrongSet;
2911         typedef HeapListHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2912         typedef HeapListHashSet<PairStrongWeak> StrongWeakSet;
2913         typedef HeapListHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2914         weakPairsHelper<WeakStrongSet, StrongWeakSet, WeakUnwrappedSet, UnwrappedWeakSet>();
2915     }
2916
2917     {
2918         typedef HeapLinkedHashSet<PairWeakStrong> WeakStrongSet;
2919         typedef HeapLinkedHashSet<PairWeakUnwrapped> WeakUnwrappedSet;
2920         typedef HeapLinkedHashSet<PairStrongWeak> StrongWeakSet;
2921         typedef HeapLinkedHashSet<PairUnwrappedWeak> UnwrappedWeakSet;
2922         weakPairsHelper<WeakStrongSet, StrongWeakSet, WeakUnwrappedSet, UnwrappedWeakSet>();
2923     }
2924 }
2925
2926 TEST(HeapTest, HeapWeakCollectionTypes)
2927 {
2928     HeapStats initialHeapSize;
2929     IntWrapper::s_destructorCalls = 0;
2930
2931     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakStrong;
2932     typedef HeapHashMap<Member<IntWrapper>, WeakMember<IntWrapper> > StrongWeak;
2933     typedef HeapHashMap<WeakMember<IntWrapper>, WeakMember<IntWrapper> > WeakWeak;
2934     typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
2935     typedef HeapLinkedHashSet<WeakMember<IntWrapper> > WeakOrderedSet;
2936
2937     clearOutOldGarbage(&initialHeapSize);
2938
2939     const int weakStrongIndex = 0;
2940     const int strongWeakIndex = 1;
2941     const int weakWeakIndex = 2;
2942     const int numberOfMapIndices = 3;
2943     const int weakSetIndex = 3;
2944     const int weakOrderedSetIndex = 4;
2945     const int numberOfCollections = 5;
2946
2947     for (int testRun = 0; testRun < 4; testRun++) {
2948         for (int collectionNumber = 0; collectionNumber < numberOfCollections; collectionNumber++) {
2949             bool deleteAfterwards = (testRun == 1);
2950             bool addAfterwards = (testRun == 2);
2951             bool testThatIteratorsMakeStrong = (testRun == 3);
2952
2953             // The test doesn't work for strongWeak with deleting because we lost
2954             // the key from the keepNumbersAlive array, so we can't do the lookup.
2955             if (deleteAfterwards && collectionNumber == strongWeakIndex)
2956                 continue;
2957
2958             unsigned added = addAfterwards ? 100 : 0;
2959
2960             Persistent<WeakStrong> weakStrong = new WeakStrong();
2961             Persistent<StrongWeak> strongWeak = new StrongWeak();
2962             Persistent<WeakWeak> weakWeak = new WeakWeak();
2963
2964             Persistent<WeakSet> weakSet = new WeakSet();
2965             Persistent<WeakOrderedSet> weakOrderedSet = new WeakOrderedSet();
2966
2967             PersistentHeapVector<Member<IntWrapper> > keepNumbersAlive;
2968             for (int i = 0; i < 128; i += 2) {
2969                 IntWrapper* wrapped = IntWrapper::create(i);
2970                 IntWrapper* wrapped2 = IntWrapper::create(i + 1);
2971                 keepNumbersAlive.append(wrapped);
2972                 keepNumbersAlive.append(wrapped2);
2973                 weakStrong->add(wrapped, wrapped2);
2974                 strongWeak->add(wrapped2, wrapped);
2975                 weakWeak->add(wrapped, wrapped2);
2976                 weakSet->add(wrapped);
2977                 weakOrderedSet->add(wrapped);
2978             }
2979
2980             EXPECT_EQ(64u, weakStrong->size());
2981             EXPECT_EQ(64u, strongWeak->size());
2982             EXPECT_EQ(64u, weakWeak->size());
2983             EXPECT_EQ(64u, weakSet->size());
2984             EXPECT_EQ(64u, weakOrderedSet->size());
2985
2986             // Collect garbage. This should change nothing since we are keeping
2987             // alive the IntWrapper objects.
2988             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
2989
2990             EXPECT_EQ(64u, weakStrong->size());
2991             EXPECT_EQ(64u, strongWeak->size());
2992             EXPECT_EQ(64u, weakWeak->size());
2993             EXPECT_EQ(64u, weakSet->size());
2994             EXPECT_EQ(64u, weakOrderedSet->size());
2995
2996             for (int i = 0; i < 128; i += 2) {
2997                 IntWrapper* wrapped = keepNumbersAlive[i];
2998                 IntWrapper* wrapped2 = keepNumbersAlive[i + 1];
2999                 EXPECT_EQ(wrapped2, weakStrong->get(wrapped));
3000                 EXPECT_EQ(wrapped, strongWeak->get(wrapped2));
3001                 EXPECT_EQ(wrapped2, weakWeak->get(wrapped));
3002                 EXPECT_TRUE(weakSet->contains(wrapped));
3003                 EXPECT_TRUE(weakOrderedSet->contains(wrapped));
3004             }
3005
3006             for (int i = 0; i < 128; i += 3)
3007                 keepNumbersAlive[i] = nullptr;
3008
3009             if (collectionNumber != weakStrongIndex)
3010                 weakStrong->clear();
3011             if (collectionNumber != strongWeakIndex)
3012                 strongWeak->clear();
3013             if (collectionNumber != weakWeakIndex)
3014                 weakWeak->clear();
3015             if (collectionNumber != weakSetIndex)
3016                 weakSet->clear();
3017             if (collectionNumber != weakOrderedSetIndex)
3018                 weakOrderedSet->clear();
3019
3020             if (testThatIteratorsMakeStrong) {
3021                 WeakStrong::iterator it1 = weakStrong->begin();
3022                 StrongWeak::iterator it2 = strongWeak->begin();
3023                 WeakWeak::iterator it3 = weakWeak->begin();
3024                 WeakSet::iterator it4 = weakSet->begin();
3025                 WeakOrderedSet::iterator it5 = weakOrderedSet->begin();
3026                 // Collect garbage. This should change nothing since the
3027                 // iterators make the collections strong.
3028                 Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3029                 if (collectionNumber == weakStrongIndex) {
3030                     EXPECT_EQ(64u, weakStrong->size());
3031                     MapIteratorCheck(it1, weakStrong->end(), 64);
3032                 } else if (collectionNumber == strongWeakIndex) {
3033                     EXPECT_EQ(64u, strongWeak->size());
3034                     MapIteratorCheck(it2, strongWeak->end(), 64);
3035                 } else if (collectionNumber == weakWeakIndex) {
3036                     EXPECT_EQ(64u, weakWeak->size());
3037                     MapIteratorCheck(it3, weakWeak->end(), 64);
3038                 } else if (collectionNumber == weakSetIndex) {
3039                     EXPECT_EQ(64u, weakSet->size());
3040                     SetIteratorCheck(it4, weakSet->end(), 64);
3041                 } else if (collectionNumber == weakOrderedSetIndex) {
3042                     EXPECT_EQ(64u, weakOrderedSet->size());
3043                     SetIteratorCheck(it5, weakOrderedSet->end(), 64);
3044                 }
3045             } else {
3046                 // Collect garbage. This causes weak processing to remove
3047                 // things from the collections.
3048                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3049                 unsigned count = 0;
3050                 for (int i = 0; i < 128; i += 2) {
3051                     bool firstAlive = keepNumbersAlive[i];
3052                     bool secondAlive = keepNumbersAlive[i + 1];
3053                     if (firstAlive && (collectionNumber == weakStrongIndex || collectionNumber == strongWeakIndex))
3054                         secondAlive = true;
3055                     if (firstAlive && secondAlive && collectionNumber < numberOfMapIndices) {
3056                         if (collectionNumber == weakStrongIndex) {
3057                             if (deleteAfterwards)
3058                                 EXPECT_EQ(i + 1, weakStrong->take(keepNumbersAlive[i])->value());
3059                         } else if (collectionNumber == strongWeakIndex) {
3060                             if (deleteAfterwards)
3061                                 EXPECT_EQ(i, strongWeak->take(keepNumbersAlive[i + 1])->value());
3062                         } else if (collectionNumber == weakWeakIndex) {
3063                             if (deleteAfterwards)
3064                                 EXPECT_EQ(i + 1, weakWeak->take(keepNumbersAlive[i])->value());
3065                         }
3066                         if (!deleteAfterwards)
3067                             count++;
3068                     } else if (collectionNumber == weakSetIndex && firstAlive) {
3069                         ASSERT_TRUE(weakSet->contains(keepNumbersAlive[i]));
3070                         if (deleteAfterwards)
3071                             weakSet->remove(keepNumbersAlive[i]);
3072                         else
3073                             count++;
3074                     } else if (collectionNumber == weakOrderedSetIndex && firstAlive) {
3075                         ASSERT_TRUE(weakOrderedSet->contains(keepNumbersAlive[i]));
3076                         if (deleteAfterwards)
3077                             weakOrderedSet->remove(keepNumbersAlive[i]);
3078                         else
3079                             count++;
3080                     }
3081                 }
3082                 if (addAfterwards) {
3083                     for (int i = 1000; i < 1100; i++) {
3084                         IntWrapper* wrapped = IntWrapper::create(i);
3085                         keepNumbersAlive.append(wrapped);
3086                         weakStrong->add(wrapped, wrapped);
3087                         strongWeak->add(wrapped, wrapped);
3088                         weakWeak->add(wrapped, wrapped);
3089                         weakSet->add(wrapped);
3090                         weakOrderedSet->add(wrapped);
3091                     }
3092                 }
3093                 if (collectionNumber == weakStrongIndex)
3094                     EXPECT_EQ(count + added, weakStrong->size());
3095                 else if (collectionNumber == strongWeakIndex)
3096                     EXPECT_EQ(count + added, strongWeak->size());
3097                 else if (collectionNumber == weakWeakIndex)
3098                     EXPECT_EQ(count + added, weakWeak->size());
3099                 else if (collectionNumber == weakSetIndex)
3100                     EXPECT_EQ(count + added, weakSet->size());
3101                 else if (collectionNumber == weakOrderedSetIndex)
3102                     EXPECT_EQ(count + added, weakOrderedSet->size());
3103                 WeakStrong::iterator it1 = weakStrong->begin();
3104                 StrongWeak::iterator it2 = strongWeak->begin();
3105                 WeakWeak::iterator it3 = weakWeak->begin();
3106                 WeakSet::iterator it4 = weakSet->begin();
3107                 WeakOrderedSet::iterator it5 = weakOrderedSet->begin();
3108                 MapIteratorCheck(it1, weakStrong->end(), (collectionNumber == weakStrongIndex ? count : 0) + added);
3109                 MapIteratorCheck(it2, strongWeak->end(), (collectionNumber == strongWeakIndex ? count : 0) + added);
3110                 MapIteratorCheck(it3, weakWeak->end(), (collectionNumber == weakWeakIndex ? count : 0) + added);
3111                 SetIteratorCheck(it4, weakSet->end(), (collectionNumber == weakSetIndex ? count : 0) + added);
3112                 SetIteratorCheck(it5, weakOrderedSet->end(), (collectionNumber == weakOrderedSetIndex ? count : 0) + added);
3113             }
3114             for (unsigned i = 0; i < 128 + added; i++)
3115                 keepNumbersAlive[i] = nullptr;
3116             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3117             EXPECT_EQ(0u, weakStrong->size());
3118             EXPECT_EQ(0u, strongWeak->size());
3119             EXPECT_EQ(0u, weakWeak->size());
3120             EXPECT_EQ(0u, weakSet->size());
3121             EXPECT_EQ(0u, weakOrderedSet->size());
3122         }
3123     }
3124 }
3125
3126 TEST(HeapTest, RefCountedGarbageCollected)
3127 {
3128     RefCountedAndGarbageCollected::s_destructorCalls = 0;
3129     {
3130         RefPtr<RefCountedAndGarbageCollected> refPtr3;
3131         {
3132             Persistent<RefCountedAndGarbageCollected> persistent;
3133             {
3134                 RefPtr<RefCountedAndGarbageCollected> refPtr1 = RefCountedAndGarbageCollected::create();
3135                 RefPtr<RefCountedAndGarbageCollected> refPtr2 = RefCountedAndGarbageCollected::create();
3136                 Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3137                 EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3138                 persistent = refPtr1.get();
3139             }
3140             // Reference count is zero for both objects but one of
3141             // them is kept alive by a persistent handle.
3142             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3143             EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
3144             refPtr3 = persistent.get();
3145         }
3146         // The persistent handle is gone but the ref count has been
3147         // increased to 1.
3148         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3149         EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
3150     }
3151     // Both persistent handle is gone and ref count is zero so the
3152     // object can be collected.
3153     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3154     EXPECT_EQ(2, RefCountedAndGarbageCollected::s_destructorCalls);
3155 }
3156
3157 TEST(HeapTest, RefCountedGarbageCollectedWithStackPointers)
3158 {
3159     RefCountedAndGarbageCollected::s_destructorCalls = 0;
3160     RefCountedAndGarbageCollected2::s_destructorCalls = 0;
3161     {
3162         RefCountedAndGarbageCollected* pointer1 = 0;
3163         RefCountedAndGarbageCollected2* pointer2 = 0;
3164         {
3165             RefPtr<RefCountedAndGarbageCollected> object1 = RefCountedAndGarbageCollected::create();
3166             RefPtr<RefCountedAndGarbageCollected2> object2 = RefCountedAndGarbageCollected2::create();
3167             pointer1 = object1.get();
3168             pointer2 = object2.get();
3169             void* objects[2] = { object1.get(), object2.get() };
3170             RefCountedGarbageCollectedVisitor visitor(2, objects);
3171             ThreadState::current()->visitPersistents(&visitor);
3172             EXPECT_TRUE(visitor.validate());
3173
3174             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3175             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3176             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3177         }
3178         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3179         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3180         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3181
3182         // At this point, the reference counts of object1 and object2 are 0.
3183         // Only pointer1 and pointer2 keep references to object1 and object2.
3184         void* objects[] = { 0 };
3185         RefCountedGarbageCollectedVisitor visitor(0, objects);
3186         ThreadState::current()->visitPersistents(&visitor);
3187         EXPECT_TRUE(visitor.validate());
3188
3189         {
3190             RefPtr<RefCountedAndGarbageCollected> object1(pointer1);
3191             RefPtr<RefCountedAndGarbageCollected2> object2(pointer2);
3192             void* objects[2] = { object1.get(), object2.get() };
3193             RefCountedGarbageCollectedVisitor visitor(2, objects);
3194             ThreadState::current()->visitPersistents(&visitor);
3195             EXPECT_TRUE(visitor.validate());
3196
3197             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3198             EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3199             EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3200         }
3201
3202         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3203         EXPECT_EQ(0, RefCountedAndGarbageCollected::s_destructorCalls);
3204         EXPECT_EQ(0, RefCountedAndGarbageCollected2::s_destructorCalls);
3205     }
3206
3207     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3208     EXPECT_EQ(1, RefCountedAndGarbageCollected::s_destructorCalls);
3209     EXPECT_EQ(1, RefCountedAndGarbageCollected2::s_destructorCalls);
3210 }
3211
3212 TEST(HeapTest, WeakMembers)
3213 {
3214     Bar::s_live = 0;
3215     {
3216         Persistent<Bar> h1 = Bar::create();
3217         Persistent<Weak> h4;
3218         Persistent<WithWeakMember> h5;
3219         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3220         ASSERT_EQ(1u, Bar::s_live); // h1 is live.
3221         {
3222             Bar* h2 = Bar::create();
3223             Bar* h3 = Bar::create();
3224             h4 = Weak::create(h2, h3);
3225             h5 = WithWeakMember::create(h2, h3);
3226             Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3227             EXPECT_EQ(5u, Bar::s_live); // The on-stack pointer keeps h3 alive.
3228             EXPECT_TRUE(h4->strongIsThere());
3229             EXPECT_TRUE(h4->weakIsThere());
3230             EXPECT_TRUE(h5->strongIsThere());
3231             EXPECT_TRUE(h5->weakIsThere());
3232         }
3233         // h3 is collected, weak pointers from h4 and h5 don't keep it alive.
3234         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3235         EXPECT_EQ(4u, Bar::s_live);
3236         EXPECT_TRUE(h4->strongIsThere());
3237         EXPECT_FALSE(h4->weakIsThere()); // h3 is gone from weak pointer.
3238         EXPECT_TRUE(h5->strongIsThere());
3239         EXPECT_FALSE(h5->weakIsThere()); // h3 is gone from weak pointer.
3240         h1.release(); // Zero out h1.
3241         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3242         EXPECT_EQ(3u, Bar::s_live); // Only h4, h5 and h2 are left.
3243         EXPECT_TRUE(h4->strongIsThere()); // h2 is still pointed to from h4.
3244         EXPECT_TRUE(h5->strongIsThere()); // h2 is still pointed to from h5.
3245     }
3246     // h4 and h5 have gone out of scope now and they were keeping h2 alive.
3247     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3248     EXPECT_EQ(0u, Bar::s_live); // All gone.
3249 }
3250
3251 TEST(HeapTest, FinalizationObserver)
3252 {
3253     Persistent<FinalizationObserver<Observable> > o;
3254     {
3255         Observable* foo = Observable::create(Bar::create());
3256         // |o| observes |foo|.
3257         o = FinalizationObserver<Observable>::create(foo);
3258     }
3259     // FinalizationObserver doesn't have a strong reference to |foo|. So |foo|
3260     // and its member will be collected.
3261     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3262     EXPECT_EQ(0u, Bar::s_live);
3263     EXPECT_TRUE(o->didCallWillFinalize());
3264
3265     FinalizationObserverWithHashMap::s_didCallWillFinalize = false;
3266     Observable* foo = Observable::create(Bar::create());
3267     FinalizationObserverWithHashMap::ObserverMap& map = FinalizationObserverWithHashMap::observe(*foo);
3268     EXPECT_EQ(1u, map.size());
3269     foo = 0;
3270     // FinalizationObserverWithHashMap doesn't have a strong reference to
3271     // |foo|. So |foo| and its member will be collected.
3272     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3273     EXPECT_EQ(0u, Bar::s_live);
3274     EXPECT_EQ(0u, map.size());
3275     EXPECT_TRUE(FinalizationObserverWithHashMap::s_didCallWillFinalize);
3276 }
3277
3278 TEST(HeapTest, Comparisons)
3279 {
3280     Persistent<Bar> barPersistent = Bar::create();
3281     Persistent<Foo> fooPersistent = Foo::create(barPersistent);
3282     EXPECT_TRUE(barPersistent != fooPersistent);
3283     barPersistent = fooPersistent;
3284     EXPECT_TRUE(barPersistent == fooPersistent);
3285 }
3286
3287 TEST(HeapTest, CheckAndMarkPointer)
3288 {
3289     HeapStats initialHeapStats;
3290     clearOutOldGarbage(&initialHeapStats);
3291
3292     Vector<Address> objectAddresses;
3293     Vector<Address> endAddresses;
3294     Address largeObjectAddress;
3295     Address largeObjectEndAddress;
3296     CountingVisitor visitor;
3297     for (int i = 0; i < 10; i++) {
3298         SimpleObject* object = SimpleObject::create();
3299         Address objectAddress = reinterpret_cast<Address>(object);
3300         objectAddresses.append(objectAddress);
3301         endAddresses.append(objectAddress + sizeof(SimpleObject) - 1);
3302     }
3303     LargeObject* largeObject = LargeObject::create();
3304     largeObjectAddress = reinterpret_cast<Address>(largeObject);
3305     largeObjectEndAddress = largeObjectAddress + sizeof(LargeObject) - 1;
3306
3307     // This is a low-level test where we call checkAndMarkPointer. This method
3308     // causes the object start bitmap to be computed which requires the heap
3309     // to be in a consistent state (e.g. the free allocation area must be put
3310     // into a free list header). However when we call makeConsistentForGC it
3311     // also clears out the freelists so we have to rebuild those before trying
3312     // to allocate anything again. We do this by forcing a GC after doing the
3313     // checkAndMarkPointer tests.
3314     {
3315         TestGCScope scope(ThreadState::HeapPointersOnStack);
3316         EXPECT_TRUE(scope.allThreadsParked()); // Fail the test if we could not park all threads.
3317         Heap::makeConsistentForGC();
3318         for (size_t i = 0; i < objectAddresses.size(); i++) {
3319             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, objectAddresses[i]));
3320             EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, endAddresses[i]));
3321         }
3322         EXPECT_EQ(objectAddresses.size() * 2, visitor.count());
3323         visitor.reset();
3324         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectAddress));
3325         EXPECT_TRUE(Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress));
3326         EXPECT_EQ(2ul, visitor.count());
3327         visitor.reset();
3328     }
3329     // This forces a GC without stack scanning which results in the objects
3330     // being collected. This will also rebuild the above mentioned freelists,
3331     // however we don't rely on that below since we don't have any allocations.
3332     clearOutOldGarbage(&initialHeapStats);
3333     {
3334         TestGCScope scope(ThreadState::HeapPointersOnStack);
3335         EXPECT_TRUE(scope.allThreadsParked());
3336         Heap::makeConsistentForGC();
3337         for (size_t i = 0; i < objectAddresses.size(); i++) {
3338             // We would like to assert that checkAndMarkPointer returned false
3339             // here because the pointers no longer point into a valid object
3340             // (it's been freed by the GCs. But checkAndMarkPointer will return
3341             // true for any pointer that points into a heap page, regardless of
3342             // whether it points at a valid object (this ensures the
3343             // correctness of the page-based on-heap address caches), so we
3344             // can't make that assert.
3345             Heap::checkAndMarkPointer(&visitor, objectAddresses[i]);
3346             Heap::checkAndMarkPointer(&visitor, endAddresses[i]);
3347         }
3348         EXPECT_EQ(0ul, visitor.count());
3349         Heap::checkAndMarkPointer(&visitor, largeObjectAddress);
3350         Heap::checkAndMarkPointer(&visitor, largeObjectEndAddress);
3351         EXPECT_EQ(0ul, visitor.count());
3352     }
3353     // This round of GC is important to make sure that the object start
3354     // bitmap are cleared out and that the free lists are rebuild.
3355     clearOutOldGarbage(&initialHeapStats);
3356 }
3357
3358 TEST(HeapTest, VisitOffHeapCollections)
3359 {
3360     HeapStats initialHeapStats;
3361     clearOutOldGarbage(&initialHeapStats);
3362     IntWrapper::s_destructorCalls = 0;
3363     Persistent<OffHeapContainer> container = OffHeapContainer::create();
3364     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3365     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3366     container = nullptr;
3367     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3368     EXPECT_EQ(OffHeapContainer::deadWrappers, IntWrapper::s_destructorCalls);
3369 }
3370
3371 TEST(HeapTest, PersistentHeapCollectionTypes)
3372 {
3373     HeapStats initialHeapSize;
3374     IntWrapper::s_destructorCalls = 0;
3375
3376     typedef HeapVector<Member<IntWrapper> > Vec;
3377     typedef PersistentHeapVector<Member<IntWrapper> > PVec;
3378     typedef PersistentHeapHashSet<Member<IntWrapper> > PSet;
3379     typedef PersistentHeapListHashSet<Member<IntWrapper> > PListSet;
3380     typedef PersistentHeapLinkedHashSet<Member<IntWrapper> > PLinkedSet;
3381     typedef PersistentHeapHashMap<Member<IntWrapper>, Member<IntWrapper> > PMap;
3382     typedef PersistentHeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > WeakPMap;
3383     typedef PersistentHeapDeque<Member<IntWrapper> > PDeque;
3384
3385     clearOutOldGarbage(&initialHeapSize);
3386     {
3387         PVec pVec;
3388         PDeque pDeque;
3389         PSet pSet;
3390         PListSet pListSet;
3391         PLinkedSet pLinkedSet;
3392         PMap pMap;
3393         WeakPMap wpMap;
3394
3395         IntWrapper* one(IntWrapper::create(1));
3396         IntWrapper* two(IntWrapper::create(2));
3397         IntWrapper* three(IntWrapper::create(3));
3398         IntWrapper* four(IntWrapper::create(4));
3399         IntWrapper* five(IntWrapper::create(5));
3400         IntWrapper* six(IntWrapper::create(6));
3401         IntWrapper* seven(IntWrapper::create(7));
3402         IntWrapper* eight(IntWrapper::create(8));
3403         IntWrapper* nine(IntWrapper::create(9));
3404         Persistent<IntWrapper> ten(IntWrapper::create(10));
3405         IntWrapper* eleven(IntWrapper::create(11));
3406
3407         pVec.append(one);
3408         pVec.append(two);
3409
3410         pDeque.append(seven);
3411         pDeque.append(two);
3412
3413         Vec* vec = new Vec();
3414         vec->swap(pVec);
3415
3416         pVec.append(two);
3417         pVec.append(three);
3418
3419         pSet.add(four);
3420         pListSet.add(eight);
3421         pLinkedSet.add(nine);
3422         pMap.add(five, six);
3423         wpMap.add(ten, eleven);
3424
3425         // Collect |vec| and |one|.
3426         vec = 0;
3427         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3428         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
3429
3430         EXPECT_EQ(2u, pVec.size());
3431         EXPECT_EQ(two, pVec.at(0));
3432         EXPECT_EQ(three, pVec.at(1));
3433
3434         EXPECT_EQ(2u, pDeque.size());
3435         EXPECT_EQ(seven, pDeque.first());
3436         EXPECT_EQ(seven, pDeque.takeFirst());
3437         EXPECT_EQ(two, pDeque.first());
3438
3439         EXPECT_EQ(1u, pDeque.size());
3440
3441         EXPECT_EQ(1u, pSet.size());
3442         EXPECT_TRUE(pSet.contains(four));
3443
3444         EXPECT_EQ(1u, pListSet.size());
3445         EXPECT_TRUE(pListSet.contains(eight));
3446
3447         EXPECT_EQ(1u, pLinkedSet.size());
3448         EXPECT_TRUE(pLinkedSet.contains(nine));
3449
3450         EXPECT_EQ(1u, pMap.size());
3451         EXPECT_EQ(six, pMap.get(five));
3452
3453         EXPECT_EQ(1u, wpMap.size());
3454         EXPECT_EQ(eleven, wpMap.get(ten));
3455         ten.clear();
3456         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3457         EXPECT_EQ(0u, wpMap.size());
3458     }
3459
3460     // Collect previous roots.
3461     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3462     EXPECT_EQ(11, IntWrapper::s_destructorCalls);
3463 }
3464
3465 TEST(HeapTest, CollectionNesting)
3466 {
3467     HeapStats initialStats;
3468     clearOutOldGarbage(&initialStats);
3469     int* key = &IntWrapper::s_destructorCalls;
3470     IntWrapper::s_destructorCalls = 0;
3471     typedef HeapVector<Member<IntWrapper> > IntVector;
3472     typedef HeapDeque<Member<IntWrapper> > IntDeque;
3473     HeapHashMap<void*, IntVector>* map = new HeapHashMap<void*, IntVector>();
3474     HeapHashMap<void*, IntDeque>* map2 = new HeapHashMap<void*, IntDeque>();
3475
3476     map->add(key, IntVector());
3477     map2->add(key, IntDeque());
3478
3479     HeapHashMap<void*, IntVector>::iterator it = map->find(key);
3480     EXPECT_EQ(0u, map->get(key).size());
3481
3482     HeapHashMap<void*, IntDeque>::iterator it2 = map2->find(key);
3483     EXPECT_EQ(0u, map2->get(key).size());
3484
3485     it->value.append(IntWrapper::create(42));
3486     EXPECT_EQ(1u, map->get(key).size());
3487
3488     it2->value.append(IntWrapper::create(42));
3489     EXPECT_EQ(1u, map2->get(key).size());
3490
3491     Persistent<HeapHashMap<void*, IntVector> > keepAlive(map);
3492     Persistent<HeapHashMap<void*, IntDeque> > keepAlive2(map2);
3493
3494     for (int i = 0; i < 100; i++) {
3495         map->add(key + 1 + i, IntVector());
3496         map2->add(key + 1 + i, IntDeque());
3497     }
3498
3499     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3500
3501     EXPECT_EQ(1u, map->get(key).size());
3502     EXPECT_EQ(1u, map2->get(key).size());
3503     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3504
3505     keepAlive = nullptr;
3506     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3507     EXPECT_EQ(1, IntWrapper::s_destructorCalls);
3508 }
3509
3510 TEST(HeapTest, GarbageCollectedMixin)
3511 {
3512     HeapStats initialHeapStats;
3513     clearOutOldGarbage(&initialHeapStats);
3514
3515     Persistent<UseMixin> usemixin = UseMixin::create();
3516     EXPECT_EQ(0, UseMixin::s_traceCount);
3517     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3518     EXPECT_EQ(1, UseMixin::s_traceCount);
3519
3520     Persistent<Mixin> mixin = usemixin;
3521     usemixin = nullptr;
3522     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3523     EXPECT_EQ(2, UseMixin::s_traceCount);
3524
3525     PersistentHeapHashSet<WeakMember<Mixin> > weakMap;
3526     weakMap.add(UseMixin::create());
3527     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3528     EXPECT_EQ(0u, weakMap.size());
3529 }
3530
3531 TEST(HeapTest, CollectionNesting2)
3532 {
3533     HeapStats initialStats;
3534     clearOutOldGarbage(&initialStats);
3535     void* key = &IntWrapper::s_destructorCalls;
3536     IntWrapper::s_destructorCalls = 0;
3537     typedef HeapHashSet<Member<IntWrapper> > IntSet;
3538     HeapHashMap<void*, IntSet>* map = new HeapHashMap<void*, IntSet>();
3539
3540     map->add(key, IntSet());
3541
3542     HeapHashMap<void*, IntSet>::iterator it = map->find(key);
3543     EXPECT_EQ(0u, map->get(key).size());
3544
3545     it->value.add(IntWrapper::create(42));
3546     EXPECT_EQ(1u, map->get(key).size());
3547
3548     Persistent<HeapHashMap<void*, IntSet> > keepAlive(map);
3549     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3550     EXPECT_EQ(1u, map->get(key).size());
3551     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3552 }
3553
3554 TEST(HeapTest, CollectionNesting3)
3555 {
3556     HeapStats initialStats;
3557     clearOutOldGarbage(&initialStats);
3558     IntWrapper::s_destructorCalls = 0;
3559     typedef HeapVector<Member<IntWrapper> > IntVector;
3560     typedef HeapDeque<Member<IntWrapper> > IntDeque;
3561     HeapVector<IntVector>* vector = new HeapVector<IntVector>();
3562     HeapDeque<IntDeque>* deque = new HeapDeque<IntDeque>();
3563
3564     vector->append(IntVector());
3565     deque->append(IntDeque());
3566
3567     HeapVector<IntVector>::iterator it = vector->begin();
3568     HeapDeque<IntDeque>::iterator it2 = deque->begin();
3569     EXPECT_EQ(0u, it->size());
3570     EXPECT_EQ(0u, it2->size());
3571
3572     it->append(IntWrapper::create(42));
3573     it2->append(IntWrapper::create(42));
3574     EXPECT_EQ(1u, it->size());
3575     EXPECT_EQ(1u, it2->size());
3576
3577     Persistent<HeapVector<IntVector> > keepAlive(vector);
3578     Persistent<HeapDeque<IntDeque> > keepAlive2(deque);
3579     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3580     EXPECT_EQ(1u, it->size());
3581     EXPECT_EQ(1u, it2->size());
3582     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3583 }
3584
3585 TEST(HeapTest, EmbeddedInVector)
3586 {
3587     HeapStats initialStats;
3588     clearOutOldGarbage(&initialStats);
3589     SimpleFinalizedObject::s_destructorCalls = 0;
3590     {
3591         PersistentHeapVector<VectorObject, 2> inlineVector;
3592         PersistentHeapVector<VectorObject> outlineVector;
3593         VectorObject i1, i2;
3594         inlineVector.append(i1);
3595         inlineVector.append(i2);
3596
3597         VectorObject o1, o2;
3598         outlineVector.append(o1);
3599         outlineVector.append(o2);
3600
3601         PersistentHeapVector<VectorObjectInheritedTrace> vectorInheritedTrace;
3602         VectorObjectInheritedTrace it1, it2;
3603         vectorInheritedTrace.append(it1);
3604         vectorInheritedTrace.append(it2);
3605
3606         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3607         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
3608
3609         // Since VectorObjectNoTrace has no trace method it will
3610         // not be traced and hence be collected when doing GC.
3611         // We trace items in a collection braced on the item's
3612         // having a trace method. This is determined via the
3613         // NeedsTracing trait in wtf/TypeTraits.h.
3614         PersistentHeapVector<VectorObjectNoTrace> vectorNoTrace;
3615         VectorObjectNoTrace n1, n2;
3616         vectorNoTrace.append(n1);
3617         vectorNoTrace.append(n2);
3618         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3619         EXPECT_EQ(2, SimpleFinalizedObject::s_destructorCalls);
3620     }
3621     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3622     EXPECT_EQ(8, SimpleFinalizedObject::s_destructorCalls);
3623 }
3624
3625 TEST(HeapTest, EmbeddedInDeque)
3626 {
3627     HeapStats initialStats;
3628     clearOutOldGarbage(&initialStats);
3629     SimpleFinalizedObject::s_destructorCalls = 0;
3630     {
3631         PersistentHeapDeque<VectorObject, 2> inlineDeque;
3632         PersistentHeapDeque<VectorObject> outlineDeque;
3633         VectorObject i1, i2;
3634         inlineDeque.append(i1);
3635         inlineDeque.append(i2);
3636
3637         VectorObject o1, o2;
3638         outlineDeque.append(o1);
3639         outlineDeque.append(o2);
3640
3641         PersistentHeapDeque<VectorObjectInheritedTrace> dequeInheritedTrace;
3642         VectorObjectInheritedTrace it1, it2;
3643         dequeInheritedTrace.append(it1);
3644         dequeInheritedTrace.append(it2);
3645
3646         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3647         EXPECT_EQ(0, SimpleFinalizedObject::s_destructorCalls);
3648
3649         // Since VectorObjectNoTrace has no trace method it will
3650         // not be traced and hence be collected when doing GC.
3651         // We trace items in a collection braced on the item's
3652         // having a trace method. This is determined via the
3653         // NeedsTracing trait in wtf/TypeTraits.h.
3654         PersistentHeapDeque<VectorObjectNoTrace> dequeNoTrace;
3655         VectorObjectNoTrace n1, n2;
3656         dequeNoTrace.append(n1);
3657         dequeNoTrace.append(n2);
3658         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3659         EXPECT_EQ(2, SimpleFinalizedObject::s_destructorCalls);
3660     }
3661     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3662     EXPECT_EQ(8, SimpleFinalizedObject::s_destructorCalls);
3663 }
3664
3665 template<typename Set>
3666 void rawPtrInHashHelper()
3667 {
3668     Set set;
3669     set.add(new int(42));
3670     set.add(new int(42));
3671     EXPECT_EQ(2u, set.size());
3672     for (typename Set::iterator it = set.begin(); it != set.end(); ++it) {
3673         EXPECT_EQ(42, **it);
3674         delete *it;
3675     }
3676 }
3677
3678 TEST(HeapTest, RawPtrInHash)
3679 {
3680     rawPtrInHashHelper<HashSet<RawPtr<int> > >();
3681     rawPtrInHashHelper<ListHashSet<RawPtr<int> > >();
3682     rawPtrInHashHelper<LinkedHashSet<RawPtr<int> > >();
3683 }
3684
3685 TEST(HeapTest, HeapTerminatedArray)
3686 {
3687     HeapStats initialHeapSize;
3688     clearOutOldGarbage(&initialHeapSize);
3689     IntWrapper::s_destructorCalls = 0;
3690
3691     HeapTerminatedArray<TerminatedArrayItem>* arr = 0;
3692
3693     const size_t prefixSize = 4;
3694     const size_t suffixSize = 4;
3695
3696     {
3697         HeapTerminatedArrayBuilder<TerminatedArrayItem> builder(arr);
3698         builder.grow(prefixSize);
3699         for (size_t i = 0; i < prefixSize; i++)
3700             builder.append(TerminatedArrayItem(IntWrapper::create(i)));
3701         arr = builder.release();
3702     }
3703
3704     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3705     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3706     EXPECT_EQ(prefixSize, arr->size());
3707     for (size_t i = 0; i < prefixSize; i++)
3708         EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
3709
3710     {
3711         HeapTerminatedArrayBuilder<TerminatedArrayItem> builder(arr);
3712         builder.grow(suffixSize);
3713         for (size_t i = 0; i < suffixSize; i++)
3714             builder.append(TerminatedArrayItem(IntWrapper::create(prefixSize + i)));
3715         arr = builder.release();
3716     }
3717
3718     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3719     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3720     EXPECT_EQ(prefixSize + suffixSize, arr->size());
3721     for (size_t i = 0; i < prefixSize + suffixSize; i++)
3722         EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
3723
3724     {
3725         Persistent<HeapTerminatedArray<TerminatedArrayItem> > persistentArr = arr;
3726         arr = 0;
3727         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3728         arr = persistentArr.get();
3729         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3730         EXPECT_EQ(prefixSize + suffixSize, arr->size());
3731         for (size_t i = 0; i < prefixSize + suffixSize; i++)
3732             EXPECT_EQ(i, static_cast<size_t>(arr->at(i).payload()->value()));
3733     }
3734
3735     arr = 0;
3736     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3737     EXPECT_EQ(8, IntWrapper::s_destructorCalls);
3738 }
3739
3740 TEST(HeapTest, HeapLinkedStack)
3741 {
3742     HeapStats initialHeapSize;
3743     clearOutOldGarbage(&initialHeapSize);
3744     IntWrapper::s_destructorCalls = 0;
3745
3746     HeapLinkedStack<TerminatedArrayItem>* stack = new HeapLinkedStack<TerminatedArrayItem>();
3747
3748     const size_t stackSize = 10;
3749
3750     for (size_t i = 0; i < stackSize; i++)
3751         stack->push(TerminatedArrayItem(IntWrapper::create(i)));
3752
3753     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3754     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3755     EXPECT_EQ(stackSize, stack->size());
3756     while (!stack->isEmpty()) {
3757         EXPECT_EQ(stack->size() - 1, static_cast<size_t>(stack->peek().payload()->value()));
3758         stack->pop();
3759     }
3760
3761     Persistent<HeapLinkedStack<TerminatedArrayItem> > pStack = stack;
3762
3763     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3764     EXPECT_EQ(stackSize, static_cast<size_t>(IntWrapper::s_destructorCalls));
3765     EXPECT_EQ(0u, pStack->size());
3766 }
3767
3768 TEST(HeapTest, AllocationDuringFinalization)
3769 {
3770     HeapStats initialHeapSize;
3771     clearOutOldGarbage(&initialHeapSize);
3772     IntWrapper::s_destructorCalls = 0;
3773     OneKiloByteObject::s_destructorCalls = 0;
3774
3775     Persistent<IntWrapper> wrapper;
3776     new FinalizationAllocator(&wrapper);
3777
3778     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3779     EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3780     // Check that the wrapper allocated during finalization is not
3781     // swept away and zapped later in the same sweeping phase.
3782     EXPECT_EQ(42, wrapper->value());
3783
3784     wrapper.clear();
3785     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3786     EXPECT_EQ(10, IntWrapper::s_destructorCalls);
3787     EXPECT_EQ(512, OneKiloByteObject::s_destructorCalls);
3788 }
3789
3790 class SimpleClassWithDestructor {
3791 public:
3792     SimpleClassWithDestructor() { }
3793     ~SimpleClassWithDestructor()
3794     {
3795         s_wasDestructed = true;
3796     }
3797     static bool s_wasDestructed;
3798 };
3799
3800 bool SimpleClassWithDestructor::s_wasDestructed;
3801
3802 class RefCountedWithDestructor : public RefCounted<RefCountedWithDestructor> {
3803 public:
3804     RefCountedWithDestructor() { }
3805     ~RefCountedWithDestructor()
3806     {
3807         s_wasDestructed = true;
3808     }
3809     static bool s_wasDestructed;
3810 };
3811
3812 bool RefCountedWithDestructor::s_wasDestructed;
3813
3814 template<typename Set>
3815 void destructorsCalledOnGC(bool addLots)
3816 {
3817     RefCountedWithDestructor::s_wasDestructed = false;
3818     {
3819         Set set;
3820         RefCountedWithDestructor* hasDestructor = new RefCountedWithDestructor();
3821         set.add(adoptRef(hasDestructor));
3822         EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3823
3824         if (addLots) {
3825             for (int i = 0; i < 1000; i++) {
3826                 set.add(adoptRef(new RefCountedWithDestructor()));
3827             }
3828         }
3829
3830         EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3831         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
3832         EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3833     }
3834     // The destructors of the sets don't call the destructors of the elements
3835     // in the heap sets. You have to actually remove the elments, call clear()
3836     // or have a GC to get the destructors called.
3837     EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3838     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3839     EXPECT_TRUE(RefCountedWithDestructor::s_wasDestructed);
3840 }
3841
3842 template<typename Set>
3843 void destructorsCalledOnClear(bool addLots)
3844 {
3845     RefCountedWithDestructor::s_wasDestructed = false;
3846     Set set;
3847     RefCountedWithDestructor* hasDestructor = new RefCountedWithDestructor();
3848     set.add(adoptRef(hasDestructor));
3849     EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3850
3851     if (addLots) {
3852         for (int i = 0; i < 1000; i++) {
3853             set.add(adoptRef(new RefCountedWithDestructor()));
3854         }
3855     }
3856
3857     EXPECT_FALSE(RefCountedWithDestructor::s_wasDestructed);
3858     set.clear();
3859     EXPECT_TRUE(RefCountedWithDestructor::s_wasDestructed);
3860 }
3861
3862 TEST(HeapTest, DestructorsCalled)
3863 {
3864     HeapHashMap<SimpleClassWithDestructor*, OwnPtr<SimpleClassWithDestructor> > map;
3865     SimpleClassWithDestructor* hasDestructor = new SimpleClassWithDestructor();
3866     map.add(hasDestructor, adoptPtr(hasDestructor));
3867     SimpleClassWithDestructor::s_wasDestructed = false;
3868     map.clear();
3869     EXPECT_TRUE(SimpleClassWithDestructor::s_wasDestructed);
3870
3871     destructorsCalledOnClear<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3872     destructorsCalledOnClear<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3873     destructorsCalledOnClear<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3874     destructorsCalledOnClear<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3875     destructorsCalledOnClear<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3876     destructorsCalledOnClear<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3877
3878     destructorsCalledOnGC<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3879     destructorsCalledOnGC<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3880     destructorsCalledOnGC<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(false);
3881     destructorsCalledOnGC<HeapHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3882     destructorsCalledOnGC<HeapListHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3883     destructorsCalledOnGC<HeapLinkedHashSet<RefPtr<RefCountedWithDestructor> > >(true);
3884 }
3885
3886 class MixinA : public GarbageCollectedMixin {
3887 public:
3888     MixinA() : m_obj(IntWrapper::create(100)) { }
3889     virtual void trace(Visitor* visitor)
3890     {
3891         visitor->trace(m_obj);
3892     }
3893     Member<IntWrapper> m_obj;
3894 };
3895
3896 class MixinB : public GarbageCollectedMixin {
3897 public:
3898     MixinB() : m_obj(IntWrapper::create(101)) { }
3899     virtual void trace(Visitor* visitor)
3900     {
3901         visitor->trace(m_obj);
3902     }
3903     Member<IntWrapper> m_obj;
3904 };
3905
3906 class MultipleMixins : public GarbageCollected<MultipleMixins>, public MixinA, public MixinB {
3907     USING_GARBAGE_COLLECTED_MIXIN(MultipleMixins);
3908 public:
3909     MultipleMixins() : m_obj(IntWrapper::create(102)) { }
3910     virtual void trace(Visitor* visitor)
3911     {
3912         visitor->trace(m_obj);
3913         MixinA::trace(visitor);
3914         MixinB::trace(visitor);
3915     }
3916     Member<IntWrapper> m_obj;
3917 };
3918
3919 static const bool s_isMixinTrue = IsGarbageCollectedMixin<MultipleMixins>::value;
3920 static const bool s_isMixinFalse = IsGarbageCollectedMixin<IntWrapper>::value;
3921
3922 TEST(HeapTest, MultipleMixins)
3923 {
3924     EXPECT_TRUE(s_isMixinTrue);
3925     EXPECT_FALSE(s_isMixinFalse);
3926
3927     HeapStats initialHeapSize;
3928     clearOutOldGarbage(&initialHeapSize);
3929     IntWrapper::s_destructorCalls = 0;
3930     MultipleMixins* obj = new MultipleMixins();
3931     {
3932         Persistent<MixinA> a = obj;
3933         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3934         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3935     }
3936     {
3937         Persistent<MixinB> b = obj;
3938         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3939         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
3940     }
3941     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
3942     EXPECT_EQ(3, IntWrapper::s_destructorCalls);
3943 }
3944
3945 class GCParkingThreadTester {
3946 public:
3947     static void test()
3948     {
3949         createThread(&sleeperMainFunc, 0, "SleepingThread");
3950
3951         // Wait for the sleeper to run.
3952         while (!s_sleeperRunning) {
3953             yield();
3954         }
3955
3956         {
3957             // Expect the first attempt to park the sleeping thread to fail
3958             TestGCScope scope(ThreadState::NoHeapPointersOnStack);
3959             EXPECT_FALSE(scope.allThreadsParked());
3960         }
3961
3962         s_sleeperDone = true;
3963
3964         // Wait for the sleeper to finish.
3965         while (s_sleeperRunning) {
3966             // We enter the safepoint here since the sleeper thread will detach
3967             // causing it to GC.
3968             ThreadState::current()->safePoint(ThreadState::NoHeapPointersOnStack);
3969             yield();
3970         }
3971         {
3972             // Since the sleeper thread has detached this is the only thread.
3973             TestGCScope scope(ThreadState::NoHeapPointersOnStack);
3974             EXPECT_TRUE(scope.allThreadsParked());
3975         }
3976     }
3977
3978 private:
3979     static void sleeperMainFunc(void* data)
3980     {
3981         ThreadState::attach();
3982         s_sleeperRunning = true;
3983
3984         // Simulate a long running op that is not entering a safepoint.
3985         while (!s_sleeperDone) {
3986             yield();
3987         }
3988
3989         ThreadState::detach();
3990         s_sleeperRunning = false;
3991     }
3992
3993     static volatile bool s_sleeperRunning;
3994     static volatile bool s_sleeperDone;
3995 };
3996
3997 volatile bool GCParkingThreadTester::s_sleeperRunning = false;
3998 volatile bool GCParkingThreadTester::s_sleeperDone = false;
3999
4000 TEST(HeapTest, GCParkingTimeout)
4001 {
4002     GCParkingThreadTester::test();
4003 }
4004
4005 TEST(HeapTest, NeedsAdjustAndMark)
4006 {
4007     // class Mixin : public GarbageCollectedMixin {};
4008     EXPECT_TRUE(NeedsAdjustAndMark<Mixin>::value);
4009     EXPECT_TRUE(NeedsAdjustAndMark<const Mixin>::value);
4010
4011     // class SimpleObject : public GarbageCollected<SimpleObject> {};
4012     EXPECT_FALSE(NeedsAdjustAndMark<SimpleObject>::value);
4013     EXPECT_FALSE(NeedsAdjustAndMark<const SimpleObject>::value);
4014
4015     // class UseMixin : public SimpleObject, public Mixin {};
4016     EXPECT_FALSE(NeedsAdjustAndMark<UseMixin>::value);
4017     EXPECT_FALSE(NeedsAdjustAndMark<const UseMixin>::value);
4018 }
4019
4020 template<typename Set>
4021 void setWithCustomWeaknessHandling()
4022 {
4023     typedef typename Set::iterator Iterator;
4024     Persistent<IntWrapper> livingInt(IntWrapper::create(42));
4025     Persistent<Set> set1(new Set());
4026     {
4027         Set set2;
4028         Set* set3 = new Set();
4029         set2.add(PairWithWeakHandling(IntWrapper::create(0), IntWrapper::create(1)));
4030         set3->add(PairWithWeakHandling(IntWrapper::create(2), IntWrapper::create(3)));
4031         set1->add(PairWithWeakHandling(IntWrapper::create(4), IntWrapper::create(5)));
4032         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
4033         // The first set is pointed to from a persistent, so it's referenced, but
4034         // the weak processing may have taken place.
4035         if (set1->size()) {
4036             Iterator i1 = set1->begin();
4037             EXPECT_EQ(4, i1->first->value());
4038             EXPECT_EQ(5, i1->second->value());
4039         }
4040         // The second set is on-stack, so its backing store must be referenced from
4041         // the stack. That makes the weak references strong.
4042         Iterator i2 = set2.begin();
4043         EXPECT_EQ(0, i2->first->value());
4044         EXPECT_EQ(1, i2->second->value());
4045         // The third set is pointed to from the stack, so it's referenced, but the
4046         // weak processing may have taken place.
4047         if (set3->size()) {
4048             Iterator i3 = set3->begin();
4049             EXPECT_EQ(2, i3->first->value());
4050             EXPECT_EQ(3, i3->second->value());
4051         }
4052     }
4053     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4054     EXPECT_EQ(0u, set1->size());
4055     set1->add(PairWithWeakHandling(IntWrapper::create(103), livingInt));
4056     set1->add(PairWithWeakHandling(livingInt, IntWrapper::create(103))); // This one gets zapped at GC time because nothing holds the 103 alive.
4057     set1->add(PairWithWeakHandling(IntWrapper::create(103), IntWrapper::create(103))); // This one gets zapped too.
4058     set1->add(PairWithWeakHandling(livingInt, livingInt));
4059     set1->add(PairWithWeakHandling(livingInt, livingInt)); // This one is identical to the previous and doesn't add anything.
4060     EXPECT_EQ(4u, set1->size());
4061     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4062     EXPECT_EQ(2u, set1->size());
4063     Iterator i1 = set1->begin();
4064     EXPECT_TRUE(i1->first->value() == 103 || i1->first == livingInt);
4065     EXPECT_EQ(livingInt, i1->second);
4066     ++i1;
4067     EXPECT_TRUE(i1->first->value() == 103 || i1->first == livingInt);
4068     EXPECT_EQ(livingInt, i1->second);
4069 }
4070
4071 TEST(HeapTest, SetWithCustomWeaknessHandling)
4072 {
4073     setWithCustomWeaknessHandling<HeapHashSet<PairWithWeakHandling> >();
4074     setWithCustomWeaknessHandling<HeapLinkedHashSet<PairWithWeakHandling> >();
4075 }
4076
4077 TEST(HeapTest, MapWithCustomWeaknessHandling)
4078 {
4079     typedef HeapHashMap<PairWithWeakHandling, RefPtr<OffHeapInt> > Map;
4080     typedef Map::iterator Iterator;
4081     HeapStats initialHeapSize;
4082     clearOutOldGarbage(&initialHeapSize);
4083     OffHeapInt::s_destructorCalls = 0;
4084
4085     Persistent<Map> map1(new Map());
4086     Persistent<IntWrapper> livingInt(IntWrapper::create(42));
4087     {
4088         Map map2;
4089         Map* map3 = new Map();
4090         map2.add(PairWithWeakHandling(IntWrapper::create(0), IntWrapper::create(1)), OffHeapInt::create(1001));
4091         map3->add(PairWithWeakHandling(IntWrapper::create(2), IntWrapper::create(3)), OffHeapInt::create(1002));
4092         map1->add(PairWithWeakHandling(IntWrapper::create(4), IntWrapper::create(5)), OffHeapInt::create(1003));
4093         EXPECT_EQ(0, OffHeapInt::s_destructorCalls);
4094
4095         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
4096         // The first map2 is pointed to from a persistent, so it's referenced, but
4097         // the weak processing may have taken place.
4098         if (map1->size()) {
4099             Iterator i1 = map1->begin();
4100             EXPECT_EQ(4, i1->key.first->value());
4101             EXPECT_EQ(5, i1->key.second->value());
4102             EXPECT_EQ(1003, i1->value->value());
4103         }
4104         // The second map2 is on-stack, so its backing store must be referenced from
4105         // the stack. That makes the weak references strong.
4106         Iterator i2 = map2.begin();
4107         EXPECT_EQ(0, i2->key.first->value());
4108         EXPECT_EQ(1, i2->key.second->value());
4109         EXPECT_EQ(1001, i2->value->value());
4110         // The third map2 is pointed to from the stack, so it's referenced, but the
4111         // weak processing may have taken place.
4112         if (map3->size()) {
4113             Iterator i3 = map3->begin();
4114             EXPECT_EQ(2, i3->key.first->value());
4115             EXPECT_EQ(3, i3->key.second->value());
4116             EXPECT_EQ(1002, i3->value->value());
4117         }
4118     }
4119     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4120
4121     EXPECT_EQ(0u, map1->size());
4122     EXPECT_EQ(3, OffHeapInt::s_destructorCalls);
4123
4124     OffHeapInt::s_destructorCalls = 0;
4125
4126     map1->add(PairWithWeakHandling(IntWrapper::create(103), livingInt), OffHeapInt::create(2000));
4127     map1->add(PairWithWeakHandling(livingInt, IntWrapper::create(103)), OffHeapInt::create(2001)); // This one gets zapped at GC time because nothing holds the 103 alive.
4128     map1->add(PairWithWeakHandling(IntWrapper::create(103), IntWrapper::create(103)), OffHeapInt::create(2002)); // This one gets zapped too.
4129     RefPtr<OffHeapInt> dupeInt(OffHeapInt::create(2003));
4130     map1->add(PairWithWeakHandling(livingInt, livingInt), dupeInt);
4131     map1->add(PairWithWeakHandling(livingInt, livingInt), dupeInt); // This one is identical to the previous and doesn't add anything.
4132     dupeInt.clear();
4133
4134     EXPECT_EQ(0, OffHeapInt::s_destructorCalls);
4135     EXPECT_EQ(4u, map1->size());
4136     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4137     EXPECT_EQ(2, OffHeapInt::s_destructorCalls);
4138     EXPECT_EQ(2u, map1->size());
4139     Iterator i1 = map1->begin();
4140     EXPECT_TRUE(i1->key.first->value() == 103 || i1->key.first == livingInt);
4141     EXPECT_EQ(livingInt, i1->key.second);
4142     ++i1;
4143     EXPECT_TRUE(i1->key.first->value() == 103 || i1->key.first == livingInt);
4144     EXPECT_EQ(livingInt, i1->key.second);
4145 }
4146
4147 TEST(HeapTest, MapWithCustomWeaknessHandling2)
4148 {
4149     typedef HeapHashMap<RefPtr<OffHeapInt>, PairWithWeakHandling> Map;
4150     typedef Map::iterator Iterator;
4151     HeapStats initialHeapSize;
4152     clearOutOldGarbage(&initialHeapSize);
4153     OffHeapInt::s_destructorCalls = 0;
4154
4155     Persistent<Map> map1(new Map());
4156     Persistent<IntWrapper> livingInt(IntWrapper::create(42));
4157
4158     {
4159         Map map2;
4160         Map* map3 = new Map();
4161         map2.add(OffHeapInt::create(1001), PairWithWeakHandling(IntWrapper::create(0), IntWrapper::create(1)));
4162         map3->add(OffHeapInt::create(1002), PairWithWeakHandling(IntWrapper::create(2), IntWrapper::create(3)));
4163         map1->add(OffHeapInt::create(1003), PairWithWeakHandling(IntWrapper::create(4), IntWrapper::create(5)));
4164         EXPECT_EQ(0, OffHeapInt::s_destructorCalls);
4165
4166         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
4167         // The first map2 is pointed to from a persistent, so it's referenced, but
4168         // the weak processing may have taken place.
4169         if (map1->size()) {
4170             Iterator i1 = map1->begin();
4171             EXPECT_EQ(4, i1->value.first->value());
4172             EXPECT_EQ(5, i1->value.second->value());
4173             EXPECT_EQ(1003, i1->key->value());
4174         }
4175         // The second map2 is on-stack, so its backing store must be referenced from
4176         // the stack. That makes the weak references strong.
4177         Iterator i2 = map2.begin();
4178         EXPECT_EQ(0, i2->value.first->value());
4179         EXPECT_EQ(1, i2->value.second->value());
4180         EXPECT_EQ(1001, i2->key->value());
4181         // The third map2 is pointed to from the stack, so it's referenced, but the
4182         // weak processing may have taken place.
4183         if (map3->size()) {
4184             Iterator i3 = map3->begin();
4185             EXPECT_EQ(2, i3->value.first->value());
4186             EXPECT_EQ(3, i3->value.second->value());
4187             EXPECT_EQ(1002, i3->key->value());
4188         }
4189     }
4190     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4191
4192     EXPECT_EQ(0u, map1->size());
4193     EXPECT_EQ(3, OffHeapInt::s_destructorCalls);
4194
4195     OffHeapInt::s_destructorCalls = 0;
4196
4197     map1->add(OffHeapInt::create(2000), PairWithWeakHandling(IntWrapper::create(103), livingInt));
4198     map1->add(OffHeapInt::create(2001), PairWithWeakHandling(livingInt, IntWrapper::create(103))); // This one gets zapped at GC time because nothing holds the 103 alive.
4199     map1->add(OffHeapInt::create(2002), PairWithWeakHandling(IntWrapper::create(103), IntWrapper::create(103))); // This one gets zapped too.
4200     RefPtr<OffHeapInt> dupeInt(OffHeapInt::create(2003));
4201     map1->add(dupeInt, PairWithWeakHandling(livingInt, livingInt));
4202     map1->add(dupeInt, PairWithWeakHandling(livingInt, livingInt)); // This one is identical to the previous and doesn't add anything.
4203     dupeInt.clear();
4204
4205     EXPECT_EQ(0, OffHeapInt::s_destructorCalls);
4206     EXPECT_EQ(4u, map1->size());
4207     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4208     EXPECT_EQ(2, OffHeapInt::s_destructorCalls);
4209     EXPECT_EQ(2u, map1->size());
4210     Iterator i1 = map1->begin();
4211     EXPECT_TRUE(i1->value.first->value() == 103 || i1->value.first == livingInt);
4212     EXPECT_EQ(livingInt, i1->value.second);
4213     ++i1;
4214     EXPECT_TRUE(i1->value.first->value() == 103 || i1->value.first == livingInt);
4215     EXPECT_EQ(livingInt, i1->value.second);
4216 }
4217
4218 static void addElementsToWeakMap(HeapHashMap<int, WeakMember<IntWrapper> >* map)
4219 {
4220     // Key cannot be zero in hashmap.
4221     for (int i = 1; i < 11; i++)
4222         map->add(i, IntWrapper::create(i));
4223 }
4224
4225 // crbug.com/402426
4226 // If it doesn't assert a concurrent modification to the map, then it's passing.
4227 TEST(HeapTest, RegressNullIsStrongified)
4228 {
4229     Persistent<HeapHashMap<int, WeakMember<IntWrapper> > > map = new HeapHashMap<int, WeakMember<IntWrapper> >();
4230     addElementsToWeakMap(map);
4231     HeapHashMap<int, WeakMember<IntWrapper> >::AddResult result = map->add(800, nullptr);
4232     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
4233     result.storedValue->value = IntWrapper::create(42);
4234 }
4235
4236 TEST(HeapTest, Bind)
4237 {
4238     Closure closure = bind(&Bar::trace, Bar::create(), static_cast<Visitor*>(0));
4239     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4240     // The closure should have a persistent handle to the Bar.
4241     EXPECT_EQ(1u, Bar::s_live);
4242
4243     Closure closure2 = bind(&Bar::trace, RawPtr<Bar>(Bar::create()), static_cast<Visitor*>(0));
4244     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4245     // The closure should have a persistent handle to the Bar.
4246     EXPECT_EQ(2u, Bar::s_live);
4247     // RawPtr<OffHeapInt> should not make Persistent.
4248     Closure closure3 = bind(&OffHeapInt::voidFunction, RawPtr<OffHeapInt>(OffHeapInt::create(1).get()));
4249
4250     UseMixin::s_traceCount = 0;
4251     Mixin* mixin = UseMixin::create();
4252     Closure mixinClosure = bind(&Mixin::trace, mixin, static_cast<Visitor*>(0));
4253     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4254     // The closure should have a persistent handle to the mixin.
4255     EXPECT_EQ(1, UseMixin::s_traceCount);
4256 }
4257
4258 typedef HeapHashSet<WeakMember<IntWrapper> > WeakSet;
4259
4260 // These special traits will remove a set from a map when the set is empty.
4261 struct EmptyClearingHashSetTraits : HashTraits<WeakSet> {
4262     static const WTF::WeakHandlingFlag weakHandlingFlag = WTF::WeakHandlingInCollections;
4263     static bool traceInCollection(Visitor* visitor, WeakSet& set, WTF::ShouldWeakPointersBeMarkedStrongly strongify)
4264     {
4265         bool liveEntriesFound = false;
4266         WeakSet::iterator end = set.end();
4267         for (WeakSet::iterator it = set.begin(); it != end; ++it) {
4268             if (visitor->isAlive(*it)) {
4269                 liveEntriesFound = true;
4270                 break;
4271             }
4272         }
4273         // If there are live entries in the set then the set cannot be removed
4274         // from the map it is contained in, and we need to mark it (and its
4275         // backing) live. We just trace normally, which will invoke the normal
4276         // weak handling for any entries that are not live.
4277         if (liveEntriesFound)
4278             set.trace(visitor);
4279         return !liveEntriesFound;
4280     }
4281 };
4282
4283 // This is an example to show how you can remove entries from a T->WeakSet map
4284 // when the weak sets become empty. For this example we are using a type that
4285 // is given to use (HeapHashSet) rather than a type of our own. This means:
4286 // 1) We can't just override the HashTrait for the type since this would affect
4287 //    all collections that use this kind of weak set. Instead we have our own
4288 //    traits and use a map with custom traits for the value type. These traits
4289 //    are the 5th template parameter, so we have to supply default values for
4290 //    the 3rd and 4th template parameters
4291 // 2) We can't just inherit from WeakHandlingHashTraits, since that trait
4292 //    assumes we can add methods to the type, but we can't add methods to
4293 //    HeapHashSet.
4294 TEST(HeapTest, RemoveEmptySets)
4295 {
4296     HeapStats initialHeapSize;
4297     clearOutOldGarbage(&initialHeapSize);
4298     OffHeapInt::s_destructorCalls = 0;
4299
4300     Persistent<IntWrapper> livingInt(IntWrapper::create(42));
4301
4302     typedef RefPtr<OffHeapInt> Key;
4303     typedef HeapHashMap<Key, WeakSet, WTF::DefaultHash<Key>::Hash, HashTraits<Key>, EmptyClearingHashSetTraits> Map;
4304     Persistent<Map> map(new Map());
4305     map->add(OffHeapInt::create(1), WeakSet());
4306     {
4307         WeakSet& set = map->begin()->value;
4308         set.add(IntWrapper::create(103)); // Weak set can't hold this long.
4309         set.add(livingInt); // This prevents the set from being emptied.
4310         EXPECT_EQ(2u, set.size());
4311     }
4312
4313     // The set we add here is empty, so the entry will be removed from the map
4314     // at the next GC.
4315     map->add(OffHeapInt::create(2), WeakSet());
4316     EXPECT_EQ(2u, map->size());
4317
4318     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4319     EXPECT_EQ(1u, map->size()); // The one with key 2 was removed.
4320     EXPECT_EQ(1, OffHeapInt::s_destructorCalls);
4321     {
4322         WeakSet& set = map->begin()->value;
4323         EXPECT_EQ(1u, set.size());
4324     }
4325
4326     livingInt.clear(); // The weak set can no longer keep the '42' alive now.
4327     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4328     EXPECT_EQ(0u, map->size());
4329 }
4330
4331 TEST(HeapTest, EphemeronsInEphemerons)
4332 {
4333     typedef HeapHashMap<WeakMember<IntWrapper>, Member<IntWrapper> > InnerMap;
4334     typedef HeapHashMap<WeakMember<IntWrapper>, InnerMap> OuterMap;
4335
4336     for (int keepOuterAlive = 0; keepOuterAlive <= 1; keepOuterAlive++) {
4337         for (int keepInnerAlive = 0; keepInnerAlive <=1; keepInnerAlive++) {
4338             Persistent<OuterMap> outer = new OuterMap();
4339             Persistent<IntWrapper> one = IntWrapper::create(1);
4340             Persistent<IntWrapper> two = IntWrapper::create(2);
4341             outer->add(one, InnerMap());
4342             outer->begin()->value.add(two, IntWrapper::create(3));
4343             EXPECT_EQ(1u, outer->get(one).size());
4344             if (!keepOuterAlive)
4345                 one.clear();
4346             if (!keepInnerAlive)
4347                 two.clear();
4348             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4349             if (keepOuterAlive) {
4350                 const InnerMap& inner = outer->get(one);
4351                 if (keepInnerAlive) {
4352                     EXPECT_EQ(1u, inner.size());
4353                     IntWrapper* three = inner.get(two);
4354                     EXPECT_EQ(3, three->value());
4355                 } else {
4356                     EXPECT_EQ(0u, inner.size());
4357                 }
4358             } else {
4359                 EXPECT_EQ(0u, outer->size());
4360             }
4361             outer->clear();
4362             Persistent<IntWrapper> deep = IntWrapper::create(42);
4363             Persistent<IntWrapper> home = IntWrapper::create(103);
4364             Persistent<IntWrapper> composite = IntWrapper::create(91);
4365             Persistent<HeapVector<Member<IntWrapper> > > keepAlive = new HeapVector<Member<IntWrapper> >();
4366             for (int i = 0; i < 10000; i++) {
4367                 IntWrapper* value = IntWrapper::create(i);
4368                 keepAlive->append(value);
4369                 OuterMap::AddResult newEntry = outer->add(value, InnerMap());
4370                 newEntry.storedValue->value.add(deep, home);
4371                 newEntry.storedValue->value.add(composite, home);
4372             }
4373             composite.clear();
4374             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4375             EXPECT_EQ(10000u, outer->size());
4376             for (int i = 0; i < 10000; i++) {
4377                 IntWrapper* value = keepAlive->at(i);
4378                 EXPECT_EQ(1u, outer->get(value).size()); // Other one was deleted by weak handling.
4379                 if (i & 1)
4380                     keepAlive->at(i) = nullptr;
4381             }
4382             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4383             EXPECT_EQ(5000u, outer->size());
4384         }
4385     }
4386 }
4387
4388 class EphemeronWrapper : public GarbageCollected<EphemeronWrapper> {
4389 public:
4390     void trace(Visitor* visitor)
4391     {
4392         visitor->trace(m_map);
4393     }
4394
4395     typedef HeapHashMap<WeakMember<IntWrapper>, Member<EphemeronWrapper> > Map;
4396     Map& map() { return m_map; }
4397
4398 private:
4399     Map m_map;
4400 };
4401
4402 TEST(HeapTest, EphemeronsPointToEphemerons)
4403 {
4404     Persistent<IntWrapper> key = IntWrapper::create(42);
4405     Persistent<IntWrapper> key2 = IntWrapper::create(103);
4406
4407     Persistent<EphemeronWrapper> chain;
4408     for (int i = 0; i < 100; i++) {
4409         EphemeronWrapper* oldHead = chain;
4410         chain = new EphemeronWrapper();
4411         if (i == 50)
4412             chain->map().add(key2, oldHead);
4413         else
4414             chain->map().add(key, oldHead);
4415         chain->map().add(IntWrapper::create(103), new EphemeronWrapper());
4416     }
4417
4418     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4419
4420     EphemeronWrapper* wrapper = chain;
4421     for (int i = 0; i< 100; i++) {
4422         EXPECT_EQ(1u, wrapper->map().size());
4423         if (i == 49)
4424             wrapper = wrapper->map().get(key2);
4425         else
4426             wrapper = wrapper->map().get(key);
4427     }
4428     EXPECT_EQ(nullptr, wrapper);
4429
4430     key2.clear();
4431     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4432
4433     wrapper = chain;
4434     for (int i = 0; i < 50; i++) {
4435         EXPECT_EQ(i == 49 ? 0u : 1u, wrapper->map().size());
4436         wrapper = wrapper->map().get(key);
4437     }
4438     EXPECT_EQ(nullptr, wrapper);
4439
4440     key.clear();
4441     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4442     EXPECT_EQ(0u, chain->map().size());
4443 }
4444
4445 TEST(HeapTest, Ephemeron)
4446 {
4447     typedef HeapHashMap<WeakMember<IntWrapper>, PairWithWeakHandling>  WeakPairMap;
4448     typedef HeapHashMap<PairWithWeakHandling, WeakMember<IntWrapper> >  PairWeakMap;
4449     typedef HeapHashSet<WeakMember<IntWrapper> > Set;
4450
4451     Persistent<WeakPairMap> weakPairMap = new WeakPairMap();
4452     Persistent<WeakPairMap> weakPairMap2 = new WeakPairMap();
4453     Persistent<WeakPairMap> weakPairMap3 = new WeakPairMap();
4454     Persistent<WeakPairMap> weakPairMap4 = new WeakPairMap();
4455
4456     Persistent<PairWeakMap> pairWeakMap = new PairWeakMap();
4457     Persistent<PairWeakMap> pairWeakMap2 = new PairWeakMap();
4458
4459     Persistent<Set> set = new Set();
4460
4461     Persistent<IntWrapper> wp1 = IntWrapper::create(1);
4462     Persistent<IntWrapper> wp2 = IntWrapper::create(2);
4463     Persistent<IntWrapper> pw1 = IntWrapper::create(3);
4464     Persistent<IntWrapper> pw2 = IntWrapper::create(4);
4465
4466     weakPairMap->add(wp1, PairWithWeakHandling(wp1, wp1));
4467     weakPairMap->add(wp2, PairWithWeakHandling(wp1, wp1));
4468     weakPairMap2->add(wp1, PairWithWeakHandling(wp1, wp2));
4469     weakPairMap2->add(wp2, PairWithWeakHandling(wp1, wp2));
4470     // The map from wp1 to (wp2, wp1) would mark wp2 live, so we skip that.
4471     weakPairMap3->add(wp2, PairWithWeakHandling(wp2, wp1));
4472     weakPairMap4->add(wp1, PairWithWeakHandling(wp2, wp2));
4473     weakPairMap4->add(wp2, PairWithWeakHandling(wp2, wp2));
4474
4475     pairWeakMap->add(PairWithWeakHandling(pw1, pw1), pw1);
4476     pairWeakMap->add(PairWithWeakHandling(pw1, pw2), pw1);
4477     // The map from (pw2, pw1) to pw1 would make pw2 live, so we skip that.
4478     pairWeakMap->add(PairWithWeakHandling(pw2, pw2), pw1);
4479     pairWeakMap2->add(PairWithWeakHandling(pw1, pw1), pw2);
4480     pairWeakMap2->add(PairWithWeakHandling(pw1, pw2), pw2);
4481     pairWeakMap2->add(PairWithWeakHandling(pw2, pw1), pw2);
4482     pairWeakMap2->add(PairWithWeakHandling(pw2, pw2), pw2);
4483
4484
4485     set->add(wp1);
4486     set->add(wp2);
4487     set->add(pw1);
4488     set->add(pw2);
4489
4490     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4491
4492     EXPECT_EQ(2u, weakPairMap->size());
4493     EXPECT_EQ(2u, weakPairMap2->size());
4494     EXPECT_EQ(1u, weakPairMap3->size());
4495     EXPECT_EQ(2u, weakPairMap4->size());
4496
4497     EXPECT_EQ(3u, pairWeakMap->size());
4498     EXPECT_EQ(4u, pairWeakMap2->size());
4499
4500     EXPECT_EQ(4u, set->size());
4501
4502     wp2.clear(); // Kills all entries in the weakPairMaps except the first.
4503     pw2.clear(); // Kills all entries in the pairWeakMaps except the first.
4504
4505     for (int i = 0; i < 2; i++) {
4506         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4507
4508         EXPECT_EQ(1u, weakPairMap->size());
4509         EXPECT_EQ(0u, weakPairMap2->size());
4510         EXPECT_EQ(0u, weakPairMap3->size());
4511         EXPECT_EQ(0u, weakPairMap4->size());
4512
4513         EXPECT_EQ(1u, pairWeakMap->size());
4514         EXPECT_EQ(0u, pairWeakMap2->size());
4515
4516         EXPECT_EQ(2u, set->size()); // wp1 and pw1.
4517     }
4518
4519     wp1.clear();
4520     pw1.clear();
4521
4522     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4523
4524     EXPECT_EQ(0u, weakPairMap->size());
4525     EXPECT_EQ(0u, pairWeakMap->size());
4526     EXPECT_EQ(0u, set->size());
4527 }
4528
4529 class Link1 : public GarbageCollected<Link1> {
4530 public:
4531     Link1(IntWrapper* link) : m_link(link) { }
4532
4533     void trace(Visitor* visitor)
4534     {
4535         visitor->trace(m_link);
4536     }
4537
4538     IntWrapper* link() { return m_link; }
4539
4540 private:
4541     Member<IntWrapper> m_link;
4542 };
4543
4544 TEST(HeapTest, IndirectStrongToWeak)
4545 {
4546     typedef HeapHashMap<WeakMember<IntWrapper>, Member<Link1> > Map;
4547     Persistent<Map> map = new Map();
4548     Persistent<IntWrapper> deadObject = IntWrapper::create(100); // Named for "Drowning by Numbers" (1988).
4549     Persistent<IntWrapper> lifeObject = IntWrapper::create(42);
4550     map->add(deadObject, new Link1(deadObject));
4551     map->add(lifeObject, new Link1(lifeObject));
4552     EXPECT_EQ(2u, map->size());
4553     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4554     EXPECT_EQ(2u, map->size());
4555     EXPECT_EQ(deadObject, map->get(deadObject)->link());
4556     EXPECT_EQ(lifeObject, map->get(lifeObject)->link());
4557     deadObject.clear(); // Now it can live up to its name.
4558     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4559     EXPECT_EQ(1u, map->size());
4560     EXPECT_EQ(lifeObject, map->get(lifeObject)->link());
4561     lifeObject.clear(); // Despite its name.
4562     Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4563     EXPECT_EQ(0u, map->size());
4564 }
4565
4566 static Mutex& mainThreadMutex()
4567 {
4568     AtomicallyInitializedStatic(Mutex&, mainMutex = *new Mutex);
4569     return mainMutex;
4570 }
4571
4572 static ThreadCondition& mainThreadCondition()
4573 {
4574     AtomicallyInitializedStatic(ThreadCondition&, mainCondition = *new ThreadCondition);
4575     return mainCondition;
4576 }
4577
4578 static void parkMainThread()
4579 {
4580     mainThreadCondition().wait(mainThreadMutex());
4581 }
4582
4583 static void wakeMainThread()
4584 {
4585     MutexLocker locker(mainThreadMutex());
4586     mainThreadCondition().signal();
4587 }
4588
4589 static Mutex& workerThreadMutex()
4590 {
4591     AtomicallyInitializedStatic(Mutex&, workerMutex = *new Mutex);
4592     return workerMutex;
4593 }
4594
4595 static ThreadCondition& workerThreadCondition()
4596 {
4597     AtomicallyInitializedStatic(ThreadCondition&, workerCondition = *new ThreadCondition);
4598     return workerCondition;
4599 }
4600
4601 static void parkWorkerThread()
4602 {
4603     workerThreadCondition().wait(workerThreadMutex());
4604 }
4605
4606 static void wakeWorkerThread()
4607 {
4608     MutexLocker locker(workerThreadMutex());
4609     workerThreadCondition().signal();
4610 }
4611
4612 class CrossThreadObject : public GarbageCollectedFinalized<CrossThreadObject> {
4613 public:
4614     static CrossThreadObject* create(IntWrapper* workerObjectPointer)
4615     {
4616         return new CrossThreadObject(workerObjectPointer);
4617     }
4618
4619     virtual ~CrossThreadObject()
4620     {
4621         ++s_destructorCalls;
4622     }
4623
4624     static int s_destructorCalls;
4625     void trace(Visitor* visitor) { visitor->trace(m_workerObject); }
4626
4627 private:
4628     CrossThreadObject(IntWrapper* workerObjectPointer) : m_workerObject(workerObjectPointer) { }
4629
4630 private:
4631     Member<IntWrapper> m_workerObject;
4632 };
4633
4634 int CrossThreadObject::s_destructorCalls = 0;
4635
4636 class CrossThreadPointerTester {
4637 public:
4638     static void test()
4639     {
4640         CrossThreadObject::s_destructorCalls = 0;
4641         IntWrapper::s_destructorCalls = 0;
4642
4643         MutexLocker locker(mainThreadMutex());
4644         createThread(&workerThreadMain, 0, "Worker Thread");
4645
4646         parkMainThread();
4647
4648         uintptr_t stackPtrValue = 0;
4649         {
4650             // Create an object with a pointer to the other heap's IntWrapper.
4651             Persistent<CrossThreadObject> cto = CrossThreadObject::create(const_cast<IntWrapper*>(s_workerObjectPointer));
4652             s_workerObjectPointer = 0;
4653
4654             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4655
4656             // Nothing should have been collected/destructed.
4657             EXPECT_EQ(0, CrossThreadObject::s_destructorCalls);
4658             EXPECT_EQ(0, IntWrapper::s_destructorCalls);
4659
4660             // Put cto into a stack value. This is used to check that a conservative
4661             // GC succeeds even though we are tracing the other thread heap after
4662             // shutting it down.
4663             stackPtrValue = reinterpret_cast<uintptr_t>(cto.get());
4664         }
4665         // At this point it is "programatically" okay to shut down the worker thread
4666         // since the cto object should be dead. However out stackPtrValue will cause a
4667         // trace of the object when doing a conservative GC.
4668         // The worker thread's thread local GC's should just add the worker thread's
4669         // pages to the heap after finalizing IntWrapper.
4670         wakeWorkerThread();
4671
4672         // Wait for the worker to shutdown.
4673         parkMainThread();
4674
4675         // After the worker thread has detached it should have finalized the
4676         // IntWrapper object on its heaps. Since there has been no global GC
4677         // the cto object should not have been finalized.
4678         EXPECT_EQ(0, CrossThreadObject::s_destructorCalls);
4679         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
4680
4681         // Now do a conservative GC. The stackPtrValue should keep cto alive
4682         // and will also cause the orphaned page of the other thread to be
4683         // traced. At this point cto should still not be finalized.
4684         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
4685         EXPECT_EQ(0, CrossThreadObject::s_destructorCalls);
4686         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
4687
4688         // This release assert is here to ensure the stackValuePtr is not
4689         // optimized away before doing the above conservative GC. If the
4690         // EXPECT_EQ(0, CrossThreadObject::s_destructorCalls) call above
4691         // starts failing it means we have to find a better way to ensure
4692         // the stackPtrValue is not optimized away.
4693         RELEASE_ASSERT(stackPtrValue);
4694
4695         // Do a GC with no pointers on the stack to see the cto being collected.
4696         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4697         EXPECT_EQ(1, CrossThreadObject::s_destructorCalls);
4698         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
4699     }
4700
4701 private:
4702     static void workerThreadMain(void* data)
4703     {
4704         MutexLocker locker(workerThreadMutex());
4705         ThreadState::attach();
4706
4707         {
4708             // Create a worker object that is only kept alive by a cross thread
4709             // pointer (from CrossThreadObject).
4710             IntWrapper* workerObject = IntWrapper::create(42);
4711             s_workerObjectPointer = workerObject;
4712         }
4713
4714         // Wake up the main thread which is waiting for the worker to do its
4715         // allocation and passing the pointer.
4716         wakeMainThread();
4717
4718         // Wait for main thread to signal the worker to shutdown.
4719         {
4720             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
4721             parkWorkerThread();
4722         }
4723
4724         ThreadState::detach();
4725
4726         // Tell the main thread the worker has done its shutdown.
4727         wakeMainThread();
4728     }
4729
4730     static volatile IntWrapper* s_workerObjectPointer;
4731 };
4732
4733 volatile IntWrapper* CrossThreadPointerTester::s_workerObjectPointer = 0;
4734
4735 TEST(HeapTest, CrossThreadPointerToOrphanedPage)
4736 {
4737     CrossThreadPointerTester::test();
4738 }
4739
4740 class DeadBitTester {
4741 public:
4742     static void test()
4743     {
4744         IntWrapper::s_destructorCalls = 0;
4745
4746         MutexLocker locker(mainThreadMutex());
4747         createThread(&workerThreadMain, 0, "Worker Thread");
4748
4749         // Wait for the worker thread to have done its initialization,
4750         // IE. the worker allocates an object and then throw aways any
4751         // pointers to it.
4752         parkMainThread();
4753
4754         // Now do a GC. This will not find the worker threads object since it
4755         // is not referred from any of the threads. Even a conservative
4756         // GC will not find it.
4757         // Also at this point the worker is waiting for the main thread
4758         // to be parked and will not do any sweep of its heap.
4759         Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4760
4761         // Since the worker thread is not sweeping the worker object should
4762         // not have been finalized.
4763         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
4764
4765         // Put the worker thread's object address on the stack and do a
4766         // conservative GC. This should find the worker object, but since
4767         // it was dead in the previous GC it should not be traced in this
4768         // GC.
4769         uintptr_t stackPtrValue = s_workerObjectPointer;
4770         s_workerObjectPointer = 0;
4771         ASSERT_UNUSED(stackPtrValue, stackPtrValue);
4772         Heap::collectGarbage(ThreadState::HeapPointersOnStack);
4773
4774         // Since the worker thread is not sweeping the worker object should
4775         // not have been finalized.
4776         EXPECT_EQ(0, IntWrapper::s_destructorCalls);
4777
4778         // Wake up the worker thread so it can continue with its sweeping.
4779         // This should finalized the worker object which we test below.
4780         // The worker thread will go back to sleep once sweeping to ensure
4781         // we don't have thread local GCs until after validating the destructor
4782         // was called.
4783         wakeWorkerThread();
4784
4785         // Wait for the worker thread to sweep its heaps before checking.
4786         parkMainThread();
4787         EXPECT_EQ(1, IntWrapper::s_destructorCalls);
4788
4789         // Wake up the worker to allow it thread to continue with thread
4790         // shutdown.
4791         wakeWorkerThread();
4792     }
4793
4794 private:
4795
4796     static void workerThreadMain(void* data)
4797     {
4798         MutexLocker locker(workerThreadMutex());
4799
4800         ThreadState::attach();
4801
4802         {
4803             // Create a worker object that is not kept alive except the
4804             // main thread will keep it as an integer value on its stack.
4805             IntWrapper* workerObject = IntWrapper::create(42);
4806             s_workerObjectPointer = reinterpret_cast<uintptr_t>(workerObject);
4807         }
4808
4809         // Signal the main thread that the worker is done with its allocation.
4810         wakeMainThread();
4811
4812         {
4813             // Wait for the main thread to do two GCs without sweeping this thread
4814             // heap. The worker waits within a safepoint, but there is no sweeping
4815             // until leaving the safepoint scope.
4816             ThreadState::SafePointScope scope(ThreadState::NoHeapPointersOnStack);
4817             parkWorkerThread();
4818         }
4819
4820         // Wake up the main thread when done sweeping.
4821         wakeMainThread();
4822
4823         // Wait with detach until the main thread says so. This is not strictly
4824         // necessary, but it means the worker thread will not do its thread local
4825         // GCs just yet, making it easier to reason about that no new GC has occurred
4826         // and the above sweep was the one finalizing the worker object.
4827         parkWorkerThread();
4828
4829         ThreadState::detach();
4830     }
4831
4832     static volatile uintptr_t s_workerObjectPointer;
4833 };
4834
4835 volatile uintptr_t DeadBitTester::s_workerObjectPointer = 0;
4836
4837 TEST(HeapTest, ObjectDeadBit)
4838 {
4839     DeadBitTester::test();
4840 }
4841
4842 static bool allocateAndReturnBool()
4843 {
4844     Heap::collectGarbage(ThreadState::HeapPointersOnStack);
4845     return true;
4846 }
4847
4848 class MixinWithGarbageCollectionInConstructor : public GarbageCollectedMixin {
4849 public:
4850     MixinWithGarbageCollectionInConstructor() : m_dummy(allocateAndReturnBool())
4851     {
4852     }
4853 private:
4854     bool m_dummy;
4855 };
4856
4857 class ClassWithGarbageCollectingMixinConstructor
4858     : public GarbageCollected<ClassWithGarbageCollectingMixinConstructor>
4859     , public MixinWithGarbageCollectionInConstructor {
4860     USING_GARBAGE_COLLECTED_MIXIN(ClassWithGarbageCollectingMixinConstructor);
4861 public:
4862     ClassWithGarbageCollectingMixinConstructor() : m_wrapper(IntWrapper::create(32))
4863     {
4864     }
4865
4866     virtual void trace(Visitor* visitor)
4867     {
4868         visitor->trace(m_wrapper);
4869     }
4870
4871     void verify()
4872     {
4873         EXPECT_EQ(32, m_wrapper->value());
4874     }
4875
4876 private:
4877     Member<IntWrapper> m_wrapper;
4878 };
4879
4880 // Regression test for out of bounds call through vtable.
4881 // Passes if it doesn't crash.
4882 TEST(HeapTest, GarbageCollectionDuringMixinConstruction)
4883 {
4884     ClassWithGarbageCollectingMixinConstructor* a =
4885         new ClassWithGarbageCollectingMixinConstructor();
4886     a->verify();
4887 }
4888
4889 static RecursiveMutex& recursiveMutex()
4890 {
4891     AtomicallyInitializedStatic(RecursiveMutex&, recursiveMutex = *new RecursiveMutex);
4892     return recursiveMutex;
4893 }
4894
4895 class DestructorLockingObject : public GarbageCollectedFinalized<DestructorLockingObject> {
4896 public:
4897     static DestructorLockingObject* create()
4898     {
4899         return new DestructorLockingObject();
4900     }
4901
4902     virtual ~DestructorLockingObject()
4903     {
4904         SafePointAwareMutexLocker lock(recursiveMutex());
4905         ++s_destructorCalls;
4906     }
4907
4908     static int s_destructorCalls;
4909     void trace(Visitor* visitor) { }
4910
4911 private:
4912     DestructorLockingObject() { }
4913 };
4914
4915 int DestructorLockingObject::s_destructorCalls = 0;
4916
4917 class RecursiveLockingTester {
4918 public:
4919     static void test()
4920     {
4921         DestructorLockingObject::s_destructorCalls = 0;
4922
4923         MutexLocker locker(mainThreadMutex());
4924         createThread(&workerThreadMain, 0, "Worker Thread");
4925
4926         // Park the main thread until the worker thread has initialized.
4927         parkMainThread();
4928
4929         {
4930             SafePointAwareMutexLocker recursiveLocker(recursiveMutex());
4931
4932             // Let the worker try to acquire the above mutex. It won't get it
4933             // until the main thread has done its GC.
4934             wakeWorkerThread();
4935
4936             Heap::collectGarbage(ThreadState::NoHeapPointersOnStack);
4937
4938             // The worker thread should not have swept yet since it is waiting
4939             // to get the global mutex.
4940             EXPECT_EQ(0, DestructorLockingObject::s_destructorCalls);
4941         }
4942         // At this point the main thread releases the global lock and the worker
4943         // can acquire it and do its sweep of its heaps. Just wait for the worker
4944         // to complete its sweep and check the result.
4945         parkMainThread();
4946         EXPECT_EQ(1, DestructorLockingObject::s_destructorCalls);
4947     }
4948
4949 private:
4950     static void workerThreadMain(void* data)
4951     {
4952         MutexLocker locker(workerThreadMutex());
4953         ThreadState::attach();
4954
4955         DestructorLockingObject* dlo = DestructorLockingObject::create();
4956         ASSERT_UNUSED(dlo, dlo);
4957
4958         // Wake up the main thread which is waiting for the worker to do its
4959         // allocation.
4960         wakeMainThread();
4961
4962         // Wait for the main thread to get the global lock to ensure it has
4963         // it before the worker tries to acquire it. We want the worker to
4964         // block in the SafePointAwareMutexLocker until the main thread
4965         // has done a GC. The GC will not mark the "dlo" object since the worker
4966         // is entering the safepoint with NoHeapPointersOnStack. When the worker
4967         // subsequently gets the global lock and leaves the safepoint it will
4968         // sweep its heap and finalize "dlo". The destructor of "dlo" will try
4969         // to acquire the same global lock that the thread just got and deadlock
4970         // unless the global lock is recursive.
4971         parkWorkerThread();
4972         SafePointAwareMutexLocker recursiveLocker(recursiveMutex(), ThreadState::NoHeapPointersOnStack);
4973
4974         // We won't get here unless the lock is recursive since the sweep done
4975         // in the constructor of SafePointAwareMutexLocker after
4976         // getting the lock will not complete given the "dlo" destructor is
4977         // waiting to get the same lock.
4978         // Tell the main thread the worker has done its sweep.
4979         wakeMainThread();
4980
4981         ThreadState::detach();
4982     }
4983
4984     static volatile IntWrapper* s_workerObjectPointer;
4985 };
4986
4987 TEST(HeapTest, RecursiveMutex)
4988 {
4989     RecursiveLockingTester::test();
4990 }
4991
4992 template<typename T>
4993 class TraceIfNeededTester : public GarbageCollectedFinalized<TraceIfNeededTester<T> > {
4994 public:
4995     static TraceIfNeededTester<T>* create() { return new TraceIfNeededTester<T>(); }
4996     static TraceIfNeededTester<T>* create(const T& obj) { return new TraceIfNeededTester<T>(obj); }
4997     void trace(Visitor* visitor) { TraceIfNeeded<T>::trace(visitor, &m_obj); }
4998     T& obj() { return m_obj; }
4999     ~TraceIfNeededTester() { }
5000 private:
5001     TraceIfNeededTester() { }
5002     explicit TraceIfNeededTester(const T& obj) : m_obj(obj) { }
5003     T m_obj;
5004 };
5005
5006 class PartObject {
5007     DISALLOW_ALLOCATION();
5008 public:
5009     PartObject() : m_obj(SimpleObject::create()) { }
5010     void trace(Visitor* visitor) { visitor->trace(m_obj); }
5011 private:
5012     Member<SimpleObject> m_obj;
5013 };
5014
5015 TEST(HeapTest, TraceIfNeeded)
5016 {
5017     CountingVisitor visitor;
5018
5019     {
5020         TraceIfNeededTester<RefPtr<OffHeapInt> >* m_offHeap = TraceIfNeededTester<RefPtr<OffHeapInt> >::create(OffHeapInt::create(42));
5021         visitor.reset();
5022         m_offHeap->trace(&visitor);
5023         EXPECT_EQ(0u, visitor.count());
5024     }
5025
5026     {
5027         TraceIfNeededTester<PartObject>* m_part = TraceIfNeededTester<PartObject>::create();
5028         visitor.reset();
5029         m_part->trace(&visitor);
5030         EXPECT_EQ(1u, visitor.count());
5031     }
5032
5033     {
5034         TraceIfNeededTester<Member<SimpleObject> >* m_obj = TraceIfNeededTester<Member<SimpleObject> >::create(Member<SimpleObject>(SimpleObject::create()));
5035         visitor.reset();
5036         m_obj->trace(&visitor);
5037         EXPECT_EQ(1u, visitor.count());
5038     }
5039
5040     {
5041         TraceIfNeededTester<HeapVector<Member<SimpleObject> > >* m_vec = TraceIfNeededTester<HeapVector<Member<SimpleObject> > >::create();
5042         m_vec->obj().append(SimpleObject::create());
5043         visitor.reset();
5044         m_vec->trace(&visitor);
5045         EXPECT_EQ(2u, visitor.count());
5046     }
5047 }
5048
5049 class PartObjectWithVirtualMethod {
5050 public:
5051     virtual void trace(Visitor*) { }
5052 };
5053
5054 class ObjectWithVirtualPartObject : public GarbageCollected<ObjectWithVirtualPartObject> {
5055 public:
5056     ObjectWithVirtualPartObject() : m_dummy(allocateAndReturnBool()) { }
5057     void trace(Visitor* visitor) { visitor->trace(m_part); }
5058 private:
5059     bool m_dummy;
5060     PartObjectWithVirtualMethod m_part;
5061 };
5062
5063 TEST(HeapTest, PartObjectWithVirtualMethod)
5064 {
5065     ObjectWithVirtualPartObject* object = new ObjectWithVirtualPartObject();
5066     EXPECT_TRUE(object);
5067 }
5068
5069 class AllocInSuperConstructorArgumentSuper : public GarbageCollectedFinalized<AllocInSuperConstructorArgumentSuper> {
5070 public:
5071     AllocInSuperConstructorArgumentSuper(bool value) : m_value(value) { }
5072     virtual void trace(Visitor*) { }
5073     bool value() { return m_value; }
5074 private:
5075     bool m_value;
5076 };
5077
5078 class AllocInSuperConstructorArgument : public AllocInSuperConstructorArgumentSuper {
5079 public:
5080     AllocInSuperConstructorArgument()
5081         : AllocInSuperConstructorArgumentSuper(allocateAndReturnBool())
5082     {
5083     }
5084 };
5085
5086 // Regression test for crbug.com/404511. Tests conservative marking of
5087 // an object with an uninitialized vtable.
5088 TEST(HeapTest, AllocationInSuperConstructorArgument)
5089 {
5090     AllocInSuperConstructorArgument* object = new AllocInSuperConstructorArgument();
5091     EXPECT_TRUE(object);
5092     Heap::collectAllGarbage();
5093 }
5094
5095 } // namespace blink