PHP7垃圾回收算法

前提本文为了梳理PHP GC工作流程所以从引用计数、部分标记清除算法做引子然后介绍PHP GC工作流程,最后介绍性能更高的GC算法引用计数概述引用计数算法中引入了一个概念计数器。计数器代表对象被引用的次数基本原理为了记录一个对象有没有被其他对象引用我们可以在每个对象的头上引用一个叫“计数器”的东西用来记录有多少其他对象引用了它这个计数器的值的变化都是由mutator引起的。例如public class MyObject { public Object ref null; public static void main(String[] args) { MyObject objA new MyObject(); MyObject objB new MyObject(); objA.ref objB; } }上图为例而objA 做为一个局部变量引用了它所以它的引用计数就是1objB这个局部变量引用了它然后objA又引用了它一次所以它的引用计数就是2mutator在运行中还会不断地修改对象之间的引用关系我们知道这种引用关系的变化都是发生在赋值的时候。例如接上文的例子我们再执行这样一行代码objA null;那么从objA到objB的引用就消失了也就是上图中那个从A的ref指向B的箭头就消失了运行原理update_ptr(ptr, obj){ inc_ref_cnt(obj) // 计数器 dec_ref_cnt(*ptr) // 计数器- *ptr obj // 重新指向 obj } inc_ref_cnt(obj){ obj.ref_cnt } dec_ref_cnt(*ptr){ obj.ref_cnt-- if (obj.ref_cnt 0) for(child : children(obj)) // 当自己被清除时自己所引用的子节点的计数器必须减一。进行递归操作。 dec_ref_cnt(*child) // 然后通过reclaim()函数将obj连接到空闲链表上面 reclaim(obj) }把 obj 赋值给 ptr 这个指针之前我们可以先改变一下这两个对象的引用计数在一次赋值中要先把老的对象的引用计数减一把新的对象的引用计数加一如果某个对象的引用计数为0就把这个对象回收掉然后把这个对象所引用的所有对象的引用计数减1。为什么要先inc_ref_cnt(obj)然后再dec_ref_cnt(*ptr)呢如果按照先dec_ref_cnt()后inc_ref_cnt()函数的顺序调用ptr和 obj又是同一对象的话执行dec_ref_cnt(ptr)时ptr的计数器的值就有可能变为0而被回收再想执行inc_ref_cnt(obj)时obj早就被回收了可能会引发重大的BUG优点可即回收的垃圾: 每个对象在被引用次数为0的时候可以立即知道没有暂停时间: 对象的回收根本不需要另外的GC线程专门去做业务线程自己就搞定了,不需要STW缺点计数器的增减处理频繁循环引用无法回收: objA引用了objBobjB也引用了objA, 两个对象的引用计数就都是1。这种情况下这两个对象是不能被回收的部分标记清除算法概述为了解决循环依赖的问题部分标记清除算法通过把对象涂成4种不同的颜色进行管理四色标记流程前提黑(BLACK): 不是垃圾对象(对象产生的初始颜色)白(WHITE): 垃圾对象灰(GRAY): 搜索完毕的对象阴影(HATCH): 可能是循环垃圾循环引用的对象群是ABC和DE其中A和D由根引用,此外C和E引用F所有对象的颜色现在还是初始的黑色dec_ref_cnt() 函数dec_ref_cnt(obj){ obj.ref_cnt-- if(obj.ref_cnt 0 ) delete(obj) else if(obj.color ! HATCH) obj.color HATCH enqueue(obj, $hatch_queue) }算法在对obj的计数器进行减量操作后检查obj的颜色。当obj的颜色不是阴影的时候算法会将其涂上阴影并追加到队列中由根到A的引用被删除了指向A的指针被追加到队列$hatch_queue之中。A被涂上了阴影new_obj()函数new_obj(size){ obj pickup_chunk(size) // 创建对象 if(obj ! NULL) obj.color BLACK obj.ref_cnt 1 return obj else if(is_empty($hatch_queue) FALSE) // 如果$hatch_queue不为空 scan_hatch_queue() // 标记清除回收垃圾 return new_obj(size) // 重新分配 else allocation_fail() }当分配无法顺利进行的时候程序会调查队列是否为空当队列不为空时程序会通过scan_hatch_ queue() 函数搜索队列分配分块scan_hatch_queue() 函数执行完毕后程序会递归地 调用 new_obj() 函数再次尝试分配。 如果队列为空则分配将会失败scan_hatch_queue(){ // 对象出队 obj dequeue($hatch_queue) // 判断对象是不是阴影 if(obj.color HATCH) paint_gray(obj) // 查找对象进行计数器的减量操作 scan_gray(obj) // 查找灰色对象按条件变换白色对象 collect_white(obj) // 回收白色对象 else if(is_empty($hatch_queue) FALSE) scan_hatch_queue() }paint_gray()函数// 查找对象进行计数器的减量操作 paint_gray(obj){ if(obj.color (BLACK|HATCH)) obj.color GRAY // 搜索完毕的颜色 for(child :children(obj)) (*child).ref_cnt-- paint_gray(*child) }scan_gray()函数// 从第一个灰色的对象开始找找到后如果计数器为0就将颜色改为白色计数器大于0就会执行paint_black(). 然后递归子节点 scan_gray(obj){ if(obj.color GRAY) if(obj.ref_cnt 0 ) paint_black(obj) else obj.color WHITE for(child :children(obj)) scan_gray(child) } // 从那些可能被涂成了灰色的有循环引用的对象群中找出不是垃圾的对象并将其归回原处 paint_black(obj){ obj.color BLACK for(child :children(obj)) (*child).ref_cnt if((*child).color ! BLACK) paint_black(child) }形成了循环垃圾的对象 A、B、C 被涂成了白色而有循环引用的非垃圾对象 D、 E、F 被涂成了黑色collect_white()函数collect_white(obj){ if(obj.color WHITE) obj.color BLACK for(child :children(obj)) collect_white(*child) reclaim(obj) }部分标记清除算法的局限性这个算法不仅付出很大成本搜索对象还需要查找三次对象分别是mark_gray()、sacn_gray()、collect_white()这很大程度的增加了内存管理所花费的时间。还因此对引用计数法最大暂停时间短的优势造成的破坏性的影响PHP7 GC对象颜色流转目前垃圾回收只针对array、object两种类型GC算法简述遍历roots链表 把当前元素标为灰色(zend_refcounted_h.gc_info置为GC_GREY)然后对当前元素的成员进行深度优先遍历把成员的refcount减1并且也标为灰色。(gc_mark_roots())遍历roots链表中所有灰色元素及其子元素如果发现其引用计数仍旧大于0说明这个元素还在其他地方使用那么将其颜色重新标记会黑色并将其引用计数加1在第一步有减1操作。如果发现其引用计数为0则将其标记为白色。(gc_scan_roots())遍历roots链表将黑色的元素从roots移除。然后对roots中颜色为白色的元素进行深度优先遍历将其引用计数加1在第一步有减1操作同时将颜色为白色的子元素也加入roots链表。最后然后将roots链表移动到待释放的列表to_free中。(gc_collect_roots())释放to_free列表的元素zend_refcounted_h 结构体typedef struct _zend_refcounted_h { uint32_t refcount; /* reference counter 32-bit */ union { struct { ZEND_ENDIAN_LOHI_3 ( zend_uchar type, // 当前元素的类型同zval的u1.v.type zend_uchar flags, // 标记数据类型可以是字符串类型或数组类型等 // 后面的两个字节标记当前元素的颜色和垃圾回收池中的位置 // 其中高地址的两位用来标记颜色低地址的14位用于记录位置 uint16_t gc_info ) // keeps GC root number (or 0) and color } v; uint32_t type_info; } u; } zend_refcounted_h;type: 当前元素的类型同zval的u1.v.typeflags: 标记数据类型可以是字符串类型或数组类型等gc_info: 后面的两个字节标记当前元素的颜色和垃圾回收池中的位置其中高地址的两位用来标记颜色低地址的14位用于记录位置define GC_COLOR 0xc000 define GC_BLACK 0x0000(黑色: 不是垃圾对象) define GC_WHITE 0x8000(白色: 垃圾对象) define GC_GREY 0x4000(灰色: 将被标记为白色) define GC_PURPLE 0xc000(紫色: 加入的垃圾收集器)垃圾收集器结构体 - zend_gc_globalstypedef struct _zend_gc_globals { zend_bool gc_enabled; //是否启用gc zend_bool gc_active; //是否在垃圾检查过程中 zend_bool gc_full; //缓存区是否已满 gc_root_buffer *buf; //启动时分配的用于保存可能垃圾的缓存区 gc_root_buffer roots; //指向buf中最新加入的一个可能垃圾 gc_root_buffer *unused; //指向buf中没有使用的buffer gc_root_buffer *first_unused; //指向buf中第一个没有使用的buffer gc_root_buffer *last_unused; //指向buf尾部 gc_root_buffer to_free; //待释放的垃圾列表 gc_root_buffer *next_to_free; //下一待释放的垃圾列表 uint32_t gc_runs; //统计gc运行次数 uint32_t collected; //统计已回收的垃圾数 } zend_gc_globals;buf: 垃圾缓冲区PHP7默认10000个节点位置。第0个位置保留roots: 指向缓冲区中最新加入的可能是垃圾的元素unused: 指向缓冲区中没有使用的位置GC算法没有开始指向空first_unused: 指向缓冲区中第一个未使用的位置新的元素插入缓冲区后指针会向后移动一位last_unused: 指向缓冲区中最后一个位置to_free: 待释放的列表next_to_free: 下一个代释放的列表gc_possible_root 函数 - 把对象加入缓冲区当进行unset的时候会调用对应函数类似于ZEND_UNSET_VAR_SPEC_CV_UNUSED_HANDLER同时判断对象为collectable类型且未加入垃圾回收缓存区。就会调用 gc_possible_root 尝试加入缓冲区/** * brief 缓冲区处理 * 1. 变量检查必须是array或object且必须是黑色说明没有加入过缓冲区 * 2. 首先尝试在unused队列中取一个buffer * 1. 如果unused队列不为空从unused队列中取到一个buffer, unused后移 * 2. 如果GC_G(first_unused) ! GC_G(last_unused) buffer队列未满则从first_unused取一个buffer, 同时将first_unused后移 * 3. 缓冲区已满的情况。启动垃圾回收 跳转到 zend_gc_collect_cycles 函数。垃圾回收之后就有空的buffer可以从unused队列取出 * 3. 得到了新的buffer把传入的变量先设置为字符串然后写入buffer之中并挂载到全局roots链中 * * param ref 是zend_value相应的gc地址 * return ZEND_API */ ZEND_API void ZEND_FASTCALL gc_possible_root(zend_refcounted *ref) { }zend_gc_collect_cycles函数 - GC回收流程/** * brief GC回收流程 * 1. GC_G(roots).next ! GC_G(roots), 判断roots链不为空 * 2. gc_mark_root函数: 遍历roots链表对当前节点value的所有成员(如数组元素、成员属性)进行深度优先遍历把成员refcount减1 * 3. gc_scan_roots函数: 遍历roots链表中所有灰色元素及其子元素如果发现其引用计数仍旧大于0说明这个元素还在其他地方使用 * 那么将其颜色重新标记会黑色并将其引用计数加1。如果发现其引用计数为0则将其标记为白色 * 4. gc_collect_roots 函数: 遍历roots链表将黑色的元素从roots移除 * 对roots中颜色为白色的元素进行深度优先遍历将其引用计数加1同时将颜色为白色的子元素也加入roots链表 * 最后然后将roots链表移动到待释放的列表to_free中 * 5. 把全局to_free列表复制到本地to_free,然后遍历释放最后把回收使用过的垃圾池buffer将其放入unused队列 * * return ZEND_API */ ZEND_API int zend_gc_collect_cycles(void) { }gc_mark_roots 函数 - 对roots链的紫色对象进行标记/** * brief 对roots链的紫色对象进行标记 * */ static void gc_mark_roots(void) { gc_root_buffer *current GC_G(roots).next; while (current ! GC_G(roots)) { // 对紫色对象进行标记 if (GC_REF_GET_COLOR(current-ref) GC_PURPLE) { gc_mark_grey(current-ref); } current current-next; } }gc_mark_grey 函数 - 标记为灰色/** * brief 标记为灰色 * 1. 对不是灰色对象标记为灰色 * 2. 对象类型。通过get_gc获取子节点并递归标记子节点。最后引用计数减1 * 3. 数组类型。如果是全局符号表EG(symbol_table)则将引用标记为黑色并返回 * 如果不是全局符号表代码将把引用转换为 zend_array 类型 * 然后遍历hashtable引用计数减1并递归子节点 * 4. 引用类型。检查引用对象的 val 是否为引用计数类型Z_REFCOUNTED * 如果是那么它会继续判断对象存储EG(objects_store).object_buckets是否为空并且 val 的类型是否为对象类型IS_OBJECT * 如果对象存储不为空或者 val 的类型不是对象类型那么它会将 val 的引用计数值减1 * * param ref */ static void gc_mark_grey(zend_refcounted *ref) { }gc_scan_roots函数 - 对roots链进行扫描static void gc_scan_roots(void) { gc_root_buffer *current GC_G(roots).next; while (current ! GC_G(roots)) { gc_scan(current-ref); current current-next; } }gc_scan 函数 - GC扫描/** * brief GC扫描 * 1. 对象为灰色 * 2. 如果引用计数大于0就把对象标记为黑色,并跳转到gc_scan_black * 3. 如果引用计数小于0则标记为白色(垃圾对象) * 1. 对象类型。通过get_gc获取子节点并递归标记子节点 * 2. 数组类型。如果是全局符号表就标记为黑色 * 如果不是全局符号表代码将把引用转换为 zend_array 类型然后遍历hashtable并递归子节点 * 3. 引用类型。如果对象存储不为空或者 val 的类型不是对象类型那么就goto tail_call * * param ref */ static void gc_scan(zend_refcounted *ref) { }gc_scan_black 函数 - 黑色对象扫描/** * brief 黑色对象扫描 * 1. 标记为黑色(不是垃圾对象) * 2. 对象类型。通过get_gc获取子节点并递归标记子节点。最后引用计数加1 * 3. 数组类型。如果不是全局符号表代码将把引用转换为 zend_array 类型 * 然后遍历hashtable引用计数加1并递归子节点 * 4. 引用类型。如果对象存储不为空或者 val 的类型不是对象类型那么它会将 val 的引用计数值加1 * * param ref */ static void gc_scan_black(zend_refcounted *ref) { }gc_collect_roots 函数 - 对roots链进行回收/** * brief 对roots链进行回收 * 1. 把黑色对象从roots链脱链 * 2. 对roots链的白色对象(垃圾)进行回收通过 gc_collect_white 函数 * 3. 把roots链的对象交换到to_free列表中 * * param flags * param additional_buffer * return int */ static int gc_collect_roots(uint32_t *flags, gc_additional_buffer **additional_buffer) { }gc_collect_white 函数 - 对白色对象进行回收/** * brief 对白色对象进行回收 * 1. 把白色对象设置为黑色对象 * 1. 对象类型。通过get_gc获取子节点并递归标记子节点。如果为黑色对象且子节点过多触发 gc_add_garbage 功能 * 2. 数组类型。如果不是全局符号表代码将把引用转换为 zend_array 类型然后遍历hashtable并递归子节点 * 同时如果为黑色对象且子节点过多触发 gc_add_garbage 功能 * 3. 引用类型。如果对象存储不为空或者 val 的类型不是对象类型那么就goto tail_call * * param ref * param flags * param additional_buffer * return int */ static int gc_collect_white(zend_refcounted *ref, uint32_t *flags, gc_additional_buffer **additional_buffer) { }gc_add_garbage 函数 - 新增垃圾回收空间/** * brief 将不在roots链上的白色元素挂接到roots链上 * 1. 将所有白色元素放到roots链上这当然也包括白色的子元素 * 2. 子元素可能有很多但受限于垃圾缓冲池的大小roots最长只有10000个不够用怎么办呢 * 3. 这时就需要临时申请额外的存储空间gc_additional_buffer * * param ref * param additional_buffer */ static void gc_add_garbage(zend_refcounted *ref, gc_additional_buffer **additional_buffer) { }总结PHP7 GC 算法 与 部分标记清除算法类似重点是对象状态流转和缓冲区队列接下来介绍的是性能更高的引用计数算法RC Immix概述RC Immix 是 合并型引用计数法 Immix结合.与以往的引用计数法相比其吞吐量平均提升12%吞吐量得到改善的原因有两个合并型引用计数法。因为没有通过写入屏障来执行计数器的增减操作所以即使对象间的引用关系频繁发生变化吞吐量也不会下降太多撤除了空闲链表。通过以线为单位来管理分块只要在线内移动指针就可以进行分配了合并型引用计数法在合并型引用计数法中要将指针发生改动的对象和其所有子对象注册到更改缓冲区中等到缓冲区满了就要运行GC(类似于PHP 的unused队列)等到GC回收时才能从缓冲区取出对应的变量进行增量/减量ImmixImmixGC 构成ImmixGC 把堆分为一定大小的块(block), 再把每一个块分成一定大小的线(line). 这个算法不是以对象为单位而是以线为单位回收垃圾块最合适的大小是32k字节线最合适的大小是128字节。每个块就有32 * 1024 / 128 256个线各个块由以下4个域line: 线mark_table: 线对应的标记位串FREE(没有对象)MARKED(标记完成)ALLOCATED(有对象)CONSERVATIVE(保守标记)status: 用于表示每个块使用情况的域FREE(所有线为空)RECYCLABLE(一部分线为空)UNAVAILABLE(没有空的线)hole_ctn: 用于表示碎片化严重程度的指标ImmixGC工作原理分配时程序首先寻找空的线然后安排对象。没找到空的线时候就执行GCGC分为3个步骤执行选定备用的From 块通过hole_ctn数来判断优先选择碎片化最严重的线作为备用From块判断标准为, “From 块中 ALLOCATED 线和 CONSERVATIVE 线的总数” “除From 以外的块中 FREE 线的总数”搜索阶段从根开始搜索对象根据对象分别进行标记处理或复制处理复制处理指的是将备用 From 块里的对象复制到别的块To 块/FREE块并进行压缩清除阶段清除阶段中要搜索各个块的 mark_table如果 mark_table[i] 的值是 ALLOCATED则设定 mark_table[i] FREE合并型引用计数法和Immix融合RC Immix 中不仅对象有计数器线也有计数器这样就可以获悉线内是否存在活动对象对象的计数器表示的是指向这个对象的引用的数量而线的计数器表示的是这个线里存在的活动对象的数量当对象的计数器为 0 时对线的计数器进行减量操作。当线的计数器为 0 时我们就可以将线整个回收再利用了RC Immix 和合并型引用计数法一样在更改缓冲区满了的时候都会查找更改缓冲区这时如果发现了新对象就会把它复制到别的空间(Immix 中的新块)去同时通过被动碎片整理对新的对象进行压缩但是也会导致旧对象碎片化而积极碎片整理。正好完善无法对旧对象进行压缩、无法回收有循环引用的垃圾的问题。原理就是决定要复制到哪个块然后把能够通过指针从根查找到的对象全部复制过去参考资料《垃圾回收的算法与实现》《PHP7 底层设计与源码实现》垃圾回收机制中引用计数法是如何维护所有对象引用的php7垃圾回收机制及相关源码解读[Go三关-典藏版]Golang垃圾回收混合写屏障GC全分析Taking off the gloves with reference counting Immix