---
tags: linux kernel class
---
# 2023q1 Homework6 (quiz5)
contributed by < `willwillhi1` >
### 測驗二
:::warning
逐行解釋程式碼之前，應先探討在記憶體配置器中，使用紅黑樹來處理 free list 的考慮因素。
:notes: jserv
:::
#### free list 的理解
先從最基本的 `allocator` 講起，可以分為:
* `explicit allocator`: 會要求使用者自行釋放記憶體，例如: C 語言的 `malloc` 和 `free`。
* `implicit allocator`: 又可以稱為 `garbage collector` ，`allocator` 會自行檢查哪個記憶體空間不再使用然後釋放那個空間。
接下來列出一個 `allocator` 的要求和目標:
* Handling arbitrary request sequences: 可以處理任意序列的分配請求和釋放，不過前提是每一個釋放都必須要先有配置請求，ex: `free` 前要有對應的 `malloc`。
* Making immediate responses to requests: `allocator` 要馬上回應每個呼叫。
* Using only the heap: 只能使用 `heap` 的空間。
* Aligning blocks (alignment requirement): 記憶體位址需要對齊，讓該空間可以保存任何資料型態。
* Not modifying allocated blocks: 不得修改已分配的記憶體區塊。
接下來是 `allocator` 在實作時要考慮到的要素:
* Free block organization: 如何管理 `free block`。
* Placement: 如何選擇合適的 `free block` 來放置新分配的 `block`。
* Splitting: 在 `free block` 配置後，如何處理剩餘(多出來)的空間。
* Coalescing: 如何處理一個剛被釋放的 `block`。
最基本的 `allocator` 的實作是 `Implicit Free Lists`。
每個 `block` 都會有 `header` 來表示 `payload` 大小以及現在這格區塊的狀態(`free` 或 `allocted`)，要注意的是如果位址是對齊 `8 bytes` 也就是末三位是 `0`，那就可以用最後一位來表示 `free` or `allocated`，與紅黑樹的親代節點同一個概念。
`payload` 表示資料實際會儲存的地方。
`padding` 是可能有或沒有的，用來處理 `external fragmentation` 或滿足 `alignment requirement`。
`Implicit Free Lists` 的優點就是實作簡單，但是缺點就是任何的操作(例如: `free list` 的搜尋, `block` 的合併等)基本上都是 $O(N)$，`N` 代表所有的 `free & allocated blocks` 總數。
Explicit Free Lists
`Explicit Free Lists` 可以說是 `Implicit Free Lists` 的優化，從原本的 `singly linked list` 變為 `doubly linked list`。
結構變為當 `block` 是 `free` 時會有 `pred` 和 `succ` 分別指向前、後 `block`。
藉由 `doubly linked list` 只存 `free block` 的機制，就可以把尋找的時間複雜度由 O(`alloated` 和 `free block` 的總數) 降到 O(`free block` 的總數)。
Segregated Free Lists
多個不同大小的 `Free Lists` 組合再一起就是 `Segregated Free Lists`。
比如根據 2 的冪來分可以分為:
```
{1}, {2}, {3, 4}, {5–8}, ... , {1,025–2,048}, {2,049–4,096}, {4,097–∞}
```
每個大小 (`size class`) 就是一個 `free List`，然後按照順序排列。
這個實作可以分為兩個模式:
Simple Segregated Storage
簡單來說就是不分割、不合併，每個 `blokc` 的大小就是 `size class` 中最大元素的大小，例如: `size class` 為 17~32 的 `block` 的大小都會固定是 32。
而且因為不分割也不合併，所以分配和釋放都可以在常數時間內完成，也就是從 `free list` 的 `head` 開始刪除和插入，因此 `free list` 可以是單向鏈結串列，從而節省記憶體的開銷。
但是不分割也不合併也造成了一個明顯的缺點，那就是 `internal and external fragmentation`。
Segregated Fits
與 `Simple Segregated Storage` 最大的不同在於每當找到了合適的 `free list` 後會依情況來切割這個 `block` 藉此避免 `internal fragmentation`，那如果沒有找到合適的 `block`，就從 `heap` 拿。
另外在釋放一個 `block` 的時候會與前後的 `free block` 合併。
在這次的測驗題中可以發現是使用紅黑樹來實作 `free list` 並且是 `Segregated Fits` 的模式。這種實作方法不僅可以將搜尋的時間複雜度控制在 $O(logN)$ 內 (N 代表 `free block` 數)，而且對這個紅黑樹執行 `first fit` 也相當於整個 `heap` 的 `best fit`。
#### 程式理解
先定義紅黑樹節點顏色，黑色是 `0`, 紅色是 `1`
```c
typedef enum rbcolor { BLACK = 0, RED = 1 } rbcolor_t;
```
結構體 `metadata_t` 放在每塊記憶體的前面，`size` 用來表示 `metameta_t` 加上其管理的 `memory block` 大小，`free` 表示這塊記憶體是否已經被分配，`next`, `prev` 則分別連接到下、上一塊 `metameta_t`。
```c
typedef struct metadata {
size_t size;
size_t free;
struct metadata *next, *prev;
} metadata_t;
```
接下來定義紅黑樹節點:
* `size`: 節點大小
* `free`: 表示節點是否被釋放(用 `YFREE`, `NFREE` 表示)
* `next`, `prev`: 用於連接相鄰節點的 `metadata_t`? (程式中都沒用到，初始化為 `NULL`)
* `key`: 表示該節點所存放的每個記憶體 (`metadata_t` + `memory block`) 的大小
* `tab_values`: 指向 `metadata_t` 結構體的指標陣列
* `size_tab`: `tab_values` 陣列長度
* `n_active`: 可用的記憶體區塊的數量
```c
typedef size_t t_key;
typedef metadata_t t_value;
typedef struct rbnode {
size_t size;
size_t free;
metadata_t *next, *prev;
t_key key;
t_value **tab_values;
size_t size_tab;
size_t n_active;
rbcolor_t color;
struct rbnode *left, *right;
} rbnode_t;
```
最後是 `malloc_t` 結構體:
* `root_rbtree`: 表示整棵樹的 `root`
* `last_node`: 代表最後一個 `metadata_t` 指標
* `end_in_page`: 所有使用到的記憶體的尾端位址(不包含 `page_remaining` 的記憶體)
* `first_block`: 所有請求記憶體的起始位置
* `page_size`: `page_size` 大小
* `mutex`: 用於多執行緒環境的鎖
* `page_remaining`: 表示沒有被使用但也沒有被納入紅黑樹的空間，該空間保留給 `get_heap` 函式使用，放在所有記憶體的最尾端。
```c
typedef struct {
rbnode_t *root_rbtree;
metadata_t *last_node;
void *end_in_page;
void *first_block;
int page_size;
pthread_mutex_t mutex;
size_t page_remaining;
} malloc_t;
```
先解釋 `malloc` 的運作:
考慮到多執行緒環境，所以在進行操作前後要上鎖、解鎖。
```c
pthread_mutex_lock(&g_info.mutex);
/* operation */
pthread_mutex_unlock(&g_info.mutex);
```
然後判斷請求的空間大小是否小於 `SIZE_DEFAULT_BLOCK`，是則把它改為 `SIZE_DEFAULT_BLOCK`。
```c
if (size < SIZE_DEFAULT_BLOCK)
size = SIZE_DEFAULT_BLOCK;
```
然後把它對齊 `16 B` (64 位元系統) 後再加上 `metadata_t` 結構體的大小。
```c
#define ALIGN_BYTES(x) ((((x - 1) >> 4) << 4) + 16)
size = ALIGN_BYTES(size) + META_SIZE;
```
接著如果 `g_info.page_size` 還沒有值，就 assign 為 `page size`。
```c
if (!g_info.page_size)
g_info.page_size = getpagesize();
```
最後從紅黑樹找出最適合的記憶體區塊，如果沒有就直接從 `heap` 拿。
```c
metadata_t *tmp;
void *ptr;
if ((tmp = search_freed_block(g_info.root_rbtree, size)))
ptr = split_block(tmp, size);
else
ptr = get_heap(size);
```
`search_freed_block` 會先通過 `find_best` 函式從紅黑樹找出大小最合適的點，也就是 `best fit` 策略。
```c
/* best fit */
while (node) {
if (node->key >= size) {
tmp = node;
node = node->left;
} else
node = node->right;
}
```
如果有找到 (`tmp` 不為 `NULL`) 就回傳該點所管理的 `metadata_t` 陣列中可以使用的 `metadata_t` (也就是不為 `NULL`)。
反之沒找到則回傳 `NULL`。
```c
if (tmp) {
size_t size_tab = tmp->size_tab;
metadata_t **tab = tmp->tab_values;
for (size_t i = 0; i < size_tab; i++) {
if (tab[i])
return tab[i];
}
}
```
回到 `malloc` 的程式中，
如果有找到就會執行 `split_block`。
`split_block` 會通過 `remove_from_freed_list` 把指定的 `metadata_t` 從紅黑樹中移除。
這邊 `remove_from_freed_list` 傳入的第一個參數是 `root`，
```c
g_info.root_rbtree = remove_from_freed_list(g_info.root_rbtree, node);
```
不過去看 `remove_from_freed_list` 發現用 `get_key` 來找到紅黑樹節點，等同多走訪一次樹，所以我感覺應該可以傳入之前透過 `search_freed_block` 找到的節點位址來節省時間。
`remove_from_freed_list` 找到節點後會把 `n_active` 減一，然後如果 `n_active` 等於零就通過 `remove_k` 函式把該節點從紅黑樹中移除。
回到 `split_block` 中，移除完後
會先做兩個判斷，但是還不是很懂會何為甚麼要這樣判斷?
* `node->size > size + sizeof(size_t)`
* `node->size - size > sizeof(rbnode_t) + SIZE_DEFAULT_BLOCK`
如果成立就會把 `node` 做分割然後把新的點 `new` 插入樹中。
```c
metadata_t *new = (void *) node + size;
new->size = node->size - size;
new->free = YFREE;
new->prev = node;
new->next = node->next;
node->next = new;
node->size = size;
if (new->next)
new->next->prev = new;
g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, new);
```
回到 `malloc`，如果 `search_freed_block` 找不到適合的記憶體就要用 `get_heap` 從 `heap` 拿。
`get_heap` 會先判斷目前的 `remain page` 夠不夠，如果不夠會透過 `get_new_page` 從 `heap` 取記憶體。
```c
if (g_info.page_remaining < size) {
if ((tmp = get_new_page(size)) == (size_t) -1)
return NULL;
g_info.page_remaining += tmp;
}
```
接下來 `get_new_page` 會先把請求的記憶體大小 `size` 轉為以 `g_info.page_size` 為單位。
```c
size_t pages = ((size / g_info.page_size) + 1) * g_info.page_size;
```
`get_new_page` 如果是第一次就會用 `sbrk(0)` (previous program break) 初始化 `g_info.first_block` 和 `g_info.end_in_page`。
```c
if (!g_info.end_in_page) {
if ((g_info.end_in_page = sbrk(0)) == (void *) -1)
return (size_t) -1;
g_info.first_block = g_info.end_in_page;
}
```
然後將 `program break` 往後移 `pages` 個 `bytes` 。
```c
if (sbrk(pages) == (void *) -1) {
errno = ENOMEM;
return (size_t) -1;
}
```
最後 `get_in_page` 會回傳 `pages` 給 `get_heap` 中的 `tmp`。
回到 `get_heap`，執行完 `get_new_page` 後會把取得的空間的大小加到 `g_info.page_remaining` 中，然後再扣掉原本要分配出去的空間大小。
```c
g_info.page_remaining += tmp;
g_info.page_remaining -= size;
```
`get_heap` 會回傳 `get_in_page(size)`，
`get_in_page` 會初始化這塊記憶體的 `metadata_t`，並更新 `g_info.last_node` 和 `g_info.end_in_page`。
```c
metadata_t *new = g_info.end_in_page;
new->size = size;
new->free = NFREE;
new->next = NULL;
new->prev = g_info.last_node;
if (g_info.last_node)
g_info.last_node->next = new;
g_info.last_node = new;
g_info.end_in_page = (void *) new + size;
return new;
```
最後終於回到 `malloc` 的最後
把鎖解開後回傳取得的 `memory block` 的起始位置。
```c
#define GET_PAYLOAD(x) ((void *) ((size_t) x + META_SIZE))
pthread_mutex_unlock(&g_info.mutex);
return ptr ? (GET_PAYLOAD(ptr)) : NULL;
```
接下來是 `free` 的部分
首先要做的就是上鎖，然後取得該 `memory block` 的 `metadata_t` 位址。
```c
#define GET_NODE(x) ((void *) ((size_t) x - META_SIZE))
pthread_mutex_lock(&g_info.mutex);
metadata_t *node = GET_NODE(ptr);
```
之後判斷完 `invalid_pointer` 和 `double_free` 後會做 `try_fusion`。
`try_fusion` 會去檢查該 `metadata_t` 前後的節點狀態是否為 `free`，如果是則會先用 `remove_from_freed_list` 把該 `metadata_t` 的前或後從紅黑樹移除，接著再用 `fusion` 把第二個空間合併到第一個記憶體的 `metadata_t` 中。
```c
while (IS_FREE(node->prev)) {
g_info.root_rbtree =
remove_from_freed_list(g_info.root_rbtree, node->prev);
node = fusion(node->prev, node);
}
while (IS_FREE(node->next)) {
g_info.root_rbtree =
remove_from_freed_list(g_info.root_rbtree, node->next);
node = fusion(node, node->next);
}
```
回到 `free`，合併完接下來會有兩個情況，第一個情況是如果這個釋放的節點是在最尾端就直接用 `change_break` 把 `program break` 往前(回)移，要移動的空間大小為 `g_info.page_remaining += node->size`，另外再移動前要先用除法無條件捨去取 `page count`，避免以 `page` 為單位釋放記憶體時釋放到正在使用的空間。
```c
g_info.page_remaining += node->size;
pages_to_remove = g_info.page_remaining / g_info.page_size;
/* FIXME: sbrk is deprecated */
brk((sbrk(0) - (pages_to_remove * g_info.page_size)));
```
最後更新 `page_remaining` 即可。
```c
g_info.page_remaining =
g_info.page_remaining - (pages_to_remove * g_info.page_size);
```
回到 `free`，合併完接下來的第二個情況就是釋放的節點不在最尾端，那就直接插入紅黑樹即可。
```c
g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, node);
```
Sign in with Wallet
Connect another wallet