程序中的数据和变量都会被分配到程序所在的 虚拟内存 中，内存空间包含两个重要区域 栈区 （Stack）和 堆区 （Heap）。函数调用的参数、返回值以及局部变量大都会被分配到栈上，这部分内存会由编译器进行管理；不同编程语言使用不同的方法管理堆区的内存，C++ 等编程语言会由工程师主动申请和释放内存，Go 等编程语言会由工程师和编译器共同管理，堆中的对象由 内存分配器 分配并由 垃圾收集器 回收。Go 语言程序内置 运行时 ，内存分配器是运行时的一个组件。

一、分配方法

编程语言的内存分配器一般包含两种分配方法，一种是 线性分配器 （Sequential Allocator，Bump Allocator），另一种是 空闲链表分配器 （Free-List Allocator）。

1、线性分配器

线性分配（Bump Allocator）是一种高效的内存分配方法，但是有较大的局限性。当我们在编程语言中使用线性分配器，我们只需要在内存中维护一个指向内存特定位置的指针，当用户程序申请内存时，分配器只需要检查剩余的空闲内存、返回分配的内存区域并修改指针在内存中的位置。
根据线性分配器的原理，我们可以推测它有较快的执行速度，以及较低的实现复杂度；但是线性分配器无法在内存被释放时重用内存。正是因为线性分配器的这种特性，我们需要合适的垃圾回收算法配合使用。标记压缩（Mark-Compact）、复制回收（Copying GC）和分代回收（Generational GC）等算法可以通过拷贝的方式整理存活对象的碎片，将空闲内存定期合并，这样就能利用线性分配器的效率提升内存分配器的性能了。因为线性分配器的使用需要配合具有拷贝特性的垃圾回收算法，所以 C 和 C ++ 等需要直接对外暴露指针的语言就无法使用该策略。

2、空闲链表分配器

空闲链表分配器（Free-List Allocator）可以重用已经被释放的内存，它在内部会维护一个类似链表的数据结构。当用户程序申请内存时，空闲链表分配器会依次遍历空闲的内存块，找到足够大的内存，然后申请新的资源并修改链表。
因为不同的内存块以链表的方式连接，所以使用这种方式分配内存的分配器可以重新利用回收的资源，但是因为分配内存时需要遍历链表，所以它的时间复杂度就是 O(n)。空闲链表分配器可以选择不同的策略在链表中的内存块中进行选择，最常见的就是以下四种方式：

• 首次适应（First-Fit）：从链表头开始遍历，选择第一个大小大于申请内存的内存块；
• 循环首次适应（Next-Fit）：从上次遍历的结束位置开始遍历，选择第一个大小大于申请内存的内存块；
• 最优适应（Best-Fit）：从链表头遍历整个链表，选择最合适的内存块；
• 隔离适应（Segregated-Fit）：将内存分割成多个链表，每个链表中的内存块大小相同，申请内存时先找到满足条件的链表，再从链表中选择合适的内存块；

Go 语言采用的是隔离适应的内存分配策略，将内存分割成由 4、8、16、32 字节的内存块组成的链表，当我们向内存分配器申请 8 字节的内存时，会在 8 字节内存块的链表找到空闲的内存块并返回。隔离适应的分配策略减少了需要遍历的内存块数量，提高了内存分配的效率。

二、分级分配

线程缓存分配（Thread-Caching Malloc，TCMalloc）是用于分配内存的的机制，它比 glibc 中的 malloc 函数还要快很多。Go 语言的内存分配器就借鉴了 TCMalloc 的设计实现高速的内存分配，它的核心理念是使用多级缓存根据将对象根据大小分类，并按照类别实施不同的分配策略。
Go 语言会根据申请分配的内存大小选择不同的处理逻辑，将对象分成微对象（0, 16B）、小对象 [16B, 32KB] 和大对象（32KB, +∞）三种。因为程序中的绝大多数对象的大小都在 32KB 以下，而申请的内存大小影响 Go 语言运行时分配内存的过程和开销，所以分别处理大对象和小对象有利于提高内存分配器的性能。
内存分配器不仅会区别对待大小不同的对象，还会将内存分成不同的级别分别管理，Go 内存分配器引入 线程缓存 （Thread Cache）、 中心缓存 （Central Cache）和 页堆 （Page Heap）三个组件分级管理内存。
线程缓存属于每一个独立的线程，它能够满足线程上绝大多数的内存分配需求，因为不涉及多线程，所以也不需要使用互斥锁来保护内存，这能够减少锁竞争带来的性能损耗。当线程缓存不能满足需求时，就会使用中心缓存作为补充解决小对象的内存分配问题；在遇到 32KB 以上的对象时，内存分配器就会选择页堆直接分配大量的内存。
这种多层级的内存分配设计与计算机操作系统中的多级缓存也有些类似，因为多数的对象都是小对象，我们可以通过线程缓存和中心缓存提供足够的内存空间，发现资源不足时就从上一级组件中获取更多的内存资源。

