黄阿信的个人博客

本实验要求我们实现一个简单的动态存储分配器，主要完成malloc、free和realloc的功能，实现过程要同时兼顾内存利用率和吞吐量。

话不多说，打开电脑，带上键盘，开启实验！

前置工作

apt-get install gcc-multilib

v1-实现

我们第一个版本主要抄一下教材9.9.12的代码，主要是实现最基本的功能，然后再考虑优化。

在教材的基础之上，我补充了mm_realloc的实现：

void* mm_realloc(void* bp, size_t size) {
    if(bp == NULL){
        return mm_malloc(size);
    }
    else if (size == (unsigned int)(0) && bp != NULL){
        mm_free(bp);
    }
    // 新块和旧块的部分内容必须相同
    // 相同部分的大小 = min(new_size, old_size)
    // 先申请一个新块，再拷贝，再free旧块
    // 这里所说的size指的是字节数，由于是双字对齐，
    // 因此size必然是8的整数倍，拷贝过程可以一次性拷贝4个字节
    char* new_bp = mm_malloc(size);
    if(new_bp == NULL){
        return NULL;
    }
    size_t copy_size = MIN(size, GET_BLOCK_SIZE(HEADER_PTR(bp)));
    char *src_ptr = bp, *dst_ptr = new_bp;
    size_t finish_size = 0;
    unsigned int word_content;
    for(; finish_size < copy_size; finish_size += 4){
        word_content = GET_WORD(src_ptr);
        PUT_WORD(dst_ptr, word_content);
        dst_ptr += 4;
        src_ptr += 4;
    }
    // 释放旧块
    mm_free(bp);
    return new_bp;
}

完整代码可以在【仓库】获得

注意事项

官网给的测试trace是少的，从pdf也可以看得出来，漏了个traces文件夹，该文件夹可以在我的【仓库】获得。

堆是往高地址增长的，因此下一块的地址比前一块的地址大，且脚部地址比头部地址大。

编写过程中，有的时候需要借助gdb进行调试，我们要在Makefile中修改为DEBUG模式并取消任何优化：

CFLAGS = -Wall -g -O0 -m32

调试步骤：

gdb ./mdriver
// 根据你要的进行下断点
// 如 break 文件名:行号
// 如 break 文件名:函数名
break mdriver.c:592
break mm.c:111
break mm.c:mm_init
// 运行
run -V  -f short1-bal.rep
run -V -f amptjp-bal.rep 
run -V -f random.rep 
// 查看指定内存的8个单元
x /8xh 0xf67ff018
// 查看调用堆栈
backtrace
// 条件断点：
break mm.c:mm_realloc if size == 8

我们也可以写一个打印空闲链表的函数，用于查看空闲链表：

void print_free_list(){
    char* bp = heap_listp;
    int cnt = 0;
    printf("\n----- free list -----\n");
    do {
        printf("block: %d\n", cnt++);
        printf("\theader ptr: %p, size: %d, alloc: %d\n", HEADER_PTR(bp), GET_BLOCK_SIZE(HEADER_PTR(bp)), GET_BLOCK_ALLOC(HEADER_PTR(bp)));
        printf("\tfooter ptr: %p, size: %d, alloc: %d\n\n", FOOTER_PTR(bp), GET_BLOCK_SIZE(FOOTER_PTR(bp)), GET_BLOCK_ALLOC(FOOTER_PTR(bp)));
        bp = NEXT_BLOCK_PAYLOAD_PTR(bp);
    } while (GET_BLOCK_SIZE(HEADER_PTR(bp)) > 0);
}

然后在mm.h中申明该函数，我们在调试mdriver.c的时候就可以方便调用call print_free_list()了。

测试

./mdriver -V -t ./traces
Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.006620   860
 1       yes   99%    5848  0.005870   996
 2       yes   99%    6648  0.010324   644
 3       yes  100%    5380  0.007445   723
 4       yes   66%   14400  0.000132108679
 5       yes   91%    4800  0.006580   729
 6       yes   92%    4800  0.006283   764
 7       yes   55%   12000  0.148051    81
 8       yes   51%   24000  0.256491    94
 9       yes   27%   14401  0.168535    85
