#FREERTOS的和heap_4内存分配算法
FreeRTOS的heap_4内存管理算法具有内存碎片合并的功能，可以有效防止内存碎片产生，使用First fit算法，在实现上与C标准库的malloc类似，但是效率更高且能进行碎片合并回收。以下是个人对源码的解析,有空再补充详细。
一、初始化
static void prvHeapInit( void )
{
BlockLink_t *pxFirstFreeBlock;
uint8_t *pucAlignedHeap;
size_t uxAddress;
size_t xTotalHeapSize = configTOTAL_HEAP_SIZE;
/*====================================== 1 ===========================================*/
/* 字节对齐,4字节 */
uxAddress = ( size_t ) ucHeap;
/*字节对齐，一般是8字节*/
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;
/*====================================== 2 ===========================================*/
/* 把xStart的next指针指向对齐后的头地址，长度设置为0.xStart只是链表头不参与内存分配*/
xStart.pxNextFreeBlock = ( void * ) pucAlignedHeap;
xStart.xBlockSize = ( size_t ) 0;
/*====================================== 3 ===========================================*/
/* 计算尾部指针地址 */
uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
/* 减去end所占用的8个字节 */
uxAddress -= xHeapStructSize;
/* pxend字节对齐，也就是尾部会空出8-15字节用于放pxend */
uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
/* pxend初始化 */
pxEnd = ( void * ) uxAddress;
pxEnd->xBlockSize = 0;
pxEnd->pxNextFreeBlock = NULL;
/*====================================== 4 ===========================================*/
/* 初始化头结构，也就是xstart一开始指向的那个地址 */
pxFirstFreeBlock = ( void * ) pucAlignedHeap;
pxFirstFreeBlock->xBlockSize = uxAddress - ( size_t ) pxFirstFreeBlock;
pxFirstFreeBlock->pxNextFreeBlock = pxEnd;
/* 初始化内存最大使用量和剩余空间这两个变量的值 */
xMinimumEverFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
xFreeBytesRemaining = pxFirstFreeBlock->xBlockSize;
/* 定义xBlockSize最高bit，因为xBlockSize的最高bit用于判断是否使用 */
xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );
}
- 进行字节对齐，找到对齐后的首地址，在32位机中以8字节进行对齐。
- 初始化xStart的值。
- 计算对齐后的尾部地址，将pxEnd指向这一地址，同时初始化。
- 初始化xStart指向的头地址的值，因为还没分配，所以next指向pxend，size为整个空间大小。初始化用于记录剩余空间的变量值
二、申请内存
void *pvPortMalloc( size_t xWantedSize )
{
BlockLink_t *pxBlock, *pxPreviousBlock, *pxNewBlockLink;
void *pvReturn = NULL;
{
/* 如果还没初始化的话，就先初始化. */
if( pxEnd == NULL )
{
prvHeapInit();
}
/* 检查要分配的大小是否超过了最大值,因为最高位用来标志空闲块是否已经使用，
所以能分配的空间最大值为0x7FFF FFFF 也就是2G*/
if( ( xWantedSize & xBlockAllocatedBit ) == 0 )
{
/* 检查分配空间是否为0 */
if( xWantedSize > 0 )
{
/* 加上链表结构的大小 */
xWantedSize += xHeapStructSize;
/* 日常字节对齐 */
if( ( xWantedSize & portBYTE_ALIGNMENT_MASK ) != 0x00 )
{
/* 补齐. */
xWantedSize += ( portBYTE_ALIGNMENT - ( xWantedSize & portBYTE_ALIGNMENT_MASK ) );
}
}
/* 这里也判断xWantedSize>0,可以跟上面的代码合并啊，判断空闲的空间还够不够 */
if( ( xWantedSize > 0 ) && ( xWantedSize <= xFreeBytesRemaining ) )
{
/* 从头开始查找大小够分配的空闲块，直到找到pxend. */
pxPreviousBlock = &xStart;
pxBlock = xStart.pxNextFreeBlock;
while( ( pxBlock->xBlockSize < xWantedSize ) && ( pxBlock->pxNextFreeBlock != NULL ) )
{
pxPreviousBlock = pxBlock;
pxBlock = pxBlock->pxNextFreeBlock;
}
/* 如果是pxEnd就是说没有能够分配的空闲块了，分配失败 */
if( pxBlock != pxEnd )
{
/* 分配的地址是空闲块管理结构地址+结构大小，如图
分配了的空间 新的空闲块
|____|_______________|________________|
☝ ↑分配的内存地址
有足够空间的结构， */
pvReturn = ( void * ) ( ( ( uint8_t * ) pxPreviousBlock->pxNextFreeBlock ) + xHeapStructSize );
/* 跳过刚刚被使用的空闲块，指向下一块 */
pxPreviousBlock->pxNextFreeBlock = pxBlock->pxNextFreeBlock;
/* 如果当前空闲块分配完之后剩余的大小还>=16字节，就分成两块 */
if( ( pxBlock->xBlockSize - xWantedSize ) > heapMINIMUM_BLOCK_SIZE )
{
/* 创建一个新的空闲块，计算偏移地址 */
pxNewBlockLink = ( void * ) ( ( ( uint8_t * ) pxBlock ) + xWantedSize );
/* 初始化新空闲块的大小，next需要做插入处理 */
pxNewBlockLink->xBlockSize = pxBlock->xBlockSize - xWantedSize;
/* 旧块重新定义大小 */
pxBlock->xBlockSize = xWantedSize;
/* Insert the new block into the list of free blocks.看英语解释 */
prvInsertBlockIntoFreeList( pxNewBlockLink );
}
/* 扣除剩余的空间统计 */
xFreeBytesRemaining -= pxBlock->xBlockSize;
/* 记录当前使用空间的最大值，也就是记录系统运行中最多用了多少空间 */
if( xFreeBytesRemaining < xMinimumEverFreeBytesRemaining )
{
xMinimumEverFreeBytesRemaining = xFreeBytesRemaining;
}
/* 最高位置为1，清楚next指针，标记已经用掉了 */
pxBlock->xBlockSize |= xBlockAllocatedBit;
pxBlock->pxNextFreeBlock = NULL;
}
}
}
}
{
if( pvReturn == NULL )
{
printf("malloc fail \r\n");
}
}
return pvReturn;
}
三、释放内存
oid vPortFree( void *pv )
{
uint8_t *puc = ( uint8_t * ) pv;
BlockLink_t *pxLink;
if( pv != NULL )
{
/* 找到结构体的地址
↓puc地址
|______|___________________|
↑BlockLink_t地址*/
puc -= xHeapStructSize;
/* 防一手编译器警告 */
pxLink = ( void * ) puc;
/* 通过最高位判断是否已经使用 */
if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
{
/* 已经使用的next被复制为null，可以看malloc */
if( pxLink->pxNextFreeBlock == NULL )
{
/*清掉标志位 */
pxLink->xBlockSize &= ~xBlockAllocatedBit;
{
/* 统计空闲内内存大小，插入链表中. */
xFreeBytesRemaining += pxLink->xBlockSize;
prvInsertBlockIntoFreeList( ( ( BlockLink_t * ) pxLink ) );
}
}
}
}
}
/*-----------------------------------------------------------*/
四、碎片整理
把新的空闲列表项插入链表中，同时进行空闲块合并。
static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
BlockLink_t *pxIterator;
uint8_t *puc;
/* 遍历链表，找到newlist的前一个list地址，也就是插入的位置.
heap4对链表的地址管理都是从小到大，所以只要循环比对地址大小就行了 */
for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
{
/* Nothing to do here, just iterate to the right position. */
}
/* 插入前，检查前(已有的项)后(要插入的项)两个空闲块是否相邻，相邻的话直接合并 */
puc = ( uint8_t * ) pxIterator;
if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
{
/* 合并处理 */
pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
pxBlockToInsert = pxIterator;
}
/* 插入前，检查前(要插入的项pxBlockToInsert)后(已有的项)两个空闲块是否相邻，相邻的话直接合并，
跟上面的流程相同，只是比对的是跟在新链表后面的那个 */
puc = ( uint8_t * ) pxBlockToInsert;
if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
{
if( pxIterator->pxNextFreeBlock != pxEnd )
{
/* 合成一块 */
pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize; pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
}
else
{
/* 不合并的话给新链表项的next赋值 */
pxBlockToInsert->pxNextFreeBlock = pxEnd;
}
}
else
{
/* 不合并的话给新链表项的next赋值 */
pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
}
/* 如果没进行过合并，插入新链表 */
if( pxIterator != pxBlockToInsert )
{
pxIterator->pxNextFreeBlock = pxBlockToInsert;
}
}