PikeAero::CMemHeap Class Reference

#include <cmemheap.h>

Data Structures
struct	FreeListBlock
Static Public Member Functions
static CMachine::ubit32	available ()
static CMachine::ubit8 *	bottom ()
static void	compress ()
static void	free (void *ptr)
static void	initialize ()
static void *	malloc (CMachine::bit32 size)
static void *	realloc (void *ptr, CMachine::bit32 size)
static CMachine::ubit8 *	top ()
static CMachine::ubit32	used ()
Static Private Member Functions
static CMachine::ubit32 mFreeCount	__attribute__ ((aligned))
static CMachine::bit32 mFreeListSize	__attribute__ ((aligned))
static CMachine::ubit8 mHeap[]	__attribute__ ((aligned(4)))
static FreeListBlock *	_freelist (CMachine::bit32 i)
static FreeListBlock *	_freelist_alloc (CMachine::bit32 size)
static FreeListBlock *	_freelist_append (FreeListBlock *f)
static void	_freelist_compress (void)
static void	_freelist_defragment (void)
static FreeListBlock *	_freelist_find (CMachine::bit32 size)
static FreeListBlock *	_freelist_findfriend (FreeListBlock *f)
static void	_freelist_free (CMachine::bit32 i)
static CMachine::bit32	_freelist_locate (void *ptr)
static bool	_freelist_remove (CMachine::bit32 index)

---

Detailed Description

Implements a memory heap.

Author:

Michael Sharkey <mike@pikeaero.com>

Definition at line 32 of file cmemheap.h.

---

Member Function Documentation

static CMachine::ubit32 mFreeCount PikeAero::CMemHeap::__attribute__

(

(aligned)

)

[static, private]

static CMachine::bit32 mFreeListSize PikeAero::CMemHeap::__attribute__

(

(aligned)

)

[static, private]

static CMachine::ubit8 mHeap [] PikeAero::CMemHeap::__attribute__

(

(aligned(4))

)

[static, private]

CMemHeap::FreeListBlock * PikeAero::CMemHeap::_freelist

(

CMachine::bit32

i

)

[static, private]

Return a pointer to the FreeListBlock corresponding to freelist offset i.

_freelist() - return a pointer to a freelist entry from an index number.

Definition at line 65 of file cmemheap.cpp.

Referenced by _freelist_free().

{
    FreeListBlock* f = (FreeListBlock*)NULL;
    if ( i < mFreeListSize && mFreeListSize > 0 )
    {
        f = (FreeListBlock*)&mHeap[i*sizeof(FreeListBlock)];
    }
    return f;
}

Here is the caller graph for this function:

CMemHeap::FreeListBlock * PikeAero::CMemHeap::_freelist_alloc

(

CMachine::bit32

size

)

[static, private]

Allocate a FreeListBlock of size and return a pointer to the FreeListBlock or NULL if failed.

_freelist_alloc - attempt to find a chunk, and if found, create a FreeListBlock, adjust the freelist, and return a pointer to the FreeListBlock struct. Allocates from top of heap downward toward freelist.

first, attemp to find a chunk that will fit....

The simple case, we found a chuck that fits exactly...

Create a new free list entry and take some memory from the free block that we found, then append to freelist.

fetch the pointer to the newly allocated freelist entry.

The heap is probably full to the point that we can't allocate a new freelist entry, so let's undo and return an error...

Definition at line 316 of file cmemheap.cpp.

References _freelist_append(), and _freelist_find().

Referenced by malloc().

{
    /**
    ** first, attemp to find a chunk that will fit....
    */
    FreeListBlock* f = _freelist_find(size);
    if ( f != (FreeListBlock*)NULL )
    {
        FreeListBlock f_new;
        FreeListBlock* ff;
        /**
        ** The simple case, we found a chuck that fits exactly...
        */
        if ( f->size == size )
        {
            f->free = false;
            return f;
        }
        /**
        ** Create a new free list entry and take some memory from
        ** the free block that we found, then append to freelist.
        */
        f_new.free = false;
        f_new.p = &f->p[f->size-size];
        f_new.size = size;
        f->size -= size;
        ff = _freelist_append(&f_new);
        if ( ff != (FreeListBlock*)NULL )
        {
            /** fetch the pointer to the newly allocated freelist entry. */
            f = ff;
        } else {
            /**
            ** The heap is probably full to the point that we can't allocate
            ** a new freelist entry, so let's undo and return an error...
            */
            f->size += size;
            return (FreeListBlock*)NULL;
        }
    }
    return f;
}

