7.1 内存分配器

程序中的数据和变量都会被分配到程序所在的虚拟内存中，内存空间包含两个重要区域：

• 栈区（Stack） 函数调用的参数、返回值以及局部变量大都会被分配到栈上，这部分内存会由编译器进行管理
• 堆区（Heap） 堆中的对象由内存分配器分配并由垃圾收集器回收

7.1.1 设计原理

内存管理一般包含三个不同的组件：

1. 用户程序（Mutator）
2. 分配器（Allocator）
3. 收集器（Collector）

当用户程序申请内存时，它会通过内存分配器申请新内存，而分配器会负责从堆中初始化相应的内存区域。

mutator-allocator-collector

分配方法

编程语言的内存分配器一般包含两种分配方法：

1. 线性分配器（Sequential Allocator，Bump Allocator）
2. 空闲链表分配器（Free-List Allocator）

线性分配器

使用线性分配器时，只需要在内存中维护一个指向内存特定位置的指针，如果用户程序向分配器申请内存，分配器只需要检查剩余的空闲内存、返回分配的内存区域并修改指针在内存中的位置，即移动下图中的指针：

bump-allocator

虽然线性分配器实现为它带来了较快的执行速度以及较低的实现复杂度，但是线性分配器无法在内存被释放时重用内存。

如下图所示，如果已经分配的内存被回收，线性分配器无法重新利用红色的内存：

bump-allocator-reclaim-memory

因为线性分配器具有上述特性，所以需要与合适的垃圾回收算法配合使用，如：

• 标记压缩（Mark-Compact）
• 复制回收（Copying GC）
• 分代回收（Generational GC）
• ...

空闲链表分配器

空闲链表分配器（Free-List Allocator）可以重用已经被释放的内存，它在内部会维护一个类似链表的数据结构。

当用户程序申请内存时，空闲链表分配器会依次遍历空闲的内存块，找到足够大的内存，然后申请新的资源并修改链表：

free-list-allocator

因为不同的内存块通过指针构成了链表，所以使用这种方式的分配器可以重新利用回收的资源。

但是因为分配内存时需要遍历链表，所以它的时间复杂度是 O(n)。

空闲链表分配器可以选择不同的策略在链表中的内存块中进行选择，最常见的是以下四种：

1. 首次适应（First-Fit）— 从链表头开始遍历，选择第一个大小大于申请内存的内存块；
2. 循环首次适应（Next-Fit）— 从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块；
3. 最优适应（Best-Fit）— 从链表头遍历整个链表，选择最合适的内存块；
4. （Segregated-Fit）— 将内存分割成多个链表，每个链表中的内存块大小相同，申请内存时先找到满足条件的链表，再从链表中选择合适的内存块；

segregated-list

隔离适应策略会将内存分割成由 4、8、16、32 字节的内存块组成的链表，向内存分配器申请 8 字节的内存时，它会在上图中找到满足条件的空闲内存块并返回。

隔离适应的分配策略减少了需要遍历的内存块数量，提高了内存分配的效率。

分级分配

线程缓存分配（Thread-Caching Malloc，TCMalloc）是用于分配内存的机制，核心理念是使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略。

对象大小

Go 语言的内存分配器会根据申请分配的内存大小选择不同的处理逻辑，运行时根据对象的大小将对象分成微对象、小对象和大对象三种：

1. 微对象：(0, 16B)
2. 小对象：[16B, 32KB]
3. 大对象：(32KB, +∞)

因为程序中的绝大多数对象的大小都在 32KB 以下，而申请的内存大小影响 Go 语言运行时分配内存的过程和开销，所以分别处理大对象和小对象有利于提高内存分配器的性能。

多级缓存

内存分配器会将内存分成不同的级别分别管理，Go 运行时分配器都会引入三个组件分级管理内存：

