GC的实现原理,Go垃圾回收机制剖析

作者: 单机游戏资讯  发布:2019-05-27

GC的实现原理,Go垃圾回收机制剖析。Golang从1.5开始引入了三色GC, 经过多次改进, 当前的1.9版本的GC停顿时间已经可以做到极短.
停顿时间的减少意味着"最大响应时间"的缩短, 这也让go更适合编写网络服务程序.
这篇文章将通过分析golang的源代码来讲解go中的三色GC的实现原理.

转载于:这里

这个系列分析的golang源代码是Google官方的实现的1.9.2版本, 不适用于其他版本和gccgo等其他实现,
运行环境是Ubuntu 16.04 LTS 64bit.
首先会讲解基础概念, 然后讲解分配器, 再讲解收集器的实现.

Golang 从第一个版本以来,GC 一直是大家诟病最多的。但是每一个版本的发布基本都伴随着 GC 的改进。下面列出一些比较重要的改动。
v1.1 STW
v1.3 Mark STW, Sweep 并行
v1.5 三色标记法
v1.8 hybrid write barrier

基础概念

GC 算法简介

GC的实现原理,Go垃圾回收机制剖析。这一小节介绍三种经典的 GC 算法:引用计数(reference counting)、标记-清扫(mark & sweep)、节点复制(Copying Garbage Collection),分代收集(Generational Garbage Collection)。

内存结构

go在程序启动时会分配一块虚拟内存地址是连续的内存, 结构如下:

图片 1

GC的实现原理,Go垃圾回收机制剖析。这一块内存分为了3个区域, 在X64上大小分别是512M, 16G和512G, 它们的作用如下:

arena

arena区域就是我们通常说的heap, go从heap分配的内存都在这个区域中.

GC的实现原理,Go垃圾回收机制剖析。bitmap

bitmap区域用于表示arena区域中哪些地址保存了对象, 并且对象中哪些地址包含了指针.
bitmap区域中一个byte(8 bit)对应了arena区域中的四个指针大小的内存, 也就是2 bit对应一个指针大小的内存.
所以bitmap区域的大小是 512GB / 指针大小(8 byte) / 4 = 16GB.

bitmap区域中的一个byte对应arena区域的四个指针大小的内存的结构如下,
每一个指针大小的内存都会有两个bit分别表示是否应该继续扫描和是否包含指针:

图片 2

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

图片 3

spans

spans区域用于表示arena区中的某一页(Page)属于哪个span, 什么是span将在下面介绍.
spans区域中一个指针(8 byte)对应了arena区域中的一页(在go中一页=8KB).
所以spans的大小是 512GB / 页大小(8KB) * 指针大小(8 byte) = 512MB.

spans区域的一个指针对应arena区域的一页的结构如下, 和bitmap不一样的是对应关系会从开头开始:

图片 4

引用计数

引用计数的思想非常简单:每个单元维护一个域,保存其它单元指向它的引用数量(类似有向图的入度)。当引用数量为 0 时,将其回收。引用计数是渐进式的,能够将内存管理的开销分布到整个程序之中。C 的 share_ptr 使用的就是引用计算方法。
GC的实现原理,Go垃圾回收机制剖析。引用计数算法实现一般是把所有的单元放在一个单元池里,比如类似 free list。这样所有的单元就被串起来了,就可以进行引用计数了。新分配的单元计数值被设置为 1(注意不是 0,因为申请一般都说 ptr = new object 这种)。每次有一个指针被设为指向该单元时,该单元的计数值加 1;而每次删除某个指向它的指针时,它的计数值减 1。当其引用计数为 0 的时候,该单元会被进行回收。虽然这里说的比较简单,实现的时候还是有很多细节需要考虑,比如删除某个单元的时候,那么它指向的所有单元都需要对引用计数减 1。那么如果这个时候,发现其中某个指向的单元的引用计数又为 0,那么是递归的进行还是采用其他的策略呢?递归处理的话会导致系统颠簸。关于这些细节这里就不讨论了,可以参考文章后面的给的参考资料。
优点

  • 渐进式。内存管理与用户程序的执行交织在一起,将 GC 的代价分散到整个程序。不像标记-清扫算法需要 STW (Stop The World,GC 的时候挂起用户程序)。
  • 算法易于实现。
  • 内存单元能够很快被回收。相比于其他垃圾回收算法,堆被耗尽或者达到某个阈值才会进行垃圾回收。

