@(嵌入式)

[TOC]

Freertos

FreeRtos 提供的幾種 heap 管理在源碼目錄 Source/Portable/MemMang 下硅卢，選擇哪種類型管理直接在編譯時(shí)把原文件加入（比如在 makefile SRC中加入）即可释树， 堆大小是 FreeRTOSConfig.h 中的常量 configTOTAL_HEAP_SIZE揣云，默認(rèn)是17*1024银受，即17KB。

FreeRtos 內(nèi)存管理提供的主要接口：

• pvPortMalloc() 對(duì)應(yīng) malloc()
• vPortFree() 對(duì)應(yīng) free()
• xPortGetFreeHeapSize() 獲取剩余可分配內(nèi)存大小

為了適配不同平臺(tái)敛纲、場(chǎng)合需求晌纫，對(duì)接口提供了不同的實(shí)現(xiàn)。

內(nèi)存對(duì)齊

在 portmacro.h (Source/Portable/ + 對(duì)應(yīng)編譯器 + 平臺(tái) 目錄下) 的常量 portBYTE_ALIGNMENT 定義了字節(jié)對(duì)齊境肾，對(duì)應(yīng)的這個(gè)變量決定了 portable.h 中的一個(gè)常量 portBYTE_ALIGNMENT_MASK剔难， 對(duì)應(yīng)關(guān)系如下：

在堆管理中涉及了一些字節(jié)對(duì)齊，此處做準(zhǔn)備奥喻。

Heap_1

這個(gè)版本的堆管理偶宫，如源碼注釋

The simplest possible implementation of pvPortMalloc(). Note that this implementation does NOT allow allocated memory to be freed again.

實(shí)現(xiàn) pvPortMalloc() 用于內(nèi)存分配，但是不支持回收衫嵌，適用于一些比較小的嵌入式設(shè)備读宙，在系統(tǒng) boot 后申請(qǐng)內(nèi)存運(yùn)行任務(wù)，隊(duì)列和信號(hào)量等楔绞，在程序生命期內(nèi)一般沒有釋放的需求结闸。對(duì)于一些安全型的系統(tǒng)，一般是不允許動(dòng)態(tài)申請(qǐng)的酒朵，滿足設(shè)計(jì)需求下桦锄，越簡(jiǎn)單越安全。

調(diào)用函數(shù) pvPortMalloc( size_t xWantedSize ) 申請(qǐng)內(nèi)存時(shí)蔫耽，按順序完成如下工作：

• 字節(jié)對(duì)齊
• 分配內(nèi)存
• 調(diào)用鉤子函數(shù)
• 返回分配內(nèi)存地址

初始化

#define configADJUSTED_HEAP_SIZE    ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )
/* Allocate the memory for the heap. */
static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ];
static size_t xNextFreeByte = ( size_t ) 0;

configADJUSTED_HEAP_SIZE 定義了實(shí)際可用的堆大小结耀，因?yàn)楸ＷC字節(jié)的對(duì)齊，所以減去一個(gè)對(duì)齊的長(zhǎng)度匙铡。
ucHeap[ configTOTAL_HEAP_SIZE ] 和 xNextFreeByte 分別對(duì)應(yīng)堆 的地址和已經(jīng)分配的值图甜，堆實(shí)際上就是一個(gè)靜態(tài)分配的大數(shù)組。

以下代碼鳖眼，均是函數(shù) pvPortMalloc() 的內(nèi)容

字節(jié)對(duì)齊處理

/* 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

if 判斷了申請(qǐng)的內(nèi)存大小是否符合字節(jié)對(duì)齊黑毅，如果不符合，則進(jìn)行對(duì)齊處理钦讳。舉個(gè)例子矿瘦，設(shè)置8字節(jié)對(duì)齊，你本來申請(qǐng)的 xWantedSize == 12 個(gè)byte愿卒，與 mask & 的結(jié)果是4（0100B）, 不對(duì)齊缚去，為了對(duì)齊，系統(tǒng)會(huì) ”強(qiáng)迫癥“ 多給你4個(gè)字節(jié)琼开。實(shí)際上你不應(yīng)該用到易结，因?yàn)槟闵暾?qǐng)了12bye。

分配內(nèi)存

vTaskSuspendAll();
{
    if( pucAlignedHeap == NULL )
    {
        /* Ensure the heap starts on a correctly aligned boundary. */
        // 字節(jié)對(duì)齊
        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. */
        // 切塊蛋糕一樣把內(nèi)存分配出來
        pvReturn = pucAlignedHeap + xNextFreeByte;
        xNextFreeByte += xWantedSize;
    }
    traceMALLOC( pvReturn, xWantedSize );
}   
xTaskResumeAll();

