# 2023q1 Homework6 (quiz5)
contributed by < `ItisCaleb` >
## 測驗 `1`
題目的 memory pool 可以運用的空間是使用者自行先分配出來，再使用 `pool_init` 並傳入 `size` 來讓程式可以運用
在 memory pool 中，可以使用的空間會有個 header，用來紀錄上/下一個可以使用的空間及大小
```c
typedef struct block {
int size; /**< Size of the data payload */
struct block *prev, *next; /**< Pointer to the previous/next block */
} block_t;
```
而使用中的空間則只會有一個 `size` 來紀錄 `payload` 的大小。
```graphviz
digraph {
node [shape=plaintext, fontcolor=black, fontsize=16];
"Free Block" -> "In-use Block" [color=white];
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
block1 [label="size|next|prev|..."];
block2 [label="size|payload"];
{ rank=same; "Free Block"; block1 }
{ rank=same; "In-use Block"; block2 }
}
```
全域變數的 `current` 指向一個可以使用的空間
### pool_malloc
會先把要的 `size` 變成 4/8 byte的倍數，如果 memory pool 剩下的空間塞不下 `_size` 跟 header 就直接回傳
```c
void *pool_malloc(int size)
{
if (!size)
return NULL;
/* Round up the size up to the arch width. Ensure the size is at minimum a
* register size and a multiple of that register. So if use 64 bits arch, a
* 4 bytes allocation is round up to 8 bytes, and 28 bytes is round up to
* 32 bytes.
*/
int _size = round_up(&size);
/* Return NULL if failed to allocate a buffer */
if (pool_free_space <= (_size + header_size))
return NULL;
```
接下來則是用 `get_loc_to_place` 並使用 `current` 去尋找符合 `_size` 的空間
> `ret` 應該設為 `ret + word_size` 而非 `current + word_size`，同時應該放到最後，這樣才方便去更新他的 `size`
```c
void *ret = get_loc_to_place(current, _size);
if (!ret)
return NULL;
/* payload's address the application can use */
//ret = (char *) ret + word_size;
```
`get_loc_to_place` 的行為很簡單
就只是透過 `current` 去往前或往後搜尋大於等於 `size` 的 free block
> 第二段的 `parse = ((block_t *) current)->prev;` 應改成 `parse = ((block_t *) current)->next;`
```c
/* Search for a free space to place a new block */
static inline void *get_loc_to_place(void *current, int size)
{
block_t *parse = current;
if (parse->size >= (size + header_size))
return current;
/* parse the prev blocks to find a place */
for (parse = ((block_t *) current)->prev; parse; parse = parse->prev) {
if (parse->size >= (size + header_size))
return parse;
}
/* parse the next blocks to find a place */
for (parse = ((block_t *) current)->next; parse; parse = parse->next) {
if (parse->size >= (size + header_size))
return parse;
}
/* No space found, stop the allocation */
return NULL;
}
```
最後則是更新 `current` ，把原本的 `prev` 跟 `next` 接上去
```c
/* Store current's info before moving its head */
void *next_pt = current->next, *prev_pt = current->prev;
int new_size = current->size - word_size - _size;
/* Adjust free space of current block and update its meta-data */
void *new_space = (char *) current + word_size + _size;
current = new_space;
if (new_size < 0) {
current->size = 0;
return NULL;
}
current->size = new_size;
current->prev = prev_pt, current->next = next_pt;
```
如果 `current` 的 `prev` 跟 `next` 不為 NULL
則也同樣把他們接上 `current`
```c
/* Update previous block to link current */
if (current->prev) {
tmp_block = prev_pt;
tmp_block->next = current;
}
/* Update next block to link current, only if exists */
if (current->next) {
tmp_block = next_pt;
tmp_block->prev = current;
}
```
在回傳 `ret` 之前，應該要先更新 `pool_free_space` 以及他本身的 `size`
```c
pool_free_space -= _size;
/* payload's address the application can use */
((block_t *) ret)->size = _size;
return (char *) ret + word_size;;
```
## pool_free
在 free 之前會先獲取 block 的 size 然後加到 `pool_free_space` 裡
```c
void pool_free(void *addr)
{
/* Get block info */
void *block_pt = (char *) addr - word_size; //HHHH
block_t *block = block_pt;
/* Update pool arena statistics */
pool_free_space += block->size;
```
接著是用 `get_loc_to_free` 來找到最近的 free block
為了等下可以 merge
```c
void *free_pt = get_loc_to_free(block_pt);
block_t *free_block = (block_t *) free_pt;
```
在 merge 的時候會有兩種情況
分別是 free block 在要釋放的 block 前面及後面
```graphviz
digraph {
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
block1 [label="free block|block"];
}
```
```graphviz
digraph {
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
block1 [label="block|free block"];
}
```
在檢查 free block 是否跟要釋放的 block 相鄰後
如果是後者的情況則要將 free block 的 header 移到要釋放的 block 前面，並且更新 `size` 及連結的區塊
前者的情況則只要更新 free block 的 `size` 就好
```c
/* Check the block can be merged with the current free space selected */
if ((uintptr_t) block_pt < (uintptr_t) free_pt) {
/* If block space matches free space start address, merge */
region = (char *) block_pt + block->size + word_size;
if (region == free_pt) {
block->prev = free_block->prev, block->next = free_block->next;
block->size += free_block->size + header_size;
pool_free_space += word_size;
/* If a next block exists, connect it */
if (block->next) {
tmp_block = block->next;
tmp_block->prev = block_pt;
}
/* If a previsou block exists, connect it */
if (block->prev) {
tmp_block = block->prev;
tmp_block->next = block_pt;
}
}
} else {
/* if free space range macthes the block start address, merge in this
* case, the free space becomes the block to release
*/
region = (char *) free_pt + free_block->size + header_size;
if (region == block_pt) {
free_block->size += block->size + word_size;
block_pt = free_pt;
block = block_pt;
pool_free_space += word_size;
}
}
```
最後如果 merge 之後前方或後方還有 free block 則再一次去做 merge
```c
/* Try to merge with next block if exists */
if (block->next) {
/* if next block is contiguous the one to free, merge them */
region = (char *) block_pt + block->size + word_size;
if (region == block->next) {
/* extend block size with next size */
tmp_block = block->next;
block->size += tmp_block->size + word_size;
/* link next->next block with current block */
tmp_block = tmp_block->next;
tmp_block->prev = block_pt;
/* Update pool's statistics */
pool_free_space += word_size;
}
}
/* Try to merge with previous block if exists */
if (block->prev) {
/* if previous block is contiguous the one to free, merge them */
tmp_block = block->prev;
region = (char *) block->prev + tmp_block->size + header_size;
if (region == block_pt) {
/* Update previous block by extending its size with block */
tmp_block->size += word_size + block->size;
/* Link block - 1 and block + 1 together */
tmp_block->next = block->next;
/* Current block's prev becomes the new current block */
block = block->prev;
/* (block + 1)'s prev is now linked to orignal (block - 1) */
tmp_block = block->next;
tmp_block->prev = block;
/* Update pool's statistics */
pool_free_space += word_size;
}
}
```
整體的行為會像是下面這樣子
```graphviz
digraph {
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
block [label="free block|block|free block"];
}
```
```graphviz
digraph {
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
block [label="free block|free block"];
}
```
```graphviz
digraph {
node [shape=record, fontcolor=black, fontsize=14, width=4.75, fixedsize=true];
block [label="free block"];
}
```
---
## 測驗 `2`
這個測驗裡的記憶體配置是搭配紅黑樹來實作的
演算法大致上的概念是在把空間 free 之後，不會直接將空間還給 kernel，而是會作為節點放到紅黑樹裡，待之後可以直接取用
這邊的紅黑樹是用 size 來當作 key ，同時如果有多個區塊是同一個 size 的話，則都會放入節點的 `tab_values` 裡
```c
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;
```
在 metadata 中除了 `size` 還會記載著 `next` 跟 `prev`，也就是相鄰的區塊
是為了之後在 free 的時候看能不能去合併
```c
typedef struct metadata {
size_t size;
size_t free;
struct metadata *next, *prev;
} metadata_t;
```
而為了可以在多執行緒的狀況下執行，在每個操作裡都會有 `mutex_lock` 及 `mutex_unlock`
### malloc
一開始會先將要的 `size` 做記憶體對齊並且加上 metadata 的大小
```c
void *malloc(size_t size)
{
metadata_t *tmp;
void *ptr;
pthread_mutex_lock(&g_info.mutex);
if (size < SIZE_DEFAULT_BLOCK)
size = SIZE_DEFAULT_BLOCK;
size = ALIGN_BYTES(size) + META_SIZE;
```
接著就是先去紅黑樹裡找到符合 `size` 的記憶體區塊
如果找到了還會透過 `split_block` 去分割區塊，然後把多餘的區塊重新插入到紅黑樹中
這樣子做就一定會保證是 best-fit
而如果沒有符合 `size` 的區塊，則透過 `get_heap` 來獲得更多記憶體空間
```c
if ((tmp = search_freed_block(g_info.root_rbtree, size)))
ptr = split_block(tmp, size);
else
ptr = get_heap(size);
```
最後回傳 payload 的地址
```c
return ptr ? (GET_PAYLOAD(ptr)) : NULL;
```
`split_block` 會將找到的區塊分割成 `size` 的大小
並且將這兩個區塊連結在一起
然後把分割完剩下來的區塊放回紅黑樹裡
```c
static void *split_block(metadata_t *node, size_t size)
{
g_info.root_rbtree = remove_from_freed_list(g_info.root_rbtree, node);
if (node->size > size + sizeof(size_t) &&
node->size - size > sizeof(rbnode_t) + SIZE_DEFAULT_BLOCK) {
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);
}
return node;
}
```
### free
首先會先通過檢查位置及 magic number 來確認 `ptr` 是不是有效的記憶體位址
並且也會檢查是否 free 多次同一個位址
```c
void free(void *ptr)
{
if (!ptr)
return;
pthread_mutex_lock(&g_info.mutex);
metadata_t *node = GET_NODE(ptr);
if (ptr < g_info.first_block || ptr > g_info.end_in_page || !IS_VALID(node))
invalid_pointer(ptr);
if (node->free == YFREE)
double_free(ptr);
```
如果都沒問題則會嘗試會合併記憶體區塊
```c
node = try_fusion(node);
```
`try_fusion` 會利用 metadata 的 `next` 跟 `prev` 來讓相鄰的區塊合併
如果在合併之後 `next` 為 `NULL` 則表示現在的區塊是最後的區塊，把 `g_info.last_node` 設為現在的區塊
```c
static metadata_t *fusion(metadata_t *first, metadata_t *second)
{
first->size += second->size;
first->next = second->next;
if (first->next)
first->next->prev = first;
else
g_info.last_node = first;
return first;
}
static inline metadata_t *try_fusion(metadata_t *node)
{
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);
}
return node;
}
```
當合併完之後會判斷現在的區塊是否是最後的區塊
如果是的話就使用 `change_break` 來把區塊還回 kernel
否則就插入到紅黑樹裡來讓之後的 `malloc` 操作可以利用
```c
if (!node->next)
change_break(node);
else
g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, node);
```
`change_break` 會利用 `sbrk` 把剩下的區塊還回 kernel
```c
static inline void change_break(metadata_t *node)
{
size_t pages_to_remove;
if (node->prev) {
node->prev->next = NULL;
g_info.last_node = node->prev;
g_info.end_in_page = (void *) g_info.last_node + g_info.last_node->size;
} else {
g_info.end_in_page = g_info.last_node;
g_info.last_node = NULL;
}
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)));
g_info.page_remaining =
g_info.page_remaining - (pages_to_remove * g_info.page_size);
}
```
Sign in with Wallet
Connect another wallet