源码分析CPython中的垃圾回收机制

一、背景

之前有幸拜读过《Python源码解析》专栏，学习了CPython的内存管理及GC，对CPython 垃圾回收相关算法有了一定了解。现在尝试去阅读CPython 的GC模块的底层源码，去学习下各个算法的原理和实现逻辑。本文旨在探究原理而仅非GC的概念。

二、CPython中三种垃圾回收机制算法

1.引用计数

2.标记-清除

3.分代回收

注：引用计数是实时清理的，标记-清除和分代回收是结合使用的

三、引用计数

先来谈谈引用计数，引用计数是CPython中 GC的主要算法。众所周知，Python中任何一个对象都是基于PyObject实现的，PyObject中包含引用计数ob_refcnt字段，记录该对象被引用的个数。影响该字段的因素主要有以下四个：

  • 构造一个新的对象时, 例如a = '2'
  • 目标对象作为函数的参数传入到函数体中, 例如 def main(a):
  • 对象之间相互引用, 例如 b = a
  • 容器对象的操作, 例如b.append(a)

当某对象ob_refcnt的值到达0时，该对象就会被立即回收，并释放他们的占据的资源。

正常情况下，基本所有的对象，他们的ob_refcnt的值最终都可以变为0，但是在编码中，由于编码不规范，存在循环引用带来的内存泄漏问题，循环引用会导致多个对象的ob_refcnt的值最终恒为1，而如果仅依赖引用计数算法的话，CPython会认为这些ob_refcnt 为1的对象还不需要清除，但实际这些对象本应被清除，这样就会引发内存泄露。看如下例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
class TestList(list):
    def __del__(self):
        print(self)


a = TestList([1, 2, 3])
b = TestList([2, 3, 4])

a.append(b)
b.append(a)
del a
del b
print('已清除')

上述为简易的循环引用的例子，在执行del a, del b时会去调用__del__内置方法，执行的结果如下：

1
2
3
已清除
[1, 2, 3, [2, 3, 4, [...]]]
[2, 3, 4, [1, 2, 3, [...]]]

我们可以看到真正实行的时机与预想的顺序不太一样，此时由CPython内部检测到存在循环引用，进而CPython会在程序执行完毕后，采用标记-清除算法回收垃圾。如果对上述代码使用手动gc呢？再来看下结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import gc
class TestList(list):
    def __del__(self):
        print(self)


a = TestList([1, 2, 3])
b = TestList([2, 3, 4])

a.append(b)
b.append(a)
del a
del b
gc.collect()
print('已清除')

结果：

1
2
3
[1, 2, 3, [2, 3, 4, [...]]]
[2, 3, 4, [1, 2, 3, [...]]]
已清除

此时，由于我们在del后手动执行了一次gc，会触发标记-清除算法，a和b的资源将被提前回收，最后打印”已清除”, 这样程序实际执行的顺序和预期的顺序就完全符合了。

所以，当程序内存在变量循环引用的情况下，CPython会自动使用标记-清除算法来解决引用计数算法下无法回收的节点对象。那么CPython是如何标记出这些不可达节点并回收他们的呢？

四、标记-清除及跟踪的对象

标记-清除是CPython解决引用计数无法处理 循环引用 的问题，在读CPython源码前，因为做了一段的前端的模块，所以特地去了解了下V8的Javascript的GC算法。简单的说，Javascript中的标记-清除算法是遍历堆中所有的节点对象，标记存活的对象，在随后的清除阶段，只清除没有被标记的对象。

