Python内核阅读(二十二): 内存管理机制(下)

Python 2017-09-05

起步

上一篇提到了python对内存管理进行了层次级的封装, 并且为了避免过多的 mallocfree 调用. 将申请的内存统统交给 arnas 来管理. 本章则要谈谈引用计数与垃圾回收机制.

自动垃圾回收是为了让开发人员从管理内存的噩梦中解放出来. 而python中的动态内存管理与java, c#有着很大的不同. 在python中, 大多数对象的生命周期都是通过对象的引用计数来管理的.

引用计数与垃圾收集

从广义上来讲, 引用计数也是一种垃圾收集机制, 而且是最直观最简单的垃圾收集技术. 虽然引用计数必须在每次分配和释放内存的时候加入管理引用计数的动作, 然而与其他主流的垃圾收集技术相比, 引用计数方法有一个最大的优先, 即实时性, 任何内存, 一单没有指向它的引用, 就会立即被回收. 而其他的垃圾收集技术必须在某种特殊条件下才能进行无效内存的回收.

引用计数机制所带来的维护引用计数的额外操作与python运行中所进行的内存分配和释放, 引用赋值次数是成正比的, 这也是引用计数执行效率较慢的原因(软肋).为了与引用计数机制搭配, 在内存的分配和释放上获得最高的效率, python因此设计了很多内存池机制, 如上一篇的小块内存池. 而且在一些PyObject中如PyLongObject, PyUnicodeObject, PyDictObject, PyListObject等都有与各个对象相关的内存池机制. 这些大量使用的面向特定对象内存池机制正式为了弥补引用计数的软肋.

引用计数还需要处理一个致命的弱点, 就是循环引用. 当若干对象相互引用, 会造成每一个对象的引用计数都不会0, 因此这些对象所占用的内存永远不会回收.

为了解决这个问题, 需要引入其他垃圾回收计数来打破循环引用, python中使用了主流的垃圾收集技术的标记--清除和分代收集两种技术来填补其内存管理机制最后的漏洞.

三色标记模型

任何垃圾收集机制, 一般都分为两个阶段: 垃圾检测和垃圾回收. 垃圾检测是从所有已分配的内存中区别出可以回收的内存和不可回收的内存, 而垃圾回收则是将可回收内存归还给操作系统. python中的垃圾收集是基于 三色标记模型 建立起来的. 这种模型有 标记--清除(Mark--Sweep) 方法.

从具体上来将, 标记--清除(Mark--Sweep) 同样遵循垃圾收集的两个阶段, 简要工作过程如下:

  • 寻找根对象(root object)的集合, 所谓的root object即是一些全局引用和函数栈中的引用. 这些引用所用的对象是不可被删除的. 而这个root object集合也是垃圾检测动作的起点.
  • root object集合出发, 沿着root object集合中的每一个引用, 如果能达到某个对象A, 则A成为可达的 (reachable) , 可达的对象也不可被删除. 这个阶段就是垃圾检测阶段.
  • 当垃圾检测极端结束后, 所有的对象分为了可达与不可达两部分. 所有可达的对象都必须给予保留, 而所有不可达的对象所占用的内存将被回收, 这就是垃圾回收阶段

在垃圾收集动作被激活之前, 系统中所分配的所有对象与对象之间的引用组成一张有向图, 其中对象是图中的节点, 而对象间的引用是图的边. 我们在这个有向图的基础上建立一个三色标注模型, 更形象的展示垃圾收集的整个动作. 当垃圾收集开始时, 我们假设系统中所有对象都是不可达, 在图中以 白色 标注, 随后,垃圾收集的动作开始, 从root object集合中某个引用链开始, 在某个时刻达到了对象A, 那么我们将A标记为 灰色 , 灰色表示一个对象是可达的, 但是其包含的引用还没检查. 当我们检查了对象A所包含的所有引用之后, A将被标记为 黑色 , 黑色表示其包含的所有引用已经被检查过了. 显然, 这时, A中引用所引用的对象则被标记为 灰色 . 加入我们从 root object 出发, 采用广度优先搜索, 灰色节点的对象集合就如同水波一样向外扩散, 随着所有的灰色节点都变为了黑色节点, 也意味着垃圾检查阶段的结束.

20170905230344.png

python 中的垃圾收集

