前言

Python 中一切皆對(duì)象，這些對(duì)象的內(nèi)存都是在運(yùn)行時(shí)動(dòng)態(tài)地在堆中進(jìn)行分配的，就連 Python 虛擬機(jī)使用的棧也是在堆上模擬的。既然一切皆對(duì)象，那么在 Python 程序運(yùn)行過(guò)程中對(duì)象的創(chuàng)建和釋放就很頻繁了，而每次都用 malloc() 和 free() 去向操作系統(tǒng)申請(qǐng)內(nèi)存或釋放內(nèi)存就會(huì)對(duì)性能造成影響，畢竟這些函數(shù)最終都要發(fā)生系統(tǒng)調(diào)用引起上下文的切換。下面我們就來(lái)看看 Python 中的內(nèi)存管理器是如何高效管理內(nèi)存的。

其實(shí)核心就是池化技術(shù)，一次性向操作系統(tǒng)申請(qǐng)一批連續(xù)的內(nèi)存空間，每次需要?jiǎng)?chuàng)建對(duì)象的時(shí)候就在這批空間內(nèi)找到空閑的內(nèi)存塊進(jìn)行分配，對(duì)象釋放的時(shí)候就將對(duì)應(yīng)的內(nèi)存塊標(biāo)記為空閑，這樣就避免了每次都向操作系統(tǒng)申請(qǐng)和釋放內(nèi)存，只要程序中總的對(duì)象內(nèi)存空間穩(wěn)定，Python 向操作系統(tǒng)申請(qǐng)和釋放內(nèi)存的頻率就會(huì)很低。這種方案是不是很熟悉，數(shù)據(jù)庫(kù)連接池也是類(lèi)似的思路。一般后端應(yīng)用程序也是提前跟數(shù)據(jù)庫(kù)建立多個(gè)連接，每次執(zhí)行 SQL 的時(shí)候就從中找一個(gè)可用的連接與數(shù)據(jù)庫(kù)進(jìn)行交互，SQL 完成的時(shí)候就將連接交還給連接池，如果某個(gè)連接長(zhǎng)時(shí)間未被使用，連接池就會(huì)將其釋放掉。本質(zhì)上，這些都是用空間換時(shí)間，消耗一些不算太大的內(nèi)存，降低諸如內(nèi)存申請(qǐng)和 TCP 建立連接等耗時(shí)操作的頻率，提高程序整體的運(yùn)行速度。

接下來(lái)具體看看 Python 的內(nèi)存管理器是如何實(shí)現(xiàn)池化技術(shù)的，先概要介紹內(nèi)存層次結(jié)構(gòu)及分配內(nèi)存的流程，然后結(jié)合源碼詳細(xì)展開(kāi)。

內(nèi)存層次結(jié)構(gòu)

Python 內(nèi)存管理器對(duì)內(nèi)存進(jìn)行了分層，從大到小分別為 arena、pool 和 block。arena 是內(nèi)存管理器直接調(diào)用 malloc() 或 calloc() 向操作系統(tǒng)申請(qǐng)的一大塊內(nèi)存，Python 中對(duì)象的創(chuàng)建和釋放都是在 arena 中進(jìn)行分配和回收。在 arena 內(nèi)部又分成了多個(gè) pool，每個(gè) pool 內(nèi)又分成了多個(gè)大小相等的 block，每次分配內(nèi)存的時(shí)候都是從某個(gè) pool 中選擇一塊可用的 block 返回。每個(gè) pool 內(nèi)的 block 的大小是相等的，不同 pool 的 block 大小可以不等。

arena、pool 和 block 的大小在 32 位機(jī)器和 64 位機(jī)器上有所不同，block 的大小必須是 ALIGNMENT 的倍數(shù)，并且最大為 512 字節(jié)，下表列出了不同機(jī)器上各種內(nèi)存的大小。

以 64 位機(jī)器為例，所有可能的 block 的大小為 16、32、48 … 496、512，每個(gè)大小都對(duì)應(yīng)一個(gè)分級(jí)(size class)，從小到大依次為0、1、2 … 30、31。每次分配內(nèi)存的時(shí)候就是找到一個(gè)不小于請(qǐng)求大小的最小的空閑 block。對(duì) block 的大小進(jìn)行分級(jí)是為了適應(yīng)不同大小的內(nèi)存請(qǐng)求，減少內(nèi)存碎片的產(chǎn)生，提高 arena 的利用率。

內(nèi)存管理邏輯

了解了 arena、pool 和 block 的概念后就可以描述內(nèi)存分配的邏輯了，假如需要的內(nèi)存大小為 n 字節(jié)

