CS:APP Malloc Lab

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{m a x_{i \leq k} P_{i}}{H_{k}}

吞吐量：平均每秒可以完成多少筆請求

最後的總分就會統整成：

P = w U + (1 - w) m i n (1, \frac{T}{T_{l i b c}})

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 Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

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 地址

/* 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 時會用不同的架構。

Alignment padding: 為了對齊後面東西，全放 0 就好
Prologue block: 只有 header 與 footer。在初始化時創建，並且永不釋放
Epilogue block: heap 以這個 block 做結尾

會需要這兩個 block 是因為要消除合併時邊界條件。分配器會有一個全域指標 heap_listp 指向 Prologue 的 footer。




















/* 
 * 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 的指標。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

/* 
 * 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 就如下圖所示。

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

`extend_heap`

在 mm_init 中的 16 行呼叫 extend_heap，作用是用來擴展 heap 空間。只會有兩個時候要用到該函式：

初始化 heap
當 mm_malloc 找不到適合的空閒塊時，為保持對齊，extend_heap 會向上捨入找到最接近 8 bytes 的空間

可以看到它實際上也是利用 mem_sbrk 函式獲取空間。接著它就初始化空閒塊與 Epilogue 的配置。

回顧剛剛 mm_init 時我們輸入的大小是 CHUNKSIZE/WSIZE 也就是 1KB 大小。現在來看實際上記憶體的配置是如何做的。

mm_init 第 13 行後，就如剛剛圖片所示
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
extend_heap 到第 8 行後，配置了 1KB 大小的空閒塊。但很明顯這時候 Epilogue 就不應該放在這裡，而是空間的最後面。
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
extend_heap 第 12 ~ 14 行，剛剛拿到的 bp 就是上圖的 old_brk。因此要做三件事：
- 設置空閒塊 header: HDRP 剛好就是減去一個 word 大小，接著放入大小與配置位，這也剛好蓋過原本的 Epilogue
- 設置空閒塊 footer: 與 header 雷同
- 設置新的 Epilogue: 從 old_brk 加上 1KB 到 mem_brk ，再用 HDRP 減 4 bytes，就可以獲得最後一個 word，就可以填上 Epilogue

圖片藍色部份是已分配，灰色部份是未分配


















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 去合併可能的空閒塊。

/*
 * 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`

合併函式就是把前後如果有空閒塊的話可以合併成一個空閒塊。其目的就是為了減上記憶體碎片。有兩種情況會呼叫合併:

extend_heap 最後，因為擴展的空間實際上就是一個空閒塊，可能前面會有小塊的空閒塊
mm_free 最後，每當釋放一塊空間時就需要做合併

那合併就會有以下四種情況：

Case 1: 前後兩個都是已分配塊，就無須合併
Case 2: 後面那塊是空閒塊，後面塊與當前塊合併成一個空閒塊
Case 3: 前面那塊是空閒塊，前面塊與當前塊合併成一個空閒塊
Case 4: 前面與後面都是空閒塊，三個合併成一個空閒塊

/*
 * 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 擴展新的空間。再將其放入。

/* 
 * 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 函式將其放入。而會有兩種情況：

空閒塊減去要分配的塊的大小後還有兩個 DSIZE，這時就要分割。一塊變成已分配塊，另一塊則是新的空閒塊。
若大小剛好只能放下分配塊，則不須分割。

/*
 * 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

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 前面會留下較多碎片。

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。

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 */
}

遇到問題：Checking mm_malloc for correctness, ERROR [trace 6, line 3926]: Payload (0xf4934918:0xf49389a1) overlaps another payload (0xf4937f58:0xf493992a)

`best_fit`

它會尋找整個 free list，檢查所有可放下的 block 中最小的 block。優點就是空間利用率一定最好，而缺點就是要跑比較久。

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，這時會出現兩種情況：

