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

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

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

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

內(nèi)存管理解決方案

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

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

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

圖1.手動重疊內(nèi)存。

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

開發(fā)動態(tài)內(nèi)存分配器時要考慮哪些功能？

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

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

標頭。當發(fā)出內(nèi)存請求時，我們?nèi)绾沃澜o定的片段足夠大？大小必須保存在內(nèi)存中的某個地方。一種解決方案是將其保存在塊內(nèi)的標頭中。這是內(nèi)存開銷的一個元素。此外，標頭中至少需要有一個位專用于指示塊是空閑的還是正在使用的。

在塊中徘徊。如果第一個塊太小，我們?nèi)绾翁D(zhuǎn)到下一個塊？如果所有塊在內(nèi)存中都是連續(xù)的，則知道塊的大小就足以跳轉(zhuǎn)到下一個塊。另一種解決方案包括保留指向標頭中下一個塊的指針 - 這是鏈表的原則。

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

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

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

圖2.動態(tài)分配器的示例。

現(xiàn)在，我們已經(jīng)介紹了所有的概念和折衷方案，以了解為Blackfin移動電話系統(tǒng)設計的分配器：ADIalloc。

當前實現(xiàn)：ADIalloc

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

基本原則

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

圖3.ADIalloc的箱/塊配置。

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

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

圖4.ADIalloc 中的區(qū)塊。

黑鰭金槍魚特有的是什么

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

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

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

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

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

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

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

分配器的靈活性

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

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

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

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

圖6.輸入表：所需的內(nèi)存級別。

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

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

調(diào)試功能如何改進實現(xiàn)

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

分配器知道內(nèi)存分區(qū)。它還知道請求的內(nèi)存量以及哪些內(nèi)存地址可用。這允許開發(fā)調(diào)試功能以采取措施避免內(nèi)存泄漏。

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

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

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

免費塊僅包含特殊代碼

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

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

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

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

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

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

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

表一. 業(yè)績匯總表

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

圖 10.單元測試流程圖。

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

結(jié)論

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

審核編輯：郭婷