• 如果 n > 512，回退為 malloc()，因?yàn)?block 最大為 512 字節(jié)
• 否則計(jì)算出不小于 n 的最小的 block size，比如 n=105，在 64 位機(jī)器上最小的 block size 為 112
• 找到對(duì)應(yīng) 2 中 block size 的 pool，從中分配一個(gè) block。如果沒(méi)有可用的 pool 就從可用的 arena 中分配一個(gè) pool，如果沒(méi)有可用的 arena 就用 malloc() 向操作系統(tǒng)申請(qǐng)一塊新的 arena

釋放內(nèi)存的邏輯如下

• 先判斷要釋放的內(nèi)存是不是由 Python 內(nèi)存管理器分配的，如果不是直接返回
• 找到要釋放的內(nèi)存對(duì)應(yīng)的 block 和 pool，并將 block 歸還給 pool，留給下次分配使用
• 如果釋放的 block 所在的 arena 中除了自己之外其他的都是空閑的，那么在 block 歸還之后整個(gè) arena 都是空閑的，就可以將 arena 用 free() 釋放掉還給操作系統(tǒng)

Python 中的對(duì)象一般都不大，并且生命周期很短，所以 arena 一旦申請(qǐng)之后，對(duì)象的分配和釋放大部分情況下都是在 arena 中進(jìn)行的，提高了效率。
上文已經(jīng)將 Python 內(nèi)存管理器的核心邏輯描述清楚了，只不過(guò)有一些細(xì)節(jié)的問(wèn)題還沒(méi)解決，比如內(nèi)存分配的時(shí)候怎么根據(jù) block size 找到對(duì)應(yīng)的 pool，這些 pool 之間怎么關(guān)聯(lián)起來(lái)的，內(nèi)存釋放的時(shí)候又是怎么判斷要釋放的內(nèi)存是不是 Python 內(nèi)存管理器分配的，等等。下面結(jié)合源碼將內(nèi)存分配和釋放的邏輯詳細(xì)展開(kāi)。

先介紹 arena 和 pool 的內(nèi)存布局和對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)，然后再具體分析 pymalloc_alloc() 和 pymalloc_free() 的邏輯，以 64 位機(jī)器為例介紹。

內(nèi)存布局及對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)

Arena

arena 為 1 MB，pool 為 16 KB，pool 在 arena 中是相鄰的，一個(gè) arena 中最多有 1 MB / 16 KB = 64 個(gè) pool。Python 內(nèi)存管理器會(huì)將 arena 中第一個(gè) pool 的首地址跟 POOL_SIZE 對(duì)齊，這樣每個(gè) pool 的首地址都是 POOL_SIZE 的整數(shù)倍，給定任意內(nèi)存地址都可以很方便的計(jì)算出其所在 pool 的首地址，這個(gè)特性在內(nèi)存釋放的時(shí)候會(huì)用到。POOL_SIZE 在 32 位機(jī)器上是 4 KB，在 64 位機(jī)器上是 16 KB，這樣做還有另外一個(gè)好處就是讓每個(gè) pool 正好落在一個(gè)或多個(gè)物理頁(yè)中，提高了訪存效率。上圖中的灰色內(nèi)存塊就是為了對(duì)齊而丟棄掉的，如果 malloc() 分配的內(nèi)存首地址恰好對(duì)齊了，那么 pool 的數(shù)量就是 64，否則就是 63。當(dāng)然 arena 不是一開(kāi)始就將全部的 pool 都劃分出來(lái)，而是在沒(méi)有可用的 pool 的時(shí)候才會(huì)去新劃分一個(gè)，當(dāng)所有的 pool 全部劃分之后布局如上圖所示。

每個(gè) arena 都由結(jié)構(gòu)體 struct arena_object 來(lái)表示，但不是所有 struct arena_object 都有對(duì)應(yīng)的 arena，因?yàn)?arena 釋放之后對(duì)應(yīng)的 struct arena_object 還保留著，這些沒(méi)有對(duì)應(yīng) arena 的 struct arena_object 存放在單鏈表 unused_arena_objects 中，在下次分配 arena 時(shí)可以拿來(lái)使用。如果 struct arena_object 有對(duì)應(yīng)的 arena，并且 arena 中有可以分配的 pool，那么 struct arena_object 會(huì)存放在 usable_arenas 這個(gè)雙向鏈表中，同時(shí)，所有的 struct arena_object 無(wú)論有沒(méi)有對(duì)應(yīng)的 arena 都存在數(shù)組 arenas 中。usable_arenas 中 arena 是按照其包含的空閑 pool 的數(shù)量從小到大排序的，這么排序是為了讓已經(jīng)使用了更多內(nèi)存的 arena 在下次分配 pool 的時(shí)候優(yōu)先被使用，那么在釋放內(nèi)存的時(shí)候排在后面的那些擁有更多空閑內(nèi)存的 arena 就有更大可能變成完全空閑狀態(tài)，從而被釋放掉將其內(nèi)存空間歸還給操作系統(tǒng)，降低整體的內(nèi)存消耗。

