Go语言为我们做了很多，创建对象不再需要我们手动申请内存，也不用考虑对象使用完后释放内存，这些对开发者来说都是透明的；但是作为一名Go开发者，内存管理和垃圾回收还是有必要深入研究的。毕竟，内存与CPU是程序高效运行的基础。

  Linux为每个进程维护一个单独的虚拟内存空间（组织为一些区域/段的集合，如代码段，数据段，堆，共享库段，以及用户栈都是不同的区域），如下图所示：

  说到这里就不得不提一下系统调用mmap，其要求内核创建一个新的虚拟内存区域（注意是新的区域，和堆是平级关系，即mmap函数并不是在堆上分配内存的）；最好是从地址addr开始（一般传null），并将文件描述fd符指定的对象的一个连续的chunk（大小为len，从文件偏移offset开始）映射到这个新的区域；当fd传-1时，可用于申请分配内存。

  函数mmap声明如下(munmap函数释放该虚拟内存区域)：

void* mmap ( void * addr , size_t len , int prot , int flags , int fd , off_t offset )
int munmap(void *addr, size_t length);

  参数prot描述这个区域的访问控制权限，可以取以下值：

PROT_EXEC //页内容可以被执行
PROT_READ //页内容可以被读取
PROT_WRITE //页可以被写入
PROT_NONE //页不可访问

  参数flags由描述被映射对象类型的位组成，如MAP_SHARED 表示与其它所有映射这个对象的进程共享映射空间；MAP_PRIVATE 表示建立一个写入时拷贝的私有映射，内存区域的写入不会影响到原文件。

  Go语言底层在向操作系统申请内存时，一次申请64M内存，就是通过mmap函数申请的。另外注意，操作系统分配内存通常是按页（4K）分配的，也就是说即使进程申请3K内存，操作系统会分配4K字节。

如何设计动态内存分配器

  Go进程向操作系统一次申请64M内存，那么业务代码需要内存时怎么分配呢？要知道业务申请内存是灵活多变的，申请与释放时机，申请内存块大小等等都是随机的。因此，需要设计一个内存分配器来实现这一类内存分配需求。要实现分配器必须考虑以下几个问题：

1.空闲块组织：如何记录空闲块；如何标记内存块是否空闲；
2.分配：如何选择一个合适的空闲块来处理分配请求；
3.分割：空闲块一般情况会大于实际的分配请求，我们如何处理这个空闲块中的剩余部分；
4.回收：如何处理一个刚刚被释放的块；

• 思考1：空闲块组织

  内存分配与释放请求时完全随机的，最终会造成堆内存被分割为若干个内存小块，其中有些处于已分配状态，有些处于空闲状态；我们需要额外的空间来标记内存状态以及内存块大小； 下图为malloc设计思路：

  注：图中显示额外使用4字节记录当前内存块属性，其中3比特记录是否空闲，29比特记录内存块大小；实际malloc头部格式可能会根据版本等调整；不论我们使用malloc分配多少字节的内存，实际malloc分配的内存都会多几个字节； 注：空闲内存块可能会被组织为一个链表结构，由此可以遍历所有空闲内存块，直到查找到一个满足条件的为止；

• 思考2：如何选择合适的空闲块

  在处理内存分配请求时，需要查找空闲内存链表，找到一个满足申请条件的空闲内存块，选择什么查找算法；而且很有可能存在多个符合条件的空闲内存块，此时如何选择？ 目前有很多比较成熟的算法，如首次适配，最佳适配，最差适配等；

• 思考3：如何分配

  在查找到满足条件的空闲内存块时，此内存一般情况会比实际请求分配的内存空间要大；全部分配给用户，浪费空间；因此一般会将此空闲内存块切割为两个小块内存，一块分配给用户，一块标记为新的空闲内存

• 思考4：如何回收：

  当用户调用free()函数释放内存时，需要将此块内存重新标记为空闲内存，并且插入空闲链表；然而需要注意的是，此块内存可能能够与其他空闲内存拼接为更大的空闲内存；此时还需要算法来处理空闲内存的合并；

