内存分配全局视野

span与元素

Go语言将内存分成了大大小小67个级别的span，其中，0级代表特殊的大对象，其大小是不固定的。当具体的对象需要分配内存时，并不是直接分配span，而是分配不同级别的span中的元素。因此span的级别不是以每个span的大小为依据的，而是以span中元素的大小为依据的。

每个具体的对象在分配时都需要对齐到指定的大小，例如分配17字节的对象，会对应分配到比17字节大并最接近它的元素级别，即第3级，这导致最终分配了32字节。因此，这种分配方式会不可避免地带来内存的浪费。

三级对象管理

为了能够方便地对span进行管理，加速span对象的访问和分配，Go语言采取了三级管理结构，分别为mcache、mcentral、mheap。

mcache

Go语言采用了现代TCMalloc内存分配算法的思想，每个逻辑处理器P都存储了一个本地span缓存，称作mcache。如果协程需要内存可以直接从mcache中获取，由于在同一时间只有一个协程运行在逻辑处理器P上，所以中间不需要加锁。mcache包含所有大小规格的mspan，但是每种规格大小只包含一个。

mcentral

除class0外，mcache的span都来自mcentral。

• mcentral是被所有逻辑处理器P共享的。
• mcentral对象收集所有给定规格大小的span。每个mcentral都包含两个mspan的链表：empty mspanList表示没有空闲对象或span已经被mcache缓存的span链表，nonempty mspanList表示有空闲对象的span链表。

做这种区分是为了更快地分配span到mcache中。除了级别0，每个级别的span都会有一个mcentral用于管理span链表。

mheap

而所有级别的这些mcentral，其实都是一个数组，由mheap进行管理。

1
2
3
4
central [numSpanClasses]struct {
	mcentral mcentral
	pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
}

mheap的作用不只是管理central，大对象也会直接通过mheap进行分配。

mheap实现了对虚拟内存线性地址空间的精准管理，建立了span与具体线性地址空间的联系，保存了分配的位图信息，是管理内存的最核心单元。堆区的内存被分成了HeapArea大小进行管理。对Heap进行的操作必须全局加锁，而mcache、mcentral可以被看作某种形式的缓存。

四级内存块管理

根据对象的大小，Go语言将堆内存分成了图1所示的HeapArea、chunk、span与page 4种内存块进行管理。其中，HeapArea内存块最大，其大小与平台相关，在UNIX 64位操作系统中占据64MB。chunk占据了512KB，span根据级别大小的不同而不同，但必须是page的倍数。而1个page占据8KB。

对象分配

内存分配时，将对象按照大小不同划分为微小（tiny）对象、小对象、大对象。

微小对象

Go语言将小于16字节的对象划分为微小对象。划分微小对象的主要目的是处理极小的字符串和独立的转义变量。

微小对象会被放入class为2的span中，在class为2的span中元素的大小为16字节。首先对微小对象按照2、4、8的规则进行字节对齐。例如，字节为1的元素会被分配2字节，字节为7的元素会被分配8字节。

查看之前分配的元素中是否有空余的空间

如果当前对象要分配8字节，并且正在分配的元素可以容纳8字节，则返回tiny+offset的地址，意味着当前地址往后8字节都是可以被分配的。

分配完成后offset的位置也需要相应增加，为下一次分配做准备。

如果当前要分配的元素空间不够，将尝试从mcache中查找span中下一个可用的元素。因此，tiny分配的第一步是尝试利用分配过的前一个元素的空间，达到节约内存的目的。

mcache缓存位图

在查找空闲元素空间时，首先需要从mcache中找到对应级别的mspan，mspan中拥有allocCache字段，其作为一个位图，用于标记span中的元素是否被分配。由于allocCache元素为uint64，因此其最多一次缓存64字节。

allocCache使用小端模式标记span中的元素是否被分配。allocCache中的最后1 bit对应的是span中的第1个元素是否被分配。当bit位为1时代表当前对应的span中的元素已经被分配。

