作者 | daydreamer
前篇《探秘 C ++ 内存治理（实践篇）》次要介绍了 Linux C++ 程序内存治理的实践根底，本文作为系列文章《探秘 C ++ 内存治理》的第二篇，将会探讨经典内存管理器 ptmalloc 如何治理 C ++ 程序的内存。借助分析 ptmalloc 解决问题的着重点和设计实现老本的衡量，更具体的出现 c ++ 内存治理面临的问题和工程落地中的巧思。
一、概述
ptmalloc 是开源 GNU C Library(glibc)默认的内存管理器，以后大部分 Linux 服务端程序应用的是 ptmalloc 提供的 malloc/free 系列函数，而它在性能上远差于 Meta 的 jemalloc 和 Google 的 tcmalloc。服务端程序调用 ptmalloc 提供的 malloc/free 函数申请和开释内存，ptmalloc 提供对内存的集中管理，以尽可能达到：
- 用户申请和开释内存更加高效，防止多线程申请内存并发和加锁
- 寻求与操作系统交互过程中内存占用和 malloc/free 性能耗费的平衡点，升高内存碎片化，不频繁调用零碎调用函数
简略概括 ptmalloc 的内存管理策略：
- 事后向操作系统申请并持有一块内存供用户 malloc，同时治理已应用和闲暇的内存
- 用户执行 free，会将回收的内存治理起来，并执行管理策略决定是否交还给操作系统
接下来，将从 ptmalloc 数据结构、内存调配及优缺点介绍最经典的 c ++ 内存管理器的实现和应用（以 32 位机为例）。
二、内存治理
2.1 数据结构
为了解决多线程锁抢夺问题，将内存调配辨别为主调配区 (main\_area) 和非主调配区(no\_main\_area)。同时，为了便于管理内存，对预申请的内存采纳边界标记法划分成很多块(chunk)；ptmalloc 内存分配器中，malloc\_chunk 是根本组织单元，用于治理不同类型的 chunk，性能和大小相近的 chunk 串联成链表，被称为一个 bin。
main\_arena 与 non\_main\_arena
主调配区和非主调配区造成一个环形链表进行治理，每一个调配区利用互斥锁实现线程对该调配区的拜访互斥。每个过程只有一个主调配区，但容许有多个非主调配区，且非主调配区的数量只减少不缩小。主调配区能够拜访过程的 heap 区域和 mmap 映射区域，即主调配区能够应用 sbrk()和 mmap()分配内存；非主调配区只能应用 mmap()分配内存。
对于不同 arena 的管理策略大抵如下：
- 分配内存
- 查看该线程的公有变量中是否曾经存在一个调配区并对其进行加锁操作，如果加锁胜利，则应用该调配区分配内存；如果未找到该分区或加锁失败，遍历环形链表中获取一个未加锁的调配区
- 如果整个环形链表中没有未加锁的调配区，开拓一个新的调配区，将其退出循环链表并加锁，应用该调配区满足以后线程的内存调配
- 开释内存
- 先获取待开释内存块所在的调配区的锁，如果有其余线程正在应用该调配区，期待其余线程开释该调配区互斥锁后，再开释内存
主调配区和非主调配区的构造如下：
其中 fastbinsY 和 bins 是对理论内存块的治理和操作构造：
- fastbinsY: 用以保留 fast bins
- bins[NBINS * 2 – 2]: unsorted bin（1 个，bin[1]）、small bins（62 个，bin[2]~bin[63]）、large bins（63 个，bin[64]~bin[126]）的汇合，一共有 126 个表项(NBINS = 128)，bin[0] 和 bin[127] 没有被应用
malloc\_chunk 与 bins
ptmalloc 对立治理 heap 和 mmap 映射区域中闲暇的 chunk，当用户进行调配申请时，会先试图在闲暇的 chunk 中查找和宰割，从而防止频繁的零碎调用，升高内存调配的开销。为了更好的治理和查找闲暇 chunk，在预调配的空间的前后增加了必要的管制信息，内存治理构造 malloc\_chunk 的成员及作用如下：
- mchunk_prev_size: 前一个闲暇 chunk 的大小
- mchunk_size: 以后 chunk 的大小
- 必要的属性标记位：
- 前一个 chunk 在应用中(P = 1)
- 以后 chunk 是 mmap 映射区域调配 (M = 1) 或是 heap 区域调配(M = 0)
- 以后 chunk 属于非主调配区 (A = 0) 或非主调配区(A = 1)
- fd 和 bk: chunk 块闲暇时存在，用于将闲暇 chunk 块退出到闲暇 chunk 块链表中对立治理
基于 chunk 的大小和应用办法，划分出以下几种 bins：
-
fast bins
fast bins 仅保留很小的堆，采纳单链表串联，增删 chunk 都产生在链表的头部，进一步提高小内存的调配效率。fast bins 记录着大小以 8 字节递增的 bin 链表，个别不会和其余堆块合并。
-
unsorted bin
small bins 和 large bins 的缓冲区，用于放慢调配的速度，chunk 大小无尺寸限度，用户开释的堆块，会先进入 unsorted bin。调配堆块时，会优先查看 unsorted bin 链表中是否存在适合的堆块，并进行切割并返回。
-
small bins
保留大小 < 512B 的 chunk 的 bin 被称为 small bins。small bins 每个 bin 之间相差 8 个字节，同一个 small bin 中的 chunk 具备雷同大小，采纳双向循环链表串联。
-
large bins
保留大小 >= 512B 的 chunk 的 bin 被称为 large bins。large bins 中的每一个 bin 别离蕴含了一个给定范畴内的 chunk，其中的 chunk 按大小降序，雷同大小按工夫降序。
当然，并不是所有 chunk 都按上述的形式来组织，其余罕用的 chunk，如：
- top chunk: 调配区的顶部闲暇内存，当 bins 不能满足内存调配要求的时候，会尝试在 top chunk 调配。
- 当 top chunk > 用户申请大小，top chunk 会分为两个局部：用户申请大小 (user chunk) 和残余 top chunk 大小(remainder chunk)
- 当 top chunk < 用户所申请大小，top chunk 就通过 sbrk（main_arena）或 mmap（non_main_arena）零碎调用来扩容
2.2 内存调配与开释
概括内存 malloc 和 free 的流程大抵如下：
内存调配 malloc 流程
1、获取调配区的锁
2、计算出须要调配的内存的 chunk 理论大小
3、如果 chunk 的大小 < max\_fast，在 fast bins 上查找适宜的 chunk；如果不存在，转到 5
4、如果 chunk 大小 < 512B，从 small bins 下来查找 chunk，如果存在，调配完结
5、须要调配的是一块大的内存，或者 small bins 中找不到 chunk：
- a. 遍历 fast bins，合并相邻的 chunk，并链接到 unsorted bin 中
- b. 遍历 unsorted bin 中的 chunk：
- ①可能切割 chunk 间接调配，调配完结
- ②依据 chunk 的空间大小将其放入 small bins 或是 large bins 中，遍历实现后，转到 6
6、须要调配的是一块大的内存，或者 small bins 和 unsorted bin 中都找不到适合的 chunk，且 fast bins 和 unsorted bin 中所有的 chunk 已革除：
- 从 large bins 中查找，反向遍历链表，直到找到第一个大小大于待调配的 chunk 进行切割，余下放入 unsorted bin，调配完结
7、检索 fast bins 和 bins 没有找到适合的 chunk，判断 top chunk 大小是否满足所需 chunk 的大小，从 top chunk 中调配
8、top chunk 不能满足需要，须要扩充 top chunk：
- a. 主分区上，如果调配的内存 < 调配阈值（默认 128KB），应用 brk()调配；如果调配的内存 > 调配阈值，应用 mmap 调配
- b. 非主分区上，应用 mmap 来调配一块内存
内存开释 free 流程
1、获取调配区的锁
2、如果 free 的是空指针，返回
3、如果以后 chunk 是 mmap 映射区域映射的内存，调用 munmap()开释内存
4、如果 chunk 与 top chunk 相邻，间接与 top chunk 合并，转到 8
5、如果 chunk 的大小 > max\_fast，放入 unsorted bin，并且查看是否有合并：
- a. 没有合并状况则 free
- b. 有合并状况并且和 top chunk 相邻，转到 8
6、如果 chunk 的大小 < max\_fast，放入 fast bin，并且查看是否有合并：
- a.fast bin 并没有扭转 chunk 的状态，没有合并状况则 free
- b. 有合并状况，转到 7
7、在 fast bin，如果相邻 chunk 闲暇，则将这两个 chunk 合并，放入 unsorted bin。如果合并后的大小 > 64KB，会触发进行 fast bins 的合并操作，fast bins 中的 chunk 将被遍历合并，合并后的 chunk 会被放到 unsorted bin 中。合并后的 chunk 和 top chunk 相邻，则会合并到 top chunk 中，转到 8
8、如果 top chunk 的大小 > mmap 膨胀阈值（默认为 128KB），对于主调配区，会试图偿还 top chunk 中的一部分给操作系统
三、优缺点
ptmalloc 作为 glibc 默认的内存管理器，曾经宽泛的满足大多数大型项目的内存治理，同时它的实现思路也对起初的内存管理器提供了借鉴。
ptmalloc 的介绍暂告一段落，接下来的几篇文章将持续探讨高性能内存治理库的集大成者——jemalloc、tcmalloc 内存治理库。
———- END ———-
参考资料：
[1] https://sourceware.org/glibc/…
[2] https://sploitfun.wordpress.c…
[3] https://www.cnblogs.com/biter…
举荐浏览【技术加油站】系列：
百度工程师教你玩转设计模式（适配器模式）
揭秘百度智能测试在测试评估畛域实际
百度工程师带你探秘 C ++ 内存治理（实践篇）
从零到一理解 APP 速度测评
百度工程师教你玩转设计模式（工厂模式）