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