malloc
malloc函数大家都用的很多，但是具体实现可能确实没怎么考虑。
void *malloc(size_t size)
他需要做的事情和要求如下：
1.分配一段size个Bytes大小的堆空间(后来才知道是至少size大小)，并返回一个void*类型的指针，指向这段空间的首地址。如果分配失败，返回NULL
2.每次分配的时候，必须是合法的地址空间，也即如何保证不会是之前分配过的。
3.便于free释放，因此必须free时候需要知道size大小，也即要和free realloc等配套使用，因此设计的DS必须兼顾
假设一段heap空间，Linux有一个break指针记录之前已经分配的空间的高地址，再高的部分就是非法地址了。因此一个toy的malloc可以借助sbrk函数来实现，
int brk(void addr);
void sbrk(intptr_t increment);
第一个函数将break上移increment字节大小，然后返回break之前的地址
这样借助sbrk函数可以完成，但是不好free因为没有记录这些大小，以及之前的首地址
#include <sys/types.h>
#include <unistd.h>
void *malloc(size_t size)
{
void *p;
p = sbrk(0);
if (sbrk(size) == (void *)-1)
return NULL;
return p;
}
然后考虑使用链表来实现空间分配，将malloc的空间练成linklist，因为频繁插入删除，比数组好(我之前也觉得链表没啥用的，可以看下，这个是OS的实现)
然后首次适应和最佳适应的策略还历历在目，首次适应就需要split多余的空间提高空间利用效率，防止出现假满。
#define BLOCK_SIZE 24
void *first_block=NULL;
/* other functions... */
void *malloc(size_t size) {
t_block b, last;
size_t s;
/* 对齐地址 */
s = align8(s);
if(first_block) {
/* 查找合适的block */
last = first_block;
b = find_block(&last, s);
if(b) {
/* 如果可以，则分裂 */
if ((b->size - s) >= ( BLOCK_SIZE + 8))
split_block(b, s);
b->free = 0;
} else {
/* 没有合适的block，开辟一个新的 */
b = extend_heap(last, s);
if(!b)
return NULL;
}
} else {
b = extend_heap(NULL, s);
if(!b)
return NULL;
first_block = b;
}
return b->data;
}
以上几乎是码代码的张洋最新的blog笔记，新鲜出炉，学习一下，面试可能探讨会涉及~~~~
http://blog.codinglabs.org/articles/a-malloc-tutorial.html