【CPython3.6源码分析】Python 内存管理机制

参考

内存策略

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
An object allocator for Python.
Here is an introduction to the layers of the Python memory architecture,
showing where the object allocator is actually used (layer +2), It is
called for every object allocation and deallocation (PyObject_New/Del).
This is also the place where the cyclic garbage collector operates
selectively on container objects.
_____ ______ ______ ________
[ int ] [ dict ] [ list ] ... [ string ] Python core |
+3 | <----- Object-specific memory -----> | <-- Non-object memory --> |
_______________________________ | |
[ Python's object allocator ] | |
+2 | ####### Object memory ####### | <------ Internal buffers ------> |
______________________________________________________________ |
[ Python's raw memory allocator (PyMem_ API) ] |
+1 | <----- Python memory (under PyMem manager's control) ------> | |
__________________________________________________________________
[ Underlying general-purpose allocator (ex: C library malloc) ]
0 | <------ Virtual memory allocated for the python process -------> |

=========================================================================
_______________________________________________________________________
[ OS-specific Virtual Memory Manager (VMM) ]
-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> |
__________________________________ __________________________________
[ ] [ ]
-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> |

通过obmalloc.c这段注释,我们可以获取到很多内容:

  • Python 内存管理,是分层次的
  • 对象的创建、销毁、 GC 都发生在+2层
  • 在最顶层,不同的对象有着不同的分配策略

从分层机制上看,似乎这个 allocator 不是固定的,那么是不是意味着可以自定义?
答案是肯定的,在 3.6 中可以通过环境变量 PYTHONMALLOC 改变分配器,甚至是自定义,
参考Environment variables

Default Memory Allocators

1
2
3
4
5
6
Python has a pymalloc allocator optimized for small objects (smaller or
equal to 512 bytes) with a short lifetime. It uses memory mappings called
“arenas” with a fixed size of 256 KiB. It falls back to PyMem_RawMalloc()
and PyMem_RawRealloc() for allocations larger than 512 bytes.

pymalloc is the default allocator of the PYMEM_DOMAIN_MEM (ex: PyMem_Malloc()) and PYMEM_DOMAIN_OBJ (ex: PyObject_Malloc()) domains.

如上,Py3.6 内存分配结构中,+1/+2 层都默认使用 pymalloc allocator。对 <= 512字节的小对象进行了优化,共用256kb字节的“arena”空间。

1
2
3
PYMEM_DOMAIN_RAW:PyMem_RawMalloc(),PyMem_RawRealloc() ,PyMem_RawFree()
PYMEM_DOMAIN_MEM:PyMem_Malloc(),PyMem_Realloc(), PyMem_Free()
PYMEM_DOMAIN_OBJ:PyObject_Malloc(),PyObject_Realloc() ,PyObject_Free()

目前存在 3 个 allocator 域,其中 PYMEM_DOMAIN_RAW 不需要持有GIL,另外两层默认都使用 pymalloc allocator,且必须持有 GIL。

+1/+2 层 API

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// obmalloc.c
typedef struct {
/* user context passed as the first argument to the 4 functions */
void *ctx;

/* allocate a memory block */
void* (*malloc) (void *ctx, size_t size);

/* allocate a memory block initialized by zeros */
void* (*calloc) (void *ctx, size_t nelem, size_t elsize);

/* allocate or resize a memory block */
void* (*realloc) (void *ctx, void *ptr, size_t new_size);

/* release a memory block */
void (*free) (void *ctx, void *ptr);
} PyMemAllocatorEx;

static PyMemAllocatorEx _PyMem = {
NULL, _PyObject_Malloc, _PyObject_Calloc, _PyObject_Realloc, _PyObject_Free
} _PyObject ;

void * PyMem_Malloc(size_t size) {
return _PyMem.malloc(_PyMem.ctx, size);
}
void * PyObject_Malloc(size_t size) {
return _PyObject.malloc(_PyObject.ctx, size);
}

因为 +1/+2 层 allocator 默认是 pymalloc,所以调用的都是相同 API,PyObject_ *。

SMALL_REQUEST_THRESHOLD

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
* Max size threshold below which malloc requests are considered to be
* small enough in order to use preallocated memory pools. You can tune
* this value according to your application behaviour and memory needs.
*
* Note: a size threshold of 512 guarantees that newly created dictionaries
* will be allocated from preallocated memory pools on 64-bit.
*
* The following invariants must hold:
* 1) ALIGNMENT <= SMALL_REQUEST_THRESHOLD <= 512
* 2) SMALL_REQUEST_THRESHOLD is evenly divisible by ALIGNMENT
*
* Although not required, for better performance and space efficiency,
* it is recommended that SMALL_REQUEST_THRESHOLD is set to a power of 2.
*/
#define SMALL_REQUEST_THRESHOLD 512
#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)

SMALL_REQUEST_THRESHOLD变量,定义了小对象的阈值,默认为 512 字节。

ALIGNMENT

1
2
3
4
5
6
7
8
9
10
/*
* Alignment of addresses returned to the user. 8-bytes alignment works
* on most current architectures (with 32-bit or 64-bit address busses).
* The alignment value is also used for grouping small requests in size
* classes spaced ALIGNMENT bytes apart.
*
* You shouldn't change this unless you know what you are doing.
*/
#define ALIGNMENT 8 /* must be 2^N */
#define ALIGNMENT_SHIFT 3

定义地址对齐大小,默认为8字节对齐。同时还用作 classes 中小对象的分组,即 8 个一组。

分配策略摘要

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
* For small requests, the allocator sub-allocates <Big> blocks of memory.
* Requests greater than SMALL_REQUEST_THRESHOLD bytes are routed to the
* system's allocator.
对于小对象,分配器将从 block 中分配,超过阈值512字节,将调用 malloc 直接分配

* Small requests are grouped in size classes spaced 8 bytes apart, due
* to the required valid alignment of the returned address. Requests of
* a particular size are serviced from memory pools of 4K (one VMM page).
* Pools are fragmented on demand and contain free lists of blocks of one
* particular size class. In other words, there is a fixed-size allocator
* for each size class. Free pools are shared by the different allocators
* thus minimizing the space reserved for a particular size class.
小对象,按大小进行分组,因为对齐原因,间隔8个字节,即8、16、24字节。

* For small requests we have the following table:
*
* Request in bytes Size of allocated block Size class idx
* ----------------------------------------------------------------
* 1-8 8 0
* 9-16 16 1
* ... ... ...
* 505-512 512 63
*
* 0, SMALL_REQUEST_THRESHOLD + 1 and up: routed to the underlying
* allocator.
*/

也就是说,对于小对象,会阶段性的分配固定大小的字节数。例如 10 字节,会分配一个 idx=1, size=16字节的block。对于 0 或 大于阈值的对象,会委托给底层的 malloc 进行分配。

block

1
2
3
4
5
6
7
8
9
10
11
12
/* When you say memory, my mind reasons in terms of (pointers to) blocks */
typedef uint8_t 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 */
uint szidx; /* block size class index */
...
};
typedef struct pool_header *poolp;

