Go-知识内存分配

在c语言中，malloc方法用于动态申请内存，其中内存分配器使用的是glibc提供的ptmalloc2。除了glibc，业界比较出名的内存分配器有Google的tcmalloc和Facebook的jemalloc，
二者在避免内存碎片和性能上均比glibc有比较大的优势，在多线程环境中效果更明显。
Go语言也实现了内存分配器，原理与tcmalloc类似，简单说就是维护一块大的全局内存，每个线程(Go中为处理器P)维护一块小的私有内存，私有内存不足时，再从全局申请。

1. 基础概念

为了方便自主管理内存，一般做法是先向系统申请一块内存，然后将内存切割成小块，通过一定的内存分配算法管理内存。
以64位系统为例，Go程序启动时向系统申请的内存：

预申请的内存划分为：spans，bitmap 和 arena 三部分。其中 arena 即所谓的堆区，应用中需要的内存从这里分配，spans 和 bitmap 是为了管理 arena 区而存在的。
arena 的大小为512GB，为了方便管理，把 arena 区域划分成一个个的 page ，每个 page 的大小为 8KB，一共有 512GB/8KB 个 page。
spans 区域存放 span 的指针，每个指针对应一个或多个 page ，所以 span 区域的大小为 (512GB/8KB) * 指针大小(8byte) = 512 MB。
bitmap 区域的大小也是通过 arena 计算出来的，主要用于GC。

2. span

span 是用于管理 arena 的 page 的关键数据，每个 span 中包含一个或多个连续的 page 。 为了满足小对象分配，会将 span 中的一个 page 划分为更小的粒度，而对于大对象比如超过 page 大小，则通过多个 page 实现。

• a. class

根据对象大小，划分了一系列 class ，每个 class 都代表一个固定大小的对象，以及每个 span 的大小。
在 runtime/sizeclass.go 中有说明:

每列的含义：

• class: class ID ，每个 span 结构中都有一个class ID，表示该 span 可处理的对象类型
• bytes/obj: 该 class 代表对象的字节数
• bytes/span: 每个 span 占用堆的字节数，即 page 数 * page 大小
• objects: 每个 span 可分配的对象个数，即 (bytes/spans) / (bytes/obj)
• waste bytes: 每个 span 产生的内存碎片，即(bytes/spans) % (bytes/obj)

上面最大的对象的大小是32KB，超过32KB大小的对象由特殊的 class 表示，该 class ID 为0，每个 class 只包含一个对象。

• b. span 的数据结构

span 是内存管理的基本单位，每个 span 用于管理特定的 class 对象，根据对象大小， span 将一个或多个 page 拆分成多个块进行管理。
在 runtime/mheap.go中定义了 span 的数据结构：

type mspan struct {
	next       *mspan    // 链表前向指针
	prev       *mspan    // 链表后继指针
	startAddr  uintptr   // 起始地址，即锁管理 page 的地址
	npages     uintptr   // 管理的 page 数
	nelems     uintptr   // 块个数，即有多少个块可供分配
	allocBits  *gcBits   // 分配位图，每一位代表一个块是否已分配
	allocCount uint16    // 已分配块的个数
	spanclass  spanClass // class 表中的 class ID
	elemsize   uintptr   // class 表中的对象大小，即块大小
}

以 class 10 为例， span 和管理的内存：

spanclass 为 10， 参照 class 表可得出 npages=1,nelems=56,elemsize=144。 其中 startAddr 是在 span 初始化时就指定了某个 page 的地址。
allocBits 指向一个位图，每位代表一个块是否被分配。
next 和 prev 用于将多个 span 连接起来，方便管理多个 span 。

3 cache

有了管理内存的基本单位 span ，还需要有一个数据结构来管理 span ，这个数据结构是 mcentral ，各个线程需要内存时，从 mcentral 管理的 span 中申请内存，为了避免多线程申请内存时不断加锁，Go 为每个线程分配了 span 的缓存，这个缓存就是 cache 。
在runtime/mcache.go中定义了 cache 的数据结构：

type mcache struct{
    alloc [68*2] *mspan // 按 class 分组的 mspan 列表
}

alloc 为 mspan 的指针数组，数组大小为 class 总数的 2 倍。数组中的每个元素代表一种 class 类型的 span 列表，每种 class 类型都有两组 span 列表，第一组列表中所表示的对象包含了指针，
第二组列表中所表示的对象不包含指针，这么做是为了提高GC扫描性能，对于不包含指针的 span 列表，没必要去扫描。
根据对象是否包含指针，将对象分为 noscan 和 scan 两类，其中 noscan 代表没有指针，而 scan 则代表有指针，需要GC进行扫描。

