Python3-源码剖析(三)-GC垃圾回收

趁着五一难得有自己的时间,就来剖析一下 CPython 的自动垃圾回收机制,并尝试提出改进的思路。

引用计数

相信有过计算机基础的人,哪怕对垃圾回收不那么熟悉,也肯定知道引用计数这个玩意。引用计数诞生于上个世纪,其主要思想是通过给每个对象增加计数,当计数为0时,则肯定没人使用该对象,可以放心将其删除。

虽然这个方法看起来有点糙,但在实际项目中,它的优点在于可以更实时的释放内存,释放内存的时机更精确,这也是为什么有的项目会尝试给 Lua 增添一个引用计数的垃圾回收,避免内存上涨过快。

凡事都有利弊,它的缺点也很明显,无法处理循环引用。

以下用 Python 举一个非常普遍的例子。

1
2
3
4
5
6
7
8
9
10
11
12
class A:  
pass

class B:
pass

a = A()
b = B()
a.b = b
b.a = a
del a
del b

在上面中,我们手动删除了 ab ,理应进行释放,但由于 ab 互相构成了循环引用,导致其引用计数总是不为0,进而造成内存泄漏,而 CPython 对其解决方法也极其简单,就是将所有可能造成循环引用的对象,构成一个双向链表进行扫描,从 root object 出发进行扫描 - 清除,无法到达的对象就是可释放的对象,普通的对象直接采用引用计数去释放,简单快捷。

怎么去验证以上结论呢?我们可以用反证法,当 del adel b 后,再调用 gc.collect() 查看其是否能被回收到,如果能回收到,说明在此时引用计数已经失效。

1
2
3
4
5
6
7
8
# 设置 debug 标签,使得垃圾回收后的对象 存放至 gc.garbage 列表中
gc.set_debug(gc.DEBUG_SAVEALL)

# 回收第0代垃圾对象
gc.collect(0)

# 打印出回收的垃圾对象
print(gc.garbage)

可以看出引用计数确实失效了,因为通过 扫描-清除 回收能回收到这两个对象。

1
[<__main__.A object at 0x10adefc10>, <__main__.B object at 0x10adeff70>, {'b': <__main__.B object at 0x10adeff70>}, {'a': <__main__.A object at 0x10adefc10>}]

接下来,我们来到 CPython 源码中查看如何用引用计数管理一个对象。我们将以整数为例,先看看整数对象的对象模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 对象的基类,拥有双向链表和引用计数
typedef struct _object {
struct _object *_ob_next;
struct _object *_ob_prev;
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
} PyObject;

typedef struct {
PyObject ob_base;
Py_ssize_t ob_size;
} PyVarObject;

struct _longobject {
PyVarObject ob_base;
digit ob_digit[1];
};

可以看出每个对象都有一条双向链表,但是这里需要说明的是,此处的双向链表并非后面扫描 - 标记所使用的双向链表,此处的双向链表会将所有的对象都链接到 refchain 中,目前从代码中只能看出是拿来做调试用途的。

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
39
40
41
42
43
44
45
46
47
void
_Py_AddToAllObjects(PyObject *op, int force)
{
if (force || op->_ob_prev == NULL) {
op->_ob_next = refchain._ob_next;
op->_ob_prev = &refchain;
refchain._ob_next->_ob_prev = op;
refchain._ob_next = op;
}
}

void
_Py_NewReference(PyObject *op)
{
if (_Py_tracemalloc_config.tracing) {
_PyTraceMalloc_NewReference(op);
}
#ifdef Py_REF_DEBUG
_Py_RefTotal++;
#endif
Py_SET_REFCNT(op, 1);
#ifdef Py_TRACE_REFS
_Py_AddToAllObjects(op, 1);
#endif
}

static inline PyObject*
_PyObject_INIT(PyObject *op, PyTypeObject *typeobj)
{
Py_TYPE(op) = typeobj;
if (PyType_GetFlags(typeobj) & Py_TPFLAGS_HEAPTYPE) {
Py_INCREF(typeobj);
}
_Py_NewReference(op);
return op;
}

