05-02-源码-Boehm GC标记阶段

源码深度：Boehm GC标记阶段

元数据

• 系列：Unity和C#的GC剖析与对比
• 章节：05-源码深度-Boehm GC与IL2CPP
• 编号：05-02
• 标签：Boehm GC, 保守标记, Root发现, Partial Clean, 标记栈
• 阅读时间：~30分钟
• 依赖知识：05-01数据结构

概述

Boehm GC的标记阶段是其最核心的组件。与SGen的精确标记不同，Boehm GC使用保守标记算法：不依赖对象的精确类型信息，而是将对象体中所有看起来像指针的word都当作潜在引用。这种设计使得Boehm GC可以与任意C/C++代码集成，但也带来了伪指针风险和扫描开销。本文深入分析保守标记算法的实现、根发现机制、Partial Clean优化以及标记栈管理。

保守标记算法

标记阶段入口

// gc_mark.c // 标记阶段入口 void GC_mark_roots (void) { // 1. 清除所有标记位 GC_clear_marks_all(); // 2. 初始化标记栈 GC_mark_stack_init(); // 3. 推送根集合 GC_push_roots(); // 4. 处理标记栈 while (!GC_mark_stack_empty()) { GC_mark_one_step(); } // 5. 处理弱引用和finalizer GC_mark_finalize(); }

清除所有标记位

// gc_mark.c static void GC_clear_marks_all (void) { // 遍历所有堆段，清除标记位图 for (int i = 0; i < GC_proc_instance.heap_sects_count; i++) { hblk *h = GC_proc_instance.heap_sects[i]; hblkhdr *hdr = GC_get_header((ptr_t)h); // 清除标记位图 memset(hdr->hb_marks, 0, sizeof(hdr->hb_marks)); } }

标记单个对象

// gc_mark.c // 保守标记：检查地址是否指向堆内对象，如果是则标记 static GC_bool GC_mark_one (ptr_t addr) { // 1. 检查是否在GC堆内 hblkhdr *hdr = GC_get_header(addr); if (!hdr) { return FALSE; // 不在堆内，不是对象指针 } // 2. 计算堆块基址 hblk *h = (hblk*)((ptr_t)addr & ~(HBLKSIZE - 1)); // 3. 检查地址是否对齐到对象边界 size_t obj_size = hdr->hb_obj_size; if (obj_size == 0) { // 大对象：整个堆块是一个对象 // 地址必须在对象起始位置 if ((ptr_t)addr != (ptr_t)h) { return FALSE; } } else { // 检查地址是否对齐到对象大小 size_t offset = (ptr_t)addr - (ptr_t)h; if (offset % obj_size != 0) { // 不对齐：可能是指向对象内部的指针 // 保守处理：找到对象起始位置 addr = (ptr_t)h + (offset / obj_size) * obj_size; } } // 4. 检查是否已标记 if (IS_MARKED(hdr, addr)) { return FALSE; // 已标记，跳过 } // 5. 设置标记位 SET_MARK(hdr, addr); // 6. 如果对象可能含指针，压入标记栈 if (hdr->hb_obj_kind != PTRFREE) { GC_mark_stack_push(addr, hdr); } return TRUE; }

保守扫描对象体

// gc_mark.c // 扫描对象体中的所有word，保守地标记可能的引用 static void GC_scan_object_body (ptr_t obj, hblkhdr *hdr) { size_t obj_size = hdr->hb_obj_size; if (obj_size == 0) { // 大对象：获取实际大小 obj_size = GC_get_large_obj_size(obj); } // 遍历对象体中每个word ptr_t end = obj + obj_size; for (ptr_t p = obj; p < end; p += sizeof(word)) { word value = *(word*)p; // 保守检查：是否指向堆内 if (GC_is_heap_ptr(value)) { GC_mark_one((ptr_t)value); } } }

标记栈处理

