Subversion Repositories openrisc

#ifndef CYGONCE_MEMALLOC_SEPMETAIMPL_INL

#define CYGONCE_MEMALLOC_SEPMETAIMPL_INL

//==========================================================================

//

//      sepmetaimpl.inl

//

//      Variable block memory pool with separate metadata class declarations

//

//==========================================================================

// ####ECOSGPLCOPYRIGHTBEGIN####

// -------------------------------------------

// This file is part of eCos, the Embedded Configurable Operating System.

// Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.

//

// eCos is free software; you can redistribute it and/or modify it under

// the terms of the GNU General Public License as published by the Free

// Software Foundation; either version 2 or (at your option) any later

// version.

//

// eCos 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 General Public License

// for more details.

//

// You should have received a copy of the GNU General Public License

// along with eCos; if not, write to the Free Software Foundation, Inc.,

// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.

//

// As a special exception, if other files instantiate templates or use

// macros or inline functions from this file, or you compile this file

// and link it with other works to produce a work based on this file,

// this file does not by itself cause the resulting work to be covered by

// the GNU General Public License. However the source code for this file

// must still be made available in accordance with section (3) of the GNU

// General Public License v2.

//

// This exception does not invalidate any other reasons why a work based

// on this file might be covered by the GNU General Public License.

// -------------------------------------------

// ####ECOSGPLCOPYRIGHTEND####

//==========================================================================

//#####DESCRIPTIONBEGIN####

//

// Author(s):    jlarmour

// Contributors: hmt

// Date:         2001-06-28

// Purpose:      Define Sepmetaimpl class interface

// Description:  Inline class for constructing a variable block allocator

//               with separate metadata.

// Usage:        #include 

//

//

//####DESCRIPTIONEND####

//

//==========================================================================

#include 

#ifdef CYGPKG_ISOINFRA

# include 

#endif

#include 

#include 

#include            // assertion support

#include           // tracing support

// Simple allocator

// The memory block lists are doubly linked lists. One for all alloced

// blocks, one for all free blocks. There's also a list of unused

// metadata from the metadata pool.  The head of the

// list has the same structure but its memnext/memprev fields are zero.

// Always having at least one item on the list simplifies the alloc and

// free code.

#ifdef CYGINT_ISO_STRING_MEMFUNCS

# include 

#endif

inline void

Cyg_Mempool_Sepmeta_Implementation::copy_data( cyg_uint8 *dst,

                                               cyg_uint8 *src,

                                               cyg_int32 nbytes )

{

#ifdef CYGINT_ISO_STRING_MEMFUNCS

    memmove( dst, src, nbytes );

#else

    if ((src < dst) && (dst < (src + nbytes))) {

        // Have to copy backwards

        src += nbytes;

        dst += nbytes;

        while (nbytes--) {

            *--dst = *--src;

        }

    } else {

        while (nbytes--) {

            *dst++ = *src++;

        }

    }

#endif

}

inline cyg_uint8 *

Cyg_Mempool_Sepmeta_Implementation::alignup( cyg_uint8 *addr )

{

    return (cyg_uint8 *)((cyg_int32)(addr + alignment-1) & -alignment);

}

inline cyg_uint8 *

Cyg_Mempool_Sepmeta_Implementation::aligndown( cyg_uint8 *addr )

{

    return (cyg_uint8 *)((cyg_int32)addr & -alignment);

}

inline cyg_uint8 *

Cyg_Mempool_Sepmeta_Implementation::alignmetaup( cyg_uint8 *addr )

{

    const size_t memdqalign = __alignof__ (struct memdq);

    return (cyg_uint8 *)((cyg_int32)(addr + memdqalign-1) & -memdqalign);

}

inline cyg_uint8 *

Cyg_Mempool_Sepmeta_Implementation::alignmetadown( cyg_uint8 *addr )

{

    const size_t memdqalign = __alignof__ (struct memdq);

    return (cyg_uint8 *)((cyg_int32)addr & -memdqalign);

}

