Memory Heaps

Zephyr provides a collection of utilities that allow threads to dynamically allocate memory.

Synchronized Heap Allocator

Creating a Heap

The simplest way to define a heap is statically, with the K_HEAP_DEFINE macro. This creates a static k_heap variable with a given name that manages a memory region of the specified size.

Heaps can also be created to manage arbitrary regions of application-controlled memory using k_heap_init().

Allocating Memory

Memory can be allocated from a heap using k_heap_alloc(), passing it the address of the heap object and the number of bytes desired. This functions similarly to standard C malloc(), returning a NULL pointer on an allocation failure.

The heap supports blocking operation, allowing threads to go to sleep until memory is available. The final argument is a k_timeout_t timeout value indicating how long the thread may sleep before returning, or else one of the constant timeout values K_NO_WAIT or K_FOREVER.

Releasing Memory

Memory allocated with k_heap_alloc() must be released using k_heap_free(). Similar to standard C free(), the pointer provided must be either a NULL value or a pointer previously returned by k_heap_alloc() for the same heap. Freeing a NULL value is defined to have no effect.

Low Level Heap Allocator

The underlying implementation of the k_heap abstraction is provided a data structure named sys_heap. This implements exactly the same allocation semantics, but provides no kernel synchronization tools. It is available for applications that want to manage their own blocks of memory in contexts (for example, userspace) where synchronization is unavailable or more complicated. Unlike k_heap, all calls to any sys_heap functions on a single heap must be serialized by the caller. Simultaneous use from separate threads is disallowed.

Implementation

Internally, the sys_heap memory block is partitioned into “chunks” of 8 bytes. All allocations are made out of a contiguous region of chunks. The first chunk of every allocation or unused block is prefixed by a chunk header that stores the length of the chunk, the length of the next lower (“left”) chunk in physical memory, a bit indicating whether the chunk is in use, and chunk-indexed link pointers to the previous and next chunk in a “free list” to which unused chunks are added.

The heap code takes reasonable care to avoid fragmentation. Free block lists are stored in “buckets” by their size, each bucket storing blocks within one power of two (i.e. a bucket for blocks of 3-4 chunks, another for 5-8, 9-16, etc…) this allows new allocations to be made from the smallest/most-fragmented blocks available. Also, as allocations are freed and added to the heap, they are automatically combined with adjacent free blocks to prevent fragmentation.

All metadata is stored at the beginning of the contiguous block of heap memory, including the variable-length list of bucket list heads (which depend on heap size). The only external memory required is the sys_heap structure itself.

The sys_heap functions are unsynchronized. Care must be taken by any users to prevent concurrent access. Only one context may be inside one of the API functions at a time.

The heap code takes care to present high performance and reliable latency. All sys_heap API functions are guaranteed to complete within constant time. On typical architectures, they will all complete within 1-200 cycles. One complexity is that the search of the minimum bucket size for an allocation (the set of free blocks that “might fit”) has a compile-time upper bound of iterations to prevent unbounded list searches, at the expense of some fragmentation resistance. This CONFIG_SYS_HEAP_ALLOC_LOOPS value may be chosen by the user at build time, and defaults to a value of 3.

Multi-Heap Wrapper Utility

The sys_heap utility requires that all managed memory be in a single contiguous block. It is common for complicated microcontroller applications to have more complicated memory setups that they still want to manage dynamically as a “heap”. For example, the memory might exist as separate discontiguous regions, different areas may have different cache, performance or power behavior, peripheral devices may only be able to perform DMA to certain regions, etc…

For those situations, Zephyr provides a sys_multi_heap utility. Effectively this is a simple wrapper around a set of one or more sys_heap objects. It should be initialized after its child heaps via sys_multi_heap_init(), after which each heap can be added to the managed set via sys_multi_heap_add_heap(). No destruction utility is provided; just as for sys_heap, applications that want to destroy a multi heap should simply ensure all allocated blocks are freed (or at least will never be used again) and repurpose the underlying memory for another usage.

It has a single pair of allocation entry points, sys_multi_heap_alloc() and sys_multi_heap_aligned_alloc(). These behave identically to the sys_heap functions with similar names, except that they also accept an opaque “configuration” parameter. This pointer is uninspected by the multi heap code itself; instead it is passed to a callback function provided at initialization time. This application-provided callback is responsible for doing the underlying allocation from one of the managed heaps, and may use the configuration parameter in any way it likes to make that decision.