PyLongObject *
_PyLong_New(Py_ssize_t size)
{
PyLongObject *result;
...
result = PyObject_MALLOC(offsetof(PyLongObject, ob_digit) +
size*sizeof(digit));
...
return (PyLongObject*)PyObject_INIT_VAR(result, &PyLong_Type, size);
}

以上关于 CPython 中的引用计数部分,就讲解完了,整体非常简单。接下来就是看容器类对象(会造成循环引用的对象)如何进行垃圾回收了。

扫描-清除

垃圾回收领域一直有几大门派,最为突出的门派分别为 扫描-清除标记-整理 ,先讲什么是 标记-整理

假设我们将语言的内存池分为两块,其中一块不用,另一块一直拿来创建对象,当垃圾回收开启时,我们将所有可达对象(即可用对象)进行标记,然后将标记的对象重新在另一块内存池中进行创建,最后直接将原本那块内存池进行释放,这就将垃圾整理完成。

标记-整理 这种垃圾回收办法依赖于一个假设,那就是垃圾对象比正常的对象要多得多,这样整理起来由于是整个内存池一起销毁的,所以会快得多。

CPython 选择的是 扫描-清除,我们就不在其他地方进行展开了,着重来介绍 扫描-清除

假设我们从 root object 出发,如果可以扫描到的对象,即成为可达对象,可达对象则代表正在被使用不可清理。最终我们将得到一个不可达对象的列表,将其清理即可。

扫描-清除 由于扫描和清除是一次性完成的,会导致 Stop The World 时间特别长,因此产生了所谓的分代垃圾回收,这也就是 CPython 目前所使用的垃圾回收。

分代垃圾回收

分代垃圾回收基于一个假设,大部分对象存活的时间比较短,少部分对象存活的时间比较长,那么就可以优先对新生代进行垃圾回收,而对老年代的垃圾回收次数放缓,这就解决了 扫描-清除 的时间过长的问题。

接下来我们就来简单看看 分代垃圾回收的实现。我们以一个容器对象作为例子,就拿 list 好了。

以下为 list 的对象模型,由于本篇主题为垃圾回收,所以不关注其他成员。

