先看文档 malloc.pdf

需要实现四个函数：

• int mm_init(void)
• void *mm_malloc(size_t size);
• void mm_free(void *ptr);
• void *mm_realloc(void *ptr, size_t size)

建议写一个 heap checker，随时检查

基本上要求是和书上一样， 双字对齐。不允许更改 mm.c 中的 interface（也就是函数定义），不允许直接使用 malloc/calloc/free/realloc/sbrk/brk... 实际上可以用的给我们在 memlib.h 中，也就是文档中 Support Routines 指出的可以用的函数。

开始

压缩包中有两个文件可用，我们run 一下：

./mdriver -f short1-bal.rep
Perf index = 30 (util) + 40 (thru) = 70/100                                                             

./mdriver -f short2-bal.rep
Perf index = 60 (util) + 40 (thru) = 100/100 

但实际所需trace file 可以此 github 可得到

然后我们先来 run 一遍测试看结果是这样：

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   23%    5694  0.000056100957
 1       yes   19%    5848  0.000064 91232
 2       yes   30%    6648  0.000074 90081
 3       yes   40%    5380  0.000061 87908
 4        no     -       -         -     -
 5        no     -       -         -     -
 6        no     -       -         -     -
 7       yes   55%   12000  0.000144 83449
 8       yes   51%   24000  0.000131182788
 9        no     -       -         -     -
10        no     -       -         -     -
Total            -       -         -     -

Terminated with 5 errors
correct:6
perfidx:0

有错误 mm_malloc failed， mm_realloc failed，所以最初的代码虽然可以让两个 short.rep 有输出但实际上是有很多问题，所以跟着老师建议，首先抄书上的implementation一遍。

implict list

从 implict list开始，此部分参见书上9.9.12 p597 - p603。链表形式如下：

memory_structure.png

第一个字是一个双字边界对齐的不适用的填充字。填充后面紧跟着一个特殊的序言块（prologue block），这是一个8字节的已分配块，只由一个头部和脚部组成。序言块是在初始化时创建的，并且永不释放。在序言块后紧跟的是零个或者多个由malloc或者free创建的普通块。堆总是以一个特殊的结尾块（epilogue block）来结束，这个块是一个大小为零的已分配块，只由一个头部组成，序言块和结尾块是一种消除合并时边界条件的技巧。分配器使用一个单独的私有（static）全局变量（heap_listp)，它总是指向序言块。

代码分解如下：

macros

// 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))   
// 这里有很多强制类型转换，书上提到因为p是一个 void * 指针

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)                   
#define GET_ALLOC(p) (GET(p) & 0x1)                    
// GET_ALLOC 很容易理解， 至于 GET_SIZE 也是类似，因为我们的 block size 总是双字对齐，所以它的大小总是后3位为0
// 我们这样做完全 GET(p) & (1111 ... 1000) 完全是 ok 的

/* 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) 
// HDRP header address 很容易理解，看图，bp - WSIZE 就是 header 的地址，同时也可以注意，这里我们也做了类型转换，把bp转成char * ，这样来计算才对。
// FTRP footer address 同样看图，是 bp + 整个块的大小 - DSIZE，就是我们先把bp移到普通快2的hdr， 然后减去两个WSIZE，也就是DSIZE，得到 footer address
// 这里我们同时也知道了GET_SIZE 是计算普通块1的大小，而不是普通块1的payload


/* 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))) 
// 这两个计算方法同样也看图，next block pointer，实际上 ((char *)(bp) - WSIZE) 就是 HDRP，header address，我们得到整个块的大小，然后bp 加上整块大小，这里也知道我们的 address 总是指向 payload
// prev block pointer, ((char *)(bp) - DSIZE) 得到 previous block footer，计算之前的块的大小，然后bp - 之前的块大小，指向 payload

宏当然也可以一个包一个的使用：

size_t size = GET_SIZE(HDRP(NEXT_BLKP(bp)));

这样得到 bp 后面块的大小。

mm_init

/* 
 * mm_init - Initialize the memory manager 
 */

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;
}

这里的注释很清楚，同时每一句我们也可以在上图的allocator看到对应结构，比如第一个WSIZE的padding部分，序言块的 header 和 footer，以及特殊的结尾块。包括我们将heap_listp 更新，指向序言块的 footer 部分（实际上我们这里也可以理解为它指向序言块的payload部分，也就是0），同时我们用到extendheap将heap 默认快到 1<<12 / WSIZE 的大小。

