0.5.1. 堆内存¶

"堆" 内存，也称为 "动态" 内存，是局部栈内存的一种替代方案。 局部内存（第 2 节）相当自动化—函数调用时它被自动 分配，函数退出时它被自动释放。 堆内存在各个方面都不同。 程序员显式地请求分配特定大小的一块内存 "块"，该块会一直保持已分配状态， 直到程序员显式请求释放它为止。 什么都不会自动发生。 因此程序员对内存有大得多的控制，但责任也 更大，因为内存现在必须被主动管理。 堆内存的优点有：

• 生存期。因为程序员现在能精确控制内存何时 被分配和释放，所以有可能在内存中构建一个数据 结构，并把它返回给 调用方。局部内存永远做不到这点，因为 函数退出时它会被自动释放。

• 大小。所分配内存的大小可以被更精细地 控制。例如，可以在运行时分配一个字符串缓冲区， 使其大小恰好能容纳某个特定的字符串。用 局部内存时，代码更可能声明一个大小为 1000 的缓冲区， 然后听天由命。（参见下面的 StringCopy() 例子。）

堆内存的缺点是：

• 更多工作。堆分配需要在代码中显式安排， 这本来就是更多的工作。

• 更多 bug。由于现在是在代码中显式完成的， 实际上分配偶尔会出错， 导致内存 bug。局部内存虽然受限，但至少 永远不会 错误。

尽管如此，仍有许多问题只能靠堆内存解决， 所以事情只能如此。 在具有垃圾回收器的语言中，比如 Perl、LISP 或 Java， 上述缺点大多被消除了。 垃圾回收器接管了堆管理的大部分 责任，代价是运行时多花费一点点时间。

0.5.2. 堆看起来是什么样？（What Does The Heap Look Like?）¶

在了解确切细节之前，我们先来看一个关于 堆中分配和释放的粗略例子。

0.5.2.1. 分配（Allocation）¶

堆是一大片可供程序使用的内存区域。 程序可以在堆内为自己请求一些内存区域或 "块"。 为了分配某一大小的块，程序通过调用堆的 分配 函数发出显式请求。 分配函数在堆中保留一块请求大小的内存，并返回指向它的指针。假设一个程序发出三次分配请求， 在堆中分配内存来存放三幅彼此独立的 GIF 图像， 每幅需要 1024 字节的内存。三次分配请求之后，内存看起来可能如下。

每次分配请求都会在堆中保留一块请求大小的连续区域， 并把指向新块的指针返回给程序。由于每个块总是通过 指针来引用，块始终扮演 "pointee"（第 1 节）的角色，程序 总是通过指针来操作它的堆块。指向堆块的指针 有时也被称为 "基地址" 指针，因为按照惯例它们指向块的基部 （地址最低的字节）。 在这个例子中，三个块从堆的底部开始连续分配， 每个块的大小都是所请求的 1024 字节。实际上，堆 管理器可以把块分配到堆中任何它想放的位置，只要块之间 不重叠且至少达到请求的大小即可。在任一特定时刻，堆中的某些区域 已经分配给程序，因而处于 "使用中"。其他区域尚未被 分配，因此是 "空闲" 的，可以用来满足分配请求。堆 管理器有自己的私有数据结构，用来记录任一时刻堆中的哪些区域 被分配作何种用途。堆管理器从空闲内存池中满足每个分配 请求，并更新其私有数据结构，记录堆中哪些区域正在使用。

0.5.2.2. 释放（Deallocation）¶

当程序用完一块内存之后，它发出一个显式的 释放请求，向堆管理器表明程序 现在已用完那块内存。 堆管理器更新其私有数据结构，表明该块 占用的内存区域重新变为空闲，因而日后可以重新用于满足分配请求。如果程序释放了三个块中的第二个， 堆看起来将如下。

释放之后，指针仍然指向那个 已被释放的块。 程序不能访问那个已释放的被指针指向者（pointee）。 这就是指针被画成灰色的原因—指针还在那里， 但绝不能使用。有时代码会在释放后紧接着把指针 设置为 NULL，以显式表明一个事实：它 不再是有效的。

0.5.3. 对堆编程（Programming The Heap）¶

在大多数语言中，对堆的编程看起来基本相同。其 基本特性是：

• 堆是一片可用的内存区域，用于为程序分配内存区域（"块"）。

• 有一些 "堆管理器" 库代码为程序管理堆。 程序员向堆管理器发出请求， 由堆管理器管理堆的内部事务。在 C 中，堆由 ANSI 库函数 malloc()、free() 和 realloc() 管理。

• 堆管理器使用自己的私有数据结构来记录堆中哪些块是 "空闲" 的（可供使用）、哪些块目前正被程序使用以及这些块有多大。 初始时，整个堆都是空闲的。

