内存分配器

内存空间包含两个重要区域：栈区和堆区。不同编程语言使用不同的方法管理堆区的内存，C++ 等编程语言会由工程师主动申请和释放内存，Go 以及 Java 等编程语言会由工程师和编译器共同管理，堆中的对象由内存分配器分配并由垃圾收集器回收。

设计原理

内存管理一般包含三个不同的组件，分别是用户程序（Mutator）、分配器（Allocator）和收集器（Collector）；当用户程序申请内存时，它会通过内存分配器申请新内存，而分配器会负责从堆中初始化相应的内存区域。

分配方法

线性分配器

使用线性分配器时，只需要在内存中维护一个指向特定位置的指针；用户程序申请内存时，移动指针。然而，这不利于在内存被释放时重用内存。如下图中红色部分难以利用：

因为线性分配器需要与具有拷贝特性的垃圾回收算法配合，所以 C 和 C++ 等需要直接对外暴露指针的语言无法使用该策略。

空闲链表分配器

在内部会维护一个类似链表的数据结构；当用户程序申请内存时，依次遍历空闲的内存块，找到足够大的内存，然后申请新的资源并修改链表，时间复杂度为O(n)，常见策略如下：

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

Go使用的内存分配策略类似第4种。

分级分配

Go 语言的内存分配器借鉴了线程缓存分配（TCMalloc）的设计实现高速的内存分配，它的核心理念是使用多级缓存将对象根据大小分类，并按照类别实施不同的分配策略。对象一共包括3种：

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

多级缓存包括3个组件：线程缓存（Thread Cache）、中心缓存（Central Cache）和页堆（Page Heap）

虚拟内存布局

在 Go 语言 1.10 以前的版本中，堆区的内存空间是连续的，即在启动时初始化整片虚拟内存区域，spans、bitmap 和 arena 区域分别预留了 512MB、16GB 以及 512GB 的内存空间。 然而有以下问题：

  1. 堆大小上限受限(512GB):
  2. C 和 Go 混合使用时易产生地址空间冲突：分配的内存地址会发生冲突，导致堆的初始化和扩容失败；没有被预留的大块内存可能会被分配给 C 语言的二进制，导致扩容后的堆不连续。

在 1.11 版本及以后换用稀疏内存的方案：runtime使用二维的 runtime.heapArena 数组管理所有的内存，每个runtime.heapArena管理 64MB 的内存空间：

在amd64的Linux操作系统上，runtime.heap会持有4,194,304个runtime.heapArena，每个runtime.heapArena管理 64MB 的内存空间，单个Go 语言程序的内存上限也就是 256TB。

1
2
3
4
5
6
7
8
9
10
11
12
type heapArena struct {
    // 位图标识 arena 区域中的那些地址保存了对象：每个字节表示堆区中的32字节是否空闲
	bitmap       [heapArenaBitmapBytes]byte
    // 存储指向内存管理单元 runtime.mspan 的指针
	spans        [pagesPerArena]*mspan
	pageInUse    [pagesPerArena / 8]uint8
	pageMarks    [pagesPerArena / 8]uint8
	pageSpecials [pagesPerArena / 8]uint8
	checkmarks   *checkmarksMap
    // 指向当前 heapArena 管理的内存基地址
	zeroedBase   uintptr
}

bitmap如下： bitmap中一个byte对应4个指针（指针大小为8bit）的内存；bitmap的高地址部分指向arena的低地址部分；

地址空间

Go的runtime构成了操作系统内存管理的抽象层（申请内存最终落到底层OS），抽象层将地址空间分为4种状态：

  1. None：地址空间默认状态，对应内存没有被保留或者映射；
  2. Reserved：runtime持有该内存空间，但访问该内存导致错误；
  3. Prepared：内存被保留，可以快速转到Ready状态（没有对应的物理内存却访问Prepared状态内存的行为是未定义的）；
  4. Ready：可以被安全访问

runtime使用 Linux 提供的 mmap、munmap 和 madvise 等系统调用实现了操作系统的内存管理抽象层，抹平了不同操作系统的差异，提供了更加方便的接口。

内存管理组件

内存管理基本单元runtime.mspan

若干个runtime.mspan组成双向链表；每个runtime.mspan管理npages个大小为8KB的页（这里的页是操作系统内存页的整数倍）

