了解 Go 内存分配

在工作中遇到线上服务内存问题时，通过pprof火焰图经常能看到一些运行时的函数，了解运行时的东西对分析线上服务出现的问题很有帮助。这篇文章主要了解Go的内存分配。

主要按照 https://www.youtube.com/watch?v=3CR4UNMK_Is 这个演讲的思路来梳理Go的内存分配。

一些基础的概念

虚拟内存

进程不直接读物理内存主要有以下优点：
- 内存安全，通过虚拟内存的方式能够避免一个进程去修改另外一个进程的内存或者内核的内存。
- 充分利用CPU，虚拟内存机制可以使进程只有一部分内存空间真正映射到物理内存，这样就可以有更多的进程能够常驻内存，CPU就有更多可运行的进程。
虚拟内存的实现：
- 分段
- 分页

进程内存空间布局

Text：存放二进制代码。
Data：存放已初始化的静态变量。
BSS：存放未初始化的静态变量。
Heap：动态分配的内存变量。
Stack：函数栈帧。

栈内存分配

栈内存分配比较简单，因为栈上分配的对象都是给定长度的，所以可以知道一次要分配的内存大小，分配时将SP向下移动size个单位，返回SP-size的地址，回收时SP向上移动size个单位就完成了回收。所以栈内存分配速度是很快的。

堆内存分配

既然栈内存分配简单高效，那为什么还要有堆内存分配呢？由于有一些对象只有在运行时才知道对象的大小，比如用户的输入，此时就无法使用栈内存分配了，只能在代码运行时手动分配，这些在运行时才知道大小的对象都分配在堆上。C提供malloc和free来分配释放堆内存，C++提供new和delete，Go使用逃逸分析和垃圾回收来分配释放堆内存。

实现一个玩具内存分配器

需要实现两个函数：

1
2


void* malloc(size_t size)
void free(void *ptr)

使用mmap/munmap系统调用向操作系统申请释放内存。

最简单的思路就是维护一个空闲内存的链表，链表中的每个节点分为两部分：头部保存当前节点的内存大小，指向的下一个节点的地址，后面就是真正的可用内存区，大小为头部保存的大小。

分配过程：

声明一个头结点指向NULL。
使用mmap向操作系统申请一块内存，将起始地址赋值给head指针，在分配了的内存的header部分写入其大小，假设申请的大小是4096 Bytes，去掉头部的大小，假设是12，则写入的size为4084 Bytes。
调用malloc(10)时，会从链表的末尾开始（通过起始地址+size的方式找到末尾的地址），分配sizeof(header) + 10的内存组成一个新的节点连在链表的结尾。
返回地址为新节点的起始地址+sizeof(header)。

释放过程：

首先让p回到分配的起始地址位置，分配的起始地址为p-sizeof(header) ，然后p-sizeof(header)->next指向head->next。
header指针指向p-sizeof(header)。
整个过程是一个向链表头部插入节点的过程。

这个分配器存在的问题：

容易产生内存碎片，假如之后要分配的大小都大于 10 那么长度为 10 的这块就永远无法利用。
没有处理对同一个指针调用两次free的情况，可能会引发内存越界。
没有归还给操作系统的处理，free只是重新放进链表中。
- 什么时候归还？
- 怎么归还？munmap, madvise…
没有处理多线程分配情况。

Go 运行时内存分配器

TCMalloc

每个线程有本地缓存。
两种分配方式：
- Small allocations (<= 32 kB)。
- Large allocations。
内存管理的单元为Spans。
- spans是一段连续的内存页。
- 元数据 (header) 与分配的内存分开。

Large Allocations 大对象分配

由central heap分配。
申请分配的内存大小按页大小向上取整。
程序申请大对象时首先向central heap申请，由于central heap是多线程访问的，所以分配时需要加全局锁。假设要申请的内存按页大小取整后需要k个page, 那么会找到不小于k page的最小span，将整个span拆分为两个span，一个span大小为k page，作为结果返回，另一个span大小n - k page，将剩下的这个span插入到其对应的小的span链表中。如果找不到合适的span，那么central heap会向操作系统申请内存然后生成新的span。

