# 2023q1 Homework5 (quiz5)
contributed by < `Korin777` >

> [測驗題目](https://hackmd.io/@sysprog/linux2023-quiz5)

## 測驗一

### 運作原理
#### `pool_malloc`
透過 `get_loc_to_place` 從 memory pool 的 free block 中配置記憶體給使用者
1. 配置記憶體的大小會根據 32 bits 或 64 bits 進行 round up
2. free block 大小要大於等於所需的 `size + header_size` 確保釋放時有足夠的空間存放 metadata
3. 因為配置的記憶體空間是從 free block 的頭開始，所以要更新 free block 的位置並重新儲存 metadata

#### `pool_free`
釋放配置的記憶體
1. 透過 `get_loc_to_free` 找出可能可以 merge 的 free block，因為 free block 的 list 根據 address 從低到高串聯，所以我們只要根據目前釋放的記憶體位置往前或往後找即可
2. 查看目前釋放的 block 是否跟上一步找到的 free block 相鄰，是的話將兩者合併
3. 合併後原本與 free block 相鄰的 free block 也可能可以合併，因此要在次檢查

### 改進
測試程式時可以發現如果將 memory pool 的記憶體配置完後，在去釋放這些記憶體，然後再去配置記憶體時會無法獲得可用的記憶體空間，以下為實作上可改進的地方

#### `pool_malloc`
* 配置空間時並未記錄配置空間大小，且沒有減少 `pool_free_space`
* 配置記憶體時，free block 不一定為 `current`
* In-use block 只配置了 `_size + word_size` 的空間，我認為應該要配置`_size + header_size`的空間，因為當這個 block 釋放為 free block 時，假設我們 `_size` 只配置了 8 bytes ， In-use block 就只有 16 bytes 而放不下 metadata ， 這時 `prev` block pointer 會動到別的 block 的記憶體

#### `pool_free`
* 釋放記憶體時，若沒有進行 merge ，這個 free block 不會跟其他 free block 接在一起
* free block 合併時未檢查 `next` 或 `prev` 是否為 NULL

#### `get_loc_to_free`
* `tmp_pt` 應為 `current` 的值而非地址，若是後者(即 `&current`) 此時 `tmp_block->prev` 會相當於 `((block_t *)&current)->prev` 但我們應該是要 `current->prev`

#### `get_loc_to_place`
* 原本的實作並不會把整個 free_block 配置出去，但只要確保不只存在一個 `free_block` ，我們就能把整個 `free_block` 的記憶體配置出去

---

## 測驗二
### 結構體
1. `metadata_t` : 紀錄配置的 memroy block 的資訊
* `size` : 配置的記憶體大小
* `free` : memroy block 是否被釋放，可用來偵測 double free
* `*next`、`*prev` : 連接前後相鄰的 memory block
2. `rbnode_t` : 用來放被釋放的 memroy block ， 相同大小的 memory block 會放在同一個 node
* `size`、`free`、`*next`、`*prev` : node 的 metadata
* `key` : 放在這個 node 的 memory block 大小
* `**tab_values` : 放 memory block ，預設可以放 256 個，透過 `resize_tab_values` 增加
* `size_tab` : memory block 可放的總數
* `n_active` : 已放的 memory block 數量
* `color` : node 的顏色
* `*left`、`*right` : node 的 child

3. `malloc_t` : 可用的記憶體空間
* `*root_rbtree` : 用來放被釋放 memroy block 的紅黑樹根節點
* `last_node` : 最新被配置的 memory block
* `*end_in_page` : 目前配置到的記憶體地址，也就是下一次配置記憶體會從這裡開始
* `*first_block` : 最一開始可以使用到的記憶體地址，也就是可用的記憶體最低地址
* `page_size` : 一個 page 的大小，在我的電腦上為 4096 bytes
* `mutex` : 確保只有一個執行續能配置及釋放記憶體的 lock
* `page_remaining` : 尚未被配置的記憶體空間大小

### `free`
* 首先會去檢查記憶體是否在以配置的記憶體範圍內及 `metadata_t->free` 來看是否合法，再來會用 `metadata_t->free` 偵測 double free
* 接下來 `try_fusion` 藉由 `metadata_t->prev`、`metadata_t->next`、`metadata_t->free` 來合併相鄰的 free block ，被合併的 block 會從該 `rbnode_t` 中移除，若移除後 `rbnode_t` 沒任何 memory block 就將該 `rbnode_t` 從紅黑樹中移除
* 最後會去釋放記憶體，分為兩種情況 :
1. 釋放的 memory block 為最新配置的 memory block : 這時可以直接透過 `change_break` 來更新 `malloc_t` ， 若 `malloc_t->page_remaining` 大於一個 page 就可以透過 `brk` 來真正釋放我們用 `sbrk` 配置的記憶體
2. 其他情況 : 此時就要將 memory block 放到紅黑樹的 `rbnode_t` 中 ， 若不存在該 memory block 大小 的 `rbnode_t`， 就插入新的 `rbnode_t` 到紅黑樹中， `malloc` 會透過紅黑樹來使用已配置但現為 free block 的記憶體

### `malloc`
* 首先會透過 `ALIGN_BYTES` 讓配置的記憶體位置以 16-bytes 對齊(64-bits 系統下)
* 接著透過 `search_freed_block` 去紅黑數找已配置但現為 free block 的記憶體，來重用記憶體空間，因為紅黑數為二元搜尋樹，可以發現 `find_best` 透過這個性質來找出不小於所需 size 的 `rbnode_t` 來達到 best-fit 的策略
* 若有找到 `rbnode_t` ，就透過 `split_block` 就將其中一個 free block 移除，因為 free block 空間可能遠高於所需的空間，所以當 free block 剩餘的空間扣掉所需的空間後，仍能放 `maclloc` 所配置的最小記憶體 `SIZE_DEFAULT_BLOCK + META_SIZE` ，就將它分割成兩塊，一塊給使用者使用 (in-use block) 而另一塊會重新插入紅黑樹中 (free block)
::: warning
在程式碼中 split_block 要分割的判斷是 node->size > size + sizeof(size_t) && node->size - size > sizeof(rbnode_t) + SIZE_DEFAULT_BLOCK 跟我的想法不同，我認為剩餘的空間扣掉所需的空間後只要不小於最小能配置的記憶體空間，分割出來的 free block 就有機會被重用
:::
* 若沒有找到 `rbnode_t` ， 就透過 `get_heap` 來配置記憶體空間
* 若可用的記憶體空間不足時就透過 `sbrk` 來真正配置不小於 size 的 n 倍 pagesize 空間
* 若可用的空間充足就從目前配置到的記憶體地址 `end_in_page` 配置新的 in-use block 並與前一個 block 相連，在更新 `malloc_t`
* 最後透過 `GET_PAYLOAD` 回傳使用者實際能使用的記憶體地址