如何检测到 StackOverflowException?

How is a StackOverflowException detected?

TL;TR
当我问这个问题时,我假设 WhosebugException 是 防止应用程序无限地 运行 的机制。这不是真的。
未检测到 WhosebugException
它在什么时候被抛出 堆栈没有分配更多内存的容量。

[原题:]

这是一个一般性问题,不同的编程语言可能会有不同的答案。
我不确定 C# 以外的语言如何处理堆栈溢出。

我今天正在经历异常,一直在思考如何检测到 WhosebugException。我相信不可能说f.e。如果堆栈是 1000 个调用深度,则抛出异常。因为也许在某些情况下正确的逻辑会那么深。

在我的程序中检测到无限循环背后的逻辑是什么?

WhosebugException class:
https://msdn.microsoft.com/de-de/library/system.Whosebugexception%28v=vs.110%29.aspx

WhosebugException class 文档中提到的交叉引用:
https://msdn.microsoft.com/de-de/library/system.reflection.emit.opcodes.localloc(v=vs.110).aspx

我刚给这个问题加了stack-overflow标签,描述说当调用堆栈消耗太多内存时抛出。这是否意味着调用堆栈是我程序当前执行位置的某种路径,如果它不能存储更多路径信息,那么会抛出异常?

堆栈溢出的问题不在于它们可能源于无限计算。问题是堆栈内存耗尽,这在当今的操作系统和语言中是一种有限的资源。

当程序试图访问超出分配给堆栈的内存部分时,会检测到这种情况。这导致异常。

堆栈只是在创建线程时分配的固定大小的内存块。还有一个 "stack pointer",一种跟踪当前使用了多少堆栈的方法。作为创建新堆栈帧的一部分(当调用方法、属性、构造函数等时),它会将堆栈指针向上移动新帧所需的数量。届时它将检查是否已将堆​​栈指针移过堆栈末尾,如果是,则抛出一个 SOE。

程序没有检测无限递归。无限递归(当运行时被迫为每次调用创建一个新的堆栈帧时)它只会导致执行如此多的方法调用以填满这个有限的 space。您可以轻松地用有限数量的嵌套方法调用来填充有限的 space,而这些嵌套方法调用恰好比堆栈消耗的 space 多。 (虽然这往往很难做到;它通常是由递归的方法引起的,但不是无限递归的,而是堆栈无法处理的足够深度。)

警告:这有一个很多 与幕后机制有关,包括 CLR 本身必须如何工作。只有开始学习汇编级编程,这才真正有意义。

在幕后,方法调用是通过将控制传递给另一个方法的站点来执行的。为了传递参数和 returns,它们被加载到堆栈上。为了知道如何return控制调用方法,CLR还必须实现一个调用栈,它被压入当一个方法被调用并从一个方法 returns 弹出时。此堆栈告诉 returning 方法 其中 到 return 控制到。

由于计算机只有有限的内存,有时调用堆栈会变得太大。因此,一个WhosebugException不是一个无限运行或无限递归程序的检测,是检测计算机无法再处理跟踪您的方法需要 return 的位置、必要的参数、return、变量或(更常见的)它们的组合所需的堆栈大小。无限递归时出现这个异常是因为逻辑不可避免地压栈。

为了回答您的问题,如果一个程序有意 具有会使堆栈过载的逻辑,那么是的,您会看到一个WhosebugException。但是,这通常是数千次到 数百万次 次调用,除非您创建了无限递归循环,否则很少有实际问题。

附录:我提到递归循环的原因是因为异常只会在你淹没堆栈时发生——这通常意味着你调用的方法最终会回调到相同的方法并增加调用堆栈。如果你有一些东西在逻辑上是无限的,但 不是 递归的,你通常不会看到 WhosebugException

堆栈溢出

我会让你轻松一点;但这实际上非常复杂...请注意,我将在这里概括很多。

