--- tags: linux2023 --- # [2023q1](http://wiki.csie.ncku.edu.tw/linux/schedule) 第 5 週測驗題 :::info 目的: 檢驗學員對記憶體管理、紅黑樹，和並行程式設計的認知 ::: ==[作答表單: 測驗 1-2](https://docs.google.com/forms/d/e/1FAIpQLSfIF6JE1bZ-kBkV2tgCk87SIxJa8saVXa63k1TQ7_Kjx7_l5w/viewform)== (針對 Linux 核心「設計」/「實作」課程) ### 測驗 `1` 在[第一次作業的解說](https://hackmd.io/@sysprog/linux2023-lab0)、〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉和〈[你所不知道的 C 語言：函式呼叫篇](https://hackmd.io/@sysprog/c-function)〉提到記憶體配置器的實作考量，我們可將這部份的認知應用於 [memory pool](https://en.wikipedia.org/wiki/Memory_pool)，程式碼可見: [mpool](https://gist.github.com/jserv/8ae560f0095b45aaefa4386c71d7a326) * `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` : 變數名稱 * 以最精簡且考慮硬體平台特性的方式回覆 :::success 延伸問題: 1. 解釋上方程式碼運作原理，指出其設計和實作缺失，並予以改進。不用抄寫題目，專注於你對程式碼的理解 2. 原本的程式碼只實作 first-fit 演算法，請重新實作為 best-fit 3. 將 memory pool 程式碼引入到 [fibdrv](https://github.com/sysprog21/fibdrv) 或課程作業中 ::: --- ### 測驗 `2` 延伸測驗 `1`，我們可運用在〈[並行和多執行緒程式設計](https://hackmd.io/@sysprog/concurrency)〉和〈[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree)〉所學，建構實際可在 GNU/Linux 運作的記憶體管理器。 簡易的 malloc 實作，可運用 [sbrk](https://man7.org/linux/man-pages/man2/brk.2.html) 系統呼叫，用法是 `sbrk(size)`，後者是回傳原本的起始位置： * `sbrk(0)` 回傳 heap 的終點 * `sbrk(size)` 回傳 (目前的 heap 終點位置 - size)，即增加 size 之前的終點位置 ```c 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` 來記錄開頭節點： ```c 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 時都需要更動爲： ```c sbrk(size + META_SIZE) ``` 接下來，實作一個在所有 block 中尋找能否使用的空間，`last` 用來記錄最後的 block 在哪裏，程式碼如下: ```c 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 連接在一起就好： ```c 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`： ```c 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](https://gist.github.com/jserv/2133fb04f30b1a08c306643521b096d3)，編譯方式: (部分遮蔽) ```shell $ gcc -O2 -Wall -Wextra -fPIC -I . -c alloc.c $ gcc -shared -o libmy_alloc.so alloc.o ``` 測試方式: ```shell LD_PRELOAD=./libmy_alloc.so ps aux ``` 關於此處 `LD_PRELOAD`，可對照看〈[你所不知道的 C 語言：動態連結器篇](https://hackmd.io/@sysprog/c-dynamic-linkage)〉。 請補完程式碼，使上述記憶體配置器得以正確運作。作答規範: * `IIII` 和 `JJJJ` 是表示式，皆不包含小括號 * `KKKK` 和 `LLLL` 是表示式，需要呼叫 POSIX Thread 規範的函式 :::success 延伸問題: 1. 解釋程式碼運作原理，說明如何搭配紅黑樹來實作 best-fit 策略 2. 以[第 3 週測驗](https://hackmd.io/@sysprog/linux2023-quiz3)和[第 4 週測驗](https://hackmd.io/@sysprog/linux2023-quiz4)題目所及、調整過的紅黑樹程式碼，重寫上述程式碼，使其得以用低的記憶體開銷和處理更大的記憶體範圍 3. 用 [mmap](https://man7.org/linux/man-pages/man2/mmap.2.html) 系統呼叫替換 sbrk 4. 研讀〈[針對多執行緒環境設計的 Memory allocator](https://hackmd.io/@ljP_AG30SzmQE5qO-cjcpQ/HkICAjeJg)〉和過往課程學員針對 [mimalloc](https://github.com/microsoft/mimalloc) 做的改進，探討 Linux 核心可用於改進記憶體配置效率的機制 > mimalloc 報告: [2021 年](https://hackmd.io/@hankluo6/mimalloc) 和 [2022 年](https://hackmd.io/@hankluo6/allocator) :::