《垃圾回收的算法与实现》

发表于   |   分类于

TL;DR

《垃圾回收的算法与实现》一书的读书笔记。

笔记

第1章 学习GC之前

GC 是什么

GC实际上可以看做管理堆上内存中对象的一个应用程序。

GC主要做清理工作，然而GC的实现会影响新对象的分配。

对象的头部以及域

对象分为头部和域两个部分，头部包含对象的基础信息以及GC相关的信息，域则是对象使用者可以直接操作的部分。如果对应到 PHP 上(参见zend_gc.h)，在生成 ZVAL 时，实际上会申请一个 zval_gc_info 大小的空间：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct _zval_gc_info {
	zval z;
	union {
		gc_root_buffer       *buffered;
		struct _zval_gc_info *next;
	} u;
} zval_gc_info;

// ...

/* The following macros override macros from zend_alloc.h */
#undef  ALLOC_ZVAL
#define ALLOC_ZVAL(z) 									\
	do {												\
		(z) = (zval*)emalloc(sizeof(zval_gc_info));		\
		GC_ZVAL_INIT(z);								\
	} while (0)

那么对于上述结构来说，头部应该是名为u的联合体以及zval中关于引用计数的部分，zval z则是对象的域。

GC算法的评价标准

常用的四大标准

  • 吞吐量，即单位时间内GC处理的内存大小
  • 最大暂停时间，即GC会中断程序正常执行的时间
  • 堆的使用效率，即内存的使用方式以及头信息的占用比例
  • 访问的局部性，即是否能更好的利用高速寄存器

第2章 GC标记-清除算法

标记-清除算法的核心是从根出发，通过 DFS 逐个标记活动的对象，标记完成之后遍历堆，回收不活动的对象。

这一算法可能会有如下的一些问题：

  • 碎片化引起分配操作时延增大
  • 不兼容写时拷贝（标记内容位于堆中，执行标记动作时触发不必要的复制操作）

碎片化带来的问题是找到合适内存空间可能需要较长的线性查找操作时间。

为了能减低清除操作带来的时间花费，会把清理工作推迟到需要分配新空间时进行，但是可能会影响分配的速度。

碎片化问题的权衡

碎片化问题，标记-清除算法的解决思路是通过对堆中内存分类进行处理，可以是通过划分多个大小的堆的方式，只允许在特定堆上申请空间，或者是 BiBOP(Big Bag Of Pages) 方法，将堆划分为多个块，每个块只能申请特定大小的空间。

写时拷贝问题

为了兼容这一个问题，通过独立设定标记位的形式，管理堆内存，只处理不在堆上的标记位。

第3章 引用计数法

引用计数法的特点在于内存空间的管理和对象的管理同时进行。

引用计数有：

  • 即刻回收垃圾
  • 缩短了最大暂停时间
  • 不需要大规模的指针操作

这些优点。

但是也有：

  • 计数器操作繁重
  • 降低内存利用率
  • 实现繁琐
  • 无法解决循环引用问题

等缺点，不过上述部分问题都有成熟的应对方案。

计数器操作繁重

通过延迟引用计数法解决根引用计数操作频繁的问题。

核心是预留出ZCT(Zero Count Table)，当一个对象引用计数到达0时加入ZCT，之后在ZCT满之后对根可达的对象引用计数增加，之后在清理引用计数为0的对象。

但是这个会带来的问题是ZCT的大小阈值设定问题，过小频繁触发ZCT扫描，过大导致扫描时长过长。

降低内存使用率

Sticky引用计数法

可以通过Sticky引用计数法，减少用于计数的数据存储空间（研究证明很少有对象有超过32次引用，即在5个bit的存储空间的情况下），之后通过改进后的标记-清除算法进行GC操作，无论是否因为计数器溢出，总能进行GC操作。

改进后的标记-清除算法主要的区别在于：

  • 先将所有对象引用计数设置为0
  • 从根引用的对象出发，使用堆栈记录子对象，并且每个对象保证只进入堆栈一次的前提下，逐个增加引用计数
  • 清理上述递归过程后引用计数仍然为0对象

