Python 中的記憶體管理

語言: CN / TW / HK

Python 中一切皆物件,這些物件的記憶體都是在執行時動態地在堆中進行分配的,就連 Python 虛擬機器使用的棧也是在堆上模擬的。既然一切皆物件,那麼在 Python 程式執行過程中物件的建立和釋放就很頻繁了,而每次都用 malloc() 和 free() 去向作業系統申請記憶體或釋放記憶體就會對效能造成影響,畢竟這些函式最終都要發生系統呼叫引起上下文的切換。下面我們就來看看 Python 中的記憶體管理器是如何高效管理記憶體的。

其實核心就是池化技術,一次性向作業系統申請一批連續的記憶體空間,每次需要建立物件的時候就在這批空間內找到空閒的記憶體塊進行分配,物件釋放的時候就將對應的記憶體塊標記為空閒,這樣就避免了每次都向作業系統申請和釋放記憶體,只要程式中總的物件記憶體空間穩定,Python 向作業系統申請和釋放記憶體的頻率就會很低。這種方案是不是很熟悉,資料庫連線池也是類似的思路。一般後端應用程式也是提前跟資料庫建立多個連線,每次執行 SQL 的時候就從中找一個可用的連線與資料庫進行互動,SQL 完成的時候就將連線交還給連線池,如果某個連線長時間未被使用,連線池就會將其釋放掉。本質上,這些都是用空間換時間,消耗一些不算太大的記憶體,降低諸如記憶體申請和 TCP 建立連線等耗時操作的頻率,提高程式整體的執行速度。

接下來具體看看 Python 的記憶體管理器是如何實現池化技術的,先概要介紹記憶體層次結構及分配記憶體的流程,然後結合原始碼詳細展開。

記憶體層次結構

Python 記憶體管理器對記憶體進行了分層,從大到小分別為 arena、pool 和 block。arena 是記憶體管理器直接呼叫 malloc() 或 calloc() 向作業系統申請的一大塊記憶體,Python 中物件的建立和釋放都是在 arena 中進行分配和回收。在 arena 內部又分成了多個 pool,每個 pool 內又分成了多個大小相等的 block,每次分配記憶體的時候都是從某個 pool 中選擇一塊可用的 block 返回。每個 pool 內的 block 的大小是相等的,不同 pool 的 block 大小可以不等。

arena、pool 和 block 的大小在 32 位機器和 64 位機器上有所不同,block 的大小必須是 ALIGNMENT 的倍數,並且最大為 512 位元組,下表列出了不同機器上各種記憶體的大小。

32 位機器 64 位機器
arena size 256 KB 1 MB
pool size 4 KB 16 KB
ALIGNMENT 8 B 16 B

以 64 位機器為例,所有可能的 block 的大小為 16、32、48 … 496、512,每個大小都對應一個分級(size class),從小到大依次為0、1、2 … 30、31。每次分配記憶體的時候就是找到一個不小於請求大小的最小的空閒 block。對 block 的大小進行分級是為了適應不同大小的記憶體請求,減少記憶體碎片的產生,提高 arena 的利用率。

記憶體管理邏輯

瞭解了 arena、pool 和 block 的概念後就可以描述記憶體分配的邏輯了,假如需要的記憶體大小為 n 位元組

  1. 如果 n > 512,回退為 malloc(),因為 block 最大為 512 位元組
  2. 否則計算出不小於 n 的最小的 block size,比如 n=105,在 64 位機器上最小的 block size 為 112
  3. 找到對應 2 中 block size 的 pool,從中分配一個 block。如果沒有可用的 pool 就從可用的 arena 中分配一個 pool,如果沒有可用的 arena 就用 malloc() 向作業系統申請一塊新的 arena

釋放記憶體的邏輯如下

  1. 先判斷要釋放的記憶體是不是由 Python 記憶體管理器分配的,如果不是直接返回
  2. 找到要釋放的記憶體對應的 block 和 pool,並將 block 歸還給 pool,留給下次分配使用
  3. 如果釋放的 block 所在的 arena 中除了自己之外其他的都是空閒的,那麼在 block 歸還之後整個 arena 都是空閒的,就可以將 arena 用 free() 釋放掉還給作業系統

Python 中的物件一般都不大,並且生命週期很短,所以 arena 一旦申請之後,物件的分配和釋放大部分情況下都是在 arena 中進行的,提高了效率。

