【RTOS學習】FreeRTOS中的鏈表

🐱作者：一只大喵咪1201
🐱專欄：《RTOS學習》
🔥格言：你只管努力，剩下的交給時間！

🥩FreeRTOS中的鏈表

鏈表是FreeRTOS的核心結構，它讓系統的功能正常運行，本喵下面來解釋一下FreeRTOS中的鏈表結構以及操作。

如上圖所示是FreeRTOS源碼中的鏈表的定義List_t，這是一個鏈表頭，重要的成員變量有三個：

volatile UBaseType_t uxNumberOfItems：表示鏈表中包含的節點個數。
ListItem_t * configLIST_VOLATILE pxIndex：這是一個指針變量，表示當前正在操作的節點。
MiniListItem_t xListEnd：這是一個結構體變量，從這個變量可以找到鏈表中所有節點。

如上圖所示MinListItem_t結構體定義，它也有三個重要的成員變量：

configLIST_VOLATILE TickType_t xItemValue：這是一個值，需要排序的時候才有意義，后面會見識到。
struct xLIST_ITEM * configLIST_VOLATILE pxNext：這是一個指針變量，該變量指向鏈表中的第一個鏈表項。
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious：這也是一個指針變量，該變量指向鏈表中的最后一個鏈表項。

如上圖所示是鏈表項ListItem_t的定義，它包含五個重要的成員變量：

configLIST_VOLATILE TickType_t xItemValue：該值作為鏈表項中的一個數值，在排序時才會起作用。
struct xLIST_ITEM * configLIST_VOLATILE pxNext：該指針變量指向下一個鏈表項。
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious：該指針變量指向前一個鏈表項。
void * pvOwner：這也是一個指針變量，指向該鏈表項所屬的容器。以后本喵會介紹。
struct xLIST * configLIST_VOLATILE pxContainer：這也是一個指針變量，指向該鏈表項所在的List_t類型鏈表頭。

從鏈表頭以及鏈表項的定義中就可以看出，FreeRTOS中的鏈表是一個帶頭雙向循環鏈表。

如上圖所示便是FreeRTOS中鏈表的鏈接關系，鏈表頭結構體成員xListEnd中的pxNext指向第一個鏈表項的起始地址，鏈表項中的pxNext指向下一個鏈表項的起始地址，如此下去，最后一個鏈表項中的pxNext指向鏈表頭中的xListEnd。

此時鏈表頭和鏈表項中的所有pxNext構成一個環路。

鏈表頭中的結構體成員xListEnd中的pxPrevious指向最后一個鏈表項的起始地址，該鏈表項中的pxPrevious指向前一個鏈表項，如此下去，第一個鏈表項中的pxPrevious指向鏈表頭中的xListEnd。

此時鏈表頭和鏈表項中的所有pxPrevious構成另一個環路。

如上圖所示，由于真正的指向關系不直觀，所以本喵后面使用這樣的示意圖來表示這個鏈表，要記住無論是pxNext還是pxPrevious指向的都是鏈表項的起始地址。

🥞初始化

如上圖所示鏈表初始化函數vListInitialise，在該函數中對傳入的鏈表pxList主要進行了四步操作：

讓鏈表頭中當前操作節點指針pxIndex指向自己的xListEnd。
讓xListEnd中的xItemValue = portMAX_DELAY，用該值來區別這是鏈表尾而不是鏈表項。
讓xListEnd中的pxNext和pxPrevious都指向自己的xListEnd，初步形成兩個環路。
讓uxNumberOfItems = 0表示當前鏈表中沒有鏈表項，是一個空鏈表。

此時一個初步的鏈表就形成了，操作的都是鏈表頭自己。

如上圖所示鏈表項初始化函數vListInitialiseItem，在該函數中，僅是將鏈表項中的pxContainer設置為NULL，因為此時并不知道該鏈表項屬于哪個鏈表頭。

🥞尾部插入

如上圖所示插入鏈表尾部的函數vListInsertEnd，在該函數中，總體進行了四步操作：

從鏈表頭中獲得當前正常操作的鏈表項pxIndex。
將新的鏈表項插入到pxIndex和pxIndex->pxPrevious之間。
讓新鏈表項的pxContainer = pxList，讓其找到所屬的鏈表。
將鏈表頭中記錄鏈表項個數的unNumberOfItems加一。

如上圖所示便是尾部插入新鏈表項的結果，但是它并不是插入到了尾部呀。