可以发现,一个 block 就是一个地址,就是一个 pool 中的一部分。

Pool

pool 结构

1
2
3
4
5
6
7
8
/*
* 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.
*/
#define SYSTEM_PAGE_SIZE (4 * 1024)
#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)
#define POOL_SIZE SYSTEM_PAGE_SIZE /* must be 2^N */
#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK

pool 是一组大小相等的 block 的集合,一个 pool 大小默认为一个系统页表大小,即 4k。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef uint8_t block;

struct pool_header {
union { block *_padding;
uint count; } ref; /* number of allocated blocks */
block *freeblock; /* 下一个可用 block 起始位置 */
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; /* 下一个可用 block 的偏移量 */
uint maxnextoffset; /* 最大 有效 偏移量 */
};
typedef struct pool_header *poolp;

pool_header 指向 pool 的起始位置,除了 header 本身所占空间,剩下的都是 block 可用内存。
pool->szidx 指定了 class size index,即指定了这个 pool 所有 block 的大小。

pool 状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
used state
初始状态,至少有一个 block 在用,至少有一个 block 未空
通过 pool_header->nextpool/prevpool 组成双向链表
只剩一个未用时,使用 malloc 会转换为 full state
只剩一个在用时,使用 free 会转换为 empty state
full state
全部在用
从 usedpools[] list 解链,不与任何东西链接在一起
在转换为 used state 之前,nextpool/prevpool 是没有意义的
在 free 之后,会转换为 used state,并重新放入 usedpools[] 表头
empty state
全部未用
不在 usedpools[] 链上
其 nextpool 指向对应的 arena_object's 表头
prevpool 是没有意义的
如果下一次使用的 class size 与之前相同,就能跳过一些初始化环节

Pool 有三种状态,并且存在一个 usedpools[],将可以使用的 pool,组成双向链表。

