Golang内存管理—垃圾收集器

0. 简介

和C/C++等语言使用手动的方式管理堆内存不同，Go和Python、Java使用自动的内存管理系统，包括垃圾收集（Garbage Collection，缩写GC）机制。下面，我们将介绍垃圾收集器的设计原理以及Golang垃圾收集器的实现原理。

1. 常见的GC算法

1.1 引用计数法

为每个对象维护一个引用计数，当引用对象销毁时，引用计数-1，当对象的引用计数变为0后，就回收该对象。

• 代表语言：Python、PHP和Swift；
• 优点：对象回收快，简单直接；
• 缺点：不能很好地处理循环引用问题；实时维护引用计数是有损耗的。

1.2 标记-清除

从根变量开始遍历所有的引用对象，标记引用对象，没有被标记的对象进行回收。

• 代表语言：Golang；
• 优点：解决了引用计数方式的缺点，较为简单；
• 缺点：需要STW(Stop The World)，影响性能；另外也有可能造成内存碎片的问题。

1.3 分代收集

按照对象生命周期长短划分不同的代空间，生命周期长的放入老年代，短的放入新生代，不同代有不同的回收算法和回收频率。

• 代表语言：Java；
• 优点：回收性能好；
• 缺点：算法复杂。

2. Golang GC原理

2.1 算法选择

Golang的垃圾回收算法使用的是无分代、不整理、并发的三色标记清除算法：

• Go运行时的内存分配基于tcmalloc算法，基本上没有碎片问题，从而避免了标记-清除算法中容易产生内存碎片的问题；
• Go的垃圾回收器与用户代码并发执行，提升GC效率，降低对用户代码的影响。

2.2 三色标记

2.2.1 标记-清除算法

最简单的标记-清除算法中，分为标记和清除阶段。在扫描阶段，从垃圾回收的根对象出发，扫描整个引用链，找到所有可达对象进行标记。在清除阶段，扫描所有的不可达对象，然后将垃圾对象清除掉。

但是该算法有一个很大的缺点：整个过程必须STW(Stop The World)。这导致整个应用程序必须停止，严重影响程序实时性和效率。

2.2.2 三色标记算法

为了解决原始标记-清除带来的长时间的STW，多数现代的追踪式垃圾收集器一般都会实现三色标记算法以缩短STW的时间。三色标记法将程序中的对象分为白色、黑色和灰色三类：

• 白色对象：潜在的垃圾，其内存可能会被垃圾收集器回收；
• 黑色对象：活跃的对象，已经被扫描过的对象；
• 灰色对象：活跃的对象，刚好扫描到的对象，但是还需要对其子对象进行扫描，因为可能存在指向白色对象。

三色标记法的标记过程如下：

1. 起初所有的对象都是白色的；
2. 从根对象出发扫描所有可达对象，标记为灰色，放入灰色集合；
3. 从灰色集合中取出灰色对象，将其引用的对象标记为灰色并放入到灰色集合中，自身标记为黑色；
4. 重复步骤3，直到灰色集合为空，此时白色对象即为不可达的“垃圾”，回收白色对象。

根对象在垃圾回收的术语中又叫根集合，它是垃圾回收器在标记过程中最先检查的对象，包括：

• 全局变量：程序在编译时就能确定的那些在整个程序生命周期都将存活的变量；
• 执行栈：每个goroutine都有自己的执行栈，这些执行栈上依旧存活的栈对象以及指向分配的堆内存的指针对象，具体可参考Golang内存管理—垃圾收集器：栈对象处理；
• 寄存器：寄存器的值可能表示一个指针，参与计算的这些指针可能指向某个分配的内存地址。

因为用户可能会在标记的过程中修改对象的指针，比如出现以下情形，在如下所示的三色标记过程中，用户程序建立了从 A 对象到 D 对象的引用，但是因为程序中已经不存在灰色对象了，所以 D 对象会被垃圾收集器错误地回收。

要想解决以上问题，要么就和“标记—清除”算法一样，STW整个过程，但是这种方式会对用户程序影响比较大，降低程序性能。

如果要GC和用户程序并发执行，且保证内存安全，那么就需要使用屏障技术了。

2.2.3 屏障技术

内存屏障技术是一种屏障指令，它可以让 CPU 或者编译器在执行内存相关操作时遵循特定的约束，目前多数的现代处理器都会乱序执行指令以最大化性能，但是该技术能够保证内存操作的顺序性，在内存屏障前执行的操作一定会先于内存屏障后执行的操作。