如前所述, 在python中, 主要的内存管理手段是引用计数机制, 而 标记--清除 和分代收集只是为了打破循环引用而引入的补充技术, 这一事实意味着python中的垃圾收集只关注可能会产生循环引用的对象. 很显然, 像PyLongObject和PyUnicodeObject这些是不可能产生循环引用. 循环引用可能法神在 container对象之间如list, dict, class等. 当python的垃圾收集机制运行时, 只需要检测这些container对象, 而对其他对象则不必理会, 这使得垃圾收集带来的开销只依赖于container对象的数量, 而非所有对象. 为了达到这一点, python需要跟踪每一个创建的container对象. python采用了一个双向链表, 所有的container对象创建之后, 都会被插入到这个链表中.

可收集对象链表

在对python对象机制的分析中我们已经看到, 任何一个python对象都分为两部分, 一部分是 PyObject_HEAD, 另一部分是对象自身的数据. 然而, 对于一个需要被垃圾收集机制跟踪的container对象而言, 这些还不够, 因为这个对象还必须链入到python内部的可收集对象的链表中去. 则必须加入另外的信息, 这个信息位于 PyObject_HEAD 之前, 称为 PyGC_Head :

[objimpl.h]
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;

所以, 对于python所创建的可收集 container对象, 其内存分布与我们之前所了解的内存部署是不同的:

[gcmodule.c]
PyObject * _PyObject_GC_New(PyTypeObject *tp)
{
    PyObject *op = _PyObject_GC_Malloc(_PyObject_SIZE(tp));
    if (op != NULL)
        op = PyObject_INIT(op, tp);
    return op;
}

展开 _PyObject_GC_Malloc :

[gcmodule.c]
#define _PyGC_REFS_UNTRACKED                    (-2)
#define GC_UNTRACKED                    _PyGC_REFS_UNTRACKED
PyObject * _PyObject_GC_Malloc(size_t basicsize)
{
    return _PyObject_GC_Alloc(0, basicsize);
}

static PyObject * _PyObject_GC_Alloc(int use_calloc, size_t basicsize)
{
    PyObject *op;
    PyGC_Head *g;
    size_t size;
    if (basicsize > PY_SSIZE_T_MAX - sizeof(PyGC_Head))
        return PyErr_NoMemory();
    size = sizeof(PyGC_Head) + basicsize;// 为本身对象即PyGC_Head申请内存
    if (use_calloc)
        g = (PyGC_Head *)PyObject_Calloc(1, size);
    else
        g = (PyGC_Head *)PyObject_Malloc(size);
    if (g == NULL)
        return PyErr_NoMemory();
    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;
    }
    op = FROM_GC(g);
    return op;
}

当python为可收集的container对象申请内存空间时, 也为 PyGC_Head 申请了空间, 并且为之在container对象之前. 所以对于 PyListObject , PyDictObject 等对象内存分布就如下:

PyGC_Head
PyObject_HEAD
container obj

在可收集的container对象的内存分布中, 内存分为三个部分, 第一块是用于垃圾收集机制, 第二块是 PyObject_HEAD, 第三块才是数据container对象自身的数据, 这部分既可以是PyDictObject, 也可以是PyListObject.

在PyGC_Head部分, 除了用来建立双向链表的指针外, 还有一个 gc_refs , 这个值被初始化为 GC_UNTRACKED . 这个变量对于垃圾收集的运行至关重要. 当垃圾收集机制运行期间, 我们需要在可收集的container对象和PyGC_Head部分和PyObject_HEAD来回转换. 某个时候, 我们持有一个对象A的PyObject_HEAD的地址, 但是我们需要根据此地址获得A的PyGC_Head地址; 而在某个时候, 我们又需要进行这一动作的逆运算. 是不是立马想到写个宏来计算呢:

[gcmodule.c]
#define AS_GC(o) ((PyGC_Head *)(o)-1)
#define FROM_GC(g) ((PyObject *)(((PyGC_Head *)g)+1))

[objimpl.h]
#define _Py_AS_GC(o) ((PyGC_Head *)(o)-1)

分代的垃圾收集

研究表明, 无论使用哪种语言开发, 无论开发的是何种类型, 何种规模的程序, 都存在一点相同之处, 即一定比例的内存块的生存周期都比较短, 通常是几百万调机制指令的时间, 而剩下的内存块, 其生存周期会比较长, 甚至会从程序开始一直持续到程序结束. 这个比例在80%~98%之间.