上述操作完成之后可以处理循环引用问题，简单思考一下：如果A对象引用B对象，B对象引用A对象，根据引用计数原理，二者虽然没有其他对象引用，但是因为计数都为1，所以无法被回收。通过上述方法首先引用计数置0之后，由于从根开始，发现没有任何可达的路径，那么这两个对象最后的引用计数为0，可以被GC。

溢出导致引用计数变为0不会影响GC的原因在于从根出发，如果一个对象是垃圾，那么必定没有可以到达的路径，也就是无法将引用计数增加，即最终引用计数为0。但是如果只是因为溢出，对象总有路径可达，所以不会引起无法GC的问题。

循环引用问题

在Sticky引用计数法中提到可以通过标记-清除算法可以解决循环引用问题，因为遍历整个堆的过程，所以效率会比较底下，所以充满智慧的前人Rafael D.Lins研究出了部分标记-清除算法解决了这个问题。

和常规的标记-清除算法有所不同的是，部分标记-清除算法关注非活动对象（标记-清除算法会找出所有的活动或者说可达的对象）。

部分标记-清除算法的核心在关注非活动对象，即只是进行限定范围内的搜索。对于引用计数直接置为0的对象，是引用计数法的经典情况，当然可以直接进行GC操作，进行回收。但是在引用计数-1之后，引用计数仍然大于0的，会认为疑似是循环引用。最常见的情况，如A引用B，B引用A，C引用B：

1
2
3
4
5
+----------+     +----------+     +----------+
|          | --> |          | --> |          |
| Object C |     | Object B |     | Object A |
|          |     |  ref:2   | <-- |  ref:1   |
+----------+     +----------+     +----------+

那么A引用计数为1，B引用计数为2，在回收C之后，发现B的引用计数仍然为1，可以怀疑B存在循环引用情况：

1
2
3
4
5
+----------+      +----------+     +----------+
|          | -X-> |          | --> |          |
| Object C |      | Object B |     | Object A |
|   GC ed  |      |  ref:1   | <-- |  ref:1   |
+----------+      +----------+     +----------+

首先要明确几个颜色的概念（即对象的状态）：

  1. 黑(BLACK):绝对不是垃圾的对象(对象产生时的初始颜色)
  2. 白(WHITE):绝对是垃圾的对象
  3. 灰(GRAY):搜索完毕的对象
  4. 阴影(HATCH):可能是循环垃圾的对象

对于上述问题，部分标记-清除算法采用的是在引用计数减少时，将疑似垃圾对象入队列，并记录对象颜色为阴影状态HATCH，如果已经是HATCH了，说明对象已经是在队列之中，不用重复入队列。

在需要进行GC操作时，从队列中扫描所有阴影（HATCH）或者黑色（BLACK）的对象，将这些对象的子对象引用计数-1，并且将当前对象颜色标记为灰色（GRAY），即已经访问过的对象，防止重复操作，对于对象的子对象，做同样的处理，因为子对象是从队列触达的，有可能并不在队列之中，也就是没有标记成HATCH，而是BLACK这样的正常状态，因为是一个递归调用，所以在最开始的描述中，会告知可以处理黑色的对象。

队列在此处的作用相当重要：队列保留了对象一旦从根切断访问路径之后仍能被GC程序访问到的唯一路径。

之后对队列中所有的灰色（GRAY）对象，对所有引用计数仍然大于0的对象，认定不存在循环引用问题，尝试涂为黑色（BLACK）并+1引用计数，对于黑色对象的不为黑色的子对象也做同样的操作；否则将对象标记为白色（WHITE），同样的，对于白色对象的子对象也做一样的操作。

最终，回收被标记为白色（WHITE）的所有对象。

看到这里，PHPer会不会突然想起，这不很类似PHP5.3之后的GC实现方式吗？从TIPI中可以读到，只不过是把HATCH用PURPLE这一颜色替代了。

来看如下例子：

1
2
3
4
5
+----------+      +----------+     +----------+
|          | ---> |  BLACK   | --> |  BLACK   |
|   ROOT   |      | Object B |     | Object A |
|          |      |  ref:2   | <-- |  ref:1   |
+----------+      +----------+     +----------+

