最近看了 glibc 的 ptmaoolc，Goolge 的 tcmalloc 和 jemalloc，顺便做了一点记录。可能有些地方理解地不太对，如有发现还请大神指出。
操作系统内存布局
各种 malloc 的内存分配管理方式离不开操作系统的内存布局策略。
32 位经典内存布局
32 位系统下经典内存布局如上，程序起始的 1GB 地址为内核空间，接下来是向下增长的栈空间和由 0x40000000 向上增长的 mmap 地址。而堆地址是从底部开始，去除 ELF、数据段、代码段、常量段之后的地址并向上增长。但是这种布局有几个问题，首先是容易遭受溢出攻击；其次是，堆地址空间只有不到 1G有木有？如果 mmap 内存比较少地址很浪费有木有？所以后来就有了另一种内存布局。
32 位默认内存布局
这幅图描述地比较清楚也比较完整。首先是加入了几种 Random offset 随机偏移，导致内存溢出攻击不那么容易了，其次是堆仍然向上，但是mmap 向下增长。但是这样的话栈空间就不是动态增长的了，所以现在的操作系统都有栈大小限制来着（Windows 好像默认是 2MB 对吧？Linux 可以 ulimit –s 查看）。这种内存布局地址利用度比较高。
64 位内存布局
64 位系统的寻址空间比较大，所以仍然沿用了 32 位的经典布局，但是加上了随机的 mmap 起始地址，以防止溢出攻击。反正一时半会是用不了这么大的内存地址了，所以至少 N 多年不会变了（话说要生产出 40TB + 的内存条，把堆内存地址用光，一时半会也搞不定吧）。
总结
纵观各种内存布局，对于大内存各种 malloc 基本上都是直接 mmap 的。而对于小数据，则通过向操作系统申请扩大堆顶，这时候操作系统会把需要的内存分页映射过来，然后再由这些 malloc 管理这些堆内存块，减少系统调用。而在 free 内存的时候，不同的 malloc 有不同的策略，不一定会把内存真正地还给系统，所以很多时候，如果访问了 free 掉的内存，并不会立即 Run Time Error，只有访问的地址没有对应的内存分页，才会崩掉。
Ptmalloc
Ptmalloc 采用主 - 从分配区的模式，当一个线程需要分配资源的时候，从链表中找到一个没加锁的分配区，在进行内存分配。
小内存分配
在 ptmalloc 内部，内存块采用chunk管理，并且将大小相似的 chunk 用链表管理，一个链表被称为一个 bin。前 64 个 bin 里，相邻的 bin 内的 chunk 大小相差 8 字节，称为small bin，后面的是large bin，large bin 里的 chunk 按先大小，再最近使用的顺序排列，每次分配都找一个最小的能够使用的 chunk。
Chunk 的结构如上所示，A 位表示是不是在主分配区，M 表示是不是 mmap 出来滴，P 表示上一个内存紧邻的 chunk 是否在使用，如果没在使用，则 size of previous chunk 是上一个 chunk 的大小，否则无意义（而且被用作被分配出去的内存了），正式根据 P 标记位和size of previous chunk在 free 内存块的时候来进行 chunk 合并的。当然，如果 chunk 空闲，mem 里还记录了一些指针用于索引临近大小的 chunk 的，实现原理就不复述了，知道大致作用就行。
在 free 的时候，ptmalloc 会检查附近的 chunk，并尝试把连续空闲的 chunk 合并成一个大的 chunk，放到 unstored bin 里。但是当很小的 chunk 释放的时候，ptmalloc 会把它并入 fast bin 中。同样，某些时候，fast bin 里的连续内存块会被合并并加入到一个 unsorted bin 里，然后再才进入普通 bin 里。所以 malloc 小内存的时候，是先查找 fast bin，再查找 unsorted bin，最后查找普通的 bin，如果 unsorted bin 里的 chunk 不合适，则会把它扔到 bin 里。
大内存分配
Ptmalloc 的分配的内存顶部还有一个 top chunk，如果前面的 bin 里的空闲 chunk 都不足以满足需要，就是尝试从 top chunk 里分配内存。如果 top chunk 里也不够，就要从操作系统里拿了。
还有就是特别大的内存，会直接从系统 mmap 出来，不受 chunk 管理，这样的内存在回收的时候也会 munmap 还给操作系统。
简而言之，就是：**
**小内存： [获取分配区 (arena) 并加锁] -> fast bin -> unsorted bin -> small bin -> large bin -> top chunk -> 扩展堆
大内存： 直接 mmap
总结
释放的时候，几乎是和分配反过来，再加上可一些 chunk 合并和从一个 bin 转移到另一个 bin 的操作。并且如果顶部有足够大的空闲 chunk，则收缩堆顶并还给操作系统。
介于此，对于 ptmalloc 的内存分配使用有几个注意事项：
- Ptmalloc 默认后分配内存先释放，因为内存回收是从 top chunk 开始的。
- 避免多线程频繁分配和释放内存，会造成频繁加解锁。
- 不要分配长生命周期的内存块，容易造成内碎片，影响内存回收。
Tcmalloc
Ptmalloc 在性能上还是存在一些问题的，比如不同分配区（arena）的内存不能交替使用，比如每个内存块分配都要浪费 8 字节内存等等，所以一般倾向于使用第三方的 malloc。
Tcmalloc 是 Google gperftools 里的组件之一。全名是 thread cache malloc（线程缓存分配器）其内存管理分为线程内存和中央堆两部分。
小内存分配
对于小块内存分配，其内部维护了60 个不同大小的分配器（实际源码中看到的是 86 个），和 ptmalloc 不同的是，它的每个分配器的大小差是不同的，依此按 8 字节、16 字节、32 字节等间隔开。在内存分配的时候，会找到最小复合条件的，比如 833 字节到 1024 字节的内存分配请求都会分配一个 1024 大小的内存块。如果这些分配器的剩余内存不够了，会向中央堆申请一些内存，打碎以后填入对应分配器中。同样，如果中央堆也没内存了，就向中央内存分配器申请内存。
在线程缓存内的 60 个分配器（文档上说 60 个，但是我在 2.0 的代码里看到得是 86 个）分别维护了一个大小固定的自由空间链表，直接由这些链表分配内存的时候是不加锁的。但是中央堆是所有线程共享的，在由其分配内存的时候会加自旋锁 (spin lock)。
在线程内存池每次从中央堆申请内存的时候，分配多少内存也直接影响分配性能。申请地太少会导致频繁访问中央堆，也就会频繁加锁，而申请地太多会导致内存浪费。在 tcmalloc 里，这个每次申请的内存量是动态调整的，调整方式使用了类似把 tcp 窗口反过来用的慢启动（slow start）算法调整 max_length， 每次申请内存是申请 max_length 和每个分配器对应的 num_objects_to_move 中取小的值的个数的内存块。
num_objects_to_move取值比较简单，是以 64K 为基准，并且最小不低于 2，最大不高于 32 的值。也就是说，对于大于等于 32K 的分配器这个值为 2（好像没有这样的分配器 class），对于小于 2K 的分配器，统一为 32。其他的会把数据调整到 64K / size 的个数。（可能是经验数值，目前 2.0 版本里的代码是这么写的）
对于 max_length 就比较复杂了，而且其更多是用于释放内存。max_length 由 1 开始，在其小于 num_objects_to_move 的时候每次累加 1，大于等于的时候累加 num_objects_to_move。释放内存的时候，首先 max_length 会对齐到 num_objects_to_move，然后在大于 num_objects_to_move 的释放次数超过一定阀值，则会按 num_objects_to_move 缩减大小。
大内存分配
对于大内存分配 (大于 8 个分页, 即 32K)，tcmalloc 直接在中央堆里分配。中央堆的内存管理是以分页为单位的，同样按大小维护了 256 个空闲空间链表，前 255 个分别是 1 个分页、2 个分页到 255 个分页的空闲空间，最后一个是更多分页的小的空间。这里的空间如果不够用，就会直接从系统申请了。
分页管理 – span
Tcmalloc 使用一种叫span的东东来管理内存分页，一个 span 可以包含几个连续分页。一个 span 的状态只有未分配(这时候在空闲链表中)，作为大对象分配，或作为小对象分配（这时候 span 内记录了小对象的 class size）。
在 32 位系统中，span 分为两级由中央分配器管理。第一级有 2^5 个节点，第二级是 2^15 个。32 位总共只能有 2^20 个分页（每个分页 4KB = 2^12）。(骗纸，我在代码里明明看到的是 2^7 和 2^13，定义了 TCMALLOC_LARGE_PAGES 宏之后才是 2^5 和 2^15，可是所有的代码或者编辑脚本里都没定义这个宏，可能是文档没更新)
在 64 为系统中，有三级。
在资源释放的时候，首先计算其分页编号，然后再查找出它对应的 span，如果它是一个小对象，则直接归入小对象分配器的空闲链表。等到空闲空间足够大以后划入中央堆。如果是大对象，则会把物理地址连续的前后的 span 也找出来，如果空闲则合并，并归入中央堆中。
而线程缓存内的分配器，会根据 max_length、num_objects_to_move 和上一次垃圾收集到现在为止的最小链表长度，按一定的策略回收资源到中央堆中，具体的算法不再复述 tcmalloc 的文档写得比较清楚。同样可以在需要时减少某一个线程的 max_length 来转移内存，但是要等到那个线程下一次执行 free，触发垃圾回收之后才会真正把内存返还中央堆。
简而言之，就是：
**小内存： 线程缓存队列 -> 中央堆 -> 中央页分配器（从系统分配）
大内存： 中央堆 -> 向系统请求
Tcmalloc 的管理策略和 ptmalloc 有很大区别，理论上性能提高的主要原因在线程缓存不加锁和少量操作的自旋锁上。不过按照它的实现方式，不适合多线程频繁分配大于 8 个分页（32KB）的内存。否则自旋锁争用会相当厉害，不过这种情况也比较少。而减少和中央堆交互又依赖于他的线程缓存长度自适应算法。
还有就是它使用了外部的数据结构来管理 span list，这样不会每次分配内存都要浪费 header 的长度。但是他的对齐操作又比 ptmalloc 多浪费了一些内存。（有点空间换时间的意思）
所以无论是 ptmalloc 还是 tcmalloc 都应该尽量减少大内存的分配和释放。尽量先分配、后释放。
Jemalloc
最后来看看第三个神器，jemalloc。这是 FreeBSD、NetBSD 和 Firefox 的默认 malloc。据作者说，在高 CPU 核心数的情况下比 tcmalloc 性能还好。
Jemalloc 的设计目标是：
- 快速分配和回收
- 低内存碎片
- 支持堆性能分析
Jemalloc 把内存分配分为了三个部分，第一部分类似 tcmalloc，是分别以 8 字节、16 字节、64 字节等分隔开的small class；第二部分以分页为单位，等差间隔开的large class；然后就是huge class。内存块的管理也通过一种 chunk 进行，一个 chunk 的大小是 2^k (默认 4 MB)。通过这种分配实现常数时间地分配 small 和 large 对象，对数时间地查询 huge 对象的 meta（使用红黑树）。
默认 64 位系统的划分方式如下：
Small: [8], [16, 32, 48, …, 128], [192, 256, 320, …, 512], [768, 1024, 1280, …, 3840]
Large: [4 KiB, 8 KiB, 12 KiB, …, 4072 KiB]
Huge: [4 MiB, 8 MiB, 12 MiB, …]
Jemalloc 也使用了分配区（arena）来维护内存。线程按第一次分配 small 或者 large 内存请求的顺序 Round-Robin 地选择一个分配区。每个分配区都维护了一系列分页，来提供 small 和 large 的内存分配请求。并且从一个分配区分配出去的内存块，在释放的时候一定会回到该分配区。
内存分配
每个分配区内都会包含 meta 信息，记录了其对应的chunk 列表，每个 chunk 的头部都记录了 chunk 的分配信息。在使用某一个 chunk 的时候，会把它分割成很多个 run，并记录到 bin 中。不同 size 的 class 对应着不同的 bin，这点和前面两种分配器一样。在bin 里，都会有一个红黑树来维护空闲的 run，并且在 run 里，使用了 bitmap 来记录了分配状态。
和前面两种分配器不同的是，分配区会同时维护两组 run 的红黑树，一组是未被分配过内存（clean 区域），另一组是回收的内存（dirty 区域）。而且不是前面那两种分配器所使用的链表。
同样，每次分配，都是选取最小且符合条件的内存块。但是优先从 dirty 区域查找。
由于分配区的设计和 ptmalloc 差不多。在访问分配区的时候需要对其加锁，或者对某一个 size 的 bin 加粒度更小的锁。为了减少锁征用，这里又参照 tcmalloc 引入了线程缓存。并且其线程缓存的垃圾回收机制和 tcmalloc 一样，也是基于分配请求的频率自动调整的。
线程缓存的结构就像一个简化版的 arena，加了一些垃圾回收的控制信息。
简而言之，就是：
**小内存（small class）： 线程缓存 bin -> 分配区 bin(bin 加锁) -> 问系统要
中型内存（large class）：分配区 bin(bin 加锁) -> 问系统要
大内存（huge class）： 直接 mmap 组织成 N 个 chunk + 全局 huge 红黑树维护 (带缓存)
总结
Jemalloc 设计上比前两个复杂地多，其内部使用了红黑树管理分页和内存块。并且对内存分配粒度分类地更细。这导致一方面比 ptmalloc 的锁争用要少，另一方面很多索引和查找都能回归到指数级别，方便了很多复杂功能的实现。而且在大内存分配上，内存碎片也会比 tcmalloc 少。但是也正是因为他的结构比较复杂，记录了很多 meta，所以在分配很多小内存的时候记录 meta 数据的空间会略微多于 tcmalloc。但是又不像 ptmalloc 那样每一个内存块都有一个 header，而采用全局的 bitmap 记录状态，所以大量小内存的时候，会比 ptmalloc 消耗的额外内存小。
大总结
看这些个分配器的分配机制，可见这些内存管理机制都是针对小内存分配和管理。对大块内存还是直接用了系统调用。所以在程序中应该尽量避免大内存的 malloc/new、free/delete 操作。另外这个分配器的最小粒度都是以 8 字节为单位的，所以频繁分配小内存，像 int 啊 bool 啊什么的，仍然会浪费空间。经过测试无论是对 bool、int、short 进行 new 的时候，实际消耗的内存在 ptmalloc 和 tcmalloc 下 64 位系统地址间距都是 32 个字节。大量 new 测试的时候，ptmalloc 平均每次 new 消耗 32 字节，tcmalloc 消耗 8 字节（我想说 ptmalloc 弱爆啦，而且 tcmalloc）。所以大量使用这些数据的时候不妨用数组自己维护一个内存池，可以减少很多的内存浪费。（原来 STL 的 map 和 set 一个节点要消耗近 80 个字节有这么多浪费在这里了啊）
而多线程下对于比较大的数据结构，为了减少分配时的锁争用，最好是自己维护内存池。单线程的话无所谓了，呵呵。不过自己维护内存池是增加代码复杂度，减少内存管理复杂度。但是我觉得，255 个分页以下（1MB）的内存话，tcmalloc 的分配和管理机制已经相当 nice，没太大必要自己另写一个。
另外，Windows 下内存分配方式不知道，不同类型 (int、short 和 bool) 连续 new 的地址似乎是隔开的，可能是内部实现的粒度更小，不同 size 的 class 更多。测试 10M 次 new 的时候，debug 模式下明显卡顿了一下，平均每次 new 的内存消耗是 52 字节（32 位）和 72 字节（64 位）[header 更复杂?]。但是Release 模式下很快，并且平均每次 new 的内存消耗是 20 字节（32 位）和 24 字节（64 位）。可以猜测 VC 的 malloc 的 debug 模式还含有挺大的 debug 信息。是不是可以得出他的 header 里，Release 版本只有 1 个指针，Debug 里有 5 个指针呢？
参考文献：
- glibc 内存管理 ptmalloc 源代码分析 http://rdc.taobao.com/blog/cs/?p=1015
- tcmalloc http://gperftools.googlecode.com/svn/trunk/doc/tcmalloc.html
- Scalable memory allocation using jemalloc http://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919
- A Scalable Concurrent malloc(3) Implementation for FreeBSD http://people.freebsd.org/~jasone/jemalloc/bsdcan2006/jemalloc.pdf
- jemalloc 原理分析 http://club.alibabatech.org/article_detail.htm?articleId=36
- Tcmalloc 2.0 源码
- Jemalloc 3.4.0 源码
https://cloud.tencent.com/developer/article/1173720
若有收获，就点个赞吧
0 人点赞
