Glibc内存管理--ptmalloc2源代码分析（三）

3. 概述

3.1 内存管理一般性描述

当不知道程序的每个部分将需要多少内存时，系统内存空间有限，而内存需求又是变化的，这时就需要内存管理程序来负责分配和回收内存。程序的动态性越强，内存管理就越重要，内存分配程序的选择也就更重要。

3.1.1内存管理的方法

可用于内存管理的方法有许多种，它们各有好处与不足，不同的内存管理方法有最适用的情形。

1．  C风格的内存管理程序

C风格的内存管理程序主要实现malloc()和free()函数。内存管理程序主要通过调用brk()或者mmap()进程添加额外的虚拟内存。Doug Lea Malloc，ptmalloc，BSD malloc，Hoard，TCMalloc都属于这一类内存管理程序。

基于malloc()的内存管理器仍然有很多缺点，不管使用的是哪个分配程序。对于那些需要保持长期存储的程序使用malloc()来管理内存可能会非常令人失望。如果有大量的不固定的内存引用，经常难以知道它们何时被释放。生存期局限于当前函数的内存非常容易管理，但是对于生存期超出该范围的内存来说，管理内存则困难得多。因为管理内存的问题，很多程序倾向于使用它们自己的内存管理规则。

 

2．    池式内存管理

内存池是一种半内存管理方法。内存池帮助某些程序进行自动内存管理，这些程序会经历一些特定的阶段，而且每个阶段中都有分配给进程的特定阶段的内存。例如，很多网络服务器进程都会分配很多针对每个连接的内存——内存的最大生存期限为当前连接的存在期。Apache 使用了池式内存（pooled memory），将其连接拆分为各个阶段，每个阶段都有自己的内存池。在结束每个阶段时，会一次释放所有内存。

在池式内存管理中，每次内存分配都会指定内存池，从中分配内存。每个内存池都有不同的生存期限。在Apache中，有一个持续时间为服务器存在期的内存池，还有一个持续时间为连接的存在期的内存池，以及一个持续时间为请求的存在期的池，另外还有其他一些内存池。因此，如果我的一系列函数不会生成比连接持续时间更长的数据，那么我就可以完全从连接池中分配内存，并知道在连接结束时，这些内存会被自动释放。另外，有一些实现允许注册清除函数（cleanup functions），在清除内存池之前，恰好可以调用它，来完成在内存被清理前需要完成的其他所有任务（类似于面向对象中的析构函数）。

使用池式内存分配的优点如下所示：

l   应用程序可以简单地管理内存。

l   内存分配和回收更快，因为每次都是在一个池中完成的。分配可以在O(1)时间内完成，释放内存池所需时间也差不多（实际上是O(n)时间，不过在大部分情况下会除以一个大的因数，使其变成O(1)）。

l   可以预先分配错误处理池（Error-handling pools），以便程序在常规内存被耗尽时仍可以恢复。

l   有非常易于使用的标准实现。

池式内存的缺点是：

l   内存池只适用于操作可以分阶段的程序。

l   内存池通常不能与第三方库很好地合作。

l   如果程序的结构发生变化，则不得不修改内存池，这可能会导致内存管理系统的重新设计。

l   您必须记住需要从哪个池进行分配。另外，如果在这里出错，就很难捕获该内存池。

 

3．    引用计数

在引用计数中，所有共享的数据结构都有一个域来包含当前活动“引用”结构的次数。当向一个程序传递一个指向某个数据结构指针时，该程序会将引用计数增加 1。实质上，是在告诉数据结构，它正在被存储在多少个位置上。然后，当进程完成对它的使用后，该程序就会将引用计数减少 1。结束这个动作之后，它还会检查计数是否已经减到零。如果是，那么它将释放内存。

在 Java，Perl 等高级语言中，进行内存管理时使用引用计数非常广泛。在这些语言中，引用计数由语言自动地处理，所以您根本不必担心它，除非要编写扩展模块。由于所有内容都必须进行引用计数，所以这会对速度产生一些影响，但它极大地提高了编程的安全性和方便性。

以下是引用计数的好处：

