CPython 实现 - 整型对象

leohowell
367 阅读8分钟
原文链接： leohowell.com

这篇文档主要介绍CPython中的整数对象

在这之前先贴一些Python代码

>>> id(1)
140574362462680
>>> id(2)
140574362462656
>>> id(3)
140574362462632
>>> id(4)
140574362462608

内存地址竟然是连续的

id(1) - 24 = id(2)
id(2) - 24 = id(3)
id(3) - 24 = id(4)

天啦噜

一句话介绍：python整数对象的值是一个c语言的long类型

我也是看到哪写到哪里，请随意看看

上来先贴一个int内存池的初始化方法

简单看一下，看不懂也没有关系，重点看字

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)
        q->ob_type = (struct _typeobject *)(q-1);
    q->ob_type = NULL;
    return p + N_INTOBJECTS - 1;
}

可以看到PyIntObject指针p指向了刚分配的PyIntBlock的起始地址

这里把PyIntObject对象指针强制转为了PyIntBlock指针

这里的强制转换是可以的，因为分配的内存大小本来就是PyIntBlock

那么什么是PyIntBlock

来看一下PyIntBlock的结构

#define BLOCK_SIZE    1000    /* 1K less typical malloc overhead */
#define BHEAD_SIZE    8    /* Enough for a 64-bit pointer */
#define N_INTOBJECTS    ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))

struct _intblock {
    struct _intblock *next;
    PyIntObject objects[N_INTOBJECTS];
};

typedef struct _intblock PyIntBlock;

static PyIntBlock *block_list = NULL;
static PyIntObject *free_list = NULL;

PyIntBlock里有一个 PyIntObject的数组object

看起来PyIntBlock是一个PyIntObject的集合

还有一个next指针

next指针说明这个结构体主要作为单链表使用

#define N_INTOBJECTS    ((BLOCK_SIZE - BHEAD_SIZE) / sizeof(PyIntObject))
sizeof(PyIntObject)在我的电脑上为24 (Macbook Pro mid 2015)

可通过以下python代码查看

import sys
sys.getsizeof(1)
>>> 24

所以objects的大小为41

也是就是说每个PyIntBlock包含41个PyIntObject

我们还看到了

block_list

free_list

这两个是什么呢，只能接着往下看

来扫一眼这堆宏

#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];
#endif
#ifdef COUNT_ALLOCS
int quick_int_allocs, quick_neg_int_allocs;
#endif

定义了NSMALLPOSINTS(n small positive ints) 257

NSMALLNEGINTS(n small negative ints) 5

然后定义了一个 small_ints指针，指向大小为(257+5)的PyIntObject数组

small_ints 为指针数组(数组中存放的都是指针)

现在是创建PyIntObject的函数

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);
#ifdef COUNT_ALLOCS
        if (ival >= 0)
            quick_int_allocs++;
        else
            quick_neg_int_allocs++;
#endif
        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 *)v->ob_type;
    PyObject_INIT(v, &PyInt_Type);
    v->ob_ival = ival;
    return (PyObject *) v;
}

这个函数先判断一下这个long类型变量ival是否在[-5,257)范围内

如果在的话直接从small_ints这个指针数组中取出一个指向PyIntObject的指针，并且将该指针指向对象的引用计数加1

如果不在的话判断一下free_list是否为空，为空的话

执行 free_list = fill_free_list()

也就是到了我们最开始的那个函数

这个free_list呢，是一个整数空闲空间对象池

那么现在的问题是什么？，我们先把代码贴下来，方便讨论

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)
        q->ob_type = (struct _typeobject *)(q-1);
    q->ob_type = NULL;
    return p + N_INTOBJECTS - 1;
}

p开始是一个PyIntObject指针

然后申请了一个sizeof(PyIntBlock)空间

p指向新申请空间的起始地址

然后p被转换为了一个PyIntBlock指针

然后p->next指向了block_list的起始地址

然后block_list指向了p

也就是说现在的block_list已经有一个PyIntBlock的内存空间了

接下来做了些什么？

接下来p又指向了刚分配内存空间的PyIntBlock结构体objects数组的第一个PyIntObject起始地址

q则指向了objects数组最后一个元素的起始地址

接下来据说是把objects中的PyIntObject对象依次用ob_type指针链接起来

但是现在问题是ob_type是个什么玩意？

这个时候来回顾一下PyIntObject

typedef struct _object {
    PyObject_HEAD
} PyObject;


#define PyObject_HEAD            \
    _PyObject_HEAD_EXTRA        \
    Py_ssize_t ob_refcnt;        \
    struct _typeobject *ob_type;

typedef struct {
    PyObject_HEAD
    long ob_ival;
} PyIntObject;

现在可以看到ob_type是指向_typeobject结构体的指针

所以我们还得看一下——typeobject是什么，我把代码贴过来

天啦噜 代码太长了不贴了，反正已经知道是指针了 天下指针都一样

下面着重分一下这两行代码干了什么

while (--q > p)
    q->ob_type = (struct _typeobject *)(q-1);

指针q指向一个PyIntObject对象，

现在让q指向的对象的ob_type指针指向q前面一个元素

这样下来所有的PyIntBlock的objects内的所有PyIntObject通过ob_type链接起来成为了一个单向链表

q->ob_type = NULL; //处理第一元素

最后返回了最后一个PyIntObject元素的地址

这个地址也就是free_list的起始地址

这样的话free_list就有了空间