/* 
 * extend_heap - Extend heap with free block and return its block pointer
 */
static void *extend_heap(size_t words) 
{
    char *bp;
    size_t 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));         /* Free block header */  
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */   
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */ 

    /* Coalesce if the previous block was free */
    return coalesce(bp);                                          
}

extend_heap 是以 words 为单位，所以之前我们传递的是 CHUNKSIZE/WSIZE 的，然后这里也体现出了结尾块的作用。回到图中，因为我们有结尾块，它是一个WSIZE但是PACK(0,1)的块，我们使用sbrk分配了一个双字节对齐的块之后，bp是指向我们分配的地址的开端，但是因为有了这个特殊的结尾块，它可以变成新的空闲块的头部，这样保证我们的bp还是指向payload处，而我们的 FTRP(bp) 也是刚好，原本的 bp + 整块大小，那是结束处，然后我们减去 DSIZE，两个WSIZE的，一部分做此 block 的 footer，另一做下一个block的header，下一block的header刚好就可以特殊化为新的结束块。这里也就体现了书上说的“结尾块是一种消除合并时边界条件的技巧。”同时检查是否会有前一块为空闲块的状况，如有，则需要合并。

mm_free

/* 
 * mm_free - Free a block 
 */
void mm_free(void *bp)
{
    if (bp == 0) 
        return;

    size_t size = GET_SIZE(HDRP(bp));

    PUT(HDRP(bp), PACK(size, 0));
    PUT(FTRP(bp), PACK(size, 0));
    coalesce(bp);
}

mm_free 非常显而易见，找到这个块的size，然后把它标记为未分配，同时检查看是否需要合并。

/*
 * coalesce - Boundary tag coalescing. Return ptr to coalesced block
 */
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;
}

coalesce 这个函数也非常明显的对应书上的4种状况：

• case 2 是后面一块free，那么我们改变size之后，对应的FTRP也变了，这一句会把整个一大块全变成free
• case 3 和 case 4 也是类似case 2需要合并，不过同时bp也改变，指向前面的free block
• 这四种情况，同时体现出了‘书上所说的序言块和结尾块标记为分配允许我们忽略潜在的麻烦边界情况’，的确，试想一下如果序言块和结尾块并不是这样做，那么我们每次必须要考虑特殊状况，比如如果在头或者尾要怎么处理

mm_malloc

/* 
 * mm_malloc - Allocate a block with at least size bytes of payload 
 */
void *mm_malloc(size_t size) 
{
    size_t asize;      /* Adjusted block size */
    size_t extendsize; /* Amount to extend heap if no fit */
    char *bp;      

    if (heap_listp == 0){
        mm_init();
    }

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

最小块的大小是16字节： 8字节用来满足对齐要求，而另外8个字节用来放头部和脚部。对于超过8字节的请求，一般的规则是加上开销字节，然后向上摄入到最接近8的整数倍。

配套的 find_fit 和 place 都很清晰

/* 
 * find_fit - Find a fit for a block with asize bytes 
 */
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; /* No fit */

}

/* 
 * place - Place block of asize bytes at start of free block bp 
 *         and split if remainder would be at least minimum block size
 */
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));
    }
}

place 会计算整个空闲块的大小，如果依旧有剩余空间会再分割空闲块，否则会直接就把这一块给 mm_malloc 用。

mm_realloc

/*
 * mm_realloc - Naive implementation of realloc
 */
void *mm_realloc(void *ptr, size_t size)
{
    size_t oldsize;
    void *newptr;

    /* If size == 0 then this is just free, and we return NULL. */
    if(size == 0) {
        mm_free(ptr);
        return 0;
    }

    /* If oldptr is NULL, then this is just malloc. */
    if(ptr == NULL) {
        return mm_malloc(size);
    }

    newptr = mm_malloc(size);

    /* If realloc() fails the original block is left untouched  */
    if(!newptr) {
        return 0;
    }

    /* Copy the old data. */
    oldsize = GET_SIZE(HDRP(ptr));
    if(size < oldsize) oldsize = size;
    memcpy(newptr, ptr, oldsize);

    /* Free the old block. */
    mm_free(ptr);

    return newptr;
}

memcpy - Copies count bytes from the object pointed to by src to the object pointed to by dest. Both objects are reinterpreted as arrays of unsigned char.

realloc 还考虑了新的allocated memory 变小的状况。

helper functions

/* 
 * mm_checkheap - Check the heap for correctness
 */
