Why does the call stack have a static maximum size?

Question

Having worked with a few programming languages, I've always wondered why the thread stack has a predefined maximum size, instead of expanding automatically as required. 

In comparison, certain very common high level structures (lists, maps, etc.) which are found in most programming languages are designed to grow as required while new elements are added, being limited in size only by available memory, or by computational limits (e.g. 32 bit addressing).

I'm not aware though of any programming languages or runtime environments where the maximum stack size isn't pre-limited by some default or compiler option. This is why too much recursion will result very quickly in a ubiquitous stack overflow error/exception, even when only a minimal percentage of the memory available to a process is used for the stack.

Why is it the case that most (if not all) runtime environments set a maximum limit for the size a stack can grow at runtime?

Answer 1

It's possible to write an operating system that doesn't require stacks to be contiguous in address space. Basically you need some extra messing about in the calling convention, to ensure that:

1. if there isn't enough space in the current stack extent for the function you're calling, then you create a new stack extent and move the stack pointer to point to the start of it as part of making the call.

2. when you return from that call you transfer back to the original stack extent. Most likely you retain the one created at (1) for future use by the same thread. In principle you could release it, but that way lie rather inefficient cases where you keep hopping back and forth across the boundary in a loop, and every call requires memory allocation.

3. setjmp and longjmp, or whatever equivalent your OS has for non-local transfer of control, are in on the act and can correctly move back to the old stack extent when required.

I say "calling convention" -- to be specific I think it's probably best done in a function prologue rather than by the caller, but my memory of this is hazy.

The reason that quite a few languages specify a fixed stack size for a thread, is that they want to work using the native stack, on OSes that don't do this. As everyone else's answers say, under the assumption that each stack needs to be contiguous in address space, and cannot be moved, you need to reserve a specific address range for use by each thread. That means choosing a size up front. Even if your address space is massive and the size you choose is really large, you still have to choose it as soon as you have two threads.

"Aha" you say, "what are these supposed OSes that use non-contiguous stacks? I bet it's some obscure academic system of no use to me!". Well, that's another question that fortunately is already asked and answered.

Answer 2

Those data structures typically have properties the OS stack has not:

• Linked lists don't require contiguous address space. So they can add a piece of memory from wherever they want when they grow.

• Even collections that need contiguous storage, like C++'s vector, have an advantage over OS stacks: They can declare all pointers/iterators invalid whenever they grow. On the other hand the OS stack needs to keep pointers to the stack valid until the function to whose frame the target belongs returns.

