GC 对根对象扫描实现的源码分析

By admin

- 5 minutes read - 1060 words

工作池gcWork

工作缓存池（work pool）实现了生产者和消费者模型，用于指向灰色对象。一个灰色对象在工作队列中被扫描标记，一个黑色对象表示已被标记不在队列中。

写屏障、根发现、栈扫描和对象扫描都会生成一个指向灰色对象的指针。扫描消费时会指向这个灰色对象，从而将先其变为黑色，再扫描它们，此时可能会产生一个新的指针指向灰色对象。这个就是三色标记法的基本知识点，应该很好理解。

gcWork 是为垃圾回收器提供的一个生产和消费工作接口。

它可以用在stack上，如

(preemption must be disabled)
gcw := &getg().m.p.ptr().gcw
.. call gcw.put() to produce and gcw.tryGet() to consume ..

在标记阶段使用gcWork可以防止垃圾收集器转换到标记终止，这一点很重要，因为gcWork可能在本地持有GC工作缓冲区。可以通过禁用抢占（systemstack 或 acquirem）来实现。

数据结构

type gcWork struct {
	wbuf1, wbuf2 *workbuf

	bytesMarked uint64
	scanWork int64
	flushedWork bool
}
  • wbuf1,wbuf2：这里 wbuf1 是主工作缓存区; wbuf2为次工作缓存区，两者要么都是nil,要么都不是。 这可以看作是两个工作缓冲区指针串联的堆栈。当我们弹出最后一个指针的时候，我们可以引入新的缓存区，并将指针向上移动一个空缓存区，从而丢失掉的缓存区；当我们填充两个缓存区的时，可以通过引入一个新的空缓冲区并丢弃一个满的缓冲区，同时将堆栈向下移动一个工作缓冲区。
  • bytesMarked 标记为黑色对象的累计大小
  • scanWork 扫描统计
  • flushedWork 表示自上次 gcMarkDone 终止检查以来，已将非空工作缓存区刷新到全局工作队列。表示是否gcWork可能传递给了另一个gcWork

wbuf1 和 wbuf2 为 workbuf 数据类型，其数据结构

type workbuf struct {
	workbufhdr
	// account for the above fields
	obj [(_WorkbufSize - unsafe.Sizeof(workbufhdr{})) / sys.PtrSize]uintptr
}

type workbufhdr struct {
	node lfnode // must be first
	nobj int
}

// Lock-free stack node.
// Also known to export_test.go.
type lfnode struct {
	next    uint64
	pushcnt uintptr
}

工作原理

GC 期间 gcBgMarkWorker() 函数会根据GC的模式(gcMarkWorkerMode、gcMarkWorkerDedicatedMode、gcMarkWorkerFractionalMode 和 gcMarkWorkerIdleMode) 调用 gcDrain() 函数采用不同的策略来实现扫描来实现将灰色对象变为黑色。

func gcBgMarkWorker() {
	gp := getg()

	for {
		......
		systemstack(func() {
			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.
					lock(&sched.lock)
					for {
						gp, _ := runqget(pp)
						if gp == nil {
							break
						}
						globrunqput(gp)
					}
					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)
		})

		......
}

gcDrain() 函数遍历所有根对象，然后调用 [markroot()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L141-L242) 函数分别扫描每一个根对象。

在GC的标记阶段首先需要标记的就是”根对象“, 从根对象开始可到达的所有对象都会被认为是存活的. 根对象包含了全局变量, 各个G的栈上的变量等, GC会先扫描根对象然后再扫描根对象可到达的所有对象。扫描根对象包含了一系列的工作，定义在函数 [gcMarkRootPrepare()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L52-L109)。

func gcDrain(gcw *gcWork, flags gcDrainFlags) {
	gp := getg().m.curg
	preemptible := flags&gcDrainUntilPreempt != 0
	flushBgCredit := flags&gcDrainFlushBgCredit != 0
	idle := flags&gcDrainIdle != 0

	initScanWork := gcw.scanWork

	// checkWork is the scan work before performing the next
	// self-preempt check.
	checkWork := int64(1<<63 - 1)
	var check func() bool
	if flags&(gcDrainIdle|gcDrainFractional) != 0 {
		checkWork = initScanWork + drainCheckThreshold
		if idle {
			check = pollWork
		} else if flags&gcDrainFractional != 0 {
			check = pollFractionalWorkerExit
		}
	}

	// 若存在未扫描完的根对象，则开始继续扫描
	if work.markrootNext < work.markrootJobs {
		// 循环遍历，直到遇到被抢占或STW
		for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
			// 下一个被扫描的根对象
			job := atomic.Xadd(&work.markrootNext, +1) - 1
			if job >= work.markrootJobs {
				break
			}

			// 扫描第 job 个根对象，期间必须禁用抢占
			markroot(gcw, job)
			if check != nil && check() {
				goto done
			}
		}
	}

	......
}

markrootNext 表示下一个扫描的对象 markrootJobs 表示要扫描的根对象数量

markrootNext uint32 // next markroot job
markrootJobs uint32 // number of markroot jobs