上文已經將 Python 記憶體管理器的核心邏輯描述清楚了,只不過有一些細節的問題還沒解決,比如記憶體分配的時候怎麼根據 block size 找到對應的 pool,這些 pool 之間怎麼關聯起來的,記憶體釋放的時候又是怎麼判斷要釋放的記憶體是不是 Python 記憶體管理器分配的,等等。下面結合原始碼將記憶體分配和釋放的邏輯詳細展開。

先介紹 arena 和 pool 的記憶體佈局和對應的資料結構,然後再具體分析 pymalloc_alloc() 和 pymalloc_free() 的邏輯,以 64 位機器為例介紹。

記憶體佈局及對應的資料結構

Arena

arena 為 1 MB,pool 為 16 KB,pool 在 arena 中是相鄰的,一個 arena 中最多有 1 MB / 16 KB = 64 個 pool。Python 記憶體管理器會將 arena 中第一個 pool 的首地址跟 POOL_SIZE 對齊,這樣每個 pool 的首地址都是 POOL_SIZE 的整數倍,給定任意記憶體地址都可以很方便的計算出其所在 pool 的首地址,這個特性在記憶體釋放的時候會用到。POOL_SIZE 在 32 位機器上是 4 KB,在 64 位機器上是 16 KB,這樣做還有另外一個好處就是讓每個 pool 正好落在一個或多個物理頁中,提高了訪存效率。上圖中的灰色記憶體塊就是為了對齊而丟棄掉的,如果 malloc() 分配的記憶體首地址恰好對齊了,那麼 pool 的數量就是 64,否則就是 63。當然 arena 不是一開始就將全部的 pool 都劃分出來,而是在沒有可用的 pool 的時候才會去新劃分一個,當所有的 pool 全部劃分之後佈局如上圖所示。

每個 arena 都由結構體 struct arena_object 來表示,但不是所有 struct arena_object 都有對應的 arena,因為 arena 釋放之後對應的 struct arena_object 還保留著,這些沒有對應 arena 的 struct arena_object 存放在單鏈表 unused_arena_objects 中,在下次分配 arena 時可以拿來使用。如果 struct arena_object 有對應的 arena,並且 arena 中有可以分配的 pool,那麼 struct arena_object 會存放在 usable_arenas 這個雙向連結串列中,同時,所有的 struct arena_object 無論有沒有對應的 arena 都存在陣列 arenas 中。usable_arenas 中 arena 是按照其包含的空閒 pool 的數量從小到大排序的,這麼排序是為了讓已經使用了更多記憶體的 arena 在下次分配 pool 的時候優先被使用,那麼在釋放記憶體的時候排在後面的那些擁有更多空閒記憶體的 arena 就有更大可能變成完全空閒狀態,從而被釋放掉將其記憶體空間歸還給作業系統,降低整體的記憶體消耗。

struct arena_object 的結構及各欄位含義如下

struct arena_object {
    uintptr_t address; // 指向 arena 的起始地址,如果當前 arena_object 沒有對應的 arena 記憶體則 address = 0
    block* pool_address; // pool 需要初始化之後才能使用,pool_address 指向的地址可以用來初始化一個 pool 用於分配
    int nfreepools; // arena 中目前可以用來分配的 pool 的數量
    uint ntotalpools; // arena 中 pool 的總數量,64 或 63
    struct pool_header* freepools; // arena 中可以分配的 pool 構成一個單鏈表,freepools 指標是單鏈表的第一個節點
    struct arena_object* nextarena; // 在 usable_arenas 或 unused_arena_objects 指向下一個節點
    struct arena_object* prevarena; // 在 usable_arenas 中指向上一個節點
}

Pool

pool 的內部等分成多個大小相等的 block,與 arena 一樣,也有一個數據結構 struct pool_header 用來表示 pool。與 arena 不同的是,struct pool_header 位於 pool 的內部,在最開始的一段記憶體中,緊接之後的是第一個 block,為了讓每個 block 的地址都能對齊機器訪問記憶體的步長,可能需要在 struct pool_header 和第一個 block 之間做一些 padding,圖中灰色部分所示。這部分 padding 不一定存在,在 64 位機器上 sizeof(struct pool_header) 為 48 位元組,本來就已經對齊了,後面就直接跟第一個 block,中間沒有 padding。即使如此,pool 最後的一小塊記憶體也可能用不上,上圖中下面的灰色部分所示,因為每個 pool 中 block 大小是相等的,假設 block 為 64 位元組,一個 pool 中可以分出 255 個 block,前面 48 位元組儲存 struct pool_header,後面 16 位元組用不上,當然如果 block 大小為 48 位元組或 16 位元組那麼整個 pool 就會被完全利用上。同 arena 一樣,pool 一開始不是把所有的 block 全部劃分出來,而是在沒有可用 block 的時候才回去新劃分一個,在所有的 block 全部劃分之後 pool 的佈局如上圖所示。

