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