In-Depth Analysis of FreeRTOS Heap Management Mechanisms: From Heap_2 to Heap_5 Design and Implementation

Introduction: An In-Depth Analysis of FreeRTOS Heap Management Mechanisms—Design and Implementation from Heap_2 to Heap_5

In embedded real-time operating systems (RTOS), dynamic memory management is one of the key factors affecting system stability and performance. FreeRTOS provides multiple heap management schemes (heap_1 to heap_5), each optimized for different application scenarios, involving memory allocation strategies, fragmentation control, and support for multiple memory regions and other core issues.

This article will focus on heap_2 (best-fit algorithm), heap_4 (first-fit algorithm + merging), and heap_5 (support for non-contiguous memory), analyzing their design concepts, implementation principles, and applicable scenarios. We will explore the following aspects:

Organization of memory blocks (e.g., free list structure, block header information);
Details of allocation and deallocation algorithms (e.g., best-fit vs. first-fit, fragmentation merging mechanism);
Key code analysis (e.g., pvPortMalloc, vPortFree, and prvHeapInit implementations);
Practical selection recommendations (how to choose the optimal heap scheme based on hardware resources and task models).

In FreeRTOS, the heap is the core mechanism for dynamic memory management, balancing flexibility (dynamic allocation) and reliability (real-time performance, fragmentation control), serving as the cornerstone of system resource management. Developers need to choose the appropriate heap scheme based on application scenarios (such as real-time requirements and hardware resources) and configure the heap size reasonably to avoid memory exhaustion. Its significance is mainly reflected in the following aspects:

1. Foundation of dynamic memory allocation

FreeRTOS tasks, queues, semaphores, timers, and other kernel objects require dynamic memory allocation at runtime, and the heap is the source of memory for these objects.
Developers can manually request/release memory through APIs such as pvPortMalloc() and vPortFree(), similar to standard C’s malloc() and free(), but optimized for real-time systems.

2. Support for multiple memory management strategies

FreeRTOS provides 5 heap management schemes (heap1 ~ heap5), adapting to different scenario requirements:

heap1~2: Simple but not thread-safe (only applicable to single-task or static allocation scenarios).
heap3: Encapsulates standard library malloc/free, sacrificing determinism (depends on system implementation).
heap4~5: Support for fragmentation management, thread safety, suitable for complex applications (e.g., heap5 supports merging non-contiguous memory blocks).

3. Adaptation to different hardware constraints

Configurable heap size (via configTOTAL_HEAP_SIZE), suitable for resource-constrained embedded devices (e.g., MCUs with only a few KB of RAM).
heap5 supports merging non-contiguous physical memory regions into a logical heap, flexibly utilizing fragmented memory.

4. Underlying support for kernel object management

The FreeRTOS kernel automatically allocates the required memory from the heap when creating tasks, queues, and other objects (e.g., task stacks, TCB structures).
Users can implement custom memory management (e.g., external SPI RAM) by overriding pvPortMalloc().

In-Depth Analysis of FreeRTOS Heap Management Mechanisms: From Heap_2 to Heap_5 Design and Implementation

This image illustrates the main tasks of the heap and corresponding functions, which will be discussed later.

2. Comparison of different implementation effects of the heap

This article will mainly focus on heap2, 3, and 5, providing a simple comparison based on characteristics, principles, and applicable scenarios.

1..heap_2 – Best-fit algorithm (no merging)

Features:

· Supports allocation and deallocation

· Uses the best-fit algorithm (Best Fit), with free blocks sorted by size

· Does not merge adjacent free blocks (which can lead to memory fragmentation)

· Suitable for scenarios where the same size memory is repeatedly allocated.

Implementation principles:

· Free blocks are managed through a linked list, sorted in ascending order by block size

· During allocation, the list is traversed to find the smallest block that meets the requirements

· During deallocation, the block is directly reinserted into the list without checking adjacent blocks

Applicable scenarios:

· Periodically creating/deleting tasks or kernel objects of the same size

· Scenarios where allocation speed is prioritized over memory efficiency

2.heap_4 – First-fit algorithm (with merging)

Features:

· Supports allocation and deallocation

· Uses the first-fit algorithm (First Fit), with free blocks sorted by address

· Merges adjacent free blocks (reducing fragmentation)

· The most general memory management scheme

Implementation principles:

· Free blocks are arranged in memory address order (not size order)

· During allocation, the first sufficiently large block is found

· During deallocation, adjacent blocks are checked for free status, and if so, they are merged

Applicable scenarios:

· Frequently allocating/releasing memory of different sizes

· Long-running systems that require low fragmentation

· Recommended choice for most general embedded applications

3.heap_5 – Support for non-contiguous memory regions

Features:

· Extends on heap_4, supporting multiple non-contiguous memory regions to form a heap