size 大於 ptr 的大小: 這代表需要分配一個 size 大小的塊，並將 ptr 裡的值複製到新的塊
size 小於 ptr 的大小: 一樣分配一個 size 大小的塊，但這時需要截斷 ptr 的值，抓 size 大小的值複製到新的塊

/*
 * 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

$ ./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

$ ./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 的前後顛倒

而 Segregated 的核心思想就是將不同大小的 Free list 按 2 的幂比例分開。我們就用一個陣列來管理，每個元素就存放一個 Free list。

Macro

因為記憶體操作涉及許多複雜的指標操作，因此我參考 CS:APP Malloc Lab 解題筆記的操作並加以解釋。我們需要額外多做一些操作，用來獲取與放入 Next 與 Prev 指標。

/* 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。考慮執行:

#define NEXT_PTR(bp) ((char *)(bp) + WSIZE)

為什麼要先將 bp 強制轉型成 (char *): 因為指標運算的步進單位是基於指標所指向型別的大小。若是指標型態為 int 的話，bp + 1 就會被編譯器翻譯成 bp + 4。因此為確保 bp + WSIZE 是正確運算須強制轉型。

這時就會獲得指標指向 0x1004，考慮執行:

#define GET_NEXT(bp) (*(char **)(NEXT_PTR(bp)))

可以看出它將剛剛獲得的指標強制轉型成指向 char 類型指標的指標。再對它 dereference。
那為什麼要那麼麻煩，不能用直接 dereference 嘛？如以下寫法

#define GET_NEXT(bp) (*(NEXT_PTR(bp)))

答案是不行，因為剛剛知道 NEXT_PTR(bp) 回傳的指標是 char 型態的，若是直接 dereference ，編譯器會以為裡面是正常的數值，所以只取出 char 大小，也就是 1 byte 的數據。就會回傳 0x48，很明顯就有問題。
因此需要先強制轉型成指向 char 類型指標的指標。告訴編譯器：「這個地址上的值是另一個地址」，這樣在 dereference 時就會把整個 word 都抓出來了。也就是 0x2048。

`PUT_PTR`

負責將 ptr 的內容放入 p 中。這次它將兩邊都強制轉型成 unsigned int:

將 p 強制轉型為 unsigned int*，表示我們準備將地址存儲為一個 4-bytes 無符號整數。
將 ptr 強制轉型為 unsigned int，表示我們把指標值（記憶體地址）轉換為整數位元組表示。
執行 dereference *(unsigned int *)(p)，將整數值 ptr 存入 p 所指向的記憶體區域。

這裡學到許多記憶體底層的指標操作，詳細指標操作可以看：

指標篇筆記

`mm_init`

初始化與前面差不多，增加兩件事:

將 extend_heap 回傳的第一個空閒塊裡的 prev 與 next 初始化。
初始化 seg_listp_arr 陣列，大小如同下列所示。以二的幂為單位分塊。（最小的塊為 16 bytes)，一共 16 個元素。

{16}, {17 \sim 32}, {33 \sim 64}, {65 \sim 128}, {129 \sim 256}, {257 \sim 512}, {513 \sim 1024},

{1025 \sim 2048}, {2049 \sim 4096}, {4097 \sim 2^{13}}, {2^{13} + 1 \sim 2^{14}}, {2^{14} + 1 \sim 2^{15}},

{2^{15} + 1 \sim 2^{16}}, {2^{16} + 1 \sim 2^{17}}, {2^{18} + 1 \sim 2^{19}}, {2^{19} + 1 \sim \infty}

/* 
 * 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。

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 的開頭就好

Case 2: Free block 後面接著空閒塊，需要先將後面的空閒塊刪除，再將這兩個合併成一個新的空閒塊。

Case 3: Free block 前面接著空閒塊，需要先將前面的空閒塊刪除，再將這兩個合併成一個新的空閒塊。

Case 4: Free block 前後都是空閒塊，就要將兩個都刪除後，再將這三個合併成一個新的空閒塊。

/*
 * 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

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 操作即可，一樣要檢查下一個節點是否存在。

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 個。

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 開始搜尋即可。

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

/*
 * 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

$ ./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

$ ./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

First fit 的速度確實比 Best fit 還快一點。但是記憶體利用率差不多。因此整體的分數是一樣的。

Virtual memory 筆記

【CSAPP录播课】9.2 地址翻译

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，代表記憶體中對應的物理地址緩存了該虛擬頁。

Virtual address

從 CPU 產出的 Virtual address 是由 Virtual page number(VPN) 與 Virtual page offset(VPO) 組成。

VPN: 用於指示在 Page table 的哪個 entry
VPO: 要娶的數據是該地址加上 offset

假設 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 一樣大。

page hit

CPU 產出 Virtual address
MMU 計算出 PTEA: PTEA = PTBR + (VPN * page size)
從 page table 中找出 PTE 回傳至 MMU
MMU 由上面方法算出 PA
從記憶體抓取資料

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

Cache in VM

快取也是可以存放 PTE 的，若發生 cache miss，再去記憶體查詢 page table 即可。

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

TLB hit

CPU 產生 VA
MMU 會先將 VA 中的 VPN 丟到 TLB 裡尋找是否有緩存 PTE
TLB 回傳 PTE 給 MMU，就可以直接拿到 PA
直接拿 PA 去記憶體裡抓資料

TLB miss

當在 TLB 中找不到緩存的 PTE 時，代表該 PTE 仍存放在記憶體裡的 page table。

如同上面計算 PTEA 後，發送給記憶體尋址
記憶體從 page table 中找到 PTE 後，要回傳給 MMU 與 TLB。前者要計算 PA，而後者因區域性，需要緩存到 TLB
直接拿 PA 去記憶體裡抓資料

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。

假設 CPU 產生一個 VA 為 0x03D4。因為 TLB 是 4-way，因此 index 佔兩個 bits。這樣我們就可以拿 index 與 tag (VPN)給 TLB。

下圖是目前 TLB 的狀態，因為 index 為 3，所以去 set3 尋找，而因 tag 是 3，所以找到一樣的數據，即是紅框的位置。接著檢查它的 vaild bit ，若為 1 則代表其數據確實存在記憶體中。因此 0D 就是我們要的 PPN。

這時候回到 MMU 將 PPN 與 PPO(與 VPO 一樣) 組合起來就是 PA 了。就可以向記憶體直接尋址抓取資料。

CS:APP Malloc Lab

背景知識

評分標準

Implict Free List

Macros

mm_init

申請 heap 空間

初始化 heap

extend_heap

mm_free

coalesce

mm_malloc

place

find_fit

first_fit

next_fit

best_fit

mm_realloc

結果

first_fit

best fit

Segregated Free Lists

Macro

NEXT_PTR & PREV_PTR

GET_NEXT & GET_PREV

PUT_PTR

mm_init

extend_heap

coalesce

insert_blk & delete_blk

Fit Algorithm

place

結果

first_fit

best_fit

Virtual memory 筆記

Page table

Virtual address

Address translation

page hit

Page fault

Cache in VM

Translation Lookaside Buffer(TLB)

TLB hit

TLB miss

Example

Read more

Linux 核心專題: Linux 的 Preempt-RT 機制

指標篇 筆記

DWT(5, 3) 期末專案

CS:APP Labs

`mm_init`

`extend_heap`

`mm_free`

`coalesce`

`mm_malloc`

`place`

`find_fit`

`first_fit`

`next_fit`

`best_fit`

`mm_realloc`

`NEXT_PTR` & `PREV_PTR`

`GET_NEXT` & `GET_PREV`

`PUT_PTR`

`mm_init`

`extend_heap`

`coalesce`

`insert_blk` & `delete_blk`

`place`

指標篇筆記