/*

 * Copyright (c) 2010 Nokia Corporation and/or its subsidiary(-ies).

 *

 * This file is part of Qt Web Runtime.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public License

 * version 2.1 as published by the Free Software Foundation.

 *

 * 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 St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 */

/****************************************************************************

 *

 * This file is part of the Symbian application wrapper of the Qt Toolkit.

 *

 * The memory allocator is backported from Symbian OS, and can eventually

 * be removed from Qt once it is built in to all supported OS versions.

 * The allocator is a composite of three allocators:

 *  - A page allocator, for large allocations

 *  - A slab allocator, for small allocations

 *  - Doug Lea's allocator, for medium size allocations

 *

 ***************************************************************************/

#include <e32std.h>

#include <e32cmn.h>

#include <hal.h>

#include <e32panic.h>

#ifndef QT_SYMBIAN_HAVE_U32STD_H

struct SThreadCreateInfo

    {

    TAny* iHandle;

    TInt iType;

    TThreadFunction iFunction;

    TAny* iPtr;

    TAny* iSupervisorStack;

    TInt iSupervisorStackSize;

    TAny* iUserStack;

    TInt iUserStackSize;

    TInt iInitialThreadPriority;

    TPtrC iName;

    TInt iTotalSize;    // Size including any extras (must be a multiple of 8 bytes)

    };

struct SStdEpocThreadCreateInfo : public SThreadCreateInfo

    {

    RAllocator* iAllocator;

    TInt iHeapInitialSize;

    TInt iHeapMaxSize;

    TInt iPadding;      // Make structure size a multiple of 8 bytes

    };

#else

#include <u32std.h>

#endif

#include <e32svr.h>

//Named local chunks require support from the kernel, which depends on Symbian^3

#define NO_NAMED_LOCAL_CHUNKS

//Reserving a minimum heap size is not supported, because the implementation does not know what type of

//memory to use. DLA memory grows upwards, slab and page allocators grow downwards.

//This would need kernel support to do properly.

#define NO_RESERVE_MEMORY

//The BTRACE debug framework requires Symbian OS 9.4 or higher.

//Required header files are not included in S60 5.0 SDKs, but

//they are available for open source versions of Symbian OS.

//Note that although Symbian OS 9.3 supports BTRACE, the usage in this file

//depends on 9.4 header files.

//This debug flag uses BTRACE to emit debug traces to identify the heaps.

//Note that it uses the ETest1 trace category which is not reserved

//#define TRACING_HEAPS

//This debug flag uses BTRACE to emit debug traces to aid with debugging

//allocs, frees & reallocs. It should be used together with the KUSERHEAPTRACE

//kernel trace flag to enable heap tracing.

//#define TRACING_ALLOCS

//This debug flag turns on tracing of the call stack for each alloc trace.

//It is dependent on TRACING_ALLOCS.

//#define TRACING_CALLSTACKS

#if defined(TRACING_ALLOCS) || defined(TRACING_HEAPS)

#include <e32btrace.h>

#endif

// Memory logging routines inherited from webkit allocator 9.2TB.

// #define OOM_LOGGING

// This debug flag logs error conditions when memory is unmapped/mapped from the system.

// Also, exports routines to dump the internal state and memory usage of the DL allocator.

// #define DL_CHUNK_MEM_DEBUG

// Exports debug rouintes to assert/trace chunked memory access.

#if defined(OOM_LOGGING) || defined(DL_CHUNK_MEM_DEBUG)

#include "MemoryLogger.h"

#endif

#ifndef __WINS__

#pragma push

#pragma arm

#endif

#include "dla_p.h"

#include "newallocator_p.h"

// if non zero this causes the slabs to be configured only when the chunk size exceeds this level

#define DELAYED_SLAB_THRESHOLD (64*1024)        // 64KB seems about right based on trace data

#define SLAB_CONFIG (0xabe)

_LIT(KDLHeapPanicCategory, "DL Heap");

#define GET_PAGE_SIZE(x)            HAL::Get(HALData::EMemoryPageSize, x)

#define __CHECK_CELL(p)

#define __POWER_OF_2(x)             ((TUint32)((x)^((x)-1))>=(TUint32)(x))

#define HEAP_PANIC(r)               Panic(r)

LOCAL_C void Panic(TCdtPanic aPanic)

