Go内存管理-上篇

本主题文章讲Go内存分配管理，分为上篇和下篇两篇文章，上篇主要讲内存分配相关概念和tcmalloc原理，下篇将具体介绍Go内存分配原理。这是上篇部分，核心内容在tcmalloc,之所以介绍tcmalloc是因为Go的内存分配算法来源于Google为C语言开发的tcmalloc（thread-caching malloc）算法。理解了tcmalloc算法，也就基本理解了Go的内存分配原理。

相关概念

Go内存管理

Go语言采用自主管理内存，也就是由runtime来管理。应用程序向runtime申请内存，runtime向操作系统申请内存。Go之所以采用runtime(运行时）管理内存，有两大方面的原因，一是可以通过内存池和预分配等技术手段实现更好的内存使用模式，不用每次申请内存都要进行系统调用。二是Go是一门自带GC的语言，需要在内存不用时主动释放，开发者无需关心内存释放问题，减轻他们的心智负担，所以需要专门管理内存释放的组件，这个组件放在runtime(运行时)非常合理。Go内存管理涵盖内存的申请、分配、回收以及释放。整体流程如下图所示

虚拟内存

虚拟内存顾名思义表示内存并不是真实存在的，与之相对的是物理内存。物理内存是真实存在的，对应到电脑上的硬件就是内存芯片。虚拟内存的引入解决了两方面问题：

• 解决了直接读写物理内存安全性问题，因为物理内存本身是不限制访问的，任何地址都可以读写，而现代操作系统需要实现不同的页面就有不同的权限。
• 解决了进程间的安全问题，如果各个进程之间没有独立的地址空间，一个进程由于执行错误的指令可能会修改其他进程的数据，甚至修改内核地址空间的数据，这有很大的安全隐患 有了虚拟内存之后，每个进程的都有自己独立的地址空间，互相不影响。从进程视角来看，每个程序申请的内存地址是从各自的虚拟内存分配的。例如有A和B两个进程，它们申请某一片内存地址都是0x00003fff,也不会影响彼此，因为它们在不同的虚拟内存空间。然后有操作系统管理虚拟内存和真实内存（物理内存）之间的映射。

操作系统将虚拟内存划分成整齐的小块，每个小块称为一个页（page)。之所以分页，原因有两个方面，一是整齐的页能够避免内存碎片的问题，二是因为每个进程使用的数据有高频和低频之分，有了分页，操作系统不在从进程角度去思考哪个进程是高频的，哪个是低频的。只需考虑哪些页被高频使用、哪些页被低频使用。如果是低频使用，就将它们保存到磁盘上，如果是高频使用，让它继续留在内存中。

堆和栈

我们先来看linux下一个进程的虚拟内存空间划分图，可以看到栈区和堆区只是虚拟内存上两个不同功能的内存区域。栈在高地址空间，从高地址向低地址增长，堆在低地址空间，从低地址向高地址增长。

堆区和栈区比较起来，有以下不同：

• 栈区内存分配由编译器自动管理，不用我们手动控制，分配内存比堆上块
• 堆区内存需要进行回收，不管是程序员主动free，还是被动的垃圾回收，像Go有GC进行垃圾回收，这些都需要花费额外的CPU.
• 堆区频繁的内存申请和释放会造成空间的不连续，从而造成大量的碎片，使得程序效率降低，但栈会被存在这个问题。
• 栈上的内存有更好的局部性，堆上内存访问就不会像栈上那么友好，CPU访问的两块数据可能在不同的页上，花费的时间就比较多。

堆内存管理

结合上面的进程虚拟内存空间划分图，内存动态变化的区域在栈区和堆区，栈区由编译器进行管理，所以我们主要关注堆内存的管理。如下图所示，堆内存管理的主要内容包括堆内存的分配和回收，以及为了方便分配和回收如何组织内存块。

在介绍堆内存分配方法之前，我们先要了解内存对齐的概念。

内存对齐

对于基础数据类型，如byte, int, double等，它们的大小和内存占用是一致的，对于结构体而言，如果我们获取它的sizeof结果，会发现这个值有可能会大于结构体内所有成员大小的总和，这时由于结构体内部进行了内存对齐。为什么要进行内存对齐？有两方面的原因