注：go 语言是没有线程的，这里的线程指的是 go 语言的协程。

三、内存划分

在 Go 语言 1.10 以前的版本，堆区的内存空间都是连续的；但是在 1.11 版本，Go 团队使用稀疏的堆内存空间替代了连续的内存，解决了连续内存带来的限制以及在特殊场景下可能出现的问题。

1、线性内存

Go 语言程序的 1.10 版本在启动时会初始化整片虚拟内存区域，分为三个区域 spans、bitmap 和 arena 分别预留了 512MB、16GB 以及 512GB 的内存空间。

• spans 区域存储了指向内存单元 runtime.mspan 的指针，每个内存单元会管理几页的内存空间，每页大小为 8KB；
• bitmap 用于标识 arena 区域中的那些地址保存了对象，位图中的每个字节都会表示堆区中的 32 字节是否包含空闲；
• arena 区域是真正的堆区，运行时会将 8KB 看做一页，这些内存页中存储了所有在堆上初始化的对象；

对于任意一个地址，我们都可以根据 arena 的基地址计算该地址所在的页数并通过 spans 数组获得管理该片内存单元 runtime.mspan，spans 数组中多个连续的位置可能对应同一个 runtime.mspan。
Go 语言在垃圾回收时会根据指针的地址判断对象是否在堆中，并通过上一段中介绍的过程找到管理该对象的 runtime.mspan。这些都建立在堆区的内存是连续的这一假设上。这种设计虽然简单并且方便，但是在 C 和 Go 混合使用时会导致程序崩溃：

• 分配的内存地址会发生冲突，导致堆的初始化和扩容失败；
• 没有被预留的大块内存可能会被分配给 C 语言的二进制，导致扩容后的堆不连续；
  线性的堆内存需要预留大块的内存空间，但是申请大块的内存空间而不使用是不切实际的，不预留内存空间却会在特殊场景下造成程序崩溃。虽然连续内存的实现比较简单，但是这些问题我们也没有办法忽略。

2、稀疏内存

稀疏内存是 Go 语言在 1.11 中提出的方案，使用稀疏的内存布局不仅能移除堆大小的上限，还能解决 C 和 Go 混合使用时的地址空间冲突问题。不过因为基于稀疏内存的内存管理失去了内存的连续性这一假设，这也使内存管理变得更加复杂。
运行时使用二维的 runtime.heapArena 数组管理所有的内存，每个单元都会管理 64MB 的内存空间：

type heapArena struct {
    bitmap [heapArenaBitmapBytes]byte
    spans [pagesPerArena]*mspan
    pageInUse [pagesPerArena / 8]uint8
    pageMarks [pagesPerArena / 8]uint8
    zeroedBase uintptr
}

该结构体中的 bitmap 和 spans 与线性内存中的 bitmap 和 spans 区域一一对应，zeroedBase 字段指向了该结构体管理的内存的基地址。这种设计将原有的连续大内存切分成稀疏的小内存，而用于管理这些内存的元信息也被切分成了小块。
不同平台和架构的二维数组大小可能完全不同，在 Linux 的 x86-64 架构上，二维数组的一维大小会是 1，而二维大小是 4,194,304，因为每一个指针占用 8 字节的内存空间，所以元信息的总大小为 32MB。由于每个 runtime.heapArena 都会管理 64MB 的内存，整个堆区最多可以管理 256TB 的内存，这比之前的 512GB 多好几个数量级。

四、地址空间

因为所有的内存最终都是要从操作系统中申请的，所以 Go 语言的运行时构建了操作系统的内存管理抽象层，该抽象层将运行时管理的地址空间分成以下的四种状态：

每一个不同的操作系统都会包含一组特定的方法，这些方法可以让内存地址空间在不同的状态之间做出转换。下面是 Linux 操作系统的方法。

