1-1.内存分配基础-TCmalloc
Last updated
Last updated
上图展示了一个进程的虚拟内存划分，代码中使用的内存地址都是虚拟内存地址，而不是实际的物理内存地址。栈和堆只是虚拟内存上2块不同功能的内存区域：
栈在高地址，从高地址向低地址增长
堆在低地址，从低地址向高地址增长
栈和堆相比有这么几个好处：
栈的内存管理简单，分配比堆上快。
栈的内存不需要垃圾回收介入处理，而堆需要进行回收，无论是主动 free，还是被动的垃圾回收，这都需要花费额外的 CPU。
栈上的内存有更好的局部性，堆上内存访问就不那么友好了，CPU 访问的 2 块数据可能在不同的页上，访问数据可能就比较耗时。
内存分配器一般包含两种分配方法，一种是线性分配器（Sequential Allocator，Bump Allocator），另一种是空闲链表分配器（Free-List Allocator）
线性分配器
线性分配（Bump Allocator）是一种高效的内存分配方法，但是有较大的局限性。当我们使用线性分配器时，只需要在内存中维护一个指向内存特定位置的指针，如果用户程序向分配器申请内存，分配器只需要检查剩余的空闲内存、返回分配的内存区域并修改指针在内存中的位置，即移动下图中的指针：
该方案有较快的执行速度以及较低的实现复杂度，但无法在内存被释放时重用内存，如上图中红色的内存。该方案需要与合适的垃圾回收算法配合使用，例如：标记压缩（Mark-Compact）、复制回收（Copying GC）和分代回收（Generational GC）等算法，它们可以通过拷贝的方式整理存活对象的碎片，将空闲内存定期合并
因为线性分配器需要与具有拷贝特性的垃圾回收算法配合，所以 C 和 C++ 等需要直接对外暴露指针的语言就无法使用该策略
空闲链表分配器
维护一个类似链表的数据结构。当用户程序申请内存时，依次遍历链表，找到空闲且足够大的内存，然后申请新的资源并修改链表
由于需要遍历链表，它的时间复杂度是 𝑂(𝑛)。空闲链表分配器可以选择不同的策略在链表中的内存块中进行选择，最常见的是以下四种：
首次适应（First-Fit）：从链表头开始遍历，选择第一个大小大于申请内存的内存块
循环首次适应（Next-Fit）：从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块
最优适应（Best-Fit）：整个链表遍历一遍，选择最合适的内存块
隔离适应（Segregated-Fit）：将内存分割成多个不同大小规格的链表，申请内存时先找到满足条件的链表，再从链表中选择合适的内存块
TCmalloc 使用的策略与第四种策略有些相似
TCMalloc (Thread-Caching Malloc)，线程缓存分配器，是 Google 开发的内存分配器，Go 的内存管理正是借鉴了 TCMalloc。
它的核心理念用一句话表示：使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略。
在Linux操作系统中，其实有不少的内存管理库，比如glibc的ptmalloc，FreeBSD的jemalloc，Google的tcmalloc等等，为何会出现这么多的内存管理库？本质都是在多线程编程下，追求更高内存管理效率：更快的分配是主要目的。
同一进程下的所有线程共享相同的内存空间，它们申请内存时需要加锁，如果不加锁就存在同一块内存被 2 个线程同时访问的问题。
TCMalloc 的做法是什么呢？为每个线程预分配一块缓存，线程申请小内存时，可以直接从这个缓存分配内存，这样有2个好处：
减少系统调用：为线程预分配缓存需要进行 1 次系统调用，后续线程申请小内存时直接从缓存分配，都是在用户态执行的，不会再进行系统调用，缩短了分配和释放时间。
减少并发竞争：多个线程同时申请小内存时，从各自的缓存分配，访问的是不同的地址空间，从而无需加锁，把内存并发访问的粒度进一步降低了。
结合上图，从右往左看，介绍 TCMalloc 的几个重要概念：
Page
操作系统对内存管理以页为单位，TCMalloc 也是这样，只不过 TCMalloc 里的 Page 大小与操作系统里的大小并不一定相等，而是倍数关系。《TCMalloc解密》里称 x64 下 Page 大小是 8KB。
Span
上图中蓝色方块。多个 Page 组成一个 Span，比如可以有 2 个页大小的 Span，也可以有 16 页大小的 Span，Span 比 Page 高一个层级，是为了方便管理一定大小的内存区域，Span 是 TCMalloc 中内存管理的基本单位。
ThreadCache 线程缓存
上图橙色区域。ThreadCache 是线程级的 Cache，一个 Cache 包含多个空闲内存块链表，每个链表连接的都是内存块，同一个链表上内存块的大小是相同的，也可以说按内存块大小，给内存块分了个类，这样可以根据申请的内存大小，快速从合适的链表选择空闲内存块。每个线程有自己的 ThreadCache，访问时无需加锁。
CentralCache 中心缓存
上图黄色区域。CentralCache 是所有线程共享的缓存，也是保存的空闲内存块链表，链表的数量与 ThreadCache 中链表数量相同，当 ThreadCache 的内存块不足时，可以从CentralCache 获取内存块； ThreadCache 内存块过多时，可以放回 CentralCache。由于 CentralCache 是共享的，所以它的访问是要加锁的。
PageHeap 页堆
PageHeap 是对堆内存的抽象，PageHeap 存的也是若干链表，链表保存的是 Span。当 CentralCache 的内存不足时，会从 PageHeap 获取空闲的内存 Span，然后把 1 个 Span 拆成若干内存块，添加到对应大小的链表中并分配内存；当 CentralCache 的内存过多时，会把空闲的内存块放回 PageHeap 中。
另外前面几层主要用于小内存对象的管理，大对象的内存直接从页堆分配。
下面将详细介绍这几个概念：
一个 Page 4KB，如果对象小于 4KB，分配在这个 Page 里即可。
首先是基本问题，假设所有对象大小固定，如何分配空间？例如，我们有一个 Page 的内存，大小为 4KB，现在已知每个对象大小为 N 字节, 要以 N 字节 为单位进行分配。为了简化问题，假设 N=16, 就以 16 字节 为单位进行分配。
解法有很多，简单的比如 bitmap。4KB / 16 / 8 = 32，用 32 字节做 bitmap 即可，标记每个单位是否被使用。
出于最大化内存利用率的目的，我们使用另一种经典的方式，freelist。将 4KB 的内存划分为 16B 的单元，每个单元的前 8B 作为节点指针，指向下一个单元。初始化的时候把所有指针指向下一个单元；分配时，从链表头分配一个对象出去；释放时，插入到链表。
由于链表指针直接分配在待分配内存中，因此不需要额外的内存开销，而且分配速度也是相当快。
我们把所有的变长记录进行取整，例如需要 7B，就分配 8B，31B 分配 32B，得到多种规格的定长记录。
就像快递盒一样，我们只提供有限几种尺寸的盒子，这样即使物品的尺寸有无限多种，我们只选一个最接近的尺寸来包装。
这里带来了内部内存碎片的问题，即分配出去的空间不会被完全利用，有一定浪费。为了减少内部碎片，分配规则按照 8, 16, 32, 48, 64, 80这样子来。注意到，这里并不是简单地使用2的幂级数，因为按照 2 的幂级数，内存碎片会相当严重，申请 65B，实际会分配 128B，接近 50% 的内存碎片。而按照这里的分配规格，只会分配 80B ，一定程度上减轻了问题。
上面讲的是基于 Page，分配小于 Page 的对象，但是如果分配的对象大于一个 Page，我们就需要用多个 Page 来分配了。
这里提出了 Span 的概念，也就是多个连续的 Page 会组成一个 Span，在 Span 中记录起始 Page 的编号，以及 Page 数量。
分配对象时，大的对象直接分配 Span，小的对象从 Span 中取一部分空间分配。
对于 Span 的管理，我们炮制 Page 里变长对象的管理方式，便实现了 PageHeap。
span 就是快递盒，会有各种不同尺寸的 span。PageHeap 里将相同规格的 span 用链表串在一起。
还是用多种定长 Page 来实现变长 Page 的分配，初始时只有 128 Page 的 Span，如果要分配 1 个 Page 的 Span，就把这个 Span 分裂成两个，1 + 127，把 127 再记录下来。对于 Span 的回收，需要考虑 Span 的合并问题，否则在分配回收多次之后，就只剩下很小的 Span 了，也就是带来了外部碎片 问题。
为此，释放 Span 时，需要将前后的空闲 Span 进行合并，当然，前提是它们的 Page 要连续。
既然有了基于 Page 的对象分配，和 Page 本身的管理，我们把它们串起来就可以得到一个简单的内存分配器了：
按照我们之前设计的，每种规格的对象，都从不同的 Span 进行分配；每种规则的对象都有一个独立的内存分配单元：CentralCache。在一个 CentralCache 内存，我们用链表把所有 Span 组织起来，每次需要分配时就找一个 Span 从中分配一个 Object；当没有空闲的 Span 时，就从 PageHeap 申请 Span。
看起来基本满足功能，但是这里有一个严重的问题，在多线程的场景下，所有线程都从 CentralCache 分配的话，竞争可能相当激烈。
因此给每个线程分配了一个线程局部的 ThreadCache，来避免多线程下 CentralCache 的竞争问题。按照不同的规格，ThreadCache 维护了对象的链表；如果 ThreadCache 的对象不够了，就从 CentralCache 进行批量分配；如果 CentralCache 依然没有，就从 PageHeap 申请 Span；如果 PageHeap 没有合适的 Page，就只能从操作系统申请了。
在释放内存的时候，ThreadCache 依然遵循批量释放的策略，对象积累到一定程度就释放给 CentralCache；CentralCache 发现一个 Span 的内存完全释放了，就可以把这个 Span 归还给 PageHeap；PageHeap 发现一批连续的 Page 都释放了，就可以归还给操作系统。
至此，TCMalloc 的大体结构便呈现在我们眼前了。
小对象的分配流程：ThreadCache -> CentralCache -> HeapPage，大部分时候，ThreadCache缓存都是足够的，不需要去访问 CentralCache 和 HeapPage，无系统调用配合无锁分配，分配效率是非常高的。
中对象分配流程：直接在 PageHeap 中选择适当的大小即可，128 Page 的 Span 所保存的最大内存就是 1MB。
大对象分配流程：还有个 large span set，专门给大对象用的，从中选择合适数量的页面组成 span，用来存储数据。
