译|从零开始的 Go 内存分配器可视化指南（golang）

原文：A visual guide to Go Memory Allocator from scratch (Golang)

当我第一次开始试图了解 Go 的内存分配器时，觉得它真令人抓狂。所有的所有都像是神秘的黑盒子。而由于几乎每一个技术魔法都隐藏在抽象之下，因此，你需要层层剥开才能理解它。

因此，在这篇博文中，我们将就做这件事。你想学习关于 Go 内存分配器的所有东西吗？那么，阅读这篇文章算是对了。

物理内存和虚拟内存

每一个内存分配器都需要使用由底层操作系统管理的虚拟内存空间。我们来看看它是如何工作的。

上图为物理内存单元的一个简单说明（并非精确表示）

单个内存单元的大大简化概述：

地址线（晶体管作为开关）提供对电容器（数据到数据线）的访问。
当地址线有电流流动时（显示为红色），那么数据线可以写入电容器，因此，电容器充电，存储的逻辑值为“1”。
当地址线没有电流流动时（显示为绿色），那么数据线不可以写入电容器，因此，电容器未充电，存储的逻辑值为“0”。
当 CPU 需要从 RAM“读取”值时，电流会沿着“地址线”发送（关闭开关）。如果电容器正处于充电状态，那么电流则沿着“数据线”向下流动（值为 1）；否则，没有电流流过数据线，故而电容器保持不带电状态（值为 0）。

（上图为物理内存单元与 CPU 交互方式的简单说明）

数据总线：在 CPU 和物理内存之间传输数据。

让我们稍微聊聊地址线和可寻址字节。

CPU 和物理内存之间的地址线的说明性表示。

1. DRAM 中的每一个“字节”被赋予一个唯一的数字标识符（地址）。 “存在的物理字节 != 地址线的数目”。(例如，16bit intel 8088, PAE)

2. 每一个地址线可以发送 1-bit 值，因此，它以给定字节地址的方式指定了“一位”。

3. 在我们的图中，我们有 32 条地址线。因此，每一字节都有一个“32 位”地址。 [ 00000000000000000000000000000000 ] — 低位内存地址。 [ 11111111111111111111111111111111 ] — 高位内存地址。

4. 由于对于每个字节我们都有一个 32 位地址，因此，我们的地址空间由 2³² 个可寻址字节（4 GB）组成（在上面的说明性表示中）。

