这次回顾Malloc Lab,主要对课本上的版本进行简单修改。

课程主页:http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料:https://github.com/EugeneLiu/translationCSAPP

课程视频:https://www.bilibili.com/video/av31289365/

参考资料:

准备工作

完成该lab需要完全理解9.9.12。

报错1:

/usr/include/stdio.h:27:10: fatal error: bits/libc-header-start.h: No such file or directory
 #include <bits/libc-header-start.h>

解决方法:

apt-get install gcc-multilib

报错2:

没有tracefiles文件,可以在如下地址下载:

报错3:

./mdriver -V

Testing mm malloc
Reading tracefile: amptjp-bal.rep
Could not open /afs/cs/project/ics2/im/labs/malloclab/traces/amptjp-bal.rep in read_trace: No such file or directory

修改config.h中TRACEDIR为自己的TRACEDIR。

运行方式:

make  && ./mdriver -V

宏说明

/* Pack a size and allocated bit into a word */
// #define PACK(size, alloc)  ((size) | (alloc)) //line:vm:mm:pack
// 第一位记录是否alloc, 第二位记录前一个位置是否alloc
#define PACK(size, alloc, prev_alloc)  ((size) | (alloc) | ((prev_alloc) << 1)) //line:vm:mm:pack
// 获得第二位, 判断前一个块是否alloc
#define IS_PREV_ALLOC(p)    ((GET(p) >> 1) & 0x1)

由于内存块是按字节对齐的,所以最后三位为0,利用最后一位标记当前内存块是否alloc,倒数第二位标记前一个内存卡是否alloc。

/* Read and write a word at address p */
#define GET(p)       (*(unsigned int *)(p))            //line:vm:mm:get
#define PUT(p, val)  (*(unsigned int *)(p) = (val))    //line:vm:mm:put

/* Read the size and allocated fields from address p */
#define GET_SIZE(p)  (GET(p) & ~0x7)                   //line:vm:mm:getsize
#define GET_ALLOC(p) (GET(p) & 0x1)                    //line:vm:mm:getalloc

GET获得头部(4字节),PUT设置头部4字节,头部前三个字节记录块大小。

说明:

  • 块大小包括首部尾部;
/* Given block ptr bp, compute address of its header and footer */
#define HDRP(bp)       ((char *)(bp) - WSIZE)                      //line:vm:mm:hdrp
#define FTRP(bp)       ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) //line:vm:mm:ftrp

/* Given block ptr bp, compute address of next and previous blocks */
#define NEXT_BLKP(bp)  ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) //line:vm:mm:nextblkp
#define PREV_BLKP(bp)  ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE))) //line:vm:mm:prevblkp

bp指向有效载荷的第一位,HDRP指向head的位置,FTRP指向foot的位置,NEXT_BLKP指向后一个块的bp位置,PREV_BLKP指向前一个块的bp位置。

/* Global variables */
static char *heap_listp = 0;  /* Pointer to first block */ 
static char *rover;           /* Next fit rover */

heap_listp指向第一个块,rover指向前一次内存分配的位置。

代码说明

辅助函数:

static void *extend_heap(size_t words);
static void place(void *bp, size_t asize);
static void *find_fit(size_t asize);
static void *coalesce(void *bp);

核心函数:

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

该版本实现的功能如下:

  • 下一次适配;
  • 空闲块需要脚部,已分配块只需要头部,见9.9.11;

mm_init

初始化函数,注意对齐块,序言块和结尾块:

/* 
 * mm_init - initialize the malloc package.
 */
int mm_init(void) {
    // 填充字(WSIZE) + 序言块(2*WSIZE) + 结尾块(WSIZE)
    // 如果产生错误, 则返回-1
    if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1){
        return -1;
    }
    // 对齐块
    PUT(heap_listp, 0);
    // 序言块
    PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1, 1));
    PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1, 1));
    // 结尾块
    PUT(heap_listp + (3 * WSIZE), PACK(0, 1, 1));
    // 指向第二个序言块
    heap_listp += (2 * WSIZE);
    rover = heap_listp;

    if (extend_heap(CHUNKSIZE / WSIZE) == NULL) {
        return -1;
    }

    return 0;
}

