Go语言内存管理简述

内存管理是非常重要的一个话题。关于编程语言是否应该支持垃圾回收就有个搞笑的争论,一派人认为,内存管理太重要了,而手动管理麻烦且容易出错,所以我们应该交给机器去管理。另一派人则认为,内存管理太重要了!所以如果交给机器管理我不能放心。争论归争论,但不管哪一派,大家对内存管理重要性的认同都是勿庸质疑的。

Go语言是一门带垃圾回收的语言,Go语言中有指针,却没有 C 中那么灵活的指针操作。大多数情况下是不需要用户自己去管理内存的,但是理解 Go语言是如何做内存管理对于写出优秀的程序是大有帮助的。

内存池概述

Go语言的内存分配器采用了跟 tcmalloc 库相同的实现,是一个带内存池的分配器,底层直接调用操作系统的 mmap 等函数。

作为一个内存池,回忆一下跟它相关的基本部分。首先,它会向操作系统申请大块内存,自己管理这部分内存。然后,它是一个池子,当上层释放内存时它不实际归还给操作系统,而是放回池子重复利用。

接着,内存管理中必然会考虑的就是内存碎片问题,如果尽量避免内存碎片,提高内存利用率,像操作系统中的首次适应,最佳适应,最差适应,伙伴算法都是一些相关的背景知识。

另外,Go语言是一个支持 goroutine 这种多线程的语言,所以它的内存管理系统必须也要考虑在多线程下的稳定性和效率问题。

在多线程方面,很自然的做法就是每条线程都有自己的本地的内存,然后有一个全局的分配链,当某个线程中内存不足后就向全局分配链中申请内存。这样就避免了多线程同时访问共享变量时的加锁。

在避免内存碎片方面,大块内存直接按页为单位分配,小块内存会切成各种不同的固定大小的块,申请做任意字节内存时会向上取整到最接近的块,将整块分配给申请者以避免随意切割。

Go中为每个系统线程分配一个本地的 MCache(前面介绍的结构体 M 中的 MCache 域),少量的地址分配就直接从 MCache 中分配,并且定期做垃圾回收,将线程的 MCache 中的空闲内存返回给全局控制堆。

小于 32K 为小对象,大对象直接从全局控制堆上以页(4k)为单位进行分配,也就是说大对象总是以页对齐的。一个页可以存入一些相同大小的小对象,小对象从本地内存链表中分配,大对象从中心内存堆中分配。

大约有 100 种内存块类别,每一类别都有自己对象的空闲链表。小于 32kB 的内存分配被向上取整到对应的尺寸类别,从相应的空闲链表中分配。一页内存只可以被分裂成同一种尺寸类别的对象,然后由空闲链表分配器管理。

分配器的数据结构包括:
  • FixAlloc: 固定大小 (128kB) 的对象的空闲链分配器,被分配器用于管理存储
  • MHeap: 分配堆,按页的粒度进行管理 (4kB)
  • MSpan: 一些由 MHeap 管理的页
  • MCentral: 对于给定尺寸类别的共享的 free list
  • MCache: 用于小对象的每 M 一个的 cache

我们可以将 Go语言的内存管理看成一个两级的内存管理结构,MHeap 和 MCache。上面一级管理的基本单位是页,用于分配大对象,每次分配都是若干连续的页,也就是若干个 4KB 的大小。

使用的数据结构是 MHeap 和 MSpan,用 BestFit 算法做分配,用位示图做回收。下面一级管理的基本单位是不同类型的固定大小的对象,更像一个对象池而不是内存池,用引用计数做回收。下面这一级使用的数据结构是 MCache。

MHeap

MHeap 层次用于直接分配较大 (>32kB) 的内存空间,以及给 MCentral 和 MCache 等下层提供空间。它管理的基本单位是 MSpan。MSpan 是一个表示若干连续内存页的数据结构,简化后如下:
struct MSpan
{
    PageID     start;          // starting page number
    uintptr     npages;        // number of pages in span
};
通过一个基地址 +(页号*页大小),就可以定位到这个 MSpan 的实际的地址空间了,基地址是在 MHeap 中存储了的。

MHeap 负责将 MSpan 组织和管理起来,MHeap 数据结构中的重要部分如图所示。

free 是一个分配池,从 free[i]出去的 MSpan 每个大小都 i 页的,总共 256 个槽位。再大了之后,大小就不固定了,由 large 链起来。

分配过程:如果能从 free[] 的分配池中分配,则从其中分配。如果发生切割则将剩余部分放回 free[] 中。比如要分配 2 页大小的空间,从图上 2 号槽位开始寻找,直到 4 号槽位有可用的 MSpan,则拿一个出来,切出两页,剩余的部分再放回 2 号槽位中。否则从 large 链表中去分配,按 BestFit 算法去找一块可用空间。

