Fun With Stack Overflow Errors

Take a look at this C code:

Copy-paste it, replace n  with 99999999, and then compile and run it. You should get an error similar to this:

unless you’re from the future and you’ve got the latest BEZ-9000   as your rig.

Why did I get this error?

The program asked the operating system to allocate an array of size a dizzilian bytes on the stack. And since the OS couldn’t do that, it terminated the process.

Now replace the array size with some unthreatening number, like 5, and then compile and run it again. You shouldn’t get any error this time.

So there has to be a rough boundary between 5 and a dizzilian, such that the program we wrote crashes if the hardcoded array size is greater than that limit, and runs fine for sizes below it.

Cool, how can we find that limit?

Simple, just compile the program with numbers in the series 5, 6, 7, ..., dizzilian as the value of n, and at some point, you should find the limit at which the program starts crashing.

Ok, but isn’t a dizzilian a very big number?

Good point. Every iteration of our method takes around a second (compiler invocation). Compiling it a dizzilian times will take a whole lot of seconds, we don’t have that much time.

So what do we do?

A binary search.

Huh?/Aha!

We’ll WAP which performs a binary search on the range [5,dizzilian] and returns the limit we’re talking about.

OK, where’s the code

This is the code I used:

This is how the code works:

  1. failsForSize takes a number, replaces the %d in template.c with that number, writes the new program to t.c, compiles it and runs it. If the program crashes, it returns True. It’s a neat little function which encapsulates the test we want to run on numbers in the range under consideration.
  2. BinarySearch.Range.endFirst is a general purpose binary search function I wrote which takes 3 arguments a, b (numbers) and pred(a predicate function). It assumes that there’s a limit c between a and b such that pred returns True for all numbers above c and False for the rest, it finds and returns that limit.
  3. failsForSize increments the global variable cC every time it’s called. maxArrSize uses its value to keep track of how many times the compiler is run for each binary search iteration.
what’s the output of this code?

The function call maxArrSize(5) prints this to the screen:

So this limit is just some random number?

No, it isn’t. I called maxArrSize with argument 50 and got back 8379000 ± 1400  as result. This is the number of bytes of stack memory available to our program over and above the main function ( main isn’t the actual starting point of a C program, there’s some stuff below it as well). That’s around (8182 ± 1.3) KB. The amount of stack memory available to the processes on my system is 8192KB (or 8MB), as given by the command ulimit -s. So the results we obtained from our experiment do make sense.

I’ll be doing a followup post expanding upon the stuff we talked about here. Subscribe to the mailing list if you want to recieve email notification of that post. (the form is available in the side bar or the menu, depending on your device)

See you later 

 

 

 

1 thought on “Fun With Stack Overflow Errors

  1. It appears that the 10KB difference between the stack limit and the memory available to my program isn’t because of plumbing below the main function. The program can’t allocate more than 8182KB on the stack even if I bypass the main function.

    Please let me know if you know where that 10KB is going.

Leave a Reply

Your email address will not be published. Required fields are marked *