cache 在初始化时是没有任何 span 的，在使用过程中会动态从 central 中获取并缓存下来，根据使用情况，每种 class 的 span 个数也不相同。
如上图所示， class0 的 span 数比 class1 的要多，说明本线程中分配的小对象要多一些。

4. central

cache 作为线程的私有资源为单个线程服务，而 central 则是全局资源，为多个线程服务，当某个线程的内存不足时会向 central 申请，当某个线程释放内存时，又会回收进 central 。
在runtime/mcentral.go中定义了 central 的数据结构：

type mcentral struct {
	spanclass uint8 // span class id
	partial [2]spanSet // 有空闲的 span 列表
	full    [2]spanSet // 没有空闲的 span 列表
}

其中的 spanSet 为：

type spanSet struct {
	spineLock mutex // 互斥锁
	spine     unsafe.Pointer // *[N]*spanSetBlock, accessed atomically
	spineLen  uintptr        // Spine array length, accessed atomically
	spineCap  uintptr        // Spine array cap, accessed under lock
	index headTailIndex // 长度
}

spanclass: 每个 mcentral 管理一组有相同 class 的 span 列表
partial: 指还有内存可用的 span 列表
full: 指没有内存可用的 span 列表
spineLock: 互斥锁，防止多线程读写冲突
spine: 内存地址
spineLen: 内存长度
spineCap: 内存最大值

线程从 central 中获取 span 的步骤：

func (c *mcentral) cacheSpan() *mspan {
	spanBytes := uintptr(class_to_allocnpages[c.spanclass.sizeclass()]) * _PageSize
	deductSweepCredit(spanBytes, 0)
	traceDone := false
	if trace.enabled {
		traceGCSweepStart()
	}
	spanBudget := 100
	var s *mspan
	// 创建锁
	sl := newSweepLocker()
	sg := sl.sweepGen
	// 尝试从 有空闲 的 span 列表中拿一个
	if s = c.partialSwept(sg).pop(); s != nil {
	    // 从 有空闲 的  span 列表中成功拿到了
		goto havespan
	}
	for ; spanBudget >= 0; spanBudget-- {
	    // 尝试从 有空闲 的 span 列表中倒序拿
		s = c.partialUnswept(sg).pop()
		if s == nil {
		    // 没有拿到
			break
		}
		// 尝试加锁
		if s, ok := sl.tryAcquire(s); ok {
			// 加锁成功
			s.sweep(true)
			// 解锁
			sl.dispose()
			// 创建
			goto havespan
		}
	}
	for ; spanBudget >= 0; spanBudget-- {
	    // 尝试从 没有空闲的 span 列表中回收一个 span
		s = c.fullUnswept(sg).pop()
		if s == nil {
			break
		}
		if s, ok := sl.tryAcquire(s); ok {
		    // 加锁成功
			s.sweep(true)
			// 获取空闲的 span
			freeIndex := s.nextFreeIndex()
			if freeIndex != s.nelems {
				s.freeindex = freeIndex
				sl.dispose()
				goto havespan
			}
			// 将 span 放到 没有空闲的列表中  
			c.fullSwept(sg).push(s.mspan)
		}
	}
	sl.dispose()
	if trace.enabled {
	    // 尝试 GC 
		traceGCSweepDone()
		traceDone = true
	}
	s = c.grow()
	if s == nil {
	    // 没有 span 
		return nil
	}
havespan:
	if trace.enabled && !traceDone {
		traceGCSweepDone()
	}
	n := int(s.nelems) - int(s.allocCount)
	if n == 0 || s.freeindex == s.nelems || uintptr(s.allocCount) == s.nelems {
	    // 无法在获取 span 了，也就是没有内存了
		throw("span has no free objects")
	}
	freeByteBase := s.freeindex &^ (64 - 1)
	whichByte := freeByteBase / 8
	// 申请内存
	s.refillAllocCache(whichByte)
	s.allocCache >>= s.freeindex % 64
	// 缓存并返回
	return s
}

加锁
从 partial 列表获取一个可用 span ，并将其从列表删除
将取出的 span 放入 full 列表
将 span 返回给线程
解锁
线程将 span 缓存到 cache

线程将 span 归还的步骤：

