go 内存分配管理

span与元素
Go语言将内存分成了大大小小67个级别的span，其中，0级代表特殊的大对象，其大小是不固定的。当具体的对象需要分配内存时，并不是直接分配span，而是分配不同级别的span中的元素。因此span的级别不是以每个span的大小为依据的，而是以span中元素的大小为依据的。各级span与其元素大小见表18-1。
表18-1 各级span与其元素大小

如表18-1所示，第1级span中元素的大小为8字节，span的大小为8192字节，因此第1级span拥有的元素个数为8192/8=1024。每个span的大小和span中元素的个数都不是固定的，例如第65级span的大小为57344字节，每个元素的大小为28672字节，元素个数为2。span的大小虽然不固定，但其是8KB或更大的连续内存区域。
每个具体的对象在分配时都需要对齐到指定的大小，例如分配17字节的对象，会对应分配到比17字节大并最接近它的元素级别，即第3级，这导致最终分配了32字节。因此，这种分配方式会不可避免地带来内存的浪费。

Go语言内存分配的基本单元是mspan，每一个mspan维护着若干个页内存，当Go程序申请内存时，底层实际上是从mspan中查找分配的。结构体mspan的定义如下所示：

结构体mspan的字段含义如下。
1)npages：表示该mspan管理了多少页内存，Go语言定义的页大小为8KB。
2)allocBits：该字段用于维护当前mspan所有内存的分配状态，Go语言使用一个比特记录每一个8字节内存的分配状态，0表示空闲状态，1表示已分配状态。
3)elemsize：为了提升空闲内存的查找效率，Go语言将mspan分为了多种类型，每一种类型的mspan仅用于分配固定大小的内存块，该字段表示当前mspan负责分配的内存块大小。
Go语言总共定义了67种类型的mspan，如下所示：

参考上面的定义，每一列的含义如下。
第1列class表示类型序号。
第2列bytes/obj表示mspan负责分配的内存块大小，单位为字节。可以看到，mspan可分配的内存块最大为32768字节（第67种类型）。
第3列bytes/span表示mspan管理的内存大小，单位为字节。注意，mspan管理的内存是以页为单位申请的，页大小为8KB。
第4列objects表示mspan最多能分割为多少个内存块。这一列是通过第三列除以第二列计算得到的（mspan管理的内存大小除以该mspan负责分配的内存块大小）。以第3种类型的mspan为例，8192/24=341，也就是说该类型的mspan能分割为341个内存块。
第5列tail waste意为尾部浪费。因为第三列除以第二列可能不能整除，也就是说会有余数。以第3种类型的mspan为例，8192 / 24=341，余数为8，而这8字节内存是无法分配的，也就是被浪费掉了。
第6列max waste表示内存最大浪费比例。思考一下，每一种类型的mspan仅用于分配固定大小的内存块，假设Go程序申请1字节的内存，Go语言分配器也会选择第1种类型的mspan，而该类型的mspan负责分配的内存块大小固定为8字节，即有7字节的内存被浪费了，浪费率比例等于7/8=0.785=87.5%。
第7列min align表示该类型的mspan分配的内存必须满足一定的内存对齐条件，比如第1种类型的mspan分配的内存都必须8字节对齐。
通过上面的介绍，我们基本上也能推测到Go语言内存分配的主要逻辑。
1)根据程序申请的内存大小，计算应该使用哪一种类型的mspan。
2)获取对应类型的mspan，从比特位allocBits中查找满足条件的连续0比特位。
3)根据第0位的索引位置（可以计算出对应内存在mspan的偏移量），以及mspan的首地址，计算返回的内存首地址。
Go语言申请内存的入口函数是runtime.mallocgc，也就是该函数实现了内存分配器的主要逻辑，代码如下所示：

