collector.cpp

linux下开源浏览器WebKit的源码,市面上的很多商用浏览器都是移植自WebKit

/*
 *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
 *  Copyright (C) 2007 Eric Seidel <[e-mail]>
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License as published by the Free Software Foundation; either
 *  version 2 of the License, or (at your option) any later version.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 */

#include "config.h"
#include "Collector.h"

#include "ArgList.h"
#include "CallFrame.h"
#include "CollectorHeapIterator.h"
#include "Interpreter.h"
#include "JSGlobalObject.h"
#include "JSLock.h"
#include "JSString.h"
#include "JSValue.h"
#include "Nodes.h"
#include "Tracing.h"
#include <algorithm>
#include <setjmp.h>
#include <stdlib.h>
#include <wtf/FastMalloc.h>
#include <wtf/HashCountedSet.h>
#include <wtf/UnusedParam.h>

#if PLATFORM(DARWIN)

#include <mach/mach_port.h>
#include <mach/mach_init.h>
#include <mach/task.h>
#include <mach/thread_act.h>
#include <mach/vm_map.h>

#elif PLATFORM(WIN_OS)

#include <windows.h>

#elif PLATFORM(UNIX)

#include <stdlib.h>
#include <sys/mman.h>
#include <unistd.h>

#if PLATFORM(SOLARIS)
#include <thread.h>
#endif

#if PLATFORM(OPENBSD)
#include <pthread.h>
#endif

#if HAVE(PTHREAD_NP_H)
#include <pthread_np.h>
#endif

#endif

#define DEBUG_COLLECTOR 0
#define COLLECT_ON_EVERY_ALLOCATION 0

using std::max;

namespace JSC {

// tunable parameters

const size_t SPARE_EMPTY_BLOCKS = 2;
const size_t GROWTH_FACTOR = 2;
const size_t LOW_WATER_FACTOR = 4;
const size_t ALLOCATIONS_PER_COLLECTION = 4000;
// This value has to be a macro to be used in max() without introducing
// a PIC branch in Mach-O binaries, see <rdar://problem/5971391>.
#define MIN_ARRAY_SIZE (static_cast<size_t>(14))

static void freeHeap(CollectorHeap*);

#if ENABLE(JSC_MULTIPLE_THREADS)

#if PLATFORM(DARWIN)
typedef mach_port_t PlatformThread;
#elif PLATFORM(WIN_OS)
struct PlatformThread {
    PlatformThread(DWORD _id, HANDLE _handle) : id(_id), handle(_handle) {}
    DWORD id;
    HANDLE handle;
};
#endif

class Heap::Thread {
public:
    Thread(pthread_t pthread, const PlatformThread& platThread, void* base) 
        : posixThread(pthread)
        , platformThread(platThread)
        , stackBase(base)
    {
    }

