Heap Handler

This group contains the Heap Handler implementation. More...

Modules
	Protected Heap Handler
	This group contains the Protected Heap Handler implementation.

Files
file	heap.h
	This header file provides interfaces of the Heap Handler which are used by the implementation and the Application Configuration.
file	heapimpl.h
	This header file provides interfaces of the Barrier Handler which are only used by the implementation.
file	heapinfo.h
	This header file provides interfaces of the Barrier Handler which are used by the implementation and the API.
file	heap.c
	This source file contains the implementation of _Heap_Initialize() and _Heap_Block_allocate().
file	heapallocate.c
	This source file contains the implementation of _Heap_Allocate_aligned_with_boundary().
file	heapextend.c
	This source file contains the implementation of _Heap_Extend().
file	heapfree.c
	This source file contains the implementation of _Heap_Free().
file	heapgetfreeinfo.c
	This source file contains the implementation of _Heap_Get_free_information().
file	heapgetinfo.c
	This source file contains the implementation of _Heap_Get_information().
file	heapgreedy.c
	This source file contains the implementation of _Heap_Greedy_allocate(), _Heap_Greedy_allocate_all_except_largest(), and _Heap_Greedy_free().
file	heapiterate.c
	This source file contains the implementation of _Heap_Iterate().
file	heapnoextend.c
	This source file contains the implementation of _Heap_No_extend().
file	heapresizeblock.c
	This source file contains the implementation of _Heap_Resize_block().
file	heapsizeofuserarea.c
	This source file contains the implementation of _Heap_Size_of_alloc_area().
file	heapwalk.c
	This source file contains the implementation of _Heap_Walk().

