Mercurial > flash_v2
diff packages/services/memalloc/common/current/include/mvarimpl.inl @ 115:6ed91473a1cd ecos-sw-2000-08-21
Merge from eCos master repository on 2000-08-21-22:40:54-BST
| author | jlarmour |
|---|---|
| date | Fri, 25 Aug 2000 17:32:38 +0000 |
| parents | |
| children | 511f4dc167f6 |
line wrap: on
line diff
new file mode 100644 --- /dev/null +++ b/packages/services/memalloc/common/current/include/mvarimpl.inl @@ -0,0 +1,431 @@ +#ifndef CYGONCE_MEMALLOC_MVARIMPL_INL +#define CYGONCE_MEMALLOC_MVARIMPL_INL + +//========================================================================== +// +// mvarimpl.inl +// +// Memory pool with variable block class declarations +// +//========================================================================== +//####COPYRIGHTBEGIN#### +// +// ------------------------------------------- +// The contents of this file are subject to the Red Hat eCos Public License +// Version 1.1 (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.redhat.com/ +// +// Software distributed under the License is distributed on an "AS IS" +// basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the +// License for the specific language governing rights and limitations under +// the License. +// +// The Original Code is eCos - Embedded Configurable Operating System, +// released September 30, 1998. +// +// The Initial Developer of the Original Code is Red Hat. +// Portions created by Red Hat are +// Copyright (C) 1998, 1999, 2000 Red Hat, Inc. +// All Rights Reserved. +// ------------------------------------------- +// +//####COPYRIGHTEND#### +//========================================================================== +//#####DESCRIPTIONBEGIN#### +// +// Author(s): hmt +// Contributors: jlarmour +// Date: 2000-06-12 +// Purpose: Define Mvarimpl class interface +// Description: Inline class for constructing a variable block allocator +// Usage: #include <cyg/memalloc/mvarimpl.hxx> +// +// +//####DESCRIPTIONEND#### +// +//========================================================================== + +#include <pkgconf/memalloc.h> +#include <cyg/memalloc/mvarimpl.hxx> + +#include <cyg/infra/cyg_ass.h> // assertion support +#include <cyg/infra/cyg_trac.h> // tracing support + +// Simple allocator + +// The free list is stored on a doubly linked list, each member of +// which is stored in the body of the free memory. The head of the +// list has the same structure but its size field is zero. This +// resides in the memory pool structure. Always having at least one +// item on the list simplifies the alloc and free code. + +// +inline cyg_int32 +Cyg_Mempool_Variable_Implementation::roundup( cyg_int32 size ) +{ + + size += sizeof(struct memdq); + size = (size + alignment - 1) & -alignment; + return size; +} + +inline struct Cyg_Mempool_Variable_Implementation::memdq * +Cyg_Mempool_Variable_Implementation::addr2memdq( cyg_uint8 *addr ) +{ + struct memdq *dq; + dq = (struct memdq *)(roundup((cyg_int32)addr) - sizeof(struct memdq)); + return dq; +} + +inline struct Cyg_Mempool_Variable_Implementation::memdq * +Cyg_Mempool_Variable_Implementation::alloc2memdq( cyg_uint8 *addr ) +{ + return (struct memdq *)(addr - sizeof(struct memdq)); +} + +inline cyg_uint8 * +Cyg_Mempool_Variable_Implementation::memdq2alloc( struct memdq *dq ) +{ + return ((cyg_uint8 *)dq + sizeof(struct memdq)); +} + +// ------------------------------------------------------------------------- + +inline void +Cyg_Mempool_Variable_Implementation::insert_free_block( struct memdq *dq ) +{ + struct memdq *hdq=&head; + + freemem += dq->size; +#ifdef CYGSEM_MEMALLOC_ALLOCATOR_VARIABLE_COALESCE +// For simple coalescing have the free list be sorted by memory base address + struct memdq *idq; + + for (idq = hdq->next; idq != hdq; idq = idq->next) { + if (idq > dq) + break; + } + // we want to insert immediately before idq + dq->next = idq; + dq->prev = idq->prev; + idq->prev = dq; + dq->prev->next = dq; + + // Now do coalescing, but leave the head of the list alone. + if (dq->next != hdq && (char *)dq + dq->size == (char *)dq->next) { + dq->size += dq->next->size; + dq->next = dq->next->next; + dq->next->prev = dq; + } + if (dq->prev != hdq && (char *)dq->prev + dq->prev->size == (char *)dq) { + dq->prev->size += dq->size; + dq->prev->next = dq->next; + dq->next->prev = dq->prev; + dq = dq->prev; + } +#else + dq->prev = hdq; + dq->next = hdq->next; + hdq->next = dq; + dq->next->prev=dq; +#endif +} + +// ------------------------------------------------------------------------- + +inline +Cyg_Mempool_Variable_Implementation::Cyg_Mempool_Variable_Implementation( + cyg_uint8 *base, + cyg_int32 size, + CYG_ADDRWORD align ) +{ + CYG_REPORT_FUNCTION(); + + CYG_ASSERT( align > 0, "Bad alignment" ); + CYG_ASSERT( size > 0, "Bad size" ); + CYG_ASSERT(0!=align ,"align is zero"); + CYG_ASSERT(0==(align & align-1),"align not a power of 2"); + + obase=base; + osize=size; + + alignment = align; + while (alignment < (cyg_int32)sizeof(struct memdq)) + alignment += alignment; + CYG_ASSERT(0==(alignment & alignment-1),"alignment not a power of 2"); + + // the memdq for each allocation is always positioned immediately before + // an aligned address, so that the allocation (i.e. what eventually gets + // returned from alloc()) is at the correctly aligned address + // Therefore bottom is set to the lowest available address given the size of + // struct memdq and the alignment. + bottom = (cyg_uint8 *)addr2memdq(base); + + // because we split free blocks by allocating memory from the end, not + // the beginning, then to preserve alignment, the *top* must also be + // aligned such that (top-bottom) is a multiple of the alignment + top = (cyg_uint8 *)((cyg_int32)(base+size+sizeof(struct memdq)) & -alignment) - + sizeof(struct memdq); + + CYG_ASSERT( top > bottom , "heap too small" ); + CYG_ASSERT( top <= (base+size), "top too large" ); + CYG_ASSERT( ((cyg_int32)(top+sizeof(struct memdq)) & alignment-1)==0, + "top badly aligned" ); + + struct memdq *hdq = &head, *dq = (struct memdq *)bottom; + + CYG_ASSERT( ((cyg_int32)memdq2alloc(dq) & alignment-1)==0, + "bottom badly aligned" ); + + hdq->prev = hdq->next = dq; + hdq->size = 0; + dq->prev = dq->next = hdq; + + freemem = dq->size = top - bottom; +} + +// ------------------------------------------------------------------------- + +inline +Cyg_Mempool_Variable_Implementation::~Cyg_Mempool_Variable_Implementation() +{ +} + +// ------------------------------------------------------------------------- +// allocation is simple +// First we look down the free list for a large enough block +// If we find a block the right size, we unlink the block from +// the free list and return a pointer to it. +// If we find a larger block, we chop a piece off the end +// and return that +// Otherwise we will eventually get back to the head of the list +// and return NULL +inline cyg_uint8 * +Cyg_Mempool_Variable_Implementation::try_alloc( cyg_int32 size ) +{ + struct memdq *dq = &head; + cyg_uint8 *alloced; + + CYG_REPORT_FUNCTION(); + + size = roundup(size); + + do { + CYG_ASSERT( dq->next->prev==dq, "Bad link in dq"); + dq = dq->next; + if(0 == dq->size) { + CYG_ASSERT(dq == &head, "bad free block"); + return NULL; + } + } while(dq->size < size); + + if( size == dq->size ) { + // exact fit -- unlink from free list + dq->prev->next = dq->next; + dq->next->prev = dq->prev; + alloced = (cyg_uint8 *)dq; + } else { + + CYG_ASSERT( dq->size > size, "block found is too small"); + + // allocate portion of memory from end of block + + dq->size -=size; + + // The portion left over has to be large enough to store a + // struct memdq. This is guaranteed because the alignment is + // larger than the size of this structure. + + CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=dq->size , + "not enough space for list item" ); + + alloced = (cyg_uint8 *)dq + dq->size; + } + + CYG_ASSERT( bottom<=alloced && alloced<=top, "alloced outside pool" ); + + // Set size on allocated block + + dq = (struct memdq *)alloced; + dq->size = size; + dq->next = dq->prev = (struct memdq *)0xd530d53; // magic number + + freemem -=size; + + cyg_uint8 *ptr = memdq2alloc( dq ); + CYG_ASSERT( ((CYG_ADDRESS)ptr & (alignment-1)) == 0, + "returned memory not aligned" ); + return ptr; +} + +// ------------------------------------------------------------------------- +// resize existing allocation, if oldsize is non-NULL, previous +// allocation size is placed into it. If previous size not available, +// it is set to 0. NB previous allocation size may have been rounded up. +// Occasionally the allocation can be adjusted *backwards* as well as, +// or instead of forwards, therefore the address of the resized +// allocation is returned, or NULL if no resizing was possible. +// Note that this differs from ::realloc() in that no attempt is +// made to call malloc() if resizing is not possible - that is left +// to higher layers. The data is copied from old to new though. +// The effects of alloc_ptr==NULL or newsize==0 are undefined + +inline cyg_uint8 * +Cyg_Mempool_Variable_Implementation::resize_alloc( cyg_uint8 *alloc_ptr, + cyg_int32 newsize, + cyg_int32 *oldsize ) +{ + cyg_uint8 *ret = NULL; + + CYG_REPORT_FUNCTION(); + + CYG_CHECK_DATA_PTRC( alloc_ptr ); + if ( NULL != oldsize ) + CYG_CHECK_DATA_PTRC( oldsize ); + + CYG_ASSERT( (bottom <= alloc_ptr) && (alloc_ptr <= top), + "alloc_ptr outside pool" ); + + struct memdq *dq=alloc2memdq( alloc_ptr ); + + // check magic number in block for validity + CYG_ASSERT( (dq->next == dq->prev) && + (dq->next == (struct memdq *)0xd530d53), "bad alloc_ptr" ); + + newsize = roundup(newsize); + + if ( NULL != oldsize ) + *oldsize = dq->size; + + if ( newsize > dq->size ) { + // see if we can increase the allocation size + if ( (cyg_uint8 *)dq + newsize <= top ) { // obviously can't exceed pool + struct memdq *nextdq = (struct memdq *)((cyg_uint8 *)dq + dq->size); + + if ( (nextdq->next != nextdq->prev) && + (nextdq->size >= (newsize - dq->size)) ) { + // it's free and it's big enough + // we therefore temporarily join this block and *all* of + // the next block, so that the code below can then split it + nextdq->next->prev = nextdq->prev; + nextdq->prev->next = nextdq->next; + dq->size += nextdq->size; + freemem -= nextdq->size; + } + } // if + } // if + + // this is also used if the allocation size was increased and we need + // to split it + if ( newsize < dq->size ) { + // We can shrink the allocation by splitting into smaller allocation and + // new free block + struct memdq *newdq = (struct memdq *)((cyg_uint8 *)dq + newsize); + + newdq->size = dq->size - newsize; + dq->size = newsize; + + CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=newdq->size , + "not enough space for list item" ); + + // now return the new space back to the freelist + insert_free_block( newdq ); + + ret = alloc_ptr; + + } // if + else if ( newsize == dq->size ) { + ret = alloc_ptr; + } + + return ret; + +} // resize_alloc() + + +// ------------------------------------------------------------------------- +// When no coalescing is done, free is simply a matter of using the +// freed memory as an element of the free list linking it in at the +// start. When coalescing, the free list is sorted + +inline cyg_bool +Cyg_Mempool_Variable_Implementation::free( cyg_uint8 *p, cyg_int32 size ) +{ + CYG_REPORT_FUNCTION(); + + CYG_CHECK_DATA_PTRC( p ); + + if (!((bottom <= p) && (p <= top))) + return false; + + struct memdq *dq=alloc2memdq( p ); + + // check magic number in block for validity + if ( (dq->next != dq->prev) || + (dq->next != (struct memdq *)0xd530d53) ) + return false; + + if ( 0==size ) { + size = dq->size; + } else { + size = roundup(size); + } + + if( dq->size != size ) + return false; + + CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=size , + "not enough space for list item" ); + + insert_free_block( dq ); + + return true; +} + +// ------------------------------------------------------------------------- + +inline void +Cyg_Mempool_Variable_Implementation::get_status( + cyg_mempool_status_flag_t flags, + Cyg_Mempool_Status &status ) +{ + CYG_REPORT_FUNCTION(); + +// as quick or quicker to just set it, rather than test flag first + status.arenabase = obase; + if ( 0 != (flags & CYG_MEMPOOL_STAT_ARENASIZE) ) + status.arenasize = top - bottom; + if ( 0 != (flags & CYG_MEMPOOL_STAT_TOTALALLOCATED) ) + status.totalallocated = (top-bottom) - freemem; +// as quick or quicker to just set it, rather than test flag first + status.totalfree = freemem; + if ( 0 != (flags & CYG_MEMPOOL_STAT_MAXFREE) ) { + struct memdq *dq = &head; + cyg_int32 mf = 0; + + do { + CYG_ASSERT( dq->next->prev==dq, "Bad link in dq"); + dq = dq->next; + if(0 == dq->size) { + CYG_ASSERT(dq == &head, "bad free block"); + break; + } + if(dq->size > mf) + mf = dq->size; + } while(1); + status.maxfree = mf; + } +// as quick or quicker to just set it, rather than test flag first + status.origbase = obase; +// as quick or quicker to just set it, rather than test flag first + status.origsize = osize; + + CYG_REPORT_RETURN(); + +} // get_status() + + +// ------------------------------------------------------------------------- +#endif // ifndef CYGONCE_MEMALLOC_MVARIMPL_INL +// EOF mvarimpl.inl
