#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 );
}

1. 进行字节对齐，找到对齐后的首地址，在32位机中以8字节进行对齐。
2. 初始化xStart的值。
3. 计算对齐后的尾部地址，将pxEnd指向这一地址，同时初始化。
4. 初始化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;    
    }    
}

原文链接：https://www.cnblogs.com/chenpangzhi/p/17291060.html