# 2020q3 Malloc Lab
contributed by < `zhu849` >
## 準備作業
### 參考資料
* 參考 [2018q3 Malloc Lab](https://hackmd.io/@Ji0m0/SkCiB4QGN)，進行 CS:APP 的 [Malloc Lab](http://csapp.cs.cmu.edu/3e/labs.html)
* [Lab Statement](http://csapp.cs.cmu.edu/3e/malloclab.pdf)
* [CS:APP 課程連接](https://www.cs.cmu.edu/afs/cs/academic/class/15213-f16/www/schedule.html), [CS:APP 課程錄影](https://scs.hosted.panopto.com/Panopto/Pages/Sessions/List.aspx#folderID=%22b96d90ae-9871-4fae-91e2-b1627b43e25e%22&sortColumn=0&sortAscending=true)
* 詳讀 CS:APP 第九章 - Virtual memory
* [第九章 - Virtual memory 閱讀筆記](https://hackmd.io/U8vreACBQ6u0VCyddNKWtg)
* [CS:APP 第 9 章重點提示和練習](https://hackmd.io/@sysprog/CSAPP-ch9?type=view)
### Lab Description
Students implement their own versions of **malloc**, **free**, and **realloc**. This lab gives students a clear understanding of data layout and organization, and requires them to evaluate different trade-offs between space and time efficiency. One of our favorite labs. When students finish this one, they really understand pointers!
In this lab, students write their own storage allocator, in particular implementations of the malloc, free, and realloc functions. A trace-driven driver (mdriver) evaluates the quality of the student's implementation in terms of space utilization and throughput.
### 討論
以下內容可以用 [Lab Statement](http://csapp.cs.cmu.edu/3e/malloclab.pdf) 輔助討論
* 在實作中會需要建構一個 **realloc** 的功能，既然如此 **realloc** 和直接組合 **malloc** 及 **free** 功能的差異為何
* 在 Heap Consistency Checker 提到 `Dynamic memory allocators are notoriously tricky beasts to program correctly and efficiently. ... You will find it
very helpful to write a heap checker that scans the heap and checks it for consistency.` 如何得知製作出來的 checker 為檢測所需的功能提供正確性及有效性
* 在 Support Routines 提到 **void \*mem sbrk(int incr)** 這個 function 的使用方法及其意義
* 在 The Trace-driven Driver Program 提到 `The driver program mdriver.c in the malloclab-handout.tar distribution tests your mm.c package for correctness, space utilization, and throughput. ` 這個 drive 執行的過程做了哪些檢查，並指出是否有需要修改或是誤判的狀況
* 在 Evaluation 提到`The driver program summarizes the performance of your allocator by computing a performance index, P` $P = wU+(1-w)min(1,\dfrac{T}{T_{libc}})$ 的由來與意義
* 在 hint 中提到 `Use a profiler. You may find the gprof tool helpful for optimizing performance.` 利用 **gprof** 分析 execution branch(if/else, switch, goto, function call, etc.)，並進一步優化效能
## 待做事項
- [x] 觀看 CMU 開放式課程
- [x] 詳讀 CS:APP 第九章 - [詳讀筆記](https://hackmd.io/U8vreACBQ6u0VCyddNKWtg)
- [ ] 設計 malloc, free, realloc 函式
- [ ] 設計其他函式
- [ ] 設計 find_fit 函式
- [ ] 設計 place 函式
- [ ] 設計 heap_check 函式
- [ ] 利用 GDB, Valgrind 檢測當前版本的記憶體使用狀況
- [ ] 利用 gprof 分析效能狀況
- [ ] 分析自定義的函式與 C lib 提供函式的效能差異
## 實作過程
### memlib.c
malloc lab 使用了 memlib.c package 提供一個記憶體系統的模型，模型的目的是允許我們不干涉已存在的系統上的 malloc package 執行 allocator
> A module that simulates the memory system. Needed because it allows us to interleave calls from the student's malloc package with the system's malloc package in libc.
能夠呼叫的功能有以下幾種:
#### **void mem_init(void)**
> initialize the memory system model
* 會根據 config.h 中的 MAX_HEAP 向系統要一塊實體空間，並用 *mem_start_brk* 指標紀錄
* *\*mem_max_addr* 指標會指向 HEAP 最大的合法位址
* *\*mem_brk* 會指向目前開發者自定義 heap 要求的最大可使用合法位址
#### **void mem_deinit(void)**
> free the storage used by the memory system model
* 將向系統需求的空間完全釋放
#### **void mem_reset_brk()**
> reset the simulated brk pointer to make an empty heap
* 將 *\*mem_brk* 重新指向 *\*mem_start_brk*，表示開發者釋放自定義的 heap 空間
#### **void \*mem_sbrk(int incr)**
> 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.
* 開發者透過呼叫 mem_sbrk 並傳入一個 incr 大小向模擬系統要求更多的 heap 空間
* 檢查開發者是否呼叫位址在合法範圍內，並更新 *mem_brk* 指標指向目前開發者自定義 heap 要求的最大可使用合法位址
* 回傳的 (void*)old_brk 指向的是舊的 mem_brk 位址
#### **void \*mem_heap_lo()**
> return address of the first heap byte
* 回傳目前開發者所宣告的 heap 空間初始位置
#### **void \*mem_heap_hi()**
> return address of last heap byte
* 回傳目前開發者所宣告的 heap 空間最大合法位址
#### **size_t mem_heapsize()**
> returns the heap size in bytes
* 回傳目前開發者所宣告的 heap 空間大小
#### **size_t mem_pagesize()**
> returns the page size of the system
* 回傳系統的 page size
### macro & constants define
首先在開始實作前定義一些會用到的 macro 和常數值
```c=
/*Basic constants and macros */
#define WSIZE 4 /*word and header/footer size (bytes) */
#define DSIZE 8 /*Double word size (bytes) */
#define CHUNKSIZE (1<<12) /*extend heap by this amount (bytes) */
#define MAX(x,y) ((x) > (y) ? (x) : (y))
/*Pack a 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))
/*read the size, allocated fields from address p */
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
/*Given block ptr bp, compute address of its header and footer */
#define HDRP(bp) ((char *)(bp) - WSIZE)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/*Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
#define ALIGNMENT 8 /* single word (4) or double word (8) alignment */
/* rounds up to the nearest multiple of ALIGNMENT */
#define ALIGN(size) (((size) + (ALIGNMENT-1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
```
* line 2: 定義一個 word 的大小，目前設定為 4byte = 1 word
* line 3: 定義 word alignment，目前設定為 8byte = 2 word (Double word alignment)
* line 4: 宣告 heap 所需要的空閒區塊大小，目前使用的是 $2^{12}$ bytes
* line 9: 將 allocated bit 併到 size bit 上，這裡因為是 8 byte aligned 所以每個區塊的後3位 bit 必為 0，這些 bit 可以被稱為 spare bit，我們用最後1個 bit 來記錄「區塊是否已經被配置」
* line 12: 從 p address 讀出資料，將 p address 轉型成 (unsigned int\*) 再取該指標指向的內容。這裡的強制轉型很重要，因為 p 原本會是一個 (void*) 型態的指標，不能夠直接進行使用
* line 13: 從 p address 寫入資料
* line 16: 利用 bitwise operation 將 spare bit 設為 0 並取其位址當作 size(單位是 byte)，因為這裡是 double-word aligned 所以後3個 bits 必須被設為 0 才是正確的位址
* line 17: 拿取 allocated bit
* line 20: 給予 block 的指標計算其 header 位址，因為指向位址只需要 1byte 所以用 char 指標指向
* line 21: 給予 block 的指標計算其 footer 位址
* line 24: 給予 block 的指標計算其下一個 block 位址
* line 25: 給予 block 的指標計算其上一個 block 位址
* line 27: 同 line 3 效果
* line 30:將傳入的 size 區塊補齊最小可容納大小的區塊大小
* line 32: size_t 型態的大小，根據不同系統會有差異
### Global variable
```c=
static char *heap_listp;
```
### Function predeclare
```c=
static void *extend_heap(size_t words);
static void *coalesce(void *bp)
static void *find_fit(size_t asize);
static void place(void *bp, size_t asize);
```
### int mm_init(void);
#### 函式敘述
> Before calling **mm_malloc** **mm_realloc** or **mm_free**, the application program (i.e.,the trace-driven driver program that you will use to evaluate your implementation) calls **mm_init** to perform any necessary initializations, such as allocating the initial heap area. The return value should be -1 if there was a problem in performing the initialization, 0 otherwise.`
##### v1
```c=
int mm_init(void)
{
return 0;
}
```
##### v2
```c=
int mm_init(void) {
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1; // failure create heap space
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1 * 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;
}
```
* 利用 *mem_sbrk* 跟系統要求4個 word (16byte)的空間
* Q:強轉成(void\*)的用意?
* 參考 implicit free list 固定格式做初始化
* 其中必然存在的區塊為：
* Alignment padding - Q:為什麼一定要padding?
* prologue block - 一種特殊區塊由一個 header 和 footer 組成，heap 初始化時會宣告，並且永遠不會釋放掉，prologue block 之後存放的區塊才是一般區塊
* Epilogue block - heap 會利用一個 Epilogue block 的特殊區塊當作區塊的結尾，是一個 size 為 0 的已配置區塊，且只有一個 header 組成
```graphviz
digraph structs {
node [shape=record];
struct [label="{index|1st word(Alignment padding)|2nd word(prologue block header)|3th word(prologue block footer)|4th word(Epilogue block)}|{31|0|0|0|0}|{30|0|0|0|0}|{29|0|0|0|0}|{28|0|0|0|0}|{...|0|0|0|0}|{3|0|1|1|0}|{2|0|0|0|0}|{1|0|0|0|0}|{0|0|1|1|1}}"];
}
```
* prologue block 和 Epilogue block 其用處為合併時當作邊界條件的判斷依據
* 這裡宣告完後會將一個全域變數 \*heap_listp 指向 prologue block
```graphviz
digraph structs {
node [shape=record];
heap_listp[shape=plaintext,fontcolor=blue];
struct [label="{P(0/0)}|{H(8/1)}|{<start>F(8/1)}|{E(0/1)}"];
heap_listp->struct:start
}
```
* 之後用 extend_heap 宣告一個初始的閒置區塊
### static void *extend_heap(size_t words)
#### 函式敘述
> Extends the heap with a new free block
##### v1
```c=
static void *extend_heap(size_t words) {
char *bp;
size_t size;
/* Allocate an even number rds to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL; // failure to request more space
/* Initialize free block header/footer and the epilogue header*/
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
/* Coalesce if the previous block was free */
return coalesce(bp);
}
```
* extend_heap 會在兩種狀況下被使用：
* 當 heap 被初始化時
* 當 mm_malloc 不能找到合適的區塊時
* 為了保持 word-aligned 的問題，所以輸入 word 大小時要取至 2 的倍數才是實際向系統要求的 byte 空間大小
* 原本的區塊狀況
```graphviz
digraph structs {
node [shape=record];
heap_listp[shape=plaintext,fontcolor=blue];
struct [label="{P(0/0)}|{H(8/1)}|{<heap_loca>F(8/1)}|{E(0/1)}"];
heap_listp->struct:heap_loca
}
```
* 呼叫 extend_heap(6)
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P(0/0)}|{H(8/1)}|{F(8/1)}|{E(0/1)}|<bp_loca>|||||"];
bp->struct:bp_loca
}
```
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P(0/0)}|{H(8/1)}|{F(8/1)}|a=0|<bp_loca>|||||a=0|E(0/1)"];
bp->struct:bp_loca
}
```
* 之後執行 coalesce(bp)
### static void *coalesce(void *bp)
#### 函式敘述
> Uses boundary-tag coalescing to merge it with any adjacent free blocks in constant time.
##### v1
```c=
static void *coalesce(void *bp) {
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc) /* Case 1 */
return bp;
else if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
} else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
} else { /* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
return bp;
}
```
* 將 bp 所指向區塊的前一個區塊之 footer 的 allocated bit 指派給 prev_alloc
* 將 bp 所指向區塊的下一個區塊之 header 的 allocated bit 指派給 next_alloc
* 將 bp 所指向區塊的大小指派給 size
* Case 1：先檢查 prev_alloc 和 next_alloc 是否為 ture，若皆為 true 則前後區塊都是已配置區塊，不需要做合併，並傳回原 bp 所指向的位址當作閒置區塊的指標即可
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(8/1)}|...|{F(8/1)}|{<bp_loca>H(16/0)}|..|{F(16/0)}|{H(16/1)}|...|{F(16/1)}|..."];
bp->struct:bp_loca
}
```
* Case 2：若 prev_alloc 為 true 而 next_alloc 為 false，則需要將目前的閒置區塊和下一個區塊(也是閒置區塊)做合併
1. 將下一個區塊的大小加到 size
2. 重設區塊的 header 和 footer
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(8/1)}|...|{F(8/1)}|{<bp_loca>H(16/0)}|..|{F(16/0)}|{H(16/0)}|...|{F(16/0)}|..."];
bp->struct:bp_loca
}
```
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(8/1)}|...|{F(8/1)}|{<bp_loca>H(32/0)}|..|{F(16/0)}|{H(16/0)}|...|{F(32/0)}|..."];
bp->struct:bp_loca
}
```
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(8/1)}|...|{F(8/1)}|{<bp_loca>H(32/0)}|..|...|...|...|{F(32/0)}|..."];
bp->struct:bp_loca
}
```
* Case 3：若 prev_alloc 為 false 而 next_alloc 為 true，則需要將目前的閒置區塊和上一個區塊(也是閒置區塊)做合併
1. 將上一個區塊的大小加到 size
2. 重設區塊的 header 和 footer
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(8/0)}|...|{F(8/0)}|{<bp_loca>H(16/0)}|..|{F(16/0)}|{H(16/1)}|...|{F(16/1)}|..."];
bp->struct:bp_loca
}
```
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(24/0)}|...|{F(8/0)}|{<bp_loca>H(16/0)}|..|{F(24/0)}|{H(16/1)}|...|{F(16/1)}|..."];
bp->struct:bp_loca
}
```
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{<bp_loca>H(24/0)}|...|...|...|..|{F(24/0)}|{H(16/1)}|...|{F(16/1)}|..."];
bp->struct:bp_loca
}
```
* Case 4：若 prev_alloc 和 next_alloc 皆為 true，則需要將目前的閒置區塊和上一個區塊(也是閒置區塊)以及下一個區塊(也是閒置區塊)做合併
1. 將下一個區塊和下一個區塊的大小加到 size
2. 重設區塊的 header 和 footer
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(8/0)}|...|{F(8/0)}|{<bp_loca>H(16/0)}|..|{F(16/0)}|{H(16/0)}|...|{F(16/0)}|..."];
bp->struct:bp_loca
}
```
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{H(32/0)}|...|{F(8/0)}|{<bp_loca>H(16/0)}|..|{F(16/0)}|{H(16/0)}|...|{F(32/0)}|..."];
bp->struct:bp_loca
}
```
```graphviz
digraph structs {
node [shape=record];
bp[shape=plaintext,fontcolor=blue];
struct [label="{P}|{H}|{F}|{<bp_loca>H(32/0)}|...|{F(8/0)}|{<bp_loca>H(16/0)}|..|{F(16/0)}|{H(16/0)}|...|{F(32/0)}|..."];
bp->struct:bp_loca
}
```
### void *mm_malloc(size_t size);
#### 函式敘述
> The **mm_malloc** routine returns a pointer to an allocated block payload of at least size bytes. The entire allocated block should lie within the heap region and should not overlap with any other allocated chunk.
> We will comparing your implementation to the version of malloc supplied in the standard C library(libc). Since the libc malloc always returns payload pointers that are aligned to 8 bytes, your malloc implementation should do likewise and always return 8-byte aligned pointers.
##### v1
```c=
void *mm_malloc(size_t size)
{
int newsize = ALIGN(size + SIZE_T_SIZE);
void *p = mem_sbrk(newsize);
if (p == (void *)-1)
return NULL;
else {
*(size_t *)p = size;
return (void *)((char *)p + SIZE_T_SIZE);
}
}
```
* line 3：將想要要求的空間 size，傳入做對齊，對齊後的區塊大小指派到 newsize
* line 4：利用 mem_sbrk() 要求 newsize 大小的空間
* line 8：將 size 寫入 p 所指向的位址內
* line 9：傳回可以寫入 payload 的位址
##### v2
```c=
void *mm_malloc(size_t size) {
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* Ignore spurious requests */
if (size <= 0)
return NULL;
/* Adjust block size to include overhead and alignment 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;
}
```
* line 7：檢查要求大小是否合法
* line 11-12：若要求大小小於兩個 word，則至少需要有 4 個 word 的大小，其中2個 word 是為了補齊，另外2個 word 是為了擺放 header 和 footer
* line 14：若要求大小大於2個 word，會將 size 加上 header 和 footer 的空間，並且將 payload 空間對齊
* line 18：這裡需要撰寫一個 find_fit 的函式找到空閒區塊(可以實作不同演算法)
* line 19, 27：找到適當區塊後，放入並切割出多餘的部分放回閒置空間列表
* line 23：沒有合適的閒置空間，用 MAX 確認要額外要求的記憶體空間，利用 extend_heap 拿到新的記憶體區塊並放入
### static void *find_fit(size_t asize)
#### 函式敘述
> Implement a find_fit function for the simple allocator described in Section 9.9.12. Your solution should perform a first-fit and next-fit search of the implicit free list.
```c=
static void *find_fit(size_t asize)
{
char *bp = heap_listp;
size_t alloc;
size_t size;
while (GET_SIZE(HDRP(NEXT_BLKP(bp))) > 0) {
bp = NEXT_BLKP(bp);
alloc = GET_ALLOC(HDRP(bp));
if (alloc) continue;
size = GET_SIZE(HDRP(bp));
if (size < asize) continue;
return bp;
}
return NULL;
}
```
* 這裡可以有多種作法(best-fit, first-fit, next-fit)，這裡採用的是 first-fit
* line 6 - 11：這裡將 bp 指向 heap_listp，逐一找尋區塊
* 先確認其 allocated bit，若已配置則往下一個區塊尋找，否則拿該區塊的 size
* 若該區塊的 size 小於要求的 size 則往下一個區塊尋找，否則直接回傳該區塊的起始位址
### static void place(void *bp, size_t asize)
#### 函式敘述
> Implement a place function for the example allocator. Your solution should place the requested block at the beginning of the free block, splitting only if the size of the remainder would equal or exceed the minimum block size.
```c=
static void place(void *bp, size_t asize)
{
size_t size = GET_SIZE(HDRP(bp));
if ((size - asize) >= (2*DSIZE)) {
PUT(HDRP(bp),PACK(asize,1));
PUT(FTRP(bp),PACK(asize,1));
PUT(HDRP(NEXT_BLKP(bp)),PACK(size - asize,0));
PUT(FTRP(NEXT_BLKP(bp)),PACK(size - asize,0));
} else {
PUT(HDRP(bp),PACK(size,1));
PUT(FTRP(bp),PACK(size,1));
}
}
```
* 拿到該閒置區塊的大小指派給 size，確認該閒置區塊在配置 asize 後是否還有空間
* 若仍有空間則需要做閒置區塊的切割
1. 將目前要求的空間區塊的 header 和 footer 的 allocated bit 設為 1
2. 計算閒置區塊中沒被配置的區塊的 header 和 footer 的 allocated bit 設置為 0
* 否則直接將該區塊直接的 header 和 footer 的 allocated bit 設為 1
### void mm_free(void *ptr);
#### 函式敘述
> The **mm_free** routine frees the block pointed to by ptr. It returns nothing. This routine is only guaranteed to work when the passed pointer (ptr) was returned by an earlier call to **mm_malloc** or **mm_realloc** and has not yet been freed.
##### v1
```c=
void mm_free(void *ptr)
{
}
```
##### v2
```c=
void mm_free(void *ptr) {
size_t size = GET_SIZE(HDRP(ptr));
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
```
* line 3：拿到區塊的大小
* line 5,6：將區塊的 allocated bit 設為 0
* line 7：將閒置區塊和鄰近區塊做合併
### void *mm_realloc(void *ptr, size_t size);
#### 函式敘述
> The **mm_realloc** routine returns a pointer to an allocated region of at least size bytes with the following constraints.
> * if ptr is NULL, the call is equivalent to **mm_malloc(size)**;
> * if size is equal to zero, the call is equivalent to **mm_free(ptr)**;
> * if ptr is not NULL, it must have been returned by an earlier call to **mm_malloc** or **mm_realloc**.
> The call to **mm_realloc** changes the size of the memory block pointed to by ptr (the old block) to size bytes and returns the address of the new block. Notice that the address of the new block might be the same as the old block, or it might be different, depending on your implementation, the amount of internal fragmentation in the old block, and the size of the **realloc** request.
> The contents of the new block are the same as those of the old ptr block, up to the minimum of the old and new sizes. Everything else is uninitialized. For example, if the old block is 8 bytes and the new block is 12 bytes, then the first 8 bytes of the new block are identical to the first 8 bytes of the old block and the last 4 bytes are uninitialized. Similarly, if the old block is 8 bytes and the new block is 4 bytes, then the contents of the new block are identical to the first 4 bytes of the old block.
##### v1
```c=
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;
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
```
### int mm_check(void)
#### 函式敘述
> It will check any invariants or consistency conditions you consider prudent. It returns a nonzero value if and only if your heap is consistent. You are not limited to the listed suggestions nor are you required to check all of them. You are encouraged to print out error messages when **mm_check** fails.
> This consistency checker is for your own debugging during development. When you submit mm.c, make sure to remove any calls to **mm_check** as they will slow down your throughput. Style points will be given for your **mm_check** function. Make sure to put in comments and document what you are checking.
```c=
```
### 習題 9.18
#### 習題敘述
> The allocator in Section 9.9.12 requires both a header and a footer for each block in order to perform constant-time coalescing. Modify the allocator so that free blocks require a header and footer, but allocated blocks require only a header.
```c=
```
### 習題 9.20
#### 習題敘述
> Write your own version of malloc and free, and compare its running time and space utilization to the version of malloc provided in the standard C library.
## 遭遇問題
### 編譯錯誤 - 32-bit 的函式庫（已解決）
* 首次 make 會出現錯誤，缺少的 lib 可以透過以下指令安裝
```
$ apt-get install gcc-multilib
```
[參考來源](https://askubuntu.com/questions/91909/trouble-compiling-a-32-bit-binary-on-a-64-bit-machine)
### 修改 trace file 讀取位置（已解決）
* 第一次執行 ./mdriver -V 的時候會出現以下錯誤
* 解決方法：修改 config.h 內的 TRACERDIR 為目標資料夾
```
#define TRACEDIR "your file path"
```
### 測試的 trace file 僅有兩份 (已解決)
* 以下為初始預設的 trace file，但是我們目前有的 trace file 僅有 "short1-bal.rep" 和 "short2-bal.rep"，其他 tracefile 可以從網路資源找到
## 實驗
### macro GET\(p\) 若沒有做轉型產生的結果
Sign in with Wallet
Connect another wallet