Golang 内存模型和分配机制笔记

对 golang 内存模型和分配的学习笔记，参考了小徐先生文章和视频讲解：Golang 内存模型与分配机制 - 知乎

也参考了这篇图解文章：A visual guide to Go Memory Allocator from scratch (Golang) | by Ankur Anand | Medium

Golang 整体内存模型

Golang 作为一个有 runtime 的语言，它的 runtime 负责向用户程序分配内存，而非采用显示的函数或者系统调用来向操作系统申请。除了作为一个 gc 语言有引入 runtime 维护内存的需要外，引入一套好的分配机制也可以提高性能。

Golang 的内存分配机制源自谷歌的 thread caching malloc 算法，也就是一套专门针对多核多线程下内存管理的优化算法。针对这个目标，Golang 的内存分配机制有几个关键点：

• 以空间换时间：一次缓存，多次复用
• 多级缓存，降低锁粒度
• 多级规格，提高利用率

Golang 的内存多级锁模型如下图：

可以看到为了面向多线程场景，golang 的内存分配机制其实就是一个多级的缓存，基于全局唯一的堆 mheap 之上依次细化粒度，产生 mcentral和mcache模型。

其中，mheap 就是 golang 程序的堆，是全局的内存来源，访问需要加一把全局大锁；mcentral 是每种对象规格（总共68种）对应的缓存，锁的粒度就是一种规格一把；mcache是对应每个P（GMP的P）持有一份的内存缓存，访问时无锁。

除了锁之外，golang 还提供多级的内存单元去提高内存的利用率，使用 page 作为分页存储单元、mspan 作为管理单元。其中 page 参考了操作系统的分页思想，但是每个 page 大小为 8KB；mspan 大小为 page 的整数倍，从 8KB到 80KB划分了67种不同的规格，这样就可以在分配时按大小映射到不同规格的 mspan，提高整体空间利用率，也支持细锁化的实现。

整体看起来，内存模型大概长这样：

mspan 内存单元

• mspan 是 golang 内存管理的最小单元，用来管理连续内存；
• mspan 大小是 page 的整数倍，且内部的页（在虚拟内存的数值上）是连续的；
• 每个 mspan 根据空间的大小和分配对象的大小会被划分为不同的等级；
• 同等级的 mspan 属于一个 mcentral，共享一把互斥锁；
• mspan 采用 bitMap 快速找到空闲的内存块，这个 bitMap 的方法有点类似于嵌入式操作系统的内存管理方法，总之就是用 bitMap 去标识空闲内存块，使用位级的运算去做快速定位。

spanClass 内存单元等级

mspan 根据空间大小和面向分配对象的大小，分成67种等级。每个等级的 span 大小都是 page 的倍数，但这个倍数并不是和等级一对一的，因为除了 span 的大小，其管理的对象的大小不同，对应的等级也不同：

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	24	8192	341	8	29.24%
4	32	8192	256	0	21.88%
...
66	28672	57344	2	0	4.91%
67	32768	32768	1	0	12.50%

可以看出不同等级下管理的对象大小、能管理的对象数量都不一样，其中因为 span 总空间和单个对象空间占用除不干净的问题还会产生不同的 tail waste。表格中的 max waste 是在最极端的情况下填满这个 span 时会浪费的内存比例，造成这个浪费的原因主要是对象的实际大小小于这个等级对应的对象大小（但是大于上一个等级）。

mcache 线程缓存

mcache 是每个 P（processor）独有的缓存，所以又叫 per-P 缓存，不需要加锁。 在分配内存的时候，优先尝试从不需要加锁的 mcache中进行尝试，以此提高性能。

对于每个级别，mcache 将其分为两个类别，每个类别分别创建一套 68 个 span 作为缓存，总共136个。这两种类型称为 scan 和 noscan，分别表示包含指针和不包含指针的对象（例如int，string等简单类型）。区分这两种类别的好处是可以将 noscan 的对象单独拎出来，在进行 gc 的时候不需要展开扫描这部分对象。

对每个 spanClass，我们把 span class 的等级和对象的 noscan 属性组装成一个 uint8 来作为它的标识，其中前7位是 span 等级，最后一位是 noscan 信息。

内存中可能也需要管理大量的<16B的小对象，对于这种小对象 golang 会将其组装在一起成为 16B 的对象进行统一存储，使用一个 offset 来标明已经被使用的字节数。这样设计就避免了小对象，特别是小于8B的微小对象都放入 span 中占用固定块的空间，同时也避免了大量小对象占满小一级的 span 导致频繁向上一级内存分配器去获取锁。

