内存管理层次

‍

内存管理层次

​​

众所周知，计算机硬件资源由操作系统负责管理，内存资源也不例外。应用程序通过 系统调用 向操作系统申请内存，而 C 库函数则进一步将系统调用封装成通用的 内存分配器 ，并提供了 malloc 系列函数。

C 库函数实现的通用目的内存管理器是一个重要的分水岭，即内存管理层次中的 第 0 层 。此层之上是应用程序自己的内存管理，此层之下则是隐藏在冰山下方的操作系统部分。

操作系统内部是一个基于页表的虚拟内存管理器 (第 - 1 层)，以 页 ( page ) 为单位管理内存，CPU 内存管理单元 ( MMU ) 在这个过程中发挥重要作用。虚拟内存管理器下方则是底层存储设备 (** 第 - 2 层**)，直接管理物理内存以及磁盘等二级存储设备。

绿色部分则是 Python 自己的内存管理，分为 3 层：

• 第 1 层，是一个内存分配器，接管一切内存分配，内部是本文的主角 —— 内存池 ；
• 第 2 层，在第 1 层提供的统一 PyMem_XXXX 接口基础上，实现统一的对象内存分配 ( object.tp_alloc )；
• 第 3 层，为特定对象服务，例如前面章节介绍的 float 空闲对象缓存池；

Python 为什么不直接使用 malloc 系列函数，而是自己折腾一遍呢？原因主要是以下几点：

• 引入内存池，可化解对象频繁创建销毁带来的内存分配压力；
• 最大程度避免内存碎片化，提升内存利用效率；
• malloc 有很多实现版本，不同实现性能千差万别；

‍

按内存尺寸分类管理

在内存管理中，内存碎片的问题是难以避免的，而其问题产生的根源则是将不同尺寸内存块混合管理，将大块内存切分后再次分配的做法是罪魁祸首。

因此一般都采用按尺寸分类管理的方案-根据内存块尺寸，将内存空间划分成不同区域，独立管理。

​​

如图，内存被划分成小、中、大三个不同尺寸的区域，区域可由若干内存页组成，每个页都划分为统一规格的内存块。这样一来，小块内存的分配，不会影响大块内存区域，使其碎片化。

每个区域的碎片仍无法完全避免，但这些碎片都是可以被重新分配出去的，影响不大。

此外，通过优化分配策略，碎片还可被进一步合并。以小块内存为例，新内存优先从内存页 1 分配，内存页 2 将慢慢变空，最终将被整体回收。

在 Python 虚拟机内部，时刻有对象创建、销毁，这引发频繁的内存申请、释放动作。这类内存尺寸一般不大，但分配、释放频率非常高，因此 Python 专门设计 内存池 对此进行优化。

Python 以 512 字节为限，小于 512 的内存分配才会被内存池接管：

• 0 ，直接调用 malloc 函数；
• 1 ~ 512 ，由专门的内存池负责分配，内存池以内存尺寸进行划分；
• 512 以上，直接调动 malloc 函数；

同时，Python 并不会为每个尺寸的内存都准备一个独立内存池，原因如下：

• 内存规格有 512 种之多，如果内存池分也分 512 种，徒增复杂性；
• 内存池种类越多，额外开销越大；
• 如果某个尺寸内存只申请一次，将浪费内存页内其他空闲内存；

实际操作中，Python 以 8 字节为梯度，将内存块分为：8 字节、16 字节、24 字节，以此类推。总共 64 种：

请求大小	分配内存块大小	类别编号
1 ~ 8	8	0
9 ~ 16	16	1
17 ~ 24	24	2
25 ~ 32	32	3
…	…	…
497 ~ 504	504	62
505 ~ 512	512	63

以八字节内存块为例，只要请求的内存大小不超过 8 字节，Python 都在这个内存池为其分配一块 8 字节内存，就算只申请 1 字节内存也是如此。

这种做法好处显而易见，前面提到的问题均得到解决，还带来另一个好处：内存起始地址均以计算机字为单位对齐。计算机以 字 ( word ) 为单位访问内存，因此内存以字对齐可提升内存读写速度。字大小从早期硬件的 2 字节、4 字节，慢慢发展到现在的 8 字节，甚至 16 字节。

当然了，有得必有失，内存利用率成了被牺牲的因素，平均利用率为(1+8)/2/8*100%​ ，大约只有 56.25% ，但这只是 8 字节内存块的平均利用率。如果考虑所有内存块的平均利用率，其实数值并不低 —— 可以达到 98.65% 。计算方法如下：

# 请求内存总量
total_requested = 0
# 实际分配内存总量
total_allocated = 0

# 请求内存从1到512字节
for i in range(1, 513):
    total_requested += i
    # 实际分配内存为请求内存向上对齐为8的整数倍
    total_allocated += (i+7)//8*8

print('{:.2f}%'.format(total_requested/total_allocated*100))
# 98.65%

‍

pool

Python内存池实现源码位于Objects/obmalloc.c​，在源码中可以看到，对于64位系统，Python将内存块大小定义为16字节的整数倍。

#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

（不过为了方便描述，以下仍假设定义的是8字节）

Python中存在一个将类别编号转化为块大小的宏-INDEX2SIZE(I)

#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)

Python 每次申请一个 内存页 ( page )，然后将其划分为统一尺寸的 内存块 ( block )，一个内存页大小是 4K ：

#define SYSTEM_PAGE_SIZE        (4 * 1024)
#define SYSTEM_PAGE_SIZE_MASK   (SYSTEM_PAGE_SIZE - 1)

