大师兄的Python源码学习笔记(五十五）: Python的内存

大师兄的Python源码学习笔记(五十四）: Python的内存管理机制(九）
大师兄的Python源码学习笔记(五十六）: Python的内存管理机制(十一）

五、Python中的垃圾收集

3. 标记——清除方法

• 由于Python采用了三代的分代收集机制，如果当前收集的是第一代，那么在开始垃圾收集之前，Python会通过gc_list_merge将比其年轻的所有代的内存链表链接到第一代内存链表之后。

Modules/gcmodule.c

/*** list functions ***/

static void
gc_list_init(PyGC_Head *list)
{
    list->gc.gc_prev = list;
    list->gc.gc_next = list;
}

Modules/gcmodule.c

/* append list `from` onto list `to`; `from` becomes an empty list */
static void
gc_list_merge(PyGC_Head *from, PyGC_Head *to)
{
    PyGC_Head *tail;
    assert(from != to);
    if (!gc_list_is_empty(from)) {
        tail = to->gc.gc_prev;
        tail->gc.gc_next = from->gc.gc_next;
        tail->gc.gc_next->gc.gc_prev = tail;
        to->gc.gc_prev = from->gc.gc_prev;
        to->gc.gc_prev->gc.gc_next = to;
    }
    gc_list_init(from);
}

• 下图展示了merge的结果：

  
  
• 此后的标记——清除算法就将在merge之后所得到的那一条内存链表上进行。
• 在开始之前，我们要先建立一个循环引用的例子，用于解释Python是如何通过标记——清除垃圾收集方法打破循环引用：

>>> list1 = []
>>> list2 = []
>>> list1.append(list2)
>>> list2.append(list1)
>>> a = list1
>>> list3 = []
>>> list4 = []
>>> list3.append(list4)
>>> list4.append(list3)

• 其中PyObject_HEAD部分的数值为对象的引用计数ob_refcnt的值。

2.1 寻找Root Object集合

• 为了使用标记——清除算法，首先需要找出root object集合，那么哪些container对象应该属于root object哪？
• 在循环引用案例中，两个对象的引用计数都为1，但仅存在它们之间，所以这两个对象都需要被回收。
• 也就是说，虽然他们的引用计数为1，但有效引用计数为0。
• 为了从引用计数获得有效引用计数，必须将循环引用的影响去除，具体的实现就是将两个对象各自的引用计数减1：

• 假设两个对象为A、B；
• 从A出发，因为它有一个对B的引用，则将B的引用计数减1；
• 然后顺着引用到B，因为它有一个对A的引用，同样将A的引用计数减1；
• 通过这种方式完成了循环引用对象间环的摘除。

• 但这样可能会引出一个问题：

• 假设可收集对象链表中的container对象A有一个对对象C的引用，而C并不在这个链表中；
• 如果将C的引用计数减1，而最后A并没有被回收，则C的被错误的减少了1，这将导致在未来的某个时刻出现一个对C的悬空引用**；
• 为此，更好的做法是并不改动真是的引用计数，而改动引用计数的副本。
• 而这个副本的唯一作用就是寻找root object集合，它就是PYGC_HEAD中的gc.gc_ref。
• 在垃圾收集的第一步，就是遍历可收集对象链表，并将每个对象的gc.gc_ref值设置为其ob_refcnt值。

Modules/gcmodule.c

/* Set all gc_refs = ob_refcnt.  After this, gc_refs is > 0 for all objects
 * in containers, and is GC_REACHABLE for all tracked gc objects not in
 * containers.
 */
static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc = gc->gc.gc_next) {
        assert(_PyGCHead_REFS(gc) == GC_REACHABLE);
        _PyGCHead_SET_REFS(gc, Py_REFCNT(FROM_GC(gc)));
        /* Python's cyclic gc should never see an incoming refcount
         * of 0:  if something decref'ed to 0, it should have been
         * deallocated immediately at that time.
         * Possible cause (if the assert triggers):  a tp_dealloc
         * routine left a gc-aware object tracked during its teardown
         * phase, and did something-- or allowed something to happen --
         * that called back into Python.  gc can trigger then, and may
         * see the still-tracked dying object.  Before this assert
         * was added, such mistakes went on to allow gc to try to
         * delete the object again.  In a debug build, that caused
         * a mysterious segfault, when _Py_ForgetReference tried
         * to remove the object from the doubly-linked list of all
         * objects a second time.  In a release build, an actual
         * double deallocation occurred, which leads to corruption
         * of the allocator's internal bookkeeping pointers.  That's
         * so serious that maybe this should be a release-build
         * check instead of an assert?
         */
        assert(_PyGCHead_REFS(gc) != 0);
    }
}

• 接着将环引用从引用中删除:

Modules/gcmodule.c

/* Subtract internal references from gc_refs.  After this, gc_refs is >= 0
 * for all objects in containers, and is GC_REACHABLE for all tracked gc
 * objects not in containers.  The ones with gc_refs > 0 are directly
 * reachable from outside containers, and so can't be collected.
 */
static void
subtract_refs(PyGC_Head *containers)
{
    traverseproc traverse;
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc=gc->gc.gc_next) {
        traverse = Py_TYPE(FROM_GC(gc))->tp_traverse;
        (void) traverse(FROM_GC(gc),
                       (visitproc)visit_decref,
                       NULL);
    }
}

• 其中的traverse是与特定的container对象相关的，在container对象的类型对象中定义。
• 一般来说，traverse的工作是遍历container对象中的每一个引用，然后对引用进行某种动作。
• 这个动作在subtract_refs中就是visit_decref，它以一个回调函数的形式传递到traverse操作中。

• 在完成了subtract_refs后，可收集对象链表中所有container对象之间的环引用都被摘除了。
• 这时，有一些container对象的PYGC_Head.gc.gc_ref还不为0，这意味着存在对这些对象的外部引用。
• 而这些对象，就是开始标记——清除算法的root object集合。