在嵌入式系統(tǒng)設(shè)計(jì)過(guò)程中，許多軟件工程師受困于動(dòng)態(tài)內(nèi)存管理。本文介紹一種將堆棧中的內(nèi)存碎片降至少的解決方案，其中講到了內(nèi)存碎片和內(nèi)存丟失的區(qū)別，以及一種在編程中有利于檢測(cè)并消除內(nèi)存丟失的策略。

    標(biāo)準(zhǔn)C庫(kù)函數(shù)malloc()和free()可在任意的時(shí)間段中，為應(yīng)用分配任意大小的內(nèi)存塊。隨著內(nèi)存塊的使用和釋放，在整個(gè)內(nèi)存區(qū)域中，分配給堆棧的存儲(chǔ)區(qū)將混雜著許多正在使用或已經(jīng)釋放的存儲(chǔ)塊，而未被使用的任何小塊內(nèi)存區(qū)將變得無(wú)法使用。例如，某個(gè)應(yīng)用要求堆棧分配30字節(jié)，如果堆棧中只有20個(gè)長(zhǎng)度為3字節(jié)的小存儲(chǔ)塊(總共為60字節(jié))，那么堆棧仍然無(wú)法為該應(yīng)用分配內(nèi)存，因?yàn)樗璧?0字節(jié)必須是連續(xù)的。

    在執(zhí)行時(shí)間較長(zhǎng)的程序中，內(nèi)存碎片可能導(dǎo)致系統(tǒng)的內(nèi)存枯竭，盡管分配的內(nèi)存總量并未超出總的可用內(nèi)存總數(shù)。內(nèi)存碎片的數(shù)量取決于堆棧的實(shí)現(xiàn)策略。大多數(shù)程序員均采用由編譯器提供的malloc()和free()函數(shù)創(chuàng)建的堆棧，因此內(nèi)存碎片就不受程序員的控制。

    內(nèi)存丟失是應(yīng)用程序的缺陷，更具體地，內(nèi)存丟失是一塊已經(jīng)分配但永遠(yuǎn)不會(huì)被釋放的內(nèi)存區(qū)。如果所有指向內(nèi)存塊的指針超出界限或者指向其他的區(qū)域，那么應(yīng)用程序?qū)⒂肋h(yuǎn)不能釋放那塊內(nèi)存區(qū)。對(duì)于將會(huì)在某時(shí)刻退出的桌面應(yīng)用程序，較小的內(nèi)存丟失還可以承受，因?yàn)橥顺鲞M(jìn)程將把占用的所有內(nèi)存返還給操作系統(tǒng)。但對(duì)于長(zhǎng)時(shí)間運(yùn)行的嵌入式系統(tǒng)，則通常需要確保沒(méi)有內(nèi)存丟失。

    避免內(nèi)存丟失不是輕而易舉的，為了確保所有分配的內(nèi)存都在隨后釋放，必須建立一套明確的規(guī)則，以確定哪個(gè)應(yīng)用占用了內(nèi)存。為跟蹤內(nèi)存，可采用類(lèi)、指針數(shù)組或鏈表。由于在動(dòng)態(tài)內(nèi)存分配中，程序員無(wú)法預(yù)先知道在給定時(shí)間內(nèi)需要分配多少數(shù)據(jù)塊，因此通常需要采用鏈表結(jié)構(gòu)。

    例如，假定一個(gè)任務(wù)正在接收來(lái)自通信信道的消息，任務(wù)將為消息分配空間，而該空間在消息得到完整的處理之前不會(huì)被釋放。因?yàn)橄⒂锌赡懿粫?huì)按照接收的順序進(jìn)行處理，因此一些消息存在的時(shí)間將比其他消息更長(zhǎng)。所有掛起的消息存在于一個(gè)列表中，列表的長(zhǎng)度取決于任意給定時(shí)間內(nèi)進(jìn)行處理的消息數(shù)目。嵌入式系統(tǒng)必須將消息轉(zhuǎn)發(fā)至另外的設(shè)備，而且消息在收到傳送確認(rèn)之前不能被刪除。由于消息將傳送至許多不同的目的地，而且某些目的地可能存在一些導(dǎo)致重傳的故障，因此不能以先入先出方式處理這些消息。

    在上述問(wèn)題中，動(dòng)態(tài)內(nèi)存管理對(duì)RAM的利用效率高于預(yù)定義緩存管理。當(dāng)內(nèi)存不再被消息隊(duì)列使用時(shí)，就能被其他隊(duì)列或完全不同的程序部分使用。

    當(dāng)多個(gè)指針同時(shí)指向某個(gè)特定的內(nèi)存塊時(shí)，通常還會(huì)產(chǎn)生另一個(gè)特殊問(wèn)題。如果個(gè)實(shí)體(entity)占有內(nèi)存并希望釋放該內(nèi)存，那么必須考慮是否還有其他指針指向該區(qū)域。如果存在，那么隨著個(gè)實(shí)體釋放內(nèi)存，其他的指針將成為懸掛指針(dangling pointer)，即該指針指向的空間不再有效。當(dāng)使用懸掛指針時(shí)，或許仍然可以得到正確的數(shù)據(jù)，但這些內(nèi)存終將被重新使用(通過(guò)另一個(gè)malloc()調(diào)用)，從而導(dǎo)致在懸掛指針和該內(nèi)存的新使用者之間出現(xiàn)不期望的相互影響。

    懸掛指針與內(nèi)存丟失剛好相反。如果沒(méi)有釋放內(nèi)存，就可能導(dǎo)致內(nèi)存丟失；而如果釋放了那些并不準(zhǔn)備釋放的內(nèi)存則將產(chǎn)生懸掛指針。

    內(nèi)存丟失在許多方面與競(jìng)爭(zhēng)條件非常相似。內(nèi)存丟失引發(fā)的性能失常完全不同于程序錯(cuò)誤，因此，這些問(wèn)題很難通過(guò)調(diào)試器對(duì)代碼進(jìn)行單步調(diào)試加以解決。對(duì)于內(nèi)存丟失和競(jìng)爭(zhēng)條件，代碼檢查有時(shí)能比采用任何技術(shù)解決方案更快地找到問(wèn)題所在。

    添加調(diào)試代碼并生成輸出通常比源代碼調(diào)試器更為有效，但在某些競(jìng)爭(zhēng)條件下，則有可能改變代碼的執(zhí)行特性，從而掩蓋了問(wèn)題。在內(nèi)存丟失中，添加調(diào)試代碼可改變內(nèi)存配置，這意味著懸掛指針故障可能具有不同的執(zhí)行特性。另一缺陷在于，如果調(diào)試代碼消耗了內(nèi)存，那么調(diào)試版將比產(chǎn)品版更快地耗盡RAM，內(nèi)存丟失就是內(nèi)存丟失，而不管這些調(diào)試代碼的副作用如何，都應(yīng)當(dāng)可被檢測(cè)。

    驅(qū)動(dòng)自動(dòng)碎片收集

    Java具有對(duì)無(wú)用存儲(chǔ)單元進(jìn)行碎片收集(garbage collection)的自動(dòng)內(nèi)存管理機(jī)制，因此Java程序員無(wú)須擔(dān)心內(nèi)存分配的釋放。如果以前曾用過(guò)Java進(jìn)行編程，那么與其他編程語(yǔ)言相比，無(wú)疑會(huì)對(duì)Java跟蹤內(nèi)存所需的時(shí)間留下深刻的印象。

    在Java中，只需犧牲運(yùn)行時(shí)間即可換來(lái)編程的簡(jiǎn)化，因?yàn)槭止す芾韮?nèi)存可以得到更為有效的實(shí)現(xiàn)方法。但當(dāng)程序變得越來(lái)越大，手工管理就變得無(wú)能為力了。雖然好的手工管理通常能使堆棧的總長(zhǎng)度降至小，但這并不總是輕而易舉的。在那些通常由數(shù)十名程序員完成的大型程序中，人為錯(cuò)誤將引入足以降低性能等級(jí)的大量?jī)?nèi)存丟失，這時(shí)就需要自動(dòng)碎片收集解決方案。

    在對(duì)無(wú)用存儲(chǔ)單元進(jìn)行自動(dòng)碎片收集過(guò)程中，一個(gè)的程序員或許做得遠(yuǎn)比自動(dòng)碎片收集器出色，但在需要眾多程序員參與的大型項(xiàng)目中，則幾乎不可能找到并修正所有的內(nèi)存丟失。選擇自動(dòng)系統(tǒng)或許要求對(duì)性能進(jìn)行折衷，而且自動(dòng)碎片收集器有時(shí)也會(huì)出現(xiàn)混亂。Dobb博士在www.ddj.com 網(wǎng)站的“Java Q&A”上列出了許多靈活利用Java進(jìn)行無(wú)用存儲(chǔ)單元收集的方法。

    盡管自動(dòng)碎片收集對(duì)超大型程序的吸引力日益增強(qiáng)，但大多數(shù)嵌入式開(kāi)發(fā)人員開(kāi)發(fā)的系統(tǒng)并沒(méi)有那么復(fù)雜。而在這些開(kāi)發(fā)中，只有極少數(shù)開(kāi)發(fā)人員需要接入包含無(wú)用存儲(chǔ)單元自動(dòng)碎片收集的編程環(huán)境，如Perl、Smalltalk或Java，因此大多數(shù)開(kāi)發(fā)人員需要知道如何在采用malloc()和free()的C程序或采用new和delete的C++程序中跟蹤內(nèi)存丟失。

    檢測(cè)工具

    查找內(nèi)存丟失的工具很多，常用的釋放工具就是dmalloc和mpatrol，這些工具提供了記錄并檢查所有內(nèi)存分配的調(diào)試版堆棧，從而有利于分析內(nèi)存丟失和懸掛指針。dmalloc和許多類(lèi)似的庫(kù)還為malloc()和free()提供了一些不同情形下的替代形式。

    在許多項(xiàng)目中，我負(fù)責(zé)跟蹤內(nèi)存丟失并提供所有內(nèi)存丟失均已消除的證明。初，我假定上面提及的一種工具可解決我的問(wèn)題。然而，實(shí)際發(fā)現(xiàn)malloc()和free()的一種完全替代并不總是適用于嵌入式系統(tǒng)。例如，軟件工程師可能對(duì)當(dāng)前的實(shí)現(xiàn)相當(dāng)滿(mǎn)意，而只想簡(jiǎn)單地添加一些監(jiān)控功能。如果選擇了替代malloc()和free()的庫(kù)，那么就不得不移植這些例行程序。

    因?yàn)榭捎玫淖杂蓭?kù)是面向Unix的，因而可通過(guò)調(diào)用sbrk()從操作系統(tǒng)獲取內(nèi)存塊。有些操作系統(tǒng)中并沒(méi)有這個(gè)調(diào)用(甚至實(shí)際上都沒(méi)有操作系統(tǒng))。在移植時(shí)，對(duì)于特定的處理器必須提及諸如指針大小和內(nèi)存對(duì)齊這樣的問(wèn)題。本文用的編譯器庫(kù)中的malloc()和free()已經(jīng)解決了這些問(wèn)題，即編譯器庫(kù)已完全移植到正在使用的處理器上，因此希望避免這樣的重復(fù)工作。對(duì)調(diào)試版malloc()和free()進(jìn)行移植的另一問(wèn)題在于，調(diào)試版通常假定可以將分析數(shù)據(jù)存入一個(gè)文件中。但本文工作的系統(tǒng)通常并不包含任何有效的文件系統(tǒng)，因此必須限制存儲(chǔ)到只帶有少資源的設(shè)備上的數(shù)據(jù)量。

    我也曾考慮利用現(xiàn)有的工具在臺(tái)式機(jī)上運(yùn)行部分代碼。Compuware公司的Bounds Checker就是這樣的工具，該工具專(zhuān)門(mén)針對(duì)窗視操作系統(tǒng)，但在特殊情形下，本文用的代碼是標(biāo)準(zhǔn)的ANSI C，因此可以簡(jiǎn)單地在PC上進(jìn)行編譯并結(jié)合Bounds Checker庫(kù)運(yùn)行。Bounds Checker工具也將檢查Win32 API的諸多部分，但只對(duì)堆棧分配感興趣。

    結(jié)果是讓人失望的，Bounds Checker面臨的障礙就在于該工具必須在程序退出后才能遞交報(bào)告。在程序退出之前尚未釋放的數(shù)據(jù)將被視為內(nèi)存丟失。盡管這是一個(gè)合理定義，但并不適用于我的應(yīng)用程序，因?yàn)榕cPC應(yīng)用程序不同，嵌入式程序通常無(wú)需退出。

    我用的代碼包含一個(gè)連續(xù)執(zhí)行的循環(huán)，為實(shí)現(xiàn)本測(cè)試的目的，可以在循環(huán)的末尾添加一些校驗(yàn)，以人為地退出程序。但不釋放所有的內(nèi)存資源而中斷程序?qū)?dǎo)致Bounds Checker指示所有正在使用的內(nèi)存此時(shí)正發(fā)生丟失。大多數(shù)內(nèi)存只是簡(jiǎn)單地等待，以便在下一次循環(huán)中重新得到使用。只需要編寫(xiě)一個(gè)釋放所有內(nèi)存的退出程序段，就能使Bounds Checker獲得更好的性能，但這樣的程序段無(wú)法在實(shí)時(shí)系統(tǒng)中運(yùn)行并將掩蓋實(shí)際存在的問(wèn)題。

    由此可以得到如下結(jié)論：一旦明確了哪行代碼存在疑問(wèn)，就能用Bounds Checker標(biāo)識(shí)出特定內(nèi)存丟失的精確來(lái)源，因此要關(guān)注Bounds Checker的整體性能。

    假定隨著程序的運(yùn)行，緩存鏈表數(shù)將增大或減少。因?yàn)殒湵砜墒钩绦蛘业矫總€(gè)緩存，因此可以在任意時(shí)間釋放所有的緩存。如果程序存在漏洞，使一個(gè)應(yīng)當(dāng)移除并釋放的緩存仍然留在鏈表中，那么鏈表將無(wú)限增長(zhǎng)。如果程序刪除整個(gè)鏈表，那么漏洞的痕跡將消失得無(wú)影無(wú)蹤，而鏈表重新開(kāi)始記錄。在需要運(yùn)行很長(zhǎng)時(shí)間的系統(tǒng)中，鏈表終將變得很大，直到耗盡所有的內(nèi)存。

    即便采用無(wú)用存儲(chǔ)自動(dòng)碎片收集器管理內(nèi)存，類(lèi)似的漏洞仍將成為障礙，因?yàn)閲?yán)格地講，額外的緩存并不是內(nèi)存丟失，它們?nèi)钥梢允栈亍榻鉀Q這類(lèi)問(wèn)題，我們希望確定總的內(nèi)存使用率是否正在增加，而不管這些內(nèi)存是否已經(jīng)釋放，或者是否可能釋放這些內(nèi)存。

    內(nèi)存使用率的測(cè)量

    如果需要修改malloc()，理想情況下應(yīng)當(dāng)采用不同的名稱(chēng)取代所有的malloc()調(diào)用。我將其取名為mmalloc()，意即“measured malloc”。這樣我們就能編寫(xiě)一個(gè)執(zhí)行一些額外工作并調(diào)用常規(guī)malloc()的函數(shù)，這也可以通過(guò)其他途徑實(shí)現(xiàn)，如采用#define取代malloc()，或在編譯庫(kù)中利用鏈接程序重命名malloc()函數(shù)。

    這種方法的一個(gè)缺陷在于，不能對(duì)從我無(wú)法更改或重新編譯的庫(kù)函數(shù)中調(diào)用的malloc()進(jìn)行監(jiān)控。例如，標(biāo)準(zhǔn)庫(kù)包含一個(gè)依次調(diào)用malloc()的函數(shù)strdup()，我們無(wú)法用malloc()調(diào)用加以取代，除非我們擁有正在使用的庫(kù)的源代碼。

    測(cè)量使用率的步是簡(jiǎn)單地添加需要分配的內(nèi)存并減去任何已經(jīng)釋放的內(nèi)存。對(duì)于malloc()，這當(dāng)然微不足道。假定定義了一個(gè)靜態(tài)值G_inUse，那么下面的代碼就能跟蹤內(nèi)存的分配：
