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