而在CPython中，标记-清除算法只针对满足条件的容器对象，因为这些容器对象是通过_PyObject_GC_Alloc 创建的，受到GC的跟踪。同时GC会忽略不可变对象，如int, bool, str, 以及由不可变对象组成的tuple等。在Include/internal/pycore_gc.h源码中有这样一段注释，告诉我们什么样的对象会被GC跟踪，被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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
   NOTE: about untracking of mutable objects.

   Certain types of container cannot participate in a reference cycle, and
   so do not need to be tracked by the garbage collector. Untracking these
   objects reduces the cost of garbage collections. However, determining
   which objects may be untracked is not free, and the costs must be
   weighed against the benefits for garbage collection.

   There are two possible strategies for when to untrack a container:

   i) When the container is created.
   ii) When the container is examined by the garbage collector.

   Tuples containing only immutable objects (integers, strings etc, and
   recursively, tuples of immutable objects) do not need to be tracked.
   The interpreter creates a large number of tuples, many of which will
   not survive until garbage collection. It is therefore not worthwhile
   to untrack eligible tuples at creation time.

   Instead, all tuples except the empty tuple are tracked when created.
   During garbage collection it is determined whether any surviving tuples
   can be untracked. A tuple can be untracked if all of its contents are
   already not tracked. Tuples are examined for untracking in all garbage
   collection cycles. It may take more than one cycle to untrack a tuple.

   Dictionaries containing only immutable objects also do not need to be
   tracked. Dictionaries are untracked when created. If a tracked item is
   inserted into a dictionary (either as a key or value), the dictionary
   becomes tracked. During a full garbage collection (all generations),
   the collector will untrack any dictionaries whose contents are not
   tracked.

   The module provides the python function is_tracked(obj), which returns
   the CURRENT tracking status of the object. Subsequent garbage
   collections may change the tracking status of the object.

   Untracking of certain containers was introduced in issue #4688, and
   the algorithm was refined in response to issue #14775.
*/

从上述注释中简要提取几点：

1.取消跟踪某一对象遵循两条策略：

  • 当容器对象创建时，无需跟踪
  • 当进行垃圾回收时，会去评估容器对象是否需要跟踪。

2.对于元祖对象来说，在创建时空元祖不用跟踪，在进行垃圾回收时，如果元祖内部的对象都取消跟踪，则元祖也取消跟踪。

3.对于字典对象来说，字典中的对象全部是不可变对象时，取消跟踪。同样在进行垃圾回收时，如果向字典中增加一个追踪的对象，那么这个字典变为可追踪的，反之当字典中都是不可追踪的对象，该字典变为不可追踪。

4.在进行垃圾回收时，容器对象的跟踪状态可能因内部对象的跟踪状态发生改变而改变。

同时CPython会维护两个容器链表，分别为包含所有待scan的结点的链表和只含unreachable结点的链表。每个结点额外增加gc_ref字段,其值初始化为每个结点对象的ob_refcnt。CPython并不像V8会去标记存活的对象，而是首先假设所收集的对象都是可达的，在遍历链表过程中，使用不可达链表记录并标识所有不可达的对象。

五、GC源码阅读

上述简要的介绍了下引用计数和标记-清除的概念，当然还有分代回收，不过值得注意的是，标记-清除算法和分代回收是结合作用于GC的。GC实现的源码位于/Modules/gcmodule.c， GC涉及的结构体定义源码位于/Include/internal/pycore_gc.h。

由于每一代触发GC时，实际是也执行了标记-清除算法，因此先来看分代的结构体定义，再来看标记-清除算法的实现原理，最后再来看分代回收算法的实现原理。

1.分代的结构体定义

先来看下分代的结构，在CPython中，默认分为三代#define NUM_GENERATIONS 3，分别记为新生代，中生代，老生代, 对应generations数组下表的0, 1, 2。分代回收遵循一种规则，即新生代中的结点对象大约占总的80%~90%，存在的时间也最短，也最容易回收，换句话说，对象存活时间越长，越能够常驻内存，那么越不太可能成为垃圾，那么应该越少去收集。这样一来，在每一代的回收中会执行标记-清除算法，而越到老生代，那么在执行Mark-Sweep算法时所需要遍历的跟踪结点对象的个数就会越少，其中体现了用空间换时间的思想。

每一代的结构体如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;

struct gc_generation {
    PyGC_Head head;  
    int threshold; /* collection threshold */
    int count; /* count of allocations or collections of younger
                  generations */
};

说明：

(1).head: 双向链表, 表示可收集对象的链表头部，用于维护对应代中的对象结点。

(2).threadshold: 表示当前代所容纳的结点阈值，当count > threadhold时，触发一次GC。

(3).count: 表示当前代的结点计数器。

GC运行时的结构体如下：

1
2
3
4
5
6
struct _gc_runtime_state {
    ...
    // 默认三代, 新生代, 中生代, 老生代
    struct gc_generation generations[NUM_GENERATIONS];
    ...
}

