Logo Search packages:      
Sourcecode: u++ version File versions

uHeapLmmm.cc

//                              -*- Mode: C++ -*- 
// 
// uC++ Version 5.0.1, Copyright (C) Peter A. Buhr 1994
// 
// uHeapLmmm.cc -- Lean Mean Malloc Machine - a runtime configurable replacement
//                 for malloc.
// 
// Author           : Peter A. Buhr
// Created On       : Sat Nov 11 16:07:20 1988
// Last Modified By : Peter A. Buhr
// Last Modified On : Thu Sep  2 12:21:16 2004
// Update Count     : 640
//
// 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.1 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.
// 

#define __U_KERNEL__
#include <uC++.h>
#include <uHeapLmmm.h>
#include <uAlign.h>
#include <uProfiler.h>

//#include <uDebug.h>

#include <cstdio>
#include <cstring>
#include <new>
#include <unistd.h>                             // sbrk, sysconf


extern "C" void uDebugPrt( const char fmt[], ... );   // used by heap trace


#ifdef __U_DEBUG__
static bool uHeapBoot = false;                        // detect recursion during boot
#endif // __U_DEBUG__
static char uHeapStorage[sizeof(uHeapManager)] __attribute__(( aligned (16) )) = {0};

uHeapManager *uHeapManager::uHeapManagerInstance = NULL;
ptrdiff_t uHeapManager::PreAlloc = 0;
bool uHeapManager::uTraceAlloc = false;


static const unsigned char msbpostab[256] = {
    0,0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
    5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7 };

static size_t ceillog2( size_t i ) {
    size_t pos;

    if ( i >> 16 )
      if ( i >> 24 )
          pos = 24 + msbpostab[i >> 24];
      else
          pos = 16 + msbpostab[i >> 16];
    else
      if ( i >> 8 )
          pos =  8 + msbpostab[i >> 8];
      else
          pos =  0 + msbpostab[i];
    if ( 1ul << pos < i ) pos += 1;             // ceil
    return pos;
} // ceillog2


bool uTraceHeapOn() {
    bool temp = uHeapManager::uTraceAlloc;
    uHeapManager::uTraceAlloc = true;
    return temp;
} // uTraceHeapOn


bool uTraceHeapOff() {
    bool temp = uHeapManager::uTraceAlloc;
    uHeapManager::uTraceAlloc = false;
    return temp;
} // uTraceHeapOff


void uHeapManager::uNoMemory() {
    uAbort( ": heap memory exhausted at %lu bytes.\n"
          "Possible cause is very large memory allocation and/or large amount of unfreed storage allocated by the program or system/library routines.",
           (unsigned long int)((char *)(sbrk( 0 )) - (char *)(uHeapManager::uHeapManagerInstance->uHeapBegin)) );
} // uHeapManager::uNoMemory


inline void uHeapManager::uHeaders( char *name, void *addr, uStorage *&block, uFreeHeader *&freeElem, size_t &alignment ) {
#ifdef __U_DEBUG__
    if ( addr < uHeapBegin || uHeapEnd <= addr ) {
      uAbort( ": attempt to %s storage 0x%p outside the current heap range:0x%p to 0x%p.\n"
            "Possible cause is invalid pointer.",
            name, addr, uHeapBegin, uHeapEnd );
    } // if
#endif // __U_DEBUG__

    block = (uStorage *)( (char *)addr - sizeof(uStorage::uHeader) );
    freeElem = block->uHdr.uVar.home;
    // see memalign for explanation
    if ( uHeapBegin <= freeElem && freeElem < uHeapEnd ) { // free header within the heap ?
      block = (uStorage *)freeElem;
      // SKULLDUGGERY: see memalign
      alignment = (size_t)block->uHdr.uProfileMallocEntry;
      freeElem = block->uHdr.uVar.home;
    } // if

#ifdef __U_DEBUG__
    if ( freeElem < &freeLists[0] || &freeLists[31] < freeElem ) {
      uAbort( ": attempt to %s storage 0x%p with corrupted header.\n"
            "Possible cause is duplicate free on same block or overwriting of header information.",
            name, addr );
    } // if
#endif // __U_DEBUG__
} // uHeapManager::uHeaders


