Heap Handler


Data Structures
struct	Heap_Block_struct
struct	Heap_Statistics
struct	Heap_Control
struct	Heap_Information
struct	Heap_Information_block
Defines
#define	HEAP_PREV_USED 1
#define	HEAP_MIN_BLOCK_SIZE (sizeof(Heap_Block))
#define	HEAP_BLOCK_HEADER_OFFSET (sizeof(uint32_t))
#define	HEAP_BLOCK_USER_OFFSET (sizeof(uint32_t) * 2)
#define	HEAP_BLOCK_USED_OVERHEAD (HEAP_BLOCK_USER_OFFSET - HEAP_BLOCK_HEADER_OFFSET)
#define	HEAP_OVERHEAD HEAP_BLOCK_USER_OFFSET
#define	_H_p2u(_p) ((_H_uptr_t)(_p))
#define	_HAssert(cond_) ((void)0)
Typedefs
typedef uintptr_t	_H_uptr_t
typedef struct Heap_Block_struct	Heap_Block
Enumerations
enum	Heap_Extend_status { HEAP_EXTEND_SUCCESSFUL, HEAP_EXTEND_ERROR, HEAP_EXTEND_NOT_IMPLEMENTED }
enum	Heap_Resize_status { HEAP_RESIZE_SUCCESSFUL, HEAP_RESIZE_UNSATISFIED, HEAP_RESIZE_FATAL_ERROR }
enum	Heap_Get_information_status { HEAP_GET_INFORMATION_SUCCESSFUL = 0, HEAP_GET_INFORMATION_BLOCK_ERROR }
Functions
uint32_t	_Heap_Initialize (Heap_Control the_heap, void starting_address, size_t size, uint32_t page_size)
Heap_Extend_status	_Heap_Extend (Heap_Control the_heap, void starting_address, size_t size, uint32_t *amount_extended)
void *	_Heap_Allocate (Heap_Control *the_heap, size_t size)
void *	_Heap_Allocate_aligned (Heap_Control *the_heap, size_t size, uint32_t alignment)
bool	_Heap_Size_of_user_area (Heap_Control the_heap, void starting_address, size_t *size)
Heap_Resize_status	_Heap_Resize_block (Heap_Control the_heap, void starting_address, size_t size, uint32_t old_mem_size, uint32_t avail_mem_size)
bool	_Heap_Free (Heap_Control the_heap, void start_address)
bool	_Heap_Walk (Heap_Control *the_heap, int source, bool do_dump)
Heap_Get_information_status	_Heap_Get_information (Heap_Control the_heap, Heap_Information_block the_info)
void	_Heap_Get_free_information (Heap_Control the_heap, Heap_Information info)
size_t	_Heap_Calc_block_size (size_t size, uint32_t page_size, uint32_t min_size)
uint32_t	_Heap_Block_allocate (Heap_Control the_heap, Heap_Block the_block, uint32_t alloc_size)
RTEMS_INLINE_ROUTINE Heap_Block *	_Heap_Head (Heap_Control *the_heap)
RTEMS_INLINE_ROUTINE Heap_Block *	_Heap_Tail (Heap_Control *the_heap)
RTEMS_INLINE_ROUTINE Heap_Block *	_Heap_First (Heap_Control *the_heap)
RTEMS_INLINE_ROUTINE Heap_Block *	_Heap_Last (Heap_Control *the_heap)
RTEMS_INLINE_ROUTINE void	_Heap_Block_remove (Heap_Block *the_block)
RTEMS_INLINE_ROUTINE void	_Heap_Block_replace (Heap_Block old_block, Heap_Block new_block)
RTEMS_INLINE_ROUTINE void	_Heap_Block_insert_after (Heap_Block prev_block, Heap_Block the_block)
RTEMS_INLINE_ROUTINE bool	_Heap_Is_aligned (uint32_t value, uint32_t alignment)
RTEMS_INLINE_ROUTINE void	_Heap_Align_up (uint32_t *value, uint32_t alignment)
RTEMS_INLINE_ROUTINE void	_Heap_Align_down (uint32_t *value, uint32_t alignment)
RTEMS_INLINE_ROUTINE bool	_Heap_Is_aligned_ptr (void *ptr, uint32_t alignment)
RTEMS_INLINE_ROUTINE void	_Heap_Align_up_uptr (_H_uptr_t *value, uint32_t alignment)
RTEMS_INLINE_ROUTINE void	_Heap_Align_down_uptr (_H_uptr_t *value, uint32_t alignment)
RTEMS_INLINE_ROUTINE Heap_Block *	_Heap_Block_at (void *base, uint32_t offset)
RTEMS_INLINE_ROUTINE void *	_Heap_User_area (Heap_Block *the_block)
RTEMS_INLINE_ROUTINE void	_Heap_Start_of_block (Heap_Control the_heap, void base, Heap_Block **the_block)
RTEMS_INLINE_ROUTINE bool	_Heap_Is_prev_used (Heap_Block *the_block)
RTEMS_INLINE_ROUTINE uint32_t	_Heap_Block_size (Heap_Block *the_block)
RTEMS_INLINE_ROUTINE bool	_Heap_Is_block_in (Heap_Control the_heap, Heap_Block the_block)

