不会飞的章鱼

熟能生巧，勤能补拙；念念不忘，必有回响。

Go高级工程师_第5课_Go语⾔的内存管理与垃圾回收

发表于 更新于 分类于
本文字数： 6.1k 阅读时长 ≈ 6 分钟

基本概念

发问

内存从哪⾥来？到哪里去？

标记对象从哪⾥来？到哪里去？

垃圾从哪⾥来？到哪里去？

栈上内存分配

栈分配，函数调⽤返回后，函数栈帧⾃动销毁(SP 下移)

栈分配

堆分配

在 C 语⾔中，返回函数的局部变量会怎么样？ 

1
2
3
4
5
6
int *func(void)
{
    int num = 1234;

    return #
}

悬垂指针：Dangling pointer
可能触发：Segmentation fault!!!!

逃逸分析

堆分配，在 Go 语⾔⾥，为什么我们不⽤担⼼ dangling pointer? 

1
2
3
4
5
6
7
//escape.go
package main

func main() {
    var m = make([]int,10240)
    println(m[0])
}

逃逸分析探究

如何找到所有逃逸分析的可能性:

⾼难度模式

cmd/compile/internal/gc/escape.go

低难度模式

https://github.com/golang/go/tree/master/test

内存管理中的⻆⾊

内存需要分配，谁来分配：⾃动 allocator，⼿⼯分配;
内存需要回收，谁来回收：⾃动 collector，⼿⼯回收。

⾃动内存回收技术=垃圾回收技术

内存管理中的三个⻆⾊

  • Mutator：fancy(花哨的) word for application，其实就是你写的应⽤程序，它会不断地修改对象的引⽤关系，即对象图。
  • Allocator：内存分配器，负责管理从操作系统中分配出的内存空间，malloc 其实底层就有⼀个内存分配器的实现(glibc 中)，tcmalloc 是malloc 多线程改进版。Go 中的实现类似 tcmalloc。
  • Collector：垃圾收集器，负责清理死对象，释放内存空间。

Mutator、Allocator、Collector 概览：

内存管理抽象

每个操作系统都有相应的实现，如：mem_linux.go,mem_windows.go
相关的抽象描述在 runtime/malloc.go 注释中

进程虚拟内存布局

内存的分配类型

进程虚拟内存分布：

进程虚拟内存分布，多线程的情况：

Allocator基础

  • Bump/Sequential Allocator
  • Free List Allocator

memory-management-and-and-garbage-collection

Free List Allocator 详解：

  • First-Fi
  • Next-Fi
  • Best-Fi
  • Segregated-Fi

memory-management-and-and-garbage-collection

malloc实现

Go 语⾔的栈内存管理

当你执⾏ malloc 时：

  • brk 只能通过调整 programbreak位置推动堆增⻓
  • mmap 可以从任意未分配位置映射内存

内存的分配类型


Go 语⾔内存分配

为什么⼈⾁管理内存不靠谱，复杂对象图维护时的 danglingpointer：

memory-management-and-and-garbage-collection

Go 语⾔内存分配

⽼版本，连续堆：

新版本，稀疏堆：

申请稀疏堆时，我们该⽤ brk 还是 mmap?

Heap grow

分配⼤⼩分类：

  • Tiny : size < 16 bytes && has no pointer(noscan)
  • Small ：has pointer(scan) || (size >= 16 bytes && size <= 32 KB)
  • Large : size > 32 KB

内存分配器在 Go 语⾔中维护了⼀个多级结构：mcache -> mcentral -> mheap

mcache：与 P 绑定，本地内存分配操作，不需要加锁。
mcentral：中⼼分配缓存，分配时需要上锁，不同 spanClass 使⽤不同的锁。
mheap：全局唯⼀，从 OS 申请内存，并修改其内存定义结构时，需要加锁，是个全局锁。

sizeClass 分类(sizeClass = spanClass >> 1)

Class 0/1 预留给 large 了

堆内存管理-内存分配

Small alloc

Large alloc

⼤对象分配会直接越过 mcache、mcentral，直接从 mheap进⾏相应数量的 page 分配。

pageAlloc 结构经过多个版本的变化，从：freelist -> treap -> radix tree，查找时间复杂度越来越低，结构越来越复杂。

