許多嵌入式系統(tǒng)不使用堆。許多確實(shí)使用堆的人使用必須按順序搜索的串行堆，因此可能非常慢。大多數(shù)其他嵌入式系統(tǒng)可能使用廣泛可用的dlmalloc，它以無(wú)法更改的固定結(jié)構(gòu)為代價(jià)提供快速操作。

一個(gè)名為eheap的新嵌入式堆在這些極端情況之間提供了一個(gè)中間地帶。它為在 RTOS 上運(yùn)行或獨(dú)立運(yùn)行的嵌入式系統(tǒng)提供高性能、適應(yīng)性和安全性。eheap 旨在為特定的嵌入式系統(tǒng)輕松定制。它符合 malloc（）、free（）、realloc（） 和 calloc（） 的 ANSI C 標(biāo)準(zhǔn)，并為堆控制和安全提供附加功能。

這是關(guān)于 eheap 的三篇文章系列中的第一篇：

? eheap 第 1 部分：配置

? eheap 第 2 部分：增強(qiáng)調(diào)試

? eheap 第 3 部分：自我修復(fù)

eheap 是一種 bin 類(lèi)型的堆，類(lèi)似于 dlmalloc。假設(shè)讀者熟悉這種類(lèi)型的堆結(jié)構(gòu)，或者對(duì)這些堆如何操作的細(xì)節(jié)不感興趣。因此，這篇文章和后續(xù)文章將討論 eheap 的獨(dú)特之處，而不是它的工作原理。對(duì)于那些想要更詳細(xì)信息的人，請(qǐng)參閱eheap 與 dlmalloc。

嵌入式系統(tǒng)特性

eheap 設(shè)計(jì)用于以下方面：

? 范圍廣泛的 RAM 大小，從非常小到大。

? 預(yù)計(jì)永遠(yuǎn)運(yùn)行。

? 需要高性能和確定性操作。

? 高優(yōu)先級(jí)任務(wù)必須能夠搶占并快速運(yùn)行。

? 小代碼量通常是必要的。

? 每個(gè)嵌入式系統(tǒng)的堆要求范圍相對(duì)較窄。

? 嵌入式系統(tǒng)有大量空閑時(shí)間。

? 嵌入式系統(tǒng)對(duì)自我修復(fù)的需求不斷增長(zhǎng)。

bin 配置

與其他 bin 類(lèi)型的堆一樣，eheap 有一個(gè)用于小塊的小型 bin 數(shù)組 （SBA） 和一個(gè)用于大塊的上部 bin 數(shù)組 （UBA）。SBA 就像一組塊池，但速度不快。與 dlmalloc 不同，UBA 中的 bin 大小是連續(xù) 2 字節(jié)的冪（256、512 等），eheap 允許選擇 bin 大小以適合應(yīng)用程序。eheap bin 大小由一個(gè)恒定的bin 大小數(shù)組確定，由程序員指定。對(duì)于小 bin，bin 大小是 bin 的塊大小。［1］ 對(duì)于大 bin，bin 大小是 bin 中的最小塊大小。一個(gè) bin 的最大塊大小是下一個(gè) bin 的大小 – 8.［2］

為了安全起見(jiàn)，bin 大小數(shù)組可以位于 ROM 中，也可以位于本地 RAM 中以獲得更高的性能。堆初始化函數(shù)使用它來(lái)創(chuàng)建 eheap 所需的 bin 和所有相關(guān)變量?？梢酝ㄟ^(guò)更改 bin 大小數(shù)組中的值、重新編譯和重新啟動(dòng)應(yīng)用程序來(lái)快速重新配置堆。這種快速重新配置支持一種啟發(fā)式方法來(lái)調(diào)整 eheap 以獲得特定系統(tǒng)的最佳性能。

小型系統(tǒng)示例

小型系統(tǒng)可能有一個(gè) bin 大小的數(shù)組，如圖 1 所示。

［圖 1］

