源码深度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_size64B: 初始化后: ------------------------------------------------ | 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 FreeLazy 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%]总结机制说明优势劣势Size-Class分级按大小分组空闲链表减少搜索时间内部碎片空闲链表每个Size-Class独立链表O(1)分配无法合并跨块碎片合并清扫时合并相邻空闲块减少碎片无法消除碎片Lazy Free延迟清扫到分配时减少GC暂停分配延迟增加大对象直接OS分配避免碎片化无法压缩Boehm GC的分配系统在简单和效率之间取得了平衡。Size-Class分级使大多数分配在O(1)时间内完成Lazy Free将清扫工作分摊到分配中减少了暂停时间。但由于不支持对象移动和压缩碎片问题是Boehm GC的根本局限——这将在下一章IL2CPP集成中进一步讨论。