When unused, a multi heap may be freed via sys_multi_heap_free(). The application does not need to pass a configuration parameter. Memory allocated from any of the managed sys_heap objects may be freed with in the same way.

System Heap

The system heap is a predefined memory allocator that allows threads to dynamically allocate memory from a common memory region in a malloc()-like manner.

Only a single system heap is defined. Unlike other heaps or memory pools, the system heap cannot be directly referenced using its memory address.

The size of the system heap is configurable to arbitrary sizes, subject to space availability.

A thread can dynamically allocate a chunk of heap memory by calling k_malloc(). The address of the allocated chunk is guaranteed to be aligned on a multiple of pointer sizes. If a suitable chunk of heap memory cannot be found NULL is returned.

When the thread is finished with a chunk of heap memory it can release the chunk back to the system heap by calling k_free().

Defining the Heap Memory Pool

The size of the heap memory pool is specified using the CONFIG_HEAP_MEM_POOL_SIZE configuration option.

By default, the heap memory pool size is zero bytes. This value instructs the kernel not to define the heap memory pool object. The maximum size is limited by the amount of available memory in the system. The project build will fail in the link stage if the size specified can not be supported.

Allocating Memory

A chunk of heap memory is allocated by calling k_malloc().

The following code allocates a 200 byte chunk of heap memory, then fills it with zeros. A warning is issued if a suitable chunk is not obtained.

char *mem_ptr;

mem_ptr = k_malloc(200);
if (mem_ptr != NULL)) {
    memset(mem_ptr, 0, 200);
    ...
} else {
    printf("Memory not allocated");
}

Releasing Memory

A chunk of heap memory is released by calling k_free().

The following code allocates a 75 byte chunk of memory, then releases it once it is no longer needed.

char *mem_ptr;

mem_ptr = k_malloc(75);
... /* use memory block */
k_free(mem_ptr);

Suggested Uses

Use the heap memory pool to dynamically allocate memory in a malloc()-like manner.

Configuration Options

Related configuration options:

• CONFIG_HEAP_MEM_POOL_SIZE

API Reference

group heap_apis

Defines

K_HEAP_DEFINE(name, bytes)

Define a static k_heap.

This macro defines and initializes a static memory region and k_heap of the requested size. After kernel start, &name can be used as if k_heap_init() had been called.

Note that this macro enforces a minimum size on the memory region to accommodate metadata requirements. Very small heaps will be padded to fit.

Parameters

• name – Symbol name for the struct k_heap object

• bytes – Size of memory region, in bytes

K_HEAP_DEFINE_NOCACHE(name, bytes)

Define a static k_heap in uncached memory.

This macro defines and initializes a static memory region and k_heap of the requested size in uncached memory. After kernel start, &name can be used as if k_heap_init() had been called.

Note that this macro enforces a minimum size on the memory region to accommodate metadata requirements. Very small heaps will be padded to fit.

Parameters

• name – Symbol name for the struct k_heap object

• bytes – Size of memory region, in bytes

Functions

void k_heap_init(struct k_heap *h, void *mem, size_t bytes)

Initialize a k_heap.

This constructs a synchronized k_heap object over a memory region specified by the user. Note that while any alignment and size can be passed as valid parameters, internal alignment restrictions inside the inner sys_heap mean that not all bytes may be usable as allocated memory.

Parameters

• h – Heap struct to initialize

• mem – Pointer to memory.

• bytes – Size of memory region, in bytes

void *k_heap_aligned_alloc(struct k_heap *h, size_t align, size_t bytes, k_timeout_t timeout)

Allocate aligned memory from a k_heap.

Behaves in all ways like k_heap_alloc(), except that the returned memory (if available) will have a starting address in memory which is a multiple of the specified power-of-two alignment value in bytes. The resulting memory can be returned to the heap using k_heap_free().

Function properties (list may not be complete)

isr-ok

Note

timeout must be set to K_NO_WAIT if called from ISR.

Note

When CONFIG_MULTITHREADING=n any timeout is treated as K_NO_WAIT.

Parameters

• h – Heap from which to allocate

• align – Alignment in bytes, must be a power of two

• bytes – Number of bytes requested

