Go内存管理源码浅析

前一篇 讲了 Go 的调度机制和相关源码，这里说一下内存的管理，代码片段也都是基于Go 1.12。

简要的背景

一个程序要运行起来，操作系统会分配一块很大的虚拟内存（或者说虚拟空间）供使用，程序实际可能只使用很小的物理内存。可以通过 ps 去查看vss（虚拟）和rss（实际）的部分。

虚拟内存空间一般会分为代码段，数据段，堆，栈等：

内存分段

程序执行时，函数中定义的各种变量，一般位于堆和栈中（上图中黄色、绿色、白色）部分。为了能动态分配内存，让程序运行过程中灵活使用，操作系统提供了很多相关函数，例如mmap/munmap，brk/sbrk，madvise，set_thread_area/get_thread_area等。C语言中malloc，free就是对这些基础函数的封装。

而其他高层语言中，例如Go，把这些对内存的操作完全屏蔽起来，写程序的过程中根本感受不到。

Go语言本身的实现中，内存由runtime自主管理。runtime与操作系统的交互并没有使用malloc这样的函数，而是通过汇编（或cgo）直接调用了mmap等函数。其内存分配核心思想非常类似于 TCMalloc ，不过由于部分特性（gc等）的需求，在TCMalloc的算法和设计上也做了部分修改。

基本概念

Go程序在启动的时候会向操作系统申请一块内存，然后分块管理。核心的结构是mheap, mcentral, mcache, mspan。

1. mheap
   全局，负责从os申请、释放内存。
2. mcentral
   全局，将内存按mspan划分，统一管理。访问需加锁。mcentral划分为_NumSizeClasses（目前是67）种mspan，每种又分为非空（nonempty，代表可以分配）和空（empty，可能是已满，可能是已分配给mcache在使用，代表不能分配）。非空和空分别形成双向链表，方便访问。
3. mcache
   每个P持有自己的mcache，于是获取内存的时候，无锁访问mcache。mcache也划分为_NumSizeClasses（目前是67）种mspan。
   注：很多文章中，认为mcache中的每种mspan也是链表，但是我从代码中看来，好像mcache对每种mspan只会保存一个。这一点待更进一步理解。
4. mspan
   设计的精华，类似tcmalloc的机制。将一个或多个内存页形成一种mspan，一种mspan只负责分配固定size的内存（不足的时候，会向上补足，例如申请7byte，会使用8 byte类型的mspan）。mspan的列表见sizeclasses.go，里面详细记录了每一种mspan的分配规则，可存储object多少，浪费率等。
   这种设计可以保证分配内存尽可能快，且能减少碎片的产生。

mspan, mcache 和 mcentral

相关代码

1. mallocinit

   最初申请内存的地方在runtime/mallocinit(malloc.go)中。

