Skip to content

垃圾回收.md

Latest commit

 

History

History
475 lines (306 loc) · 20.9 KB

垃圾回收.md

File metadata and controls

475 lines (306 loc) · 20.9 KB

垃圾回收

Python 中主要的垃圾回收机制是引用计数，辅以标记清除和分代回收。

引用计数

引用计数是非常直观的一种垃圾回收算法，每个对象内部维护着一个引用计数，如果引用计数变为 0，说明该对象生命周期结束，因此可以马上释放它的内存。

优点：

  • 原理简单，容易实现。

  • 垃圾回收的实时性高，一旦对象的引用技术变为 0，马上可以回收其占用的内存。

缺点：

  • 循环引用。

  • 维护引用计数带来许多额外的操作，和对象数量成正比。

循环引用只会发生在 container 对象中，例如 list，dict 等。

循环引用例子：

In [505]: l1 = []

In [506]: l2 = []

In [507]: l1.append(l2)

In [508]: l2.append(l1)

In [509]: print l1
[[[...]]]

In [510]: print l2
[[[...]]]

In [511]:
   +----------+           +----------+
+-->  list 1  |   +------->  list 1  |
|  +----------+   |       +----------+
|  |          +---+    +--+          |
|  +----------+        |  +----------+
|  |          |        |  |          |
|  +----------+        |  +----------+
|  |          |        |  |          |
|  +----------+        |  +----------+
|                      |
+----------------------+

为了解决循环引用问题，引入了标记 - 清除垃圾回收机制和分代垃圾回收机制。

和 GC 相关的几个 tp_xxx

tp_clear

摘自 官方文档:

An optional pointer to a clear function for the garbage collector. This is only used if the Py_TPFLAGS_HAVE_GC flag bit is set. The signature is:

int tp_clear(PyObject *);

The tp_clear member function is used to break reference cycles in cyclic garbage detected by the garbage collector. Taken together, all tp_clear functions in the system must combine to break all reference cycles. This is subtle, and if in any doubt supply a tp_clear function. For example, the tuple type does not implement a tp_clear function, because it’s possible to prove that no reference cycle can be composed entirely of tuples. Therefore the tp_clear functions of other types must be sufficient to break any cycle containing a tuple. This isn’t immediately obvious, and there’s rarely a good reason to avoid implementing tp_clear.

Implementations of tp_clear should drop the instance’s references to those of its members that may be Python objects, and set its pointers to those members to NULL, as in the following example:

static int
local_clear(localobject *self)
{
    Py_CLEAR(self->key);
    Py_CLEAR(self->args);
    Py_CLEAR(self->kw);
    Py_CLEAR(self->dict);
    return 0;
}

The Py_CLEAR() macro should be used, because clearing references is delicate: the reference to the contained object must not be decremented until after the pointer to the contained object is set to NULL. This is because decrementing the reference count may cause the contained object to become trash, triggering a chain of reclamation activity that may include invoking arbitrary Python code (due to finalizers, or weakref callbacks, associated with the contained object). If it’s possible for such code to reference self again, it’s important that the pointer to the contained object be NULL at that time, so that self knows the contained object can no longer be used. The Py_CLEAR() macro performs the operations in a safe order.

Because the goal of tp_clear functions is to break reference cycles, it’s not necessary to clear contained objects like Python strings or Python integers, which can’t participate in reference cycles. On the other hand, it may be convenient to clear all contained Python objects, and write the type’s tp_dealloc function to invoke tp_clear.

More information about Python’s garbage collection scheme can be found in section Supporting Cyclic Garbage Collection.

在 typeobject.c 的 type_new 函数中, 可以看到用户定义的类的 tp_clear 被设置为 subtype_dealloc.

type->tp_clear = subtype_clear;

tp_dealloc

摘自 官方文档:

A pointer to the instance destructor function. This function must be defined unless the type guarantees that its instances will never be deallocated (as is the case for the singletons None and Ellipsis). The function signature is:

void tp_dealloc(PyObject *self);

The destructor function is called by the Py_DECREF() and Py_XDECREF() macros when the new reference count is zero. At this point, the instance is still in existence, but there are no references to it. The destructor function should free all references which the instance owns, free all memory buffers owned by the instance (using the freeing function corresponding to the allocation function used to allocate the buffer), and call the type’s tp_free function. If the type is not subtypable (doesn’t have the Py_TPFLAGS_BASETYPE flag bit set), it is permissible to call the object deallocator directly instead of via tp_free. The object deallocator should be the one used to allocate the instance; this is normally PyObject_Del() if the instance was allocated using PyObject_New() or PyObject_VarNew(), or PyObject_GC_Del() if the instance was allocated using PyObject_GC_New() or PyObject_GC_NewVar().