· Suitable for hardware with scattered memory layouts

· Requires explicit initialization of memory regions (vPortDefineHeapRegions())

Implementation principles:

· Allows multiple physically non-contiguous memory blocks to be used as a logical heap

· Each region must define a starting address and size

· Internally uses the same algorithm as heap_4 (first-fit + merging)

Applicable scenarios:

· Hardware with multiple independent memory blocks (e.g., SRAM + SDRAM)

· Systems that require flexible management of complex memory layouts

3. Specific implementation functions for memory allocation

The core function of any heap module is to allocate memory and implement malloc and free. Memory in the heap is stored in blocks.

Memory block structure:

typedef struct A_BLOCK_LINK {    struct A_BLOCK_LINK *pxNextFreeBlock; // Pointer to the next free block    size_t xBlockSize; // Size of the current block (including header)} BlockLink_t;

1. Memory block sorting function prvInsertBlockIntoFreeList( pxBlockToInsert )

#define prvInsertBlockIntoFreeList( pxBlockToInsert )                                                                               \
    {                                                                                                                               \
        BlockLink_t * pxIterator;                                                                                                   \
        size_t xBlockSize;                                                                                                          \
                                                                                                                                    \
        xBlockSize = pxBlockToInsert->xBlockSize;                                                                                   \
                                                                                                                                    \
        /* Iterate through the list until a block is found that has a larger size */                                                \
        /* than the block we are inserting. */                                                                                      \
        for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \
        {                                                                                                                           \
            /* There is nothing to do here - just iterate to the correct position. */                                               \
        }                                                                                                                           \
                                                                                                                                    \
        /* Update the list to include the block being inserted in the correct */                                                    \
        /* position. */                                                                                                             \
        pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;                                                             \
        pxIterator->pxNextFreeBlock = pxBlockToInsert;

For Heap2, the storage block chain header BlockLink_t will continuously traverse backward until it finds a storage block larger than the block to be inserted, thus linking all blocks in ascending order through bubble sorting.

For Heap4/5, they do not sort by block size but by address. The purpose is to check whether adjacent blocks can be merged (by checking address continuity) to reduce fragmentation/solve the problem of non-contiguous memory blocks.

2. Initialization function

static void prvHeapInit( void ){    BlockLink_t * pxFirstFreeBlock;    uint8_t * pucAlignedHeap;    /* Ensure the heap starts on a correctly aligned boundary. */    pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) & ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );    /* xStart is used to hold a pointer to the first item in the list of free     * blocks.  The void cast is used to prevent compiler warnings. */    xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;    xStart.xBlockSize = ( size_t ) 0;    /* xEnd is used to mark the end of the list of free blocks. */    xEnd.xBlockSize = configADJUSTED_HEAP_SIZE;    xEnd.pxNextFreeBlock = NULL;    /* To start with there is a single free block that is sized to take up the     * entire heap space. */    pxFirstFreeBlock = ( void * ) pucAlignedHeap;    pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;

This function initializes the heap memory

(1) Aligning the starting address (8 bytes)

Aligning to an 8-byte address simplifies subsequent space allocation

uint8_t *pucAlignedHeap = (uint8_t*)( ((portPOINTER_SIZE_TYPE)&ucHeap[portBYTE_ALIGNMENT]) &                                     (~((portPOINTER_SIZE_TYPE)portBYTE_ALIGNMENT_MASK)) );

&ucHeap[portBYTE_ALIGNMENT]：Starts from the offset of ucHeap array at portBYTE_ALIGNMENT (skipping any potentially unaligned parts).

& ~portBYTE_ALIGNMENT_MASK：Aligns the address down to the nearest alignment boundary using a mask operation.

(2) Initializing the chain header

xStart.pxNextFreeBlock = (void*)pucAlignedHeap;  // Points to the aligned heap starting addressxStart.xBlockSize = (size_t)0;                  // The head node itself does not participate in allocation

xStart serves as a virtual head node for the free list, with its pxNextFreeBlock pointing to the first real free block

(3) Initializing the initial free block

BlockLink_t *pxFirstFreeBlock = (void*)pucAlignedHeap; pxFirstFreeBlock->xBlockSize = configADJUSTED_HEAP_SIZE;  // The entire heap as a large blockpxFirstFreeBlock->pxNextFreeBlock = &xEnd;                // Points to the tail node

For heap2/4, the entire heap is treated as a large block:

xStart → [pxFirstFreeBlock: size=entire heap] → xEnd

For heap5, it will chain several memory blocks:

xStart → [pxFirstFreeBlock: size=entire heap] → xEnd

3. Memory allocation function malloc

void * pvPortMalloc( size_t xWantedSize ){    BlockLink_t * pxBlock, * pxPreviousBlock, * pxNewBlockLink;    static BaseType_t xHeapHasBeenInitialised = pdFALSE;    void * pvReturn = NULL;    vTaskSuspendAll();    {        /* If this is the first call to malloc then the heap will require         * initialisation to setup the list of free blocks. */        if( xHeapHasBeenInitialised == pdFALSE )        {            prvHeapInit();            xHeapHasBeenInitialised = pdTRUE;        }        /* The wanted size must be increased so it can contain a BlockLink_t         * structure in addition to the requested amount of bytes. */        if( ( xWantedSize > 0 ) &&            ( ( xWantedSize + heapSTRUCT_SIZE ) >  xWantedSize ) ) /* Overflow check */        {            xWantedSize += heapSTRUCT_SIZE;            /* Byte alignment required. Check for overflow. */            if( ( xWantedSize + ( portBYTE_ALIGNMENT - ( xWantedSize && portBYTE_ALIGNMENT_MASK ) ) )                    > xWantedSize )            {                xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize && portBYTE_ALIGNMENT_MASK ) );                configASSERT( ( xWantedSize && portBYTE_ALIGNMENT_MASK ) == 0 );            }            else            {                xWantedSize = 0;            }        }        else        {            xWantedSize = 0;        }        if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )        {            /* Blocks are stored in byte order - traverse the list from the start             * (smallest) block until one of adequate size is found. */            pxPreviousBlock = &xStart;            pxBlock = xStart.pxNextFreeBlock;            while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )            {                pxPreviousBlock = pxBlock;                pxBlock = pxBlock->pxNextFreeBlock;            }            /* If we found the end marker then a block of adequate size was not found. */            if( pxBlock != &xEnd )            {                /* Return the memory space - jumping over the BlockLink_t structure                 * at its start. */                pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );                /* This block is being returned for use so must be taken out of the                 * list of free blocks. */                pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;                /* If the block is larger than required it can be split into two. */                if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )                {                    /* This block is to be split into two.  Create a new block                     * following the number of bytes requested. The void cast is                     * used to prevent byte alignment warnings from the compiler. */                    pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );                    /* Calculate the sizes of two blocks split from the single                     * block. */                    pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;                    pxBlock->xBlockSize = xWantedSize;                    /* Insert the new block into the list of free blocks. */                    prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );                }                xFreeBytesRemaining -= pxBlock->xBlockSize;            }        }        traceMALLOC( pvReturn, xWantedSize );    }    ( void ) xTaskResumeAll();    #if ( configUSE_MALLOC_FAILED_HOOK == 1 )        {            if( pvReturn == NULL )            {                extern void vApplicationMallocFailedHook( void );                vApplicationMallocFailedHook();            }        }    #endif    return pvReturn;}/*--------------

