go-内存机制(3)

go的内存分配

Golang有一套自己的内存管理机制，自主的去完成内存分配、垃圾回收、内存管理等过程，从而避免频繁的向操作系统申请、释放内存，有效的提升go语言的处理性能。
Golang的内存管理是基于tcmalloc模型设计，但又有些差异，局部缓存并不是分配给进程或者线程，而是分配给P（Processor）；Golang的GC是stop the world，并不是每个进程单独进行GC；golang语言对span的管理更有效率。

基本概念

1.Span

span是golang内存管理的基本单位，每个span管理指定规格（以page为单位）的内存块，内存池分配出不同规格的内存块就是通过span体现出来的，应用程序创建对象就是通过找到对应规格的span来存储的，

下面我们看一下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
    list *mSpanList // For debugging. TODO: Remove.

    startAddr uintptr // address of first byte of span aka s.base()
    npages    uintptr // number of pages in span

    manualFreeList gclinkptr // list of free objects in mSpanManual spans


    freeindex uintptr //freeindex是0到nelems之间的位置索引，标记下一个空对象索引。
    // TODO: Look up nelems from sizeclass and remove this field if it
    // helps performance.
    nelems uintptr // number of object in the span.

    
    allocCache uint64

    allocBits  *gcBits
    gcmarkBits *gcBits

    // sweep generation:
    // if sweepgen == h->sweepgen - 2, the span needs sweeping
    // if sweepgen == h->sweepgen - 1, the span is currently being swept
    // if sweepgen == h->sweepgen, the span is swept and ready to use
    // if sweepgen == h->sweepgen + 1, the span was cached before sweep began and is still cached, and needs sweeping
    // if sweepgen == h->sweepgen + 3, the span was swept and then cached and is still cached
    // h->sweepgen is incremented by 2 after every GC

    sweepgen    uint32
    divMul      uint16        // for divide by elemsize - divMagic.mul
    baseMask    uint16        // if non-0, elemsize is a power of 2, & this will get object allocation base
    allocCount  uint16        // number of allocated objects
    spanclass   spanClass     // size class and noscan (uint8)
    state       mSpanStateBox // mSpanInUse etc; accessed atomically (get/set methods)
    needzero    uint8         // needs to be zeroed before allocation
    divShift    uint8         // for divide by elemsize - divMagic.shift
    divShift2   uint8         // for divide by elemsize - divMagic.shift2
    elemsize    uintptr       // computed from sizeclass or from npages
    limit       uintptr       // end of data in span
    speciallock mutex         // guards specials list
    specials    *special      // linked list of special records sorted by offset.
}

根据源码和图结合来看，会更加容易理解mspan，每一个mspan就是用来给程序分配对象空间的，也就是说一般我们对象都会放到mspan中管理，这里我们重点解释一下如图所示的几个属性，startAddr 是该mspan在arena区域的首地址，freeindex 用来表示下一个可能是空对象的位置，也就是说freeindex之前的元素（存储对象的空间）均是已经被使用的，freeindex之后的元素可能被使用可能没被使用，allocCache是从freeindex开始对后续元素分配情况进行缓存标记，通过freeindex和allocCache结合进行查找未分配的元素位置效率会更高，我们能快速的找到一个空对象分配给程序使用，而不用全局遍历。allocBits用来标识该span中所有元素的使用分配情况，gcmarkBits 用来sweep过程进行标记垃圾对象的，用于后续gc。

2.怎么区分span

那么要想区分不同规格的span，我们必须要有一个标识，每个span通过splanclass标识属于哪种规格的span，golang的span规格一共有67种，具体查看:

// 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%
//。。。。。
//    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%

其中：

• class： 分类id或者规格id，也就是spanclass, 表示该span可存储的对象规格类型
• bytes/obj：该列代表能存储每个对象的字节数，也就是说可以存储多大的对象，字段是elemsize
• bytes/span：每个span占用堆的字节数，也即页数页大小,npages8KB
• objects: 每个span可分配的元素个数，或者说可存储的对象个数，也就是nelems，也即（bytes/spans）/（bytes/obj）
• tail bytes: 每个span产生的内存碎片，也即（bytes/span）%（bytes/obj）
• max waste：最大浪费比例，（bytes/obj-最小使用量）objects/(bytes/span)100,比如classId=2 最小使用量是9bytes，则max waste=（16-9）512/8192100=43.75%

通过上表，我们可以很清楚的知道在创建一个对象时候，需要去选哪一个splanclass的span去获取内存空间，一个span能存多少这样大小的对象等等信息，非常清晰而又尽可能节约的去使用内存。另外上表可见最大的对象是32KB大小，超过32KB大小的由特殊的class表示，该class ID为0，每个class只包含一个对象。所以上面只有列出了1-66。

内存管理组件

