典型的DSP通常具有少量快速片上存儲器。微控制器通常可以訪問更大的外部存儲器。Blackfin處理器具有分層內存架構，結合了兩種方法的優點，提供具有不同性能級別的多個級別的內存。對于需要最大確定性的應用，它可以在單個內核時鐘周期內訪問片內SRAM。對于代碼大小較大的系統，可以使用更大的片上和片外存儲器，但延遲會增加。

就其本身而言，此層次結構僅具有中等實用性;今天的高速處理器通常以慢得多的速度運行，因為較大的應用程序只能容納較慢的外部存儲器。為了提高性能，程序員可以選擇手動將密鑰代碼移入和移出內部SRAM。此外，在架構中添加數據和指令緩存使外部存儲器更易于管理。緩存減少了指令和數據手動移動到處理器內核的過程。這極大地簡化了編程模型，無需擔心管理進入內核的數據和指令流。

雖然Blackfin的存儲器用途廣泛且易于在許多應用中使用，但在某些應用中，例如嵌入式手機系統，任何嵌入式處理器的內存分配都可能很困難。在這種應用中，指令高速緩存不能提供與手動移入和移出SRAM相同的代碼管理級別。本文建議使用動態內存分配工具來應對這一挑戰。

為移動電話平臺開發協議棧和應用軟件的一個基本要素是系統中內存資源的高效處理。過去，內存資源是“手動”分配給系統內的每一段代碼;但是，視頻和語音識別等模塊數量的增加使得使用這種方法的解決方案在優化方面更具挑戰性。動態內存分配器可用于在大型應用程序中分配和釋放內存，無需手動管理此任務。本文描述了動態內存分配的一些原則，并演示了一個特定的實現，該實現考慮了整體系統考慮因素以及Blackfin內存劃分為具有各種屬性（價格，速度，雙訪問可能性）的不同空間。

內存管理解決方案

在大型嵌入式應用中，可以實現多種內存管理方法。主要方法如下所述。

堆疊。所有變量和緩沖區都可以簡單地在函數之上聲明。它們存儲在堆棧空間中，并且僅在退出函數時釋放該空間。該解決方案的主要缺點是堆棧增長，例如，堆棧在函數的生命周期內不斷增長。它的生存期有時可能很長，因為函數可能是遞歸的和/或可中斷的。

手動重疊。另一種流行的解決方案包括使用在鏈接階段定義的部分對緩沖區地址進行硬編碼。這比在堆棧中分配更靈活一些，因為它允許內存重疊。如果兩個模塊永遠不會相互中斷，則它們的臨時內存可以共享相同的內存部分。然而，隨著模塊數量的增加，對于集成系統來說，這種解決方案確實變得難以管理。此外，其他內存問題（例如不適當的重疊或給定部分的緩沖區大小不足）可能很難跟蹤。更糟糕的是，當需要新功能需要兩個以前從未及時重疊的功能來同時運行時，情況就更加困難了。圖 1 顯示了一個基于重疊的手動實現示例。

圖1.手動重疊內存。

動態分配。 動態分配可實現內存重疊：一旦不需要內存空間，就會釋放內存空間并可以重用。與堆棧分配方法不同，動態分配不會導致不受控制的內存空間增加。實際上，函數使用的內存在不需要時會立即釋放，而不是等待函數結束。

開發動態內存分配器時要考慮哪些功能？

動態內存分配器由兩個函數組成：一個分配內存空間;另一個釋放內存。分配會保留一些空間來處理內存請求。調用 free 函數后，將釋放保留的空間，并可用于滿足進一步的請求。例如，讓我們構建一個非常基本的動態內存分配器來理解這段代碼必須處理的所有權衡。我們將從一些基本定義開始，然后描述分配器。

塊。假設分配器可以為所需的內存提供大內存空間的塊。很容易理解，不能拿走整個空間來滿足第一個請求。相反，初始內存空間可以拆分為不同大小的不同塊。