l   实现简单。

l   易于使用。

l   由于引用是数据结构的一部分，所以它有一个好的缓存位置。

不过，它也有其不足之处：

l   要求您永远不要忘记调用引用计数函数。

l   无法释放作为循环数据结构的一部分的结构。

l   减缓几乎每一个指针的分配。

l   尽管所使用的对象采用了引用计数，但是当使用异常处理（比如try或setjmp()/ longjmp()）时，您必须采取其他方法。

l   需要额外的内存来处理引用。

l   引用计数占用了结构中的第一个位置，在大部分机器中最快可以访问到的就是这个位置。

l   在多线程环境中更慢也更难以使用。

 

4．    垃圾收集

垃圾收集（Garbage collection）是全自动地检测并移除不再使用的数据对象。垃圾收集器通常会在当可用内存减少到少于一个具体的阈值时运行。通常，它们以程序所知的可用的一组“基本”数据——栈数据、全局变量、寄存器——作为出发点。然后它们尝试去追踪通过这些数据连接到每一块数据。收集器找到的都是有用的数据；它没有找到的就是垃圾，可以被销毁并重新使用这些无用的数据。为了有效地管理内存，很多类型的垃圾收集器都需要知道数据结构内部指针的规划，所以，为了正确运行垃圾收集器，它们必须是语言本身的一部分。

垃圾收集的一些优点：

l   永远不必担心内存的双重释放或者对象的生命周期。

l   使用某些收集器，您可以使用与常规分配相同的API。

其缺点包括：

l   使用大部分收集器时，您都无法干涉何时释放内存。

l   在多数情况下，垃圾收集比其他形式的内存管理更慢。

l   垃圾收集错误引发的缺陷难于调试。

l   如果您忘记将不再使用的指针设置为null，那么仍然会有内存泄漏。

3.1.2内存管理器的设计目标

内存管理器为什么难写？在设计内存管理算法时，要考虑什么因素？管理内存这是内存管理器的功能需求。正如设计其它软件一样，质量需求一样占有重要的地位。分析内存管理算法之前，我们先看看对内存管理算法的质量需求有哪些：

1． 最大化兼容性

要实现内存管理器时，先要定义出分配器的接口函数。接口函数没有必要标新立异，而是要遵循现有标准（如POSIX或者Win32），让使用者可以平滑的过度到新的内存管理器上。

 

2． 最大化可移植性

通常情况下，内存管理器要向OS申请内存，然后进行二次分配。所以，在适当的时候要扩展内存或释放多余的内存，这要调用OS提供的函数才行。OS提供的函数则是因平台而异，尽量抽象出平台相关的代码，保证内存管理器的可移植性。

 

3． 浪费最小的空间

内存管理器要管理内存，必然要使用自己一些数据结构，这些数据结构本身也要占内存空间。在用户眼中，这些内存空间毫无疑问是浪费掉了，如果浪费在内存管理器身的内存太多，显然是不可以接受的。

内存碎片也是浪费空间的罪魁祸首，若内存管理器中有大量的内存碎片，它们是一些不连续的小块内存，它们总量可能很大，但无法使用，这也是不可以接受的。

 

4． 最快的速度

内存分配/释放是常用的操作。按着2/8原则，常用的操作就是性能热点，热点函数的性能对系统的整体性能尤为重要。

 

5． 最大化可调性（以适应于不同的情况）

内存管理算法设计的难点就在于要适应用不同的情况。事实上，如果缺乏应用的上下文，是无法评估内存管理算法的好坏的。可以说在任何情况下，专用算法都比通用算法在时/空性能上的表现更优。

为每种情况都写一套内存管理算法，显然是不太合适的。我们不需要追求最优算法，那样代价太高，能达到次优就行了。设计一套通用内存管理算法，通过一些参数对它进行配置，可以让它在特定情况也有相当出色的表现，这就是可调性。

 

6．  最大化局部性（Locality）

大家都知道，使用cache可以提高程度的速度，但很多人未必知道cache使程序速度提高的真正原因。拿CPU内部的cache和RAM的访问速度相比，速度可能相差一个数量级。两者的速度上的差异固然重要，但这并不是提高速度的充分条件，只是必要条件。