缺点

  • 原始的引用计数不能处理循环引用。大概这是被诟病最多的缺点了。不过针对这个问题,也除了很多解决方案,比如强引用等。

  • 维护引用计数降低运行效率。内存单元的更新删除等都需要维护相关的内存单元的引用计数,相比于一些追踪式的垃圾回收算法并不需要这些代价。

  • 单元池 free list 实现的话不是 cache-friendly 的,这样会导致频繁的 cache miss,降低程序运行效率。

什么时候从Heap分配对象

很多讲解go的文章和书籍中都提到过, go会自动确定哪些对象应该放在栈上, 哪些对象应该放在堆上.
简单的来说, 当一个对象的内容可能在生成该对象的函数结束后被访问, 那么这个对象就会分配在堆上.
在堆上分配对象的情况包括:

  • 返回对象的指针
  • 传递了对象的指针到其他函数
  • 在闭包中使用了对象并且需要修改对象
  • 使用new

在C语言中函数返回在栈上的对象的指针是非常危险的事情, 但在go中却是安全的, 因为这个对象会自动在堆上分配.
GC的实现原理,Go垃圾回收机制剖析。go决定是否使用堆分配对象的过程也叫"逃逸分析".

标记-清扫

标记-清扫算法是第一种自动内存管理,基于追踪的垃圾收集算法。算法思想在 70 年代就提出了,是一种非常古老的算法。内存单元并不会在变成垃圾立刻回收,而是保持不可达状态,直到到达某个阈值或者固定时间长度。这个时候系统会挂起用户程序,也就是 STW,转而执行垃圾回收程序。垃圾回收程序对所有的存活单元进行一次全局遍历确定哪些单元可以回收。算法分两个部分:标记(mark)清扫(sweep)。标记阶段表明所有的存活单元,清扫阶段将垃圾单元回收。可视化可以参考下图。

图片 5

标记清扫算法过程

标记-清扫算法的优点也就是基于追踪的垃圾回收算法具有的优点:避免了引用计数算法的缺点(不能处理循环引用,需要维护指针)。缺点也很明显,需要 STW。

GC Bitmap

GC在标记时需要知道哪些地方包含了指针, 例如上面提到的bitmap区域涵盖了arena区域中的指针信息.
除此之外, GC还需要知道栈空间上哪些地方包含了指针,
因为栈空间不属于arena区域, 栈空间的指针信息将会在函数信息里面.
另外, GC在分配对象时也需要根据对象的类型设置bitmap区域, 来源的指针信息将会在类型信息里面.

总结起来go中有以下的GC Bitmap:

  • bitmap区域: 涵盖了arena区域, 使用2 bit表示一个指针大小的内存
  • 函数信息: 涵盖了函数的栈空间, 使用1 bit表示一个指针大小的内存 (位于stackmap.bytedata)
  • 类型信息: 在分配对象时会复制到bitmap区域, 使用1 bit表示一个指针大小的内存 (位于_type.gcdata)
三色标记算法

三色标记算法是对标记阶段的改进,原理如下:

  1. 起初所有对象都是白色。
  2. 从根出发扫描所有可达对象,标记为灰色,放入待处理队列。
  3. 从队列取出灰色对象,将其引用对象标记为灰色放入队列,自身标记为黑色,并放入黑色集合中。
  4. 重复 3,直到灰色对象队列为空。此时白色对象即为垃圾,进行回收。

可视化如下:

图片 6

三色标记法过程

