From 962e894f4ed0836a5aad472805682bb2f2c90201 Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Thu, 20 Jan 2005 18:22:29 +0000 Subject: 2005-01-20 Sergei Organov PR 536/rtems Heap manager re-implementation to consume less memory and still satisfy alignment requirements. * score/src/heap.c, score/src/heapallocate.c, score/src/heapextend.c, score/src/heapfree.c, score/src/heapgetinfo.c, score/src/heapgetfreeinfo.c, core/src/heapsizeofuserarea.c, score/src/heapwalk.c, core/macros/rtems/score/heap.inl, score/inline/rtems/score/heap.inl, score/include/rtems/score/heap.h: Reimplemented. * score/src/heapallocatealigned.c: new file * score/Makefile.am: HEAP_C_FILES: add score/src/heapallocatealigned.c --- cpukit/score/src/heapallocate.c | 93 +++++++++++++---------------------------- 1 file changed, 29 insertions(+), 64 deletions(-) (limited to 'cpukit/score/src/heapallocate.c') diff --git a/cpukit/score/src/heapallocate.c b/cpukit/score/src/heapallocate.c index 54bdd58e45..d49eb62b46 100644 --- a/cpukit/score/src/heapallocate.c +++ b/cpukit/score/src/heapallocate.c @@ -36,78 +36,43 @@ void *_Heap_Allocate( uint32_t size ) { - uint32_t excess; - uint32_t the_size; + uint32_t the_size; + uint32_t search_count; Heap_Block *the_block; - Heap_Block *next_block; - Heap_Block *temporary_block; - void *ptr; - uint32_t offset; - - /* - * Catch the case of a user allocating close to the limit of the - * uint32_t . - */ - - if ( size >= (-1 - HEAP_BLOCK_USED_OVERHEAD) ) - return( NULL ); + void *ptr = NULL; + Heap_Statistics *const stats = &the_heap->stats; + Heap_Block *const tail = _Heap_Tail(the_heap); + + the_size = + _Heap_Calc_block_size(size, the_heap->page_size, the_heap->min_block_size); + if(the_size == 0) + return NULL; + + /* Find large enough free block. */ + for(the_block = _Heap_First(the_heap), search_count = 0; + the_block != tail; + the_block = the_block->next, ++search_count) + { + /* As we always coalesce free blocks, prev block must have been used. */ + _HAssert(_Heap_Is_prev_used(the_block)); - excess = size % the_heap->page_size; - the_size = size + the_heap->page_size + HEAP_BLOCK_USED_OVERHEAD; + /* Don't bother to mask out the HEAP_PREV_USED bit as it won't change the + result of the comparison. */ + if(the_block->size >= the_size) { + the_block = _Heap_Block_allocate(the_heap, the_block, the_size ); - if ( excess ) - the_size += the_heap->page_size - excess; + ptr = _Heap_User_area(the_block); - if ( the_size < sizeof( Heap_Block ) ) - the_size = sizeof( Heap_Block ); + stats->allocs += 1; + stats->searches += search_count + 1; - for ( the_block = the_heap->first; - ; - the_block = the_block->next ) { - if ( the_block == _Heap_Tail( the_heap ) ) - return( NULL ); - if ( the_block->front_flag >= the_size ) + _HAssert(_Heap_Is_aligned_ptr(ptr, the_heap->page_size)); break; + } } - if ( (the_block->front_flag - the_size) > - (the_heap->page_size + HEAP_BLOCK_USED_OVERHEAD) ) { - the_block->front_flag -= the_size; - next_block = _Heap_Next_block( the_block ); - next_block->back_flag = the_block->front_flag; - - temporary_block = _Heap_Block_at( next_block, the_size ); - temporary_block->back_flag = - next_block->front_flag = _Heap_Build_flag( the_size, - HEAP_BLOCK_USED ); - ptr = _Heap_Start_of_user_area( next_block ); - } else { - next_block = _Heap_Next_block( the_block ); - next_block->back_flag = _Heap_Build_flag( the_block->front_flag, - HEAP_BLOCK_USED ); - the_block->front_flag = next_block->back_flag; - the_block->next->previous = the_block->previous; - the_block->previous->next = the_block->next; - ptr = _Heap_Start_of_user_area( the_block ); - } - - /* - * round ptr up to a multiple of page size - * Have to save the bump amount in the buffer so that free can figure it out - */ - - offset = the_heap->page_size - (((uint32_t ) ptr) & (the_heap->page_size - 1)); - ptr = _Addresses_Add_offset( ptr, offset ); - *(((uint32_t *) ptr) - 1) = offset; - -#ifdef RTEMS_DEBUG - { - uint32_t ptr_u32; - ptr_u32 = (uint32_t ) ptr; - if (ptr_u32 & (the_heap->page_size - 1)) - abort(); - } -#endif + if(stats->max_search < search_count) + stats->max_search = search_count; return ptr; } -- cgit v1.2.3