Malloc内存泄露和内存越界问题的研究

------内存跟踪与检测篇

1.      引言

熟悉c语言的人都知道，内存泄露，特别是内存越界是软件界非常棘手，甚至防不胜防的问题。由于这种问题一般为概率问题，时而出现时而不出现，这样给问题的定位分析带来很大的困难，后期排查的代价也比较大，因此，这个问题一直困扰着软件开发人员和软件界。不管多牛的技术高手，甚至技术专家都不敢拍着胸脯说，他负责的项目没有内存泄露和内存越界问题。

那如何解决这种问题呢？

解决这种问题无非有两种方案，一：进行后期内存跟踪，即对分配的内存进行跟踪，检查它们有没有内存泄露和内存越界问题，如有修改之；二：进行前期内存检测，即在分配和使用内存前，先检测其合法性。第一个方案的优点就是逻辑相对简单，容易实现些，且基本能够发现90%以上的内存问题；缺点就是需要额外的内存开销，同时问题的发现依赖于问题的复现。第二种方案其实就是完整的内存管理，由于其实现难道比较大，要求运行效率比较高，同时需要解决内存碎片和编码习惯等问题。因此，这里只研究通过后期内存跟踪与检查来发现malloc内存是否泄漏和越界问题。至于第二种方案和栈内存，静态内存，全局内存等越界问题，以后有时间再慢慢研究。

2.      Malloc内存泄露与内存越界问题的跟踪

2.1 堆内存泄露问题描述

    内存泄露的原因很多，有malloc了内存没free的，有open了文件没close的，有创建了socket和sem没释放的等待。相对于堆内存泄露，open, fopen, opendir，socket, sem等系统调用导致的内存泄露可能更容易被忽视些。这里只讨论malloc内存的泄露问题。

对于malloc内存泄露，只要遵循：”谁申请谁释放，在同一函数中申请在同一函数中释放”原则基本上可以杜绝内存泄露问题。当然，在很多情况下，不可避免地需要在不同的函数中申请和释放，甚至需要在不同的任务中申请和释放。这，才是造成堆内存泄露的主要原因。

相对于堆内存越界问题，堆内存泄露问题的排查相对简单的多。但谁要是敢拍胸脯说他做的系统绝对不会有内存泄露问题，要么就是他参与的项目很少涉及在不同任务中分配和释放等复杂情况，要么就是他太过轻率。

2.2 堆内存越界问题描述(还有野指针的访问会造成内存越界问题)

http://blog.chinaunix.net/attachment/201208/14/27629626_13449172296hjg.jpg

内存越界问题一直以来是开发人员，甚至软件界非常棘手的问题，但仔细分析起来无非三种情况：踩了别人，被人踩了，既踩了别人同时也被人踩了，如上图1，图2，图3所示。

下面我们将针对内存越界的三种情况采取对应的解决方案。

2.3 堆内存跟踪与检测

2.3.1 在堆内存块中插入头尾法来跟踪内存越界问题

http://blog.chinaunix.net/attachment/201208/14/27629626_1344917317ZB5i.jpg

<1>. 堆内存块中插入头尾法描述：

在用户分配的内存中插入头尾信息，一般来说，当一个内存对象需要踩掉别人时，必须先踩掉自己的尾部，它就是凶手，如图4；当一个内存块的头部被踩时，它肯定是受害者，如图5；当一个内存对象的头尾都被踩时，它有可能是受害者(头尾被踩穿)，也有可能它既是凶手也是受害者(被人踩的同时也踩了别人)。至于自己踩自己的头部，那属于我们所谓的自杀行为，它本身既是凶手也是是受害者。

需要说明的是，我们将这里的内存块看着对象，即内存块对象。它包含了内存块(数据)和内存块访问行为(操作)。因为内存块本身是不会被踩的，它只是块数据而已，只有行为才构成威胁。而如果仅仅只研究内存块访问行为，那么我们将很难根据内存跟踪的方法查找谁踩了谁？甚至连嫌疑对象都很难查找。否则就变成了另一个研究课题”分配和使用内存前，必须先检测其合法性”。这，不是我们本次研究的对象。

    这三种情况衍生的更复杂的情况，下面我们将慢慢叙述。

<2>. 踩了别人(主动行为)

http://blog.chinaunix.net/attachment/201208/14/27629626_1344917362cCKM.jpg

如果一个内存对象踩了别人，如果在内存块中插入头尾信息，那么它必须先踩自己的尾部，然后才可能踩到别人；因此，只要它的尾部被踩，不管它有没有踩到别人，说明它肯定内存越界啦，如图4所示。至于被别人击穿而导致的尾部被踩的情况，我们将在后面讨论。

