From e6f7f81766efeb713b3e0a6fa67122f3f1cf9895 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Tue, 23 Jul 2013 16:50:51 +0200 Subject: score: Create heap implementation header Move implementation specific parts of heap.h and heap.inl into new header file heapimpl.h. The heap.h contains now only the application visible API. --- cpukit/score/include/rtems/score/heap.h | 375 +------------------------------- 1 file changed, 3 insertions(+), 372 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 bea9f3ec25..5a6b3a1a00 100644 --- a/cpukit/score/include/rtems/score/heap.h +++ b/cpukit/score/include/rtems/score/heap.h @@ -18,8 +18,7 @@ #ifndef _RTEMS_SCORE_HEAP_H #define _RTEMS_SCORE_HEAP_H -#include -#include +#include #ifdef __cplusplus extern "C" { @@ -136,6 +135,8 @@ typedef struct Heap_Block Heap_Block; #ifndef HEAP_PROTECTION #define HEAP_PROTECTION_HEADER_SIZE 0 #else + #include + #define HEAP_PROTECTOR_COUNT 2 #define HEAP_BEGIN_PROTECTOR_0 ((uintptr_t) 0xfd75a98f) @@ -177,17 +178,6 @@ typedef struct Heap_Block Heap_Block; (sizeof(Heap_Protection_block_begin) + sizeof(Heap_Protection_block_end)) #endif -/** - * @brief See also @ref Heap_Block.size_and_flag. - */ -#define HEAP_PREV_BLOCK_USED ((uintptr_t) 1) - -/** - * @brief Size of the part at the block begin which may be used for allocation - * in charge of the previous block. - */ -#define HEAP_ALLOC_BONUS sizeof(uintptr_t) - /** * @brief The block header consists of the two size fields * (@ref Heap_Block.prev_size and @ref Heap_Block.size_and_flag). @@ -377,15 +367,6 @@ typedef struct { Heap_Information Used; } Heap_Information_block; -/** - * @brief See _Heap_Resize_block(). - */ -typedef enum { - HEAP_RESIZE_SUCCESSFUL, - HEAP_RESIZE_UNSATISFIED, - HEAP_RESIZE_FATAL_ERROR -} Heap_Resize_status; - /** * @brief Heap area structure for table based heap initialization and * extension. @@ -413,48 +394,6 @@ typedef uintptr_t (*Heap_Initialization_or_extend_handler)( uintptr_t page_size_or_unused ); -/** - * @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. - * - * 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. - * - * Returns @c true if the area is big enough, and @c false otherwise. - */ -bool _Heap_Get_first_and_last_block( - uintptr_t heap_area_begin, - uintptr_t heap_area_size, - uintptr_t page_size, - uintptr_t min_block_size, - Heap_Block **first_block_ptr, - Heap_Block **last_block_ptr -); - -/** - * @brief Initializes the heap control block @a heap to manage the area - * starting at @a area_begin of size @a area_size bytes. - * - * 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. - * - * @see Heap_Initialization_or_extend_handler. - */ -uintptr_t _Heap_Initialize( - Heap_Control *heap, - void *area_begin, - uintptr_t area_size, - uintptr_t page_size -); - /** * @brief Extends the memory available for the heap @a heap using the memory * area starting at @a area_begin of size @a area_size bytes. @@ -495,316 +434,8 @@ uintptr_t _Heap_No_extend( uintptr_t unused_3 ); -/** - * @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. - * - * 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. - */ -void *_Heap_Allocate_aligned_with_boundary( - Heap_Control *heap, - uintptr_t size, - uintptr_t alignment, - uintptr_t boundary -); - -/** - * @brief See _Heap_Allocate_aligned_with_boundary() with boundary equals zero. - */ -RTEMS_INLINE_ROUTINE void *_Heap_Allocate_aligned( - Heap_Control *heap, - uintptr_t size, - uintptr_t alignment -) -{ - return _Heap_Allocate_aligned_with_boundary( heap, size, alignment, 0 ); -} - -/** - * @brief See _Heap_Allocate_aligned_with_boundary() with alignment and - * boundary equals zero. - */ -RTEMS_INLINE_ROUTINE void *_Heap_Allocate( Heap_Control *heap, uintptr_t size ) -{ - return _Heap_Allocate_aligned_with_boundary( heap, size, 0, 0 ); -} - -/** - * @brief Frees the allocated memory area starting at @a addr in the heap - * @a heap. - * - * Inappropriate values for @a addr may corrupt the heap. - * - * Returns @c true in case of success, and @c false otherwise. - */ -bool _Heap_Free( Heap_Control *heap, void *addr ); - -/** - * @brief Walks the heap @a heap to verify its integrity. - * - * 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. - * - * Returns @c true if no errors occurred, and @c false if the heap is corrupt. - */ -bool _Heap_Walk( - Heap_Control *heap, - int source, - bool dump -); - -/** - * @brief Heap block visitor. - * - * @see _Heap_Iterate(). - * - * @retval true Stop the iteration. - * @retval false Continue the iteration. - */ -typedef bool (*Heap_Block_visitor)( - const Heap_Block *block, - uintptr_t block_size, - bool block_is_used, - void *visitor_arg -); - -/** - * @brief Iterates over all blocks of the heap. - * - * For each block the @a visitor with the argument @a visitor_arg will be - * called. - */ -void _Heap_Iterate( - Heap_Control *heap, - Heap_Block_visitor visitor, - void *visitor_arg -); - -/** - * @brief Greedy allocate that empties the heap. - * - * 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. - * - * @see _Heap_Greedy_free(). - */ -Heap_Block *_Heap_Greedy_allocate( - Heap_Control *heap, - const uintptr_t *block_sizes, - size_t block_count -); - -/** - * @brief Greedy allocate 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. - * - * @see _Heap_Greedy_free(). - */ -Heap_Block *_Heap_Greedy_allocate_all_except_largest( - Heap_Control *heap, - uintptr_t *allocatable_size -); - -/** - * @brief Frees blocks of a greedy allocation. - * - * The @a blocks must be the return value of _Heap_Greedy_allocate(). - */ -void _Heap_Greedy_free( - Heap_Control *heap, - Heap_Block *blocks -); - -/** - * @brief Returns information about used and free blocks for the heap @a heap - * in @a info. - */ -void _Heap_Get_information( - Heap_Control *heap, - Heap_Information_block *info -); - -/** - * @brief Returns information about free blocks for the heap @a heap in - * @a info. - */ -void _Heap_Get_free_information( - Heap_Control *heap, - Heap_Information *info -); - -/** - * @brief Returns the size of the allocatable memory area starting at @a addr - * in @a size. - * - * The size value may be greater than the initially requested size in - * _Heap_Allocate_aligned_with_boundary(). - * - * 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. - */ -bool _Heap_Size_of_alloc_area( - Heap_Control *heap, - void *addr, - uintptr_t *size -); - -/** - * @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. - * - * Inappropriate values for @a addr may corrupt the heap. - */ -Heap_Resize_status _Heap_Resize_block( - Heap_Control *heap, - void *addr, - uintptr_t size, - uintptr_t *old_size, - uintptr_t *new_size -); - -RTEMS_INLINE_ROUTINE uintptr_t _Heap_Align_up( - uintptr_t value, - uintptr_t alignment -) -{ - uintptr_t remainder = value % alignment; - - if ( remainder != 0 ) { - return value - remainder + alignment; - } else { - return value; - } -} - -/** - * @brief Returns the worst case overhead to manage a memory area. - */ -RTEMS_INLINE_ROUTINE uintptr_t _Heap_Area_overhead( - uintptr_t page_size -) -{ - if ( page_size != 0 ) { - page_size = _Heap_Align_up( page_size, CPU_ALIGNMENT ); - } else { - page_size = CPU_ALIGNMENT; - } - - return 2 * (page_size - 1) + HEAP_BLOCK_HEADER_SIZE; -} - -#if !defined(__RTEMS_APPLICATION__) - -#include - -/** - * @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 - * may be used or free. Free block parts which form a vaild new block will be - * inserted into the free list or merged with an adjacent free block. If the - * block is used, they will be inserted after the free list head. If the block - * is free, they will be inserted after the previous block in the free list. - * - * Inappropriate values for @a alloc_begin or @a alloc_size may corrupt the - * heap. - * - * Returns the block containing the allocated memory area. - */ -Heap_Block *_Heap_Block_allocate( - Heap_Control *heap, - Heap_Block *block, - uintptr_t alloc_begin, - uintptr_t alloc_size -); - -#ifndef HEAP_PROTECTION - #define _Heap_Protection_block_initialize( heap, block ) ((void) 0) - #define _Heap_Protection_block_check( heap, block ) ((void) 0) - #define _Heap_Protection_block_error( heap, block ) ((void) 0) - #define _Heap_Protection_free_all_delayed_blocks( heap ) ((void) 0) -#else - static inline void _Heap_Protection_block_initialize( - Heap_Control *heap, - Heap_Block *block - ) - { - (*heap->Protection.block_initialize)( heap, block ); - } - - static inline void _Heap_Protection_block_check( - Heap_Control *heap, - Heap_Block *block - ) - { - (*heap->Protection.block_check)( heap, block ); - } - - static inline void _Heap_Protection_block_error( - Heap_Control *heap, - Heap_Block *block - ) - { - (*heap->Protection.block_error)( heap, block ); - } - - static inline void _Heap_Protection_free_all_delayed_blocks( Heap_Control *heap ) - { - uintptr_t large = 0 - - (uintptr_t) HEAP_BLOCK_HEADER_SIZE - - (uintptr_t) HEAP_ALLOC_BONUS - - (uintptr_t) 1; - void *p = _Heap_Allocate( heap, large ); - _Heap_Free( heap, p ); - } -#endif - /** @} */ -#ifdef RTEMS_DEBUG - #define RTEMS_HEAP_DEBUG -#endif - -#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__) */ - #ifdef __cplusplus } #endif -- cgit v1.2.3