void *uHeapManager::uExtend( size_t size ) {
    extlock.acquire();
#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uExtend( %u ), uHeapBegin:0x%p, uHeapEnd:0x%p, uHeapRemaining:0x%x, sbrk:0x%p\n",
               this, size, uHeapBegin, uHeapEnd, uHeapRemaining, sbrk(0) );
#endif // __U_DEBUG_H__
    ptrdiff_t rem = uHeapRemaining - size;
    if ( rem < 0 ) {
      // If the size requested is bigger than the current remaining storage,
      // increase the size of the heap.

      size_t uDefault = uDefaultHeapExpansion();
      size_t uAmount = uCeiling( size > uDefault ? size : uDefault, uAlign() );
      if ( sbrk( uAmount ) == (void *)-1 ) {
#ifdef __U_DEBUG_H__
          uDebugPrt( "0x%x = (uHeap &)0x%p.uExtend( %u ), uHeapBegin:0x%p, uHeapEnd:0x%p, uHeapRemaining:0x%x, sbrk:0x%p\n",
                   NULL, this, size, uHeapBegin, uHeapEnd, uHeapRemaining, sbrk(0) );
#endif // __U_DEBUG_H__
          extlock.release();
          return NULL;
      } // if
#ifdef __U_DEBUG__
      // Set new memory to garbage so subsequent uninitialized usages might fail.
      memset( (char *)uHeapEnd + uHeapRemaining, '\377', uAmount );
#endif // __U_DEBUG__
      rem = uHeapRemaining + uAmount - size;
    } // if

    uStorage *block = (uStorage *)uHeapEnd;
    uHeapRemaining = rem;
    uHeapEnd = (char *)uHeapEnd + size;
#ifdef __U_DEBUG_H__
    uDebugPrt( "0x%p = (uHeap &)0x%p.uExtend( %u ), uHeapBegin:0x%p, uHeapEnd:0x%p, uHeapRemaining:0x%x, sbrk:0x%p\n",
               block, this, size, uHeapBegin, uHeapEnd, uHeapRemaining, sbrk(0) );
#endif // __U_DEBUG_H__
    extlock.release();
    return block;
} // uHeapManager::uExtend


void *uHeapManager::uDoMalloc( size_t size ) {
#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uDoMalloc( %u )\n", this, size );
#endif // __U_DEBUG_H__

    uStorage *block;

    // Look up size in the size list.  Make sure the user request includes
    // space for the header that must be allocated along with the block and is
    // a multiple of the alignment size.

    if ( size == 0 ) size = 1;
    uFreeHeader &freeElem = freeLists[ceillog2( size + sizeof(uStorage::uHeader) )]; // optimize subscripting
    size_t tsize = freeElem.blockSize;                // total space needed for request

#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uDoMalloc, size after lookup:%u\n", this, tsize );
#endif // __U_DEBUG_H__
    
    // Spin until the lock is acquired for this particular size of block.

    freeElem.lock.acquire();
    if ( freeElem.freeList != NULL ) {
      block = freeElem.freeList;
      freeElem.freeList = block->uHdr.uVar.next;
      freeElem.lock.release();
    } else {
      freeElem.lock.release();

      // Freelist for that size was empty, so carve it out of the heap if
      // there's enough left, or get some more and then carve it off.

      block = (uStorage *)uExtend( tsize );           // mutual exclusion on call
      if ( block == NULL ) return NULL;
    } // if

    block->uHdr.uVar.home = &freeElem;                // pointer back to free list of apropriate size
    block->uHdr.uProfileMallocEntry = NULL;           // profiler
    void *area = &(block->uData);               // adjust off header to user bytes
#ifdef __U_DEBUG__
    if ( uTraceAlloc ) {
      uDebugPrt( "0x%p = Malloc( %u ) (allocated %u)\n", area, size, tsize );
    } // if
#endif // __U_DEBUG__

    if ( uThisTask().uProfileActive && uProfiler::uProfiler_RegisterMemoryAllocate ) {
      block->uHdr.uProfileMallocEntry = (*uProfiler::uProfiler_RegisterMemoryAllocate)( uProfiler::uProfilerInstance, area, size, tsize ); 
    } // if
#ifdef __U_DEBUG_H__
    uDebugPrt( "0x%p = (uHeap &)0x%p.uDoMalloc\n", area, this );
#endif // __U_DEBUG_H__
    return area;
} // uHeapManager::uDoMalloc


