《Python 源码剖析》一些理解以及勘误笔记（3）

以下是本人阅读此书时理解的一些笔记，包含一些影响文义的笔误修正，当然不一定正确，贴出来一起讨论。注：此书剖析的源码是2.5版本，在python.org 可以找到源码。纸质书阅读，pdf 贴图。文章篇幅太长，故切分成3部分，这是第三部分。p316: 初始化线程环境Python 虚拟机运行期间某个时刻整个的运行环境如下图：建立

s1mba

4830人浏览 · 2015-05-09 11:57:27

s1mba · 2015-05-09 11:57:27 发布

以下是本人阅读此书时理解的一些笔记，包含一些影响文义的笔误修正，当然不一定正确，贴出来一起讨论。

注：此书剖析的源码是2.5版本，在python.org 可以找到源码。纸质书阅读，pdf 贴图。

文章篇幅太长，故切分成3部分，这是第三部分。

p316: 初始化线程环境

Python 虚拟机运行期间某个时刻整个的运行环境如下图：

建立联系之后的PyThreadState 对象和 PyInterpreterState 对象的关系如下图：

_PyThreadState_Current 是个全局变量，是当前活动线程对应的 PyThreadState 对象；

interp->modules 指向一个 PyDictObject 对象（module_name, module_object），维护系统所有的module，可能动态添加，为所有PyThreadState 对象所共享；import sys sys.modules or sys.__dict__['modules'] 可以访问到module 集合。同理 interp->builtins 指向 __builtins__.__dict__; interp->sysdict 指向 sys.__dict__;

p320: 系统module 的初始化

在 Python 中，module 通过 PyModuleObject 对象来实现。

 
   C++ Code  
 

1
2
3
4

typedef struct {
PyObject_HEAD
PyObject *md_dict;
} PyModuleObject;

在初始化 __builtin__ 模块时，需要将Python 的内置类型对象塞到 md_dict 中，此外内置函数也需要添加。

