内存管理方案

page、span、元素

Go语言的内存分配算法源自于TCMalloc，是Google开发的内存分配算法库，TCMalloc的内存分配单位叫page，也就是用固定大小的page来执行内存获取、分配、释放等操作。一个page的大小为8KB

go语言的内存管理的基本单位叫span，每个span用于管理特定大小的内存。go语言将内存分成了大大小小67个级别的span，各级span与其元素大小如下所示：每个span的大小都是page的整数倍。

// class  bytes/obj  bytes/span  objects  waste bytes
//     1          8        8192     1024            0
//     2         16        8192      512            0
//     3         32        8192      256            0
//     4         48        8192      170           32
//     5         64        8192      128            0
//    ........
//    64      27264       81920        3          128
//    65      28672       57344        2            0
//    66      32768       32768        1            0
  • span的级别是以span中的元素大小为依据，同一span中的每个元素大小相同；
  • 每个span的大小和span中的元素个数都是不固定的，因此span的大小是不固定的，但都是page的整数倍；
  • 当具体的对象需要分配不同的内存时，并不是直接分配span，而是分配span中的元素；
  • 每个对象在分配时都需要对齐到指定的大小；
  • 0级代表特殊的大对象，其大小是不固定的。

span的数据结构，字段没有展示全面，位置：src/runtime/mheap.go

type mspan struct {
	_    sys.NotInHeap
	next *mspan     // next span in list, or nil if none
	prev *mspan     // previous span in list, or nil if none

	startAddr uintptr // address of first byte of span aka s.base()
	npages    uintptr // number of pages in span

	nelems uintptr // 块个数（多少个块可供分配）

	allocBits  *gcBits  // 分配位图，和allocCache是一致的
	gcmarkBits *gcBits  // 垃圾回收时的标记位图
    
    freeindex uintptr
    allocCache uint64   // 分配位图，每一位代表一个块是否已分配

	allocCount            uint16        // 已分配的块个数
	spanclass             spanClass     // size class and noscan (uint8)

	elemsize              uintptr       // 块大小
}

假如一个class为5的span，从上表可以得出mspan中的一些值如下：

  • npages（管理的页数）：因为这个级别的span的大小为8K，所以只有一个page，为1
  • nelems（span中元素的个数）：128
  • elemsize（span中每个元素的大小）：64

三级对象管理

为了能够方便的对span进行管理，加速span对象的访问和分配，Go语言采取了三级管理结构：mcache、mcentral、mheap。三级内存对象管理示意图：

下面从最底层mache到高层mheap看看每层都负责什么样的工作

mcache

协程直接从mcache获取内存，无需加锁

每个逻辑处理器P都存储了一个本地span缓存，称作mcache，由于同一时间只可能有一个协程运行在逻辑处理器P上，因此无需加锁。mcache包含所有规格大小的mspan。

mcache的结构如下：src/runtime/mcache.go

type mcache struct {
	.....
	alloc [numSpanClasses]*mspan // spans to allocate from, indexed by spanClass
	.....
}

numSpanClasses=134，即class数量的2倍。

alloc数组中每个元素代表了一种class类型的span列表，每种class都有两组列表：

  • noscan，没有指针，不需要GC扫描
  • scan，有指针，需要进行GC扫描

mcache和mspan的关系如下：

mcache初始状态下没有span，在使用过程中会动态从mcentral中获取并缓存。

mcentral

  • 除class0外，mcache的span都来自于mcentral；
  • 某个协程需要内存时从mcentral申请，释放内存时回收进mcentral；
  • mcentral是被所有逻辑处理器共享；
  • mcentral同样包含两个mspan链表：
    1. empty mspanList：没有空闲对象或span已经被mcache缓存的span链表
    2. nonempty mspanList：有空闲对象的span链表

mcentral的结构如下：src/runtime/mcentral.go

type mcentral struct {
    lock      mutex     //互斥锁
    spanclass spanClass // span class ID
    nonempty  mSpanList // non-empty 指还有空闲块的span列表
    empty     mSpanList // 指没有空闲块的span列表

    nmalloc uint64      // 已累计分配的对象个数
}

协程从mcentral获取span的步骤如下：

  1. 加锁
  2. 从nonempty列表获取可用的span，并将其从链表中删除
  3. 将取出的span放入empty链表
  4. 将span返回给协程
  5. 解锁
  6. 协程将该span缓存进cache

mheap

从mcental的结构可见，每个mcentral对象只管理特定class规格的span。事实上每种class都会对应一个mcentral，这个mecntral的集合存放于mheap数据结构中。

  • 管理mcentral，所有级别的mcentral构成一个数组，由mheap管理；
  • 大对象直接通过mheap进行分配；
  • 建立了span与具体线性地址空间的联系，保存了分配的位图信息，是管理内存的最核心单元；
  • 对heap进行操作必须全局加锁，mecache、mcentral可以看作是某种形式的缓存。

mheap的结构如下（只列出来少数字段）：src/runtime/mheap.go