每代状态的初始化函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void
_PyGC_InitState(GCState *gcstate)
{
    gcstate->enabled = 1; /* automatic collection enabled? */
#define _GEN_HEAD(n) GEN_HEAD(gcstate, n)
	// 默认分三代
    struct gc_generation generations[NUM_GENERATIONS] = {
        /* PyGC_Head,                                    threshold,    count */
        {{(uintptr_t)_GEN_HEAD(0), (uintptr_t)_GEN_HEAD(0)},   700,        0},
        {{(uintptr_t)_GEN_HEAD(1), (uintptr_t)_GEN_HEAD(1)},   10,         0},
        {{(uintptr_t)_GEN_HEAD(2), (uintptr_t)_GEN_HEAD(2)},   10,         0},
    };
    for (int i = 0; i < NUM_GENERATIONS; i++) {
        gcstate->generations[i] = generations[i];
    };
    gcstate->generation0 = GEN_HEAD(gcstate, 0);
    struct gc_generation permanent_generation = {
          {(uintptr_t)&gcstate->permanent_generation.head,
           (uintptr_t)&gcstate->permanent_generation.head}, 0, 0
    };
    gcstate->permanent_generation = permanent_generation;
}

说明:

(1).默认分为三代，分为新生代，中生代，老生代，对应的阈值分别为700, 10, 10, 新生代的阈值相比于中生代和老生代更大，因为所有新创建的被GC跟踪的对象都会使得新生代的count++, 且新生代中的对象存活时间不会太长，执行GC的次数相比要更频繁，所以为了减少新生代执行GC的频率，提高其对应的threshold。

(2).每代的默认count设置为0。

2.标记-清除算法原理

Mark-Sweep算法的执行原理框架位于/Modules/gcmodule.c中的deduce_unreachable函数。

1
2
3
4
5
6
7
8
9
10
11
12
static inline void
deduce_unreachable(PyGC_Head *base, PyGC_Head *unreachable) {
    validate_list(base, collecting_clear_unreachable_clear);
 
    update_refs(base);  // gc_prev is used for gc_refs
    subtract_refs(base);

    gc_list_init(unreachable);
    move_unreachable(base, unreachable);  // gc_prev is pointer again
    validate_list(base, collecting_clear_unreachable_clear);
    validate_list(unreachable, collecting_set_unreachable_set);
}

遍历可收集的链表, 标识出不可达节点和推断出不可达链表的步骤主要有以下三步：

(1).首先调用遍历一遍可收集链表, 将每个结点的真实ob_refcnt引用计数值赋值到_gc_prev字段中，而不是开辟一个新的字段存储(网上很多资料都说是gc_refs字段，在我阅读的这个Python10版本并没有所谓的gc_refs字段, 只是概念上叫做gc_refs),这里_gc_prev字段既做结点(含有标识flag)又做引用计数的承载体。

(2).第二遍遍历每个结点对象，将他们的_gc_prev字段值减一, 这样做是为了 解内部引用,内部引用是指某结点被链表内的其他结点所引用。在遍历完成后,所有可达对象(_gc_prev值为正数)一定是存在外部引用,而那些不可达对象的_gc_prev值一定为0。这样一来，初步筛选并标记出不可达对象(此时并不移入不可达链表)

(3).此时虽然所有结点概念上被分为两个链表（可达和不可达)，但是他们之间的引用关系(指针)并未真正解除，意思仍可能存在可达链表中的结点指向不可达链表中某结点的现象, 而这些被可达结点所引用的不可达结点也是不能被回收的(这里可以仔细思考下，可以将引用关系理解为需求，就好理解了)。因此接下来所要做的就是将被可达结点所引用的不可达结点的gc_refs重设置为1，标识为可达，而将真正不可达对象设置标识为NEXT_MASK_UNREACHABLE，并将他们移动到不可达链表中。

(4).最终，所有对象都经过scan后，所有位于不可达链表的结点才会被GC真正回收。

源码分析具体算法步骤：

第一步：在开始收集结点时**, CPython首先会遍历收集的链表中所有结点，拷贝他们的ob_refcnt到_gc_prev(gc_refs),此时_gc_prev用于表示gc_refs。对应源码如下：

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
// /Modules/gcmodule.c
static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = GC_NEXT(containers);
    // 循环遍历双向链表
    for (; gc != containers; gc = GC_NEXT(gc)) {
        gc_reset_refs(gc, Py_REFCNT(FROM_GC(gc)));
        _PyObject_ASSERT(FROM_GC(gc), gc_get_refs(gc) != 0);
    }
}