每个mspan按照其对应SpanClass的大小分割成若干个object，每个object可存储一个对象（对象的大小不超过object的大小），并使用一个位图标记object的占用情况。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
type mspan struct {
	next *mspan     // 指向前一个mspan
	prev *mspan     // 指向后一个mspan
	list *mSpanList 
    ...
    // 页与内存：
	startAddr uintptr   // 起始地址
	npages    uintptr   // 页数
	freeindex uintptr   // 扫描页中空闲对象的初始索引

	allocBits  *gcBits  // 标记内存的占用情况
	gcmarkBits *gcBits  // 标记内存的回收情况
	allocCache uint64   // allocBits的补码，用于快速查找内存中未被使用的内存
	...
    // 状态：可能处于 mSpanDead、mSpanInUse、mSpanManual 和 mSpanFree 四种情况
    /*当 runtime.mspan 在空闲堆中，它会处于 mSpanFree 状态；当 runtime.mspan 已经被分配时，它会处于 mSpanInUse、mSpanManual 状态：
        1. 在垃圾回收的任意阶段，可能从 mSpanFree 转换到 mSpanInUse 和 mSpanManual；
        2. 在垃圾回收的清除阶段，可能从 mSpanInUse 和 mSpanManual 转换到 mSpanFree；
        3. 在垃圾回收的标记阶段，不能从 mSpanInUse 和 mSpanManual 转换到 mSpanFree；
    */
    state       mSpanStateBox   // 设置 runtime.mspan 状态的操作必须是原子性的以避免垃圾回收造成的线程竞争问题
    // 跨度类：Go 语言的内存管理模块中一共包含 67 种跨度类（对象大小从 8B 到 32KB），每一个跨度类都会存储特定大小的对象并且包含特定数量的页数以及对象
    spanclass   spanClass
}

线程缓存runtime.mcache：与线程上的处理器一一绑定

每一个工作线程绑定一个mcache，每一个mcache持有68*2个runtime.mspan，存储在alloc字段中，用于缓存用户程序申请的微小对象。 

1
2
3
4
5
6
7
8
9
type mcache struct {
    // 微对象分配器：专门管理16 字节以下的对象
    tiny             uintptr        // 指向堆中的一片内存
	tinyoffset       uintptr        // 下一个空闲内存所在的偏移量
	local_tinyallocs uintptr        // 记录内存分配器中分配的对象个数
    ... 
	alloc [numSpanClasses]*mspan 
}
numSpanClasses = _NumSizeClasses << 1

初始化线程缓存时调用runtime.allocmcache，刚初始化时alloc中的所有runtime.mspan都是空占位符；只有当用户程序申请内存时，才会从上一级组件获取新的 runtime.mspan满足内存分配的需求。

那么如何申请新的runtime.mspan并插入线程内存呢？调用runtime.mcache.refill从中心缓存申请。

1
2
3
4
5
6
func (c *mcache) refill(spc spanClass) {    // 获取指定跨度类的mspan
    // 被替换的单元不能包含空闲的内存空间；获取的单元中需要至少包含一个空闲对象用于分配内存
	s := c.alloc[spc]
	s = mheap_.central[spc].mcentral.cacheSpan()
	c.alloc[spc] = s
}

中心缓存runtime.mcentral

每个中心缓存管理某个跨度类的mspan。 

1
2
3
4
5
type mcentral struct {
	spanclass spanClass
	partial  [2]spanSet     // 包含空闲对象的mspan集合
	full     [2]spanSet     // 不包含空闲对象的mspan集合
}

