How is a StackOverflowException detected?

问题:

TL;TR
When I asked the question I assumed a StackOverflowException is a mechanism to prevent applications to run infinitely. This is not true.
A StackOverflowException is not being detected.
It is thrown when the stack does not have the capacity to allocate more memory.

[Original question:]

This is a general question, which may has different answers per programming language.
I am unsure how languages other than C# process a stack overflow.

I was going through exceptions today and kept thinking about how a StackOverflowException can be detected. I believe it is not possible to say f.e. 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?

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

Cross reference mentioned in the StackOverflowException class documentation:
https://msdn.microsoft.com/de-de/library/system.reflection.emit.opcodes.localloc(v=vs.110).aspx

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?

回答1:

Stack overflows

I'll make it easy for you; but this is actually quite complex... Note that I will generalize quite a bit here.

As you might know, most languages use the stack for storing call information. See also: https://msdn.microsoft.com/en-us/library/zkwh89ks.aspx for how cdecl works. If you call a method, you push stuff on the stack; if you return, you pop stuff from the stack.

Note that recursion isn't normally 'inlined'. (Note: I explicitly say 'recursion' here and not 'tail recursion'; the latter works like a 'goto' and doesn't grow the stack).

The easiest way to detect a stack overflow is to check your current stack depth (e.g. bytes used) - and if it hits a boundary, give an error. To clarify about this 'boundary check': the way these checks are done is normally by using guard pages; this means boundary checks aren't normally implemented as if-then-else checks (although some implementations exist...).

In most languages, each thread has its own stack.

Detecting infinite loops

Well now, here's a question I haven't heard for a while. :-)

Basically detecting all infinite loops requires you to solve the Halting Problem. Which is by the way an undecidable problem. This is definitely not done by compilers.

This doesn't mean you can't do any analysis; in fact, you can do quite a bit of analysis. However, also note that sometimes you want things to run indefinitely (such as the main loop in a web server).

Other languages

Also interesting... Functional languages use recursion, so they are basically bound by the stack. (That said, functional languages also tend to use tail recursion, which works more or less like a 'goto' and don't grow the stack.)

And then there's Logical languages.. well now, I'm not sure how to loop forever in that - you'll probably end up with something that won't evaluate at all (no solution can be found). (Though, this probably depends on the language... )

Yielding, async, continuations

An interesting concept is you might think of is called continuations. I've heard from Microsoft that when yield was first implemented, real continuations were considered as implementation. Continuations basically allow you to 'save' the stack, continue somewhere else and 'restore' the stack back at a later point... (Again, the details are much more complicated than this; this is just the basic idea).

Unfortunately Microsoft didn't go for this idea (although I can imagine why), but implemented it by using a helper class. Yield and async in C# work by adding a temporary class and interning all the local variables within the class. If you call a method that does a 'yield' or 'async', you actually create a helper class (from within the method you call and push on the stack) that's pushed on the heap. The class that's pushed on the heap has the functionality (e.g. for yield this is the enumeration implementation). The way this is done is by using a state variable, which stores the location (e.g. some state id) where the program should continue when MoveNext is called. A branch (switch) using this ID takes care of the rest. Note that this mechanism does nothing 'special' with the way the stack works itself; you can implement the same by yourself using classes and methods (it just involves more typing :-)).

Solving stack overflows with a manual stack

I always like a good flood fill. A picture will give you a hell of a lot of recursion calls if you do this wrong... say, like this:

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);
    }
}

There's nothing wrong with this code though. It does all the work, but our stack gets in the way. Having a manual stack solves this, even though the implementation is basically the same:

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));
        }
    }
}

回答2:

There are a number of answers here already, many of which get the gist across, and many of which have subtle or large errors. Rather than try to explain the whole thing from scratch, let me just hit a few high points.

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

Your question is "how is a stack overflow detected?" Is your question about how it is detected in C#, or in some other language? If you have a question about another language, I recommend creating a new question.

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.

It is absolutely possible to implement a stack overflow detection like that. In practice, this is not how it is done, but there is no in-principle reason why the system could not have been designed that way.

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

You mean an unbounded recursion, not an infinite loop.