static inline void
gc_reset_refs(PyGC_Head *g, Py_ssize_t refs)
{
    g->_gc_prev = (g->_gc_prev & _PyGC_PREV_MASK_FINALIZED)
        | PREV_MASK_COLLECTING
        | ((uintptr_t)(refs) << _PyGC_PREV_SHIFT);
}

// /Include/object.h

#define _PyVarObject_CAST_CONST(op) ((const PyVarObject*)(op))

static inline Py_ssize_t _Py_REFCNT(const PyObject *ob) {
    return ob->ob_refcnt;
}
#define Py_REFCNT(ob) _Py_REFCNT(_PyObject_CAST_CONST(ob))

第二步：遍历链表，将每个结点的gc_prev减一。

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
static void
subtract_refs(PyGC_Head *containers)
{
    traverseproc traverse;
    PyGC_Head *gc = GC_NEXT(containers);
    for (; gc != containers; gc = GC_NEXT(gc)) {
        PyObject *op = FROM_GC(gc);
        traverse = Py_TYPE(op)->tp_traverse;
        (void) traverse(op,
                        (visitproc)visit_decref,
                        op);
    }
}
static int
visit_decref(PyObject *op, void *parent)
{
    _PyObject_ASSERT(_PyObject_CAST(parent), !_PyObject_IsFreed(op));

    if (_PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        /* We're only interested in gc_refs for objects in the
         * generation being collected, which can be recognized
         * because only they have positive gc_refs.
         */
        if (gc_is_collecting(gc)) {
            // 将该对象结点的引用计数减一
            gc_decref(gc);
        }
    }
    return 0;
}
static inline void
gc_decref(PyGC_Head *g)
{
    _PyObject_ASSERT_WITH_MSG(FROM_GC(g),
                              gc_get_refs(g) > 0,
                              "refcount is too small");
    g->_gc_prev -= 1 << _PyGC_PREV_SHIFT;
}

第三步：使用gc_list_init(unreachable);初始化一个空的不可达链表。

第四步：调用该move_unreachable，该函数是找出真正不可达的结点。主要包含两个作用：

(1).若结点对象的gc_refs大于0，调用visit_reachable函数，遍历待收集链表中从该结点起始的引用链，若位于该引用链上结点的gc_refs为0，将其gc_refs值重设置为1，或者在此之前已经被标记为NEXT_MASK_UNREACHABLE且移入不可达链表的结点对象，则将其gc_refs值重设置为1并且移入待收集链表，即表示被可达对象引用的对象也是可达的，同时以便后序再次访问该结点时，因该结点的gc_refs已经是1了，而不会将其归为不可达结点。

(2).若结点对象的gc_refs等于0，表明该结点确实不可达，则将其移入不可达链表，并给予NEXT_MASK_UNREACHABLE不可达的标识(该结点后序可能会变为可达结点)。

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
static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
    // previous elem in the young list, used for restore gc_prev.
    PyGC_Head *prev = young;
    PyGC_Head *gc = GC_NEXT(young);

    while (gc != young) {
        // 遍历gc_refs大于0的结点对象及其引用的对象, 将其引用的对象中gc_refs为0的对象的gc_refs重设为1, 或者将其引用的对象中标识为NEXT_MASK_UNREACHABLE的结点对象的gc_refs重设为1，并将其移入待收集链表。
        if (gc_get_refs(gc)) {
            PyObject *op = FROM_GC(gc);
            traverseproc traverse = Py_TYPE(op)->tp_traverse;
            _PyObject_ASSERT_WITH_MSG(op, gc_get_refs(gc) > 0,
                                      "refcount is too small");
            (void) traverse(op,
                    (visitproc)visit_reachable,
                    (void *)young);
            // relink gc_prev to prev element.
            _PyGCHead_SET_PREV(gc, prev);
            gc_clear_collecting(gc);
            prev = gc;
        }
        // 对真正gc_refs为0的对象，将其移入unreachable不可达链表,并标识为NEXT_MASK_UNREACHABLE，以便在未来遍历到该对象结点时，发现器是被可达对象引用的，还需将其移回待收集链表，去除其标识。
        else {
            prev->_gc_next = gc->_gc_next;

            PyGC_Head *last = GC_PREV(unreachable);
            last->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)gc);
            _PyGCHead_SET_PREV(gc, last);
            gc->_gc_next = (NEXT_MASK_UNREACHABLE | (uintptr_t)unreachable);
            unreachable->_gc_prev = (uintptr_t)gc;
        }
        gc = (PyGC_Head*)prev->_gc_next;
    }
    // young->_gc_prev must be last element remained in the list.
    young->_gc_prev = (uintptr_t)prev;
    // don't let the pollution of the list head's next pointer leak
    unreachable->_gc_next &= ~NEXT_MASK_UNREACHABLE;
}


