When does stack overflow occur?

Question

Is infinite recursion the only case, or could happen for other reasons? Doesn't the stack size increase the same as a heap?

Sorry, if this question was asked before, links to them will be appreciated, if so.

Answer 1

I can’t speak on all platforms, but as it happens, I just spent some time working with Windows.exe files (I mean, actually studying their binary format), I know, in a sense, we all work with executable files here;)). I am sure that most other platforms have similar capabilities, but I am not immediately familiar with them.

Part of the file format itself includes two values ​​related to the current discussion:

typedef struct _IMAGE_OPTIONAL_HEADER { ... DWORD SizeOfStackReserve; DWORD SizeOfStackCommit; ... } IMAGE_OPTIONAL_HEADER32, *PIMAGE_OPTIONAL_HEADER32; 

From MSDN:

SizeOfStackReserve

The number of bytes to reserve for the stack. Only memory specified by a member of SizeOfStackCommit committed at boot time; the rest is available one page at a time until this reserve size is reached.

SizeOfStackCommit

The number of bytes to commit for the stack.

In other words, the linker sets the maximum size for the program stack. If you click the maximum size, you will overflow - no matter how you click the maximum size. You can write a simple program to do this in one line of code by simply highlighting one stack variable (say, an array) that is larger than the maximum stack size. Or you can do this through infinite (or finite, but very deep) recursion, or simply by allocating too many stack variables.

The Microsoft component sets this default value to 1 MB on X86 platforms (4 MB on Itanium systems). It seems small at first glance, for a modern system. However, more modern versions of Windows interpret these values ​​in a slightly different way. Instead of completely restricting the stack, it limits the physical memory that the stack will use. If your stack grows further, virtual memory will be involved, so you should still be good ... if you have enough virtual memory.

remember, that may be enough memory, even in modern systems with a huge amount of RAM and lots of virtual memory on disk. You just need to allocate really large amounts of data.

So a long story: is stack overflow possible without infinite recursion? Definitely. Is it possible? In fact, if you do not select really huge objects.

Answer 2

The stack overflows when the stack pointer is popped out of the memory block allocated by the operating system for the stack. Some operating systems will change the size of the stack as it grows (IIRC Linux does this), while in other cases the size of the stack is fixed at the beginning of the process or thread (this is done by IIRC Windows).

Possible reasons:

• Unlimited stack frames (e.g. from unlimited recursion)
• Trying to allocate large blocks from the stack
• Buffer overflow for buffers allocated on the stack

There are probably other reasons that I cannot remember.

Answer 3

This question does not indicate which stack is a "stack". So here are some answers:

Call stack

The call stack overflows whenever the number of calls in the stack overflows the amount of memory. The most common way is infinite recursion, but it is possible to have recursion that is excessive, but not infinite. For example, calculating the Ackermann function would naively tax any computer.

Languages

Stack based languages

Some languages, such as Postscript and Forth, and some virtual machines, such as the Java virtual machine, are stack based. In these languages, it may be possible to make expressions so complex that they overflow the stack.

Languages ​​without context

Context-free languages ​​are often implemented using the stack. If the lines for the code in these languages ​​become too complex, a stack overflow is possible.

Answer 4

On a laptop or desktop computer, it may be unusual to stack overflow without infinite (or very deeply nested) recursion when starting from the main thread ... however, stack overflow is not uncommon for:

• A thread code in which a small fixed-size stack has been allocated to a thread.
• Signal processing code in which the signal processing context has a small stack of fixed size.
• Code execution on embedded devices, where there is usually not enough memory.

As an example, if you register a signal handler using sigaction , if the signal handler performs any complex (i.e., deeply nested operations), it is very easy to get a stack overflow in a number of operating systems, since handlers usually get a small stack of fixed size. Similarly, if you create a thread with pthread_create , but you specify a small stacksize with pthread_attr_setstacksize , then it is very easy to achieve. On such devices with limited memory, such wireless sensors are an art to avoid.

Answer 5

My day job is related to a lot of work with LotusScript in Lotus Notes, which has fixed stack restrictions for various areas. For instance. most of the variables in the procedure / function should fit on the 32 KB stack, except that the contents of the class variables are stored on the heap.
If fixed-size variables exceed the stack size, the code will not compile.
A run-time stack overflow can occur with recursion. This is easy to achieve in LotusScript because it restricts the recursion of any single function to the 32KB stack. Because of this, I refused to use recursive QuickSort.

Answer 6

If your program exceeds the allocated stack space without infinite recursion, then you are doing something wrong.

Although this can happen if you omit some asterisks and try passing some huge buffers by value.

The memory allocated for the stack usually grows as needed within reasonable limits - I'm not sure what the upper limit is for different systems.