# 10.3 CPython 内存分配器

CPython 的内存分配器位于系统的内存分配器之上，并拥有它自己的分配算法。该算法与系统内存分配器类似，不同之处在于它是为 CPython 定制的：

* 大部分需要分配的内存都是小块且大小固定的内存，因为 `PyObject` 占 16 字节，`PyASCIIObject` 占 42 字节，`PyCompactUnicodeObject` 占 72 字节，`PyLongObject` 占 32 字节；
* `pymalloc` 内存分配器最多只能分配 256 KB 大小的内存，更大的内存需要交给系统的内存分配器去处理；
* `pymalloc` 内存分配器使用 GIL 而不是系统的线程安全性检查。

为了更好的解释这种情况，我们来做个类比：你可以想象有一个 CPython 足球俱乐部的主场体育场。为了帮助管理人群，CPython 足球俱乐部实现了一个系统，这个系统将体育场分为 A 至 E 区，每个区都有 1 至 40 排的座位：

图10.3.1 CPython 内存体育场

在体育场前端，第 1 至 10 排是较宽敞的高级座位，每排有 80 个座位。在体育场后端，第 31 至 40 排是经济舱座位，每排有 150 个座位。

Python 内存分配算法也具有类似的特点：

* 就像体育场有座位一样，`pymalloc` 算法中也有 **block**；
* 就像座位可以是高级、普通和经济型，这些内存块也都是一系列固定大小的。你不能带上自己的躺椅；
* 就像同样大小的座位被排成一排一样，也需要将同样大小的内存块放入 **pool** 中。

核心存储单元会记录 block 存储的位置和在 pool 中可用的 block 数量，这与体育场分配座位类似。当体育场一排满员后，就将使用下一排。当一个 pool 的 block 达到最大时，就会使用下一个 pool。而 pool 被分组存储在 **arena** 中，就像体育场会将数排座位分配到几个片区一样。

这种策略有以下几种优点：

1. 这种算法在 CPython 的主要应用场景（小内存且生命周期较短的对象）下有更好的性能；
2. 这种算法使用了 GIL 而不是系统的线程锁检测；
3. 算法使用内存映射（`mmap()`）而不是堆上内存分配。

## 相关源文件

以下是与内存分配器相关的源文件：

| 文件                             | 功能                    |
| ------------------------------ | --------------------- |
| Include/pymem.h                | PyMem 分配器 API         |
| Include/cpython/pymem.h        | PyMem 内存分配器配置 API     |
| Include/internal/pycore\_mem.h | 垃圾回收的数据结构及内部 API      |
| Objects/obmalloc.c             | 域分配器的实现和`pymalloc`的实现 |

表10.3.1 内存分配器相关的源文件

## 重要术语

以下是本章中你将遇到的一些重要术语：

* 申请的内存大小需要和 **block** 大小匹配；
* 相同大小的 block 要放进同一个内存池（**pool**）中；
* pool 被分组存储在 **arena** 中。

## Blocks，Pools 和 Arenas

单个 arena 是可分配的最大内存单元。CPython 中创建的 arenas 大小为 256 KB，与系统页的大小对齐。而系统页的边界是固定长度的连续内存块。

即便是在现代高速内存架构中，连续内存的加载速度也比碎片化的内存更快。所以使用连续的内存块是有益的。

### Arenas