Small Allocations 小对象分配

由local thread cache（线程本地缓存）分配
申请分配的内存大小按class大小向上取整，class分为多级，每级的大小不一样，每次分配都会找到不小于分配大小的最小class，按这个class的大小向上取整。
如果本地缓存中有合适大小的内存，直接从本地缓存分配，因为是线程本地缓存，访问时不需要加锁，分配速度非常快。
如果本地缓存中没有合适大小的内存，本地缓存会向central free list 中申请，central free list 维护了相应class的对象。central free list 和 central heap一样是多线程访问的需要加锁。central free list 相对于central heap而言提供了更多不同大小的内存块，能够使申请的内存和class size的大小更好地匹配，central free list 按class size object分配，而central heap 按span分配，这样做有利于减少内部碎片。

TCMalloc 内存释放

TCMalloc维护了一个内存页和span之间的映射。
如果调用free(object)，那么首先通过object地址找到它是属于哪一页，然后通过内存页与span之间的映射关系找到这个object属于哪个span，span中有一些元信息记录了这个object的大小。
如果这个对象是一个小对象，那么直接将它放到相应class size的本地缓存链表中。
如果这个对象是一个大对象，首先会看一下相邻的page是否是空闲的，如果相邻的page是空闲的还要将这些page一起合并成一个span，然后将这个新的span放到central heap对应的链表中。
此时的释放只是将其放到空闲链表中进行内存复用，并没有归还给操作系统。

Go 内存分配器

基于TCMalloc设计
垃圾回收
- 与垃圾回收耦合在一起
- 无法像C/C++一样用其他内存分配实现替换
三种分配类型
- Tiny Allocations (size < 16 bytes, no pointers)
- Small Allocations (size <= 32 kbytes)
- Large Allocations

GC

Go的GC使用并发标记清扫算法。从根对象出发，标记所有可达节点，如果节点不可达，说明可以回收了，两种情况触发回收，一种是一个独立的线程定时进行清扫，另一种是分配内存时触发清扫。

大对象分配

Go使用mheap对大对象分配。
mheap中的span分为busy和free两种，在分配内存之前，会先对busy spans进行一次清扫，清扫的大小为请求分配内存的大小，如果清扫的过程发现在上一次GC过程中没有被标记的对象，说明对象可以回收，会将其放到free spans list 中。
超过255pages的span转为树结构存储。
分配大对象可能因引发清扫过程中的额外工作而带来大的延迟。

小对象分配

每个P都有一个本地缓存mcache。
每个mcache为每个class size维护一个span。
mcache将对应class size的span上空闲对象的地址作为结果返回。
如果mcache中对象class size的span已经没有空闲的对象了，那么会向mcentral申请。
mcentral为相应class size维护了两种类型的span，完全没有分配对象出去的span，和已经有一些对象分配出去的span。
完全没有分配对象出去的空span会返回给mcache，如果没有空span，mcentral会清扫非空的span。
如果还无法满足分配，mcentral会向mheap申请新的span，然后将新的span返回给mcache。

超小对象分配

超小对象分配主要是为了小于16bytes的小对象，单独的逃逸变量。
每个P会从span获取一段64bytes大小的空间，每一次超小对象的分配都在这里分配，类似于栈内存分配，直接在之前已分配内存后面向后分配。
如果这个64bytes的空间被用完了会向mcache申请一个新的64bytes大小的空间，之前已经用完了的会通过GC进行回收。

归还内存给操作系统

运行时周期性的将内存归还给操作系统。
归还已经清扫了超过5min的spans。
在Linux上，Go1.12版本之前使用madvise(MADV_DONTNEED)系统调用归还，这种是立即生效，内核立即回收内存。
在Linux上，Go1.12版本之后使用madvise(MADV_FREE)系统调用归还，在linux内核版本4.5以后才支持这种归还方式，这种不会立即生效，而是等到内存紧张时内核才回收内存。

Contents