垃圾回收下篇
2021.07

6.3 垃圾回收

目前Go中垃圾回收的核心函数是scanblock,源代码在文件runtime/mgc0.c中。这个函数非常难读,单个函数写了足足500多行。上面有两个大的循环,外层循环作用是扫描整个内存块区域,将类型信息提取出来,得到其中的gc域。内层的大循环是实现一个状态机,解析执行类型信息中gc域的指令码。

先说说上一节留的疑问吧。MType中的数据其实是类型信息,但它是用uintptr表示,而不是Type结构体的指针,这是一个优化的小技巧。由于内存分配是机器字节对齐的,所以地址就只用到了高位,低位是用不到的。于是低位可以利用起来存储一些额外的信息。这里的uintptr中高位存放的是Type结构体的指针,低位用来存放类型。通过

    t = (Type*)(type & ~(uintptr)(PtrSize-1));

就可以从uintptr得到Type结构体指针,而通过

type & (PtrSize-1)

就可以得到类型。这里的类型有TypeInfo_SingleObject,TypeInfo_Array,TypeInfo_Map,TypeInfo_Chan几种。

基本的标记过程

从最简单的开始看,基本的标记过程,有一个不带任何优化的标记的实现,对应于函数debug_scanblock。

debug_scanblock函数是递归实现的,单线程的,更简单更慢的scanblock版本。该函数接收的参数分别是一个指针表示要扫描的地址,以及字节数。

首先要将传入的地址,按机器字节大小对齐。
然后对待扫描区域的每个地址:
找到它所属的MSpan,将地址转换为MSpan里的对象地址。
根据对象的地址,找到对应的标记位图里的标记位。
判断标记位,如果是未分配则跳过。否则加上特殊位标记(debug_scanblock中用特殊位代码的mark位)完成标记。
判断标记位中标记了无指针标记位,如果没有,则要递归地调用debug_scanblock。

这个递归版本的标记算法还是很容易理解的。其中涉及的细节在上节中已经说过了,比如任意给定一个地址,找到它的标记位信息。很明显这里仅仅使用了一个无指针位,并没有精确的垃圾回收。

并行的垃圾回收

Go在这个版本中不仅实现了精确的垃圾回收,而且实现了并行的垃圾回收。标记算法本质上就是一个树的遍历过程,上面实现的是一个递归版本。

并行的垃圾回收需要做的第一步,就是先将算法做成非递归的。非递归版本的树的遍历需要用到一个队列。树的非递归遍历的伪代码大致是:

根结点进队
while(队列不空) {
    出队
    访问
    将子结点进队
}

第二步是使上面的代码能够并行地工作,显然这时是需要一个线程安全的队列的。假设有这样一个队列,那么上面代码就能够工作了。但是,如果不加任何优化,这里的队列的并行访问非常地频繁,对这个队列加锁代价会非常高,即使是使用CAS操作也会大大降低效率。

所以,第三步要做的就是优化上面队列的数据结构。事实上,Go中并没有使用这样一个队列,为了优化,它通过三个数据结构共同来完成这个队列的功能,这三个数据结构分别是PtrTarget数组,Workbuf,lfstack。

先说Workbuf吧。听名字就知道,这个结构体的意思是工作缓冲区,里面存放的是一个数组,数组中的每个元素都是一个待处理的结点,也就是一个Obj指针。这个对象本身是已经标记了的,这个对象直接或间接引用到的对象,都是应该被标记的,它们不会被当作垃圾回收掉。Workbuf是比较大的,一般是N个内存页的大小(目前是2页,也就是8K)。

PtrTarget数组也是一个缓冲区,相当于一个intermediate buffer,跟Workbuf有一点点的区别。第一,它比Workbuf小很多,大概只有32或64个元素的数组。第二,Workbuf中的对象全部是已经标记过的,而PtrTarget中的元素可能是标记的,也可能是没标记的。第三,PtrTarget里面的元素是指针而不是对象,指针是指向任意地址的,而对象是对齐到正确地址的。从一个指针变为一个对象要经过一次变换,上一节中有讲过具体细节。

