Limit of the stack

stack

Recently I've tested the limit of a stack on three devices with different OSs (by limit, I mean the maximum number of levels that can the stack have), and I noticed that every time when I hit 2^16 levels it gives me overflow error, and when I put 2^16-1 it works properly.

So my question is – is that true? Does the stack has the maximum limit 2^16-1 by definition or it depends on the OS?

Best Answer

It is strongly operating system specific (& computer specific) and on some OSes you have some ways to configure (and even increase) the limit. It is even compiler specific (or your-programming-language-implementation specific), since some compilers (including recent GCC for some limited kind of C code) are able to optimize some tail calls.

(some programming language specifications require tail call optimizations, e.g. R5RS)

I'm not sure your question makes sense (and certainly not your 216 limit). On my Linux desktop (Debian/Sid/x86-64, Linux 4.9 kernel, 32Gb RAM, Intel i5-4690S), I might have a call stack of up to 8 megabytes (and I could increase that limit, if I really wanted to).

Multi-threading and ASLR are making your question much more complex. See e.g. pthread_attr_setstack(3). Read also about split stacks (often used by Go implementations) and about continuation passing style. See also this answer.

For what it is worth, I just tried the following C99 (and also C11) code:

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

void recfun(int x, int d) {
  printf("start recfun x=%d d=%d\n", x, d);
  fflush(NULL);
  if (d>0)
    recfun(x+1, d-1);
  printf("end recfun x=%d d=%d\n", x, d);
}

int main(int argc, char**argv) {
  int md = argc>1?atoi(argv[1]):10000;
  printf ("start md=%d\n", md);
  recfun(0, md);
  printf("end md=%d clock=%ld µs\n", md, clock());
}    
// eof recur.c

and I was able to run that recur program (compiled with GCC 6 as gcc -Wall -O recur.c -o recur) as recur 161000 (so much above your 216 limit). With recur 256000 it also worked. With recur 456000 it crashed (with a stack overflow for level x=272057). I don't have the patience for other tests. Try that on your computer. Don't forget to ask for optimizations.

A rule of thumb (for desktops, laptops, tablets) might be to keep your call stack below one megabyte.

By passing also -fstack-usage to gcc I'm getting the following recur.su file (numbers are in bytes, consistent with my 8Mb stack limit intuition; don't forget the main call frame, and more importantly the initial stack layout, installed by the kernel when doing execve(2)..., for crt0):

 recur.c:5:10:recfun    32  static
 recur.c:13:9:main  16  static

PS. My Arduino has a Atmega328 with only 2Kbytes of RAM, so certainly cannot recur that much. I guess only a few hundreds stack frames are at most practically possible on Arduinos.

Related Topic