struct arena_object 的結(jié)構(gòu)及各字段含義如下

struct arena_object {
    uintptr_t address; // 指向 arena 的起始地址，如果當(dāng)前 arena_object 沒(méi)有對(duì)應(yīng)的 arena 內(nèi)存則 address = 0
    block* pool_address; // pool 需要初始化之后才能使用，pool_address 指向的地址可以用來(lái)初始化一個(gè) pool 用于分配
    int nfreepools; // arena 中目前可以用來(lái)分配的 pool 的數(shù)量
    uint ntotalpools; // arena 中 pool 的總數(shù)量，64 或 63
    struct pool_header* freepools; // arena 中可以分配的 pool 構(gòu)成一個(gè)單鏈表，freepools 指針是單鏈表的第一個(gè)節(jié)點(diǎn)
    struct arena_object* nextarena; // 在 usable_arenas 或 unused_arena_objects 指向下一個(gè)節(jié)點(diǎn)
    struct arena_object* prevarena; // 在 usable_arenas 中指向上一個(gè)節(jié)點(diǎn)
}

Pool

pool 的內(nèi)部等分成多個(gè)大小相等的 block，與 arena 一樣，也有一個(gè)數(shù)據(jù)結(jié)構(gòu) struct pool_header 用來(lái)表示 pool。與 arena 不同的是，struct pool_header 位于 pool 的內(nèi)部，在最開(kāi)始的一段內(nèi)存中，緊接之后的是第一個(gè) block，為了讓每個(gè) block 的地址都能對(duì)齊機(jī)器訪問(wèn)內(nèi)存的步長(zhǎng)，可能需要在 struct pool_header 和第一個(gè) block 之間做一些 padding，圖中灰色部分所示。這部分 padding 不一定存在，在 64 位機(jī)器上 sizeof(struct pool_header) 為 48 字節(jié)，本來(lái)就已經(jīng)對(duì)齊了，后面就直接跟第一個(gè) block，中間沒(méi)有 padding。即使如此，pool 最后的一小塊內(nèi)存也可能用不上，上圖中下面的灰色部分所示，因?yàn)槊總€(gè) pool 中 block 大小是相等的，假設(shè) block 為 64 字節(jié)，一個(gè) pool 中可以分出 255 個(gè) block，前面 48 字節(jié)存儲(chǔ) struct pool_header，后面 16 字節(jié)用不上，當(dāng)然如果 block 大小為 48 字節(jié)或 16 字節(jié)那么整個(gè) pool 就會(huì)被完全利用上。同 arena 一樣，pool 一開(kāi)始不是把所有的 block 全部劃分出來(lái)，而是在沒(méi)有可用 block 的時(shí)候才回去新劃分一個(gè)，在所有的 block 全部劃分之后 pool 的布局如上圖所示。

接下來(lái)看看 struct pool_header 的結(jié)構(gòu)

struct pool_header {
    union { block *_padding;
            uint count; } ref; // 當(dāng)前 pool 中已經(jīng)使用的 block 數(shù)量，共用體中只有 count 字段有意義，_padding 是為了讓 ref 字段占 8 個(gè)字節(jié)，這個(gè)特性在 usedpools 初始化的時(shí)候有用
    block *freeblock; // pool 中可用來(lái)進(jìn)行分配的 block 單鏈表的頭指針
    struct pool_header *nextpool; // 在 arena_object.freepools 或 usedpools 中指向下一個(gè) pool
    struct pool_header *prevpool; // 在 usedpools 中指向上一個(gè) pool
    uint arenaindex; // pool 所在 arena 在 arenas 數(shù)組中的索引
    uint szidx; // pool 中 block 大小的分級(jí)
    uint nextoffset; // 需要新的 block 可以從 nextoffset 處分配
    uint maxnextoffset; // nextoffset 最大有效值
};

typedef struct pool_header *poolp;

每個(gè) pool 一旦被分配之后一定會(huì)處于 full、empty 和 used 這 3 種狀態(tài)中的一種。

• full 所有的 block 都分配了
• empty 所有的 block 都是空閑的，都可用于分配，所有處于 empty 狀態(tài)的 pool 都在其所在 arena_object 的 freepools 字段表示的單鏈表中
• used 有已分配的 block，也有空閑的 block，所有處于 used 狀態(tài)的 pool 都在全局?jǐn)?shù)組 usedpools 中某個(gè)元素指向的雙向循環(huán)鏈表中

usedpools 是內(nèi)存分配最常訪問(wèn)的數(shù)據(jù)結(jié)構(gòu)，分配內(nèi)存時(shí)先計(jì)算申請(qǐng)的內(nèi)存大小對(duì)應(yīng)的 block 分級(jí) i，usedpools[i+i] 指向的就是屬于分級(jí) i 的所有處于 used 狀態(tài)的 pool 構(gòu)成的雙向循環(huán)鏈表的頭結(jié)點(diǎn)，如果鏈表不空就從頭結(jié)點(diǎn)中選擇一個(gè)空閑 block 分配。接下來(lái)分析一下為什么 usedpools[i+i] 指向的就是屬于分級(jí) i 的 pool 所在的鏈表。