Pool init

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
init_pool:
/* 处理 usedpools[] 此处略,见 Arena.usedpools */
pool->ref.count = 1; // 已分配数 1
if (pool->szidx == size) {
bp = pool->freeblock;
pool->freeblock = *(block **)bp;
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}
// 设置 class size index
pool->szidx = size;
// 计算实际 block 大小:(size+1) << ALIGNMENT_SHIFT=3
size = INDEX2SIZE(size);
// 第一个 blcok 位置,跳过 header 部分
bp = (block *)pool + POOL_OVERHEAD;
// 下一个可用 blcok 偏移量,跳过 头+ 1个 block
pool->nextoffset = POOL_OVERHEAD + (size << 1);
// 最大偏移量:池大小 - 最后一个 block
pool->maxnextoffset = POOL_SIZE - size;
// 下一个可用 block 起始位置
pool->freeblock = bp + size;
// 构建 freeblock 链表头(尾)
*(block **)(pool->freeblock) = NULL;
if (use_calloc)
memset(bp, 0, nbytes);
// 返回第一个 block 指针
return (void *)bp;

初始化完成后,内存布局见下图:
一个 pool 初始化后的布局
上图,实线是指针指向,虚线是数值等于。

freeblock 链表

1
2
*(block **)p = lastfree = pool->freeblock;
pool->freeblock = (block *)p;

释放 block 时,pool->freeblock 指向下一个可用的 block 起始位置,但 *freeblock为 NULL。
将要释放的 p,所指向地址的值 *p设置为 freeblock。通过一种巧妙地利用删除了的 block,构建链表。见图:
释放了 block 后的自由 block 链表

Arena

1
2
3
4
5
6
7
8
9
10
11
#define ARENA_SIZE              (256 << 10)     /* 256KB */

struct arena_object {
uintptr_t address; // pool 起始地址
block* pool_address; // 指向下一个 pool
uint nfreepools; // 可用的 pool 数
uint ntotalpools; // pool 总数
struct pool_header* freepools; // 可用 pool 指针
struct arena_object* nextarena;
struct arena_object* prevarena;
};

通过 malloc/mmap 获取虚拟地址空间,每个 arenas 默认为 256k。而默认 pool 为 4k,意味着每个 arena 默认有64个 pool。通过内部的两个指针,组成跟 pool 类似的链式结构。

pymalloc allocator 会创建一个 256kb 的固定的大小,作为 arena 维护的空间。用完后,会再再次创建一倍空间,默认是没有上限的。

arena 内部只是管理着 pool 的集合,并未指定集合中 pool 的类型。意味着其 pool->szidx 可以是不同大小。

arena 链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 单链表,未使用的 arena
static struct arena_object* unused_arena_objects = NULL;

// 双向链表,部分可用的 arena
static struct arena_object* usable_arenas = NULL;
/*
所有 pool 都未用:
nextarena 指向下一个 都未用的 arena
unused_arena_objects 为表头,指向 当前
所有 pool 都已用:
nextarena/prevarena 无意义,不在链上
部分 pool 可用:
nextarena/prevarena 与 其他 usable_arenas 组成双向链表
usable_arenas 为表头,指向 当前
*/

某一时刻的 arena 链
注意,所有的 arena 都在数组 arenas 中。通过 maxarenas 记录个数。

new_arena()

1
2
3
4
5
6
7
8
9
10
11
#define INITIAL_ARENA_OBJECTS 16
static struct arena_object* arenas = NULL;
static uint maxarenas = 0;

static struct arena_object* new_arena(void){
if (unused_arena_objects == NULL) {
/* 不存在 未使用的 arena 链表,先构建一个 */
...
}
/* 获取一个 unused_arena_objects */
}

申请 arena 大概分为两步,第一步先判断是否需要扩充未使用的 unused_arena_objects,第二获取到unused_arena_objects。此处,调用位置在 Alloc 不存在可用 pool

