第二章 堆数据结构

数据结构无疑是任何程序的核心部分。内存分配和释放，数据对象的构建、析构、引用和访问是一个程序最普遍和复杂的操作。因为C/C++语言赋能程序员通过引用和指针最大的自由去操作内存对象，不会有人惊讶这些程序大部分的bugs是跟一种形式或者另外一种形式的错误的内存访问。我在这方面有一手的经历，因为每天都在调试如段错误这种程序错误。这些问题包含室内的测试和客户产品的环境。大部分问题归结为分配内存的不正确使用。

取决于错误发生在哪里：栈还是堆，内存错误有两种。

栈是分配给每一个独立的控制流：线程，的连续内存区域。它用来追踪线程的动态函数调用链。每一个函数在进入的时候会分配一个栈帧，一个大小取决于架构的ABI(Application Binary Interface)的内存块和函数的传入参数、局部变量、上下文（ABI要求保存的寄存器）、编译器操作的区域等等。一个函数在任意一个时刻有一群嵌套的函数，也就是，调用栈，在这当中，两个相邻的函数是caller-callee的关系。这些函数栈帧像一叠蛋糕叠在一起。被调用的函数栈帧紧邻它的调用者栈帧的后面。

随着一个线程运行，一个函数可能调用另外一个函数，另外一个函数可能调用另外一个函数，或者一个函数可能返回到它的调用者。因此，一个线程栈会随着调用栈持续性的伸展和收缩。但是栈大小是有限制的。比如，主线程的栈大小，也就是当进程创建时的第一个线程，是由生成这个进程的shell的栈大小ulimit设置决定的；对于Windows，它是一个存储在二进制文件被链接器设置的。对于动态创建的线程，传入创建线程API的其中一个参数是新线程的栈大小。因此，当一个线程创建以后，它的栈大小上限是固定的和不能超出。如果嵌套的函数调用深度太深或者栈上有很多局部变量，栈可能被溢出了。在这样的情形下，因为许多系统为了抓住栈溢出在线程的栈末尾放置了保护页，程序很大概率会crash；如果没有保护页或者保护页没有足够大来抓住溢出，它也可能随机的损坏其他内存区域。

另外一个常见的栈bug是当一个局部变量覆写栈上的其他数据对象。在栈上，有许多重要的信息，比如，函数的返回地址和指向前一个栈帧的指针等等，这些是由编译器和链接器根据为了让函数调用和返回成可能的ABI规则生成的。对这些数据的损坏可以轻易搞垮程序或者更糟糕的是击破程序的安全。

堆，另外一方面，是程序代显示创建和释放动态数据对象的内存区域。堆服务于所有在同一个进程下的线程。它通常在可执行文件的全局数据段后面开始。堆是被一个叫做内存管理器的模块管理，或者简单叫分配器。它工作很像一个批发商，从内核获取大块的内存，然后为了满足应用程序每个内存请求，将大块的内存削成小的碎片。

除了栈和堆内存，全局数据也是应用程序访问的另一类存储。他们要么放置在.data节（初始化的数据）或者.bss节（未初始化的数据）。当一个模块被加载到进程，它的全局数据位置被分配，不会再改变。全局数据的生命周期跟包含它的模块一样。只要程序被编译了调试符号，调试器对程序的全局对象有完全的可见性。一个用户可以查看它们的值或者在任何时候任何上下文对它们设置监测点。因此，调试全局数据对象相关的内存错误是相对容易的。

在调试内存问题的时候，知道内存是怎么组织的是非常基本的。对于栈，关键是栈的内存布局，我们将会在第五章谈论架构特定ABI的时候讨论细节。对于堆，内存管理器使用的数据结构和底层内存分配算法是最重要的。

内存管理器记录着每一个内存块的大小和它是空闲的还是使用中。这个简单但重要的信息常常可以帮助我们缩小一个挑战性问题的范围和为证明或者证伪一个理论提供强有力的证据。比如当一个程序因为访问一个堆对象垮掉的时候，搞清楚这个对象是活跃的还是已经被释放了是非常重要的，这可以通过底层的内存块的状态来决定。这个结果可以引导随后的调查到不同的策略。

在举一个例子，为了找到一个损坏结构的任何引用，一个方案是搜索进程的整个内存来寻找指向可疑结构体的指针。如果这样的指针存在，下一步是确定这个引用是有效的和持有这个引用的数据对象的类型。内存管理告诉我们包含这个引用的底层内存块的状态。一个在空闲内存块的引用显然是无关的和可以被标红。另一个方面，使用中的内存块的大小可以限制数据类型到一些候选项。尽管我们不知道这个对象可能有的数据成员，通过分析在范围内的内存块的数据内容，我们也许可以找到对象类型的线索，比如通过指向对象的虚拟表。

内存分配和释放是大部分应用最频繁被调用的函数。不用说，任何一个内存管理器的性能是非常重要的。同时，最小的保留进程的内存印记是非常紧要的。尽管内存芯片每年越来越便宜了，应用的规模稳定地增加的同时也在需要越多的内存。一个爆炸性的程序有不好的内存局部性，从而影响程序的性能。因此，当内存管理器在满足应用的内存请求的时候，需要节省和保证内存使用在控制中。这对性能和资源节省的互相竞争的需求经常让内存管理器处于两难境地。结果是，一个内存管理器的堆数据结构和算法通常复杂和不透露给终端用户。内存管理器是系统运行的一个模块，尽管一个用户可以使用他自己的实现。破解堆数据结构具有挑战性，同时对调试内存问题也非常有帮助性。