malloclab 思路

结构综述

该堆为四层块结构，每层按粒度分配空间。结构末尾存有块信息。
逻辑地址空间与物理地址空间转换为 

vaddr = (addr - header_size) & (2M - 1)

实现细节

块结构按粒度从高至低分为 L3 L2 L1 L0，粒度分别为 2M 32K 512B 8B
大小为粒度*64，但只有62个块可以自由分配。

逻辑地址最后为当前最大块块头，初始时为 L0 。当分配块大于等于 64/2 = 32 或者当前块不足以分配时，进行块拓展操作。在原地新建一更高级块结构，当前块为更高级块的第一个子块。初始化父块的最后一子块，分配空间将当前块头拷入。将最大块块头初始化为父块块头。

但当 L2 拓展为 L3 时，容易发现按物理地址 L3 块最后的子块超出了 2M 范围，而将地址转换为逻辑地址后初始化时分配的块头和最后的 L2 块便在逻辑上连续。而位于末尾的块头必然是已分配状态，从而不会将物理上不连续的地址分配给用户。