Question

三色标记，需要高性能队列暂存灰色对象。为此，每个 P 都有本地队列，再以全局队列平衡。

• 白色：不可达对象，等待回收。
• 黑色：存活对象，其内容已被扫描。
• 灰色：存活对象，内容未被扫描。放入队列，等待处理。

// runtime2.go

type p struct {
    
    // gcw is this P's GC work buffer cache. The work buffer is
	// filled by write barriers, drained by mutator assists, and
	// disposed on certain GC state transitions.
	gcw gcWork
    
}

// mgc.go

var work struct {
	full  lfstack          // lock-free list of full blocks workbuf
}

从根对象开始，标记存活对象。内容尚未扫描的灰色对象，放入队列等待处理。

// mgc.go

// gcDrain scans roots and objects in work buffers, blackening grey
// objects until it is unable to get more work. It may return before
// GC is done; it's the caller's responsibility to balance work from
// other Ps.

func gcDrain(gcw *gcWork, flags gcDrainFlags) {

    // 小时工和临时工抢占（self-preempt）检查。
	if flags & (gcDrainIdle|gcDrainFractional) != 0 {
		if idle {
			check = pollWork  // P.runq | netpoll
		} else if flags & gcDrainFractional != 0 {
			check = pollFractionalWorkerExit  // time
		}
	}

	// 从根对象开始。
	if work.markrootNext < work.markrootJobs {
		for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
			job := atomic.Xadd(&work.markrootNext, +1) - 1
			if job >= work.markrootJobs {
				break
			}
            
            // 标记。
			markroot(gcw, job, flushBgCredit)
            
            // 退出检查。
			if check != nil && check() {
				goto done
			}
		}
	}

    // 处理灰色队列。
	for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
        
        // 全局队列空，转移一批过去。
		if work.full == 0 {
			gcw.balance()
		}

        // 从队列（本地和全局）提取一个对象。
		b := gcw.tryGetFast()
		if b == 0 {
			b = gcw.tryGet()
			if b == 0 {
				// Flush the write barrier
				// buffer; this may create
				// more work.
				wbBufFlush(nil, 0)
				b = gcw.tryGet()
			}
		}
		if b == 0 {
			// Unable to get work.
			break
		}
        
        // 扫描对象内容，找出下级灰色对象。
		scanobject(b, gcw)
	}

done:
    
}

markroot

根对象由 gcStart / gcMarkRootPrepare 提前准备，包括运行和等待中的 G 栈。

// mgcmark.go

func markroot(gcw *gcWork, i uint32, flushBgCredit bool) int64 {
	var workDone int64
	var workCounter *atomic.Int64
    
	switch {
	case work.baseData <= i && i < work.baseBSS: ...
	case work.baseBSS <= i && i < work.baseSpans: ...
	case i == fixedRootFinalizers: ...
	case i == fixedRootFreeGStacks: ...
	case work.baseSpans <= i && i < work.baseStacks: ...
	default:
        // ... allgs ...
        gp := work.stackRoots[i-work.baseStacks]
		workDone += scanstack(gp, gcw)
	}
    
	return workDone
}

// mgcmark.go

// scanstack scans gp's stack, greying all pointers found on the stack.
func scanstack(gp *g, gcw *gcWork) int64 {

	switch readgstatus(gp) &^ _Gscan {
	default:
		throw("mark - bad status")
	case _Gdead:
		return 0
	case _Grunning:
		throw("scanstack: goroutine not stopped")
	case _Grunnable, _Gsyscall, _Gwaiting:
		// ok
	}

    // Shrink the stack if not much of it is being used ...
	// Scan the saved context register ...
	// Scan the stack. Accumulate a list of stack objects ...
	// Find and trace other pointers in defer records ...

    // Find and scan all reachable stack objects.
	for {
		obj := state.findObject(p)
		gcdata := r.gcdata()

		b := state.stack.lo + uintptr(obj.off)
		if conservative {
			scanConservative(b, r.ptrdata(), gcdata, gcw, &state)
		} else {
			scanblock(b, r.ptrdata(), gcdata, gcw, &state)
		}
	}
    
	return int64(stackSize)
}

所有这些（markrootBlock、scanstack）最终将调用 scanblock 函数。

根对象有自己的位图。

// mgcmark.go

// scanblock scans b as scanobject would, but using an explicit
// pointer bitmap instead of the heap bitmap.