• runtime.sysAlloc 会从操作系统中获取一大块可用的内存空间，可能为几百 KB 或者几 MB；
• runtime.sysFree 会在程序发生内存不足（Out-of Memory，OOM）时调用并无条件地返回内存；
• runtime.sysReserve 会保留操作系统中的一片内存区域，对这片内存的访问会触发异常；
• runtime.sysMap 保证内存区域可以快速转换至准备就绪；
• runtime.sysUsed 通知操作系统应用程序需要使用该内存区域，需要保证内存区域可以安全访问；
• runtime.sysUnused 通知操作系统虚拟内存对应的物理内存已经不再需要了，它可以重用物理内存；
• runtime.sysFault 将内存区域转换成保留状态，主要用于运行时的调试；
  运行时使用 Linux 提供的 mmap、munmap 和 madvise 等系统调用实现了操作系统的内存管理抽象层，抹平了不同操作系统的差异，为运行时提供了更加方便的接口，除了 Linux 之外，运行时还实现了 BSD、Darwin、Plan9 以及 Windows 等平台上抽象层。

五、内存布局

Go 语言的内存分配器包含内存单元、线程缓存、中心缓存和页堆几个重要组件，分别对应运行时的数据结构 runtime.mspan、runtime.mcache、runtime.mcentral 和 runtime.mheap。

所有的 Go 语言程序都会在启动时初始化如上图所示的内存布局，每一个线程都会被分配一个线程缓存 runtime.mcache 用于处理微对象和小对象的分配，它们会持有内存单元 runtime.mspan。每个类别的内存单元都会管理特定大小的对象，当内存管理单元中不存在空闲对象时，它们会从 runtime.mheap 持有的 134 个中心缓存 runtime.mcentral 中获取新的内存单元，中心缓存属于全局的堆结构体 runtime.mheap，它会从操作系统中申请内存。
在 amd64 的 Linux 操作系统上，runtime.mheap 会持有 4,194,304runtime.heapArena。

runtime.mspan 是 Go 语言内存管理的基本单元，该结构体中包含 next 和 prev 两个字段，它们分别指向了前一个和后一个 runtime.mspan：

type mspan struct {
    next *mspan
    prev *mspan
    ...
}

串联后的上述结构体会构成如下双向链表，运行时会使用 runtime.mSpanList 存储双向链表的头结点和尾节点并在线程缓存以及中心缓存中使用。因为相邻的管理单元会互相引用，所以我们可以从任意一个结构体访问双向链表中的其他节点。
每个 runtime.mspan 都管理 npages 个大小为 8KB 的页，这里的页不是操作系统中的内存页，它们是操作系统内存页的整数倍，该结构体会使用下面的这些字段来管理内存页的分配和回收：

type mspan struct {
    startAddr uintptr // 起始地址
    npages    uintptr // 页数
    freeindex uintptr

    allocBits  *gcBits
    gcmarkBits *gcBits
    allocCache uint64
    ...
}

• startAddr 和 npages：确定该结构体管理的多个页所在的内存，每个页的大小都是 8KB；
• freeindex：扫描页中空闲对象的初始索引；
• allocBits 和 gcmarkBits：分别用于标记内存的占用和回收情况；
• allocCache：allocBits 的补码，可以用于快速查找内存中未被使用的内存；

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

type mspan struct {
    ...
    state       mSpanStateBox
    ...
}

该状态可能处于 mSpanDead、mSpanInUse、mSpanManual 和 mSpanFree 四种情况。当 runtime.mspan 在空闲堆中，它会处于 mSpanFree 状态；当 runtime.mspan 已经被分配时，它会处于 mSpanInUse、mSpanManual 状态，这些状态会在遵循以下规则发生转换：

• 在垃圾回收的任意阶段，可能从 mSpanFree 转换到 mSpanInUse 和 mSpanManual；
• 在垃圾回收的清除阶段，可能从 mSpanInUse 和 mSpanManual 转换到 mSpanFree；

• 在垃圾回收的标记阶段，不能从 mSpanInUse 和 mSpanManual 转换到 mSpanFree；
  设置 runtime.mspan 结构体状态的读写操作必须是原子性的避免垃圾回收造成的线程竞争问题。
  runtime.spanClass 是 runtime.mspan 结构体的类别，它决定了内存单元中存储的对象大小和个数。本质是一个 uint8 类型的整数，它的前 7 位存储着内存单元 mspan 种类的 ID，最后一位表示是否包含指针，该类型提供的两个方法能够帮我们快速获取对应的字段。

  type mspan struct {

    ...
    spanclass   spanClass
    ...

  }

Go 语言的内存管理模块中一共包含 67 类的内存单元 mspan，每一类内存单元都会存储特定大小的对象并且包含特定数量的页数以及对象，所有的数据都会被预选计算好并存储在 runtime.class_to_size 和 runtime.class_to_allocnpages 等变量中。运行时中还包含 ID 为 0 的特殊跨度类，它能够管理大于 32KB 的特殊对象。

1、线程缓存