您可能知道,大多数语言都使用堆栈来存储调用信息。另请参阅:https://msdn.microsoft.com/en-us/library/zkwh89ks.aspx 了解 cdecl 的工作原理。如果你调用一个方法,你将东西压入堆栈;如果你return,你从堆栈中弹出东西。

请注意,递归通常不是 'inlined'。 (注意:我在这里明确说 'recursion' 而不是 'tail recursion';后者的工作方式类似于 'goto',并且不会增加堆栈)。

检测堆栈溢出的最简单方法是检查您当前的堆栈深度(例如使用的字节数)——如果它到达边界,则给出错误。澄清一下 'boundary check':这些检查的完成方式通常是使用保护页;这意味着边界检查通常不会像 if-then-else 检查那样实现(尽管存在一些实现...)。

在大多数语言中,每个线程都有自己的堆栈。

正在检测无限循环

好吧,这是我好久没听到的问题了。 :-)

基本上检测所有死循环需要你解决Halting Problem. Which is by the way an undecidable problem。这绝对不是编译器干的。

这并不意味着你不能做任何分析;事实上,你可以做相当多的分析。但是,还要注意,有时您希望事情 运行 无限期地进行(例如 Web 服务器中的主循环)。

其他语言

也很有趣...函数式语言使用递归,因此它们基本上受堆栈约束。 (也就是说,函数式语言也倾向于使用尾递归,它的工作方式或多或少类似于 'goto',并且不会增加堆栈。)

然后是逻辑语言..现在,我不确定如何在其中永远循环 - 您可能会得到根本无法评估的东西(找不到解决方案)。 (不过,这可能取决于语言...)

屈服、异步、延续

您可能会想到一个有趣的概念叫做 continuations。我从微软那里听说,当 yield 首次实现时,真正的延续被认为是实现。 Continuations 基本上允许你 'save' 堆栈,在其他地方继续,然后 'restore' 稍后返回堆栈......(同样,细节比这复杂得多;这只是基本思想).

不幸的是,微软并没有采用这个想法(虽然我可以想象为什么),而是通过使用一个助手 class 实现了它。 C# 中的 Yield 和 async 通过添加临时 class 并在 class 中驻留所有局部变量来工作。如果您调用执行 'yield' 或 'async' 的方法,您实际上创建了一个助手 class(从您调用并压入堆栈的方法内),它被压入堆中。推送到堆上的 class 具有功能(例如,对于 yield 这是枚举实现)。完成此操作的方法是使用状态变量,该变量存储调用 MoveNext 时程序应继续执行的位置(例如某些状态 ID)。使用此 ID 的分支(交换机)负责其余的工作。请注意,此机制对堆栈本身的工作方式没有任何作用 'special';您可以使用 classes 和方法自己实现相同的功能(它只涉及更多输入:-))。

用手动堆栈解决堆栈溢出问题

我总是喜欢好的洪水填充。如果你做错了,一张图片会给你大量的递归调用......说,像这样:

public void FloodFill(int x, int y, int color)
{
    // Wait for the crash to happen...
    if (Valid(x,y))
    {
        SetPixel(x, y, color);
        FloodFill(x - 1, y, color);
        FloodFill(x + 1, y, color);
        FloodFill(x, y - 1, color);
        FloodFill(x, y + 1, color);
    }
}

这段代码没有任何问题。它完成了所有工作,但我们的堆栈妨碍了它。有一个手动堆栈解决了这个问题,即使实现基本相同:

public void FloodFill(int x, int y, int color)
{
    Stack<Tuple<int, int>> stack = new Stack<Tuple<int, int>>();
    stack.Push(new Tuple<int, int>(x, y));
    while (stack.Count > 0)
    {
        var current = stack.Pop();

        int x2 = current.Item1;
        int y2 = current.Item2;

        // "Recurse"
        if (Valid(x2, y2))
        {
            SetPixel(x2, y2, color);
            stack.Push(new Tuple<int, int>(x2-1, y2));
            stack.Push(new Tuple<int, int>(x2+1, y2));
            stack.Push(new Tuple<int, int>(x2, y2-1));
            stack.Push(new Tuple<int, int>(x2, y2+1));
        }
    }
}

