The Case of the Failed Demo – StackOverflowException on X64

a while ago, i was explaining runtime mechanisms like the stack and the heap to some folks. (as an aside, i'm writing a debugger course on "advanced .net debugging with windbg with sos", which is an ongoing project. time will tell when it's ready to hit the streets.) since the context was functional programming where recursion is a typical substitute (or fuel, if you will) for loops , an obvious topic for discussion is the possibility to hit a stack overflow. armed with my favorite editor, notepad.exe, and the c# command-line compiler, i quickly entered the following sample to show "looping with recursion" and how disaster can strike:

the module-based condition in there is to avoid excessive slowdowns due to console.writeline use, which is rather slow due to the way the win32 console output system works. to my initial surprise, the overflow didn't come anywhere in sight and the application kept running happily:

i rather expected something along the following lines:

so, what's going on here? though i realized pretty quickly what the root cause is of this unexpected good behavior, i'll walk the reader through the thought process used to "debug" the application's code.

the first thing to check is that we really are making a recursive call in our rec method. obviously, ildasm is the way to go to inspect that kind of stuff, so here's the output which we did expect.

in fact, the statement made above — "which we did expect" — is debatable. couldn't the compiler just turn the call into a jump right to the start of the method after messing around a bit with the local argument slot that holds argument value n? that way we wouldn't have to make a call and the code would still work as expected. essentially what we're saying here is that the compiler could have turned the recursive call into a loop construct. and indeed, some compilers do exactly that. for example, consider the following f# sample:

notice the explicit indication of the recursive nature of a function by means of the "rec" keyword. after compiling this piece of code using fsc.exe, the following code is shown in reflector (decompiling to c# syntax) for the rec function:

the mechanics of the printf call are irrelevant. what matters is the code that's executed after the n++ statement, which isn't a recursive call to rec itself. instead, the compiler has figured out a loop can be used. hence, no stackoverflowexception will result.

back to the c# sample though. what did protect the code from overflowing the stack? let's have some further investigations, but first ... some background.

one optimization that can be carried out for recursive functions is to spot tail calls and optimize them away into looping - or at a lower level, jumps - constructs. a tail call is basically a call after which the current stack frame is no longer needed upon return from the call. for example, our simple sample can benefit from tail call optimization since the rec method doesn't really do anything anymore after returning from the recursive rec call:

this kind of optimization — as carried out by f# in the sample shown earlier — can't always take place. for example, consider the following definition of a factorial method:

the above has quite a few issues such as the inability to deal with negative values and obviously the arithmetic overflow disaster that will strike when the supplied "n" parameter is too large for the resulting factorial to fit in an int32. the biginteger type introduced in .net 4 (and not in .net 3.5 as originally planned) would be a better fit for this kind of computation, but let's ignore this fact for now.

a more relevant issue in the context of our discussion is the code's use of recursion where a regular loop would suffice, but now i'm making a value judgment of imperative control flow constructs versus a more functional style of using recursion. that's true nonetheless is the fact that the code above is not immediately amenable for tail call optimization. to see why this is, rewrite the code as follows:

see what's going on? after returning from the recursive call to fac, we still need to have access to the value of "n" in the current call frame. as a result, we can't reuse the current stack frame when making the recursive call. implementing the above in f# (just for the sake of it) and decompiling it, shows the following code:

the culprit keeping us from employing tail call optimization is the multiplication instruction needed after the return from the recursive call to fac. (note: the second operand to the multiplication was pushed onto the evaluation stack in il_0005; in fact il_0006 could also have been a dup instruction.) c# code will be slightly different but achieve the same computation (luckily!).

sometimes it's possible to make a function amenable for tail call optimization by carrying out a manual rewrite. in the case of the factorial method, we can employ the following trick:

here, we're not only decrementing n in every recursive call, we're also keeping the running multiplication at the same time. in my post jumping the trampoline in c# - stack-friendly recursion , i explained this principle in the "don't stand on my tail!" section. the f# equivalent of the code, shown below, results in tail call optimization once more:

the compilation result is shown below:

you can clearly see the reuse of local argument slots.

all of this doesn't yet explain why the original c# code is just working fine though our look at the generated il code in the second section of this post did reveal the call instruction to really be there. one more party is involved in getting our much-beloved piece of c# code to run on the bare metal of the machine: the jit compiler.

in fact, as soon as i saw the demo not working as intended, the mental click was made to go and check this possibility. why? well, the c# compiler doesn't optimize tail calls into loops, nor does it emit tail.call instructions . the one and only remaining party is the jit compiler. and indeed, since i'm running on x64 and am using the command-line compiler, the jit compiler is more aggressive about performing tail call optimizations.

let's explain a few things about the previous paragraph. first of all, why does the use of the command-line compiler matter? won't the same result pop up if i used a console application project in visual studio? not quite, if you're using visual studio 2010 that is. one the decisions made in the last release is to mark executables il assemblies (managed .exe files) as 32-bit only. that doesn't mean the image contains 32-bit instructions (in fact, the c# compiler never emits raw assembler); all it does it tell the jit to only emit 32-bit assembler at runtime, hence resulting in a wow64 process on 64-bit windows. the reasons for this are explained in the rick byer's blog post on the subject . in our case, we're running the c# compiler without the /platform:x86 flag - which now is passed by the default settings of a visual studio 2010 executable (not library!) project - therefore resulting in an "anycpu" assembly. the corflags.exe tool can be used to verify this claim:

in visual studio 2010, a new console application project will have the 32-bit only flag set by default. again, reasons for this decision are brought up in rick's post on the subject.

indeed, when running the 32-bit only assembly, a stackoverflowexception results. an alternative way to tweak the flags of a managed assembly is by using corflags.exe itself, as shown below:

it turns out when the 64-bit jit is involved, i.e. when the anycpu platform target is set - the default on the csc.exe compiler - tail call optimization is carried out for our piece of code. a whole bunch of conditions under which tail calls can be optimized by the various jit flavors can be found on david broman's blog . grant richins has been blogging about improvements made in .net 4 (which don't really apply to our particular sample). one important change in .net 4 is the fact the 64-bit jit now honors the "tail." prefix on call instructions, which is essential to the success of functional style languages like f# (indeed, f#'s compiler actually has a tailcalls flags, which is on by default due to the language's nature).

in order to show the reader the generated x64 code for our recursive rec method definition, we'll switch gears and open up windbg, leveraging the sos debugger extension. obviously, this requires one to install the debugging tools for windows . also, notice the section's title to apply to x64. for x86 users, the same experiment can be carried out, revealing the x86 instructions generated without the tail call optimization, hence explaining the overflow observed on 32-bit executions.

loading the ovf.exe sample (making sure the 32-bit only flag is set!) under the windbg debugger - using windbg.exe ovf.exe - brings us to the first loader breakpoint as shown below. in order to load the son of strike (sos) debugger extension, set a module load breakpoint for clrjit.dll (which puts us in a convenient spot where the clr has been sufficiently loaded to use sos successfully). when that breakpoint hits, the extension can be loaded using .loadby sos clr:

next, we need to set a breakpoint on the rec method. in my case, the assembly's file name is ovf.exe, the class is program and the method is rec, requiring me to enter the following commands:

the !bpmd extension command is used to set a breakpoint based on a methoddesc - a structure used by the clr to describe a method. since the method hasn't been jit compiled yet, and hence no physical address for the executable code is available yet, a pending breakpoint is added. now we let go the debugger and end up hitting the breakpoint which got automatically set when the jit compiler took care of compiling the method (since it came "in sight" for execution, i.e. because of main's call into it). using the !u (for unassemble) command, we can now see the generated code:

