golang笔记——Go堆内存管理

前言

本文主要记录个人学习Golang堆内存管理，涉及到的相关内容，算是对个人所学知识点的梳理与总结。从非常宏观的角度看，Go的堆内存管理就是下图这个样子

学习内存管理，肯定首先需要了解内存管理的基本知识，我会按照内存管理基础知识-->TCMalloc-->Go堆内存管理基础概念-->Go堆内存分配流程，这样的顺序来逐步梳理相关知识。内存管理基础知识

1. 存储器与内存

在计算机的组成结构中有一个很重要的部分是存储器。它是用来存储程序和数据的部件。对于计算机来说，有了存储器，才有记忆功能，才能保证正常工作。存储器的种类很多。按其用途可分为主存储器（也称为内存储器，简称内存）和辅助存储器（也称为外存储器）。

外存储器主要是指除计算机内存及CPU缓存以外的储存器，此类储存器一般断电后仍然能保存数据。常见的外存储器有硬盘、软盘、光盘、U盘等。

内存一般采用半导体存储单元，包括随机存储器（RAM），只读存储器（ROM），以及高速缓存（CACHE）。

只读存储器 ROM（Read Only Memory）
只能读出，一般不能写入，即使机器停电，这些数据也不会丢失。一般用于存放计算机的基本程序和数据，如BIOS ROM。
随机存储器 RAM（Random Access Memory）
既可以从中读取数据，也可以写入数据。当机器电源关闭时，存于其中的数据就会丢失。
RAM分为两种：动态存储芯片（DRAM）和静态存储芯片（SRAM）。
1. DRAM：DRAM结构较简单且集成度高，通常用于制造内存条中的存储芯片。
2. SRAM：SRAM速度快且不需要刷新操作，但集成度差和功耗较大，通常用于制造容量小但效率高的CPU缓存。
高速缓存 Cache
高速缓冲存储器是存在于主存与CPU之间的一级存储器，由静态存储芯片(SRAM)组成，容量比较小但速度比主存高得多，接近于CPU的速度。由于从1980年开始CPU和内存速率差距在不断拉大，为了弥补这2个硬件之间的速率差异，所以在CPU跟内存之间增加了比内存更快的Cache，Cache是内存数据的缓存，可以降低CPU访问内存的时间。

三级Cache分别是L1、L2、L3，它们的速率是三个不同的层级，L1速率最快，与CPU速率最接近，是RAM速率的100倍，L2速率就降到了RAM的25倍，L3的速率更靠近RAM的速率。

寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。

那么当CPU要去读取来自远程网络服务器上的磁盘文件时，就是由CPU直接和远程服务器磁盘交互吗？事实当然不是这样的。由于CPU的执行速率远远高于外部存储的读写速率，所以当CPU去读取磁盘中数据时，通常会先查看离自己最近的寄存器是否有缓存对应的数据，如果存在想要的数据就会直接获取。而寄存器的读写速率十分接近CPU，将数据缓存在寄存其中可以极大地提升执行效率，避免低效的磁盘读写降低性能。

由于计算机的存储体系中，存储量越大越低廉的存储设备往往读写越慢，存储量越小越昂贵的存储设备往往读写越快。而为了存储更多的数据，大量数据往往存储在读写慢的存储设备上。为了让CPU在执行读写操作时，执行效率尽可能地不被读写慢的存储设备影响，于是下图中的存储器层次结构便孕育而生了。

存储器层次结构的主要思想，就是让读写更快的存储设备作为读写慢但容量更大的存储器的高速缓存，让CPU每次优先访问上层读写更快的设备，尽量减少与低效存储设备的读写交互，以保证计算机的整体性能。

2. 虚拟内存

2.1 为什么使用虚拟内存

计算机对于内存真正的载体是物理内存条,这个是实打实的物理硬件容量，所以在操作系统中定义这部份的容量叫物理内存（主存）。物理内存的布局实际上就是一个内存大数组，如图所示。

每一个元素都会对应一个地址，称之为物理内存地址。那么CPU在运算的过程中，如果需要从内存中取1个字节的数据，就需要基于这个数据的物理内存地址去运算即可，而且物理内存地址是连续的，可以根据一个基准地址进行偏移来取得相应的一块连续内存数据。

一个操作系统是不可能只运行一个程序的，当N个程序共同使用同一个物理内存时，就会存在以下问题：

1. 内存资源是稀缺的，每个进程为了保证自己能够运行，会为自己申请额外大的内存，导致空闲内存被浪费
2. 物理内存对所有进程是共享的，多进程同时访问同一个物理内存会存在并发问题

为了解决以上问题，操作系统便引入了虚拟内存。通过虚拟内存作为物理内存和进程之间的中间层，让进程通过虚拟内存来访问物理内存。引入了虚拟内存后的操作系统如图所示。

用户程序（进程）只能使用虚拟的内存地址来获取数据，进程会通过页表中的虚拟内存地址查看Memory Map，判断当前要访问的虚拟内存地址，是否已经加载到了物理内存。如果已经在物理内存，则取物理内存数据，如果没有对应的物理内存，则从磁盘加载数据到物理内存，并把物理内存地址和虚拟内存地址更新到页表。

