# 2023q1 Homework6 (quiz5)
contributed by < `yanjiew1` >

## 測驗`1`

`mpool` 為 memory pool 實作。

`pool_init` 是用來初始化 `mpool` 系統，透過它告訴 `mpool` 使用哪塊空間作為 memory pool 使用 ，空間大小有多少。

`mpool` 實作了類似 C 語言標準函式庫提供的記憶體配置器函式，分別為 `pool_malloc` 、 `pool_calloc` 、 `pool_realloc` 、 `pool_free` 。功能與 C 語言的記憶體置器很像，差別在於 `mpool` 是從一個設定好的一塊 memory pool 來配置空間。

### 程式碼運作原理

已配置的空間為系統 word size 大小的 `size` 和 `payload` 組成。`malloc` 會回傳 `payload` 部份的指標。`payload` 為使用 `mpool` 程式可以利用的空間。

+------------------------------------------------+
| size | payload                                 |
+------------------------------------------------+

未配置空間除了 `size` 外，後面還會接續 `prev` 和 `next` 二個指標，分別指向上一個和下一個未配置空間。

--------------------------------------------------
| size | prev | next | ..........                |
--------------------------------------------------

上述二種狀態都可用 `block_t` 結構來表示。`size` 為已配置和未配置空間都會使用的欄位，而 `prev` 和 `next` 只會在未配置空間使用。

/* The basic data structure describing a free space arena element */
typedef struct block {
    int size;                  /**< Size of the data payload */
    struct block *prev, *next; /**< Pointer to the previous/next block */
} block_t;

#### `pool_init`

程式一開始會呼叫 `pool_init` 來告訴 `mpool` 可以使用哪塊空間作為 memory pool 。函式中會檢查大小是否大於 `header_size` (即 3 個 word size) ，若大小小於 `head_size` 代表連未配置空間的標頭都放不下，無法使用。

if (size <= header_size) // AAAA /* size is too small, can notstore a header */
    return false;

`pool_init` 也會設定全域變數 `pool_size` 和 `pool_free_space` 。 `pool_size` 為總共 memory pool 空間， `pool_free_space` 為未配置空間。這二個空間都要減去 `word_size` 是因為即使一次把整塊空間都配置出去，其最前面的標頭還是需要放配置出去的空間大小，故使用者可用的空間需要減去 `word_size` 。

pool_size = size - word_size;
pool_free_space = size - word_size;

`pool_init` 會把傳入的空間放到 free list 上，並寫入未配置空間的標頭，即 `size` 、 `prev` 和 `next` 。 程式中的 `current` 為 free list 。

current = (block_t *) addr;
current->size = pool_free_space;
current->prev = NULL, current->next = NULL;

#### `pool_malloc`

`pool_malloc` 會從 memory pool 配置空間。配置時，會使用 `round_up` 取得大於等於 `size` 的最小可以被 word_size 整除的數字，作為真正配置的空間。這樣做是為了讓得到的記憶體空間都能跟 word size 對齊，避免出現未對齊的操作。其中 `round_up` 實作如下：

/* Round up a size to the next multiple of 32 or 64 bits size */
static inline int round_up(const int *x)
{
    return ((*x + 7) >> log2_word_size) << log2_word_size; // BBBB and CCCC
}

其實就是先把原本的數加上 7 再 round down 至 word size。

:::warning
但這裡有問題是， `+ 7` 是針對 64 bits 系統 (word size 為 8 bytes)， 32 bits 系統應該要 `+ 3` (word size 為 4 bytes)。 雖然在　32 bits 系統也能用，但會造成空間浪費。
> TODO: 學習 Linux 核心的 ilog2，編譯時期決定要調整的空間。 :notes: jserv
:::

接著 `pool_malloc` 會透過 `get_loc_to_place` 用 first-fit 的演算法，從　free list 中找到一塊可用的空間。　`get_loc_to_place` 會先檢查 `current` 指標所指向的空間是否可用，若不可用則會先走訪 `prev` 指標，若仍然未找到可用的空間再走訪 `next` 指標。

/* 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)->prev; parse; parse = parse->next) {
        if (parse->size >= (size + header_size))
            return parse;
    }

    /* No space found, stop the allocation */
    return NULL;
}

:::warning
程式有錯誤。在走訪 `next` 指標是，應該是由 `((block_t *) current)->next` 開始走訪，而不是 `((block_t *) current)->prev` 。這樣子導致當 `((block_t *) current)->prev` 為 `NULL` 時，無法正常配置空間，即使走訪 `next` 有可用的空間。

