> For the complete documentation index, see [llms.txt](https://wtifs.gitbook.io/diva-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wtifs.gitbook.io/diva-notes/go/6.-nei-cun-guan-li/11.-nei-cun-fen-pei-ji-chu-tcmalloc.md).

# 1-1.内存分配基础-TCmalloc

## 栈和堆

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-e683f6eb578fa93696858ed1d2337b76407d70a1%2Fv2-e31cd14b12214aefd979bb9885a3e546_1440w.jpg?alt=media)

上图展示了一个进程的虚拟内存划分，代码中使用的内存地址都是虚拟内存地址，而不是实际的物理内存地址。栈和堆只是虚拟内存上2块不同功能的内存区域：

* 栈在高地址，从高地址向低地址增长
* 堆在低地址，从低地址向高地址增长

栈和堆相比有这么几个好处：

* 栈的内存管理简单，分配比堆上快。
* 栈的内存不需要垃圾回收介入处理，而堆需要进行回收，无论是主动 `free`，还是被动的垃圾回收，这都需要花费额外的 `CPU`。
* 栈上的内存有更好的局部性，堆上内存访问就不那么友好了，`CPU` 访问的 `2` 块数据可能在不同的页上，访问数据可能就比较耗时。

## 堆内存管理

#### 分配方法

内存分配器一般包含两种分配方法，一种是线性分配器（Sequential Allocator，Bump Allocator），另一种是空闲链表分配器（Free-List Allocator）

**线性分配器**

线性分配（Bump Allocator）是一种高效的内存分配方法，但是有较大的局限性。当我们使用线性分配器时，只需要在内存中维护一个指向内存特定位置的指针，如果用户程序向分配器申请内存，分配器只需要检查剩余的空闲内存、返回分配的内存区域并修改指针在内存中的位置，即移动下图中的指针：

![bump-allocator-reclaim-memory](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-6c26ba4f87c2b7466e1a8da994aa645d0b8c225d%2F2021-02-28-16145096642930-bump-allocator-reclaim-memory.png?alt=media)

该方案有较快的执行速度以及较低的实现复杂度，但无法在内存被释放时重用内存，如上图中红色的内存。该方案需要与合适的垃圾回收算法配合使用，例如：标记压缩（Mark-Compact）、复制回收（Copying GC）和分代回收（Generational GC）等算法，它们可以通过拷贝的方式整理存活对象的碎片，将空闲内存定期合并

因为线性分配器需要与具有拷贝特性的垃圾回收算法配合，所以 C 和 C++ 等需要直接对外暴露指针的语言就无法使用该策略

**空闲链表分配器**

维护一个类似链表的数据结构。当用户程序申请内存时，依次遍历链表，找到空闲且足够大的内存，然后申请新的资源并修改链表

由于需要遍历链表，它的时间复杂度是 𝑂(𝑛)。空闲链表分配器可以选择不同的策略在链表中的内存块中进行选择，最常见的是以下四种：

* 首次适应（First-Fit）：从链表头开始遍历，选择第一个大小大于申请内存的内存块
* 循环首次适应（Next-Fit）：从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块
* 最优适应（Best-Fit）：整个链表遍历一遍，选择最合适的内存块
* 隔离适应（Segregated-Fit）：将内存分割成多个不同大小规格的链表，申请内存时先找到满足条件的链表，再从链表中选择合适的内存块

TCmalloc 使用的策略与第四种策略有些相似

## TCmalloc

TCMalloc (Thread-Caching Malloc)，线程缓存分配器，是 Google 开发的内存分配器，Go 的内存管理正是借鉴了 TCMalloc。

它的核心理念用一句话表示：**使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略。**

在Linux操作系统中，其实有不少的内存管理库，比如glibc的ptmalloc，FreeBSD的jemalloc，Google的tcmalloc等等，为何会出现这么多的内存管理库？本质都是在多线程编程下，追求更高内存管理效率：更快的分配是主要目的。