// Panic the process with USER as the category.

    {

    User::Panic(_L("USER"),aPanic);

    }

    /* Purpose:     Map chunk memory pages from system RAM

 * Arguments:   tp - tchunkptr in which memmory should be mapped

 *              psize - incoming tchunk size

 * Return:      KErrNone if successful, else KErrNoMemory

 * Note:

 */

TInt RNewAllocator::map_chunk_pages(tchunkptr tp, size_t psize)

{

    if (page_not_in_memory(tp, psize)) {

        char *a_addr = tchunk_page_align(tp);

        size_t npages = tp->npages;

#ifdef OOM_LOGGING

        // check that npages matches the psize

        size_t offset = address_offset(a_addr,tp);

        if (offset < psize && (psize - offset) >= mparams.page_size )

        {

            size_t tpages = ( psize - offset) >> pageshift;

            if (tpages != tp->npages) //assert condition

                MEM_LOG("CHUNK_PAGE_ERROR:map_chunk_pages, error in npages");

        }

        else

            MEM_LOG("CHUNK_PAGE_ERROR::map_chunk_pages: - Incorrect page-in-memmory flag");

#endif

        if (map(a_addr, npages*mparams.page_size)) {

            TRACE_DL_CHUNK_MAP(tp, psize, a_addr, npages*mparams.page_size);

            ASSERT_RCHUNK_SIZE();

            TRACE_UNMAPPED_CHUNK(-1*npages*mparams.page_size);

            return KErrNone;

        }

        else {

#ifdef OOM_LOGGING

            MEM_LOGF(_L8("CHUNK_PAGE_ERROR:: map_chunk_pages - Failed to Commit RAM, page_addr=%x, npages=%d, chunk_size=%d"), a_addr, npages, psize);

            MEM_DUMP_OOM_LOGS(psize, "RSymbianDLHeap::map_chunk_pages - Failed to Commit RAM");

#endif

            return KErrNoMemory;

        }

    }

    return KErrNone;

}

/* Purpose:     Map partial chunk memory pages from system RAM

 * Arguments:   tp - tchunkptr in which memmory should be mapped

 *              psize - incoming tchunk size

 *              r - remainder chunk pointer

 *              rsize - remainder chunk size

 * Return:      Number of unmapped pages from remainder chunk if successful (0 or more), else KErrNoMemory

 * Note:        Remainder chunk should be large enough to be mapped out (checked before invoking this function)

 *              pageout headers will be set from insert_large_chunk(), not here.

 */

TInt RNewAllocator::map_chunk_pages_partial(tchunkptr tp, size_t psize, tchunkptr r, size_t rsize)

{

    if (page_not_in_memory(tp, psize)) {

        size_t npages = tp->npages; // total no of pages unmapped in this chunk

        char *page_addr_map = tchunk_page_align(tp); // address to begin page map

        char *page_addr_rem = tchunk_page_align(r);  // address in remainder chunk to remain unmapped

        assert(address_offset(page_addr_rem, r) < rsize);

        size_t npages_map = address_offset(page_addr_rem, page_addr_map) >> pageshift; // no of pages to be mapped

        if (npages_map > 0) {

            if (map(page_addr_map, npages_map*mparams.page_size)) {

#ifdef DL_CHUNK_MEM_DEBUG

                TRACE_DL_CHUNK_MAP(tp, psize, page_addr_map, npages_map*mparams.page_size);

                ASSERT_RCHUNK_SIZE();

                TRACE_UNMAPPED_CHUNK(-1*npages_map*mparams.page_size);

#endif

                return (npages - npages_map);

            }

            else {

#ifdef OOM_LOGGING

                MEM_LOGF(_L8("CHUNK_PAGE_ERROR:: map_chunk_pages_partial - Failed to Commit RAM, page_addr=%x, npages=%d, chunk_size=%d"), page_addr_map, npages_map, psize);

                MEM_DUMP_OOM_LOGS(psize, "RSymbianDLHeap::map_chunk_pages_partial - Failed to Commit RAM");

#endif

                return KErrNoMemory;

            }

        }

        else {

             // map not needed, first page is already mapped

             return npages;

        }

    }

    return 0;

}

/* Purpose:     Release (unmap) chunk memory pages to system RAM

 * Arguments:   tp - tchunkptr from which memmory may be released

 *              psize - incoming tchunk size

 *              prev_npages - number of pages that has been already unmapped from this chunk

 * Return:      total number of pages that has been unmapped from this chunk (new unmapped pages + prev_npages)

 * Note:        pageout headers will be set from insert_large_chunk(), not here.

 */