void uHeapManager::uDoFree( void *addr ) {
#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uDoFree( 0x%p )\n", this, addr );
#endif // __U_DEBUG_H__

  if ( addr == NULL ) {
      if ( uThisTask().uProfileActive && uProfiler::uProfiler_RegisterMemoryDeallocate ) {
        (*uProfiler::uProfiler_RegisterMemoryDeallocate)( uProfiler::uProfilerInstance, addr, 0, 0 ); 
      } // if

#ifdef __U_DEBUG__
      if ( uTraceAlloc ) {
        uDebugPrt( "Free( 0x%p ) size:0\n", addr );
      } // if
#endif // __U_DEBUG__
      return;
    } // exit

#ifdef __U_DEBUG__
    if ( uHeapManager::uHeapManagerInstance == NULL ) {
      fprintf( stderr, "uDoFree( 0x%p ) called before heap is initialized.\n", addr );
      _exit( -1 );
    } // if
#endif // __U_DEBUG__

    uStorage *block;
    uFreeHeader *freeElem;
    size_t alignment;                           // not used (see realloc)
    uHeaders( "free", addr, block, freeElem, alignment );

    if ( uThisTask().uProfileActive && uProfiler::uProfiler_RegisterMemoryDeallocate ) {
      (*uProfiler::uProfiler_RegisterMemoryDeallocate)( uProfiler::uProfilerInstance, addr, freeElem->blockSize, block->uHdr.uProfileMallocEntry ); 
    } // if

#ifdef __U_DEBUG__
    if ( uTraceAlloc ) {
      uDebugPrt( "Free( 0x%p ) size:%u\n", addr, freeElem->blockSize );
    } // if
#endif // __U_DEBUG__

#ifdef __U_DEBUG__
    // Set free memory to garbage so subsequent usages might fail.
    memset( block, '\377', freeElem->blockSize );
#endif // __U_DEBUG__

#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uDoFree( 0x%p ) block:0x%p freeElem:0x%p\n", this, addr, &block, &freeElem );
#endif // __U_DEBUG_H__

    freeElem->lock.acquire();                   // acquire spin lock
    block->uHdr.uVar.next = freeElem->freeList;       // remove node from chain
    freeElem->freeList = block;
    freeElem->lock.release();                   // release spin lock

#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uDoFree( 0x%p ) returning free block in list 0x%x\n", this, addr, freeElem->blockSize );
#endif // __U_DEBUG_H__
} // uHeapManager::uDoFree


size_t uHeapManager::uCheckFree() {
    size_t total = 0;
    for ( int i = 0; i < 32; i += 1 ) {
      size_t size = freeLists[i].blockSize;
      for ( uStorage *p = freeLists[i].freeList; p; p = p->uHdr.uVar.next ) {
          total += size;
      } // for
    } // for
    return (char *)uHeapEnd - (char *)uHeapBegin - total;
} // uHeapManager::uCheckFree


uHeapManager::uHeapManager() {
#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uHeap()\n", this );
#endif // __U_DEBUG_H__
    for ( int i = 0; i < 32; i += 1 ) {               // initialize the free lists
      freeLists[i].blockSize = 1ul << i;
      freeLists[i].freeList = NULL;
    } // for

    char *end = (char *)sbrk( 0 );
    sbrk( (char *)uCeiling( (long unsigned int)end, uAlign() ) - end ); // move start of heap to multiple of alignment
    uHeapBegin = uHeapEnd = sbrk( 0 );                // get new start point
#ifdef __U_DEBUG_H__
    uDebugPrt( "(uHeap &)0x%p.uHeap() uHeapBegin:0x%p, uHeapEnd:0x%p\n", this, uHeapBegin, uHeapEnd );
#endif // __U_DEBUG_H__
    uHeapRemaining = 0;                         // don't pre-allocate storage that might not get used

    std::set_new_handler( uNoMemory );                // don't throw exception as the default
} // uHeapManager::uHeapManager


