Python 内存管理架构
Object-specific allocators
_____ ______ ______ ________
[int] [ dict ] [ list ] ... [ string ] Python core |
+3 | <----- Object-specific memory -----> | <-- Non-object memory --> |
_______________________________ | |
[Python's object allocator] | |
+2 | ####### Object memory ####### | <------ Internal buffers ------> |
______________________________________________________________ |
[Python's raw memory allocator (PyMem_ API) ] |
+1 | <----- Python memory (under PyMem manager's control) ------> | |
__________________________________________________________________
[Underlying general-purpose allocator (ex: C library malloc) ]
0 | <------ Virtual memory allocated for the python process -------> |
=========================================================================
_______________________________________________________________________
[OS-specific Virtual Memory Manager (VMM) ]
-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> |
__________________________________ __________________________________
[] []
-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> |
Python 层面的内存管理重点在 +2 层，其代码在 obmalloc.c，主要的 API 是 PyObject_Malloc 和 PyObject_Free。
这一层的内存管理主要是对 C 语言提供的内存管理函数进行封装，以兼容不同平台的行为。
不同平台对 malloc(0) 的处理表现不一致，有的平台返回 NULL 以表示错误，有的平台返回一个特殊的指针指向不存在的内存区域。Python 的解决方法是最少分配 1 字节的内存。
这一层的内存管理专门针对 Python 中的对象。
Python 中频繁使用对象，因此必然产生大量的内存分配和释放。为了提高内存分配的效率，Python 采取了内存池的方案，如果要分配对象的内存小于一个预设阈值，那么就从内存池中找出一个合适的 block。
通过使用内存池避免了频繁调用 malloc。
默认的内存阈值是 SMALL_REQUEST_THRESHOLD = 256。
内存池使用的内存管理技术叫做「简单分离存储」，将内存池中的内存按照大小分成不同的块（block），这个大小叫做 size class，相同 size class 的块组织到一个 pool 中。当想要申请内存时，就从 pool 中找出最合适的一个空闲块。
size class 是 8 的倍数，最小的 size class 是 8 字节，接下来依次是 16、24、32、40、...、256。
* For small requests we have the following table:
*
* Request in bytes Size of allocated block Size class idx
* ----------------------------------------------------------------
* 1-8 8 0
* 9-16 16 1
* 17-24 24 2
* 25-32 32 3
* 33-40 40 4
* 41-48 48 5
* 49-56 56 6
* 57-64 64 7
* 65-72 72 8
* ... ... ...
* 497-504 504 62
* 505-512 512 63
*
* 0, SMALL_REQUEST_THRESHOLD + 1 and up: routed to the underlying
* allocator.
*/
/*==========================================================================*/
一个 pool 的大小一般等于虚拟内存页的大小，即 4KB。pool 包含一个 pool 头部和许多的 block，pool 中所有的 block 都是相同大小的。
pool 头部的定义：
// Objects/obmalloc.c
/* Pool for small blocks. */
struct pool_header {
union { block *_padding;
uint count; } ref; /* number of allocated blocks */
block *freeblock; /* pool's free list head */
struct pool_header *nextpool; /* next pool of this size class */
struct pool_header *prevpool; /* previous pool "" */
uint arenaindex; /* index into arenas of base adr */
uint szidx; /* block size class index */
uint nextoffset; /* bytes to virgin block */
uint maxnextoffset; /* largest valid nextoffset */
};pool_header 的大小可能不是 8 字节的整数倍，为了对齐 pool_header 后面会填充一些字节。计算方式如下：
#define POOL_OVERHEAD _Py_SIZE_ROUND_UP(sizeof(struct pool_header), ALIGNMENT)pool 的状态：
-
used
pool 中至少有一个空闲 block，至少有一个已分配的 block。也就是说 pool 中一部分 block 被分配了，还剩下一部分 block 是空闲的。
used 状态的 pool 通过 usedpools 的循环双向链表连接在一起。
-
full
pool 中所有 block 都被分配了。full 状态的 pool 不被任何链表连接，是游离的。
-
empty
pool 中所有 block 都是空闲的。empty 状态的 pool 通过 arena_object 的 freepools 链表连接在一起。
当一个 pool 被初始化时，第一个 block 用于分配，freeblock 指向第二个 block，nextoffset 指向第三个 block，maxnextoffset 指向最后一个 block。当从 pool 中申请新的 block 时，返回 freeblock 指向的 block，然后 freeblock 指向 nextoffset。
如果 pool 中的 block 在将来被释放，那么使 freeblock 指向该 block，并在该 block 中设置一个指针，指向原来的 freeblock。从而 freeblock 指向一个空闲 block 的链表。
#define PTA(x) ((poolp )((uchar *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
#define PT(x) PTA(x), PTA(x)
static poolp usedpools[2 * ((NB_SMALL_SIZE_CLASSES + 7) / 8) * 8] = {
PT(0), PT(1), PT(2), PT(3), PT(4), PT(5), PT(6), PT(7)
#if NB_SMALL_SIZE_CLASSES > 8
, PT(8), PT(9), PT(10), PT(11), PT(12), PT(13), PT(14), PT(15)
#if NB_SMALL_SIZE_CLASSES > 16
, PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23)
#if NB_SMALL_SIZE_CLASSES > 24
, PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31)
#if NB_SMALL_SIZE_CLASSES > 32
, PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39)
#if NB_SMALL_SIZE_CLASSES > 40
, PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47)
#if NB_SMALL_SIZE_CLASSES > 48
, PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55)
#if NB_SMALL_SIZE_CLASSES > 56
, PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63)
#if NB_SMALL_SIZE_CLASSES > 64
#error "NB_SMALL_SIZE_CLASSES should be less than 64"
#endif /* NB_SMALL_SIZE_CLASSES > 64 */
#endif /* NB_SMALL_SIZE_CLASSES > 56 */
#endif /* NB_SMALL_SIZE_CLASSES > 48 */
#endif /* NB_SMALL_SIZE_CLASSES > 40 */
#endif /* NB_SMALL_SIZE_CLASSES > 32 */
#endif /* NB_SMALL_SIZE_CLASSES > 24 */
#endif /* NB_SMALL_SIZE_CLASSES > 16 */
#endif /* NB_SMALL_SIZE_CLASSES > 8 */
};usedpools 是一个非常古怪的数组，usedpools 将所有 used 状态的 pool 组织成一个循环双向链表。usedpools[i + i] 是 size class index 等于 i 的 pool 的循环双向链表的头。
usedpools[i + i] 是一个 poolp 类型的指针，指向一个 pool_header。在上面的初始化代码中，仔细研究可以发现 usedpools[i + i] 其实等于 (uchar *)&(usedpools[i + i]) - 2 * sizeof(block *)，也就是说它指向前面两个元素，考虑到 pool_header 的前面两个字段的长度恰好等于 2 * sizeof(block *)，所以相当于将前面两个元素当作是 pool_header 的前两个字段，将 usedpool[i + i] 和 usedpool[i + i + 1] 当作是 pool_header 的 nextpool 和 prevpool。
一个 arena 包含许多的 pool，arena 的大小等于 256KB。arena 只是一大块内存块，它通过 arena_object 来表示和管理。另外，使用一个数组来保存 arena_object。
arena_object 的定义：
// Objects/obmalloc.c
/* Record keeping for arenas. */
struct arena_object {
/* The address of the arena, as returned by malloc. Note that 0
* will never be returned by a successful malloc, and is used
* here to mark an arena_object that doesn't correspond to an
* allocated arena.
*/
uptr address;
/* Pool-aligned pointer to the next pool to be carved off. */
block* pool_address;
/* The number of available pools in the arena: free pools + never-
* allocated pools.
*/
uint nfreepools;
/* The total number of pools in the arena, whether or not available. */
uint ntotalpools;
/* Singly-linked list of available pools. */
struct pool_header* freepools;
/* Whenever this arena_object is not associated with an allocated
* arena, the nextarena member is used to link all unassociated
* arena_objects in the singly-linked `unused_arena_objects` list.
* The prevarena member is unused in this case.
*
* When this arena_object is associated with an allocated arena
* with at least one available pool, both members are used in the
* doubly-linked `usable_arenas` list, which is maintained in
* increasing order of `nfreepools` values.
*
* Else this arena_object is associated with an allocated arena
* all of whose pools are in use. `nextarena` and `prevarena`
* are both meaningless in this case.
*/
struct arena_object* nextarena;
struct arena_object* prevarena;
};arena_object 有两种状态:
-
unused
此时的 arena_object 没有关联 arena。address 字段等于 0。所有 unused 状态的 arena_object 通过 unused_arena_objects 单向链表连接在一起。
-
usable
此时的 arena_object 关联了一个 arena，address 字段不等于 0。所有 usable 状态的 arena_object 通过 usable_arenas 双向链表连接在一起。
-
full
此时 arena_object 关联的 arena 的空间全部被使用完了，arena_object 从 usable_arenas 链表上分离出来。
usable_arenas 链表是根据 arena_object 的 nfreepools 从小到大排序的，这样排序的目的是为了尽量将快要分配满的 arena_object 耗尽，而将空闲的 arena_object 放到后面。当空闲 arena_object 的 nfreepools 等于 ntotalpools 时，便释放 arena_object 关联的 arena 的内存给操作系统。
当没有可用的 pool 时，new_arena 函数负责分配新的 arena_object，一般是从 unused_arena_objects 链表中取出一个 arena_objecgs。如果 unused_arena_objects 链表用完，那么 new_arena 向操作系统申请新的内存用于新的 arena_object，新的 arena_object 添加到 unused_arena_objects 链表中。
...
if (unused_arena_objects == NULL) {
uint i;
uint numarenas;
size_t nbytes;
/* Double the number of arena objects on each allocation.
* Note that it's possible for `numarenas` to overflow.
*/
numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;
if (numarenas <= maxarenas)
return NULL; /* overflow */
#if SIZEOF_SIZE_T <= SIZEOF_INT
if (numarenas> PY_SIZE_MAX / sizeof(*arenas))
return NULL; /* overflow */
#endif
nbytes = numarenas * sizeof(*arenas);
arenaobj = (struct arena_object *)PyMem_RawRealloc(arenas, nbytes);
if (arenaobj == NULL)
return NULL;
arenas = arenaobj;
/* We might need to fix pointers that were copied. However,
* new_arena only gets called when all the pages in the
* previous arenas are full. Thus, there are *no* pointers
* into the old array. Thus, we don't have to worry about
* invalid pointers. Just to be sure, some asserts:
*/
assert(usable_arenas == NULL);
assert(unused_arena_objects == NULL);
/* Put the new arenas on the unused_arena_objects list. */
for (i = maxarenas; i < numarenas; ++i) {
arenas[i].address = 0; /* mark as unassociated */
arenas[i].nextarena = i < numarenas - 1 ?
&arenas[i+1] : NULL;
}
/* Update globals. */
unused_arena_objects = &arenas[maxarenas];
maxarenas = numarenas;
}
..._PyObject_Alloc 函数负责实际的分配内存的工作。
流程：
-
如果要申请的内存大于
SMALL_REQUEST_THRESHOLD，那么使用 +1 层的PyMem_xxx函数分配内存。 -
计算申请的内存对应的 size class index，如果 usedpools[size class index * 2] 没有可用的 pool，那么从 usable_arenas 链表中取出一个可用的 pool。
-
如果 usable_arenas 等于 NULL，意味着所有 pool 都使用完了。那么调用
new_arena函数分配新的 arena_object。usable_arena 指向新分配的 arena_object，prevarena 和 nextarena 等于 NULL。 -
从 usable_arenas 链表中的第一个 arena_object 中取出一个 pool，如果 pool 等于 NULL，说明这个 arena_object 中的 pool 一直被分配，而还没有被归还过。此时将 pool_address 指向的 poll 分配出去，并设置 pool 的 arenaindex。
-
如果 pool 不等于 NULL，就使用这个 pool。
-
接着 nfreepools 减 1，如果 nfreepools 等于 0，说明这个 arena_object 的 pool 用完了，那么将这个 arena_object 从 usable_arenas 链表移除。
-
需要初始化 pool。例如：
-
将 pool 加入 usedpools[i + i] 的循环双向链表。
-
初始化 pool_header 的 szidx、nextoffset、maxnextoffset 和 freeblocks。
-
-
返回对应的 block。
-
-
如果 usedpools 有可用的 pool，那么从第一个 pool 中取出一个 block 并返回。如果 pool 所有的 block 都分配完了，那么将 pool 移除 usedpools 。
_PyObject_Free 函数负责实际的释放内存的工作。
流程：
-
为了安全考虑，首先检查 block 的地址是否属于内存池。如果不属于内存池，那么使用
PyMem_RawFree函数释放该内存。 -
假设 pool 表示包含该 block 的 pool，将 block 添加到 freeblocks 链表。
-
如果 pool 处于 full 状态，由于释放了一个 block，pool 从 full 变为 used，因此将 pool 添加到 usedpools 链表中。
-
如果 pool 由于释放一个 block 变为 empty 状态，那么：
-
将 pool 从 usedpools 链表中移除。
-
将 pool 添加到 arena_object 的 freepools 链表中。nfreepools 加 1。
-
如果 arena_object 的 nfreepools 等于 ntotalpools，说明 arena_object 的所有的 pool 都是空闲的，因此可以将 arena_object 关联的 arena 内存释放掉，然后将 arena_object 从 usable_arenas 链表中移除，然后加入 unused_arena_objects 链表。
-
如果 arena_object 的 nfreepools 等于 1，说明 arena_object 从 full 变为 usable 状态。将 arena_object 加入 usable_arenas 链表。
-
如果 arena_object 的 nfreepools 属于其它情况，则检查 nfreepools 是否大于下一个 arena_object 的 nfreepools，如果大于则说明 usable_arenas 链表的顺序被破坏了，需要将 arena_object 移到链表后面适当的位置。
-
返回。
-
-
如果 pool 仍处于 used 状态，那么直接返回。
-
usedpools 的结构。
-
freeblock 指针的处理。
-
freepools 指针的处理。
-
arena 中对 pool 地址的对齐和 pool 中对 block 地址的对齐。
-
计算一个指针所属的 pool。
#define POOL_ADDR(P) ((poolp)_Py_ALIGN_DOWN((P), POOL_SIZE)) -
计算一个指针是否属于内存池（arena）。
#define Py_ADDRESS_IN_RANGE(P, POOL) \ ((arenaindex_temp = (POOL)->arenaindex) < maxarenas && \ (uptr)(P) - arenas[arenaindex_temp].address < (uptr)ARENA_SIZE && \ arenas[arenaindex_temp].address != 0)
为了方便，Python 内部对 PyObject_Malloc 函数进行了封装，例如 PyObject_New 等函数。
PyObject *
PyObject_Init(PyObject *op, PyTypeObject *tp)
{
if (op == NULL)
return PyErr_NoMemory();
/* Any changes should be reflected in PyObject_INIT (objimpl.h) */
Py_TYPE(op) = tp;
_Py_NewReference(op);
return op;
}
PyVarObject *
PyObject_InitVar(PyVarObject *op, PyTypeObject *tp, Py_ssize_t size)
{
if (op == NULL)
return (PyVarObject *) PyErr_NoMemory();
/* Any changes should be reflected in PyObject_INIT_VAR */
op->ob_size = size;
Py_TYPE(op) = tp;
_Py_NewReference((PyObject *)op);
return op;
}
PyObject *
_PyObject_New(PyTypeObject *tp)
{
PyObject *op;
op = (PyObject *) PyObject_MALLOC(_PyObject_SIZE(tp));
if (op == NULL)
return PyErr_NoMemory();
return PyObject_INIT(op, tp);
}
PyVarObject *
_PyObject_NewVar(PyTypeObject *tp, Py_ssize_t nitems)
{
PyVarObject *op;
const size_t size = _PyObject_VAR_SIZE(tp, nitems);
op = (PyVarObject *) PyObject_MALLOC(size);
if (op == NULL)
return (PyVarObject *)PyErr_NoMemory();
return PyObject_INIT_VAR(op, tp, nitems);
}指的注意的是 tp->basicsize 和 tp->itemsize。
Python 使用了「简单分离存储」的内存管理技术，将内存池中的 block 按照 size class 规划为不同的大小，size class 是 8 的倍数，最小的 block 等于 8 个字节，相同 size class 的 block 放到一个 pool 中。
block 是内存池中的基本单位，也就是说最少分配一个 block。例如想要申请一块 20 字节的内存，那么 Python 会分配一个 24（size class index = 2）字节的 block，意味着有 4 个字节的浪费。
通过 usedpools 数组管理不同 size class 的 pool，usedpools[i * 2] 指向 size class index 等于 i 的 pool 链表。
当申请内存时，计算内存大小对应的 size class index，然后从 usedpools 中的 pool 取出合适的 block。
当释放内存时，将 block 归还给对应的 pool。
为了管理 pool，使用 arena_object 结构，arena_object 负责分配一个比 pool 更大的内存区域，一般等于 256KB，而 pool 等于 4KB，也就是说 arena_object 分配的内存区域可以容纳 64 个 pool。
arena_object 是内存池中最大的单位，当内存池没有可用的 pool 时，就使用 malloc 系统调用向操作系统申请新的 arena_object，将新申请的内存划入内存池。当 arena_object 中的所有 pool 都被释放后，arena_object 的内存会返回给操作系统。
总的来说，这种内存分配策略优点是分配速度快，减少 malloc 系统调用，缺点是容易造成内部碎片和潜在的内存长期占用，内存池的内存只有在 arena_object 的所有 pool 都被释放后才会归还给操作系统，典型的空间换时间。
这一层的内存管理主要和具体的对象有关，例如内部的整数、列表、字典和字符串对象。
这些内部对象的使用频率非常高，为了避免频繁的分配对象的内存，Python 的做法是为这些对象分配独立的内存池。当需要分配对象时，就从内存池取出一个对象的内存，当释放一个对象时，其内存归还给内存池。其实内存池就是一个简单的数组，数组元素指向对象的内存。指的注意的是，内存池并不保存对象内部指向的数据结构，而是只保存对象本身的结构体。以列表为例，内存池保存列表对象的结构体 listobj，但是不保存列表指向的数组，因为这些数组非常占据内存，而且也不好重复利用。
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 |
| +----------+ | +----------+
| | +---+ +--+ |
| +----------+ | +----------+
| | | | | |
| +----------+ | +----------+
| | | | | |
| +----------+ | +----------+
| |
+----------------------+
为了解决循环引用问题，引入了标记 - 清除垃圾回收机制和分代垃圾回收机制。
标记清除的基本原理是：
-
寻找根对象（root object）的集合，所谓的 root object 即是一些全局引用和函数栈中的引用。这些引用所用的对象是不可被删除的。而这个 root object 集合也是垃圾检测动作的起点。
-
从 root object 集合出发，沿着 root object 集合中的每一个引用，如果能到达某个对象 A，则 A 称为可达的（reachable），可达的对象也不可被删除。这个阶段就是垃圾检测阶段。
-
当垃圾检测阶段结束后，所有的对象分为了可达的和不可达的（unreachable）两部分，所有的可达对象都必须予以保留，而所有的不可达对象所占用的内存将被回收，这就是垃圾回收阶段。
由于只有 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。
-
move_legacy_finalizer_reachable。遍历 finalizers 链表，通过对象的 tp->traverse 方法，将对象引用的其它对象也移到动 finalizers 链表，前提是其它对象在 unreachable 链表上。
-
handle_weakrefs。处理弱引用，这个暂时还没搞懂。
-
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 为例：
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代频繁进行垃圾回收也是毫无意义的。
-
早期的一篇关于 Python GC 的文章：http://www.arctrix.com/nas/python/gc/
-
Python Dev Mail List 上关于 Python GC 实现的讨论：
-
关于优化 Python GC 的 issue：
-
减少 GC 追踪对象的数量，例如只包含不可变对象的元祖可以不用被 GC 追踪。
-