From dea3eccb38b556b04552219e00b7abd656587278 Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Sun, 6 Sep 2009 15:24:08 +0000 Subject: 2009-09-06 Sebastian Huber * libcsupport/src/free.c, libmisc/stackchk/check.c, rtems/include/rtems/rtems/region.h, rtems/src/regioncreate.c, rtems/src/regionextend.c, rtems/src/regiongetinfo.c, rtems/src/regiongetsegment.c, rtems/src/regiongetsegmentsize.c, rtems/src/regionresizesegment.c, score/src/pheapallocate.c, score/src/pheapallocatealigned.c, score/src/pheapextend.c, score/src/pheapfree.c, score/src/pheapgetblocksize.c, score/src/pheapgetfreeinfo.c, score/src/pheapgetinfo.c, score/src/pheapgetsize.c, score/src/pheapinit.c, score/src/pheapresizeblock.c, score/src/pheapwalk.c: Update for heap API changes. * score/include/rtems/score/apimutex.h, score/include/rtems/score/object.h: Documentation. * score/include/rtems/score/heap.h, score/include/rtems/score/protectedheap.h, score/inline/rtems/score/heap.inl, score/src/heap.c, score/src/heapallocate.c, score/src/heapallocatealigned.c, score/src/heapextend.c, score/src/heapfree.c, score/src/heapgetfreeinfo.c, score/src/heapgetinfo.c, score/src/heapresizeblock.c, score/src/heapsizeofuserarea.c, score/src/heapwalk.c: Overall cleanup. Added boundary constraint to allocation function. More changes follow. --- cpukit/score/src/heapallocate.c | 214 +++++++++++++++++++++++++++++++++++----- 1 file changed, 189 insertions(+), 25 deletions(-) (limited to 'cpukit/score/src/heapallocate.c') diff --git a/cpukit/score/src/heapallocate.c b/cpukit/score/src/heapallocate.c index 7c9e78f31e..7b0f51e232 100644 --- a/cpukit/score/src/heapallocate.c +++ b/cpukit/score/src/heapallocate.c @@ -1,9 +1,17 @@ -/* - * Heap Handler +/** + * @file + * + * @ingroup ScoreHeap * + * @brief Heap Handler implementation. + */ + +/* * COPYRIGHT (c) 1989-1999. * On-Line Applications Research Corporation (OAR). * + * Copyright (c) 2009 embedded brains GmbH. + * * The license and distribution terms for this file may be * found in the file LICENSE in this distribution or at * http://www.rtems.com/license/LICENSE. @@ -19,48 +27,204 @@ #include #include -void *_Heap_Allocate( Heap_Control *heap, uintptr_t size ) +#ifdef RTEMS_HEAP_DEBUG + static void _Heap_Check_allocation( + const Heap_Control *heap, + const Heap_Block *block, + uintptr_t alloc_begin, + uintptr_t alloc_size, + uintptr_t alignment, + uintptr_t boundary + ) + { + uintptr_t const min_block_size = heap->min_block_size; + uintptr_t const page_size = heap->page_size; + + uintptr_t const block_begin = (uintptr_t) block; + uintptr_t const block_size = _Heap_Block_size( block ); + uintptr_t const block_end = block_begin + block_size; + + uintptr_t const alloc_end = alloc_begin + alloc_size; + + uintptr_t const alloc_area_begin = _Heap_Alloc_area_of_block( block ); + uintptr_t const alloc_area_offset = alloc_begin - alloc_area_begin; + uintptr_t const alloc_area_size = alloc_area_offset + alloc_size; + + _HAssert( block_size >= min_block_size ); + _HAssert( block_begin < block_end ); + _HAssert( + _Heap_Is_aligned( block_begin + HEAP_BLOCK_HEADER_SIZE, page_size ) + ); + _HAssert( + _Heap_Is_aligned( block_size, page_size ) + ); + + _HAssert( alloc_end <= block_end + HEAP_BLOCK_SIZE_OFFSET ); + _HAssert( alloc_area_begin == block_begin + HEAP_BLOCK_HEADER_SIZE); + _HAssert( alloc_area_offset < page_size ); + + _HAssert( _Heap_Is_aligned( alloc_area_begin, page_size ) ); + if ( alignment == 0 ) { + _HAssert( alloc_begin == alloc_area_begin ); + } else { + _HAssert( _Heap_Is_aligned( alloc_begin, alignment ) ); + } + + if ( boundary != 0 ) { + uintptr_t boundary_line = _Heap_Align_down( alloc_end, boundary ); + + _HAssert( alloc_size <= boundary ); + _HAssert( boundary_line <= alloc_begin || alloc_end <= boundary_line ); + } + } +#else + #define _Heap_Check_allocation( h, b, ab, as, ag, bd ) ((void) 0) +#endif + +static uintptr_t _Heap_Check_block( + const Heap_Control *heap, + const Heap_Block *block, + uintptr_t alloc_size, + uintptr_t alignment, + uintptr_t boundary +) +{ + uintptr_t const page_size = heap->page_size; + uintptr_t const min_block_size = heap->min_block_size; + + uintptr_t const block_begin = (uintptr_t) block; + uintptr_t const block_size = _Heap_Block_size( block ); + uintptr_t const block_end = block_begin + block_size; + + uintptr_t const alloc_begin_floor = _Heap_Alloc_area_of_block( block ); + uintptr_t const alloc_begin_ceiling = block_end - min_block_size + + HEAP_BLOCK_HEADER_SIZE + page_size - 1; + + uintptr_t alloc_end = block_end + HEAP_BLOCK_SIZE_OFFSET; + uintptr_t alloc_begin = alloc_end - alloc_size; + + alloc_begin = _Heap_Align_down( alloc_begin, alignment ); + + /* Ensure that the we have a valid new block at the end */ + if ( alloc_begin > alloc_begin_ceiling ) { + alloc_begin = _Heap_Align_down( alloc_begin_ceiling, alignment ); + } + + alloc_end = alloc_begin + alloc_size; + + /* Ensure boundary constaint */ + if ( boundary != 0 ) { + uintptr_t const boundary_floor = alloc_begin_floor + alloc_size; + uintptr_t boundary_line = _Heap_Align_down( alloc_end, boundary ); + + while ( alloc_begin < boundary_line && boundary_line < alloc_end ) { + if ( boundary_line < boundary_floor ) { + return 0; + } + alloc_begin = boundary_line - alloc_size; + alloc_begin = _Heap_Align_down( alloc_begin, alignment ); + alloc_end = alloc_begin + alloc_size; + boundary_line = _Heap_Align_down( alloc_end, boundary ); + } + } + + /* Ensure that the we have a valid new block at the beginning */ + if ( alloc_begin >= alloc_begin_floor ) { + uintptr_t const alloc_block_begin = + (uintptr_t) _Heap_Block_of_alloc_area( alloc_begin, page_size ); + uintptr_t const free_size = alloc_block_begin - block_begin; + + if ( free_size >= min_block_size || free_size == 0 ) { + return alloc_begin; + } + } + + return 0; +} + +void *_Heap_Allocate_aligned_with_boundary( + Heap_Control *heap, + uintptr_t alloc_size, + uintptr_t alignment, + uintptr_t boundary +) { Heap_Statistics *const stats = &heap->stats; - Heap_Block * const tail = _Heap_Free_list_tail( heap ); - Heap_Block *block = _Heap_First_free_block( heap ); + Heap_Block *const free_list_tail = _Heap_Free_list_tail( heap ); + Heap_Block *block = _Heap_Free_list_first( heap ); + uintptr_t const block_size_floor = alloc_size + HEAP_BLOCK_HEADER_SIZE + - HEAP_BLOCK_SIZE_OFFSET; + uintptr_t const page_size = heap->page_size; + uintptr_t alloc_begin = 0; uint32_t search_count = 0; - void *alloc_area_begin_ptr = NULL; - size = _Heap_Calc_block_size( size, heap->page_size, heap->min_block_size ); - if( size == 0 ) { + if ( block_size_floor < alloc_size ) { + /* Integer overflow occured */ return NULL; } - /* - * Find large enough free block. - * - * Do not bother to mask out the HEAP_PREV_BLOCK_USED bit as it will not - * change the result of the size comparison. - */ - while (block != tail && block->size_and_flag < size) { - _HAssert( _Heap_Is_prev_used( block )); + if ( boundary != 0 ) { + if ( boundary < alloc_size ) { + return NULL; + } - block = block->next; - ++search_count; + if ( alignment == 0 ) { + alignment = page_size; + } } - if (block != tail) { - _Heap_Block_allocate( heap, block, size ); + while ( block != free_list_tail ) { + _HAssert( _Heap_Is_prev_used( block ) ); + + /* Statistics */ + ++search_count; + + /* + * The HEAP_PREV_BLOCK_USED flag is always set in the block size_and_flag + * field. Thus the value is about one unit larger than the real block + * size. The greater than operator takes this into account. + */ + if ( block->size_and_flag > block_size_floor ) { + if ( alignment == 0 ) { + alloc_begin = _Heap_Alloc_area_of_block( block ); + } else { + alloc_begin = _Heap_Check_block( + heap, + block, + alloc_size, + alignment, + boundary + ); + } + } + + if ( alloc_begin != 0 ) { + break; + } + + block = block->next; + } - alloc_area_begin_ptr = (void *) _Heap_Alloc_area_of_block( block ); + if ( alloc_begin != 0 ) { + block = _Heap_Block_allocate( heap, block, alloc_begin, alloc_size ); - _HAssert( _Heap_Is_aligned( (uintptr_t) alloc_area_begin_ptr, heap->page_size )); + _Heap_Check_allocation( + heap, + block, + alloc_begin, + alloc_size, + alignment, + boundary + ); /* Statistics */ - ++stats->allocs; stats->searches += search_count; } /* Statistics */ - if (stats->max_search < search_count) { + if ( stats->max_search < search_count ) { stats->max_search = search_count; } - return alloc_area_begin_ptr; + return (void *) alloc_begin; } -- cgit v1.2.3