嵌入式系统设计中消除内存丢失的策略
在嵌入式系统设计过程中，许多软件工程师受困于动态内存管理。本文介绍一种将堆栈中的内存碎片降至最少的解决方案，其中讲到了内存碎片和内存丢失的区别，以及一种在编程中有利于检测并消除内存丢失的策略。
标准C库函数malloc()和free()可在任意的时间段中，为应用分配任意大小的内存块。随着内存块的使用和释放，在整个内存区域中，分配给堆栈的存储区将混杂着许多正在使用或已经释放的存储块，而未被使用的任何小块内存区将变得无法使用。例如，某个应用要求堆栈分配30字节，如果堆栈中只有20个长度为3字节的小存储块(总共为60字节)，那么堆栈仍然无法为该应用分配内存，因为所需的30字节必须是连续的。
在执行时间较长的程序中，内存碎片可能导致系统的内存枯竭，尽管分配的内存总量并未超出总的可用内存总数。内存碎片的数量取决于堆栈的实现策略。大多数程序员均采用由编译器提供的malloc()和free()函数创建的堆栈，因此内存碎片就不受程序员的控制。
内存丢失是应用程序的缺陷，更具体地，内存丢失是一块已经分配但永远不会被释放的内存区。如果所有指向内存块的指针超出界限或者指向其他的区域，那么应用程序将永远不能释放那块内存区。对于将会在某时刻退出的桌面应用程序，较小的内存丢失还可以承受，因为退出进程将把占用的所有内存返还给操作系统。但对于长时间运行的嵌入式系统，则通常需要确保绝对没有内存丢失。
避免内存丢失不是轻而易举的，为了确保所有分配的内存都在随后释放，必须建立一套明确的规则，以确定哪个应用占用了内存。为跟踪内存，可采用类、指针数组或链表。由于在动态内存分配中，程序员无法预先知道在给定时间内需要分配多少数据块，因此通常需要采用链表结构。
例如，假定一个任务正在接收来自通信信道的消息，任务将为消息分配空间，而该空间在消息得到完整的处理之前不会被释放。因为消息有可能不会按照接收的顺序进行处理，因此一些消息存在的时间将比其他消息更长。所有挂起的消息存在于一个列表中，列表的长度取决于任意给定时间内进行处理的消息数目。嵌入式系统必须将消息转发至另外的设备，而且消息在收到传送确认之前不能被删除。由于消息将传送至许多不同的目的地，而且某些目的地可能存在一些导致重传的故障，因此不能以先入先出方式处理这些消息。
在上述问题中，动态内存管理对RAM的利用效率高于预定义缓存管理。当内存不再被消息队列使用时，就能被其他队列或完全不同的程序部分使用。
当多个指针同时指向某个特定的内存块时，通常还会产生另一个特殊问题。如果第一个实体(entity)占有内存并希望释放该内存，那么必须考虑是否还有其他指针指向该区域。如果存在，那么随着第一个实体释放内存，其他的指针将成为悬挂指针(dangling pointer)，即该指针指向的空间不再有效。当使用悬挂指针时，或许仍然可以得到正确的数据，但这些内存终将被重新使用(通过另一个malloc()调用)，从而导致在悬挂指针和该内存的新使用者之间出现不期望的相互影响。
悬挂指针与内存丢失刚好相反。如果没有释放内存，就可能导致内存丢失；而如果释放了那些并不准备释放的内存则将产生悬挂指针。
内存丢失在许多方面与竞争条件非常相似。内存丢失引发的性能失常完全不同于程序错误，因此，这些问题很难通过调试器对代码进行单步调试加以解决。对于内存丢失和竞争条件，代码检查有时能比采用任何技术解决方案更快地找到问题所在。
添加调试代码并生成输出通常比源代码调试器更为有效，但在某些竞争条件下，则有可能改变代码的执行特性，从而掩盖了问题。在内存丢失中，添加调试代码可改变内存配置，这意味着悬挂指针故障可能具有不同的执行特性。另一缺陷在于，如果调试代码消耗了内存，那么调试版将比产品版更快地耗尽RAM，内存丢失就是内存丢失，而不管这些调试代码的副作用如何，都应当可被检测。
驱动自动碎片收集
Java具有对无用存储单元进行碎片收集(garbage collection)的自动内存管理机制，因此Java程序员无须担心内存分配的释放。如果以前曾用过Java进行编程，那么与其他编程语言相比，无疑会对Java跟踪内存所需的时间留下深刻的印象。
在Java中，只需牺牲运行时间即可换来编程的简化，因为手工管理内存可以得到更为有效的实现方法。但当程序变得越来越大，手工管理就变得无能为力了。虽然好的手工管理通常能使堆栈的总长度降至最小，但这并不总是轻而易举的。在那些通常由数十名程序员完成的大型程序中，人为错误将引入足以降低性能等级的大量内存丢失，这时就需要自动碎片收集解决方案。
[page]
在对无用存储单元进行自动碎片收集过程中，一个优秀的程序员或许做得远比自动碎片收集器出色，但在需要众多程序员参与的大型项目中，则几乎不可能找到并修正所有的内存丢失。选择自动系统或许要求对性能进行折衷，而且自动碎片收集器有时也会出现混乱。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);
}
=================
标准C库函数malloc()和free()可在任意的时间段中，为应用分配任意大小的内存块。随着内存块的使用和释放，在整个内存区域中，分配给堆栈的存储区将混杂着许多正在使用或已经释放的存储块，而未被使用的任何小块内存区将变得无法使用。例如，某个应用要求堆栈分配30字节，如果堆栈中只有20个长度为3字节的小存储块(总共为60字节)，那么堆栈仍然无法为该应用分配内存，因为所需的30字节必须是连续的。
在执行时间较长的程序中，内存碎片可能导致系统的内存枯竭，尽管分配的内存总量并未超出总的可用内存总数。内存碎片的数量取决于堆栈的实现策略。大多数程序员均采用由编译器提供的malloc()和free()函数创建的堆栈，因此内存碎片就不受程序员的控制。
内存丢失是应用程序的缺陷，更具体地，内存丢失是一块已经分配但永远不会被释放的内存区。如果所有指向内存块的指针超出界限或者指向其他的区域，那么应用程序将永远不能释放那块内存区。对于将会在某时刻退出的桌面应用程序，较小的内存丢失还可以承受，因为退出进程将把占用的所有内存返还给操作系统。但对于长时间运行的嵌入式系统，则通常需要确保绝对没有内存丢失。
避免内存丢失不是轻而易举的，为了确保所有分配的内存都在随后释放，必须建立一套明确的规则，以确定哪个应用占用了内存。为跟踪内存，可采用类、指针数组或链表。由于在动态内存分配中，程序员无法预先知道在给定时间内需要分配多少数据块，因此通常需要采用链表结构。
例如，假定一个任务正在接收来自通信信道的消息，任务将为消息分配空间，而该空间在消息得到完整的处理之前不会被释放。因为消息有可能不会按照接收的顺序进行处理，因此一些消息存在的时间将比其他消息更长。所有挂起的消息存在于一个列表中，列表的长度取决于任意给定时间内进行处理的消息数目。嵌入式系统必须将消息转发至另外的设备，而且消息在收到传送确认之前不能被删除。由于消息将传送至许多不同的目的地，而且某些目的地可能存在一些导致重传的故障，因此不能以先入先出方式处理这些消息。
在上述问题中，动态内存管理对RAM的利用效率高于预定义缓存管理。当内存不再被消息队列使用时，就能被其他队列或完全不同的程序部分使用。
当多个指针同时指向某个特定的内存块时，通常还会产生另一个特殊问题。如果第一个实体(entity)占有内存并希望释放该内存，那么必须考虑是否还有其他指针指向该区域。如果存在，那么随着第一个实体释放内存，其他的指针将成为悬挂指针(dangling pointer)，即该指针指向的空间不再有效。当使用悬挂指针时，或许仍然可以得到正确的数据，但这些内存终将被重新使用(通过另一个malloc()调用)，从而导致在悬挂指针和该内存的新使用者之间出现不期望的相互影响。
悬挂指针与内存丢失刚好相反。如果没有释放内存，就可能导致内存丢失；而如果释放了那些并不准备释放的内存则将产生悬挂指针。
内存丢失在许多方面与竞争条件非常相似。内存丢失引发的性能失常完全不同于程序错误，因此，这些问题很难通过调试器对代码进行单步调试加以解决。对于内存丢失和竞争条件，代码检查有时能比采用任何技术解决方案更快地找到问题所在。
添加调试代码并生成输出通常比源代码调试器更为有效，但在某些竞争条件下，则有可能改变代码的执行特性，从而掩盖了问题。在内存丢失中，添加调试代码可改变内存配置，这意味着悬挂指针故障可能具有不同的执行特性。另一缺陷在于，如果调试代码消耗了内存，那么调试版将比产品版更快地耗尽RAM，内存丢失就是内存丢失，而不管这些调试代码的副作用如何，都应当可被检测。
驱动自动碎片收集
Java具有对无用存储单元进行碎片收集(garbage collection)的自动内存管理机制，因此Java程序员无须担心内存分配的释放。如果以前曾用过Java进行编程，那么与其他编程语言相比，无疑会对Java跟踪内存所需的时间留下深刻的印象。
在Java中，只需牺牲运行时间即可换来编程的简化，因为手工管理内存可以得到更为有效的实现方法。但当程序变得越来越大，手工管理就变得无能为力了。虽然好的手工管理通常能使堆栈的总长度降至最小，但这并不总是轻而易举的。在那些通常由数十名程序员完成的大型程序中，人为错误将引入足以降低性能等级的大量内存丢失，这时就需要自动碎片收集解决方案。
[page]
在对无用存储单元进行自动碎片收集过程中，一个优秀的程序员或许做得远比自动碎片收集器出色，但在需要众多程序员参与的大型项目中，则几乎不可能找到并修正所有的内存丢失。选择自动系统或许要求对性能进行折衷，而且自动碎片收集器有时也会出现混乱。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);
}
=================