首页 文章

通过在堆上分配堆栈部分来避免堆栈溢出？

提问于
浏览 次
2

是否有一种语言可以在超出原始堆栈空间时启用在堆上分配新堆栈空间的机制？

我记得在我的大学做了一个实验室，我们在C中使用内联汇编来实现基于堆的可扩展堆栈，所以我知道它原则上应该是可行的 .

我知道在开发应用程序时获取堆栈溢出错误可能很有用，因为它会在不使系统占用大量内存并开始交换的情况下快速终止疯狂的无限递归 .

但是，当你有一个经过良好测试的完成的应用程序要部署并希望它尽可能健壮时（比如它是一个在桌面计算机上运行的非常关键的程序），那么知道它不会很好在堆栈更有限的一些其他系统上可悲地失败，其中一些对象占用更多空间，或者如果程序面临一个非常特殊的情况需要比测试中更多的堆栈内存 .

我认为正是由于这些陷阱，通常在 生产环境 代码中避免了递归 . 但是如果我们在 生产环境 代码中有一个自动堆栈扩展机制，那么我们就能够使用递归编写更优雅的程序，因为知道它不会意外地出现段错误，而系统有16 GB的堆内存可供使用...

c recursion stack stack-overflow heap-memory

5 回答

  • 2

    它有先例 .

    • GHC（Haskell编译器）的运行时使用堆而不是堆栈 . 堆栈仅在您调用外部代码时使用 .

    • Google的Go实现使用goroutines的分段堆栈，根据需要扩大堆栈 .

    • Mozilla的Rust过去常常使用分段堆栈，虽然它确定它引起的问题多于解决的问题（参见[rust-dev] Abandoning segmented stacks in Rust） .

    • 如果内存服务，一些Scheme实现将堆栈帧放在堆上，然后垃圾收集帧就像其他对象一样 .

    在命令式语言的传统编程风格中，大多数代码都会避免递归地调用自身 . 堆栈溢出在野外很少见，并且它们通常由草率编程或恶意输入触发 - 尤其是递归下降解析器等，这就是为什么一些解析器在嵌套超过阈值时拒绝代码的原因 .

    避免 生产环境 代码中堆栈溢出的传统建议：

    • 不要写递归代码 . （示例：重写搜索算法以使用显式堆栈 . ）

    • 如果您确实编写了递归代码，请证明递归是有界的 . （例如：搜索 balancer 树的大小取决于树大小的对数 . ）

    • 如果您无法证明它是无界的，请添加一个绑定 . （示例：为解析器支持的嵌套量添加限制 . ）

    回复于
  • 2

    我不相信你会找到一种强制要求的语言 . 但是特定的实现可以提供这样的机制，并且取决于操作系统，很可能运行时环境根据需要自动扩大堆栈 .

    回复于
  • 0

    根据 gcc 的文档， gcc 可以生成执行此操作的代码，如果使用 -fsplit_stack 选项进行编译：

    -fsplit-stack
     Generate code to automatically split the stack before it overflows.
     The resulting program has a discontiguous stack which can only
     overflow if the program is unable to allocate any more memory.
     This is most useful when running threaded programs, as it is no
     longer necessary to calculate a good stack size to use for each
     thread.  This is currently only implemented for the i386 and
     x86_64 backends running GNU/Linux.

     When code compiled with -fsplit-stack calls code compiled
     without -fsplit-stack, there may not be much stack space
     available for the latter code to run.  If compiling all code,
     including library code, with -fsplit-stack is not an option,
     then the linker can fix up these calls so that the code compiled
     without -fsplit-stack always has a large stack.  Support for
     this is implemented in the gold linker in GNU binutils release 2.21
     and later.

    llvm 代码生成框架为分段堆栈提供支持，这些堆栈在 go 语言中使用，最初用于Mozilla的 rust （尽管它们因为执行开销对于"high-performance language"来说太高而被删除了 . （参见this mailing list thread）

    尽管 rust -team的反对意见，但分段堆栈的速度却出乎意料地快，尽管堆栈抖动问题会影响特定程序 . （有些 Go 程序也受此问题的影响 . ）

    Henry Baker在其1994年的论文_2859085中提出了以相对有效的方式堆栈分配堆栈段的另一种机制，并成为Chicken Scheme的运行时的基础，这是一个主要编译R5RS的方案实现 .

    回复于
  • 0

    在 生产环境 代码中肯定不会避免递归 - 它只是在适当的地方和时间使用 .

    如果你担心它，正确的答案可能不仅仅是切换到向量中的手动维护堆栈或其他任何东西 - 尽管你可以这样做 - 但重新组织逻辑 . 例如，我正在研究的编译器用工作列表驱动的进程替换了一个深度递归进程，因为不需要按处理顺序维护严格的嵌套，只是为了确保变量我们在使用之前计算了依赖性 .

    回复于
  • 4

    如果链接到线程库（例如C中的pthreads），则每个线程都有一个单独的堆栈 . 这些堆栈以这样或那样的方式分配，最终（在UNIX环境中）使用 brk 或匿名 mmap . 这些可能会或可能不会在途中使用堆 .

    我注意到以上所有答案都是指单独的堆栈;没有明确说“在堆上”（在C意义上） . 我认为海报只是意味着“来自动态分配的内存”，而不是调用处理器堆栈 .

    回复于

相关问题