第6篇CPython内存模型架构-Layer 2 - 内存池缓存阵列

在Python3.x中，Python内部默认的小块内存与大块内存的分界点是512字节，我们知道当小于512字节的内存请求，PyObject_Malloc会在内存池中申请内存，当申请的内存大于512字节，PyObject_Malloc的行为会蜕化为malloc的行为。例如当我们申请一个28字节的内存时，Python内部会在内存池寻找一块能满足需求的pool，并从中取出一个block，而不会去需找arena，这实际上事由pool和arena自身的属性确定的，pool有一个size概念的内存管理抽象体，一个pool中的block总是有确定的类型尺寸.pool_header结构体定义中有一个szidx就是指定了对应的pool分配出去的块的最小的块单位-类型尺寸(size class)，然而arena没有size idx的概念，这意味着同一个arena，在某个时刻，其托管的内存池集合可能是size class为32字节的内存池，而另一个时刻该内存池可能会被重新划分，变为64字节的block。

我们在讨论单个内存池时，有涉及池状态的概念。这里复习一下

used:池中至少由一个block已经正在使用，并且至少由一个block还未被使用，这种状态的内存池由CPython的usedpool统一管理
full状态：pool中所有block都已正在使用，这种状态的pool在arena托管的池集合内，但不再arena的freepools链表中。
empty状态：pool中的所有状态都未被使用，处于这个状态的pool的集合通过其pool_header结构体的nextpool构成一个链表，这个链表的表头就是arena_object结构体的freepools指针。

解读usedpools数组

Python内部通过使用usedpools数组，维护者所有处于used状态的pool。当申请内存size class为N时，Python会通过usedpools查找到与N对应的size idx可用的内存池，从中分配一个类型尺寸为N的块，我们看看Objects/obmalloc.c源代码的第1101行到1130行定义，其中的NB_SMALL_SIZE_CLASSES标识当前的CPython实现有多少个size class，对于CPython3.6之前表示有64种size class，CPython3.7之后有32种size class.

#define SMALL_REQUEST_THRESHOLD 512
#define NB_SMALL_SIZE_CLASSES   (SMALL_REQUEST_THRESHOLD / ALIGNMENT)

参考如下源代码的第1101行到1130行。

#define PTA(x)  ((poolp )((uint8_t *)&(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)
#if NB_SMALL_SIZE_CLASSES > 16
    , PT(16), PT(17), PT(18), PT(19), PT(20), PT(21), PT(22), PT(23)
#if NB_SMALL_SIZE_CLASSES > 24
    , PT(24), PT(25), PT(26), PT(27), PT(28), PT(29), PT(30), PT(31)
#if NB_SMALL_SIZE_CLASSES > 32
    , PT(32), PT(33), PT(34), PT(35), PT(36), PT(37), PT(38), PT(39)
#if NB_SMALL_SIZE_CLASSES > 40
    , PT(40), PT(41), PT(42), PT(43), PT(44), PT(45), PT(46), PT(47)
#if NB_SMALL_SIZE_CLASSES > 48
    , PT(48), PT(49), PT(50), PT(51), PT(52), PT(53), PT(54), PT(55)
#if NB_SMALL_SIZE_CLASSES > 56
    , PT(56), PT(57), PT(58), PT(59), PT(60), PT(61), PT(62), PT(63)
#if NB_SMALL_SIZE_CLASSES > 64
#error "NB_SMALL_SIZE_CLASSES should be less than 64"
#endif /* NB_SMALL_SIZE_CLASSES > 64 */
#endif /* NB_SMALL_SIZE_CLASSES > 56 */
#endif /* NB_SMALL_SIZE_CLASSES > 48 */
#endif /* NB_SMALL_SIZE_CLASSES > 40 */
#endif /* NB_SMALL_SIZE_CLASSES > 32 */
#endif /* NB_SMALL_SIZE_CLASSES > 24 */
#endif /* NB_SMALL_SIZE_CLASSES > 16 */
#endif /* NB_SMALL_SIZE_CLASSE

由于任意一个usedpools元素项的表达式为PT(x)等价于“PTA(x),PTA(x)”,那么usedpools的中间形式均等价如下

对于CPython 3.6之前的版本，按8字节对齐,上面的usedpools数组形式，等价于以下代码

static poolp usedpools[142] = {
    PTA(0), PTA(0), PTA(1), PTA(1), PTA(2), PTA(2), PTA(3), PTA(3),
    PTA(4), PTA(4), PTA(5), PTA(5), 
    ...PTA(70),PTA(70)
}

对于CPython3.7之后的版本，按16字节对齐,上面的usedpools数组形式，等价于以下代码

static poolp usedpools[78] = {
    PTA(0), PTA(0), PTA(1), PTA(1), PTA(2), PTA(2), PTA(3), PTA(3),
    PTA(4), PTA(4), PTA(5), PTA(5), 
    ...PTA(38),PTA(38)
}

好了，从任意一个PTA(x)的元素项,等价于

((poolp )((uint8_t *)&(usedpools[2*(x)]) - 2*sizeof(block *)))

其实整个usedpools数组的核心难点就是该PTA(x)的宏等价表达式。这个宏表达式意思是，指向usedpools[2x]的地址再向前偏移sizeof(pool_header.ref)+sizeof(block)后的地址，显然我们知道在x86_64的C编译器中刚好是16个字节,从pool_header结构体的定义发现从pool_header首个字节到nextpool字段首个字节的边界，刚好相差16个字节的偏移量。

