动态内存分配通常在堆上进行，堆其实就是一块连续的内存空间。为了实现内存的动态分配与回收，需要提供一组函数来管理这片内存。

隐式空闲链表

为了记录分配的内存的大小，需要使用额外的空间来存储，一种方法是在分配的内存块的前面存放该块的大小。当用户释放了这块内存后，这块内存就可以得到复用，因此还需要记录当前块是否被使用。

由于内存块的大小往往需要对齐到 4 字节或 8 字节，因此内存大小的低 2 bit 一定是 0。因此，可以使用这两个 bit 来记录当前块是否被使用。比如最低 bit 为 1，表示该块正在被使用。

上图中的这种设计，将内存划分成了一个个块，通过第一块的地址，和块中存放的大小信息，可以得到第二块的地址。在内存分配的时候，可以从第一块开始，寻找一个合适的块，将其交给用户。如果没有已经分配的块可用，就可以在剩余的堆空间中再分配一个块。

在选择合适的块时，可以采用多种策略，包括：

• first fit
• next fit
• best fit

这些分配方式最终会将内存划分为一个个块，设想如果将内存全部划分成了 100 字节的块，最后虽然有很多空闲块，但是依然没办法分配一个 200 字节的块。

上图中，每次分配整个空间的一半，两次后，将空间划分为两块，随后需要整个空间那么大的块时，却无法满足。因此，合并空闲的块是非常必要的。

合并空闲块

合并可以发生在释放内存的时候，这叫做立即合并，也可以在下次分配的时候，这叫做推迟合并。在释放时合并，有可能出现合并-划分-再合并的情况。

如果是立即合并，在隐式空闲链表的方法中，从前一块访问后一块很容易，但是无法从后一个块访问前一个块。如果当前释放的块的后面一块是空闲的，那么合并很容易进行。但是，如果当前释放的块的前一块时空闲的，而通过当前块是无法获得前一块的信息的，这就很麻烦。

一种策略是，在块的尾部添加一个 footer，这和 header 内容一样。这样以来，当前块的 header 前面就是上一个块的 footer，可以通过 footer 信息得到上一块的大小。

但问题是，每一个块都需要一个 header 和 footer，如果分配大量较小的块，那么单单 header 和 footer 就会占用很大比例的内存。 但其实只有空闲的块是需要 footer，因为如果一个块正在被使用，也用不着合并它。

因此，对于使用中的块，不需要 footer 部分，对于未使用的块，可以利用未使用的空间的尾部来放置 footer。在块的 header 部分，可以利用一个未使用的 bit 来表示前一块是否被使用。如果没有被使用，那么 header 前面就是前一块的 footer。