创建 unused_arena_objects

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static struct arena_object* new_arena(void){
/* 若 不存在可用的 arena,就先申请一个 arena 头部的空间 */
if (unused_arena_objects == NULL) {
uint i;
uint numarenas;
size_t nbytes;
// 申请的 arena 数目,默认 16 个,每次都翻倍
numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;
if (numarenas <= maxarenas)
return NULL; /* overflow */
// 16个 arena 头部数据长度 sizeof(arena_object)
nbytes = numarenas * sizeof(*arenas);
// PyMem_Raw 调用 realloc
arenaobj = (struct arena_object *)PyMem_RawRealloc(arenas, nbytes);
arenas = arenaobj;

/* arenas中,所有 pool 都未用, nextarena 指向下一个 arena */
for (i = maxarenas; i < numarenas; ++i) {
arenas[i].address = 0; /* 此时不存在 pool集合 */
/* 构造链表,表头 arena->next 为 NULL */
arenas[i].nextarena = i < numarenas - 1 ?
&arenas[i+1] : NULL;
}
// unused_arena_objects 指向 表头
unused_arena_objects = &arenas[maxarenas];
maxarenas = numarenas;
}

申请一组 arena 头部空间。unused_arena_objects 指向的是数组尾部,即”表头”。

存在 unused_arena_objects

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
static struct arena_object* new_arena(void){
/* 弹出未使用 arenae 链表 unused_arena_objects 第一个 */
arenaobj = unused_arena_objects;
unused_arena_objects = arenaobj->nextarena;

/* 申请 arena_object 管理的内存
_PyObject_Arena.alloc 是一个区分平台的函数
Linux 上,如不用 nmap,会直接调用 malloc(256kb)
*/
address = _PyObject_Arena.alloc(_PyObject_Arena.ctx, ARENA_SIZE);
if (address == NULL) {
/* 创建失败,把 arena 放回未用链表头 */
arenaobj->nextarena = unused_arena_objects;
unused_arena_objects = arenaobj;
return NULL;
}
// 改变 arena 指向的 pool 地址
arenaobj->address = (uintptr_t)address;

++narenas_currently_allocated;
++ntimes_arena_allocated;
if (narenas_currently_allocated > narenas_highwater)
narenas_highwater = narenas_currently_allocated;

/* 可用 pool 指针,释放 pool 时用到 */
arenaobj->freepools = NULL;
/* pool_address 指向第一个 pool */
arenaobj->pool_address = (block*)arenaobj->address;
/* nfreepools 为可用的 pool 数 256k/4k = 64 */
arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE;

// 将 pool 起始地址调整为系统页的边界
excess = (uint)(arenaobj->address & POOL_SIZE_MASK);
if (excess != 0) {
// 弹出一个 立马使用
--arenaobj->nfreepools;
// 改变 下一个指向位置
arenaobj->pool_address += POOL_SIZE - excess;
}
arenaobj->ntotalpools = arenaobj->nfreepools;
return arenaobj;
}

创建新的 arena 时,判断存在可用的 unused_arena_objects,将执行上面的代码。把一个 arena 从链中摘下,申请256kb内存,构建出64个 pool 集合。返回该 arena,跳转到Alloc 不存在可用 pool

arena 中的 pool 链

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct arena_object {
uintptr_t address; // 自身起始地址
block* pool_address; // 指向下一个 pool
struct pool_header* freepools; // 未用 pools 表头
};

struct pool_header {
block *freeblock; /* 下一个可用 block 起始位置 */
struct pool_header *nextpool; /* next pool of this size class */
struct pool_header *prevpool; /* previous pool "" */
};

/*
全部未用 empty
pool 中所有 block 都未使用
通过 freepools + nextpool,构成单向链表
部分使用 used
pool 中存在被使用,且存在未被使用 block
通过 usedpools[] 维护链表
全部使用 full
各自独立,不存在 链
*/

arena 中 pool 集合

注意了,arena 中的 pool 并非相同大小,而 pool->nextpoll 是相同大小的 szidx。那么,这就意味着,必须有个地方,把 arena pool size 给关联起来,那就是 usedpools。

usedpools

指针数组定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef struct pool_header *poolp;

// NB_SMALL_SIZE_CLASSES = SMALL_REQUEST_THRESHOLD / ALIGNMENT = 512/8 = 64
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)
...
}
// 等效于
#define PTA(x) ((poolp )((uint8_t *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
static poolp usedpools[2 * 64] = {
PTA(0), PTA(0), PTA(1), PTA(1),
...
}
/*
指针,`block *` 为四个字节
那么 usedpools[2*(x=3)],所指向的值为 usedpools[6] - 8
整个 usedpools 数组,都是指针,都是4个字节
那么,`- 8`,就是位置左移 2,即指向了`usedpools[4]`
意思就是,usedpools[6] == &usedpools[4]
*/

再来看 pool_header 的定义。

pool 结构体定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct pool_header {
union { block *_padding;
uint count; } ref; /* number of allocated blocks */
block *freeblock; /* 下一个可用 block 起始位置 */
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; /* 下一个可用 block 的偏移量 */
uint maxnextoffset; /* 最大 有效 偏移量 */
}
/*
ref + *freeblock,也正好是 8 个字节
pool->nextpool,就是 pool 指针后移8个字节
pool->prevpool,就是 pool 指针后移8+4个字节
*/

巧合的 8 字节,意味着有阴谋!

trick

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
usedpools[6] == &usedpools[6] -8 == &usedpools[4]
>>> 初始状态 usedpools[6] 就是指向 usedpools[4]

usedpools[6]->nextpool == &usedpools[4] +8 == usedpools[6]
>>> 初始状态 usedpools[6]->nextpool 就是 usedpools[6]
>>> 初始状态 usedpools[i+i] == usedpools[i+i]->nextpool // 注意这里,很重要

usedpools[6]->prevpool == &usedpools[4] +12 == usedpools[7]
>>> 初始状态 usedpools[6]->prevpool,就是 usedpools[7]