我们如何理解整个usedpools的内部运行机制呢？相信看过《Python源码剖析：深度探索动态语言核心技术》这本的大伙们应该知道那本书会给出直观地给出下面的图例，包括国内任何有关CPython内存管理的源码分析的技术文章，基本上会引用到该图。但细心的读者有否提出个疑问这个图凭什么依据绘制出来的呢？对于刚接触C代码的程序员可能不太好理解。

来源:《Python源码剖析：深度探索动态语言核心技术》第445页

其实很简单，你在pymalloc_alloc函数或pymalloc_free函数，因为它们的上下文在函数都调用usedpools数组，只要在函数结束的return语句之前，尝试用for循环配合printf函数打印usedpools数组的元素项，如下代码

static inline void*
pymalloc_alloc(void *ctx, size_t nbytes)
{
    ...

    //测试代码
    for(int j=0;j<30;j++){
        printf("usedpools[%d] addr is %ld; usedpools[%d]->nextpool is %ld,
        usedpools[%d]->prevpool is %ld\n"
        ,j,&usedpools[j],j,usedpools[j]->nextpool,j,usedpools[j]->prevpool);
    }
    return (void *)bp;
}

在编译后,尝试在运行一次python解释器，在运行时随机打印前12项的usedpools元素，请留意观察如下代码的一些规律

Ok,还不明白的话！我们将上面的打印输出绘制成一个usedpools数组的前12项，这回一目了然吧。

我们看看如上图中有什么规律可循吧！！

下标为偶数的元素项usedpool[2x]->nextpool始终指向usedpools[2x-2]的内存地址。
下标为偶数的元素项usedpool[2x]->prevpool始终指向usedpools[2x-2]的内存地址。
下标为奇数的元素项usedpool[2x+1]->prevpool始终指向usedpools[2x+1-3] ,即usedpools[2x-2]的内存地。

备注:以上x是一个大于1的正整数,很奇妙的是不论什么索引，当前usedpool元素项的prevpool或nextpool指针的向前偏移单位均为2倍的block尺寸。

我们用一个源代码示例简述一下CPython如何调用usedpools数组中的可用内存池。例如当CPython尝试为一个内存量为28字节的Python对象，那么CPython会在底层执行如下源代码Objects/obmalloc.c的第1604行到1634行所示


static inline void*
pymalloc_alloc(void *ctx, size_t nbytes)
{
    ...
    //第一步：
    uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
    poolp pool = usedpools[size + size];
    block *bp;

    //第二步:比较pool->nextpool和当前pool的地址不同表明存在可用的内存池
    if (LIKELY(pool != pool->nextpool)) {
        ++pool->ref.count;
        bp = pool->freeblock;
        assert(bp != NULL);
    //第三步
    if (UNLIKELY((pool->freeblock = *(block **)bp) == NULL)) {
            // Reached the end of the free list, try to extend it.
            pymalloc_pool_extend(pool, size);
    }
    else {
        /* There isn't a pool of the right size class immediately
         * available:  use a free pool.
         */
        bp = allocate_from_new_pool(size);
    }

    return (void *)bp;
}

第一步:这是一个小型对象，28字节换算成size class就是32,那么size class换算成对应的szidx在不同版本的CPython版本中，会有不同的差别，见如下图,Cpython3.6之前的szidx是3,CPython3.7之后的szidx是1

第二步:CPython根据对应的szidx去访问usedpools，对于CPython3.6之前的是usedpool[3+3]，那么usedpools[6]->nextpool指向usedpools[4]的内存地址,并从usedpools[4]所指向的内存池(pool->freeblock)分配可用的32字节的块

对于CPython3.7之后来说就是usedpools[1+1]，那么usedpools[2]->nextpool自然就指向usedpools[0]，并从usedpools[0]所指向的内存池(pool->freeblock)分配可用的32字节的块。

第三步:若第二步usedpools若返回的内存池pool，并且pool中freeblock链表为NULL时，就会触发pymalloc_pool_extend(pool, size)函数，朝高地址方向偏移pool内部nextoffset指针划分新的块，并分配该块。

static void
pymalloc_pool_extend(poolp pool, uint size)
{
    if (UNLIKELY(pool->nextoffset <= pool->maxnextoffset)) {
        /* There is room for another block. */
        pool->freeblock = (block*)pool + pool->nextoffset;
        pool->nextoffset += INDEX2SIZE(size);
        *(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;
}

内存池缓存队列的初始化

OK，我们理解usedpools的内存模型后，还有个问题，就是CPython如何初始化我们的usedpools的呢？当CPython启动后，usedpool这个连续的内存空间并不存在任何指向可用内存池的指针。事实上CPython采取了延迟分配的策略，当确实开始申请小型对象的内存时，CPython才科室构建这个内存池，正如前面所提到的，当申请28个字节的内存时，实际上是申请32个字节的内存，假设CPython3.6之前的版本，也就找到usedpool[4]中的pool_header指针所指向的内存池，若在对应的位置没有找到任何pool_header指针，怎么办呢？请回忆一下前一篇所说过arenas对象，CPython会从usable_arenas链表中的第一个"可用"的arena对象中取出一个pool

更新中....