V8 垃圾回收中的增量标记（Incremental Marking）与并发清理（Concurrent Sweeping）的同步机制

各位同仁，下午好！今天我们探讨一个在高性能JavaScript引擎V8中至关重要的话题：垃圾回收中的增量标记（Incremental Marking）与并发清理（Concurrent Sweeping）及其同步机制。这两个技术是V8实现低延迟、高吞吐量垃圾回收的核心，它们将原本可能导致长时间停顿（Stop-the-World）的GC操作分解为小块，甚至与主程序（Mutator）并发执行，从而显著提升了用户体验。

V8垃圾回收的挑战与演进

JavaScript作为一门动态语言，其内存管理是自动进行的，这极大地简化了开发。然而，自动内存管理并非没有代价。垃圾回收器（Garbage Collector, GC）的任务是识别并回收不再被程序使用的内存，但这个过程本身会消耗CPU时间，并可能导致应用程序出现可感知的停顿。

在早期的GC实现中，尤其是在传统的“标记-清除”（Mark-Sweep）算法中，GC过程通常需要暂停整个应用程序的执行，才能安全地遍历对象图并回收内存。这种“Stop-the-World”式的停顿，对于小型应用可能微不足道，但对于大型、内存密集型应用（如复杂的Web应用、Node.js服务器）来说，几十甚至上百毫秒的停顿是不可接受的，它会直接影响用户体验和系统响应性。

V8作为Google Chrome的JavaScript引擎，其设计目标之一就是极致的性能。为了应对GC停顿的挑战，V8的垃圾回收器经过了多次迭代和优化，引入了一系列先进技术，其中增量标记和并发清理是降低“Stop-the-World”时间的关键。

标记-清除垃圾回收基础

在深入增量标记和并发清理之前，我们先回顾一下“标记-清除”算法的基本原理。

标记阶段（Marking Phase）：
从一组“根”（Roots）对象开始，这些根是程序可以直接访问的对象，例如全局变量、栈上的局部变量、寄存器中的值等。GC从这些根对象出发，通过遍历所有可达（reachable）的对象，将它们标记为“存活”（Live）。这个遍历过程通常采用深度优先搜索（DFS）或广度优先搜索（BFS）。

// 概念性代码：标记算法的简化表示

enum MarkState { WHITE, GREY, BLACK }; // 三色标记法

class Object {
public:
    MarkState mark_state = WHITE;
    std::vector<Object*> children; // 指向其他对象的指针

    void AddChild(Object* child) {
        children.push_back(child);
    }
};

// 标记函数
void Mark(Object* obj) {
    if (obj->mark_state == GREY || obj->mark_state == BLACK) {
        return; // 已经访问过或正在访问
    }

    obj->mark_state = GREY; // 标记为灰色，表示已访问但子节点未处理
    std::vector<Object*> worklist;
    worklist.push_back(obj);

    while (!worklist.empty()) {
        Object* current = worklist.back();
        worklist.pop_back();

        for (Object* child : current->children) {
            if (child->mark_state == WHITE) {
                child->mark_state = GREY;
                worklist.push_back(child);
            }
        }
        current->mark_state = BLACK; // 所有子节点都已处理或加入工作列表
    }
}

// 从根开始标记
void MarkFromRoots(const std::vector<Object*>& roots) {
    for (Object* root : roots) {
        Mark(root);
    }
}

清除阶段（Sweeping Phase）：
标记阶段完成后，所有未被标记为存活（即仍为白色）的对象都是垃圾。清除阶段会遍历整个堆内存，回收这些白色对象占用的空间，并将这些空间添加到空闲列表（Free List）中，以备后续分配使用。

// 概念性代码：清除算法的简化表示

class Heap {
public:
    std::vector<Object*> all_objects; // 堆中所有对象
    FreeList free_list; // 存储空闲内存块

    void Sweep() {
        for (Object* obj : all_objects) {
            if (obj->mark_state == WHITE) {
                // 回收对象内存
                free_list.Add(obj->address, obj->size);
            } else {
                // 重置标记状态为白色，为下一次GC做准备
                obj->mark_state = WHITE;
            }
        }
        // all_objects 实际上是遍历内存页，而不是一个对象列表
    }
};

这种朴素的“标记-清除”算法在执行标记和清除时，都需要停止JavaScript程序的执行，这正是导致GC停顿的根本原因。

增量标记（Incremental Marking）