如 __builtins__.__dict__['int'] 显示为 <type 'int'>; __builtins__.__dict__['dir] 显示为<built-in function dir>;

系统的 __builtin__ 模块的 name为 '__builtin__ ', 即 __builtins__.__dict__['__name__'] 显示为 '__builtin__ ';

__builtins__.__dict__['__doc__'] 显示为 "Built-in functions, exceptions, .... ";

也可直接 __builtins__.__name__ , __builtins__.__doc__;

这里解释下为什么会出现 '__builtins__'。我们经常做单元测试使用的机制 if __name__ == '__main__' ，表明作为主程序运行的Python 源文件可以被视为名为 __main__ 的 module，当然以 import py 方式加载，则__name__ 不会为 __main__。在初始化 __main__ module 时会将（'__builtins__', __builtin__ module）插入到其 dict 中。也就是说'__builtins__' 是 dict 中的一个 key。比如在命令行下输入 dir() ，输出为 ['__builtins__', '__doc__', '__name__ ']。实际上在激活字节码虚拟机的过程中创建的第一个PyFrameObject 对象，所设置的 local、global、builtin 名字空间都是从__main__ 模块的dict 中得到的，当然在真正开始运行指令时，local or global 会动态增删。

builtin_methods 中每一个函数对应一个 PyMethodDef 结构，会基于它创建一个 PyCFunctionObject 对象，这个对象是Python 对函数指针的包装。

 
   C++ Code  
 

1
2
3
4
5
6
7

struct PyMethodDef {
    const char  *ml_name;   /* The name of the built-in function/method */
    PyCFunction  ml_meth;   /* The C function that implements it */
    int      ml_flags;  /* Combination of METH_xxx flags, which mostly
                   describe the args expected by the C func */
    const char  *ml_doc;    /* The __doc__ attribute, or NULL */
};

 
   C++ Code  
 

1
2
3
4
5
6

typedef struct {
    PyObject_HEAD
    PyMethodDef *m_ml; /* Description of the C function to call */
    PyObject    *m_self; /* Passed as 'self' arg to the C func, can be NULL */
    PyObject    *m_module; /* The __module__ attribute, can be anything */
} PyCFunctionObject;

__builtin__ module 初始化完成后如下图：

在完成了__builtin__ 和 sys 两个模块的设置之后，内存布局如下图：

Python 内部维护了一个全部变量extensions，这个PyDictObject 对象将维护所有已经被Python 加载的module 中的

PyDictObject 的一个备份。当Python 系统的 module 集合中的某个标准扩展module 被删除后不久又被重新加载时，Python 就不需要再次初始化这些module，只需要用extensions 中备份的 PyDictObject 对象来创建一个新的module 即可。这一切基于假设：Python 中的标准扩展module 是不会在运行时动态改变的。实际上Python 内部提供的module 可以分成两类，一类是C 实现的builtin module 如thread，一类是用python 实现的标准库module。

p328:设置搜索路径、site-specific 的 module 搜索路径

sys.path 即 sys.__dict__['path'] 是一个 PyListObject 对象，包含了一组PyStringObject 对象，每一个对象是一个module 的搜索路径。

第三方库路径的添加是 lib/site.py 完成的，在site.py 中完成两个动作：

1. 将 site-packages 路径加入到 sys.path 中。

2. 处理 site-packages 目录下所有.pth 文件中保存的所有路径加入到 sys.path。

完成初始化后的环境如下图所示：

p347: import 机制的黑盒探测

 
   Python Code  
 

1
2
3

# hello.py
a = 1
b = 2

import hello 之后，使用dir() 获得的信息

也就是说，hello module 中的 __builtins__ 符号对应的 dict 正是当前名字空间中 __builtins__ 符号对应的module对象所维护的那个dict 对象。

注意 from hello import a 的情况有所不同：

注意 from hello import * ，如果 hello.py 定义了__all__ = [ ... ]，那么只加载列表里面的符号；当然如果在 __init__.py 定义了 __all__，那么只加载列表中的 module。类似地，import A.tank as Tank 在locals() 中出现的名字是 'Tank'，但还是需要通过 sys.modules['A.tank'] 才能正确访问。

注意：不要从其他模块 import 初始值为None, 而后值一直被修改的符号，此时应该使用函数等方式来传递此符号。因为当前模块中此符号所引用的值可能一直都是None，这取决于初始化顺序。

如果出现了嵌套import 的情况呢？

 
   Python Code  
 

1
2
3
4
5

# usermodule1.py
import usermodule2

# usermodule2.py
import sys

也就是说在每个py 中进行的import 动作并不会影响上一层的名字空间，只是影响各个module 自身的名字空间；但所有import 动作，无论发生在什么时间、什么地点，都会影响到全局module 集合即 sys.modules。图中的 __file__ 是文件路径名。

注意：尽量避免相互引用，这是模块化开发的一条准则。

实际上“动态加载”真实含义是将这个module 以某个符号的形式引入到某个名字空间，del xxx 只是删除了符号，而sys.modules 中仍然维护了xxx 对应的module 对象。如果我们更新了module A 的某个功能实现，可以使用 reload 来更新 sys.modules 中维护的module A 对象，注意：Python 虚拟机在调用reload() 操作更新module 时，只是将新的符号加入到module 中，而不管module 中的先前符号是否已经在源文件中被删除了。

只有在文件夹中有一个特殊的 __init__.py 文件，Python 虚拟机才会认为这是一个合法的package，当Python 虚拟机执行 import A 时，会动态加载目录A 的 __init__.py，除非 __init__.py 中有显式的import 语句，否则只会将package 自身加载到Python，并不会对package 中的module 进行任何动作。

在加载package 下的module 时，比如 A.B.C（多层路径），Python 内部将这个module 的表示视为一个树状的结构。如果 A 在import A.D 时被加载了，那么在 A 对应的PyModuleObject 对象中的dict 中维护着一个 __path__，表示这个 package 的搜索路径，那么接下来对B 的搜索将只在 A.__path__ 中进行，而不在所有Python 搜索路径中执行了（直接 import module 时）。

p362: import 机制的实现

 
   Python Code  
 

1
2
3
4
5
6
7

import sys
import xml.sax # xml/sax.py
from xml import sax
from xml.sax import xmlreader
from sys import path
from sys import path as mypath
import usermodule

如上举例说明 " from A import mod"，尽管 mod 并不在 A 对应的module 对象的名字空间中，但是import 机制能够根据 A 发现 mod，也是合法的。

Python import 机制的起点是builtin module 的 __import__ 操作，也就是 builtin__import__ 函数。

Python 将寻找一切可以作为module的文件，比如subname 来说，Python 将寻找 subname.py、subname.pyc、subname.pyd、subname.pyo、subname.dll（Python 2.5 已不再执行dll 后缀名的文件）。

对于py 文件，Python 虚拟机会先对py 文件进行编译产生PyCodeObject 对象，然后执行了co_code 字节码，即通过执行def、class 等语句创建PyFunctionObject、PyClassObject 等对象，最后得到一个从符号映射到对象的dict，自然也就是所创建的module 对象中维护的那个dict。

import 创建的module 都会被放到全局module 集合 sys.module 中。

p386: 与 module 有关的名字空间问题

 
   Python Code  
 

1
2
3
4
5
6
7
8
9
10
11

# module1.py
import module2

owner = "module1"
module2.show_owner() # "module2"

# module2.py
owner = "module2"
def show_owner():
print owner

在执行 import module2 时，Python 会创建一个新的PyFrameObject 对象，刚开始这个对象中的global 名字空间可能只有 '__builtins__'

、'__doc__'、'__name__' 等符号，随着代码的执行，global名字空间会增加 'owner' 和'show_owner'，并且'show_owner' 对应的PyFunctionObject 对

象中的 func_globals 保存了当前 global名字空间的所有符号。在 module1.py 中执行完 owner = "module1" 后， module1的global 名字空间大概是

{..., 'owner' : 'module1', 'module2': <module 'module2...'>}，在执行 module2.show_owner() 时，首先要获得符号'show_owner' ：

执行函数需要创建一个PyFrameObject 对象，根据笔记（1）的条目p226所说，PyFrame_New(tstate, co, globals, NULL) 中的

global 参数是来自 PyFunctionObject.func_globals，故根据LEGB原则，print owner 输出的是'module2' 。

p392: Python 的线程在GIL(global interpreter lock) 的控制之下，线程之间，对整个Python 解释器（虚拟机），对Python 提供的 C API 的访问，都是互斥的，这可以看作是 Python 内核级的互斥机制。Python 内部维护一个数值N（sys.getcheckinterval() ），模拟内部的“软件中断”，当执行了某个线程的N 条指令之后应该立刻启动线程调度机制，因为 Python 中的线程实际上就是操作系统所支持的原生线程，故下一个被调度运行的线程由操作系统来选择。

p394: Python 线程的创建

threadmodule.c 提供的函数接口很少，定义在 static PyMethodDef thread_methods[] = { ...};

Python 虚拟机通过三个主要的动作，完成一个线程的创建：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14

//threadmodule.c
// thread.start_new_thread 对应的 c 实现函数
static PyObject *
thread_PyThread_start_new_thread(PyObject *self, PyObject *fargs)
{
    ...
    boot = PyMem_NEW( struct bootstate, 1); // 1)
    ...
    PyEval_InitThreads(); /* Start the interpreter's thread-awareness */ // 2)
    ...
    ident = PyThread_start_new_thread(t_bootstrap, ( void *) boot); // 3)
    ...
     return indent;
}

1). 创建并初始化bootstate 结构，保存线程的函数、函数参数等。

    C++ Code  
 

