15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/*
25267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) * Copyright (C) 2013 Google Inc. All rights reserved.
35267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) *
45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without
55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions are
65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * met:
75267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) *
85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     * Redistributions of source code must retain the above copyright
95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer.
105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     * Redistributions in binary form must reproduce the above
115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * copyright notice, this list of conditions and the following disclaimer
125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * in the documentation and/or other materials provided with the
135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * distribution.
145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) *     * Neither the name of Google Inc. nor the names of its
155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * contributors may be used to endorse or promote products derived from
165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * this software without specific prior written permission.
175267f701546148b83dfbe1d151cb184385bb5c22Torne (Richard Coles) *
185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */
305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)
31a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)#include "config.h"
32a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch#include "platform/heap/Heap.h"
33a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)
34197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#include "platform/ScriptForbiddenScope.h"
357242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#include "platform/Task.h"
36323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)#include "platform/TraceEvent.h"
377242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#include "platform/heap/CallbackStack.h"
38a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch#include "platform/heap/ThreadState.h"
39f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)#include "public/platform/Platform.h"
40197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#include "wtf/AddressSpaceRandomization.h"
41f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include "wtf/Assertions.h"
42323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)#include "wtf/LeakAnnotations.h"
4309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include "wtf/PassOwnPtr.h"
44e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
45f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include "wtf/HashMap.h"
46f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include "wtf/HashSet.h"
47f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include "wtf/text/StringBuilder.h"
48f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include "wtf/text/StringHash.h"
49f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include <stdio.h>
50f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#include <utility>
51f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
52e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_HEAP)
53e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#include "platform/TracedValue.h"
54e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#endif
5509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
5609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if OS(POSIX)
5709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include <sys/mman.h>
5809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include <unistd.h>
5909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#elif OS(WIN)
6009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#include <windows.h>
6109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
6209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
63c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink {
64a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)
65e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
66f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liustatic String classOf(const void* object)
67f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu{
68f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    const GCInfo* gcInfo = Heap::findGCInfo(reinterpret_cast<Address>(const_cast<void*>(object)));
69f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    if (gcInfo)
70f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return gcInfo->m_className;
71f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
72f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    return "unknown";
73f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu}
74f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
75f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
76a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdochstatic bool vTableInitialized(void* objectPointer)
77a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch{
78a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    return !!(*reinterpret_cast<Address*>(objectPointer));
79a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch}
80a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
8109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if OS(WIN)
8209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static bool IsPowerOf2(size_t power)
8309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
8409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return !((power - 1) & power);
8509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
8609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
8709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
8809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static Address roundToBlinkPageBoundary(void* base)
8909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
9009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return reinterpret_cast<Address>((reinterpret_cast<uintptr_t>(base) + blinkPageOffsetMask) & blinkPageBaseMask);
9109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
9209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
9309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static size_t roundToOsPageSize(size_t size)
9409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
9509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return (size + osPageSize() - 1) & ~(osPageSize() - 1);
9609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
9709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
9809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)size_t osPageSize()
9909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
10009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if OS(POSIX)
10109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    static const size_t pageSize = getpagesize();
10209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#else
10309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    static size_t pageSize = 0;
10409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (!pageSize) {
10509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        SYSTEM_INFO info;
10609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        GetSystemInfo(&info);
10709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        pageSize = info.dwPageSize;
10809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(IsPowerOf2(pageSize));
10909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
11009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
11109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return pageSize;
11209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
11309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
11409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class MemoryRegion {
11509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)public:
116f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    MemoryRegion(Address base, size_t size)
117f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        : m_base(base)
118f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        , m_size(size)
119f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    {
120f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        ASSERT(size > 0);
121f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    }
12209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
12309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    bool contains(Address addr) const
12409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
12509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return m_base <= addr && addr < (m_base + m_size);
12609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
12709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
12809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
12909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    bool contains(const MemoryRegion& other) const
13009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
13109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return contains(other.m_base) && contains(other.m_base + other.m_size - 1);
13209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
13309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
13409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    void release()
13509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
13609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if OS(POSIX)
13709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        int err = munmap(m_base, m_size);
13809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        RELEASE_ASSERT(!err);
13909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#else
14009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        bool success = VirtualFree(m_base, 0, MEM_RELEASE);
14109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        RELEASE_ASSERT(success);
14209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
14309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
14409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
14509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    WARN_UNUSED_RETURN bool commit()
14609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
147f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        ASSERT(Heap::heapDoesNotContainCacheIsEmpty());
14809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if OS(POSIX)
14909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        int err = mprotect(m_base, m_size, PROT_READ | PROT_WRITE);
15009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!err) {
15109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            madvise(m_base, m_size, MADV_NORMAL);
15209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return true;
15309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
15409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return false;
15509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#else
15609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        void* result = VirtualAlloc(m_base, m_size, MEM_COMMIT, PAGE_READWRITE);
15709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return !!result;
15809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
15909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
16009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
16109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    void decommit()
16209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
16309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if OS(POSIX)
16409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        int err = mprotect(m_base, m_size, PROT_NONE);
16509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        RELEASE_ASSERT(!err);
16609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // FIXME: Consider using MADV_FREE on MacOS.
16709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        madvise(m_base, m_size, MADV_DONTNEED);
16809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#else
16909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        bool success = VirtualFree(m_base, m_size, MEM_DECOMMIT);
17009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        RELEASE_ASSERT(success);
17109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
17209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
17309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
17409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address base() const { return m_base; }
175f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    size_t size() const { return m_size; }
17609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
17709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)private:
17809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address m_base;
17909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t m_size;
18009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)};
18109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
182197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// A PageMemoryRegion represents a chunk of reserved virtual address
183197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// space containing a number of blink heap pages. On Windows, reserved
184197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// virtual address space can only be given back to the system as a
185197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// whole. The PageMemoryRegion allows us to do that by keeping track
186197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// of the number of pages using it in order to be able to release all
187197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// of the virtual address space when there are no more pages using it.
188197021e6b966cfb06891637935ef33fff06433d1Ben Murdochclass PageMemoryRegion : public MemoryRegion {
189197021e6b966cfb06891637935ef33fff06433d1Ben Murdochpublic:
190197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ~PageMemoryRegion()
191197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    {
192197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        release();
193197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
194197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
195197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    void pageRemoved()
196197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    {
197197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (!--m_numPages)
198197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            delete this;
199197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
200197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
201197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    static PageMemoryRegion* allocate(size_t size, unsigned numPages)
202197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    {
203197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT(Heap::heapDoesNotContainCacheIsEmpty());
204197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
205197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Compute a random blink page aligned address for the page memory
206197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // region and attempt to get the memory there.
207197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address randomAddress = reinterpret_cast<Address>(WTF::getRandomPageBase());
208197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address alignedRandomAddress = roundToBlinkPageBoundary(randomAddress);
209197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
210197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if OS(POSIX)
211197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address base = static_cast<Address>(mmap(alignedRandomAddress, size, PROT_NONE, MAP_ANON | MAP_PRIVATE, -1, 0));
212197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        RELEASE_ASSERT(base != MAP_FAILED);
213197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (base == roundToBlinkPageBoundary(base))
214197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return new PageMemoryRegion(base, size, numPages);
215197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
216197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // We failed to get a blink page aligned chunk of
217197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // memory. Unmap the chunk that we got and fall back to
218197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // overallocating and selecting an aligned sub part of what
219197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // we allocate.
220197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        int error = munmap(base, size);
221197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        RELEASE_ASSERT(!error);
222197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        size_t allocationSize = size + blinkPageSize;
223197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        base = static_cast<Address>(mmap(alignedRandomAddress, allocationSize, PROT_NONE, MAP_ANON | MAP_PRIVATE, -1, 0));
224197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        RELEASE_ASSERT(base != MAP_FAILED);
225197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
226197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address end = base + allocationSize;
227197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address alignedBase = roundToBlinkPageBoundary(base);
228197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address regionEnd = alignedBase + size;
229197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
230197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // If the allocated memory was not blink page aligned release
231197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // the memory before the aligned address.
232197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (alignedBase != base)
233197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            MemoryRegion(base, alignedBase - base).release();
234197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
235197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Free the additional memory at the end of the page if any.
236197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (regionEnd < end)
237197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            MemoryRegion(regionEnd, end - regionEnd).release();
238197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
239197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return new PageMemoryRegion(alignedBase, size, numPages);
240197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#else
241197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address base = static_cast<Address>(VirtualAlloc(alignedRandomAddress, size, MEM_RESERVE, PAGE_NOACCESS));
242197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (base) {
243197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            ASSERT(base == alignedRandomAddress);
244197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return new PageMemoryRegion(base, size, numPages);
245197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
246197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
247197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // We failed to get the random aligned address that we asked
248197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // for. Fall back to overallocating. On Windows it is
249197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // impossible to partially release a region of memory
250197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // allocated by VirtualAlloc. To avoid wasting virtual address
251197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // space we attempt to release a large region of memory
252197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // returned as a whole and then allocate an aligned region
253197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // inside this larger region.
254197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        size_t allocationSize = size + blinkPageSize;
255197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        for (int attempt = 0; attempt < 3; attempt++) {
256197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            base = static_cast<Address>(VirtualAlloc(0, allocationSize, MEM_RESERVE, PAGE_NOACCESS));
257197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            RELEASE_ASSERT(base);
258197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            VirtualFree(base, 0, MEM_RELEASE);
259197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
260197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            Address alignedBase = roundToBlinkPageBoundary(base);
261197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            base = static_cast<Address>(VirtualAlloc(alignedBase, size, MEM_RESERVE, PAGE_NOACCESS));
262197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            if (base) {
263197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                ASSERT(base == alignedBase);
264197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                return new PageMemoryRegion(alignedBase, size, numPages);
265197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            }
266197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
267197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
268197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // We failed to avoid wasting virtual address space after
269197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // several attempts.
270197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        base = static_cast<Address>(VirtualAlloc(0, allocationSize, MEM_RESERVE, PAGE_NOACCESS));
271197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        RELEASE_ASSERT(base);
272197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
273197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // FIXME: If base is by accident blink page size aligned
274197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // here then we can create two pages out of reserved
275197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // space. Do this.
276197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address alignedBase = roundToBlinkPageBoundary(base);
277197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
278197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return new PageMemoryRegion(alignedBase, size, numPages);
279197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
280197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
281197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
282197021e6b966cfb06891637935ef33fff06433d1Ben Murdochprivate:
283197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    PageMemoryRegion(Address base, size_t size, unsigned numPages)
284197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        : MemoryRegion(base, size)
285197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        , m_numPages(numPages)
286197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    {
287197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
288197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
289197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    unsigned m_numPages;
290197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch};
291197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
29209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Representation of the memory used for a Blink heap page.
29309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)//
29409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// The representation keeps track of two memory regions:
29509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)//
296197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch// 1. The virtual memory reserved from the system in order to be able
297197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch//    to free all the virtual memory reserved. Multiple PageMemory
298197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch//    instances can share the same reserved memory region and
299197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch//    therefore notify the reserved memory region on destruction so
300197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch//    that the system memory can be given back when all PageMemory
301197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch//    instances for that memory are gone.
30209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)//
30309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// 2. The writable memory (a sub-region of the reserved virtual
30409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)//    memory region) that is used for the actual heap page payload.
30509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)//
30609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)// Guard pages are created before and after the writable memory.
30709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class PageMemory {
30809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)public:
309f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    ~PageMemory()
310f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    {
311f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        __lsan_unregister_root_region(m_writable.base(), m_writable.size());
312197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        m_reserved->pageRemoved();
313f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    }
31409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
31509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    bool commit() WARN_UNUSED_RETURN { return m_writable.commit(); }
31609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    void decommit() { m_writable.decommit(); }
31709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
31809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address writableStart() { return m_writable.base(); }
31909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
320197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    static PageMemory* setupPageMemoryInRegion(PageMemoryRegion* region, size_t pageOffset, size_t payloadSize)
321197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    {
322197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Setup the payload one OS page into the page memory. The
323197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // first os page is the guard page.
324197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Address payloadAddress = region->base() + pageOffset + osPageSize();
325197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return new PageMemory(region, MemoryRegion(payloadAddress, payloadSize));
326197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
327197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
328197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // Allocate a virtual address space for one blink page with the
32909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // following layout:
33009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    //
33109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    //    [ guard os page | ... payload ... | guard os page ]
33209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    //    ^---{ aligned to blink page size }
33309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    //
33409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    static PageMemory* allocate(size_t payloadSize)
33509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
33609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(payloadSize > 0);
33709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
33809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // Virtual memory allocation routines operate in OS page sizes.
33909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // Round up the requested size to nearest os page size.
34009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        payloadSize = roundToOsPageSize(payloadSize);
34109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
342197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Overallocate by 2 times OS page size to have space for a
343197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // guard page at the beginning and end of blink heap page.
344197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        size_t allocationSize = payloadSize + 2 * osPageSize();
345197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PageMemoryRegion* pageMemoryRegion = PageMemoryRegion::allocate(allocationSize, 1);
346197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PageMemory* storage = setupPageMemoryInRegion(pageMemoryRegion, 0, payloadSize);
347197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        RELEASE_ASSERT(storage->commit());
34809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return storage;
34909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
35009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
35109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)private:
352197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    PageMemory(PageMemoryRegion* reserved, const MemoryRegion& writable)
35309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        : m_reserved(reserved)
35409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        , m_writable(writable)
35509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
356197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT(reserved->contains(writable));
357f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)
358f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        // Register the writable area of the memory as part of the LSan root set.
359f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        // Only the writable area is mapped and can contain C++ objects. Those
360f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        // C++ objects can contain pointers to objects outside of the heap and
361f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        // should therefore be part of the LSan root set.
362f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        __lsan_register_root_region(m_writable.base(), m_writable.size());
36309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
36409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
365197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
366197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    PageMemoryRegion* m_reserved;
36709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    MemoryRegion m_writable;
36809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)};
36909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
37009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class GCScope {
37109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)public:
37209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    explicit GCScope(ThreadState::StackState stackState)
37309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        : m_state(ThreadState::current())
37409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        , m_safePointScope(stackState)
375323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        , m_parkedAllThreads(false)
37609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
377e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        TRACE_EVENT0("blink_gc", "Heap::GCScope");
378323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        const char* samplingState = TRACE_EVENT_GET_SAMPLING_STATE();
379323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        if (m_state->isMainThread())
380e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            TRACE_EVENT_SET_SAMPLING_STATE("blink_gc", "BlinkGCWaiting");
381323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)
38209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        m_state->checkThread();
38309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
38409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // FIXME: in an unlikely coincidence that two threads decide
38509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // to collect garbage at the same time, avoid doing two GCs in
38609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // a row.
387d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)        RELEASE_ASSERT(!m_state->isInGC());
388d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)        RELEASE_ASSERT(!m_state->isSweepInProgress());
389323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        if (LIKELY(ThreadState::stopThreads())) {
390323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)            m_parkedAllThreads = true;
391323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)            m_state->enterGC();
392323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        }
393323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        if (m_state->isMainThread())
394323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)            TRACE_EVENT_SET_NONCONST_SAMPLING_STATE(samplingState);
39509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
39609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
397323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)    bool allThreadsParked() { return m_parkedAllThreads; }
398323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)
39909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ~GCScope()
40009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
401323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        // Only cleanup if we parked all threads in which case the GC happened
402323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        // and we need to resume the other threads.
403323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        if (LIKELY(m_parkedAllThreads)) {
404323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)            m_state->leaveGC();
405323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)            ASSERT(!m_state->isInGC());
406323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)            ThreadState::resumeThreads();
407323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)        }
40809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
40909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
41009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)private:
41109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ThreadState* m_state;
41209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ThreadState::SafePointScope m_safePointScope;
413323480423219ecd77329f8326dc5e0e3b50926d4Torne (Richard Coles)    bool m_parkedAllThreads; // False if we fail to park all threads
41409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)};
41509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
41609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)NO_SANITIZE_ADDRESS
41709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)bool HeapObjectHeader::isMarked() const
41809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
41909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    checkHeader();
4207242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    unsigned size = asanUnsafeAcquireLoad(&m_size);
4217242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return size & markBitMask;
42209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
42309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
42409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)NO_SANITIZE_ADDRESS
42509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapObjectHeader::unmark()
42609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
42709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    checkHeader();
42809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_size &= ~markBitMask;
42909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
43009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
43109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)NO_SANITIZE_ADDRESS
432197021e6b966cfb06891637935ef33fff06433d1Ben Murdochbool HeapObjectHeader::hasDeadMark() const
43309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
43409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    checkHeader();
435197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return m_size & deadBitMask;
43609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
43709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
43809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)NO_SANITIZE_ADDRESS
439197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid HeapObjectHeader::clearDeadMark()
44009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
44109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    checkHeader();
442197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    m_size &= ~deadBitMask;
44309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
44409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
44509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)NO_SANITIZE_ADDRESS
446197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid HeapObjectHeader::setDeadMark()
44709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
448197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ASSERT(!isMarked());
44909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    checkHeader();
450197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    m_size |= deadBitMask;
45109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
45209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
453197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
45409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)NO_SANITIZE_ADDRESS
45509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapObjectHeader::zapMagic()
45609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
45709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_magic = zappedMagic;
45809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
45909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
46009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
46109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)HeapObjectHeader* HeapObjectHeader::fromPayload(const void* payload)
46209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
46309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address addr = reinterpret_cast<Address>(const_cast<void*>(payload));
46409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    HeapObjectHeader* header =
46509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        reinterpret_cast<HeapObjectHeader*>(addr - objectHeaderSize);
46609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return header;
46709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
46809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
46909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapObjectHeader::finalize(const GCInfo* gcInfo, Address object, size_t objectSize)
47009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
47109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gcInfo);
47209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (gcInfo->hasFinalizer()) {
47309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        gcInfo->m_finalize(object);
47409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
475197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
476197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER)
477197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // In Debug builds, memory is zapped when it's freed, and the zapped memory is
478197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // zeroed out when the memory is reused. Memory is also zapped when using Leak
479197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // Sanitizer because the heap is used as a root region for LSan and therefore
480197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // pointers in unreachable memory could hide leaks.
48109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (size_t i = 0; i < objectSize; i++)
48209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        object[i] = finalizedZapValue;
483197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
484197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // Zap the primary vTable entry (secondary vTable entries are not zapped).
4857242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (gcInfo->hasVTable()) {
4867242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        *(reinterpret_cast<uintptr_t*>(object)) = zappedVTable;
4877242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
488197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
489197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // In Release builds, the entire object is zeroed out when it is added to the free list.
490197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // This happens right after sweeping the page and before the thread commences execution.
49109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
49209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
49309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)NO_SANITIZE_ADDRESS
49409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void FinalizedHeapObjectHeader::finalize()
49509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
49609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    HeapObjectHeader::finalize(m_gcInfo, payload(), payloadSize());
49709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
49809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
49909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
50009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void LargeHeapObject<Header>::unmark()
50109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
50209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return heapObjectHeader()->unmark();
50309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
50409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
50509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
50609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)bool LargeHeapObject<Header>::isMarked()
50709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
50809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return heapObjectHeader()->isMarked();
50909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
51009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
51109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
512197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid LargeHeapObject<Header>::setDeadMark()
513197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
514197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    heapObjectHeader()->setDeadMark();
515197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
516197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
517197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<typename Header>
518f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)void LargeHeapObject<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
51909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
520f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    ASSERT(contains(address));
521197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (!objectContains(address) || heapObjectHeader()->hasDeadMark())
522f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        return;
523e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
524f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    visitor->setHostInfo(&address, "stack");
525f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
526f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    mark(visitor);
52709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
52809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
529e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(ASSERT)
530e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)static bool isUninitializedMemory(void* objectPointer, size_t objectSize)
531e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles){
532e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    // Scan through the object's fields and check that they are all zero.
533e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    Address* objectFields = reinterpret_cast<Address*>(objectPointer);
534e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    for (size_t i = 0; i < objectSize / sizeof(Address); ++i) {
535e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (objectFields[i] != 0)
536e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            return false;
537e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
538e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    return true;
539e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)}
540e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#endif
541e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
54209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
54309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void LargeHeapObject<FinalizedHeapObjectHeader>::mark(Visitor* visitor)
54409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
545e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    if (heapObjectHeader()->hasVTable() && !vTableInitialized(payload())) {
546e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        FinalizedHeapObjectHeader* header = heapObjectHeader();
547e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        visitor->markNoTracing(header);
548e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        ASSERT(isUninitializedMemory(header->payload(), header->payloadSize()));
549e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    } else {
550a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        visitor->mark(heapObjectHeader(), heapObjectHeader()->traceCallback());
551e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
55209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
55309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
55409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
55509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void LargeHeapObject<HeapObjectHeader>::mark(Visitor* visitor)
55609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
55709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gcInfo());
558e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    if (gcInfo()->hasVTable() && !vTableInitialized(payload())) {
559e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        HeapObjectHeader* header = heapObjectHeader();
560e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        visitor->markNoTracing(header);
561e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        ASSERT(isUninitializedMemory(header->payload(), header->payloadSize()));
562e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    } else {
563a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        visitor->mark(heapObjectHeader(), gcInfo()->m_trace);
564e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
56509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
56609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
56709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
56809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void LargeHeapObject<FinalizedHeapObjectHeader>::finalize()
56909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
57009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    heapObjectHeader()->finalize();
57109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
57209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
57309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
57409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void LargeHeapObject<HeapObjectHeader>::finalize()
57509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
57609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gcInfo());
57709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    HeapObjectHeader::finalize(gcInfo(), payload(), payloadSize());
57809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
57909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
58009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)FinalizedHeapObjectHeader* FinalizedHeapObjectHeader::fromPayload(const void* payload)
58109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
58209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address addr = reinterpret_cast<Address>(const_cast<void*>(payload));
58309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    FinalizedHeapObjectHeader* header =
58409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        reinterpret_cast<FinalizedHeapObjectHeader*>(addr - finalizedHeaderSize);
58509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return header;
58609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
58709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
58809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
589197021e6b966cfb06891637935ef33fff06433d1Ben MurdochThreadHeap<Header>::ThreadHeap(ThreadState* state, int index)
59009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    : m_currentAllocationPoint(0)
59109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    , m_remainingAllocationSize(0)
59209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    , m_firstPage(0)
59309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    , m_firstLargeHeapObject(0)
5949e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    , m_firstPageAllocatedDuringSweeping(0)
5959e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    , m_lastPageAllocatedDuringSweeping(0)
5967242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    , m_mergePoint(0)
59709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    , m_biggestFreeListIndex(0)
59809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    , m_threadState(state)
599197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    , m_index(index)
6009e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    , m_numberOfNormalPages(0)
6017242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    , m_promptlyFreedCount(0)
60209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
60309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    clearFreeLists();
60409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
60509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
60609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
60709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)ThreadHeap<Header>::~ThreadHeap()
60809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
609197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ASSERT(!m_firstPage);
610197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ASSERT(!m_firstLargeHeapObject);
611197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
612197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
613197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<typename Header>
614197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid ThreadHeap<Header>::cleanupPages()
615197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
61609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    clearFreeLists();
617197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    flushHeapContainsCache();
618197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
619197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // Add the ThreadHeap's pages to the orphanedPagePool.
620197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (HeapPage<Header>* page = m_firstPage; page; page = page->m_next)
621197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
622197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    m_firstPage = 0;
623197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
624197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (LargeHeapObject<Header>* largeObject = m_firstLargeHeapObject; largeObject; largeObject = largeObject->m_next)
625197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Heap::orphanedPagePool()->addOrphanedPage(m_index, largeObject);
626197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    m_firstLargeHeapObject = 0;
62709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
62809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
62909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
63009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)Address ThreadHeap<Header>::outOfLineAllocate(size_t size, const GCInfo* gcInfo)
63109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
63209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t allocationSize = allocationSizeFromSize(size);
63309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (threadState()->shouldGC()) {
63409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (threadState()->shouldForceConservativeGC())
63509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            Heap::collectGarbage(ThreadState::HeapPointersOnStack);
63609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        else
63709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            threadState()->setGCRequested();
63809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
63909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ensureCurrentAllocation(allocationSize, gcInfo);
64009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return allocate(size, gcInfo);
64109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
64209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
64309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
64409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)bool ThreadHeap<Header>::allocateFromFreeList(size_t minSize)
64509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
64609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t bucketSize = 1 << m_biggestFreeListIndex;
64709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    int i = m_biggestFreeListIndex;
64809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (; i > 0; i--, bucketSize >>= 1) {
64909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (bucketSize < minSize)
65009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            break;
65109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        FreeListEntry* entry = m_freeLists[i];
65209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (entry) {
65309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            m_biggestFreeListIndex = i;
65409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            entry->unlink(&m_freeLists[i]);
65509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            setAllocationPoint(entry->address(), entry->size());
65609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            ASSERT(currentAllocationPoint() && remainingAllocationSize() >= minSize);
65709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return true;
65809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
65909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
66009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_biggestFreeListIndex = i;
66109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return false;
66209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
66309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
66409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
66509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<Header>::ensureCurrentAllocation(size_t minSize, const GCInfo* gcInfo)
66609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
66709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(minSize >= allocationGranularity);
66809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (remainingAllocationSize() >= minSize)
66909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return;
67009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
6717242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (remainingAllocationSize() > 0) {
67209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        addToFreeList(currentAllocationPoint(), remainingAllocationSize());
6737242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        setAllocationPoint(0, 0);
6747242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
67509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (allocateFromFreeList(minSize))
67609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return;
6777242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (coalesce(minSize) && allocateFromFreeList(minSize))
6787242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return;
67909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    addPageToHeap(gcInfo);
68009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    bool success = allocateFromFreeList(minSize);
68109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    RELEASE_ASSERT(success);
68209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
68309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
68409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
68509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)BaseHeapPage* ThreadHeap<Header>::heapPageFromAddress(Address address)
68609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
68709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
68809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (page->contains(address))
68909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return page;
69009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
6919e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    for (HeapPage<Header>* page = m_firstPageAllocatedDuringSweeping; page; page = page->next()) {
6929e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        if (page->contains(address))
6939e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            return page;
6949e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    }
69509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
696f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        // Check that large pages are blinkPageSize aligned (modulo the
697f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        // osPageSize for the guard page).
698f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        ASSERT(reinterpret_cast<Address>(current) - osPageSize() == roundToBlinkPageStart(reinterpret_cast<Address>(current)));
69909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (current->contains(address))
70009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return current;
70109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
70209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return 0;
70309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
70409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
705e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
706f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liutemplate<typename Header>
707f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liuconst GCInfo* ThreadHeap<Header>::findGCInfoOfLargeHeapObject(Address address)
708f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu{
709f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
710f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        if (current->contains(address))
711f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            return current->gcInfo();
712f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
713f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    return 0;
714f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu}
715f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
716f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
717e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_HEAP)
718e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#define GC_PROFILE_HEAP_PAGE_SNAPSHOT_THRESHOLD 0
719e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)template<typename Header>
720e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)void ThreadHeap<Header>::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
721e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles){
722e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    size_t previousPageCount = info->pageCount;
723e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
724e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    json->beginArray("pages");
725e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    for (HeapPage<Header>* page = m_firstPage; page; page = page->next(), ++info->pageCount) {
726e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        // FIXME: To limit the size of the snapshot we only output "threshold" many page snapshots.
727e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (info->pageCount < GC_PROFILE_HEAP_PAGE_SNAPSHOT_THRESHOLD) {
728e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            json->beginArray();
729e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            json->pushInteger(reinterpret_cast<intptr_t>(page));
730e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            page->snapshot(json, info);
731e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            json->endArray();
732e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        } else {
733e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            page->snapshot(0, info);
734e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        }
735e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
736e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    json->endArray();
737e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
738e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    json->beginArray("largeObjects");
739e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
740e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        json->beginDictionary();
741e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        current->snapshot(json, info);
742e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        json->endDictionary();
743e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
744e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    json->endArray();
745e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
746e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    json->setInteger("pageCount", info->pageCount - previousPageCount);
747e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)}
748e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#endif
749e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
75009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
75109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<Header>::addToFreeList(Address address, size_t size)
75209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
75309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(heapPageFromAddress(address));
75409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(heapPageFromAddress(address + size - 1));
75509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(size < blinkPagePayloadSize());
75609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // The free list entries are only pointer aligned (but when we allocate
75709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // from them we are 8 byte aligned due to the header size).
75809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(!((reinterpret_cast<uintptr_t>(address) + sizeof(Header)) & allocationMask));
75909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(!(size & allocationMask));
76009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASAN_POISON_MEMORY_REGION(address, size);
76109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    FreeListEntry* entry;
76209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (size < sizeof(*entry)) {
76309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // Create a dummy header with only a size and freelist bit set.
76409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(size >= sizeof(BasicObjectHeader));
76509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // Free list encode the size to mark the lost memory as freelist memory.
76609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        new (NotNull, address) BasicObjectHeader(BasicObjectHeader::freeListEncodedSize(size));
76709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // This memory gets lost. Sweeping can reclaim it.
76809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return;
76909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
77009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    entry = new (NotNull, address) FreeListEntry(size);
77109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if defined(ADDRESS_SANITIZER)
772197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // For ASan we don't add the entry to the free lists until the asanDeferMemoryReuseCount
77309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // reaches zero. However we always add entire pages to ensure that adding a new page will
77409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // increase the allocation space.
77509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (HeapPage<Header>::payloadSize() != size && !entry->shouldAddToFreeList())
77609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return;
77709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
77809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    int index = bucketIndexForSize(size);
77909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    entry->link(&m_freeLists[index]);
7809e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    if (!m_lastFreeListEntries[index])
7819e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        m_lastFreeListEntries[index] = entry;
78209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (index > m_biggestFreeListIndex)
78309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        m_biggestFreeListIndex = index;
78409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
78509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
78609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
7877242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccivoid ThreadHeap<Header>::promptlyFreeObject(Header* header)
7887242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci{
7897242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(!m_threadState->isSweepInProgress());
7907242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    header->checkHeader();
7917242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    Address address = reinterpret_cast<Address>(header);
7927242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    Address payload = header->payload();
7937242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    size_t size = header->size();
7947242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    size_t payloadSize = header->payloadSize();
7957242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    BaseHeapPage* page = pageHeaderFromObject(address);
7967242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(size > 0);
7977242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(page == heapPageFromAddress(address));
7987242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
7997242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    {
8007242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        ThreadState::NoSweepScope scope(m_threadState);
8017242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        HeapObjectHeader::finalize(header->gcInfo(), payload, payloadSize);
8027242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
8037242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        memset(payload, 0, payloadSize);
8047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#endif
8057242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        header->markPromptlyFreed();
8067242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
8077242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8087242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    page->addToPromptlyFreedSize(size);
8097242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    m_promptlyFreedCount++;
8107242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci}
8117242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8127242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Header>
8137242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccibool ThreadHeap<Header>::coalesce(size_t minSize)
8147242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci{
8157242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (m_threadState->isSweepInProgress())
8167242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return false;
8177242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8187242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (m_promptlyFreedCount < 256)
8197242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return false;
8207242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8217242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // The smallest bucket able to satisfy an allocation request for minSize is
8227242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // the bucket where all free-list entries are guarantied to be larger than
8237242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // minSize. That bucket is one larger than the bucket minSize would go into.
8247242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    size_t neededBucketIndex = bucketIndexForSize(minSize) + 1;
8257242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    size_t neededFreeEntrySize = 1 << neededBucketIndex;
8267242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    size_t neededPromptlyFreedSize = neededFreeEntrySize * 3;
8277242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    size_t foundFreeEntrySize = 0;
8287242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8297242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // Bailout early on large requests because it is unlikely we will find a free-list entry.
8307242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (neededPromptlyFreedSize >= blinkPageSize)
8317242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return false;
8327242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8337242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    TRACE_EVENT_BEGIN2("blink_gc", "ThreadHeap::coalesce" , "requestedSize", (unsigned)minSize , "neededSize", (unsigned)neededFreeEntrySize);
8347242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8357242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // Search for a coalescing candidate.
8367242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(!ownsNonEmptyAllocationArea());
8377242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    size_t pageCount = 0;
8387242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    HeapPage<Header>* page = m_firstPage;
8397242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    while (page) {
8407242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // Only consider one of the first 'n' pages. A "younger" page is more likely to have freed backings.
8417242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (++pageCount > numberOfPagesToConsiderForCoalescing) {
8427242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            page = 0;
8437242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            break;
8447242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        }
8457242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // Only coalesce pages with "sufficient" promptly freed space.
8467242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (page->promptlyFreedSize() >= neededPromptlyFreedSize) {
8477242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            break;
8487242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        }
8497242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        page = page->next();
8507242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
8517242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8527242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // If we found a likely candidate, fully coalesce all its promptly-freed entries.
8537242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (page) {
8547242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        page->clearObjectStartBitMap();
8557242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        page->resetPromptlyFreedSize();
8567242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        size_t freedCount = 0;
8577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        Address startOfGap = page->payload();
8587242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        for (Address headerAddress = startOfGap; headerAddress < page->end(); ) {
8597242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            BasicObjectHeader* basicHeader = reinterpret_cast<BasicObjectHeader*>(headerAddress);
8607242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            ASSERT(basicHeader->size() > 0);
8617242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            ASSERT(basicHeader->size() < blinkPagePayloadSize());
8627242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8637242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            if (basicHeader->isPromptlyFreed()) {
8647242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                stats().decreaseObjectSpace(reinterpret_cast<Header*>(basicHeader)->payloadSize());
8657242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                size_t size = basicHeader->size();
8667242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                ASSERT(size >= sizeof(Header));
8677242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
8687242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                memset(headerAddress, 0, sizeof(Header));
8697242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#endif
8707242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                ++freedCount;
8717242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                headerAddress += size;
8727242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                continue;
8737242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            }
8747242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8757242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            if (startOfGap != headerAddress) {
8767242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                size_t size = headerAddress - startOfGap;
8777242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                addToFreeList(startOfGap, size);
8787242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                if (size > foundFreeEntrySize)
8797242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                    foundFreeEntrySize = size;
8807242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            }
8817242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8827242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            headerAddress += basicHeader->size();
8837242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            startOfGap = headerAddress;
8847242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        }
8857242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8867242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (startOfGap != page->end()) {
8877242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            size_t size = page->end() - startOfGap;
8887242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            addToFreeList(startOfGap, size);
8897242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            if (size > foundFreeEntrySize)
8907242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci                foundFreeEntrySize = size;
8917242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        }
8927242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
8937242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // Check before subtracting because freedCount might not be balanced with freed entries.
8947242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        if (freedCount < m_promptlyFreedCount)
8957242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            m_promptlyFreedCount -= freedCount;
8967242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        else
8977242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            m_promptlyFreedCount = 0;
8987242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
8997242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
9007242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    TRACE_EVENT_END1("blink_gc", "ThreadHeap::coalesce", "foundFreeEntrySize", (unsigned)foundFreeEntrySize);
9017242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
9027242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (foundFreeEntrySize < neededFreeEntrySize) {
9037242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // If coalescing failed, reset the freed count to delay coalescing again.
9047242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        m_promptlyFreedCount = 0;
9057242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return false;
9067242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
9077242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
9087242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return true;
9097242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci}
9107242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
9117242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccitemplate<typename Header>
91209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)Address ThreadHeap<Header>::allocateLargeObject(size_t size, const GCInfo* gcInfo)
91309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
91409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // Caller already added space for object header and rounded up to allocation alignment
91509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(!(size & allocationMask));
91609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
91709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t allocationSize = sizeof(LargeHeapObject<Header>) + size;
91809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
91909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // Ensure that there is enough space for alignment. If the header
92009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // is not a multiple of 8 bytes we will allocate an extra
92109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // headerPadding<Header> bytes to ensure it 8 byte aligned.
92209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    allocationSize += headerPadding<Header>();
92309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
924197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // If ASan is supported we add allocationGranularity bytes to the allocated space and
92509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // poison that to detect overflows
92609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if defined(ADDRESS_SANITIZER)
92709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    allocationSize += allocationGranularity;
92809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
92909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (threadState()->shouldGC())
93009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        threadState()->setGCRequested();
931f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    Heap::flushHeapDoesNotContainCache();
93209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    PageMemory* pageMemory = PageMemory::allocate(allocationSize);
93309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address largeObjectAddress = pageMemory->writableStart();
93409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address headerAddress = largeObjectAddress + sizeof(LargeHeapObject<Header>) + headerPadding<Header>();
93509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    memset(headerAddress, 0, size);
93609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Header* header = new (NotNull, headerAddress) Header(size, gcInfo);
93709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address result = headerAddress + sizeof(*header);
93809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(!(reinterpret_cast<uintptr_t>(result) & allocationMask));
939d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    LargeHeapObject<Header>* largeObject = new (largeObjectAddress) LargeHeapObject<Header>(pageMemory, gcInfo, threadState());
94009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
94109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // Poison the object header and allocationGranularity bytes after the object
94209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASAN_POISON_MEMORY_REGION(header, sizeof(*header));
94309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASAN_POISON_MEMORY_REGION(largeObject->address() + largeObject->size(), allocationGranularity);
94409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    largeObject->link(&m_firstLargeHeapObject);
94509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    stats().increaseAllocatedSpace(largeObject->size());
94609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    stats().increaseObjectSpace(largeObject->payloadSize());
94709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return result;
94809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
94909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
95009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
95109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<Header>::freeLargeObject(LargeHeapObject<Header>* object, LargeHeapObject<Header>** previousNext)
95209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
953f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    flushHeapContainsCache();
95409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    object->unlink(previousNext);
95509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    object->finalize();
95609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
95709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // Unpoison the object header and allocationGranularity bytes after the
95809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // object before freeing.
95909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASAN_UNPOISON_MEMORY_REGION(object->heapObjectHeader(), sizeof(Header));
96009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASAN_UNPOISON_MEMORY_REGION(object->address() + object->size(), allocationGranularity);
961197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
962197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (object->terminating()) {
963197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT(ThreadState::current()->isTerminating());
964197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // The thread is shutting down so this object is being removed as part
965197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // of a thread local GC. In that case the object could be traced in the
966197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // next global GC either due to a dead object being traced via a
967197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // conservative pointer or due to a programming error where an object
968197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // in another thread heap keeps a dangling pointer to this object.
969197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // To guard against this we put the large object memory in the
970197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // orphanedPagePool to ensure it is still reachable. After the next global
971197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // GC it can be released assuming no rogue/dangling pointers refer to
972197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // it.
973197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // NOTE: large objects are not moved to the free page pool as it is
974197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // unlikely they can be reused due to their individual sizes.
975197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Heap::orphanedPagePool()->addOrphanedPage(m_index, object);
976197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    } else {
977197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT(!ThreadState::current()->isTerminating());
978197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PageMemory* memory = object->storage();
979197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        object->~LargeHeapObject<Header>();
980197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        delete memory;
981197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
982197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
983197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
984197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<typename DataType>
985197021e6b966cfb06891637935ef33fff06433d1Ben MurdochPagePool<DataType>::PagePool()
986197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
987197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (int i = 0; i < NumberOfHeaps; ++i) {
988197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        m_pool[i] = 0;
989197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
990197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
991197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
992197021e6b966cfb06891637935ef33fff06433d1Ben MurdochFreePagePool::~FreePagePool()
993197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
994197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (int index = 0; index < NumberOfHeaps; ++index) {
995197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        while (PoolEntry* entry = m_pool[index]) {
996197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            m_pool[index] = entry->next;
997197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            PageMemory* memory = entry->data;
998197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            ASSERT(memory);
999197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            delete memory;
1000197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            delete entry;
1001197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
1002197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1003197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1004197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1005197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid FreePagePool::addFreePage(int index, PageMemory* memory)
1006197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1007197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // When adding a page to the pool we decommit it to ensure it is unused
1008197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // while in the pool. This also allows the physical memory, backing the
1009197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // page, to be given back to the OS.
1010197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    memory->decommit();
1011197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    MutexLocker locker(m_mutex[index]);
1012197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    PoolEntry* entry = new PoolEntry(memory, m_pool[index]);
1013197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    m_pool[index] = entry;
1014197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1015197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1016197021e6b966cfb06891637935ef33fff06433d1Ben MurdochPageMemory* FreePagePool::takeFreePage(int index)
1017197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1018197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    MutexLocker locker(m_mutex[index]);
1019197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    while (PoolEntry* entry = m_pool[index]) {
1020197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        m_pool[index] = entry->next;
1021197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PageMemory* memory = entry->data;
1022197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT(memory);
1023197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        delete entry;
1024197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (memory->commit())
1025197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            return memory;
1026197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1027197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // We got some memory, but failed to commit it, try again.
1028197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        delete memory;
1029197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1030197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return 0;
1031197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1032197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1033197021e6b966cfb06891637935ef33fff06433d1Ben MurdochOrphanedPagePool::~OrphanedPagePool()
1034197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1035197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (int index = 0; index < NumberOfHeaps; ++index) {
1036197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        while (PoolEntry* entry = m_pool[index]) {
1037197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            m_pool[index] = entry->next;
1038197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            BaseHeapPage* page = entry->data;
1039197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            delete entry;
1040197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            PageMemory* memory = page->storage();
1041197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            ASSERT(memory);
1042197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            page->~BaseHeapPage();
1043197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            delete memory;
1044197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
1045197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1046197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1047197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1048197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid OrphanedPagePool::addOrphanedPage(int index, BaseHeapPage* page)
1049197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1050197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    page->markOrphaned();
1051197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    PoolEntry* entry = new PoolEntry(page, m_pool[index]);
1052197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    m_pool[index] = entry;
1053197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1054197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1055197021e6b966cfb06891637935ef33fff06433d1Ben MurdochNO_SANITIZE_ADDRESS
1056197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid OrphanedPagePool::decommitOrphanedPages()
1057197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1058197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
1059197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // No locking needed as all threads are at safepoints at this point in time.
1060197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
1061197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it)
1062197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        ASSERT((*it)->isAtSafePoint());
1063197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
1064197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1065197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (int index = 0; index < NumberOfHeaps; ++index) {
1066197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PoolEntry* entry = m_pool[index];
1067197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PoolEntry** prevNext = &m_pool[index];
1068197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        while (entry) {
1069197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            BaseHeapPage* page = entry->data;
1070197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            if (page->tracedAfterOrphaned()) {
1071197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                // If the orphaned page was traced in the last GC it is not
1072197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                // decommited. We only decommit a page, ie. put it in the
1073197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                // memory pool, when the page has no objects pointing to it.
1074197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                // We remark the page as orphaned to clear the tracedAfterOrphaned
1075197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                // flag and any object trace bits that were set during tracing.
1076197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                page->markOrphaned();
1077197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                prevNext = &entry->next;
1078197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                entry = entry->next;
1079197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                continue;
1080197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            }
1081197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1082197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // Page was not traced. Check if we should reuse the memory or just
1083197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // free it. Large object memory is not reused, but freed, normal
1084197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // blink heap pages are reused.
1085197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // NOTE: We call the destructor before freeing or adding to the
1086197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // free page pool.
1087197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            PageMemory* memory = page->storage();
1088197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            if (page->isLargeObject()) {
1089197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                page->~BaseHeapPage();
1090197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                delete memory;
1091197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            } else {
1092197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                page->~BaseHeapPage();
1093197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                // Clear out the page's memory before adding it to the free page
1094197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                // pool to ensure it is zero filled when being reused.
1095197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                clearMemory(memory);
1096197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                Heap::freePagePool()->addFreePage(index, memory);
1097197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            }
1098197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1099197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            PoolEntry* deadEntry = entry;
1100197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            entry = entry->next;
1101197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            *prevNext = entry;
1102197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            delete deadEntry;
1103197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
1104197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1105197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1106197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1107197021e6b966cfb06891637935ef33fff06433d1Ben MurdochNO_SANITIZE_ADDRESS
1108197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid OrphanedPagePool::clearMemory(PageMemory* memory)
1109197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1110197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if defined(ADDRESS_SANITIZER)
1111197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // Don't use memset when running with ASan since this needs to zap
1112197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // poisoned memory as well and the NO_SANITIZE_ADDRESS annotation
1113197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // only works for code in this method and not for calls to memset.
1114197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    Address base = memory->writableStart();
1115197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (Address current = base; current < base + blinkPagePayloadSize(); ++current)
1116197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        *current = 0;
1117197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#else
1118197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    memset(memory->writableStart(), 0, blinkPagePayloadSize());
1119197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
112009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
112109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1122197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
1123197021e6b966cfb06891637935ef33fff06433d1Ben Murdochbool OrphanedPagePool::contains(void* object)
1124197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
1125197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (int index = 0; index < NumberOfHeaps; ++index) {
1126197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        for (PoolEntry* entry = m_pool[index]; entry; entry = entry->next) {
1127197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            BaseHeapPage* page = entry->data;
1128197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            if (page->contains(reinterpret_cast<Address>(object)))
1129197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                return true;
1130197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
1131197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1132197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return false;
1133197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
1134197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
1135197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
113609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
113709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<FinalizedHeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
113809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
113909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // When adding a page to the ThreadHeap using FinalizedHeapObjectHeaders the GCInfo on
114009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // the heap should be unused (ie. 0).
114109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    allocatePage(0);
114209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
114309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
114409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
114509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<HeapObjectHeader>::addPageToHeap(const GCInfo* gcInfo)
114609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
114709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // When adding a page to the ThreadHeap using HeapObjectHeaders store the GCInfo on the heap
114809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // since it is the same for all objects
114909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gcInfo);
115009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    allocatePage(gcInfo);
115109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
115209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1153197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate <typename Header>
1154197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid ThreadHeap<Header>::removePageFromHeap(HeapPage<Header>* page)
115509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
11569e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    MutexLocker locker(m_threadState->sweepMutex());
1157f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    flushHeapContainsCache();
1158197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (page->terminating()) {
1159197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // The thread is shutting down so this page is being removed as part
1160197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // of a thread local GC. In that case the page could be accessed in the
1161197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // next global GC either due to a dead object being traced via a
1162197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // conservative pointer or due to a programming error where an object
1163197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // in another thread heap keeps a dangling pointer to this object.
1164197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // To guard against this we put the page in the orphanedPagePool to
1165197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // ensure it is still reachable. After the next global GC it can be
1166197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // decommitted and moved to the page pool assuming no rogue/dangling
1167197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // pointers refer to it.
1168197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Heap::orphanedPagePool()->addOrphanedPage(m_index, page);
1169197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    } else {
1170197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PageMemory* memory = page->storage();
1171197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        page->~HeapPage<Header>();
1172197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Heap::freePagePool()->addFreePage(m_index, memory);
1173197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
117409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
117509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
117609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
117709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<Header>::allocatePage(const GCInfo* gcInfo)
117809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
1179f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    Heap::flushHeapDoesNotContainCache();
1180197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    PageMemory* pageMemory = Heap::freePagePool()->takeFreePage(m_index);
1181197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // We continue allocating page memory until we succeed in getting one.
1182197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // Since the FreePagePool is global other threads could use all the
1183197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    // newly allocated page memory before this thread calls takeFreePage.
1184197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    while (!pageMemory) {
1185197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Allocate a memory region for blinkPagesPerRegion pages that
1186197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // will each have the following layout.
1187197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        //
1188197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        //    [ guard os page | ... payload ... | guard os page ]
1189197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        //    ^---{ aligned to blink page size }
1190197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        PageMemoryRegion* region = PageMemoryRegion::allocate(blinkPageSize * blinkPagesPerRegion, blinkPagesPerRegion);
1191197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Setup the PageMemory object for each of the pages in the
1192197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // region.
1193197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        size_t offset = 0;
1194197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        for (size_t i = 0; i < blinkPagesPerRegion; i++) {
1195197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            Heap::freePagePool()->addFreePage(m_index, PageMemory::setupPageMemoryInRegion(region, offset, blinkPagePayloadSize()));
1196197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            offset += blinkPageSize;
1197197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
1198197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        pageMemory = Heap::freePagePool()->takeFreePage(m_index);
119909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
120009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    HeapPage<Header>* page = new (pageMemory->writableStart()) HeapPage<Header>(pageMemory, this, gcInfo);
12019e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // Use a separate list for pages allocated during sweeping to make
12029e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // sure that we do not accidentally sweep objects that have been
12039e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // allocated during sweeping.
12049e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    if (m_threadState->isSweepInProgress()) {
12059e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        if (!m_lastPageAllocatedDuringSweeping)
12069e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            m_lastPageAllocatedDuringSweeping = page;
12079e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        page->link(&m_firstPageAllocatedDuringSweeping);
12089e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    } else {
12099e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        page->link(&m_firstPage);
12109e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    }
12119e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    ++m_numberOfNormalPages;
121209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    addToFreeList(page->payload(), HeapPage<Header>::payloadSize());
121309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
121409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1215197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
121609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
12179e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)bool ThreadHeap<Header>::pagesToBeSweptContains(Address address)
12189e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles){
12199e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    for (HeapPage<Header>* page = m_firstPage; page; page = page->next()) {
12209e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        if (page->contains(address))
12219e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            return true;
12229e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    }
12239e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    return false;
12249e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)}
12259e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)
12269e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)template<typename Header>
12279e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)bool ThreadHeap<Header>::pagesAllocatedDuringSweepingContains(Address address)
12289e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles){
12299e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    for (HeapPage<Header>* page = m_firstPageAllocatedDuringSweeping; page; page = page->next()) {
12309e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        if (page->contains(address))
12319e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            return true;
12329e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    }
12339e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    return false;
12349e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)}
12359e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)
12369e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)template<typename Header>
123709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<Header>::getScannedStats(HeapStats& scannedStats)
123809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
12399e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    ASSERT(!m_firstPageAllocatedDuringSweeping);
124009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
124109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        page->getStats(scannedStats);
124209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next())
124309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        current->getStats(scannedStats);
124409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
124509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
124609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
124709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
12489e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)void ThreadHeap<Header>::sweepNormalPages(HeapStats* stats)
124909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
12507242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    TRACE_EVENT0("blink_gc", "ThreadHeap::sweepNormalPages");
125109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    HeapPage<Header>* page = m_firstPage;
12529e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    HeapPage<Header>** previousNext = &m_firstPage;
12539e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    HeapPage<Header>* previous = 0;
125409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    while (page) {
12557242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        page->resetPromptlyFreedSize();
125609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (page->isEmpty()) {
125709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            HeapPage<Header>* unused = page;
12589e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            if (unused == m_mergePoint)
12599e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)                m_mergePoint = previous;
126009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            page = page->next();
12619e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            HeapPage<Header>::unlink(this, unused, previousNext);
12629e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            --m_numberOfNormalPages;
126309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        } else {
12649e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            page->sweep(stats, this);
12659e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            previousNext = &page->m_next;
12669e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            previous = page;
126709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            page = page->next();
126809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
126909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
12709e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)}
127109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
12729e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)template<typename Header>
12739e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)void ThreadHeap<Header>::sweepLargePages(HeapStats* stats)
12749e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles){
12757242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    TRACE_EVENT0("blink_gc", "ThreadHeap::sweepLargePages");
127609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    LargeHeapObject<Header>** previousNext = &m_firstLargeHeapObject;
127709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current;) {
127809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (current->isMarked()) {
12799e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            stats->increaseAllocatedSpace(current->size());
12809e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            stats->increaseObjectSpace(current->payloadSize());
128109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            current->unmark();
128209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            previousNext = &current->m_next;
128309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            current = current->next();
128409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        } else {
128509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            LargeHeapObject<Header>* next = current->next();
128609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            freeLargeObject(current, previousNext);
128709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            current = next;
128809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
128909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
129009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
129109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
12929e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)
12939e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)// STRICT_ASAN_FINALIZATION_CHECKING turns on poisoning of all objects during
12949e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)// sweeping to catch cases where dead objects touch each other. This is not
12959e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)// turned on by default because it also triggers for cases that are safe.
12969e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)// Examples of such safe cases are context life cycle observers and timers
12979e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)// embedded in garbage collected objects.
12989e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)#define STRICT_ASAN_FINALIZATION_CHECKING 0
12999e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)
13009e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)template<typename Header>
13019e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)void ThreadHeap<Header>::sweep(HeapStats* stats)
13029e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles){
13039e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    ASSERT(isConsistentForSweeping());
13049e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)#if defined(ADDRESS_SANITIZER) && STRICT_ASAN_FINALIZATION_CHECKING
13059e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // When using ASan do a pre-sweep where all unmarked objects are
13069e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // poisoned before calling their finalizer methods. This can catch
13079e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // the case where the finalizer of an object tries to modify
13089e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // another object as part of finalization.
13099e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
13109e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        page->poisonUnmarkedObjects();
13119e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)#endif
13129e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    sweepNormalPages(stats);
13139e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    sweepLargePages(stats);
13149e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)}
13159e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)
13169e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)template<typename Header>
13179e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)void ThreadHeap<Header>::postSweepProcessing()
13189e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles){
13199e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // If pages have been allocated during sweeping, link them into
13209e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // the list of pages.
13219e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    if (m_firstPageAllocatedDuringSweeping) {
13229e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        m_lastPageAllocatedDuringSweeping->m_next = m_firstPage;
13239e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        m_firstPage = m_firstPageAllocatedDuringSweeping;
13249e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        m_lastPageAllocatedDuringSweeping = 0;
13259e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        m_firstPageAllocatedDuringSweeping = 0;
13269e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    }
13279e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)}
13289e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)
13299e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)#if ENABLE(ASSERT)
133009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
13319e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)bool ThreadHeap<Header>::isConsistentForSweeping()
133209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
13339e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // A thread heap is consistent for sweeping if none of the pages to
13349e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // be swept contain a freelist block or the current allocation
13359e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    // point.
133609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (size_t i = 0; i < blinkPageSizeLog2; i++) {
13379e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        for (FreeListEntry* freeListEntry = m_freeLists[i]; freeListEntry; freeListEntry = freeListEntry->next()) {
13389e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            if (pagesToBeSweptContains(freeListEntry->address())) {
13399e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)                return false;
13409e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            }
13419e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            ASSERT(pagesAllocatedDuringSweepingContains(freeListEntry->address()));
13429e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        }
134309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
13449e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    if (ownsNonEmptyAllocationArea()) {
13459e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        ASSERT(pagesToBeSweptContains(currentAllocationPoint())
13469e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            || pagesAllocatedDuringSweepingContains(currentAllocationPoint()));
13479e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        return !pagesToBeSweptContains(currentAllocationPoint());
13489e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    }
13499e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    return true;
135009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
13519e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)#endif
135209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
135309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
13549e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)void ThreadHeap<Header>::makeConsistentForSweeping()
135509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
135609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (ownsNonEmptyAllocationArea())
135709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        addToFreeList(currentAllocationPoint(), remainingAllocationSize());
135809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    setAllocationPoint(0, 0);
135909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    clearFreeLists();
136009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
136109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
136209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
1363197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid ThreadHeap<Header>::clearLiveAndMarkDead()
136409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
13659e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    ASSERT(isConsistentForSweeping());
136609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (HeapPage<Header>* page = m_firstPage; page; page = page->next())
1367197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        page->clearLiveAndMarkDead();
1368197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    for (LargeHeapObject<Header>* current = m_firstLargeHeapObject; current; current = current->next()) {
1369197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (current->isMarked())
1370197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            current->unmark();
1371197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        else
1372197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            current->setDeadMark();
137309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
137409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
137509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
137609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
137709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void ThreadHeap<Header>::clearFreeLists()
137809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
13797242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    m_promptlyFreedCount = 0;
13809e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    for (size_t i = 0; i < blinkPageSizeLog2; i++) {
138109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        m_freeLists[i] = 0;
13829e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        m_lastFreeListEntries[i] = 0;
13839e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    }
138409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
138509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
138609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)int BaseHeap::bucketIndexForSize(size_t size)
138709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
138809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(size > 0);
138909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    int index = -1;
139009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    while (size) {
139109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        size >>= 1;
139209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        index++;
139309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
139409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return index;
139509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
139609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
139709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
139809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)HeapPage<Header>::HeapPage(PageMemory* storage, ThreadHeap<Header>* heap, const GCInfo* gcInfo)
1399d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    : BaseHeapPage(storage, gcInfo, heap->threadState())
140009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    , m_next(0)
140109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
140209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    COMPILE_ASSERT(!(sizeof(HeapPage<Header>) & allocationMask), page_header_incorrectly_aligned);
140309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_objectStartBitMapComputed = false;
140409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(isPageHeaderAddress(reinterpret_cast<Address>(this)));
140509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    heap->stats().increaseAllocatedSpace(blinkPageSize);
140609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
140709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
140809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
140909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapPage<Header>::link(HeapPage** prevNext)
141009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
141109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_next = *prevNext;
141209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    *prevNext = this;
141309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
141409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
141509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
14169e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)void HeapPage<Header>::unlink(ThreadHeap<Header>* heap, HeapPage* unused, HeapPage** prevNext)
141709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
141809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    *prevNext = unused->m_next;
14199e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    heap->removePageFromHeap(unused);
142009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
142109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
142209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
142309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapPage<Header>::getStats(HeapStats& stats)
142409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
142509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    stats.increaseAllocatedSpace(blinkPageSize);
142609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address headerAddress = payload();
142709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(headerAddress != end());
142809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    do {
142909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        Header* header = reinterpret_cast<Header*>(headerAddress);
143009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!header->isFree())
143109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            stats.increaseObjectSpace(header->payloadSize());
143209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(header->size() < blinkPagePayloadSize());
143309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        headerAddress += header->size();
143409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(headerAddress <= end());
143509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    } while (headerAddress < end());
143609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
143709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
143809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
143909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)bool HeapPage<Header>::isEmpty()
144009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
144109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    BasicObjectHeader* header = reinterpret_cast<BasicObjectHeader*>(payload());
144209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return header->isFree() && (header->size() == payloadSize());
144309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
144409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
144509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
14469e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)void HeapPage<Header>::sweep(HeapStats* stats, ThreadHeap<Header>* heap)
144709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
144809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    clearObjectStartBitMap();
14499e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)    stats->increaseAllocatedSpace(blinkPageSize);
145009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address startOfGap = payload();
145109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (Address headerAddress = startOfGap; headerAddress < end(); ) {
145209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        BasicObjectHeader* basicHeader = reinterpret_cast<BasicObjectHeader*>(headerAddress);
1453e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        ASSERT(basicHeader->size() > 0);
145409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(basicHeader->size() < blinkPagePayloadSize());
145509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
145609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (basicHeader->isFree()) {
1457197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            size_t size = basicHeader->size();
1458197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
1459197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // Zero the memory in the free list header to maintain the
1460197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // invariant that memory on the free list is zero filled.
1461197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // The rest of the memory is already on the free list and is
1462197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // therefore already zero filled.
1463197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            if (size < sizeof(FreeListEntry))
1464197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                memset(headerAddress, 0, size);
1465197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            else
1466197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch                memset(headerAddress, 0, sizeof(FreeListEntry));
1467197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
1468197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            headerAddress += size;
146909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            continue;
147009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
147109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // At this point we know this is a valid object of type Header
147209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        Header* header = static_cast<Header*>(basicHeader);
147309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
147409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!header->isMarked()) {
1475197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // For ASan we unpoison the specific object when calling the finalizer and
147609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            // poison it again when done to allow the object's own finalizer to operate
147709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            // on the object, but not have other finalizers be allowed to access it.
147809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            ASAN_UNPOISON_MEMORY_REGION(header->payload(), header->payloadSize());
147909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            finalize(header);
1480197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            size_t size = header->size();
1481197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
1482197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // This memory will be added to the freelist. Maintain the invariant
1483197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            // that memory on the freelist is zero filled.
1484197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            memset(headerAddress, 0, size);
1485197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
148609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            ASAN_POISON_MEMORY_REGION(header->payload(), header->payloadSize());
1487197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            headerAddress += size;
148809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            continue;
148909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
149009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
149109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (startOfGap != headerAddress)
14929e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            heap->addToFreeList(startOfGap, headerAddress - startOfGap);
149309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        header->unmark();
149409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        headerAddress += header->size();
14959e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        stats->increaseObjectSpace(header->payloadSize());
149609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        startOfGap = headerAddress;
149709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
149809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (startOfGap != end())
14999e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        heap->addToFreeList(startOfGap, end() - startOfGap);
150009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
150109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
150209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
1503197021e6b966cfb06891637935ef33fff06433d1Ben Murdochvoid HeapPage<Header>::clearLiveAndMarkDead()
150409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
150509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (Address headerAddress = payload(); headerAddress < end();) {
150609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        Header* header = reinterpret_cast<Header*>(headerAddress);
150709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(header->size() < blinkPagePayloadSize());
1508197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // Check if a free list entry first since we cannot call
1509197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        // isMarked on a free list entry.
1510197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (header->isFree()) {
1511197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            headerAddress += header->size();
1512197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            continue;
1513197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        }
1514197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        if (header->isMarked())
151509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            header->unmark();
1516197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        else
1517197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch            header->setDeadMark();
151809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        headerAddress += header->size();
151909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
152009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
152109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
152209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
152309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapPage<Header>::populateObjectStartBitMap()
152409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
152509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    memset(&m_objectStartBitMap, 0, objectStartBitMapSize);
152609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address start = payload();
152709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (Address headerAddress = start; headerAddress < end();) {
152809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        Header* header = reinterpret_cast<Header*>(headerAddress);
152909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        size_t objectOffset = headerAddress - start;
153009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(!(objectOffset & allocationMask));
153109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        size_t objectStartNumber = objectOffset / allocationGranularity;
153209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        size_t mapIndex = objectStartNumber / 8;
153309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(mapIndex < objectStartBitMapSize);
153409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        m_objectStartBitMap[mapIndex] |= (1 << (objectStartNumber & 7));
153509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        headerAddress += header->size();
153609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(headerAddress <= end());
153709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
153809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_objectStartBitMapComputed = true;
153909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
154009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
154109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
154209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapPage<Header>::clearObjectStartBitMap()
154309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
154409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_objectStartBitMapComputed = false;
154509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
154609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
154709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)static int numberOfLeadingZeroes(uint8_t byte)
154809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
154909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (!byte)
155009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return 8;
155109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    int result = 0;
155209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (byte <= 0x0F) {
155309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        result += 4;
155409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        byte = byte << 4;
155509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
155609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (byte <= 0x3F) {
155709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        result += 2;
155809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        byte = byte << 2;
155909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
156009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (byte <= 0x7F)
156109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        result++;
156209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return result;
156309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
156409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
156509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
1566f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo LiuHeader* HeapPage<Header>::findHeaderFromAddress(Address address)
156709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
1568f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    if (address < payload())
1569f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return 0;
157009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (!isObjectStartBitMapComputed())
157109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        populateObjectStartBitMap();
1572f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    size_t objectOffset = address - payload();
157309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t objectStartNumber = objectOffset / allocationGranularity;
157409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t mapIndex = objectStartNumber / 8;
157509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(mapIndex < objectStartBitMapSize);
157609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t bit = objectStartNumber & 7;
157709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    uint8_t byte = m_objectStartBitMap[mapIndex] & ((1 << (bit + 1)) - 1);
157809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    while (!byte) {
157909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(mapIndex > 0);
158009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        byte = m_objectStartBitMap[--mapIndex];
158109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
158209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    int leadingZeroes = numberOfLeadingZeroes(byte);
158309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    objectStartNumber = (mapIndex * 8) + 7 - leadingZeroes;
158409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    objectOffset = objectStartNumber * allocationGranularity;
158509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address objectAddress = objectOffset + payload();
158609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Header* header = reinterpret_cast<Header*>(objectAddress);
158709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    if (header->isFree())
1588f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return 0;
1589f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    return header;
1590f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu}
1591f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1592f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liutemplate<typename Header>
1593f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)void HeapPage<Header>::checkAndMarkPointer(Visitor* visitor, Address address)
1594f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu{
1595f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    ASSERT(contains(address));
1596f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    Header* header = findHeaderFromAddress(address);
1597197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    if (!header || header->hasDeadMark())
1598f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        return;
159909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1600e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
1601f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    visitor->setHostInfo(&address, "stack");
1602f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
1603e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    if (hasVTable(header) && !vTableInitialized(header->payload())) {
1604e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        visitor->markNoTracing(header);
1605e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        ASSERT(isUninitializedMemory(header->payload(), header->payloadSize()));
1606e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    } else {
1607a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        visitor->mark(header, traceCallback(header));
1608e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
160909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
161009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1611e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
1612f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liutemplate<typename Header>
1613f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liuconst GCInfo* HeapPage<Header>::findGCInfo(Address address)
1614f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu{
1615f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    if (address < payload())
1616f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return 0;
1617f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1618f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    if (gcInfo()) // for non FinalizedObjectHeader
1619f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return gcInfo();
1620f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1621f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    Header* header = findHeaderFromAddress(address);
1622f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    if (!header)
1623f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return 0;
1624f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1625f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    return header->gcInfo();
1626f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu}
1627f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
1628f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1629e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_HEAP)
1630e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)template<typename Header>
1631e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)void HeapPage<Header>::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
1632e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles){
1633e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    Header* header = 0;
1634e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    for (Address addr = payload(); addr < end(); addr += header->size()) {
1635e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        header = reinterpret_cast<Header*>(addr);
1636e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (json)
1637e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            json->pushInteger(header->encodedSize());
1638e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (header->isFree()) {
1639e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            info->freeSize += header->size();
1640e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            continue;
1641e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        }
1642e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
1643e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        const GCInfo* gcinfo = header->gcInfo() ? header->gcInfo() : gcInfo();
1644e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        size_t tag = info->getClassTag(gcinfo);
1645e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        size_t age = header->age();
1646e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (json)
1647e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            json->pushInteger(tag);
1648e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (header->isMarked()) {
1649e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            info->liveCount[tag] += 1;
16509e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            info->liveSize[tag] += header->size();
1651e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            // Count objects that are live when promoted to the final generation.
1652e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            if (age == maxHeapObjectAge - 1)
1653e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)                info->generations[tag][maxHeapObjectAge] += 1;
1654e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            header->incAge();
1655e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        } else {
1656e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            info->deadCount[tag] += 1;
16579e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)            info->deadSize[tag] += header->size();
1658e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            // Count objects that are dead before the final generation.
1659e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            if (age < maxHeapObjectAge)
1660e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)                info->generations[tag][age] += 1;
1661e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        }
1662e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
1663e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)}
1664e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#endif
1665e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
166609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#if defined(ADDRESS_SANITIZER)
166709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
166809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void HeapPage<Header>::poisonUnmarkedObjects()
166909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
167009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (Address headerAddress = payload(); headerAddress < end(); ) {
167109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        Header* header = reinterpret_cast<Header*>(headerAddress);
167209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(header->size() < blinkPagePayloadSize());
167309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
167409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!header->isFree() && !header->isMarked())
167509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            ASAN_POISON_MEMORY_REGION(header->payload(), header->payloadSize());
167609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        headerAddress += header->size();
167709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
167809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
167909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#endif
168009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
168109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
168209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)inline void HeapPage<FinalizedHeapObjectHeader>::finalize(FinalizedHeapObjectHeader* header)
168309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
168409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    header->finalize();
168509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
168609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
168709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
168809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)inline void HeapPage<HeapObjectHeader>::finalize(HeapObjectHeader* header)
168909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
169009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gcInfo());
169109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    HeapObjectHeader::finalize(gcInfo(), header->payload(), header->payloadSize());
169209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
169309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
169409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
169509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)inline TraceCallback HeapPage<HeapObjectHeader>::traceCallback(HeapObjectHeader* header)
169609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
169709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(gcInfo());
169809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return gcInfo()->m_trace;
169909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
170009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
170109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<>
170209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)inline TraceCallback HeapPage<FinalizedHeapObjectHeader>::traceCallback(FinalizedHeapObjectHeader* header)
170309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
170409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return header->traceCallback();
170509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
170609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1707a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdochtemplate<>
1708a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdochinline bool HeapPage<HeapObjectHeader>::hasVTable(HeapObjectHeader* header)
1709a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch{
1710a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    ASSERT(gcInfo());
1711a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    return gcInfo()->hasVTable();
1712a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch}
1713a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
1714a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdochtemplate<>
1715a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdochinline bool HeapPage<FinalizedHeapObjectHeader>::hasVTable(FinalizedHeapObjectHeader* header)
1716a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch{
1717a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch    return header->hasVTable();
1718a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch}
1719a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
172009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)template<typename Header>
172109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void LargeHeapObject<Header>::getStats(HeapStats& stats)
172209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
172309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    stats.increaseAllocatedSpace(size());
172409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    stats.increaseObjectSpace(payloadSize());
172509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
172609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1727e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_HEAP)
1728e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)template<typename Header>
1729e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)void LargeHeapObject<Header>::snapshot(TracedValue* json, ThreadState::SnapshotInfo* info)
1730e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles){
1731e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    Header* header = heapObjectHeader();
1732e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    size_t tag = info->getClassTag(header->gcInfo());
1733e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    size_t age = header->age();
1734e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    if (isMarked()) {
1735e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        info->liveCount[tag] += 1;
17369e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        info->liveSize[tag] += header->size();
1737e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        // Count objects that are live when promoted to the final generation.
1738e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (age == maxHeapObjectAge - 1)
1739e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            info->generations[tag][maxHeapObjectAge] += 1;
1740e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        header->incAge();
1741e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    } else {
1742e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        info->deadCount[tag] += 1;
17439e12abdf8c3a23d52091ea54ebb6a04d327f9300Torne (Richard Coles)        info->deadSize[tag] += header->size();
1744e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        // Count objects that are dead before the final generation.
1745e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        if (age < maxHeapObjectAge)
1746e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)            info->generations[tag][age] += 1;
1747e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
1748e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
1749e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    if (json) {
1750e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        json->setInteger("class", tag);
1751e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        json->setInteger("size", header->size());
1752e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)        json->setInteger("isMarked", isMarked());
1753e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)    }
1754e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)}
1755e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#endif
1756e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)
1757f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)template<typename Entry>
1758f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)void HeapExtentCache<Entry>::flush()
175909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
1760f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    if (m_hasEntries) {
1761f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        for (int i = 0; i < numberOfEntries; i++)
1762f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)            m_entries[i] = Entry();
1763f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        m_hasEntries = false;
1764f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    }
176509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
176609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1767f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)template<typename Entry>
1768f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)size_t HeapExtentCache<Entry>::hash(Address address)
176909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
177009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t value = (reinterpret_cast<size_t>(address) >> blinkPageSizeLog2);
177109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    value ^= value >> numberOfEntriesLog2;
177209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    value ^= value >> (numberOfEntriesLog2 * 2);
177309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    value &= numberOfEntries - 1;
177409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return value & ~1; // Returns only even number.
177509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
177609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1777f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)template<typename Entry>
1778f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)typename Entry::LookupResult HeapExtentCache<Entry>::lookup(Address address)
177909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
178009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t index = hash(address);
178109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(!(index & 1));
178209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address cachePage = roundToBlinkPageStart(address);
1783f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    if (m_entries[index].address() == cachePage)
1784f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        return m_entries[index].result();
1785f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    if (m_entries[index + 1].address() == cachePage)
1786f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        return m_entries[index + 1].result();
1787f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    return 0;
178809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
178909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1790f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)template<typename Entry>
1791f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)void HeapExtentCache<Entry>::addEntry(Address address, typename Entry::LookupResult entry)
179209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
1793f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    m_hasEntries = true;
179409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    size_t index = hash(address);
179509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(!(index & 1));
179609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    Address cachePage = roundToBlinkPageStart(address);
179709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    m_entries[index + 1] = m_entries[index];
1798f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    m_entries[index] = Entry(cachePage, entry);
1799f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)}
1800f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)
1801f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)// These should not be needed, but it seems impossible to persuade clang to
1802f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)// instantiate the template functions and export them from a shared library, so
1803f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)// we add these in the non-templated subclass, which does not have that issue.
1804f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)void HeapContainsCache::addEntry(Address address, BaseHeapPage* page)
1805f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles){
1806f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    HeapExtentCache<PositiveEntry>::addEntry(address, page);
1807f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)}
1808f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)
1809f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)BaseHeapPage* HeapContainsCache::lookup(Address address)
1810f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles){
1811f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    return HeapExtentCache<PositiveEntry>::lookup(address);
1812f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)}
1813f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)
1814f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)void Heap::flushHeapDoesNotContainCache()
1815f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles){
1816f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    s_heapDoesNotContainCache->flush();
181709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
181809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
18197242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci// The marking mutex is used to ensure sequential access to data
18207242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci// structures during marking. The marking mutex needs to be acquired
18217242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci// during marking when elements are taken from the global marking
18227242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci// stack or when elements are added to the global ephemeron,
18237242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci// post-marking, and weak processing stacks. In debug mode the mutex
18247242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci// also needs to be acquired when asserts use the heap contains
18257242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci// caches.
18267242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccistatic Mutex& markingMutex()
182709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
18287242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
18297242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return mutex;
183009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
183109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
18327242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccistatic ThreadCondition& markingCondition()
183309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
18347242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    AtomicallyInitializedStatic(ThreadCondition&, condition = *new ThreadCondition);
18357242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return condition;
183609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
183709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
18387242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccistatic void markNoTracingCallback(Visitor* visitor, void* object)
183909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
18407242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    visitor->markNoTracing(object);
184109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
184209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
184309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)class MarkingVisitor : public Visitor {
184409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)public:
1845e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
1846f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    typedef HashSet<uintptr_t> LiveObjectSet;
1847f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    typedef HashMap<String, LiveObjectSet> LiveObjectMap;
1848f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    typedef HashMap<uintptr_t, std::pair<uintptr_t, String> > ObjectGraph;
1849f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
1850f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
18517242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    MarkingVisitor(CallbackStack* markingStack) : m_markingStack(markingStack)
18527242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    {
18537242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
18547242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
185509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    inline void visitHeader(HeapObjectHeader* header, const void* objectPointer, TraceCallback callback)
185609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
185709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(header);
18587242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#if ENABLE(ASSERT)
18597242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        {
18607242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            // Check that we are not marking objects that are outside
18617242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            // the heap by calling Heap::contains. However we cannot
18627242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            // call Heap::contains when outside a GC and we call mark
18637242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            // when doing weakness for ephemerons. Hence we only check
18647242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            // when called within.
18657242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            MutexLocker locker(markingMutex());
18667242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            ASSERT(!ThreadState::isAnyThreadInGC() || Heap::containedInHeapOrOrphanedPage(header));
18677242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        }
18687242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#endif
186909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        ASSERT(objectPointer);
187009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (header->isMarked())
187109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return;
187209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        header->mark();
1873e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
1874f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        MutexLocker locker(objectGraphMutex());
1875f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        String className(classOf(objectPointer));
1876f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        {
1877f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            LiveObjectMap::AddResult result = currentlyLive().add(className, LiveObjectSet());
1878f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            result.storedValue->value.add(reinterpret_cast<uintptr_t>(objectPointer));
1879f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        }
1880f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        ObjectGraph::AddResult result = objectGraph().add(reinterpret_cast<uintptr_t>(objectPointer), std::make_pair(reinterpret_cast<uintptr_t>(m_hostObject), m_hostName));
1881f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        ASSERT(result.isNewEntry);
1882f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        // fprintf(stderr, "%s[%p] -> %s[%p]\n", m_hostName.ascii().data(), m_hostObject, className.ascii().data(), objectPointer);
1883f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
188409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (callback)
18857242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            Heap::pushTraceCallback(m_markingStack, const_cast<void*>(objectPointer), callback);
188609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
188709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
188809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    virtual void mark(HeapObjectHeader* header, TraceCallback callback) OVERRIDE
188909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
189009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // We need both the HeapObjectHeader and FinalizedHeapObjectHeader
189109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // version to correctly find the payload.
189209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        visitHeader(header, header->payload(), callback);
189309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
189409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
189509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    virtual void mark(FinalizedHeapObjectHeader* header, TraceCallback callback) OVERRIDE
189609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
189709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // We need both the HeapObjectHeader and FinalizedHeapObjectHeader
189809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        // version to correctly find the payload.
189909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        visitHeader(header, header->payload(), callback);
190009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
190109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
190209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    virtual void mark(const void* objectPointer, TraceCallback callback) OVERRIDE
190309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
190409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!objectPointer)
190509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return;
190609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        FinalizedHeapObjectHeader* header = FinalizedHeapObjectHeader::fromPayload(objectPointer);
190709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        visitHeader(header, header->payload(), callback);
190809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
190909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
19107242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    virtual void registerDelayedMarkNoTracing(const void* object) OVERRIDE
19117242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    {
19127242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        Heap::pushPostMarkingCallback(const_cast<void*>(object), markNoTracingCallback);
19137242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
19147242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
1915d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    virtual void registerWeakMembers(const void* closure, const void* containingObject, WeakPointerCallback callback) OVERRIDE
191609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
1917d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)        Heap::pushWeakObjectPointerCallback(const_cast<void*>(closure), const_cast<void*>(containingObject), callback);
191809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
191909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
1920197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    virtual void registerWeakTable(const void* closure, EphemeronCallback iterationCallback, EphemeronCallback iterationDoneCallback)
1921197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    {
1922197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        Heap::registerWeakTable(const_cast<void*>(closure), iterationCallback, iterationDoneCallback);
1923197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1924197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
1925197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
1926197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    virtual bool weakTableRegistered(const void* closure)
1927197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    {
1928197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch        return Heap::weakTableRegistered(closure);
1929197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    }
1930197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
1931197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
193209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    virtual bool isMarked(const void* objectPointer) OVERRIDE
193309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {
193409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return FinalizedHeapObjectHeader::fromPayload(objectPointer)->isMarked();
193509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
193609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
193709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    // This macro defines the necessary visitor methods for typed heaps
193809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#define DEFINE_VISITOR_METHODS(Type)                                              \
193909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    virtual void mark(const Type* objectPointer, TraceCallback callback) OVERRIDE \
194009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {                                                                             \
194109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if (!objectPointer)                                                       \
194209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return;                                                               \
194309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        HeapObjectHeader* header =                                                \
194409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            HeapObjectHeader::fromPayload(objectPointer);                         \
194509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        visitHeader(header, header->payload(), callback);                         \
194609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }                                                                             \
194709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    virtual bool isMarked(const Type* objectPointer) OVERRIDE                     \
194809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    {                                                                             \
194909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        return HeapObjectHeader::fromPayload(objectPointer)->isMarked();          \
195009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
195109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
195209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    FOR_EACH_TYPED_HEAP(DEFINE_VISITOR_METHODS)
195309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)#undef DEFINE_VISITOR_METHODS
1954d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)
1955e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
1956f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    void reportStats()
1957f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
1958f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        fprintf(stderr, "\n---------- AFTER MARKING -------------------\n");
1959f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        for (LiveObjectMap::iterator it = currentlyLive().begin(), end = currentlyLive().end(); it != end; ++it) {
1960f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            fprintf(stderr, "%s %u", it->key.ascii().data(), it->value.size());
1961f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1962c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)            if (it->key == "blink::Document")
1963f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu                reportStillAlive(it->value, previouslyLive().get(it->key));
1964f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1965f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            fprintf(stderr, "\n");
1966f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        }
1967f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1968f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        previouslyLive().swap(currentlyLive());
1969f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        currentlyLive().clear();
1970f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1971f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        for (HashSet<uintptr_t>::iterator it = objectsToFindPath().begin(), end = objectsToFindPath().end(); it != end; ++it) {
1972f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            dumpPathToObjectFromObjectGraph(objectGraph(), *it);
1973f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        }
1974f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
1975f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1976f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static void reportStillAlive(LiveObjectSet current, LiveObjectSet previous)
1977f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
1978f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        int count = 0;
1979f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1980f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        fprintf(stderr, " [previously %u]", previous.size());
1981f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        for (LiveObjectSet::iterator it = current.begin(), end = current.end(); it != end; ++it) {
1982f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            if (previous.find(*it) == previous.end())
1983f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu                continue;
1984f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            count++;
1985f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        }
1986f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1987f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        if (!count)
1988f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            return;
1989f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
1990f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        fprintf(stderr, " {survived 2GCs %d: ", count);
1991f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        for (LiveObjectSet::iterator it = current.begin(), end = current.end(); it != end; ++it) {
1992f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            if (previous.find(*it) == previous.end())
1993f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu                continue;
1994f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)            fprintf(stderr, "%ld", *it);
1995f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            if (--count)
1996f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)                fprintf(stderr, ", ");
1997f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        }
1998f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        ASSERT(!count);
1999f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        fprintf(stderr, "}");
2000f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
2001f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2002f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static void dumpPathToObjectFromObjectGraph(const ObjectGraph& graph, uintptr_t target)
2003f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
2004f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        ObjectGraph::const_iterator it = graph.find(target);
20055d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        if (it == graph.end())
20065d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            return;
20075d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        fprintf(stderr, "Path to %lx of %s\n", target, classOf(reinterpret_cast<const void*>(target)).ascii().data());
2008f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        while (it != graph.end()) {
20095d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            fprintf(stderr, "<- %lx of %s\n", it->value.first, it->value.second.utf8().data());
2010f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu            it = graph.find(it->value.first);
2011f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        }
2012f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        fprintf(stderr, "\n");
2013f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
2014f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2015f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static void dumpPathToObjectOnNextGC(void* p)
2016f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
2017f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        objectsToFindPath().add(reinterpret_cast<uintptr_t>(p));
2018f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
2019f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2020f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    static Mutex& objectGraphMutex()
2021f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    {
2022f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        AtomicallyInitializedStatic(Mutex&, mutex = *new Mutex);
2023f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)        return mutex;
2024f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)    }
2025f6b7aed3f7ce69aca0d7a032d144cbd088b04393Torne (Richard Coles)
2026f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static LiveObjectMap& previouslyLive()
2027f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
2028f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        DEFINE_STATIC_LOCAL(LiveObjectMap, map, ());
2029f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return map;
2030f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
2031f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2032f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static LiveObjectMap& currentlyLive()
2033f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
2034f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        DEFINE_STATIC_LOCAL(LiveObjectMap, map, ());
2035f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return map;
2036f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
2037f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2038f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static ObjectGraph& objectGraph()
2039f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
2040f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        DEFINE_STATIC_LOCAL(ObjectGraph, graph, ());
2041f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return graph;
2042f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
2043f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2044f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static HashSet<uintptr_t>& objectsToFindPath()
2045f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    {
2046f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        DEFINE_STATIC_LOCAL(HashSet<uintptr_t>, set, ());
2047f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu        return set;
2048f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    }
2049f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
2050f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2051d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)protected:
2052d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    virtual void registerWeakCell(void** cell, WeakPointerCallback callback) OVERRIDE
2053d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    {
2054d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)        Heap::pushWeakCellPointerCallback(cell, callback);
2055d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    }
20567242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
20577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucciprivate:
20587242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    CallbackStack* m_markingStack;
205909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)};
206009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
206109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)void Heap::init()
206209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
206309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ThreadState::init();
20647242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_markingStack = new CallbackStack();
20657242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_postMarkingCallbackStack = new CallbackStack();
20667242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_weakCallbackStack = new CallbackStack();
20677242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_ephemeronStack = new CallbackStack();
2068f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    s_heapDoesNotContainCache = new HeapDoesNotContainCache();
20697242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_markingVisitor = new MarkingVisitor(s_markingStack);
2070197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    s_freePagePool = new FreePagePool();
2071197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    s_orphanedPagePool = new OrphanedPagePool();
20727242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_markingThreads = new Vector<OwnPtr<blink::WebThread> >();
20737242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (blink::Platform::current()) {
20747242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // FIXME: We should let the amount of threads scale with the
20757242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // amount of processors in the system instead of hardcoding
20767242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // it.
20777242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        for (int i = 0; i < numberOfMarkingThreads; i++)
20787242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci            s_markingThreads->append(adoptPtr(blink::Platform::current()->createThread("Blink Heap Marker Thread")));
20797242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
208009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
208109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
2082a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles)void Heap::shutdown()
2083a854de003a23bf3c7f95ec0f8154ada64092ff5cTorne (Richard Coles){
208410f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch    s_shutdownCalled = true;
208510f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch    ThreadState::shutdownHeapIfNecessary();
20866f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch}
20876f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch
208810f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdochvoid Heap::doShutdown()
20896f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch{
209010f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch    // We don't want to call doShutdown() twice.
209110f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch    if (!s_markingVisitor)
209210f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch        return;
209310f88d5669dbd969c059d61ba09fa37dd72ac559Ben Murdoch
20946f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch    ASSERT(!ThreadState::isAnyThreadInGC());
20956f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch    ASSERT(!ThreadState::attachedThreads().size());
20967242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    delete s_markingThreads;
20977242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_markingThreads = 0;
2098d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    delete s_markingVisitor;
20996f543c786fc42989f552b4daa774ca5ff32fa697Ben Murdoch    s_markingVisitor = 0;
2100f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    delete s_heapDoesNotContainCache;
2101f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    s_heapDoesNotContainCache = 0;
2102197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    delete s_freePagePool;
2103197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    s_freePagePool = 0;
2104197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    delete s_orphanedPagePool;
2105197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    s_orphanedPagePool = 0;
21067242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    delete s_weakCallbackStack;
21077242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_weakCallbackStack = 0;
21087242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    delete s_postMarkingCallbackStack;
21097242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_postMarkingCallbackStack = 0;
21107242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    delete s_markingStack;
21117242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_markingStack = 0;
21127242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    delete s_ephemeronStack;
21137242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    s_ephemeronStack = 0;
2114d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    ThreadState::shutdown();
211509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
211609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
2117d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)BaseHeapPage* Heap::contains(Address address)
211809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
211909380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(ThreadState::isAnyThreadInGC());
212009380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
212109380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
2122d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)        BaseHeapPage* page = (*it)->contains(address);
2123d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)        if (page)
2124d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)            return page;
212509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
2126d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)    return 0;
212709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
212809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
2129197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if ENABLE(ASSERT)
2130197021e6b966cfb06891637935ef33fff06433d1Ben Murdochbool Heap::containedInHeapOrOrphanedPage(void* object)
2131197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch{
2132197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch    return contains(object) || orphanedPagePool()->contains(object);
2133197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch}
2134197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#endif
2135197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch
213609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)Address Heap::checkAndMarkPointer(Visitor* visitor, Address address)
213709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
213809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ASSERT(ThreadState::isAnyThreadInGC());
2139f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)
2140197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(ASSERT)
2141f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    if (s_heapDoesNotContainCache->lookup(address))
2142a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch        return 0;
2143f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)#endif
2144a9984bf9ddc3cf73fdae3f29134a2bab379e7029Ben Murdoch
214509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    ThreadState::AttachedThreadStateSet& threads = ThreadState::attachedThreads();
214609380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    for (ThreadState::AttachedThreadStateSet::iterator it = threads.begin(), end = threads.end(); it != end; ++it) {
214709380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        if ((*it)->checkAndMarkPointer(visitor, address)) {
2148f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)            // Pointer was in a page of that thread. If it actually pointed
2149f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)            // into an object then that object was found and marked.
2150f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)            ASSERT(!s_heapDoesNotContainCache->lookup(address));
2151d6cdb82654e8f3343a693ca752d5c4cee0324e17Torne (Richard Coles)            s_lastGCWasConservative = true;
215209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)            return address;
215309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)        }
215409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    }
2155f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)
2156197021e6b966cfb06891637935ef33fff06433d1Ben Murdoch#if !ENABLE(ASSERT)
2157f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    s_heapDoesNotContainCache->addEntry(address, true);
2158f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)#else
2159f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)    if (!s_heapDoesNotContainCache->lookup(address))
2160f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)        s_heapDoesNotContainCache->addEntry(address, true);
2161f523d2789ac2f83c4eca0ee4d5161bfdb5f2d052Torne (Richard Coles)#endif
216209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    return 0;
216309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
216409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
2165e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
2166f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liuconst GCInfo* Heap::findGCInfo(Address address)
2167f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu{
21685d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    return ThreadState::findGCInfoFromAllThreads(address);
2169f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu}
2170e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#endif
2171f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
2172e38fbeeb576b5094e34e038ab88d9d6a5c5c2214Torne (Richard Coles)#if ENABLE(GC_PROFILE_MARKING)
2173f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liuvoid Heap::dumpPathToObjectOnNextGC(void* p)
2174f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu{
2175f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu    static_cast<MarkingVisitor*>(s_markingVisitor)->dumpPathToObjectOnNextGC(p);
2176f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu}
21775d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
21785d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)String Heap::createBacktraceString()
21795d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles){
21805d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    int framesToShow = 3;
21815d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    int stackFrameSize = 16;
21825d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    ASSERT(stackFrameSize >= framesToShow);
21835d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    typedef void* FramePointer;
21845d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    FramePointer* stackFrame = static_cast<FramePointer*>(alloca(sizeof(FramePointer) * stackFrameSize));
21855d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    WTFGetBacktrace(stackFrame, &stackFrameSize);
21865d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)
21875d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    StringBuilder builder;
21885d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    builder.append("Persistent");
21895d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    bool didAppendFirstName = false;
2190c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    // Skip frames before/including "blink::Persistent".
21915d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    bool didSeePersistent = false;
21925d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    for (int i = 0; i < stackFrameSize && framesToShow > 0; ++i) {
21935d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        FrameToNameScope frameToName(stackFrame[i]);
21945d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        if (!frameToName.nullableName())
21955d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            continue;
2196c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)        if (strstr(frameToName.nullableName(), "blink::Persistent")) {
21975d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            didSeePersistent = true;
21985d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            continue;
21995d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        }
22005d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        if (!didSeePersistent)
22015d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            continue;
22025d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        if (!didAppendFirstName) {
22035d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            didAppendFirstName = true;
22045d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)            builder.append(" ... Backtrace:");
22055d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        }
22065d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        builder.append("\n\t");
22075d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        builder.append(frameToName.nullableName());
22085d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)        --framesToShow;
22095d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)    }
2210c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)    return builder.toString().replace("blink::", "");
22115d92fedcae5e801a8b224de090094f2d9df0b54aTorne (Richard Coles)}
2212f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu#endif
2213f91f5fa1608c2cdd9af1842fb5dadbe78275be2aBo Liu
22147242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccivoid Heap::pushTraceCallback(CallbackStack* stack, void* object, TraceCallback callback)
221509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
22167242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#if ENABLE(ASSERT)
22177242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    {
22187242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        MutexLocker locker(markingMutex());
22197242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        ASSERT(Heap::containedInHeapOrOrphanedPage(object));
22207242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
22217242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#endif
22227242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    CallbackStack::Item* slot = stack->allocateEntry();
222309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)    *slot = CallbackStack::Item(object, callback);
222409380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
222509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
2226197021e6b966cfb06891637935ef33fff06433d1Ben Murdochtemplate<CallbackInvocationMode Mode>
22277242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccibool Heap::popAndInvokeTraceCallback(CallbackStack* stack, Visitor* visitor)
222809380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
22297242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    CallbackStack::Item* item = stack->pop();
22307242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (!item)
22317242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return false;
22327242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // If the object being traced is located on a page which is dead don't
22337242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // trace it. This can happen when a conservative GC kept a dead object
22347242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // alive which pointed to a (now gone) object on the cleaned up page.
22357242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // Also, if doing a thread local GC, don't trace objects that are located
22367242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    // on other thread's heaps, ie, pages where the terminating flag is not set.
22377242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    BaseHeapPage* heapPage = pageHeaderFromObject(item->object());
22387242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (Mode == GlobalMarking && heapPage->orphaned()) {
22397242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // When doing a global GC we should only get a trace callback to an orphaned
22407242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // page if the GC is conservative. If it is not conservative there is
22417242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // a bug in the code where we have a dangling pointer to a page
22427242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        // on the dead thread.
22437242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        RELEASE_ASSERT(Heap::lastGCWasConservative());
22447242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        heapPage->setTracedAfterOrphaned();
22457242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return true;
22467242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
22477242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (Mode == ThreadLocalMarking && (heapPage->orphaned() || !heapPage->terminating()))
22487242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return true;
22497242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
22507242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#if ENABLE(GC_PROFILE_MARKING)
22517242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    visitor->setHostInfo(item->object(), classOf(item->object()));
22527242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci#endif
22537242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    item->call(visitor);
22547242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return true;
22557242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci}
22567242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
22577242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccivoid Heap::pushPostMarkingCallback(void* object, TraceCallback callback)
22587242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci{
22597242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    MutexLocker locker(markingMutex());
22607242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    ASSERT(!Heap::orphanedPagePool()->contains(object));
22617242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    CallbackStack::Item* slot = s_postMarkingCallbackStack->allocateEntry();
22627242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    *slot = CallbackStack::Item(object, callback);
22637242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci}
22647242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci
22657242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tuccibool Heap::popAndInvokePostMarkingCallback(Visitor* visitor)
22667242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci{
22677242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    if (CallbackStack::Item* item = s_postMarkingCallbackStack->pop()) {
22687242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        item->call(visitor);
22697242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci        return true;
22707242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    }
22717242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    return false;
227209380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)}
227309380295ba73501a205346becac22c6978e4671dTorne (Richard Coles)
2274d5428f32f5d1719f774f62e19147104ca245a3abTorne (Richard Coles)void Heap::pushWeakCellPointerCallback(void** cell, WeakPointerCallback callback)
227509380295ba73501a205346becac22c6978e4671dTorne (Richard Coles){
22767242dc3dbeb210b5e876a3c42d1ec1a667fc621aPrimiano Tucci    MutexLocker locker(markingMutex());
2277