// gc_mark.c // 标记栈：存储待扫描的对象（灰色节点） typedef struct mark_stack_entry { ptr_t obj; // 对象地址 hblkhdr *hdr; // 堆块头 size_t scan_offset; // 已扫描到的偏移（增量标记用） } mark_stack_entry; static mark_stack_entry *GC_mark_stack; static mark_stack_entry *GC_mark_stack_top; static mark_stack_entry *GC_mark_stack_limit; // 压入标记栈 static void GC_mark_stack_push (ptr_t obj, hblkhdr *hdr) { if (GC_mark_stack_top >= GC_mark_stack_limit) { GC_mark_stack_grow(); } GC_mark_stack_top->obj = obj; GC_mark_stack_top->hdr = hdr; GC_mark_stack_top->scan_offset = 0; GC_mark_stack_top++; } // 弹出并处理一个标记栈条目 static void GC_mark_one_step (void) { GC_mark_stack_top--; mark_stack_entry *entry = GC_mark_stack_top; // 保守扫描对象体 GC_scan_object_body(entry->obj, entry->hdr); } // 标记栈扩容 static void GC_mark_stack_grow (void) { size_t old_size = GC_mark_stack_limit - GC_mark_stack; size_t new_size = old_size * 2; mark_stack_entry *new_stack = (mark_stack_entry*)GC_alloc_os_memory( new_size * sizeof(mark_stack_entry), GC_PROT_READ | GC_PROT_WRITE); memcpy(new_stack, GC_mark_stack, old_size * sizeof(mark_stack_entry)); // 更新指针 GC_mark_stack_top = new_stack + (GC_mark_stack_top - GC_mark_stack); GC_mark_stack = new_stack; GC_mark_stack_limit = new_stack + new_size; }

Root发现机制

根集合组成

// gc_root.c // Boehm GC的根集合由以下部分组成： // 1. 线程栈（包括寄存器） // 2. 静态数据区（.data, .bss段） // 3. 通过GC_add_roots注册的自定义根 // 4. GC Handle表 void GC_push_roots (void) { // 1. 扫描所有线程的栈和寄存器 GC_push_all_thread_stacks(); // 2. 扫描静态数据区 GC_push_roots_static(); // 3. 扫描注册的自定义根 GC_push_roots_custom(); // 4. 扫描GC Handle表 GC_push_roots_handles(); }

线程栈扫描

// gc_pthread.c // 扫描所有线程的栈 static void GC_push_all_thread_stacks (void) { // 遍历所有注册的线程 GC_thread *thread = GC_thread_list; while (thread) { // 获取线程的栈范围 ptr_t stack_bottom = thread->stack_base; ptr_t stack_top = thread->stack_ptr; // 当前栈指针 // 保存的寄存器上下文 ptr_t regs = (ptr_t)&thread->context; size_t regs_size = sizeof(thread->context); // 1. 保守扫描寄存器 GC_push_all(regs, regs + regs_size); // 2. 保守扫描栈 GC_push_all_stack(stack_bottom, stack_top); thread = thread->next; } }

保守栈扫描详解

// gc_root.c // 保守扫描一段内存区域 void GC_push_all (ptr_t bottom, ptr_t top) { ptr_t p; // 遍历区域中每个word for (p = bottom; p < top; p += sizeof(word)) { word value = *(word*)p; // 快速过滤：检查地址范围 // 优化：先检查是否在堆段的大致范围内 if (GC_quick_is_heap_ptr(value)) { // 精确检查：页表查找 if (GC_is_heap_ptr(value)) { // 标记对象 GC_mark_one((ptr_t)value); } } } } // 快速过滤：使用地址范围检查 static inline GC_bool GC_quick_is_heap_ptr (word addr) { // 检查是否在堆的大致地址范围内 // 这是一个快速但不精确的检查 return (addr >= GC_heap_addr_min && addr < GC_heap_addr_max); }

静态数据区扫描

// gc_root.c // 扫描静态数据区（.data和.bss段） static void GC_push_roots_static (void) { struct roots_static *root = GC_proc_instance.static_roots; while (root) { GC_push_all(root->start, root->end); root = root->next; } } // 注册静态数据区（在GC初始化时调用） void GC_register_static_roots (void) { // .data段 extern char __data_start[]; extern char __data_end[]; GC_add_roots(__data_start, __data_end); // .bss段 extern char __bss_start[]; extern char __bss_end[]; GC_add_roots(__bss_start, __bss_end); }

GC Handle扫描

// gc_handle.c // Boehm GC支持类似.NET的GC Handle机制 // 在IL2CPP中用于实现GCHandle、WeakReference等 typedef struct { void *obj; // 指向的对象 int type; // Handle类型 // 类型: NORMAL, PINNED, WEAK, WEAK_TRACK_RESURRECTION } GC_handle_entry; static GC_handle_entry *GC_handle_table; static size_t GC_handle_table_size; static void GC_push_roots_handles (void) { for (size_t i = 0; i < GC_handle_table_size; i++) { if (GC_handle_table[i].obj) { switch (GC_handle_table[i].type) { case GC_HANDLE_NORMAL: case GC_HANDLE_PINNED: // 强引用：标记对象 GC_mark_one((ptr_t)GC_handle_table[i].obj); break; case GC_HANDLE_WEAK: case GC_HANDLE_WEAK_TRACK: // 弱引用：不标记，在标记完成后处理 break; } } } }