执行 usedpools[6]->nextpool = 一个 i=3 的 pool
>>> 就是对 usedpools 数组赋值,将位置 6 存储为一个 pool 地址
>>> 再然后,就可以直接用 usedpools[6],获取到该 pool 地址

执行 usedpools[6]->prevpool = 一个 i=3 的 pool
>>> 就是对 usedpools 数组赋值,将位置 7 存储为一个 pool 地址

嘿,饶了大半圈,结果原来时这么回事。用两个位置指针,模拟出 pool_head 的结构。
初始状态[i+i] == [i+i]->next,一旦调用 [i+i]->next= pool,那么就可以直接取用 [i+i]。

再来看看如何对 usedpools 进行操作。

add by Alloc init

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize){

init_pool:
next = usedpools[size + size]; /* 此时 [6] = &[4] */
pool->nextpool = next; // pool->next = &[4]
pool->prevpool = next; // pool->prev = &[4]
next->nextpool = pool; // &[4]->next == [6] >>> [6] = pool
next->prevpool = pool; // &[4]->prev == [7] >>> [7] = pool
/* 结果就是:
A->nextpool == &[4]
A->prevpool == &[4]

&[4]->nextpool == [6] == A
&[4]->prevpool == [7] == A
*/
}

Pool init 中,我们省略了部分代码如上。可以发现,在初始化 pool 时,构造出一个双向链表,其中只有两个节点,A 与 虚拟的 usedpools。

add by Free full

Free block 时,遇到一个 full poll,会将其挂载到 usedpools[] 双向链表上。下面分两种情况查看:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void _PyObject_Free(void *ctx, void *p) {
next = usedpools[size + size]; // &[4]
prev = next->prevpool; // [7]
pool->nextpool = next; // A->nextpool == &[4]
pool->prevpool = prev; // A->prevpool == [7] == &[4]
next->prevpool = pool; // [7] = pool
prev->nextpool = pool; // [6] = pool
}
/* usedpools 为初始状态,结果等于 init pool。
A->nextpool == &[4]
A->prevpool == &[4]

&[4]->nextpool == [6] == A
&[4]->prevpool == [7] == A
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static void _PyObject_Free(void *ctx, void *p) {
next = usedpools[size + size]; // A
prev = next->prevpool; // A->prevpool == &[4]

/* insert pool before next: prev <-> pool <-> next */
pool->nextpool = next; // B->nextpool == A
pool->prevpool = prev; // B->prevpool == &[4]
next->prevpool = pool; // A->prevpool = B
prev->nextpool = pool; // &[4]->next == [6] = B
}
/* usedpools 已经挂载了一个 A,现在新挂一个 B
A->nextpool == &[4]
A->prevpool == B

B->nextpool == A
B->prevpool == &[4]

&[4]->nextpool == [6] == B
&[4]->prevpool == [7] == A

注意,不是直接挂载到头上,而是插入其中
&[4] -next-> B -next-> A
&[4] <-prev- B <-prev- A

但,通过 usedpools[6] 获取到的却是刚刚插入的 B
*/

remove by Alloc full

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize){
/* 假设:
A->nextpool == &[4]
A->prevpool == &[4]

&[4]->nextpool == [6] == A
&[4]->prevpool == [7] == A
*/
/* Pool is full, unlink from used pools. */
next = pool->nextpool; // &[4]
pool = pool->prevpool; // &[4]
next->prevpool = pool; // [7] = &[4]
pool->nextpool = next; // [6] = &[4]
...
}

在 Pool 满了之后,只是简单的将自己从双向链表中 摘掉。
如果只有 1 个 usedpool,就会把 usepools 恢复到最开始的状态。

remove by Free empty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static void _PyObject_Free(void *ctx, void *p) {
/* 假设:
A->nextpool == &[4]
A->prevpool == B

B->nextpool == A
B->prevpool == &[4]

&[4]->nextpool == [6] == B
&[4]->prevpool == [7] == A
*/
next = pool->nextpool; // A
prev = pool->prevpool; // &[4]
next->prevpool = prev; // A->prevpool = &[4]
prev->nextpool = next; // &[4]->nextpool = A
}

/* 结果是:
&[4] -next-> A
&[4] <-prev- A
*/

在 Free 时,遇到 emtyp pool,如果 usedpool,不止一个,会将自己从双向链表中 摘掉。

PyObject_Alloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static void * _PyObject_Malloc(void *ctx, size_t nbytes) {
return _PyObject_Alloc(0, ctx, 1, nbytes);
}
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize) {
size_t nbytes = nelem * elsize;
/* The small block allocator. */
if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) {
...
}
void *result;
if (use_calloc)
result = PyMem_RawCalloc(nelem, elsize);
else
result = PyMem_RawMalloc(nbytes);
return result;
}