为了减少标记阶段的停顿时间，V8引入了增量标记。其核心思想是将一个漫长的标记过程分解为多个小的、可管理的步骤。在每个步骤中，GC只标记一部分对象，然后将控制权交还给JavaScript程序（Mutator），让程序继续执行一小段时间，然后再由GC执行下一个标记步骤。

挑战：标记并发下的正确性

增量标记的最大挑战在于，当GC在执行标记步骤时，JavaScript程序也在同时修改对象图。这种并发性可能导致两种错误：

1. 对象被错误地回收（程序崩溃）：如果GC已经访问了一个黑色对象，并且该黑色对象的一个字段被修改，使其指向了一个尚未被标记的白色对象。如果此时白色对象变得只可达于这个黑色对象，并且没有其他路径可达，那么在标记结束时，这个白色对象可能仍是白色，从而被错误地回收。
2. 浮动垃圾（内存泄漏）：一个白色对象在GC开始时是可达的，但在GC过程中变得不可达。如果GC错误地将其标记为黑色，那么它将不会被回收，成为“浮动垃圾”。虽然这不会导致程序崩溃，但会浪费内存。

为了解决第一个更严重的问题（程序崩溃），V8采用了“写屏障”（Write Barrier）机制。

写屏障（Write Barrier）与三色不变性

写屏障是一小段在程序修改对象指针时自动执行的代码。它的作用是维护GC的正确性，即使在标记阶段，Mutator也在修改对象图。

V8的增量标记基于三色抽象（Tri-color Abstraction）：

• 白色（White）：尚未被GC访问的对象，可能是垃圾。
• 灰色（Grey）：已被GC访问，但其子对象尚未被访问的对象（已加入GC工作列表）。
• 黑色（Black）：已被GC访问，且其所有子对象也已被访问（或已加入GC工作列表）的对象。

增量标记的目标是最终所有可达对象都变为黑色，所有不可达对象都保持白色。在理想情况下，我们希望维护以下三色不变性（Tri-color Invariant）：

“黑色对象不指向白色对象” (Black objects do not point to white objects)。

如果一个黑色对象指向了一个白色对象，这就违反了不变性，意味着白色对象可能被遗漏，从而被错误回收。

V8主要采用写屏障（Write Barrier）来维护这个不变性，具体实现更接近于快照在开始时（Snapshot-at-the-Beginning, SATB）的变种。

SATB写屏障的工作原理：
当Mutator修改一个对象的指针字段时，如果：

1. 被修改的宿主对象（host）是黑色的。
2. 被覆盖的旧值（old_value）是白色的（表示它可能还没有被GC扫描到）。

那么，这个old_value在被覆盖之前，会被记录到一个“写屏障缓冲区”（Write Barrier Buffer）中。GC会在后续的某个标记步骤中，重新扫描这些缓冲区中的对象，确保它们的可达性。这样，即使old_value在程序执行过程中变得不可达，GC也会在缓冲区中找到它并将其标记为灰色，从而避免了它被错误回收。

// 概念性V8写屏障（SATB风格）
// 假设这是在V8内部，通过JIT生成的机器码或运行时调用触发的
void V8Heap::WriteBarrier(HeapObject* host, Object* old_value, Object* new_value) {
    // 检查GC是否处于标记阶段
    if (!IsMarkingInProgress()) {
        return; // 如果不在标记，则无需写屏障
    }

    // 假设我们有一个MarkingState来查询对象的标记状态
    if (MarkingState::IsBlack(host) && MarkingState::IsWhite(old_value)) {
        // 如果黑色对象将要覆盖一个白色指针，则将这个旧的白色对象加入到待重新扫描的集合中
        // 这是一个缓冲区，会在GC的下一个增量步中被处理
        MarkingState::RecordObjectForRescanning(old_value);
    }
    // 注意：这里的new_value通常不需要特殊处理，因为SATB关注的是“在快照开始时”的对象图，
    // 任何新指向的对象（无论是新的还是旧的）都会在后续的正常标记中被发现，
    // 或者如果它是新创建的，则默认被标记为灰色。
}

// 示例：JavaScript中对象属性的赋值操作，在编译后可能触发写屏障
// var obj = {};
// var val1 = {}; // 假设 val1 是白色对象
// var val2 = {}; // 假设 val2 是白色对象
// obj.prop = val1; // 第一次赋值，obj如果是黑色，val1是白色，此处触发写屏障，记录val1