踩了别人又分为三种情况：第一种是只踩了自己的尾部；第二种是既踩了自己的尾部还踩了别人的头部；第三种就是踩到别的地方去了，当然也踩了自己的尾部。不管怎么样，它都是凶手，至少是嫌疑犯。

2  如果只踩了自己的尾部而没有踩穿的话，如图4.1所示。说明由于我们穿了马甲而没有伤着别人，否则不知道谁又会遭殃啦。

2  如果踩穿了自己的尾部，同时也踩掉了别人的头部的话，如图4.2所示。那么我们就既可以知道谁是受害者，也可以知道谁是凶手。

2  如果踩到别的地方去了，如图4.3所示。那么我们一下子很难查到受害者，但我们至少查到了凶手。我们的目的不就是为了查凶手吗？至于受害者嘛，由民政部去处理好啦，咱也管不了那么多。

<3>. 被人踩了(被动行为)：

如果一个内存块被踩了，如果在内存块中插入头尾信息，那么它的头部信息肯定被踩掉了；因此，不管怎么样，它都是受害者，如图5所示。

被人踩了大致可以分为三种情况：第一种是头部被踩了，但尾部没有被踩；第二种是头尾都被踩了。第三种是自杀行为。

2  头部被踩，但尾部没有被踩，如图5.1所示。这种情况，我们一般可以通过<2>. 踩了别人来检查到谁的尾部被踩了谁可能就是凶手。非堆内存导致的这种问题这里不作研究，后续有相关问题答疑。

2  头尾都被踩了，如图5.2所示。这种情况，我们一般可以通过<2>. 踩了别人来检查到谁的尾部被踩了谁可能就是凶手。至于有没有可能踩穿尾部导致第三者被踩，这，取决于越界的长度和被踩的内存块长度。至于有没有可能是既被人踩了，同时也踩了别人所致？这种情况在<4> 既踩了别人，也被人踩了中描述。

2  自杀行为，如图5.3所示。从内存访问的角度来看，自己的头部信息也可能被自己踩啦，比如指针减减，数组下标减减等操作，这样的话，就是属于自杀行为。同时还可能导致别的内存块尾部被踩。因此在跟踪内存被踩时，不可忽略这种可能性，虽然这种情况很少。需要注意的是，仅仅只是自杀行为的话，是不可能自己踩着自己的尾部的。除非该内存对象踩了别人后，畏罪自杀啦。呵呵~~ 感觉像查案啊！！

 请注意：当我们顺序跟踪内存，无法查找凶手时，请考虑自杀行为。

<4>. 既踩了别人，也别人踩了(自动和被动同时存在)：

http://blog.chinaunix.net/attachment/201208/14/27629626_1344917440p7aD.jpg

既踩了别人，也被人踩了，有点像它既是凶手，也是受害者。这种情况比较复杂，涉及到多种不同的组合；。我们大致分为三类：第一情况是头部被踩了，但尾部没被踩，同时还踩了别人，如图6.1所示；第二种情况是头尾被踩，同时也踩了别人，如图6.2所示；第三种情况是头尾被踩，还有自杀行为，如图6.3所示。至于它踩了别人后自杀了，已在<3>. 被人踩了(被动行为)中描述；从内存块对象被踩的现象来看，这块内存头尾都被踩啦。

<5>. 内存被踩问题总结

    查内存越界有点像查案，纷繁复杂，不知道你们有没有头晕，反正我是晕啦！！呵呵~~ 现在我们小结一下，理清一下思路。

从内存块对象的数据角度来看，分为三种情况：头被踩，尾被踩，头尾都被踩；从内存对象的行为来看，也分为三种情况：踩了别人，被人踩了，既踩了别人，也被人踩啦。

从查案的线索来看，这个最复杂。复杂？不复杂找你干嘛，不直接找个清洁工来查呀，你看人家不但任劳任怨，还不讨价还价。嘿嘿~~放松一下！言归正传，从查案的线索来看，分为：（头晕啦，先放着吧）

这里说到用插入头尾法标识内存块有没有被踩来判断谁踩了踩，然而我们怎么跟踪和查看这些内存信息呢？

2.3.2 用链表记录内存块的信息

http://blog.chinaunix.net/attachment/201208/14/27629626_1344917478ZNk8.jpg

    如果仅仅只在malloc的内存中插入头尾信息，那么我们就无法跟踪这些内存，他们是否存在内存泄露和内存越界问题，因此，需要对这些内存块进行记录。我们将创建一个链表来记录每块堆内存的信息，当我们需要查看内存是否泄漏和越界时，我们通过遍历这个链表来查看每个节点对应的内存块的头尾信息是否被踩掉来实现。