1
2
3
4
5
6
7

struct bootstate
{
    PyInterpreterState *interp;
    PyObject *func;
    PyObject *args;
    PyObject *keyw;
};

其中 boot->interp 指向了PyInterpreterState 对象，这个对象携带了如module pool 这样的全局信息，被所有 thread 所共享。

2). 初始化Python 的多线程环境。

当Python 启动时是不支持多线程的（线程的调度需要代价），一旦用户调用 thread.start_new_thread，Python 意识到用户需要多线程的支持，自动创建多线程机制需要的数据结构、环境以及重要的GIL 等。

    C++ Code  
 

1
2
3
4
5
6

// pythread.h
typedef void *PyThread_type_lock;

// ceval.c
static PyThread_type_lock interpreter_lock = 0; /* This is the GIL */
static long main_thread = 0;

如上定义可以看到实际上 GIL 就是一个 void* 指针，无论建立多少个线程，初始化只进行一次。

Python 多线程机制具有平台相关性，在Python/Python 目录下有一批 thread_***.h 的头文件，包装了不同操作系统的原生线程，并通过统一的接口暴露给 Python，比如thread_nt.h 包装的是win32 平台的原生 thread，interpreter_lock 就是指向了如下的 NRMUTEX 结构。

    C++ Code  
 

