2023q1 Homework6 (quiz5)

--- tags: linux kernel, jserv --- # 2023q1 Homework6 (quiz5) contributed by < [`WangHanChi`](https://github.com/WangHanChi) > > [作業要求](https://hackmd.io/@sysprog/linux2023-quiz5) :::info - 測驗一 - [ ] 解釋上方程式碼運作原理，指出其設計和實作缺失，並予以改進。不用抄寫題目，專注於你對程式碼的理解 - [ ] 原本的程式碼只實作 first-fit 演算法，請重新實作為 best-fit - [ ] 將 memory pool 程式碼引入到 fibdrv 或課程作業中 - 測驗二 - [ ] 解釋程式碼運作原理，說明如何搭配紅黑樹來實作 best-fit 策略 - [ ] 以第 3 週測驗和第 4 週測驗題目所及、調整過的紅黑樹程式碼，重寫上述程式碼，使其得以用低的記憶體開銷和處理更大的記憶體範圍 - [ ] 用 mmap 系統呼叫替換 sbrk - [ ] 研讀〈針對多執行緒環境設計的 Memory allocator〉和過往課程學員針對 mimalloc 做的改進，探討 Linux 核心可用於改進記憶體配置效率的機制 ::: --- :::spoiler 實驗環境 ``` $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 Copyright (C) 2021 Free Software Foundation, Inc. $ lscpu | less Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 48 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 12 On-line CPU(s) list: 0-11 Vendor ID: AuthenticAMD Model name: AMD Ryzen 5 5600X 6-Core Processor CPU family: 25 Model: 33 Thread(s) per core: 2 Core(s) per socket: 6 Socket(s): 1 Stepping: 0 Frequency boost: enabled CPU max MHz: 4650.2920 CPU min MHz: 2200.0000 BogoMIPS: 7385.75 ``` ::: ## 測驗一 ### 程式碼運作原理 #### `block_t` ```c /* 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; ``` 這個結構體包括了該 block 的有效的空閒大小也有指向下一個以及前一個 block 的指標。 ```graphviz digraph list_ele { rankdir=LR; node[shape=record]; node [shape=record]; head [label="size|{<left>prev|<right>next}", style=bold]; e1 [label="size|{<left>prev|<right>next}", style=bold]; e2 [label="size|{<left>prev|<right>next}", style=bold]; e3 [label="size|{<left>prev|<right>next}", style=bold]; NULL [label = "NULL"]; NULL2 [label = "NULL"]; head:right -> e1:size; e1:right -> e2:size; e2:right -> e3:size; e3:right -> NULL e3:left -> e2:size; e2:left -> e1:size; e1:left -> head:size; head:left -> NULL2; } ``` 如上圖，將閒置的 block 以 list 進行串接。而 `prev` 和 `next` 則用於將該塊 block 連接到空閒記憶體一堆 block 雙向 list 中，以便於在執行 malloc() 時快速地查找可用的空間。當此 block 被釋放時，也可以通過這個結構體的指標在 list 中搜索前一個和後一個 block，以實現 block 合併。因此，這個結構體的用途是為了管理 memory pool 中的可用 block 所設計的。 #### word_size ```c /* Size of a memory element, 32 or 64 bits */ enum { word_size = __SIZE_WIDTH__ / 8, /**< size of memory element */ #if __SIZE_WIDTH__ == 64 log2_word_size = 3, #else log2_word_size = 2, #endif header_size = 3 * word_size, /**< size, previous/next block addresses */ }; ``` 這邊是根據機器的架構來設定 word_size，並且根據 word_size 來決定 `log2_word_size` 最後還設定了 header_size 的大小為 3 個 word_size。而我的機器是 X86-64 的，所以我的 word_size 會是 `64 / 8` 也就是 `8` ， `log2_word_size` 的大小會是 `3`。 #### Global variables ```c /* Used to track arena status during usage and check if no leaks occcur */ static int pool_size; static int pool_free_space; ``` 在這邊可以看到他在假設沒有發生 memory leak 的情況下，設定了 pool 的大小 `pool_size` ，以及剩下可以使用的空間 `pool_free_space` #### `pool_init` ```c bool pool_init(void *addr, int size) { if (!addr) /* not a valid memory address */ return false; if (size <= header_size) /* size is too small, can notstore a header */ return false; tmp_block = 0; tmp_pt = 0; pool_size = size - word_size; pool_free_space = size - word_size; current = (block_t *) addr; current->size = pool_free_space; current->prev = NULL, current->next = NULL; return true; } ``` 上面這段程式碼主要做的就進行初始化。並且檢查了初始化池的大小被需要大於 3 個 `word_size` 才可以進行初始化。 #### `round_up` ```c /* 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; } ``` 這段程式碼主要在進行的是進位到指定的數字，來確保每次要進行 alloc 的空間都會是 word_size 的倍數。下方的註解也同時印證了功能 ```c /* Round up the size up to the arch width. Ensure the size is at minimum a * register size and a multiple of that register. So if use 64 bits arch, a * 4 bytes allocation is round up to 8 bytes, and 28 bytes is round up to * 32 bytes. */ ``` 先以 64 bit 的機器為例 ``` 假設傳入 *x 為 35 那(35 + 7) >> 3 會得到 5 再將 5 << 3 ，最終可以得到 40。 40 對齊的 8 bytes 的記憶體大小 ``` 再以 32 bit 的機器為例 ``` 假設傳入 *x 為 35 那(35 + 7) >> 2 會得到 10 再將 10 << 2 ，最終可以得到 40。 40 對齊的 4 bytes 的記憶體大小且慢!!! 40 並不是一個正確的數字，原本的 35 應該要進位到 36 的。但是因為在 (35 + 7) 的時候，加超過了 word_size 的大小，才會造成這樣的情況發生 ``` 由上面的例子可以發現這邊有小錯誤，因此將其進行修改 ```c static inline int round_up(const int *x) { return ((*x + (word_size - 1)) >> log2_word_size) << log2_word_size; } ``` 這樣就可以在應對 64 bit 的機器時，加上 `7` ; 而在面對 32 bit 的機器的時候可以加上 `3` #### `get_loc_to_place` ```c /* 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; } ``` 這個函式是用來找尋有沒有一個可以用的空閒 block 的。可以看到它會先去搜尋 `prev` 的部份，如果沒有找到足夠大小的話，就會搜尋 `next` 的部份。 #### `pool_malloc` :pencil: 由於這個函式比較長，所以擷取部份的程式碼來講解 ```c /* Round up the size up to the arch width. Ensure the size is at minimum a * register size and a multiple of that register. So if use 64 bits arch, a * 4 bytes allocation is round up to 8 bytes, and 28 bytes is round up to * 32 bytes. */ int _size = round_up(&size); /* Return NULL if failed to allocate a buffer */ if (pool_free_space <= (_size + header_size)) return NULL; void *ret = get_loc_to_place(current, _size); if (!ret) return NULL; ``` 這邊先將 size 進行對齊 word_size ，再根據新的 \_size ，來找到大小合適的閒置 block。 ```c /* payload's address the application can use */ ret = (char *) current + word_size; /* 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; /* Adjust free space of current block and update its meta-data */ void *new_space = (char *) current + word_size + _size; current = new_space; if (new_size < 0) { current->size = 0; return NULL; } current->size = new_size; current->prev = prev_pt, current->next = next_pt; ``` 這邊主要在設定新的節點的大小以及 size 。可以看到它都是先將原本的 `next` 與 `prev` 存在 `next_pt` 與 `prev_pt` 中。在 size 改變完成之後，再把這兩個指標設定回 current 的 `next` 與 `prev`。 #### `pool_calloc` ```c void *pool_calloc(int size) { void *ptr = pool_malloc(size); if (!ptr) return NULL; memset(ptr, 0, size); return ptr; } ``` 可以明顯的看到 `calloc` 就是使用了 malloc 加上 memset 的組合。先將一段記憶體分配之後在初始化為 `0`。 #### `pool_realloc` ```c 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; } ``` 這邊可以看到它會先使用新的 size 進行一段記憶體的分配。再來會把 `addr` 的值複製到 `ptr` 中。最後再將 `addr` 釋放。 >目前看起來沒有什麼大礙，但是感覺在處理字串的時候會出問題 ('\0') !? >但是後來想想，這個問題應該交由使用者來處理，不應該是在配置記憶體時考慮 #### `get_loc_to_free` ```c ... /* Location found to place the bloc under release */ void *loc = NULL; /* The list is ordered by address, so we can divide the parsing to select * directly the right direction. */ if ((uintptr_t) addr < (uintptr_t) tmp_pt) { for (;; tmp_block = tmp_block->prev) { loc = (block_t *) &tmp_block; /* No more free space on smaller address range, so when can place * this block on left of the current tmp / current free space. */ if (!tmp_block->prev) break; /* Next free block has a smaller address, so we are place between * two blocks: free.prev < data block < tmp / currrent free space. */ if ((uintptr_t) addr > (uintptr_t) tmp_block->prev) break; } } else { ... ``` 以上為部份程式碼這邊可以看到他的他先將 loc 設定為 NULL，若是在兩個 for 迴圈(`prev` 與 `next` )透過比大小的方式找到合適的 free 區域，就會回傳那個區域的指標。若是沒有找到，就會回傳 NULL。 #### `pool_free` ```c /* Get block info */ void *block_pt = (char *) addr - word_size; block_t *block = block_pt; /* Update pool arena statistics */ pool_free_space += block->size; /* Region is used to check if the block to release is adjacent to a free * space. */ void *region; /* 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; ... ``` 這邊先對 pool_free_size 進行釋放後到大小的調整，接著透過上面所提到的 `get_loc_to_free` 來找到哪個部分可以進行釋放，再將其轉型成我們所定義的 `block_t`。接下來會依據 `block_pt` 與 `free_pt` 分成兩個部分 ```c /* 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; } } } ... ``` 這邊可以看到他先檢查了要釋放的區域是否符合 `block 的地址` + `block 的大小` + `word_size` 若是符合的話，就會進行 `next` 與 `prev` 的連接。 ```c 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; } } ``` 這邊是 `(uintptr_t) block_pt >= (uintptr_t) free_pt` 的情況同樣也是確認了釋放的區域是否符合 `block 的地址` + `block 的大小` + `word_size` 但是這邊沒有做連接的動作，推測是當 `block_pt` 的記憶體位址大於等於 `free_pt` 的記憶體位址時，代表需要把 `free_block` 與 `block` 合併。在此情況下，已經把 `free_block` 的空間加入到 `block` 中了，而 `block` 的起始位置是在原先的 `free_block` 之前，因此已經不需要再次與前面的記憶體空間連接。所以在這個情況下，沒有必要再次連接前後的記憶體。 ### First-fit & Best-fit 首先先複習 First-fit 與 Best-fit，可以透過 [Best-Fit Allocation in Operating System](https://www.geeksforgeeks.org/best-fit-allocation-in-operating-system/) 與[恐龍書](https://www.tenlong.com.tw/products/9789865522506)歸納出幾個重點。 #### First-fit First-fit 演算法是指從頭開始搜尋可用的記憶體區塊，當找到第一個大於等於要求大小的區塊時，就將該區塊分配給申請記憶體的程序。這種演算法的優點是簡單且快速，但可能會造成內部碎片（未使用的小塊記憶體），進而浪費可用的記憶體空間。 - 優點 - 簡單高效的搜索演算法 - 最小化記憶體碎片 - 快速分配記憶體 - 缺點 - 在高度碎片化的記憶體中性能不佳 - 可能導致記憶體利用率低下 - 可能會分配比所需更大的記憶體 block。 #### Best-fit Best-fit 演算法是指從所有可用的記憶體區塊中，選擇最小但大於等於要求大小的區塊分配給申請記憶體的程序。該演算法可以最小化內部碎片，但需要額外的搜索時間來找到最佳的可用區塊，因此較為耗時。 - 優點 - 作業系統在記憶體中為 block 分配盡可能小的空間，使記憶體管理非常高效率。 - 為了避免記憶體被浪費。 - 提高記憶體利用率 - 減少記憶體碎片 - 最小化外部碎片 - 缺點 - 這是一個非常耗時間的過程。為每個 block 檢查整個記憶體會使作業系統的運行非常緩慢。完成這項工作需要很多時間。 - 增加計算開銷 - 可能導致內部碎片增加 - 可能導致記憶體分配時間變慢。 #### 進行修改由上面可以知道 best-fit 的重點是他會找到最小的記憶體區塊，所以我們可以在目前 first-fit 的基礎上，加上一個暫存 block，來代表符合 block 的大小同時又是最小值，因此可以將 `get_loc_to_place_best_fit` 如下表示 ```c /* Search for a free space to place a new block */ static inline void *get_loc_to_place_best_fit(void *current, int size) { block_t *parse = current; block_t *best_fit = NULL; if (parse->size >= (size + header_size)) return current; /* parse the prev blocks to find the best-fit block */ for (parse = ((block_t *) current)->prev; parse; parse = parse->prev) { if (parse->size >= (size + header_size) && (!best_fit || parse->size < best_fit->size)) best_fit = parse; } /* parse the next blocks to find the best-fit block */ for (parse = ((block_t *) current)->next; parse; parse = parse->next) { if (parse->size >= (size + header_size) && (!best_fit || parse->size < best_fit->size)) best_fit = parse; } if (best_fit) return (void *)best_fit; /* No space found, stop the allocation */ return NULL; } ``` 可以看到他在進行走訪時，不會因為找到一個可用的區塊就回傳，而是會繼續走訪，嘗試找到更小的記憶體區塊。接下來 `get_loc_to_free_best_fit` 也要進行修改 ```c static void *get_loc_to_free_best_fit(void *addr) { /* In case the free block is monolithic, just return its address */ if (!current->prev && !current->next) return &current; /* The current block of free space manipulated */ tmp_pt = (block_t *) &current; tmp_block = tmp_pt; /* Location found to place the bloc under release */ void *loc = NULL; void *best_fit = NULL; /* The list is ordered by address, so we can divide the parsing to select * directly the right direction. */ if ((uintptr_t) addr < (uintptr_t) tmp_pt) { for (;; tmp_block = tmp_block->prev) { loc = (block_t *) &tmp_block; /* No more free space on smaller address range, so when can place * this block on left of the current tmp / current free space. */ if (!tmp_block->prev) break; /* Next free block has a smaller address, so we are place between * two blocks: free.prev < data block < tmp / currrent free space. */ if ((uintptr_t) addr > (uintptr_t) tmp_block->prev && (!best_fit || ((block_t *)loc)->size < best_fit->size)){ best_fit = loc; } } } else { for (;; tmp_block = tmp_block->next) { loc = (block_t *) &tmp_block; /* No more free space on higher address range, so when can place * this block on right of the current tmp / current free space. */ if (!tmp_block->next) break; /* Next free block has a higher address, so we are place between * two blocks: free.prev < data block < tmp / currrent free space. */ if ((uintptr_t) addr < (uintptr_t) tmp_block->prev && (!best_fit || ((block_t *)loc)->size < best_fit->size)){ best_fit = loc; } } } return loc; } ``` ### 指出設計缺失其實在閱讀這份程式碼的時候覺得很<s>抽象</s> ---，可能是因為實作上有缺失或是我不了解 memory pool :::warning 不要濫用「[抽象](https://dict.revised.moe.edu.tw/dictView.jsp?ID=122548)」一詞，以下摘錄國語辭典: * 哲學上指從個別的、偶然的不同事物中，分析出其共同點的思想活動。相對於具體而言。 * 泛指籠統概括。亦相對於具體而言不懂就說不懂，不要用不相關的詞彙搪塞。 :notes: jserv ::: #### get_loc_to_place ```c ... /* Current free space manipulated by the arena */ static block_t *current; ... static inline void *get_loc_to_place(void *current, int size) ... ``` 這邊程式碼可以看到他在一開始的全域變數中就已經使用到了 current 這個變數名稱，但是在函式 `get_loc_to_plcae` 中又同樣使用了一樣的變數名稱 #### pool_malloc ```c void *ret = get_loc_to_place(current, _size); if (!ret) return NULL; /* payload's address the application can use */ ret = (char *) current + word_size; ``` 這邊可以看到它先用了 ret 來儲存要配置的位置，但是後來用直接修改掉了這個位置，所以這邊應該的缺失是應該用以 ret 來做為要配置的位置。 --- ## 測驗二 ### 程式碼運作原理 #### 結構體這邊定義了三個結構體 `metadata_t`, `rbnode_t` 與 `malloc_t` ```c typedef struct metadata { size_t size; size_t free; struct metadata *next, *prev; } metadata_t; ``` metadata_t 紀錄了大小與空閒空間的大小還有以 list 的方式指向前一個及下一個節點的資訊。 ```c typedef struct rbnode { size_t size; size_t free; metadata_t *next, *prev; t_key key; t_value **tab_values; size_t size_tab; size_t n_active; rbcolor_t color; struct rbnode *left, *right; } rbnode_t; ``` 這個結構主要在實作紅黑樹的節點，但是同時也參雜了其他的資訊，像是 metadata_t 等等其中還有一些目前不確定用意的資訊，像是 `size_t n_active`，等看到下面理解了再回來補！ ```c typedef struct { rbnode_t *root_rbtree; metadata_t *last_node; void *end_in_page; void *first_block; int page_size; pthread_mutex_t mutex; size_t page_remaining; } malloc_t; ``` 這個結構包含了紅黑樹的根節點, metadata 的最後一個節點, 指向最後一個 page 的指標, page_size 等等的。特別看到它塞了一個 mutex 在裡面，目的是確保在進行 malloc 的時候是 thread-safe 的。 >因為在標準函式庫中的 malloc 也是 thread-safe 的，因此這裡應該是想要做一樣的功能。 > > | Interface | Attribute | Value | > | ------------------------------------- | ------------- | ------- | > | malloc(), free(), calloc(), realloc() | Thread safety | MT-Safe | #### Macro 再來是很多的巨集 define ```c #define YFREE 0xDEADBEEF5EBA571E #define NFREE 0x5EBA571EDEADBEEF ``` 這兩個巨集代表了記憶體的狀態，其中 YFREE 代表該塊記憶體已被釋放，NFREE 代表該塊記憶體未被釋放。這些數值都是為了避免特定的數值被誤認為有效的指標或記憶體狀態而設定的。 ```c #define ALIGN_BYTES(x) ((((x - 1) >> 4) << 4) + 16) ``` 可以看到 64-bit 的機器在進行 malloc 的時候會以 16 個 byte 進行 align，詳情可以參考 [你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory#data-alignment) 中有詳細的介紹並且也有實驗證明。 ```c #define GET_PAYLOAD(x) ((void *) ((size_t) x + META_SIZE)) ``` 可以參考下面的圖(出處:〈[自己擼了一個 malloc 內存分配器](https://www.readfog.com/a/1650959933121859584)〉) 或是 CSAPP 第 592 頁中的圖 **9-35**，`x` 就是紅色的那個區塊，而 `META_DATA` 就是藍色的那個區塊，因此這個函式可以得到 PAYLOAD 的地址，也就是下圖中灰色的區塊。 :::spoiler 原圖 ![](https://i.imgur.com/IQywGI0.png) ::: ```graphviz digraph list_ele { rankdir=LR; node[shape=record]; node [shape=record]; head [label="{<left>META_DATA|<right>x}|<load>PAYLOAD", style=bold]; xptr [shape=plaintext;label="引數 x 所指向的記憶體位置"] header [shape=plaintext;label="關於這個 block 的 header"] payload [shape=plaintext;label="可以被配置的空閒記憶體區塊"] xptr -> head:right header -> head:left payload -> head:load } ``` :::warning 重新製圖，留意使用一致的術語。 :notes: jserv ::: ```c #define IS_VALID(x) \ (((metadata_t *) x)->free == YFREE || ((metadata_t *) x)->free == NFREE) ``` 檢查所傳入的指標是否是有效的記憶體區塊。 - 如果記憶體區塊的 free 欄位等於 `YFREE` 或 `NFREE`，則視為有效的記憶體區塊。 - 如果記憶體區塊的 free 欄位不等於 `YFREE` 也不等於 `NFREE`，則視為無效的記憶體區塊。 #### 紅黑樹的操作由於有些操作比較基本，就不特別說明 ##### `insert_node` 這個函式是用來在紅黑樹的節點中插入一個新的記憶體區塊(metadata_t) ```c if (node->n_active == size) { i = node->n_active; if (!resize_tab_values(tmp, node)) return false; } else { while (i < size && tmp[i]) i++; } ``` 可以看到如果節點中已經有 `n_active` 個有效值了，表示 tab_values 陣列已滿，需要擴大陣列，使用到了 resize_tab_size 這個函式; 若是 tab_values 陣列沒有滿，則會進到 else-statement 從 tab_values 陣列的第0個位置開始，查找一個空的元素，直到找到一個空的位置或陣列結束為止。在找到了之後， tab_values 陣列中的第 `i` 個位置上，插入新的記憶體區塊 (metadata_t)，再來就是更新節點中n_active變數的數值。 #### 記憶體的操作 ##### `get_new_page` 可以在 `get_new_page` 中看到使用 sbrk() 系統呼叫來分配這些 page 。如果分配失敗，它會回傳 -1 並將錯誤設定為 ENOMEM。如果是第一次呼叫的話，就會進到這個 if-statement ```c if (!g_info.end_in_page) { if ((g_info.end_in_page = sbrk(0)) == (void *) -1) return (size_t) -1; g_info.first_block = g_info.end_in_page; } ``` 它會將 `g_info.end_in_page` 設定為現在 heap 的結尾。 ##### `get_in_page` 這段程式碼是用來在 page 中分配新的記憶體區塊。它會在 `g_info.end_in_page` 指向的位置建立一個新的 metadata_t，並使用 size 設定其大小和其他屬性。然後它會將這個新的區塊插入到 g_info 的 list 中，並將 `g_info.end_in_page` 指向下一個可用的位置。 ##### `get_heap` 這段程式碼是用來從 heap 中分配新的區塊。它會檢查 `g_info.page_remaining` 是否足夠分配這個區塊，如果不足則使用 `get_new_page()` 分配更多的 page 。然後它會從這些 page 中使用 get_in_page() 分配區塊，並更新 `g_info.page_remaining` 的值。最後，它會回傳新分配區塊的指標。 ##### `split_block` 這個函是的功能是會將一個很大的記憶體區塊，切分成兩個比較小的區塊。可以看到他先將這個 node 移出了閒置的 list ，再來判斷它可不可以進行切割，如果可以的話，再進行分割，切完之後，再把切下來的空間 `new` 插入到閒置的 list 裡面。 #### `malloc` 可以看到在 malloc 的過程中，使用了 mutex 來對共享的資料進行保護，他的 critial section 是從決定分配的大小開始，到回傳之前 ```c pthread_mutex_lock(&g_info.mutex); if (size < SIZE_DEFAULT_BLOCK) size = SIZE_DEFAULT_BLOCK; size = ALIGN_BYTES(size) + META_SIZE; if (!g_info.page_size) g_info.page_size = getpagesize(); if ((tmp = search_freed_block(g_info.root_rbtree, size))) ptr = split_block(tmp, size); else ptr = get_heap(size); pthread_mutex_unlock(&g_info.mutex); ``` 在函式開始時，先檢查要分配的記憶體大小是否小於預設的區塊大小 **SIZE_DEFAULT_BLOCK** (32)，如果是，就把大小設為 **SIZE_DEFAULT_BLOCK**。然後使用 **ALIGN_BYTES** 巨集對記憶體大小進行記憶體位元對齊，並且加上一個 metadata_t 的大小，詳情可以看到上面的記憶體區段的圖。接下來，使用 `search_freed_block()` 函式在空閒記憶體區塊的紅黑樹中查找是否有足夠大的區塊，如果有就使用 `split_block()` 函式將該區塊切成兩個部分：一部分用於分配所需大小的記憶體，另一部分放回空閒記憶體塊的紅黑樹中，以便後續的分配使用。如果找不到足夠大的區塊，就使用 `get_heap()` 函式從作業系統中獲取一個新的記憶體區塊。 #### `free` 在進行 free 時候，同樣的也是要進行多執行緒的保護。接下來就進行一些檢查，確定是否為有效的指標，還有重複釋放的問題再來就是把要釋放的記憶體區塊前後嘗試連接成更大的區塊，結束後檢查這個區塊的下一個區塊是否存在，若是不存在的話，就要通過呼叫 brk() 調整 `break` 的位置; 若是存在的話，就將這個要是放的區塊放入空閒的 list 裡面。 #### `calloc` 這邊也是通過 `malloc()` 先進行記憶體配置，接下再將 `memset` 的動作用 mutex 鎖住 ### 測試可以從 [測驗題說明](https://hackmd.io/@sysprog/linux2023-quiz5#%E6%B8%AC%E9%A9%97-2) 看到編譯以及測試的方式也從 [〈你所不知道的 C 語言：動態連結器篇〉](https://hackmd.io/@sysprog/c-dynamic-linkage) 看到可以在 `malloc` 這個函式中加入 ```c sprintf(buf, "malloc called, size = %zu\n", size); write(2, buf, strlen(buf)); ``` 來確定動態連結庫有成功被載入並且使用 - malloc ```c void *malloc(size_t size) { metadata_t *tmp; void *ptr; char buf[32]; pthread_mutex_lock(&g_info.mutex); if (size < SIZE_DEFAULT_BLOCK) size = SIZE_DEFAULT_BLOCK; size = ALIGN_BYTES(size) + META_SIZE; if (!g_info.page_size) g_info.page_size = getpagesize(); if ((tmp = search_freed_block(g_info.root_rbtree, size))) ptr = split_block(tmp, size); else ptr = get_heap(size); sprintf(buf, "malloc called, size = %zu\n", size); write(2, buf, strlen(buf)); pthread_mutex_unlock(&g_info.mutex); return ptr ? (GET_PAYLOAD(ptr)) : NULL; } ``` - 編譯 ```shell $ gcc -O2 -Wall -Wextra -fPIC -I . -c alloc.c $ gcc -shared -o libmy_alloc.so alloc.o ``` - 測試 ```shell $ LD_PRELOAD=./libmy_alloc.so ls ``` 可以看到結果如實配置指定的空間: ```shell $ LD_PRELOAD=./libmy_alloc.so ls malloc called, size = 512 malloc called, size = 160 malloc called, size = 1056 malloc called, size = 64 ... ``` ### 用 mmap 替換 sbrk 先從 man page 以及 CSAPP 來學習 `brk`, `sbrk`, `mmap`, `munmap` 這幾個系統呼叫 #### sbrk ```c #include <unistd.h> void *sbrk(intptr_t increment); ``` `sbrk` 可以透過將 kernel 管理的 heap 指標上移或是下移來以此分配空間。因此 increment 可以是正, 負還有 0 ，0 就不配置空間, 大於 0 就配置空間, 小於 0 就釋放空間。如果成功的話，就會回傳舊的 `brk` 指標，如果出錯的話就會回傳 `-1` #### brk ```c #include <unistd.h> int brk(void *addr); ``` `brk` 使用的方式就是根據傳入的 `addr` 作為新的 heap 頂端指標，因此從舊的 `brk` 指標到新的 `addr` 距離就是我們所需要分配的空間。 #### mmap :::warning 搭配參照[第 11 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz11) :notes: jserv ::: ```c #include <sys/mman.h> void *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset); ``` 引數 `start` 通常被定義為 NULL， `length` 被定義為要分配的大小 `port` 被定義為描述新映射虛擬記憶體的訪問權限共有幾種，例如 - PORT_EXEC : Page 可以被執行 - PORT_READ : Page 可以被讀取 - PORT_WRITE: Page 可以被寫入 - PORT_NONE : Page 不可以被訪問 `flags` 指定映射對象的類型，映射的選項及是否可以共享 `fd` 是有效的檔案描述子，如果在 `flags` 有設定 `MAP_ANONYMOUS` ，就要把這個設成 `-1` `offset` 是要從檔案的哪裡開始映射，通常設為 `0` #### munmap ```c #include <sys/mman.h> int munmap(void *addr, size_t length); ``` 清除會從引數 `addr` 開始進行清除，並且從起點 `addr` 開始 `length` 的記憶體空間都會被釋放。 #### 著手進行修改首先先添加所需的標頭檔 `#include <sys/mman.h>` 再來需要修改的地方是配置記憶體的函式 `change_break` 原本是用來進行釋放記憶體 (移動 heap 指標) ，而我們需要將它變成 munmap 的方式進行釋放，修改如下 ```diff static inline void change_break(metadata_t *node) { size_t pages_to_remove; if (node->prev) { node->prev->next = NULL; g_info.last_node = node->prev; g_info.end_in_page = (void *) g_info.last_node + g_info.last_node->size; } else { g_info.end_in_page = g_info.last_node; g_info.last_node = NULL; } g_info.page_remaining += node->size; pages_to_remove = g_info.page_remaining / g_info.page_size; /* FIXME: sbrk is deprecated */ - brk((sbrk(0) - (pages_to_remove * g_info.page_size))); + munmap(node, (pages_to_remove * g_info.page_size)); g_info.page_remaining = g_info.page_remaining - (pages_to_remove * g_info.page_size); } ``` 以及 `get_new_pages` 這個函式需要改動將原本使用 sbrk 進行配置的部份都改成 mmap，改動如下 ```diff static size_t get_new_page(size_t size) { size_t pages = ((size / g_info.page_size) + 1) * g_info.page_size; /* FIXME: sbrk is deprecated */ - if (!g_info.end_in_page) { - if ((g_info.end_in_page = sbrk(0)) == (void *) -1) + if (!g_info.end_in_page) { + g_info.end_in_page = mmap(0, pages, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0); + if ((g_info.end_in_page == (void *) -1)) return (size_t) -1; g_info.first_block = g_info.end_in_page; } - if (sbrk(pages) == (void *) -1) { + if (mmap(0, pages, PROT_READ | PROT_WRITE, + MAP_PRIVATE | MAP_ANONYMOUS, -1, 0) == (void *) -1) { errno = ENOMEM; return (size_t) -1; } return pages; } ``` 接下來進行編譯 ```shell $ make rm -f libmy_alloc.so alloc.o gcc -O2 -Wall -Wextra -fPIC -I . -c alloc.c /usr/include/stdlib.h: In function ‘malloc’: alloc.c:347:5: warning: ignoring return value of ‘write’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 347 | write(2, buf, strlen(buf)); | ^~~~~~~~~~~~~~~~~~~~~~~~~~ gcc -shared -o libmy_alloc.so alloc.o ``` 可以正常的編譯，接著開始測試: ```shell $ make test LD_PRELOAD=./libmy_alloc.so ps aux malloc called, size = 80 malloc called, size = 512 malloc called, size = 4128 Segmentation fault (core dumped) make: *** [Makefile:14: test] Error 139 ``` 發現執行到一半的時候會產生 Segmentation fault。思考一下 bug 出現在哪！ :::info 在參考了 [quiz11](https://hackmd.io/@sysprog/linux2023-quiz11) 以及 [mmap-malloc](https://github.com/mdukat/mmap-malloc) 後，取消上面的修改，改成引入 mmap-malloc，並且用巨集讓 malloc 可以從 brk/sbrk 切換到 mmap。詳細程式碼在 [WangHanChi/rbtmalloc](https://github.com/WangHanChi/rbtmalloc) ::: 主要透過 `MMAP` 這個巨集決定要使用 brk/sbrk 或是 mmap 來分配記憶體。我將結構體 `malloc_t` 稍微做了修改 ```c typedef struct metadata { struct metadata *next, *prev; size_t size; #ifdef MMAP void *ptr; #else size_t free; #endif } metadata_t; typedef struct { metadata_t *last_node; size_t page_size; pthread_mutex_t mutex; #ifdef MMAP void *ptr; #else void *end_in_page; void *first_block; rbnode_t *root_rbtree; size_t page_remaining; #endif } malloc_t; ``` 主要都是將 mmap 所需要的結構成員獨立出來，避免不必要的定義。接著在 `malloc`, `realloc`, `free`, `calloc` 這些函式中可以看到都使用了 `define MMAP` 來決定要使用哪一種方式進行分配 ```c void *malloc(size_t size) { #ifdef MMAP return mmap_malloc(size); #else return brk_malloc(size); #endif } void free(void *ptr) { #ifdef MMAP mmap_free(ptr); #else brk_free(ptr); #endif } void *calloc(size_t nmemb, size_t size) { #ifdef MMAP return mmap_calloc(nmemb, size); #else return brk_calloc(nmemb, size); #endif } void *realloc(void *ptr, size_t size) { #ifdef MMAP return mmap_realloc(ptr, size); #else return brk_realloc(ptr, size); #endif } ``` 可以看到在執行測試 `make test ` 了之後，確實有成功動態載入並呼叫了 `ls` 這個命令 ```shell $ LD_PRELOAD=./libmy_alloc.so ls malloc(472) = 0x7fa4c46c2000 malloc(120) = 0x7fa4c4681000 malloc(1024) = 0x7fa4c467f000 free(0x7fa4c4681000) free(0x7fa4c467f000) free(0x7fa4c46c2000) free((nil)) malloc(5) = 0x7fa4c46c2000 free(0x7fa4c46c2000) ...... ``` 關於 rbtmalloc 更多的開發紀錄在 [rbtmalloc 開發紀錄](https://hackmd.io/@wanghanchi/linux2023-rbtmalloc) ! ### 引入 quiz4 的紅黑樹 --- ## 參考資料 - [linux]([torvalds/linux](https://github.com/torvalds/linux)) <s> - [自己擼了一個 malloc 內存分配器~](https://www.readfog.com/a/1650959933121859584) </s> :::warning 先閱讀權威材料，例如 CS:APP，[第 9 章](https://hackmd.io/@sysprog/CSAPP-ch9)提到如何建構記憶體配置器。 :notes: jserv ::: - [mmap-malloc](https://github.com/mdukat/mmap-malloc)