软件开发架构师

图解 Go 内存分配器

架构 64 2019-03-12 10:59
作者 | Ankur Anand
译者 | 闫亮

内存分配器一直是性能优化的重头戏,其结构复杂、内容抽象,涉及的数据结构繁多,相信很多人都曾被它搞疯了。本文将从内存的基本知识入手,到一般的内存分配器,进而延伸到 Go 内存分配器,对其进行全方位深层次的讲解,希望能让你对进程内存管理有一个全新的认识。

物理内存 VS 虚拟内存

在研究内存分配器之前,让我们先看一下物理内存和虚拟内存的背景知识。剧透一下,内存分配器实际上操作的不是物理内存而是虚拟内存。

内存细胞作为物理内存结构的最小单元,工作原理如下:

  1. 地址线(三相晶体管)其实是连接数据线与数据电容的三相开关。

  2. 当地址线负载时(红线),数据线开始向电容中写数据,电容处于充电状态,逻辑值变为 1

  3. 当地址线空载时(绿线),数据线不能向电容中写数据,电容处于未充电状态,逻辑值为 0

  4. 当 CPU 从 RAM 中读值时,它首先会给地址线发送一个电流信号从而合上开关,连通数据电路。这时如果电容处于高电位,则电容中的电流会流向数据线,CPU 读数为 1;否则,数据线中没有电流负载,CPU 读数为 0。

CPU 和内存的交互

CPU 实际上通过地址总线、数据总线和控制总线实现对内存的访问。

  • 数据总线:在 CPU 和内存之间传递数据的通道;

  • 控制总线:在 CPU 和内存之间传递各种控制 / 状态信号的通道;

  • 地址总线: 传送地址信号,以确定所要访问的内存地址。

让我们进一步分析一下 地址线按字节寻址:

  1. 在 DRAM 中,每一个字节都有一个唯一的地址。“可寻址字节不一定等于地址线的数量”,

    例如 16 位的 Intel 8088、PAE(物理地址扩展)等,其物理字节大于地址线数量。

  2. 每一条地址线可以传送 1-bit 的数值,可表示寻址字节中的一位。

  3. 图中有 32 位地址线,所以可认为可寻址字节是 32 位的。

    [ 00000000000000000000000000000000 ] —低位内存地址。

    [ 11111111111111111111111111111111 ] — 高位内存地址。

  4. 因为上图物理字节有 32 条地址线,所以其寻址空间大小为 2 的 32 次方,也就是 4GB

可寻址字节的大小其实取决于地址线的数量,例如具有 64 个地址线的 CPU(x86–64 处理器)可以寻址 2 的 64 次方,但是目前大多数 64 位的 CPU 其实只使用了其中的 48 位(AMD)或者 42 位(Intel)。尽管理论上可访问 2 的 64 次方(256TB)大小的地址空间,但是通常操作系统并没有完全支持它们(Linux 的 四层页表结构 允许处理器访问 128TB 大小的地址空间,Windows 支持 192TB)。

由于实际物理内存的大小是有限制的,所以每个进程都运行在各自的沙盒中,也就是所谓的“虚拟地址空间”,简称虚拟内存。

虚拟内存中的字节地址其实并不是实际的物理地址。操作系统需要记录所有虚拟地址到物理地址的映射转换,也就是我们熟知的页表。

进程中的虚拟地址如下图所示:

       

虚拟地址空间示意图

所以当 CPU 执行内存中一条指令的时候,它首先需要把 VMA(虚拟内存区域)中的逻辑地址转换为线性地址,转化过程通过 MMU(内存管理单元)实现。

                                 

虚拟地址与实际物理地址的映射

由于逻辑地址太大很难被有效地管理,于是引入了页(page)的概念。所有的虚拟内存空间被分成很多相对较小的区域(通常为 4KB),也就是我们所称的页。页是虚拟内存管理中最小的单位,虚拟内存通常不存储任何内容,只是简单的将程序地址空间映射到底层的物理地址。

用户进程只能使用虚拟内存地址。让我们来看一下程序如何申请堆内存空间:

                       

(堆内存申请的汇编实现)


程序通常使用系统调用 brk(sbrk/mmap) 来获取更多的内存,内核仅更新堆的 VMA,并没有进行进行实际的申请操作。