引入虚拟内存后，每个进程都有各自的虚拟内存，内存的并发访问问题的粒度从多进程级别，可以降低到多线程级别。从程序的角度来看，它觉得自己独享了一整块内存，且不用考虑访问冲突的问题。系统会将虚拟地址翻译成物理地址，从内存上加载数据。但如果仅仅把虚拟内存直接理解为地址的映射关系，那就是过于低估虚拟内存的作用了。

虚拟内存的目的是为了解决以下几件事：
（1）物理内存无法被最大化利用。
（2）程序逻辑内存空间使用独立。
（3）内存不够，继续虚拟磁盘空间。

2.2 读时共享，写时复制

读时共享，写时复制

上图所示如果一个进程需要进行写操作，则这个内存将会被复制一份，成为当前进程的独享内存。如果是读操作，可能多个进程访问的物理空间是相同的空间。

如果一个内存几乎大量都是被读取的，则可能会多个进程共享同一块物理内存，但是他们的各自虚拟内存是不同的。当然这个共享并不是永久的，当其中有一个进程对这个内存发生写，就会复制一份，执行写操作的进程就会将虚拟内存地址映射到新的物理内存地址上。

2.3 虚拟内存映射磁盘空间

对于第（3）点，是虚拟内存为了最大化利用物理内存，如果进程使用的内存足够大，则导致物理内存短暂的供不应求，那么虚拟内存也会“开疆拓土”从磁盘（硬盘）上虚拟出一定量的空间，挂在虚拟地址上，而且这个动作进程本身是不知道的，因为进程只能够看见自己的虚拟内存空间，如下图所示。

综上可见虚拟内存的重要性，不仅提高了利用率而且整条内存调度的链路完全是对用户态物理内存透明，用户可以安心的使用自身进程独立的虚拟内存空间进行开发。

3. 页、页表、页表条目

单位名称

有效位	集合特征
1	虚拟内存已创建和分配页，已缓存在物理内存中。
0	虚拟内存还未分配或创建。
0	虚拟内存已创建和分配页，但未缓存在物理内存中。

4. CPU访问内存过程

当某个进程进行一次内存访问指令请求，将触发上图的内存访问，具体的访问流程如下：

Virtual Page Numberoffset

5. 局部性

一个优秀的程序通常具有良好的局部性，它们通常会重复使用已用过的数据，或者使用已用过数据的邻近数据，也就是说，程序常常会使用集中在一起的局部数据。局部性分为：时间局部性和空间局部性。

空间局部性：一个内存位置被引用过一次，在短时间内，其附近的内存位置也将被引用。（内存都是按页读取，读取1个内存位置后，其所在页的内存数据会被缓存，所以再次读取其附近的内存位置效率更高）
时间局部性：被引用过一次的内存位置，在短时间内将被多次引用。（执行效率越高的缓存，容量越小。读取1个内存位置后，长时间不再读取此内存位置，会有新的内存位置被缓存，该内存位置可能不再存在缓存中）

6. 栈和堆

Linux为每个进程维护了一个单独的虚拟地址空间，并且这个地址空间是连续的，进程就可以很方便地访问内存，也就是我们常说的虚拟内存。虚拟内存形式如下图所示。

一个进程的地址空间通常包括代码段、数据段、堆、栈等，地址从低到高。代码中使用的内存地址都是虚拟内存地址，而不是实际的物理内存地址。栈和堆只是虚拟内存上2块不同功能的内存区域。在x64架构中，使用rsp寄存器指向栈顶；在x86架构中，使用esp寄存器指向栈顶的内存地址。一般可以简称为sp。

由编译器自动分配和释放，速度快
栈中存储着函数的入参以及局部变量，这些参数（如函数参数、函数返回地址，局部变量、临时变量等）会随着函数的创建而创建，函数的返回而销毁。(通过 CPU push & release)
栈的特性：后入先出LIFO
栈需要存储函数中的局部变量和参数，函数又是最后调用的最先销毁，栈的后进先出正好满足这一点。
栈由高地址向低地址扩展，栈内是连续分配内存的
如果给一个数组或对象分配内存，栈会选择还没分配的最小的内存地址给数组，在这个内存块中，数组中的元素从低地址到高地址依次分配（不要和栈的从高到低弄混了）。所以数组中第一个元素的其实地址对应于已分配栈的最低地址。
栈只能获取栈顶的内存地址
栈是从高地址往低地址扩展的，栈顶正好指向数组的起始地址，即数组的指针。

栈桢

栈帧本质上是一种栈
栈帧本质上是一种栈。栈帧是指函数在被调用时，所拥有的一块独立的用于存放函数所使用的状态和变量的栈空间。
函数的每次进入，都对应1个栈桢
每个函数都对应有一个栈帧。同一个函数多次调用，每次可能会分配到不同的栈帧。整个栈的内容在同一个时刻可以看作是由许多栈帧依序“堆叠”组成的。栈桢的结构详见下图。

