none
How to survive StackOverflowException? RRS feed

  • Question

  • I've faced a problem, that seems hard to overcome. I'm working on genetic programming framework written in F#. It generates random program abstract syntax trees, and compiles them to dynamic functions. Then it runs them on some input, and compares by running time and correctness.

    The problem is that some of generated programs may contain infinite recursion that leads to StackOverflowException during dynamic method execution. In that case CLR 2.0+ terminates my program. I've tried the following:

    1. try ... catch ... - doesn't help, since in CLR 2.0 StackOverflowException thrown by runtime is non-catchable.
    2. running in background thread (e.g. thread with IsBackground == true) - doesn't help either. CLR terminates whole process.
    3. running the code in a separate AppDomain like described here: http://thevalerios.net/matt/2008/06/run-anonymous-methods-in-another-appdomain/ This failed with FatalExecutionEngineError: "The runtime has encountered a fatal error. The address of the error was at 0x6bd014cb, on thread 0x125c. The error code is 0xc0000005. This error may be a bug in the CLR or in the unsafe or non-verifiable portions of user code. Common sources of this bug include user marshaling errors for COM-interop or PInvoke, which may corrupt the stack." Which is probably caused by a bug in CLR (4.5 x64 in Windows 8 CP) or some problem with passing F# delegates or dynamic methods through AppDomain boundaries.

    I see two not easy ways to avoid total crash: spawn separate process for each function run (bad, requires AST serialization), check stack size before call inside generated programs, and throw own exception (bad, complicates program generation, negatively impacts performance).

    So the question is, is there any simpler way to survive StackOverflowException?

    Monday, May 28, 2012 12:39 PM

Answers

  • I've avoided StackOverflowException by using RuntimeHelpers.EnsureSufficientExecutionStack in generated programs before every call. I'll set it to run for a while since that seems that this call does not guarantee, that StackOverflowException will not occur, but it is tolerable if it would occur rarely.
    • Marked as answer by lostmsu Wednesday, May 30, 2012 10:50 AM
    Wednesday, May 30, 2012 10:50 AM

All replies

  • In terms of algorithms that you are using to solve your problem, the stack is just that:  a stack.  You can opt not to use the thread's stack to solve your problem and instead use a different stack.

    Recursion implemented in code is only good for small amounts of recursion because it uses the thread's processing stack, which is limited in address space.  

    For large stack requirements, use a stack allocated on the heap or on disk, and code for a loop instead of recursion.

    If you have INFINITE recursion, that will be an error regardless.  You will just run out of memory instead of stack space.  You should probably prevent that another way, such as by marking visited nodes to prevent revisiting, or something like that (hard to say without knowing your specific application.)


    • Edited by Wyck Monday, May 28, 2012 1:47 PM
    Monday, May 28, 2012 1:47 PM
  • Implementing stack on heap does not seems to be a good option. This would consume lots of performance, and requires significant amount of code to be written. In that sense spawning a new process seems to be simpler and more efficient (serialization-deserialization 2 times to pass input and receive output versus boxing, and unboxing data on every function cal).

    I'm still thinking of AppDomain hack, but have no idea on how to debug FatalExecutionEngineError.

    Infinite recursion is already handled by terminating execution after some time.

    Monday, May 28, 2012 2:03 PM
  • If you are generating random programs then the only solution I would trust is to have the code run in its own process.  A process is the best mechanism for isolation.  If they're going to be running out of stack space, this is the only mechanism I would trust.
    Monday, May 28, 2012 2:24 PM
  • I've implemented AppDomain and process isolation. The later works, but extremely slowly (as expected). The first one does not help against StackOverflowException. That's extremely sad. Does that mean, that running the code in other AppDomain does not save my program from crash in case of 3rd party component crash, or I'm just missing something?
    Wednesday, May 30, 2012 8:55 AM
  • I've avoided StackOverflowException by using RuntimeHelpers.EnsureSufficientExecutionStack in generated programs before every call. I'll set it to run for a while since that seems that this call does not guarantee, that StackOverflowException will not occur, but it is tolerable if it would occur rarely.
    • Marked as answer by lostmsu Wednesday, May 30, 2012 10:50 AM
    Wednesday, May 30, 2012 10:50 AM