其实就是free_list分配空间的过程

接下来回到

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);
#ifdef COUNT_ALLOCS
        if (ival >= 0)
            quick_int_allocs++;
        else
            quick_neg_int_allocs++;
#endif
        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 *)v->ob_type;
    PyObject_INIT(v, &PyInt_Type);
    v->ob_ival = ival;
    return (PyObject *) v;
}

现在

v = free_list;

这里v就是指向刚分配的PyIntBlock的objects数组的最后一个元素

然后free_list沿着链表指向了objects中的前一个元素

现在调用了PyObject_INIT()函数，先不管这个函数，就当它是初始化好了

然后给v指向的PyIntObject的ob_ival赋值

最后返回一个PyObject对象的指针

注意哦 这里不是PyIntObject

从函数定义上也能看出来

PyObject * PyInt_FromLong(long ival)

至于是为什么，我知道了再更新在下面

现在呢当你调用了PyInt_FromLong方法之后

就会得到一个指向个这个整数PyIntObject的指针

现在我们就知道当生成一个大整数对象的时候要从free_list中拿到分配的空间

只有当free_list == NULL的时候才会重新申请一个PyIntBlock

之前提到了block_list

什么是block_list?

((PyIntBlock *)p)->next = block_list;
block_list = (PyIntBlock *)p;

static PyIntBlock *block_list = NULL;
static PyIntObject *free_list = NULL;

free_list是一个PyIntObject链表

block_list是一个PyIntBlock链表

每次分配的PyIntBlock都会加入到block_list

free_list则指向PyIntBlock objects中的PyIntObject

block_list指向的永远是最近创建的PyIntBlock

这个时候出现重大问题

block_list 这个链表中一旦有其中一个PyIntBlock中的objects中的PyIntObject需要被释放，那怎么办？

答案是python在回收的时候把空闲的全都链接到了一起

那么链接到什么地方去了

空闲空间怎么复用

原有objects链表如何链接？

只能继续往下看

PyIntObject的销毁

static void
int_dealloc(PyIntObject *v)
{
    if (PyInt_CheckExact(v)) {
        v->ob_type = (struct _typeobject *)free_list;
        free_list = v;
    }
    else
        v->ob_type->tp_free((PyObject *)v);
}

大致扫一眼就知道了

回收的PyIntObject对象空间被放到了free_list的链表的头部

v->ob_type = (struct _typeobject *)free_list;
free_list = v;

也就是说这部分内存并没有被释放

这里请注意，永远没有被释放

一个PyIntObject 24个字节

1GB内存 理论上可以容纳 44739242 个整数对象，实际更少

那么 大整数就是这样了 做个简单总结

当要生成一个大整数对象的时候

先去free_list中取空间

没有就初始化free_list

每一次初始化就会申请一个PyIntBlock的空间

空间大小为1000-8 = 992个字节(992B)

这些空间为41个整数

所有的PyIntBlock都在block_list这个链表上

而free_list则是所有这些PyIntBlock中可用PyIntObject的链表

当空间需要回收的时候，就把这个空间放到free_list链表的头部，以备下次使用

现在关注一下小整数对象池small_ints

static PyIntObject *small_ints[NSMALLNEGINTS + NSMALLPOSINTS];


int
_PyInt_Init(void)
{
    PyIntObject *v;
    int ival;
#if NSMALLNEGINTS + NSMALLPOSINTS > 0
    for (ival = -NSMALLNEGINTS; ival < NSMALLPOSINTS; ival++) {
              if (!free_list && (free_list = fill_free_list()) == NULL)
            return 0;
        /* PyObject_New is inlined */
        v = free_list;
        free_list = (PyIntObject *)v->ob_type;
        PyObject_INIT(v, &PyInt_Type);
        v->ob_ival = ival;
        small_ints[ival + NSMALLNEGINTS] = v;
    }
#endif
    return 1;
}

这段代码还是很清晰的，

从free_list中取空间，然后挨个初始化[-5,257）中所有的整数对象

然后加入small_ints这个指针数组中，下标就是对应的整数值

这里值得注意的是申请空间同样是通过fill_free_list实现

也就是说小整数对象也是在block_list中的

最后总结

当使用python整数的时候，申请空间不是24B一个一个申请的，而是一次申请992B

也就是说一次申请41个PyIntObject的空间

而小整数[-5, 257) 永远占据着内存空间，并且在Python启动的时候就完成初始化了

并且之后申请的整数空间Python也不会释放，而是放到整数空间池free_list里

就这样直到地老天荒~

想要试一下内存占用是否真的那么夸张？

来执行下下面代码

for i in range(44739242):
    pass

在系统监视器或者任务管理器里面查看一下内存占用

~= 1GB

EOF

参考文档

[1]. 《Python源码剖析》

0 许可 CC BY-SA 3.0

© 2017 Leo Howell

avatar
文章
阅读
粉丝
相关推荐
Nftables整型溢出（CVE-2023-0179）
767阅读
 · 
0点赞
如何实现 H5 秒开？
119k阅读
 · 
2.0k点赞
智能合约安全之整型溢出
318阅读
 · 
0点赞
Vue3.3 + Vite+ Element-Plus + TypeScript 从0到1搭建企业级后台管理系统（前后端开源）
154k阅读
 · 
1.0k点赞
面试官问我按钮级别权限怎么控制，我说v-if，面试官说再见
255k阅读
 · 
2.7k点赞