Python記憶體管理器如何實現池化技術

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 中指向上一個節點
}

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;

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

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

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))

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;

}

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

nfp2lasta[usable_arenas->nfreepools] = usable_arenas;

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

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

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