在FreeRTOS8.0.1這個(gè)版本中，一共有四個(gè)內(nèi)存堆模型。這一次講的就是第二個(gè)模型Heap_2.c。從一開始就可以看到注釋中對Heap_2的模型解釋：這是對pvPortMalloc()和vPortFree()的簡單實(shí)現(xiàn)，除了可以分配內(nèi)存之外，還可以對已分配的內(nèi)存進(jìn)行回收，但相鄰空閑塊不會(huì)進(jìn)行合并，因此會(huì)造成一定的內(nèi)存碎片。（A sample implementation of pvPortMalloc() and vPortFree() that permits allocated blocks to be freed, but does not combine adjacent free blocks into a single larger block (and so will fragment memory).）

在Heap_2中，由于開始支持對內(nèi)存進(jìn)行回收，因此FreeRTOS以空閑塊對內(nèi)存堆進(jìn)行管理，并且使用了最佳適配算法(best fit algorithm)去進(jìn)行內(nèi)存的分配。

首先，還是由內(nèi)存中開辟一個(gè)靜態(tài)數(shù)組ucHeap[ configTOTAL_HEAP_SIZE ]作為FreeRTOS的內(nèi)存堆。同樣也會(huì)因?yàn)閷R的原因FreeRTOS對內(nèi)存堆的可用空間進(jìn)行了調(diào)整，并定義了常量configADJUSTED_HEAP_SIZE。（具體已在上一篇《內(nèi)存管理Heap_1.c》中介紹）

接下來可以留意Heap_2.c中最重要的結(jié)構(gòu)struct A_BLOCK_LINK。由于FreeRTOS用空閑塊對內(nèi)存堆進(jìn)行管理，于是用這一個(gè)結(jié)構(gòu)來形成一條空閑塊鏈表對空閑塊進(jìn)行組織和管理。
/* 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;

這個(gè)結(jié)構(gòu)有兩個(gè)成員，第一個(gè)是節(jié)點(diǎn)Next指針pxNextFreeBlock，第二個(gè)是空閑塊大小。一個(gè)空閑塊就用這樣的一個(gè)結(jié)構(gòu)節(jié)點(diǎn)表示，所有節(jié)點(diǎn)通過Next指針形成一條空閑塊鏈表。FreeRTOS還定義了這個(gè)鏈表的頭xStart和尾xEnd。
/* Create a couple of list links to mark the start and end of the list. */
static BlockLink_t xStart, xEnd;

與Heap_1不同，在Heap_2中會(huì)有一個(gè)堆初始化的過程prvHeapInit()。這一個(gè)過程被pvPortMalloc()調(diào)用，但只被調(diào)用一次。主要還是對內(nèi)存堆進(jìn)行對齊還有對空閑塊表進(jìn)行初始化工作。下面是它的工作流程。

首先，初始化流程對整個(gè)內(nèi)存堆進(jìn)行地址對齊工作。對齊的原因的原理與Heap_1一樣。
/* Ensure the heap starts on a correctly aligned boundary. */
pucAlignedHeap = ( uint8_t * ) ( ( ( portPOINTER_SIZE_TYPE ) &ucHeap[ portBYTE_ALIGNMENT ] ) & ( ( portPOINTER_SIZE_TYPE ) ~portBYTE_ALIGNMENT_MASK ) );

