实验 4：泛型和回调#

本次实验带你了解原始内存的世界。目标是让你能够写出并使用将函数作为参数的代码（包括一些神秘的语法），并了解如何尽可能地利用类型系统来编写代码，以及在没有类型系统的情况下该如何处理。你应该知道如何正确调用 memcpy/memmove，确切地知道在哪里需要类型转换以及为什么需要，并且对二级指针的正确使用提高警惕。

以下一些问题用于检测你的理解，并让你进一步思考这些概念：

  • 为什么必须在指针算术表达式中对 void* 进行类型转换？

  • 当源和目标重叠时 memcpy 的行为是什么？ memmove 如何正确处理重叠区域？

  • 非对称比较函数是将其两个 void* 参数转换为不同的指针类型的函数。为什么将非对称比较函数传递给 bsearch？

  • C 语言搜索函数找到元素后，通常返回一个指向该元素的指针，而不是元素本身。为什么是这样？

学习目标#

  • 探索 C 语言中的 void* 和函数指针如何用于泛型编程

  • 学习如何实现泛型函数和用户回调函数

  • 调试 void* 陷阱

初始代码#

你的个人用户目录下应该已经有 cs102 这个文件夹了，通过下面的命令拷贝初始代码到该目录中：

cp -r /home/cs102-shared/labs/lab4 ~/cs102

任务 1：回调函数#

C 标准库中的通用排序/搜索函数（qsort、bsearch、lfind …）是可以对任何类型的数据进行排序/搜索的。然而，为了做到这一点，这些接口需要用户提供比较函数，以便让它们知道如何比较两个值。所有这些函数都使用相同形式的标准比较函数：

int comparison_fn_t (const void *, const void *)

你实现的任何版本的比较函数，都要接收指向两个待比较值的指针，并返回一个表示比较大小的整数，类似 strcmp 的 +/-/0 返回值。

要理解的最关键的问题是，所有通用操作都是通过指向值的指针来处理数据的，而不是直接处理值。通过地址引用数据是 C 支持泛型函数的基础。发送或接收实际值是不现实的，因为这些值的类型/大小各不相同。相反，交换的是指向值的指针。所有指针，无论指针对象是什么，都是与 void* 类型兼容的 8 字节地址。

比较函数的实现遵循以下类似的模式：

  1. 将 void* 参数转换成已知类型的指针

  2. 解引用类型化的指针以访问该值 （步骤 1 和 2 通常结合起来，在一个表达式中进行强制转换并解引用）

  3. 比较值以确定要返回的结果

实际的比较逻辑（步骤 3）通常很简单；你必须小心的是步骤 1 和步骤 2 中对 void* 的处理，确保不要出错。

查看 callbacks.c 文件中的比较函数示例，了解每个函数是如何实现上述模式的。以下是一些需要思考的问题：

  • 这些回调函数内部立刻转换 void* 参数并存储到类型正确的局部变量中。预先执行此操作，而不是每次使用时再转换并解引用，这样处理有什么优点？

  • 向 qsort 提供不同的比较函数，允许你使用不同的条件对数组进行排序。例如，对自定义结构体 city 进行操作的两个回调函数，分别按不同的字段进行排序。如何编写一个比较函数，实现逆序排序？如何编写一个比较函数，将一个字段作为主要排序顺序进行比较，再通过辅助字段来比较相等的字段？

  • 按邮政编码对城市进行排序的比较函数，该实现采用了一种快速的方法来计算正、负或零的比较结果，并返回两个值之间的差异。你明白它是如何运作的吗？这是比较整数值的常见快捷方式。（注意：如果差值超过 INT_MAX，减法就会溢出，因此如果需要支持此类极值，请使用 if/else 进行判断。）

  • 所有比较函数都符合上面列出的原型。这意味着任何比较函数都可以应用于任何类型的数组——不特定于任何类型。使用字符比较函数对 int 数组进行排序会产生什么结果？使用字符串比较函数对城市数组进行排序又会怎么样？

  • 仔细观察并识别 compare_letters 和 compare_strings 回调之间的细微差别。可以使用 compare_letters 按第一个字母对字符串数组进行排序吗？为什么？

  • GNU libc 文档给出了一个 compare_doubles 比较函数的示例。乍一看，该实现逻辑有点难以理解，所以一起来研究一下。评估类似 5 > 2 之类的不等式的结果是什么？尝试在 gdb 中确认！在这个案例中，为什么两个不等式相减，可以计算出正确的结果？