    Thread* next;
    pthread_t posixThread;
    PlatformThread platformThread;
    void* stackBase;
};

#endif

Heap::Heap(JSGlobalData* globalData)
    : m_markListSet(0)
#if ENABLE(JSC_MULTIPLE_THREADS)
    , m_registeredThreads(0)
    , m_currentThreadRegistrar(0)
#endif
    , m_globalData(globalData)
{
    ASSERT(globalData);

    memset(&primaryHeap, 0, sizeof(CollectorHeap));
    memset(&numberHeap, 0, sizeof(CollectorHeap));
}

Heap::~Heap()
{
    // The destroy function must already have been called, so assert this.
    ASSERT(!m_globalData);
}

void Heap::destroy()
{
    JSLock lock(false);

    if (!m_globalData)
        return;

    // The global object is not GC protected at this point, so sweeping may delete it
    // (and thus the global data) before other objects that may use the global data.
    RefPtr<JSGlobalData> protect(m_globalData);

    delete m_markListSet;
    m_markListSet = 0;

    sweep<PrimaryHeap>();
    // No need to sweep number heap, because the JSNumber destructor doesn't do anything.

    ASSERT(!primaryHeap.numLiveObjects);

    freeHeap(&primaryHeap);
    freeHeap(&numberHeap);

#if ENABLE(JSC_MULTIPLE_THREADS)
    if (m_currentThreadRegistrar) {
        int error = pthread_key_delete(m_currentThreadRegistrar);
        ASSERT_UNUSED(error, !error);
    }

    MutexLocker registeredThreadsLock(m_registeredThreadsMutex);
    for (Heap::Thread* t = m_registeredThreads; t;) {
        Heap::Thread* next = t->next;
        delete t;
        t = next;
    }
#endif

    m_globalData = 0;
}

template <HeapType heapType>
static NEVER_INLINE CollectorBlock* allocateBlock()
{
#if PLATFORM(DARWIN)
    vm_address_t address = 0;
    // FIXME: tag the region as a JavaScriptCore heap when we get a registered VM tag: <rdar://problem/6054788>.
    vm_map(current_task(), &address, BLOCK_SIZE, BLOCK_OFFSET_MASK, VM_FLAGS_ANYWHERE, MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_DEFAULT, VM_INHERIT_DEFAULT);
#elif PLATFORM(SYMBIAN)
    // no memory map in symbian, need to hack with fastMalloc
    void* address = fastMalloc(BLOCK_SIZE);
    memset(reinterpret_cast<void*>(address), 0, BLOCK_SIZE);
#elif PLATFORM(WIN_OS)
     // windows virtual address granularity is naturally 64k
    LPVOID address = VirtualAlloc(NULL, BLOCK_SIZE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#elif HAVE(POSIX_MEMALIGN)
    void* address;
    posix_memalign(&address, BLOCK_SIZE, BLOCK_SIZE);
    memset(address, 0, BLOCK_SIZE);
#else

#if ENABLE(JSC_MULTIPLE_THREADS)
#error Need to initialize pagesize safely.
#endif
    static size_t pagesize = getpagesize();

    size_t extra = 0;
    if (BLOCK_SIZE > pagesize)
        extra = BLOCK_SIZE - pagesize;

    void* mmapResult = mmap(NULL, BLOCK_SIZE + extra, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANON, -1, 0);
    uintptr_t address = reinterpret_cast<uintptr_t>(mmapResult);

    size_t adjust = 0;
    if ((address & BLOCK_OFFSET_MASK) != 0)
        adjust = BLOCK_SIZE - (address & BLOCK_OFFSET_MASK);

    if (adjust > 0)
        munmap(reinterpret_cast<char*>(address), adjust);

    if (adjust < extra)
        munmap(reinterpret_cast<char*>(address + adjust + BLOCK_SIZE), extra - adjust);

    address += adjust;
    memset(reinterpret_cast<void*>(address), 0, BLOCK_SIZE);
#endif
    reinterpret_cast<CollectorBlock*>(address)->type = heapType;
    return reinterpret_cast<CollectorBlock*>(address);
}

static void freeBlock(CollectorBlock* block)
{
#if PLATFORM(DARWIN)    
    vm_deallocate(current_task(), reinterpret_cast<vm_address_t>(block), BLOCK_SIZE);
#elif PLATFORM(SYMBIAN)
    fastFree(block);
#elif PLATFORM(WIN_OS)
    VirtualFree(block, 0, MEM_RELEASE);
#elif HAVE(POSIX_MEMALIGN)
    free(block);
#else
    munmap(reinterpret_cast<char*>(block), BLOCK_SIZE);
#endif
}

static void freeHeap(CollectorHeap* heap)
{
    for (size_t i = 0; i < heap->usedBlocks; ++i)
        if (heap->blocks[i])
            freeBlock(heap->blocks[i]);
    fastFree(heap->blocks);
    memset(heap, 0, sizeof(CollectorHeap));
}

void Heap::recordExtraCost(size_t cost)
{
    // Our frequency of garbage collection tries to balance memory use against speed
    // by collecting based on the number of newly created values. However, for values
    // that hold on to a great deal of memory that's not in the form of other JS values,
    // that is not good enough - in some cases a lot of those objects can pile up and
    // use crazy amounts of memory without a GC happening. So we track these extra
    // memory costs. Only unusually large objects are noted, and we only keep track
    // of this extra cost until the next GC. In garbage collected languages, most values
    // are either very short lived temporaries, or have extremely long lifetimes. So
    // if a large value survives one garbage collection, there is not much point to
    // collecting more frequently as long as it stays alive.
    // NOTE: we target the primaryHeap unconditionally as JSNumber doesn't modify cost 

    primaryHeap.extraCost += cost;
}

template <HeapType heapType> ALWAYS_INLINE void* Heap::heapAllocate(size_t s)
{
    typedef typename HeapConstants<heapType>::Block Block;
    typedef typename HeapConstants<heapType>::Cell Cell;

    CollectorHeap& heap = heapType == PrimaryHeap ? primaryHeap : numberHeap;
    ASSERT(JSLock::lockCount() > 0);
    ASSERT(JSLock::currentThreadIsHoldingLock());
    ASSERT_UNUSED(s, s <= HeapConstants<heapType>::cellSize);

    ASSERT(heap.operationInProgress == NoOperation);
    ASSERT(heapType == PrimaryHeap || heap.extraCost == 0);
    // FIXME: If another global variable access here doesn't hurt performance
    // too much, we could CRASH() in NDEBUG builds, which could help ensure we
    // don't spend any time debugging cases where we allocate inside an object's
    // deallocation code.

#if COLLECT_ON_EVERY_ALLOCATION
    collect();
#endif

    size_t numLiveObjects = heap.numLiveObjects;
    size_t usedBlocks = heap.usedBlocks;
    size_t i = heap.firstBlockWithPossibleSpace;

    // if we have a huge amount of extra cost, we'll try to collect even if we still have
    // free cells left.
    if (heapType == PrimaryHeap && heap.extraCost > ALLOCATIONS_PER_COLLECTION) {
        size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
        size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
        const size_t newCost = numNewObjects + heap.extraCost;
        if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect)
            goto collect;
    }

    ASSERT(heap.operationInProgress == NoOperation);
#ifndef NDEBUG
    // FIXME: Consider doing this in NDEBUG builds too (see comment above).
    heap.operationInProgress = Allocation;
#endif

scan:
    Block* targetBlock;
    size_t targetBlockUsedCells;
    if (i != usedBlocks) {
        targetBlock = reinterpret_cast<Block*>(heap.blocks[i]);
        targetBlockUsedCells = targetBlock->usedCells;
        ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
        while (targetBlockUsedCells == HeapConstants<heapType>::cellsPerBlock) {
            if (++i == usedBlocks)
                goto collect;
            targetBlock = reinterpret_cast<Block*>(heap.blocks[i]);
            targetBlockUsedCells = targetBlock->usedCells;
            ASSERT(targetBlockUsedCells <= HeapConstants<heapType>::cellsPerBlock);
        }
        heap.firstBlockWithPossibleSpace = i;
    } else {

collect:
        size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;
        size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;
        const size_t newCost = numNewObjects + heap.extraCost;

        if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect) {
#ifndef NDEBUG
            heap.operationInProgress = NoOperation;
#endif
            bool collected = collect();
#ifndef NDEBUG
            heap.operationInProgress = Allocation;
#endif
            if (collected) {
                numLiveObjects = heap.numLiveObjects;
                usedBlocks = heap.usedBlocks;
                i = heap.firstBlockWithPossibleSpace;
                goto scan;
            }
        }
  
        // didn't find a block, and GC didn't reclaim anything, need to allocate a new block
        size_t numBlocks = heap.numBlocks;
        if (usedBlocks == numBlocks) {
            numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);
            heap.numBlocks = numBlocks;
            heap.blocks = static_cast<CollectorBlock**>(fastRealloc(heap.blocks, numBlocks * sizeof(CollectorBlock*)));
        }

        targetBlock = reinterpret_cast<Block*>(allocateBlock<heapType>());
        targetBlock->freeList = targetBlock->cells;
        targetBlock->heap = this;
        targetBlockUsedCells = 0;
        heap.blocks[usedBlocks] = reinterpret_cast<CollectorBlock*>(targetBlock);
        heap.usedBlocks = usedBlocks + 1;
        heap.firstBlockWithPossibleSpace = usedBlocks;
    }
  
    // find a free spot in the block and detach it from the free list
    Cell* newCell = targetBlock->freeList;

    // "next" field is a cell offset -- 0 means next cell, so a zeroed block is already initialized
    targetBlock->freeList = (newCell + 1) + newCell->u.freeCell.next;

    targetBlock->usedCells = static_cast<uint32_t>(targetBlockUsedCells + 1);
    heap.numLiveObjects = numLiveObjects + 1;

#ifndef NDEBUG