解读 V8 GC Log（二）: 堆内外内存的划分与 GC 算法

2022-03-21 22:28:09

原作者：洗影

上一篇文章介绍了理解 V8 GC Log 的意义在哪，简单介绍了一下 V8 GC 的整体特征。在这篇文章里，我们介绍 V8 中堆内存的划分与新老生代的 GC 算法。这些基础知识是理解 V8 GC Log 的关键，不过这篇文章的介绍点到为止，能够读懂 V8 GC Log 即可，以免把大家在细节中带迷路。

V8 堆外内存的划分

在 V8 中，大部分的对象都直接在堆上创建（虽然 V8 的优化编译器会将一些静态分析后确定完全本地的对象放到栈上，即所谓的逃逸分析 = Escape Analysis，此处不赘述）。V8 将堆划分成了几个不同的空间（space，以下以 4.x 为准，老版本有更多），其中新生代包括一个 New Space，老生代包括 Old Space，Code Space，和 Map Space，此外还有一个特殊的 Large Object Space 用于存储特别大的对象（也属于老生代）。V8 的用户还可以自行维护堆外内存，并将这些内存的数据上报给 V8，帮助 V8 调整 GC 的策略和时机。

新生代的 New Space 使用 Scavenge 算法回收，而老生代的几个 space 都使用 Mark-Sweep-Compact 回收。内存按照 1MB 分页，并且都按照 1MB 对齐。新生代的内存页是连续的，而老生代的内存页是分散的，以链表的形式串联起来。Large Object Space 也分页，但页的大小会比 1MB 大一些。

每一个 Space 里的内存页开头都是一个 header，里面包括

各种元数据和 flag（比如本页属于哪个空间），GC 需要使用的各种统计数据，GC 各个阶段在本页的进展状况等
一个 slots buffer，记录了所有指向本页内对象的指针，以节省回收时的一些扫描操作。
一个 skip list，将本页划分为多个区（region）并维护各个区的边界，用于快速搜索页上的对象

紧跟着 header 的是一个 bitmap，上面的每个 bit 对应页上的一个字，用于后面会介绍到的 marking。前面的部分按 32 个字对齐后，剩余的空间才是用于存储对象的。

堆内空间：New Space（新生代）

正如前面的弱分代假设所说，大部分的对象都死得早，因此大部分的对象都属于新生代，诞生在这里。放在其他地方分配的例外主要包括：

对象的布局结构信息在 Map Space 分配
编译出来的代码在 Code Space 分配
太大不能直接放进来的对象在 Large Object Space 分配
创建的对象常常被晋升到 Old Space 的函数，在这些对象达到一定的生存率（survival rate）之后它再创建的对象会被自动在 Old Space 分配

出于垃圾回收算法（Scavenge）的需要，New Space 被平分成两半（两个 semispace），任一时刻只有一半被使用。在垃圾回收日志中看到的 new 和 semispace 相关的字段就与 New Space 有关。

堆内空间：Old Space（老生代）

Old Space 保存的是老生代里的普通对象（在 V8 中指的是 Old Object Space，与保存对象结构的 Map Space 和保存编译出的代码的 Code Space 相对），这些对象大部分是从新生代（即 New Space）晋升而来。

V8 4.x 引入了一个新的机制 pretenuring，来应对弱分代假设不成立的情况。当 V8 探测到某些函数创建的对象有很高的存活率率（survival rate），经常晋升到老生代（存活超过2次）的时候，下次这些函数再创建的对象将会直接在 Old Space 分配。这样就省略了这些对象在 New Space 第一次 GC 的时候大量复制到另一个 semispace，第二次 GC 又大量复制到 Old Space 的开销。即使猜错了，反正下一次老生代 GC 的时候这些对象也会被回收走，影响不大。

在垃圾回收日志中看到的 old 相关的字段就与 Old Space 有关，而 survival 和 promoted 相关的字段则与对象在新老生代之间的迁移有关。

堆内空间：Large Object Space（老生代）

当 V8 需要分配一个 1MB 的页（减去 header）无法直接容纳的对象时，就会直接在 Large Object Space 而不是 New Space 分配。在垃圾回收时，Large Object Space 里的对象不会被移动或者复制（因为成本太高）。Large Object Space 属于老生代，使用 Mark-Sweep-Compact 回收内存。

堆内空间：Map Space（老生代）