图7表示增加了头尾信息的内存块，图8表示用于记录内存块信息的链表，图9表示链表节点信息。其链表节点由blkId, blkAddr, blklength组成； blkID是ULONG类型，其中第一个8位可以存放模块ID，第二个8位可以存放任务ID或者文件ID，第三个8位用于存放申请内存代码所在的行号和申请的次数编号，因为同一个包含申请内存块的接口有可能被多次访问；blkAddr表示内存的首地址；blklength表示内存块的总长度。当我们查出是由于某个模块的某个文件的第几行申请的内存访问踩了别人，那么我们就可以查找该内存块所有使用者，从而找到真正的凶手。

需要注意的是，实现这个功能时，我们需要对malloc和free进行封装，当用户调用封装的malloc接口时，我们需要分配的实际内存大小为头长度+用户内存长度+尾长度；因此我们记录的blkLength为内存块总长度,blkAddr为实际内存块的首地址。头尾长度为多少？头尾信息是什么呢？为了节省内存开销，建议采用约定的方式实现。当然也可以包含在链表头节点中。

同样，对于堆内存泄露问题，当我们发现某个模块的内存块不停地被申请而没有被释放的话，就需要相关人员来确认是否有内存泄露的嫌疑。注意：这只是嫌疑而已，因为到底是否为内存泄露有时很难确定。对于像分配一块单板就分配一块内存，删除一块单板就释放一块内存来说，就比较容易判断。如果我分配了10次，删除了5次，如果内存块较长时间多于5个的话，肯定就有内存泄露，如果少于5个的话，说明由于哪个状态标志问题多释放了内存块。

3.      如何解决记录内存块的链表被踩的问题

既然malloc的内存块可能被踩，当然记录内存块的链表也可能被踩掉，如果链表的头结点被踩掉的话，我们将无法通过链表信息来跟踪和检测它。如果我们再用别的内存来记录这个链表的话，谁能保证记录链表的这个内存不被踩掉？这不就陷入到死循环中了？ 如果用全局变量记录头结点的话，如果链表中的某个结点被踩，后面的结点将无法访问。

怎么办呢？

通过和bsp组交流后发现，他们在bootload中可以为我们划分一块保留内存，然后封装一套接口供我们使用。用户态无法直接访问这块内存，必须通过他们封装的接口才能访问，这样就可以解决链表被踩的问题。

4.      如何解决额外的内存开销问题

       由于分配内存时需要额外增加头尾信息，同时需要创建对应的链表节点来记录这块内存信息，这在整个系统中的内存开销是巨大的。如何解决这个问题呢？

n  我们可以在分布版本时分为release版本和debug版本，release版本关闭内存跟踪功能，debug版本则开启内存跟踪功能。测试部可以尽量用debug版本进行测试，以便发现问题；产业化和鉴定测试中心可以用release版本进行测试，如release版本发现问题，可以用debug版本进行复现。

n  我们也可以在release版本中增加动态开关，一开始运行时关闭这个开关，如需要时，可以随时打开和关闭这个开关。

5.      Malloc内存(堆内存)是否会被其它非堆内存踩掉

http://blog.chinaunix.net/attachment/201208/14/27629626_1344917512hC6n.jpg

图1:  典型的内存空间布局

一个典型的Linux C程序内存空间由如下几部分组成：

• 代码段（.text）。这里存放的是CPU要执行的指令。代码段是可共享的，相同的代码在内存中只会有一个拷贝，同时这个段是只读的，防止程序由于错误而修改自身的指令。
• 初始化数据段（.data）。这里存放的是程序中需要明确赋初始值的变量，例如位于所有函数之外的全局变量：int val=100。需要强调的是，以上两段都是位于程序的可执行文件中，内核在调用exec函数启动该程序时从源程序文件中读入。
• 未初始化数据段（.bss）。位于这一段中的数据，内核在执行该程序前，将其初始化为0或者null。例如出现在任何函数之外的全局变量：int sum;
• 堆（Heap）。这个段用于在程序中进行动态内存申请，例如经常用到的malloc，new系列函数就是从这个段中申请内存。
• 栈（Stack）。函数中的局部变量以及在函数调用过程中产生的临时变量都保存在此段中

根据以上内存布局可以知道，除非是堆边界内存可能被初始化或非初始化或栈内存踩掉，一般情况下不用担心这种问题。因此这种特殊情况，基本上不用太多的担心。