Refill 流程

  • 本地 mcache 没有时触发(mcache.refill
  • 从 mcentral ⾥的 non-empty 链表中找(mcentral.cacheSpan
  • 尝试 sweep mcentral 的 empty，insert sweeped -> non-empty(mcentral.cacheSpan
  • 增⻓ mcentral，尝试从 arena 获取内存(mcentral.grow
  • arena 如果还是没有，向操作系统申请(mheap.alloc

最终还是会将申请到的 mspan 放在 mcache 中。

数据结构总览

数据结构总览

Bitmap 与 allocCache

垃圾回收基础

垃圾分类

语义垃圾(semantic garbage)

有的被称作内存泄露语义垃圾指的是从语法上可达(可以通过局部、全局变量引⽤得到)的对象，但从语义上来讲他们是垃圾，垃圾回收器对此⽆能为⼒。

语法垃圾(syntactic garbage)

语法垃圾是讲那些从语法上⽆法到达的对象，这些才是垃圾收集器主要的收集⽬标。

语义垃圾

语义垃圾(semantic garbage)

语法垃圾

语法垃圾(syntactic garbage)

在 allocOnHeap 返回后，堆上的 a ⽆法访问，便成为了语法垃圾。

常⻅垃圾回收算法

  • 引⽤计数(Reference Counting)：某个对象的根引⽤计数变为 0 时，其所有⼦节点均需被回收。
  • 标记压缩(Mark-Compact)：将存活对象移动到⼀起，解决内存碎⽚问题。
  • 复制算法(Copying)：将所有正在使⽤的对象从 From 复制到 To 空间，堆利⽤率只有⼀半。
  • 标记清扫(Mark-Sweep)：解决不了内存碎⽚问题。需要与能尽量避免内存碎⽚的分配器使⽤，如 tcmalloc。(<— Go 在这⾥)

Visualizing Garbage Collection Algorithms

Go 语⾔垃圾回收

基本流程

1.8 后通过混合 write barrier 消除了第⼆个 stw 中的 stack re-scan，stw 时间⼤⼤减少。

新流程：

程序⼊⼝ && 触发点

垃圾回收⼊⼝：gcStart

GC 标记流程

标记对象从哪⾥来？

  • gcMarkWorker
  • Mark assist
  • mutator write/delete heap pointers

标记对象到哪⾥去？

  • Work buffer
    本地 work buffer => p.gc
    全局 work buffer => runtime.work.ful

  • Write barrier buffe
    本地 write barrier buffer => p.wbBuf

三⾊抽象

⿊：已经扫描完毕，⼦节点扫描完毕。(gcmarkbits = 1，且在队列外。)
灰：已经扫描完毕，⼦节点未扫描完毕。(gcmarkbits = 1, 在队列内)
⽩：未扫描，collector 不知道任何相关信息。

基本流程

⼀些问题

GC 时要注意的问题：

    1. 对象在标记过程中不能丢失
    1. Mark 阶段 mutator 的指向堆的指针修改需要被记录下来
    1. GC Mark 的 CPU 控制要努⼒做到 25% 以内

三⾊抽象的问题，标记过程中对象漏标，导致被意外回收：

memory-management-and-and-garbage-collection

解决丢失问题的理论基础

强三⾊不变性(strong tricolor invariant)

禁⽌⿊⾊对象指向⽩⾊对象

弱三⾊不变性(weak tricolor invariant)

⿊⾊对象指向的⽩⾊对象，如果有灰⾊对象到它的可达路径，那也可以

GC 标记流程-write barrier

barrier 本质是 : snippet of code insert before pointer modify

这就是 writebarrier，是在指针修改前插⼊的⼀个函数调⽤。

252行：指针修改。

Dijkstra barrier：

Yuasa barrier：

Slot 是 Go 代码⾥的被修改的指针对象
Ptr 是 Slot 要修改成的值

问：如果我们在所有指针操作中都加上 Dijkstra barrier 或者 Yuasa barrier，就可以避免对象丢失了，为啥实际的实现没那么简单？
答:因为栈的操作频率极⾼，所以 Go 在栈上指针操作上是不加 barrier 的。

因为 Go 的栈上的指针编辑不加 barrier，所以单独使⽤任意⼀种 barrier 都会有问题

  • Dijkstra 的问题
    会出现栈上⿊指向堆上⽩的情况，该⽩⾊对象之前被堆上对象所指；

  • Yuasa 的问题
    会出现堆上⿊指向堆上⽩的情况，该⽩⾊对象之前被栈上某对象所指。

堆内存管理-write barrier

Dijkstra barrier

优点：

  • 能够保证堆上对象的强三⾊不变性(⽆栈对象参与时)
  • 能防⽌指针从栈被隐藏进堆(因为堆上新建的连接都会被着⾊)

缺点：

  • 不能防⽌栈上的⿊⾊对象指向堆上的⽩⾊对象(这个⽩⾊对象之前是被堆上的⿊/灰指着的)
  • 所以在 mark 结束后需要 stw重新扫描所有 goroutine 栈

memory-management-and-and-garbage-collection

Yuasa barrier

优点：

  • 能够保证堆上的弱三⾊不变性(⽆栈对象参与时)
  • 能防⽌指针从堆被隐藏进栈(因为堆上断开的连接都会被着⾊)

缺点：

  • 不能防⽌堆上的⿊⾊对象指向堆上的⽩⾊对象(这个⽩⾊对象之前是由栈的⿊/灰⾊对象指着的)
  • 所以需要 GC 开始时 STW 对栈做快照

memory-management-and-and-garbage-collectionpage

Hybrid barrier

Reality in Go

Go 实际的混合写屏障：代码在 gcWriteBarrier汇编函数中：

混合屏障会将指针(指向堆的)修改前指向的位置和修改后指向的位置都标灰。

垃圾回收代码流程

  • gcStart -> gcBgMarkWorker && gcRootPrepare，这时 gcBgMarkWorker 在休眠中
  • schedule -> findRunnableGCWorker 唤醒适宜数量的 gcBgMarkWorke
  • gcBgMarkWorker -> gcDrain -> scanobject -> greyobject(set mark bit and put to gcw
  • 在 gcBgMarkWorker 中调⽤ gcMarkDone 排空各种 wbBuf 后，使⽤分布式 termination检查算法，进⼊ gcMarkTermination -> gcSweep 唤醒后台沉睡的 sweepg 和 scvg -> sweep -> wake bgsweep && bgscavenge

堆内存管理-垃圾回收

堆内存管理-垃圾回收-CPU 使⽤控制

  • GC 的 CPU 控制⽬标是整体 25%
  • 当 P = 4 * N 时，只要启动 N 个 worker 就可以。
  • 但 P ⽆法被 4 整除时，需要兼职的 gcMarkWorker 来帮助做⼀部分⼯作
    全职 GC 员⼯：Dedicated worker，需要⼀直⼲活，直到被抢占。
    兼职 GC 员⼯：Fractional worker，达到业绩⽬标(fractionalUtilizationGoal)时可以主动让出。
    还有⼀种 IDLE 模式，在调度循环中发现找不到可执⾏的 g，但此时有标记任务未完成，就⽤开启 IDLE 模式去帮忙。

Worker 运⾏模式在：p.gcMarkWorkerMode

Go 语⾔的栈内存管理

栈本身的内存：newstack,shrinkstack

使⽤ allocManual 和 freeManual 相当于⼿动管理内存，不计⼊ heap_inuse 和 heap_sys；计⼊ stackinuse 和 stacksys

栈上变量的内存：SP 移动销毁，简单快速

sweep 流程(待补充)

References

memorymanagement.org
https://my.eng.utah.edu/~cs4400/malloc.pdf
https://cboard.cprogramming.com/linux-programming/101090-what-differences-between-brk-mmap.html
https://medium.com/a-journey-with-go/go-memory-management-and-memory-sweep-cc71b484de05
https://medium.com/a-journey-with-go/go-memory-management-and-allocation-a7396d430f44
https://spin.atomicobject.com/2014/09/03/visualizing-garbage-collection-algorithms/
https://golangpiter.com/system/attachments/files/000/001/718/original/GP_2019_-_An_Insight_Into_Go_Garbage_Collection.pdf?1572419303
https://www.cnblogs.com/zkweb/p/7880099.html?utm_source=tuicool&utm_medium=referral
https://go.googlesource.com/proposal/+/master/design/17503-eliminate-rescan.md
https://blog.golang.org/ismmkeynote
https://www.ardanlabs.com/blog/2018/12/garbage-collection-in-go-part1-semantics.html
https://docs.google.com/document/d/1wmjrocXIWTr1JxU-3EQBI6BK6KgtiFArkG47XK73xIQ/edit#
https://zhuanlan.zhihu.com/p/95056679

未涉及

Runtime 中 Not in heap 类对象的内存管理
Page alloc && Page cach
Stack alloc && persistentAllo
Tiny 分配时的 offset 对⻬逻辑
为防⽌⻓时间标记导致应⽤请求阻塞，引⼊的 oblet 概念
对象被回收时的 finalizer 执⾏逻辑
Fd 类内置数据结构的引⽤计数逻辑
Sweep 和 Scvg 流程未涉及

------ 本文结束------
如果本篇文章对你有帮助，可以给作者加个鸡腿~(*^__^*)，感谢鼓励与支持！