对于对象B来说，如果执行 unset($b) 操作，此时引用计数会-1，但是对象B的引用计数目前仍然为1，符合我们对疑似循环引用的推断：

1
2
3
4
5
+----------+      +----------+     +----------+
|          | -X-> |  HATCH   | --> |  BLACK   |
|   ROOT   |      | Object B |     | Object A |
|          |      |  ref:1   | <-- |  ref:1   |
+----------+      +----------+     +----------+

如果按照常规的引用计数的处理，目前对象B引用计数仍然大于0，是不能被回收的。

对象B入HATCH队列，假设开始GC操作，首先执行灰色标记操作：

1
2
3
4
5
+----------+      +----------+     +----------+
|          | -X-> |   GRAY   | --> |  BLACK   |
|   ROOT   |      | Object B |     | Object A |
|          |      |  ref:1   | <-- |  ref:0   |
+----------+      +----------+     +----------+

根据算法，对于对象B的子对象对象A也需要进行标记操作：

1
2
3
4
5
+----------+      +----------+     +----------+
|          | -X-> |   GRAY   | --> |   GRAY   |
|   ROOT   |      | Object B |     | Object A |
|          |      |  ref:1   | <-- |  ref:0   |
+----------+      +----------+     +----------+

根据算法，对于对象A的子对象对象B也需要进行标记操作，但是因为对象B已经标记为灰色，所以无需进行标记操作，但是仍然需要进行子对象引用计数-1操作，下一步执行扫描灰色对象操作：

1
2
3
4
5
+----------+      +----------+     +----------+
|          | -X-> |   WHITE  | --> |   WHITE  |
|   ROOT   |      | Object B |     | Object A |
|          |      |  ref:0   | <-- |  ref:0   |
+----------+      +----------+     +----------+

不幸的是，对象B作为一个灰色对象并且引用计数已经为0，需要标记成白色，确认是一个垃圾对象。根据算法也要对子对象进行同样的操作，所以对象A也会标记成白色，因为当前没有存在黑色的对象，所以标记黑色操作不进行。

最后回收所有白色对象。

对于需要对子对象引用计数先-1，而不是对象本身-1，如果首先对对象本身-1，那么假设对象A当前引用计数为2，存在子对象B，子对象B没有引用A。现在从根对象中解除引用，A的引用计数变为1，在标记操作过程中会使得A对象引用计数边为0，而B对象引用计数也会变为0，但是事实上，B并没有引用A，不存在循环引用情况，但是这样的操作步骤却使得A误认为是垃圾，被清理。

来看一下PHP中的标记阶段 zobj_mark_grey() 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
static void zobj_mark_grey(struct _store_object *obj, zval *pz TSRMLS_DC)
{
	Bucket *p;
	zend_object_get_gc_t get_gc;

	if (GC_GET_COLOR(obj->buffered) != GC_GREY) {
		GC_BENCH_INC(zobj_marked_grey);
		GC_SET_COLOR(obj->buffered, GC_GREY);
		if (EXPECTED(EG(objects_store).object_buckets[Z_OBJ_HANDLE_P(pz)].valid &&
		             (get_gc = Z_OBJ_HANDLER_P(pz, get_gc)) != NULL)) {
			int i, n;
			zval **table;
			HashTable *props = get_gc(pz, &table, &n TSRMLS_CC);

			for (i = 0; i < n; i++) {
				if (table[i]) {
					pz = table[i];
					if (Z_TYPE_P(pz) != IS_ARRAY || Z_ARRVAL_P(pz) != &EG(symbol_table)) {
						pz->refcount__gc--;
					}
					zval_mark_grey(pz TSRMLS_CC);
				}
			}
			if (!props) {
				return;
			}
			p = props->pListHead;
			while (p != NULL) {
				pz = *(zval**)p->pData;
				if (Z_TYPE_P(pz) != IS_ARRAY || Z_ARRVAL_P(pz) != &EG(symbol_table)) {
					pz->refcount__gc--;
				}
				zval_mark_grey(pz TSRMLS_CC);
				p = p->pListNext;
			}
		}
	}
}

这里确实是对子对象先行操作引用计数的。

未完待续。