csapp:malloclab

建立一个动态内存分配器。

---

内存的组织形式大致有三种。隐式空闲链表，显式空闲链表，以及分离的空闲链表。而内存的分配策略也大致分为三种，最先分配，下一次分配和最优分配。而内存的合并策略则是立即合并和延迟合并。

合并策略就很直观，当你归还内存的时候，我将我前后的空闲块合并起来变成一个大的空闲块，这样，就可以让我的内存碎片变少。立即合并就是立即做这件事，而推迟合并就是在合适的时候才做这件事。至于合适的时候是什么时候，就是仁者见仁了。

最先分配就是最先遇到的合适的内存块就分配出去，下一次分配就是从上一次分配的地方开始寻找，而最优分配就是遍历整个堆空间，找到最合适的空闲块分配出去。

隐式空闲链表 + 首次分配 + 立即合并

隐式空闲链表就是，将分配的内存大小保存在内存块的头部，当你需要分配的时候，只需要遍历整个堆空间，找到相应大小的块，然后，按照分配策略就可也分配出想要的块出来了。其内存的组织形式大概是这样

struct block
{
	unsigned int header;
	char payload[N];  //负载元素
	char extend[M];   //字节对齐
	unsigned int footer;
}

书上有代码介绍的也是这种方式。

实现出来的效果其实也不差。

Using default tracefiles in traces/
Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.006654   856
 1       yes   99%    5848  0.006160   949
 2       yes   99%    6648  0.010249   649
 3       yes  100%    5380  0.007564   711
 4       yes   66%   14400  0.000107135084
 5       yes   93%    4800  0.006334   758
 6       yes   92%    4800  0.006370   754
 7       yes   55%    6000  0.030002   200
 8       yes   51%    7200  0.023748   303
 9       yes   27%   14401  0.127947   113
10       yes   34%   14401  0.002625  5487
Total          74%   89572  0.227759   393

Perf index = 44 (util) + 26 (thru) = 71/100

可以看出，吞吐量虽然不高，不过内存利用率还是不错的。吞吐量不高的原因应该是因为每一次的内存的分配都要从堆的开头开始寻找，因此，当前面的内存都是以分配的时候，就会耗费大量的时间去分配内存了。

分离适配链表 + 首次适配 + 立即合并

显式链表其实是对隐式链表的升级，在之前，由于隐式链表的存在，我们只知道分配块的大小而不知道空闲块的地址，因此，只能从堆开头去寻找合适的空闲块，因此，我们在这里，可以用链表的形式将所有的空闲块串在一起，那么，我们搜索空闲块就只需要从空闲块中寻找了。其形式大致是这样的。

struct block
{
	unsigned int header;
	union{
		struct pointer{
			unsigned int * next;
			unsigned int * prev;
		}
		struct alloc{	
			char payload[N];
			char extend[M];
		}
	};
	unsigned int footer;
}

由于当内存被归还的时候，负载的内容都是不需要的，因此，我们就可以利用那里的内容去组织成指针，用来记录空闲块。

而分离适配链表就是显式链表的升级版。

分离适配链表，将不同大小的块分为不同的大小类，每一个大小类都维护着一块链表。比如，大小为16-32的块是一个大小类，那么当我要申请一个18大小的内存的时候，只需要从16-32的大小类开始寻找就可以了。可以避免去2-4之类的更小的类去寻找内容，节省了查找空闲块的时间。这样需要，在一开始，就为大小类们分配一个数组，数组的内容为他们的根结点，这样，就可以很轻松的组织这个大小类链表了。

其实代码方面和隐式分配链表是差不多的，就是在查找合适的块(find_fit)的时候是用链表去查找，以及合并，归还，分配块的时候，要对这个双向链表的指针进行一次调整而已。

Measuring performance with gettimeofday().

Results for mm malloc:
trace  valid  util     ops      secs  Kops
 0       yes   99%    5694  0.000210 27114
 1       yes   99%    5848  0.000192 30427
 2       yes   99%    6648  0.000240 27677
 3       yes  100%    5380  0.000207 25940
 4       yes   66%   14400  0.000244 58992
 5       yes   93%    4800  0.000986  4866
 6       yes   91%    4800  0.000960  4999
 7       yes   55%    6000  0.001979  3032
 8       yes   51%    7200  0.002620  2748
 9       yes   43%   14401  0.000562 25638
10       yes   52%   14401  0.000248 58045
Total          77%   89572  0.008449 10601

Perf index = 46 (util) + 40 (thru) = 86/100

恩，良好的吞吐量和内存利用率

不过当你用./mdriver -t traces/ -v -l -a去对比libc的数据的话，发现，确实差距挺明显的orz;