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

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

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

? eheap 第 1 部分：配置

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

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

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

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

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

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

? 預(yù)計永遠運行。

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

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

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

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

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

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

bin 配置

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

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

小型系統(tǒng)示例

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

［圖 1］

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

上垃圾箱搜索

eheap 和 dlmalloc 在 SBA 方面是相似的。兩者都針對非常快速的訪問進行了優(yōu)化，這是面向?qū)ο蟪绦蛲ǔＰ枰摹Ｖ饕獏^(qū)別在于 UBA，其中 dlmalloc 在 free（） 操作期間構(gòu)建樹以指導(dǎo) malloc（） 操作期間的最佳分配。樹節(jié)點鏈接巧妙地存儲在塊本身中。

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

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

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

圖 2 顯示了一個 bin 堆示例。

【圖2】

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

圖 3 顯示了一個沒有 SBA 堆的示例。

［圖 3］

用 C 編寫的嵌入式系統(tǒng)可能對小塊幾乎沒有用處，或者，塊池可能更適合特定系統(tǒng)中的小塊。在這種情況下，bin 0 以 24 開頭，因為必須覆蓋 24 字節(jié)及以上的所有大小，但 bin 0 可能僅用于 64 字節(jié)及更大的塊。 ［3］

圖 4 顯示了一個沒有 UBA 堆的示例。

［圖 4］

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

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

Donor chunk

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

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

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

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

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

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

塊合并和泄漏箱

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

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

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

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

概括

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

審核編輯：郭婷