Function analysis:

(1) Initialization check

if( xHeapHasBeenInitialised == pdFALSE ){    prvHeapInit();    xHeapHasBeenInitialised = pdTRUE;}

This code checks whether the stack has been initialized before the first call (drawing the entire stack as a large block and preparing the head and tail of the list).(2) Format adjustment

if( ( xWantedSize > 0 ) &&(( xWantedSize + heapSTRUCT_SIZE ) >xWantedSize ) ){    xWantedSize+= heapSTRUCT_SIZE;}

This part aims to add the header to calculate the actual required size.

if( ( xWantedSize + ( portBYTE_ALIGNMENT - ( xWantedSize && portBYTE_ALIGNMENT_MASK ) ) )>xWantedSize ){    xWantedSize+= ( portBYTE_ALIGNMENT - ( xWantedSize && portBYTE_ALIGNMENT_MASK ) );    configASSERT(( xWantedSize && portBYTE_ALIGNMENT_MASK ) == 0 );}

This part is to supplement the alignment space:

·Alignment algorithm:Calculate the number of bytes to fill: portBYTE_ALIGNMENT – (size % alignment); typical alignment values: 8 bytes (32-bit systems) or 16 bytes (64-bit systems)

·Assertion check:Ensure the final size is a multiple of the alignment value.

(3) Return address

pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + heapSTRUCT_SIZE );pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;

·Address calculation:

Returns the address to the user, skipping the block header (usable address): block starting address + heapSTRUCT_SIZE

·List update:

Removes the target block from the free list (the predecessor node directly points to the successor node).

(4) Block splitting mechanism

if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE ){    pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );    pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;    pxBlock->xBlockSize= xWantedSize;    prvInsertBlockIntoFreeList(pxNewBlockLink );}

·Splitting condition:

The remaining space must be able to accommodate at least heapMINIMUM_BLOCK_SIZE (usually 2*heapSTRUCT_SIZE), otherwise it is ignored.

·Operation steps:Calculate the size of a block after cutting off a piece.