// return the alloced dq at mem

inline struct Cyg_Mempool_Sepmeta_Implementation::memdq *

Cyg_Mempool_Sepmeta_Implementation::find_alloced_dq( cyg_uint8 *mem )

{

    struct memdq *dq=allocedhead.next;

    while (dq->mem != mem ) {

        CYG_ASSERT( dq->next->prev==dq, "Bad link in dq");

        CYG_ASSERT( dq->memnext->memprev==dq, "Bad link in mem dq");

        if (dq->next == &memend) // address not found!

            return NULL;

        dq = dq->next;

    }

    return dq;

}

// returns a free dq of at least size, or NULL if none

inline struct Cyg_Mempool_Sepmeta_Implementation::memdq *

Cyg_Mempool_Sepmeta_Implementation::find_free_dq( cyg_int32 size )

{

    struct memdq *dq = freehead.next;

    while ( (dq->memnext->mem - dq->mem) < size ) {

        CYG_ASSERT( dq->next->prev==dq, "Bad link in dq");

        CYG_ASSERT( dq->memnext->memprev==dq, "Bad link in mem dq");

        if (dq->next == &freehead) { // reached end of list

            return NULL;

        }

        dq = dq->next; // next on free list

    }

    return dq;

}

// returns the free dq following mem

inline struct Cyg_Mempool_Sepmeta_Implementation::memdq *

Cyg_Mempool_Sepmeta_Implementation::find_free_dq_slot( cyg_uint8 *mem )

{

    struct memdq *dq;

    for (dq = freehead.next; dq->mem < mem; dq = dq->next) {

        if ( dq == &freehead ) // wrapped round

            break;

    }

    return dq;

}

inline void

Cyg_Mempool_Sepmeta_Implementation::check_free_memdq( struct memdq *dq )

{

    if (dq == &freehead)

        return;

    CYG_ASSERT(dq->memnext->memprev == dq, "corrupted free dq #1");

    CYG_ASSERT(dq->next->prev == dq, "corrupted free dq #2");

    CYG_ASSERT(dq->memprev->memnext == dq, "corrupted free dq #3");

    CYG_ASSERT(dq->prev->next == dq, "corrupted free dq #4");

    CYG_ASSERT(dq->memnext->mem > dq->mem, "free dq mem not sorted #1");

    if (dq->memprev != &memend)

        CYG_ASSERT(dq->memprev->mem < dq->mem, "free dq mem not sorted #2");

}

inline void

Cyg_Mempool_Sepmeta_Implementation::check_alloced_memdq( struct memdq *dq )

{

    CYG_ASSERT(dq->memnext->memprev == dq, "corrupted alloced dq #1");

    CYG_ASSERT(dq->next->prev == dq, "corrupted alloced dq #2");

    CYG_ASSERT(dq->memprev->memnext == dq, "corrupted alloced dq #3");

    CYG_ASSERT(dq->prev->next == dq, "corrupted alloced dq #4");

    if (dq != &memend)

        CYG_ASSERT(dq->memnext->mem > dq->mem, "alloced dq mem not sorted #1");

    if (dq->memprev != &memhead)

        CYG_ASSERT(dq->memprev->mem < dq->mem, "alloced dq mem not sorted #2");

}

// -------------------------------------------------------------------------

inline void

Cyg_Mempool_Sepmeta_Implementation::insert_free_block( struct memdq *dq )