假設現在正在操作的是編號為2的鏈表項，所以pxIndex指向它，如果沒有新鏈表項插入的話，這幾個鏈表項的操作順序是2->3->1。

此時要插入新的鏈表項，但是并不能影響原本的操作順序，否則就破壞了公平性，所以將新的鏈表項4插入到pxIndex和pxIndex->pxPreviou之間，此時這幾個鏈表項的操作順序是2->3->1->4，并不會影響原來三個鏈表項的操作順序。

尾插時要保證公共性，插入于正在操作鏈表項pxIndex和它的前一個鏈表項pxIndex->pxPrevious之間。

上面所演示的是鏈表中已經存在鏈表項時尾插的結果，如果是一個空鏈表呢？

如上圖所示第一次尾插的結果，在插入之前pxIndex和pxIndex->pxPrevious都是指向的鏈表頭中的xListEnd，當新節點插入時，pxIndex->pxPrevious指向新節點，pxIndex->pxNext也指向新節點，新節點的pxIndex和pxPrevious都指向鏈表頭中的xListEnd。

所以說，尾插函數vListInsertEnd可以實現第一次插入和已經存在多個鏈表項時再插入新鏈表項兩個場景。

🥞按順序插入

如上圖所示按照鏈表項中的xItemValue值插入函數vListInsert，該函數中主要進行了四步操作：

獲取新插入鏈表項中的xItemValue值。
根據xItemValue值在鏈表中尋找合適位置：
- xItemValue = portMAX_DELAY說明新的鏈表項應該插入到鏈表的最后面，直接讓插入位置pxIterator等于鏈表的最后一項。
- xItemValue不是最大，則迭代尋找合適位置，pxIterator從鏈表頭開始，直到pxIterator->pxNext指向的鏈表項中的xItemValue大于新鏈表項的xItemValue，此時得到插入位置就是pxIterator后面。
插入新鏈表項，改變指向關系。
修改新鏈表項中的pxContainer，讓其屬于當前鏈表頭，并且修改鏈表頭中的鏈表項個數。

如上圖所示是插入后的結果，原本鏈表中的xItemValue從左到右依次是1->3->4，將xItemValue為2的新鏈表項插入以后，xItemValue成了1->2->3->4。

🥞刪除

如上圖所示刪除指定鏈表項的函數uxListRemove，該函數中進行的主要操作也是四步：

從要刪除的鏈表項中得到它所屬的鏈表pxList。
改變鏈表中的指向關系，讓被刪除鏈表項的前一個直接和被刪除鏈表項的后一個建立互相的指向關系。
進行判斷，如果刪除的是正在操作的鏈表項，那么需要將pxIndex指向下一個鏈表項，更換正在操作的鏈表項。
讓被刪除的鏈表項失憶，也就是將其pxContainer = NULL，讓它找不到原本所屬的鏈表，再將鏈表頭中鏈表項的個數減一，最后返回鏈表項的個數。

如上圖所示是刪除后的示意圖，所謂刪除就是改變被刪除鏈表項的前一個和后一個鏈表項的指向關系，讓其從鏈表中脫離出來。

🥩堆的管理

很多人把"堆棧"相提并論，其實"堆"、"棧"是完全沒有聯系。"棧"的作用我們前面已經講了很多，"堆"是什么？

在匯編代碼里指定一個AREA：在匯編代碼里，使用SPACE命令可以分配一段空間，這段空間就是堆：
在C代碼里，定義一個全局數組：該數組的大小是17KB，這段空間就是堆：

"堆"就是一塊或者多塊內存，我們可以從中申請一小塊內存來使用，使用完畢后可以釋放這一小塊內存。

簡單地說，一開始，"堆"是一些空閑內存，我們可以：

使用malloc函數從中申請、獲得一小塊內存
使用free函數釋放這一小塊內存
這些malloc、free函數就是用來管理這些內存的
malloc、free函數可以有其他名稱，比如FreeRTOS里是pvPortMalloc、vPortFree。

在FreeRTOS的源碼中，默認提供了5個文件，對應內存管理的5種方法：

文件	優點	缺點
heap_1.c	分配簡單，時間確定	只分配、不回收
heap_2.c	動態分配、最佳匹配	碎片、時間不定
heap_3.c	調用標準庫函數	速度慢、時間不定
heap_4.c	相鄰空閑內存可合并	可解決碎片問題、時間不定
heap_5.c	在heap_4基礎上支持分隔的內存塊	可解決碎片問題、時間不定