Finally, if the type is heap allocated (Py_TPFLAGS_HEAPTYPE), the deallocator should decrement the reference count for its type object after calling the type deallocator. In order to avoid dangling pointers, the recommended way to achieve this is:

static void foo_dealloc(foo_object *self) {
    PyTypeObject *tp = Py_TYPE(self);
    // free references and buffers here
    tp->tp_free(self);
    Py_DECREF(tp);
}

当减少引用计数时发现引用计数等于 0, 便会调用 tp_dealloc. tp_alloc 一般调用 tp_free, 释放对象的成员, 以及本身的内存.

在 typeobject.c 的 type_new 函数中, 可以看到用户定义的类的 tp_dealloc 被设置为 subtype_dealloc.

type->tp_dealloc = subtype_dealloc;

tp_free

摘自 官方文档

An optional pointer to an instance deallocation function. Its signature is:

void tp_free(void *self);

An initializer that is compatible with this signature is PyObject_Free().

Inheritance:

This field is inherited by static subtypes, but not by dynamic subtypes (subtypes created by a class statement)

Default:

In dynamic subtypes, this field is set to a deallocator suitable to match PyType_GenericAlloc() and the value of the Py_TPFLAGS_HAVE_GC flag bit.

For static subtypes, PyBaseObject_Type uses PyObject_Del.

在 typeobject.c 的 type_new 函数中, 可以看到用户定义的类的 tp_free 被设置为 PyObject_GC_Del.

type->tp_free = PyObject_GC_Del;

tp_del

tp_del 已经不推荐使用.

在 Python 中 tp_del 对应于 __del__.

tp_finalize

官方文档

在 Python 中 tp_finalize 对应于 __del__.

总结

tp_clear 用于打破对象之间的循环引用.

tp_dealloc 用于释放对象内的成员的内存.

tp_free 用于释放对象本身的内存.

它们之间的调用关系为:

Py_DECREF
    |
    v
tp_dealloc -> tp_clear
    |
    +-------> tp_free

参考:

标记清除（mark-sweep）

标记清除的基本原理是：

  • 寻找根对象（root object）的集合，所谓的 root object 即是一些全局引用和函数栈中的引用。这些引用所用的对象是不可被删除的。而这个 root object 集合也是垃圾检测动作的起点。

  • 从 root object 集合出发，沿着 root object 集合中的每一个引用，如果能到达某个对象 A，则 A 称为可达的（reachable），可达的对象也不可被删除。这个阶段就是垃圾检测阶段。

  • 当垃圾检测阶段结束后，所有的对象分为了可达的和不可达的（unreachable）两部分，所有的可达对象都必须予以保留，而所有的不可达对象所占用的内存将被回收，这就是垃圾回收阶段。

container 对象链表

由于只有 contaier 对象才会存在循环引用的问题，所以 Python 为这些特定对象增加了一个额外的头信息，即 PyGG_Head。

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;

PyObject *
_PyObject_GC_Malloc(size_t basicsize)
{
	PyObject *op;
	PyGC_Head *g = (PyGC_Head *)PyObject_MALLOC(
                sizeof(PyGC_Head) + basicsize);
	if (g == NULL)
		return PyErr_NoMemory();
	g->gc.gc_refs = 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;
	}
	op = FROM_GC(g);
	return op;
}

通过 PyGC_Head，所有的 container 对象形成一个循环双向链表。

gc_refs 有四种状态：

  • GC_UNTRACKED

    这是通过 PyObject_GC_Malloc 分配对象后的初始状态。实际值等于 -2。

  • GC_REACHABLE

    这个状态表示对象在 GC 链表上。实际值等于 -3

  • GC_TENTATIVELY_UNREACHABLE

    当进行 GC 时，gc_refs 可能会被设置为这个状态，表示对象可能不可达。实际值等于 -4。

  • > 0

    当进行 GC 时，gc_refs 表示对象 refcnt。

gc_refs 其实使用最低位表示 tp_finalized 是否被调用，其余高位用来表示状态。具体看下面的代码。

/* Bit 0 is set when tp_finalize is called */
#define _PyGC_REFS_MASK_FINALIZED  (1 << 0)
/* The (N-1) most significant bits contain the gc state / refcount */
#define _PyGC_REFS_SHIFT           (1)
#define _PyGC_REFS_MASK            (((size_t) -1) << _PyGC_REFS_SHIFT)

#define _PyGCHead_REFS(g) ((g)->gc.gc_refs >> _PyGC_REFS_SHIFT)
#define _PyGCHead_SET_REFS(g, v) do { \
    (g)->gc.gc_refs = ((g)->gc.gc_refs & ~_PyGC_REFS_MASK) \
        | (((size_t)(v)) << _PyGC_REFS_SHIFT);             \
    } while (0)