// 编译后的伪代码（简化）
// function SetProperty(obj_ptr, prop_offset, new_value_ptr) {
//     Object* host = (Object*)obj_ptr;
//     Object* old_value = host->GetField(prop_offset); // 获取旧值

//     // 执行实际的赋值操作
//     host->SetField(prop_offset, new_value_ptr);

//     // 触发写屏障
//     V8Heap::WriteBarrier(host, old_value, new_value_ptr);
// }

Dijkstra写屏障（Incremental Update）：
虽然V8主要使用SATB的变种，但了解Dijkstra的屏障有助于全面理解。Dijkstra屏障关注的是“新值”。当一个黑色对象host的字段被修改，使其指向一个白色对象new_value时，Dijkstra屏障会立即将new_value染成灰色。这样就保证了黑色对象不会指向白色对象。

// 概念性Dijkstra写屏障（仅作对比说明）
void DijkstraWriteBarrier(HeapObject* host, Object* old_value, Object* new_value) {
    if (!IsMarkingInProgress()) return;

    if (MarkingState::IsBlack(host) && MarkingState::IsWhite(new_value)) {
        // 将新指向的白色对象立即染成灰色
        MarkingState::MarkGrey(new_value);
        // 并将其添加到GC工作列表中，以便后续扫描其子节点
        MarkingState::AddToWorklist(new_value);
    }
}

SATB的优点是实现相对简单，且不会增加GC的遍历工作量（因为只记录旧值）。缺点是可能产生更多的“浮动垃圾”，因为它将“快照”冻结在GC开始时，任何在此之后变为不可达的对象都可能被误标记为存活。Dijkstra屏障能减少浮动垃圾，但可能需要更频繁地修改对象状态和GC工作列表。V8通过精妙的设计，平衡了这些考量。

增量标记的调度与执行

V8的增量标记通常在JavaScript主线程空闲时，或者在达到一定内存分配阈值时触发。

• 空闲时间调度：V8利用浏览器的requestIdleCallback机制（或类似的内部机制），在主线程有空闲时间时执行一小步标记。
• 内存分配阈值：当JavaScript程序分配了一定量的内存后，V8会强制执行一个增量标记步骤，以防止堆增长过快。

这些增量标记步骤非常短，通常只有几毫秒，从而将GC停顿分散到应用程序的整个生命周期中，使其对用户不可感知。

标记工作列表（MarkingWorklist）：
V8使用MarkingWorklist来管理待处理的灰色对象。增量标记步骤会从工作列表中取出对象进行扫描，将其子对象加入工作列表，然后将自身染成黑色。写屏障记录的对象也会被添加到这个工作列表中。

最终标记（Finalize Marking）：
在增量标记的最后阶段，V8会执行一个短时间的“Stop-the-World”停顿，来处理剩余的写屏障缓冲区中的对象，并确保所有可达对象都被正确标记。这个停顿通常非常短，因为大部分工作已经在增量阶段完成。

并发清理（Concurrent Sweeping）

标记阶段完成后，我们已经知道哪些对象是存活的，哪些是垃圾。接下来的清除阶段就是回收这些垃圾对象占用的内存。如果清除阶段也像传统GC那样“Stop-the-World”，那么即使标记实现了增量，总停顿时间仍然会很高。因此，V8引入了并发清理。

并发清理的核心思想是将清除操作卸载到后台的GC辅助线程（Helper Threads）上执行，而主JavaScript线程可以继续执行JS代码。

挑战：清理并发下的同步

并发清理的主要挑战在于：

1. Mutator与Sweeper的内存访问冲突：Mutator需要分配新的内存，它会向空闲列表请求。Sweeper则负责生成空闲内存块并将其添加到空闲列表。这两个操作必须同步，以防止数据竞争。
2. Sweeper对未完成标记的页面的访问：Sweeper只能清理已经完成标记的内存页（Memory Chunk）。如果一个页面还在增量标记过程中，Sweeper不能触碰它。

同步机制

V8主要通过以下机制实现并发清理的同步：

1. 内存页（Memory Chunk）与空闲列表（Free Lists）：
   V8的堆内存被划分为多个MemoryChunk（通常是1MB的页面）。每个MemoryChunk可以有自己的局部空闲列表。
   Sweeper的工作：GC辅助线程会遍历这些MemoryChunk。对于一个已完成标记的MemoryChunk，Sweeper会扫描其中的所有对象。如果一个对象未被标记（即是白色），它就被认为是垃圾，Sweeper会将其地址和大小添加到该MemoryChunk的局部空闲列表中。
   Allocator的工作：当Mutator需要分配内存时，它会首先尝试从全局或局部空闲列表中获取。

