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/include/rtems/score/heap.h | 386 +++++++++++++++++++++----------- 1 file changed, 259 insertions(+), 127 deletions(-) (limited to 'cpukit/score/include') diff --git a/cpukit/score/include/rtems/score/heap.h b/cpukit/score/include/rtems/score/heap.h index c68bfd0fd1..7559cd89fb 100644 --- a/cpukit/score/include/rtems/score/heap.h +++ b/cpukit/score/include/rtems/score/heap.h @@ -1,4 +1,4 @@ -/** +/** * @file rtems/score/heap.h * * This include file contains the information pertaining to the Heap @@ -6,11 +6,18 @@ * 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 header - * contains control information for the heap. - */ - -/* + * 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. + * * COPYRIGHT (c) 1989-2004. * On-Line Applications Research Corporation (OAR). * @@ -37,152 +44,200 @@ extern "C" { #endif /** - * Status codes for heap_extend + * 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 enum { - HEAP_EXTEND_SUCCESSFUL, - HEAP_EXTEND_ERROR, - HEAP_EXTEND_NOT_IMPLEMENTED -} Heap_Extend_status; + +typedef unsigned long int _H_uptr_t; /** - * Status codes for _Heap_Get_information + * Forward reference + * + * @ref Heap_Block */ -typedef enum { - HEAP_GET_INFORMATION_SUCCESSFUL = 0, - HEAP_GET_INFORMATION_SYSTEM_STATE_ERROR, - HEAP_GET_INFORMATION_BLOCK_ERROR -} Heap_Get_information_status; +typedef struct Heap_Block_struct Heap_Block; /** - * Information block returned by the Heap routines used to - * obtain statistics. This information is returned about - * either free or used blocks. + * 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). + * */ -typedef struct { - /** Number of blocks of this type. */ - uint32_t number; - /** Largest blocks of this type. */ - uint32_t largest; - /** Total size of the blocks of this type. */ - uint32_t total; +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; +}; -} Heap_Information; +/** + * 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 1 /* indicates previous block is in use */ /** - * Information block returned by _Heap_Get_information + * The following constants reflect various requirements of the + * heap data structures which impact the management of a heap. */ -typedef struct { - /** This field is information on the used blocks in the heap. */ - Heap_Information Free; - /** This field is information on the used blocks in the heap. */ - Heap_Information Used; -} Heap_Information_block; + +#define HEAP_MIN_BLOCK_SIZE (sizeof(Heap_Block)) /** - * This constant is used in the size/used field of each heap block to - * indicate when a block is in use. + * Offset of the block header from the block pointer. Equal to the + * offsetof(Heap_Block.size). */ -#define HEAP_BLOCK_USED 1 +#define HEAP_BLOCK_HEADER_OFFSET (sizeof(uint32_t)) /** - * This constant is used in the size/used field of each heap block to - * indicate when a block is free. + * Offset of user data pointer from the block pointer. Equal to the + * offsetof(Heap_Block.next). */ -#define HEAP_BLOCK_FREE 0 +#define HEAP_BLOCK_USER_OFFSET (sizeof(uint32_t) * 2) /** - * The size/used field value for the dummy front and back flags. + * Num bytes of overhead in used block. Equal to the sizeof(Heap_Block.size). */ -#define HEAP_DUMMY_FLAG (0 + HEAP_BLOCK_USED) +#define HEAP_BLOCK_USED_OVERHEAD \ + (HEAP_BLOCK_USER_OFFSET - HEAP_BLOCK_HEADER_OFFSET) -/* - * The following constants reflect various requirements of the - * heap data structures which impact the management of a heap. +/** Size of the permanent dummy last block. */ +#define HEAP_OVERHEAD HEAP_BLOCK_USER_OFFSET + +/** + * Run-time heap statistics. + * + * @note (double)searches/allocs gives mean number of searches per alloc while + * max_search gives maximum number of searches ever performed on a + * single call to alloc. * - * NOTE: Because free block overhead is greater than used block - * overhead AND a portion of the allocated space is from - * the extra free block overhead, the absolute lower bound - * of the minimum fragment size is equal to the size of - * the free block overhead. + * @note the statistics is always gathered. I believe the imposed overhead is + * rather small. Feel free to make it compile-time option if you think + * the overhead is too high for your application. */ -/** size dummy first and last blocks */ -#define HEAP_OVERHEAD (sizeof( uint32_t ) * 2) - -/** number of bytes of overhead in used block */ -#define HEAP_BLOCK_USED_OVERHEAD (sizeof( void * ) * 2) +typedef struct Heap_Statistics_tag { + /** instance number of this heap */ + uint32_t instance; + /** the size of the memory for heap */ + uint32_t size; + /** current free size */ + uint32_t free_size; + /** minimum free size ever */ + uint32_t min_free_size; + /** current number of free blocks */ + uint32_t free_blocks; + /** maximum number of free blocks ever */ + uint32_t max_free_blocks; + /** current number of used blocks */ + uint32_t used_blocks; + /** maximum number of blocks searched ever */ + uint32_t max_search; + /** total number of successful calls to alloc */ + uint32_t allocs; + /** total number of searches ever */ + uint32_t searches; + /** total number of suceessful calls to free */ + uint32_t frees; +} Heap_Statistics; -/** Minimum number of bytes the user may specify for the heap size */ -#define HEAP_MINIMUM_SIZE (HEAP_OVERHEAD + sizeof (Heap_Block)) +/** + * Control block used to manage each heap. + */ +typedef struct { + /** head and tail of circular list of free blocks */ + Heap_Block free_list; + /** allocation unit and alignment */ + uint32_t page_size; + /** minimum block size aligned on page_size */ + uint32_t min_block_size; + /** first address of memory for the heap */ + void *begin; + /** first address past end of memory for the heap */ + void *end; + /** first valid block address in the heap */ + Heap_Block *start; + /** last valid block address in the heap */ + Heap_Block *final; + /** run-time statistics */ + Heap_Statistics stats; +} Heap_Control; /** - * Forward reference - * - * @ref Heap_Block + * Status codes for heap_extend */ -typedef struct Heap_Block_struct Heap_Block; + +typedef enum { + HEAP_EXTEND_SUCCESSFUL, + HEAP_EXTEND_ERROR, + HEAP_EXTEND_NOT_IMPLEMENTED +} Heap_Extend_status; /** - * The following defines the data structure used to manage - * individual blocks in a heap. When the block is allocated, the - * next and previous fields are not used by the Heap Handler - * and thus the address returned for the block starts at - * the address of the next field. - * - * @note The next and previous pointers are only valid when the - * block is free. Caution must be exercised to insure that - * allocated blocks are large enough to contain them and - * that they are not accidentally overwritten when the - * block is actually allocated. + * Status codes for _Heap_Get_information */ -struct Heap_Block_struct { - /** size and status of prev block */ - uint32_t back_flag; - /** size and status of block */ - uint32_t front_flag; - /** pointer to next block */ - Heap_Block *next; - /** pointer to previous block */ - Heap_Block *previous; -}; + +typedef enum { + HEAP_GET_INFORMATION_SUCCESSFUL = 0, + HEAP_GET_INFORMATION_BLOCK_ERROR +} Heap_Get_information_status; /** - * The following defines the control block used to manage each heap. - * - * @note This structure is layed out such that it can be used a a dummy - * first and last block on the free block chain. The extra padding - * insures the dummy last block is the correct size. - * - * The first Heap_Block starts at first while the second starts at - * final. This is effectively the same trick as is used in the Chain - * Handler. + * Information block returned by the Heap routines used to + * obtain heap information. This information is returned about + * either free or used blocks. */ typedef struct { - /** first valid block address in heap */ - Heap_Block *start; - /** last valid block address in heap */ - Heap_Block *final; + /** Number of blocks of this type. */ + uint32_t number; + /** Largest blocks of this type. */ + uint32_t largest; + /** Total size of the blocks of this type. */ + uint32_t total; +} Heap_Information; - /** pointer to first block in heap */ - Heap_Block *first; - /** always NULL pointer */ - Heap_Block *permanent_null; - /** pointer to last block in heap */ - Heap_Block *last; - /** allocation unit */ - uint32_t page_size; - /** reserved field */ - uint32_t reserved; -} Heap_Control; +/** + * Information block returned by _Heap_Get_information + */ +typedef struct { + /** This field is information on the used blocks in the heap. */ + Heap_Information Free; + /** This field is information on the used blocks in the heap. */ + Heap_Information Used; +} 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. + * @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. * * @param the_heap (in) is the heap to operate upon * @param starting_address (in) is the starting address of the memory for @@ -206,7 +261,7 @@ uint32_t _Heap_Initialize( * @param starting_address (in) is the starting address of the memory * to add to the heap * @param size (in) is the size in bytes of the memory area to add - * @param amount_extended (in) points to a user area to return the + * @param amount_extended (in) points to a user area to return the * @return a status indicating success or the reason for failure * @return *size filled in with the amount of memory added to the heap */ @@ -218,9 +273,9 @@ Heap_Extend_status _Heap_Extend( ); /** - * This function attempts to allocate a block of size bytes from + * 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 block of the requested size, then NULL is returned. + * a block of the requested size, then NULL is returned. * * @param the_heap (in) is the heap to operate upon * @param size (in) is the amount of memory to allocate in bytes @@ -228,16 +283,38 @@ Heap_Extend_status _Heap_Extend( */ void *_Heap_Allocate( Heap_Control *the_heap, - uint32_t size + uint32_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 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 the_heap (in) is the heap to operate upon + * @param size (in) is the amount of memory to allocate in bytes + * @param alignment (in) the required alignment + * @return NULL if unsuccessful and a pointer to the block if successful + */ +void *_Heap_Allocate_aligned( + Heap_Control *the_heap, + uint32_t size, + uint32_t alignment ); /** - * This kernel routine sets size to the size of the given heap block. - * It returns TRUE if the @a starting_address is in @a the_heap, and FALSE + * This function sets @a *size to the size of the block of user memory + * 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 the_heap (in) is the heap to operate upon - * @param starting_address (in) is the starting address of the user block + * @param starting_address (in) is the starting address of the user block * to obtain the size of * @param size (in) points to a user area to return the size in * @return TRUE if successfully able to determine the size, FALSE otherwise @@ -246,7 +323,7 @@ void *_Heap_Allocate( boolean _Heap_Size_of_user_area( Heap_Control *the_heap, void *starting_address, - uint32_t *size + size_t *size ); /** @@ -255,7 +332,7 @@ boolean _Heap_Size_of_user_area( * possible with the freeing of this routine is performed. * * @param the_heap (in) is the heap to operate upon - * @param starting_address (in) is the starting address of the user block + * @param starting_address (in) is the starting address of the user block * to free * @return TRUE if successfully freed, FALSE otherwise */ @@ -266,20 +343,22 @@ boolean _Heap_Free( /** * This routine walks the heap to verify its integrity. - * + * * @param the_heap (in) is the heap to operate upon * @param source (in) XXX * @param do_dump (in) is set to TRUE if errors should be printed + * @return TRUE if the test passed fine, FALSE otherwise. */ -void _Heap_Walk( + +boolean _Heap_Walk( Heap_Control *the_heap, int source, boolean do_dump ); /** - * This kernel routine walks the heap and tots up the free and allocated - * sizes. Derived from _Heap_Walk. + * This routine walks the heap and tots up the free and allocated + * sizes. * * @param the_heap (in) pointer to heap header * @param the_info (in) pointer to a status information area @@ -294,22 +373,75 @@ Heap_Get_information_status _Heap_Get_information( /** * This heap routine returns information about the free blocks * in the specified heap. - * + * * @param the_heap (in) pointer to heap header. * @param info (in) pointer to the free block information. - * + * * @return free block information filled in. - */ - + */ + void _Heap_Get_free_information( Heap_Control *the_heap, Heap_Information *info ); -#ifndef __RTEMS_APPLICATION__ +#if !defined(__RTEMS_APPLICATION__) + +/* + * A pointer to unsigned integer conversion. + */ +#define _H_p2u(_p) ((_H_uptr_t)(_p)) + #include + +/* + * Internal routines shared by _Heap_Allocate() and _Heap_Allocate_aligned(). + * Refer to 'heap.c' for details. + */ + +extern uint32_t _Heap_Calc_block_size( + uint32_t size, + uint32_t page_size, + uint32_t min_size); + +extern Heap_Block* _Heap_Block_allocate( + Heap_Control* the_heap, + Heap_Block* the_block, + uint32_t alloc_size); + +/* + * Debug support + */ + +#if defined(RTEMS_DEBUG) +#define RTEMS_HEAP_DEBUG #endif +#if defined(RTEMS_HEAP_DEBUG) + +#include + +/* + * 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. + */ + +#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) */ + +#endif /* !defined(__RTEMS_APPLICATION__) */ + #ifdef __cplusplus } #endif -- cgit v1.2.3