源码深度：Boehm GC分配与碎片管理

元数据

• 系列：Unity和C#的GC剖析与对比
• 章节：05-源码深度-Boehm GC与IL2CPP
• 编号：05-03
• 标签：Boehm GC, Size-Class分配, 空闲链表, 碎片合并, Lazy Free
• 阅读时间：~30分钟
• 依赖知识：05-01数据结构、05-02标记阶段

概述

Boehm GC的分配系统采用分级空闲链表（Size-Class Free Lists）策略，将对象按大小分组，每组维护独立的空闲链表。由于Boehm GC不支持压缩和对象移动，碎片管理是其核心挑战。本文深入分析Size-Class分配机制、空闲链表管理、碎片合并策略以及Lazy Free优化。

Size-Class分配机制

大小分级

// gc_alloc.c // Boehm GC将对象大小分为多个等级（Size Class） // 每个等级对应一个空闲链表 // 小对象分级（word为单位） // 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56, 64, ... // 使用近似2的幂次分组，减少分级数量 #define GC_TINY_FREELISTS 64 // 小对象分级数 // 大小到Size-Class的映射 static inline int GC_size_to_class (size_t size) { // 转换为word数 size_t words = (size + sizeof(word) - 1) / sizeof(word); if (words <= GC_TINY_FREELISTS) { // 小对象：直接使用words作为索引 return words - 1; } // 大对象：使用对数分组 int log = 0; size_t s = words; while (s > 1) { s >>= 1; log++; } return GC_TINY_FREELISTS + log; } // Size-Class到实际大小的映射 static size_t GC_class_to_size[] = { 1 * sizeof(word), // class 0 2 * sizeof(word), // class 1 3 * sizeof(word), // class 2 // ... 64 * sizeof(word), // class 63 128 * sizeof(word), // class 64 (大对象) 256 * sizeof(word), // class 65 // ... };

分配入口

// gc_inline.h // 内联分配函数（性能关键路径） static inline void * GC_malloc_inline (size_t size) { // 1. 对齐大小 size = GC_align_size(size); // 2. 计算Size-Class int size_class = GC_size_to_class(size); size_t actual_size = GC_class_to_size[size_class]; // 3. 从空闲链表分配 obj_head *obj = GC_free_lists[size_class]; if (obj) { // 快路径：空闲链表非空 GC_free_lists[size_class] = obj->next; return obj; } // 慢路径：空闲链表为空 return GC_malloc_slow(size, size_class, actual_size); }

快路径分配

// gc_inline.h // 快路径：从空闲链表取出一个块 static inline void * GC_malloc_fast (int size_class) { obj_head *obj = GC_free_lists[size_class]; if (GC_LIKELY(obj != NULL)) { // 空闲链表非空，取出头节点 GC_free_lists[size_class] = obj->next; // 清零对象（如果需要） // Boehm GC默认不清零，由调用方负责 return obj; } return NULL; // 触发慢路径 }

慢路径分配

// gc_alloc.c static void * GC_malloc_slow (size_t size, int size_class, size_t actual_size) { // 1. 检查是否需要GC if (GC_proc_instance.used_heap_size > GC_proc_instance.gc_threshold) { GC_try_to_collect(GC_never_stop_func); } // 2. 尝试从现有堆块中获取空闲块 void *obj = GC_alloc_from_blocks(size_class, actual_size); if (obj) return obj; // 3. 分配新的堆块 hblk *new_hblk = GC_alloc_heap_sect(HBLKSIZE); if (!new_hblk) { // OOM return GC_oom_fn(size); } // 4. 将新堆块切分为对象大小的块 GC_init_hblk(new_hblk, actual_size, NORMAL); // 5. 从新堆块中分配 obj = GC_alloc_from_hblk(new_hblk, actual_size); return obj; }

从堆块中分配

// gc_alloc.c // 从堆块的空闲链表中分配 static void * GC_alloc_from_hblk (hblk *h, size_t obj_size) { hblkhdr *hdr = GC_get_header((ptr_t)h); // 检查块是否有空闲块 if (hdr->hb_free_list == NULL) { return NULL; } // 取出空闲链表头 obj_head *obj = hdr->hb_free_list; hdr->hb_free_list = obj->next; // 更新统计 GC_proc_instance.used_heap_size += obj_size; return obj; } // 从多个堆块中查找可用块 static void * GC_alloc_from_blocks (int size_class, size_t obj_size) { // 遍历所有堆块，查找匹配大小的块 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); if (hdr->hb_obj_size == obj_size && hdr->hb_free_list != NULL) { return GC_alloc_from_hblk(h, obj_size); } } return NULL; }

