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