从这里,可以看出,小对象与大对象的处理方式不同,大对象直接调用 mallco。下面,主要看小对象的处理方式。

Alloc 存在可用 pool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize)
{
// 前提条件,小对象
size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; // 计算 pool->szidx
pool = usedpools[size + size]; // 获取可用 szidx= size 的可用pool

/* usedpools 中存在可用 pool */
if (pool != pool->nextpool) {
++pool->ref.count; // 增加 使用计数
bp = pool->freeblock; // 可用的 blcok 起始地址

// 将 freeblock 在链表上移动,如果未到达尾部,则直接返回
if ((pool->freeblock = *(block **)bp) != NULL) {
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}

// 已经到达 freelist 尾部,但存在 未使用过的 block
if (pool->nextoffset <= pool->maxnextoffset) {
// 下一个可用 block 起始位置,指向上一个 block 的结束为止
pool->freeblock = (block*)pool + pool->nextoffset;
// 偏移位置后移 block size
pool->nextoffset += INDEX2SIZE(size);
// 再次设置 freelist 链表尾
*(block **)(pool->freeblock) = NULL;
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}
/* Pool is full, unlink from used pools. */
next = pool->nextpool;
pool = pool->prevpool;
next->prevpool = pool;
pool->nextpool = next;
if (use_calloc)
memset(bp, 0, nbytes);
return (void *)bp;
}
}

注意其中起始的两句,pool = usedpools[size + size] if(pool != pool->nextpool)

在前面 usedpools 中,我们已经知道:初始状态 usedpools[i+i] == usedpools[i+i]->nextpool。
那么,意味着此次,进入 if 的条件就是存在可用的 pool。

Alloc 不存在可用 pool

1
2
3
4
5
6
7
8
9
10
11
static struct arena_object* usable_arenas = NULL;
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize)
{
// 前提条件 pool == pool->nextpool
if (usable_arenas == NULL) {
/* 创建一个 arena */
usable_arenas = new_arena();
usable_arenas->nextarena =
usable_arenas->prevarena = NULL;
}

Alloc 不存在可用 free pool,即 usedpools 中不存在可用 pool。若不存在 可用arena,调用 new_arena() 获取一个 arena。接着在把它前后指针都置为NULL.。

Alloc 创建 pool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize)
{
/* 前提条件:
pool == pool->nextpool
usable_arenas != NULL
*/
/* Try to get a cached free pool. */
pool = usable_arenas->freepools;
if (pool != NULL) {
/* 找到一个可用的 pool */
usable_arenas->freepools = pool->nextpool;
--usable_arenas->nfreepools;
// 处理 =0 的情况,从链中摘掉 usable_arenas
...
init_pool: {
/* 初始化 pool */
...
return (void *)bp;
}
}
/* Carve off a new pool. */
assert(usable_arenas->nfreepools > 0);
assert(usable_arenas->freepools == NULL);
pool = (poolp)usable_arenas->pool_address;
...
goto init_pool;
}

new_arena() 中,初始化时设定了arenaobj->freepools = NULL;,因此直接走 Carve off a new pool 环节。

Carve off a new pool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize)
{
/* 前提条件:
usable_arenas != NULL
usable_arenas->freepools == NULL
*/
/* Carve off a new pool. */
pool = (poolp)usable_arenas->pool_address;

/* arenaindex: pool 所在 arena 位于 arenas 数组中的序号 */
pool->arenaindex = (uint)(usable_arenas - arenas);
assert(&arenas[pool->arenaindex] == usable_arenas);
pool->szidx = DUMMY_SIZE_IDX; // 0xffff
// 指向下一个 pool
usable_arenas->pool_address += POOL_SIZE;
// 调整剩余数量
--usable_arenas->nfreepools;

if (usable_arenas->nfreepools == 0) {
assert(usable_arenas->nextarena == NULL ||
usable_arenas->nextarena->prevarena ==
usable_arenas);
/* 全部Pool 用完,Unlink the arena */
usable_arenas = usable_arenas->nextarena;
if (usable_arenas != NULL) {
usable_arenas->prevarena = NULL;
assert(usable_arenas->address != 0);
}
}
goto init_pool;
}

其中,涉及到arenaindex的使用,见PyObject_Free.address_in_range