#define _PyGCHead_DECREF(g) ((g)->gc.gc_refs -= 1 << _PyGC_REFS_SHIFT)

#define _PyGCHead_FINALIZED(g) (((g)->gc.gc_refs & _PyGC_REFS_MASK_FINALIZED) != 0)
#define _PyGCHead_SET_FINALIZED(g, v) do {  \
    (g)->gc.gc_refs = ((g)->gc.gc_refs & ~_PyGC_REFS_MASK_FINALIZED) \
        | (v != 0); \
    } while (0)

#define _PyGC_FINALIZED(o) _PyGCHead_FINALIZED(_Py_AS_GC(o))
#define _PyGC_SET_FINALIZED(o, v) _PyGCHead_SET_FINALIZED(_Py_AS_GC(o), v)

#define _PyGC_REFS(o) _PyGCHead_REFS(_Py_AS_GC(o))

#define _PyGC_REFS_UNTRACKED                    (-2)
#define _PyGC_REFS_REACHABLE                    (-3)
#define _PyGC_REFS_TENTATIVELY_UNREACHABLE      (-4)

分代回收

分代回收的基本原理是：将所有的对象按照其存活时间划分成不同的代，对象的存活时间越长，说明该对象越不可能是垃圾，被回收的概率越低。存活时间指的是经历的垃圾回收的次数，经历次数越多，说明代越老。

Python 的 GC 有三个代，每个代其实就是一个双向循环链表，该链表通过前面的 PyGC_Head 连接起来。

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

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

第 0 代是最年轻的代，新分配的对象被添加到第 0 代的链表上（当然并不是所有 GC 对象都被添加到链表上）。

回收流程

主要流程：

  • 当 PyObject_GC_Malloc 分配对象内存时，第 0 代的 count 加 1。如果 count 超过阈值（700）那么就会触发 GC。

  • 调用 collect_generations 函数。该函数找到 count 超过阈值的最老的一代，假设为 generation。然后在开始收集垃圾对象之前先调用 start 用户回调函数，收集完成后在调用 stop 用户回调函数。

    这里有一个优化后面再讲。

  • 调用 collect 函数。collect 函数负责主要的垃圾回收工作。

collect 函数的流程：

  • 将 generation 和比 generation 更年轻的代的 count 设置为 0。假设比 young 老一辈的代为 old（odl = young + 1），如果 old 存在，那么将 old 的 count 加 1。

  • 将比 generation 更年轻的代合并到 generation 链表的后面，形成一条链表。假设这条链表名字为 young。

  • udpate_refs。遍历 young 链表，将每个 container 对象的 refcnt 复制到 PyGC_Head 的 gc_refs 字段。

  • subtract_refs。遍历 young 链表，访问每个 container 对象时，调用对象的 tp_traverse 方法，该方法支持回调函数以便访问对象内部引用的其它对象，然后将每个引用的其它对象的 gc_refs 减 1。

    这一步的目的是断开所有的引用链。对象之间的循环引用被断开了。

  • move_unreachable。

    遍历 young 链表，如果 contaienr 对象的 gc_refs 大于 0，说明该对象是从外部可以直接访问到的，这称为可达的（reachable）。将可达对象的 gc_refs 设为 GC_REACHABLE，然后通过 tp_traverse 访问对象内部引用的其它对象。

    • 如果引用对象的的 gc_refs 等于 0，那么将其设置为 1，因为这个引用对象可以从 container 对象访问到，这称为间接可达。

    • 如果引用对象的 gc_refs 等于 GC_TENTATIVELY_UNREACHABLE，说明这个引用对象在此之前已经被 move_unreachable 访问过，而且原来的 gc_refs 等于 0，GC_TENTATIVELY_UNREACHABLE 表示对象可能不可达。现在发现 container 对象可以访问到该引用对象，因此将该引用对象的 gc_refs 设置为 1，并将其从 unreachable 链表移回到 young 链表。

    如果 container 对象的 gc_refs 等于 0（除了大于 0 只可能等于 0），那么暂时认为其不可达，将 gc_refs 设置为 GC_TENTATIVELY_UNREACHABLE，并将其移到 unreachable 链表。

  • 到这一步标记阶段已经完成了，young 链表上的对象都是可达的，unreachable 链表上的对象都是不可达的，也就是垃圾。

  • 如果 old 存在，那么将 young 链表合并到 old 链表，如果 old 不存在，那么说明 young 是最老的一代，说明这次垃圾回收是完整地对所有代进行的。这个过程就是分代回收，每经历一次垃圾回收，留下来的对象就 “老了一代”。

