# malloc lab

> [GitHub](https://github.com/KYG-yaya573142/malloc-lab)

:::info
本 lab 程式碼已完成，但筆記大部分內容還在撰寫中
:::

:::info
PS. 在閱讀過[如何寫一個 Git Commit Message](https://blog.louie.lu/2017/03/21/%E5%A6%82%E4%BD%95%E5%AF%AB%E4%B8%80%E5%80%8B-git-commit-message/)後深覺自己的 git message 根本在亂寫，本來想用 git rebase -i 來逐一修改，但考量只是作業的紀錄，決定留著作為紀念
:::

開始前先來看看 writeup 內的 hint 最後一項
> Start early! It is possible to write an efficient malloc package with a few pages of code. However, we can guarantee that it will be some of the most difficult and sophisticated code you have written so far in your career. So start early, and good luck!

看來這個 lab 會相當難搞啊XD
## 簡介
本 lab 需要自行撰寫一個 dynamic memory allocator，涵蓋 `malloc` 、 `free` 與 `realloc`

## 題目分析
首先 dyamic memory allcator 有兩種主要的分類，由於作業題目要求使用 C 語言撰寫，因此 malloc lab 使用的是 Explicit allocator
1. Explicit allocator
需要使用者主動的呼叫 `free` 等方程式來將配置的動態記憶體釋放
3. Implicit allocator
依靠 garbage collectors 來自動的釋放配置的動態記憶體

影響 allocator 效能 (空間利用率及吞吐量) 的關鍵因素是 free block 的組織方式及動態記憶體配置的尋找方式

free block 的組織方式有以下三種
1. implicit free block
2. explicit free list
3. segregated free list

配置動態記憶體時的尋找方式有三種
1. first fit
2. next fit
3. best fit

## CS:APP 第 7 章 virtual memory 複習 (待補)

## 前置作業
malloc lab 會強制使用 32-bit 的函式庫進行編譯，如果缺少對應的函式庫，在 ubuntu (Debian) 中可以用以下方式取得

$ apt-get install gcc-multilib

## 解題路徑1 - implicit free list + first fit
基本上照著 CS:APP 第 9 章的範例稍作修改就能寫完這個部分，採用 implicit free list 來管理 free block，heap block 則採用皆有 header 與 footer 的格式，如下圖


最後的結果如下

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.007360   774
 1       yes   99%    5848  0.007895   741
 2       yes   99%    6648  0.013615   488
 3       yes  100%    5380  0.009066   593
 4       yes   66%   14400  0.000284 50794
 5       yes   92%    4800  0.007785   617
 6       yes   92%    4800  0.008416   570
 7       yes   55%   12000  0.206528    58
 8       yes   51%   24000  0.276396    87
 9       yes   27%   14401  0.064584   223
10       yes   34%   14401  0.002457  5861
Total          74%  112372  0.604384   186

Perf index = 44 (util) + 12 (thru) = 57/100

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.007283   782
 1       yes  100%    5848  0.007488   781
 2       yes   99%    6648  0.012473   533
 3       yes  100%    5380  0.009148   588
 4       yes   99%   14400  0.000193 74496
 5       yes   92%    4800  0.007895   608
 6       yes   92%    4800  0.008242   582
 7       yes   55%   12000  0.156152    77
 8       yes   51%   24000  0.285498    84
 9       yes   30%   14401  0.062039   232
10       yes   34%   14401  0.002285  6301
Total          77%  112372  0.558696   201

Perf index = 46 (util) + 13 (thru) = 60/100

## 解題路徑2 - explicit free list (待補)

## 解題路徑3 - segregated free list (待補)

## 改善 realloc 的效能 (待補)
無論用哪種 free block 組織的方式實作 allocator，都會發現評分後只能拿到及格分數，因此需要進一步優話 realloc 的效能

### 改變初始的 heap 大小
初始配置的空間大小會影響效率

int mm_init(void)
{
...
    /* extend the empty heap size by 4kB */
    if(extend_heap(4*WSIZE) == NULL)
        return -1;
...
}

void *mm_malloc(size_t size)
{
...
    /* no fit found, extend heap to place the block */
    extendsize = MAX(asize, CHUNKSIZE);
    if((bp = extend_heap(extendsize)) == NULL)
        return NULL;
...
}

### 改變 realloc 的實作方式 (待補)

void *mm_realloc(void *ptr, size_t size)
{
    char *new_bp;
    size_t old_size = GET_SIZE(HDRP(ptr)) - 2*WSIZE;  /* content size of the old block */

    /* ignore spurious requests */
    if(ptr == NULL && size == 0) {
        return NULL;
    }
    /* if ptr is NULL, the call is equivalent to mm malloc(size) */
    else if(ptr == NULL) {
        return mm_malloc(size);
    }
    /* if size is equal to zero, the call is equivalent to mm free(ptr) */
    else if(size == 0) {
        mm_free(ptr);
        return NULL;
    }

    if(size > old_size) {  /* allocate a larger space */
        /* allocate the new block */
        if((new_bp = mm_malloc(size)) == NULL)
            return NULL;
        memcpy(new_bp, ptr, old_size);
        mm_free(ptr);  /* free the old block */
        return (void *)new_bp;
    }
    else {  /**/
        size = ALIGN(size + 2*WSIZE);
        old_size += 2*WSIZE;
        if((old_size - size) >= (2*DSIZE)) {
            /* shrink the block to size */
            PUTW(HDRP(ptr), PACK(size, 1));
            PUTW(FTRP(ptr), PACK(size, 1));
            /* free the remainder block */
            PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
            PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
            if((GET_NEXT(freelist_root)) == NULL) {
                PUT_NEXT(freelist_root, NEXT_BLKP(ptr));
                PUT_PREV(freelist_root, NEXT_BLKP(ptr));
                PUT_NEXT(NEXT_BLKP(ptr), freelist_root);
                PUT_PREV(NEXT_BLKP(ptr), freelist_root);
            }
            else {
                PUT_PREV(GET_NEXT(freelist_root), ptr);
                PUT_NEXT(ptr, GET_NEXT(freelist_root));
                PUT_NEXT(freelist_root, ptr);
                PUT_PREV(ptr, freelist_root);
            }
            return ptr;
        }
        else {
            return ptr;
        }
    }
}

## simplest remalloc
最簡單的實作方式，但空間利用率和效率都非常糟糕

/*
 * mm_realloc - Implemented simply in terms of mm_malloc and mm_free
 */
void *mm_realloc(void *ptr, size_t size)
{
    char *new_bp;
    size_t old_size = GET_SIZE(HDRP(ptr)) - 2*WSIZE;  /* content size of the old block */

    /* ignore spurious requests */
    if(ptr == NULL && size == 0) {
        return NULL;
    }
    /* if ptr is NULL, the call is equivalent to mm malloc(size) */
    else if(ptr == NULL) {
        return mm_malloc(size);
    }
    /* if size is equal to zero, the call is equivalent to mm free(ptr) */
    else if(size == 0) {
        mm_free(ptr);
        return NULL;
    }

    #ifndef TEST_REALLOC

    /* allocate the new block */
    if((new_bp = mm_malloc(size)) == NULL)
        return NULL;

    /* The contents of the new block are same as the old ptr block 
       (up to the minimum of the old and new block sizes). */
    if(old_size <= size) {
        memcpy(new_bp, ptr, old_size);
    }
    else {
        memcpy(new_bp, ptr, size);
    }
    
    mm_free(ptr);  /* free the old block */
    return (void *)new_bp;

    #else

    size_t prev_alloc = GET_ALLOC(HDRP(PREV_BLKP(ptr)));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(ptr)));
    size_t prev_size = prev_alloc? 0 : GET_SIZE(HDRP(PREV_BLKP(ptr)));
    size_t next_size = next_alloc? 0 : GET_SIZE(HDRP(NEXT_BLKP(ptr)));

    /* use the whole block size instead of the content size */
    size = ALIGN(size + 2*WSIZE);
    old_size = GET_SIZE(HDRP(ptr));

    if(size == old_size) {
        return ptr;
    }

    /* realloc a smaller block */
    if(size < old_size) {
        if(prev_alloc && next_alloc) { /* both prev and next block are allocated */
            if((old_size - size) < (2*DSIZE)) {  /* use original block when size changes too small */
                return ptr;
            }
            else {  /* shrink the block */
                PUTW(HDRP(ptr), PACK(size, 1));
                PUTW(FTRP(ptr), PACK(size, 1));
                /* re-insert the new block at the root of the list */
                PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
                PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size - size), 0));
                insert_root(NEXT_BLKP(ptr));
                return ptr;
            }
        }
        else {
           if(!next_alloc) { /* shrink ptr and adjust next free block */
                detach(NEXT_BLKP(ptr));
                PUTW(HDRP(ptr), PACK(size, 1));
                PUTW(FTRP(ptr), PACK(size, 1));
                /* re-insert the new block at the root of the list */
                PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
                PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
                insert_root(NEXT_BLKP(ptr));
                return ptr;
            }
            else { /* only prev block is free */
                detach(PREV_BLKP(ptr));
                ptr = PREV_BLKP(ptr);
                memmove(ptr, NEXT_BLKP(ptr), (size - 2*WSIZE));
                PUTW(HDRP(ptr), PACK(size, 1));
                PUTW(FTRP(ptr), PACK(size, 1));
                /* re-insert the new block at the root of the list */
                PUTW(HDRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
                PUTW(FTRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
                insert_root(NEXT_BLKP(ptr));
                return ptr;
            }
        }
    }
    /* realloc a larger block */
    else {
        if(size > (old_size + prev_size + next_size)) { /* need to allocate a new block by malloc */
            /* allocate the new block */
            if((new_bp = mm_malloc(size)) == NULL)
                return NULL;
            memcpy(new_bp, ptr, (old_size - 2*WSIZE));            
            mm_free(ptr);  /* free the old block */
            return (void *)new_bp;
        }
        else {
            if((old_size + next_size) >= size) { /* use ptr + next block */
                detach(NEXT_BLKP(ptr));
                if((old_size + next_size - size) >= (2*DSIZE)) {
                    PUTW(HDRP(ptr), PACK(size, 1));
                    PUTW(FTRP(ptr), PACK(size, 1));
                    /* re-insert the new block at the root of the list */
                    PUTW(HDRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
                    PUTW(FTRP(NEXT_BLKP(ptr)), PACK((old_size + next_size - size), 0));
                    insert_root(NEXT_BLKP(ptr));
                    return ptr;
                }
                else {  /* use whole ptr + next */
                    PUTW(HDRP(ptr), PACK((old_size + next_size), 1));
                    PUTW(FTRP(ptr), PACK((old_size + next_size), 1));
                    return ptr;
                }

            }
            else if((prev_size + old_size) >= size) { /* use ptr + prev block */
                detach(PREV_BLKP(ptr));
                if((prev_size + old_size - size) >= (2*DSIZE)) {
                    ptr = PREV_BLKP(ptr);
                    memmove(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
                    PUTW(HDRP(ptr), PACK(size, 1));
                    PUTW(FTRP(ptr), PACK(size, 1));
                    /* re-insert the new block at the root of the list */
                    PUTW(HDRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
                    PUTW(FTRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size - size), 0));
                    insert_root(NEXT_BLKP(ptr));
                    return ptr;
                }
                else {  /* use whole prev + ptr */
                    ptr = PREV_BLKP(ptr);
                    memcpy(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
                    PUTW(HDRP(ptr), PACK((prev_size + old_size), 1));
                    PUTW(FTRP(ptr), PACK((prev_size + old_size), 1));
                    return ptr;
                }
            }
            else { /* use prev + ptr + next block */
                detach(PREV_BLKP(ptr));
                detach(NEXT_BLKP(ptr));
                if((prev_size + old_size + next_size - size) >= (2*DSIZE)) {
                    ptr = PREV_BLKP(ptr);
                    memcpy(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
                    PUTW(HDRP(ptr), PACK(size, 1));
                    PUTW(FTRP(ptr), PACK(size, 1));
                    /* re-insert the new block at the root of the list */
                    PUTW(HDRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size + next_size - size), 0));
                    PUTW(FTRP(NEXT_BLKP(ptr)), PACK((prev_size + old_size + next_size - size), 0));
                    insert_root(NEXT_BLKP(ptr));
                    return ptr;
                }
                else {  /* use whole prev + ptr + next */
                    ptr = PREV_BLKP(ptr);
                    memcpy(ptr, NEXT_BLKP(ptr), (old_size - 2*WSIZE));
                    PUTW(HDRP(ptr), PACK((prev_size + old_size + next_size), 1));
                    PUTW(FTRP(ptr), PACK((prev_size + old_size + next_size), 1));
                    return ptr;
                }
            }
        }
    }
    #endif
}

## reference
[compiling a 32 bit binary on a 64 bit machine](https://askubuntu.com/questions/91909/trouble-compiling-a-32-bit-binary-on-a-64-bit-machine)
[97分來源](https://www.jianshu.com/p/48d5d0554b3b)
[glibc 的 malloc/free 實作](https://hackmd.io/@sysprog/c-memory?type=view#glibc-%E7%9A%84-mallocfree-%E5%AF%A6%E4%BD%9C)

###### tags: `csapp`