• 内存对齐使数据读取更高效，在硬件设计上，数据读取的处理器只能从地址为x的倍数的内存处开始读取数据。这种读取方式相当于将内存分为了多个“块”，假设内存可以从任意位置开始存放的话，数据很可能会被分散到多个“块”中，处理分散在多个块中的数据需要移除首尾不需要的字节，再进行合并，非常耗时。为了提高数据读取的效率，程序分配的内存并不是连续存储的，而是按首地址为x的倍数的方式存储；这样就可以一次性读取数据，而不需要额外的操作上图为非内存对齐读取，因为硬件只能从地址x的倍数读取，而恰好data放的位置不是x的倍数，所以上面图中数据要进行两次读取。然后还要进行移位合并操作，花费额外时间。
• 在某些平台下，不进行内存对齐会崩溃

下面程序中结构体A和B成员变量是一样的，但是通过输出可以看到他们占用的内存大小是不一样的。在我的电脑上输出的分别是24和16，在你的电脑上跑结果可能与我的不一致，但输出的两个值是不相等的。

type A struct {
 a byte
 b int
 c byte
}

type B struct {
 b int
 a byte
 c byte
}

func testMemoryAlign() {
 fmt.Println(unsafe.Sizeof(A{}), unsafe.Sizeof(B{}))
}

假如现在让我设计一个堆内存分配方法，我该怎么做呢？也许你会想到，按需分配，堆内存最开始的时候是一个完整的大块，当发现有内存申请的时候，就从未分配的内存中划分出一个小内存块.核心思想就是用多少分配多少，用一个标识标注已经分配到哪里了，下一次分配的时候从标记的位置后面开始分配。

但是这里有一个问题，已经分配的内存被释放了，下次如何才能够在使用？所以还要维护每个分配的内存块信息，称之为内存分配的元数据信息，元数据信息需要记录内存块block的大小（size)，从哪个地址开始到哪里结束，是否在使用中(used)，下一个内存块的位置(next)。嗯，我们可用链表LinkedList将内存块串联起来。于是，得到改进后的内存分配方法，如下图所示。

一个内存块包含了3类信息，元数据信息（meta data）、对齐字段(align)和用户数据(data)，前面也讲了内存对齐的问题。内存释放就是把标记为used从1改为0，即视为此块内存未使用，当再次分配内存块的时候，可以从未使用的内存块中查找到大小相近的内存块。如果找不到，再从未分配的内存中分配内存。

上述简单分配内存的方法称之为FreeeList.为什么说它简单，因为没有考虑到内存碎片的问题。随着内存不断的申请和释放，内存上会存在大量的碎片，降低了内存的使用率。根据碎片产生的原因，把碎片分为内部碎片和外部碎片两种类型：

• 内部碎片：系统分配的内存大于实际所需的内存，由于内存对齐机制。
• 外部碎片：不断分配回收不同大小的内存，由于内存分布散乱，较大内存分配无法分配。

tcmalloc

page

我们知道操作系统对内存管理以page(页)为单位，tcmalloc管理内存也是以page为单位。不过需要留意的是tcmalloc里的page大小与操作系统里的大小并不一定相等，tcmalloc里的page大小一般是操作系统的数倍。在X64系统下，tcmalloc里page的默认大小为8KB.多数linux系统中一页大小为4KB，也就是说tcmalloc中的一页对应linux中两页。整个内存空间可以看成是一个一个page连接起来的，tcmalloc将并不是只将堆内存划分成page的集合，而是将整个虚拟内存空间都看做是page的集合。从内存地址0x0开始到最大内存地址，每8KB划分为一个page,每一个page都有唯一的pageID，从低地址向高地址，pageID是递增的。下图是以64位系统page划分的示意图。

span

span是tcmalloc管理内存的基本单位，内存分配组件基本都是围绕span展开。我们先来看span的定义，一个或多个连续的page组成一个span. tcmalloc以span为单位向系统操作系统申请内存。注意span定义中的2个要素：1个或多个，连续的page.

如上图所示，span1占用了2个page，span2占用了3个page，span3和span4分别占用了1个page.

下面是span的结构体定义

struct Span {
  PageID        start;          // Span描述的内存的起始地址
  Length        length;         // Span页面数量
  Span*         next;           // Span由双向链表组成，PageHeap和CentralFreeList中都用的到
  Span*         prev;           
  void*         objects;        // Span会在CentralFreeList中拆分成由object组成的free list
  unsigned int  refcount : 16;  // Span的object被引用次数，当refcount=0时，表示此Span没有被使用
  unsigned int  sizeclass : 8;  // Span属于的size class
  unsigned int  location : 2;   // Span在的位置是IN_USE还是normal还是returned
  unsigned int  sample : 1;    
  enum { IN_USE, ON_NORMAL_FREELIST, ON_RETURNED_FREELIST };
};

