Golang GC算法解读

柔光的暖阳◎ 2022-02-03 10:39 437阅读 0赞

概括

Go的垃圾回收官方形容为 非分代 非紧缩 写屏障 三色并发标记清理算法。
非分代：不像Java那样分为年轻代和年老代，自然也没有minor gc和maj o gc的区别。
非紧缩：在垃圾回收之后不会进行内存整理以清除内存碎片。
写屏障：在并发标记的过程中，如果应用程序（mutator）修改了对象图，就可能出现标记遗漏的可能，写屏障就是为了处理标记遗漏的问题。
三色：将GC中的对象按照搜索的情况分成三种：

  1. 黑色: 对象在这次GC中已标记,且这个对象包含的子对象也已标记
  2. 灰色: 对象在这次GC中已标记, 但这个对象包含的子对象未标记
  3. 白色: 对象在这次GC中未标记
    并发：可以和应用程序（mutator）在一定程度上并发执行。
    标记清理：GC算法分为两个大步骤：标记阶段找出要回收的对象，清理阶段则回收未被标记的对象（要被回收的对象）

触发时机

  • gcTriggerAlways: 强制触发GC，没找到什么情况下使用这个
  • gcTriggerHeap: 当前分配的内存达到一定值（动态计算）就触发GC
  • gcTriggerTime: 当一定时间（2分钟）没有执行过GC就触发GC

  • gcTriggerCycle: 要求启动新一轮的GC, 已启动则跳过, 手动触发GC的runtime.GC()会使用这个条件

    func gcStart(mode gcMode, trigger gcTrigger) {

    1. // Since this is called from malloc and malloc is called in
    2. // the guts of a number of libraries that might be holding
    3. // locks, don't attempt to start GC in non-preemptible or
    4. // potentially unstable situations.
    5. mp := acquirem()
    6. if gp := getg(); gp == mp.g0 || mp.locks > 1 || mp.preemptoff != "" {
    7.     releasem(mp)
    8.     return
    9. }
    10. releasem(mp)
    11. mp = nil
    13. // 检查GC条件是否满足，和下面的test()构成双检查锁，如果满足GC条件但目前处于GC清理阶段，那就参与清理
    14. for trigger.test() && gosweepone() != ^uintptr(0) {
    15.     sweep.nbgsweep++
    16. }
    18. // 加锁检查
    19. semacquire(&work.startSema)
    20. if !trigger.test() {
    21.     semrelease(&work.startSema)
    22.     return
    23. }
    24. /***************  .....  *****************/

    }

在trigger.test()函数中，检查是否满足GC触发的条件

  1. func (t gcTrigger) test() bool {
  2.     if !memstats.enablegc || panicking != 0 {
  3.         return false
  4.     }
  5.     if t.kind == gcTriggerAlways {
  6.         return true
  7.     }
  8.     if gcphase != _GCoff {
  9.         return false
  10.     }
  11.     switch t.kind {
  12.     case gcTriggerHeap:
  13.         // Non-atomic access to heap_live for performance. If
  14.         // we are going to trigger on this, this thread just
  15.         // atomically wrote heap_live anyway and we'll see our
  16.         // own write.
  17.         return memstats.heap_live >= memstats.gc_trigger
  18.     case gcTriggerTime:
  19.         if gcpercent < 0 {
  20.             return false
  21.         }
  22.         lastgc := int64(atomic.Load64(&memstats.last_gc_nanotime))
  23.         // forcegcperiod = 2分钟
  24.         return lastgc != 0 && t.now-lastgc > forcegcperiod
  25.     case gcTriggerCycle:
  26.         // t.n > work.cycles, but accounting for wraparound.
  27.         return int32(t.n-work.cycles) > 0
  28.     }
  29.     return true
  30. }
  31. const (
  32.     // gcTriggerAlways indicates that a cycle should be started
  33.     // unconditionally, even if GOGC is off or we're in a cycle
  34.     // right now. This cannot be consolidated with other cycles.
  35.     gcTriggerAlways gcTriggerKind = iota
  37.     // gcTriggerHeap indicates that a cycle should be started when
  38.     // the heap size reaches the trigger heap size computed by the
  39.     // controller.
  40.     gcTriggerHeap
  42.     // gcTriggerTime indicates that a cycle should be started when
  43.     // it's been more than forcegcperiod nanoseconds since the
  44.     // previous GC cycle.
  45.     gcTriggerTime
  47.     // gcTriggerCycle indicates that a cycle should be started if
  48.     // we have not yet started cycle number gcTrigger.n (relative
  49.     // to work.cycles).
  50.     gcTriggerCycle
  51. )