type mheap struct {
    lock      mutex
    spans []*mspan

    central [134]struct {  // 每种class对应的两个mcentral（scan和noscan）
        mcentral mcentral
        pad      [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
    }
}

从数据结构可见，mheap管理着全部的central，即所有的内存。事实上Golang就是通过一个mheap类型的全局变量进行内存管理的。

四级内存块管理

经过以上的分析，go语言使用mheap实现了对虚拟内存线性地址空间的精准管理：

在分块上go语言又将堆内存分成了HeapArena、chunk、span、page，4种内存块进行管理。

  • HeapArena内存块最大，大小与平台相关，在UNIX64位系统种占据64MB；
  • 每个chunk占据512KB；
  • span根据级别大小的不同而不同，但必须是page的倍数；
  • 每个page占8KB；

管理线性地址空间的位图结构叫**基数树(radix tree)**，其结构和一般的基数树结构不太一样，会有这个名字很大一部分是由于父节点包含了子节点的若干信息，该结构如下图所示：

该树中每个节点都对应一个pallocSum，最底层的叶子节点对应的pallocSum包含一个chunk（64*page）的信息，除叶子节点外的节点都包含连续8个子节点的内存信息。例如倒数第2层的节点包含连续8个叶子节点（8*chunk）的内存信息。

pallocSum是一个简单的uint64，包含了这个区域中连续空闲内存页的信息，分为3部分：

  • 开头（start）：占21bit，表示开头有多少个连续内存页
  • 中间（max）：占22bit，表示最多有多少个连续内存页
  • 末尾（end）：占21bit，表示末尾有多少个连续内存页

对于最顶层的节点，由于max位为22bit，因此一颗完整的基数树最大代表2^21^个page为16G内存

另外go语言还存储了一个特别的字段searchAddr，在searchAddr前面的字段一定是已经分配过的。因此在查找时不用从根节点开始。

微小对象分配过程

内存分配时，按照对象大小不同，划分为：微小对象(tiny)，小对象，大对象。微小对象的分配流程最长，逻辑链路最复杂。微小对象的分配流程其实已经包含了小对象、大对象的分配流程。

go语言将小于16字节的对象划分为微小对象，也就是属于class2级别及以下的span中的元素都属于微小对象。

分配时按照2，4，8的规则进行字节对齐。

  • tiny分配首先要查看之前分配的元素中是否有空余空间，
  • 如果当前要分配的元素空间不够，尝试从mcahe中查找span中的下一个可用元素

mcache分配

  • 查找空闲元素空间时，首先从mcache中找到对应级别的mspan；
  • mspan中拥有allocCache字段为uint64，其作为一个位图，用于标记span中的元素是否被分配，因此其最多一次缓存64个元素；
  • allocCache使用小端模式（最后一个bit位表示第一个元素的分配情况）标记span中的元素是否被分配。1表示元素未被分配，0表示元素已被分配；
  • 如果span中的元素大于64，有一个专门的freeindex标识当前span中的元素分配到了哪里；
  • 当allocCache中的bit位都被标记为0，需要移动freeindex并更新allocCache，一直到span中元素的末尾为止。

mcentral分配

  • 如果当前的span中没有可以使用的元素，就从mcentral中加锁查找
  • 分别遍历empty和nonempty这两个链表，查找是否有可用的span。为什么需要遍历没有空闲元素的empty列表？这是因为：有些span虽然被垃圾回收器标记为空闲了，但是还没来得及清理，这些span在清扫后仍然是可以使用的；
  • 如果在mcentral中查找到有空闲元素的span，则将其赋值到mcache中，并更新allocCache，同时将span添加到mcentral链表中的empty链表中。

mheap分配

缓存查找

如果在mcentral中找不到可以使用的span，就需要在mheap中查找，go1.12采用了treap结构进行内存管理，treap是一种引入随机数的二叉搜索树，其实现简单，引入的随机数及必要时的旋转保证了比较好的平衡性。

为了避免加锁，在go1.14之后，每个逻辑处理器P中都维护了一份page cache

mheap会首先查找每个逻辑处理器中的pageCache字段的cache，cache是一个位图，unit64，每一位代表了一个page（8k）。因此一共可以提供64*8k=512KB的连续虚拟内存，在cache中，1代表未分配的内存，0代表已分配的内存

基数树查找

如果要分配的page过大或者在逻辑处理器P的cache中没有找到可用的page，就需要对mheap加锁，并在整个mheap管理的虚拟地址空间的位图中查找是否有可用的page。

基数树的特性是：要分配的内存越大，它能够越快的查找到当前的基数树中是否有满足需求的空间。

操作系统内存申请

在基数树中找不到可用的连续内存时，需要从操作系统中获取内存。从操作系统中获取内存时平台独立的，例如在unix操作系统中，最终使用了mmap系统调用。

每一次向操作系统申请内存，必须为heapArena的倍数，heapArena是和平台有关的内存大小，在64位unix系统中，其大小为64MB。

小对象、大对象分配

小对象：小于32KB的对象，go语言先计算小对象对应于哪一个等级的span，并在指定等级的span中查找。此后和微小对象的分配一样：mcache->mcentral->mheap位图查找->操作系统分配

大对象：大于32KB的对象，内存分配不经过mcache和mcrntral，直接通过mheap进行分配：mheap基数树查找->操作系统分配

说明

本文参考了《Go语言底层原理剖析》《Go专家编程》这两本书，以及部分源码，重新梳理进行的总结。没有看所有的源码对细节进行深究。

随着go版本的升级，有些细节也发生了变化。比如这两本书参考的都是go1.12，span一共有67个class。而在go1.20中，span一共划分了68个class，多了一个对象大小为24byte的class。

但总体的思想应该是一致的。