只能使用上訴五種方式的中的一種來管理堆，其中heap_3.c由于使用的是標準庫函數中的malloc和free，速度比較慢，所以本喵這里也不做介紹，只介紹其他四種。

🥞heap_1.c

如上圖所示在堆區上申請空間的函數pvPortMalloc，其中xWantedSize是要申請的空間大小，申請過程主要分為四步：

創建返回地址pvReturn和對齊地址pucAlignedHeap，讓這兩個指針都為0。
對申請的空間大小進行對齊。

如上圖所示宏定義#define portBYTE_ALIGNMENT 8規定了8字節對齊，什么是字節對齊呢？

如上圖所示，假設現在有9個字節的空間在內存中連續排列，而我們的CPU是32位的，也就是說一次讀取或者寫入數據必須操作的是4字節大小的空間。

現在一共9字節，操作兩次以后還剩下一個字節，再操作時仍然是4字節，所以要想操作第9個字節，就會額外多操作三個字節，此時就會導致效率低下。

甚至有的CPU并不支持這種不對齊訪問。

由于是8字節對齊，所以申請的空間大小必須是8的整數倍，如果不符合8字節對齊，就需要向上對齊，如申請100個字節，實際上申請的是對齊后的104字節。

找到堆區的對齊地址pucAlignedHeap

如上圖所示，假設整個堆區ucHeap在內存上的起始地址是0x20000001，按照CPU每次操作4字節的規律，該地址無論如何也無法作為單次CPU的起始地址，所以操作起來不方便。

按照代碼中所寫，所以對齊地址求出來就是0x20000008，該地址一定是CPU操作時4字節中的起始地址。

此時對齊地址pucAlignedHeap就是指向這里，而且讓xNextFreeByte + = xWantedSize，得到此次申請空間大小。

獲取申請空間

如上圖所示，如果是第一次申請空間，那么最后返回的就是對齊地址pucAlignedHeap所指向的地址，如果不是第一次申請，那么在pucAlignedHeap基礎上增加上次空間大小的偏移量pxNextFreeByte得到的就是返回地址。

簡單來說，heap_1管理堆的方式就是，通過pucAlignedHeap和pxNextFreeByte兩個全局變量，每申請一次，就返回上一次申請后剩余空間的起始位置。

如上圖釋放動態空間函數vPortFree，并不支持釋放空間。

heap_1.c里，只能用pvPortMalloc函數來申請空間，無法使用vPortFree函數來釋放空間。

🥞heap_2.c

heap_2.c里，使用鏈表來管理內存。鏈表結構體為：

這個結構體用來表示空閑塊：

pxNextFreeBlock：指向下一個空閑塊
xBlockSize：當前空閑塊的內存大小

如上圖所示，在這個結構體后面，緊跟著空閑內存。

在堆空間static uint8_t ucHeap[ configTOTAL_HEAP_SIZE ]上，空閑空間往前偏移8個字節就得到BlockLink_t結構體的起始地址。

初始化：

如上圖所示堆的初始化函數prvHeapInit，在該文件中定義了兩個BlockLink_t類型的全局變量，一個是鏈表頭xStart，另一個是鏈表尾xEnd，在該函數中主要進行四步操作：

從整個堆空間上計算對齊地址pucAlignedHeap。
讓鏈表頭xStart中的pxNextFreeBlock指向對齊地址，并且將鏈表頭中的xBlockSize = 0，因為鏈表頭并不管理空閑內存。
讓鏈表尾xEnd中的pxNextFreeBlock指向空，xBlockSize = configADJUSTED_HEAP_SIZE，這是堆的最大值，為了排序時方便才這樣設計的。
讓pxFirstFreeBlock指向對齊地址，并且構造BlockLink_t中的成員，讓xBlockSize = configADJUSTED_HEAP_SIZE，pxNextFreeBlock指向鏈表尾。

如上圖所示初始化完成的結果，此時在整塊堆空間的中，最前面的8字節就是BlockLink_t結構體，包含該空間的大小，并鏈入了管理空閑堆空間的鏈表中。

分配內存：

如上圖所示分配空間函數pvPortMalloc的部分代碼，主要進行了四步操作：

如果是第一次調用pvPortMalloc，則先對整個堆區進行初始化，讓整個堆區作為空閑空間鏈入到空閑空間管理鏈表xStart和xEnd之間。
對申請的空間大小進行對齊計算。
從空閑空間管理鏈表中尋找合適的空間塊。
- 假設此時鏈表中存在多個含有BlockLink_t的空閑塊，所以根據要申請空間的大小迭代找到比申請空間大的空閑塊。
通過鏈表找到的是空閑塊的起始地址，包含BlockLink_t，所以向后偏移8個字節，得到該空閑塊的對齊地址作為返回值供申請者使用。

