1

So I wrote a toy C program that would intentionally cause a stack overflow, just to play around with the limits of my system:

#include <stdio.h>

int kefladhen(int i) {
    int j = i + 1;
    printf("j is %d\n",j);
    kefladhen(j);
}

int main() {
    printf("Hello!:D\n");
    kefladhen(0);
}

I was surprised to find that the last line printed before a segmentation fault was "j is 174651". Of course the exact number it got to varied a little each time I ran it, but in general I'm surprised that 174-thousand odd stack frames are enough to exhaust the memory for a process on my 4GB linux laptop. I thought that maybe printf was incurring some overhead, but printf returns before I call kefladhen() recursively so the stack pointer should be back where it was before. I'm storing exactly one int per call, so each stack frame should only be 8 bytes total, right? So 174-thousand odd of them is only about a megabyte and a half of actual memory used, which seems way low to me. What am I misunderstanding here?

Tneuktippa
  • 1,645
  • 3
  • 15
  • 25
  • how big is your default stack size? it's usually somewhere between 1MB and 2MB... – Mitch Wheat Apr 30 '12 at 10:52
  • 1
    Note that the stack stores more than just your local variables. The return adress, for instance. –  Apr 30 '12 at 10:57
  • 1
    Try, at the bash prompt, `ulimit -a` (or `ulimit -s` for just the stack size). Also you may want to verify the size of your ints with `sizeof (int)`. – pmg Apr 30 '12 at 10:59
  • I bet you even didn't compile with `-O3`, `-Os` or so, because I don't manage to get it crashed with your program. Your program is a standard exercise for tail recursion, every decent compiler should transform this into an iterative version without problem. – Jens Gustedt Apr 30 '12 at 11:40

3 Answers3

8

...but in general I'm surprised that 174-thousand odd stack frames are enough to exhaust the memory for a process on my 4GB linux laptop...

Note that the stack isn't the general memory pool. The stack is a chunk pre-allocated for the purpose of providing the stack. It could be just 1MB out of those 4GB of memory on the machine. My guess is your stack size is about 1.3MB; that would be enough for 174,651 eight-byte frames (four bytes for return address, four bytes for the int).

T.J. Crowder
  • 1,031,962
  • 187
  • 1,923
  • 1,875
2

I think that the key misunderstanding here is that the stack does not grow dynamically by itself. It is set statically to a relatively small number, but you can change it in runtime (here is a link to an answer explaining how it is done with setrlimit call).

Community
  • 1
  • 1
Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
1

Others have already discussed the size and allocation of the stack. The reason why the "the exact number it got to varied a little each time I ran it" has to do with cache performance on multi-threaded systems.

In general, you can expect the memory pre-allocated for the stack to be page aligned. However, the starting stack pointer will vary from thread-to-thread/process-to-process/task-to-task. This is to help avoid cache line flushes, invalidations and loads. If all the tasks/threads/processes had the same virtual address for the stack pointer, you would expect that there would be more cache collisions whenever a context switch occurs. In an attempt to reduce this likelihood, many OSes will have the starting stack pointer somewhere within the starting stack page, but not necessarily at the very top, or at the same position. Thus, when a context switch occurs and a subsequent stack access occurs, there is ...

  1. a better chance the variable will already be in the cache
  2. a better chance that there will not be a cache collision

Hope this helps.

Sparky
  • 13,505
  • 4
  • 26
  • 27