• 思考5：内存分配效率问题：

  用户请求分配内存时，需要遍历空闲内存链表，直到查找到一个满足申请条件的空闲内存；由此可见，算法复杂度与链表长度成正比；我们可以将空闲内存按照空间大小组织为多个空闲链表，内存大小相近的形成一个链表；此时只需要根据申请内存大小查找相应空闲链表即可；更进一步的，空闲内存只会被切割为固定大小，如2^n字节，每种字节大小的空闲内存形成一个链表；（用户实际分配的内存是2^n字节，大于用户实际请求）

  总结：任何内存分配器都需要额外的空间（数据结构）记录每个内存块大小及其分配状态

Go版本内存分配器

  Go语言是如何实现这种内存分配器的呢？与上面介绍的malloc一样，在内存块头部额外添加几个字节吗？其实不是的，Go语言是基于bitmap标识的，针对每一个内存块，使用一个比特位表示该内存块空闲与否。

  Go语言内存管理的基本单元是mspan，mspan结构包含字段allocBits（就是bitmap），记录着每一个内存块空闲还是已分配：

type mspan struct {
    // 页数，Go定义页大小为8K
    npages    uintptr // number of pages in span

    //bitmap，记录每一个内存块空闲与否
    allocBits  *gcBits
    //bitmap的缓存，缓存64bit，用于快速查找（De Bruijn算法）
    allocCache uint64

    //每种规格mspan负责分配的内存块大小
    elemsize    uintptr       // computed from sizeclass or from npages
}

  另外，为了提升空闲内存查找效率，Go语言定义了多种规格的mspan，每种规格的mspan只负责分配固定大小的内存块（总计67种规格大小），如下：

// class  bytes/obj  bytes/span  objects  tail waste  max waste  min align
//     1          8        8192     1024           0     87.50%          8
//     2         16        8192      512           0     43.75%         16
//     3         24        8192      341           8     29.24%          8
//     4         32        8192      256           0     21.88%         32
//     5         48        8192      170          32     31.52%         16
......
//    67      32768       32768        1           0     12.50%       8192

  这里只截取了前5种规格的定义，如第一种规格负责分配的内存块大小不超过8字节，每一个mspan大小为8K，所以每一个mspan最多只能分配1024个内存块。max waste是什么呢？表示最大内存浪费比例，想想加入每次只申请一字节内存呢？Go内存分配器也会选择第一种规格的mspan，这样最差情况浪费了7/8的内存（87.50%）。

  对于一个mspan，需要多少比特位表示内存块空闲状态呢？这就与该mspan划分的内存块数目有关了；我们看一下allocBits初始化逻辑：

func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan) {

    // 页*页大小 = 页字节数
    nbytes := npages * pageSize

    //计算mspan最多能分割为多少内存块
    s.nelems = nbytes / s.elemsize

    //申请bitmap
    s.allocBits = newAllocBits(s.nelems)
}

//newAllocBits计算bitmap所需字节数
blocksNeeded := uintptr((nelems + 63) / 64)
bytesNeeded := blocksNeeded * 8

  allocBits存储对应内存块是否空闲，0表示空闲 1表示已分配。参考上面对mspan的介绍，内存申请的逻辑基本也就清楚了：根据申请内存的大小，确定mspan规格，查找bitmap（比特位0），如果找到标记已分配，返回内存块地址。

//内存申请入口
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {

    //根据申请内存大小，计算mspan规格
    sizeclass = size_to_class8[divRoundUp(size, smallSizeDiv)]
    spc := makeSpanClass(sizeclass, noscan)

    //获取对应规格的mspan
    span = c.alloc[spc]

    //查找空闲内存块
    v := nextFreeFast(span)
    x = unsafe.Pointer(v)

    return x
}

  查找空闲内存块其实就是在bitmap中搜索0比特，普通搜索算法时间复杂度为O(n)，Go语言使用De Bruijn算法提升搜索效率。

