From: Andreas Dachsberger <andreas.dachsber...@embedded-brains.de> --- cpukit/include/rtems/score/heapimpl.h | 366 ++++++++++++++++++++++++++++------ 1 file changed, 301 insertions(+), 65 deletions(-)
diff --git a/cpukit/include/rtems/score/heapimpl.h b/cpukit/include/rtems/score/heapimpl.h index 12da2defea..cd213ec2d8 100644 --- a/cpukit/include/rtems/score/heapimpl.h +++ b/cpukit/include/rtems/score/heapimpl.h @@ -26,8 +26,9 @@ extern "C" { /** * @addtogroup RTEMSScoreHeap + * + * @{ */ -/**@{**/ /** * @brief See also @ref Heap_Block.size_and_flag. @@ -50,18 +51,19 @@ typedef enum { } Heap_Resize_status; /** - * @brief Gets the first and last block for the heap area with begin - * @a heap_area_begin and size @a heap_area_size. - * - * A page size of @a page_size and minimal block size of @a min_block_size will - * be used for calculation. + * @brief Gets the first and last block for the heap area. * * Nothing will be written to this area. * - * In case of success the pointers to the first and last block will be returned - * via @a first_block_ptr and @a last_block_ptr. + * @param heap_area_begin The starting address of the heap area. + * @param heap_area_size The size of the heap area. + * @param page_size The page size for the calculation. + * @param min_block_size The minimal block size for the calculation. + * @param[out] first_block_ptr The pointer to the first block in the case of success + * @param[out] last_block_ptr The pointer to the last block in the case of success * - * Returns @c true if the area is big enough, and @c false otherwise. + * @retval true The area is big enough. + * @retval false The area is not big enough. */ bool _Heap_Get_first_and_last_block( uintptr_t heap_area_begin, @@ -73,14 +75,19 @@ bool _Heap_Get_first_and_last_block( ); /** - * @brief Initializes the heap control block @a heap to manage the area - * starting at @a area_begin of size @a area_size bytes. + * @brief Initializes the heap control block. * * 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. * - * Returns the maximum memory available, or zero in case of failure. + * @param[out] heap The heap control block to manage the area. + * @param area_begin The starting address of the area. + * @param area_size The size of the area in bytes. + * @param page_size The page size for the calculation + * + * @retval some_value The maximum memory available. + * @retval 0 The initialization failed. * * @see Heap_Initialization_or_extend_handler. */ @@ -92,22 +99,22 @@ uintptr_t _Heap_Initialize( ); /** - * @brief Allocates a memory area of size @a size bytes from the heap @a heap. - * - * If the alignment parameter @a alignment is not equal to zero, the allocated - * memory area will begin at an address aligned by this value. - * - * If the boundary parameter @a boundary is not equal to zero, the allocated - * memory area will fulfill a boundary constraint. The boundary value - * specifies the set of addresses which are aligned by the boundary value. The - * interior of the allocated memory area will not contain an element of this - * set. The begin or end address of the area may be a member of the set. + * @brief Allocates an aligned memory area with boundary constraint. * * A size value of zero will return a unique address which may be freed with * _Heap_Free(). * - * Returns a pointer to the begin of the allocated memory area, or @c NULL if - * no memory is available or the parameters are inconsistent. + * @param[in, out] heap The heap to allocate a memory are from. + * @param size The size of the desired memory are in bytes. + * @param alignment The allocated memory area will begin at an address aligned by this value. + * @param boundary The allocated memory area will fulfill a boundary constraint, + * if this value is not equal to zero. The boundary value specifies + * the set of addresses which are aligned by the boundary value. The + * interior of the allocated memory area will not contain an element of this + * set. The begin or end address of the area may be a member of the set. + * + * @retval pointer The starting address of the allocated memory area. + * @retval NULL No memory is available of the parameters are inconsistent. */ void *_Heap_Allocate_aligned_with_boundary( Heap_Control *heap, @@ -117,7 +124,17 @@ void *_Heap_Allocate_aligned_with_boundary( ); /** - * @brief See _Heap_Allocate_aligned_with_boundary() with boundary equals zero. + * @brief Allocates an aligned memory area. + * + * A size value of zero will return a unique address which may be freed with + * _Heap_Free(). + * + * @param[in, out] heap The heap to allocate a memory are from. + * @param size The size of the desired memory are in bytes. + * @param alignment The allocated memory area will begin at an address aligned by this value. + * + * @retval pointer The starting address of the allocated memory area. + * @retval NULL No memory is available of the parameters are inconsistent. */ RTEMS_INLINE_ROUTINE void *_Heap_Allocate_aligned( Heap_Control *heap, @@ -129,8 +146,16 @@ RTEMS_INLINE_ROUTINE void *_Heap_Allocate_aligned( } /** - * @brief See _Heap_Allocate_aligned_with_boundary() with alignment and - * boundary equals zero. + * @brief Allocates a memory area. + * + * A size value of zero will return a unique address which may be freed with + * _Heap_Free(). + * + * @param[in, out] heap The heap to allocate a memory are from. + * @param size The size of the desired memory are in bytes. + * + * @retval pointer The starting address of the allocated memory area. + * @retval NULL No memory is available of the parameters are inconsistent. */ RTEMS_INLINE_ROUTINE void *_Heap_Allocate( Heap_Control *heap, uintptr_t size ) { @@ -138,22 +163,29 @@ RTEMS_INLINE_ROUTINE void *_Heap_Allocate( Heap_Control *heap, uintptr_t size ) } /** - * @brief Frees the allocated memory area starting at @a addr in the heap - * @a heap. + * @brief Frees the allocated memory area. * * Inappropriate values for @a addr may corrupt the heap. * - * Returns @c true in case of success, and @c false otherwise. + * @param[in, out] heap The heap of the allocated memory area. + * @param addr The starting address of the memory area to be freed. + * + * @retval true The allocated memory area was successfully freed. + * @retval false The method failed. */ bool _Heap_Free( Heap_Control *heap, void *addr ); /** - * @brief Walks the heap @a heap to verify its integrity. + * @brief Verifies the integrity of the heap. * - * If @a dump is @c true, then diagnostic messages will be printed to standard - * output. In this case @a source is used to mark the output lines. + * Walks the heap to verify its integrity. * - * Returns @c true if no errors occurred, and @c false if the heap is corrupt. + * @param heap The heap whose integrity is to be verified. + * @param source If @a dump is @c true, this is used to mark the output lines. + * @param dump Indicates whether diagnostic messages will be printed to standard output. + * + * @retval true No errors occured, the heap“s integrity is not violated. + * @retval false The heap is corrupt. */ bool _Heap_Walk( Heap_Control *heap, @@ -179,8 +211,10 @@ typedef bool (*Heap_Block_visitor)( /** * @brief Iterates over all blocks of the heap. * - * For each block the @a visitor with the argument @a visitor_arg will be - * called. + * @param[in, out] heap The heap to iterate over. + * @param visitor This will be called for each heap block with + * the argument @a visitor_arg. + * @param[in, out] visitor_arg The argument for all calls of @a visitor. */ void _Heap_Iterate( Heap_Control *heap, @@ -189,11 +223,18 @@ void _Heap_Iterate( ); /** - * @brief Greedy allocate that empties the heap. + * @brief Greedily allocates and empties the heap. + * + * Afterwards, the heap has at most @a block_count allocatable blocks of sizes + * specified by @a block_sizes. All other blocks are used. * - * Afterwards the heap has at most @a block_count allocatable blocks of sizes - * specified by @a block_sizes. The @a block_sizes must point to an array with - * @a block_count members. All other blocks are used. + * @param[in, out] heap The heap to operate upon + * @param block_sizes The sizes of the allocatable blocks. Must point to an + * array with @a block_count members. + * @param block_count The maximum number of allocatable blocks of sizes + * specified by @block_sizes. + * + * @return Pointer to the first allocated block. * * @see _Heap_Greedy_free(). */ @@ -204,11 +245,16 @@ Heap_Block *_Heap_Greedy_allocate( ); /** - * @brief Greedy allocate all blocks except the largest free block. + * @brief Greedily allocates all blocks except the largest free block. * * Afterwards the heap has at most one allocatable block. This block is the - * largest free block if it exists. The allocatable size of this block is - * stored in @a allocatable_size. All other blocks are used. + * largest free block if it exists. All other blocks are used. + * + * @param[in, out] heap The heap to operate upon. + * @param[out] allocatable_size Stores the size of the largest free block of + * the heap after the method call. + * + * @return Pointer to the first allocated block. * * @see _Heap_Greedy_free(). */ @@ -220,7 +266,8 @@ Heap_Block *_Heap_Greedy_allocate_all_except_largest( /** * @brief Frees blocks of a greedy allocation. * - * The @a blocks must be the return value of _Heap_Greedy_allocate(). + * @param[in, out] heap The heap to operate upon. + * @param blocks Must be the return value of _Heap_Greedy_allocate(). */ void _Heap_Greedy_free( Heap_Control *heap, @@ -228,8 +275,10 @@ void _Heap_Greedy_free( ); /** - * @brief Returns information about used and free blocks for the heap @a heap - * in @a info. + * @brief Returns information about used and free blocks for the heap. + * + * @param heap The heap to get the information from. + * @param[out] info Stores the information of the @a heap after the method call. */ void _Heap_Get_information( Heap_Control *heap, @@ -237,8 +286,11 @@ void _Heap_Get_information( ); /** - * @brief Returns information about free blocks for the heap @a heap in - * @a info. + * @brief Returns information about free blocks for the heap. + * + * @param heap The heap to get the information from. + * @param[out] info Stores the information about free blocks of @a heap after the + * method call. */ void _Heap_Get_free_information( Heap_Control *heap, @@ -246,8 +298,7 @@ void _Heap_Get_free_information( ); /** - * @brief Returns the size of the allocatable memory area starting at @a addr - * in @a size. + * @brief Returns the size of the allocatable memory area. * * The size value may be greater than the initially requested size in * _Heap_Allocate_aligned_with_boundary(). @@ -255,7 +306,12 @@ void _Heap_Get_free_information( * Inappropriate values for @a addr will not corrupt the heap, but may yield * invalid size values. * - * Returns @a true if successful, and @c false otherwise. + * @param heap The heap to operate upon. + * @param addr The starting address of the allocatable memory area. + * @param[out] size Stores the size of the allocatable memory area after the method call. + * + * @retval true The operation was successful. + * @retval false The operation was not successful. */ bool _Heap_Size_of_alloc_area( Heap_Control *heap, @@ -264,17 +320,25 @@ bool _Heap_Size_of_alloc_area( ); /** - * @brief Resizes the block of the allocated memory area starting at @a addr. - * - * The new memory area will have a size of at least @a size bytes. A resize - * may be impossible and depends on the current heap usage. - * - * The size available for allocation in the current block before the resize - * will be returned in @a old_size. The size available for allocation in - * the resized block will be returned in @a new_size. If the resize was not - * successful, then a value of zero will be returned in @a new_size. + * @brief Resizes the block of the allocated memory area. * * Inappropriate values for @a addr may corrupt the heap. + * + * @param[in, out] heap The heap to operate upon. + * @param addr The starting address of the allocated memory area to be resized. + * @param size The least possible size for the new memory area. Resize may be + * impossible and depends on the current heap usage. + * @param[out] old_size Stores the size available for allocation in the current + * block before the resize after the method call. + * @param[out] new_size Stores the size available for allocation in the resized + * block after the method call. In the case of an unsuccessful resize, + * zero is returned in this parameter + * + * @retval HEAP_RESIZE_SUCCESSFUL The resize was successful. + * @retval HEAP_RESIZE_UNSATISFIED The least possible size @a size was too big. + * Resize not possible. + * @retval HEAP_RESIZE_FATAL_ERROR The block starting at @a addr is not part of + * the heap. */ Heap_Resize_status _Heap_Resize_block( Heap_Control *heap, @@ -285,7 +349,8 @@ Heap_Resize_status _Heap_Resize_block( ); /** - * @brief Allocates the memory area starting at @a alloc_begin of size + * @brief Allocates the memory area. + * starting at @a alloc_begin of size * @a alloc_size bytes in the block @a block. * * The block may be split up into multiple blocks. The previous and next block @@ -297,7 +362,12 @@ Heap_Resize_status _Heap_Resize_block( * Inappropriate values for @a alloc_begin or @a alloc_size may corrupt the * heap. * - * Returns the block containing the allocated memory area. + * @param[in, out] heap The heap to operate upon. + * @param block The block in which the memory area should be allocated + * @param alloc_begin The starting address of the memory area that shall be allocated. + * @param alloc_size The size of the desired allocated area in bytes. + * + * @return The block containing the allocated memory area. */ Heap_Block *_Heap_Block_allocate( Heap_Control *heap, @@ -354,8 +424,8 @@ Heap_Block *_Heap_Block_allocate( * The default is to free half the delayed free blocks. This is equal to a * fraction value of two. * - * @param[in] heap The heap control. - * @param[in] fraction The fraction is one divided by this fraction value. + * @param[in, out] heap The heap control. + * @param fraction The fraction is one divided by this fraction value. */ RTEMS_INLINE_ROUTINE void _Heap_Protection_set_delayed_free_fraction( Heap_Control *heap, @@ -370,26 +440,59 @@ RTEMS_INLINE_ROUTINE void _Heap_Protection_set_delayed_free_fraction( #endif } +/** + * @brief Returns the head of the free list of the heap. + * + * @param heap The heap to operate upon. + * + * @return The head of the free list. + */ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_head( Heap_Control *heap ) { return &heap->free_list; } +/** + * @brief Returns the tail of the free list of the heap. + * + * @param heap The heap to operate upon. + * + * @return The tail of the free list. + */ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_tail( Heap_Control *heap ) { return &heap->free_list; } +/** + * @brief Returns the first block of the free list of the heap. + * + * @param heap The heap to operate upon. + * + * @return The first block of the free list. + */ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_first( Heap_Control *heap ) { return _Heap_Free_list_head(heap)->next; } +/** + * @brief Returns the last block of the free list of the heap. + * + * @param heap The heap to operate upon. + * + * @return The last block of the free list. + */ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_last( Heap_Control *heap ) { return _Heap_Free_list_tail(heap)->prev; } +/** + * @brief Removes the block from the free list. + * + * @param block The block to be removed. + */ RTEMS_INLINE_ROUTINE void _Heap_Free_list_remove( Heap_Block *block ) { Heap_Block *next = block->next; @@ -399,6 +502,12 @@ RTEMS_INLINE_ROUTINE void _Heap_Free_list_remove( Heap_Block *block ) next->prev = prev; } +/** + * @brief Replaces one block in the free list by another. + * + * @param old_block The block in the free list to replace. + * @param new_block The block that should replace @a old_block. + */ RTEMS_INLINE_ROUTINE void _Heap_Free_list_replace( Heap_Block *old_block, Heap_Block *new_block @@ -414,6 +523,12 @@ RTEMS_INLINE_ROUTINE void _Heap_Free_list_replace( prev->next = new_block; } +/** + * @brief Inserts a block after an existing block in the free list. + * + * @param block_before The block that is already in the free list. + * @param new_block The block to be inserted after @a block_before. + */ RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_after( Heap_Block *block_before, Heap_Block *new_block @@ -427,6 +542,12 @@ RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_after( next->prev = new_block; } +/** + * @brief Inserts a block before an existing block in the free list. + * + * @param block_before The block that is already in the free list. + * @param new_block The block to be inserted before @a block_before. + */ RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_before( Heap_Block *block_next, Heap_Block *new_block @@ -440,6 +561,15 @@ RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_before( block_next->prev = new_block; } +/** + * @brief Checks if the value is aligned to the given alignment. + * + * @param value The value to check the alignment of. + * @param alignment The alignment for the operation. + * + * @retval true The value is aligned to the given alignment. + * @retval false The value is not aligned to the given alignment. + */ RTEMS_INLINE_ROUTINE bool _Heap_Is_aligned( uintptr_t value, uintptr_t alignment @@ -448,6 +578,14 @@ RTEMS_INLINE_ROUTINE bool _Heap_Is_aligned( return (value % alignment) == 0; } +/** + * @brief Returns the aligned value, truncating. + * + * @param value The value to be aligned + * @param alignment The alignment for the operation. + * + * @return The aligned value, truncated. + */ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Align_down( uintptr_t value, uintptr_t alignment @@ -458,6 +596,11 @@ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Align_down( /** * @brief Returns the block which is @a offset away from @a block. + * + * @param block The block for the relative calculation. + * @param offset The offset for the calculation. + * + * @return The address of the block which is @a offset away from @a block. */ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Block_at( const Heap_Block *block, @@ -467,6 +610,13 @@ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Block_at( return (Heap_Block *) ((uintptr_t) block + offset); } +/** + * @brief Returns the address of the previous block. + * + * @param block The block of which the address of the previous block is requested. + * + * @return The address of the previous block. + */ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Prev_block( const Heap_Block *block ) @@ -474,6 +624,13 @@ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Prev_block( return (Heap_Block *) ((uintptr_t) block - block->prev_size); } +/** + * @brief Returns the first address in the block without the heap header. + * + * @param block The block for the operation. + * + * @return The first address after the heap header. + */ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Alloc_area_of_block( const Heap_Block *block ) @@ -481,6 +638,14 @@ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Alloc_area_of_block( return (uintptr_t) block + HEAP_BLOCK_HEADER_SIZE; } +/** + * @brief Returns the starting address of the block corresponding to the allocatable area. + * + * @param alloc_begin The starting address of the allocatable area. + * @param page_size The page size for the calculation. + * + * @return The Starting address of the corresponding block of the allocatable area. + */ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Block_of_alloc_area( uintptr_t alloc_begin, uintptr_t page_size @@ -490,11 +655,24 @@ RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Block_of_alloc_area( - HEAP_BLOCK_HEADER_SIZE); } +/** + * @brief Returns the block size. + * + * @param block The block of which the size is requested. + * + * @return The block size. + */ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Block_size( const Heap_Block *block ) { return block->size_and_flag & ~HEAP_PREV_BLOCK_USED; } +/** + * @brief Sets the block size. + * + * @param[in, out] block The block of which the size shall be set. + * @param size The new size of the block. + */ RTEMS_INLINE_ROUTINE void _Heap_Block_set_size( Heap_Block *block, uintptr_t size @@ -505,11 +683,28 @@ RTEMS_INLINE_ROUTINE void _Heap_Block_set_size( block->size_and_flag = size | flag; } +/** + * @brief Returns if the previous heap block is used. + * + * @param block The block of which the information about the previous + * block is requested. + * + * @retval true The previous block is used. + * @retval false The previous block is not used. + */ RTEMS_INLINE_ROUTINE bool _Heap_Is_prev_used( const Heap_Block *block ) { return block->size_and_flag & HEAP_PREV_BLOCK_USED; } +/** + * @brief Returns if the heap block is used. + * + * @param block The block of which the information is requested. + * + * @retval true The block is used. + * @retval false The block is not used. + */ RTEMS_INLINE_ROUTINE bool _Heap_Is_used( const Heap_Block *block ) @@ -520,6 +715,14 @@ RTEMS_INLINE_ROUTINE bool _Heap_Is_used( return _Heap_Is_prev_used( next_block ); } +/** + * @brief Returns if the heap block is free. + * + * @param block The block of which the information is requested. + * + * @retval true The block is free. + * @retval false The block is not free. + */ RTEMS_INLINE_ROUTINE bool _Heap_Is_free( const Heap_Block *block ) @@ -527,6 +730,15 @@ RTEMS_INLINE_ROUTINE bool _Heap_Is_free( return !_Heap_Is_used( block ); } +/** + * @brief Returns if the block is part of the heap. + * + * @param heap The heap to test if the @a block is part of it. + * @param block The block of which the information is requested. + * + * @retval true The block is part of the heap. + * @retval false The block is not part of the heap. + */ RTEMS_INLINE_ROUTINE bool _Heap_Is_block_in_heap( const Heap_Control *heap, const Heap_Block *block @@ -537,7 +749,7 @@ RTEMS_INLINE_ROUTINE bool _Heap_Is_block_in_heap( } /** - * @brief Sets the size of the last block for heap @a heap. + * @brief Sets the size of the last block for the heap. * * The next block of the last block will be the first block. Since the first * block indicates that the previous block is used, this ensures that the last @@ -546,6 +758,8 @@ RTEMS_INLINE_ROUTINE bool _Heap_Is_block_in_heap( * * This feature will be used to terminate the scattered heap area list. See * also _Heap_Extend(). + * + * @param[in, out] heap The heap to set the last block size of. */ RTEMS_INLINE_ROUTINE void _Heap_Set_last_block_size( Heap_Control *heap ) { @@ -559,17 +773,39 @@ RTEMS_INLINE_ROUTINE void _Heap_Set_last_block_size( Heap_Control *heap ) * @brief Returns the size of the allocatable area in bytes. * * This value is an integral multiple of the page size. + * + * @param heap The heap to get the allocatable area from. + * + * @return The size of the allocatable area in @a heap in bytes. */ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Get_size( const Heap_Control *heap ) { return heap->stats.size; } +/** + * @brief Returns the bigger one of the two arguments. + * + * @param a The parameter on the left hand side of the comparison. + * @param b The parameter on the right hand side of the comparison. + * + * @retval a If a > b. + * @retval b If b >= a + */ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Max( uintptr_t a, uintptr_t b ) { return a > b ? a : b; } +/** + * @brief Returns the smaller one of the two arguments. + * + * @param a The parameter on the left hand side of the comparison. + * @param b The parameter on the right hand side of the comparison. + * + * @retval a If a < b. + * @retval b If b <= a + */ RTEMS_INLINE_ROUTINE uintptr_t _Heap_Min( uintptr_t a, uintptr_t b ) { return a < b ? a : b; -- 2.16.4 _______________________________________________ devel mailing list devel@rtems.org http://lists.rtems.org/mailman/listinfo/devel