三色标记的一个明显好处是能够让用户程序和 mark 并发的进行,具体可以参考论文:《On-the-fly garbage collection: an exercise in cooperation.》。Golang 的 GC 实现也是基于这篇论文,后面再具体说明。

Span

span是用于分配对象的区块, 下图是简单说明了Span的内部结构:

图片 7

通常一个span包含了多个大小相同的元素, 一个元素会保存一个对象, 除非:

  • span用于保存大对象, 这种情况span只有一个元素
  • span用于保存极小对象且不包含指针的对象(tiny object), 这种情况span会用一个元素保存多个对象

span中有一个freeindex标记下一次分配对象时应该开始搜索的地址, 分配后freeindex会增加,
在freeindex之前的元素都是已分配的, 在freeindex之后的元素有可能已分配, 也有可能未分配.

span每次GC以后都可能会回收掉一些元素, allocBits用于标记哪些元素是已分配的, 哪些元素是未分配的.
使用freeindex allocBits可以在分配时跳过已分配的元素, 把对象设置在未分配的元素中,
但因为每次都去访问allocBits效率会比较慢, span中有一个整数型的allocCache用于缓存freeindex开始的bitmap, 缓存的bit值与原值相反.

gcmarkBits用于在gc时标记哪些对象存活, 每次gc以后gcmarkBits会变为allocBits.
需要注意的是span结构本身的内存是从系统分配的, 上面提到的spans区域和bitmap区域都只是一个索引.

节点复制

节点复制也是基于追踪的算法。其将整个堆等分为两个半区(semi-space),一个包含现有数据,另一个包含已被废弃的数据。节点复制式垃圾收集从切换(flip)两个半区的角色开始,然后收集器在老的半区,也就是 Fromspace 中遍历存活的数据结构,在第一次访问某个单元时把它复制到新半区,也就是 Tospace 中去。在 Fromspace 中所有存活单元都被访问过之后,收集器在 Tospace 中建立一个存活数据结构的副本,用户程序可以重新开始运行了。
优点

  • 所有存活的数据结构都缩并地排列在 Tospace 的底部,这样就不会存在内存碎片的问题。
  • 获取新内存可以简单地通过递增自由空间指针来实现。

缺点

  • 内存得不到充分利用,总有一半的内存空间处于浪费状态。

Span的类型

span根据大小可以分为67个类型, 如下:

// 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%
//    11        160        8192       51          32      9.73%
//    12        176        8192       46          96      9.59%
//    13        192        8192       42         128      9.25%
//    14        208        8192       39          80      8.12%
//    15        224        8192       36         128      8.15%
//    16        240        8192       34          32      6.62%
//    17        256        8192       32           0      5.86%
//    18        288        8192       28         128     12.16%
//    19        320        8192       25         192     11.80%
//    20        352        8192       23          96      9.88%
//    21        384        8192       21         128      9.51%
//    22        416        8192       19         288     10.71%
//    23        448        8192       18         128      8.37%
//    24        480        8192       17          32      6.82%
//    25        512        8192       16           0      6.05%
//    26        576        8192       14         128     12.33%
//    27        640        8192       12         512     15.48%
//    28        704        8192       11         448     13.93%
//    29        768        8192       10         512     13.94%
//    30        896        8192        9         128     15.52%
//    31       1024        8192        8           0     12.40%
//    32       1152        8192        7         128     12.41%
//    33       1280        8192        6         512     15.55%
//    34       1408       16384       11         896     14.00%
//    35       1536        8192        5         512     14.00%
//    36       1792       16384        9         256     15.57%
//    37       2048        8192        4           0     12.45%
//    38       2304       16384        7         256     12.46%
//    39       2688        8192        3         128     15.59%
//    40       3072       24576        8           0     12.47%
//    41       3200       16384        5         384      6.22%
//    42       3456       24576        7         384      8.83%
//    43       4096        8192        2           0     15.60%
//    44       4864       24576        5         256     16.65%
//    45       5376       16384        3         256     10.92%
//    46       6144       24576        4           0     12.48%
//    47       6528       32768        5         128      6.23%
//    48       6784       40960        6         256      4.36%
//    49       6912       49152        7         768      3.37%
//    50       8192        8192        1           0     15.61%
//    51       9472       57344        6         512     14.28%
//    52       9728       49152        5         512      3.64%
//    53      10240       40960        4           0      4.99%
//    54      10880       32768        3         128      6.24%
//    55      12288       24576        2           0     11.45%
//    56      13568       40960        3         256      9.99%
//    57      14336       57344        4           0      5.35%
//    58      16384       16384        1           0     12.49%
//    59      18432       73728        4           0     11.11%
//    60      19072       57344        3         128      3.57%
//    61      20480       40960        2           0      6.87%
//    62      21760       65536        3         256      6.25%
//    63      24576       24576        1           0     11.45%
//    64      27264       81920        3         128     10.00%
//    65      28672       57344        2           0      4.91%
//    66      32768       32768        1           0     12.50%