對(duì)于這個(gè)系統(tǒng)，SBA 由 bin 0、1 和 2 組成，分別保存大小為 24、32 和 40 的塊；bin3 包含從 48 到 120 的 10 個(gè)尺寸；bin4 是一個(gè)只包含大小為 128 的小 bin；bin 5 包含從 136 到 248 的 14 個(gè)尺寸；和 bin6 ，頂部 bin，包含從 264 開(kāi)始的所有大小。-1 標(biāo)記大小數(shù)組的結(jié)尾。在這個(gè)特定的嵌入式系統(tǒng)中，對(duì)小塊的需求是有限的，對(duì)中等塊有一些需求，而對(duì) 264 字節(jié)以上的大塊的需求很少。請(qǐng)注意，為 128 字節(jié)的塊添加了一個(gè)小 bin，這些塊在此系統(tǒng)中經(jīng)常使用。

上垃圾箱搜索

eheap 和 dlmalloc 在 SBA 方面是相似的。兩者都針對(duì)非?？焖俚脑L問(wèn)進(jìn)行了優(yōu)化，這是面向?qū)ο蟪绦蛲ǔＰ枰?。主要區(qū)別在于 UBA，其中 dlmalloc 在 free（） 操作期間構(gòu)建樹(shù)以指導(dǎo) malloc（） 操作期間的最佳分配。樹(shù)節(jié)點(diǎn)鏈接巧妙地存儲(chǔ)在塊本身中。

對(duì)于 eheap，每個(gè) bin 都有一個(gè)適合該 bin 的空閑塊列表。在 free（） 操作期間，如果塊大于 bin 的第一個(gè)塊，則將其放在 bin 空閑列表的末尾；否則，將其放在 bin 空閑列表的開(kāi)頭。在空閑時(shí)間，大的 bin 空閑列表按增加的塊大小進(jìn)行排序。在 malloc（） 操作期間，會(huì)在大的 bin 空閑列表中搜索第一個(gè)足夠大的塊，這也是最合適的。

eheap 最適合具有偏好塊大小并且不使用廣泛的塊大小的系統(tǒng)。如上例所示，可以在 UBA 中放入一個(gè)小 bin 以提供常用尺寸。實(shí)現(xiàn)此結(jié)果的另一種方法是使大的 bin 大小等于經(jīng)常使用的塊大小。那么最適合的將始終是 bin 中的第一個(gè)塊，然后是更大的尺寸。

在某種程度上，大型垃圾箱就像已排序的迷你串行堆一樣運(yùn)行。過(guò)多的搜索時(shí)間可能會(huì)受到箱大小與系統(tǒng)需求的明智選擇以及對(duì)合并的明智使用的限制，如下所述。堆設(shè)計(jì)的一個(gè)原則是處理更大的塊需要更長(zhǎng)的時(shí)間，因此更長(zhǎng)的 malloc（） 時(shí)間不會(huì)降低平均性能。當(dāng)然， malloc（） 不能花費(fèi)太長(zhǎng)時(shí)間以致更高優(yōu)先級(jí)的任務(wù)錯(cuò)過(guò)它們的截止日期。

圖 2 顯示了一個(gè) bin 堆示例。

【圖2】

在這種情況下，沒(méi)有SBA也沒(méi)有UBA，只有top bin。此堆接近串行類(lèi)型堆，但仍比它具有優(yōu)勢(shì)。

圖 3 顯示了一個(gè)沒(méi)有 SBA 堆的示例。

［圖 3］

用 C 編寫(xiě)的嵌入式系統(tǒng)可能對(duì)小塊幾乎沒(méi)有用處，或者，塊池可能更適合特定系統(tǒng)中的小塊。在這種情況下，bin 0 以 24 開(kāi)頭，因?yàn)楸仨毟采w 24 字節(jié)及以上的所有大小，但 bin 0 可能僅用于 64 字節(jié)及更大的塊。 ［3］

圖 4 顯示了一個(gè)沒(méi)有 UBA 堆的示例。

［圖 4］

在這個(gè)堆中，SBA 覆蓋大小為 24 到 64 的塊，所有其他塊進(jìn)入 bin 6，覆蓋 72 個(gè)字節(jié)及以上。

幾乎無(wú)限的堆配置是可能的。目前，為了獲得最佳性能，eheap 限制為 32 個(gè) bin。如果更多的 bin 被證明對(duì)某些嵌入式系統(tǒng)有益，則可以增加此限制。

