之前写过一篇为什么free函数不需要指定需要释放的内存大小，这个问题算是解释清楚了，但是针对malloc的实现又不怎么记得了，抽空又把《深入理解计算机系统》相关段落看了一遍，真的是好书啊！浅显易懂，真是适合我。
内存分配是按照堆块实现的，一个堆块是由头部和有效载荷量组成，其中的有效载荷量就是我们申请的堆的大小。
头部块包括 块大小和是否可用这两个部分组成。
在内存中这些堆块以链表形式组成
malloc函数的实质体现在：它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。调用malloc函数时，它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后，将该内存块一分为二（一块的大小与用户请求的大小相等，另一块的大小就是剩下的字节）。接下来，将分配给用户的那块内存传给用户，并将剩下的那块（如果有的话）返回到连接表上。
这里注意，malloc找到的内存块大小一定是会大于等于我们需要的内存大小，下面会提到如果所有的内存块都比要求的小会怎么办？
调用free函数时，它将用户释放的内存块连接到空闲链上。到最后，空闲链会被切成很多的小内存片段，如果这时用户申请一个大的内存片段，那么空闲链上可能没有可以满足用户要求的片段了。于是，malloc函数请求延时，并开始在空闲链上翻箱倒柜地检查各内存片段，对它们进行整理，将相邻的小空闲块合并成较大的内存块。
glibc维护了不止一个不定长的内存块链表，而是好几个，每一个这种链表负责一个大小范围，这种做法有效减少了分配大内存时的遍历开销，类似于哈希的方式，将很大的范围的数据散列到有限的几个小的范围内而不是所有数据都放在一起，虽然最终还是要在小的范围内查找，但是最起码省去了很多的开销，如果只有一个不定长链表那么就要全部遍历，如果分成3个，就省去了2/3的开销，总之这个策略十分类似于散列。
glibc另外的策略就是不止维护一类空闲链表，而是另外再维护一个缓冲链表和一个高速缓冲链表，在分配的时候首先在高速缓存中查找，失败之后再在空闲链表查找，如果找到的内存块比较大，那么将切割之后的剩余内存块插入到缓存链表，如果空闲链表查找失败那么就往缓存链表中查找. 如果还是没有合适的空闲块，就向内存申请比请求数更大的内存块，然后把剩下的内存放入链表中。
在对内存块进行了 free 调用之后，我们需要做的是诸如将它们标记为未被使用的等事情，并且，在调用 malloc 时，我们要能够定位未被使用的内存块。因此， malloc返回的每块内存的起始处首先要有这个结构：
这就解释了，为什么在程序中free之后，但是堆的内存还是没有释放。
内存控制块结构定义
struct mem_control_block {
int is_available;
int size;
};
现在，您可能会认为当程序调用 malloc 时这会引发问题 —— 它们如何知道这个结构？答案是它们不必知道；在返回指针之前，我们会将其移动到这个结构之后，把它隐藏起来。这使得返回的指针指向没有用于任何其他用途的内存。那样，从调用程序的角度来看，它们所得到的全部是空闲的、开放的内存。然后，当通过 free() 将该指针传递回来时，我们只需要倒退几个内存字节就可以再次找到这个结构。
在讨论分配内存之前，我们将先讨论释放，因为它更简单。为了释放内存，我们必须要做的惟一一件事情就是，获得我们给出的指针，回退 sizeof(struct mem_control_block) 个字节，并将其标记为可用的。这里是对应的代码：
解除分配函数
void free(void *firstbyte) {
struct mem_control_block *mcb;
/* Backup from the given pointer to find the
* mem_control_block
*/
mcb = firstbyte - sizeof(struct mem_control_block);
/* Mark the block as being available */
mcb->is_available = 1;
/* That''s It! We''re done. */
return;
}