Data Structures
struct	Heap_Error_context
	Context of a heap error. More...
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, reason)   ((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_Error_reason {   HEAP_ERROR_BROKEN_PROTECTOR , HEAP_ERROR_FREE_PATTERN , HEAP_ERROR_DOUBLE_FREE , HEAP_ERROR_BAD_USED_BLOCK ,   HEAP_ERROR_BAD_FREE_BLOCK }
	The heap error reason. More...
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. 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...
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. More...
uintptr_t	_Heap_Initialize (Heap_Control *heap, void *area_begin, uintptr_t area_size, uintptr_t page_size)
	Initializes the heap control block. More...
void *	_Heap_Allocate_aligned_with_boundary (Heap_Control *heap, uintptr_t size, uintptr_t alignment, uintptr_t boundary)
	Allocates an aligned memory area with boundary constraint. More...
bool	_Heap_Free (Heap_Control *heap, void *addr)
	Frees the allocated memory area. More...
bool	_Heap_Walk (Heap_Control *heap, int source, bool dump)
	Verifies the integrity of the heap. 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)
	Greedily allocates and empties the heap. More...
Heap_Block *	_Heap_Greedy_allocate_all_except_largest (Heap_Control *heap, uintptr_t *allocatable_size)
	Greedily allocates 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. More...
void	_Heap_Get_free_information (Heap_Control *heap, Heap_Information *info)
	Returns information about free blocks for the heap. More...
bool	_Heap_Size_of_alloc_area (Heap_Control *heap, void *addr, uintptr_t *size)
	Returns the size of the allocatable memory area. 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. 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...

Detailed Description

This group contains the Heap Handler implementation.

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 Documentation

Heap_Block_visitor

typedef bool(* Heap_Block_visitor) (const Heap_Block *block, uintptr_t block_size, bool block_is_used, void *visitor_arg)

Heap block visitor.

See also

_Heap_Iterate().

Return values

true	Stop the iteration.
false	Continue the iteration.

Heap_Initialization_or_extend_handler

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().

See also

Heap_Area, _Heap_Initialize(), _Heap_Extend(), or _Heap_No_extend().

Enumeration Type Documentation

Heap_Error_reason

enum Heap_Error_reason

The heap error reason.

See also

_Heap_Protection_block_error().

Enumerator
HEAP_ERROR_BROKEN_PROTECTOR	There is an unexpected value in the heap block protector area.
HEAP_ERROR_FREE_PATTERN	There is an unexpected value in the free pattern of a free heap block.
HEAP_ERROR_DOUBLE_FREE	There is was an attempt to free the same block twice.
HEAP_ERROR_BAD_USED_BLOCK	The next block of a supposed to be used block does not indicate that the block is used.
HEAP_ERROR_BAD_FREE_BLOCK	A supposed to be free block is not inside the heap memory area.

Function Documentation

_Heap_Allocate_aligned_with_boundary()

void * _Heap_Allocate_aligned_with_boundary	(	Heap_Control *	heap,
		uintptr_t	size,
		uintptr_t	alignment,
		uintptr_t	boundary
	)

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().

Parameters

[in,out]	heap	The heap to allocate a memory are from.
	size	The size of the desired memory are in bytes.
	alignment	The allocated memory area will begin at an address aligned by this value.
	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.

Return values

pointer	The starting address of the allocated memory area.
NULL	No memory is available of the parameters are inconsistent.

_Heap_Block_allocate()

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.

Parameters

[in,out]	heap	The heap to operate upon.
	block	The block in which the memory area should be allocated
	alloc_begin	The starting address of the memory area that shall be allocated.
	alloc_size	The size of the desired allocated area in bytes.

Returns

The block containing the allocated memory area.

_Heap_Extend()

uintptr_t _Heap_Extend	(	Heap_Control *	heap,
		void *	area_begin,
		uintptr_t	area_size,
		uintptr_t	unused
	)

Extends the memory available for the heap.

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.

Parameters

[in,out]	heap	The heap to extend.
[out]	area_begin	The start address of the area to extend the heap with.
	area_size	The size of the area in bytes.
	unused	Is not used, only provided to have the same signature as _Heap_Initialize().

Return values

some_value	The extended space available for allocation after successful extension.
0	The heap extension failed.

See also

Heap_Initialization_or_extend_handler.

_Heap_Free()

bool _Heap_Free	(	Heap_Control *	heap,
		void *	addr
	)

Frees the allocated memory area.

Inappropriate values for addr may corrupt the heap.

Parameters

[in,out]	heap	The heap of the allocated memory area.
	addr	The starting address of the memory area to be freed.

Return values

true	The allocated memory area was successfully freed.
false	The method failed.

_Heap_Get_first_and_last_block()

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.

Nothing will be written to this area.

Parameters

	heap_area_begin	The starting address of the heap area.
	heap_area_size	The size of the heap area.
	page_size	The page size for the calculation.
	min_block_size	The minimal block size for the calculation.
[out]	first_block_ptr	The pointer to the first block in the case of success
[out]	last_block_ptr	The pointer to the last block in the case of success

Return values

true	The area is big enough.
false	The area is not big enough.

_Heap_Get_free_information()

void _Heap_Get_free_information	(	Heap_Control *	heap,
		Heap_Information *	info
	)

Returns information about free blocks for the heap.

Parameters

	heap	The heap to get the information from.
[out]	info	Stores the information about free blocks of heap after the method call.

_Heap_Get_information()

void _Heap_Get_information	(	Heap_Control *	heap,
		Heap_Information_block *	info
	)

Returns information about used and free blocks for the heap.

Parameters

	heap	The heap to get the information from.
[out]	info	Stores the information of the heap after the method call.

_Heap_Greedy_allocate()

Heap_Block * _Heap_Greedy_allocate	(	Heap_Control *	heap,
		const uintptr_t *	block_sizes,
		size_t	block_count
	)

Greedily allocates and empties the heap.

Afterwards, the heap has at most block_count allocatable blocks of sizes specified by block_sizes. All other blocks are used.

Parameters

[in,out]	heap	The heap to operate upon
	block_sizes	The sizes of the allocatable blocks. Must point to an array with block_count members.
	block_count	The maximum number of allocatable blocks of sizes specified by @block_sizes.

Returns

Pointer to the first allocated block.

See also

_Heap_Greedy_free().

_Heap_Greedy_allocate_all_except_largest()

Heap_Block * _Heap_Greedy_allocate_all_except_largest	(	Heap_Control *	heap,
		uintptr_t *	allocatable_size
	)

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. All other blocks are used.

Parameters

[in,out]	heap	The heap to operate upon.
[out]	allocatable_size	Stores the size of the largest free block of the heap after the method call.

Returns

Pointer to the first allocated block.

See also

_Heap_Greedy_free().

_Heap_Greedy_free()

void _Heap_Greedy_free	(	Heap_Control *	heap,
		Heap_Block *	blocks
	)

Frees blocks of a greedy allocation.

Parameters

[in,out]	heap	The heap to operate upon.
	blocks	Must be the return value of _Heap_Greedy_allocate().

_Heap_Initialize()

uintptr_t _Heap_Initialize	(	Heap_Control *	heap,
		void *	area_begin,
		uintptr_t	area_size,
		uintptr_t	page_size
	)

Initializes the heap control block.

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.

Parameters

[out]	heap	The heap control block to manage the area.
	area_begin	The starting address of the area.
	area_size	The size of the area in bytes.
	page_size	The page size for the calculation

Return values

some_value	The maximum memory available.
0	The initialization failed.

See also

Heap_Initialization_or_extend_handler.

_Heap_Iterate()

void _Heap_Iterate	(	Heap_Control *	heap,
		Heap_Block_visitor	visitor,
		void *	visitor_arg
	)

Iterates over all blocks of the heap.

Parameters

[in,out]	heap	The heap to iterate over.
	visitor	This will be called for each heap block with the argument visitor_arg.
[in,out]	visitor_arg	The argument for all calls of visitor.

_Heap_No_extend()

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.

Parameters

unused_0	This parameter does nothing.
unused_1	This parameter does nothing.
unused_2	This parameter does nothing.
unused_3	This parameter does nothing.

See also

Heap_Initialization_or_extend_handler.

_Heap_Resize_block()

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.

Inappropriate values for addr may corrupt the heap.

Parameters

[in,out]	heap	The heap to operate upon.
	addr	The starting address of the allocated memory area to be resized.
	size	The least possible size for the new memory area. Resize may be impossible and depends on the current heap usage.
[out]	old_size	Stores the size available for allocation in the current block before the resize after the method call.
[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

Return values

HEAP_RESIZE_SUCCESSFUL	The resize was successful.
HEAP_RESIZE_UNSATISFIED	The least possible size size was too big. Resize not possible.
HEAP_RESIZE_FATAL_ERROR	The block starting at addr is not part of the heap.

_Heap_Size_of_alloc_area()

bool _Heap_Size_of_alloc_area	(	Heap_Control *	heap,
		void *	addr,
		uintptr_t *	size
	)

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().

Inappropriate values for addr will not corrupt the heap, but may yield invalid size values.

Parameters

	heap	The heap to operate upon.
	addr	The starting address of the allocatable memory area.
[out]	size	Stores the size of the allocatable memory area after the method call.

Return values

true	The operation was successful.
false	The operation was not successful.

_Heap_Walk()

bool _Heap_Walk	(	Heap_Control *	heap,
		int	source,
		bool	dump
	)

Verifies the integrity of the heap.

Walks the heap to verify its integrity.

Parameters

heap	The heap whose integrity is to be verified.
source	If dump is true, this is used to mark the output lines.
dump	Indicates whether diagnostic messages will be printed to standard output.

Return values

true	No errors occurred, the heap´s integrity is not violated.
false	The heap is corrupt.