对于一个运行中的函数，其使用的栈帧区域被sp和bp寄存器限定（对于x86，sp等价esp，bp等价rsp；对于x64，sp等价rsp，bp等价rbp）。bp指向栈帧的底部，sp指向栈帧的顶部。
在函数中使用的所有变量（本地变量、实参），一般使用bp定位。设N为整型字节数，bp+2N是第一个实参的地址，bp-N是第一个本地变量的地址。

自由分配，自己申请，自己释放（否则发生内存泄漏），速度较慢，更灵活
堆的特性：先入先出FIFO
堆的内存地址是不连续的，由低地址向高地址扩展，一般是链表结构

由于栈都会随着函数的创建而创建，函数的返回而销毁。所以我们大多时候谈到的内存管理，都是对堆内存的管理。

TCMalloc

Golang的内存管理是基于TCMalloc的核心思想来构建的。在了解Golang的内存管理之前，一定要了解TCMalloc（Thread Cache Malloc）的内存申请模式。随着Go的迭代，Go的内存管理与TCMalloc不一致地方在不断扩大，但其主要思想、原理和概念都是和TCMalloc一致的，如果跳过TCMalloc直接去看Go的内存管理，也许你会似懂非懂。本节将介绍TCMalloc的基础理念和结构。

在Linux操作系统中，其实有不少的内存管理库，内存管理库的本质都是在多线程编程下，追求更高内存管理效率：更快的分配是主要目的。

通过引入虚拟内存，使每个进程拥有自己独立的虚拟内存，让内存的并发访问问题的粒度从多进程级别，降低到多线程级别。然而同一进程下的所有线程仍会共享相同的内存空间，它们申请内存时需要加锁，如果不加锁就存在同一块进程内存被2个线程同时访问的问题。

TCMalloc的做法是什么呢？为每个线程预分配一块缓存，线程申请小内存时，可以从缓存分配内存，这样有2个好处：

预分配缓存需要进行1次系统调用，后续线程申请小内存时直接从缓存分配，都是在用户态执行的，没有了系统调用，缩短了内存总体的分配和释放时间
多个线程同时申请小内存时，从各自的缓存分配，不再需要加锁

1. 基本原理

结合上图，我们依次介绍下TCMalloc的几个重要概念：

Page
TCMalloc执行内存管理的一种单位。操作系统执行内存管理以页单位，TCMalloc里的Page大小与操作系统里的页大小并不一定相等，而是整数倍关系。《TCMalloc解密》里称x64下Page大小是8KB。
Span
一个或多个连续的Page 组成一个 Span，Span是TCMalloc中内存管理的基本单位，多个这样的Span就用链表来管理。比如可以有1个Page大小的Span，也可以有2个Page大小的Span，Span比Page高一个层级，是为了方便管理一定大小的内存区域。
每个Span记录了第一个起始Page的编号Start，和一共有多少个连续Page的数量Length。
Size Class
Size Class是空间规格。TCMalloc会将这些小对象集合划分成多个内存刻度，同属于一个刻度类别下的内存集合称之为属于一个Size Class。每个Size Class都对应一个大小比如8字节、16字节、32字节等。在申请小对象内存的时候，TCMalloc会根据使用方申请的空间大小就近向上取最接近的一个Size Class的Span（由多个等空间的Page组成）内存块返回给使用方。
如果将Size Class、Span、Page用一张图来表示，则具体的抽象关系如下图所示
ThreadCache
ThreadCache是每个线程各自的Cache，一个Cache包含多个空闲内存块链表，每个链表连接的都是大小相同的内存块。也可以说按内存块大小，给内存块分了个类，这样可以根据申请的内存大小，快速从合适的链表选择空闲内存块。

由于每个线程有自己的ThreadCache，所以ThreadCache访问是无锁的。
CentralCache
CentralCache是所有线程共享的缓存，也是保存的空闲内存块链表，链表的数量与ThreadCache中链表数量相同，当ThreadCache的内存块不足时，可以从CentralCache获取内存块；当ThreadCache内存块过多时，可以放回CentralCache。

由于CentralCache是共享的，所以它的访问是要加锁的。
PageHeap
PageHeap是对堆内存的抽象，PageHeap存的是若干Span链表。
如下图所示，分别是1页Page的Span链表，2页Page的Span链表等，最后是large span set用来保存中、大对象。为了方便Span和Span之间的管理，Span集合是以双向链表的形式构建。

当CentralCache的内存不足时，会从PageHeap获取空闲的内存Span，然后把1个Span拆成若干内存块，添加到对应大小的链表中并分配内存；当CentralCache的内存过多时，会把空闲的内存块放回PageHeap中。毫无疑问，PageHeap也是要加锁的。

2. 分配流程

TCMalloc中对于对象类型的划分：

小对象大小：0~256KB
中对象大小：257~1MB
大对象大小：>1MB

TCMalloc内存分配流程：