故而，可寻址字节依赖于总地址线，因此，对于 64 条地址线（x86–64 CPU），则有 2⁶⁴ 个可寻址字节（16 个艾字节），但是，大多数使用 64 位指针的架构实际上使用的是 48 位地址线（AMD64）和 42 位地址线（Intel），因此，理论上允许 256 TB 的物理 RAM（Linux 允许[带四级页面表](https://www.kernel.org/doc/Documentation/x86/x86_64/mm.txt) 的 x86-64 上的每个进程拥有大小为 128TB 的地址空间，而 windows 则是 192TB）

由于物理 RAM 的大小有限，因此，每个进程都运行在其自己的内存沙箱中 —— “虚拟地址空间”，又称虚拟内存。

在此虚拟地址空间中的字节地址不再与处理器强加于地址总线的地址相同。一次呢，必须建立转换数据结构和系统，来将虚拟地址空间中的字节映射到物理字节。

这个虚拟地址长啥样呢？

虚拟地址空间表示

因此，当 CPU 执行引用内存地址的指令时，第一步就是将 VMA 中的逻辑地址转换为线性地址（linear address）。此转换由 MMU 完成。

（这不是物理图，它只是描述。为简单起见，不包括地址转换过程。）

由于该逻辑地址太大以致于不能实际（取决于各种因素）单独管理，因此，它们是按页进行管理的。当必要的分页结构被激活时，虚拟内存空间被分成较小的区域，这就是页（在大多数的 OS 上，大小为 4kB，可以修改）。这是虚拟内存中的内存管理的最小数据单元。虚拟内存并不存储任何内容，它只是将程序的地址空间_映射_到底层的物理内存。

个别进程仅仅将此 VMA 视为其地址。因此，当我们的程序请求更多“堆内存”时，会发生什么呢？

上面是一个简单的汇编代码，它请求更多的堆内存。

上图为堆内存增量

程序通过 [brk](http://www.kernel.org/doc/man-pages/online/pages/man2/brk.2.html)（sbrk/mmap 等）系统调用，请求更多的内存。

内核仅仅更新堆 VMA，然后调用它。

此时，实际上并没有分配任何页帧，而且新的页也不存在于物理内存中。关键是 VSZ 与 RSS 大小之间的差异点。

内存分配器

通过“虚拟地址空间”的基本概述，以及增加堆的含义，内存分配器现在变得更容易理解了。

如果堆有足够的空间以满足代码的内存请求，那么内存分配器可以在没有内核参与的情况下完成请求，否则，它会通过系统（_brk_）调用来扩大堆，通常是请求大块内存。（默认情况下，分配大块内存意味着大于 MMAP_THRESHOLD 字节 -128 kB）。

然而，与仅仅更新 brk 地址 相比，内存分配器会更尽职些。其中主要是如何同时减少 internal 和 external 碎片，以及它可以多快分配块。考虑我们的程序以 p1 到 p4 的顺序，通过使用函数 malloc(size) 来请求连续内存块，然后使用函数 free(pointer) 释放该内存。

上图为外部碎片演示

在步骤 p4 中，即使我们有足够的内存块，但是仍然无法满足对 6 个连续内存块的请求，从而导致内存碎片。

所以，我们要如何减少内存碎片呢？这个问题的答案取决于底层库使用的具体的内存分配算法。

我们将看看 TCMalloc 概述，Go 内存分配器就是紧密模仿这个内存分配器的。

TCMalloc

TCMalloc（线程缓存内存分配）的核心思想是将内存划分为多个级别，以减少锁粒度。TCMalloc 内存管理内部分为两部分：线程内存和页堆。

线程内存

每个内存页分为 —— 多个可分配的固定大小规格（size class）的可用列表，这有助于减少碎片。因此，每个线程都将有一个没有锁的小对象缓存，这使得在并行程序下分配小对象（<= 32k）效率很高。

线程缓存（每个线程都获取自己线程的本地线程缓存）

页堆（Page Heap）

TCMalloc 管理的堆由一组页组成，其中，一组连续的页可以用 span 来表示。当分配的对象大于 32K 时，页堆被用于分配。

页堆（用于 span 管理）

当没有足够的内存来分配小对象时，就会转到页堆来分配内存。如果还是不够，那么页堆将会向操作系统请求更多的内存。

由于这样的分配模型维护了一个用户空间的内存池，故而能够极大提高内存分配和释放的效率。

注意：虽然说 go 内存分配器最初是基于 tcmalloc 的，但是二者之间已经分歧良多。

Go 内存分配器

我们知道，Go 运行时将 Goroutine（G）安排到逻辑处理器（P）上执行。同样，TCMalloc Go 也会将内存页划分成 67 个不同大小规格。

如果你不熟悉 Go 调度器，那么你可以看看概述（Go 调度器：M，P 和 G），我会在这里等你看完。

Go 的大小规格（size class）

由于 Go 以 8192B 的粒度管理页，因此如果该页面被分成大小为 1kB 的块，那么，对于该页，我们就能获得总共 8 个这样的块。例如：

8 KB 页面被分成 1KB 的大小规格（size class）（在 Go 中，页以 8KB 的粒度进行维护）

Go 中这些页的运行也通过称为 mspan 的结构进行管理。

mspan

简单来说，它是一个双链表对象，包含页的起始地址（startAddr）、页的 span 类（spanClass）以及所包含的页数目（npages）。

内存分配器中的 mspan 的说明性表示

mcache

正如 TCMalloc，Go 为每个逻辑处理器（P） 提供一个称为 mcache 的本地线程缓存，因此，如果 Goroutine 需要内存，那么它可以直接从 mcache 获取，而无需涉及任何的锁，因为在任何时候，逻辑处理器（P） 上面只会运行一个 Goroutine。

mcache 包含一个由所有大小规格组成的 mspan 作为缓存。

Go 中 P、mcache 和 mspan 之间关系的说明性表示。

由于每个 P 都有 mcache，因此从 mcache 分配内存的时候无需持有锁。

对于每一种大小规格，有两种类型。

scan — 包含指针的对象。
noscan — 不包含指针的对象。

这种方法的好处之一是在进行垃圾收集时，无需遍历 noscan 对象来找到任何包含活动对象的对象。

啥时会用到 mcache ？

大小 <= 32K 字节的对象会使用相应大小规格（size class）的 mspan，直接分配到 mcache。

当 mcache 没有空闲的 slot 时，会发生什么？

从所需大小规格（size class）的 mspans 的 mcentral 列表中获取新的 mspan。

mcentral

mcentral 对象收集给定大小规格（size class）的所有 span，每个 mcentral 由两个 mspans 列表组成。

empty mspanList — 非空闲对象（或者缓存在 mcache 中）的 mspan 列表。
nonempty mspanList — 拥有空闲对象的 span 列表。

mcentral 的说明性表示

mheap 结构维护每一个 mcentral 结构。

mheap

mheap 是 Go 中管理堆的对象，全局只有一个 mheap 实例。它拥有虚拟地址空间。

mheap 的说明性表示。

正如上面说明所示，mheap 拥有一个 mcentral 数组。该数组包含由每个 span 类组成的 mcentral。

central [numSpanClasses]struct {  
  	mcentral mcentral  
    	pad      [sys.CacheLineSize unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte  
}

由于对于每个 span 大小规格（size class），我们都有 mcentral，因此当 mcache 向 mcentral 请求 mspan 时，lock 被应用于单个 mcentral 级别，因此，还可以服务于任何其他同时请求不同大小的 mspan 的 mcache。

填充（Padding）确保 MCentral 固定 CacheLineSize 字节的间隔，这样，每一个 MCentral.lock 就可以获得自己的缓存行，从而避免错误的共享问题。

那么，当这个 mcentral 列表为空时，会发生什么呢？mcentral 会从 mheap 获取一连串的页，以组成所需大小规格（size class）的 span。

free [_MaxMHeapList]mSpanList：这是一个 spanList 数组。每一个 spanList 中的 mspan 由 1 ~ 127（_MaxMHeapList — 1）个页组成。例如，free[3] 是一个包含 3 个页的 mspans 链表。free 意味着空闲列表，也就是未分配。相对应的是 busy 列表。
freelarge mSpanList：mspans 列表。列表中每个元素（也就是 mspan）的页数都比 127 大。这作为 mtreap 数据结构进行维护。相对应的是 busylarge。

大小 > 32k 的对象是一个大对象，直接从 mheap 分配。这些大对象的分配请求是以中央锁为代价的，因此，在任何给定时间点只能处理一个 P 的请求。

对象分配流程

大小 > 32k 属于大对象，直接从 mheap 分配。
大小 < 16B 的对象，则使用 mcache 的微小分配器（tiny allocator）进行分配
大小介于 16B ~ 32k 之间的对象，则会计算要使用的 sizeClass，然后使用 mcache 中对应的 sizeClass 的块分配
- 如果 mcache 相应的 sizeClass 没有可用的块，则向 mcentral 申请。
- 如果 mcentral 没有可用的块，那么向 mheap 申请，然后使用 BestFit 来查找最适合的 mspan。如果超出了应用程序大小，那么，将根据需要进行划分，以返回用户所需的页数。其余的页面构成一个新的 mspan，并返回 mheap free 列表。
- 如果 mheap 没有可用的 span，那么向操作系统申请一组新的页（至少 1MB）。