/* A traversal callback for move_unreachable. */
// 重设被可达对象引用的对象的gc_refs为1
static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{	
    // 忽略gc_refs值<=0的结点对象
    if (!_PyObject_IS_GC(op)) {
        return 0;
    }

    PyGC_Head *gc = AS_GC(op);
    const Py_ssize_t gc_refs = gc_get_refs(gc);

    if (! gc_is_collecting(gc)) {
        return 0;
    }
    assert(gc->_gc_next != 0);

    if (gc->_gc_next & NEXT_MASK_UNREACHABLE) {
        PyGC_Head *prev = GC_PREV(gc);
        PyGC_Head *next = (PyGC_Head*)(gc->_gc_next & ~NEXT_MASK_UNREACHABLE);
        _PyObject_ASSERT(FROM_GC(prev),
                         prev->_gc_next & NEXT_MASK_UNREACHABLE);
        _PyObject_ASSERT(FROM_GC(next),
                         next->_gc_next & NEXT_MASK_UNREACHABLE);
        prev->_gc_next = gc->_gc_next;  // copy NEXT_MASK_UNREACHABLE
        _PyGCHead_SET_PREV(next, prev);

        gc_list_append(gc, reachable);
        gc_set_refs(gc, 1);
    }
    else if (gc_refs == 0) {
        // 重设被可达对象引用的对象的gc_refs为1
        gc_set_refs(gc, 1);
    }
    else {
        _PyObject_ASSERT_WITH_MSG(op, gc_refs > 0, "refcount is too small");
    }
    return 0;
}

第五步：在分代回收算法基础上，调用delete_garbage，清理不可达链表中的结点对象。

3.分代算法原理

最后，我们来看下分代回收算法，事实上，在执行分代回收算法时，会基于不同的分代策略执行标记-清除算法将可收集链表拆分成可达和不可达链表，然后调用delete_garbage回收不可达链表中的结点，最终会调用该结点对象的tp->clear函数指针指向的函数，清理结点对象。分代算法核心源码同样位于gcmodules.c中。

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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
/*
    回收的核心算法
*/
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; /* 待收集的对象个数 */
    Py_ssize_t n = 0; /* 不能被收集的不可达对象个数 */
    PyGC_Head *young; /* 正在处理的这一代 */
    PyGC_Head *old; /* young的下一代 */
    PyGC_Head unreachable; /* 不可达链表 */
    PyGC_Head finalizers;  /* 实现__del__的对象 */
    PyGC_Head *gc;
    _PyTime_t t1 = 0;   /* initialize to prevent a compiler warning */

    // GC状态体
    GCState *gcstate = &tstate->interp->gc;

    // gc_collect_main() must not be called before _PyGC_Init
    // or after _PyGC_Fini()
    assert(gcstate->garbage != NULL);
    assert(!_PyErr_Occurred(tstate));

#ifdef EXPERIMENTAL_ISOLATED_SUBINTERPRETERS
    if (tstate->interp->config._isolated_interpreter) {
        // bpo-40533: The garbage collector must not be run on parallel on
        // Python objects shared by multiple interpreters.
        return 0;
    }