1. 系統(tǒng)調(diào)用了 vTaskSuspendAll() 掛起所有任務(wù)柜候，保證線程安全搞动， 避免分配時(shí)被切任務(wù)導(dǎo)致出錯(cuò)。
2. 對(duì)堆的首地址作對(duì)齊處理
   可能有人疑問堆首地址不就是上面提到那個(gè)數(shù)組的首地址 &ucHeap[0]改橘， 為什么這里要使用 &ucHeap[ portBYTE_ALIGNMENT ] & portPOINTER_SIZE_TYPE滋尉？
   其實(shí)這個(gè)地方處理還是考慮對(duì)齊問題，舉個(gè)例子就明白了：
   設(shè)置8byte對(duì)齊飞主， 假如&ucHeap[0]地址是 0x00000006, 為了保證對(duì)齊狮惜，F(xiàn)reeRtos 直接在這個(gè)地址加上一個(gè)對(duì)齊的長(zhǎng)度（保證&后不會(huì)越界訪問），然后和 mark &一下碌识，對(duì)應(yīng)的碾篡，&ucHeap[ portBYTE_ALIGNMENT ]對(duì)應(yīng)了0x000000014，& 上 mark 就是 0x00000008筏餐。由于做了這個(gè)調(diào)整后开泽，實(shí)際的堆大小改變了，所以 configADJUSTED_HEAP_SIZE 表示實(shí)際可用的內(nèi)存大小
3. 分配內(nèi)存
   Heap_1 比較簡(jiǎn)單魁瞪，按順序分配穆律，所以只需要判斷剩下的內(nèi)存夠大惠呼，直接切出來，更新已分配大小的值峦耘，返回地址就可以了

鉤子函數(shù)調(diào)用&返回地址

定義了configUSE_MALLOC_FAILED_HOOK == 1 后剔蹋， 當(dāng)申請(qǐng)失敗的時(shí)候會(huì)調(diào)用鉤子函數(shù)， 也可以自己添加其他處理代碼辅髓。

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

Heap_1 的 vPortFree 函數(shù)就不提了

Heap_2

Heap_2 內(nèi)存分配使用最佳匹配算法(best fit algorithm)泣崩，比如我們申請(qǐng)25k的內(nèi)存，而可申請(qǐng)內(nèi)存中有三塊對(duì)應(yīng)大小30K洛口， 50K 和 100 K矫付，按照最小匹配，這時(shí)候會(huì)把30k進(jìn)行分割并返回申請(qǐng)內(nèi)存的地址第焰，剩余部分插回鏈表留待下次申請(qǐng)买优。
Heap_2 支持內(nèi)存回收，但是不會(huì)把碎片合并樟遣，對(duì)于每次申請(qǐng)內(nèi)存大小都比較固定的而叼，這個(gè)方式是沒有問題的。

開始和 Heap_1 差不多豹悬， 在內(nèi)存中開辟了一個(gè)靜態(tài)數(shù)組作為堆的空間葵陵，定義大小，字節(jié)對(duì)齊處理等瞻佛。

建立鏈表

Heap_2 通過一個(gè)鏈表維護(hù)未分配的內(nèi)存脱篙，鏈表節(jié)點(diǎn)定義：

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;

兩個(gè)變量分別是指向下一塊內(nèi)存的地址指針 pxNextFreeBlock 以及自己的內(nèi)存大小 xBlockSize。

在第一次申請(qǐng)內(nèi)存的時(shí)候會(huì)調(diào)用初始化函數(shù) prvHeapInit() 初始化列表伤柄。初始化包括鏈表頭 xStart 和鏈表尾 xEnd (這兩個(gè)節(jié)點(diǎn)不包含空閑內(nèi)存)绊困，以及把整個(gè)堆作為一個(gè)完整的空閑節(jié)點(diǎn)。

每塊內(nèi)存（分配出的和未分配的）的結(jié)構(gòu)如下 :