TInt RNewAllocator::unmap_chunk_pages(tchunkptr tp, size_t psize, size_t prev_npages)

{

    size_t npages = 0;

    char *a_addr = tchunk_page_align(tp);

    size_t offset = address_offset(a_addr,tp);

    if (offset < psize && (psize - offset) >= mparams.page_size)

    { /* check for new pages to decommit */

        npages = ( psize - offset) >> pageshift;

        if (npages > prev_npages) {

            unmap(a_addr, npages*mparams.page_size);    // assuming kernel takes care of already unmapped pages

            TRACE_DL_CHUNK_UNMAP(tp, psize, a_addr, npages*mparams.page_size);

            iChunkSize += prev_npages*mparams.page_size; //adjust actual chunk size

            ASSERT_RCHUNK_SIZE();

            TRACE_UNMAPPED_CHUNK((npages-prev_npages)*mparams.page_size);

            assert((a_addr + npages*mparams.page_size - 1) < (char*)next_chunk(tp));

        }

    }

#ifdef OOM_LOGGING

    if (npages && (npages < prev_npages))

        MEM_LOG("CHUNK_PAGE_ERROR:unmap_chunk_pages, error in npages");

    if (npages > prev_npages) {

        /* check that end of decommited address lie within this chunk */

        if ((a_addr + npages*mparams.page_size - 1) >= (char*)next_chunk(tp))

            MEM_LOG("CHUNK_PAGE_ERROR:unmap_chunk_pages, error chunk boundary");

    }

#endif

#ifdef DL_CHUNK_MEM_DEBUG

    mchunkptr next = next_chunk(tp);

    do_check_any_chunk_access(next, chunksize(next));

    if (!npages)  do_check_any_chunk_access((mchunkptr)tp, psize);

#endif

    return (npages);

}

/* Purpose:     Unmap all pages between previously unmapped and end of top chunk

                and reset top to beginning of prev chunk

 * Arguments:   fm - global malloc state

 *              prev - previous chunk which has unmapped pages

 *              psize - size of previous chunk

 *              prev_npages - number of unmapped pages from previous chunk

 * Return:      nonzero if sucessful, else 0

 * Note:

 */

TInt RNewAllocator::sys_trim_partial(mstate m, mchunkptr prev, size_t psize, size_t prev_npages)

{

    size_t released = 0;

    size_t extra = 0;

    if (is_initialized(m)) {

      psize += m->topsize;

      char *a_addr = tchunk_page_align(prev); // includes space for TOP footer

      size_t addr_offset = address_offset(a_addr, prev);

      assert(addr_offset > TOP_FOOT_SIZE); //always assert?

      assert((char*)iTop >= a_addr); //always assert?

      if ((char*)iTop > a_addr)

          extra = address_offset(iTop, a_addr);

#ifdef OOM_LOGGING

      if ((char*)iTop < a_addr)

          MEM_LOGF(_L8("RSymbianDLHeap::sys_trim_partial - incorrect iTop value, top=%x, iTop=%x"), m->top, iTop);

#endif

        msegmentptr sp = segment_holding(m, (TUint8*)prev);

        if (!is_extern_segment(sp)) {

          if (is_mmapped_segment(sp)) {

            if (HAVE_MMAP &&  sp->size >= extra && !has_segment_link(m, sp)) { /* can't shrink if pinned */

             // size_t newsize = sp->size - extra;

              /* Prefer mremap, fall back to munmap */

              if ((CALL_MREMAP(sp->base, sp->size, sp->size - extra, 0) != MFAIL) ||

                  (CALL_MUNMAP(sp->base + sp->size - extra, extra) == 0)) {

                released = extra;

              }

            }

          }

          else if (HAVE_MORECORE) {

            if (extra >= HALF_MAX_SIZE_T) /* Avoid wrapping negative */

                extra = (HALF_MAX_SIZE_T) + SIZE_T_ONE - mparams.granularity;

            ACQUIRE_MORECORE_LOCK(m);

            {

              /* Make sure end of memory is where we last set it. */

              TUint8* old_br = (TUint8*)(CALL_MORECORE(0));

              if (old_br == sp->base + sp->size) {

                TUint8* rel_br = (TUint8*)(CALL_MORECORE(-extra));

                TUint8* new_br = (TUint8*)(CALL_MORECORE(0));

                if (rel_br != CMFAIL && new_br < old_br)

                  released = old_br - new_br;

              }

            }

            RELEASE_MORECORE_LOCK(m);

          }

        }

        if (released != 0) {

          TRACE_DL_CHUNK_UNMAP(prev, psize, a_addr, released);

          iChunkSize += prev_npages*mparams.page_size; // prev_unmapped was already unmapped

          TRACE_UNMAPPED_CHUNK(-1*prev_npages*mparams.page_size);

          ASSERT_RCHUNK_SIZE();

          sp->size -= released;

          m->footprint -= released;

        }

        /* reset top to prev chunk */

        init_top(m, prev, addr_offset - TOP_FOOT_SIZE);

        check_top_chunk(m, m->top);

    }

    // DL region not initalized, do not reset top here

    return (released != 0)? 1 : 0;

}

