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