算法过程

  1. Sweep Termination: 对未清扫的span进行清扫, 只有上一轮的GC的清扫工作完成才可以开始新一轮的GC
  2. Mark: 扫描所有根对象, 和根对象可以到达的所有对象, 标记它们不被回收
  3. Mark Termination: 完成标记工作, 重新扫描部分根对象(要求STW)
  4. Sweep: 按标记结果清扫span
  1. ![1036501-0d3bcaade977a46f.jpg][]
  3. golang\_gc.jpg
  5. func gcStart(mode gcMode, trigger gcTrigger) {
  6.     // 拿到锁，保证只有一个执行流进入到这个临界区
  7.     semacquire(&worldsema)
  9.     // 启动后台扫描任务(G)
  10.     if mode == gcBackgroundMode {
  11.         gcBgMarkStartWorkers()
  12.     }
  14.     gcResetMarkState()
  16.     work.stwprocs, work.maxprocs = gomaxprocs, gomaxprocs
  17.     if work.stwprocs > ncpu {
  18.         work.stwprocs = ncpu
  19.     }
  20.     work.heap0 = atomic.Load64(&memstats.heap_live)
  21.     work.pauseNS = 0
  22.     work.mode = mode
  24.     now := nanotime()
  25.     work.tSweepTerm = now
  26.     work.pauseStart = now
  27.     if trace.enabled {
  28.         traceGCSTWStart(1)
  29.     }
  30.     systemstack(stopTheWorldWithSema)
  31.     // Finish sweep before we start concurrent scan.
  32.     systemstack(func() {
  33.         finishsweep_m()
  34.     })
  35.     // clearpools before we start the GC. If we wait they memory will not be
  36.     // reclaimed until the next GC cycle.
  37.     clearpools()
  39.     work.cycles++
  40.     if mode == gcBackgroundMode { // Do as much work concurrently as possible
  41.         gcController.startCycle()
  42.         work.heapGoal = memstats.next_gc
  44.         // Enter concurrent mark phase and enable
  45.         // write barriers.
  46.         setGCPhase(_GCmark)
  48.         gcBgMarkPrepare() // Must happen before assist enable.
  49.         gcMarkRootPrepare()
  51.         // Mark all active tinyalloc blocks. Since we're
  52.         // allocating from these, they need to be black like
  53.         // other allocations. The alternative is to blacken
  54.         // the tiny block on every allocation from it, which
  55.         // would slow down the tiny allocator.
  56.         gcMarkTinyAllocs()
  58.         // At this point all Ps have enabled the write
  59.         // barrier, thus maintaining the no white to
  60.         // black invariant. Enable mutator assists to
  61.         // put back-pressure on fast allocating
  62.         // mutators.
  63.         atomic.Store(&gcBlackenEnabled, 1)
  65.         // Assists and workers can start the moment we start
  66.         // the world.
  67.         gcController.markStartTime = now
  69.         // Concurrent mark.
  70.         systemstack(func() {
  71.             now = startTheWorldWithSema(trace.enabled)
  72.         })
  73.         work.pauseNS += now - work.pauseStart
  74.         work.tMark = now
  75.     }
  77.     semrelease(&work.startSema)
  78. }