1. 线程缓存（Thread Cache） 线程缓存属于每一个独立的线程，它能够满足线程上绝大多数的内存分配需求
2. 中心缓存（Central Cache） 当线程缓存不能满足需求时，运行时会使用中心缓存作为补充解决小对象的内存分配
3. 页堆（Page Heap） 遇到 32KB 以上的对象时，内存分配器会选择页堆直接分配大内存

multi-level-cache

虚拟内存布局

• 1.10 以前，堆区的内存空间都是连续的
• 1.11 ，使用稀疏的堆内存空间替代了连续的内存

线性内存

启动时会初始化整片虚拟内存区域：

1. spans：512MB 存储了指向内存管理单元 runtime.mspan 的指针，每个内存单元会管理几页的内存空间，每页大小为 8KB
2. bitmap：16GB 用于标识 arena 区域中的那些地址保存了对象，位图中的每个字节都会表示堆区中的 32 字节是否空闲
3. arena：512GB 真正的堆区，运行时会将 8KB 看做一页，这些内存页中存储了所有在堆上初始化的对象

heap-before-go-1-10

这种设计虽然简单并且方便，但是在 C 和 Go 混合使用时会导致程序崩溃：

1. 分配的内存地址会发生冲突，导致堆的初始化和扩容失败
2. 没有被预留的大块内存可能会被分配给 C 语言的二进制，导致扩容后的堆不连续

线性的堆内存需要预留大块的内存空间，但是申请大块的内存空间而不使用是不切实际的，不预留内存空间却会在特殊场景下造成程序崩溃。

稀疏内存

使用稀疏的内存布局不仅能移除堆大小的上限，还能解决 C 和 Go 混合使用时的地址空间冲突问题。

heap-after-go-1-11

运行时使用二维的 runtime.heapArena 数组管理所有的内存，每个单元都会管理 64MB 的内存空间：

type heapArena struct {
	bitmap       [heapArenaBitmapBytes]byte
	spans        [pagesPerArena]*mspan
	pageInUse    [pagesPerArena / 8]uint8
	pageMarks    [pagesPerArena / 8]uint8
	pageSpecials [pagesPerArena / 8]uint8
	checkmarks   *checkmarksMap
	zeroedBase   uintptr
}

• bitmap 和 spans 与线性内存中的 bitmap 和 spans 区域对应
• zeroedBase 字段指向了该结构体管理的内存的基地址

上述设计将原有的连续大内存切分成稀疏的小内存，而用于管理这些内存的元信息也被切成了小块。

地址空间

所有的内存最终都是要从操作系统中申请的，所以 Go 语言的运行时构建了操作系统的内存管理抽象层，该抽象层将运行时管理的地址空间分成以下四种状态：

状态	解释
None	内存没有被保留或者映射，是地址空间的默认状态
Reserved	运行时持有该地址空间，但是访问该内存会导致错误
Prepared	内存被保留，一般没有对应的物理内存访问该片内存的行为是未定义的可以快速转换到 Ready 状态
Ready	可以被安全访问

每个不同的操作系统都会包含一组用于管理内存的特定方法，这些方法可以让内存地址空间在不同的状态之间转换，可以通过下图了解不同状态之间的转换过程：

memory-regions-states-and-transitions

运行时中包含多个操作系统实现的状态转换方法，所有的实现都包含在以 mem_ 开头的文件中。

7.1.2 内存管理组件

Go 语言的内存分配器包含：

1. 内存管理单元
2. 线程缓存
3. 中心缓存
4. 页堆

go-memory-layout

Go 语言程序都会在启动时初始化如上图所示的内存布局，每一个处理器 P 都会分配一个线程缓存 runtime.mcache 用于处理微对象和小对象的分配，它们会持有内存管理单元 runtime.mspan。

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

内存管理单元

runtime.mspan 是 Go 语言内存管理的基本单元：

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

• next 和 prev 两个字段，分别指向了前一个和后一个 runtime.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
	...
}

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

