golang内存分配学习记录

Go内存分配器的设计与实现

• 函数调用的参数，返回值，局部变量基本都分配在栈上。

• 内存管理一般包含三个不同的组件，分别是用户程序，分配器和收集器。

• 一般有两种内存分配方法，一种是线性分配器，另一种是空闲链表分配器。

  线性分配器

  线性分配（Bump Allocator）是一种高效的内存分配方法。当我们在编程语言中使用线性分配器，我们只需要在内存中维护一个指向内存特定位置的指针，当用户程序申请内存时，分配器只需要检查剩余的空闲内存、返回分配的内存区域并修改指针在内存中的位置，即标记已经被使用了的内存。

  因为线性分配器足够简单，可以有较快的执行速度和实现复杂度，但是垃圾回收存在局限性，需要配合压缩标记，复制回收和分代回收这种通过拷贝的方式整理存活对象的碎片，将空闲内存定时合并。

  空闲链表回收器

  不同的内存块以链接的方式链接，这种方式可以方便的回收内存资源，但是在分配内存的时候需要遍历链表，所以分配内容的时候时间复杂度是O(n)。

  内存分配策略有四种方式：首次适应，循环首次适应，最优适应，隔离适应

go语言的内容分配

• go语言使用的内存策略类似隔离适应。隔离适应是把内存隔离成4,8,16,32的内存块组成的链表，然后当我们向内存分配器申请8字节的内容时，遍历8字节的链表，直到找到空的内存块并返回。减少了遍历内存的长度，提高了效率。

• go利用多级缓存，将对象根据大小分类，并按照类型实施不同的分配策略。分成线程缓存，中心缓存，页堆三个组件。

• image-20200525104154084

• go利用分别对待处理对象大小来处理内存分配，从而提高分配效率。

  类别	大小
  微对象	(0, 16B)
  小对象	[16B, 32KB]
  大对象	(32KB, +∞)

• 通过多级缓存可以减少锁次数，当线程缓存不能满足需求时，就会使用中心内存补充解决小对象的内容分配问题，在遇到32kb以上的对象时，内存分配器会直接使用页堆直接分配大量内存。

• go语言在1.10版本的时候还是连续内容。Go 语言在垃圾回收时会根据指针的地址判断对象是否在堆中，建立在堆区的内存是连续的这一假设上，才能找到内存管理单元，这种设计虽然简单并且方便，但是在 C 和 Go 混合使用时会导致程序崩溃：分配的内存地址会发生冲突，导致堆的初始化和扩容失败；没有被预留的大块内存可能会被分配给 C 语言的二进制，导致扩容后的堆不连续。

• image

  程序内存根据自己所在位置的基地址算到spans所在的数组位置，从而找到属于它的内容管理单元。

• 在1.11使用了稀疏的内存布局。不过因为基于稀疏内存的内存管理失去了内存的连续性这一假设，这也使内存管理变得更加复杂，但是解决了上述相关的问题。

image-20200525105921837

如上图所示，运行时使用二维的 runtime.heapArena 数组管理所有的内存，每个单元都会管理 64MB 的内存空间：

type heapArena struct {
    bitmap [heapArenaBitmapBytes]byte //对应bitmap
    spans [pagesPerArena]*mspan //对应spans
    pageInUse [pagesPerArena / 8]uint8
    pageMarks [pagesPerArena / 8]uint8
    zeroedBase uintptr  //该结构体管理的内存的基地址
}

稀疏的内容布局不再是直接算的管理单元，而是直接指向。

由于内存的管理变得更加复杂，上述改动对垃圾回收稍有影响，大约会增加 1% 的垃圾回收开销。

内存状态变化

四种状态

状态	解释
None	内存没有被保留或者映射，是地址空间的默认状态
Reserved	运行时持有该地址空间，访问该内存会导致错误
Prepared	内存被保留，一般没有对应的物理内存，只有虚拟内存，访问该片内存的行为是未定义的 可以快速转换到 Ready 状态
Ready	可以被安全访问

go内存管理对象结构

image-20200525114545568

runtime.mspan 是 Go 语言内存管理的基本单元，他是一个双向链表结构。