I'll describe it below.

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?

Short answer: yes.

Longer answer: The call stack is used for two purposes.

First, to represent activation information. That is, the values of the local variables and temporary values whose lifetimes are equal to or shorter than the present activation ("call") of a method.

Second, to represent continuation information. That is, when I am done with this method, what do I need to do next? Note that the stack does not represent "where did I come from?". The stack represents where am I going next, and it just so happens that usually when a method returns, you go back to where you came from.

The stack also stores information for non-local continuations -- that is, exception handling. When a method throws, the call stack contains data that helps the runtime determine what code, if any, contains the relevant catch block. That catch block then becomes the continuation -- the "what do I do next" -- of the method.

Now, before I go on, I note that the call stack is a data structure that is being used for two purposes, violating the single responsibility principle. There is no requirement that there be one stack used for two purposes, and in fact there are some exotic architectures in which there are two stacks, one for activation frames and one for return addresses (which are the reification of continuation.) Such architectures are less vulnerable to "stack smashing" attacks that can occur in languages like C.

When you call a method, memory is allocated on the stack to store the return address -- what do I do next -- and the activation frame -- the locals of the new method. Stacks on Windows are by default of fixed size, so if there is not enough room, bad things happen.

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

I wrote the out-of-stack detection logic for 32 bit Windows versions of VBScript and JScript in the 1990s; the CLR uses similar techniques as I used, but if you want to know the CLR-specific details, you'll have to consult an expert on the CLR.

Let's consider just 32 bit Windows; 64 bit Windows works similarly.

Windows uses virtual memory of course -- if you do not understand how virtual memory works, now would be a good time to learn before you read on. Each process is given a 32 bit flat address space, half reserved for the operating system and half for the user code. Each thread is by default given a reserved contiguous block of one megabyte of address space. (Note: this is one reason why threads are heavyweight. A million bytes of contiguous memory is a lot when you only have two billion bytes in the first place.)

There are some subtleties here regarding whether that contiguous address space is merely reserved or actually committed, but let's gloss those over. I'll continue to describe how it works in a conventional Windows program rather than going into the CLR details.

OK, so we have lets say a million bytes of memory, divided into 250 pages of 4kb each. But the program when it first starts running is only going to need maybe a few kb of stack. So here's how it works. The current stack page is a perfectly good committed page; it's just normal memory. The page beyond that is marked as a guard page. And the last page in our million byte stack is marked as a very special guard page.

Suppose we try to write a byte of stack memory beyond our good stack page. That page is guarded, so a page fault occurs. The operating system handles the fault by making that stack page good, and the next page becomes the new guard page.

However, if the last guard page is hit -- the very special one -- then Windows triggers an out-of-stack exception, and Windows resets the guard page to mean "if this page is hit again, terminate the process". If that happens then Windows terminates the process immediately. No exception. No cleanup code. No dialog box. If you've ever seen a Windows app just suddenly disappear completely, probably what happened was someone hit the guard page at the end of the stack for the second time.

OK, so now that we understand the mechanisms -- and again, I am glossing over many details here -- you can probably see how to write code that makes out-of-stack exceptions. The polite way -- which is what I did in VBScript and JScript -- is to do a virtual memory query on the stack and ask where the final guard page is. Then periodically look at the current stack pointer, and if it is getting within a couple of pages, simply create a VBScript error or throw a JavaScript exception right then and there rather than letting the operating system do it for you.

If you don't want to do that probing yourself, then you can handle the first chance exception that the operating system gives you when the final guard page is hit, turn that into a stack overflow exception that C# understands, and be very careful to not hit the guard page a second time.

回答3:

The stack is simply a block of memory of a fixed size that is allocated when the thread is created. There is also a "stack pointer", a way of keeping track how much of the stack is currently being used. As a part of creating a new stack frame (when calling a method, property, constructor, etc.) it moves the stack pointer up by the amount that the new frame is going to need. At that time it will check if has moved the stack pointer past the end of the stack, and if so, throw a SOE.