Donor chunk

eheap 有一個(gè)可選的donor chunk （dc），它類(lèi)似于dlmalloc 的指定犧牲塊（dvc），但操作方式不同并且服務(wù)于不同的目的：

? 快速小塊分配的初始源。

? 將小塊分離到下堆，將大塊分離到上堆。

? 基于緩存的系統(tǒng)的小塊本地化。

如果啟用，則 dc 的空間將由程序員在頂部塊 （tc） 下方分配。通常，它只是總初始可用空間的一小部分，它是 dc 和 tc 的組合。如果用于分配小塊的選定 SBA 箱為空，則從 dc 中分割該塊，而不是從下一個(gè)較大的占用箱中取出它。這不僅更快，而且還避免了減少更大的垃圾箱。由于 dc 最初是堆的較低部分，因此小塊將來(lái)自較低的堆。這改善了小塊分配的本地化，并且還傾向于按塊大小隔離堆，以幫助減少使用中的小塊，以免阻塞大塊的合并。

在堆使用一段時(shí)間后，小塊分配將主要來(lái)自 SBA 箱，很少來(lái)自 dc。此時(shí)可以關(guān)閉使用 dc 并將剩余的內(nèi)容釋放到垃圾箱中。或者，可以繼續(xù)使用 dc。當(dāng)下面和相鄰的已釋放塊合并到其中時(shí)，它會(huì)增長(zhǎng)，并且隨著從中分配塊，它會(huì)縮小。這將提高空 SBA 箱的性能。

塊合并和泄漏箱

dlmalloc 和 eheap 之間的一個(gè)重要區(qū)別是 dlmalloc 總是合并相鄰的空閑塊，而 eheap 允許延遲合并。eheap 合并由其cmerge 模式控制，應(yīng)用程序可以打開(kāi)或關(guān)閉該模式。在堆初始化之后它是關(guān)閉的。

延遲合并的原因是塊合并會(huì)產(chǎn)生泄漏的 bin。例如，假設(shè)一個(gè) 24 字節(jié)的塊被釋放到 bin 0，而物理上相鄰的 48 字節(jié)的空閑塊駐留在 bin 3。如果啟用合并，這些塊將被合并成一個(gè) 72 字節(jié)的塊，該塊將被放入bin 6。如果應(yīng)用程序需要 24 和 48 字節(jié)的塊而不是 72 字節(jié)的塊，這不利于獲得最佳性能。此外，在 free（） 操作期間，將 48 字節(jié)塊出列并合并它需要額外的時(shí)間。如果后續(xù) malloc（） 獲取 72 字節(jié)塊，將其拆分為 24 和 48 字節(jié)塊以獲取其中任何一個(gè)，然后將剩余部分重新排隊(duì)，則這是浪費(fèi)時(shí)間。

與可能使用多種塊大小的一般處理不同，嵌入式系統(tǒng)傾向于使用有限的塊大小。因此，泄漏箱對(duì)于嵌入式系統(tǒng)來(lái)說(shuō)不是最佳的。

cmerge可以直接控制也可以自動(dòng)控制。如果自動(dòng)模式amerge為 ON，則當(dāng)可用空間低于下限時(shí)， cmerge 將打開(kāi)，當(dāng)可用空間高于上限時(shí)，它將關(guān)閉。限制由配置常數(shù)決定。或者，可以使用空閑塊的數(shù)量、平均空閑塊大小或 bin 中的總空間，這取決于在特定系統(tǒng)中最有效的方法。

概括

eheap 是一種新的嵌入式堆，可以通過(guò)調(diào)整 bin 大小數(shù)組，決定是否使用 dc 以及它應(yīng)該多大，以及決定是否使用延遲合并以及如果使用，如何控制它。這些選項(xiàng)允許將eheap調(diào)整到特定系統(tǒng)，以實(shí)現(xiàn)最佳系統(tǒng)性能，而不會(huì)出現(xiàn)碎片導(dǎo)致分配失敗。eheap 可免費(fèi)用于非商業(yè)用途。

審核編輯：郭婷