为什么 stackoverflow 错误乱七八糟？

Question

这个简单的 C 程序很少在相同的调用深度处终止：

#include <stdio.h>
#include <stdlib.h>

void recursive(unsigned int rec);

int main(void)
{
  recursive(1);
  return 0;
}

void recursive(unsigned int rec) {
    printf("%u\n", rec);
    recursive(rec + 1);
}

这种混乱行为背后的原因可能是什么？

我正在使用 fedora（16GiB 内存，堆栈大小为 8192），并使用 cc 编译，没有任何选项。

编辑

我知道这个程序会抛出 Whosebug
我知道启用一些编译器优化会改变行为并且程序会达到整数溢出。
我知道这是未定义的行为，这个问题的目的是 understand/get 概述可能解释我们在那里观察到的实现的特定内部行为。

问题更多，考虑到在 Linux 上线程堆栈大小是固定的并由 ulimit -s 给出，什么会影响可用堆栈大小，以便 Whosebug 不会总是发生在调用深度相同？

编辑 2 @BlueMoon 在他的 CentOS 上总是看到相同的输出，而在我的 Fedora 上，堆栈为 8M，我看到不同的输出（最后打印的整数 261892 或 261845，或 261826，或...）

Answer 1

执行之间不会有相同的行为，因为它取决于当前可用的内存。您可用的内存越多，您将在这个递归函数中走得越远。

Answer 2

你的程序会无限运行，因为你的递归函数中没有基本条件。堆栈会随着每次函数调用而不断增长，并会导致堆栈溢出。
如果是tail-recursion优化（带option-O2）的话，栈溢出肯定会发生。它调用未定义的行为。

what would influence the available stack size so that the Whosebug does not always occur at the same call depth?

当发生堆栈溢出时，它会调用未定义的行为。这种情况下的结果无话可说。

Answer 3

栈段和堆段之间有间隙。现在因为堆的大小是可变的（在执行期间不断变化），因此在发生 Whosebug 之前堆栈增长的程度也是可变的，这就是为什么你的程序很少在相同的调用深度终止的原因。

Answer 4

以上代码可能导致两个问题：

堆栈溢出。
整数溢出。

堆栈溢出： 当调用递归函数时，它的所有变量都被推送到 call stack 上，包括它的 return 地址。由于没有终止递归的基本条件并且堆栈内存有限，堆栈将耗尽导致 堆栈溢出 异常。调用堆栈可能包含有限数量的地址 space，通常在程序开始时确定。调用栈的大小取决于很多因素，包括编程语言、机器架构、多线程[=45] =]，以及 可用内存量 。当一个程序试图使用比调用堆栈上可用的更多 space 时（即，当它试图访问超出调用堆栈边界的内存时，这本质上是缓冲区溢出），称堆栈溢出，通常会导致程序崩溃。

注意，每次函数exits/return，该函数压入堆栈的所有变量都被释放（也就是说，它们被删除）。一旦堆栈变量被释放，该内存区域就可用于其他堆栈变量。但是对于递归函数，return 地址仍然在堆栈中，直到递归终止。此外，自动局部变量被分配为单个块，堆栈指针提前到足以说明它们大小的总和。您可能对 Recursive Stack in C.
感兴趣
整数溢出： 随着 recursive() 的每次递归调用将 rec 递增 1，有可能 整数溢出 可能会发生。为此，你的机器必须有一个巨大的堆栈内存，因为无符号整数的范围是：0 到 4,294,967,295。请参阅参考资料 here。

Answer 5

您的递归调用在实践中不一定会由于计算器溢出（但会由于整数溢出）而导致未定义的行为。一个优化的编译器可以简单地将你的编译器变成一个带有跳转指令的无限"loop"：

void recursive(int rec) {
   loop:
    printf("%i\n", rec);
    rec++;
   goto loop;
}

请注意，这将导致未定义的行为，因为它会溢出rec（有符号整数溢出是 UB）。例如，如果 rec 是一个无符号整数，那么代码是有效的，理论上应该永远运行。

Answer 6

当进程从可执行文件加载程序时，通常它会为代码、堆栈、堆、已初始化和未初始化的数据分配内存区域。

分配的堆栈 space 通常不会那么大（可能为 10 兆字节），因此您可以想象物理 RAM 耗尽在现代系统上不会成为问题，堆栈溢出总是会发生在相同的递归深度。

但是，出于安全原因，堆栈并不总是位于同一位置。 Address Space Layout Randomisation 确保堆栈位置的基数在程序调用之间变化。这意味着程序可以在堆栈顶部遇到无法访问的东西（如程序代码）之前执行更多（或更少）的递归。

无论如何，这是我对正在发生的事情的猜测。

Answer 7

将 printf 调用更改为：

printf("%u %p\n", rec, &rec);

这会强制 gcc 将 rec 放入堆栈并为您提供它的地址，这很好地指示了堆栈指针的情况。

运行你的程序几次，注意最后打印的地址发生了什么。我机器上的一些运行显示了这个：

261958 0x7fff82d2878c
261778 0x7fffc85f379c
261816 0x7fff4139c78c
261926 0x7fff192bb79c

首先要注意的是堆栈地址总是以78c或79c结尾。这是为什么？我们应该在跨越页面边界时崩溃，页面的长度为 0x1000 字节，每个函数占用 0x20 字节的堆栈，因此地址应以 00X 或 01X 结尾。但是仔细观察，我们在 libc 中崩溃了。所以堆栈溢出发生在 libc 的某个地方，由此我们可以得出结论，调用 printf 和它调用的所有其他东西至少需要 0x78c = 1932（可能加上 X*4096）字节的堆栈才能工作。

第二个问题是为什么到达栈尾需要不同的迭代次数？一个提示是我们得到的地址在程序的每个运行上都是不同的。

1 0x7fff8c4c13ac
1 0x7fff0a88f33c
1 0x7fff8d02fc2c
1 0x7fffbc74fd9c

栈在内存中的位置是随机的。这样做是为了防止整个系列的缓冲区溢出攻击。但是由于内存分配，尤其是在这个级别，只能在多个页面（4096 字节）中完成，所有初始堆栈指针都将在 0x1000 处对齐。这将减少随机堆栈地址中的随机位数，因此通过在堆栈顶部浪费随机数量的字节来增加额外的随机性。

操作系统只能在整个页面中计算您使用的内存量，包括堆栈限制。因此，即使堆栈从随机地址开始，堆栈上最后可访问的地址也始终是一个以 0xfff 结尾的地址。

简短的回答是：为了增加随机内存布局中的随机性，堆栈顶部的一堆字节被故意浪费，但堆栈的末尾必须在页面边界结束。

为什么 stackoverflow 错误乱七八糟？

Why are stackoverflow errors chaotic?

c

stack-overflow

recursion

operating-system