小对象的分配流程
ThreadCache -> CentralCache -> HeapPage，大部分时候，ThreadCache缓存都是足够的，不需要去访问CentralCache和HeapPage，无系统调用配合无锁分配，分配效率是非常高的。
具体分配流程，详见下图
中对象分配流程
中对象为大于256KB且小于等于1MB的内存。直接在PageHeap中选择适当的大小即可，128 Pages的Span所保存的最大内存就是1MB。
具体分配流程，详见下图
大对象分配流程
对于超过128个Page（即1MB）的内存分配则为大对象分配流程。从PageHeap中的large span set选择合适数量的页面组成span，用来存储数据。
具体分配流程，详见下图

Go堆内存管理

1. Go内存模型层级结构

Golang内存管理模型与TCMalloc的设计极其相似。基本轮廓和概念也几乎相同，只是一些规则和流程存在差异。

2. Go内存管理的基本概念

Go内存管理的许多概念在TCMalloc中已经有了，含义是相同的，只是名字有一些变化。

2.1 Page

与TCMalloc中的Page相同，x64架构下1个Page的大小是8KB。Page表示Golang内存管理与虚拟内存交互内存的最小单元。操作系统虚拟内存对于Golang来说，依然是划分成等分的N个Page组成的一块大内存公共池。

2.2 mspan

与TCMalloc中的Span一致。mspan概念依然延续TCMalloc中的Span概念，在Golang中将Span的名称改为mspan,1个mspan为多个Page(go中为8KB的内存大小)。1个mspan对应1个或多个大小相同的object，mspan主要用于分配对象的区块，下图简单说明了Span的内部结构。

mspan结构体如下：

type mspan struct {
    next *mspan     // 在mspan链表中，指向后一个mspan
    prev *mspan     // 在mspan链表中，指向前一个mspan
    list *mSpanList // 供debug使用
    startAddr uintptr // mspan起始地址
    npages    uintptr // 当前mspan对应的page数
    manualFreeList gclinkptr // mSpanManual状态mspan中的可用对象链表
    // freeindex是slot索引，标记下一次分配对象时应该开始搜索的地址, 分配后freeindex会增加
    // 每一次分配都从freeindex开始扫描allocBits，直到它遇到一个表示空闲对象的0
    // 在freeindex之前的元素都是已分配的, 在freeindex之后的元素有可能已分配, 也有可能未分配
    freeindex uintptr
    nelems uintptr // 当前span中object数量.

    // allocCache是从freeindex位置开始的allocBits缓存
    allocCache uint64

    // allocBits用于标记哪些元素是已分配的, 哪些元素是未分配的。
    // 使用freeindex + allocBits可以在分配时跳过已分配的元素, 把对象设置在未分配的元素中.
    allocBits  *gcBits
    // 用于在gc时标记哪些对象存活, 每次gc以后allocBits都会与gcmarkBits保持一致
    gcmarkBits *gcBits

    // 清理代数，每GC1次sweepgen会+2
    // sweepgen=currrent sweepgen - 2：该span需要被清扫
    // sweepgen=currrent sweepgen - 1：该span正在被清扫
    // sweepgen=currrent sweepgen：该span已被清扫，带使用
    // sweepgen=currrent sweepgen + 1：该span在清扫开始前，仍然被缓存，需要被清扫
    // sweepgen=currrent sweepgen + 3：该span已被清扫，仍然被缓存
    sweepgen    uint32
    divMul      uint32        // for divide by elemsize
    allocCount  uint16        // 已分配对象的数量
    spanclass   spanClass
    state       mSpanStateBox
    needzero    uint8         // 在分配前需要清零
    elemsize    uintptr       // 对象大小
    limit       uintptr       // span数据末尾
    speciallock mutex         // specials链表的锁
    specials    *special      // 根据object偏移量排序的special链表.
}

mspan的allocBits是一个bitmap，用于标记哪些元素是已分配的, 哪些元素是未分配的。通过使用allocBits已经可以达到O(1)的分配速度，但是go为了极限性能，对其做了一个缓存allocCache，allocCache是从freeindex开始的allocBits缓存。

2.3 Size Class

Golang内存管理针对衡量内存的概念又更加详细了很多，这里面介绍一些基础的有关内存大小的名词及算法。

Object Class

Page是Golang内存管理与操作系统交互时，衡量内存容量的基本单元
Object是用来存储一个变量数据的内存空间，是Golang内存管理为对象分配存储内存的基本单元

Size Class

_NumSizeClasses = 68

Span Class

通过设置两种span，让GC扫描对象的时候，对于noscan的span可以不去查看bitmap区域来标记子对象。也就是说进行扫描的时候，直接判定该span中的对象不会存在引用对象，不再进行更深层的扫描，这样可以大幅提升GC Mark的效率。

具体Span Class与Size Class的逻辑结构关系如下图所示。

其中Size Class和Span Class的对应关系计算方式可以参考Golang源代码，如下：

//usr/local/go/src/runtime/mheap.go

type spanClass uint8 

//……(省略部分代码)

