packages/services/memalloc/common/v2_0/include/mvarimpl.inl

   1 #ifndef CYGONCE_MEMALLOC_MVARIMPL_INL
   2 #define CYGONCE_MEMALLOC_MVARIMPL_INL
   3
   4 //==========================================================================
   5 //
   6 //      mvarimpl.inl
   7 //
   8 //      Memory pool with variable block class declarations
   9 //
  10 //==========================================================================
  11 //####ECOSGPLCOPYRIGHTBEGIN####
  12 // -------------------------------------------
  13 // This file is part of eCos, the Embedded Configurable Operating System.
  14 // Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
  15 //
  16 // eCos is free software; you can redistribute it and/or modify it under
  17 // the terms of the GNU General Public License as published by the Free
  18 // Software Foundation; either version 2 or (at your option) any later version.
  19 //
  20 // eCos is distributed in the hope that it will be useful, but WITHOUT ANY
  21 // WARRANTY; without even the implied warranty of MERCHANTABILITY or
  22 // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  23 // for more details.
  24 //
  25 // You should have received a copy of the GNU General Public License along
  26 // with eCos; if not, write to the Free Software Foundation, Inc.,
  27 // 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
  28 //
  29 // As a special exception, if other files instantiate templates or use macros
  30 // or inline functions from this file, or you compile this file and link it
  31 // with other works to produce a work based on this file, this file does not
  32 // by itself cause the resulting work to be covered by the GNU General Public
  33 // License. However the source code for this file must still be made available
  34 // in accordance with section (3) of the GNU General Public License.
  35 //
  36 // This exception does not invalidate any other reasons why a work based on
  37 // this file might be covered by the GNU General Public License.
  38 //
  39 // Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
  40 // at http://sources.redhat.com/ecos/ecos-license/
  41 // -------------------------------------------
  42 //####ECOSGPLCOPYRIGHTEND####
  43 //==========================================================================
  44 //#####DESCRIPTIONBEGIN####
  45 //
  46 // Author(s):    hmt
  47 // Contributors: jlarmour
  48 // Date:         2000-06-12
  49 // Purpose:      Define Mvarimpl class interface
  50 // Description:  Inline class for constructing a variable block allocator
  51 // Usage:        #include <cyg/memalloc/mvarimpl.hxx>
  52 //
  53 //
  54 //####DESCRIPTIONEND####
  55 //
  56 //==========================================================================
  57
  58 #include <pkgconf/memalloc.h>
  59 #include <cyg/memalloc/mvarimpl.hxx>
  60
  61 #include <cyg/infra/cyg_ass.h>           // assertion support
  62 #include <cyg/infra/cyg_trac.h>          // tracing support
  63
  64 // Simple allocator
  65
  66 // The free list is stored on a doubly linked list, each member of
  67 // which is stored in the body of the free memory.  The head of the
  68 // list has the same structure but its size field is zero.  This
  69 // resides in the memory pool structure.  Always having at least one
  70 // item on the list simplifies the alloc and free code.
  71
  72 //
  73 inline cyg_int32
  74 Cyg_Mempool_Variable_Implementation::roundup( cyg_int32 size )
  75 {
  76
  77     size += sizeof(struct memdq);
  78     size = (size + alignment - 1) & -alignment;
  79     return size;
  80 }
  81
  82 inline struct Cyg_Mempool_Variable_Implementation::memdq *
  83 Cyg_Mempool_Variable_Implementation::addr2memdq( cyg_uint8 *addr )
  84 {
  85     struct memdq *dq;
  86     dq = (struct memdq *)(roundup((cyg_int32)addr) - sizeof(struct memdq));
  87     return dq;
  88 }
  89
  90 inline struct Cyg_Mempool_Variable_Implementation::memdq *
  91 Cyg_Mempool_Variable_Implementation::alloc2memdq( cyg_uint8 *addr )
  92 {
  93     return (struct memdq *)(addr - sizeof(struct memdq));
  94 }
  95
  96 inline cyg_uint8 *
  97 Cyg_Mempool_Variable_Implementation::memdq2alloc( struct memdq *dq )
  98 {
  99     return ((cyg_uint8 *)dq + sizeof(struct memdq));
 100 }
 101
 102 // -------------------------------------------------------------------------
 103
 104 inline void
 105 Cyg_Mempool_Variable_Implementation::insert_free_block( struct memdq *dq )
 106 {
 107     struct memdq *hdq=&head;
 108
 109     freemem += dq->size;
 110 #ifdef CYGSEM_MEMALLOC_ALLOCATOR_VARIABLE_COALESCE
 111 // For simple coalescing have the free list be sorted by memory base address
 112     struct memdq *idq;
 113
 114     for (idq = hdq->next; idq != hdq; idq = idq->next) {
 115         if (idq > dq)
 116             break;
 117     }
 118     // we want to insert immediately before idq
 119     dq->next = idq;
 120     dq->prev = idq->prev;
 121     idq->prev = dq;
 122     dq->prev->next = dq;
 123
 124     // Now do coalescing, but leave the head of the list alone.
 125     if (dq->next != hdq && (char *)dq + dq->size == (char *)dq->next) {
 126         dq->size += dq->next->size;
 127         dq->next = dq->next->next;
 128         dq->next->prev = dq;
 129     }
 130     if (dq->prev != hdq && (char *)dq->prev + dq->prev->size == (char *)dq) {
 131         dq->prev->size += dq->size;
 132         dq->prev->next = dq->next;
 133         dq->next->prev = dq->prev;
 134         dq = dq->prev;
 135     }
 136 #else
 137     dq->prev = hdq;
 138     dq->next = hdq->next;
 139     hdq->next = dq;
 140     dq->next->prev=dq;
 141 #endif
 142 }
 143
 144 // -------------------------------------------------------------------------
 145
 146 inline
 147 Cyg_Mempool_Variable_Implementation::Cyg_Mempool_Variable_Implementation(
 148         cyg_uint8 *base,
 149         cyg_int32 size,
 150         CYG_ADDRWORD align )
 151 {
 152     CYG_REPORT_FUNCTION();
 153
 154     CYG_ASSERT( align > 0, "Bad alignment" );
 155     CYG_ASSERT(0!=align ,"align is zero");
 156     CYG_ASSERT(0==(align & align-1),"align not a power of 2");
 157
 158     if ((unsigned)size < sizeof(struct memdq)) {
 159         bottom = NULL;
 160         return;
 161     }
 162
 163     obase=base;
 164     osize=size;
 165
 166     alignment = align;
 167     while (alignment < (cyg_int32)sizeof(struct memdq))
 168         alignment += alignment;
 169     CYG_ASSERT(0==(alignment & alignment-1),"alignment not a power of 2");
 170
 171     // the memdq for each allocation is always positioned immediately before
 172     // an aligned address, so that the allocation (i.e. what eventually gets
 173     // returned from alloc()) is at the correctly aligned address
 174     // Therefore bottom is set to the lowest available address given the size of
 175     // struct memdq and the alignment.
 176     bottom = (cyg_uint8 *)addr2memdq(base);
 177
 178     // because we split free blocks by allocating memory from the end, not
 179     // the beginning, then to preserve alignment, the *top* must also be
 180     // aligned such that (top-bottom) is a multiple of the alignment
 181     top = (cyg_uint8 *)((cyg_int32)(base+size+sizeof(struct memdq)) & -alignment) -
 182         sizeof(struct memdq);
 183
 184     CYG_ASSERT( top > bottom , "heap too small" );
 185     CYG_ASSERT( top <= (base+size), "top too large" );
 186     CYG_ASSERT( ((cyg_int32)(top+sizeof(struct memdq)) & alignment-1)==0,
 187                 "top badly aligned" );
 188
 189     struct memdq *hdq = &head, *dq = (struct memdq *)bottom;
 190
 191     CYG_ASSERT( ((cyg_int32)memdq2alloc(dq) & alignment-1)==0,
 192                  "bottom badly aligned" );
 193
 194     hdq->prev = hdq->next = dq;
 195     hdq->size = 0;
 196     dq->prev = dq->next = hdq;
 197
 198     freemem = dq->size = top - bottom;
 199 }
 200
 201 // -------------------------------------------------------------------------
 202
 203 inline
 204 Cyg_Mempool_Variable_Implementation::~Cyg_Mempool_Variable_Implementation()
 205 {
 206 }
 207
 208 // -------------------------------------------------------------------------
 209 // allocation is simple
 210 // First we look down the free list for a large enough block
 211 // If we find a block the right size, we unlink the block from
 212 //    the free list and return a pointer to it.
 213 // If we find a larger block, we chop a piece off the end
 214 //    and return that
 215 // Otherwise we will eventually get back to the head of the list
 216 //    and return NULL
 217 inline cyg_uint8 *
 218 Cyg_Mempool_Variable_Implementation::try_alloc( cyg_int32 size )
 219 {
 220     struct memdq *dq = &head;
 221     cyg_uint8 *alloced;
 222
 223     CYG_REPORT_FUNCTION();
 224
 225     //  Allow uninitialised (zero sized) heaps because they could exist as a
 226     //  quirk of the MLT setup where a dynamically sized heap is at the top of
 227     //  memory.
 228     if (NULL == bottom)
 229         return NULL;
 230
 231     size = roundup(size);
 232
 233     do {
 234         CYG_ASSERT( dq->next->prev==dq, "Bad link in dq");
 235         dq = dq->next;
 236         if(0 == dq->size) {
 237             CYG_ASSERT(dq == &head, "bad free block");
 238             return NULL;
 239         }
 240     } while(dq->size < size);
 241
 242     if( size == dq->size ) {
 243         // exact fit -- unlink from free list
 244         dq->prev->next = dq->next;
 245         dq->next->prev = dq->prev;
 246         alloced = (cyg_uint8 *)dq;
 247     } else {
 248
 249         CYG_ASSERT( dq->size > size, "block found is too small");
 250
 251         // allocate portion of memory from end of block
 252
 253         dq->size -=size;
 254
 255         // The portion left over has to be large enough to store a
 256         // struct memdq.  This is guaranteed because the alignment is
 257         // larger than the size of this structure.
 258
 259         CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=dq->size ,
 260                 "not enough space for list item" );
 261
 262         alloced = (cyg_uint8 *)dq + dq->size;
 263     }
 264
 265     CYG_ASSERT( bottom<=alloced && alloced<=top, "alloced outside pool" );
 266
 267     // Set size on allocated block
 268
 269     dq = (struct memdq *)alloced;
 270     dq->size = size;
 271     dq->next = dq->prev = (struct memdq *)0xd530d53; // magic number
 272
 273     freemem -=size;
 274
 275     cyg_uint8 *ptr = memdq2alloc( dq );
 276     CYG_ASSERT( ((CYG_ADDRESS)ptr & (alignment-1)) == 0,
 277                 "returned memory not aligned" );
 278     CYG_MEMALLOC_FAIL_TEST(ptr==NULL, size);
 279
 280     return ptr;
 281 }
 282
 283 // -------------------------------------------------------------------------
 284 // resize existing allocation, if oldsize is non-NULL, previous
 285 // allocation size is placed into it. If previous size not available,
 286 // it is set to 0. NB previous allocation size may have been rounded up.
 287 // Occasionally the allocation can be adjusted *backwards* as well as,
 288 // or instead of forwards, therefore the address of the resized
 289 // allocation is returned, or NULL if no resizing was possible.
 290 // Note that this differs from ::realloc() in that no attempt is
 291 // made to call malloc() if resizing is not possible - that is left
 292 // to higher layers. The data is copied from old to new though.
 293 // The effects of alloc_ptr==NULL or newsize==0 are undefined
 294
 295 inline cyg_uint8 *
 296 Cyg_Mempool_Variable_Implementation::resize_alloc( cyg_uint8 *alloc_ptr,
 297                                                    cyg_int32 newsize,
 298                                                    cyg_int32 *oldsize )
 299 {
 300     cyg_uint8 *ret = NULL;
 301
 302     CYG_REPORT_FUNCTION();
 303
 304     CYG_CHECK_DATA_PTRC( alloc_ptr );
 305     if ( NULL != oldsize )
 306         CYG_CHECK_DATA_PTRC( oldsize );
 307
 308     CYG_ASSERT( (bottom <= alloc_ptr) && (alloc_ptr <= top),
 309                 "alloc_ptr outside pool" );
 310
 311     struct memdq *dq=alloc2memdq( alloc_ptr );
 312
 313     // check magic number in block for validity
 314     CYG_ASSERT( (dq->next == dq->prev) &&
 315                 (dq->next == (struct memdq *)0xd530d53), "bad alloc_ptr" );
 316
 317     newsize = roundup(newsize);
 318
 319     if ( NULL != oldsize )
 320         *oldsize = dq->size;
 321
 322     if ( newsize > dq->size ) {
 323         // see if we can increase the allocation size
 324         if ( (cyg_uint8 *)dq + newsize <= top ) { // obviously can't exceed pool
 325             struct memdq *nextdq = (struct memdq *)((cyg_uint8 *)dq + dq->size);
 326
 327             if ( (nextdq->next != nextdq->prev) &&
 328                  (nextdq->size >= (newsize - dq->size)) ) {
 329                 // it's free and it's big enough
 330                 // we therefore temporarily join this block and *all* of
 331                 // the next block, so that the code below can then split it
 332                 nextdq->next->prev = nextdq->prev;
 333                 nextdq->prev->next = nextdq->next;
 334                 dq->size += nextdq->size;
 335                 freemem -= nextdq->size;
 336             }
 337         } // if
 338     } // if
 339
 340     // this is also used if the allocation size was increased and we need
 341     // to split it
 342     if ( newsize < dq->size ) {
 343         // We can shrink the allocation by splitting into smaller allocation and
 344         // new free block
 345         struct memdq *newdq = (struct memdq *)((cyg_uint8 *)dq + newsize);
 346
 347         newdq->size = dq->size - newsize;
 348         dq->size = newsize;
 349
 350         CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=newdq->size ,
 351                     "not enough space for list item" );
 352
 353         // now return the new space back to the freelist
 354         insert_free_block( newdq );
 355
 356         ret = alloc_ptr;
 357
 358     } // if
 359     else if ( newsize == dq->size ) {
 360         ret = alloc_ptr;
 361     }
 362
 363     CYG_MEMALLOC_FAIL_TEST(ret==NULL, newsize);
 364
 365     return ret;
 366
 367 } // resize_alloc()
 368
 369
 370 // -------------------------------------------------------------------------
 371 // When no coalescing is done, free is simply a matter of using the
 372 // freed memory as an element of the free list linking it in at the
 373 // start. When coalescing, the free list is sorted
 374
 375 inline cyg_bool
 376 Cyg_Mempool_Variable_Implementation::free( cyg_uint8 *p, cyg_int32 size )
 377 {
 378     CYG_REPORT_FUNCTION();
 379
 380     CYG_CHECK_DATA_PTRC( p );
 381
 382     if (!((bottom <= p) && (p <= top)))
 383         return false;
 384
 385     struct memdq *dq=alloc2memdq( p );
 386
 387     // check magic number in block for validity
 388     if ( (dq->next != dq->prev) ||
 389          (dq->next != (struct memdq *)0xd530d53) )
 390         return false;
 391
 392     if ( 0==size ) {
 393         size = dq->size;
 394     } else {
 395         size = roundup(size);
 396     }
 397
 398     if( dq->size != size )
 399         return false;
 400
 401     CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=size ,
 402                 "not enough space for list item" );
 403
 404     insert_free_block( dq );
 405
 406     return true;
 407 }
 408
 409 // -------------------------------------------------------------------------
 410
 411 inline void
 412 Cyg_Mempool_Variable_Implementation::get_status(
 413     cyg_mempool_status_flag_t flags,
 414     Cyg_Mempool_Status &status )
 415 {
 416     CYG_REPORT_FUNCTION();
 417
 418 // as quick or quicker to just set it, rather than test flag first
 419     status.arenabase = obase;
 420     if ( 0 != (flags & CYG_MEMPOOL_STAT_ARENASIZE) )
 421         status.arenasize = top - bottom;
 422     if ( 0 != (flags & CYG_MEMPOOL_STAT_TOTALALLOCATED) )
 423         status.totalallocated = (top-bottom) - freemem;
 424 // as quick or quicker to just set it, rather than test flag first
 425     status.totalfree = freemem;
 426     if ( 0 != (flags & CYG_MEMPOOL_STAT_MAXFREE) ) {
 427         struct memdq *dq = &head;
 428         cyg_int32 mf = 0;
 429
 430         do {
 431             CYG_ASSERT( dq->next->prev==dq, "Bad link in dq");
 432             dq = dq->next;
 433             if(0 == dq->size) {
 434                 CYG_ASSERT(dq == &head, "bad free block");
 435                 break;
 436             }
 437             if(dq->size > mf)
 438                 mf = dq->size;
 439         } while(1);
 440         status.maxfree = mf - sizeof(struct memdq);
 441     }
 442 // as quick or quicker to just set it, rather than test flag first
 443     status.origbase = obase;
 444 // as quick or quicker to just set it, rather than test flag first
 445     status.origsize = osize;
 446
 447     CYG_REPORT_RETURN();
 448
 449 } // get_status()
 450
 451
 452 // -------------------------------------------------------------------------
 453 #endif // ifndef CYGONCE_MEMALLOC_MVARIMPL_INL
 454 // EOF mvarimpl.inl