怎么把这些各种规格孤立的span串起来？下面我们来说一下golang的内存管理组件，内存分配是由内存分配器完成，分配器由3种组件构成：mcache、mcentral、mheap，我们来详细讲一下每个组件。

我们知道golang之所有有很强的并发能力，依赖于它的G-P-M并发模型
)，

1.mcache

mcache就绑在并发模型的P上，也就是说我们每一个P都会有一个mcahe绑定，用来给协程分配对象存储空间的。下面具体看一下mcache的结构

type mcache struct {
    // The following members are accessed on every malloc,
    // so they are grouped here for better caching.
    next_sample uintptr // trigger heap sample after allocating this many bytes
    local_scan  uintptr // bytes of scannable heap allocated

    // Allocator cache for tiny objects w/o pointers.
    // See "Tiny allocator" comment in malloc.go.

    // tiny points to the beginning of the current tiny block, or
    // nil if there is no current tiny block.
    //
    // tiny is a heap pointer. Since mcache is in non-GC'd memory,
    // we handle it by clearing it in releaseAll during mark
    // termination.
    tiny             uintptr
    tinyoffset       uintptr
    local_tinyallocs uintptr // number of tiny allocs not counted in other stats

    // The rest is not accessed on every malloc.

    alloc [numSpanClasses]*mspan // spans to allocate from, indexed by spanClass

    stackcache [_NumStackOrders]stackfreelist

    // Local allocator stats, flushed during GC.
    local_largefree  uintptr                  // bytes freed for large objects (>maxsmallsize)
    local_nlargefree uintptr                  // number of frees for large objects (>maxsmallsize)
    local_nsmallfree [_NumSizeClasses]uintptr // number of frees for small objects (<=maxsmallsize)

    // flushGen indicates the sweepgen during which this mcache
    // was last flushed. If flushGen != mheap_.sweepgen, the spans
    // in this mcache are stale and need to the flushed so they
    // can be swept. This is done in acquirep.
    flushGen uint32
}

可以看到在mcache结构体中并没有锁存在，这是因为每个P都会绑定一个mcache，而每个P同时只会处理一个groutine，而且不同P之间是内存隔离的，因此不存在竞争情况。关键字段都已经在代码中解释了，这里我们重点关注一下alloc [numSpanClasses] *mspan，由于SpanClasses一共有67种，为了满足指针对象和非指针对象，这里为每种规格的span同时准备scan和noscan两个，因此一共有134个mspan缓存链表，分别用于存储指针对象和非指针对象，这样对非指针对象扫描的时候不需要继续扫描它是否引用其他对象，GC扫描对象的时候对于noscan的span可以不去查看bitmap区域来标记子对象, 这样可以大幅提升标记的效率。另外mcache在初始化时是没有任何mspan资源的，在使用过程中会动态地申请，不断的去填充 alloc[numSpanClasses]*mspan，通过双向链表连接，如下图所示：

通过图示我们可以看到alloc[numSpanClasses]*mspan管理了很多不同规格不同类型的span，golang对于[16B,32KB]的对象会使用这部分span进行内存分配，所以所有在这区间大小的对象都会从alloc这个数组里寻找
而对于更小的对象，我们叫它tiny对象，golang会通过tiny和tinyoffset组合寻找位置分配内存空间，这样可以更好的节约空间.

2.mcentral

type mcentral struct {
    lock      mutex
    spanclass spanClass
    nonempty  mSpanList // list of spans with a free object, ie a nonempty free list
    empty     mSpanList // list of spans with no free objects (or cached in an mcache)

    // nmalloc is the cumulative count of objects allocated from
    // this mcentral, assuming all spans in mcaches are
    // fully-allocated. Written atomically, read under STW.
    nmalloc uint64
}

我们提到mcache中的mspan都是动态申请的，那到底是去哪里申请呢？其实当空间不足的时候，mcache会去mcentral中申请对应规格的mspan.
首先mcentral与mcache有一个明显区别，就是有锁存在，由于mcentral是公共资源，会有多个mcache向它申请mspan，因此必须加锁，另外，mcentral与mcache不同，由于P绑定了很多Goroutine，在P上会处理不同大小的对象，mcache就需要包含各种规格的mspan，但mcentral不同，同一个mcentral只负责一种规格的mspan就够了。
mcentral也是用spanclass 进行标记规格类型，该规格的所有未被使用的空闲mspan会挂载到nonempty 链表上，已经被mcache拿走，未归还的会挂载到empty 链表上，归还后会再挂载到nonempty上，用图表示如下，以规格sizeClass=1为例：

每一个mSpanList都挂着同一规格mspan双向链表，当然这个链表也不是固定大小的，都会动态变化的。

从central获取span步骤如下：

1. 加锁
2. 从nonempty列表获取一个可用span，并将其从链表中删除
3. 将取出的span放入empty链表
4. 将span返回给线程
5. 解锁
6. 线程将该span缓存进cache线程

