Hello everyone, welcome to Lixin Embedded.
Recently, while optimizing an industrial control project, I encountered the age-old problem of dynamic memory allocation once again.
First, let’s talk about dynamic memory allocation. When coding on a PC, using new to create an object and delete to remove it is quite normal. Not enough memory? Just add more RAM. But in embedded systems, especially on MCUs with only a few tens of kilobytes of RAM, the situation is completely different.
Dynamic memory allocation does have its advantages. For example, when writing a protocol stack, different data packets can vary in size. If you allocate static memory based on the largest size, it would be a waste. Additionally, if you want to implement some advanced data structures like linked lists or queues, it can be quite difficult without dynamic allocation.
However, the problems are also quite evident. First is the uncertainty in timing; malloc needs to traverse the free list to allocate memory, which is a big taboo in real-time systems. Secondly, there is the issue of memory fragmentation. You may find that there is plenty of free memory, but you cannot allocate a contiguous block. Most critically, many small MCUs’ toolchains do not support malloc at all, or they do so poorly, causing the code size to balloon.
I once maintained an old project where the previous engineer extensively used malloc and free, resulting in the system crashing mysteriously after running for a few hours. After spending a whole week troubleshooting, I discovered that memory fragmentation caused allocation failures, and the error handling was poorly written, leading to direct access of a null pointer. The project eventually stabilized only after switching to static allocation.
Introducing the Pool Pattern
Since malloc has so many issues, is there a good alternative? This brings us to today’s main topic: the memory pool pattern, or Pool Pattern.
The idea of a memory pool is quite simple, similar to the trays in a cafeteria. The cafeteria prepares a fixed number of trays, all of the same size. When you come to eat, you take one, wash it after use, and return it for the next person. This is much more practical than buying new trays every time or throwing them away after use.
In embedded systems, we can pre-allocate a fixed-size memory area and divide it into several blocks of the same size. When memory is needed, we take a block from the pool and return it after use. The benefits of this approach are obvious: allocation time is deterministic at O(1), it does not produce memory fragmentation, and the memory usage can be determined at compile time, making debugging easier.
Implementing a Memory Pool
Having discussed the theory, let’s get practical and demonstrate a generic C language implementation of a memory pool:
// Memory pool structure definition
typedef struct {
void* memory_pool; // Start address of the memory pool
void* free_list; // Head of the free block list
uint8_t* bitmap; // Bitmap management array
size_t block_size; // Size of each block
size_t block_count; // Total number of blocks
size_t free_count; // Remaining free blocks
} MemPool;
// Memory pool interface functions
void mempool_init(MemPool* pool, void* buffer, size_t block_size, size_t block_count);
void* mempool_alloc(MemPool* pool);
void mempool_free(MemPool* pool, void* block);
size_t mempool_available(MemPool* pool);
When using it, you need to prepare a static memory area first:
// Define a memory pool that can hold 32 CAN messages
#define CAN_MSG_SIZE 64
#define CAN_MSG_COUNT 32
static uint8_t can_buffer[CAN_MSG_SIZE * CAN_MSG_COUNT];
static uint8_t can_bitmap[(CAN_MSG_COUNT + 7) / 8];
static MemPool can_msg_pool;
// Initialization
mempool_init(&can_msg_pool, can_buffer, CAN_MSG_SIZE, CAN_MSG_COUNT);
// Usage
void* msg = mempool_alloc(&can_msg_pool);
if (msg != NULL) {
// Use the message buffer
process_can_message(msg);
// Return after use
mempool_free(&can_msg_pool, msg);
}
If you don’t want to pass so many parameters every time, you can simplify the definition using macros:
#define DEFINE_POOL(name, type, count) \
static type name##_buffer[count]; \
static uint8_t name##_bitmap[(count + 7) / 8]; \
static MemPool name = { \
.memory_pool = name##_buffer, \
.bitmap = name##_bitmap, \
.block_size = sizeof(type), \
.block_count = count, \
.free_count = count \
}
// Use macro to define a memory pool
DEFINE_POOL(uart_pool, UartFrame, 16);
// Allocate and free
UartFrame* frame = (UartFrame*)mempool_alloc(&uart_pool);
mempool_free(&uart_pool, frame);
Efficient Bitmap Management of Memory Status
The key issue in implementing a memory pool is how to efficiently track the status of each memory block, whether it is free or allocated. The most straightforward method is to use a boolean array, where each element corresponds to a memory block. However, this method is too extravagant for resource-constrained MCUs. A boolean typically occupies one byte, so managing 64 memory blocks would require 64 bytes of overhead.
Here’s a little trick: use a bitmap for management. A uint8_t has 8 bits, which can manage the status of 8 memory blocks. Thus, managing 64 memory blocks only requires 8 bytes.
Calculating how many bytes are needed is straightforward:
#define BITS_PER_BYTE 8
#define BITMAP_SIZE(n) (((n) + BITS_PER_BYTE - 1) / BITS_PER_BYTE)
// For example: bitmap size needed for 64 blocks
uint8_t bitmap[BITMAP_SIZE(64)]; // Actually allocates 8 bytes
The formula ((n) + BITS_PER_BYTE - 1) is a common technique for rounding up, ensuring that even if the number of blocks is not a multiple of 8, enough space is allocated.
Manipulating the bitmap requires some bit manipulation skills; here is the specific implementation:
// Set a bit to 1 (mark as free)
static inline void bitmap_set(uint8_t* bitmap, size_t index)
{
size_t byte_idx = index / 8;
size_t bit_idx = index % 8;
bitmap[byte_idx] |= (1u << bit_idx);
}
// Clear a bit to 0 (mark as allocated)
static inline void bitmap_clear(uint8_t* bitmap, size_t index)
{
size_t byte_idx = index / 8;
size_t bit_idx = index % 8;
bitmap[byte_idx] &= ~(1u << bit_idx);
}
// Test the status of a bit
static inline int bitmap_test(const uint8_t* bitmap, size_t index)
{
size_t byte_idx = index / 8;
size_t bit_idx = index % 8;
return (bitmap[byte_idx] & (1u << bit_idx)) != 0;
}
// Find the first set bit
static int bitmap_find_first_set(const uint8_t* bitmap, size_t total_bits)
{
size_t bytes = BITMAP_SIZE(total_bits);
for (size_t i = 0; i < bytes; i++) {
if (bitmap[i] != 0) {
// Use __builtin_ctz to find the lowest set bit (GCC built-in function)
// If the compiler does not support it, a loop can be used instead
uint8_t byte = bitmap[i];
for (int j = 0; j < 8; j++) {
if (byte & (1u << j)) {
size_t index = i * 8 + j;
if (index < total_bits) {
return (int)index;
}
}
}
}
}
return -1; // No free block found
}
The core code for the complete memory pool implementation is as follows:
void mempool_init(MemPool* pool, void* buffer, size_t block_size, size_t block_count)
{
pool->memory_pool = buffer;
pool->block_size = block_size;
pool->block_count = block_count;
pool->free_count = block_count;
// Initialize bitmap, mark all as free
size_t bitmap_bytes = BITMAP_SIZE(block_count);
memset(pool->bitmap, 0xFF, bitmap_bytes);
}
void* mempool_alloc(MemPool* pool)
{
if (pool->free_count == 0) {
return NULL;
}
// Find the first free block
int index = bitmap_find_first_set(pool->bitmap, pool->block_count);
if (index < 0) {
return NULL;
}
// Mark as allocated
bitmap_clear(pool->bitmap, index);
pool->free_count--;
// Calculate and return block address
return (uint8_t*)pool->memory_pool + (index * pool->block_size);
}
void mempool_free(MemPool* pool, void* block)
{
if (block == NULL) {
return;
}
// Calculate block index
size_t offset = (uint8_t*)block - (uint8_t*)pool->memory_pool;
size_t index = offset / pool->block_size;
// Boundary check
if (index >= pool->block_count) {
return; // Invalid address
}
// Mark as free
bitmap_set(pool->bitmap, index);
pool->free_count++;
}
Conclusion
In practical projects using memory pools, I have summarized a few experiences:
First is determining the size of the pool. This needs to be assessed based on the actual application scenario. My usual approach is to start with a larger value, monitor actual usage during the testing phase, and gradually adjust to an appropriate size. Remember to leave about 20% headroom for unexpected situations.
Secondly, error handling is crucial. mempool_alloc may return NULL, so it must be checked! I have seen too many system crashes due to neglecting this check. Consider adding assertions in the debug version to expose issues immediately upon allocation failure.
Another detail is memory alignment. If your type T has alignment requirements, such as double needing 8-byte alignment on certain ARM platforms, ensure that the elements array also meets this requirement. Modern compilers usually handle this automatically, but in some special cases, you may need to manually specify alignment attributes.
Finally, regarding usage scenarios, memory pools are particularly suitable for situations where object sizes are fixed and lifetimes are relatively short, such as communication protocol data packet buffers, message objects in event systems, and state nodes in state machines. In our implementation of Modbus RTU, we effectively managed request and response frames using a memory pool.
If your system requires dynamic memory of various sizes, you can create multiple memory pools of different specifications. For example, a small object pool for 32 bytes, a medium object pool for 256 bytes, and a large object pool for 1K. Choose the appropriate pool based on the requested size to reduce internal fragmentation.
Another optimization direction is to support variable-size allocations. You can allocate multiple contiguous blocks for a single request, but this increases management complexity and requires weighing the pros and cons.
For scenarios where memory is only allocated during initialization and not released during operation, you can implement a simpler unidirectional memory pool that only supports allocation without freeing, further reducing overhead.