notice the presence of code like initializestdouterror which is the result from inlining of the console.writeline method's code. what's going on here with regards to the tail call behavior is the replacement of a call instruction with a jump simply to the beginning of the generated code. the rest of the code can be deciphered with a bit of x86/x64 knowledge. for one thing, you can recognize the 1024 value (used for our modulo arithmetic) in 3ff which is 1023. the module check stretches over a few instructions that basically use a mask over the value to see whether any of the low bits is non-zero. if so, the value is not dividable by 1024; otherwise, it is. based on this test (whose value gets stored in eax), a jump is made or not, either going through the path of calling console.writeline or not.

in the x86 setting, we'll see different code. to show this, let's use a console application in visual studio 2010, whose default platform target is - as mentioned earlier - 32-bit. in order to load sos from inside the immediate window, enable the native debugger through the project settings:

using similar motions as before, we can load the sos extension upon hitting a breakpoint. instead of using !bpmd , we can use !name2ee to resolve the jitted code address for the given symbol, in this case, the program.rec method:

inspecting the generated code, one will encounter the following call instruction to the same method. this is the regular recursive call without any tail call optimization carried out. obviously, this will cause a stackoverflowexception to occur. also, notice from the output below that the console.writeline method call didn't get inlined in this particular x86 case.

as referred to before , the il instruction set has a tail. prefix for call instructions. before .net 4, this was merely a hint to the jit compiler. for x86, it was (and still is) a request of the il generator to the jit compiler to perform a tail call. for x64, prior to clr 4.0, this request was not always granted. for our x86 case, we can have a go at inserting the tail. prefix for the recursive call in the code generated by the c# compiler (which doesn't emit this instruction by itself as explained before). using ildasm's /out parameter, you can export the ovf.exe il code to a text file. notice the cor flags have been set to "32-bit required" using either the x86 platform target flag on csc.exe or by using corflags /32bit+:

now tweak the code of rec as shown below. after a tail call instruction, no further code should execute other than a ret. if this rule isn't obeyed, the clr will throw an exception signaling an invalid program. hence we remove the nop instruction that resulted from a non-optimized build (debug build or csc.exe use without /o+ flag). to turn the call into a tail call one, we add the "tail." prefix. don't forget the space after the dot though:

the session of roundtripping through ildasm and ilasm with the manual tweak in notepad shown above is shown here:

with this change in place, the ovf.exe will keep on running without overflowing the stack. looking at the generated code through the debugger, one would see a jmp instruction instead of a call, explaining the fixed behavior.

tail calls are the bread and butter of iterative programs written in a functional style. as such, the clr has evolved to support tail call optimization in the jit when the tail. prefix is present, e.g. as emitted by the f# compiler when needed (though the il code itself may be turned into a loop by the compiler itself). one thing to know is that on x64, the jit is more aggressive about detecting and carrying out tail recursive calls (since it has a good value proposition with regards to "runtime intelligence cost" versus "speed-up factor").