将span归还步骤如下：

1. 加锁
2. 将span从empty列表删除
3. 将span加入noneempty列表
4. 解锁

3.mheap

mcentral 的nonempty也有用完的时候，当nonempty为空，再被申请的时候，也就是mcentral空间不足了，那么它会向mheap申请新的页，

type mheap struct {
    lock      mutex

    spans []*mspan

    bitmap        uintptr     //指向bitmap首地址，bitmap是从高地址向低地址增长的

    arena_start uintptr        //指示arena区首地址
    arena_used  uintptr        //指示arena区已使用地址位置

    central [67*2]struct {
        mcentral mcentral
        pad      [sys.CacheLineSize - unsafe.Sizeof(mcentral{})%sys.CacheLineSize]byte
    }
}

我们知道每个golang程序启动时候会向操作系统申请一块虚拟内存空间，仅仅是虚拟内存空间，真正需要的时候才会发生缺页中断，向系统申请真正的物理空间，在golang1.11版本以后，申请的内存空间会放在一个heapArena数组里，由arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena表示，用于应用程序内存分配，下面展示一下数组中一块heapArena虚拟内存空间区域分配，

分为三个区域，分别是：

• spans区域：存放span指针地址的地方，每个指针大小是8Byte
• bitmap区域：用于标记arena区域中哪些地址保存了对象, 并且对象中哪些地址包含了指针，主要用于GC
• arena区域：heap区域，程序内存分配的地方，管理的最小基本单位是页，golang一个page的大小是：8KB

可以看出spans大小等于arenaSize/8KB，可以理解为有多少page就准备出对应数量的“地址格子”，来充分保证能存下所有的span地址。

对于bitmap区域，由于bitmap是用来标记每个地址空间的使用情况，我们知道指针大小是8Byte，因此需要arenaSize/8个，一个bitmap可以标记四个地址，因此再除4。

介绍完三个区域，我们再来看一下central [numSpanClasses]，它就是管理的所有规格mcentral的集合，同样是134种，pad对齐填充用于确保 mcentrals 以 CacheLineSize 个字节数分隔，所以每一个 MCentral.lock 都可以获取自己的缓存行。而fixalloc类型的相关成员都是用来分配span、mache等对象的内存分配器，这里大家不要搞晕，具体来讲，以span举例，每一个span也需要空间存储，这个就是在spanalloc这个二叉树堆上存储，拿到这个对象，将startAddr 指向arena区域内的npages的内存空间才是给mcache使用的，或者说给P进行对象分配的。另外，由于mheap也是公共资源，一定也要有锁的存在。

下面结合图看一下：

从上图可以更清楚的看到，一个mheap会有134种mcentral，而每一种规格的mcentral会挂载该规格的mspan链表。

前面我们讲过tiny对象和小对象的内存分配，那大于 32KB 的对象怎么办呢？golang将大于32KB的对象定义为大对象，直接通过 mheap 分配。这些大对象的申请是以一个全局锁为代价的，所以同时只能服务一个P申请，大对象内存分配一定是页（8KB）的整数倍。

不管多大对象，一切的空间都是从mheap获取的，那mheap要是不足了呢？就只能向操作系统申请了。

内存分配原则

针对待分配对象的大小不同有不同的分配逻辑：
(0, 16B) 且不包含指针的对象： Tiny分配
(0, 16B) 包含指针的对象：小对象分配
[16B, 32KB] : 小对象分配
(32KB, -) : 大对象分配

、、

• tiny对象内存分配，直接向mcache的tiny对象分配器申请，如果空间不足，则向mcache的tinySpanClass规格的span链表申请，如果没有，则向mcentral申请对应规格mspan，依旧没有，则向mheap申请，最后都用光则向操作系统申请。
• 小对象内存分配，先向本线程mcache申请，发现mspan没有空闲的空间，向mcentral申请对应规格的mspan，如果mcentral对应规格没有，向mheap申请对应页初始化新的mspan，如果也没有，则向操作系统申请，分配页。
• 大对象内存分配，直接向mheap申请spanclass=0，如果没有则向操作系统申请。

总结

Golang内存分配是个相当复杂的过程，其中还掺杂了GC的处理。
总的分配过程，

获取当前p的mcahce->
根基对象的大小计算出合适的class->
是否为指针对象->
从mcache的alloc[class]的链表中查询是否存在可用的span->
如果mcache没有可用的span则从mcentral申请一个新的span加入mcache中->
如果mcentral中也没有可用的span则从mheap中申请一个新的span加入mcentral->
从该span中获取到空闲对象地址并返回

1、Golang程序启动时申请一大块内存并划分成spans、bitmap、arena区域
2、arena区域按页划分成一个个小块。
3、span管理一个或多个页。
4、mcentral管理多个span供线程申请使用
5、mcache作为线程私有资源，资源来源于mcentral。

---