Memory Pools

Note

The k_mem_pool data structure defined here has been deprecated in current Zephyr code. It still exists for applications which require the specific memory allocation and alignment patterns detailed below, but the default heap implementation (including the default backend to the k_mem_pool APIs) is now a k_heap allocator, which is a better choice for general purpose code.

A memory pool is a kernel object that allows memory blocks to be dynamically allocated from a designated memory region. The memory blocks in a memory pool can be of any size, thereby reducing the amount of wasted memory when an application needs to allocate storage for data structures of different sizes. The memory pool uses a “buddy memory allocation” algorithm to efficiently partition larger blocks into smaller ones, allowing blocks of different sizes to be allocated and released efficiently while limiting memory fragmentation concerns.

Concepts

Any number of memory pools can be defined. Each memory pool is referenced by its memory address.

A memory pool has the following key properties:

  • A minimum block size, measured in bytes. It must be at least 4X bytes long, where X is greater than 0.

  • A maximum block size, measured in bytes. This should be a power of 4 times larger than the minimum block size. That is, “maximum block size” must equal “minimum block size” times 4^Y, where Y is greater than or equal to zero.

  • The number of maximum-size blocks initially available. This must be greater than zero.

  • A buffer that provides the memory for the memory pool’s blocks. This must be at least “maximum block size” times “number of maximum-size blocks” bytes long.

The memory pool’s buffer must be aligned to an N-byte boundary, where N is a power of 2 larger than 2 (i.e. 4, 8, 16, …). To ensure that all memory blocks in the buffer are similarly aligned to this boundary, the minimum block size must also be a multiple of N.

A thread that needs to use a memory block simply allocates it from a memory pool. Following a successful allocation, the data field of the block descriptor supplied by the thread indicates the starting address of the memory block. When the thread is finished with a memory block, it must release the block back to the memory pool so the block can be reused.

If a block of the desired size is unavailable, a thread can optionally wait for one to become available. Any number of threads may wait on a memory pool simultaneously; when a suitable memory block becomes available, it is given to the highest-priority thread that has waited the longest.

Unlike a heap, more than one memory pool can be defined, if needed. For example, different applications can utilize different memory pools; this can help prevent one application from hijacking resources to allocate all of the available blocks.

Internal Operation

A memory pool’s buffer is an array of maximum-size blocks, with no wasted space between the blocks. Each of these “level 0” blocks is a quad-block that can be partitioned into four smaller “level 1” blocks of equal size, if needed. Likewise, each level 1 block is itself a quad-block that can be partitioned into four smaller “level 2” blocks in a similar way, and so on. Thus, memory pool blocks can be recursively partitioned into quarters until blocks of the minimum size are obtained, at which point no further partitioning can occur.

A memory pool keeps track of how its buffer space has been partitioned using an array of block set data structures. There is one block set for each partitioning level supported by the pool, or (to put it another way) for each block size. A block set keeps track of all free blocks of its associated size using an array of quad-block status data structures.

When an application issues a request for a memory block, the memory pool first determines the size of the smallest block that will satisfy the request, and examines the corresponding block set. If the block set contains a free block, the block is marked as used and the allocation process is complete. If the block set does not contain a free block, the memory pool attempts to create one automatically by splitting a free block of a larger size or by merging free blocks of smaller sizes; if a suitable block can’t be created, the allocation request fails.

The memory pool’s merging algorithm cannot combine adjacent free blocks of different sizes, nor can it merge adjacent free blocks of the same size if they belong to different parent quad-blocks. As a consequence, memory fragmentation issues can still be encountered when using a memory pool.

When an application releases a previously allocated memory block it is combined synchronously with its three “partner” blocks if possible, and recursively so up through the levels. This is done in constant time, and quickly, so no manual “defragmentation” management is needed.

Implementation

Defining a Memory Pool

A memory pool is defined using a variable of type k_mem_pool. However, since a memory pool also requires a number of variable-size data structures to represent its block sets and the status of its quad-blocks, the kernel does not support the runtime definition of a memory pool. A memory pool can only be defined and initialized at compile time by calling K_MEM_POOL_DEFINE.

The following code defines and initializes a memory pool that has 3 blocks of 4096 bytes each, which can be partitioned into blocks as small as 64 bytes and is aligned to a 4-byte boundary. (That is, the memory pool supports block sizes of 4096, 1024, 256, and 64 bytes.) Observe that the macro defines all of the memory pool data structures, as well as its buffer.

K_MEM_POOL_DEFINE(my_pool, 64, 4096, 3, 4);

Allocating a Memory Block

A memory block is allocated by calling k_mem_pool_alloc().

The following code builds on the example above, and waits up to 100 milliseconds for a 200 byte memory block to become available, then fills it with zeroes. A warning is issued if a suitable block is not obtained.

Note that the application will actually receive a 256 byte memory block, since that is the closest matching size supported by the memory pool.

struct k_mem_block block;

