// 标记追踪：从根集合（寄存器、执行栈、全局变量）开始遍历对象图，标记遇到的每个对象；
func mark() {
    worklist.Init()                       // 初始化标记 work 列表
    for root := range roots {             // 从根开始扫描
        ref := *root
        if ref != nil && !isMarked(ref) { // 标记每个遇到的对象
            setMarked(ref)
            worklist.Add(ref)
            for !worklist.Empty() {
                ref := worklist.Remove()  // ref 已经标记过
                for fld := range Pointers(ref) {
                    child := *fld
                    if child != nil && !isMarked(child) {
                        setMarked(child)
                        worlist.Add(child)
                    }
                }
            }
        }
    }
}
// 清扫回收：检查堆中每一个对象，将所有未标记的对象当做垃圾进行回收。
func sweep() {
    // 检查堆区间内所有的对象
    for scan := worklist.Start(); scan < worklist.End(); scan = scan.Next {
        if isMarked(scan) {
            unsetMarked(scan)
        } else {
            free(scan) // 将未标记的对象释放
        }
    }
}

func isWhite(ref interface{}) bool {
    return !isMarked(ref)
}
func isGrey(ref interface{}) bool {
    return worklist.Find(ref)
}
func isBlack(ref interface{}) bool {
    return isMarked(ref) && !isGrey(ref)
}

// 并发标记
func markSome() bool {
    if worklist.empty() {       // 初始化回收过程
        scan(Roots)             // 赋值器不持有任何白色对象的引用
        if worklist.empty() {   // 此时灰色对象已经全部处理完毕
            sweep()             // 标记结束，立即清扫
            return false
        }
    }
    // 回收过程尚未完成，后续过程仍需标记
    ref = worklist.remove()
    scan(ref)
    return true
}

func scan(ref interface{}) {
    for fld := range Pointers(ref) {
        child := *fld
        if child != nil {
            shade(child)
        }
    }
}

func shade(ref interface{}) {
    if !isMarked(ref) {
        setMarked(ref)
        worklist.add(ref)
    }
}

// 并发清扫
func New() (interface{}, error) {
    collectEnough()
    ref := allocate()
    if ref == nil {
        return nil, errors.New("Out of memory")
    }
    return ref, nil
}
func collectEnough() {
    stopTheWorld()
    defer startTheWorld()
    for behind() { // behind() 控制回收工作每次的执行量
        if !markSome() {
            return
        }
    }
}

func RealityWB(slot *unsafe.Pointer, ptr unsafe.Pointer){
    shade(*slot)
    shade(ptr)
    *slot = ptr
}

type mspan struct {
    next *mspan             // next span in list, or nil if none
    prev *mspan             // previous span in list, or nil if none
    startAddr uintptr       // address of first byte of span aka s.base()
    npages    uintptr       // number of pages in span
    spanclass   spanClass     // size class and noscan (uint8)
    ...
    allocBits  *gcBits
	gcmarkBits *gcBits        // 实现 span 的颜色标记
}
func (s *mspan) sweep(preserve bool) bool {
    ...
}
// markBits.setMarked 就算是标记了
func (s *mspan) markBitsForIndex(objIndex uintptr) markBits {
    ...
}

// 每一个P 都有一个 gcWork
// go/1.15.2/libexec/src/runtime/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
	wbBuf wbBuf     // wbBuf is this P's GC write barrier buffer. write barrier 缓存
    ...
}
// go/1.15.2/libexec/src/runtime/mgcwork.go
// work poll/worklist 的实现
type gcWork struct {
	// wbuf1 is always the buffer we're currently pushing to and popping from and wbuf2 is the buffer that will be discarded next.
	wbuf1, wbuf2 *workbuf
	bytesMarked uint64
	scanWork int64
	flushedWork bool
	pauseGen uint32
	putGen uint32
	pauseStack [16]uintptr
}

// gcStart starts the GC.
// go/1.15.2/libexec/src/runtime/mgc.go
func gcStart(trigger gcTrigger) {
	
	mp := acquirem()
	mode := gcBackgroundMode
	...
	gcBgMarkStartWorkers()
	...
    // 设置全局变量中的GC状态为_GCmark
    // 然后启用写屏障
	setGCPhase(_GCmark)
	gcBgMarkPrepare() // Must happen before assist enable.
	gcMarkRootPrepare()
    ...
}
// gcBgMarkStartWorkers 会为全局每个 P 创建用于执行后台标记任务的 Goroutine，但是可以同时工作的只有 25%，调度器在调度循环 runtime.schedule中通过调用 gcController.findRunnableGCWorker方法进行控制。
func gcBgMarkStartWorkers() {
	// Background marking is performed by per-P G's. Ensure that each P has a background GC G.
	for _, p := range allp {
		if p.gcBgMarkWorker == 0 {
			go gcBgMarkWorker(p)
		}
	}
}
func gcBgMarkWorker(_p_ *p) {
	gp := getg()
	for {
        ...
		systemstack(func() {
			switch _p_.gcMarkWorkerMode {
			default:
				throw("gcBgMarkWorker: unexpected gcMarkWorkerMode")
			case gcMarkWorkerDedicatedMode:
				gcDrain(&_p_.gcw, gcDrainUntilPreempt|gcDrainFlushBgCredit)
				gcDrain(&_p_.gcw, gcDrainFlushBgCredit)
			case gcMarkWorkerFractionalMode:
				gcDrain(&_p_.gcw, gcDrainFractional|gcDrainUntilPreempt|gcDrainFlushBgCredit)
			case gcMarkWorkerIdleMode:
				gcDrain(&_p_.gcw, gcDrainIdle|gcDrainUntilPreempt|gcDrainFlushBgCredit)
			}
		})
        ...
	}
}
// 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.
// go/1.15.2/libexec/src/runtime/mgcmark.go
func gcDrain(gcw *gcWork, flags gcDrainFlags) {
	if !writeBarrier.needed {
		throw("gcDrain phase incorrect")
	}
	gp := getg().m.curg
	// Drain root marking jobs.
	if work.markrootNext < work.markrootJobs {
		...
		markroot(gcw, job)
        ...
	}
	// Drain heap marking jobs.Stop if we're preemptible or if someone wants to STW.
	for !(gp.preempt && (preemptible || atomic.Load(&sched.gcwaiting) != 0)) {
		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)
        ...
    }
}