这里已经有很多答案,其中很多都抓住了要点,但也有很多存在细微或较大的错误。与其试图从头开始解释整个事情,不如让我说几个要点。

I am not sure how languages other than C# handle a stack overflow.

您的问题是 "how is a stack overflow detected?" 您的问题是关于如何在 C# 或其他语言中检测到它?如果您对其他语言有疑问,我建议您创建一个新问题。

I think it is not possible to say (for example) if the stack is 1000 calls deep, then throw the exception. Because maybe in some cases the correct logic will be that deep.

绝对可以实现这样的堆栈溢出检测。在实践中,这不是它是如何完成的,但没有原则上的理由说明为什么系统不能那样设计。

What is the logic behind the detection of an infinite loop in my program?

你的意思是无限递归,而不是无限循环

我会在下面描述。

I just added the stack-overflow tag to this question, and the description says it is being thrown when the call stack consumes too much memory. Does that mean the call stack is some sort of path to the current executing position of my program and if it cannot store more path information, then the exception is thrown?

简短回答:是的。

更长的答案:调用堆栈有两个用途。

首先,表示激活信息。也就是说,局部变量的值和临时值的生命周期等于或短于方法的当前激活("call")。

其次,表示延续信息。也就是说,当我用完这个方法后,接下来我需要做什么? 注意堆栈 代表 "where did I come from?".堆栈代表我下一步要去哪里,碰巧通常当一个方法returns,你回到你从哪里来。

堆栈还存储非本地延续的信息——即异常处理。当方法抛出时,调用堆栈包含有助于运行时确定哪些代码(如果有)包含相关 catch 块的数据。该 catch 块随后成为方法的 continuation -- "what do I do next" --

现在,在我继续之前,我注意到调用堆栈是一种数据结构,用于两个目的,违反了单一责任原则。没有 要求 一个堆栈用于两个目的,事实上有一些异国情调的架构,其中有两个堆栈,一个用于激活帧,一个用于 return 地址(这是延续的具体化。)这样的体系结构不太容易受到 "stack smashing" 可能发生在 C 等语言中的攻击。

当您调用一个方法时,会在堆栈上分配内存以存储 return 地址——我接下来要做什么——以及激活帧——新方法的局部变量。 Windows 上的堆栈默认为固定大小,因此如果没有足够的空间,就会发生不好的事情。

In more detail, how does Windows do out of stack detection?

我在 1990 年代为 32 位 Windows 版本的 VBScript 和 JScript 编写了堆栈外检测逻辑; CLR 使用的技术与我使用的类似,但是如果您想了解特定于 CLR 的详细信息,则必须咨询 CLR 专家。

我们只考虑 32 位 Windows; 64 位 Windows 工作方式类似。

Windows 当然使用虚拟内存——如果您不了解虚拟内存的工作原理,现在是学习的好时机,然后再继续阅读。每个进程都有一个 32 位平面地址 space,一半保留给操作系统,另一半留给用户代码。默认情况下,每个线程都有一个保留的连续块,地址为 1 兆字节 space。 (注意:这是线程重量级的一个原因。当你一开始只有 20 亿字节时,100 万字节的连续内存很多。)

这里有一些关于连续地址 space 只是保留还是实际提交的微妙之处,但让我们掩盖这些。我将继续描述它在常规 Windows 程序中的工作原理,而不是深入探讨 CLR 的细节。

好的,假设我们有一百万字节的内存,分为 250 页,每页 4kb。但是程序在第一次启动时 运行 只需要几 kb 的堆栈。所以这就是它的工作原理。当前堆栈页面是一个非常好的提交页面;这只是正常的记忆。被标记为保护页的 beyond 页。而我们百万字节栈中的last页被标记为非常特殊的保护页