usedpools 的原始定義如下

#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),
    …
}

將宏定義稍微展開(kāi)一下

static poolp usedpools[64] = { 
    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(6), PTA(6), PTA(7), PTA(7),
    …
}

PTA(x) 表示數(shù)組 usedpools 中第 2*x 個(gè)元素的地址減去兩個(gè)指針的大小也就是 16 字節(jié)（64 位機(jī)器），假設(shè)數(shù)組 usedpools 首地址為 1000，則數(shù)組初始化的值如下圖所示

假設(shè) i = 2，則 usedpools[i+i] = usedpools[4] = 1016，數(shù)組元素的類(lèi)型為 poolp 也就是 struct pool_header *，如果認(rèn)為 1016 存儲(chǔ)的是 struct pool_header，那么 usedpools[4] 和 usedpools[5] 的值也就是地址 1032 和 1040 存儲(chǔ)的值，分別是字段 nextpool 和 prevpool 的值，可以得到

usedpools[4]->prevpool = usedpools[4]->nextpool = usedpools[4] = 1016

將 usedpools[4] 用指針 p 表示就有 p->prevpool = p->nextpool = p，那么 p 就是雙向循環(huán)鏈表的哨兵節(jié)點(diǎn)，初始化的時(shí)候哨兵節(jié)點(diǎn)的前后指針都指向自己，表示當(dāng)前鏈表為空。

雖然 usedpools 的定義非常繞，但是這樣定義有個(gè)好處就是省去了哨兵節(jié)點(diǎn)的數(shù)據(jù)域，只保留前后指針，可以說(shuō)是將節(jié)省內(nèi)存做到了極致。

下面分別看看源碼是怎么實(shí)現(xiàn)內(nèi)存分配和釋放的邏輯的，下文中的源碼基于 Python 3.10.4。另外說(shuō)明一下，源碼中有比本文詳細(xì)的多注釋說(shuō)明，有興趣的讀者可以直接看源碼，本文為了代碼不至于過(guò)長(zhǎng)會(huì)對(duì)代碼做簡(jiǎn)化處理并且省略掉了大部分注釋。

內(nèi)存分配

內(nèi)存分配的主邏輯在函數(shù) pymalloc_alloc 中，簡(jiǎn)化后代碼如下

static inline void*
pymalloc_alloc(void *ctx, size_t nbytes)
{  
    // 計(jì)算請(qǐng)求的內(nèi)存大小 ntybes 所對(duì)應(yīng)的內(nèi)存分級(jí) size
    uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
    // 找到屬于內(nèi)存分級(jí) size 的 pool 所在的雙向循環(huán)鏈表的頭指針 pool
    poolp pool = usedpools[size + size];
    block *bp;
    // pool != pool->nextpool，說(shuō)明 pool 不是哨兵節(jié)點(diǎn)，是真正的 pool
    if (LIKELY(pool != pool->nextpool)) {
        ++pool->ref.count;
        // 將 pool->freeblock 指向的 block 分配給 bp，因?yàn)?pool 是從 usedpools 中取的，
        // 根據(jù) usedpools 的定義，pool->freeblock 指向的一定是空閑的 block
        bp = pool->freeblock;
        // 如果將 bp 分配之后 pool->freeblock 為空，需要從 pool 中劃分一個(gè)空閑 block
        // 到 pool->freeblock 鏈表中留下次分配使用
        if (UNLIKELY((pool->freeblock = *(block **)bp) == NULL)) {
            pymalloc_pool_extend(pool, size);
        }
    }
    // 如果沒(méi)有對(duì)應(yīng)內(nèi)存分級(jí)的可用 pool，就從 arena 中分配一個(gè) pool 之后再?gòu)闹蟹峙?block
    else {
        bp = allocate_from_new_pool(size);
    }
    
    return (void *)bp;
}

主體邏輯還是比較清晰的，代碼中注釋都做了說(shuō)明，不過(guò)還是要解釋一下下面的這個(gè)判斷語(yǔ)句。

if (UNLIKELY((pool->freeblock = *(block **)bp) == NULL))

