.data 内存段、.text 内存段、共享对象内存段在程序加载和链接时就确认了一个不会变的地址范围，而 stack 内存段范围随着函数栈而自动伸缩，不在开发者的掌握之中。如果开发者想要自由地使用一点内存，就要通过 malloc 向 heap 内存申请一段空间来使用。
但 heap 内存空间也不是无限的，如何高效利用 heap 内存空间也就显得很重要了。
高效利用 heap 内存的第一关键点在于回收不再使用的空间，第二点在于分配时合理利用空闲空间。
一、heap 内存空间的空闲/占用状态
不管是分配还是回收一段内存，都要求我们能够快速得知这段内存的起止地址，并且能轻易改变它的状态。
那我们怎么做呢？对于一段位置已知的内存段，每个 Bit 只能保存一个 Bit 的信息，而“空闲-已分配”刚好一个 Bit 的信息，因此内存是否被占用是不可能保存在内存段内的比特位上面的。
还可以借鉴 vm_area_struct 的做法，把已占用的内存段的范围记录起来，保存到一个链表里。这样每查询空闲内存段时，遍历所有已分配的内存段的范围。但是这样也不行。假如记录一个范围需要两个 int 数据，那就要 8 + 1(bool) 字节。而如果我申请的只是一个 8 个字节的 int 类型的空间，那光记录就用掉了 9 字节。如果内存段本身更小的话，记录内存段范围所使用的内存有可能比内存段本身还多。
实际采用的方案是上述方案的变种，它利用了这样一个事实来减少对额外空间的需求：申请一段内存后会返回申请到的内存段的首字节地址给申请者作为指针。于是内存段的起始地址不需要记录下来，交给开发者去维护。操作系统只需要把申请的到内存段的大小和状态被保存在指针(首地址)的前 1 个字的头部里面(或者两个，取决于操作系统位数)，就能保存内存段的范围和状态了。
1 个字能覆盖所有的内存段大小并记录状态吗？答案是能。以 32 位操作系统来说，一个内存段大小的理论上限是 2 ^ 32 个字节。但是考虑到内存对齐要求，内存分配的最小单位是 2 ^ 3 个字节，所以内存段大小永远是 8 的倍数。也就是只需要 29 个比特就能记录所有内存段的大小，还有 3 个比特可以用来记录其它信息。于是在最低位三个比特中，一个比特就拿来记录内存段是否被占用。
这种方法实际上也实现了一个能够快速访问所有内存段的单向链表。由一段内存的首字节指针获得其头部地址，从中获知这段内存的长度，就能获得了下一段内存头部地址。当得到一段长度为 0 的空闲内存段时，就表明已经遍历到最后一个内存段了。
使用这种方法的优点和缺点都很明显。优点在于它额外内存要求低，而且速度快。它很容易就能从一个指针知道内存段的起止位置，也很容易就能获知以及改变内存段的空闲/占用状态。缺点在于它只能基于指针来判断，而对于指针是否合法是不做判断的。如果给定的指针不是一段内存的首地址，它也会把它前面一个字当做头部来读写。
二、分配/回收 heap 内存
上述内存段链表使我们获得了快速得知所有内存段的大小和状态的方法，接下来我们看看怎么使用它来分配和回收内存。
在最开始的情况下，把 heap 分区当成一个跨越整个分区的空闲内存段，开始地址是 char* base，总大小为 24，(int *)base 处的四字节保存状态 0x0 以及长度 16。最后还有一个特殊字标志长度为 0 的空闲内存作为 heap 分区的结尾。
当要分配 12 个字节的时候，头部 (int *)base 处的四字保存状态 0x1 。由于对齐要求，最少要分配 16 个字节，于是 *(int *) base 保存长度 0x10，最终值为 0x10 | 0x1 = 0x11。设置好 (int *)base 的值后，再设置下一个空闲头部 *(int *)(base + 20) = 24 - 20 - 4, 然后返回 base + 4 给调用者作为指针 p。调用者自己有义务不要使用超过 (char*) p + 11 范围的内存，否则可能会导致内存问题。有可能会没事，有可能会复写其它内存段的数据或者被其它内存段复写，也有可能触发段错误。
当再要分配 4 个字节的时候， 操作系统从头部 (int *)base 知道 base 到 base + 19 都被占用了，从下一个头部 (int *)(base + 20) 知道接下来没有空闲 heap 内存空间了。于是调用 sbrk 申请扩容 heap 内存空间，得到一段新的空闲内存段，更新 (int *)(base + 20) 并设置新的尾部标志。之后再开始正常的分配流程。假设 H 是扩容后的 heap 总大小，*(int *)(base + 20) = 0x8 | 0x1，*(int *)(base + 32) = H - 32, 返回 base + 24 给调用者做指针 p2。
如果此时对 p 执行 free 操作回收内存，则只需要把 * (((int *)p) - 1) = * (((int *)p) - 1) & ~0x7，也就是把低 3 位设置为 0。
释放 p 后，*(int *)base 的值为 0x10，意味着 (char *)base + 4 到 (char *)base + 19 是空闲空间，可以拿来做分配。
如果之后需要分配 8 个字节，可以从 p2 前面的 16 个字节的空间空间分配，也可以从 p2 后面的空闲空间分配，具体分配哪个区间的空闲区间取决于搜寻空闲空间的算法。但是如果需要分配 20 个字节，那就只能从 p2 后面的空间分配，因为只能分配连续的空闲空间。
如果释放 p 后，立即释放 p2。按照之前的做法，只需要执行 *((char *)p2 - 4) = *((char *)p2 - 4) & ~0x7 就可以了。此时，p 和 p2 分表代表两段大小为 16 和 4 字节的空闲内存段。如果要分配 20 字节的空间，p 查得 16 字节空闲空间，不合适，p2 查得 4 字节空闲空间，也不合适。即使有 21 个字节的总空闲空间，但是还是不能被好好利用。这个时候，就需要在释放空间后尝试合并前后相邻的空闲空间。
正如我们所发现的，如何搜寻空闲空间和如何合并空闲空间，是合理利用回收空间的关键，下面我们来专门讨论它们。
三、合理利用空闲内存空间
3.1 搜寻空闲空间
当为一次内存申请搜寻空间时，搜寻时间和搜得空间的匹配度是两个重要的性能指标。前者反映搜寻的速度，后者反映对空间的利用效率。
最好的算法当然是用最少的时间找到最小的适合需求的空闲内存段。但是后者要求对所有的空闲内存段有所了解，因此要求更彻底的搜寻，以及更长的搜寻时间。因此，二者可以说互相矛盾。
基于对二者的取舍，衍生出了三种简单的搜寻策略：
- 最佳适配。搜寻所有的空闲空间，找到最合适的。速度最慢，空间利用率最高
- 首次适配。从头开始搜寻，使用第一个找到的可用的空闲空间。速度较快，空间利用率较高
- 下一次适配。从上一个找到适配的位置开始搜寻，使用第一个找到的可用空闲空间。速度最快，空间利用率较差
为了进一步优化搜寻算法，我们可以尝试减少搜寻的次数，也可以尝试把大小接近的空闲内存段组织在一起，根据所需空间去不同的集合搜寻。
对于前者，一种实现方式是把所有空闲内存段显示地链接在一起形成空闲内存链表。在之前的内存段单向链表中，所有内存段都被链接在一起，而内存段是否是空闲的则通过头部的 flag 来隐式地表示。为了遍历所有的空闲内存段，需要遍历所有的内存段。如果使用显示空闲内存链表，则每次搜寻空闲内存段时只需要搜寻少量的空闲内存链表，不需要搜寻整个内存链表。其实现方式是在每个空闲内存块的头部之后记录后一个空闲内存段的头部地址。它的缺点是空闲内存段必须足够大以放得下必要的指针。
对于后者，有诸多基于显示空闲链表的改良方案。其总体思路是维护多个显示空闲链表，每个链表中的空闲内存段的大小在一个特定范围内，并且按升序排列。比如说大小为 1 的属于一个链表，大小为 2 的属于一个链表，大小为 3~4 的属于一个链表，大小为 5~8 的属于一个链表。
首先是简单分离存储。每一类空闲链表中的内存块都是一样大的，比如 5~8 大小的链表中的块都是 8 字节大小。每当要分配一个大小为 n 的内存块时，把 n 向上取整到 2 的整数次幂，然后到对应的空闲链表中去搜索。如果空闲链表不为空，从里面使用首次适配选取一个。如果空闲链表为空，或者没有找到对应大小的空闲链表，就申请扩容 heap 内存区，把新拿到的内存区划分为对应大小的链表，再从中使用首次适配选择一个空闲内存段。每当释放一个大小为 n 的内存块时，把对应空闲链接表的首指针改成这个内存块就好了。
它的优点在于，分配和释放都是常数级操作。由于每个内存块的大小都是固定的，因此空闲内存块不需要头部，增加了对小范围空闲地址的回收效率。它的缺点在于，分配的内存块都是固定大小的，因此会造成浪费。
然后是分离适配。每一类空闲链表中的内存块是接近的，比如 5~8 大小的链表中的块在 5~8 范围波动。每当要分配一个大小为 n 的内存块时，找到对应的空链链表。如果链表不为空，使用首次适配方法找到一个空闲块，从中分割出最适配的大小块用作分配，把剩余的空间作为一个空闲块插入到更小的空闲链表中去。如果没有找到对应的链表，或者链表为空，就申请扩容 heap 内存，把新拿到的内存分割出最适配的大小用于分配，把剩下的划分到最大的空闲链表中去。每当释放一个大小为 n 的内存块时，就把它插入到对应的空闲链表中。
它的优点是空间效率非常高，因为每次都是分割最适配大小的内存块用于分配。而因为把搜寻限定在部分空闲链表上，也减少了搜寻时间。malloc 采用的就是这种策略。
3.2 合并空闲空间
正如在第二节所发现的那样，释放后紧挨在一起的空闲空间，由于没有合并，导致就算总空间足够了也不能被使用。
如何实现合并呢？
在基于第二节所说的单向空闲链表的情况下，合并当前内存段的下一个内存不难，但是合并前一个内存段就只能遍历整个内存段链表了。这样做的话，性能是一个大大的隐患。
为了高效地合并前面的相邻内存段，有一种方式利用了头部 3 个 flag 中的第 2 个(第 1 个用来表示当前段是否被分配) flag 来标志前一个内存段的空闲状态，并在空闲内存段的最后一个字保存了它的头部的副本。在释放当前内存段时，检查 flag 得知前一个内存段是空闲的，然后从其最后一个字得知前一个内存段的头部地址。修改前一个内存段的头部使其范围包括两个内存段的范围就实现了合并。
隐式空闲链表和分离适配空闲链表都需要以这种方式来合并空闲空间。但是这样一来的话，空闲链表中就需要额外一个字来保存头部的副本。这提高了回收空闲空间的门槛，很多小的空闲内存段因此就可能无法回收了。
四、总结
操作系统提供 void *malloc(size_t s) 函数向 heap 空间申请 s 个字节的空闲内存并获得一个指针 p 指向所获得的空间的首地址。操作系统向我们保证 [p, p + s) 范围的内存是可以放心使用的，但是需要我们自己注意不能使用范围之外的内存地址。
当 heap 内存中的空闲空间不够时，操作系统通过 sbrk 扩容 heap 内存空间。但是就算 heap 内存空间可以扩容，它也不是无限的。因此适时回收不再需要的空间就非常重要。
回收的时机由我们自己决定，操作系统只提供 free(void* p) 函数来释放 p 指向的内存。p 指向的内存在通过 malloc 分配内存时记录在 p 的前一个字中(称为 p 的头部)。因此传递给 free 的参数 p 必须是通过 malloc 返回的指针，否则会读到错误的头部释放错误的内存段。
p 的头部把 heap 内存空间划分为一个内存段的单向链表，内存段是否被使用由头部隐式地表示。为了减少搜寻空闲内存段的时间，可以使用显示空闲链表替代隐式空闲链表。为了减少搜寻时间的同时又提高分配空闲空间的适配程度，可以使用多个空闲链表组织大小接近的空闲内存块。而取决于搜寻算法，有时候需要合并相邻的空闲内存块。
为了实现显示空闲链表和相邻空闲内存块合并功能，需要在空闲块中使用额外的字记录信息。这提高了回收空闲内存块的空间门槛，很多体积过小的空闲内存块可能因此就无法回收了。