sepmetaimpl.inl

eCos操作系统源码

#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 Red Hat, 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.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 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.
//
// This exception does not invalidate any other reasons why a work based on
// this file might be covered by the GNU General Public License.
//
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
// at http://sources.redhat.com/ecos/ecos-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 <cyg/memalloc/sepmetaimpl.hxx>
//
//
//####DESCRIPTIONEND####
//
//==========================================================================

#include <pkgconf/system.h>
#ifdef CYGPKG_ISOINFRA
# include <pkgconf/isoinfra.h>
#endif
#include <pkgconf/memalloc.h>
#include <cyg/memalloc/sepmetaimpl.hxx>

#include <cyg/infra/cyg_ass.h>           // assertion support
#include <cyg/infra/cyg_trac.h>          // 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 <string.h>
#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 <cyg/infra/diag.h>
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;