125 lines
9.2 KiB
Markdown
125 lines
9.2 KiB
Markdown
|
## 设计原理
|
|||
|
|
|
|||
|
|
### 内存分配方式
|
|||
|
|
|
|||
|
|
- 线性分配
|
|||
|
|
- 空闲链表分配
|
|||
|
|
|
|||
|
|
#### 线性分配方式
|
|||
|
|
|
|||
|
|
- 线性分配（Bump Allocator）是一种高效的内存分配方法。只需要在内存中维护一个指向内存特定位置的指针，如果用户程序向分配器申请内存，分配器只需要检查剩余的空闲内存、返回分配的内存区域并修改指针在内存中的位置，即移动下图中的指针：
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
- 线性分配器实现带来较快的执行速度以及较低的实现复杂度，但是线性分配器无法在内存被释放时重用内存。如下图所示，如果已经分配的内存被回收，线性分配器无法重新利用红色的内存：
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
- 需要与垃圾分配算法配合使用，例如：标记压缩（Mark-Compact）、复制回收（Copying GC）和分代回收（Generational GC）等算法，它们可以通过拷贝的方式整理存活对象的碎片，将空闲内存定期合并，就能利用线性分配器的效率提升内存分配器的性能
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
#### 空闲链表分配方式
|
|||
|
|
|
|||
|
|
- 空闲链表分配器（Free-List Allocator）可以重用已经被释放的内存，它在内部会维护一个类似链表的数据结构。当用户程序申请内存时，空闲链表分配器会依次遍历空闲的内存块，找到足够大的内存，然后申请新的资源并修改链表：
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
- 不同的内存块通过指针构成了链表，使用这种方式的分配器可以重新利用回收的资源，分配内存时需要遍历链表，所以它的时间复杂度是 𝑂(𝑛)。空闲链表分配器可以选择不同的策略在链表中的内存块中进行选择，最常见的是以下四种：
|
|||
|
|
|
|||
|
|
- 首次适应（First-Fit）— 从链表头开始遍历，选择第一个大小大于申请内存的内存块；
|
|||
|
|
|
|||
|
|
- 循环首次适应（Next-Fit）— 从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块；
|
|||
|
|
|
|||
|
|
- 最优适应（Best-Fit）— 从链表头遍历整个链表，选择最合适的内存块；
|
|||
|
|
|
|||
|
|
- 隔离适应（Segregated-Fit）— 将内存分割成多个链表，每个链表中的内存块大小相同，申请内存时先找到满足条件的链表，再从链表中选择合适的内存块；隔离适应策略如下
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
- 隔离适应策略会将内存分割成由 4、8、16、32 字节的内存块组成的链表，当我们向内存分配器申请 8 字节的内存时，它会在上图中找到满足条件的空闲内存块并返回。隔离适应的分配策略减少了需要遍历的内存块数量，提高了内存分配的效率。
|
|||
|
|
|
|||
|
|
### 分级分配
|
|||
|
|
|
|||
|
|
- Go 语言的内存分配器就借鉴了 TCMalloc 的设计实现高速的内存分配，它的核心理念是使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略
|
|||
|
|
|
|||
|
|
##### 对象大小
|
|||
|
|
|
|||
|
|
- Go 语言的内存分配器会根据申请分配的内存大小选择不同的处理逻辑，运行时根据对象的大小将对象分成微对象、小对象和大对象三种：
|
|||
|
|
|
|||
|
|
| 类别 | 大小 |
|
|||
|
|
| :----: | :-----------: |
|
|||
|
|
| 微对象 | `(0, 16B)` |
|
|||
|
|
| 小对象 | `[16B, 32KB]` |
|
|||
|
|
| 大对象 | `(32KB, +∞)` |
|
|||
|
|
|
|||
|
|
##### 多级缓存
|
|||
|
|
|
|||
|
|
- 内存分配器不仅会区别对待大小不同的对象，还会将内存分成不同的级别分别管理，TCMalloc 和 Go 运行时分配器都会引入线程缓存（Thread Cache）、中心缓存（Central Cache）和页堆（Page Heap）三个组件分级管理内存：
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
#### 虚拟内存布局
|
|||
|
|
|
|||
|
|
##### Go 1.10及以前连续分配
|
|||
|
|
|
|||
|
|
- 启动时会初始化整片虚拟内存区域，如下所示的三个区域 `spans`、`bitmap` 和 `arena` 分别预留了 512MB、16GB 以及 512GB 的内存空间，这些内存并不是真正存在的物理内存，而是虚拟内存：
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
- `spans` 区域存储了指向内存管理单元 [`runtime.mspan`](https://draveness.me/golang/tree/runtime.mspan) 的指针，每个内存单元会管理几页的内存空间，每页大小为 8KB；
|
|||
|
|
- `bitmap` 用于标识 `arena` 区域中的那些地址保存了对象，位图中的每个字节都会表示堆区中的 32 字节是否空闲；
|
|||
|
|
- `arena` 区域是真正的堆区，运行时会将 8KB 看做一页，这些内存页中存储了所有在堆上初始化的对象；
|
|||
|
|
|
|||
|
|
- 对于任意一个地址，都可以根据 `arena` 的基地址计算该地址所在的页数并通过 `spans` 数组获得管理该片内存的管理单元 [`runtime.mspan`](https://draveness.me/golang/tree/runtime.mspan)，`spans` 数组中多个连续的位置可能对应同一个 [`runtime.mspan`](https://draveness.me/golang/tree/runtime.mspan) 结构。
|
|||
|
|
|
|||
|
|
##### Go 1.11以后稀疏分配
|
|||
|
|
|
|||
|
|
- 稀疏的内存布局能移除堆大小的上限
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
### 地址空间
|
|||
|
|
|
|||
|
|
- Go 语言的运行时构建了操作系统的内存管理抽象层，该抽象层将运行时管理的地址空间分成以下四种状态[8](https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-memory-allocator/#fn:8)：
|
|||
|
|
|
|||
|
|
| 状态 | 解释 |
|
|||
|
|
| :--------: | :----------------------------------------------------------: |
|
|||
|
|
| `None` | 内存没有被保留或者映射，是地址空间的默认状态 |
|
|||
|
|
| `Reserved` | 运行时持有该地址空间，但是访问该内存会导致错误 |
|
|||
|
|
| `Prepared` | 内存被保留，一般没有对应的物理内存访问，该片内存的行为是未定义的可以快速转换到 `Ready` 状态 |
|
|||
|
|
| `Ready` | 可以被安全访问 |
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
运行时中包含多个操作系统实现的状态转换方法，所有的实现都包含在以 `mem_` 开头的文件中，本节将介绍 Linux 操作系统对上图中方法的实现：
|
|||
|
|
|
|||
|
|
- [`runtime.sysAlloc`](https://draveness.me/golang/tree/runtime.sysAlloc) 会从操作系统中获取一大块可用的内存空间，可能为几百 KB 或者几 MB；
|
|||
|
|
- [`runtime.sysFree`](https://draveness.me/golang/tree/runtime.sysFree) 会在程序发生内存不足（Out-of Memory，OOM）时调用并无条件地返回内存；
|
|||
|
|
- [`runtime.sysReserve`](https://draveness.me/golang/tree/runtime.sysReserve) 会保留操作系统中的一片内存区域，访问这片内存会触发异常；
|
|||
|
|
- [`runtime.sysMap`](https://draveness.me/golang/tree/runtime.sysMap) 保证内存区域可以快速转换至就绪状态；
|
|||
|
|
- [`runtime.sysUsed`](https://draveness.me/golang/tree/runtime.sysUsed) 通知操作系统应用程序需要使用该内存区域，保证内存区域可以安全访问；
|
|||
|
|
- [`runtime.sysUnused`](https://draveness.me/golang/tree/runtime.sysUnused) 通知操作系统虚拟内存对应的物理内存已经不再需要，可以重用物理内存；
|
|||
|
|
- [`runtime.sysFault`](https://draveness.me/golang/tree/runtime.sysFault) 将内存区域转换成保留状态，主要用于运行时的调试；
|
|||
|
|
|
|||
|
|
运行时使用 Linux 提供的 `mmap`、`munmap` 和 `madvise` 等系统调用实现了操作系统的内存管理抽象层，抹平了不同操作系统的差异，为运行时提供了更加方便的接口，除了 Linux 之外，运行时还实现了 BSD、Darwin、Plan9 以及 Windows 等平台上抽象层
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
## 内存管理组件
|
|||
|
|
|
|||
|
|
- 内存管理单元 runtime.mspan
|
|||
|
|
- 线程缓存 runtime.mcache
|
|||
|
|
- 中心缓存 runtime.mcentral
|
|||
|
|
- 页堆 runtime.mheap
|
|||
|
|
|
|||
|
|
### Go内存布局
|
|||
|
|
|
|||
|
|
|
|||
|
|
|
|||
|
|
- 每一个处理器都会分配一个线程缓存 [`runtime.mcache`](https://draveness.me/golang/tree/runtime.mcache) 用于处理微对象和小对象的分配，它们会持有内存管理单元 [`runtime.mspan`](https://draveness.me/golang/tree/runtime.mspan)
|
|||
|
|
|
|||
|
|
- 每个类型的内存管理单元都会管理特定大小的对象，当内存管理单元中不存在空闲对象时，它们会从 [`runtime.mheap`](https://draveness.me/golang/tree/runtime.mheap) 持有的 134 个中心缓存 [`runtime.mcentral`](https://draveness.me/golang/tree/runtime.mcentral) 中获取新的内存单元，中心缓存属于全局的堆结构体 [`runtime.mheap`](https://draveness.me/golang/tree/runtime.mheap)，它会从操作系统中申请内存
|
|||
|
|
- 在 amd64 的 Linux 操作系统上，[`runtime.mheap`](https://draveness.me/golang/tree/runtime.mheap) 会持有 4,194,304 [`runtime.heapArena`](https://draveness.me/golang/tree/runtime.heapArena)，每个 [`runtime.heapArena`](https://draveness.me/golang/tree/runtime.heapArena) 都会管理 64MB 的内存，单个 Go 语言程序的内存上限也就是 256TB。
|