Heap

First-fit heap allocator over a caller-provided memory region. More...

Data Structures
struct	HeapLockImpl
	Locking of a heap. More...
struct	Heap
	Heap state. More...

Typedefs
typedef void(*	LockFunction) (void *)
	Lock function of a heap, called with HeapLockImpl::lock_context.
typedef void(*	UnlockFunction) (void *)
	Unlock function of a heap, called with HeapLockImpl::lock_context.
typedef void(*	DoubleFreeHandler) (void *)
	Handler of a double free, called with the pointer being freed.
typedef void(*	CorruptionHandler) (void *)
	Handler of a corrupted heap, called with the block where corruption was found.

Functions
void	heap_init (Heap *const heap, void *start, void *end, bool fuzz_on_free)
	Initialize a heap over a memory region, zeroing it.
void	heap_set_lock_impl (Heap *heap, HeapLockImpl lock_impl)
	Make a heap thread safe with a lock.
void	heap_set_double_free_handler (Heap *heap, DoubleFreeHandler double_free_handler)
	Set the function called on a double free, instead of asserting.
void	heap_set_corruption_handler (Heap *heap, CorruptionHandler corruption_handler)
	Set the function called when corruption is detected, instead of asserting.
void *	heap_malloc (Heap *const heap, unsigned long nbytes, uintptr_t client_pc)
	Allocate memory.
void	heap_free (Heap *const heap, void *ptr, uintptr_t client_pc)
	Free memory, merging it with adjacent free blocks.
void *	heap_realloc (Heap *const heap, void *ptr, unsigned long nbytes, uintptr_t client_pc)
	Reallocate memory.
void *	heap_zalloc (Heap *const heap, size_t size, uintptr_t client_pc)
	Allocate zeroed memory.
void *	heap_calloc (Heap *const heap, size_t count, size_t size, uintptr_t client_pc)
	Allocate a zeroed array.
bool	heap_contains_address (Heap *const heap, void *ptr)
	Check whether an address is within a heap.
bool	heap_is_allocated (Heap *const heap, void *ptr)
	Check whether a pointer is an allocated block of a heap.
size_t	heap_size (const Heap *heap)
	Get the size of a heap.
uint32_t	heap_get_minimum_headroom (Heap *heap)
	Get the smallest amount of free memory the heap has had.
void	heap_calc_totals (Heap *const heap, unsigned int *used, unsigned int *free, unsigned int *max_free)
	Calculate the current memory usage of a heap, for debugging.
void	heap_dump_malloc_instrumentation_to_dbgserial (Heap *heap)
	Dump every block and the heap totals to the debug serial port.

Detailed Description

First-fit heap allocator over a caller-provided memory region.

Small allocations are taken from the start of the region and large ones (256 bytes or more) from the end, to limit fragmentation. Each block carries a small header. The heap is not thread safe unless given a lock with heap_set_lock_impl().

static uint8_t s_region[4096];
static Heap s_heap;
 
heap_init(&s_heap, s_region, s_region + sizeof(s_region), false);
void *p = heap_malloc(&s_heap, 100, (uintptr_t)__builtin_return_address(0));
heap_free(&s_heap, p, 0);

---

Data Structure Documentation

HeapLockImpl

struct HeapLockImpl

Locking of a heap.

Data Fields
void *	lock_context	Context passed to both functions.
LockFunction	lock_function	Takes the lock.
UnlockFunction	unlock_function	Releases the lock.

Heap

struct Heap

Heap state.

Data Fields
HeapInfo_t *	begin	First block of the heap.
void *	corrupt_block	Corrupted block found while locked, reported once unlocked.
CorruptionHandler	corruption_handler	Corruption handler, NULL to assert.
unsigned int	current_size	Number of allocated bytes, including block headers.
DoubleFreeHandler	double_free_handler	Double free handler, NULL to assert.
HeapInfo_t *	end	End of the heap, right after the last block.
bool	fuzz_on_free	Fill freed memory with a junk pattern (non-release builds).
unsigned int	high_water_mark	Peak of current_size.
HeapLockImpl	lock_impl	Locking.

Typedef Documentation

CorruptionHandler

typedef void(* CorruptionHandler) (void *)

Handler of a corrupted heap, called with the block where corruption was found.

Called after the heap lock is released.

DoubleFreeHandler

typedef void(* DoubleFreeHandler) (void *)

Handler of a double free, called with the pointer being freed.

LockFunction

typedef void(* LockFunction) (void *)

Lock function of a heap, called with HeapLockImpl::lock_context.

UnlockFunction

typedef void(* UnlockFunction) (void *)

Unlock function of a heap, called with HeapLockImpl::lock_context.

Function Documentation

heap_calc_totals()

