用于内存管理的malloc与free这对函数，对于使用C语言的程序员应该很熟悉。前段时间听说有的IT公司以“实现一个简单功能的malloc”作为面试题，正好最近在复习K&R，上面有所介绍，因此花了些时间仔细研究了一下。毕竟把题目做出来是次要的，了解实现思想、提升技术才是主要的。本文主要是对malloc与free实现思路的介绍，蓝色部分文字是在个人思考中觉得比较核心的东西；另外对于代码的说明，有一些K&R上的解释，使用绿色加亮。
在研究K&R第八章第五节的实现之前，不妨先看看其第五章第四节的alloc/afree实现，虽然这段代码主要目的是展示地址运算。
#define ALLOCSIZE 10000
static char allocbuf[ALLOCSIZE]; /*storage for alloc*/
static char *allocp = allocbuf; /*next free position*/
char *alloc(int n)
{
if(allocbuf+ALLOCSIZE - allocp >= n) {
allocp += n;
return alloc - n;
} else
return 0;
}
void afree(char *p)
{
if (p >= allocbuf && p<allocbuf + ALLOCSIZE)
allocp = p;
}
</div>
这种简单实现的缺点：
1.作为代表内存资源的allocbuf，其实是预先分配好的，可能存在浪费。
2.分配和释放的顺序类似于栈，即“后进先出”，释放时如果不按顺序会造成异常。
这个实现虽然比较简陋，但是依然提供了一个思路。如果能把这两个缺点消除，就能够实现比较理想的malloc/free。
仅仅依靠地址运算来进行定位，是限制分配回收灵活性的原因，它要求已使用部分和未使用部分必须通过某个地址分开成两个相邻区域。为了能让这两个区域能够互相交错，甚至其中还包括一些没有分配的地址空间，需要使用指针把同类的内存空间连接起来形成链表，这样就可以处理地址不连续的一系列内存空间。但是为什么只连接了空闲空间而不连接使用中的空间？这么问可能出于在对图中二者类比时的直觉而没有经过思考，这很简单，因为没有必要。前者相互链接是为了能够在内存分配时遍历所有空闲空间，并且在使用free()回收已使用空间时进行重新插入。而对于使用中的空间，由于我们在分配空间时已经知道它们的地址了，回收时可以直接告诉free()，并不用像malloc()时进行遍历。
既然提到了链表，可能对数据结构稍有了解的人会立刻写下一个struct来代表一个内存区域，其中包含一个指向下一个内存区域的指针，但是这个struct的其他成员该怎么写呢？作为待分配的内存区域，大小是不定的，如果把它声明为struct的成员变量显然不妥；如果声明为一个指向某个其他的区域的指针，这似乎又和上面的直观表示不相符合。（当然，这么做也是可以实现的，它看上去是介于上图的两者之间，把管理结构和实际分配的空间相剥离，在文末我会专门的讨论一下这种实现方法）因此，这里仍然把控制结构和空闲空间相分开，但保持它们在内存地址中相邻，形成下图的形式，而正由这个特点，我们可以利用对控制结构指针的指针运算来定位对应的内存区域：
对应地，把控制信息定义为Header：
typedef union header Header;
</div>
这样，malloc的主要工作就是对这些Header和其后的内存块的管理。
static Header base;
static Header *freep = NULL;
void *malloc(unsigned nbytes)
{
Header *p, *prevp;
unsigned nunits;
nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
if((prevp = freep) == NULL) { /* no free list */
base.s.ptr = freep = prevp = &base;
base.s.size = 0;
}
for(p = prevp->s.ptr; ;prevp = p, p= p->s.ptr) {
if(p->s.size >= nunits) { /* big enough */
if (p->s.size == nunits) /* exactly */
prevp->s.ptr = p->s.ptr;
else {
p->s.size -= nunits;
p += p->s.size;
p->s.size = nunits;
}
freep = prevp;
return (void*)(p+1);
}
if (p== freep) /* wrapped around free list */
if ((p = morecore(nunits)) == NULL)
return NULL; /* none left */
}
}
</div>
实际分配的空间是Header大小的整数倍，并且多出一个Header大小的空间用于放置Header。但是直观来看这并不是nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1啊？如果用(nbytes+sizeof(Header))/sizeof(Header)+1岂不是刚好？其实不是这样，如果使用后者，nbytes+sizeof(Header)%sizeof(Header) == 0时，又多分配了一个Header大小的空间了，因此还要在小括号里减去1，这时才能符合要求。
malloc()第一次调用时建立一个退化链表base，只有一个大小是0的空间，并指向它自己。freep用于标识空闲链表的某个元素，每次查找时可能发生变化；中间的查找和分配过程是基本的链表操作，在空闲链表中不存在合适大小的空闲空间时调用morecore()获得更多内存空间；最后的返回值是空闲空间的首地址，即Header之后的地址，这个接口与库函数一致。
#define NALLOC 1024 /* minimum #units to request */
static Header *morecore(unsigned nu)
{
char *cp;
Header *up;
if(nu < NALLOC)