func makeSpanClass(sizeclass uint8, noscan bool) spanClass {
   return spanClass(sizeclass<<1) | spanClass(bool2int(noscan))
}

//……(省略部分代码)

makeSpanClass()函数为通过Size Class来得到对应的Span Class，其中第二个形参noscan表示当前对象是否需要GC扫描
，不难看出来Span Class 和Size Class的对应关系公式如下表所示：

对象	Size Class 与 Span Class对应公式
需要GC扫描是否存在引用对象	Span Class = Size Class * 2 + 0
不需要GC扫描是否存在引用对象	Span Class = Size Class * 2 + 1

Golang源码里列举了详细的Size Class和Object大小、存放Object数量，以及每个Size Class对应的Span内存大小关系，我们这里只展示部分：

//usr/local/go/src/runtime/sizeclasses.go

package runtime

// [class]: Size Class
// [bytes/obj]: Object Size，一次对外提供内存Object的大小
// [bytes/span]: 当前Object所对应Span的内存大小
// [objects]: 当前Span一共有多少个Object
// [tail waste]: 当前Span平均分N份Object后，会有多少内存浪费。 ===> [bytes/span]%[bytes/obj]
// [max waste]: 当前Size Class最大可能浪费的空间所占百分比。 ===> （(本级Object Size – (上级Object Size + 1)）*本级Object数量) + [tail waste]）/ 本级Span Size

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

由以上源码可见，并没有列举Size Class为0的规格刻度内存。对于Span Class为0和1的，也就是对应Size Class为0的规格刻度内存，mcache实际上是没有分配任何内存的。因为Golang内存管理对内存为0的数据申请做了特殊处理，如果申请的数据大小为0将直接返回一个固定内存地址，不会走Golang内存管理的正常逻辑，详见以下源码

//usr/local/go/src/runtime/malloc.go

// Al Allocate an object of size bytes.                                     
// Sm Small objects are allocated from the per-P cache's free lists.        
// La Large objects (> 32 kB) are allocated straight from the heap.         
func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {                        
// ……（省略部分代码）

if size == 0 {
return unsafe.Pointer(&zerobase)
}

//……（省略部分代码）
}

zerobase

golang中[0]int、 struct{}等，全部的0内存对象分配，返回的都是一个固定的地址。

max waste为当前Size Class最大可能浪费的空间所占百分比计算方式，详见下图

2.4 MCache

mcache与TCMalloc中的ThreadCache类似，但也有所不同。
相同点：都保存的是各种大小的Span，并按Span class分类，小对象直接从此分配内存，起到了缓存的作用，并且可以无锁访问
不同点：TCMalloc中是1个线程1个ThreadCache，Go中是1个P拥有1个mcache，两者绑定关系的区别如下图所示

如果将上图的mcache展开，来看mcache的内部构造，则具体的结构形式如下图6所示

当其中某个Span Class的MSpan已经没有可提供的Object时，MCache则会向MCentral申请一个对应的MSpan。mcache在初始化时是没有任何mspan资源的，在使用过程中会动态地申请，不断地去填充 alloc[numSpanClasses]*mspan，通过双向链表连接。

下面具体看一下mcache在源码中的定义：

//go:notinheap
type mcache struct { 
   
   tiny             uintptr //<16byte 申请小对象的起始地址
   tinyoffset       uintptr //从起始地址tiny开始的偏移量
   local_tinyallocs uintptr //tiny对象分配的数量   

   alloc [numSpanClasses]*mspan // 分配的mspan list，其中numSpanClasses=67*2，索引是splanclassId

   stackcache [_NumStackOrders]stackfreelist //栈缓存

  
   local_largefree  uintptr                  // 大对象释放字节数
   local_nlargefree uintptr                  // 释放的大对象数量
   local_nsmallfree [_NumSizeClasses]uintptr // 每种规格小对象释放的个数

 
   flushGen uint32 //扫描计数
}

MCache中每个Span Class都只会对应一个MSpan对象，不同Span Class的MSpan的总体长度不同，参考runtime/sizeclasses.go的标准规定划分。比如对于Span Class为4的MSpan来说，存放内存大小为1Page，即8KB。每个对外提供的Object大小为16B，共存放512个Object。其他Span Class的存放方式类似。

[16B,32KB]

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)
//alloc中查到
span := c.alloc[spc]

而对于更小的对象，我们叫它tiny对象，golang会通过tiny和tinyoffset组合寻找位置分配内存空间，这样可以更好的节约空间，源码如下：

off := c.tinyoffset
//根据不同大小内存对齐
if size&7 == 0 {
   off = round(off, 8)
} else if size&3 == 0 {
   off = round(off, 4)
} else if size&1 == 0 {
   off = round(off, 2)
}
if off+size <= maxTinySize && c.tiny != 0 {
   // tiny+偏移量
   x = unsafe.Pointer(c.tiny + off)
   c.tinyoffset = off + size
   c.local_tinyallocs++
   mp.mallocing = 0
   releasem(mp)
   return x
}
// 空间不足从alloc重新申请空间用于tiny对象分配
span := c.alloc[tinySpanClass]