void mm_checkheap(int verbose)  
{ 
    checkheap(verbose);
}

/* 
 * checkheap - Minimal check of the heap for consistency 
 */
void checkheap(int verbose) 
{
    char *bp = heap_listp;

    if (verbose)
        printf("Heap (%p):\n", heap_listp);

    if ((GET_SIZE(HDRP(heap_listp)) != DSIZE) || !GET_ALLOC(HDRP(heap_listp)))
        printf("Bad prologue header\n");
    checkblock(heap_listp);

    for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp)) {
        if (verbose) 
            printblock(bp);
        checkblock(bp);
    }

    if (verbose)
        printblock(bp);
    if ((GET_SIZE(HDRP(bp)) != 0) || !(GET_ALLOC(HDRP(bp))))
        printf("Bad epilogue header\n");
}


static void printblock(void *bp) 
{
    size_t hsize, halloc, fsize, falloc;

    checkheap(0);
    hsize = GET_SIZE(HDRP(bp));
    halloc = GET_ALLOC(HDRP(bp));  
    fsize = GET_SIZE(FTRP(bp));
    falloc = GET_ALLOC(FTRP(bp));  

    if (hsize == 0) {
        printf("%p: EOL\n", bp);
        return;
    }

    printf("%p: header: [%ld:%c] footer: [%ld:%c]\n", bp, 
           hsize, (halloc ? 'a' : 'f'), 
           fsize, (falloc ? 'a' : 'f')); 
}

static void checkblock(void *bp) 
{
    if ((size_t)bp % 8)
        printf("Error: %p is not doubleword aligned\n", bp);
    if (GET(HDRP(bp)) != GET(FTRP(bp)))
        printf("Error: header does not match footer\n");
}

运行./mdriver -a -g -v -t traces/，首先得到也就是老师说的F分数，不及格:

./mdriver -a -g -v -t traces/
Using default tracefiles in traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.028564   199
 1       yes   99%    5848  0.023404   250
 2       yes   99%    6648  0.040033   166
 3       yes  100%    5380  0.027339   197
 4       yes   66%   14400  0.000596 24161
 5       yes   92%    4800  0.031682   152
 6       yes   92%    4800  0.022937   209
 7       yes   55%   12000  0.858851    14
 8       yes   51%   24000  0.670486    36
 9       yes   27%   14401  0.128240   112
10       yes   34%   14401  0.003167  4548
Total          74%  112372  1.835299    61

Perf index = 44 (util) + 4 (thru) = 49/100
correct:11
perfidx:49

如果去掉 -v 的话可以得 53分

./mdriver -a -g -t traces/
Using default tracefiles in traces/
Perf index = 44 (util) + 9 (thru) = 53/100
correct:11
perfidx:53

实际上书上给的例子 place 的 policy 除了 first-fit 还有 next-fit可用。

explict list

对于explicit list：

• allocated block 跟之前一样，free block 在 payload area 需要有next 和 prev 指针
• 我们的 list 只用关注 free blocks

explict-list.png

这个lab 完全没有头绪，做不来（哭泣脸，参考这里来理解）

实际上 explict list 跟 implict list 的很多代码很类似，这里特别来之处一些不同的地方，首先，在macro部分添加了：

/* pointer of next and prev free block, only free blocks have this */
#define PREV_LINKNODE_RP(bp) ((char *)(bp))
#define NEXT_LINKNODE_RP(bp) ((char *)(bp) + WSIZE)

mm_init 分配要求了6个WSIZE， 而不是之前的4个，画示意图，觉得应该是这样：

explict-list-structure.png

root 部分添加的 linknode prev 和 linknode next 也是跟之前的 implict list 类似，为了方便而添加的。

/* 
 * mm_init - Initialize the memory manager 
 */