所以向 标记--清除 这样的垃圾收集所带来的额外操作实际上与系统中总的内存块数量是相关的, 当需要回收的内存块越多, 垃圾检测带来的额外操作就越多, 而来及回收带来的额外操作就越少.

为了是垃圾收集的效率提高, 基于这个统计规律, 我们就采用一种以空间换时间的策略.

这种策略的思想是: 将系统中的所有内存块根据其存活时间划分为不同的集合, 每一个集合就称为一个 "代" , 垃圾收集的频率随着"代"的存活时间的增大而减小, 也就是说, 获得越长的对象, 就越可能不是垃圾, 就应该越少去收集. 那么这个存活时间是如何来衡量的呢, 通常是利用经过了几次垃圾收集动作来衡量, 如果一个对象经过的垃圾收集次数越多, 那么显然, 其存活时间久越长.

当某些内存块M经过了3次垃圾收集的洗礼依然存活, 我们就将M划到一个集合A中去, 而新分配的内存都划到集合B中去. 当垃圾收集开始工作时, 大多数情况下都只对集合B进行垃圾回收, 而对于A的回收要等到过了比较长的时候才进行, 这就使得垃圾收集需要处理的内存变少了, 效率则得到提高. B中的内存经过几次收集后, 也会有一部分内存被转移到A中. 而A中确实也会存在一些垃圾, 但这些垃圾的回收因为这种分代机制会被延迟. 这就是我们所说的以空间换时间的策略.

这个"代" 是怎么定义的呢, 其实, 这也是一个链表, 所有属于同一"代"的内存块都链在同一个链表中.

[gcmodule.c]
struct gc_generation {
    PyGC_Head head;
    int threshold; /* collection threshold */
    int count; /* count of allocations or collections of younger
                  generations */
};

在python中, 总共有三个 "代" .

[gcmodule.c]
#define NUM_GENERATIONS 3
#define GEN_HEAD(n) (&generations[n].head)
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);

_PyGC_generation0 就是指向第0代的快捷变量.

对于每一个 gc_generation , 其中count记录了当前这条可收集对象链表中一共有多少个可收集的对象. threshold记录了该条可以收集对象链表中最多可容纳多少个可收集对象, 从python的实现代码中,可以发现, 第0代最多可以容纳700个container对象, 一但第0代内存链表的count超过700, 就会立刻触发垃圾回收机制.

[gcmodule.c]
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)
                continue;
            n = collect_with_callback(i);
            break;
        }
    }
    return n;
}

python 中的标记--清除方法

前面我们提到, python采用了三代的分代收集机制, 如果当前收集的是第一代, 那么在开始垃圾收集之前, python会将比其更年轻的所有带的内存链表整个地连接到第一代链表后, 这个操作是通过 gc_list_merge 实现的.

[gcmodule.c]
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);
}

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

在我们的例子中, from就是第0代, to就是第1代. 此后的 标记--清除 算法就将在merge之后的那一条内存链表上进行.

20170905230651.png

寻找 root Object 集合

为了使用 标记--清除 算法, 按照前面对垃圾手机算法的一般性描述, 首先我们需要寻找处root object集合. 那么 那些container对象应该属于root object呢?

换个角度来思考, 前面提到, root Object是不能被删除的对象. 也就是说, 有可收集对象外部某个引用在引用这个对象, 删除这个对象会导致错误的行为.

如果两个对象的引用计数都为1, 但他们之间是循环引用的, 那么这两个对象都需要被回收, 也就是说, 虽然他们引用计数表现为非0, 但实际引用计数为0, 这里我们提出了 有效引用数 的概念, 为了从引用计数获得有效的引用计数, 必须将其循环引用的影响去除, 也就是说, 将环从引用中摘除, 具体的实现就是两个对象各自引用计数都减去1. 这样一来, 两个对象的引用计数都成为了0. 使有效引用计数现出来真身.

那么如果使两个对象的引用计数都减1呢. 很简单, 假设这两个对象A, B. 我们从A出发, 因为它有一个对B的引用, 则将B的引用计数减1; 然后顺着引用达到B, 因为B有一个对A的引用, 同样将A的引用减1, 这样, 就完成了循环引用对象环的摘除.

但是这样就引出另一个问题, 如果A和B之间并不构成环呢, 若B中没有A的引用, 显然 B就被错误的减少了1, 这将导致在某个时刻出现对C的悬空引用. 这种情况就要求我们进行恢复. 但这样会时维护引用计数性能慢一倍. 有没有更好的做法.