Detailed Description

This handler encapsulates functionality which provides the foundation Heap services used in all of the APIs supported by RTEMS.

Define Documentation

#define _H_p2u ( _p ) ((_H_uptr_t)(_p))

A pointer to unsigned integer conversion.

Referenced by _Heap_Is_aligned_ptr(), and _Heap_Start_of_block().

#define _HAssert ( cond_ ) ((void)0)

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 HEAP_BLOCK_HEADER_OFFSET (sizeof(uint32_t))

Offset of the block header from the block pointer. Equal to the offsetof(Heap_Block.size).

#define HEAP_BLOCK_USED_OVERHEAD (HEAP_BLOCK_USER_OFFSET - HEAP_BLOCK_HEADER_OFFSET)

Num bytes of overhead in used block. Equal to the sizeof(Heap_Block.size).

#define HEAP_BLOCK_USER_OFFSET (sizeof(uint32_t) * 2)

Offset of user data pointer from the block pointer. Equal to the offsetof(Heap_Block.next).

Referenced by _Heap_Start_of_block(), and _Heap_User_area().

#define HEAP_MIN_BLOCK_SIZE (sizeof(Heap_Block))

The following constants reflect various requirements of the heap data structures which impact the management of a heap.

#define HEAP_OVERHEAD HEAP_BLOCK_USER_OFFSET

Size of the permanent dummy last block.

#define HEAP_PREV_USED 1

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.

Referenced by _Heap_Block_size(), and _Heap_Is_prev_used().

Typedef Documentation

typedef uintptr_t _H_uptr_t

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 struct Heap_Block_struct Heap_Block

Forward reference

Heap_Block

Enumeration Type Documentation

enum Heap_Extend_status

Status codes for _Heap_Extend

enum Heap_Get_information_status

Status codes for _Heap_Get_information

enum Heap_Resize_status

Status codes for _Heap_Resize_block

Function Documentation

RTEMS_INLINE_ROUTINE void _Heap_Align_down	(	uint32_t *	value,
		uint32_t	alignment
	)

Align *value down to the nearest multiple of alignment.

Parameters:

`[in]`	value	is a pointer to be aligned.
`[in]`	alignment	is the alignment value.

Returns:: Upon return, value will contain the aligned result.

RTEMS_INLINE_ROUTINE void _Heap_Align_down_uptr	(	_H_uptr_t *	value,
		uint32_t	alignment
	)

Align *value down to the nearest multiple of alignment.

Parameters:

`[in]`	value	is a pointer to be aligned.
`[in]`	alignment	is the alignment value.

Returns:: Upon return, value will contain the aligned result.

Referenced by _Heap_Start_of_block().

RTEMS_INLINE_ROUTINE void _Heap_Align_up	(	uint32_t *	value,
		uint32_t	alignment
	)

Align *value up to the nearest multiple of alignment.

Parameters:

`[in]`	value	is a pointer to be aligned.
`[in]`	alignment	is the alignment value.

Returns:: Upon return, value will contain the aligned result.

RTEMS_INLINE_ROUTINE void _Heap_Align_up_uptr	(	_H_uptr_t *	value,
		uint32_t	alignment
	)

Align *value up to the nearest multiple of alignment.

Parameters:

`[in]`	value	is a pointer to be aligned.
`[in]`	alignment	is the alignment value.

