2023q1 Homework6 (quiz5)

contributed by < zeddyuu >

測驗 1

解釋程式碼運作原理，指出其設計和實作缺失，並予以改進。

程式一開始宣告了名為 block 的結構體來存放 metadata，有 size 代表實際存放的資料大小以及 prev 和 next 指標指向前一個和下一個 block，並且根據硬體架構是 32 bit 或是 64 bit 定義了 word_size 為多少 bytes。

/* 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()

此函式用作初始化一個 memory pool，會在系統啟動時呼叫，會先檢查傳入的位址是否合法，以及檢查傳入欲創建的大小是否大於 header_size，也就是一個 free block 必須儲存的 metadata 大小 (size, prev, next)，若檢查失敗則直接回傳錯誤，確認無誤後即開始設定一些全域變數，欲配置的 size 都必須先減掉 word_size 再賦值給 pool_size 以及 pool_free_space 紀錄，原因是因為若初始化完成後馬上全部配置出去成為 In-use block 也必須儲存 size 的資訊。

• pool_malloc()

分配參數 size 大小的記憶體，但分配之前會先對 size 進行 round up，以配合硬體架構使其可以為暫存器大小的倍數

int _size = round_up(&size);

static inline int round_up(const int *x)
{
    return ((*x + 7) >> log2_word_size) << log2_word_size;
}

但這裡 round up 的寫法只適用於 64 bit 的系統，也就是以 8 bytes 進行 round up，若為 32 bit 的系統應該要是 (*x + 3) 才對，可用 bitwise 的方法稍微改寫。

static inline int round_up(const int *x)
{
    int offset = (1 << log2_word_size) - 1;  
    return ((*x + offset) >> log2_word_size) << log2_word_size;
}

接著檢查 memory pool 的 free space 大小是否足夠分配 round up 後的 size 的量加上 header_size，若足夠則用 get_loc_to_place 找出一個大小足夠置放的 free block 記憶體位址，但在 get_loc_to_space 中發現一個錯誤是在往後找 block 時的迴圈初始化設定錯誤，應該要從 current->next 開始找起而不是 current->prev

    /* parse the next blocks to find a place */
    for (parse = ((block_t *) current)->next; parse; parse = parse->next) {
        if (parse->size >= (size + header_size))
            return parse;
    }

但奇怪的是在找到可放入的 block 後，卻沒有利用這塊找到的空間，而是直接用 current 當作可用的空間，且在 get_loc_to_space 其實也有檢查 current，故這可能會導致因為 current 其實沒有足夠的空間而發生錯誤，且在分配空間之後並沒有更新 pool_free_space 變數

• pool_calloc()

利用 pool_malloc() 分配記憶體，並且將記憶體內存的值設為 0

• pool_realloc()

利用 pool_malloc() 重新分配一個大小不同的記憶體空間，且新的記憶體內容會使用給定的 addr 記憶體內容進行複製

• pool_free()

將分配的記憶體釋放掉，利用 get_loc_to_free 去找出鄰近的 free block 用於合併，這邊注意到 get_loc_to_free 中回傳的變數型態應該要是 void * (實際上是 block_t *)，但在這個函式中的回傳型態為指標變數的記憶體位置，也就是要用指標的指標 block_t ** 去做顯式轉型，但這邊卻用了 block_t * 去做轉型，根據函式的目的應該只需要回傳 block_t *，只要將取址運算子 & 拿掉即可修正錯誤。

參考 void * 之謎

    if (!current->prev && !current->next)
        return current;
    .
    .
    loc = (block_t *) tmp_block;
    .
    .
    return loc;

    void *free_pt = get_loc_to_free(block_pt);
    block_t *free_block = (block_t *) free_pt;

接著就是對找出的 free block 去確認是否可以跟欲釋放的 block 進行合併，合併完成之後再對相鄰的 block 確認一次合併條件進行合併。

原本的程式碼只實作 first-fit 演算法，請重新實作為 best-fit

只要重新實作尋找 free block 的 get_loc_to_place() 函式即可，如果要找最適合的一定要每個 free block 都尋訪並跟當前最接近的 size 比較更新過後才能決定，因 bestfit_block 初值為 NULL，若過程中都沒找到也不會進行更新，故最後直接回傳 bestfit_block 即可，複雜度是

$O(n)$，bestfit 的演算法會造成計算上的負擔以及讓分配記憶體的複雜度變高，整體速度變慢

static inline void *get_loc_to_place(void *current, int size)
{
    block_t *parse = current;
    block_t *bestfit_block = NULL;
    int min_size = INT_MAX;
    if (parse->size >= (size + header_size)){
        if(parse->size < min_size){
            min_size = parse->size;
            bestfit_block = parse;
        }
    }

    /* parse the prev blocks to find a place */
    for (parse = ((block_t *) current)->prev; parse; parse = parse->prev) {
        if (parse->size >= (size + header_size)){
            if(parse->size < min_size){
            min_size = parse->size;
            bestfit_block = parse;
            }
        }
    }

    /* parse the next blocks to find a place */
    for (parse = ((block_t *) current)->next; parse; parse = parse->next) {
        if (parse->size >= (size + header_size)){
            if(parse->size < min_size){
            min_size = parse->size;
            bestfit_block = parse;
            }
        }
    }
    
    return bestfit_block;
}

---

測驗 2

---