每塊的開頭節(jié)點(diǎn)數(shù)據(jù)适刀，提供了分配內(nèi)存或者回收內(nèi)存所需要的信息秤朗。

分配內(nèi)存

當(dāng)我們嘗試申請(qǐng)內(nèi)存的時(shí)候，除了和 Heap_1 一樣進(jìn)行對(duì)齊等處理外笔喉，系統(tǒng)會(huì)在我們申請(qǐng)內(nèi)存大小 xWantedSize 的基礎(chǔ)上增加一個(gè) heapSTRUCT_SIZE （鏈表節(jié)點(diǎn)對(duì)齊后的大腥∈印）的鏈表節(jié)點(diǎn)，記錄這塊分配出去的內(nèi)存的大小常挚，供回收的時(shí)候使用作谭。

從鏈表頭開始遍歷未分配內(nèi)存鏈表，查找符合大小的內(nèi)存塊（鏈表按內(nèi)存塊大小排列奄毡，所以最先返回的的塊最符合申請(qǐng)內(nèi)存大小折欠，所謂的最匹配算法就是這個(gè)意思來的）。返回該塊 heapSTRUCT_SIZE 個(gè)字節(jié)后的地址給函數(shù)調(diào)用者， 前面預(yù)留的字節(jié)保留鏈表節(jié)點(diǎn)信息锐秦。

同時(shí)會(huì)判斷當(dāng)前這塊內(nèi)存是否有剩余（大于一個(gè)鏈表節(jié)點(diǎn)所需空間）咪奖，如果有，就把剩余的內(nèi)存再新建一個(gè)未分配內(nèi)存塊節(jié)點(diǎn)农猬，插入到未分配鏈表中赡艰，供下次分配使用售淡。其中 prvInsertBlockIntoFreeList() 這個(gè)宏函數(shù)是把節(jié)點(diǎn)按大小插入到鏈表中斤葱。

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;
    // 尋找匹配的內(nèi)存塊節(jié)點(diǎn)
    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. */
        //返回給我們用地址，前面 heapSTRUCT_SIZE 保存鏈表節(jié)點(diǎn)數(shù)據(jù)
        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. */
        // 內(nèi)存塊比較大揖闸，拆分多余的內(nèi)存揍堕，插回到鏈表
        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. */
            //　按內(nèi)存大小插入
            prvInsertBlockIntoFreeList( ( pxNewBlockLink ) );
        }

        xFreeBytesRemaining -= pxBlock->xBlockSize;
    }
}

回收內(nèi)存

回收內(nèi)存， 拿到分配時(shí)返回的地址汤纸，向前索引到對(duì)應(yīng)鏈表節(jié)點(diǎn)衩茸，取出這塊返回內(nèi)存塊的信息，調(diào)用鏈表插入函數(shù)贮泞，將這個(gè)節(jié)點(diǎn)歸還楞慈。（線程安全）

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 );
}
xTaskResumeAll();

！？胁痢囊蓝！　這里感覺，如果隨便傳個(gè)地址進(jìn)來令蛉，會(huì)不會(huì)把系統(tǒng)弄傻.....

Heap_3

Heap_3 實(shí)現(xiàn)是直接對(duì)標(biāo)準(zhǔn)庫(kù)的 malloc 進(jìn)行封裝聚霜， 保證線程安全。

void *pvPortMalloc( size_t xWantedSize ) 
{ 
void *pvReturn; 
    vTaskSuspendAll();  // 掛起任務(wù)
    { 
        pvReturn = malloc( xWantedSize ); 
    } 
    xTaskResumeAll(); 
    return pvReturn; 
} 
void vPortFree( void *pv ) 
{ 
    if( pv != NULL ) 
    { 
        vTaskSuspendAll(); 
        { 
            free( pv ); 
        } 
        xTaskResumeAll(); 
    } 
} 

!! 這種模式下珠叔，堆大小不再由 FreeRTOSConfig.h 中定義的常量 configTOTAL_HEAP_SIZE 決定蝎宇，而是由連接器或者啟動(dòng)代碼決定。

Heap_4