func scanblock(b0, n0 uintptr, ptrmask *uint8, gcw *gcWork, stk *stackScanState) {

    b := b0
	n := n0

	for i := uintptr(0); i < n; {
        
        // 读取标记位。
		bits := uint32(*addb(ptrmask, i/(goarch.PtrSize*8)))
		if bits == 0 {
			i += goarch.PtrSize * 8
			continue
		}
        
		for j := 0; j < 8 && i < n; j++ {
            
            // 如果标记为 1，表示指针。
			if bits&1 != 0 {
                
                // 利用指针获取目标，并将其放入队列。
				p := *(*uintptr)(unsafe.Pointer(b + i))
				if p != 0 {
					if obj, span, objIndex := findObject(p, b, i); obj != 0 {
						greyobject(obj, b, i, span, gcw, objIndex)
					}
				}
			}
            
            // 下一个标记位。
			bits >>= 1
			i += goarch.PtrSize
		}
	}
}

scanobject

为对象分配堆内存时，会依据类型信息，在位图标记指针。另垃圾回收期间，新对象直接为黑色。

// malloc.go

func mallocgc(size uintptr, typ *_type, needzero bool) unsafe.Pointer {

    noscan := typ == nil || typ.ptrdata == 0

    // 如包含指针，须在 heapArena.bitmap 添加记录。
	if !noscan {
		heapBitsSetType(uintptr(x), size, dataSize, typ)
	}

    // 垃圾回收期间，新分配对象直接标记为黑色（marked）。
	if gcphase != _GCoff {
		gcmarknewobject(span, uintptr(x), size, scanSize)
	}

	return x
}

扫描对象内容，将指针字段所引用对象标记为灰色，放入本地队列。

// mgcmark.go

const (
    
	// maxObletBytes is the maximum bytes of an object to scan at
	// once. Larger objects will be split up into "oblets" of at
	// most this size. Since we can scan 1–2 MB/ms, 128 KB bounds
	// scan preemption at ~100 µs.
    
	maxObletBytes = 128 << 10
)

// mgcmark.go

// scanobject scans the object starting at b, adding pointers to gcw.
// b must point to the beginning of a heap object or an oblet.
// scanobject consults the GC bitmap for the pointer mask and the
// spans for the size of the object.

func scanobject(b uintptr, gcw *gcWork) {

    // 从 heapArena 获取 bitmap 和 span。
	hbits := heapBitsForAddr(b)
	s := spanOfUnchecked(b)
	n := s.elemsize

    // 大于 128 KB 的大对象，分割扫描。
	if n > maxObletBytes {
        
		// Large object. Break into oblets for better
		// parallelism and lower latency.
        
        // 如果是从起始地址开始，那么表示尚未分隔。
		if b == s.base() {
            
            // 如果是 noscan，表示不包含指针，直接黑色即可。
			if s.spanclass.noscan() {
				// Bypass the whole scan.
				gcw.bytesMarked += uint64(n)
				return
			}

            // 以 128 KB 为单位，分割成多个 oblet，放入队列。
			for oblet := b + maxObletBytes; oblet < s.base()+s.elemsize; oblet += maxObletBytes {
				if !gcw.putFast(oblet) {
					gcw.put(oblet)
				}
			}
		}

        // 分割后，确定对象长度。
		n = s.base() + s.elemsize - b
		if n > maxObletBytes {
			n = maxObletBytes
		}
	}

    // 如果是包含指针的复合结构，那么必然按指针长度对齐。
    // 按指针长度遍历对象内容，配合标记位进行检查。
    
	var i uintptr
	for i = 0; i < n; i, hbits = i+goarch.PtrSize, hbits.next() {
        
		bits := hbits.bits()
		if bits&bitScan == 0 {
			break // no more pointers in this object
		}
		if bits&bitPointer == 0 {
			continue // not a pointer
		}

        // 读取指针内容，获取所指向目标对象地址。
		obj := *(*uintptr)(unsafe.Pointer(b + i))
		if obj != 0 && obj-b >= n {
            
            // 将目标灰色对象放入队列。
			if obj, span, objIndex := findObject(obj, b, i); obj != 0 {
				greyobject(obj, b, i, span, gcw, objIndex)
			}
		}
	}
    
	gcw.bytesMarked += uint64(n)
	gcw.heapScanWork += int64(i)
}

greyobject

灰色对象（存活）需要在 span.gcMarkBits 标记。

// mgcmark.go

// obj is the start of an object with mark mbits.
// If it isn't already marked, mark it and enqueue into gcw.

func greyobject(obj, base, off uintptr, span *mspan, gcw *gcWork, objIndex uintptr) {

    mbits := span.markBitsForIndex(objIndex)

	// 避免重复标记。
	if mbits.isMarked() {
		return
	}
	
    // 存活标记。
    mbits.setMarked()

    // 如所在 span 为 noscan，那么表示对象没有指针字段。
    // 存活标记（黑色）后，无需放入队列。
	if span.spanclass.noscan() {
		gcw.bytesMarked += uint64(span.elemsize)
		return
	}

    // 放入队列。
	if !gcw.putFast(obj) {
		gcw.put(obj)
	}
}