线程缓存在runtime.mcache.refill中调用runtime.mcentral.cacheSpan方法获取新的mspan，步骤如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func (c *mcentral) cacheSpan() *mspan {
    sg := mheap_.sweepgen
	spanBudget := 100
	// 1. 先从清理过的、包含空闲对象的mspan集合中查找可以使用的mspan
	if s = c.partialSwept(sg).pop(); s != nil {
		goto havespan
	}

	// 2. 再从未被清理过的、包含空闲对象的mspan集合中查找可以使用的mspan
	for ; spanBudget >= 0; spanBudget-- {
		s = c.partialUnswept(sg).pop()
		if s == nil {
			break
		}
		if atomic.Load(&s.sweepgen) == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
            // 找到需要回收的mspan时：触发sweep清理；
			s.sweep(true)
			goto havespan
		}
	}
    // 3. 接着从未被清理过的、不包含空闲对象的mspan集合中获取mspan，通过sweep清理其内存空间
	for ; spanBudget >= 0; spanBudget-- {
		s = c.fullUnswept(sg).pop()
		if s == nil {
			break
		}
		if atomic.Load(&s.sweepgen) == sg-2 && atomic.Cas(&s.sweepgen, sg-2, sg-1) {
			s.sweep(true)
			freeIndex := s.nextFreeIndex()
			if freeIndex != s.nelems {
				s.freeindex = freeIndex
				goto havespan
			}
			c.fullSwept(sg).push(s)
		}
	}
	...
    // 4. 调用grow从堆中申请新的mspan
	s = c.grow()
	if s == nil {
		return nil
	}

havespan:   // s是一个有空闲对象的mspan时跳转到这里：
	freeByteBase := s.freeindex &^ (64 - 1)
	whichByte := freeByteBase / 8
    // 更新  allocBits 和 allocCache 等字段，让runtime在分配内存时能够快速找到空闲对象
    s.refillAllocCache(whichByte)
	s.allocCache >>= s.freeindex % 64

	return s
}

页堆runtime.mheap

mheap代表Go程序持有的所有堆空间，使用一个全局对象_mheap管理堆内存。

当mcentral没有空闲的mspan时，会向mheap申请；mheap没有足够资源时，向操作系统申请新的内存（扩容）。

mheap中含有所有规格的mcentral；所以，当一个mcache从mcentral申请mspan时，只需要在独立的mcentral中使用锁，并不会影响申请其他规格的mspan。 

1
2
3
4
5
6
7
type mheap struct {
    arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
    central [numSpanClasses]struct {    // 全局中心缓存列表
		mcentral mcentral               // 长度为136的中心缓存数组（68 个为跨度类需要 scan 的中心缓存，另外的 68 个是 noscan 的中心缓存）
		pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
	}
}

runtime.mheap通过runtime.mheap.alloc在系统栈中获取新的runtime.span单元：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
func (h *mheap) alloc(npages uintptr, spanclass spanClass, needzero bool) *mspan {
	var s *mspan
	systemstack(func() {
		if h.sweepdone == 0 {
			h.reclaim(npages)       // 1. 先回收
		}
		s = h.allocSpan(npages, false, spanclass, &memstats.heap_inuse)     // 2. 再分配
	})
	...
	return s
}

func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan) {
    gp := getg()
	base, scav := uintptr(0), uintptr(0)
	pp := gp.m.p.ptr()
    // 1. 小内存申请（尝试从处理器缓存获取）：
	if pp != nil && npages < pageCachePages/4 {
		c := &pp.pcache
		base, scav = c.alloc(npages)        // 调用runtime.pageCache.alloc
		if base != 0 {
			s = h.tryAllocMSpan()
			if s != nil && gcBlackenEnabled == 0 && (manual || spanclass.sizeclass() != 0) {
				goto HaveSpan
			}
		}
	}

    // 2. 大内存或缓存不足（从页堆分配）：
	if base == 0 {
		base, scav = h.pages.alloc(npages)  // 通过runtime.pageAlloc.alloc在页堆上申请
        // 3. 页堆内存不足（扩容）
		if base == 0 {
			h.grow(npages)
            base, scav = h.pages.alloc(npages)
            // 3.1 申请到内存：扩容成功
			if base == 0 {
				throw("grew heap, but no adequate free space found")
			}
		}
	}
    // 3.2 没有申请到内存：扩容失败，宿主机可能不存在空闲内存，运行时直接终止当前程序
	if s == nil {
		s = h.allocMSpanLocked()
	}
	...
}

runtime.mheap如何扩容呢？

通过runtime.mheap.grow向操作系统申请更多内存空间：通过传入的页数获取期望分配的内存空间大小以及内存的基地址；如果 arena 区域没有足够的空间，调用runtime.mheap.sysAlloc从操作系统中申请更多的内存。

内存分配runtime.mallocgc