runtime.mspan 会以两种不同的视角看待管理的内存，当结构体管理的内存不足时，运行时会以页为单位向堆申请内存：

mspan-and-pages

当用户程序或者线程向 runtime.mspan 申请内存时，它会使用 allocCache 字段以对象为单位在管理的内存中快速查找待分配的空间：

mspan-and-objects

如果能在内存中找到空闲的内存单元会直接返回，当内存中不包含空闲的内存时，上一级的组件 runtime.mcache 会为调用 runtime.mcache.refill 更新内存管理单元以满足为更多对象分配内存的需求。

状态

运行时会使用 runtime.mSpanStateBox 存储内存管理单元的状态 runtime.mSpanState：

type mspan struct {
	...
	state       mSpanStateBox
	...
}

该状态可能处于四种情况：

1. mSpanDead
2. mSpanInUse
3. mSpanManual
4. mSpanFree

当 runtime.mspan 在空闲堆中，它会处于 mSpanFree 状态；当 runtime.mspan 已经被分配时，它会处于 mSpanInUse、mSpanManual 状态，运行时会遵循下面的规则转换该状态：

• 在垃圾回收的任意阶段，可能从 mSpanFree 转换到 mSpanInUse 和 mSpanManual；
• 在垃圾回收的清除阶段，可能从 mSpanInUse 和 mSpanManual 转换到 mSpanFree；
• 在垃圾回收的标记阶段，不能从 mSpanInUse 和 mSpanManual 转换到 mSpanFree；

设置 runtime.mspan 状态的操作必须是原子性的以避免垃圾回收造成的线程竞争问题。

跨度类

runtime.spanClass 是 runtime.mspan 的跨度类，它决定了内存管理单元中存储的对象大小和个数：

type mspan struct {
	...
	spanclass   spanClass
	...
}

Go 语言的内存管理模块中一共包含 67 种跨度类，每一个跨度类都会存储特定大小的对象并且包含特定数量的页数以及对象，所有的数据都会被预选计算好并存储在 runtime.class_to_size 和 runtime.class_to_allocnpages 等变量中。

mspan-max-waste-memory

线程缓存

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

mcache-and-mspans

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

初始化

运行时在初始化处理器时会调用 runtime.allocmcache 初始化线程缓存，该函数会在系统栈中使用 runtime.mheap 中的线程缓存分配器初始化新的 runtime.mcache 结构体：

func allocmcache() *mcache {
	var c *mcache
	systemstack(func() {
		lock(&mheap_.lock)
		c = (*mcache)(mheap_.cachealloc.alloc())
		c.flushGen = mheap_.sweepgen
		unlock(&mheap_.lock)
	})
	for i := range c.alloc {
		c.alloc[i] = &emptymspan
	}
	c.nextSample = nextSample()
	return c
}

初始化后的 runtime.mcache 中的所有 runtime.mspan 都是空的占位符 emptymspan。

替换

runtime.mcache.refill 会为线程缓存获取一个指定跨度类的内存管理单元，被替换的单元不能包含空闲的内存空间，而获取的单元中需要至少包含一个空闲对象用于分配内存：

func (c *mcache) refill(spc spanClass) {
	s := c.alloc[spc]
	s = mheap_.central[spc].mcentral.cacheSpan()
	c.alloc[spc] = s
}

该方法会从中心缓存中申请新的 runtime.mspan 存储到线程缓存中，这也是向线程缓存插入内存管理单元的唯一方法。

微分配器

线程缓存中还包含几个用于分配微对象的字段，下面的这三个字段组成了微对象分配器，专门管理 16 字节以下的对象：

type mcache struct {
	tiny             uintptr
	tinyoffset       uintptr
	local_tinyallocs uintptr
}

微分配器只会用于分配非指针类型的内存，上述三个字段中 tiny 会指向堆中的一片内存，tinyOffset 是下一个空闲内存所在的偏移量，最后的 local_tinyallocs 会记录内存分配器中分配的对象个数。

