Go内存分配学习

Posted by DeepBlue on 07-20,2021

内存管理组件

内存管理一般包括三个组件,即用户程序(Mutator) 、分配器(Allocator)和收集器(Collector),其中用户程序向内存分配器提交内存分配请求,内存分配器分配内存同时进行初始化,收集器可以理解为程序中的GC,它将分配器分配出的内存进行收集。

mutatoralloc

内存分配器

线性分配法

内存分配器一般有两种分配方法,一种是线性分配另一种为空闲链表分配线性分配法相当于Java中的指针碰撞的方法进行内存的分配,将内存分为两个部分,一部分为已分配内存区域,另一部分为未进行内存分配的空闲区域,使用一个指针记录空闲区和已经分配区的位置,在进行内存分配时移动这个指针完成内存的分配。具体原理如下所示

但是使用这种线性会有一个缺点,即无法在内存被释放时进行重用,例如下图所示

bump-allocator-reclaim-memory

如果使用这种方法进行内存分配的话,我们需要配合垃圾回收算法进行重用,例如进行标记压缩,复制算法,分代回收算法,这些算法可以将存活对象的内存空间进行拷贝移动,这样可以使用线性分配的内存分配方法进行内存空间的分配。

但是,Go并没有采用这种内存分配方法,因为在Go中存在指针类型的变量,将堆中的对象移动后要改变指针的指向,这就导致我们在Go中没有办法使用这一种内存分配的策略。

空闲链表分配法

空闲链表分配器(Free-List Allocator)可以重用已经被释放的内存,它在内部会维护一个类似链表的数据结构。当用户程序申请内存时,空闲链表分配器会依次遍历空闲的内存块,找到足够大的内存,然后申请新的资源并修改链表:

free-list-allocator

利用空闲链表法可以使得内存进行重用,但是使用这种方法我们需要维护一个内存的链表结构,在每次进行内存分配的时候遍历这个链表,这样的话就有了O(n)的时间复杂度。当然我们也可以使用以下几种内存分配方法进行内存的分配:

  • 首次适应(First-Fit)— 从链表头开始遍历,选择第一个大小大于申请内存的内存块;
  • 循环首次适应(Next-Fit)— 从上次遍历的结束位置开始遍历,选择第一个大小大于申请内存的内存块;
  • 最优适应(Best-Fit)— 从链表头遍历整个链表,选择最合适的内存块;
  • 隔离适应(Segregated-Fit)— 将内存分割成多个链表,每个链表中的内存块大小相同,申请内存时先找到满足条件的链表,再从链表中选择合适的内存块;

前三种内存分配方法我们应该在学计算机操作系统的时候都有所了解,Go使用的内存分配策略和隔离适应算法有些相似,但是不完全相同。该策略抽象如下。

segregated-list如图所示,该策略会将内存分割成由 4、8、16、32 字节的内存块组成的链表,当我们向内存分配器申请 8 字节的内存时,它会在上图中找到满足条件的空闲内存块并返回。隔离适应的分配策略减少了需要遍历的内存块数量,提高了内存分配的效率。

分级分配

线程缓存分配(Thread-Caching Malloc,TCMalloc)是用于分配内存的机制,它比 glibc 中的 malloc 还要快很多。Go 语言的内存分配器就借鉴了 TCMalloc 的设计实现高速的内存分配,它的核心理念是使用多级缓存将对象根据大小分类,并按照类别实施不同的分配策略。

Go语言依据对象大小将对象分成微对象,小对象和大对象。

对象类型对象大小
微对象(0, 16B)
小对象[16B, 32KB]
大对象(32KB, +∞)

内存分配器不仅会区别对待大小不同的对象,还会将内存分成不同的级别分别管理,TCMalloc 和 Go 运行时分配器都会引入线程缓存(Thread Cache)、中心缓存(Central Cache)和页堆(Page Heap)三个组件分级管理内存:

multi-level-cache

线程缓存属于每一个独立的线程,它能够满足线程上绝大多数的内存分配需求,因为不涉及多线程,所以也不需要使用互斥锁来保护内存,这能够减少锁竞争带来的性能损耗。当线程缓存不能满足需求时,运行时会使用中心缓存作为补充解决小对象的内存分配,在遇到 32KB 以上的对象时,内存分配器会选择页堆直接分配大内存。