通过上面Span的结构体定义可以看到，它有一个start和length字段，start记录了该span是从哪个pageID开始，length记录该span含有几个page,所以start和length可以确定一个span对应的pages. 一个span要么被拆分成多个相同size class的小对象用于小对象分配，要么作为一个整体用于中对象或大对象分配。当用作小对象分配时，span中的sizeclass字段记录了其对应的size class.具体小对象、中对象和大对象的划分见下文的说明。在span结构中，还有两个span类型的指针变量（prev,next)，分别指向前一个span和下一个span,将多个span以链表形式串起来。span结构体中的location标识该span处于什么状态。span一共有三种状态:IN_USE,ON_NORMAL_FREELIST,ON_RETURNED_FREELIST.怎么理解这些状态呢？站在pageHeap的角度，pageHeap具体概念见下文。这里先记住pageHeap是管理span的。IN_USE顾名思义就是正在使用中，就是说拆分的小对象已分配给centralCache或者threadCache或者是已分配给应用程序了。因为从pageHeap角度看，span不管是被mcentralCache还是被threadCache，还是被应用程序使用，反正都是被使用了。ON_NORMAL_FREELIST和ON_RETURNED_FREELIST都可以看做为空闲状态，两者的区别是：ON_RETURNED_FREELIST是指span对应的内存已被pageHeap释放给操作系统了。在linux下，对于MAP_PRIVATE|MAP_ANONYMOUS的内存采用madvise来回收。注意这里的内存即使返回给操作系统了，这片地址还是可以访问的，在下一次访问的时候会导致page fault.

span结构体中的objects、refcount、sizeclass字段属于centralFreeList管理的内容。这里先不细说。

pageMap

通过前面span结构的介绍，可以看到知道了span，就可以知道它维护的page.但反过来，现在有一个page, 怎么才能知道它属于哪个span?对，这就是pageMap要维护的，pageMap维护了page到span的关系。pageMap缓存了pageID到span的对应关系，下面以32系统进行说明，采用两级pageMap. 结构如下图所示

root数组大小为512，每个数组中的元素又是1024个void的数组，数组索引为pageID,数组元素为page所属的span的指针，所以总的数组元素个数为512*1024=2^19,也就是能够维护2^19个page.使用两级map可以减少tcmalloc元素数据的内存占用，因为初始化只会给第一层root_数组分配空间，占用的大小为512*4B=2048B=2KB.第二层只有在实际使用到的时候才会实际分配内存。如果不采用两级使用一级，初始化的时候就需要分配2^19*4B=2MB的内存。

小对象、中对象和大对象

在申请对象的时候，需要给对象分配空间。不同的对象的大小往往是不同的，为了方便内存分配管理，tcmalloc将对象占用的内存大小划分为三种类型：小对象、中对象和大对象。

