实验 3：栈和堆#
本次实验进一步练习使用 gdb 和 valgrind，并提供了大量指针相关的代码供你阅读和练习。数组和指针在 C 语言中无处不在，充分理解它们至关重要。以下一些问题用于检测你的理解，并让你进一步思考这些概念：
如果
ptr声明为char*，ptr++的作用是什么？如果ptr声明为int*有什么区别？尽管将
&应用于栈上分配的数组名（例如&buffer）是合法的表达式并且具有特定的含义，但实际上这样的用法并不明智。解释为什么这样使用可能会造成错误/误解。malloc函数的参数是size_t（无符号整型）。考虑一下错误的调用malloc(-1)，这似乎完全没有意义。但编译器没有任何警告信息——为什么会这样？如果程序中有这样的代码，可能会发生什么？realloc函数的目的是什么？如果尝试重新分配非malloc返回的指针（例如字符串常量）会发生什么情况？内存错误（memory error）和内存泄漏（memory leak）有什么区别？
学习目标#
进一步练习
gdb和valgrind加深对指针和数组的理解
尝试编写在堆上动态分配内存的代码
初始代码#
你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：
cp -r /home/cs102-shared/labs/lab3 ~/cs102
任务 1：堆内存的使用#
在 heap.c 文件中包含了一些使用 malloc、strdup 和 realloc 在堆上动态分配内存的代码。你可以在 gdb 中运行或跟踪该文件，其中有两个示例函数，remove_first_occurrence 和 join。
函数 remove_first_occurrence(text, pattern) 返回一个字符串，该字符串是 text 的副本，删除了首次出现的 pattern。返回的字符串是在堆上分配的，完成后将由客户端负责释放。以下列出了一些问题供你思考，以便理解这个函数的实现代码：
库函数
strstr的用途是什么？它返回什么？第 17~19 行用于处理
text中没有出现pattern的情况，即没有要删除的内容。为什么该函数返回strdup(text)而不直接返回text？第 21 行两个指针相减，其结果是什么？提示：如果
q = p + 3，则q - p结果为 3。此处sizeof(pointee)如何影响减法的结果？如果传入的表达式为
false，那么assert将终止程序。第 24 行的作用是什么？第 26 行执行后，字符串
result是否以空字符结尾？为什么？你的同事建议将第 27 行更改为
strcat(result, found + nremoved)并声称其操作是等效的。你尝试了一下，似乎确实是等效的。真的是这样吗？不，不完全是……这行代码只是“运气好”而已。它以什么样的方式错误地依赖于初始内容（堆内存上分配）？当该假设不成立时，函数将如何崩溃？尝试运行代码。如果不带参数运行
./heap，它将运行一个简短的测试，从“centimeter”中删除“time”。
函数 join(strings, strings_count) 返回一个字符串，该字符串由 strings 中前 strings_count 个字符串串联拼接而成。返回的字符串是在堆上分配的，完成后由客户端负责释放。该实现的核心函数是 realloc 函数。以下列出了一些问题供你思考，以便理解这个函数的实现代码：
在循环开始时，所需的堆内存总大小是未知的，因此无法预先进行分配。相反，它会先分配一个初始内存，然后在每次附加字符串时扩大该内存。这种按需调整内存的方式是
realloc的惯用法。提供给
realloc的分配大小参数，是额外增加的字节数呢，还是包括现有内存在内的总字节数？变量
result被初始化为strdup(strings[0])。为什么要拷贝字符串而不是直接赋值result = strings[0]？man realloc手册介绍说realloc(ptr, newsize)的返回值可能与ptr相同，但也可能不同。如果不同，realloc会将旧位置的内容复制到新位置，然后释放旧位置的内存。更改代码，在调用realloc后不使用其返回值（即，不重新赋值给result，直接丢弃返回结果）。重新编译程序，你应该会收到编译器的警告。该警告试图让你注意什么错误？不捕获返回值的realloc调用永远不正确的！尝试运行代码。如果使用一个或多个参数运行
./heap，它将使用join函数将所有参数连接在一起。
最后，我们将研究 calloc 的实现（malloc 内存分配函数的替代函数），以便更好地理解堆内存分配的工作原理。首先，阅读该函数的文档 man calloc，然后查看 musl_calloc 实现（基于 musl 的代码）。
calloc 接口包含用于确定分配数组元素个数的 nelems 以及元素类型大小的 elemsz。该接口会将内存内容初始化为零，这是 calloc 区别于 malloc 的特点。以下列出了一些问题供你思考，以便理解这个函数的实现代码：
用数组描述的
calloc接口可能有些误导，因为其操作没有任何特定于数组的内容。它只是分配一个总大小为nelems * elemsz字节的区域。调用calloc(10, 2)或calloc(4, 5)或calloc(1, 20)效果完全相同，分配的内存都可以用来存储长度为 20 的字符串或长度为 5 的整型数组。该函数的第 44~46 行在做什么？如果删除这些代码对函数的运行会产生什么影响？
你的一位同事反对在第 44 行使用除法，因为除法比乘法更耗时，并且需要额外检查零除数。他们建议将其更改为
if (nelems * elemsz > SIZE_MAX)，认为这是等效的并且运行更高效。请你向他们解释为什么这个方案行不通。第 48 行将
p声明为void*类型，它与malloc的返回类型匹配。void*是泛型指针，它存储一个地址，但不声明数据的类型。对void*解引用或进行指针算术运算是非法的，因为这两个操作都取决于数据的类型，但在本例中指针的类型是未知的。然而，void*可以省略显式强制转换直接赋值。第 49 行的目的是什么？如果删除该测试并且它始终进入循环，会对函数的操作产生什么影响？
第 51 行包含表达式
sizeof(*wp)。鉴于wp已声明但未进行分配，这看起来会解引用一个未初始化的指针！但此处不用担心，事实证明sizeof是在编译时根据其声明类型来计算表达式大小的。由于wp被声明为long*，因此表达式*wp的类型为long，在服务器上其大小为 8 个字节。编译器会将其转换为(total + 8 - 1)/8。进一步深入研究第 51 行，这行代码应该会让你想起实验 1 中的
roundup函数。对于calloc(20, 4)、calloc(2, 7)或calloc(3, 1)这些调用，nw的值是多少？正如你的推测，这是一个舍入操作。对于给定的请求malloc实际上分配了多少个字节，该表达式做出了一个假设。请问这个假设是什么？ 注意，这个行为不是该接口默认提供的，在使用过程中我们不应该假设这一点。由于calloc和malloc是由同一个程序员编写的，其对malloc内部结构了如指掌，因此calloc的实现作了这样的假设。第 52 行
for循环的初始化部分，赋值语句wp = p中的wp和p的声明类型不同，这里为什么不需要类型转换？如果添加类型转换wp = (long *)p，该函数的行为是否会有所不同？第 52 行
for循环的增量部分使用了 C 语言的逗号运算符，难得一见！可以在维基百科上阅读有关逗号运算符的更多信息；在实际代码中你可能看到该运算符的唯一用途是将多个表达式打包到循环的初始化或增量部分中。在本例中，增量部分将同时使指针wp前进并减少迭代的计数nw。想象一下，如果第 50 行的声明改为
char* wp，代码其他部分不进行更改，这将如何改变该函数的行为？如果声明是int* wp情况又会如何？如果声明是void* wp呢？对于每种情况，考虑指针类型如何影响wp++和*wp = 0的操作。你认为作者选择long*的动机是什么？
任务 2：Valgrind 检测内存错误#
上个实验介绍了 Valgrind。随着我们不断编写大量使用指针和动态内存的 C 代码，这个工具将变得越来越重要。特别是，Valgrind 非常擅长检测与动态内存相关的内存问题，例如越界写入已分配的内存、访问已释放的内存、重复释放内存等。程序 buggy.c 植入了一些堆内存使用上的错误，可以看看 Valgrind 是如何处理和报告这些错误的。
查看
buggy.c中的程序并考虑error #1。当执行./buggy 1 argument调用时，程序将把argument复制到堆分配的 8 个字符的空间中。如果参数太长，写入内存时，数据将超出分配空间的末尾——即“缓冲区溢出”。类似之前的字符串写入溢出，区别是当时溢出发生在栈内存上，而此处溢出发生在堆内存上。这类错误会产生什么后果？我们来观察一下。运行
./buggy 1 leland程序可以正确运行，参数长度符合程序条件。现在尝试更长的参数./buggy 1 stanford和./buggy 1 lelandstanford，但令人惊讶的是，这些参数似乎也“没问题”，显然在溢出相对较小的情况下，程序仍然可以幸运地执行。可以继续尝试更长的输入，似乎很难暴露溢出的问题。许多程序错误并没有明确给出“segmentation fault”这样的提示，但这类错误通常也会破坏程序的状态，并且非常难以发现。此时就需要使用 Valgrind 来辅助我们。
尝试
valgrind ./buggy 1 stanford并查看 Valgrind 的报告，看看它提供了哪些信息。无论写入超出 1 个字节还是 1000 个字节，Valgrind 都会在越界时提供错误报告。这是一个非常强大的工具！error #2和error #3提供了其他滥用堆内存的问题。依次检查这些代码，确定问题的形式，然后运行（例如./buggy 2）。是否可以观察到错误结果？在 Valgrind 下再次运行它。如果能把 Valgrind 报告中使用的术语关联到错误代码，后续遇到类似报告时，就可以很快定位问题所在。
需要警醒的是，内存错误（memory error）可能非常难以捉摸。当错误发生时，有些程序会立即崩溃，但有些程序隐藏较深，会悄悄破坏一些东西，直到运行很久以后才会暴露。所以，这类错误很难将观察到的情况与其根本原因联系起来。最令人沮丧的是那些“运气好”的错误，它们一般不会造成明显的破坏，但在某些特殊的情况下，往往会给你带来“惊喜”。养成在开发过程中尽早并经常使用 Valgrind 的习惯，例行检测并消除内存错误！
任务 3：Valgrind 检测内存泄漏#
虽然内存泄漏（memory leaks）不是内存错误，但 Valgrind 也可以帮助我们检测此类问题。内存泄漏是指在堆上分配内存但不释放它。这类问题很少会导致程序崩溃，所以我们建议你在程序编写完成之前，不要过早担心内存泄漏。等程序开发完成后，再安排时间专门处理内存释放的问题，但要确保每一次释放的正确性。然而，内存泄漏仍然是一个程序设计上的错误，因为你的程序有责任清理不再需要的任何内存。特别是较大的程序，如果你分配非常大的内存但却从不释放，那么很可能会耗尽堆中的内存！
程序 leaks.c 植入了一些内存泄漏的代码，练习并了解 Valgrind 如何处理并报告内存泄漏问题。
查看
leaks.c中的程序并考虑leak #1。当执行./leaks 1时，程序将在堆上分配 8 个字节，但随后立即返回，导致程序丢失该堆内存的地址。此时发生了内存泄漏，但程序却正常终止了。让我们看看 Valgrind 如何帮助我们检测这个问题。尝试
valgrind ./leaks 1并查看 Valgrind 报告，看看提供了哪些帮助信息。你会注意到 Valgrind 输出的底部报告了 “LEAK SUMMARY” 以及整个堆的使用情况的摘要，其中显示了退出时仍在使用的内存（退出应该释放）。你还可以看到报告的分配和释放的数量不匹配，这也表明存在泄漏。非常有帮助！有关内存泄漏更多信息，请确保在运行 Valgrind 时使用
--leak-check=full和--show-leak-kinds=all参数标志。像这样再次运行valgrind --leak-check=full --show-leak-kinds=all ./leaks 1将显示更多信息，包含泄漏的内存在代码中最初分配的位置！我们建议始终使用这些参数标志运行 Valgrind 以便获得最多信息。请确保将这些标志放在运行实际程序的命令之前。具体来说，以下内容并不等效：valgrind ./leaks 1 --leak-check=full --show-leak-kinds=all，因为这会将这些标志传递给你的程序，而不是 Valgrind 本身！报告中的“definitely lost”、“indirectly lost”等有什么区别？了解更多信息可以查看 Valgrind guide 在线文档。
leak #2和leak #3提供了其他内存泄漏的可能表现形式。依次检查这些代码，确定问题的形式，然后运行（例如./leaks 2）。可以看出程序每次运行都很良好。现在在 Valgrind 下运行它。请注意 Valgrind 报告使用的术语以及它与根本原因之间的关系。请注意，泄漏不仅是使用malloc分配的内存。像strdup这样的函数也会分配内存，由调用者负责释放！整个堆的使用量不仅仅包括显式分配，其他函数（例如
strdup）也可以在内部分配/释放内存！
任务 4：调试练习#
在编程过程中，使用良好的调试策略至关重要。一个良好的调试策略包括如何使用 GDB 和 Valgrind 等调试工具并了解其内部机制，以及如何有效地利用它们在整个调试过程中查找、缩小范围并修复错误。现在是时候花点时间掌握 gdb 等调试器提供的强大功能，并学会一套周密且系统的调试方法！这是在调试时应该使用的一份核心清单（摘自 GDB and Debugging）。花一分钟时间阅读以下步骤：
观察漏洞行为。如果你从没见过程序崩溃，你也很难修复漏洞。这也是你要进行全面测试的一个原因。
创建一个可复现输入。创建一个可以触发程序失败的可靠输入将会提供巨大的帮助。
缩小检查范围。调查整个程序或者一行一行执行通常来说不太可行。关于如何缩小检查的范围，以下给了一些建议：
凭直觉，先从可能出错的位置开始，例如最近更改的代码或其他可疑的地方。
使用二分查找来剖析。在中点设置一个断点，然后查看程序状态是否已经出错（这表明问题在前半部分）或看起来不错（从而需要将注意力集中在后半部分）。重复以上过程，以进一步缩小范围。
在 Valgrind 下运行以识别任何潜在内存错误的根本原因。
在 GDB 下运行以识别任何崩溃的根本原因
分析。范围缩小后，就只需要检查少量代码，此时单步调试就变得非常可行。使用
gdb查看变量值、控制流等，看看能发现什么。通过画图，也可能会有帮助。设计实验并验证。推断漏洞的根本原因并设计实验来验证你的假设。重复这个过程，直到找出根本原因。
修改代码消除错误。修复是否成功应该根据你的实验和测试用例来验证。你应该能够解释漏洞的根本原因，以及测试和推论这些事实。
以上策略的一个关键原则是不要随意更改代码。类似科学实验，每次只改变一个变量。否则，这将使观察到的行为更加难以解释，并往往会引入新的错误。也就是说，如果你发现代码有错误，即使它和你现在正在跟踪的错误没有明显关联，你仍可能会停下来先修复它。但请遵守以上策略，使用可重现的输入来触发、修复并验证错误。该错误可能与原始错误有关或掩盖了原始错误，所以最好的措施是消除任何潜在的干扰源。
利用这种调试策略，你将可以有效地发现、理解并修复程序中出现的任何错误。鉴于此，我们提供了一个程序 pig_latin.c 供你练习以上策略，其中植入了一个潜在的漏洞。该程序的功能和课上讲解过的程序类似，只不过此处使用单纯的 C 语言重新实现了一遍。然而，它似乎在某些输入上崩溃了！特别注意代码最近所做的更改，在 pig_latin 函数的开头添加了几行代码，如果该单词无法翻译为 Pig Latin（以非小写字母的字符开头），则返回 NULL。但当运行一些自定义测试时，程序似乎无法通过。我们按照上面的调试流程来修复下！
观察漏洞行为。这部分已经为你完成。在
custom_tests中有一个自定义测试用例触发了程序崩溃。尝试使用sanitycheck运行看看！创建一个可复现输入。初始项目已经提供了一个触发崩溃的测试用例，但是输入比较复杂，对调试来说不太方便。尝试使用一个尽可能简单的输入来重现错误非常重要，这样可以更好地理解其输出，并且方便后续调试。根据目前提供的信息尝试在自定义测试中创建一个这样的输入。先不要查看源码！有时可以避免被不相关代码误导。
缩小检查范围。现在的任务是缩小可能导致崩溃的代码范围。这对于缩短调试过程非常重要，例如如果错误仅潜伏在一个地方，则没必要逐步执行整个程序。幸运的是，GDB 可以为我们做一部分工作！如果你在 GDB 中运行程序，它会在发生崩溃的源码处暂停，让你查看程序的状态。现在尝试这样做：
使用你在上一步中发现的测试用例在 GDB 中运行程序
当程序崩溃时，你应该可以看到 GDB 警告出现段错误，以及导致崩溃的代码行！
尝试使用
backtrace命令查看崩溃时程序的调用栈——这将准确显示执行过程中发生崩溃的位置。你还可以打印出变量值并使用其他 GDB 命令来检查程序崩溃时的状态。非常好！现在我们已经缩小了导致问题的代码范围。
分析。现在的工作是在这种状态下使用 GDB 进行探索，获取有关程序崩溃原因的更多信息。尝试打印出变量值，找出该行发生崩溃的原因。然后尝试使用 GDB 再次运行该程序，但应该在发生崩溃的函数开头设置断点，并单步调试，看看发生了什么。
设计实验并验证。一旦对导致问题的原因有了某种假设，就应该设计一个测试输入，并使用 GDB 来验证你的假设。
修改代码消除错误。现在集思广益并尝试修复这个问题。确保你准确理解正在做出的改变，以及为什么要做这些改变。运行之前的测试，确认更改是否解决了问题。至此，我们修复了这个错误——完美！
希望这个过程可以让你更好地了解如何遵循有效的调试策略，让调试的每一分钟都变得有意义。以下是一些其他关键要点：
良好的测试有助于发现错误。正如步骤 1 所示，如果不先发现潜在的错误，你将无法施展你出色的调试技能！确保测试的完整性，尽早触发任何潜在的问题。
尽可能让自己少做一些工作。简单且可重现的输入是让调试和跟踪更容易的关键。如果输入非常复杂，那么追踪起来可能会非常困难！同样，缩小问题代码的范围可以让你只关注该代码块而不是整个程序。
良好的风格可以使调试更容易。合理的分解、注释以及代码组织，可以让程序更容易调试。想象一下，如果代码注释很糟糕，或者全部包含在一个函数中。那将浪费更多的时间！
一个好的调试器是系统化的。任何级别的程序员都花费大量时间进行调试。提高调试技能的关键是知道如何尽可能有效地规划你的时间，缩小调试范围并消除这些错误！