我们并不改动真实的引用计数, 而是改动引用计数的副本. 对于副本无论做任何的改动, 都不会影响到对象生命周期的维护, 以为这个副本的唯一作用就是寻找root obejct 集合. 这个副本就是 PyGC_Head 中的 gc.gc_ref . 在垃圾手机的第一步, 就是遍历可手机对象链表, 将每个对象的 gc.gc_ref值设置为其ob_refcnt值.

[gcmodule.c]
static void
update_refs(PyGC_Head *containers)
{
    PyGC_Head *gc = containers->gc.gc_next;
    for (; gc != containers; gc = gc->gc.gc_next) {
        _PyGCHead_SET_REFS(gc, Py_REFCNT(FROM_GC(gc)));
    }
}

接下来的动作就是将环引用从引用中摘除.

[gcmodule.c]
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操作中. 来看看dict对象所指定的 tp_traverse 动作:

[dictobject.c]
PyTypeObject PyDict_Type = {
    ...
    dict_traverse,                              /* tp_traverse */
    ...
}

static int dict_traverse(PyObject *op, visitproc visit, void *arg)
{
    PyDictObject *mp = (PyDictObject *)op;
    PyDictKeysObject *keys = mp->ma_keys;
    PyDictKeyEntry *entries = DK_ENTRIES(keys);
    Py_ssize_t i, n = keys->dk_nentries;

    if (keys->dk_lookup == lookdict) {
        for (i = 0; i < n; i++) {
            if (entries[i].me_value != NULL) {
                Py_VISIT(entries[i].me_value);
                Py_VISIT(entries[i].me_key);
            }
        }
    }
    else {
        if (mp->ma_values != NULL) {
            for (i = 0; i < n; i++) {
                Py_VISIT(mp->ma_values[i]);
            }
        }
        else {
            for (i = 0; i < n; i++) {
                Py_VISIT(entries[i].me_value);
            }
        }
    }
    return 0;
}

对于dict中所有键和所有值都有回调函数, 即 visit_decref 中传递过来的visit_dicref :

[gcmodule.c]
static int visit_decref(PyObject *op, void *data)
{
    assert(op != NULL);
    if (PyObject_IS_GC(op)) {
        PyGC_Head *gc = AS_GC(op);
        if (_PyGCHead_REFS(gc) > 0)
            _PyGCHead_DECREF(gc);
    }
    return 0;
}

在完成了 subtract_refs 之后, 可手机对象的链表中所有container对象之间的引用都被摘除了. 这是有一些container对象的PyGC_Head.gc.gc_ref还不为0, 这就意味着存在这些对象的外部引用, 这些对象就是开始标记的 root object集合.

图表示经过 upeate_refssubtract_refs两步处理所得到的root Object集合.

垃圾标记

成果寻找到root object集合后, 我们就可以从他们出发, 沿着引用链, 一个接一个地标记不能回收的内存, 由于root object中的对象是不能回收的, 因此, 被这些对象直接或间接引用的对象也是不能回收的. 在从root object出发之前, 我们首先将现在的内存表一分为二, 一条链表中维护root object集合, 成为root链表; 而另一个链表维护剩下的对象, 成为 unreachable 链表. 虽然成为不可达到链表, 但其中可能存在被root表链表中对象直接或者间接引用的对象. 这些对象也是不能回收的. 一旦在编辑过程中, 发现了这些对象, 就将其从unreachable链表中移到root链表中; 当完成标记后, unreachable链表就是名副其实的垃圾垃圾对象了, 接下来的垃圾回收只需限制在unreachable链表中即可.

为此, python使用 move_unreachable 完成从unreachable表到root表的划分:

[gcmodule.c]
static void
move_unreachable(PyGC_Head *young, PyGC_Head *unreachable)
{
    PyGC_Head *gc = young->gc.gc_next;

    while (gc != young) {
        PyGC_Head *next;
        // 对于root object , 设置其gc_refs为GC_REACHABLE标志
        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);
            (void) traverse(op,
                            (visitproc)visit_reachable,
                            (void *)young);
            next = gc->gc.gc_next;
            if (PyTuple_CheckExact(op)) {
                _PyTuple_MaybeUntrack(op);
            }
        }
        else {// 对非root对象, 迁移到unreachable链表
            next = gc->gc.gc_next;
            gc_list_move(gc, unreachable);
            _PyGCHead_SET_REFS(gc, GC_TENTATIVELY_UNREACHABLE);
        }
        gc = next;
    }
}