func (c *mcentral) uncacheSpan(s *mspan) {
    // 没有 span 可以释放
	if s.allocCount == 0 {
		throw("uncaching span but s.allocCount == 0")
	}
	// 锁
	sg := mheap_.sweepgen
	stale := s.sweepgen == sg+1
	if stale {
		atomic.Store(&s.sweepgen, sg-1)
	} else {
		atomic.Store(&s.sweepgen, sg)
	}
	if stale {
	    // 加锁
		ss := sweepLocked{s}
		ss.sweep(false)
	} else {
		if int(s.nelems)-int(s.allocCount) > 0 {
			// 将 span 放入 有空闲 的列表
			c.partialSwept(sg).push(s)
		} else {
		    // 将 span 从 没有空闲的列表中删除
			c.fullSwept(sg).push(s)
		}
	}
}

加锁
将 span 从 full 列表删除
将 span 放入 partial 列表
解锁

5. heap

由 central 的数据结构可见，每个 mcentral 对象只管理特定的 class 规格的 span ，事实上每种 class 都会对应一个 mcentral ，这个 mcentral 的集合存放于 mheap 的数据结构中。
在runtime/mheap.go中定义了 heap 的数据结构：

type mheap struct {
	lock  mutex // 互斥锁
	pages pageAlloc // page allocation data structure
	sweepgen     uint32 // sweep generation, see comment in mspan; written during STW
	sweepDrained uint32 // all spans are swept or are being swept
	sweepers     uint32 // number of active sweepone calls
	// 指向 spans 区域，映射 span 和 page 的关系
	allspans []*mspan // all spans out there
	_ uint32 // align uint64 fields on 32-bit for atomics
	pagesInUse         uint64  // pages of spans in stats mSpanInUse; updated atomically
	pagesSwept         uint64  // pages swept this cycle; updated atomically
	pagesSweptBasis    uint64  // pagesSwept to use as the origin of the sweep ratio; updated atomically
	sweepHeapLiveBasis uint64  // value of gcController.heapLive to use as the origin of sweep ratio; written with lock, read without
	sweepPagesPerByte  float64 // proportional sweep ratio; written with lock, read without
	scavengeGoal uint64
	reclaimCredit uintptr
	arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
	heapArenaAlloc linearAlloc
	arenaHints *arenaHint
	arena linearAlloc
	allArenas []arenaIdx
	sweepArenas []arenaIdx
	markArenas []arenaIdx
	curArena struct {
		base, end uintptr
	}
	_ uint32 // ensure 64-bit alignment of central
	// 每种 class 对应的两个 mcentral
	central [numSpanClasses]struct {
		mcentral mcentral
		pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
	}
	spanalloc             fixalloc // allocator for span*
	cachealloc            fixalloc // allocator for mcache*
	specialfinalizeralloc fixalloc // allocator for specialfinalizer*
	specialprofilealloc   fixalloc // allocator for specialprofile*
	specialReachableAlloc fixalloc // allocator for specialReachable
	speciallock           mutex    // lock for special record allocators.
	arenaHintAlloc        fixalloc // allocator for arenaHints
	unused *specialfinalizer // never set, just here to force the specialfinalizer type into DWARF
}

mheap 管理着全部的内存，Go通过一个 mheap 类型的全局变量进行内存管理。

系统预分配的内存分为 spans,bitmap,arena 三个区域，通过 mheap 管理。

6. 内存分配过程

针对待分配对象大小的不同有不同的分配逻辑：

• (0,16B) 且不包含指针的对象: Tiny 分配
• (0,16B) 且包含指针的对象: 正常分配
• [16B, 32KB): 正常分配
• (32KB, …): 大对象分配

已申请 size 为 n 的内存为例，分配对象如下：

1. 获取当前线程的私有缓存 mcache
2. 根据 size 计算出适合的 class 的 ID
3. 从 mcache 的 alloc[class] 链表中查询可用的 span
4. 如果 mcache 没有可用的 span，则聪哥 mcentral 中申请一个新的 span 加入 mcache
5. 如果 mcentral 中也没有可用的 span ，则从 mheap 中申请一个新的 span 加入 mcentral
6. 从该 span 中获取空闲对象地址并返回

7. 总结

Go 内存分配是一个相当复杂的过程，只关注关键结构和过程如下：

• Go 程序启动时申请一大块内存，并划分成 spans, bitmap, arena 区域
• arena 区域按页划分成一个个小块
• span 管理一个或多个页
• mcentral 管理多个 span 供线程申请使用
• mcache 作为线程私有资源，资源来源于 mcentral