5

I've run into a situation where, according to a minidump, certain files are causing a stack overflow in a recursive-descent parser. Unfortunately I can't get my hands on an example of a file that does this in order to reproduce the issue (the client has confidentiality concerns), which leaves me a bit hamstrung on diagnosing the real problem for the moment.

Clearly the parser needs some attention, but right now my top priority is to just keep the program running. As a stopgap measure, what can I do to keep this from bringing down the whole program?

My first choice would be to find some way to anticipate that I'm running out of room on the stack so that I can gracefully abort the parser before the overflow happens. Failing to parse the file is an acceptable option. The second choice would be to let it happen, catch the error and log it, then continue with the rest of the data.

The parsing is happening in a Parallel.ForEach() loop. I'm willing to swap that out for some other approach if that will help.

EDIT: What would be really killer is if I could just get the size of the current thread's stack, and the position of the stack pointer. Is this possible?

EDIT 2: I finally managed to wring a sample file out of someone and trap the error in a debugger. It turns out it's not code that belongs to us at all - the exception's happening somewhere in HtmlAgilityPack. So it looks like I'm going to have to try and find a completely different tack.

carla
  • 1,970
  • 1
  • 31
  • 44
Sean U
  • 6,730
  • 1
  • 24
  • 43
  • Not sure if this will help since what exactly causes the stack overflow is not clear (paralellism shouldn't cause this: recursiveness could), but have you tried using `ParallelOptions.MaxDegreeOfParallelism` to limit the amount of concurrent calls? – Jcl Aug 02 '12 at 19:11
  • One option is to just track the current "depth" of the parse, and bail if it gets too high. – dlev Aug 02 '12 at 19:13
  • @dlev I would like more detail, though. The .NET documentation suggests that, but how do I choose an appropriate maximum depth, given that both stack frames and the call stack as a whole can have varying sizes? – Sean U Aug 02 '12 at 19:15
  • @SeanU You'd have to make an educated guess. Try creating a highly nested document, and run the parser on successively more nested versions until it blows up. Check the stack frame count at that point, and then set the limit at 2/3 or 3/5 or whatever of that depth. – dlev Aug 02 '12 at 19:40
  • May be you can catch the error. http://stackoverflow.com/questions/753841/how-to-catch-exceptions-from-a-threadpool-queueuserworkitem – MACMAN Aug 03 '12 at 03:35

2 Answers2

3

Stack has 1 MB limit by default on desktop CLR, but you can increase it.

You can use a continuation passing style to use heap instead of stack.

In C# 5.0, there's async mechanism provided by compiler that automates this process. I haven't tried this with the latest build. As mentioned by Alex, there is no support for tail-call optimization in C#, and this might be big enough of a reason to adopt F# for parsing problems. Here's some material on lexing and parsing with F#. YMMV, as demonstrated in this article.

You'd also need graph cycle detection to make your program solid in the presence of bad inputs.

As a way to collect more info, you can needle through an accumulator integer that tracks how deep is your call stack. This will not directly translate into memory consumed by said call stack, but it gives you a general idea. For example, you could throw and catch your own exception when that number is greater than some user-configurable or predefined threshold.

public void Recursive(int acc)
{
    if (acc > myLimit)
       throw new MyOverflowException(acc); 

    Recursive(acc+1);
}

and then at the call-site:

try { Recursive(0); } catch (MyOverflowException) { /* handle it*/ }

As requested, I'll link you up to the fabulous blog by Eric Lippert on this very topic.

GregC
  • 7,737
  • 2
  • 53
  • 67
  • 1
    A little detail would be nice. – John Saunders Aug 02 '12 at 19:14
  • @GregC This is something I'm considering doing as a longer-term solution. But right now I'm looking for a stopgap, and that would be a rather large refactor. – Sean U Aug 02 '12 at 19:17
  • 1
    I mean give an example of a continuation passing style, and maybe even demonstrate how that uses less stack. – John Saunders Aug 02 '12 at 19:23
  • How does C# 5 async do continuation passing style? – Peter Ritchie Aug 02 '12 at 20:48
  • @PeterRitchie http://blogs.msdn.com/b/ericlippert/archive/2010/11/01/asynchrony-in-c-5-part-three-composition.aspx – GregC Aug 02 '12 at 20:52
  • 1
    @GregC That's continuation passing style in that an asynchronous invocation (`await`) doesn't use the heap for the result, the result is passed, effectively, to a callback. I really don't think you could use `await` as a way to "automate" avoiding stack overflow exceptions. – Peter Ritchie Aug 02 '12 at 21:07
  • @GregC Eric Lippert goes into more detail on this and why this isn't quite the same as true call/cc here: http://stackoverflow.com/a/4071015/5620 But, he does call it that at one point before kinda correcting it... – Peter Ritchie Aug 02 '12 at 21:29
0

A thread crashing due to SOE will bring down the whole process and there's not much you can do about it.

As a recovery measure you could instead launch the parser as a separate process and set up an IPC mechanism to communicate with the child. That way, the child process is free to die without impacting the main process.

Tudor
  • 61,523
  • 12
  • 102
  • 142