在C90中实现一个无溢出系统堆栈

Question

我刚刚了解到Google Go默认使每个线程的堆栈大小减小，如果溢出会链接到新的堆栈(请参见这里的第16页)。我在想如何用C实现最佳方法。

我必须说我不是C专家，所以可能有更好的方法来检测C中的堆栈溢出，但考虑到我的无知，以下是我认为我会实现的方式：

我首先想到的是，每次我们有一个全新的堆栈，我们会得到一个堆栈变量的地址，然后大致得到起始堆栈地址。然后，我们需要能够检索线程具有多少堆栈空间。如果线程不是主线程，则可能可以实现此操作，但我不知道如何在C中获取此信息。

然后，我们需要检查（每个函数调用可能都需要）已使用了多少堆栈，通过检索当前堆栈变量地址。如果检测到可能的堆栈溢出，我们需要有一种方法创建一个新的堆栈并链接到上一个堆栈。我认为在C语言中唯一可行的方法是创建一个新线程来执行我们想要的函数，并锁定当前线程直到该函数返回其结果。

那么，是否有更清晰/更好的方法来实现这一点？

- Waneck

---

我不确定我喜欢你的反溢出态度。你确定你没有来到错误的网站吗 ;) - Chris Eberle

请注意，分割堆栈并没有解决溢出问题。无论使用什么方法来分配新的堆栈片段，例如malloc，都有可能失败，而应用程序也无法检测和处理这种情况。 - R.. GitHub STOP HELPING ICE

Answer 1

请查看GCC的分割栈功能。我相信最初是为了支持Go而实现的。它几乎就像你所建议的那样工作。

编辑：下面的评论讨论了另一个可以对激活记录进行堆分配的系统。

- Ira Baxter

---

我知道这个链接的原因是我构建了一种非C语言（PARLANSE），它实现了堆分配的堆栈片段，所以我长期以来一直对这样的方案感兴趣。PARLANSE为每个函数调用分配一个新片段，价格大约与GCC方法相同。根据我们的测量，开销约为3-5％，但我们的语言和编码风格倾向于鼓励大型函数（一个好的C编译器也会通过内联所有小函数来做到这一点）。请参见www.semanticdesigns.com/Products/PARLANSE。 - Ira Baxter

不，PARLANSE比那还要疯狂得多。它被设计成允许数百万个计算粒子并行运行，这是您无法使用“大堆栈模型”实现的（请参见https://dev59.com/wXNA5IYBdhLWcg3wUL5Y#1053159）。如果每个粒子都可以分叉并行子工作，并且分叉的粒子可以在资源上交错，则需要执行此操作。因此，PARLANSE将1个操作系统线程多路复用到潜在的数百万个运行的“粒子”上。实际上，它试图保持粒子计数远大于线程数，这足以发挥作用。 - Ira Baxter

你从哪里得到足够的工作来证明这一点呢？我们使用PARLANSE来处理完整的源代码系统（请参见www.semanticdesigns.com/Products/DMS/DMSToolkit.html），这需要巨大的数据结构和大量的分析。对于这个任务，最好采用并行处理。PARLANSE并不完美，但它比我们看到的任何其他东西都要好 :-{ - Ira Baxter

开销就是速度差异。内存开销大约为25％，因为我们使用了二进制幂级别的伙伴系统大小块。每个函数都知道它（及其并行子粒度）需要多少堆栈空间，并请求下一个二进制幂级别的大小。真正的技巧在于拥有许多可用的块，这些块不需要锁定来分配 :-} 我们使用大量的线程本地存储来使其更加高效。 - Ira Baxter

在实践中，这对我们的意义是，我们可以在巨大的结构（主要是AST或图上的跨度树）上编写递归算法，而不会耗尽堆栈空间或担心堆栈空间不足。我们已经进行了数百万次递归！虽然您可能会使用一个线程来执行此操作，但请想象它发生在许多随机颗粒之一上，而您事先不知道哪个颗粒。您几乎必须将堆栈分配为小片段。 - Ira Baxter

Answer 2

你可以这样做 - 我相信现代gcc甚至可能有一个选项可以实现 - 但它大大增加了函数调用的成本，而且几乎没有实际的好处。特别是在具有64位寻址的现代系统上，每个线程都有足够的地址空间，可以拥有自己的堆栈，并远离其他线程的堆栈。如果您发现自己使用的递归调用超过对数级别，则算法肯定存在问题...

- R.. GitHub STOP HELPING ICE

---

它并不会大大增加函数调用的成本。它只比CPU内置的标准调用多几条指令，而且大多数有趣的函数都有数百条指令长。（如果编译器擅长内联，则较短的函数往往会消失）。至少这是我的个人经验；请参见我回答中的评论。 - Ira Baxter

对于一个 Web 服务器，你可以为每个线程准备一个小堆栈。只需使用 pthread_attr_setstacksize(&attr, getconf(_SC_THREAD_STACK_MIN));，并且不要编写愚蠢的递归代码。 - R.. GitHub STOP HELPING ICE

关于函数大小，良好分解的代码使用小而简单的函数，并且通过共享库和带有访问器函数的不透明类型，编译器无法优化调用。即使没有额外的丑陋浪费，如分割堆栈，我已经遇到了一些情况，其中gcc的调用开销（例如堆栈对齐和在不需要的情况下保存无用寄存器）正在产生函数总运行时间的10-30％。这将很容易跳到60-90％，如果使用分割堆栈。 - R.. GitHub STOP HELPING ICE

还要注意，对于良好的代码，编译器可以轻松执行静态分析，以确定每个线程启动函数所需的确切堆栈大小。只有使用递归或任意回调函数的代码才无法在编译时建立堆栈空间的界限。 - R.. GitHub STOP HELPING ICE

@R. 这在分离编译或动态加载器中不起作用。 - Ira Baxter