Go内存管理概述

  Go语言内存管理这么简单吗？显然不是。考虑几个问题，Go语言是多线程程序，肯定会出现多线程并发申请内存的情况，每次申请都需要加锁吗？这显然是不合适的。上面提到Go语言底层在向操作系统申请内存时，一次申请64M内存，但是内存管理的基本单位又是mspan，64M内存怎么转化为mspan呢？最后，内存管理还伴随着垃圾回收（内存释放），这就更复杂了（后面篇章会介绍）。

  如上图所示，每一个逻辑处理器P都缓存着mspan（缓存在p.mcache，是一个数组），这样协程在申请内存时，只需要在当前P的mcache查找空闲内存就行了，这里缓存了所有规格的mcache，定义如下：

type p struct {
    mcache      *mcache
}

type mcache struct {
    // mspan数组，numSpanClasses == 136
    alloc [numSpanClasses]*mspan // spans to allocate from, indexed by spanClass
}

  alloc数组存储所有规则的mspan，数组长度为136。之前介绍不是说mspan只有67种规格吗？这里需要解释下：为了提升垃圾回收效率，Go语言在分配内存时，会考虑要存储的对象是否包含指针，将有指针和无指针的内存分为了两种规格的mspan，这样垃圾回收扫描时，就不会扫描无指针的mspan了。这么一算，mspan规格数应该是67 2 = 134，还有两种规格呢？这两种规格的mspan负责大块内存的分配（大于32768 = 4 8192 = 4page），同样分为有指针和无指针。

  如果当然逻辑处理器P的缓存mcache已经分配完了呢？这时候就只能从全局的mcentral分配了，mcentral同样分为136种规格，每种规格的mcentral存储着一些mspan（可能有空闲内存，可能没有空闲内存；可能已经被垃圾回收标记-清理了，可能只是被垃圾回收标记了但是还没有清理），接下来就是从对应规格的mcentral查找可用的mspan了。

type mheap struct {
    //全局mcentral
    central [numSpanClasses]struct {
        mcentral mcentral
    }
}

type mcentral struct {
    spanclass spanClass

    //partial存储有空闲内存的mspan
    partial [2]spanSet // list of spans with a free object

    //full存储的mspan没有空闲内存
    full    [2]spanSet // list of spans with no free objects
}

  注意多个协程可能会并发访问mcentral，所以这里的一些操作是需要加锁的。参考mcentral结构的定义，查找mspan的逻辑应该是怎么样的呢：1）查找partial已被清理的mspan数组，如果有返回mspan；2）查找partia未被清理的mspan数组，如果有则执行清理工作，并返回该mspan；3）查找full未被清理的mspan数组，如果有则执行清理工作，并返回该mspan。另外，查找mcentral也是有次数限制的，最多遍历查找100次，如果查找100次后还没有找到可用的mspan，则申请新的mspan。

  如果在全局mcentral没有查找到可用的mspan呢？那只能向pageCache申请新的mspan了。同样的，每一个逻辑处理器P都缓存有pageCache（缓存有64个空闲页），用于处理页的分配请求。注意从p.pageCache分配mspan是不需要加锁的。

  如果逻辑处理器P的缓存pageCache也没有足够的空闲页呢？那就通过页分配器pageAlloc分配缓存页呗，页分配器的内存从哪来呢？这里就是从操作系统申请的，而且一次申请64M内存，这块内存称之为heapArena。

  内存分配的入口函数是mallocgc，整个函数调用链路如下所示，有兴趣的读者可以阅读学习;