接下來看看 struct pool_header 的結構

struct pool_header {
    union { block *_padding;
            uint count; } ref; // 當前 pool 中已經使用的 block 數量,共用體中只有 count 欄位有意義,_padding 是為了讓 ref 欄位佔 8 個位元組,這個特性在 usedpools 初始化的時候有用
    block *freeblock; // pool 中可用來進行分配的 block 單鏈表的頭指標
    struct pool_header *nextpool; // 在 arena_object.freepools 或 usedpools 中指向下一個 pool
    struct pool_header *prevpool; // 在 usedpools 中指向上一個 pool
    uint arenaindex; // pool 所在 arena 在 arenas 陣列中的索引
    uint szidx; // pool 中 block 大小的分級
    uint nextoffset; // 需要新的 block 可以從 nextoffset 處分配
    uint maxnextoffset; // nextoffset 最大有效值
};

typedef struct pool_header *poolp;

每個 pool 一旦被分配之後一定會處於 full、empty 和 used 這 3 種狀態中的一種。

  • full 所有的 block 都分配了
  • empty 所有的 block 都是空閒的,都可用於分配,所有處於 empty 狀態的 pool 都在其所在 arena_object 的 freepools 欄位表示的單鏈表中
  • used 有已分配的 block,也有空閒的 block,所有處於 used 狀態的 pool 都在全域性陣列 usedpools 中某個元素指向的雙向迴圈連結串列中

usedpools 是記憶體分配最常訪問的資料結構,分配記憶體時先計算申請的記憶體大小對應的 block 分級 i,usedpools[i+i] 指向的就是屬於分級 i 的所有處於 used 狀態的 pool 構成的雙向迴圈連結串列的頭結點,如果連結串列不空就從頭結點中選擇一個空閒 block 分配。接下來分析一下為什麼 usedpools[i+i] 指向的就是屬於分級 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),
    …
}

將巨集定義稍微展開一下

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) 表示陣列 usedpools 中第 2*x 個元素的地址減去兩個指標的大小也就是 16 位元組(64 位機器),假設陣列 usedpools 首地址為 1000,則陣列初始化的值如下圖所示

假設 i = 2,則 usedpools[i+i] = usedpools[4] = 1016 ,陣列元素的型別為 poolp 也就是 struct pool_header *,如果認為 1016 儲存的是 struct pool_header,那麼 usedpools[4] 和 usedpools[5] 的值也就是地址 1032 和 1040 儲存的值,分別是欄位 nextpool 和 prevpool 的值,可以得到

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

usedpools[4] 用指標 p 表示就有 p->prevpool = p->nextpool = p ,那麼 p 就是雙向迴圈連結串列的哨兵節點,初始化的時候哨兵節點的前後指標都指向自己,表示當前連結串列為空。

雖然 usedpools 的定義非常繞,但是這樣定義有個好處就是省去了哨兵節點的資料域,只保留前後指標,可以說是將節省記憶體做到了極致。

下面分別看看原始碼是怎麼實現記憶體分配和釋放的邏輯的,下文中的原始碼基於 Python 3.10.4。另外說明一下,原始碼中有比本文詳細的多註釋說明,有興趣的讀者可以直接看原始碼,本文為了程式碼不至於過長會對程式碼做簡化處理並且省略掉了大部分註釋。

記憶體分配

記憶體分配的主邏輯在函式 pymalloc_alloc 中,簡化後代碼如下

static inline void*
pymalloc_alloc(void *ctx, size_t nbytes)
{  
    // 計算請求的記憶體大小 ntybes 所對應的記憶體分級 size
    uint size = (uint)(nbytes - 1) >> ALIGNMENT_SHIFT;
    // 找到屬於記憶體分級 size 的 pool 所在的雙向迴圈連結串列的頭指標 pool
    poolp pool = usedpools[size + size];
    block *bp;
    // pool != pool->nextpool,說明 pool 不是哨兵節點,是真正的 pool
    if (LIKELY(pool != pool->nextpool)) {
        ++pool->ref.count;
        // 將 pool->freeblock 指向的 block 分配給 bp,因為 pool 是從 usedpools 中取的,
        // 根據 usedpools 的定義,pool->freeblock 指向的一定是空閒的 block
        bp = pool->freeblock;
        // 如果將 bp 分配之後 pool->freeblock 為空,需要從 pool 中劃分一個空閒 block
        // 到 pool->freeblock 連結串列中留下次分配使用
        if (UNLIKELY((pool->freeblock = *(block **)bp) == NULL)) {
            pymalloc_pool_extend(pool, size);
        }
    }
    // 如果沒有對應記憶體分級的可用 pool,就從 arena 中分配一個 pool 之後再從中分配 block
    else {
        bp = allocate_from_new_pool(size);
    }
    
    return (void *)bp;
}

