下载掌阅APP，畅读海量书库
立即打开
市场上有许多商用的内存管理器，实践中也有很多广泛应用的自定义设计和实现的内存管理器。由于我们的目标不是编写一个新的内存管理器，因此读者无须理解内存管理器设计和实现的每一个细节，研究掌握每个内存管理器也没有必要且不切实际。但是，如果需要调试涉及堆内存的问题，那么了解程序中所使用的内存管理器是绝对重要且有帮助的。
为了调试的目的，我们第一个感兴趣的是任何一个被管理的内存块的状态。换句话说，我们应该了解足够多的堆数据结构来搞明白一个内存块。虽然内存管理器可能使用不同的数据结构，但它们仍然具有很多相似之处。如果我们熟悉一种或几种典型的实现，你会更快理解其他任何一种内存管理器。
下面，笔者将介绍两种受欢迎的内存管理器——ptmalloc和TCmalloc。ptmalloc是一个开源的项目，被Linux多个发行版和其他使用C运行库的应用程序使用；TCmalloc也是一个开源项目，由Google团队出品。这两种实现都支持各种平台，如Windows/Intel、Linux/Intel、AIX/PowerPC、Solaris/SPARC、HP-UX/IA等，包括32位和64位。为了专注于调试主题，笔者将跳过一些设计和实现细节的一般性讨论，而更多关注于数据结构部分。
ptmalloc在Doug Lee开发的内存分配器的基础上增加了一层并发分配的增强功能。它是Linux Red Hat发行版和许多其他发行版的系统默认内存管理器。在性能和空间节省的平衡方面，它被广泛认为是最好的内存管理器之一。下面的讨论适用于ptmalloc 2.7.0。
ptmalloc通过两个关键的数据结构来管理堆内存块：边界标签和盒子。它们被声明在文件malloc/malloc.c中，源代码可以在GNU C运行库glibc里面找到。
边界标签也称为块标签，是一个小巧的数据结构，在ptmalloc里叫作malloc_chunk，每个内存块里都有，用来记录当前内存块的大小和状态。因此，在ptmalloc术语里面，chunk是一个内存块的别名。
图2-1显示的是ptmalloc边界标签，灰色框的是边界标签。大小字段放在内存块的开始位置，它最低的两个比特分别表示当前块和前一个内存块是空闲的还是在使用中。需要注意的是，使用中的块和空闲块的边界标签的内容和大小是不一样的。正在使用中的块标签只使用了大小字段，但是空闲的内存块的标签使用了结构体malloc_chunk所有的4个字段。prev-size是放置在空闲内存块末尾的另一个大小字段，目的是让内存管理器可以由地址低端向上合并地址高端的空闲块。
当一个内存块被释放时，ptmalloc检查编码在大小字段的状态比特。如果前一个内存块是空闲的，那么它的开始地址会通过prev_size字段来计算，因此这两个内存块可以合并成一个空闲块。在size字段之后，是两个指向其他空闲块的指针fd和bk。ptmalloc会使用它们来构建空闲块的双链表。当应用程序请求一个新的内存块时，ptmalloc会搜索这个链表来寻找最合适的空闲块。因为标签数据结构的存在，一个ptmalloc管理的最小内存块不会小于结构体malloc_chunk的大小，对于64位应用程序来说，是32字节。
图2-1 ptmalloc边界标签
被分配出去的内存块的实际空间消耗仅仅只有8字节，也就是size字段使用的空间。不同于空闲块，使用中的内存块不需要双链表的下一个和前一个指针，同时它把末尾的紧邻块的prev-size字段给占用了，因为当它在使用的时候，我们不需要合并这个块。
所有的空闲块被收集到盒子bins里，这些盒子被实现为双向链表数组，并按块大小进行索引。这个数组被声明为ptmalloc管理堆的顶层元数据结构体malloc_state的数据成员：
盒子中空闲块的大小随着数组索引的增大而增大。盒子之间的间距是仔细选择过的。因为大部分用户请求都是小块的内存，从24字节到512字节的盒子都是精确的大小，以8字节隔开。这些盒子被叫作小盒子（Small Bin）。
剩下的盒子以大小的对数间隔。如果找不到确切的匹配，那么分配器可以提取大一点的盒子里的内存块。如图2-2所示的ptmalloc空闲块的盒子们，显示24字节大小的盒子有3个空闲块，40字节大小的盒子有1个空闲块，576字节大小的盒子有两个空闲块，大小在512字节和576字节之间。盒子的空闲块大小大于512字节的，按大小排好序并用最好匹配方法分配。
图2-2 ptmalloc空闲块的盒子
当接收到用户请求时，分配器首先检查并调整请求块的大小。如果有必要，取整到不小于最小块的大小（64位程序是32字节），另外为了满足对齐要求可能会增加一些填充。如果调整过的请求块大小落在精确大小的小盒子（24～512字节）上，那么计算得到对应的数组索引并检查其中的空闲链表。
如果链表具有空闲块，那么会移除链表头部空闲块并返回给用户。因为链表所有的空闲块都是同样大小，所以没有必要遍历链表。如果链表是空的，那么下一个比较大的缓存着的盒子就会被检查。如果有一个空闲块大于请求的大小，那么它会被分割成两部分：一部分满足请求并返回给用户；另外一部分叫作剩余块，会放到相应盒子中以备将来使用。
如果下一个盒子没有空闲块，分配器会继续搜索更大的盒子，直到合适的空闲块被找到。如果所有的盒子都被用光并且没有可以满足申请大小的候选内存块，ptmalloc会转向系统的VMM（虚拟机管理器）来获取一大块内存，并分割成两个内存块：一个返回给用户，一个被存入相应的盒子里。
当内存块被用户释放时，分配器从镶嵌的块标签中获取它的大小。如果当前内存块的前面和后面也是空闲的，ptmalloc会试图合并它们，此时前一个和后一个空闲块会从它们相应的双链表中移除。合并后的空闲块会被放到以下描述的未排序的链表列表中。除了上面描述的算法，ptmalloc还采用了其他一些有趣的技术来提高性能和减少内存消耗。如果感兴趣，读者可通过阅读源代码来获得更多的细节。下面简要介绍一下。
· 快速盒子（Fast Bin）与小盒子相似；保存在快速盒子中的最大空闲块更小，默认值是80字节。如果用户释放的内存块的大小小于快速盒子的最大内存块的大小，它会被直接放入对应的快速盒子里，且不更改它的块标签，这一点非常重要。即使可以合并，它也不会跟周围的空闲块合并。当新的请求到来时，在检查常规的盒子前，会先检查快速盒子。如果有合适的，这个缓存的内存块会立即返回。同样的它的标签不需要被调整。在这种情况下，请求可以尽可能快地被满足。这个算法在经常需要构建和析构小对象的C++程序中工作得很好。为了避免碎片化，快速盒子的空闲块在一些条件下会被合并。如果一个请求大于小盒子的最大块的大小或者没有空闲的块可以满足小的请求，在快速盒子中的内存块就会被处理，也就是先与邻近的空闲块合并然后放到对应的常规盒子里。
· 另外还有一种特殊的盒子叫未排序chunks，因为在这种盒子里的内存块是未排序的。这个盒子里包含了暂时的最近内存分割带来的剩余部分或者是用户刚刚释放的空闲块。如果快速盒子和小盒子都不能够满足一个请求，那么在未排序的chunks里的空闲块会一个接一个地被考虑。如果找到一个匹配的空闲块，那么这个块会被返回给用户；否则，它会被放入常规盒子里。当搜索遍历完所有空闲块后，它们会重新分配到合适的盒子里。这种对最近空闲块的处理是为了提高内存的局部性和性能，因为程序往往会申请一组相关的内存块，比如一个数组的所有单元结构体，分配器采用上述考虑提高了数组内存地址顺序排列的可能性。
· 如果用户请求的大小超出了一个可调整的阈值（默认是128KB），并且ptmalloc无法找到一个足够大的缓存内存块来满足该请求，那么它会从VMM分配一块匿名的mmaped内存并直接返回给用户。为了减少内存碎片和程序占用的系统内存，当这样的内存块被用户释放时，ptmalloc不会缓存它，而是直接返回给VMM。这在很大程度上保证了进程在运行了很长时间后，还可以保持低内存占用。
TCMalloc（Thread-Caching Malloc）是一种高性能的内存管理器，由Google开发。它是一个优化过的内存分配器，旨在为C和C++应用程序提供更快、更高效的内存分配和释放。TCMalloc具有以下特性：
· 高性能：TCMalloc在多线程环境中具有出色的性能，因为它为每个线程提供了本地缓存，从而减少了锁争用和全局内存管理器的争用。
· 高效的内存使用：TCMalloc通过细粒度的内存块划分和缓存策略来减少内存碎片，从而提高内存使用率。
· 快速的内存分配与释放：相较于其他内存分配器，TCMalloc在分配和释放内存时能达到更快的速度。
· 可扩展性：TCMalloc的设计使其能够在多处理器、多核心系统上提供良好的性能，从而支持大型、高负载应用程序。
· 跟踪与分析工具：TCMalloc提供了用于内存使用情况跟踪和分析的工具，有助于发现内存泄漏、内存碎片等问题。
· 易于集成：TCMalloc可以很容易地集成到现有的C或C++应用程序中，通常只需要链接到相应的库即可。
TCMalloc的以上特性特别适用于在多线程环境中运行的C和C++应用程序。它可以提高程序的性能，减少内存碎片，并帮助开发人员更好地诊断和解决内存问题。在实现方面，TCMalloc采用了以下策略：
· 线程缓存：为了减少线程之间的锁争用，TCMalloc为每个线程维护了一个本地缓存。这样，当一个线程请求内存分配时，它可以从自己的缓存中快速分配内存，而不需要与其他线程争用全局内存管理器。同样，当线程释放内存时，它会将内存归还给本地缓存，而不是全局内存管理器。这大大降低了锁的争用和全局内存管理器的压力。
· 大小类划分：TCMalloc将内存分成多个大小类，每个大小类分别管理一定范围的内存块大小。这样可以使内存分配更加精确，减少内存碎片的产生。
· 页面堆：TCMalloc使用了一种被称为页面堆（Page Heap）的结构来管理大块内存。页面堆负责分配和回收大于一定阈值（例如32KB）的内存。通过将大块内存的管理从线程缓存和大小类管理器中分离出来，TCMalloc可以更高效地管理大块内存，同时减少内存碎片的产生。
· 内存释放：为了进一步减少内存碎片，TCMalloc会定期地将线程本地缓存中的空闲内存归还给全局内存管理器。这使得全局内存管理器可以更好地合并相邻的空闲内存块，从而减少内存碎片。
· 跟踪和监控（Monitoring）：TCMalloc提供了一系列用于跟踪和监控内存使用情况的工具。这些工具可以帮助开发人员发现内存泄漏、内存碎片等问题，从而优化内存使用。
TCMalloc包括几个主要部分：
· 页面堆（Page Heap）负责与系统接口，管理大块的以系统页为单位的内存，它支持上游的内存块缓存器，同时也直接分配系统页给大内存申请。
· 中央自由链缓存（Central Freelist Cache）是一个全局的缓存管理器，负责批量提供内存块给所有线程。
· 线程缓存（Thread Cache）负责局部的自己线程私有的小内存块缓存，来自应用的最频繁的内存申请大都由它分配。这几个部件的关系如图2-3所示，从图中可以看出，TCMalloc采用了常见的由大到小、由底层向上的多梯次的结构。
下面我们再看看各个部件的主要数据结构。
图2-3 TCMalloc请求分配简图
TCMalloc的页面堆是一个用于管理大块内存的数据结构。页面堆负责分配和回收大于一定阈值（例如32KB）的内存申请。页面堆的设计旨在高效地管理这些大块内存，同时降低内存碎片的产生。页面堆的数据结构设计如下：
· 页面（Page）：页面堆将内存划分为固定大小（例如8KB）的页面。页面是页面堆中的基本单位。页面堆使用一个数组来存储所有页面的元数据信息，例如空闲状态、大小等。
· 跨度（Span）：跨度是一个或多个连续的页面。跨度是页面堆分配和管理内存的实际单位。每个跨度都有一个跨度描述符（Span Descriptor），其中包含有关该跨度的信息，例如起始地址、页面数、空闲状态等。
· 自由跨度列表（Free Span List）：页面堆维护了一个自由跨度列表，用于存储空闲跨度。自由跨度列表按照跨度大小进行组织，以便快速查找大小合适的空闲跨度。页面堆还可以合并相邻的空闲跨度，以减少内存碎片。
· 非空闲跨度列表（Non-idle Span List）：页面堆还维护了一个非空闲跨度列表，用于存储已分配的跨度。这可以帮助页面堆在释放内存时快速定位相关跨度。
页面堆使用一组简单的链表来管理可用的系统页，这些页可能是刚从内核分配出来或者由应用层释放返回给堆分配器的，每个链表上的节点指向地址连续且页数固定的1～255个系统页，最后的一个链表包含地址连续的256页以上的超大内存。这种结构便于迅速找到满足要求的连续地址页，如图2-4所示。
跨度是堆管理的主要数据结构，如图2-5所示。TCMalloc需要在很多上下文里找到它以便查询或更新堆数据，由此诞生了页表（Page Map），其目的是快速地从内存地址中找到对应的跨度。在图2-5中，整个页表由一个全局变量记录，并由三级阵列组成（早期版本中曾为二级），它们是由64位内存地址的一部分（36位至47位，24位至35位，13位至23位）组成的整数索引，最终指向地址对应的跨度结构体。当一个跨度管理多个页面时，最后一级阵列会有多个元素指向同一个跨度。页表是一个高效的插入和读取结构，其设计与内核的页表设计非常相似。
图2-4 页面堆
图2-5 页表与跨度关系
页面堆的主要操作包括：
· 分配内存：当请求大块内存时，页面堆会在自由跨度列表中查找大小合适的空闲跨度。如果找到合适的跨度，页面堆会将其从自由跨度列表中移除，并添加到非空闲跨度列表中。如果没有合适的空闲跨度，页面堆会从操作系统中分配新的内存。
· 释放内存：当释放大块内存时，页面堆会根据内存地址在非空闲跨度列表中查找相应的跨度。然后将其从非空闲跨度列表中移除，并添加到自由跨度列表中。页面堆还会尝试合并相邻的空闲跨度，以减少内存碎片。
总之，页面堆的数据结构设计旨在高效地管理大块内存。通过将内存划分为页面和跨度，以及维护自由跨度列表和非空闲跨度列表，页面堆可以实现快速的内存分配和释放，同时降低内存碎片的产生。
TCMalloc通过大小类划分来实现对内存的精细管理，以提高内存分配的效率并减少内存碎片。大小类划分的原理是将内存块按大小分组，每个组管理一定范围内的内存块。TCMalloc进行大小类划分的方法如下：
· 小对象（Small Object）：对于小对象（通常为几字节到几千字节），TCMalloc使用固定间隔的大小类。例如，第一个大小类管理8字节的内存块，第二个大小类管理16字节的内存块，以此类推。这些固定大小的内存块可以减少内存碎片，因为它们在分配和回收时不会产生不匹配的空间。
· 中等对象（Medium Object）：对于中等大小的对象，TCMalloc使用稍大的间隔进行大小类划分。例如，大小类可以按8字节的倍数增加（如64字节、72字节、80字节等）。这允许TCMalloc更高效地管理这些相对较大的内存块，同时仍然保持较低的内存碎片。
· 大对象（Large Object）：对于大对象（通常大于一个页面，例如32KB），TCMalloc不再使用大小类进行管理。大对象由Page Heap管理，如前面所述。
当应用程序请求内存分配时，TCMalloc根据请求的内存大小查找合适的大小类。然后，TCMalloc从该大小类中分配一个内存块。如果大小类中没有可用的内存块，TCMalloc会从更大的大小类或Page Heap中获取内存并将其划分。
当应用程序释放内存时，TCMalloc将内存块归还给相应的大小类。这样，当相同大小的内存再次被请求时，它可以快速地重新分配。
通过这种大小类划分策略，TCMalloc能够实现对内存的精细管理，并降低内存碎片。这也使得TCMalloc在分配和释放内存时具有更高的性能和效率。
相对于ptmalloc的边界标签的位置，TCMalloc的跨度与应用内存块在地址上并不毗邻，所以应用程序的越界读写不会直接造成跨度结构的毁坏。这就导致两种内存分配器在由非法读写造成崩溃的时候会呈现完全不同的现象：ptmalloc常常在malloc与free函数中崩溃，这是因为程序的越界读写常常会在无意中改写边界标签，比如所属内存块的大小或者下一个自由内存块的地址，改写的过程并不会导致立即崩溃，只有当ptmalloc的malloc与free函数读取被篡改的边界标签，然后由此计算出别的内存地址并试图读写这个地址时，程序才会因为错误地址而崩溃；TCMalloc的跨度结构在同样情况下不会损坏，因而TCMalloc的malloc与free函数不受影响，但是问题依然存在，因为毗邻的内存物体会被意外改动，其后果取决于该物体的使用环境，有可能没有任何影响，有可能改变程序的某个功能，也有可能导致程序崩溃，结果更具随机性。
现代内存管理器（如ptmalloc和TCMalloc等）能够创建和管理多个堆。一个堆可以包含一个或多个段。这些段在地址上不一定是连续的。它们在逻辑上组织在一起以服务一组线程、特定的功能或者程序特定的模块。多个堆显著地提高了在多处理器上运行的多线程程序的性能，这也是当今应用程序的标准。使用多个堆还有如下优点：
· 将拥有特定堆的特定模块的内存问题隔离起来。
· 可以通过将函数的多个内存请求放到同一个堆来提高性能。同个堆的内存块倾向于具有更好的缓存局部性。
· 由于同一个堆的内存块大概率是为同一个任务创建的，因此它们倾向于有相同的生命周期，从而减少了内存的碎片。
例如，Windows上的C运行时自己的DLL单独使用一个堆。这就是为什么即使对于像下面这样简单的程序，我们也会看到好几个堆。在程序退出之前，使用Windbg的拓展命令“!heap”来列出所有的堆。这个例子有3个堆，变量p指向一个从开始地址为0x00330000的默认堆里分配的内存块。
在ptmalloc中，我们称堆为“arena”，所有的arena都位于一个循环链表之中。为了确保堆的元数据不受损害，当线程执行操作（如内存分配或释放）时，会对arena进行独占锁定。如果此时有其他线程请求内存，其请求可能被拒绝。不过，ptmalloc不会简单地等待当前线程解锁arena，它会尝试寻找链表中的下一个可用arena。如果找到了，该请求就由此arena来处理。如果连续的arena都被其他线程占用，ptmalloc会继续在链表中搜索，直至找到可用的arena。如果整个链表都被搜索完毕而没有找到空闲的arena，系统会新建一个arena并与已存在的arenas连接起来。新建的arena用于处理所请求的内存分配。
为了优化性能，每个线程都有一个线程本地变量，用于记忆最后一次成功分配内存的arena。在新的请求中，线程会优先考虑使用这个arena，因为这样做更容易获得锁定，并且能提高内存的缓存效率。