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/heap.c | 245 ++++++++++++++++++++++++++++------ cpukit/score/src/heapallocate.c | 93 ++++--------- cpukit/score/src/heapextend.c | 50 +++---- cpukit/score/src/heapfree.c | 111 +++++++++------ cpukit/score/src/heapgetfreeinfo.c | 23 ++-- cpukit/score/src/heapgetinfo.c | 84 ++++-------- cpukit/score/src/heapsizeofuserarea.c | 36 +++-- cpukit/score/src/heapwalk.c | 168 +++++++++++++---------- 8 files changed, 485 insertions(+), 325 deletions(-) (limited to 'cpukit/score/src') diff --git a/cpukit/score/src/heap.c b/cpukit/score/src/heap.c index 6d6873ebed..910ac94c33 100644 --- a/cpukit/score/src/heap.c +++ b/cpukit/score/src/heap.c @@ -16,6 +16,8 @@ #include #include +static uint32_t instance = 0; + /*PAGE * * _Heap_Initialize @@ -32,27 +34,77 @@ * returns - maximum memory available if RTEMS_SUCCESSFUL * 0 - otherwise * - * This is what a heap looks like in memory immediately - * after initialization: - * - * +--------------------------------+ - * 0 | size = 0 | status = used | a.k.a. dummy back flag - * +--------------------------------+ - * 4 | size = size-8 | status = free | a.k.a. front flag - * +--------------------------------+ - * 8 | next = PERM HEAP_TAIL | - * +--------------------------------+ - * 12 | previous = PERM HEAP_HEAD | - * +--------------------------------+ + * This is what a heap looks like in memory immediately after initialization: + * + * + * +--------------------------------+ <- begin = starting_address + * | unused space due to alignment | + * | size < page_size | + * 0 +--------------------------------+ <- first block + * | prev_size = 1 (arbitrary) | + * 4 +--------------------------------+ + * | size = size0 | 1 | + * 8 +---------------------+----------+ <- aligned on page_size + * | next = HEAP_TAIL | | + * 12 +---------------------+ | + * | prev = HEAP_HEAD | memory | + * +---------------------+ | + * | available | * | | - * | memory available | - * | for allocation | + * | for allocation | * | | - * +--------------------------------+ - * size - 8 | size = size-8 | status = free | a.k.a. back flag - * +--------------------------------+ - * size - 4 | size = 0 | status = used | a.k.a. dummy front flag - * +--------------------------------+ + * size0 +--------------------------------+ <- last dummy block + * | prev_size = size0 | + * +4 +--------------------------------+ + * | size = 0 (arbitrary) | 0 | <- prev block is free + * +8 +--------------------------------+ <- aligned on page_size + * | unused space due to alignment | + * | size < page_size | + * +--------------------------------+ <- end = begin + size + * + * This is what a heap looks like after first allocation of SIZE bytes. + * BSIZE stands for SIZE + 4 aligned up on 'page_size' boundary if allocation + * has been performed by _Heap_Allocate(). If allocation has been performed + * by _Heap_Allocate_aligned(), the block size BSIZE is defined differently + * (see 'heapallocatealigned.c' for details). + * + * +--------------------------------+ <- begin = starting_address + * | unused space due to alignment | + * | size < page_size | + * 0 +--------------------------------+ <- first block + * | prev_size = 1 (arbitrary) | + * 4 +--------------------------------+ + * | size = S = size0 - BSIZE | 1 | + * 8 +---------------------+----------+ <- aligned on page_size + * | next = HEAP_TAIL | | + * 12 +---------------------+ | + * | prev = HEAP_HEAD | memory | + * +---------------------+ | + * | available | + * | | + * | for allocation | + * | | + * S +--------------------------------+ <- used block + * | prev_size = size0 - BSIZE | + * +4 +--------------------------------+ + * | size = BSIZE | 0 | <- prev block is free + * +8 +--------------------------------+ <- aligned on page_size + * | . | Pointer returned to the user + * | . | is (S+8) for _Heap_Allocate() + * | . | and is in range + * S + 8 + | user-accessible | [S+8,S+8+page_size) for + * page_size+- - - - - -+ _Heap_Allocate_aligned() + * | area | + * | . | + * S + BSIZE +- - - - - . - - - - -+ <- last dummy block + * | . | + * +4 +--------------------------------+ + * | size = 0 (arbitrary) | 1 | <- prev block is used + * +8 +--------------------------------+ <- aligned on page_size + * | unused space due to alignment | + * | size < page_size | + * +--------------------------------+ <- end = begin + size + * */ uint32_t _Heap_Initialize( @@ -62,31 +114,148 @@ uint32_t _Heap_Initialize( uint32_t page_size ) { - Heap_Block *the_block; - uint32_t the_size; + Heap_Block *the_block; + uint32_t the_size; + _H_uptr_t start; + _H_uptr_t aligned_start; + uint32_t overhead; + Heap_Statistics *const stats = &the_heap->stats; + + if(page_size == 0) + page_size = CPU_ALIGNMENT; + else + _Heap_Align_up( &page_size, CPU_ALIGNMENT ); - if ( !_Heap_Is_page_size_valid( page_size ) || - (size < HEAP_MINIMUM_SIZE) ) - return 0; + /* Calculate aligned_start so that aligned_start + HEAP_BLOCK_USER_OFFSET + (value of user pointer) is aligned on 'page_size' boundary. Make sure + resulting 'aligned_start' is not below 'starting_address'. */ + start = _H_p2u(starting_address); + aligned_start = start + HEAP_BLOCK_USER_OFFSET; + _Heap_Align_up_uptr ( &aligned_start, page_size ); + aligned_start -= HEAP_BLOCK_USER_OFFSET; + + /* Calculate 'min_block_size'. It's HEAP_MIN_BLOCK_SIZE aligned up to the + nearest multiple of 'page_size'. */ + the_heap->min_block_size = HEAP_MIN_BLOCK_SIZE; + _Heap_Align_up ( &the_heap->min_block_size, page_size ); + + /* Calculate 'the_size' -- size of the first block so that there is enough + space at the end for the permanent last block. It is equal to 'size' + minus total overhead aligned down to the nearest multiple of + 'page_size'. */ + overhead = HEAP_OVERHEAD + (aligned_start - start); + if ( size < overhead ) + return 0; /* Too small area for the heap */ + the_size = size - overhead; + _Heap_Align_down ( &the_size, page_size ); + if ( the_size == 0 ) + return 0; /* Too small area for the heap */ the_heap->page_size = page_size; - the_size = size - HEAP_OVERHEAD; + the_heap->begin = starting_address; + the_heap->end = starting_address + size; + + the_block = (Heap_Block *) aligned_start; + + the_block->prev_size = HEAP_PREV_USED; + the_block->size = the_size | HEAP_PREV_USED; + the_block->next = _Heap_Tail( the_heap ); + the_block->prev = _Heap_Head( the_heap ); + _Heap_Head(the_heap)->next = the_block; + _Heap_Tail(the_heap)->prev = the_block; + the_heap->start = the_block; - the_block = (Heap_Block *) starting_address; - the_block->back_flag = HEAP_DUMMY_FLAG; - the_block->front_flag = the_size; - the_block->next = _Heap_Tail( the_heap ); - the_block->previous = _Heap_Head( the_heap ); + _HAssert(_Heap_Is_aligned(the_heap->page_size, CPU_ALIGNMENT)); + _HAssert(_Heap_Is_aligned(the_heap->min_block_size, page_size)); + _HAssert(_Heap_Is_aligned_ptr(_Heap_User_area(the_block), page_size)); - the_heap->start = the_block; - the_heap->first = the_block; - the_heap->permanent_null = NULL; - the_heap->last = the_block; - the_block = _Heap_Next_block( the_block ); - the_block->back_flag = the_size; - the_block->front_flag = HEAP_DUMMY_FLAG; - the_heap->final = the_block; + the_block = _Heap_Block_at( the_block, the_size ); + the_heap->final = the_block; /* Permanent final block of the heap */ + the_block->prev_size = the_size; /* Previous block is free */ + the_block->size = 0; /* This is the only block with size=0 */ + + stats->size = size; + stats->free_size = the_size; + stats->min_free_size = the_size; + stats->free_blocks = 1; + stats->max_free_blocks = 1; + stats->used_blocks = 0; + stats->max_search = 0; + stats->allocs = 0; + stats->searches = 0; + stats->frees = 0; + stats->instance = instance++; return ( the_size - HEAP_BLOCK_USED_OVERHEAD ); } + +/*PAGE + * + * Internal routines shared by _Heap_Allocate() and _Heap_Allocate_aligned(). + * + * Note: there is no reason to put them into a separate file(s) as they are + * always required for heap to be usefull. + * + */ + + +/* + * Convert user requested 'size' of memory block to the block size. + * Return block size on success, 0 if overflow occured + */ +uint32_t _Heap_Calc_block_size( + uint32_t size, + uint32_t page_size, + uint32_t min_size) +{ + uint32_t block_size = size + HEAP_BLOCK_USED_OVERHEAD; + _Heap_Align_up(&block_size, page_size); + if(block_size < min_size) block_size = min_size; + return (block_size > size) ? block_size : 0; +} + + +/* + * Allocate block of size 'alloc_size' from 'the_block' belonging to + * 'the_heap'. Either split 'the_block' or allocate it entirely. + * Return the block allocated. + */ +Heap_Block* _Heap_Block_allocate( + Heap_Control* the_heap, + Heap_Block* the_block, + uint32_t alloc_size) +{ + Heap_Statistics *const stats = &the_heap->stats; + uint32_t const block_size = _Heap_Block_size(the_block); + uint32_t const the_rest = block_size - alloc_size; + + _HAssert(_Heap_Is_aligned(block_size, the_heap->page_size)); + _HAssert(_Heap_Is_aligned(alloc_size, the_heap->page_size)); + _HAssert(alloc_size <= block_size); + + if(the_rest >= the_heap->min_block_size) { + /* Split the block so that lower part is still free, and upper part + becomes used. */ + the_block->size = the_rest | HEAP_PREV_USED; + the_block = _Heap_Block_at(the_block, the_rest); + the_block->prev_size = the_rest; + the_block->size = alloc_size; + } + else { + /* Don't split the block as remainder is either zero or too small to be + used as a separate free block. Change 'alloc_size' to the size of the + block and remove the block from the list of free blocks. */ + _Heap_Block_remove(the_block); + alloc_size = block_size; + stats->free_blocks -= 1; + } + /* Mark the block as used (in the next block). */ + _Heap_Block_at(the_block, alloc_size)->size |= HEAP_PREV_USED; + /* Update statistics */ + stats->free_size -= alloc_size; + if(stats->min_free_size > stats->free_size) + stats->min_free_size = stats->free_size; + stats->used_blocks += 1; + return the_block; +} 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; } diff --git a/cpukit/score/src/heapextend.c b/cpukit/score/src/heapextend.c index 3cb318d70b..8166d99e6f 100644 --- a/cpukit/score/src/heapextend.c +++ b/cpukit/score/src/heapextend.c @@ -39,8 +39,8 @@ Heap_Extend_status _Heap_Extend( uint32_t *amount_extended ) { - Heap_Block *the_block; - uint32_t *p; + uint32_t the_size; + Heap_Statistics *const stats = &the_heap->stats; /* * The overhead was taken from the original heap memory. @@ -62,22 +62,13 @@ Heap_Extend_status _Heap_Extend( * As noted, this code only supports (4). */ - if ( starting_address >= (void *) the_heap->start && /* case 3 */ - starting_address <= (void *) the_heap->final + if ( starting_address >= the_heap->begin && /* case 3 */ + starting_address < the_heap->end ) return HEAP_EXTEND_ERROR; - if ( starting_address < (void *) the_heap->start ) { /* cases 1 and 2 */ - - return HEAP_EXTEND_NOT_IMPLEMENTED; /* cases 1 and 2 */ - - } else { /* cases 4 and 5 */ - - the_block = (Heap_Block *) - _Addresses_Subtract_offset( starting_address, HEAP_OVERHEAD ); - if ( the_block != the_heap->final ) - return HEAP_EXTEND_NOT_IMPLEMENTED; /* case 5 */ - } + if ( starting_address != the_heap->end ) + return HEAP_EXTEND_NOT_IMPLEMENTED; /* cases 1, 2, and 5 */ /* * Currently only case 4 should make it to this point. @@ -85,27 +76,26 @@ Heap_Extend_status _Heap_Extend( * block and free it. */ + old_final = the_heap->final; + the_heap->end = _Addresses_Add_offset( the_heap->end, size ); + the_size = _Addresses_Subtract( the_heap->end, old_final ) - HEAP_OVERHEAD; + _Heap_Align_down( &the_size, the_heap->page_size ); + *amount_extended = size; - old_final = the_heap->final; - new_final = _Addresses_Add_offset( old_final, size ); - /* SAME AS: _Addresses_Add_offset( starting_address, size-HEAP_OVERHEAD ); */ + if( the_size < the_heap->min_block_size ) + return HEAP_EXTEND_SUCCESSFUL; + old_final->size = the_size | (old_final->size & HEAP_PREV_USED); + new_final = _Heap_Block_at( old_final, the_size ); + new_final->size = HEAP_PREV_USED; the_heap->final = new_final; - old_final->front_flag = - new_final->back_flag = _Heap_Build_flag( size, HEAP_BLOCK_USED ); - new_final->front_flag = HEAP_DUMMY_FLAG; - - /* - * Must pass in address of "user" area - * So add in the offset field. - */ + stats->size += size; + stats->used_blocks += 1; + stats->frees -= 1; /* Don't count subsequent call as actual free() */ - p = (uint32_t *) &old_final->next; - *p = sizeof(uint32_t ); - p++; - _Heap_Free( the_heap, p ); + _Heap_Free( the_heap, _Heap_User_area( old_final ) ); return HEAP_EXTEND_SUCCESSFUL; } diff --git a/cpukit/score/src/heapfree.c b/cpukit/score/src/heapfree.c index 40e56a7b88..0bd413d1dc 100644 --- a/cpukit/score/src/heapfree.c +++ b/cpukit/score/src/heapfree.c @@ -39,65 +39,90 @@ boolean _Heap_Free( { Heap_Block *the_block; Heap_Block *next_block; - Heap_Block *new_next_block; - Heap_Block *previous_block; - Heap_Block *temporary_block; - uint32_t the_size; + uint32_t the_size; + uint32_t next_size; + Heap_Statistics *const stats = &the_heap->stats; + boolean next_is_free; - the_block = _Heap_User_block_at( starting_address ); + _Heap_Start_of_block( the_heap, starting_address, &the_block ); - if ( !_Heap_Is_block_in( the_heap, the_block ) || - _Heap_Is_block_free( the_block ) ) { - return( FALSE ); + if ( !_Heap_Is_block_in( the_heap, the_block ) ) { + _HAssert(starting_address == NULL); + return( FALSE ); } - the_size = _Heap_Block_size( the_block ); + the_size = _Heap_Block_size( the_block ); next_block = _Heap_Block_at( the_block, the_size ); - if ( !_Heap_Is_block_in( the_heap, next_block ) || - (the_block->front_flag != next_block->back_flag) ) { - return( FALSE ); + if ( !_Heap_Is_prev_used( next_block ) ) { + _HAssert(FALSE); + return( FALSE ); + } + + if ( !_Heap_Is_block_in( the_heap, next_block ) ) { + _HAssert(FALSE); + return( FALSE ); } - if ( _Heap_Is_previous_block_free( the_block ) ) { - previous_block = _Heap_Previous_block( the_block ); + next_size = _Heap_Block_size( next_block ); + next_is_free = next_block < the_heap->final && + !_Heap_Is_prev_used(_Heap_Block_at(next_block, next_size)); + + if ( !_Heap_Is_prev_used( the_block ) ) { + uint32_t const prev_size = the_block->prev_size; + Heap_Block *const prev_block = _Heap_Block_at( the_block, -prev_size ); - if ( !_Heap_Is_block_in( the_heap, previous_block ) ) { - return( FALSE ); + if ( !_Heap_Is_block_in( the_heap, prev_block ) ) { + _HAssert(FALSE); + return( FALSE ); } - if ( _Heap_Is_block_free( next_block ) ) { /* coalesce both */ - previous_block->front_flag += next_block->front_flag + the_size; - temporary_block = _Heap_Next_block( previous_block ); - temporary_block->back_flag = previous_block->front_flag; - next_block->next->previous = next_block->previous; - next_block->previous->next = next_block->next; + /* As we always coalesce free blocks, the block that preceedes prev_block + must have been used. */ + if ( !_Heap_Is_prev_used ( prev_block) ) { + _HAssert(FALSE); + return( FALSE ); + } + + if ( next_is_free ) { /* coalesce both */ + uint32_t const size = the_size + prev_size + next_size; + _Heap_Block_remove( next_block ); + stats->free_blocks -= 1; + prev_block->size = size | HEAP_PREV_USED; + next_block = _Heap_Block_at( prev_block, size ); + _HAssert(!_Heap_Is_prev_used( next_block)); + next_block->prev_size = size; } - else { /* coalesce prev */ - previous_block->front_flag = - next_block->back_flag = previous_block->front_flag + the_size; + else { /* coalesce prev */ + uint32_t const size = the_size + prev_size; + prev_block->size = size | HEAP_PREV_USED; + next_block->size &= ~HEAP_PREV_USED; + next_block->prev_size = size; } } - else if ( _Heap_Is_block_free( next_block ) ) { /* coalesce next */ - the_block->front_flag = the_size + next_block->front_flag; - new_next_block = _Heap_Next_block( the_block ); - new_next_block->back_flag = the_block->front_flag; - the_block->next = next_block->next; - the_block->previous = next_block->previous; - next_block->previous->next = the_block; - next_block->next->previous = the_block; - - if (the_heap->first == next_block) - the_heap->first = the_block; + else if ( next_is_free ) { /* coalesce next */ + uint32_t const size = the_size + next_size; + _Heap_Block_replace( next_block, the_block ); + the_block->size = size | HEAP_PREV_USED; + next_block = _Heap_Block_at( the_block, size ); + next_block->prev_size = size; } - else { /* no coalesce */ - next_block->back_flag = - the_block->front_flag = the_size; - the_block->previous = _Heap_Head( the_heap ); - the_block->next = the_heap->first; - the_heap->first = the_block; - the_block->next->previous = the_block; + else { /* no coalesce */ + /* Add 'the_block' to the head of the free blocks list as it tends to + produce less fragmentation than adding to the tail. */ + _Heap_Block_insert_after( _Heap_Head( the_heap), the_block ); + the_block->size = the_size | HEAP_PREV_USED; + next_block->size &= ~HEAP_PREV_USED; + next_block->prev_size = the_size; + + stats->free_blocks += 1; + if ( stats->max_free_blocks < stats->free_blocks ) + stats->max_free_blocks = stats->free_blocks; } + stats->used_blocks -= 1; + stats->free_size += the_size; + stats->frees += 1; + return( TRUE ); } diff --git a/cpukit/score/src/heapgetfreeinfo.c b/cpukit/score/src/heapgetfreeinfo.c index 910eda838f..1b8d8598a0 100644 --- a/cpukit/score/src/heapgetfreeinfo.c +++ b/cpukit/score/src/heapgetfreeinfo.c @@ -37,21 +37,24 @@ void _Heap_Get_free_information( ) { Heap_Block *the_block; + Heap_Block *const tail = _Heap_Tail(the_heap); info->number = 0; info->largest = 0; info->total = 0; - for ( the_block = the_heap->first; - ; - the_block = the_block->next ) { - if ( the_block == _Heap_Tail( the_heap ) ) - return; - - info->number++; - info->total += the_block->front_flag; + for(the_block = _Heap_First(the_heap); + the_block != tail; + the_block = the_block->next) + { + uint32_t const the_size = _Heap_Block_size(the_block); + + /* As we always coalesce free blocks, prev block must have been used. */ + _HAssert(_Heap_Is_prev_used(the_block)); - if ( the_block->front_flag >= info->largest ) - info->largest = the_block->front_flag; + info->number++; + info->total += the_size; + if ( info->largest < the_size ) + info->largest = the_size; } } diff --git a/cpukit/score/src/heapgetinfo.c b/cpukit/score/src/heapgetinfo.c index 9e71ea7e43..6ba368c7a0 100644 --- a/cpukit/score/src/heapgetinfo.c +++ b/cpukit/score/src/heapgetinfo.c @@ -8,6 +8,7 @@ * found in the file LICENSE in this distribution or at * http://www.rtems.com/license/LICENSE. * + * $Id$ */ @@ -37,11 +38,11 @@ Heap_Get_information_status _Heap_Get_information( Heap_Information_block *the_info ) { - Heap_Block *the_block = 0; /* avoid warnings */ - Heap_Block *next_block = 0; /* avoid warnings */ - int notdone = 1; - uint32_t size; + Heap_Block *the_block = the_heap->start; + Heap_Block *const end = the_heap->final; + _HAssert(the_block->prev_size == HEAP_PREV_USED); + _HAssert(_Heap_Is_prev_used(the_block)); the_info->Free.number = 0; the_info->Free.total = 0; @@ -50,60 +51,31 @@ Heap_Get_information_status _Heap_Get_information( the_info->Used.total = 0; the_info->Used.largest = 0; - /* - * We don't want to allow walking the heap until we have - * transferred control to the user task so we watch the - * system state. - */ - - if ( !_System_state_Is_up( _System_state_Get() ) ) - return HEAP_GET_INFORMATION_SYSTEM_STATE_ERROR; - - the_block = the_heap->start; - - /* - * Handle the 1st block - */ - - if ( the_block->back_flag != HEAP_DUMMY_FLAG ) { - return HEAP_GET_INFORMATION_BLOCK_ERROR; + while ( the_block != end ) { + uint32_t const the_size = _Heap_Block_size(the_block); + Heap_Block *const next_block = _Heap_Block_at(the_block, the_size); + + if ( _Heap_Is_prev_used(next_block) ) { + the_info->Used.number++; + the_info->Used.total += the_size; + if ( the_info->Used.largest < the_size ) + the_info->Used.largest = the_size; + } else { + the_info->Free.number++; + the_info->Free.total += the_size; + if ( the_info->Free.largest < the_size ) + the_info->Free.largest = the_size; + if ( the_size != next_block->prev_size ) + return HEAP_GET_INFORMATION_BLOCK_ERROR; + } + + the_block = next_block; } - while (notdone) { - - /* - * Accumulate size - */ - - size = _Heap_Block_size(the_block); - if ( _Heap_Is_block_free(the_block) ) { - the_info->Free.number++; - the_info->Free.total += size; - if ( size > the_info->Free.largest ) - the_info->Free.largest = size; - } else { - the_info->Used.number++; - the_info->Used.total += size; - if ( size > the_info->Used.largest ) - the_info->Used.largest = size; - } - - /* - * Handle the last block - */ - - if ( the_block->front_flag != HEAP_DUMMY_FLAG ) { - next_block = _Heap_Next_block(the_block); - if ( the_block->front_flag != next_block->back_flag ) { - return HEAP_GET_INFORMATION_BLOCK_ERROR; - } - } - - if ( the_block->front_flag == HEAP_DUMMY_FLAG ) - notdone = 0; - else - the_block = next_block; - } /* while(notdone) */ + /* Handle the last dummy block. Don't consider this block to be + "used" as client never allocated it. Make 'Used.total' contain this + blocks' overhead though. */ + the_info->Used.total += HEAP_OVERHEAD; return HEAP_GET_INFORMATION_SUCCESSFUL; } diff --git a/cpukit/score/src/heapsizeofuserarea.c b/cpukit/score/src/heapsizeofuserarea.c index 3321816c4a..002e815bd5 100644 --- a/cpukit/score/src/heapsizeofuserarea.c +++ b/cpukit/score/src/heapsizeofuserarea.c @@ -20,12 +20,14 @@ * * _Heap_Size_of_user_area * - * This kernel routine returns the size of the memory area - * given heap block. + * This kernel routine sets '*size' to the size of the block of memory + * which begins at 'starting_address'. + * It returns TRUE if the 'starting_address' is in the heap, and FALSE + * otherwise. * * Input parameters: * the_heap - pointer to heap header - * starting_address - starting address of the memory block to free. + * starting_address - starting address of the memory block * size - pointer to size of area * * Output parameters: @@ -37,7 +39,7 @@ boolean _Heap_Size_of_user_area( Heap_Control *the_heap, void *starting_address, - uint32_t *size + size_t *size ) { Heap_Block *the_block; @@ -48,22 +50,32 @@ boolean _Heap_Size_of_user_area( starting_address, (void *)the_heap->start, (void *)the_heap->final ) ) return( FALSE ); - the_block = _Heap_User_block_at( starting_address ); - - if ( !_Heap_Is_block_in( the_heap, the_block ) ) - return( FALSE ); + _Heap_Start_of_block( the_heap, starting_address, &the_block ); - if ( _Heap_Is_block_free( the_block ) ) + if ( !_Heap_Is_block_in( the_heap, the_block ) ) return( FALSE ); the_size = _Heap_Block_size( the_block ); next_block = _Heap_Block_at( the_block, the_size ); - if ( !_Heap_Is_block_in( the_heap, next_block ) || - (the_block->front_flag != next_block->back_flag) ) + if ( + !_Heap_Is_block_in( the_heap, next_block ) || + !_Heap_Is_prev_used( next_block ) + ) return( FALSE ); - *size = the_size; + /* 'starting_address' could be greater than 'the_block' address plus + HEAP_BLOCK_USER_OFFSET as _Heap_Allocate_aligned() may produce such user + pointers. To get rid of this offset we calculate user size as difference + between the end of 'the_block' (='next_block') and 'starting_address' + and then add correction equal to the offset of the 'size' field of the + 'Heap_Block' structure. The correction is due to the fact that + 'prev_size' field of the next block is actually used as user accessible + area of 'the_block'. */ + + *size = _Addresses_Subtract ( next_block, starting_address ) + + HEAP_BLOCK_HEADER_OFFSET; + return( TRUE ); } diff --git a/cpukit/score/src/heapwalk.c b/cpukit/score/src/heapwalk.c index 4f93ae7be0..a589b3cdf4 100644 --- a/cpukit/score/src/heapwalk.c +++ b/cpukit/score/src/heapwalk.c @@ -30,32 +30,32 @@ * Output parameters: NONE */ -#ifndef RTEMS_DEBUG +#if !defined(RTEMS_HEAP_DEBUG) -void _Heap_Walk( +boolean _Heap_Walk( Heap_Control *the_heap, int source, boolean do_dump ) { + return TRUE; } -#else +#else /* defined(RTEMS_HEAP_DEBUG) */ #include -#include -void _Heap_Walk( +boolean _Heap_Walk( Heap_Control *the_heap, int source, boolean do_dump ) { - Heap_Block *the_block = 0; /* avoid warnings */ - Heap_Block *next_block = 0; /* avoid warnings */ - int notdone = 1; - int error = 0; - int passes = 0; + Heap_Block *the_block = the_heap->start; + Heap_Block *const end = the_heap->final; + Heap_Block *const tail = _Heap_Tail(the_heap); + int error = 0; + int passes = 0; /* * We don't want to allow walking the heap until we have @@ -64,86 +64,110 @@ void _Heap_Walk( */ if ( !_System_state_Is_up( _System_state_Get() ) ) - return; + return FALSE; - the_block = the_heap->start; + if (source < 0) + source = the_heap->stats.instance; - if (do_dump == TRUE) { - printf("\nPASS: %d start @ 0x%p final 0x%p, first 0x%p last 0x%p\n", - source, the_heap->start, the_heap->final, - the_heap->first, the_heap->last - ); - } + if (do_dump == TRUE) + printf("\nPASS: %d start %p final %p first %p last %p begin %p end %p\n", + source, the_block, end, + _Heap_First(the_heap), _Heap_Last(the_heap), + the_heap->begin, the_heap->end); /* * Handle the 1st block */ - if (the_block->back_flag != HEAP_DUMMY_FLAG) { - printf("PASS: %d Back flag of 1st block isn't HEAP_DUMMY_FLAG\n", source); + if (!_Heap_Is_prev_used(the_block)) { + printf("PASS: %d !HEAP_PREV_USED flag of 1st block isn't set\n", source); error = 1; } - while (notdone) { - passes++; - if (error && (passes > 10)) - abort(); - - if (do_dump == TRUE) { - printf("PASS: %d Block @ 0x%p Back %d, Front %d", - source, the_block, - the_block->back_flag, the_block->front_flag); - if ( _Heap_Is_block_free(the_block) ) { - printf( " Prev 0x%p, Next 0x%p\n", - the_block->previous, the_block->next); - } else { - printf("\n"); - } + if (the_block->prev_size != HEAP_PREV_USED) { + printf("PASS: %d !prev_size of 1st block isn't HEAP_PREV_USED\n", source); + error = 1; + } + + while ( the_block < end ) { + uint32_t const the_size = _Heap_Block_size(the_block); + Heap_Block *const next_block = _Heap_Block_at(the_block, the_size); + boolean prev_used = _Heap_Is_prev_used(the_block); + + if (do_dump) { + printf("PASS: %d block %p size %d(%c)", + source, the_block, the_size, (prev_used ? 'U' : 'F')); + if (prev_used) + printf(" prev_size %d", the_block->prev_size); + else + printf(" (prev_size) %d", the_block->prev_size); } - /* - * Handle the last block - */ + if (!_Heap_Is_block_in(the_heap, next_block)) { + if (do_dump) printf("\n"); + printf("PASS: %d !block %p is out of heap\n", source, next_block); + error = 1; + break; + } - if ( the_block->front_flag != HEAP_DUMMY_FLAG ) { - next_block = _Heap_Next_block(the_block); - if ( the_block->front_flag != next_block->back_flag ) { + if (!_Heap_Is_prev_used(next_block)) { + if (do_dump) + printf( " prev %p next %p", the_block->prev, the_block->next); + if (_Heap_Block_size(the_block) != next_block->prev_size) { + if (do_dump) printf("\n"); + printf("PASS: %d !front and back sizes don't match", source); error = 1; - printf("PASS: %d Front and back flags don't match\n", source); - printf(" Current Block (%p): Back - %d, Front - %d", - the_block, the_block->back_flag, the_block->front_flag); - if (do_dump == TRUE) { - if (_Heap_Is_block_free(the_block)) { - printf(" Prev 0x%p, Next 0x%p\n", - the_block->previous, the_block->next); - } else { - printf("\n"); - } - } else { - printf("\n"); - } - printf(" Next Block (%p): Back - %d, Front - %d", - next_block, next_block->back_flag, next_block->front_flag); - if (do_dump == TRUE) { - if (_Heap_Is_block_free(next_block)) { - printf(" Prev 0x%p, Next 0x%p\n", - the_block->previous, the_block->next); - } else { - printf("\n"); - } - } else { - printf("\n"); + } + if (!prev_used) { + if (do_dump || error) printf("\n"); + printf("PASS: %d !two consecutive blocks are free", source); + error = 1; + } + + { /* Check if 'the_block' is in the free block list */ + Heap_Block* block = _Heap_First(the_heap); + while(block != the_block && block != tail) + block = block->next; + if(block != the_block) { + if (do_dump || error) printf("\n"); + printf("PASS: %d !the_block not in the free list", source); + error = 1; } } + } + if (do_dump || error) printf("\n"); - if (the_block->front_flag == HEAP_DUMMY_FLAG) - notdone = 0; - else - the_block = next_block; + if (the_size < the_heap->min_block_size) { + printf("PASS: %d !block size is too small\n", source); + error = 1; + break; + } + if (!_Heap_Is_aligned( the_size, the_heap->page_size)) { + printf("PASS: %d !block size is misaligned\n", source); + error = 1; + } + + if (++passes > (do_dump ? 10 : 0) && error) + break; + + the_block = next_block; + } + + if (the_block != end) { + printf("PASS: %d !last block address isn't equal to 'final'\n", source); + error = 1; + } + + if (_Heap_Block_size(the_block) != 0) { + printf("PASS: %d !last block's size isn't 0\n", source); + error = 1; } - if (error) - abort(); + if(do_dump && error) + abort(); + + return error == 0; + } -#endif +#endif /* defined(RTEMS_HEAP_DEBUG) */ -- cgit v1.2.3