前文已經(jīng)介紹過(guò) pool->freeblock 表示 pool 中可用來(lái)進(jìn)行分配的 block 所在單鏈表的頭指針，類(lèi)型為 block*，但是 block 的定義為 typedef uint8_t block;，并不是一個(gè)結(jié)構(gòu)體，所以沒(méi)有指針域，那么是怎么實(shí)現(xiàn)單鏈表的呢?？紤]到 pool->freeblock 的實(shí)際含義，只需要把空閑 block 用單鏈表串起來(lái)就可以了，不需要數(shù)據(jù)域，Python 內(nèi)存管理器把空閑 block 內(nèi)存的起始 8 字節(jié)（64 位機(jī)器）當(dāng)做虛擬的 next 指針，指向下一個(gè)空閑 block，具體是通過(guò) *(block **)bp 實(shí)現(xiàn)的。首先用 (block **) 將 bp 轉(zhuǎn)換成 block 的二級(jí)指針，然后用 * 解引用，將 bp 指向內(nèi)存的首地址內(nèi)容轉(zhuǎn)換成 (block *) 類(lèi)型，表示下一個(gè) block 的地址，不得不說(shuō)，C 語(yǔ)言真的是可以為所欲為。再來(lái)看一下上面判斷語(yǔ)句，首先將 bp 的下一個(gè)空閑 block 地址賦值給 pool->freeblock，如果是 NULL 證明沒(méi)有更多空閑 block，需要調(diào)用 pymalloc_pool_extend 擴(kuò)充。

pymalloc_pool_extend 的源碼簡(jiǎn)化后如下

static void
pymalloc_pool_extend(poolp pool, uint size)
{
    // 如果 pool 還有更多空間，就劃分一個(gè)空閑 block 放到 pool->freeblock 中
    if (UNLIKELY(pool->nextoffset <= pool->maxnextoffset)) {
        pool->freeblock = (block*)pool + pool->nextoffset;
        pool->nextoffset += INDEX2SIZE(size);
        // pool->freeblock 只有一個(gè) block，需要將虛擬的 next 指針置為 NULL
        *(block **)(pool->freeblock) = NULL;
        return;
    }

    // 如果沒(méi)有更多空間，需要將 pool 從 usedpools[size+size] 中移除
    poolp next;
    next = pool->nextpool;
    pool = pool->prevpool;
    next->prevpool = pool;
    pool->nextpool = next;

}

過(guò)程也很清晰，如果有更多空間就劃分一個(gè) block 到 pool->freeblock，如果沒(méi)有更多空間就將 pool 從 usedpools[size+size] 中移除。pool->nextoffset 指向的是 pool 中從未被使用過(guò)內(nèi)存的地址，分配 block 時(shí)候優(yōu)先使用 pool->nextoffset 之前的空閑 block，這些空閑的 block 一般是之前分配過(guò)后來(lái)又被釋放到 pool->freeblock 中的。這種復(fù)用空閑 block 的方式讓 pool 更加經(jīng)久耐用，如果每次都從 pool->nextoffset 劃分一個(gè)新的 block，pool 很快就會(huì)被消耗完，變成 full 狀態(tài)。

在 pymalloc_alloc 中如果沒(méi)有可用 pool 就會(huì)調(diào)用 allocate_from_new_pool 先分配一個(gè)新的 pool，再?gòu)男碌?pool 中分配 block，其源碼簡(jiǎn)化后如下