在上面的代码中可以看到，函数runtime.mallocgc的核心逻辑与我们的猜测一致。当然，这里我们只摘抄了部分核心代码，还有部分逻辑被省略了。比如，mspan可分配的内存块最大为32768字节，那么当Go程序申请的内存大于32768字节时该怎么办？这时候其实是直接申请整个mspan返回给程序。比如，如果当前mspan没有满足条件的连续0比特位该怎么办？总不能返回申请内存失败吧？当然不会，Go语言会申请新的mspan，申请成功之后再从新的mspan查找满足条件的连续为0的位，并返回对应的内存首地址。

Go语言内存管理

Go语言内存管理还是比较复杂的，以申请内存为例，整个流程涉及多个对象，并且这些对象相互依赖，如图5-3所示。

图5-3 Go语言内存管理示意图
参考图5-3，虚线中的对象由逻辑处理器P单独维护（避免加锁），实线框中的对象由Go进程全局维护。可以看到，每个逻辑处理器P都有一个mcache对象，该对象缓存有可用的mspan，这样Go程序申请内存时只需要从逻辑处理器P缓存的mspan查找即可，而这一操作是不需要加锁的。mcache的定义如下所示：

参考上面的定义，alloc是一个数组，数组长度为136，用于存储所有类型的mspan。但在5.1.2小节中明明介绍的是Go语言总共定义了67种类型的mspan，为什么这里只存储了136种类型的mspan呢？因为Go语言将每一种类型的mspan又拆分为两种，分别存储包含指针的对象以及不包含指针的对象。为什么这么做呢？其实是为了提升垃圾回收效率，因为垃圾回收需要扫描所有包含指针的内存，如果不拆分就需要扫描所有mspan，但是拆分之后，一部分mspan就完全不需要扫描了。这样的话，总共应该有67×2=134种类型的mspan，那还有两种类型呢？这两种类型的mspan用于分配大块内存（大于32768字节）。同样，分别存储包含指针的对象以及不包含指针的对象。
那如果当前逻辑处理器P缓存的mspan已经没有可分配内存了，这时程序申请内存该怎么办？参考图5-3，Go语言会从全局的mcentral查找可用的mspan。mcentral的定义如下所示：

在上面的代码中，mheap是一个全局变量，mheap.central是一个全局对象，用于存储136种类型的mspan。需要注意的是，mcentral存储的mspan根据有无空闲内存分为了两种：partial存储的mspan有空闲内存，full存储的mspan没有空闲内存。但是partial/full存储的mspan还有可能已经被垃圾回收过程标记完成而实际并没有清理，即清理之后可能会多出额外的空闲内存。
参考结构体mcentral的定义，基本上也能猜测出从全局的mcentral分配mspan的主要流程了。
1)由于多个协程可能会并发地访问全局mcentral，所以第一步肯定是需要加锁的。
2)从partial查找已被清理的mspan，如果有，返回该mspan。
3)从partial查找未被清理的mspan，如果有，则执行垃圾回收清理逻辑，清理之后返回该mspan。
4)从full查找未被清理的mspan，如果有，则执行垃圾回收清理逻辑，清理之后如果有空闲内存则返回该mspan。
最后，从mcentral查找mspan是有次数限制的，默认查找100次之后如果还没有可用的mspan，则从对象pageCache中申请新的mspan。与mcache类似，每一个逻辑处理器P还有一个pageCache对象（页缓存），该对象缓存了64个空闲页，也就是说可以向该对象申请新的mspan，并且这一操作是不需要加锁的。那如果逻辑处理器P的页缓存pageCache也没有足够的空闲页呢？那就通过页分配器pageAlloc分配页缓存，如果页分配器pageAlloc页也没有足够的内存，则最终通过线性分配器linearAlloc向操作申请64MB内存，这一整块内存也被称为heapArena。

三级对象管理

