# 2023q1 Homework6 (quiz5)
contributed by < `terry23304` >
## 測驗 1
根據電腦結構設定 `word_size` ，`header_size = sizeof(block_t)` 更好理解
```c
/* Size of a memory element, 32 or 64 bits */
enum {
word_size = __SIZE_WIDTH__ / 8, /**< size of memory element */
#if __SIZE_WIDTH__ == 64
log2_word_size = 3,
#else
log2_word_size = 2,
#endif
// header_size = 3 * word_size, /**< size, previous/next block addresses */
header_size = sizeof(block_t), /**< size, previous/next block addresses */
};
```
- pool_init
檢查傳入的 address 是否合法與大小是否大於 `block_t` 的大小，若通過則用 `current->size` 紀錄可用空間， `current->size` 要減去儲存 `size` 的大小， `current->prev` 、 `current->next` 因為是指向 `NULL` 所以不占空間。
```c
pool_free_space = size - word_size;
current = (block_t *) addr;
current->size = pool_free_space;
current->prev = NULL, current->next = NULL;
```
- round_up
確保空間為 `word_size` 的倍數，原本的寫法在 32 位元時不成立
```c
static inline int round_up(const int *x)
{
// return ((*x + 7) >> log2_word_size) << log2_word_size;
return ((*x + (word_size - 1)) >> log2_word_size) << log2_word_size;
}
```
- get_loc_to_place
找到可以配置的空間
先確認 `current` size 夠不夠大，因為是 first-fit，找到就直接 retrun
```c
static inline void *get_loc_to_place(void *current, int size)
{
/* Search for a free space to place a new block */
block_t *parse = current;
if (parse->size >= (size + header_size))
return current;
```
往前找
```c
/* 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 = ((block_t *) current)->prev` ， 會重複檢查 `current->prev` 跟 `current` ，應為 `parse = ((block_t *) current)->next`
```c
// for (parse = ((block_t *) current)->prev; parse; parse = parse->next) {
for (parse = ((block_t *) current)->next; parse; parse = parse->next) {
if (parse->size >= (size + header_size))
return parse;
}
return NULL;
}
```
- pool_malloc
先把大小補到 `word_size` 的倍數後，找到可配置的空間，但得到可配置空間後卻使用 `current` 來配置
```c
int _size = round_up(&size);
/* Return NULL if failed to allocate a buffer */
if (pool_free_space <= (_size + header_size))
return NULL;
void *ret = get_loc_to_place(current, _size);
if (!ret)
return NULL;
/* payload's address the application can use */
ret = (char *) current + word_size;
void *next_pt = current->next, *prev_pt = current->prev;
int new_size = current->size - word_size - _size;
```
- pool_free
呼叫 `get_loc_to_free` 得到 free space，並檢查 block 能不能跟 free space 合併，再嘗試與前後的 block 合併
```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;
void *region;
void *free_pt = get_loc_to_free(block_pt);
block_t *free_block = (block_t *) free_pt;
```
修改 first-fit 成 best-fit
```c
static inline void *get_loc_to_place(void *current, int size) {
block_t *parse = current;
block_t *best_fit = NULL;
if (parse->size >= (size + header_size))
best_fit = parse;
for (parse = ((block_t *)current)->prev; parse; parse = parse->prev) {
if (parse->size >= (size + header_size) &&
(best_fit == NULL || parse->size < best_fit->size)) {
best_fit = parse;
}
}
for (parse = ((block_t *)current)->next; parse; parse = parse->next) {
if (parse->size >= (size + header_size) &&
(best_fit == NULL || parse->size < best_fit->size)) {
best_fit = parse;
}
}
/* No space found, stop the allocation */
return best_fit;
}
```
---
## 測驗 2
用 `rbnode` 儲存各個 block 的資訊
```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;
```
:::warning
TODO: 討論使用紅黑樹實作 free list 的好處和考量因素
:notes: jserv
:::
走訪紅黑樹找到最接近且大於 size 的 node
```c
static inline rbnode_t *find_best(rbnode_t *node, size_t size)
{
rbnode_t *tmp = NULL;
while (node) {
if (node->key >= size) {
tmp = node;
node = node->left;
} else
node = node->right;
}
return tmp;
}
```
把 `node` 從 `freed_list` 中刪除後，用 `new` 更新剩餘空間的大小，再插入 freed list
```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;
}
```
合併 `first` 、 `second`
```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;
}
```
free 時檢查前後是否為 freed 狀態，若則合併兩個 node
```c
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;
}
```
避免多個 thread 同時存取 memory block
```c
void *realloc(void *ptr, size_t size)
{
if (!ptr)
return malloc(size);
if (!size)
return free_realloc(ptr);
ptr = (void *) ptr - META_SIZE;
metadata_t *tmp = (metadata_t *) ptr;
metadata_t *new = ptr;
if (size + META_SIZE > tmp->size) {
if (!(new = malloc(size)))
return NULL;
size = ALIGN_BYTES(size);
pthread_mutex_lock(&g_info.mutex);
memcpy(new, (void *) ptr + META_SIZE,
(size <= tmp->size) ? (size) : (tmp->size));
pthread_mutex_unlock(&g_info.mutex);
free((void *) ptr + META_SIZE);
} else
new = GET_PAYLOAD(new);
return new;
}
```
Sign in with Wallet
Connect another wallet