任务 2：探究 gfind_max#

在文件 generic.c 中包含了一些写好的代码。其中，gfind_max 是我们编写的一个通用函数，根据用户提供的比较函数查找最大的数组元素。查看该函数的实现，先了解下泛型函数是如何实现的。

以下一些问题用于检测你的理解，并让你进一步思考这些概念：

  • 第 40 行是一个对通用数组中第 i 个位置的惯用访问方式。确保理解该表达式的目的和操作逻辑。类型转换为 (char*) 的目的是什么？删除该转换会产生什么后果？

  • 网站 cdecl.org 可以将 C 晦涩的声明转换成可读的英语。当试图解开一个难以理解的声明时，这个工具很方便。复制 compare_function 的参数声明并粘贴到 cdecl 中，看看其英文解释。

  • 需要注意的是，通过函数指针实现的回调函数，看起来与普通函数调用几乎相同。如果尝试使用错误数量或类型的参数调用函数指针时，会发生什么情况？尝试编辑 generic.c， 修改 gfind_max 的参数，删除 compare_function 的一个参数，看看会发生什么。

  • gfind_max 返回一个 void*。该指针代表什么？为什么函数返回一个指向值的指针而不是值本身？

  • 用户如何使用 gfind_max 来查找最小元素而不是最大元素？

然而 void* 接口天生的宽松的特性，必然会带来危险的客户体验。滥用泛型函数的方法有很多种，并且编译器通常不会警告你的这些违规行为。让我们进一步探讨这种情况。

文件 generic.c 中的 test_max 函数对 gfind_max 进行了四次调用。第一次调用完全正确，并打印了预期的结果。随后的三个调用中的每个调用，在某种程度上都是不正确的。对于下面的每一个，尝试计算出你认为会打印的内容，然后通过运行程序来验证你的理解是否正确。在 gdb 中绘制内存图并跟踪程序的状态，可能对理解程序的行为非常有帮助。

  • 不正确的调用 call #1 传递了一个用于 int 元素数组的 char 比较函数。奇怪的是，为什么这样的错误调用没有编译或运行时报错？运行 Valgrind 报告有什么帮助吗？在这种情况下 gfind_max 的表现如何？

  • call #2 中的错误是什么？报告的“最大值”从哪里来？注意字节的顺序，我们的服务器采用的是“小端法”表示。

  • call #3 中的错误是什么？为什么这个调用总是返回指向最后一个元素的指针？

任务 3：探究 bsearch_bug#

现在检查文件 bsearch_bug.c 中的函数 test_bsearch。 bsearch 是一个 C 标准库函数，用于搜索数组中的元素。通常，为了使 bsearch 能够正常工作，必须使用搜索时使用的相同比较函数对数组进行排序。编写此函数的程序员却无法理解这个机制，他不明白为什么可以使用相同的比较函数。最终，他的实现使用了与排序时不同的比较来进行搜索。他知道这样的实现不太好，但无法找到正确的解决方案。