Here is the call graph for this function:

Here is the caller graph for this function:

CMemHeap::FreeListBlock * PikeAero::CMemHeap::_freelist_append

(

FreeListBlock *

f

)

[static, private]

Append a FreeListBlock to the freelist and return a pointer to it.

_freelist_append - append a FreeListBlock to the freelist the contents of the input FreeListBlock struct are copied , so the caller maintains pointer ownership of the input pointer.

Get the target destination for the new freelist entry as well as the new target destination for the new free heap base..

Resize the free pointer that's pointi to the base of the heap area..

we found it, now just resize it and point to the new heap base...

this is an already allocated block. this means the heap is very full and we are having freelist allocation problems. Let's not push it....sorry...

We've sucessfully made room, so now copy the new freelist entry in the freed up heap slot and increment the freelist size.

Definition at line 97 of file cmemheap.cpp.

References _fast_freelist, and memcpy.

Referenced by _freelist_alloc(), and initialize().

{
    /**
     ** Get the target destination for the new freelist entry as well
     ** as the new target destination for the new free heap base..
     */
    CMachine::ubit8* dst = &mHeap[mFreeListSize*sizeof(FreeListBlock)];
    CMachine::ubit8* hbase = &mHeap[(mFreeListSize+1)*sizeof(FreeListBlock)];

    /**
     ** Resize the free pointer that's pointi to the base of the heap
     ** area..
     */
    CMachine::bit32 i;
    for( i=mFreeListSize-1; i >=0; i-- )
    {
        FreeListBlock* f = _fast_freelist(i);
        if ( f->p == dst )
        {
            if ( f->free )
            {
                /**  we found it, now just resize it and point to the new heap base... */
                f->p = hbase;
                f->size -= sizeof(FreeListBlock);
            }
            else
            {
                /**
                ** this is an already allocated block.
                ** this means the heap is very full and
                ** we are having freelist allocation
                ** problems. Let's not push it....sorry...
                */
                return (FreeListBlock*)NULL;
            }
        }
    }
    /**
    ** We've sucessfully made room, so now copy the new freelist
    ** entry in the freed up heap slot and increment the freelist size.
    */
    memcpy(dst,f,sizeof(FreeListBlock));
    ++mFreeListSize;
    return (FreeListBlock*)dst;
}

Here is the caller graph for this function:

void PikeAero::CMemHeap::_freelist_compress

(

void

)

[static, private]

Remove FreeListBlocks from the freelist which have no size

_freelist_compress - remove 0 size blocks

Definition at line 188 of file cmemheap.cpp.

References _fast_freelist, and _freelist_remove().

Referenced by _freelist_defragment().

