CPython源码阅读笔记(2)
PyObject
CPython 中基本的数据结构是 Object，所有的 Python 对象都可以用 PyObject * 来访问，CPython 中通过 Object 手动实现了对象系统。
PyObject 定义于 include/object.h 中，可以看到，结构体里只是一个简单的 PyObject_HEAD 宏。
typedef struct _object {
PyObject_HEAD
} PyObject;
展开之后为
typedef struct _object {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
} PyObject;
其中 ob_refcnt 为 Python 对象的引用计数，用于实现自动的内存管理，当对象没有任何被引用的时候自动回收内存。
继承 PyObject 的对象需要在结构体声明的第一项引用 PyObject_HEAD 的宏。
例如 PyIntObject
// include/intobject.h
typedef struct {
PyObject_HEAD
long ob_ival;
} PyIntObject;
PyIntObject 第一行为 PyObject_HEAD 宏，也就是说和 PyObject 结构一致。 在将 PyIntObject * 转换为 PyObject * 时，会忽略掉下面多出的 ob_ival 字段，所以能成功的把 PyIntObject 转为 PyObject *。
通过 *ob_type 可以确定对应的对象的类型，对象的类型创建后便不会更改。通过类型可以确定对应的对象中包含的数据。
CPython 中的对象都需要通过特定的函数来创建，所有对象都需要申请内存来创建在堆中，不允许创建在栈上或者创建为全局变量(例如直接声明 PyIntObject i)，因为需要统一使用引用计数来管理内存。
Py_INCREF(op)
// include/object.h
#define Py_INCREF(op) ( \
_Py_INC_REFTOTAL _Py_REF_DEBUG_COMMA \
((PyObject*)(op))->ob_refcnt++)
Py_DECREF(op)
使用 do while 将宏中的 if else 包裹起来是为了避免嵌套的 if else 中使用宏无法正确配对的问题。
Py_DECREF 对 Object 的引用计数 ob_refcnt 字段进行减一操作，若 ob_refcnt 为 0 则调用析构函数销毁对象。
// include/object.h
#define Py_DECREF(op) \
do { \
if (_Py_DEC_REFTOTAL _Py_REF_DEBUG_COMMA \
--((PyObject*)(op))->ob_refcnt != 0) \
_Py_CHECK_REFCNT(op) \
else \
_Py_Dealloc((PyObject *)(op)); \
} while (0)
#define _Py_Dealloc(op) ( \
_Py_INC_TPFREES(op) _Py_COUNT_ALLOCS_COMMA \
(*Py_TYPE(op)->tp_dealloc)((PyObject *)(op)))
默认的析构函数为对应的 _typeobject 中tp_dealloc字段填写的函数指针。
PyVarObject
PyVarObject 中包含一组 object，数量由 ob_size 指定。
#define PyObject_VAR_HEAD \
PyObject_HEAD \
Py_ssize_t ob_size; /* Number of items in variable part */
typedef struct {
PyObject_VAR_HEAD
} PyVarObject;
展开后为
typedef struct {
Py_ssize_t ob_refcnt;
struct _typeobject *ob_type;
Py_ssize_t ob_size;
} PyVarObject;
变长的对象需要在结构体声明的第一项引用 PyObject_VAR_HEAD 宏。
PyTypeObject
继承 PyObject 的对象需要创建对应的 PyTypeObject 对象用于初始化，具体参考
https://docs.python.org/2/extending/newtypes.html https://docs.python.org/2/c-api/typeobj.html。
通过给对应的字段填入不同的函数指针，结合对应的宏，实现运行时多态。
typedef struct _typeobject {
PyObject_VAR_HEAD
const char *tp_name; /* For printing, in format "<module>.<name>" */
Py_ssize_t tp_basicsize, tp_itemsize; /* For allocation */
/* Methods to implement standard operations */
destructor tp_dealloc;
printfunc tp_print;
getattrfunc tp_getattr;
setattrfunc tp_setattr;
cmpfunc tp_compare;
reprfunc tp_repr;
/* Method suites for standard classes */
PyNumberMethods *tp_as_number;
PySequenceMethods *tp_as_sequence;
PyMappingMethods *tp_as_mapping;
/* More standard operations (here for binary compatibility) */
hashfunc tp_hash;
ternaryfunc tp_call;
reprfunc tp_str;
getattrofunc tp_getattro;
setattrofunc tp_setattro;
/* Functions to access object as input/output buffer */
PyBufferProcs *tp_as_buffer;
/* Flags to define presence of optional/expanded features */
long tp_flags;
const char *tp_doc; /* Documentation string */
/* Assigned meaning in release 2.0 */
/* call function for all accessible objects */
traverseproc tp_traverse;
/* delete references to contained objects */
inquiry tp_clear;
/* Assigned meaning in release 2.1 */
/* rich comparisons */
richcmpfunc tp_richcompare;
/* weak reference enabler */
Py_ssize_t tp_weaklistoffset;
/* Added in release 2.2 */
/* Iterators */
getiterfunc tp_iter;
iternextfunc tp_iternext;
/* Attribute descriptor and subclassing stuff */
struct PyMethodDef *tp_methods;
struct PyMemberDef *tp_members;
struct PyGetSetDef *tp_getset;
struct _typeobject *tp_base;
PyObject *tp_dict;
descrgetfunc tp_descr_get;
descrsetfunc tp_descr_set;
Py_ssize_t tp_dictoffset;
initproc tp_init;
allocfunc tp_alloc;
newfunc tp_new;
freefunc tp_free; /* Low-level free-memory routine */
inquiry tp_is_gc; /* For PyObject_IS_GC */
PyObject *tp_bases;
PyObject *tp_mro; /* method resolution order */
PyObject *tp_cache;
PyObject *tp_subclasses;
PyObject *tp_weaklist;
destructor tp_del;
/* Type attribute cache version tag. Added in version 2.6 */
unsigned int tp_version_tag;
} PyTypeObject;
PyIntObject
PyIntObject 为 CPython 中存储普通整数的对象（使用 long 类型存储）。 为 Python 中的 immutable object （不可变对象），即 Python 中每次对变量赋新的整数值时，会申请新的 PyIntObject 对象并将变量指向这个新的对象（或者从 freelist 中找到已有的变量）。
因为，使用 long 存储，PyIntObject 存储的整数上限为 LONG_MAX 即 0x7fffffffffffffff(在 Python2 中 可以用 hex(sys.maxint) 得到)。超过上限的数据将存储到 PyLongObject 中。
PyIntObject 定义在 include/intobject.h 中。
typedef struct {
PyObject_HEAD
long ob_ival;
} PyIntObject;
PyIntObject 的创建
PyIntObject 的创建可以通过 5 个 API 中的一个来完成， 其中最常用的为 PyInt_FromLong， CPython 内部创建新的 PyIntObject 也会通过该 API 。
PyAPI_FUNC(PyObject *) PyInt_FromString(char*, char**, int);
#ifdef Py_USING_UNICODE
PyAPI_FUNC(PyObject *) PyInt_FromUnicode(Py_UNICODE*, Py_ssize_t, int);
#endif
PyAPI_FUNC(PyObject *) PyInt_FromLong(long);
PyAPI_FUNC(PyObject *) PyInt_FromSize_t(size_t);
PyAPI_FUNC(PyObject *) PyInt_FromSsize_t(Py_ssize_t);
// Objects/intobject.c PyInt_FromLong
PyObject *
PyInt_FromLong(long ival)
{
register PyIntObject *v;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
if (-NSMALLNEGINTS <= ival && ival < NSMALLPOSINTS) {
v = small_ints[ival + NSMALLNEGINTS];
Py_INCREF(v);
return (PyObject *) v;
}
#endif
if (free_list == NULL) {
if ((free_list = fill_free_list()) == NULL)
return NULL;
}
/* Inline PyObject_New */
v = free_list;
free_list = (PyIntObject *)Py_TYPE(v);
PyObject_INIT(v, &PyInt_Type);
v->ob_ival = ival;
return (PyObject *) v;
}
PyInt_FromLong 中可以看到， 定义了名为 small_ints 的全局数组，用于存储大于-5小于257的小整数，这些对象在解释器初始化后便申请完成，并且在 CPython 解释器整个生存周期里会一直存在。
#ifndef NSMALLPOSINTS
#define NSMALLPOSINTS 257
#endif
#ifndef NSMALLNEGINTS
#define NSMALLNEGINTS 5
#endif
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
/* References to small integers are saved in this array so that they
can be shared.
The integers that are saved are those in the range
-NSMALLNEGINTS (inclusive) to NSMALLPOSINTS (not inclusive).
*/
static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];
我们可以在 if (free_list == NULL) { 这一行下一个断点，运行 Python 输入 a = 1。
单步执行可以看，到应该会直接跳过 if (free_list == NULL) {，执行 /* Inline PyObject_New */ 注释下的那几行代码。
v = free_list; // 从空闲链表里获取一个申请好的 PyIntObject
free_list = (PyIntObject *)Py_TYPE(v); // 将指针指向空闲链表中下一个空闲的对象
PyObject_INIT(v, &PyInt_Type); // 将 v->ob_type 设置为 `PyIntObject *` 并将 ob_refcnt 设置为 1
v->ob_ival = ival;
return (PyObject *) v;
free_list 空闲链表
为了节省空间，空闲链表复用了 PyIntObject 中 ob_type 字段存放指向链表下一个元素的指针。
当 free_list 用完之后，也就是 free_list == NULL 为 True 时，会调用 fill_free_list 申请新的空闲链表。
*block_list 和 *free_list 为 intobject.c 中的全局变量
static PyIntBlock *block_list = NULL;
static PyIntObject *free_list = NULL;
PyIntBlock 定义如下
struct _intblock {
struct _intblock *next;
PyIntObject objects[N_INTOBJECTS];
};
typedef struct _intblock PyIntBlock;
PyIntBlock 在内存中的布局大致如下
PyIntBlock PyIntBlock
+--------+ +--------+
| | | |
| Next +---------------------------> Next |
| | | |
+--------+ +--------+
| | | |
| | | |
| objects| | objects|
| | | |
| | | |
+---+----+ +---+----+
| |
+---------v---+------------+ +---------v---+------------+
| | | | | |
| PyIntObject | ...... | | PyIntObject | ...... |
| | | | | |
| | | | | |
+-------------+------------+ +-------------+------------+
N_INTOBJECTS N_INTOBJECTS
gdb 中在该函数处设置断点， p sizeof(PyIntBlock->objects) 得到 960, p sizeof(PyIntObject) 得到 40， 所以在我的机器上 N_INTOBJECTS 等于 24，即空闲链表一次性申请 24 个 PyIntObject。
static PyIntObject *
fill_free_list(void)
{
PyIntObject *p, *q;
/* Python's object allocator isn't appropriate for large blocks. */
p = (PyIntObject *) PyMem_MALLOC(sizeof(PyIntBlock));
if (p == NULL)
return (PyIntObject *) PyErr_NoMemory();
((PyIntBlock *)p)->next = block_list;
block_list = (PyIntBlock *)p;
/* Link the int objects together, from rear to front, then return
the address of the last int object in the block. */
p = &((PyIntBlock *)p)->objects[0];
q = p + N_INTOBJECTS;
while (--q > p)
Py_TYPE(q) = (struct _typeobject *)(q-1);
Py_TYPE(q) = NULL;
return p + N_INTOBJECTS - 1;
}
fill_free_list 为 PyIntBlock 申请内存，将 objects 中的对象，复用其 ob_type 字段做指针，指向上一个空闲块，最后返回 objects 数组最后一项赋值给 free_list
free_list = fill_free_list()
PyIntBlock->objects
+------------+--------------+--------------+
|PyIntObject | PyIntObject | PyIntObject |
| | | | <----+ free_list
| ob_type | ob_type | ob_type |
| + | + | + |
+---------+--+-----------+--+--------------+
| ^ | ^ |
| | | | |
NULL<--------+ +---------+ +---------+
PyIntBlock申请后不会主动释放，只有在解释器结束时调用 PyInt_Fini 释放。
运行时不再使用（ob_refcnt=0）的 PyIntObject 会归还到空闲链表。
Py_DECREF 当 ob_refcnt = 0 会调用对应 PyTypeObject 中 tp_dealloc 字段对应的函数指针。
PyTypeObject PyInt_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int",
sizeof(PyIntObject),
0,
(destructor)int_dealloc, /* tp_dealloc */
(printfunc)int_print, /* tp_print */
在 PyIntObject 创建的 PyTypeObject 中 tp_dealloc 字段指向了 int_dealloc。
static void
int_dealloc(PyIntObject *v)
{
if (PyInt_CheckExact(v)) {
Py_TYPE(v) = (struct _typeobject *)free_list;
free_list = v;
}
else
Py_TYPE(v)->tp_free((PyObject *)v);
}
可以看到，int_dealloc 中并没有将内存返给系统，而是将对象加入空闲链表。
我们可以在调试器中观察该过程， 启动 Python 后挂上 gdb，在 dealloc 处设置断点，使用 del 手动触发 dealloc 。
>>> a = 1
>>> del a
// 先查看传入的 object 的地址
> p v
$18 = (PyIntObject *) 0x8c6218
// 查看当前 block_list 的开始地址
> p &block_list->objects[0]
$16 = (PyIntObject *) 0x8c61c8
// 所以传入的 object 在 objects 数组的第 (0x8c6218 - 0x8c61c8 ) / 40 = 2 个位置
// 查看对应的 object， 也可以用 p *(PyIntObject *)v
> p block_list->objects[2]
$21 = {_ob_next = 0x0, _ob_prev = 0x0, ob_refcnt = 0, ob_type = 0x7e8fc0 <PyInt_Type>, ob_ival = 1000}
// 将 object 加入 free_list 之后
> p block_list->objects[2]
$23 = {_ob_next = 0x0, _ob_prev = 0x0, ob_refcnt = 0, ob_type = 0x8c6240, ob_ival = 1000}
// 查看 free_list 中的其他元素
> p *(PyIntObject *)v->ob_type->ob_type
$27 = {_ob_next = 0x0, _ob_prev = 0x0, ob_refcnt = 0, ob_type = 0x8c61f0, ob_ival = 9498440}
> p &(*(PyIntObject *)v->ob_type->ob_type)
$35 = (PyIntObject *) 0x8c6268
运行一段时间后， free_list 的内存布局大概会变成这样
PyIntBlock PyIntBlock
+--------+ +--------+
| | | |
| Next +---------------------------> Next |
| | | |
+--------+ +--------+
| | | |
| | | |
| objects| | objects|
| | | |
| | | |
+---+----+ +---+----+
| |
+-----+---v-+----+-----+-----+ +-----+---v-+----+-----+-----+
| | | | | | | | | | | |
| | | | | | | | | | | |
|used | free|used|used |free | |used | free|used|used |free |
| | | | | | | | | | | |
+-----+--+--+----+-----+--+-++ +-----+-^-+-+----+-----+--+--+
| ^ | | | ^
+----------------+ +----------------- +---------------+
PyIntObject 的运算
上一篇中我们了解了 CPython 解释器的基本执行流程，根据之前的知识，代码先会被编译成字节码，然后在核心循环中执行，所以我们调试 CPython 时可以按照如下步骤：
- 编写想要调试的功能对应的 Python 代码
- 使用 dis 模块得到源码对应的字节码
- 在 PyEval_EvalFrameEx 的核心循环中找到字节码对应的 TARGET，下断点
先看一下两个 PyIntObject 如何相加， 创建 test.py 文件写入以下内容：
# test.py
a=1
b=2
c=a+b
调用反编译模块， 查看对应的字节码
python2 -m dis test.py
1 0 LOAD_CONST 0 (1)
3 STORE_NAME 0 (a)
2 6 LOAD_CONST 1 (2)
9 STORE_NAME 1 (b)
3 12 LOAD_NAME 0 (a)
15 LOAD_NAME 1 (b)
18 BINARY_ADD
19 STORE_NAME 2 (c)
22 LOAD_CONST 2 (None)
25 RETURN_VALUE
在之前我们看过的 ceval.c 中，可以找到对 BINARY_ADD 字节码进行解释执行的代码。
可以看到，反编译出的字节码中，先通过 LOAD_NAME 将两个变量压栈，所以 BINARY_ADD 先从栈中 POP 出这两个变量，PyInt_AS_LONG 宏是从 PyIntObject 中取对应的 ob_ival 字段，相加得到结果后检查是否溢出。没有溢出的情况直接将结果写回栈顶。
// Python/ceval.c PyEval_EvalFrameEx
TARGET_NOARG(BINARY_ADD)
{
w = POP();
v = TOP();
if (PyInt_CheckExact(v) && PyInt_CheckExact(w)) {
/* INLINE: int + int */
register long a, b, i;
a = PyInt_AS_LONG(v);
b = PyInt_AS_LONG(w);
/* cast to avoid undefined behaviour
on overflow */
i = (long)((unsigned long)a + b);
if ((i^a) < 0 && (i^b) < 0)
goto slow_add;
x = PyInt_FromLong(i);
}
else if (PyString_CheckExact(v) &&
PyString_CheckExact(w)) {
x = string_concatenate(v, w, f, next_instr);
/* string_concatenate consumed the ref to v */
goto skip_decref_vx;
}
else {
slow_add:
x = PyNumber_Add(v, w);
}
Py_DECREF(v);
skip_decref_vx:
Py_DECREF(w);
SET_TOP(x);
if (x != NULL) DISPATCH();
break;
}
为了提升速度，再检查了栈中 pop 的两个变量的类型均为 PyInt_Type 后，加法运算的代码直接写在了 PyEval_EvalFrameEx 里，只有当溢出发生时才调用对应的 PyNumber_Add 方法。
PyIntObject 中使用 long 存储对应的整数，使用 sys.maxint 可以得到 PyIntObject 可以存储的数的上限。 (即 long 的存储上限， 64位系统下 long 为64位，因为有符号，所以上限为 2^63 -1 = 9223372036854775807)
>>> sys.maxint
9223372036854775807
修改 test.py 成下面这样可以触发 PyNumber_Add。
# test.py
a=9223372036854775807
b=1
c = a+b
PyNumber_Add 将传入的两个对象，和对应的 slot （即 PyInt_Type->tp_as_number->nb_add， 对应 int_add 函数) 传入 binary_op1。
#define NB_SLOT(x) offsetof(PyNumberMethods, x)
PyObject *
PyNumber_Add(PyObject *v, PyObject *w)
{
PyObject *result = binary_op1(v, w, NB_SLOT(nb_add));
if (result == Py_NotImplemented) {
PySequenceMethods *m = v->ob_type->tp_as_sequence;
Py_DECREF(result);
if (m && m->sq_concat) {
return (*m->sq_concat)(v, w);
}
result = binop_type_error(v, w, "+");
}
return result;
}
单步执行可以看到， binary_op1 进行了几个判断后，调用了对应的 slot 函数，即 int_add。
static PyObject *
binary_op1(PyObject *v, PyObject *w, const int op_slot)
{
PyObject *x;
binaryfunc slotv = NULL;
binaryfunc slotw = NULL;
if (v->ob_type->tp_as_number != NULL && NEW_STYLE_NUMBER(v))
slotv = NB_BINOP(v->ob_type->tp_as_number, op_slot);
....
if (slotv) {
....
x = slotv(v, w);
if (x != Py_NotImplemented)
return x;
Py_DECREF(x); /* can't do it */
}
....
}
int_add 和 TARGET_NOARG(BINARY_ADD) 的区别仅在溢出后主动调用 PyLong_Type 的 long_add 来处理 PyIntObject 无法表示的数。
static PyObject *
int_add(PyIntObject *v, PyIntObject *w)
{
register long a, b, x;
CONVERT_TO_LONG(v, a);
CONVERT_TO_LONG(w, b);
/* casts in the line below avoid undefined behaviour on overflow */
x = (long)((unsigned long)a + b);
if ((x^a) >= 0 || (x^b) >= 0)
return PyInt_FromLong(x);
return PyLong_Type.tp_as_number->nb_add((PyObject *)v, (PyObject *)w);
}
PyIntObject 的其他方法
根据文档 tp_str 会在调用 Python str 函数时调用，PyInt_Type 中 tp_str 指向 int_to_decimal_string。
PyTypeObject PyInt_Type = {
PyVarObject_HEAD_INIT(&PyType_Type, 0)
"int",
sizeof(PyIntObject),
0,
(destructor)int_dealloc, /* tp_dealloc */
(printfunc)int_print, /* tp_print */
0, /* tp_getattr */
0, /* tp_setattr */
(cmpfunc)int_compare, /* tp_compare */
(reprfunc)int_to_decimal_string, /* tp_repr */
&int_as_number, /* tp_as_number */
0, /* tp_as_sequence */
0, /* tp_as_mapping */
(hashfunc)int_hash, /* tp_hash */
0, /* tp_call */
(reprfunc)int_to_decimal_string, /* tp_str */
单行的语句可以在 Python 中使用 compile 得到 CodeObject， 将 CodeObject 传入 dis.dis 函数可以得到字节码。
>>> import dis
>>> co = compile('str(123)', '' ,'single')
>>> dis.dis(co)
1 0 LOAD_NAME 0 (str)
3 LOAD_CONST 0 (123)
6 CALL_FUNCTION 1
9 PRINT_EXPR
10 LOAD_CONST 1 (None)
13 RETURN_VALUE
在 int_to_decimal_string 处下断点， 运行 str(123) 得到调用栈如下
(gdb) bt
#0 int_to_decimal_string (v=0x8606b0) at Objects/intobject.c:1174
#1 0x000000000045ed4c in _PyObject_Str (v=0x8606b0) at Objects/object.c:430
#2 0x000000000045ee75 in PyObject_Str (v=0x8606b0) at Objects/object.c:451
#3 0x000000000047c784 in string_new (type=0x7f2580 <PyString_Type>, args=0x7ffff6dc4450, kwds=0x0) at Objects/stringobject.c:3709
#4 0x00000000004858b7 in type_call (type=0x7f2580 <PyString_Type>, args=0x7ffff6dc4450, kwds=0x0) at Objects/typeobject.c:749
#5 0x0000000000421043 in PyObject_Call (func=0x7f2580 <PyString_Type>, arg=0x7ffff6dc4450, kw=0x0) at Objects/abstract.c:2546
#6 0x00000000004d9721 in do_call (func=0x7f2580 <PyString_Type>, pp_stack=0x7fffffffd968, na=1, nk=0) at Python/ceval.c:4567
#7 0x00000000004d8ae6 in call_function (pp_stack=0x7fffffffd968, oparg=1) at Python/ceval.c:4372
#8 0x00000000004d33a9 in PyEval_EvalFrameEx (f=0x7ffff6a55060, throwflag=0) at Python/ceval.c:2987
gdb 中使用 f 8 查看 PyEval_EvalFrameEx 中调用的代码，发现确实是从 CALL_FUNCTION 进入。
// PyEval_EvalFrameEx
TARGET(CALL_FUNCTION)
{
PyObject **sp;
PCALL(PCALL_ALL);
sp = stack_pointer;
x = call_function(&sp, oparg);
....
}
/* Convert an integer to a decimal string. On many platforms, this
will be significantly faster than the general arbitrary-base
conversion machinery in _PyInt_Format, thanks to optimization
opportunities offered by division by a compile-time constant. */
static PyObject *
int_to_decimal_string(PyIntObject *v) {
char buf[sizeof(long)*CHAR_BIT/3+6], *p, *bufend;
long n = v->ob_ival;
unsigned long absn;
p = bufend = buf + sizeof(buf);
absn = n < 0 ? 0UL - n : n;
do {
*--p = '0' + (char)(absn % 10);
absn /= 10;
} while (absn);
if (n < 0)
*--p = '-';
return PyString_FromStringAndSize(p, bufend - p);
}