mcache 在设计上负责处理对象大小 <= 32K 字节的分配，mcache 再根据这个大小找对应的 mspan 处理。

mcentral 中心缓存

mcentral 是 runtime 用来管理每一类 spanClass 的统一空闲列表，每一种 spanClass 对应一个。每个 mcentral 包含两个 mspan 列表，分别记录空闲 span 和完全满的 span：

如果 mchache 中没有可用大小的内存，它会找当前级别的 mcentral 去申请一块。

因为 mcentral 是所有线程共享的，所以需要加锁访问。

mheap 全局堆缓存

mheap 是在 runtime 中对于操作系统虚拟内存的抽象，golang 的上层应用都基于此分配内存。mheap 以页（8KB）为单位，以页作为最小内存存储单元，负责将连续的页组装成 mspan。

mheap 采用 bitMap 来完成对页的使用情况的标识和分配，每个 bit 对应一个页是否被分配（被 mspan 组装）。同时也有一个 heapArena 数组记录了页到 mspan 的映射信息。

除此之外，还有一个 redix tree index 建立了一个空闲页基数树索引，快速寻找空闲页。

mheap 的主要设计定位是 mcentral 的持有者，持有所有 spanClass 下的 mcentral 作为自身的缓存；当内存不够时，mheap 负责向操作系统申请内存，这个申请的单位是 heapArena（64MB）。

mheap 同样需要持锁操作，有一把大锁锁住全部。

mheap 的空闲页索引机制

mheap 中，采用 bitMap + 基数树的形式来快速寻页。每颗基数树包含 16GB 空间的各页的使用情况的索引信息，mheap 共持有 2^14 = 16384 棵基数树，因此可以覆盖 2^14 * 16GB = 256T 的内存空间。

需要注意的是这里说用基数树，其实不是一般说的基数树。一般说的基数树是像 trie 树一样的前缀树，基于相同前缀的压缩来减少搜索时间，主要做的是 k-v 的映射，用来在一定程度上可以替换 hash map，因为其存储节省空间且查找速度快。

但这里讲的基数树实际上是一个固定8叉、5层高的树，每个节点叫做 pallocSum，为一个uint64，对应一段内存区间的使用情况信息，叫这个名字是因为父节点包含了子节点对应的区间：

它把 uint64 分成三段，start、end、max分别放当前映射的页表范围中首段、末端 以及整个范围中 最大的连续空闲页数量（bitMap中连续0的数量）。因为分成的是八段，所以八个子节点分别对应父节点的八等分。树高五层，意味着最后一层对应的页面区间大小为 16GB/8^4 = 4MB，对应512个 page，又叫一个 chunk。

在寻页时，我们就可以自顶向下遍历每个节点，先看 start 是否满足，如果是就寻页成功；否则看 max 是否满足，如果满足则进入其下层子节点递归寻页；如果 max 也不满足，就看 end 和下一个同辈节点的 start 加起来能不能满足（仍然是连续的），如果能就寻页成功，否则在这一层寻页失败。可以看出，要分配的内存越大，就能越快的判断当前的基数树是否能够更满足它。

这样的设计考虑有两个，一个是通过 bitMap + 这个类基数树可以减少持锁的时间，一个是可以为内存管理引入可扩展性（扩展这个树的高度）。在 golang 1.12 的时候，mheap 采用 treap 来进行内存的管理，但作为一个全局的结构，一切事情都要操作这个 treap 就导致在对树做任何操作时都要一直保持这个锁。在需要密集对象分配或者 P 需要扩展性提高的时候，就不能满足需求，产生较长的等待时间。更换这个设计并为每个P增加一个自己的缓存，主要目的就是将锁粒度细化从而实现扩展性和性能的提高。

除了维护空闲页的 bitMap，mheap 还维护了一个heapArena 来记录页到 mspan 的映射。这个 arena 其实就是 mheap 向操作系统申请内存时的那个单位（64M），对应 8192 个页。因为是连续内存，所以根据偏移地址找到页很方便，但是每个页归属的 mspan 就不好找了，而 gc 的时候这个又需要，所以需要维护一个这个映射：

const pagesPerArena = 8192
type heapArena struct {
    // ...
    spans [pagesPerArena]*mspan
}

对象分配流程