{
    CMachine::bit32     i;
    bool    clean;
    do {
        clean=true;
        for( i=0; i < mFreeListSize; i++ )
        {
            FreeListBlock* f = _fast_freelist(i);
            if ( f->size == 0 )
            {
                _freelist_remove(i);
                clean=false;
                break;
            }
        }
    } while (!clean);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void PikeAero::CMemHeap::_freelist_defragment

(

void

)

[static, private]

Attempt to re-integrate previously split blocks.

_freelist_defragment - attempt to re-integrate previously split blocks.

Definition at line 212 of file cmemheap.cpp.

References _fast_freelist, _freelist_compress(), and _freelist_findfriend().

Referenced by _freelist_free(), and compress().

{
    CMachine::bit32     i;
    bool    clean;
    mFreeCount=0;
    do
    {
        clean=true;
        for( i=0; i < mFreeListSize; i++ )
        {
            FreeListBlock* f = _fast_freelist(i);
            if ( f != (FreeListBlock*)NULL && f->free == true && f->size != 0 )
            {
                FreeListBlock* ff = _freelist_findfriend(f);
                if (  ff != (FreeListBlock*)NULL && ff->size != 0 )
                {
                    if ( f->p == &(ff->p[ff->size]) )
                    {
                        ff->size += f->size;
                        f->size=0;
                    }
                    else if ( ff->p == &(f->p[f->size]) )
                    {
                        f->size += ff->size;
                        ff->size=0;
                    }
                    clean=false;
                    break;
                }
            }
        }
    } while(!clean);
    _freelist_compress();
}

Here is the call graph for this function:

Here is the caller graph for this function:

CMemHeap::FreeListBlock * PikeAero::CMemHeap::_freelist_find

(

CMachine::bit32

size

)

[static, private]

Attempt to find a FreeListBlock with enough memory to fit size

_freelist_find - find a free block with enough space to fit requested size.

First, try to find a chuck that fits exactly....

Second, try to find a chuck that fits pretty good.... This assumes that much of the time we will be aloocating objects of the same size, so we look for a block which is at no more than twice the size of what we need so that the remaining free block will at least be able to allocate another of the same object size.

Third, try to find a chuck that fits at all....

Forth, no matching chunk was found...return NULL..

Definition at line 266 of file cmemheap.cpp.

References _fast_freelist.

Referenced by _freelist_alloc().

{
    /**
    ** First, try to find a chuck that fits exactly....
    */
    for( CMachine::bit32 i=mFreeListSize-1; i >= 0; i-- )
    {
        FreeListBlock* f = _fast_freelist(i);
        if ( f->free && f->size == size )
        {
            return f;
        }
    }
    /**
    ** Second, try to find a chuck that fits pretty good....
    ** This assumes that much of the time we will be aloocating
    ** objects of the same size, so we look for a block which is at no more than
    ** twice the size of what we need so that the remaining free block will
    ** at least be able to allocate another of the same object size.
     */
    for( CMachine::bit32 i=mFreeListSize-1; i >= 0; i--  )
    {
        FreeListBlock* f = _fast_freelist(i);
        if ( f->free && f->size > size && f->size <= (size*2) )
        {
            return f;
        }
    }
    /**
    ** Third, try to find a chuck that fits at all....
    */
    for( CMachine::bit32 i=0; i < mFreeListSize; i++ )
    {
        FreeListBlock* f = _fast_freelist(i);
        if ( f->free && f->size >= size )
        {
            return f;
        }
    }
    /**
    ** Forth, no matching chunk was found...return NULL..
    */
    return (FreeListBlock*)NULL;
}

Here is the caller graph for this function:

CMemHeap::FreeListBlock * PikeAero::CMemHeap::_freelist_findfriend

(

FreeListBlock *

f

)

[static, private]

Attempt to find another free block which is contiguous with respect to the input block. Return NULL if not found

_freelist_findfriend - find another free block which is contiguous with respect to the input block.

Definition at line 165 of file cmemheap.cpp.

References _fast_freelist.

Referenced by _freelist_defragment().

{
    if ( f->free )
    {
        CMachine::bit32 i;
        for( i=0; i < mFreeListSize; i++ )
        {
            FreeListBlock* ff = _fast_freelist(i);
            if ( ff->free && ff->size > 0)
            {
                if ( f->p == &(ff->p[ff->size]) || ff->p == &(f->p[f->size]) )
                {
                    return ff;
                }
            }
        }
    }
    return (FreeListBlock*)NULL;
}

Here is the caller graph for this function:

void PikeAero::CMemHeap::_freelist_free

(

CMachine::bit32

i

)

[static, private]

Free a FreeListBlock from the freelist. The data pointer is assumed to have been already freed

_freelist_free - free a block

Definition at line 250 of file cmemheap.cpp.

References _freelist(), _freelist_defragment(), and DEFRAG_THRESHOLD.

Referenced by free(), and realloc().

{
    FreeListBlock* f = _freelist(i);
    if ( f != NULL )
    {
        f->free = true;
        if ( ++mFreeCount > DEFRAG_THRESHOLD )
        {
            _freelist_defragment();
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

CMachine::bit32 PikeAero::CMemHeap::_freelist_locate

(

void *

ptr

)

[static, private]

Get the freelist offset from a FreeListBlock pointer

_freelist_locate - attempt to locate a freelist entry based on a heap memory pointer.

Definition at line 79 of file cmemheap.cpp.

References _fast_freelist.

Referenced by free(), and realloc().

{
    for(CMachine::bit32 i=mFreeListSize-1; i >= 0; i-- )
    {
        FreeListBlock* f =  _fast_freelist(i);
        if ( f->p == (CMachine::ubit8*)ptr )
        {
            return i;
        }
    }
    return (-1);
}

Here is the caller graph for this function:

bool PikeAero::CMemHeap::_freelist_remove

(

CMachine::bit32

index

)

[static, private]

Remove a FreeListBlock from the freelist referenced by offset i

_freelist_remove - remove a FreeListBlock from the freelist based on an index reference.

Definition at line 147 of file cmemheap.cpp.

References memmove.

Referenced by _freelist_compress().

{
    if ( index < mFreeListSize && mFreeListSize > 0 )
    {
        CMachine::bit32 dst = index*sizeof(FreeListBlock);
        CMachine::bit32 src = (index+1)*sizeof(FreeListBlock);
        CMachine::bit32 len = (mFreeListSize-index)*sizeof(FreeListBlock);
        memmove(&mHeap[dst],&mHeap[src],len);
        --mFreeListSize;
        return true;
    }
    return false;
}

Here is the caller graph for this function:

CMachine::ubit32 PikeAero::CMemHeap::available

(

)

[static]

available() Total up the amout of available memory on the heap.

Definition at line 464 of file cmemheap.cpp.

References _fast_freelist.

Referenced by PikeAero::CTaskConsolePacket::monitor(), and PikeAero::CTaskConsole::monitor().

{
    CMachine::ubit32 size=0;
    for( CMachine::bit32 i=0; i < mFreeListSize; i++ )
    {
        FreeListBlock* f = _fast_freelist(i);
        if ( f->free )
        {
            size += f->size - sizeof( FreeListBlock );
        }
    }
    return size;
}

Here is the caller graph for this function:

CMachine::ubit8 * PikeAero::CMemHeap::bottom

(

)

[static]

bottom() - return the address of the byte at the bottom of the heap space

Definition at line 57 of file cmemheap.cpp.

Referenced by PikeAero::CTaskConsolePacket::monitor(), and PikeAero::CTaskConsole::monitor().

{
    return &mHeap[0];
}

Here is the caller graph for this function:

static void PikeAero::CMemHeap::compress

(

)

[inline, static]

Definition at line 44 of file cmemheap.h.

References _freelist_defragment().

Referenced by PikeAero::CTaskQueue::initialize().

{_freelist_defragment();}

Here is the call graph for this function:

Here is the caller graph for this function:

void PikeAero::CMemHeap::free

(

void *

ptr

)

[static]

free() frees the memory space pointed to by ptr, which must have been returned by a previous call to malloc() or realloc(). Otherwise, or if free(ptr) has already been called before, undefined behavior occurs. If ptr is NULL, no opera‐ tion is performed.

Definition at line 436 of file cmemheap.cpp.

References _freelist_free(), and _freelist_locate().

Referenced by PikeAero::CByteArray::clear(), PikeAero::CArray< T >::clear(), PikeAero::CConfiguration::createVolatileRecord(), PikeAero::CConfiguration::disposeVolatile1DMap(), PikeAero::CConfiguration::disposeVolatile2DMap(), PikeAero::CConfiguration::disposeVolatileRecord(), PikeAero::CObject::operator delete(), PikeAero::CObject::operator delete[](), realloc(), PikeAero::CMap::unload(), and PikeAero::CObject::~CObject().

{
    CMachine::bit32 i = _freelist_locate(ptr);
    if ( i >= 0 ) {
        _freelist_free(i);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void PikeAero::CMemHeap::initialize

(

void

)

[static]

FIXME - Make this class thread-safe using CMutexLock when accessing the freelist table. FIXME - Emit a CEventTriggerSourceprogramFault on allocation/free errors TODO - Provide an interface for retrieving information about memory usage and fragmentation TODO - use const where applicable

initialize() - initialize memory.

Definition at line 38 of file cmemheap.cpp.

References _freelist_append().

{
    FreeListBlock f;

    mFreeListSize=0;
    mFreeCount=0;
    f.free = true;
    f.p = &mHeap[sizeof(FreeListBlock)];
    f.size = sizeof(mHeap)-sizeof(FreeListBlock);
    _freelist_append(&f);
}

Here is the call graph for this function:

void * PikeAero::CMemHeap::malloc

(

CMachine::bit32

size

)

[static]

malloc() allocates size bytes and returns a pointer to the allocated memory. The memory is not cleared. If size is 0, then malloc() returns either NULL, or a unique pointer value that can later be successfully passed to free().

Adjust size to end up on 32 bit boundary...

Definition at line 363 of file cmemheap.cpp.

References _freelist_alloc().

Referenced by PikeAero::CConfiguration::createVolatile1DMap(), PikeAero::CConfiguration::createVolatile2DMap(), PikeAero::CConfiguration::createVolatileRecord(), PikeAero::CEventQueue::initialize(), PikeAero::CObject::installCallback(), PikeAero::CMap::load(), PikeAero::CObject::operator new(), PikeAero::CObject::operator new[](), and realloc().

{
    /**
    ** Adjust size to end up on 32 bit boundary...
    */
    while ( (size & 0x03) != 0x00 )
    {
        ++size;
    }
    if ( size > 0 )
    {
        FreeListBlock* f = _freelist_alloc(size);
        if ( f != (FreeListBlock*)NULL )
        {
            return f->p;
        }
    }
    return (void*)NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void * PikeAero::CMemHeap::realloc	(	void *	ptr,
		CMachine::bit32	size
	)			[static]

realloc() changes the size of the memory block pointed to by ptr to size bytes. The contents will be unchanged to the minimum of the old and new sizes; newly allocated memory will be uninitialized. If ptr is NULL, then the call is equivalent to mal‐ loc(size), for all values of size; if size is equal to zero, and ptr is not NULL, then the call is equivalent to free(ptr). Unless ptr is NULL, it must have been returned by an earlier call to malloc() or realloc(). If the area pointed to was moved, a free(ptr) is done.

Adjust size to end up on 32 bit boundary...

Definition at line 390 of file cmemheap.cpp.

References _fast_freelist, _freelist_free(), _freelist_locate(), free(), malloc(), and memmove.

Referenced by PikeAero::CObjectList::append(), PikeAero::CObjectList::insert(), PikeAero::CObject::installCallback(), PikeAero::CObjectList::remove(), PikeAero::CByteArray::resize(), and PikeAero::CArray< T >::resize().

{
    /**
    ** Adjust size to end up on 32 bit boundary...
    */
    while ( (size & 0x03) != 0x00 )
    {
        ++size;
    }
    if ( ptr != (void*)NULL )
    {
        if ( size == 0 )
        {
            free( ptr );
        }
        else
        {
            CMachine::bit32 i = _freelist_locate(ptr);
            if ( i >= 0 )
            {
                FreeListBlock* f = _fast_freelist(i);
                CMachine::bit32 s = f->size;
                CMachine::ubit8* p = (CMachine::ubit8*)f->p;
                if ( f->size < size )
                {
                    CMachine::ubit8* pp = (CMachine::ubit8*)malloc(size);
                    _freelist_free(i);
                    if ( pp != (CMachine::ubit8*)NULL )
                    {
                        memmove(pp,p,s);
                    }
                    return pp;
                }
                return f->p;
            }
        }
        return((void*)NULL);
    }
    return malloc(size);
}

Here is the call graph for this function:

Here is the caller graph for this function:

CMachine::ubit8 * PikeAero::CMemHeap::top

(

)

[static]

top() - return the address of the byte at the top of the heap space

Definition at line 51 of file cmemheap.cpp.

References HEAP_SIZE.

Referenced by PikeAero::CTaskConsolePacket::monitor(), and PikeAero::CTaskConsole::monitor().

{
    return &mHeap[HEAP_SIZE-1];
}

Here is the caller graph for this function:

CMachine::ubit32 PikeAero::CMemHeap::used

(

)

[static]

used() Total up the amout of used memory on the heap.

Definition at line 447 of file cmemheap.cpp.

References _fast_freelist.

Referenced by PikeAero::CTaskConsolePacket::monitor(), and PikeAero::CTaskConsole::monitor().

{
    CMachine::ubit32 size=0;
    for( CMachine::bit32 i=0; i < mFreeListSize; i++ )
    {
        FreeListBlock* f = _fast_freelist(i);
        if ( !f->free )
        {
            size += f->size + sizeof( FreeListBlock );
        }
    }
    return size;
}

Here is the caller graph for this function:

---

The documentation for this class was generated from the following files:

• cmemheap.h
• cmemheap.cpp