1
2
3
4
5
6
7

//thread_nt.h
typedef struct NRMUTEX
{
    LONG   owned ;
    DWORD  thread_id ;
    HANDLE hevent ;
} NRMUTEX, *PNRMUTEX ;

其中 hevent 对应 win32 下的 Event 这个内核对象，以实现线程的互斥；thread_id 记录任一时刻获得 GIL 的线程id；owned 初始化为-1表示可用，当一个线程开始等待 GIL 时owned 值原子性地加1，释放时原子性地减1。当一个线程释放GIL 时会通过 SetEvent 通知等待 Event 内核对象的所有线程，此时调度线程运行的难题就交给了操作系统选择。

当初始化环境完毕之后主线程（执行python.exe 时操作系统创建的线程）首先获得 GIL 控制权。

3). 以bootstate 为参数创建操作系统的原生线程。

在 PyThread_start_new_thread 中首先将t_bootstrap 和 boot 打包到一个类型为 callobj 的结构体obj 中，如下所示：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11

long PyThread_start_new_thread( void (*func)( void *), void *arg)
{
    callobj obj;
    obj.done = CreateSemaphore( NULL, 0, 1, NULL);
    ...
    rv = _beginthread(bootstrap, _pythread_stacksize, &obj);
     /* wait for thread to initialize, so we can get its id */
    WaitForSingleObject(obj.done, INFINITE); // 挂起

     return obj.id;
}

    C++ Code  
 

1
2
3
4
5
6

typedef struct {
     void (*func)( void*);
     void *arg;
     long id;
    HANDLE done;
} callobj;

当完成打包之后，调用 win32 下创建thread的api:_beginthread 来完成线程的创建，函数返回后主线程会挂起等待obj.done 这个Semaphore内核对象，子线程开始执行bootstrap ，在其中完成3个动作：1). 获取线程id; 2). 通知obj.done 内核对象; 3). 调用 t_bootstrap;

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12

static int bootstrap( void *call)
{
    callobj *obj = (callobj*)call;
     /* copy callobj since other thread might free it before we're done */
     void (*func)( void*) = obj->func;
     void *arg = obj->arg;

    obj->id = PyThread_get_thread_ident();
    ReleaseSemaphore(obj->done, 1, NULL);
    func(arg);
     return 0;
}

此时正在等待 obj.done 的主线程被唤醒而继续执行，返回了子线程id。而子线程继续执行 t_bootstrap，在里面进入等待 GIL 的状态。

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

static void t_bootstrap( void *boot_raw)
{
     struct bootstate *boot = ( struct bootstate *) boot_raw;
    PyThreadState *tstate;
    PyObject *res;

    tstate = PyThreadState_New(boot->interp);

    PyEval_AcquireThread(tstate); // 申请GIL
    res = PyEval_CallObjectWithKeywords(
        boot->func, boot->args, boot->keyw); // 最终调用 PyEval_EvalFrameEx
    ...
    PyMem_DEL(boot_raw);
    PyThreadState_Clear(tstate);
    PyThreadState_DeleteCurrent(); // 释放 GIL
    PyThread_exit_thread();
}

在子线程得到 GIL 后，PyEval_AcquireThread 返回，PyEval_CallObjectWithKeywords 最终调用 PyEval_EvalFrameEx，在 PyEval_EvalFrameEx 中Python 内部维护的模拟时钟中断会不断地激活线程的调度机制，在子线程和主线程之间不断地进行切换，从而真正实现多线程机制。

