| 作者: | dai.zz.flora@gmail.com |
|---|
注解
本文的目的是对Python的垃圾回收机制做一个全景式的描述。 宗旨是一、对读者阅读Python源码起一个指导作用。二、尽量从细节中脱离出来，抽象其大体骨架。 关于Python垃圾回收的一些原始构思见 [1]
Python包含一个比较轻量级的垃圾回收器，其主要代码分布gcmodule.c(主要负责分代垃圾回收)和obmalloc.c(主要负责引用计数垃圾回收)这两个文件中。几个主要关键的技术分别是
引用计数
大多数对象的资源释放都通过引用计数来实现。当对象被引用(包括被设置为属性值、被添加到各式容器中等等)时，引用计数增长；当取消引用时， 引用计数减少；引用计数为0时，对象被释放。这里在python语言级别所用的引用，取消引用均由Python本身来完成；而在用C写扩展时，上述两种 操作由开发人员完成。
标记清除(mark and sweep)
大多数情况下，引用计数可以很好地工作，但考虑到可能存在下面这种代码，造成循环引用
1 2 3 4 | if something
l = [] # l.ref_count = 1
l.append(l) # l.ref_count = 2
do something;# l.ref_count = 1
|
因此引入标记清除的机制，标记即从根节点开始标记其直接或间接引用的子对象，清除即释放所有未被引用的对象
分代垃圾回收
分代垃圾回收是现代垃圾回收器的基本特性，主要思路是存活越久的对象，越少对其进行垃圾回收扫描，以便提高性能。
对象链表
在Python中，所有对象会被添加维护到对象链表中，每一代对象均由一个自己的链表来维护。
python对象头引用计数:
每个PyObject对象都会包含一个PyObject_HEAD的结构，其在Python 2.7.3版本中的定义如下
其中 Py_ssize_t ob_refcnt 标示的被引用的次数
可被垃圾回收对象结构 :
当一个PyObject对象在其类型声明中指定了 Py_TPFLAGS_HAVE_GC 则该对象初始化时系统自动在对象内存空间之前分配一个 PyGC_Head 的结构
1 2 3 4 5 6 7 8 | 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 */
} PyGC_Head;
|
其中 Py_ssize_t gc_refs; 会在之后的垃圾回收的标记中起到关键租用
可被垃圾回收对象链表 :
从上面 PyGC_Head 结构中可以看出，所有的可被垃圾回收对象由 gc_next 和 gc_head 链接起来，形成一个链表
分代 :
Python程序启动时会根据 NUM_GENERATIONS 分配若干代垃圾回收空间。每个空间均由一个可被回收对象链表组成。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /*** Global GC state ***/
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},
};
PyGC_Head *_PyGC_generation0 = GEN_HEAD(0);
|
在上面的代码中 gc_generation 为分代的数据结构，其内容包含阀值( threshold ）和被回收的次数 ( count )。随后的全局初始化代码会自动 生成一个不跟随对象空间的 PyGC_Head 结构，其prev和next（通过调用 GEN_HEAD 宏）都指向自己，由此之后的插入都会使得该链表成一个环状， 在今后的遍历中，以该头为开始，且以该头为结束。
- 1.根据 PyTypeObject 信息计算所需内存空间，申请内存空间，如果有必要的话，申请GC头。
- 2.根据 PyTypeObject 调用用户定义申请空间流程，并调用。
- 3.初始化通用属性值，包括引用计数。
- 4.调用 PyTypeObject 自定义的 init 函数，传入初始化参数，进行初始化。
- 5.加入GC链表
- 6.返回结果.
伪代码: 伪代码根据具体实现代码进行了抽象，部分流程与实际代码对比有差别，仅供参考
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | PyObject* obj;
/*1.Get allocated size*/
int size = _PyObject_VAR_SIZE(type, nitems+1);
if (PyType_IS_GC(type))/*是否需要垃圾回收*/
obj = _PyObject_GC_Malloc(size);
else
obj = (PyObject *)PyObject_MALLOC(size);
/*2.Call custom defined new*/
type->tp_new(obj);
/*3.Call PyObject_Init*/
obj->obj_type = type;
obj->obj_refcnt = 1;
/*4.call custom define init*/
type->tp_init(obj,args);
/*5.gc track*/
if (PyType_IS_GC(type))
_PyObject_GC_TRACK(obj);
/*6.return*/
return obj;
|
- 1.根据 PyTypeObject 自定义方法，清除对属性对象的引用
- 2.从GC链表中删除自身
- 3.释放各种私有属性资源
- 4.释放对象
伪代码:
1 2 3 4 5 6 7 8 9 10 11 12 | /*1.clear reference*/
type->tp_clear(obj);
/*2.untrack*/
if (PyType_IS_GC(type))
_PyObject_GC_UNTRACK(obj);
/*3.free private resource*/
free(obj->private_fields);
/*4.free*/
free(obj);
|
- 1.引用计数减1
- 2.判断引用计数是否为0，为0则调用对象销毁方法
伪代码:
1 2 3 | if(obj->obj_refcnt--!=0){
type->dealloc(obj);
}
|
- 1.从最老的代开始倒序遍历所有代
- 2.判断本代对象数量是否超过阀值，如果超过则进行下列回收操作
- 3.合并本代所有比本代更年轻的代，
- 4.找到根节点
- 5.标记不可到达对象
- 6.将可到达对象加入到更老的代
- 7.清除不可到达对象
伪代码:
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 | static Py_ssize_t
collect_generations(void)
{
int i;
/* 1.Find the oldest generation (highest numbered) where the count
* exceeds the threshold.
* 2. Objects in the that generation and
* generations younger than it will be collected.*/
for (i = NUM_GENERATIONS-1; i >= 0; i--) {
if (generations[i].count > generations[i].threshold) {
n = collect(i);
break;
}
}
}
static Py_ssize_t
collect(int generation)
{
int i;
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head *unreachable; /* non-problematic unreachable trash */
/*3.merge younger generations with one we are currently collecting*/
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
}
young = GEN_HEAD(generation);
old = GEN_HEAD(generation<NUM_GENERATIONS-1?generation+1:generation);
/*4.find roots*/
find_and_mark_roots(young)
/*5.mark and move unreachable,rest object in young is reachable*/
move_unreachable(young, unreachable);
/*6.merge young to old*/
gc_list_merge(young, old);
/*7.delete garbage*/
delete_garbage(unreachable);
}
|
标记清除的第一个关键点如何找到本代中所有对象的根对象，Python里利用了引用计数来计算根对象。原理是消除本对象链表中对象之间的引用计数， 如果还有对象的引用计数不为0的话，说明该对象有来自于对象链表之外的引用，则认为该对象是该对象链表中所有其他对象的根对象。
Python垃圾回收标记工作有如下几个关键点
标记根对象的引用对象为可到达对象
如果发现根节点的引用对象被错认为不可达到对象，将其重新加到可到达对象链表末尾等待标记操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | PyGC_Head *unreachable;
PyGC_Head *containers;
/*遍历*/
for(PyGC_Head *gc in containers){
if(gc->gc.gc_refs>0){/*根节点*/
for(PyObject* direct_child in parent){
if(AS_GC(direct_child)->gc_refs = GC_TENTATIVELY_UNREACHABLE){
gc_list_move(gc, containers);
}
/*减去该对象对其直接引用对象的引用计数*/
AS_GC(direct_child)->gc_refs = 1;
}
}
else {
gc_list_move(gc,unreachable);
gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
}
}
PyGC_Head* reachable = container;
|
由于采用链表，因此此项工作只用将新生代的链表头修改为老年代的最后节点即可
任何PyObject对象在实现时会定义其类型描述 PyTypeObject ，其中要实现 tp_traverse 方法。 当需要对该对象的引用对象进行访问时，会采用Visit模式调用 tp_traverse 方法，由 tp_traverse 的实现来决定访问哪些引用对象。 至于如何对引用对象进行操作（例如上面的减去引用计数），则由 tp_traverse 的函数指针参数 visitproc 来决定。一般 tp_traverse 的实现参照如下模式：
| [1] | Python垃圾回收的一些原始构思：http://www.arctrix.com/nas/python/gc/ |
| [2] | (1, 2) Python对象创建和销毁的C语言API的描述: http://docs.python.org/2/c-api/allocation.html |
| [3] | PyTypeObject的相关C语言API的描述：http://docs.python.org/2/c-api/type.html |
| [4] | 引用计数相关函数：http://docs.python.org/2/c-api/refcounting.html |