另外一个条件是程序访问内存的局部性（Locality）。大多数情况下，程序总访问一块内存附近的内存，把附近的内存先加入到cache中，下次访问cache中的数据，速度就会提高。否则，如果程序一会儿访问这里，一会儿访问另外一块相隔十万八千里的内存，这只会使数据在内存与cache之间来回搬运，不但于提高速度无益，反而会大大降低程序的速度。

因此，内存管理算法要考虑这一因素，减少cache miss和page fault。

 

7． 最大化调试功能

作为一个C/C++程序员，内存错误可以说是我们的噩梦，上一次的内存错误一定还让你记忆犹新。内存管理器提供的调试功能，强大易用，特别对于嵌入式环境来说，内存错误检测工具缺乏，内存管理器提供的调试功能就更是不可或缺了。

 

8． 最大化适应性

前面说了最大化可调性，以便让内存管理器适用于不同的情况。但是，对于不同情况都要去调设置，无疑太麻烦，是非用户友好的。要尽量让内存管理器适用于很广的情况，只有极少情况下才去调设置。

设计是一个多目标优化的过程，有些目标之间存在着竞争。如何平衡这些竞争力是设计的难点之一。在不同的情况下，这些目标的重要性又不一样，所以根本不存在一个最好的内存分配算法。

 

一切都需要折衷：性能、易用、易于实现、支持线程的能力等，为了满足项目的要求，有很多内存管理模式可供使用。每种模式都有大量的实现，各有其优缺点。内存管理的设计目标中，有些目标是相互冲突的，比如最快的分配、释放速度与内存的利用率，也就是内存碎片问题。不同的内存管理算法在两者之间取不同的平衡点。

         为了提高分配、释放的速度，多核计算机上，主要做的工作是避免所有核同时在竞争内存，常用的做法是内存池，简单来说就是批量申请内存，然后切割成各种长度，各种长度都有一个链表，申请、释放都只要在链表上操作，可以认为是O(1)的。不可能所有的长度都对应一个链表。很多内存池是假设，A释放掉一块内存后，B会申请类似大小的内存，但是A释放的内存跟B需要的内存不一定完全相等，可能有一个小的误差，如果严格按大小分配，会导致复用率很低，这样各个链表上都会有很多释放了，但是没有复用的内存，导致利用率很低。这个问题也是可以解决的，可以回收这些空闲的内存，这就是传统的内存管理，不停地对内存块作切割和合并，会导致效率低下。所以通常的做法是只分配有限种类的长度。一般的内存池只提供几十种选择。

3.1.3常见C内存管理程序

本文主要关注的是C内存管理程序，比较著名的几个C内存管理程序，其中包括：

l   Doug Lea Malloc：Doug Lea Malloc实际上是完整的一组分配程序，其中包括Doug Lea的原始分配程序，GNU libc分配程序和ptmalloc。Doug Lea的分配程序加入了索引，这使得搜索速度更快，并且可以将多个没有被使用的块组合为一个大的块。它还支持缓存，以便更快地再次使用最近释放的内存。ptmalloc是Doug Lea Malloc 的一个扩展版本，支持多线程。在本文后面的部分详细分析ptamlloc2的源代码实现。

l   BSD Malloc：BSD Malloc是随4.2 BSD发行的实现，包含在FreeBSD之中，这个分配程序可以从预先确实大小的对象构成的池中分配对象。它有一些用于对象大小的 size类，这些对象的大小为2的若干次幂减去某一常数。所以，如果您请求给定大小的一个对象，它就简单地分配一个与之匹配的size类。这样就提供了一个快速的实现，但是可能会浪费内存。

l   Hoard：编写Hoard的目标是使内存分配在多线程环境中进行得非常快。因此，它的构造以锁的使用为中心，从而使所有进程不必等待分配内存。它可以显著地加快那些进行很多分配和回收的多线程进程的速度。