以类型(class)为1的span为例,
span中的元素大小是8 byte, span本身占1页也就是8K, 一共可以保存1024个对象.

在分配对象时, 会根据对象的大小决定使用什么类型的span,
例如16 byte的对象会使用span 2, 17 byte的对象会使用span 3, 32 byte的对象会使用span 3.
从这个例子也可以看到, 分配17和32 byte的对象都会使用span 3, 也就是说部分大小的对象在分配时会浪费一定的空间.

有人可能会注意到, 上面最大的span的元素大小是32K, 那么分配超过32K的对象会在哪里分配呢?
超过32K的对象称为"大对象", 分配大对象时, 会直接从heap分配一个特殊的span,
这个特殊的span的类型(class)是0, 只包含了一个大对象, span的大小由对象的大小决定.

特殊的span加上的66个标准的span, 一共组成了67个span类型.

分代收集

基于追踪的垃圾回收算法(标记-清扫节点复制)一个主要问题是在生命周期较长的对象上浪费时间(长生命周期的对象是不需要频繁扫描的)。同时,内存分配存在这么一个事实 “most object die young”。基于这两点,分代垃圾回收算法将对象按生命周期长短存放到堆上的两个(或者更多)区域,这些区域就是分代(generation)。对于新生代的区域的垃圾回收频率要明显高于老年代区域。
分配对象的时候从新生代里面分配,如果后面发现对象的生命周期较长,则将其移到老年代,这个过程叫做 promote。随着不断 promote,最后新生代的大小在整个堆的占用比例不会特别大。收集的时候集中主要精力在新生代就会相对来说效率更高,STW 时间也会更短。
优点:性能更优

缺点:实现复杂

Span的位置

在前一篇中我提到了P是一个虚拟的资源, 同一时间只能有一个线程访问同一个P, 所以P中的数据不需要锁.
为了分配对象时有更好的性能, 各个P中都有span的缓存(也叫mcache), 缓存的结构如下:

图片 8

各个P中按span类型的不同, 有67*2=134个span的缓存,

其中scan和noscan的区别在于,
如果对象包含了指针, 分配对象时会使用scan的span,
如果对象不包含指针, 分配对象时会使用noscan的span.
把span分为scan和noscan的意义在于,
GC扫描对象的时候对于noscan的span可以不去查看bitmap区域来标记子对象, 这样可以大幅提升标记的效率.

在分配对象时将会从以下的位置获取适合的span用于分配:

  • 首先从P的缓存(mcache)获取, 如果有缓存的span并且未满则使用, 这个步骤不需要锁
  • 然后从全局缓存(mcentral)获取, 如果获取成功则设置到P, 这个步骤需要锁
  • 最后从mheap获取, 获取后设置到全局缓存, 这个步骤需要锁

在P中缓存span的做法跟CoreCLR中线程缓存分配上下文(Allocation Context)的做法相似,
都可以让分配对象时大部分时候不需要线程锁, 改进分配的性能.