func mallocinit() {
    if class_to_size[_TinySizeClass] != _TinySize {
        throw("bad TinySizeClass")
    }

    testdefersizes()

    if heapArenaBitmapBytes&(heapArenaBitmapBytes-1) != 0 {
        // heapBits expects modular arithmetic on bitmap
        // addresses to work.
        throw("heapArenaBitmapBytes not a power of 2")
    }

    // Copy class sizes out for statistics table.
    for i := range class_to_size {
        memstats.by_size[i].size = uint32(class_to_size[i])
    }

初始化的过程相较于之前的版本，已经有了非常大的变化，不过核心也依然是作各种检查，然后初始化mheap（主要是初始化各种allocator，方便以后allocator真正分配内存。mcentral就是这个时候初始化的），尝试为当前的M（M是什么，参见调度的文章）分配mcache以及根据操作系统设置正确的arenaHints。

2. heapArena

   之前的Go版本里，arena是大小512G的（网上很多图介绍，自行Google）。但我在go1.12源码里发现不是这样了。 mheap_.arenas 是一个二维数组 [L1][L2]heapArena （heapArena存的是对应arena的元数据），维度以及arena本身的大小和寻址bit位数相关，每个arena的起始地址按对应大小对齐。 heapArena 这些元数据本身不存在heap里面。以我自己的机器(64位）为例，属于下图中的第一行。32位机器上是4M。计算方法是：

1 << 48 = 2 ^ 48 = 64M * 1 * 4M (即只有1行，4M列，每个大小64M）

arena大小

的这个二维数组中有些有对应的堆，有些没有（那么就是nil，例如垃圾回收之后，把内存还给了操作系统）。go的内存分配器总是尝试分配连续的arena，这样某些大的span可以跨越arena。

heapArena中bitmap用每2个bit记录一个指针大小（8byte）的内存信息，主要用于gc。spans是一个数组，长度等于一个heap中的页数（每页大小为8k，页数可能为64M/8k，不同架构会不同），每个页可能会指向一个span（即一个mspan指针）。实际上，对于分配的，空闲的和未分配的span，指针情况可能各不相同。pageInUse和pageMarks都是标记页的，按位处理。

3. mache初始化和fixalloc

   再扯回来，第一次分配mcache，这里就涉及到真正的内存分配了。 allocmcache 中可以看到，之前已经初始化了cachealloc，这里调用alloc函数，走到的是 fixalloc 的alloc函数：

func (f *fixalloc) alloc() unsafe.Pointer {
    if f.size == 0 {
        print("runtime: use of FixAlloc_Alloc before FixAlloc_Init\n")
        throw("runtime: internal error")
    }

    if f.list != nil {
        v := unsafe.Pointer(f.list)
        f.list = f.list.next
        f.inuse += f.size
        if f.zero {
            memclrNoHeapPointers(v, f.size)
        }
        return v
    }
    if uintptr(f.nchunk) < f.size {
        f.chunk = uintptr(persistentalloc(_FixAllocChunk, 0, f.stat))
        f.nchunk = _FixAllocChunk
    }

    v := unsafe.Pointer(f.chunk)
    if f.first != nil {
        f.first(f.arg, v)
    }
    f.chunk = f.chunk + f.size
    f.nchunk -= uint32(f.size)
    f.inuse += f.size
    return v
}

nchunk代表目前剩余的大小，size是目标大小。如果nchunk小于size，就从系统申请一块（ _FixAllocChunk 这么大）内存，然后按照size这个固定的大小一点一点用。对于用完释放的，又会存在list属性中，供之后再次使用（使用的时候清零）。实际分配内存是通过persistentalloc一步步调用sysAlloc进而调用mmap分配的。

allocmcache 接下来就会把mcache中各个spanclass对应的mspan初始化为空mspan。

需要注意的是，上面这个特殊的M是这样初始化mcache。其实mcache是应该跟着P的，所以其他的mcache的初始化都是在procresize这个函数里，它在schedinit()中，位于mallocinit()之后。

4. newobject和mallocgc

   上面讲了启动过程的各种初始化。初始化完毕，程序执行的时候，在堆上的对象是通过runtime.newobject函数来分配的。

   什么时候分配在堆，什么时候分配在栈，这又是另外一个值得长篇探讨的问题，称为“逃逸分析”，这里暂不深入。

   newobject的代码位于malloc.go中，它直接调用了mallocgc：

func newobject(typ *_type) unsafe.Pointer {
    return mallocgc(typ.size, typ, true)
}

而mallocgc里面就是包含了分配内存时最核心的顺序和步骤，即小对象从mcache的freelist中开始分配，大对象（大于32k，即maxSmallSize）直接从堆上分配。小对象的分配又分为是否是tiny对象（以maxTinySize=16为界）。

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
...
            size = maxTinySize
        } else {
            var sizeclass uint8
            if size <= smallSizeMax-8 {
                sizeclass = size_to_class8[(size+smallSizeDiv-1)/smallSizeDiv]
            } else {
                sizeclass = size_to_class128[(size-smallSizeMax+largeSizeDiv-1)/largeSizeDiv]
            }
            size = uintptr(class_to_size[sizeclass])
            spc := makeSpanClass(sizeclass, noscan)
            span := c.alloc[spc]
            v := nextFreeFast(span)
            if v == 0 {
                v, span, shouldhelpgc = c.nextFree(spc)
            }
            x = unsafe.Pointer(v)
            if needzero && span.needzero != 0 {
                memclrNoHeapPointers(unsafe.Pointer(v), size)
            }
        }
    } else {
        var s *mspan
        shouldhelpgc = true
        systemstack(func() {
            s = largeAlloc(size, needzero, noscan)
        })
        s.freeindex = 1
        s.allocCount = 1
        x = unsafe.Pointer(s.base())
        size = s.elemsize
    }

    var scanSize uintptr
    if !noscan {
        // If allocating a defer+arg block, now that we've picked a malloc size
        // large enough to hold everything, cut the "asked for" size down to
        // just the defer header, so that the GC bitmap will record the arg block
        // as containing nothing at all (as if it were unused space at the end of
        // a malloc block caused by size rounding).
        // The defer arg areas are scanned as part of scanstack.
        if typ == deferType {
            dataSize = unsafe.Sizeof(_defer{})
        }
        heapBitsSetType(uintptr(x), size, dataSize, typ)
        if dataSize > typ.size {
            // Array allocation. If there are any
            // pointers, GC has to scan to the last
            // element.
            if typ.ptrdata != 0 {
                scanSize = dataSize - typ.size + typ.ptrdata
            }
        } else {
            scanSize = typ.ptrdata
        }
        c.local_scan += scanSize
    }
...

从核心分配代码看，先根据待分配对象size算出实际使用的sizeClass（即mspan的不同分类），然后算出spanClass，这里spanClass（本身是一个uint8）包含了span的size信息和span是否需要scan（用于gc）的信息，相当于mcache中alloc数组的index，数组是按一个noscan sizeClass一个scan sizeClass这样交替排列下去的。

算好这些， 就调用nextFreeFast尝试分配（mcache中），如果不成功，调用nextFree分配（还是mcache中），再不成功，调用memclrNoHeapPointers分配（mcentral或mheap中）。

nextFreeFast相对简单。mspan中allbits记录着哪些元素是已分配的，哪些未分配。alloccache用数字按位代表freeindex开始的

func nextFreeFast(s *mspan) gclinkptr {
    theBit := sys.Ctz64(s.allocCache) // Is there a free object in the 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)
            s.freeindex = freeidx
            s.allocCount++
            return gclinkptr(result*s.elemsize + s.base())
        }
    }
    return 0
}