**Arena** 需要在系统堆上进行内存分配，对于支持匿名内存映射的系统则会使用 [mmap()](https://man7.org/linux/man-pages/man2/mmap.2.html) 函数进行分配。内存映射有助于减少 arena 上的堆碎片。

下面是系统堆中四个 arenas 的可视化表示：

System Heap：系统堆

图10.3.2 Arenas的可视化表示

Arenas 对应数据结构 `arenaobject`:

| 字段            | 类型              | 用途                                           |
| ------------- | --------------- | -------------------------------------------- |
| address       | uintptr\_r      | arena 的内存地址                                  |
| pool\_address | block \*        | 指向要分配的下一个 pool 的指针                           |
| nfreepools    | uint            | arena 中可用 pool 的数量（已被释放的 pool 加从未被分配过的 pool） |
| ntotalpools   | uint            | arena 中 pool 的总数，不论其是否可用                     |
| freepools     | pool\_header\*  | 可用 pool 的单向链表                                |
| nextarena     | arena\_object\* | 下一个 arena（见注）                                |
| prevarena     | arena\_object\* | 前一个 arena（见注）                                |

表10.3.2 arenaobject 数据结构

**注**

一系列的 Arenas 通过其数据结构中的双向链表指针（`nextarena` 和 `prevarena`）链接在一起。

如果当前的 arena **未被分配**，就需要使用 `nextarena` 成员。`nextarena` 成员链接了所有独立、存储在全局变量 `unused_arena_objects` （一个单向链表）中的 arenas。

当这个 arena 与至少有一个可用 pool 的 arena 关联时，它的 `nextarena` 和 `prevarena` 都在双向链表 `usable_arenas` 中。这个链表根据 `nfreepools` 成员的值按升序排序。

### Pools

在 arena 中，最多可以为大小是 512 字节的 block 创建 pool。对于 32 位系统，block 大小的步长是 8 字节，所以总共有 64 种不同大小的 block：

| 以字节为单位的请求 | 分配的 block 大小 | 类型尺寸索引 |
| --------- | ------------ | ------ |
| 1-8       | 8            | 0      |
| 9-16      | 16           | 1      |
| 17-24     | 24           | 2      |
| 25-32     | 32           | 3      |
| ...       | ...          | ...    |
| 497-504   | 504          | 62     |
| 505-512   | 512          | 63     |

表10.3.3 32 位系统的 block 大小分类

对于 64 位系统，内存块大小的步长是 16 字节，所以有 32 种不同大小的 block：

| 以字节为单位的请求 | 分配的 block 大小 | 类型尺寸索引 |
| --------- | ------------ | ------ |
| 1-8       | 16           | 0      |
| 9-16      | 32           | 1      |
| 17-24     | 48           | 2      |
| 25-32     | 64           | 3      |
| ...       | ...          | ...    |
| 497-504   | 496          | 30     |
| 505-512   | 512          | 31     |

表10.3.4 64 位系统的 block 大小分类

Pool 的大小都是 4096 字节（4 KB），所以一个 arena 中总是包含 64 个 pool。

图10.3.3 Arena与Pool的关系

Pool 将按需分配。当没有可用 pool 可以用于请求的类型尺寸索引时，就将调配一个新的 pool。Arena 中有一个 "**高水位线**" 的概念，用于查询已经调配的 pool 数量。

Pool 共有 3 种状态：

1. 满载（Full）：pool 中所有可用的 block 都已被分配；
2. 部分使用（Used）：pool 已被分配，其中部分 block 已被设置，但还有剩余的空间；
3. 空闲（Empty）：pool 已被分配，但没有 block 被设置。

在 arena 中，高水位线位于最后一个被分配的 pool：

图10.3.4 高水位线示意图

Pool 包含数据结构 `poolp`，是结构体 `pool_header` 的静态内存分配。`pool_header` 类型有以下属性：

| 字段            | 类型             | 用途                             |
| ------------- | -------------- | ------------------------------ |
| ref           | uint           | 当前这个 pool 中分配的 block 数量        |
| freeblock     | block \*       | 指向这个 pool 空闲列表头的指针             |
| nextpool      | pool\_header\* | 指向下一个此类型尺寸的 pool 的指针           |
| prevpool      | pool\_header\* | 指向前一个此类型尺寸的 pool 的指针           |
| arenaindex    | uint           | 可用 pool 的单向链表                  |
| szidx         | uint           | 此 pool 的类型尺寸索引                 |
| nextoffset    | uint           | 未使用的 block 字节数                 |
| maxnextoffset | uint           | 在 pool 满载之前，`nextoffset` 的最大数量 |

表10.3.5 pool\_header结构体属性

特定大小的 pool 会使用双向链表在前后链接同一大小的 pool。当内存分配的发生时，通过这个双向链表就很容易从相同大小的 pool 之间跳转。当内存分配发生时，通过此双向链表可以很容易地在 arena 内相同大小的 pool 之间跳转。

### Pool Tables

在 arena 中 pool 的存储单元名为 **pool table**，pool table 是记录了已被部分使用的 pool 的双向循环链表头节点。

内存池表按 pool 的类型尺寸索引 `i` 进行分类。基于索引 `i`，`usedpools[i + i]` 指向所有已被部分使用且具有相同大小索引的 pool 双向链表头节点，

Pool table 有如下基本特性：

* 当一个 pool 饱和后，它将不再链接在 `usedpools[]` 中；
* 如果已饱和的 pool 中有一个 block 被释放了，pool 将重新回到部分使用的状态。此时会把刚刚释放过内存的 pool 链接到 `usepools[]` 的前面，这样下一次分配同样大小的内存时将复用刚刚释放内存的 block；
* 当一个 pool 变为空闲状态时，这个 pool 将从链表 `usedpools[]` 中脱离，同时链接到它所在的 arena 中的单向链表 `freepools` 前面。

### Blocks

在 pool 内，内存被分配到一个个 block 中。Block 有以下特征：

* 在一个 pool 中，可以分配和释放固定大小尺寸索引的 block；
* 在一个 pool 中，所有可用的 block 都链接在单向链表 `freeblock` 上；
* 当一个 block 被释放后，它会被重新插入到 `freeblock` 链表的最前面；
* 当 pool 初始化时，只有前两块内存被链接到 `freeblock` 链表上；
* 只要 pool 处于部分使用的状态，就至少有一个 block 可以用于内存分配。

这里是已被分配了部分内存的 pool 示意图，它由已使用、已被释放和未被分配过的 block 组合而成：

图10.3.5 已被部分使用的 Pool 示意图

## 内存块分配 API

当使用 `pymalloc` 的内存域请求一块内存时，将会调用 `pymalloc_alloc()` 函数。这个函数是插入断点，然后逐步调试代码去检验你对于 block、pool 和 arena 相关知识的好地方。

```c
// Object/obmalloc.c line 1590
static inline void*
pymalloc_alloc(void *ctx, size_t nbytes)
{
...
```

首先内存请求 `nbytes` 既不能为 0，也不能超过 `SMALL_REQUEST_THRESHOLD` (512 字节)，现以 `nbytes = 30` 为例进行说明：

```c
if (UNLIKELY(nbytes == 0)) {
    return NULL;
}
if (UNLIKELY(nbytes > SMALL_REQUEST_THRESHOLD)) {
    return NULL;
}
```

在 64 位系统上，可以求解出 30 字节 对应的 block 类型尺寸索引是 1，这对应第二行类型尺寸索引（17-32 字节）。

此目标的 pool 是 `usedpools[1 + 1] (即 usedpools[2])` ：

```c
uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
poolp pool = usedpools[size + size];
block *bp;
```

接下来，首先需要校验该类型尺寸索引的 pool 是否可用（包括部分使用）。如果 `freeblock` 链表在该 pool 的末尾，则说明 pool 中仍有未分配过内存的 block。

此时可以调用 `pymalloc_pool_extend()` 去扩展 `freeblock` 链表：

```c
    if (LIKELY(pool != pool->nextpool)) {
        /*
         * There is a used pool for this size class.
         * Pick up the head block of its free list.
         */
        ++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);
        }
    }
```

如果没有可用的 pool，就会创建一个新的 pool 并将其中第一个 block 返回。`allocate_from_new_pool()` 函数将创建一个新的 pool 并自动将它插入到 `usedpools` 中。

```c
    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;
}
```

最终，函数会返回一个新的 block 地址。

## 使用 Python Debug API

`sys` 模块包含了一个内部方法 `_debugmallocstats()`，用于获取在特定类型尺寸索引的 pool 中已使用的 block 数量。同时，它还将打印已分配和已回收的 arena 数量以及已用 block 的数量等数据。

你可以使用这个函数去查看运行时内存的使用情况：

```shell
$ ./python -c "import sys; sys._debugmallocstats()"

Small block threshold = 512, in 32 size classes.

class 	size 	num pools 	blocks in use 	avail blocks
----- 	---- 	--------- 	------------- 	------------
0 		16 		1 			181 			72
1 		32 		6 			675 			81
2 		48 		18 			1441 			71
...
2 free 18-sized PyTupleObjects * 168 bytes each = 336
3 free 19-sized PyTupleObjects * 176 bytes each = 528
```

上述输出展现了内存类型尺寸索引表、内存分配情况和其他的一些统计信息。