標頭。當發出內存請求時，我們如何知道給定的片段足夠大？大小必須保存在內存中的某個地方。一種解決方案是將其保存在塊內的標頭中。這是內存開銷的一個元素。此外，標頭中至少需要有一個位專用于指示塊是空閑的還是正在使用的。

在塊中徘徊。如果第一個塊太小，我們如何跳轉到下一個塊？如果所有塊在內存中都是連續的，則知道塊的大小就足以跳轉到下一個塊。另一種解決方案包括保留指向標頭中下一個塊的指針 - 這是鏈表的原則。

找到合適的。我們如何選擇哪個空閑塊將服務于請求？一個必要的條件是找到一個大小至少為所需大小的空閑塊。然后可以使用滿足此要求的第一個塊。此策略稱為“先擬合”。另一個策略（最合適的策略）包括查找可以容納請求的最小可用塊。這是動態內存分配器必須處理的最具挑戰性的困境：速度與內存大小。第一次適合的速度很快，但可能會導致巨大的記憶損失，而找到最佳適合的替代方案需要時間。通過使用多個塊（bins）鏈表可以達成折衷，其中每個列表都有其相似大小的塊。最適合的策略選擇數據桶，而第一次適合的策略選擇數據桶中的區塊。

碎片化。另一種解決方案包括使用首次適合策略，并釋放大于請求的區塊末尾。此解決方案的一個缺點是，內存很快由幾個分散的未使用內存塊（大小不同，通常很小）組成。由于產生的可用空間很小，未來的分配很困難。這種情況稱為內存碎片。

為了加快請求速度，一些分配器基于免費塊的鏈接列表。這樣可以節省一些時間，因為搜索可以避免考慮所有正在使用的塊。但是，這種方法確實有一個缺點。如果只將空閑塊保存在列表中，則很難將它們全部連續放置在內存中;此問題會阻止分配器獲取兩個相鄰的中等塊并將它們放在一起（或合并它們）以構建一個更大的塊。

圖2.動態分配器的示例。

現在，我們已經介紹了所有的概念和折衷方案，以了解為Blackfin移動電話系統設計的分配器：ADIalloc。

當前實現：ADIalloc

信號處理功能（例如新的視頻和音頻標準）的不斷增加促使人們開發一種稱為ADIalloc的分配器，用于手機應用。它旨在通過避免不必要的內存重疊來幫助縮短使用處理器的產品的上市時間，并通過減少峰值內存使用量來降低成本。

基本原則

當前的實現更側重于速度性能而不是內存開銷。內存被分區到箱中。每個箱都包含大小相等的內存塊。箱中的塊具有連續的地址，允許從一個塊快速跳轉到下一個塊。查找適合請求的區塊的策略最適合 bin 和 bin-first fit in - 這意味著第一個空閑塊，因為所有塊的大小相同。此外，選擇箱中塊的大小是為了便于找到最佳箱：它們都由 2 的冪相關。bin （N+1） 中的塊是 bin N 中塊大小的兩倍（bin N 也可以包含 0 個塊......

圖3.ADIalloc的箱/塊配置。

某些軟件模塊有時可能需要一個“大”塊。但是，如果允許大塊，則內存將被分區為非常少的塊。最好不要有一個大塊，最好有兩個較小的塊，在少數需要的情況下合并在一起形成一個大塊。因此，允許將兩個塊合并在一起。

為了保證速度，每個塊都有一個標頭，指示它是否可用并合并。對于合并的塊，合并的同伴或“伙伴”的大小保留在標頭中。這用于在這對夫婦被釋放時快速恢復好友的標題。

圖4.ADIalloc 中的區塊。

黑鰭金槍魚特有的是什么

Blackfin為內存分配器增加了另一個維度：它的數據內存空間被劃分為幾個內存級別。內存級別在價格、速度和雙訪問可能性方面具有不同的特征：

外部存儲器Lext體積大，使用成本更低，但訪問延遲更高。

