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。

但這裡有問題是， + 7 是針對 64 bits 系統 (word size 為 8 bytes)， 32 bits 系統應該要 + 3 (word size 為 4 bytes)。 雖然在　32 bits 系統也能用，但會造成空間浪費。

TODO: 學習 Linux 核心的 ilog2，編譯時期決定要調整的空間。

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

程式有錯誤。在走訪 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;

程式錯誤：

• 用 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;

當 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;
    }
}

若 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 章閱讀。

jserv

此外程式碼註解的英文有許多文法或單字錯誤，註解很難閱讀。

其實一開始是給 ChatGPT 的 prompt

jserv

錯誤修正

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

重新實作

---

測驗 2