#define POOL_SIZE               SYSTEM_PAGE_SIZE
#define POOL_SIZE_MASK          SYSTEM_PAGE_SIZE_MASK

Python 将内存页看做是由一个个内存块组成的池子 ( pool )，内存页开头是一个 pool_header 结构，用于组织当前页，并记录页中的空闲内存块：

/* 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;       /* 下一个pool:next pool of this size class  */
    struct pool_header *prevpool;       /* 上一个pool: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      */
};

当 Python 通过内存池申请内存时，如果没有可用 pool ，内存池将新申请一个 4K 页，并进行初始化。注意到，由于新内存页总是由内存请求触发，因此初始化时第一个内存块便已经被分配出去了，并且随着随着内存分配请求的发起，空闲块将被分配出去。Python 将从灰色区域取出下一个作为空闲块，直到灰色块用光：

​​

当有内存块被释放时，比如第一块，Python 将其链入空闲块链表头。请注意空闲块链表的组织方式 —— 每个块头部保存一个 next 指针，指向下一个空闲块：

​​

因此一个 pool 在其生命周期内，可能处于以下 3 种状态：

• empty ，完全空闲 状态，内部所有内存块都是空闲的，没有任何块已被分配，因此 count 为 0 ；
• used ，部分使用 状态，内部内存块部分已被分配，但还有另一部分是空闲的；
• full ，完全用满 状态，内部所有内存块都已被分配，没有任何空闲块，因此 freeblock 为 NULL ；

同时pool的状态也决定了Python对其的处理策略：

• 如果 pool 完全空闲，Python 可以将它占用的内存页归还给操作系统，或者缓存起来，后续需要分配新 pool 时直接拿来用；
• 如果 pool 完全用满，Python 就无须关注它了，将它丢到一边；
• 如果 pool 只是部分使用，说明它还有内存块未分配，Python 则将它们以 双向循环链表 的形式组织起来；

‍

pool的组织

虚拟节点和双向循环链表

由于 used 状态的 pool 只是部分使用，内部还有内存块未分配，将它们组织起来可供后续分配。Python 通过 pool_header 结构体中的 nextpool 和 prevpool 指针，将他们连成一个双向循环链表：

​​

注意到，同个可用 pool 链表中的内存块大小规格都是一样的。

另外，为了简化链表处理逻辑，Python 引入了一个虚拟节点，这是一个常见的 C 语言链表实现技巧。一个空的 pool 链表是这样的，判断条件是 pool->nextpool == pool​ ：

​​

虚拟节点只参与链表维护，并不实际管理内存块。因此，无须为虚拟节点分配一个完整的 4K 内存页，64 字节的 pool_header 结构体足矣。实际上，Python 作者们更抠，只分配刚好足够 nextpool 和 prevpool 指针用的内存，手法巧妙得令人瞠目结舌，我们稍后再表。

used->full

Python 优先从链表第一个 pool 分配内存块，如果 pool 用满则将其从链表中剔除：

​​

当一个内存块 ( block ) 被回收，Python 根据块地址计算得到 pool 地址。计算方法是大概是这样的：将 block 地址对齐为内存页 ( pool ) 尺寸的整数倍，便得到 pool 地址，具体请参看源码中的宏定义 POOL_ADDR 。

得到 pool 地址后，Python 将空闲内存块插到空闲内存块链表头部。如果 pool 状态是由 完全用满 ( full ) 变为 可用 ( used )，Python 还会将它插回可用 pool 链表头部：

​​

插到可用 pool 链表头部是为了保证比较满的 pool 在链表前面，以便优先使用。位于尾部的 pool 被使用的概率很低，随着时间的推移，更多的内存块被释放出来，慢慢变空。因此，pool 链表明显头重脚轻，靠前的 pool 比较满，而靠后的 pool 比较空，正如上图所示。

used->empty

当一个 pool 所有内存块 ( block ) 都被释放，状态就变为 完全空闲 ( empty )。Python 会将它移出链表，内存页可能直接归还给操作系统，或者缓存起来以备后用：

​​

实际上，pool 链表任一节点均有机会完全空闲下来。这由概率决定，尾部节点概率最高，因此上图就这么画了。

‍

pool链表数组

Python 内存池管理内存块，按照尺寸分门别类进行。因此，每种规格都需要维护一个独立的可用 pool 链表。如果以 8 字节为梯度，内存块规格可分 64 种之多。

那么，如何组织这么多 pool 链表呢？最直接的方法是分配一个长度为 64 的虚拟节点数组：

​​

但实际上因为虚拟节点只参与维护链表结构，并不管理内存页。因此，虚拟节点其实只使用 pool_header 结构体中参与链表维护的 nextpool 和 prevpool 这两个指针字段，所以Python 作者们将虚拟节点想象成一个个卡片，将深蓝色部分首尾相接，最终转换成一个纯指针数组。数组在 Objects/obmalloc.c 中定义，即 usedpools 。每个虚拟节点对应数组里面的两个指针：

​​

接下来的一切交给想象力 —— 将两个指针前后的内存空间想象成自己的，这样就得到一个虚无缥缈的却非常完整的 pool_header 结构体（如下图左边虚线部分），我们甚至可以使用这个 pool_header 结构体的地址！由于我们不会访问除了 nextpool 和 prevpool 指针以外的字段，因此虽有内存越界，却也无伤大雅。

下图以一个代表空链表的虚拟节点为例，nextpool 和 prevpool 指针均指向 pool_header 自己。虽然实际上 nextpool 和 prevpool 都指向了数组中的其他虚拟节点，但逻辑上可以想象成指向当前的 pool_header 结构体：

​​

‍