# 35｜内存管理第2关：实现垃圾回收 你好，我是宫文学。 今天这节课，我们继续上一节课未完成的内容，完成垃圾回收功能。 在上一节课，我们已经实现了一个基于Arena做内存分配的模块。并且，我们还在可执行程序里保存了函数、类和闭包相关的元数据信息。 有了上一节课的基础之后，我们这节课就能正式编写垃圾回收的算法了。算法思路是这样的： * 首先，我们要有一个种机制来触发垃圾回收，进入垃圾回收的处理程序； * 第二，我们要基于元数据信息来遍历栈帧，找到所有的GC根； * 第三，从每个GC根出发，我们需要去标记GC根直接和间接引用的内存对象； * 最后，我们再基于对象的标记信息，来回收内存垃圾。 在今天这节课，你不仅仅会掌握标记-清除算法，其中涉及的知识点，也会让你能够更容易地实现其他垃圾回收算法，并且让我们的程序能更好地与运行时功能相配合。 那接下来，我们就顺着算法实现思路，看看如何启动垃圾回收机制。 ## 启动垃圾回收机制 在现代的计算机语言中，我们可以有各种策略来启动垃圾回收机制。比如，在申请内存时，如果内存不足，就可以触发垃圾回收。甚至，你也可以每隔一段时间就触发一下垃圾收集。不过不论采取哪种机制，我们首先要有办法从程序的正常执行流程，进入垃圾回收程序才行。 进入垃圾回收程序，其实有一个经常使用的时机，就是在**函数返回**的时候。这个时候，我们可以不像平常那样，使用retq跳回调用者，而是先去检查是否需要做垃圾回收：如果需要做垃圾回收，那就先回收完垃圾，再返回到原来函数的调用者；如果不需要做垃圾回收，那就直接跳转到函数的调用者。 ![](https://static001.geekbang.org/resource/image/84/a8/8469d534e77f0e46a792aac104232ba8.jpg?wh=1891x841) 实现这个功能很简单，只需要在return语句之前调用frame\_walker这个内置函数，并把当前%rbp寄存器的值作为参数传进去就好了： ```plain visitReturnStatement(rtnStmt:ReturnStatement):any{ if (rtnStmt.exp!=null){ let ret = this.visit(rtnStmt.exp) as Oprand; //调用一个内置函数，来做垃圾回收 this.callBuiltIns("frame_walker",[Register.rbp]);//把当前%rbp的值传进去 //把返回值赋给相应的寄存器 let dataType = getCpuDataType(rtnStmt.exp.theType as Type); this.movIfNotSame(dataType, ret, Register.returnReg(dataType)); ... } } ``` 这样，我们就能获得调用GC程序的时机。 在这段代码中，frame\_walker内置函数的功能是遍历整个调用栈。这就是我们启动垃圾回收机制后，要进行的下一个任务。接下来我们就来分析一下具体怎么做。 ## 遍历栈帧和对象 遍历栈帧其实很简单，因为我们能够知道每个栈帧的起始地址。从哪里知道呢？就是rbp寄存器。rbp寄存器里保存的是每个栈帧的底部地址。 每次新建立一个栈帧的时候，我们总是把前一个栈帧的rbp值保护起来，这就是你在每个函数开头看到的第一行指令：pushq %rbp。因此，我们从栈帧里的第一个8字节区域，就可以读出前一个栈帧的%rbp值，这就意味着我们得到了前一个栈帧的栈底。然后你可以到这个位置，再继续获取更前一个栈帧的地址。具体你可以看下面这张图： ![](https://static001.geekbang.org/resource/image/1c/80/1c5f725c3db3f4d8b34dbee123db5a80.jpg?wh=1080x1073) 那这个思路真的有用吗？我们直接动手试一下！ 首先，我写了一个简单的测试程序。在这个程序里，main函数调用了foo，foo又调用了bar。这样，在foo和bar返回前，我们都可以启动垃圾回收，但从main函数返回的时候就没有必要启动了，因为这个时候进程结束，进程从操作系统申请的所有内存，都会还给操作系统。 ```plain function foo(a:number):string{ let s:string = "PlayScript!" let b:number = bar(a+5); return s; } function bar(b:number):number{ let a:number[] = [1,2,b]; let s:string = "Hello"; println(s); println(a[2]); b = b*10; return b; } println(foo(2)); ``` 接下来，我又写了一个frame\_walker.c的程序。这个程序很简单，就是依次打印出每个栈帧所保存的rbp寄存器的地址。在程序里，rbpValue0是调用frame\_walker.c程序的函数的rbp值，这个值是当前栈帧的底部。在这个地址里，保存的是前一个栈帧原来的rbp值，也就是前一个栈帧的rbp的地址，依次类推。 ```plain //遍历栈帧 void frame_walker(unsigned long rbpValue0){ //当前栈帧的rbp值 printf("\nrbpValue0:\t0x%lx(%ld)\n", rbpValue0, rbpValue0); //往前一个栈帧的rbp值 unsigned long rbpValue1 = *(unsigned long*)rbpValue0; printf("rbpValue1:\t0x%lx(%ld)\n", rbpValue1, rbpValue1); //再往前一个栈帧 unsigned long rbpValue2 = *(unsigned long*)rbpValue1; printf("rbpValue2:\t0x%lx(%ld)\n", rbpValue2, rbpValue2); //再往前一个栈帧 unsigned long rbpValue3 = *(unsigned long*)rbpValue2; printf("rbpValue3:\t0x%lx(%ld)\n", rbpValue3, rbpValue3); //再往前一个栈帧 unsigned long rbpValue4 = *(unsigned long*)rbpValue3; printf("rbpValue4:\t0x%lx(%ld)\n", rbpValue4, rbpValue4); } ``` 最后，你可以用make example\_gc命令，编译成可执行文件。运行这个可执行文件，会打印出下面的输出内容： ![图片](https://static001.geekbang.org/resource/image/21/94/213a5cccafb1f04ddf88be0a9b3bf194.png?wh=1200x640) 你可能注意到了，frame\_walker一共打印了5个栈帧的rbp值。但是我们的程序最多的时候也只用到了3个栈帧呀，那之前更多的那些栈帧是什么呢？这个问题我留给你，看看你能不能用操作系统的知识来回答这个问题。 但目前，我们还只是能找到每个栈帧，接下来我们还要进一步解析栈帧里的内容，从而找到GC根，并经由GC跟查找到内存对象。**这就需要我们查找函数的元数据了**。 这时候你会发现，为了查找函数的元数据，我们必须知道每个栈帧是由哪个函数生成的。这个问题我们在闭包的那一节课也曾经讨论过，正好在这里实现。 具体实现起来倒也不复杂。我们可以约定，在栈帧的一开头、紧挨着保存%rbp寄存器的信息的下面，保存该函数的元数据区的指针。这样，每个函数的汇编代码的序曲部分就会像下面那样。其中，后两行代码就是用来保存meta区的地址的： ```plain pushq %rbp movq %rsp, %rbp movq _foo.meta@GOTPCREL(%rip), %rax movq %rax, -8(%rbp) ``` 在这里，“\_foo.meta@GOTPCREL(%rip)”是使用相对于%rip寄存器的偏移量，也就是通过下一行代码地址的偏移量来确定\_foo.meta标签的地址的。 我们曾经也用过相对于%rip寄存器寻址的方式，比如获取double型字面量。你会发现这里有一点不同，当时我们并没有“@GOTPCREL”这一小段文字。这里会涉及到链接器和代码定位的一些技术细节。在这里，你可以理解为，因为我们把这些元数据声明在数据段，而不是像double字面量一样声明在文本段，所以就要用到一个不同的定位方式就行了。 好了，现在我们可以从每个函数的栈帧出发，来找到函数的元数据了。所以，我又写了一个新版本的frame\_walker函数，来访问函数元数据，打印出每个栈帧里的变量的情况。我们给这个函数传递的参数，是当前栈帧rbp的值。 ```plain void frame_walker(unsigned long rbpValue){ printf("\nwalking the stack:\n"); while(1){ //rbp寄存器的值，也就是栈底的地址 printf("rbp value:\t\t\t0x%lx(%ld)\n", rbpValue, rbpValue); //函数元数据区的地址 unsigned long metaAddress = *(unsigned long*)(rbpValue -8); printf("address of function meta:\t0x%lx(%ld)\n", metaAddress, metaAddress); //函数名称的地址，位于元数据区的第一个位置 unsigned long pFunName = *(unsigned long*)metaAddress; printf("address of function name:\t0x%lx(%ld)\n", pFunName,pFunName); //到函数名称区，去获取函数名称 const char* funName = (const char*)pFunName; printf("function name:\t\t\t%s\n", funName); //变量数量，位于元数据区的第二个位置 unsigned long numVars = *(unsigned long*)(metaAddress+8); printf("number of vars:\t\t\t%ld\n", numVars); //遍历所有的变量 for (int i = 0; i< numVars; i++){ //获取变量属性的压缩格式，3个属性压缩到了8个字节中 unsigned long varAttr = *(unsigned long*)(metaAddress+8*(i+2)); printf("var attribute(compact):\t\t0x%lx(%ld)\n", varAttr,varAttr); //拆解出变量的属性 unsigned long varIndex = varAttr>>32; //变量下标，4个字节 unsigned long typeTag = (varAttr>>24) & 0x00000000000000ff; //变量类型编号，1个字节 unsigned long offset = varAttr & 0x0000000000ffffff; //变量在栈帧中的地址偏移量 printf("var attribute(decoded):\t\tvarIndex:%ld, typeTag:%ld, offset:%ld\n", varIndex, typeTag, offset); } //去遍历上一个栈帧 rbpValue = *(unsigned long*)rbpValue; printf("\n"); //如果遇到main函数，则退出 if (strcmp(funName, "main")==0) break; } } ``` 再次编译并运行，就会打印出每个函数栈帧里的信息。这些信息是在bar函数快要返回的时候，遍历各个栈帧打印出来的。从这些信息里，你能够清晰地看到每个函数的栈帧里保存了哪些变量，还有每个变量在栈帧中的位置和每个变量的类型。 ![图片](https://static001.geekbang.org/resource/image/7e/0e/7ec414116c96549f4640f3ba9d24d20e.png?wh=1424x1080) **接着我们来找GC根和它直接引用的对象。**你可以看到，bar函数的栈帧里一共有2个变量，分别是参数b和变量a。其中参数b是整型的，所以不是GC根。而变量a是一个数组，它是GC根，所以我们要标记该数组对象为活跃的。而foo函数的栈帧里也有两个变量，分别是参数a和变量s。 不过，看到这个结果，你肯定会产生一些疑问。首先，为什么bar函数里字符串变量s没有出现在栈帧里，而foo函数里同样的字符串变量s却出现在了栈桢里呢？ 这是因为，在bar函数要返回的时刻，字符串s已经被bar函数使用完毕了，变成内存垃圾了。而foo函数现在是执行到第二个语句，并且调用了bar函数。在从bar函数返回以后，它还要在第三条语句中用到字符串变量s，所以s仍然是alive的，需要被保存下来。 bar函数里的参数b也是一样的，因为它是被return语句引用的，所以在返回之前，仍然是alive。 那可能你又要问了，不对呀，按照这么说，bar函数中的数组变量a和foo函数中的参数a，应该都没有用了呀，不用去遍历了呀。特别是bar函数中的数组，应该作为内存垃圾回收了才对。 没错，这是我们当前算法的缺陷。我们没有去保存变量活跃性分析的结果，也就是说在每一行代码处，到底哪些变量是活跃的，我们是不知道的。这样，我们也就没有办法精确地判断哪些变量其实已经失效了。并且，其实我们也没有办法精确地判断，每个函数现在执行到了哪一行代码，哪些代码是活跃的。 所以，我们这里用了一个近似的算法：只要是曾经被spill到栈帧里的变量，我们都认为它们是值得被保护的，还是活跃的。这个算法其实这在实际的应用中已经足够了。 **那既然找到了对象引用，接下来我们就可以标记这个对象了**。在每个对象的头部，我们都预留了8个字节的空间，用来设置各种标志位。这8个字节，在一开始申请内存的时候，都被设置成了0。我们现在要做的也比较简单，只需要把第一位作为“是否是内存垃圾”的标记位就好了。如果该标志位为1，那就说明这对象是有用的，不能回收。如果是0，那么就说明它是内存垃圾。 好了，现在我们已经完成了最复杂的任务，也就是遍历栈帧，找到并标记对象引用。**接下来，我们还要基于这些对象，进一步找出它们所引用的其他内存对象**。 在这一部分，针对自定义对象、数组和闭包，我们都需要编写相对应的遍历方法，但原理跟前面我们遍历函数寻找GC根是一致的，都是去查找元数据，这里我就不一一展开了，你可以去看mem.c中的源代码。 现在标记完所有的对象以后，接下来的事情就简单了。接下来，我们可以遍历Arena中的每个内存块，然后再在内存块里遍历每一个对象，把没有标记的对象删掉。对于标记过的对象，我们就要把它的标记去掉，为下一次垃圾收集做好准备。 好了到这里，我们相关算法的实现思路已经梳理清楚了。现在是时候验证我们的成果了，我们内存管理的相关算法到底是否能成功呢？ ## 测试垃圾回收算法 我们直接运行程序，来检验一下。你可以运行命令make example\_gc，生成可执行程序，并运行它，会得到如下输出结果： ![](https://static001.geekbang.org/resource/image/9d/9b/9dec8cbaab7c1ccc9df8beb4ef94409b.png?wh=1000x1080) 你可以看到，程序bar函数和foo函数结束的时候，分别释放了一些内存垃圾。并且，每次申请内存和垃圾回收，GC都打印出了当前Arena中的信息，你会看到Arena中内存分配的详细信息。在做完垃圾回收以后，相关内存空间确实被释放掉了。 也就是说，我们的垃圾回收算法算是圆满成功了！ ## 课程小结 今天这一节课，我们接着上一节完成了垃圾回收算法。我希望你能记住几个要点： 第一，我们有很多种方式可以启动垃圾回收机制。在这里，我们用了最简单的一种方式，也就是在退出函数前触发垃圾回收机制。类似的，你还可以在循环语句的地方检查是否需要做垃圾回收，因为程序中的循环可能会耗费很长的时间，积累很多内存垃圾。这里，我们的程序和运行时就形成了一种协作机制。 其实这种协作机制，也是实现另一个重要的运行时功能，并发管理的基础，特别是协程机制，需要当前程序与协程的调度器主动配合，才能完成细颗粒度的并发调度。你从这节课中，应该会直观地感受到这些运行时的调度机制是怎么运作的。 第二，我们是通过查询栈帧的布局信息去寻找GC根的。我们可以认为，没有出现在栈帧布局中的变量，肯定是已经失效了的。而出现在栈帧布局中的变量，有些其实也已经失效了，但我们当前没有必要去做更加精细化地管控。 第三，这节课示范了如何具体访问各种元数据信息。这些技能很重要，能让你可以在可执行文件里自由地存放各种自己需要的静态数据，让程序的运行机制拥有更多的可能性。 最后，我们通过两节课实现了内存分配和垃圾回收的工作。虽然实现得比较简单，但却是一个良好的开始。你在此基础上，可以更快地实现其他的算法。比如，你可以把内存整理一下，减少内存碎片，这样就是实现了标记-整理算法。你还可以把所有分配了的内存对象拷贝到一个新的区域，这就实现了停止-拷贝算法，也就是Java等语言普遍采用的算法。 不过，当你在内存中移动对象的时候，又会遇到新的技术挑战。比如，你需要知道栈帧中的哪些变量是引用了这个对象，再来更新这些值。再比如，当你的程序正在读写一个数组的时候，整个数组却被GC挪到了另一个位置，那与数组处理有关的功能就可能会出错。当然，这些技术点也都有解决办法，相关的书籍和文章已经有很多。但有了我们这两节的基础，你可以自己动手来验证这些知识点了。 在作为开源项目的PlayScript代码库中，我会继续迭代、修改与垃圾收集有关的算法，如果你有兴趣可以继续一起研究。 ## 思考题 在这节课的示例程序中，为了启动垃圾回收机制，我采用了一个普通的函数调用的方式。但是，有没有办法对这个方式进行优化？比如，因为当前函数要退出了，除了返回值，其他变量都不用检查了。再比如，这个函数的栈桢也可以被垃圾回收函数复用，就像尾调用优化那样。我想问一下，你要如何修改现有的调用垃圾回收函数的机制，才能实现上面的优化呢？ 欢迎把这节课分享给更多对内存管理感兴趣的朋友。我是宫文学，我们下节课见。 ## 资源链接 [这节课的示例代码目录在这里！](https://gitee.com/richard-gong/craft-a-language/tree/master/34-35)