Base on go 1.13
简介
golang runtime的另外一大主题就是内存分配器，内存分配策略与协程栈、堆、GC等话题息息相关。
- 类似于TC malloc的思想；
- 使用span机制来减少内存碎片，每个span至少为一个页(go中的一个page为8KB)，且大小为页的整数倍，每一种span用于一个范围的内存分配需求. 比如16-32byte使用分配32byte的span, 112-128使用分配128byte的span.
- 一共有67个size范围, 8byte-32KB；每个size有两种类型(scan和noscan, 表示分配的对象是否会包含指针，不包含指针的就不用GC scan)
- 多层次Cache来减少分配的冲突。 per-P无锁的mcache，全局67*2个对应不同size的span的后备mcentral, 全局1个的mheap.
- mheap中以 treap 的结构维护空闲连续page. 归还内存到heap时, 连续地址会进行合并.
- stack分配也是多层次和多class的.
- 对象由GC进行回收. sysmon会定时把空余的内存归还给操作系统
golang的内存分配器虽然思想来源于tcmalloc但是实际上与tcmalloc有很大区别，其中很重要一点是Go 语言被设计为没有显式的内存分配与释放，完全依靠编译器与 runtime 的配合来自动处理，因此也就造就为了内存分配器、垃圾回收器两大组件。
在计算机领域性能优化基本离不开空间换时间，时间换空间，统一管理内存会提前分配或一次性释放一大块内存，进而减少与操作系统沟通造成的开销，进而提高程序的运行性能。支持内存管理另一个优势就是能够更好的支持垃圾回收，这一点我们留到垃圾回收器一节中进行讨论。
内存分配器主要结构
核心的结构就是：
- heapArena: 保留整个虚拟地址空间
- mspan：是 mheap 上管理的一连串的页
- mheap：分配的堆，在页大小为 8KB 的粒度上进行管理
- mcentral：搜集了给定大小等级的所有 span
- mcache：为 per-P 的缓存。
页是向操作系统申请内存的最小单位，目前设计为 8kb。
这些结构之间的关系比较复杂，后面我们将一点点梳理他们之间的关系。
在golang里面内存分为部分，传统意义上的栈由 runtime 统一管理，用户态不感知。而传统意义上的堆内存，又被 Go 运行时划分为了两个部分，
- 一个是 Go 运行时自身所需的堆内存，即堆外内存；
- 另一部分则用于 Go 用户态代码所使用的堆内存，也叫做 Go 堆。
Go 堆负责了用户态对象的存放以及 goroutine 的执行栈。
heapArena
Golang 的堆由很多个 arena 组成，每个 arena 在 64 位机器上是 64MB，且起始地址与 arena 的大小对齐，
所有的 arena 覆盖了整个 Golang 堆的地址空间。
heapArena 对象存储了一个 heap arena的元数据，heapArena对象自身存储在Go heap之外，并且通过mheap_.arenas index 来访问。heapArena对象直接从操作系统分配的，所以理想情况下应该是系统页面大小的倍数。
const(
pageSize = 8192//8KB
heapArenaBytes = 67108864 //一个heapArena是64MB
heapArenaBitmapBytes = heapArenaBytes / 32 // 一个heapArena的bitmap占用2MB
pagesPerArena = heapArenaBytes / pageSize // 一个heapArena包含8192个页
)
//go:notinheap
type heapArena struct {
bitmap [heapArenaBitmapBytes]byte //2,097,152
spans [pagesPerArena]*mspan //
pageInUse [pagesPerArena / 8]uint8
pageMarks [pagesPerArena / 8]uint8
}
- bitmap：是一个2MB个byte数组来标记这个heap area 64M 内存的使用情况，bitmap位图主要为GC标记数组，用2bits标记8(PtrSize) 个byte的使用情况。之所以用2个bits，一是标记对应地址中是否存在对象，另外是标记此对象是否被gc标记过。一个功能一个bit位，所以， heap bitmaps用两个bit位；
- spans：是一个8192（pagesPerArena）大小的指针数组，每个mspan是8KB；
- pageInUse：是一个位图，使用1024 * 8 bit来标记 8192个页(8192*8KB = 64MB)中哪些页正在使用中；
- pageMarks：标记页，与GC相关；
简而言之，heapArena 描述了一个 heap arena 的元信息。
arenaHint
arenaHint结构比较简单，是 arenaHint 链表的节点结构，保存了arena 的起始地址、是否为最后一个 arena，以及下一个 arenaHint 指针。
//go:notinheap
type arenaHint struct {
addr uintptr
down bool
next *arenaHint
}
mspan
前面说了，heapArena 的内存大小是64M，直接管理这么粗粒度的内存明显不符合实践。golang使用span机制来减少碎片. 每个span至少分配1个page(8KB), 划分成固定大小的slot, 用于分配一定大小范围的内存需求，小于 32kb 的小对象则分配在固定大小等级的 span 上，否则直接从 mheap 上进行分配。
mspan//go:notinheap
type mspan struct {
next *mspan // next span in list, or nil if none
prev *mspan // previous span in list, or nil if none
startAddr uintptr // address of first byte of span aka s.base()
npages uintptr // number of pages in span
//......
freeindex uintptr
//......
allocCount uint16 // number of allocated objects
spanclass spanClass // size class and noscan (uint8)
state mSpanStateBox // mSpanInUse etc; accessed atomically (get/set methods)
elemsize uintptr // computed from sizeclass or from npages
}
- npages：表示当前span包含多少个页，npages是根据spanclass来确定的。前面说过了，一个页是8k，也就是这个span存储的是 npages*8k 大小内存。
- spanclass：spanClass是一个uint8，用于计算当前span分配对象的大小。spanClass 的值为0-66，每一个值分别对应一个分配对象的大小以及页数。比如spanclass为1，则span用于分配8个字节的对象，且当前span占用一个页的存储，也就是span是8kb。
- elemsize：表示分配对象的size，根据spanclass和npages都能够算出来。
这里举一个例子：32byte的span,span占用一个页，所以总共有256个slot：
- 这里表示slot大小为32byte的span, 上一次gc之后, 前8个slot使用如上.
- freeindex表示 <该位置的都被分配了, >=该位置的可能被分配, 也可能没有. 配合allocCache来寻找. 每次分配后, freeindex设置为分配的slot+1.
- allocBits表示上一次GC之后哪一些slot被使用了. 0未使用或释放, 1已分配.
- allocCache表示从freeindex开始的64个slot的分配情况, 1为未分配, 0为分配. 使 用ctz(Count Trailing Zeros指令)来找到第一个非0位. 使用完了就从allocBits加载, 取 反.
- 每次gc完之后, sweep阶段, 将allocBits设置为gcmarkBits.
前面一直都说，spanclass可以确定当前span的page数以及分配的对象的大小：
// sizeclasses.go
// class bytes/obj bytes/span objects tail waste max waste
// 1 8 8192 1024 0 87.50%
// 2 16 8192 512 0 43.75%
// 3 32 8192 256 0 46.88%
// 4 48 8192 170 32 31.52%
// 5 64 8192 128 0 23.44%
// 6 80 8192 102 32 19.07%
// 7 96 8192 85 32 15.95%
// 8 112 8192 73 16 13.56%
// 9 128 8192 64 0 11.72%
// 10 144 8192 56 128 11.82%
// 11 160 8192 51 32 9.73%
// 12 176 8192 46 96 9.59%
// 13 192 8192 42 128 9.25%
// 14 208 8192 39 80 8.12%
// 15 224 8192 36 128 8.15%
// 16 240 8192 34 32 6.62%
// 17 256 8192 32 0 5.86%
// 18 288 8192 28 128 12.16%
// 19 320 8192 25 192 11.80%
// 20 352 8192 23 96 9.88%
// 21 384 8192 21 128 9.51%
// 22 416 8192 19 288 10.71%
// 23 448 8192 18 128 8.37%
// 24 480 8192 17 32 6.82%
// 25 512 8192 16 0 6.05%
// 26 576 8192 14 128 12.33%
// 27 640 8192 12 512 15.48%
// 28 704 8192 11 448 13.93%
// 29 768 8192 10 512 13.94%
// 30 896 8192 9 128 15.52%
// 31 1024 8192 8 0 12.40%
// 32 1152 8192 7 128 12.41%
// 33 1280 8192 6 512 15.55%
// 34 1408 16384 11 896 14.00%
// 35 1536 8192 5 512 14.00%
// 36 1792 16384 9 256 15.57%
// 37 2048 8192 4 0 12.45%
// 38 2304 16384 7 256 12.46%
// 39 2688 8192 3 128 15.59%
// 40 3072 24576 8 0 12.47%
// 41 3200 16384 5 384 6.22%
// 42 3456 24576 7 384 8.83%
// 43 4096 8192 2 0 15.60%
// 44 4864 24576 5 256 16.65%
// 45 5376 16384 3 256 10.92%
// 46 6144 24576 4 0 12.48%
// 47 6528 32768 5 128 6.23%
// 48 6784 40960 6 256 4.36%
// 49 6912 49152 7 768 3.37%
// 50 8192 8192 1 0 15.61%
// 51 9472 57344 6 512 14.28%
// 52 9728 49152 5 512 3.64%
// 53 10240 40960 4 0 4.99%
// 54 10880 32768 3 128 6.24%
// 55 12288 24576 2 0 11.45%
// 56 13568 40960 3 256 9.99%
// 57 14336 57344 4 0 5.35%
// 58 16384 16384 1 0 12.49%
// 59 18432 73728 4 0 11.11%
// 60 19072 57344 3 128 3.57%
// 61 20480 40960 2 0 6.87%
// 62 21760 65536 3 256 6.25%
// 63 24576 24576 1 0 11.45%
// 64 27264 81920 3 128 10.00%
// 65 28672 57344 2 0 4.91%
// 66 32768 32768 1 0 12.50%
const (
_MaxSmallSize = 32768
smallSizeDiv = 8
smallSizeMax = 1024
largeSizeDiv = 128
_NumSizeClasses = 67
_PageShift = 13
)
var class_to_size = [_NumSizeClasses]uint16{
0, 8, 16, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}
var class_to_allocnpages = [_NumSizeClasses]uint8{
0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 3, 2, 3, 1, 3, 2, 3, 4, 5, 6,