1.Calculate the split point: original block address + requested size

2.Initialize the new block header: remaining space size

3.Reinsert the remaining block into the free list

(5) Failure handling

Malloc will use a hook function to clear after allocation failure: (the hook function needs to be designed by the user)

#if ( configUSE_MALLOC_FAILED_HOOK == 1 )    {        if(pvReturn == NULL )        {            extern void vApplicationMallocFailedHook( void );            vApplicationMallocFailedHook();        }    }#endif

(4) Memory release function vPortFree

void vPortFree( void * pv ){    uint8_t * puc = ( uint8_t * ) pv;    BlockLink_t * pxLink;    if( pv != NULL )    {        /* The memory being freed will have an BlockLink_t structure immediately         * before it. */        puc -= heapSTRUCT_SIZE;        /* This unexpected casting is to keep some compilers from issuing         * byte alignment warnings. */        pxLink = ( void * ) puc;        vTaskSuspendAll();        {            /* Add this block to the list of free blocks. */            prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );            xFreeBytesRemaining += pxLink->xBlockSize;            traceFREE( pv, pxLink->xBlockSize );        }        ( void ) xTaskResumeAll();    }}/*---

PortFree is the core function for dynamic memory release in FreeRTOS, mainly completing:

Locating the memory block header (finding the management structure by backing up the pointer).

Reinserting the released block into the free list (sorted by strategy). Merging adjacent free blocks (only supported by Heap_4/Heap_5). Updating the remaining heap memory count

, ensuring thread safety.

(1) Finding the memory block header (locating the memory block)

if (pv != NULL) {    uint8_t *puc = (uint8_t *)pv;  // Convert user pointer to byte pointer (for arithmetic operations)    puc -= heapSTRUCT_SIZE;        // Backtrack to the start of the block header    BlockLink_t *pxLink = (void *)puc;  // Force cast to block header structure pointer}

The address calculation involves adding the length of the header to the user’s pointer pv to find the actual head of the storage block pxLink for release.

[BlockLink_t header][User Data]             ↑pxLink             ↑pv (User-provided pointer)

(2) Suspending the scheduler

vTaskSuspendAll() does not welcome the scheduler during release, just like during malloc

(3) Inserting into the free list

prvInsertBlockIntoFreeList((BlockLink_t*)pxLink);

While inserting into the free list, adjacent blocks will be merged; heap2 does not merge adjacent blocks, while heap4/5 will check and merge adjacent free blocks.

(4) Updating the free memory count

xFreeBytesRemaining += pxLink->xBlockSize;

4. Conclusion

FreeRTOS’s heap management mechanism is the core of dynamic memory allocation, balancing flexibility (dynamic allocation) and reliability (real-time performance, fragmentation control). Its core value is reflected in:

Foundation of dynamic memory
Basic: Provides memory sources for tasks, queues, semaphores, etc., supporting manual allocation/release (pvPortMalloc/vPortFree).
Support for multiple strategies: 5 heap schemes (Heap_1 to Heap_5) adapt to different scenarios, such as Heap_2 (best-fit) suitable for fixed-size allocations, and Heap_4/5 (first-fit + merging) suitable for long-term low-fragmentation needs.

Key implementation mechanisms:

Memory block structure

Each block contains a block header (BlockLink_t) and user data area, with the block header storing size and list pointer.
User pointers locate the block header by backing up heapSTRUCT_SIZE (puc -= heapSTRUCT_SIZE).

Allocation process (pvPortMalloc)

Alignment adjustment: The requested size must include the block header and alignment padding (e.g., 8-byte alignment).
List traversal: Heap_2 finds the smallest block in ascending order by size, while Heap_4/5 finds the first sufficient block by address.
Block splitting: If the remaining space is greater than heapMINIMUM_BLOCK_SIZE, split and insert the remaining block into the list.

Release process (vPortFree)

List insertion: Released blocks are reinserted into the list according to strategy (Heap_4/5 merges adjacent blocks).
Thread safety: All operations are performed within the critical section of vTaskSuspendAll().

Initialization (prvHeapInit)

Address alignment: The heap starting address is aligned to portBYTE_ALIGNMENT (e.g., 0x1003 → 0x1008).
List construction: Initialized as a single large free block (xStart → initial block → xEnd).

In-Depth Analysis of FreeRTOS Heap Management Mechanisms: From Heap_2 to Heap_5 Design and Implementation

Table of Contents:

1. Introduction

2. Core significance of the heap module

3. Comparison of heap implementation schemes

4. Analysis of key implementation mechanisms

5. Conclusion

1. Foundation of dynamic memory allocation

2. Support for multiple memory management strategies

3. Adaptation to different hardware constraints

4. Underlying support for kernel object management

Leave a Comment Cancel reply