collect 函数的其它工作：

  • move_legacy_finalizers。将 unreachable 链表中包含 tp->tp_del（tp_del != NULL，tp_del 对应 Python 中的__del__）方法的对象移到到 finalizers 链表，同时将这些对象的 gc_refs 设置为 GC_REACHABLE。

    如果定义 tp_del, GC 认为这些对象是无法回收的, 因此将它们从 unreachable 链表中移出来.

  • move_legacy_finalizer_reachable。遍历 finalizers 链表，通过对象的 tp->traverse 方法，将对象引用的其它对象也移到动 finalizers 链表，前提是其它对象在 unreachable 链表上。

  • handle_weakrefs。处理弱引用。

    简单来讲就是遍历 unreachable 链表, 调用对象的弱引用的回调函数. 具体的细节我还全部没想明白.

  • finalize_garbage。遍历 unreachable 链表，调用对象的 tp_finalizer 方法。

  • check_garbage。再次检查 unreachable 链表是否真的全部是不可达对象。检查方法是 update_refs 和 subtract_refs。如果发现某个对象的 gc_refs 不等于 0，那么将 unreachable 链表合并到 old 链表。

  • delete_garbage。遍历 unreachable 链表，调用对象的 tp_clear 方法。

    tp_clear 负责打破循环引用, 简单来说就是减少内部引用的成员的引用计数. tp_clear 导致一系列的链式反应. 最终所有循环引用中的对象的引用计数都会变为 0, 此时会调用 tp_dealloc, tp_dealloc 一般会调用 tp_clear 和 tp_free, 因此在 tp_clear 要注意无限循环调用的问题. tp_free 负责回收对象本身的内存.

    以列表的 tp_clear 为例：

    static int
list_clear(PyListObject *a)
{
    Py_ssize_t i;
    PyObject **item = a->ob_item;
    if (item != NULL) {
        /* Because XDECREF can recursively invoke operations on
          this list, we make it empty first. */
        i = Py_SIZE(a);
        Py_SIZE(a) = 0;
        a->ob_item = NULL;
        a->allocated = 0;
        while (--i>= 0) {
            Py_XDECREF(item[i]);
        }
        PyMem_FREE(item);
    }
    /* Never fails; the return value can be ignored.
      Note that there is no guarantee that the list is actually empty
      at this point, because XDECREF may have populated it again! */
    return 0;
}

  • handle_legacy_finalizers。将 finalizers 链表合并到 old 链表。

  • clear_freelists。释放对象特有的内存池，例如列表的 free_list。这一步只有在 generation 等于最老的一代才会进行。

回收优化

为了减少垃圾收集的次数，Python 引入了两个变量：long_lived_pending 和 long_lived_total。

先定义两个概念：

  • 完全垃圾收集：在 collect_generations 函数，找到的 generatioon 是最老的一代，也就是第 2 代，因此垃圾收集需要从最老的一代开始，然后到最年轻的一代结束。完全垃圾收集指的就是对所有代进行垃圾收集。

  • 部分垃圾收集：与完全垃圾收集的概念相反，部分垃圾收集指的是只对中间一代（第 1 代）到最年轻一代（第 0 代）进行垃圾收集。

long_lived_total 表示上次进行完全垃圾收集后第 2 代链表的长度。

long_lived_pending 表示自上次进行完全垃圾收集以来，每次进行部分垃圾收集后第 1 代链表长度的累积值。前面提到第 1 代链表会合并到第 2 代，所以名字中有 pending。

优化：在 collect_generations 函数中，如果找到的 generation 等于 2，那么只有 long_lived_pending > long_lived_total / 4 才会进行完全垃圾收集，否则寻找一下个代。

因为第 2 代保存了非常多的对象，几乎是所有一直存活的对象，对第 2 代进行垃圾回收是非常耗时的，另外，对第 2 代频繁进行垃圾回收也是毫无意义的。

总结

GC 中最复杂的就是如何正确地处理弱引用的回调函数以及 tp_finalize.

弱引用的回调函数和 tp_finalize 都有可能是 Python 代码, 而执行 Python 代码会回到 ceval, 从而有可能当前执行 GC 的线程放弃 GIL, 其它线程开始执行.

一些容易导致的问题如下:

  • 重入问题. Python 层面的回调函数可以调用任意函数.

  • Python 层面的代码有可能复活 unreachable 对象.

  • Python 层面的代码有可能访问某些已经执行了 tp_clear 的对象, 这些对象的状态可能已经不合法了, 访问这些对象可能导致 segmentfault.

解决办法是 handle_weakrefs 函数, handle_weakrefs 负责清除 unreachable 对象的弱引用链表. 这样以来在 delete_garbage 时就不会调用弱引用的回调函数.

可以看一下源码中的 gc_weakref.txt.

为了避免一些 GC 导致的奇怪问题, 在 __del__ 和弱引用的回调函数中不要做大多复杂的事情, 最好不要访问可能在循环引用链中的对象.

People simply shouldn't try to use `__del__` or weakref callbacks to do fancy stuff.

相关文章和讨论