//内存分配入口
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer
//查找空闲内存块，如果没有申请mspan
func (c *mcache) nextFree(spc spanClass) (v gclinkptr, s *mspan, shouldhelpgc bool)
//获取新的mspan
func (c *mcache) refill(spc spanClass)
//mcentral查找可用mspan
func (c *mcentral) cacheSpan() *mspan
//mcentral申请新的mspan
func (c *mcentral) grow() *mspan
//申请mspan
func (h *mheap) allocSpan(npages uintptr, typ spanAllocType, spanclass spanClass) (s *mspan)
//从p.pageCache申请mspan
func (c *pageCache) alloc(npages uintptr) (uintptr, uintptr)
//pageCache缓存不够，申请新的pageCache
func (p *pageAlloc) allocToCache() pageCache
//pageAlloc申请内存
func (h *mheap) grow(npage uintptr) (uintptr, bool)
func (p *pageAlloc) grow(base, size uintptr)
//向操作系统申请heapArena（64M）
func (h *mheap) sysAlloc(n uintptr) (v unsafe.Pointer, size uintptr)

  什么是内存逃逸呢？一句话解释就是一个对象（变量）本来应该分配在栈上，结果分配到堆内存了。我们都知道一般函数内写的局部变量等，应该是分配在栈上的，随着函数的调用与返回，该局部变量也会同步分配与释放；但是在某些情况下该局部变量是不能分配到栈上的，只能分配到堆内存。

  编译阶段可以通过-m分析内存逃逸的情况，如下：

// -N 禁止编译优化  -l 禁止内联   -m 输出优化详情（包括逃逸分析），可以多个，-m越多输出信息越多（最多4个）
go build -gcflags '-N  -m -m -l' test.go

  举一个例子，假设函数有一个局部变量，同时函数返回了该局部变量的地址，这可以吗？在部分语言如C这种写法是行不通的，因为函数返回后，该局部变量的地址会释放。但是Go语言是允许这种写法的，只是这种情况下，该局部变量会逃逸到堆内存。

package main

import "fmt"

func main() {
    ret := test()
    fmt.Println(ret)
}

func test() *int {
    var num = 10
    return &num
}

/*
go build -gcflags '-N -m -m -l' test.go
# command-line-arguments
./test.go:11:6: num escapes to heap:
./test.go:11:6:   flow: ~r0 = &num:
./test.go:11:6:     from &num (address-of) at ./test.go:12:9
./test.go:11:6:     from return &num (return) at ./test.go:12:2
./test.go:11:6: moved to heap: num
./test.go:7:13: ... argument does not escape
*/

  可以很明显的看到，"moved to heap: num"，说明变量num逃逸到堆上了。

  再比如，假设一个局部变量的赋值给map或者切片呢，而且赋值的不是值而是地址，函数返回后，局部变量也会随之释放，这显然会引起异常，所以这种局部变量也会逃逸到堆内存，如下面程序所示

package main

var score = make(map[int]*int, 0)

func main() {
    s := 100
    score[0] = &s
}

/*
go build -gcflags '-N -m -m -l' test.go
# command-line-arguments
./test.go:6:2: s escapes to heap:
./test.go:6:2:   flow: {heap} = &s:
./test.go:6:2:     from &s (address-of) at ./test.go:7:13
./test.go:6:2:     from score[0] = &s (assign) at ./test.go:7:11
./test.go:6:2: moved to heap: s
./test.go:3:17: make(map[int]*int, 0) escapes to heap:
./test.go:3:17:   flow: {heap} = &{storage for make(map[int]*int, 0)}:
./test.go:3:17:     from make(map[int]*int, 0) (spill) at ./test.go:3:17
./test.go:3:17:     from score = make(map[int]*int, 0) (assign) at ./test.go:3:5
./test.go:3:17: make(map[int]*int, 0) escapes to heap
*/

  可以很明显的看到，"moved to heap: s"，说明变量s逃逸到堆上了。另外，变量score是一个map，make函数底层也是在堆上申请的内存（参考map章节）。

  当然还有其他情况，比如局部变量占用内存非常大，这时候就不适合分配到栈上了，等等，这里就不一一介绍了，简单了解即可。

  本篇文章从虚拟内存开始，逐步介绍了动态内存分配器的设计思路，引入Go语言内存分配设计，最后整体介绍了Go内存管理整个流程，最后还简单介绍了内存逃逸的基本概念。下一篇将结合内存管理的内容，开始介绍垃圾回收实现过程。