MySQL MEM_ROOT 內存分配機制深度解析：源碼級原理與啟發式算法

MEM_ROOT 核心定位

MEM_ROOT 是 MySQL 內部廣泛使用的內存分配器，採用啟發式分配算法，適用於：

• 查詢解析、優化階段的臨時對象
• 存儲過程/函數執行上下文
• 複雜連接操作的中間結果集
• 任何生命週期明確、批量釋放的場景

核心數據結構

MEM_ROOT 主結構

typedef struct st_mem_root {
    USED_MEM *free;           // 空閒塊鏈表頭
    USED_MEM *used;           // 已用塊鏈表頭
    USED_MEM *pre_alloc;      // 預分配塊
    size_t min_malloc;        // 移至 used 列表的閾值（默認 32 字節）
    size_t block_size;        // 初始塊大小
    unsigned int block_num;   // 實際塊計數（初始 4，用於擴容計算）
    unsigned int first_block_usage; // 首塊分配失敗計數
    void (*error_handler)(void);    // OOM 處理器
} MEM_ROOT;

USED_MEM 塊結構

typedef struct st_used_mem {
    struct st_used_mem *next; // 下一塊指針
    unsigned int left;        // 剩餘可用空間
    unsigned int size;        // 總大小
} USED_MEM;

雙鏈表管理機制

• free 列表：尚有剩餘空間的塊，按地址順序鏈接
• used 列表：空間耗盡或碎片過多的塊
• 分配時優先從 free 列表獲取，不足時申請新塊

初始化流程

void init_alloc_root(MEM_ROOT *mem_root, size_t block_size, size_t pre_alloc_size) {
    mem_root->free = mem_root->used = mem_root->pre_alloc = 0;
    mem_root->min_malloc = 32;
    mem_root->block_size = block_size - ALLOC_ROOT_MIN_BLOCK_SIZE;
    mem_root->error_handler = 0;
    mem_root->block_num = 4;  // 4 >> 2 = 1，確保首次擴容至少 1 倍
    mem_root->first_block_usage = 0;
}

核心分配邏輯 alloc_root()

void *alloc_root(MEM_ROOT *mem_root, size_t length) {
    length = ALIGN_SIZE(length);  // 雙字節對齊
    
    // 1. 遍歷 free 列表尋找可用塊
    USED_MEM **prev = &mem_root->free;
    USED_MEM *next = *prev;
    
    // 碎片整理：首塊連續 10 次分配失敗且剩餘 < 4KB，移至 used
    if (next && next->left < length) {
        if (mem_root->first_block_usage++ >= ALLOC_MAX_BLOCK_USAGE_BEFORE_DROP 
            && next->left < ALLOC_MAX_BLOCK_TO_DROP) {
            *prev = next->next;
            next->next = mem_root->used;
            mem_root->used = next;
            mem_root->first_block_usage = 0;
            next = *prev;
        }
    }
    
    // 尋找足夠大的塊
    for (; next && next->left < length; next = next->next)
        prev = &next->next;
    
    // 2. 無可用塊，申請新內存
    if (!next) {
        size_t block_size = mem_root->block_size * (mem_root->block_num >> 2);
        size_t get_size = MY_MAX(length + ALIGN_SIZE(sizeof(USED_MEM)), block_size);
        
        next = (USED_MEM*) my_malloc(get_size, MYF(MY_WME | ME_FATALERROR));
        if (!next) { /* 錯誤處理 */ }
        
        mem_root->block_num++;
        next->next = *prev;
        next->size = get_size;
        next->left = get_size - ALIGN_SIZE(sizeof(USED_MEM));
        *prev = next;  // 二級指針技巧：直接修改前驅節點的 next
    }
    
    // 3. 從塊尾部分配（指針算術）
    uchar *point = (uchar*)next + (next->size - next->left);
    
    // 4. 更新剩餘空間，檢查是否移至 used
    if ((next->left -= length) < mem_root->min_malloc) {
        *prev = next->next;
        next->next = mem_root->used;
        mem_root->used = next;
        mem_root->first_block_usage = 0;
    }
    return point;
}

關鍵算法特點

指數增長策略

block_size = 初始大小 * (block_num >> 2)

• 前 4 次分配：1x 基礎大小
• 第 5-8 次：2x
• 第 9-12 次：4x
• 以此類推，減少系統調用次數

二級指針鏈表操作

prev = &next->next 使 *prev = new_block 可直接修改前驅節點的 next 指針，無需特殊情況處理頭節點。

碎片保護機制

• first_block_usage 計數器防止首塊長期佔用微小剩餘空間
• min_malloc = 32 閾值避免產生大量微小碎片塊
• 塊移動到 used 列表後不再參與分配，僅在銷毀時統一釋放

銷毀與重置

void free_root(MEM_ROOT *mem_root, MYF my_flags) {
    // 釋放 used 列表所有塊
    for (USED_MEM *next = mem_root->used; next; ) {
        USED_MEM *tmp = next;
        next = next->next;
        my_free(tmp);
    }
    // 釋放 free 列表所有塊
    for (USED_MEM *next = mem_root->free; next; ) {
        USED_MEM *tmp = next;
        next = next->next;
        my_free(tmp);
    }
    // 重置狀態（保留 pre_alloc 供復用）
    mem_root->used = mem_root->free = 0;
    mem_root->first_block_usage = 0;
}

實際應用場景與調優建議

總結

MEM_ROOT 通過啟發式指數增長、雙鏈表分級管理、碎片閾值保護三大機制，在 MySQL 內部實現了高效、低碎片的內存分配。其設計思想對開發高效能 C/C++ 內存池有重要參考價值。