实验目标

你要完成malloc, free, realloc 函数的实现；给予你一个模拟的堆空间，每次模拟分配/释放一段空间，当堆大小不够时进行扩展。

方法

实现malloc有几种方法：隐式链表、显式链表、分离适配（多级链表）、伙伴系统等等。一般而言最优解为采用显式链表+多级链表的形式，每一级列表只存储大小在[2^i, 2^(i+1)）之间的块，需要时直接在里面找，把malloc完剩余的块丢到对应的堆里面去。而显式链表的作用在于优化了free时合并相邻空闲块的步骤：采用隐式链表，需要在每个表里寻找相邻块并将之删除（因为要合并为一个更大的块），而显式链表的话每个块内部存储了指针，可以直接找到其在多级列表中的位置。

一些必要的参数

由于本题特殊性，不能开全局变量，故所有数据结构都要存到堆里，不够再分配。

设fp = first pointer 为堆首指针，*(int*)fp简记为*fp表示取4字节得到的值。则：*fp 为链表堆的堆顶指针（链表堆是专门分配链表结点的空间）， *(fp+4)为链表回收指针（垃圾回收），*(fp+8)为链表堆最大大小（若*fp 超过这个大小则要再分配一段链表堆）, *(fp + 12), *(fp + 16)为当前最小、最大已分配块的大小，*(fp + 20 ... 76) 为表头a[0...19]，意义如上所述。

每个链表结点的大小为12，分别存4字节next、data、prep(int类型的offset，使用时以fp进行映射)，表示下一个结点、结点对应的块地址（若存在）、上一个结点（无则为-1）.

每个块内部碎片为16，包括8字节HEADER和8字节FOOTER，HEADER存4字节块大小和4字节指向它的链表的地址，FOOTER存4字节块大小和4字节识别符KEY（程序自定义的常数，用于检测该块属于链表堆区或分配堆区）.

函数实现

malloc：

（1）在链表里找第一个合适的块（first-fit)，若找到，判断大小是否正好，若正好则将链表结点删除；若块更大，取剩余块，将该链表结点删除，安排新链表结点链接至该剩余块，安排进入新的链表位置。

（2）若未找到这样的块，申请堆分配更多的空间，一般为分配等malloc size大小的空间，也可以是至少page大小的空间，重复（1）.

优化/tips:

（1）若剩余块在第i个链表，原块也在第i个链表，则不用重新安排插入、分配新链表结点，而是修改链表结点信息即可。

（2）找到块后，若块大小小于某一值K，则分配在块左侧；否则分配在块右侧。这是特别针对某一binary数据的写法。

（3）分配后可能出现这样的情况：剩余块的大小<=内部碎片（即HEADER+FOOTER)的大小，这样即使插入链表也没用，但不插入又可能造成浪费（永远无法再次使用）。由于块为8对齐，这样的块大小至少为8，出现这样的情况时要特殊判断。

free:

先确定相邻块是否是heap块且为空块，若是，将其从链表中删除，合并后形成新块加入新的链表。

优化/tips:

与malloc类似，如果...大小不变可以不用删除而是修改链表结点信息。

用KEY（识别符）判断很方便且出错概率很低，但也可能出现访问KEY所在地址发生SEGMENT FAULT的情况，需要先判断该地址是否合法（建议用和fp的相对地址进行比较；还要考虑是否越界）。

realloc:

malloc+free方法略。

优化：

若长度小于原长度，直接分割；若长度大于原长度，先判断块右侧是否有足够的空间，若有，删除、合并、加入链表，更新一堆东西。

其他优化/Tips

分配新空间/新块时不必memset，去掉memset能够使Kops上升一大截。

请务必写好必要的调试工具，如最好打印每次操作后整个堆区的运行情况，这样更容易debug.(只打印一些片段信息（如在每个函数段调用mm_check()）在debug时真的很困难且麻烦= =.)

一些需要注意的细节如：链表的前驱/后继更新；一块空间被多个链表结点引用（一些地方缺乏更新）；内部碎片处理等，这些每一个都耗费了笔者非常多的调试时间，导致在ddl最后也没能写好较为完美的程序，拿到很高的分数。

实验结果

多级链表+隐式链表：

多级链表+显式链表：

将memset全部去掉后：

8号点（binary）和9号点（realloc）预计均为mm_sbrk调用次数较多的点，因此效率较差，若时间足够将进一步进行对程序进行优化。