假设我们试图在我们良好的堆栈页面之外写入一个字节的堆栈内存。该页面受到保护,因此会发生页面错误。操作系统通过使该堆栈页面正常来处理故障,下一个页面成为新的保护页面。

但是,如果 last 保护页被击中——非常特殊的那个——然后 Windows 触发一个堆栈外异常,Windows 将保护页重置为 "if this page is hit again, terminate the process"。如果发生这种情况,则 Windows 会立即 终止进程 。没有例外。没有清理代码。没有对话框。如果您曾经看到 Windows 应用程序突然完全消失,可能是有人在 时间点击了堆栈末尾的保护页面。

好的,现在我们了解了这些机制——再次强调,我在这里掩盖了许多细节——你可能会看到如何编写产生堆栈外异常的代码。礼貌的方式——这是我在 VBScript 和 JScript 中所做的——是在堆栈上执行虚拟内存查询并询问最终保护页在哪里。然后定期查看当前堆栈指针,如果它在几页之内,只需创建一个 VBScript 错误或立即抛出一个 JavaScript 异常,而不是让操作系统为您做这件事。

如果你不想自己做那个探测,那么你可以处理第一次机会操作系统给你的异常,当最后的保护页面被命中时,转这会导致 C# 理解的堆栈溢出异常,并且 非常小心 不要再次访问保护页面。

大部分子问题都得到了充分的回答。我想澄清关于检测堆栈溢出情况的部分,希望以一种比 Eric Lippert 的回答更容易理解的方式(当然,这是正确的,但不必要地令人费解。)相反,我将让我的回答令人费解以不同的方式,通过提及不是一种,而是两种不同的方法。

有两种方法可以检测堆栈溢出:使用代码或借助硬件。

在 PC 运行 16 位 real 时代,使用代码 进行堆栈溢出检测模式和硬件是懦弱的。它不再被使用,但值得一提。在这种情况下,我们指定一个编译器开关,要求编译器在我们编写的每个函数的开头发出一段特殊的隐藏堆栈检查代码。这段代码只是简单地读取堆栈指针寄存器的值,并检查它是否离堆栈末尾太近;如果是这样,它会停止我们的程序。 x86 架构上的堆栈向下增加,因此如果地址范围 0x80000 到 0x90000 已指定为我们程序的堆栈,则堆栈指针最初指向 0x90000,并且随着您不断调用嵌套函数,它会向下指向 0x80000。因此,如果堆栈检查代码发现堆栈指针太接近 0x80000(例如,等于或低于 0x80010),它就会停止。

所有这一切的缺点是 a) 增加了我们进行的每个函数调用的开销,以及 b) 在调用未使用该特殊编译器开关编译的外部代码期间无法检测到堆栈溢出,以及因此不执行任何堆栈溢出检查。在那些日子里,Whosebug 异常是闻所未闻的奢侈品:您的程序要么以非常简洁(几乎可以说是 粗鲁)的错误消息终止,要么会有系统崩溃,需要重新启动。

借助硬件进行堆栈溢出检测 基本上将工作委托给 CPU。现代 CPU 有一个精心设计的系统,可以将内存细分为页面(通常每页 4KB 长)并对每个页面执行各种技巧,包括自动中断的能力(在某些体系结构中称为 'trap')当特定页面被访问时发出。因此,操作系统将 CPU 配置为如果您尝试访问低于分配的最小值的堆栈内存地址,则会发出中断。当该中断发生时,它会被您的语言的运行时(在 C# 的情况下为 .Net 运行时)接收,并被转换为 Whosebug 异常。

这样做的好处是完全没有额外开销。 CPU 一直在执行与页面管理相关的开销,但这无论如何都会得到报酬,因为它是虚拟内存工作所必需的,以及保护内存地址等各种其他事情 space 来自其他进程的一个进程,等等