---
title: 2023q1 Homework6 (quiz5)
tags: Linux核心設計
---
# [2023q1 Homework6 (quiz5)](https://hackmd.io/@sysprog/linux2023-quiz5)
## [測驗一](https://hackmd.io/@sysprog/linux2023-quiz5#%E6%B8%AC%E9%A9%97-1)
### 程式碼原理
#### Basic data structure
```c
typedef struct block {
int size; /**< Size of the data payload */
struct block *prev, *next; /**< Pointer to the previous/next block */
} block_t;
```
`block` 為每塊可使用區塊的 metadata ，其中紀錄每個區塊的大小及前一個與後一個區塊的 link。
#### pool_init
首先會檢查要配置的記憶體位址是否合法，再去檢查大小是否能至少容納一個區塊所需的 metadata 大小，一個 block 包含 `size, *prev, *next` ，所以至少要 3 個 word 大小，所以 `header_size` 為 `word_size * 3`，`current` 去紀錄此可用區塊的位址。
#### round_up
```c
static inline int round_up(const int *x)
{
return ((*x + 7) >> log2_word_size) << log2_word_size;
}
```
`round_up` 是為了使宣告的大小能對齊記憶體，因為 `x` 至少為 1 ，所以當 `word_size == 8` 時，因為要對齊 8 bytes，所以最右邊 3 bits 要清除為 0 ，所以要 `*x + 7`，接著右移 3 bits 後，再左移 3 bits ，就能對齊 8 bytes。但這裡適用於 `word_size == 8` 時，所以當`word_size == 4` ，並不適用，所以改成：
```c
static inline int round_up(const int *x)
{
return ((*x + word_size - 1) >> log2_word_size) << log2_word_size;
}
```
則當`word_size == 4 or 8` 時，都能對齊。
#### pool_malloc
用 `pool_malloc` 來配置在 memory pool 中的可用區塊，先檢查要配置的記憶體大小是否 > 0，再將要配置的大小對齊 `word_size` ，最後檢查 `pool_free_space` 須配置的大小是否足夠，然後用 `ret` 去紀錄要使用的區塊，由 `get_loc_to_place` 去尋找可使用的區塊。
```c
void *ret = get_loc_to_place(current, _size);
```
因為採用 first-fit ，所以當有足夠大小的區塊時就直接配置，否則就往下尋找。這裡有個問題是 `get_loc_to_place` 傳入的參數名稱與全域變數 `current` 是一樣的，會導致自己判斷時可能會錯誤。
```c
static inline void *get_loc_to_place(void *current, int size)
{
block_t *parse = current;
if (parse->size >= (size + header_size))
return current;
...
}
```
因為將 memory pool 的區塊配置，所以更新 free space 的值，先更新 `current` 的位址，再更新 `current->size` 的值，為目前 free space 大小 - 以配置的空間大小 - 配置出去的區塊的 metadata 大小(`size`)。
```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;
```
最後將 free block 的 `prev, next` 的 link 接上。
```c
current->prev = prev_pt, current->next = next_pt;
/* 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;
}
```
#### pool_free
首先求出要釋放的 block 的位址，並將它的大小更新到 free space 中。
```c
/* Get block info */
void *block_pt = (char *) addr - word_size;
block_t *block = block_pt;
/* Update pool arena statistics */
pool_free_space += block->size;
```
用 `get_loc_to_free` 去找到可以連接的 free block。
```c
void *free_pt = get_loc_to_free(block_pt);
```
再來會檢查 released block 的位址是否跟 free block 相鄰，會有兩種情況，一是 free block 在 released block 前，二是 free block 在 released block 後，再進行合併。
```ㄏ
/* 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;
...
}
...
}
```
最後合併完的 free block 可能也會跟其他 free block 相鄰，所以需要再次合併，分成兩種情況，分別是存在相鄰的 free block 在前或在後。
```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;
}
}
...
```
### 答案
:::success
* `AAAA = header_size`
* `BBBB = log2_word_size`
* `CCCC = log2_word_size`
* `DDDD = header_size`
* `EEEE = _size`
* `FFFF = word_size`
* `GGGG = word_size`
* `HHHH = word_size`
:::
---
## [測驗二](https://hackmd.io/@sysprog/linux2023-quiz5#%E6%B8%AC%E9%A9%97-2)
### [alloc.c](https://gist.github.com/jserv/2133fb04f30b1a08c306643521b096d3) 程式碼原理
#### split_block
主要將 `node` 從 freed list 移出，並用 `new` 去更新大小跟節點關係，最後更新 rb_tree 的資訊。
```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; //IIII
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;
}
```
#### fusion
這裡主要是做將兩塊 free block 合併，首先將兩塊空間大小加總，再將 freed list 的 link 連接，若是合併後的空間為最後一塊，則會去更新最後一個節點的資訊 `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; //JJJJ
return first;
}
```
#### malloc
因為考慮到多執行序的問題，所以在配置 block 時，使用 mutex lock，防止可能重複配置空間的問題，首先檢查要配置的大小是否不足 4 bytes，再將 `size` 加上所需的 metadata 大小，最後去 freed list 尋找合適的空間，若有找到，則回傳位址，若無，則回傳 `NULL` 。
```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;
if (!g_info.page_size)
g_info.page_size = getpagesize();
if ((tmp = search_freed_block(g_info.root_rbtree, size)))
ptr = split_block(tmp, size);
else
ptr = get_heap(size);
pthread_mutex_unlock(&g_info.mutex);
return ptr ? (GET_PAYLOAD(ptr)) : NULL;
}
```
#### free
首先判斷要釋放的指標是否合法，再去判斷是否為 double free ，最後將這塊空間加入到 freed list 中。
```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);
node = try_fusion(node);
if (!node->next)
change_break(node);
else
g_info.root_rbtree = insert_in_freed_list(g_info.root_rbtree, node);
pthread_mutex_unlock(&g_info.mutex);
}
```
### 答案
:::success
* `IIII = node->size - size`
* `JJJJ = g_info.last_node = first`
* `KKKK = pthread_mutex_lock(&g_info.mutex);`
* `LLLL = pthread_mutex_unlock(&g_info.mutex);`
:::
Sign in with Wallet
Connect another wallet