2.5 MCentral

MCentral与TCMalloc中的Central概念依然相似。向MCentral申请Span是同样是需要加锁的。
当MCache的某个级别Span的内存被分配光时，它会向MCentral申请1个当前级别的Span。

Goroutine、MCache、MCentral、MHeap互相交换的内存单位是不同，其中协程逻辑层与MCache的内存交换单位是Object，MCache与MCentral、MCentral与MHeap的内存交换单位是Span，MHeap与操作系统的内存交换单位是Page。

MCentral与TCMalloc中的Central不同的是：CentralCache是每个级别的Span有1个链表，mcache是每个级别的Span有2个链表。如下图所示。

MCentral属于MHeap，MCentral是各个规格的mcentral集合，实际上1个mcentral对应1个Span Class，即Span Class个mcentral小内存管理单元。对应源码为:

type mheap struct {
    ......
    central [numSpanClasses]struct {
        mcentral mcentral
        pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
    }
    ......
}

NonEmpty Span List
表示还有可用空间的Span链表。链表中的所有Span都至少有1个空闲的Object空间。如果MCentral上游MCache退还Span，会将退还的Span加入到NonEmpty Span List链表中。
Empty Span List
表示没有可用空间的Span链表。该链表上的Span都不确定是否存在空闲的Object空间。如果MCentral提供给一个Span给到上游MCache，那么被提供的Span就会加入到Empty List链表中。

注意在Golang 1.16版本之后，MCentral中的NonEmpty Span List 和 Empty Span List
均由链表管理改成集合管理，分别对应Partial Span Set 和 Full Span Set。虽然存储的数据结构有变化，但是基本的作用和职责没有区别。

下面是MCentral层级中其中一个Size Class级别的MCentral的定义Golang源代码（V1.14版本）:

//usr/local/go/src/runtime/mcentral.go  , Go V1.14

// Central list of free objects of a given size.
// go:notinheap
type mcentral struct {
  lock      mutex      //申请MCentral内存分配时需要加的锁

  spanclass spanClass //当前哪个Size Class级别的

  // list of spans with a free object, ie a nonempty free list
  // 还有可用空间的Span 链表
  nonempty  mSpanList 

  // list of spans with no free objects (or cached in an mcache)
  // 没有可用空间的Span链表，或者当前链表里的Span已经交给mcache
  empty     mSpanList 

  // 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是从该mcentral分配的对象的累积计数
  // 假设mcaches中的所有跨度都已完全分配。
  // 以原子方式书写，在STW下阅读。
  nmalloc uint64
}

在GolangV1.16版本的相关MCentral结构代码如下：

//usr/local/go/src/runtime/mcentral.go  , Go V1.16+

//…

type mcentral struct {
  // mcentral对应的spanClass
  spanclass spanClass

  partial  [2]spanSet // 维护全部空闲的Span集合
  full     [2]spanSet // 维护存在非空闲的Span集合
}

//…

新版本的改进是将List变成了两个Set集合，Partial集合与NonEmpty Span List责任类似，Full集合与Empty Span List责任类似。可以看见Partial和Full都是一个[2]spanSet类型，也就每个Partial和Full都各有两个spanSet集合，这是为了给GC垃圾回收来使用的，其中一个集合是已扫描的，另一个集合是未扫描的。

2.6 MHeap

Golang内存管理的MHeap依然是继承TCMalloc的PageHeap设计。MHeap的上游是MCentral，MCentral中的Span不够时会向MHeap申请。MHeap的下游是操作系统，MHeap的内存不够时会向操作系统的虚拟内存空间申请。访问MHeap获取内存依然是需要加锁的。
MHeap是对内存块的管理对象，是通过Page为内存单元进行管理。那么用来详细管理每一系列Page的结构称之为一个HeapArena，它们的逻辑层级关系如下图所示。

一个HeapArena占用内存64MB，其中里面的内存的是一个一个的mspan，当然最小单元依然是Page，图中没有表示出mspan，因为多个连续的page就是一个mspan。所有的HeapArena组成的集合是一个arenas [1]*[4M]*heapArena数组，运行时使用arenas 管理所有的内存。

mheap是Golang进程全局唯一的，所以访问依然加锁。图中又出现了mcentral，因为mcentral本也属于mheap中的一部分。只不过会优先从MCentral获取内存，如果没有mcentral会从Arenas中的某个heapArena获取Page。

heapArena结构体如下：

type heapArena struct {   
   bitmap [heapArenaBitmapBytes]byte  // 用于标记当前这个HeapArena的内存使用情况，1. 对应地址中是否存在过对象、对象中哪些地址包含指针，2. 是否被GC标记过。主要用于GC
   spans [pagesPerArena]*mspan  //  存放heapArena中的span指针地址
   pageInUse [pagesPerArena / 8]uint8   // 保存哪些spans处于mSpanInUse状态
   pageMarks [pagesPerArena / 8]uint8   // 保存哪些spans中包含被标记的对象
   pageSpecials [pagesPerArena / 8]uint8  // 保存哪些spans是特殊的
   checkmarks *checkmarksMap  // debug.gccheckmark state
   zeroedBase uintptr  //该arena第一页的第一个字节地址
}

