---
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)
:::
Sign in with Wallet
Connect another wallet