How Enumerable.Concat brought down a production server

TL;DR Using Enumerable.Concat to build a long sequence one item at a time is a particularly bad idea, since enumerating the items will consume a lot of stack space.

A while ago, a customer reported that our .NET application running in IIS started crashing on user registration after an application upgrade. The crash happened as the application was about to send an activation e-mail. Since there had been no changes to this particular code since the last version, this was quite a mystery. Furthermore, since the crash didn’t happen on a test server, I suspected an environmental problem. In the end, it turned out to be an environmental factor that revealed a bug in the code.

It’s of course impossible to fix something based on suspicions - you need hard evidence. After more testing on a copy of the production server, we could pinpoint the problem to updating a user in general (which happens during user registration) rather than sending e-mail - changing user settings would reliably reproduce the crash. After studying the Windows event log while doing so, I got the hard evidence I needed:

...
Faulting application name: w3wp.exe, ...
...
Exception code: 0xc00000fd
...

0xc00000fd is STATUS_STACK_OVERFLOW, i.e. a StackOverflowException was thrown. The next step was to figure out where it came from. To do that, I downloaded Debug Diagnostic Tool (DebugDiag) from Microsoft and installed it on the production server. I found a useful CodeProject article about how to use DebugDiag. While it is written for an older version than the one I installed (v2 Update 1), the only difference I found was that DebugDiag nowadays is split into two applications, DebugDiag Collection and DebugDiag Analysis.

By using DebugDiag to collect and analyze a process dump, I was able to pinpoint the location in the application code that caused the crash. The code was part of an in-memory index, and was quite innocent-looking:

var newEnum = @enum.Where(item => someItem != item).ToList();

In other words, enumerate items, exclude a particular one and create a list out of the result. What this line resulted in was the following stack trace:

...
System_Core_ni!System.Linq.Enumerable+<ConcatIterator>d__71`1[[System.__Canon, mscorlib]].MoveNext()+126 
System_Core_ni!System.Linq.Enumerable+<ConcatIterator>d__71`1[[System.__Canon, mscorlib]].MoveNext()+126 
System_Core_ni!System.Linq.Enumerable+<ConcatIterator>d__71`1[[System.__Canon, mscorlib]].MoveNext()+126 
System_Core_ni!System.Linq.Enumerable+<ConcatIterator>d__71`1[[System.__Canon, mscorlib]].MoveNext()+126 
System_Core_ni!System.Linq.Enumerable+<ConcatIterator>d__71`1[[System.__Canon, mscorlib]].MoveNext()+126 
System_Core_ni!System.Linq.Enumerable+<ConcatIterator>d__71`1[[System.__Canon, mscorlib]].MoveNext()+126 
...

ConcatIterator is a method called from Enumerable.Concat that yields results from the two enumerables that are concatenated together:

private static IEnumerable<TSource> ConcatIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second)
{
  foreach (TSource source in first)
    yield return source;
  foreach (TSource source in second)
    yield return source;
}

Concatenating enumerables is in general not a problem, nor is enumerating the result. However, in this case a one-item enumerable was extended one item at a time using Enumerable.Concat, like so:

// initial creation:
@enum = new[] { item };
// later on, done repeatedly:
@enum = @enum.Concat(new[] { itemToAppend });

And herein lies the bug. When I wrote this code, I thought of it as building a linear sequence of identifiers, but what it does is rather the opposite - it builds an unbalanced binary tree. This is fairly obvious if you think about it for a second, which I clearly didn’t, so this entire thing is a bit embarassing… Anyway, here’s an illustation of what happens:

In the first step (left), we have the initial enumerable (array) of a single item (black). When we concatenate with another enumerable (array) of one item (white), we get the tree in the middle, where the resulting enumerable (grey) refers to its two constituent enumerables. Another concatenation, and we get the tree to the right, where another level has been added. Continue concatenating, and the tree will grow quite high.

To enumerate items, ConcatIterator effectively does a depth-first traversal of the entire tree structure. And that eats as many stack frames as the tree is high, which corresponds to the number of items in the tree.

The solution was simple: Just use a regular list instead of building a super-concatenated enumerable.

There’s one more thing I’d like to share. I rarely, if ever, fix a bug without reproducing it in a test case. Given the same number of items as on the production server, I couldn’t reproduce the crash though. It was first when I increased the number of items quite a bit that I saw the crash. The explanation for this is documented in this Knowledge Base article:

In Windows Server 2008 and higher, the maximum stack size of a thread running on 32-bit version of IIS is 256 KB, and on an x64 server is 512 KB.

However, the default stack size of a thread in Windows is 1 MB, and that’s what I got when running my test case.

By the way, the reason the application worked on the test server? Fewer items in the in-memory index!