主體邏輯還是比較清晰的,程式碼中註釋都做了說明,不過還是要解釋一下下面的這個判斷語句。

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

前文已經介紹過 pool->freeblock 表示 pool 中可用來進行分配的 block 所在單鏈表的頭指標,型別為 block*,但是 block 的定義為 typedef uint8_t block;,並不是一個結構體,所以沒有指標域,那麼是怎麼實現單鏈表的呢。考慮到 pool->freeblock 的實際含義,只需要把空閒 block 用單鏈表串起來就可以了,不需要資料域,Python 記憶體管理器把空閒 block 記憶體的起始 8 位元組(64 位機器)當做虛擬的 next 指標,指向下一個空閒 block,具體是通過 *(block **)bp 實現的。首先用 (block **) 將 bp 轉換成 block 的二級指標,然後用 * 解引用,將 bp 指向記憶體的首地址內容轉換成 (block *) 型別,表示下一個 block 的地址,不得不說,C 語言真的是可以為所欲為。再來看一下上面判斷語句,首先將 bp 的下一個空閒 block 地址賦值給 pool->freeblock ,如果是 NULL 證明沒有更多空閒 block,需要呼叫 pymalloc_pool_extend 擴充。

pymalloc_pool_extend 的原始碼簡化後如下

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

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

}

過程也很清晰,如果有更多空間就劃分一個 block 到 pool->freeblock ,如果沒有更多空間就將 pool 從 usedpools[size+size] 中移除。 pool->nextoffset 指向的是 pool 中從未被使用過記憶體的地址,分配 block 時候優先使用 pool->nextoffset 之前的空閒 block,這些空閒的 block 一般是之前分配過後來又被釋放到 pool->freeblock 中的。這種複用空閒 block 的方式讓 pool 更加經久耐用,如果每次都從 pool->nextoffset 劃分一個新的 block,pool 很快就會被消耗完,變成 full 狀態。

在 pymalloc_alloc 中如果沒有可用 pool 就會呼叫 allocate_from_new_pool 先分配一個新的 pool,再從新的 pool 中分配 block,其原始碼簡化後如下

static void*
allocate_from_new_pool(uint size)
{
    // 沒有可用的 arena 就新申請一個
    if (UNLIKELY(usable_arenas == NULL)) {
        usable_arenas = new_arena();
        if (usable_arenas == NULL) {
            return NULL;
        }
        // 將新的 arena 作為 usable_arenas 連結串列的頭結點
        usable_arenas->nextarena = usable_arenas->prevarena = NULL;
        nfp2lasta[usable_arenas->nfreepools] = usable_arenas;
    }

    // 如果有可用 arena 就從中分配一個空閒 pool,並調整當前 arena 在 usable_arenas 中的位置,使 usable_arenas 按空閒 pool 的數量從小到大排序
    if (nfp2lasta[usable_arenas->nfreepools] == usable_arenas) {
        nfp2lasta[usable_arenas->nfreepools] = NULL;
    }
    if (usable_arenas->nfreepools > 1) {
        nfp2lasta[usable_arenas->nfreepools - 1] = usable_arenas;
    }

    // 執行到這裡,usable_arenas->freepools 就是當前需要的可用 pool
    poolp pool = usable_arenas->freepools;
    // 更新 freepools 連結串列和 nfreepools 計數
    if (LIKELY(pool != NULL)) {
        usable_arenas->freepools = pool->nextpool;
        usable_arenas->nfreepools--;
        // 分配之後,如果 arena 中沒有空閒 pool,需要更新 usable_arenas 連結串列
        if (UNLIKELY(usable_arenas->nfreepools == 0)) {
            usable_arenas = usable_arenas->nextarena;
            if (usable_arenas != NULL) {
                usable_arenas->prevarena = NULL;
            }
        }
    }
    // 如果當前 arena 中沒有可用 pool,就重新劃分一個
    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 中沒有空閒 pool,需要更新 usable_arenas 連結串列
        if (usable_arenas->nfreepools == 0) {
            usable_arenas = usable_arenas->nextarena;
            if (usable_arenas != NULL) {
                usable_arenas->prevarena = NULL;
            }
        }
    }

    // 執行到這裡,變數 pool 就是找到的可用 pool,將其置為連結串列 usedpools[size+size] 的頭節點
    block *bp;
    poolp next = usedpools[size + size];
    pool->nextpool = next;
    pool->prevpool = next;
    next->nextpool = pool;
    next->prevpool = pool;
    pool->ref.count = 1;
    // 如果 pool 的記憶體分級跟請求的一致,直接從中分配一個 block 返回
    // 證明這個 pool 之前被使用之後又釋放到 freepools 中了
    // 並且當時使用的時候記憶體分級也是 size
    if (pool->szidx == size) {
        bp = pool->freeblock;
        pool->freeblock = *(block **)bp;
        return bp;
    }
    
    // 執行到這裡,說明 pool 是 arena 新劃分的,需要對其進行初始化
    // 然後分配 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;
}