相比 Heap_2, Heap_4 能夠把內(nèi)存碎片合并成大塊內(nèi)存祷安，為了實(shí)現(xiàn)這個(gè)合并算法姥芥，空閑內(nèi)存鏈表是按內(nèi)存地址大小進(jìn)行存儲(chǔ)的（Heap_2　是按照內(nèi)存塊大小進(jìn)行存儲(chǔ)）。

xEnd 的位置

不同 heap_2 中 用一個(gè)靜態(tài)變量 xEnd 作為鏈表尾汇鞭，heap_4 把鏈表尾放在了堆的最后位置凉唐，如源碼：

// 堆地址最后往回推一個(gè)鏈表節(jié)點(diǎn)的空間
uxAddress = ( ( size_t ) pucAlignedHeap ) + xTotalHeapSize;
uxAddress -= xHeapStructSize;
uxAddress &= ~( ( size_t ) portBYTE_ALIGNMENT_MASK );
pxEnd = ( void * ) uxAddress;
pxEnd->xBlockSize = 0;
pxEnd->pxNextFreeBlock = NULL;

xBlockAllocatedBit 判斷

另外，為了安全虱咧，增加一個(gè)位（xBlockSize　的最高位）標(biāo)記檢測(cè) Free 時(shí)傳入地址的正確性熊榛，在初始化的時(shí)候設(shè)置 xBlockAllocatedBit 的值, 一個(gè) size_t 大小的值最高位置1， 分配出去的內(nèi)存塊鏈表節(jié)點(diǎn)的 xBlockSize 或上腕巡，回收的時(shí)候判斷玄坦，如果最高位不是1， 說明出錯(cuò)。

/* Work out the position of the top bit in a size_t variable. */
xBlockAllocatedBit = ( ( size_t ) 1 ) << ( ( sizeof( size_t ) * heapBITS_PER_BYTE ) - 1 );

進(jìn)行字節(jié)對(duì)齊和線程安全等的操作和前面兩種方式差不多煎楣。

鏈表插入 （合并實(shí)現(xiàn)）

Heap_2 中的鏈表插入是通過宏實(shí)現(xiàn)的豺总，按內(nèi)存塊大小進(jìn)行插入，而 Heap_4 的插入操作是一個(gè)函數(shù)择懂，該函數(shù)按內(nèi)存塊地址進(jìn)行插入（低位前）喻喳，這么做是為了實(shí)現(xiàn)內(nèi)存塊合并。
如下困曙， 準(zhǔn)備插入的內(nèi)存塊p表伦， 系統(tǒng)查找到內(nèi)存地址對(duì)應(yīng)與其前面的內(nèi)存塊A, 判斷 A 和 P 之間是否還有其他分配的塊，如果沒有慷丽，直接合并蹦哼； 然后再判斷和內(nèi)存C 的位置關(guān)系，沒有其他分配了的內(nèi)存塊的話要糊，就直接合并纲熏。

下面對(duì)應(yīng)看看源碼 ：

static void prvInsertBlockIntoFreeList( BlockLink_t *pxBlockToInsert )
{
    BlockLink_t *pxIterator;
    uint8_t *puc;
    // for 的目的是知道 pxIterator 指向內(nèi)存塊A
    // pxIterator->pxNextFreeBlock 指向內(nèi)存塊C
    // 插入內(nèi)存塊P 剛好夾在中間
    for( pxIterator = &xStart; pxIterator->pxNextFreeBlock < pxBlockToInsert; pxIterator = pxIterator->pxNextFreeBlock )
    {
        /* Nothing to do here, just iterate to the right position. */
    }
    // 判斷內(nèi)存塊A 能否與插入內(nèi)存塊P 合并
    // 合并條件：頭尾銜接剛好
    puc = ( uint8_t * ) pxIterator;
    if( ( puc + pxIterator->xBlockSize ) == ( uint8_t * ) pxBlockToInsert )
    {
        pxIterator->xBlockSize += pxBlockToInsert->xBlockSize;
        pxBlockToInsert = pxIterator;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }
    // 判斷內(nèi)存塊C 能否與插入塊P 合并
    puc = ( uint8_t * ) pxBlockToInsert;
    if( ( puc + pxBlockToInsert->xBlockSize ) == ( uint8_t * ) pxIterator->pxNextFreeBlock )
    {
        // 如果是內(nèi)存塊C 是最后一個(gè)節(jié)點(diǎn) xEnd，不能合并
        if( pxIterator->pxNextFreeBlock != pxEnd )
        {
            pxBlockToInsert->xBlockSize += pxIterator->pxNextFreeBlock->xBlockSize;
            pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock->pxNextFreeBlock;
        }
        else
        {
            pxBlockToInsert->pxNextFreeBlock = pxEnd;
        }
    }
    else
    {
        // 內(nèi)存塊C 不能合并的話锄俄，讓上一塊指向他
        pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock;
    }
    if( pxIterator != pxBlockToInsert )
    {   
        // 內(nèi)存塊A 不能合并局劲，更新他指向剛插入的內(nèi)存塊P
        pxIterator->pxNextFreeBlock = pxBlockToInsert;
    }
    else
    {
        mtCOVERAGE_TEST_MARKER();
    }
}