// 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) {
	// Find the bits for b and the size of the object at b.
	hbits := heapBitsForAddr(b)
	s := spanOfUnchecked(b)
	n := s.elemsize
	if n > maxObletBytes {
		// Large object. Break into oblets for better parallelism and lower latency.
        ...
	}
	var i uintptr
	for i = 0; i < n; i += sys.PtrSize {
		...
        // 取出指针的值
		obj := *(*uintptr)(unsafe.Pointer(b + i))
		if obj != 0 && obj-b >= n {
            // 根据地址值去堆中查找对象
			if obj, span, objIndex := findObject(obj, b, i); obj != 0 {
                 // 调用 greyobject 标记对象并把对象放到标记队列中
				greyobject(obj, b, i, span, gcw, objIndex)
			}
		}
	}
	gcw.bytesMarked += uint64(n)
	gcw.scanWork += int64(i)
}

// 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) {
	// obj should be start of allocation, and so must be at least pointer-aligned.
	mbits := span.markBitsForIndex(objIndex)
    // If marked we have nothing to do.
    if mbits.isMarked() {
        return
    }
    mbits.setMarked()
    // Mark span.
    arena, pageIdx, pageMask := pageIndexOf(span.base())
    if arena.pageMarks[pageIdx]&pageMask == 0 {
        atomic.Or8(&arena.pageMarks[pageIdx], pageMask)
    }
    // If this is a noscan object, fast-track it to black instead of greying it.
    if span.spanclass.noscan() {
        gcw.bytesMarked += uint64(span.elemsize)
        return
    }
	// Queue the obj for scanning. 
	if !gcw.putFast(obj) {
		gcw.put(obj)
	}
}

// go/1.15.2/libexec/src/runtime/asm_amd64.s
// gcWriteBarrier performs a heap pointer write and informs the GC.
TEXT runtime·gcWriteBarrier(SB),NOSPLIT,$120
	...
    CALL	runtime·wbBufFlush(SB)
	...
    JMP	ret

// go/1.15.2/libexec/src/runtime/mwbbuf.go
// wbBufFlush flushes the current P's write barrier buffer to the GC workbufs.
func wbBufFlush(dst *uintptr, src uintptr) {
    ...
    systemstack(func() {
        ...
        wbBufFlush1(getg().m.p.ptr())
    })
}
func wbBufFlush1(_p_ *p) {
    // 获取缓存的指针
    start := uintptr(unsafe.Pointer(&_p_.wbBuf.buf[0]))
    n := (_p_.wbBuf.next - start) / unsafe.Sizeof(_p_.wbBuf.buf[0])
    ptrs := _p_.wbBuf.buf[:n]
    _p_.wbBuf.next = 0  
    gcw := &_p_.gcw
    pos := 0
    for _, ptr := range ptrs {
        // 查找到对象
        obj, span, objIndex := findObject(ptr, 0, 0)
        if obj == 0 { continue } 
        mbits := span.markBitsForIndex(objIndex)
        // 判断是否已被标记
        if mbits.isMarked() { continue }
        // 进行标记
        mbits.setMarked()
        // 标记 span.
        arena, pageIdx, pageMask := pageIndexOf(span.base())
        if arena.pageMarks[pageIdx]&pageMask == 0 {
            atomic.Or8(&arena.pageMarks[pageIdx], pageMask)
        }
        if span.spanclass.noscan() {
            gcw.bytesMarked += uint64(span.elemsize)
            continue
        }
        ptrs[pos] = obj
        pos++
    }
    // 将对象加入到 gcWork队列中
    gcw.putBatch(ptrs[:pos]) 
    // 重置 write barrier 缓存
    _p_.wbBuf.reset()
}

var sweep sweepdata
type sweepdata struct {
	lock    mutex
	g       *g
	parked  bool
	started bool

	nbgsweep    uint32  // 记录sweep 情况
	npausesweep uint32
}

func gcSweep(mode gcMode) {
    // 将 mheap_ 相关的标志位清零
    lock(&mheap_.lock)
    mheap_.sweepgen += 2
    mheap_.sweepdone = 0
    ...
    unlock(&mheap_.lock)
    ...
    // 唤醒后台清扫任务
    if sweep.parked {
        sweep.parked = false
        ready(sweep.g, 0, true)
    }
    ...
}
func gcenable() {
    // Kick off sweeping and scavenging.
    c := make(chan int, 2)
    // 设置异步清扫
    go bgsweep(c) 
    <-c 
}
func bgsweep(c chan int) {
    // 设置清扫 Goroutine 
    sweep.g = getg()
    // 循环清扫
    for {
        // 清扫一个span, 然后进入调度
        for sweepone() != ^uintptr(0) {
            sweep.nbgsweep++
            Gosched()
        }
        // 释放一些未使用的标记队列缓冲区到heap
        for freeSomeWbufs(true) {
            Gosched()
        }
        // 否则让后台清扫任务进入休眠
    }
}
func sweepone() uintptr {
    var s *mspan
    for {
        var s *mspan
        //查找一个 span 并释放
        s = mheap_.nextSpanForSweep()
        // 回收内存
        s.sweep(false) 
        ...
    }
}