10

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?

  • 5
    here i mean by limit the maximum number of levels that can the stack have whats a level? – tkausl Jan 26 '17 at 13:57
  • 1
    Possible duplicate of Why is call stack not implemented as a dynamic array in modern OS? – gnat Jan 26 '17 at 13:59
  • 3
    How are you testing it? Are you using a 2-byte (dword) as input? – pro3carp3 Jan 26 '17 at 14:04
  • 6
    Which programming language are you using? Such a sharp limit at a fixed number indicates it's a deliberate limitation by your language specific runtime and not by the stack size the OS allocated. For example python seems to enforce a limit of 1000 by default to prevent you from hitting a real stack overflow (recovering from a real stack overflows is hard) – CodesInChaos Jan 26 '17 at 15:15
  • 1
    Possible duplicate of Why does the call stack have a static maximum size? – user22815 Jan 26 '17 at 18:52
20

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.

3

Stack size for the main thread of a process Windows is set by the linker. The default is 1MB but can be adjusted with the /STACK switch. Threads created later can use the dwStackSize parameter of the CreateThread function.

So.. if you're testing various Windows OS's, they've all had the same default stack size since at least NT4.0.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.