分配內(nèi)存

相比 Heap_2 差別不大，主要是在分配過程多了一個(gè)位標(biāo)記防止出錯(cuò)奶赠，因?yàn)槭褂昧?xBlockSize 的最高位做標(biāo)記鱼填，所以實(shí)際傳入的 xWantedSize 最高位不能為1，否則超出范圍车柠。
其他差別不大剔氏，此處不做贅述。

回收內(nèi)存

相比 Heap_2, Heap_4 多了一些檢查竹祷，更加安全谈跛。

// 判斷位標(biāo)記，判斷指向下一個(gè)節(jié)點(diǎn)是否 設(shè)置為 Null
configASSERT( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 );
configASSERT( pxLink->pxNextFreeBlock == NULL );
if( ( pxLink->xBlockSize & xBlockAllocatedBit ) != 0 )
{
    if( pxLink->pxNextFreeBlock == NULL )
    {
    ...

最后清除 xBlockSize 的高位標(biāo)記塑陵，調(diào)用插入函數(shù)歸還內(nèi)存感憾。

獲取歷史堆剩余最小值

可用于最壞情況下，堆的使用情況令花， 在每次調(diào)用 pvPortMalloc() 中進(jìn)行更新阻桅。

size_t xPortGetMinimumEverFreeHeapSize( void )

Heap_5

前面方式1、2和4 方式都是靜態(tài)申請(qǐng)一個(gè)數(shù)組作為堆兼都，Heap_5 允許使用多個(gè)不連續(xù)的區(qū)域組成堆嫂沉，申請(qǐng)函數(shù)前，必須通過函數(shù) vPortDefineHeapRegions() 進(jìn)行設(shè)置扮碧，對(duì)于一些內(nèi)存分布不連續(xù)的嵌入式設(shè)備還是很有價(jià)值的趟章，之后其他操作杏糙，和 Heap_4 基本一致。

所以這里主要分析下 vPortDefineHeapRegions() 的實(shí)現(xiàn)蚓土。

設(shè)置作為堆的區(qū)域需要用到一下結(jié)構(gòu)體

/* Used by heap_5.c. */
typedef struct HeapRegion
{
    uint8_t *pucStartAddress;
    size_t xSizeInBytes;
} HeapRegion_t;

舉個(gè)例子宏侍，
有兩個(gè)不連續(xù)區(qū)域首地址0x00200000， 長(zhǎng)度0x10000 和首地址0x00300000蜀漆， 長(zhǎng)度0xA0000 只做為堆谅河，則可以建立如下數(shù)組傳遞給 vPortDefineHeapRegions(), 進(jìn)行設(shè)置。

HeapRegion_t xHeapRegions[] =  
{  
    { ( uint8_t * ) 0x00200000UL, 0x10000 },   
    { ( uint8_t * ) 0x00300000UL, 0xA0000 },   
    { NULL, 0 }         // 告知結(jié)束         
};  

相比前面其他模式确丢，初始化時(shí)绷耍，把可以分配的內(nèi)存作為一個(gè)節(jié)點(diǎn)，Heap_5 就把這幾個(gè)不連續(xù)的內(nèi)存區(qū)域分別作為節(jié)點(diǎn)鏈接起來蠕嫁。

每個(gè)連續(xù)區(qū)域作為一個(gè)節(jié)點(diǎn)锨天，其結(jié)構(gòu)如下

參考

Using the FreeRTOS Real Time Kernel - A Practical Guide_opened
FreeRTOS memory