if (k_mem_pool_alloc(&my_pool, &block, 200, 100) == 0)) {
    memset(block.data, 0, 200);
    ...
} else {
    printf("Memory allocation time-out");
}

Memory blocks may also be allocated with malloc()-like semantics using k_mem_pool_malloc(). Such allocations must be freed with k_free().

Releasing a Memory Block

A memory block is released by calling either k_mem_pool_free() or k_free(), depending on how it was allocated.

The following code builds on the example above, and allocates a 75 byte memory block, then releases it once it is no longer needed. (A 256 byte memory block is actually used to satisfy the request.)

struct k_mem_block block;

k_mem_pool_alloc(&my_pool, &block, 75, K_FOREVER);
... /* use memory block */
k_mem_pool_free(&block);

Thread Resource Pools

Certain kernel APIs may need to make heap allocations on behalf of the calling thread. For example, some initialization APIs for objects like pipes and message queues may need to allocate a private kernel-side buffer, or objects like queues may temporarily allocate kernel data structures as items are placed in the queue.

Such memory allocations are drawn from memory pools that are assigned to a thread. By default, a thread in the system has no resource pool and any allocations made on its behalf will fail. The supervisor-mode only k_thread_resource_pool_assign() will associate any implicit kernel-side allocations to the target thread with the provided memory pool, and any children of that thread will inherit this assignment.

If a system heap exists, threads may alternatively have their resources drawn from it using the k_thread_system_pool_assign() API.

Suggested Uses

Use a memory pool to allocate memory in variable-size blocks.

Use memory pool blocks when sending large amounts of data from one thread to another, to avoid unnecessary copying of the data.

API Reference

group mem_pool_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.

Parameters

  • name: Symbol name for the struct k_heap object

  • bytes: Size of memory region, in bytes

K_MEM_POOL_DEFINE(name, minsz, maxsz, nmax, align)

Statically define and initialize a memory pool.

The memory pool’s buffer contains n_max blocks that are max_size bytes long. The memory pool allows blocks to be repeatedly partitioned into quarters, down to blocks of min_size bytes long. The buffer is aligned to a align -byte boundary.

If the pool is to be accessed outside the module where it is defined, it can be declared via

extern struct k_mem_pool <name>;
Note

When CONFIG_MEM_POOL_HEAP_BACKEND is enabled, the k_mem_pool API is implemented on top of a k_heap, which is a more general purpose allocator which does not make the same promises about splitting or alignment detailed above. Blocks will be aligned only to the 8 byte chunk stride of the underlying heap and may point anywhere within the heap; they are not split into four as described.

Parameters

  • name: Name of the memory pool.

  • minsz: Size of the smallest blocks in the pool (in bytes).

  • maxsz: Size of the largest blocks in the pool (in bytes).

  • nmax: Number of maximum sized blocks in the pool.

  • align: Alignment of the pool’s buffer (power of 2).

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_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.

Note

Can be called by ISRs, but timeout must be set to K_NO_WAIT.

Return

A pointer to valid heap memory, or NULL

Parameters

  • h: Heap from which to allocate

  • bytes: Desired size of block to allocate

  • timeout: How long to wait, or K_NO_WAIT

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

int k_mem_pool_alloc(struct k_mem_pool *pool, struct k_mem_block *block, size_t size, k_timeout_t timeout)

Allocate memory from a memory pool.

This routine allocates a memory block from a memory pool.

Note

Can be called by ISRs, but timeout must be set to K_NO_WAIT.

Parameters

  • pool: Address of the memory pool.

  • block: Pointer to block descriptor for the allocated memory.

  • size: Amount of memory to allocate (in bytes).

  • timeout: Waiting period to wait for operation to complete. Use K_NO_WAIT to return without waiting, or K_FOREVER to wait as long as necessary.

Return Value

  • 0: Memory allocated. The data field of the block descriptor is set to the starting address of the memory block.

  • -ENOMEM: Returned without waiting.

  • -EAGAIN: Waiting period timed out.

void *k_mem_pool_malloc(struct k_mem_pool *pool, size_t size)

Allocate memory from a memory pool with malloc() semantics.

Such memory must be released using k_free().

Return

Address of the allocated memory if successful, otherwise NULL

Parameters

  • pool: Address of the memory pool.

  • size: Amount of memory to allocate (in bytes).

void k_mem_pool_free(struct k_mem_block *block)

Free memory allocated from a memory pool.

This routine releases a previously allocated memory block back to its memory pool.

Return

N/A

Parameters

  • block: Pointer to block descriptor for the allocated memory.

void k_mem_pool_free_id(struct k_mem_block_id *id)

Free memory allocated from a memory pool.

This routine releases a previously allocated memory block back to its memory pool

Return

N/A

Parameters

  • id: Memory block identifier.

struct k_heap
#include <kernel.h>
struct k_mem_block_id
#include <mempool_heap.h>
struct k_mem_block
#include <mempool_heap.h>