小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
static void *
_PyObject_Alloc(int use_calloc, void *ctx, size_t nelem, size_t elsize) {
// 如果是小对象,<256字节,使用内存池 arena
if ((nbytes - 1) < SMALL_REQUEST_THRESHOLD) {
size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT; // 计算 pool->szidx
pool = usedpools[size + size]; // 获取可用 szidx= size 的可用pool

/* usedpools 中存在可用 pool */
if (pool != pool->nextpool) {
bp = pool->freeblock; // 分配 block
/* 判断处理 freeblocks 链表状态:
存在已释放,未到达 freelist 尾部
已经到达 freelist 尾部,但存在 free block
Pool is full, unlink from used pools.
*/
...
}

/* 不存在可用的pool, 那么就找一个 arena 创建 pool */
if (usable_arenas == NULL) {
/* 扩充 arenas 空间 */
usable_arenas = new_arena();
usable_arenas->nextarena = usable_arenas->prevarena = NULL;
}

/* 从表头的 arena 中获取一个 pool */
pool = usable_arenas->freepools;
if (pool != NULL) {
/* 找到一个可用的 pool */
usable_arenas->freepools = pool->nextpool;
--usable_arenas->nfreepools;
// 处理 =0 的情况,从链中摘掉 usable_arenas
...
init_pool: {
/* 初始化 pool */
...
return (void *)bp;
}
}

/* 获取失败,就创建一个 pool,然后转入:初始化 */
assert(usable_arenas->nfreepools > 0);
assert(usable_arenas->freepools == NULL);
pool = (poolp)usable_arenas->pool_address;
...
goto init_pool;
}

// 否则,使用 mallcoc
return PyMem_RawMalloc(nbytes);
}

复杂的逻辑,主要难点在于:

  • 通过已经释放的区域,当做链表的中间环节
  • pool 内部指向,一个 pool 初始化后布局
  • freeblocks 链表,释放了 block 后的自由 block 链表
  • arena 中的 pool 分布,arena 中 pool 集合
  • arena 集合的分布,arena 集合的分布

PyObject_Free

1
2
3
4
5
6
7
8
9
10
static void _PyObject_Free(void *ctx, void *p) {
// 找到最近的 pool 地址
pool = POOL_ADDR(p);
// 根据 pool,找到 arena,判断 p 是否在其中
if (address_in_range(p, pool)) {
... // 小对象
return;
}
PyMem_RawFree(p);
}

下面主要查看小对象的处理。

POOL_ADDR

1
2
3
4
5
6
7
pool = POOL_ADDR(p);

/* 向下,找到距离 p 最近的 pool 地址 */
#define POOL_ADDR(P) ((poolp)_Py_ALIGN_DOWN((P), POOL_SIZE))

/* Round pointer "p" down to the closest "a"-aligned address <= "p". */
#define _Py_ALIGN_DOWN(p, a) ((void *)((uintptr_t)(p) & ~(uintptr_t)((a) - 1)))

address_in_range

1
2
3
4
5
6
7
8
9
static bool ATTRIBUTE_NO_ADDRESS_SAFETY_ANALYSIS
address_in_range(void *p, poolp pool)
{
// &arenas[pool->arenaindex] == pool 所在 arena
uint arenaindex = *((volatile uint *)&pool->arenaindex);
return arenaindex < maxarenas &&
(uintptr_t)p - arenas[arenaindex].address < ARENA_SIZE &&
arenas[arenaindex].address != 0;
}

获取到 pool 所在 arena 地址,在通过 .address 获取到 pool 的起始地址。在创建 unused_arena_objects 中,所有初始 arena.address 都为0。通过计算指针差值,能就能得出 p 是否在 arena 中。

Free full pool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
static void _PyObject_Free(void *ctx, void *p) {
// 前提条件:address_in_range(p, pool)

// 设置 freeblocks 链表
*(block **)p = lastfree = pool->freeblock;
pool->freeblock = (block *)p;

// lastfree 有效,表明当前 pool 未满
if (lastfree) {
...
}

// 当前 pool 处于 full 状态,释放 block 后,需要转为 used 状态
// 将 pool 放入 usedpools 头部
--pool->ref.count;
size = pool->szidx;
next = usedpools[size + size];
prev = next->prevpool;
/* insert pool before next: prev <-> pool <-> next */
pool->nextpool = next;
pool->prevpool = prev;
next->prevpool = pool;
prev->nextpool = pool;
return;
}

如上,当 pool 已满时,释放后 block 后,需要将 pool 连接到可用的 pools 上。