想要在并发和增量的标记算法中保证正确性，我们需要满足以下两种三色不变性之一：

• 强三色不变性：黑色对象不会指向白色对象，只会指向灰色或者黑色对象；
• 弱三色不变性：黑色对象指向的白色对象必须包含一条从灰色对象经由多个白色对象的可达路径；

插入写屏障

Dijkstra 于1978年提出的插入写屏障，通过如下所示的算法，用户程序和垃圾收集器可以在并行工作的情况下保证内存安全：

// 灰色赋值器 Dijkstra 插入屏障
func DijkstraWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {
    shade(ptr) //先将新下游对象 ptr 标记为灰色
    *slot = ptr
}

//说明：
添加下游对象(当前下游对象slot, 新下游对象ptr) {   
  //step 1
  标记灰色(新下游对象ptr)   
  
  //step 2
  当前下游对象slot = 新下游对象ptr                    
}

//场景：
A.添加下游对象(nil, B)   //A 之前没有下游， 新添加一个下游对象B， B被标记为灰色
A.添加下游对象(C, B)     //A 将下游对象C 更换为B，  B被标记为灰色

上述伪代码很好理解，每当执行*slot = ptr表达式时，我们会执行上述写屏障（通过shade）尝试改变该指针的颜色，如果该指针原本是白色的，那么通过该函数将其设置为灰色，否则保持不变。

如上图所示的标记过程：

1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色；
2. 用户程序修改 A 对象的指针，将原本指向 B 对象的指针指向 C 对象，这时触发写屏障将 C 对象标记成灰色；
3. 垃圾收集器依次遍历程序中的其他灰色对象，将它们分别标记成黑色；

插入写屏障是一种相对保守的屏障技术，它有以下两个缺点：

• 在一次回收过程中可能会残留一部分对象没有回收成功，只有下一个回收过程中才会回收；
• 栈对象在垃圾回收中也被认为是根对象，为了保证内存安全：
  • 为栈上的对象增加屏障：大幅增加写入指针的额外开销；
  • 重新对栈上对象进行扫描：重新扫描栈对象需要STW；

删除写屏障

Yuasa 于1990年提出的删除写屏障的算法如下：

// 黑色赋值器 Yuasa 屏障  
func YuasaWritePointer(slot *unsafe.Pointer, ptr unsafe.Pointer) {  
    shade(*slot) 先将*slot标记为灰色  
    *slot = ptr  
}  
  
//说明：  
添加下游对象(当前下游对象slot， 新下游对象ptr) {  
    //step 1  
    if (当前下游对象slot是灰色 || 当前下游对象slot是白色) {  
        标记灰色(当前下游对象slot) //slot为被删除对象， 标记为灰色  
    }  
    //step 2  
    当前下游对象slot = 新下游对象ptr  
}  
  
//场景  
A.添加下游对象(B, nil) //A对象，删除B对象的引用。B被A删除，被标记为灰(如果B之前为白)  
A.添加下游对象(B, C) //A对象，更换下游B变成C。B被A删除，被标记为灰(如果B之前为白)

上述代码会在老对象的引用被删除时，将白色的老对象涂成灰色，这样删除写屏障就可以保证弱三色不变性，老对象引用的下游对象一定可以被灰色对象引用。

如上图所示的标记过程：

1. 垃圾收集器将根对象指向 A 对象标记成黑色并将 A 对象指向的对象 B 标记成灰色；
2. 用户程序将 A 对象原本指向 B 的指针指向 C，触发删除写屏障，但是因为 B 对象已经是灰色的，所以不做改变；
3. 用户程序将 B 对象原本指向 C 的指针删除，触发删除写屏障，白色的 C 对象被涂成灰色，避免发生悬挂指针以保证用户程序的正确性；
4. 垃圾收集器依次遍历程序中的其他灰色对象，将它们分别标记成黑色；

混合写屏障

分析以上两种屏障方式，如果采用纯粹的插入写屏障，满足强三色不变原理，但是栈上的对象不设置写屏障的话会导致黑色的栈可能指向白色的堆，所以必须STW重新扫描栈才能保证不丢对象，而在大量goroutine的环境下，STW的延迟不可控。