這段程式碼比較長,歸納一下做了下面 3 件事

  1. 如果沒有可用的 arena 就重新申請一個
  2. 從可用的 arena 中分配一個新的 pool
  3. 從分配的 pool 中分配空閒的 block

首先是 arena 的申請,申請流程在函式 new_arena() 中,申請完之後將對應的 arena_object 置為 雙線連結串列 usable_arenas 的頭結點,並且前後指標都置為 NULL,因為只有在沒有可用 arena 的時候才回去呼叫 new_arena(),所以申請之後系統裡只有一個可用 arena。另外還有一個操作如下

nfp2lasta[usable_arenas->nfreepools] = usable_arenas;

nfp2lasta 是一個數組, nfp2lasta[i] 表示的是在 usable_arenas 連結串列中,空閒 pool 的數量為 i 的所有 arena 中最後一個 arena。前文已經說明 usable_arenas 是按照 arena 中空閒 pool 的數量從小到大排序的,為了維護 usable_arenas 的有序性,在插入或刪除一個 arena 的時候需要找到對應的位置,時間複雜度為 O(N),為了避免線性搜尋,Python 3.8 引入了 nfp2lasta ,將時間複雜度降為常量級別。

有了可用的 arena 就可以從中分配 pool 了,分配 pool 之後 arena->nfreepools 就會減少,需要更新 nfp2lasta,由於使用的是連結串列 usable_arenas 的頭結點,並且是減少其空閒 pool 數量,所以整個連結串列依然有序。接下來優先複用 arena->freepools 中空閒的 pool,如果沒有就從 arena->pool_address 指向的未使用記憶體處新劃分一個 pool,這點跟 pool 中複用空閒 block 的策略是一樣的。

分配了可用的 pool,先將其置為連結串列 usedpools[size+size] 的頭結點,然後從中分配 block,如果 pool 不是從新分配的 arena 獲得的,那麼 pool 就是之前初始化使用之後釋放掉的,如果 pool 的分級恰好就是請求的記憶體分級那麼直接從 pool->freeblock 分配 block,否則需要將 pool 重新初始化,當然如果 pool 來自新分配的 arena 也要進行初始化。初始化的時候,先將第一個 block 的地址進行記憶體對齊,然後將 pool->freeblock 指向第 2 個 block 留下次分配使用(第 1 個 block 本次要返回),將 pool->nextoffset 指向第 3 個 block,在下次劃分新的 block 時使用。

記憶體釋放

記憶體釋放的主邏輯在 pymalloc_free 函式中,程式碼簡化後如下

