source: SVN/cambria/redboot/packages/services/memalloc/common/current/include/mvarimpl.inl @ 1

Last change on this file since 1 was 1, checked in by Tim Harvey, 2 years ago

restored latest version of files from server backup

Signed-off-by: Tim Harvey <tharvey@…>

File size: 14.7 KB
Line 
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//
73inline cyg_int32
74Cyg_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
82inline struct Cyg_Mempool_Variable_Implementation::memdq *
83Cyg_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
90inline struct Cyg_Mempool_Variable_Implementation::memdq *
91Cyg_Mempool_Variable_Implementation::alloc2memdq( cyg_uint8 *addr )
92{
93    return (struct memdq *)(addr - sizeof(struct memdq));
94}
95
96inline cyg_uint8 *
97Cyg_Mempool_Variable_Implementation::memdq2alloc( struct memdq *dq )
98{
99    return ((cyg_uint8 *)dq + sizeof(struct memdq));
100}
101
102// -------------------------------------------------------------------------
103
104inline void
105Cyg_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
146inline
147Cyg_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
203inline
204Cyg_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
217inline cyg_uint8 *
218Cyg_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
295inline cyg_uint8 *
296Cyg_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   
375inline cyg_bool
376Cyg_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
411inline void
412Cyg_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
Note: See TracBrowser for help on using the repository browser.