如果单纯的使用删除写屏障，其基于其实快照的解决方案（snapshot-at-the-begining）。顾名思义，就是在开始 gc 之前，必须 STW ，对整个根做一次起始快照。当赋值器（业务线程）从灰色或者白色对象中删除白色指针时候，写屏障会捕捉这一行为，将这一行为通知给回收器。

在Go v1.8版本引入了混合写屏障，结合了二者的优点，极大地减少了STW的时间，提升系统性能。

混合写屏障的具体操作如下：

1. GC开始时将栈上的可达对象全部扫描并且标记为黑色（之后不再进行第二次重复扫描，无需STW）；
2. GC期间，任何在栈上创建的新对象，均为黑色；
3. 堆上被删除的对象标记为灰色；
4. 堆上新添加的对象标记为灰色。

以下是个简单的流程，图片来自于详细总结： Golang GC、三色标记、混合写屏障机制，侵删！

其实总结起来就是，在GC期间：

• 栈上可达对象都标记为黑色，包括在此期间新创建的；
• 堆上的对象则会触发混合屏障机制，那么在机制生效后，即使有栈上黑色指向白色的堆对象，那也一定有一条从灰色堆对象到此白对象的可达路径，符合弱三色不变原理。

比如以下，就不会有栈对象能引用堆对象8，因为图中的8号显然是不可达的，所以不会出现不满足弱三色不变原理的情形。那为什么1号对象可以引用7号对象呢？这是因为1号对象在引用7号对象的时候，对象7是在对象6的下游，本身是可达。

总结下来就是，混合屏障结合了插入和删除写屏障的优点：

• 栈上数据（存活可达的）直接置黑保证了各个goroutine栈无需多次扫描，优化了空间；
• 插入写屏障保障了堆上的新增数据是灰色的；
• 删除写屏障保障了堆上被删除的数据是灰色的，避免黑色的栈上数据指向时，其未变色被删；

3. Golang GC过程

Golang垃圾收集的过程有以下四个阶段：

• GC开始（STW）；
• 并发扫描与辅助标记；
• 标记终止；
• 内存清理。

3.1 GC开始（STW）

垃圾回收在启动时都会调用runtime.gcStart函数：

func gcStart(trigger gcTrigger) {
   ...
   for trigger.test() && sweepone() != ^uintptr(0) {
      sweep.nbgsweep++
   }

   // Perform GC initialization and the sweep termination
   // transition.
   semacquire(&work.startSema)
   // Re-check transition condition under transition lock.
   if !trigger.test() {
      semrelease(&work.startSema)
      return
   }
   ...
}

首先检查是否符合GC条件，在循环中验证收集条件的同时还会不断调用runtime.sweepone清理已经被标记的内存单元，完成上一个垃圾收集循环的收尾工作。

在下一小步之前，会再次check一下是否满足GC条件。

接下来，调用gcBgMarkStartWorkers启动后台标记任务、在系统栈中调用stopTheWorldWithSema暂停程序并调用finishsweep_m保证上一次GC的工作结束。

func gcStart(trigger gcTrigger) {
	...
	semacquire(&worldsema)
	gcBgMarkStartWorkers()
	work.stwprocs, work.maxprocs = gomaxprocs, gomaxprocs
	...

	systemstack(stopTheWorldWithSema)
	systemstack(func() {
		finishsweep_m()
	})

	work.cycles++
	gcController.startCycle()
	...
}

在完成上面的准备工作后，修改垃圾回收状态到_GCmark后：

1. 调用runtime.gcBgMarkPrepare初始化后台扫描需要的状态；
2. 调用runtime.gcMarkRootPrepare扫描栈上、全局变量等根对象并将它们加入队列；
3. 设置全局变量runtime.gcBlackenEnabled，用户程序和标记任务可以将对象涂黑；
4. 调用runtime.startTheWorldWithSema启动程序，后台任务也会开始标记堆中的对象；

func gcStart(trigger gcTrigger) {
	...
	setGCPhase(_GCmark)

	gcBgMarkPrepare()
	gcMarkRootPrepare()

	atomic.Store(&gcBlackenEnabled, 1)
	systemstack(func() {
		now = startTheWorldWithSema(trace.enabled)
		work.pauseNS += now - work.pauseStart
		work.tMark = now
	})
	semrelease(&work.startSema)
}

总结下来，在GC开启阶段：

1. 需要STW暂停程序执行；
2. 启动后台标记任务，用于第二阶段；
3. 启动写屏障；
4. 将root根对象放入到标记队列（放入就是标记为灰色）；
5. 取消STW，进入第二阶段。