static inline int
pymalloc_free(void *ctx, void *p)
{
    // 假設 p 是 pool 分配的,計算 p 所在 pool 的首地址
    poolp pool = POOL_ADDR(p);
    // 如果 p 不是記憶體管理器分配的直接返回
    if (UNLIKELY(!address_in_range(p, pool))) {
        return 0;
    }
    
    // 將 p 指向的 block 歸還給 pool,置為 pool->freeblock 的頭結點
    block *lastfree = pool->freeblock;
    *(block **)p = lastfree;
    pool->freeblock = (block *)p;
    pool->ref.count--;
    // 如果 pool 原來處於 full 狀態,現在有一個空閒的 block 就變成了 used 狀態
    // 需要將其作為頭結點插到 usedpools[size+size] 中
    if (UNLIKELY(lastfree == NULL)) {
        insert_to_usedpool(pool);
        return 1;
    }

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

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

pymalloc_free 函式的邏輯也很清晰

  1. 計算地址 p 所在 pool 首地址,前文介紹過每個 pool 首地址都是 POOL_SIZE 的整數倍,所以將 p 的低位置 0 就得到了 pool 的地址
  2. address_in_range(p, pool) 判斷 p 是否是由 pool 分配的,如果不是直接返回
  3. 將 p 指向的 block 釋放掉,被 pool->freeblock 回收
  4. 如果 pool 開始為 full 狀態,那麼回收 block 之後就是 used 狀態,呼叫函式 insert_to_usedpool(pool) 將其置為 usedpools[size+size] 的頭結點。這裡的策略跟 usable_arenas 一樣,優先使用快滿的 pool,讓比較空閒的 pool 有較高的概率被釋放掉。
  5. 如果 pool 回收 block 之後變成 empty 狀態,需要呼叫 insert_to_freepool(pool) 將 pool 也釋放掉

address_in_range 函式如下

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

這段邏輯能在常量時間內判斷出 p 是否由 pool 分配,但是存在一個可能出問題的地方,畢竟這裡的 pool 是在假設 p 是由 pool 分配的前提下計算出來的,有可能 pool 指向的地址可能還沒被初始化, pool->arenaindex 操作可能會出錯。Python 3.10 在這個 commit 中利用基數樹來判斷任意一個地址 p 是不是由記憶體管理器分配的,避免了可能出現的記憶體訪問錯誤。

insert_to_usedpool 函式中只是簡單的指標操作就不展開了,insert_to_freepool 稍微複雜一點,下面再展開一下

static void
insert_to_freepool(poolp pool)
{
    poolp next = pool->nextpool;
    poolp prev = pool->prevpool;
    next->prevpool = prev;
    prev->nextpool = next;
    // 將 pool 置為 ao->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];
    // 如果 arena 是排在最後的包含 nf 個空閒 pool 的 arena,
    // 需要將 nfp2lasta[nf] 置為 arena 的前驅結點或 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 變成完全空閒狀態,並且系統中還有其他可用 arena,
    // 需要將 arena 從 usable_arenas 中移除並呼叫 free() 函式將其釋放歸還給作業系統
    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 頭結點,
    // 因為 arena 空閒 pool 數量為 1,作為頭結點不會破壞 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 本來就是包含 lastnf 個空閒 pool 的最後一個,現在空閒 pool 數量加 1,
    // 整個 usable_arenas 還是有序的
    if (ao == lastnf) {
        return;
    }

    // arena->nfreepools 的增加導致 usable_arenas 失序,
    // 重新調整 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;
}

首先將這個空閒的 pool 置為 ao->freepools 的頭結點,這樣可以保證最後釋放的 pool 會最先被使用,提高訪存效率,因為之前釋放的 pool 可能被置換出了實體記憶體。然後根據不同情況更新 nfp2lasta,便於後續維護 usable_arenas 的有序性。接著根據 pool 釋放前後其所在 arena 狀態的變化做不同操作。

  1. 如果 arena 由可用狀態變成空閒狀態,並且系統中還有其他可用 arena,就呼叫 free() 將 arena 釋放掉歸還給作業系統。如果系統中僅有這一個空閒 arena 就不釋放,避免記憶體抖動。
  2. 如果 arena 由不可用狀態(所有 pool 都分配了)變成可用狀態,將其置為 usable_arenas 的頭結點。
  3. 如果 pool 釋放前後 arena 都是可用狀態,也就是一直都在 usable_arenas 連結串列中,如果其可用 pool 數量的增加導致 usable_arenas 連結串列失序,需要移動 arena 到合適位置來保持 usable_arenas 的有序性。

總結一下,本文首先介紹了 Python 記憶體管理器的背景,是為了避免頻繁呼叫 malloc() 和 free() 來建立和釋放物件,採用記憶體池的方案提高效率。然後介紹了記憶體管理器的細節,Arena、Pool 和 Block 的含義,並且具體說明了 Arena 和 Pool 的記憶體佈局及其相關的資料結構,在此基礎上詳細展開了記憶體分配演算法 pymalloc_alloc() 和 記憶體釋放演算法 pymalloc_free() 。希望本文能對你理解 Python 的記憶體管理有所幫助。