主流操作系统上程序的 C/C 最大堆栈大小

Question

我想在 100 X 100 阵列上进行 DFS。 （假设数组的元素表示图节点）因此，假设最坏的情况，递归函数调用的深度可以达到 10000，每次调用最多占用 20 个字节。那么这是否可行意味着是否存在stackoverflow的可能性？

C/C++ 中堆栈的最大大小是多少？

请为两者指定 gcc

1. Windows 上的 cygwin

2. Unix

一般限制是什么？

原文由 avd 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

在 Visual Studio 中，我认为默认堆栈大小为 1 MB，因此在递归深度为 10,000 的情况下，每个堆栈帧最多可以有 ~100 个字节，这对于 DFS 算法来说应该足够了。

包括 Visual Studio 在内的大多数编译器都允许您指定堆栈大小。在某些（全部？）linux 风格上，堆栈大小不是可执行文件的一部分，而是操作系统中的环境变量。然后，您可以使用 ulimit -s 检查堆栈大小，并使用例如 ulimit -s 16384 将其设置为新值。

这是 gcc 的默认堆栈大小的 链接。

没有递归的 DFS：

 std::stack<Node> dfs;
dfs.push(start);
do {
    Node top = dfs.top();
    if (top is what we are looking for) {
       break;
    }
    dfs.pop();
    for (outgoing nodes from top) {
        dfs.push(outgoing node);
    }
} while (!dfs.empty())

原文由 Andreas Brinck 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

（2020 年 9 月 26 日添加）

2009 年 10 月 24 日， 正如@pixelbeat 在这里首次指出的那样， Bruno Haible 凭经验发现了几个系统的以下默认线程堆栈大小。他说， 在多线程程序中，“默认线程堆栈大小” 如下。我在“实际”大小列中添加了因为@Peter.Cordes 在他的评论中指出我的答案，但是，下面显示的奇数测试数字不包括所有线程堆栈，因为其中一些用于初始化。如果我运行 ulimit -s 查看我的 Linux 计算机配置的“最大堆栈大小”，它会输出 8192 kB，它正好是 8 MB ， 而不是 列出的奇数 7.4 MB 下表是我的带有 gcc 编译器和 glibc 的 x86-64 计算机。因此，您可能可以在下表中添加一些数字，以获得给定线程的实际完整堆栈大小。

另请注意，以下“已测试”列单位均以 MB 和 KB（以 1000 个为基数）为单位，而不是 MiB 和 KiB（以 1024 个为基数）。我已经通过验证 7.4 MB 的情况向自己证明了这一点。

 Thread stack sizes

System and std library  Tested  Actual
----------------------  ------  ------
- glibc i386, x86_64    7.4 MB  8 MiB (8192 KiB, as shown by `ulimit -s`)
- Tru64 5.1             5.2 MB  ?
- Cygwin                1.8 MB  ?
- Solaris 7..10           1 MB  ?
- MacOS X 10.5          460 KB  ?
- AIX 5                  98 KB  ?
- OpenBSD 4.0            64 KB  ?
- HP-UX 11               16 KB  ?

Bruno Haible 还表示：

32 KB 超出了您在多线程程序中的堆栈上可以安全分配的空间

他说：

sigaltstack 的默认堆栈大小 SIGSTKSZ 是

• 在某些平台上只有 16 KB：IRIX、OSF/1、Haiku。
• 在某些平台上只有 8 KB：glibc、NetBSD、OpenBSD、HP-UX、Solaris。
• 在某些平台上只有 4 KB：AIX。

布鲁诺

他编写了以下简单的 Linux C 程序来凭经验确定上述值。您现在可以在您的系统上运行它以快速查看您的最大线程堆栈大小是多少，或者您可以在 GDBOnline 上在线运行它： https ://onlinegdb.com/rkO9JnaHD。