可以认为到此时子线程的初始化才算真正完成，子线程和主线程一样，都完全被Python 线程调度机制所控制了。需要注意的是：当所有线程都完成了初始化之后，操作系统的线程调度是与Python 的线程调度统一的（Python 线程调度--> GIL --> Event 内核对象 --> 操作系统调度），但在初始化完成之前，它们之间并没有因果关系。

我们知道操作系统在进行进程切换时需要保存or 恢复上下文环境，Python 在进行线程切换时也需要将线程状态保存在 PyThreadState 对象，前面说过，_PyThreadState_Current 这个全局变量一直指向当前被激活的线程对应的 PyThreadState 对象。Python 内部维护了一个单向链表来管理所有Python 线程的状态对象，对于这个链表的访问有一个独立的锁而不必在GIL 保护下进行，此锁的创建在Python 进行初始化时完成。

其中 id 是指线程id，如果value 都是指向 PyThreadState 对象，那么它们的 key 值都一致。

p413: Python 线程的调度

Python 的线程调度机制是内建在 Python 的解释器核心 PyEval_EvalFrameEx 中的。除了标准的计数调度外，还存在另一种阻塞调度，即在线程 A通过某种操作比如等待输入或者睡眠等，将自身阻塞后，Python 应该将等待GIL 的线程B 唤醒，当然 A 在挂起前肯定需要释放 GIL。

比如 time.sleep(1) 大概是这样实现的： { Py_BEGIN_ALLOW_THREADS(释放GIL) sleep(1); Py_END_ALLOW_THREADS(申请GIL) }

即通过两个宏来实现阻塞调度，注意阻塞调度则不会重置 PyEval_EvalFrameEx 内的 _Py_Ticker 为初始值 _Py_CheckInterval。

注：python中 thread 的一些机制和C/C++不同：在C/C++中，主线程结束后，其子线程会默认被主线程kill 掉。而在python中，主线程结束后，默认会等待子线程结束后，主线程才退出。The entire Python program exits when no alive non-daemon threads are left.
python 对于 thread 的管理中有两个函数：join 和 setDaemon
join：如在一个线程B中调用threadA.join()，则 threadA 结束后，线程B才会接着 threadA.join() 往后运行。
setDaemon：主线程A 启动了子线程B，调用B.setDaemaon(True)，则主线程结束时，会把子线程B也杀死，与C/C++ 中的默认效果是一样的。

p420: Python 线程的用户级互斥与同步

内核级通过 GIL 实现的互斥保护了内核的共享资源，同样用户级互斥保护了用户程序中的共享资源。

用户级的锁是用 lockobject 实现的，与GIL 一样， lock_lock 也指向一个win32 下的 Event 内核对象。

    C++ Code  
 

1
2
3
4

typedef struct {
PyObject_HEAD
PyThread_type_lock lock_lock;
} lockobject;

lockobject 对象提供的属性操作定义在 static PyMethodDef lock_methods[] = { ... }; 需要注意的是当锁不可用时 lockobject.acquire 操作也是一个阻塞操作，故大概是这样实现的： { Py_BEGIN_ALLOW_THREADS(释放GIL) PyThread_acquire_lock(); Py_END_ALLOW_THREADS(申请GIL) }

这是由于线程需要等待一个 lock 资源，为了避免死锁，需要将 GIL 转交给其他的等待 GIL 的线程，然后调用 PyThread_acquire_lock 开始尝试获得

用户级锁，在获得用户级锁之后，再尝试获得内核级lock--GIL。

p430:Python 的内存管理机制

layer 0 即操作系统提供的malloc or free 等接口；layer 1 是Python 基于第0 层包装而成，没有加入太多动作，只是为了处理与平台相关的内存分配行为而提供统一的接口； layer 2 主要提供创建Python 对象的接口，这一套函数族又被称为 Pymalloc 机制；layer 3 主要是常用对象如整数、字符串等的缓冲池机制。真正需要分析的是 layer 2 的实现，也是 GC(garbage collector) 的藏身之处。

p432: 小块空间的内存池

在Python 2.5 中，整个小块内存的内存池可以视为一个层次结构，在这个层次结构中，一共分为4层，从上至下为：block、pool、arena 和内存池。

前三个都是可以在源码中找到的实体，而 “内存池” 只是一个概念上的东西，表示Python 对整个小块内存分配和释放行为的内存管理机制。

