2023q1 Homework6 (quiz5)

contributed by < a1091150 >

GitHub: 測驗 1
GitHub: 測驗 2

實驗機器： Macbook Air 2013 A1466

Architecture:            x86_64
  Byte Order:            Little Endian
CPU(s):                  4
  On-line CPU(s) list:   0-3
Vendor ID:               GenuineIntel
  Model name:            Intel(R) Core(TM) i5-4250U CPU @ 1.30GHz
  
gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0

測驗 1

指出其設計和實作缺失

• 使用全域變數 tmp_block 跨越函式存取
• 變數重複命名，全域變數 current 與部份區域變數同樣名稱
• 部份函式實作錯誤
  • pool_malloc 函式經由 get_loc_to_place() 取得定 block，但是之後直接使用 current
  • round_up() 函式實作錯誤

修正的方式：加入 lab0 中的 list.h 檔案時候一併修正所有問題

使用 list_head

這裡移植第一次的作業中 lab0 的 list.h 檔案，方便之後加入至 fibdrv 中，依照原本的程式碼概念重寫函式

struct block 結構體

根據註釋， free block 的 prev 與 next 成員會成為 in-use block 的 payload，因此加入一個 union 來描述此結構體

將原本 prev 與 next 修改為 list_head 結構體

typedef struct block {
    int size;
    union {
        char *payload;
        struct {
            struct list_head list; 
        };
    };
} block_t;

以圖片表示其構造

  In-use block                            Free block

    start addr ──────► ┌──────────┐ ◄───── block.size
                       │          │
                       │   size   │
block->payload ──────► ├──────────┤ ◄───── block.list.prev
                       │   prev   │
                       ├──────────┤ ◄───── block.list.next
                       │   next   │
                       ├──────────┤
                       │   ...    │
                       │          │
                       └──────────┘

word_size 與 header_size

word_size 原本是對應 __SIZE_WIDTH__ / 8 ，但是在程式碼中只描述 block 中的 int 位元組大小，在命名上我認為可以改成 payload_offset

header_size 原本是對應 word_size * 3，但在程式碼中描述 block 結構體的位元組大小，在命名上我認為可以改成 block_size

因此可以改為以下程式碼，命名維持不變：

enum {
    word_size = sizeof(int),
    log2_word_size = __builtin_ctz(sizeof(int)),
    header_size = sizeof(block_t), 
};

round_up 函式

未特別設定下log2_word_size 為 2，原本的實作假設為 3，導致實作上不會與 4 位元組對齊。修改成以下函式：

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

新增 block_head 變數

新增一個串列 static LIST_HEAD(block_head);，將所有 free block 以位址由小至大排列。

pool_init 函式

透過 list_head 相關函式將 free block 加入至 block_head 中

bool pool_init(void *addr, int size)
{
    if (!addr)
        return false;

    if (size <= header_size)
        return false;

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

    block_t *current = (block_t *) addr;
    current->size = pool_free_space;
    list_add(&current->list, &block_head);
    return true;
}

pool_malloc 函式

在原本的 pool_malloc 函式實作中，必定會有一個 free block ，它的作用類似於 stack pointer，同時表示末端位址的剩餘空間。可以假定一定有一個 free block

• get_loc_to_place 函式透過 list_head 相關函式簡化實作，回傳首個符合的 free block (first fit)
• pool_malloc 函式分裂該 free block 成兩個，其中一個回傳，另一個加回 block_head 中
• 由分裂後的 free block 替代原本的 free block，list_replace 函式便是替代該節點

// First fit
static inline block_t *get_loc_to_place(int size)
{
    block_t *node;
    list_for_each_entry (node, &block_head, list) {
        if (node->size >= (size + header_size))
            return node;
    }
    return NULL;
}

static inline void list_replace(struct list_head *from, struct list_head *to)
{
    *to = *from;
    to->next->prev = to;
    to->prev->next = to;
}

void *pool_malloc(int size)
{
    if (size <= 0)
        return NULL;

    int _size = round_up(&size);
    if (pool_free_space <= (_size + header_size))
        return NULL;

    block_t *ret = get_loc_to_place(size);

    if (!ret)
        return NULL;

    block_t *new_block = (block_t *) (&ret->payload + _size);
    new_block->size = ret->size - word_size - _size;
    ret->size = _size;
    list_replace(&ret->list, &new_block->list);
    pool_free_space -= _size;
    pool_free_space -= word_size;
    return &ret->payload;
}

pool_free 函式

• 在 pool_free 函式中，在 block_head 尋找適合的節點位址，將回收的 block 加入，並嘗試合併前後一個的 free block
• get_loc_to_free 函式透過 block_head 中的 free block 以位址大小排列的特性，比較位址順序，回傳後一個 free block
• list_insert_before 函式將回收的 block 加入至指定串列位址中
• block_try_merge 函式嘗試合併前後 free block

static inline struct list_head *get_loc_to_free(void *addr)
{
    /* In case the free block is monolithic, just return its address */
    if (list_is_singular(&block_head))
        return block_head.prev;

    block_t *target = container_of(addr, block_t, payload);
    block_t *node = NULL;

    list_for_each_entry (node, &block_head, list) {
        if ((uintptr_t) target < (uintptr_t) node)
            break;
    }

    return &node->list;
}

static inline void list_insert_before(struct list_head *node,
                                      struct list_head *after)
{
    struct list_head *prev = after->prev;
    node->prev = prev;
    node->next = after;
    after->prev = node;
    prev->next = node;
}

static void block_try_merge(struct list_head *node1, struct list_head *node2)
{
    if (node1 == &block_head || node2 == &block_head)
        return;

    block_t *n1 = container_of(node1, block_t, list);
    block_t *n2 = container_of(node2, block_t, list);
    uintptr_t loc = (uintptr_t) (&n1->payload + n1->size);
    if (loc == (uintptr_t) n2) {
        list_del(node2);
        n1->size += word_size + n2->size;
        pool_free_space += word_size;
    }
}

void pool_free(void *addr)
{
    block_t *target = container_of(addr, block_t, payload);
    pool_free_space += target->size;
    struct list_head *target_after = get_loc_to_free(addr);
    list_insert_before(&target->list, target_after);
    block_try_merge(&target->list, target->list.next);
    block_try_merge(target->list.prev, &target->list);
}

mpool_realloc 函式與 pool_calloc 函式

函式維持不變

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

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

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

---

測驗 2

alloc.c 的程式碼與測驗 1 部份實作概念類似

• metadata_t 紀錄 block，與測驗 1 的 block_t 概念相同，這一次有紀錄 *prev 與 *next
• rbnode_t 紀錄相同大小的 free block
  • **tab_values 指標的指標陣列，分別指向相同 size 大小的 free block
  • alloc_tab 一樣透過 get_heap() 函式取得空間，若用 resize_tab_values 增加陣列大小，則原本的空間有機會在 free 函式呼叫時，透過 try_fusion 函式重新加入 red black tree

另外程式碼有些怪異的寫法：

• rbnode_t 中的 metadata_t *next, *prev 完全沒有使用；但是重新觀察會發現該前三個成員與 metadata_t 完全相同

改進實作

GitHub: 測驗 2

程式碼可以拆成：

• metadata_t 與 sbrk 實作於 heap.c 與 heap.h
• rbnode_t 實作於 rbtree.h 與 rbtree.c
• malloc, free 函式實作於 xalloc.h 與 xalloc.c