下载掌阅APP，畅读海量书库
立即打开
数据结构毫无疑问是任何程序的核心部分。内存分配和释放以及数据对象的构建、析构、引用和访问是一个程序最普遍的操作。因为C/C++语言赋予程序员通过引用和指针来操纵内存对象的最大自由，所以毫不奇怪的是这些程序中的大多数bug都与错误的内存访问有关。笔者每天都在调试程序故障，例如段错误引发的程序崩溃，包括内部测试和客户生产环境，因此在这方面有很多的实际经验。大多数问题都可以归结为对分配的内存块的错误使用。
根据错误发生的位置是栈还是堆，内存错误可分为两种：栈错误和堆错误。
栈是分配给每一个独立的控制流（线程）的连续内存区域，用于追踪线程的动态函数调用链。每个函数在进入时会分配一个栈帧，即一个内存块，其大小取决于架构的应用程序二进制接口的规定ABI（Application Binary Interface）和函数的传入参数、局部变量、上下文（ABI要求保存的寄存器）、编译器临时操作区域等。任何时刻，一个线程都有一组嵌套函数，也就是调用栈，其中两个相邻的函数是调用方-被调用方（caller-callee）的关系。这些函数的栈帧像煎饼一样叠在一起，被调用函数的帧紧随其调用者栈帧之后。
随着线程运行，函数可能调用另外一个函数，另外一个函数可能再调用另外一个函数，或者函数可能返回到它的调用者。因此，线程栈会随着调用栈不断地拓展或缩小。但是栈的大小是有限制的。比如，主线程（也就是进程创建时的第一个线程）的大小是由生成这个进程的shell的栈大小ulimit设置决定的；对于Windows，它的值被链接器存储在二进制文件中。对于动态创建的线程，传递给API以创建线程的参数之一是新线程的栈大小。线程一旦创建，它的栈大小上限就被固定且不能溢出。如果嵌套函数调用深度太深或者栈上有很多局部变量，栈可能被溢出。在这样的情形下，程序很大概率会崩溃，这是因为许多系统在线程的栈末尾放置了保护页以捕获栈溢出；如果没有保护页或者保护页没有足够大来抓住溢出，也可能随机损坏其他内存区域。
另一个常见的栈bug是局部变量覆盖栈上的其他数据对象。编译器在栈上存放了许多重要的信息，比如函数的返回地址和指向前一个栈帧的指针等，这些是函数调用和返回的必要信息，并且必须符合ABI的调用规则。对这些数据的损坏可以轻易搞垮程序，甚至有可能造成程序安全漏洞。
堆是程序代码显式创建和释放动态数据对象的内存区域。堆服务于同一进程下的所有线程，它的地址通常紧接在可执行文件的全局数据段之后。堆是由被称为内存管理器（或简称为分配器）的组件管理。它的工作很像一个批发商，从内核中大块获取内存，然后将它们分割成小块以满足应用程序的单独内存请求，这显然是为了减少调用内核接口的缓存方案。
除了栈和堆内存之外，全局数据也是应用程序访问的一种存储类型。它们被放置在.data节（初始化的数据）或者.bss节（未初始化的数据）。一旦模块被加载到进程中，它的全局数据位置就被分配并不再改变。全局数据的生命周期跟包含它的模块相同。只要程序在编译时生成了全局数据的调试符号，调试器就可以在任何时候任何上下文观察到程序的全局对象。用户可以随时随地查看它们的值或者设置相应的监测点。从这个意义上说，调试全局数据对象相关的内存错误相对容易。
在调试内存问题的时候，有必要了解内存的组织方式。对于栈来说，关键是栈的内存布局，我们将会在讲解架构特定ABI时详细讨论这一点。而对于堆来说，内存管理器使用的数据结构和底层内存分配算法无疑是最重要的。
内存管理器记录着每个堆内存块的大小和状态，即内存块是空闲的还是在使用中。这个简要信息常常可以帮助我们缩小一个棘手问题的范围，并提供强有力的证据来证明或者证伪一个理论。比如当程序因为访问一个堆对象而出错时，搞清楚这个对象是活跃的还是已经被释放了非常重要，它将引导我们在随后的调查中使用不同的调查策略，而这个状态信息可以通过底层内存块的实现来获得。
了解内存分配算法的一个例子是分析数据对象的引用关系。当发现一个结构损坏时，可以搜索进程的整个内存来寻找指向可疑结构体的所有指针。如果这样的指针存在，下一步就是确定这个引用是有效的以及持有该引用的数据对象的类型。内存管理告诉我们包含该引用底层内存块的状态。空闲内存块的引用显然是无关的；对于正在使用的内存块，我们可以根据大小将其对象的类型限制到几个有限的选项中。尽管我们不知道对象可能具有的数据成员，但通过分析内存块范围内的数据内容，也许可以找到对象类型的线索，例如通过指向对象虚函数表的指针。
内存分配和释放是大部分应用调用最频繁的函数之一。毫无疑问，性能对于内存管理器的任何实现都至关重要。同时，将进程的内存占用最小化也是必要的。虽然内存芯片的价格一年比一年低，但应用规模也在稳步增长，对内存的需求也越来越大。臃肿的进程具有糟糕的内存局部性，这反过来会影响程序的性能。因此，内存管理器需要节俭并控制内存使用，同时快速满足应用程序的内存请求。这些对性能和资源节约的竞争需求常常使内存管理器陷入两难境地，结果使内存管理器的堆数据结构和算法也变得很复杂。内存管理器是系统运行的一个重要模块，实际应用中用户也常常使用自己的实现来满足程序的特殊需求。虽然破译堆数据结构具有挑战性，但它对调试内存问题确实非常有帮助。