Golang GC

分配对象的处理

Overview

在说 Golang 的具体垃圾回收流程时,我们先来看一下几个基本的问题。

分配对象的流程

go从堆分配对象时会调用newobject函数, 这个函数的流程大致如下:

图片 9

首先会检查GC是否在工作中, 如果GC在工作中并且当前的G分配了一定大小的内存则需要协助GC做一定的工作,
这个机制叫GC Assist, 用于防止分配内存太快导致GC回收跟不上的情况发生.

之后会判断是小对象还是大对象, 如果是大对象则直接调用largeAlloc从堆中分配,
如果是小对象分3个阶段获取可用的span, 然后从span中分配对象:

  • 首先从P的缓存(mcache)获取
  • 然后从全局缓存(mcentral)获取, 全局缓存中有可用的span的列表
  • 最后从mheap获取, mheap中也有span的自由列表, 如果都获取失败则从arena区域分配

这三个阶段的详细结构如下图:

图片 10

何时触发 GC

在堆上分配大于 32K byte 对象的时候进行检测此时是否满足垃圾回收条件,如果满足则进行垃圾回收。

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {
    ...
    shouldhelpgc := false
    // 分配的对象小于 32K byte
    if size <= maxSmallSize {
        ...
    } else {
        shouldhelpgc = true
        ...
    }
    ...    
    // gcShouldStart() 函数进行触发条件检测
    if shouldhelpgc && gcShouldStart(false) {       
        // gcStart() 函数进行垃圾回收
        gcStart(gcBackgroundMode, false)
    }
}

上面是自动垃圾回收,还有一种是主动垃圾回收,通过调用 runtime.GC(),这是阻塞式的。

// GC runs a garbage collection and blocks the caller until the
// garbage collection is complete. It may also block the entire program
func GC() {
    ...
    gcStart(gcForceBlockMode, false)
    ...
}

数据类型的定义

分配对象涉及的数据类型包含:

p: 前一篇提到过, P是协程中的用于运行go代码的虚拟资源
m: 前一篇提到过, M目前代表系统线程
g: 前一篇提到过, G就是goroutine
mspan: 用于分配对象的区块
mcentral: 全局的mspan缓存, 一共有67*2=134个
mheap: 用于管理heap的对象, 全局只有一个

GC 触发条件

触发条件主要关注下面代码中的中间部分:

 forceTrigger ||memstats.heap_live >= memstats.gc_trigger

forceTrigger 是 forceGC 的标志;后面半句的意思是当前堆上的活跃对象大于我们初始化时候设置的 GC 触发阈值。在 malloc 以及 free 的时候 heap_live 会一直进行更新,这里就不再展开了。

// gcShouldStart returns true if the exit condition for the _GCoff
// phase has been met. The exit condition should be tested when
// allocating.
// If forceTrigger is true, it ignores the current heap size, but
// checks all other conditions. In general this should be false.
func gcShouldStart(forceTrigger bool) bool {
    return gcphase == _GCoff && (forceTrigger || memstats.heap_live >= memstats.gc_trigger) && memstats.enablegc && panicking == 0 && gcpercent >= 0
}
//初始化的时候设置 GC 的触发阈值
func gcinit() {
    _ = setGCPercent(readgogc())
    memstats.gc_trigger = heapminimum
    ...
}
// 启动的时候通过 GOGC 传递百分比 x
// 触发阈值等于 x * defaultHeapMinimum (defaultHeapMinimum 默认是 4M)
func readgogc() int32 {
    p := gogetenv("GOGC")
    if p == "off" {
        return -1
    }
    if n, ok := atoi32(p); ok {
        return n
    }
    return 100
}

本文由bg游戏资讯发布于单机游戏资讯,转载请注明出处:GC的实现原理,Go垃圾回收机制剖析

关键词: 日记本 单机游戏 Golang源码探索 go学习

上一篇:天天动听,高晓松任董事长
下一篇:没有了