A programming language or runtime can choose to implement their own stacks which are either non-contiguous or movable to avoid the limitations OS stacks. Golang uses such custom stacks to support very high numbers of co-routines, originally implemented as non-contiguous memory and now via movable stacks thanks to pointer tracking (see hobb's comment). Stackless python, Lua and Erlang might also use custom stacks, but I didn't confirm that.

On 64-bit systems you can configure relatively large stacks with relatively low cost, since address space is plenty and physical memory only gets allocated when you actually use it.

Answer 3

In practice, it's difficult (and sometimes impossible) to grow the stack. To understand why requires some understanding of virtual memory.

In Ye Olde Days of single-threaded applications and contiguous memory, three were three components of a process address space: the code, the heap, and the stack. How those three were laid out depended on the OS, but generally the code came first, starting at the bottom of memory, the heap came next and grew upwards, and the stack started at the top of memory and grew downwards. There was also some memory reserved for the operating system, but we can ignore that. Programs in those days had somewhat more dramatic stack overflows: the stack would crash into the heap, and depending on which got updated first you'd either work with bad data or return from a subroutine into some arbitrary part of memory.

Memory management changed this model somewhat: from the program's perspective you still had the three components of a process memory map, and they were generally organized the same way, but now each of the components was managed as an independent segment and the MMU would signal the OS if the program tried to access memory outside a segment. Once you had virtual memory, there was no need or desire to give a program access to its entire address space. So the segments were assigned fixed boundaries.

So why isn't it desirable to give a program access to its full address space? Because that memory constitutes a "commit charge" against the swap; at any time any or all of the memory for one program might have to be written to swap to make room for another program's memory. If every program could potentially consume 2GB of swap, then either you'd have to provide enough swap for all of your programs or take the chance that two programs would need more than they could get.

At this point, assuming sufficient virtual address space, you could extend these segments if needed, and the data segment (heap) does in fact grow over time: you start out with a small data segment, and when the memory allocator requests more space when it's needed. At this point, with a single stack, it would have been physically possible to extend the stack segment: the OS could trap the attempt to push something outside of the segment and add more memory. But this isn't particularly desirable either.

Enter multi-threading. In this case, each thread has an independent stack segment, again fixed size. But now the segments are laid out one after another in the virtual address space, so there's no way to expand one segment without moving another -- which you can't do because the program will potentially have pointers to memory living in the stack. You could alternatively leave some space between segments, but that space would be wasted in almost all cases. A better approach was to put the burden on the application developer: if you really needed deep stacks, you could specify that when creating the thread.

Today, with a 64-bit virtual address space, we could create effectively infinite stacks for effectively infinite numbers of threads. But again, that isn't particularly desirable: in almost all cases, a stack overlow indicates a bug with your code. Providing you a 1 GB stack simply defers discovery of that bug.

Answer 4

The stack having a fixed maximal size is not ubiquitous.

It is also hard to get right: stack depths follow a Power Law Distribution, which means that no matter how small you make the stack size, there will still be a significant fraction of functions with even smaller stacks (so, you waste space), and no matter how large you make it, there will still be functions with even larger stacks (so you force a stack overflow error for functions that have no error). In other words: whatever size you choose, it will always be both too small and too large at the same time.

You can fix the first problem by allowing stacks to start small and grow dynamically, but then you still have the second problem. And if you allow the stack to grow dynamically anyway, then why put an arbitrary limit on it?

There are systems where stacks can grow dynamically and have no maximum size: Erlang, Go, Smalltalk, and Scheme, for example. There are plenty of ways to implement something like that:

• movable stacks: when the contiguous stack cannot grow anymore because there is something else in the way, move it to another location in memory, with more free space
• discontiguous stacks: instead of allocating the entire stack in a single contiguous memory space, allocate it in multiple memory spaces
• heap-allocated stacks: instead of having separate memory areas for stack and heap, just allocate the stack on the heap; as you noticed yourself, heap-allocated data structures tend to have no problems growing and shrinking as needed
• don't use stacks at all: that is also an option, e.g. instead of keeping track of function state in a stack, have the function pass a continuation to the callee

As soon as you have powerful non-local control-flow constructs, the idea of a single contiguous stack goes out the window anyway: resumable exceptions and continuations, for example, will "fork" the stack, so you actually end up with a network of stacks (e.g. implemented with a spaghetti stack). Also, systems with first-class modifiable stacks, such as Smalltalk pretty much require spaghetti stacks or something similar.

Answer 5

The maximum stack size is static because that is the definition of "maximum". Any sort of maximum on anything is a fixed, agreed-upon limiting figure. If it behaves as a spontaneously moving target, it isn't a maximum.

Stacks on virtual-memory operating systems do in fact grow dynamically, up to the maximum.

Speaking of which, it doesn't have to be static. Rather, it can be configurable, on a per-process or per-thread basis, even.

If the question is "why is there a maximum stack size" (an artificially imposed one, usually a lot less than available memory)?

One reason is that most algorithms do not require a tremendous amount of stack space. A large stack is an indication of a possible runaway recursion. It's good to stop runaway recursion before it allocates all available memory. A problem that looks like runaway recursion is degenerate stack use, perhaps triggered by an unexpected test case. For instance, suppose a parser for a binary, infix operator works by recursing on the right operand: parse first operand, scan operator, parse rest of the expression. This means that the stack depth is proportional to the length of the expression: a op b op c op d .... A huge test case of this form will require a huge stack. Aborting the program when it hits a reasonable stack limit will catch this.

Another reason for a fixed maximum stack size is that the virtual space for that stack can be reserved via a special kind of mapping, and thus guaranteed. Guaranteed means that the space won't be given to another allocation which the stack will then collide with it before hitting the limit. The maximum stack size parameter is required in order to request this mapping.

Threads need a maximum stack size for a similar reason to this. Their stacks are dynamically created and cannot be moved if they collide with something; the virtual space has to be reserved upfront, and a size is required for that allocation.

Answer 6

The OS has to give a contiguous block when a stack is requested. The only way it can do that is if a maximum size is specified.

For example, let's say memory looks like this during the request (Xs represent used, Os unused):

XOOOXOOXOOOOOX

If a request for a stack size of 6, the OS answer will answer no, even if more than 6 is available. If a request for a stack of size 3, the OS answer will be one of the areas of 3 empty slots (Os) in a row.

Also, one can see the difficulty of allowing growth when the next contiguous slot is occupied.

The other objects that are mentioned (Lists, etc.) do not go on the stack, they end up on the heap in non-contiguous or fragmented areas, so when they grow they just grab space, they do not require contiguous as they are managed differently.

Most systems set a reasonable value for stack size, you can override it when the thread is constructed if a bigger size is required.

Answer 7

On linux, this is purely a resource limit that exists to kill runaway processes before they consume harmful amounts of the resource. On my debian system, the following code

#include <sys/resource.h>
#include <stdio.h>

int main() {
    struct rlimit limits;
    getrlimit(RLIMIT_STACK, &limits);
    printf("   soft limit = 0x%016lx\n", limits.rlim_cur);
    printf("   hard limit = 0x%016lx\n", limits.rlim_max);
    printf("RLIM_INFINITY = 0x%016lx\n", RLIM_INFINITY);
}

produces the output

   soft limit = 0x0000000000800000
   hard limit = 0xffffffffffffffff
RLIM_INFINITY = 0xffffffffffffffff

Note, that the hard limit is set to RLIM_INFINITY: The process is allowed to raise its soft limit to any amount. However, as long as the programmer has no reason to believe that the program really needs unusual amounts of stack memory, the process will be killed when it exceeds a stack size of eight mebibytes.

Due to this limit, a runaway process (unintended infinite recursion) is killed a long time before it begins to consume so large amounts of memory that the system is forced to start swapping. This can make the difference between a crashed process and a crashed server. However, it does not limit programs with a legitimate need for a large stack, they just need to set the soft limit to some appropriate value.

---

Technically, stacks do grow dynamically: When the soft-limit is set to eight mebibyte, that does not mean that this amount of memory has actually been mapped yet. This would be rather wasteful as most programs never get anywhere near their respective soft-limits. Rather, the kernel will detect accesses below the stack, and just map in memory pages as needed. Thus, the only real limitation on stack size is available memory on 64 bit systems (address space fragmentation is rather theoretical with a 16 zebibyte address space size).