10       yes   34%   14401  0.008131  1771
Total          74%  112372  0.624462   180

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

56分，比较一般，这是隐式空闲链表+首次匹配

v2-实现

由于我们使用的是隐式空闲链表，使得首次分配的分配时间为块总数的线性时间，我们可以使用显性空闲链表，把首次分配降到空闲块数量的线性时间，使用LIFO的方式维护链表。

此外，由于我们使用了显性空闲链表，最小的空闲块变大了，要至少能够装下前驱指针后后继指针，我们在分割空闲块的时候要注意这点。

原先用于对齐的那个内存单元可以用于保存第一个空闲块的地址。

下面的函数便于调试

void print_free_list(){
    char* bp = heap_listp;
    int cnt = 0;
    // 打印所有块
    printf("\n----- block list -----\n");
    do {
        printf("block: %d\n", cnt++);
        printf("\theader ptr: %p, size: %d, alloc: %d\n", HEADER_PTR(bp), GET_BLOCK_SIZE(HEADER_PTR(bp)), GET_BLOCK_ALLOC(HEADER_PTR(bp)));
        printf("\tfooter ptr: %p, size: %d, alloc: %d\n\n", FOOTER_PTR(bp), GET_BLOCK_SIZE(FOOTER_PTR(bp)), GET_BLOCK_ALLOC(FOOTER_PTR(bp)));
        bp = NEXT_BLOCK_PAYLOAD_PTR(bp);
    } while (GET_BLOCK_SIZE(HEADER_PTR(bp)) > 0);


     cnt = 0;
    printf("\n\n===== free list =====\n");
    printf("\tfirst free block ptr:%p\n", GET_WORD((char *)(heap_listp) - 2 * WSIZE));
    // 打印所有空闲块
    // 获取第一个空闲块地址
    char *first_free_block_bp = GET_WORD((char *)(heap_listp) - 2 * WSIZE);
    bp = first_free_block_bp;
    for(;bp != NULL;bp = GET_WORD(SUCC_PTR(bp))){
        printf("block: %d\n", cnt++);
        printf("\theader ptr: %p, size: %d, alloc: %d\n", HEADER_PTR(bp), GET_BLOCK_SIZE(HEADER_PTR(bp)), GET_BLOCK_ALLOC(HEADER_PTR(bp)));
        printf("\tpred block bp: %p\n", GET_WORD(PRED_PTR(bp)));
        printf("\tsucc block bp: %p\n", GET_WORD(SUCC_PTR(bp)));
        printf("\tfooter ptr: %p, size: %d, alloc: %d\n\n", FOOTER_PTR(bp), GET_BLOCK_SIZE(FOOTER_PTR(bp)), GET_BLOCK_ALLOC(FOOTER_PTR(bp)));

    } 
}

测试

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   89%    5694  0.001498  3800
 1       yes   92%    5848  0.001231  4751
 2       yes   94%    6648  0.001989  3342
 3       yes   96%    5380  0.001337  4023
 4       yes   66%   14400  0.000198 72727
 5       yes   86%    4800  0.005451   881
 6       yes   85%    4800  0.005552   865
 7       yes   55%   12000  0.046197   260
 8       yes   51%   24000  0.216260   111
 9       yes   26%   14401  0.116903   123
10       yes   34%   14401  0.005556  2592
Total          70%  112372  0.402172   279

Perf index = 42 (util) + 19 (thru) = 61/100

显示空闲链表+首次匹配，看来提升不大。吞吐量上来了，利用率竟然下降了

完整代码可以在【仓库】获得

v3-实现

显示空闲链表+首次匹配+分离适配

在一开始的时候申请9个字的空间，分别用于存放不同大小类的头指针，划分的方式是根据2的幂来划分。