static void*
allocate_from_new_pool(uint size)
{
    // 沒(méi)有可用的 arena 就新申請(qǐng)一個(gè)
    if (UNLIKELY(usable_arenas == NULL)) {
        usable_arenas = new_arena();
        if (usable_arenas == NULL) {
            return NULL;
        }
        // 將新的 arena 作為 usable_arenas 鏈表的頭結(jié)點(diǎn)
        usable_arenas->nextarena = usable_arenas->prevarena = NULL;
        nfp2lasta[usable_arenas->nfreepools] = usable_arenas;
    }

    // 如果有可用 arena 就從中分配一個(gè)空閑 pool，并調(diào)整當(dāng)前 arena 在 usable_arenas 中的位置，使 usable_arenas 按空閑 pool 的數(shù)量從小到大排序
    if (nfp2lasta[usable_arenas->nfreepools] == usable_arenas) {
        nfp2lasta[usable_arenas->nfreepools] = NULL;
    }
    if (usable_arenas->nfreepools > 1) {
        nfp2lasta[usable_arenas->nfreepools - 1] = usable_arenas;
    }

    // 執(zhí)行到這里，usable_arenas->freepools 就是當(dāng)前需要的可用 pool
    poolp pool = usable_arenas->freepools;
    // 更新 freepools 鏈表和 nfreepools 計(jì)數(shù)
    if (LIKELY(pool != NULL)) {
        usable_arenas->freepools = pool->nextpool;
        usable_arenas->nfreepools--;
        // 分配之后，如果 arena 中沒(méi)有空閑 pool，需要更新 usable_arenas 鏈表
        if (UNLIKELY(usable_arenas->nfreepools == 0)) {
            usable_arenas = usable_arenas->nextarena;
            if (usable_arenas != NULL) {
                usable_arenas->prevarena = NULL;
            }
        }
    }
    // 如果當(dāng)前 arena 中沒(méi)有可用 pool，就重新劃分一個(gè)
    else {
        pool = (poolp)usable_arenas->pool_address;
        pool->arenaindex = (uint)(usable_arenas - arenas);
        pool->szidx = DUMMY_SIZE_IDX;
        usable_arenas->pool_address += POOL_SIZE;
        --usable_arenas->nfreepools;
        // 劃分之后，如果 arena 中沒(méi)有空閑 pool，需要更新 usable_arenas 鏈表
        if (usable_arenas->nfreepools == 0) {
            usable_arenas = usable_arenas->nextarena;
            if (usable_arenas != NULL) {
                usable_arenas->prevarena = NULL;
            }
        }
    }

    // 執(zhí)行到這里，變量 pool 就是找到的可用 pool，將其置為鏈表 usedpools[size+size] 的頭節(jié)點(diǎn)
    block *bp;
    poolp next = usedpools[size + size];
    pool->nextpool = next;
    pool->prevpool = next;
    next->nextpool = pool;
    next->prevpool = pool;
    pool->ref.count = 1;
    // 如果 pool 的內(nèi)存分級(jí)跟請(qǐng)求的一致，直接從中分配一個(gè) block 返回
    // 證明這個(gè) pool 之前被使用之后又釋放到 freepools 中了
    // 并且當(dāng)時(shí)使用的時(shí)候內(nèi)存分級(jí)也是 size
    if (pool->szidx == size) {
        bp = pool->freeblock;
        pool->freeblock = *(block **)bp;
        return bp;
    }
    
    // 執(zhí)行到這里，說(shuō)明 pool 是 arena 新劃分的，需要對(duì)其進(jìn)行初始化
    // 然后分配 block 返回
    pool->szidx = size;
    size = INDEX2SIZE(size);
    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ǎng)，歸納一下做了下面 3 件事

• 如果沒(méi)有可用的 arena 就重新申請(qǐng)一個(gè)
• 從可用的 arena 中分配一個(gè)新的 pool
• 從分配的 pool 中分配空閑的 block

首先是 arena 的申請(qǐng)，申請(qǐng)流程在函數(shù) new_arena() 中，申請(qǐng)完之后將對(duì)應(yīng)的 arena_object 置為 雙線鏈表 usable_arenas 的頭結(jié)點(diǎn)，并且前后指針都置為 NULL，因?yàn)橹挥性跊](méi)有可用 arena 的時(shí)候才回去調(diào)用 new_arena()，所以申請(qǐng)之后系統(tǒng)里只有一個(gè)可用 arena。另外還有一個(gè)操作如下

nfp2lasta[usable_arenas->nfreepools] = usable_arenas;

nfp2lasta 是一個(gè)數(shù)組，nfp2lasta[i] 表示的是在 usable_arenas 鏈表中，空閑 pool 的數(shù)量為 i 的所有 arena 中最后一個(gè) arena。前文已經(jīng)說(shuō)明 usable_arenas 是按照 arena 中空閑 pool 的數(shù)量從小到大排序的，為了維護(hù) usable_arenas 的有序性，在插入或刪除一個(gè) arena 的時(shí)候需要找到對(duì)應(yīng)的位置，時(shí)間復(fù)雜度為 O(N)，為了避免線性搜索，Python 3.8 引入了 nfp2lasta，將時(shí)間復(fù)雜度降為常量級(jí)別。

有了可用的 arena 就可以從中分配 pool 了，分配 pool 之后 arena->nfreepools 就會(huì)減少，需要更新 nfp2lasta，由于使用的是鏈表 usable_arenas 的頭結(jié)點(diǎn)，并且是減少其空閑 pool 數(shù)量，所以整個(gè)鏈表依然有序。接下來(lái)優(yōu)先復(fù)用 arena->freepools 中空閑的 pool，如果沒(méi)有就從 arena->pool_address 指向的未使用內(nèi)存處新劃分一個(gè) pool，這點(diǎn)跟 pool 中復(fù)用空閑 block 的策略是一樣的。

分配了可用的 pool，先將其置為鏈表 usedpools[size+size] 的頭結(jié)點(diǎn)，然后從中分配 block，如果 pool 不是從新分配的 arena 獲得的，那么 pool 就是之前初始化使用之后釋放掉的，如果 pool 的分級(jí)恰好就是請(qǐng)求的內(nèi)存分級(jí)那么直接從 pool->freeblock 分配 block，否則需要將 pool 重新初始化，當(dāng)然如果 pool 來(lái)自新分配的 arena 也要進(jìn)行初始化。初始化的時(shí)候，先將第一個(gè) block 的地址進(jìn)行內(nèi)存對(duì)齊，然后將 pool->freeblock 指向第 2 個(gè) block 留下次分配使用（第 1 個(gè) block 本次要返回），將 pool->nextoffset 指向第 3 個(gè) block，在下次劃分新的 block 時(shí)使用。