空闲链表管理

空闲链表初始化

// gc_alloc.c // 将新堆块切分为相同大小的空闲块 static void GC_init_hblk (hblk *h, size_t obj_size, int obj_kind) { hblkhdr *hdr = GC_get_header((ptr_t)h); // 设置堆块头 hdr->hb_obj_size = obj_size; hdr->hb_obj_kind = obj_kind; hdr->hb_block_kind = BLK_FREE; hdr->hb_last_gc = GC_proc_instance.gc_no; // 清除标记位 memset(hdr->hb_marks, 0, sizeof(hdr->hb_marks)); // 初始化空闲链表 int obj_count = HBLKSIZE / obj_size; obj_head *prev = NULL; for (int i = 0; i < obj_count; i++) { obj_head *obj = (obj_head*)((char*)h + i * obj_size); obj->next = prev; prev = obj; } hdr->hb_free_list = prev; // 更新全局统计 GC_proc_instance.free_bytes += obj_count * obj_size; }

空闲链表分配可视化

堆块(4KB), obj_size=64B: 初始化后: +--------+--------+--------+--------+--------+--------+ | Free_0 | Free_1 | Free_2 | Free_3 | ... | Free_63| +--------+--------+--------+--------+--------+--------+ | | | | | v v v v v NULL Free_0 Free_1 Free_2 Free_62 (链表头) 分配3个对象后: +--------+--------+--------+--------+--------+--------+ | Obj1 | Obj2 | Obj3 | Free_3 | ... | Free_63| +--------+--------+--------+--------+--------+--------+ | v Free_4 -> Free_5 -> ... -> NULL (链表头)

碎片管理

碎片问题

由于Boehm GC不支持压缩和对象移动，长期运行后堆中会产生碎片：

碎片示例: +----+----+----+----+----+----+----+----+----+----+ |Live|Free|Live|Free|Free|Live|Free|Live|Free|Free| | 64 | 64 | 64 | 64 | 64 | 64 | 64 | 64 | 64 | 64 | +----+----+----+----+----+----+----+----+----+----+ 总空闲: 6 * 64 = 384B 但最大连续空闲: 2 * 64 = 128B 无法满足256B的分配请求（即使总空闲足够）

碎片合并策略

// gc_reclaim.c // Boehm GC的碎片合并策略 // 由于不支持对象移动，只能在清扫时合并相邻空闲块 static void GC_coalesce_free_blocks (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); // 只处理可回收类型的块 if (hdr->hb_obj_kind == NORMAL || hdr->hb_obj_kind == PTRFREE) { GC_coalesce_block(h, hdr); } } } static void GC_coalesce_block (hblk *h, hblkhdr *hdr) { size_t obj_size = hdr->hb_obj_size; int obj_count = HBLKSIZE / obj_size; // 检查块中所有对象的标记状态 int live_count = 0; int free_count = 0; for (int i = 0; i < obj_count; i++) { ptr_t obj = (ptr_t)h + i * obj_size; if (IS_MARKED(hdr, obj)) { live_count++; } else { free_count++; } } if (free_count == obj_count) { // 整个块都空闲：可以归还给OS或加入大块池 GC_free_hblk(h); } else if (live_count == obj_count) { // 整个块都存活：无需处理 hdr->hb_block_kind = BLK_USED; } else { // 部分空闲：重建空闲链表 GC_rebuild_free_list(h, hdr); } } static void GC_rebuild_free_list (hblk *h, hblkhdr *hdr) { size_t obj_size = hdr->hb_obj_size; int obj_count = HBLKSIZE / obj_size; // 清空现有空闲链表 hdr->hb_free_list = NULL; // 遍历块中所有对象 obj_head *prev = NULL; for (int i = 0; i < obj_count; i++) { ptr_t obj = (ptr_t)h + i * obj_size; if (!IS_MARKED(hdr, obj)) { // 未标记的对象加入空闲链表 obj_head *free_obj = (obj_head*)obj; free_obj->next = prev; prev = free_obj; } } hdr->hb_free_list = prev; }

