/*---------------------------------------------------------------------------*
 *  pmalloc.c  *
 *                                                                           *
 *  Copyright 2007, 2008 Nuance Communciations, Inc.                               *
 *                                                                           *
 *  Licensed under the Apache License, Version 2.0 (the 'License');          *
 *  you may not use this file except in compliance with the License.         *
 *                                                                           *
 *  You may obtain a copy of the License at                                  *
 *      http://www.apache.org/licenses/LICENSE-2.0                           *
 *                                                                           *
 *  Unless required by applicable law or agreed to in writing, software      *
 *  distributed under the License is distributed on an 'AS IS' BASIS,        *
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * 
 *  See the License for the specific language governing permissions and      *
 *  limitations under the License.                                           *
 *                                                                           *
 *---------------------------------------------------------------------------*/


/* this source file is only used when PORTABLE_DINKUM_MEM_MGR is defined
 */
#ifdef PORTABLE_DINKUM_MEM_MGR

#include <stdlib.h>
#include <string.h> /* for memset */
#include "pmalloc.h"
#include "passert.h"
#include "ptypes.h"
#include "plog.h"

#undef malloc
#undef calloc
#undef realloc
#undef free

#ifdef __cplusplus
extern "C"
{
#endif

  /*
   * There are two controlling options within this scheme:
   *
   * STATIC_MEMORY_POOL: When defined, there is a static array from which memory is
   * allocated.  The size of this array is defined at compile time.  When undefined
   * (the default), the memory is allocated via malloc().  This code works under PSOS and
   * PSOSIM, but has not been tested anywhere else (4March02).
   * VOYAGER_KERNEL_MEMORY: When defined for the Voyager platform, it is similar to the
   * non-static memory pool, but the memory buffer is pre-defined, and is simply pointed
   * at by the pmalloc initializer.
   * RTXC_PARTITION_MEMORY: When defined for the RTXC operating system, uses a static kernel
   * partition resource for the memory chunk.
   * VOYAGER_KERNEL_MEMORY and RTXC_PARTITION_MEMORY are mutually exclusive and take precedence
   * over STATIC_MEMORY.
   *
  
   * the standard off-the-shelf Dinkumware software is pretty slow, primarily due to
   * scanning the free-memory linked list in PortFree(). If SPEEDUP is defined, then
   * split the memory pool into imaginary 'bins', and keep track of the first free list
   * entry in each bin. Then the linked list lookup can be MUCH faster, as you can
   * start very close to the final destination in the linked list.
   *
   * (If SPEEDUP_COMPARE is defined, then run BOTH the standard technique and the
   * speedup technique and compare the results.)
   */
  
  /* malloc function */
  _STD_BEGIN
  
  /* data *******************************************************************************/
  
#if defined(PORTABLE_DINKUM_MEM_MGR) || defined(PORTABLE_FIXED_SIZE_MEM_BLOCK_SCHEME)
  /* Verify that memory pool actually was created, because of the lack of structure, this is accessed externally */
  ESR_ReturnCode memory_pool_creation_status = ESR_FATAL_ERROR;
#endif
  
  /* static data */
  _Altab  _Aldata  = {0}; /* heap initially empty */
  psize_t  _Size_block = {SIZE_BLOCK}; /* preferred _Getmem chunk */
  
  /* Memory pool size */
#define MEM_SIZE_MB( mbytes )   ((mbytes) * 1024 * 1024 )
  
#ifndef MEM_SIZE
  /* If not defined on the command line, use default values. */
#define MEM_SIZE    MEM_SIZE_MB( 5 )
#endif
  
  /* Memory pool initialized */
  static int pmallocInitted = FALSE;  /* TRUE once initialized */
  
#ifdef STATIC_MEMORY_POOL
  /* The memory pool can either be statically allocated or require a one-time system malloc.
   * For VTB, the system was taking 2 seconds to zero the static memBuffer[] array at
   * boot time, since it's in the BSS segment. Therefore, for VTB, it is better to allocate
   * at run time.
   */
  static char memBuffer[MEM_SIZE];
#else
  static char *memBuffer;
#endif
  
  static psize_t memSize = MEM_SIZE;
  
  /* Memory pool free list */
  /* partition memory range into 'bins', and keep track of the first
   * free list entry in each bin. This is to speed up the linked-list search
   * that takes place when memory is freed.
   */
#define BIN_BITS         14   /* smaller number ==> more bins */
#define BIN_SIZE      16384   /* 2 ^ BIN_BITS */
  
#define __NUM_MEM_BINS(memPoolSize)  (((memPoolSize)/BIN_SIZE) + 5) /* 5 = extra for roundoff */
#define GET_MEM_BIN( _ptr_ )   (int)(((unsigned int)_ptr_ - (unsigned int)&memBuffer[0]) >> BIN_BITS)
  
#define NUM_MEM_BINS  __NUM_MEM_BINS(MEM_SIZE)
static _Cell				*binsFirstFreeCell[NUM_MEM_BINS+1] = {0};
  static psize_t    numMemBins;
  
  /* Memory Pool sbrk/getmem variables */
  
  static char *__heap_ptr = NULL;
  static char *__heap_end = NULL;
  static int  maxMemUsed = 0;
  
  /* Memory Pool initialization and _GetMem functions ************************************/
  
#if _USE_EXISTING_SYSTEM_NAMES
#define _Sbrk sbrk
#endif
  
  _STD_BEGIN
  
  void *_Sbrk(int incr)
  {
    char *ret;
    
    /* Subtract 1 from __heap_ptr so that the left hand side of the comparison evaluates to the address of the
       last address of the requested memory block */
    if ((__heap_ptr + incr - 1) > __heap_end) return(void *) - 1;
    
    ret = __heap_ptr;
    __heap_ptr += incr;
    maxMemUsed += incr;
    return (void *)ret;
  }
  
  void *_Getmem(psize_t size)
  { /* allocate raw storage */
    void *p;
    int isize = size;
    
    return (isize <= 0 || (p = _Sbrk(isize)) == (void *) - 1
            ? 0 : p);
  }
  _STD_END
  
  /* PortMallocInit() : initialize memory pool. There is no initialization needed for
   * a static memory pool. Otherwise, perform a one-time malloc from the OS.
   */
  void PortMallocInit(void)
  {
#if defined STATIC_MEMORY_POOL
    memSize = MEM_SIZE;
#else
    /* TODO: is malloc of binsFirstFreeCell safe under PSOS in all conditions ? */
    memBuffer    = (char *)malloc(memSize);
#if defined(PORTABLE_DINKUM_MEM_MGR) || defined(PORTABLE_FIXED_SIZE_MEM_BLOCK_SCHEME)
    if (memBuffer != NULL) /* For external access, check comment at top */
      memory_pool_creation_status = ESR_SUCCESS;
#endif
    numMemBins    = __NUM_MEM_BINS(memSize);
#endif /* #ifdef VOYAGER_KERNEL_MEMORY */
    
    passert(memBuffer != NULL);
    passert(binsFirstFreeCell != NULL);
    
    __heap_ptr = &memBuffer[0];
    __heap_end = &memBuffer[memSize-1];
    
    /* set initted flag so we only do this once */
    pmallocInitted = TRUE;
    maxMemUsed = 0;
    
    memset(&_Aldata, 0, sizeof(_Altab));
    
    memset(binsFirstFreeCell, 0, sizeof(_Cell*)*(NUM_MEM_BINS + 1));
  }
  
  void PortMallocTerm(void)
  {
#ifndef STATIC_MEMORY_POOL
    memSize = 0;
    free(memBuffer);
    memBuffer = NULL;
#if defined(PORTABLE_DINKUM_MEM_MGR) || defined(PORTABLE_FIXED_SIZE_MEM_BLOCK_SCHEME)
    memory_pool_creation_status = ESR_FATAL_ERROR; /* For external access, check comment at top */
#endif
#endif
    pmallocInitted = FALSE;
  }
  
  /* PortGetMaxMemUsed() : return the maximum real memory allocated.
   * There is another function of the same name in pmemory.cpp, for tracking
   * psos block memory. It uses #ifdef MEM_PSOS_BLOCK_SCHEME to enable.
   */
  int PortMallocGetMaxMemUsed(void)
  {
    return maxMemUsed;
  }
  
  /* PortMallocSetPoolSize( psize_t size ) : define size of memory pool.
   */
  void PortMallocSetPoolSize(psize_t size)
  {
#if !defined(STATIC_MEMORY_POOL) && !defined(VOYAGER_KERNEL_MEMORY) && !defined(RTXC_PARTITION_MEMORY)
    if (!pmallocInitted)
    {
      memSize = size;
    }
#else
    (void)size;
#endif
  }
  
  /* PortMallocGetPoolSize() : return size of memory pool.
   */
  psize_t PortMallocGetPoolSize(void)
  {
#if defined STATIC_MEMORY_POOL
    return MEM_SIZE;
#else
    return memSize;
#endif
  }
  
  /* debug *******************************************************************************/
  
  /* xalloc.h internal header - debugging components */
#if DEBUG
  
  int _OK_Cell(_Cell *p)
  {
    passert(SIZE_CELL <= p->_Size);
    return 1;
  }
  
  typedef struct _DB_Altab
  {
    psize_t total_heap;
    psize_t total_alloc;
    psize_t total_free;
  }
  _DB_Altab;
  
  _DB_Altab _DB_Altab_object = {0};
  
  void _UPD_Altab(psize_t d_heap, psize_t d_alloc, psize_t d_free)
  {
    _DB_Altab *pd = &_DB_Altab_object;
    pd->total_heap += d_heap;
    pd->total_alloc += d_alloc;
    pd->total_free += d_free;
  }
  
  int _OK_Altab(_Altab *p)
  {
    _DB_Altab *pd = &_DB_Altab_object;
    _Cell *q;
    psize_t total_free = 0;
    if (p->_Head == 0)
      return 1;
    for (q = p->_Head; q != 0; q = q->_Next)
    {
      total_free += q->_Size;
      _OK_Cell(q);
      if (q->_Next != 0)
      {
        passert(_PTR_NORM((char *)q + q->_Size) <=
                _PTR_NORM((char *)q->_Next));
        passert(_PTR_NORM(q) < _PTR_NORM(q->_Next));
      }
    }
    passert(pd->total_heap == pd->total_alloc + pd->total_free);
    passert(total_free == pd->total_free);
    return 1;
  }
#endif /* DEBUG */
  
  /* allocation functions ***************************************************************/
  
  static _Cell **findmem(psize_t size)
  { /* find storage */
    _Cell *q, **qb;
    
    for (; ;)
    { /* check freed space first */
      if ((qb = _Aldata._Plast) == 0)
      { /* take it from the top */
        for (qb = &_Aldata._Head; *qb != 0;
             qb = &(*qb)->_Next)
          if (size <= (*qb)->_Size)
            return (qb);
      }
      else
      { /* resume where we left off */
        for (; *qb != 0; qb = &(*qb)->_Next)
          if (size <= (*qb)->_Size)
            return (qb);
        q = *_Aldata._Plast;
        for (qb = &_Aldata._Head; *qb != q;
             qb = &(*qb)->_Next)
          if (size <= (*qb)->_Size)
            return (qb);
      }
      { /* try to buy more space */
        psize_t bs;
        
        for (bs = _Size_block; ; bs >>= 1)
        { /* try larger blocks first */
          if (bs < size)
            bs = size;
          if ((q = (_Cell *)_Getmem(bs)) != 0)
            break;
          else if (bs == size)
            return (0); /* no storage */
        }
        /* got storage: add to heap and retry */
        q->_Size = bs;
        _UPD_Altab(q->_Size, q->_Size, 0); /* heap=alloc+free */
        PortFree((char *)q + CELL_OFF);
      }
    }
  }
  
  
  void *(PortMalloc)(psize_t size_arg)
  { /* allocate a data object on the heap */
    _Cell *q, **qb;
#ifdef SPEEDUP
    int qbsBin;
    int qbNextBin;
#endif /* SPEEDUP */
    psize_t size;
    
    passert(pmallocInitted);
    
    size = (size_arg + (CELL_OFF + M_MASK)) & ~M_MASK;
    
    _OK_Altab(&_Aldata);
    if (size <= size_arg)
      return (0); /* size_arg too large */
    if (size < SIZE_CELL) /* round up size */
      size = SIZE_CELL;
    if ((qb = findmem(size)) == 0)
      return (0);
    q = *qb;
    if (q->_Size - SIZE_CELL < size)
    {
      /* use entire cell (there's not enough space to carve out a new cell from this one) */
#ifdef SPEEDUP
      /* remove *qb cell from free list.
       * careful : the Next pointer may be in a different bin.
       */
      qbsBin = GET_MEM_BIN(*qb);
      
      /* Check whether the cell is at the end of the 'free' linked-list */
      if (0 != ((*qb)->_Next))
      {
        /* The cell is not at the end of the free linked-list; find out which bin the next free cell is in */
        qbNextBin = GET_MEM_BIN((*qb)->_Next);
        
        if (qbsBin == qbNextBin)
        {
          if (binsFirstFreeCell[qbsBin] == *qb)
          {
            /* The allocated cell was the first free cell in the bin; update the first free cell
               pointer to point to the next free cell */
            binsFirstFreeCell[qbsBin] = (*qb)->_Next;
          }
        }
        else
        {
          if (binsFirstFreeCell[qbsBin] == *qb)
          {
            /* The allocated cell was the only free cell in the bin; update the first free cell
               pointer to point to NULL */
            
            binsFirstFreeCell[qbsBin] = 0;
          }
        }
      }
      else
      {
        /* Cell is at the end of the 'free' linked-list */
        if (binsFirstFreeCell[qbsBin] == *qb)
        {
          /* The allocated cell was the first free cell in the bin; there are no following free cells
             so set the first free cell pointer to NULL */
          binsFirstFreeCell[qbsBin] = 0;
        }
      }
#endif /* SPEEDUP */
      *qb = q->_Next;
    }
    else
    { /* peel off a residual cell */
      *qb = (_Cell *)((char *)q + size);
      (*qb)->_Next = q->_Next;
      (*qb)->_Size = q->_Size - size;
      q->_Size = size;
#ifdef SPEEDUP
      /* remove q from free list, and add *qb to free list.
       * Do this as two separate steps because they may be in 2 different bins.
       */
      /* remove q from free list */
      if (binsFirstFreeCell[GET_MEM_BIN(q)] == q)
        binsFirstFreeCell[GET_MEM_BIN(q)] = 0;
      /* now add *qb to its bin's free list if it's the first */
      qbsBin = GET_MEM_BIN(*qb);
      if ((binsFirstFreeCell[qbsBin] == 0) || (*qb < binsFirstFreeCell[qbsBin]))
        binsFirstFreeCell[qbsBin] = *qb;
#endif /* SPEEDUP */
    }
    _Aldata._Plast = qb; /* resume scan here */
    _UPD_Altab(0, q->_Size, -q->_Size); /* heap=alloc+free */
    _OK_Altab(&_Aldata);
    return ((char *)q + CELL_OFF);
  }
  _STD_END
  
  
  /* free function */
  _STD_BEGIN
  
  void(PortFree)(void *ptr)
  { /* free an allocated data object */
    register _Cell *q;
    register psize_t size;
#ifdef SPEEDUP
    int binNum;
    int binIndex;
    int qNextBin;
    int qNextNextBin;
#endif /* SPEEDUP */
    static int portFreeCount = 0;
    portFreeCount++;
    
    passert(pmallocInitted);
    
    _OK_Altab(&_Aldata);
    if (ptr == 0)
      return;
    q = (_Cell *)((char *)ptr - CELL_OFF);
    size = q->_Size;
#ifdef SPEEDUP
    binNum = GET_MEM_BIN(q);
#endif /* SPEEDUP */
    if (size < SIZE_CELL || (size & M_MASK) != 0)
      return; /* erroneous call, bad count */
    if (_Aldata._Head == 0
        || _PTR_NORM(q) < _PTR_NORM(_Aldata._Head))
    { /* insert at head of list */
      q->_Next = _Aldata._Head;
      _Aldata._Head = q;
#ifdef SPEEDUP
      /* always the start of a bin */
      binsFirstFreeCell[binNum] = q;
#endif /* SPEEDUP */
    }
    else
    { /* scan for insertion point */
      register _Cell *qp = _Aldata._Head;
      register char *qpp;
      register _Cell *nextCell;
#if !defined SPEEDUP || defined SPEEDUP_COMPARE
      _Cell *savedQp;
      
      /* this search loop is where all the time is spent */
      while ((nextCell = qp->_Next) != 0
             && _PTR_NORM(nextCell) < _PTR_NORM(q))
        qp = qp->_Next;
      savedQp = qp;
#endif /* SPEEDUP */
      
#ifdef SPEEDUP
      /* this is where the SPEEDUP code is sped up : start with the bin's first free cell */
      _Cell *firstFreeInBin = binsFirstFreeCell[binNum];
      if ((firstFreeInBin != 0) && (q > firstFreeInBin))
      {
        qp = firstFreeInBin;
        while ((nextCell = qp->_Next) != 0
               && _PTR_NORM(nextCell) < _PTR_NORM(q))
        {
          qp = qp->_Next;
        }
      }
      else
      {
        /* go back to the previous non-zero bin */
        qp = NULL;  /* for diagnostics */
        for (binIndex = binNum; binIndex >= 0; binIndex--)
        {
          if ((binsFirstFreeCell[binIndex] != 0) && (q > binsFirstFreeCell[binIndex]))
          {
            qp = binsFirstFreeCell[binIndex];
            break;
          }
        }
        /* this code for diagnostic purposes to see how often it happens. otherwise,
         * qp could have been set to _Aldata._Head prior to the binIndex loop above.
         */
        if (qp == NULL)
        {
          qp = _Aldata._Head;
        }
        
        /* find the free cell location */
        while ((nextCell = qp->_Next) != 0
               && _PTR_NORM(nextCell) < _PTR_NORM(q))
          qp = qp->_Next;
      }
      
#ifdef SPEEDUP_COMPARE
      if (qp != savedQp)
        printf("oops \n");
#endif /* SPEEDUP_COMPARE */
#endif /* SPEEDUP */
        
#if !defined SPEEDUP || defined SPEEDUP_COMPARE
      qp = savedQp;
#endif /* SPEEDUP */
      
      qpp = (char *)qp + qp->_Size;
      if (_PTR_NORM((char *)q) < _PTR_NORM(qpp))
        return; /* erroneous call, overlaps qp */
      else if (_PTR_NORM(qpp) == _PTR_NORM((char *)q))
      { /* merge qp and q (merge with prior cell) */
        /* nothing to do to bin's free list here */
        qp->_Size += q->_Size;
        q = qp;
      }
      else if (qp->_Next != 0 && _PTR_NORM((char *)qp->_Next)
               < _PTR_NORM((char *)q + q->_Size))
        return; /* erroneous call, overlaps qp->_Next */
      else
      { /* splice q after qp */
#ifdef SPEEDUP
        /* add 1 entry here - this could change first entry in q's bin */
        _Cell *firstFree = binsFirstFreeCell[binNum];
        if ((firstFree == 0) || (q < firstFree))
          binsFirstFreeCell[binNum] = q;
#endif /* SPEEDUP */
        q->_Next = qp->_Next;
        qp->_Next = q;
      }
    }
    if (q->_Next != 0 && _PTR_NORM((char *)q + q->_Size)
        == _PTR_NORM((char *)q->_Next))
    { /* merge q and q->_Next (merge with latter cell) */
#ifdef SPEEDUP
      /* lose 1 cell here - this could change first entry in bin.
       * if q->_Next was first in bin, now it's its Next.
       * careful : watch for next being in a different bin.
       */
      qNextBin = GET_MEM_BIN(q->_Next);
      
      if (binsFirstFreeCell[qNextBin] == q->_Next)
      {
        /* The q->_Next cell is the first free cell in its bin; set the first free cell
           pointer to NULL for now; if there is another free cell in the same bin then
           the first free cell pointer will be updated in next 'if' code block */
        binsFirstFreeCell[qNextBin] = 0;
        
        /* If there is another free cell after q->_Next and it's in the same bin then
           update the first free cell pointer if necessary */
        if (0 != (q->_Next->_Next))
        {
          qNextNextBin = GET_MEM_BIN(q->_Next->_Next);
          
          /* The first free cell pointer for q->_Next->_Next's bin can only be set to 0
             by the code above; if it is 0 then q->_Next->_Next must be the first free
             cell in the bin */
          if (0 == binsFirstFreeCell[qNextNextBin])
          {
            binsFirstFreeCell[qNextNextBin] = q->_Next->_Next;
          }
        }
      }
#endif /* SPEEDUP */
      _Aldata._Plast = 0; /* deoptimize for safety */
      q->_Size += q->_Next->_Size;
      q->_Next = q->_Next->_Next;
    }
    _UPD_Altab(0, -size, size); /* heap=alloc+free */
    _OK_Altab(&_Aldata);
    /* every successful free "falls off" here */
  }
  _STD_END
  
#ifdef __cplusplus
} /* end extern "C" */
#endif

#endif /* PORTABLE_DINKUM_MEM_MGR */