內(nèi)存釋放

內(nèi)存釋放的主邏輯在 pymalloc_free 函數(shù)中，代碼簡(jiǎn)化后如下

static inline int
pymalloc_free(void *ctx, void *p)
{
    // 假設(shè) p 是 pool 分配的，計(jì)算 p 所在 pool 的首地址
    poolp pool = POOL_ADDR(p);
    // 如果 p 不是內(nèi)存管理器分配的直接返回
    if (UNLIKELY(!address_in_range(p, pool))) {
        return 0;
    }
    
    // 將 p 指向的 block 歸還給 pool，置為 pool->freeblock 的頭結(jié)點(diǎn)
    block *lastfree = pool->freeblock;
    *(block **)p = lastfree;
    pool->freeblock = (block *)p;
    pool->ref.count--;
    // 如果 pool 原來(lái)處于 full 狀態(tài)，現(xiàn)在有一個(gè)空閑的 block 就變成了 used 狀態(tài)
    // 需要將其作為頭結(jié)點(diǎn)插到 usedpools[size+size] 中
    if (UNLIKELY(lastfree == NULL)) {
        insert_to_usedpool(pool);
        return 1;
    }

    if (LIKELY(pool->ref.count != 0)) {
        return 1;
    }

    // 如果 block 釋放之后，其所在 pool 所有的 block 都是空閑狀態(tài)，
    // 將 pool 從 usedpools[size+size] 中移到 arena->freepools 
    insert_to_freepool(pool);
    return 1;
}

pymalloc_free 函數(shù)的邏輯也很清晰

• 計(jì)算地址 p 所在 pool 首地址，前文介紹過(guò)每個(gè) pool 首地址都是 POOL_SIZE 的整數(shù)倍，所以將 p 的低位置 0 就得到了 pool 的地址
• address_in_range(p, pool) 判斷 p 是否是由 pool 分配的，如果不是直接返回
• 將 p 指向的 block 釋放掉，被 pool->freeblock 回收
• 如果 pool 開(kāi)始為 full 狀態(tài)，那么回收 block 之后就是 used 狀態(tài)，調(diào)用函數(shù) insert_to_usedpool(pool) 將其置為 usedpools[size+size] 的頭結(jié)點(diǎn)。這里的策略跟 usable_arenas 一樣，優(yōu)先使用快滿的 pool，讓比較空閑的 pool 有較高的概率被釋放掉。
• 如果 pool 回收 block 之后變成 empty 狀態(tài)，需要調(diào)用 insert_to_freepool(pool) 將 pool 也釋放掉

address_in_range 函數(shù)如下

address_in_range(void *p, poolp pool)
{
    uint arenaindex = *((volatile uint *)&pool->arenaindex);
    return arenaindex < maxarenas &&
        (uintptr_t)p - arenas[arenaindex].address < ARENA_SIZE &&
        arenas[arenaindex].address != 0;
}

這段邏輯能在常量時(shí)間內(nèi)判斷出 p 是否由 pool 分配，但是存在一個(gè)可能出問(wèn)題的地方，畢竟這里的 pool 是在假設(shè) p 是由 pool 分配的前提下計(jì)算出來(lái)的，有可能 pool 指向的地址可能還沒(méi)被初始化，pool->arenaindex 操作可能會(huì)出錯(cuò)。Python 3.10 在這個(gè) commit 中利用基數(shù)樹(shù)來(lái)判斷任意一個(gè)地址 p 是不是由內(nèi)存管理器分配的，避免了可能出現(xiàn)的內(nèi)存訪問(wèn)錯(cuò)誤。

insert_to_usedpool 函數(shù)中只是簡(jiǎn)單的指針操作就不展開(kāi)了，insert_to_freepool 稍微復(fù)雜一點(diǎn)，下面再展開(kāi)一下

