外国熟女网站,亚洲国色天香在线,91在线亚洲

先看文檔 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字節(jié)的已分配塊，只由一個頭部和腳部組成。序言塊是在初始化時創(chuàng)建的，并且永不釋放。在序言塊后緊跟的是零個或者多個由malloc或者free創(chuàng)建的普通塊。堆總是以一個特殊的結尾塊（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 的，然后這里也體現出了結尾塊的作用?；氐綀D中，因為我們有結尾塊，它是一個WSIZE但是PACK(0,1)的塊，我們使用sbrk分配了一個雙字節(jié)對齊的塊之后，bp是指向我們分配的地址的開端，但是因為有了這個特殊的結尾塊，它可以變成新的空閑塊的頭部，這樣保證我們的bp還是指向payload處，而我們的 FTRP(bp) 也是剛好，原本的 bp + 整塊大小，那是結束處，然后我們減去 DSIZE，兩個WSIZE的，一部分做此 block 的 footer，另一做下一個block的header，下一block的header剛好就可以特殊化為新的結束塊。這里也就體現了書上說的“結尾塊是一種消除合并時邊界條件的技巧?！蓖瑫r檢查是否會有前一塊為空閑塊的狀況，如有，則需要合并。

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字節(jié)： 8字節(jié)用來滿足對齊要求，而另外8個字節(jié)用來放頭部和腳部。對于超過8字節(jié)的請求，一般的規(guī)則是加上開銷字節(jié)，然后向上攝入到最接近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 循環(huán)

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

Csapp - MallocLab

Csapp - MallocLab

先看文檔 malloc.pdf

開始

implict list

macros

mm_init

mm_free

mm_malloc

mm_realloc

helper functions

explict list

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

Csapp - MallocLab

先看文檔 malloc.pdf

開始

implict list

macros

mm_init

mm_free

mm_malloc

mm_realloc

helper functions

explict list

相關閱讀更多精彩內容

友情鏈接更多精彩內容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av