此外，這裡確保取得的空間有 `size + header_size` ，是因為在 `pool_malloc` 中，會把一個 free block 的前半部分配出去，後半部作為剩下的空間， `pool_malloc` 沒有考慮到整塊空間配置出去的情況，一定會留下一個 free block 。
:::

呼叫 `get_loc_to_place` 取得可用的 block 。回傳值設為取得的空間加上 word size 。因為最前面要存放 `size` 。

void *ret = get_loc_to_place(current, _size); // EEEE

if (!ret)
    return NULL;

/* payload's address the application can use */
ret = (char *) current + word_size;

:::danger
程式錯誤：
- 用 `get_loc_to_place` 取得 free block 後，卻又把 `current` 指向的 free block 配置出去，沒有利用到 `get_loc_to_place` 找到的空間。
- 沒有設定配置出去的空間標頭中的 `size` 欄位。
:::

從 `current` 配置空間後，備份原本 `current` 的 `prev` 和 `next` 指標，並設定把 `current` 設定成新的 free block 。

/* 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; // FFFF

/* Adjust free space of current block and update its meta-data */
void *new_space = (char *) current + word_size + _size; // GGGG
current = new_space;

if (new_size < 0) {
    current->size = 0;
    return NULL;
}
current->size = new_size;

current->prev = prev_pt, current->next = next_pt;

:::danger
當 `new_size` 小於 0 時，會放棄設定新的 free block ，但裡面有把 `current->size` 指定為 0 ，可能就覆寫到其他空間了。此外如果要有足夠空間存放新的 free block ，至少 `new_size` 要有二個 word size 的空間才夠，但這裡也沒考慮到。

不過因為前面的程式已經錯了，所以後面的程式自然就接連有問題。
:::

最後更新前後 free blocks 的指標：

/* 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_calloc`

`pool_calloc` 可以利用原有的 `pool_malloc` ，再把新配置的空間填 0 。

void *pool_calloc(int size)
{
    void *ptr = pool_malloc(size);
    if (!ptr)
        return NULL;

    memset(ptr, 0, size);
    return ptr;
}

#### `pool_realloc`

`pool_realloc` 重新呼叫 `pool_malloc` 配置新空間，再把原有的內容拷貝過去，再把原有的空間釋放。

void *pool_realloc(void *addr, int size)
{
    void *ptr = pool_malloc(size);
    if (!ptr)
        return NULL;

    memcpy(ptr, addr, size);
    pool_free(addr);
    return ptr;
}

#### `pool_free`

取得傳入位址的包含標頭的位址。因為知道所有經由 `mpool` 配置出來的空間前一個 word ，就是記錄配置空間的大小。

/* Get block info */
void *block_pt = (char *) addr - word_size; // HHHH
block_t *block = block_pt;

使用 `get_loc_to_free` 取得鄰近的 free block

/* Free space zone to connect or merge with the block to release. Multiple
 * free blocks are suitable to connect, ensuring we will parse fastly the
 * linked list.
 */
void *free_pt = get_loc_to_free(block_pt);
block_t *free_block = (block_t *) free_pt;

若找到的 free block 與傳入要釋放的記憶體相鄰，則將此 free 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;
        /* 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;
    }
}

:::danger
若 `free_pt` 與 `block_pt` 不相鄰怎麼辦？ 這樣子 `block` 內的 `prev` 和 `next` 就沒被設置。 `pool_free` 顯然沒考慮此情況，會產生不可預期的結果。
:::

最後再嘗試合併相鄰的 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;
    }
}

/* 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;
    }
}

### 程式的缺失與改進

#### 缺失

`mpool` 不論是 `pool_malloc` 或是 `pool_free` 都有明顯的錯誤。`pool_realloc` 採用重新配置空間的策略，沒有考慮是不有可能就地縮小或增加空間，也還有改進的空間。在 `pool_free` 需要再走訪 free list ，才能找到鄰近的 free block ，時間複雜度為 $O(n)$ 較沒效率。
> 可對照 CS:APP 第 9 章閱讀。 :notes: jserv

此外程式碼註解的英文有許多文法或單字錯誤，註解很難閱讀。
> 其實一開始是給 ChatGPT 的 prompt :notes: jserv

#### 錯誤修正

嘗試保留原有的程式碼，但修復程式中的錯誤。

#### 重新實作

---

## 測驗 `2`