示例源码基于FreeRTOS V9.0.0
内存管理
1 概述
FreeRTOS 有自己的一套内存管理机制，而非直接使用malloc和free等C库函数。
malloc和free由于实现复杂，代码量大，运行时间不确定，存在内存碎片，非线程安全等问题，不适用于资源紧缺的FreeRTOS系统；
FreeRTOS 实现了5种内存管理方式，实际使用时再根据需求决定使用哪种内存管理方案，每种内存管理方案均由一个c文件实现，命名分别为heap_1.c、heap_2.c、heap_3.c、heap_4.c、heap_5.c，位于FreeRTOS\Source\portable\MemMang目录下。使用时选择其中一个加入编译即可；
常用的内存管理方案是heap_4.c；
2 接口API
void *pvPortMalloc( size_t xWantedSize );
void vPortFree( void *pv );
5种内存管理方案都提供了如上两个API接口，用于申请和释放内存；
void vApplicationMallocFailedHook( void );
内存分配失败后，如果开启了configUSE_MALLOC_FAILED_HOOK宏，则会调用钩子函数，由用户实现具体行为；
size_t xPortGetFreeHeapSize( void );
用户获取剩余空闲内存大小（在heap_3.c中无法使用）；
size_t xPortGetMinimumEverFreeHeapSize( void );
获取分配过程中，空闲内存容量的最小值（只在heap_4.c heap_5.c中才能使用）；
3 五种内存管理方式
3.1 heap_1
3.1.1 实现原理
使用一个静态定义的大数组，每次分配从数组内进行分配；
3.1.2 源码分析
内存数组：
/* Allocate the memory for the heap. */
#if( configAPPLICATION_ALLOCATED_HEAP == 1 )
/* The application writer has already defined the array used for the RTOS
heap - probably so it can be placed in a special segment or address. */
extern uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
#else
static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
#endif /* configAPPLICATION_ALLOCATED_HEAP */
内存申请：
void *pvPortMalloc( size_t xWantedSize )
{
void *pvReturn = NULL;
static uint8_t *pucAlignedHeap = NULL;
/* Ensure that blocks are always aligned to the required number of bytes. */
#if( portBYTE_ALIGNMENT != 1 )
{
if( xWantedSize & portBYTE_ALIGNMENT_MASK )
{
/* Byte alignment required. */
xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
}
}
#endif
vTaskSuspendAll();
{
if( pucAlignedHeap == NULL )
{
/* Ensure the heap starts on a correctly aligned boundary. */
pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ~( ( portPOINTER_SIZE_TYPE ) portBYTE_ALIGNMENT_MASK ) ) );
}
/* Check there is enough room left for the allocation. */
if( ( ( xNextFreeByte + xWantedSize ) < configADJUSTED_HEAP_SIZE ) &&
( ( xNextFreeByte + xWantedSize ) > xNextFreeByte ) )/* Check for overflow. */
{
/* Return the next free byte then increment the index past this
block. */
pvReturn = pucAlignedHeap + xNextFreeByte;
xNextFreeByte += xWantedSize;
}
traceMALLOC( pvReturn, xWantedSize );
}
( void ) xTaskResumeAll();
#if( configUSE_MALLOC_FAILED_HOOK == 1 )
{
if( pvReturn == NULL )
{
extern void vApplicationMallocFailedHook( void );
vApplicationMallocFailedHook();
}
}
#endif
return pvReturn;
}
分配步骤如下：
- 将申请大小调整为字节对齐数的整数倍，向上调整；
- 挂起调度器；
- 如果是首次分配，将起始分配地址调整为字节对齐数的整数倍，向上调整；
- 判断剩余空间是否充足，是否会溢出，若充足且不溢出，则分配内存。计算空闲地址，累计分配大小；pucAlignedHeap记录了起始分配地址，它是字节对齐数的整数倍。xNextFreeByte记录了总共分配的内存大小；
- 恢复调度器；
- 若分配失败，调用钩子函数；
- 返回分配好的内存地址；
内存释放（不做实现，只校验了指针）：
void vPortFree( void *pv )
{
/* Memory cannot be freed using this scheme. See heap_2.c, heap_3.c and
heap_4.c for alternative implementations, and the memory management pages of
http://www.FreeRTOS.org for more information. */
( void ) pv;
/* Force an assert as it is invalid to call this function. */
configASSERT( pv == NULL );
}
3.1.3 特点
- 实现简单，不存在内存碎片；
- 只实现了分配（pvPortMalloc），没有实现释放（vPortFree）；
3.1.4 使用场景
不允许使用动态内存，不需要删除对象时使用；
3.1.5 内存分配示例
3.2 heap_2
3.2.1 实现原理
-
在heap_1的基础上，增加了内存回收机制；
-
依旧使用一个静态定义的大数组用以分配内存，但增加了单向链表用来维护空闲内存块，链表有序，按内存块大小排列，每次分配从空闲链表内进行分配（本质也是从数组分配）；
-
单向链表包含头节点和尾节点，两个节点并不使用数组内存。链表初始化时头节点指向数组首地址（经字节对齐后的地址）；
-
采用最佳匹配算法分配，分配时它会遍历链表，找到满足分配大小的最小一块内存，并将其剩余部分拆分成一个新的内存块，作为新节点插入空闲链表；
3.2.2 源码分析
单向链表节点：
/* Define the linked list structure. This is used to link free blocks in order
of their size. */
typedef struct A_BLOCK_LINK
{
struct A_BLOCK_LINK *pxNextFreeBlock; /*<< The next free block in the list. */
size_t xBlockSize; /*<< The size of the free block. */
} BlockLink_t;
插入空闲链表：
/*
* Insert a block into the list of free blocks - which is ordered by size of
* the block. Small blocks at the start of the list and large blocks at the end
* of the list.
*/
#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; \
}
链表按节点的xBlockSize来排序，从小到大升序排列。插入前先从头到尾遍历找到比待插入节点xBlockSize大或等于的节点（pxIterator->pxNextFreeBlock），并将新节点插入其之前。
空闲链表初始化：
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;
pxFirstFreeBlock->pxNextFreeBlock = &xEnd;
}
-
pucAlignedHeap为数组首地址按字节对齐后的地址。如按8字节对齐，数组首地址为15，则pucAlignedHeap为(15+8)&(~0x07)=16；
-
xStart为头节点，指针域指向pucAlignedHeap，xBlockSize为0；
-
xEnd为尾节点，指针域为NULL，xBlockSize为数组可总分配大小（即数组大小 - 字节对齐数，减去字节对齐数是因为pucAlignedHeap在对齐地址后，舍去了数组头部的部分字节，这部分大小一定小于字节对齐数）；
-
pxFirstFreeBlock是首个链表节点，指针域指向尾节点xEnd，内存块大小xBlockSize为可分配总大小（因为初始化时只一个节点），pxFirstFreeBlock本身存储也占用了数组空间；
内存申请：
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 is increased so it can contain a BlockLink_t
structure in addition to the requested amount of bytes. */
if( xWantedSize > 0 )
{
xWantedSize += heapSTRUCT_SIZE;
/* Ensure that blocks are always aligned to the required number of bytes. */
if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0 )
{
/* Byte alignment required. */
xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
}
}
if( ( xWantedSize > 0 ) && ( xWantedSize < configADJUSTED_HEAP_SIZE ) )
{
/* 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;
}
分配步骤如下：
- 挂起调度器；
- 首次分配时进行链表初始化；
- 申请大小xWantedSize 加上链表节点大小heapSTRUCT_SIZE（按字节对齐数向上取整后），再按字节对齐数向上取整；
- 从头到尾遍历空闲链表，找到可以分配的内存块（pxBlock指向）；
- 将内存块返回给用户，返回的地址需要进行偏移（+heapSTRUCT_SIZE），移除头部。同时将该节点从空闲链表移除；
- 拆分内存块，构建新节点，指向内存块剩余部分，并将其插入空闲链表（按序插入）；
- 恢复调度器；
- 如果分配失败，调用钩子函数；
内存释放：
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();
}
}
回收步骤如下：
- 指针偏移，定位链表节点结构；
- 挂起调度器；
- 将节点插入空闲链表；
- 更新统计计数；
- 恢复调度器；
3.2.3 特点
-
最佳匹配算法分配；
-
会有内存碎片产生，但如果分配的大小始终是相同，则不会有内存碎片；
3.2.4 使用场景
频繁地创建、删除任务，但任务的栈大小都是相同的(创建任务时，需要分配TCB和栈，TCB总是一样的)。
3.2.5 内存分配示例
3.3 heap_3
3.3.1 实现原理
只是简单封装了C库函数malloc和free，加入了任务挂起和恢复保护，保证线程安全；
3.3.2 源码分析
内存申请：
void *pvPortMalloc( size_t xWantedSize )
{
void *pvReturn;
vTaskSuspendAll();
{
pvReturn = malloc( xWantedSize );
traceMALLOC( pvReturn, xWantedSize );
}
( void ) xTaskResumeAll();
#if( configUSE_MALLOC_FAILED_HOOK == 1 )
{
if( pvReturn == NULL )
{
extern void vApplicationMallocFailedHook( void );
vApplicationMallocFailedHook();
}
}
#endif
return pvReturn;
}
分配步骤如下：
- 挂起调度器；
- malloc分配内存；
- 恢复调度器；
- 如果分配失败，调用钩子函数；
内存释放：
void vPortFree( void *pv )
{
if( pv )
{
vTaskSuspendAll();
{
free( pv );
traceFREE( pv, 0 );
}
( void ) xTaskResumeAll();
}
}
回收步骤如下：
- 挂起调度器；
- free释放内存；
- 恢复调度器；
3.4 heap_4
3.4.1 实现原理
-
在heap_2的基础上进行的改进，优化内存碎片问题；
-
依旧使用一个静态定义的大数组用以分配内存，增加了单向链表用来维护空闲内存块，每次分配从空闲链表内进行分配（本质也是从数组分配），每次回收时进行相邻内存块的合并（前向和后向）；
-
单向链表包含头节点和尾节点，头节点并不使用数组内存，尾节点存于数组。链表初始化时头节点指向数组首地址（经字节对齐后的地址）；
-
采用首次适应算法分配，分配时它会遍历链表，找到首个满足分配大小的内存块，并将其剩余部分拆分成一个新的内存块，作为新节点插入空闲链表；
3.4.2 源码分析
列表节点结构同heap_2.c实现；
空闲链表初始化：
static void prvHeapInit( void )
{
BlockLink_t *pxFirstFreeBlock;
uint8_t *pucAlignedHeap;
size_t uxAddress;
size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
/* Ensure the heap starts on a correctly aligned boundary. */
uxAddress = ( size_t ) ucHeap;
if( ( uxAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
{
uxAddress += ( portBYTE_ALIGNMENT - 1 );
uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
xTotalHeapSize -= uxAddress - ( size_t ) ucHeap;
}
pucAlignedHeap = ( uint8_t * ) uxAddress;
/* 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;
/* pxEnd is used to mark the end of the list of free blocks and is inserted
at the end of the heap space. */
uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
uxAddress -= xHeapStructSize;
uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
pxEnd = ( void * ) uxAddress;
pxEnd->xBlockSize = 0;
pxEnd->pxNextFreeBlock = NULL;
/* To start with there is a single free block that is sized to take up the
entire heap space, minus the space taken by pxEnd. */
pxFirstFreeBlock = ( void * ) pucAlignedHeap;
pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
/* Only one block exists - and it covers the entire usable heap space. */
xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
/* Work out the position of the top bit in a size_t variable. */
xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
}
- 类同heap_2.c实现，与其区别是heap_4实现的链表，尾节点是存放在数组空间内的；
- 初始uxAddress指向数组首地址，然后对其进行字节对齐取整处理；
- 初始化头节点，指针域指向对齐后的起始地址pucAlignedHeap，xBlockSize赋为0；
- uxAddress指向数组尾地址，偏移xHeapStructSize字节预留链表节点空间，再进行字节对齐取整；
- 初始化尾节点，存储在尾地址uxAddress上，指针域指向NULL，xBlockSize赋为0；
- 初始化首个空闲内存块，pxFirstFreeBlock指针域指向起始地址pucAlignedHeap，xBlockSize为数组总的可分配内存大小（包含pxFirstFreeBlock节点本身占用）；
- 更新计数值xMinimumEverFreeBytesRemaining和xFreeBytesRemaining；
- xBlockAllocatedBit 最高位置1；
插入空闲链表：
static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
BlockLink_t *pxIterator;
uint8_t *puc;
/* Iterate through the list until a block is found that has a higher address
than the block being inserted. */
for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
{
/* Nothing to do here, just iterate to the right position. */
}
/* Do the block being inserted, and the block it is being inserted after
make a contiguous block of memory? */
puc = ( uint8_t * ) pxIterator;
if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
{
pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
pxBlockToInsert = pxIterator;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* Do the block being inserted, and the block it is being inserted before
make a contiguous block of memory? */
puc = ( uint8_t * ) pxBlockToInsert;
if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
{
if( pxIterator->pxNextFreeBlock != pxEnd )
{
/* Form one big block from the two blocks. */
pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
}
else
{
pxBlockToInsert->pxNextFreeBlock = pxEnd;
}
}
else
{
pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
}
/* If the block being inserted plugged a gab, so was merged with the block
before and the block after, then it's pxNextFreeBlock pointer will have
already been set, and should not be set here as that would make it point
to itself. */
if( pxIterator != pxBlockToInsert )
{
pxIterator->pxNextFreeBlock = pxBlockToInsert;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
- 从头遍历链表，找到插入点，因为链表节点均是存于数组，其地址也是按序增长的，这里直接比对链表节点的地址；
- pxIterator位于插入点pxBlockToInsert前最近一个空闲的节点块；
- pxIterator->pxNextFreeBlock位于插入点pxBlockToInsert后最近一个空闲的节点块；
- 如果pxIterator和pxBlockToInsert指向的内存块间没有间隙（满足条件puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert），说明它们是相邻内存块，则进行内存块合并，节点合并（pxBlockToInsert = pxIterator）。这是前向合并；
- 如果pxIterator->pxNextFreeBlock和pxBlockToInsert指向的内存块间没有间隙（满足条件puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock），说明它们是相邻内存块，则考虑进行内存块合并。这是后向合并；
- 如果后向节点不是尾节点（pxIterator->pxNextFreeBlock != pxEnd），则正常进行合并；
- 如果后向节点是尾节点，不进行合并，pxBlockToInsert是最后一块内存块，下一节点指向尾节点；
- 如果pxIterator->pxNextFreeBlock和pxBlockToInsert指向的内存块间存在间隙，无法后向合并，pxBlockToInsert下一节点指向pxIterator->pxNextFreeBlock（pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock）；
- 如果没有前向合并过（pxIterator != pxBlockToInsert），pxIterator下一节点指向pxBlockToInsert（pxIterator->pxNextFreeBlock = pxBlockToInsert）；
内存申请：
void *pvPortMalloc( size_t xWantedSize )
{
BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
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( pxEnd == NULL )
{
prvHeapInit();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* Check the requested block size is not so large that the top bit is
set. The top bit of the block size member of the BlockLink_t structure
is used to determine who owns the block - the application or the
kernel, so it must be free. */
if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
{
/* The wanted size is increased so it can contain a BlockLink_t
structure in addition to the requested amount of bytes. */
if( xWantedSize > 0 )
{
xWantedSize += xHeapStructSize;
/* Ensure that blocks are always aligned to the required number
of bytes. */
if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
{
/* Byte alignment required. */
xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
configASSERT( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) == 0 );
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
else
{
mtCOVERAGE_TEST_MARKER();
}
if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
{
/* Traverse the list from the start (lowest address) 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 the end marker was reached then a block of adequate size
was not found. */
if( pxBlock != pxEnd )
{
/* Return the memory space pointed to - jumping over the
BlockLink_t structure at its start. */
pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
/* 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 );
configASSERT( ( ( ( size_t ) pxNewBlockLink ) & portBYTE_ALIGNMENT_MASK ) == 0 );
/* 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 );
}
else
{
mtCOVERAGE_TEST_MARKER();
}
xFreeBytesRemaining -= pxBlock->xBlockSize;
if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
{
xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* The block is being returned - it is allocated and owned
by the application and has no "next" block. */
pxBlock->xBlockSize |= xBlockAllocatedBit;
pxBlock->pxNextFreeBlock = NULL;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
else
{
mtCOVERAGE_TEST_MARKER();
}
traceMALLOC( pvReturn, xWantedSize );
}
( void ) xTaskResumeAll();
#if( configUSE_MALLOC_FAILED_HOOK == 1 )
{
if( pvReturn == NULL )
{
extern void vApplicationMallocFailedHook( void );
vApplicationMallocFailedHook();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif
configASSERT( ( ( ( size_t ) pvReturn ) & ( size_t ) portBYTE_ALIGNMENT_MASK ) == 0 );
return pvReturn;
}
分配步骤如下：
- 挂起调度器；
- 首次分配时进行链表初始化；
- 申请大小xWantedSize 加上链表节点大小xHeapStructSize（按字节对齐数向上取整后），再按字节对齐数向上取整；
- 剩余空间足够分配，则从头遍历空闲链表，找到可分配的内存块（pxBlock）；
- 能找到（pxBlock不是尾节点），将内存块返回给用户，返回的地址需要进行偏移（+xHeapStructSize），移除头部，从空闲链表内移除节点pxBlock；
- 拆分内存块，构建新节点，指向内存块剩余部分，并将其插入空闲链表；
- 更新计数值xFreeBytesRemaining和xMinimumEverFreeBytesRemaining；
- pxBlock->xBlockSize最高位置1（pxBlock->xBlockSize |= xBlockAllocatedBit）；
- 恢复调度器；
- 如果分配失败，调用钩子函数；
内存释放：
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 -= xHeapStructSize;
/* This casting is to keep the compiler from issuing warnings. */
pxLink = ( void * ) puc;
/* Check the block is actually allocated. */
configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
configASSERT( pxLink->pxNextFreeBlock == NULL );
if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
{
if( pxLink->pxNextFreeBlock == NULL )
{
/* The block is being returned to the heap - it is no longer
allocated. */
pxLink->xBlockSize &= ~xBlockAllocatedBit;
vTaskSuspendAll();
{
/* Add this block to the list of free blocks. */
xFreeBytesRemaining += pxLink->xBlockSize;
traceFREE( pv, pxLink->xBlockSize );
prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
}
( void ) xTaskResumeAll();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
}
回收步骤如下：
- 指针偏移，定位链表节点结构；
- 校验内存块有效性（pxBlock->xBlockSize最高位是否为1）；
- pxBlock->xBlockSize最高位重新置0；
- 挂起调度器；
- 更新计数值xFreeBytesRemaining；
- 将内存块插入空闲链表；
- 恢复调度器；
3.4.3 特点
-
首次适应算法分配；
-
会自动合并相邻内存块，减少内存碎片化问题；
-
执行的时间是不确定的，但是它的效率高于标准库的malloc、free；
3.4.4 使用场景
频繁地分配、释放不同大小的内存。
3.4.5 内存分配示例
3.5 heap_5
3.5.1 实现原理
- 在heap_4的基础上进行的改进，不再是在单独一个大数组内进行内存分配，而是支持在多块非连续内存上进行分配；
- 链表设计和分配算法同heap_4, 但链表不再是单独组织一个大数组内存块，二而是将多个非连续内存块进行了串联；
3.5.2 源码分析
链表结构体设计同heap_4;
新增了HeapRegion结构体，用于描述内存区域（定义在FreeRTOS\Source\include\portable.h）：
/* Used by heap_5.c. */
typedef struct HeapRegion
{
uint8_t *pucStartAddress;
size_t xSizeInBytes;
} HeapRegion_t;
空闲链表初始化：
在使用heap_5的内存申请接口前，必须先调用void vPortDefineHeapRegions( const HeapRegion_t * const pxHeapRegions );接口进行空闲链表初始化，它将各个内存区域做了串联。
void vPortDefineHeapRegions( const HeapRegion_t * const pxHeapRegions )
{
BlockLink_t *pxFirstFreeBlockInRegion = NULL, *pxPreviousFreeBlock;
size_t xAlignedHeap;
size_t xTotalRegionSize, xTotalHeapSize = 0;
BaseType_t xDefinedRegions = 0;
size_t xAddress;
const HeapRegion_t *pxHeapRegion;
/* Can only call once! */
configASSERT( pxEnd == NULL );
pxHeapRegion = &( pxHeapRegions[ xDefinedRegions ] );
while( pxHeapRegion->xSizeInBytes > 0 )
{
xTotalRegionSize = pxHeapRegion->xSizeInBytes;
/* Ensure the heap region starts on a correctly aligned boundary. */
xAddress = ( size_t ) pxHeapRegion->pucStartAddress;
if( ( xAddress & portBYTE_ALIGNMENT_MASK ) != 0 )
{
xAddress += ( portBYTE_ALIGNMENT - 1 );
xAddress &= ~portBYTE_ALIGNMENT_MASK;
/* Adjust the size for the bytes lost to alignment. */
xTotalRegionSize -= xAddress - ( size_t ) pxHeapRegion->pucStartAddress;
}
xAlignedHeap = xAddress;
/* Set xStart if it has not already been set. */
if( xDefinedRegions == 0 )
{
/* 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 = ( BlockLink_t * ) xAlignedHeap;
xStart.xBlockSize = ( size_t ) 0;
}
else
{
/* Should only get here if one region has already been added to the
heap. */
configASSERT( pxEnd != NULL );
/* Check blocks are passed in with increasing start addresses. */
configASSERT( xAddress > ( size_t ) pxEnd );
}
/* Remember the location of the end marker in the previous region, if
any. */
pxPreviousFreeBlock = pxEnd;
/* pxEnd is used to mark the end of the list of free blocks and is
inserted at the end of the region space. */
xAddress = xAlignedHeap + xTotalRegionSize;
xAddress -= xHeapStructSize;
xAddress &= ~portBYTE_ALIGNMENT_MASK;
pxEnd = ( BlockLink_t * ) xAddress;
pxEnd->xBlockSize = 0;
pxEnd->pxNextFreeBlock = NULL;
/* To start with there is a single free block in this region that is
sized to take up the entire heap region minus the space taken by the
free block structure. */
pxFirstFreeBlockInRegion = ( BlockLink_t * ) xAlignedHeap;
pxFirstFreeBlockInRegion->xBlockSize = xAddress - ( size_t ) pxFirstFreeBlockInRegion;
pxFirstFreeBlockInRegion->pxNextFreeBlock = pxEnd;
/* If this is not the first region that makes up the entire heap space
then link the previous region to this region. */
if( pxPreviousFreeBlock != NULL )
{
pxPreviousFreeBlock->pxNextFreeBlock = pxFirstFreeBlockInRegion;
}
xTotalHeapSize += pxFirstFreeBlockInRegion->xBlockSize;
/* Move onto the next HeapRegion_t structure. */
xDefinedRegions++;
pxHeapRegion = &( pxHeapRegions[ xDefinedRegions ] );
}
xMinimumEverFreeBytesRemaining = xTotalHeapSize;
xFreeBytesRemaining = xTotalHeapSize;
/* Check something was actually defined before it is accessed. */
configASSERT( xTotalHeapSize );
/* Work out the position of the top bit in a size_t variable. */
xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
}
- 接口内遍历HeapRegion_t数组，pxHeapRegions指向HeapRegion_t数组元素；
- xAddress为内存区域首地址，进行字节对齐向上取整后，得到分配的起始地址xAlignedHeap；
- 第一次遍历时，初始化链表头节点xStart，其指针域指向起始地址xAlignedHeap，即HeapRegion_t数组首个元素（首个内存区）的可分配起始地址；
- 计算内存区域最后一个对齐的地址，用于存放链表尾节点pxEnd，初始化尾节点pxEnd；
- 构建空闲链表，节点pxFirstFreeBlockInRegion指针域pxNextFreeBlock指向尾节点pxEnd， xBlockSize赋为该内存区的总的可分配内存大小；
- 非首次遍历，需要将两个内存区串联（pxPreviousFreeBlock->pxNextFreeBlock = pxFirstFreeBlockInRegion）；
- 更新计数xMinimumEverFreeBytesRemaining、xFreeBytesRemaining；
- xBlockAllocatedBit最高位置1；
接口初始化结束后，HeapRegion_t数组内所有内存区块都将被链表串联，每个链表节点指向一个内存区块；
接口的使用方式如下（必须在pvPortMalloc()之前调用）：
/*
* Usage notes:
*
* vPortDefineHeapRegions() ***must*** be called before pvPortMalloc().
* pvPortMalloc() will be called if any task objects (tasks, queues, event
* groups, etc.) are created, therefore vPortDefineHeapRegions() ***must*** be
* called before any other objects are defined.
*
* vPortDefineHeapRegions() takes a single parameter. The parameter is an array
* of HeapRegion_t structures. HeapRegion_t is defined in portable.h as
*
* typedef struct HeapRegion
* {
* uint8_t *pucStartAddress; << Start address of a block of memory that will be part of the heap.
* size_t xSizeInBytes; << Size of the block of memory.
* } HeapRegion_t;
*
* The array is terminated using a NULL zero sized region definition, and the
* memory regions defined in the array ***must*** appear in address order from
* low address to high address. So the following is a valid example of how
* to use the function.
*
* HeapRegion_t xHeapRegions[] =
* {
* { ( uint8_t * ) 0x80000000UL, 0x10000 }, << Defines a block of 0x10000 bytes starting at address 0x80000000
* { ( uint8_t * ) 0x90000000UL, 0xa0000 }, << Defines a block of 0xa0000 bytes starting at address of 0x90000000
* { NULL, 0 } << Terminates the array.
* };
*
* vPortDefineHeapRegions( xHeapRegions ); << Pass the array into vPortDefineHeapRegions().
*
* Note 0x80000000 is the lower address so appears in the array first.
*/
插入空闲链表：
源码同heap_4一致；
内存申请：
void *pvPortMalloc( size_t xWantedSize )
{
BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
void *pvReturn = NULL;
/* The heap must be initialised before the first call to
prvPortMalloc(). */
configASSERT( pxEnd );
vTaskSuspendAll();
{
/* Check the requested block size is not so large that the top bit is
set. The top bit of the block size member of the BlockLink_t structure
is used to determine who owns the block - the application or the
kernel, so it must be free. */
if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
{
/* The wanted size is increased so it can contain a BlockLink_t
structure in addition to the requested amount of bytes. */
if( xWantedSize > 0 )
{
xWantedSize += xHeapStructSize;
/* Ensure that blocks are always aligned to the required number
of bytes. */
if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
{
/* Byte alignment required. */
xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
else
{
mtCOVERAGE_TEST_MARKER();
}
if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
{
/* Traverse the list from the start (lowest address) 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 the end marker was reached then a block of adequate size
was not found. */
if( pxBlock != pxEnd )
{
/* Return the memory space pointed to - jumping over the
BlockLink_t structure at its start. */
pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
/* 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 ) );
}
else
{
mtCOVERAGE_TEST_MARKER();
}
xFreeBytesRemaining -= pxBlock->xBlockSize;
if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
{
xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* The block is being returned - it is allocated and owned
by the application and has no "next" block. */
pxBlock->xBlockSize |= xBlockAllocatedBit;
pxBlock->pxNextFreeBlock = NULL;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
else
{
mtCOVERAGE_TEST_MARKER();
}
traceMALLOC( pvReturn, xWantedSize );
}
( void ) xTaskResumeAll();
#if( configUSE_MALLOC_FAILED_HOOK == 1 )
{
if( pvReturn == NULL )
{
extern void vApplicationMallocFailedHook( void );
vApplicationMallocFailedHook();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif
return pvReturn;
}
源码同heap_4大致一致， 区别在于heap_4是在pvPortMalloc()接口内进行的链表初始化，而heap_5则是在接口外做的初始化，需要主动调用初始化接口；
内存释放：
源码同heap_4一致；
3.5.3 特点
- 可以管理多块、分隔开的内存；
3.5.4 使用场景
在嵌入式系统中，存在多块并不连续的内存区域，可以考虑使用heap_5；
4 总结
heap_1 —— 最简单，不允许释放内存；
heap_2 —— 允许释放内存，但不会合并相邻的空闲块；
heap_3 —— 简单包装了标准 malloc() 和 free()，以保证线程安全；
heap_4 —— 合并相邻的空闲块以避免碎片化。 包含绝对地址放置选项；
heap_5 —— 如同 heap_4，能够跨越多个不相邻内存区域的堆；