如上圖，返回的是該空閑塊中紅色箭頭指向的地址。

如上圖所示的緊接著前面pvPortMalloc函數剩下的代碼，主要有四步操作，本喵這里接著前面從標號5開始講解：

將尋找到的空閑塊從空閑鏈表中移除，也就是修改該塊前后的指向關系。
如果找到的這塊空間大于所申請的字節數，將用不了的部分賦值給pxNewBlockLink。
構造用不了的那部分塊中的BlockLink_t結構體。
調用prvInsertBlockIntoFreeList將這個剩余的塊作為空閑塊插入到管理鏈表中。

如上圖所示prvInsertBlockIntoFreeList宏函數，用來插入空閑內存塊到管理鏈表中，主要操作分為三步：

獲取插入內存塊的大小xBlockSize。
根據大小xBlcokSize迭代按照升序找到合適的插入位置pxIterator。
將內存塊pxBlockToInsert插入到pxIterator之后。

如上圖所示是最終分配效果，Block1從管理鏈表中移除，供申請者使用，Blcok2是用不了剩下的部分，重新鏈入到管理鏈表中。

釋放內存：

如上圖所示釋放內存函數vPortFree，主要操作有兩步：

由于傳入的pv是申請者使用的地址，所以向前偏移8個字節得到該內存塊的BlcokLink_t地址。
調用pxBlockToInsert將該內存塊鏈入到管理鏈表中。

如上圖所示，假設釋放的是Block1內存塊，此時該內存塊和原本的Block2一起在管理鏈表中。

heap_2管理的鏈表，支持內存的申請和釋放。
由于釋放的內存塊直接鏈入到管理鏈表，所以如果再次申請的內存比上次釋放的大，那么釋放的這塊就無法再次利用，就會存在內存碎片。
所以heap_2適合用在頻繁申請和釋放固定大小內存的場景。

🥞heap_4.c

初始化：

如上圖所示是使用prvHeapInit初始化完的示意圖，heap_4整體上和heap_2的管理方式一樣，也是通過鏈表和BlockLink_t來管理空閑內存塊，但是不一樣的是：

鏈表尾xEnd位于整個堆空間的末尾，它并不是獨立的一個變量，而是依附在空閑空間上。
鏈表尾xEnd中的xBlockSize = 0，和heap_2中的configADJUSTED_HEAP_SIZE不一樣。

分配內存：

如上圖所示，分配內存時和heap_2一樣，將Block1中管理鏈表中移除，將用不完的Block2部分再次鏈入到鏈表中，返回值也是Block1的對齊地址。

在將用不了的內存塊重新鏈入到管理鏈表中時，也會調用prvInsertBlockIntoFreeList函數，heap_4和heap_2的區別就在這個函數中。

釋放內存：

釋放內存時，和heap_2一樣，也會調用到prvInsertBlockIntoFreeList函數來將釋放的內存塊鏈入到管理鏈表，來分析一下這個函數：

如上圖所示prvInsertBlockIntoFreeList的部分代碼，這里進行的操作就是尋找合適的插入位置。

沒有獲取插入內存塊的大小。
迭代時按照內存塊的地址尋找，當插入內存塊pxBlockToInsert的地址小于等于pxIterator->pxNextFreeBlock時，將內存塊插入到pxIterator后面。

如上圖所示prvInsertBlockIntoFreeList中緊接前面部分的后續代碼，進行的操作主要分為3步：

在尋找到插入位置pxIterator以后，先判斷插入內存塊pxBlockToInsert和其前面的pxIterator是否緊挨著(pxIterator的地址 + 偏移量 == pxBlockToInsert的地址)。
- 如果相等，說明pxBlockToInsert和pxIterator緊挨著，可以進行合并，此時改變pxBlockToInsert的大小xBlockSize和pxNextFreeBlock覆蓋pxIterator。
再判斷判斷插入內存塊pxBlockToInsert和其后面的pxIterator->pxNextFreeBlock是否緊挨著(pxBlockToInsert的地址 + 偏移量 == pxIterator->pxNextFreeBlock的地址)。
- 如果相等，說明 pxBlockToInsert和pxIterator->pxNextFreeBlock是緊挨著，可以進行合并，同樣僅修改pxBlockToInsert的BlockLink_t覆蓋pxIterator->pxNextFreeBlock即可。