Partial Clean机制

什么是Partial Clean

Partial Clean是Boehm GC的一种优化策略：在标记阶段完成后、清扫阶段之前，对某些"明显不可达"的堆块进行快速清理，减少完整清扫的工作量。

// gc_reclaim.c // Partial Clean：在标记完成后立即回收某些块 void GC_partial_clean (void) { // 遍历所有堆块 for (int i = 0; i < GC_proc_instance.heap_sects_count; i++) { hblk *h = GC_proc_instance.heap_sects[i]; hblkhdr *hdr = GC_get_header((ptr_t)h); // 只处理PTRFREE类型的块 // PTRFREE对象不含指针，可以快速判断可达性 if (hdr->hb_obj_kind == PTRFREE) { GC_partial_clean_block(h, hdr); } } } static void GC_partial_clean_block (hblk *h, hblkhdr *hdr) { size_t obj_size = hdr->hb_obj_size; int obj_count = HBLKSIZE / obj_size; // 检查块中每个对象的标记状态 int all_unmarked = TRUE; int all_marked = TRUE; for (int i = 0; i < obj_count; i++) { ptr_t obj = (ptr_t)h + i * obj_size; if (IS_MARKED(hdr, obj)) { all_unmarked = FALSE; } else { all_marked = FALSE; // 回收未标记的对象 GC_reclaim_obj(obj, obj_size); } } if (all_unmarked) { // 整个块都不可达，可以归还给OS或加入空闲块池 GC_free_hblk(h); } else if (all_marked) { // 整个块都存活，跳过清扫 hdr->hb_last_gc = GC_proc_instance.gc_no; } }

Partial Clean的优势

// gc_reclaim.c // Partial Clean减少了完整清扫的工作量 // 特别对PTRFREE对象（如byte[], int[]等）效果显著 // 性能对比： // 不使用Partial Clean: // 标记 -> 清扫所有块 -> 重建空闲链表 // 时间复杂度: O(堆大小) // // 使用Partial Clean: // 标记 -> Partial Clean(PTRFREE块) -> 清扫剩余块 // PTRFREE块可以快速处理（无需扫描对象体） // 时间复杂度: O(非PTRFREE块大小) + O(PTRFREE块数)

标记阶段优化

标记位图缓存优化

// gc_mark.c // Boehm GC使用位图标记，与SGen的vtable低位标记不同 // 位图的优势：不修改对象体，对缓存友好 // 劣势：需要额外的内存开销 // 标记位图布局: // 堆块(4KB): // +---+---+---+---+---+---+---+---+---+---+ // | O0| O1| O2| O3| O4| O5| O6| O7| ... | // +---+---+---+---+---+---+---+---+---+---+ // // 标记位图(每个对象1位): // +---+---+---+---+---+---+---+---+ // | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | (O0存活, O2存活, O6存活) // +---+---+---+---+---+---+---+---+

批量标记

// gc_mark.c // 批量处理标记栈，减少函数调用开销 static void GC_mark_batch (int batch_size) { mark_stack_entry batch[GC_MARK_BATCH_SIZE]; int count = 0; // 批量弹出 while (count < batch_size && !GC_mark_stack_empty()) { GC_mark_stack_top--; batch[count++] = *GC_mark_stack_top; } // 批量处理 for (int i = 0; i < count; i++) { GC_scan_object_body(batch[i].obj, batch[i].hdr); } }

并行标记

// gc_par_mark.c // Boehm GC支持并行标记（可选） typedef struct { mark_stack_entry *local_stack; mark_stack_entry *local_stack_limit; mark_stack_entry *local_stack_top; // 全局共享标记栈（用于工作窃取） mark_stack_entry *global_stack; mono_mutex_t *global_lock; int worker_id; volatile int *done_flag; } GC_mark_worker; static void GC_mark_parallel (void) { int n_workers = GC_proc_instance.mark_parallelism; GC_mark_worker *workers = (GC_mark_worker*)calloc(n_workers, sizeof(GC_mark_worker)); // 初始化工作线程 for (int i = 0; i < n_workers; i++) { workers[i].worker_id = i; workers[i].global_stack = GC_mark_stack; workers[i].global_lock = &GC_mark_stack_lock; workers[i].done_flag = &GC_mark_done; // 分配本地标记栈 workers[i].local_stack = (mark_stack_entry*)GC_alloc_os_memory( GC_MARK_STACK_INIT_SIZE * sizeof(mark_stack_entry), GC_PROT_READ | GC_PROT_WRITE); workers[i].local_stack_limit = workers[i].local_stack + GC_MARK_STACK_INIT_SIZE; workers[i].local_stack_top = workers[i].local_stack; } // 启动工作线程 for (int i = 1; i < n_workers; i++) { GC_start_mark_thread(&workers[i]); } // 主线程也参与标记 GC_mark_worker_main(&workers[0]); // 等待所有工作线程完成 GC_wait_mark_workers_done(); }