了解到这里就可以整体地自上而下梳理一下 golang 分配对象的流程。

不管是通过哪种方式（new，make，或者 literal的方式）申明新对象，最终都会调用 mallocgc 方法。根据要分配对象的大小，对象被分为三类：tiny（0-16B）、small（16B-32KB）、large（32KB+）。这三类对象分别有不同的处理步骤。

总的来说，对象分配流程有下面几个步骤（不同类型经过的不同，如果某一步成功就可以结束返回，不成功则继续往下走）：

1. 从 P 对应的 mcache 的 tiny 分配器取内存；（tiny，无锁）
2. 根据所属的 spanClass，从 mcache 缓存的 mspan 中取内存（tiny 、small，无锁）
3. 根据所属的 spanClass，从对应的 mcentral 中取 mspan 填充到 mcache，然后从 mspan 中取内存（tiny、small，有 mcentral 的 spanClass 粒度的锁）
4. 根据所属的 spanClass，从 mheap 页分配器 pageAlloc 取得足够数量空闲页组装成 mspan 填充到 mcache，然后从 mspan 中获取内存（tiny、small、large，需要 mheap 全局锁）
5. mheap 向操作系统申请内存，更新页分配器的索引信息，重复4.（同4）

具体的步骤就结合源码来看。

tiny 分配

if noscan && size < maxTinySize {
        // tiny 内存块中，从 offset 往后有空闲位置
          off := c.tinyoffset
          // ...
            // 如果当前 tiny 内存块空间还够用，则直接分配并返回
            if off+size <= maxTinySize && c.tiny != 0 {
            // 分配空间
                x = unsafe.Pointer(c.tiny + off)
                c.tinyoffset = off + size
                c.tinyAllocs++
                mp.mallocing = 0
                releasem(mp)
                return x
            }
           // ...
        }

tiny 分配比较简单，基于 mcache 上的微对象分配器 用 offset 线性移动的方式来分配即可。对象大小会被向上取整为2的整数次幂进行补齐。

mcache 分配

		  // 根据对象大小，映射到其所属的 span 的等级(0~66）
          var sizeclass uint8
          // get size class ....     
          // 对应 span 等级下，分配给每个对象的空间大小(0~32KB)
          // get span class
          spc := makeSpanClass(sizeclass, noscan) 
          // 获取 mcache 中的 span
          span = c.alloc[spc]  
          // 从 mcache 的 span 中尝试获取空间        
          v := nextFreeFast(span)
          if v == 0 {
          // mcache 分配空间失败，则通过 mcentral、mheap 兜底            
             v, span, shouldhelpgc = c.nextFree(spc)
          }     
          // 分配空间  
          x = unsafe.Pointer(v)

其中 nextFreeFast 这个方法是在 mspan 里尝试获取空间，根据 bitMap 去快速查空闲 object 位：

func nextFreeFast(s *mspan) gclinkptr {
    // 通过 ctz64 算法，在 bit map 上寻找到首个 object 空位
    theBit := sys.Ctz64(s.allocCache) 
    if theBit < 64 {
        result := s.freeindex + uintptr(theBit)
        if result < s.nelems {
            freeidx := result + 1
            if freeidx%64 == 0 && freeidx != s.nelems {
                return 0
            }
            s.allocCache >>= uint(theBit + 1)
            // 偏移 freeindex 
            s.freeindex = freeidx
            s.allocCount++
            // 返回获取 object 空位的内存地址 
            return gclinkptr(result*s.elemsize + s.base())
        }
    }
    return 0

当 mspan 没有可用 object 位时，会调用 mcache.nextFree 兜底：

func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool) {
    s = c.alloc[spc]
    // ...
    // 从 mcache 的 span 中获取 object 空位的偏移量
    freeIndex := s.nextFreeIndex()
    if freeIndex == s.nelems {
        // ...
        // 倘若 mcache 中 span 已经没有空位，则调用 refill 方法从 mcentral 或者 mheap 中获取新的 span    
        c.refill(spc)
        // ...
        // 再次从替换后的 span 中获取 object 空位的偏移量
        s = c.alloc[spc]
        freeIndex = s.nextFreeIndex()
    }
    // ...
    v = gclinkptr(freeIndex*s.elemsize + s.base())
    s.allocCount++
    // ...
    return
}

mcentral 分配

如果 mcache 中的 span 也没有空位，就会调用 refill 方法从上层再获取空间。

