Why are stackoverflow errors chaotic?

Question

This simple C program rarely terminates at the same call depth:

#include <stdio.h>
#include <stdlib.h>

void recursive(unsigned int rec);

int main(void)
{
  recursive(1);
  return 0;
}

void recursive(unsigned int rec) {
    printf("%u\n", rec);
    recursive(rec + 1);
}

What could be the reasons behind this chaotic behavior?

I am using fedora (16GiB ram, stack size of 8192), and compiled using cc without any options.

EDIT

• I am aware that this program will throw a stackoverflow
• I know that enabling some compiler optimizations will change the behavior and that the program will reach integer overflow.
• I am aware that this is undefined behavior, the purpose of this question is to understand/get an overview of the implementation specific internal behaviors that might explain what we observe there.

The question is more, given that on Linux the thread stack size is fixed and given by ulimit -s, what would influence the available stack size so that the stackoverflow does not always occur at the same call depth?

EDIT 2 @BlueMoon always sees the same output on his CentOS, while on my Fedora, with a stack of 8M, I see different outputs (last printed integer 261892 or 261845, or 261826, or ...)

Answer 1

Change the printf call to:

printf("%u %p\n", rec, &rec);

This forces gcc to put rec on the stack and gives you its address which is a good indication of what's going on with the stack pointer.

Run your program a few times and note what's going on with the address that's being printed at the end. A few runs on my machine shows this:

261958 0x7fff82d2878c
261778 0x7fffc85f379c
261816 0x7fff4139c78c
261926 0x7fff192bb79c

First thing to note is that the stack address always ends in 78c or 79c. Why is that? We should crash when crossing a page boundary, pages are 0x1000 bytes long and each function eats 0x20 bytes of stack so the address should end with 00X or 01X. But looking at this closer, we crash in libc. So the stack overflow happens somewhere inside libc, from this we can conclude that calling printf and everything else it calls needs at least 0x78c = 1932 (possibly plus X*4096) bytes of stack to work.

The second question is why does it take a different number of iterations to reach the end of the stack? A hint is in the fact that the addresses we get are different on every run of the program.

1 0x7fff8c4c13ac
1 0x7fff0a88f33c
1 0x7fff8d02fc2c
1 0x7fffbc74fd9c

The position of the stack in memory is randomized. This is done to prevent a whole family of buffer overflow exploits. But since memory allocations, especially at this level, can only be done in multiple of pages (4096 bytes) all initial stack pointers would be aligned at 0x1000. This would reduce the number of random bits in the randomized stack address, so additional randomness is added by just wasting a random amount of bytes at the top of the stack.

The operating system can only account the amount of memory you use, including the limit on the stack, in whole pages. So even though the stack starts at a random address, the last accessible address on the stack will always be an address ending in 0xfff.

The short answer is: to increase the amount of randomness in the randomized memory layout a bunch of bytes on the top of the stack are deliberately wasted, but the end of the stack has to end on a page boundary.