uHeapManager::~uHeapManager() {
#ifdef __U_DEBUG__
    size_t underby = uCheckFree() - uHeapManager::PreAlloc;
    if ( underby != 0 ) {
      // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
      fprintf( stderr, "uC++ Runtime warning (UNIX pid:%ld) : program terminating with %d(0x%x) bytes of storage allocated but not freed.\n"
             "Possible cause is unfreed storage allocated by the program or system/library routines called from the program.\n",
             (long int)getpid(), underby, underby ); // always print the UNIX pid
    } // if
#endif // __U_DEBUG__
} // uHeapManager::~uHeapManager


void uHeapManager::boot() {
    if ( ! uKernelModule::uKernelModuleInitialized ) {
      uKernelModule::startup();
    } // if
#ifdef __U_DEBUG__
    if ( uHeapBoot ) {                          // check for recursion during system boot
      // DO NOT USE STREAMS AS THEY MAY BE UNAVAILABLE AT THIS POINT.
      fprintf( stderr, "uHeapManager::boot() recursively invoked during system boot.\n" );
      _exit( -1 );
    } // if
    uHeapBoot = true;
#endif // __U_DEBUG__

    // SKULLDUGGERY: This ensures that calls to uThisCoroutine work before the
    // kernel is initialized.

    ((uBaseTask *)&uKernelModule::uTaskBootStorage)->uCurrCoroutine = (uBaseTask *)&uKernelModule::uTaskBootStorage;
    ((uBaseTask *)&uKernelModule::uTaskBootStorage)->uInheritTask = (uBaseTask *)&uKernelModule::uTaskBootStorage;
    uHeapManager::uHeapManagerInstance = new((void *)&uHeapStorage) uHeapManager;
} // uHeapManager::boot


void *uHeapManager::operator new( size_t, void *storage ) {
    return storage;
} // uHeapManager::operator new


void *uHeapManager::operator new( size_t size ) {
    return ::operator new( size );
} // uHeapManager::operator new


// Unnecessary to redefine __builtin_new, __builtin_vec_new, __builtin_delete
// as they call malloc and free, which are redefined below.


