（计算机应用技术专业论文）一种内存泄漏检测技术的研究和实现.pdf

中文摘要 摘要：c c + + 程序设计语言能够让程序员灵活而高效地进行动态堆内存的分配和释 放，这是c c + + 编程语言的重要优点之一；然而，由于程序的复杂性以及人类思 维的局限性等主客观原因，程序员在利用c c + + 编程语言这一特点管理动态内存 时，很容易造成程序内存泄漏。因为短时间内这个问题并不会暴露出来，所以内 存泄漏的错误往往会被忽视。如果不及时发现并解决程序中内存泄漏的问题，长 时间运行存在内存泄漏的程序，将浪费大量宝贵的系统内存资源，从而导致系统 运行速度减慢甚至系统崩溃等严重后果。为了提高软件的性能，保证软件的可靠 性，检测c c + + 程序的内存泄漏具有重要的意义。 为了获得较好的内存检测效果，本文在研究垃圾收集算法的基础上，提出了 基于三色标记技术的指针式内存检测算法，这种算法没有对象拷贝操作，同时也 就避免了拷贝算法造成的一些问题，譬如在活动对象较多时效率较差，会浪费一 半的内存总量等等。其执行效率要优于一些传统的垃圾收集算法。 v c + + 提供了内置的内存泄漏报告，但是其功能有限。本文在其基础上改进了 报告方式，包括：为每一个泄漏的内存块提供了完整堆栈跟踪，包括源代码文件 名以及行号；以十六进制和a s c i i 码两种形式提供了完整的泄漏内存内容报告。 关键词：内存泄漏；垃圾收集；三色标记 分类号：t p 3 9 j e 塞交通太堂亟堂僮i 佥塞垦墨! b 至 a b s t r a c t a b s t r a c t ：p r o g r a m m e r sm a yt a k ea d v a n t a g eo fc c + + p r o g r a m m i n gl a n g u a g et o a l l o c a t eo rf r e ed y n a m i cm e m o r yb u te a s i l yf a i l e dt or e l e a s ep r e v i o u s l ya l l o c a t e d m e m o r y b l o c k t h ee f f e c to fm e m o r yl e a ki sm i n o rf o rt h es h o r t - l i v e dp r o g r a m b u ti ti s v i t a lt od e t e c ta n dr e m o v et h em e m o r yl e a k m e m o r yl e a km a yc o n s u m eam a s so f m e m o r yr e s o u r c e ，e v e n t u a l l yc a u s et h ep r o g r a mt of a i ld u et ol a c ko fm e m o r y i no r d e r t oe n h a n c et h ep e r f o r m a n c eo fs o f t w a r ea n da s s u r et h er e l i a b i l i t yo fs o f t w a r e ，i ti sv e r y i m p o r t a n tt od e t e c tt h em e m o r yl e a ki nc c + + p r o g r a m s f o rb e t t e re f f e c tw h e n d e t e c t i n gm e m o r yl e a k , a na l g o r i t h m b a s e do n t r i c o l o r - m a r k i n gc o l l e c t i o na l g o r i t h mi sp r e s e n t e dw h i c hd o e sn o tc o p ym e m o r y e l e m e n t s ，t h e r e b ya v o i d i n gs o m eo ft h ep r o b l e m sc a u s e db yt h ea s y n c h r o n o u sm o t i o no f o b j e c t s ( f o re x a m p l e ，l o wp e r c e n t a g eo fm e m o r yu t i l i z a t i o n ) t h i si n p l a c ed e t e c t i o n s c h e m eh a sa p p r o x i m a t e l yt h es a m ec o m p l e x i t ya so t h e rn o n - m o v i n gg a r b a g e c o l l e c t o r s ， t h u sm a k i n gi tu s a b l ei nah i g h - l e v e ll a n g u a g ei m p l e m e n t a t i o nw h e r es o m ep o i n t e r s c a n n o tb et r a c e d v i s u a lc + + p r o v i d e sb u i l t - i nm e m o r yl e a kd e t e c t i o n b u ti t sc a p a b i l i t i e sa r em i n i m a l a tb e s t h e r ea r es o m ef e a t u r e sw ei n t r o d u c ei nt h i sa r t i c a l ，n o n eo fw h i c he x i s ti nt h e b u i l t i nd e t e c t o r ： i tp r o v i d e sac o m p l e t es t a c kt r a c ef o re a c hl e a k e db l o c k ，i n c l u d i n gs o u r c ef i l ea n d l i n en u m b e ri n f o r m a t i o nw h e na v a i l a b l e i tp r o v i d e sc o m p l e t ed a t ad u m p s ( i nh e xa n d a s c i i ) o fl e a k e db l o c k s i tp r o v i d e sc u s t o m i z a b l el e v e lo fd e t a i li nt h em e m o r yl e a k r e p o r t i tp r o v i d e sc u s t o m i z a b l el e v e lo fd e t a i li nt h em e m o r yl e a kr e p o r t k e y w o r d s ：m e m o r yl e a k ；g a r b a g ec o l l e c t i o n ；t r i c o l o r - m a r k i n g c l a s s n o ：t p 3 9 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索， 并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国 家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：三- 4 - 二迫吃 导师签名： 乏嫩灶 签字日期：四年石月6 日 签字同期：锄, 1 7 年月日 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研 究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或 撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位论文作者签名：互如 签字日期：劢荷年石月日 致谢 本论文的工作是在我的导师张骏温副教授的悉心指导下完成的，张骏温副教 授严谨的治学态度和科学的工作方法给了我极大的帮助和影响。在此衷心感谢两 年来张老师对我的关心和指导。 同时，我要深深感谢含辛茹苦养育我的父母，是你们的爱让我能克服种种困 难，不断进取! 感谢所有给我授课的教师，他们孜孜不倦的教导，拓展了我的知 识面，使我在计算机科学领域奠定了扎实的基础，为进一步的学习和工作增强了 信心。 在实验室工作及撰写论文期间，董毅、刘树为、胡范山、张洲舟等同学对我 研究工作给予了热情帮助，在此向他们表达我的感激之情。 最后，衷心感谢各位专家和学者的评议和指导! 1 引言 1 1课题背景 c 和c + + 语言使得用户能够直接控制程序的内存资源的使用，这对于实现运行 程序的高性能或提高计算机资源的利用率是至关重要的，同时它给编程人员带来 了更大的灵活性与自由度。然而，由此而引发的内存泄漏错误一直困扰着开发人 员。 内存泄漏是一种常见的内存管理错误【1 1 ，它是由于在程序中动态分配内存后没 有及时释放而造成的。内存泄漏对于短时间运行的程序而言，它的影响可忽略不 计，然而对于诸如服务器或守护进程这类长时间运行的应用程序，它所带来的影 响不可轻视。当应用程序在执行过程中需要越来越多的内存，系统就会按照定 的策略将一些内存块交换出去，这样频繁地页面交换势必使得系统的性能也会随 之下降，一旦系统耗尽所有可用的虚拟地址空间，应用程序就会因为缺页错误而 被系统终止。这在很多应用方面所造成的损失是不可估量的，因此，通过检测软 件的内存泄漏缺陷，揭示软件产品中隐藏的内存错误，能够提高软件的性能和可 靠性，保证软件产品的质量，让程序员对软件系统高效正确的运行充满信心。 1 2国内外研究现状 随着人们对软件质量的重视，检测并去除软件中的内存错误己经成为不可缺 少的软件测试过程之一。国内外软件专家研究出各类检测内存错误的技术，软件 市场中也涌现出许多内存错误测试工具。 早在1 9 8 8 年，b o c h m d e m e r s w e i s e r 保守垃圾收集库是由b o e h m 、d e m e r s 和 w e i s e r 在x e r o xp a r c 所开发的保守垃圾收集器1 2 j 。可以在c c + + 语言中使用该函 数库完成自动垃圾收集功能。必要时，甚至还可以让传统的c c + + 代码与使用自动 垃圾收集功能的c c + + 代码在一个程序里协同工作。该库支持u n i x ，l i n u x ，m a c o s ， w i n d o w s 等主流平台。这是一个非移动式的收集器，采用标记和延迟清扫算法。这 个收集器自从出现后经历了相当大的发展，现在已经能够支持增量式收集和分代 式收集。 在检查代码中内存错误的工具软件中：比较著名的有c e n t e r u n e l 4 j 和p i i d 母1 习。 从这些软件的产生可以看出，在编码过程中正确管理动态分配内存是一件很困难 的事情。这些工具只是在调试内存读写错误方面比较实用，检测内存泄漏的功能 并不好用，而且它们的运行效率很低，会严重拖慢被监测软件的速度( 在c e n t e r l i n e 的解释器上，程序运行的开销是正常运行的5 0 倍，p u r i f y 连接器则是2 至1 4 倍) 。当 发现内存泄漏或是悬空指针之后，必须花费很大精力来修正代码。 如今已经研究出许多新技术来应对此问题，l l 如s m a r tp o i n t e r 7 】，g a r b a g e c o l l e c t i o n ，新的开发语言等。s m a r tp o i n t e r 技术比较成熟，s t l 中已经包含支持 s m a r tp o i n t e r 的c l a s s ，但是它的使用似乎并不广泛，而且它也不能解决所有的问题； 以j 2 m e 为代表，j a v a 在嵌入式开发领域得到了大量的应用。然而就目前来说，j a v a 的代码性能、垃圾收集的巨大开销、以及j v m 本身的内存消耗都一定程度上限制 了它在嵌入式领域的应用范围。 1 3 本文研究重点 对于内存泄漏问题通常有两种解决方法：一种方法利用内存泄漏检测工具定 位造成内存泄漏的源程序代码，辅助程序员在适当的位置调用内存管理函数显示 释放不再使用的内存空间，彻底消除源代码中的内存泄漏错误。c c + + 程序通常采 用这类方法处理内存泄漏的错误。另外一种是由系统负责内存的释放，不再由程 序显式地释放分配的内存空间，这种方式通常被称为“垃圾回收”，垃圾收集虽然解 决了内存泄漏的错误，但它却消耗了系统相当的性能和内存来完成内存的回收工 作，j a v a 就是采用的垃圾回收机制。综合以上两种方法，c c + + 语言的垃圾收集技 术便成了本文感兴趣的目标。 本文的研究工作具体如下： ( 1 ) 研究内存泄漏检测技术的发展情况以及内存泄漏的特征和产生原因，广泛 收集和了解国内外在内存错误检测领域内的最新研究成果及其技术，并对此进行 总结。 ( 2 ) 介绍了现有的垃圾收集算法，比较了各种垃圾收集算法的优缺点。 ( 3 ) 分析了c c + + 语言中的垃圾收集技术需要关注的问题。 ( 4 ) 研究了垃圾收集算法中的c h e n e y 算法，并根据内存泄漏检测的需要，提出 了改进 拘c h e n e y 算法，即基于三色标记的指针式内存检测算法，从而在一定程度 上提高了检测效率。 ( 5 ) 在v i s u a lc + + d e b u g g e r 内存调试机制和c 运行时刻库的基础上，研究了如何 高效检索并输出内存分配操作对应的调用堆栈信息，为分析查找内存泄漏原因提 供详细信息。 2 1 4 本文的组织结构 本文的内容安排如下： 第一章阐述本课题的研究意义，简述目前国内外在该领域内的研究现状，指明 本文研究的工作重点。 第二章内存泄漏检测技术总论，介绍内存泄漏的相关概念，综合介绍内存泄漏 检测技术，分析并比较各种内存泄漏检测方法的实现原理，介绍了几种经典的垃 圾收集算法，并做了详细分析，明确了各种算法优缺点，以及c c + + 语言中的垃圾 收集技术需要关注的问题。 第三章介绍了经典的c h e n e y 算法，并在此基础上，提出改进i 拘c h e n e y 算法，即 基于三色标记的指针式内存检测算法，阐述了该算法基本思想和执行过程，并且与 其他的垃圾收集算法做了效率比较。 第四章分析了分配的内存节点单元的记录方式，以及相关的调用堆栈记录方 式，以及如何通过这些信息实现具有较高可读性的内存泄漏信息提示系统。 第五章对于目前的研究工作予以总结，并提出需要进一步完善和改进的部分， 分析今后的研究发展方向。 2 内存泄漏检测技术研究 2 1内存泄漏相关概念 内存泄漏( m e m o r yl e a k ) 是指程序中己动态分配的堆内存由于某种原因程序未 释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等 严重后果。 内存泄漏缺陷具有隐蔽性、积累性的特征，比其他内存非法访问错误更难检 测。因为内存泄漏的产生原因是内存块未被释放，属于遗漏型缺陷而不是过错型 缺陷。此外，内存泄漏通常不会直接产生可观察的错误症状，而是逐渐积累，降 低系统整体性能，极端的情况下可能使系统崩溃。 随着计算机应用需求的日益增加，应用程序的设计与开发也相应的日趋复杂， 开发人员在程序实现的过程中处理的变量也大量增加，如何有效进行内存分配和 释放，防止内存泄漏的问题变得越来越突出。例如服务器应用软件，需要长时间 的运行，不断的处理由客户端发来的请求，如果没有有效的内存管理，每处理一 次请求信息就有一定的内存泄漏。这样不仅影响到服务器的性能，还可能造成整 个系统的崩溃。因此，内存管理成为软件设计开发人员在设计中考虑的主要方面。 2 1 1内存泄漏的原因 在c 语言中，从变量存在的时间( 生命周期) 角度上，把变量分为静态存储变量 和动态存储变量两类。静态存储变量是指在程序运行期间分配了固定存储空间的 变量。而动态存储变量是指在程序运行期间根据实际需要进行动态地分配存储空 间的变量。在内存中供用户使用的内存空间分为三部分：( 1 ) 程序存储区；( 2 ) 静 态存储区；( 3 ) 动态存储区。程序中所用的数据分别存放在静态存储区和动态存储 区中。静态存储区数据在程序的开始就分配好内存区，在整个程序执行过程中它 们所占的存储单元是固定的，在程序结束时就释放，因此静态存储区数据一般为 全局变量。动态存储区数据则是在程序执行过程中根据需要动态分配和动态释放 的存储单元，动态存储区数据有三类：函数形参变量、局部变量和函数调用时的 现场保护与返回地址。由于动态存储变量可以根据函数调用的需要，动态地分配 和释放存储空间，大大提高了内存的使用效率，使得动态存储变量在程序中被广 泛使用。 开发人员进行程序开发的过程使用动态存储变量时，不可避免地面对内存管理 4 的问题。程序中动态分配的存储空间，在程序执行完毕后需要进行释放。没有释 放动态分配的存储空间而造成内存泄漏，是使用动态存储变量的主要问题。一般 情况下，开发人员使用系统提供的内存管理基本函数，如m a l l o e 、r e c a l l o e 、c a l l o e 、 f r e e 等，完成动态存储变量存储空间的分配和释放。但是，当开发程序中使用动态 存储变量较多和频繁使用函数调用时，就会经常发生内存管理错误，例如：( 1 ) 分 配个内存块并使用其中未经初始化的内容：( 2 ) 释放一个内存块，但继续引用其 中的内容；( 3 ) 子函数中分配的内存空间在主函数出现异常中断时、或主函数对子 函数返回的信息使用结束时，没有对分配的内存进行释放；( 4 ) 程序实现过程中分 配的临时内存在程序结束时，没有释放临时内存。内存错误一般是不可再现的， 开发人员不易在程序调试和测试阶段发现，既使花费了很多精力和时间，也无法 彻底消除。 2 1 2内存泄漏产生方式的分类 以产生的方式来分类，内存泄漏可以分为四类【9 】： 1 常发性内存泄漏 发生内存泄漏的代码会被多次执行到，每次被执行时都会导致一块内存泄漏。 2 偶发性内存泄漏 发生内存泄漏的代码只有在某些特定环境或操作过程下才会发生。常发性和 偶发性是相对的。对于特定的环境，偶发性的也许就变成了常发性的。所以测试 环境和测试方法对检测内存泄漏至关重要。 3 一次性内存泄漏 发生内存泄漏的代码只会被执行一次，或者由于算法上的缺陷，导致总会有 一块且仅有一块内存发生泄漏。 4 隐式内存泄漏 程序在运行过程中不停的分配内存，但是直到结束的时候才释放内存。严格 的说这里并没有发生内存泄漏，因为最终程序释放了所有申请的内存。但是对于 一个服务器程序，需要运行几天，几周甚至几个月，不及时释放内存也可能导致 最终耗尽系统的所有内存。所以，我们称这类内存泄漏为隐式内存泄漏。从用户 使用程序的角度来看，内存泄漏本身不会产生什么危害，作为一般的用户，根本 感觉不到内存泄漏的存在。真正有危害的是内存泄漏的堆积，这会最终消耗尽系 统所有的内存。从这个角度来说，一次性内存泄漏并没有什么危害，因为它不会 堆积，而隐式内存泄漏危害性则非常大，因为较之于常发性和偶发性内存泄漏它 更难被检测到。 5 2 1 3 内存泄漏检测方法 无论是c 还是c + + 程序，运行时候的变量主要有三种分配方式：堆分配、栈分 配、全局和静态内存分配。内存泄漏主要是发生在堆内存分配方式中，即“配置了 内存后，所有指向该内存的指针都遗失了”，若缺乏j a v a 语言这样的垃圾回收机制， 这样的内存片就无法归还系统。因为内存泄漏属于程序运行中的问题，无法通过 编译识别，所以只能在程序运行过程中来判别和诊断。下面将介绍几种常用的内存 检测方法，每种方法均以现有的内存检测工具为分析范例，并对各种方法进行比 较。 1 静态分析技术 静态分析技术就是直接分析程序的源代码或机器代码，获得一些有用的信息， 而并不运行程序本身。目前有许多静态分析的工具，编译器就属于这一类，它读 入源程序代码，对源程序进行词法和语法分析，进行数据类型的检查以及一些优 化的分析等，以此来提高程序的质量与运行效率。这类静态的分析工具仅仅是读 入程序代码进行相关的分析，而并不进行其它额外的操作，如修改源程序代码等。 l c l i n k 1 4 】是一种通过对源代码及添加到源代码中特定格式的注释说明进行静 态分析的程序理解和检错工具，l c l i n k 的检查对象是a n s ic 源程序，能检查出的内 存错误有：内存分配释放故障、空指针的错误使用、使用未定义或己被释放的内 存等程序错误。 l c l i n k 重点分析两类内存释放错误：( 1 ) 试图释放某内存块，该内存块有两个 或两个以上的有效指针指向它。( 2 ) 试图释放某内存块，该内存块没有任何有效指 针指向它。l c l i n k 解决此类内存错误的方法是规定分配某块内存时返回的指针必 须释放该内存。使用注释* o n l y * 表示某指针是唯一指向某内存块的指针，使 用注释* t e m p * 表示被调用函数可能释放函数参数指向的内存块或创建新的指 针指向该内存块。 示例如下： s l ：e x e r n 木 o n l y 宰c h a r 木g n a m e ； s 2 ：v o i ds e t n a m e ( 宰 t e m p 木c h a r + p n a m e ) s 3 ：g n a m e = p n a m e ， l c l i n t 将检查出上一段中存在一个内存泄漏错误，由于朗锄e 已被注释为 * o n l y 幸型的指针，l 天| f l ：g n a m e 需要负责释放该内存块。但s 3 语句中f l j g n a m e 指 向的内存块未被释放，g n a m e 却被赋予新值，因而产生内存泄漏错误。 6 2 源代码插装技术 为了获得被测程序的动态执行信息，需要对其进行跟踪，一般使用插装方法。 所谓插装就是在保持被测程序的逻辑完整性的基础上，在被测程序的特定部位插 入一段检测程序( 又称探针函数) ，通过探针的执行抛出程序的运行特征数据。基于 这些特征数据分析，可以获得程序的控制流及数据流信息，进而获得逻辑覆盖等 动态信息，这样就可以在被测程序执行的过程中动态地同步执行程序的检测工作。 插装方法又分为源代码级程序插装( s c l ) 和目标代码级程序插装( o c i ) 。 源代码插装测试必须在静态测试部分获得的被测程序的结构信息、静态数据 信息、控制流信息等基础上，应用插装技术向被测程序中的适当位置植入相应类 型的探针，通过运行带有探针的被测程序而获得程序运行的动态数据。 源代码插装要通过运行被测程序来测定程序的各种指标，如覆盖率、时间性 能、内存使用等等，实现源代码插装的关键技术是借助于插入到源程序中的监控 语句来收集执行信息，以达到揭示程序内部行为和特性的目的，如图2 1 所示。 广一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一一 i 插装阶段 l 图2 1 基于程序插装的动态测试实现原理图 基于源代码插装的动态测试框架分为4 个主要的阶段： ( 1 ) 插装交互与动态测试信息分析； ( 2 ) 插装阶段； ( 3 ) 插装库制作阶段； ( 4 ) 测试实施阶段。 插装交互与动态测试信息分析是软件测试工具与用户交互的界面。用户通过 7 该界面选择要进行动态测试的程序模块，拓扑产生相应的插装选择记录文件。用 户还可以通过该交互界而浏览动态测试结果信息，在软件测试工具的实现上。采 用可视化的方式显示这些动态信息。 插装阶段实现了在被测程序中植入探针，并生成带有插装信息的源文件。在 此过程中，首先将被测程序经过预处理展开为不包含宏、条件编译和头文件的文 件格式。然后，按照一定的插装策略，根据前面生成的插装选择记录文件，将探 针函数加载到该文件中，最后生成插装后的程序。插装库制作阶段的目的是生成 插装库中的探针函数，它含有插装语句调用的函数及其函数的定义。显然，插装 过程中生成的目标文件中含有探针函数的桩( s t u b ) ，而探针函数的实现恰恰在本过 程完成。需要指出的是，插装库的制作过程是独立于动态测试过程之外的，可以 与软件测试工具开发同步。测试实施阶段将插装过程生成的文件与插装库制作过 程生成的插装静态库连接生成带有插装信息的可执行文件，选取测试用例，运行 该程序，可以获得被测程序的动态跟踪信息。 在以上四个阶段中，其中的插装交互与动态测试信息分析与测试实施阶段是 测试人员的可视部分，通过这两部分，用户与系统交互，完成测试工作。而插装 阶段与插装库制作阶段对测试人员是不可见的，在后台完成，对于用户而言，这 两部分是完全透明的。 在性能方面，采用插装方法应尽量减少插装开销。为了达到不同的统计目的( 如 语句覆盖、分支覆盖等) ，应尽量减少插装次数。若能仅仅插装一次就能完成多种 类型的统计，则可使插装代码得到优化。此外，应尽量减少插装代码的数量，减 少插装代码的运行次数，从而达到减小插装代码运行开销的目的。特别是对于一 些实时系统的测试，在这方面的要求尤为苛刻。 i i l s l l 陀h 【1 0 】是一个运行时错误检测工具，能够自动检测c c + + 应用中大量的编 程和运行时错误。i n s u r 卅通过使用源码插装和运行时指针跟踪的专利技术，在编 译时，m s u 附+ 插入测试和分析代码，它建立一个有关程序中各种对象的数据库。 然后在运行时通过检查数据值和内存引用验证对象的一致性和正确性。使用这些 技术，包括变异测试技术等，i n s u r e + + f l 皂够检查和测试用户的代码，精确定位错误 的准确位置并给出详细的诊断信息。i n s u r e + + 能够可视化实时内存操作，优化内存 算法。m s u 附h 还能执行覆盖性分析，清楚地指示那些代码已经测试过。将i i l s u 盼h 集成到开发环境中，能够极大地减少调试时间并有效地防止错误。1 1 1 s u 附卜+ 检验每 一次内存操作的有效性，包括静态( 全局) 和堆栈以及动态分配内存的操作。 1 1 1 s u r 卅有两种运行模式。监护模式下用户可以快速检测代码中的错误，不需 要对代码作任何插装和处理；源码插装模式则进行彻底地代码检测。 3 目标代码插装技术 目标代码插装实现主要分为预处理、测试执行和结果汇总3 个阶段，工作流程 如图2 2 所示，系统主要工作是围绕断点而进行的。在预处理阶段，首先静态分析 被测程序的目标代码，查找待测程序中源代码各语句、函数入口点在目标代码中 的对应位置，然后在相应位置插入断点；在测试执行阶段，启动调试进程，当被 测程序执行到断点处时，响应断点信息，在相应的断点处完成相应的统计操作； 在结果汇总阶段，根据各断点处的统计结果，按不同的统计角度进行归并、综合 得到最终的统计数据。 图2 2 系统的丁作流程图 ( 1 ) 被测代码预处理 在测试预处理阶段。对被测程序的目标代码进行分析，可以获得目标代码与源 代码中语句、函数的对应关系。在目标代码中为相对应的源代码的每条语句及每 个函数的入口点插入断点。对于第三方代码，只要其目标代码格式与v c 6 0 下生成 的目标代码格式一致，我们就可以用与分析用户代码同样的方法获取信息。获取 断点的信息后，为所有的断点建立断点链表。同时建立语句及函数的信息链表， 供随后的测试执行阶段存储信息。预处理流程如图2 3 所示： 9 八 八 自 c 编 目断 插 动 入 被 + 译 标点 断 测 + 点 进 源 链 代插 后 程 程 的 和 序 接 码入 代 检 码 测 进 程 图2 3 预处理阶段的工作流程 ( 2 ) 测试执行阶段 利用o c i 技术，我们把测试执行看作是一个在被测进程和检测进程间不断切换 的过程。每当被测进程遇到断点，就会将自身挂起，同时发送消息唤醒检测进程， 检测进程根据当前断点的地址在断点链表中查找相应节点，并查找对应的语句或 函数信息，记录该语句或函数的执行次数、到达或离开的时刻，供以后统计之用。 然后，将插入的断点信息去除，恢复原来的指令，转入被测进程继续执行。在转 入被测进程之前，必须将上一个断点处的断点恢复( 上一个断点处的断点在指令运 行时被去除了) 。具体流程如图2 4 所示： 响应断点消息 根据当前地址，在 断点链表中盘找相 应节点，并杏找对 应的行和函数信息 记录行或甬数的执 行次数，时日j 恢复上一次断点 去除当前断点，恢 复原指令 是：一了天 遇断点 一一一一一一一一一一一 是嚣行 j完毕 h 执行 广： i 一二= = 二= j 一一一一一一至一一一一一一一一j 图2 4 测试执行阶段工作流程 1 0 厂。i。i一 ( 3 ) 数据统计与结果汇总 根据各断点处的统计结果，按不同的统计角度进行归并、综合，进行覆盖率 及各种时间的计算，得到最终的统计数据。 p 谢矽是i b mr a t i o n a ls o f t w a r e 公司出品的一种软件测试和质量保证工具，它能 检测程序内存泄漏和内存访问冲突等错误。 p u r i f y 使用目标码插装技术，在编译器生成的目标码中直接插入特殊的检查 指令实现对内存错误的检测。p 埘f y 在程序的所有代码中插入这些检查逻辑，包括 第三方目标码库，并且验证系统调用的接口。目标码插装技术分为链接前插装和 链接后插装两种插装方法。p 谢匆使用如图2 5 所示的链接前插装法。 编译插装链接 图2 5 链接前目标插装法示意图 p u r i f y 检查插装后程序的每个内存读写动作，跟踪内存使用情况，使用类似垃 圾收集器的技术来检查内存泄漏。垃圾收集机制分为两阶段：垃圾检测和垃圾回 收。为了不影响程序的执行速度，p u r i f y 提供了一个可调用的垃圾检测器，使用类 似于保守式垃圾收集算法，即标记清除算法。在标记阶段，p u r i f y 递归地从数据段、 堆栈段到数据堆跟踪分析指针，并使用标准保守式方法为所有被引用的内存块做 标记。在清除阶段，p u n f y 逐步访问数据堆，并报告已分配但程序不再引用的内存 块，即程序的内存泄漏。 4 各种检测方法的分析比较 ( 1 ) 动态分析和静态分析技术的比较 静态分析能够遍历程序中的每一个分支，它所提供的信息一般都比较全面而 正确，而动态分析一次只能监测分析程序运行的一个分支，有很大随机性。但是 由于动态分析是在实际运行过程中基于具体数据的基础上，因此具有较高的准确 性，而静态分析由于要遍历程序的每一个分支，因而随之而来的也是分析实现的 高代价。上述两种方法是互补的，在实际应用中，通常是将二者的结合使用。 ( 2 ) 源代码插装和目标代码插装技术的比较 利用o c i 技术插装后不用对被测代码进行重新编译，效率较高，而且可以分析 没有源程序的第三方代码。但o c i 技术本身也存在着以下几个缺陷： 实现起来难度较大，因为这涉及到厂家对语言的具体实现和操作系统的一 些底层机制，这些机制往往是保密的。 由于编译器对源代码的编译过程中进行了某种优化，对于分支结构生成与 之等价的非分支指令，所以利用o c i 技术无法获得源代码的结构信息，在覆盖率统 计时，只能达到函数覆盖和语句覆盖，无法对分支覆盖、条件覆盖等覆盖标准进 行计算。 相比较而言，s c i 技术简便易行，效率也比较高。对源代码进行词法、语法分 析后，可以按各种标准进行插装，分析计算出在各种标准下的测试数据。程序插 装在实践中应用广泛，可以用来捕获程序执行过程中变量值的变化情况，也可以 用来检测程序的语句覆盖和分支覆盖等逻辑覆盖情况。程序插装的关键技术包括 要探测哪些信息、在程序中什么部位设置探针、如何设计探针、以及探针函数捕 获数据的编码和解码。 ( 3 ) 内存垃圾收集技术与内存泄漏检测技术的比划1 3 】 垃圾收集技术基本解决程序中悬空指针和内存泄漏问题，提高可靠性、使内存 管理与用户程序设计分离，并使开发者减少了跟踪内存管理错误的时间。但垃圾 收集存在一些缺陷：垃圾收集暂停、因为垃圾收集而产生的c p u 时间损失、垃圾 收集器会与虚拟内存或者缓存有负面的互动，并且堆需要大于应用程序的驻留空 间( 即堆占用) 。因此，垃圾收集需要付出程序执行效率上代价，包括对性能的影响、 暂停、配置复杂性和不确定的结束。 内存泄漏检测技术的目的是检查出程序中存在的内存泄漏，并不是内存管理 方法，不会为程序员完成自动释放已分配内存的工作。检测内存泄漏的目的是帮 助开发人员排除程序中的内存泄漏缺陷，在不影响程序性能的前提下，提高软件 可靠性，保证软件的质量。 因此垃圾收集技术用于内存管理系统的开发，内存泄漏检测技术通常应用于软 件测试和软件调试领域。 2 2 内存泄漏检测与垃圾回收机制 为了检测到内存的物理泄漏，一种可行且有效的方法就是跟踪每一块动态 分配的内存及其所有指针引用，以此发现那些无法再被程序访i - j n 的内存空间。 1 2 这样，从这点看来，内存泄漏的检测在一定程度等同于垃圾回收机制。因此我们 可以采取垃圾收集机制的很多经典算法来实现我们的内存泄漏的检测。这里我们 先简单地介绍一下垃圾收集概念及其一些比较经典的算法。 2 2 1垃圾收集机制 垃圾收集机制是一种计算机存储单元的自动回收过程【l5 1 。“垃圾”这个概念可 以定义为系统应用中不再使用的内存对象。当系统的内存需求不能被满足时，内 存分配机制就会触发垃圾收集器来尽可能地回收内存空间。由于垃圾收集器的调 用方式内嵌于内存分配器的调用方式之中，因此垃圾收集器无法在外部进行调用。 内存分配器可以调用垃圾收集器来得到释放系统所需要的内存空间。 手动内存管理方式使用跟踪内存空间是否被占用的方法，可以有效地防止空 指针或者内存泄漏等编程错误。垃圾收集机制可以自动地防止以上所遇到的问题， 这样就可以大大地减轻程序员在内存管理方面的负担。在完全模块化的程序语言 中，垃圾收集机制对于避免不必要的模块问依赖关系和面向对象编程语言封装方 式来说非常重要。理想的垃圾收集器可以在“垃圾”对象不再被引用的时候完成收 集。但是，当这些对象在最后一次被引用的时候就可能难以确定它们是否下一次 会被继续引用。所以，垃圾收集器采用了一种对象“生存状态”( l i v e n e s s ) 标准来决 定对象是否被视为“垃圾”。垃圾收集的讨论中常常涉及下面一些术语： 对象( o b j e c t ) ：在堆上分配的所有数据均称为对象，在j a v a 虚拟机中，堆上的 对象还包括数组。 对象l 虱( o b j e c tg r a p h ) ：在进行垃圾收集时，内存中的对象间关系可以看做是一 个有向图( v ，a ) v 为有向图中顶点的集合，每个顶点可以代表根集合中节点或堆上 的对象，a 为有向图中弧( a r c ) 的集合，每个弧代表内存中的指针。如图为一个简单 的垃圾收集有向图模型，图中r o o t l 和r o o t 2 为根集合中的节点，其余的节点表示堆 上的对象。图中的弧代表堆上的对象间的指针以及根集合节点指向堆上对象的指 针。如图 图2 6 垃圾收集的有向图模型 根集合( r o o t s ) ：堆栈、寄存器等指向堆上活动对象的引用的集合。 可引用到的( r e a c h a b l e ) ：从对象图模型看，如果一个节点存在一条通过根集合 的某个节点达到该节点的路径，则该节点代表的对象是可引用到的，或称可达到 的。 活动对象( l i v eo b j e c t ) ：一个对象如果是可引用到的，该对象为活动对象。 垃圾对象( g a r b a g eo b j e c 0 ：一个对象如果是不可引用到的，该对象为垃圾对 象。 非移动的垃圾收集算法( n o n - m o v i n gg a r b a g ec o l l e c t o r ) ：在垃圾收集过中，不 需要移动活动对象的垃圾收集算法，如引用计数，标记清除算法等，称为非移动 的垃圾收集算法。 移动的垃圾收集( m o v i n gg a r b a g ec o l l e c t o r ) ：在垃圾收集过程中，需要移动活 动对象的垃圾收集算法，如拷贝算法和标记紧缩算法，称为移动的垃圾收集算法。 保守性( c o n s e r v a t i v e ) 和精确性( e x a c t ) ：保守的垃圾收集器不能确切地断定所有 对象的引用的分布位置，不能精确的判断内存中的一个字是否确切是一个对象的 引用，例如将一个整数误认为是一个对象指针。保守的垃圾收集器的一个优点是 易于增加到一个不支持垃圾回收的系统( 如将垃圾收集用于c 和c + + 语言) 中，其缺 点为效率较低。与之相对的则是精确性，精确的垃圾收集能确切地断定所有对象 的引用的分布位置。精确性具有以下几个优点：( 1 ) 所有不可访问的对象都可以被 可靠地回收。( 2 ) 所有的对象都可以被重新定位，因此能够采用移动式的垃圾收集 算法。 2 2 2垃圾收集的过程抽象 任何垃圾收集的算法都可以抽象的分为两个阶段：垃圾对象检测阶段和垃圾 对象回收阶段。 垃圾对象检测( g a r b a g ed e t e c t i o n ) 阶段：以某种方式判断垃圾对象，检测出堆 上所有的垃圾对象。判断一个对象是否为垃圾对象，主要有对象计数( c o u n t ) 和跟 踪( t r a c e ) 两种方法。对象计数的基本思想是对每个对象维护一个计数值，该计数 值记录了对象的被引用数目。当对象的计数值为0 时，该对象为垃圾对象。如上图 2 6 中，对象o b i 4 有两个指针指向它，则对象o b j 4 的计数值为2 。对象o b j 7 无指针指 向它，其计数值为0 ，因此，对象o b j 7 为垃圾对象。另一种方式为跟踪对象指针， 即从一个根集合( r o o ts e t ) 开始，根集合中所有可引用到的对象均为活动对象，这 些可引用到的活动对象中如果含有指向别的对象的指针，该指针指向的对象也为 活动对象。上图2 6 中，节点3 、节点4 为根集合( 节点r o o t l 和r o o t 2 ) 可弓l 用到的对象， 1 4 节点8 和节点5 为节点4 可引用到的对象，因此，节点3 、节点4 、节点5 、节点8 为上 图2 6 中的活动对象，节点6 、节点7 、节点9 、节点1 0 为垃圾对象。 - 垃圾对象回收阶段( g a r b a g er e c l a m a t i o n ) ：回收堆上垃圾对象占用的内存空间， 以便应用程序能够再次使用这部分空间。垃圾对象的回收可以采用显式的回收方 式，如将垃圾对象占用的内存空间插入一个f r e e 1 i s t 中，或者采用隐式的回收方式， 具体的回收方式取决于具体的垃圾收集算法。 在实际的垃圾收集算法中，运行时这两个阶段可能交织在一起执行或明确的 分成两个阶段单独执行。 2 2 3 垃圾收集算法介绍 1 引用计数( r e 矗。r e n c ec o u n t i n g ) 算法【1 9 】 引用计数法是在每个被动态分配的对象中使用额外的空间来存放引用计数值。 从而来表示对该对象的活跃引用的数量。当增加一个新的引用时，引用计数值加l ； 当一个原有的引用被丢弃时，引用计数值减l 。一旦引用计数值为0 ，该对象就满 足了垃圾收集的条件，这时立即触发垃圾收集器对该对象占用的内存进行回收。 算法的参考代码如下： a l g o r i t h mr e l e a s e ( o b j e c to b j ) o b j r e f c o u n t = o b j r e f c o u n t - 1 i fo b j r e f c o u n t = ot h e n f o r e a c hc h i l di no b j g e t c h i l d r e n od o i fc h i l d ! = n u l lt h e n r e l e a s e ( c h i l d ) e n di f e n dl o o p f r e e ( o b j ) e n di f e n d a l g o r i t h mw r i t e b a r r i e r ( o b j e c ti no u tl h s ，o b j e c tr h s ) i f r h s ! = n u l lt h e n r h s r e f c o u n t = r h s r e f c o u n t + l i f l h si - n u l lt h e n r e l e a s e ( 1 h s ) e n d i f l h s = r h s e n d 从上面的分析过程可以看到：引用计数法对内存管理的开销是分布在整个计 算过程之中。因为它对垃圾对象的检测、回收工作是与用户程序的执行交织在一 起进行的。这种渐进式的特点使得它运行较快。不会长时间中断程序的执行。比 较适宜于对响应时间要求较高的应用环境( 如高度交互性的系统或者是实时统) 。同 时它与那些非渐进式的、基于追踪的算法形成了鲜明的对比：后者通常在运行时 会挂起工作中的用户程序。因为它需要在回收垃圾对象之前遍历所有活动对象。 然而，引用计数算法在实际应用中使用很少的原因是它存在两个主要的缺陷： ( 1 ) 增加了程序执行的开销，效率较低。因为一方面增加或减少内存块时，与 之相关的一系列对象的引用计数值都必须进行调整。这类实现不得不支付高昂的 处理开销。另一方面，对于生命期很短的对象，例如过程调用中的参数传递，会 频繁地进行计数值的增加和减小的操作。此外，引用计数要占用相当数量的