为了能够方便的对span进行管理，加速span对象的访问和分配，Go语言采取了三级管理结构，分别为mcache、mcentral、mheap。
Go语言采用了现代TCMalloc内存分配算法的思想，每个逻辑处理器P都存储了一个本地span缓存，称作mcache。如果协程需要内存可以直接从mcache中获取，由于在同一时间只有一个协程运行在逻辑处理器P上，所以中间不需要加锁。mcache包含所有大小规格的mspan，但是每种规格大小只包含一个。除class0外，mcache的span都来自mcentral。
◎ mcentral是被所有逻辑处理器P共享的。
◎ mcentral对象收集所有给定规格大小的span。每个mcentral都包含两个mspan的链表：empty mspanList表示没有空闲对象或span已经被mcache缓存的span链表，nonempty mspanList表示有空闲对象的span链表。
做这种区分是为了更快地分配span到mcache中。图18-1为三级内存对象管理的示意图。除了级别0，每个级别的span都会有一个mcentral用于管理span链表。而所有级别的这些mcentral，其实都是一个数组，由mheap进行管理。

图18-1 三级内存对象管理
mheap的作用不只是管理central，大对象也会直接通过mheap进行分配。如图18-2所示，mheap实现了对虚拟内存线性地址空间的精准管理，建立了span与具体线性地址空间的联系，保存了分配的位图信息，是管理内存的最核心单元。后面还会看到，堆区的内存被分成了HeapArea大小进行管理。对Heap进行的操作必须全局加锁，而mcache、mcentral可以被看作某种形式的缓存。

图18-2 mheap管理虚拟内存线性地址空间
18.1.3 四级内存块管理
根据对象的大小，Go语言将堆内存分成了图18-3所示的HeapArea、chunk、span与page 4种内存块进行管理。其中，HeapArea内存块最大，其大小与平台相关，在UNIX 64位操作系统中占据64MB。chunk占据了512KB，span根据级别大小的不同而不同，但必须是page的倍数。而1个page占据8KB。不同的内存块用于不同的场景，便于高效地对内存进行管理。

图18-3 内存块管理结构

对象分配

正如前面介绍的，不同大小的对象会被分配到不同的span中，在这一小节中，将看到其分配细节。在运行时分配对象的逻辑主要位于mallocgc函数中，这个名字很有意思，malloc代表分配，gc代表垃圾回收（GC），此函数除了分配内存还会为垃圾回收做一些位图标记工作。本节主要关注内存的分配。

内存分配时，将对象按照大小不同划分为微小（tiny）对象、小对象、大对象。微小对象的分配流程最长，逻辑链路最复杂。我们在介绍微小对象的分配时，其实已经包含了小对象、大对象的类似分配流程，因此，下一节将重点介绍微小对象，并对比介绍几种对象在内存分配上的不同。
18.2.1 微小对象
Go语言将小于16字节的对象划分为微小对象。划分微小对象的主要目的是处理极小的字符串和独立的转义变量。对json的基准测试表明，使用微小对象减少了12%的分配次数和20%的堆大小[1]。
微小对象会被放入class为2的span中，我们已经知道，在class为2的span中元素的大小为16字节。首先对微小对象按照2、4、8的规则进行字节对齐。例如，字节为1的元素会被分配2字节，字节为7的元素会被分配8字节。

查看之前分配的元素中是否有空余的空间，图18-4所示为微小对象分配示意图。如果当前对象要分配8字节，并且正在分配的元素可以容纳8字节，则返回tiny+offset的地址，意味着当前地址往后8字节都是可以被分配的。

图18-4 微小对象分配
如图18-5所示，分配完成后offset的位置也需要相应增加，为下一次分配做准备。

图18-5 tiny offset代表当前已分配内存的偏移量
如果当前要分配的元素空间不够，将尝试从mcache中查找span中下一个可用的元素。因此，tiny分配的第一步是尝试利用分配过的前一个元素的空间，达到节约内存的目的。

18.2.2 mcache缓存位图
在查找空闲元素空间时，首先需要从mcache中找到对应级别的mspan，mspan中拥有allocCache字段，其作为一个位图，用于标记span中的元素是否被分配。由于allocCache元素为uint64，因此其最多一次缓存64字节。