在开始之前，请记住核心原则：所有泛型操作都是通过指向值的指针来处理数据的，而不是直接处理值。当你探索这些代码时，请记住这一点。绘制内存图并跟踪正在使用的指针和间接引用的级别。此代码是作业 4 中常见的错误示例，因此现在深入了解它，可以更好地完成作业！

  • 按原样编译程序并运行它，可以观察到，尽管比较函数不匹配，但它似乎确实有效。更改代码，使用 compare_first_characters 作为排序和搜索的比较函数。运行这个版本时，程序就会崩溃。代码中的哪个操作会崩溃？为什么？

  • 原作者的解决方法是添加一个不同的比较函数用于搜索。这是一个潜在的危险操作，该比较函数将其两个 void* 参数类型转换为不同的指针对象类型。它能够正常“工作”的机制并不周全，并且依赖于 bsearch 实现中的一些具体细节，这对于其他通用函数的实现来说可能不正确。你能看出是什么细节吗？如果你非常仔细地阅读 man bsearch 的文档，你会发现，只根据文档要求来，这个实现细节肯定是正确的（查看文档的第二段），但以这种方式实现，仍然不是一个好主意，有一点拼凑的嫌疑（提示：比较函数的第一个参数代表什么？第二个参数代表什么？）

  • 对代码进行正确的修复，使用相同的比较函数 compare_first_characters 进行排序和搜索，并使程序正常工作（提示：在调用 bsearch 时仔细查看传递给 bsearch 的参数值）。

本练习的目的是强调作为用户，在使用 void* 接口时保持警惕的必要性。同时也说明在编写代码时，试图通过反复试验并拼凑出一份正确代码，也是徒劳的。

虽然随机排列 * & 和类型转换可能最终会得到正确的组合，但这种方法对你的理解绝对没有任何帮助。

相反，如果你花点时间在纸上画出操作过程、绘制图表并在 gdb 中跟踪执行情况，那么你就会明白在什么样的上下文中使用什么级别的间接引用更合适，并且能够深刻理解其中的原因。加油吧，少年！

任务 4：探究 memmove#

C 标准库提供了一些原始内存（raw memory）相关函数，可以对未指定类型的数据进行内存级别的操作（例如 memcpy、memset 等）。在文件 memmove.c 中包含了一个 memmove 的实现，该版本基于 musl 的实现代码。一起来研究下函数的实现，以便更好地理解这些函数是如何实现的。

以下一些问题用于检测你的理解，并让你进一步思考这些概念：

  • 该函数的接口将其参数声明为 void* 指针，但在内部它将这些指针作为 char* 进行操作。这里为什么不一致？尝试通过将接口声明为 char* 或更改实现为 void* 来统一操作，这将产生什么后果？

  • 请注意第 11 和 12 行，非类型化指针赋值给类型化指针时，没有强制类型转换。void* 是通用指针，可以与其他指针类型自由交换，无需强制转换。话虽如此，关于是否需要强制类型转换的争议问题，网上一直存在着一场持续不断的讨论；这里采用的策略是不作转换，因为这是非必需的。

  • 第 14 行在处理什么特殊情况？

  • 查看 memcpy 和 memmove 的 man 文档，了解这两个函数之间的差异。第 18 行在处理什么特殊情况？

  • 第 22 和 27 行的 if/else 区分了哪两种情况？为什么这两种情况都是必要的？

  • memmove 的 man 文档指出，该操作就像复制了两次数据一样（src->temp、temp->dst），这意味着调用 memmove 的时间可能是调用 memcpy 的两倍。然而，musl 并没有按照文档字面的方式实现。它不仅正确处理了重叠问题，还避免了复制两次的问题。那么它是如何操作的呢？关注下第 24~26 行和第 29-31 行——每个循环中发生了什么？在此实现中，使用 memmove 相对于 memcpy 的额外成本预期是多少？

  • 跟踪调用 musl_memmove(NULL, "cs102", 0)，请问尝试读/写无效指针是否会导致段错误？为什么？调用 musl_memmove(NULL, "cs102", -1) 的情况又是什么？通过运行 memmove.c 程序来验证你的理解。

  • 为什么不总是使用 memmove？man 文档似乎暗示在使用 memmove 而不是 memcpy 时，某些实现（尽管不是 musl）确实会受到性能影响。此外，适当地使用 memmove 和 memcpy 可以告诉某些代码读取器，数据是否会发生重叠。鉴于此，我们默认使用 memcpy，仅在必要时使用 memmove。

