= Python垃圾回收算法描述  --解读PythonGC.leo =
                               --- by [[HuangYi]]

我是个懒人啊，老早就研究过一小点gc，但是一看c语言代码就郁闷了。

今天下午把一直想试试的leo弄下来玩，顺便下下来pythonGC.leo，一会就把整个脉络弄清楚了，leo在阅读复杂代码方面确实不错，其他的好处，挖掘中...，呵呵

如果对一些gc基本不了解，建议先看我以前写的[[http://codeplayer.blogbus.com/logs/2006/01/1864297.html|一篇blog]]，开始了：

{{{
#!cplusplus

// 这个函数最关键，阅读这个函数能够帮助理解收集工作大致是如何进行的

static long
collect(PyGC_Head *young, PyGC_Head *old)
{
/*young是当前收集的一代，剩下的对象也就是还有用的对象留下来放到old这一代*/
 long n = 0;
 long m = 0;
 PyGC_Head reachable;
 PyGC_Head unreachable;
 PyGC_Head finalizers;
 PyGC_Head *gc;

 if (debug & DEBUG_STATS) {
  PySys_WriteStderr(
   "gc: collecting generation %d...\n"
   "gc: objects in each generation: %ld %ld %ld\n",
   generation,
   gc_list_size(&_PyGC_generation0),
   gc_list_size(&generation1),
   gc_list_size(&generation2));
 }

 /* 使用 ob_refcnt 和 gc_refs, 计算容器集合中哪些对象
  * 从该集合外部可达的 (比如考虑了容器内部所有引用
  * 之后，refcount仍然大于0的) */
 update_refs(young);
 subtract_refs(young);

 /* 将所有从外部可达的对象移动到
  * reachable 集合(ie. gc_refs > 0).  然后, 
  * 移动所有从reachable集合中的对象可达的对象
  */
 gc_list_init(&reachable);
 move_roots(young, &reachable);
 move_root_reachable(&reachable);

 /* 将不可达的对象移动到临时列表, 
  * 在这开始就可以分配新对象了 */
 gc_list_init(&unreachable);
 gc_list_move(young, &unreachable);

 /* 将可达的对象移动到下一代 */
 gc_list_merge(&reachable, old);

 /* 移动从finalizers可达的对象, 我们还不能安全的删除他们
  * .  Python程序员注意不要去创建这样的东西。
  * 对Python来说 finalizers 就是拥有 __del__ 方法的对象实例. */
 gc_list_init(&finalizers);
 move_finalizers(&unreachable, &finalizers);
 move_finalizer_reachable(&finalizers);

 /* 收集已发现的可回收的对象的统计数据，
  * 然后打印调试信息 */
 for (gc = unreachable.gc.gc_next; gc != &unreachable;
   gc = gc->gc.gc_next) {
  m++;
  if (debug & DEBUG_COLLECTABLE) {
   debug_cycle("collectable", FROM_GC(gc));
  }
 }
 /* 对每个可回收的对象调用tp_clear.  它可以打破引用循环
  * .也可能导致一些finalizer对象被释放*/
 delete_garbage(&unreachable, old);

 /* 收集不可回收对象的统计数据。
  * 打印调试信息. */
 for (gc = finalizers.gc.gc_next; gc != &finalizers;
   gc = gc->gc.gc_next) {
  n++;
  if (debug & DEBUG_UNCOLLECTABLE) {
   debug_cycle("uncollectable", FROM_GC(gc));
  }
 }
 if (debug & DEBUG_STATS) {
  if (m == 0 && n == 0) {
   PySys_WriteStderr("gc: done.\n");
  }
  else {
   PySys_WriteStderr(
       "gc: done, %ld unreachable, %ld uncollectable.\n",
       n+m, n);
  }
 }

 /* 将finalizers加到一个可达的 Python 垃圾列表
  * 程序员必须处理这个问题，如果他们非要创建这种结构的话. */
 handle_finalizers(&finalizers, old);

 if (PyErr_Occurred()) {
  if (gc_str == NULL) {
      gc_str = PyString_FromString("garbage collection");
  }
  PyErr_WriteUnraisable(gc_str);
  Py_FatalError("unexpected exception during garbage collection");
 }
 allocated = 0;
 return n+m;
}
}}}

注释够清晰吧(可能翻译有点烂，受不了的话就赶紧去下个leo玩吧)
下面一段是分代机制：

{{{
#!cplusplus
static long
collect_generations(void)
{
/* static就相当于是全局变量了
 * collections0的意思就是第0代收集了多少次了
 * threshold1的意思就是第0代需要收集多少次才开始收集第1代
 * 这里可以先告诉大家threshold1=threshold2=10
 * 中心思想就是：从0代开始收集，10次之后收集第1代，
 * 又10次之后收集第2代，收集一次后回到第0代
 */
 static long collections0 = 0;
 static long collections1 = 0;
 long n = 0;


 if (collections1 > threshold2) {
  generation = 2;
  gc_list_merge(&_PyGC_generation0, &generation2);
  gc_list_merge(&generation1, &generation2);
  if (generation2.gc.gc_next != &generation2) {
   n = collect(&generation2, &generation2);
  }
  collections1 = 0;
 }
 else if (collections0 > threshold1) {
  generation = 1;
  collections1++;
  gc_list_merge(&_PyGC_generation0, &generation1);
  if (generation1.gc.gc_next != &generation1) {
   n = collect(&generation1, &generation2);
  }
  collections0 = 0;
 }
 else {
  generation = 0;
  collections0++;
  if (_PyGC_generation0.gc.gc_next != &_PyGC_generation0) {
   n = collect(&_PyGC_generation0, &generation1);
  }
 }
 return n;
}
}}}

再往上走就是_PyObject_GC_Malloc了，这里大家可以看到垃圾回收是什么条件下触发的。

{{{
#!cplusplus
PyObject *
_PyObject_GC_Malloc(PyTypeObject *tp, int nitems)
{
 PyObject *op;
 const size_t basicsize = _PyObject_VAR_SIZE(tp, nitems);
#ifdef WITH_CYCLE_GC
 const size_t nbytes = sizeof(PyGC_Head) + basicsize;
 PyGC_Head *g = PyObject_MALLOC(nbytes);
 if (g == NULL)
  return (PyObject *)PyErr_NoMemory();
 g->gc.gc_next = NULL;
 allocated++;
 /*
  *allocated是个全局变量，记录从上次回收以来
  *分配的对象的数目，而 threshold0=700
  */
  if (allocated > threshold0 &&
      enabled &&
      threshold0 &&
      !collecting &&
      !PyErr_Occurred()) {
  collecting = 1;
   collect_generations();
  collecting = 0;
 }
 op = FROM_GC(g);
#else
 op = PyObject_MALLOC(basicsize);
 if (op == NULL)
  return (PyObject *)PyErr_NoMemory();

#endif
 return op;
}
}}}

如果还要往上走，就是

{{{
#!cplusplus
PyObject *
_PyObject_GC_New(PyTypeObject *tp)
{
 PyObject *op = _PyObject_GC_Malloc(tp, 0);
 if (op != NULL)
  op = PyObject_INIT(op, tp);
 return op;
}
}}}

了，分配内存然后初始化，所有的对象模型都是一个样。

当然内部还有许多细节了，比如确定一个对象是否可达，处理引用循环，处理finalizers (想了半天还是不知道该怎么翻译这个词) 等等。大家自己用leo看吧，保证越看越爽，哈哈。

 * 感谢分享快乐体验！我也是一直使用Leo 的，如果你感觉说明不清楚，可以截屏来表达哪！？ -- ZoomQuiet