Shared Overflow

I encountered my first stack overflow in a long time the other day. I’m going to name the situation that I ran into a shared_ptr cascade, a situation can probably best be illustrated by the following:

struct Node
{
   std::shared_ptr<Node> m_next_p;
   int m_data;
};

void shared_ptr_cascade
{
   const auto numNodes = 100000;

   auto head_p = std::make_shared<Node>();
   auto cur_p = head_p;
   for (auto i = 0; i < numNodes; ++i)
   {
      cur_p->m_next_p = std::make_shared<Node>();
      cur_p = cur_p->m_next_p;
   }
   cur_p = nullptr;

   head_p = nullptr;
}

Notice the last line of shared_ptr_cascade, that bit about head_p = nullptr. Using both Microsoft’s compiler and Clang I get a stack overflow right there. Releasing the pointer to the head node causes a cascade of calls to ~shared_ptr with each call calling the destructor for the m_next_p member in turn until our stack is thousands of calls deep and the OS steps in and kills the program.

Of course the actual situation where I encountered this was not so straightforward and involved some timing complications (we had to release the head pointer after another thread had written lots of nodes into the list1 in order for the crash to happen) and some issues unique to our STM implementation (the head_p in this case was sticking around in the transaction until the commit was done, thus obscuring the source of the problem since we got the overflow at the end of the STM commit code instead of where we wrote nullptr into head_p). It had been a long time since I’d encountered a stack overflow and I have to admit that it did take a bit of time to realize that’s what was going on.

So the next question is: how do we fix it? Recursion is causing a problem (a worse problem that just performance degradation which is the usual problem caused by recursion in C++) so we need to convert it to iteration. In the example above the solution is to change the head_p = nullptr line to

while (head_p)
{
   head_p = head_p->m_next_p;
}

So that the stack only ever goes one level deeper with a call to ~shared_ptr instead of one level for each link in the chain. With this change we can deal with as many nodes as we want up to the point where memory exhaustion kicks in.

So the moral of the story is that while RAII is great, it does have a sharp edge that one needs to be wary of. I seem to have cut myself on it in this instance.


  1. Yes, I know, we’re not supposed to be using linked lists anymore. But in this case it makes sense, I promise.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: