业余生活要有意义，不要越轨。——华盛顿
上次说了Golang的垃圾回收机制之后，小黑觉得不太理解里面的内存分配机制，我说你去看书啊，她说没时间 ,,,
给自己找借口，相当于谋财害命，尤其是技术人，切记不要错过任何学习的机会。
1 业界常见的内存分配器
- tcmalloc（Google）
- jemalloc（Facebook）
Golang中也实现了自己的内存分配器，原理与tcmalloc相似，简单的说就是程序预先申请一块大的内存，每个P(GMP)维护一块小的私有内存，私有内存不足再从全局中申请。
2 基础概念
2.1 简述
为了方便自主管理内存，做法便是先向系统申请一块内存，然后将内存切割成小块，通过一定的内存分配算法管理内存。
2.2 详细介绍
以64位系统为例，Golang程序启动时会向系统申请的内存如下图所示：
预申请的内存划分为spans、bitmap、arena三部分。其中arena即为所谓的堆区，应用中需要的内存从这里分配。其中spans和bitmap是为了管理arena区而存在的。
arena的大小为512G，为了方便管理把arena区域划分成一个个的page，每个page为8KB,一共有512GB/8KB个页；
spans区域存放span的指针，每个指针对应一个page，所以span区域的大小为(512GB/8KB)*指针大小8byte = 512M
bitmap区域大小也是通过arena计算出来，不过主要用于GC。
2.2.1 span
span是用于管理arena页的关键数据结构，每个span中包含1个或多个连续页，为了满足小对象分配，span中的一页会划分更小的粒度，而对于大对象比如超过页大小，则通过多页实现。
2.2.1.1 class
跟据对象大小，划分了一系列class，每个class都代表一个固定大小的对象，以及每个span的大小。如下表所示
// class bytes/obj bytes/span objects waste bytes 1 8 8192 1024 0 2 16 8192 512 0 3 32 8192 256 0 4 48 8192 170 32 5 64 8192 128 0 6 80 8192 102 32 7 96 8192 85 32 8 112 8192 73 16 9 128 8192 64 0 10 144 8192 56 128 11 160 8192 51 32 12 176 8192 46 96 13 192 8192 42 128 14 208 8192 39 80 15 224 8192 36 128 16 240 8192 34 32 17 256 8192 32 0 18 288 8192 28 128 19 320 8192 25 192 20 352 8192 23 96 21 384 8192 21 128 22 416 8192 19 288 23 448 8192 18 128 24 480 8192 17 32 25 512 8192 16 0 26 576 8192 14 128 27 640 8192 12 512 28 704 8192 11 448 29 768 8192 10 512 30 896 8192 9 128 31 1024 8192 8 0 32 1152 8192 7 128 33 1280 8192 6 512 34 1408 16384 11 896 35 1536 8192 5 512 36 1792 16384 9 256 37 2048 8192 4 0 38 2304 16384 7 256 39 2688 8192 3 128 40 3072 24576 8 0 41 3200 16384 5 384 42 3456 24576 7 384 43 4096 8192 2 0 44 4864 24576 5 256 45 5376 16384 3 256 46 6144 24576 4 0 47 6528 32768 5 128 48 6784 40960 6 256 49 6912 49152 7 768 50 8192 8192 1 0 51 9472 57344 6 512 52 9728 49152 5 512 53 10240 40960 4 0 54 10880 32768 3 128 55 12288 24576 2 0 56 13568 40960 3 256 57 14336 57344 4 0 58 16384 16384 1 0 59 18432 73728 4 0 60 19072 57344 3 128 61 20480 40960 2 0 62 21760 65536 3 256 63 24576 24576 1 0 64 27264 81920 3 128 65 28672 57344 2 0 66 32768 32768 1 0
- class：class ID，每个span结构中都有一个class ID, 表示该span可处理的对象类型
- bytes/obj：该class代表对象的字节数
- bytes/span：每个span占用堆的字节数，也即页数*页大小
- objects: 每个span可分配的对象个数，也即（bytes/spans）/（bytes/obj）
- waste bytes: 每个span产生的内存碎片，也即（bytes/spans）%（bytes/obj）
上表可见最大的对象是32K大小，超过32K大小的由特殊的class表示，该class ID为0，每个class只包含一个对象。
2.2.1.2 span数据结构
span是内存管理的基本单位,每个span用于管理特定的class对象, 跟据对象大小，span将一个或多个页拆分成多个块进行管理。
src/runtime/mheap.go:mspan定义了其数据结构：
type mspan struct { //链表前向指针，用于将span链接起来 next *mspan //链表前向指针，用于将span链接起来 prev *mspan // 起始地址，也即所管理页的地址 startAddr uintptr // 管理的页数 npages uintptr // 块个数，也即有多少个块可供分配 nelems uintptr //分配位图，每一位代表一个块是否已分配 allocBits *gcBits // 已分配块的个数 allocCount uint16 // class表中的class ID spanclass spanClass // class表中的对象大小，也即块大小 elemsize uintptr }
以class 10为例，span和管理的内存如下图所示：
spanclass为10，参照class表可得出npages=1,nelems=56,elemsize为144。其中startAddr是在span初始化时就指定了某个页的地址。allocBits指向一个位图，每位代表一个块是否被分配，本例中有两个块已经被分配，其allocCount也为2。
next和prev用于将多个span链接起来，这有利于管理多个span，接下来会进行说明。
2.2.2 cache
有了管理内存的基本单位span，还要有个数据结构来管理span，这个数据结构叫mcentral，各线程需要内存时从mcentral管理的span中申请内存，为了避免多线程申请内存时不断的加锁，Golang为每个线程分配了span的缓存，这个缓存即是cache。
src/runtime/mcache.go:mcache定义了cache的数据结构：
type mcache struct { // 按class分组的mspan列表 alloc [67*2]*mspan }
alloc为mspan的指针数组，数组大小为class总数的2倍。数组中每个元素代表了一种class类型的span列表，每种class类型都有两组span列表，第一组列表中所表示的对象中包含了指针，第二组列表中所表示的对象不含有指针，这么做是为了提高GC扫描性能，对于不包含指针的span列表，没必要去扫描。
根据对象是否包含指针，将对象分为noscan和scan两类，其中noscan代表没有指针，而scan则代表有指针，需要GC进行扫描。
mcache和span的对应关系如下图所示：
mchache在初始化时是没有任何span的，在使用过程中会动态的从central中获取并缓存下来，跟据使用情况，每种class的span个数也不相同。上图所示，class 0的span数比class1的要多，说明本线程中分配的小对象要多一些。
2.2.3 central
cache作为线程的私有资源为单个线程服务，而central则是全局资源，为多个线程服务，当某个线程内存不足时会向central申请，当某个线程释放内存时又会回收进central。
src/runtime/mcentral.go:mcentral定义了central数据结构：
type mcentral struct { //互斥锁 lock mutex // span class ID spanclass spanClass // non-empty 指还有空闲块的span列表 nonempty mSpanList // 指没有空闲块的span列表 empty mSpanList // 已累计分配的对象个数 nmalloc uint64 }
- lock: 线程间互斥锁，防止多线程读写冲突
- spanclass : 每个mcentral管理着一组有相同class的span列表
- nonempty: 指还有内存可用的span列表
- empty: 指没有内存可用的span列表
- nmalloc: 指累计分配的对象个数
线程从central获取span步骤如下：
加锁
- 从nonempty列表获取一个可用span，并将其从链表中删除
- 将取出的span放入empty链表
- 将span返回给线程
- 解锁
- 线程将该span缓存进cache
线程将span归还步骤如下：
- 加锁
- 将span从empty列表删除
- 将span加入noneempty列表
- 解锁
上述线程从central中获取span和归还span只是简单流程，为简单起见，并未对具体细节展开。
2.2.4 heap
从mcentral数据结构可见，每个mcentral对象只管理特定的class规格的span。事实上每种class都会对应一个mcentral,这个mcentral的集合存放于mheap数据结构中。
src/runtime/mheap.go:mheap定义了heap的数据结构：
type mheap struct { lock mutex spans []*mspan //指向bitmap首地址，bitmap是从高地址向低地址增长的 bitmap uintptr //指示arena区首地址 arena_start uintptr //指示arena区已使用地址位置 arena_used uintptr central [67*2]struct { mcentral mcentral pad [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte } }
- lock：互斥锁
- spans: 指向spans区域，用于映射span和page的关系
- bitmap：bitmap的起始地址
- arena_start: arena区域首地址
- arena_used: 当前arena已使用区域的最大地址
- central: 每种class对应的两个mcentral
从数据结构可见，mheap管理着全部的内存，事实上Golang就是通过一个mheap类型的全局变量进行内存管理的。
mheap内存管理示意图如下：
系统预分配的内存分为spans、bitmap、arean三个区域，通过mheap管理起来。接下来看内存分配过程。
3 内存分配过程
针对待分配对象的大小不同有不同的分配逻辑：
- (0, 16B) 且不包含指针的对象：Tiny分配
- (0, 16B) 包含指针的对象：正常分配
- [16B, 32KB] : 正常分配
- (32KB, -) : 大对象分配其中Tiny分配和大对象分配都属于内存管理的优化范畴，这里暂时仅关注一般的分配方法。
以申请size为n的内存为例，分配步骤如下：
- 获取当前线程的私有缓存mcache
- 跟据size计算出适合的class的ID
- 从mcache的alloc[class]链表中查询可用的span
- 如果mcache没有可用的span则从mcentral申请一个新的span加入mcache中
- 如果mcentral中也没有可用的span则从mheap中申请一个新的span加入mcentral
- 从该span中获取到空闲对象地址并返回
4 总结
Golang内存分配是个相当复杂的过程
其中还掺杂了GC的处理，这里仅仅对其关键数据结构进行了说明，了解其原理而又不至于深陷实现细节。
- Golang程序启动时申请一大块内存，并划分成spans、bitmap、arena区域
- arena区域按页划分成一个个小块
- span管理一个或多个页
- mcentral管理多个span供线程申请使用
- mcache作为线程私有资源，资源来源于mcentral
6 关注公众号
微信公众号：堆栈future