extern "C" {
void *malloc( size_t size ) {
    if ( uHeapManager::uHeapManagerInstance == NULL ) {
      uHeapManager::boot();
    } // if

    void *area = uHeapManager::uHeapManagerInstance->uDoMalloc( size );
#ifdef __U_DEBUG_H__
    uDebugPrt( "0x%p = malloc( %u )\n", area, size );
#endif // __U_DEBUG_H__
    return area;
} // malloc


void *calloc( size_t noOfElems, size_t elemSize ) {
    if ( uHeapManager::uHeapManagerInstance == NULL ) {
      uHeapManager::boot();
    } // if

    void *area = uHeapManager::uHeapManagerInstance->uDoMalloc( noOfElems * elemSize );
  if ( area == NULL ) return NULL;
    memset( area, '\0', noOfElems * elemSize );       // must set to zeros
#ifdef __U_DEBUG_H__
    uDebugPrt( "0x%p = calloc( %u, %u )\n", area, noOfElems, elemSize );
#endif // __U_DEBUG_H__
    return area;
} // calloc


void *realloc( void *addr, size_t size ) {
    if ( uHeapManager::uHeapManagerInstance == NULL ) {
      uHeapManager::boot();
    } // if

  if ( addr == NULL ) return uHeapManager::uHeapManagerInstance->uDoMalloc( size );
  if ( size == 0 ) {
      uHeapManager::uHeapManagerInstance->uDoFree( addr );
      return NULL;
    } // exit

    uHeapManager::uStorage *block;
    uHeapManager::uFreeHeader *freeElem;
    size_t alignment = 0;
    uHeapManager::uHeapManagerInstance->uHeaders( "realloc", addr, block, freeElem, alignment );

    // Subtract off storage before user location (handles memalign)
    size_t s = (char *)block + freeElem->blockSize - (char *)addr;
  if ( s >= size ) return addr;                       // already sufficient storage

    void *area;
    if ( alignment != 0 ) {                     // previous request memalign?
      area = memalign( alignment, size );       // create new area
    } else {
      area = malloc( size );                    // create new area
    } // if
  if ( area == NULL ) return NULL;
    memcpy( area, addr, s < size ? s : size );
    uHeapManager::uHeapManagerInstance->uDoFree( addr );
#ifdef __U_DEBUG_H__
    uDebugPrt( "0x%p = realloc( 0x%p, %u )\n", area, addr, size );
#endif // __U_DEBUG_H__
    return area;
} // realloc


void *memalign( size_t alignment, size_t size ) {
    if ( uHeapManager::uHeapManagerInstance == NULL ) {
      uHeapManager::boot();
    } // if

    // range check for alignment

    if ( alignment < sizeof(int) || ((alignment - 1) & alignment) != 0 ) {
      uAbort( ": alignment %lu for memory allocation is less than sizeof(int) and/or not a power of 2.",
            (unsigned long int)alignment );
    } // if

    // if alignment <= sizeof(uHeader), do normal malloc as two headers are
    // unnecessary

  if ( alignment <= sizeof(uHeapManager::uStorage::uHeader) ) {
      void *area = uHeapManager::uHeapManagerInstance->uDoMalloc( size );
#ifdef __U_DEBUG_H__
      uDebugPrt( "0x%p = memalign( %u, %u )\n", area, alignment, size );
#endif // __U_DEBUG_H__
      return area;
    } // exit

    // Allocate enough storage to guarantee an address on the alignment
    // boundary, and sufficient space after it for the storage size. This
    // happens automatically because the request is rounded up to the next
    // power of 2.
    char *area = (char *)uHeapManager::uHeapManagerInstance->uDoMalloc( size + alignment );
  if ( area == NULL ) return NULL;
    // Calculate address in the block of the "next" alignment address. Adding 1
    // ensures the user area does not start at "area" if it happens to be a
    // multiple of alignment.
    char *user = (char *)uCeiling( (long unsigned int)area + 1, alignment );
    // Create a fake header *before* the alignment location and point this
    // headers free-list pointer to the start of the actual storage block.
    // Hence, it is necessary to check if the free-list pointer is in the heap
    // to determine if the request has a fake or actual header.
    uHeapManager::uStorage *fake = (uHeapManager::uStorage *)(user - sizeof(uHeapManager::uStorage::uHeader));
    uHeapManager::uStorage *block = (uHeapManager::uStorage *)(area - sizeof(uHeapManager::uStorage::uHeader));
    // SKULLDUGGERY: Store alignment value as it is needed in realloc.  This
    // field is not used by the profiler; the profiler uses the field in the
    // fake header.
    block->uHdr.uProfileMallocEntry = (uMemoryInfoEntry *)alignment;
    fake->uHdr.uVar.home = (uHeapManager::uFreeHeader *)block;
#ifdef __U_DEBUG_H__
    uDebugPrt( "0x%p = memalign( %u, %u )\n", user, alignment, size );
#endif // __U_DEBUG_H__
    return user;
} // memalign


void *valloc( size_t size ) {
    return memalign( sysconf( _SC_PAGESIZE ), size );
} // valloc


void free( void *addr ) {
    uHeapManager::uHeapManagerInstance->uDoFree( addr );
#ifdef __U_DEBUG_H__
    uDebugPrt( "free( 0x%p )\n", addr );
#endif // __U_DEBUG_H__
} // free

} // extern "C"


// Local Variables: //
// compile-command: "gmake install" //
// End: //

Generated by  Doxygen 1.6.0   Back to index