Free used pool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void _PyObject_Free(void *ctx, void *p) {
// 前提条件:address_in_range(p, pool)
*(block **)p = lastfree = pool->freeblock;
if (lastfree) {
/* ref.count > 1 表明,还有其他的 pool 可使用 */
if (--pool->ref.count != 0) {
return;
}

/* ref.count==1, free 之后就 emtpy了,应脱离 usedpools[] */
next = pool->nextpool;
prev = pool->prevpool;
next->prevpool = prev;
prev->nextpool = next;

/* 把 pool 关联到 arena->freepools 链上 */
struct arena_object* ao = &arenas[pool->arenaindex];
pool->nextpool = ao->freepools;
ao->freepools = pool;
uint nf = ++ao->nfreepools;

/* All the rest is arena management. */
...
}

当释放一个 block,若 Pool 本身就是 used 状态,无需更多操作。反之,若 Pool 从 used 变为 empty 时,不仅要处理 pool,脱离 usedpools 链表,还要处理 arena。

Free arena management

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void _PyObject_Free(void *ctx, void *p) {
// 前提条件:address_in_range(p, pool)
*(block **)p = lastfree = pool->freeblock;
if (lastfree) {
/* All the rest is arena management. */

// ntotalpools > pool->ref.count > 1,不止一个且未满
struct arena_object* ao = &arenas[pool->arenaindex];
uint nf = ++ao->nfreepools;

// Case 1: pool 全部 free,销毁 arena
if (nf == ao->ntotalpools) {}

// Case 2: 仅此一个 pool 可用,挂载到 usable_arenas 链上
if (nf == 1) {}

// Case 3: 如果当前 pool <= next->nf,什么都不干
...
// Case 4:调整 usable_arenas 链表顺序,快满的 arena 首先被使用
...
return ;
}
}

在 pool 从 used 转变为 empty 时,arena 有可能出现 全部 free,以及,仅此一个 pool 可用两种状态。当满足仅此一个pool 为 usable 时,又要挂载链表,调整顺序。

Free a block then arena empty

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
if (nf == ao->ntotalpools) {
// Case 1: pool 全部 free,销毁 arena

/* Case 1. First unlink ao from usable_arenas. */
assert(ao->prevarena == NULL ||
ao->prevarena->address != 0);
assert(ao ->nextarena == NULL ||
ao->nextarena->address != 0);

/* 调整 usable_arenas 链表 */
if (ao->prevarena == NULL) {
// ao 在表头
usable_arenas = ao->nextarena;
assert(usable_arenas == NULL ||
usable_arenas->address != 0);
}
else {
// ao 不在表头
assert(ao->prevarena->nextarena == ao);
ao->prevarena->nextarena =
ao->nextarena;
}

if (ao->nextarena != NULL) {
// ao 不在末尾
assert(ao->nextarena->prevarena == ao);
ao->nextarena->prevarena =
ao->prevarena;
}

// 挂载到 unused_arena_objects 链表
ao->nextarena = unused_arena_objects;
unused_arena_objects = ao;

/* Free the entire arena. ao->address */
_PyObject_Arena.free(_PyObject_Arena.ctx,
(void *)ao->address, ARENA_SIZE);
ao->address = 0; /* mark unassociated */
--narenas_currently_allocated;

UNLOCK();
return;
}

如上,在 free block 遇到一个 emtpy 的 arena 时,会调整 used/unused 链表,并且 free(arena)。

Free a block then arena can use

1
2
3
4
5
6
7
8
9
10
11
12
13
// Case 2: 仅此一个 pool 可用,挂载到 usable_arenas 链上
if (nf == 1) {

ao->nextarena = usable_arenas;
ao->prevarena = NULL;
if (usable_arenas)
usable_arenas->prevarena = ao;
usable_arenas = ao;
assert(usable_arenas->address != 0);

UNLOCK();
return;
}

仅此一个 Pool 可用,那么意味着arena 之前不在 usable_arenas 链表上,直接挂载上去。

Free a block then 调整 usable 链表

1
2
3
4
5
6
7
// Case 3: 如果当前 pool <= next->nf,什么都不干
if (ao->nextarena == NULL ||
nf <= ao->nextarena->nfreepools) {
return;
}

// Case 4:调整 usable_arenas 链表顺序,快满的 arena 首先被使用

如上,调整 usable 顺序,始终保持 most full arena 在链表头,最先被使用。

小结

Python 主要围绕几张链表来管理内存:

  • free block 单链表,由 pool 管理
  • free pool 单链表,由 usedpools 管理
  • usable arena 双向链表,由 usable_arenas 管理
  • unusable arena 单链表,由 unused_arena_objects 管理

free 操作的对象是 block,blok 受 pool 管理,pool 在 arena 中,所有arena 构成数组 arenas。

  • free block 后,要将 block 挂载到 pool->freeblocks 上
  • 如果 pool 变为 used,就把 pool 挂载到 usedpools[] 上
    • 如果所在 arena,仅此一个可用,还得把 arena 从 unused_arena 脱离,挂载到 usable 上
  • 如果 pool 变为 empty,就把 pool 从 usedpools 脱离,挂载到 arena->freepools 上
    • 如果所在 arena 都 empty,还得把 arena 从 usable_arenas 脱离,释放内存,挂载到 unused_arena 上

Python 小块内存池全景