Returns:: Upon return, value will contain the aligned result.

void* _Heap_Allocate	(	Heap_Control *	the_heap,
		size_t	size
	)

This function attempts to allocate a block of size bytes from the_heap. If insufficient memory is free in the_heap to allocate a block of the requested size, then NULL is returned.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	size	is the amount of memory to allocate in bytes

Returns:: NULL if unsuccessful and a pointer to the block if successful

void* _Heap_Allocate_aligned	(	Heap_Control *	the_heap,
		size_t	size,
		uint32_t	alignment
	)

This function attempts to allocate a memory block of size bytes from the_heap so that the start of the user memory is aligned on the alignment boundary. If alignment is 0, it is set to CPU_ALIGNMENT. Any other value of 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.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	size	is the amount of memory to allocate in bytes
`[in]`	alignment	the required alignment

Returns:: NULL if unsuccessful and a pointer to the block if successful

uint32_t _Heap_Block_allocate	(	Heap_Control *	the_heap,
		Heap_Block *	the_block,
		uint32_t	alloc_size
	)

This method allocates a block of size alloc_size from the_block belonging to the_heap. Split the_block if possible, otherwise allocate it entirely. When split, make the lower part used, and leave the upper part free.

This is an internal routines used by _Heap_Allocate() and _Heap_Allocate_aligned(). Refer to 'heap.c' for details.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	the_block	is the block to allocates the requested size from
`[in]`	alloc_size	is the requested number of bytes to take out of the block

Returns:: This methods returns the size of the allocated block.

RTEMS_INLINE_ROUTINE Heap_Block* _Heap_Block_at	(	void *	base,
		uint32_t	offset
	)

This function calculates and returns a block's location (address) in the heap based upon a base address base and an offset.

Parameters:

`[in]`	base	is the base address of the memory area.
`[in]`	offset	is the byte offset into base.

Returns:: This method returns a pointer to the block's address.

References _Addresses_Add_offset().

RTEMS_INLINE_ROUTINE void _Heap_Block_insert_after	(	Heap_Block *	prev_block,
		Heap_Block *	the_block
	)

This function inserts the_block after prev_block in the doubly-linked free block list.

Parameters:

`[in]`	prev_block	is the previous block in the free list.
`[in]`	the_block	is the block being freed.

References Heap_Block_struct::next, and Heap_Block_struct::prev.

RTEMS_INLINE_ROUTINE void _Heap_Block_remove ( Heap_Block * the_block )

This function removes 'the_block' from doubly-linked list.

Parameters:

[in] the_block is the block to remove from the heap used block list.

References Heap_Block_struct::next, and Heap_Block_struct::prev.

RTEMS_INLINE_ROUTINE void _Heap_Block_replace	(	Heap_Block *	old_block,
		Heap_Block *	new_block
	)

This function replaces old_block by new_block in doubly-linked list. When a block is allocated, the memory is allocated from the low memory address range of the block. This means that the upper address range of the memory block must be added to the free block list in place of the lower address portion being allocated. This method is also used as part of resizing a block.

Parameters:

`[in]`	old_block	is the block which is currently on the list.
`[in]`	new_block	is the new block which will replace it on the list.

References Heap_Block_struct::next, and Heap_Block_struct::prev.

RTEMS_INLINE_ROUTINE uint32_t _Heap_Block_size ( Heap_Block * the_block )

This function returns the size of the_block in bytes.

Parameters:

[in] the_block is the block to operate upon.

Returns:: This method returns the size of the specified heap block in bytes.

References HEAP_PREV_USED, and Heap_Block_struct::size.

size_t _Heap_Calc_block_size	(	size_t	size,
		uint32_t	page_size,
		uint32_t	min_size
	)

Convert user requested 'size' of memory block to the block size.

Note:: This is an internal routine used by _Heap_Allocate() and _Heap_Allocate_aligned(). Refer to 'heap.c' for details.

Parameters:

`[in]`	size	is the size of the block requested
`[in]`	page_size	is the page size of this heap instance
`[in]`	min_size	is minimum size block that should be allocated from this heap instance

Returns:: This method returns block size on success, 0 if overflow occured.

Heap_Extend_status _Heap_Extend	(	Heap_Control *	the_heap,
		void *	starting_address,
		size_t	size,
		uint32_t *	amount_extended
	)