==========================
void *mmalloc(size_t size){
G_inUse += size;
return malloc(size);
}
==========================

    mfree()略微復(fù)雜一些，因?yàn)閒ree()并不傳遞表示內(nèi)存大小的變量。函數(shù)free()傳遞指向內(nèi)存塊的指針。通常表示釋放內(nèi)存大小的量隱藏在指針?biāo)赶驍?shù)據(jù)塊之前的數(shù)據(jù)頭中，所以可以得到下面的函數(shù)：
==========================
void mfree(void *p)
{
size_t *sizePtr=((size_t *) p)-1;
G_inUse -= *sizePtr;
free(p);
}
==========================

    因?yàn)樵卺尫胚^(guò)程中或許不會(huì)使用這種轉(zhuǎn)換，或者需要在略微不同的偏移位置存儲(chǔ)表示釋放內(nèi)存大小的量，因此這種方法是無(wú)法移植的。

    釋放的內(nèi)存大小或許并不與分配的內(nèi)存匹配，malloc()的某些實(shí)現(xiàn)方法向上舍入為接近的一個(gè)值。例如，如果要求分配11字節(jié)，而實(shí)際上卻接收到了12字節(jié)。在這種情況下，12將存儲(chǔ)在數(shù)據(jù)頭中。因此分配和釋放的數(shù)據(jù)塊就能通過(guò)使用G_inUse－1實(shí)現(xiàn)平衡。