思源笔记

# 垃圾回收机制

# 对象跟踪-可收集列表

一个对象是否需要跟踪，取决于它会不会形成循环引用。按照引用特征，Python 对象可以分为两类：

  • 内向型对象 ，例如 int 、float 、 str 等，这类对象不会引用其他对象，因此无法形成循环引用，无须跟踪；
  • 外向型对象 ，例如 tuple 、 list 、 dict 等容器对象，以及函数、类实例等复杂对象，这类对象一般都会引用其他对象，存在形成循环引用的风险，因此是垃圾回收算法关注的重点；

下面是一个典型的例子，橘红色外向型对象存在循环引用的可能性，需要跟踪；而绿色内向型对象在引用关系图中只能作为叶子节点存在，无法形成任何环状，因此无需跟踪：

​图片描述​

Python 为外向型对象分配内存时，调用位于 Modules/gcmodule.c 源文件的 _PyObject_GC_Alloc 函数。该函数在对象头部之前预留了一些内存空间，以便垃圾回收模块用 链表 将它们跟踪起来。预留的内存空间是一个 _gc_head 结构体，它定义于 Include/objimpl.h 头文件：

typedef union _gc_head {
    struct {
        union _gc_head *gc_next;
        union _gc_head *gc_prev;
        Py_ssize_t gc_refs;
    } gc;
    long double dummy;  /* force worst-case alignment */
    // malloc returns memory block aligned for any built-in types and
    // long double is the largest standard C type.
    // On amd64 linux, long double requires 16 byte alignment.
    // See bpo-27987 for more discussion.
} PyGC_Head;
  • gc_next ，链表后向指针，指向后一个被跟踪的对象；
  • gc_prev ，链表前向指针，指向前一个被跟踪的对象；
  • gc_refs ，对象引用计数副本，在标记清除算法中使用；
  • dummy ，内存对齐用，以 64 位系统为例，确保 _gc_head 结构体大小是 16 字节的整数倍，结构体地址以 16 字节为单位对齐；

以 list 对象为例，_PyObject_GC_Alloc 函数在 PyListObject 结构体基础上加上 _gc_head 结构体来申请内存，但只返回 PyListObject 的地址作为对象地址，而不是整块内存的首地址:

​image​

就这样，借助 gc_next 和 gc_prev 指针，Python 将需要跟踪的对象一个接一个组织成 双向链表 ：

​image​

这个链表也被称为 可收集 ( collectable )对象链表，Python 将从这个链表中收集并回收垃圾对象。

‍

# 分代回收机制

Python 程序启动后，内部可能会创建大量对象。如果每次执行标记清除法时，都需要遍历所有对象，多半会影响程序性能。为此，Python 引入分代回收机制——将对象分为若干“代”( generation )，每次只处理某个代中的对象，因此 GC 卡顿时间更短。

考察对象的生命周期，可以发现一个显著特征：一个对象存活的时间越长，它下一刻被释放的概率就越低。

因此，根据对象存活时间，对它们进行划分就是一个不错的选择。对象存活时间越长，它们被释放的概率越低，可以适当降低回收频率；相反，对象存活时间越短，它们被释放的概率越高，可以适当提高回收频率。

Python 内部根据对象存活时间，将对象分为 3 代(见 Include/internal/mem.h )：

每个代都由一个 gc_generation 结构体来维护，它同样定义于 Include/internal/mem.h 头文件：

struct gc_generation {
    PyGC_Head head; // 可收集对象链表头部，代中的对象通过该链表维护；
    int threshold; /* 仅当 *count* 超过本阀值时，*Python* 垃圾回收操作才会扫描本代对象 collection threshold */
    int count; /* 计数器，不同代统计项目不一样 count of allocations or collections of younger
                  generations */
};

Python 虚拟机运行时状态由 Include/internal/pystate.h 中的 pyruntimestate 结构体表示，它内部有一个 _gc_runtime_state ( Include/internal/mem.h )结构体，保存 GC 状态信息，包括 3 个对象代。这 3 个代，在 GC 模块( Modules/gcmodule.c ) _PyGC_Initialize 函数中初始化：

    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},
    };

为方便讨论，我们将这 3 个代分别称为：初生代、中生代 以及 老生代。当这 3 个代初始化完毕后，对应的 gc_generation 数组大概是这样的：

​image​

Python 调用 _PyObject_GC_Alloc 为需要跟踪的对象分配内存时，该函数将初生代 count 计数器加一，随后对象将接入初生代对象链表；当 Python 调用 PyObject_GC_Del 释放垃圾对象内存时，该函数将初生代 count 计数器减一；_PyObject_GC_Alloc 自增 count 后如果超过阀值( 700 )，将调用 collect_generations 执行一次垃圾回收( GC )。

collect_generations 函数从老生代开始，逐个遍历每个生代，找出需要执行回收操作( count>threshold )的最老生代。随后调用 collect_with_callback 函数开始回收该生代，而该函数最终调用 collect 函数。

collect 函数处理某个生代时，先将比它年轻的生代计数器 count 重置为 0 ；然后将它们的对象链表移除，与自己的拼接在一起后执行 GC 算法；最后，将下一个生代计数器加一。

几条直白的策略：

  • 每新增 701 个需要 GC 的对象，触发一次新生代 GC ；
  • 每执行 11 次新生代 GC ，触发一次中生代 GC ；
  • 每执行 11 次中生代 GC ，触发一次老生代 GC (老生代 GC 还受其他策略影响，频率更低)；
  • 执行某个生代 GC 前，年轻生代对象链表也移入该代，一起 GC ；
  • 一个对象创建后，随着时间推移将被逐步移入老生代，回收频率逐渐降低；

‍

# 标记清除法

# 循环引用