3.2 并发扫描与标记辅助

前面说过，调用gcBgMarkStartWorkers启动后台标记任务，该函数为每个处理器创建用于执行后台任务的goroutine，每个协程都会运行gcBgMarkWorker，所有的goroutine都在启动后陷入睡眠，等待findRunnabledGCWorker函数唤醒。

func gcBgMarkStartWorkers() {
   // Background marking is performed by per-P G's. Ensure that each P has
   // a background GC G.
   //
   // Worker Gs don't exit if gomaxprocs is reduced. If it is raised
   // again, we can reuse the old workers; no need to create new workers.
   for gcBgMarkWorkerCount < gomaxprocs {
      go gcBgMarkWorker()

      notetsleepg(&work.bgMarkReady, -1)
      noteclear(&work.bgMarkReady)
      // The worker is now guaranteed to be added to the pool before
      // its P's next findRunnableGCWorker.

      gcBgMarkWorkerCount++
   }
}

func gcBgMarkWorker() {
	gp := getg()

	gp.m.preemptoff = "GC worker init"
	node := new(gcBgMarkWorkerNode)
	gp.m.preemptoff = ""

	node.gp.set(gp)

	node.m.set(acquirem())
	notewakeup(&work.bgMarkReady)

	for {
		gopark(func(g *g, parkp unsafe.Pointer) bool {
			node := (*gcBgMarkWorkerNode)(nodep)
			if mp := node.m.ptr(); mp != nil {
				releasem(mp)
			}

			gcBgMarkWorkerPool.push(&node.node)
			return true
		}, unsafe.Pointer(node), waitReasonGCWorkerIdle, traceEvGoBlock, 0)
	...
}

唤醒后，我们根据处理器gcMarkWorkerMode 选择不同的标记执行策略，不同的执行策略都会调用gcDrain执行扫描，这个函数可以作为分析Goalng三色着色的入口。

func gcBgMarkWorker() {
   ...

      // Preemption must not occur here, or another G might see
      // p.gcMarkWorkerMode.

      // Disable preemption so we can use the gcw. If the
      // scheduler wants to preempt us, we'll stop draining,
      // dispose the gcw, and then preempt.
      node.m.set(acquirem())
      pp := gp.m.p.ptr() // P can't change with preemption disabled.

      if gcBlackenEnabled == 0 {
         println("worker mode", pp.gcMarkWorkerMode)
         throw("gcBgMarkWorker: blackening not enabled")
      }

      if pp.gcMarkWorkerMode == gcMarkWorkerNotWorker {
         throw("gcBgMarkWorker: mode not set")
      }

      startTime := nanotime()
      pp.gcMarkWorkerStartTime = startTime

      decnwait := atomic.Xadd(&work.nwait, -1)
      if decnwait == work.nproc {
         println("runtime: work.nwait=", decnwait, "work.nproc=", work.nproc)
         throw("work.nwait was > work.nproc")
      }

      systemstack(func() {
         // Mark our goroutine preemptible so its stack
         // can be scanned. This lets two mark workers
         // scan each other (otherwise, they would
         // deadlock). We must not modify anything on
         // the G stack. However, stack shrinking is
         // disabled for mark workers, so it is safe to
         // read from the G stack.
         casgstatus(gp, _Grunning, _Gwaiting)
         switch pp.gcMarkWorkerMode {
         default:
            throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
         case gcMarkWorkerDedicatedMode:
            gcDrain(&pp.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
            if gp.preempt {
               // We were preempted. This is
               // a useful signal to kick
               // everything out of the run
               // queue so it can run
               // somewhere else.
               if drainQ, n := runqdrain(pp); n > 0 {
                  lock(&sched.lock)
                  globrunqputbatch(&drainQ, int32(n))
                  unlock(&sched.lock)
               }
            }
            // Go back to draining, this time
            // without preemption.
            gcDrain(&pp.gcw, gcDrainFlushBgCredit)
         case gcMarkWorkerFractionalMode:
            gcDrain(&pp.gcw, gcDrainFractional|gcDrainUntilPreempt|gcDrainFlushBgCredit)
         case gcMarkWorkerIdleMode:
            gcDrain(&pp.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit)
         }
         casgstatus(gp, _Gwaiting, _Grunning)
      })

      ...
}

当所有的后台工作任务都陷入等待并且没有剩余工作时，我们就认为该轮垃圾收集的标记阶段结束了，然后调用gcMarkDone通知垃圾收集器。

func gcBgMarkWorker() {
   ...
       if incnwait == work.nproc && !gcMarkWorkAvailable(nil) {
         // We don't need the P-local buffers here, allow
         // preemption because we may schedule like a regular
         // goroutine in gcMarkDone (block on locks, etc).
         releasem(node.m.ptr())
         node.m.set(nil)

         gcMarkDone()
      }
   }
}

标记辅助

为了保证用户程序分配内存的速度不会超出后台任务的标记速度，运行时还引入了标记辅助技术，它遵循一条非常简单并且朴实的原则，分配多少内存就需要完成多少标记任务。

3.3 标记终止（STW）

func gcMarkDone() {
   ...
   systemstack(stopTheWorldWithSema)
   ...

   // Perform mark termination. This will restart the world.
   gcMarkTermination(nextTriggerRatio)
}

可以看到，进入标记终止阶段之前会STW，然后在gcMarkTermination中会取消STW，所以此阶段会取消STW，所以在此阶段是会STW的。值得注意的是，在引入了混合写屏障之后，即Go v1.8之后就不会在此阶段对栈进行re-scan了。

3.4 内存清理

func gcSweep(mode gcMode) {
    ...
    //阻塞式
    if !_ConcurrentSweep || mode == gcForceBlockMode {
        // Special case synchronous sweep.
        ...
        // Sweep all spans eagerly.
        for sweepone() != ^uintptr(0) {
            sweep.npausesweep++
        }
        // Do an additional mProf_GC, because all 'free' events are now real as well.
        mProf_GC()
        mProf_GC()
        return
    }
  	
    // 并行式
    // Background sweep.
    lock(&sweep.lock)
    if sweep.parked {
        sweep.parked = false
        ready(sweep.g, 0, true)
    }
    unlock(&sweep.lock)
}

对于并行式清扫，在 GC 初始化的时候就会启动 bgsweep()，然后在后台一直循环。不管是阻塞式还是并行式，都是通过 sweepone()函数来做清扫工作的。

func bgsweep(c chan int) {
    sweep.g = getg()

    lock(&sweep.lock)
    sweep.parked = true
    c <- 1
    goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1)

    for {
        for gosweepone() != ^uintptr(0) {
            sweep.nbgsweep++
            Gosched()
        }
        lock(&sweep.lock)
        if !gosweepdone() {
            // This can happen if a GC runs between
            // gosweepone returning ^0 above
            // and the lock being acquired.
            unlock(&sweep.lock)
            continue
        }
        sweep.parked = true
        goparkunlock(&sweep.lock, "GC sweep wait", traceEvGoBlock, 1)
    }
}