用户程序向堆上申请内存的必经之路：堆上对象调用runtime.newobject函数分配内存，进而调用runtime.mallocgc分配指定大小的内存空间（根据对象的大小执行不同的分配逻辑）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
}
  1. 微对象 (0, 16B)，不可以是指针类型：先使用微型分配器，再依次尝试线程缓存、中心缓存和堆分配内存；
  2. 小对象 [16B, 32KB]：依次尝试使用线程缓存、中心缓存和堆分配内存；
  3. 大对象 (32KB, +∞) ：直接在堆上分配内存。

微对象

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

假设微分配器已经在 16 字节的内存块中分配了 12 字节的对象，如果下一个待分配的对象小于 4 字节，它会直接使用上述内存块的剩余部分，减少内存碎片。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
	...
	if size <= maxSmallSize {
		if noscan && size < maxTinySize {   // 微对象分配
			off := c.tinyoffset
            ...
            // 1. 如果当前块中还包含大小合适的空闲内存：通过基地址和偏移量获取并返回这块内存
			if off+size <= maxTinySize && c.tiny != 0 {
				x = unsafe.Pointer(c.tiny + off)
				c.tinyoffset = off + size
				c.local_tinyallocs++
				releasem(mp)
				return x
			}
			...
            // 2. 内存块中不包含空闲的内存时：
            span = c.alloc[tinySpanClass]
            // 2.1 从线程缓存找到跨度类对应的mspan
			v := nextFreeFast(span)
            // 2.2 不存在空闲内存时：调用nextFree从中心缓存或者页堆中获取可分配的mspan
			if v == 0 {
				v, span, shouldhelpgc = c.nextFree(tinySpanClass)
			}
            // 3. 清空空闲内存中的数据、更新构成微对象分配器的几个字段 tiny 和 tinyoffset 并返回新的空闲内存
			x = unsafe.Pointer(v)
			(*[2]uint64)(x)[0] = 0
			(*[2]uint64)(x)[1] = 0
			if size < c.tinyoffset || c.tiny == 0 {
				c.tiny = uintptr(x)
				c.tinyoffset = size
			}
			size = maxTinySize
		}
		...
	}
	...
}

小对象

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
	...
	if size <= maxSmallSize {
		...
		} else {
            // 1. 确定分配对象的大小，构建跨度类spc；
			var sizeclass uint8
			if size <= smallSizeMax-8 {
				sizeclass = size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]
			} else {
				sizeclass = size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]
			}
			size = uintptr(class_to_size[sizeclass])
			spc := makeSpanClass(sizeclass, noscan)
            // 2. 从线程缓存、中心缓存或者堆中获取mspan，并从mspan找到空闲的内存空间；
			span := c.alloc[spc]
            // 2.1 线程缓存维度：nextFreeFast 利用mspan中的allocCache字段，快速找到该字段为 1 的位数，获取当前位对应的内存空间：
			v := nextFreeFast(span)
            // 2.2 中心缓存维度：从中心缓存申请新的mspan替换线程缓存中已经不存在可用对象的mspan
			if v == 0 {
				v, span, _ = c.nextFree(spc)
			}
			x = unsafe.Pointer(v)
			if needzero && span.needzero != 0 {
				memclrNoHeapPointers(unsafe.Pointer(v), size)
			}
		}
	} else {
		...
	}
	...
	return x
}

大对象

对于大于 32KB 的大对象，直接调用 runtime.mcache.allocLarge 分配大片内存（计算该对象所需的页数，按照 8KB 的倍数在堆上申请内存）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
	...
	if size <= maxSmallSize {
		...
	} else {
		var s *mspan
		span = c.allocLarge(size, needzero, noscan)
		span.freeindex = 1
		span.allocCount = 1
		x = unsafe.Pointer(span.base())
		size = span.elemsize
	}

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

	return x
}

func (c *mcache) allocLarge(size uintptr, needzero bool, noscan bool) *mspan {
	npages := size >> _PageShift
	if size&_PageMask != 0 {
		npages++
	}
	...
	s := mheap_.alloc(npages, spc, needzero)
	mheap_.central[spc].mcentral.fullSwept(mheap_.sweepgen).push(s)
	s.limit = s.base() + size
	heapBitsForAddr(s.base()).initSpan(s)
	return s
}

小结

运行时的内存分配器使用类似 TCMalloc 的分配策略将对象根据大小分类，并设计多层级的组件提高内存分配器的性能。那么TCMalloc的结构是怎样的呢？以后写一节进行分析（画个饼）

参考

Go 语言设计与实现 图解Go语言内存分配