垃圾回收

要回收 unreachable 链表中的垃圾对象, 在回收之前, 已经打破对象间的循环引用, 到回收这步时, unreachable表中的每一个对象的ob_refcnt都是0, 引发对象的销毁:

[gcmodule.c]
static int gc_list_is_empty(PyGC_Head *list)
{
    return (list->gc.gc_next == list);
}

static void delete_garbage(PyGC_Head *collectable, PyGC_Head *old)
{
    inquiry clear;

    while (!gc_list_is_empty(collectable)) {
        PyGC_Head *gc = collectable->gc.gc_next;
        PyObject *op = FROM_GC(gc);

        if (debug & DEBUG_SAVEALL) {
            PyList_Append(garbage, op);
        }
        else {
            if ((clear = Py_TYPE(op)->tp_clear) != NULL) {
                Py_INCREF(op);
                clear(op);
                Py_DECREF(op);
            }
        }
        if (collectable->gc.gc_next == gc) {
            gc_list_move(gc, old);
            _PyGCHead_SET_REFS(gc, GC_REACHABLE);
        }
    }
}

清理的动作交个各个类型的tp_clear来完成, clear = Py_TYPE(op)->tp_clear , 然后调用回调函数 clear(op); .

垃圾收集全景

到此我们就分析完了python中的垃圾收集机制和垃圾回收了. 垃圾收集的入口, 就是 collect . 代码不贴了, 在collect函数中, 还有对python中弱引用(weakref)的处理.

python的垃圾收集机制完全是为了处理循环引用而设计的, , 被垃圾收集监控的对象并非只有垃圾收集机制才能回收, 正常的引用计数就能销毁一个纳入垃圾收集机制监控的对象.

python中的 gc 模块

python通过gc模块为程序员提供了观察和手动使用gc机制的接口, 这一节, 我们通过gc模块进行一些观察, 以加深对垃圾收集机制的理解.

import gc
class A(object):
    pass

class B(object):
    pass
gc.set_debug(gc.DEBUG_STATS | gc.DEBUG_LEAK)
a = A()
b = B()
gc.collect()
######### output:
gc: collecting generation 2...
gc: objects in each generation: 299 1527 4971
gc: done, 0.0000s elapsed
gc: collecting generation 2...
gc: objects in each generation: 1 0 6670
gc: done, 0.0000s elapsed

这是正常的维护对象, 当有循环引用呢:

import gc
class A(object):
    pass

class B(object):
    pass
gc.set_debug(gc.DEBUG_STATS | gc.DEBUG_LEAK)
a = A()
b = B()
a.b = b
b.a = a
del a
del b
gc.collect()
######output:
gc: collecting generation 2...
gc: objects in each generation: 301 1527 4971
gc: collectable <A 0x000001E4337B6080>
gc: collectable <B 0x000001E4337B6048>
gc: collectable <dict 0x000001E4337B1510>
gc: collectable <dict 0x000001E4338867E0>
gc: done, 4 unreachable, 0 uncollectable, 0.0000s elapsed

这种情况下, 引用计数不起作用了, 而垃圾收集机制能正确回收内存. 当我们定义了 __del__ 呢:

import gc
class A(object):
    def __del__(self):
        pass

class B(object):
    def __del__(self):
        pass
gc.set_debug(gc.DEBUG_STATS | gc.DEBUG_LEAK)
a = A()
b = B()
a.b = b
b.a = a
del a
del b
gc.collect()
#### output:
gc: collecting generation 2...
gc: objects in each generation: 307 1527 4971
gc: collectable <A 0x000002151F446080>
gc: collectable <B 0x000002151F50B908>
gc: collectable <dict 0x000002151F441510>
gc: collectable <dict 0x000002151F6C6240>
gc: done, 4 unreachable, 0 uncollectable, 0.0000s elapsed

由于我们执意在类型添加了 __del__ 操作, 所以GC很生气, 后果很严重, 不管是对象a本身(显示中A指的是A类型的a), 就连a对象内维护的 __dict__ 也不能回收. 所以, 没什么事, 千万别轻易自定义 __del__ 操作.


本文由 hongweipeng 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!