垃圾回收过程中,会有一个从PtrTarget数组冲刷到Workbuf缓冲区的过程。对应于源代码中的flushptrbuf函数,这个函数作用就是对PtrTaget数组中的所有元素,如果该地址是mark了的,则将它移到Workbuf中。标记过程形成了一个环,在环的一边,对Workbuf中的对象,会将它们可能引用的区域全部放到PtrTarget中记录下来。在环的另一边,又会将PtrTarget中确定需要标记的地址刷到Workbuf中。这个过程一轮一轮地进行,推动非递归版本的树的遍历过程,也就是前面伪代码中的出队,访问,子结点进队的过程。

另一个数据结构是lfstack,这个名字的意思是lock free栈。其实它是被用作了一个无锁的链表,链表结点是以Workbuf为单位的。并行垃圾回收中,多条线程会从这个链表中取数据,每次以一个Workbuf为工作单位。同时,标记的过程中也会产生Workbuf结点放到链中。lfstack保证了对这个链的并发访问的安全性。由于现在链表结点是以Workbuf为单位的,所以保证整体的性能,lfstack的底层代码是用CAS操作实现的。

经过第三步中数据结构上的拆解,整个并行垃圾回收的架构已经呼之欲出了,这就是标记扫描的核心函数scanblock。这个函数是在多线程下并行安全的。

那么,最后一步,多线程并行。整个的gc是以runtime.gc函数为入口的,它实际调用的是gc。进入gc函数后会先stoptheworld,接着添加标记的root区域。然后会设置markroot和sweepspan的并行任务。运行mark的任务,扫描块,运行sweep的任务,最后starttheworld并切换出去。

有一个ParFor的数据结构。在gc函数中调用了

    runtime·parforsetup(work.markfor, work.nproc, work.nroot, nil, false, markroot);
    runtime·parforsetup(work.sweepfor, work.nproc, runtime·mheap->nspan, nil, true, sweepspan);

是设置好回调函数让线程去执行markroot和sweepspan函数。垃圾回收时会stoptheworld,其它goroutine会对发起stoptheworld做出响应,调用runtime.gchelper,这个函数会调用scanblock帮助标记过程。也会并行地做markroot和sweepspan的过程。

    void
    runtime·gchelper(void)
    {
        gchelperstart();

        // parallel mark for over gc roots
        runtime·parfordo(work.markfor);

        // help other threads scan secondary blocks
        scanblock(nil, nil, 0, true);

        if(DebugMark) {
            // wait while the main thread executes mark(debug_scanblock)
            while(runtime·atomicload(&work.debugmarkdone) == 0)
                runtime·usleep(10);
        }

        runtime·parfordo(work.sweepfor);
        bufferList[m->helpgc].busy = 0;
        if(runtime·xadd(&work.ndone, +1) == work.nproc-1)
            runtime·notewakeup(&work.alldone);
    }

其中并行时也有实现工作流窃取的概念,多个worker同时去工作缓存中取数据出来处理,如果自己的任务做完了,就会从其它的任务中“偷”一些过来执行。

垃圾回收的时机

垃圾回收的触发是由一个gcpercent的变量控制的,当新分配的内存占已在使用中的内存的比例超过gcprecent时就会触发。比如,gcpercent=100,当前使用了4M的内存,那么当内存分配到达8M时就会再次gc。如果回收完毕后,内存的使用量为5M,那么下次回收的时机则是内存分配达到10M的时候。也就是说,并不是内存分配越多,垃圾回收频率越高,这个算法使得垃圾回收的频率比较稳定,适合应用的场景。

gcpercent的值是通过环境变量GOGC获取的,如果不设置这个环境变量,默认值是100。如果将它设置成off,则是关闭垃圾回收。