在獲取到地址對齊后的內(nèi)存堆首地址之后，就要對空閑塊鏈表進(jìn)行初始化。留意，xStart是鏈表頭，并不表示一個(gè)空閑塊，xEnd是鏈表尾，也不表示一個(gè)空閑塊，但記錄著整個(gè)堆的大小。其代碼如下：
/* 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;

經(jīng)過上面的初始化流程后，整個(gè)鏈表如下圖所示。注意，xStart和xEnd是存在于靜態(tài)存儲區(qū)中，并不在FreeRTOS申請的內(nèi)存堆數(shù)組中，但初始時(shí)第一個(gè)節(jié)點(diǎn)卻在內(nèi)存堆數(shù)組中。我用的編譯器是Keil MDK 5.11，并且將FreeRTOS移植到STM32上，因此一個(gè)A_BLOCK_LINK的大小為8個(gè)字節(jié)。

整個(gè)初始化的流程就完成了。接下來看看pvPortMalloc()分配內(nèi)存的流程。如Heap_1一樣，在真正開始分配內(nèi)存時(shí)，用vTaskSuspendAll()掛起所有任務(wù)，防止分配內(nèi)存的過程被中斷，確保操作的原子性。緊接著，如果是第一次調(diào)用pvPortMalloc()，則調(diào)用prvHeapInit()對內(nèi)存堆和空閑塊鏈表進(jìn)行初始化。由于在Heap_2中將內(nèi)存堆用空閑塊處理，因此用戶每申請一次內(nèi)存，F(xiàn)reeRTOS都會(huì)在申請的空間前加上空閑塊頭部BlockLink_t，用于記錄分配出去的空間的大小。因此，真正要分配的內(nèi)存空間大小就等于用戶申請的內(nèi)存空間大小加上空閑塊頭部的大小。加上頭部之后，還要對整個(gè)大小進(jìn)行對齊。因此，在真正分配空間之前，F(xiàn)reeRTOS都對用戶申請的空間大小進(jìn)行了調(diào)整。如下面的代碼所示。
/* 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 ) );
}
}

在這一段代碼里，有一個(gè)地方要注意的就是這里用到的空閑塊頭部并不是直接sizeof(BlockLink_t)，而是heapSTRUCT_SIZE，這個(gè)常量也定義在Heap_2.c中，這是對空閑塊頭部的大小再進(jìn)行了一次大小對齊。
接下來做了一個(gè)分配判斷。xWantedSize0，還看得我很迷糊的。本來xWantedSize就是unsigned int，是大于等于0的，一下子沒有留意到等于0是什么情況。等于0，就是加上空閑塊頭之后的大小變?yōu)?了？這是神馬情況？！看來這個(gè)判斷條件很另人費(fèi)解啊。過了分配判斷之后，接下來就是best fit algorithm的實(shí)現(xiàn)了。在這里，空閑塊的大小是按從小到大的順序排列的。因此，遍歷鏈表，找到第一塊比申請空間大的空閑塊即為最合適的空閑塊。然后返回這個(gè)空閑塊頭后的首地址。注意，一定是空閑塊頭后的首地址哦，要是直接將空閑塊的首地址返回的話，那用戶就會(huì)將空閑塊頭修改了。另一個(gè)要注意的地方是，要是分配出去的空閑塊的剩余空間要是比兩倍的空閑塊頭還要大，則將分配出去的這個(gè)空閑塊分割剩余的空間出來，重新放到空閑塊鏈表中。例如，初始化后只有一個(gè)空閑塊，這個(gè)空閑塊大小為17KB。經(jīng)過調(diào)整后的用戶申請空間大小為1KB，則FreeRTOS就從這個(gè)空閑塊靠近塊首的地方分割出1KB出來分配出去，剩余的16KB則重新放回空閑塊鏈表里。以便下一次繼續(xù)分配。這一個(gè)切割空閑塊的代碼如下。
/* 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 ) );
}

在上面的一段代碼里，有一個(gè)值得注意的宏prvInsertBlockIntoFreeList()。這個(gè)宏的作用是將空閑塊重新添加到空閑塊鏈表中。注意，并不能將分割出來的空閑塊放到原空閑塊的位置中，因?yàn)殒湵碇械目臻e塊是按從小到大的順序排列的，這個(gè)宏的作用就是將新空閑塊插入到合適的鏈表位置中。這是一個(gè)簡單的鏈表操作，非常簡單，也不必詳細(xì)說明了。這個(gè)宏的具體代碼如下。
/*
* 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;
}

完成以上操作后，修改剩余空閑塊空閑大小xFreeBytesRemaining，整個(gè)分配內(nèi)存的工作就差不多結(jié)束了。接下來FreeRTOS調(diào)用一個(gè)調(diào)試信息用的宏traceMALLOC()，恢復(fù)所有掛起的任務(wù)，再根據(jù)宏配置調(diào)用勾子函數(shù)vApplicationMallocFailedHook()，最后返回分配出來的空間地址pvReturn（成功時(shí)為空間地址，失敗時(shí)為NULL）。這樣整個(gè)pvPortMalloc()就結(jié)束了。
接下來要繼續(xù)剖析的是Heap_1中所沒有具體實(shí)現(xiàn)的vPortFree()。這一個(gè)函數(shù)非常地短，首先判斷要釋放的內(nèi)存是否為空。要是不為空，則尋找這個(gè)內(nèi)存空間的空閑塊頭，然后掛起所有任務(wù)，按照空閑塊頭的信息把它重新插入到空閑塊鏈表中，最后調(diào)用調(diào)試信息宏，恢復(fù)掛起的任務(wù)就結(jié)束了。其代碼如下。
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 );
}
xTaskResumeAll();
}
}

不過在仔細(xì)想想這一段代碼，我覺得這一段代碼是有點(diǎn)問題，就是判斷要釋放內(nèi)存的有效性。這里它只是很簡單地判斷傳進(jìn)來的指針是否為空而已，但是要是這個(gè)指針不為空，但卻在FreeRTOS申請的內(nèi)存堆數(shù)組之外呢？這樣的話就會(huì)修改到內(nèi)存的其它部分了，非常危險(xiǎn)的操作。因此我覺得，如果要修改的話，應(yīng)該還要加上判斷傳入進(jìn)來的地址是否在有效的地址范圍內(nèi)，如下面代碼所示。至于我這一個(gè)想法是否有問題，希望大家能討論一下，這樣我也可以從大家的討論中學(xué)習(xí)學(xué)習(xí)。
if( pv!=NULL)
{
if( pv >= &ucHeap[ pucAlignedHeap ] && pv <= &ucHeap[ pucAlignedHeap + configADJUSTED_HEAP_SIZE ] )
{
/* the operation of adding the block to the list of free blocks */
}
}

到這里，Heap_2的重點(diǎn)部分就已經(jīng)剖析完了。剩下的xPortGetFreeHeapSize()只是返回剩余堆大小而已，vPortInitialiseBlocks()實(shí)際上啥也沒實(shí)現(xiàn)，根據(jù)注釋它的作用只是防止鏈接器放警告而已。

總結(jié)：Heap_2比Heap_1的代碼更長，要剖析的知識點(diǎn)更多。一開始看的時(shí)候還覺得有點(diǎn)怕怕，怕剖著剖著就不知道怎么剖了。在剖的過程中還有很多知識點(diǎn)要翻翻課本，例如在看到最佳適配算法(best fit algorithm)時(shí)，要翻翻Andrew S. Tanenbaum寫的《Modern Operating Systems》。經(jīng)過這樣的實(shí)例剖析之后，我發(fā)覺對以前學(xué)的東西有了更深刻的理解。以前上課只是說說有這個(gè)算法而已，具體怎么實(shí)現(xiàn)卻完全沒有講。直到現(xiàn)在，我才發(fā)覺原來這個(gè)算法的真實(shí)應(yīng)用，真是另我大開眼界。以后學(xué)習(xí)的路還很長，剖析完FreeRTOS還有很長的一段距離。要繼續(xù)加油加油！