本主题文章讲Go内存分配管理,分为上篇和下篇两篇文章,上篇主要讲内存分配相关概念和tcmalloc原理,下篇将具体介绍Go内存分配原理。这是上篇部分,核心内容在tcmalloc,之所以介绍tcmalloc是因为Go的内存分配算法来源于Google为C语言开发的tcmalloc(thread-caching malloc)算法。理解了tcmalloc算法,也就基本理解了Go的内存分配原理。
Go语言采用自主管理内存,也就是由runtime来管理。应用程序向runtime申请内存,runtime向操作系统申请内存。Go之所以采用runtime(运行时)管理内存,有两大方面的原因,一是可以通过内存池和预分配等技术手段实现更好的内存使用模式,不用每次申请内存都要进行系统调用。二是Go是一门自带GC的语言,需要在内存不用时主动释放,开发者无需关心内存释放问题,减轻他们的心智负担,所以需要专门管理内存释放的组件,这个组件放在runtime(运行时)非常合理。Go内存管理涵盖内存的申请、分配、回收以及释放。整体流程如下图所示
虚拟内存顾名思义表示内存并不是真实存在的,与之相对的是物理内存。物理内存是真实存在的,对应到电脑上的硬件就是内存芯片。虚拟内存的引入解决了两方面问题:
操作系统将虚拟内存划分成整齐的小块,每个小块称为一个页(page)。之所以分页,原因有两个方面,一是整齐的页能够避免内存碎片的问题,二是因为每个进程使用的数据有高频和低频之分,有了分页,操作系统不在从进程角度去思考哪个进程是高频的,哪个是低频的。只需考虑哪些页被高频使用、哪些页被低频使用。如果是低频使用,就将它们保存到磁盘上,如果是高频使用,让它继续留在内存中。
我们先来看linux下一个进程的虚拟内存空间划分图,可以看到栈区和堆区只是虚拟内存上两个不同功能的内存区域。栈在高地址空间,从高地址向低地址增长,堆在低地址空间,从低地址向高地址增长。
堆区和栈区比较起来,有以下不同:
结合上面的进程虚拟内存空间划分图,内存动态变化的区域在栈区和堆区,栈区由编译器进行管理,所以我们主要关注堆内存的管理。如下图所示,堆内存管理的主要内容包括堆内存的分配和回收,以及为了方便分配和回收如何组织内存块。
在介绍堆内存分配方法之前,我们先要了解内存对齐的概念。
对于基础数据类型,如byte, int, double等,它们的大小和内存占用是一致的,对于结构体而言,如果我们获取它的sizeof结果,会发现这个值有可能会大于结构体内所有成员大小的总和,这时由于结构体内部进行了内存对齐。为什么要进行内存对齐?有两方面的原因
下面程序中结构体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.为什么说它简单,因为没有考虑到内存碎片的问题。随着内存不断的申请和释放,内存上会存在大量的碎片,降低了内存的使用率。根据碎片产生的原因,把碎片分为内部碎片和外部碎片两种类型:
我们知道操作系统对内存管理以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是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管理的内容。这里先不细说。
通过前面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将对象占用的内存大小划分为三种类型:小对象、中对象和大对象。
上面介绍完了内存分配的几个基本概念,下面将分别介绍小对象、中对象和大对象是如何分配的,以及涉及到的三大分配组件:threadCache、centralCache和pageHeap.
对于小对象的分配,即对象的大小在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.
tcmalloc通过SizeMap类维护了上面小对象分配具体的映射关系,摘录的部分映射关系如下:
申请大小 | size class index | object_size | num_objects_to_move | class_to_pages |
---|---|---|---|---|
1 | 1 | 8 | 32 | 1 |
9 | 2 | 16 | 32 | 1 |
16 | 2 | 16 | 32 | 1 |
2047 | 37 | 2048 | 32 | 2 |
4068 | 43 | 4096 | 16 | 2 |
262144 | 85 | 262144 | 2 | 32 |
对每个线程,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分配小内存的流程为:
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后会进行如下处理:
当threadCache从centralFreeList获取object时:
当threadCache归还object给centralFreeList时:
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)申请内存时:
调用Delete(Span *span)进行内存回收:
占用内存大小在(256kB,1MB]范围内的对象被称为中对象,中等对象的分配与小对象的分配方式不同。通过前面小对象的分配流程,小对象的分配过程是threadCache<->centralCache<->pageHeap.中等对象分配是直接从pageHeap分配的。256KB大小的内存占用32个page(每个page 8K),1MB的内存占用128个page. tcmalloc会将应用程序申请的内存大小向上取整到整数个page,然后向pageHeap申请一个指定page数量的span并返回起始地址。假设要申请的100个page的内存,具体分配流程为:
超过128个page的内存分配视为大对象分配,大对象的分配也是直接从pageHeap分配的。从前面pageHeap结构字段可以看到,free_中最大的page是128个。所以大对象的分配不能走free_中的链表了,而是一个按span大小排序的有序set,方便按大小搜索。假设现在要分配一个130个page的大对象,具体的分配流程如下:
tcmalloc算法总结起来,不外乎两点,将所有分配的对象的大小划分成了小对象、中对象和大对象,小对象的分配需要经过threadCache,centralCache,pageHeap三层缓存,中对象和大对象的分配直接从pageHeap分配,相当于只有一层缓存。增高分配流程概览如下图。
图解 TCMalloc[1]详解Go语言的内存模型及堆的分配管理[2]TCMalloc解密[3]
图解 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