所有在堆上分配的对象都带有指向它的“隐藏类”的指针，这些“隐藏类”是 V8 根据运行时的状态记录下的对象布局结构，用于快速访问对象成员，而这些“隐藏类”（Map）就保存在 Map Space。Map Space 也属于老生代，所以也使用 Mark-Sweep-Compact 回收内存。当一个 Map 不再被任何对象引用的时候（即不再有相应结构的对象存在的时候），它也会被回收掉。

堆内空间：Code Space（老生代）

在最近针对小内存设备的 ignition 解释器推出之前，V8 长期以来都只有编译器（JavaScript 是脚本语言不代表它一定会被解释执行 :)），包括一个无优化的基线编译器（baseline compiler）和一个优化编译器（optimizing compiler，目前默认是 CrankShaft，还有一个升级版的 TurboFan）。这些编译器针对运行平台架构编译出的机器码（存储在可执行内存中）本身也是数据，连同一些其它的元数据（比如由哪个编译器编译，源代码的位置等），放置在 Code Space 中。在 Node.js 开发中比较常见的是模板引擎编译渲染函数后，V8 为这些函数编译出的机器码会出现在这里。注意 JavaScript 代码中的函数一开始只会被解析成抽象语法树，只有在它第一次执行的时候才会被真正编译成机器码，并且在程序的执行过程中会根据统计数据不断进行优化和修改。

Code Space 属于老生代，垃圾回收的算法也是 Mark-Sweep-Compact（实际在 V8 的源代码里 Code Space 跟 Old Space 用的是同一个类）。这些代码同样会被引用，当引用消失后（即没有办法再调用这段代码的时候）也会被回收。

堆空间页管理抽象：Memory Allocator

前面说到，V8 中的堆划分为空间，而空间又划分为页，这些内存页里的内存是怎么来的呢？V8 为此抽象出了 Memory Allocator，专门用于与操作系统交互，当空间需要新的页的时候，它从操作系统手上分配（使用mmap）内存再交给空间，而当有内存页不再使用的时侯，它从空间手上接过这些内存，还给操作系统（使用munmap）。因此堆上的内存都要经过 Memory Allocator 的手，在垃圾回收日志中也能看到它经手过的内存的使用情况。

堆外内存：External memory

除了堆上的内存以外，V8 还允许用户自行管理对象的内存，比如 Node.js 中的 Buffer 就是自己管理内存的。这些叫做外部内存（external memory），在垃圾回收的时候会被 V8 跳过，但是外部的代码可以通过向 V8 注册 GC 回调，跟随 JS 代码中暴露的引用的回收而自行回收内存，相关信息也会显示在垃圾回收日志中。外部内存也会影响 V8 的 GC，比如当外部内存占用过大时，V8 可能会选择 Full GC（包含老生代）而不是仅仅回收新生代，尝试触发用户的 GC 回调以空出更多的内存来使用。

由于外部代码需要将自己使用的内存通过 Isolate::AdjustAmountOfExternalAllocatedMemory 告知 V8 才能记录下来，假如外部代码没有做好上报，就可能出现进程 RSS（Resident Set Size，实际占用的内存大小）很高，但减去垃圾回收日志中 Memory Allocator 分配的堆内存和 V8 记录下的外部内存之后，有很大一部分“神秘消失”的现象，这个时候就可以定位到 C++ addon 或者是 Node.js 自己管理的内存里去排查问题了。

GC 算法

新生代：Scavenge

前面说到，V8 中的新生代对象使用的是 Scavenge 算法进行垃圾回收的。这是一种典型的以空间换时间的垃圾回收算法，基本思路就是将内存分成两半，任一时刻只有一半（semispace）被使用，使用中的叫做 to space，不被使用的叫做 from space。当程序需要创建新对象，而 New Space 的空间不够用时，Scavenge 就会启动，先调换两个 semispace，这样充满待清理对象的就是 from space 了。然后将根对象以及一些从特定集合可达的对象先复制到 to space，接下来从这些对象开始做宽度优先扫描，找到所有存活（可达）的对象，之前已经存活过一次的晋升到 Old Space，其他的复制到 to space 去，并在 from space 原来的位置留下一个转发地址（forwarding address）。这样当复制结束后，to space 就充满了存活的对象，而 from space 就可以当成被清空了，下次再 GC 的时候可以直接拿来重新使用。由于对象存活两次就会晋升，所以下次 GC 的时候就不需要放在这次残存在 from space 的转发地址了，对于还没有死的对象直接扫描外来引用，并更新为对象迁移到 Old Space 之后的地址即可。