This routine grows the_heap memory area using the size bytes which begin at starting_address.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	starting_address	is the starting address of the memory to add to the heap
`[in]`	size	is the size in bytes of the memory area to add
`[in]`	amount_extended	points to a user area to return the

Returns:: a status indicating success or the reason for failure
*size filled in with the amount of memory added to the heap

RTEMS_INLINE_ROUTINE Heap_Block* _Heap_First ( Heap_Control * the_heap )

Return the first free block of the specified heap.

Parameters:

[in] the_heap points to the heap being operated upon

Returns:: This method returns a pointer to the first free block.

References _Heap_Head(), and Heap_Block_struct::next.

bool _Heap_Free	(	Heap_Control *	the_heap,
		void *	start_address
	)

This routine returns the block of memory which begins at starting_address to the_heap. Any coalescing which is possible with the freeing of this routine is performed.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	start_address	is the starting address of the user block to free

Returns:: TRUE if successfully freed, FALSE otherwise

void _Heap_Get_free_information	(	Heap_Control *	the_heap,
		Heap_Information *	info
	)

This heap routine returns information about the free blocks in the specified heap.

Parameters:

`[in]`	the_heap	pointer to heap header.
`[in]`	info	pointer to the free block information.

Returns:: free block information filled in.

Heap_Get_information_status _Heap_Get_information	(	Heap_Control *	the_heap,
		Heap_Information_block *	the_info
	)

This routine walks the heap and tots up the free and allocated sizes.

Parameters:

`[in]`	the_heap	pointer to heap header
`[in]`	the_info	pointer to a status information area

Returns:: *the_info is filled with status information
0=success, otherwise heap is corrupt.

RTEMS_INLINE_ROUTINE Heap_Block* _Heap_Head ( Heap_Control * the_heap )

This function returns the head of the specified heap.

Parameters:

[in] the_heap points to the heap being operated upon

Returns:: This method returns a pointer to the dummy head of the free block list.

References Heap_Control::free_list.

Referenced by _Heap_First().

uint32_t _Heap_Initialize	(	Heap_Control *	the_heap,
		void *	starting_address,
		size_t	size,
		uint32_t	page_size
	)

This routine initializes the_heap record to manage the contiguous heap of size bytes which starts at starting_address. Blocks of memory are allocated from the heap in multiples of page_size byte units. If page_size is 0 or is not multiple of CPU_ALIGNMENT, it's aligned up to the nearest CPU_ALIGNMENT boundary.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	starting_address	is the starting address of the memory for the heap
`[in]`	size	is the size in bytes of the memory area for the heap
`[in]`	page_size	is the size in bytes of the allocation unit

Returns:: This method returns the maximum memory available. If unsuccessful, 0 will be returned.

RTEMS_INLINE_ROUTINE bool _Heap_Is_aligned	(	uint32_t	value,
		uint32_t	alignment
	)

Return TRUE if value is a multiple of alignment, FALSE otherwise

Parameters:

`[in]`	value	is the address to verify alignment of.
`[in]`	alignment	is the alignment factor to verify.

Returns:: This method returns TRUE if the address is aligned and false otherwise.

RTEMS_INLINE_ROUTINE bool _Heap_Is_aligned_ptr	(	void *	ptr,
		uint32_t	alignment
	)

Return TRUE if ptr is aligned at alignment boundary, FALSE otherwise.

Parameters:

`[in]`	ptr	is the pointer to verify alignment of.
`[in]`	alignment	is the alignment factor.

Returns:: This method returns TRUE if ptr is aligned at alignment boundary, and FALSE otherwise.

References _H_p2u.

RTEMS_INLINE_ROUTINE bool _Heap_Is_block_in	(	Heap_Control *	the_heap,
		Heap_Block *	the_block
	)

This function returns TRUE if the_block is within the memory area managed by the_heap, and FALSE otherwise.

Parameters:

`[in]`	the_heap	points to the heap being operated upon
`[in]`	the_block	is the block address to check.

Returns:: This method returns TRUE if the_block appears to have been allocated from the_heap, and FALSE otherwise.

References _Addresses_Is_in_range(), Heap_Control::final, and Heap_Control::start.