在最底层，block 是一个确定大小的内存块(8, 16, 24, ...., 256)，大小超过256字节的内存申请转交给layer 1 PyMem 函数族处理。

一个pool 管理一堆具有固定大小的内存块，一个pool 大小通常为一个系统内存页4KB。

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/* 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  */
};

一块经过改造的 4KB 内存如下图：

其中实线箭头是指针，但虚线箭头只是偏移位置的形象表示。

ref.count 表示已经被分配的block 数量，此时为1。bp 返回的是一个可用地址，实际后面的内存都是可用的，但可以肯定申请内存的函数只会使用[bp, bp+size] 区间的内存，比如申请 25～32 字节大小的内存，会返回一个 32字节 block 的地址。

szidx 表示 size class index，比如 szidx=3 表示pool 管理的是 32字节的block 集合。在 pool header 中，nextoffset 和 maxoffset 是两个用于对pool 中的block 集合进行迭代的变量，如初始化时：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/*
* Initialize the pool header, set up the free list to
* contain just the second block, and return the first
* block.
*/
pool->szidx = size;
size = INDEX2SIZE(size); // 由szidx 转换成 size
bp = (block *)pool + POOL_OVERHEAD;
pool->nextoffset = POOL_OVERHEAD + (size << 1); // POOL_OVERHEAD + 2*size
pool->maxnextoffset = POOL_SIZE - size;
pool->freeblock = bp + size;
*(block **)(pool->freeblock) = NULL;

return ( void *)bp;

freeblock 指向下一个可用的block 地址，而nextoffset 是下下可用block 距离头部的偏移，故再次分配block 时，只需将freeblock 返回，并将其移动 nextoffset 的距离，同样地 nextoffset 值加上2个size 距离，即如下代码 2）处所示。

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/*
* There is a used pool for this size class.
* Pick up the head block of its free list.
*/
++pool->ref.count;
bp = pool->freeblock;
assert(bp != NULL);
if ((pool->freeblock = *(block **)bp) != NULL) // 1)
{
     return ( void *)bp;
}
/*
* Reached the end of the free list, try to extend it.
*/
if (pool->nextoffset <= pool->maxnextoffset) // 2)
{
     /* There is room for another block. */
    pool->freeblock = (block *)pool +
                      pool->nextoffset;
    pool->nextoffset += INDEX2SIZE(size);
    *(block **)(pool->freeblock) = NULL;
     return ( void *)bp;
}

现在考虑一种情况，假设pool 中5个连续的block 都被分配出去了，过一段时间释放了块2 和块4，那么下一次申请32字节内存，pool 返回的是第2块还是第6块呢？出于使用效率显然是第2块，具体实现是在 free block 时做的手脚，将一些离散的资源block 组织起来成为自由block 链表，而freeblock 则是这个链表的表头，如下代码所示：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

pool = POOL_ADDR(p); // p 是 PyObject_Free 的参数
if (Py_ADDRESS_IN_RANGE(p, pool))
{
     /* We allocated this address. */

     /* Link p to the start of the pool's freeblock list.  Since
     * the pool had at least the p block outstanding, the pool
     * wasn't empty (so it's already in a usedpools[] list, or
     * was full and is in no list -- it's not in the freeblocks
     * list in any case).
     */
    assert(pool->ref.count > 0);     /* else it was empty */
    *(block **)p = lastfree = pool->freeblock;
    pool->freeblock = (block *)p;
    ...
}

回到前面分析的block 分配行为，可以知道如果有先前释放的block 则直接返回如1）处代码所示，没有再进行2）处代码判断，在2）处还需指出一点即 maxoffset 是该pool 最后一个可用block 距离pool header 的偏移，故如果

nextoffset > maxnextoffset 则此pool 已经无block 可用了，可以考虑再申请一个pool 了。

一个area 大小是256KB，可以容纳 64个pool，这些pools 可能并不属于同一个 class size index 。pool_header 管理的内存与pool_header 自身是一块连续的内存，而 arena_object 与其管理的内存是分离的，也就是说当arena_object 被申请时，它所管理的pool 集合的内存还没被申请，下面是 arena_object 的定义，每个条目注释都写得非常清楚，我就不狗尾续貂解释了。

    C++ Code  
 

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

