2023q1 第 5 週測驗題

目的: 檢驗學員對記憶體管理、紅黑樹，和並行程式設計的認知

作答表單: 測驗 1-2 (針對 Linux 核心「設計」/「實作」課程)

測驗 `1`

在第一次作業的解說、〈你所不知道的 C 語言：記憶體管理、對齊及硬體特性〉和〈你所不知道的 C 語言：函式呼叫篇〉提到記憶體配置器的實作考量，我們可將這部份的認知應用於 memory pool，程式碼可見: mpool

mpool.h : 規範公開介面，包含 pool_init, pool_malloc, pool_calloc, pool_realloc, pool_free 等函式
mpool.c

請補完程式碼，使其運作符合程式註解提及的行為。作答規範: (皆不包含小括號 [即 ( 和 )])

AAAA, BBBB, CCCC, DDDD, FFFF, GGGG, HHHH 皆為 identifier，不是常數或 integer literal
EEEE : 變數名稱
以最精簡且考慮硬體平台特性的方式回覆

延伸問題:

解釋上方程式碼運作原理，指出其設計和實作缺失，並予以改進。不用抄寫題目，專注於你對程式碼的理解
原本的程式碼只實作 first-fit 演算法，請重新實作為 best-fit
將 memory pool 程式碼引入到 fibdrv 或課程作業中

測驗 `2`

延伸測驗 1，我們可運用在〈並行和多執行緒程式設計〉和〈Linux 核心的紅黑樹〉所學，建構實際可在 GNU/Linux 運作的記憶體管理器。

簡易的 malloc 實作，可運用 sbrk 系統呼叫，用法是 sbrk(size)，後者是回傳原本的起始位置：

sbrk(0) 回傳 heap 的終點
sbrk(size) 回傳 (目前的 heap 終點位置 - size)，即增加 size 之前的終點位置

void *malloc(size_t size)
{
    void *ptr = sbrk(size);
    if (!ptr)
        return NULL;
    return ptr;
}

爲了確保 heap 內的記憶體是連續的，因此不能任意將中間的記憶體釋放回作業系統，於是需要一個機制以確認，heap 內的某個部分的記憶體是否爲 free。有了該機制，即可就能確保在 free 後，heap 內的記憶體還是連續的。

另一個好處是，每次呼叫 malloc 時不用頻繁呼叫 sbrk，而是去 heap 中尋找能否有空閒且足夠的記憶體即可。為此，我們需要一個結構在每塊記憶體的前面，size 用來知道這塊 block_meta_t 所管理的記憶體大小，next 則連接到下一塊 block_meta_t，然後我們需要一個指標global_base 來記錄開頭節點：

typedef struct block_meta {
    size_t size; /* 本 block_meta_t 後面的記憶體大小 */
    struct block_meta *next; /* 連接到下一塊 block_meta_t */
    int free; /* 是否爲 free */
} block_meta_t

#define META_SIZE sizeof(block_meta_t) 
void *global_base = NULL; /* 記錄開頭節點 */

每塊記憶體前面都必須要有這塊 block_meta_t，因此每次 malloc 時都需要更動爲：

sbrk(size + META_SIZE)

接下來，實作一個在所有 block 中尋找能否使用的空間，last 用來記錄最後的 block 在哪裏，程式碼如下:

block_meta_t *find_free_block(block_meta_t **last, size_t size)
{
    block_meta_t *cur = global_base;
    while (cur && !(cur->free && cur->size >= size)) {
        *last = cur;
        cur = cur->next;
    }
    return cur;
}

如果在目前的 heap 中找不到一塊空閒且足夠大小的空間，那就必須申請 sbrk 增加 heap 的大小，在上方 find_free_block 已找到 last，因此申請新的 block 時，只需將 last 跟 block 連接在一起就好：

block_meta_t *request_space(block_meta_t *last, size_t size)
{
    block_meta_t *block = sbrk(0);
    void *request = sbrk(size + META_SIZE);
    assert((void *) block == request); /* Not thread safe */
    if (request == (void *) -1)
        return NULL; /* sbrk failed */
    if (last) /* 首次 malloc 時，last 爲空，不用連接 */
        last->next; 
    block->size = size;
    block->next = NULL;
    block->free = 0;
    return block;
}

準備工作都完成，利用上方函式來實作 malloc 進入點 malloc(0)。爲了在 free 時以安全通過，因此每次 malloc(0) 都回傳一個 NULL：

void *malloc(size_t size)
{
    if (size <= 0)
        return NULL;

    block_meta_t block;	
    if (!global_base) { /* 首次 malloc */
        block = request_space(NULL, size);
        if (!block)
            return NULL;
        global_base = block;
    } else {
        block_meta_t *last = global_base;
        block = find_free_block(&last, size);
        if (!block) { /* 尋找失敗，申請 sbrk */
            block = request_space(last, size);
            if (!block)
                return NULL;
        } else /* 尋找成功，設定 block 爲 unfree */
            block->free = 0;
     }

    /* block 的大小爲 block_meta_t size，
     * 因此 block + 1 = block + META_SIZE
     * 回傳的記憶體不需要包括 meta 資訊
     */
    return block + 1; 
}

如此，簡易的 malloc 即可實作。本題額外考慮多執行緒環境，並運用紅黑樹來建構記憶體配置器，程式碼可見 alloc.c，編譯方式: (部分遮蔽)

$ gcc -O2 -Wall -Wextra -fPIC -I . -c alloc.c
$ gcc -shared -o libmy_alloc.so alloc.o

測試方式:

LD_PRELOAD=./libmy_alloc.so ps aux

關於此處 LD_PRELOAD，可對照看〈你所不知道的 C 語言：動態連結器篇〉。

請補完程式碼，使上述記憶體配置器得以正確運作。作答規範:

IIII 和 JJJJ 是表示式，皆不包含小括號
KKKK 和 LLLL 是表示式，需要呼叫 POSIX Thread 規範的函式

延伸問題:

解釋程式碼運作原理，說明如何搭配紅黑樹來實作 best-fit 策略
以第 3 週測驗和第 4 週測驗題目所及、調整過的紅黑樹程式碼，重寫上述程式碼，使其得以用低的記憶體開銷和處理更大的記憶體範圍
用 mmap 系統呼叫替換 sbrk
研讀〈針對多執行緒環境設計的 Memory allocator〉和過往課程學員針對 mimalloc 做的改進，探討 Linux 核心可用於改進記憶體配置效率的機制

mimalloc 報告: 2021 年和 2022 年

2023q1 第 5 週測驗題

測驗 1

測驗 2

測驗 `1`

測驗 `2`