runtime.mcache 是 Go 语言中的线程缓存，主要用来缓存线程申请的微小对象。每一个线程缓存都持有 67* 2 个 runtime.mspan，这些内存管理单元都存储在结构体的 alloc 字段中。线程缓存在刚刚被初始化时是不包含 runtime.mspan 的，只有当用户程序申请内存时才会从上一级组件获取新的 runtime.mspan 满足内存分配的需求。
运行时在初始化处理器时会调用 runtime.allocmcache 初始化线程缓存，该函数会在系统栈中使用 runtime.mheap 中的线程缓存分配器初始化新的 runtime.mcache 结构体。初始化后的 runtime.mcache 中的所有 runtime.mspan 都是空的占位符 emptymspan。
runtime.mcache.refill 方法会为线程缓存获取一个指定类别的内存单元，被替换的单元不能包含空闲的内存空间，而获取的单元中需要至少包含一个空闲对象用于分配内存。该函数会从中心缓存中申请新的 runtime.mspan 存储到线程缓存中，这也是向线程缓存中插入内存管理单元的唯一方法。
线程缓存中还包含几个用于分配微对象的字段，下面的这三个字段组成了微对象分配器，专门为 16 字节以下的对象申请和管理内存：

type mcache struct {
    tiny             uintptr
    tinyoffset       uintptr
    local_tinyallocs uintptr
}

微分配器只会用于分配非指针类型的内存，上述三个字段中 tiny 会指向堆中的一篇内存，tinyOffset 是下一个空闲内存所在的偏移量，最后的 local_tinyallocs 会记录内存分配器中分配的对象个数。

2、中心缓存

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

type mcentral struct {
    lock      mutex
    spanclass spanClass
    nonempty  mSpanList
    empty     mSpanList
    nmalloc uint64
}

每一个中心缓存都会管理某个类别的内存单元，它会同时持有两个 runtime.mSpanList，分别存储包含空闲对象的列表和不包含空闲对象的链表。该结构体在初始化时，两个链表都不包含任何内存，程序运行时会扩容结构体持有的两个链表，nmalloc 字段也记录了该结构体中分配的对象个数。
线程缓存会通过中心缓存的runtime.mcentral.cacheSpan方法获取新的内存管理单元，可以将其分成以下几个部分：

• 从有空闲对象的 runtime.mspan 链表中查找可以使用的内存单元；
• 从没有空闲对象的 runtime.mspan 链表中查找可以使用的内存单元；
• 调用 runtime.mcentral.grow 从堆中申请新的内存单元；
• 更新内存管理单元的 allocCache 等字段帮助快速分配内存；
  无论通过哪种方法获取到了内存单元，该方法的最后都会对内存单元的 allocBits 和 allocCache 等字段进行更新，让运行时在分配内存时能够快速找到空闲的对象。
  中心缓存的扩容方法 runtime.mcentral.grow 会根据预先计算的 class_to_allocnpages 和 class_to_size 获取待分配的页数以及 spanClass 并调用 runtime.mheap.alloc 获取新的 runtime.mspan 结构。

3、页堆

runtime.mheap 是内存分配的核心结构体，Go 语言程序只会存在一个全局的结构，而堆上初始化的所有对象都由该结构体统一管理，该结构体中包含两组非常重要的字段，其中一个是全局的中心缓存列表 central，另一个是管理堆区内存区域的 arenas 以及相关字段。
页堆中包含一个长度为 134 的 runtime.mcentral 数组，其中 67 个为不同类别的 scan 的中心缓存，另外的 67 个是 noscan 的中心缓存，通过 runtime.spanClass 索引。堆区的初始化会使用runtime.mheap.init方法，该方法初始化了非常多的结构体和字段，不过其中初始化的两类变量比较重要：

• spanalloc、cachealloc 以及 arenaHintAlloc 等 runtime.fixalloc 类型的空闲链表分配器；
• central 切片中 runtime.mcentral 类型的中心缓存；
  该方法中初始化所有的中心缓存，这些中心缓存会维护全局的内存单元，各个线程会通过中心缓存获取新的内存单元。运行时会通过它的runtime.mheap.alloc方法在系统栈中获取新的 runtime.mspan。runtime.mheap.grow方法会向操作系统申请更多的内存空间，传入的页数经过对齐可以得到期望的内存大小。

六、内存分配

堆上所有的对象都会通过调用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, +∞)：直接在堆上分配内存；

运行时对于大于 32KB 的大对象会单独处理，不会从线程缓存或者中心缓存中获取内存管理单元，而是直接在系统的栈中调用runtime.largeAlloc函数分配大片的内存，函数会计算分配该对象所需要的页数，它会按照 8KB 的倍数为对象在堆上申请内存。