mm_malloc

size指有效载荷大小,注意申请空间时需要头部尾部:

void *mm_malloc(size_t size) {
    size_t asize;
    size_t extendsize;
    char *bp;

    // 第一次malloc
    if (heap_listp == 0) {
        mm_init();
    }

    // 忽略空申请
    if (size == 0) {
        return NULL;
    }

    if (size <= WSIZE) {
        // head + content + 8字节对齐
        // 4 + 4
        asize = DSIZE;
    }else { 
        // head + 8字节对齐
        asize = DSIZE * ((size + (WSIZE) + (DSIZE - 1)) / DSIZE);
    }
    // head + foot + 对齐
    // asize = DSIZE + DSIZE * ((size + (DSIZE - 1)) / DSIZE);

    // 如果没找到合适的块, 则申请额外空间
    if ((bp = find_fit(asize)) == NULL) {
        extendsize = MAX(asize, CHUNKSIZE);
        // 无法申请到空间
        if ((bp = extend_heap(extendsize / WSIZE)) == NULL) {
            return NULL;
        }
    }

    // 设置块
    place(bp, asize);

    return bp;
}

mm_free

void mm_free(void *bp) {
    if (bp == 0) {
        return;
    }

    size_t size = GET_SIZE(HDRP(bp));
    // 如果为空则申请
    if (heap_listp == 0) {
        mm_init();
    }

    // 更新cur bp
    PUT(HDRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
    PUT(FTRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
    // 更新next bp
    void *next = NEXT_BLKP(bp);
    size_t next_size = GET_SIZE(HDRP(next));
    if (GET_ALLOC(HDRP(next))) {
        // 注意alloc没有foot
        PUT(HDRP(next), PACK(next_size, 1, 0));
    }else {
        PUT(HDRP(next), PACK(next_size, 0, 0));
        PUT(FTRP(next), PACK(next_size, 0, 0));
    }
    
    coalesce(bp);
}

mm_realloc

参考课本的realloc:

void *mm_realloc(void *ptr, size_t size) {
    size_t oldsize;
    void *newptr;
    
    if (ptr == NULL) {
        return mm_malloc(size);
    }

    if (size == 0) {
        mm_free(ptr);
        return 0;
    }

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

extend_heap

// 给heap扩充空闲块, 返回块指针
static void *extend_heap(size_t words) {
    char *bp;
    size_t size;
    // 2字对齐
    size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
    // 扩充失败
    if ((bp = mem_sbrk(size)) == (void *)-1){
        return NULL;
    }

    // 更新head, foot
    PUT(HDRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
    PUT(FTRP(bp), PACK(size, 0, IS_PREV_ALLOC(HDRP(bp))));
    // 更新结尾块
    PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1, 0));
   
    // 合并块
    return coalesce(bp);
}

coalesce

参考课本的函数即可,这里对prev_alloc进行了修改:

// 合并块, 返回合并后的指针
static void *coalesce(void *bp) {
    // size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
    size_t prev_alloc = IS_PREV_ALLOC(HDRP(bp));
    size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
    size_t size = GET_SIZE(HDRP(bp));

    // free的前面为alloc
    if (prev_alloc && next_alloc) { // afa
        return bp;
    }else if (prev_alloc && (!next_alloc)) { // aff
        size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
        PUT(HDRP(bp), PACK(size, 0, 1));
        PUT(FTRP(bp), PACK(size, 0, 1));
    }else if ((!prev_alloc) && next_alloc) { // ffa
        size += GET_SIZE(HDRP(PREV_BLKP(bp)));
        PUT(FTRP(bp), PACK(size, 0, 1));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));
        bp = PREV_BLKP(bp);
    }else { // fff
        size += GET_SIZE(HDRP(PREV_BLKP(bp))) + GET_SIZE(FTRP(NEXT_BLKP(bp)));
        PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0, 1));
        PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0, 1));
        bp = PREV_BLKP(bp);
    }

    // 更新下一次适配的指针
    if ((rover > (char *)bp) && (rover < NEXT_BLKP(bp))) {
        rover = bp;
    }

    return bp;
}