• 堆的大小可以是固定的（通常的概念模型），也可以在虚拟内存的支持下表现为固定但极其巨大的大小。 无论哪种情况，如果堆的全部内存都已被分配，堆都可能变 "满"，从而无法 满足某个分配请求。分配函数会以某种方式把这种 运行时状况告知程序—通常是返回一个 NULL 指针或抛出特定于语言的 运行时异常。

• 分配函数请求堆中一块特定大小的内存。 堆管理器选择一块内存区域来满足请求，在其私有数据 结构中把该区域标记为 "使用中"，并返回指向该堆块的指针。此后，调用方 就可以顺着指针自由使用那块内存。该块保证保留给调用方 单独使用—堆不会把同一块内存区域交给其他 调用方。块不会在堆内移动—一旦分配，它的 位置和大小就固定了。一般来说，当一个块被分配时，它的内容是随机的。新所有者 有责任把内存设置成有意义的 内容。有时内存分配函数 会有一种变体，把块设置成全部为零（C 中的 calloc()）。

• 释放函数是分配函数的反面。 程序发出一次释放调用，把一块内存归还给堆的空闲区域，以便日后重新使用。每个块 只应被释放一次。释放函数接受 一个指向先前由分配函数提供的堆块的指针作为参数。这个指针必须与 分配函数先前返回的指针完全相同，而不只是 指向块内某处的任意指针。释放之后，程序必须把 该指针视为无效，并且不能访问那个已释放的被指针指向者。

0.5.4. C 语言的特定细节（C Specifics）¶

在 C 语言中，发出堆请求的库函数是 malloc()``（"memory allocate"）和 ``free()。 这些函数的原型在头文件 <stdlib.h> 中。 虽然各语言的语法有所不同，但 malloc() 和 free() 的作用在所有语言中几乎是相同的。

void* malloc(unsigned long size); malloc() 函数接受一个无符号整数，即所请求的 以字节计量的块大小。 如果分配成功，malloc() 返回指向一个新堆块的指针；如果因为堆已满而无法 满足请求，则返回 NULL。 C 运算符 sizeof() 是一种计算一个类型 字节数的便捷方式—对于 int 被指针指向者用 sizeof(int)， 对于 struct fraction 被指针指向者用 sizeof(struct fraction)。

void free(void* heapBlockPointer); free() 函数接受一个指向堆块的指针，把它 归还给空闲池以便日后重新使用。传给 free() 的指针必须恰好是先前由 malloc() 返回的指针，而不只是指向块内某处的指针。 用错误的指针调用 free() 以 造成特别丑陋的崩溃而闻名。调用 free() 不需要给出堆块的大小—堆管理器会在它的私有数据中记下这个大小 结构。对 free() 的调用只需通过指针识别 要释放哪个块。如果一个程序正确地 释放了它分配的全部内存，那么对 malloc() 的每次调用 之后都将恰好有一次对 free() 的调用与之匹配。 不过，作为一种实际情况，程序并不总是需要 释放它分配的每个块—参见 下面的 "内存泄漏"。

0.5.5. 简单堆示例（Simple Heap Example）¶

下面是一个简单例子，它在堆中分配一个 int 块，把数字 42 存进块中，然后释放它。 这是堆块分配、使用和释放的最简例子。 这个例子展示了上述代码执行过程中三个不同时刻的内存状态。图中分别展示了栈和堆—对于既使用栈内存又使用堆内存的代码，其图示需要 区分这两块区域才能保持准确，因为支配这两块区域的规则 差别很大。在这个例子中，局部变量 intPtr 的生存期与 堆块的生存期完全 分离，图中需要反映出这种 区别。