void heap_calc_totals	(	Heap *const	heap,
		unsigned int *	used,
		unsigned int *	free,
		unsigned int *	max_free
	)

Calculate the current memory usage of a heap, for debugging.

Parameters

	heap	Heap.
[out]	used	Bytes allocated.
[out]	free	Bytes free.
[out]	max_free	Size of the largest free block.

heap_calloc()

void * heap_calloc	(	Heap *const	heap,
		size_t	count,
		size_t	size,
		uintptr_t	client_pc
	)

Allocate a zeroed array.

The multiplication is not checked for overflow.

Parameters

heap	Heap.
count	Number of elements.
size	Size of an element in bytes.
client_pc	Caller address, for instrumentation.

Returns

Allocated memory, or NULL.

heap_contains_address()

bool heap_contains_address	(	Heap *const	heap,
		void *	ptr
	)

Check whether an address is within a heap.

Parameters

heap	Heap.
ptr	Address.

Returns

true if ptr is in the heap region.

heap_dump_malloc_instrumentation_to_dbgserial()

void heap_dump_malloc_instrumentation_to_dbgserial

(

Heap *

heap

)

Dump every block and the heap totals to the debug serial port.

Only available with CONFIG_MALLOC_INSTRUMENTATION.

Parameters

heap

Heap.

heap_free()

void heap_free	(	Heap *const	heap,
		void *	ptr,
		uintptr_t	client_pc
	)

Free memory, merging it with adjacent free blocks.

Parameters

heap	Heap, initialized.
ptr	Memory allocated from heap, or NULL (no-op).
client_pc	Caller address, for instrumentation.

heap_get_minimum_headroom()

uint32_t heap_get_minimum_headroom

(

Heap *

heap

)

Get the smallest amount of free memory the heap has had.

Parameters

heap

Heap.

Returns

Heap size minus the high water mark, in bytes.

heap_init()

void heap_init	(	Heap *const	heap,
		void *	start,
		void *	end,
		bool	fuzz_on_free
	)

Initialize a heap over a memory region, zeroing it.

The usable size is capped to about 32767 alignment units (128 KiB with 4-byte units).

Parameters

[out]	heap	Heap.
	start	Start of the region, rounded up to the alignment.
	end	End of the region, exclusive, rounded down to the alignment.
	fuzz_on_free	Fill freed memory with a junk pattern to catch use after free sooner.

heap_is_allocated()

bool heap_is_allocated	(	Heap *const	heap,
		void *	ptr
	)

Check whether a pointer is an allocated block of a heap.

Parameters

heap	Heap.
ptr	Pointer.

Returns

true if ptr was returned by an allocation and not freed.

heap_malloc()

void * heap_malloc	(	Heap *const	heap,
		unsigned long	nbytes,
		uintptr_t	client_pc
	)

Allocate memory.

Parameters

heap	Heap, initialized.
nbytes	Number of bytes, greater than 0.
client_pc	Caller address, recorded with CONFIG_MALLOC_INSTRUMENTATION.

Returns

Allocated memory, or NULL if there is not enough contiguous free space.

heap_realloc()

void * heap_realloc	(	Heap *const	heap,
		void *	ptr,
		unsigned long	nbytes,
		uintptr_t	client_pc
	)

Reallocate memory.

Always allocates a new block, copies as much of the old data as fits, then frees ptr.

Parameters

heap	Heap.
ptr	Memory to reallocate, or NULL.
nbytes	New size in bytes.
client_pc	Caller address, recorded with CONFIG_MALLOC_INSTRUMENTATION.

Returns

New memory, or NULL on failure (ptr is then left untouched).

heap_set_corruption_handler()

void heap_set_corruption_handler	(	Heap *	heap,
		CorruptionHandler	corruption_handler
	)

Set the function called when corruption is detected, instead of asserting.

Parameters

heap	Heap.
corruption_handler	Handler.

heap_set_double_free_handler()

void heap_set_double_free_handler	(	Heap *	heap,
		DoubleFreeHandler	double_free_handler
	)

Set the function called on a double free, instead of asserting.

Parameters

heap	Heap.
double_free_handler	Handler; the free is then ignored.

heap_set_lock_impl()

void heap_set_lock_impl	(	Heap *	heap,
		HeapLockImpl	lock_impl
	)

Make a heap thread safe with a lock.

Parameters

heap	Heap.
lock_impl	Lock functions.

heap_size()

size_t heap_size

(

const Heap *

heap

)

Get the size of a heap.

Parameters

heap

Heap.

Returns

Size in bytes.

heap_zalloc()

void * heap_zalloc	(	Heap *const	heap,
		size_t	size,
		uintptr_t	client_pc
	)

Allocate zeroed memory.

Parameters

heap	Heap.
size	Number of bytes.
client_pc	Caller address, for instrumentation.

Returns

Allocated memory, or NULL.