1 #ifndef CYGONCE_MEMALLOC_MVARIMPL_INL
2 #define CYGONCE_MEMALLOC_MVARIMPL_INL
4 //==========================================================================
8 // Memory pool with variable block class declarations
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.
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.
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
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.
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.
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.
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####
47 // Contributors: jlarmour
49 // Purpose: Define Mvarimpl class interface
50 // Description: Inline class for constructing a variable block allocator
51 // Usage: #include <cyg/memalloc/mvarimpl.hxx>
54 //####DESCRIPTIONEND####
56 //==========================================================================
58 #include <pkgconf/memalloc.h>
59 #include <cyg/memalloc/mvarimpl.hxx>
61 #include <cyg/infra/cyg_ass.h> // assertion support
62 #include <cyg/infra/cyg_trac.h> // tracing support
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.
74 Cyg_Mempool_Variable_Implementation::roundup( cyg_int32 size )
77 size += sizeof(struct memdq);
78 size = (size + alignment - 1) & -alignment;
82 inline struct Cyg_Mempool_Variable_Implementation::memdq *
83 Cyg_Mempool_Variable_Implementation::addr2memdq( cyg_uint8 *addr )
86 dq = (struct memdq *)(roundup((cyg_int32)addr) - sizeof(struct memdq));
90 inline struct Cyg_Mempool_Variable_Implementation::memdq *
91 Cyg_Mempool_Variable_Implementation::alloc2memdq( cyg_uint8 *addr )
93 return (struct memdq *)(addr - sizeof(struct memdq));
97 Cyg_Mempool_Variable_Implementation::memdq2alloc( struct memdq *dq )
99 return ((cyg_uint8 *)dq + sizeof(struct memdq));
102 // -------------------------------------------------------------------------
105 Cyg_Mempool_Variable_Implementation::insert_free_block( struct memdq *dq )
107 struct memdq *hdq=&head;
110 #ifdef CYGSEM_MEMALLOC_ALLOCATOR_VARIABLE_COALESCE
111 // For simple coalescing have the free list be sorted by memory base address
114 for (idq = hdq->next; idq != hdq; idq = idq->next) {
118 // we want to insert immediately before idq
120 dq->prev = idq->prev;
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;
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;
138 dq->next = hdq->next;
144 // -------------------------------------------------------------------------
147 Cyg_Mempool_Variable_Implementation::Cyg_Mempool_Variable_Implementation(
152 CYG_REPORT_FUNCTION();
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");
158 if ((unsigned)size < sizeof(struct memdq)) {
167 while (alignment < (cyg_int32)sizeof(struct memdq))
168 alignment += alignment;
169 CYG_ASSERT(0==(alignment & alignment-1),"alignment not a power of 2");
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);
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);
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" );
189 struct memdq *hdq = &head, *dq = (struct memdq *)bottom;
191 CYG_ASSERT( ((cyg_int32)memdq2alloc(dq) & alignment-1)==0,
192 "bottom badly aligned" );
194 hdq->prev = hdq->next = dq;
196 dq->prev = dq->next = hdq;
198 freemem = dq->size = top - bottom;
201 // -------------------------------------------------------------------------
204 Cyg_Mempool_Variable_Implementation::~Cyg_Mempool_Variable_Implementation()
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
215 // Otherwise we will eventually get back to the head of the list
218 Cyg_Mempool_Variable_Implementation::try_alloc( cyg_int32 size )
220 struct memdq *dq = &head;
223 CYG_REPORT_FUNCTION();
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
231 size = roundup(size);
234 CYG_ASSERT( dq->next->prev==dq, "Bad link in dq");
237 CYG_ASSERT(dq == &head, "bad free block");
240 } while(dq->size < size);
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;
249 CYG_ASSERT( dq->size > size, "block found is too small");
251 // allocate portion of memory from end of block
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.
259 CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=dq->size ,
260 "not enough space for list item" );
262 alloced = (cyg_uint8 *)dq + dq->size;
265 CYG_ASSERT( bottom<=alloced && alloced<=top, "alloced outside pool" );
267 // Set size on allocated block
269 dq = (struct memdq *)alloced;
271 dq->next = dq->prev = (struct memdq *)0xd530d53; // magic number
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);
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
296 Cyg_Mempool_Variable_Implementation::resize_alloc( cyg_uint8 *alloc_ptr,
300 cyg_uint8 *ret = NULL;
302 CYG_REPORT_FUNCTION();
304 CYG_CHECK_DATA_PTRC( alloc_ptr );
305 if ( NULL != oldsize )
306 CYG_CHECK_DATA_PTRC( oldsize );
308 CYG_ASSERT( (bottom <= alloc_ptr) && (alloc_ptr <= top),
309 "alloc_ptr outside pool" );
311 struct memdq *dq=alloc2memdq( alloc_ptr );
313 // check magic number in block for validity
314 CYG_ASSERT( (dq->next == dq->prev) &&
315 (dq->next == (struct memdq *)0xd530d53), "bad alloc_ptr" );
317 newsize = roundup(newsize);
319 if ( NULL != oldsize )
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);
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;
340 // this is also used if the allocation size was increased and we need
342 if ( newsize < dq->size ) {
343 // We can shrink the allocation by splitting into smaller allocation and
345 struct memdq *newdq = (struct memdq *)((cyg_uint8 *)dq + newsize);
347 newdq->size = dq->size - newsize;
350 CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=newdq->size ,
351 "not enough space for list item" );
353 // now return the new space back to the freelist
354 insert_free_block( newdq );
359 else if ( newsize == dq->size ) {
363 CYG_MEMALLOC_FAIL_TEST(ret==NULL, newsize);
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
376 Cyg_Mempool_Variable_Implementation::free( cyg_uint8 *p, cyg_int32 size )
378 CYG_REPORT_FUNCTION();
380 CYG_CHECK_DATA_PTRC( p );
382 if (!((bottom <= p) && (p <= top)))
385 struct memdq *dq=alloc2memdq( p );
387 // check magic number in block for validity
388 if ( (dq->next != dq->prev) ||
389 (dq->next != (struct memdq *)0xd530d53) )
395 size = roundup(size);
398 if( dq->size != size )
401 CYG_ASSERT( (cyg_int32)sizeof(struct memdq)<=size ,
402 "not enough space for list item" );
404 insert_free_block( dq );
409 // -------------------------------------------------------------------------
412 Cyg_Mempool_Variable_Implementation::get_status(
413 cyg_mempool_status_flag_t flags,
414 Cyg_Mempool_Status &status )
416 CYG_REPORT_FUNCTION();
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;
431 CYG_ASSERT( dq->next->prev==dq, "Bad link in dq");
434 CYG_ASSERT(dq == &head, "bad free block");
440 status.maxfree = mf - sizeof(struct memdq);
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;
452 // -------------------------------------------------------------------------
453 #endif // ifndef CYGONCE_MEMALLOC_MVARIMPL_INL