int mm_init(void)
{
    /* Create the initial empty heap */
    if ((heap_listp = mem_sbrk(6*WSIZE)) == (void *)-1)
        return -1;
    PUT(heap_listp, 0);                          /* Alignment padding */
    PUT(heap_listp + (1*WSIZE), 0);              /* Free PREV LINKNODE */
    PUT(heap_listp + (1*WSIZE), 0);              /* Free NEXT LINKNODE */
    PUT(heap_listp + (3*WSIZE), PACK(DSIZE, 1)); /* Prologue header */   
    PUT(heap_listp + (4*WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
    PUT(heap_listp + (5*WSIZE), PACK(0, 1));     /* Epilogue header */
    root = heap_listp + (1 * WSIZE);
    heap_listp += (4*WSIZE);

    /* Extend the empty heap with a free block of CHUNKSIZE bytes */
    if (extend_heap(CHUNKSIZE/WSIZE) == NULL) 
        return -1;
#ifdef DEBUG
    mm_check(__FUNCTION__);
#endif // DEBUG
    return 0;
}

可以看到 mm_init 跟它一一对应的状况。

// minimal size of heap is 4 WORD, 16 byte
static void *extend_heap(size_t words)
{
    char *bp;
    size_t size;

    /* Allocate an even number of words to maintain alignment */
    size = (words % 2) ? (words+1) * DSIZE : words * DSIZE;
    if ((long)(bp = mem_sbrk(size)) == -1)  
        return NULL;                                      

    /* Initialize free block header/footer and the epilogue header */
    PUT(HDRP(bp), PACK(size, 0));         /* Free block header */   
    PUT(FTRP(bp), PACK(size, 0));         /* Free block footer */  
    PUT(NEXT_LINKNODE_RP(bp), 0);         /* Next linknode */
    PUT(PREV_LINKNODE_RP(bp), 0);         /* Prev linknode */
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
    
    /* Coalesce if the previous block was free */
    return coalesce(bp);
}

跟之前的 extend_heap 不同，我们用的 size 是双字的偶数倍，这样可以保证至少有4字，这也是因为 free node 跟之前的 free node 相比，多了 prev pointer 和 next pointer.

mm_malloc 跟之前还是类似的，因为allocated block 并没有改变。

mm_free 跟之前的代码也很类似，不过在 coalesce 之前添加了两行，这是因为针对 free block 的不同：

    PUT(NEXT_LINKNODE_RP(bp), 0);
    PUT(PREV_LINKNODE_RP(bp), 0);

mm_realloc 并没有什么变化，跟之前一样。

最大变化的当然就是 coalesce 函数，处理 free block 的时候我们需要重新处理指针。

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

    }

    else if (prev_alloc && !next_alloc) {      /* Case 2 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        fix_linklist(NEXT_BLKP(bp));  /* remove from empty list */
        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)));
        fix_linklist(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)));
        fix_linklist(PREV_BLKP(bp));
        fix_linklist(NEXT_BLKP(bp));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
        bp = PREV_BLKP(bp);
    }

    insert_to_Emptylist(bp);
    return bp;
}

它用到了两个辅助函数 insert_to_EmptyList(char *) 和 fix_link_list(char *)

我们来看这两个函数：

inline void insert_to_Emptylist(char *p)
{
    /* p will be insert into the linklist, LIFO */
    char *nextp = GET(root);
    if (nextp != NULL)
       PUT(PREV_LINKNODE_RP(nextp), p);

    PUT(NEXT_LINKNODE_RP(p), nextp);
    PUT(root, p);
}

这个函数其实应该叫 insert_to_Emptylisthead, 所做的事是将 free block p 插到 Emptylist 的头部，也就是case 1 我们做的事情。

case1.png

我们做的事是找到 root 指向的头（这个函数中被叫做nextp)，如果这个(nextp)不为空，那么我们更新空的这一块 p， 让它的 next 指向原本的头，而让原本的nextp 的previous 指向新的这一块，最后更新root指向新的头部。

如果想要代码清晰一点，可以这样:

inline void insert_to_Emptylisthead(char *new_head)
{
  char *old_head_block = GET(root);
  if (old_head_block != NULL)
    PUT(PREV_LINKNODE_RP(old_head_block), new_head);
  
  PUT(NEXT_LINKNODE_RP(new_head), old_head_block);
  PUT(root, new_head);
}

来看case 2:

case2.png

来相信看一下 case 2 的代码：

    else if (prev_alloc && !next_alloc) {      /* Case 2 */
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        fix_linklist(NEXT_BLKP(bp));  /* remove from empty list */
        PUT(HDRP(bp), PACK(size, 0));
        PUT(FTRP(bp), PACK(size,0));
    }

更新更新 size， 然后这里传入 fix_linklist的指针是 NEXT_BLKP(bp)，也就是图中的free 指向的后边部分， 黑色圈出来的部分。

它应该做的事包括：

• 更新prevp 和 nextp 的指针，使它们指向正确的位置
• 像 case 1 一样调整 list 的 head

原本觉得是简单的：