这种方法的好处是实现起来简单，不需要考虑空间中死亡对象留下的空洞，每次 GC 后存活的对象自然被整理成连续的一块，而且因为做的是宽度优先搜索，临近的对象大多有一定的联系，提高了 cache locality。由弱分代假设可知，新生代的对象分配和 GC 会十分频繁，并且每次 GC 后存活下来的对象应该只有比较少的一部分。在分配时，我们只需要挪动一下记录 semispace 顶部的指针（allocation pointer），空出适当的空间来用即可（称为 bump-pointer allocation），只要 New Space 还有充足的空间不需要引发 GC，这个过程就相当廉价。在 GC 时，由于活下来的对象一般只有一小部分，需要扫描和复制的量也应该是不大的。由于 New Space 是连续的，这种 GC 方法保证了 New Space 中的对象总是按照分配时间排序，只要记录 GC 后 allocation pointer 的位置（age mark），在下一次 GC 时就可以直接确定该位置以下的存活对象活过了两次 GC，可以晋升。因此，这种算法很好地满足了新生代的需要。由于 New Space 很小（一般在 1～20 MB 左右，V8 会根据程序的运行状态自动调整），V8 可以在新生代 GC 的时候 stop-the-world，而不对程序的运行造成太大的影响（新生代 GC 一般在 0~3ms 内，V8 设计的目标在 1ms 以下，超过 1ms 的一般是 bug 或者用户代码发生了内存问题）。

Scavenge 的局限性

Scavenge 只适用于新生代这种对象生死频繁，并且整体内存使用量不大，可以忍受浪费多一倍空间的情况。对于对象多长驻，而且空间会越来越大的老生代来说，这种算法显然就划不来了，毕竟复制对象这种操作（V8 用的是 memcpy）在量大的时候本身也是比较昂贵的，扫描大量的引用也会对性能产生影响。于是对于老生代，我们需要其他的垃圾回收策略，V8 选择的是后文所说的 Mark-Sweep／Mark-Compact。

写屏障（write barrier）

在介绍老生代的 GC 算法之前，我们还需要补充一个问题。由于我们想回收的是新生代的对象，只需要检查指向新生代的引用，那么在跟随根对象->新生代或者新生代->新生代的引用时，我们可以放心走下去。而对于新生代->老生代或者根对象->老生代的引用，如果选择跟随，要是中间九转十八弯，扫遍了整个堆，花费的时间就划不来了。但是如果不沿着扫描，万一新生代里有对象只有从老生代过来的引用怎么办呢？如果不能确定老生代没有对象指向它，我们就不能放心地回收掉这个对象了，这样一推，新生代的 GC 就没法做了。

对于这个问题，V8 选择的解决方案是使用写屏障（write barrier），即每次往一个对象写入一个指针（添加引用）的时候，都执行一段代码，这段代码会检查这个被写入的指针是否是由老生代对象指向新生代对象的，这样我们就能明确地记录下所有从老生代指向新生代的指针了。这个用于记录的数据结构叫做 store buffer，每个堆维护一个，为了防止它无限增长下去，会定期地进行清理、去重和更新。这样，我们可以通过扫描，得知根对象->新生代和新生代->新生代的引用，通过检查 store buffer，得知老生代->新生代的引用，就没有漏网之鱼，可以安心地对新生代进行回收了。

这样往所有的写入指针的操作注入额外的记录动作的方法，看上去似乎会严重影响性能，但看前文介绍弱分代假设的时候读者应该也注意到了，在不考虑统计概率的情况下讨论性能是很耍流氓的。

在程序运行的过程中，写一般比读发生得少得多
老生代->新生代的指针写入并不常见，我们可以先检查指针的两头是不是在同一代，是的话直接跳过写屏障即可。由于 V8 里的页都是按至少 1MB（20 bit）对齐的，任意一个内存地址从第一位到倒数第 21 位之间的数字，都可以唯一定位到一个内存页上。这样我们可以快速得到指针两端的页，而每个内存页的 header 又自带 flag 标明自己属于哪个空间，于是我们只要做一下位运算和简单的检查就可以跳过占多数的新生代->新生代和老生代->老生代引用了。
V8 的优化编译器可以通过静态分析证明一个对象不会出现在老生代，或者证明这个对象不会被（内联后的）函数作用域外的对象引用而直接将它放在栈上，这时我们也就没必要对这类对象执行写屏障了。

因此，大部分场景下写屏障的性能开销相比起扫描整个堆的开销，还是划算得多的。

优化：分配合并（Allocation Folding）

由于在 JavaScript 代码中经常出现连续的分配（比如很多人习惯在函数的开头把所有需要的变量都尽早分配好），V8 引入了分配合并（Allocation Folding）的机制。在优化过的函数里（此时假设这些对象结构遵循一定的模式且稳定不变，如果变了立刻退出改用普通的分配机制），将这些连续分配的对象组合起来，先为它们分配一块能容纳所有对象的内存，然后再逐个初始化（注意如果有 pretenuring 可能会一起分配在 Old Space）。这样，当这些对象在初始化时互相之间出现引用的时候，由于它们是一起分配的，我们可以确定它们一定在同一个空间里，连检查指针两端都不用，直接就能跳过写屏障。并且由于只需要一次性找一块足够大的空间，而不需要为每个对象找一次合适的内存，这项优化也提高了分配内存的速度。

老生代：Mark-Sweep／Mark-Compact

对于老生代，V8 使用的是 Mark-Sweep／Mark-Compact 来回收垃圾。这两种方法其实是紧密联系的。

三色 marking

V8 为每一个内存页维护了一个 marking bitmap，页内的每一个可用于分配的字在其中都有一个对应的 bit，由于 V8 中的对象起码是 2 个字的长，所以对象们起码能对应 2 个 bit，于是这个标记最多能有 4 种类型。V8 使用的是一种三色 marking（tricolor marking）的算法，白色代表这个对象可以被回收；黑色代表这个对象不能回收，而且它产生的所有引用都已经扫描完毕；灰色代表这个对象不能被回收，但它产生的引用还没有被扫描完。

当老生代 GC 启动的时候，V8 会扫描老生代的对象，沿着引用做标记（mark），将这些标记保留在对应的 marking bitmap 里。最开始的时候所有的非根对象带有的标记都是白的，接着 V8 将根对象直接引用的对象放进一个显式的栈，并标记它们为灰色。接下来，V8 从这些对象开始做深度优先搜索，每访问一个对象，就将它 pop 出来，标记为黑色，然后将它引用的所有白色对象标记为灰色，push 到栈上，如此循环往复，直到栈上的所有对象都 pop 掉了为止。这样，最后老生代的对象就只有黑色（不可回收）和白色（可以回收）两种了。

需要注意的是，当对象太大无法 push 进空间有限的栈的时候，V8 会先把这个对象保留灰色放弃掉，然后将整个栈标记为溢出状态（overflowed）。在溢出状态下，V8 会继续从栈上 pop 对象，标记为黑色，再将引用的白色对象标记为灰色和溢出，但不会将这些灰色的对象 push 到栈上去。这样没多久，栈上的所有对象都被标黑清空了。此时 V8 开始遍历整个堆，把那些同时标记为灰色和溢出对象按照老方法标记完。由于溢出后需要额外扫描一遍堆（如果发生多次溢出还可能扫描多遍），当程序创建了太多大对象的时候，就会显著影响 GC 的效率。

标记完死亡对象（白色）之后，V8 就可以回收这些死亡对象占用的内存了。回收的方法有两种：sweeping 或者 compacting。

Sweeping

Sweeping 就是扫描每一页的 marking bitmap，找到死亡对象占用的连续区块，将这些块添加到随该页维护的一个 freelist 里。这个数据结构保存了页上可用于下次分配的内存位置，可以用于 compacting、新生代晋升与老生代直接分配对象等需要在老生代中分配内存的场景。V8 中按照可用内存块大小的区间分出了多个 freelist，这样能更快找到合适的可用内存。

Compacting

Compacting 则是将页中的所有存活的对象都转移到另一页里（evacuation），这样存活对象都被移走了的那一页就可以直接还给操作系统了。这种方法主要发生在某一页中死亡对象留下来的空洞（hole）比较多的时候，但也会有例外，比如这一页中的对象被太多其他页的对象引用的时候就不会 compact，不然移动对象后更新所有指过来的指针将会是不小的开销。

优化：增量式 marking（incremental marking）

前面说过，V8 的垃圾回收器已经开始往增量式、并发式改进了，目前主要的改进发生在老生代的 GC 上，因为新生代的 GC 一般很短暂，优化的空间不大。

在 marking 方面，V8 引入了增量式 marking（incremental marking），原来 V8 需要停止程序的运行，扫描完整个堆，回收完内存后，才能重新运行程序，每次暂停时间可以到几百甚至几千毫秒，严重影响了程序的性能。现在 V8 将 marking 拆分开来，当堆大小涨到一定程度的时候，开始增量式 GC，在每次分配了一定量的内存后／触发了足够多次写屏障后，就暂停一下程序，做几毫秒到几十毫秒的 marking，然后恢复程序的运行。当老生代需要 GC 的时候，由于之前断断续续地标记过了大部分的堆内存，不需要从头扫描整个堆，工作量便大大减少了（除去每个 GC 周期的最后一次 marking，V8 对增量式 marking 设计的运行时间不超过 5ms，超过了一般有问题）。

增量式的 marking 主要步骤和原来的类似，但是因为在完成整个堆的 marking 之前程序会断断续续地运行，改变对象的生存状态，所以 V8 在前面所说的写屏障之上，额外加多了一个需要记录的情形：每次产生从黑色对象指向白色对象的引用的时候，将被指的对象重新标记为灰色，放回 marking 的队列里，这样便不会误将存活的对象标记为死亡了。

优化：black allocation

V8 5.x 还引入了 black allocation，将所有新出现在 Old Space 的对象（包括pretentured 的分配或者晋升）直接标记为黑色，放在特殊的内存页（black page）中，这个内存页里只有黑色的对象，因此一定能活过下一次 GC。新出现在 Old Space 的对象一般存活过下一轮 GC 的几率非常高，这样做可以一定程度上减轻 marking 的负担，即使猜错了，下下轮 marking 前这些对象又会先刷白，只逃过一次 GC 所以造成的影响也不大。

优化：lazy sweeping, concurrent sweeping, parallel sweeping

在 sweeping 方面，V8 引入了 lazy sweeping，当我们已经标记完哪些对象的内存可以被回收之后，并没有必要马上回收完这些内存，然后再开始运行。我们可以先恢复程序的运行，再一点点对各页的空间做 sweeping。当然，只有当所有页的内存都被回收完之后，我们才能重新开始 marking。

另外，由于这些死亡对象占据的空间不会在被运行中的程序使用，V8 还引入了 concurrent sweeping，让其他线程同时来做 sweeping，而不用担心和执行程序的主线程冲突，这样在 sweeping 的时候，就不需要暂停程序的执行了。

同样地，因为 sweeping 作用的对象们已经确定而且不会被主线程访问，可以比较容易地并行化，V8 引入了 parallel sweeping，让多个 sweeping 线程同时工作，提升 sweeping 的吞吐量，缩短整个 GC 的周期。

小结

V8 中大部分 JavaScript 对象都分配在堆上，堆内空间分为频繁诞生与死亡的对象所属的 New Space（<20MB），倾向于长时间存活的对象所属的 Old Space，可执行代码所属的 Code Space，用于描述对象隐藏类的数据所属的 Map Space，以及大对象所属的 Large Object Space。这些空间都分页，页在 V8 和操作系统之间的转移由 Memory Allocator 进行管理。堆外空间（External Memoery）由外部代码维护，通过 API 上报大小给 V8，通过注册 GC 回调随 V8 内对象的回收而自行回收。

V8 对新生代使用 Scavenge 算法，将 New Space 分成两半，每次只使用一半，回收时相当于从根对象开始做 BFS，将存活的对象移到另一半中，死亡对象原来占据的空间就相当于被释放了，这一过程一般不超过 1ms。老生代使用 tricolor marking 增量式地标记存活对象，相当于从根对象开始做 DFS，每次 marking 一般不超过 5ms。标记完后，使用 sweeping 扫描并回收死亡对象占据的空间，用 compacting 移动存活对象整理碎片严重的内存页。Sweeping 按需执行（lazy），一般不阻碍主线程执行程序（concurrent），并且由多个 sweeper 线程并行完成（parallel）。为了降低新生代 GC 扫描的开销，以及保证增量式 marking 的结果不会随着程序运行失效，V8 引入了写屏障（write barrier），在发生引用变化的时候执行一段代码，用于记录相关信息以供 GC 快速查询。

预告

本系列还有一篇实战，介绍如何获取 V8 GC 日志，如何阅读该日志以及如何利用 GC 日志解决一个由 V8 对闭包的实现引起的内存泄漏，敬请期待~ （Node Live Beijing 上的 slides 与代码点这里）

码农公寓

解读 V8 GC Log（二）: 堆内外内存的划分与 GC 算法