static void
insert_to_freepool(poolp pool)
{
    poolp next = pool->nextpool;
    poolp prev = pool->prevpool;
    next->prevpool = prev;
    prev->nextpool = next;
    // 將 pool 置為 ao->freepools 頭結(jié)點(diǎn)
    struct arena_object *ao = &arenas[pool->arenaindex];
    pool->nextpool = ao->freepools;
    ao->freepools = pool;
    uint nf = ao->nfreepools;
    struct arena_object* lastnf = nfp2lasta[nf];
    // 如果 arena 是排在最后的包含 nf 個(gè)空閑 pool 的 arena，
    // 需要將 nfp2lasta[nf] 置為 arena 的前驅(qū)結(jié)點(diǎn)或 NULL
    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;

    // 如果 pool 釋放后 arena 變成完全空閑狀態(tài)，并且系統(tǒng)中還有其他可用 arena，
    // 需要將 arena 從 usable_arenas 中移除并調(diào)用 free() 函數(shù)將其釋放歸還給操作系統(tǒng)
    if (nf == ao->ntotalpools && ao->nextarena != NULL) {
        if (ao->prevarena == NULL) {
            usable_arenas = ao->nextarena;
        }
        else {
            ao->prevarena->nextarena = ao->nextarena;
        }
        if (ao->nextarena != NULL) {
            ao->nextarena->prevarena = ao->prevarena;
        }
        ao->nextarena = unused_arena_objects;
        unused_arena_objects = ao;
        arena_map_mark_used(ao->address, 0);
        _PyObject_Arena.free(_PyObject_Arena.ctx, (void *)ao->address, ARENA_SIZE);
        ao->address = 0;          
        --narenas_currently_allocated;
        return;
    }
    // 如果 pool 釋放后 arena 從滿變成可用，需要將其置為 usable_arenas 頭結(jié)點(diǎn)，
    // 因?yàn)?arena 空閑 pool 數(shù)量為 1，作為頭結(jié)點(diǎn)不會(huì)破壞 usable_arenas 有序性
    if (nf == 1) {
        ao->nextarena = usable_arenas;
        ao->prevarena = NULL;
        if (usable_arenas)
            usable_arenas->prevarena = ao;
        usable_arenas = ao;
        if (nfp2lasta[1] == NULL) {
            nfp2lasta[1] = ao;
        }
        return;
    }

    if (nfp2lasta[nf] == NULL) {
        nfp2lasta[nf] = ao;
    } 
    // 如果 arena 本來(lái)就是包含 lastnf 個(gè)空閑 pool 的最后一個(gè)，現(xiàn)在空閑 pool 數(shù)量加 1，
    // 整個(gè) usable_arenas 還是有序的
    if (ao == lastnf) {
        return;
    }

    // arena->nfreepools 的增加導(dǎo)致 usable_arenas 失序，
    // 重新調(diào)整 arena 在 usable_arenas 的位置
    if (ao->prevarena != NULL) {
        ao->prevarena->nextarena = ao->nextarena;
    }
    else {
        usable_arenas = ao->nextarena;
    }
    ao->nextarena->prevarena = ao->prevarena;
    ao->prevarena = lastnf;
    ao->nextarena = lastnf->nextarena;
    if (ao->nextarena != NULL) {
        ao->nextarena->prevarena = ao;
    }
    lastnf->nextarena = ao;
}

首先將這個(gè)空閑的 pool 置為 ao->freepools 的頭結(jié)點(diǎn)，這樣可以保證最后釋放的 pool 會(huì)最先被使用，提高訪存效率，因?yàn)橹搬尫诺?pool 可能被置換出了物理內(nèi)存。然后根據(jù)不同情況更新 nfp2lasta，便于后續(xù)維護(hù) usable_arenas 的有序性。接著根據(jù) pool 釋放前后其所在 arena 狀態(tài)的變化做不同操作。

• 如果 arena 由可用狀態(tài)變成空閑狀態(tài)，并且系統(tǒng)中還有其他可用 arena，就調(diào)用 free() 將 arena 釋放掉歸還給操作系統(tǒng)。如果系統(tǒng)中僅有這一個(gè)空閑 arena 就不釋放，避免內(nèi)存抖動(dòng)。
• 如果 arena 由不可用狀態(tài)（所有 pool 都分配了）變成可用狀態(tài)，將其置為 usable_arenas 的頭結(jié)點(diǎn)。
• 如果 pool 釋放前后 arena 都是可用狀態(tài)，也就是一直都在 usable_arenas 鏈表中，如果其可用 pool 數(shù)量的增加導(dǎo)致 usable_arenas 鏈表失序，需要移動(dòng) arena 到合適位置來(lái)保持 usable_arenas 的有序性。

總結(jié)一下，本文首先介紹了 Python 內(nèi)存管理器的背景，是為了避免頻繁調(diào)用 malloc() 和 free() 來(lái)創(chuàng)建和釋放對(duì)象，采用內(nèi)存池的方案提高效率。然后介紹了內(nèi)存管理器的細(xì)節(jié)，Arena、Pool 和 Block 的含義，并且具體說(shuō)明了 Arena 和 Pool 的內(nèi)存布局及其相關(guān)的數(shù)據(jù)結(jié)構(gòu)，在此基礎(chǔ)上詳細(xì)展開(kāi)了內(nèi)存分配算法 pymalloc_alloc() 和 內(nèi)存釋放算法 pymalloc_free()。希望本文能對(duì)你理解 Python 的內(nèi)存管理有所幫助。

總結(jié)

到此這篇關(guān)于Python內(nèi)存管理器如何實(shí)現(xiàn)池化技術(shù)的文章就介紹到這了,更多相關(guān)Python內(nèi)存管理內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！