中心缓存

runtime.mcentral 是内存分配器的中心缓存，与线程缓存不同，访问中心缓存中的内存管理单元需要使用互斥锁：

type mcentral struct {
	spanclass spanClass
	partial  [2]spanSet
	full     [2]spanSet
}

每个中心缓存都会管理某个跨度类的内存管理单元，它会同时持有两个 runtime.spanSet，分别存储包含空闲对象和不包含空闲对象的内存管理单元。

内存管理单元

线程缓存会通过中心缓存的 runtime.mcentral.cacheSpan 方法获取新的内存管理单元，可以将其分成以下几个部分：

1. 调用 runtime.mcentral.partialSwept 从清理过的、包含空闲空间的 runtime.spanSet 结构中查找可以使用的内存管理单元；
2. 调用 runtime.mcentral.partialUnswept 从未被清理过的、有空闲对象的 runtime.spanSet 结构中查找可以使用的内存管理单元；
3. 调用 runtime.mcentral.fullUnswept 获取未被清理的、不包含空闲空间的 runtime.spanSet 中获取内存管理单元并通过 runtime.mspan.sweep 清理它的内存空间；
4. 调用 runtime.mcentral.grow 从堆中申请新的内存管理单元；
5. 更新内存管理单元的 allocCache 等字段帮助快速分配内存；

扩容

中心缓存的扩容方法 runtime.mcentral.grow 会根据预先计算的 class_to_allocnpages 和 class_to_size 获取待分配的页数以及跨度类并调用 runtime.mheap.alloc 获取新的 runtime.mspan 结构：

func (c *mcentral) grow() *mspan {
	npages := uintptr(class_to_allocnpages[c.spanclass.sizeclass()])
	size := uintptr(class_to_size[c.spanclass.sizeclass()])

	s := mheap_.alloc(npages, c.spanclass, true)
	if s == nil {
		return nil
	}

	n := (npages << _PageShift) >> s.divShift * uintptr(s.divMul) >> s.divShift2
	s.limit = s.base() + size*n
	heapBitsForAddr(s.base()).initSpan(s)
	return s
}

获取了 runtime.mspan 后，会在上述方法中初始化 limit 字段并清除该结构在堆上对应的位图。

页堆

runtime.mheap 是内存分配的核心结构体，Go 语言程序会将其作为全局变量存储，而堆上初始化的所有对象都由该结构体统一管理。

结构体中包含两组非常重要的字段：

• 全局的中心缓存列表 central
• 管理堆区内存区域的 arenas 以及相关字段

页堆中包含一个长度为 136 的 runtime.mcentral 数组，其中 68 个为跨度类需要 scan 的中心缓存，另外的 68 个是 noscan 的中心缓存：

mheap-and-mcentrals

mheap-and-memories

初始化

堆区的初始化会使用 runtime.mheap.init 方法，其中初始化的两类变量比较重要：

1. spanalloc、cachealloc 以及 arenaHintAlloc 等 runtime.fixalloc 类型的空闲链表分配器
2. central 切片中 runtime.mcentral 类型的中心缓存

func (h *mheap) init() {
	h.spanalloc.init(unsafe.Sizeof(mspan{}), recordspan, unsafe.Pointer(h), &memstats.mspan_sys)
	h.cachealloc.init(unsafe.Sizeof(mcache{}), nil, nil, &memstats.mcache_sys)
	h.specialfinalizeralloc.init(unsafe.Sizeof(specialfinalizer{}), nil, nil, &memstats.other_sys)
	h.specialprofilealloc.init(unsafe.Sizeof(specialprofile{}), nil, nil, &memstats.other_sys)
	h.arenaHintAlloc.init(unsafe.Sizeof(arenaHint{}), nil, nil, &memstats.other_sys)

	h.spanalloc.zero = false

	for i := range h.central {
		h.central[i].mcentral.init(spanClass(i))
	}

	h.pages.init(&h.lock, &memstats.gc_sys)
}