{

    // scan for correct slot in the sorted free list

    struct memdq *fdq = find_free_dq_slot( dq->mem );

    CYG_ASSERT(fdq != &freehead ? fdq->mem > dq->mem : 1,

               "Block address is already in freelist");

    check_free_memdq(fdq);

    if (dq->memnext == fdq) {

        // we can coalesce these two together

        // adjust fdq's mem address backwards to include dq

        fdq->mem = dq->mem;

        // and remove dq

        fdq->memprev = dq->memprev;

        fdq->memprev->memnext = fdq;

        // Don't need to adjust fdq's next/prev links as it stays in the

        // same place in the free list

        // dq is now redundant so return to metadata free list

        dq->next = freemetahead;

        freemetahead = dq;

        // reset dq

        dq = fdq;

    } else {

        // insert behind fdq

        dq->next = fdq;

        dq->prev = fdq->prev;

        fdq->prev = dq;

        dq->prev->next = dq;

    }

    check_free_memdq(dq);

    // maybe also coalesce backwards

    if (dq->memprev == dq->prev) {

        // adjust dq's mem address backwards to include dq->prev

        dq->mem = dq->prev->mem;

        // return dq->prev to metadata free list

        dq->prev->next = freemetahead;

        freemetahead = dq->prev;

        // and remove dq->prev from mem list

        dq->memprev = dq->prev->memprev;

        dq->memprev->memnext = dq;

        // and free list

        dq->prev = dq->prev->prev;

        dq->prev->next = dq;

        check_free_memdq(dq);

    }

}

// -------------------------------------------------------------------------

#include 

inline

Cyg_Mempool_Sepmeta_Implementation::Cyg_Mempool_Sepmeta_Implementation(

        cyg_uint8 *base,

        cyg_int32 size,

        CYG_ADDRWORD consargs)

{

    CYG_REPORT_FUNCTION();

    struct constructorargs *args = (struct constructorargs *)consargs;

    CYG_CHECK_DATA_PTRC( args );

    alignment = args->alignment;

    CYG_ASSERT( alignment > 0, "Bad alignment" );

    CYG_ASSERT( 0!=alignment, "alignment is zero" );

    CYG_ASSERT( 0==(alignment & (alignment-1)), "alignment not a power of 2" );

    obase=base;

    osize=size;

    metabase = args->metabase;

    metasize = args->metasize;

    // bottom is set to the lowest available address given the alignment.

    bottom = alignup( base );

    cyg_uint8 *metabottom = alignmetaup( metabase );

    // because we split free blocks by allocating memory from the end, not

    // the beginning, then to preserve alignment, the *top* must also be

    // aligned

    top = aligndown( base+size );

    cyg_uint8 *metatop = metabottom +

        sizeof(struct memdq)*(metasize/sizeof(struct memdq));

    CYG_ASSERT( top > bottom , "heap too small" );

    CYG_ASSERT( top <= (base+size), "top too large" );

    CYG_ASSERT( (((cyg_int32)(top)) & (alignment-1))==0,

                "top badly aligned" );

    CYG_ASSERT( (((cyg_int32)(bottom)) & (alignment-1))==0,

                "bottom badly aligned" );

    CYG_ASSERT( metatop > metabottom , "meta space too small" );

    CYG_ASSERT( metatop <= (metabase+metasize), "metatop too large" );

    // Initialize list of unused metadata blocks. Only need to do next

    // pointers - can ignore prev and size

    struct memdq *fq = freemetahead = (struct memdq *)metabottom;

    while ((cyg_uint8 *)fq < metatop) {

        fq->next = fq+1;

        fq++;

    }

    CYG_ASSERT((cyg_uint8 *)fq == metatop, "traversed metadata not aligned");

    // set final pointer to NULL;

    --fq; fq->next = NULL;

    // initialize the free list. memhead is the initial free block occupying

    // all of free memory.

    memhead.next = memhead.prev = &freehead;

    // The mem list is circular for consistency.

    memhead.memprev = memhead.memnext = &memend;

    memhead.mem = bottom;

    // initialize block that indicates end of memory. This pretends to

    // be an allocated block

    memend.next = memend.prev = &allocedhead;

    memend.memnext = memend.memprev = &memhead;

    memend.mem = top;

    // initialize alloced list memdq. memend pretends to be allocated memory

    // at the end

    allocedhead.next = allocedhead.prev = &memend;

    freehead.next = freehead.prev = &memhead;

    // Since allocedhead and freehead are placeholders, not real blocks,

    // assign addresses which can't match list searches

    allocedhead.memnext = allocedhead.memprev = NULL;

    freehead.memnext = freehead.memprev = NULL;

    freehead.mem = allocedhead.mem = NULL;

    freemem = top - bottom;

}