关键函数及路径：

  1. gcBgMarkStartWorkers():准备后台标记工作goroutine（allp）， 启动后等待该任务通知信号量bgMarkReady再继续，notewakeup(&work.bgMarkReady)
  2. gcResetMarkState():重置一些全局状态和所有gorontine的栈（一种根对象）扫描状态
  3. systemstack(stopTheWorldWithSema):启动stop the world
  4. systemstack(func(){finishsweep_m()}): 不断去除要清理的span进行清理，然后重置gcmark位
  5. clearpools(): 清扫sched.sudogcache和sched.deferpool，不知道在干嘛……
  6. gcController.startCycle():启动新一轮GC，设置gc controller的状态位和计算一些估计值
  7. setGCPhase(_GCmark):设置GC阶段，启用写屏障
  8. gcBgMarkPrepare():设置后台标记任务计数；work.nproc = ^uint32(0)，work.nwait = ^uint32(0)
  9. gcMarkRootPrepare(): 计算扫描根对象的任务数量
  10. gcMarkTinyAllocs(): 标记所有tiny alloc等待合并的对象
  11. atomic.Store(&gcBlackenEnabled, 1): 启用辅助GC

  12. systemstack(func(){now=startTheWorldWithSema(trace.enable)}): 停止stop the world

    func gcBgMarkWorker(p *p) {

    1. /**********  .......  ***********/
    2. // 通知gcBgMarkStartWorkers可以继续处理
    3. notewakeup(&work.bgMarkReady)
    5. for {
    7.     // 切换到g0运行
    8.     systemstack(func() {
    9.         // Mark our goroutine preemptible so its stack
    10.         // can be scanned. This lets two mark workers
    11.         // scan each other (otherwise, they would
    12.         // deadlock). We must not modify anything on
    13.         // the G stack. However, stack shrinking is
    14.         // disabled for mark workers, so it is safe to
    15.         // read from the G stack.
    16.         casgstatus(gp, _Grunning, _Gwaiting)
    17.         switch _p_.gcMarkWorkerMode {
    18.         default:
    19.             throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
    20.         case gcMarkWorkerDedicatedMode:
    21.             gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
    22.             if gp.preempt {
    23.                 lock(&sched.lock)
    24.                 for {
    25.                     gp, _ := runqget(_p_)
    26.                     if gp == nil {
    27.                         break
    28.                     }
    29.                     globrunqput(gp)
    30.                 }
    31.                 unlock(&sched.lock)
    32.             }
    33.             // Go back to draining, this time
    34.             // without preemption.
    35.             gcDrain(&_p_.gcw, gcDrainNoBlock|gcDrainFlushBgCredit)
    36.         case gcMarkWorkerFractionalMode:
    37.             gcDrain(&_p_.gcw, gcDrainFractional|gcDrainUntilPreempt|gcDrainFlushBgCredit)
    38.         case gcMarkWorkerIdleMode:
    39.             gcDrain(&_p_.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit)
    40.         }
    41.         casgstatus(gp, _Gwaiting, _Grunning)
    42.     })
    44.     /********   ......  ***********/
    45.     // 判断是否所有后台标记任务都完成, 并且没有更多的任务
    46.     if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
    47.         gcMarkDone()
    48.     }
    49. }

    }

  13. gcDrain()是执行标记的函数

  14. 当所有标记任务完成时，执行gcMarkDone()函数

    func gcDrain(gcw *gcWork, flags gcDrainFlags) {

    1. initScanWork := gcw.scanWork
    2. // 如果根对象未扫描完，则先扫描根对象，Jobs为根对象总数，next相当于一个对象任务的取数器
    3. if work.markrootNext < work.markrootJobs {
    4.     for !(preemptible && gp.preempt) {
    5.         job := atomic.Xadd(&work.markrootNext, +1) - 1
    6.         if job >= work.markrootJobs {
    7.             break
    8.         }
    9.         // 将会扫描根对象，并把它加入到标记队列gcWork中之中，也就是把对象变成灰色
    10.         markroot(gcw, job)
    11.         if check != nil && check() {
    12.             goto done
    13.         }
    14.     }
    15. }
    17. // 当根对象全部put到标记队列中, 消费标记队列，根据对象图进行消费
    18. for !(preemptible && gp.preempt) {
    19.     if work.full == 0 {
    20.         gcw.balance()
    21.     }
    23.     var b uintptr
    24.     if blocking {
    25.         b = gcw.get()
    26.     } else {
    27.         b = gcw.tryGetFast()
    28.         if b == 0 {
    29.             b = gcw.tryGet()
    30.         }
    31.     }
    32.     if b == 0 {
    33.         // work barrier reached or tryGet failed.
    34.         break
    35.     }
    36.     scanobject(b, gcw)
    38.     // 如果已经扫描了一定数量的对象(gcCreditSlack的值是2000)
    39.     if gcw.scanWork >= gcCreditSlack {
    40.         // 把扫描的对象数量添加到全局
    41.         atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
    42.         // 减少辅助GC的工作量和唤醒等待中的G
    43.         if flushBgCredit {
    44.             gcFlushBgCredit(gcw.scanWork - initScanWork)
    45.             initScanWork = 0
    46.         }
    47.         idleCheck -= gcw.scanWork
    48.         gcw.scanWork = 0
    50.         // 如果是idle模式且达到了检查的扫描量, 则检查是否有其他任务(G), 如果有则跳出循环
    51.         if idle && idleCheck <= 0 {
    52.             idleCheck += idleCheckThreshold
    53.             if pollWork() {
    54.                 break
    55.             }
    56.         }
    57.     }
    58. }

    done:

    1. // 把扫描的对象数量添加到全局
    2. if gcw.scanWork > 0 {
    3.     atomic.Xaddint64(&gcController.scanWork, gcw.scanWork)
    4.     // 减少辅助GC的工作量和唤醒等待中的G
    5.     if flushBgCredit {
    6.         gcFlushBgCredit(gcw.scanWork - initScanWork)
    7.     }
    8.     gcw.scanWork = 0
    9. }

    }

    func gcMarkDone() {

    1. semacquire(&work.markDoneSema)
    3. // Re-check transition condition under transition lock.
    4. if !(gcphase == _GCmark && work.nwait == work.nproc && !gcMarkWorkAvailable(nil)) {
    5.     semrelease(&work.markDoneSema)
    6.     return
    7. }
    9. // 暂时禁止启动新的后台标记任务
    10. atomic.Xaddint64(&gcController.dedicatedMarkWorkersNeeded, -0xffffffff)
    11. prevFractionalGoal := gcController.fractionalUtilizationGoal
    12. gcController.fractionalUtilizationGoal = 0
    13. // 转换到Mark Termination阶段，进入STW阶段
    14. systemstack(stopTheWorldWithSema)
    15. // 标记对根对象的扫描已完成
    16. work.markrootDone = true
    17. // 禁止辅助GC和后台任务
    18. atomic.Store(&gcBlackenEnabled, 0)
    19. // 唤醒所有因为辅助GC而休眠的G
    20. gcWakeAllAssists()
    22. semrelease(&work.markDoneSema)
    23. // 计算下一次触发gc需要的heap大小
    24. nextTriggerRatio := gcController.endCycle()
    26. // 计算下一次触发gc需要的heap大小
    27. gcMarkTermination(nextTriggerRatio)

    }

    func gcMarkTermination(nextTriggerRatio float64) {

    1. // 禁止辅助GC和后台标记任务的运行
    2. // 重新允许本地标记队列(下次GC使用)
    3. // 设置当前GC阶段到完成标记阶段, 并启用写屏障
    4. atomic.Store(&gcBlackenEnabled, 0)
    5. gcBlackenPromptly = false
    6. setGCPhase(_GCmarktermination)
    8. systemstack(func() {gcMark(startTime)})
    10. systemstack(func() {
    11.     // 设置当前GC阶段到关闭, 并禁用写屏障
    12.     setGCPhase(_GCoff)
    13.     // 唤醒后台清扫任务, 将在STW结束后开始运行
    14.     gcSweep(work.mode)
    15. })
    17. // 更新下一次触发gc需要的heap大小(gc_trigger)
    18. gcSetTriggerRatio(nextTriggerRatio)
    20. // 重置清扫状态
    21. sweep.nbgsweep = 0
    22. sweep.npausesweep = 0
    24. // 统计执行GC的次数然后唤醒等待清扫的G
    25. lock(&work.sweepWaiters.lock)
    26. memstats.numgc++
    27. injectglist(work.sweepWaiters.head.ptr())
    28. work.sweepWaiters.head = 0
    29. unlock(&work.sweepWaiters.lock)
    31. // 重新启动世界
    32. systemstack(func() { startTheWorldWithSema(true) })
    33. // 移动标记队列使用的缓冲区到自由列表, 使得它们可以被回收
    34. prepareFreeWorkbufs()
    35. // 释放未使用的栈
    36. systemstack(freeStackSpans)
    38. semrelease(&worldsema)
    39. // 重新允许当前的G被抢占
    40. releasem(mp)
    41. mp = nil

当标记的扫描工作完成之后，会进入到GC Mark Termination阶段，也就是gcMarkDone()函数，关键路径：

  1. systemstack(stopTheWorldWithSema)：启动STW
  2. gcWakeAllAssists()：唤醒所有因辅助gc而休眠的G
  3. nextTriggerRatio:=gcController.endCycle()：计算下一次触发gc需要的heap大小
  4. setGCPhase(_GCmarktermination)：启用写屏障
  5. systemstack(func() {gcMark(startTime)})： 再次执行标记
  6. systemstack(func(){setGCPhase(_GCoff)；gcSweep(work.mode)})：关闭写屏障，唤醒后台清扫任务，将在STW结束后开始运行
  7. gcSetTriggerRatio(nextTriggerRatio)：更新下次触发gc时的heap大小
  8. systemstack(func() { startTheWorldWithSema(true) }): 停止STW

STW分析：web程序中，我们关注最大停顿时间

STW出现在两个位置，分别是在初始标记阶段Mark和并发标记完成后重标记Mark Termination:

初始标记阶段：

  • systemstack(stopTheWorldWithSema):启动stop the world
  • systemstack(func(){finishsweep_m()}): 不断去除要清理的span进行清理，然后重置gcmark位
  • clearpools(): 清扫sched.sudogcache和sched.deferpool，不知道在干嘛……
  • gcController.startCycle():启动新一轮GC，设置gc controller的状态位和计算一些估计值
  • gcMarkRootPrepare(): 计算扫描根对象的任务数量
  • gcMarkTinyAllocs(): 涂灰所有tiny alloc等待合并的对象
  • systemstack(func(){now=startTheWorldWithSema(trace.enable)}): 停止stop the world

找出其中比较耗时的阶段：

  • finishsweep_m():如果上一次GC清扫阶段没有完成，那么在新的一轮GC阶段中就会在阻塞在这里，使得原本可以和应用程序并行的清扫阶段被放进STW。所以，如果频繁的执行GC，就可能会使得GC的最大停顿时间变长。
  • clearpools():时间复杂度大概为：O(5*L),L为_defer中链表的长度。
  • gcController.startCycle():O(P)，P为go的P的数量，和cpu数有关，时间复杂度可以忽略
  • gcMarkRootPrepare(): O(全局变量区)，包括bss段和data段
  • gcMarkTinyAllocs(): O(P)

个人觉得，对STW影响最大的是finishsweep_m()阶段，所有我们应该尽量避免让go在清扫期执行新一轮的GC。

重新标记阶段

  • systemstack(stopTheWorldWithSema)：启动STW
  • gcWakeAllAssists()：唤醒所有因辅助gc而休眠的G
  • nextTriggerRatio:=gcController.endCycle()：计算下一次触发gc需要的heap大小
  • setGCPhase(_GCmarktermination)：启用写屏障
  • systemstack(func() {gcMark(startTime)})： 再次执行标记
  • systemstack(func(){setGCPhase(_GCoff)；gcSweep(work.mode)})：关闭写屏障，唤醒后台清扫任务，将在STW结束后开始运行
  • gcSetTriggerRatio(nextTriggerRatio)：更新下次触发gc时的heap大小
  • systemstack(func() { startTheWorldWithSema(true) }): 停止STW

找出其中比较耗时的阶段：

  • gcWakeAllAssists()：O(G)，将所有可运行的G插入到调度链表
  • systemstack(func() {gcMark(startTime)})：

发表评论

表情：
评论列表 （有 0 条评论，437人围观）

还没有评论，来说两句吧...

相关阅读

    相关 快速解读GC日志

    本文是 Plumbr 发行的 Java垃圾收集指南 的部分内容。文中将介绍GC日志的输出格式, 以及如何解读GC日志, 从中提取有用的信息。我们通过 `-XX:+UseSeri

    Dear 丶Dear 丶/ 0 赞/ 338 阅读

    相关 【JVM】GC日志解读实例

    每一种收集器的日志形式都是由它们自身的实现所决定的，换而言之，每个收集器的日志格式都可以不一样。但虚拟机设计者为了方便用户阅读，将各个收集器的日志都维持一定的共性。例如以下GC

    水深无声水深无声/ 0 赞/ 394 阅读

    相关 GC算法

    GC算法： 标记-清除(Mark-Sweep)算法,算法分为“标记”和“清除”两个阶段: 首先标记出所有需要回收的对象，在标记完成后统一回收所有被标记的对象，它的标记过

    旧城等待，旧城等待，/ 0 赞/ 430 阅读