1
2
3
4
5
typedef struct {
PyVarObject ob_base;
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;

结构也是非常简单,同样有引用计数与双向链表(在 PyVarObject 结构中),那么就会有疑惑了,这里的双向链表用于链接所有对象到 refchain ,那么我们的分代垃圾回收的扫描链表去哪了?

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/* GC information is stored BEFORE the object structure. */
typedef struct {
// Pointer to next object in the list.
// 0 means the object is not tracked
uintptr_t _gc_next;

// Pointer to previous object in the list.
// Lowest two bits are used for flags documented later.
uintptr_t _gc_prev;
} PyGC_Head;

void
_PyObject_GC_Link(PyObject *op)
{
PyGC_Head *g = AS_GC(op);
PyThreadState *tstate = _PyThreadState_GET();
GCState *gcstate = &tstate->interp->gc;
g->_gc_next = 0;
g->_gc_prev = 0;
gcstate->generations[0].count++; /* number of allocated GC objects */
if (gcstate->generations[0].count > gcstate->generations[0].threshold &&
gcstate->enabled &&
gcstate->generations[0].threshold &&
!gcstate->collecting &&
!_PyErr_Occurred(tstate))
{
gcstate->collecting = 1;
gc_collect_generations(tstate);
gcstate->collecting = 0;
}
}

PyObject *
_PyType_AllocNoTrack(PyTypeObject *type, Py_ssize_t nitems)
{
PyObject *obj;
const size_t size = _PyObject_VAR_SIZE(type, nitems+1);

// 计算真实内存大小
const size_t presize = _PyType_PreHeaderSize(type);
char *alloc = PyObject_Malloc(size + presize);
if (alloc == NULL) {
return PyErr_NoMemory();
}
obj = (PyObject *)(alloc + presize);
if (presize) {
((PyObject **)alloc)[0] = NULL;
((PyObject **)alloc)[1] = NULL;
_PyObject_GC_Link(obj);
}
memset(obj, '\0', size);

if (type->tp_itemsize == 0) {
_PyObject_Init(obj, type);
}
else {
_PyObject_InitVar((PyVarObject *)obj, type, nitems);
}
return obj;
}

// list的构造函数
PyObject *
PyType_GenericAlloc(PyTypeObject *type, Py_ssize_t nitems)
{
PyObject *obj = _PyType_AllocNoTrack(type, nitems);
if (obj == NULL) {
return NULL;
}

if (_PyType_IS_GC(type)) {
_PyObject_GC_TRACK(obj);
}
return obj;
}

可以看出,在创建这类需要扫描的对象时,会提前算好头部还需要加多少内存,在头部再加一个 PyGC_Head 作为分代回收的链表,然后调用 _PyObject_GC_Link 触发垃圾回收,可以看出当创建一个对象达到该代的阈值时,将会触发垃圾回收,最后才调用 _PyObject_GC_TRACK 将其链入 第0代 GC链表 中。

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
// Lowest bit of _gc_next is used for flags only in GC.
// But it is always 0 for normal code.
#define _PyGCHead_NEXT(g) ((PyGC_Head*)(g)->_gc_next)
#define _PyGCHead_SET_NEXT(g, p) _Py_RVALUE((g)->_gc_next = (uintptr_t)(p))

// Lowest two bits of _gc_prev is used for _PyGC_PREV_MASK_* flags.
#define _PyGCHead_PREV(g) ((PyGC_Head*)((g)->_gc_prev & _PyGC_PREV_MASK))
#define _PyGCHead_SET_PREV(g, p) do { \
assert(((uintptr_t)p & ~_PyGC_PREV_MASK) == 0); \
(g)->_gc_prev = ((g)->_gc_prev & ~_PyGC_PREV_MASK) \
| ((uintptr_t)(p)); \
} while (0)

static inline void _PyObject_GC_TRACK(
PyObject *op)
{
PyGC_Head *gc = _Py_AS_GC(op);

PyInterpreterState *interp = _PyInterpreterState_GET();
PyGC_Head *generation0 = interp->gc.generation0;
PyGC_Head *last = (PyGC_Head*)(generation0->_gc_prev);
_PyGCHead_SET_NEXT(last, gc);
_PyGCHead_SET_PREV(gc, last);
_PyGCHead_SET_NEXT(gc, generation0);
generation0->_gc_prev = (uintptr_t)gc;
}

从宏中可以看出,CPython 用了地址的最后两位去做一些事情,之所以可以这么做是因为内部实现了个小的内存分配器,里面的地址按4字节对齐,这意味着后两位一定为0,这也是一个常用技巧了,没什么好说的。

现在让我们关注最重要的 垃圾回收过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static Py_ssize_t
gc_collect_generations(PyThreadState *tstate)
{
GCState *gcstate = &tstate->interp->gc;
Py_ssize_t n = 0;
for (int i = NUM_GENERATIONS-1; i >= 0; i--) {
if (gcstate->generations[i].count > gcstate->generations[i].threshold) {
if (i == NUM_GENERATIONS - 1
&& gcstate->long_lived_pending < gcstate->long_lived_total / 4)
continue;
n = gc_collect_with_callback(tstate, i);
break;
}
}
return n;
}

从最老一代开始进行收集,目前 CPython 默认有3代,分别为 0,1,2代。为了避免多次进行 full gc ,这里设置了个条件,当清理最老一代的时候,必须要 非最老一代存活的对象(long_lived_pending) / 当前最老一代存活的对象(long_lived_total) 超过 25% 才进行全量回收,其实这主要是因为 扫描-清理 过程是一次完成的,所以要尽量避免 full gc

