什麼是適用於嵌入式系統的C內存分配器？

Question

我有一個單線程的嵌入式應用程序，可以分配和取消分配很多很多的小塊（32-64b）。基於緩存的分配器的完美場景。儘管我可以嘗試寫一篇，但這可能會浪費時間，而且還沒有經過良好的測試和調整，因爲一些解決方案已經在前線。

那麼什麼是我可以用於這種情況的最佳分配器？

注意：我在系統中使用了一個Lua虛擬機（這是80 +％分配的罪魁禍首），所以我不能輕易重構我的代碼以使用堆棧分配來提高分配性能。

Answer 1

我最近在這個話題上做了一些研究，因爲我們有內存碎片問題。最後，我們決定繼續使用GNU libc的實現，並在必要時添加一些應用程序級內存池。還有其他的分配器具有更好的分裂行爲，但是我們不滿意他們在全球取代malloc。 GNU的背後有着悠久的歷史。

在你的情況下，似乎有理由;假設你無法修復虛擬機，那麼這些微小的分配是非常浪費的。我不知道你的整個環境是什麼，但是你可能會考慮把調用包裝到只有虛擬機的malloc/realloc/free上，以便將它傳遞給爲小池設計的處理程序。

Answer 2

在C編寫的一個過去的項目中，我們走上了實現我們自己的內存管理例程的道路，該例程適用於運行在包括嵌入式系統在內的各種平臺上的庫。該庫還分配並釋放了大量小緩衝區。它運行得相對較好，並且不需要大量的代碼來實現。如果你想自己開發一些東西，我可以給你一些背景知識。

基本實現包括一組管理設置大小的緩衝區的例程。這些例程被用作malloc（）和free（）的包裝器。我們使用這些例程來管理我們經常使用的結構的分配，並管理設置大小的通用緩衝區。一個結構被用來描述被管理的每種類型的緩衝區。當分配了特定類型的緩衝區時，我們將malloc（）存儲在塊中（如果空閒緩衝區列表爲空）。 IE中，如果我們管理10個字節的緩衝區，我們可能會爲包含100個這些緩衝區的空間創建一個malloc（），以減少碎片以及所需的底層malloc數量。

在每個緩衝區的前端會有一個指針，用來鏈接空閒列表中的緩衝區。當分配100個緩衝區時，每個緩衝區將在空閒列表中鏈接在一起。當緩衝區正在使用時，指針將被設置爲空。我們還維護了一個緩衝區「塊」的列表，以便我們可以通過在每個實際的malloc'd緩衝區上調用free（）來做一個簡單的清理。

爲了管理動態緩衝區大小，我們還在每個緩衝區的開始處添加了一個size_t變量，告訴緩衝區的大小。然後這被用來識別哪個緩衝區塊在釋放時將緩衝區放回。我們有用於malloc（）和free（）的替換例程，它們執行指針運算來獲取緩衝區大小，然後將緩衝區放入空閒列表中。我們也對我們管理的緩衝區有多大限制。大於此限制的緩衝區只是malloc'd並傳遞給用戶。對於我們管理的結構，我們創建了用於分配和釋放特定結構的包裝例程。

最終我們還演化了系統，以便在用戶請求清理未使用的內存時包含垃圾收集。由於我們可以控制整個系統，因此我們可以通過各種優化來提高系統的性能。正如我提到的那樣，它確實工作得很好。

Answer 3

雖然我問了這個問題有一段時間，但我的最終解決方案是使用LoKi的SmallObjectAllocator，它工作的很好。擺脫了所有的操作系​​統調用並改善了我的Lua引擎對於嵌入式設備的性能。非常好，簡單，只需5分鐘的工作！

Answer 4

由於version 5.1，Lua已允許在creating new states時設置custom allocator。

Answer 5

我也想補充一點，即使它是一箇舊線程。在嵌入式應用程序中，如果您可以分析應用程序的內存使用情況並提供最大數量的不同大小的內存分配，通常最快的分配器類型是使用內存池的分配器。在我們的嵌入式應用程序中，我們可以確定運行時所需的所有分配大小。如果你能做到這一點，你可以完全消除堆碎片並且分配速度非常快。大多數這些實現都有一個溢出池，它會爲特殊情況做一個正常的malloc，如果你做了分析的話，這些特殊情況下希望是遠遠少之又少。

Answer 6

我已經在vxworks下使用'binary buddy'系統來取得良好效果。基本上，通過將塊切割成一半以獲得兩塊大小最小的塊以滿足您的要求，當塊被釋放時，您可以將樹合併，將塊合併到一起以緩解碎片。谷歌搜索應該會顯示你需要的所有信息。

Answer 7

我有點遲到了，但我想和大家分享非常高效的內存分配用於嵌入式系統的，我最近發現並測試：https://github.com/dimonomid/umm_malloc

這是一個內存管理庫專門設計的，使用ARM7，我個人使用它在PIC32器件上，但它可以在任何16位和8位器件上工作（我計劃在16位PIC24上測試，但我還沒有測試過）

我被默認分配器的碎片嚴重毆打：我的項目經常分配不同大小的塊，從幾個字節到幾百個字節，有時我面臨'內存不足'的錯誤。我的PIC32器件總共有32K的RAM，8192字節用於堆。在特定時刻有超過5K的空閒內存，但由於碎片，默認分配程序具有最大非碎片內存塊，只有大約700字節。這太糟糕了，所以我決定尋找更有效的解決方案。我已經知道了一些分配器，但它們都有一些限制（例如塊大小應該是一個2或2，並且不是從2開始，而是從128個字節開始），或者只是越野車。每次之前，我都不得不切換回默認的分配器。

但是這一次，我很幸運：我發現這一個：http://hempeldesigngroup.com/embedded/stories/memorymanager/

當我試圖此內存分配器，在完全相同的情況下的空閒內存5K，有超過3800個字節塊！這對我來說太難以置信了（相比700字節），並且我進行了嚴格測試：設備工作超過30個小時。沒有內存泄漏，一切正常，因爲它應該工作。 我還在FreeRTOS存儲庫中發現了這個分配器：http://svnmios.midibox.org/listing.php?repname=svn.mios32&path=%2Ftrunk%2FFreeRTOS%2FSource%2Fportable%2FMemMang%2F&rev=1041&peg=1041#，這個事實是umm_malloc穩定性的另一個證據。 所以我完全切換到了umm_malloc，我對它很滿意。

我只是不得不改變它一點：當宏UMM_TEST_MAIN沒有被定義時，配置有點麻煩，所以我創建了github庫（鏈接在這篇文章的頂部）。現在，依賴於用戶的配置存儲在單獨的文件umm_malloc_cfg中。h

我在這個分配器中應用的算法還沒有深入，但它對算法有非常詳細的解釋，所以任何有興趣的人都可以查看umm_malloc.c文件的頂部。至少，「分箱」方法應該在較少的碎片中給予巨大的好處：http://g.oswego.edu/dl/html/malloc.html

我相信任何需要高效的微控制器內存分配器的人都應該試試這個。

Answer 8

我正在寫一個名爲tinymem的C內存分配器，目的是能夠對堆進行碎片整理，並重新使用內存。檢查出來：

https://github.com/vitiral/tinymem

注：此項目已停止對鏽實施工作：

https://github.com/vitiral/defrag-rs

另外，我沒有聽說過umm_malloc之前。不幸的是，它似乎無法處理碎片，但它看起來非常有用。我將不得不檢查出來。