System.StackOverflowException

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

You did not properly implement the base case termination, which causes quicksort to never stop recursing into itself with sublists of length 0.

Change this:

if (low < high)
    pivot_loc = partition(input, low, high);
quicksort(input, low, pivot_loc - 1);
quicksort(input, pivot_loc + 1, high);

to this:

if (low < high) {
    pivot_loc = partition(input, low, high);
    quicksort(input, low, pivot_loc - 1);
    quicksort(input, pivot_loc + 1, high);
}

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.

When setting the price property, you invoke the setter, which invokes the setter which invokes the setter, etc..

Solution:

public int _price;
public int price
{
    get
    {
        return no * 5;
    }

    set
    {
        _price = value;
    }
}