Python 采用标记清除法识别垃圾对象。该算法的输入是可收集对象链表，链表给出所有需要检测的对象；算法的输出是两个链表，其中一个包含 可达 ( reachable )对象，另一个包含 不可达 ( unreachable )对象。

标记清除算法在 collect 函数中实现，它位于 Modules/gcmodule.c​，步骤并不复杂。为避免深陷源码细节，我们先抽出身来进行一次直观考察。假设待检测可收集对象链表中的对象引用关系如下：

​图片描述​

其中，数字表示引用计数，箭头表示引用关系，虚线表示链表外对象(来自其他年代)，而链表结构被省略了。

首先，我们需要找出根对象。这里根对象是指被本链表以外的对象引用或被 Python 虚拟机直接引用的对象，与上一小节讨论的略有不同。由于根对象存在来自外部的引用，不能安全释放，应该标记为 可达 ( reachable )。

根对象集合不难确定：我们只需遍历每个对象引用的对象，将它们的引用计数减一，最后计数不为零的就是根对象。

​图片描述​

请注意，虚线表示外部对象，它既不会被遍历到，引用计数也不会被减一。

接着，从深色的根对象出发，遍历引用关系，将可以访问到的对象同样标为深色。标色完毕后，对象将分成有色和无色两种：

​图片描述​

这样一来，无色部分就是只存在循环引用的垃圾对象，可以被安全释放。

‍

回过头来研究位于 collect 函数的算法处理逻辑，它先将对象引用计数拷贝到 gc_refs 字段：

    update_refs(young);

这是因为直接操作 ob_refcnt 字段的话，对象的引用计数就被破坏了，而且无法复原。操作 gc_refs 副本字段，就不存在这个问题。

接着，collect 函数调用 subtract_refs 遍历链表中每个对象，将它们引用的对象引用计数( gc_refs )减一。注意到，subtract_refs 函数调用 tp_traverse 函数，来遍历被一个对象引用的对象：

subtract_refs(young);

static int
visit_decref(PyObject *op, void *data)
{
    assert(op != NULL);
    if (PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        assert(_PyGCHead_REFS(gc) != 0); /* else refcount was too small */
        if (_PyGCHead_REFS(gc) > 0)
            // 将对象引用计数减一(gc_refs)
            _PyGCHead_DECREF(gc);
    }
    return 0;
}

static void
subtract_refs(PyGC_Head *containers)
{
    traverseproc traverse;
    PyGC_Head *gc = containers->gc.gc_next;
    // 遍历链表每一个对象
    for (; gc != containers; gc=gc->gc.gc_next) {
        // 遍历当前对象所引用的对象，调用visit_decref将它们的引用计数减一
        traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
        (void) traverse(FROM_GC(gc),
                       (visitproc)visit_decref,
                       NULL);
    }
}

经过这个步骤之后，根对象就被找出来了，它们的引用计数( gc_refs )不为零。

最后，collect 函数初始化一个链表 unreachable 来保存不可达对象，调用 move_unreachable 标记可达对象，并将不可达对象移入 unreachable 链表：

    gc_list_init(&unreachable);
    move_unreachable(young, &unreachable);

move_unreachable 遍历给定对象链表，如果一个对象的引用计数不为 0 ，就将它标记为可达( GC_REACHABLE )；否则将它标记为临时不可达，移入不可达链表。

    // 遍历链表每个对象
    while (gc != young) {
        PyGC_Head *next;

        // 如果引用计数不为0，说明它可达
        if (_PyGCHead_REFS(gc)) {
            PyObject *op = FROM_GC(gc);
            traverseproc traverse = Py_TYPE(op)->tp_traverse;
            assert(_PyGCHead_REFS(gc) > 0);
            // 将它标记为可达
            _PyGCHead_SET_REFS(gc, GC_REACHABLE);
            // 遍历被它引用的对象，调用visit_reachable将被引用对象标记为可达
            (void) traverse(op,
                            (visitproc)visit_reachable,
                            (void *)young);
            next = gc->gc.gc_next;
            if (PyTuple_CheckExact(op)) {
                _PyTuple_MaybeUntrack(op);
            }
        }
        else {
            next = gc->gc.gc_next;
            // 暂时移入不可达链表
            gc_list_move(gc, unreachable);
            _PyGCHead_SET_REFS(gc, GC_TENTATIVELY_UNREACHABLE);
        }
        gc = next;
    }

如果一个对象可达，Python 还通过 tp_traverse 逐个遍历它引用的对象，并调用 visit_reachable 函数进行标记：

static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{
    if (PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        const Py_ssize_t gc_refs = _PyGCHead_REFS(gc);

        if (gc_refs == 0) {
            // 引用计数为零，将计数设置为1，表明它是可达的
            _PyGCHead_SET_REFS(gc, 1);
        }
        else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
            // 如果对象被临时标记为不可达，将引用计数设置为1表明它是可达的
            // 并移回原链表继续处理
            gc_list_move(gc, reachable);
            _PyGCHead_SET_REFS(gc, 1);
        }
         else {
            assert(gc_refs > 0
                   || gc_refs == GC_REACHABLE
                   || gc_refs == GC_UNTRACKED);
         }
    }
    return 0;
}

如果被引用的对象引用计数为 0 ，将它的引用计数设为 1 ，之后它将被 move_unreachable 遍历到并设为可达；如果被引用的对象被临时移入 unreachable 链表，同样将它的引用计数设为 1 ，并从 unreachable 链表移回原链表尾部，之后它将被 move_unreachable 遍历到并设为可达。

当 move_unreachable 函数执行完毕，unreachable 链表中的对象就是不可达对象，可被安全回收。

‍

← PyCodeObj和PyFrameObj →