设计并实现一个堆区动态内存分配器mm，提供接口mm_malloc、mm_realloc、mm_free（对应于GNU libc的malloc、realloc、free）。mm设定堆区内存为32位，并采用8字节内存对齐。Lab提供一个测试程序和许多trace文件，用于评估mm的内存利用和吞吐量性能。
-
编译
make
-
运行简单样例
./mdriver -g -V -f short1-bal.rep
-
运行复杂样例
./mdriver -g -V -l
运行结果：
Results for libc malloc: trace valid util ops secs Kops 0 yes 0% 5694 0.0002113 26947 1 yes 0% 5848 0.0001611 36300 2 yes 0% 6648 0.0004267 15580 3 yes 0% 5380 0.0004252 12653 4 yes 0% 14400 0.0003131 45992 5 yes 0% 4800 0.0003426 14011 6 yes 0% 4800 0.0002818 17033 7 yes 0% 12000 0.0002013 59613 8 yes 0% 24000 0.0003290 72948 9 yes 0% 14401 0.0007387 19495 10 yes 0% 14401 0.0001444 99730 Total 0% 112372 0.0035752 31431 Results for mm_malloc: trace valid util ops secs Kops 0 yes 99% 5694 0.0001897 30016 1 yes 99% 5848 0.0001884 31040 2 yes 99% 6648 0.0002312 28754 3 yes 100% 5380 0.0001881 28602 4 yes 100% 14400 0.0002546 56559 5 yes 94% 4800 0.0003723 12893 6 yes 93% 4800 0.0003657 13126 7 yes 55% 12000 0.0039371 3048 8 yes 51% 24000 0.0140888 1703 9 yes 28% 14401 0.0009133 15768 10 yes 38% 14401 0.0002875 50090 Total 78% 112372 0.0210167 5347
mm总体上基于隔离空闲链(Segregated Free Lists)的方式维护空闲块。将空闲块根据块大小划分到不同的空闲块类中，每个类中的空闲块组成一个空闲链。与单个空闲链相比，隔离空闲链能够使得动态内存分配器具有更高的吞吐量和空间利用率。由于采用了多个空闲链，查找空闲块时只需搜索部分空闲块，减小了查找时间，因此吞吐量更高。由于基于块大小划分空闲链，查找空闲块时更容易匹配到大小最合适的空闲块，因此空间利用率更高。具体地，mm采用Segregated Fits方法，详细设计要点描述如下。
-
空闲块组织 (Organization)
-
块格式
空闲块开头是header字段，接着是该块在空闲链中的前驱指针(pred)和后继指针(succ)，块的最后是footer字段，内容与header一致，目的是便于向前合并空闲块。对于header字段，因为块大小是8的倍数，所以header的低3位可用作标记。其中，a0表示当前块是空闲还是已分配，a1表示紧邻的上个块是空闲还是已分配，a2暂时保留。空闲块的格式使得最小块大小为4*4=16Bytes。
已分配块包括开头的header字段和分配给用户的Payload区域。已分配块不需要footer字段，得益于a1的设置。已分配块的下一个相邻块通过a1判断其上一个块是已分配的，因此不会尝试解析上一个块的footer来做进一步合并操作。
-
空闲块分类和空闲链组织
空闲块以2的次幂大小分成如下20类：{16} {17-32} {33-64} {65-128} {129-256} {257-512} {513-1024} {1025-2048} {2049-4096} ...... {(2M+1)-4M} {(4M+1)-∞}。
每一类空闲块按照内存顺序组成空闲链。一个包含两个空闲链的堆区内存布局示例如下图所示。其中，开头绿色4字节作为填充，保证后续块的Payload地址是8字节对齐。末尾绿色4字节包含header字段，块大小是0，a0设1，用于简化空闲块合并时的边界判断逻辑。蓝色填充块是已分配块，未填充块是空闲块。空闲块组成了2条空闲链。
last_block指针永远指向最后一个块的payload，在扩展堆区大小时会用到。
-
-
空闲块定位 (Placement)
空闲块定位采用first-fit方式。对于一个空闲块请求，找到其所在的类，在该类对应的空闲链查找空闲块，若没有空闲块，则查找下一个空闲链，依此类推，直到找到第一个空闲块为止。若还是没有找到空闲块，则扩展堆区容量，创建一个新的空闲块。
-
划分空闲块 (Splitting)
定位到空闲块之后，若在满足内存请求的前提下，该空闲块还能剩下至少最小块大小16Bytes的空间，则将该空间划分出来单独形成一个空闲块，并添加至对应的空闲链中。
-
合并空闲块 (Coalescing)
在已分配块被释放变成空闲块之后，立即尝试合并前后相邻的空闲块。合并后的空闲块添加至对应的空闲链中。
mm.{c,h}：动态内存分配器mm源代码，提供接口mm_malloc、mm_free、mm_reallocmdriver.c：动态内存分配器mm的测试程序short{1,2}-bal.rep：简单的malloc测试用例，用于帮助验证mm的正确性traces/：复杂测试用例，用于测试mm的性能timer/：计时模块，提供测量函数执行用时的接口mem/memlib.c：模拟堆区内存，提供管理堆区的接口如sbrk等
- 了解动态内存分配器的性能目标和设计思想；
- 掌握基于Segregated Fits方法来管理空闲块的思想；
- 掌握C语言直接编写内存级别的底层代码的要点，如内存对齐、指针类型转换等。