type mspan struct {
    next *mspan
    prev *mspan
    ...
    startAddr uintptr // 起始地址
    npages    uintptr // 页数
    freeindex uintptr // 扫描页中空闲对象的初始索引

    allocBits  *gcBits //用于标记内存的占用情况
    gcmarkBits *gcBits //用于标记内存的回收情况
    allocCache uint64 //allocBits 的补码，可以用于快速查找内存中未被使用的内存
    ...
    state       mSpanStateBox //mSpanDead、mSpanInUse、mSpanManual 和 mSpanFree
    ...
    spanclass   spanClass ///它决定了内存管理单元中存储的对象大小和个数
}

runtime.mspan 会当结构体管理的内存不足时，运行时会以页为单位向堆申请内存

当用户程序或者线程向 runtime.mspan 申请内存时，该结构会使用 allocCache 字段以对象为单位在管理的内存中快速查找待分配的空间，如果我们能在内存中找到空闲的内存单元，就会直接返回，当内存中不包含空闲的内存时，上一级的组件 runtime.mcache 可能会为该结构体添加更多的内存页以满足为更多对象分配内存的需求。

Go 语言的内存管理模块中一共包含 67 种跨度类，每一个跨度类都会存储特定大小的对象并且包含特定数量的页数以及对象，所有的数据都会被预选计算好并存储在 runtime.class_to_size 和 runtime.class_to_allocnpages 等变量中：

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%
...	...	...	...	...	...
66	32768	32768	1	0	12.50%

跨度类中除了存储类别的 ID 之外，它还会存储一个 noscan 标记位，该标记位表示对象是否包含指针，垃圾回收会对包含指针的 runtime.mspan 结构体进行扫描。

runtime.mcache

runtime.mcache 是 Go 语言中的线程缓存，它会与线程上的处理器一一绑定，主要用来缓存用户程序申请的微小对象。每一个线程缓存都持有 67 * 2 个 runtime.mspan，这些内存管理单元都存储在结构体的 alloc 字段中。

type mcache struct {
    tiny             uintptr //会指向堆中的一篇内存
    tinyoffset       uintptr //下一个空闲内存所在的偏移量
    local_tinyallocs uintptr //内存分配器中分配的对象个数
}

这三个字段组成了微对象分配器，专门为 16 字节以下的对象申请和管理内存

runtime.mcentral

runtime.mcentral 是内存分配器的中心缓存，与线程缓存不同，访问中心缓存中的内存管理单元需要使用互斥锁。

type mcentral struct {
    lock      mutex
    spanclass spanClass
    nonempty  mSpanList   //不含空闲对象的列表
    empty     mSpanList   //含空闲对象的列表
    nmalloc uint64
}

该结构体在初始化时，两个链表都不包含任何内存，程序运行时会扩容结构体持有的两个链表，nmalloc 字段也记录了该结构体中分配的对象个数。

线程缓存会通过中心缓存的 runtime.mcentral.cacheSpan 方法获取新的内存管理单元，分几步：

1. 从empty查找。
2. 从nonempty查找，看看有没有被标记回收或者已经回收的，插回到empty中。
3. 遍历nonempty看看有没有内存可以回收的。
4. 调用runtime.mcentral.grow从堆中申请新的内容管理单元。
5. 更新allocCache等字段。

runtime.mheap

runtime.mheap 是内存分配的核心结构体，Go 语言程序只会存在一个全局的结构，而堆上初始化的所有对象都由该结构体统一管理，该结构体中包含两组非常重要的字段，其中一个是全局的中心缓存列表 central，另一个是管理堆区内存区域的 arenas 以及相关字段。

页堆中包含一个长度为 134 的 runtime.mcentral 数组，其中 67 个为跨度类需要 scan 的中心缓存，另外的 67 个是 noscan 的中心缓存。

初始化：

1. spanalloc、cachealloc 以及 arenaHintAlloc 等 runtime.fixalloc 类型的空闲链表分配器；
2. central 切片中 runtime.mcentral 类型的中心缓存；

func (h *mheap) init() {
    h.spanalloc.init(unsafe.Sizeof(mspan{}), recordspan, unsafe.Pointer(h), &memstats.mspan_sys)
    h.cachealloc.init(unsafe.Sizeof(mcache{}), nil, nil, &memstats.mcache_sys)
    h.specialfinalizeralloc.init(unsafe.Sizeof(specialfinalizer{}), nil, nil, &memstats.other_sys)
    h.specialprofilealloc.init(unsafe.Sizeof(specialprofile{}), nil, nil, &memstats.other_sys)
    h.arenaHintAlloc.init(unsafe.Sizeof(arenaHint{}), nil, nil, &memstats.other_sys)

    h.spanalloc.zero = false

    for i := range h.central {
        h.central[i].mcentral.init(spanClass(i))
    }

    h.pages.init(&h.lock, &memstats.gc_sys)
}

