【CPython3.6源码分析】Python 垃圾回收

前言

垃圾回收一般分为两个阶段:

  • 垃圾检测,从所有已分配的内存中识别出可以回收和不可以回收的内存
  • 垃圾回收,是系统从掌握在检测阶段标识出的可回收内存

Python 基于古老的引用计数,必须在每次分配和释放内存时,加入 计数 的动作。
引用计数,其特点和缺点都很明显

  • 优点:实时性,发生在整个程序运行期间
  • 缺点:循环引用

Python 为了解决循环引用,引入了标记清除和分代收集两种技术。

标记清除

标记清除(Mark——Sweep)同样遵循垃圾回收的两个阶段,其工作过程如下:

  1. 寻找根对象(root object)的集合,即全局引用和函数栈中的引用。这些引用都是不可删除的。
  2. 从根对象出发,沿着集合中的对象的每一个引用,都是可到达的(reachable),这些对象都是不可删除的
  3. 检测完成后,能区分出可删除和不可删除的。

整体上,就是遍历一张有向图。节点为对象,边为对象间的引用。利用BFS/DFS,遍历所有出度,利用三色标记,区分出可到达,最终找到孤立的节点,即可删除对象。

标记清除,主要是为了打破循环引用存在,而针对 PyLongObject、PyUnicodeObject,等对象是不可能出现循环引用的。因此,只需要检查 container 对象。所以 Python 将所有 container 对象组织成一个双向链表。

1
2
3
4
5
6
7
8
9
PyObject *  PyList_New(Py_ssize_t size)
{
PyListObject *op;
...
op = PyObject_GC_New(PyListObject, &PyList_Type);
...
_PyObject_GC_TRACK(op);
return (PyObject *) op;
}

查看容器对象 PyListObject,可以发现创建对象是通过PyObject_GC_New。创建完对象后,通过宏_PyObject_GC_TRACK,把对象放入 containner 链表中。

PyObject_GC_New

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
// objimpl.h.252
typedef union _gc_head {
struct {
union _gc_head *gc_next;
union _gc_head *gc_prev;
Py_ssize_t gc_refs;
} gc;
double dummy; /* force worst-case alignment */
} PyGC_Head;

static PyObject * _PyObject_GC_Alloc(int use_calloc, size_t basicsize)
{
PyObject *op;
PyGC_Head *g;

// 分配内存
size_t size = sizeof(PyGC_Head) + basicsize;
if (use_calloc)
g = (PyGC_Head *)PyObject_Calloc(1, size);
else
g = (PyGC_Head *)PyObject_Malloc(size);

// 初始化 gc.gc_refs
g->gc.gc_refs = 0;
_PyGCHead_SET_REFS(g, GC_UNTRACKED);

// 分代收集
generations[0].count++; /* number of allocated GC objects */
if (generations[0].count > generations[0].threshold &&
enabled &&
generations[0].threshold &&
!collecting &&
!PyErr_Occurred()) {
collecting = 1;
collect_generations();
collecting = 0;
}
// 根据 g 地址,找到 ob 地址
// #define AS_GC(o) ((PyGC_Head *)(o)-1)
// #define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))
op = FROM_GC(g);
return op;
}

可以发现,在创建对象时,同时申请了两块内存,PyGC_Head + PyListObject。最终还是调用的上一节上到的 PyObject_Malloc。在 object 和 gc head 之间,通过宏进行地址转换。注意其中的SET_REFS(g, GC_UNTRACKED);

_PyObject_GC_TRACK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define _PyObject_GC_TRACK(o) do { \
PyGC_Head *g = AS_GC(o); \
if (_PyGCHead_REFS(g) != _PyGC_REFS_UNTRACKED) \
Py_FatalError("GC object already tracked"); \
_PyGCHead_SET_REFS(g, _PyGC_REFS_REACHABLE); \
g->gc.gc_next = _PyGC_generation0; \
g->gc.gc_prev = _PyGC_generation0->gc.gc_prev; \
g->gc.gc_prev->gc.gc_next = g; \
_PyGC_generation0->gc.gc_prev = g; \
} while (0);