说明： 它只是创建一个新线程，以便检查 线程堆栈大小 而不是 _程序堆栈大小_，如果它们不同，那么它让该线程 在堆栈上重复分配 128 字节的内存（不是堆） ，使用 Linux alloca() 调用，然后它将 0 写入这个新内存块的第一个字节，然后打印出它已分配的总字节数。它重复这个过程，每次 在堆栈上 再分配 128 个字节，直到程序崩溃并出现 Segmentation fault (core dumped) 错误。最后打印的值是系统允许的估计最大线程堆栈大小。

重要说明： alloca() 在堆栈上 分配： 即使这 看起来像 堆上的动态内存分配，类似于 malloc() 调用， alloca() 不动态分配—到堆上。相反， alloca() 是一个专门的 Linux 函数，用于“伪动态”（我不确定我会称之为什么，所以这是我选择的术语）直接分配 _到堆栈上_，就好像它是静态的一样-分配的内存。由 alloca() 使用和返回的堆栈内存在 函数级别 范围内，因此“当调用 alloca() 的 函数 返回其调用者时自动释放。”这就是为什么它的静态范围没有退出并且由 alloca() 分配的内存不会在每次 for 循环迭代完成和 for 循环结束时被释放范围达到。详见 man 3 alloca 。这是相关的引述（强调添加）：

描述

alloca() 函数 在调用者的栈帧中 分配 size 个字节的空间。当调用 alloca() 的 函数 返回 给它的调用者时，这个临时空间会自动释放。

返回值

alloca() 函数返回一个指向分配空间开头的指针。 如果分配导致堆栈溢出，则程序行为未定义。

这是 Bruno Haible 从 2009 年 10 月 24 日开始的程序， 直接从 GNU 邮件列表复制而来：

同样，您可以 在此处在线运行它。

 // By Bruno Haible
// 24 Oct. 2009
// Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html

// =============== Program for determining the default thread stack size =========

#include <alloca.h>
#include <pthread.h>
#include <stdio.h>
void* threadfunc (void*p) {
  int n = 0;
  for (;;) {
    printf("Allocated %d bytes\n", n);
    fflush(stdout);
    n += 128;
    *((volatile char *) alloca(128)) = 0;
  }
}

int main()
{
  pthread_t thread;
  pthread_create(&thread, NULL, threadfunc, NULL);
  for (;;) {}
}

当我使用上面的链接在 GDBOnline 上运行它时，每次运行它都会得到完全相同的结果，无论是 C 程序还是 C++17 程序。运行大约需要 10 秒左右。以下是输出的最后几行：

