// -*- mode: c++; c-basic-offset: 4 -*-

/*

 *  This file is part of the KDE libraries

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

 *

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

#include "list.h"

#include "value.h"

#include <algorithm>

#include <setjmp.h>

#include <stdlib.h>

#include <wtf/FastMalloc.h>

#include <wtf/HashCountedSet.h>

#include <wtf/UnusedParam.h>

#if USE(MULTIPLE_THREADS)

#include <pthread.h>

#endif

#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>

#include "CollectorHeapIntrospector.h"

#elif PLATFORM(WIN_OS)

#include <windows.h>

#elif PLATFORM(UNIX)

#include <stdlib.h>

#include <sys/mman.h>

#include <unistd.h>

#if HAVE(PTHREAD_NP_H)

#include <pthread_np.h>

#else

#include <pthread.h>

#endif

#elif PLATFORM(SYMBIAN)

#include <e32std.h>

#include <e32cmn.h>

#endif

#define DEBUG_COLLECTOR 0

using std::max;

namespace KJS {

// tunable parameters

const size_t SPARE_EMPTY_BLOCKS = 2;

const size_t MIN_ARRAY_SIZE = 14;

const size_t GROWTH_FACTOR = 2;

const size_t LOW_WATER_FACTOR = 4;

const size_t ALLOCATIONS_PER_COLLECTION = 4000;

enum OperationInProgress { NoOperation, Allocation, Collection };

struct CollectorHeap {

  CollectorBlock** blocks;

  size_t numBlocks;

  size_t usedBlocks;

  size_t firstBlockWithPossibleSpace;

  size_t numLiveObjects;

  size_t numLiveObjectsAtLastCollect;

  size_t extraCost;

  OperationInProgress operationInProgress;

};

static CollectorHeap heap = { 0, 0, 0, 0, 0, 0, 0, NoOperation };

// FIXME: I don't think this needs to be a static data member of the Collector class.

// Just a private global like "heap" above would be fine.

size_t Collector::mainThreadOnlyObjectCount = 0;

bool Collector::memoryFull = false;

#if PLATFORM(SYMBIAN)

unsigned int Collector::CallStackGrowthThresh = 0;

Vector<JSCell *> Collector::recursivelyOrphanedMarkTops;

#endif // PLATFORM(SYMBIAN)

static CollectorBlock* allocateBlock()

{

#if 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);

#else

#if PLATFORM(DARWIN)    

    vm_address_t address = 0;

    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(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

    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<void*>(address), adjust);

    if (adjust < extra)

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

    address += adjust;

    memset(reinterpret_cast<void*>(address), 0, BLOCK_SIZE);

#endif

#endif  // PLATFORM(SYMBIAN)

    return reinterpret_cast<CollectorBlock*>(address);

}

static void freeBlock(CollectorBlock* block)

{

#if PLATFORM(SYMBIAN)

    fastFree(block);

#else

#if PLATFORM(DARWIN)    

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

#elif PLATFORM(WIN_OS)

    VirtualFree(block, BLOCK_SIZE, MEM_RELEASE);

#elif HAVE(POSIX_MEMALIGN)

    free(block);

#else

    munmap(block, BLOCK_SIZE);

#endif

#endif

}

void Collector::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.

    heap.extraCost += cost;

}

void* Collector::allocate(size_t s)

{

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

  ASSERT(JSLock::currentThreadIsHoldingLock());

  ASSERT(s <= CELL_SIZE);

  UNUSED_PARAM(s); // s is now only used for the above assert

  ASSERT(heap.operationInProgress == NoOperation);

  // FIXME: If another global variable access here doesn't hurt performance

  // too much, we could abort() in NDEBUG builds, which could help ensure we

  // don't spend any time debugging cases where we allocate inside an object's

  // deallocation code.

  // collect if needed

  size_t numLiveObjects = heap.numLiveObjects;

  size_t numLiveObjectsAtLastCollect = heap.numLiveObjectsAtLastCollect;

  size_t numNewObjects = numLiveObjects - numLiveObjectsAtLastCollect;

  size_t newCost = numNewObjects + heap.extraCost;

  if (newCost >= ALLOCATIONS_PER_COLLECTION && newCost >= numLiveObjectsAtLastCollect) {

    collect();

    numLiveObjects = heap.numLiveObjects;

  }

  ASSERT(heap.operationInProgress == NoOperation);

#ifndef NDEBUG

  // FIXME: Consider doing this in NDEBUG builds too (see comment above).

  heap.operationInProgress = Allocation;

#endif

  // slab allocator

  size_t usedBlocks = heap.usedBlocks;

  size_t i = heap.firstBlockWithPossibleSpace;

  CollectorBlock *targetBlock;

  size_t targetBlockUsedCells;

  if (i != usedBlocks) {

    targetBlock = heap.blocks[i];

    targetBlockUsedCells = targetBlock->usedCells;

    ASSERT(targetBlockUsedCells <= CELLS_PER_BLOCK);

    while (targetBlockUsedCells == CELLS_PER_BLOCK) {

      if (++i == usedBlocks)

        goto allocateNewBlock;

      targetBlock = heap.blocks[i];

      targetBlockUsedCells = targetBlock->usedCells;

      ASSERT(targetBlockUsedCells <= CELLS_PER_BLOCK);

    }

    heap.firstBlockWithPossibleSpace = i;

  } else {

allocateNewBlock:

    // didn't find one, 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 = allocateBlock();

    targetBlock->freeList = targetBlock->cells;

    targetBlockUsedCells = 0;

    heap.blocks[usedBlocks] = targetBlock;

    heap.usedBlocks = usedBlocks + 1;

    heap.firstBlockWithPossibleSpace = usedBlocks;

  }

  // find a free spot in the block and detach it from the free list

  CollectorCell *newCell = targetBlock->freeList;

  // "next" field is a byte offset -- 0 means next cell, so a zeroed block is already initialized

  // could avoid the casts by using a cell offset, but this avoids a relatively-slow multiply

  targetBlock->freeList = reinterpret_cast<CollectorCell *>(reinterpret_cast<char *>(newCell + 1) + newCell->u.freeCell.next);

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

  heap.numLiveObjects = numLiveObjects + 1;

#ifndef NDEBUG

  // FIXME: Consider doing this in NDEBUG builds too (see comment above).

  heap.operationInProgress = NoOperation;

#endif

  return newCell;

}

static inline void* currentThreadStackBase()

{

#if PLATFORM(DARWIN)

    pthread_t thread = pthread_self();

    return pthread_get_stackaddr_np(thread);

#elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(MSVC)

    // offset 0x18 from the FS segment register gives a pointer to

    // the thread information block for the current thread

    NT_TIB* pTib;

    __asm {

        MOV EAX, FS:[18h]

        MOV pTib, EAX

    }

    return (void*)pTib->StackBase;

#elif PLATFORM(WIN_OS) && PLATFORM(X86) && COMPILER(GCC)

    // offset 0x18 from the FS segment register gives a pointer to

    // the thread information block for the current thread

    NT_TIB* pTib;

    asm ( "movl %%fs:0x18, %0\n"

          : "=r" (pTib)

        );

    return (void*)pTib->StackBase;

#elif PLATFORM(UNIX)

    static void *stackBase = 0;

    static size_t stackSize = 0;

    static pthread_t stackThread;

    pthread_t thread = pthread_self();

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

        pthread_attr_t sattr;

        pthread_attr_init(&sattr);

#if HAVE(PTHREAD_NP_H)

        // e.g. on FreeBSD 5.4, neundorf@kde.org

        pthread_attr_get_np(thread, &sattr);

#else

        // FIXME: this function is non-portable; other POSIX systems may have different np alternatives

        pthread_getattr_np(thread, &sattr);

#endif

        int rc = pthread_attr_getstack(&sattr, &stackBase, &stackSize);

        (void)rc; // FIXME: deal with error code somehow?  seems fatal...

        ASSERT(stackBase);

        pthread_attr_destroy(&sattr);

        stackThread = thread;

    }

    return (void*)(size_t(stackBase) + stackSize);

#elif PLATFORM(SYMBIAN)

    static void *stackBase = 0;

    if (stackBase == 0) {

        TThreadStackInfo info;

        RThread thread;

        thread.StackInfo(info);

        stackBase = (void*)info.iBase;

    }

    //fixme

    return (void*)stackBase;

#else

#error Need a way to get the stack base on this platform

#endif

}

#if USE(MULTIPLE_THREADS)

static pthread_t mainThread;

#endif

void Collector::registerAsMainThread()

{

#if USE(MULTIPLE_THREADS)

    mainThread = pthread_self();

#endif

}

static inline bool onMainThread()

{

#if PLATFORM(SYMBIAN)

    return true;

#else

#if USE(MULTIPLE_THREADS)

#if PLATFORM(DARWIN)

    return pthread_main_np();

#else

    return !!pthread_equal(pthread_self(), mainThread);

#endif

#else

    return true;

#endif

#endif

}

#if USE(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

static inline PlatformThread getCurrentPlatformThread()

{

#if PLATFORM(DARWIN)

    return pthread_mach_thread_np(pthread_self());

#elif PLATFORM(WIN_OS)

    HANDLE threadHandle = pthread_getw32threadhandle_np(pthread_self());

    return PlatformThread(GetCurrentThreadId(), threadHandle);

#endif

}

class Collector::Thread {

public:

  Thread(pthread_t pthread, const PlatformThread& platThread) : posixThread(pthread), platformThread(platThread) {}

  Thread* next;

  pthread_t posixThread;

  PlatformThread platformThread;

};

pthread_key_t registeredThreadKey;

pthread_once_t registeredThreadKeyOnce = PTHREAD_ONCE_INIT;

Collector::Thread* registeredThreads;

static void destroyRegisteredThread(void* data) 

{

  Collector::Thread* thread = (Collector::Thread*)data;

  // Can't use JSLock convenience object here because we don't want to re-register

  // an exiting thread.

  JSLock::lock();

  if (registeredThreads == thread) {

    registeredThreads = registeredThreads->next;

  } else {

    Collector::Thread *last = registeredThreads;

    Collector::Thread *t;

    for (t = registeredThreads->next; t != NULL; t = t->next) {

      if (t == thread) {          

          last->next = t->next;

          break;

      }

      last = t;

    }

    ASSERT(t); // If t is NULL, we never found ourselves in the list.

  }

  JSLock::unlock();

  delete thread;

}

static void initializeRegisteredThreadKey()

{

  pthread_key_create(&registeredThreadKey, destroyRegisteredThread);

}

void Collector::registerThread()

{

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

  ASSERT(JSLock::currentThreadIsHoldingLock());

  pthread_once(&registeredThreadKeyOnce, initializeRegisteredThreadKey);

  if (!pthread_getspecific(registeredThreadKey)) {

#if PLATFORM(DARWIN)

      if (onMainThread())

          CollectorHeapIntrospector::init(&heap);

#endif

    Collector::Thread *thread = new Collector::Thread(pthread_self(), getCurrentPlatformThread());

    thread->next = registeredThreads;

    registeredThreads = thread;

    pthread_setspecific(registeredThreadKey, thread);

  }

}

#endif

#define IS_POINTER_ALIGNED(p) (((intptr_t)(p) & (sizeof(char *) - 1)) == 0)

// cell size needs to be a power of two for this to be valid

#define IS_CELL_ALIGNED(p) (((intptr_t)(p) & CELL_MASK) == 0)

void Collector::markStackObjectsConservatively(void *start, void *end)

{

  if (start > end) {

    void* tmp = start;

    start = end;

    end = tmp;

  }

  ASSERT(((char*)end - (char*)start) < 0x1000000);

  ASSERT(IS_POINTER_ALIGNED(start));

  ASSERT(IS_POINTER_ALIGNED(end));

  char** p = (char**)start;

  char** e = (char**)end;

  size_t usedBlocks = heap.usedBlocks;

  CollectorBlock **blocks = heap.blocks;

  const size_t lastCellOffset = sizeof(CollectorCell) * (CELLS_PER_BLOCK - 1);

  while (p != e) {

    char* x = *p++;

#if PLATFORM(SYMBIAN)

    // fixme symbian's default allocator doesn't guarentee 64KB-aligned blocks,

    // we have to fall back to slower searching.

    if (IS_POINTER_ALIGNED(x) && x) {

        for (size_t block = 0; block < usedBlocks; ++block) {

            int offset = x - (char*)blocks[block];

            if ((offset >= 0) && (offset < BLOCK_SIZE) && (offset%CELL_SIZE == 0)) {

              if (((CollectorCell*)x)->u.freeCell.zeroIfFree != 0) {

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

                if (!imp->marked())

                  imp->mark();

              }

              break;             

            }

        }

    }

#else

    if (IS_CELL_ALIGNED(x) && x) {

      uintptr_t offset = reinterpret_cast<uintptr_t>(x) & BLOCK_OFFSET_MASK;

      CollectorBlock* blockAddr = reinterpret_cast<CollectorBlock*>(x - offset);

      for (size_t block = 0; block < usedBlocks; block++) {

        if ((blocks[block] == blockAddr) & (offset <= lastCellOffset)) {

          if (((CollectorCell*)x)->u.freeCell.zeroIfFree != 0) {

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

            if (!imp->marked())

              imp->mark();

          }

          break;

        }

      }

    }

#endif

  }

}

void Collector::markCurrentThreadConservatively()

{

    // setjmp forces volatile registers onto the stack

    jmp_buf registers;

#if COMPILER(MSVC)

#pragma warning(push)