2. 锁（Mutexes）与原子操作（Atomic Operations）：
   为了保护共享数据结构（如全局空闲列表、MemoryChunk的状态）免受并发访问的破坏，V8会使用互斥锁（std::mutex）和原子操作（std::atomic）。

   • 空闲列表的同步：当多个Sweeper线程完成各自MemoryChunk的清除工作后，它们会将其局部空闲列表中的内存块合并到全局空闲列表中。这个合并过程需要锁来保护，以确保空闲列表的数据结构完整性。分配器在从全局空闲列表获取内存时，也需要获取相应的锁。
   • MemoryChunk状态的同步：每个MemoryChunk都有一个状态，指示它是否正在被Sweeper清理。这个状态通常使用std::atomic变量进行更新，以确保可见性和排序。

   // 概念性MemoryChunk及其状态
   class MemoryChunk {
   public:
       enum SweepingState { kNotSweeping, kSweepingInProgress, kSweepingDone };
   
       // 原子变量确保多线程对状态的可见性
       std::atomic<SweepingState> sweeping_state_ = kNotSweeping;
       std::mutex sweeping_mutex_; // 保护chunk内部的某些操作，如free_list的合并
       std::condition_variable sweeping_cv_; // 用于等待sweeping完成
   
       FreeList local_free_list_; // Sweeper在此chunk中生成的空闲列表
   
       // ... 其他成员 ...
   
       SweepingState GetSweepingState() {
           return sweeping_state_.load(std::memory_order_acquire);
       }
   
       void SetSweepingState(SweepingState state) {
           sweeping_state_.store(state, std::memory_order_release);
           if (state == kSweepingDone) {
               // 通知所有等待该chunk清理完成的线程
               std::lock_guard<std::mutex> lock(sweeping_mutex_);
               sweeping_cv_.notify_all();
           }
       }
   
       // ... 获取局部空闲列表等方法 ...
   };
   
   // 概念性并发Sweeper线程
   void ConcurrentSweeperThread::Run() {
       while (true) {
           MemoryChunk* chunk = GetNextChunkToSweep(); // 从共享队列中获取待清理的chunk
           if (!chunk) {
               // 没有更多chunk，或者GC完成
               break;
           }
   
           chunk->SetSweepingState(MemoryChunk::kSweepingInProgress);
   
           // 遍历chunk中的对象，判断是否被标记
           for (Object* obj = chunk->StartOfObjects(); obj < chunk->EndOfObjects(); obj = obj->NextObject()) {
               if (!obj->IsMarked()) { // 假设IsMarked()能安全读取标记位
                   // 将垃圾对象添加到chunk的局部空闲列表
                   chunk->local_free_list_.Add(obj->address, obj->size);
               }
           }
   
           chunk->SetSweepingState(MemoryChunk::kSweepingDone);
   
           // 将局部空闲列表中的内存块合并到全局空闲列表
           // 这个操作通常需要全局锁来保护
           GlobalFreeLists::Merge(chunk->local_free_list_);
       }
   }

3. 分配器与清理器的协同：
   当主线程的分配器需要内存时：

   • 它首先尝试从已有的空闲列表中分配。
   • 如果空闲列表为空，分配器会检查是否有正在进行清理的MemoryChunk。如果存在，分配器可能会短暂等待某个MemoryChunk完成清理，以便利用其生成的空闲内存。
   • 为了避免长时间等待，V8的分配器可以“预清理”（Pre-sweep）一个正在被清理的MemoryChunk。这意味着主线程会暂时帮助Sweeper线程完成该MemoryChunk的清理工作，然后利用其产生的空闲内存。这种机制避免了主线程完全停顿，同时加速了内存的可用性。

   // 概念性分配器
   class HeapAllocator {
   public:
       Object* Allocate(size_t size) {
           // 1. 尝试从全局空闲列表分配
           Object* obj = GlobalFreeLists::TryAllocate(size);
           if (obj) return obj;
   
           // 2. 尝试从正在清理的chunk中获取或帮助清理
           for (MemoryChunk* chunk : GetSweepingChunks()) { // 遍历正在清理的chunk
               if (chunk->GetSweepingState() == MemoryChunk::kSweepingInProgress) {
                   // 尝试“预清理”该chunk，即主线程帮助完成清理
                   // 这会短暂阻塞主线程，但通常比等待一个完整的GC周期要短
                   // 实际V8实现会更复杂，可能只清理一部分或等待通知
                   std::unique_lock<std::mutex> lock(chunk->sweeping_mutex_);
                   chunk->sweeping_cv_.wait(lock, [chunk]{
                       return chunk->GetSweepingState() == MemoryChunk::kSweepingDone;
                   });
                   obj = chunk->local_free_list_.TryAllocate(size);
                   if (obj) return obj;
               }
           }
   
           // 3. 如果所有空闲列表都为空，则可能需要从操作系统申请新的内存页，
           // 或者触发一个Full GC（如果内存压力大）。
           return AllocateNewPageFromOS(size);
       }
   };