RTEMS_INLINE_ROUTINE bool _Heap_Is_prev_used ( Heap_Block * the_block )

This function returns TRUE if the previous block of the_block is in use, and FALSE otherwise.

Parameters:

[in] the_block is the block to operate upon.

Returns:: This method returns TRUE if the previous block is used and FALSE if the previous block is free.

References HEAP_PREV_USED, and Heap_Block_struct::size.

RTEMS_INLINE_ROUTINE Heap_Block* _Heap_Last ( Heap_Control * the_heap )

Return the last free block of the specified heap.

Parameters:

[in] the_heap points to the heap being operated upon

Returns:: This method returns a pointer to the last block on the free list.

References _Heap_Tail(), and Heap_Block_struct::prev.

Heap_Resize_status _Heap_Resize_block	(	Heap_Control *	the_heap,
		void *	starting_address,
		size_t	size,
		uint32_t *	old_mem_size,
		uint32_t *	avail_mem_size
	)

This function tries to resize in place the block that is pointed to by the starting_address to the new size.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	starting_address	is the starting address of the user block to be resized
`[in]`	size	is the new size
`[in]`	old_mem_size	points to a user area to return the size of the user memory area of the block before resizing.
`[in]`	avail_mem_size	points to a user area to return the size of the user memory area of the free block that has been enlarged or created due to resizing, 0 if none.

Returns:

HEAP_RESIZE_SUCCESSFUL if successfully able to resize the block, HEAP_RESIZE_UNSATISFIED if the block can't be resized in place, HEAP_RESIZE_FATAL_ERROR if failure

*old_mem_size filled in with the size of the user memory area of the block before resizing.

*avail_mem_size filled in with the size of the user memory area of the free block that has been enlarged or created due to resizing, 0 if none.

bool _Heap_Size_of_user_area	(	Heap_Control *	the_heap,
		void *	starting_address,
		size_t *	size
	)

This function sets *size to the size of the block of user memory which begins at starting_address. The size returned in *size could be greater than the size requested for allocation. Returns TRUE if the starting_address is in the heap, and FALSE otherwise.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	starting_address	is the starting address of the user block to obtain the size of
`[in]`	size	points to a user area to return the size in

Returns:: TRUE if successfully able to determine the size, FALSE otherwise
*size filled in with the size of the user area for this block

RTEMS_INLINE_ROUTINE void _Heap_Start_of_block	(	Heap_Control *	the_heap,
		void *	base,
		Heap_Block **	the_block
	)

Fill *the_block with the address of the beginning of the block given pointer to the user accessible area base.

Parameters:

`[in]`	the_heap	points to the heap being operated upon
`[in]`	base	points to the user area in the block.
`[in]`	the_block	will be the address of the heap block.

Returns:: This method returns a pointer to the heap block based upon the given heap and user pointer.

References _H_p2u, _Heap_Align_down_uptr(), HEAP_BLOCK_USER_OFFSET, and Heap_Control::page_size.

RTEMS_INLINE_ROUTINE Heap_Block* _Heap_Tail ( Heap_Control * the_heap )

This function returns the tail of the specified heap.

Parameters:

[in] the_heap points to the heap being operated upon

Returns:: This method returns a pointer to the dummy tail of the heap free list.

References Heap_Control::free_list.

Referenced by _Heap_Last().

RTEMS_INLINE_ROUTINE void* _Heap_User_area ( Heap_Block * the_block )

This function returns the starting address of the portion of the_block which the user may access.

Parameters:

[in] the_block is the heap block to find the user area of.

Returns:: This method returns a pointer to the start of the user area in the block.

References _Addresses_Add_offset(), and HEAP_BLOCK_USER_OFFSET.

bool _Heap_Walk	(	Heap_Control *	the_heap,
		int	source,
		bool	do_dump
	)

This routine walks the heap to verify its integrity.

Parameters:

`[in]`	the_heap	is the heap to operate upon
`[in]`	source	is a user specified integer which may be used to indicate where in the application this was invoked from
`[in]`	do_dump	is set to TRUE if errors should be printed

Returns:: TRUE if the test passed fine, FALSE otherwise.

Referenced by _Thread_Disable_dispatch().

Heap Handler

Data Structures

Defines

Typedefs

Enumerations

Functions

Detailed Description

Define Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation