# 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` 結構體 ```c 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` 因此可以改為以下程式碼，命名維持不變： ```c 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 位元組對齊。修改成以下函式： ```c 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` 中 ```c 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` 函式便是替代該節點 ```c // 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 ```c 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` 函式 函式維持不變 ```c 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〉 -->