# CS:APP Malloc Lab > [mallocLab PDF](http://csapp.cs.cmu.edu/3e/malloclab.pdf) 本實驗希望做出一個動態記憶體分配器，我們需要用 C 語言實作 `malloc`、`free`、`realloc` 函式。目標是開發出正確、快速且記憶體碎片少的顯式分配器。 ## 背景知識 我們需要實作以下四個函式： * `mm_init`: 在呼叫 `mm_malloc` 與 `mm_free` 之前，需要先初始化，例如分配 heap 區域的空間 * `mm_malloc`: 分配並回傳指向一塊已分配區域的有效負載(payload)的指標。分配的區域要在 heap 內，並且不能和其他已分配區域重疊。而分配大小始終要是 8 bytes 對齊的 * `mm_free`: 釋放掉 `ptr` 指標指向的已分配區域空間。要確保 `ptr` 指向的空間是利用 `mm_malloc` 或 `mm_realloc` 分配過的空間，不然就會變成 UB * `mm_realloc`: 輸入 `ptr` 與 `size` 參數，回傳指向至少 `size` 大小的已分配記憶體空間的指標。對於輸入有以下條件： * `ptr` 為 NULL 時，等於 `mm_malloc(size)` * `size` 為 0 時，等於 `mm_free` * `ptr` 不為 NULL 時，要確保 `ptr` 指向的空間是利用 `mm_malloc` 或 `mm_realloc` 分配過的空間 ### 評分標準 以空間利用率與吞吐量作為評分標準。 * 空間利用率：使用 `mm_malloc` 與 `mm_realloc` 分配且並未被 `mm_free` 釋放的空間大小與 heap 大小的比值。目標希望減少碎片(fragmentation)的存在。公式如下： $$ U_k = \frac{max_{i\leq k}P_i}{H_k} $$ * 吞吐量：平均每秒可以完成多少筆請求 最後的總分就會統整成： $$ P = wU + (1 − w)min(1,\frac{T}{T_{libc}}) $$ ## Implict Free List 分配器需要靠一些資料結構來維護這些記憶體資料。會把記憶體空間切分成不同的組成，用來區分邊界以及區分分配塊或位分配塊。下圖是一個已配置或是空閒塊的結構。 * **Header**: 紀錄這個 block 的大小，包括 header、footer、payload 與 padding。因為記憶體是 8 bytes 對齊。因此 header 的低 3 位永遠是 0。所以我們利用最低位用來表示是否已分配 * **footer**: 當有一個 block 被釋放時，會想看前後有沒有能夠合併的空閒塊。但如果想要確認前面是否為空閒塊時，就會發現因為 `malloc` 的大小是不固定的，因此不知道要找多久才能找到 header。因此在每個 block 的最後放上 footer，它就是 header 的副本，一樣存放大小與是否分配。 * **Payload**: 真實存放資料的地方 * **Padding**: 因對齊而增加的區域。例如我 `malloc` 10 個 bytes，那它實際上會給我 24 bytes 的大小。因為 header 與 footer 各需要 4 bytes，而 payload 是我需要的 10 bytes。所以加起來是 $4+4+10=18$，再根據 8 bytes 對齊，因此需要給到 24 bytes，而 padding 就是 6 bytes ![image](https://hackmd.io/_uploads/SycLVWtrJe.png) ### Macros 課本與 lab 提供了我們一些方便的 Macros，因此涉及到記憶體，所以大多都是指標操作。以下說明： * `ALIGNMENT`: 8 bytes 對齊 * `ALIGN`: 向上取大於等於 `size` 的 8 bytes 對齊 * `SIZE_T_SIZE`: `size_t` 大小 * `WSIZE`: Word 大小(header 與 footer 也是 word size) * `DSIZE`: Double word 大小 * `CHUNKSIZE`: 可延伸 heap 的大小，4 KB * `PACK`: 將 `size` 與 `alloc` 資訊放入 word，通常用於 header 或 footer * `GET`: 讀取地址 `p` 的值 * `PUT`: 寫 `val` 進地址 `p` * `GET_SIZE`: 從 header 或 footer 中獲取 `size`，去掉低三位資訊 * `GET_ALLOC`: 從 header 或 footer 中獲取是否已分配 * `HDRP`: `bp` 是指向某 payload 區域，用來計算該 block 的 header address * `FTRP`: `bp` 是指向某 payload 區域，用來計算該 block 的 footer address。減去 8 bytes 是因為區塊的大小包含 header 和 footer 的 8 bytes。 * `NEXT_BLKP`: 計算下一個 block 的 payload 地址 * `PREV_BLKP`: 計算前一個 block 的 payload 地址 ```cpp /* single word (4) or double word (8) alignment */ #define ALIGNMENT 8 /* rounds up to the nearest multiple of ALIGNMENT */ #define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7) #define SIZE_T_SIZE (ALIGN(sizeof(size_t))) /* Basic constants and macros */ #define WSIZE 4 /* Word and header/footer size (bytes) */ #define DSIZE 8 /* Double words size (bytes) */ #define CHUNKSIZE (1 << 12) /* Extend heap size (4K bytes)*/ #define MAX(x, y) ((x) > (y)? (x) : (y)) /* Pack size and allocated bit into a word */ #define PACK(size, alloc) ((size) | (alloc)) /* Read and Write a word at address p */ #define GET(p) (*(unsigned int*)(p)) #define PUT(p, val) (*(unsigned int*)(p) = (val)) /* Get the size and allocated field from address p */ #define GET_SIZE(p) (GET(p) & ~0x7) #define GET_ALLOC(p) (GET(p) & 0x1) /* Compute address of its header and footer */ #define HDRP(bp) ((char *)(bp) - WSIZE) #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) /* Compute address of next and previous block */ #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) ``` ### `mm_init` 首先需要初始化 heap 空間。在課本 fig 9-44 有給出範例程式。我們就基於這個版本做解釋。 我們要先了解 Implict Free List 的形式。前面說到的 block 是作為普通塊，一般的分配塊與空閒塊會用上面的架構。但初始化 heap 時會用不同的架構。 1. Alignment padding: 為了對齊後面東西，全放 0 就好 2. Prologue block: 只有 header 與 footer。在初始化時創建，並且永不釋放 3. Epilogue block: heap 以這個 block 做結尾 會需要這兩個 block 是因為要消除合併時邊界條件。分配器會有一個全域指標 `heap_listp` 指向 Prologue 的 footer。 ```cpp= /* * mm_init - initialize the malloc package. */ int mm_init(void) { /* Create the initial empty heap */ if (heap_listp = mem_sbrk(4 * WSIZE) == (void *) - 1) return -1; PUT(heap_listp, 0); /* Alignment padding */ PUT(heap_listp + WSIZE, PACK(DSIZE, 1)); /* Prologue header */ PUT(heap_listp + 2 * WSIZE, PACK(DSIZE, 1)); /* Prologue footer */ PUT(heap_listp + 3 * WSIZE, PACK(0, 1)); /* Epilogue header */ heap_listp += (2 * WSIZE); /* Extend the empty heap with a free block of CHUNKSIZE bytes */ if (extend_heap(CHUNKSIZE/WSIZE) == NULL) return -1; return 0; } ``` ### 申請 heap 空間 在 `mm_init` 的第 7, 8 行中呼叫 `mem_sbrk`。其用意是向 kernel 申請輸入 size 大小的 heap 空間。我們知道作業系統會有一個指標指向 heap 的最上面地址。而在這裡就是使用 `mem_brk`。它會先去判斷你申請的大小是否超出範圍。若沒有則回傳回原本 heap 的指標。 ![Screenshot from 2024-12-25 19-13-22](https://hackmd.io/_uploads/HkrJFwtryg.png) ```cpp /* * mem_sbrk - simple model of the sbrk function. Extends the heap * by incr bytes and returns the start address of the new area. In * this model, the heap cannot be shrunk. */ void *mem_sbrk(int incr) { char *old_brk = mem_brk; if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) { errno = ENOMEM; fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n"); return (void *)-1; } mem_brk += incr; return (void *)old_brk; } ``` ### 初始化 heap 我們先用 `mem_sbrk` 向系統申請了 4 words 的空間，要放入前面講的初始化數值。第 9 ~ 12 行中，我們將其 `PUT` 進去。Alignment padding 放入 0，Prologue block 大小為 double word。而 Epilogue block 大小為 0。所以到第 13 行時 Implict Free List 就如下圖所示。 ![implict1(1)](https://hackmd.io/_uploads/H14Q6PYByx.png) ### `extend_heap` 在 `mm_init` 中的 16 行呼叫 `extend_heap`，作用是用來擴展 heap 空間。只會有兩個時候要用到該函式： 1. 初始化 heap 2. 當 `mm_malloc` 找不到適合的空閒塊時，為保持對齊，`extend_heap` 會向上捨入找到最接近 8 bytes 的空間 可以看到它實際上也是利用 `mem_sbrk` 函式獲取空間。接著它就初始化空閒塊與 Epilogue 的配置。 回顧剛剛 `mm_init` 時我們輸入的大小是 `CHUNKSIZE/WSIZE` 也就是 1KB 大小。現在來看實際上記憶體的配置是如何做的。 * `mm_init` 第 13 行後，就如剛剛圖片所示 ![implict1(1)](https://hackmd.io/_uploads/H14Q6PYByx.png) * `extend_heap` 到第 8 行後，配置了 1KB 大小的空閒塊。但很明顯這時候 Epilogue 就不應該放在這裡，而是空間的最後面。 ![implict2(1)](https://hackmd.io/_uploads/BknCwctH1x.png) * `extend_heap` 第 12 ~ 14 行，剛剛拿到的 `bp` 就是上圖的 `old_brk`。因此要做三件事： * 設置空閒塊 header: `HDRP` 剛好就是減去一個 word 大小，接著放入大小與配置位，這也剛好蓋過原本的 Epilogue * 設置空閒塊 footer: 與 header 雷同 * 設置新的 Epilogue: 從 `old_brk` 加上 1KB 到 `mem_brk` ，再用 `HDRP` 減 4 bytes，就可以獲得最後一個 word，就可以填上 Epilogue ![implict3](https://hackmd.io/_uploads/rk3UoctSyx.png) > 圖片藍色部份是已分配，灰色部份是未分配 ```cpp= static void *extend_heap(size_t words) { char *bp; int size; /* Allocate an even number of words to maintain alignment */ size = (words % 2)? (words + 1) * WSIZE: words * WSIZE; if ((long)(bp = mem_sbrk(size)) == -1) return NULL; /* Initialize free block header/footer and the epilogue header*/ PUT(HDRP(bp), PACK(size, 0)); /* Header */ PUT(FTRP(bp), PACK(size, 0)); /* Footer */ PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */ /* Coalesce if the previous block was free */ return coalesce(bp); } ``` ### `mm_free` 釋放記憶體的部份課本上也有給出範例。而從這邊也得知，為什麼 `free` 函式只須給入指標不用給大小，就是因為動態分配器利用 free list 在管理記憶體。 那釋放的部份很簡單，只須改變 header 與 footer 的分配位變成 0 即可。但是需要執行 `coalesce` 去合併可能的空閒塊。 ```cpp /* * mm_free - Freeing a block does nothing. */ void mm_free(void *bp) { size_t size = GET_SIZE(HDRP(bp)); PUT(HDRP(bp), PACK(size, 0)); PUT(FTPR(bp), PACK(size, 0)); coalesce(bp); } ``` ### `coalesce` 合併函式就是把前後如果有空閒塊的話可以合併成一個空閒塊。其目的就是為了減上記憶體碎片。有兩種情況會呼叫合併: 1. `extend_heap` 最後，因為擴展的空間實際上就是一個空閒塊，可能前面會有小塊的空閒塊 2. `mm_free` 最後，每當釋放一塊空間時就需要做合併 那合併就會有以下四種情況： 1. Case 1: 前後兩個都是已分配塊，就無須合併 2. Case 2: 後面那塊是空閒塊，後面塊與當前塊合併成一個空閒塊 3. Case 3: 前面那塊是空閒塊，前面塊與當前塊合併成一個空閒塊 4. Case 4: 前面與後面都是空閒塊，三個合併成一個空閒塊 ![coal1](https://hackmd.io/_uploads/HkWn0tqHJg.png) ```cpp /* * Coalesce free list */ void *coalesce(void *bp) { size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); /* previous block alloc bit */ size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); /* next block alloc bit */ size_t size = GET_SIZE(HDRP(bp)); /* the size of current block */ /* Case 1 */ if(prev_alloc && next_alloc){ return bp; /* do nothing */ } /* Case 2 */ else if(prev_alloc && !next_alloc){ size += GET_SIZE(HDRP(NEXT_BLKP(bp))); /* add the size of next block */ PUT(HDRP(bp), PACK(size, 0)); /* modify header */ PUT(FTRP(bp), PACK(size, 0)); /* modify footer */ } /* Case 3 */ else if(!prev_alloc && next_alloc){ size += GET_SIZE(HDRP(PREV_BLKP(bp))); /* add the size of previous block */ PUT(FTRP(bp), PACK(size, 0)); /* modify footer */ PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); /* modify header */ bp = PREV_BLKP(bp); /* change block pointer */ } /* Case 4 */ else{ size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); /* add the size of next and previous block */ PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0)); /* modify footer */ PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0)); /* modify header */ bp = PREV_BLKP(bp); /* change block pointer */ } return bp; } ``` ### `mm_malloc` 要分配記憶體空間，首先要先檢查 `size` 。要確認其是 8 bytes 對齊的。最小也需要 16 bytes。接著在 Free list 找到適合的 block，放入所需的空間。若是找不到可以放得下的 block ，就會呼叫 `extend_heap` 擴展新的空間。再將其放入。 ```cpp /* * mm_malloc - Allocate a block by incrementing the brk pointer. * Always allocate a block whose size is a multiple of the alignment. */ void *mm_malloc(size_t size) { size_t asize; size_t extendsize; char *bp; if(size == 0) return NULL; /* Adjust block size to include overhead and ailgnment reqs. */ if(size <= DSIZE) asize = 2 * DSIZE; else asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE); /* Search the free list for a fit */ if((bp = find_fit(asize)) != NULL){ place(bp, asize); return bp; } /* No fit found. Get more memory and place the block */ extendsize = MAX(asize, CHUNKSIZE); if((bp = extend_heap(extendsize / WSIZE)) == NULL) return NULL; place(bp, asize); return bp; } ``` #### `place` 當找到一塊空閒塊後，就可以執行 `place` 函式將其放入。而會有兩種情況： 1. 空閒塊減去要分配的塊的大小後還有兩個 `DSIZE`，這時就要分割。一塊變成已分配塊，另一塊則是新的空閒塊。 2. 若大小剛好只能放下分配塊，則不須分割。 ```cpp /* * place the block and split free block */ void place(void *bp, size_t asize) { size_t brk_size = GET_SIZE(HDRP(bp)); size_t remain_size = brk_size - asize; /* Split allocated block and free block if there are some remain space */ if(remain_size >= 2 * DSIZE) { PUT(HDRP(bp), PACK(asize, 1)); PUT(FTRP(bp), PACK(asize, 1)); bp = NEXT_BLKP(bp); PUT(HDRP(bp), PACK(remain_size, 0)); PUT(FTRP(bp), PACK(remain_size, 0)); } /* Not split */ else{ PUT(HDRP(bp), PACK(brk_size, 1)); PUT(FTRP(bp), PACK(brk_size, 1)); } } ``` ### `find_fit` 要從 Free list 找到適合的 block 放入，我一共實作了三個放置策略(placement policy): * First fit * Next fit * best fit ```cpp void *find_fit(FIT_ALGOR algor, size_t asize) { char* bp; switch (algor) { case FIRST_FIT: bp = first_fit(asize); break; case NEXT_FIT: bp = next_fit(asize); break; case BEST_FIT: bp = best_fit(asize); break; default: printf("Error: fit algorithm error.\n"); bp = NULL; break; } return bp; } ``` #### `first_fit` 從頭開始找到第一塊可以放置的 block。優點是它趨向將較大的空閒塊保留在後面，而缺點就是靠近 list 前面會留下較多碎片。 ```cpp static void *first_fit(size_t asize) { void *bp = heap_listp; /* pointer to Prologue footer */ size_t size; for (; (size = GET_SIZE(HDRP(bp))) > 0; bp = NEXT_BLKP(bp)) { if ((GET_ALLOC(HDRP(bp)) == 0) && size > asize) return bp; } return NULL; /* Can't find block */ } ``` #### `next_fit` 它是基於說上次已經在這裡找到匹配的 block 了，那很可能下一次就可以很快找到可匹配 block。其優點就是比 first fit 快速，但有研究表明空間利用率比較低。 而實作方面也比較複雜些，在找到可以的空閒塊後，需要檢查下一塊是否為 Epilogue block。這時就要重製 `next_listp`。 ```cpp static void *next_fit(size_t asize) { size_t size; void *bp = next_listp; void *tmp_listp; for (; (size = GET_SIZE(HDRP(bp))) > 0; bp = NEXT_BLKP(bp)) { if ((GET_ALLOC(HDRP(bp)) == 0) && size > asize) { tmp_listp = NEXT_BLKP(bp); if ((GET_SIZE(HDRP(tmp_listp)) == 0) && (GET_ALLOC(HDRP(tmp_listp)) == 1)) { next_listp = heap_listp; return PREV_BLKP(tmp_listp); } else { next_listp = tmp_listp; return PREV_BLKP(tmp_listp); } } } next_listp = heap_listp; return NULL; /* Can't find block */ } ``` :::danger 遇到問題：Checking mm_malloc for correctness, ERROR [trace 6, line 3926]: Payload (0xf4934918:0xf49389a1) overlaps another payload (0xf4937f58:0xf493992a) ::: #### `best_fit` 它會尋找整個 free list，檢查所有可放下的 block 中最小的 block。優點就是空間利用率一定最好，而缺點就是要跑比較久。 ```cpp static void *best_fit(size_t asize) { void *bp = heap_listp; /* pointer to Prologue footer */ void *best_bp = NULL; size_t min_size = 0, size; for (; (size = GET_SIZE(HDRP(bp))) > 0; bp = NEXT_BLKP(bp)) { if ((GET_ALLOC(HDRP(bp)) == 0) && size > asize) { if (min_size == 0 || (size < min_size)) { min_size = size; best_bp = bp; } } } return best_bp; } ``` ### `mm_realloc` 可參考背景知識提及要做的三件事。假設 `size` 不為 0，這時會出現兩種情況： 1. `size` 大於 `ptr` 的大小: 這代表需要分配一個 `size` 大小的塊，並將 `ptr` 裡的值複製到新的塊 2. `size` 小於 `ptr` 的大小: 一樣分配一個 `size` 大小的塊，但這時需要截斷 `ptr` 的值，抓 `size` 大小的值複製到新的塊 ```cpp /* * mm_realloc - Implemented simply in terms of mm_malloc and mm_free */ void *mm_realloc(void *ptr, size_t size) { void *oldptr = ptr; void *newptr; size_t copySize; newptr = mm_malloc(size); if (newptr == NULL) return NULL; size = GET_SIZE(HDRP(oldptr)); copySize = GET_SIZE(HDRP(newptr)); if (size < copySize) copySize = size; memcpy(newptr, oldptr, copySize-WSIZE); mm_free(oldptr); return newptr; } ``` ### 結果 #### first_fit ```cpp $ ./mdriver -t ./traces -V Results for mm malloc: trace valid util ops secs Kops 0 yes 93% 5694 0.006006 948 1 yes 91% 5848 0.005914 989 2 yes 91% 6648 0.008790 756 3 yes 90% 5380 0.006914 778 4 yes 66% 14400 0.000068213018 5 yes 93% 4800 0.005247 915 6 yes 91% 4800 0.004868 986 7 yes 55% 12000 0.073963 162 8 yes 51% 24000 0.248159 97 9 yes 26% 14401 0.036192 398 10 yes 34% 14401 0.001588 9069 Total 71% 112372 0.397710 283 Perf index = 43 (util) + 19 (thru) = 61/100 ``` #### best fit ```cpp $ ./mdriver -t ./traces -V Results for mm malloc: trace valid util ops secs Kops 0 yes 90% 5694 0.006993 814 1 yes 88% 5848 0.006650 879 2 yes 90% 6648 0.010481 634 3 yes 90% 5380 0.007325 734 4 yes 66% 14400 0.000085170414 5 yes 96% 4800 0.010682 449 6 yes 95% 4800 0.010338 464 7 yes 55% 12000 0.074601 161 8 yes 51% 24000 0.249368 96 9 yes 25% 14401 0.038243 377 10 yes 25% 14401 0.001639 8785 Total 70% 112372 0.416405 270 Perf index = 42 (util) + 18 (thru) = 60/100 ``` ## Segregated Free Lists Segregated Free Lists 是 Explicit Free Lists 的改良版本，我打算一起實作。它與 Implicit Free List 的差別為它將 payload 的前兩個 word 當作 `Next` 與 `Prev` 指標，以實作 double linked list 將 Free list 串起來。也就是說一個空閒塊最小有 16 bytes (4 words)。 > 這張圖有點錯，後面實作會把 `Next` 跟 `Prev` 的前後顛倒 ![Screenshot from 2025-01-09 20-33-50](https://hackmd.io/_uploads/ryxrfBaLyx.png) 而 Segregated 的核心思想就是將不同大小的 Free list 按 2 的幂比例分開。我們就用一個陣列來管理，每個元素就存放一個 Free list。 ![Screenshot from 2025-01-09 20-39-12](https://hackmd.io/_uploads/Sk-F7HTL1g.png) ### Macro 因為記憶體操作涉及許多複雜的指標操作，因此我參考 [CS:APP Malloc Lab 解題筆記](https://hackmd.io/@Chang-Chia-Chi/r13xrF0Vt#CSAPP-Malloc-Lab-%E8%A7%A3%E9%A1%8C%E7%AD%86%E8%A8%98)的操作並加以解釋。我們需要額外多做一些操作，用來獲取與放入 `Next` 與 `Prev` 指標。 ```cpp /* compute address of next and previous free block from a given pointer of a free block */ #define NEXT_PTR(bp) ((char *)(bp) + WSIZE) #define PREV_PTR(bp) ((char *)(bp)) #define GET_NEXT(bp) (*(char **)(NEXT_PTR(bp))) #define GET_PREV(bp) (*(char **)(bp)) #define PUT_PTR(p, ptr) (*(unsigned int *)(p) = (unsigned int)(ptr)) ``` #### `NEXT_PTR` & `PREV_PTR` 負責獲取 `Next` 與 `Prev` 的地址。 #### `GET_NEXT` & `GET_PREV` 負責獲得下一個空閒塊的地址。但這邊的指標操作有些複雜，考慮以下空閒塊。`bp` 指標為 `0x1000`。考慮執行: ```cpp #define NEXT_PTR(bp) ((char *)(bp) + WSIZE) ``` * 為什麼要先將 `bp` 強制轉型成 `(char *)`: 因為指標運算的步進單位是基於指標所指向型別的大小。若是指標型態為 `int` 的話，`bp + 1` 就會被編譯器翻譯成 `bp + 4`。因此為確保 `bp + WSIZE` 是正確運算須強制轉型。 這時就會獲得指標指向 `0x1004`，考慮執行: ```cpp #define GET_NEXT(bp) (*(char **)(NEXT_PTR(bp))) ``` * 可以看出它將剛剛獲得的指標強制轉型成指向 `char` 類型指標的指標。再對它 dereference。 * 那為什麼要那麼麻煩，不能用直接 dereference 嘛？如以下寫法 ```cpp #define GET_NEXT(bp) (*(NEXT_PTR(bp))) ``` * 答案是不行，因為剛剛知道 `NEXT_PTR(bp)` 回傳的指標是 `char` 型態的，若是直接 dereference ，編譯器會以為裡面是正常的數值，所以只取出 `char` 大小，也就是 1 byte 的數據。就會回傳 `0x48`，很明顯就有問題。 * 因此需要先強制轉型成指向 `char` 類型指標的指標。告訴編譯器：「這個地址上的值是另一個地址」，這樣在 dereference 時就會把整個 word 都抓出來了。也就是 `0x2048`。 ![freeBlock](https://hackmd.io/_uploads/HydodrTUJx.png) #### `PUT_PTR` 負責將 `ptr` 的內容放入 `p` 中。這次它將兩邊都強制轉型成 `unsigned int`: * 將 `p` 強制轉型為 `unsigned int*`，表示我們準備將地址存儲為一個 4-bytes 無符號整數。 * 將 `ptr` 強制轉型為 `unsigned int`，表示我們把指標值（記憶體地址）轉換為整數位元組表示。 * 執行 dereference `*(unsigned int *)(p)`，將整數值 `ptr` 存入 `p` 所指向的記憶體區域。 :::info 這裡學到許多記憶體底層的指標操作，詳細指標操作可以看： > [指標篇 筆記](https://hackmd.io/2Zd7d5cYTcy1X_OdPLciCA?view) ::: ### `mm_init` 初始化與前面差不多，增加兩件事: * 將 `extend_heap` 回傳的第一個空閒塊裡的 `prev` 與 `next` 初始化。 * 初始化 `seg_listp_arr` 陣列，大小如同下列所示。以二的幂為單位分塊。（最小的塊為 16 bytes)，一共 16 個元素。 $\left\{ 16\right\},\left\{ 17\sim 32\right\},\left\{ 33\sim 64\right\},\left\{ 65\sim 128\right\},\left\{ 129\sim 256\right\},\left\{ 257\sim 512\right\},\left\{ 513\sim 1024\right\},$ $\left\{ 1025\sim 2048\right\},\left\{ 2049\sim 4096\right\},\left\{ 4097\sim 2^{13} \right\},\left\{ 2^{13}+1\sim 2^{14} \right\},\left\{ 2^{14}+1\sim 2^{15} \right\},$ $\left\{ 2^{15}+1\sim 2^{16} \right\},\left\{ 2^{16}+1\sim 2^{17} \right\},\left\{ 2^{18}+1\sim 2^{19} \right\},\left\{ 2^{19}+1\sim \infty \right\}$ ```cpp /* * mm_init - initialize the malloc package. */ int mm_init(void) { /* Create the initial empty heap */ if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *) - 1) return -1; PUT(heap_listp, 0); /* Alignment padding */ PUT(heap_listp + WSIZE, PACK(DSIZE, 1)); /* Prologue header */ PUT(heap_listp + 2 * WSIZE, PACK(DSIZE, 1)); /* Prologue footer */ PUT(heap_listp + 3 * WSIZE, PACK(0, 1)); /* Epilogue header */ heap_listp += (2 * WSIZE); next_listp = heap_listp; for (int i = 0; i < 16; i++) { seg_listp_arr[i] = NULL; } /* Extend the empty heap with a free block of CHUNKSIZE bytes */ char *bp; if ((bp = extend_heap(CHUNKSIZE/WSIZE)) == NULL) return -1; /* Set NULL into prev and next pointer */ PUT_PTR(PREV_PTR(bp), NULL); PUT_PTR(NEXT_PTR(bp), NULL); return 0; } ``` #### `extend_heap` 一樣要在新空閒塊中設置 `prev` 與 `next`。 ```cpp static void *extend_heap(size_t words) { char *bp; int size; /* Allocate an even number of words to maintain alignment */ size = (words % 2)? (words + 1) * WSIZE: words * WSIZE; if ((long)(bp = mem_sbrk(size)) == -1) return NULL; /* Initialize free block header/footer and the epilogue header*/ PUT(HDRP(bp), PACK(size, 0)); /* Header */ PUT(FTRP(bp), PACK(size, 0)); /* Footer */ PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */ PUT_PTR(PREV_PTR(bp), NULL); /* Set NULL pointer to prev */ PUT_PTR(NEXT_PTR(bp), NULL); /* Set NULL pointer to next */ /* Coalesce if the previous block was free */ return coalesce(bp); } ``` ### `coalesce` 合併 free block 與前面雷同，採用 LIFO 策略，有四個 case: * Case 1: Free block 的前後都無空閒塊，單純將其插入 Free list 的開頭就好 ![Screenshot from 2025-01-10 15-19-15](https://hackmd.io/_uploads/r1fZqHA8ke.png) * Case 2: Free block 後面接著空閒塊，需要先將後面的空閒塊刪除，再將這兩個合併成一個新的空閒塊。 ![Screenshot from 2025-01-10 15-21-04](https://hackmd.io/_uploads/Hyeu5HRLyx.png) * Case 3: Free block 前面接著空閒塊，需要先將前面的空閒塊刪除，再將這兩個合併成一個新的空閒塊。 ![Screenshot from 2025-01-10 15-23-46](https://hackmd.io/_uploads/SylziS0Uye.png) * Case 4: Free block 前後都是空閒塊，就要將兩個都刪除後，再將這三個合併成一個新的空閒塊。 ![Screenshot from 2025-01-10 15-24-21](https://hackmd.io/_uploads/ByVEjBAIkx.png) ```cpp /* * Coalesce free list */ void *coalesce(void *bp) { size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp))); /* previous block alloc bit */ size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp))); /* next block alloc bit */ size_t size = GET_SIZE(HDRP(bp)); /* the size of current block */ void *prev_blk = PREV_BLKP(bp); void *next_blk = NEXT_BLKP(bp); /* Case 1 */ if(prev_alloc && next_alloc){ insert_blk(bp); return bp; } /* Case 2 */ else if(prev_alloc && !next_alloc){ size += GET_SIZE(HDRP(NEXT_BLKP(bp))); /* add the size of next block */ delete_blk(next_blk); /* delete next block*/ } /* Case 3 */ else if(!prev_alloc && next_alloc){ size += GET_SIZE(HDRP(PREV_BLKP(bp))); /* add the size of previous block */ delete_blk(prev_blk); /* delete prev block */ bp = prev_blk; /* change block pointer */ } /* Case 4 */ else{ size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp))); /* add the size of next and previous block */ delete_blk(next_blk); /* delete next block */ delete_blk(prev_blk); /* delete prev block */ bp = prev_blk; /* change block pointer */ } /* Case 2 ~ 4 free block update header and footer */ PUT(HDRP(bp), PACK(size, 0)); PUT(FTRP(bp), PACK(size, 0)); insert_blk(bp); /* After delteting free block, insert merged free block */ return bp; } ``` ### `insert_blk` & `delete_blk` 要從 Free list 中刪除一個 Free block，只要斷開 double linked list 的節點就好。因此找到前後的節點，並檢查是否存在。 * 若 Free list 為空: 直接將 head 設置為 NULL 就好 * 若要刪除的是**第一個節點**: 將第二個節點的 `prev` 指標設置為 NULL，並更新 head 為第二個節點 * 若要刪除的是**最後一個節點**: 將倒數第二個節點的 `next` 指標設置為 NULL * 若要刪除的是中間的話: 將前一個節點的 `next` 設置成 `bp`，將後一個節點的 `prev` 設置成 `bp` ```cpp static void delete_blk(void *bp) { size_t size = GET_SIZE(HDRP(bp)); int list_id = get_listId(size); void *next_blk = GET_NEXT(bp); void *prev_blk = GET_PREV(bp); /* Empty free list */ if (!prev_blk && !next_blk) { seg_listp_arr[list_id] = NULL; /* do nothing */ } /* First node */ else if (!prev_blk && next_blk) { PUT_PTR(PREV_PTR(next_blk), NULL); /* delete link */ seg_listp_arr[list_id] = next_blk; } /* Last node */ else if (prev_blk && !next_blk) { PUT_PTR(NEXT_PTR(prev_blk), NULL); /* delete link */ } else { PUT_PTR(PREV_PTR(next_blk), prev_blk); PUT_PTR(NEXT_PTR(prev_blk), next_blk); } } ``` 要插入空閒塊到 Free list 中，我們可以設計使其大小位於適合的位置。也就是說，越大的 block 會在 Free list 的越後面。透過判斷 `bp` 大小在 Free list 的哪個位置來實作。 * 若要插入的是第一個節點: 將 `bp` 節點的 `prev` 設置為 NULL，`next` 設置為下一個節點。檢查下一個節點是否存在(若不存在，代表原本為 empty list)將下一個節點的 `prev` 設置為 `bp`。最後更新 head 為 `bp`。 * 若不是第一個節點就操作 double linked list 操作即可，一樣要檢查下一個節點是否存在。 ```cpp static void insert_blk(void *bp) { size_t size = GET_SIZE(HDRP(bp)); int list_id = get_listId(size); void *root_blk = seg_listp_arr[list_id]; void *next_blk = root_blk; void *prev_blk = NULL; /* Find smallest block */ while (next_blk) { if (GET_SIZE(HDRP(bp)) < GET_SIZE(HDRP(next_blk))) break; prev_blk = next_blk; next_blk = GET_NEXT(next_blk); } /* First node */ if (next_blk == root_blk) { PUT_PTR(PREV_PTR(bp), NULL); PUT_PTR(NEXT_PTR(bp), next_blk); if (next_blk) { PUT_PTR(PREV_PTR(next_blk), bp); } seg_listp_arr[list_id] = bp; } else { PUT_PTR(PREV_PTR(bp), prev_blk); PUT_PTR(NEXT_PTR(bp), next_blk); PUT_PTR(NEXT_PTR(prev_blk), bp); if (next_blk) { PUT_PTR(PREV_PTR(next_blk), bp); } } } ``` 根據 block 的大小尋找插入與刪除要在哪個 Free list 中使用。而大小從最小的 16 bytes 開始，一共 16 個。 ```cpp static int get_listId(size_t size) { int i; /* 2^4 ~ 2^20 */ for (i = 4; i < 19; i++) { if (size <= (1 << i)) return i - 4; } return i - 4; } ``` ### Fit Algorithm 演算法的執行流程與之前相似，只是現在有 Free list 就可以比較方面做搜尋。注意到只須從大小大於該 block 的 Free list 開始搜尋即可。 ```cpp static void *first_fit(size_t asize) { void *bp; int list_id = get_listId(asize); for (; list_id < SEG_SIZE; list_id++) { bp = seg_listp_arr[list_id]; for (; bp != NULL; bp = GET_NEXT(bp)) { if (GET_SIZE(HDRP(bp)) >= asize) { return bp; } } } return NULL; } static void *best_fit(size_t asize) { void *bp; void *best_bp = NULL; size_t min_size = 0, size; for (; list_id < SEG_SIZE; list_id++) { bp = seg_listp_arr[list_id]; for (; bp != NULL; bp = GET_NEXT(bp)) { if ((size = GET_SIZE(HDRP(bp))) >= asize) { if (min_size == 0 || size < min_size) { min_size = size; best_bp = bp; } } } } return best_bp; } ``` ### `place` 在 `mm_malloc` 中找到適合的空閒塊後便要放入。如果配置一塊記憶體空間，那勢必要把這個空閒塊從 Free list 中移除。也會分兩種情況: * 配置後空閒塊不夠分割: 只要單純的將其從 Free list 中刪除即可 * 配置後空閒塊還可以分割(至少有 16 bytes): 如下圖所示，將其從 Free list 中刪除後需要將分割出來的 Free block 重新插入回 Free list ![Screenshot from 2025-01-10 21-10-17](https://hackmd.io/_uploads/rydHnqALJg.png) ```cpp /* * place the block and split free block */ void place(void *bp, size_t asize) { size_t blk_size = GET_SIZE(HDRP(bp)); size_t remain_size = blk_size - asize; delete_blk(bp); /* Split allocated block and free block if there are some remain space */ if(remain_size >= 2 * DSIZE) { PUT(HDRP(bp), PACK(asize, 1)); PUT(FTRP(bp), PACK(asize, 1)); bp = NEXT_BLKP(bp); PUT(HDRP(bp), PACK(remain_size, 0)); PUT(FTRP(bp), PACK(remain_size, 0)); insert_blk(bp); } /* Not split */ else{ PUT(HDRP(bp), PACK(blk_size, 1)); PUT(FTRP(bp), PACK(blk_size, 1)); } } ``` ### 結果 #### first_fit ```cpp $ ./mdriver -t ./traces -V Results for mm malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.000193 29487 1 yes 99% 5848 0.000181 32327 2 yes 99% 6648 0.000217 30622 3 yes 100% 5380 0.000184 29303 4 yes 66% 14400 0.000349 41237 5 yes 96% 4800 0.000528 9093 6 yes 95% 4800 0.000532 9021 7 yes 55% 12000 0.007032 1706 8 yes 51% 24000 0.026313 912 9 yes 31% 14401 0.039348 366 10 yes 30% 14401 0.001904 7562 Total 75% 112372 0.076782 1464 Perf index = 45 (util) + 40 (thru) = 85/100 ``` #### best_fit ```cpp $ ./mdriver -t ./traces -V Results for mm malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.000267 21326 1 yes 99% 5848 0.000255 22933 2 yes 99% 6648 0.000325 20474 3 yes 100% 5380 0.000246 21861 4 yes 66% 14400 0.000281 51264 5 yes 96% 4800 0.001041 4612 6 yes 95% 4800 0.000856 5606 7 yes 55% 12000 0.007069 1698 8 yes 51% 24000 0.026433 908 9 yes 31% 14401 0.038652 373 10 yes 30% 14401 0.001979 7275 Total 75% 112372 0.077405 1452 Perf index = 45 (util) + 40 (thru) = 85/100 ``` :::success First fit 的速度確實比 Best fit 還快一點。但是記憶體利用率差不多。因此整體的分數是一樣的。 ::: ## Virtual memory 筆記 > [【CSAPP录播课】9.2 地址翻译](https://www.bilibili.com/video/BV1SL411f79i/?spm_id_from=333.1391.0.0&vd_source=136f2593873d8d8ac2205e55686669d6) ### Page table 記憶體(memory)作為磁碟(disk)的緩存，使用 page table 來管理。下圖顯示 Physical memory 是記憶體，而 Virtual memory 是磁碟。而記憶體的一個儲存單位就是 Page frame，裡面會存放磁碟中 swap 過來的數據。而 page table 則是會記錄兩者之間的狀態。 * 未分配: VM 還未分配到 page table 裡 (PTE0, PTE5) * 緩存的: 已經在記憶體中分配一個 page (PTE1, PTE2, PTE7) * 未緩存的: 還未緩存到記憶體中 (PTE4, PTE6) Page table entry 由對應的物理地址與一個 valid bit 組成。物理地址就是記憶體中實際的初始地址，而若 valid bit 為 1，代表記憶體中對應的物理地址緩存了該虛擬頁。 ![image](https://hackmd.io/_uploads/H1MhjqHNkx.png) ### Virtual address 從 CPU 產出的 Virtual address 是由 Virtual page number(VPN) 與 Virtual page offset(VPO) 組成。 * VPN: 用於指示在 Page table 的哪個 entry * VPO: 要娶的數據是該地址加上 offset ![image](https://hackmd.io/_uploads/HyusMoSVJe.png) 假設 page size 為 4KB，page table 如下表所示。VPN 是 3，VPN 是 0x200，那其對應的位置應該是 VP3 再位移 0x200，也就是記憶體 0x3200 的位置。 ``` |-------| 0x0000 | VP0 | |-------| 0x1000 | VP1 | |-------| 0x2000 | VP2 | |-------| 0x3000 | VP3 | |-------| 0x4000 | VP4 | |-------| 0x5000 ``` ### Address translation 首先，在控制暫存器中有一個 Page Table Base Register(PTBR)用於指向 Page table 所在位置。接著就用 VPN 查詢對應的 Page table entry，若 valid bit 為 1，則可以直接使用 Physical page number，而虛擬與物理的偏移量是一樣的。因為 page size 一樣大。 ![image](https://hackmd.io/_uploads/HkL-s6BNkg.png) #### page hit 1. CPU 產出 Virtual address 2. MMU 計算出 PTEA: `PTEA = PTBR + (VPN * page size)` 3. 從 page table 中找出 PTE 回傳至 MMU 4. MMU 由上面方法算出 PA 5. 從記憶體抓取資料 ![image](https://hackmd.io/_uploads/Hkv4ATr4ke.png) #### Page fault 1~3. 與 page hit 一樣 4. 當回傳的 PTE 的 vaild bit 是 0 時，代表資料沒有緩存在記憶體，就會觸發 page fault exception。handler 就會負責選出一個記憶體中要被替換的 page ，稱作 victim page。 5. 從記憶體中將 victim page 放到磁碟 6. 將需要的資料 swap 回記憶體 7. CPU 要重新發送 VA ![image](https://hackmd.io/_uploads/Hk6PAaBN1e.png) #### Cache in VM 快取也是可以存放 PTE 的，若發生 cache miss，再去記憶體查詢 page table 即可。 ![image](https://hackmd.io/_uploads/BJ9Of0rEke.png) ### Translation Lookaside Buffer(TLB) 可以發現到每次都需要去記憶體裡的 page table 找 PTE 回到 MMU，產生 PA 後再去記憶體取資料，這樣每次都需要兩輪的時間(記憶體非常耗時)。因此我們可以在 CPU chip 內建立一個小小的 buffer 用來緩存 PTE，稱作 TLB。 在 CPU 產生 VA 後，會先將 VA 傳給 TLB。而 TLB 本身就是一個緩存機制，因此它的架構與 Cache 類似。因此我們可以將 VA 裡面的 VPN 拆分成 tag 與 index 位(位元數根據 n-way assocativity)。 > [CS:APP Cache Lab](https://hackmd.io/@Appmedia/r1MmKyjh0) ![image](https://hackmd.io/_uploads/Syq9IRH41e.png) #### TLB hit 1. CPU 產生 VA 2. MMU 會先將 VA 中的 VPN 丟到 TLB 裡尋找是否有緩存 PTE 3. TLB 回傳 PTE 給 MMU，就可以直接拿到 PA 4. 直接拿 PA 去記憶體裡抓資料 ![image](https://hackmd.io/_uploads/H1VlPASNyx.png) #### TLB miss 當在 TLB 中找不到緩存的 PTE 時，代表該 PTE 仍存放在記憶體裡的 page table。 3. 如同上面計算 PTEA 後，發送給記憶體尋址 4. 記憶體從 page table 中找到 PTE 後，要回傳給 MMU 與 TLB。前者要計算 PA，而後者因區域性，需要緩存到 TLB 5. 直接拿 PA 去記憶體裡抓資料 ![image](https://hackmd.io/_uploads/Bkh39g_Nke.png) ### Example 我們現在來模擬一次 VM 的運作方式。首先給出以下假設: * Virtual address 有 14 位長 * Physical address 有 12 位長 * Page size 是 64 bytes * TLB 是 4-way assocative，有 16 個 PTE * L1 d-cache 是 direct-mapped，line 大小為 4 bytes 基於上面假設，Virtual address 有 14 個 bits，Physical address 有 12 個 bits。而因 page size 為 64 bytes，所以 VPO 與 PPO 都是 6 bits。 ![image](https://hackmd.io/_uploads/H1SoZZ_Vkg.png) 假設 CPU 產生一個 VA 為 `0x03D4`。因為 TLB 是 4-way，因此 index 佔兩個 bits。這樣我們就可以拿 index 與 tag (VPN)給 TLB。 ![image](https://hackmd.io/_uploads/r1R7zWuNye.png) 下圖是目前 TLB 的狀態，因為 index 為 3，所以去 set3 尋找，而因 tag 是 3，所以找到一樣的數據，即是紅框的位置。接著檢查它的 vaild bit ，若為 1 則代表其數據確實存在記憶體中。因此 `0D` 就是我們要的 PPN。 ![image](https://hackmd.io/_uploads/B1zpzWOE1g.png) 這時候回到 MMU 將 PPN 與 PPO(與 VPO 一樣) 組合起來就是 PA 了。就可以向記憶體直接尋址抓取資料。 ![image](https://hackmd.io/_uploads/SkoFQ-dN1g.png)