接着就正式进入垃圾回收主函数。

1
2
3
4
5
6
7
8
9
static Py_ssize_t
gc_collect_with_callback(PyThreadState *tstate, int generation)
{
...
Py_ssize_t result, collected, uncollectable;
result = gc_collect_main(tstate, generation, &collected, &uncollectable, 0);
...
return result;
}

在阅读之前,还要补充一个知识点,分代垃圾回收里面的三代回收是有阈值的,其中只有第0代也就是最年轻的一代的阈值指的是对象个数,剩下两代都是执行年轻代的次数。默认值为 (700, 10, 10) 这意味着想触发第0代垃圾回收需要创建出700个对象,而想触发第1代垃圾回收,需要第0代垃圾回收执行过10次,想要触发第2代垃圾回收则需要第1代垃圾回收执行过10次(同时还要满足上面的一个条件,这里就不重复了)。

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
static Py_ssize_t
gc_collect_main(PyThreadState *tstate, int generation,
Py_ssize_t *n_collected, Py_ssize_t *n_uncollectable,
int nofail)
{
int i;
Py_ssize_t m = 0; /* # objects collected */
Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head finalizers; /* objects with, & reachable from, __del__ */
PyGC_Head *gc;
_PyTime_t t1 = 0; /* initialize to prevent a compiler warning */
GCState *gcstate = &tstate->interp->gc;

// 将更老的一代的 count + 1 从而让之后能执行到后续的垃圾回收
if (generation+1 < NUM_GENERATIONS)
gcstate->generations[generation+1].count += 1;

// 当前代和比当前代更年轻的计数重置,因为我们会将[0, 当前代]全部处理完
for (i = 0; i <= generation; i++)
gcstate->generations[i].count = 0;

// 将更年轻的代归到当前代的链表上
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(gcstate, i), GEN_HEAD(gcstate, generation));
}

// young = [0, 当前代]
young = GEN_HEAD(gcstate, generation);
if (generation < NUM_GENERATIONS-1)
// 当当前为第1代则old为第2代,当当前为第0代则old为第1
old = GEN_HEAD(gcstate, generation+1);
else
// 说明当前为第2代,则old也为第2代
old = young;

// 核心, 将young中的对象的引用计数拷贝一份放到 _gc_prev.
// 因为如果真正去修改引用计数的话,会导致意外释放掉一些本不该释放的对象
// 但是拷贝一份出来做运算就没有这问题,此函数值得之后细说
deduce_unreachable(young, &unreachable);
// 找到可以停止追踪的tuples,减少垃圾回收工作量,这里不懂没关系,后面会举例细说
untrack_tuples(young);

// 将可达对象进行升级(升级到更老一代)
if (young != old) {
if (generation == NUM_GENERATIONS - 2) {
gcstate->long_lived_pending += gc_list_size(young);
}
gc_list_merge(young, old);
}
else {
// 同理,找到可以停止追踪的dict,只在full gc启用,原因后面说
untrack_dicts(young);
gcstate->long_lived_pending = 0;
gcstate->long_lived_total = gc_list_size(young);
}

// 处理带有析构函数的对象,__del__,类似于 Lua 的 __gc
gc_list_init(&finalizers);
move_legacy_finalizers(&unreachable, &finalizers);
move_legacy_finalizer_reachable(&finalizers);

/* Clear weakrefs and invoke callbacks as necessary. */
m += handle_weakrefs(&unreachable, old);

// 调用 tp_finalize 即 __del__
finalize_garbage(tstate, &unreachable);

// 处理复活的对象
PyGC_Head final_unreachable;
handle_resurrected_objects(&unreachable, &final_unreachable, old);

// 打破容器的引用计数
m += gc_list_size(&final_unreachable);
delete_garbage(tstate, gcstate, &final_unreachable, old);

// 将终结器对象的bug信息进行整理
handle_legacy_finalizers(tstate, gcstate, &finalizers, old);

