cache missing

# on-heap object allocator

on-heap 和 off-heap 的区别是这个对象占用的内存是否支持垃圾自动回收，不过on-heap 中，也有部分内存可以支持手动管理。但是对于off-heap的对象，必须只能手动管理，比如heapArena，mspan等runtime中的数据结构。用户程序运行过程中分配的空间都是on-heap的。

# mspan

mspan是内存分配的一个关键数据结构，它管理着一个或多个页面大小的空间，支持多种分配方式，非常灵活，既可以实现segregated allocator、也可以实现 free list allocator （go routine 栈空间分配）

//go:notinheap
type mspan struct {
    startAddr uintptr
    npages uintptr
    manualFreeList gclinkptr
    freeindex uintptr
    nelems uintptr // number of object in the span
    allocBits *gcBits
    ...
}
1
2
3
4
5
6
7
8
9
10
字段 描述
startAddr mspan管理的内存空间的起始地址
npages mspan管理的页面数量
manualFreeList Free List Allocator 相关字段，使用场景：stack pool
freeindex segregated allocator 用于记录从哪里开始扫描空闲块
allocCache mspan中的bitmap是int8， 而这个allocCache是int64，可以加快空闲块的速度，使用的时候需要从bitmap中填充，然后使用count trailing zero的方式快速定位到空闲块
allocBits segregated allocator 用的位图，用来标记哪些块被分配出去了

# segregated-fit allocator

golang 对象分配采用的是segregated-fit allocator，分配方式的选择与垃圾回收也是互相影响的。常见的分配方式还有sequential allocation、free list allocation
sequential allocation 的实现方式非常简单，只需要把维护的空间直接分配出去就好，每次分配以后挪动指针，指向剩余空闲的位置的首地址，runtime off-heap object allocator一节中介绍的persistent allocator采用的就是sequential allocation这个方式。sequential allocation这种分配方式的缺点是不能直接回收，得配合特定的垃圾回收算法，比如semispace copying collection，这种垃圾回收算法把堆划分成两份，当一份分配完以后，把仍然有用的对象拷贝到另外半个堆中，这样没有用的对象的空间就被回收了，分配空间继续在另外半个堆进行，当满了以后再拷贝有用的对象回到原来的半个堆中。
free list allocation 这种分配方式相对sequential allocation这种方式没能更好的利用上缓存的空间局部性原理，并且分配的时候速度慢，虽然有first fit 、next fit、best fit三种寻找空闲块的策略 ，但是多少还是会造成外部碎片。但是free list allocation 可以支持立马把释放的空间放到list中用于后续的分配。
segregated-fit allocation 的策略是，设置K个size class ，各自的大小是s1,s2...sk (从小到大排队)，当程序需要S大小空间的时候，给其分配sn这么多的空间(sn<=S<sn+1)，每种size class都有一个分配器，专门分配这个大小，这样相比 free list allocation 可以免去寻找合适内存块的过程。但是会造成更多的浪费，因为对象的大小不一定正好等于slot的大小。调整size class 的个数和每个的大小是减少浪费的关键。

segregated-fit allocation 还有一个好处是可以非常方便的处理指向对象内部的指针，这可以为垃圾回收提供便利，对于任何一个指针，可以很轻松的找到这个指针所指向的对象的首地址。

# size class 的选择

golang 使用了66个size class，最小的8字节，最大的占4个页面

 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%
    ...
     9        128        8192       64           0     11.72%
    10        144        8192       56         128     11.82%
    ...
    36       1792       16384        9         256     15.57%
    37       2048        8192        4           0     12.45%
    38       2304       16384        7         256     12.46%
    ...
    65      28672       57344        2           0      4.91%
    66      32768       32768        1           0     12.50%
1
2
3
4
5
6
7
8
9
10
11
12
13
14

golang 希望把空间的浪费控制在12.5%以下，所以后一种size class 的大小最大只能是上一种size class的 1.125倍。上边的表格列出了部分size class。可以看到，有一些 size class 的max waste 明显超过了 12.5% , 这是因为在x86下,如果想使用SSE ,地址必须是16bytes 对齐的.
在大小小于128之前,每个size class的大小间隔都是16字节(忽略class 1) . 当介于(128,2048]区间时候,每个size class与前一个size class的大小间隔是前一个size class的1/8 ,2K之后,size class的大小间隔都是256字节.
golang使用mspan实现segregated allocator，因为mspan管理内存的最小单位是页面, 而页面的大小不一定是size class大小的倍数，这也会导致一些内存被浪费. 所以,有一些size class 的 mspan 会管理多个页面,并且在页面数量和所能容纳对象不变的情况下,尽可能的增加size class的大小.

举两个例子

  1. 如果size class的大小是1408,那么一个页面只能放5个对象,浪费率高达14% = (1152 / 8192),如果增加一个页面,两个页面可以放11个对象,浪费率只有5%=896/2/8192 .
  2. 如果size class的大小是8448,那么7个页面最多能容纳6个对象.但是如果页面数量不变,把size class大小调整为9472, 7个页面依旧能容纳下6个对象.并且浪费的空间还能减少许多.

slot

上图是一个简单的示意图，一个mspan划分成若干个slot 用于分配，但是mspan占用页面的大小不能被slot的大小整除，所以有一个tail waste，同时，分配出去的slot 实际存放的对象大小比slot小，又会造成另外一些浪费。

# mspan实现segregated allocator

golang中包含指针和不包含指针的对象分配的时候是区分开的，给一个size class 是 S的对象分配空间 ，如果这个对象包含指针，就会使用span class 为 S << 1 的mspan， 否则就会使用 span calss 为 S<<1 | 1 mspan，这样区分有利于减轻垃圾回收过程中的扫描工作。