// obmalloc.c
#define ARENA_SIZE      ( 256 << 10) /* 256KB */
/* 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;
};

实际上在 Python 中存在多个 arena_object 构成的数组，数组首地址由全局变量 arenas 维护。当一个 arena_object 没有与pool 集合建立联系（申请pool集合内存）时为“未使用”状态，当建立联系后转为“可用”状态，各自由两个头指针链接起来，如下图：

一个pool 在Python 运行的任一时刻，总是处于以下三种状态之一：

used 状态：pool 中至少有一个 block 已经被使用，并且至少有一个block 还未被使用。这种状态的pool 受控于 Python 内部维护的 usedpools 数组，对于同样 class size index 的 pools， usedpools 只保存一个引用，而它们之间链接成链表。
full 状态：pool 中所有的 block 都已经被使用，这种状态的 pool 在 arena 中，但不在 arena 的 freepools 链表中；
empty 状态：pool 中所有block 都未被使用，处于这个状态的pool 的集合通过其pool_header 中的next_pool 构成一个链表，这个链表的表头就是 arena_object 的 freepools；

下图给出了一个“可用”的 arena 包含三种状态的pool 集合的一个可能状态。

注意：arena 中处于full 状态的pool 是各自独立的，并没有像其他pool 一样会链接成链表。

接着来看一下存放 pool_head 指针的 usedpools 数组的定义：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

#define SMALL_REQUEST_THRESHOLD 256
#define ALIGNMENT        8        /* must be 2^N */
#define NB_SMALL_SIZE_CLASSES   (SMALL_REQUEST_THRESHOLD / ALIGNMENT)

typedef struct pool_header *poolp;
#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)
    ...
#endif
}

即数组初始化完成之后如下图：

对比pool_header 结构体，此时我们可以发现这样的规律，usedpools[6]->nextpool == usedpools[6]，因为 usedpools[6] 即 usedpools[4] 的地址，向后偏移8个字节（一个ref 加上一个 block*），即 &nextpool，也就是 usedpools[6] 的地址。

当我们手中有一个 size 为 32 字节的pool，想要放入 usedpools 数组，只需要 usedpools[i+i]->nextpool = pool，其中 i 为size class index。在PyObject_Malloc 代码中，利用 usedpools 的巧妙结构，只需要通过简单判断来发现与某个class size index 对应的pool 是否在 usedpools 存在，如下：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12

size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; // class size index
pool = usedpools[size + size];
if (pool != pool->nextpool) // 简单判断
{
     /*
     * There is a used pool for this size class.
     * Pick up the head block of its free list.
     */
      // usedpools 有可用的 pool
}
...
// usedpools 无可用的pool，尝试获取 empty 状态pool

Python 的小块内存的内存池全景可以用下面一幅图展示：

p457: 循环引用的垃圾收集

在Python 中，主要的内存管理手段是引用计数机制，而标记--清除（Mark--Sweep）和分代收集只是为了打破循环引用而引入的补充技术。Python 中的循环引用总是发生在 container 对象之间，即是内部可持有对其他对象引用的对象，比如list、dict、class、instance 等。这些container 对象在创建后必须链入到 Python 内部的可收集对象链表中去，故需要在对象头部增加 PyGC_Head，如下图所示：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11

/* GC information is stored BEFORE the object structure. */
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 中有一个维护了三个 gc_generation 结构的数组，通过这个数组控制流三条可收集对象链表，这就是Python 中用于分代垃圾收集的三个“代”。初始化完毕如下图所示：

    C++ Code  
 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/*** 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，其中的count 记录了当前这条可收集对象链表中一共有多少个可收集对象，所有新创建的对象实际上都会被加入第0代链表中，即 generations[0].count++。而 threshold 记录了该条链表最多可容纳多少个可收集对象，一旦超过将立刻触发垃圾回收机制。

关于回收机制的大致描述：

/* 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. */

具体实现可以看collect 函数，下面列举比较重要的步骤及注释：

    C++ Code  
 

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