span中元素的个数大于64，因此需要专门有一个字段freeindex标识当前span中的元素被分配到了哪里。

span中小于freeindex序号的元素都已经被分配了，将从freeindex开始继续分配。

因此，只要从allocCache开始找到哪一位为0即可。假如X位为0，那么X+freeindex为当前span中可用的元素序号。当allocCache中的bit位全部被标记为1后，需要移动freeindex，并更新allocCache，一直到span中元素的末尾为止。

mcentral遍历span

如果当前的span中没有可以使用的元素，这时就需要从mcentral中加锁查找。mcentral中有两种类型的span链表，分别是有空闲元素的nonempty链表和没有空闲元素的empty链表。在mcentral查找时，会分别遍历这两个链表，查找是否有可用的span。

没有空闲元素的empty链表可能有些span虽然被垃圾回收器标记为空闲了，但是还没有来得及清理，这些span在清扫后仍然是可以使用的，因此需要遍历。

如果在mcentral中查找到有空闲元素的span，则将其赋值到mcache中，并更新allocCache，同时需要将span添加到mcentral的empty链表中去。

mheap缓存查找

如果在mcentral中找不到可以使用的span，就需要在mheap中查找。Go 1.12采用treap结构进行内存管理，treap是一种引入了随机数的二叉搜索树，其实现简单，引入的随机数及必要时的旋转保证了比较好的平衡性。由于这棵树是mheap管理的，所以在操作它时需要维持一个lock。这在密集的对象分配及逻辑处理器P过多时，会导致更长的等待时间。 在Go 1.14之后，用bitmap来管理内存页，每个逻辑处理器P中都维护了一份page cache。

1
2
3
4
5
type pageCache struct {
	base  uintptr // base address of the chunk
	cache uint64  // 64-bit bitmap representing free pages (1 means free)
	scav  uint64  // 64-bit bitmap representing scavenged pages (1 means scavenged)
}

mheap会首先查找每个逻辑处理器P中pageCache字段的cache。

cache也是一个位图，每一位都代表了一个page（8KB）。由于cache为uint64，因此一共可以提供64×8=512KB的连续虚拟内存。在cache中，1代表未分配的内存，0代表已分配的内存。base代表该虚拟内存的基地址。当需要分配的内存小于512/4=128KB时，需要首先从cache中分配。

例如要分配n pages，就需要查找cache中是否有连续n个为1的位。如果存在，则说明在缓存中查找到了合适的内存，用于构建span。

mheap基数树查找

如果要分配的page过大或者在逻辑处理器P的cache中没有找到可用的page，就需要对mheap加锁，并在整个mheap管理的虚拟地址空间的位图中查找是否有可用的page。

管理线性地址空间的位图结构叫作基数树（radix tree）

该结构和一般的基数树结构不太一样，会有这个名字很大一部分是由于父节点包含了子节点的若干信息。

该树中的每个节点都对应一个pallocSum，最底层的叶子节点对应的pallocSum包含一个chunk的信息（512×8KB），除叶子节点外的节点都包含连续8个子节点的内存信息。

pallocSum是一个简单的uint64，分为开头（start）、中间（max）、末尾（end）3部分。

pallocSum的开头与末尾部分各占21bit，中间部分占22bit，它们分别包含了这个区域中连续空闲内存页的信息，包括开头有多少连续内存页，最多有多少连续内存页，末尾有多少连续内存页。对于最顶层的节点，由于其max位为22bit，因此一棵完整的基数树最多代表221 pages=16GB内存。

不需要每一次查找都从根节点开始。在Go语言中，存储了一个特别的字段searchAddr，顾名思义是用于搜索可用内存的。

searchAddr有一个重要的设定是它前面的地址一定是已经分配过的，因此在查找时，只需要向searchAddr地址的后方查找即可跳过已经查找的节点，减少查找的时间。

在第1次查找时，会从当前searchAddr的chunk块中查找是否有对应大小的连续空间，这种优化主要针对比较小的内存（至少小于512KB）分配。Go语言对于内存有非常精细的管理，chunk块的每个page（8 KB）都有位图表明其是否已经被分配。