#endif

    if (gcstate->debug & DEBUG_STATS) {
        PySys_WriteStderr("gc: collecting generation %d...\n", generation);
        show_stats_each_generations(gcstate);
        t1 = _PyTime_GetMonotonicClock();
    }

    if (PyDTrace_GC_START_ENABLED())
        PyDTrace_GC_START(generation);

    /* update collection and allocation counters */
    // 将当前代的后一代的GC计数值 + 1
    // 将当前代及其以前的GC计数值重置为0, 因为回收某一代时, 会一起回收该代之前的所有代的不可达结点
    if (generation+1 < NUM_GENERATIONS)
        gcstate->generations[generation+1].count += 1;
    for (i = 0; i <= generation; i++)
        gcstate->generations[i].count = 0;

    /* merge younger generations with one we are currently collecting */
    // 将当前代与其之前的所有代的可收集结点的链表合并起来
    for (i = 0; i < generation; i++) {
        gc_list_merge(GEN_HEAD(gcstate, i), GEN_HEAD(gcstate, generation));
    }

    /* handy references */
    // young: 当前代可收集链表的头部节点, old: 当前代的下一代可收集链表的头部结点
    young = GEN_HEAD(gcstate, generation);
    if (generation < NUM_GENERATIONS-1)
        old = GEN_HEAD(gcstate, generation+1);
    else
        old = young;
    validate_list(old, collecting_clear_unreachable_clear);

    // 执行标记-清除算法, 将可收集对象链表拆分成可达链表和不可达链表
    deduce_unreachable(young, &unreachable);

    untrack_tuples(young);
    /* Move reachable objects to next generation. */
    // 将当前代的可达对象移入下一代中, 并将当前代的链表置空。
    if (young != old) {
        if (generation == NUM_GENERATIONS - 2) {
            gcstate->long_lived_pending += gc_list_size(young);
        }
        gc_list_merge(young, old);
    }
    else {
        /* We only un-track dicts in full collections, to avoid quadratic
           dict build-up. See issue #14775. */
        untrack_dicts(young);
        gcstate->long_lived_pending = 0;
        gcstate->long_lived_total = gc_list_size(young);
    }

    /* All objects in unreachable are trash, but objects reachable from
     * legacy finalizers (e.g. tp_del) can't safely be deleted.
     */
    gc_list_init(&finalizers);
    // NEXT_MASK_UNREACHABLE is cleared here.
    // After move_legacy_finalizers(), unreachable is normal list.

    // 去除不可达结点的标识, 最终移入finalizers链表
    move_legacy_finalizers(&unreachable, &finalizers);
    /* finalizers contains the unreachable objects with a legacy finalizer;
     * unreachable objects reachable *from* those are also uncollectable,
     * and we move those into the finalizers list too.
     */
    move_legacy_finalizer_reachable(&finalizers);

    validate_list(&finalizers, collecting_clear_unreachable_clear);
    validate_list(&unreachable, collecting_set_unreachable_clear);

    /* Print debugging information. */
    if (gcstate->debug & DEBUG_COLLECTABLE) {
        for (gc = GC_NEXT(&unreachable); gc != &unreachable; gc = GC_NEXT(gc)) {
            debug_cycle("collectable", FROM_GC(gc));
        }
    }

    /* Clear weakrefs and invoke callbacks as necessary. */
    // 清除不可达对象自身绑定的弱引用，并执行弱引用绑定的回调函数。
    m += handle_weakrefs(&unreachable, old);

    validate_list(old, collecting_clear_unreachable_clear);
    validate_list(&unreachable, collecting_set_unreachable_clear);

    /* Call tp_finalize on objects which have one. */
    finalize_garbage(tstate, &unreachable);

    /* Handle any objects that may have resurrected after the call
     * to 'finalize_garbage' and continue the collection with the
     * objects that are still unreachable */
    PyGC_Head final_unreachable;
    handle_resurrected_objects(&unreachable, &final_unreachable, old);

    /* Call tp_clear on objects in the final_unreachable set.  This will cause
    * the reference cycles to be broken.  It may also cause some objects
    * in finalizers to be freed.
    */
    m += gc_list_size(&final_unreachable);

    // 动态清除垃圾
    delete_garbage(tstate, gcstate, &final_unreachable, old);

    /* Collect statistics on uncollectable objects found and print
     * debugging information. */
    for (gc = GC_NEXT(&finalizers); gc != &finalizers; gc = GC_NEXT(gc)) {
        n++;
        if (gcstate->debug & DEBUG_UNCOLLECTABLE)
            debug_cycle("uncollectable", FROM_GC(gc));
    }
    if (gcstate->debug & DEBUG_STATS) {
        double d = _PyTime_AsSecondsDouble(_PyTime_GetMonotonicClock() - t1);
        PySys_WriteStderr(
            "gc: done, %zd unreachable, %zd uncollectable, %.4fs elapsed\n",
            n+m, n, d);
    }

    /* Append instances in the uncollectable set to a Python
     * reachable list of garbage.  The programmer has to deal with
     * this if they insist on creating this type of structure.
     */
    handle_legacy_finalizers(tstate, gcstate, &finalizers, old);
    validate_list(old, collecting_clear_unreachable_clear);

    /* Clear free list only during the collection of the highest
     * generation */
    if (generation == NUM_GENERATIONS-1) {
        clear_freelists(tstate->interp);
    }

    if (_PyErr_Occurred(tstate)) {
        if (nofail) {
            _PyErr_Clear(tstate);
        }
        else {
            _PyErr_WriteUnraisableMsg("in garbage collection", NULL);
        }
    }

    /* Update stats */
    // 更新
    if (n_collected) {
        *n_collected = m;
    }
    if (n_uncollectable) {
        *n_uncollectable = n;
    }

    // 维护GC状态体
    struct gc_generation_stats *stats = &gcstate->generation_stats[generation];
    stats->collections++;
    stats->collected += m;
    stats->uncollectable += n;

    if (PyDTrace_GC_DONE_ENABLED()) {
        PyDTrace_GC_DONE(n + m);
    }

    assert(!_PyErr_Occurred(tstate));
    return n + m;
}
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
static void
delete_garbage(PyThreadState *tstate, GCState *gcstate,
               PyGC_Head *collectable, PyGC_Head *old)
{
    assert(!_PyErr_Occurred(tstate));

    while (!gc_list_is_empty(collectable)) {
        PyGC_Head *gc = GC_NEXT(collectable);
        PyObject *op = FROM_GC(gc);

        _PyObject_ASSERT_WITH_MSG(op, Py_REFCNT(op) > 0,
                                  "refcount is too small");

        if (gcstate->debug & DEBUG_SAVEALL) {
            assert(gcstate->garbage != NULL);
            if (PyList_Append(gcstate->garbage, op) < 0) {
                _PyErr_Clear(tstate);
            }
        }
        else {
            inquiry clear;
            // 执行tp_clear函数指针指向的函数, 像list列表, dict字典对应的应该是clear方法
            if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
                Py_INCREF(op);
                (void) clear(op);
                if (_PyErr_Occurred(tstate)) {
                    _PyErr_WriteUnraisableMsg("in tp_clear of",
                                              (PyObject*)Py_TYPE(op));
                }
                Py_DECREF(op);
            }
        }
        // 由于程序运行, collectable链表在程序运行时是动态变化的, 
        // 如果该对象又回到了可收集链表中，那么表明它可能还活着, 将其移入下一代中，后序再回收。
        if (GC_NEXT(collectable) == gc) {
            /* object is still alive, move it, it may die later */
            gc_clear_collecting(gc);
            gc_list_move(gc, old);
        }
    }
}