// -------------------------------------------------------------------------

inline

Cyg_Mempool_Sepmeta_Implementation::~Cyg_Mempool_Sepmeta_Implementation()

{

}

// -------------------------------------------------------------------------

// allocation is mostly 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 reach the end of the list and return NULL

inline cyg_uint8 *

Cyg_Mempool_Sepmeta_Implementation::try_alloc( cyg_int32 size )

{

    struct memdq *alloced;

    CYG_REPORT_FUNCTION();

    //  Allow uninitialised (zero sized) heaps because they could exist as a

    //  quirk of the MLT setup where a dynamically sized heap is at the top of

    //  memory.

    if (NULL == bottom || NULL==metabase)

        return NULL;

    size = (size + alignment - 1) & -alignment;

    struct memdq *dq = find_free_dq( size );

    if (NULL == dq) {

        CYG_MEMALLOC_FAIL(size);

        return NULL;

    }

    cyg_int32 dqsize = dq->memnext->mem - dq->mem;

    if( size == dqsize ) {

        // exact fit -- unlink from free list

        dq->prev->next = dq->next;

        dq->next->prev = dq->prev;

        // set up this block for insertion into alloced list

        dq->next = dq->memnext; // since dq was free, dq->memnext must

                                // be allocated otherwise it would have

                                // been coalesced

        dq->prev = dq->next->prev;

        alloced = dq;

    } else {

        CYG_ASSERT( dqsize > size, "block found is too small");

        // Split into two memdq's, returning the second one

        // first get a memdq

        if ( NULL == freemetahead ) {

            // out of metadata.

            CYG_MEMALLOC_FAIL(size);

            return NULL;

        }

        // FIXME: since we don't search all the way for an exact fit

        // first we may be able to find an exact fit later and therefore

        // not need more metadata. We don't do this yet though.

        alloced = freemetahead;

        freemetahead = alloced->next;

        // now set its values

        alloced->memnext = dq->memnext;

        alloced->next = dq->memnext; // since dq was free, dq->memnext must

                                     // be allocated otherwise it would have

                                     // been coalesced

        alloced->memprev = dq;

        alloced->prev = alloced->next->prev;

        alloced->mem = alloced->next->mem - size;

        // now set up dq (the portion that remains a free block)

        // dq->next and dq->prev are unchanged as we still end up pointing

        // at the same adjacent free blocks

        // dq->memprev obviously doesn't change

        dq->memnext = alloced;

        // finish inserting into memory block list

        alloced->memnext->memprev = alloced;

    alloced->next->prev = alloced->prev->next = alloced;

        check_free_memdq(dq);

    }

    CYG_ASSERT( bottom <= alloced->mem && alloced->mem <= top,

                "alloced outside pool" );

    // Insert block into alloced list.

    alloced->next->prev = alloced->prev->next = alloced;

    check_alloced_memdq(alloced);

    freemem -=size;

    CYG_ASSERT( ((CYG_ADDRESS)alloced->mem & (alignment-1)) == 0,

                "returned memory not aligned" );

    return alloced->mem;

}

// -------------------------------------------------------------------------

// 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_Sepmeta_Implementation::resize_alloc( cyg_uint8 *alloc_ptr,

                                                   cyg_int32 newsize,

                                                   cyg_int32 *oldsize )