调用 [runtime.markroot](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L141-L242) 函数扫描第 job 个根对象的 缓存、数据段、存放全局变量 和 静态变量的 BSS 段以及 Goroutine 的栈内存；一旦完成了对根对象的扫描，当前 Goroutine 会开始从本地和全局的工作缓存池中获取待执行的任务：

// markroot scans the i'th root.
//
// Preemption must be disabled (because this uses a gcWork).
//
// nowritebarrier is only advisory here.
//
//go:nowritebarrier
//
// 参数 i 表示第几个根对象
func markroot(gcw *gcWork, i uint32) {
	// fixRootCount 是一个常量，值为2
	baseFlushCache := uint32(fixedRootCount)

	// work.nFlushCacheRoots 表示各种根对象的总数量, 由gcMarkRootPrepare() 更新此值为0,
	baseData := baseFlushCache + uint32(work.nFlushCacheRoots)
	baseBSS := baseData + uint32(work.nDataRoots)
	baseSpans := baseBSS + uint32(work.nBSSRoots)
	baseStacks := baseSpans + uint32(work.nSpanRoots)
	end := baseStacks + uint32(work.nStackRoots)

	switch {

	// 释放p下在的mcache中的所有span
	case baseFlushCache <= i && i < baseData:
		flushmcache(int(i - baseFlushCache))

	// data段 已初始化的全局变量
	case baseData <= i && i < baseBSS:
		for _, datap := range activeModules() {
			markrootBlock(datap.data, datap.edata-datap.data, datap.gcdatamask.bytedata, gcw, int(i-baseData))
		}

	// bss 未初始化的全局变量（只读变量）
	case baseBSS <= i && i < baseSpans:
		for _, datap := range activeModules() {
			markrootBlock(datap.bss, datap.ebss-datap.bss, datap.gcbssmask.bytedata, gcw, int(i-baseBSS))
		}

	// 扫描 finalizers 析构器列表， allfin 是一个全局变量，是一个 block list
	case i == fixedRootFinalizers:
		for fb := allfin; fb != nil; fb = fb.alllink {
			cnt := uintptr(atomic.Load(&fb.cnt))
			scanblock(uintptr(unsafe.Pointer(&fb.fin[0])), cnt*unsafe.Sizeof(fb.fin[0]), &finptrmask[0], gcw, nil)
		}

	// 已中止的G的栈(_Gdead), 但不会释放已缓存中的G, 这里指的是 sched.gFree.stack 中的g, 非 sched.gFree.noStack 列表
	case i == fixedRootFreeGStacks:
		// Switch to the system stack so we can call
		// stackfree.
		systemstack(markrootFreeGStacks)

	case baseSpans <= i && i < baseStacks:
		// mark mspan.specials
		markrootSpans(gcw, int(i-baseSpans))

	default:
		// 扫描剩下的所有goroutine 栈
		var gp *g
		if baseStacks <= i && i < end {
			gp = allgs[i-baseStacks]
		} else {
			throw("markroot: bad index")
		}

		// remember when we've first observed the G blocked
		status := readgstatus(gp) // We are not in a scan state
		if (status == _Gwaiting || status == _Gsyscall) && gp.waitsince == 0 {
			gp.waitsince = work.tstart
		}

		// 在系统栈执行，这样还可以实现对自己stack的扫描
		systemstack(func() {
			userG := getg().m.curg
			selfScan := gp == userG && readgstatus(userG) == _Grunning

			// 如果扫描的是自己的栈，则进行G状态的切换
			if selfScan {
				casgstatus(userG, _Grunning, _Gwaiting)
				userG.waitreason = waitReasonGarbageCollectionScan
			}

			// 暂停休眠G
			stopped := suspendG(gp)
			if stopped.dead {
				gp.gcscandone = true
				return
			}
			if gp.gcscandone {
				throw("g already scanned")
			}
			// 扫描栈
			scanstack(gp, gcw)
			gp.gcscandone = true
			resumeG(stopped)

			// 如果扫描的是自己的栈，则恢复G的状态
			if selfScan {
				casgstatus(userG, _Gwaiting, _Grunning)
			}
		})
	}
}

先计算出一些各种标记对象的数量：