并发清理的阶段：
并发清理通常在标记阶段结束后开始。在标记的最后阶段，V8会确保所有页面的标记信息都已稳定，然后将这些页面提交给并发清理器。清理器会在后台线程中独立工作，将垃圾对象转化为可用的空闲内存。

增量标记与并发清理的同步集成

增量标记和并发清理是V8垃圾回收器中的两个独立但又紧密协作的机制。它们的同步和集成是确保整个GC流程高效且正确运行的关键。

特性/阶段	增量标记（Incremental Marking）	并发清理（Concurrent Sweeping）
主要目标	减少标记阶段的“Stop-the-World”停顿，将标记工作分解。	减少清除阶段的“Stop-the-World”停顿，将清理工作卸载到辅助线程。
执行线程	主JavaScript线程（Mutator），在空闲或分配阈值触发时执行小步。	GC辅助线程（Helper Threads）。
同步机制	写屏障（Write Barrier，SATB变种），维护三色不变性，记录并发修改。	锁（Mutexes）、原子操作（Atomics）保护共享空闲列表和Chunk状态；分配器与清理器协同。
数据结构	标记工作列表（MarkingWorklist）、写屏障缓冲区。	内存页（MemoryChunk）、局部空闲列表、全局空闲列表。
阶段依赖	必须在标记阶段完成，才能进行清理。	依赖于标记阶段的结果（对象的标记状态）。
对Mutator影响	写屏障引入少量开销；增量步引入微小停顿。	分配内存时可能需要等待或帮助清理，但大部分时间可并发执行。

整体流程概览：

1. GC开始：V8判断需要进行一次老年代GC。
2. 增量标记启动：GC进入标记阶段，启动增量标记。主线程在执行JS的同时，周期性地执行一小步标记。
3. 写屏障激活：在整个增量标记期间，JavaScript代码中的指针修改会触发写屏障，将可能被遗漏的对象记录到缓冲区。
4. 标记完成（Finalize Marking）：当增量标记接近完成时，V8会执行一个非常短的“Stop-the-World”停顿。在此期间，它会处理所有写屏障缓冲区中记录的对象，确保所有可达对象都被标记。这是保证标记正确性的最后一道防线。
5. 并发清理启动：一旦标记阶段完全结束，GC辅助线程被唤醒，开始对所有已完成标记的MemoryChunk进行并发清理。主线程同时继续执行JS。
6. Mutator分配内存：当JS程序需要分配新内存时，它会首先尝试从空闲列表中获取。如果空闲列表不足，它会与并发清理器协调，可能等待某个MemoryChunk清理完成，或者主动“预清理”来获取内存。
7. 清理完成：所有MemoryChunk清理完毕后，GC辅助线程进入休眠状态，等待下一次GC循环。

这种紧密的协作，使得V8能够有效地将大部分GC工作从主线程卸载，显著降低了GC停顿。

总结与展望

增量标记和并发清理是V8垃圾回收器中不可或缺的优化技术。它们通过将耗时的GC操作分解为细小的增量步骤，并利用多线程并发执行，极大地减少了“Stop-the-World”停顿，使得JavaScript应用的响应性和流畅性得到了显著提升。写屏障机制在增量标记中保证了并发操作下的正确性，而精巧的内存页管理、锁、原子操作以及分配器与清理器的协同，则确保了并发清理能够安全高效地运行。这些技术的结合，是现代高性能JavaScript引擎能够应对复杂Web应用和Node.js服务器内存管理挑战的关键所在。