# 2023q1 Homework6 (quiz5)
contributed by < `a1091150` >
> [GitHub: 測驗 1](https://github.com/a1091150/2023q1_Homework6_quiz5.git)
> [GitHub: 測驗 2](https://github.com/a1091150/2023q1_Homework6_quiz5_problem2)

實驗機器： 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
<!--
- https://www.youtube.com/live/za-AbFs0ztM?feature=share&t=1646
- https://hackmd.io/@ljP_AG30SzmQE5qO-cjcpQ/rkMwMKf6
- memory pool 對頻繁 malloc 的程式碼可以有改進空間

---
- 指出其缺失
- 修改成 best-fit
-
- 修改成 `list_head` 的形式、移除 std 使用，並加入 `fibdrv`

-->
### 指出其設計和實作缺失
- 使用全域變數 `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](https://gist.github.com/jserv/2133fb04f30b1a08c306643521b096d3) 的程式碼與測驗 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](https://github.com/a1091150/2023q1_Homework6_quiz5_problem2)

程式碼可以拆成：
- `metadata_t` 與 `sbrk` 實作於 `heap.c` 與 `heap.h`
- `rbnode_t` 實作於 `rbtree.h` 與 `rbtree.c`
- `malloc`, `free` 函式實作於 `xalloc.h` 與 `xalloc.c`
<!--
目前正在研讀〈針對多執行緒環境設計的 Memory allocator〉
-->