为什么是9个？实际上是为了对齐，即满足8*k+1即可，k是正整数

第一个指针指向块大小是4096以上（包含4096）的，第二个指向2048（包含2048）到4096的，以此类推，最后的指向大小低于32的（不包括32）。

测试

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   98%    5694  0.000325 17493
 1       yes   94%    5848  0.000378 15491
 2       yes   98%    6648  0.000410 16234
 3       yes   99%    5380  0.000353 15258
 4       yes   66%   14400  0.000441 32616
 5       yes   87%    4800  0.002970  1616
 6       yes   85%    4800  0.002823  1700
 7       yes   55%   12000  0.014242   843
 8       yes   51%   24000  0.062740   383
 9       yes   30%   14401  0.118283   122
10       yes   45%   14401  0.006070  2372
Total          73%  112372  0.209035   538

Perf index = 44 (util) + 36 (thru) = 80/100

这次吞吐量提升巨大！

下面的函数便于调试

void print_free_list(){
    char* bp = heap_listp;
    int cnt = 0;
    // 打印所有块
    printf("\n----- block list -----\n");
    do {
        printf("block: %d\n", cnt++);
        printf("\theader ptr: %p, size: %d, alloc: %d\n", HEADER_PTR(bp), GET_BLOCK_SIZE(HEADER_PTR(bp)), GET_BLOCK_ALLOC(HEADER_PTR(bp)));
        printf("\tfooter ptr: %p, size: %d, alloc: %d\n\n", FOOTER_PTR(bp), GET_BLOCK_SIZE(FOOTER_PTR(bp)), GET_BLOCK_ALLOC(FOOTER_PTR(bp)));
        bp = NEXT_BLOCK_PAYLOAD_PTR(bp);
    } while (GET_BLOCK_SIZE(HEADER_PTR(bp)) > 0);


    for(int i = 0; i < 9; i++){
        cnt = 0;
        printf("\n\n#### free list [%d-%d) ####\n", 1 << (i + 4),1 << (i + 5));
        printf("\tfirst free block ptr:%p\n", GET_WORD((char *)(heap_listp) - 2 * WSIZE - i * WSIZE));
        // 打印所有空闲块
        // 获取第一个空闲块地址
        char *first_free_block_bp = GET_WORD((char *)(heap_listp) - 2 * WSIZE - i * WSIZE);
        bp = first_free_block_bp;
        for(;bp != NULL;bp = GET_WORD(SUCC_PTR(bp))){
            printf("block: %d\n", cnt++);
            printf("\theader ptr: %p, size: %d, alloc: %d\n", HEADER_PTR(bp), GET_BLOCK_SIZE(HEADER_PTR(bp)), GET_BLOCK_ALLOC(HEADER_PTR(bp)));
            printf("\tpred block bp: %p\n", GET_WORD(PRED_PTR(bp)));
            printf("\tsucc block bp: %p\n", GET_WORD(SUCC_PTR(bp)));
            printf("\tfooter ptr: %p, size: %d, alloc: %d\n\n", FOOTER_PTR(bp), GET_BLOCK_SIZE(FOOTER_PTR(bp)), GET_BLOCK_ALLOC(FOOTER_PTR(bp)));

        } 
    }
}

完整代码可以在【仓库】获得

后记

其实所谓的堆管理器，就是在用户空间指定的一段区域内（堆开始和堆结束之间），维护一段一段内存区域（即所谓的块）的空闲与否，当有新的需求无法满足时，再向操作系统请求对堆进行缩小或者扩展，因此当我们堆中存在空闲块的时候，在操作系统看来，该程序占用的内存比实际占用的要大。

当然后面还可以继续在各种细节优化，例如采用下次匹配、延迟合并和采用红黑树等策略，但是我不想再继续和gdb打交道了，我表示再也不想看到gdb了！

CS:APP-Malloc Lab

前置工作

v1-实现

注意事项

测试

v2-实现

测试

v3-实现

测试

后记