Python內(nèi)存管理介紹
CPython內(nèi)存管理器
CPython源碼包的功能分類
此文是按照源碼Python3.9來寫，其中有些assert語句與一些不必要的宏字段會刪除，保留核心的邏輯并添加注釋，方便自己和大家理解。在代碼中都會注明源碼出處方便大家完整閱讀。
| 目錄 | 概要 |
|---|---|
| Demo | 采用了Python的演示應(yīng)用程序 |
| Doc | 文檔 |
| Grammer | Python的語法文件 |
| Include | 編譯Python時引用的各種頭文件 |
| Lib | 標準附加庫 |
| Mac | Mac用的工具等 |
| Misc | 很多文件的集合（如gdbinit和vimrc等） |
| Modules | Python的C語言擴展模塊 |
| Objects | Python的對象用的C語言代碼 |
| PC | 依存于OS等環(huán)境的程序 |
| PCbuild | 構(gòu)造Win32和x64時使用 |
| Parser | Python用的解析器 |
| Python | Python的核心 |
Python的內(nèi)存管理架構(gòu)
Python是一門動態(tài)的、一切皆對象的語言，這些內(nèi)存申請可能會產(chǎn)生大量小的內(nèi)存，為了加快內(nèi)存操作和減少內(nèi)存碎片化，使用Python自己的內(nèi)存管理器，叫PyMalloc。
# Objects/obmalloc.c 代碼注釋
/* 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),
unless the object-specific allocators implement a proprietary allocation
scheme (ex.: ints use a simple free list). This is also the place where
the cyclic garbage collector operates selectively on container objects.
Object-specific allocators
_____ ______ ______ ________
[ int ] [ dict ] [ list ] ... [ string ] Python core |
+3 | <----- Object-specific memory -----> | <-- Non-object memory --> | # 對象特有的內(nèi)存分配器
_______________________________ | |
[ Python's object allocator ] | |
+2 | ####### Object memory ####### | <------ Internal buffers ------> | # Python對象分配器
______________________________________________________________ |
[ Python's raw memory allocator (PyMem_ API) ] |
+1 | <----- Python memory (under PyMem manager's control) ------> | | # Python低級內(nèi)存分配器
__________________________________________________________________
[ Underlying general-purpose allocator (ex: C library malloc) ]
0 | <------ Virtual memory allocated for the python process -------> | # 通用的基礎(chǔ)分配器（如glibc的malloc等）
=========================================================================
_______________________________________________________________________
[ OS-specific Virtual Memory Manager (VMM) ]
-1 | <--- Kernel dynamic storage allocation & management (page-based) ---> | # OS特有的虛擬內(nèi)存管理器
__________________________________ __________________________________
[ ] [ ]
-2 | <-- Physical memory: ROM/RAM --> | | <-- Secondary storage (swap) --> | # 物理內(nèi)存和交換目的地（如HDD等）
*/
PyDict_New() // 第三層
PyObject_GC_New() // 第二層
PyObject_Malloc() // 第二層
new_arena() // 第一層
malloc() // 第零層
////////////////////////////////////////以下2層屬于操作系統(tǒng)范疇，不在討論范圍/////////////////////////////////
通用的基礎(chǔ)分配器（0層）
512字節(jié)是CPython的閾值
//Objects/obmalloc.c
#define SMALL_REQUEST_THRESHOLD 512
#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
/* Largest positive value of type Py_ssize_t. */
#define PY_SSIZE_T_MAX ((Py_ssize_t)(((size_t)-1)>>1))
static void *
_PyObject_Malloc(void *ctx, size_t nbytes)
{ // 走Python的分配器，函數(shù)進去就會有判斷(0,512]的才使用
void* ptr = pymalloc_alloc(ctx, nbytes);
if (LIKELY(ptr != NULL)) {
return ptr;
}
// 大于512字節(jié)走C的malloc，函數(shù)進去進做了越界判斷,Py_ssize_t為閾值
ptr = PyMem_RawMalloc(nbytes);
if (ptr != NULL) {
raw_allocated_blocks++;
}
return ptr;
}
0: 直接調(diào)用 malloc 函數(shù)1 ~ 512: 由Python的內(nèi)存池負責分配，內(nèi)存池以內(nèi)存尺寸進行劃分512以上: 直接調(diào)動 malloc 函數(shù)
在源代碼中以PyMem_為前綴的所有函數(shù)是封裝C語言提供給Python語法使用的，其核心使用的就是第0層malloc之類的C庫函數(shù)。
通常Python沒有對小塊內(nèi)存的內(nèi)存池的大小做任何的限制
當Python在WITH_MEMORY_LIMITS編譯符號打開的背景下進行編譯時，Python內(nèi)部的另一個符號會被激活，這個名為SMALL_MEMORY_LIMIT的符號限制了整個內(nèi)存池的大小，同時，也就限制了可以創(chuàng)建的arena的個數(shù)。
在默認情況下，不論是Win32平臺，還是unix平臺，這個編譯符號都是沒有打開的，所以通常Python都沒有對小塊內(nèi)存的內(nèi)存池的大小做任何的限制。
[obmalloc.c]
#ifdef WITH_MEMORY_LIMITS
#ifndef SMALL_MEMORY_LIMIT
#define SMALL_MEMORY_LIMIT (64 * 1024 * 1024) /* 64 MB -- more? */
#endif
#endif
#ifdef WITH_MEMORY_LIMITS
#define MAX_ARENAS (SMALL_MEMORY_LIMIT / ARENA_SIZE)
#endif
CPython讓我們只需要提供類型和數(shù)量
有了以下的宏定義，我們寫代碼的時候只需要提供類型和數(shù)量，而不用自己去計算具體需要申請多少空間
//Include/pymem.h
#define PyMem_New(type, n) \
( ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
( (type *) PyMem_Malloc((n) * sizeof(type)) ) )
#define PyMem_NEW(type, n) \
( ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
( (type *) PyMem_MALLOC((n) * sizeof(type)) ) )
#define PyMem_Resize(p, type, n) \
( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
(type *) PyMem_Realloc((p), (n) * sizeof(type)) )
#define PyMem_RESIZE(p, type, n) \
( (p) = ((size_t)(n) > PY_SSIZE_T_MAX / sizeof(type)) ? NULL : \
(type *) PyMem_REALLOC((p), (n) * sizeof(type)) )
#define PyMem_Del PyMem_Free
#define PyMem_DEL PyMem_FREE
內(nèi)存碎片問題
每次申請內(nèi)存的時候一定不會每次都遇到剛好的塊去分配，那么一下一大塊內(nèi)存會被切割使用，那么中間會產(chǎn)生很多小的但是可能不在會被使用的碎片（但是整個加起來也是一個大的可使用的塊），而且每次查找合適的塊需要遍歷整個堆，所以為了減少碎片和快速分配內(nèi)存，我們需要內(nèi)存管理。
Python內(nèi)存管理的劃分
小于512字節(jié)的內(nèi)存申請由Python的低級分配器接管（空白內(nèi)存，raw memory），做了3級層次的劃分，依次為block、pool、arena
block是Python內(nèi)存管理的最小單元，其中他的大小與pool_head的szidx一致，而且采用的Best-fit分配策略
Best-fit分配策略：返回大于等于 size 的最小分塊 pool是管理一類規(guī)格的block，是具有size概念的內(nèi)存管理抽象體，有pool_head的一個szidx管理。（當然她還有狀態(tài)的管理后面會介紹）
arena是可以管理多個pool，每個pool的規(guī)格可以各不相同。（他也有自己的狀態(tài)管理后面會介紹）
pool與arena頭與boby連接的不同
Python低級內(nèi)存分配器（1層）
現(xiàn)在來到的是真正Python的內(nèi)存管理談?wù)摰牟糠至耍琍ython內(nèi)存管理做了哪些處理
減少內(nèi)存碎片的問題
上面的block概念的提出，是為了有效改善內(nèi)存碎片的問題，但是不可能解決的
不可能讓每次分配都遍歷整個堆
所以arena_head、pool_head都比較復(fù)雜，其中都維護了多條鏈表來把開銷從O(N)降低到O（1） Python分配器主要是處理<512字節(jié)小內(nèi)存，頻繁的分配/釋放一定是會浪費
Python的大部分基礎(chǔ)類引入了緩存池的機制用于管理小塊內(nèi)存的申請和釋放，提供
pymalloc_alloc、pymalloc_realloc、pymalloc_free三個接口比如字典有80大小的數(shù)組作為緩存池
列表也有80大小的數(shù)組作為緩存池
arena
“第一層的核心就是創(chuàng)建arena
arena的大小
arena的默認值是256K
#define ARENA_BITS 18 /* 256 KiB */
#define ARENA_SIZE (1 << ARENA_BITS)
arena頭結(jié)構(gòu)體
// Objects/obmalloc.c
struct arena_object {
// arena_object地址
uintptr_t address;
// 將arena的地址用于給pool使用而對齊的地址
block* pool_address;
// 該arena中可用pool的數(shù)量
uint nfreepools;
// 該arena中所有pool的數(shù)量
uint ntotalpools;
// 使用完畢的pool，用單鏈表維護
struct pool_header* freepools;
// 雙向鏈表指針
struct arena_object* nextarena;
struct arena_object* prevarena;
};
為什么arena_object需要address和pool_address2個字段？
“上面內(nèi)存管理的劃分提到arena_object與body是不連續(xù)的，圖4
pool_header被申請時，它所管理的block集合的內(nèi)存一定也被申請了；所以他是連續(xù)的一塊空間
但是當aerna_object被申請時，它所管理的pool集合的內(nèi)存則沒有被申請；arena需要指針相連
所以address指定的是頭數(shù)據(jù)，pool_address指定的是真實數(shù)據(jù)開始的位置，所以不同
new_arena
類型
“uintptr_t 是由從 C99 開始導(dǎo)入的 stdint.h 提供的，在將 C 指針轉(zhuǎn)化成整數(shù)時，它起著很大的作用。uintptr_t 正是負責填補這種環(huán)境差異的。uintptr_t 會根據(jù)環(huán)境變換成 4 字節(jié)或 8 字節(jié)，將指針安全地轉(zhuǎn)化，避免發(fā)生溢出的問題。
// uchar 和 uint 分別是 unsigned ××× 的略稱。
#undef uchar
#define uchar unsigned char /* 約8位 */
#undef uint
#define uint unsigned int /* 約大于等于16位 */
#undef ulong
#define ulong unsigned long /* 約大于等于32位 */
#undef uptr
#define uptr Py_uintptr_t
typedef uchar block;
//[obmalloc.c]
// arenas管理著arena_object的集合
static struct arena_object* arenas = NULL;
// 當前arenas中管理的arena_object的個數(shù)
static uint maxarenas = 0;
// “未使用的”arena_objectd單向鏈表
static struct arena_object* unused_arena_objects = NULL;
// “可用的”arena_object鏈表
static struct arena_object* usable_arenas = NULL;
// 初始化時需要申請的arena_object的個數(shù)
#define INITIAL_ARENA_OBJECTS 16
//[obmalloc.c]
static struct arena_object*
new_arena(void)
{
struct arena_object* arenaobj;
uint excess; /* number of bytes above pool alignment */
// 初始化默認值為NULL，需要生成arena_objects
if (unused_arena_objects == NULL) {
uint i;
uint numarenas;
size_t nbytes;
// 確定申請arena的個數(shù)，初始化得到16個，之后會2倍擴容
numarenas = maxarenas ? maxarenas << 1 : INITIAL_ARENA_OBJECTS;
// 溢出判斷
if (numarenas <= maxarenas)
return NULL;
nbytes = numarenas * sizeof(*arenas);
if (nbytes / sizeof(*arenas) != numarenas)
return NULL;
// 需要使用0層的分配器分配numarenas個數(shù)arena_object（頭信息）所需的raw memory
// 分配完后arenas作為靜態(tài)全局變量
arenaobj = (struct arena_object *)realloc(arenas, nbytes);
if (arenaobj == NULL)
return NULL;
arenas = arenaobj;
// 把以上分配的raw memory，維護到unused_arena_objects單向鏈表中
for (i = maxarenas; i < numarenas; ++i) {
// arena地址，如果沒有分配就用0作為標識符
arenas[i].address = 0;
// 最后一個arena指向NULL，其余都指向下一個指針，初始化分配是一個連續(xù)的單鏈表
arenas[i].nextarena = i < numarenas - 1 ? &arenas[i+1] : NULL;
}
/* 反映到全局變量中 */
unused_arena_objects = &arenas[maxarenas];
maxarenas = numarenas;
}
////////////////////////////////////以上完成了arenas 的初始化,如下圖所示//////////////////////////////////////////
// 從unused_arena_objects鏈表中取出一個“未使用的”arena_object（表頭）
arenaobj = unused_arena_objects;
unused_arena_objects = arenaobj->nextarena;
assert(arenaobj->address == 0);
// 分配一塊arena內(nèi)存，256KB
// 這時候address有具體地址了
arenaobj->address = (uptr)malloc(ARENA_SIZE);
++narenas_currently_allocated;
if (arenaobj->address == 0) {
// 分配失敗，讓把拿出來的頭放回到unused_arena_objects鏈表中
arenaobj->nextarena = unused_arena_objects;
unused_arena_objects = arenaobj;
return NULL;
}
///////////////////////////////以上是分配arena空間與arena_object連接///////////////////////////////////////
// 將arena內(nèi)的空間分割為各個pool
arenaobj->freepools = NULL;
/* pool_address 對齊后開頭pool的地址
nfreepools 對齊后arena中pool的數(shù)量 */
arenaobj->pool_address = (block*)arenaobj->address;
arenaobj->nfreepools = ARENA_SIZE / POOL_SIZE;
// 內(nèi)存對齊
excess = (uint)(arenaobj->address & POOL_SIZE_MASK);
if (excess != 0) {
--arenaobj->nfreepools;
arenaobj->pool_address += POOL_SIZE - excess;
}
arenaobj->ntotalpools = arenaobj->nfreepools;
return arenaobj;
}
/////////////////////////////////////////以上是劃分pool/////////////////////////////////////////////////////
1、初始化16個arena_object
2、擴容
3、分配arena空間，就是arena表頭與真實數(shù)據(jù)相連
4、給arena劃分pool，excess是什么-內(nèi)存對齊會消耗一個pool
結(jié)構(gòu)體 arena_object 的成員 pool_address 中存有以 4K 字節(jié)對齊的 pool 的地址。
在此使用 POOL_SIZE_MASK 來對用 malloc() 保留的 arena 的地址進行屏蔽處理，計算超過的量（excess）。
如果超過的量（excess）為 0，因為 arena 的地址剛好是 4K 字節(jié)（2 的 12 次方）的倍數(shù)，所以程序會原樣返回分配的 arena_object。這時候因為 arena 內(nèi)已經(jīng)被 pool 填滿了，所以可以通過計算 arena 的大小或 pool 的大小來求出 arena 內(nèi) pool 的數(shù)量。
如果超過的量不為 0，程序就會計算“arena 的地址 ＋ 超過的量”，將其設(shè)置為成員pool_address。此時 arena 內(nèi)前后加起來會產(chǎn)生一個 pool 的空白，nfreepools--。
arena的2個狀態(tài)
“arena_object是否與pool建立聯(lián)系導(dǎo)致狀態(tài)不同
unused_arena_object（未使用狀態(tài)）
只有當結(jié)構(gòu)體arena_object的成員address為0時，才將其存入這個列表
剛剛new_arena()產(chǎn)生的arena_object，還沒和pool建立連接
在PyObject_Free()時arena為空的情況下，arena_object會頭插于此鏈表
單向鏈表維護
usable_arenas（可用狀態(tài)）
有已經(jīng)使用過的pool和還未被使用的都是empty狀態(tài)，也就是nfreepool>0
used狀態(tài)都是被usedpools管轄起來了，當全是used狀態(tài)的arena哪怕pool還有可能用的塊，也是要從此雙鏈表中刪除。因為申請內(nèi)存的時候會去usedpool找的。所以只需要判斷usable_arenas->nfreepools == 0，從雙鏈表中刪除 雙向鏈表維護
鏈表按照block數(shù)量最多的arena的順序排列。（基于成員nfreepools升序排列，意思就是先盡量用完整個arena）
Python對象分配器（2層）
“第 2 層的分配器負責管理 pool 內(nèi)的 block。這一層實際上是將 block 的開頭地址返回給申請者，并釋放 block 等。
block
一個pool被分割成一個個的block。Python中生成對象時，最終都會被分一個或幾個block上。block是Python內(nèi)存分配的最小單元
內(nèi)存對齊
大小以8個字節(jié)為梯度的內(nèi)存塊，就是類保證內(nèi)存對齊（字對齊）
1、提高了CPU的讀寫速度
2、減少了碎片大?。ū夭豢缮俚睦速M）
// 以下的宏
// 索引為0的話, 就是1 << 3, 顯然結(jié)果為8
// 索引為1的話, 就是2 << 3, 顯然結(jié)果為16
#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)
* Request in bytes Size of allocated block Size class idx
* ----------------------------------------------------------------
* 1-8 8 0
* 9-16 16 1
* 17-24 24 2
* 25-32 32 3
* 33-40 40 4
* 41-48 48 5
* 49-56 56 6
* 57-64 64 7
* 65-72 72 8
* ... ... ...
* 497-504 504 62
* 505-512 512 63
所以當我們需要申請44個字節(jié)的內(nèi)存空間的時候，PyObject_Malloc會從內(nèi)存池中劃分一個 48 字節(jié)的block使用
//Objects/obmalloc.c
#define ALIGNMENT 8 /* must be 2^N */
#define ALIGNMENT_SHIFT 3
“我們可以從圖8里看到excess是為了在arena中pool4K大小的對齊，所以block以8字節(jié)的倍數(shù)自然都是對齊的
由于pool_header中szidx確定
利用內(nèi)存對齊的hack
CPU 原則上能從對齊的地址取出數(shù)據(jù)。相應(yīng)地，malloc() 分配的地址也應(yīng)配合 CPU 對齊來返回數(shù)據(jù)。
利用這一點的著名 hack 就是將地址的低 3 位用作標志。
假設(shè)在結(jié)構(gòu)體內(nèi)存入某個指針。如果從 malloc() 返回的地址是按 8 字節(jié)對齊的，那么其指針的低 3 位肯定為“0”。于是我們想到了在這里設(shè)置位，將其作為標志來使用。當我們真的要訪問這個指針時，就將低 3 位設(shè)為 0，無視標志。
這是一個非常大膽的 hack，但事實上 glibc malloc 卻實現(xiàn)了這個 hack。
block的狀態(tài)
block 有3種狀態(tài)管理
已經(jīng)分配
使用完畢：就是已經(jīng)被使用過，再次釋放的block
freeblock單向鏈表維護使用完畢的塊，block是在發(fā)生釋放的時候連接到鏈表上的
freeblock是指向第一塊空閑可以使用的塊，當還沒有產(chǎn)生使用完畢的塊時候，他是NULL。那么一直是通過nextoffset來使用未使用的塊，當有回收的塊那么freeblock就指向第一個空閑的塊，并優(yōu)先與偏移量nextoffset使用。
未使用:未使用自然沒有鏈表的指向了，那么我們只能在pool_head上設(shè)置第一個可以使用塊的偏移量
nextoffset
pool
pool的大小
pool是與系統(tǒng)頁一樣的4KB的大小，其中一個pool只能管理一個種規(guī)格的block，由szidx字段來標識。所以pool是具有size概念的block集合
//Objects/obmalloc.c
#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的內(nèi)存對齊
在講解arena初始化的時候第4部分講到了excess就是為了做pool的內(nèi)存對齊，可見圖8。這里就不在贅述
pool的頭結(jié)構(gòu)
一個pool的頭由48個字節(jié)組成，所有的pool以雙向鏈表的形式連接
//Objects/obmalloc.c
/* 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; /* 當前pool里面已分配出去的block數(shù)量 */
block *freeblock; /* 指向空閑block鏈表的第一塊 */
struct pool_header *nextpool; /* next和prev提供usedpool使用，減少緩存表的空間 */
struct pool_header *prevpool;
uint arenaindex; /* 自己所屬的arena的索引（對于arenas而言） */
uint szidx; /* 分配的block的大小，所以pool中的所有塊大小一致 */
uint nextoffset; /* 下一個可用block的內(nèi)存偏移量 */
uint maxnextoffset; /* 最后一個block距離開始位置的偏移量 */
};
typedef struct pool_header *poolp;
pool的狀態(tài)
empty狀態(tài)：pool中所有的block都未被使用已經(jīng)使用完的，pool已經(jīng)有pool_size，意味著大小已經(jīng)確定的pool
used狀態(tài)：pool中至少有一個block已經(jīng)被使用，并且至少有一個block未被使用。由usedpools數(shù)組維護full狀態(tài)：pool中所有的block都已經(jīng)被使用，并從usedpools鏈表上刪除。
usedpools
“作用就是管理所有used狀態(tài)的pool
// poolp大概是pool_header的指針型的別名。也就是說，usedpools 是 pool_header 的指針型的數(shù)組。
typedef struct pool_header *poolp;
宏 NB_SMALL_SIZE_CLASSES
#define ALIGNMENT 8 /* 有必要為2的N次方 */
#define SMALL_REQUEST_THRESHOLD 512
// 指明了在當前的配置之下，一共有多少個size class。
#define NB_SMALL_SIZE_CLASSES (SMALL_REQUEST_THRESHOLD / ALIGNMENT)
usedpools的初始化大小
// 這個宏定義了一個指針，這個指針指向的位置是從一組的開頭再往前“兩個 block 指針型的大小”。
#define PTA(x) ((poolp )((uint8_t *)&(usedpools[2*(x)]) - 2*sizeof(block *)))
// 宏 PT() 以兩個一組的形式調(diào)用宏 PTA()。
#define PT(x) PTA(x), PTA(x)
// usedpools數(shù)組有128個
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_CLASSES > 8 */
};
現(xiàn)在以為usedpool的角度出發(fā)來看
usedpools如何做的快-像hash一樣處理
used就是把使用了至少一個塊，但是還沒有全部使用完的pool整合到一個usedpool中，那么這一個做法類似以hash表的鏈地址法，通過下標可以O(shè)（1）到達同一size的usedpool[下標]的位置，然后使用鏈表，因為empty->used和used->full，方便插入和刪除pool
一個例子
1、當申請20個字節(jié)內(nèi)存的時候，Python會首先獲得size class index，通過size = (uint )(nbytes \- 1) >> ALIGNMENT_SHIFT,其中ALIGNMENT_SHIFT是內(nèi)存對齊的需要右移3位（即8字節(jié)對齊），得到（20-1）>>3=2
2、通過usedpools[i+i]->nextpool可以快速找到一個最合適當前內(nèi)存需求的pool
byte = 20 /* 申請的字節(jié)數(shù)*/
byte = (20 - 1) >> 3 /* 對齊：結(jié)果 2 */
pool = usedpools[byte+byte] /* 因為是兩兩一組，所以索引加倍: index 4 */ // O（1）
// 這時，取出的 pool 存在如下關(guān)系。
pool; == pool->nextpool
pool; == pool->prevpool
pool->nextpool == pool->prevpool // O（1）
usedpool也需要盡可能節(jié)省空間
在需要緩存的時候，能夠盡可能地讓緩存少承載一些引用表。（只需要pool_header中兩個內(nèi)部的指針成員，next和prev）
如果直接保留 pool_header 的話，往往就會出現(xiàn) usedpools 變得太大，緩存承載不下的狀況。因為我們要頻繁引用數(shù)組 usedpools，所以讓它小一些才會減輕緩存的壓力。
arena和pool的釋放策略
通過盡量不使用那些可用空間多的內(nèi)存空間，增加了使其完全變?yōu)榭盏臋C會。如果這部分內(nèi)存空間完全為空，那么就能將其釋放。
usable_arenas:是按照nfreepools升序排序的，目的是為了盡可能先使用完一個arena 當full->used狀態(tài)：都是頭插到usedpools中的，也是為了現(xiàn)使用完一個pool
為什么usedpools需要2倍的空間
在釋放的時候從pymalloc_free函數(shù)觀察來看,是頭插放在usedpool[奇數(shù)]，full狀態(tài)變?yōu)閡sed狀態(tài)
// free中的代碼，
if (UNLIKELY(lastfree == NULL)) {
uint size = pool->szidx;
poolp next = usedpools[size + size]; // 雙向鏈表的尾部
poolp prev = next->prevpool;
pool->nextpool = next;
pool->prevpool = prev;
next->prevpool = pool;
prev->nextpool = pool;
return 1;
}
而分配的時候使用是直接從usedpools[偶數(shù)]也會就是尾部開始使用的，所以也盡可能用光一個pool的
// 定位在尾部，直接使用
poolp pool = usedpools[size + size];
block *bp;
if (LIKELY(pool != pool->nextpool)) {
// block使用數(shù)量++
++pool->ref.count;
bp = pool->freeblock; // freeblock指向第一塊空閑塊，直接使用
assert(bp != NULL);
分配執(zhí)行流程
pymalloc_alloc
“當申請的內(nèi)存小于512字節(jié)就來到這個函數(shù)了，他的主要功能是分配block、分配pool、分配arena
// 下標映射到size大小
#define INDEX2SIZE(I) (((uint)(I) + 1) << ALIGNMENT_SHIFT)
// 內(nèi)存對齊的宏
#define POOL_OVERHEAD _Py_SIZE_ROUND_UP(sizeof(struct pool_header), ALIGNMENT)
#define DUMMY_SIZE_IDX 0xffff /* size class of newly cached pools */
//Objects/obmalloc.c
static void*
pymalloc_alloc(void *ctx, size_t nbytes)
{
// 1、如果申請的內(nèi)存>512和==0的情況走朋友python0層，交給C處理
// 如下是Python來接管這個raw memory，當然raw memory也是由C創(chuàng)建的
if (UNLIKELY(nbytes == 0)) {
return NULL;
}
if (UNLIKELY(nbytes > SMALL_REQUEST_THRESHOLD)) {
return NULL;
}
// 2、用size去計算usedpools數(shù)組中的位置，
uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
poolp pool = usedpools[size + size];
block *bp;
// 如果usedpools中的雙向鏈表有pool那么就分配
if (LIKELY(pool != pool->nextpool)) {
// block使用數(shù)量++
++pool->ref.count;
bp = pool->freeblock; // freeblock指向第一塊空閑塊，直接使用
assert(bp != NULL);
if (UNLIKELY((pool->freeblock = *(block **)bp) == NULL)) {
// 如果freeblock是NULL，通過偏移量取未使用的block
if (UNLIKELY(pool->nextoffset <= pool->maxnextoffset)) {
pool->freeblock = (block*)pool + pool->nextoffset;
// 用小標去還原size
pool->nextoffset += INDEX2SIZE(size);
*(block **)(pool->freeblock) = NULL;
return;
}
/* 沒有可分配的block了，那么從usedpools中刪除*/
poolp next;
next = pool->nextpool;
pool = pool->prevpool;
next->prevpool = pool;
pool->nextpool = next;
}
// usedpools沒有可用的pool，需要去申請
else {
bp = allocate_from_new_pool(size);
}
// 返回pool內(nèi)的塊
return (void *)bp;
}
allocate_from_new_pool
#define ROUNDUP(x) (((x) + ALIGNMENT_MASK) & ~ALIGNMENT_MASK)
#define POOL_OVERHEAD ROUNDUP(sizeof(struct pool_header))
// 虛擬大值，是為了防止與freepool中的block匹配上，這個虛擬值是標記用來初始化空pool的
#define DUMMY_SIZE_IDX 0xffff
static void*
allocate_from_new_pool(uint size)
// 0、首先會嘗試去usable_arenas雙向鏈表中拿，沒有可用的arena時，就調(diào)用new_arena（）
// new_arena將arena_object設(shè)置到usable_arenas中，因為是第一個所以雙向鏈表指針都置空
if (usable_arenas == NULL) {
usable_arenas = new_arena();
usable_arenas->nextarena = usable_arenas->prevarena = NULL;
}
poolp pool = usable_arenas->freepools;
// 1、freepools鏈表存在，使用已經(jīng)使用完畢的pool（szidx已經(jīng)確定需要匹配）
// 那么要從freepools中取出，放到usedpools中
if (pool != NULL) {
usable_arenas->freepools = pool->nextpool;
--usable_arenas->nfreepools;
// freepools用完了，那么使用下個usable_arenas，歸還arena_object頭
if (UNLIKELY(usable_arenas->nfreepools == 0)) {
usable_arenas = usable_arenas->nextarena;
if (usable_arenas != NULL) {
usable_arenas->prevarena = NULL;
}
}
}
// 2、freepools鏈表不存在，使用未使用的pool，那么需要初始化空白pool
else {
pool = (poolp)usable_arenas->pool_address;
pool->arenaindex = (uint)(usable_arenas - arenas);
// 設(shè)置虛擬值是為了防止與freepool中的block匹配上，這個虛擬值是標記用來初始化空pool的
pool->szidx = DUMMY_SIZE_IDX;
usable_arenas->pool_address += POOL_SIZE;
--usable_arenas->nfreepools;
// 如果沒有可用的pool了把arena_object頭歸還
if (usable_arenas->nfreepools == 0) {
usable_arenas = usable_arenas->nextarena;
}
}
// 無論是情況1還是2都是要返回一塊block后，此pool插入usedpools[下標]的雙向鏈表中，并作為第一個pool
block *bp;
poolp next = usedpools[size + size]; /* == prev */
pool->nextpool = next;
pool->prevpool = next;
next->nextpool = pool;
next->prevpool = pool;
pool->ref.count = 1;
// 使用的是情況1，直接使用freepools（指向第一個已經(jīng)使用完的pool）鏈表上的塊
if (pool->szidx == size) {
bp = pool->freeblock;
assert(bp != NULL);
pool->freeblock = *(block **)bp;
return bp;
}
// 使用的情況2，需要初始化pool header的空白pool
pool->szidx = size;
// 一個宏, 將szidx轉(zhuǎn)成內(nèi)存塊的大小, 比如: 0->8， 1->16， 63->512
size = INDEX2SIZE(size);
// 跳過用于pool_header的內(nèi)存，并進行對齊
bp = (block *)pool + POOL_OVERHEAD;
pool->nextoffset = POOL_OVERHEAD + (size << 1);
pool->maxnextoffset = POOL_SIZE - size;
pool->freeblock = bp + size;
*(block **)(pool->freeblock) = NULL; // 有空閑鏈表頭指向空
return bp;
}
釋放執(zhí)行流程
這個函數(shù)有三個作用，分別是“釋放 block”“釋放 pool”以及“釋放 arena”。
pymalloc_free
從block搜索pool的技巧
#define SYSTEM_PAGE_SIZE (4 * 1024)
#define SYSTEM_PAGE_SIZE_MASK (SYSTEM_PAGE_SIZE - 1)
#define POOL_SIZE_MASK SYSTEM_PAGE_SIZE_MASK
// 基于地址P獲得離P最近的pool的邊界地址
#define POOL_ADDR(P) ((poolp)_Py_ALIGN_DOWN((P), POOL_SIZE)) //等價如下
#define POOL_ADDR(P) (P & 0xfffff000)
pool 地址對齊是按 4K 字節(jié)對齊的。也就是說，只要從pool 內(nèi)部某處 block 的地址開始用 0xfffff000 標記，肯定能取到 pool 的開頭。
末尾3個0是16^3=4096，取前面幾位就一定是4K的倍數(shù)
//Objects/obmalloc.c
static inline int
pymalloc_free(void *ctx, void *p)
{
poolp pool = POOL_ADDR(p);
// 負責檢查用宏 POOL_ADDR() 獲得的 pool 是否正確
if (UNLIKELY(!address_in_range(p, pool))) {
return 0;
}
// 把需要釋放的p，頭插到freeblock中
block *lastfree = pool->freeblock;
*(block **)p = lastfree;
pool->freeblock = (block *)p;
pool->ref.count--;
// full狀態(tài)變?yōu)閡sed狀態(tài)，是頭插到usedpools中
if (UNLIKELY(lastfree == NULL)) {
uint size = pool->szidx;
poolp next = usedpools[size + size];
poolp prev = next->prevpool;
pool->nextpool = next;
pool->prevpool = prev;
next->prevpool = pool;
prev->nextpool = pool;
return 1;
}
// 還有可分配的block
if (LIKELY(pool->ref.count != 0)) {
/* pool isn't empty: leave it in usedpools */
return 1;
}
// 如果釋放是最后一塊，從used狀態(tài)變?yōu)閑mpty，要加入freepool鏈表（這是最復(fù)雜的情況，走insert_to_freepool函數(shù)）
insert_to_freepool(pool);
return 1;
}
insert_to_freepool
在Python2.4之前一直存在內(nèi)存泄漏的問題，因為python2.4對arena是沒有區(qū)分"未使用"和可用的2種狀態(tài)，所以當pool都釋放了內(nèi)存，arena始終不會釋放它維護的pool集合。
2.5之后對arena的處理實際上分為了4種情況
如果arena中所有的pool都是empty的，釋放pool集合占用的內(nèi)存
將arena維護的pools的內(nèi)存歸還給系統(tǒng)之外，Python還調(diào)整了usable_arenas和unused_arena_object鏈表，將arena的狀態(tài)轉(zhuǎn)到了“未使用”狀態(tài)，以及一些其他的維護工作。
如果之前arena中沒有了empty的pool，那么在usable_arenas鏈表中就找不到該arena，由于現(xiàn)在arena中有了一個pool，所以需要將這個arena鏈入到usable_arenas鏈表的表頭。
若arena中的empty的pool個數(shù)為n，則從usable_arenas開始尋找arena可以插入的位置，將arena插入到usable_arenas。這個操作的原因是由于usable_arenas實際上是一個有序的鏈表，從表頭開始往后，每一個arena中的empty的pool的個數(shù)，即nfreepools，都不能大于前面的arena，也不能小于前面的arena。保持這種有序性的原因是分配block時，是從usable_arenas的表頭開始尋找可用的arena的，這樣，就能保證如果一個arena的empty pool數(shù)量越多，它被使用的機會就越少。因此，它最終釋放其維護的pool集合的內(nèi)存的機會就越大，這樣就能保證多余的內(nèi)存會被歸還給系統(tǒng)。
其他情況，不進行任何對arena的處理。
static void
insert_to_freepool(poolp pool)
{
// 從usedpools中取出pool
poolp next = pool->nextpool;
poolp 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;
struct arena_object* lastnf = nfp2lasta[nf];
if (lastnf == ao) { /* it is the rightmost */
struct arena_object* p = ao->prevarena;
nfp2lasta[nf] = (p != NULL && p->nfreepools == nf) ? p : NULL;
}
ao->nfreepools = ++nf;
if (nf == ao->ntotalpools && ao->nextarena != NULL) {
/* 情況1、最后一個block、最后一個pool，最終歸還arena_object*/
// 從usable_arenas取出arena_object
if (ao->prevarena == NULL) {
usable_arenas = ao->nextarena;
}
else {
ao->prevarena->nextarena =
ao->nextarena;
}
if (ao->nextarena != NULL) {
assert(ao->nextarena->prevarena == ao);
ao->nextarena->prevarena =
ao->prevarena;
}
// 頭插到unused_arena_objects鏈表中
ao->nextarena = unused_arena_objects;
unused_arena_objects = ao;
// 釋放內(nèi)存
_PyObject_Arena.free(_PyObject_Arena.ctx,
(void *)ao->address, ARENA_SIZE);
// “arena尚未被分配”的標記
ao->address = 0;
--narenas_currently_allocated;
return;
}
// 情況2、所以有pool是full/used狀態(tài)，釋放一個block使得used-empty狀態(tài)，就此有唯一的empty狀態(tài)的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);
if (nfp2lasta[1] == NULL) {
nfp2lasta[1] = ao;
}
return;
}
/* If this arena is now out of order, we need to keep
* the list sorted. The list is kept sorted so that
* the "most full" arenas are used first, which allows
* the nearly empty arenas to be completely freed. In
* a few un-scientific tests, it seems like this
* approach allowed a lot more memory to be freed.
*/
/* If this is the only arena with nf, record that. */
if (nfp2lasta[nf] == NULL) {
nfp2lasta[nf] = ao;
/* 情況4、 Nothing to do. */
if (ao == lastnf) {
return;
}
// 情況3、因為usable_arenas維護的是有序表，插入響應(yīng)的位置
if (ao->prevarena != NULL) {
/* ao isn't at the head of the list */
ao->prevarena->nextarena = ao->nextarena;
}
else {
/* ao is at the head of the list */
usable_arenas = ao->nextarena;
}
ao->nextarena->prevarena = ao->prevarena;
/* And insert after lastnf. */
ao->prevarena = lastnf;
ao->nextarena = lastnf->nextarena;
if (ao->nextarena != NULL) {
ao->nextarena->prevarena = ao;
}
lastnf->nextarena = ao;
/* Verify that the swaps worked. */
assert(ao->nextarena == NULL || nf <= ao->nextarena->nfreepools);
assert(ao->prevarena == NULL || nf > ao->prevarena->nfreepools);
assert(ao->nextarena == NULL || ao->nextarena->prevarena == ao);
assert((usable_arenas == ao && ao->prevarena == NULL)
|| ao->prevarena->nextarena == ao);
}
情況3
Python1、2層內(nèi)存內(nèi)存管理匯總
對象特有的分配器（第3層）
對象有列表和元組等多種多樣的型，在生成它們的時候要使用各自特有的分配器。見我的其他Python底層數(shù)據(jù)結(jié)構(gòu)的分析。
參考引用
垃圾回收的算法與實現(xiàn)
Python源碼剖析
memory management in python
文章授權(quán)轉(zhuǎn)載：一直飛的無腳鳥
（版權(quán)歸原作者所有，侵刪）
點擊下方“閱讀原文”查看更多