系统在内存分配的时候,其实并没有申请相应的物理页帧,只有在真正赋值的时候才会申请物理页帧。这也是 VSZ(进程虚拟内存大小)和 RSS(常驻物理内存大小)的最大区别。

内存分配器

相信通过前面对“虚拟地址空间”以及堆内存申请的学习,相信我们对内存分配器说也就不难理解了。

如果堆中有足够多的内存空间,那么分配器就可以独立完成内存的申请而不需要访问内核。否则,系统将会通过系统调用函数 brk 来扩展堆,通常是增加变量 MMAP_THRESHOLD 的默认值 (128KB)。

当然内存分配器的职责不仅仅是更新 brk 地址,更多的还是用于减少碎片以及快速分配内存块。让我们来看一个实例:假设我们的程序通过函数 malloc 来申请一块连续内存块,使用函数 free 来释放申请的内存块,步骤 p1 到 p4 的整个操作顺序如下:

到步骤 p4 的时候,尽管剩余的内存块数量大于需要申请的数量,但是因为碎片的关系,我们已经不能获得 6 个连续的内存块了。我们该如何减少内存碎片呢?答案要取决于具体使用的分配算法。

由于 Go 内存分配器同 TCMalloc 分配器非常相似,我们先看一下相对简单的 TCMalloc。

TCMalloc

TCMalloc(Thread Cache Malloc)的核心思想是将内存分解为多层,从而减小内存锁的粒度。TC-Malloc 内存管理分为 线程内存 以及 页堆 两部分:

线程内存

为减少内存碎片,每个内存页都被分成了多个固定类大小的空闲列表。这样每一个线程都都有一个不带锁的小对象缓存,从而可以高效的为并行程序分配小对象(<=32KB)。

页   堆

TCMalloc 管理的堆其实由一组页构成,而这样一组连续的页又被称为页堆(span)。当我们申请大于 32K 的对象时,TCMalloc 将使用页堆进行分配。

当没有足够的内存来分配小对象时,将使用页堆内存;而如果页堆内存也不不能满足时,将会向操作系统申请更多的内存。这种基于用户空间内存池的管理模式极大地提高了内存分配和释放的效率。

注: 早期的 go 内存分配器是基于 TCMalloc 开发的,但时至今日,两者已经大不相同了。

Go 内存分配器

Go 运行时调度器其实把 Goroutines (G) 绑定到逻辑处理器(P)上执行。同 TCMalloc 一样,Go 内存分配器将内存页分成了 67 个不同类大小的块。

如果你不熟悉 Go 调度器的话,建议先阅读一下文章(Go scheduler: Ms, Ps & Gs)。

Go 中内存的最小粒度为 8KB,如果页被分成大小为 1KB 的块,那么将会有如下 8 个块。

Go 通过数据结构 mspan 来管理这些页。

mspan

简单来讲,mspan 是一个双端链表,包含了页起始地址,span 类以及这个类中页的数量。

mcache

同 TCMalloc 一样,Go 内存分配器为每一个逻辑处理器 (P) 提供了一个本地线程缓存,也就是 mcache。如果 Goroutine 需要内存,可以直接从 mcache 中获取,由于只有一个 Goroutine 运行在逻辑处理器(P)上,所以中间不需要使用任何锁。

mcache 包含了所有类大小的 mspan。

  • 由于 mcache 是基于 CPU 存在的,从 mcache 获取内存时没有必要使用锁机制。

每一种类大小的 mspan 都有两种类型:

  1. scan — 含有指针的对象。

  2. noscan — 没有指针的对象。

这样分类的好处是在垃圾回收的时候,不需要遍历 noscan 对象(noscan 中根本就没有指针)。那什么情况下内存分配器会从 mcache 中申请内存呢?

  • <=32K 字节的对象将直接从 mchae 中相应大小的 mspan 申请。

如果 mcache 没有可用空间的时候会怎么样?将会从 mcentra 中相应大小的 mspanl 列表中分配一个新的 mspan。

mcentral

mcentral 对象收集了所有给定类大小的 span,每一个 mcentral 都包含了两个 mspan 列表:

  1. empty mspanList — 没有空闲对象或者已经被 mcache 缓存的 mspans 列表。

  2. noempty mspanList — 所有空闲对象的 span 列表。