片上存儲器L1具有快速訪問功能。它本身分為不同的銀行和子銀行，允許從不同的子銀行同時訪問兩項數據（雙重訪問）。

L2在價格和速度方面介于兩者之間。但是，可以通過將其緩存到 L1 中來提高其速度。緩存是一個額外的維度。

堆疊。雖然（如前所述）在堆棧中分配所有變量不是一個好的解決方案，但仍然需要一個堆棧。對于小型緩沖區、循環計數器和索引，由于分配而丟失周期是沒有意義的。然而，在系統集成階段之前，某些緩沖區的分配（堆棧或動態）可能存在一些不確定性。這就是為什么堆棧被視為額外的內存級別。

緩存。如上所述，Blackfin可以將L2內存緩存到L1或L1的一部分中。在這種情況下，最好不必將分配器的代碼重新調整到新的內存中。在初始化期間，分配器能夠從一些專用的Blackfin寄存器中讀取緩存配置，然后決定其箱和塊。然而，由于分配器必須在任何平臺上進行測試，因此它必須保持最低限度的Blackfin特異性。只有讀取數據緩存配置是特定于 Blackfin 的。除此之外，分配器可以在帶有Blackfin以外的編譯器的PC上進行全面測試。唯一的區別是內存資源的選擇與平臺的速度或雙訪問功能無關。

憑借上述所有功能，ADIalloc成為一款重要的軟件。因此，只要這不會過度影響循環次數，它應該盡可能“靈活”。

分配器的靈活性

宏。C宏廣泛用于ADIalloc實現。事實上，ADIalloc本身就是一個宏。第一個好處是能夠快速將一個分配器替換為另一個分配器，而無需重寫調用 ADIalloc 的所有軟件。例如，這可用于研究不同動態分配器的性能。

阿洛卡。宏的另一個優點是能夠將 Stack 用作內存級別，而不必以比使用 malloc 更復雜的方式調用分配器。實際上，在 Stack 中分配無法通過函數調用來實現。相反，當使用 Stack 作為內存級別調用 ADIalloc 時，將執行“alloca”。（大多數編譯器都提供 Alloca。它僅在執行 alloca 指令時保留堆棧上的空間 — 這與函數頂部的堆棧上的聲明不同，后者為函數生存期保留空間。宏 ADIalloc 測試所需的內存級別，并將其重定向到分配器或對分配器的函數調用，ADI_alloc。

圖5.通過 ADIalloc 進行堆棧分配。

存儲所需的內存級別。能夠處理Blackfin上的不同內存級別是一個非常大的優勢。為了充分利用此功能，內存級別在編譯時不是固定的。因此，對于每個分配，分配器允許測試不同的內存級別，而無需重寫或重新編譯軟件模塊的 C 代碼。軟件模塊附帶一個表，其中包含此類或此類分配所需的內存級別。表的內容可以在運行時更改，就像在特定地址寫入新的所需內存級別一樣簡單。然而，應該注意的是，如果無法提供所需的內存級別，分配器會選擇另一個級別 - 就內存訪問速度而言最接近的級別。

圖6.輸入表：所需的內存級別。

更改箱/塊配置。ADIalloc的另一個靈活功能是能夠更改箱和塊配置，而無需重新編譯分配器的代碼。實際上，定義此配置的所有變量都保存在表中。在初始化期間讀取表。可以隨時更改表的內容，這將在下次調用初始化時修改 bins/chunks 配置。不必在編譯時修復拆分的箱/塊，作為下一個功能，可以在分配器周圍有一個智能包裝器來動態調整內存大小。我們還可以想到一個系統運行兩個需要兩種不同內存配置的連續任務。任務完成后，將使用最適合第二個任務的配置調用分配器初始化。

最后，ADIalloc有兩種形式：第一種用于開發和集成，第二種用于最終產品。在開發過程中，調試功能是必需的。下一節將提供有關當前實現以及如何充分利用調試功能的更多詳細信息。

