/*

 *  Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc. All rights reserved.

 *  Copyright (C) 2007 Eric Seidel <eric@webkit.org>

 *

 *  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 "CodeBlock.h"

#include "CollectorHeapIterator.h"

#include "Interpreter.h"

#include "JSArray.h"

#include "JSGlobalObject.h"

#include "JSLock.h"

#include "JSONObject.h"

#include "JSString.h"

#include "JSValue.h"

#include "JSZombie.h"

#include "MarkStack.h"

#include "Nodes.h"

#include "Tracing.h"

#include <algorithm>

#include <limits.h>

#include <setjmp.h>

#include <stdlib.h>

#include <wtf/FastMalloc.h>

#include <wtf/HashCountedSet.h>

#include <wtf/UnusedParam.h>

#include <wtf/VMTags.h>

#if OS(DARWIN)

#include <mach/mach_init.h>

#include <mach/mach_port.h>

#include <mach/task.h>

#include <mach/thread_act.h>

#include <mach/vm_map.h>

#elif OS(WINDOWS)

#include <windows.h>

#include <malloc.h>

#elif OS(HAIKU)

#include <OS.h>

#elif OS(UNIX)

#include <stdlib.h>

#if !OS(HAIKU)

#include <sys/mman.h>

#endif

#include <unistd.h>

#if OS(SOLARIS)

#include <thread.h>

#else

#include <pthread.h>

#endif

#if HAVE(PTHREAD_NP_H)

#include <pthread_np.h>

#endif

#if OS(QNX)

#include <fcntl.h>

#include <sys/procfs.h>

#include <stdio.h>

#include <errno.h>

#endif

#endif

#define COLLECT_ON_EVERY_ALLOCATION 0

using std::max;

namespace JSC {

// tunable parameters

const size_t GROWTH_FACTOR = 2;

const size_t LOW_WATER_FACTOR = 4;

const size_t ALLOCATIONS_PER_COLLECTION = 3600;

// 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))

#if ENABLE(JSC_MULTIPLE_THREADS)

#if OS(DARWIN)

typedef mach_port_t PlatformThread;

#elif OS(WINDOWS)

typedef HANDLE PlatformThread;

#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

#if OS(SYMBIAN)

    , m_blockallocator(JSCCOLLECTOR_VIRTUALMEM_RESERVATION, BLOCK_SIZE)

#endif

    , m_globalData(globalData)

{

    ASSERT(globalData);

    memset(&m_heap, 0, sizeof(CollectorHeap));

    allocateBlock();

}

Heap::~Heap()

{

    // The destroy function must already have been called, so assert this.

    ASSERT(!m_globalData);

}

void Heap::destroy()

{

    JSLock lock(SilenceAssertionsOnly);

    if (!m_globalData)

        return;

    ASSERT(!m_globalData->dynamicGlobalObject);

    ASSERT(!isBusy());

    // 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;

    freeBlocks();

#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

#if OS(SYMBIAN)

    m_blockallocator.destroy();

#endif

    m_globalData = 0;

}

NEVER_INLINE CollectorBlock* Heap::allocateBlock()

{

#if OS(DARWIN)

    vm_address_t address = 0;

    vm_map(current_task(), &address, BLOCK_SIZE, BLOCK_OFFSET_MASK, VM_FLAGS_ANYWHERE | VM_TAG_FOR_COLLECTOR_MEMORY, MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_DEFAULT, VM_INHERIT_DEFAULT);

#elif OS(SYMBIAN)

    void* address = m_blockallocator.alloc();  

    if (!address)

        CRASH();

#elif OS(WINCE)

    void* address = VirtualAlloc(NULL, BLOCK_SIZE, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);

#elif OS(WINDOWS)

#if COMPILER(MINGW) && !COMPILER(MINGW64)

    void* address = __mingw_aligned_malloc(BLOCK_SIZE, BLOCK_SIZE);

#else

    void* address = _aligned_malloc(BLOCK_SIZE, BLOCK_SIZE);

#endif

    memset(address, 0, BLOCK_SIZE);

#elif HAVE(POSIX_MEMALIGN)

    void* address;

    posix_memalign(&address, BLOCK_SIZE, 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;

#endif

    // Initialize block.

    CollectorBlock* block = reinterpret_cast<CollectorBlock*>(address);

    block->heap = this;

    clearMarkBits(block);

    Structure* dummyMarkableCellStructure = m_globalData->dummyMarkableCellStructure.get();

    for (size_t i = 0; i < HeapConstants::cellsPerBlock; ++i)

        new (&block->cells[i]) JSCell(dummyMarkableCellStructure);

    // Add block to blocks vector.

    size_t numBlocks = m_heap.numBlocks;

    if (m_heap.usedBlocks == numBlocks) {

        static const size_t maxNumBlocks = ULONG_MAX / sizeof(CollectorBlock*) / GROWTH_FACTOR;

        if (numBlocks > maxNumBlocks)

            CRASH();

        numBlocks = max(MIN_ARRAY_SIZE, numBlocks * GROWTH_FACTOR);

        m_heap.numBlocks = numBlocks;

        m_heap.blocks = static_cast<CollectorBlock**>(fastRealloc(m_heap.blocks, numBlocks * sizeof(CollectorBlock*)));

    }

    m_heap.blocks[m_heap.usedBlocks++] = block;

    return block;

}

NEVER_INLINE void Heap::freeBlock(size_t block)

{

    m_heap.didShrink = true;

    ObjectIterator it(m_heap, block);

    ObjectIterator end(m_heap, block + 1);

    for ( ; it != end; ++it)

        (*it)->~JSCell();

    freeBlockPtr(m_heap.blocks[block]);

    // swap with the last block so we compact as we go

    m_heap.blocks[block] = m_heap.blocks[m_heap.usedBlocks - 1];

    m_heap.usedBlocks--;

    if (m_heap.numBlocks > MIN_ARRAY_SIZE && m_heap.usedBlocks < m_heap.numBlocks / LOW_WATER_FACTOR) {

        m_heap.numBlocks = m_heap.numBlocks / GROWTH_FACTOR; 

        m_heap.blocks = static_cast<CollectorBlock**>(fastRealloc(m_heap.blocks, m_heap.numBlocks * sizeof(CollectorBlock*)));

    }

}

NEVER_INLINE void Heap::freeBlockPtr(CollectorBlock* block)

{

#if OS(DARWIN)    

    vm_deallocate(current_task(), reinterpret_cast<vm_address_t>(block), BLOCK_SIZE);

#elif OS(SYMBIAN)

    m_blockallocator.free(reinterpret_cast<void*>(block));

#elif OS(WINCE)

    VirtualFree(block, 0, MEM_RELEASE);

#elif OS(WINDOWS)

#if COMPILER(MINGW) && !COMPILER(MINGW64)

    __mingw_aligned_free(block);

#else

    _aligned_free(block);

#endif

#elif HAVE(POSIX_MEMALIGN)

    free(block);

#else

    munmap(reinterpret_cast<char*>(block), BLOCK_SIZE);

#endif

}

void Heap::freeBlocks()

{

    ProtectCountSet protectedValuesCopy = m_protectedValues;

    clearMarkBits();

    ProtectCountSet::iterator protectedValuesEnd = protectedValuesCopy.end();

    for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)

        markCell(it->first);

    m_heap.nextCell = 0;

    m_heap.nextBlock = 0;

    DeadObjectIterator it(m_heap, m_heap.nextBlock, m_heap.nextCell);

    DeadObjectIterator end(m_heap, m_heap.usedBlocks);

    for ( ; it != end; ++it)

        (*it)->~JSCell();

    ASSERT(!protectedObjectCount());

    protectedValuesEnd = protectedValuesCopy.end();

    for (ProtectCountSet::iterator it = protectedValuesCopy.begin(); it != protectedValuesEnd; ++it)

        it->first->~JSCell();

    for (size_t block = 0; block < m_heap.usedBlocks; ++block)

        freeBlockPtr(m_heap.blocks[block]);

    fastFree(m_heap.blocks);

    memset(&m_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.

    if (m_heap.extraCost > maxExtraCost && m_heap.extraCost > m_heap.usedBlocks * BLOCK_SIZE / 2) {

        // If the last iteration through the heap deallocated blocks, we need

        // to clean up remaining garbage before marking. Otherwise, the conservative

        // marking mechanism might follow a pointer to unmapped memory.

        if (m_heap.didShrink)

            sweep();

        reset();

    }

    m_heap.extraCost += cost;

}

void* Heap::allocate(size_t s)

{

    typedef HeapConstants::Block Block;

    typedef HeapConstants::Cell Cell;

    ASSERT(JSLock::lockCount() > 0);

    ASSERT(JSLock::currentThreadIsHoldingLock());

    ASSERT_UNUSED(s, s <= HeapConstants::cellSize);

    ASSERT(m_heap.operationInProgress == NoOperation);

#if COLLECT_ON_EVERY_ALLOCATION

    collectAllGarbage();

    ASSERT(m_heap.operationInProgress == NoOperation);

#endif

allocate:

    // Fast case: find the next garbage cell and recycle it.

    do {

        ASSERT(m_heap.nextBlock < m_heap.usedBlocks);

        Block* block = reinterpret_cast<Block*>(m_heap.blocks[m_heap.nextBlock]);

        do {

            ASSERT(m_heap.nextCell < HeapConstants::cellsPerBlock);

            if (!block->marked.get(m_heap.nextCell)) { // Always false for the last cell in the block

                Cell* cell = &block->cells[m_heap.nextCell];

                m_heap.operationInProgress = Allocation;

                JSCell* imp = reinterpret_cast<JSCell*>(cell);

                imp->~JSCell();

                m_heap.operationInProgress = NoOperation;

                ++m_heap.nextCell;

                return cell;

            }

            block->marked.advanceToNextPossibleFreeCell(m_heap.nextCell);

        } while (m_heap.nextCell != HeapConstants::cellsPerBlock);

        m_heap.nextCell = 0;

    } while (++m_heap.nextBlock != m_heap.usedBlocks);

    // Slow case: reached the end of the heap. Mark live objects and start over.

    reset();

    goto allocate;

}

void Heap::resizeBlocks()

{

    m_heap.didShrink = false;

    size_t usedCellCount = markedCells();

    size_t minCellCount = usedCellCount + max(ALLOCATIONS_PER_COLLECTION, usedCellCount);

    size_t minBlockCount = (minCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;

    size_t maxCellCount = 1.25f * minCellCount;

    size_t maxBlockCount = (maxCellCount + HeapConstants::cellsPerBlock - 1) / HeapConstants::cellsPerBlock;

    if (m_heap.usedBlocks < minBlockCount)

        growBlocks(minBlockCount);

    else if (m_heap.usedBlocks > maxBlockCount)

        shrinkBlocks(maxBlockCount);

}

void Heap::growBlocks(size_t neededBlocks)

{

    ASSERT(m_heap.usedBlocks < neededBlocks);

    while (m_heap.usedBlocks < neededBlocks)

        allocateBlock();

}

void Heap::shrinkBlocks(size_t neededBlocks)

{

    ASSERT(m_heap.usedBlocks > neededBlocks);

    // Clear the always-on last bit, so isEmpty() isn't fooled by it.

    for (size_t i = 0; i < m_heap.usedBlocks; ++i)

        m_heap.blocks[i]->marked.clear(HeapConstants::cellsPerBlock - 1);

    for (size_t i = 0; i != m_heap.usedBlocks && m_heap.usedBlocks != neededBlocks; ) {

        if (m_heap.blocks[i]->marked.isEmpty()) {

            freeBlock(i);

        } else

            ++i;

    }

    // Reset the always-on last bit.

    for (size_t i = 0; i < m_heap.usedBlocks; ++i)

        m_heap.blocks[i]->marked.set(HeapConstants::cellsPerBlock - 1);

}

#if OS(WINCE)

JS_EXPORTDATA void* g_stackBase = 0;

inline bool isPageWritable(void* page)

{

    MEMORY_BASIC_INFORMATION memoryInformation;

    DWORD result = VirtualQuery(page, &memoryInformation, sizeof(memoryInformation));

    // return false on error, including ptr outside memory

    if (result != sizeof(memoryInformation))

        return false;

    DWORD protect = memoryInformation.Protect & ~(PAGE_GUARD | PAGE_NOCACHE);

    return protect == PAGE_READWRITE

        || protect == PAGE_WRITECOPY

        || protect == PAGE_EXECUTE_READWRITE

        || protect == PAGE_EXECUTE_WRITECOPY;

}

static void* getStackBase(void* previousFrame)

{

    // find the address of this stack frame by taking the address of a local variable

    bool isGrowingDownward;

    void* thisFrame = (void*)(&isGrowingDownward);

    isGrowingDownward = previousFrame < &thisFrame;

    static DWORD pageSize = 0;

    if (!pageSize) {

        SYSTEM_INFO systemInfo;

        GetSystemInfo(&systemInfo);

        pageSize = systemInfo.dwPageSize;

    }

    // scan all of memory starting from this frame, and return the last writeable page found

    register char* currentPage = (char*)((DWORD)thisFrame & ~(pageSize - 1));

    if (isGrowingDownward) {

        while (currentPage > 0) {

            // check for underflow

            if (currentPage >= (char*)pageSize)

                currentPage -= pageSize;

            else

                currentPage = 0;

            if (!isPageWritable(currentPage))

                return currentPage + pageSize;

        }

        return 0;

    } else {

        while (true) {

            // guaranteed to complete because isPageWritable returns false at end of memory

            currentPage += pageSize;

            if (!isPageWritable(currentPage))

                return currentPage;

        }

    }

}

#endif

#if OS(QNX)

static inline void *currentThreadStackBaseQNX()

{

    static void* stackBase = 0;

    static size_t stackSize = 0;

    static pthread_t stackThread;

    pthread_t thread = pthread_self();

    if (stackBase == 0 || thread != stackThread) {

        struct _debug_thread_info threadInfo;

        memset(&threadInfo, 0, sizeof(threadInfo));

        threadInfo.tid = pthread_self();

        int fd = open("/proc/self", O_RDONLY);

        if (fd == -1) {

            LOG_ERROR("Unable to open /proc/self (errno: %d)", errno);

            return 0;

        }

        devctl(fd, DCMD_PROC_TIDSTATUS, &threadInfo, sizeof(threadInfo), 0);

        close(fd);

        stackBase = reinterpret_cast<void*>(threadInfo.stkbase);

        stackSize = threadInfo.stksize;