• timeout – How long to wait, or K_NO_WAIT

Returns

Pointer to memory the caller can now use

void *k_heap_alloc(struct k_heap *h, size_t bytes, k_timeout_t timeout)

Allocate memory from a k_heap.

Allocates and returns a memory buffer from the memory region owned by the heap. If no memory is available immediately, the call will block for the specified timeout (constructed via the standard timeout API, or K_NO_WAIT or K_FOREVER) waiting for memory to be freed. If the allocation cannot be performed by the expiration of the timeout, NULL will be returned. Allocated memory is aligned on a multiple of pointer sizes.

Function properties (list may not be complete)

isr-ok

Note

timeout must be set to K_NO_WAIT if called from ISR.

Note

When CONFIG_MULTITHREADING=n any timeout is treated as K_NO_WAIT.

Parameters

• h – Heap from which to allocate

• bytes – Desired size of block to allocate

• timeout – How long to wait, or K_NO_WAIT

Returns

A pointer to valid heap memory, or NULL

void k_heap_free(struct k_heap *h, void *mem)

Free memory allocated by k_heap_alloc()

Returns the specified memory block, which must have been returned from k_heap_alloc(), to the heap for use by other callers. Passing a NULL block is legal, and has no effect.

Parameters

• h – Heap to which to return the memory

• mem – A valid memory block, or NULL

void *k_aligned_alloc(size_t align, size_t size)

Allocate memory from the heap with a specified alignment.

This routine provides semantics similar to aligned_alloc(); memory is allocated from the heap with a specified alignment. However, one minor difference is that k_aligned_alloc() accepts any non-zero size, whereas aligned_alloc() only accepts a size that is an integral multiple of align.

Above, aligned_alloc() refers to: C11 standard (ISO/IEC 9899:2011): 7.22.3.1 The aligned_alloc function (p: 347-348)

Parameters

• align – Alignment of memory requested (in bytes).

• size – Amount of memory requested (in bytes).

Returns

Address of the allocated memory if successful; otherwise NULL.

void *k_malloc(size_t size)

Allocate memory from the heap.

This routine provides traditional malloc() semantics. Memory is allocated from the heap memory pool. Allocated memory is aligned on a multiple of pointer sizes.

Parameters

• size – Amount of memory requested (in bytes).

Returns

Address of the allocated memory if successful; otherwise NULL.

void k_free(void *ptr)

Free memory allocated from heap.

This routine provides traditional free() semantics. The memory being returned must have been allocated from the heap memory pool.

If ptr is NULL, no operation is performed.

Parameters

• ptr – Pointer to previously allocated memory.

void *k_calloc(size_t nmemb, size_t size)

Allocate memory from heap, array style.

This routine provides traditional calloc() semantics. Memory is allocated from the heap memory pool and zeroed.

Parameters

• nmemb – Number of elements in the requested array

• size – Size of each array element (in bytes).

Returns

Address of the allocated memory if successful; otherwise NULL.

struct k_heap

#include <kernel.h>

Heap listener

group heap_listener_apis

Defines

HEAP_ID_FROM_POINTER(heap_pointer)

Construct heap identifier from heap pointer.

Construct a heap identifier from a pointer to the heap object, such as sys_heap.

Parameters

• heap_pointer – Pointer to the heap object

HEAP_ID_LIBC

Libc heap identifier.

Identifier of the global libc heap.

HEAP_LISTENER_ALLOC_DEFINE(name, _heap_id, _alloc_cb)

Define heap event listener node for allocation event.

Sample usage:

void on_heap_alloc(uintptr_t heap_id, void *mem, size_t bytes)
{
  LOG_INF("Memory allocated at %p, size %ld", heap_id, mem, bytes);
}

HEAP_LISTENER_ALLOC_DEFINE(my_listener, HEAP_ID_LIBC, on_heap_alloc);

Parameters

• name – Name of the heap event listener object

• _heap_id – Identifier of the heap to be listened

• _alloc_cb – Function to be called for allocation event

HEAP_LISTENER_FREE_DEFINE(name, _heap_id, _free_cb)

Define heap event listener node for free event.

Sample usage:

void on_heap_free(uintptr_t heap_id, void *mem, size_t bytes)
{
  LOG_INF("Memory freed at %p, size %ld", heap_id, mem, bytes);
}