allocCache使用图18-6中的小端模式标记span中的元素是否被分配。allocCache中的最后1 bit对应的是span中的第1个元素是否被分配。当bit位为1时代表当前对应的span中的元素已经被分配。

图18-6 allocCache位图标记span中的元素是否被分配
有时候，span中元素的个数大于64，因此需要专门有一个字段freeindex标识当前span中的元素被分配到了哪里。如图18-7所示，span中小于freeindex序号的元素都已经被分配了，将从freeindex开始继续分配。

图18-7 freeindex之前的元素都已被分配
因此，只要从allocCache开始找到哪一位为0即可。假如X位为0，那么X+freeindex为当前span中可用的元素序号。当allocCache中的bit位全部被标记为1后，需要移动freeindex，并更新allocCache，一直到span中元素的末尾为止。
18.2.3 mcentral遍历span

如果当前的span中没有可以使用的元素，这时就需要从mcentral中加锁查找。之前介绍过，mcentral中有两种类型的span链表，分别是有空闲元素的nonempty链表和没有空闲元素的empty链表。在mcentral查找时，会分别遍历这两个链表，查找是否有可用的span。
有些读者可能有疑问，既然是没有空闲元素的empty链表，为什么还需要遍历呢？这是由于可能有些span虽然被垃圾回收器标记为空闲了，但是还没有来得及清理，这些span在清扫后仍然是可以使用的，因此需要遍历。

图18-8为查找mcentral中可用span并分配到mcache中的示意图。如果在mcentral中查找到有空闲元素的span，则将其赋值到mcache中，并更新allocCache，同时需要将span添加到mcentral的empty链表中去。

图18-8 查找mcentral中的可用span并分配到mcache中
18.2.4 mheap缓存查找
如果在mcentral中找不到可以使用的span，就需要在mheap中查找。Go 1.12采用treap结构进行内存管理，treap是一种引入了随机数的二叉搜索树，其实现简单，引入的随机数及必要时的旋转保证了比较好的平衡性。Michael Knyszek提出，这种方式有扩展性的问题[2]，由于这棵树是mheap管理的，所以在操作它时需要维持一个lock。这在密集的对象分配及逻辑处理器P过多时，会导致更长的等待时间。Michael Knyszek提出用bitmap来管理内存页，因此在Go 1.14之后，我们会看到每个逻辑处理器P中都维护了一份page cache，这就是现在Go语言实现的方式。

mheap会首先查找每个逻辑处理器P中pageCache字段的cache。如图18-9所示，cache也是一个位图，每一位都代表了一个page（8 KB）。由于cache为uint64，因此一共可以提供64×8=512KB的连续虚拟内存。在cache中，1代表未分配的内存，0代表已分配的内存。base代表该虚拟内存的基地址。当需要分配的内存小于512/4=128KB时，需要首先从cache中分配。

图18-9 cache位图标记内存缓存页是否分配
例如要分配n pages，就需要查找cache中是否有连续n个为1的位。如果存在，则说明在缓存中查找到了合适的内存，用于构建span。

18.2.5 mheap基数树查找
如果要分配的page过大或者在逻辑处理器P的cache中没有找到可用的page，就需要对mheap加锁，并在整个mheap管理的虚拟地址空间的位图中查找是否有可用的page，这涉及Go语言对线性地址空间的位图管理。
管理线性地址空间的位图结构叫作基数树（radix tree），其结构如图18-10所示。该结构和一般的基数树结构不太一样，会有这个名字很大一部分是由于父节点包含了子节点的若干信息。

图18-10 内存管理基数树结构
该树中的每个节点都对应一个pallocSum，最底层的叶子节点对应的pallocSum包含一个chunk的信息（512×8KB），除叶子节点外的节点都包含连续8个子节点的内存信息。例如，倒数第2层的节点包含连续8个叶子节点（即8×chunk）的内存信息。因此，越上层的节点对应的内存越多。