void Heap1() {
  int* intPtr;
  // Allocates local pointer local variable (but not its pointee)
  // T1

// Allocates heap block and stores its pointer in local variable.
// Dereferences the pointer to set the pointee to 42.
intPtr = malloc(sizeof(int));
*intPtr = 42;
// T2

// Deallocates heap block making the pointer bad.
// The programmer must remember not to use the pointer
// after the pointee has been deallocated (this is
// why the pointer is shown in gray).
free(intPtr);
// T3

0.5.6. 简单堆观察（Simple Heap Observations）¶

• 分配调用在堆中分配块之后，程序把指向该块的指针存储在局部变量 intPtr 中。如 T2 所示，块是 "被指针指向者"（pointee），intPtr 是指向它的指针。 在这种状态下，可以安全地 解引用指针来操作被指针指向者。第 1 节中的指针/被指针指向者规则仍然适用，唯一的区别在于被指针指向者 最初是如何分配的。

• 在调用 malloc() 之前的 T1 时刻，intPtr 未初始化， 没有被指针指向者—此时 intPtr 在第 1 节讨论的 意义上也是 "坏" 的。和之前一样，解引用这样的 未初始化指针是一种常见但灾难性的 错误。有时这个错误会立即崩溃（幸运）。其他 时候它只是轻微破坏一个随机数据结构 （不幸）。

• 如 T3 所示，调用 free() 会释放被指针指向者。在 被指针指向者被释放之后再解引用指针 是错误。遗憾的是，这个错误几乎永远不会被标记 为立即的运行时错误。99% 的情况下解引用会 产生合理的结果，1% 的情况下解引用会 产生略有错误的结果。具有讽刺意味的是，这种很少出现的 bug 是最难追踪的类型。

• 当函数退出时，它的局部变量 intPtr 会按照局部 变量（第 2 节）的通常规则自动被释放。 所以这个函数拥有整洁的内存行为—它在运行时 分配的所有内存（它的局部变量、它的一个堆块） 在它退出时都被释放掉了。

0.5.7. 堆数组（Heap Array）¶

在 C 语言中，在堆中分配数组很方便， 因为 C 可以把任何指针当作数组。 数组内存块的大小是每个元素的大小（由 sizeof() 运算符计算）乘以元素的 个数（参见 CS 教育文库 /101 C 语言，那里对 C、尤其是数组和指针， 有完整的讨论）。 因此下面的代码在堆中分配一个包含 100 个 struct fraction 的数组，把它们全部设为 22/7，并 释放这个堆数组。

void HeapArray() {
  struct fraction* fracts;
  int i;
  // allocate the array
  fracts = malloc(sizeof(struct fraction) * 100);
  // use it like an array -- in this case set them all to 22/7
  for (i=0; i<99; i++) {
    fracts[i].numerator = 22;
    fracts[i].denominator = 7;
  }
  // Deallocate the whole array
  free(fracts);
}

0.5.8. 堆字符串示例（Heap String Example）¶

下面是一个更有用的堆数组例子。StringCopy() 函数接受一个 C 字符串， 在堆中复制一份该字符串，并返回指向新字符串的指针。调用方 接管新字符串的所有权，并有责任释放它。

/*
 Given a C string, return a heap allocated copy of the string.
 Allocate a block in the heap of the appropriate size,
 copies the string into the block, and returns a pointer to the block.
 The caller takes over ownership of the block and is responsible
 for freeing it.
*/
char* StringCopy(const char* string) {
  char* newString;
  int len;
  len = strlen(string) + 1;   // +1 to account for the '\0'
  newString = malloc(sizeof(char)*len);         // elem-size * number-of-elements
  assert(newString != NULL);    // simplistic error check (a good habit)
  strcpy(newString, string);    // copy the passed in string to the block

  return(newString);    // return a ptr to the block
}

0.5.9. 内存泄漏（Memory Leaks）¶

如果一些内存在堆中分配了，却从未被释放，会发生什么？ 忘记释放块的程序被称为有 内存泄漏，这可能是也可能不是严重问题。 结果将是堆随着持续不断有分配请求、 却没有释放请求归还块以供复用， 而逐渐变满。 对于运行、计算出结果、然后立即退出的程序，内存泄漏 通常不是问题。这样的 "一次性" 程序可以省略它所有的释放 请求，仍然大体工作正常。内存泄漏对于运行 时间不确定的程序来说更是问题。在这种情况下，内存泄漏会逐渐 填满堆，直到分配请求无法被满足、程序停止工作 或崩溃为止。许多商业程序都有内存泄漏，因此运行 足够长时间、或使用大数据集时，它们会装满堆并崩溃。通常 针对堆满错误状况的错误检测 和规避代码没有得到很好的测试，恰恰因为 这种状况在程序的短运行时很少遇到—这就是为什么 填满堆常常导致真正的崩溃，而不是礼貌的错误信息。大多数编译器都有 一个 "堆调试" 工具，它会向程序添加调试代码，用来跟踪每次 分配和释放。当一个分配没有相应的释放时， 那就是泄漏，堆调试器可以帮助你找到它们。

0.5.10. 所有权（Ownership）¶

StringCopy() 分配了堆块，但没有释放它。这样调用方 才能使用新字符串。然而，这引入了一个问题：确实需要有人 记住释放这个块，而这个人不会是 StringCopy()。这就是为什么 StringCopy() 的注释特别提到调用方正在接管 该块的所有权。每块内存都有并且只有一个 "所有者"，由他负责 释放它。其他实体可以持有指针，但只是共享而已。只有一个 所有者，而 StringCopy() 的注释清楚地表明所有权正 从 StringCopy() 传递给调用方。好的文档总是记得 讨论一个函数期望应用于其参数或返回 值的所有权规则。反过来说，文档中一个常见的错误是 忘记说明参数或返回值的所有权规则 到底是什么。这正是产生内存错误和泄漏的方式之一。

0.5.11. 堆内存小结（Heap Memory Summary）¶

堆内存为程序员提供了更大的控制权—内存块可以按任意大小请求，并且保持 已分配状态，直到被显式释放为止。 堆内存可以传回给调用方，因为它不会在退出时被释放，而且 它可以用来构建链式结构，例如链表和二叉树。 堆内存的缺点是，程序必须显式调用分配和 释放函数来管理堆内存。堆内存不会像局部内存那样 自动而方便地运作。