• entries
    58
  • comments
    218
  • views
    114343

Christmas Allocators

Sign in to follow this  

1143 views

This is a heartwarming Christmas tale of why you should not try to get fancy with custom allocators. Although the protagonist of our story, Developer A, probably feels like I've beat this one to death, Developer B has requested that I reiterate the details of this incident, and I am more than happy to oblige.

I remember it like it was yesterday. While working on TheProject, Developers A and B and I were happily making use of the SC++L to avoid manual memory allocations whenever possible. As I recall, Developer A happened around this time to stumble upon the _malloca function, which is designed to allow the allocation of memory on the stack instead of on the heap. Being an enterprising young man, Developer A immediately saw the practical uses of such a function; what a perfect way to make a quick optimization across the TheProject.

He theorized that by using this function inside of a placement new, he could set up an allocator for std::vector and std::auto_ptr to allocate objects on the stack and gain a modest performance boost. Of course, at this point I've given you everything you need to know to figure out why this turned out to be a hilarious idea, but at the time it seemed like a perfectly reasonable proposal, so work was quickly begun.


void* operator new(std::size_t size, stackalloc_t stackalloc)
{
void* p = _malloca(size);
if(!p)
throw std::bad_alloc();

return p;
}



I'll pause for a moment to give you a chance to figure out what went wrong.

...

OK, ready? Let's move on with our tale.

Work on the stack allocator was finished quickly and the results put into production across TheProject. We didn't bother profiling the changes; the performance gained, if any, would be modest, and it wasn't really worth our time. Things worked well for one release cycle, and then things started to hit the fan. Bug reports started trickling in, targeting areas across the library. They were few and far between, however, and almost impossible to reproduce. For one thing, they only ever showed up in the release version of the library, while us developers were using debug mode almost exclusively. For another, they often showed up in some of the hairiest corners of the API, and so we chalked them up to other implementation details. Nobody even suspected the innocent looking stack allocator, who sat in the corner quietly and did his job without a peep.

It wasn't until a few months later that I began to piece together the true nature of the situation. While tracking down yet another random crash bug, I managed to isolate the issue down to a little sliver of code that made use of our stack_vector, a specialized version of std::vector that used our custom allocator. I was surprised to learn that if replaced the stack_vector with it's more legitimate older brother std::vector, all the crashes surrounding that method instantly vanished. I immediately began to suspect our stack_vector, but as anyone will tell you, stack bugs can be extremely fickle and cause problems in other, unrelated sections of code, so I had my doubts. Besides, if the stack_vector really wasn't working, we would have seen widespread problems all across the library, no?

All the same, I took a look at the stack_vector implementation. Nothing stood out as obviously broken, but I still felt uneasy, so I started a separate, blank project and duplicated the allocator code there. All seemed to work perfectly. I was just about to write it off as a dead end when I played on a hunch and changed the configuration to Release mode. Blam! Immediately, the program crashed, and I knew I had found the culprit. The only question was, what the heck was actually wrong with it?

Logging onto IRC, I quickly found Developer A and explained the situation I had uncovered. (Developer B was nowhere to be found; God only knows what HE was doing during all of this.) After sending him my test application, we immediately began working on the issue together, throwing ideas back and forth across IRC as they occurred to us. "Hey, I just noticed that vtable of derived classes don't get initialized when using the allocator." "Oh? I just finished examining the memory of an array of objects allocated, and things seem to be fine here."

So it went, back and forth, until we were just about at the end of our ropes. You're probably laughing right now at how foolish we were, but things aren't always so easy to see when you have preconceived notions of how something works. Anyway, some helpful soul on IRC piped up and said "hey guys, you DO realize that _malloca allocates on the STACK, right?" "Of course", we replied, smugly thinking to ourselves "What could this guy tell us that we don't already know?" "Well, how is operator new supposed to return a pointer to memory ALLOCATED ON THE STACK?"

We sat there silently for a few minutes, unwilling to face the obvious truth. This can't be right. This thing has caused us so much trouble. How could it be that simple? He was right of course, and we knew it. It explained everything. Even the release mode only issue, which was caused by the fact that _malloca allocates on the HEAP in debug mode, and on the STACK in release mode. After the shock wore off, we found ourselves laughing hysterically. Of course, we still wonder to this day how anything managed to work at all with our allocator, which should have been returning invalid pointers EVERY time.

The moral of this story is... well, there is no moral. I guess you could say "don't return pointers to local stack memory", but if you'd told us that several months ago we would have nodded and said "yeah, uh-huh, we know that already." The question is, did YOU see the problem coming? I know I didn't.

Merry Christmas!
Sign in to follow this  


2 Comments


Recommended Comments

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now