块级合并

// gc_reclaim.c // 相邻堆块的合并（如果两个相邻块都完全空闲） static void GC_coalesce_adjacent_hblks (void) { // 按地址排序堆块 GC_sort_heap_sects(); for (int i = 0; i < GC_proc_instance.heap_sects_count - 1; i++) { hblk *h1 = GC_proc_instance.heap_sects[i]; hblk *h2 = GC_proc_instance.heap_sects[i + 1]; // 检查是否地址相邻 if ((ptr_t)h1 + HBLKSIZE == (ptr_t)h2) { hblkhdr *hdr1 = GC_get_header((ptr_t)h1); hblkhdr *hdr2 = GC_get_header((ptr_t)h2); // 两个块都必须完全空闲 if (hdr1->hb_block_kind == BLK_FREE && hdr2->hb_block_kind == BLK_FREE) { // 合并为一个大块 GC_merge_hblks(h1, h2); // 从数组中移除h2 GC_remove_heap_sect(i + 1); i--; // 重新检查当前位置 } } } }

Lazy Free机制

什么是Lazy Free

Lazy Free（懒惰释放）是Boehm GC的一种优化策略：在GC清扫阶段，不立即回收所有未标记对象，而是延迟到分配时按需回收。这减少了GC暂停时间，将清扫工作分摊到后续的分配操作中。

// gc_reclaim.c // Lazy Free：标记完成后不立即清扫，而是在分配时按需回收 // 标记完成后设置"需要清扫"标志 void GC_start_reclaim (void) { if (GC_proc_instance.lazy_free) { // Lazy Free模式：只标记需要清扫的块 GC_mark_blocks_for_reclaim(); // 不立即清扫 } else { // 立即清扫模式 GC_reclaim_all(); } } // 标记需要清扫的块 static void GC_mark_blocks_for_reclaim (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); // 检查块中是否有未标记对象 GC_bool needs_reclaim = FALSE; size_t obj_size = hdr->hb_obj_size; int obj_count = HBLKSIZE / obj_size; for (int j = 0; j < obj_count; j++) { ptr_t obj = (ptr_t)h + j * obj_size; if (!IS_MARKED(hdr, obj)) { needs_reclaim = TRUE; break; } } if (needs_reclaim) { hdr->hb_block_kind = BLK_NEEDS_RECLAIM; } } }

分配时Lazy Free

// gc_alloc.c // 分配时检查块是否需要清扫 static void * GC_alloc_from_blocks_lazy (int size_class, size_t obj_size) { 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); if (hdr->hb_obj_size != obj_size) continue; // 检查块是否需要清扫 if (hdr->hb_block_kind == BLK_NEEDS_RECLAIM) { // Lazy Free：在分配前清扫这个块 GC_reclaim_block_now(h, hdr); } // 从清扫后的块中分配 if (hdr->hb_free_list != NULL) { return GC_alloc_from_hblk(h, obj_size); } } return NULL; } // 立即清扫单个块 static void GC_reclaim_block_now (hblk *h, hblkhdr *hdr) { size_t obj_size = hdr->hb_obj_size; int obj_count = HBLKSIZE / obj_size; // 重建空闲链表 obj_head *prev = NULL; for (int i = 0; i < obj_count; i++) { ptr_t obj = (ptr_t)h + i * obj_size; if (!IS_MARKED(hdr, obj)) { // 未标记对象：加入空闲链表 obj_head *free_obj = (obj_head*)obj; free_obj->next = prev; prev = free_obj; } else { // 已标记对象：清除标记位（为下次GC准备） CLEAR_MARK(hdr, obj); } } hdr->hb_free_list = prev; hdr->hb_block_kind = BLK_FREE; // 更新统计 int free_count = 0; obj_head *p = prev; while (p) { free_count++; p = p->next; } GC_proc_instance.free_bytes += free_count * obj_size; }

Lazy Free的优势