memmove 的实现可能会让你想起 strncpy 函数。 memxxx 函数与其 strxxx 等效函数有很多共同点，特殊情况是没有在零字节处停止。事实上，memxxx 函数包含在 <string.h> 模块中，并且很可能是由同一作者编写的。

任务 5：GDB 调试技巧#

我们会定期尝试向你介绍新的有用的 gdb 命令或功能，目的是帮助你进行调试。本次实验，我们介绍“检查”命令，以及如何打印数组。对于每一个命令，尝试设置断点并打印 gdb_practice.c 文件中的值，我们已经在其中声明了一些变量。请随意编辑并使用该文件，以便熟悉这些功能。

检查命令 x（单击此处查看文档）是一个很有用的命令，用于检查内存内容，但与内存中的数据类型无关。它类似于 print，但针对的是通用内存而不是特定类型的变量。

例如，你可以使用 x 打印给定地址开始的一定数量的字节。例如，如果有一个指针 ptr，则可以通过执行 x/8bx ptr 打印出从指针记录的位置开始的 8 个字节，其中包含的是十六进制的地址。斜杠后面的可选参数指定你要打印的内容。第一个（例如 8 或 2）指定要检查的数量，第二个（例如 b 或 w）指定要打印的单位是字节还是字（一个字为 4 个字节）等，第三个（例如 x）指定如何打印它们（例如 x 代表十六进制，d 代表十进制）。

准备好后，请使用 gdb_practice 尝试以下操作：

  • 在 gdb_practice 程序上运行 gdb。在 main 上设置断点，并单步执行变量声明/初始化（包括数组 nums）之后的函数。

  • 尝试 x/4bx ptr 以十六进制打印出从 ptr 中的地址开始的 4 个字节。你看到了什么？这是为什么？

  • 尝试 x/8bx ptr 以十六进制打印出从 ptr 中的地址开始的 8 个字节。你看到了什么？这是为什么？ （提示：number2 和 number 的位置有什么关系？）

  • 尝试 x/8bx nums 以十六进制打印从数组 nums 开头开始的 8 个字节。你看到了什么？这是为什么？

如果从栈数组的声明函数中打印栈数组，gdb 将显示该数组及其内容。在这种情况下，gdb 可以访问元素类型和元素计数，并利用这些信息来打印整个数组的表示。但是，在其他上下文中，它不能自动执行相同的操作，例如堆数组或传递到函数中的数组/指针。

  • 在 main 函数中尝试使用 print 打印 nums

  • 在 my_function 中再次尝试此操作，查看该行为

然而，在这些上下文中打印整个数组是可行的，但你必须向 gdb 提供更多信息。让我们看看如何操作：

  • 在 gdb_practice 程序上运行 gdb。在 main 上设置断点，并单步执行变量声明/初始化（包括数组 nums）之后的函数。

  • 尝试 p num。在其声明的上下文中，gdb 知道它是一个特定大小的栈数组，并且可以显示整个栈数组的内容。很棒！

  • 尝试 p argv。 gdb 对 argv 的了解就是它是一个指针。糟糕！

  • 尝试 p argv[0]@argc，gdb 现在将打印 argv 数组的全部内容。万岁！

  • 要学习的语法是 p ELEM@COUNT，其中 ELEM 是要打印的第一个元素，COUNT 是要打印的元素的数量。 ELEM 和 COUNT 是 C 表达式，可以引用当前作用域中的任何变量。尝试 p nums[1]@2 显示数组中间的 2 个元素。

  • 尝试在 my_function 函数使用此功能来打印传入的数组内容。

  • 如果需要，你还可以添加类型转换。例如，给定一个 void* 类型的参数 ptr，你知道它是 char* 类型的 nelems 元素数组的基地址，那么你就可以使用 p *(char**)ptr@nelems 打印整个数组。