func (c *mcache) refill(spc spanClass) {  
    s := c.alloc[spc]
    // ...
    // 从 mcentral 当中获取对应等级的 span
    s = mheap_.central[spc].mcentral.cacheSpan()
    // ...
    // 将新的 span 添加到 mcahe 当中
    c.alloc[spc] = s
}

注意从这个 mcentral.cacheSpan 方法开始就需要加锁了。mcentral 分别从 partial 和 full 的 mspan list 里尝试 获取有空间的 mspan：

 if sl.valid {
        for ; spanBudget >= 0; spanBudget-- {
            s = c.partialUnswept(sg).pop()
            // ...
            if s, ok := sl.tryAcquire(s); ok {
                // ...
                sweep.active.end(sl)
                goto havespan
            }
            
        // 通过 sweepLock，加锁尝试从 mcentral 的非空链表 full 中获取 mspan
        for ; spanBudget >= 0; spanBudget-- {
            s = c.fullUnswept(sg).pop()
           // ...
            if s, ok := sl.tryAcquire(s); ok {
                // ...
                sweep.active.end(sl)
                goto havespan
                }
            }
        }
    }

mheap 分配

如果在 mcache 处的 partial 和 full 都找不到合适的 mspan 了，则会调用 mcentral 的 grow 方法，向 mheap 获取空间：

func (c *mcentral) grow() *mspan {
    npages := uintptr(class_to_allocnpages[c.spanclass.sizeclass()])
    size := uintptr(class_to_size[c.spanclass.sizeclass()])
    s := mheap_.alloc(npages, c.spanclass)
    // ...
    return s
}

在 mheap 的处理中，主要是 allocSpan 方法在处理：

func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan) {
    gp := getg()
    base, scav := uintptr(0), uintptr(0)
// ...
// 加上堆全局锁
    lock(&h.lock)
    if base == 0 {
        // 通过基数树索引快速寻找满足条件的连续空闲页
        base, scav = h.pages.alloc(npages)
        // ...
    }
    // ...
    unlock(&h.lock)

HaveSpan:
    // 把空闲页组装成 mspan
    s.init(base, npages)
    // 将这批页添加到 heapArena 中，建立由页指向 mspan 的映射
    h.setSpans(s.base(), npages, s)
    // ...
    return s
}

系统分配

最后就是 mheap 也没有足够多的空闲页，这时候就发起 mmap 系统调用申请额外空间：

func (h *mheap) grow(npage uintptr) (uintptr, bool) {
    av, asize := h.sysAlloc(ask)
}
func (h *mheap) sysAlloc(n uintptr) (v unsafe.Pointer, size uintptr) {
       v = sysReserve(unsafe.Pointer(p), n)
}
func sysReserve(v unsafe.Pointer, n uintptr) unsafe.Pointer {
    return sysReserveOS(v, n)
}
func sysReserveOS(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
}

到此整个流程都走过一遍了。

总结

一段话总结 golang 有关内存分配的机制：

golang 的 runtime 通过自主管理的 mheap 来为 go 应用程序提供了独立于操作系统的内存分配机制。采用分页方式存储内存，将内存分为 8KB 的页存储；使用大小为 page 整数倍的不同规格的 mspan 来管理内存用以对应不同大小的内存对象，其内部使用 bitMap 快速查找空闲块；每个 P 持有自己的线程缓存 mcache，它将每种规格的 mspan 各缓存了一个，线程中的内存申请优先在 mcache中进行，同时也提供了微对象分配器处理小于16B的对象；每种规格的 mspan 都在一个 mcentral 中进行聚合，mcentral 维护列表管理 mspan；使用全局堆缓存mheap 作为操作系统虚拟内存的抽象，维护 bitMap 标识页的使用情况，使用空闲页基数树索引辅助快速寻找空闲页，同时维护了页到 mspan 的映射信息，负责将连续页组装成 mspan，并在内存不够时向操作系统申请。

看完 golang 的内存管理，可以吸收其两个设计思想：

• 使用缓存提高效率，并且缓存是多级的。利用缓存，一个是减少了系统调用的次数，一个是多级的缓存也降低了锁的粒度，从而降低了加锁的次数。总而言之就是提高了内存管理的效率。
• 细化分级。针对并发性要求，我们对每个 P 都细化出一个专属的缓存，尽可能减少需要加锁的影响；针对不同的对象大小分别做不同的专门处理，提高内存的利用率和小对象的分配效率。

---