每个chunk都有一个pallocData结构，其中pallocBits管理其分配的位图。pallocBits是uint64，有8字节，由于其每一位对应一个page，因此pallocBits一共对应64×8=512KB，恰好是一个chunk块的大小。位图的对应方式和之前是一样的。

1
2
3
4
5
6
type pageBits [pallocChunkPages / 64]uint64
type pallocBits pageBits
type pallocData struct {
	pallocBits
	scavenged pageBits
}

而所有的chunk pallocData都在pageAlloc结构中进行管理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
type pageAlloc struct {
	summary [summaryLevels][]pallocSum
	chunks [1 << pallocChunksL1Bits]*[1 << pallocChunksL2Bits]pallocData
	searchAddr offAddr
	start, end chunkIdx
	inUse addrRanges
	scav struct {
		lock mutex
		inUse addrRanges
		gen uint32
		reservationBytes uintptr
		released uintptr
		scavLWM offAddr
		freeHWM offAddr
	}
	mheapLock *mutex
	sysStat *sysMemStat
	test bool
}

当内存分配过大或者当前chunk块没有连续的npages空间时，需要到基数树中从上到下进行查找。基数树有一个特性——要分配的内存越大，它能够越快地查找到当前的基数树中是否有连续的满足需求的空间。

在查找基数树的过程中，需要从上到下、从左到右地查找每个节点是否符合要求。先计算pallocSum的开头有多少连续的内存空间，如果大于或等于npages，则说明找到了可用的空间和地址。如果小于npages，则会计算pallocSum字段的max，即中间有多少连续的内存空间。如果max大于或等于npages，那么需要继续向基数树当前节点对应的下一级查找，原因在于，max大于npages，表明当前一定有连续的空间大于或等于npages，但是并不知道具体在哪一个位置，必须查找下一级才能找到可用的地址。如果max也不满足，有可能两个节点可以合并起来组成一个更大的连续空间。因此还需要将当前pallocSum计算的end与后一个节点的start加起来查看是否能够组合成大于npages的连续空间。

每一次从基数树中查找到内存，或者事后从操作系统分配到内存时，都需要更新基数树中每个节点的pallocSum。

操作系统内存申请

当在基数树中查找不到可用的连续内存时，需要从操作系统中获取内存。从操作系统获取内存的代码是平台独立的，例如在UNIX操作系统中，最终使用了mmap系统调用向操作系统申请内存。

1
2
3
4
5
6
7
func sysReserve(v unsafe.Pointer, n uintptr) unsafe.Pointer {
	p, err := mmap(v, n, _PROT_NONE, _MAP_ANON|_MAP_PRIVATE, -1, 0)
	if err != 0 {
		return nil
	}
	return p
}

Go语言规定，每一次向操作系统申请的内存大小必须为heapArena的倍数。heapArena是和平台有关的内存大小，在64位UNIX操作系统中，其大小为64MB。这意味着即便需要的内存很小，最终也至少要向操作系统申请64MB内存。多申请的内存可以用于下次分配。

Go语言中对于heapArena有精准的管理，精准到每个指针大小的内存信息，每个page对应的mspan信息都有记录。

1
2
3
4
5
6
7
8
9
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
}

小对象分配

当对象不属于微小对象时，在内存分配时会继续判断其是否为小对象，小对象指小于32KB的对象。Go语言会计算小对象对应哪一个等级的span，并在指定等级的span中查找。

此后和微小对象的分配一样，小对象分配经历mcache→mcentral→mheap位图查找→mheap基数树查找→操作系统分配的过程。

大对象分配

大对象指大于32KB的对象，内存分配时不与mcache和mcentral沟通，直接通过mheap进行分配。大对象分配经历mheap基数树查找→操作系统分配的过程。每个大对象都是一个特殊的span，其class为0。

• Previous
  Golang并发控制
• Next
  Golang反射