From 371cea31d3cffb1e1d2ae2e865d1e9a462a3fbd6 Mon Sep 17 00:00:00 2001 From: Joel Sherrill Date: Wed, 26 Aug 2009 12:00:24 +0000 Subject: 2009-08-24 Sebastian Huber * libmisc/stackchk/check.c, rtems/src/regionreturnsegment.c, rtems/src/regiongetsegmentsize.c, src/heapalignupuptr.c, src/heapallocatealigned.c, src/heapallocate.c, src/heap.c, src/heapextend.c, src/heapfree.c, src/heapgetfreeinfo.c, src/heapgetinfo.c, src/heapresizeblock.c, src/heapsizeofuserarea.c, src/heapwalk.c, src/pheapgetblocksize.c, inline/rtems/score/heap.inl, include/rtems/score/heap.h: Overall cleanup. Changed all types for addresses, sizes, offsets and alignments to uintptr_t. Reformatted. Added variables for clarity. Renamed various objects. Enabled _HAssert() for all instances. More changes follow. --- cpukit/score/include/rtems/score/heap.h | 481 ++++++++++++++++---------------- 1 file changed, 237 insertions(+), 244 deletions(-) (limited to 'cpukit/score/include/rtems/score/heap.h') diff --git a/cpukit/score/include/rtems/score/heap.h b/cpukit/score/include/rtems/score/heap.h index 52b55fac70..fedddd20f3 100644 --- a/cpukit/score/include/rtems/score/heap.h +++ b/cpukit/score/include/rtems/score/heap.h @@ -1,23 +1,10 @@ /** - * @file rtems/score/heap.h - * - * This include file contains the information pertaining to the Heap - * Handler. A heap is a doubly linked list of variable size - * blocks which are allocated using the first fit method. Garbage - * collection is performed each time a block is returned to the heap by - * coalescing neighbor blocks. Control information for both allocated - * and unallocated blocks is contained in the heap space. A heap control - * structure contains control information for the heap. - * - * FIXME: the alignment routines could be made faster should we require only - * powers of two to be supported both for 'page_size' and for - * 'alignment' arguments. However, both workspace and malloc heaps are - * initialized with CPU_HEAP_ALIGNMENT as 'page_size', and while all - * the BSPs seem to use CPU_ALIGNMENT (that is power of two) as - * CPU_HEAP_ALIGNMENT, for whatever reason CPU_HEAP_ALIGNMENT is only - * required to be multiple of CPU_ALIGNMENT and explicitly not - * required to be a power of two. + * @file * + * Heap Handler API. + */ + +/* * COPYRIGHT (c) 1989-2006. * On-Line Applications Research Corporation (OAR). * @@ -31,104 +18,162 @@ #ifndef _RTEMS_SCORE_HEAP_H #define _RTEMS_SCORE_HEAP_H -/** - * @defgroup ScoreHeap Heap Handler - * - * This handler encapsulates functionality which provides the foundation - * Heap services used in all of the APIs supported by RTEMS. - */ -/**@{*/ - #ifdef __cplusplus extern "C" { #endif /** - * This type defines unsigned integer type to store 'void*'. Analog of C99 - * 'uintptr_t'. This should work on 16/32/64 bit architectures. - * - * FIXME: Something like this should better be defined by - * 'rtems/score/types.h' and used here. - */ - -typedef uintptr_t _H_uptr_t; - -/** - * Forward reference - * - * @ref Heap_Block - */ -typedef struct Heap_Block_struct Heap_Block; - -/** - * The following defines the data structure used to manage individual blocks - * in a heap. When the block is allocated, the 'next' and 'prev' fields, as - * well as 'prev_size' field of the next block, are not used by the heap - * manager and thus the address returned for the block starts at the address - * of the 'next' field and the size of the user accessible area includes the - * size of the 'prev_size' field. - * - * @note The 'next' and 'prev' pointers are only valid when the block is free. - * Caution must be taken to ensure that every block is large enough to - * hold them and that they are not accessed while the block is actually - * allocated (i.e., not free). - * - * @note The 'prev_size' field is only valid when HEAP_PREV_USED bit is clear - * in the 'size' field indicating that previous block is not allocated. - * If the bit is set, the 'prev_size' field is part of user-accessible - * space of the previous allocated block and thus shouldn't be accessed - * by the heap manager code. This trick allows to further decrease - * overhead in the used blocks to the size of 'size' field (4 bytes). - * - */ - -struct Heap_Block_struct { - /** size of prev block (if prev block is free) */ - uint32_t prev_size; - /** size of block in bytes and status of prev block */ - uint32_t size; - /** pointer to the next free block */ - Heap_Block *next; - /** pointer to the previous free block */ - Heap_Block *prev; -}; - -/** - * This flag used in the 'size' field of each heap block to indicate - * if previous block is free or in use. As sizes are always multiples of - * 4, the 2 least significant bits would always be 0, and we use one of them - * to store the flag. - */ - -#define HEAP_PREV_USED 1u /* indicates previous block is in use */ - -/** - * The following constants reflect various requirements of the - * heap data structures which impact the management of a heap. - */ - -#define HEAP_MIN_BLOCK_SIZE (sizeof(Heap_Block)) - -/** - * Offset of the block header from the block pointer. Equal to the - * offsetof(Heap_Block.size). - */ -#define HEAP_BLOCK_HEADER_OFFSET (sizeof(uint32_t)) - -/** - * Offset of user data pointer from the block pointer. Equal to the - * offset of(Heap_Block.next). - */ -#define HEAP_BLOCK_USER_OFFSET (sizeof(uint32_t) * 2) - -/** - * This is the number of bytes of overhead in a used block. - * Equal to the sizeof(Heap_Block.previous and next). - */ -#define HEAP_BLOCK_USED_OVERHEAD (sizeof(uint32_t) * 2) - -/** Size of the permanent dummy last block. */ -#define HEAP_OVERHEAD HEAP_BLOCK_USER_OFFSET + * @defgroup ScoreHeap Heap Handler + * + * The Heap Handler provides a heap. + * + * A heap is a doubly linked list of variable size blocks which are allocated + * using the first fit method. Garbage collection is performed each time a + * block is returned to the heap by coalescing neighbor blocks. Control + * information for both allocated and free blocks is contained in the heap + * area. A heap control structure contains control information for the heap. + * + * FIXME: The alignment routines could be made faster should we require only + * powers of two to be supported both for 'page_size' and for 'alignment' + * arguments. However, both workspace and malloc heaps are initialized with + * CPU_HEAP_ALIGNMENT as 'page_size', and while all the BSPs seem to use + * CPU_ALIGNMENT (that is power of two) as CPU_HEAP_ALIGNMENT, for whatever + * reason CPU_HEAP_ALIGNMENT is only required to be multiple of CPU_ALIGNMENT + * and explicitly not required to be a power of two. + * + * There are two kinds of blocks. One sort describes a free block from which + * we can allocate memory. The other blocks are used and contain allocated + * memory. The free blocks are accessible via a list of free blocks. + * + * Free blocks look like: + * + * + * + * + * + * + * + * + * + * + *
@ref Heap_Blockprevious block size in case the + * previous block is free,
otherwise it may contain data used by + * the previous block
block size and a flag which indicates if the previous block is free + * or used,
this field contains always valid data regardless of the + * block usage
pointer to next block (this field is page size aligned)
pointer to previous block
free space
+ * + * Used blocks look like: + * + * + * + * + * + * + * + * + * + * + *
@ref Heap_Blockprevious block size in case the + * previous block is free,
otherwise it may contain data used by + * the previous block
block size and a flag which indicates if the previous block is free + * or used,
this field contains always valid data regardless of the + * block usage
begin of allocated area (this field is page size aligned)
allocated space
allocated space
+ * + * The heap area after initialization contains two blocks and looks like: + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + * + *
LabelContent
heap->beginheap area begin address
first_block->prev_sizearbitrary value
first_block->sizesize available for allocation + * | @c HEAP_PREV_BLOCK_USED
first_block->next_Heap_Free_list_tail(heap)memory area available for allocation
first_block->prev_Heap_Free_list_head(heap)
...
second_block->prev_sizesize of first block
second_block->sizearbitrary size | @c HEAP_PREV_BLOCK_FREE
heap->endheap area end address
+ * + * @{ + */ + +/** + * @brief Description for free or used blocks. + */ +typedef struct Heap_Block { + /** + * @brief Size of the previous block or part of the allocated area of the + * previous block. + * + * This field is only valid if the previous block is free. This case is + * indicated by a cleared @c HEAP_PREV_BLOCK_USED flag in the + * @a size_and_flag field of the current block. + */ + uintptr_t prev_size; + + /** + * @brief Contains the size of the current block and a flag which indicates + * if the previous block is free or used. + * + * If the flag @c HEAP_PREV_BLOCK_USED is set, then the previous block is + * used, otherwise the previous block is free. A used previous block may + * claim the @a prev_size field for allocation. This trick allows to + * decrease the overhead in the used blocks by the size of the + * @a prev_size field. As sizes are always multiples of four, the two least + * significant bits are always zero. We use one of them to store the flag. + * + * This field is always valid. + */ + uintptr_t size_and_flag; + + /** + * @brief Pointer to the next free block or part of the allocated area. + * + * This field is page size aligned and begins of the allocated area in case + * the block is used. + * + * This field is only valid if the block is free and thus part of the free + * block list. + */ + struct Heap_Block *next; + + /** + * @brief Pointer to the previous free block or part of the allocated area. + * + * This field is only valid if the block is free and thus part of the free + * block list. + */ + struct Heap_Block *prev; +} Heap_Block; + +#define HEAP_PREV_BLOCK_USED ((uintptr_t) 1) + +#define HEAP_PREV_BLOCK_FREE ((uintptr_t) 0) + +/** + * @brief Offset from the block begin up to the block size field. + */ +#define HEAP_BLOCK_SIZE_OFFSET (sizeof(uintptr_t)) + +/** + * @brief Offset from the block begin up to the allocated area begin. + */ +#define HEAP_BLOCK_ALLOC_AREA_OFFSET (sizeof(uintptr_t) * 2) + +#define HEAP_BLOCK_USED_OVERHEAD (sizeof(uintptr_t) * 2) + +#define HEAP_LAST_BLOCK_OVERHEAD HEAP_BLOCK_ALLOC_AREA_OFFSET /** * Run-time heap statistics. @@ -145,11 +190,11 @@ typedef struct { /** instance number of this heap */ uint32_t instance; /** the size of the memory for heap */ - intptr_t size; + uintptr_t size; /** current free size */ - intptr_t free_size; + uintptr_t free_size; /** minimum free size ever */ - intptr_t min_free_size; + uintptr_t min_free_size; /** current number of free blocks */ uint32_t free_blocks; /** maximum number of free blocks ever */ @@ -173,15 +218,15 @@ typedef struct { */ typedef struct { /** head and tail of circular list of free blocks */ - Heap_Block free_list; + Heap_Block free_list; /** allocation unit and alignment */ - uint32_t page_size; + uintptr_t page_size; /** minimum block size aligned on page_size */ - uint32_t min_block_size; + uintptr_t min_block_size; /** first address of memory for the heap */ - void *begin; + uintptr_t begin; /** first address past end of memory for the heap */ - void *end; + uintptr_t end; /** first valid block address in the heap */ Heap_Block *start; /** last valid block address in the heap */ @@ -193,7 +238,6 @@ typedef struct { /** * Status codes for _Heap_Extend */ - typedef enum { HEAP_EXTEND_SUCCESSFUL, HEAP_EXTEND_ERROR, @@ -203,7 +247,6 @@ typedef enum { /** * Status codes for _Heap_Resize_block */ - typedef enum { HEAP_RESIZE_SUCCESSFUL, HEAP_RESIZE_UNSATISFIED, @@ -213,7 +256,6 @@ typedef enum { /** * Status codes for _Heap_Get_information */ - typedef enum { HEAP_GET_INFORMATION_SUCCESSFUL = 0, HEAP_GET_INFORMATION_BLOCK_ERROR @@ -244,33 +286,27 @@ typedef struct { } Heap_Information_block; /** - * This routine initializes @a the_heap record to manage the - * contiguous heap of @a size bytes which starts at @a starting_address. - * Blocks of memory are allocated from the heap in multiples of - * @a page_size byte units. If @a page_size is 0 or is not multiple of - * CPU_ALIGNMENT, it's aligned up to the nearest CPU_ALIGNMENT boundary. + * Initializes the @a heap control block to manage the area starting at + * @a area_begin of @a area_size bytes. * - * @param[in] the_heap is the heap to operate upon - * @param[in] starting_address is the starting address of the memory for - * the heap - * @param[in] size is the size in bytes of the memory area for the heap - * @param[in] page_size is the size in bytes of the allocation unit + * Blocks of memory are allocated from the heap in multiples of @a page_size + * byte units. If the @a page_size is equal to zero or is not multiple of + * @c CPU_ALIGNMENT, it is aligned up to the nearest @c CPU_ALIGNMENT boundary. * - * @return This method returns the maximum memory available. If - * unsuccessful, 0 will be returned. + * Returns the maximum memory available, or zero in case of failure. */ -uint32_t _Heap_Initialize( - Heap_Control *the_heap, - void *starting_address, - intptr_t size, - uint32_t page_size +uintptr_t _Heap_Initialize( + Heap_Control *heap, + void *area_begin, + uintptr_t area_size, + uintptr_t page_size ); /** - * This routine grows @a the_heap memory area using the size bytes which + * This routine grows @a heap memory area using the size bytes which * begin at @a starting_address. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] starting_address is the starting address of the memory * to add to the heap * @param[in] size is the size in bytes of the memory area to add @@ -279,71 +315,68 @@ uint32_t _Heap_Initialize( * @return *size filled in with the amount of memory added to the heap */ Heap_Extend_status _Heap_Extend( - Heap_Control *the_heap, - void *starting_address, - intptr_t size, - intptr_t *amount_extended + Heap_Control *heap, + void *area_begin, + uintptr_t area_size, + uintptr_t *amount_extended ); /** * This function attempts to allocate a block of @a size bytes from - * @a the_heap. If insufficient memory is free in @a the_heap to allocate + * @a heap. If insufficient memory is free in @a heap to allocate * a block of the requested size, then NULL is returned. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] size is the amount of memory to allocate in bytes * @return NULL if unsuccessful and a pointer to the block if successful */ -void *_Heap_Allocate( - Heap_Control *the_heap, - intptr_t size -); +void *_Heap_Allocate( Heap_Control *heap, uintptr_t size ); /** * This function attempts to allocate a memory block of @a size bytes from - * @a the_heap so that the start of the user memory is aligned on the + * @a heap so that the start of the user memory is aligned on the * @a alignment boundary. If @a alignment is 0, it is set to CPU_ALIGNMENT. * Any other value of @a alignment is taken "as is", i.e., even odd * alignments are possible. * Returns pointer to the start of the memory block if success, NULL if * failure. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] size is the amount of memory to allocate in bytes * @param[in] alignment the required alignment * @return NULL if unsuccessful and a pointer to the block if successful */ void *_Heap_Allocate_aligned( - Heap_Control *the_heap, - intptr_t size, - uint32_t alignment + Heap_Control *heap, + uintptr_t size, + uintptr_t alignment ); /** - * This function sets @a *size to the size of the block of user memory + * This function sets @a size to the size of the block of allocatable area * which begins at @a starting_address. The size returned in @a *size could * be greater than the size requested for allocation. * Returns true if the @a starting_address is in the heap, and false * otherwise. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] starting_address is the starting address of the user block * to obtain the size of * @param[in] size points to a user area to return the size in * @return true if successfully able to determine the size, false otherwise * @return *size filled in with the size of the user area for this block */ -bool _Heap_Size_of_user_area( - Heap_Control *the_heap, - void *starting_address, - intptr_t *size +bool _Heap_Size_of_alloc_area( + Heap_Control *heap, + void *area_begin, + uintptr_t *size ); /** * This function tries to resize in place the block that is pointed to by the * @a starting_address to the new @a size. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] starting_address is the starting address of the user block * to be resized * @param[in] size is the new size @@ -362,39 +395,36 @@ bool _Heap_Size_of_user_area( * resizing, 0 if none. */ Heap_Resize_status _Heap_Resize_block( - Heap_Control *the_heap, + Heap_Control *heap, void *starting_address, - intptr_t size, - intptr_t *old_mem_size, - intptr_t *avail_mem_size + uintptr_t size, + uintptr_t *old_mem_size, + uintptr_t *avail_mem_size ); /** * This routine returns the block of memory which begins - * at @a starting_address to @a the_heap. Any coalescing which is + * at @a alloc_area_begin to @a heap. Any coalescing which is * possible with the freeing of this routine is performed. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] start_address is the starting address of the user block * to free * @return true if successfully freed, false otherwise */ -bool _Heap_Free( - Heap_Control *the_heap, - void *start_address -); +bool _Heap_Free( Heap_Control *heap, void *alloc_area_begin ); /** * This routine walks the heap to verify its integrity. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] source is a user specified integer which may be used to * indicate where in the application this was invoked from * @param[in] do_dump is set to true if errors should be printed * @return true if the test passed fine, false otherwise. */ bool _Heap_Walk( - Heap_Control *the_heap, + Heap_Control *heap, int source, bool do_dump ); @@ -403,13 +433,13 @@ bool _Heap_Walk( * This routine walks the heap and tots up the free and allocated * sizes. * - * @param[in] the_heap pointer to heap header + * @param[in] heap pointer to heap header * @param[in] the_info pointer to a status information area * @return *the_info is filled with status information * @return 0=success, otherwise heap is corrupt. */ Heap_Get_information_status _Heap_Get_information( - Heap_Control *the_heap, + Heap_Control *heap, Heap_Information_block *the_info ); @@ -417,107 +447,72 @@ Heap_Get_information_status _Heap_Get_information( * This heap routine returns information about the free blocks * in the specified heap. * - * @param[in] the_heap pointer to heap header. + * @param[in] heap pointer to heap header. * @param[in] info pointer to the free block information. * * @return free block information filled in. */ void _Heap_Get_free_information( - Heap_Control *the_heap, + Heap_Control *heap, Heap_Information *info ); #if !defined(__RTEMS_APPLICATION__) -/** - * A pointer to unsigned integer conversion. - */ -#define _H_p2u(_p) ((_H_uptr_t)(_p)) - #include /** - * Convert user requested 'size' of memory block to the block size. - * - * @note This is an internal routine used by _Heap_Allocate() and - * _Heap_Allocate_aligned(). Refer to 'heap.c' for details. + * @brief Returns the minimal block size for a block which may contain an area + * of size @a alloc_size for allocation, or zero in case of an overflow. * - * @param[in] size is the size of the block requested - * @param[in] page_size is the page size of this heap instance - * @param[in] min_size is minimum size block that should be allocated - * from this heap instance - * - * @return This method returns block size on success, 0 if overflow occured. + * Uses the heap values @a page_size and @a min_block_size. */ -size_t _Heap_Calc_block_size( - size_t size, - uint32_t page_size, - uint32_t min_size +uintptr_t _Heap_Calc_block_size( + uintptr_t alloc_size, + uintptr_t page_size, + uintptr_t min_block_size ); /** * This method allocates a block of size @a alloc_size from @a the_block - * belonging to @a the_heap. Split @a the_block if possible, otherwise + * belonging to @a heap. Split @a the_block if possible, otherwise * allocate it entirely. When split, make the lower part used, and leave * the upper part free. * * This is an internal routines used by _Heap_Allocate() and * _Heap_Allocate_aligned(). Refer to 'heap.c' for details. * - * @param[in] the_heap is the heap to operate upon + * @param[in] heap is the heap to operate upon * @param[in] the_block is the block to allocates the requested size from * @param[in] alloc_size is the requested number of bytes to take out of * the block * * @return This methods returns the size of the allocated block. */ -uint32_t _Heap_Block_allocate( - Heap_Control* the_heap, - Heap_Block* the_block, - uint32_t alloc_size +uintptr_t _Heap_Block_allocate( + Heap_Control *heap, + Heap_Block *block, + uintptr_t alloc_size ); -/** - * Align @a *value up to the nearest multiple of @a alignment. - * - * @param[in] value is a pointer to be aligned. - * @param[in] alignment is the alignment value. - * - * @return Upon return, @a value will contain the aligned result. - */ -void _Heap_Align_up_uptr ( - _H_uptr_t *value, - uint32_t alignment -); - -/* - * Debug support - */ +/** @} */ -#if defined(RTEMS_DEBUG) -#define RTEMS_HEAP_DEBUG +#ifdef RTEMS_DEBUG + #define RTEMS_HEAP_DEBUG + #define RTEMS_MALLOC_BOUNDARY_HELPERS #endif -/** - * We do asserts only for heaps with instance number greater than 0 assuming - * that the heap used for malloc is initialized first and thus has instance - * number 0. Asserting malloc heap may lead to troubles as printf may invoke - * malloc thus probably leading to infinite recursion. - */ -#if defined(RTEMS_HEAP_DEBUG) -#include - -#define _HAssert(cond_) \ - do { \ - if (the_heap->stats.instance && !(cond_)) \ - __assert(__FILE__, __LINE__, #cond_); \ - } while(0) - -#else /* !defined(RTEMS_HEAP_DEBUG) */ - -#define _HAssert(cond_) ((void)0) - -#endif /* !defined(RTEMS_HEAP_DEBUG) */ +#ifdef RTEMS_HEAP_DEBUG + #include + #define _HAssert( cond ) \ + do { \ + if ( !(cond) ) { \ + __assert( __FILE__, __LINE__, #cond ); \ + } \ + } while (0) +#else + #define _HAssert( cond ) ((void) 0) +#endif #endif /* !defined(__RTEMS_APPLICATION__) */ @@ -525,7 +520,5 @@ void _Heap_Align_up_uptr ( } #endif -/**@}*/ - #endif /* end of include file */ -- cgit v1.2.3