堆中初始化的多个空闲链表分配器与设计原理中提到的分配器没有太多区别，当调用 runtime.fixalloc.init 初始化分配器时，需要传入待初始化的结构体大小等信息，这会帮助分配器分割待分配的内存，它提供了以下两个用于分配和释放内存的方法：

1. runtime.fixalloc.alloc — 获取下一个空闲的内存空间；
2. runtime.fixalloc.free — 释放指针指向的内存空间；

除了这些空闲链表分配器之外，还会在该方法中初始化所有的中心缓存，这些中心缓存会维护全局的内存管理单元，各个线程会通过中心缓存获取新的内存单元。

内存管理单元

runtime.mheap 是内存分配器中的核心组件，运行时会通过它的 runtime.mheap.alloc 方法在系统栈中获取新的 runtime.mspan 单元：

func (h *mheap) alloc(npages uintptr, spanclass spanClass, needzero bool) *mspan {
	var s *mspan
	systemstack(func() {
		if h.sweepdone == 0 {
			h.reclaim(npages)
		}
		s = h.allocSpan(npages, false, spanclass, &memstats.heap_inuse)
	})
	...
	return s
}

为了阻止内存的大量占用和堆的增长，我们在分配对应页数的内存前需要先调用 runtime.mheap.reclaim 方法回收一部分内存，随后运行时通过 runtime.mheap.allocSpan 分配新的内存管理单元，我们会将该方法的执行过程拆分成两个部分：

1. 从堆上分配新的内存页和内存管理单元 runtime.mspan；
2. 初始化内存管理单元并将其加入 runtime.mheap 持有内存单元列表；

扩容

runtime.mheap.grow 会向操作系统申请更多的内存空间，传入的页数经过对齐可以得到期望的内存大小，可以将该方法的执行过程分成以下几个部分：

1. 通过传入的页数获取期望分配的内存空间大小以及内存的基地址；
2. 如果 arena 区域没有足够的空间，调用 runtime.mheap.sysAlloc 从操作系统中申请更多的内存；
3. 扩容 runtime.mheap 持有的 arena 区域并更新页分配器的元信息；
4. 在某些场景下，调用 runtime.pageAlloc.scavenge 回收不再使用的空闲内存页；

7.1.3 内存分配

堆上所有的对象都会通过调用 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 会根据对象的大小执行不同的分配逻辑：

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

微对象

微对象是小于 16 字节的对象，使用线程缓存上的微分配器提高微对象分配的性能，主要使用它来分配较小的字符串以及逃逸的临时变量。

微分配器可以将多个较小的内存分配请求合入同一个内存块中，只有当内存块中的所有对象都需要被回收时，整片内存才可能被回收。

微分配器管理的对象不可以是指针类型，管理多个对象的内存块大小 maxTinySize 是可以调整的，在默认情况下，内存块的大小为 16 字节：

• maxTinySize 的值越大，组合多个对象的可能性就越高，内存浪费也就越严重

• maxTinySize 越小，内存浪费就会越少

tiny-allocator

如上图所示，微分配器已经在 16 字节的内存块中分配了 12 字节的对象，如果下一个待分配的对象小于 4 字节，它会直接使用上述内存块的剩余部分，减少内存碎片，不过该内存块只有所有对象都被标记为垃圾时才会回收。

小对象

小对象是指大小为 16 字节到 32,768 字节的对象以及所有小于 16 字节的指针类型的对象。

小对象的分配可以被分成以下的三个步骤：

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

大对象

运行时对于大于 32KB 的大对象会单独处理，直接调用 runtime.mcache.allocLarge 分配大片内存。

Reference

1. https://draveness.me/golang/docs/part3-runtime/ch07-memory/golang-memory-allocator/