pallocSum是一个简单的uint64，分为开头（start）、中间（max）、末尾（end）3部分，其结构如图18-11所示。pallocSum的开头与末尾部分各占21bit，中间部分占22bit，它们分别包含了这个区域中连续空闲内存页的信息，包括开头有多少连续内存页，最多有多少连续内存页，末尾有多少连续内存页。对于最顶层的节点，由于其max位为22bit，因此一棵完整的基数树最多代表221 pages=16GB内存。

图18-11 pallocSum的内部结构
不需要每一次查找都从根节点开始。在Go语言中，存储了一个特别的字段searchAddr，顾名思义是用于搜索可用内存的。如图18-12所示，利用searchAddr可以加速内存查找。searchAddr有一个重要的设定是它前面的地址一定是已经分配过的，因此在查找时，只需要向searchAddr地址的后方查找即可跳过已经查找的节点，减少查找的时间。

图18-12 利用searchAddr加速内存查找
在第1次查找时，会从当前searchAddr的chunk块中查找是否有对应大小的连续空间，这种优化主要针对比较小的内存（至少小于512KB）分配。Go语言对于内存有非常精细的管理，chunk块的每个page（8 KB）都有位图表明其是否已经被分配。
每个chunk都有一个pallocData结构，其中pallocBits管理其分配的位图。pallocBits是uint64，有8字节，由于其每一位对应一个page，因此pallocBits一共对应64×8=512KB，恰好是一个chunk块的大小。位图的对应方式和之前是一样的。

而所有的chunk pallocData都在pageAlloc结构中进行管理。

当内存分配过大或者当前chunk块没有连续的npages空间时，需要到基数树中从上到下进行查找。基数树有一个特性——要分配的内存越大，它能够越快地查找到当前的基数树中是否有连续的满足需求的空间。
在查找基数树的过程中，需要从上到下、从左到右地查找每个节点是否符合要求。先计算pallocSum的开头有多少连续的内存空间，如果大于或等于npages，则说明找到了可用的空间和地址。如果小于npages，则会计算pallocSum字段的max，即中间有多少连续的内存空间。如果max大于或等于npages，那么需要继续向基数树当前节点对应的下一级查找，原因在于，max大于npages，表明当前一定有连续的空间大于或等于npages，但是并不知道具体在哪一个位置，必须查找下一级才能找到可用的地址。如果max也不满足，那么是不是就不满足了呢？不一定，如图18-13所示，有可能两个节点可以合并起来组成一个更大的连续空间。因此还需要将当前pallocSum计算的end与后一个节点的start加起来查看是否能够组合成大于npages的连续空间。

图18-13 更大的可用内存可能跨越了多个pallocSum
每一次从基数树中查找到内存，或者事后从操作系统分配到内存时，都需要更新基数树中每个节点的pallocSum。
18.2.6 操作系统内存申请
当在基数树中查找不到可用的连续内存时，需要从操作系统中获取内存。从操作系统获取内存的代码是平台独立的，例如在UNIX操作系统中，最终使用了mmap系统调用向操作系统申请内存。

Go语言规定，每一次向操作系统申请的内存大小必须为heapArena的倍数。heapArena是和平台有关的内存大小，在64位UNIX操作系统中，其大小为64MB。这意味着即便需要的内存很小，最终也至少要向操作系统申请64MB内存。多申请的内存可以用于下次分配。
Go语言中对于heapArena有精准的管理，精准到每个指针大小的内存信息，每个page对应的mspan信息都有记录。

18.2.7 小对象分配
当对象不属于微小对象时，在内存分配时会继续判断其是否为小对象，小对象指小于32KB的对象。Go语言会计算小对象对应哪一个等级的span，并在指定等级的span中查找。
此后和微小对象的分配一样，小对象分配经历mcache→mcentral→mheap位图查找→mheap基数树查找→操作系统分配的过程。
18.2.8 大对象分配
大对象指大于32KB的对象，内存分配时不与mcache和mcentral沟通，直接通过mheap进行分配。大对象分配经历mheap基数树查找→操作系统分配的过程。每个大对象都是一个特殊的span，其class为0。