根据heapArena结构体，我们可以了解到mheap内存空间的逻辑视图如下所示：

其中arena区域就是我们通常说的heap, go从heap分配的内存都在这个区域中。
其中spans区域用于表示arena区中的某一页(Page)属于哪个span，spans区域中一个指针(8 byte)对应了arena区域中的一页(在go中一页=8KB)。所以spans的大小是 512GB / 页大小(8KB) * 指针大小(8 byte) = 512MB。spans区域和arenas区域的对应关系如下图所示：

其中每个HeapArean包含一个bitmap，其作用是用于标记当前这个HeapArena的内存使用情况。

1个bitmap的逻辑结构图如下所示：

1个bitmap是8bit，每一个指针大小的内存都会有两个bit分别表示是否应该继续扫描和是否包含指针，这样1个byte就会对应arena区域的四个指针大小的内存。当前HeapArena中的所有Page均会被bitmap所标记，bitmap的主要作用是服务于GC垃圾回收模块。

bitmap中的byte和arena的对应关系从末尾开始, 也就是随着内存分配会向两边扩展

MHeap里面相关的数据结构和指针依赖关系，可以参考下图：

mheap结构体如下：

type mheap struct {
    lock  mutex    //必须在系统堆栈上获得，否则当G持有锁时，堆栈增长，可能会自我死锁
    pages pageAlloc // page分配器数据结构
    sweepgen     uint32 // 记录span的sweep及cache状态
    sweepDrained uint32 // 所有的span都已被清扫，或都正在被清扫
    sweepers     uint32 // 启动的swepper数量
    allspans []*mspan // 曾经创建的所有mspans地址的切片，allspans的内存是手动管理的，可以随着堆的增长而重新分配和移动。
                      // 一般来说，allspans受到mheap_.lock的保护，它可以防止并发访问以及释放后备存储。
                      // 在STW期间的访问可能不会持有锁，但必须确保访问周围不能发生分配（因为这可能会释放支持存储）。
    pagesInUse         uint64  // pages所属的spans处于状态mSpanInUse; 原子式更新
    pagesSwept         uint64  // 本周期内被清扫的pages数; 原子式更新
    pagesSweptBasis    uint64  // 被用作Proportional sweep模式原点的pagesSwept; 原子式更新
    sweepHeapLiveBasis uint64  // gcController.heapLive的值，作为扫描率的原点；带锁写入，不带锁读取。
    sweepPagesPerByte  float64 // Proportional sweep比例; 写时有锁，读时无锁
    // TODO(austin): pagesInUse should be a uintptr, but the 386 compiler can't 8-byte align fields.
    scavengeGoal uint64     // 维持的总的保留堆内存量（运行时试图通过向操作系统返回内存来维持该内存量，该内存量由heapRetained衡量）。
    reclaimIndex uint64 // 下一个要回收的page在allArenas中的索引
    reclaimCredit uintptr

    // arenas是*heapArena的map. 它指向整个可用的虚拟地址空间的每一个arena帧的堆的元数据。
    // 这是一个两级映射，由一个L1映射和可能的许多L2映射组成。当有大量的arena时，这可以节省空间
    arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena
    heapArenaAlloc linearAlloc // 用于分配heapArena对象的预留空间。这只在32位上使用，我们预先保留这个空间以避免与堆本身交错。
    arenaHints *arenaHint // arenaHints是一个地址列表，用于标记哪里的heap arenas需要扩容
    arena linearAlloc // 是一个预先保留的空间，用于分配heap arenas。只用在32位操作系统

    allArenas []arenaIdx // 所有arena序号集合，可以根据arenaIdx算出对应arenas中的那一个heapArena
    sweepArenas []arenaIdx // sweepArenas是在扫描周期开始时对所有Arenas的快照，通过禁用抢占可以安全读取
    markArenas []arenaIdx // markArenas是在标记周期开始时对所有Arenas的快照，由于allArenas只可向后追加，并且标记不会修改该切片内容，所以可以安全读取

    //curArena是堆当前正在扩容的区域，curArena总是与physPageSize对齐
    curArena struct {
        base, end uintptr
    }

    // central 是存放small size classes的列表
    central [numSpanClasses]struct {
        mcentral mcentral
        // pad确保mcentrals间隔CacheLinePadSize字节，以便每个mcentral.lock得到它自己的缓存行
        pad      [cpu.CacheLinePadSize - unsafe.Sizeof(mcentral{})%cpu.CacheLinePadSize]byte
    }

    spanalloc             fixalloc // allocator for span*
    cachealloc            fixalloc // allocator for mcache*
    specialfinalizeralloc fixalloc // allocator for specialfinalizer*
    specialprofilealloc   fixalloc // allocator for specialprofile*
    specialReachableAlloc fixalloc // allocator for specialReachable
    speciallock           mutex    // lock for special record allocators.
    arenaHintAlloc        fixalloc // allocator for arenaHints

    unused *specialfinalizer // never set, just here to force the specialfinalizer type into DWARF
}

