自製編程語言 Crowbar(v0.1) 解析器內存分配機制深度剖析

自製編程語言 Crowbar(v0.1) 解析器內存分配機制深度剖析

Crowbar 是一個教學級解釋型語言實現。本文深入剖析其解析器構建階段的內存分配體系：從 `MEM_Storage` 內存池設計、`MEM_Controller` 控制器架構、到 `MEM_malloc_func` 底層分配流程，完整還原解析器創建時的內存申請鏈路。

整體架構概覽

CRB_create_interpreter()
  → MEM_open_storage(0)           // 創建內存池 Storage
  → MEM_storage_malloc()          // 從池中分配 Interpreter 結構體
  → 初始化各字段、註冊內置函數
  → 返回 Interpreter*

核心數據結構

1. 內存控制器 `MEM_Controller`

typedef struct MEM_Controller_tag {
    FILE *error_fp;           // 錯誤輸出流
    MEM_ErrorHandler handler; // 錯誤回調
    MEM_FailMode fail_mode;   // 失敗策略：退出/返回
    Header *block_header;     // 已分配塊鏈表頭（調試用）
} *MEM_Controller;

全局默認控制器 `mem_default_controller`，宏 `MEM_CURRENT_CONTROLLER` 允許用戶覆蓋。

2. 內存池 `MEM_Storage`

struct MEM_Storage_tag {
    MemoryPageList page_list;     // 頁鏈表頭
    int current_page_size;        // 頁大小（Cell數）
};
// 頁結構
struct MemoryPage_tag {
    int cell_num;          // 頁總 Cell 數
    int use_cell_num;      // 已用 Cell 數
    MemoryPageList next;   // 下一頁
    Cell cell[1];          // 柔性數組：Cell 聯合體數組
};
// Cell: 內存對齊基本單元
typedef union { long l_dummy; double d_dummy; void *p_dummy; } Cell;

**設計精華**：以 `Cell`（最大基本類型大小）為分配粒度，`MemoryPage` 批量向系統申請內存，`Storage` 管理頁鏈表，實現**內存池/區域分配器**，避免頻繁系統調用，天然支持批量釋放。

3. 調試用塊頭 `Header`

struct HeaderStruct {
    int size;           // 用戶請求大小
    char *filename;     // 分配文件
    int line;           // 分配行號
    Header *prev, *next; // 雙向鏈表
    unsigned char mark[4]; // 邊界標記 0xCD
};
// 對齊填充後的 Header
union Header_tag { HeaderStruct s; Align u[HEADER_ALIGN_SIZE]; };

僅在 `DEBUG` 模式啟用，用於檢測越界、洩漏、雙重釋放。

關鍵分配流程詳解

步驟 1：`MEM_open_storage(0)` 創建內存池

MEM_Storage MEM_open_storage_func(MEM_Controller ctl, char *file, int line, int page_size) {
    MEM_Storage storage = MEM_malloc_func(ctl, file, line, sizeof(struct MEM_Storage_tag));
    storage->page_list = NULL;
    storage->current_page_size = (page_size > 0) ? page_size : DEFAULT_PAGE_SIZE; // 1024 Cells
    return storage;
}

先從系統堆分配 `MEM_Storage_tag` 結構體本身（約 16 字節），設置默認頁大小 1024 Cells（≈ 16KB）。

步驟 2：`MEM_malloc_func` 系統級分配（DEBUG 模式）

void *MEM_malloc_func(MEM_Controller ctl, char *file, int line, size_t size) {
    size_t alloc_size = size + sizeof(Header) + MARK_SIZE; // 頭+尾標記
    void *ptr = malloc(alloc_size); // 系統 malloc
    if (!ptr) error_handler(...);
    memset(ptr, 0xCC, alloc_size); // 填充 0xCC 檢測未初始化讀取
    set_header(ptr, size, file, line); // 填充 Header
    set_tail(ptr, alloc_size);         // 尾部標記
    chain_block(ctl, (Header*)ptr);    // 掛入控制器塊鏈表
    return (char*)ptr + sizeof(Header); // 返回用戶區起始地址
}

非 DEBUG 模式直接 `return malloc(size);`。

步驟 3：`MEM_storage_malloc` 內存池分配（核心）

void *MEM_storage_malloc_func(MEM_Controller ctl, char *file, int line, MEM_Storage storage, size_t size) {
    int cell_num = ((size - 1) / CELL_SIZE) + 1; // 向上取整所需 Cell 數

    // 情況 A：當前頁有足夠剩餘空間
    if (storage->page_list && 
        storage->page_list->use_cell_num + cell_num < storage->page_list->cell_num) {
        void *p = &(storage->page_list->cell[storage->page_list->use_cell_num]);
        storage->page_list->use_cell_num += cell_num;
        return p;
    }

    // 情況 B：需分配新頁
    int alloc_cell_num = (cell_num > storage->current_page_size) ? cell_num : storage->current_page_size;
    MemoryPage *new_page = MEM_malloc_func(ctl, file, line, 
        sizeof(MemoryPage) + CELL_SIZE * (alloc_cell_num - 1));
    new_page->next = storage->page_list; // 頭插法
    new_page->cell_num = alloc_cell_num;
    new_page->use_cell_num = cell_num;
    storage->page_list = new_page;
    return &(new_page->cell[0]);
}

**關鍵點**：

• **首次分配** `Interpreter` 結構體（約幾百字節），`cell_num` 很小，滿足情況 B，分配一頁 1024 Cells，使用前幾個 Cell，剩餘留待後續解析器構建（AST 節點、符號表等）使用。
• **無碎片整理**：線性分配，極快；銷毀整個 `Storage` 時一次性釋放所有頁，O(1) 批量釋放。
• **對齊保證**：`Cell` 聯合體包含 `long`、`double`、`void*`，滿足最大基本類型對齊要求。

解析器創建完整調用鏈

CRB_create_interpreter()
  → storage = MEM_open_storage(0)
      → storage = MEM_malloc_func(ctl, ..., sizeof(MEM_Storage_tag)) // 系統分配 Storage 結構
  → interpreter = MEM_storage_malloc(storage, sizeof(CRB_Interpreter_tag))
      → cell_num = ceil(sizeof(Interpreter)/CELL_SIZE)
      → 新頁 1024 Cells，Interpreter 置於頁首
  → 初始化 interpreter 字段
  → add_native_functions(interpreter) // 後續分配也將從同一 Storage 頁獲取
  → return interpreter

設計優勢總結

總結

Crowbar 的內存分配體系展示了**區域內存分配器**的教科書級實現：以頁為單位向系統申請，以 Cell 為粒度內部劃分，線性分配、批量釋放、天然對齊、調試友好。這種設計廣泛應用於編譯器、解釋器、游戲引擎、數據庫等高性能系統中。理解其 `Storage`→`Page`→`Cell` 三層架構與 `MEM_storage_malloc` 分配邏輯，是掌握系統級內存管理的關鍵一課。