RTEMS
5.0.0
|
The Heap Handler provides a heap. More...
Modules | |
Protected Heap Handler | |
Provides protected heap services. | |
Files | |
file | heap.h |
Heap Handler API. | |
file | heapimpl.h |
Heap Handler Implementation. | |
file | heapinfo.h |
Heap Handler Information API. | |
file | heap.c |
Heap Handler implementation. | |
file | heapallocate.c |
Heap Handler implementation. | |
file | heapextend.c |
Heap Handler implementation. | |
file | heapfree.c |
Heap Handler implementation. | |
file | heapgetfreeinfo.c |
Heap Handler implementation. | |
file | heapgetinfo.c |
Heap Handler implementation. | |
file | heapgreedy.c |
Heap Handler API. | |
file | heapiterate.c |
_Heap_Iterate() implementation. | |
file | heapnoextend.c |
Heap Handler implementation. | |
file | heapresizeblock.c |
Heap Handler implementation. | |
file | heapsizeofuserarea.c |
Heap Handler implementation. | |
file | heapwalk.c |
Heap Handler implementation. | |
Data Structures | |
struct | Heap_Block |
Description for free or used blocks. More... | |
struct | Heap_Control |
Control block used to manage a heap. More... | |
struct | Heap_Area |
Heap area structure for table based heap initialization and extension. More... | |
struct | Heap_Statistics |
Run-time heap statistics. More... | |
struct | Heap_Information |
Information about blocks. More... | |
struct | Heap_Information_block |
Information block returned by _Heap_Get_information(). More... | |
Macros | |
#define | HEAP_PROTECTION_HEADER_SIZE 0 |
#define | HEAP_BLOCK_HEADER_SIZE (2 * sizeof(uintptr_t) + HEAP_PROTECTION_HEADER_SIZE) |
The block header consists of the two size fields (Heap_Block::prev_size and Heap_Block::size_and_flag). | |
#define | HEAP_PREV_BLOCK_USED ((uintptr_t) 1) |
See also Heap_Block::size_and_flag. | |
#define | HEAP_ALLOC_BONUS sizeof(uintptr_t) |
Size of the part at the block begin which may be used for allocation in charge of the previous block. | |
#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) |
#define | _HAssert(cond) ((void) 0) |
Typedefs | |
typedef struct Heap_Control | Heap_Control |
typedef struct Heap_Block | Heap_Block |
typedef uintptr_t(* | Heap_Initialization_or_extend_handler) (Heap_Control *heap, void *area_begin, uintptr_t area_size, uintptr_t page_size_or_unused) |
Heap initialization and extend handler type. More... | |
typedef bool(* | Heap_Block_visitor) (const Heap_Block *block, uintptr_t block_size, bool block_is_used, void *visitor_arg) |
Heap block visitor. More... | |
Enumerations | |
enum | Heap_Resize_status { HEAP_RESIZE_SUCCESSFUL, HEAP_RESIZE_UNSATISFIED, HEAP_RESIZE_FATAL_ERROR } |
See _Heap_Resize_block(). | |
Functions | |
uintptr_t | _Heap_Extend (Heap_Control *heap, void *area_begin, uintptr_t area_size, uintptr_t unused) |
Extends the memory available for the heap heap using the memory area starting at area_begin of size area_size bytes. More... | |
uintptr_t | _Heap_No_extend (Heap_Control *unused_0, void *unused_1, uintptr_t unused_2, uintptr_t unused_3) |
This function returns always zero. More... | |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Align_up (uintptr_t value, uintptr_t alignment) |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Min_block_size (uintptr_t page_size) |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Area_overhead (uintptr_t page_size) |
Returns the worst case overhead to manage a memory area. | |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Size_with_overhead (uintptr_t page_size, uintptr_t size, uintptr_t alignment) |
Returns the size with administration and alignment overhead for one allocation. | |
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) |
Gets the first and last block for the heap area with begin heap_area_begin and size heap_area_size. More... | |
uintptr_t | _Heap_Initialize (Heap_Control *heap, void *area_begin, uintptr_t area_size, uintptr_t page_size) |
Initializes the heap control block heap to manage the area starting at area_begin of size area_size bytes. More... | |
void * | _Heap_Allocate_aligned_with_boundary (Heap_Control *heap, uintptr_t size, uintptr_t alignment, uintptr_t boundary) |
Allocates a memory area of size size bytes from the heap heap. More... | |
RTEMS_INLINE_ROUTINE void * | _Heap_Allocate_aligned (Heap_Control *heap, uintptr_t size, uintptr_t alignment) |
See _Heap_Allocate_aligned_with_boundary() with boundary equals zero. | |
RTEMS_INLINE_ROUTINE void * | _Heap_Allocate (Heap_Control *heap, uintptr_t size) |
See _Heap_Allocate_aligned_with_boundary() with alignment and boundary equals zero. | |
bool | _Heap_Free (Heap_Control *heap, void *addr) |
Frees the allocated memory area starting at addr in the heap heap. More... | |
bool | _Heap_Walk (Heap_Control *heap, int source, bool dump) |
Walks the heap heap to verify its integrity. More... | |
void | _Heap_Iterate (Heap_Control *heap, Heap_Block_visitor visitor, void *visitor_arg) |
Iterates over all blocks of the heap. More... | |
Heap_Block * | _Heap_Greedy_allocate (Heap_Control *heap, const uintptr_t *block_sizes, size_t block_count) |
Greedy allocate that empties the heap. More... | |
Heap_Block * | _Heap_Greedy_allocate_all_except_largest (Heap_Control *heap, uintptr_t *allocatable_size) |
Greedy allocate all blocks except the largest free block. More... | |
void | _Heap_Greedy_free (Heap_Control *heap, Heap_Block *blocks) |
Frees blocks of a greedy allocation. More... | |
void | _Heap_Get_information (Heap_Control *heap, Heap_Information_block *info) |
Returns information about used and free blocks for the heap heap in info. | |
void | _Heap_Get_free_information (Heap_Control *heap, Heap_Information *info) |
Returns information about free blocks for the heap heap in info. | |
bool | _Heap_Size_of_alloc_area (Heap_Control *heap, void *addr, uintptr_t *size) |
Returns the size of the allocatable memory area starting at addr in size. More... | |
Heap_Resize_status | _Heap_Resize_block (Heap_Control *heap, void *addr, uintptr_t size, uintptr_t *old_size, uintptr_t *new_size) |
Resizes the block of the allocated memory area starting at addr. More... | |
Heap_Block * | _Heap_Block_allocate (Heap_Control *heap, Heap_Block *block, uintptr_t alloc_begin, uintptr_t alloc_size) |
Allocates the memory area starting at alloc_begin of size alloc_size bytes in the block block. More... | |
RTEMS_INLINE_ROUTINE void | _Heap_Protection_set_delayed_free_fraction (Heap_Control *heap, uintptr_t fraction) |
Sets the fraction of delayed free blocks that is actually freed during memory shortage. More... | |
RTEMS_INLINE_ROUTINE Heap_Block * | _Heap_Free_list_head (Heap_Control *heap) |
RTEMS_INLINE_ROUTINE Heap_Block * | _Heap_Free_list_tail (Heap_Control *heap) |
RTEMS_INLINE_ROUTINE Heap_Block * | _Heap_Free_list_first (Heap_Control *heap) |
RTEMS_INLINE_ROUTINE Heap_Block * | _Heap_Free_list_last (Heap_Control *heap) |
RTEMS_INLINE_ROUTINE void | _Heap_Free_list_remove (Heap_Block *block) |
RTEMS_INLINE_ROUTINE void | _Heap_Free_list_replace (Heap_Block *old_block, Heap_Block *new_block) |
RTEMS_INLINE_ROUTINE void | _Heap_Free_list_insert_after (Heap_Block *block_before, Heap_Block *new_block) |
RTEMS_INLINE_ROUTINE void | _Heap_Free_list_insert_before (Heap_Block *block_next, Heap_Block *new_block) |
RTEMS_INLINE_ROUTINE bool | _Heap_Is_aligned (uintptr_t value, uintptr_t alignment) |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Align_down (uintptr_t value, uintptr_t alignment) |
RTEMS_INLINE_ROUTINE Heap_Block * | _Heap_Block_at (const Heap_Block *block, uintptr_t offset) |
Returns the block which is offset away from block. | |
RTEMS_INLINE_ROUTINE Heap_Block * | _Heap_Prev_block (const Heap_Block *block) |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Alloc_area_of_block (const Heap_Block *block) |
RTEMS_INLINE_ROUTINE Heap_Block * | _Heap_Block_of_alloc_area (uintptr_t alloc_begin, uintptr_t page_size) |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Block_size (const Heap_Block *block) |
RTEMS_INLINE_ROUTINE void | _Heap_Block_set_size (Heap_Block *block, uintptr_t size) |
RTEMS_INLINE_ROUTINE bool | _Heap_Is_prev_used (const Heap_Block *block) |
RTEMS_INLINE_ROUTINE bool | _Heap_Is_used (const Heap_Block *block) |
RTEMS_INLINE_ROUTINE bool | _Heap_Is_free (const Heap_Block *block) |
RTEMS_INLINE_ROUTINE bool | _Heap_Is_block_in_heap (const Heap_Control *heap, const Heap_Block *block) |
RTEMS_INLINE_ROUTINE void | _Heap_Set_last_block_size (Heap_Control *heap) |
Sets the size of the last block for heap heap. More... | |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Get_size (const Heap_Control *heap) |
Returns the size of the allocatable area in bytes. More... | |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Max (uintptr_t a, uintptr_t b) |
RTEMS_INLINE_ROUTINE uintptr_t | _Heap_Min (uintptr_t a, uintptr_t b) |
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.
The alignment routines could be made faster should we require only powers of two to be supported for page size, alignment and boundary arguments. The minimum alignment requirement for pages is currently CPU_ALIGNMENT and this value is only required to be multiple of two 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 provide an allocated memory area. The free blocks are accessible via a list of free blocks.
Blocks or areas cover a continuous set of memory addresses. They have a begin and end address. The end address is not part of the set. The size of a block or area equals the distance between the begin and end address in units of bytes.
Free blocks look like:
Heap_Block | previous 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:
Heap_Block | previous 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:
Label | Content | |
---|---|---|
heap->area_begin | heap area begin address | |
first_block->prev_size | subordinate heap area end address (this will be used to maintain a linked list of scattered heap areas) | |
first_block->size | size available for allocation | 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) | |
... | ||
last_block->prev_size | size of first block | |
last_block->size | first block begin address - last block begin address | |
heap->area_end | heap area end address |
The next block of the last block is the first block. Since the first block indicates that the previous block is used, this ensures that the last block appears as used for the _Heap_Is_used() and _Heap_Is_free() functions.
typedef bool(* Heap_Block_visitor) (const Heap_Block *block, uintptr_t block_size, bool block_is_used, void *visitor_arg) |
Heap block visitor.
true | Stop the iteration. |
false | Continue the iteration. |
typedef uintptr_t(* Heap_Initialization_or_extend_handler) (Heap_Control *heap, void *area_begin, uintptr_t area_size, uintptr_t page_size_or_unused) |
Heap initialization and extend handler type.
This helps to do a table based heap initialization and extension. Create a table of Heap_Area elements and iterate through it. Set the handler to _Heap_Initialize() in the first iteration and then to _Heap_Extend().
void* _Heap_Allocate_aligned_with_boundary | ( | Heap_Control * | heap, |
uintptr_t | size, | ||
uintptr_t | alignment, | ||
uintptr_t | boundary | ||
) |
Allocates a memory area of size size bytes from the heap heap.
If the alignment parameter alignment is not equal to zero, the allocated memory area will begin at an address aligned by this value.
If the boundary parameter 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 NULL
if no memory is available or the parameters are inconsistent.
Heap_Block* _Heap_Block_allocate | ( | Heap_Control * | heap, |
Heap_Block * | block, | ||
uintptr_t | alloc_begin, | ||
uintptr_t | alloc_size | ||
) |
Allocates the memory area starting at alloc_begin of size alloc_size bytes in the block 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 alloc_begin or alloc_size may corrupt the heap.
Returns the block containing the allocated memory area.
uintptr_t _Heap_Extend | ( | Heap_Control * | heap, |
void * | area_begin, | ||
uintptr_t | area_size, | ||
uintptr_t | unused | ||
) |
Extends the memory available for the heap heap using the memory area starting at area_begin of size area_size bytes.
There are no alignment requirements for the memory area. The memory area must be big enough to contain some maintenance blocks. It must not overlap parts of the current heap memory areas. Disconnected memory areas added to the heap will lead to used blocks which cover the gaps. Extending with an inappropriate memory area will corrupt the heap resulting in undefined behaviour.
The unused fourth parameter is provided to have the same signature as _Heap_Initialize().
Returns the extended space available for allocation, or zero in case of failure.
bool _Heap_Free | ( | Heap_Control * | heap, |
void * | addr | ||
) |
Frees the allocated memory area starting at addr in the heap heap.
Inappropriate values for addr may corrupt the heap.
Returns true
in case of success, and 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 | ||
) |
Gets the first and last block for the heap area with begin heap_area_begin and size heap_area_size.
A page size of page_size and minimal block size of 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 first_block_ptr and last_block_ptr.
Returns true
if the area is big enough, and false
otherwise.
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Get_size | ( | const Heap_Control * | heap | ) |
Returns the size of the allocatable area in bytes.
This value is an integral multiple of the page size.
Heap_Block* _Heap_Greedy_allocate | ( | Heap_Control * | heap, |
const uintptr_t * | block_sizes, | ||
size_t | block_count | ||
) |
Greedy allocate that empties the heap.
Afterwards the heap has at most block_count allocatable blocks of sizes specified by block_sizes. The block_sizes must point to an array with block_count members. All other blocks are used.
Heap_Block* _Heap_Greedy_allocate_all_except_largest | ( | Heap_Control * | heap, |
uintptr_t * | allocatable_size | ||
) |
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 allocatable_size. All other blocks are used.
void _Heap_Greedy_free | ( | Heap_Control * | heap, |
Heap_Block * | blocks | ||
) |
Frees blocks of a greedy allocation.
The blocks must be the return value of _Heap_Greedy_allocate().
uintptr_t _Heap_Initialize | ( | Heap_Control * | heap, |
void * | area_begin, | ||
uintptr_t | area_size, | ||
uintptr_t | page_size | ||
) |
Initializes the heap control block heap to manage the area starting at area_begin of size area_size bytes.
Blocks of memory are allocated from the heap in multiples of page_size byte units. If the page_size is equal to zero or is not multiple of CPU_ALIGNMENT
, it is aligned up to the nearest CPU_ALIGNMENT
boundary.
Returns the maximum memory available, or zero in case of failure.
void _Heap_Iterate | ( | Heap_Control * | heap, |
Heap_Block_visitor | visitor, | ||
void * | visitor_arg | ||
) |
Iterates over all blocks of the heap.
For each block the visitor with the argument visitor_arg will be called.
uintptr_t _Heap_No_extend | ( | Heap_Control * | unused_0, |
void * | unused_1, | ||
uintptr_t | unused_2, | ||
uintptr_t | unused_3 | ||
) |
This function returns always zero.
This function only returns zero and does nothing else.
Returns always zero.
RTEMS_INLINE_ROUTINE void _Heap_Protection_set_delayed_free_fraction | ( | Heap_Control * | heap, |
uintptr_t | fraction | ||
) |
Sets the fraction of delayed free blocks that is actually freed during memory shortage.
The default is to free half the delayed free blocks. This is equal to a fraction value of two.
[in] | heap | The heap control. |
[in] | fraction | The fraction is one divided by this fraction value. |
Heap_Resize_status _Heap_Resize_block | ( | Heap_Control * | heap, |
void * | addr, | ||
uintptr_t | size, | ||
uintptr_t * | old_size, | ||
uintptr_t * | new_size | ||
) |
Resizes the block of the allocated memory area starting at addr.
The new memory area will have a size of at least 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 old_size. The size available for allocation in the resized block will be returned in new_size. If the resize was not successful, then a value of zero will be returned in new_size.
Inappropriate values for addr may corrupt the heap.
RTEMS_INLINE_ROUTINE void _Heap_Set_last_block_size | ( | Heap_Control * | heap | ) |
Sets the size of the last block for heap 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 block appears as used for the _Heap_Is_used() and _Heap_Is_free() functions.
This feature will be used to terminate the scattered heap area list. See also _Heap_Extend().
bool _Heap_Size_of_alloc_area | ( | Heap_Control * | heap, |
void * | addr, | ||
uintptr_t * | size | ||
) |
Returns the size of the allocatable memory area starting at addr in size.
The size value may be greater than the initially requested size in _Heap_Allocate_aligned_with_boundary().
Inappropriate values for addr will not corrupt the heap, but may yield invalid size values.
Returns true if successful, and false
otherwise.
bool _Heap_Walk | ( | Heap_Control * | heap, |
int | source, | ||
bool | dump | ||
) |
Walks the heap heap to verify its integrity.
If dump is true
, then diagnostic messages will be printed to standard output. In this case source is used to mark the output lines.
Returns true
if no errors occurred, and false
if the heap is corrupt.