---
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

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

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` ，並不適用，所以改成：

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` 去尋找可使用的區塊。

void *ret = get_loc_to_place(current, _size);

因為採用 first-fit ，所以當有足夠大小的區塊時就直接配置，否則就往下尋找。這裡有個問題是 `get_loc_to_place` 傳入的參數名稱與全域變數 `current` 是一樣的，會導致自己判斷時可能會錯誤。

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`)。

/* 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 接上。

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 中。

/* 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。

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 在前或在後。

/* 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 的資訊。

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` 。

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` 。

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 中。

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);`
:::