find_fit

// 下一次适配
static void *find_fit(size_t asize) {
    char *oldrover = rover;

    // 从上次匹配的地址开始找
    for ( ; GET_SIZE(HDRP(rover)) > 0; rover = NEXT_BLKP(rover)) {
        if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover)))) {
            return rover;
        }
    }

    // 如果没找到则从头开始
    void *bp;
    for (rover = heap_listp; rover < oldrover; rover = NEXT_BLKP(rover)) {
        if (!GET_ALLOC(HDRP(rover)) && (asize <= GET_SIZE(HDRP(rover)))) {
            return rover;
        }
    }

    // 没找到则返回null
    return NULL;
}

place

// 设置块, 如果块大小大于申请大小 + 2 * DSIZE, 则划分块, 不用设置脚步
static void place(void *bp, size_t asize) {
    // 保证csize >= asize
    size_t csize = GET_SIZE(HDRP(bp));
    
    // 有问题
    if (csize >= asize + (2 * DSIZE)) {
        // 划分, 设置剩余部分为未划分
        // 标记为alloc, free前面为alloc
        PUT(HDRP(bp), PACK(asize, 1, 1));
        // PUT(FTRP(bp), PACK(asize, 1));
        bp = NEXT_BLKP(bp);
        PUT(HDRP(bp), PACK(csize - asize, 0, 1));
        PUT(FTRP(bp), PACK(csize - asize, 0, 1));
    }else {
        // 
        PUT(HDRP(bp), PACK(csize, 1, 1));
        void *next_bp = NEXT_BLKP(bp);
        size_t size = GET_SIZE(HDRP(next_bp));
        PUT(HDRP(next_bp), PACK(size, 1, 1));
        // PUT(FTRP(bp), PACK(csize, 1));
    }
}

实验结果

当前版本:

trace  valid  util     ops      secs  Kops
 0       yes   90%    5694  0.001748  3258
 1       yes   92%    5848  0.001267  4616
 2       yes   95%    6648  0.004152  1601
 3       yes   96%    5380  0.004113  1308
 4       yes   66%   14400  0.000156 92072
 5       yes   91%    4800  0.004463  1076
 6       yes   89%    4800  0.004313  1113
 7       yes   55%   12000  0.020264   592
 8       yes   51%   24000  0.009431  2545
 9       yes   27%   14401  0.124472   116
10       yes   34%   14401  0.002566  5611
Total          71%  112372  0.176945   635

Perf index = 43 (util) + 40 (thru) = 83/100

课本版本(首次适配):

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.006908   824
 1       yes   99%    5848  0.005984   977
 2       yes   99%    6648  0.010540   631
 3       yes  100%    5380  0.007576   710
 4       yes   66%   14400  0.000112128917
 5       yes   92%    4800  0.006536   734
 6       yes   92%    4800  0.006056   793
 7       yes   55%   12000  0.140259    86
 8       yes   51%   24000  0.258947    93
 9       yes   27%   14401  0.097961   147
10       yes   34%   14401  0.002108  6833
Total          74%  112372  0.542987   207

Perf index = 44 (util) + 14 (thru) = 58/100

下一次适配:

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   91%    5694  0.001704  3342
 1       yes   92%    5848  0.001098  5328
 2       yes   95%    6648  0.003192  2083
 3       yes   97%    5380  0.003308  1627
 4       yes   66%   14400  0.000094153191
 5       yes   91%    4800  0.003757  1278
 6       yes   89%    4800  0.003610  1330
 7       yes   55%   12000  0.014973   801
 8       yes   51%   24000  0.007385  3250
 9       yes   27%   14401  0.097140   148
10       yes   45%   14401  0.002111  6822
Total          73%  112372  0.138371   812

Perf index = 44 (util) + 40 (thru) = 84/100