9.9.13 显式空闲链表
隐式空闲链表为我们提供了一种介绍一些基本分配器概念的简单方法。然而，因为块分配与堆块的总数呈线性关系，所以对于通用的分配器，隐式空闲链表是不合适的（尽管对于堆块数量预先就知道是很小的特殊的分配器来说它是可以的）
一种更好的方法是将空闲块组织为某种形式的显示数据结构。根据定义，程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。 例如，堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个 pred（前驱）和 succ（后继）组织，图9-48
使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略。
一种方法是用 后进先出（LIFO）的顺序维护链表，将新释放的块放置在链表的开始处。使用 LIFO 的顺序和首次适配的放置策略，分配器会最先检查最近使用过的块。在这种情况下，释放一个块可以在常数时间内完成。如果使用了边界标记，那么合并也可以在常数时间内完成。
另一种方法是按照地址顺序来维护链表，其中链表中每个块的地址都小于它后继的地址。在这种情况下，释放一个块需要线性时间的搜索来定位合适的前驱。平衡点在于，按照地址排序的首次适配比 LIFO 排序的首次适配有更高的内存利用率，接近最佳适配的利用率。
一般而言，显示链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，潜在地提高了内部碎片的程度。
9.9.14 分离的空闲链表
正如看到的，一个使用单向空闲块链表的分配需要与空闲块数量呈线性关系的时间来分配块。一种流行的减少时间分配的方法，称为 分离存储，就是维护多个空闲链表，其中每个链表中的块有大致相等的大小。一般的思路是将所有可能的块大小分成一些等价类，也叫做大小类（size class）。有很多种方式来定义大小类。例如，可以根据 2 的幂来划分块大小：
{1}，{2}，{3,4}，{5~8},,,,,{1025~2048}，{2048~4096}，{4097~∞}
或者可以将小的块分配到它们自己的大小类里，而将大块按照2的幂分类：
{1}，{2}，{3},,,,,{1023}，{1024}，{1025~2048}，{2048~4096}，{4097~∞}
分配器维护着一个空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列。当分配器需要一个大小为 n 的块时，它就搜索相应的空闲链表。如果不能找到合适的块与之匹配，它就搜索下一个链表，以此类推。
有关动态内存分配的文献描述了几十种分离内存的方法，主要的区别在于它们如何定义大小类，何时进行合并，何时向操作系统请求额外的堆内存，是否允许分割，等等。为了使你大致了解有哪些可能性，我们会描述两种基本的方法：简单分离存储和分离适配。
1.简单分离存储
使用简单分离存储，每个大小类的空闲链表包含大小相等的块，每个块的大小就是这个大小类种最大元素的大小。例如，如果某个大小类定义为{17-32}，那么这个类的空闲链表全由大小为 32 的块组成。
为了分配一个给定大小的块，我们检查相应的空闲链表。如果链表非空，简单地分配其中第一块的全部。空闲块是不会分割以满足分配请求的。 如果链表为空，分配器就向操作系统请求一个固定大小的额外内存片（通常是页大小的整数倍），将这个片分成大小相等的块，并将这些块链接起来形成一个新的空闲链表。要释放一个块，分配器只需要简单地将这个块插入到相应的空闲链表的前部。
这种简单的方法有许多优点，分配和释放块都是很快的常数时间操作。而且，每个片中都是大小相等的块，不分割，不合并，这意味着每个块只有很少的内存开销。由于每个片只有大小相同的块，那么一个已分配块的大小就可以从它的地址中推断出来。因为没有合并，所以已分配块的头部不需要一个已分配/空闲标记。因此已分配块不需要头部，同时因为没有合并，也不需要脚部。因为分配和释放操作都是在空闲链表的起始处操作，所以链表只需要是单向的，而不是双向的。关键点在于，在任何块中都需要唯一字段是每个空闲块中的一个字的 succ 指针，因此最小块大小就是一个字。
一个显著的缺点是，简单分离存储很容易造成内部和外部碎片。因为空闲块是不会被分割的，所以可能会造成内部碎片。更糟的是，因为不会合并空闲块，所以某些引用模式会引起极多的外部碎片。
2.分离适配
使用这种方法，分配器维护着一个空闲链表的数组。每个空闲链表是和一个大小类相关联的，并且被组织成某种类型的显示或隐式链表。每个链表包含潜在的大小不同的块，这些块的大小是大小类的成员。有许多种不同的分离适配分配器。
为了分配一个块，必须确定请求的大小类，并且对适当的空闲链表做首次适配，查找一个合适的块。如果找到了一个，那么就可选地分割它，并将剩余的部分插入到适当的空闲链表中。如果找不到合适的块，那么就搜索下一个更大的大小类的空闲链表。 如此重复，直到找到一个合适的块。如果空闲链表中没有合适的块，那么就向操作系统请求额外的堆内存，从这个新的堆内存中分配出一个块，将剩余部分放置在适当的大小类中。要释放一个块，执行合并，并将结果放置到相应的空闲链表中。
分离适配方法是一种常见的选择，C标准库中提供的 GNU malloc 包就是采用的这种方法，因为这种方法既快速，对内存的使用也很有效率。搜索时间减少了，因为搜索被限制在堆的某个部分，而不是整个堆。内存利用率得到改善：对分离空闲链表的简单的首次适配搜索，其内存利用率近似对整个堆的最佳适配搜索的内存利用率。
3. 伙伴系统
伙伴系统是分离适配的一种特例，其中每个大小类都是 2 的幂。基本的思路是假设一个堆的大小为 2^m 个字，我们为每个块大小2^k维护一个分离空闲链表，其中 。请求块大小向上舍入到最接近的 2 的幂。最开始时，只有一个大小为 2^m 个字的空闲块。
为了分配一个大小为 2^k 的块，我们找到第一个可用的，大小为 2^j 的块 。如果 j=k，那么就完成了。否则，我们递归地二分割这个块，直到 j=k。当进行这样的分割时，每个剩下的半块（也叫伙伴）被放置在相应的空闲链表中。要释放一个大小为 2^k 的块，继续合并空闲的伙伴。当遇到一个已分配的伙伴时，就停止合并。
关于伙伴系统的一个关键事实，给定地址和块的大小，很容易计算出它的伙伴的地址。例如一个块，大小为 32 字节，地址为： xxx...x00000，它的伙伴地址为 xxx...x10000。 换句话说，一个块的地址和它的伙伴只有一位不相同。
伙伴系统分配器的主要优点是它的快速搜索和快速合并。主要缺点是要求块大小为 2 的幂可能导致显著的内部碎片。因此，伙伴系统分配器不适合通用目的的工作负载。然而，对于某些特定应用的工作负载，其中块大小预先知道是 2 的幂，伙伴系统分配器就很有吸引力。
9.10 垃圾收集
在诸如 C malloc 包这样的显示分配器中，应用通过调用 malloc 和 free 来分配和释放堆块。应用要负责释放所有不再需要的已分配块。
未能释放已分配的块是一种常见的编程错误。例如，考虑下面的C函数，作为处理的一部分，它分配一块临时存储：
因为程序不再需要 p，所以在 garbage 返回之前应该释放 p。不幸的是，程序员忘了释放这个块。它在程序的生命周期内部保持为已分配状态，毫无必要地占用着本来可以用来满足后面分配请求的堆空间。
垃圾收集器 是一种动态内存分配器，它自动释放程序不再需要的已分配块。这些块被称为垃圾。自动回收堆存储的过程叫做垃圾收集。在一个支持垃圾收集的系统中，应用显式分配堆块，但是从不显式地释放它们。 在C程序的上下文中，应用调用 malloc ，但是从不调用 free。反之，垃圾收集器定期识别垃圾块，并相应地调用 free，将这些块放回到空闲链表中。
9.10.1 垃圾收集器的基本知识
垃圾收集器将内存视为一张有向可达图，其形式如图 9-49 所示。该图的节点被分成一组根节点和一组堆节点。每个堆节点对应于堆中的一个已分配块。 有向边 p->q 意味着块p 中的某个位置指向块 q 中的某个位置。根节点对应于这样一种不在堆中的位置，它们中包含指向堆中的指针。这些位置可以是寄存器，栈里的变量，或者是虚拟内存中读写数据区域内的全局变量，
当存在一条从任意根节点出发并到达 p 的有向路径时，我们说节点 p是可达的。在任何时刻，不可达节点对应于垃圾，是不能被应用再次使用的。垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点且将它们返回给空闲链表，来定期的回收它们。
像 ML 和 Java 这样的语言的垃圾收集器，对应用如何创建和使用指针有很严格的控制，能够维护可达图的一种精确的表示，因此也就能够回收所有垃圾。然而，诸如C和C＋＋这样的语言的收集器通常不能维持可达图的精确表示。这样的收集器叫做保守的垃圾收集器。从某种意义来说它们是保守的，即每个可达块都被正确地标记为可达了，而一些不可达节点却可能错误地被标记为可达。
收集器可以按需提供它们的服务，或者它们可以作为一个和应用并行的独立线程，不断地更新可达图和回收垃圾。例如，考虑如何将一个 C 程序的保守的收集器加入到已存在的 malloc 包中
无论何时需要堆空间时，应用都会用通常的方式调用 malloc。如果 malloc 找不到一个合适的空闲块，那么它就调用垃圾收集器，希望能够回收一些垃圾到空闲链表。收集器识别出垃圾块，并通过调用 free 函数将它们返回给堆。关键的思想是收集器代替应用去调用 free。当对收集器的调用返回时，malloc 重试，试图发现一个合适的空闲块。 如果还是失败了，那么他就会像操作系统要求额外的内存。最后，malloc 返回一个指向请求块的指针（如果成功）或者返回一个空指针（不成功）。
9.10.2 Mark 或 Sweep 垃圾收集器
Mark & Sweep 垃圾收集器由标记（mark）阶段和清除（sweep）阶段组成，标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段释放每个未被标记的已分配块。块头部中 空闲的低位中的一位通常用来表示这个块是否被标记了。
对 Mark & Sweep 的描述将假设使用下列函数，其中 ptr 定义为 typedef void *ptr:
① ptr isPtr（ptr p）：如果 p 指向一个已分配块中的某个字，那么就返回一个指向这个块的起始位置的指针 b。否则返回 NULL。
② int blockMarked（ptr b）：如果块 b 是已标记的，那么就返回 true
③ int blockAllocated（ptr b）：如果块 b 是已分配的，那么就返回 true
④ void markBlock（ptr b）：标记块 b
⑤ int length（b）：返回块 b 的以字为单位的长度（不包括头部）
⑥ void unmarkBlock（ptr b）：将块 b 的状态由已标记的改为未标记的
⑦ ptr nextBlock（ptr b）：返回堆中块 b 的后继
标记阶段为每个根节点调用一次图 9-51a 所示的 mark 函数。如果 p 不指向一个已分配并且未标记的堆块，mark 函数就立即返回。否则，它就标记这个块，并对块中的每个字递归地调用它自己。每次对 mark 函数的调用都标记某个根节点的所有未标记并且可达的后继节点。在标记阶段的末尾，任何未标记的已分配块都被认定为是不可达的，是垃圾，可以在清除阶段回收。
清除阶段是对图 9-51b 所示的 sweep 函数的一次调用。sweep 函数在堆中每个块上反复循环，释放它所遇到的所有未标记的已分配块（也就是垃圾）。
图 9-52 展示了一个小堆的 Mark&Sweep 的图形化解释。块边界用粗线条表示。每个方块对应于内存中的一个字。每个块有一个字的头部，要么是已标记的，要么是未标记的。
初始情况下，图9-52中的堆由 6 个已分配块组成，其中每个块都是未分配的，第3个块包含一个指向第 1 块的指针。第 4 块包含指向第 3 块和第 6 块的指针。根指向第 4 块。在标记阶段之后，第 1 块，第 3 块，第 4 块 和 第 6 块做了标记，因为它们是从根节点可达的。第 2 块和第 5 块是未标记的，因为它们是不可达的。在清除阶段之后，这两个不可达块被回收到空闲链表。
9.10.3 C程序的保守 Mark & Sweep
Mark & Sweep 对 C程序的垃圾收集是一种合适的方法，因为它可以就地工作，而不需要移动任何块。然而，C语言为 isPtr 函数的实现造成了一些有趣的挑战
第一：C不会用任何类型信息来标记内存位置。因此，对 isPtr 没有一种明显的方式来判断它的输入参数 p 是不是一个指针。第二：即使知道 p 是一个指针，对 isPtr 也没有明显的方式来判断 p 是否指向一个已分配块的有效载荷中的某个位置。
对后一问题的解决方法是将已分配块集合维护成一棵平衡二叉树，这棵树保持着这样一个属性：左子树中所有的块都放在较小的地址处，而右子树中的所有块都放在较大的地址处。图9-53所示，这就要求每个已分配块的头部里由两个附加字段（left 和 right）。每个字段指向某个已分配块的头部。 isPtr（ptr p）函数用树来执行对已分配块的二分查找。在每一步中，它依赖于块头部中的大小字段来判断 p 是否落在这个块的范围之内。
平衡树方法保证会标记所有从根节点到可达的节点，从这个意义上说是正确的。这是一个必要的保证，因为应用程序的用户当然不会喜欢把它们的已分配块过早地返回给空闲链表。然而，这种方法在某种意义上而言又是保守的，因为它可能不正确地标记实际上不可达的块，因此他可能不会释放某些垃圾。虽然者并不影响应用程序的正确性，但是这可能导致不必要的外部碎片。
C 程序的 Mark & Sweep 收集器必须是保守的，其根本原因是 C语言不会用类型信息来标记内存位置。因此，像 int 或者 float 这样的标量可以伪装成指针。例如，假设某个可达的已分配块在它的有效载荷中包含一个 int，其值碰巧对应于某个其他已分配块 b 的有效载荷中的一个地址。对于收集器而言，是没有办法推断出这个数据实际上是 int 而不是指针。因此，分配器必须保守地将块 b 标记为可达，尽管事实上可能是不可达的。
9.11 C程序中常见的与内存有关的错误
对 C程序员来说，管理和使用虚拟内存可能是个困难的，容易出错的任务。与内存有关的错误属于那些最令人惊恐的错误，因为它们在时间和空间上，经常在距错误源一段距离之后才表现出来。将错误的数据写到错误的位置，程序可能在最终失败之前运行了好几个小时，且使程序中止的位置距离错误的位置已经很远了。常见的与内存有关的错误讨论。
9.11.1 间接引用坏指针
在进程的虚拟地址空间中有较大的洞，没有映射到任何有意义的数据。如果试图间接引用一个指向这些洞的指针，那么操作系统就会以段 异常中止程序。而且，虚拟内存的某些区域是只读的。试图写这些区域将会以保护 异常中止这个程序。
间接引用坏指针的一个常见示例是经典的 scanf 错误。假设想要使用 scanf 从 stdin 读一个整数到一个变量。正确的方法是传递给 scanf 一个格式串和变量的地址： scanf("%d",&val);
然而，对于C程序员初学者，很容易传递 val 的内容，而不是其地址 scanf("%d",val);
这种情况下， scanf 将把 val 的内容解释为一个地址，并试图将一个字写到这个位置。在最好的情况下，程序立即以异常终止。最糟糕的情况，val 的内容对应于虚拟内存的某个合法的读/写区域，于是我们就覆盖了这块内存，这通常会在相当长的一段时间以后造成灾难性的，令人困惑的后果。
9.11.2 读未初始化的内存
虽然 bss 内存位置（诸如未初始化的全局 C 变量）总是被加载器初始化为零，但是对于堆内存却并不是这样的。一个常见的错误就是假设堆内存被初始化为零。
9.11.3 允许栈缓冲区溢出
如果一个程序不检查输入串的大小就写入栈中的目标缓冲区，那么这个程序就会有缓冲区溢出错误。例如，下面的函数就有缓冲区溢出错误，因为 gets 函数复制一个任意长度的串到缓冲区。为了纠正这个错误，必须使用 fgets 函数，这个函数限制了输入串的大小。
9.11.4 假设指针和它们指向的对象是相同大小的
一种常见的错误是假设指向对象的指针和它们所指向的对象是相同大小的：
这里的目的是创建一个由 n 个指针组成的数组，每个指针都指向一个包含 m 个int 的数组。然而，在第 5 行将 sizeof(int *) 写成了 sizeof(int)，代码实际上创建的是一个 int 的数组。
这段代码只有在 int 和 指向 int 的指针大小相同的机器上运行良好。但是，如果在像 core i7 这样的机器上运行这段代码，其中指针大于 int，那么第 7 行 和 第 8 行的循环将写到超出 A 数组结尾的地方。因为这些字中的一个很可能是已分配块的边界标记脚部，所以可能不会发现这个错误，直到在这个程序的后面很久释放这个块时，此时，分配器中的合并代码会戏剧性地失败，而没有任何明显的原因。这时，“在远处起作用”的一个示例，这类“在远处起作用”是与内存有关的编程错误的典型情况。
9.11.5 造成错位错误
错位（off-by-one）错误是另一种很常见的造成覆盖错误的来源：
9.11.6 引用指针，而不是它所指向的对象
如果不太注意 C 操作符的优先级和结合性，我们就会错误地操作指针，而不是指针所指向的对象。比如，考虑下面的函数，其目的是删除一个有 *size 项的二叉堆里的第一项，然后对剩下的 *size-1 项重新建堆。
在第 6 行，目的是减少 size 指针指向的整数的值。然而，因为一元运算符-- 和 *的优先级相同，从右向左结合，所以第 6 行中的代码实际上减少的是指针自己的值，而不是它所指向整数的值。如果幸运，程序会立即失败；但更可能发生的是，当程序在执行过程后很久才产生出一个不正确的结果，我们只有一头雾水。这里的原则是当你对优先级和结合性有疑问时，就使用括号。比如，第六行中可以使用 （*size）--。
9.11.7 误解指针运算
另一种常见的错误是忘记了指针的算术操作是以它们指向的对象的大小为单位来进行的，而这种大小单位并不一定是字节。例如，下面函数的目的是扫描一个 int 数组，并返回一个指针，指向 val 的首次出现：
9.11.8 引用不存在的变量
9.11.9 引用空闲堆块中的数据
一个相似的错误是引用已经被释放了的堆块中的数据。例如，考虑下面的示例，这个示例在第 6 行分配了一个整数数组 x，第 10 行中先释放了块 x，然后在第 14 行中又引用了它：
取决于在第 6 行和第 10 行发生的 malloc 和 free 的调用模式，当程序在第 14 行引用 x[i]时，数组 x 可能是某个其他已分配块的一部分了，因此其内容被重写了。和其他许多与内存有关的错误一样，这个错误只会在程序执行的后面，当我们注意到 y 中的值被破坏了时才会显现出来。
9.11.10 引起内存泄漏
内存泄漏是缓慢，隐性的杀手，当程序员不小心忘记释放已分配块，而在堆里创建了垃圾时，会发生这种问题。例如，下面的函数分配了一个堆块 x，然后不释放它就返回：