// gc_reclaim.c // Lazy Free的性能优势 // 不使用Lazy Free: // GC暂停时间 = 标记时间 + 全部清扫时间 // 标记: O(存活对象数) // 清扫: O(堆总大小) <-- 可能很长 // // 使用Lazy Free: // GC暂停时间 = 标记时间 + 标记块时间 // 标记: O(存活对象数) // 标记块: O(堆块数) <-- 很快 // // 清扫工作分摊到后续分配: // 每次分配时清扫一个块 // 分配开销增加少量清扫时间 // 但GC暂停时间显著减少 // 伪代码对比 void gc_without_lazy() { mark_phase(); // 暂停 sweep_all_blocks(); // 暂停（长） // 总暂停: mark + sweep_all } void gc_with_lazy() { mark_phase(); // 暂停 mark_blocks_for_reclaim(); // 暂停（短） // 总暂停: mark + mark_blocks（短） // 清扫在后续分配中完成 void* alloc() { if (block_needs_reclaim) sweep_block_now(); // 分摊到分配 return alloc_from_block(); } }

大对象分配

// gc_alloc.c // 大对象（超过一个堆块大小的对象）的特殊分配 static void * GC_alloc_large (size_t size) { // 计算需要的堆块数 size_t hblks = (size + HBLKSIZE - 1) / HBLKSIZE; size_t total = hblks * HBLKSIZE; // 从OS分配连续堆块 hblk *h = (hblk*)GC_alloc_os_memory( total, GC_PROT_READ | GC_PROT_WRITE); if (!h) { // OOM：尝试GC后重试 GC_try_to_collect(GC_never_stop_func); h = (hblk*)GC_alloc_os_memory(total, GC_PROT_READ | GC_PROT_WRITE); if (!h) return NULL; } // 设置堆块头 hblkhdr *hdr = GC_get_header((ptr_t)h); hdr->hb_obj_size = 0; // 0表示大对象 hdr->hb_obj_kind = NORMAL; hdr->hb_block_kind = BLK_USED; // 大对象大小存储在堆块头的额外字段中 GC_set_large_obj_size(h, size); // 注册到堆段数组 GC_register_large_hblk(h, hblks); // 更新统计 GC_proc_instance.heap_size += total; GC_proc_instance.used_heap_size += total; return (void*)h; }

分配性能分析

分配路径性能

// gc_alloc.c // 分配路径的性能统计 typedef struct { int fast_path_count; // 快路径命中次数 int slow_path_count; // 慢路径命中次数 int gc_trigger_count; // GC触发次数 int new_block_count; // 新块分配次数 int64_t total_alloc_bytes; int64_t total_alloc_time_ns; } GC_alloc_stats; static GC_alloc_stats GC_alloc_statistics; // 输出统计 void GC_print_alloc_stats (void) { GC_alloc_stats *s = &GC_alloc_statistics; printf("=== Boehm GC Alloc Stats ===\n"); printf("Fast path: %d (%.1f%%)\n", s->fast_path_count, (double)s->fast_path_count / (s->fast_path_count + s->slow_path_count) * 100); printf("Slow path: %d (%.1f%%)\n", s->slow_path_count, (double)s->slow_path_count / (s->fast_path_count + s->slow_path_count) * 100); printf("GC triggers: %d\n", s->gc_trigger_count); printf("New blocks: %d\n", s->new_block_count); printf("Avg alloc time: %.1f ns\n", (double)s->total_alloc_time_ns / (s->fast_path_count + s->slow_path_count)); }

分配路径总结

GC_malloc(size) | +-- GC_align_size(size) // 对齐 +-- GC_size_to_class(size) // 计算Size-Class | +-- 快路径: free_lists[class] != NULL? | YES -> 取出头节点, 返回 [~80%] | NO -> 慢路径 | +-- 慢路径: |-- 检查是否需要GC |-- 遍历现有堆块找空闲块 |-- 如果找到: 返回 [~15%] |-- 如果没找到: |-- 分配新堆块 |-- 初始化空闲链表 |-- 从新块分配 [~5%]

总结

Boehm GC的分配系统在"简单"和"效率"之间取得了平衡。Size-Class分级使大多数分配在O(1)时间内完成，Lazy Free将清扫工作分摊到分配中减少了暂停时间。但由于不支持对象移动和压缩，碎片问题是Boehm GC的根本局限——这将在下一章IL2CPP集成中进一步讨论。