同一进程下的所有线程共享相同的内存空间，它们申请内存时需要加锁，如果不加锁就存在同一块内存被 2 个线程同时访问的问题。

TCMalloc 的做法是什么呢？为每个线程预分配一块缓存，线程申请小内存时，可以直接从这个缓存分配内存，这样有2个好处：

1. 减少系统调用：为线程预分配缓存需要进行 1 次系统调用，后续线程申请小内存时直接从缓存分配，都是在用户态执行的，不会再进行系统调用，缩短了分配和释放时间。
2. 减少并发竞争：多个线程同时申请小内存时，从各自的缓存分配，访问的是不同的地址空间，从而无需加锁，把内存并发访问的粒度进一步降低了。

### 基本原理

![preview](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-47b18bd41f53514144d43bf37b59c478ed0675cb%2Fv2-17a205c8fdfe0d21ab06f469df72b2fe_r-20210629225321854.jpg?alt=media)

结合上图，从右往左看，介绍 `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

一个 `Page 4KB`，如果对象小于 `4KB`，分配在这个 `Page` 里即可。

#### 固定size对象

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-19c1ca4c333d515af1f1456dff2012e92dcc8d92%2Fv2-8627f1c08819b6c8bd03d0b74935ba19_1440w.png?alt=media)

首先是基本问题，假设所有对象大小固定，如何分配空间？例如，我们有一个 `Page` 的内存，大小为 `4KB`，现在已知每个对象大小为 `N 字节`, 要以 `N 字节` 为单位进行分配。为了简化问题，假设 `N=16`, 就以 `16 字节` 为单位进行分配。

解法有很多，简单的比如 `bitmap`。`4KB / 16 / 8 = 32`，用 32 字节做 `bitmap` 即可，标记每个单位是否被使用。

出于最大化内存利用率的目的，我们使用另一种经典的方式，`freelist`。将 `4KB` 的内存划分为 `16B` 的单元，每个单元的前 `8B` 作为节点指针，指向下一个单元。初始化的时候把所有指针指向下一个单元；分配时，从链表头分配一个对象出去；释放时，插入到链表。

由于链表指针直接分配在待分配内存中，因此不需要额外的内存开销，而且分配速度也是相当快。

#### 变长size对象

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-07a293ed3150fc8f7701bcc5f2d89c169a916870%2Fv2-2c7c35cc567510ab8187b18297217b81_1440w.png?alt=media)

我们把所有的变长记录进行取整，例如需要 `7B`，就分配 `8B`，`31B` 分配 `32B`，得到多种规格的定长记录。

就像快递盒一样，我们只提供有限几种尺寸的盒子，这样即使物品的尺寸有无限多种，我们只选一个最接近的尺寸来包装。

这里带来了内部内存碎片的问题，即分配出去的空间不会被完全利用，有一定浪费。为了减少内部碎片，分配规则按照 8, 16, 32, 48, 64, 80这样子来。注意到，这里并不是简单地使用2的幂级数，因为按照 `2` 的幂级数，内存碎片会相当严重，申请 `65B`，实际会分配 `128B`，接近 `50%` 的内存碎片。而按照这里的分配规格，只会分配 `80B` ，一定程度上减轻了问题。

### Span

上面讲的是基于 `Page`，分配小于 `Page` 的对象，但是如果分配的对象大于一个 `Page`，我们就需要用多个 `Page` 来分配了。

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-c6fe0b4cacc39b53eef76f7c472688990009a444%2Fv2-10c1aaa4eb52977fb9330d015d851cdf_1440w.png?alt=media)

这里提出了 `Span` 的概念，也就是多个连续的 `Page` 会组成一个 `Span`，在 `Span` 中记录起始 `Page` 的编号，以及 Page 数量。

分配对象时，大的对象直接分配 `Span`，小的对象从 `Span` 中取一部分空间分配。

### PageHeap

对于 `Span` 的管理，我们炮制 `Page` 里变长对象的管理方式，便实现了 `PageHeap`。

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-7884624d43a0d75406950ff0347dab872e4f3302%2Fv2-8092c1103b6f8f3bc64952e922451ea4_1440w-20210704232914013.png?alt=media)

`span` 就是快递盒，会有各种不同尺寸的 `span`。`PageHeap` 里将相同规格的 `span` 用链表串在一起。

还是用多种定长 `Page` 来实现变长 `Page` 的分配，初始时只有 `128 Page` 的 `Span`，如果要分配 `1` 个 `Page` 的 `Span`，就把这个 `Span` 分裂成两个，`1 + 127`，把 `127` 再记录下来。对于 `Span` 的回收，需要考虑 `Span` 的合并问题，否则在分配回收多次之后，就只剩下很小的 `Span` 了，也就是带来了**外部碎片** 问题。

为此，释放 `Span` 时，需要将前后的空闲 `Span` 进行合并，当然，前提是它们的 `Page` 要连续。

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-d792a61689e0f0d569df4e43e8b4d3a75a30d6d2%2Fv2-c83e0ec9342a505e69cfeaf304d4bb9f_1440w-20210704233023836.png?alt=media)

### 全局对象分配

既然有了基于 `Page` 的对象分配，和 `Page` 本身的管理，我们把它们串起来就可以得到一个简单的内存分配器了：

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-dc2f5f5a40f69f9ef6f892422adf16950a7fe225%2Fv2-31841a2868a542b4e5384f938b56124e_1440w-20210704233606170.png?alt=media)

按照我们之前设计的，每种规格的对象，都从不同的 `Span` 进行分配；每种规则的对象都有一个独立的内存分配单元：`CentralCache`。在一个 `CentralCache` 内存，我们用链表把所有 `Span` 组织起来，每次需要分配时就找一个 `Span` 从中分配一个 `Object`；当没有空闲的 `Span` 时，就从 `PageHeap` 申请 `Span`。

看起来基本满足功能，但是这里有一个严重的问题，在多线程的场景下，**所有线程都从 CentralCache 分配的话，竞争可能相当激烈**。

### ThreadCache

因此给每个线程分配了一个线程局部的 `ThreadCache`，来避免多线程下 `CentralCache` 的竞争问题。按照不同的规格，`ThreadCache` 维护了对象的链表；如果 `ThreadCache` 的对象不够了，就从 `CentralCache` 进行批量分配；如果 `CentralCache` 依然没有，就从 `PageHeap` 申请 `Span`；如果 `PageHeap` 没有合适的 `Page`，就只能从操作系统申请了。

在释放内存的时候，`ThreadCache` 依然遵循批量释放的策略，对象积累到一定程度就释放给 `CentralCache`；`CentralCache` 发现一个 `Span` 的内存完全释放了，就可以把这个 `Span` 归还给 `PageHeap`；`PageHeap` 发现一批连续的 `Page` 都释放了，就可以归还给操作系统。

至此，`TCMalloc` 的大体结构便呈现在我们眼前了。

![img](https://4237436490-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FxhDxW69eCVrvTGotZqcT%2Fuploads%2Fgit-blob-4b8d94b4d13b7056e37ab5dc5ffbb7333b012f22%2Fv2-05a8740554bedf4dc0a6912c6e8551db_1440w-20210704233625910.png?alt=media)

小对象的分配流程：`ThreadCache` -> `CentralCache` -> `HeapPage`，大部分时候，`ThreadCache`缓存都是足够的，不需要去访问 `CentralCache` 和 `HeapPage`，无系统调用配合无锁分配，分配效率是非常高的。

中对象分配流程：直接在 `PageHeap` 中选择适当的大小即可，`128 Page` 的 `Span` 所保存的最大内存就是 `1MB`。

大对象分配流程：还有个 `large span set`，专门给大对象用的，从中选择合适数量的页面组成 `span`，用来存储数据。

### 参考

[hellocode - 图解TCMalloc](https://zhuanlan.zhihu.com/p/29216091)