这种多层级的内存分配设计与计算机操作系统中的多级缓存有些类似,因为多数的对象都是小对象,我们可以通过线程缓存和中心缓存提供足够的内存空间,发现资源不足时从上一级组件中获取更多的内存资源。这样设计可以使得内存分配速度更快,效率更高。

Go内存管理组件

Go 语言的内存分配器包含内存管理单元线程缓存中心缓存页堆几个重要组件。其中Go的内存布局如图所示

go-memory-layout

每一个处理器都会分配一个线程缓存 runtime.mcache 用于处理微对象和小对象的分配,它们会持有内存管理单元 runtime.mspan

每个类型的内存管理单元都会管理特定大小的对象,当内存管理单元中不存在空闲对象时,它们会从 runtime.mheap 持有的 134 个中心缓存 runtime.mcentral 中获取新的内存单元,中心缓存属于全局的堆结构体 runtime.mheap,它会从操作系统中申请内存。

Go内存管理单元

runtime.mspan 是 Go 语言内存管理的基本单元,该结构体中包含 nextprev 两个字段,它们分别指向了前一个和后一个 runtime.mspan

type mspan struct {
	next *mspan
	prev *mspan
	...
}

串联后的上述结构体会构成如下双向链表,运行时会使用 runtime.mSpanList 存储双向链表的头结点和尾节点并在线程缓存以及中心缓存中使用。

mspan-and-linked-list

每个 runtime.mspan 都管理 npages 个大小为 8KB 的页,这里的页不是操作系统中的内存页,它们是操作系统内存页的整数倍,该结构体会使用下面这些字段来管理内存页的分配和回收:

type mspan struct {
	startAddr uintptr // 起始地址
	npages    uintptr // 页数
	freeindex uintptr

	allocBits  *gcBits
	gcmarkBits *gcBits
	allocCache uint64
	...
}
  • startAddrnpages — 确定该结构体管理的多个页所在的内存,每个页的大小都是 8KB;
  • freeindex — 扫描页中空闲对象的初始索引;
  • allocBitsgcmarkBits — 分别用于标记内存的占用和回收情况;
  • allocCacheallocBits 的补码,可以用于快速查找内存中未被使用的内存;

runtime.mspan 会以两种不同的视角看待管理的内存,当结构体管理的内存不足时(申请的时候结构体内没有足够的内存,第一次看到这个我也懵了),运行时会以页为单位向堆申请内存。

mspan-and-pages

当用户程序或者线程向 runtime.mspan 申请内存时,它会使用 allocCache 字段以对象为单位在管理的内存中快速查找待分配的空间,如果我们能在内存中找到空闲的内存单元会直接返回,当内存中不包含空闲的内存时,上一级的组件 runtime.mcache 会为调用 runtime.mcache.refill 更新内存管理单元以满足为更多对象分配内存的需求。

线程缓存

runtime.mcache 是 Go 语言中的线程缓存,它会与线程上的处理器一一绑定,主要用来缓存用户程序申请的微小对象。每一个线程缓存都持有 68 * 2 个 runtime.mspan,这些内存管理单元都存储在结构体的 alloc 字段中:

mcache-and-mspans

线程缓存在刚刚被初始化时是不包含 runtime.mspan 的,只有当用户程序申请内存时才会从上一级组件获取新的 runtime.mspan

中心缓存

runtime.mcentral 是内存分配器的中心缓存,与线程缓存不同,访问中心缓存中的内存管理单元需要使用互斥锁:每个中心缓存都会管理某个跨度类的内存管理单元,它会同时持有两个 runtime.spanSet,分别存储包含空闲对象和不包含空闲对象的内存管理单元。

页堆

runtime.mheap 是内存分配的核心结构体,Go 语言程序会将其作为全局变量存储,而堆上初始化的所有对象都由该结构体统一管理,该结构体中包含两组非常重要的字段,其中一个是全局的中心缓存列表 central,另一个是管理堆区内存区域的 arenas 以及相关字段。

mheap