#define STACKSIZE 32

inline void RNewAllocator::TraceCallStack()

{

#ifdef TRACING_CALLSTACKS

    TUint32 filteredStack[STACKSIZE];

    TThreadStackInfo info;

    TUint32 *sp = (TUint32*)&sp;

    RThread().StackInfo(info);

    Lock();

    TInt i;

    for (i=0;i<STACKSIZE;i++) {

        if ((TLinAddr)sp>=info.iBase) break;

        while ((TLinAddr)sp < info.iBase) {

            TUint32 cur = *sp++;

            TUint32 range = cur & 0xF0000000;

            if (range == 0x80000000 || range == 0x70000000) {

                filteredStack[i] = cur;

                break;

            }

        }

    }

    Unlock();

    BTraceContextBig(BTrace::EHeap, BTrace::EHeapCallStack, (TUint32)this, filteredStack, i * 4);

#endif

}

size_t getpagesize()

{

    TInt size;

    TInt err = GET_PAGE_SIZE(size);

    if (err != KErrNone)

        return (size_t)0x1000;

    return (size_t)size;

}

#define gm  (&iGlobalMallocState)

RNewAllocator::RNewAllocator(TInt aMaxLength, TInt aAlign, TBool aSingleThread)

// constructor for a fixed heap. Just use DL allocator

    :iMinLength(aMaxLength), iMaxLength(aMaxLength), iOffset(0), iGrowBy(0), iChunkHandle(0),

    iNestingLevel(0), iAllocCount(0), iFailType(ENone), iTestData(NULL), iChunkSize(aMaxLength)

    {

    if ((TUint32)aAlign>=sizeof(TAny*) && __POWER_OF_2(iAlign))

        {

        iAlign = aAlign;

        }

    else

        {

        iAlign = 4;

        }

    iPageSize = 0;

    iFlags = aSingleThread ? (ESingleThreaded|EFixedSize) : EFixedSize;

    Init(0, 0, 0);

    }

RNewAllocator::RNewAllocator(TInt aChunkHandle, TInt aOffset, TInt aMinLength, TInt aMaxLength, TInt aGrowBy,

            TInt aAlign, TBool aSingleThread)

        : iMinLength(aMinLength), iMaxLength(aMaxLength), iOffset(aOffset), iChunkHandle(aChunkHandle), iAlign(aAlign), iNestingLevel(0), iAllocCount(0),

            iFailType(ENone), iTestData(NULL), iChunkSize(aMinLength),iHighWaterMark(aMinLength)

    {

    iPageSize = malloc_getpagesize;

    __ASSERT_ALWAYS(aOffset >=0, User::Panic(KDLHeapPanicCategory, ETHeapNewBadOffset));

    iGrowBy = _ALIGN_UP(aGrowBy, iPageSize);

    iFlags = aSingleThread ? ESingleThreaded : 0;

    // Initialise

    // if the heap is created with aMinLength==aMaxLength then it cannot allocate slab or page memory

    // so these sub-allocators should be disabled. Otherwise initialise with default values

    if (aMinLength == aMaxLength)

        Init(0, 0, 0);

    else

        Init(0x3fff, 15, 0x10000);  // all slabs, page {32KB}, trim {64KB} // Andrew: Adopting Webkit config?

        //Init(0xabe, 16, iPageSize*4); // slabs {48, 40, 32, 24, 20, 16, 12, 8}, page {64KB}, trim {16KB}

#ifdef TRACING_HEAPS

    RChunk chunk;

    chunk.SetHandle(iChunkHandle);

    TKName chunk_name;

    chunk.FullName(chunk_name);

    BTraceContextBig(BTrace::ETest1, 2, 22, chunk_name.Ptr(), chunk_name.Size());

    TUint32 traceData[4];

    traceData[0] = iChunkHandle;

    traceData[1] = iMinLength;

    traceData[2] = iMaxLength;

    traceData[3] = iAlign;

    BTraceContextN(BTrace::ETest1, 1, (TUint32)this, 11, traceData, sizeof(traceData));

#endif

    }

