堆的理论基础
我们为什么需要堆
在编写程序时，我们要存储的数据的量可能是运行时确定的，这意味着使用静态的内存分配方式（如在栈，data或者bss段分配一个固定的空间）是不合适的。虽然在Linux操作系统中，我们还有mmap和munmap两个函数可以帮助我们动态的向内核申请一个页，但这种方式过于底层，在可移植性上做了妥协。此时堆便成了首选的解决方案。 通常用于维护堆区域的程序被称为动态内存分配器，该分配器分为两种：
显式分配器：我们的应用程序需要显式地分配和释放一个块，正如我们在C语言中的malloc和free函数一样。
隐式分配器：这种分配器也称为垃圾收集器，分配器自动检测一个块是否不再使用，并隐式的释放不再使用的块。这种分配器的特性通常由语言提供，如Java语言。
在这里，我们重点介绍显式分配器及其实现。
分配器的要求和目标
这一部分内容是重中之重，我们接下来的所有讨论都将基于这部分内容。
基本术语
分配器将堆视为一组不同大小的块（block），从内存的角度，也称为内存片（chunk），这些块有两种状态，即已分配或者未分配。
分配器的要求
首先，我们肯定不希望分配器在我们不知情的情况下改变我们存放在已分配块中的数据，也希望一个已分配块老老实实地呆在它原来的位置，因此我们提出了下面几个要求：
- 不得修改或移动已经分配的块。
- 我们的分配器必须具有基本的健壮性：它可以处理任意由分配/释放构成的请求序列。
- 为了避免出现意料之外的后果，分配器不应当改变我们输入的请求序列
- 为了保证分配器是可扩展的，分配器所使用的数据必须存放在堆中（因为堆本身就是可扩展的，这一点有点像之前提到的ld.so开头的自举代码）
- 分配器必须对齐块，以保证能够处理各种类型的数据。
分配器的目标
这里涉及到算法设计中的一个常用的思想：以空间换时间，以时间换空间。分配器需要做的便是保证两者之间的平衡。
假设一个个数为
首先我们想要分配器处理这段序列所花费的时间尽可能短，即吞吐率最大化。这牵扯到分配器在分配和释放过程中所使用的算法的时间复杂度。
其次，我们不希望堆中存在过多的碎片，这意味着我们想要最大化堆的利用率。我们将一个应用程序请求
假设一个堆的大小是
在这个定义中，我们隐含的假设是
分配器的第二个目标便是保证峰值利用率最大，即我们的堆空间得到了充分的利用。这听起来很简单，但实际上要考虑到空闲块的重复利用，碎片化的解决等一系列复杂的问题。下面我们使用一个例子来对其进行进一步阐释。
一个例子
现在我们尝试自己实现一个极端的分配器：堆的结构是一个顺序表，有一个top指针指向顺序表的顶部，当我们分配n字节空间时，分配器将top加上n并返回top的值。当我们释放某一空间时，分配器什么也不做。 这样的分配器在吞吐率上做到了极致，但在峰值利用率上惨不忍睹——它从不重新利用空间。从而导致了巨额的外部碎块（我们使用它来代指那些不能重新利用，又要占用空间的空闲块）。 这告诉我们实现一 个分配器并不简单，我们需要找到吞吐率和峰值利用率之间的一个平衡点。实际上，我们需要考虑下面几个问题：
- 如何记录空闲块：我们上面的实现中并没有考虑这一问题，因为我们从不重新利用空闲块
- 分配时如何选择一个空闲块，当我们执行分配操作时，该如何选取一个最优的空闲块
- 如何分割空闲块：被选择的空闲块可能比我们请求的要大，我们如何处理空闲块的剩余部分？
- 如何处理一个刚刚被释放的块（最大限度的保证不产生碎片）
注意上面描述的问题都与空闲块有关，因此我们对分配器的优化实际上就是对处理空闲块的方式的优化。 一个稍为简单的解决方案是使用隐式空闲链表。
隐式空闲链表
为了满足上面提到的要求，我们首先需要思考该使用什么样的数据结构。在本方案中当然是使用简单的顺序表结构。当我们分配一个块时，我们需要遍历这个表，查找一个大小合适的空闲块。
注意！上面这句话传达了哪些信息？首先，遍历这个表意味着表中的数据（即块）拥有严格的分界，大小合适意味着我们可以得知块的大小，空闲意味着我们可以得知一个块是否是“inuse”的。为了便捷的获取这些信息（别忘了我们块是对齐的），我们需要一种这样的数据结构：info + payload (+ padding)
同时我们从对齐得知块的大小总是2的幂，在这里我们假设块是使用8字节对齐的，因此块大小的最低3位必然是0。这三位用来存储如inuse位这种可以使用布尔值来表示的信息。
总结一下，现在我们的块结构是这样的：
1 | |
可以看到，其名为链表，但实际上并没有指向节点的指针出现，因为空闲块实际上是根据块的头部隐式的串联起来的，而且该结构同样拥有单链表的特点，如不能反向遍历。 该结构虽然简单，但它最大的缺点便是遍历空闲块的时间实际上与遍历所有堆块的时间成正比，即使只有一个空闲块放在表的尾部，我们也需要遍历所有堆块才能访问到它。 这种方案的另一个缺点在于合并堆块的问题：为了避免内存的碎片化（我们把相邻，但因为过小而无法使用的小空闲块称为假碎片），即让每个空闲块尽可能的大，我们需要将稍小的空闲块与相邻的较大的空闲块合并。该结构的劣势就体现在这里。考虑这样一种情况：
1 | |
在中间的堆块被释放后，我们很快可以得知它可以和之后的堆块合并，这一过程很简单，只需要将当前堆块的头部做相应的改变，再删除后方空闲块的头部即可。那么问题来了，如何合并前方的堆块呢？很显然，这需要另一次的遍历。这种方式显然并不优雅。这时回想链表的知识，我们知道，双向链表可以解决这一问题，将时间复杂度变为常数。因此，仿照之前的做法，我们将堆的结构变更如下：
1 | |
注意这种做法也是典型的拿空间换时间的做法，我们虽然提高了吞吐率，但由于额外的信息，内部碎片（位于堆块内部的，有效载荷之外的数据）增加了，峰值利用率也相应的降低了。 那么还有没有方法降低峰值利用率呢，注意到只有前方的块空闲时，我们才需要脚部中的信息。因此可以再已分配的堆块中将脚部作为有效载荷使用，而将前方块是否空闲的信息存入到当前块头部（以及脚部）多出来的低位中。
显式空闲链表
基本结构
由于我们提到过的遍历空闲块的额外时间开销，隐式空闲链表对于现代的分配器来讲并非最优的解决方案。我们知道，空闲块没有内容，那么为什么不把它的有效载荷利用起来呢？因此一种将空闲块显式地组织成双向链表的思路出现了，这时空闲块的结构如下：
1 | |
如此一来，当我们释放一个块时，有两种策略可以使用，其一是采用后进先出的策略，即下一次适配时优先搜索最后释放的块。这意味着释放的块都在链表的首部，如此一来，块的释放和合并都可以在常数时间内完成。 另一种策略是按照地址组织链表，即空闲块在链表中的地址顺序代表了其实际地址的顺序。如此一来，块的合并仍然是常数时间，然而块的释放需要一个线性的时间来搜索合适的位置。可以看到，这种策略就是将之前的隐式空闲链表的空闲块中按顺序加上前驱与后继指针的结果。 后一种策略虽然在释放时花费了更多时间，但在使用特定策略（首次适配）为新分配的块查找合适的空间时，该策略可以体现出比后进先出策略更优秀的性能。
分离的空闲链表
现在有了这样的堆块结构，我们要解决的几个重点问题（分割，合并）已经得到了较为妥善的答案。然而与分配块时的适配问题紧密相关的记录上还欠功夫。在介绍进一步的解决方案之前，我们需要先了解分配器对新分配的块的几种放置策略：
- 首次适配策略：从空闲块的首部开始遍历空闲块，直到某一个空闲块的有效负荷大小大于等于所请求的大小，（分割该空闲块）返回有效负荷的起始地址。
- 下一次适配策略：下一次适配是首次适配的一个替代品，它从上一次遍历结束的位置开始遍历，以期上一次分割后的剩余块能满足请求（不用想也知道开始部分的碎片化有多严重=-=）
- 最佳适配策略：遍历所有的空闲块，查找一个最优的块。
可以看到，第3种做法是空间利用率最高的策略，也是最耗时的策略。现在我们试图适当的组织空闲块的结构，以期首次适配策略能提高速度的同时尽可能赶上最佳适配策略的空间利用率。也就是下面我们要讲到的大小类。 一个采用大小类方式存储空闲块的例子可能如下所示：
1 | |
可以看到，分配器维护着一个链表指针数组，不同大小的空闲块被按照一定的规则（如2的幂）划分成了几个类，每个大小类一个空闲链表。当分配器需要分配一个n字节的空闲块时，它就会去相应的空闲链表中查找，查找失败则进入更大的大小类并对那里的空闲块进行分割与重新链接。 使用大小类的存储策略有很多，这里我们介绍两种：
简单分离存储
在这种存储策略中，每个大小类相应的空闲链表中只存放该大小类中最大元素的空闲块。这种策略有以下几种特性：
- 当分配一个给定大小的块时，我们只需要直接分配相应大小类对应空闲链表中的第一个元素。当该空闲链表为空时，只需要等分更大的大小类对应的空闲链表的的一个空闲块，将其挂在相应的的大小类中即可。
- 释放块时，只需要将块插入到相应空闲链表的头部即可，不需要合并，因此不需要块的脚部与后继指针
- 块是否在空闲链表中隐式地提示了提示了块是否被使用，因此不需要inuse标志位
- 块在哪个大小类中隐式地提示了块的大小，因此空闲块不需要size
综上所述，我们只需要为空闲块保留一个后继指针即可，因此最小的块大小便是一个指针的大小。这听起来很诱人，然而因其不合并空闲块的特性，简单分离存储很容易造成大量的外部碎片，尤其是我们为各种不同大小都申请了少量堆块时。
分离适配
分离适配的方式不要求一个大小类中的所有块都一致，该方案在分配时会对相应的链表做首次适配，适配失败时转向更大的大小类并将一个大空闲块分割（可选），将剩余部分插入到相应的空闲链表中。 该方案是一种常见的方法，由于其快速和媲美最佳适配的内存利率。GNU提供的malloc便使用了该方案。实际上，GNU的malloc提供了多种方案以应对不同情况，以达到整体的效率最大化。下次我们将会对此进行详细讨论。