弱引用与Finalizer处理

弱引用处理

// gc_mark.c // 标记完成后处理弱引用 void GC_mark_finalize (void) { // 1. 处理弱引用 GC_process_weak_refs(); // 2. 处理finalizer队列 GC_process_finalize_queue(); } static void GC_process_weak_refs (void) { // 遍历所有弱引用 for (size_t i = 0; i < GC_handle_table_size; i++) { if (GC_handle_table[i].type == GC_HANDLE_WEAK || GC_handle_table[i].type == GC_HANDLE_WEAK_TRACK) { void *obj = GC_handle_table[i].obj; if (obj && !GC_is_marked(obj)) { // 目标不可达，清空弱引用 GC_handle_table[i].obj = NULL; if (GC_handle_table[i].type == GC_HANDLE_WEAK_TRACK) { // 加入复活队列 GC_add_to_resurrection_queue(obj); } } } } }

Finalizer处理

// gc_mark.c static void GC_process_finalize_queue (void) { // 遍历finalizer队列 GC_finalize_entry *entry = GC_finalize_list; GC_finalize_entry *prev = NULL; while (entry) { GC_finalize_entry *next = entry->next; if (!GC_is_marked(entry->obj)) { // 对象不可达，需要finalizer // 临时标记对象（使其在本次GC中存活） GC_mark_one((ptr_t)entry->obj); // 移到待执行队列 GC_add_to_to_finalize(entry->obj, entry->fn); // 从finalizer队列中移除 if (prev) prev->next = next; else GC_finalize_list = next; } else { prev = entry; } entry = next; } }

保守标记的误标记分析

伪指针场景

// 伪指针示例： // 栈上有一个整数值 0x7F3A0010 // 恰好堆中有一个对象地址为 0x7F3A0010 // 保守GC会将这个整数误认为对象引用，标记该对象为存活 // 伪代码展示： void foo() { int x = 0x7F3A0010; // 一个整数值 // ... 此时GC触发 // GC扫描栈，发现x的值看起来像堆地址 // GC标记地址0x7F3A0010处的对象为存活 // 即使该对象实际上不可达 }

误标记的影响

// 误标记导致的问题： // 1. 内存泄漏：不可达对象被误标记为存活，无法回收 // 2. 级联效应：被误标记对象的引用也被标记 // 导致更多对象无法回收 // 3. 不可预测性：误标记取决于运行时的栈/寄存器状态 // 同一程序在不同运行中可能有不同的GC行为 // 缓解措施： // 1. 黑名单机制：记录可疑地址，避免在这些地址分配对象 // 2. 对齐检查：只将对齐到对象边界的地址视为有效引用 // 3. 堆块隔离：不同类型的对象分配在不同区域 // 减少伪指针命中的概率

总结

Boehm GC标记阶段流程: GC_mark_roots() | +-- GC_clear_marks_all() // 清除所有标记位 | +-- GC_push_roots() // 推送根集合 | |-- GC_push_all_thread_stacks() // 扫描线程栈+寄存器 | |-- GC_push_roots_static() // 扫描静态数据区 | |-- GC_push_roots_custom() // 扫描自定义根 | +-- GC_push_roots_handles() // 扫描GC Handle | +-- while (!mark_stack_empty) // 处理标记栈 | +-- GC_scan_object_body() // 保守扫描对象体 | +-- 遍历每个word | +-- GC_is_heap_ptr() // 检查是否指向堆 | +-- GC_mark_one() // 标记对象+压栈 | +-- GC_mark_finalize() // 处理弱引用和finalizer |-- GC_process_weak_refs() // 清空指向不可达对象的弱引用 +-- GC_process_finalize_queue() // 临时标记需finalizer的对象

Boehm GC的保守标记策略是其最大的设计决策，既带来了通用性优势，也引入了性能和正确性方面的挑战。下一章将分析分配与碎片管理。