mheap-and-memories

内存分配

堆上所有的对象都会通过调用 runtime.newobject 函数分配内存,该函数会调用 runtime.mallocgc 分配指定大小的内存空间,这也是用户程序向堆上申请内存空间的必经函数

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
	mp := acquirem()
	mp.mallocing = 1

	c := gomcache()
	var x unsafe.Pointer
	noscan := typ == nil || typ.ptrdata == 0
	if size <= maxSmallSize {
		if noscan && size < maxTinySize {
			// 微对象分配
		} else {
			// 小对象分配
		}
	} else {
		// 大对象分配
	}

	publicationBarrier()
	mp.mallocing = 0
	releasem(mp)

	return x
}

上述代码使用 runtime.gomcache 获取线程缓存并判断申请内存的类型是否为指针。我们从这个代码片段可以看出 runtime.mallocgc 会根据对象的大小执行不同的分配逻辑,在前面的章节也曾经介绍过运行时根据对象大小将它们分成微对象、小对象和大对象,这里会根据大小选择不同的分配逻辑:

  • 微对象 (0, 16B) — 先使用微型分配器,再依次尝试线程缓存、中心缓存和堆分配内存;
  • 小对象 [16B, 32KB] — 依次尝试使用线程缓存、中心缓存和堆分配内存;
  • 大对象 (32KB, +∞) — 直接在堆上分配内存;

微对象内存分配

Go 语言运行时将小于 16 字节的对象划分为微对象,它会使用线程缓存上的微分配器提高微对象分配的性能,我们主要使用它来分配较小的字符串以及逃逸的临时变量。微分配器可以将多个较小的内存分配请求合入同一个内存块中,只有当内存块中的所有对象都需要被回收时,整片内存才可能被回收。

微分配器管理的对象不可以是指针类型,管理多个对象的内存块大小 maxTinySize 是可以调整的,在默认情况下,内存块的大小为 16 字节。maxTinySize 的值越大,组合多个对象的可能性就越高,内存浪费也就越严重;maxTinySize 越小,内存浪费就会越少,不过无论如何调整,8 的倍数都是一个很好的选择。

tiny-allocator

如上图所示,微分配器已经在 16 字节的内存块中分配了 12 字节的对象,如果下一个待分配的对象小于 4 字节,它会直接使用上述内存块的剩余部分,减少内存碎片,不过该内存块只有所有对象都被标记为垃圾时才会回收。当内存块中不包含空闲的内存时,会先从线程缓存找到跨度类对应的内存管理单元 runtime.mspan,调用 runtime.nextFreeFast 获取空闲的内存;当不存在空闲内存时,我们会调用 runtime.mcache.nextFree 从中心缓存或者页堆中获取可分配的内存块:

小对象内存分配

小对象是指大小为 16 字节到 32,768 字节的对象以及所有小于 16 字节的指针类型的对象,小对象的分配可以被分成以下的三个步骤:

  1. 确定分配对象的大小以及跨度类 runtime.spanClass
  2. 从线程缓存、中心缓存或者堆中获取内存管理单元并从内存管理单元找到空闲的内存空间;
  3. 调用 runtime.memclrNoHeapPointers 清空空闲内存中的所有数据;

大对象内存分配

运行时对于大于 32KB 的大对象会单独处理,我们不会从线程缓存或者中心缓存中获取内存管理单元,而是直接调用 runtime.mcache.allocLarge 分配大片内存,runtime.mcache.allocLarge 会计算分配该对象所需要的页数,按照 8KB 的倍数在堆上申请内存

小结

Go使用的这种内存分配原则,将内存分配的粒度降低,微对象直接从线程缓存中的微内存分配器进行分配,如果微内存没有足够的内存使用,那么就向高一级的线程缓存进行内存申请,如果还不够的话,就向中心缓存区申请,同理,不够的话就向堆内存进行申请,这样做的好处是可以大大加快内存分配的效率,内存分配更快程序也就运行的更快,通过使用TCmalloc直接在线程缓存中进行内存的分配,避免使用锁来导致效率低下,可以说设计的非常巧妙了。

参考文档

Go语言并发编程-内存管理-面向信仰编程