#define _PyObject_GC_UNTRACK(o) do { \
... \
_PyGCHead_SET_REFS(g, _PyGC_REFS_UNTRACKED);

如上,通过两个指针,构成了双向链表。当创建 List 对象后,就把其挂载到链表上。并且可以发现_PyGC_generation0始终指向链表头。注意其中的SET_REFS()

分代收集

研究表明:无论任何语言开发的任何程序,都存在一定比例(80%-98%)的内存块生存期比较短,而另一些生存期特别长。

分代搜集,以空间换时间,是支撑 JAVA 的关键技术。其总体思想是:
将系统中的所有内存块根据其存活时间划分为不同的集合,每个集合称为一个代,垃圾收集的频率与代的存活时间成反比。

  1. 若内存块 M 经过3次垃圾收集后依然存活,就将M划分到集合A中
  2. 新创建的对象,都划分到集合B中
  3. 一段时间后,B 中也有一批存活的对象,将其划分到A中
  4. 集合 A 因收集频率低,会存在一些已经被销毁的对象尸体(空间换时间)

在 Python 中,总共有三个代。
上面的 GC_TRACK 中,存在的变量 _PyGC_generation0 即是一个内部指针,指向 第0代 的内存块集合。

generations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct gc_generation {
PyGC_Head head;
int threshold;
int count;
};

// 一个代,就是一个链表
#define NUM_GENERATIONS 3
#define GEN_HEAD(n) (&generations[n].head)

/* linked lists of container objects */
static struct gc_generation generations[NUM_GENERATIONS] = {
/* PyGC_Head, threshold, count */
{{{GEN_HEAD(0), GEN_HEAD(0), 0}}, 700, 0},
{{{GEN_HEAD(1), GEN_HEAD(1), 0}}, 10, 0},
{{{GEN_HEAD(2), GEN_HEAD(2), 0}}, 10, 0},
};

PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);

如上,Python 内部维护这一个 3个对象的数组generations。通过这个数组,控制着三条可收集对象链表,这就是 Python 分代收集的三个代。
上面的 GC_TRACK 中,存在的变量 _PyGC_generation0 即是一个内部指针,指向 第0代 的内存块集合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static PyObject * _PyObject_GC_Alloc(int use_calloc, size_t basicsize)
{
...
/* 增加 0 代 count */
generations[0].count++;
// 判断是否触发 回收条件
if (generations[0].count > generations[0].threshold &&
enabled &&
generations[0].threshold &&
!collecting &&
!PyErr_Occurred()) {
collecting = 1;
collect_generations();
collecting = 0;
}
}

PyObject_GC_Alloc,我们能看见,每次创建完对象会先进程收集检测。然后才再宏中加入到_PyGC_generation0链上。一旦满足判断条件,就会调用collect_generations开始回收。

collect_generations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static Py_ssize_t collect_generations(void)
{
int i;
Py_ssize_t n = 0;

for (i = NUM_GENERATIONS-1; i >= 0; i--) {
if (generations[i].count > generations[i].threshold) {
if (i == NUM_GENERATIONS - 1 // 最大代,直接回收
&& long_lived_pending < long_lived_total / 4)
// 默认 0, 0
continue;
// 执行回收
n = collect_with_callback(i);
break;
}
}
return n;
}

从上面的代码,能看出回收策略:

  • 回收操作是由第一代触发
  • 通过两个参数,long_lived_*,决定第三代是否执行回收
  • 回收从 old->new,只要执行一次回收,就会 break,不在执行其他代

collect

1
2
3
4
5
6
7
8
9
10
11
12
/* Invoke progress callbacks to notify clients that garbage collection
* is starting or stopping
*/
static Py_ssize_t
collect_with_callback(int generation)
{
Py_ssize_t result, collected, uncollectable;
invoke_gc_callback("start", generation, 0, 0);
result = collect(generation, &collected, &uncollectable, 0);
invoke_gc_callback("stop", generation, collected, uncollectable);
return result;
}

显然,大头都在 collect源码中。

