2018q3 Malloc Lab
===
contributed by < `Jyun-Neng`, `LiuJuiHung` >
## Writing a Dynamic Storage Allocator for C Programs
分配器(Allocator)有兩種：
* 顯式分配器(Explicit allocator): 需要自行分配及釋放空間，例如：C語言中的 `malloc` 及 `free`。
* 隱式分配器(Implicit allocator): 僅需自行分配，當被分配的空間被檢測到不再使用時會自動釋放，例如：Java的垃圾收集(garbage collection)。
[Malloc Lab](http://csapp.cs.cmu.edu/3e/malloclab.pdf) 目的為實作出正確、有效率、快速的 `malloc free realloc`。
在 `mm.c mm.h` 中提供四種函式：
* `int mm_init(void)`
* `void *mm_malloc(size_t size)`
* `void mm_free(void *ptr)`
* `void *mm_realloc(void *ptr, size_t size)`
## 實現一個簡單的分配器(Allocator)
我們參照 CS:APP 的範例來實作，假設記憶體為 double-word(8-byte) 對齊。
### Heap
在實作中我們採用的 boundary tag 的 Heap 格式如下圖所示：
* Boundary tag: Heap 除了有 header 記錄此 Heap 中 block 的大小及是否被分配外，另外於 heap 尾端複製了 header 的資料 -- footer。==此方法允許常數時間前後 block 合併。==
### 定義巨集
```clike
#define WSIZE 4
#define DSIZE 8
#define CHUNKSIZE (1 << 12)
#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 and allocation bit from address p
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
// Address of block's header and footer
#define HDRP(ptr) ((char *)(ptr) - WSIZE)
#define FTRP(ptr) ((char *)(ptr) + GET_SIZE(HDRP(ptr)) - DSIZE)
// Address of (physically) next and previous blocks
#define NEXT_BLKP(ptr) ((char *)(ptr) + GET_SIZE(((char *)(ptr) - WSIZE)))
#define PREV_BLKP(ptr) ((char *)(ptr) - GET_SIZE(((char *)(ptr) - DSIZE)))
```
### `mm_init` 函式實作
```clike=
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 + (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;
}
```
```clike=
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;
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1));
return coalesce(bp);
}
```
產生新的 heap 後，我們需要判斷其前後 heap 是否被分配，進而進行合併。
```clike=
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)
return bp;
else if (prev_alloc && !next_alloc) {
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) {
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 {
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;
}
```
### `mm_malloc` 函式實作
```clike=
void *mm_malloc(size_t size) {
size_t asize;
size_t extendsize;
char *bp;
if (heap_listp == 0)
mm_init();
if (size == 0)
return NULL;
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
```
```clike=
static void *find_fit(size_t asize) {
void *bp;
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
return bp;
}
return NULL;
}
```
```clike=
static void place(void *bp, size_t asize) {
size_t csize = GET_SIZE(HDRP(bp));
if ((csize - asize) >= (2 * DSIZE)) {
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(csize - asize, 0));
PUT(FTRP(bp), PACK(csize - asize, 0));
} else {
PUT(HDRP(bp), PACK(csize, 1));
PUT(FTRP(bp), PACK(csize, 1));
}
}
```
### `mm_free` 函式實作
```clike=
void mm_free(void *ptr) {
if (ptr <= 0)
return;
size_t size = GET_SIZE(HDRP(ptr));
if (heap_listp == 0)
mm_init();
PUT(HDRP(ptr), PACK(size, 0));
PUT(FTRP(ptr), PACK(size, 0));
coalesce(ptr);
}
```
### `mm_realloc` 函式實作
```clike=
void *mm_realloc(void *ptr, size_t size) {
void *newptr;
size_t copySize;
if (size == 0) {
mm_free(ptr);
return 0;
}
if (ptr == NULL)
return mm_malloc(size);
newptr = mm_malloc(size);
if (!newptr)
return NULL;
copySize = GET_SIZE(HDRP(ptr));
if (size < copySize)
copySize = size;
memcpy(newptr, ptr, copySize);
mm_free(ptr);
return newptr;
}
```
### 實驗結果
```shell
$./mdriver -V
...
Testing mm malloc
Reading tracefile: short1-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Reading tracefile: short2-bal.rep
Checking mm_malloc for correctness, efficiency, and performance.
Results for mm malloc:
trace valid util ops secs Kops
0 yes 66% 12 0.000001 17143
1 yes 89% 12 0.000001 20000
Total 78% 24 0.000001 18462
Perf index = 47 (util) + 40 (thru) = 87/100
```
Sign in with Wallet
Connect another wallet