fixedRootCount 是量个常量，值为2；work.nFlushCacheRoots 表示各种根对象的总数量，此值由 [gcMarkRootPrepare](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L52-L109)() 函数更新为 ``，此函数同时会计算出所有标记任务的总数量，见work.markrootJobs = uint32(fixedRootCount + work.nFlushCacheRoots + work.nDataRoots + work.nBSSRoots + work.nSpanRoots + work.nStackRoots)；剩下的几类对象将根据数值依次增加。也就是说这些不同类的对象有从左到右的顺序。

  • 调用 [flushmcache](https://github.com/golang/go/blob/go1.16.2/src/runtime/mstats.go#L705-L720)() 函数释放指定 P下面的 mcache，期间必须为 STW 状态
  • 调用 [markrootBlock()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L244-L270) 函数实现对 data段 和 bss段 全局变量的扫描（参考： https://www.cnblogs.com/yanghong-hnu/p/4705755.html）
  • 调用 [scanblock()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L1159-L1197) 函数 实现对 finalizers 析构器列表的扫描
  • 在系统栈调用 [markrootFreeGStacks()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L272-L301) 函数释放 _Gdead 状态的G的栈
  • 调用 [markrootSpans()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L303-L381) 函数扫描 [mheap.markArenas](https://github.com/golang/go/blob/go1.16.2/src/runtime/mheap.go#L187-L191) 中共享的根对象
  • 在系统栈扫描所的剩下的G，期间会 [暂停休眠G](https://github.com/golang/go/blob/go1.16.2/src/runtime/preempt.go#L61-L254)(在安全点抢占G) 和 [唤醒恢复G](https://github.com/golang/go/blob/go1.16.2/src/runtime/preempt.go#L256-L280)(从安全点继续执行)

标记阶段(Mark)会做其中的”Fixed Roots”, “Data Roots”, “BSS Roots”, “Span Roots”, “Stack Roots”. 完成标记阶段(Mark Termination)会做其中的”Fixed Roots”, “Flush Cache Roots”.

释放mcache

主要通过 [flushmcache()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mstats.go#L710) 实现。

func flushmcache(i int) {
	assertWorldStopped()

	p := allp[i]
	c := p.mcache
	if c == nil {
		return
	}
	c.releaseAll()
	stackcache_clear(c)
}

每次释放是一个p（allp[i])，真正的释放操作是 [mcache.releaseAll()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mcache.go#L251-L290) 函数

全局变量baseData 和只读变量 baseBSS

调用 [markrootBlock()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L244-L270) 函数实现。

finalizers 析构器列表

func markroot(gcw *gcWork, i uint32) {
	switch {
	......
	case i == fixedRootFinalizers:
		for fb := allfin; fb != nil; fb = fb.alllink {
			cnt := uintptr(atomic.Load(&fb.cnt))
			scanblock(uintptr(unsafe.Pointer(&fb.fin[0])), cnt*unsafe.Sizeof(fb.fin[0]), &finptrmask[0], gcw, nil)
		}
	......
	}
	......
}

这里 allfin 是一个全局变量，是一个 链接类型，表示所有blocks的列表。

主要实现函数为 [scanblock()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L1159-L1197)。

空闲的G栈

这里指的是 全局调度器 上的G栈，并不处理 P 上抽的 G 栈。

在系统栈调用函数 markrootFreeGStacks()，释放所有包含 `stack 的 G，然后再将这些G放在 noStack 的空闲列表中。

// markrootFreeGStacks frees stacks of dead Gs.
//
// This does not free stacks of dead Gs cached on Ps, but having a few
// cached stacks around isn't a problem.
func markrootFreeGStacks() {
	// Take list of dead Gs with stacks.
	// 调度器中包含栈的全局空闲g列表（
	lock(&sched.gFree.lock)
	list := sched.gFree.stack
	sched.gFree.stack = gList{}
	unlock(&sched.gFree.lock)
	if list.empty() {
		return
	}

	// Free stacks.
	// 从head遍历gList,调用 statckfree() 函数释放g的stacks信息,直到处理完所有g
	q := gQueue{list.head, list.head}
	for gp := list.head.ptr(); gp != nil; gp = gp.schedlink.ptr() {
		stackfree(gp.stack)
		gp.stack.lo = 0
		gp.stack.hi = 0
		// Manipulate the queue directly since the Gs are
		// already all linked the right way.
		q.tail.set(gp)
	}

	// Put Gs back on the free list.
	// 将原来包含statck的g放到 noStack 的 g 空闲队列中
	lock(&sched.gFree.lock)
	sched.gFree.noStack.pushAll(q)
	unlock(&sched.gFree.lock)
}
  1. 遍历全局调度器中的空闲的g，只处理包含 stack 的 sched.gFree.stack
  2. 遍历包含 stack 的 gList，调用 [stackfree()](https://github.com/golang/go/blob/9b955d2d3fcff6a5bc8bce7bafdc4c634a28e95b/src/runtime/stack.go#L421-L496) 函数释放stack信息（内存)，参考 goroutine栈的申请与释放
  3. 最后再将这些释放掉stack信息的g放在不包含stack的 sched.gFree.noStack 列表中

mheap.markArenas 中共享的根对象

调用函数 markrootSpans() 实现，很重要的一个方法。理解起来比较吃力…

G 栈

在系统栈进行对g的扫描，以便可以扫描自己当前运行的g。

  1. 调用 [suspendG()](https://github.com/golang/go/blob/go1.16.2/src/runtime/preempt.go#L76-L254) 暂停g的运行；
  2. 调用 [scanstack()](https://github.com/golang/go/blob/go1.16.2/src/runtime/mgcmark.go#L684-L860) 进行stack的扫描，结束后将其标记为 gp.gcscandone = true；其实就是一个将stack上的指针变为灰色的操作
  3. 调用 [resumeG()](https://github.com/golang/go/blob/go1.16.2/src/runtime/preempt.go#L256-L280) 恢复G的运行

如果扫描的是当前G自己，则需要对其状态在 _Grunning 和 _Gwaiting 之间进行一次转换。

源码分析见： https://blog.haohtml.com/archives/30519

参考资料