第4篇:CPython的内存模型架构-Layer 2-内存池
前言
我们前一篇，已经讨论了内存块，这是CPython内存管理模型里面一个基本的逻辑单位，当然block有明确的基本单位那就是8个字节，而对于不同Python对象来说，有着不同类型尺寸(size class)来描述小型Python对象的内存分配需求，内size class index维系内存池和当前块用于什么size class的小型Python对象内存分配的关系。
备注：还有一个重要的分水岭，由于CPython3.6是基于8字节的内存对齐，CPython3.7之后的版本是基于16字节对齐，那么我们勾勒出内存池的逻辑示意图就要分情况讨论啦。
下面我们深入讨论内存池，在此之前请回顾一下这个CPython内存架构图.
Layer 1与Layer 2的内存APIs的交互
池(Pools)
池封装大小相同的块，每个池的大小为4KB,可以查看源代码
/*
* The system's VMM page size can be obtained on most unices with a
* getpagesize() call or deduced from various header files. To make
* things simpler, we assume that it is 4K, which is OK for most systems.
* It is probably better if this is the native page size, but it doesn't
* have to be. In theory, if SYSTEM_PAGE_SIZE is larger than the native page
* size, then `POOL_ADDR(p)->arenaindex' could rarely cause a segmentation
* violation fault. 4K is apparently OK for all the platforms that python
* currently targets.
*/
/*源文件Objects/obmalloc.c的第885行*/
#define SYSTEM_PAGE_SIZE (4 * 1024)
#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)
....
*
* Size of the pools used for small blocks. Should be a power of 2,
* between 1K and SYSTEM_PAGE_SIZE, that is: 1k, 2k, 4k.
*/
/*源文件Objects/obmalloc.c的第920行*/
#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */
#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK
每个池对象由一个叫struct pool_header的结构体来表示，源代码的Objects/obmalloc.c从938到948行的就是池头部定义
/* 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 */
};
typedef struct pool_header *poolp;
其中重要的字段
- ref表示已分配内存块的数量
- freeblock)：标识下一次分配block的起始位置
- nextpool和prevpool:它们是struct pool_header类型的指针分别指向当前池对象下一个内存池和上一个内存池，和其他池构成一个双重链表，这样，即使在不同的池中，该算法也可以轻松找到给定块类型大小的可用空间。
- arenaindex:表示当前pool所属的arena的索引
- nextoffset: 表示freeblock的下一次偏移的位置
- maxnextoffset：表示当前pool最后一个block未知距离pool的偏移，这意味当nextoffset大于maxnextoffset时，就没有可分配的block了
其中理解struct pool_header的nextpool和prevpool字段这个较为简单，它们构成如下关于pool_header的双向链表:
理解单个内存池的难点就是pool_header如何根据freeblock和nextoffset和maxnextoffset字段来管理整个4KB的内存空间，因为pool的整个头部结构，我任你怎么打肿脸充胖子，也无法填满4KB的空间，唯一肯定的是pool_header会以8或16字节填充到4KB空间的低地址位置。那么CPython究竟如何去让pool_header的字段成员去描述4KB空间中,除了pool_header外的剩余内存空间？
CPython3.9的源代码文件Objects/obmalloc.c，从CPython2.5到目前Cpython3.9没有定义一个独立的函数描述单个池初始化的过程，其中关于初始化pool_header结构体的代码位于allocate_from_new_pool(size)函数内部位于1571行到1578行。
allocate_from_new_pool(size)是一个初始化arenas对象和pool_heade链表的函数，我们这里仅抽取其中相关的代码，封装在一个自定义的block* pool_init(poolp poop,uint szidx)函数内部，如下代码所示
#include <stdio.h>
#define uint unsigned int
#define SIZEOF_VOID_P 4
#if SIZEOF_VOID_P > 4
#define ALIGNMENT 16 /* must be 2^N */
#define ALIGNMENT_SHIFT 4
#else
#define ALIGNMENT 8 /* must be 2^N */
#define ALIGNMENT_SHIFT 3
#endif
#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)
#define _Py_SIZE_ROUND_UP(n, a) (((size_t)(n) + \
(size_t)((a) - 1)) & ~(size_t)((a) - 1))
#define POOL_SIZE (4*1024)
#define POOL_OVERHEAD _Py_SIZE_ROUND_UP(sizeof(struct pool_header), ALIGNMENT)
/* When you say memory, my mind reasons in terms of (pointers to) blocks */
typedef unsigned char 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 */
};
typedef struct pool_header *poolp;
/*
* Initialize the pool header, set up the free list to
* contain just the second block, and return the first
* block.
*/
block* pool_init(poolp pool,uint szidx){
block* bp;
uint size=0;
pool->ref.count=1
pool->szidx = szidx;
size = INDEX2SIZE(szidx);
bp = (block *)pool + POOL_OVERHEAD;
pool->nextoffset = POOL_OVERHEAD + (size << 1);
pool->maxnextoffset = POOL_SIZE - size;
pool->freeblock = bp + size;
//构建 freeblock 链表头(尾)
*(block **)(pool->freeblock) = NULL;
return bp;
}
int main()
{
poolp pool;
block* firstBlock=pool_init(pool,1);
return 0;
}
我们这里假设内存池分配的block类型尺寸(size class)是16字节，我们建议读者自行使用类似gdb工具调试上面的演示代码，会有一个深刻的认识。
对于CPython 3.6之前的单个内存池内的初始内存布局如下图所示，由于是基于8字节对齐的，因此szidx字段的索引值，自然根据换算公式 16/8-1=1，我们来看看内存池初始化时,pool_header各个字段成员是如何变化的。
- pool->szidx=1,表示这个池用于适用于分配9～16字节的任意python对象。那么CPython可以通过一个usedpool数组通过该szidx=1找到该内存池，然后该内存池再查找可用的内存块。
- INDEX2SIZE(size)是一个将size class idx转换为size class的宏，此时局部变量size=16
-
宏POOL_OVERHEAD表示当前pool_header基于8字节对齐后的大小,这个基于不同的编译器或机器环境有所差异，我的机器显示48字节。
需要明确的是内存池初始化位于堆内存中，因此基于堆向高地址端增长的特性，上面图我特意表明这个细节。
- bp指针指向就是仅挨着POOL_OVERHEAD的 第一个的内存块，这个内存块会在内存池初始化时返回给上一级调用函数pymalloc_alloc，并且pool_header中引用计数器会记账为1,因此此时bp指针所指向该块的状态是使用中(Using)，
这是目前网上其他基于Python2.5或2.7为蓝本的CPython 3.x源码解读文章没有明确提到的。 - freeblock,在内存池初始化时,指向紧挨着第一个内存块的第二个未使用内存块的地址(如下图的0x8429a0)
- pool_init函数中的return语句之前的,这条语句其实类似于memset函数将freeblock所指向的内存块的所有字节位重置为0,因为pool本身是一个指针，所以源代码使用解引二级指针的语法才能修改freeblock所指内存块中内容。
*(block **)(pool->freeblock) = NULL;
为什么要设定为NULL呢?
理解这个问题放在内存池初始化阶段理解，可能有些难，因为内存池的回收被使用过(Used)的块，由freeblock指针跟踪,此时设为NULL目地就是为构建 freeblock的单链表,只不过freeblock链表尚未有何被回收的块加入，所以它指向尾指针NULL。
顺带提一下,对于CPython 3.7之后的单个内存池的初始内存布局如下图所示，由于是基于16字节对齐的，因此szidx字段的索引值，自然根据换算公式 16/16-1=0
从内存池分配更多的内存块
为了加深对内存池的理解,若从上面例子基于8字节对齐的内存池,连续分配更多块会是什么情况？假定当内存池接收到来自pymalloc_alloc连续分配4个size class为16的内存请求，池分配内存块的过程是一个朝向nextoffset不断指向高地址的过程，也是nextoffset和maxnextoffset的距离越来越少的过程，现在我们看看pymalloc_alloc从检索内存池的算法。
首先，我们这里的重点是理解单个内存池位多次分配内存块的过程，其他过程代码暂不理会,我日后的文章会提到，这里我们只需认为pymalloc_alloc函数已经从其数组得到了池头部字段为szidx=0的内存池并赋值给变量pool。
随即递增引用计数,即语句++pool->ref.count。这里的重点是理解pymalloc_alloc在向可用的内存池申请内存块的优先策略是
- 优先尝试在状态为使用中(Using)的内存池中调配可用的的内存块,上图第1612行到1620行的细节就说明了这一点。
- 若没可适合当前size class的内存池或内存池的所有块正在使用中(using),就会额外调用allocate_from_new_pool分配新的内存池并返回内存块(该函数是一个由arenas对象管理内存分配的函数接口，这里暂不讨论)
我们这里看回第1621行到1623行的代码细节，随后内存池在初始化后，每当pymalloc_alloc向内存池请求内存块，只需将pool_header的freeblock返回所指向的处女块(即图中的第1618行)，随即内存池为确保后续的内存能如常分配，pool_header的freeblock会移动到下一个内存块的起始地址，如下代码所示
// Called when freelist is exhausted. Extend the freelist if there is
// space for a block. Otherwise, remove this pool from usedpools.
static void
pymalloc_pool_extend(poolp pool, uint size)
{
if (UNLIKELY(pool->nextoffset <= pool->maxnextoffset)) {
/* 确保下一次有可用的内存块分配 */
pool->freeblock = (block*)pool + pool->nextoffset;
pool->nextoffset += INDEX2SIZE(size);
//设置*freeblock 的动作正是建立离散自由 block 链表的关键所在
*(block **)(pool->freeblock) = NULL;
return;
}
/* Pool is full, unlink from used pools. */
poolp next;
next = pool->nextpool;
pool = pool->prevpool;
next->prevpool = pool;
pool->nextpool = next;
}
为加深理解内存池的分配细节，我特意制作了一段简单的动画
当nextoffset>maxnextoffset表示该池的所有内存块已用尽(fulled),那么默认python内存分配器会执行两个动作
- 要么在内存池双重链表查找其他可用池返回未使用的内存块。
- 要么当前内存池链表所有内存池都耗尽(fulled),就要求arenas对象向第1层的PyMem函数接口分配更多的对内村给arenas对象，并创建新的内存池。
此时，我们顺带理顺一下内存池目前提到的3种状态。
使用中(Using)：池内有1个以上(包含1个)的块已分配,即块正在使用，换句话说，初始化的内存池的状态就是使用中.
满载(Full):池内所有块正在使用。如下图所示
上面的解析单个内存池的已经是目前全网最透彻的了，我们就要讨论一下内存池如何管理回收使用过的内存块。
内存池回收块
我们知道Python中的一切对象，即C实现中的PyObject都有一个引用计数器，当引用计数为0时，被引用的Python对象就会从堆内存中被释放,。在Python生命周期内，实际上针对任何低于512字节的Python对象的内存释放，并没有将内存空间返回给操作系统的虚拟内存管理器(VVM)，而是将使用过的内存块返回给内存池，并由内存池的头部字段freeblock指针重新指向该内存块。
关于NULL指针的设定
我们来看看前文关于内存池初始化和内存池分配的相关C代码出现的这条语句`*(block **)(pool->freeblock) = NULL;所做的操作实质上,在当前freeblock指针指向的内存块(16字节)的前8个字节(x86_64平台的指针占用8个字节的内存空间)的所有二进制为重置为0，要理解内存池回收内存块。用一个示例演示能什么设计的巧妙之处在哪里。
内存池有5个内存块正在使用，我们假设pymalloc_free依次传递的内存块顺序是小型对象Py3、Py2的指针，
当回收Py3这个内存块时，如下图所示，pymalloc_free会将当前池freeblock所指向的内存指针，保存到一个临时指针变量lastfree。
由于lastfree指针副本持有的是指向NULL指针，此时last副本赋值给Py3所在的内存块，换句说就是让Py3所在的内存块指向NULL指针，而pool->freeblock = (block *)p;这条语句就让pool_header的freeblock指针指向了Py3所在的节点，咦！如果你熟悉数据结构的话，这实质上就是单链表表头插入元素的算法嘛！
当回收Py2对象的内存块，同理如上所述。
到回收第二个元素，其实整个freeblock指针，它维护的是一个单链表，这样的设计非常精妙,因为freeblock指针所指向的内存块一直都位于链表的头部，试想一下在频繁的内存块分配和回收交替进行中，内存的分配的时间开销始终为O(1)。
而NULL的设定，目地就是让链表中的最初被内存的那个内存块指向NULL指针，就是充当一个末尾节点。用单链表来管理回收的内存其实并不是什么新鲜的事物，这样的算法其实在C底层的malloc也有使用叫做隐式链表，你有兴趣的话，可以完这两篇文章。
《C堆内存管理-概念篇》
《C堆内存管理-原理篇》
而CPython内存池的妙哉就是，它采用链表的表头插入算法，pymalloc_alloc函数向内存池申请可用的内存块时，像上面情况往往是返回链表首部的内存块即可。
小结
我们了解了单个内存池的基本操作原理，没错，你要摸透CPython的内存模型架构，其实还有一段历程要走。我们有了堆、栈、内存块、CPython内存模型1层和2层单个内存池的内存分配和回收，这一系列背景知识，那么我们深入了解arenas对象和内存池缓冲队列(usedpool数组)这些复杂的实现，就得心应手啦。