arenaHint结构体为：

type arenaHint struct {
    addr uintptr // 为指向的对应heapArena首地址。
    down bool // 为当前的heapArena是否可以扩容。
    next *arenaHint // 指向下一个heapArena所对应的ArenaHint首地址。
}

3. 内存分配规则

介绍完内存管理基本概念，我们再来总结一下内存分配规则，流程图如下：

3.1 Tiny对象分配流程

判断对象大小是否小于maxSmallSize=32KB，如果小于32KB则进入Tiny对象或小对象申请流程，否则进入大对象申请流程。
判断对象大小是否小于maxTinySize=16B并且对象中是否包含指针，如果大于16B或包含指针，则进入小对象申请流程，否则进入Tiny对象申请流程
Tiny对象申请流程后，会先获取mcache目前的tinyoffset，再根据申请tiny对象的大小及mcache.tinyoffset值，进行内存对齐，计算出满足内存对齐后的对象插入位置offset
如果从插入位置offset插入对象后，不超出16B，并且存在待分配的tiny空间，则将对象填充到该tiny空间，并将地址返回给M，结束内存申请
如果当前的tiny空间不足，则通过nextFreeFast(span)查找span中一个可用对象地址，存在则返回地址，并结束内存申请
如果span中不存在一个可用对象，则调用mcache.nextFree(tinySpanClass)从mcentral申请1个相同规格的msapn。申请成功则结束流程

3.2 小对象分配流程

进入小对象申请流程后，通过mcache.alloc(spc)获取1个指定规格的mspan
通过nextFreeFast(span)查找span中一个可用对象地址，存在则返回地址给协程逻辑层P，P得到内存空间，流程结束
如果不存在可用对象，则通过mcache.nextFree(tinySpanClass)中mcache.refill(spc)从mcentral申请1个相同规格的msapn
4.mcache.refill(spc)中，会首先尝试通过mcentral的noempty list获取mspan，获取不到则在尝试通过mcentral的empty list获取mspan（1.16之后，通过mcentral.cacheSpan()从partial set获取mspan，获取不到则从full set获取可回收的mspan）。mcache成功获取mcentral返回的mspan后，返回可用对象地址，结束申请流程
mcache中empty List（1.16之后，full set）也没有可回收的mspan，则会调用mcache.grow()函数，从mheap中申请内存
mheap收到内存请求从其中一个heapArena从取出一部分pages返回给mcentral；当mheap没有足够的内存时，mheap会向操作系统申请内存，将申请的内存也保存到heapArena中的mspan中。mcentral将从mheap获取的由Pages组成的mspan添加到对应的span class链表或集合中
最后协程业务逻辑层得到该对象申请到的内存，流程结束

3.3 大对象分配流程

进入大对象分配流程后，会调用mcache.allocLarge()方法申请大对象
mcache.allocLarge()中主要的mspan申请链路为：mheap.alloc -> mheap.allocSpan，mheap.allocSpan为申请mspan的核心方法。mheap.allocSpan会首先判断申请的page数是否小于P.pageCache的最大page数，如果P.pageCache满足需要，则会从P.mspancache获取mspan地址给P，流程结束
P.pageCache不足，则对mheap加锁，从mheap.pageAlloc这种Radix tree（基数树）数据结构中查找可用的page，协程逻辑层P得到内存，流程结束
mheap.pageAlloc中查找不存在可用的page，则调用mheap.grow()向操作系统申请内存。申请成功后，再次从mheap.pageAlloc中查找可以page，P得到内存后，流程结束

References:
https://zhuanlan.zhihu.com/p/76802887
https://zhuanlan.zhihu.com/p/404813126
https://studygolang.com/articles/22500?fr=sidebar
https://www.yuque.com/aceld/golang/qzyivn
https://u.geekbang.org/lesson/267
https://u.geekbang.org/lesson/279
https://baike.baidu.com/item/%E5%86%85%E5%AD%98/103614
https://www.bilibili.com/video/BV1KD4y1U7Rr
https://www.zhihu.com/question/25142664
https://goalong.github.io/2019/09/20/%E8%BF%9B%E7%A8%8B%E4%B8%AD%E7%9A%84%E5%A0%86%E5%92%8C%E6%A0%88
https://blog.csdn.net/sandonz/article/details/117742864
https://ctfbook.ph0en1x.com/reverse/zhan-3001-zhan-zheng-yu-han-shu-diao-yong
https://www.cnblogs.com/jiujuan/p/13869547.html
https://note.youdao.com/noteshare?id=f843698db192fbbc887252f64d2214bd
https://zhuanlan.zhihu.com/p/266496735
https://zhuanlan.zhihu.com/p/53581298
https://www.cnblogs.com/zkweb/p/7880099.html