分析：

(1).上文提到CPython默认分为三代，新生代，中生代，老生代，三代的计数器阈值分别为700, 20, 10。每触发一次GC，会导致后一代的计数器值加1。同时会将当前代及其前面所有代的计数器重置为0，因为后序操作会将当前代及其前面所有代的可收集链表合并，然后走标记-清除算法deduce_unreachable，具体实现原理前文已经分析过。

(2).执行完Mark-Sweep算法后，已经区分出可达链表和不可达链表，接下来要将可达链表中的所有结点对象移入到下一代的可收集对象链表中。

(3).对不可达链表进行垃圾回收，遍历不可达链表，对每个对象调用其tp_clear函数指针指向的函数，因此像list，dict，在Python层面来说，与tp_clear指向的函数等效的是clear()。

注：

在delete_garbage中有这样一段代码，我觉得开发者考虑的确实挺严谨的。

1
2
3
4
5
if (GC_NEXT(collectable) == gc) {
    /* object is still alive, move it, it may die later */
    gc_clear_collecting(gc);
    gc_list_move(gc, old);
}

程序在运行中, collectable链表在程序运行时是动态变化的, 如果该对象又出现在了可收集链表中，那么表明它可能还活着, 所以需要将其移入下一代中，后序再回收。这样虽然会额外增加判断、移动操作，但解决了再极偶然情况下，对象被误判回收的问题。

参考：

https://pythoninternal.wordpress.com/2014/08/04/the-garbage-collector/

https://github.com/python/cpython