調試功能如何改進實現

使用內存分配器時的常見問題是分配器導致的低效率以及未正確分配和釋放內存的風險，主要導致內存泄漏。

分配器知道內存分區。它還知道請求的內存量以及哪些內存地址可用。這允許開發調試功能以采取措施避免內存泄漏。

跟蹤已被遺忘的免費。內存泄漏的第一個原因是在分配了內存但從未釋放時。這很容易預防。在調試模式下（不是在正常模式下，因為此測試需要許多周期），分配器會生成內存使用情況的統計信息。如果上一個報告顯示某些內存空間仍在使用中，則表示已忘記空閑空間。為了更深入地跟蹤問題，可以使用另一個報告，其中包含緩沖區名稱，它們的地址，以及它們是否被釋放或分配（每次調用分配器或free函數時都會生成報告）。

圖7.如何跟蹤已被遺忘的免費。

跟蹤使用的空間是否超過保留的空間。另一種類型的泄漏發生在緩沖區分配的空間少于其所需空間，并開始使用已分配給它的空間之外的空間時。在調試模式下，分配器使用特殊代碼（該代碼成為“真實”基準面的可能性非常低）“標記”所有可用內存空間。它不僅標記空閑塊，而且還包括分配不需要的塊中的所有地址。在每個分配的塊中，所需的大小也保留為分配的塊的一部分。因此，每次輸入分配器（對于新分配或免費分配）時，它都會驗證：

免費塊僅包含特殊代碼

分配的塊包含所需大小和塊末尾之間的特殊代碼

執行此檢查的函數也可以在分配器外部隨時調用。當發現泄漏時，將生成消息并將其傳遞到另一個模塊，該模塊以一種或另一種形式輸出（屏幕，特殊的可視化工具，用于實時分析的高速記錄器等）。

圖8.用于跟蹤分配器消息的查看器示例（泄漏情況）。

幫助選擇箱/塊配置。分配器調試功能還可以部分解決有關分配器效率低下的問題。在調試模式下，分配器保存諸如所需內存與分配的內存、每個箱使用的塊數等數據。這提供了一種簡單的方法來避免效率低下，例如使用一些從未使用的箱大小。

圖9.捕獲的數據有助于選擇最佳箱/塊配置。

內存級別之間的內存重新分區。一個很大的問題是如何在不同的軟件之間分配內存級別。顯然，快速存取存儲器最適合每一段代碼。然而，由于這種記憶是有限的，因此必須做出選擇。只有在將整個軟件模塊內置到系統中后，才能做出此選擇。通常，時間關鍵型任務需要最快的內存。分配器可以協助做出此類選擇。

分配器更加有用，因為它可以與包裝器一起交付，該包裝器負責為特定模塊運行所有可能的內存配置，同時節省所需的周期數。這有助于了解無法為特定緩沖區獲得最快內存對周期的影響。

表一. 業績匯總表

表中顯示的數字表示與參考配置相比，在新配置中運行單元測試所需的周期數的差異。參考配置是模塊編寫器默認提供的配置。PASS 表示對新配置運行單元測試的結果與運行引用配置的結果相同。參考循環次數為：128078。

圖 10.單元測試流程圖。

包裝器運行軟件模塊單元測試 （UT）。第一次運行它時，要求分配器返回指針的名稱以及它查找內存級別的表的地址。收集需要查找內存級別的所有地址后，包裝器會針對所有可能的內存配置重新運行 UT。

結論

當前的ADIalloc實現是動態內存分配器的一種可能實現。它的使用表明，當前實現最有用的功能是調試功能。它們減少了與動態分配相關的風險（特別是滲漏的風險）。同時，它們有助于更好地管理復雜的內存結構。現在，在手機應用程序中，在Blackfin中添加新的軟件模塊變得更加容易，而無需重新設計模塊之間的內存劃分。

審核編輯：郭婷