TAny* RNewAllocator::operator new(TUint aSize, TAny* aBase) __NO_THROW

    {

    __ASSERT_ALWAYS(aSize>=sizeof(RNewAllocator), HEAP_PANIC(ETHeapNewBadSize));

    RNewAllocator* h = (RNewAllocator*)aBase;

    h->iAlign = 0x80000000; // garbage value

    h->iBase = ((TUint8*)aBase) + aSize;

    return aBase;

    }

void RNewAllocator::Init(TInt aBitmapSlab, TInt aPagePower, size_t aTrimThreshold)

    {

    __ASSERT_ALWAYS((TUint32)iAlign>=sizeof(TAny*) && __POWER_OF_2(iAlign), HEAP_PANIC(ETHeapNewBadAlignment));

    /*Moved code which does initialization */

    iTop = (TUint8*)this + iMinLength;

    spare_page = 0;

    iAllocCount = 0; // FIXME  -- not used anywhere - already initialized to 0 in constructor anyway

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

    Init_Dlmalloc(iTop - iBase, 0, aTrimThreshold);

    slab_init(aBitmapSlab);

    /*10-1K,11-2K,12-4k,13-8K,14-16K,15-32K,16-64K*/

    paged_init(aPagePower);

#ifdef TRACING_ALLOCS

        TUint32 traceData[3];

        traceData[0] = aBitmapSlab;

        traceData[1] = aPagePower;

        traceData[2] = aTrimThreshold;

        BTraceContextN(BTrace::ETest1, BTrace::EHeapAlloc, (TUint32)this, 0, traceData, sizeof(traceData));

#endif

    }

RNewAllocator::SCell* RNewAllocator::GetAddress(const TAny* aCell) const

//

// As much as possible, check a cell address and backspace it

// to point at the cell header.

//

    {

    TLinAddr m = TLinAddr(iAlign - 1);

    __ASSERT_ALWAYS(!(TLinAddr(aCell)&m), HEAP_PANIC(ETHeapBadCellAddress));

    SCell* pC = (SCell*)(((TUint8*)aCell)-EAllocCellSize);

    __CHECK_CELL(pC);

    return pC;

    }

TInt RNewAllocator::AllocLen(const TAny* aCell) const

{

    if (ptrdiff(aCell, this) >= 0)

    {

        mchunkptr m = mem2chunk(aCell);

        return chunksize(m) - CHUNK_OVERHEAD; // Andrew: Picking up webkit change.

    }

    if (lowbits(aCell, pagesize) > cellalign)

        return header_size(slab::slabfor(aCell)->header);

    if (lowbits(aCell, pagesize) == cellalign)

        return *(unsigned*)(offset(aCell,-int(cellalign)))-cellalign;

    return paged_descriptor(aCell)->size;

}

TAny* RNewAllocator::Alloc(TInt aSize)

{

    __ASSERT_ALWAYS((TUint)aSize<(KMaxTInt/2),HEAP_PANIC(ETHeapBadAllocatedCellSize));

    TAny* addr;

#ifdef TRACING_ALLOCS

    TInt aCnt=0;

#endif

    Lock();

    if (aSize < slab_threshold)

    {

        TInt ix = sizemap[(aSize+3)>>2];

        ASSERT(ix != 0xff);

        addr = slab_allocate(slaballoc[ix]);

        if (addr) iTotalAllocSize += slaballoc[ix].size;

    }else if ((aSize >> page_threshold)==0)

        {

#ifdef TRACING_ALLOCS

        aCnt=1;

#endif

        addr = dlmalloc(aSize);

        }

    else

        {

#ifdef TRACING_ALLOCS

        aCnt=2;

#endif

        addr = paged_allocate(aSize);

        //attempt dlmalloc() if paged_allocate() fails. This can improve allocation chances if fragmentation is high in the heap.

        if (!addr) { // paged_allocator failed, try in dlmalloc

            addr = dlmalloc(aSize);

        }

    }