在嵌入式系統設計過程中，許多軟件工程師受困于動態內存管理。本文介紹一種將堆棧中的內存碎片降至少的解決方案，其中講到了內存碎片和內存丟失的區別，以及一種在編程中有利于檢測并消除內存丟失的策略。

    標準C庫函數malloc()和free()可在任意的時間段中，為應用分配任意大小的內存塊。隨著內存塊的使用和釋放，在整個內存區域中，分配給堆棧的存儲區將混雜著許多正在使用或已經釋放的存儲塊，而未被使用的任何小塊內存區將變得無法使用。例如，某個應用要求堆棧分配30字節，如果堆棧中只有20個長度為3字節的小存儲塊(總共為60字節)，那么堆棧仍然無法為該應用分配內存，因為所需的30字節必須是連續的。

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

    內存丟失是應用程序的缺陷，更具體地，內存丟失是一塊已經分配但永遠不會被釋放的內存區。如果所有指向內存塊的指針超出界限或者指向其他的區域，那么應用程序將永遠不能釋放那塊內存區。對于將會在某時刻退出的桌面應用程序，較小的內存丟失還可以承受，因為退出進程將把占用的所有內存返還給操作系統。但對于長時間運行的嵌入式系統，則通常需要確保沒有內存丟失。

    避免內存丟失不是輕而易舉的，為了確保所有分配的內存都在隨后釋放，必須建立一套明確的規則，以確定哪個應用占用了內存。為跟蹤內存，可采用類、指針數組或鏈表。由于在動態內存分配中，程序員無法預先知道在給定時間內需要分配多少數據塊，因此通常需要采用鏈表結構。

    例如，假定一個任務正在接收來自通信信道的消息，任務將為消息分配空間，而該空間在消息得到完整的處理之前不會被釋放。因為消息有可能不會按照接收的順序進行處理，因此一些消息存在的時間將比其他消息更長。所有掛起的消息存在于一個列表中，列表的長度取決于任意給定時間內進行處理的消息數目。嵌入式系統必須將消息轉發至另外的設備，而且消息在收到傳送確認之前不能被刪除。由于消息將傳送至許多不同的目的地，而且某些目的地可能存在一些導致重傳的故障，因此不能以先入先出方式處理這些消息。

    在上述問題中，動態內存管理對RAM的利用效率高于預定義緩存管理。當內存不再被消息隊列使用時，就能被其他隊列或完全不同的程序部分使用。

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

    懸掛指針與內存丟失剛好相反。如果沒有釋放內存，就可能導致內存丟失；而如果釋放了那些并不準備釋放的內存則將產生懸掛指針。

    內存丟失在許多方面與競爭條件非常相似。內存丟失引發的性能失常完全不同于程序錯誤，因此，這些問題很難通過調試器對代碼進行單步調試加以解決。對于內存丟失和競爭條件，代碼檢查有時能比采用任何技術解決方案更快地找到問題所在。

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

    驅動自動碎片收集

    Java具有對無用存儲單元進行碎片收集(garbage collection)的自動內存管理機制，因此Java程序員無須擔心內存分配的釋放。如果以前曾用過Java進行編程，那么與其他編程語言相比，無疑會對Java跟蹤內存所需的時間留下深刻的印象。

    在Java中，只需犧牲運行時間即可換來編程的簡化，因為手工管理內存可以得到更為有效的實現方法。但當程序變得越來越大，手工管理就變得無能為力了。雖然好的手工管理通常能使堆棧的總長度降至小，但這并不總是輕而易舉的。在那些通常由數十名程序員完成的大型程序中，人為錯誤將引入足以降低性能等級的大量內存丟失，這時就需要自動碎片收集解決方案。

    在對無用存儲單元進行自動碎片收集過程中，一個的程序員或許做得遠比自動碎片收集器出色，但在需要眾多程序員參與的大型項目中，則幾乎不可能找到并修正所有的內存丟失。選擇自動系統或許要求對性能進行折衷，而且自動碎片收集器有時也會出現混亂。Dobb博士在www.ddj.com 網站的“Java Q&A”上列出了許多靈活利用Java進行無用存儲單元收集的方法。

    盡管自動碎片收集對超大型程序的吸引力日益增強，但大多數嵌入式開發人員開發的系統并沒有那么復雜。而在這些開發中，只有極少數開發人員需要接入包含無用存儲單元自動碎片收集的編程環境，如Perl、Smalltalk或Java，因此大多數開發人員需要知道如何在采用malloc()和free()的C程序或采用new和delete的C++程序中跟蹤內存丟失。

    檢測工具

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

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

    因為可用的自由庫是面向Unix的，因而可通過調用sbrk()從操作系統獲取內存塊。有些操作系統中并沒有這個調用(甚至實際上都沒有操作系統)。在移植時，對于特定的處理器必須提及諸如指針大小和內存對齊這樣的問題。本文用的編譯器庫中的malloc()和free()已經解決了這些問題，即編譯器庫已完全移植到正在使用的處理器上，因此希望避免這樣的重復工作。對調試版malloc()和free()進行移植的另一問題在于，調試版通常假定可以將分析數據存入一個文件中。但本文工作的系統通常并不包含任何有效的文件系統，因此必須限制存儲到只帶有少資源的設備上的數據量。

    我也曾考慮利用現有的工具在臺式機上運行部分代碼。Compuware公司的Bounds Checker就是這樣的工具，該工具專門針對窗視操作系統，但在特殊情形下，本文用的代碼是標準的ANSI C，因此可以簡單地在PC上進行編譯并結合Bounds Checker庫運行。Bounds Checker工具也將檢查Win32 API的諸多部分，但只對堆棧分配感興趣。

    結果是讓人失望的，Bounds Checker面臨的障礙就在于該工具必須在程序退出后才能遞交報告。在程序退出之前尚未釋放的數據將被視為內存丟失。盡管這是一個合理定義，但并不適用于我的應用程序，因為與PC應用程序不同，嵌入式程序通常無需退出。

    我用的代碼包含一個連續執行的循環，為實現本測試的目的，可以在循環的末尾添加一些校驗，以人為地退出程序。但不釋放所有的內存資源而中斷程序將導致Bounds Checker指示所有正在使用的內存此時正發生丟失。大多數內存只是簡單地等待，以便在下一次循環中重新得到使用。只需要編寫一個釋放所有內存的退出程序段，就能使Bounds Checker獲得更好的性能，但這樣的程序段無法在實時系統中運行并將掩蓋實際存在的問題。

    由此可以得到如下結論：一旦明確了哪行代碼存在疑問，就能用Bounds Checker標識出特定內存丟失的精確來源，因此要關注Bounds Checker的整體性能。

    假定隨著程序的運行，緩存鏈表數將增大或減少。因為鏈表可使程序找到每個緩存，因此可以在任意時間釋放所有的緩存。如果程序存在漏洞，使一個應當移除并釋放的緩存仍然留在鏈表中，那么鏈表將無限增長。如果程序刪除整個鏈表，那么漏洞的痕跡將消失得無影無蹤，而鏈表重新開始記錄。在需要運行很長時間的系統中，鏈表終將變得很大，直到耗盡所有的內存。

    即便采用無用存儲自動碎片收集器管理內存，類似的漏洞仍將成為障礙，因為嚴格地講，額外的緩存并不是內存丟失，它們仍可以收回。為解決這類問題，我們希望確定總的內存使用率是否正在增加，而不管這些內存是否已經釋放，或者是否可能釋放這些內存。

    內存使用率的測量

    如果需要修改malloc()，理想情況下應當采用不同的名稱取代所有的malloc()調用。我將其取名為mmalloc()，意即“measured malloc”。這樣我們就能編寫一個執行一些額外工作并調用常規malloc()的函數，這也可以通過其他途徑實現，如采用#define取代malloc()，或在編譯庫中利用鏈接程序重命名malloc()函數。

    這種方法的一個缺陷在于，不能對從我無法更改或重新編譯的庫函數中調用的malloc()進行監控。例如，標準庫包含一個依次調用malloc()的函數strdup()，我們無法用malloc()調用加以取代，除非我們擁有正在使用的庫的源代碼。

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

    mfree()略微復雜一些，因為free()并不傳遞表示內存大小的變量。函數free()傳遞指向內存塊的指針。通常表示釋放內存大小的量隱藏在指針所指向數據塊之前的數據頭中，所以可以得到下面的函數：
==========================
void mfree(void *p)
{
size_t *sizePtr=((size_t *) p)-1;
G_inUse -= *sizePtr;
free(p);
}
==========================

    因為在釋放過程中或許不會使用這種轉換，或者需要在略微不同的偏移位置存儲表示釋放內存大小的量，因此這種方法是無法移植的。

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