{

    cyg_int32 currsize, origsize;

    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=find_alloced_dq( alloc_ptr );

    CYG_ASSERT( dq != NULL, "passed address not previously alloced");

    currsize = origsize = dq->memnext->mem - dq->mem;

    if ( NULL != oldsize )

        *oldsize = currsize;

    if ( newsize > currsize ) {

        cyg_int32 nextmemsize=0, prevmemsize=0;

        // see if we can increase the allocation size. Don't change anything

        // so we don't have to undo it later if it wouldn't fit

        if ( dq->next != dq->memnext ) { // if not equal, memnext must

                                         // be on free list

            nextmemsize = dq->memnext->memnext->mem - dq->memnext->mem;

        }

        if ( dq->prev != dq->memprev) { // ditto

            prevmemsize = dq->mem - dq->memprev->mem;

        }

        if (nextmemsize + prevmemsize + currsize < newsize)

        {

            CYG_MEMALLOC_FAIL_TEST(true, newsize);

            return NULL; // can't fit it

        }

        // expand forwards

        if ( nextmemsize != 0 ) {

            if (nextmemsize <= (newsize - currsize)) { // taking all of it

                struct memdq *fblk = dq->memnext;

                // fix up mem list ptrs

                dq->memnext = fblk->memnext;

                dq->memnext->memprev=dq;

                // fix up free list ptrs

                fblk->next->prev = fblk->prev;

                fblk->prev->next = fblk->next;

                // return to meta list

                fblk->next = freemetahead;

                freemetahead = fblk->next;

                currsize += nextmemsize;

            } else { // only needs some

                dq->memnext->mem += (newsize - currsize);

                currsize = newsize;

            }

        }

        // expand backwards

        if ( currsize < newsize && prevmemsize != 0 ) {

            cyg_uint8 *oldmem = dq->mem;

            CYG_ASSERT( prevmemsize >= newsize - currsize,

                        "miscalculated expansion" );

            if (prevmemsize == (newsize - currsize)) { // taking all of it

                struct memdq *fblk = dq->memprev;

                // fix up mem list ptrs

                dq->memprev = fblk->memprev;

                dq->memprev->memnext=dq;

                dq->mem = fblk->mem;

                // fix up free list ptrs

                fblk->next->prev = fblk->prev;

                fblk->prev->next = fblk->next;

                // return to meta list

                fblk->next = freemetahead;

                freemetahead = fblk->next;

            } else { // only needs some

                dq->mem -= (newsize - currsize);

            }

            // move data into place

            copy_data( dq->mem, oldmem, origsize );

        }

    }

    if (newsize < currsize) {

        // shrink allocation

        // easy if the next block is already a free block

        if ( dq->memnext != dq->next ) {

            dq->memnext->mem -= currsize - newsize;

            CYG_ASSERT( dq->memnext->mem > dq->mem,

                        "moving next block back corruption" );

        } else {

            // if its already allocated we need to create a new free list

            // entry

            if (NULL == freemetahead) {

                CYG_MEMALLOC_FAIL(newsize);

                return NULL;  // can't do it

            }

            struct memdq *fdq = freemetahead;

            freemetahead = fdq->next;

            fdq->memprev = dq;

            fdq->memnext = dq->memnext;

            fdq->mem = dq->mem + newsize;

            insert_free_block( fdq );

        }

    }

    freemem += origsize - newsize;

    return dq->mem;

} // 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_Sepmeta_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 = find_alloced_dq( p );

    if (NULL == dq)

        return false;

    if (0 == size)

        size = dq->memnext->mem - dq->mem;

    else {

        size = (size + alignment - 1) & -alignment;

        if( (dq->memnext->mem - dq->mem) != size )

            return false;

    }

    check_alloced_memdq( dq );

    // Remove dq from alloced list

    dq->prev->next = dq->next;

    dq->next->prev = dq->prev;

    insert_free_block( dq );

    freemem += size;

    return true;

}

// -------------------------------------------------------------------------

inline void

Cyg_Mempool_Sepmeta_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 = &freehead;

        cyg_int32 mf = 0;

        do {

            CYG_ASSERT( dq->next->prev==dq, "Bad link in dq");

            dq = dq->next;

            if (dq == &freehead) // wrapped round

                break;

            if(dq->memnext->mem - dq->mem > mf)

                mf = dq->memnext->mem - dq->mem;

        } 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_SEPMETAIMPL_INL

// EOF sepmetaimpl.inl