/* 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;

     /* merge younger generations with one we are currently collecting */ // 1)
     for (i = 0; i < generation; i++) {
        gc_list_merge(GEN_HEAD(i), GEN_HEAD(generation));
    }

    ...
     /* Using ob_refcnt and gc_refs, calculate which objects in the
     * container set are reachable from outside the set (i.e., have a
     * refcount greater than 0 when all the references within the
     * set are taken into account).
     */
    update_refs(young); // 2)
    subtract_refs(young);

     /* Leave everything reachable from outside young in young, and move
     * everything else (in young) to unreachable.
     * NOTE:  This used to move the reachable objects into a reachable
     * set instead.  But most things usually turn out to be reachable,
     * so it's more efficient to move the unreachable things.
     */
    gc_list_init(&unreachable);
    move_unreachable(young, &unreachable); // 3)

     /* Move reachable objects to next generation. */
     if (young != old)
        gc_list_merge(young, old);

     /* All objects in unreachable are trash, but objects reachable from
     * finalizers can't safely be deleted.  Python programmers should take
     * care not to create such things.  For Python, finalizers means
     * instance objects with __del__ methods.  Weakrefs with callbacks
     * can also call arbitrary Python code but they will be dealt with by
     * handle_weakrefs().
     */
    gc_list_init(&finalizers);
    move_finalizers(&unreachable, &finalizers);
     /* finalizers contains the unreachable objects with a finalizer;
     * unreachable objects reachable *from* those are also uncollectable,
     * and we move those into the finalizers list too.
     */
    move_finalizer_reachable(&finalizers); // 4)

     /* Clear weakrefs and invoke callbacks as necessary. */
    m += handle_weakrefs(&unreachable, old);

     /* Call tp_clear on objects in the unreachable set.  This will cause
     * the reference cycles to be broken.  It may also cause some objects
     * in finalizers to be freed.
     */
    delete_garbage(&unreachable, old);   // 5)

     /* Append instances in the uncollectable set to a Python
     * reachable list of garbage.  The programmer has to deal with
     * this if they insist on creating this type of structure.
     */
    ( void)handle_finalizers(&finalizers, old);


     return n+m;
}

下图是用于演示标记--清除算法的例子：

1). 将比当前代年轻的一代链接在其后面，此后的标记清除算法在此条链表进行。

2). update_refs 将PyGC_Head 中的gc.gc_ref 赋值为其对象 ob_refcnt 值；subtract_refs 将循环引用摘除，即对 gc.gc_ref 值做相应减法操作。完成后如下图：

3). 将待处理链表的unreachable object 移动到 unreachable 链表中。处理完成后如下图所示：

这里说明下reachable的含义，也就是所谓的标记阶段：所谓的root object 是被一些全局引用和函数栈中的引用所引用的对象，这些对象是不可被删除的；从 root object 集合出发，沿着集合中的每一个引用，如果能够达到某个对象 A，则称 A 是可达的 reachable。如list2 的gc.gc_ref 本来为0，被暂时移动到 unreachable 链表中，后来发现root object list1 引用着它，则将其 gc.gc_ref 修改为1，表示 reachable。

4). 对于一类特殊的container 对象，即从类对象实例化得到的实例对象，如果 class 定义中有一个特殊方法：'__del__'，则将unreachable 链表中拥有 finalizer 的 instance 对象都移动到一个名为 garbage 的PyListObject 对象中。

5). 在3) 中只是使用 gc.gc_ref 模拟量循环引用的打破，在 delete_garbage 中会调用container 对象的类型对象中的tp_clear 操作，进而调整container 对象中每个引用所用的对象的引用计数值，从而完成打破循环引用的最终目标。

注：可以使用Python 中的gc 模块来观察垃圾回收，如

import gc

gc.set_debug(gc.DEBUG_STATS | gc.DEBUG_LEAK)

gc.collect()

Memory-wise, we already know that subprocess.Popen uses fork/clone under the hood, meaning that every time you call it you're requesting once more as much memory as Python is already eating up, i.e. in the hundreds of additional MB, all in order to then exec a puny 10kB executable such as free or ps. In the case of an unfavourable overcommit policy, you'll soon see ENOMEM.