GC触发时机

后台触发

运行时会在应用程序启动时在后台开启一个用于强制触发垃圾收集的 Goroutine，该 Goroutine 的职责非常简单 — 调用runtime.gcStart尝试启动新一轮的垃圾收集：

func init() {
	go forcegchelper()
}

func forcegchelper() {
	forcegc.g = getg()
	for {
		lock(&forcegc.lock)
		atomic.Store(&forcegc.idle, 1)
		goparkunlock(&forcegc.lock, waitReasonForceGGIdle, traceEvGoBlock, 1)
		gcStart(gcTrigger{kind: gcTriggerTime, now: nanotime()})
	}
}

为了减少对计算资源的占用，该 Goroutine 会在循环中调用runtime.goparkunlock主动陷入休眠等待其他 Goroutine 的唤醒，runtime.forcegchelper在大多数时间都是陷入休眠的，但是它会被系统监控器runtime.sysmon在满足垃圾收集条件时唤醒：

func sysmon() {
	...
	for {
		...
		if t := (gcTrigger{kind: gcTriggerTime, now: now}); t.test() && atomic.Load(&forcegc.idle) != 0 {
			lock(&forcegc.lock)
			forcegc.idle = 0
			var list gList
			list.push(forcegc.g)
			injectglist(&list)
			unlock(&forcegc.lock)
		}
	}
}

手动触发

用户程序会通过runtime.GC函数在程序运行期间主动通知运行时执行，该方法在调用时会阻塞调用方直到当前垃圾收集循环完成

4. 参考文献

7.2 垃圾收集器

Golang垃圾回收(GC)介绍

Golang 垃圾回收剖析

详细总结： Golang GC、三色标记、混合写屏障机制