• 小对象，占用的内存大小为(0,256KB]
• 中对象，占用的内存大小为(256KB,1MB]
• 大对象，占用的内存大小为(1MB,+∞） tcmalloc对小对象分配与中对象和大对象是不同的，分配细节见下面的介绍。

上面介绍完了内存分配的几个基本概念，下面将分别介绍小对象、中对象和大对象是如何分配的，以及涉及到的三大分配组件：threadCache、centralCache和pageHeap.

小对象分配

size class

对于小对象的分配，即对象的大小在256KB(含)以内的分配，tcmalloc定义了86个size class（从class0到class85），每个size class都维护了一个可以分配的空闲列表(FreeList). FreeList中的每一项称为一个object，同一个class的空闲列表中的每个object大小都是相同的。在申请小对象内存时，tcmalloc会根据大小映射到某个class中。比如说，在申请1到8个Byte的大小时，会被映射到class1中，分配8个字节的大小。申请9到16字节大小时，会被映射到class2中，实际分配16个字节的大小。依次类推，直到class85.

SizeMap

tcmalloc通过SizeMap类维护了上面小对象分配具体的映射关系，摘录的部分映射关系如下：

• num_objects_to_move用来定义threadCache在内存不足时从centralFreeList一次获取多少个object
• class_to_pages用来定义centralFreeList在内存不足时每次从pageHeap获取多少页
• 当申请的内存大小大于256KB时，不再通过SizeMap预定义分配内存，而是通过pageHeap直接分配大内存

threadCache

对每个线程，tcmalloc都为它保存了一份单独的缓存，称之为threadCache.每个threadCache中有一组FreeList,每个size class都有一个单独的FreeList,所以这一组FreeList为87个，FreeList缓存了还未被应用程序使用的空闲对象。threadCache结构的核心字段如下

class FreeList {
private:
 void*    list_;
 uint32_t length_;
 uint32_t lowater_;
 uint32_t max_length_;
};

class ThreadCache {
private:
     FreeList      list_[kNumClasses];    
};

threadCache结构体中list_字段即为FreeList数组，在实现FreeList的时候tcmalloc采用一种小技巧，没有使用next指针指向下一个位置，而是直接使用了void *list，将每个object的前8个字节存储下一个object地址。小对象的分配直接从待分配对象映射到的FreeList中返回一个空闲对象，同理，在小对象回收的时候也是将其重新放回threadCache中的FreeList中。由于每个线程一个threadCache,不存在数据竞争，因此从ThreadCache中申请或回收内存是不需加锁的，速度很快。为了方便统计数据，各线程的threadCache构成了一个双向链表。得到threadCache的结构图如下

通过threadCache分配小内存的流程为：

1. 通过SizeMap查找要分配的内存对应的size class以及object size大小
2. 查看当前threadCache的free list是否为空，如果free list不为空，直接从列表中移除第一个object并返回，这个过程不需要加锁，所以速度很快
3. 如果free list为空，从centralFreeList中获取若干个object到threadCache对应的size class列表中，并取出其中一个object返回,具体获取的object个数由慢启动算法决定，为了防止空间浪费。
4. 如果centralFreeList中object也不够，则centralFreeList会向pageHeap申请一连串页面,具体为class_to_pages个，并将申请的页面切割成一系列的object，之后再将部分object转移给threadCache.

centralCache

centralCache可以理解为中间人角色，它逻辑上位于threadCache和pageHeap之间，它本质上是一个CentralFreeListPadded类型的数组，数组大小为87(size class的数量)，每个size class对应数组中的一个元素，数组中的元素是CentralFreeListPadded类型，CentralFreeListPadded是CentralFreeList的子类，不同在于它是字节对齐的。下面我们来看它的结构体定义

static CentralFreeListPadded central_cache_[kNumClasses];
  class CentralFreeList {
  private:
      SpinLock lock_;
      size_t size_class_;
      Span empty_;       
      Span nonempty_;
  };

threadCache之间共享这些centralFreeList.所以，使用centralCache时需要加锁。通过上面CentralFreeList的结构体定义可以看到，它包含3个核心字段，size_class_表示size class， 另外两个都是Span类型，因为CentralFreeList真正管理的就是span. empty_链表保存了已经没有空闲对象可用的span,也就是span中的object对象都已划分出去了。nonempty_链表保存了还有空闲对象可用的span.

centralFreeList的功能之一就是从pageHeap中取出部分span并按照预定大小（在SizeMap中有定义）将其拆分成大小固定的object供threadCache共享，CentralFreeList从PageHeap拿个一个span后会进行如下处理：

1. 通过调用PageHeap:RegisterSizeClass()将span中的location赋值为IN_USE,并将sizeclass填充为指定的值
2. 通过SizeMap获取size class对应的object大小，然后将span切片，通过void *objects保存为object的free list
3. 将span挂载到nonempty_链表中

当threadCache从centralFreeList获取object时：

1. 从nonempty_链表中获取第一个span, 并从span中的objects链表中获取可用object返回，每分配一个object,span的refcount加1
2. 当span无可用object时，将此span从nonempty_链表摘除，挂载到empty_链表，当object回收归还给此span时会重新将其挂载到nonempty_链表

当threadCache归还object给centralFreeList时：

1. 找到此object对应的span,挂载到objects链表表头，如果span在empty_链表，则重新挂接到nonempty_链表
2. span的refcount减1，如果refcount变为0，表示此span所有的object都已经归还，将此span从centralFreeList链表中摘除，并将它退还给pageHeap.

pageHeap

pageHeap主要功能是向操作系统申请内存，然后管理划分后的内存。pageHeap主要结构为

struct SpanList {
   Span        normal;
   Span        returned;
};

SpanList free_[kMaxPages]; // kMaxPages = 128

SpanSet large_normal_;
SpanSet large_returned_;

可以看到pageHeap中有一个大小为128的free_数组，数组的元素为SpanList类型，SpanList是一个含有两个Span的结构体。128page以内的span称为小span,128page以上的span称为大span. 小span的管理在free_数组，大span的管理由large_normal_和large_returned_维护。对于小span,每个大小的span都用一个单独的链表来管理，大span用std::set. pageHeap是分开管理ON_NORMAL_FREELIST和ON_RETURNED_FREELIST状态的span的。

SpanList中的normal span是页明确映射到进程地址空间的span,returned span是tcmalloc已经通过madvise归还给操作系统空间，调用madvise相当于取消了虚拟内存与物理内存的映射，之所以保留returned链表，是因为虽然通过madvise归还给了操作系统，但是操作系统有可能还没有收回这部分内存空间，可以直接使用，即使操作系统已经回收了这部分内存，重新使用这部分空间时内核会引发page fault并将其映射到一块全零的内存空间，不影响使用。

下面看pageHeap是如何申请内存和释放内存的。调用Span *New(Length n)申请内存时：

1. free_[KMaxPages]中大于等于n的free list会被遍历一遍，查找是否有合适大小的span, 如果有，则将此span从free list中移除，如果span大小比n大，则会将span进行Carve,将剩余的span重新放入到free list中。例如，n为2，但是在遍历时发现free_[2]对应的链表中已经没有空闲的span了，但是在free_[3]中找到了空闲的span，这时候会将此span切分成两份，一份对应2个page,返回给调用方，另一份对应1个page，挂载到free_[1]中，供下次使用
2. 如果free_中的normal和returned链表中找不到合适的span,则从spanSet中查大小最合适的span.这时候需要遍历large_normal_和large_returned_列表
3. 如果large_normal_和large_returned_也没有可用的span,则通过tcmalloc_SystemAlloc()向操作系统申请，并返回指定大小span.每次都会尝试申请至少128页，以供下次使用

调用Delete(Span *span)进行内存回收：

1. 将span重新放入pageHeap的free list中，如果span的左右相邻的span也是空闲的，则将它们从free list中去除，然后合并为同一个span再挂载到free list
2. 检查是否需要释放内存给操作系统，如果需要，则释放

中对象分配

占用内存大小在(256kB,1MB]范围内的对象被称为中对象，中等对象的分配与小对象的分配方式不同。通过前面小对象的分配流程，小对象的分配过程是threadCache<->centralCache<->pageHeap.中等对象分配是直接从pageHeap分配的。256KB大小的内存占用32个page(每个page 8K),1MB的内存占用128个page. tcmalloc会将应用程序申请的内存大小向上取整到整数个page,然后向pageHeap申请一个指定page数量的span并返回起始地址。假设要申请的100个page的内存，具体分配流程为：

1. 在pageHeap中从100个page的span链表开始，直到128个page的span链表，按顺序找到第一个非空的链表
2. 取出此非空链表中的一个span,假设有102个page，将这个切分成两个span,一个span的大小为100个page,用作结果返回，另一个span大小为2个page,重新插入到2个page的span链表中
3. 如果找不到非空链表，则将此次分配看做大对象分配对待，大对象的分配见下面的介绍

大对象分配

超过128个page的内存分配视为大对象分配，大对象的分配也是直接从pageHeap分配的。从前面pageHeap结构字段可以看到，free_中最大的page是128个。所以大对象的分配不能走free_中的链表了，而是一个按span大小排序的有序set,方便按大小搜索。假设现在要分配一个130个page的大对象，具体的分配流程如下：

1. 从pageHeap的span set中取一个大小为130个page的span.如果恰好有130个page的span，就分配出去。如果set中找不到130个page的span,则从大于130个page的span中挑选pages最小的那个，假设为135个page。
2. 对挑选出来的span进行切分成两个span.一个span大小为130个page,作为返回结果，另一个span大小为(135-130)=5个page,因为5<128,所以将其插入到小span链表中，如果切分后剩余的span中的page大于128，则插入到大span的set中
3. 如果找不到合适的span,则会使用sbrk或mmap向操作系统申请新的内存以生产新的span,并重新执行中对象或大对象的分配算法

总结

tcmalloc算法总结起来，不外乎两点，将所有分配的对象的大小划分成了小对象、中对象和大对象，小对象的分配需要经过threadCache,centralCache,pageHeap三层缓存，中对象和大对象的分配直接从pageHeap分配，相当于只有一层缓存。增高分配流程概览如下图。

图解 TCMalloc[1]详解Go语言的内存模型及堆的分配管理[2]TCMalloc解密[3]

Reference

[1]

图解 TCMalloc: https://zhuanlan.zhihu.com/p/29216091

[2]

详解Go语言的内存模型及堆的分配管理: https://zhuanlan.zhihu.com/p/76802887

[3]

TCMalloc解密: https://wallenwang.com/2018/11/tcmalloc/#ftoc-heading-26