HEAP_LISTENER_FREE_DEFINE(my_listener, HEAP_ID_LIBC, on_heap_free);

Parameters

• name – Name of the heap event listener object

• _heap_id – Identifier of the heap to be listened

• _free_cb – Function to be called for free event

HEAP_LISTENER_RESIZE_DEFINE(name, _heap_id, _resize_cb)

Define heap event listener node for resize event.

Sample usage:

void on_heap_resized(uintptr_t heap_id, void *old_heap_end, void *new_heap_end)
{
  LOG_INF("Libc heap end moved from %p to %p", old_heap_end, new_heap_end);
}

HEAP_LISTENER_RESIZE_DEFINE(my_listener, HEAP_ID_LIBC, on_heap_resized);

Parameters

• name – Name of the heap event listener object

• _heap_id – Identifier of the heap to be listened

• _resize_cb – Function to be called when the listened heap is resized

Typedefs

typedef void (*heap_listener_resize_cb_t)(uintptr_t heap_id, void *old_heap_end, void *new_heap_end)

Callback used when heap is resized.

Note

Minimal C library does not emit this event.

Param heap_id

Identifier of heap being resized

Param old_heap_end

Pointer to end of heap before resize

Param new_heap_end

Pointer to end of heap after resize

typedef void (*heap_listener_alloc_cb_t)(uintptr_t heap_id, void *mem, size_t bytes)

Callback used when there is heap allocation.

Note

Heaps managed by libraries outside of code in Zephyr main code repository may not emit this event.

Note

The number of bytes allocated may not match exactly to the request to the allocation function. Internal mechanism of the heap may allocate more than requested.

Param heap_id

Heap identifier

Param mem

Pointer to the allocated memory

Param bytes

Size of allocated memory

typedef void (*heap_listener_free_cb_t)(uintptr_t heap_id, void *mem, size_t bytes)

Callback used when memory is freed from heap.

Note

Heaps managed by libraries outside of code in Zephyr main code repository may not emit this event.

Note

The number of bytes freed may not match exactly to the request to the allocation function. Internal mechanism of the heap dictates how memory is allocated or freed.

Param heap_id

Heap identifier

Param mem

Pointer to the freed memory

Param bytes

Size of freed memory

Enums

enum heap_event_types

Values:

enumerator HEAP_EVT_UNKNOWN = 0

enumerator HEAP_RESIZE

enumerator HEAP_ALLOC

enumerator HEAP_FREE

enumerator HEAP_REALLOC

enumerator HEAP_MAX_EVENTS

Functions

void heap_listener_register(struct heap_listener *listener)

Register heap event listener.

Add the listener to the global list of heap listeners that can be notified by different heap implementations upon certain events related to the heap usage.

Parameters

• listener – Pointer to the heap_listener object

void heap_listener_unregister(struct heap_listener *listener)

Unregister heap event listener.

Remove the listener from the global list of heap listeners that can be notified by different heap implementations upon certain events related to the heap usage.

Parameters

• listener – Pointer to the heap_listener object

void heap_listener_notify_alloc(uintptr_t heap_id, void *mem, size_t bytes)

Notify listeners of heap allocation event.

Notify registered heap event listeners with matching heap identifier that an allocation has been done on heap

Parameters

• heap_id – Heap identifier

• mem – Pointer to the allocated memory

• bytes – Size of allocated memory

void heap_listener_notify_free(uintptr_t heap_id, void *mem, size_t bytes)

Notify listeners of heap free event.

Notify registered heap event listeners with matching heap identifier that memory is freed on heap

Parameters

• heap_id – Heap identifier

• mem – Pointer to the freed memory

• bytes – Size of freed memory

void heap_listener_notify_resize(uintptr_t heap_id, void *old_heap_end, void *new_heap_end)

Notify listeners of heap resize event.

Notify registered heap event listeners with matching heap identifier that the heap has been resized.

Parameters

• heap_id – Heap identifier

• old_heap_end – Address of the heap end before the change

• new_heap_end – Address of the heap end after the change

struct heap_listener

#include <heap_listener.h>

Public Members

sys_snode_t node

Singly linked list node

uintptr_t heap_id

Identifier of the heap whose events are listened.

It can be a heap pointer, if the heap is represented as an object, or 0 in the case of the global libc heap.

enum heap_event_types event

The heap event to be notified.