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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了加快請(qǐng)求速度，一些分配器基于免費(fèi)塊的鏈接列表。這樣可以節(jié)省一些時(shí)間，因?yàn)樗阉骺梢员苊饪紤]所有正在使用的塊。但是，這種方法確實(shí)有一個(gè)缺點(diǎn)。如果只將空閑塊保存在列表中，則很難將它們?nèi)窟B續(xù)放置在內(nèi)存中;此問(wèn)題會(huì)阻止分配器獲取兩個(gè)相鄰的中等塊并將它們放在一起（或合并它們）以構(gòu)建一個(gè)更大的塊。

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

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

當(dāng)前實(shí)現(xiàn)：ADIalloc

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

基本原則

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

圖3.ADIalloc的箱/塊配置。

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

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

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

黑鰭金槍魚特有的是什么

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

外部存儲(chǔ)器Lext體積大，使用成本更低，但訪問(wèn)延遲更高。

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

L2在價(jià)格和速度方面介于兩者之間。但是，可以通過(guò)將其緩存到 L1 中來(lái)提高其速度。緩存是一個(gè)額外的維度。

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

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

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

分配器的靈活性

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

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

圖5.通過(guò) ADIalloc 進(jìn)行堆棧分配。

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

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

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

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

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

使用內(nèi)存分配器時(shí)的常見(jiàn)問(wèn)題是分配器導(dǎo)致的低效率以及未正確分配和釋放內(nèi)存的風(fēng)險(xiǎn)，主要導(dǎo)致內(nèi)存泄漏。

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

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

圖7.如何跟蹤已被遺忘的免費(fèi)。

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

免費(fèi)塊僅包含特殊代碼

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

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

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

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

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

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

分配器更加有用，因?yàn)樗梢耘c包裝器一起交付，該包裝器負(fù)責(zé)為特定模塊運(yùn)行所有可能的內(nèi)存配置，同時(shí)節(jié)省所需的周期數(shù)。這有助于了解無(wú)法為特定緩沖區(qū)獲得最快內(nèi)存對(duì)周期的影響。

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

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

圖 10.單元測(cè)試流程圖。

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

結(jié)論

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

審核編輯：郭婷