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

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

這是關于 eheap 的三篇文章系列中的第一篇：

? eheap 第 1 部分：配置

? eheap 第 2 部分：增強調試

? eheap 第 3 部分：自我修復

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

嵌入式系統特性

eheap 設計用于以下方面：

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

? 預計永遠運行。

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

? 高優先級任務必須能夠搶占并快速運行。

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

? 每個嵌入式系統的堆要求范圍相對較窄。

? 嵌入式系統有大量空閑時間。

? 嵌入式系統對自我修復的需求不斷增長。

bin 配置

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

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

小型系統示例

小型系統可能有一個 bin 大小的數組，如圖 1 所示。

［圖 1］

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

上垃圾箱搜索

eheap 和 dlmalloc 在 SBA 方面是相似的。兩者都針對非常快速的訪問進行了優化，這是面向對象程序通常需要的。主要區別在于 UBA，其中 dlmalloc 在 free（） 操作期間構建樹以指導 malloc（） 操作期間的最佳分配。樹節點鏈接巧妙地存儲在塊本身中。

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

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

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

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

【圖2】

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

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

［圖 3］

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

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

［圖 4］

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

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

Donor chunk

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

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

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

? 基于緩存的系統的小塊本地化。

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

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

塊合并和泄漏箱

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

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

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

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

概括

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

審核編輯：郭婷