collect 源码

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
88
89
90
91
92
static Py_ssize_t
collect(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 */

struct gc_generation_stats *stats = &generation_stats[generation];

/* 1. 老代.count+1,当代+年轻代.count=0 */
if (generation+1 < NUM_GENERATIONS)
generations[generation+1].count += 1;
for (i = 0; i <= generation; i++)
generations[i].count = 0;

/* 2. 将年轻代链表,合并到当前代 */
for (i = 0; i < generation; i++) {
/* gc_list_merge(PyGC_Head *from, PyGC_Head *to)
append list `from` onto list `to`;
`from` becomes an empty list
*/
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
}

/* handy references */
young = GEN_HEAD(generation);
if (generation < NUM_GENERATIONS-1)
old = GEN_HEAD(generation+1);
else
old = young;

// 3. 通过下面两步,在链表上进行打破循环的的模拟,寻找 root object
// 3.1. Set all gc_refs = ob_refcnt.
update_refs(young);
// 3.2. 从 gc_refs 中减去内部引用。gc_refs>0,表示 reachable
subtract_refs(young);

/* 4.Move the unreachable objects from young to unreachable. */
gc_list_init(&unreachable);
move_unreachable(young, &unreachable);

// 5.如果可能,将当代中的 reachable 合并到更老代中
if (young != old) {
if (generation == NUM_GENERATIONS - 2) {
long_lived_pending += gc_list_size(young);
}
gc_list_merge(young, old);
}
else {
/* We only untrack dicts in full collections, to avoid quadratic
dict build-up. See issue #14775. */
untrack_dicts(young);
long_lived_pending = 0;
long_lived_total = gc_list_size(young);
}

/* 6.收集含有 tp_finalize(__del__) 的对象,放入 finalizers:PEP-442 */
gc_list_init(&finalizers);
move_legacy_finalizers(&unreachable, &finalizers);
/* 被 finalizers 引用的对象,也不能直接删除,也放入 finalizers */
move_legacy_finalizer_reachable(&finalizers);

/* 7. 处理弱引用,尝试调用 callback 函数 */
m += handle_weakrefs(&unreachable, old);

/* 8. 尝试调用 tp_finalize 方法,完成回收前的 用户定义工作 */
finalize_garbage(&unreachable);

if (check_garbage(&unreachable)) {
revive_garbage(&unreachable);
gc_list_merge(&unreachable, old);
}
else {
/* 9. 尝试调用 tp_clear 方法,打破循环引用 */
delete_garbage(&unreachable, old);
}

/* 10.将含有 tp_finalize(__del__) 的对象,放入 old 代 */
handle_legacy_finalizers(&finalizers, old);

/* 11.释放所有的 free list */
if (generation == NUM_GENERATIONS-1) {
clear_freelists();
}
}

collect 简略

大致 collect 过程:

  1. 老代.count+1,当代+年轻代.count=0
  2. 将 年轻代,合并到当前代中
  3. 在当前代链表上,寻找 root object
  4. 遍历当前代,生成 unreachable 链表
  5. 将当代 reachable 合并到更老的 代中
  6. 遍历 unreachable 链表,收集含有 del的对象,以及这些对象所引用的对象,放入 finalizers
  7. 处理弱引用 weakref,尝试调用回调
  8. 尝试调用 tp_finalize 方法,完成回收前的 用户定义工作
  9. 尝试调用 tp_clear 方法,打破循环引用
  10. 将含有 tp_finalize(del) 的对象,放入 old 代
  11. 释放所有的 free list。

小结

Python 垃圾回收最主要的方式是通过对象的引用计数实现,只要 ref 降为0,就触发操作。为了避免频繁的操作带来性能问题,Python 中大量使用内存池计数。从系统层面的 arena->pool->block,到对象层面的各种对象池共享机制。

为了解决循环引用,Python 又引入了标记清除和分代收集两种技术。将可能出现循环引用的对象,通通关联到 generations 上。用三个元素,来表示三个不同的代。在每次创建对象时,根据 分代数量,判断是否需要进行分代回收。