l   TCMalloc：（Thread-Caching Malloc）是google开发的开源工具──“google-perftools”中的成员。与标准的Glibc库的malloc相比，TCMalloc在内存的分配上效率和速度要高得多。TCMalloc是一种通用内存管理程序，集成了内存池和垃圾回收的优点，对于小内存，按8的整数次倍分配，对于大内存，按4K的整数次倍分配。这样做有两个好处，一是分配的时候比较快，那种提供几十种选择的内存池，往往要遍历一遍各种长度，才能选出合适的种类，而TCMalloc则可以简单地做几个运算就行了。二是短期的收益比较大，分配的小内存至多浪费7个字节，大内存则4K。但是长远来说，TCMalloc分配的种类还是比别的内存池要多很多的，可能会导致复用率很低。 TCMalloc还有一套高效的机制回收这些空闲的内存。当一个线程的空闲内存比较多的时候，会交还给进程，进程可以把它调配给其他线程使用；如果某种长度交还给进程后，其他线程并没有需求，进程则把这些长度合并成内存页，然后切割成其他长度。如果进程占据的资源比较多呢，据说不会交回给操作系统。周期性的内存回收，避免可能出现的内存爆炸式增长的问题。TCMalloc有比较高的空间利用率，只额外花费1%的空间。尽量避免加锁（一次加锁解锁约浪费100ns），使用更高效的spinlock，采用更合理的粒度。小块内存和打开内存分配采取不同的策略：小于32K的被定义为小块内存，小块内存按大小被分为8Bytes，16Bytes，。。。，236Bytes进行分级。不是某个级别整数倍的大小都会被分配向上取整。如13Bytes的会按16Bytes分配，分配时，首先在本线程相应大小级别的空闲链表里面找，如果找到的话可以避免加锁操作（本线程的cache只有本线程自己使用）。如果找不到的话，则尝试从中心内存区的相应级别的空闲链表里搬一些对象到本线程的链表。如果中心内存区相应链表也为空的话，则向中心页分配器请求内存页面，然后分割成该级别的对象存储。大块内存处理方式：按页分配，每页大小是4K，然后内存按1页，2页，……，255页的大小分类，相同大小的内存块也用链表连接。

 

各种C内存管理程序实现的对比

策略	分配速度	回收速度	局部缓存	易用性	通用性	SMP线程友好度
GNU Malloc	中	快	中	容易	高	中
Hoard	中	中	中	容易	高	高
TCMalloc	快	快	中	容易	高	高

从上表可以看出，TCMalloc的优势还是比较大的，TCMalloc的优势体现在：

l   分配内存页的时候，直接跟OS打交道，而常用的内存池一般是基于别的内存管理器上分配，如果完全一样的内存管理策略，明显TCMalloc在性能及内存利用率上要省掉第三方内存管理的开销。之所以会出现这种情况，是因为大部分写内存池的coder都不太了解OS

l   大部分的内存池只负责分配，不管回收。当然了，没有回收策略，也有别的方法解决问题。比如线程之间协调资源，模索模块一般是一写多读，也就是只有一个线程申请、释放内存，就不存在线程之间协调资源；为了避免某些块大量空闲，常用的做法是减少内存块的种类，提高复用率，这可能会造成内部碎片比较多，如果空闲的内存实在太多了，还可以直接重启。

         作为一个通用的内存管理库，TCMalloc也未必能超过专用的比较粗糙的内存池。比如应用中主要用到7种长度的块，专用的内存池，可以只分配这7种长度，使得没有内部碎片。或者利用统计信息设置内存池的长度，也可以使得内部碎片比较少。

所以TCMalloc的意义在于，不需要增加任何开发代价，就能使得内存的开销比较少，而且可以从理论上证明，最优的分配不会比TCMalloc的分配好很多。

对比Glibc可以发现，两者的思想其实是差不多的，差别只是在细节上，细节上的差别，对工程项目来说也是很重要的，至少在性能与内存使用率上TCMalloc是领先很多的。Glibc在内存回收方面做得不太好，常见的一个问题，申请很多内存，然后又释放，只是有一小块没释放，这时候Glibc就必须要等待这一小块也释放了，也把整个大块释放，极端情况下，可能会造成几个G的浪费。