化整为零简单,化零为整麻烦。回收的时候如果相邻的块是未使用的,要进行合并,否则一直划分下去就会产生很多碎片,找不到一个足够大小的连续空间。因为涉及到合并,回收会比分配复杂一些,所有就有什么伙伴算法,边界标识算法,位示图之类的。

Go 在这里使用的类似于位示图。可以看到 MHeap 中有一个

MSpan  *map[1<<MHeapMap_Bits];

这个数组是一个用于将内存地址映射成 MSpan 结构体的表,每个内存页都会对应到 map 中的一个 MSpan 指针,通过 map 就能够将地址映射到相应的 MSpan。

具体做法,给定一个地址,可以通过(地址-基地址)/ 页大小得到页号,再通过 map[页号] 就得到了相应的 MSpan 结构体。

前面说过,MSpan 就是若干连续的页。那么,一个多页的 MSpan 会占用 map 数组中的多项,有多少页就会占用多少项。比如,可能 map[502] 到 map[505] 都指向同一个 MSpan,这个 MSpan 的 PageId 为 502,npages 为 4。

回收过程:回收一个 MSpan 时,首先会查找它相邻的页的址址,再通过 map 映射得到该页对应的 MSpan,如果 MSpan 的 state 是未使用,则可以将两者进行合并。最后会将这页或者合并后的页归还到 free[] 分配池或者是 large 中。

MCache

MCache 层次跟 MHeap 层次非常像,也是一个分配池,对每个尺寸的类别都有一个空闲对象的单链表。Go 的内存管理可以看成一个两级的层次,上面一级是 MHeap 层次,而 MCache 则是下面一级。

每个 M 都有一个自己的局部内存缓存 MCache,这样分配小对象的时候直接从 MCache 中分配,就不用加锁了,这是 Go 能够在多线程环境中高效地进行内存分配的重要原因。MCache 是用于小对象的分配。

分配一个小对象 (<32kB) 的过程:
  • 将小对象大小向上取整到一个对应的尺寸类别,查找相应的 MCache 的空闲链表。如果链表不空,直接从上面分配一个对象。这个过程可以不必加锁。
  • 如果 MCache 自由链是空的,通过从 MCentral 自由链拿一些对象进行补充。
  • 如果 MCentral 自由链是空的,则通过 MHeap 中拿一些页对 MCentral 进行补充,然后将这些内存截断成规定的大小。
  • 如果 MHeap 是空的,或者没有足够大小的页了,从操作系统分配一组新的页(至少 1MB)。分配一大批的页分摊了从操作系统分配的开销。

注意上面表述中的用词“一些”。从 MCentral 中拿“一些“自由链对象补充 MCache 分摊了访问 MCentral 加锁的开销。从 MHeap 中分配“一些“的页补充 MCentral 分摊了对 MHeap 加锁的开销。

释放一个小对象也是类似的过程:
  • 查找对象所属的尺寸类别,将它添加到 MCache 的自由链。
  • 如果 MCache 自由链太长或者 MCache 内存大多了,则返还一些到 MCentral 自由链。
  • 如果在某个范围的所有的对象都归还到 MCentral 链了,则将它们归还到页堆。

归还到 MHeap 就结束了,目前还是没有归还到操作系统。

MCache 层次仅用于分配小对象,分配和释放大的对象则是直接使用 MHeap 的,跳过 MCache 和 MCentral 自由链。MCache 和 MCentral 中自由链的小对象可能是也可能不是清 0 了的。对象的第 2 个字节作为标记,当它是 0 时,此对象是清 0 了的。页堆中的总是清零的,当一定范围的对象归还到页堆时,需要先清零。这样才符合 Go语言规范:分配一个对象不进行初始化,它的默认值是该类型的零值。

MCentral

MCentral 层次是作为 MCache 和 MHeap 的连接。对上,它从 MHeap 中申请 MSpan; 对下,它将 MSpan 划分成各种小尺寸对象,提供给 MCache 使用。
struct  MCentral
{
    Lock;
    int32  sizeclass;
    MSpan  nonempty;
    MSpan  empty;
    int32  nfree;
};
注意,每个 MSpan 只会分割成同种大小的对象。每个 MCentral 也是只含同种大小的对象。MCentral 结构中,有一个 nonempty 的 MSpan 链和一个 empty 的 MSpan 链,分别表示还有空间的 MSpan 和装满了对象的 MSpan。

分配还是很简单,直接从 MCentral->nonempty->freelist 分配。如果发现 freelist 空了,则说明这一块 MSpan 满了,将它移到 MCentral->empty。

前面说过,回收比分配复杂,因为涉及到合并。这里的合并是通过引用计数实现的。从 MSpan 中每划出一个对象,则引用计数加一,每回收一个对象,则引用计数减一。如果减完之后引用计数为零了,则说明这整块的 MSpan 已经没被使用了,可以将它归还给 MHeap。