In the previous part we solved a problem using recursion. In this solution a method keeps calling itself. When a method calls a method, it has some administrative cost, it needs memory. For example, the CPU needs to know where to continue the execution of the program code after it returns from a method, so it needs to store the return address. Also, if the caller and callee method want to communicate, they need a shared memory, this is what they use to pass parameters and return values.
Execution Stack
The most common solution to provide the necessary memory for method calls is using a stack. The size of the stack is limited, however. The exact size depends on several factors – it can be set for a new thread, for example, but usually it is around 1-2Mb. To see what this size is enough for, let’s try it out through an example.
The limits of an Execution Stack
Let’s say that the problem we want to solve is to answer the question that how many times we need to add 1 to itself to get the value n. The solution of this problem cries for recursion:
- if n=0, then the solution is 0
- if n>0, it’s getting complicated, but it helps a lot that we know that the solution of n is greater by 1 than the solution of n-1. For example, f(10) = 1 + f(9).
Now that we have figured out how to solve a part of the problem and how we can get a smaller problem with a similar shape, we can write a recursive method:
static uint f(uint n)
{
if (n == 0)
return 0;
else
return 1 + f(n - 1);
}
Calling the method, it calculates the result for a given n:
Console.WriteLine(f(5000));
and the result is 5000. But when we want to calculate the result for 50000, what we get is:
Process is terminated due to StackOverflowException.
We can see that the stack is not big enough to support 50000 calls. My configuration provides enough space for ~37000 calls. It sounds a lot, but this example is very limited. It is a static method, so no need to pass the “this” reference, which is the hidden first parameter of every non static method. Also, it has only one parameter, and the jitter compiles a code where this single parameter is passed through a register instead of the stack. And no explicit local variables. Still the CLR allocates 64 bytes on the stack just to run this simple method.
push ebp ; 4 bytes mov ebp,esp push edi ; 4 bytes push esi ; 4 bytes push ebx ; 4 bytes sub esp,40h ; 64 bytes ...
This 64 bytes doesn’t contain the saved registers and the return address. This simple method needs 64 + 16 bytes and the return address, 84 bytes altogether on a 32 bit system.
We can increase the length of a call chain if we allocate larger stack for a thread:
var thread = new Thread( _ => Console.WriteLine(f(50000)), 8000000); // ~ 8MB stack thread.Start(); thread.Join();
In this case the method can calculate the result.
Catch me if you can
Another problem with stack overflow is that we cannot catch the exception it generates. We cannot prevent this application to crash:
try
{
Console.WriteLine(f(300000));
}
catch
{
Console.WriteLine("ooops..");
}
Even if we try to catch every type of exceptions, this “every” doesn’t include StackOverflowException. It is a bad news. Let’s say that we are implementing a service application, and it’s API can accept a recursive data structure. If a client sends a huge recursive data block, the service will fill up the stack processing this input, and crashes. It will stop serving not only the client who sent the poisoning data, but all the other clients being served.
Ensure Sufficient Execution Stack
The example with the service application is not just random, I discovered a possible solution of this problem browsing the source code of the model binder of MVC4. This model binder was able to read recursive data – and it would not crash if someone sent a 100000 deep tree structure. The trick it used was provided by the RuntimeHelpers class, which had gotten a new method EnsureSufficientExecutionStack() with .NET 4.
This method does what its name says: it checks that the stack has enough space to support a method call. If not, it throws its own exception instead of StackOverflowException, so we can catch it:
static uint f(uint n)
{
if (n == 0)
{
return 0;
}
else
{
RuntimeHelpers.EnsureSufficientExecutionStack();
return 1 + f(n - 1);
}
}
static void Main(string[] args)
{
try
{
Console.WriteLine(f(300000));
}
catch (InsufficientExecutionStackException)
{
Console.WriteLine("Out of stack space");
}
catch
{
Console.WriteLine("ooops..");
}
}
Now the program will not crash and we have a chance to handle the problem in a more sophisticated way.
viktorpeller.com 