PUT(NEXT_LINKNODE_RP(prevp), nextp); //把 prevp 的 next 指针指向 nextp
PUT(PREV_LINKNODE_RP(nextp), prevp); //把 nextp 的 prev 指针指向 prevp

但是这里会出现一些必须考虑的 corner case， 比如 prevp == NULL, nextp == NULL. 否则的话我们可能会丢失这两块的踪迹？

inline void fix_linklist(char *p)
{
    char* prevp = GET(PREV_LINKNODE_RP(p));
    char* nextp = GET(NEXT_LINKNODE_RP(p));

    if (prevp == NULL) {
    // 如果 prevp 不存在
      if (nextp != NULL) PUT(PREV_LINKNODE_RP(nextp), 0);
      // 如果nextp 存在，那么我们把 nextp 的 prev 指针指向不存在
      PUT(root, nextp);
      // 同时我们把 nextp 变成新的头部，这里的状况是原来的那一块可能就是free的头
    }
    else 
    {
    // prevp 存在
      if (nextp != NULL) PUT(PREV_LINKNODE_RP(nextp), prevp);
      // nextp 的 prev 指针指向 prevp
      PUT(NEXT_LINKNODE_RP(prevp), nextp);
      // prevp 的 next 指针 指向 nextp
    }
    
    // 这两句是调整黑色的部分，它们不再需要有指向，因为这一块已经被合并
    // 同时这也表明这个被移除empty_list
    PUT(NEXT_LINKNODE_RP(p), 0);
    PUT(PREV_LINKNODE_RP(p), 0);
}

最后，做完这些事之后，我们仍旧需要把 free得到的 block 更换到头部。

case 3.png

case 4.png

case 3 和 case 4 也是类似的，同时也类似implict list，我们需要更新bp，因为现在是指向之前的一块。

find_fit 也变化不大，只是改成了 while 循环

/* 
 * find_fit - Find a fit for a block with asize bytes 
 */
static void *find_fit(size_t asize)
{

    char *tmpP = GET(root);

    while (tmpP != NULL) {
      if (GET_SIZE(HDRP(tmpP) >= asize)) return tmpP;
      tmpP = GET(NEXT_LINKNODE_RP(tmpP));
    }
    return NULL; /* No fit */
}

place 有一些变化：

static void place(void *bp, size_t asize)
{
    size_t csize = GET_SIZE(HDRP(bp));   
    fix_linklist(bp); /* remove from empty_list */
    
    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));
        PUT(NEXT_LINKNODE_RP(bp), 0);
        PUT(PREV_LINKNODE_RP(bp), 0);
        coalesce(bp);
    }
    else { 
        PUT(HDRP(bp), PACK(csize, 1));
        PUT(FTRP(bp), PACK(csize, 1));
    }
}

我们需要把 bp 从 Emptylist 移除，同时对于分隔出来的快，我们需要把它放回 Emptylist 中。这里有一个问题，感觉 coalesce 是否一定需要：implict-list 没有coalesce 这一行，感觉对于implict list 也并不是那么必要，因为我们在free的时候进行合并，但是对于 explict list 一定必要！！！我们需要将分割出来的这一块放入 Emptylist 中。否则我么就会把这一块弄丢。

还有 mm_check function值得注意：

void mm_check(char *function)
{
    printf("--- cur function:%s empty blocks: \n", function );
    char *tmpP = GET(root);
    int count_empty_block = 0;
    while (tmpP != NULL) {
      count_empty_block++;
      printf("address: %x size: %d \n", tmpP, GET_SIZE(HDRP(tmpP)));
      tmpP = GET(NEXT_LINKNODE_RP(tmpP));
    }
    printf("empty_block num: %d \n", count_empty_block);
}

然后使用是这样，加上这几行:

// macro里加上 
#define DEBUG

// 想要打印出来的地方加上这个：
#ifdef DEBUG
    mm_check(__FUNCTION__);
#endif // DEBUG

才知道

”__FUNCTION__,__FILE__,__LINE__在LINUX下的C/C 编程中,这3个变量分别为当前函数名(char *)，当前文件(char *)，当前行号(int)。”

然后如果我们要打印的话，真的会打印很多。

然后还值得注意的是如果我们make 会有很多warning，是因为我们在一些地方没有做 pointer cast，比如 find_next 等函数中。explicit-list 可以得82分

/mdriver -a -g  -t traces
Using default tracefiles in traces/
Perf index = 42 (util) + 40 (thru) = 82/100
correct:11
perfidx:82