allocBits

mspan 在初始化的时候会根据 size class 初始化位图allocBits，分配合适数量的gcBits。在寻找空闲块的时候，不会逐个扫描gcBits，查看里边的每一个bit，而是使用allocCache配合高效的count trailing zero算法用于加速寻找空闲块，allocCache由8个gcBits填充，count trailing zero 可以快速找出uint64中末尾连续0的个数。如上图所示，图中的gcBits中绿色表示0，代表空闲，灰色表示1，代表已经被使用。count trailing zero 数的是末尾0的数量，这里有一个小细节，就是allocCache填充以后做了位翻转。下图是寻找空闲slot的伪代码（python风格），refillAllocCache 就是把连续的8个gcBits通过位运算拼接成一个uint64，freeIndex指向的是上次分配出去的空闲块紧挨着的下一块的下标，每次分配完成后会更新，freeIndex 不仅用于与CountTrailingZero的结果组合成最终的空闲slot下标，还用于记录下次填充的位置，每次填充都是64bits对齐的 （freeIndex + 64 &~(64-1)）。
nextFree

# per-P Segregated Allocator

同样是为了减少竞争，golang为每个P都配置了一个mcache，里边有各种span class的 mspan，这样分配对象的时候，不会因为与其他P同步而降低性能。并且Golang借鉴了google TCMalloc 的设计，引入了mCentral。
mcentral 的数量与span class的数量是相同的，每个span class有对应的一个mcentral，当mcache 中某个mspan空间耗尽的时候，就会找同span class的mcentral 重新分配一个mspan ，这个过程就是下图中的uncacheSpan（把用完的mspan归还到mcentral中）和cacheSpan（从mcentral中领取有空闲空间的mspan）。

tc

mcentral 中有四个mspan列表，分别是 已经清扫且有空闲空间、尚未清扫且有空闲空间、尚未清扫且没有空闲空间、已经清扫且没有空闲空间。当需要从mcentral中取走一个mspan时，优先级如上述，不过，不会从最后一种（已经清扫且没有空闲空间）mspan的列表中取mspan。如果需要从尚未清扫的mspan列表中取走一个mspan，那么在使用之前得先进行清扫工作，如何清扫会在垃圾回收部分进行讨论

mcentral 的背后是页分配器，当mcentral中没有能用的mspan的时候，就会使用页面分配器分配合适数量的页面，然后重新创建一个mspan。

# tiny Allocator

大小落在[0,16) KB范围内的都是微小对象，如果这个微小对象中不含有指针，就会使用 tiny Allocator 进行分配。

tiny allocator

tiny Allocator 也是每个P都有一个，tiny allocator 是在mspan 实现的 segregated allocator 的基础上进行改造的。tiny Allocator 使用的 mspan 对应的 span class 是 5 = 2<<1 | 1，每个slot的大小都是16字节。c.tiny和 c.tinyoffset 分别用来表示可用于分配的slot的首地址和剩余可分配空间到首地址的偏移。上图中，假设某个时刻tiny allocator的状态如A所示，B和C是分配一个新的tiny object 后的对比，这个对比意在说明 c.tiny的更新策略，可以在图中看到，当object B分配以后，因为A中的tinyoffset后边的free不满足object B的大小，所以object B 使用了一个新的slot，又因为新的slot在分配完 object B 以后剩下的空间比前一个slot的剩余空间多，所以c.tiny就指向了新的slot 。与之对比的是C，当需要分配一个 object C ，且新的slot在分配以后剩余空间不如前一个slot剩余空间多的时候，c.tiny仍然指向原slot，不更新

# 栈空间的分配

程序运行过程中，可能go routine 的数量会很庞大，所以一个go routine (普通的routine)被创建的时候，初始仅会分配 2KB栈空间(这里指的是linux/amd64)，对于一些特殊的go routine比如g0 和 signal handling routine则不同。在linux下，signal handling routine的栈大小是32KB，g0的栈在是8KB (!cgo)。
在windows 、solaris、illumos、plan9、darwin操作系统下，g0的栈空间并不是由golang分配的(cgo下也不是)。不过无论是在什么系统，无论是不是cgo，g0的栈空间大小都是不能变的。

os 32bit/64bit arch 初始栈大小(bytes)
windows 32 * 4096
windows 64 * 8192
plan9 * * 4096
Darwin * arm/arm64 4096
其他 * * 2048

当普通的go routine栈空间不足的时候，会扩充栈空间。在16KB 以内(包括 16KB)内呈2 倍增长，超过 16KB 以后，分配的大小是2 的指数个页面的大小。接下来的讨论都是围绕普通的routine的栈

stack

在[初始栈大小,32KB)范围内的栈空间分配，都有对应stack pool的。如果要分配2KB的栈，就直接从对应大小的stack pool中取，如果池里没有，就会分配一个32KB大小的mspan拆分成16份放入池中，用于分配。同样，为了减少竞争，也有per-P的实现，每个P都有自己的stack pool。

当需要分配的stack大小大于等于32KB以后，栈的大小的页面数是2的幂次。此时就没有stack pool了，不过还是设计了一个free list，分配的时候先从free list取，如果没有再从heap中申请。free list的访问需要加锁，并没有per-P的设计

free list

上图是mspan实现free list的示意图，页面被切成一个个大小相同的slot，manualFreeList是mspan结构体中的一个成员，指向的是free list的头，如图8所示，指向下一个空闲块的指针就存在空闲块的起始位置（ptr）

← 垃圾回收基础 →