6.1 内存池

6.1 内存池

概述

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。

其它

本节的内存池涉及的文件包括：

malloc.h 头文件
malloc.goc 最外层的包装
msize.c 将各种大小向上取整到相应的尺寸类别
mheap.c 对应MHeap中相关实现,还有MSpan
mcache.c 对应MCache中相关实现
mcentral.c 对应MCentral中相关实现
mem_linux.c SysAlloc等sys相关的实现