The program does nothing to detect infinite recursion. Infinite recursion (when the runtime is forced to create a new stack frame for each invocation) it simply results in so many method calls being performed as to fill up this finite space. You can just as easily fill up that finite space with a finite number of nested method calls that just happen to consume more space than the stack has. (This tend to be rather hard to do though; it's usually caused by methods that are recursive, and not infinitely so, but of sufficient depth that the stack can't handle it.)

回答4:

WARNING: This has a lot to do with under the hood mechanics, including how the CLR itself has to work. This will only really make sense if you start to study assembly-level programming.

Under the hood, method calls are performed by passing control to the site of another method. In order to pass arguments and returns, these are loaded onto the stack. In order to know how to return control to the calling method, the CLR must also implement a call stack, which is pushed to when a method is called and popped from when a method returns. This stack tells the returning method where to return control to.

Since a computer only has a finite memory, there are times when the call stack gets too big. Thus, a StackOverflowException is not the detection of a infinitely running or infinitely recursive program, it is the detection that the computer can no longer handle the size of the stack required to keep track of where your methods need to return to, the necessary arguments, returns, variables, or (more commonly) a combination thereof. The fact that this exception occurs during infinite recursion is because the logic inevitably overwhelms the stack.

To answer your question, if a program intentionally has logic which would overload the stack then yes you will see a StackOverflowException. However, this is generally thousands up to millions of calls deep and rarely an actual concern unless you've created an infinitely recursive loop.

addendum: The reason I mention recursive loops is beause the exception will only happen if you overwhlem the stack - which generally means you're calling methods which eventually call back into the same method and grow the call stack. If you have something which is logically infinite, but not recursive, you generally won't see a StackOverflowException

回答5:

The problem with stack overflows is not that they might stem from an infinite computation. The problem is exhaustion of stack memory which is a finite resource in today's operating systems and languages.

This condition is detected when the program tries to access a portion of memory that is beyond what is allocated to the stack. This results in an exception.

回答6:

Most of the sub-questions have been sufficiently answered. I would like to clarify the part about the detection of the stack overflow condition, hopefully in a way which is easier to understand than Eric Lippert's answer (which is, correct, of course, but unnecessarily convoluted.) Instead, I will convolute my answer in a different way, by mentioning not one, but two different approaches.

There are two ways to detect stack overflow: either with code, or with the help of hardware.

Stack overflow detection using code was being used back in the days when PCs were running in 16-bit real mode and the hardware was wimpy. It is not used anymore, but it is worth mentioning. In this scenario, we specify a compiler switch asking the compiler to emit a special hidden piece of stack-checking code in the beginning of each function that we write. This code simply reads the value of the stack pointer register and checks to see if it is too close to the end of the stack; if so, it halts our program. The stack on the x86 architecture increases downwards, so if the address range 0x80000 to 0x90000 has been designated as our program's stack, then the stack pointer initially points at 0x90000, and as you keep invoking nested functions it goes down towards 0x80000. So, if the stack checking code sees that the stack pointer is too close to 0x80000, (say, at or below 0x80010,) then it halts.

All this has the disadvantage of a) adding overhead to every single function call that we make, and b) not being able to detect a stack overflow during calls to external code which was not compiled with that special compiler switch and therefore is not performing any stack overflow checking. Back in those days a StackOverflow exception was a luxury unheard of: your program would either terminate with a very laconic (one could almost say rude) error message, or there would be a system crash, requiring a reboot.

Stack overflow detection with the help of hardware basically delegates the job to the CPU. Modern CPUs have an elaborate system for subdividing memory into pages (usually 4KB long each) and doing various tricks with each page, including the ability to have an interrupt (in some architectures called a 'trap') automatically issued when a particular page gets accessed. So, the operating system configures the CPU in such a way that an interrupt will be issued if you attempt to access a stack memory address below the assigned minimum. When that interrupt occurs, it is received by the runtime of your language, (in C#'s case, the .Net runtime,) and it gets translated into a StackOverflow exception.

This has the benefit of having absolutely no extra overhead. There is an overhead associated with the page management that the CPU is performing all the time, but this gets paid anyway, as it is necessary for virtual memory to work, and for various other things like protecting the memory address space of one process from other processes, etc.