>  Allocated 7449856 bytes
> Allocated 7449984 bytes
> Allocated 7450112 bytes
> Allocated 7450240 bytes
> Allocated 7450368 bytes
> Allocated 7450496 bytes
> Allocated 7450624 bytes
> Allocated 7450752 bytes
> Allocated 7450880 bytes
> Segmentation fault (core dumped)
>
> ```

因此，该系统的线程堆栈大小约为 7.45 MB，正如上文提到的 Bruno (7.4 MB)。

我对程序进行了一些更改，主要是为了清晰，但也是为了提高效率，还有一点学习。

**我的变化总结：**

1. \[学习\] 我将 `BYTES_TO_ALLOCATE_EACH_LOOP` 作为参数传递给 `threadfunc()` 只是为了练习在 C 中传入和使用泛型 `void*` 参数。

   1. 注意：这也是所需的函数原型，正如 [`pthread_create()` 函数](https://www.man7.org/linux/man-pages/man3/pthread_create.3.html) 所要求的，用于传递给 `pthread_create()` `threadfunc()` 回调函数（在我的例子中为 \-\-\- ）。请参阅： [https](https://www.man7.org/linux/man-pages/man3/pthread_create.3.html) ://www.man7.org/linux/man-pages/man3/pthread_create.3.html。
2. \[效率\] 我让主线程休眠而不是浪费地旋转。

3. \[清晰\] 我添加了更详细的变量名称，例如 `BYTES_TO_ALLOCATE_EACH_LOOP` 和 `bytes_allocated` 。

4. \[清晰\]我改变了这个：

 *((volatile char *) alloca(128)) = 0;

   对此：

 volatile uint8_t * byte_buff =
        (volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP);
byte_buff[0] = 0;

**这是我修改后的测试程序，它和布鲁诺的完全一样，甚至有同样的结果：**

你可以 [在这里在线运行它](https://onlinegdb.com/rJddZ6aSP)，或者 [从我的 repo 下载它](https://github.com/ElectricRCAircraftGuy/eRCaGuy_hello_world/blob/master/c/onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c)。如果您选择从我的 repo 本地运行它，这里是我用于测试的构建和运行命令：

1. 作为 C 程序构建并运行它：

 mkdir -p bin && \
gcc -Wall -Werror -g3 -O3 -std=c11 -pthread -o bin/tmp \
onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \
time bin/tmp

2. 作为 C++ 程序构建并运行它：

 mkdir -p bin && \
g++ -Wall -Werror -g3 -O3 -std=c++17 -pthread -o bin/tmp \
onlinegdb--empirically_determine_max_thread_stack_size_GS_version.c && \
time bin/tmp

在线程堆栈大小约为 7.4 MB 的快速计算机上本地运行需要 < 0.5 秒。

这是程序：

// =============== Program for determining the default thread stack size =========

// Modified by Gabriel Staples, 26 Sept. 2020

// Originally by Bruno Haible // 24 Oct. 2009 // Source: https://lists.gnu.org/archive/html/bug-coreutils/2009-10/msg00262.html

#include #include #include #include #include #include // sleep

/// Thread function to repeatedly allocate memory within a thread, printing /// the total memory allocated each time, until the program crashes. The last /// value printed before the crash indicates how big a thread’s stack size is. /// /// Note: passing in a uint32_t as a void * type here is for practice, /// to learn how to pass in ANY type to a func by using a void * parameter. /// This is also the required function prototype, as required by the /// pthread_create() function, for the callback function (this function) /// passed to pthread_create(). See: /// https://www.man7.org/linux/man-pages/man3/pthread_create.3.html void* threadfunc(void* bytes_to_allocate_each_loop) { const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP = (uint32_t)bytes_to_allocate_each_loop;

uint32_t bytes_allocated = 0;
while (true)
{
    printf("bytes_allocated = %u\n", bytes_allocated);
    fflush(stdout);
    // NB: it appears that you don't necessarily need `volatile` here,
    // but you DO definitely need to actually use (ex: write to) the
    // memory allocated by `alloca()`, as we do below, or else the
    // `alloca()` call does seem to get optimized out on some systems,
    // making this whole program just run infinitely forever without
    // ever hitting the expected segmentation fault.
    volatile uint8_t * byte_buff =
            (volatile uint8_t *)alloca(BYTES_TO_ALLOCATE_EACH_LOOP);
    byte_buff[0] = 0;
    bytes_allocated += BYTES_TO_ALLOCATE_EACH_LOOP;
}

}

int main() { const uint32_t BYTES_TO_ALLOCATE_EACH_LOOP = 128;

pthread_t thread;
pthread_create(&thread, NULL, threadfunc,
               (void*)(&BYTES_TO_ALLOCATE_EACH_LOOP));
while (true)
{
    const unsigned int SLEEP_SEC = 10000;
    sleep(SLEEP_SEC);
}

return 0;

}

”`

示例输出（与 Bruno Haible 的原始程序的结果相同）：

 bytes_allocated = 7450240
bytes_allocated = 7450368
bytes_allocated = 7450496
bytes_allocated = 7450624
bytes_allocated = 7450752
bytes_allocated = 7450880
Segmentation fault (core dumped)

原文由 Gabriel Staples 发布，翻译遵循 CC BY-SA 4.0 许可协议