// 最老一代还会清空缓存池
if (generation == NUM_GENERATIONS-1) {
clear_freelists(tstate->interp);
}
...
}

整体来看,除了代码量略大,其他的还是很简单的,接下来我们将解决上面几个遗留问题。

  1. 如何找到 root object
  2. untrack_tuples 是个啥?
  3. untrack_dicts 为什么只在 full gc 时调用?

先解释第二点,为了加快垃圾回收的迭代,当 tuple 容器没有内嵌容器时,会将其从垃圾回收跟踪中删除,只使用最基础的引用计数。证明这一点很简单。

1
2
3
4
a = (1, 2)  
print(gc.is_tracked(a)) # True
gc.collect()
print(gc.is_tracked(a)) # False

可以看出,对 tuple 取消追踪,是个惰性过程。接下来我们引申到 dict

1
2
3
4
5
6
a = {"a": 1}
print(gc.is_tracked(a)) # False
a["b"] = {}
print(gc.is_tracked(a)) # True
a.pop("b")
print(gc.is_tracked(a)) # True

可以得出,当 dict 没有复杂的对象时,则不会对其追踪,那么我们是否可以将同样的思路引用于 list 呢?

接下来我们回到问题1,如何找到 root object ?如果读者对 Lua 了解的话就知道,Lua 的对象都可以从 registry 这个全局表中追踪到,但在 Python 的世界中却是不可行的,之所以会产生这样的问题,主要还是因为 Python 扩展模块(extension modules) 工作方式导致用于无法确定根集,这就使得复杂度一下就上来了。

CPython 的解决方法也很简单,结合引用计数和扫描清除两种办法去解决。拷贝一份引用计数(如果在原本的引用计数上操作太危险了,不小心变成0,就触发了引用计数回收了),然后在其基础上进行遍历,每次将引用计数 -1,这样就得到了相对引用计数,相对引用计数为0,则有可能是不可达对象,先猜想它是,后续再遍历可达对象,如果从可达对象可以找到相对引用计数为0的对象,那么它就是可达对象,需要将其恢复。

这块虽然有点绕,但仔细品味一下还是非常简单的。

接下来我们来讨论第三个问题,为什么 untrack_dicts 只在 第三代垃圾回收时触发?
这主要是因为 dict 插入一个对象时,会判断这个对象是不是容器,是容器就会将其追踪,但是每次都会在 untrack_dicts 去遍历检查是否可以取消追踪,这就很蠢了,有兴趣的可以阅读 Issue #14775

其实还有些内容想讲,随便来个话题,在 Python 2 时代,当两个对象循环引用又同时有 __del__ 时,垃圾回收会不回收这两个对象这类问题,但我不想在这里继续展开了,太累了,有兴趣可以阅读 PEP-442 进行学习。

想法

渐进分代?

CPython 的GC是 Stop The World 的,哪怕它已经很尽力用分代的方式去减少GC的损耗。是否可以将其改进为渐进的方式?我目前的想法是在容器操作时,进行 Barrier 操作,维护一个中间态,使得前面的扫描过程是可渐进的,最后处理垃圾的时候再停下来一次性处理完,减少停止的时间。但这个思路貌似不行,原因是根集是不确定的,坑爹的语言设计。

减少跟踪对象?

是否可以对其它常用容器也做 untrack 操作,当容器没有嵌套容器时,取消 track 操作,减少GC遍历损耗?这个思路需要小心避免犯上面 untrack_dicts 的错误。

甚至我们扩展 gcmodule 的接口,使得对一些常驻内存的对象进行标记,使其不要被跟踪?

尽可能少用 del

这点就不说啥了,Lua 里也最好别用 __gc

最后的最后,感谢 CPython 这份非常漂亮的代码设计,让我在这个五一假期,受益良多,下一步可能会回到 Lua 5.2 中,阅读它 “失败” 的分代GC作品,我认为学习失败的经验比成功的经验要重要得多。