这会帮助分配器分割待分配的内存，该分配器提供了以下两个用于分配和释放内存的方法：

1. runtime.fixalloc.alloc — 获取下一个空闲的内存空间；
2. runtime.fixalloc.free — 释放指针指向的内存空间；

除了这些空闲链表分配器之外，我们还会在该方法中初始化所有的中心缓存，这些中心缓存会维护全局的内存管理单元，各个线程会通过中心缓存获取新的内存单元。

用户程序申请内容流程

堆上所有的对象都会通过调用 runtime.newobject 函数分配内存，该函数会调用 runtime.mallocgc 分配指定大小的内存空间，这也是用户程序向堆上申请内存空间的必经函数。

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    mp := acquirem()
    mp.mallocing = 1

    c := gomcache()
    var x unsafe.Pointer
    noscan := typ == nil || typ.ptrdata == 0
    if size <= maxSmallSize {
        if noscan && size < maxTinySize {
            // 微对象分配
        } else {
            // 小对象分配
        }
    } else {
        // 大对象分配
    }

    publicationBarrier()
    mp.mallocing = 0
    releasem(mp)

    return x
}

上述代码使用 runtime.gomcache 获取了线程缓存并通过类型判断类型是否为指针类型。我们从这个代码片段可以看出 runtime.mallocgc 会根据对象的大小执行不同的分配逻辑，在前面的章节也曾经介绍过运行时根据对象大小将它们分成微对象、小对象和大对象，这里会根据大小选择不同的分配逻辑.

• 微对象 (0, 16B) — 先使用微型分配器，再依次尝试线程缓存、中心缓存和堆分配内存；
• 小对象 [16B, 32KB] — 依次尝试使用线程缓存、中心缓存和堆分配内存；
• 大对象 (32KB, +∞) — 直接在堆上分配内存；

微对象

Go 语言运行时将小于 16 字节的对象划分为微对象，它会使用线程缓存上的微分配器提高微对象分配的性能，我们主要使用它来分配较小的字符串以及逃逸的临时变量。微分配器可以将多个较小的内存分配请求合入同一个内存块中，只有当内存块中的所有对象都需要被回收时，整片内存才可能被回收。

微分配器管理的对象不可以是指针类型，管理多个对象的内存块大小 maxTinySize 是可以调整的，在默认情况下，内存块的大小为 16 字节。maxTinySize 的值越大，组合多个对象的可能性就越高，内存浪费也就越严重；maxTinySize 越小，内存浪费就会越少，不过无论如何调整，8 的倍数都是一个很好的选择。

线程缓存 runtime.mcache 中的 tiny 字段指向了 maxTinySize 大小的块，如果当前块中还包含大小合适的空闲内存，运行时会通过基地址和偏移量获取并返回这块内存。

当内存块中不包含空闲的内存时。会从先线程缓存找到跨度类对应的内存管理单元 runtime.mspan，调用 runtime.nextFreeFast 获取空闲的内存；当不存在空闲内存时，我们会调用 runtime.mcache.nextFree 从中心缓存或者页堆中获取可分配的内存块。获取新的空闲内存块之后，会清空空闲内存中的数据、更新构成微对象分配器的几个字段 tiny 和 tinyoffset 并返回新的空闲内存。

小对象

小对象是指大小为 16 字节到 32,768 字节的对象以及所有小于 16 字节的指针类型的对象，小对象的分配可以被分成以下的三个步骤：

1. 确定分配对象的大小以及跨度类 runtime.spanClass；
2. 从线程缓存、中心缓存或者堆中获取内存管理单元并从内存管理单元找到空闲的内存空间；
3. 调用 runtime.memclrNoHeapPointers 清空空闲内存中的所有数据；

大对象

运行时对于大于 32KB 的大对象会单独处理，我们不会从线程缓存或者中心缓存中获取内存管理单元，而是直接在系统的栈中调用 runtime.largeAlloc 函数分配大片的内存。

参考：Go 内存分配器的设计与实现 作者：Draveness