但为了讲清这里的方式，需要简单了解mspan的内部结构，贴出一张网上盗的图，简单明了：

mspan内部主要结构

所以可以看到，mspan里面用位图记录了元素分配与否，直接查找即可。

nextFree稍微复杂，因为要处理分配不成功，继续向mcentral申请内存的逻辑：

func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool) {
    s = c.alloc[spc]
    shouldhelpgc = false
    freeIndex := s.nextFreeIndex()
    if freeIndex == s.nelems {
        // The span is full.
        if uintptr(s.allocCount) != s.nelems {
            println("runtime: s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
            throw("s.allocCount != s.nelems && freeIndex == s.nelems")
        }
        c.refill(spc)
        shouldhelpgc = true
        s = c.alloc[spc]

        freeIndex = s.nextFreeIndex()
    }

    if freeIndex >= s.nelems {
        throw("freeIndex is not valid")
    }

    v = gclinkptr(freeIndex*s.elemsize + s.base())
    s.allocCount++
    if uintptr(s.allocCount) > s.nelems {
        println("s.allocCount=", s.allocCount, "s.nelems=", s.nelems)
        throw("s.allocCount > s.nelems")
    }
    return
}

其中，refill函数会从mcentral甚至mheap获取mspan。

这块是最主要的分配逻辑。剩下的是tiny object（注意，需要不含指针且足够小）和large object的分配。它们做特殊处理都是因为太小或太大，而不适合适配到某些固定大小。在许多场景中tiny object这种分配策略能显著优化性能。

参考资料

1. https://yq.aliyun.com/articles/652551
2. https://povilasv.me/go-memory-management/
3. http://legendtkl.com/2017/04/02/golang-alloc/
4. https://www.youtube.com/watch?v=3CR4UNMK_Is&t=1009s