0x01 内存管理架构
Python中所有内存机制都有两套实现，由编译符号PYMALLOC_DEBUG控制：
- 符号未被定义时，
Python的内存管理机制只进行正常的内存管理动作；- 符号定义时，使用的是
debug模式下的内存管理机制，除了正常的内存管理动作之外，还会记录许多关于内存的信息，以方便Python在开发时进行调试。我们这里讲的是非
debug模式下的内存管理机制。
Python内存管理机制的层次结构
在Python中，内存管理机制被抽象成一种层次结构，如上图所示。
Layer 0
在最底层，是操作系统提供的内存管理接口，比如C运行时所提供的malloc和free接口，这一层由操作系统实现和管理，Python不能干涉这一层的行为。从这一层往上，剩余三层都是由Python实现并维护的。
Layer 1
第一层是Python基于第零层操作系统的内存管理接口包装而成的，这一层并没有在第零层加入太多动作，其目的仅仅是为Python提供一层统一的raw memory的管理接口（不同平台不同操作系统提供的原始内存申请的接口存在差异，所以Python包装了一层接口，使其与平台无关）。
在Python中，第一层的实现就是一组以PyMem_为前缀的函数族。
// pymem.h
#define PyMem_MALLOC(n) (((n) < 0 || (n) > PY_SSIZE_T_MAX) ? NULL \
: malloc((n) ? (n) : 1))
#define PyMem_REALLOC(p, n) (((n) < 0 || (n) > PY_SSIZE_T_MAX) ? NULL \
: realloc((p), (n) ? (n) : 1))
#define PyMem_FREE free
// object.c
/* Python's malloc wrappers (see pymem.h) */
void *
PyMem_Malloc(size_t nbytes)
{
return PyMem_MALLOC(nbytes);
}
void *
PyMem_Realloc(void *p, size_t nbytes)
{
return PyMem_REALLOC(p, nbytes);
}
void
PyMem_Free(void *p)
{
PyMem_FREE(p);
}
上面代码可以看到，Python提供了类似于C中的malloc、realloc、free的语义。
显然，PyMem_Malloc就是C中的malloc，只是对申请大小为0的内存动作做了特殊处理（强制申请大小为1的内存，从而避免不同操作系统上不同运行时的行为）。
Python为什么会提供宏和函数两套操作内存相关的接口？
Python为了运行效率考虑，使用宏可以减少一次函数调用。但是对于用户来使用C来编写Python的扩展库时，Python提供了函数接口，因为随着Python的发展，宏所代码的代码可能会改变，这样会很危险。
其实在第一层，除了实现分配raw memory之外，也提供了面向Python中类型的内存分配器：
// pymem.h
#define PyMem_New(type, n) \
( ((n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
( (type *) PyMem_Malloc((n) * sizeof(type)) ) )
#define PyMem_NEW(type, n) \
( ((n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
( (type *) PyMem_MALLOC((n) * sizeof(type)) ) )
#define PyMem_Resize(p, type, n) \
( (p) = ((n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
(type *) PyMem_Realloc((p), (n) * sizeof(type)) )
#define PyMem_RESIZE(p, type, n) \
( (p) = ((n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
(type *) PyMem_REALLOC((p), (n) * sizeof(type)) )
#define PyMem_Del PyMem_Free
#define PyMem_DEL PyMem_FREE
对于使用PyMem_New来申请内存，不用像PyMem_MALLOC一样提供具体的内存大小，这里只需要提供类型和数量就可以。
Layer 2
第一层提供的接口功能是有限的。比如我要创建一个PyIntObject对象，还需要进行很多额外的工作（设置对象的类型参数、初始化引用计数等）。为了简化Python自身的开发，Python在第一层的基础上提供了第二层的内存管理接口。
这一层接口以PyObje_为前缀的函数族（又被称为Pymalloc机制），主要提供创建Python对象的接口。
Layer 3
在第二层的内存管理机制之上，对于Python中的一些常用对象（整数、字符串对象等），Python又构建了更高抽象层次的内存管理策略：主要就是对象缓冲池机制。
总结
第一层的内存管理机制仅仅是对malloc的包装，第三层主要是缓冲池机制，针对某个类型中已经讲过。
所以，第二层才真正在Python中发挥巨大作用，同时也是GC的实现之处。接下来重点来看第二层。
0x02 小块空间的内存池
在
Python中，很多时候申请的内存都是小块内存，这些内存申请后很快就会释放， 这些内存不是为了创建对象的，所以没有第三层（对象一级）的内存池机制。这样频繁的
malloc和free操作，导致操作系统频繁在用户态和内核态之间进行切换，影响Python的执行效率。所以在此引入内存池机制，用于管理小块内存的申请和释放。整个小块内存的内存池可以视为一个层次结构：
block、pool、arena和内存池。block、pool、arena在Python中可以找到对应的实体；内存池只是概念上的抽象，表示Python对整个小块内存分配和释放行为的内存管理机制。
Block
在最底层，block是一个确定大小的内存块。在Python中有很多种block，不同种类的block都有不同的内存大小（size class）。为了在当前主流32位和64位平台获得最佳性能，所有block的长度都是8字节对齐的。
//obmalloc.c
#define ALIGNMENT 8 /* must be 2^N */
#define ALIGNMENT_SHIFT 3
#define ALIGNMENT_MASK (ALIGNMENT - 1)
同时Python为block的大小设定了一个上限（Python 2.5是256）。当申请的内存小于这个上限，Python可以使用不同的block来满足内存需求；如果申请的内存大于这个上限，Python会将这个内存申请请求转由第一层的内存管理机制处理（PyMem函数族）。
//obmalloc.c
#define SMALL_REQUEST_THRESHOLD 256
#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
根据SMALL_REQUEST_THRESHOLD和ALIGNMENT的限定，可以得到如下表格：
/*
* 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
* ... ... ...
* 241-248 248 30
* 249-256 256 31
*
* 0, 257 and up: routed to the underlying allocator.
*/
也就是说，当我们申请一个大小为28字节的内存时，实际上PyObject_Malloc从内存池中划给我们的内存是32字节的一个block，从size class index为3的pool中划出。从size class index转换到size class：#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)，从size class转换到size class index：size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT。
在Python中，block只是一个概念上的东西，没有源码与之对应，它仅仅是具有一定大小的内存。但是pool管理着block。
Pool
一组
block的集合称为pool（换句话说，一个pool管理着一堆有固定大小的内存块）。在
Python中，pool管理着一大块内存，通常为一个系统内存页（4KB）。
// obmalloc.c
#define SYSTEM_PAGE_SIZE (4 * 1024)
#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)
#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */
#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK
···
`Python`没有为block提供对应的结构，但是pool有对应的结构pool_header：
```c
// obmalloc.c
/* When you say memory, my mind reasons in terms of (pointers to) blocks */
typedef uchar block;
/* 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仅仅是pool的头部，4KB内存除了pool_header，剩下的都是block集合使用的。
一个pool管理的所有block都具有相同大小的内存（不会管理着50个32字节的block和50个64字节的block），也就是说一个pool和一个size class index联系在一起，即szidx域表示的内容。
// obmalloc.c
#define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK)
#define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header))
typedef struct pool_header *poolp;
typedef uchar block;
void *
PyObject_Malloc(size_t nbytes)
{
block *bp;
poolp pool;
poolp next;
uint size;
......
// pool指向一块4KB的内存
pool->ref.count = 1;
// 设置pool的size class index（也就是指定了block的字节大小，因为size class index和size class是对应的）
pool->szidx = size;
// 将size class index转换为size，比如3转换成32字节
size = INDEX2SIZE(size);
// 跳过用于pool_header的内存，并进行对齐
bp = (block *)pool + POOL_OVERHEAD;
// 实际就是pool->nextoffset = POOL_OVERHEAD+size+size
pool->nextoffset = POOL_OVERHEAD + (size << 1);
pool->maxnextoffset = POOL_SIZE - size;
pool->freeblock = bp + size;
*(block **)(pool->freeblock) = NULL;
return (void *)bp;
}
上面代码就是将一块4KB内存改造成固定字节block的pool，并从pool中取出第一个块block（最后返回的bp就是指向pool中取出的第一块block的指针，也就是说pool中第一块block已经被分配了，所以ref.count赋值为1）。bp实际是一个地址，这个地址之后又将近4KB内存都是可用的，但是可以申请内存的函数只会使用[bp, bp+size]区间内的内存。
pool的4KB内存分布
接下来看看Python在申请block时，pool_header中各个域的变动情况。比如现在申请5块28字节内存，实际上会申请5块32字节的内存。
// obmalloc.c
void *
PyObject_Malloc(size_t nbytes)
{
......
/*
* Reached the end of the free list, try to extend it.
*/
if (pool->nextoffset <= pool->maxnextoffset) {
/* There is room for another block. */
// 有足够的block空间
pool->freeblock = (block*)pool +
pool->nextoffset;
pool->nextoffset += INDEX2SIZE(size);
*(block **)(pool->freeblock) = NULL;
UNLOCK();
return (void *)bp;
}
......
}
freeblock指向的是下一个可用的block的起始地址，所以在申请block的时候，直接返回freeblock的地址即可。接下来对各个域进行调整：nextoffset指向freeblock的下一个位置，maxnextoffset指向pool的最后一个block，定义了pool的边界。这里只需将freeblock和nextoffset向后挪动一个block的位置即可。
Python如何对之前申请然后又释放了的block进行管理？建立
freeblock链表。
释放了block后产生的freeblock链表
// obmalloc.c
// 基于地址p获得离p最近的pool的边界地址
#define POOL_ADDR(P) ((poolp)((uptr)(P) & ~(uptr)POOL_SIZE_MASK))
void
PyObject_Free(void *p)
{
poolp pool;
block *lastfree;
poolp next, prev;
uint size;
if (p == NULL) /* free(NULL) has no effect */
return;
pool = POOL_ADDR(p);
if (Py_ADDRESS_IN_RANGE(p, pool)) {
// 判断p指向的block是否属于pool
assert(pool->ref.count > 0); /* else it was empty */
*(block **)p = lastfree = pool->freeblock;
pool->freeblock = (block *)p;
......
}
}
从freeblock开始，以freeblock=*freeblock的方式遍历这条链表，直到*freeblock为NULL，则表示该链表到尾部了。
所以在一般的block进行分配时，会先分配离散自由的block链表，知道*freeblock为NULL，然后继续分配pool中nextoffset指定的下一块内存，如果nextoffset <= maxnextoffset都不成立，表示该pool的所有block已经分配完。
Arena
一个
pool中的block分配完后，接下来会分配另一个pool的内存，所以在Python中，pool也具有一个集合，也就是arena。
pool的大小默认值是4KB，arena的大小默认值是256KB（使用宏ARENA_SIZE），所以一个arena中可以容纳64（ARENA_SIZE/POOL_SIZE）个pool。
// onmalloc.c
struct arena_object {
uptr address;
block* pool_address;
uint nfreepools;
struct pool_header* freepools;
struct arena_object* nextarena;
struct arena_object* prevarena;
};
arena_object仅仅是一个arena的一部分，就像pool_header是pool的一部分。
"未使用"的arena和"可用"的arena
在
Python中，多个arena_object会构成一个集合，这个集合用数组来维护，数组的首地址由arenas维护。前面讲，
pool_header管理的内存与pool_header是一块连续的内存，而arena_object与其管理的内存是分离的。
pool和arena的内存布局区别
所以，arena_object被申请的时候，它所管理的pool集合内存还没有被申请，即arena_object和pool集合还没有建立联系：
- 当一个
arena的arena_object没有与pool集合建立联系时，这时的arena处于"未使用"状态； - 一旦建立联系，这时的
arena就是"可用"状态；
对于每种状态都有一个arena链表：
- "未使用"的
arena的链表表头是unused_arena_objects，arena之间通过nextarena连接，即单向链表； - "可用"的
arena链表表头是usable_arenas，arena之间通过nextarena和prevarena连接，即双向链表；
arena某时刻状态
申请arena
// obmalloc.c
/* arenas管理着arena_object的集合 */
static struct arena_object* arenas = NULL;
/* 当前arenas管理的arena_object的个数 */
static uint maxarenas = 0;
/* 未使用的*arena_object链表 */
static struct arena_object* unused_arena_objects = NULL;
/* 可用的*arena_object链表 */
static struct arena_object* usable_arenas = NULL;
/* 初始化时需要申请的arena_object的个数 */
#define INITIAL_ARENA_OBJECTS 16
static struct arena_object* new_arena(void)
{
struct arena_object* arenaobj;
uint excess; /* number of bytes above pool alignment */
// 判断是否需要扩充未使用的arena_object链表
if (unused_arena_objects == NULL) {
uint i;
uint numarenas;
size_t nbytes;
// 确定本次需要申请的arena_object的个数，并申请内存
numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;
if (numarenas <= maxarenas)
return NULL; /* overflow */
if (numarenas > PY_SIZE_MAX / sizeof(*arenas))
return NULL; /* overflow */
nbytes = numarenas * sizeof(*arenas);
arenaobj = (struct arena_object *)realloc(arenas, nbytes);
if (arenaobj == NULL)
return NULL;
arenas = arenaobj;
/* 初始化新申请的arena_object，并将其放入unused_arena_objects 链表中 */
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;
}
/* 从unused_arena_objects 链表中取出一个未使用的arena_object */
arenaobj = unused_arena_objects;
unused_arena_objects = arenaobj->nextarena;
assert(arenaobj->address == 0);
/* 申请arena_object管理的内存，即pool集合内存 */
arenaobj->address = (uptr)malloc(ARENA_SIZE);
if (arenaobj->address == 0) {
arenaobj->nextarena = unused_arena_objects;
unused_arena_objects = arenaobj;
return NULL;
}
++narenas_currently_allocated;
/* 设置pool集合的相关信息 */
arenaobj->freepools = NULL;
arenaobj->pool_address = (block*)arenaobj->address;
arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE;
assert(POOL_SIZE * arenaobj->nfreepools == ARENA_SIZE);
/* 将pool的起始地址调整为系统页的边界 */
excess = (uint)(arenaobj->address & POOL_SIZE_MASK);
if (excess != 0) {
--arenaobj->nfreepools;
arenaobj->pool_address += POOL_SIZE - excess;
}
arenaobj->ntotalpools = arenaobj->nfreepools;
return arenaobj;
}
-
Python首先会检查当前unused_arena_objects链表中是否还有"未使用"的arena：- 如果
unused_arena_objects为NULL，则表明目前系统中已经没有"未使用"的arena了，Python将首先扩大系统的arena集合（小块内存内存池），获得新maxarenas后，调用realloc扩大arenas指向的内存，将新申请的arena的address一律设置为0（这个用来标识一个arena是否处于"未使用"状态），然后将unused_arena_objects设置为非NULL - 申请完新
arena或者unused_arena_objects本身就不是NULL的情况下，从unused_arena_objects中抽取出一个arena，然后调整unused_arena_objects使其与抽取出的arena断绝关系。然后Python申请一块大小为ARENA_SIZE（256KB）的内存，赋值给address。
- 如果
内存池
小块内存池模拟图
可用pool缓冲池—usedpools
Python内部默认的小块内存和大块内存的分界点是256字节（SMALL_REQUEST_THRESHOLD符号控制）。当申请小于256字节时，PyObject_Malloc会在内存池中申请内存，否则将使用malloc申请。
Python内部对于arena的个数是否有限制？通常情况下没有对小块内存的内存池大小做任何限制。
Python内部申请内存时，最基本的操作单元是pool而不是arena，因为pool是一个有size概念的内存管理抽象体，一个pool中的block总是有确定的大小（与某个size class index对应），arena没有size这个概念，arena中的pool中存储的block可能是不一样的。
内存池中的pool，不仅有size概念，它还有状态，一个pool在Python运行时，总是处于以下三种状态：
-
used状态：pool中至少有一个block已经使用，并且至少有一个block还未被使用，这种状态的pool受控于usedpools数组； -
full状态：pool中的所有block都已经被使用，这种状态的pool在arena中，但不在arena的freepool链表中；
+empty状态：pool中所有的block都未被使用，这种状态的pool通过其pool_header中的nextpool连接构成一个链表，表头是arena_object中的freepools
某时刻arena中pool集合的可能状态
arena中处于full状态的pool是各自独立的，并没有像其他pool一样会链接称链表。
arena中处于used状态的pool都被置于usedpools的控制之下。当申请内存时，Python会通过usedpools寻找到一块可用的（处于used状态的）pool，从中分配一个block。
pool的初始化
当Python启动后，在usedpools这小块内存空间内存池中，并不存在任何可用的内存（不存在任何可用的pool），这里，Python采用延迟分配的策略，即当我们确实开始申请小块内存时，Python才开始建立这个内存池。
比如，我现在想申请28个字节的内存时，Python实际上将申请32字节的内存。Python首先会根据32字节对应的size class index（3）在usedpools中对应的位置查找，如果发现对应的位置没有链接任何可用的pool，Python会从usable_arena链表中的第一个可用的arena中获得一个pool，将这个pool用作32字节的pool。
如果下次分配的内存时64字节的，那么再从当前可用的arena中取出一个pool用作64字节的pool。
block的释放
对block的释放其实就是将一块block归还给pool。之前将pool是由状态的，释放block时可能会导致状态的变化：
-
used状态转变成empty状态：这种情况，首先Python会将empty状态的pool链入到freepools中去， -
full状态转变成used状态：这种情况比较简单，仅仅是将pool重新链回到usedpools中即可
一般情况下，尽管回收一个block，但是它仍然处于used状态。这种状态下仅仅将block重新放入到自由block链表中，并调整pool中的ref.count这个引用计数。
block释放机制导致的内存泄漏问题？比如我申请了
10x1024x1024个16字节的小内存，也就是我需要申请160MB内存，之前说的Python没有限制内存池的大小，所以用户申请的内存Python会使用arena来满足。申请完成以后，如果以后Python运行时不会再用到160MB这么大的内存，那内存岂不是浪费了。最后在
Python 2.5版本加入了对这个问题的修复。
Python 2.5中，arena可以将自己维护的pool集合释放，返回给操作系统，即arena必须从"可用"状态转为"未使用"状态（这就是必须有这两种状态的原因）。
当Python处理完pool之后，就开始处理arena了，这里分4种情况：
- 如果
arena中所有的pool都是empty的，释放pool集合占用的内存。除了将arena维护的pools集合的内存归还给系统之外，Python还调整了usable_arenas和unused_arena_object链表，将arena状态转到了"未使用"状态。 - 如果之前的
arena中没有empty的pool，那么在usable_arenas链表中就找不到该arena，由于现在arena中有了一个可有使用的pool，所以需要将这个arena链入到usable_arenas链表的表头。 - 若
arena中的empty的pool个数为n，则从usable_arenas开始寻找arena可以插入的位置，将arena插入到usable_arenas。这样做的目的是将empty pool的数量越大的arena排在usable_arenas链表的后边（因为申请block的时候是从表头开始），这样它释放其维护的pool集合的内存的机会就越大，保证了多余的内存会被归还给系统 - 其他情况，不进行任何对
arena的处理
Python中小块内存的内存池全景图
Note：所有的内存都在arenas的掌握之中。
0x03 循环引用的垃圾收集
引用计数与垃圾收集
从广义上说，引用计数也是一种垃圾回收机制：
- 优点：
- 简单
- 实时性（任何内存，一旦没有指向它的引用，就会立即被回收）
- 缺点：
-
执行效率低（引用计数机制带来的额外维护操作与内存分配/释放/引用赋值的次数成正比）
- 主流的垃圾回收机制（标记-清除，停止-复制等），所带来的额外操作基本上只与待回收的内存数量相关
- 为了与引用计数机制搭配，在内存分配和释放上获得更高的效率，
Python因此设计了大量的内存池机制（小块内存池、与各种对象相关的内存池机制等），这样大量使用的面向特定对象的对象内存池机制正式为了竭力弥补引用计数机制的软肋
-
循环引用（与手动进行内存管理出现内存泄漏一样）
- 引入标记-清除和分代收集两种技术来填补该漏洞
-
执行效率低（引用计数机制带来的额外维护操作与内存分配/释放/引用赋值的次数成正比）
三色标记模型
垃圾收集一般包含两个阶段：
- 垃圾检测
垃圾检测是从所有已分配的内存中区别出可以回收的内存和不可回收的内存- 垃圾回收
垃圾回收是使系统重新掌握在垃圾检测阶段所标识出来的可回收的内存块
Python中的垃圾收集是基于三色标记模型完成的，即标记-清除（mark-sweep）方法的实现：
- 寻找根对象（
root object）的集合，所谓root object就是一些全局引用和函数栈中的引用。这些引用所用的对象是不可被删除的。root object集合是垃圾检测动作的起点； - 从
root object集合出发，沿着root object集合中的每一个引用，如果能到达某个对象A，则A称为可达的（reachable），可达的对象也不可被删除。这个阶段就是垃圾检测阶段； - 当垃圾检测阶段结束后，所有对象分为了可达的（
reachable）和不可达的（unreachable）两部分，所有的可达对象都必须给予保留，而所有不可达对象所占用的内存将被回收，这就是垃圾回收阶段。
在垃圾收集动作被激活之前，系统中所分配的所有对象和对象之间的引用组成了一张有向图，其中对象是图中的节点，而对象间的引用是图的边。
垃圾收集过程中某个时刻的多个对象组成的有向图
在有向图的基础上，建立一个三色标注模型，更形象地展示垃圾收集的整个动作：
- 当垃圾收集开始时，假设系统中的所有对象都是不可达的，对应到有向图上，即所有的节点都标注为白色；
- 随后，从垃圾收集动作开始，沿着始于
root object集合中的某个object的引用链，在某时刻到达了对象A，那么A被标记为灰色（灰色表示一个对象是可达的，但是其所包含的引用还没有检查） - 当我们检查了对象
A中所包含的所有引用之后，A被标记为黑色（表示其包含的所有引用已经被检查过了）。
0x04 Python中的垃圾收集
在
Python中，主要的内存管理手段是引用计数机制，而标记-清除（mark-sweep）和分代收集只是为了打破循环引用而引入的补充技术。这就意味着
Python中的垃圾收集只关注可能会产生循环引用的对象（因为引用计数可以自己清理引用为0的垃圾）。可能产生循环引用的对象总是发生在container对象（所谓container对象就是内部可持有其他对象的引用的对象，比如list、dict、class、instance等，PyIntObject、PyStringObject等对象不会持有其他对象的引用）之间。当
Python的垃圾收集机制运行时，只需要去检查这些container对象，带来的开销只依赖于container对象的数量，而非所有对象。为了达到这一点，
Python必须跟踪所创建的每一个container对象，并将这些对象组织到一个集合中，因为只有弄到一个集合里，才能将垃圾收集的动作做限制在这些对象上。
Python采用双向链表将所有container对象组织在一起。
可收集对象链表
之前讲任何一个
Python对象都分为两部分：PyObject_HEAD和对象自身的数据。对于
container对象而言，它必须链入到Python内部的可收集对象链表中去，所以在PyObject_HEAD之前还需要加入PyGC_Head。
// objimp1.h
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;
所以，对于Python所创建的可收集container对象，其内存分布与我们之前所了解的内存布局是不同的。
被垃圾收集机制监控的container对象
可收集container对象内存分为三部分：
- 首先的一块内存用于垃圾收集机制
- 然后紧跟着是
Python中所有对象都会有的PyObject_HEAD - 最后是属于
container对象自身的数据（PyDictObject、PyListObject等）
当垃圾收集机制运行期间，我们需要在一个可收集container对象的PyGC_Head部分和PyObject_HEAD部分来回转换（即某些时候，我们持有一个对象A的PyObject_HEAD的地址，但是我们需要根据此地址获得A的PyGC_Head的地址；而某些时候需要进行相反的操作）。这个转换很容易，减去偏移量就可以了。
我们还需要将创建好的可收集container对象链接到Python内部维护的可收集对象链表中，这样Python垃圾收集机制才能跟踪和处理这个container对象。这个动作在创建container对象的最后一步进行：_PyObject_GC_TRACK()
可收集对象链表
同样的，在销毁这个对象的时候，调用_PyObject_GC_UNTRACK()函数将container对象从该链表中移除。
分代的垃圾收集
研究表明，
80%到98%之间的内存块的生命周期都比较短，通常是几百万条机器指令的寿命，而剩下的内存块，其生命周期会比较长，甚至从程序的开始到结束。像标记-清除（
mark-sweep）这样的垃圾收集所带来的额外操作实际上与系统中总的内存块数量是成正比的。即当系统中使用的内存越少时，整个垃圾收集所带来的额外操作也就越少。为了提高垃圾收集的效率，采用这种以空间换时间的策略。
将系统中的所有内存块根据其存活时间划分为不同的集合，每一个集合称为一个"代"（其实也就是和上面提到的可收集对象链表一样的一个链表），垃圾收集的频率随着"代"的存活时间的增大而减小（即活的时间越长，越不可能是垃圾，所以收集的频率没必要那么高）。
存活时间的衡量：通常是利用经过了几次垃圾收集动作来衡量。
举个栗子，当某个内存块M经过3次垃圾收集还依然存在，我们就将M划到一个集合A中去，而新分配的内存都划到集合B中去。当垃圾收集开始工作时，大多数情况下只对集合B进行回收，而对B的回收周期就会比较长一些。这使得垃圾收集需要处理的内存变少了，效率则得到了提高。可以想见，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 */
};
#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},
};
在Python中，一共分为3"代"。通过一个数组维护了三个gc_generation结构，也就是3条可收集对象链表。
3代内存的控制结构
对于每一个gc_generation来说，count记录了当前这条可收集对象链表中一共有多少个可收集对象。
threshold表示该条可收集对象链表最多可容纳多少个可收集对象。根据代码，第0代链表最多可容纳700个container对象，一旦第0代链表的count超过了700这个极限值，则会立即触发垃圾收集机制。
//gcmodule.c
static Py_ssize_t
collect_generations(void)
{
int i;
Py_ssize_t n = 0;
/* Find the oldest generation (higest numbered) where the count
* exceeds the threshold. 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;
}
}
return n;
}
在_PyObject_GC_Malloc中，虽然由第0代链表的越界触发了垃圾收集，但是Python会对所有"代"的内存链表都进行垃圾收集（当然，只有在某"代"内存链表的count值也发生越界的条件下才进行）。
在collect_generations中，Python将寻找满足count值越界条件中最"老"的那一"代"（也就是数组索引最大的那一"代"），然后回收这"代"对应的内存和所有比它"年轻"的"代"对应的内存。
标记-清除（Mark-Sweep）
如前所述：如果当前收集的是第
1代，，那么在垃圾收集之前，Python会将比其"年轻"的所有"代"的内存链表整个的链接到第1代内存链表之后，通过gc_list_merge实现：
// gcmodule.c
static void
gc_list_init(PyGC_Head *list)
{
list->gc.gc_prev = list;
list->gc.gc_next = list;
}
/* 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过程
此后的标记-清除（Mark-Sweep）算法将在merge之后所得到的那一条内存链表上进行。标记-清除算法是用来打破循环引用的垃圾收集方法。
用于演示标记-清除算法的栗子
寻找Root Object集合
按照之前所讲，需要先找到
root object集合，才能开始垃圾收集机制。
为了从引用计数获得有效引用计数，必须将循环引用的影响去除。具体的实现就是两个对象各自的引用计数值都减去1。这里并不改动真实的引用计数，而是改用引用计数的副本（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) {
assert(gc->gc.gc_refs == GC_REACHABLE);
gc->gc.gc_refs = FROM_GC(gc)->ob_refcnt;
assert(gc->gc.gc_refs != 0);
}
}
接下来就是将环引用从引用中摘除：
// 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 = FROM_GC(gc)->ob_type->tp_traverse;
(void) traverse(FROM_GC(gc),
(visitproc)visit_decref,
NULL);
}
}
其中的traverse是与特定的container相关的，在container的类型对象中定义。一般来说traverse的动作就是遍历container中的每一个引用，然后对引用进行visit_decref操作。
在完成subtract_refs函数之后，可收集对象链表中的container对象的环引用就消除了。此时，还有一些container对象的PyGC_Head.gc.gc_red还不为0（即存在对这些对象的外部引用），这些对象就是开始标记-清除（Mark-Sweep）算法的root object集合。
update_refs和subtract_refs的执行结果
垃圾标记
找到root object集合以后，我们就可以从root object出发，沿着引用链一个一个的标记不能回收的对象，由于root object集合中的对象是不能被回收的，所以被这些对象直接或间接引用的对象也不能被回收。
在从root object出发前，需要将现在的内存链一分为二：一条链表中维护root object集合，称为root链表；另一条链表中维护剩下的对象，称为unreachable链表。
此时的unreachable链表中，可能存在被root链表中的对象直接或间接引用的对象，这些对象是不能被回收的。一旦在标记过程中发现这些对象，就将其从unreachable链表移到root链表中。
当完成标记后，unreachable链表中剩下的对象都是垃圾对象了，接下来的垃圾回收只限制在unreachable链表中。
然后通过move_unreachable函数完成对原始链表的划分：
//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;
if (gc->gc.gc_refs) {
/* 对于root object，设置其gc_refs为GC_REACHABLE标志 */
PyObject *op = FROM_GC(gc);
traverseproc traverse = op->ob_type->tp_traverse;
assert(gc->gc.gc_refs > 0);
gc->gc.gc_refs = GC_REACHABLE;
(void) traverse(op,
(visitproc)visit_reachable,
(void *)young);
next = gc->gc.gc_next;
}
else {
/* 对于非root对象，移到unreachable链表中 */
next = gc->gc.gc_next;
gc_list_move(gc, unreachable);
gc->gc.gc_refs = GC_TENTATIVELY_UNREACHABLE;
}
gc = next;
}
}
/* A traversal callback for move_unreachable. */
static int
visit_reachable(PyObject *op, PyGC_Head *reachable)
{
if (PyObject_IS_GC(op)) {
PyGC_Head *gc = AS_GC(op);
const Py_ssize_t gc_refs = gc->gc.gc_refs;
if (gc_refs == 0) {
/* 对于还没有处理的对象，恢复其gc_refs */
gc->gc.gc_refs = 1;
}
else if (gc_refs == GC_TENTATIVELY_UNREACHABLE) {
/* 对于已经挪到unreachable链表的对象，将其再次挪到原来的链表中 */
gc_list_move(gc, reachable);
gc->gc.gc_refs = 1;
}
else {
assert(gc_refs > 0
|| gc_refs == GC_REACHABLE
|| gc_refs == GC_UNTRACKED);
}
}
return 0;
}
在move_unreachable中，沿着可收集对象链表依次前进，并检查（这里只是简单的遍历，没有从root object集合出发，）PyGC_Head.gc.gc_ref是否为0，为0的话并不能立即断定就是垃圾对象，因为之后可能有root object引用该对象，所以只是暂时标记为GC_TENTATIVELY_UNREACHABLE。
当move_unreachable继续遍历时，遇到一个gc_refs不为0的对象A，即A就是一个root object对象或者从某个root object能够引用到的对象，而A所引用的对象也都是不可回收对象。
然后依次对A中所引用的对象进行visit_reachable：如果A所引用的对象之间被标记为GC_TENTATIVELY_UNREACHABLE，那么现在可以通过A访问到它，说明他是一个不可回收对象，所以Python会将其从unreachable链表中挪到原来的链表，还会将gc_refs设置为1（表示该对象是一个不可回收对象）。
此时得到的reachable链表和unreachable链表
垃圾回收
前面我们已经打破了对象间循环引用。上面只是对gc_refs进行了调整。接下来对ob_refcnt进行调整，直到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);
assert(IS_TENTATIVELY_UNREACHABLE(op));
if (debug & DEBUG_SAVEALL) {
PyList_Append(garbage, op);
}
else {
if ((clear = op->ob_type->tp_clear) != NULL) {
Py_INCREF(op);
clear(op);
Py_DECREF(op);
}
}
if (collectable->gc.gc_next == gc) {
/* object is still alive, move it, it may die later */
gc_list_move(gc, old);
gc->gc.gc_refs = GC_REACHABLE;
}
}
}
其中会调用container对象的类型对象中的tp_clear操作，这个操作会调整container对象中每个引用所用的对象的引用计数值，从而完成打破循环的目的。
在delete_garbage函数中，有一些unreachable链表中的对象会被重新送回到reachable链表中（old参数）。这是由于clear操作成功后，该对象会将自己从垃圾收集机制维护的链表中移除；但是由于某系原因，clear时没有成功，从而没有将自己从collectable链表中移除（表示对象认为自己还不能被销毁，所以Python需要将这些对象返回reachable链表中）。
上例list3和list4回收过程：假设从list3开始，调用其tp_clear（list_clear函数），那么会减少list4的引用计数，list4的引用计数（ob_refcnt）为0，引发对象销毁动作。然后会将list4从可收集对象链表中移除，然后会调整list4引用的对象的引用计数，也就是list3的引用计数，所以list3也会触发对象销毁动作。
垃圾收集全景
Python中实际完成垃圾收集动作的是collect函数：
// gcmodule.c
/* This is the main function. Read this to understand how the
* collection process works. */
static Py_ssize_t
collect(int generation)
{
int i;
Py_ssize_t m = 0; /* # objects collected */
Py_ssize_t n = 0; /* # unreachable objects that couldn't be collected */
PyGC_Head *young; /* the generation we are examining */
PyGC_Head *old; /* next older generation */
PyGC_Head unreachable; /* non-problematic unreachable trash */
PyGC_Head finalizers; /* objects with, & reachable from, __del__ */
PyGC_Head *gc;
double t1 = 0.0;
if (delstr == NULL) {
delstr = PyString_InternFromString("__del__");
if (delstr == NULL)
Py_FatalError("gc couldn't allocate \"__del__\"");
}
/* update collection and allocation counters */
if (generation+1 < NUM_GENERATIONS)
generations[generation+1].count += 1;
for (i = 0; i <= generation; i++)
generations[i].count = 0;
/* 将比当前处理的"代"年轻的"代"的链表合并到当前"代"中 */
for (i = 0; i < generation; i++) {
gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
}
/* handy references */
young = GEN_HEAD(generation);
if (generation < NUM_GENERATIONS-1)
old = GEN_HEAD(generation+1);
else
old = young;
// 在待处理链表上进行打破循环的模拟，寻找root obnject
update_refs(young);
subtract_refs(young);
// 将待处理的链表中的unreachable object转移到unreachable链表中
// 处理完成后，当前代中只剩下reachable object了
gc_list_init(&unreachable);
move_unreachable(young, &unreachable);
// 如果可能将当前代中的reachable object合并到更老的代中
if (young != old)
gc_list_merge(young, old);
// 对于unreachable链表中的对象，如果带有__del__函数，则不能安全的回收，需要将这些对象收集到finalizers链表中，因此，这些对象引用的对象也不能回收，也需要放入finalizers链表中
gc_list_init(&finalizers);
move_finalizers(&unreachable, &finalizers);
move_finalizer_reachable(&finalizers);
// 处理弱引用，如果可能，调用弱引用中注册的callback操作
m += handle_weakrefs(&unreachable, old);
// 对unreachable链表上的对象进行垃圾回收操作
delete_garbage(&unreachable, old);
// 将含有__del__操作的实例对象收集到Python内部维护的名为garbage的链表中，同时将finalizers链表中所有对象加到old链表中。
(void)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");
}
return n+m;
}
需要注意：Python的垃圾收集机制完全是为了处理循环引用而设计的。
几乎所有的对象都会调用PyObject_GC_New，将其加入到垃圾收集机制的监控中。但是，被垃圾收集机制监控的对象也可以通过正常的引用计数降为0时进行销毁（并非只有垃圾收集机制才能回收）。
虽然很多对象挂在垃圾收集机制监控的链表上，但是实际上更多时候都是依靠引用计数机制在维护这些对象，只有对循环引用（引用计数机制无法解决），垃圾收集机制才会起作用。
事实上，对于循环引用之外的对象，垃圾收集机制无能为力。初次之外还有两种情况：不是循环引用但引用计数不为0的情况；引用计数为0的情况。引用计数为0的情况下，对象会被自动回收。所以垃圾回收能且只能处理循环引用中的对象。
gc模块
Python通过gc模块为程序员提供了观察和手动使用gc机制的接口。
总结
尽管Python采用了最经典也是最土的引用计数来作为自动内存管理的方案，但是Python采用了多种方式来弥补引用计数的不足（内存池、标记-清除）。虽然引用计数存在需要花费额外的内存维护引用计数值得缺点，但是这点开销在现在这个年代还是值得的，另外引用计数还将垃圾收集的开销分摊在了运行时整个过程中，而不是某个时刻点。
欢迎关注微信公众号（coder0x00）或扫描下方二维码关注，我们将持续搜寻程序员必备基础技能包提供给大家。
网友评论