每一个 mcentral 结构体都由 mheap 结构体维护。

mcentral

mheap 是一个全局变量,管理着 Go 中所有的虚拟地址空间。

如上图所示:mheap 保存了一个 mcentral 的数组,而 mcentral 又保存了所有 span。

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

因为我们用 mcentral 保存了所有 span,当 mchache 向 mcentral 申请一个 mspan 的时候,我们需要锁住 mcentral 层,但我们还是可以同时请求其他大小的 mspan。

Padding(对齐填充)确保了 mcentrals 按照 CacheLine 的大小对齐,所以每一个 MCentral.lock 都可以获得自己的的 cache line,避免了伪共享问题。如果 mcentral 为空会发生什么呢?mcentral 会从 mheap 中申请一些页来创建不同大小的 span。

  • free[_MaxMHeapList]mSpanList: 一个 spanList 数组。每一个 spanList 中的 mspan 都包含了 1 ~ 127 个页 (_MaxMHeapList - 1) 。例如,free[3] 是一个包含了 3 个页的 mspan 链表,Free 表示列表为空,未分配,对应 busy list。

  • freelarge mSpanList: 一个 mspan 列表。每一个元素的页数大于 127。通过数据结构 mtreap 来管理,对应 busylarge。

  • 大于 32K 的对象被称为大对象,直接从 mheap 中申请。每次申请大对象都需要事先调用一个全局锁,因此每次只能处理一个 P 申请。

  • 小于 16B,使用 mcache 的 Tiny 分配。

  • 大小介于 16B 和 32k,计算 sizeClass 的大小,然后在 mcache 中申请相应大小的内存块。

  • 大于 32k 的大对象, 直接从 mheap 中分配。

  • 如果 mcache 中找不到相应大小的内存块,则转向 mcentral 申请。

  • 如果 mcentral 中也没有相应大小的内存块,则转向 mheap 申请,使用 BestFit 策略找寻最合适的 mspan;如果申请到的 mspan 太大,则根据用户的需求进行切分,剩余的页构成一个新的 mspan,并放回到 mheap 的空闲列表。

  • 如果 mheap 中没有可用的 span,将会直接向操作系统申请新的内存页(至少 1M)

如果要申请更大的内存块(arena),将会转向操作系统申请。一次申请大批量的内存页会减少访问操作系统的次数。

所有在在堆上申请的内存都来自 arena,让我们接下来看一看 arean:

Go 虚拟内存:Arena

让我们通过一个简单的 Go 程序来看一下内存使用情况:

func main() {
for {}
}

即便是只有三行的小程序也使用了大约 100MB 的虚拟内存,但 RSS(实际物理内存占用大小)仅为 696KB。让我们先看一下两者的区别:

这里有一些大小为 2MB、32MB 和 64MB 的内存区域,这些区域其实就是 arena 内存块。Go 的虚拟内存其实由一系列的 arena 构成,初始堆映射也是一个 arena,如 go 1.11.5采用了 64MB 的 arena 内存块。

当前 Go 内存分配器是按照程序需要逐步增加内存映射的,初始只预留留了一个 arena 的大小(约 64MB)。而早期的 Go 内存分配器会先保留一大段虚拟内存,在 64 位系统上为 512GB(发散问题:如果申请的内存太大,以至于被 mmap 拒绝了怎么办?)这些 arena 就是我们所说的堆。Go 中每一个 arena 都按照 8KB 的粒度进行管理。

Go 同时还有两个其它块:span 和 bitmap。两者都独立于堆内存空间之外,并且保存了所有 arena 的元数据。他们主要在垃圾回收的时候使用,我们暂且不在这里讨论。

结语

我们刚刚讨论的内存分配策略只是众多内存分配器的冰山一角。但其管理核心本质上是一致的:针对不同大小的对象,在不同的 cache 层中,使用不同的内存结构;将从系统中获得的一块连续内存分割成多层次的 cache,以减少锁的使用以提高内存分配效率;申请不同类大小的内存块来减少内存碎片,同时加速内存释放后的垃圾回收。

最后让我们用 GO 内存分配器的结构示意图作为结束:

英文原文

https://blog.learngoprogramming.com/a-visual-guide-to-golang-memory-allocator-from-ground-up-e132258453ed



点个好看少个 bug

文章评论